研究生: |
劉宗瑋 Zong-Wei Liu |
---|---|
論文名稱: |
在非同步無線感測網路環境底下連續Top-k查詢之研究 A Study on Continuous Exact Top-k Query in Asynchronous Wireless Sensor Networks |
指導教授: |
邱舉明
Ge-Ming Chiu |
口試委員: |
陳秋華
Chyou-hwa Chen 項天瑞 Tien-Ruey Hsiang 鄧惟中 Wei-Chung Teng |
學位類別: |
碩士 Master |
系所名稱: |
電資學院 - 資訊工程系 Department of Computer Science and Information Engineering |
論文出版年: | 2014 |
畢業學年度: | 102 |
語文別: | 中文 |
論文頁數: | 62 |
中文關鍵詞: | 無線感測網路 、top-k 、連續查詢 、候選點 |
外文關鍵詞: | Wireless sensor networks, top-k, continuous query, candidate node |
相關次數: | 點閱:398 下載:3 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
本篇論文中,主要是探討在非同步無線感測網路的環境底下,連續且準確結果的top-k查詢。也就是說,我們想要隨時知道在目前環境,偵測數值最高的前k台感測器分別是那些,以及這些感測器偵測的數值各是多少。
無線感測網路通常是由一群感測器和一基地台所組成,由感測器偵測目前環境的資料,經由傳輸路徑上傳資料給基地台,然後由基地台負責計算目前的top-k結果。因為每台感測器有電量限制,而且感測數值的週期也不相同,所以如何降低感測器間的傳輸量以減少電力的消耗和獲得正確的感測器資料是本篇論文主要研究議題。
我們在此研究中分成兩種類別去討論,Periodical sensing和Aperiodical sensing,這兩類別差異在於基地台端是否有已知的一些感測器資訊。但主要做法都是在基地台端保留一些可能為結果的感測器資料,我們稱做候選點。在其有效時間之內,如果需要計算新的top-k結果,可以拿來做為參考的依據。最後將與現有的方法比較,證明我們的方法能夠有效的減少感測器間資料量傳輸以及減少電池的消耗,進而增長整體感測器的網路生命週期。
In this paper, we consider the continuous exact top-k query problem in the asynchronous wireless sensor networks. That is, we want to know the k highest reported values as well as the complete set of nodes that reported them at any time.
A wireless sensor network typically consists of a base station and a group of sensor nodes. The sensor nodes are responsible for sensing local environment data and pass through other sensor nodes to base station. After receiving the data, base station calculate the top-k result. However, owning to the limited energy and different sensing period of every sensor node, it’s an important issue that how to suppress the data transmission in order to balance energy consumption and also get the exact top-k result.
We have tackled the problem in two different aspects, Periodical sensing and Aperiodical sensing respectively. The main idea is that base station maintains some candidate nodes’ sensing value which has been updated to the base station but is not in the top-k result set. Each candidate value has a period of valid time. Before the candidate value expires, base station utilizes this data value to facilitate the process of finding top-k result. Last, we have compared our method with existing solution to show that our method effectively reduces the amount of communication traffic and energy consumption and prolongs the network lifetime as well.
[1] S. Tilak, N. Abu-Ghazaleh, and W. Heinzelman, "A Taxonomy of Wireless Micro-sensor Network Models," ACM SIGMOBILE Mobile Comp. Commun. Rev., vol. 6, no. 2, pp.28 -36 2002.
[2] I. Akyildiz, "A Survey on Sensor Networks, " IEEE Commun. Mag., vol. 40, no. 8, pp.102 -114 2002.
[3] Mihaela Cardei and Jie Wu, "Coverage in Wireless Sensor Networks, Handbook of Sensor Networks, " M. Ilyas and I. Magboub (eds.), CRC Press, 2004.
[4] F. Zhao, J. Shin, and J. Reich, "Information-driven dynamic sensor collaboration for tracking applications," IEEE Signal Processing Mag., vol. 19, pp.68 -77 2002.
[5] M. Kochhal, L. Schwiebert and S. Gupta, "Role-Based Hierarchical Self Organization for Wireless Ad Hoc Sensor Networks," in Proc. ACM Int',l Workshop Wireless Sensor Networks and Applications (WSNA ',03), 2003.
[6] M. Wu, J. Xu, X. Tang and W.-C. Lee, "Top-K Monitoring in Wireless Sensor Networks," IEEE Trans. Knowledge and Data Eng., vol. 19, no. 7, pp. 962-976, July 2007.
[7] B. Malhotra, M. A. Nascimento, I. Nikolaidis, "Exact top-k queries in wireless sensor networks," IEEE Transactions on Knowledge and Data Engineering (TKDE), Vol. 23 IEEE Press, 2011, pp. 1513-1525.
[8] S. Madden, M.J. Franklin, J.M. Hellerstein and W. Hong, "TAG: A Tiny Aggregation Service for Ad Hoc Sensor Networks," in Proc. Usenix Fifth Symp. Operating Systems Design and Implementation (OSDI ',02), pp. 131-146, Dec. 2002.
[9] X.Tang and J. Xu, "Extending Network Lifetime for Precision-Constrained Data Aggregation in Wireless Sensor Networks," in Proc. IEEE INFOCOM, Apr. 2006.
[10] O. Younis and S. Fahmy, "Distributed Clustering for Ad Hoc Sensor Networks: A Hybrid Energy-Efficient Approach," in Proc. IEEE INFOCOM, Mar. 2004.
[11] A. Silberstein, K. Munagala and J. Yang, "Energy-Efficient Monitoring of Extreme Values in Sensor Networks," in Proc. ACM Int',l Conf. Management of Data (SIGMOD ',06), pp. 169-180, 2006.
[12] A. Silberstein, R. Braynard and J. Yang, "Constraint-Chaining: On Energy-Efficient Continuous Monitoring in Sensor Networks," in Proc. ACM Int',l Conf. Management of Data (SIGMOD ',06), pp. 157-168, 2006.
[13] R. Fagin, A. Lotem and M. Naor, "Optimal Aggregation Algorithms for Middleware," in Proc. ACM Symp. Principles of Database Systems (PODS ',01), Aug. 2001.
[14] S. Nepal and M.V. Ramakrishna, "Query Processing Issues in Image (Multimedia) Databases," in Proc. IEEE Int',l Conf. Data Eng. (ICDE ',99), 1999.
[15] U. Guntzer, W.-T. Balke and W. Kieβling, "Optimizing Multi-Feature Queries for Image Databases," in Proc. 26th Int',l Conf. Very Large Data Bases (VLDB ',00), 2000.
[16] M. Theobald, G. Weikum and R. Schenkel, "Top- k Query Evaluation with Probabilistic Guarantees," in Proc. 30th Int',l Conf. Very Large Data Bases (VLDB ',04), Aug. 2004.
[17] J. Considine, F. Li, G. Kollios and J. Byers, "Approximate Aggregation Techniques for Sensor Databases," in Proc. IEEE Int',l Conf. Data Eng. (ICDE ',04), Mar. 2004.
[18] A. Deligiannakis, Y. Kotidis and N. Roussopoulos, "Hierarchical In-Network Data Aggregation with Quality Guarantees," in Proc. Int',l Conf. Extending Database Technology (EDBT ',04), Mar. 2004.
[19] M.A. Sharaf, J. Beaver, A. Labrinidis and P.K. Chrysanthis, "Balancing Energy Efficiency and Quality of Aggregate Data in Sensor Networks," VLDB J., vol. 13, no. 4, pp. 374-403, Dec. 2004.
[20] R. Szewczyk, E. Osterweil, J. Polastre, M. Hamilton, A. Mainwaring and D. Estrin, "Habitat Monitoring with Sensor Networks," Comm. ACM, vol. 47, no. 6, pp. 34-40, June 2004.
[21] J. Pan, Y. T. Hou, L. Cai, Y. Shi, and S. X. Shen, "Topology control for wireless sensor networks," in Proc. ACM MobiCom'03, Sept. 2003, pp. 286-299.
[22] W. Heinzelman, "Application-Specific Protocol Architectures for Wireless Networks," PhD dissertation, Massachusetts Inst. of Tech nology, 2000.