Energy conservation algorithms for maintaining coverage and connectivity in wireless sensor networks

Energy conservation, coverage and connectivity are three critical application requirements in wireless sensor networks, especially in sensor networks for vehicular applications. Related researches have either concerned coverage, connectivity and energy conservation separately or required sensing/transmission range restrictions. In this study, the authors aim to maximise the network lifetime by redundant sensor nodes, while maintaining coverage and connectivity simultaneously, without any sensing or transmission range restriction. We propose maximum disjoint sets for maintaining coverage and connectivity (MDS-MCC) problem and the authors prove it is NP-complete. We also present two algorithms to solve MDS-MCC, Heuristic Algorithm and Network Flow Algorithm. We analyse and compare the performance of these two algorithms through simulations. According to several metrics, the authors give some suggestions of designing a sensor network. Furthermore, we study MDS-MCC problem under some special conditions, and an important theoretical result is obtained while designing a sensor network. As well as aiming to design an energy conservation sensor network, the present work can also be applied in applications requiring fault tolerance by redundancy.