A Distributed Approximate Algorithm for Minimal Connected Cover Set Problem in Sensor Networks

For wireless sensor networks, it is an effective approach for energy conservation in wireless sensor networks to keep the most of redundant sensors asleep while the remaining nodes stay active to maintain both sensing coverage and network connectivity, i.e., to form the minimal connected cover set. A novel concept named "square grid partition" is proposed, and based on the good characteristics of "square grid partition", a new distributed approximate algorithm for constructing the Minimal Connected Cover Set is presented, in which, Sink partitions its area of interest into square grids firstly, and then broadcasts the partition information to all the sensors in the whole network. According to those received partition information of the area of interest, each sensor node will construct the minimal connected cover set of G through information exchanges among its neighbors only. Algorithm analysis and simulation results show that, the newly given algorithm outperforms the traditional similar algorithms in terms of the time complexity and the size of constructed connected cover set.