延遲容忍網絡中緊急狀態驅動的多擺渡機飛行控制算法

張小亮，王立松，劉 亮

(南京航空航天大學 計算機科學與技術學院，南京 210000)E-mail ：zhangxiaoliangnjit@163.com

1 引 言

多無人機相互協作被應用于工業、農業、軍事、搶險救災等領域，而多無人機的通信是多無人機系統的設計的最重要的問題之一.基于如地面中繼站、衛星等的基礎設施實現網絡有很多限制，一般采用飛行自組織網絡(Flying Ad-Hoc Networks—FANET)實現多無人機之間的通信[1-3].由于無人機快速移動的特性，導致無人機自組網會出現隨機的頻繁的中斷.延時容忍網絡(Delay-tolerant Networking—DTN)原則上能夠解決這個問題.DTN因為具有“存儲—攜帶—轉發”的特性，所以適用在節點間沒有端到端通信的情況[4,5].

智能的路徑規劃配合路由協議能夠有效的減少包的損失和消息延遲等[6].關于擺渡節點的路徑規劃問題，近年來有不少研究.文獻[7]中首先提出了MF機制，并針對普通節點是靜止的情況設計一個擺渡節點路線.指出該問題是旅行商(TSP)問題，并用通用方法解決TSP問題.文獻[8]中在文獻[7]中提出的消息擺渡機制的基礎上進行擴展.根據擺渡節點或者普通節點主動運動，將消息擺渡機制分為普通節點發起消息擺渡機制、擺渡節點發起消息擺渡機制.文獻[9]對DTN中多擺渡節點路線進行設計.將擺渡節點間交互的方式分為三種情況提出算法來求解路徑.文獻[10]中將移動的任務節點按照地理位置進行分簇，然后設計擺渡節點路線穿過簇的中心.文獻[11]中每次都用最小概率去和每個移動節點接觸.移動節點-擺渡節點接觸概率又反過來決定了下一輪的擺渡節點的路線.文獻[12]中是基于圖像獲取率的獎勵函數來選取無人機的中繼航路點，然后還是轉化TSP問題求解路徑.文獻[13]提出基于預測和地理位置信息的路由算法，針對典型搜救場景這一小型任務進行模擬實驗，擺渡機按照預設的航路點在執行任務區域和地面站之間乒乓方式飛行.文獻[14]針對無人機采集圖像任務，采用了靜態和在線的路徑設計方法.

我們發現，目前擺渡節點的路徑設計方法主要針對稀疏節點的網絡[7-9，12]，且在TSP求解航路點問題基礎上提出.在設計出航路點后，擺渡節點通常按照航路點作簡單循環方式飛行.但是該飛行方式下，擺渡機無法根據網絡中任務機節點的擁塞狀況及位置信息做出及時調整，從而導致平均消息延遲過長.在時間關鍵任務中，數據傳輸延遲是考慮的關鍵因素[15].然而在小型搜救任務等小面積網絡中，我們可以應用基于一跳的低通量網絡傳遞更多的控制指令等消息來進行實時控制[13，16].所以在設計出擺渡機航路點之后，對于飛行方式進一步優化是有必要的.

本文針對無人機的典型搜救任務設計了一個小面積DTN的單播消息擺渡模型，在已有的航路點基礎上設計了一種緊急狀態驅動的擺渡機飛行控制機制.通過地面站的調度和分配，實時控制擺渡機的飛行方向.從而緩解了該場景下的擁塞問題，降低了消息平均延遲.本文主要分為以下幾個部分：第二節介紹了小面積DTN的網絡模型.第三節從地面站端和擺渡機端介紹了緊急狀態驅動的擺渡機飛行控制算法.第四節針對任務機移動場景進行仿真實驗并分析實驗結果.第五節對全文進行總結.

2 網絡模型

2.1 混合網絡技術

本文參考已有的混合網絡技術設計小面積DTN的整體網絡構架.文獻[13,16]中采用了高通量和低通量混合網絡技術進行無線通訊.其中低通量網絡傳遞較小的數據量，如GPS數據，控制消息，還有本文的緊急信號等.高通量網絡能傳遞較大的數據量，如圖像數據.

低通量網絡可以采用XBee-PRO(IEEE 802.15.4)技術.它的覆蓋半徑長達1.5km，低通量(小于80kbit/s，所有無人機共享)能傳遞控制消息，遙感數據，消息接收確認等消息.XBee-PRO將所有無人機和地面站連接，所有無人機的GPS數據(經度，維度，高度)，方向，速度等數據在無人機和地面站范圍內按照一定頻率廣播.

高通量網絡可以采用Wi-Fi(IEEE 802.11n)技術.它是一種范圍短，高通量的通信技術.其通信范圍為200-300m，UDP通量為80-100Mbit/s.為了防止和XBee-PRO干擾，Wi-Fi頻率可以與XBee-PRO設置不同的頻率.高通量網絡主要傳遞圖像等較大的數據.

2.2 場景建模

在如搜救之類的任務中，任務區域通常是遠離地面站的一片區域.執行任務的任務機在此任務區域內的一小片區域按照一定軌跡飛行來收集該子區域的圖像或者其他數據.擺渡機按照規定的路線在任務區域和地面站之間來回飛行，最終將任務機收集到的消息傳遞到地面站.針對典型搜救場景，我們設計了小面積DTN單播消息擺渡(Message Ferrying-MF)模型.MF機制首先在文獻[7]提出，為了解決高度分區網絡中擺渡節點的路徑規劃問題.我們認為在諸如搜救等任務中可以借用該思想，但是和之前的MF機制又有區別.

假設N=1,2,…，k是k個收集消息且需要將傳遞消息到地面站g的任務機的集合.F=f1，f2，…，fl是l個負責將任務機消息傳遞到地面站的擺渡機的集合.無人機的高通量網絡的通訊半徑為r.D=D1，D，…，Dk是所有任務機的移動區域的集合.任務機飛行區域的最小外接圓為E，半徑為R，圓心為e.網絡示意圖如圖1所示.

圖1 小面積DTN中消息擺渡模型Fig.1 Message ferrying model in small-area DTN

小面積DTN的單播MF網絡有以下性質：

性質1.地面站g距離任務機飛行區域D的最遠距離Rmax小于等于低通量網絡的覆蓋半徑Rl，記為：Rmax≤Rl.

性質2.擺渡機一次循環飛行，通訊圓覆蓋的面積Ac小于等于覆蓋區域D的最小外接圓面積Ae，記為：Ac≤Ae.

2.3 延遲建模

假設ft(i)是t時間分配給任務機i的擺渡機，擺渡機按照Tft(i)路線飛行，wig是任務機i等待擺渡機飛至任務機附近將消息全部接收的等待時間，cij是擺渡機從任務機i到地面站的時間，Δd表示由于任務機移動帶來的時間差.如果任務機i的消息不經過其他節點而完全由擺渡機傳遞到地面站g，則任務機節點i的最大消息延遲的digmax可以表示為：

digmax=wig+cig+Δd

(1)

因為任務機在傳播過程中能通過其他無人機進行消息擺渡，所以則任務機節點i的消息延遲dig和digmax有如下關系：

dig≤digmax

(2)

假設lft(i)iTft(i)表示擺渡機ft(i)按照Tft(i)路線從當前位置到任務機i的距離，ligTft(i)表示擺渡機ft(i)按照Tft(i)路線從任務機i到地面站g的距離，無人機的飛行速度為v，由(1)得：

(3)

由于Δd是任務機移動帶來的時間差，任務機是執行主要收集數據任務的無人機，我們一般不能改變.所以本文考慮優化公式(3)中前兩項的值.

3 基于緊急狀態的多擺渡機飛行控制方法

3.1 基本思想

圖2 算法示意圖Fig.2 Algorithm diagram

如本文的飛行控制算法是指擺渡機的飛行軌跡控制算法.如圖2所示，假設G、A、B是擺渡機的航路點.其中G為地面站，即消息的目的地.Si表示任務機.Fi表示擺渡機.r為擺渡機的通訊半徑，a、b是以S1為圓心，r為半徑做出的圓與AB的交點.Rl表示低通量網絡的覆蓋圓半徑，地面站能夠接收到該圓內節點發送的GPS數據和本文中的緊急信號等消息.擺渡機F1按照G→A→B→G路徑順時針方向循環飛行，F2按照G→D→B→G路徑順時針方向循環飛行.任務機的消息數在不停的增長，如果不及時往地面站方向轉移，則會導致消息的平均延遲過長.我們研究的問題是在各航路點已定的前提下對飛行方式進行優化，從而來減少消息的平均延遲.

傳統方式采用丟包或者接收速度的方法來處理DTN中的擁塞[17].本文利用主動使擺渡機飛行的方法來緩解擁塞.算法基本思想如下：

首先，對于單架擺渡機本身，如果擺渡機F1此時在(3，0)順時針飛行.若按照原方向做循環飛行，那么將S1任務機的消息接收到返回地面站G需要走12的路程.在本文方法中，當S1中的消息數超過預警值時，S1此時置為緊急狀態.然后使與其配對的擺渡機此時調轉方向，即按路徑F1→B→b.將消息接收后，然后再選擇一個最短距離路徑，即b→B→G，那么該消息到達地面站總共所走的距離為7.所以該實時控制的方法，大大減少了時間.

(4)

易證明，digmax+≤digmax.從而證明及時調整航向有利于減少消息延遲.

其次，我們借用了操作系統中的先來先服務的調度思想來處理多架任務機緊急的情況.當此時有多個緊急狀態的任務機需要分配擺渡機，那么地面站優先分配為發生時間較早的那一架任務機分配擺渡機.如果同時發生緊急狀態，優先為分配編號較小的那一架任務機分配擺渡機.

圖3 單位時間處理時序圖Fig.3 Processing sequence diagram in unit of time

為了更加清楚的表達本文所提方法的工作原理，我們用SysML對算法執行過程進行建模.網絡中有3個對象：地面站，任務機，擺渡機.每個單位時間中，首先各無人機檢測本身的消息存儲數，在本機進行判斷緊急或非緊急.并通過低通量網絡發送緊急或者非緊急信號至地面站.地面站更新各無人機的狀態并根據先來先服務的思想為任務機分配擺渡機，然后將改變Locked位指令信息發送至擺渡機.最后擺渡機根據飛行控制算法做出調整后飛行△t時間.時序圖如圖3所示.下文將給出相關定義并圍繞時序圖中的地面站更新緊急任務列表算法，先來先服務思想的分配算法以及擺渡機中飛行控制算法等方面進行詳細的闡述.

3.2 地面站集中式處理算法

本文采用地面站集中式結構管理整個網絡無人機的緊急狀態以及做出相應的控制.隨著時間的推移，每架無人機的狀態會發生改變，更新緊急狀態是擺渡機飛行控制的基礎.地面站控制算法中所提到的相關數據結構以及相關名詞解釋如下：

定義1.緊急任務機列表(emergeSearchList) 是按照緊急狀態產生時間順序存放當前網絡中所有的緊急狀態的任務機編號的列表.

定義2.緊急任務機-擺渡機配對列表(emergeMap)是存放緊急狀態任務機編號以及與其配對的擺渡機編號的鍵值對列表.

定義3.緊急擺渡機列表(emergeFerryList)是存放緊急狀態擺渡機編號的列表.

定義4.緊急狀態是無人機中消息存儲數超過預警值后無人機所處的狀態.

定義5.Locked位是任務機和擺渡機相互間是否能夠配對的標志位.當擺渡機分配給緊急狀態任務機時，擺渡機和任務機的Locked位置為true.當擺渡機中的消息存儲數超過預警值，則將擺渡機和原先與之配對的任務機解鎖，即將任務機和擺渡機的Locked位置為false.

3.2.1 更新緊急列表算法

更新算法主要分為取消非緊急狀態項和增添緊急狀態項兩部分.原先緊急狀態的無人機中的消息數降低到0，我們將取消各列表中相應的緊急狀態項.當無人機中的消息數超過規定的預警值，而且之前不在列表中，將要添加相應的項.

添加緊急狀態項分為以下步驟.

1)更新emergeFerryList.在emergeFerryList中添加新項時，我們需要作出特殊處理.因為當擺渡機中的消息數過多，如果前一時刻自身分配給任務機，此時應該解除分配關系，使得擺渡機立刻飛向地面站.原先緊急的任務機在下一個時刻重新分配擺渡機.

2)更新emergeSearchList.根據無人機的緊急信號更新emergeSearchList.

3)更新emergeMap.根據任務機和擺渡機配對算法更新emergeMap.添加緊急狀態項算法示意圖如圖4所示.

圖4 添加緊急狀態項算法Fig.4 Adding emergency term algorithm

3.2.2 任務機和擺渡機配對算法

利用操作系統中先來先服務的調度思想，我們首先根據緊急狀態發生的時間順序在emergeSearchList尾部插入新項.然后從前往后遍歷emergeSearchList，利用任務機和擺渡機配對算法為每架緊急任務機找到擺渡機，最后擺渡機根據飛行控制算法飛行.

一架擺渡機可以將一架或者多架任務機的消息傳遞到地面站.同樣一架任務機也可能由多架擺渡機來傳遞消息.假設任務機i對應的擺渡機集合Fi，F是網絡中所有擺渡機的集合，則Fi?F.Fi(t-Δt)為前一時刻Fi中還未分配的擺渡機集合.ft(i)為t時間與任務機i配對的擺渡機，是距離緊急狀態任務機i最近的未配對的擺渡機.ft(i)可以表示為：

(5)

3.3 緊急狀態驅動的擺渡機飛行控制算法

無人機的運動模型可以參考高斯-馬爾科夫運動模型，它意味著擺渡機前后時刻的運動是有聯系的，不是完全隨機的[18].該算法在擺渡機上執行，為每架擺渡機提供實時控制.另外需要強調的是，該算法是建立在已有航路點基礎上的.飛行控制算法的思想為：如果擺渡機被分配給緊急狀態的任務機，則擺渡機朝著緊急狀態任務機飛行，建立通訊之后再朝向地面站飛行.如果擺渡機自身緊急，那么朝著地面站方向飛行.如果擺渡機自身不緊急，也沒有分配給任務機，那么按照簡單的循環方式飛行.綜上，擺渡機飛行控制算法總共有三種飛行模式：循環飛行、朝地面站飛行、朝緊急任務機飛行.擺渡機的飛行控制算法偽代碼如下：

算法1.flyControl Algorithm.

1：//擺渡機按照飛行控制算法，每次飛行Δt時間

2：procedureflyControl (Δt)

3：//如果擺渡機沒有和其他任務機建立配對且該機不緊急

4：//表現為擺渡機上的Locked位為false

5：ifLocked==falsethen

6： circleMove(Δt) ?循環飛行

7：else

8：//當擺渡機因為自身的消息數超過預警值，即本機緊急

9：ifmsgNumber>ferryTriggerthen

10： moveToStation(Δt) ?朝地面站飛行

11：//當擺渡機和任務機建立配對關系

12：else

13：//擺渡機和緊急任務機無法建立高通量聯系

14：ifcan not connecting emerge SearchHostthen

15： moveToEmerge(Δt) ?朝緊急任務飛行

16：else

17： moveToStation(Δt) ?朝地面站飛行

18：endif

19：endif

20：endif

21：endprocedure

4 仿真實驗及其實驗結果分析

4.1 實驗場景及參數設置

本文實驗是在TheOne模擬器中進行.TheOne是一個機會網絡環境模擬器，它可以模擬不同路由協議，不同的運動模型的DTN網絡的消息傳輸，還可以實時交互式可視化模擬和結果.我們在任務機移動場景中分別以簡單循環飛行方式和本文提出的基于緊急狀態量驅動飛行方式兩種飛行方式進行模擬實驗，從而對比兩種算法的優劣.

實驗場景如圖5所示.假設有4架擺渡機(f10-f13)，9架任務機(u1-u9)和1個地面站(g0).其中任務機按照Z型路線循環飛行，任務機按照圖示路線飛行.各無人機從各自按照軌跡循環飛行.

圖5 任務機移動場景Fig.5 Moving search UAV scene

其他試驗參數設置如表1所示.

表1 實驗參數Table 1 Experimental parameters

4.2 實驗結果及其分析

本文算法由無人機的消息存儲量觸發無人機的緊急狀態.因為任務機和擺渡機可以分別設置預警值，為了分析不同預警值對傳遞消息的各個指標的影響，我們采用控制變量法進行實驗.我們先設擺渡機的預警值為無窮大，設置不同的任務機的預警值進行實驗.然后從中選取合適的任務機預警值固定不變，再去改變擺渡機的預警值進行實驗.任務機移動場景實驗數據如圖6-圖9所示.

分析以上實驗結果可以發現：

1)本文提出的緊急狀態量驅動的擺渡機飛行方法的投遞率、消息平均延遲與簡單循環在動態場景下相比均有提升. 在該動態場景下，各任務機節點按照一定的運動軌跡運動，任務機節點之間有一定的概率發生通訊.如圖6-圖7，緊急信號量驅動的飛行方式相較與簡單循環飛行方式，僅任務機設置預警值時，投遞率相近，平均消息延遲減少約20%.如圖8-圖9，任務機選取600的緊急預警值固定不變，改變擺渡機的預警值時，平均消息延遲減少約47%.而且加入擺渡機預警值是防止網絡負載過高時，擺渡機無法及時返回地面站造成網絡擁塞，增強了算法的魯棒性.平均消息延遲平均值對比如表2所示.其中+表示提高，-表示降低.

圖6 單預警值緊急驅動與簡單循環方式投遞率比較Fig.6 Deliveryratecompa-risonofsinglewarningvalueemergency-driveandsimplecycle圖7 單預警值緊急驅動與簡單循環方式平均消息延遲比較Fig.7 Delaycomparisonofsinglewarningvalueemer-gency-driveandsimplecycle

圖8 單/雙預警值緊急驅動與簡單循環投遞率比較Fig.8 Deliveryratecomparisonofsingle/doublewarningvalueemergency-driveandsimplecycle圖9 單/雙預警值緊急驅動與簡單循環投遞率比較Fig.9 Delaycomparisonofsingle/doublewarningvalueemergency-driveandsimplecycle

表2 平均消息延遲平均值對比Table 2 Average delay comparison

2) 當設置預警值過小時，性能表現不佳;預警值足夠大時，其運動方式和簡單循環方式相同.如果任務機的預警值設置過小時，擺渡機會很快地向任務機靠近，并將消息擺渡到地面站.導致一次擺渡的消息數量較小，從而導致消息在任務機上堆積.如果擺渡機的預警值設置過小時，擺渡機接收的消息不多就往地面站飛行，導致消息在任務機上堆積.所以預警值不能設置過小.當預警值設置很大時，將不會觸發緊急狀態，所以緊急狀態驅動飛行方式將和簡單循環飛行方式相同.

5 總 結

本文針對典型的搜救場景，提出了小面積延遲容忍網絡下的單播消息擺渡模型.并在簡單循環飛行方式基礎上提出了一種基于緊急狀態的擺渡機飛行控制策略.當消息數超過一定的預警值，無人機將變為緊急狀態，然后通過地面站的調度和分配來驅動擺渡機飛行.實驗證明，當選取合適的預警值時，緊急狀態驅動擺渡機的飛行方式會使消息的投遞率和平均延時表現提升.本文是在基于范圍較小的低通量網絡中實現了緊急狀態驅動的飛行控制算法，未來考慮擴展到范圍更大的網絡中.