劉 麗，郭中華，雍 輝

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

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

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

1 MWSR路由算法

1.1算法的基本思想

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

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

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

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

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

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

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

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

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

1.2.2路由權(quán)重函數(shù)

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

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

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

1.2.3加權(quán)因子

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

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

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

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

1.3 MWSR路由算法的描述

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

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

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

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

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

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

2仿真及分析

2.1場景設(shè)置

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

2.2仿真結(jié)果與分析

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

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

圖1 端到端平均延時(shí)與vmax之間的關(guān)系

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

由圖2可以看出，采用MWSR算法的網(wǎng)絡(luò)生存時(shí)間要比采用DSR協(xié)議的網(wǎng)絡(luò)生存時(shí)間長。這是因?yàn)樵撍惴ò焰溌返氖Ｓ嗌谧鳛檫x擇路由的標(biāo)準(zhǔn)之一，選擇路由時(shí)盡量避開生命期較短的節(jié)點(diǎn)，從而延長了網(wǎng)絡(luò)的生存時(shí)間。而且隨著死亡節(jié)點(diǎn)數(shù)量的增加，該算法的節(jié)能效果越明顯。通過對(duì)圖2中的3個(gè)圖進(jìn)行對(duì)比可以看出，節(jié)點(diǎn)最大移動(dòng)速度vmax越小，算法的節(jié)能效果越明顯，這說明該算法主要適合于節(jié)點(diǎn)移動(dòng)速度較慢的場合。

圖2 不同vmax時(shí)死亡節(jié)點(diǎn)與仿真時(shí)間的關(guān)系

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

[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].杭州：浙江大學(xué)，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]秦冀，姜雪松.移動(dòng) IP技術(shù)與 NS-2模擬[M].北京：機(jī)械工業(yè)出版社，2006.