MANET中基于能量約束的機會路由研究

摘 要:為了使能量受限的無線網絡壽命更大化，提出了MANET中基于能量約束的機會路由(ECOR)。根據節點的能量消耗模型(NECM)建立了候選節點等待時間函數(WTF);提出了基于能量的節點轉發候選集選擇策略(ECETX)，綜合考慮每個節點的歸一化能量值(PI)與鏈路狀況來產生投遞矩陣(delivery matrix)，以確定轉發候選集中節點的優先級;利用以上策略設計了基于能量約束的機會路由(ECOR)。仿真實驗表明，提出的ECOR比ExOR的網絡壽命有明顯提高，平均增長55%～70%左右，吞吐量也有15%～23%的提高。

關鍵詞:無線自組織網; 機會路由; 能量約束; 能量消耗模型; 等待時間函數; 候選節點集選擇策略

中圖分類號:TP393

文獻標志碼:A

文章編號:1001-3695(2010)02-0642-04

doi:10.3969/j.issn.1001-3695.2010.02.066

Study of opportunistic routing with energy constraint in mobile Ad hoc network

LI Qin-wei， CHEN Zhi-gang， ZENG Feng， QI Hua-mei， LI Deng

(School of Information Science Engineering， Central South University， Changsha 410083， China)

Abstract:This paper proposed an opportunistic routing based on energy-constrainting in mobile Ad hoc networks to maximize the life of energy-constrainting wirless networks. Firstly， introduced the node energy-consuming model(NECM)， and constructed the waiting time function(WTF). Then proposed the strategy for selecting forwarding candidates set based on metric named ECETX which consider both the unitary energy(PI) and the link state in order to build the delivery matrix， and then selected the nodes’ priorities which in forwarding candidates set. At last， designed an energy-constrainting opportunistic routing(ECOR) based on all of the above strategies. The simulation results show that the life of the network using ECOR is longer than using ExOR， increase by 60~70 percents in average， and the throughput increase by about 15~23 percents.

Key words:MANET; opportunistic routing; energy-constraint; NECM; WTF; ECETX

無線自組織網(MANET，又稱Ad hoc網絡)是一種節點完全對等的無線網絡。網絡中的每個節點既有主機又有路由器的功能，具有很強的移動性和靈活性，這也給設計高效的路由協議帶來了挑戰。傳統路由協議如AODV[1]、DSDV[2]等必須先建立一條有效的傳輸路徑之后，才能傳輸數據，而在很短的時間內由于網絡節點的移動或鏈路故障等問題往往會導致該條路由的失效，源節點只能重新建立路由，這就給網絡帶來了較大的傳輸延時并且導致數據報文的丟失。機會路由[3～7]與傳統路由不同，它并不在傳送數據報文之前建立一條完整的路由，而是通過鄰居節點的每一次轉發更加靠近目的節點。機會路由提高了在不穩定的無線鏈路傳輸數據的可靠性，尤其是在丟包率很高的動態變化的網絡中。然而，無線自組網中的每個節點都是通過能量有限的電池來支持其運行，一些節點提前死亡對整個網絡數據的傳輸會帶來很大的影響[8]，但目前的機會路由，如ExOR[4]、DART[7]等并沒有考慮節點能量的限制，因此，本文在ExOR路由協議的基礎上，考慮每個節點的能量狀況，提出了一種基于能量約束的機會路由(energy constraint opportunistic routing， ECOR)。

在一般情況下，機會路由的主要工作過程如下所述:

a)源節點通過某種策略在鄰居節點中選擇轉發候選節點集(forwarding candidates set)， 并給候選集中的節點分配轉發優先級(relay priority)，之后再向鄰居節點廣播發送數據包。

b)分為以下三種:(a)鄰居節點如果不在候選集中則忽略接收到的數據包;(b)如果在候選集中，首先檢查自己在候選集中的優先級，如果發現自己在候選集中優先級最高，則向發送節點返回ACK，并轉發數據包，否則必須等待優先級比它高的節點返回ACK后，再把自身的ACK和接收到的ACK綁定發回給源節點;(c)如果該節點經過一段時間等待后并沒有收到優先級比它高的節點的ACK，那么它認為優先級比它高的節點并沒有收到數據包，它有義務轉發數據包并返回自身的ACK給源節點。可以看出，機會路由充分利用了節點之間的協作和無線網絡的廣播機制，能夠在很大程度上提高鏈路傳輸數據的可靠性和網絡的吞吐量。

1 相關工作

2005年，Biswas等人[3，4]首先提出機會路由(extremely opportunistic routing， ExOR)基本策略之后，許多學者對其進行了深入的研究。文獻[5]提出的MORE路由算法，通過隨機線性網絡編碼與機會路由的結合，消去ACK響應，使得協議性能提升明顯，但隨之而來的是計算的開銷明顯增大，對節點的性能要求也比較高。在文獻[9]中給出了基于機會路由策略的網絡緩存模型——Ditto。在文獻[10]中，提出了基于機會路由與節點地理位置結合的路由算法GOR，使用地理位置與傳輸時間消耗結合作為轉發候選集合的選擇指標，然而不可忽略的是該算法(GOR)需要明確知道節點的地理位置。同時可以看出，以上各種算法均基于一個假設，節點能量是無限的(以上算法均未考慮節點的能量情況)，即使采用一種洪泛廣播方式來搜尋整個網絡的鏈路狀態信息，并且每個鄰居節點都時刻處于偵聽并等待轉發數據包的情況下，都不會給網絡的節點壽命帶來任何影響。事實上，無線自組網中的節點能量是極其有限的[8]，每個節點都來廣播并時刻等待轉發數據包勢必會造成某些負載重的節點提前死亡，造成網絡壽命的降低。影響整個網絡的性能。因此，有必要建立一種能夠均衡網絡節點能耗的機會路由，保證網絡中節點耗能的平衡性，從而提高網絡的整體壽命。

目前，已有很多學者提出了基于節能路由協議，總結起來有兩種設計方法:最小化傳輸能量和最大化網絡生存時間。以上設計都是基于傳統路由協議。機會路由因為其特有的特性，如投遞矩陣靠洪泛廣播方式完成，由每個節點維護，并依靠其對候選集節點分配轉發優先級，這些均導致了在機會路由中加入節能機制的困難性。本文通過給網絡中每個節點根據自身能量狀況建立等待時間函數(wait time function，WTF)，保證能量低的節點延時較長時間返回ACK幀，以回避轉發數據包;同時，提出了基于能量的節點轉發候選集選擇策略(ECETX)，綜合考慮每個節點的歸一化能量值(PI)與鏈路狀況來產生投遞矩陣，確定候選集中節點的優先級，從而避免使用能量低的節點轉發數據包，最終實現提高網絡壽命的目的。

本文介紹了節點的能量消耗模型，并構造了等待時間函數，同時，提出轉發候選節點集選擇策略(ECETX)，并以此為基礎在MANET中重新設計了一種基于能量約束的機會路由(ECOR)。通過仿真實驗，驗證了本文提出協議的有效性。

2 基于能量約束的機會路由設計

2.1 節點的能量消耗模型及等待時間函數

本文采用文獻[11]中提出的能量消耗模型，設節點i的電池能量最大值是Eimax，Ei表示當前節點剩余能量，Eiconsume表示節點i已經消耗的總能量，因此，可以得到:

Ei=Eimax-Eiconsume(1)

定義PI為PI=Ei/Eimax(2)

節點的能量消耗主要可以分為三種狀態，分別是發送、接收和轉發。設節點發送一個數據分組所需能量為

Esend=PsTp=IsvTp(3)

接收一個數據分組所需要的能量為

Erecv=PrTp=IrvTp(4)

轉發一個數據分組所需能量為

Efw=(Psend+Precv)Tp(5)

可以得到節點i已經消耗的總能量為

Eiconsume=Esend+Erecv+(N-1)Efw(6)

其中:Psend為發射功率;Precv為接收功率;Tp表示發送和接收一個分組所需時間，在傳輸速率為1 Mbps的情況下，Tp=Psize×10-6，Psize為分組長度;Is為發送電流;Ir為接收電流。根據文獻[12]，在Ad hoc網絡環境下，經過多次實驗所測的對于不同傳輸速率的無線網卡在相同狀態下的能量消耗值近似。因此，取v=4.74 V～5.00 V，在發射狀態下Is=280 mA，接收狀態下Ir=204 mA。

為了能夠使網絡的壽命最大化，網絡中的節點應該滿足:能量充足的節點應該轉發數據包，而能量低的節點則應該盡量回避轉發數據包。機會路由中，源節點向鄰居節點廣播發送數據包，數據包中的頭部字段標明了候選集中節點的優先級，如果優先級高的節點能量很小，這時候可以讓它啟動一個計時器等待一定的時間，這就會使優先級比它低的候選集節點收不到優先級高的節點的回應ACK幀，從而，優先級稍低的節點就會認為優先級高的節點并沒有收到源節點廣播的數據包，它有義務將接收到的數據包轉發出去，而此時優先級高的節點偵聽到其他候選節點將數據包轉發出去后，就停止計時器，并丟棄收到的源節點的數據包。從而，避免了能量低的優先級高的節點轉發數據包耗費大量的能量，降低網絡的壽命。

由以上分析可知，應該根據節點剩余能量值產生一定的延時時間，當能量充足時，延時時間極小，近似為0;而當能量比較低，尤其是低于某個限度時，此時的延時應該足夠大，大于SIFS和ACK幀的回應時間。從而，可以建立一個延時函數，使之與PI成反比關系，當PI很大時，延時函數下降速度加快，并且值極小(近似為0)，PI很小時，延時函數快速增大。由此，本文定義WTF為PI的函數，并基于以上性質，可以用指數函數ex得到函數e-nx，如圖1所示。該函數的值域為[0，1]，n為常數。由圖可知，取n=23或25均可。本文中取n=23。在這種情況下，可以得到當PI>0.2時，WTF(PI)值很小，近似于0。而當PI<0.1時，WTF(PI)值大于0.1D，且隨著PI的減小，WTF(PI)的值急劇增大。

所以，有

WTF=f(PI)=De-nPI=De-n(Ei/Eimax)(7)

其中:D為設定的最長等待時間。本文設置D的值為10SIFS。

可以看出，在每個網絡節點加入等待時間函數后，節點會根據自己能量的大小計算出等待時間函數的值，然后等待時間耗盡之后再回應源節點的信息。由于每個節點的剩余能量在很大概率上不可能完全相同，等待時間或大或小也不盡相同，這也能有效地避免回應ACK幀之間的碰撞和沖突。針對等待時間函數，可以在每個節點加入一個計時器來實現。此時如果優先級高的節點收到了優先級低的回應ACK或偵聽到優先級低的節點轉發了源節點數據包，則丟棄收到的源節點廣播的信息包。當然，網絡單純靠一個等待時間函數機制的話，可以想像，如果能量低的節點被選做轉發候選集中優先級高的節點，為了回避轉發數據包，能量低的節點會選擇等待一個較大的時間，這就會導致整個網絡傳輸延時的增大，從而不能很有效且有質量的做到網絡節點消耗能量平衡與網絡QoS性能之間的均衡，所以應該保證網絡中節點能力低的情況下，盡量被不選做轉發候選集中優先級高的節點。因此，本文提出轉發候選集的選擇策略ECETX，與WTF相互作用，共同保證網絡能量消耗的平衡和整個網絡的QoS性能。

2.2 節點轉發候選集選擇策略(ECETX)

事實上，如果源節點在發送數據包時，能量很低的節點在源節點的轉發候選集中的優先級都是最高的，這樣勢必會給網絡的壽命帶來影響，并且極大地影響網絡的傳輸延時，即便它消除了回應ACK幀之間的沖突與碰撞。因此，為了避免能量過低的節點在候選節點集中優先級最高，本節中提出基于能量約束的候選集選擇策略，在傳統機會路由候選集選取策略中加入能量限制選定候選節點的優先級，同時考慮鏈路狀態，兩者有機的結合。

定義1 設Ad hoc網絡的節點集為V，鏈路集合為E。源節點vs到目的節點vd在不考慮能量時的最佳路徑bestxEnergy_psd={vs，vi，…，vd}滿足:psd∈Psd，ETX(bestxEnergy_psd)≤ETX(psd)。其中ETX[7](expect transmission count)為當前節點成功發送一個數據包到目的節點的期望傳輸包數。設s節點的鄰居節點集為Ns，轉發候選節點集Fs={v1，v2，…，vi，…，vn}，FsNs。

定義2 轉發候選集選擇策略ECETX。

ECETX=(1-α)ETX/ETX+αPI(8)

容易得到若ECETX(vs，vi)>ECETX(vs，vj)，則有vi優先級大于vj。其中，ETX為發送節點通過每個鄰居節點到目的節點的平均期望發包數，PI為節點剩余能量歸一化值，α為鏈路狀態與PI之間的均衡因子，且0≤α≤1。本文中取α=0.5。從該策略中可以看出，每個節點根據當前的鏈路狀態和剩余能量狀況選擇轉發候選集中節點的優先級，而不是像ExOR一樣單純地考慮候選集節點距離目的節點的遠近來選定節點的優先級。本文中，設候選節點集的節點數為8[3]。

在這種情況下，轉發候選集產生算法如下:

//GetFsByECETX(s，Ns)

CsΦ，Cs′Φ，FsΦ，old-ECETX(s，Nx)=0，cnt=0;

for each v ∈Ns∩(v∈Ns，PI(v)>0)

add v to Cs′;

calculate ECETX(s，Ns);

old-ECETX(s，Ns)=ECETX(s，Ns);

decending sort Cs′by old-ECETX(s，Ns);

CsCs′;

while(Cs′!=Φ){

Remove v from Cs′， and add v to Fs， cnt++;

if(cnt>8‖PI(v∈Ns)==0) break;

get new-ECETX(s，Ns)according to Eq.8;

decending sort Cs′ by new-ECETX(s，Ns);

}//end while

return Cs，Fs;

對于轉發候選集產生算法，其計算量比較小，設n為s節點鄰居節點數，則該算法的時間復雜度僅為O(n2)。下面給出一個示例，如圖2所示。

示例中，節點1向8發送數據，節點1首先計算與每個鄰居節點的ECETX值，更新自己的投遞矩陣，并得到F1={2，4，3}，然后依此類推，得到F2={5，3}，F5={8，6}，可見，采用本文提出的ECETX轉發候選集選擇策略有效地避免了使用能量很低的節點3作為轉發優先級高的節點。

2.3 基于ECETX的機會路由設計

本文設計的機會路由中，ACK幀[5]增加一個字段，表示節點自身剩余的能量信息，這樣，節點在收到候選集節點返回的ACK幀時，可以查看這個字段，并將信息讀取出，以更新轉發矩陣。這時的ACK幀如圖3所示。

preamblePLCPheaderframecontrolrecieveraddresscand.ID

FCSpadenergyPI

圖3 ACK幀字段

則更改后的機會路由過程可以描述如下:

/Initizlize: enum pkt_type{ack， pkt};node PI=1，count[][ack]=0， count[][pkt]=0， from now on， every node update PI with count changing/

1Sending node calculate delivery matix with ECETX， and creates prioritized candidate set.

2Send packet with cand.ID， count[node_ID][pkt]++， update PI.

3Accept pkt， count[node_ID][pkt]++， update its PI. Check if(destination)， Reply the sending node with ACK that the pkt arrives the destination now， return; else open its timer， and delay WTF(PI); During timer not expired， listen and judge if(Timer>0)， go on waiting untill time expire， and if(pkt=itself or recv other Cand.ID relpy ACK)， drop its pkt， set timer=0; if(timer==0) reply sending node ACK， count[node_ID][ack]++， update PI.

Forwarding node act as sending node， goto 1.

End.

以上為基于能量約束的機會路由的具體執行過程，可以看出，此過程僅在原來算法(ExOR)基礎上增加了少量的更新節點能量的開銷，這對于整體網絡來說，影響甚小，可以忽略。當然，在具體應用ECOR時，可以采取WTF和ECETX啟用或關閉的方式使用。

3 仿真實驗與性能分析

3.1 評價指標

1)網絡節點存活數 當節點能量耗盡時，稱該節點死亡。網絡節點存活數指網絡中未死亡節點的個數。表示為

liveNum=∑i0)(9)

其中:num(energy>0)表示為當節點能量值大于0時，記為1，最終累加得到網絡節點存活數。

2)節點剩余能量均方差 在某一時刻，取所有節點的剩余能量的均方差值來衡量網絡中節點能量消耗之間的均衡程度。表示為

σt=1N∑Ni=0(Eit-Et)2(10)

其中:Eit為t時刻節點i的剩余能量，Et-表示t時刻網絡中所有剩余能量的平均值，N為網絡中節點的數目。

3)網絡吞吐量 指網絡實際所達到的有效帶寬大小。表示為

throughput=∑Ni=0Ni(recv)Pkt_size/T(11)

其中:Ni(recv)表示節點i所接收到的所有數據包，Pkt_size為數據包的大小，T為仿真的時間。

3.2 仿真場景與結果分析

本文的整個實驗在NS2.31[13]上完成，物理層為雙向無線鏈路，每個節點的信道帶寬為1 Mbps，MAC子層采用IEEE 802.11協議，模擬節點在2000×2000的區域內移動，移動模型采用random way point運動模型，采用的協議分別為ECOR、ExOR，網絡的規模為100個節點。模擬時間為100 s，節點的最大移動速度Vmax取5 m/s，停止時間pausetime=10 s。數據包大小為512 bit，類型為cbr，修改后的ACK幀大小為32 bit。取電壓v=5.00V，在發射狀態下Is=280 mA，接收狀態下Ir=204 mA。每個節點初始能量均為10 J。

在隨機場景下按照以上實驗配置，每隔2 s統計一次各種情況下的節點存活數，得到結果如圖4所示。

由圖4可以看出，本文設計的機會路由ECOR(WTF-ON，ECETX-ON，后文中若不特別注明，均為此種情況)比傳統的機會路由ExOR的平均網絡壽命提高了60%～70%，同時，可以看到ExOR中網絡節點在30 s以后，死亡速率基本相同，在90 s時，網絡節點全部死亡。而ECOR的網絡節點中50 s～80 s時，節點陸續死亡，但死亡數量很少，而在80 s～90 s時，大量節點死亡，網絡中存活節點劇烈減少。這是因為，本文設計的ECOR有效的回避了能量低的節點轉發數據包，從而延長了網絡壽命，網絡節點的死亡完全是因為自身發送數據包而造成。同時，從ECOR(WTF-ON，ECETX-OFF)和ECOR(WTF-OFF，ECETX-ON)，可以發現它們均與ECOR變化規律基本吻合，只是ECOR比它們的網絡壽命稍長，因此，后文中，只討論ECOR在WTF和ECETX均啟用時的網絡狀態。

同樣采用以上隨機場景，每10 s統計一次網絡中節點剩余能量的均方差，得到結果如圖5所示。

由圖5可以看出，在仿真時間小于20 s時，網絡中節點剩余能量均方差幾乎相等，而在仿真時間大于30 s后，ExOR中節點剩余能量均方差均大于ECOR的節點剩余能量均方差。則說明了本文提出的ECOR路由能夠很好的均衡網絡中節點能量消耗，從而達到最大化網絡壽命的目的。

最后，本文使用相同的隨機場景，每10 s計算一下網絡的吞吐量，吞吐量為網絡中這10 s內所傳輸數據的大小。所得結果如圖6所示。

由圖6可以看出，仿真時間T<30 s前，ExOR與ECOR的吞吐量幾乎相等，而當T>40 s時，ExOR吞吐量明顯下降，而ECOR則相對穩定，網絡吞吐量下降緩慢。整體來看，ECOR比ExOR的網絡吞吐量提高了15%～23%。

以上實驗將本文設計的機會路由ECOR與傳統的機會路由ExOR比較，均體現了ECOR的有效性。其網絡壽命和網絡吞吐量均比ExOR有所提高，同時，能夠達到網絡節點能量消耗均衡的目的。

4 結束語

本文中設計了基于能量約束的機會路由，通過引入節點的能量模型，構造了等待時間函數WTF并提出了基于能量約束的節點轉發候選集選擇策略ECETX，有效地做到了網絡中各個節點能量消耗的均衡，延長了網絡的壽命并提高了網絡的吞吐量。然而，在網絡中常常會出現某些節點負載很重而造成局部擁塞的現象，但此基于能量約束的機會路由尚沒有考慮網絡的負載情況，同時也可能因采用了一定的WTF機制導致數據包傳輸的延時增大，因此將在下一步工作中繼續研究基于能量約束和負載均衡的機會路由協議，并尋找出一種能夠均衡網絡能量消耗和降低數據包傳輸延時的路由機制。

參考文獻:

[1]PERKINS C E， ROYER E M. Ad hoc on-demand distance vector routing[C]//Proc of IEEE WorkShop on Mobile Computing Systems and Applications (WMCSA).1999:90-100.

[2]PERKINS E，BHAGWAT P. Highly dynamic destination-sequenced distance-vector routing(DSDV) for mobile computer[J]. ACM SIGCOMM: Computer Communications Review，1994，24(4):234-244.

[3]BISWAS， MORRIS R. Opportunistic routing in multi-hop wireless networks[J]. ACM SIGCOMM Computer Communication Review，2004，34(1):69-74.

[4]BISWAS S， MORRIS R. ExOR: opportunistic multi-hop routing for wireless networks[C]//Proc of SIGCOMM’05.2005:133-145.

[5]CHACHULSKI S， JENNINGS M， KATTI S， et al. Trading structure for randomness in wireless opportunistic routing[C]//Proc of ACM SIGCOMM. Kyoto:[s.n.]，2007.

[6]ZENG K， LOU W， ZHAI H. On end-to-end throughput of opportuni-stic routing in multirate and multihop wireless networks[C]//Proc of IEEE INFOCOM.2008.

[7]ERIKSSON J， FALOUTSOS M， KRISHNAMURTHY S. DART:dynamic address routing for scalable Ad hoc and mesh networks[J]. IEEE/ACM Trans on Networking， 2007，15(1):119-132.

[8]CORSON S. Macker IRFC2501， Mobile Ad hoc networking (MANET):routing protocol performance issues and evaluation considerations[S].1999.

[9]DOGAR F R， PHANISHAYEE A， PUCHA H， et al. Ditto:a system for opportunistic caching in multi-hop wireless networks[C]//Proc of MOBICOM.2008.

[10]ZENG K， LOU W， YANG J， et al.On throughput efficiency of geographic opportunistic routing in multihop wireless networks[C]//Proc of QShine’07. Vancouver， British Columbia:[s.n.]，2007.

[11]WANG Yu， GARCIA-LUNA-ACEVES J J. Collision avoidance in multi-hop Ad hoc networks[C]//Proc of the 10th IEEE International Symposium on Modeling， Analysis， and Simulation of Computer and Telecommunications Systems (MASCOTS’02). TX， USA: IEEE， 2002.

[12]LAUER G. Address servers in hierarchical networks[C]//Proc of ICC. Atlanta， GA: IEEE， 1988: 443-451.

[13]NS-2 network simulator[EB/OL]. http://www.isi.edu/nsnam/ns/.

[14]De COUTO D S J， AGUAYO D， BICKET J， et al. A high-throughput path metric for multi-hop wireless routing[C]//Proc of MOBICOM.2003.