View article

This paper discusses online power‐aware routing in large wireless ad hoc networks (especially sensor networks) for applications in which the message sequence is not known. We seek to optimize the lifetime of the network. We show that online power‐aware routing does not have a constant competitive ratio to the off‐line optimal algorithm. We develop an approximation algorithm called max–min zP_min that has a good empirical competitive ratio. To ensure scalability, we introduce a second online algorithm for power‐aware routing. This hierarchical algorithm is called zone‐based routing. Our experiments show that its performance is quite good. Finally, we describe a distributed version of this algorithm that does not depend on any centralization. Copyright © 2003 John Wiley & Sons, Ltd.