臺灣博碩士論文加值系統

本篇論文中，主要是探討在非同步無線感測網路的環境底下，連續且準確結果的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.

摘要 I
Abstract II
目錄 III
圖目錄 V
表目錄 VII
第一章 緒論 1
1.1 背景 1
1.2 論文目標 5
1.3 論文架構 6
第二章 相關研究 7
第三章 問題描述 17
3.1 Periodical sensing 19
3.2 Aperiodical sensing 31
3.3 Periodical sensing和Aperiodical sensing的正確性 43
第四章 實驗與模擬結果 45
4.1 環境設定與模擬參數 45
4.2 系統模擬結果 46
4.2.1 Periodical sensing方法 46
4.2.2 Aperiodical sensing方法 48
4.2.3不同的參數觀察 49
第五章 結論與未來研究方向 52
參考文獻 54

[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.