M.Sc Student | Yassour Ben-Ami |
---|---|

Subject | Energy-Efficient Routing in Wireless Networks |

Department | Department of Electrical Engineering |

Supervisor | Professor Ariel Orda |

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. Taking an algorithmic approach, we aim at finding
solutions with proven performance bounds. 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 receivers, which correspond to
omni-directional 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 receiver* 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 omni-directional transmission, the problem of lifetime maximization
under this environment has received only limited attention. We demonstrate that
the change from the traditional (multiple receiver) environment to the single
receiver 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 problem is computationally solvable and the
multi-topology problem is NP-hard, while *the opposite* holds for the
single-receiver model. Finally, we discuss the extension of our results to the
case of multiple sessions.