Location-Aware Wireless Sensor Networks

Wireless sensor networks have recently received a lot of attention due to a wide range of applications such as object tracking, environmental monitoring, warehouse inventory, and health care. In these applications, physical data is continuously collected by the sensor nodes in order to facilitate application specific processing and analysis. The goal of our research in this area is to build data management systems for wireless sensor networks in support of data collection, aggregation, dissemination, in-network query processing and query optimization. We are particularly interested in location-aware wireless sensor networks since sensor network applications typically are concerned more about physical phenomena or events associated with a geographical location or region than the raw data on a specific sensor node. Our research is focused on:

1. Location tracking of moving objects;
2. Location-based routing and data collection;
3. In-network query processing and query optimization.

For location tracking of moving objects, we have observed that the monitoring and reporting activities of object tracking sensor networks (OTSNs) consume the most energy. Accordingly, we developed two prediction-based methods (called PES and DPR) to reduce energy consumption of the sensor nodes in OTSNs. PES predicts the future movement of the tracked objects to allow a wake up mechanism to decide which sensor nodes need to be activated in time to track the moving objects [MDM'04]. On the other hand, by predicting the movements of the tracked objects in both of the base station and sensor nodes, Reporting of sensor readings are avoided as long as the predictions are consistent with the real object movements. DPR achieves energy saving by intelligently trading off multi-hop/long-range transmissions of sensor readings between sensor nodes and the base station with one-hop/short-range communications of object movement history among neighbor sensor nodes [Mobiquitous'04]. Recently, by observing that many sensor applications for object tracking can tolerate a certain degree of imprecision in the location data of the tracked objects, we developed an in-network storage technique (called EASE) to efficiently answer approximate location queries in OTSNs [SECON'05]. EASE innovatively maintains two versions of object location data in the network. High-precision data is kept at some local storage node close to a moving object in order to reduce long-distance traffic resulted from remote updates. Meanwhile, the same data with a lower precision is replicated at some designated storage node which is known to users in order to reduce the querying traffic. Our study shows that EASE significantly cuts network traffic and prolongs the network lifetime.

Location-based routing protocols have been widely adopted in the design of wireless sensor networks. Most of the existing location-based routing protocols are stateful, i.e., make routing decisions based on cached geographical information of neighboring sensor nodes. However, possible node movements, node failures, and energy conservation techniques in sensor networks result in dynamic networks with frequent topology transients, and thus pose a major challenge to stateful packet routing algorithms. We have proposed a novel stateless location-based routing protocol, called PSGR, for location-aware sensor networks [MASS'05]. Based on PSGR, sensor nodes can locally determine their priority to serve as the next relay node using dynamically estimated network density and effectively suppress potential communication collisions without prolonging routing delays. PSGR also overcomes the communication void problem using two alternative stateless schemes, rebroadcast and bypass. Research result shows that PSGR exhibits superior performance in terms of energy consumption, routing latency and delivery rate.

Also based on location-based routing, we have developed an infrastructure-free window query processing technique for wireless sensor networks, called itinerary based window query execution (IWQE) [ICDE'06a]. In contrast to the conventional in-network query processing techniques proposed for wireless sensor networks which split a query execution in two stages,  query propagation and data aggregation, IWQE combines them into one single stage for execution along a well-designed itinerary inside a query window. IWQE, to the best of our knowledge, is the first infrastructure-free window query processing technique for wireless sensor networks. Many unique and challenging research issues which arise in IWQE (e.g., itinerary settings, query window coverage, in-network data processing, continuous data collection and handling of packet losses) have been studied thoroughly. To process k nearest neighbor (KNN) queries, we developed two alternative algorithms, namely the GeoRouting Tree (GRT) and the KNN Boundary Tree (KBT) [Mobiquitous'05b]. The former is based on a distributed spatial index structure and the latter is based upon ad-hoc location-based routing. This is the first study on KNN query processing in wireless sensor networks. Monitoring of top-k query is also important to many wireless sensor applications. We have exploited the semantics of top-k query and proposes a novel energy-efficient monitoring approach, called FILA, by installing a filter at each sensor node to suppress unnecessary sensor updates [ICDE'06b]. Finally, we proposed several decentralized architectures for in-network query processing and optimization. By exploiting sensor node’s innate spatial and semantic characteristics, those decentralized query processing systems can reduce energy costs of queries significantly [Mobiquitous'05a].

1. Y. Xu and W.-C. Lee, Exploring Spatial Correlation for Link Quality Estimation in Wireless Sensor Networks, IEEE International Conference on Pervasive Computing and Communications (PerCom’06), Pisa, Italy, March 2006, to appear.

2. C.K. Lee, W.-C. Lee, B. Zheng, and J. Winter, Processing Multiple Aggregation Queries in Geo-Sensor Networks, the Eleventh International Conference on Database Systems for Advanced Applications (DASFAA'06), Singapore, April 2006, to appear.

3. Y. Xu, W.-C. Lee, J. Xu, and G. Mitchell, Processing Window Queries in Wireless Sensor Networks, IEEE International Conference on Data Engineering (ICDE’06), Atlanta, GA, April 2006, to appear. [pdf]

4. M. Wu, J. Xu, X. Tang, and W.-C. Lee, Monitoring Top-k Query in Wireless Sensor Networks, IEEE International Conference on Data Engineering (ICDE’06), Atlanta, GA, April 2006, to appear. (Poster) [pdf]

5. Y. Xu, W.-C. Lee, J. Xu, and G. Mitchell, PSGR: Priority-based Stateless Geo-Routing in Wireless Sensor Networks, the Second IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS'05), Washington D.C., November, 2005, to appear. [pdf]

6. J. Xu, X. Tang, and W.-C. Lee, EASE: An Energy-Efficient In-Network Storage Scheme for Object Tracking in Sensor Networks, the Second IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks (SECON'05), Santa Clara, California, September 2005. [pdf]

7. R. Rosemark and W.-C. Lee, Decentralizing Query Processing in Sensor Networks, the Second International Conference on Mobile and Ubiquitous Systems: Networking and Services (Mobiquitous'05), San Diego, CA, July, 2005, pp. 270-280. [pdf]

8. J. Winter, Y. Xu, and W.-C. Lee, Energy Efficient Processing of K Nearest Neighbor Queries in Location-aware Sensor Networks, the Second International Conference on Mobile and Ubiquitous Systems: Networking and Services (Mobiquitous'05), San Diego, CA, July, 2005, pp. 281-292. [pdf]

9. Y. Xu, and W.-C. Lee, Window Query Processing in Highly Dynamic GeoSensor Networks: Issues and Solutions, GeoSensor Networks, edited by A. Stefanidis and S. Nittel, CRC Press LLC., 2004, ISBN: 0-41532-404-1, pp. 31-52. [pdf]

10. J. Winter and W.-C. Lee, KPT: A Dynamic KNN Query Processing Algorithm for Location-aware Sensor Networks, International Workshop on Data Management for Sensor Networks (DMSN'04), Toronto, Canada, August 2004, pp. 119-125. [pdf]

11. J. Winter, Y. Xu, and W.-C. Lee, Dual Prediction-based Reporting Mechanism for Object Tracking Sensor Networks, the First International Conference on Mobile and Ubiquitous Systems: Networking and Services (Mobiquitous'04), Boston, MA, August 22-26, 2004, pp. 154-163. [pdf]

12. J. Winter, Y. Xu, and W.-C. Lee, Prediction Based Strategies for Energy Saving in Object Tracking Sensor Networks, IEEE International Conference on Mobile Data Management (MDM'04), Berkeley, CA, Jan. 2004, pp. 346-357. [pdf]

13. Y. Xu, and W.-C. Lee, On Localized Prediction for Power Efficient Object Tracking in Sensor Networks, International Workshop on Mobile Distributed Computing (MDC’03), Providence, Rhode Island, May 19-22, 2003, pp. 434-439. [pdf]