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

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

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

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

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

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

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

國(guó)際地磁參考場(chǎng)；路由算法

0 引言

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

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

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

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

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

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

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

1）鏈路生存時(shí)間的計(jì)算

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

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

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

QMRA綜合考慮鏈路生存時(shí)間和能量?jī)煞N因素，得出節(jié)點(diǎn)i和j之間的鏈路lij的鏈路質(zhì)量為：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

9）釋放分組。

2 仿真分析

2.1 仿真環(huán)境

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

1)驗(yàn)證節(jié)點(diǎn)移動(dòng)速度對(duì)算法性能的影響；

2)驗(yàn)證網(wǎng)絡(luò)負(fù)載對(duì)算法性能的影響。

仿真算法：

1)QMRA；

2)AOMDV；

3)AODV。

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

2.2 仿真結(jié)果

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

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

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

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

圖3 平均端對(duì)端延遲

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

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

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

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

3 結(jié)語(yǔ)

本文提出了一種Ad Hoc網(wǎng)絡(luò)QoS多徑路由算法QMRA。QMRA采用移動(dòng)預(yù)測(cè)模型計(jì)算出鏈路的生命周期，應(yīng)用能量模型實(shí)時(shí)計(jì)算節(jié)點(diǎn)的剩余能量，用節(jié)點(diǎn)的鏈路生命周期和節(jié)點(diǎn)的剩余能量計(jì)算出鏈路質(zhì)量。在發(fā)送數(shù)據(jù)分組時(shí)，優(yōu)先選擇鏈路質(zhì)量大的路徑。仿真結(jié)果表明：QMRA的網(wǎng)絡(luò)生命周期、平均端對(duì)端延遲、數(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]張暉,董育寧,楊龍祥.移動(dòng)Ad hoc網(wǎng)絡(luò)中基于穩(wěn)定性的QoS路由算法綜述[J].計(jì)算機(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.

>>>作者簡(jiǎn)介

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

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）