一種基于期望傳輸時(shí)間的多徑OLSR路由協(xié)議

楊 路,朱 顯,王詩(shī)言

(重慶郵電大學(xué) 通信與信息工程學(xué)院,重慶 400065)

0 概述

移動(dòng)自組織網(wǎng)絡(luò)(Mobile Ad-hoc Networks,MANET)是自組織和自配置網(wǎng)絡(luò),其無(wú)需任何蜂窩基礎(chǔ)設(shè)施,如接入點(diǎn)(Access Point,AP)、基站(Base Station,BS)或固定傳輸鏈路,各無(wú)線終端(計(jì)算機(jī)、基于微處理器的設(shè)備、個(gè)人數(shù)字適配器(Personal Digital Adapter,PDA)、移動(dòng)電話或具有兼容通信能力的任何數(shù)字設(shè)備)可以動(dòng)態(tài)地自組織成臨時(shí)性的任意網(wǎng)絡(luò)拓?fù)洳⒔⒕W(wǎng)絡(luò)[1-2]。由于無(wú)線自組織網(wǎng)絡(luò)承載容量大、數(shù)據(jù)傳輸帶寬高、容錯(cuò)能力強(qiáng)、組網(wǎng)靈活,因此在工業(yè)、商業(yè)、學(xué)術(shù)、醫(yī)療保健、軍事搜索和救援行動(dòng)以及個(gè)人局域網(wǎng)(Personal LAN,PAN)領(lǐng)域得到了廣泛應(yīng)用[3-4]。

針對(duì)MANET網(wǎng)絡(luò)拓?fù)渥兓l繁以及節(jié)點(diǎn)不規(guī)則移動(dòng)的特點(diǎn),相對(duì)單徑路由協(xié)議,多徑路由協(xié)議更具有優(yōu)勢(shì),原因具體表現(xiàn)在以下4個(gè)方面:1)容錯(cuò)性,為確保數(shù)據(jù)的正確傳輸,多徑路由協(xié)議采取多條路徑發(fā)送冗余數(shù)據(jù),即使某一路徑出現(xiàn)故障,也能保證數(shù)據(jù)的成功傳輸;2)負(fù)載均衡,多條鏈路分擔(dān)數(shù)據(jù),避免單一鏈路負(fù)載過(guò)重;3)為傳輸提供足夠的帶寬;4)多徑路由協(xié)議擁有備用鏈路,可以提高路由恢復(fù)的效率。因此,多徑路由能在對(duì)時(shí)延和吞吐量要求較高的場(chǎng)景表現(xiàn)出卓越的性能[5]。

本文提出一種基于差分期望傳輸時(shí)間(Expected Transmission Time,ETT)的多徑OLSR(Optimized Link State Routing)路由協(xié)議SETT_MPOLSR。將期望傳輸時(shí)間作為路由度量,同時(shí)為避免路徑上的鏈路ETT值相差較大影響整條鏈路的穩(wěn)定性,本文還設(shè)計(jì)一種優(yōu)化評(píng)判因子S,以提升鏈路穩(wěn)定性。最后通過(guò)實(shí)驗(yàn)驗(yàn)證該協(xié)議在投遞率和時(shí)延方面的性能。

1 相關(guān)工作

典型多徑路由協(xié)議有基于AODV的AOMDV[6]、基于DSR的SMR[7]、基于OLSR的MP_OLSR[8]。文獻(xiàn)[9]提到AOMDV只能找到等長(zhǎng)的多條路徑,在大型網(wǎng)絡(luò)中,當(dāng)節(jié)點(diǎn)密度變稀疏時(shí)其采用2段鏈路不相交路徑的方法,這增加了路由出錯(cuò)信息重新傳送的開(kāi)銷,因此,AOMDV協(xié)議只適用于節(jié)點(diǎn)密度較大的小型網(wǎng)絡(luò)。SMR協(xié)議由于只能提供2條最大的不相交路徑,這2條路徑并不一定是節(jié)點(diǎn)不相交的路徑,由此導(dǎo)致協(xié)議不易擴(kuò)展。MP_OLSR協(xié)議既適合節(jié)點(diǎn)密度小的場(chǎng)景,也適合節(jié)點(diǎn)密度大的場(chǎng)景,當(dāng)負(fù)載過(guò)大時(shí),網(wǎng)絡(luò)中的端到端時(shí)延和丟包率都能夠明顯降低,但其采用多重Dijkstra算法和源路由機(jī)制,這增大了節(jié)點(diǎn)處理負(fù)擔(dān)。

MP_OLSR協(xié)議使用跳數(shù)作為其路由度量，在無(wú)線自組織網(wǎng)絡(luò)中,路由度量有很多,如跳數(shù)、預(yù)期傳輸次數(shù)(Expected Transmission count,ETX)、誤碼率(Bit Error Rate,BER)等。其中,跳數(shù)是較早和較普遍的一個(gè)度量,原因是其易于理解和實(shí)現(xiàn)。鏈路中的每個(gè)節(jié)點(diǎn)(終端)都是一跳,在數(shù)據(jù)包傳輸過(guò)程中,每經(jīng)過(guò)一個(gè)節(jié)點(diǎn)就記錄一跳,因此,跳數(shù)是計(jì)算路徑距離的一種粗略辦法,基于跳數(shù)小的鏈路其路徑較短這一假設(shè),路由協(xié)議嘗試找到具有最小跳數(shù)的路徑,以便最小化端到端延遲。但是在無(wú)線多跳網(wǎng)絡(luò)環(huán)境中,跳數(shù)少的無(wú)線鏈路不一定通信質(zhì)量好、帶寬和吞吐量高、時(shí)延小,為解決該問(wèn)題,有研究者對(duì)MP_OLSR協(xié)議進(jìn)行了不同的改進(jìn)。

文獻(xiàn)[10-11]分別提出LIA-MPOLSR協(xié)議和HIA-MPOLSR協(xié)議。然而,基于度量的干擾路徑選擇策略并不總是可用的,這需要GPS來(lái)定位用于計(jì)算該度量的鄰居位置。文獻(xiàn)[12]提出一種基于能量度量的多徑OLSR協(xié)議,其目的是獲得網(wǎng)絡(luò)中所有節(jié)點(diǎn)的能量?jī)?yōu)化,并使所有節(jié)點(diǎn)的能量消耗均勻。文獻(xiàn)[13]提出一種基于OLSR變量的能量和移動(dòng)模式度量標(biāo)準(zhǔn),目的是增加節(jié)點(diǎn)和鏈路的生存時(shí)間和選定路徑的可靠性。然而,移動(dòng)模式度量需要鄰居節(jié)點(diǎn)位置,因此,這些信息并不可靠。

本文針對(duì)應(yīng)急場(chǎng)景(地震、火災(zāi)等)設(shè)計(jì)一種路由協(xié)議SETT_MPOLSR。由于多徑路由擁有冗余鏈路且路由恢復(fù)快,因此本文是對(duì)基于多徑OLSR協(xié)議進(jìn)行的改進(jìn)。在無(wú)線網(wǎng)絡(luò)中,使用最短跳數(shù)路徑的協(xié)議仍然存在諸多弊端,跳數(shù)少的無(wú)線鏈路沒(méi)有考慮不同鏈路的性能差異,且已有研究多數(shù)沒(méi)有考慮鏈路丟包及鏈路帶寬。為此,本文將期望傳輸時(shí)間引入到路由中,以此來(lái)找到高吞吐量、低時(shí)延的鏈路并進(jìn)行通信傳輸。

1.1 期望傳輸次數(shù)

ETX定義為從發(fā)送端到接收端成功傳輸數(shù)據(jù)包的期望傳輸次數(shù),它是一種路由判據(jù)。ETX計(jì)算公式如下:

(1)

其中,k為數(shù)據(jù)包重傳次數(shù),s(k)為第k次重傳數(shù)據(jù)包成功發(fā)送的概率,其計(jì)算公式如下:

s(k)=pk-1(1-p)

(2)

p計(jì)算公式如下:

p=1-(1-pf)(1-pr)

(3)

其中,pf和pr分別為正向、反向傳輸鏈路的丟包率。

為計(jì)算無(wú)線多跳網(wǎng)中每條鏈路的ETX值,采用文獻(xiàn)[14]方法:節(jié)點(diǎn)默認(rèn)周期性地(1 s)廣播一個(gè)ETX探測(cè)封包,每10 s時(shí)間統(tǒng)計(jì)這段時(shí)期內(nèi)會(huì)有多少探測(cè)封包被成功接收到。根據(jù)探測(cè)封包的結(jié)果,所有節(jié)點(diǎn)便可以計(jì)算出自己達(dá)到鄰居節(jié)點(diǎn)無(wú)線鏈路的丟包率,進(jìn)而根據(jù)式(1)計(jì)算每條無(wú)線鏈路的ETX值。

1.2 期望傳輸時(shí)間

期望傳輸時(shí)間ETT由微軟無(wú)線Mesh網(wǎng)絡(luò)研究項(xiàng)目組提出[15],是對(duì)ETX的擴(kuò)展,其將無(wú)線鏈路上的傳輸時(shí)間作為路由度量。ETT計(jì)算公式如下:

(4)

其中,D是使用的數(shù)據(jù)包大小,B是鏈路間的帶寬。

確定每條鏈路的帶寬較復(fù)雜,其中一種辦法是將每個(gè)802.11無(wú)線鏈路的帶寬固定為給定的值。例如,文獻(xiàn)[16]設(shè)置802.11b無(wú)線電的帶寬為1 Mb/s。本文采用分組對(duì)技術(shù)來(lái)測(cè)量帶寬[17]。每個(gè)節(jié)點(diǎn)每分鐘向每個(gè)鄰居發(fā)送2個(gè)背對(duì)背探測(cè)數(shù)據(jù)包。第1個(gè)探測(cè)數(shù)據(jù)包很小(100 Byte),第2個(gè)探測(cè)數(shù)據(jù)包很大(1 000 Byte)。鄰居測(cè)量第1分組和第2分組接收時(shí)間差,并將該值傳送給發(fā)送節(jié)點(diǎn)。提取連續(xù)10個(gè)時(shí)間差的最小值,然后用探測(cè)包的大小除以最小采樣時(shí)間差,以此估計(jì)帶寬。ETT的定義不包括等待無(wú)線電信道的退避時(shí)間,它只反映實(shí)際使用信道的時(shí)間。

2 SETT_MPOLSR路由協(xié)議

2.1 協(xié)議流程

圖1所示為SETT_MPOLSR網(wǎng)絡(luò)拓?fù)涞墓芾砹鞒獭ello包除了攜帶基本鏈路信息外還攜帶ETT信息。節(jié)點(diǎn)根據(jù)Hello包攜帶的信息以及接受率計(jì)算出鄰居間的ETT值,然后記錄到相應(yīng)的路由表項(xiàng)中。

圖1 SETT_MPOLSR協(xié)議流程

對(duì)于MPR節(jié)點(diǎn),其發(fā)送出的TC包(用于交換各自MPR對(duì)的信息)包含所有涉及的MPR包對(duì)的ETT信息。當(dāng)其他MPR節(jié)點(diǎn)接收到TC包信息時(shí),除提取地址信息外,還要提取相應(yīng)的ETT值并記錄到路由表項(xiàng)中。在SETT_MPOLSR協(xié)議中,ETT值通過(guò)Hello包和TC包來(lái)計(jì)算并在全網(wǎng)進(jìn)行廣播。

2.2 Hello包與TC包報(bào)文格式

SETT_MPOLSR協(xié)議改變了Hello包的信息格式,新的Hello包比原始Hello包多了3個(gè)TLV單元,分別為F_TEX、R_TEX和帶寬B,格式如圖2所示。其中,三者的值按照TimeTLV進(jìn)行編碼,Hello包的發(fā)送機(jī)制不改變。TC消息幫助網(wǎng)絡(luò)中的所有節(jié)點(diǎn)獲取消息原始生成器與其MPR選擇器之間的ETX值。相比于原始TC包,新的TC包多了一個(gè)TLV單元,如圖3所示,TC包的發(fā)送機(jī)制也不變。

圖2 SETT_MPOLSR協(xié)議的Hello消息報(bào)文格式

圖3 SETT_MPOLSR協(xié)議的TC消息報(bào)文格式

2.3 SETT_MPOLSR路徑選擇算法

SETT_MPOLSR路徑選擇算法基于圖G=(V,E,C)、點(diǎn)(s,d)∈e2和正整數(shù)N。(P1,P2,…,Pt)是根據(jù)Dijkstra算法算出的從源節(jié)點(diǎn)s到目的節(jié)點(diǎn)d的t條最短路徑。

在SETT_MPOLSR中,鏈路的權(quán)值C設(shè)為該鏈路的ETT值。SETT_MPOLSR協(xié)議的Dijkstra多徑算法沒(méi)有以期望傳輸時(shí)間總和最小作為原則計(jì)算出多條不同的路徑,原因是當(dāng)傳輸條件極度不好時(shí)(比如災(zāi)難救援場(chǎng)景),鏈路質(zhì)量時(shí)好時(shí)壞,鏈路間的ETT值會(huì)參差不齊,一條鏈路中斷就會(huì)導(dǎo)致整條路徑通信中斷。因此,為避免該路徑的鏈路ETT值相差較大影響整條路徑的穩(wěn)定性,本文提出一種優(yōu)化評(píng)判因子,公式如下:

(5)

其中,ETTl為鏈路l的ETT值,l是路徑p上的一條鏈路,THRESHOLDETT為期望傳輸時(shí)間門(mén)限值。

被選路徑p*定義為:

(6)

其中,P是從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的發(fā)現(xiàn)路徑集合。

若存在多條鏈路的S值都相等,此時(shí)比較ETT值,選擇ETT值最小的路徑作為被選路徑p*,定義為:

(7)

路徑選擇算法偽代碼如下:

Function Modified MultiPath Dijkstra(s,d,G,t)

c1←c;

G1←G;

for(i←1 to t) do

SourceTreei←Dijkstra(Gi,d);

pi←GetPath(SourceTreei,d);

for all arcs e in E do

if e is in pior reverse(e) is in pithen

ci+1(e)←ci(e);

else if the vertex Head(e) is in pithen

ci+1(e)←ci(e);

else

ci+1(e)←ci(e);

end if

end for

Gi+1=(V,E,ci+1);

end for

for(i←1 to t) do

end for

return((p1,S1),(p2,S2),…,(pt,St));

3 仿真驗(yàn)證

3.1 仿真參數(shù)與指標(biāo)

對(duì)本文算法的分組投遞率、平均端到端時(shí)延、網(wǎng)絡(luò)吞吐量性能進(jìn)行仿真對(duì)比,各指標(biāo)計(jì)算公式如下:

1)分組投遞率:

(8)

2)平均端到端時(shí)延:

(9)

3)網(wǎng)絡(luò)吞吐量:

(10)

本文采用的仿真工具為NS2,仿真參數(shù)如表1所示,繪圖工具為gnuplot。仿真結(jié)束后會(huì)生成一個(gè)trace文件,利用awk腳本文件從trace里提取相關(guān)數(shù)據(jù),再根據(jù)式(8)～式(10)計(jì)算各指標(biāo)的值,最后利用gnuplot工具將計(jì)算結(jié)果用圖的形式進(jìn)行表示。

表1 仿真參數(shù)

3.2 仿真結(jié)果與分析

在仿真中,本文比較帶有S因子的SETT_MPOLSR協(xié)議、沒(méi)有S因子的ETT_MPOLSR協(xié)議、原始多徑路由協(xié)議MPOLSR以及單徑OLSR協(xié)議之間的性能。

圖4所示為節(jié)點(diǎn)移動(dòng)性與投遞率之間的關(guān)系。從圖4可以看出,所有協(xié)議呈現(xiàn)出相同的趨勢(shì),節(jié)點(diǎn)移動(dòng)越快,投遞率就越低。這是因?yàn)楫?dāng)節(jié)點(diǎn)移動(dòng)加快時(shí),鏈路斷開(kāi)的概率就會(huì)增大。其中,3個(gè)多徑OLSR路由協(xié)議均比單徑OLSR協(xié)議表現(xiàn)更好,原因是多徑OLSR協(xié)議有多條鏈路傳輸,即使某條鏈路出現(xiàn)故障,其他鏈路也能夠正常傳輸數(shù)據(jù),因此,多徑傳輸可以增強(qiáng)網(wǎng)絡(luò)的健壯性。當(dāng)節(jié)點(diǎn)數(shù)量、傳輸跳數(shù)、鏈路數(shù)量較多時(shí),選到路徑最短同時(shí)傳輸質(zhì)量又最好的鏈路的可能性非常低,因此,相比用跳數(shù)作為度量,用期望傳輸時(shí)間作為度量的協(xié)議表現(xiàn)更好。SETT_MPOLSR協(xié)議引入優(yōu)化因子S后,傳輸鏈路的投遞率上升,但是并沒(méi)有表現(xiàn)出其在惡劣場(chǎng)景下的優(yōu)勢(shì),本文最后將對(duì)惡劣場(chǎng)景進(jìn)行仿真。

圖5所示為各協(xié)議的平均端對(duì)端延遲,其包括每個(gè)節(jié)點(diǎn)中的隊(duì)列延遲和從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的傳播延遲。從圖5可以看出,多徑路由比單徑路由時(shí)延低得多,這是因?yàn)槎鄰铰酚傻牧髁糠植荚诓煌逆溌分?可以減少隊(duì)列延遲,此外,雖然多徑路由協(xié)議可能花費(fèi)更多的時(shí)間重新計(jì)算和恢復(fù)路徑,但因?yàn)榛謴?fù)機(jī)制可以避免通過(guò)故障鏈路發(fā)送數(shù)據(jù)包,因此,其仍然具有較低的延遲。相比用跳數(shù)作為度量,用期望傳輸時(shí)間作為度量時(shí)所選傳輸路徑的鏈路質(zhì)量更好,出現(xiàn)鏈路故障的概率更低,因此,在時(shí)延性能上,以ETT作為度量的協(xié)議表現(xiàn)更優(yōu)。引入優(yōu)化因子S后,能避免路徑鏈路ETT值相差較大而影響整條路徑的穩(wěn)定性,因此,本文SETT_MPOLSR協(xié)議能夠有效降低時(shí)延。

圖5 4種協(xié)議的平均端到端時(shí)延與節(jié)點(diǎn)速度關(guān)系曲線

圖6所示為4種協(xié)議的網(wǎng)絡(luò)吞吐量與節(jié)點(diǎn)移動(dòng)速度之間的關(guān)系。從圖6可以看出,隨著速度的上升,網(wǎng)絡(luò)鏈路開(kāi)始不穩(wěn)定,由此導(dǎo)致傳輸時(shí)延增加,因此,吞吐量整體呈現(xiàn)下降的趨勢(shì),但是本文SETT_MPOLSR協(xié)議的網(wǎng)絡(luò)吞吐量表現(xiàn)最優(yōu)。

圖6 4種協(xié)議的網(wǎng)絡(luò)吞吐量與節(jié)點(diǎn)速度關(guān)系曲線

為了模擬災(zāi)難救援等極端環(huán)境時(shí)協(xié)議的通信質(zhì)量,在表1的基礎(chǔ)上將有效傳輸范圍縮小到200 m,增大發(fā)包率為15 包/s,以驗(yàn)證SETT_MPOLSR協(xié)議的分組投遞率。如圖7所示,在傳輸范圍縮小以及發(fā)包率增加后,網(wǎng)絡(luò)的分組投遞率下降,但相比運(yùn)行3種對(duì)比協(xié)議的網(wǎng)絡(luò),運(yùn)行SETT_MPOLSR協(xié)議的網(wǎng)絡(luò)投遞率明顯提高,該結(jié)果說(shuō)明本文提出的優(yōu)化因子S在通信惡劣的場(chǎng)景下仍然具有良好性能。

圖7 改變參數(shù)后的分組投遞率與節(jié)點(diǎn)速度關(guān)系曲線

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

多徑OLSR協(xié)議沒(méi)有考慮鏈路中的丟包、帶寬等因素。為提高鏈路穩(wěn)定性,本文提出基于差分期望傳輸時(shí)間的多徑OLSR路由協(xié)議SETT_MPOLSR。該協(xié)議將ETT作為路由度量,計(jì)算節(jié)點(diǎn)間鏈路的ETX值和帶寬值后進(jìn)行路由選擇,同時(shí),為避免路徑上的鏈路ETT值相差較大影響整條鏈路的穩(wěn)定性,引入優(yōu)化因子S。實(shí)驗(yàn)結(jié)果表明,該路由協(xié)議具有較高的投遞率和較低的時(shí)延,網(wǎng)絡(luò)整體性能良好。今后考慮將速度引入到路由度量中,并在路由廣播時(shí)縮小廣播范圍,以進(jìn)行有方向目的性的廣播并減小網(wǎng)絡(luò)開(kāi)銷。