טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentYassour Ben-Ami
SubjectEnergy-Efficient Routing in Wireless Networks
DepartmentDepartment of Electrical Engineering
Supervisor Professor Ariel Orda


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. 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.