一種基于權重的DSR路由改進算法＊

劉 麗，郭中華，雍 輝

(寧夏大學 物理電氣信息學院，寧夏 銀川 750021)

Ad Hoc網(wǎng)絡是由一組帶有無線收發(fā)裝置的移動節(jié)點組成的多跳臨時性自組織系統(tǒng)。由于其拓撲結構的時變性，以及無線信道的不確定性，使得其路由算法面臨挑戰(zhàn)。而節(jié)點依靠有限壽命的電池供電，一旦節(jié)點的電池能量耗盡，將會影響網(wǎng)絡中數(shù)據(jù)包的轉發(fā)，進而影響網(wǎng)絡性能。因此，如何在節(jié)點間選擇合適的路由，是Ad Hoc網(wǎng)絡的核心問題[1]?，F(xiàn)有的經(jīng)典路由算法，如DSDV[2]、CGSR[3]、AODV[4]、DSR[5]等 都 是 最 短 路 由 ， 即 最 小 跳 數(shù) 路由，不考慮能量因素。

目前，Ad Hoc中的節(jié)能路由算法主要有兩個方向[6]：一是使發(fā)送每個數(shù)據(jù)包耗費的總能量最?。欢潜M可能地延長網(wǎng)絡的生存時間。參考文獻[7]提出的MECR(Minimum Energy Cost Routing)是最小能耗路由協(xié)議。由于它總是選擇能耗最小的節(jié)點，容易使一些關鍵節(jié)點過早地消亡，導致了節(jié)點間的能量不均衡和網(wǎng)絡的分區(qū)；ESR[8](Energy Saving Routing)協(xié)議通過引入節(jié)點的期望時間(剩余能量和當前傳輸功率的比值)來延長網(wǎng)絡的生存時間，但是傳輸功率控制的引進將會導致無線設備的硬件改動。本文提出的算法，是在原有的DSR路由算法基礎上改進而成的。方案保留DSR的按需路由機制，在選路由的時候，除了最小跳數(shù)外，綜合考慮每條路由組成節(jié)點的剩余能量，提出一種基于權重的路由算法，根據(jù)路由權重的大小選取路由，盡量選用跳數(shù)少、剩余能量多的路由，從而達到節(jié)省能量，延長網(wǎng)絡生命的目的。

1 MWSR路由算法

1.1算法的基本思想

該算法綜合考慮能量與跳數(shù)構建一個路由權重函數(shù)，在這兩個參數(shù)之間尋找一個折中點，選擇路由權重值最大的路徑傳送數(shù)據(jù)，即期望找到一條組成鏈路生存時間比較長且跳數(shù)又較少的路由作為最后選定的路由，使得在延長網(wǎng)絡生存時間的同時，不會犧牲其他一些性能。至于上述兩個參數(shù)在路由權重函數(shù)中的比重，將由加權因子決定。

1.2算法的參數(shù)模型

為了便于研究，把Ad Hoc網(wǎng)絡定義為圖 G=(V，E，t)，其中 V為節(jié)點，E為邊，t為邊的權值，表示對應鏈路的剩余生存時間，即一條邊還能保持通路的時間值。

1.2.1路由的能量參數(shù)

本文將路由有效期作為路由的能量參數(shù)，即預測路由所有組成鏈路的剩余生存時間，將其最小值作為該條路由的能量參數(shù)。該能量參數(shù)可用如下公式表示：

以此為基礎構造的路由權重函數(shù)可以起到保護剩余能量較低節(jié)點的作用。其中，En表示路由rn的能量參數(shù)，i，j代表路由 rn中的兩個相鄰節(jié)點，t(i，j)代表節(jié)點 i與j之間鏈路的剩余生存時間值。

鏈路的剩余生存時間值并不能如節(jié)點剩余能量那樣直接得到，而是需要通過預測得知。在GSM[9]算法中，鏈路剩余生存時間值的計算公式為

式(2)在計算時忽略了接收節(jié)點被用來作為下一跳還能維持的時間。

為了克服GSM這個弱點，既要考慮發(fā)射節(jié)點發(fā)射該數(shù)據(jù)所能維持的時間，又要考慮接收節(jié)點接收并轉發(fā)該數(shù)據(jù)到下一跳還能持續(xù)的時間，以兩者中較短的時間作為該鏈路對應的剩余生存時間。因此，該時間權值可由如下公式表示：

1.2.2路由權重函數(shù)

為了選擇出最佳路由，需要構建一個路由權重函數(shù)，該函數(shù)的表示形式如下：

式中，rn表示有效路由集 R={r1，r2， …，rN}(1≤n≤N)中的某條路徑，ω是加權因子，En表示路由rn的能量參數(shù)，Hn表示路由rn的跳數(shù)，且有：

從表示形式可看出，此路由權重函數(shù)由兩部分組成：跳數(shù)和能量。之所以將跳數(shù)也作為代價函數(shù)的參數(shù)之一，是因為如果只將能量作為函數(shù)的考慮因素，確實可以起到延長網(wǎng)絡生存時間的作用，但網(wǎng)絡的其他一些性能將會“惡化”很多。而且路由的跳數(shù)對節(jié)省節(jié)點能量也起一些作用，數(shù)據(jù)傳輸時所用路由的跳數(shù)越少，路由就越穩(wěn)定，越不容易發(fā)生路由“斷裂”的情況，從而有效地避免數(shù)據(jù)重傳以及再次發(fā)起路由發(fā)現(xiàn)過程，這對于節(jié)點移動性較強的Ad Hoc網(wǎng)絡作用尤為明顯。

1.2.3加權因子

加權因子ω決定了跳數(shù)和能量這兩個參數(shù)在路由權重函數(shù)中的比重。CMMBCR[11]協(xié)議根據(jù)網(wǎng)絡中節(jié)點剩余能量的不同情況采取不同的路由選擇策略。借鑒這一思想，加權因子ω的值將根據(jù)路由候選集中各條路由組成節(jié)點的剩余能量情況來確定。

假設網(wǎng)絡中所有節(jié)點的初始能量值相同，則有：

式中，vn，l表示 路由 rn中的節(jié)點，p(vn，l)表示節(jié) 點 vn，l的剩余能量，p0表示節(jié)點的初始能量。

可以看出，當各條路由中節(jié)點的能量狀況較好時，ω值較大，此時跳數(shù)在路由權重函數(shù)中所占的比重較大，該算法傾向于選擇跳數(shù)較少的路由；反之，當能量狀況較差時，ω值較小，此時能量參數(shù)所占的比重較大，該算法傾向于選擇有效生存期較長的路由，從而起到保護剩余能量較低的“瓶頸”節(jié)點，盡可能延長網(wǎng)絡生存時間的目的。

1.3 MWSR路由算法的描述

該算法的前提是基于網(wǎng)絡中所有鏈路均為雙向，且節(jié)點可以隨時提供剩余能量的假設。

假設S為源節(jié)點，D為目的節(jié)點。一次數(shù)據(jù)傳輸過程的主要步驟如下：

(1)利用DSR路由機制進行路由發(fā)現(xiàn)，但在RREQ報文中需添加節(jié)點最小剩余能量域re、鏈路最小剩余時間域rt與節(jié)點剩余能量和域sum。

(2)D開啟一個定時器，保存該時間內(nèi)收到的所有RREQ報文中的路由。

(3)D根據(jù)路由信息計算出每條路由的路由權值W，選出具有最大權值的路由rn。

(4)D沿rn反向路由發(fā)送RREP報文到 S，進行數(shù)據(jù)傳輸。

2仿真及分析

2.1場景設置

使用NS[12]軟件來進行仿真，場景設置如下：在1 000 m×1 000 m的正方形區(qū)域內(nèi)隨機分布25個無線節(jié)點，節(jié)點按照RandomWaypoint模型移動；MAC層協(xié)議采用 IEEE 802.ll；使用CBR作為流量源，每條流的通信流量為20 kb/s；節(jié)點的無線信號傳輸模型設為TwoRayGround；節(jié)點的初始能量設為200 J，路由損失因子設為4，即如果節(jié)點 u和v之間的距離為d，則u發(fā)射數(shù)據(jù)到v需要的能量為d4，接收功率設為 0.l W，監(jiān)聽功率設為 0.08 W；仿真時間1 200 s。

2.2仿真結果與分析

仿真結束之后，對Trace文件進行分析，主要統(tǒng)計端到端平均延時和網(wǎng)絡生存時間來衡量網(wǎng)絡性能。

圖1表示網(wǎng)絡的端到端平均延時與節(jié)點最大移動速度之間的關系；圖2表示死亡節(jié)點個數(shù)與仿真時間的關系。

圖1 端到端平均延時與vmax之間的關系

由圖1可以看出，隨著網(wǎng)絡節(jié)點最大移動速度的增加，端到端平均時延總體上呈上升趨勢，但MWSR算法的端到端平均延時要比DSR低。雖然DSR協(xié)議選取最小跳數(shù)的路由發(fā)送數(shù)據(jù)，本應獲得更短的時延，但由于DSR協(xié)議沒有考慮網(wǎng)絡節(jié)點的負載情況，容易導致網(wǎng)絡擁塞，從而加大了網(wǎng)絡時延。所以在網(wǎng)絡負載較重的情況下，MWSR算法的延時會較短。

由圖2可以看出，采用MWSR算法的網(wǎng)絡生存時間要比采用DSR協(xié)議的網(wǎng)絡生存時間長。這是因為該算法把鏈路的剩余生命期作為選擇路由的標準之一，選擇路由時盡量避開生命期較短的節(jié)點，從而延長了網(wǎng)絡的生存時間。而且隨著死亡節(jié)點數(shù)量的增加，該算法的節(jié)能效果越明顯。通過對圖2中的3個圖進行對比可以看出，節(jié)點最大移動速度vmax越小，算法的節(jié)能效果越明顯，這說明該算法主要適合于節(jié)點移動速度較慢的場合。

圖2 不同vmax時死亡節(jié)點與仿真時間的關系

本文在原有DSR路由協(xié)議的基礎上作了一些改進，提出了一種基于權值的節(jié)能路由算法。通過綜合考慮路由有效期與跳數(shù)，構造路由權重函數(shù)對路由進行選擇，以期達到節(jié)能的目的。仿真結果表明，在相同條件下，該算法比基于最小跳數(shù)的DSR能節(jié)省較多的能量，從而延長了網(wǎng)絡的生命周期，同時也減小了網(wǎng)絡的端到端延時。但是由于數(shù)據(jù)包頭部附加的信息改變了數(shù)據(jù)包的結構，增加了數(shù)據(jù)包的長度，不可避免地會帶來額外的開銷。

[1]LI Jiang， CORDES D， ZHANG Jing Yuan.Power-aware routing protocols in Ad hoc networks[J].IEEE Wireless Communication， 2005(12)：1536-1284.

[2]MAHESH K M，DAS S R.On-demand multipath distance vector routing in Ad hoc networks[C]//Ninth International Conference on Network Protocols.Washington D.C.，USA：[s.n.]， 2001：14-23.

[3]PERKINS C E，ROYER E M.Ad-hoc on-demand distance vector routing，Proc[C].2nd IEEE Workshop on Mobile Com.Sys.and Apps.，1999：90-100.

[4]RFC3561.Ad hoc on demand distance vector(AODV)routing[DB/OL].http：//www.Ietf.org/rfc/rfc 3561.2003-07-23.

[5]JOHNSON D B， MALTZ D A， BROCH J.DSR：the dynamic source routing protocol for multi-Hop wireless Ad Hoc networks[M].Boston， MA，USA：Addison-Wesley Longman Publishing Co.，Inc， 2001：139-172.

[6]CHEN JiaYing，ZHEN Yang.Modified energy-aware AODV routing for Ad hoc networks[J].Journal of Nanjing University of Posts and Telecommunication， 2004，24(3).

[7]WANG H C，WANG Y H.Energy-efficient routing algorithms for wireless ad-hoc networks，Proc[C].18th IEEE PIMRC，2007.

[8]PENG Jing， TANG Chang Jie， ZHANG Jing， et al.Evolu-tionary algorithm based on overlapped gene expression[C]//ICNC-LNCS3612.Berlin：Springer，2005：194-204.

[9]ORDA A，YASSOUR B A.Maximum lieftime routing algorithms for networks with omnidirectional and directional Antennas[C].Proceedings of the 6th ACM International Symposium on Mobile Ad hoc Networking and Computing Mobi-Hoc’05， May 2005.

[10]樓驥洲.Ad hoc網(wǎng)格的生命周期最大化算法[D].杭州：浙江大學，2006.

[11]TOH C K.Maximum battery life routing to support ubiquitous mobile computing in wireless ad hoc networks[J].IEEE Communications Magazine， 2001(6)：2-11.

[12]秦冀，姜雪松.移動 IP技術與 NS-2模擬[M].北京：機械工業(yè)出版社，2006.