Group:Wireless Sensor Network Group
Title: Power Aware Routing for Sensor Databases, On the Complexity of Scheduling with P
Speaker: Xiao Qi, Guanyu Wang University
Time: 2010-11-15 10:00-2010-11-15 11:30
Venue: FIT 1-222


Abstract of “Power aware routing for sensor databases”:


Wireless sensor networks offer the potential to span and monitor large geographical areas inexpensively. Sensor network databases like TinyDB [1] are the dominant architectures to extract and manage data in such networks. Since sensors have significant power constraints (battery life), and high communication costs, design of energy efficient communication algorithms is of great importance. The data flow in a sensor database is very different from data flow in an ordinary network and poses novel challenges in designing efficient routing algorithms. In this work we explore the problem of energy efficient routing for various different types of database queries and show that in general, this problem is NP-complete. We give a constant factor approximation algorithm for one class of query, and for other queries give heuristic algorithms. We evaluate the efficiency of the proposed algorithms by simulation and demonstrate their near optimal performance for various network sizes.


Abstract of “On the Complexity of Scheduling with Power Control in Geometric SINR”:


Although being a very fundamental problem in the field of wireless networks, the complexity of transmission scheduling with power control in the Geometric SINR model is still unknown. In this article, we show that the joint problem of finding transmission powers and scheduling the transmissions is NP-hard if the available powers are bounded, independent of the actual bounds. This also implies that scheduling with a finite number of power levels is NP-hard.