地震災區(qū)中繼無人機群組角色指派研究

劉冬寧，曾思敏，陳凌豐，吳詩玨

(廣東工業(yè)大學 計算機學院，廣東 廣州，510006)

在地震發(fā)生后，地面的基礎設施被破壞，導致災區(qū)的通信網絡癱瘓。救援工作是緊急、突發(fā)、具有時效性的，通信中斷會極大地影響救援工作，所以構建穩(wěn)定的通信網絡是災區(qū)救援的重要任務。無人機(unmanned aerial vehicle,UAV)可以跨越地理環(huán)境障礙，在救援中完成巡邏、搜索、探測等多項任務，還可以搭載相關設備后作為網絡中繼，為災區(qū)提供穩(wěn)定的通信服務。因此利用無人機中繼建立臨時的通信網絡的方式應運而生[1-4]。其中，Liu等[3]充分探討了在發(fā)生災難時，如何部署無人機基站的網絡接入和通信資源分配的方案，證明在災后利用無人機基站恢復通信的可行性。

然而，通信網絡需要有多個中繼點不規(guī)則地散布在災區(qū)的各個角落。利用無人機建立網絡時，因無人機在數(shù)量有限的情況下還需要完成多項任務，如巡航、偵察遇難者等，所以在保證通信質量的前提下，如何使用有限的無人機完成中繼任務，實現(xiàn)任務的最優(yōu)分配，是災區(qū)重建通信網絡面臨的重大挑戰(zhàn)。

為解決非飽和式救援期間的多無人機協(xié)同最優(yōu)分配這一關鍵問題，王峰[5]、王巍等[6]研究如何利用啟發(fā)式算法解決多無人機協(xié)同任務分配問題。除此之外，集中式和分布式的新型算法也被廣泛應用于無人機指派中，其中Schwarzrock等[7]基于集中式提出3種基于啟發(fā)式算法的變形，使其互相補充來解決多架無人機執(zhí)行協(xié)同任務的分配問題。Geng等[8]針對搜索和救援應用領域，提出一種基于粒子群優(yōu)化的改進集中式算法 (modified centralized algorithm based on particle swarm optimization，MCPSO) 來解決搜索和救援領域的任務分配問題。然而不管是啟發(fā)式算法，還是分布式和集中式算法，都可以應用在任務分配這類研究中。

在任務分配的研究中，Zhu等[9]和Liu等[10]提出集中式建模分布式執(zhí)行的群組角色指派 (group role assignment，GRA)，它是基于角色的協(xié)同 (role-based collaboration，RBC) 方法及其通用模型E-CARGO的子模型。RBC[11-14]、E-CARGO和GRA已經發(fā)展成為一種與任務分配相關的有效決策方法，在角色分配問題中有很強的適用性。GRA能根據(jù)Agent評價的結果，尋求一個最優(yōu)的角色分配。學者們研究GRA在各種不同場景中的適用性，如劉冬寧等[15]研究了志愿偏好指派問題。另外，Liu等[14]研究GRA在協(xié)同無人機部署通信網絡的場景中的應用情況，發(fā)現(xiàn)GRA在無人機協(xié)同上有很好的效果。

綜上，本文使用最小生成樹算法生成通信網絡，利用群組角色指派進行建模。將中繼點作為角色，分布在不同基地的無人機作為Agent。應用GRA模型求解最優(yōu)分配問題的關鍵在于將作為Agent的無人機的飛行距離作為救援代價進行評估，建立代價矩陣。但是，受機械特性與電氣特性限制，在惡劣復雜環(huán)境下，無人機的定位系統(tǒng)無法對自身進行精準定位，且隨著飛行距離的增加，無人機定位的垂直與水平誤差也會隨之增加，導致定位偏離過大，使得規(guī)劃的通信網絡不能聯(lián)通。因此，在無人機實際飛行中需要通過水平、垂直誤差修正點進行精確定位。針對這一問題，本文設計了貪心回溯算法，以盡可能減少誤差糾正次數(shù)為目標，快速、精確求解無人機飛行軌跡，并依此建立代價矩陣。最終使用GRA模型解決非飽和式救援下的最優(yōu)分配問題，快速重建網絡恢復通信。

1 場景預設

2017年8月8日，九寨溝發(fā)生7.0級地震。據(jù)中國地震臺網中心 (CENC)稱，地震發(fā)生在20 km深處。超過90輛緊急車輛和1 200名人員被派往災區(qū)參與救援工作。為了快速恢復通信，救援中心決定采用視距通信[6]的方式，使用無人機中繼與地面移動終端組建通信網絡。為此，在災區(qū)部分地區(qū)部署了一些通信車輛作為地面移動終端以及無人機基地。為解決同類問題，科學指導救災，本文根據(jù)九寨溝災區(qū)高程數(shù)據(jù)，隨機仿真20個通信車輛的坐標作為地面移動終端，7個救援中心作為無人機基地。圖1是災區(qū)高程圖，其中描繪了移動終端的分布情況，圖1中的圓點表示地面移動終端，五角星表示無人機基地在災區(qū)的分布情況。

圖1 災區(qū)高程線圖Figure 1 Elevation line of a disaster area

由于受道路影響，這些車輛在災區(qū)不便通行，移動范圍和通信距離有限，無人機與地面移動終端的距離需要在一定范圍內，才能保證通信的有效性。本文假設通信車輛與無人機之間的有效通信距離在5 km內。

為盡快恢復災區(qū)的通信，救援隊決定部署攜帶通信設備的太陽能蓄能固定翼無人機作為中繼點部署通信網絡[16]。這些無人機從多個救援中心出發(fā)，無人機與無人機之間組成Ad-Hoc網絡[6]。假設每架無人機能在空中穩(wěn)定盤旋。由于無人機受負載、電力等因素限制，通信覆蓋范圍有限，本文為便于描述與實驗，假設每架無人機的通信覆蓋范圍在3 km的覆蓋半徑下能保證穩(wěn)定的通信，即無人機與無人機之間的最大通信距離為6 km。

為了利用最少無人機建立通信網絡，救援隊決定使用最小生成樹算法來確定中繼點數(shù)量和位置。此外，由于在非飽和救援下無人機有多項任務需要執(zhí)行，例如災區(qū)巡邏和遇難者探測等，所以每個基地對指派中繼任務的無人機數(shù)量都有上限。隨機仿真數(shù)據(jù)如表1所示。

表1 各個基地指派中繼任務的無人機數(shù)量上限Table 1 Maximum number of UAVs assigned to relay tasks by each base

由于災區(qū)救援工作緊迫，需要盡快將來自不同基地的無人機按最優(yōu)分配原則分配到各個信號中繼點上，為此使用GRA作為任務分配的決策方法。在應用GRA時用于評估的代價矩陣定義為資格矩陣Q，可將無人機飛往中繼點的航跡距離作為執(zhí)行能力的評分，得到Q矩陣。

無人機在飛行過程中會實時定位，由于受機械與電氣特性限制，無人機在飛行過程中會產生飛行誤差，其中誤差分為水平誤差和垂直誤差。結合實際情況，本文預設無人機每飛行1 m，垂直誤差和水平誤差各增加1 mm。為保證無人機飛行過程不產生較大的定位誤差，偏離指定的任務中繼點較遠，導致無人機脫離通信范圍，設定無人機到達指定位置時垂直誤差和水平誤差均應小于2 m?？稍跒膮^(qū)尋找一些未損毀的標志性建筑或已勘測點等作為垂直和水平校正點，校正點分布如圖2所示。在考慮無人機的機械參數(shù)、當時環(huán)境等因素下，確定當無人機在垂直矯正點時，垂直誤差小于2 m，水平誤差小于1 m時，可以矯正到垂直誤差為0，水平誤差保持不變；無人機在水平校正點時，垂直誤差小于1.5 m，水平誤差小于2 m時，可以矯正到水平誤差為0，垂直誤差保持不變。

圖2 災區(qū)內無人機校正點分布圖Figure 2 Distribution of UAV calibration points in a disaster area

當無人機距離目標位置過遠時，直線飛往目的點很有可能由于誤差過大導致偏離中繼點位置。所以在計算資格矩陣Q時需要為無人機規(guī)劃合理的航跡，確保無人機的誤差在允許的范圍內?？紤]到災區(qū)救援的緊急性，在規(guī)劃航跡時要盡可能減少校正次數(shù)，避免花費不必要的校正時間。航跡的長度盡量接近直線距離，使無人機能飛行更短的距離，更快到達中繼點執(zhí)行中繼任務。

2 算法設計

2.1 最小生成樹組網算法

在選擇中繼點之前已知所有地面移動終端的位置，并且無人機的數(shù)量足以完全覆蓋所有地面移動終端時，最小生成樹算法具有全局通信最小成本的特性。因此本文使用Prim算法聯(lián)通所有的地面移動終端。圖3是根據(jù)圖1生成的最小生成樹圖。

圖3 最小生成樹Figure 3 Minimum spanning tree

得到最小生成樹后需要確保通信網絡能全部覆蓋這個樹，因此可根據(jù)移動終端與無人機的通信距離以及無人機之間的通信覆蓋范圍，在該樹上得到全覆蓋通信所需要的最少中繼數(shù)N。

其中V是所有通信車輛位置的集合；DAB是從A到B的距離；d是通信車輛與無人機的通信距離減去無人機的通信覆蓋半徑，在此場景中d為2 km；Ddrone是無人機通信的覆蓋直徑。在最小生成樹的枝干位置上根據(jù)信號半徑確定這些中繼點的位置。中繼點的具體位置如圖4所示。其中黃色五角星為無人機基地；紅色圓點為地面移動終端，其外圍紅色圓為該終端的通信范圍；藍色圓點為中繼點，其外圍藍色圓為該中繼無人機的通信范圍。

圖4 中繼點分布圖Figure 4 Distribution of relay points

2.2 群組角色指派

問題建模采用的是群組角色指派模型 (GRA)，它是RBC及其通用模型E-CARGO的子模型。ECARGO 模型以9元組＜C,O,A,M,R,E,G,s0,H＞抽象描述了協(xié)作系統(tǒng)的組成部分。其中，C表示類；O表示對象；A(Agent) 表示協(xié)作個體單元集合；M表示消息；R(Role) 表示角色集合 (即任務與需求抽象)；E用于抽象協(xié)作環(huán)境；G(Group) 表示群組集合；s0是系統(tǒng)的初始狀態(tài)；H是一組用戶。

本文視無人機作為代理，通信網絡的各個中繼點作為任務角色。因此，在使用GRA之前需要先確定中繼點個數(shù)和位置。以下根據(jù)RBC和E-CARGO對問題進行形式化建模。

定義1角色需求向量為L。

在本文的場景中，每個角色只能分配給一個代理，?j.L[j]=1(0≤j＜n)，即L=[111···111]。

定義2能力極限向量為La，即每個代理能分配出去的最大資源數(shù)。

根據(jù)表1各個基地指派中繼任務的無人機數(shù)量上限表，可得La=[17 19 18 22 15 12 21]。

定義3資格矩陣為Q，是一個m×n的矩陣。其中Q[i,j]∈[0,1]，代表Ai(0≤i＜m)擔 當Rj(0≤j＜n)的執(zhí)行力評分。

在本文的場景中，使用無人機從基站到中繼點的航跡長度作為執(zhí)行能力的評分Qintial如下。

中國高鐵要走出國門，合作國目前的政治社會環(huán)境也是一個不可忽視的因素，復雜的地域政治因素同樣會造成影響。例如我國在2015年印度高鐵項目競標中取得了勝利，然而同一年安倍出訪印度，莫迪總統(tǒng)在12月13日選擇了讓日本修筑印度高鐵，雖然日本提出的方案中貸款政策相較我國更加優(yōu)惠，但其中也摻雜著政治因素。

對其進行[0,1]空間歸一化處理。

定義4分配矩陣為T，是一個m×n矩陣。其中T[i,j] ∈{0,1}(0≤i＜m，0≤j＜n)，代表Ai是否被分配執(zhí)行Rj。T[i,j]=1代表執(zhí)行；T[i,j]=0代表不執(zhí)行。

群組執(zhí)行能力 σ的求解過程是將資格矩陣Q與分配矩陣T進行矩陣點乘。

定義8群組角色指派的線性求解，即尋找可行的分配矩陣T，其中目標函數(shù)為

其中條件 (5) 根據(jù)本文場景中?j.L[j]=1(0≤j＜n)的條件，又可以轉化成

約束條件 (4) 表示角色分配矩陣T的值只能取0或1；約束條件 (6) 與最初的GRA問題不同，這意味著代理只能分配給有限數(shù)量的角色；約束條件(7) 表示角色分配矩陣T每一列的1的個數(shù)總和分別等于向量L每個值。

例如，在本文中根據(jù) ?j.L[j]=1(0≤j＜n)和La=[17 19 18 22 15 12 21]，結合上述約束可以得到分配矩陣T。7個基地的無人機群組執(zhí)行力 σ為12.09，這是通過GRA得到的最佳結果。分配矩陣T散點圖如圖5所示。

圖5 分配矩陣散點圖Figure 5 Scatter diagram of a distribution matrix

2.3 貪心回溯航跡規(guī)劃算法

為了解決無人機航跡規(guī)劃的問題，使得無人機在盡可能減少校正次數(shù)的情況下，到達中繼點時誤差在允許范圍內，并且使得航跡距離盡量接近直線距離。本文設計貪心回溯算法為無人機進行航跡規(guī)劃。

雖然貪心算法存在容易陷入局部最優(yōu)解的問題，但是考慮到災區(qū)救援的背景，首先需要一個能快速為所有無人機規(guī)劃航跡的算法，在確保高速的前提下才考慮其他的目標。所以在設計算法時需要首先考慮算法的運行時間。

本文使用非負整數(shù)p代表校正點集合S的大小，其中 {k0,k1,···,kn}∈S，具體指每一個校正點。非負整數(shù)p代表航跡經過的校正點集合P的大小，其中{x0,x1,···,xn}∈P，具體指每一個需要經過的校正點。

當無人機的起點是A，終點是B，所需要經過的校正點x0時，x0與AB的垂線交于。如圖6所示。

圖6 無人機飛行軌跡示意圖Figure 6 Example diagram of UAVs’ flight trajectories

由此可得

根據(jù)式(9)可以看出，當Dsum越小，Daverage越大時，經過的校正總數(shù)e的值越小。為此航跡中兩點之間距離應能在誤差允許的范圍內盡量大，即圖6中的盡量大。其中Daverage代表航跡中兩點之間的平均長度。

綜上所述，本文為每一個校正點引入一個權值w。

根據(jù)權值w將所有校正點進行排序，每次遍歷，探索能到達的下一個校正點時，優(yōu)先選擇權值大的校正點。以此快速選出更滿足規(guī)劃目標的路徑。該算法的流程圖如圖7所示。

圖7 貪心回溯算法流程圖Figure 7 Flow chart of the greedy backtracking algorithm

3 實驗及結果分析

論文實驗在Windows10 系統(tǒng)下使用Matlab R2016b完成。

為了使算法滿足災區(qū)救援的時間窗壓力，本文通過實驗得到貪心算法的回溯次數(shù)對時間和無解情況的影響，以找到一個能平衡時間和求解能力回溯次數(shù)限制。本文進行了大規(guī)模隨機仿真實驗，根據(jù)起點與終點的距離取值30～ 130 km，以步長10 km作為跳變，隨機起點與終點的位置。另外設置連續(xù)回溯數(shù)取值1～ 10，步長為1。測試回溯次數(shù)對實驗出現(xiàn)無解的影響。

針對不同步長距離和連續(xù)回溯數(shù)，隨機100個起點與終點位置?？偣策M行10 000次實驗。其中每組不同回溯次數(shù)的實驗中，回溯限制導致無解的平均耗時，以及無解情況占總無解數(shù)的比例情況如表2所示。

表2 回溯限制導致無解的情況表Table 2 Situations of no solution caused by backtracking restrictions

將這些數(shù)據(jù)根據(jù)式 (2) 作歸一化處理后得到圖8。在圖8中可以看到當回溯次數(shù)取7時，算法在很好地兼顧求解時間的同時也避免了無解的出現(xiàn)。因此，本文將最長連續(xù)回溯次數(shù)設置為7。

圖8 回溯次數(shù)限制導致無解的情況Figure 8 Situations of no solution due to the limitation of backtracking times

在設置連續(xù)回溯次數(shù)為7之后，再分別對不同步長距離做100次隨機實驗，共做1 000次實驗。進一步論證算法的時效性以及對無人機災區(qū)中繼救援的影響。實驗結果如圖9～ 11所示。

圖9 距離與時間的關系Figure 9 Relationship between the distance and the time

圖9表示實驗距離與求解時間的關系，從中可以看出本文算法能在1 s內求出解，而且平均求解時間穩(wěn)定在0.1 s內。在救災工作中能極快地為無人機規(guī)劃航跡。

圖10表示偏離率與實驗距離的關系，偏離率為算法求解的實際距離與直線距離的比值。其中顯示航跡距離在直線距離的2倍以內，而平均值則穩(wěn)定在1.3倍以內。這表明無人機航跡在盡可能地接近直線距離，保證算法規(guī)劃的航跡不偏離直線飛行方向。

圖10 距離與偏離率的關系Figure 10 Relationship between the distance and the deviation rate

圖11表示實驗距離與校正次數(shù)的關系。數(shù)據(jù)顯示，實驗距離每增加10 km，校正次數(shù)約增加2次，表明在本文的算法中飛行距離與校正次數(shù)為線性相關。這能保證在長距離飛行中，所需的校正次數(shù)不會突然劇增。

圖11 距離與校正次數(shù)的關系Figure 11 Relationship between the distance and correction times

4 結論

針對災區(qū)部署無人機通信網絡問題，設計了統(tǒng)一可行的解決方案。通過群組角色指派 (GRA) 對部署無人機通信網絡進行了形式化建模并且給出了有效的解決方案。數(shù)千次隨機實驗表明，本文的解決方案可以在1 s內為無人機規(guī)劃出航跡，并且保證航跡長度與直線距離的比值穩(wěn)定在1.3以內，以及每10 km校正2次左右的校正頻率。因此解決了通信網絡不會因為無人機定位誤差而導致整個網絡通信存在部分中斷的問題，確保了通信網絡的穩(wěn)定性。采用本文的解決方案，可以及時、高效地為災區(qū)部署穩(wěn)定的通信網絡。在下一步工作中，將研究不同性能的無人機在災區(qū)救援中根據(jù)不同任務的指派。