基于鏈路擁塞的無人機(jī)動(dòng)態(tài)路由組網(wǎng)

黎云，李健

（四川大學(xué)電子信息學(xué)院，成都 610065）

0 引言

復(fù)雜的戰(zhàn)場(chǎng)環(huán)境導(dǎo)致單無人機(jī)無法完成戰(zhàn)場(chǎng)偵查、攻擊目標(biāo)等任務(wù)，多個(gè)無人機(jī)作戰(zhàn)將會(huì)成為一種重要的作戰(zhàn)方式。多無人機(jī)作戰(zhàn)首要任務(wù)是無人機(jī)之間自組網(wǎng)，是由多個(gè)無人機(jī)動(dòng)態(tài)組成的、無中心的多跳網(wǎng)絡(luò)，F(xiàn)ANETs（Flying Ad hoc NETworks）是一種特別的移動(dòng)自組織網(wǎng)絡(luò)（Mobile Ad hoc NETworks，MANETs），具有高速移動(dòng)的特點(diǎn)[1,2]。FANETs比MANETs拓?fù)渥兓母欤芏嗦酚蓞f(xié)議是為MANETs設(shè)計(jì)的，如BABEL[3]、OLSR（the Optimized Link-State Routing）[4,5]協(xié)議都不能對(duì)網(wǎng)絡(luò)拓?fù)涞淖兓龀隹焖俚姆磻?yīng)，因此路由的研究變成了關(guān)鍵問題，Stefano Rosati等人[6]提出了P-OLSR（Predictive-OLSR）路由協(xié)議,該協(xié)議引入了GPS，考慮到了無人機(jī)之間的相對(duì)速度，比OLSR協(xié)議能更快的適應(yīng)拓?fù)涞淖兓荘-OLSR協(xié)議引入的ETX鏈路評(píng)價(jià)機(jī)制只考慮到了探針包的接收率和節(jié)點(diǎn)之間的相對(duì)速度，并未考慮到延遲。本人依據(jù)前面的相關(guān)工作，對(duì)P-OLSR協(xié)議進(jìn)行改進(jìn)。

1 P-OLSR路由協(xié)議

Ad Hoc網(wǎng)絡(luò)中OLSR協(xié)議是目前比較流行的網(wǎng)絡(luò)協(xié)議，是基于鏈路狀態(tài)路由選擇的協(xié)議，在原始的OL?SR協(xié)議中設(shè)計(jì)沒有考慮無線鏈路的質(zhì)量，路徑的選擇是根據(jù)跳數(shù)決定，對(duì)于FANET這是不適用的。DR提出了P-OLSR算法考慮了鏈路的質(zhì)量和節(jié)點(diǎn)的相對(duì)速度，利用改進(jìn)ETX度量[7]，P-OLSR可以保證鏈路的質(zhì)量，ETX度量標(biāo)準(zhǔn)定義為：

其中R是兩個(gè)節(jié)點(diǎn)之間的路徑，η是R中的一跳路徑，?（η）是發(fā)送節(jié)點(diǎn)的接收比，ρ（η）是接收節(jié)點(diǎn)的接收比是節(jié)點(diǎn)i和節(jié)點(diǎn)j的相對(duì)速度，β是一個(gè)非負(fù)的參數(shù)。OLSR協(xié)議選擇ETX最小的路徑，可能不是跳數(shù)最短的路徑。如果R中所有的跳數(shù)都是正確無誤的（如：?（η）=ρ（η）=1），且相對(duì)速度為0，ETX（R）就等于路徑R的跳數(shù)。

接收比是通過鏈路探針來估計(jì)的，OLSR的鏈路探針通過Hello消息來實(shí)現(xiàn)。?通過指數(shù)移動(dòng)平均的方法計(jì)算，如下：

其中：

α是OLSR的一個(gè)參數(shù)，叫做鏈路質(zhì)量老化。α在準(zhǔn)確性和反應(yīng)性之間取的平衡，然后去估計(jì)接收比。

如果α很大，接收比將會(huì)反應(yīng)很慢，會(huì)非常穩(wěn)定可靠。如果α很小，接收比將會(huì)反應(yīng)地很快。

如果節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的距離在變小，相對(duì)速度就為負(fù)數(shù)，ETX則會(huì)乘一個(gè)小于1的權(quán)重系數(shù)。如果節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的距離在變大，相對(duì)速度就為正數(shù)，ETX則會(huì)乘一個(gè)大于1的權(quán)重系數(shù)。也就是說在2條一跳路徑具有相同的?和ρ會(huì)選擇節(jié)點(diǎn)在相互靠近的一跳路徑，而不是2個(gè)節(jié)點(diǎn)相互遠(yuǎn)離的一跳路徑。根據(jù)GPS獲取地理信息然后加入Hello消息中，然后就可以計(jì)算節(jié)點(diǎn)之間的相對(duì)速度了，計(jì)算相對(duì)速度的公式如下：

其中tl是最后一次接收到Hello的時(shí)間，tl-1是最后一次的上一次接收到Hello的時(shí)間，和分別對(duì)應(yīng)2個(gè)不同時(shí)間的節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的距離，由于GPS存在誤差，可以通過指數(shù)移動(dòng)平均的方法進(jìn)行處理，方法如下：

其中γ是P-OLSR的一個(gè)參數(shù)。但是P-OLSR協(xié)議考慮了節(jié)點(diǎn)的移動(dòng)狀態(tài)，所利用的ETX機(jī)制只考慮了探針包丟包的狀態(tài)，并沒有考慮探針包的延遲。

2 基于擁塞的P-OLSR

原始的ETX并未考慮探針包的延時(shí)，探針包的延遲，可以反應(yīng)出鏈路的質(zhì)量，對(duì)ETX的探針包進(jìn)行修改，如下：

其中：

其中p為P-OLSR的參數(shù)，Δtl為最后一次接收到探針包的延時(shí)，Δtl-1為最后一次的前一次接收到探針包的延時(shí)。Δt的計(jì)算如下：

其中trl為探針包發(fā)送的時(shí)間，tsl為探針包接收的時(shí)間。在相對(duì)速度為0的情況下，如果二個(gè)一跳鏈路具有相同的?和ρ，修改后的ETX會(huì)選擇延時(shí)在減小的鏈路，從而可以提前避免鏈路的擁堵。

3 仿真分析

3.1 仿真平臺(tái)

利用NS-2仿真平臺(tái)[8]來仿真OLSR、P-OLSR、POLSR的協(xié)議改進(jìn)，在不同的運(yùn)動(dòng)速度下。NS-2是個(gè)開源的軟件，NS-2是用C++和OTCL編寫的，能夠仿真不同的網(wǎng)絡(luò)傳輸協(xié)議，例如：TCP、UDP[9]，還能方便添加各種路由協(xié)議如：OLSR[10]。

3.2 仿真參數(shù)

表1

3.3 性能參數(shù)

本文選取了分組投遞率和平均時(shí)延對(duì)三個(gè)路由協(xié)議的性能進(jìn)行比較，分組投遞率定義為數(shù)據(jù)包成功傳輸?shù)谋壤扔诳偣步邮盏降臄?shù)據(jù)包比上總共發(fā)送的數(shù)據(jù)包。分組投遞率的值越大，協(xié)議的性能越好。端到端的延遲定義為數(shù)據(jù)包發(fā)送到目的點(diǎn)所花時(shí)間的平均值，端到端的延遲越小，協(xié)議的性能越好。

3.4 仿真結(jié)果

取α=0.2,γ=0.04,β=0.004,p=0.5的情況下，分別在不同的速度下重復(fù)10次取平均值，OSLR，P-OL?SR，P-OLSR-IMPROVE的分組投遞率的對(duì)比如圖1所示，P-OLSR，P-OLSR-IMPROVE協(xié)議的分組投遞率都好于原始協(xié)議OSLR，P-OLSR-IMPROVE在6個(gè)速度仿真中，5個(gè)速度點(diǎn)優(yōu)于P-OSLR。OSLR，P-OLSR，P-OLSR-IMPROVE的端到端的時(shí)延的對(duì)比如圖2所示，P-OLSR，P-OLSR-IMPROVE協(xié)議的端到端的時(shí)延都好于原始協(xié)議OSLR，同時(shí)與P-OLSR協(xié)議比較，POLSR-IMPROVE的時(shí)延更低，因?yàn)?P-OLSR-IM?PROVE選擇了擁塞較小的鏈路，因此時(shí)延會(huì)較P-OL?SR會(huì)下降。

圖1 OLSR、P-OLSR、P-OLSR數(shù)據(jù)分組到達(dá)率

圖2 OLSR、P-OLSR、P-OLSR端到端的延遲

4 結(jié)語(yǔ)

本文在ETX的算法上考慮了鏈路的延遲，提出了改進(jìn)后的路由協(xié)議。仿真實(shí)驗(yàn)表明，改進(jìn)后的網(wǎng)絡(luò)能提前避開擁塞的鏈路，在數(shù)據(jù)分組投遞率上有一定的提升，在端到端的延遲上有較大的提升，改進(jìn)后的協(xié)議更加適合無人機(jī)自組網(wǎng)。

參考文獻(xiàn)：

[1]Oubbati O S,Lakas A,Zhou F,et al.A Survey on Position-based Routing Protocols for Flying Ad Hoc Networks（FANETs）[J].Vehicular Communications,2017.

[2]I.Bekmezci,O.K.Sahingoz,S.Temel.Flying Ad-Hoc Networks（FANETs）:A Survey.Ad Hoc Networks,2013（11），3：1254-1270.

[3]J.Chroboczek.The Babel Routing Protocol.RFC 6126,2011.

[4]T.Clausen，P.Jacquet.Optimized Link State Routing Protocol（OLSR）.RFC 3626,2003.

[5]C.Dearlove,T.Clausen,P.Jacquet.The Optimized Link State Routing Protocol Version 2.IETF Draft RFC Draft-ietf-manet-olsrv2-10,2009.

[6]Rosati S,Kruzelecki K,Heitz G,et al.Dynamic Routing for Flying Ad Hoc Networks[J].IEEE Transactions on Vehicular Technology,2016,65（3）:1690-1700.

[7]D.S.J.De Couto,D.Aguayo,J.Bicket,R.Morris.A High-Throughput Path Metric for Multi-hop Wireless Routing.in Proceedings of the 9th Annual International Conference on Mobile Computing and Networking,ser.MobiCom'03.New York,NY,USA:ACM,2003：134-146.

[8]ZhibinWu,Rutgres University,Available:http://www.winlab.rutgres.edu/~zhibinwu/html/network_simulator_2.html,2007.

[9]Issariyakul,Teerawat,Hossain,Ekram.Introduction to Network Simulators[online]Available.http://www.springer.com/engineering/signals/book/978-0-3871759-3,2009.

[10]Francisco J.Ros,OLSR.Available:http://masimum.inf.um.es/fjrm/development/um-olsr/,September,2013.