Low-Overhead Dominating Set based Algorithms for Maximizing Lifetime in Wireless Sensor Networks

In wireless sensor networks, connected dominating set (CDS) has become a key technique to identify redundant nodes and extend network lifetime. Most CDS-based algorithms focus on building the minimal CDS to find as many redundant nodes as possible. However, role rotation is not considered so that the dominating nodes will run out of energy much faster than the non-dominating nodes. Existing CDS-based algorithms for maximizing network lifetime rely on the up-to-date remaining energy level (REL) information within h-hop neighborhood to rotate node roles iteratively. Furthermore, global time synchronization is required to synchronize every round. The overhead on REL updating and time synchronization can lead to energy waste and packet collision. In this paper, we first propose a randomized rotation algorithm, which can totally avoid REL updating. Then, dominating node history is added as an enhancement to further extend network lifetime. Finally, we propose a broadcast-based synchronization mechanism to reduce the synchronization overhead and assist dominating node selection. Extensive simulations show that our proposed algorithm can significantly reduce overhead without sacrificing network lifetime.