摘要：針對(duì)在移動(dòng)Ad hoc網(wǎng)絡(luò)中，由于節(jié)點(diǎn)移動(dòng)和能量有限導(dǎo)致節(jié)點(diǎn)失效、傳輸鏈路不穩(wěn)定的問(wèn)題，改進(jìn)原有鏈路剩余時(shí)間計(jì)算方法，并與節(jié)點(diǎn)剩余能量結(jié)合計(jì)算路徑質(zhì)量，將路徑質(zhì)量作為判決條件引入到AODV協(xié)議中，最終形成基于鏈路質(zhì)量的路由算法。仿真表明改進(jìn)的算法可提高選擇路徑的可靠性，降低丟包率和平均端到端時(shí)延。

關(guān)鍵詞：路由算法； AODV；鏈路質(zhì)量

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2013）04-0751-04

Routing Algorithm Based on Link Quality in Moblie Ad hoc Networks

ZENG Ge-ping，CHEN Yue

（ Chongqing University of Posts and Telecommunications， Chongqing 400065，China）

Abstract： Because of node mobility and energy limitation lead to node failure and transmission link instability in Ad hoc Networks， improve original Link Lifetime calculation method， calculate path quality with node residual energy， the path quality as a judgment condition introduced into AODV protocol，Ultimately form routing algorithm based on link quality. Simulation results show that the improved algorithm can improve the selection path reliability and reduce the packet loss rate and the average end-to-end delay.

Key words： routing algorithm； AODV； Link quality

移動(dòng)Ad hoc網(wǎng)絡(luò)[1]是一種無(wú)線自組織網(wǎng)絡(luò)，節(jié)點(diǎn)間通信無(wú)需固定基礎(chǔ)設(shè)施的支持，廣泛應(yīng)用于戰(zhàn)場(chǎng)、應(yīng)急救援等需快速部署的環(huán)境。在該網(wǎng)絡(luò)中，節(jié)點(diǎn)間通過(guò)中間節(jié)點(diǎn)的幫助以多跳的方式進(jìn)行通信，由于網(wǎng)絡(luò)中節(jié)點(diǎn)間的移動(dòng)和能量有限，網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)變化可能導(dǎo)致鏈路斷裂、路由重建，從而使數(shù)據(jù)包丟失重傳，網(wǎng)絡(luò)性能下降。目前基于鏈路質(zhì)量的Ad Hoc路由的研究主要在路由協(xié)議中增加QoS機(jī)制，該文針對(duì)現(xiàn)有的鏈路剩余時(shí)間預(yù)測(cè)方法進(jìn)行改進(jìn)，結(jié)合數(shù)據(jù)傳輸對(duì)節(jié)點(diǎn)能量的需求，提出一種新的基于鏈路質(zhì)量的路由算法。

1 網(wǎng)絡(luò)模型

給定網(wǎng)絡(luò)拓?fù)鋱DG=（V，E），V是網(wǎng)絡(luò)節(jié)點(diǎn)集合， vi∈V表示網(wǎng)絡(luò)中任意節(jié)點(diǎn)，E表示網(wǎng)絡(luò)中存在的通信鏈路集合。假設(shè)網(wǎng)絡(luò)中所有節(jié)點(diǎn)都能感知自身實(shí)時(shí)能量狀態(tài)，附帶配置GPS獲取節(jié)點(diǎn)位置。

2 路徑可用性預(yù)測(cè)算法

該算法的核心思想是：對(duì)所選的影響鏈路質(zhì)量因子進(jìn)行預(yù)測(cè)處理，將不同參數(shù)通過(guò)一定的規(guī)則形成一個(gè)單一的度量，并以此作為路由選路的基礎(chǔ)。該文選擇兩個(gè)影響Ad Hoc網(wǎng)絡(luò)的參數(shù)：剩余鏈路時(shí)間和節(jié)點(diǎn)剩余能量來(lái)簡(jiǎn)化鏈路質(zhì)量預(yù)測(cè)問(wèn)題，通過(guò)將節(jié)點(diǎn)當(dāng)前剩余能量能夠滿足待傳數(shù)據(jù)的能量需求為基礎(chǔ)，并對(duì)節(jié)點(diǎn)間鏈路有效維持時(shí)間進(jìn)行預(yù)測(cè)，通過(guò)對(duì)路徑中的節(jié)點(diǎn)的剩余能量瓶頸與路徑中各條鏈路的有效時(shí)間的最小值進(jìn)行處理，形成一個(gè)路徑質(zhì)量，比較不同路徑的路徑質(zhì)量進(jìn)行選路。

2.1 節(jié)點(diǎn)剩余能量計(jì)算

節(jié)點(diǎn)剩余能量計(jì)算是確定節(jié)點(diǎn)能量是否滿足數(shù)據(jù)流對(duì)傳輸節(jié)點(diǎn)的能量要求，路由請(qǐng)求時(shí)，計(jì)算源節(jié)點(diǎn)發(fā)送的數(shù)據(jù)流所需能量，在選路時(shí)記錄中間節(jié)點(diǎn)完成當(dāng)前任務(wù)后剩余能量與能量需求進(jìn)行比較，得出節(jié)點(diǎn)能否作為路由中間節(jié)點(diǎn)進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)。

本文采用文獻(xiàn)[2]中提出的能量消耗模型，Eold表示節(jié)點(diǎn)當(dāng)前能量，Enew表示節(jié)點(diǎn)剩余能量，Econsume表示節(jié)點(diǎn)消耗能量，由此可得：

[Enew=Eold-Econsume] （1）

節(jié)點(diǎn)的能量消耗Econsume主要由數(shù)據(jù)發(fā)送、接收和轉(zhuǎn)發(fā)三部分組成，設(shè)節(jié)點(diǎn)發(fā)送一個(gè)數(shù)據(jù)分組所需能量為

[Esen=PsTp=IsVTp] （2）

接收需要消耗的能量為

[Erecv=PrTp=IrVTp] （3）

轉(zhuǎn)發(fā)需要消耗的能量為

[Eforw=（Psend+Precv）Tp] （4）

因此節(jié)點(diǎn)消耗的能量為

[Econsume=Esend+Erecv+（N-1）Eforw] （5）

其中Psend表示節(jié)點(diǎn)發(fā)射功率；Precv為接收功率；Tp表示發(fā)送或接收數(shù)據(jù)時(shí)間；Is為發(fā)送電流；Ir為接收電流，在無(wú)線網(wǎng)絡(luò)環(huán)境下傳輸速率不同的網(wǎng)卡在同等條件下的能量消耗相似，所以取無(wú)線網(wǎng)卡工作電壓為5V，數(shù)據(jù)接收狀態(tài)工作電流Ir=230mA，數(shù)據(jù)發(fā)送狀態(tài)工作電流Is=330mA。

定義1：一條路徑中剩余能量值最小的節(jié)點(diǎn)為該路徑的能量瓶頸節(jié)點(diǎn)，其剩余能量為路徑瓶頸剩余能量（記為Path _bn_RE）

[Path_bn_RE=min（REvi）] （6）

由于移動(dòng)Ad Hoc網(wǎng)絡(luò)是由多個(gè)能量受限的節(jié)點(diǎn)組成，因此應(yīng)選取滿足數(shù)據(jù)包傳輸能量需求的節(jié)點(diǎn)作為中繼節(jié)點(diǎn)。

2.2 節(jié)點(diǎn)運(yùn)動(dòng)模型及鏈路剩余時(shí)間預(yù)測(cè)

定義2：組成路徑的各條鏈路中鏈路剩余時(shí)間最小的鏈路為該路徑的瓶頸鏈路，其鏈路剩余時(shí)間為路徑瓶頸鏈路剩余時(shí)間（記為Path_bn_RLL）。

考慮如圖1所示的網(wǎng)絡(luò)模型：設(shè)節(jié)點(diǎn)S為源節(jié)點(diǎn)，B為目的節(jié)點(diǎn)，A為它們的鄰居節(jié)點(diǎn)，坐標(biāo)分別為（xS，yS）、（xA，yA）、（xB，，yB），速率與方向分別為[vS]、[θS]，[vA]、[θA]，[vB]、[θB]，節(jié)點(diǎn)A要作為S和B節(jié)點(diǎn)的中間節(jié)點(diǎn)，必須滿足：A在S的通信范圍之內(nèi)；B不在S的直接通信范圍之內(nèi)，因此定義SA鏈路的壽命定義為節(jié)點(diǎn)A處于節(jié)點(diǎn)S的傳輸范圍內(nèi)時(shí)間和節(jié)點(diǎn)運(yùn)動(dòng)過(guò)程中距離dAB小于距離dSB的時(shí)間。

圖 1 鏈路剩余時(shí)間預(yù)測(cè)模型

根據(jù)文獻(xiàn)[3]，節(jié)點(diǎn)A處于節(jié)點(diǎn)S通信范圍的時(shí)間預(yù)測(cè)為：

[t*=[-（ab+cd）+（a2+c2）r2-（ad-bc）2]/（a2+c2）]r表示傳輸范圍，[a=vAcosθA-vScosθS] ，[b=xA-xS]，[c=vAsinθA-vSsinθS]，[d=yA-yS]。

另一方面，節(jié)點(diǎn)B作為中間節(jié)點(diǎn)，dSB應(yīng)大于dAB因此鏈路剩余時(shí)間計(jì)算的臨界條件為dSB等于dAB； 設(shè)dSB=dAB的時(shí)刻為t，由文獻(xiàn)[4]得：

[t=[（ag+bh-ce-df）]±e2（a2+b2-d2）+f2（a2+b2-c2）+g2（c2+d2-b2）+h2（c2+d2-a2）+2（cdef+agbh）-（cd+df）（ag+bh）]/（e2+f2-g2-h2）]

其中

[a=xB-xSe=vBcosθB-vAcosθAb=yD-ySf=vBsinθB-vAsinθAc=xB-xAg=vBcosθB-vScosθSd=yB-yAh=vBsinθB-vSsinθS]

因此，鏈路LinkSA的鏈路剩余時(shí)間為：

[RLLSA=min（t*，t）]

因此，路徑的瓶頸鏈路剩余時(shí)間為：

[Path_bn_RLL=min（RLLij）]

其中，RLLij為路徑中的相鄰節(jié)點(diǎn)Vi與Vj之間的鏈路剩余時(shí)間。

2.3 路徑質(zhì)量計(jì)算

定義3：路徑質(zhì)量，用Path_qualityi表示存在的路由中i條路徑的路徑質(zhì)量，Path_bn_REi表示i條路徑的路徑瓶頸剩余能量，Path_bn_RLLi表示第i條路徑的路徑瓶頸剩余鏈路時(shí)間，HopCouti表示第i條路徑的跳數(shù)，則：

[Path_qualityi=（w1×Path_bn_REi+w2×Path_bn_RLLi）/HopCounti]

其中，w1，w2為對(duì)應(yīng)的加權(quán)系數(shù)，其大小體現(xiàn)不同參數(shù)的重要性，且滿足w1+w2=1；加權(quán)系數(shù)的大小可以根據(jù)不同的環(huán)境來(lái)設(shè)定，這樣使得算法更加靈活。

3 PQR-AODV路由協(xié)議

本算法與標(biāo)準(zhǔn)的AODV算法比較，存在以下幾點(diǎn)不同：

1）RREQ包中增加能量需求度量In_node_energy_req、Path_bn_RE以及路徑瓶頸鏈路剩余時(shí)間Path_bn_RLL字段；

2）RREP包中增加一個(gè)1bit標(biāo)志位區(qū)分子路徑修復(fù)通知的RREP與路由發(fā)現(xiàn)應(yīng)答和路徑質(zhì)量字段Path_quality；

3）Hello包中需要增加節(jié)點(diǎn)位置信息字段。

4）增加一個(gè)Notice消息，在路徑修復(fù)過(guò)程中充當(dāng)通知消息。

當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)有通信需求時(shí)，但又沒(méi)有直接可用的路由，源節(jié)點(diǎn)生成路由請(qǐng)求包（RREQ）并廣播該報(bào)文從而開(kāi)始路由發(fā)現(xiàn)過(guò)程，算法描述如下。

1）RREQ處理步驟

第一步：節(jié)點(diǎn)收到RREQ報(bào)文后，首先判斷是否重復(fù)收包，是則丟棄該報(bào)文結(jié)束處理，否則轉(zhuǎn)第二步；

第二步：檢查判斷該節(jié)點(diǎn)是否為目的節(jié)點(diǎn)，是則轉(zhuǎn)第三步，否，則轉(zhuǎn)第四步；

第三步：計(jì)算路徑質(zhì)量并回復(fù)RREP報(bào)文，轉(zhuǎn)第六步；

第四步：判斷節(jié)點(diǎn)記錄的剩余能量REnew是否大于In_node_energy_req，若是，則轉(zhuǎn)到第五步；否，則丟棄RREQ報(bào)文，轉(zhuǎn)第六步；

第五步：判斷節(jié)點(diǎn)記錄的剩余能量是否大于Path_bn_RE，否，則將Path_bn_RE更新為REnew的值；判斷該節(jié)點(diǎn)與上游節(jié)點(diǎn)的鏈路剩余時(shí)間RLL是否大于Path_bn_RLL，否，則將Path_bn_RLL更新為RLL的值。

第六步：結(jié)束。

2）路徑修復(fù)

路由修復(fù)借鑒了蜂窩網(wǎng)絡(luò)中的切換思想，路徑上的節(jié)點(diǎn)實(shí)時(shí)監(jiān)測(cè)剩余能量和鏈路剩余時(shí)間，若低于危險(xiǎn)閥值，發(fā)送Notice消息，通知原節(jié)點(diǎn)建立備份路由；繼續(xù)監(jiān)測(cè)節(jié)點(diǎn)鏈路信息，若低于切換閥值，則認(rèn)為鏈路即將斷裂，切換路由到備份路由，保證數(shù)據(jù)傳輸

4 仿真分析

本文利用NS2[8]對(duì)AODV協(xié)議與改進(jìn)協(xié)議的性能進(jìn)行了比較，仿真場(chǎng)景如下：節(jié)點(diǎn)運(yùn)動(dòng)模型采用Random way’point model ，30個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)分布在800[×]800m2的矩形區(qū)域內(nèi)，節(jié)點(diǎn)分別以（5，10，15，20，25，30）m/s五種速度移動(dòng)，節(jié)點(diǎn)無(wú)線覆蓋范圍為250m，節(jié)點(diǎn)初始能量為250J，仿真時(shí)間為300s，分別對(duì)不同的權(quán)值進(jìn)行模擬，仿真采用固定包速率的流量源，以每秒5個(gè)數(shù)據(jù)包的速率發(fā)送，每個(gè)包的大小為512字節(jié)。

4.1 仿真結(jié)果及分析

本仿真場(chǎng)景主要對(duì)比節(jié)點(diǎn)移動(dòng)狀態(tài)下三種路由協(xié)議的性能，分別對(duì)比丟包率、平均端到端時(shí)延以及控制信息開(kāi)銷(xiāo)三個(gè)方面。

如圖2所示，隨著節(jié)點(diǎn)移動(dòng)速度的增加，兩種協(xié)議包丟失率都相應(yīng)增加。這是由于節(jié)點(diǎn)移動(dòng)速度增大，節(jié)點(diǎn)鏈路斷鏈概率增大，路由斷鏈修復(fù)次數(shù)增多，包丟失率上升。改進(jìn)路由協(xié)議由于加入鏈路質(zhì)量選路機(jī)制且對(duì)路徑修復(fù)機(jī)制進(jìn)行改進(jìn)，在路徑失效前進(jìn)行路由修復(fù)，降低了節(jié)點(diǎn)因能量耗盡而引起的路由失效對(duì)數(shù)據(jù)傳輸?shù)挠绊?，其包丟失率比AODV小。

如圖3，在平均端到端時(shí)延方面，兩種協(xié)議均隨節(jié)點(diǎn)移動(dòng)速度增加而增加，節(jié)點(diǎn)移動(dòng)速度較小時(shí)，改進(jìn)協(xié)議與AODV近似，隨著節(jié)點(diǎn)移動(dòng)速度的增加，改進(jìn)協(xié)議端到端時(shí)延明顯優(yōu)于AODV路由協(xié)議，這是由于節(jié)點(diǎn)移動(dòng)速度增大，改進(jìn)協(xié)議選擇路由可靠性比于AODV高，路徑斷裂概率降低，且采用的路徑修復(fù)策略能進(jìn)一步縮小路徑修復(fù)時(shí)間，從而進(jìn)一步降低端到端時(shí)延。

5 結(jié)束語(yǔ)

由于移動(dòng)Ad hoc網(wǎng)絡(luò)的移動(dòng)性和節(jié)點(diǎn)能量有限傳輸路徑失效導(dǎo)致網(wǎng)絡(luò)性能下降，該文提出基于鏈路質(zhì)量的路由算法。在路由發(fā)現(xiàn)過(guò)程中，通過(guò)考慮節(jié)點(diǎn)剩余能量和鏈路質(zhì)量提高所選路由穩(wěn)定性，并提出基于節(jié)點(diǎn)剩余能量的路由修復(fù)機(jī)制通過(guò)預(yù)測(cè)提前發(fā)起路由修復(fù)，有效防止路由失效所產(chǎn)生的丟包問(wèn)題。仿真結(jié)果表明改進(jìn)后的算法選擇的路徑具有更好的可靠性，降低了平均端到端時(shí)延以及丟包率。

參考文獻(xiàn)：

[1] Toh C-K. Ad hoc mobile wireless networks： protocols and systems[M].New Jersey： Prentice Hall， 2002.

[2] WANG Yu.Collision avoidance in multi-hop Ad hoc networks[C].Proc of the 10th IEEE International Symposium on Modeling Analysis and Simulation of Computer and Telecom unications Systems（MASCOTS’02）.USA：IEEE，2002.

[3] Chen Y，Wang G，Peng S.Link Lifetime-Based Segment-by-Segment Routing Protocol in MANETs[C].International Symposium on Parallel and Distribute Processing with Applications.2008

[4] Hadi Noureddine， Hamed Al-Raweshidy.A New Link Lifetime Prediction Method for Greedy and Contention-based Routing in Mobile Ad Hoc Networks[C].10th IEEE International Conference on Computer and Information Technology，2010.

[5] 陳林星，曾曦，曹毅.移動(dòng)Ad Hoc網(wǎng)絡(luò)--自組織分組無(wú)線網(wǎng)絡(luò)技術(shù)[M].北京：電子工業(yè)出版社，2006：4-1.

[6] 劉元安，唐碧華.Ad Hoc網(wǎng)絡(luò)中的路由算法[M].北京：北京郵電大學(xué)學(xué)報(bào)，2004，27（2）：1-7.

[7] 黃蕾，劉利祥.Ad Hoc網(wǎng)絡(luò)尋路階段的合作激勵(lì)機(jī)制研究[J].計(jì)算機(jī)學(xué)報(bào)，2008，31（2）：262-269.

[8] 徐雷鳴，龐博，趙耀.NS與網(wǎng)絡(luò)仿真[M]北京：人民郵電出版社，2003.