Minimum Energy Strong Bidirectional Topology for Ad Hoc Wireless Sensor Networks

A node in a wireless sensor network typically consists of a micro-controller, a communication device or transceiver, and a battery unit for powering the transceiver and other devices. An important feature of wireless sensor networks is the low power consumption requirement, since these sensor nodes carry generally irreplaceable power sources or batteries. We consider the problem of assigning a power to each node in the network such that the induced connectivity graph is strongly connected with only bidirectional links, and the sum total of powers assigned to all sensor nodes is minimized. This will allow the nodes to communicate with each other, while conserving battery power as much as possible. This problem has been shown to be strongly NP-complete and heuristic approaches for solving this problem have been reported in the literature. In this paper, we establish a lower bound on the optimal power value, and provide a sufficient condition for a minimal spanning tree (MST) based approach to be an optimal solution to the problem. Based on this condition, we propose a novel heuristic approach which computationally outperforms previously reported heuristics.