胡 春，任 智，崔忠林

1(重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065) 2(電子科技集團(tuán)公司第三十八研究所，合肥 230000)

1 引 言

無(wú)人機(jī)自組網(wǎng) (UAV Ad-Hoc Network，UANET)是移動(dòng)自組網(wǎng)的一個(gè)特例[1]，無(wú)人機(jī)自組網(wǎng)具有功能多樣性、靈活性、易于安裝部署和相對(duì)較小的運(yùn)營(yíng)費(fèi)用等優(yōu)勢(shì)，在軍事和民用領(lǐng)域得到廣泛應(yīng)用[2-4].應(yīng)用在無(wú)人機(jī)自組網(wǎng)中的OLSR協(xié)議是Ad Hoc網(wǎng)絡(luò)中廣泛使用的路由協(xié)議的一種[5-7]，OLSR協(xié)議是先驗(yàn)式路由的一種，時(shí)延較小，適合于節(jié)點(diǎn)數(shù)較多，拓?fù)渥兓惶珓×业膱?chǎng)景[8].AODV路由協(xié)議是按需路由協(xié)議的一種，在路由發(fā)生錯(cuò)誤，超時(shí)的情況下，會(huì)啟動(dòng)路由維護(hù)機(jī)制，保證通信的正常[9,10].針對(duì)無(wú)人機(jī)自組網(wǎng)的應(yīng)用場(chǎng)景，在OLSR路由協(xié)議中引入按需路由機(jī)制，能夠更好的結(jié)合兩類協(xié)議的優(yōu)點(diǎn).目前基于按需路由OLSR協(xié)議已經(jīng)有了一定的研究.文獻(xiàn)[10]提出基于下一跳機(jī)制的OLSR協(xié)議，提高了OLSR協(xié)議對(duì)動(dòng)態(tài)變化網(wǎng)絡(luò)結(jié)構(gòu)的適應(yīng)能力以及局部重載時(shí)的自動(dòng)調(diào)節(jié)能力.文獻(xiàn)[12]提出了基于集合運(yùn)算的MPR集選擇算法，找到了一種最新、最有效的MPR選擇算法，但是該算法比經(jīng)典OLSR協(xié)議增加了時(shí)延.文獻(xiàn)[13]利用OLSR協(xié)議中Hello消息報(bào)文，獲取鄰居節(jié)點(diǎn)的健康指數(shù)，建立路由修復(fù)機(jī)制.文獻(xiàn)[15]提出了將時(shí)延容忍網(wǎng)絡(luò)和自組織網(wǎng)絡(luò)結(jié)合，把時(shí)延容忍網(wǎng)絡(luò)中的機(jī)會(huì)路由思想引入OLSR協(xié)議，在數(shù)據(jù)包沒(méi)有下一條路由時(shí)，不是直接丟棄，而是借鑒機(jī)會(huì)路由思想，將數(shù)據(jù)包發(fā)給連接度高的一跳鄰居，提高發(fā)包成功率.

按需路由和OLSR協(xié)議的結(jié)合，提高OLSR協(xié)議在各種應(yīng)用場(chǎng)景中的性能[16,17].本文根據(jù)文獻(xiàn)[15]的思路，針對(duì)該協(xié)議中機(jī)會(huì)路由無(wú)法保證低時(shí)延的缺點(diǎn)，在仔細(xì)研究OLSR協(xié)議和AODV路由協(xié)議的基礎(chǔ)上，將AODV的鏈路維護(hù)機(jī)制和OLSR協(xié)議相結(jié)合，提出了一種基于按需尋路的可靠OLSR協(xié)議(Reliable OLSR protocol for on-demand pathfinding of drone ad hoc networks，ODR-OLSR).

2 無(wú)人機(jī)自組網(wǎng)OLSR協(xié)議的問(wèn)題

無(wú)人機(jī)自組網(wǎng)場(chǎng)景中，由于無(wú)人機(jī)移動(dòng)速度快和無(wú)線信道的特點(diǎn)，傳統(tǒng)的OLSR協(xié)議存在如下問(wèn)題：

2.1 無(wú)人機(jī)移動(dòng)速度快造成鏈路中斷

由于無(wú)人機(jī)移動(dòng)速度快，網(wǎng)絡(luò)拓?fù)渥兓?，造成多跳鏈路通信失?如圖 1所示，1號(hào)節(jié)點(diǎn)和4號(hào)節(jié)點(diǎn)進(jìn)行通信，由于3號(hào)無(wú)人機(jī)的快速移動(dòng)，與2號(hào)和4號(hào)的通信距離超過(guò)通信范圍，導(dǎo)致通信鏈路中斷，通信失敗.在無(wú)人機(jī)自組網(wǎng)應(yīng)用環(huán)境中，通信中斷可能性，隨著通信跳數(shù)增加.

圖1 鏈路模型Fig.1 Link model

2.2 新入網(wǎng)節(jié)點(diǎn)無(wú)發(fā)及時(shí)與全網(wǎng)通信

由于無(wú)人機(jī)的高動(dòng)態(tài)性，可能造成無(wú)人機(jī)頻繁脫網(wǎng)和入網(wǎng).OLSR協(xié)議主要是靠定期廣播HELLO消息和TC消息，維持全網(wǎng)路由信息.新入網(wǎng)無(wú)人機(jī)無(wú)發(fā)接收足夠多的TC消息，因此無(wú)法得到全網(wǎng)路由，導(dǎo)致通信失敗，嚴(yán)重影響網(wǎng)絡(luò)的通信需求.

3 改進(jìn)協(xié)議ODR-OLSR介紹

針對(duì)無(wú)人機(jī)自組網(wǎng)中的問(wèn)題，ODR-OLSR協(xié)議提出了以下改進(jìn)：

3.1 機(jī)制1：基于TC消息尋路機(jī)制

針對(duì)多跳鏈路中斷問(wèn)題，提出當(dāng)節(jié)點(diǎn)發(fā)現(xiàn)鏈路中斷時(shí)，借鑒AODV協(xié)議中的RREQ路由維護(hù)機(jī)制，節(jié)點(diǎn)主動(dòng)發(fā)送基于TC消息的路由維護(hù)消息.

由于OLSR協(xié)議會(huì)定期全網(wǎng)泛洪T(mén)C消息，但是沒(méi)有尋路功能，AODV協(xié)議利用全網(wǎng)泛洪的RREQ消息進(jìn)行尋路，因此當(dāng)節(jié)點(diǎn)發(fā)現(xiàn)鏈路中斷，利用TC消息攜帶目的地址，進(jìn)行尋路.具體步驟如下：

1)鏈路中斷的判斷：多跳鏈路進(jìn)行通行時(shí)，中間節(jié)點(diǎn)執(zhí)行鏈路監(jiān)控的功能.MAC層傳遞數(shù)據(jù)幀時(shí)，存在重傳機(jī)制，當(dāng)重傳次數(shù)達(dá)到上限，即判定鏈路中斷.

2)鏈路維護(hù)機(jī)制啟動(dòng)：發(fā)生鏈路中斷的節(jié)點(diǎn)啟動(dòng)鏈路維護(hù)，立刻向全網(wǎng)廣播TC消息，并利用TC消息中的保留字段Reserved攜帶目的地址，進(jìn)行尋路，并修改消息類型為T(mén)C尋址消息.每個(gè)節(jié)點(diǎn)在一個(gè)TC周期內(nèi)，只能進(jìn)行一次TC尋址，避免反復(fù)向全網(wǎng)泛洪T(mén)C消息，減小控制開(kāi)銷.

3)TC尋址消息的處理：其他節(jié)點(diǎn)在接收到TC尋址消息后，除了進(jìn)行正常的TC消息處理程序，還需將保留字段Reserved的值與節(jié)點(diǎn)自身地址進(jìn)行比較，如果兩者相等，立刻啟動(dòng)TC尋址回復(fù)機(jī)制，向全網(wǎng)廣播TC消息，并修改消息類型為T(mén)C回復(fù)消息.

4)生成臨時(shí)路由：?jiǎn)?dòng)鏈路維護(hù)機(jī)制的節(jié)點(diǎn)可能會(huì)收到多個(gè)轉(zhuǎn)發(fā)來(lái)的TC回復(fù)消息，節(jié)點(diǎn)在接收第一個(gè)TC回復(fù)消息時(shí)，將轉(zhuǎn)發(fā)節(jié)點(diǎn)定義為通往目的節(jié)點(diǎn)的下一跳路由.

3.2 機(jī)制2：基于HELLO消息尋址機(jī)制

針對(duì)新入網(wǎng)節(jié)點(diǎn)由于缺乏全網(wǎng)的路由信息，導(dǎo)致無(wú)發(fā)及時(shí)通信問(wèn)題，提出基于HELLO消息尋址機(jī)制，通過(guò)HELLO消息攜帶目的地址，向周圍一跳鄰居進(jìn)行尋址，形成一條臨時(shí)路由，縮短路由獲取時(shí)間.其具體步驟如下：

1)HELLO尋址消息生成：當(dāng)節(jié)點(diǎn)網(wǎng)絡(luò)層接收到上層數(shù)據(jù)流時(shí)，發(fā)現(xiàn)目的地址路由缺失，啟動(dòng)HELLO尋址機(jī)制，立刻發(fā)送HELLO消息，利用HELLO消息保留字段Reserved攜帶目的地址，同時(shí)修改消息類型為HELLO尋址消息.

2)HEELLO尋址消息的處理：周圍一跳鄰居接收到HELLO尋址消息后，除了進(jìn)行正常HELLO消息處理程序外，還查詢Reserved字段的值，如果存在到達(dá)目的節(jié)點(diǎn)的路由，啟動(dòng)HELLO回復(fù)機(jī)制，立即發(fā)送HELLO消息，利用HELLO消息保留字段Reserved攜帶目的地址，并將消息類型改為HELLO回復(fù)消息.

3)生成臨時(shí)路由：發(fā)起HELLO尋址機(jī)制的節(jié)點(diǎn)可能會(huì)收到多個(gè)HELLO回復(fù)消息，節(jié)點(diǎn)接收第一個(gè)HELLO回復(fù)消息時(shí)，將發(fā)送節(jié)點(diǎn)定義為通往目的地址的下一跳路由.

3.3 控制消息的動(dòng)態(tài)發(fā)送

原始的OLSR協(xié)議控制消息是定期發(fā)送，由于機(jī)制1和機(jī)制2會(huì)利用HELLO消息和TC消息進(jìn)行臨時(shí)尋路，如果不調(diào)整控制消息的發(fā)送時(shí)間會(huì)導(dǎo)致控制開(kāi)銷增加.因此引入控制消息的動(dòng)態(tài)發(fā)送.如圖2所示，正?？刂葡橹芷谛园l(fā)送，周期為T(mén)，在[t0，t0+3T]時(shí)間段發(fā)送了4次控制消息.

圖2 控制消息發(fā)送時(shí)刻表Fig.2 Control message sending schedule

當(dāng)節(jié)點(diǎn)發(fā)送尋路控制消息，采取動(dòng)態(tài)發(fā)送機(jī)制，如圖3所示，t1時(shí)刻發(fā)送了尋址控制消息，原來(lái)t0+T時(shí)刻發(fā)送的控制消息取消，則在[t0，t0+3T]時(shí)間段發(fā)送了4次控制消息，和固定發(fā)送機(jī)制數(shù)量一樣，保證了控制開(kāi)銷總量不變.

圖3 控制消息動(dòng)態(tài)發(fā)送時(shí)刻表Fig.3 Control message dynamic schedule

4 理論性能分析

按需路由機(jī)制的引入是在沒(méi)有增加控制開(kāi)銷的前提下，使OLSR協(xié)議在發(fā)包成功率和吞吐量得到明顯改善，具體分析如下：

4.1 控制開(kāi)銷分析

改進(jìn)前的HELLO消息和TC消息都是定期發(fā)送的，改進(jìn)后采用動(dòng)態(tài)發(fā)送機(jī)制，保證控制開(kāi)銷和改進(jìn)前保持一致.

4.2 發(fā)包成功率分析

引理1.一跳鏈路節(jié)點(diǎn)移動(dòng)速度越快，鏈路中斷可能性越高.

定義：S為發(fā)包成功率，p為單跳鏈路中斷概率，L為鏈路連通概率，V為節(jié)點(diǎn)速度，n為通信跳數(shù).

由引理1可知：

p∝V

(1)

有單跳鏈路和多跳鏈路連通性關(guān)系：

(2)

發(fā)包成功率S和鏈路連通概率L成正比，則有：

S∝L

(3)

由公式(1)-公式(3)可知：發(fā)包成功率S與鏈路跳數(shù)n和節(jié)點(diǎn)移動(dòng)速度V相關(guān)，當(dāng)節(jié)點(diǎn)移動(dòng)速度越快，通信跳數(shù)越長(zhǎng)，多跳鏈路越容易中斷，發(fā)包成功率越低.

機(jī)制一在鏈路發(fā)生中斷時(shí)，及時(shí)啟動(dòng)鏈路維護(hù)機(jī)制，發(fā)送TC消息進(jìn)行尋路，維護(hù)了多跳鏈路的連通，并且該機(jī)制性能隨著鏈路跳數(shù)和節(jié)點(diǎn)速度增加而增加，因此ODR-OLSR協(xié)議在發(fā)包成功率上優(yōu)于OLSR協(xié)議，則有SODR-OLSR>SOLSR.

4.3 吞吐量分析

吞吐量定義為：成功接收數(shù)據(jù)量/總時(shí)間，則有

(4)

式(4)中：H為吞吐量，Mrcv為接收數(shù)據(jù)總量，Msend為發(fā)送數(shù)據(jù)總量，T為總時(shí)間，S為發(fā)包成功率.由于ODR-OLSR協(xié)議發(fā)包成功率更高,在發(fā)送數(shù)據(jù)量和時(shí)間相等時(shí)，有公式(5)：

HODR-OLSR>HOLSR

(5)

4.4 時(shí)延分析

由于節(jié)點(diǎn)在缺失路由或者鏈路中斷時(shí)，對(duì)于上層的數(shù)據(jù)包通常采取的先保存在緩沖區(qū)，通過(guò)公式(6)可知，發(fā)包時(shí)延由傳輸時(shí)延和緩沖區(qū)時(shí)延構(gòu)成.由于ODR-OLSR協(xié)議增加路由維護(hù)機(jī)制和路由獲取的途徑，減小了緩沖區(qū)時(shí)延，減小了數(shù)據(jù)包總時(shí)延.

Dall=Dtransfer+Dbuffer

(6)

其中Dall為總時(shí)延，Dtransfer為傳輸時(shí)延，Dbuffer為緩沖區(qū)時(shí)延.

5 仿真驗(yàn)證

選取OLSR協(xié)議，ODR-OLSR協(xié)議和文獻(xiàn)[15]中的DTN-OLSR協(xié)議作為比較對(duì)象，通過(guò)仿真實(shí)驗(yàn)分析它們?cè)诎l(fā)包成功率，時(shí)延，控制開(kāi)銷，吞吐量等指標(biāo)上的區(qū)別.

5.1 仿真參數(shù)設(shè)置

使用Windows XP平臺(tái)上的OPNET仿真軟件,設(shè)置了5個(gè)仿真場(chǎng)景，節(jié)點(diǎn)數(shù)分別為20，40，60，80，100個(gè)，節(jié)點(diǎn)在1500m×1500m的矩形區(qū)域均勻分布，節(jié)點(diǎn)最大移動(dòng)速度為10m/s,最大通信距離為200m，節(jié)點(diǎn)通信最大跳數(shù)為15跳.仿真參數(shù)設(shè)置如表1所示，MAC層使用IEEE 802.11標(biāo)準(zhǔn).每個(gè)場(chǎng)景實(shí)驗(yàn)做5次，取平均值.

表1 仿真參數(shù)設(shè)置Table 1 Simulation parameter setting

5.2 仿真結(jié)果分析

5.2.1 控制開(kāi)銷分析

圖4表明，ODR-OLSR協(xié)議在控制開(kāi)銷方面和OLSR協(xié)議基本相等.原因在于：基于HELLO消息尋址機(jī)制和基于TC消息尋址機(jī)制沒(méi)有引入新的字段攜帶目的地址，保證了控制消息報(bào)文大小和OLSR協(xié)議相等.通過(guò)控制消息的動(dòng)態(tài)發(fā)送機(jī)制能有效保證在總時(shí)間內(nèi)發(fā)送控制報(bào)文次數(shù)和OLSR協(xié)議相等，因此ODR-OLSR協(xié)議在不帶來(lái)額外開(kāi)銷的同時(shí)，提高其他指標(biāo)的性能.

圖4 控制開(kāi)銷比較Fig.4 Control overhead comparison

5.2.2 端到端時(shí)延分析

圖5表明，ODR-OLSR協(xié)議在端到端時(shí)延方面較OLSR和DTN-OLSR協(xié)議有著明顯改善.其中可以發(fā)現(xiàn)DTN-OLSR協(xié)議在時(shí)延性能上比較差，原因是DTN-OLSR協(xié)議引入機(jī)會(huì)路由機(jī)制，在無(wú)人機(jī)自組網(wǎng)環(huán)境下的通信業(yè)務(wù)一般都是低時(shí)延業(yè)務(wù)，通過(guò)增大時(shí)延來(lái)提高網(wǎng)絡(luò)的性能可能需要修正.ODR-OLSR協(xié)議引入路由維護(hù)機(jī)制，縮小了緩沖區(qū)等待時(shí)間，提高了網(wǎng)絡(luò)端到端時(shí)延性能.

5.2.3 發(fā)包成功率分析

圖6表明，DTN-OLSR協(xié)議和ODR-OLSR協(xié)議在發(fā)包成功率相比OLSR協(xié)議有較明顯改善，其中在20節(jié)點(diǎn)和40節(jié)點(diǎn)場(chǎng)景下，DTN-OLSR協(xié)議發(fā)包成功率比ODR-OLSR協(xié)議性能更加優(yōu)秀，但是在節(jié)點(diǎn)密度更高的場(chǎng)景中，發(fā)包成功率低于ODR-OLSR協(xié)議.原因是機(jī)會(huì)路由存在傳播時(shí)延或者跳數(shù)的限制，隨著節(jié)點(diǎn)密度增加，通信跳數(shù)增加，機(jī)會(huì)路由由于最大傳播時(shí)延和最大跳數(shù)限制，導(dǎo)致性能下降.而ODR-OLSR協(xié)議隨著通信跳數(shù)的增大，鏈路中斷可能性增大，增加了啟動(dòng)鏈路維護(hù)機(jī)制的概率，提高了網(wǎng)絡(luò)的性能.

圖6 成功率比較Fig.6 Success rate comparison

5.2.4 吞吐量分析

圖7表明，DTN-OLSR協(xié)議和ODR-OLSR協(xié)議在吞吐量相比OLSR協(xié)議有較明顯改善.通過(guò)控制開(kāi)銷，時(shí)延，發(fā)包成功率，吞吐量分析可知，DTN-OLSR協(xié)議是通過(guò)犧牲端到端時(shí)延為代價(jià)換取發(fā)包成功率和吞吐量的提高.但是隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，由于機(jī)會(huì)路由最大時(shí)延和最大跳數(shù)的限制，導(dǎo)致DTN-OLSR協(xié)議的性能不如預(yù)期.在無(wú)人機(jī)自組網(wǎng)環(huán)境下通信業(yè)務(wù)要求低時(shí)延，因此DTN-OLSR協(xié)議還需進(jìn)一步改進(jìn).

圖7 吞吐量比較Fig.7 Throughput comparison

5.2.5 通信跳數(shù)對(duì)發(fā)包成功率的影響

圖8 跳數(shù)對(duì)發(fā)包成功率的影響Fig.8 Impact of hops on packet success rate

圖8表明，ODR-OLSR協(xié)議從4跳-9跳相比OLSR協(xié)議成功率分別提高了：1%，1%，2%，5%，7%，9%.說(shuō)明隨著通信跳數(shù)的增加，ODR-OLSR協(xié)議對(duì)發(fā)包成功率的改善更加明顯.其中發(fā)現(xiàn)：OLSR協(xié)議的發(fā)包成功率隨著通信跳數(shù)的增加快速下降，因?yàn)樵跓o(wú)人機(jī)自組網(wǎng)中隨著通信跳數(shù)越長(zhǎng)，通信鏈路中斷的可能性越大.因此在多跳通信中引入鏈路維護(hù)機(jī)制更有使用價(jià)值.

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

本文提出一種基于按需路由的OLSR路由協(xié)議(ODR-OLSR路由協(xié)議)，當(dāng)節(jié)點(diǎn)進(jìn)行通信時(shí)，發(fā)現(xiàn)路由信息丟失，及時(shí)發(fā)送HELLO尋址消息和TC尋址消息，增加路由的獲取途徑.理論分析和仿真實(shí)驗(yàn)表明：ODR-OLSR協(xié)議在保持控制開(kāi)銷不變的基礎(chǔ)上，明顯改善時(shí)延，發(fā)包成功率和吞吐量.但是HELLO消息尋址和TC消息尋址都要依賴保留字段Reserved攜帶目的地址，Reserved字段長(zhǎng)度為16bit，標(biāo)準(zhǔn)的OLSR協(xié)議網(wǎng)絡(luò)地址為32bit，因此按需尋址機(jī)制適用于地址范圍為0～216-1的網(wǎng)絡(luò).在未來(lái)工作中，將深入研究ODR-OLSR協(xié)議地址范圍問(wèn)題，解決OLSR路由協(xié)議的不足.