[[alternative]]Designing a hierarchy-based routing protocol for wireless sensor networks

碩士[[abstract]]我們在本篇論文提出一個透過多躍距收集資料的路由協定—BHAR(Bidirectional Hierarchy-based Anycast Routing)，和HAR做比較，BHAR加快了建構階層式路由樹及修復路由的速度，並改善其運作機制。在BHAR中，匯集節點及來源節點皆能建立階層式路由樹，各個節點僅需依靠對其自身的親節點及鄰居節點的認識加入路由樹；來源節點所建立的路由樹可藉由與其它相鄰路由樹的路由交換，學到至遠端匯集節點的路由，並透過中繼路由樹節點將資料送達最近的匯集節點；在不依靠位置資訊、不需遠端控制的情況下執行路由修復，同時做局部網路的最佳化調整，以避免定期及條件式重建網路拓樸對網路及資料傳輸所造成的衝擊，並改善HAR在路由修復上修復彈性較差及仍有可能發生迴圈的缺點。我們使用VC++對BHAR與HAR做效能比較，從模擬結果來看，BHAR在匯集節點與來源節點數目增加時，可減少一般節點加入路由樹的平均等待時間；總節點數及網路大小的增加對BHAR的效能衝擊也相對小很多；BHAR的可擴充性(scalable)也比HAR大許多；在修復路由的能力上，BHAR比HAR能容忍更多的節點故障，並維持有效的路由運作，大幅提高了網路的強健性(Robustness)；在節點因各種因素導致分佈不平均的情況下，BHAR在路由修復的能力上比HAR優秀甚多。[[abstract]]In this paper, we present Bidirectional Hierarchy-based Anycast Routing (BHAR), a routing protocol for collecting data over multi-hop. In comparative to HAR, BHAR speeds up and improve the mechanism to construct hierarchical trees and to repair the route. In BHAR, sinks and sources can initial to construct a hierarchical tree. By knowing only its own parent and neighbor, each node in BHAR can join a tree; a tree can learn the routes to a remote sink by exchanging its routes with its neighboring trees, and send data to the nearest sink by intermediate trees; each node can perform route repair without geographical information or being controlled remotely, and perform local network topology optimization simultaneously in order to prevent the impact to the network and to data communication by periodically and conditionally network reconstruction. We evaluate the performance of BHAR by using VC++ and comparing with those of HAR. The simulation results demonstrate that the average waiting time for a node to join a tree decrease when the number of sinks and sources increase in BHAR. The impact of the increase of the node number and network size to the performance of BHAR is relatively small, which means the scalability is much better. BHAR can endure more nodes to be failed and maintain effective routing operation, which has improve the robustness of BHAR. BHAR achieves much higher performance on route repair in the situation of the unevenly distribution due to different factors.[[tableofcontents]]目錄 第一章 緒論 1 1.1 研究背景 1 1.2 研究動機 1 1.3 研究目的及方法 3 1.4 論文架構 4 第二章 無線網路路由協定 6 2.1 無線感測網路簡介 6 2.2 RUMOR ROUTING 12 2.3 PEGASIS 15 2.4 MCFA 17 2.5 DD 18 2.6 SPIN 20 2.7 EDDD 22 2.8 LEACH 25 2.9 LLC 26 2.10 MECH 28 2.11 PCBRP & PCBRP-OPT 28 2.12 EDGE & HAR 31 2.13 HMRP 34 2.14 運作機制比較 36 第三章 新提出的路由協定 42 3.1 設計目標及假設前提 42 3.2 運作機制說明 44 3.2.1 建立網路拓樸 44 3.2.2 路由修復機制 53 3.3 新路由協定的運作特點 57 第四章 模擬與評比 63 4.1 模擬方式 63 4.2 效能指標 63 4.3 總節點數的影響 65 4.4 網路大小的影響 68 4.5 匯集節點密度的影響 81 4.6 反常態分佈對模擬結果的影響 82 4.7 控制封包產生數評比 92 第五章 結論 99 參考文獻 104 圖目錄 圖2.1：無線網路路由協定分類 7 圖2.2：使用與未使用叢集架構與聚集轉送資料 10 圖2.3：ROUMOR ROUTING運作機制說明 14 圖2.4：PEGASIS使用GREEDY演算法形成鍊結架構 16 圖2.5：MCFA以倒數計時法建立最佳成本域圖示範例 18 圖2.6：圖解DD於不同時態的擴散 20 圖2.7：SPIN的點對點資料傳送機制 21 圖2.8：EDDD以RT及BE過濾器劃分的封包傳送路徑組 25 圖2.9：LEACH每回合的時間線示意圖 26 圖2.10：PCBRP藉由連結方式來認定節點狀態 30 圖2.11：PCBRP-OPT在叢集內使用單播路由請求封包以減少廣播封包 31 圖2.12: HAR狀態轉換示意圖 34 圖2.13：由HAR建立的階層式路由樹 35 圖2.14：HMRP階層建構結果 36 圖3.1：由匯集節點及來源節點發出路由探索封包，開始路由樹的建立 45 圖 3.2：可與不同路由樹節點通訊的節點彼此交換路由 47 圖 3.3：路由樹成員節點會將所接收到至其它路由樹根節點的路由向親節點彙總 48 圖3.4：來源節點依路由表資訊向另一個來源節點更新至匯集節點的路由資訊 48 圖 3.5：根節點可得到自下游或鄰接節點所彙總至其它根節點的路由資訊 49 圖3.6：來源節點透過路由表的查詢將資料逐躍距傳送至匯集節點 50 圖3.7：當節點的路由表單容量較小，會優先儲存至各個根節點較短的路由 52 圖3.8：節點故障發生後，鄰接節點會向路由表單中可至各路由樹根節點的下一躍距節點更新資訊 53 圖3.9：節點故障發生時，其子節點會藉由路由表單尋找適合的親節點候選者 55 圖3.10：若故障節點的子節點找不到合適的親節點候選者，則其與其下遊子節點會解除彼此間從屬關係，並各自尋找新的親節點 57 圖3.11：節點接受到路由探索封包時的運作機制流程圖 61 圖3.12：節點發現鄰接節點故障時的節點運作流程圖 61 圖3.13：節點接收到路由修正資訊時的節點運作流程圖 62 圖3.14：節點接收到親節點探索封包時的節點運作流程圖 62 圖4.1：不同總節點數的平均等待時間比較 67 圖4.2：不同總節點數的平均路徑長度比較 70 圖4.3：不同總節點數的網路強健度比較 72 圖4.4：不同網路大小的平均等待時間比較 76 圖4.5：不同網路大小的平均路徑長度比較 78 圖4.6：不同網路大小的網路強健度比較 80 圖4.7：不同匯集節點密度的平均等待時間比較 84 圖4.8：不同匯集節點密度的平均路徑長度比較 86 圖4.9：不同匯集節點密度的網路強健度比較 88 圖4.10：路由協定在節點反常態分佈時的平均等待時間 91 圖4.11：路由協定在節點反常態分佈時的平均路徑長度 91 圖4.12：路由協定在節點反常態分佈時的網路強健度 92 圖4.13：在網路大小不同時建構網路拓樸的節點平均接收控制封包數 95 圖4.14：建構網路拓樸時BHAR與HAR的節點平均接收控制封包比率 98 表目錄 表2.1：各類型路由協定運作機制比較 38 表3.1：感測器節點中的路由表項目格式 45 表4.1：總節點數影響評估的模擬環境參數 65 表4.2：網路大小影響評估的模擬環境參數 73 表4.3：匯集節點密度影響評估的模擬環境參數 81 表4.4：反常態分佈影響評估的模擬環境參數 90 表4.5：控制封包產生數評估的模擬環境參數 93 表5.1：BHAR運作機制 101 表5.2：BHAR與HAR優劣比較 102[[note]]學號: 793350108, 學年度: 9