一種基于位置信息的速度加權(quán)OLSR算法*

王旭東 ，米志超 ，姜雨卿，趙 寧

（1.陸軍工程大學(xué) 通信工程學(xué)院，江蘇 南京 210007；2.中國電子科技集團公司第二十八研究所，江蘇 南京 210007）

0 引 言

由于電子、傳感器和通信技術(shù)等方面的技術(shù)快速進步，無人機系統(tǒng)得到了不斷發(fā)展和提高。由于具有功能多樣性、靈活性、易于安裝部署和相對較小的運營費用等優(yōu)勢，無人機在軍事和民用領(lǐng)域得到廣泛應(yīng)用。雖然單無人機系統(tǒng)已經(jīng)使用了幾十年，相關(guān)技術(shù)與應(yīng)用已經(jīng)不斷完善，但是使用一組小型多無人機的協(xié)同應(yīng)用，將具有可生存性更強、可擴展性更高、完成任務(wù)更快、雷達截面小更難被發(fā)現(xiàn)等優(yōu)勢。然而，多無人機系統(tǒng)也存在獨特的挑戰(zhàn)，其中最突出的一個設(shè)計問題是通信。為此，提出了無人機自組網(wǎng)（UAV Ad-Hoc Network，UANET）。正如在文獻[1]中指出的，UANET是移動自組網(wǎng)（Mobile Ad-Hoc Network，MAENT）的一個特例，具有高度的移動性。

UANET由無人機節(jié)點構(gòu)成，自動組成多跳無線網(wǎng)絡(luò)。由于無人機的特點導(dǎo)致了網(wǎng)絡(luò)節(jié)點的高速移動性，因此傳統(tǒng)的移動自組網(wǎng)中的路由協(xié)議不能直接應(yīng)用于UANET，不能提供可靠的通信保障。本文在傳統(tǒng)OLSR[2-3]（Optimized Link-State Routing）協(xié)議的基礎(chǔ)上，提出了一種改進的路由算法，即使在高速動態(tài)的無人機網(wǎng)絡(luò)中也能提供可靠的通信服務(wù)。其中，關(guān)鍵點是利用位置信息計算節(jié)點間的相對移動速度，然后使用速度因子加權(quán)預(yù)期傳輸計數(shù)（ETX）度量。因此，將本協(xié)議稱為速度加權(quán)的OLSR協(xié)議（Speed Weighted OLSR，SW-OLSR）。

1 無人機平臺

本文使用的無人機如圖1所示，為小型四旋翼無人機。無人機為組裝無人機，主要包含GPS模塊、飛控模塊、通信模塊（樹莓派）和外置USB WiFi（802.11b/g/n）天線。本實驗使用樹莓派3B作為無人機的通信模塊。樹莓派是一種嵌入式計算機，其內(nèi)部運行嵌入式Linux系統(tǒng)。使用該嵌入式計算機，可建立無線多跳網(wǎng)絡(luò)，并通過外置USB WiFi天線來實現(xiàn)無人機間通信。飛控模塊和GPS模塊通過串口與樹莓派連接，因此路由協(xié)議可以獲得該無人機的實時位置信息用于計算相對速度信息。此外，樹莓派可以轉(zhuǎn)發(fā)來自地面站的控制指令給飛控模塊，用于控制飛行姿態(tài)、速度、航向和起落等狀態(tài)。

2 路由協(xié)議設(shè)計

為了減少多無人機間協(xié)同通信對地面站或衛(wèi)星等基礎(chǔ)通信設(shè)施的依賴，UANET將每個無人機作為網(wǎng)絡(luò)中的節(jié)點。各節(jié)點間能夠相互收發(fā)數(shù)據(jù)，自動連接搭建起一個無線移動多跳網(wǎng)絡(luò)。該網(wǎng)絡(luò)中，每個節(jié)點都集成了發(fā)射器、接收器和路由器的功能，以多跳通信的方式把數(shù)據(jù)傳遞給遠處的節(jié)點。在實際應(yīng)用中，由于無人機節(jié)點快速和不穩(wěn)定的移動，UANET的網(wǎng)絡(luò)拓撲結(jié)構(gòu)通?？焖僮兓夜?jié)點必須通過自動更新其路由表做出反應(yīng)。因此，在UANET中采用快速且主動性的路由協(xié)議至關(guān)重要[4-5]。在MANET中，最常見的主動路由協(xié)議有OLSR、DSDV（Destination Sequenced Distance Vector，目的序列距離矢量）等。但是，它們都無法跟蹤UANET的快速拓撲變化。為此，設(shè)計了一種基于位置信息的快速OLSR算法，利用位置信息快速計算節(jié)點間相對速度，從而得到加權(quán)的ETX輔助路由決策。

圖1 實驗中用到的無人機

2.1 鏈路質(zhì)量估計

傳統(tǒng)的OLSR協(xié)議是基于鏈路狀態(tài)路由協(xié)議的改進。協(xié)議設(shè)計時沒有考慮無線鏈路的質(zhì)量，路由選擇基于跳數(shù)度量值，在移動無線網(wǎng)絡(luò)中明顯不足。然而，可以使用ETX[6]度量值來將無線鏈路的鏈路質(zhì)量考慮在內(nèi)。

它的定義如下：

R是兩個節(jié)點間存在的所有路由，η是路由R中的一跳，rf(η)是前向接收比率，即一個數(shù)據(jù)包通過η跳后被成功接收的概率。rf(η)是反向接收比率，即相應(yīng)的反向數(shù)據(jù)包被成功接收的概率。換言之，ETX估計是將數(shù)據(jù)包從源節(jié)點傳送到其最終目的節(jié)點所需的預(yù)期傳輸次數(shù)（包括重傳）。路由協(xié)議通過最小的ETX值選擇路由，但這不一定是跳數(shù)最少的路徑。如果形成路由R的所有跳數(shù)都是無丟包的（即rf(η)=rr(η)=1），則ETX(R)就等于路由R的跳數(shù)總和。

通常，通過鏈路探測消息來估計接收比率。在路由算法中使用控制消息Hello作為鏈路探測消息，前向接收比率使用指數(shù)移動平均來計算

其中：

式中的α是算法中的參數(shù)。注意，α是鏈路質(zhì)量估計的準(zhǔn)確性和響應(yīng)速度之間的權(quán)衡。α值越大，接收比率將取平均值，以產(chǎn)生更穩(wěn)定可靠的鏈路質(zhì)量估計；而α值越小，則接收比率更快，便于跟蹤當(dāng)前的鏈路質(zhì)量。反向接收比率是通過接收到的Hello數(shù)據(jù)包獲得的，上述計算得到的前向接收比率將記錄在Hello數(shù)據(jù)包中發(fā)送給鄰居節(jié)點。鄰居節(jié)點在收到Hello數(shù)據(jù)包后讀取該值作為本節(jié)點的反向接收比率，再結(jié)合本節(jié)點的前向接收比率計算ETX。

2.2 速度加權(quán)的ETX

ETX是準(zhǔn)靜態(tài)無線Ad-Hoc網(wǎng)絡(luò)中鏈路質(zhì)量的有效衡量標(biāo)準(zhǔn)，但其反應(yīng)性較差，不足以應(yīng)對高度動態(tài)的無線Ad-Hoc網(wǎng)絡(luò)，如UANET。由于指數(shù)移動平均值的計算導(dǎo)致節(jié)點在注意到無線鏈路質(zhì)量變化之前需要消耗一定的時間，將導(dǎo)致在此期間將繼續(xù)在該斷開的鏈路上傳輸數(shù)據(jù)包，從而可能導(dǎo)致通信服務(wù)中斷。為了解決這個問題，引入位置信息來改善路由協(xié)議。為了準(zhǔn)確判斷鏈路質(zhì)量可能的變化，使用節(jié)點間的相對速度來加權(quán)ETX。

修改后的ETX為：

如果節(jié)點i和節(jié)點j的移動趨勢是相互靠近彼此，則相對速度是一個負值，此ETX會被一個小于1的因子加權(quán)；否則，如果節(jié)點i和節(jié)點j移動相互遠離，則相對速度是正值，ETX會被一個大于1的因子加權(quán)。即如果在前向接收比率和反向接收比率相同的情況下，如果兩節(jié)點相互靠近的路由效果要比節(jié)點相互遠離的路由效果更好，即在相同的情況下，節(jié)點更傾向于選擇一個正在靠近自己的節(jié)點來路由數(shù)據(jù)包。

為了計算速度加權(quán)的ETX，需要使用位置信息，節(jié)點將自己的位置坐標(biāo)存放于Hello數(shù)據(jù)包中發(fā)送給鄰居節(jié)點。因此，需要在原有的Hello數(shù)據(jù)包中添加字段，用于存放位置坐標(biāo)。節(jié)點每次收到Hello消息后，便可以計算一次ETX，同時更新位置信息。在tl時刻節(jié)點i和節(jié)點j之間的瞬時相對速度計算如下：

3 協(xié)議設(shè)計細節(jié)

為了實現(xiàn)設(shè)計的路由算法，通過擴展鏈路質(zhì)量，加入了鏈路質(zhì)量感知和ETX指標(biāo)，擴充Hello消息，增加了節(jié)點的位置信息，使每個節(jié)點都知道其周圍鄰居節(jié)點的位置，并根據(jù)式（4）計算相應(yīng)的速度加權(quán)ETX，通過Hello和TC消息在網(wǎng)絡(luò)中共享該信息。

圖2展示了修改后的Hello數(shù)據(jù)包格式，灰色標(biāo)注的表示添加或修改的部分。首先，添加了三段4字節(jié)的空間用于存放節(jié)點的位置坐標(biāo)（包括經(jīng)度、緯度和高度），之后修改原有字段用于存放前向接收比rf(η)、反向接收比rr(η)速度加權(quán)的ETX的分子部分。修改后的Hello消息比原始的Hello消息略大，與網(wǎng)絡(luò)中的節(jié)點數(shù)無關(guān)。Hello消息被封裝進UDP報文中，而后UDP報文又被封裝進IP數(shù)據(jù)包中，之后再封裝進802.11幀中。在中型大型網(wǎng)絡(luò)中，修改后增加的字節(jié)大小與幀的總大小相比可以忽略不計。

圖1 實驗中用到的無人機

圖2 修改后的Hello數(shù)據(jù)包格式

圖3 展示了修改后的TC消息格式，灰色標(biāo)注的是修改的部分。修改原有字段空間，用于存放前向接收比rf(η)、反向接收比rr(η)以及速度加權(quán)的ETX的分子部分。修改后的TC消息與原始TC消息大小一致，沒有增加額外的字節(jié)。

4 實 驗

分別進行了兩個部分的實驗，以驗證路由協(xié)議的性能。第一部分實驗是在計算機上進行的網(wǎng)絡(luò)仿真實驗，使用EXata 5.1仿真軟件，驗證大型網(wǎng)絡(luò)環(huán)境中的SW-OLSR協(xié)議性能，并與原始OLSR協(xié)議做比較。第二部分是室外無人機飛行測試實驗，驗證無人機和地面站之間的通信性能，以及在快速鏈路切換中路由協(xié)議的性能。

4.1 仿真實驗

仿真實驗基于仿真軟件進行。Exata是QualNet開發(fā)商推出的一款全新的無線仿真系統(tǒng)，可以更快更逼真地模擬時下不斷發(fā)展的通信網(wǎng)絡(luò)。Exata采用最優(yōu)化的網(wǎng)絡(luò)模型和并行計算技術(shù)，支持協(xié)議效果仿真和網(wǎng)絡(luò)服務(wù)仿真。同時，Exata協(xié)議模型的精確程度，是其他仿真軟件達不到的。本仿真實驗采用該軟件進行建模與仿真。為盡可能提高本實驗結(jié)果的可靠性，無人機各參數(shù)的設(shè)置盡可能貼近當(dāng)前市面上常見無人機的工作參數(shù)。具體參數(shù)配置如表1所示。

表1 仿真參數(shù)配置

實驗中使用64個無人機節(jié)點，采用全向天線，其通信范圍為500 m。MAC協(xié)議采用CSMA協(xié)議，節(jié)點均勻分布在4 km×4 km的場景中，節(jié)點采用Random Waypoint移動模型。選擇32個節(jié)點兩兩為一組，設(shè)置了16個CBR（Constant Bit Rate）業(yè)務(wù)數(shù)據(jù)流，持續(xù)時間25 min。仿真持續(xù)時間為30 min。分別使用OLSR和SW-OLSR路由協(xié)議進行100次獨立仿真測試，然后對比協(xié)議性能。

第一組實驗中，固定節(jié)點速度10 m/s，CBR業(yè)務(wù)中數(shù)據(jù)流量大小為4 kb/s，Hello間隔分別取值2 s、1 s和0.5 s，實驗結(jié)果如圖4所示。豎線條形圖表示SW-OLSR協(xié)議的平均吞吐量，橫線條形圖表示OLSR協(xié)議的平均吞吐量。實驗結(jié)果表明，在不同Hello間隔下，使用SW-OLSR協(xié)議的平均吞吐量較使用OLSR協(xié)議的平均吞吐量均有明顯提升。在HI為0.5 s時，平均吞吐量提升4.3%；在HI為1 s時，平均吞吐量提升7.1%；在HI為2 s時，平均吞吐量提升17.9%。這表明隨著Hello間隔的增大，兩個協(xié)議的結(jié)果差距也在變大。這是因為Hello間隔增大，OLSR協(xié)議反應(yīng)變慢，不能適應(yīng)拓撲的快速變化，導(dǎo)致部分鏈路丟失而造成路由不可用，從而引起吞吐量的降低。而SW-OLSR協(xié)議引入速度加權(quán)的ETX，同時使用節(jié)點位置信息，在某些情況下可以在鏈路丟失前提前切換到質(zhì)量更優(yōu)的路徑上路由數(shù)據(jù)包，從而可以適應(yīng)拓撲快速變化的情況，獲得更高的網(wǎng)絡(luò)吞吐量。

圖4 不同Hello間隔下兩個協(xié)議的平均吞吐量對比

在第二組實驗中，固定Hello間隔為2 s，CBR業(yè)務(wù)數(shù)據(jù)流量大小為4 kb/s，改變節(jié)點移動速度為5 m/s、10 m/s、15 m/s和20 m/s，實驗結(jié)果如圖5所示。其中，黑色三角折線表示SW-OLSR的實驗結(jié)果，黑色方形折線表示OLSR的實驗結(jié)果。實驗結(jié)果表明，隨著節(jié)點移動速度的增加，兩個協(xié)議的平均吞吐量均在減少。這是因為隨著節(jié)點移動速度增加，留給節(jié)點間彼此通信的時間減少，多數(shù)時間節(jié)點都處于孤立狀態(tài)，造成數(shù)據(jù)包丟失嚴(yán)重，最終導(dǎo)致吞吐量的下降。結(jié)果還表明，在不同的移動速度下，SW-OLSR協(xié)議的表現(xiàn)均優(yōu)于OLSR協(xié)議。在4組實驗結(jié)果中，吞吐量分別提升18.1%、17.9%、17.1%和16.3%，性能的提升得益于SW-OLSR協(xié)議可以提前切換到鏈路質(zhì)量更好的路徑上，從而可以路由更多的業(yè)務(wù)數(shù)據(jù)包。這表明SW-OLSR協(xié)議在節(jié)點移動速度較快時也能具有良好的性能表現(xiàn)。

圖5 不同速度下兩協(xié)議的平均吞吐量對比

第三組實驗中，固定Hello間隔為2 s，節(jié)點移動速度為10 m/s，改變CBR業(yè)務(wù)數(shù)據(jù)的流量大小為4 kb/s和8 kb/s，實驗結(jié)果如圖6所示。

圖6 不同CBR流量大小下兩協(xié)議的平均吞吐量對比

其中，格子紋條形圖表示SW-OLSR協(xié)議的實驗結(jié)果，斜線條形圖表示OLSR協(xié)議的實驗結(jié)果。實驗結(jié)果表明，當(dāng)增大CBR流量時，獲得的平均吞吐量隨之增大，這是因為增大CBR流量后，在節(jié)點有效的通信時間內(nèi)傳遞的業(yè)務(wù)數(shù)據(jù)更多，從而可以獲得更大的吞吐量。結(jié)果還表明，在不同的CBR流量下，SW-OLSR協(xié)議的表現(xiàn)均優(yōu)于OLSR協(xié)議，在4 kb/s時性能提升17.9%，在8 kb/s時性能提升22.4%，在16 kb/s時性能提升24.8%。

4.2 室外實驗

在室外進行快速鏈路切換實驗，場景如圖7所示。1、2、3號無人機和地面站均以Ad Hoc組網(wǎng)方式連接在同一個無線網(wǎng)絡(luò)環(huán)境中，地面站到1、2號人機均是1跳可達，到3號無人機需要2跳，圖中圓形區(qū)域表示無人機的通信范圍。1、2號無人機固定懸停在彼此的通信范圍之外，地面站在二者通信范圍交集的Ⅱ區(qū)域下方。3號無人機位于1號通信范圍Ⅰ區(qū)域左上遠處。實驗中，3號需要沿著圖中標(biāo)注的移動方向勻速向右飛行，經(jīng)過Ⅱ區(qū)域最終到達Ⅲ區(qū)域邊緣懸停，期間大約花費20 s時間。實驗開始時從地面站向3號無人機持續(xù)發(fā)送ping數(shù)據(jù)包，直到3號無人機最后懸停，觀察反饋的往返時間基本未出現(xiàn)波動。反復(fù)測試10次，結(jié)果基本一致。之后將所有節(jié)點和地面站的路由協(xié)議都換成OLSR協(xié)議，再進行與之前相同的實驗。結(jié)果表明，大約在13 s出現(xiàn)短暫的鏈路不可達情況，15 s后恢復(fù)正常。反復(fù)測試10次，結(jié)果基本一致。

圖7 鏈路切換的場景

分析上述實驗結(jié)果表明，使用OLSR協(xié)議時，在3號無人機飛出Ⅱ區(qū)域進入Ⅲ區(qū)域后，出現(xiàn)了鏈路中斷現(xiàn)象。這是由于超出1號無人機通信范圍后，需要重新找路計算路由，在與2號無人機建立鏈路之后恢復(fù)正常通信。而在使用SW-OLSR協(xié)議時并沒有這種現(xiàn)象，這是因為3號無人機在進入Ⅱ區(qū)域之后，判斷2號無人機正在靠近自己，而1號無人機正在遠離自己，所以提前將鏈路切換到質(zhì)量更好的2號上。因此，在拓撲快速變化的情況下，使用SW-OLSR協(xié)議的性能要優(yōu)于使用OLSR協(xié)議的性能。同時，證明無人機節(jié)點和地面站組成的網(wǎng)絡(luò)中，SW-OLSR協(xié)議運行正常，能保證正常的通信服務(wù)。

5 結(jié) 語

由小型無人機組成的無人機自組網(wǎng)具有易操作、快速部署、價格低廉等特點，使得它們在很多領(lǐng)域都廣受關(guān)注。由于節(jié)點的高移動性，維持無人機之間的通信鏈路是一項具有挑戰(zhàn)性的任務(wù)。因此，本文設(shè)計實現(xiàn)了一種基于位置信息的速度加權(quán)OLSR（SW-OLSR）協(xié)議，通過使用無人機的位置信息計算速度加權(quán)的ETX輔助路由決策，適用于拓撲快速變化的網(wǎng)絡(luò)環(huán)境。首先，使用仿真平臺通過三組實驗對比OLSR協(xié)議，在不同的移動速度下、不同的流量下、不同的路由控制消息發(fā)送頻率下，在網(wǎng)絡(luò)吞吐量方面均有不同程度的提升，說明本協(xié)議性能更好地適應(yīng)了大型網(wǎng)絡(luò)拓撲快速變化的情況，性能優(yōu)于傳統(tǒng)OLSR協(xié)議。之后，使用小型四旋翼無人機搭建的無線多跳自組織網(wǎng)絡(luò)驗證了協(xié)議的可行性，表明該協(xié)議性能優(yōu)于傳統(tǒng)OLSR協(xié)議。