移動Ad Hoc網絡中的節能路由協議

陸 偉，楊余旺

(1.南京理工大學 計算機科學與工程學院， 江蘇 南京 210094；2.淮陰師范學院 計算機科學與技術學院， 江蘇 淮安 223300)

0 引 言

移動Ad Hoc網絡(mobile Ad Hoc network，MANET)是一種無任何基礎架構的開放式、可擴展式自組織網絡。由于MANET節點具有轉發功能，其接收數據分組和轉發均需要消耗能量。與源節點和目的節點不同，中間節點需要消耗更多的能量維持正常通信和網絡連通性[1]。

目前，MANET中已經有針對節能路由協議的研究文獻，這些協議均是將功率控制引入到現有各種路由協議設計之中[2-9]。文獻[4]提出了一種旨在增強網絡壽命的能量感知路由協議框架，和DSR協議相比，改進協議能夠節省20%的能量。文獻[6]使用圖論理論形成網絡拓撲結構以確保節點最小能量消耗維持網絡連通性，但研究結果并未從能量和時間上進行理論分析及測試。文獻[8]提出了一種能量感知多徑路由協議AOMR-LM，能夠平衡各條支路上的能量消耗和保存節點剩余能量，其使用了一種能量感知機制，通過節點的能量水平選擇節點剩余能量并實現路徑分類，和其它節能路由相比能夠有效提高網絡壽命、節約能耗。從上述研究可以發現，大多節能路由協議是基于最短路徑算法改進，而最短路徑路由中存在的缺陷會同樣存在于改進算法之中，缺乏創新性，存在缺少數學解析模型的理論基礎。綜上所述，由于已有的節能路由協議并未分析出路由尋路效率與能量消耗之間的關系，因此普遍存在節能效率低下的問題。

為此，本文引入MANET信號屬性，在其基礎上建立簡單穩健的數學解析模型，提出了一種能同時解決能量和路由效率的節能路由協議(energy saving routing protocol based on mathematical modeling，ESRP-MM)，最后實驗結果驗證了ESRP-MM的優越性。

1 問題描述

現有大多數路由協議[10]均使用最短路徑尋優技術，但最短路徑尋優存在的問題不可忽視，因為其僅考慮了最短傳輸距離和時間，并未將干擾、衰落、散射、噪聲等因素考慮其中。此外，最短路徑尋優技術容易造成網絡分割中斷，這是因為移動節點耗盡能量后可能中斷路徑重啟路由發現過程。再者，將能耗問題和最短路徑聯合考慮，將會進一步重新定義最短路徑的有效性，因為其路徑成本和計算復雜度將會因為能耗因素的引入而大為降低。

經典AODV協議[11]是當前MANET節能路由改造中最常用的基礎協議，盡管AODV具有低延時和按需建立路由等優點，但其仍存在各種不足使得其能量節省效率難以大幅降低。比如，在大規模高密度MANET網絡環境下，AODV會產生不一致的路由從而增加重傳次數，從而造成了不必要的能量消耗。

因此，針對上述問題，需要從數學模型建立角度設計路由規則。在能量控制階段，應該在隨機鏈路選擇或者路由維持的基礎上考慮設計路由策略，節能策略應該從路由發現過程就開始執行，故下文將設計一種節能路由協議。

2 ESRP-MM協議的設計

本節提出了適用于大規模MANET網絡的節能路由協議ESRP-MM，引入了帶寬效率到協議中，提高了節能效率和通信性能。為提高計算效率，ESRP-MM使用了成本因素用于選擇源目的節點對之間的最佳路由。其次，在路由發現階段通過更精確的成本計算實現最低能量路由選擇。ESRP-MM協議運行在802.11MAC協議[12]之上。

2.1 能量模型

能量模型設計基于MAC層協議，目前MAC媒體接入控制協議分為點協調式接入機制和分布式協調接入機制，由于點協調式接入機制是集中式控制，故ESRP-MM使用分布式協議接入機制。因此，當移動節點想要發送數據給另一個節點時，通常要進行網絡分配向量初始檢查。如果發現網絡分配向量大于0，節點停止發送直至其為0。為了消除MANET隱藏終端[13]的影響，ESRP-MM使用CMRTS和CMCTS兩類不同類型的控制分組。源節點發送CMRTS給接收節點，當接收節點收到CMRTS后，目的節點發送CMCTS分組。如果發送節點在特定時間周期內沒有收到CMCTS，則重新發送。源節點收到CMCTS后，將發送數據分組，而接收節點收到數據分組后將返回確認分組。此過程一至重復到源節點收到接收節點返回的確認分組為止。圖1給出了ESRP-MM狀態轉移圖。

圖1 ESRP-MM分組發送狀態轉移

(1)

式中：ηo為物理層的開銷。因此，結合概率理論和上述能量模型，ESRP-MM協議中，數據分組發送需要的累積能量表示為

(2)

式中：Em表示MAC層消耗能量。此外，數據分組成功接收消耗能量為

(3)

式中：在源節點i和目的節點j之間，ESRP-MM認為有(n-1)個中間節點。0,1,2…,M為節點序列號。結合式(2)、式(3)，有數據分組傳輸需要消耗系統的累積能量表達式為

(4)

2.2 路由成本評估

由前文可知，傳輸過程中大多數參數是較容易計算的，但也存在一些參數不容易得到。ESRP-MM協議考慮信號衰減由節點的隨意移動性引起，衰減速率可被定義為1/DP，其中D為節點間距離，P為路徑損耗指數[14]。因此，數據分組接收能量水平Er取決于發射端能量Et和DP比值，其中Et為分組傳輸所需的能量，故有表達式為

(5)

式中：α是實時環境中和環境因素相關的變量參數。因此，移動節點可以根據已知數據分組的接收能量水平以及期望接收能量值預估出其它數據分組傳輸需要的能量。此外，數據分組中的比特錯誤通常由噪聲、干擾和沖突造成，802.11MAC使用載波偵聽能夠有效識別沖突和干擾。因此，在利用噪聲和干擾參數的基礎上，ESRP-MM能夠通過調制方案和接收能量水平預估出誤碼率。如果分組包含s個比特，誤碼率為BER，則有分組錯誤率為1-(1-BER)s。因此，很容易給出RTS、CTS、ACK等控制分組的分組錯誤率，分組錯誤率主要受分組大小、干擾、接收能量和噪聲等因素影響。不過，RTS控制分組的分組錯誤率僅受沖突和干擾兩個因素影響，結合式(1)，將無線環境中的噪聲干擾表示為eIN，沖突為eCL，故有RTS請求控制分組的分組錯誤率為

eR,i,j=eIN+eCL-eINeCL

(6)

2.3 能量感知路由

ESRP-MM協議旨在路由發現過程中尋找具有高節能效率的路由，通過周期性維護路由以減小動態拓撲造成的不利影響。和傳統路由協議相似，ESRP-MM以尋找最短路徑的方法初始化路由發現進程。以圖2所示的場景為例，在源節點X和目的節點Y之間存在3種路徑。考慮到路徑上的所有節點，最短路徑有XPQY，XRSY，XTUY，而潛在的其它路徑有XPY，XQY，XRY，XSY，XTY和XUY。以S表示收發X和Y的路徑集合，Ns為路徑s的跳數，Es,i是路徑s上消耗的能量。因此，最短路徑可表示為

Sp=argmin(Ns),s∈S

(7)

類似，可定義節能最短路徑為

(8)

圖2 一種簡單MANET場景

ESRP-MM協議中，設計了一種路由策略用于確保首先找到最短路徑再篩選出具有最低能量消耗的路徑。在路由發現過程中，RREQ包含能量損耗和跳數等附加信息。源節點廣播RREQ分組，接收到RREQ的中間節點更新RREQ中的能量損耗和跳數信息。此外，ESRP-MM再設置兩個條件用于判斷中間節點是否轉發RREQ：①如果之前未收到相同的RREQ分組；②如果收到的分組和之前分組具有相同的跳數，但是具有更低的能量損耗。因此，前者可確保最短路徑尋優，后者能夠確保能耗最低。

3 性能評估

本節使用OPNET14.5網絡仿真軟件對ESRP-MM協議進行了性能仿真，從分組傳輸時間、分組丟失率、數據流丟失數目、耗能等角度給出了協議性能評估，并和文獻[8]所提協議、經典協議AODV進行性能對照。由于ESRP-MM借鑒文獻[8]的思想，其仿真環境、參數配置相近，而AODV協議則通過適當修改使其能夠計算能量消耗，并適用于ESRP-MM的仿真環境。在給定仿真區域面積內，節點位置隨機分布，節點采用隨機路點移動模型。仿真結果通過獨立50次循環求統計平均獲得。主要仿真參數配置見表1。

表1 仿真參數配置

圖3給出了ESRP-MM協議在不同分組大小、不同節點移動速率條件下的分組傳輸時間仿真結果。分組傳輸時間指分組由源節點發送經中間節點轉發目的節點接收整個過程需要的時間。由圖3可知，分組傳輸時間會隨節點移動速率和分組長度增加而上升。在節點移動速率小的條件下，分組大小變化對分組傳輸時間的影響呈正相關，但影響較小。在節點移動速率大時，分組長度越大分組傳輸時間越長。

圖3 分組大小不同時的網絡分組傳輸時間仿真結果

圖4給出了分組丟失率隨仿真時間的變化結果。和文獻[8]相比，ESRP-MM分組丟失率更小，表明ESRP-MM具有更優的分組傳輸性能。

圖4 分組丟失率隨仿真時間變化趨勢

圖5給出了不同節點數目條件下請求分組能量消耗結果。仿真對網絡內所有節點發送的請求分組的能量消耗進行統計并求平均給出單請求分組耗能結果。據圖可知，AODV隨著節點數目增加其能量消耗近線性增長，故AODV存在網絡節點易耗盡能量關機的問題，這是因為網絡規模的增加會使中間節點變多進而加速中間節點能量消耗所致。

圖5 節點數目不同時請求信息能量消耗結果

文獻[8]使用了迭代計算方法得到節點剩余能量，由于計算方法的低復雜度降低了系統的能量消耗。ESRP-MM由于使用了基于鏈路成本的路由因子，提高了最佳路由尋找速度，此外并未在能量計算過程中引入額外的復雜度，故大大降低了尋路能耗。

圖6給出了不同節點移動速率條件下的單數據分組能量消耗結果。高速移動節點一般會引起網絡拓撲結構的急劇變化、路由中斷和隱藏終端等問題。相比AODV和文獻[8]，ESRP-MM的單分組耗能隨著節點移動速率增加并未快速增加，而是保持在一個較穩定的低能耗水平，這和其使用的能量控制策略有關。ESRP-MM的能量控制策略能夠有效解決隱藏終端問題，能夠在高速移動場景下縮小給鄰居節點發送信息的傳輸范圍從而有效降低發送功率，實現單分組傳輸低能耗的目的。

圖6 不同節點移動速率條件下單數據分組能耗結果

4 結束語

能量節省問題是移動Ad Hoc網絡路由協議的研究點之一，傳統節能路由協議大多是在最短路徑路由協議基礎上增加能量控制策略實現，普遍存在能量效率低下、缺少數學模型論證的問題。本文提出了一種節能路由協議ESRP-MM，建立了包含節點屬性的數學模型，將帶寬效率引入到尋路策略中，描述了一種簡單能量控制策略，同時實現了最短路徑尋優和能量節約。仿真結果驗證表明ESRP-MM協議相較傳統協議具有更優的傳輸性能和能量節約性能。下一步，將借鑒ESRP-MM路由思想，研究適用于無線傳感器網絡的節能路由。