跳到主要內容

臺灣博碩士論文加值系統

(35.175.191.36) 您好!臺灣時間:2021/07/30 12:10
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:葉宗哲
研究生(外文):Zhong-Jer Yeh
論文名稱:在低密度無限感測器網路中搜尋可能的最近K個鄰居
論文名稱(外文):Probabilistic K-Nearest Neighbor Query in Low Density Wireless Sensor Network
指導教授:李強李強引用關係
指導教授(外文):Chiang Lee
學位類別:碩士
校院名稱:國立成功大學
系所名稱:資訊工程學系碩博士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2008
畢業學年度:96
語文別:中文
論文頁數:77
中文關鍵詞:空間查詢定位感測密度無線感測器網路
外文關鍵詞:sensing coverageK-nearest neighbor querywireless sensor networksprobabilistic query
相關次數:
  • 被引用被引用:0
  • 點閱點閱:132
  • 評分評分:
  • 下載下載:27
  • 收藏至我的研究室書目清單書目收藏:0
在無線感測器網路環境中, 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.
Abstract i
Table of Contents iii
Table of Figures vi
Table of Tables ix
1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 KNN query inWSN . . . . . . . . . . . . . . . . . . . . . 1
1.3 Challenge . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 SolutionOverview . . . . . . . . . . . . . . . . . . . . . . 6
1.5 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . 8
2 Related Work 10
2.1 KNN queries inWireless Sensor Network . . . . . . . . . . 10
2.2 Probabilistic Query in Uncertain Database . . . . . . . . . 11
2.2.1 Tuple-UncertaintyDatabase . . . . . . . . . . . . . 11
2.2.2 Attribute-Uncertainty Database . . . . . . . . . . . 13
3 Uncertainty Circle and Probabilistic K Nearest Neighbor
Query 15
3.1 Assumption . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2 Uncertainty Circle . . . . . . . . . . . . . . . . . . . . . . 16
3.3 Probabilistic K Nearest Neighbor Query . . . . . . . . . . 18
4 Distributed Probabilistic K Nearest Neighbor Query Processing
(DPKNN) 20
4.1 Data Collection Phase . . . . . . . . . . . . . . . . . . . . 22
4.1.1 Routing and Collecting . . . . . . . . . . . . . . . . 22
4.1.2 KNN Search Boundary and In-network Pruning . . 24
4.2 PKNN Evaluation Phase . . . . . . . . . . . . . . . . . . . 29
4.2.1 Filter Impossible PKNN . . . . . . . . . . . . . . . 29
4.2.2 Calculating Probability of PKNN . . . . . . . . . . 35
5 Improvement - Uncertainty Circle Refinement 41
5.1 Uncertainty Circle Refinement . . . . . . . . . . . . . . . . 41
5.1.1 Reducing Uncertainty Circle (Case 1) . . . . . . . . 42
5.1.2 Precise Localization (Case 2) . . . . . . . . . . . . 43
5.2 New Ni, Fi of Uncertainty Circle . . . . . . . . . . . . . . 44
5.3 Modification in Sampling-based Calculation . . . . . . . . 47
5.3.1 Sampling on Reduced Uncertainty Circle . . . . . . 47
6 Experimental Results 49
6.1 Setting and Metrics . . . . . . . . . . . . . . . . . . . . . . 49
6.2 Discussion of Sampling-based Evaluation . . . . . . . . . . 50
6.3 Effect of Uncertainty Degree of Object Position . . . . . . 53
6.4 Effect of Node Failures . . . . . . . . . . . . . . . . . . . . 54
6.5 Efficiency of DPKNN . . . . . . . . . . . . . . . . . . . . . 55
6.6 Impact of In-network Pruning Techniques . . . . . . . . . . 57
6.7 Impact of PermutationCandidate Table . . . . . . . . . . 58
6.8 Impact of Uncertainty Circle Refinement . . . . . . . . . . 60
7 Conclusions and Future Work 62
Appendices 64
Biography 77
[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
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊