基于能量有效的移動Ad Hoc網絡路由算法

摘要:由于移動Ad hoc網絡中節點通常采用電池供電，一旦電源耗盡，節點就會被迫退出網絡，因此降低節點的能量消耗對保證節點間鏈路穩定至關重要。給出了節點剩余能量的計算公式，基于節點剩余能量提出了一種能量有效的移動Ad Hoc網絡路由算法MTMR，該算法能夠延長網絡的生命周期，并給出了該路由算法的尋徑示例。

關鍵詞:移動Ad Hoc網絡;節點剩余能量;能量有效路由算法MTMR;網絡生命周期;路由發現

中圖分類號:TP311文獻標識碼:A文章編號:1009-3044(2009)25-7122-03

An Energy-Efficient Routing Algorithm for Mobile Ad Hoc Networks

GUO Xiao-xi

(Computer Engineering College of Jimei University， Xiamen 361021， China)

Abstract: Nodes in mobile Ad hoc networks are supported by batteries. The limited energy supply will make nodes quit the network for running out of power. Reducing energy consumption is the key issue to assure the link stability. A function to estimate the node power situation and an energy efficient routing algorithm MTMR leading to a longer network lifespan were proposed. Based on MTMR， a routing discovery example was given to show how MTMR works.

Key words: ad hoc networks; remaining energy; energy efficient routing algorithm MTMR; network lifespan; routing discovery

移動Ad hoc網絡是由一組帶有無線收發裝置的移動節點組成的無線通信移動網，它沒有固定的基礎設施，具有組網靈活、建設維護成本低、易于迅速展開以及系統整體抗毀能力強等特點，移動Ad hoc網絡被廣泛應用于軍事領域、災難救援、移動辦公、臨時會場布置、傳感器網絡等不便于構建固定網絡而又需要傳遞數據和信息并協同工作的環境中，因此，移動Ad hoc網絡將成為未來無線通信系統結構中一個重要組成部分。

由于無線通信距離受限且Ad hoc網絡沒有基站設施的支持，網內節點間的通信往往需要通過借助其他節點中繼轉發才能實現，這樣就形成了多跳路由。節點動態加入和退出網絡并能隨機運動，以及節點采用電池供電等因素，造成鏈路斷開和重建相當頻繁，所以造成鏈路中斷的兩個主要原因是:節點高移動性、節點能量有限。在路徑選擇的時候如何能夠選擇更穩定的鏈路組成路由，將提高路由有效性，減少路由控制開銷，保證網絡服務質量。

針對節點高移動性，筆者在文獻[1]中已經提出了節點可信度模型和相關算法，該模型能夠有效的評估節點移動性和可靠性，提高了Ad hoc網絡路由算法的性能。

Ad hoc網內節點兼有主機和路由器的功能，節點能量不足，不僅使得這些節點本身不能工作，還會影響到依靠這些節點進行分組轉發的其他網絡節點，可能降低網絡的連通性，影響到整個網絡的壽命。能量有效路由算法的主要目的是在不影響路由協議基本性能的前提下，盡量的延長網絡節點的壽命，保證網絡的連通時間，進一步保證Ad hoc網絡的服務質量(QoS)。

目前，主要有以下一些能量有效路由算法:最小電池代價路由算法MBCR(Minimum Batery Cost Routing)[2]:使用節點的電池能量作為節點壽命的度量，把路由上節點的代價(與剩余電池能量相關的函數)之和作為路由選擇的量度，雖然能保證所選的路徑具有總的最低電池代價，但有可能該路徑上某些節點具有最大電池代價，從而加速這些節點的能量耗盡;最小化最大電池代價路由算法MMBCR(Min-Max Battery Cost Routing)[2]:在每條可用的路徑上，找出其中能量剩余最小的節點，然后比較各個路徑上這些能量剩余最小的節點，選擇其中具有最大值的節點所在的路徑作為路由，從而避免在所有可用路徑中選擇含有最小電池剩余能量節點的那條路徑，但無法對路徑總的能量進行選擇控制;條件最小化最大電池代價路由算法CMMBCR(Conditional Min-Max Battery Cost Routing)[3]:既考慮路徑上的能量消耗總量，也考慮節點的剩余能量情況。當源節點到目的節點的多條路徑上所有節點都有足夠的電池剩余能量，選擇傳輸總能量最小的那條路徑，否則采用MMBCR算法計算路由，避免選擇含有最小電池剩余能量節點所在的路徑。CMMBCR算法中存在高剩余電池能量的節點由于分配過多任務而出現能量迅速耗盡的現象。

該文將針對節點能量有限的問題，在第二部分提出了節點剩余能量的計算公式，基于節點剩余能量提出了一種能量有效的移動Ad Hoc網絡路由算法MTMR(Max Total and Min Remains)和MTMR算法的尋徑示例，并與AODV路由算法進行比較;第三部分給出結論和需要進一步研究的工作。

1 能量有效路由算法MTMR

目前主要有五種能量度量方式[4]:1) 最小化路由通信消耗的總能量，目的是在兩個通信節點之間找到一條各跳鏈路消耗的能量之和最小的路徑;2) 最大化網絡生命周期;3) 最小化節點能量水平差異;4) 最小化代價/分組，目標就是要得到一條具有最小總代價的路由;5) 最小化節點最大開銷。

MTMR路由算法綜合最大化網絡生命周期和最小化節點最大開銷兩種方法，從可用路徑中排除具有最小剩余能量的節點的同時選擇具有最大總剩余能量的路徑最為首選路由，從而保證所選路由的穩定性，提高路由有效性。

1.1 節點剩余能量的計算

節點剩余能量基于這樣的假設:每個節點有一個初始的能量E0，剩余能量為Er。節點從t1時刻經過Δt時間到達t2時刻，在Δt時間內節點發送的數據包數目為packet_size，每發送一個數據包消耗的能量假設為e，節點維持非休眠狀態最低單位時間能耗為c，則節點在t2時刻的剩余能量為:

Er(t2)=Er(t1)-e × packet_size-c × Δt(1)

1.2 能量有效路由算法MTMR

MTMR路由算法包括3種基本的控制分組:路由請求分組RREQ、路由應答分組RREP和路由出錯分組RERR。MTMR路由包括路由發現、資源預留、路由維護和資源釋放4個部分，本文主要介紹MTMR的路由發現操作。

假設節點i的剩余能量為Eri，有一條路徑N1…Ni…Nm，該路徑總的剩余能量為∑( Eri)，某個節點j是在這條路徑上所有節點中具有最小剩余能量的節點。

路由請求分組RREQ報文格式如表1所示。

路由應答分組RREP報文格式如表2所示。

1.2.1 路由發現

當一個節點需要和某個節點通信而沒有到達此目的節點的有效路徑時，便啟動路由發現過程。源節點首先向其鄰節點廣播路由請求分組RREQ。RREQ分組用一個極大

的數字初始化最小Eri字段，初始化∑( Eri)字段為0，這樣保證源節點的剩余能量不影響路徑選擇。

當節點j接受到從節點i發送來的一個RREQ分組，節點j是否轉發該分組取決于分組的相關字段，本文用P表示RREQ分組，RT表示節點j的分組接收列表。能量有效路由算法MTMR的轉發路由請求分組的處理機制如下所示:

RREQ_Process( i， j， P )

input

i: the node broadcasting P

j: the node receiving P

P: the routing request

RT: the reception table of node j

output:

an update P or none

body {

if node j receives P the first time

{

Add RT(P);

P. ∑( Eri) = P. ∑( Eri)+Erj;

if (P. Er > Erj) { P. Er= Erj;}

Update P;

Forward P;

Exit;

}

if node i already got the same routing request

{

if ( P. ∑( Eri)> RT. ∑( Eri)

|| P. Er > RT. Er)

{

Rewrite RT with P;

P. ∑( Eri) = P. ∑( Eri)+Eri;

if (P. Er > Erj) { P. Er= Erj;}

Update P;

Forward P;

Exit;

}

}

}

如果收到RREQ分組的節點為目的節點或者存有到目的節點的有效路由，該節點向源節點發送路由應答分組RREP，并將RREQ分組中的最小Eri和∑(Eri)的值復制到RREP相應字段中。當中間當節點收到多個RREP分組時，采用與節點轉發多個RREQ分組相同的機制進行RREP分組選擇轉發。

源節點收到多個RREP分組時，要根據目的節點序列號、跳數、最小Eri和∑( Eri)四個字段的值來決定選擇哪一條路徑作為源節點到目的節點的路由，若目的節點序列號、跳數相同，則選擇最終路由的機制是:

1) 首先排除在所有可用路徑中的最小Eri字段最小的路徑;

2) 從剩余路徑中選擇具有最大∑( Eri)字段的路徑作為最終路由。

1.2.2 應用MTMR路由算法的尋徑實例

圖1給出了MTMR路由發現過程的一個實例，其中節點S表示源節點，節點D表示目的節點，其余為中間節點，中間節點上的數字表示該節點的剩余能量(源節點和目的節點必須參與通信，它們的剩余能量不用考慮):

(a) RREQ分組的傳播 (b) RREP分組的傳播

圖1MTMR的路由發現過程

圖1(a)中根據MTMR路由協議的RREP分組轉發機制，目的節點D會收到三個路由請求分組，經由的路徑分別是S->A->E->L、S->B->F->L和S->C->G->M，并產生三個RREP分組。

當三個RREP分組到達源節點S時，三個RREP分組的跳數相同，最小Eri和∑( Eri)字段的值分別為(5，18)、(3，19)和(2、20)，根據源節點選擇最終路徑的機制，雖然路徑S->C->G->M->D有最大路徑總剩余能量∑(Eri)，但這條路徑也包含了三條路徑中的最小Eri的最小值，因此不選擇該路徑，最后選擇的將是路徑S->B->F->L->D。

與按需驅動路由協議AODV (Ad-hoc On-demand Distance Vector Routing)相比，在AODV中最多只有兩條路徑的路由請求分組會到達目的節點，這兩條路徑的組合可能是S->C->G->M->D和S->B->F->L->D，或者是S->C->G->M->D和S->A->E->L->D，無論是哪種情形，路徑S->C->G->M->D都有50%的概率被選中做為最終路由。而采用MTMR路由算法，路徑S->C->G->M->D被選中的概率為0%。這樣，可以徹底避免由于節點C的剩余能量過小導致其在通信未結束前就耗盡能量而退出網絡，源節點需要重新進行路由請求的情況。

2 結論

文中給出了節點剩余能量的計算公式，基于能量有效的MTMR路由算法，該路由算法既考慮了路由中單個節點的能量剩余，也考慮了整個路由的能量代價，能夠保證在滿足路由能量最大的情況下不存在某些節點剩余能量過低的情況，從而避免了由于個別節點能量耗盡引起路由失效需要重啟路由發現的情況。

目前節點剩余能量的計算公式只考慮了節點活動和維持非休眠狀態的能量消耗，將來應該針對不同的物理鏈路特性的節點活動、空閑、休眠和消亡[5]的4種狀態做出更精確的修改。另外，還需進一步進行仿真實驗，將MTMR算法與其他算法在路由控制開銷、路由有效率、數據分組端到端時延、數據分組遞交率等方面進行定量的比較。

參考文獻:

[1] Xiaoxi Guo， Chuanfeng Chen. A Node Credit Model for QoS Ad Hoc Routing Algorithms [J]. Dynamics of Continuous， Discrete Impulsive System， Series B: Applications Algorithms， 2007:187-190.

[2] S. Singh， M. Woo， C.S. Raghavendra. Power-aware with Routinging Mobile Ad Hoc Networks [C]. Proceedings of Mobicom， 1998:181-190.

[3] C.K. Toh. Maximum Battery Life Routing to Support Ubiquitous Mobile Computing in Wireless Ad hoc Networks[J]. IEEE Communication Magazine， 2001:138-147.

[4] 張卿. 無線自組網中節能相關若干關鍵問題研究 [D]. 上海: 復旦大學計算機與信息技術系， 2005.

[5] A.R. Lebeck， X. Fan， H. Zeng and C. Ellis， Power-aware page allocation [C]. Proceeding of Ninth ACM ASPLOS，2000:105-116.