簡易檢索 / 詳目顯示
| 研究生： |
陳青霞 Ching-hsia Chen |
|---|---|
| 論文名稱： |
在行動同儕網路中處理連續移動範圍查詢之有效協定 An Efficient Protocol for Processing Continuous Moving Range Queries in MP2P Networking Environment |
| 指導教授： |
邱舉明
Ge-ming Chiu |
| 口試委員: |
陳秋華
Chyou-hwa Chen 鮑興國 Hsing-kuo Pao 鄧惟中 Wei-chung Teng |
| 學位類別： |
碩士 Master |
| 系所名稱： |
電資學院 - 資訊工程系 Department of Computer Science and Information Engineering |
| 論文出版年： | 2011 |
| 畢業學年度： | 99 |
| 語文別： | 英文 |
| 論文頁數： | 45 |
| 中文關鍵詞： | 連續範圍查詢 、位置自覺 、行動同儕網路 、更新合作 |
| 外文關鍵詞： | Continuous range query, MP2P, safe period, update collaboration |
| 相關次數： | 點閱：177 下載：3 |
| 分享至: |
| 查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
近年來，由於定位系統與無線通訊技術的蓬勃發展，使得連續空間查詢成為在行動網路計算中最被需要的服務之一。其中，又以連續範圍查詢(continuous range query)為最常見的空間查詢議題。
在這篇論文中，主要研究設計出如何在行動同儕網路(mobile peer-to-peer network)中，進行處理連續範圍查詢的機制。在這樣的網路環境中，需仰賴同儕行動裝置傳遞訊息給欲送達的目的地。我們的研究特別專注於在處理連續範圍查詢時，如何減少通訊交通量的產生。為了能達到減少通訊交通量的目標，又不會犧牲掉查詢結果的正確性，在此我們提出了兩個機制，分別是位置自覺(location awareness)與更新合作(update collaboration)。論文中也描述了另一種方式，可用來管理多個連續範圍查詢發生在網路環境中的情形，進而大幅度地降低通訊花費。
最後，本論文提出一種方法，可去除現有解決方法中，對於擴展範圍(extended range)的需求。也因為如此，定期地範圍廣播也不需要存在了。而模擬的結果也顯示出，我們的機制對於減低連續範圍查詢中的通訊交通量非常有用。
In recent years, due to the advancement of the positioning system and wireless communication technologies, the continuous spatial query has been one of the most demanded services in mobile computing systems. The well-known range query is one of the most studied spatial query. This thesis investigates techniques for processing continuous range queries in mobile peer-to-peer networking environment. Such networking environment relies on peer mobile devices to forward a message to its destination. Our study aims especially at reducing communication traffic incurred when processing continuous range queries. We propose two techniques, called location awareness and update collaboration, for achieving this goal without sacrificing correctness of the query result. The thesis also describes a way of managing multiple continuous range queries that concurrently exist in the network, so that communication cost can be further reduced. Finally, the thesis proposes a scheme for eliminating the requirement for the extended range, which is required by existing solutions, and periodical range broadcast needed to support the concept is no longer required as a consequence. The simulation results demonstrate that our techniques are highly useful in reducing the amount of communication traffic needed for processing continuous range queries.
[1] N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger, "The R*-tree: An Efficient and Robust Access Method for Points and Rectangles," in Proc. ACM SIGMOD, pp. 322-331, 1990.
[2] C. Bettstetter, G. Resta, and P. Santi, "The Node Distribution of The Random Waypoint Mobility Model for Wireless Ad Hoc Networks," IEEE Trans. on Mobile Computing, vol. 2, pp. 257-269, July-September 2003.
[3] M. A. Cheema, L. Brankovic, X. Lin, W. Zhang, and W. Wang,"Multi-Guarded Safe Zone: An Effective Technique to Monitor Moving Circular Range Queries," in Proc. IEEE 26th International Conference on Data Engineering, pp. 189-200, 2010.
[4] T. T. Do, K. A. Hua, and C.-S. Lin, "ExtRange: Continuous Moving Range Queries in Mobile Peer-to-Peer Networks," in Proc. 10th International Conference on Mobile Data Management, pp. 317-322, 2009.
[5] B. Gedik and L. Liu, "MobiEyes: A Distributed Location Monitoring Service Using Moving Location Queries," IEEE Trans. on Mobile Computing, vol. 5, pp. 1384-1402, Oct. 2006.
[6] G. Ghinita, P. Kalnis, and S. Skiadopoulos, "MOBIHIDE: A Mobilea Peer-to-Peer System for Anonymous Location-Based Queries," in Proc. 10th International Conference on Advances in Spatial and Temporal Databases, Boston, MA, USA, pp. 221-238, 2007.
[7] D. Greene, "An Implementation and Performance Analysis of Spatial Data Access Methods," in Proc. 5th International Conference on Data Engineering, pp. 606-615, 1989.
[8] A. Guttman, "R-Trees: A Dynamic Index Structure for Spatial Searching," in Proc. ACM SIGMOD, pp. 47-57, 1984.
[9] T. Horozov, A. Grama, V. Vasudevan, and S. Landis, "MOBY - A Mobile Peer-to-Peer Service and Data Network," in Proc. International Conference on Parallel Processing, pp. 437-444, 2002.
[10] H. Hu, J. Xu, and D. L. Lee, "A Generic Framework for Monitoring Continuous Spatial Queries over Moving Objects," in Proc. ACM SIGMOD, Baltimore, Maryland, pp. 479-490, 2005.
[11] K. Kim, Y. Cai, and W. Tavanapong, "Safe-Time: Distributed Real-Time Monitoring of cKNN in Mobile Peer-to-Peer Networks," in Proc. 9th International Conference on Mobile Data Management, pp. 124-131, 2008.
[12] W.-S. Ku, R. Zimmermann, and H. Wang, "Location-Based Spatial Query Processing in Wireless Broadcast Environments," IEEE Trans. on Mobile Computing, vol. 7, pp. 778-791, 2008.
[13] F. Liu, K. A. Hua, and T. T. Do, "A P2P Technique for Continuous k-Nearest-Neighbor Query in Road Networks," in Proc. 18th International Conference on Database and Expert Systems Applications, Regensburg, pp. 264-276, 2007.
[14] M. F. Mokbel, X. Xiong, and W. G. Aref, "SINA: Scalable Incremental Processing of Continuous Queries in Spatio-temporal Databases," in Proc. ACM SIGMOD, Paris, France, pp. 623-634, 2004.
[15] J. M. Patel, Y. Chen, and V. P. Chakka, "STRIPES: An Efficient Index for Predicted Trajectories," in Proc. ACM SIGMOD, Paris, France, pp. 635-646, 2004.
[16] S. Prabhakar, Y. Xia, D. V. Kalashnikov, W. G. Aref, and S. E. Hambrusch, "Query Indexing and Velocity Constrained Indexing: Scalable Techniques for Continuous Queries on Moving Objects," IEEE Trans. on Computers, vol. 51, pp. 1124-1140, Oct. 2002.
[17] B. Rao and L. Minakakis, "Evolution of Mobile Location-Based Services," Communications of the ACM, vol. 46, pp. 61-65, Dec. 2003.
[18] N. Roussopoulos, S. Kelley, and F. Vincent, "Nearest Neighbor Queries," in Proc. ACM SIGMOD, pp. 71-79, 1995.
[19] S. Šaltenis, C. S. Jensen, S. T. Leutenegger, and M. A. Lopez, "Indexing the Positions of Continuously Moving Objects," in Proc. ACM SIGMOD, vol. 29, pp. 331-342, 2000.
[20] Z. Song and N. Roussopoulos, "K-Nearest Neighbor Search for Moving Query Point," in Proc. 7th International Symposium on Advances in Spatial and Temporal Databases, pp. 79-96, 2001.
[21] Y. Tao, D. Papadias, and J. Sun, "The TPR*-tree: An Optimized Spatio-Temporal Access Method for Predictive Queries," in Proc. 29th International Conference on Very Large Data Bases, Berlin, Germany, pp. 790-801, 2003.
[22] O. Wolfson, B. Xu, and R. M. Tanner, "Mobile Peer-to-Peer Data Dissemination with Resource Constraints," in Proc. International Conference on Mobile Data Management, pp. 16-23, 2007.
[23] S.-H. Wu, K.-T. Chuang, C.-M. Chen, and M.-S. Chen, "DIKNN: An Itinerary-Based KNN Query Processing Algorithm for Mobile Sensor Networks," in Proc. IEEE 23rd International Conference on Data Engineering, Istanbul, pp. 456-465, 2007.
[24] W. Wu, W. Guo, and K.-L. Tan, "Distributed Processing of Moving K-Nearest-Neighbor Query on Moving Objects," in Proc. IEEE 23rd International Conference on Data Engineering, pp. 1116-1125, 2007.
[25] X. Yu, K. Q. Pu, and N. Koudas, "Monitoring k-Nearest Neighbor Queries over Moving Objects," in Proc. IEEE 21st International Conference on Data Engineering, Tokyo, pp. 631-642, 2005.
[26] J. Zhang, M. Zhu, D. Papadias, Y. Tao, and D. L. Lee, "Location-Based Spatial Queries," in Proc. ACM SIGMOD, San Diego, California, pp. 443-454, 2003.
[27] B. Zheng and D. L. Lee, "Semantic Caching in Location-Dependent Query Processing," in Proc. 7th International Symposium on Advances in Spatial and Temporal Databases, pp. 97-116, 2001.
