An adaptive backbone formation algorithm for wireless sensor networks

Connected dominating set (CDS) problem is the most promising and widely used approach for backbone formation in wireless networks. In this paper, a degree-constrained extension of the CDS problem called OMCDS (Optimal degree-constrained Minimum-weight CDS) is proposed for modeling the delay-bounded energy-efficient backbone formation in wireless sensor networks (WSN). OMCDS aims at minimizing the total weight of the CDS and finding the optimal degree constraint simultaneously. This paper constructs the network backbone by finding a near optimal solution to the proxy equivalent OMCDS problem, where the residual energy of the sensor is defined as the node weight. Taking advantage of learning automata theory, the proposed algorithm makes a trade-off between the backbone delay and backbone duration. Experimental results show the superiority of the proposed backbone formation method over the others in terms of the backbone lifetime, backbone delay, backbone size, and message overhead.