Basic Search / Detailed Display

Author: 張智彥
Chih-Yen Chang
Thesis Title: 應用於無線感測網路之混合式資料聚集方法
Hybrid In-Network Data Aggregation Method in Wireless Sensor Networks
Advisor: 鄧惟中
Wei-Chung Teng
Committee: 張志勇
Chih-Yung Chang
邱舉明
Ge-Ming Chiu
賴源正
Yuan-Cheng Lai
Degree: 碩士
Master
Department: 電資學院 - 資訊工程系
Department of Computer Science and Information Engineering
Thesis Publication Year: 2009
Graduation Academic Year: 97
Language: 中文
Pages: 53
Keywords (in Chinese): 無線感測網路資料聚集
Keywords (in other languages): wireless sensor networks, data aggregation
Reference times: Clicks: 250Downloads: 1
Share:
School Collection Retrieve National Library Collection Retrieve Error Report
  •   過去有不少研究提出無線感測網路上的in-network資料聚集方法,其中混合式架構與傳統的架構相比,在資料查詢的校能與正確性方面有更好的表現。由於感測網路環境較為特殊,感測器所處在的環境時常受到環境的影響而導致通訊品質受到干擾,若能根據區域性通訊品質的變化,來適時的更改網路中的拓樸以及in-network資料聚集的方式,將有助於查詢結果的改善。近年的研究所提出的Tributaries-Deltas方法首次包含了這樣的概念,但其方法仍有值得探討及改進的地方。本論文即針對Tributaries-Deltas方法提出一些改進方向,首先是用於拓樸調整的判斷依據「貢獻百分比值」並不能單獨針對通訊錯誤以及誤差錯誤進行判斷,因此我們嘗試分別對通訊錯誤及誤差錯誤進行判斷。其次,跨區域的資料轉換可能導致結果的偏差更大,本論文在每個感測節點上,在每回合的聚集,皆紀錄其累加值,當作是更改拓樸時的判斷,並提供了更彈性的拓樸更新頻率。實驗的結果顯示,本方法在全域訊息遺失率的配置下,將退化成synopsis diffusion方法,均方根誤差值與synopsis diffusion有一樣的表現。另外在區域性資料遺失率方面的實驗,做了四種實驗條件的配置,實驗結果表示本方法能夠抵禦區域性環境其通訊品質的變化。由這兩項實驗可得知,本論文提出的混合式架構在某些情況下,能夠因環境的變化,適時的更改網路中的拓樸及方法,進而提升最後查詢結果的準確率。


    Many researches aim on issues of in-network data aggregation methods, but hybrid methods, comparing to traditional ones, have advantage on performance and accuracy of data queries. Since many wireless sensor networks are allocated on hostile environments, communication failure rate between sensor nodes become not negligible in these cases. The recently proposed Tributaries-Deltas method compensates this problem by dynamically adjust the topology of data aggregation according to communication failure rate. This hybrid method successfully increases the accuracy of query results but keeping the required communication cost minimum. However, Tributaries¬Deltas method still has its problems. First, it can not distinguish between communication error and approximation error from the percentage contributing. Second, the conversion function it used could decrease the accuracy of the final results. Thus, we propose a new method that could check the communi¬cation error and the approximation error individually by the 2-layer checking at each mote. In our approach, the updating frequency can be changed by the querier, and a table is used to accumulate every epoch’s counting value at each mote. The results of experiments show that the proposed method could downgrade to synopsis diffusion method under high loss ratio environment. The other experiment results about the regional communication loss ratio showed that the approach change to synopsis diffusion when the sensor nodes near the base station got higher loss ratio. Under other conditions, our method could resist the bad environment caused by the communication error by adjusting the topology dynamically. From the experiment results, we conclude that our method could increase the accuracy of the result compared to Tributaries-Deltas and update the topology according to the network conditions.

    摘要 I Abstract II 誌謝 III 目錄 IV 圖目錄 VII 表目錄 IX 第一章 緒論 1 1.1 前言 1 1.2 研究背景與動機 2 1.3 研究目的與方法 3 1.4 論文架構 3 第二章 文獻探討 5 2.1 以樹為主的方法 5 2.1.1 TAG [5] 5 2.1.2 Directed Diffusion [1] 6 2.1.3 PEGASIS [2] 7 2.2 叢集為主的方法 7 2.2.1 LEACH [9] 7 2.3 多路徑路由方法 8 2.3.1 Synopsis Diffusion [10] 9 2.4 Hybrid approaches 9 2.4.1 Tributaries and Deltas [7] 9 2.4.2 Hybrid approach of tree and gossip aggregation [11] 9 第三章 研究方法 11 3.1 Tiny Aggregation 11 3.2 Synopsis Diffusion 13 3.3 混合式in-network 資料聚集方法 16 3.3.1 Tributaries-Deltas 16 3.3.2 本論文所提出的方法 17 第四章 實驗建置與結果分析 21 4.1 實驗目的 21 4.2 平台介紹與環境設置 22 4.2.1 實驗平台介紹 22 4.2.2 環境設定 24 4.3 誤差項分析 25 4.3.1 全域訊息遺失率實驗 25 4.3.2 區域訊息遺失率實驗 29 4.4 能源項分析 35 4.5 實驗總結 36 第五章 結論與未來工作 37 5.1 結論 37 5.2 未來工作 37 參考文獻 39

    [1] Chalermek Intanagonwiwat, Ramesh Govindan, Deborah Estrin, John Heidemann, and Fabio Silva, “Directed diffusion for wireless sensor networking,” IEEE/ACM Transaction on Networking, vol. 11, no. 1, pp. 2–16, Feb. 2002.
    [2] Stephanie Lindsey, Cauligi S. Raghavendra, and Krishna M. Sivalingam, “Data Gathering Algorithms in Sensor Networks using Energy Metrics,” IEEE Transaction on Parallel Distributed Systems, vol. 13, no. 9, pp. 924–935, Sep. 2002.
    [3] Jeffrey Considine, Feifei Li, George Kollios, and John Byers, “Approximate aggregation techniques for sensor databases,” IEEE International Conference on Data Engineering, Apr. 2004.
    [4] Philippe Flajolet and G. Nigel Martin, “Probabilistic counting algorithms for database applications,” Journal of Computer and System Sciences, vol. 31, no. 2, pp. 182–209, Sep. 1985.
    [5] Samuel Madden, Michael J. Franklin, Joseph M. Hellerstein, and Wei Hong, “Tag: A tiny aggregation service for ad hoc sensor networks,” USENIX Symposium on Operating Systems Design and Implementation, vol. 36, no. SI, pp. 131–146, Dec. 2002.
    [6] Jerry Zhao and Ramesh Govindan, “Understanding packet delivery performance in dense wireless sensor networks,” ACM Conference on Embedded Networked Sensor Systems, Nov. 2003.
    [7] Amit Manjhi, Suman Nath, and Phillip B. Gibbons, “Tributaries and Deltas: Efficient and Robust Aggregation in Sensor Network Stream,” ACM International Conference on Management of Data, Jun. 2005.
    [8] Amit Manjhi, Suman Nath, and Phillip B. Gibbons, “Tributaries and deltas: Efficient and robust aggregation in sensor network streams,” Technical Report IRP-TR-05-01, Mar. 2005.
    [9] Wendi B. Heinzelman, Anantha P. Chandrakasan, and Hari Balakrishnan, “An application-specific protocol architecture for wireless microsensor networks,” IEEE Transactions on Wireless Communication, vol. 1, no. 4, pp. 660–670, Oct. 2002.
    [10] Suman Nath, Phillip B. Gibbons, Srinivasan Seshan, Zachary R. Anderson, “Synopsis diffusion for robust aggregation in sensor networks,” ACM Conference on Embedded Networked Sensor Systems, Nov. 2004.
    [11] Laukik Chitnis, Alin Dobra, and Sanjay Ranka, “Aggregation methods for large-scale sensor networks,” ACM Transaction on Sensor Networks, vol. 4, issue 2, Mar. 2008.
    [12] Samuel Madden, Michael J. Franklin, Joseph M. Hellerstein, and Wei Hong, “The design of an acquisitional query processor for sensor networks,” ACM International Conference on Management of Data, Jun. 2003.

    QR CODE