Virtual Backbone Scheduling with Connected Domatic Partition in Wireless Sensor Networks
Jing Zhang, Li Xu, Xingsi Xue, Wei Wu and Hong Yang
Sleep scheduling is an efficient mechanism to optimize energy consumption in Wireless Sensor Networks (WSNs). In sleep schedule, nodes in the Virtual Backbone (VB) of WSNs remain active while other nodes may be put into the sleep state. VB can be formed by constructing a Connected Dominating Set (CDS). Since the dominators consume too much extra overheads if using only one CDS, then WSN cannot work. How to optimize the network lifetime is a critical issue. To this end, in this paper, lifetime maximization sleep scheduling problem is first modeled as a maximum Connected Domatic Partition (CDP) problem. Then Induced Tree of Crossed Cube based Partition Algorithm (IPA) is proposed to divide all of the nodes in the whole network into maximum CDP. Later, a schedule mechanism is presented to schedule the CDS rotation periodically by duty-cycling, which makes sure the network energy consumption being evenly distributed among all sensor nodes. The theoretical analysis establishes an upper bound of the CDP size, and the simulation results show that the lifetime can be enhanced significantly by using our proposed scheduling algorithm.
Keywords: Lifetime maximization, sleep scheduling, connected dominating Set, connected domatic partition, duty-cycling.