The Power Balancing Problem in Energy Constrained Multi-Hop Wireless Networks

Power efficient operation is very critical in energy constrained multi-hop wireless networks. One important technique is to intelligently assign transmission powers to nodes while maintaining network connectivity. Previous work has focused on assigning a single transmission power to each node. This often leads to "power imbalance", where some nodes use much more power than other nodes. This can reduce network lifetime. In this paper, we investigate the problem of two power assignments where nodes alternate the use of these assigned powers. We rigorously formulate the problem of two power assignment under the constraint that the network connectivity is maintained. The objective here is to minimize the maximum average power used by the nodes. We show that, in general, the problem is not just NP-hard but also hard to approximate. We then propose a distributed localized heuristic to compute the two power assignments. We perform extensive simulations to show that the algorithm can reduce the average power significantly when compared with algorithms that assign a single power. By assuming some properties on radio propagation, we also present a centralized algorithm with bounded worst case guarantees for the two power assignment problem.