Optimizing parallel itineraries for knn query processing in wireless sensor networks

ABSTRACT

Spatial queries for extracting data from wireless sensor networks are important for many applications, such as environmental monitoring and military surveillance. One such query is K Nearest Neighbor (KNN) query that facilitates sampling of monitored sensor data in correspondence with a given query location. Recently, itinerary-based KNN query processing techniques, that propagate queries and collect data along a pre-determined itinerary, have been developed concurrently [12] [14]. These research works demonstrate that itinerary-based KNN query processing algorithms are able to achieve better energy efficiency than other existing algorithms. However, how to derive itineraries based on different performance requirements remains a challenging problem. In this paper, we propose a new itinerary-based KNN query processing technique, called PCIKNN, that derives different itineraries aiming at optimizing two performance criteria, response latency and energy consumption. The performance of PCIKNN is analyzed mathematically and evaluated through extensive experiments. Experimental results show that PCIKNN has better performance and scalability than the state-of-the-art.

REFERENCES

• 1: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 2: Brad Karp , H. T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345953]
• 3: Fabian Kuhn , Roger Wattenhofer , Aaron Zollinger, Worst-Case optimal and average-case efficient geometric ad-hoc routing, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778447]
• 4: S. J. Leon. Linear Algebra with Applications. Prentice Hall, 2002.
• 5: Dragos Niculescu , Badri Nath, Trajectory based forwarding and its applications, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939012]
• 6: H. Qi, X. Wang, S. Iyengar, and K. Chakrabarty. High Performance Sensor Integration in Distributed Sensor Networks Using Mobile Agents. International Journal of High Performance Computer Applications, 16(3):325--335, 2002.
• 7: Nick Roussopoulos , Stephen Kelley , Frédéric Vincent, Nearest neighbor queries, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.71-79, May 22-25, 1995, San Jose, California, United States
• 8: H. Schwetman. CSIM user's guide (version 18). Mesquite Software, Inc., http://www.mesquite.com.
• 9: Thomas Seidl , Hans-Peter Kriegel, Optimal multi-step k-nearest neighbor search, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.154-165, June 01-04, 1998, Seattle, Washington, United States
• 10: Zhexuan Song , Nick Roussopoulos, K-Nearest Neighbor Search for Moving Query Point, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.79-96, July 12-15, 2001
• 11: Julian Winter , Yingqi Xu , Wang-Chien Lee, Energy Efficient Processing of K Nearest Neighbor Queries in Location-aware Sensor Networks, Proceedings of the The Second Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services, p.281-292, July 17-21, 2005 [doi>10.1109/MOBIQUITOUS.2005.28]
• 12: B. Wu, K. T. Chuang, C. M. Chen, and M. S. Chen. DIKNN: An Itinerary-based KNN Query Processing Algorithm for Mobile Sensor Networks. In ICDE, 2007.
• 13: Yingqi Xu , Wang-Chien Lee , Jianliang Xu , Gail Mitchell, ProcessingWindow Queries in Wireless Sensor Networks, Proceedings of the 22nd International Conference on Data Engineering, p.70, April 03-07, 2006 [doi>10.1109/ICDE.2006.119]
• 14: Yingqi Xu , Tao-Yang Fu , Wang-Chien Lee , Julian Winter, Processing k nearest neighbor queries in location-aware sensor networks, Signal Processing, v.87 n.12, p.2861-2881, December, 2007 [doi>10.1016/j.sigpro.2007.05.013]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Distributed systems

General Terms:
Design, Experimentation, Performance

Keywords:
k nearest neighbor query, wireless sensor networks