On Minimal Energy Skew Routing in Lossy Wireless Sensor Networks

Roozbeh Jafari, Alberto Cerpa, Soheil Ghiasi, Majid Sarrafzadeh

Abstract

For several sensor networks applications, it is critical to extend the lifetime of each individual sensor node in order to remain operational for the longest time possible. Therefore, the power consumption rate should be evenly distributed over all the nodes in the system. Traditional routing algorithms attempt to minimize the total power consumption of the system, but they do not attempt to evenly distribute the load over all the nodes in the network. In this paper, we present an efficient routing algorithm that minimizes the energy skew among nodes in a network with lossy links. We propose an epsilon-optimal polynomial time centralized multi-hop routing technique that maximizes the lifetime a system of distributed power sources, considering the quality of the wireless links and the vagaries of the radio communication channel. Our technique aims to evenly distribute the power consumption rate which yields in a minimal-skew solution. We theoretically prove that our technique is efficient. Finally, we illustrate the quality of the solutions provided by our algorithms on a set of benchmarks that consider the quality of the wireless channels based on models using real RF transceivers. We show that our solution provides significant increase in the lifetime of the network (up to five times) at the cost of a slight increase in the latency of the end-to-end paths (up to 10%).

Availability

PDF

Reference

Roozbeh Jafari, Alberto Cerpa, Soheil Ghiasi, Majid Sarrafzadeh, "On Minimal Energy Skew Routing in Lossy Wireless Sensor Networks," UCLA Technical Report TR-05-0056, pp. 1--15, Computer Science Department, University of California, Los Angeles, December, 2005.

Bibtex

@TechReport{Jafari05a,
  author =       "Roozbeh Jafari and Alberto Cerpa and Soheil Ghiasi and
                 Majid Sarrafzadeh",
  title =        "On Minimal Energy Skew Routing in Lossy Wireless
                 Sensor Networks",
  institution =  "Computer Science Department, University of California,
                 Los Angeles",
  year =         "2005",
  number =       "UCLA Technical Report TR-05-0056",
  pages =        "1--15",
  month =        dec,
  URL =          "http://www.andes.ucmerced.edu/papers/Jafari05a.pdf",
}

Copyright

This paper is copyright © 2005 by its authors. Permission to make digital or hard copies of part or all of this work for personal use is granted without fee provided that copies are not made or distributed for profit or commercial purposes. New copies must bear this notice and the full citation on the first page. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission of the authors.