基于蜂窝结构的传感器网络覆盖问题求解算法

在无线传感器网络中,求解能够完全覆盖目标区域的最小覆盖集是个NP难问题.在传感器节点数目较多时,目前只能通过近似算法求解.蜂窝结构是覆盖二维平面的最佳拓扑结构,但不能直接用于求解无线传感器网络的覆盖问题.提出了一种基于蜂窝结构的覆盖问题求解算法,在该算法迭代求解过程的每一阶段,选出一个节点加入到初始为空的节点集合中,并使得该节点集合的拓扑结构接近于蜂窝结构,直至该节点集合成为覆盖集.该算法在最坏情况下的时间复杂度为O(n3),这里n为传感器节点总数.实验结果表明该算法可在很短的时间内执行完,在所得覆盖集的大小方面要优于现有的覆盖问题求解算法.

An Algorithm for the Cover Problem Based on Cellular Structure in Wireless Sensor Networks

In wireless sensor networks, network lifetime can be effectively extended by scheduling some sensor nodes into sleep mode while keeping the target region fully covered by other active nodes. Finding a minimum cover set that can completely cover the target region is an NP-hard problem. When the number of sensor nodes is large, the cover problem can be only solved by approximation algorithm now. Cellular structure is the optimal topologic structure to cover a two-dimensional plane. But it can’t be directly applied to the cover problem in wireless sensor networks. An algorithm for the cover problem based on cellular structure is proposed. In each stage of the iterative construction process of this algorithm, a node is selected into a set which is initially empty while keeping the topologic structure of this set close to the cellular structure. This process is repeated until this node set becomes a cover set. The worst-case time complexity of this algorithm is O(n3), where n is the total number of sensor nodes in the network. Simulation results show that this algorithm can obtain a cover set in very short time, and outperforms existing algorithms for the cover problem with respect to the size of the obtained cover set.