周盛，趙煥義，趙文婷，周平平，李蕓

（中航工業(yè)洪都,江西南昌330024）

Ad Hoc網(wǎng)絡(luò)QoS路由算法仿真研究

周盛，趙煥義，趙文婷，周平平，李蕓

（中航工業(yè)洪都,江西南昌330024）

服務(wù)質(zhì)量保障(QoS)是設(shè)計Ad Hoc網(wǎng)絡(luò)的必備環(huán)節(jié)，QoS路由算法對于Ad Hoc網(wǎng)絡(luò)有重要意義。本文提出了一種Ad Hoc網(wǎng)絡(luò)QoS多徑按需路由算法QMRA，該算法采用移動預(yù)測計算鏈路的生存時間，應(yīng)用能量模型獲得鏈路的剩余能量，然后綜合鏈路生存時間和剩余能量兩種因素來計算鏈路質(zhì)量，并選擇鏈路質(zhì)量大的路徑轉(zhuǎn)發(fā)分組。仿真結(jié)果表明：與AOMDV算法相比，QMRA算法提高了網(wǎng)絡(luò)的生命周期與數(shù)據(jù)發(fā)送成功率，降低了網(wǎng)絡(luò)的平均端對端延遲。

國際地磁參考場；路由算法

0 引言

自組織網(wǎng)絡(luò)是由一組帶有無線收發(fā)裝置移動節(jié)點組成的多跳的臨時性自治系統(tǒng)[1,2]，具有多跳路由、網(wǎng)絡(luò)拓撲變化頻繁的特點。服務(wù)質(zhì)量保障(QoS)可以定義為網(wǎng)絡(luò)中從源節(jié)點到目的節(jié)點傳輸數(shù)據(jù)需要滿足的需求集[3,4]。在Ad Hoc中提供QoS支持將面臨許多問題和挑戰(zhàn)：無線信道的復(fù)雜性和隨機性、終端節(jié)點的移動性、共享的無線信道之間的干擾等等。Ad Hoc網(wǎng)絡(luò)中QoS支持包括QoS模型、QoS資源保留信令、QoS介質(zhì)訪問控制和QoS路由算法[5-7]。

QoS路由算法在實現(xiàn)QoS保證中具有很重要的作用。QoS-AODV[8]算法是一種典型的按需QoS路由算法。為了支持QoS路由，QoS-AODV對AODV的路由表結(jié)構(gòu)、路由請求和路由回復(fù)分組進行了更改。在路由表項中，增加了最大延遲、最小可用帶寬、源節(jié)點要求延遲保證列表、源節(jié)點要求帶寬保證列表四個字段。QoS-AODV的優(yōu)點是通過對AODV算法的擴展，實現(xiàn)了對QoS的支持。但是，由于在源節(jié)點到目的節(jié)點的路徑上沒有資源預(yù)留，QoS-AODV并不適合要求硬性QoS的應(yīng)用。MCP QoS(Multi-Constrained Path QoS routing)[9]算法是一種典型的表驅(qū)動QoS路由算法，它是在OLSR算法的基礎(chǔ)上實現(xiàn)的。MCP QoS routing采用非線性開銷函數(shù)，對路徑進行評價。開銷函數(shù)是由多個加性QoS參數(shù)組成的。核心提取分布式QoS路由算法CEDAR[10]是一種典型QoS混合路由算法。CEDAR算法主要包含3個部分：核心提取、鏈路狀態(tài)傳播和路由計算。CEDAR的優(yōu)點是減少了QoS路由算法的開銷。但其缺點是網(wǎng)絡(luò)核心的建立和維護算法比較復(fù)雜，僅適用于中小規(guī)模的移動Ad Hoc網(wǎng)絡(luò)。

本文提出了一種QoS多徑路由算法QMRA。QMRA采用移動預(yù)測的方法評價鏈路生命周期，應(yīng)用能量模型均衡節(jié)點的能量消耗，綜合鏈路生存周期和能量兩種因素對鏈路質(zhì)量進行評價。對于路由，選擇鏈路質(zhì)量高的路徑進行通信，可以減少鏈路斷開的概率，均衡網(wǎng)絡(luò)中的能量消耗，延長網(wǎng)絡(luò)生命周期。仿真結(jié)果表明：QMRA在路由發(fā)現(xiàn)頻率、平均端對端延遲和數(shù)據(jù)發(fā)送成功率等方面優(yōu)于AOMDV算法。

1 Ad Hoc網(wǎng)絡(luò)QoS多徑路由算法(QMRA)實現(xiàn)

1.1 節(jié)點不相交路徑的形成

QMRA路由發(fā)現(xiàn)過程中，為確保建立的多條路徑節(jié)點不相交，節(jié)點仍然只轉(zhuǎn)發(fā)第一次收到的RREQ，并在RREQ增加一個firsthop值，記錄直接從源節(jié)點S收到RREQ的一跳鄰居節(jié)點的ID，也就是建立的正向路徑中的第一跳節(jié)點，同時每個節(jié)點也將每個RREQ的firsthop保存在本節(jié)點。由于算法設(shè)定中間節(jié)點只轉(zhuǎn)發(fā)第一次收到的RREQ，因而節(jié)點I只能形成一條節(jié)點不相交路徑，而不是兩條鏈路不相交路徑。

1.2 鏈路質(zhì)量的度量

1）鏈路生存時間的計算

設(shè)一個源節(jié)點S和目的節(jié)點D之間的m條不相交路徑集p=(p1,p2,…，pm)，路徑pi=(li1,li2,…,lm)存在n段鏈路。設(shè)節(jié)點通過GPS裝置獲得移動節(jié)點的位置、運動速度和運動方向，對節(jié)點i和j之間的鏈路lij的生存時間進行預(yù)測[32]：

式中a=vicosθi-vjcosθj，b=xi-xj，c=visinθj-vjsinθj，d= yi-yj，vi、vj分別為相鄰節(jié)點i、j的移動速度，θi、θj(0≤ θi,θj＜2π)為相鄰節(jié)點i、j的移動方向，(xi,yi)和(xj,yj)分別為相鄰節(jié)點i、j的坐標(biāo)，r為節(jié)點的傳輸半徑。

2）鏈路質(zhì)量的度量

QMRA綜合考慮鏈路生存時間和能量兩種因素，得出節(jié)點i和j之間的鏈路lij的鏈路質(zhì)量為：

其中α為鏈路生存周期調(diào)節(jié)因子，β為路徑剩余能量調(diào)節(jié)因子，Einitial為節(jié)點的初始能量值。鏈路質(zhì)量越大，就意味著鏈路穩(wěn)定性越強，鏈路的剩余能量越大。

1.2 路由表結(jié)構(gòu)

QMRA要求節(jié)點維護一個路由表和一個鄰居列表，鄰居列表中存儲鄰居節(jié)點地址和有效期。路由表的結(jié)構(gòu)如圖1所示。

圖1 QMRA路由表結(jié)構(gòu)

路由表中包含：目的地址、序列號、廣播跳數(shù)、廣播鏈路質(zhì)量和路由列表五個字段。路由列表中存儲到目的節(jié)點的若干條路徑，每條路徑包含：第一跳地址、倒數(shù)第一跳地址、到目的節(jié)點的跳數(shù)、到目的節(jié)點的鏈路質(zhì)量和有效期五個字段。

1.3 路由發(fā)現(xiàn)

當(dāng)有數(shù)據(jù)需要發(fā)送時，而源節(jié)點沒有在生存期內(nèi)到目的節(jié)點的有效路由時，便啟動路由發(fā)現(xiàn)過程。QMRA路由發(fā)現(xiàn)過程的步驟如下：

1）源節(jié)點向鄰居節(jié)點發(fā)送一個路由請求分組RREQ。其中RREQ分組的各個域的信息為：源節(jié)點ID、廣播ID、第一跳地址、x坐標(biāo)、y坐標(biāo)、節(jié)點的移動速度、節(jié)點的移動方向和鏈路質(zhì)量等字段。源節(jié)點在發(fā)送RREQ前，將自己的x，y坐標(biāo)和速度值，節(jié)點的移動方向，添加到路由請求分組中，PQ值初始化為0。

2）中間節(jié)點收到(源節(jié)點ID，廣播ID)相同的RREQ分組，轉(zhuǎn)步驟9。如果中間節(jié)點是源節(jié)點的鄰居節(jié)點，根據(jù)式(1)計算出與發(fā)送節(jié)點的鏈路生存時間Tl，根據(jù)能量模型式(2)，計算出節(jié)點的剩余能量，將計算出的鏈路質(zhì)量值和自己的IP地址添加到RREQ中，轉(zhuǎn)發(fā)分組。否則，轉(zhuǎn)步驟3。

3）根據(jù)式(1)計算出與發(fā)送節(jié)點的鏈路生存時間Tl。根據(jù)公式(2)計算鏈路質(zhì)量，并將計算出的鏈路質(zhì)量值和RREQ中的鏈路質(zhì)量值比較，取較小的值添加到路由表中，轉(zhuǎn)步驟4。

4）中間節(jié)點查詢自己的反向路由表中是否有到源節(jié)點的路由，如果有并且滿足路由更新條件，就根據(jù)更新規(guī)則，更新路由。如果沒有，就在路由表中添加到源節(jié)點的路徑，將跳數(shù)信息和鏈路質(zhì)量信息添加到路由表中。

5）如果中間節(jié)點有到目的節(jié)點的路由，則發(fā)送路由回復(fù)分組RREP給源節(jié)點。RREP中包含源地址、目的地址、目的序列號、跳數(shù)、鏈路質(zhì)量等字段。中間節(jié)點接收到RREP后，根據(jù)更新規(guī)則，更新路由表的相關(guān)信息，RREP經(jīng)若干中間節(jié)點回到源節(jié)點。否則，轉(zhuǎn)發(fā)RREQ分組。

6）目的節(jié)點接收到RREQ分組后，對(源節(jié)點ID，廣播ID)不同的RREQ分組進行路由回復(fù)。對于(源節(jié)點ID，廣播ID)相同的分組，但是分組中第一跳節(jié)點地址不同的節(jié)點予以回復(fù)，以便形成節(jié)點不相交的多路徑。

7）中間節(jié)點接收到EERP分組后，根據(jù)路由更新規(guī)則對路由表進行更新，然后轉(zhuǎn)發(fā)RREP分組。

8）源節(jié)點接收到路由回復(fù)分組后，延遲一段時間，以便接收到來自多個不相交路徑的RREP分組，并在其中選擇鏈路質(zhì)量最大的路徑進行數(shù)據(jù)分組的傳輸，同時將其他的路由作為備用路徑，當(dāng)所有到目的節(jié)點的路由斷開或是失效后，源節(jié)點重啟路由發(fā)現(xiàn)過程。

9）釋放分組。

2 仿真分析

2.1 仿真環(huán)境

仿真環(huán)境是帶有CMU無線擴展的NS-2(Version 2.31)，仿真場景為1500m×1500m，節(jié)點的無線傳輸半徑為250m，網(wǎng)絡(luò)帶寬為2Mbit/s。α和β均取值為1。仿真分兩組進行：

1)驗證節(jié)點移動速度對算法性能的影響；

2)驗證網(wǎng)絡(luò)負載對算法性能的影響。

仿真算法：

1)QMRA；

2)AOMDV；

3)AODV。

仿真結(jié)果均為10次仿真的平均值。

2.2 仿真結(jié)果

仿真方法：改變網(wǎng)絡(luò)中節(jié)點的平均移動速度大小，得到性能隨節(jié)點的平均移動速度變化的情況。網(wǎng)絡(luò)總節(jié)點的數(shù)量為100，仿真場景為1000m×1000m。網(wǎng)絡(luò)中連接數(shù)為50，源節(jié)點的分組發(fā)送速率為1分組/秒。仿真時間為200s。通過改變節(jié)點平均移動速度來改變節(jié)點的移動速度，節(jié)點實際的移動速度在[v-1,v+1]均勻分布。仿真過程中，節(jié)點的平均移動速度在2-10m/s范圍內(nèi)變化。圖2～圖5顯示了QMRA、AOMDV和AODV三種算法的性能隨節(jié)點的平均移動速度變化的情況。

圖2顯示了三種算法的網(wǎng)絡(luò)生命周期隨節(jié)點的平均移動速度變化的情況。從圖中可以看出，三種算法的網(wǎng)絡(luò)生命周期隨節(jié)點的平均移動速變化不大，QMRA的網(wǎng)絡(luò)生命周期明顯高于AOMDV和AODV，原因是QMRA在路由選擇方面，選擇能量大的路徑進行數(shù)據(jù)分組的傳輸，均衡了網(wǎng)絡(luò)的能量消耗。相比AOMDV算法和AODV算法，QMRA的網(wǎng)絡(luò)生命周期分別提高了0.96%和0.98%。

圖2 網(wǎng)絡(luò)生命周期

圖3顯示了三種算法的平均端對端延遲隨節(jié)點的平均移動速度變化的情況。從圖中可以看出，三種算法的平均端對端延遲隨節(jié)點的平均移動速度增加而增加。當(dāng)網(wǎng)絡(luò)中節(jié)點移動速度增加時，鏈路斷開的概率開始增加，鏈路的穩(wěn)定性降低，因而導(dǎo)致節(jié)點重啟路由發(fā)現(xiàn)的數(shù)量增加，延遲時間開始增加。QMRA的平均端對端延遲明顯低于AOMDV和AODV，原因是QMRA選擇路徑生存時間長的路徑進行數(shù)據(jù)分組的傳輸，降低了鏈路斷開的概率，減少了路由重啟的次數(shù)。相比AOMDV算法和AODV算法，QMRA的平均端對端延遲分別平均降低了47%和68%。

圖3 平均端對端延遲

圖4顯示了三種算法的路由發(fā)現(xiàn)次數(shù)隨節(jié)點的平均移動速度變化的情況。從圖中可以看出，三種算法的路由發(fā)現(xiàn)次數(shù)隨節(jié)點的平均移動速度增加而增加。當(dāng)網(wǎng)絡(luò)中節(jié)點移動速度增加時，鏈路斷開的概率開始增加，因而導(dǎo)致節(jié)點重啟路由發(fā)現(xiàn)的數(shù)量增加。QMRA的路由發(fā)現(xiàn)次數(shù)明顯低于AOMDV和AODV，原因是QMRA選擇路徑生存時間長的路徑進行數(shù)據(jù)分組的傳輸，降低了鏈路斷開的概率，減少了路由重啟的次數(shù)。相比AOMDV算法和AODV算法，QMRA的路由發(fā)現(xiàn)次數(shù)分別平均降低了14%和38%。

圖4 路由發(fā)現(xiàn)次數(shù)

圖5顯示了三種算法的數(shù)據(jù)發(fā)送成功率隨節(jié)點的平均移動速度變化的情況。從圖中可以看出，三種算法的數(shù)據(jù)發(fā)送成功率隨節(jié)點的平均移動速度增加而減少。當(dāng)網(wǎng)絡(luò)中節(jié)點移動速度增加時，鏈路斷開的概率開始增加，導(dǎo)致被丟棄的分組數(shù)量增加。QMRA的數(shù)據(jù)發(fā)送成功率明顯高于AOMDV和AODV，原因是QMRA選擇穩(wěn)定路徑進行通信，減少了因鏈路斷開而丟棄的分組的數(shù)量。相比AOMDV算法和AODV算法，QMRA的數(shù)據(jù)發(fā)送成功率分別平均提高了4%和5%。

圖5 數(shù)據(jù)發(fā)送成功率

3 結(jié)語

本文提出了一種Ad Hoc網(wǎng)絡(luò)QoS多徑路由算法QMRA。QMRA采用移動預(yù)測模型計算出鏈路的生命周期，應(yīng)用能量模型實時計算節(jié)點的剩余能量，用節(jié)點的鏈路生命周期和節(jié)點的剩余能量計算出鏈路質(zhì)量。在發(fā)送數(shù)據(jù)分組時，優(yōu)先選擇鏈路質(zhì)量大的路徑。仿真結(jié)果表明：QMRA的網(wǎng)絡(luò)生命周期、平均端對端延遲、數(shù)據(jù)發(fā)送成功率和路由發(fā)現(xiàn)次數(shù)四種指標(biāo)明顯優(yōu)于AOMDV算法。

[1]Wu K.,Harms J.QoS support in mobile ad hoc networks[J].Crossing Boundaries-the GSA Journal of University of Alberta,2001,1(1):92-106.

[2]Liao W.H.,Wang S.L.,Sheu J.P.,et al.A multi-path QoS routing protocol in a wireless mobile ad hoc network[J].Networking??ICN 2001,2001:158-167.

[3]張暉,董育寧,楊龍祥.移動Ad hoc網(wǎng)絡(luò)中基于穩(wěn)定性的QoS路由算法綜述[J].計算機工程與應(yīng)用,2009,45(1):1-6.

[5]ZhangB.,MouftahH.T.QoSroutingfor wireless ad hoc networks:problems,algorithms,and protocols[J].Communications Magazine,IEEE,2005, 43(10):110-117.

[6]Chakrabarti S.,Mishra A.QoS issues in ad hoc wireless networks[J].Communications Magazine,IEEE, 2001,39(2):142-148.

[7]Reddy T.Bheemarjuna,Karthigeyan I.,Manoj B.S.,et al.Quality of service provisioning in ad hoc wireless networks:a survey of issues and solutions[J]. Ad Hoc Networks,2006,4(1):83-124.

[8]Ad M.,Royer E.M.,Perkins C.E.,et al.Quality of Service for Ad hoc On-Demand Distance Vector Routing[J].2000.

[9]Kunavut K.,Sanguankotchakorn T.Multi-Constrained Path(MCP)QoS routing in OLSR based on multiple additive QoS metrics[C].//Proceedings of the Communications and Information Technologies(ISCIT), 2010 International Symposium on.2010:226-231.

[10]SinhaP.,SivakumarR.,BharghavanV. CEDAR:a core-extraction distributed ad hoc routing algorithm[C].//Proceedings of the INFOCOM'99. Eighteenth Annual Joint Conference of the IEEE ComputerandCommunicationsSocieties.Proceedings. IEEE.1999:202-209 vol.1.

>>>作者簡介

周盛，男，1980年11月出生，2002年畢業(yè)于南京航空航天大學(xué)，工程師，現(xiàn)主要從事項目工程工作。

Simulation Research on QoS Routing Algorithm Under Ad Hoc Network

Zhou Sheng,Zhao Huanyi,Zhao Wenting,Zhou Pingping,Li Yun
(AVIC Hongdu Aviation Industry Group,Nanchang,Jiangxi,330024)

QoS is an essential procedure for Ad Hoc network design and QoS routing algorithm is important to Ad Hoc network.The paper puts forward QoS multipath routing algorithm QMRA under Ad Hoc network.The algorithm calculates survival time of link by movement forecasting and applies energy module to get remaining energy of link. Then it calculates link mass by integrating two factors:link survival time and remaining energy,and selects the path with greater mass in link to transmit it to the sub-group.The simulation result shows that QMRA algorithm can increase the life cycle of network and effective data transmission rate,and decrease the average end-to-end delay of network when compared with AOMDV.

international geomagnetic reference field(IGRF);routing algorithm

2016-04-16）