Probabilistic Power Management for Wireless Ad Hoc Networks

Extending system lifetime by effectively managing power on participating nodes is critical in wireless ad hoc networks. Recent work has shown that, by appropriately powering off nodes, energy may be significantly saved up to a factor of two, especially when node density is high. Such approaches rely on the selection of a virtual backbone (i.e., a connected dominating set) of the topology to forward ongoing traffic, coupled with algorithms to manually and periodically recompute such a backbone for load balancing purposes. The common drawback of such schemes is the need to involve periodic message exchanges and to make additional restrictive assumptions. This paper presents Odds¹, an integrated set of energy-efficient and fully distributed algorithms for power management in wireless ad hoc networks. Odds build on the observation that explicit and periodic re-computation of the backbone topology is costly with respect to its additional bandwidth overhead, especially when nodes are densely populated or highly mobile. Building on a fully probabilistic approach, Odds seek to make a minimum overhead, perfectly balanced, and fully localized decision on each node with respect to when and how long it needs to enter standby mode to conserve energy. Such a decision does not rely on periodic message broadcasts in the local neighborhood, so that Odds are scalable as node density increases. Detailed mathematical analysis, discussions and simulation results have shown that Odds are indeed able to achieve our objectives while operating in a wide range of density and traffic loads.Zongpeng Li received his B.Engr. in 1999, from Department of Computer Science and Technology, Tsinghua University, China, and his M.S. degree in 2001 from the Department of Computer Science, University of Toronto. He is currently working towards his Ph.D. degree in the Department of Electrical and Computer Engineering, University of Toronto. His research interests include algorithm design and analysis for both wireless and wireline networks.Baochun Li received his B.Engr. degree in 1995 from Department of Computer Science and Technology, Tsinghua University, China, and his M.S. and Ph.D. degrees in 1997 and 2000 from the Department of Computer Science, University of Illinois at Urbana-Champaign. Since 2000, he has been with the Department of Electrical and Computer Engineering at the University of Toronto, where he is an Assistant Professor. In 2000, he was the recipient of the IEEE Communications Society Leonard G. Abraham Award in the Field of Communications Systems. His research interests include network-level and application-level Quality of Service provisioning, application-layer overlay networks, wireless ad hoc networks, and mobile computing.