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(n\+3), 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.