An Effective Algorithm for Computing Energy-Efficient Broadcasting Trees in All-Wireless Networks
Given a wireless network in which node positions are fixed and a specific source node r in the network, the minimum energy broadcasting problem (MEB) asks each node to adjust its transmission range to create a spanning tree rooted at r with minimum total energy. This problem is NP-complete for both general graphs and Euclidean space graphs. We propose a heuristic algorithm called Greedy Tradeoff (GT) for the MEB problem. We compare the broadcasting trees computed by our GT algorithm with the broadcasting trees computed by two previously proposed algorithms, BIP and IMBM, in terms of total power, tree height, and the number of leave nodes. Our results show that the performance of our GT algorithm is better than the performances of BIP and IMBM.
spanning tree broadcast algorithm energy efficiency minimum-energy broadcast performance analysis wireless ad hoc network