Distributed Search for Balanced Energy Consumption Spanning Trees

Abstract — Sensor networks are commonly used for security and surveillance applications. As sensor nodes have limited battery paower, computing, and storage resources, the energy efficient security techniques are needed. We provide a new heuris-tic approach to search for balanced and small weight routing spanning trees in a network. The approach is a modification of Kruskal’s minimum spanning tree (MST) search algorithm and is based on a distributed search by hierarchical clusters. It provides spanning trees with a lower maximum degree, a bigger diameter and can be used for balanced energy consumption routing in wireless sensor networks (WSNs). The approach can be implemented in parallel as well as a simple locally distributed algorithm. Simulations of a realistic 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 3 − 4 times in terms of sensor transmission energy. Possible preliminary clustering of the input network is considered as well. I