Skip to main content

Routing for Network Capacity Maximization in Energy-constrained As-hoc Networks

01 January 2003

New Image

We present a new distributed algorithm for routing of messages in ad-hoc networks where the nodes are energy-constrained. The routing objective is to maximize the total number of messages that can be successfully sent over the network without knowing any information regarding future message arrivals or message generation rates. From a theoretical perspective, we show that if admission control of messages is permitted, then the worst case performanace of our algorithm is within a factor of O(log(network size)) of the best achievable solution. In other words, our algorithm achieves a logarithmic compeitive ratio. Our approach provides sound theoretical backing for several obseravtions that have been made by previous researchers. From a practical perspective, we show by extensive simulations that the perfoprmance of the algorithm is very good even in the absence of admission control (the admission control being necessary only to prove the competitive ratio result) and that it also peforms better than previously proposed algorithms for other suggested metrics such as network lifetime maximization. Our algorithm uses a single shortest path computation, and is amenable to efficient implementation. we also evaluate by simulations the performance impact of inexact knowledge of residual battery energy, and the impact of energy drain due to dissemination of residual engergy information.