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: