劉冬寧，曾思敏，陳凌豐，吳詩(shī)玨

(廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，廣東 廣州，510006)

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

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

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

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

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

1 場(chǎng)景預(yù)設(shè)

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

圖1 災(zāi)區(qū)高程線(xiàn)圖Figure 1 Elevation line of a disaster area

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

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

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

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

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

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

圖2 災(zāi)區(qū)內(nèi)無(wú)人機(jī)校正點(diǎn)分布圖Figure 2 Distribution of UAV calibration points in a disaster area

當(dāng)無(wú)人機(jī)距離目標(biāo)位置過(guò)遠(yuǎn)時(shí)，直線(xiàn)飛往目的點(diǎn)很有可能由于誤差過(guò)大導(dǎo)致偏離中繼點(diǎn)位置。所以在計(jì)算資格矩陣Q時(shí)需要為無(wú)人機(jī)規(guī)劃合理的航跡，確保無(wú)人機(jī)的誤差在允許的范圍內(nèi)。考慮到災(zāi)區(qū)救援的緊急性，在規(guī)劃航跡時(shí)要盡可能減少校正次數(shù)，避免花費(fèi)不必要的校正時(shí)間。航跡的長(zhǎng)度盡量接近直線(xiàn)距離，使無(wú)人機(jī)能飛行更短的距離，更快到達(dá)中繼點(diǎn)執(zhí)行中繼任務(wù)。

2 算法設(shè)計(jì)

2.1 最小生成樹(shù)組網(wǎng)算法

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

圖3 最小生成樹(shù)Figure 3 Minimum spanning tree

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

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

圖4 中繼點(diǎn)分布圖Figure 4 Distribution of relay points

2.2 群組角色指派

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

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

定義1角色需求向量為L(zhǎng)。

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

定義2能力極限向量為L(zhǎng)a，即每個(gè)代理能分配出去的最大資源數(shù)。

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

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

在本文的場(chǎng)景中，使用無(wú)人機(jī)從基站到中繼點(diǎn)的航跡長(zhǎng)度作為執(zhí)行能力的評(píng)分Qintial如下。

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

對(duì)其進(jìn)行[0,1]空間歸一化處理。

定義4分配矩陣為T(mén)，是一個(gè)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í)行能力 σ的求解過(guò)程是將資格矩陣Q與分配矩陣T進(jìn)行矩陣點(diǎn)乘。

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

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

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

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

圖5 分配矩陣散點(diǎn)圖Figure 5 Scatter diagram of a distribution matrix

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

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

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

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

當(dāng)無(wú)人機(jī)的起點(diǎn)是A，終點(diǎn)是B，所需要經(jīng)過(guò)的校正點(diǎn)x0時(shí)，x0與AB的垂線(xiàn)交于。如圖6所示。

圖6 無(wú)人機(jī)飛行軌跡示意圖Figure 6 Example diagram of UAVs’ flight trajectories

由此可得

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

綜上所述，本文為每一個(gè)校正點(diǎn)引入一個(gè)權(quán)值w。

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

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

3 實(shí)驗(yàn)及結(jié)果分析

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

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

針對(duì)不同步長(zhǎng)距離和連續(xù)回溯數(shù)，隨機(jī)100個(gè)起點(diǎn)與終點(diǎn)位置?？偣策M(jìn)行10 000次實(shí)驗(yàn)。其中每組不同回溯次數(shù)的實(shí)驗(yàn)中，回溯限制導(dǎo)致無(wú)解的平均耗時(shí)，以及無(wú)解情況占總無(wú)解數(shù)的比例情況如表2所示。

表2 回溯限制導(dǎo)致無(wú)解的情況表Table 2 Situations of no solution caused by backtracking restrictions

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

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

在設(shè)置連續(xù)回溯次數(shù)為7之后，再分別對(duì)不同步長(zhǎng)距離做100次隨機(jī)實(shí)驗(yàn)，共做1 000次實(shí)驗(yàn)。進(jìn)一步論證算法的時(shí)效性以及對(duì)無(wú)人機(jī)災(zāi)區(qū)中繼救援的影響。實(shí)驗(yàn)結(jié)果如圖9～ 11所示。

圖9 距離與時(shí)間的關(guān)系Figure 9 Relationship between the distance and the time

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

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

圖10 距離與偏離率的關(guān)系Figure 10 Relationship between the distance and the deviation rate

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

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

4 結(jié)論

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