<4D F736F F D20BDD7A4E5ABCAADB1A4CEA4BAADB62E646F63>

Transcription

1 國立交通大學 資訊科學與工程研究所 碩士論文 ZigBee 網路之主幹感知的網路形成機制 BANF - A Backbone-Aware Network Formation Scheme for ZigBee Networks 研究生 : 吳昭男 指導教授 : 曾建超教授 中華民國九十七年六月

2 ZigBee 網路之主幹感知的網路形成機制 BANF - A Backbone-Aware Network Formation Scheme for ZigBee Networks 研究生 : 吳昭男 指導教授 : 曾建超 Student:Chao-Nan Wu Advisor:Chien-Chao Tseng 國立交通大學資訊科學與工程研究所碩士論文 A Thesis Submitted to Institute of Computer Science and Engineering College of Computer Science National Chiao Tung University in partial Fulfillment of the Requirements for the Degree of Master in Computer Science June 2008 Hsinchu, Taiwan, Republic of China 中華民國九十七年六月

3 ZigBee 網路之主幹感知的網路形成機制 研究生 : 吳昭男 指導教授 : 曾建超教授 國立交通大學資訊學院資訊科學與工程研究所 摘要 本論文針對無線感測網路 (Wireless Sensor Network) 提出一套可以舒緩熱點問題 (Hot-spot Problem) 以至於延長網路生命週期的繞送機制 無線感測網路常用於偵測周圍環境, 將相關資訊傳回給基地台 (Base Station), 方便管理者根據資料進行判斷與反應 ; 無線感測網路由許多具有電量限制的感測節點所組成 感測節點會消耗許多的電力在傳送資料上 然而無線感測網路會有熱點問題存在, 亦即距離基地台較近的節點會有較重的資料轉送負載, 所以這些節點會先耗盡電能而損耗 然而在感測網路的實際部署環境中, 某些感測節點可持續接電或較容易更換電池, 我們將這些感測節點統稱為具電節點 (Power-node) 本論文即是以具電節點為主幹, 提出一套的主幹感知的網路形成機制 (Backbone-Aware Network Formation; BANF) 來舒緩熱點問題造成的影響 我們透過具電節點建立起主幹網路 (Backbone Networks), 透過主幹網路將資料負載分散至多個具電節點 BANF 具有兩個特色 :⑴ 建立以具電節點為樹根 (Root) 的子樹 ;⑵ 提出了當具電節點突然損壞的主幹網路臨時修復機制 經由在 NS2 網路模擬平台的實驗, 本研究所提出的主幹感知網路形成機制相對於 ZigBee 無線感測網路, 依據不同的網路拓樸可以延長 193% 至 310% 的節點平均運作時間 關鍵詞 : 無線感測網路 主幹網路 具電節點 熱點 ZigBee - i -

4 BANF - A Backbone-Aware Network Formation Scheme for ZigBee Networks Student: Chao-Nan Wu Advisor: Dr. Chien-Chao Tseng Institute of Computer Science and Engineering College of Computer Science National Chiao Tung University Abstract In this thesis, we propose a routing mechanism that can mitigate the hot-spot problem of wireless sensor networks (WSNs) so as to extend the network lifetime. A WSN consists of a coordinator and many sensor nodes that periodically collect and report to the coordinator the sensed information. With such periodical transmission, a sensor node may exhaust its energy sometime if it has limited energy resources. Moreover, the energy consumption may further be aggravated by the hot-spot problem that commonly exists in most WSNs; that is, sensor nodes closer to the coordinator tend to relay more traffic, and will exhaust their power sooner than others. However, in most deployments of sensor networks, there exist some nodes, henceforth referred to as power-nodes, with fixed power supplies or easy to replace if malfunction. In this thesis, we propose a Backbone-Aware Network Formation (BANF) scheme to mitigate the influence of hot-spot problem. We use power-nodes to construct the backbone of a network and route information toward a backbone power-node first, or the coordinator if it is closer than other power-nodes. The power-nodes then route the traffic toward the coordinator through other power-nodes in the backbone. Therefore, BANF can distribute traffic loads to more spots (nodes near backbone power-nodes) and alleviate the hot-spot problem of WSNs. BANF has two features: (1) power-node based subtrees and routing, and (2) - ii -

5 fault tolerance mechanism for power-node failures. Results from NS2 simulations show that BANF can prolong network lifetime about 193~310%, compared with ZigBee under various network topologies. Keywords: Wireless sensor network Backbone Power-node Hot-spot ZigBee - iii -

6 誌謝 首先, 我要感謝我的指導教授 曾建超老師 感謝老師這兩年來的指導與啟發, 在我碩士研究兩年間的教誨, 指導我正確的研究方法與態度, 引領我走向正確的研究方向, 並且提供一個完整且自由的研究環境 在這學習的過程中, 也讓我體認到積極奮發與創意思考為研究之要務 同時要感謝曹孝櫟教授 蔡文能教授與翁永昌教授於百忙之中撥冗審閱我的論文並擔任口試委員, 老師們所提供的寶貴建議使本篇論文更為完善, 也感謝老師們對我的鼓勵與指導 特別感謝王瑞堂學長, 又稱 RT, 以及 LB(Load Balancing) 三人組中另外兩位成員 : 宗羲 俊羽, 大家一起腦力激盪將論文題目以及方法想出來 並且相互切磋將論文完成, 最後大家一起順利畢業, 也預祝大家將來在工作上會有好的成績 另外還要感謝無線網際網路實驗室的同學 博班學長以及學弟妹, 在我碩士求學過程中給予的意見 支持與鼓勵, 讓我的碩士生涯不僅在課業上以及課餘活動皆豐富且充實 最後, 僅以此文獻給我摯愛的雙親, 感謝你們在背後無止盡的支持, 讓我能夠無後顧之憂完成學業 - iv -

7 目錄 摘要... i Abstract... ii 誌謝... iv 目錄... v 圖目錄... vii 表目錄... ix 第一章緒論 前言 研究動機 章節簡介... 3 第二章背景知識介紹 無線感測網路介紹 無線感測網路概論 無線感測網路架構 無線感測網路議題 IEEE 通訊協定 IEEE 架構 IEEE 特性及介紹 ZigBee 網路識別碼分配機制與路由協定 第三章相關研究 無線感測網路之路由協定 叢集式基礎架構 :LEACH 鏈基礎架構 :PEGASIS 資源導向協定 :ROP 不相等的叢集架構 :UCS 其他 第四章 BANF 機制 v -

8 4.1 BANF 設計概念與目標 BANF 運作流程 主幹網路建立階段 一般節點加入階段 主幹網路修復階段 總結 第五章模擬結果與討論 模擬環境 模擬結果與分析 網路拓樸之模擬結果 具電節點樹深度的影響之模擬結果 第六章結論與未來工作 結論 未來工作 Reference vi -

9 圖目錄 圖 1.1 熱點問題示意圖... 2 圖 2.1 無線感測網路架構圖... 5 圖 2.2 無線感測網路協定架構... 6 圖 2.3 IEEE 協定架構 圖 2.4 星狀拓樸 圖 2.5 點對點拓樸 圖 2.6 資料傳輸模式 ( 裝置 協調者 ) 圖 2.7 資料傳輸模式 ( 協調者 裝置 ) 圖 2.8 ZigBee 識別碼分配範例 圖 3.1 LEACH 叢集式基礎架構 圖 3.2 LEACH 叢集頭選擇範例 圖 3.3 鏈架構建置範例 圖 3.4 鏈架構資料傳送方式 圖 3.5 ROP 範例說明 圖 3.6 ROP 處理程序 圖 3.7 ROP 拓樸形成流程圖 圖 3.8 UCS 架構 圖 4.1 BANF 具電節點加入網路 圖 4.2 BANF 新增具電節點範例 圖 4.3 Association priority 圖 4.4 Regular node N wants to join the PAN 圖 4.5 Different with ZigBee and BANF 圖 4.6 兩層式可繞送識別碼 圖 4.7 主幹網路修復流程圖 圖 4.8 主幹網路修復第一階段範例 圖 4.9 主幹網路修復第一階段結果 圖 4.10 主幹網路修復第二階段範例 圖 4.11 主幹網路修復第二階段結果 圖 4.12 主幹網路修復第三階段範例 圖 4.13 主幹網路修復第三階段結果 圖 5.1 Case1 與 Case2 網路拓樸 vii -

10 圖 5.2 Case3~5 網路拓樸 圖 5.3 不同網路拓樸之節點平均運作時間 圖 5.4 Case1 節點存活時間之關係圖 圖 5.5 Case2 節點存活時間之關係圖 圖 5.6 Case3 節點存活時間之關係圖 圖 5.7 Case4 節點存活時間之關係圖 圖 5.8 Case5 節點存活時間之關係圖 圖 5.9 Depth of power-node based subtree: 3 and 圖 5.10 不同具電節點樹深度的節點平均運作時間關係圖 viii -

11 表目錄 表 2.1 IEEE 的工作群組... 9 表 5.1 實驗一模擬參數設定值 表 5.2 Case1 ~ Case5 條件表 表 5.3 實驗二模擬參數設定值 ix -

12 第一章緒論 1.1 前言 近年來, 由於無線網路的蓬勃發展和普及化, 許多應用與技術因應而生 像是無線區域網路 (Wireless Local Area Network,WLAN) 在最近幾年快速崛起, 成為炙手可熱的無線網路技術之一, 舉凡在公共場合中熱點 (Hot Spot) 的建置, 以及各種個人數位通訊設備 (PDA 手機 筆記型電腦) 等, 都是目前常見的無線區域網路應用 而在無線個人區域網路 (Wireless Personal Area Network,WPAN) 上面, 強調低功率以及短距離的特性, 與無線區域網路的應用領域有所區分, 譬如藍芽 (Bluetooth) Z-Wave[17] 以及 ZigBee[15] 等都是屬於無線個人區域網路的技術, 也是近幾年新興的熱門研究議題, 其中之一就是無線感測網路 (Wireless Sensor Network,WSN) 無線感測網路, 其主要的功能在於觀察環境中的一些物理狀態的變化, 譬如溫度 壓力 濕度以及聲音等等 在待觀測環境中佈署多個感測節點 (Sensor Nodes), 透過感測節點的自我組織 (Self-organization) 能力形成無線通訊網路去偵測特定的資料, 並且將感測到的資料透過無線傳輸技術回傳至匯集點或基地台 (Sink or Base Station), 之後再作後續的資料處理 分析以及執行對應的動作 無線感測網路無須人力手工操作以及管理便可以輕易地被建置起來, 因此被廣泛地應用, 舉凡軍事偵察 健康照護 環境監測 居家安全等皆可窺見 目前 IEEE 規格內 TG4 的 IEEE 低速率無線個人區域網路 (Low Rate -Wireless Personal Area Network, LR-WPAN), 其特性為低速率 低能量消耗以及成本低廉, 與無線感測網路的特性相符合, 為目前無線感測網路所使用的規格協定之一 無線隨意網路 (Wireless Ad Hoc Network) 是與無線感測網路最為接近的網路架構, 同為無固定基礎結構 (Infrastructure) 型的網路, 但是在無線感測網路的環境中, 感測網路的節點個數可能從數百至數萬個, 感測節點的運算能力 記憶體空間以及電量供應不足等限制使得網路的運作變得比較複雜, 因此無法將無線隨意網路的路由協定直接套用於無線感測網路, 而且可能因為節點數量眾多 佈署的環境地形險惡不易到達無法輕易更換感測節點上的電池, 導致網路會有損壞的可能, 所以有效的能量管理幾乎是目前感測節點設計以及路由協定設計最主要的考量因素 此外, 因為無線感測網路的多元發展, 除了電量管理外, 容錯機制 睡眠機制 路由協定 網路安全以及服務品質等, 皆為目前無線感測網路的研究議題 - 1 -

13 1.2 研究動機 在目前無線感測網路的研究中, 電量問題一直是熱門的研究議題 每個感測節點將所收集到的資料傳回給 Sink 端, 而感測節點會大量散佈在環境之中, 因為距離 Sink 端有遠近的關係所以不是每個感測節點都可以直接與 Sink 做連結, 那些距離 Sink 端比較遠的感測節點就必須要透過其他離 Sink 端比較近的感測節點幫忙將資料轉送 (Data Forwarding) 給 Sink 端, 因此越靠近 Sink 端的感測節點的負載就越重, 而因感測節點裝置上的電量有限, 當感測節點沒有電時可能會造成底下的感測節點收集到資料沒有辦法傳回 Sink 端導致網路毀損 如圖 1.1 所示, 圖中 A B C 三點為距離 Sink 端最近的感測節點, 除了要將自己的資料傳送給 Sink 端之外還要幫底下的感測節點轉送, 所以負載相對於其他感測節點都還要來的重, 使得 A B C 三點的電量消耗比較快, 而當 A B C 三點沒電時就會造成底下的感測節點無法將收集到的資料回傳給 Sink 端因而造成網路損壞, 此即為所謂的熱點 (Hot Spot) 問題 A B Sink Sensor C 圖 1.1 熱點問題示意圖當那些位於熱點的感測節點損壞時儘管底下的節點都還有電量不過卻沒有辦法把資料回傳給 Sink 端, 熱點問題會縮短節點的運作時間, 因此為了延長網路的運作時間就必須舒緩熱點問題所造成的影響 我們觀察現實生活中的感測節點可以得知, 並非所有節點的電量都是相同的, 譬如在室內某些感測節點可以直接接上電源或者是附屬在電視 冰箱之類的設備上, 因此就能擁有比較多的電量 ; 而在戶外的部分, 感測節點可以 - 2 -

14 結合太陽能提供較多的電量或是放置在走道上或定期巡邏的感測節點, 因為可以定時更換電池所以將其視為擁有源源不絕電量的感測節點, 我們在這裡定義這些比較有電的感測節點為具電節點 (Power-node) 在本論文中, 我們提出了一個主幹感知的網路形成機制 :Backbone-Aware Network Formation(BANF), 利用這些具電節點來舒緩熱點問題造成的影響, 針對不同的實體網路拓樸需求, 透過硬體或是軟體的支援, 在特定的位置擺放具電節點, 利用具電節點建立主幹 (Backbone) 網路 具電節點至少可以與另一個具電節點直接溝通, 多個具電節點可以連結成一條或多條主幹網路, 使得其他感測節點在傳送資料時往離自己最近的具電節點方向傳送即可, 而不需要延續傳統方法, 減少離後端伺服器較近的感測節點的子樹節點也就減緩其電量的消耗 資料負載會分散至主幹網路上每個具電節點上, 熱點轉移至那些距離具電節點最近的感測節點上, 由於負載減輕其消耗的電量就隨之減緩, 使得整個網路的運作時間得以延長 具電節點在 BANF 中扮演很重要的角色, 因此我們針對具電節點這個新的節點類型突然損壞時提出主幹網路修復的容錯機制 1.3 章節簡介 本論文之架構主要分為六章 : 第一章緒論 : 簡述本論文之基本概念 研究動機與目的 第二章背景知識介紹 : 將介紹和分析無線感測網路以及 IEEE 的特性 第三章相關研究 : 將介紹感測網路的路由協定, 並且對路由協定的特色加以分析討論 第四章研究機制 : 將介紹我們的 BANF 設計概念, 並且對 BANF 的運作流程加以詳細說明 第五章模擬結果與討論 : 將說明模擬參數以及環境, 並且對實驗模擬結果加以分析探討 第六章結論與未來工作 : 將對我們的研究做個總結說明, 並且提出未來的研究方向 - 3 -

15 第二章背景知識介紹 2.1 無線感測網路介紹 此章節分為兩個部分, 第一部分介紹無線感測網路的概論 架構以及相關議題 ; 第 二部份針對 ZigBee/IEEE 通訊協定做介紹, 包括其架構 特性 資料傳送模式等 無線感測網路概論 由於近來的微型製造技術 電池技術 嵌入式計算技術與通訊技術的進步, 使得微小的感測節點 (Sensor Nodes) 可具有感應 無線通訊及處理資訊的能力 而此種微型的感測節點常被應用在各種目標物的即時變化感應以及環境物理資訊 ( 溫度 濕度 聲音 光強度 土壤成分等 ) 的變化偵測上, 並且透過佈置感測節點在觀測環境中, 定期收集所需要之資料以無線傳輸的方式回送至基地台 (Base Station) 或資料收集中心 (Sink), 而此時管理者即可透過遠端的方式來觀測以及控制感測的區域, 這就是感測網路最主要的概念 無線感測網路基本架構圖, 如圖 2.1 所示, 由多個感測節點組成, 自己組織形成一個網路, 而網路中的節點可能藉由直接傳送或者多重跳躍等通訊方式將資料傳遞到基地台, 感測節點的傳輸距離一般為數公尺到數十公尺, 為了節省傳輸資料時的能量消耗, 如果感測節點距離基地台太遠, 感測節點必須利用網路路由 (Routing) 的方法經由多個感測節點所組成的路徑將資料回傳至基地台 感測節點屬於微小而且便宜的裝置, 散佈在欲觀測的環境之中, 感測網路的節點個數可能從數百個至數十萬個, 而且感測節點的電池可能無法更換, 因此能量控制幾乎是所有感測節點設計以及網路管理考量的重點, 加上感測節點為便宜的裝置, 故障的機率相對提高, 所以容錯 (Fault tolerance) 機制亦是必須考慮的重點之一 關於無線感測網路, 我們整理它的特性如下 [1]: I. 低製造成本 (Low Cost) II. 低功率 (Low Power) III. 低傳輸速率 (Low Data Rate) IV. 能量有限 (Limited Energy) - 4 -

16 V. 傳輸距離短 (Short Distances) VI. 體積小 (Small Size) VII. 多樣的偵測節點 (Multifunctional Sensor Nodes) VIII. 容錯功能 (Fault Tolerance) IX. 感測節點的數量通常很多, 密度也較高 X. 感測節點網路的傳輸以群播為主並可能需支援多點跳躍傳輸路由 (Multi-hop Routing) XI. 感測節點的網路識別碼不適用傳統 IEEE 802 系列的 6 個位元組 圖 2.1 無線感測網路架構圖 無線感測網路運作方式與目前現有的無線 Ad Hoc 網路極為相似, 它們同為無固定基礎結構 (Infrastructure) 型的網路, 但因感測節點的結構與特性, 使得現有的無線 Ad Hoc 網路協定 (Protocol) 及演算法 (Algorithm) 大多無法直接應用到無線感測網路上 其中導致此結果最主要的幾個原因如下 [2]: I. 無線感測網路的節點數常是 Ad Hoc 網路的數十倍至數千倍 II. 無線感測網路的節點密度高 III. 感測節點十分容易故障 IV. 無線感測網路的網路拓樸 (Topology) 會因為節點損壞而時常改變 - 5 -

17 V. 無線感測網路主要使用廣播通訊 (Broadcast Communication) 而大部份 Ad Hoc 網路使用點對點 (Point-to-Point) 通訊 VI. 感測節點的能量 記憶體及運算能力受到極大限制 VII. 無線感測網路中節點數量眾多, 且可能有多數節點進行著相同的偵測任務, 不易給定節點如 IP 位址般的識別證 (Identification) 在上述提到的這些特性與限制之中, 感測節點的電量管理是被討論最多而且是無線感測網路研究的熱門議題, 而且有限的電量也是無線感測網路與無線隨意網路最大的差異所在 因此在設計無線感測網路協定與演算法時, 電量限制也大都會被納入設計的考慮之中 除此之外, 感測節點容易受到外在環境的影響而發生故障, 所以當感測節點損壞時, 需要擁有足夠的容錯能力, 讓無線感測網路可以正常工作並發揮應有的功能而不受到故障的影響造成網路中斷 因此電量管理 容錯能力以及生產價格幾乎主導了無線感測網路的研究 無線感測網路架構 在無線感測網路的功能架構上, 在這裡以概念上的級別來對無線感測網路的功能架 構做個簡單說明 我們將無線感測網路的協定架構分為五層, 由下而上分別為 : 基礎層 網路層 資料管理及處理層 應用環境發展層以及應用層, 如圖 2.2 所示 圖 2.2 無線感測網路協定架構 在第一層基礎層之中, 主要是以感測節點集合為核心, 包括每個感測節點的軟體 硬體資源, 如感測元件 嵌入式處理器與儲存器 通訊元件 嵌入式作業系統 嵌入式 - 6 -

18 數據庫系統等 而基礎層的功能包括監測感測對象 收集感測對象的訊息 傳輸發佈感測到的訊息以及初步的訊息處理等 網路層則是以通訊網路為主要核心, 實現感測節點與感測節點 感測節點與基地台之間的通訊, 支援整體的感測節點協作完成大型感測任務 網路層包括通訊網路 支援網路通信的各種協定和軟 硬體資源 數據管理及處理層主要以感測節點數據管理與處理軟體為核心, 包括支援各種感測數據的收集 儲存 查詢 分析等各種數據的管理和分析處理的軟體系統, 而有效的支援這些感測收集的數據, 爲管理者的決策提供有效的幫助 應用開發環境層主要是由感測網路中各種應用軟體系統所組合而成的, 目的是爲使用者能夠在基礎層 網路層 數據管理及處理層的開發上, 提供各種軟件的開發環境及工具 我們根據感測節點及基地台的移動性, 將感測網路架構分為靜態 (Static) 及動態 (Dynamic) 兩大種類 在靜態感測網路中, 感測節點及基地台皆不移動, 因此靜態環境中最佳化所額外的能量消耗通常遠小於網路最佳化後所降低的能量損耗, 所以是非常適合進行最佳化網路的結構, 而且靜態感測網路的最佳化演算法通常並不複雜, 因此所需額外消耗的能量也較少 另一方面, 在動態感測網路的最佳化演算法則是相當複雜, 並且其所消耗的額外能量也較多, 同時當網路架構改變後, 網路常需再次進行最佳化, 此時不但網路的偵測功能暫停且必須消耗額外能量, 所以在動態感測網路進行最佳化時則必須把總消耗的額外能量加以比較考量, 而感測網路的拓樸架構如階層式架構 叢聚式架構 鏈狀式架構 樹狀式架構等路由協定便因應而生, 在第三章無線感測網路之路由協定中將作詳細之介紹 無線感測網路議題 目前各項新興的感測網路應用快速發展, 然而目前感測網路中仍有許多問題需要解決, 下面為整理目前感測網路的發展研究及探討之議題 : (1) 存活的時間 (Lifetime): 由於無線感測網路應具有獨立生存的能力, 因此每個感測節點的存活時間以及整體環境的運作週期都是非常重要的議題, 其中包括節點電量 路由演算法 系統內部協定 以及硬體本身的特性, 都需做到考量 (2) 通訊的效能 (Communication Efficiency): 通訊的能力主要在於對每個感測節點之間的溝通 協調, 而主要的考量包括了傳輸距離 以及訊號傳輸的功率 此外, 由於無線感測網路是以群播傳輸為主, 並可支援點 - 7 -

19 對點的傳輸, 因此多重跳躍路由 (Multi-hop Routing) 等相關演算法也是值得研究的 (3) 位置的辨識 (Location Awareness): 對於無線感測網路中每一個感測節點, 其存在於感測網路的相關位置, 可利用路由 訊號的強弱 位置演算法等相關訊息來取得, 甚至可利用衛星或是裝置 GPS 來得知節點的位置 而主要的考量在於如何取得更正確而較少的誤差, 並做出一個正確的監測, 是相關研究文章討論的主要重點 (4) 協調的行為 (Cooperation Behavior): 在無線感測網路中的每個感測節點的行為, 主要是根據基地台群播出訊息之後, 各個節點自行經由路由的訊息傳遞, 進而得知自己所需進行之工作的資訊 如各個節點將自己所行經路徑的資訊, 經由路由將訊息傳遞出去, 而使得其他的節點知道該往那條路徑前進, 才不會造成與其他節點相撞或是行進的路徑重疊, 或者是經由協調將有意義或是優先權較高之感測資料先行傳送或是經過資料聚集融合等工作, 都是屬於此方面的研究 (5) 電力的損耗 (Power Consumption): 電力是影響感測節點運作最大的因素 而關於電力的問題必須要由多方面來做考量, 包括了硬體的選擇或設計 提供電力的設備 通訊協定的運作 以及馬達等機械部份等等 (6) 安全性與私密性 (Security and Privacy): 由於無線感測網路是使用無線傳輸技術, 所以對於傳送訊號的安全性與資料私密性也較為不足, 容易受到威脅 但由於感測網路在目前的應用上和一般 的無線網路有所不同, 感測網路所傳輸的, 通常都是一些控制訊息, 加上感測網路本身傳輸速度慢, 因此一般人不會將它用來做為網路資料傳送的選擇, 不過隨著感測網路的應用逐漸增加, 安全性及私密性也成為極需重視的議題 2.2 IEEE 通訊協定 在 IEEE 的規格內共有四個工作群組, 如表 2.1 而它們之間主要以能量損 耗 資料傳輸速率以及服務品質 (Quality of Service,QoS) 等特性來做區別 每個工作群組主要為 : - 8 -

20 TG1: 藍芽無線個人區域網路 (WPAN/Bluetooth Task Group), 它是一個中等級傳輸速率的 WPAN, 目前的應用非常多, 手機與 PDA 以及電腦設備之間的通訊上都可發現 TG2: 共存式個人無線區域網路 (Coexistence Task Group), 主要是為了提供 IEEE 與 IEEE 相容機制的通訊協定, 研究各個裝置在免執照頻帶中使用, 是否可共享頻寬而不會彼此相互干擾 TG3: 高傳輸速率無線個人區域網路 (WPAN High Rate Task Group), 主要應用在各項多媒體方面, 並且需要較高的傳輸速率 (20 Mbps 以上 ) 與服務品質, 最高速率可達 55Mbps TG4: 低傳輸速率無線個人區域網路 (WPAN Low Rate Task Group), 具有低傳輸速率以及低能量消耗和便宜的特性, 而這些特性便是它符合無線感測網路的重要因素 表 2.1 IEEE 的工作群組 IEEE 架構 目前的 IEEE 低速率無線個人區域網路 (Low-Rate Wireless Personal Area Network,LR-WPAN) 與無線感測網路, 由於其架構與理念近似, 因此被是目前最適合運用在感測器網路實體層 (Physical Layer) 與資料鏈結層 (Data Link Layer) 的規格 而 IEEE 架構的是依照 OSI 模型來建立, 如圖 2.3 在其實體層部分定義了兩個實體層標準, 分別是 2.4GHz 實體層和 868/915MHz 實體層 它們都基於 DSSS(Direct Sequence Spread Spectrum), 使用相同的實體層數據包格式, 區別 - 9 -

21 在於工作頻率 調製技術 擴頻碼片長度和傳輸速率 2.4GHz 波段為全球統一的無需申請的 ISM 頻段 2.4GHz 實體層通過採用高階調制技術能夠提供 250kb/s 的傳輸速率, 有助於獲得更高的頻寬 更小的通訊延遲和更短的工作週期, 因此更加省電 868MHz 是歐洲的 ISM 頻段,915MHz 是美國的 ISM 頻段, 這兩個頻段的引入避免了 2.4GHz 附近各種無線通信設備的相互干擾 868MHz 的傳輸速率為 20kb/s,916MHz 是 40kb/s 這兩個頻段上無線信號傳播損耗較小, 因此可以降低對接收機靈敏度的要求, 獲得較遠的有效通信距離, 可以用較少的設備覆蓋給定的區域 而其 MAC 層控制所有類別之傳送, 支援多種 LLC 標準, 通過 SSCS(Service-Specific Convergence Sublayer) 協議承載 IEEE 類型的 LLC 標準, 同時允許其他 LLC 標準直接使用 IEEE 的 MAC 層服務 網路層提供網路結構 操控及封包路徑等功能, 而應用層則是依照裝置所需功能而制定, 對於網路層和應用層這些屬於上層之通訊協定的部分則有另一組織 ZigBee 在制定相關協定 ZigBee 是一組基於 IEEE 批准通過的 無線標準研製所開發關於網路 安全和應用軟體方面的技術標準並針對其網路層協定和 API 進行標準化 網路層以上協議由 ZigBee 聯盟制定, 而 IEEE 則負責實體層和鏈結層標準 而完整的 ZigBee 協議套件由高層應用規範 應用聚集層 網路層 數據鏈結層和實體層所組成 圖 2.3 IEEE 協定架構

22 2.2.2 IEEE 特性及介紹 IEEE 主要負責實體層和鏈結層的標準, 其特性主要如下 : 其操作頻帶共有三種選擇 : (1) 在 2.4 GHz ISM 頻帶中有 16 頻道, 傳輸速率為 250 Kbps (2) 在 915 MHz ISM 頻帶中有 10 頻道, 傳輸速率為 40 Kbps (3) 在 868 MHz 頻帶中有 1 頻道, 傳輸速率為 20 Kbps 利用 IEEE CSMA/CA 方式競爭溝通 支援低延遲設備 支援 64 位元延伸位址與 16 位元短位址 資料鏈結層中的回應封包 (ACK) 的使用是有可選擇性的 拓樸架構中, 可選擇使用點對點 (Peer to Peer) 星狀(Star) 或者是叢集樹狀 (Cluster Tree) 使用低能量消耗, 並且具有極短的執行週期 在 IEEE 的網路中, 其規格定義了兩種裝置 : 精簡功能型裝置 (Reduced Function Device,RFD) 全功能型裝置(Full Function Device,FFD) 全功能型裝置除了可以與全功能型裝置溝通外, 也可以與精簡功能型裝置通訊, 扮演協調的角色 ; 而精簡功能型裝置就只能夠和全功能型裝置作通訊 數個裝置可以構成一個網路, 我們稱此為個人區域網路 (Personal Area Network,PAN), 其中內部每個成員都依照無線個人區域網路 (WPAN) 的通訊協定進行資料交換 在每個個人區域網路中至少要有一個全功能型裝置作為個人區域網路之協調者 (PAN Coordinator) 在 IEEE 的網路拓樸中可以根據不同應用需求分為兩類 : 星狀拓樸 (Star Topology) 以及點對點拓樸 (Peer-to-Peer Topology) 星狀拓樸如圖 2.4 所示, 主要由一個協調者和其他裝置所組成, 此協調者又稱做 (PAN Coordinator), 每個裝置都與協調者連線, 並且由協調者負責處理所要做的事情 ; 此網路拓樸方式基本上使用 64 位元延伸位址 ; 此外, 協調者可配置 16 位元短位址給裝置以避免頻寬的浪費, 短位址的分配是當裝置與協調者進行連結 (Association) 時取得 協調者因為要負責處理控制問題, 例如 : 控制系統的同步問題 轉換長短位址的對應 處理裝置彼此間的溝通等, 所以需要較大能量, 因此可使用連接式電源, 而其它一般裝置基本上僅需使用電池

23 圖 2.4 星狀拓樸另外一種為點對點拓樸, 圖 2.5, 主要有一個協調者, 和其他裝置 ( 包含精簡功能型裝置以及全功能型裝置 ) 所組成 而其中非協調者的全功能裝置, 可以跟協調者做通訊, 也能夠對在其訊號範圍內的其他裝置溝通, 不過精簡功能型裝置則只能和全功能型裝置連結, 而點對點的拓樸也可以相互連結擴展成更複雜的拓樸方式運作, 例如網狀網路拓樸 (Mesh Networking Topology) 叢集式網路拓樸(Cluster Networking Topology), 並且節點透過多重跳躍的方式傳送資料 圖 2.5 點對點拓樸在通訊方面, 是應用類似 CSMA/CA 的競爭溝通, 而其中可以分類為無信標網路 (Non Beacon-enabled Network) 與有信標網路 (Beacon-enabled Network); 在無信標網路的通訊上, 協調者恆處於聆聽的狀態, 當裝置要回傳資訊時則會先彼此競爭, 等通知協調者後, 再傳送資料給協調者 而有信標網路中, 則含有超級訊框 (Superframe) 的架構, 其固定將包含信標及超級訊框分為 16 個時槽, 超級訊

24 框持續時間 (Superframe Duration) 與信標間距 (Beacon Interval) 依照協調者使用信標級數 (Beacon Order,BO) 及超級訊框級數 (Superframe Order,SO) 來控制, 而彼此關係是 0 SO BO 14, 如此可限制超級訊框持續時間會小於等於信標間距 ; 協調者發送信標, 除了用作同步化外, 也包含網路相關資訊等 ; 超級訊框以有無使用保證時槽 (Guaranteed Time Slots,GTS) 來區別, 有保證時槽的超級訊框可分成兩部分, 一是競爭存取週期 (Contention Access Period,CAP), 另一是無競爭週期 (Contention Free Period,CFP), 而無保證時槽的超級訊框則全都是 CAP 而在資料傳輸模式中, 分成三種類型 : (1) 裝置 協調者 : 在有信標網路中, 如圖 2.6 左圖所示, 裝置必須先跟協調者取得信標與協調者同步, 之後便可以使用時槽型 CSMA/CA 的方式來傳送資料 而在無信標網路中, 如圖 2.6 右圖所示, 裝置利用非時槽型 CSMA/CA 的競爭方式傳送資料給協調者 Coordinator Network Device Coordinator Network Device Beacon Data Data Ack (optional) In a beacon-enabled network Ack (optional) In a non beacon-enabled network 圖 2.6 資料傳輸模式 ( 裝置 協調者 ) (2) 裝置 協調者 : 在有信標的網路中, 如圖 2.7 左圖所示, 當協調者要送資料給裝置時, 協調者會先在信標中夾帶訊息告知該裝置, 當裝置發現協調者有資料要傳給自己, 裝置便會利用時槽型 CSMA/CA 機制競爭媒介使用權, 得到使用權後裝置發送 Data request 訊框給協調者, 之後協調者收到要求後先發送一個回復訊框接著傳送欲傳送給裝置的資料 而在無信標網路中, 如圖 2.7 右圖所示, 裝置必須定期詢問協調者有無資料要傳送

25 給他, 若有則裝置先以非時槽型 CSMA/CA 機制競爭媒介使用權, 接著發送 Data request 訊框給協調者, 詢問協調者有無暫存這筆資料 Coordinator Network Device Coordinator Network Device Beacon Data Request Ack Data Ack In a beacon-enabled network Data Request Ack Data Ack In a non beacon-enabled network 圖 2.7 資料傳輸模式 ( 協調者 裝置 ) (3) 裝置 裝置 : 在對等環境中, 每個裝置可能直接和傳輸範圍內的其他裝置直接通訊 為了更有效率的傳輸資料, 想要傳輸資料的裝置無法進入睡眠模式, 而裝置則以非時槽型 CSMA/CA 機制傳遞資料 ZigBee 網路識別碼分配機制與路由協定 在形成 ZigBee 網路時, 網路中的全功能型裝置 (FFD) 會先互相競爭為協調者角色, 當裝置決定成為協調者時, 協調者首先會搜尋所有的頻道以決定出一個適當的工作頻道, 然後協調者會做初始化程序, 接著開始廣播信標 (Beacon) 訊框傳送給其它尚未加入網路的裝置, 而當裝置接收到信標 (Beacon) 訊框時, 開始執行結合程序 (Association) 成為該感測網路中的路由器 (Router) 或終端裝置 (End device), 此時已加入該網路的裝置會被給定一組網路識別碼, 作為資料傳輸之位址 若裝置成為路由器時, 則開始廣播信標訊框讓其它裝置可以加入成為該路由器之下的子節點 若裝置成為終端裝置時, 則本身不具有發送信標的能力, 也不允許其它裝置加入該終端裝置之下 在同一個 ZigBee 網路中, 裝置間規範了所遵循的分散式網路識別碼分配機制, 以分配網路識別碼給加入該網路之裝置, 其中裝置所分配到的網路識別碼均是唯一的, 並且由父節點 ( 協調者或路由器 ) 分配一個有限的網路識別碼區段給所加入的子節點 ( 路

26 由器與終端裝置 ) 在分散式識別碼分配機制的過程中, 由協調者先定義一路由器最多可允許連接的所有子節點個數 (Cm) 子節點路由器最大的個數(Rm) 以及網路的深度 (Lm) ZigBee 規定 Cm Rm, 因此一路由器至少可容許 (Cm-Rm) 終端裝置連結 裝置的網路識別碼是由其父節點所給定的, 對於協調者而言, 將整個網路識別碼空間劃分成 Rm+1 個區塊, 前 Rm 塊識別碼空間會分配給其 Rm 個子路由器, 保留最後的部份給與其連結的終端裝置 路由器利用 Cm Rm 和 Lm 來計算一個 Cskip 的參數, 利用這個 Cskip 來計算底下的子路由器以及終端裝置的網路識別碼, 假設有個路由器位於網路的第 d 層, 其 Cskip 的數值可以經由下列公式得到 : (2.1) 識別碼的分配是由協調者開始, 協調者會先將自己的識別碼以及深度指定為 0, 假設一個在深度 d 的父節點的網路識別碼為 A parent, 則該父節點的第 n 個子路由器的識別碼為 A parent +(n-1) Cskip(d)+1, 而其第 m 個子終端設備的識別碼為 A parent +Rm Cskip(d)+m 圖 2.8 為 ZigBee 分配識別碼的範例, 其中 Cm=4,Rm=4,Lm=3 圖 2.8 ZigBee 識別碼分配範例

27 第三章相關研究 3.1 無線感測網路之路由協定 整理目前感測網路之路由協定中, 透過參考文獻 [14] 以及分析所研究過的路由協定, 我們對無線感測網路的路由協定做出以下的分類 : I. 若以感測節點傳送資料至 Sink 端的方式, 可以分為四種架構 :(1) 最短路徑優先 (2) 叢集基礎架構 (3) 鏈基礎架構 (4) 擴散基礎架構 (1) 最短路徑優先 : 當節點有資料要傳送時, 會盡量的找尋更接近目的地之節點來幫忙轉送資料, 一般最短路徑的建立方法是由 Sink 端建立到各節點 每當有資料傳送時, 節點即可將資料循最短路徑傳送到 Sink 端 (2) 叢集式基礎架構 : 主要概念是將感測網路依照地理區域分成多個叢集, 然後每個叢集都會選出一個感測節點擔任叢集頭, 叢集的成員只要將資料傳送給叢集頭即可, 而叢集頭則會將收集到的資料傳遞給 Sink 端 (3) 鏈基礎架構 : 主要概念是將感測節點形成一條或數條鏈架構, 而每個鏈都會有一個感測節點擔任鏈頭, 節點只需要將資料往鏈上靠近鏈頭的鄰居傳遞, 最後鏈頭則會將鏈上的資料收集並傳回給 Sink 端 (4) 擴散基礎架構 : 主要運作方式如同一般路由協定的氾濫法 (Flooding), 因此擴散即是透過不斷的廣播傳送將資料傳遞至目的地 II. 以感測節點如何獲取路由的資訊做分類, 可以分為三種類型 :(1) 預先設定型 (Proactive) (2) 反應型 (Reactive) (3) 混合型 (Hybrid) 預先設定型是指所有的路由都在收集資料前就被設定好, 並且將這些路由資訊廣播給感測節點, 因此非常適合靜態的環境架構 反應型則是當節點需要傳送資料提出請求的時候, 感測節點才開始去計算路由, 通常應用在動態架構的環境上 最後混合型則是結合前兩者的另一種型態 III. 以收集感測資料的環境做分類, 設計的路由協定可以是針對以下四種環境來做設計 :(1) 連續型 (Continuous) (2) 事件驅動型 (Event-driven) (3) 觀測者啟動型 (Observer-initiated) (4) 混合型 (Hybrid) 連續型的路由協定即是以週期性收集資料為主, 也由於收集資料的時間固定, 因此非常適合預先設定路由 而事件驅動型的路由協定則是以事件的發生為資料收集的觸發點,

28 如溫度過高而觸發節點傳送緊急訊息等 觀測者啟動型為觀測者透過 Sink 端對感測網路發出命令, 而感測節點針對命令將指定的資料傳回 Sink 端 最後混合型就算是將前三者做組合的類型 IV. 分析路由協定的拓樸以及傳送型態, 可以分為三種類型 :(1) 直接傳送 (Direct) (2) 平行傳送 (Flat) (3) 叢集式傳送 (Cluster) 直接傳送是指感測節點直接將資料傳送回 Sink 端, 不過這必須要 Sink 端與感測節點距離相當靠近時才能採用 平行傳送的話類似 PEGASIS[6] 的路由協定, 並且通常會搭配利用 CDMA 的機制 叢集式傳送則是將感測節點分成多個群組, 再收集資料作傳送 V. 針對感測節點位置對路由協定做討論, 又可以分類為 : (1) 位置已知型 (Location-aware) (2) 位置未知型 (Location-less) 位置已知型協定非常適合用來進行事先設定路由的動作, 也容易進行最佳化路由的計算, LEACH-C[5] 即屬於此類, 通常在節點上透過裝置 GPS 或者是透過進行定位的協定, 即可達到 而 [12] 則是位置未知型的協定的典型 VI. 若以控制方式區分, 路由協定又可分為兩種類型 :(1) 集中式運作 (2) 分散式運作 一般在位置已知型的環境非常適合做集中式的路由設定, 而位置未知的環境則通常採用分散式的處理 由於感測網路的多變, 各種不同的環境及應用都可能是影響分類的因素, 甚至 Sink 端的遠近 Sink 端的移動性 感測節點的移動性等也都可能成為設計路由協定的分類準則 3.2 叢集式基礎架構 :LEACH 叢集式基礎架構方式是將感測網路根據地理區域分成多個叢集 (Clusters), 每個叢集由其若干感測節點中選出一個叢集頭 (Cluster Head) 負責收集該叢集中所有節點的資料, 然後回傳給 Sink 端 叢集的好處在於能將整個網路區域化, 除了可以減少傳輸次數 節省通訊成本, 亦可提升網路擴充性 以往的叢集方式中, 在選定擔任叢集頭的節點後, 就不會更換, 使得擔任叢集頭的節點能量快速耗盡, 而為了改善此問題, 發展出採用輪流的方式或是選出最合適者 ( 譬如 : 選擇剩餘電力最多的節點 ) 來擔任叢集頭之概念, 而其中 LEACH 是叢集式架構中最具有代表的路由協定

29 圖 3.1 LEACH 叢集式基礎架構 LEACH(Low Energy Adaptive Clustering Hierarchy)[4], 如圖 3.1 所示, 主要是將多個鄰近的感測節點集合組成叢集, 每個叢集再經由一定的程序選出一個叢集頭 (Cluster Head), 由叢集頭負責將此叢集中其它感測器節點的資料進行資料融合後傳送給 Sink 端, 如此可避免每一個感測節點都個別將資料傳送 Sink 端而造成能量大量且不必要的消耗 為了要能平衡叢集中各個感測節點的能量消耗,LEACH 讓所有節點都輪流擔任叢集頭, 其運作方式為週期性的讓節點根據一個機率值來決定自己是否成為叢集頭, 成為叢集頭後的節點必須廣播訊息告訴其鄰近節點, 收到此訊息的節點會選擇對自己而言是最省電的叢集頭來加入該叢集, 當所有節點都成功加入叢集後, 每個叢集頭採用 TDMA 方式對其叢集內的所有節點進行排程, 使得自己叢集內的其他節點能依序將資料傳給自己而不造成碰撞, 在收集完自己叢集內所有節點的資料後, 叢集頭便直接傳給 Sink 端 LEACH 採用機率方式選出叢集頭, 避免特定節點過度消耗電力提早失效, 除了叢集頭外, 其餘節點不與 Sink 端直接通訊以減少回傳次數, 並且叢集頭所執行的資料融合會將多筆資料進行合併才回傳給 Sink 端, 藉由刪除冗餘資料達到降低通訊的資料量, 有效地節省能量消耗, 進而提升了整體網路的生命週期 但是在叢集式架構下有一個負載不平衡的現象, 如圖 3.2(a) 中,B 區的叢集頭所負責的成員數比 A 區多, 因此 B 區叢集頭消耗的能量就會較 A 區多 此外, 如果只是單純的依據機率值來選擇叢集頭, 必須考慮到幾個問題, 例如 : 叢集頭是否彼此都很接近 選到的叢集頭剩餘能量是否足夠傳送資料到 Sink 端 叢集頭是否很接近邊界等 圖 3.2(a) 中, 所選出的叢集頭彼此都很接近且也很靠近其叢集的邊界, 然而對於應用而言, 圖 3.2(b) 的均勻分佈方式是較佳選擇, 因此在選擇叢集頭時, 也應考量其他因素, 例如 : 節點剩餘的電力 [5] 最後在 LEACH 中的叢集頭能夠將收集到的資料直接回傳給 Sink 端, 倘若節點散佈在廣闊的環境之中,

30 要讓叢集頭直接與 Sink 端通訊似乎是不太合理, 若真的能夠實現, 那麼離 Sink 端較遠的叢集頭所消耗的能量就會比離 Sink 端較近的叢集頭要來的多, 反而加速了叢集頭的能量消耗速度 圖 3.2 LEACH 叢集頭選擇範例而除了分散式的叢集式架構外,LEACH 也提出在中央控制環境下的叢集式架構, LEACH-Centralized(LEACH-C)[5] 在中央控制環境中, 前提是 Sink 端需要擁有感測節點能量以及位置的資料, 利用這些資料 Sink 端對於叢集頭的選擇以及叢集的分配, 將可以容易計算出較佳效能的分割方式, 進而在 LEACH 中提升了非常多的效能 3.3 鏈基礎架構 :PEGASIS 鏈基礎架構概念將網路上的感測節點組成一個或數個鏈 (Chain), 鏈上會有一個節點擔任鏈頭 (Chain Head), 其餘節點只要將資料朝向鏈頭方向傳給距離自己最近的鄰近節點即可, 當鏈頭收集完鏈上所有節點的資料後就直接傳給 Sink 端 PEGASIS(Power Efficient Gathering in Sensor Information Systems)[6][7][8] 是將網路中的所有節點相互連結成一條鏈, 如圖 3.3, 在每回合 (Round) 中, 從鏈架構的節點裡選擇出一個鏈頭, 鏈架構兩尾端的節點開始將資料透過相鄰的節點往鏈頭方向傳送, 並且每個接收到資料的節點都會進行資料的融合, 最後由鏈頭將資料傳送至 Sink 端, 如圖 3.4 在鏈架構中, 每個節點僅與離自己最近之鄰近節點進行資料通訊,

31 並輪流擔任鏈頭與 Sink 端通訊 而為了能成功建構鏈, 必須知道整個網路的拓樸架構, 即每個節點都知道網路中其他節點的位置, 進而得出其鄰近節點資訊 PEGASIS 中鏈架構的相鄰節點是使用 Greedy 演算法所形成, 鏈頭只會收到來自其左右相鄰近節點的兩個訊息, 這樣可避免叢集式架構中的負載不平衡問題, 且每一回合僅有一個節點會傳送資料給 Sink 端, 相較於 LEACH, 降低了資料量與傳輸次數, 可以更加地延長網路生命週期 PEGASIS 中採用節點輪流擔任鏈頭的方式來平均電力消耗, 但是那些距離 Sink 端較遠的鏈頭的能量消耗自然會比距離 Sink 端較近的鏈頭多, 所以仍然會造成部分節點提早耗盡能量而必須重新建構鏈, 而且, 節點每次僅與相鄰近節點通訊, 鏈架構愈長, 資料傳遞延遲就愈嚴重, 導致鏈頭就愈晚收集到資料 因此 PEGASIS 的缺點是當形成的鏈架構越長, 會導致資料傳送至鏈頭的傳遞延遲時間也就越久, 而透過 CDMA 機制或者透過建立多鏈 (Multi-chain) 的架構可降低其延遲時間的影響 ; 另外, 形成鏈架構的複雜度較高, 節點所需負擔的能量消耗亦是一個問題 圖 3.3 鏈架構建置範例 圖 3.4 鏈架構資料傳送方式

32 3.4 資源導向協定 :ROP 資源基礎架構的提出主要是因為在現實生活中並非所有感測節點的電量都是相同的, 所以利用電量不均等的特性提出資源基礎協定 (Resource Oriented Protocol, ROP)[9][10] 找出那些比較有電的節點讓他們擔任叢集頭的角色, 給予其較大的流量負載, 而其他比較沒有電量的節點僅需要把欲傳送的資料傳給鄰近的叢集頭即可, 透過叢集頭將資料送達至目的地 在資源導向協定中根據感測節點的電量大小分成三種不同的類型, 依照電量大小依序為 LRC(Large Resource Capacity) MRC(Medium Resource Capacity) SRC (Small Resource Capacity) 如圖 3.5 所示, 節點 D 想要傳送資料給節點 E, 而原本的傳送路徑可能為 D F G B E, 而在 ROP 中,D 會先將資料傳給區域內的叢集頭 A,A 再傳給能力最強的 C, 最後 C 直接傳給 E, 所以路徑就變成了 D A C E, 避免經過那些電量比較不足的節點來延長網路的生命週期 圖 3.5 ROP 範例說明而 ROP 的架構可以分成兩個階段, 如圖 3.6 所示, 第一階段為拓樸形成 (Topology Formation), 和第二階段拓樸更新 (Topology Update) 在第一階段之中, 每個感測節點向各自的鄰居廣播自己的電量, 而根據收到的資訊節點可以自己定義為 LRC MRC 或 SRC 任一種類型 : LRC: 若收到的資訊發現鄰居的電量都比自己還要少甚至差距很大, 則將自己定義為能力最強的 LRC MRC: 若收到的封包中鄰居的電量有比自己小的也有比自己還要大的, 便將自己定義成能力中等的 MRC, 扮演區域叢集頭的角色

33 SRC: 收到的資訊裡鄰居的電量都比自己的還要大或是差不多, 則將自己定義 成能力最弱的 SRC 圖 3.6 ROP 處理程序定義好節點的類型後,MRC 收集剛剛收到的鄰居電量的訊息傳給 LRC, 而 LRC 之間再去做協調, 建立出負載比較平均的網路的拓樸, 再將整個網路拓樸廣播告訴所有的 MRC,MRC 會紀錄到達自己的 LRC 的路徑, 而 SRC 只需知道到達自己的 MRC 的路徑即可, 拓樸形成的流程圖如圖 3.7 所示 當拓樸形成之後便開始正常的運作, 而此時便進入到拓樸更新階段, 若節點有任何異動便啟動相關的程序讓網路達到穩定性 而 ROP 若用於感測節點比較多的環境之中, 其拓樸形成階段便會耗費不少時間, 而且在 ROP 中是由 MRC 收集底下 SRC 的資料後將其融合傳給 LRC, 似乎是不太適合於需要即時性服務的應用上

34 Broadcast resource characteristics Time SRC Decide resource levels MRC Aggregated data report to LRCs LRC Broadcast its neighbors Contact other LRCs Broadcast Topology Receive Topology Packet Receive Topology Packet 圖 3.7 ROP 拓樸形成流程圖 3.5 不相等的叢集架構 :UCS 在無線感測網路中, 叢集式架構通常會被拿來延長網路的生命週期, 然而叢集式架構可能會有叢集頭電量消耗不平均的問題, 倘若叢集頭可以直接送資料給 Sink 端, 則距離 Sink 端較遠的叢集頭電量消耗較多, 若透過多重跳躍因為距離基地台比較近的叢集頭必須要幫忙那些距離基地台比較遠的叢集頭轉送資料給基地台所以電量消耗會比較多, 因此為了解決叢集頭電量消耗不平均的問題而有了不相等的叢集架構 (Unequal Clustering Size,UCS)[11] UCS 架構如圖 3.8 所示, 將感測節點平均分布在區域之內, 根據感測環境大小以及感測節點個數等參數事先計算出叢集頭的擺放位置, 而由電量比較多的節點擔任叢集頭, 因為感測節點是平均分布, 所以根據叢集的區域大小就可以知道掌控多少節點 一般多重跳躍的叢集式架構中, 距離基地台比較近的叢集頭除了要幫自己掌管的節點傳送資料外還需要幫底下的叢集頭轉送資料給基地台, 因此其負載會比底下的叢集頭還要大, 也就是第一層的叢集頭比第二層的負載大, 所以 UCS 為了平均不同層別叢集頭的負載, 讓第一層的叢集頭掌管的區域比第二層要來的小, 這樣第一層的叢集頭掌管的節點就比較少, 如此電量消耗變少再加上幫第二層的叢集頭轉送資料消耗的電量, 使得第

35 一層與第二層的叢集頭電量消耗能夠均等 而在 UCS 中, 還可以將環境擴充為每個節點的電量相等, 而叢集頭的角色就由節點輪流擔任, 平均消耗節點的電量 在 UCS 中除了可以利用叢集頭將資料融合傳給基地台節省電量外, 也可以利用叢集頭傳送即時性的資料, 儘管 UCS 可以平均不同層別的叢集頭的能量消耗來達到延長網路的生命週期, 但是因為在叢集內的節點是與叢集頭直接通訊, 所以會造成叢集內的節點因為距離叢集頭的遠近而造成電量消耗不均的問題 圖 3.8 UCS 架構 3.6 其他 除了上述的各種架構的路由協定外, 在感測網路中最原始的資料收集方法就是最短路徑優先選擇方法, 但是單純只透過最短距離的路徑選擇, 往往會導致了網路中某些區域的節點成為熱點 (Hot-spot), 並且消耗大量的能量, 造成了熱點感測節點的快速死亡而造成網路斷裂, 形成能量不平衡的狀態 因此之前討論的各種路由協定也都將平衡能量的方法以及節省能量機制列入考量重點 而在感測網路之中最有效的節省能量機制通常是使用睡眠機制, 如 [13] 中, 感測節點加入網路後和鄰居之間彼此溝通好傳送資料的時間, 彼此做好同步化後變進入睡眠模式, 為有在節點本身為接收者或發送者時才需要起來處理資料, 藉由節點長期處於睡眠來延長網路的生命週期, 而且此方法也可以相容於 ZigBee 協定, 但是這個機制可能無法是用於即時性的應用上, 而且當感測節點數量太多時同步化可能會是一個問題, 並且會使得繞送協定變得很複雜

36 歸納上述各種架構的路由協定, 最後整理我們提出 BANF 的原因如下.. 由於傳輸所消耗的電力與距離遠近成高度相關, 因此在資料的傳送距離上儘可能的縮短 如鏈架構其節點只需傳送資料至鄰居節點 叢集式架構以叢集做區分來縮短點與點的傳送距離 環境佈置具電節點 (Power-node) 由於感測網路的節點皆具有能量限制, 根據現實環境中的特性, 若是可以透過佈置少數的具電節點, 讓其他一般節點利用這些特殊裝置和位於遠處的 Sink 端或基地台進行溝通並且幫忙轉送封包等, 這樣可以節省一般節點的電力消耗, 並且擁有更大的運用空間 精簡明確的路由協定, 由於過多的控制訊息或者是複雜的路由協定對於節點的能量消耗都會形成負擔, 因此讓節點可以自動且快速的形成網路減少不必要的控制訊息, 節省節點的電力消耗

37 第四章 BANF 機制 無線感測網路是由許多電量微小的感測節點所組成, 並且節點的電量通常是固定的用完便無法補充, 因此如何有效的節省感測節點能源並且延長整體感測網路的生命週期, 是一個相當重要的研究議題 我們從上述幾個叢集式架構的概念得到了啟發, 叢集頭的角色在叢集式架構中非常重要, 配合現實生活中並非所有節點的電量都是相同的特性, 因此我們利用那些比較有電的節點提出一個新的網路形成機制 :Backbone-aware Network Formation(BANF), 我們在無線感測網路中新定義了一種節點類型 : 具電節點 (Power-node), 透過多個具電節點建立起主幹網路 (Backbone), 改變網路的拓樸架構並且延伸整體感測環境收集資料的運作時間, 在此章節我們將會說明 BANF 的環境假設及其架構並且介紹 BANF 的運作流程 4.1 BANF 設計概念與目標 現實生活中的感測節點的電量並非是相等的, 譬如在室內的環境中某些節點可以直接接上電源或是依附在電視 冰箱等電器上, 所以這些節點的電量相對於其他節點就來的比較多 ; 而若在戶外的感測環境, 可以在感測節點上裝置太陽能電池來提供其電量, 由於太陽能設備通常比較昂貴, 所以僅能加裝在特定位置上的感測節點, 另外如果節點位於管理者能夠定期巡邏的位置上或走道上, 那麼我們也將其視為電量比較充足的節點, 儘管這些節點只裝置一般電池, 因為管理者可以很快的知道節點是否快沒電並且提供更換電池的服務 我們把上述所說的這些電量限制比較小的感測節點定義成新的節點類型 : 具電節點 (Power-node) 而這些具電節點我們可以經由軟體也就是程式的修改或節點本身的硬體設定與其他一般節點做區分 在這裡我們將 ZigBee 所定義的全功能型裝置以及精簡功能型裝置皆稱為一般節點 (Regular Node) 我們的 BANF 機制就是希望利用這些具電節點串連成一條或多條主幹網路 (Backbone), 使得一般節點只需要將資料往主幹網路的方向傳送即可, 而不須和傳統的傳送方式一樣單純地往協調者 (Coordinator) 或 Sink 端送, 將那些原本距離協調者比較近的節點的流量負載分散到其他的節點上面, 舒緩熱點 (Hot-spot) 問題所造成的影響, 進而達到延長感測網路運作時間的目標 BANF 的運作流程主要為主幹網路建立與一般節點加入這兩個程序, 其中主幹網路建立階段為一開始在感測環境之中散佈感測節點, 先將主幹網路建立完成後進入一般節點加入階段讓其他一般節點加入到感測網路, 當整個網路建構完成後感測節點便開始進

38 入工作狀態, 將自己所感測到的資料傳回給協調者做分析 處理 具電節點在我們的 BANF 機制中扮演著相當重要的角色, 因此在感測網路的工作期間考量到具電節點可能會因不明原因突然損壞或是因為管理者來不及更換其電池而造成網路暫時斷路, 所以針對我們新定義的具電節點損壞的問題, 定期偵測具電節點是否正常運作, 若具電節點損壞則進入主幹網路修復階段, 以期能夠暫時恢復主幹網路的連線 4.2 BANF 運作流程 主幹網路建立階段 我們提出的 BANF 機制是在 ZigBee 網路環境下做討論, 利用 ZigBee 網路的深度特性, 原來的 ZigBee 網路中將感測節點到協調者需要經過幾個節點當成此節點的深度, 深度越深代表距離協調者越遠, 而協調者的深度為 0,BANF 修改原來的 ZigBee 網路中深度的定義來達成延長網路生命週期的目標 BANF 的第一個階段為主幹網路建立, 一開始在特定的位置上擺放具電節點將主幹網路建立起來, 而這些具電節點有下列三個特性 : 至少有一個具電節點能夠直接與協調者通訊 具電節點的訊號範圍內至少要有一個具電節點, 也就是說鄰居至少要有一個具電節點存在 具電節點的訊號範圍可以比一般節點還要大, 因為具電節點的電量限制小, 所以具電節點的可傳輸距離能設定的比一般節點遠 我們的 BANF 必須先將主幹網路 (Backbone) 建立起來, 事先得知欲感測環境的架構並且在特定的位置 ( 負載較重 走道或定期巡邏的點 ) 上擺放具電節點, 透過這些具電節點形成一條或多條主幹網路 而具電節點加入感測網路的步驟如下 : I. 具電節點搜尋鄰居的節點, 建立鄰居表格 (Neighbor table) II. 具電節點從鄰居表格中選取深度 (Depth) 最低的一個節點提出加入網路的要求 III. 收到具電節點連結要求的節點 ( 通常也為具電節點 ) 配置一個網路識別碼給此具電節點並回覆要求 IV. 具電節點收到回覆後即表示加入網路成功, 發出信標 (Beacon) 告訴鄰居自己的存在, 而在信標中自己的深度設為

39 範例如圖 4.1 所示, 節點 A 已經成功加入感測網路而因為其為具電節點所以深度為 1, 而現在具電節點 B 要加入到網路中, 在 B 的訊號範圍內可以偵測到節點 A, 因此 B 向 A 提出加入網路的要求,A 收到 B 的加入要求後配置一個網路識別碼給 B 並且將此訊息回覆給 B, 而節點 B 得到網路識別碼後便表示成功加入網路, 因為 B 為具電節點所以 B 的深度不同於 ZigBee 網路的規則為父節點的深度加 1, 在這裡我們將 B 的深度也設為 1, 目的在於希望低深度可以吸引多其他節點在傳送資料時有比較大的機率會經由 B 送往協調者 圖 4.1 BANF 具電節點加入網路我們會事先將主幹網路建立起來, 當然也可以根據網路實際運作狀況適時地新增具電節點減輕其他一般節點的負擔, 如圖 4.2(a) 的情況, 節點 A 由於是具電節點所以不考慮其電量消耗的影響, 而在其中節點 B 為負載較重的一般節點, 因此在我們的 BANF 機制運作下可以在流量負載比較重的地方新增具電節點如圖 4.2(b), 新增了具電節點 F, 當 F 成功加入網路後會發出信標讓鄰居知道自己的存在, 而節點 C D E 聽到 F 的信標後發現 F 的深度比較低, 因此便會脫離原來的父節點 B 而向 F 提出加入網路的要求, 這樣的結果雖然會造成具電節點 F 的負載增加, 不過因為 F 是具電節點對其影響不大, 但卻能夠減輕一般節點 B 的負載, 讓 B 可以有更長的運作時間

40 4.2.2 一般節點加入階段 圖 4.2 BANF 新增具電節點範例 當主幹網路建立完成後則是一般節點加入階段, 當一般節點欲加入到網路時, 若偵測到多個鄰居, 可以根據連結的優先順序來抉擇, 而其選擇方式如圖 4.3 所示, 一開始先從鄰居中選擇最靠近主幹網路上的節點 ( 最靠近具電節點或是最靠近協調者 ), 也就是深度最低的節點做連結, 倘若最低深度的節點只有一個便直接跟此節點提出加入網路的要求 ; 如果發現有多個最低深度的節點, 則首先判斷其是否有具電節點, 如果存在多個具電節點鄰居就選擇離協調者最近的具電節點連結 ; 如果鄰居皆非具電節點又具有相同最低深度則從中選擇距離協調者較近的節點連結, 如此確保一般節點將資料送給協調者的路徑經過主幹網路是最短的, 以便減少延遲的時間

41 圖 4.3 Association priority 從範例中可以知道 BANF 和原來 ZigBee 網路的不同, 如圖 4.4 所示, 一般節點 N 想要加入網路, 而在 N 的訊號範圍內有節點 A 和 C 兩個鄰居, 而原來的 ZigBee 選擇機制節點 N 會跟節點 A 提出加入網路的要求, 因為在 ZigBee 中並不知道節點 C 為具電節點而且節點 A 的深度比較低, 因而加重了一般節點 A 的負載, 如圖 4.5(a) 所示 ; 而在我們的 BANF 中, 如圖 4.5(b) 所示, 節點 N 會發現節點 C 的深度比較低, 因此會跟具電節點 C 提出加入網路的要求, 減輕一般節點 A 的負載

42 圖 4.4 Regular node N wants to join the PAN 圖 4.5 Different with ZigBee and BANF

43 關於 BANF 的路由協定 (Routing) 以及實現, 因為我們是在 ZigBee 的網路環境下討論, 原來的 ZigBee 路由協定是使用可繞送識別碼 (Routable Identity) 而詳細運作過程如前面 節所提, 以協調者為樹根 (Root) 向外長出樹狀架構, 比對識別碼的大小將資料繞送到正確的目的地 而為了具體實現 BANF 機制, 我們修改原來的 ZigBee 分散式識別碼分配機制, 將其擴充為兩層式可繞送識別碼 (Two Levels Routable Identity), 將 ZigBee 的 16 位元網路識別碼切成兩個區段, 如圖 4.6 所示, 前半段稱為具電節點層提供給協調者以及具電節點分配網路識別碼給底下的具電節點使用, 而後半段為一般節點層提供父節點 ( 包含協調者 具電節點和一般節點 ) 分配網路識別碼給底下的一般節點 圖 4.6 兩層式可繞送識別碼 BANF 之所以使用兩層式可繞送識別碼是希望原本 ZigBee 網路中網路識別碼是以協調者為樹根開始命名, 而現在希望節點的資料流向可以先送往主幹網路, 再透過主幹網路將資料送達協調者, 因此採用兩層式可繞送識別碼, 一般節點可以根據自己的識別碼區段中的一般節點層得知自己繞送至父具電節點的資訊, 若一般節點有資料要傳送至協調者或是其他具電節點底下的節點時都要先將資料送至父具電節點再由父具電節點做處理 ; 若協調者有資料要送給一般節點時便會先看具電節點層的識別碼透過主幹網路繞送至指定的具電節點後再將資料傳送至目的地節點 而其中兩個區段只要是可繞送識別碼皆可使用, 譬如 ZigBee 識別碼分配法 質數識別碼分配法, 而 BANF 則是兩個區段都使用 ZigBee 分散式網路識別碼分配機制, 由於不是本論文的研究範圍在此便不多加討論 另外兩層式可繞送識別碼中兩區段的大小可以根據不同感測網路環境的需求而有所彈性變動 不同的感測環境就會需要不同的主幹網路架構, 然而識別碼固定為 16 位元, 可以根據環境不同而彈性分割, 在比較狹長的環境之中, 建立主幹網路可能需要擺放多一些具電節點才能夠達成, 因此可以增加具電節點層的識別碼使用位元來因應 ; 若是在比較中廣的環境下, 每個具電節點需要掌管的一般節點數目可能很多, 可以藉由增加一

44 般節點層的識別碼位元來實現 BANF 可以彈性地調整具電節點層與一般節點層的識別碼使用位元使其能符合各種不同的感測環境特性, 而此兩區段的位元分配方式亦不在本論文的研究範圍內 主幹網路修復階段 在 ZigBee 網路之中的一般節點倘若損壞則底下的子節點可以再一次搜尋鄰居重新選擇一個深度低的節點當作父節點加入到網路, 或是利用類似 AODV 的方式搜尋出去的路徑 而在 BANF 中, 一般節點損壞的話仍然可以沿用 ZigBee 路由協定內原本定義好的處理程序, 然而 BANF 的主幹網路是透過新定義的具電節點才能夠建構完成, 因此具電節點對於我們的架構相當重要, 倘若具電節點因為不明原因損壞或是管理者來不及更換具電節點的電池而暫時沒電時需要有個容錯機制讓主幹網路的連線可以維持以便確保感測資料可以正確地回傳至後端, 因此我們提出具電節點損壞的容錯處理機制 我們所提出的主幹網路修復階段, 針對具電節點損壞提出主幹網路修復機制, 分成三個有先後順序的處理程序, 第一階段為利用其他具電節點的鄰居維持主幹網路的連線 ; 而第二階段則是利用底下具電節點的具電節點鄰居建立新的主幹網路連線 ; 第三階段為利用一般節點來維持主幹網路的連線, 以下分別就這三個處理機制做說明 具電節點加入至網路後會定期詢問父具電節點是否正常運作, 倘若在一段時間內偵測不到父具電節點則視為父具電節點已損壞, 此時具電節點便會進入主幹網路修復處理程序, 流程圖如圖 4.7 所示, 大致程序為 : I. 當具電節點發現父具電節點損壞後, 首先搜尋自己的鄰居表格查看是否有屬於具電節點的鄰居存在, 進入第一階段主幹修復程序 II. 第一階段修復程序, 如果具電節點有找到屬於具電節點的鄰居則向其提出加入網路的需求, 重新要一個網路識別碼連上網路, 成功連結後即可正常傳送資料, 離開主幹修復程序 ; 如果鄰居中沒有找到具電節點的鄰居則進入主幹修復第二階段程序 III. 第二階段先確定底下是否有具電節點也就是子具電節點的存在, 若無則進入至第三階段, 若有則詢問子具電節點是否有屬於具電節點的鄰居, 而子具電節點檢查後發現有屬於具電節點的鄰居則回報具電節點, 而具電節點便以子具電節點為父節點, 向其索取識別碼重新加入至網路, 角色互換讓子具電節點當成是自己的上游, 成功連結後便可正常傳送資料, 離開主幹修復程序 而這個程序會一直持續直到底下的具電節點都詢問過, 倘若子具電節點皆詢問完仍無法完成主幹網路的修復則進入第三階段

45 IV. 倘若在前兩階段皆無法完成主幹網路的重建, 則進入到主幹修復第三階段, 利用一般節點來重建主幹網路, 在這裡我們提供了一種利用一般節點的重建方式, 具電節點會搜尋鄰居挑選深度最低的一般節點向其提出連結要求, 收到要求的一般節點會發現有具電節點向其提出連結要求, 因此一般節點除了給此具電節點一個由它管轄的網路識別碼外, 還會將此訊息回傳給自己的父具電節點, 由父具電節點分配一個具電節點層的識別碼給提出連結要求的具電節點使其擁有兩個識別碼可供繞送使用, 對外以具電節點層的識別碼顯示, 如此透過一般節點維持主幹網路的連線 在這裡我們僅提供了一種利用一般節點重建主幹網路的方法, 可能還有其他更好 更有效率的做法值得研究討論, 這部份由於不是本論文的主軸因此不多加討論留待未來工作完成 Search neighbors if any power nodes If any neighbor is power node? No Ask power node children if they have power node neighbors Yes Have power node neighbors? Choice one and send association with it Yes Associate with powernode children No Search neighbors and associate with the node with the lowest depth Data communication 圖 4.7 主幹網路修復流程圖

46 倘若在我們所提出的主幹網路修復程序完成主幹網路重建, 後續還有一些細節需要處理, 因為 BANF 是使用可繞送識別碼實現, 因此當具電節點換父節點時需要更換識別碼, 而底下的節點不管是子具電節點還是一般節點也都需要做更換識別碼的動作, 而這部份由於節點會定期去偵測父節點是否還存活, 因此也可同時偵測父節點的識別碼是否有變動, 若發現變動則重新向父節點索取新的識別碼, 確保能正確的繞送資料 以下就三個修復程序分別舉例說明, 圖 4.8 是一個 BANF 架構的網路, 具電節點 G 跟具電節點 B 有潛在的連結存在, 如果具電節點 F 突然損壞,F 底下的一般節點會搜尋鄰居尋找其他出路, 而具電節點 G 發現 F 不見後會先搜尋鄰居發現有具電節點 B 的存在, 因此向 B 提出加入網路的要求, 當 G 成功加入後即可離開主幹網路修復程序, 此時 G 的網路識別碼做了更動, 因此以 G 為父節點 ( 包含一般節點以及具電節點 H) 都會偵測到 G 換了識別碼, 所以會重新跟 G 提出加入網路的要求索取新的識別碼, 而底下的節點也會產生連鎖效應陸續跟自己的父節點索取新的識別碼, 最後完成的結果如圖 4.9 所示, 此為主幹網路修復第一階段程序 圖 4.8 主幹網路修復第一階段範例

47 圖 4.9 主幹網路修復第一階段結果 圖 4.10 主幹網路修復第二階段範例而 BANF 主幹網路修復第二階段, 範例如圖 4.10 所示, 如果現在具電節點 F 突然損壞, 其底下的子具電節點 G 會偵測到並且進入主幹網路的修復程序, 而 G 一開始檢

48 查鄰居沒有發現其他具電節點的鄰居, 因此進入到主幹網路修復第二階段發現底下有子具電節點 H 的存在, 詢問 H 是否有具電節點的鄰居, 而在此範例中 H 與具電節點 C 是鄰居有個潛在的連結存在,H 將此訊息回報給 G,G 收到後便轉而向 H 提出加入網路的要求, 而 H 會以 C 會父節點連上網路後同意 G 加入網路的要求, 因此 G 和 H 的父親與兒子的角色互換, 最後的結果如圖 4.11 圖 4.11 主幹網路修復第二階段結果主幹網路修復第三階段範例如圖 4.12, 具電節點 F 突然損壞,G 偵測到後查詢鄰居沒有其他具電節點而子具電節點也無具電節點的鄰居, 因此進入到主幹網路修復第三階段, 最後結果如圖 4.13,G 搜尋鄰居選擇深度最低的一般節點 J 提出加入網路的要求, J 收到具電節點 G 的加入要求後, 除了分配一個識別碼給 G 還會將此訊息再傳給父具電節點 B,B 會分配一個具電節點層的識別碼給 G, 如此 G 便擁有兩個不同的識別碼,B 和 G 之間無法直接送達需要透過中間的一般節點轉送, 利用識別碼轉換讓資料能夠在 B 和 G 之間正確繞送,G 向外則以具電節點層的識別碼顯示, 深度仍為

49 圖 4.12 主幹網路修復第三階段範例 圖 4.13 主幹網路修復第三階段結果

50 4.3 總結 我們的 BANF 機制根據現實生活中感測節點的特性新增節點類型 : 具電節點, 在特定位置上擺放具電節點, 利用具電節點建立主幹網路, 讓一般節點能夠選擇較能延長運作時間的路徑將資料傳輸至協調者, 將整個網路拓樸建立起來 BANF 對於一些感測網路的應用可以增加感測網路的生命週期, 譬如在醫護站或是醫院, 在病床或病人身上裝上一般感測節點, 而在走道上擺放具電節點建構主幹網路, 使得病人的一些生理資訊可以透過走道上的具電節點回傳至護理站 ; 又如在戶外環境, 為了要觀測土石流或洪水等天災, 在觀測環境之中比較安全的位置或定期巡邏的點放置具電節點, 之後再佈署一般感測節點在觀測環境內, 使得感測節點能夠將環境中物理變化資訊回傳至防災中心

51 第五章模擬結果與討論 本章節主要介紹模擬架構以及模擬結果, 模擬架構將說明模擬環境 模擬參數 模 擬方案, 最後藉由各模擬結果所呈現的現象, 進行分析與討論可能的原因 5.1 模擬環境 為了驗證我們所提出來的方法, 我們利用 NS2[16] 網路模擬平台來模擬 BANF 的工 作效能, 首先第一個實驗為幾近相同的節點數量但不同的網路拓樸, 參數設定如表 5.1 表 5.1 實驗一模擬參數設定值 Parameter Value Network size 200M*200M Number of sensor nodes 98, 100 Number of power-nodes 4~19 Initial energy of sensor nodes Application traffic Packet size Packet interval 10 Joules CBR (Constant Bit Rate) 70 bytes 20 seconds 實驗一我們模擬在 200M*200M 的環境之中, 佈署 98 跟 100 個感測節點 ( 包含具電節點以及協調者 ), 每個感測節點會以週期 20 秒的頻率傳送資料給協調者, 資料封包傳送方式是使用 Constant Bit Rate(CBR) 資料流型式 一般感測節點的電量為 10 焦耳, 接收與傳送資料皆需要消耗能量, 當感測節點電量消耗完畢後即代表死亡, 而在死亡結點底下的節點會因為父節點或上游死亡導致資料無法送達致協調者, 因此我們也將這些資料無法送達致協調者的節點視為死亡, 並且統計出節點的平均運作時間 首先針對我們所提出的 BANF 與 ZigBee 節點平均運作時間的比較, 模擬不同的網路拓樸環境來證明 BANF 的確有延長節點平均運作時間的效果, 並且證明 BANF 對於何

52 種網路拓樸會有較佳的效果 實驗一模擬方案區分成五種不同的網路拓樸以及不同數量的具電節點個數來觀察感測網路的運作時間 :Case1 網路拓樸為 5x20, 有 4 個具電節點 Case2 網路拓樸為 7x14, 有 6 個具電節點 Case3 網路拓樸為 10x10, 有 9 個具電節點 Case4 網路拓樸為 14x7, 有 13 個具電節點 Case5 網路拓樸為 20x5, 有 19 個具電節點, 說明如表 5.2 所示 表 5.2 Case1 ~ Case5 條件表 Case Topology Conditions 1 5x20 Number of power-nodes = 4 2 7x14 Number of power-nodes = x10 Number of power-nodes = x7 Number of power-nodes = x5 Number of power-nodes = 19 表 5.3 實驗二模擬參數設定值 Parameter Value Network size 200M*200M Number of sensor nodes 50~190 Number of power-nodes 9 Initial energy of sensor nodes Application traffic Packet size Packet interval 10 Joules CBR (Constant Bit Rate) 70 bytes 20 seconds

53 而在實驗二的部份我們觀察以具電節點為樹根 (Root) 形成的子樹的深度對於節點的平均運作時間有何影響, 在 200M*200M 的環境之中散佈 50~190 個感測節點 ( 包含協調者 具電節點以及一般節點 ), 其中協調者與具電節點的電量皆沒有限制, 而一般節點的電量為 10 焦耳, 感測節點每 20 秒以 CBR 傳送資料封包給協調者, 模擬參數設定值如表 模擬結果與分析 對於實驗一的模擬結果我們主要觀察不同網路拓樸對節點平均運作時間的影響, 而實驗二則觀察具電節點樹深度對節點平均運作時間的影響 其中節點運作時間的定義為感測節點是否能將資料回傳給協調者, 當感測節點的父節點或上游死亡而造成資料無法送至協調者則將此節點視為死亡, 觀察感測節點 ( 不包含具電節點 ) 的死亡曲線圖並且計算出平均運作時間 ; 而具電節點樹深度的部份, 固定具電節點的個數, 變化以具電節點為樹根的感測節點深度, 觀察具電節點樹深度對於節點平均運作時間有何影響 網路拓樸之模擬結果 實驗一針對五種不同方案的網路拓樸來驗證 BANF 的效能, 每個感測節點距離 10 公尺, 而感測節點可傳輸距離為 13 公尺, 因此每個節點至多會有 4 個鄰居 Case1 為 5x20 的網路拓樸如圖 5.1(a) 所示, 編號為 0 的節點為協調者, 而編號 1~4 在 ZigBee 中為電量較多的節點在 BANF 中則為具電節點, 其他則為一般節點, 其中編號 三個節點可以直接與協調者連結 ;Case 2 為 7x14 的網路拓樸圖 5.1 (b) 如所示, 擺設基本原則與 Case1 相同, 編號 0 為協調者, 編號 1~6 在 ZigBee 中為電量較多的節點在 BANF 中為具電節點 ;Case3 為 10x10 的網路拓樸如圖 5.2 (a), 編號 0 為協調者, 編號 1~9 在 ZigBee 中為電量較多的節點在 BANF 中則為具電節點, 其他為一般節點 ; Case4 為 14x7 的網路拓樸如圖 5.2 (b), 編號 0 為協調者, 編號 1~19 為具電節點 ; Case5 為 20x5 的網路拓樸如圖 5.2(c), 編號 0 為協調者, 編號 1~19 為具電節點, 其他則為一般節點 在我們模擬的過程中, 協調者以及具電節點皆不會損壞且具有無窮盡的電量

54 圖 5.1 Case1 與 Case2 網路拓樸 圖 5.2 Case3~5 網路拓樸

55 圖 5.3 不同網路拓樸之節點平均運作時間我們觀察 Case1 ~ Case5 的平均節點 ( 不包含具電節點 ) 運作時間如圖 5.3 所示, X 軸為五種不同的網路拓樸,Y 軸為時間軸, 單位為秒, 可以從中看出 BANF 的效能的確比 ZigBee 要來得好, 節點平均運作時間比 ZigBee 延長了 193% 到 310%, 根據不同的網路拓樸環境的模擬結果可以得知感測節點數量固定時,BANF 對於狹長型的網路拓樸 (Skewed Topology) 擁有最佳的效能, 因為狹長型的網路拓樸中主幹網路比較長而且靠近協調者附近的一般節點比較少, 所以可以吸引比較多的一般節點的傳送路徑經過主幹網路傳往協調者, 也就能舒緩 Hot-spot 問題的影響延長整體感測網路的運作時間 以下則針對上述五種方案的節點平均運作時間做比較深入的探討 Case1 的模擬結果如圖 5.4,X 軸為時間, 單位為秒, 而 Y 軸為存活的一般節點個數, 具電節點個數為 4, 在先前有提到當感測節點的上游死亡的話那節點的資料便無法送達至協調者, 因此將死亡的節點以及它的下游皆視為死亡 而從關係圖可以看出 ZigBee 在 1500 秒的時候就開始有節點死亡而且死亡的曲線幅度很大, 大概在將近 4000 秒的時候一般感測節點就幾乎全死亡了, 節點感測到的資料無法正確地送回協調者 ; 而我們的 BANF 在將近 2500 秒時才開始有節點死亡, 而且由圖可知之後一般節點死亡的速度也比較緩和, 大概在 5300 秒時一般節點才幾乎都死光,BANF 整體的一般節點死亡速度比 ZigBee 要來得緩和, 因此具有較佳的系統運作時間

56 圖 5.4 Case1 節點存活時間之關係圖 圖 5.5 Case2 節點存活時間之關係圖

57 圖 5.6 Case3 節點存活時間之關係圖 圖 5.5 為 Case2 的模擬結果, 圖中虛線為 ZigBee, 實線為 BANF, 具電節點個數為 7, 從圖可以發現 ZigBee 在將近 1500 秒的時候就開始有一般節點死亡, 而在 2800 秒後一般節點就幾乎全死光了 ; 而 BANF 大約在 2400 秒時開始有一般節點死亡, 之後隨著時間具電節點旁的一般節點逐一死亡, 和 ZigBee 相對照可以發現節點死亡的曲線比 ZigBee 要來得趨緩很多, 在 8000 秒的時候還有一般節點存活, 因此可以發現我們的 BANF 確實延長了系統的運作時間 圖 5.6 為 Case3 的模擬結果, 圖中虛線為 ZigBee, 實線為 BANF, 具電節點個數為 9, 從圖可以發現 ZigBee 在將近 1500 秒的時候就開始有一般節點死亡, 而在 2400 秒時一般節點就幾乎全死光了 ; 而 BANF 大約在 2200 秒時開始有一般節點死亡, 之後隨著時間具電節點旁的一般節點逐一死亡, 和 ZigBee 相對照可以發現節點死亡的曲線比 ZigBee 來得趨緩許多, 甚至在 秒的時候還有一般節點存活, 因此可以發現我們的 BANF 確實延長了系統的運作時間

58 圖 5.7 Case4 節點存活時間之關係圖 Case4 的模擬結果如圖 5.7, 圖中虛線為 ZigBee, 實線為 BANF, 有 13 個具電節點, 可以從圖得知 ZigBee 在大概 1700 秒的時候就開始有一般節點死亡並且急速下降, 而且在將近 3000 秒時一般節點就全部死光 ; 而我們的 BANF 大約在 2000 秒時才開始有一般節點死亡, 之後節點死亡的曲線非常緩和, 並且在 秒時仍然有一般節點存活, 可以看出 BANF 相較於 ZigBee 有很明確地緩和了一般節點死亡的時間, 使得系統可以有更長的運作時間, 節點死亡的順序就由最靠近協調者與具電節點旁的一般節點開始至離協調者最遠的具電節點旁的一般節點, 而由於 Case4 有 13 個具電節點, 因此使得 BANF 的曲線有比較緩和的情況 Case5 的模擬結果如圖 5.8, 圖中虛線為 ZigBee, 實線為 BANF, 有 19 個具電節點, 可以從圖得知 ZigBee 在大概 2100 秒的時候就開始有一般節點死亡並且急速下降, 而且在將近 2300 秒時一般節點就幾乎全部死光 ; 而我們的 BANF 大約在 2300 秒時才開始有一般節點死亡, 之後節點死亡的曲線非常地緩和, 並且在 秒時仍然有一般節點存活, 可以看出 BANF 相較於 ZigBee 有很明確地緩和了一般節點死亡的時間, 使得系統有更長的運作時間, 節點死亡的順序就由最靠近協調者與具電節點旁的一般節點開始至離協調者最遠的具電節點旁的一般節點, 而由於 Case5 有 19 個具電節點, 因此使得 BANF 的曲線有非常緩和的情況

59 圖 5.8 Case5 節點存活時間之關係圖 具電節點樹深度的影響之模擬結果 實驗二我們觀察以具電節點為樹根 (Root) 形成的子樹的深度對於節點運作時間有何影響, 而模擬的拓樸範例如圖 5.9 所示, 圖中編號 0 為協調者 (Coordinator), 編號 1 到編號 9 為具電節點, 其他皆為一般節點, 圖 5.9(a) 為以具電節點為樹根,BANF 中具電節點的深度是 1, 所長出來的樹深度最高為 3, 因此我們將此稱為具電節點樹深度為 3 的網路拓樸 ; 而圖 5.9(b) 則為深度為 5 的具電節點樹 我們模擬深度 3 到深度 10 這八種情況, 觀察具電節點樹深度對於節點平均運作時間會有怎樣的影響 模擬結果如圖 5.10 所示, 具電節點數量為 9, 利用 NS2 模擬在 ZigBee 以及 BANF 的運作情況, 如同前一個模擬實驗, 在 BANF 中的具電節點在 ZigBee 中只是擁有無限電量的感測節點 圖 5.10 的 X 軸為具電節點樹的深度,Y 軸為時間, 單位為秒, 代表的是扣除具電節點後剩餘的那些一般節點的平均運作時間, 我們可以從實驗結果發現兩個結果, 第一個為我們的 BANF 與 ZigBee 相比總是有比較長的節點平均運作時間, 而且延長時間的倍率大約都在 258%; 第二個為隨著具電節點樹的深度越高對 BANF 而言會使得節點平均運作時間隨之慢慢遞減, 因此可以知道具電節點樹深度越高會縮短節點運作時間, 所以我們可以在環境中針對具電節點樹深度較高的區域擺放多一些具電節點

60 降低具電節點樹的深度來延長節點運作時間, 更加發揮 BANF 延長節點運作時間的目的 圖 5.9 Depth of power-node based subtree: 3 and 5 圖 5.10 不同具電節點樹深度的節點平均運作時間關係圖

61 第六章結論與未來工作 6.1 結論 由於無線感測網路的應用潛力無窮, 目前在軍事 環境 健康 家庭等各領域的應用上都已經可以發現它的存在, 因此未來各種新穎的應用環境以及想法都可能會使得無線感測網路的設計產生影響, 不過感測節點能量的問題與運作效能的研究仍然會是無線感測網路重要的研究議題 我們提供了一個主幹感知的網路形成機制 (Backbone-Aware Network Formation,BANF) 應用於無線感測網路上, 利用現實生活中節點電量不同的特性定義具電節點 (Power-node), 在特定位置擺放具電節點建立起主幹 (Backbone) 網路, 使得感測節點先將資料傳往主幹再送達協調者, 感測節點不需經過複雜的程序或演算法就可以選擇到一條運作時間較長的繞送路徑將資料傳送給協調者, 而 BANF 的確延長了節點的平均運作時間, 減緩 Hot-spot 問題所造成的影響 並且從模擬的結果可得,BANF 相對於 ZigBee, 在不同網路拓樸下延長了 193% 至 310% 的節點平均運作時間 6.2 未來工作 由於具電節點是我們新定義的節點, 而且對於 BANF 而言是形成主幹網路的重要角色, 因此當具電節點損壞時的容錯機制就相當重要, 而在本論文所提出的方法只是其中幾種可行的做法, 還有更多不同的角度以及更有效率的做法值得研究與探討, 因此具電節點容錯機制的完整性是未來需要完成的目標 另外在本論文中的 BANF 是使用可繞送識別碼來實現, 所以當節點移動時需要更換識別碼, 因此會有移動性 (Mobility) 的問題存在, 或許將來可以使用支援移動性的繞送機制來達成 BANF 最後,BANF 的精神是將熱點分散至具電節點周圍的多個感測節點上, 若希望再多延長節點的運作時間, 則具電節點底下的感測節點可以做負載平衡 (Load balancing), 更加地分散熱點問題所造成的影響, 增加感測節點電量的使用效率

62 Reference [1] Akyildiz, I.F.; Weilian Su; Sankarasubramaniam, Y.; Cayirci, E., A survey on sensor networks, Communications Magazine, IEEE, vol.40, no.8, pp , Aug 2002 [2] C. Perkins, Ad Hoc Networks, Addison-Wesley, Reading, MA, 2000 [3] H. Karl; A. Willig, Protocols and Architectures for Wireless Sensor Networks, Wiley 2005 [4] Heinzelman, W.R.; Chandrakasan, A.; Balakrishnan, H., Energy-efficient communication protocol for wireless microsensor networks, System Sciences, Proceedings of the 33rd Annual Hawaii International Conference on, vol., no., pp. 10 pp. vol.2-, 4-7 Jan [5] Matthias Handy; Marc Haase; Dirk Timmermann, LEACH-C:Low Energy Adaptive Clustering Hierarchy with Deterministic Cluster-head Selection, Mobile and Wireless Communications Network, th International Workshop on, 9-11 Sept. 2002, pp [6] Lindsey, S.; Raghavendra, C.; Sivalingam, K.M., Data gathering algorithms in sensor networks using energy metrics, Parallel and Distributed Systems, IEEE Transactions on, vol.13, no.9, pp , Sep 2002 [7] Lindsey, S.; Raghavendra, C.S., PEGASIS: Power-efficient gathering in sensor information systems, Aerospace Conference Proceedings, IEEE, vol.3, no., pp vol.3, 2002 [8] Kemei Du; Jie Wu; Dan Zhou, Chain-based protocols for data broadcasting and gathering in the sensor networks, Parallel and Distributed Processing Symposium, Proceedings. International, vol., no., pp. 8 pp.-, April 2003 [9] Y. Ma; S. Dalal; M. Alwan; J. Aylor, Rop: A Resource Oriented Protocol for Heterogeneous Sensor Networks, Proc. 13th VT/MPRG Symp. Wireless Personal Comm., pp , June 2003 [10] Yong Ma; Aylor, J.H., System lifetime optimization for heterogeneous sensor networks with a hub-spoke technology, Mobile Computing, IEEE Transactions on, vol.3, no.3, pp , July-Aug [11] Soro, S.; Heinzelman, W.B., Prolonging the lifetime of wireless sensor networks via unequal clustering, Parallel and Distributed Processing Symposium, Proceedings. 19th IEEE International, vol., no., pp. 8 pp.-, 4-8 April 2005 [12] Wei Ye; Heidemann, J.; Estrin, D., An energy-efficient MAC protocol for wireless sensor networks, INFOCOM Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, vol.3, no., pp vol.3,

63 [13] Viswanathan, A.; Boult, T.E., Power Conservation in ZigBee Networks using Temporal Control, Wireless Pervasive Computing, ISWPC '07. 2nd International Symposium on, vol., no., pp.-, 5-7 Feb [14] Qiangfeng Jiang; Manivannan, D., Routing protocols for sensor networks, Consumer Communications and Networking Conference, CCNC First IEEE, vol., no., pp , 5-8 Jan [15] ZigBee Standards Organization, ZigBee Document r06, Version 1.0, December 14, 2004 [16] The Network Simulator ns2, [17] Z-Wave Alliance,