針對移動物體的 continuous k-nearest neighbor (CKNN) queries 對於 spatial database 應用以及 LBS 服務來說是一項重要的功能. 在集中式環境中已經提出許多有效率的 query processing 方法. 然而, CKNN 問題在 wireless sensor networks 中尚未很有效率地被解決. 在 wireless sensor networks 中處理此類問題的困難主要是因為 sensor nodes 需要花費大量的 communications 去收集和回報 objects 位置,進而導致 sensor nodes 消耗很多的電量. 在本文中我們提出 tracking-based distributed monitoring (TDM) 方法, 有效率地在 wireless sensor networks 處理 CKNN queries. TDM 藉由維護 answer space 的方式判斷目前的 KNN 並且連續地監控 KNN 的移動, 因此能以少量的 communications 獲得每個時間點的 query answer. 此外, 考慮到不同應用對於 KNN order 精準率的需求不同,我們也將 TDM 延伸去處理提供不同 order 精準率的 CKNN queries. 最後我們以實驗的結果證明我們所提出的方法多數的情況下都有很好的表現。

Continuous k-nearest neighbor (CKNN) search for moving objects is an important function in the applications of spatial databases and location based services (LBS). Many query processing approaches have been proposed in tradition environments. However, the CKNN query is still not addressed efficiently in wireless sensor environments. The challenges of addressing this issue in wireless sensor networks mainly come from fact that communication among sensors for continuous gathering and reporting object locations is highly expensive. In this paper, we propose a tracking-based distributed monitoring (TDM) approach for efficiently processing CKNN queries in wireless sensor networks. TDM establishes an answer space to determine the current KNN and monitor their movement continuously, so that the query answer at each time unit can be obtained with few communications. In addition, we also consider that different applications require different order precision of KNN, thus we extend TDM to address CKNN queries with various order precision. Finally, we conduct a comprehensive set of experiments to reveal that the proposed approach outperforms other existing methods.

[BHE00] Nirupama Bulusu, John Heidemann, and Deborah Estrin. GPS-less low cost outdoor localization for very small devices. In IEEE Personal Communications Magazine, pages 28–34, June 2000.
[BMJ+98] Josh Broch, David A. Maltz, David B. Johnson, Yih-Chun Hu, and Jorjeta Jetcheva. A performance comparison of multihop wireless ad hoc network routing protocols. In Proceedings of the 4th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom’98), pages 85–98, 1998.
[CEE+01] Alberto Cerpa, Jeremy Elson, Deborah Estrin, Lewis Girod, Michael Hamilton, and Jerry Zhao. Habitat monitoring: Application driver for wireless communications technology. In Proceedings of the 2001 ACM SIGCOMM Workshop on Data Communications in Latin America and the Caribbean, pages 20–41, April 2001.
[CHS04] Wei-Peng Chen, Jennifer C. Hou, and Lui Sha. Dynamic clustering for acoustic target tracking in wireless sensor networks. IEEE Transactions on Mobile Computing, (3):258–271, July 2004.
[CK03] Chee-Yee Chong and Srikanta P. Kumar. Sensor networks: Evolution, opportunities, and challenges. Proceedings of the IEEE, 91(8), August 2003.
[DF03] Murat Demirbas and Hakan Ferhatosmanoglu. Peer-to-peer spatial queries in sensor networks. In Proceedings of P2P ’03, page 32, Washington, DC, USA, 2003. IEEE Computer Society.
[DPIK05] Arjan Durresi, Vamsi K. Paruchuri, S. Sitharama Iyengar, and Rajgopal Kannan. Optimized broadcast protocol for sensor networks. IEEE Transactions on Computers, 54(8):1013–1024, August 2005.
[HXL05] Haibo Hu, Jianliang Xu, and Dik Lun Lee. A generic framework for monitoring continuous spatial queries over moving objects. In Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data, pages 479–490, 2005.
[KK00] Brad Karp and H. T. Kung. GPSR: Greedy perimeter stateless routing for wireless networks. In Proceedings of ICWCN, pages 243–254, May 2000.
[MFHH05] Samuel R. Madden, Michael J. Franklin, Joseph M. Hellerstein, and Wei Hong. Tinydb: An acquisitional query processing system for sensor networks. ACM Transactions on Database Systems (TODS), 30(1):122–173, March 2005.
[MHP05] Kyriakos Mouratidis, Marios Hadjieleftheriou, and Dimitris Papadias. Conceptual Partitioning: An Efficient Method for Continuous Nearest Neighbor Monitoring. In Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data, pages 634–645, June 2005.
[MKY+05] N. Malhotra, M. Krasniewski, C. Yang, S. Bagchi, and W. Chappell. Location estimation in ad-hoc networks with directional antennas. In Proceeding of the 2005 IEEE International Conference on Distributed Computing Systems (ICDCS05), pages 633–642, June 2005.
[MPBT05] Kyriakos Mouratidis, Dimitris Papadias, Spiridon Bakiras, and Yufei Tao. A Threshold-Based Algorithm for Continuous Monitoring of k Nearest Neighbors. IEEE Transactions on Knowledge and Data Engineering (TKDE), 17(11):1451–1464, November 2005.
[NN01] Dragos Niculescu and Badri Nath. Ad hoc positioning system (APS) using AOA. In IEEE Global Telecommunications Conference (GLOBECOM01), pages 2926–2931, November 2001.
[SBGP04] Adam Smith, Hari Balakrishnan, Michel Goraczko, and Nissanka Priyantha. Tracking moving devices with the cricket location system. In Proceedings of the 2nd International Conference on Mobile Systems, Applications, and Services (MobiSys04), pages 190–202, June 2004.
[SV04] Jochen Schiller and Agnes Voisard. Location-Based Services. Morgan Kaufmann, 2004.
[TCLH07] Yung-Chiao Tseng, Chao-Chun Chen, Chiang Lee, and Yuan-Ko Huang. Incremental in-network reverse nearest neighbor search in wireless sensor networks. In Proceedings of the First International Workshop on Ubiquitous Computing for Parallel and Distributed Systems (uPADS07), pages 77–77, September 2007.
[WCCC07] Brandon Wu, Kun-Ta Chuang, Chung-Min Chen, and Ming-Syan Chen. DIKNN: An itinerary-based KNN query processing algorithm for mobile sensor networks. In Proceeedings of IEEE 23rd International Conference on Data Engineering (ICDE’07), April 2007.
[WL04] Julian Winter and Wang-Chien Lee. KPT: a dynamic KNN query processing algorithm for location-aware sensor networks. In Proceeedings of DMSN ’04, pages 119–124, New York, NY, USA, 2004. ACM Press.
[XMA05] Xiaopeng Xiong, Mohamed F. Mokbel, and Walid G. Aref. SEA-CNN: Scalable Processing of Continuous K-Nearest Neighbor Queries in Spatial-Temporal Databases. In Proceedings of the 21st International Conference on Data Engineering (ICDE’05), pages 643–654, April 2005.
[XTL05] Jianliang Xu, Xueyan Tang, and Wang-Chien Lee. EASE: An energy-efficient in-network storage scheme for object tracking in sensor networks. In Proceedings of SECON’05, pages 396–405, September 2005.
[XWL04] Yingqi Xu, Julian Winter, and Wang-Chien Lee. Prediction-based strategies for energy saving in object tracking sensor networks. In Proceedings of MDM’04, pages 346–357, January 2004.
[YPK05] Xiaohui Yu, Ken Q. Pu, and Nick Koudas. Monitoring k-Nearest Neighbor Queries Over Moving Objects. In Proceedings of the 21st International Conference on Data Engineering (ICDE’05), pages 631–642, April 2005.
[YTL06a] Yuxia Yao, Xueyan Tang, and Ee-Peng Lim. Continuous monitoring of kNN queries in wireless sensor networks. In Proceedings of 2nd International Conference on Mobile Ad-hoc Sensor Networks, pages 662–673, December 2006.
[YTL06b] Yuxia Yao, Xueyan Tang, and Ee-Peng Lim. In-network processing of nearest neighbor queries for wireless sensor networks. In Proceedings of DASFAA’06, April 2006.
[ZC04] Wensheng Zhang and Guohong CIO. DCTC: Dynamic convoy tree-based collaboration for target tracking in sensor networks. IEEE Transactions on Wireless Communications, 3(5):1689–1701, 2004.