An Algorithm for Minimal Connected Cover Set Problem in Wireless Sensor Networks

Reducing power consumption to extend network lifetime is one of the most important challenges in designing wireless sensor networks. One promising approach to conserving system energy is to keep only a minimal number of sensors active and put others into low-powered sleep mode, while the active sensors can maintain the communication connectivity and cover the target region completely. The problem of computing such minimal active sensor set is NP-hard. In this paper, a centralized Voronoi tessellation (CVT) based approximate algorithm is proposed to construct a near optimal cover set of active sensors required to cover the target region completely. The communication graph induced by the cover set computed by CVT algorithm is connected if sensor’s communication radius is at least twice of its sensing radius. In case of sensor’s communication radius is smaller than twice of its sensing radius, a minimum spanning tree (MST) based connection algorithm is proposed to ensure the communication connectivity of the cover set. Finally, the performance of the proposed algorithm is evaluated through theoretical analysis and extensive numerical experiments. Experimental results show that the proposed algorithm outperforms the greedy algorithm in terms of the runtime and the size of the constructed connected cover set.