<4D F736F F D20B0F2A9F3AFD3AFE0A7A1A4C6AABAB54CBD75B750B4FABAF4B8F4B0CABA41B44DAE7CAA6B>

Size: px

Start display at page:

Download "<4D F736F F D20B0F2A9F3AFD3AFE0A7A1A4C6AABAB54CBD75B750B4FABAF4B8F4B0CABA41B44DAE7CAA6B>"

聘质东方
4 years ago
Views:

1 基於耗能均化的無線感測網路動態尋徑法呂柏宏陳怡婷戴榆庭廖斌毅洪盟峰國立高雄應用科技大學電子工程系摘要本研究提出均化節點耗能的概念, 提升無線感測網路的使用壽命藉由找尋拓樸中平均剩餘能量較高且跳數較少的路徑, 以及設置門檻值來做為切換路徑的標準, 使得重新路由搜尋, 以避免過度使用造成部分節點能量耗盡藉由上述方法來均化拓樸中節點的能量, 達到延長網路壽命的目的本研究利用 NS2 來進行驗證, 經由不同網路規模節點佈放密度以及不同長短路徑的應用情境驗證, 結果顯示所提出的方法與傳統 AODV 路由方法相較之下, 可在保有原來的網路服務品質的前提下延長的網路壽命而在高密度佈放時具有較佳的效益, 在最佳的情形下可延長近 33% 的網路使用壽命與過去的方法比較, 本研究所提方法具有良好特性且對於長效無線網路技術有顯著的貢獻關鍵字 : 耗能均化無線感測網路網路壽命 AODV Abstract In this paper, a dynamic AODV based on equalization of residual energy (D-AODVRE) is considered to improve AODV routing protocols. In this proposed method, the nodes with higher residual energy and less hops are selected to establish a transmission route. By this way, the required energy consumption is equalized by all nodes in a network to prolong the network lifetime. Moreover, many scenarios with various network scales and node densities are utilized to validate the efficiency of D- AODVRE. NS2 is used to implement D-AODVRE. And, the simulated results show that the network lifetime of D-AODVRE is prolonged about 33% compared with AODV in high-density deployment. Keywords: equalization of residual energy, wireless sensor network, network lifetime, AODV 1. 前言隨著無線通訊技術嵌入式處理器以及電池技術的進步下促使無線感測網路 [1] 的發展更加快速化, 且佈設成本也漸漸獲得有效的縮減, 功能也越來越強, 而在眾多的感測器所建構出的網路上, 不僅涵蓋了大面積的資料蒐集數據監控自主運算以及傳輸等現代化技術, 其應用上也日漸蓬勃發展, 據 Markets and Markets 調研機構預測, 全球智慧型感測市場, 到 2020 年底, 將高達億美元, 並以 36.25% 的 CAGR( 複合年均增長率 ) 成長 [2] 在無線感測網路中, 本研究以探討感測節點能量之消耗為主, 因為在無線感測網路中, 感測節點通常會佈建於人類不易到達的區域, 感測節點會因能量的消耗而失去偵測資料的能力, 並且可能導致整個網路所收集回來的資訊不完整 [3], 因此如何減少感測節點能量之消耗延長網路壽命並且同時兼顧網路服務品質, 是值得加以探討與研究的議題為了改善網路壽命, 本研究所提出的方法藉由目的端挑選剩餘能量較高且跳數相對較少的路徑來做為傳輸路徑, 避免過度使用單一路徑造成拓樸中某些節點能量耗盡也同時在節點中設置門檻值來做為切換路徑的標準, 當節點能量低於門檻值就重新搜尋路徑藉由這兩個機制來達成能量均化的功能, 並且達到延長網路壽命的目的本文架構分為五節, 在第一節說明本研究

2 的研究背景動機以及目的, 第二節說明 AODV 協定的服務情境描述並且提出缺點以及國內外相關研究分析, 第三節說明本研究改善的方法, 第四節針對本研究所提出的方法做模擬驗證以及成果分析, 最後為本文的結論 2. 相關文獻無線隨意按需路由協定 (Ad hoc On-Demand Distance Vector Routing,AODV) 的優點在於節點不需要維護拓樸中所有的路由資訊, 這對於無線感測網路中感測器能量有限的條件是有利的而 AODV 主要是由兩個機制組成當節點欲傳送資料前會先檢查自身路由資訊, 沒有相關路由資訊則開啟 Route discovery, 並且發送 RREQ(Route Request) 封包 ; 經由目的節點確認後開啟 RREP(Route Reply) 回覆來源節點路由資訊以及在資料傳送失敗時開啟 Route maintain, 發送重新修復路徑所需的 RERR(Route Error)[4] 而在 AODV 路由協定中同時存在著一些缺點, 例如 AODV 在搜尋路徑時, 目的節點只要收到第一筆 RREQ 的廣播封包時, 馬上就會回覆 RREP 訊息但這樣的機制並不會去考慮路徑的長短以及中繼節點的剩餘能量因此許多在路徑的切換進行相關研究, 例如 Radhika D. Joshi 等人 [5] 改進 AODV 路由協定, 提出一個 AODVM (AODV Modified), 此路由協定主要是新增封包欄位來記錄最小能量, 利用最小能量以及跳數比值所得出的數, 挑選出最佳路徑 Mounir FRIKHA 等人 [6] 為了有效地減少中繼節點的能量消耗, 提出一個 ECB-AODV (Energy Constraint protocol Based on AODV) 路由協定, 此路由協定在中繼節點接收到 RREQ 時, 除了判斷是否收到相同的封包, 也同時判斷自身剩餘能量是否大於預設門檻值, 如果大於預設門檻值時, 則繼續轉發到下一個中繼節點進行判斷, 如果小於預設門檻值時, 則丟棄 RREQ 封包另外在傳送資料時, 每個中繼節點去判斷自身剩餘能量是否小於預設門檻值, 如果某個中繼節點的剩餘能量小於預設門檻值時則刪除自身的路由表並發送 RERR 至來源節點, 重新進行路由發現程序, 來達到均化節點能量消耗的效果 3. 剩餘能量均化動態 AODV 尋徑 (D- AODVRE) 設計為了改善 AODV 過度使用相同路徑的缺陷, 因此本研究提出一個透過目的端挑選條件較好路徑當作傳輸徑的剩餘能量均化動態 AODV 尋徑法此方法在無線感測網路靜態拓樸中, 在目的端挑選平均剩餘能量較高且跳數 (Hop) 少的路徑, 來降低同一條路徑重複被使用的問題, 藉此均化中繼節點的能量而在傳輸資料越長時, 很容易讓路徑上的中繼節點能量快速的耗盡, 所以為了改善此問題, 因此在演算法中多增加一個路由更新機制, 達到能量均化的效果, 接下來將說明如何改良 AODV 路由協定來達成本研究目標 3.1 廣播封包格式設計本研究在 RREQ 廣播封包格式新增名為 Total_energy 的 32bit 欄位, 單位焦耳 (J), 如圖 1 所示, 在廣播 RREQ 封包時, 用來存放來源節點到目前節點間的傳輸路徑上, 每個節點剩餘能量數值的總和, 主要是讓目的節點用來選擇合適節能且符合所預期服務品質的傳輸路徑, 另外也利用保留欄位 (Reserved) 存放初始能量門檻值 (B), 主要是讓各中繼節點更新路由表時, 將 B 存放在自身路由表裡,B 主要是在傳送資料時與各個中繼節點的剩餘能量比較, 判斷是否需要切換路徑圖 1. D-AODVRE 中 RREQ 封包格式

3 3.2 D-AODVRE 工作流程設計工作流程設計來源節點工作流程設計主要參照傳統 AODV 路由協定, 如圖 2 所示, 首先來源節點會先準備發送 RREQ 廣播封包, 在來檢查來源節點自身的路由表是否有到達目的節點的路徑, 若沒有則將初始能量門檻值 (B) 放入 RREQ 廣播封包裡的保留欄位 (Reserved), 然後開始發送 RREQ, 並且設定等待時間, 等待 RREP 回覆封包, 如果等待時間超時, 則來源節點重新發送 RREQ 廣播封包中繼節點部分, 如圖 3, 首先判斷自身節點是否為目的節點, 如果是目的節點則挑選平均能量高且跳數少的路徑, 如果不是目的節點則檢查自身路由表是否收到相同的 <Source address, Broadcast ID>, 檢查完之後中繼節點進行路由表更新, 在將自身的剩餘能量累加至 RREQ 封包的 Total_energy 欄位裡再轉送 RREQ 封包但是當傳送資料時間越長很容易讓路徑上的中繼節點能量快速耗盡, 為了解決這問題, 在本研究所提出的方法多增加一個路由更新的機制, 如圖 4, 路徑上各節點會將自身剩餘能量與自身路由表裡的初始能量門檻值 (B) 進行比較, 如果路徑上各節點的剩餘能量小於 B, 則刪除路徑上小於 B 的節點路由表, 在將 B 除以 2, 並發送 RERR 封包至來源節點, 讓來源節點重新搜尋路徑圖 3. D-AODVRE 中繼節點工作工作流程圖 NO 開始中繼節點接收封包傳輸路徑上各中繼節點剩餘能量 < 初始能量門檻 (B) YES 初始能量門檻 (B)= 初始能量門檻 (B)/2 刪除路由表, 發送 RERR 至來源端結束圖 4. D-AODVRE 中繼節點路由更新工作工作流程圖而在目的端節點部分並不會檢查是否收到相同的 <Source address, Broadcast ID>, 而是去收集各條路徑剩餘能量做進一步的計算而目的節點的部分主要是去計算每一條路徑的平均剩餘能量與判斷跳數 (Hop) 是否為最少的, 其平均剩餘能量的計算公式為 : (1) 圖 2. D-AODVRE 來源端節點節點工作工作流程圖 : 前路徑節點的索引 (2)

4 能量 : 每條路徑剩餘能量加總 : 每條路徑所經過的節點個數 : 節點 i 剩餘能量 : 計算路徑的平均剩餘為了避免目的節點收集過多 RREQ 廣播封包而造成延遲太久的情況發生, 在目的節點部分設置時間門檻 (A), 如圖 5, 當等待時間大於 A 時, 則目的節點停止接收 RREQ 廣播封包, 之後目的節點可以根據以上公式 (2) 來計算平均剩餘能量, 並挑選出來平均能量高且跳數少的路徑回傳 RREP 封包至來源節點而 RREQ 3 路徑的平均剩餘能量雖然大於 RREQ 1 路徑與 RREQ 2 路徑, 但是 RREQ 3 路徑的跳數 (Hop) 仍大於 RREQ 1 路徑與 RREQ 2 路徑, 所以目的節點 D 將會選擇 RREQ 2 路徑來做資料傳輸以上可以看出使用 D-AODVRE 的差異, 不僅可以挑選跳數少的路徑防止周圍的鄰近節點減少收到資料訊框與回覆訊框, 也可以挑選平均能量高的路徑降低傳送路徑快速中斷之問題開始 NO 目的節點接收 RREQ 封包儲存每條路徑 Total_energy, 儲存每條路徑路徑長度, 紀錄接收 RREQ 次數等待時間 > 時間門檻值 (A) YES 利用公式 (3) 計算每條路徑平均剩餘能量儲存平均剩餘能量高且跳數 (Hop) 為最少的路徑 i > 接收 RREQ 次數將挑選平均剩餘能量高且挑數 (Hop) 為最少的路徑, 回傳 RREP 封包至來源節點結束 YES 圖 5. D-AODVRE 目的節點工作工作流程圖 3.3 D-AODVRE 路由選擇方式路由選擇方式 NO i ++ 接下來介紹 D-AODVRE 如何選擇路由, 如圖 6 所示假設目的節點會陸續接收到來源節點 S 到目的節點 D 的三條路徑, 路徑的相關數值如下 :RREQ 1 路徑 (a-b-c-d) 有 5 個跳數 (Hop) 而平均剩餘能量則為 60J;RREQ 2 路徑 (e-f-g-h) 有 5 個跳數而平均剩餘能量則為 77.5J;RREQ 3 路徑 (i-j-k-l-m) 有 6 個跳數而平均剩餘能量則為 80 J 在修改後的演算法中, 目的節點將會選擇 RREQ 2 路徑來做資料的傳輸, 因為 RREQ 1 路徑雖然跳數 (Hop) 與 RREQ 2 路徑相同但是平均剩餘能量小於 RREQ 2 路徑的平均剩餘能量, 4. 模擬結果分析圖 6. 選擇資料傳輸路由舉例本模擬平台為 NS2(Network Simulator 2), 利用模擬器設置模擬情境 ( 包括剩餘能量的比較初始門檻值設置的差異以及網路品質的比較 ), 並且透過模擬數據來表現出傳統 AODV 以及本研究所提出方法的差異以及效能 4.1 D-AODVRE 與 AODV 剩餘能量分析本模擬環境在 800 公尺 x 800 公尺的區域隨機佈放固定的感測節點, 此網路傳送封包大小 1000bytes, 且固定資料傳輸速率為 1Mbps, 每個感測節點起始能量 20 焦耳 (J), 時間門檻 (A): 0.1 秒, 初始能量門檻 (B): 10 焦耳 (J), 傳輸消耗功率 : 瓦, 接收消耗功率 : 瓦, 使用的資料流 Constant bit rate (CBR), 模擬時間 800 秒此模擬情境在不同的節點個數模擬中, 為了便於觀察, 所以在每 100 秒時擷取一次剩餘能量, 並且將本研究所提出的方法以及傳統 AODV 做比較

在圖 7 中, 本研究所提的方法並沒有明顯的改善, 其原因在節點個數少的情況下, 所選擇出的路徑與 AODV 較無差異, 雖然在模擬情境中, 路徑有做切換, 但是所使用的節點數量依然相同, 另外,D-AODVRE 在挑選路徑時, 條件為平均能量高且跳數較少的路徑, 所以在感測節點密度少的情況下, 挑選重複的路徑機率較高, 使得 D-AODVRE 無法達到能量均化的作用而在圖 8 至圖 10

5 在圖 7 中, 本研究所提的方法並沒有明顯的改善, 其原因在節點個數少的情況下, 所選擇出的路徑與 AODV 較無差異, 雖然在模擬情境中, 路徑有做切換, 但是所使用的節點數量依然相同, 另外,D-AODVRE 在挑選路徑時, 條件為平均能量高且跳數較少的路徑, 所以在感測節點密度少的情況下, 挑選重複的路徑機率較高, 使得 D-AODVRE 無法達到能量均化的作用而在圖 8 至圖 10 中, 可看出 D-AODVRE 的平均剩餘能量高於 AODV 的平均剩餘能量, 其原因在節點個數多的情況下,D-AODVRE 所挑選出的路徑長度都較 AODC 來的短, 使得周圍節點減少接收資訊以及回覆所帶來的能量消耗, 而在 80 個感測節點中,D-AODVRE 平均剩餘能量與 AODV 平均剩餘能量相比, 使用 D-AODVRE 可延長 34% 網路壽命 ; 在 120 個感測節點可延長 23% 網路壽命 ; 在 160 個感測節點, 可延長 13% 網路壽命圖個節點 D-AODERE 與 AODV 比較圖個節點 D-AODERE 與 AODV 比較將路由表的資訊做刪除, 導致來源端重新搜尋路徑, 所以以下在初始門檻值的設定上做了一個測試, 是利用 160 個感測節點使用 D-AODVRE, 模擬不同的初始能量門檻值 (B): 焦耳 (J), 來觀察使用不同的 B 來比較傳送資料量是否完整, 其模擬時間為 1450 秒圖個節點 D-AODERE 與 AODV 比較圖 11. 初始能量門檻 (B) 傳送資料量關係關係圖圖個節點 D-AODERE 與 AODV 比較 4.2 不同初始門檻值設置結果在文中所提到的初始門檻值的設置, 其影響在於路徑上的節點剩餘能量低於門檻值時, 會模擬出的結果, 如圖 11 所示, 可看出在使用初始能量門檻 (B): (J), 來源節點可以完整傳送筆資料量而初始能量門檻為 17(J) 時, 來源節點傳送筆資料量, 少傳送筆資料量 ; 使用 18(J) 時, 來源節點傳送筆資料量, 少傳送 6041 筆資料量其原因在初始能量門檻為 : (J) 時,

6 切換路徑的次數為 4 次, 其路徑長度平均介於 2~3 個跳數而初始能量門檻為 17 18(J) 時, 切換路徑的次數為 6 次, 其路徑長度平均介於 2~4 個跳數, 使得來源節點多接收到不必要的資料訊框與回覆訊框, 造成來源節點能量快速耗盡, 導致無法繼續傳送資料所以本研究所使用 D- AODVRE 所設定的 B 值大概平均介於感測節點初始能量的 80% 以下, 可以確保來源節點傳送的資料量完整 4.3 D-AODVRE 與 AODV 網路品質比較此模擬利用 D-AODVRE 與 AODV 進行網路品質比較, 比較個節點的平均點到點延遲時間, 如圖 12 所示, 在 40 個感測節點使用 D-AODVRE 一開始所搜尋到的路徑長度與 AODV 的路徑長度相同, 使得在傳輸資料時平均延遲時間與 AODV 相同, 其他的個感測節點使用 D-AODVRE 所挑選出來的路徑都是跳數少的路徑, 使得傳送資料的時間並不會延遲太長, 所以改善無線感測網路的能量消耗, 平均點到點延遲時間並不會受到太大的影響資料訊框與回覆訊框, 而造成節點消耗不必要的能量成本另外為了防止傳輸路徑上的中繼節點能量過度消耗, 在中繼節點上設定門檻值的判斷, 檢查是否需要切換路徑, 藉此達到能量均化的效果, 在模擬以及資料分析中, 使用 D-AODVRE 在高密度靜態無線感測網路裡, 在不影響網路品質的情況下, 可延長無線感測節點的壽命誌謝感謝科技部專題研究計畫 MOST E 補助, 使本研究可以順利進行參考文獻 [1] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, E. Cayirci, Wireless sensor network: a survey, Computer Networks, vol. 38, pp , [2] WSN 無線感測網路市場趨勢 DIGITIMES 企劃, 取自 : d=4&id= _8xe7wa947p48522wl6pyn&n =1 [3] E. J. Duarte-Melo and M. Liu. Analysis of energy consumption and lifetime of heterogeneous wireless sensor networks, Proc. Global Telecommunication Conference, pp , Nov [4] C. E. Perkins; Royer; S. Das, Ad Hoc On-Demand Distance Vector (AODV) Routing, Internet-Draft, IETF RFC3561, Mar 結論圖 12. 平均點到點延遲時間比較圖在此篇論文中, 本研究提出了一種剩餘能量均化來動態調整 AODV 尋徑的方法 (Dynamic AODV Routing Based on Residual Energy, D- AODVRE) 來均化感測節點能量消耗並藉此延長網路壽命, 該路由方式是在靜態無線感測網路裡找尋平均能量高且跳數少的路徑, 是為了防止路徑在傳送資料時, 周邊的鄰近節點收到過多的 [5] Radhika D. Joshi & Priti P.Rege, "Energy Aware Routing in Ad Hoc Networks", 6th WSEAS International Conference on CIRCUITS, Dec [6] Mounir FRIKHA, Fatma GHANDOUR, Implementation and Performance Evaluation of An Energy Constraint Routing Protocol for Mobile Ad Hoc Networks, Proc. of The Third Advanced International Conference on Telecommunications, pp.13-19, May

Microsoft PowerPoint - Aqua-Sim.pptx

Microsoft PowerPoint - Aqua-Sim.pptx Peng Xie, Zhong Zhou, Zheng Peng, Hai Yan, Tiansi Hu, Jun-Hong Cui, Zhijie Shi, Yunsi Fei, Shengli Zhou Underwater Sensor Network Lab 1 Outline Motivations System Overview Aqua-Sim Components Experimental