Ad Hoc網絡QoS路由算法仿真研究

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

（中航工業洪都,江西南昌330024）

Ad Hoc網絡QoS路由算法仿真研究

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

（中航工業洪都,江西南昌330024）

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

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

0 引言

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

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

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

1 Ad Hoc網絡QoS多徑路由算法(QMRA)實現

1.1 節點不相交路徑的形成

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

1.2 鏈路質量的度量

1）鏈路生存時間的計算

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

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

2）鏈路質量的度量

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

其中α為鏈路生存周期調節因子，β為路徑剩余能量調節因子，Einitial為節點的初始能量值。鏈路質量越大，就意味著鏈路穩定性越強，鏈路的剩余能量越大。

1.2 路由表結構

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

圖1 QMRA路由表結構

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

1.3 路由發現

當有數據需要發送時，而源節點沒有在生存期內到目的節點的有效路由時，便啟動路由發現過程。QMRA路由發現過程的步驟如下：

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

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

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

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

5）如果中間節點有到目的節點的路由，則發送路由回復分組RREP給源節點。RREP中包含源地址、目的地址、目的序列號、跳數、鏈路質量等字段。中間節點接收到RREP后，根據更新規則，更新路由表的相關信息，RREP經若干中間節點回到源節點。否則，轉發RREQ分組。

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

7）中間節點接收到EERP分組后，根據路由更新規則對路由表進行更新，然后轉發RREP分組。

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

9）釋放分組。

2 仿真分析

2.1 仿真環境

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

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

2)驗證網絡負載對算法性能的影響。

仿真算法：

1)QMRA；

2)AOMDV；

3)AODV。

仿真結果均為10次仿真的平均值。

2.2 仿真結果

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

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

圖2 網絡生命周期

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

圖3 平均端對端延遲

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

圖4 路由發現次數

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

圖5 數據發送成功率

3 結語

本文提出了一種Ad Hoc網絡QoS多徑路由算法QMRA。QMRA采用移動預測模型計算出鏈路的生命周期，應用能量模型實時計算節點的剩余能量，用節點的鏈路生命周期和節點的剩余能量計算出鏈路質量。在發送數據分組時，優先選擇鏈路質量大的路徑。仿真結果表明：QMRA的網絡生命周期、平均端對端延遲、數據發送成功率和路由發現次數四種指標明顯優于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網絡中基于穩定性的QoS路由算法綜述[J].計算機工程與應用,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年畢業于南京航空航天大學，工程師，現主要從事項目工程工作。

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）