[[alternative]]Data gathering schemes for wireless sensor networks

碩士[[abstract]] 無線感測網路係指由數百至數千個微小的感測器所組成之網路系統。此系統中的感測器有二個任務，一個是收集自己周圍環境中，我們所需要的資料，另一個則是利用無線網路將收集到的資料傳至基地台。 因為該網路中的感測器是利用電池作為電力來源，且感測網路的主要用途是在於觀測不易實地探查之環境，故散佈之後往往難以回收，就算可以回收，要為此數量龐大的感測器充電或是更換電池也不是件易事，所以對感測器的各個組成部份而言，能源消耗都是重要考量。在此論文中，我們將探討的重心放在無線感測網路中的資料收集架構上，因為對感測器而言，其能源花費的最主要因素就是在於資料傳輸所耗去的部份。所以若能在此部份有所突破，則感測器網路的生命期將會有顯著的提升。 在感測網路中主要有兩種資料收集方法，一種是感測器定期回報資料給基地台，稱之為data gathering，另一種則是每當基地台需要資料時，再發送要求至網路中，這稱之為data dissemination。其中前者的代表有LEACH (Low Energy Adaptive Clustering Hierarchy)及PEGASIS (Power Efficient GAthering in Sensor Information Systems)等，而後者的代表有Directed Diffusion及SEAD (Scalable Energy-efficient Asynchronous Dissemination)等。在論文中，我們將對這兩種資料收集方法作各別的探討。 我們以節省能源為出發點，參考過去所提出之資料收集架構的優缺點，提出適合於不同需求的資料收集架構，並在能源之外，再加入新的考量，比如減少收集資料所需之時間(transmission delay)、以分散式來建構、及為此網路加入容錯(fault-tolerant)等，以建出合於感測器網路之需求，且強健之資料收集架構。 從研究的結果中，我們可以得知，我們的方法能夠將我們所考量到的各個要素達成平衡，取得最佳化。利用這些資料收集架構將可以使感測器網路的應用層面更為廣闊。[[abstract]] Wireless sensor networks consist of hundreds or thousands of sensor nodes. These nodes have two tasks, the first is to collect information we want, and the second is to transmit the sensed data to the base station. The power of the nodes is limited battery, and nodes are always deployed to gather information in inhospitable or dangerous environment, so it is difficult to recharge their power. Even if nodes are rechargeable, the hung number of nodes will also make recharge inefficient. So in each component of sensor node, energy dispassion is the important consideration. In this paper we focus on the point of transmission schemes for wireless sensor networks because the transmission is the main consumer of battery power. If we can make good progress on them, we will also bring significant improvement on the life time of the sensor network. There are two kinds of schemes to collect sensed data, one is that nodes periodically report their collected data to the base station, which is named data gathering, like LEACH (Low Energy Adaptive Clustering Hierarchy) and PEGASIS (Power Efficient GAthering in Sensor Information Systems), another is that nodes transmit their gathered data only when the base station transmits its interest, which is named data dissemination, like directed-diffusion and SEAD (Scalable Energy-efficient Asynchronous Dissemination). In this paper, we will discuss these two kinds of schemes separately. We propose several data gathering schemes for wireless sensor networks, which not only takes energy efficiency for consideration but also other important terms into account, like efficiency of transmission delay, distributed way of construction schemes, and fault tolerant. After balancing these considerations, we can produce power efficient, robust and fast data gathering schemes for wireless sensor networks.[[tableofcontents]]中文摘要.............................................................................Ⅰ 英文摘要.............................................................................Ⅲ 目錄.....................................................................................Ⅴ 圖目錄.................................................................................Ⅷ 表目錄.............................................................................ⅩⅠ 第一章 序言.........................................................................1 1.1何謂無線感測網路...............................................................................1 1.2無線感測網路之資料收集模式...........................................................3 第二章 相關背景.................................................................4 2.1感測網路上資料收集演算法的要點...................................................4 2.2感測器之規格.......................................................................................6 2.3感測器的收發機模組...........................................................................7 第三章 各種資料收集機制.................................................8 3.1 Directed Transmission..........................................................................8 3.2 LEACH.................................................................................................9 3.2 PEGASIS............................................................................................11 3.3 Binary Approach for PEGASIS..........................................................13 3.4 Three-Level Scheme for PEGASIS....................................................15 3.5 Chain Based相關機制之探討...........................................................17 第四章 新提出之機制.......................................................19 4.1超立方體傳輸.....................................................................................19 4.1.1何謂超立方體.............................................................................................19 4.1.2 如何建立超立方體....................................................................................20 4.1.3 超立方體的資料收集方法........................................................................27 4.1.4 超立方體的重建與再結構........................................................................29 4.2分散式超立方體傳輸.........................................................................31 4.3分散式二元樹傳輸.............................................................................34 第五章 評估.......................................................................39 5.1超立方體傳輸與 Binary Approach for PEGASIS..............................39 5.2超立方體傳輸與PEGASIS的比較...................................................41 5.3傳輸時間上之比較.............................................................................43 5.4 新提出之三種機制的比較...............................................................45 第六章 模擬.......................................................................47 6.1模擬參數說明.....................................................................................47 6.2回合數與存活感測器的關係圖.........................................................49 6.3各機制的傳輸延遲關係圖.................................................................50 6.4各機制的傳輸所消耗能源之關係圖.................................................51 6.5各機制的能源*延遲之關係圖...........................................................52 6.6超立方體的重建與再結構之比較.....................................................53 第七章Data Dissemination概述........................................54 7.1 何謂Data Dissemination...................................................................54 7.2 各種Data Dissemination機制...........................................................56 7.2.1 Directed Diffusion.......................................................................................56 7.2.2 TTDD..........................................................................................................57 7.2.3 SEAD...........................................................................................................60 7.3 新機制探討.......................................................................................63 第八章 結論..................................................................66 參考文獻.............................................................................68 圖1.1 有100 個感測器的無線感測網路與基地台..........................................1 圖2.1 能源模組之示意圖.................................................................................7 圖3.1 direct transmission 之示意圖..................................................................8 圖3.2 LEACH 建立拓撲的流程.....................................................................10 圖3.3 分群機制的圖例...................................................................................10 圖3.4 PEGASIS 之傳輸示意圖......................................................................12 圖3.5 binary approach of PEGASIS 之傳輸示意圖.......................................14 圖3.6 PEGASIS with three level transmission 之傳輸示意圖.......................16 圖3.7 multiple-chain.......................................................................................17 圖3.8 Minimum Total Energy Algorithm........................................................18 圖4.1 一個4-cube 的範例...............................................................................19 圖4.2 建立超立方體的範例...........................................................................21 圖4.3 建立超立方體之演算法.......................................................................23 圖4.4 建立2-cube 的範例...............................................................................24 圖4.5 兩個2-cube 化成一個3-cube 的方法...................................................25 圖4.6 超立方體中兩種特別的情形說明.......................................................26 圖4.7 錯誤的建立超立方體之方法...............................................................27 圖4.8 一個4-cube 的communication tree.......................................................28 圖4.9 分散式超立方體之建立流程...............................................................30 圖4.10 分散式二元樹之建立流程.................................................................31 圖4.11 分散式超立方體之編號與連結的dimension....................................32 圖4.12 分散式超立方體之傳輸流程.............................................................33 圖4.13 分散式二元樹之建立流程.................................................................34 圖4.14 建立二元樹之演算法.........................................................................36 圖4.15 計算傳輸stage 之演算法....................................................................37 圖4.16 分散式二元樹之傳輸流程.................................................................38 圖5.1 超立方體與binary approach for PEGASIS 所建出的傳輸路徑比較.40 圖5.2 PEGASIS 和超立方體在傳輸上的差距..............................................42 圖6.1 每個機制的回合數與存活感測器之關係圖.......................................49 圖6.2 每次收集資料所需要的延遲之比較...................................................50 圖6.3 平均每回合感測器間傳輸所消耗之能源比較...................................51 圖6.4 平均能源*延遲之比較.........................................................................52 圖6.5 超立方體中，重新建立超立方體與路徑再規畫之效能比.................53 圖7.1 data dissemination 的範例...................................................................54 圖7.2 Directed Diffusion 建立連線的範例....................................................56 圖7.3 TTDD 所建立出的grid 的範例............................................................57 圖7.4 sink 傳query 到dissemination node 的範例.........................................57 圖7.5 dissemination node 間傳輸資料的範例...............................................58 圖7.6 SEAD tree 的範例...............................................................................60 圖7.7 SEAD的傳輸方式................................................................................61 圖7.8 從sink 到access node 間的路徑建立...................................................62 圖7.9 TTDD 的傳輸示意圖...........................................................................63 圖7.10 新提出之data dissemination 機制......................................................63 圖7.11 即時性的範例.....................................................................................65 表5.1 各種資料收集演算法的時間複雜度之比較.......................................44 表5.2 新提出之機制的優缺點比較...............................................................46 表6.1 模擬中所會使用到的參數..................................................................48[[note]]學號: 692390031, 學年度: 9