Boruvka-Incremental Power Greedy Heuristic for Strong Minimum Energy Topology in Wireless Sensor Networks

Abstract

Given a set of sensors, the strong minimum energy topology (SMET) problem is to assign transmission range to each sensor node so that the sum of the transmission range for all the sensor is minimum subject to the constraint that the network is strongly connected (there is a directed path between every pair of nodes in the Network). This problem is known to be NP-hard. As this problem has lots of practical applications, several approximation algorithms and heuristics have been proposed. In this paper, we propose a new heuristic called Boruvka-incremental power greedy heuristic based on the Boruvka algorithm for the minimum spanning tree (MST) problem for solving the SMET problem. We compare the performance of the Boruvka-incremental power greedy heuristic with Kruskal-incremental power greedy heuristic and Prim-incremental power greedy heuristic. Extensive simulation results illustrate that Boruvka heuristic outperforms the Kruskal-incremental power greedy heuristic and Prim-incremental power greedy heuristic. We have also proved that apart from providing significant improvement in terms of average power savings, Boruvka incremental power greedy heuristic takes O(n) time for planar graphs as compared to O(n log n) time taken by Kruskal-incremental power greedy heuristic and O(n2) time taken by Prim-incremental power greedy heuristic, where n is the number of nodes in the network.