论文部分内容阅读
在无线传感器网络中,虚拟骨干网技术可使得平面网络层次化,从而简化网络路由、数据传输和网络维护.提出一个2-连通r-hop k-支配虚拟骨干网构造算法,本算法通过多次构造r-hop独立集实现k-支配,添加节点使其连通,最终扩展为2-连通支配集,既保证了支配集自身的容错性(2-连通),又保证了被支配节点的容错性(k-支配),本文从理论和仿真上对算法的复杂度、近似比和算法性能做了全面的分析和验证.
In wireless sensor networks, the virtual backbone technology can make the planar network hierarchical, thus simplifying network routing, data transmission and network maintenance.This paper proposes a 2-connected r-hop k-dominated virtual backbone network construction algorithm, Constructing r-hop independent sets to achieve k-dominance, adding nodes to make them connect, and eventually expanding into 2-connected dominating sets not only ensure the fault tolerance of the dominating set itself (2-connected), but also ensure the fault tolerance of the dominating node (k-dominance). In this paper, the complexity, approximate ratio and algorithm performance of the algorithm are analyzed and verified theoretically and emulatively.