传感器网络中最小k-连通m-控制集问题的近似算法

Approximation Algorithm for Minimum k-connected m-dominating Set Problem in Wireless Sensor Networks

在当前无线传感器网络的相关研究中,虚拟骨干网的构造引起广泛的关注.通过引进虚拟骨干网来设计路由协议,使得路由更加可靠和高效,从而减少广播风暴.无线传感器网络中具有容错功能的虚拟骨干网的构造可转化为圆盘图中的最小k-连通m-控制集问题.本文研究了具有不同传输半径的双向圆盘图中的最小k-连通m-控制集问题,给出了一个构造最小k-连通m-控制集的多项式时间近似算法,理论分析表明该算法具有较好的近似比.最后,在不同的网络拓扑上进行了仿真实验,仿真结果进一步验证了算法的有效性.

The construction of virtuM backbone network in wireless sensor network has caused much attention in current research. With the introduction of virtual backbone network, routing can be more robust and efficiently, hence the broadcasting storm can be alleviated in wireless sensor network. The design of fault tolerant virtual backbone network in wireless sensor network can be converts to a minimum k-connected m-dominated set problem in disk graph. In this paper, we consider the minimum k-connected m-dominated set problem in disk graph with different transmission ranges. We propose a polynomial time approximation algorithm to construct a minimum k-connected m-dominating set in disk graph, and the theoretical analysis shows that our algorithm has better performance ratio. Besides theoretical analysis, simulations are carried out on different network topologies to validate the effectiveness of the method presented.