Maximum-lifetime routing algorithms for networks with omnidirectional and directional antennas

Abstract

A major problem in wireless networks is how to route either broadcast, unicast or multicast traffic so as to maximize the lifetime, i.e., the time until the battery of a transmitting node drains out. Focusing on the fundamental single-session problem, our solution approach is based on the employment of multi-topology routing schemes. Such a scheme consists of a set of routing topologies, which are employed sequentially, for some prescribed duration times. First, we consider the standard wireless environment of multiple recipients, which correspond to omnidirectional antennas. For the cases of either single-topology schemes or unicast sessions, we establish optimal solutions of polynomial complexity. For the general (multi-topology) cases of broadcast and multicast, which are NP-hard, we derive a novel heuristic scheme, and demonstrate its efficiency by way of simulations. We then consider an alternative, single-recipient wireless environment, which corresponds to the important case of directional antennas. While the employment of directional antennas is known to posses significant advantages over the traditional omnidirectional transmission, the problem of lifetime maximization under this environment has received only limited attention. We demonstrate that the change from the traditional (multiple-recipients) environment to the single-recipient environment is of major significance in terms of computational complexity and produces an interesting twist of difficulty: namely, for the standard model, the single-topology broadcast problem is computationally solvable and the multi-topology problem is NP-hard, while the opposite holds for the single-recipient model. Finally, we discuss the extension of our results to the case of multiple sessions. Copyright 2005 ACM.