一種改進(jìn)的移動(dòng)自組織網(wǎng)多路徑路由協(xié)議
2016-12-16 11:10:04李旭仇頌清彭進(jìn)霖王聰
兵工學(xué)報(bào) 2016年11期
李旭， 仇頌清， 彭進(jìn)霖， 王聰
(1.北京交通大學(xué) 電子信息工程學(xué)院, 北京 100044; 2.北京跟蹤與通信技術(shù)研究所, 北京 100092)
?
一種改進(jìn)的移動(dòng)自組織網(wǎng)多路徑路由協(xié)議
李旭1， 仇頌清1， 彭進(jìn)霖2， 王聰1
(1.北京交通大學(xué) 電子信息工程學(xué)院, 北京 100044; 2.北京跟蹤與通信技術(shù)研究所, 北京 100092)
在移動(dòng)自組網(wǎng)中，相比于單路徑路由協(xié)議，多路徑路由協(xié)議通過(guò)建立和維護(hù)多條備用路徑，可以有效地減小通信中斷的概率，降低端到端的時(shí)延。然而，目前對(duì)備用路徑數(shù)目的分析方法不適合于復(fù)雜多變的無(wú)線自組網(wǎng)絡(luò)傳輸環(huán)境，而且現(xiàn)有多路徑路由協(xié)議難以滿足混合業(yè)務(wù)中不同業(yè)務(wù)對(duì)傳輸質(zhì)量的不同要求。為解決上述問(wèn)題，對(duì)單路徑與多路徑路由協(xié)議進(jìn)行建模研究，分析維護(hù)備用路徑數(shù)目參量對(duì)多路徑路由協(xié)議性能的影響；基于此建模分析的結(jié)論，提出一種面向業(yè)務(wù)的多路徑路由協(xié)議，根據(jù)不同業(yè)務(wù)的服務(wù)質(zhì)量(QoS)需求，綜合考慮跳數(shù)、平均連接度、最小帶寬等參數(shù)，選擇針對(duì)本業(yè)務(wù)QoS需求的最優(yōu)路徑。仿真結(jié)果表明，調(diào)整權(quán)值系數(shù)，數(shù)據(jù)類(lèi)業(yè)務(wù)的投遞率最多可提高25%，語(yǔ)音類(lèi)業(yè)務(wù)的平均時(shí)延可減少10%～20%，證明該協(xié)議針對(duì)不同業(yè)務(wù)能選擇性地帶來(lái)時(shí)延、可靠性、可用帶寬等性能的提升。
計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)； 移動(dòng)自組網(wǎng)； 多路徑路由協(xié)議； 多路徑路由協(xié)議； 服務(wù)質(zhì)量
0 引言
在移動(dòng)自組網(wǎng)中，由于節(jié)點(diǎn)移動(dòng)速度較快、網(wǎng)絡(luò)拓?fù)渥兓瘎×?、傳輸環(huán)境干擾較大等原因，通信鏈路中斷的概率較大。如果使用單路徑路由協(xié)議在鏈路每次發(fā)生中斷時(shí)重新尋路，則會(huì)由于多次尋路而帶來(lái)較大時(shí)延，嚴(yán)重影響通信質(zhì)量。使用多路徑路由協(xié)議能有效地解決這個(gè)問(wèn)題，減小復(fù)雜的無(wú)線環(huán)境對(duì)數(shù)據(jù)傳輸造成的影響。多路徑路由協(xié)議在尋路過(guò)程中建立多條路徑，在信息傳輸過(guò)程中可以選擇其中的一條或者多條路徑傳輸數(shù)據(jù)，是基于單路徑路由協(xié)議的擴(kuò)展。當(dāng)一條路徑發(fā)生中斷時(shí)，數(shù)據(jù)可以通過(guò)其他的備用路徑進(jìn)行傳輸，從而有效減小信息傳輸中斷的概率，同時(shí)避免由于單一路徑中斷造成的多次尋路過(guò)程，有效降低端到端時(shí)延。
現(xiàn)有的多路徑路由協(xié)議包括按需多徑距離矢量路由(AOMDV)[1]、多徑源路由(MSR)[2]、按需距離矢量備份路由(AODV-BR)[3]、分裂多徑路由(SMR)[4]、緩存多徑路由(CHAMP)[5]等。其中，AOMDV協(xié)議是一種較為完善的多路徑路由協(xié)議，其主要思想是在路由發(fā)現(xiàn)過(guò)程中建立和維護(hù)多條路徑，并選擇其中一條作為通信的主路徑，其余的則作為備用路徑，在傳輸數(shù)據(jù)時(shí)，如果主路徑發(fā)生故障，可啟用備用路徑進(jìn)行通信。
AOMDV等多路徑路由協(xié)議可以有效地降低端到端時(shí)延，提高通信服務(wù)質(zhì)量。但目前對(duì)多路徑路由協(xié)議的研究存在許多不足。備用路徑數(shù)目、環(huán)境節(jié)點(diǎn)密度、發(fā)包速率、包長(zhǎng)度等參量對(duì)協(xié)議的性能有著重要的影響，特別是維護(hù)備用路徑的數(shù)目，極大程度上制約著多路徑路由協(xié)議的性能改進(jìn)情況，影響了多路徑路由協(xié)議的適用場(chǎng)景。然而，目前缺乏對(duì)于備用路徑數(shù)目參量的有效判斷機(jī)制，美國(guó)Pham等[6]此前通過(guò)簡(jiǎn)化條件，從分析兩次尋路時(shí)間間隔的角度出發(fā)探討多路徑的最優(yōu)路徑數(shù)目。然而該方法主要基于傳輸環(huán)境比較穩(wěn)定、干擾較小的情況進(jìn)行分析，未能體現(xiàn)出多路徑路由協(xié)議的優(yōu)勢(shì)，也不適合傳輸環(huán)境多變的移動(dòng)自組網(wǎng)絡(luò)。
目前AOMDV等多路徑路由協(xié)議將路徑跳數(shù)作為尋路和選路的主要判斷依據(jù)，難以滿足移動(dòng)自組網(wǎng)中混合業(yè)務(wù)傳輸?shù)姆?wù)質(zhì)量(QoS)需求。然而，隨著傳輸業(yè)務(wù)的多樣化，如何滿足業(yè)務(wù)的傳輸需求成為路由協(xié)議改進(jìn)的一個(gè)重要方向。業(yè)務(wù)的QoS需求指標(biāo)大體可分為時(shí)延、可靠性、帶寬、能量等方面。對(duì)于單路徑路由，目前已經(jīng)提出多種針對(duì)業(yè)務(wù)QoS需求的路由協(xié)議。文獻(xiàn)[7]提出基于時(shí)延約束的QoS路由，應(yīng)用于語(yǔ)音、視頻等對(duì)時(shí)延敏感的業(yè)務(wù)，主要方法是用定時(shí)器記錄探測(cè)包的累積時(shí)延，然后選取滿足時(shí)延要求的路由。文獻(xiàn)[8]提出基于帶寬約束的QoS路由，應(yīng)用于對(duì)帶寬要求較嚴(yán)的業(yè)務(wù)，協(xié)議在建立路由時(shí)充分考慮節(jié)點(diǎn)的帶寬信息，選擇有效帶寬較大的節(jié)點(diǎn)建立路由，以滿足業(yè)務(wù)的帶寬需求。然而上述面向業(yè)務(wù)需求的QoS路由是基于單路徑路由協(xié)議提出的，并未涉及多路徑路由。文獻(xiàn)[9]在傳統(tǒng)AODV協(xié)議的基礎(chǔ)上根據(jù)負(fù)載情況和跳數(shù)擴(kuò)展多路徑，文獻(xiàn)[10]則綜合考慮網(wǎng)絡(luò)負(fù)載和干擾因素對(duì)AOMDV協(xié)議進(jìn)行改進(jìn)，都達(dá)到了降低平均開(kāi)銷(xiāo)和平均丟包率的目的，但依舊無(wú)法針對(duì)業(yè)務(wù)的特性作適合具體業(yè)務(wù)的路由選擇。
針對(duì)上述問(wèn)題，本文首先對(duì)單路徑路由協(xié)議AODV與多路徑路由協(xié)議AOMDV的性能進(jìn)行建模，分析維護(hù)備用路徑的數(shù)目對(duì)協(xié)議性能的影響；然后利用該建模分析的結(jié)論，基于AOMDV協(xié)議提出一種面向業(yè)務(wù)的多路徑路由協(xié)議(A-AOMDV)，綜合考慮時(shí)延、帶寬、連接度等多個(gè)參數(shù)的影響，建立和選擇適合于不同業(yè)務(wù)QoS需求的最優(yōu)路徑，以滿足不同業(yè)務(wù)的需求。
1 單路徑與多路徑路由協(xié)議的建模分析
根據(jù)相交性，多路徑路由可分為3種方式：節(jié)點(diǎn)分離、鏈路分離和相交。節(jié)點(diǎn)分離多路徑，是指各條路徑除源節(jié)點(diǎn)和目的節(jié)點(diǎn)之外沒(méi)有其他共用節(jié)點(diǎn)。鏈路分離多路徑是指各條路徑?jīng)]有共用的鏈路，但可能共用節(jié)點(diǎn)。相交多路徑是指各條路徑間既可能共用節(jié)點(diǎn)，又可能共用鏈路。本文討論的AOMDV和A-AOMDV均為節(jié)點(diǎn)分離多路徑協(xié)議。
本節(jié)分別建立單路徑路由協(xié)議AODV和多路徑路由協(xié)議AOMDV的端到端傳輸時(shí)延模型，分析維護(hù)備用路徑數(shù)目對(duì)多路徑路由協(xié)議性能的影響。
在建模過(guò)程中進(jìn)行如下假設(shè)：
1)一條端到端的k跳路徑由k段點(diǎn)到點(diǎn)的鏈路構(gòu)成，每段鏈路的中斷概率滿足獨(dú)立同分布，設(shè)中斷概率為p，則每段鏈路有效的概率為q=1-p. 只有路徑的所有鏈路都有效才能確保路徑有效，那么該路徑有效的概率為qk；
2)設(shè)每段鏈路的傳輸時(shí)延為T(mén)1，則該路徑的端到端傳輸時(shí)延Tk滿足Tk=kT1；
3)設(shè)多路徑路由協(xié)議首選路徑跳數(shù)為m，備用路徑按路由表順序排列，跳數(shù)分別為k2,k3,…,km，所有路徑失效后重新尋路得到的路徑跳數(shù)為h. 由于傳輸時(shí)延與路徑跳數(shù)呈正比關(guān)系，應(yīng)優(yōu)先維護(hù)跳數(shù)較少的路由，滿足k1≤k2≤k3≤…≤km≤h.
4)新路徑的端到端傳輸時(shí)延Th滿足Th=hT1. 尋路過(guò)程通過(guò)源節(jié)點(diǎn)向目的節(jié)點(diǎn)發(fā)送路由請(qǐng)求(RREQ)分組并獲取路徑上節(jié)點(diǎn)回復(fù)的路由應(yīng)答(RREP)分組來(lái)實(shí)現(xiàn)路由更新，路徑的最遠(yuǎn)節(jié)點(diǎn)即為目的節(jié)點(diǎn)，所以尋路時(shí)間為RREQ分組從源節(jié)點(diǎn)到達(dá)目的節(jié)點(diǎn)和RREP分組從目的節(jié)點(diǎn)到達(dá)源節(jié)點(diǎn)的時(shí)間總和。令s為尋路過(guò)程中RREQ和RREP分組傳遞的總跳數(shù)，則s=2h，尋找新路徑用時(shí)Ts=2Th.
下面分別考慮單路徑路由協(xié)議和多路徑路由協(xié)議的端到端傳輸時(shí)延：
對(duì)于單路徑路由協(xié)議，端到端的傳輸時(shí)延包含兩部分：一部分是首選k1跳路徑有效時(shí)的傳輸時(shí)延；另一部分是該條路徑失效時(shí)，尋路找到h跳新路徑并用該路徑傳輸數(shù)據(jù)的時(shí)延(Ts+Th)。則單路徑路由協(xié)議端到端傳輸時(shí)延平均值Tu表達(dá)式為
Tu=qk1Tk1+(1-qk1)(Ts+Th),
將Tk1=k1T1，Th=hT1和Ts=2Th代入，得
Tu=qk1k1T1+3(1-qk1)hT1.
(1)
對(duì)多路徑路由協(xié)議，端到端傳輸時(shí)延Tm由3部分構(gòu)成，第1部分TA是之前維護(hù)的首選k1跳路徑有效時(shí)的傳輸時(shí)延，其路徑有效的概率為qk1，則
TA=qk1Tk1=qk1k1T1.
(2)
第2部分TBm是當(dāng)該首選路徑失效時(shí)，利用其他多條備用路徑傳輸?shù)臅r(shí)延，則
TBm=(1-qk1)qk2Tk2+(1-qk1)(1-qk2)qk3Tk3+…+
(1-qk1)(1-qk2)…(1-qkm-1)qkmTkm=
(3)
第3部分TCm是所有維護(hù)路徑都失效時(shí)尋路找到h跳新路徑并用該路徑傳輸數(shù)據(jù)的時(shí)延，大小為(Ts+Th)，概率為(1-qk1)(1-qk2)…(1-qkm). 則
TCm=(1-qk1)(1-qk2)…(1-qkm)(Ts+Th)+
(4)
綜上，多路徑路由協(xié)議端到端時(shí)延為T(mén)m=TA+TBm+TCm，將TA、TBm、TCm代入得
(5)
單路徑和多路徑路由協(xié)議的端到端時(shí)延差值為
σm=Tu-Tm.
(6)
下面根據(jù)增加維護(hù)路徑對(duì)傳輸時(shí)延改善的程度來(lái)討論m的合適取值，將維護(hù)路徑數(shù)量從m-1增加到m，改善的時(shí)延差Δm=σm-σm-1，將(1)式、(5)式、(6)式代入，得
Δm=Tm-1-Tm=
(7)
現(xiàn)用Δm與單路徑路由協(xié)議端到端時(shí)延Tu的比值ηm來(lái)表征改善程度，即
ηm=Δm/Tu=
(8)
按照假設(shè)3隨機(jī)構(gòu)建1 000組不同的正整數(shù)序列(k1,k2,k3,…,km,h),并選取不同的中斷概率p對(duì)η進(jìn)行仿真，并對(duì)1 000組結(jié)果取平均值，得到η與m和p的關(guān)系如圖1所示。
圖1 中斷概率和維護(hù)路徑數(shù)目對(duì)傳輸時(shí)延改善的影響Fig.1 Effects of outage probability and the number of maintenance paths on the improvement of transmission delay
從圖1中可看出，對(duì)于合理的中斷概率條件0
2 面向業(yè)務(wù)的多路徑路由協(xié)議
2.1 業(yè)務(wù)的QoS需求
業(yè)務(wù)的QoS需求指標(biāo)包括時(shí)延、可靠性(丟包率)、帶寬等多個(gè)方面。3GPP[11]在TS22.105規(guī)范中從業(yè)務(wù)的QoS角度出發(fā)，將移動(dòng)網(wǎng)絡(luò)業(yè)務(wù)分為4大類(lèi)，即會(huì)話類(lèi)、流媒體類(lèi)、交互類(lèi)和后臺(tái)類(lèi)。每一類(lèi)業(yè)務(wù)又包括音頻、視頻、數(shù)據(jù)等若干子類(lèi)。不同類(lèi)型的業(yè)務(wù)具有不同的QoS需求，如話音、可視電話等會(huì)話類(lèi)業(yè)務(wù)對(duì)時(shí)延敏感，要求時(shí)延控制在250 ms內(nèi)，而對(duì)可靠性要求較低；數(shù)據(jù)類(lèi)業(yè)務(wù)則對(duì)可靠性要求嚴(yán)格，需要較低的丟包率，而對(duì)時(shí)延則沒(méi)有嚴(yán)格的要求。表1列出了一些主要應(yīng)用的業(yè)務(wù)特征及QoS需求。
表1 主要應(yīng)用的業(yè)務(wù)特征及QoS需求
2.2 協(xié)議設(shè)計(jì)目標(biāo)和思路
本文提出的A-AOMDV協(xié)議主要針對(duì)不同業(yè)務(wù)的QoS需求，綜合考慮多個(gè)指標(biāo)，建立和選擇針對(duì)本業(yè)務(wù)最優(yōu)的路徑來(lái)傳輸業(yè)務(wù)流，從而克服傳統(tǒng)路由算法只根據(jù)某一項(xiàng)指標(biāo)選路，不適合用于傳輸混合業(yè)務(wù)這一局限性，真正實(shí)現(xiàn)面向業(yè)務(wù)需求的目標(biāo)。
本協(xié)議的主要設(shè)計(jì)思路為，在建路過(guò)程中建立源節(jié)點(diǎn)到目的節(jié)點(diǎn)的多條不相交路徑，每條路徑都有衡量自身服務(wù)質(zhì)量的多個(gè)QoS參數(shù)。不同業(yè)務(wù)根據(jù)各自的QoS需求，選擇適合本業(yè)務(wù)的最優(yōu)路徑進(jìn)行傳輸。當(dāng)所有備用路徑都失效時(shí)，則重新尋路。
2.3 參數(shù)定義
在A-AOMDV協(xié)議中，將業(yè)務(wù)的QoS需求歸結(jié)為3方面：時(shí)延、可靠性和可用帶寬?，F(xiàn)為每條路徑添加跳數(shù)D、平均連接度R、最小帶寬B3個(gè)服務(wù)質(zhì)量參數(shù)，以分別衡量時(shí)延、可靠性和可用帶寬，并定義路徑整體服務(wù)質(zhì)量L來(lái)表征具體某種業(yè)務(wù)的QoS需求。根據(jù)前面建模分析的結(jié)論，對(duì)每種QoS需求，將端到端之間的所有路徑按照L的大小進(jìn)行排序，只維護(hù)排序靠前的3條路徑。修改后的路由表單元結(jié)構(gòu)如圖2所示。
圖2 修改的路由表單元結(jié)構(gòu)Fig.2 Unit structure of modified routing table
2.3.1 跳數(shù)D→時(shí)延
在多跳無(wú)線網(wǎng)絡(luò)中，路徑時(shí)延很大程度上取決于源節(jié)點(diǎn)到目的節(jié)點(diǎn)的跳數(shù)。跳數(shù)越大，時(shí)延越大。所以，我們將源節(jié)點(diǎn)到目的節(jié)點(diǎn)的跳數(shù)D作為衡量路徑時(shí)延的參數(shù)。
2.3.2 平均連接度R→可靠性
路徑上節(jié)點(diǎn)的連接度是路徑可靠性的最好度量。一般來(lái)說(shuō)，節(jié)點(diǎn)的鄰居數(shù)越大，則連接度越高，路徑中斷概率越小，路徑也就越可靠，丟包率也越低。節(jié)點(diǎn)通過(guò)接收鄰居周期性廣播的Hello消息可以得知自身鄰居連接情況，也就是該節(jié)點(diǎn)的連接度。我們用路徑上所有節(jié)點(diǎn)的平均連接度R作為衡量路徑可靠性的參數(shù)：
(9)
式中：N為該路徑上的節(jié)點(diǎn)數(shù)；Ci為路徑上第i個(gè)節(jié)點(diǎn)的連接度，即節(jié)點(diǎn)i的鄰居個(gè)數(shù)。
2.3.3 最小帶寬B→可用帶寬
在多跳無(wú)線網(wǎng)絡(luò)中，路徑可用帶寬的大小取決于該路徑上所有節(jié)點(diǎn)的最小帶寬。節(jié)點(diǎn)的等待隊(duì)列中等待發(fā)送的數(shù)據(jù)包個(gè)數(shù)越多，可用的排隊(duì)空間越小，該節(jié)點(diǎn)可用帶寬越小。將路徑上所有節(jié)點(diǎn)的最小帶寬B作為衡量路徑可用帶寬的參數(shù)：
B=min{Qmax-Qi},
(10)
式中：Qmax為路徑上節(jié)點(diǎn)可發(fā)送數(shù)據(jù)包隊(duì)列的最大長(zhǎng)度，現(xiàn)假設(shè)其為固定值；Qi為路徑中節(jié)點(diǎn)i等待發(fā)送的數(shù)據(jù)包隊(duì)列長(zhǎng)度。
2.3.4 路徑整體服務(wù)質(zhì)量L
L=|αD+βB+γR|ρ,
(11)
式中：ρ為修正因子；α、β、γ分別為跳數(shù)D、最小帶寬B和平均連接度R的權(quán)值，滿足α+β+γ=1，由用戶(hù)指定并添加到包頭結(jié)構(gòu)中，可以根據(jù)不同的業(yè)務(wù)進(jìn)行調(diào)整。比如：數(shù)據(jù)業(yè)務(wù)對(duì)可靠性要求較高，應(yīng)將R所對(duì)應(yīng)的權(quán)值γ提高；語(yǔ)音業(yè)務(wù)對(duì)時(shí)延和帶寬要求較大，則可將D、B所對(duì)應(yīng)的權(quán)值α、β作適當(dāng)提高。
需要注意的是，為平衡3個(gè)服務(wù)質(zhì)量參數(shù)所占的比重，應(yīng)根據(jù)具體的應(yīng)用場(chǎng)景使用修正因子ρ來(lái)調(diào)整3個(gè)服務(wù)質(zhì)量參數(shù)的權(quán)值。
2.4 路由協(xié)議的實(shí)現(xiàn)過(guò)程
2.4.1 數(shù)據(jù)轉(zhuǎn)發(fā)過(guò)程
當(dāng)源節(jié)點(diǎn)從應(yīng)用層接收數(shù)據(jù)包時(shí)，首先根據(jù)目的地址查找路由表有無(wú)到其目的節(jié)點(diǎn)的有效路由，如果有則根據(jù)數(shù)據(jù)包包頭中用戶(hù)指定的權(quán)值α、β、γ計(jì)算每條路徑的整體服務(wù)質(zhì)量L，選擇適合于本業(yè)務(wù)的最優(yōu)路徑；如果沒(méi)有則觸發(fā)尋路過(guò)程。
2.4.2 尋路過(guò)程
1)源節(jié)點(diǎn)廣播RREQ包，包結(jié)構(gòu)中添加跳數(shù)、經(jīng)過(guò)的所有節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)總和(用以計(jì)算平均連接度)、所有節(jié)點(diǎn)中最小的可用等待隊(duì)列長(zhǎng)度3種尋路信息。修改后的RREQ包結(jié)構(gòu)如圖3所示，其中，灰色處為協(xié)議添加的信息，路徑所有節(jié)點(diǎn)的鄰居數(shù)總和簡(jiǎn)稱(chēng)為鄰居節(jié)點(diǎn)數(shù)，所有節(jié)點(diǎn)中最小的可用等待隊(duì)列長(zhǎng)度表示為最小帶寬。
圖3 修改的RREQ分組Fig.3 Modified RREQ packet
2)中間節(jié)點(diǎn)接收到該RREQ包時(shí)：
①首先建立或更新到源節(jié)點(diǎn)的反向路由：
a.如果沒(méi)有到源節(jié)點(diǎn)的反向路徑則建立新的反向路徑；
b.如果有到源節(jié)點(diǎn)的反向路徑，且接收的RREQ包中攜帶的3種尋路信息中有一項(xiàng)或多項(xiàng)優(yōu)于已存在的反向路徑的3個(gè)服務(wù)質(zhì)量參數(shù)(跳數(shù)、可用等待隊(duì)列長(zhǎng)度、路徑節(jié)點(diǎn)鄰居數(shù)總和)，則接收作為備用路徑；
②更新該RREQ包中的信息，繼續(xù)廣播。
3)當(dāng)目的節(jié)點(diǎn)或到目的節(jié)點(diǎn)有效路由的中間節(jié)點(diǎn)接收到該RREQ包時(shí)，回復(fù)RREP包，包結(jié)構(gòu)中同樣添加3種尋路信息。修改后的RREP包結(jié)構(gòu)如圖4所示，其中，灰色處為協(xié)議添加的信息，路徑所有節(jié)點(diǎn)的鄰居數(shù)總和簡(jiǎn)稱(chēng)為鄰居節(jié)點(diǎn)數(shù)，所有節(jié)點(diǎn)中最小的可用等待隊(duì)列長(zhǎng)度表示為最小帶寬。
4)中間節(jié)點(diǎn)接收到該RREP分組：
圖4 修改的RREP分組Fig.4 Modified RREP packet
①建立或更新到目的節(jié)點(diǎn)的反向路由；
②更新該RREP中的信息；
③查尋路由表，尋找到源節(jié)點(diǎn)的最優(yōu)路徑，繼續(xù)轉(zhuǎn)發(fā)該RREP包
5)源節(jié)點(diǎn)接收多個(gè)RREP包，建立到目的節(jié)點(diǎn)的多條路徑。
3 仿真與分析
3.1 仿真環(huán)境與場(chǎng)景參數(shù)
利用NS2仿真軟件對(duì)改進(jìn)后的協(xié)議A-AOMDV進(jìn)行仿真，并與原始的AOMDV協(xié)議進(jìn)行比較分析。底層協(xié)議為IEEE 802.11協(xié)議，實(shí)驗(yàn)平臺(tái)是Fedora 8.0. 由于網(wǎng)絡(luò)中節(jié)點(diǎn)的移動(dòng)性會(huì)造成網(wǎng)絡(luò)拓?fù)涞膭?dòng)態(tài)變化，而網(wǎng)絡(luò)拓?fù)涞膭?dòng)態(tài)變化會(huì)對(duì)路由協(xié)議的性能造成嚴(yán)重的影響。主要通過(guò)改變節(jié)點(diǎn)的最大移動(dòng)速率，對(duì)比分析改進(jìn)后的協(xié)議性能。
具體的仿真場(chǎng)景參數(shù)設(shè)置如表2所示。
表2 仿真場(chǎng)景參數(shù)
由于對(duì)協(xié)議的改進(jìn)主要是為了滿足不同業(yè)務(wù)的QoS需求，所以分別選擇最具有代表性的數(shù)據(jù)類(lèi)業(yè)務(wù)和語(yǔ)音類(lèi)業(yè)務(wù)進(jìn)行仿真分析。
在仿真結(jié)果分析中，選擇平均時(shí)延、投遞率和控制開(kāi)銷(xiāo)3個(gè)指標(biāo)來(lái)評(píng)估協(xié)議的性能。
3.2 仿真分析
3.2.1 數(shù)據(jù)類(lèi)業(yè)務(wù)仿真結(jié)果分析
數(shù)據(jù)類(lèi)業(yè)務(wù)對(duì)可靠性要求較高，主要關(guān)注投遞率的提升，所以應(yīng)當(dāng)相應(yīng)的增大平均連接度R所對(duì)應(yīng)的權(quán)值。本部分對(duì)數(shù)據(jù)類(lèi)業(yè)務(wù)的投遞率、平均時(shí)延和控制開(kāi)銷(xiāo)進(jìn)行了仿真，結(jié)果如圖5～圖7所示。
圖5 數(shù)據(jù)類(lèi)業(yè)務(wù)在不同移動(dòng)速度下的投遞率Fig.5 Delivery rate of data service at different speed
圖6 數(shù)據(jù)類(lèi)業(yè)務(wù)在不同移動(dòng)速度下的平均時(shí)延Fig.6 Average delay of data service at different speed
圖7 數(shù)據(jù)類(lèi)業(yè)務(wù)在不同移動(dòng)速度下的控制開(kāi)銷(xiāo)Fig.7 Control overhead of data service at different speed
由圖5可以看到，傳輸數(shù)據(jù)類(lèi)業(yè)務(wù)時(shí)，A-AOMDV協(xié)議可以有效提高分組投遞率。因?yàn)樵跒闃I(yè)務(wù)選擇傳輸路徑時(shí)，AOMDV協(xié)議只考慮端到端跳數(shù)，A-AOMDV協(xié)議則更側(cè)重于路徑可靠性。通過(guò)增大平均連接度R所對(duì)應(yīng)的權(quán)值，從多條路徑中選擇可靠性最高的路徑傳輸業(yè)務(wù)，可以提高分組的投遞率。在一定的范圍內(nèi)，當(dāng)節(jié)點(diǎn)的移動(dòng)速率越高，A-AOMDV協(xié)議在分組投遞率方面優(yōu)化越明顯。
從圖6和圖7中可以看到A-AOMDV和AOMDV協(xié)議的平均時(shí)延和控制開(kāi)銷(xiāo)占比曲線存在交叉，但從整體趨勢(shì)而言?xún)烧咻^為接近，說(shuō)明協(xié)議改進(jìn)沒(méi)有對(duì)時(shí)延和控制開(kāi)銷(xiāo)產(chǎn)生太大影響。
3.2.2 語(yǔ)音類(lèi)業(yè)務(wù)仿真結(jié)果分析
語(yǔ)音類(lèi)業(yè)務(wù)主要關(guān)注時(shí)延的減少和可用帶寬的增加，應(yīng)當(dāng)相應(yīng)的增大跳數(shù)D和最小帶寬B所對(duì)應(yīng)的權(quán)值。本部分對(duì)語(yǔ)音類(lèi)業(yè)務(wù)的投遞率、平均時(shí)延和控制開(kāi)銷(xiāo)進(jìn)行了仿真，結(jié)果如圖8～圖10所示。
圖8 語(yǔ)音類(lèi)業(yè)務(wù)不同移動(dòng)速度下的投遞率Fig.8 Delivery rate of voice service at different speed
圖9 語(yǔ)音類(lèi)業(yè)務(wù)不同移動(dòng)速度下的平均時(shí)延Fig.9 Average delay of voice service at different speed
圖10 語(yǔ)音類(lèi)業(yè)務(wù)不同移動(dòng)速度下的控制開(kāi)銷(xiāo)Fig.10 Control overhead of voice service at different speed
由圖9可以看到，當(dāng)傳輸語(yǔ)音類(lèi)業(yè)務(wù)時(shí)，相比于AOMDV協(xié)議， A-AOMDV協(xié)議可以有效地降低分組的平均時(shí)延。因?yàn)樵跒檎Z(yǔ)音類(lèi)業(yè)務(wù)選擇傳輸路徑時(shí)， A-AOMDV協(xié)議綜合考慮端到端的跳數(shù)、路徑的最小帶寬兩個(gè)方面的QoS需求，從所建立的多條路徑中選擇綜合性能較好的路徑來(lái)傳輸業(yè)務(wù)，不僅考慮端到端的最短路徑，同時(shí)盡可能避免網(wǎng)絡(luò)擁塞，因此可以有效地降低分組平均時(shí)延。
圖8和圖10曲線的接近擬合反映A-AOMDV協(xié)議沒(méi)有影響語(yǔ)音業(yè)務(wù)的分組投遞率和控制開(kāi)銷(xiāo)。
3.2.3 仿真分析總結(jié)
通過(guò)對(duì)數(shù)據(jù)類(lèi)業(yè)務(wù)和語(yǔ)音類(lèi)業(yè)務(wù)進(jìn)行仿真，對(duì)比原AOMDV協(xié)議和改進(jìn)后的A-AOMDV協(xié)議在投遞率、平均時(shí)延、控制開(kāi)銷(xiāo)3個(gè)方面的性能指標(biāo)，可以看到：改進(jìn)的A-AOMDV協(xié)議在傳輸數(shù)據(jù)類(lèi)業(yè)務(wù)時(shí)，可以在不過(guò)分影響分組時(shí)延和控制開(kāi)銷(xiāo)的前提下有效提高投遞率；當(dāng)傳輸語(yǔ)音類(lèi)業(yè)務(wù)時(shí)，則能在保持AOMDV協(xié)議投遞率和控制開(kāi)銷(xiāo)的基礎(chǔ)上大幅降低分組時(shí)延。在仿真中，選擇最具有代表性的兩類(lèi)業(yè)務(wù)。對(duì)于其他類(lèi)的業(yè)務(wù)可以相應(yīng)調(diào)整3個(gè)服務(wù)質(zhì)量參數(shù)的權(quán)值來(lái)滿足各自的QoS需求。
4 結(jié)論
針對(duì)移動(dòng)自組織網(wǎng)，本文首先對(duì)單路徑路由協(xié)議和多路徑路由協(xié)議進(jìn)行建模比較，分析維護(hù)備用路徑的數(shù)目對(duì)多路徑路由協(xié)議性能的重要影響。然后從尋路和選路的角度出發(fā)，基于AOMDV協(xié)議提出一種能適用于傳輸具有不同QoS需求的混合業(yè)務(wù)的多路徑路由協(xié)議A-AOMDV。該協(xié)議針對(duì)不同業(yè)務(wù)的QoS需求，綜合考慮時(shí)延、可靠性和可用帶寬3個(gè)參數(shù)來(lái)選擇最優(yōu)路徑。最后通過(guò)仿真與AOMDV協(xié)議進(jìn)行對(duì)比，對(duì)改進(jìn)后協(xié)議的投遞率、時(shí)延、控制開(kāi)銷(xiāo)等方面的性能進(jìn)行驗(yàn)證，結(jié)果證明該協(xié)議針對(duì)不同業(yè)務(wù)能選擇性地帶來(lái)時(shí)延、可靠性、可用帶寬等性能的提升。該協(xié)議最大的特點(diǎn)是針對(duì)業(yè)務(wù)需求對(duì)多路徑路由協(xié)議進(jìn)行改進(jìn)，不僅能有效減小移動(dòng)自組網(wǎng)網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)變化等因素對(duì)通信質(zhì)量造成的影響，同時(shí)能夠很好地適應(yīng)于多種業(yè)務(wù)共存的場(chǎng)景，達(dá)到了面向業(yè)務(wù)需求的目的。
References)
[1] Araghi T K, Zamani M, Mnaf A B A. Performance analysis in reactive routing protocols in wireless mobile ad hoc networks using DSR, AODV and AOMDV[C]∥International Conference on Informatics and Creative Multimedia. Kuala Lumpur, Malaysia: IEEE, 2013.
[2] Hu Q L, Huang Q Y, Han B, et al. MSR: A novel MPLS-like secure routing protocol for mobile ad hoc networks[C]∥International Conference on Networks Security, Wireless Communications and Trusted Computing. Wuhan, Hubei, China: IEEE, 2009: 129-132.
[3] Rao M, Singh N. Quality of service enhancement in MANETs with an efficient routing algorithm[C]∥IEEE International Advance Computing Conference. Gurgaon, New Delhi, India: IEEE, 2014: 381-384.
[4] Li L Y, Wu M Q, Chen Z Q, et al. Analysis and optimization of multipath routing protocols based on SMR[C]∥2nd International Conference on Signal Processing Systems. Dalian, Liaoning, China: IEEE, 2010: 205-209.
[5] Valera A, Seah W K G, Rao S V. Cooperative packet caching and shortest multipath routing in mobile ad hoc networks[C]∥22nd Annual Joint Conference of the IEEE Computer and Communications. San Francisco, CA, US:IEEE, 2003:260-269.
[6] Pham P, Perreau S. Multi-path routing protocol with load balancing policy in mobile ad hoc network[C]∥4th International Workshop on Mobile and Wireless Communications Network. Stockholm, Sweden: IEEE, 2002: 48-52.
[7] Aldosari F M, Alradady F. Localized QoS routing with end-to-end delay guarantees[C]∥Tenth International Conference on Information Technology: New Generations. Las Vegas, NV, US: IEEE Computer Society, 2013: 464-472.
[8] Du K M, Yang Y H. A QoS routing for maximum bandwidth in ad hoc networks[C]∥2010 Second International Conference on Future Networks. Sanya, Hainan, China: IEEE, 2010: 343-345.
[9] 王潔, 李明明, 劉建生, 等. 基于優(yōu)先級(jí)AODV的擴(kuò)展多路徑路由協(xié)議研究[J]. 軟件導(dǎo)刊, 2015,14(5): 158-161. WANG Jie, LI Ming-ming, LIU Jian-sheng, et al.Research on extended multipath routing protocol based on priority AODV[J]. Software Guide, 2015, 14(5): 158-161. (in Chinese)
[10] 尚碩. 無(wú)線Mesh網(wǎng)絡(luò)多路徑路由協(xié)議研究[D]. 長(zhǎng)春：吉林大學(xué), 2015. SHANG Shuo. Research on multipath routing protocol in wireless mesh network[D]. Changchun: Jilin University, 2015. (in Chinese)
[11] 3GPP. TS22.105 Technical specification group services and system aspects: services and service capabilities(Release 8)[S]. Valbonne, France: 3GPP, 2007.
An Improved Multi-path Routing Protocol in Mobile Ad Hoc Network
LI Xu1， QIU Song-qing1， PENG Jin-lin2， WANG Cong1
(1.School of Electronic and Information Engineering, Beijing Jiaotong University, Beijing 100044, China; 2.Beijing Institute of Tracking and Telecommunication Technology, Beijing 100092, China)
Multi-path routing protocol can effectively reduce the probability of communication interrupt and end-to-end delay by establishing and maintaining multiple alternate paths in mobile ad-hoc network. The current analysis methods of the number of alternate paths are unavailable for the complex wireless ad-hoc network transmission environment. The existing multipath routing protocols can’t meet the requirements of mixed services. In order to solve the above-mentioned problems, the models for single-path and multi-path routing protocols are established to analyze the effect of the number of alternate paths on the performance of multi-path routing protocol. An application-oriented ad hoc on-demand multipath distance vector (A-AOMDV) is proposed, in which many parameters, such as hop, average connectivity, minimum bandwidth and so on, are considered, and the best path is selected for any service. The simulated result shows that the delivery rate of data service can be increased by 25% and the average delay of voice service can be reduced by 10%～20% by adjusting the weights of parameters. The proposed protocol can selectively improve the properties of delay, reliability and available bandwidth for different services.
computer system architecture; mobile ad-hoc network; multi-path routing protocol; A-AOMDV; quality of service
2016-04-08
國(guó)家自然科學(xué)基金項(xiàng)目(61371068)；國(guó)家“863”計(jì)劃項(xiàng)目(2015AA01A705)；國(guó)家科技支撐計(jì)劃項(xiàng)目(2014BAK02B04)； 中央高校基本科研業(yè)務(wù)費(fèi)專(zhuān)項(xiàng)資金項(xiàng)目(2014JBZ002)
李旭(1970—)，女，教授，博士生導(dǎo)師。E-mail: xli@bjtu.edu.cn； 仇頌清(1991—)，男，碩士研究生。E-mail: 14120111@bjtu.edu.cn
TN915.04
A
1000-1093(2016)11-2022-07
10.3969/j.issn.1000-1093.2016.11.009
