楊 路,朱 顯,王詩言

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

0 概述

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

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

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

1 相關(guān)工作

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

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

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

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

1.1 期望傳輸次數(shù)

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

(1)

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

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

(2)

p計算公式如下:

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

(3)

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

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

1.2 期望傳輸時間

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

(4)

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

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

2 SETT_MPOLSR路由協(xié)議

2.1 協(xié)議流程

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

圖1 SETT_MPOLSR協(xié)議流程

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

2.2 Hello包與TC包報文格式

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

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

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

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多徑算法沒有以期望傳輸時間總和最小作為原則計算出多條不同的路徑,原因是當(dāng)傳輸條件極度不好時(比如災(zāi)難救援場景),鏈路質(zhì)量時好時壞,鏈路間的ETT值會參差不齊,一條鏈路中斷就會導(dǎo)致整條路徑通信中斷。因此,為避免該路徑的鏈路ETT值相差較大影響整條路徑的穩(wěn)定性,本文提出一種優(yōu)化評判因子,公式如下:

(5)

其中,ETTl為鏈路l的ETT值,l是路徑p上的一條鏈路,THRESHOLDETT為期望傳輸時間門限值。

被選路徑p*定義為:

(6)

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

若存在多條鏈路的S值都相等,此時比較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)

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

1)分組投遞率:

(8)

2)平均端到端時延:

(9)

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

(10)

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

表1 仿真參數(shù)

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

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

圖4所示為節(jié)點(diǎn)移動性與投遞率之間的關(guān)系。從圖4可以看出,所有協(xié)議呈現(xiàn)出相同的趨勢,節(jié)點(diǎn)移動越快,投遞率就越低。這是因?yàn)楫?dāng)節(jié)點(diǎn)移動加快時,鏈路斷開的概率就會增大。其中,3個多徑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ù)量較多時,選到路徑最短同時傳輸質(zhì)量又最好的鏈路的可能性非常低,因此,相比用跳數(shù)作為度量,用期望傳輸時間作為度量的協(xié)議表現(xiàn)更好。SETT_MPOLSR協(xié)議引入優(yōu)化因子S后,傳輸鏈路的投遞率上升,但是并沒有表現(xiàn)出其在惡劣場景下的優(yōu)勢,本文最后將對惡劣場景進(jìn)行仿真。

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

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

圖6所示為4種協(xié)議的網(wǎng)絡(luò)吞吐量與節(jié)點(diǎn)移動速度之間的關(guān)系。從圖6可以看出,隨著速度的上升,網(wǎng)絡(luò)鏈路開始不穩(wěn)定,由此導(dǎo)致傳輸時延增加,因此,吞吐量整體呈現(xiàn)下降的趨勢,但是本文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)境時協(xié)議的通信質(zhì)量,在表1的基礎(chǔ)上將有效傳輸范圍縮小到200 m,增大發(fā)包率為15 包/s,以驗(yàn)證SETT_MPOLSR協(xié)議的分組投遞率。如圖7所示,在傳輸范圍縮小以及發(fā)包率增加后,網(wǎng)絡(luò)的分組投遞率下降,但相比運(yùn)行3種對比協(xié)議的網(wǎng)絡(luò),運(yùn)行SETT_MPOLSR協(xié)議的網(wǎng)絡(luò)投遞率明顯提高,該結(jié)果說明本文提出的優(yōu)化因子S在通信惡劣的場景下仍然具有良好性能。

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

4 結(jié)束語

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