在無線感測器網路環境中， K-Nearest Neighbor (KNN) query 是一個很重要的查詢，以往也有許多論文提出在感測器網路有效解決 KNN 查詢的演算法。
然而，以往討論感測器網路中 KNN 查詢的論文，都會假設物體的位置可被感測器準確定位。
藉由計算物體位置與查詢點的距離， KNN 物體可被準確的判別出來。
然而，無線感測器可能因為硬體損毀或是電力不足而無法繼續作業。
感測器節點損毀或是節點分佈不均都會使得網路的感測密度不足。
在感測密度不足的情況下，因為定位技術的限制，感測器將無法準確定位物體的位置。
若是感測器無法得知物體位置，就無法確定 KNN 查詢的答案為何。

在本文中，我們提出 Probabilistic K-Nearest Neighbor (PKNN) query 來解決當物體位置有不確定性時的 KNN 查詢。
PKNNQ 會找出在所有可能成立的 KNN 之中，成立機率最高、最可信的 KNN 答案。
我們提出了 In-network Pruning techniques 來減少收集物體資訊時的通訊花費。
面對大量可能成立的 PKNN 組合，我們設計了演算法來過濾那些不可能成立的 PKNN 答案，避免多餘的計算。
我們也利用取樣計算的技巧來減少計算 PKNN 機率的繁複計算。
最後我們以實驗結果來證明我們所提出的方法在低密度的感測器網路環境中能有效地找出可信的 KNN 答案。

Many efficient approachs to answer K-Nearest Neighbor (KNN) query have been proposed in wireless sensor network (WSN).
These works assume the location of objects can be obtained and recorded on the sensor nodes.
By calculating the distance between objects and the query point, the KNN answer can be easily found.
However, sensor network may become low density because of hardware-damaged or improper distribution of sensor nodes.
In this environment, the sensing coverage becomes low and it is infeasible for the sensor nodes to locate the precise position of objects.
So the KNN queries may produce incorrect answers or cannot determine the KNN at all.

In this paper, we propose the Probabilistic K-Nearest Neighbor (PKNN) query, which returns a set of KNN objects with the highest probability to be the accurate KNN.
We propose In-network Pruning Techniques to reduce message size when collecting data in WSN.
We develop data structures and algorithms for filtering impossible PKNN answers.
A sampling-based probability calculation method is proposed to ease the computation load of sensor nodes.
%Furthermore, we exploit the sensing range of neighboring nodes to reduce uncertainty degree of objects and improve the accuracy of PKNN answers.
Experimetal results show that our approach can save significant energy and find out the probable KNN answer in low density sensor networks.

[1] Mainwaring, A., Culler, D., Polastre, J., Szewczyk, R., Anderson, J.: Wireless sensor networks for habitat monitoring. In: Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications. (2002) 88–97
[2] Li, S., Lin, Y., Son, S.H., Stankovic, J.A., Wei, Y.: Event detection services using data service middleware in distributed sensor networks. In: Telecommunication Systems. Volume 26. (2004) 351–368
[3] Xu, Y., Winter, J., Lee, W.C.: Prediction-based strategies for energy saving in object tracking sensor networks. In: Proceedings of the IEEE International Conference on Mobile Data Management. (2004) 346–357
[4] Xu, J., Tang, X., Lee, W.C.: EASE: An energy-efficient in-network storage scheme for object tracking in sensor networks. In: Proceedings of the 2nd Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks. (2005) 396–405
[5] Demirbas, M., Ferhatosmanoglu, H.: Peer-to-peer spatial queries in sensor networks. In: Proceedings of the 3rd International Conference on Peer-to-Peer Computing. (2003) 32–39
[6] Winter, J., Xu, Y., Lee, W.C.: Energy efficient processing of k nearest neighbor queries in location-aware sensor networks. In: Proceedings of the 2nd Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services. (2005) 281–292
[7] Winter, J., Lee, W.C.: KPT: A dynamic KNN query processing algorithm for location-aware sensor networks. In: Proceedings of the 1st Workshop on Data Management for Sensor Networks. (2004) 119–124
[8] Wu, S.H., Chuang, K.T., Chen, C.M., Chen, M.S.: DIKNN: An itinerary-based KNN query processing algorithm for mobile sensor networks. In: Proceedings of the 23th International Conference on Data Engineering. (2007) 456–465
[9] Sawides, A., Han, C.C., Strivastava, M.B.: Dynamic fine-grained localization in ad-hoc networks of sensors. In: Proceedings of the 7th Annual International Conference on Mobile Computing and Networking. (2001) 166–179
[10] Galstyan, A., Krishnamachari, B., Lerman, K., Pattem, S.: Distributed online localization in sensor networks using a moving target. In: Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks. (2004) 61–70
[11] Bai, X., Kumar, S., Xuan, D., Yun, Z., Lai, T.H.: Maintaining sensing coverage and connectivity in large sensor networks. In: Proceedings of the 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing. (2006) 131–142
[12] Cheng, R., Kalashnikov, D.V., Prabhakar, S.: Querying imprecise data in moving object environments. IEEE Transactions on Knowledge and Data Engineering Volume 16 (2004) 1112–1127
[13] Kriegel, H.P., Kunath, P., Renz, M.: Probabilistic nearest-neighbor query on uncertain objects. In: Proceedings of the 12th International Conference on Database Systems for Advanced Applications. Volume 4443 of Lecture Notes in Computer Science., Springer (2007) 337–348
[14] Yao, Y., Tang, X., peng Lim, E.: Continuous monitoring of kNN queries in wireless sensor networks. In: Mobile Ad-hoc and Sensor Networks. (2006) 662–673
[15] Cheng, R., Chen, J., Mokbel, M., Chow, C.Y.: robabilistic verifiers: Evaluating constrained nearest-neighbor queries over uncertain data. In: Proceedings of the 24th International Conference on Data Engineering. (2008) 973–982
[16] Soliman, M.A., Ilyas, I.F., Chang, K.C.: Top-k query processing in uncertain databases. In: Proceedings of the 23th International Conference on Data Engineering. (2007) 896–905
[17] Yi, K., Li, F., Kollios, G., Srivastava, D.: Efficient processing of top-k queries in uncertain databases. In: Proceedings of the 24th International Conference on Data Engineering. (2008) 1406–1408
[18] Hua, M., Pei, J., Zhang, W., Lin, X.: Efficiently answering probabilistic threshold top-k queries on uncertain data. In: Proceedings of the 24th International Conference on Data Engineering. (2008) 1403–1405
[19] Cheng, R., Kalashnikov, D.V., Prabhakar, S.: Evaluating probabilistic queries over imprecise data. In: Proceedings of the ACM SIGMOD International Conference on Management of Data. (2003) 551–562
[20] Yao, Y., Tang, X., Lim, E.P.: In-network processing of nearest neighbor queries for wireless sensor networks. In: Proceedings of the 11th International Conference on Database Systems for Advanced Applications. (2006) 35–49
[21] Niculescu, D., Nath, B.: Trajectory based forwarding and its applications. In: Proceedings of the 9th Annual International Conference on Mobile Computing and Networking. (2003) 260–272
[22] Patil, S., Das, S.R., Nasipuri, A.: Serial data fusion using space-filling curves in wireless sensor networks. In: Proceedings of the 1st Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks. (2004) 182–190
[23] Gui, C., Mohapatra, P.: Virtual patrol: a new power conservation design for surveillance using sensor networks. In: Proceedings of the Information Processing in Sensor Networks. (2005) 246–253
[24] Agrawal, P., Benjelloun, O., Sarma, A.D., Hayworth, C., Nabar, S., Sugihara, T., Widom, J.: Trio: a system for data, uncertainty, and lineage. In: Proceedings of the 32nd International Conference on Very Large Data Bases. (2006) 1151–1154
[25] Re, C., Dalvi, N., Suciu, D.: Efficient top-k query evaluation on probabilistic data. In: Proceedings of the 23th International Conference on Data Engineering. (2007) 886–895
[26] Sistla, A.P., Wolfson, O., Chamberlain, S., Dao, S.: Querying the uncertain position of moving objects. Volume 1399. (1998) 310–337
[27] Pfoser, D., Jensen, C.S.: Capturing the uncertainty of moving-object representations. Volume 1651. (1999) 111–127
[28] Cheng, R., Xia, Y., Prabhakar, S., Shah, R., Vitter, J.S.: Efficient indexing methods for probabilistic threshold queries over uncertain data. In: Proceedings of the 30th International Conference on Very Large Data Bases. Volume 30. (2004) 876–887
[29] Tao, Y., Cheng, R., Xiao, X., Ngai, W.K., Kao, B., Prabhakar, S.: Indexing multi-dimensional uncertain data with arbitrary probability density functions. In: Proceedings of the 31th International Conference
on Very Large Data Bases. (2005) 922–933
[30] Chen, J., Cheng, R.: Efficient evaluation of imprecise location dependent queries. In: Proceedings of the 23rd International Conference on Data Engineering. (2007) 586–595
[31] Deshpande, A., Guestrin, C., Madden, S.R., Hellerstein, J.M., Hong, W.: Model-driven data acquisition in sensor networks. In: Proceedings of the 13th International Conference on Very Large Data Bases.
(2004) 588–599
[32] Bulusu, N., Heidemann, J., Estrin, D.: Gps-less low cost outdoor localization for very small devices. IEEE Personal Communications Magazine 7 (2000) 28–34
[33] Girod, L., Estrin, D.: Robust range estimation using acoustic and multimodal sensing. In: Proceedings of the IEEE/RSJ Conference on Intelligent Robots and Systems. Volume 3. (2001) 1312–1320
[34] Chen, W.P., Hou, J.C., Sha, L.: Dynamic clustering for acoustic target tracking in wireless sensor networks. In: IEEE Transactions on Mobile Computing. Volume 3. (2004) 258–271
[35] Zhang, H., Hou, J.: Maintaining sensing coverage and connectivity in large sensor networks. In: International Workshop on Theoretical and Algorithmic Aspects of Sensor, Ad hoc Wireless and Peer-to-Peer Networks. (2004) 89–124
[36] Xu, Y., Lee, W.C., Xu, J., Mitchell, G.: Processing window queries in wireless sensor networks. In: Proceedings of the 22th IEEE International Conference on Data Engineering. (2006) 70
[37] Karp, B., Kung, H.T.: GPSR: Greedy perimeter stateless routing for wireless networks. In: Proceedings of the 6th Annual International Conference on Mobile Computing and Networking. (2000) 243–254