Distributed hierarchical search for balanced energy consumption routing spanning trees in wireless sensor networks

We provide a new heuristic method approach to search for degree-balanced and small weight routing spanning trees in a network. The method is a modification of Kruskal’s minimum spanning tree search algorithm and is based on a distributed search by hierarchical clusters. It provides spanning trees with a lower maximum weighted degree, a bigger diameter, and can be used for balanced energy consumption routing in wireless sensor networks (WSN’s). The method can be naturally implemented in parallel or as a simple locally distributed algorithm. Simulations for a realistic case scenario WSN are done based on the transmission energy matrix. The simulation results show that the proposed approach can extend the functional lifetime of a WSN in terms of sensor transmission energy by 3–4 times. We also show that the results can be further improved by using a preliminary clustering of the input network.

Research highlights
► Spanning trees are constructed hierarchically by amalgamating vertex clusters in pairs
► The resulting spanning tree has a lower maximum weighted vertex degree and is close to a minimum total weight spanning tree
► The resulting spanning tree has an intermediate structure between depth-first and breadth-first search spanning trees
► The functional lifetime of a wireless sensor network is extended by several times in terms of sensor transmission energies
► The method can be naturally implemented in parallel or as a locally distributed algorithm.