Energy-efficient backbone formation in wireless sensor networks

This paper proposes a new approach to the connected dominating set based backbone formation in wireless sensor network. In this approach, the delay-constrained energy-efficient backbone formation problem is modeled by the equivalent degree-constrained minimum-weight connected dominating set problem first. Then, a learning automata-based heuristic is proposed to find a near optimal solution to the proxy equivalent connected dominating set problem. The degree-constrained minimum-weight connected dominating set problem seeks for the connected dominating set having the minimum expected weight subject to a given constraint on the node degree. The running time of the proposed algorithm is approximated for finding a 11-ε optimal backbone of the network graph. Several simulation experiments are conducted to show the efficacy of the proposed heuristic. The obtained results show the outperformance of the proposed method over the others in terms of the backbone duration, transmission delay, and backbone size.

Graphical abstractFigure optionsDownload full-size imageDownload as PowerPoint slideHighlights► Proposing a new approach to backbone formation in wireless sensor network. ► Modeling backbone formation problem as degree-constrained connected dominating set problem. ► Finding a 11-ε optimal backbone for the network graph. ► Approximating the running time of the proposed algorithm. ► Comparing the proposed method with the best previous backbone formation methods.