Title:Prolonging Network Lifetime for Data Gathering in Wireless Sensor Networks
Speaker: Weifa Liang School of Computer Science, Australian National University
Time: 2009-12-16 16:00-2009-12-16 17:00
Venue:Room 1-222, FIT Building, Tsinghua University
Download:Click!

Abstract:

Energy-constrained sensor networks have been widely deployed for environmental monitoring and surveillance purpose. Data gathering in such networks is often a prevalent operation. Since sensors having significant power constraints are powered by energy-limited batteries, energy efficient routing protocols for data gathering must be employed to prolong the network lifetime.

In this paper we address the problem of prolonging network lifetime for mission-critical data gathering that the sensed data by each sensor must be relayed to the base station with the minimum number of hops, through the construction of an energy load-balanced routing tree rooted at the base station. We first formulate the problem and show that finding such a tree is NP-complete. Instead, we then devise three novel heuristics by employing network flow techniques. We also show how to extend the proposed algorithms to solve the problem with multiple base stations. We finally conduct extensive experiments by simulations to evaluate the performance of the proposed algorithms, in terms of network lifetime. The experimental results demonstrate that the proposed algorithms outperform a popular heuristic significantly.



Short Bio:

Weifa Liang (M'99--SM'01) received the PhD degree from the Australian National University in 1998, the Master of Engineering degree from the University of Science and Technology of China in 1989, and the BSc degree from Wuhan University, China in 1984, all in computer science. He is currently an Associate Professor in the School of Computer Science at the Australian National University. His research interests include design and analysis of energy-efficient routing protocols for wireless ad hoc and sensor networks, information processing in wireless sensor networks, routing protocol design for WDM optical networks, design and analysis of parallel and distributed algorithms, query optimization, and graph theory. He is a senior member of the IEEE.