無線Ａｄ ｈｏｃ網絡中基于區域代價的功率感知路由協議

摘 要：由于能量的限制，無線Ad hoc網絡面臨網絡生存時間、無線資源利用效率以及時延要求等方面的挑戰。為了降低網絡的能量消耗，延長節點壽命和網絡生存周期，提出了一種基于區域代價的功率感知路由協議。該協議在路徑選擇時，綜合考慮節點及其鄰居的剩余能量、節點發射功率和節點接收處理功率等因素，使網絡中節點的能耗趨于一致，并延長網絡的生存時間。該算法的復雜度不高，易于在節點運行。仿真結果證明該協議能取得較好的性能。

關鍵詞：節能; 區域代價; 功率感知； 路由協議; 無線自組網絡

中圖分類號：TN929.5; TP393 文獻標志碼：A

文章編號：10013695(2008)09278104

Regioncost based poweraware routing protocols for wireless Ad hoc networks

WEN Kai， GUO Wei， HUANG Guangjie

(National AntiInterference Communication Technology Lab， University of Electronic Science Technology of China， Chengdu 610054， China)

Abstract:Due to energy limitation， the wireless Ad hoc networks faces to the challenge of lifetime， wireless resource utilized efficiency and delay. This paper proposed a regioncost based poweraware routing protocol for reducing energy consumption and extending the survival period of networks. In route selecting， this protocol synthetically considers the factors ofreserving energy of node and its neighbor， transmitting power， and receiving process power etc. So this protocol lets the energy consumption of nodes tend to keep at same level， and prolongs the lifetime of networks. This protocol has lower complexity to carry out at nodes， and the simulation results show it can achieve well performance.

Key words：energy conserving; regioncost; poweraware; routing protocol; wireless Ad hoc network

無線Ad hoc網絡是在沒有任何現存基礎網絡設施或集中管理情況下動態形成的臨時網絡。由于無線節點發射功率和無線網絡接口傳輸范圍的限制，在無線Ad hoc網絡中傳輸數據往往需要多跳才能實現，故節點具備主機和路由器的功能。在很多典型的無線Ad hoc網絡應用中，由于重量和體積的限制，網絡節點配備的能量源通常都是有限的（如采用可充電或不可充電電池），這使得網絡中的節能策略顯得至關重要。目前無線Ad hoc網絡中的節能策略主要集中在MAC層和路由層，并且通常都是緊密結合在一起^[1，2]。在傳統基于最短路徑的路由協議中，網絡往往選擇最短的路由進行通信，導致網絡中局部區域負載過重，以至于過快地消耗完該區域內節點所存儲的能量，造成網絡分裂甚至網絡癱瘓。為了平衡網絡中區域負載不均和保護低剩余能量較少的網絡節點，RPR協議通過采用區域使用代價的機制作用于網絡路徑的建立過程，達到平衡使用網絡節點，延長網絡生存周期的目的。

1 研究現狀

路由是網絡層的主要功能，無線Ad hoc網絡中的路由協議根據節點獲得路由信息的途徑分為按需 (ondemand)和表驅動 (tabledriven)兩大類。按需路由協議又稱為反應式路由協議， 節點并不保存及時準確的路由信息。這類協議的主要代表有AODV(Ad hoc ondemand distance vector)^[3]、DSR(dynamic source routing)^[4]、DYMO(dynamic MANET ondemand routing)^[5]和TORA(temporallyordered routing algorithm)^[6]等。表驅動路由協議又被稱為先應式路由協議，是基于路由表周期性交換的路由協議。典型的表驅動無線移動路由協議有OLSR(optimized link state routing protocol)^[7]、TBRPF(topology dissemination based on reversepath forwarding)^[8]、DSDV(destinationsequenced distance vector routing)^[9]、WRP(wireless routing protocol)^[10]和STARA(system and traffic dependent adaptive routing algorithm)^[11]等。主動路由基于路由表的更新機制，其更新時間間隔對網絡性能的影響很大：更新間隔大，則路由表的信息可能陳舊過時；更新間隔小，會造成網絡開銷大，降低網絡效率。按需路由無須維護路由表，其路由控制信息比表驅動路由少得多，但是由于在數據傳輸之前必須先建立路由，會產生路由建立延遲。為了延長節點的壽命及網絡的生存周期，需要在路由建立中將節點功耗作為一個限制尺度，將路由的功耗要求同路由建立一體化考慮；另外，網絡負荷平衡對功率路由也很重要，它可避免少數節點被過分使用，電能很快被耗盡，造成網絡分割，從而影響網絡的互通性和性能。功率路由解決的基本問題有兩方面的內容：盡量延長網絡的生存周期；在一定的約束條件下使每個數據包從源點到目的節點所需的等效能量最小。

目前關于功率路由的研究主要集中在最小能量消耗的功率路由，最小能量消耗功率路由的主要出發點基于最小總體能量消耗。傳統路由協議對網絡的能量消耗是不同的，如在使用最小跳數的路由協議時，若信源—信宿間存在多條絕對距離（歐氏空間中的距離）相等的路由，則具有最小跳數的路由會作為首選路由，但從能量消耗的角度來看，由于發射功率正比于節點間距離的α次方(α≥2)，則這條路由的能量消耗最大。最小能量消耗的功率路由度量的基本原則是：分組從信源到信宿中各跳所消耗的發射功率之和最小。最小能量消耗的功率路由最為簡單的實現就是通過比較路由集合中的絕對能量消耗，然后選擇消耗能量最小的路由，但這種方法沒有考慮路由中節點的實際情況，如剩余能量、負載強度等，不能解決網絡中某些節點因能量過度使用從網絡脫離的問題。

為了改正使用絕對功率作為度量標準的缺點，目前的最小能量消耗功率路由中引入了與能量消耗相關的權重因子。引入權重因子后，節點的絕對能量消耗不再是最小能量消耗功率路由的惟一標準，最小能量消耗變為一種等效能耗的概念。目前這方面的典型研究有MBCR(minimum battery cost routing)^[12]、PAR（poweraware routing）^[13]、CMMBCR(conditional maxmin battery capacity routing）^[12]、CMRCR（conditional maximum relay capacity routing）^[14]。MBCR采用節點的剩余電池能量作為路由度量，節點愿意轉發分組的程度是其剩余電池能量的函數。剩余能量越小，節點越不愿意轉發分組，因而轉發費用越高。這種方法將選擇一條使各節點電池費用之和最小的路由作為最佳路由。如果所有節點的剩余電池容量相當，那么該度量將選擇最小跳數的路由。該度量的缺點是僅僅考慮了電池費用函數的總和，所選擇的最佳路由中仍然可能含有只有少量剩余電池容量的節點。PAR提出基于功率優化和設備行為的能量感知路由算法，節點的使用代價為每個節點在傳輸時的電池使用代價同其傳輸功率的乘積，每條路由總的使用代價就是節點使用代價的總和，路由選擇的準則就是選取代價最小的那條路由。CMMBCR期望讓最大節點電池壽命和公平使用節點能量這兩個目標不能同時達到。它的基本思想是：如果從源節點到目的節點的每一條可能路由中的所有節點都具有足夠的電池容量(超過某個門限γ) ，那么選擇每個分組消費的總能量最小的路由；如果所有的路由都有較少電池容量(低于某一門限γ) 的節點，則使用最小電池費用路由。CMRCR中引入節點傳遞能力（relay capacity，RC），它是節點當前的數據傳輸速率和現有條件下可支持傳輸時間的乘積，可支持傳輸時間是通過節點的剩余電池能量和能效消耗速度計算得到，它提高傳輸鏈路的可靠性，并降低網絡功耗。

目前的大多數研究都采用一種靜態方法去度量路由中的等效功率消耗，如采用節點剩余電量、節點傳輸功率等，這些度量標準在網絡初始化時就設定好，不能隨著網絡條件的變化進行改變，缺乏自適應性，并且對網絡中關鍵節點（如多條路由的共用節點）的使用沒有考慮主動負載均衡，采用的是能用就用的原則。因此最小能量消耗功率路由在動態的能量消耗度量模型、關鍵節點主動能量負載均衡等方面有較大的研究價值。

2 基于區域代價的路由協議

2.1 協議基礎

在文獻[15]中的研究表明，網絡中的每跳數據傳輸均存在一個與距離無關固定的能量開銷（接收處理能耗），因此在功率路由中應該對該開銷進行一定的折中。但在現有較多的功率路由協議中，常常沒有考慮節點無線接口的接收處理功耗，只考慮節點的發射功耗。這樣帶來兩個問題：a)雖然選到了最小發射功率路由，但路由的總體能量功耗并不是最小，這樣就會影響到網絡的節能效果；b)由于追求發射功率總和最小，則可能選擇到路徑很長的路由，這樣可能會增加網絡的時延，降低網絡的服務質量。

在通常的功率路由中，一般將節點的發射功率總和作為路由選擇的度量基數，而忽略了節點在接收數據時的處理功耗。從文獻[16，17]中可知四種常見無線網絡卡的功率消耗情況，如表1所示。

通過計算不難發現，上述四款無線網卡中，接收狀態時的功率消耗最低都相當于發射狀態的50%，高的接近85%。在實際的通信網絡中，無線發射接口的參數能較好地統一，但節點內部的情況可謂千差萬別。當節點處理功耗達到發射功耗的一定比例時，在功率路由協議設計中不考慮接收狀態功耗就會顯得不太合理，可見傳統功率路由的節能效果會受到一定的影響。

假設網絡中兩個通信的節點u和v，u為源節點，v為目的節點；從u到v的某一路徑需要m跳，將u到v路徑中的節點從1到(m+1)依次編號，則從節點u到v的路徑上絕對功率消耗為

定理1 節點的最大發射功率為Pt，max，節點的接收處理功耗為λPt，max，0＜λ≤1；節點發射功率連續可調，且節點間以最小功率通信。若節點u和v間的最短路由R1的跳數為m，則節點u和v間最小功率消耗由R2的跳數

證明 根據式（1），R1路由的功率消耗：Psum(M)=∑mi=1(Pt(i)+

因為R2路由是節點u和v間最小功率消耗路由，必有

定理1表明，節點間的最小功耗路由并一定是跳數越多的路由，當路由的跳數超過某個閾值時，雖然路由上節點的發射功率總和可以下降到一個相當小的水平，但是節點的接收處理功率總和會上升主導地位，從而導致路由節能效果的下降。

2.2 RPR協議

若以簡單的絕對能量消耗做為路徑選擇的度量標準，往往會導致網絡中某些節點能量消耗過快，造成節點過早關閉甚至網絡分裂。節能路由的目的除了降低數據傳送的能量消耗外，還有一個更為重要的目的是延長網絡的生存周期。延長網絡生存周期的一個有效手段就是盡量降低能量剩余不多節點的使用頻度，從而使網絡節點的生存時間盡量接近。為了保護能量剩余較少的節點，在度量路徑能量消耗時就不能使用簡單的絕對功率消耗。

基于上述分析，本文提出一種新的綜合考慮節點及其鄰居剩余能量、發射和接收處理功耗的節能路由協議——RPR(regioncost based poweraware routing）協議，該協議以AODV路由協議為基礎，其m跳路徑上的功率消耗度量標準如下：

其中：αi為路徑上節點i的使用代價因子，與節點自身的狀態或其鄰居節點的能量狀態相關。當αi同自身狀態相關時，此時的目的是延長單個節點的使用壽命，αi設計為與其剩余能量相關的函數；當αi同鄰居狀態相關時，此時的目的是防止節點所在區域能量消耗過快，αi設計為鄰居節點平均剩余能量的函數。

2.2.1 節點使用代價因子

在節能路由中節點使用代價因子——αi的設計是至關重要的。RPR在設計αi時將綜合考慮節點及其鄰居節點的剩余能量情況。在RPR協議中將與節點自身的狀態相關使用代價記為αi，self(i)，稱為單節點代價；與其鄰居節點狀態相關的使用代價記為αi，neighbor(i)，稱為區域代價；αi的最終取定為αi=

在以往許多的代價因子設計中，會出現代價因子非常大甚至無窮大的情況，有將使用代價絕對化的趨勢，這樣可能會導致網絡性能下降。圖1是網絡節點采用MBCR路由協議時情況：節點A需要發送數據到C，ABC路由（R1）的代價為11.67，AHGFEDC（R2）路由的代價為11.19。根據選用代價最小路由的原則，算法會選擇R2這條路由，通過簡單比較可以得到：R2路由的時延是R1的3倍，R2總傳輸功率消耗也是R1的3倍，R2中間節點數量是R1的5倍，從全網的角度來看R2，其路由的代價是相當大的。

傳統的代價因子設計在網絡節點剩余能量普遍較多時，效果較好；隨著網絡節點能量的逐漸下降，代價因子會快速上升，路由選擇可能會出現如圖1所示的情況，導致網絡性能下降。在設計節能路由時，除了考慮路由中節點的使用代價外，還應將節點鄰居的能量狀態聯系起來?？紤]路由中單個節點的使用代價是為了讓網絡中的節點盡可能同步調地消耗功率網絡，盡量避免網絡中某個節點的剩余能量較多其鄰居節點剩余能量較少的這種情況或與之相反的情況；考慮節點鄰居的能量狀態是為了在選擇路由時，避開能量剩余相對不多的區域?；谏鲜龇治?，RPR構建的代價因子包括兩個方面：單節點代價和區域代價。

2)單節點代價αi，self(i)的設計

節點轉發數據的代價與節點的剩余能量相對應，取值區間設計為0~Cmax。當節點剩余能量（αi，energy）的取值同其剩余電量的百分比對應時，取

由協議會將R2作為首選路由?？紤]單節點的使用代價是為了平衡網絡中節點的剩余能量情況。

余狀態聯系起來，有利于實現網絡中不同子區域間的使用均衡，如圖2所示：節點A傳送數據到節點B中的路由ACB和AEB，在只計算節點自身使用代價的情況下，這兩條路徑的代價完全一樣。IEEE 802.11中節點無論是否為數據包的目的節點，MAC都要進行接收，網絡中的這種無意識接收也是需要消耗能量的，由于節點E鄰居剩余的能量要多一些，從全網的角度上來考慮，路由AEB比路由ACB要優越，選擇AEB路由有利于進一步延長網絡的生存時間。

2.22 路由請求報文

在RPR中的路由請求（RREQ）報文中，將增加一個ARC(accumulated route cost)域，ARC代表從源節點到當前節點路由的累計代價。當節點第一次收到某個RREQ報文后，取出RREQ報文中ARC域的值存儲到本地，然后在轉發報文前將自己的轉發代價累加到ARC域中；若節點不是第一次接收到某個RREQ報文，將從新收到的RREQ報文中取出ARC的值同本地存儲的值比較，若小于前面存儲的值，則替換原有存儲的值，并轉發該報文，反之則丟棄該報文。

RPR與以往能量路由相比有兩個方面的區別：其一是在度量標準中引入了節點處理功耗，能更真實地反映節點在轉發數據時的使用代價，相比于傳統的方法更能保護低能量節點；另外一個是考慮節點所位于區域的能量情況，能更加有效地均衡節點的能量消耗。

為了評價RPR路由協議的性能， 從以下幾個方面對RPR路由協議進行檢驗：

a)MAC層能量消耗總量。該參數在MAC層進行統計，是MAC層發送數據包所消耗能量的一個總和，能直接反映網絡的能量消耗情況。計算方式為

∑數據包每個數據包的能量消耗

b)成功傳送1 bit的能量消耗。該參數反映網絡能量的有效使用效率。計算方式為

MAC層能量消耗總量/網絡中成功傳送的數據量

網絡中成功傳送的數據量是在IP層統計的，反映網絡中用戶數據的成功交換情況。

c)網絡節點的平均剩余能量。該參數反映網絡能量剩余的整體狀況。計算方式為

（∑節點節前當前能量剩余比較）/網絡節點數量

d)網絡中節點剩余能量不大于10%的比例。該參數反映網絡對某些節點過度使用的情況，同時能反映路由協議對節點過使用的抑制能力。計算方式為

剩余能量不大于10%的節點數量/網絡節點數量

e)網絡節點剩余能量方差。該參數能反映網絡中節點剩余能量的波動情況和路由協議對節點使用的平衡能力。計算方式為

∑節點（節前當前能量剩余-網絡平均剩余能量）2/網絡節點數量

f)仿真場景設置。60個節點隨機分布在1 500 m×1 500 m的矩形區域內。節點初始能量為0.015 J，最低接收門限為-88.62 dbmW，節點無線傳輸半徑為600 m；信道容量為1 Mbps， 網絡中的每個節點都是數據業務源， 業務分組的長度為1 024 bit， 分組產生時間間隔服從均值為1/0.25 s泊松分布， 仿真時間為600 s。節點支持三種路由協議，即AODV、MBCR和RPR。其中RPR的k值取定為1，根據文獻[18]中的調查數據，將最大發射功率同接收處理功率間的比值取定為1.4；同時為了更好地評估路由協議對能量消耗的均衡性能，并使網絡實現更好的節能效果，節點的發射功率可調，最大發射功率為5 mW，最小發射功率為2 mW。

從圖3可以看出，雖然均采用了功率調整以及相同的數據業務模式，在MAC層能量消耗總量上AODV是最高的，MBCR次之，RPR最低。這最主要的原因是AODV建立的路由是最短跳數路徑，根據電波衰減特性，其需要的發射功率要大很多，MBCR和RPR由于使用了代價函數，選擇的路徑不一定是最短路徑，其MAC層的能量消耗總量要低一些。MBCR由于其代價函數的取值可以趨于無窮大，增加其可能選擇跳數較多路徑的概率，其能量消耗總量要高于RPR。在仿真結束時，MBCR協議消耗的總能量相當于AODV協議的94%，而RPR只有AODV協議的90%。

圖4反映的是網絡總體能量的消耗情況，該曲線不能直觀地反映出網絡能量的使用效率。在圖4中，可以看到三種不同協議成功傳送1 bit數據時的平均能量消耗。雖然在圖3中，三個協議的能量消耗差異不太大，但由于AODV協議對網絡中某些節點的過度使用，造成關鍵節點能量過早地用完，導致數據重傳以及路由重建，以致網絡的能量使用效率最低。相比之下RPR的能量使用效率最高，傳送1 bit數據所消耗的能量相當于MBCR協議的97%；同AODV協議相比則只有它的84%。

圖5是在不同仿真時刻，網絡中節點平均剩余能量的情況。該仿真數據表明，在總體情況上，采用RPR路由協議時網絡節點的平均剩余能量相對較多。當仿真600 s結束時，各協議的網絡節點平均剩余能量情況如下：AODV協議的節點平均剩余能量為17%，MBCR協議的節點平均剩余能量為23%，而RPR協議的節點平均剩余能量達到了27%。

圖6反映了不同路由協議對節點能量使用的均衡能力。從圖中可以看出，當仿真一直進行到500 s時，剩余能量小于10%的節點比例情況各協議大體相當，但隨著仿真的進一步推進，各協議的性能表現迅速拉開差距。在仿真結束時，AODV協議剩余能量小于10%的節點比例達到了48%；MBCR協議也達到了33%；RPR協議情況最好，只有30%。圖7也是反映不同路由協議下的節點能量使用情況，從總體可以看見，RPR協議的性能表現也是最好的。

4 結束語

隨著技術的發展，無線Ad hoc網絡將得到越來越廣泛的應用。如何降低節點的能量消耗，延長網絡的生命周期，是無線Ad hoc網絡研究中的熱點問題。RPR路由協議在節點使用代價的度量上，引入了區域代價的方法，相比于單節點代價的路由協議，在節點能量使用上具備更好區域均衡性能。通過計算機仿真驗證，在節點發射功率可調的情況下，RPR在MAC層能量消耗總量、成功傳送1 bit的能量消耗、網絡節點平均剩余能量、節點剩余能量均衡等方面均有較好的性能表現。

參考文獻：

［1］WENIGER K， ZITTERBART M. Address autoconfiguration in mobile Ad hoc networkscurrent approaches and future directions [J].IEEE Network，2004，18(4):611.

[2]GOLDSMITH A J，WICKER S B. Design challenges for energyconstrained Ad hoc wireless networks[J].Wireless Communications，2002，9(4):827.

[3]PERKINS C， BELDINGROYER E， DAS S. RFC 3561，Ad hoc ondemand distance vector(AODV) Routing[S].2003.

[4]JOHNSON D B，MALTZ D A， HU Y C. The dynamic source routing protocol for mobile Ad hoc networks(DSR)[R].[S.l.]:Internet Draft， IETF MANET Working Group， 2004.

[5]CHAKERES I， BELDING R E， PERKINS C. Dynamic MANET ondemand(DYMO) routing[R].[S.l.]:Internet Draft， IETF MANET Working Group， 2005.

[6]PARK V， CORSON M. A highly adaptive distributed routing algorithm for mobile wireless networks[C]//Proc ofIEEE INFOCOM’97.1997:14051413.

[7]CLAUSEN T， JACQUET P E. RFC 3626， Optimized link state routing protocol(OLSR)[S]. 2003.

[8]OGIER R， TEMPLIN F， LEWIS M. RFC 3684，Topology dissemination based on reversepath forwarding(TBRPF)[S].2004.

[9]CHARLES E P， PRAVIN B. Highly dynamic destinationsequenced distancevector routing(DSDV) for mobile computers[C]//ACM SIGCOMM’94. London:[s.n.]，1994:234244.

[10]MURTHY S J， GARCIALUNAACEVES J. An efficient routing protocol for wireless networks[J].ACM Mobile Communication Networks，1996，1(2):183197.

[11]GUPTA P， KUMAR P. A system and traffic dependent adaptive routing algorithm for Ad hoc networks[C]//Proc of the 36th Conference on Decision and Control. San Diego， California:[s.n.]，1997:23752380.

[12]TOH C K. Maximum battery life routing to support ubiquitous mobile computing in wireless Ad hoc networks[J].IEEE Communication Magazine， 2001，39(6):138147.

[13]CAMPBELL A T， NAGHSHINEH M， BISDIKIAN C. Poweraware routing in wireless packet networks[C]//Proc of the IEEE International Workshop on Mobile Multimedia Communications(MoMuC’99).1999:380383.

[14]ZHOU Y，LAURENSON D I，MCLAUGHLIN S. High survival probability routing in poweraware mobile Ad hoc networks[J].Electronics Letters，2004，40(22):14241425.

[15]MHATRE V， ROSENBERG C. Design guidelines for wireless sensor networks: communication， clustering and aggregation[J].Ad hoc Network，2004，2(1):4563.

[16]WANG Szuchi， WEI D S L，KUO Y Y. A topology control algorithm for constructing power efficient wireless Ad hoc networks[C]//Proc of GLOBECOM. 2003:12901926.

[17]RAM R， REGINA R H. Topology control of multihop wireless networks using transmit power adjustment[C]//Proc of INFOCOM. 2000:404413.

[18]FEENEY L M， NILSSON M. Investigating the energy consumption of a wireless network interface in an Ad hoc networking environment[C]//Proc of INFOCOM. 2001:15481557.