一種基于多無人機的中繼節(jié)點布置問題建模與優(yōu)化方法

吳高峰，高曉光，符小衛(wèi)

西北工業(yè)大學(xué) 電子信息學(xué)院，西安 710072

一種基于多無人機的中繼節(jié)點布置問題建模與優(yōu)化方法

吳高峰，高曉光*，符小衛(wèi)

西北工業(yè)大學(xué) 電子信息學(xué)院，西安 710072

針對戰(zhàn)場環(huán)境下急需在無法通信的節(jié)點間構(gòu)建有效通信鏈路的情形，使用多無人機作為中繼節(jié)點，建立了中繼節(jié)點布置(RNP)問題模型。模型以中繼鏈路有效和無人機安全為約束，以中繼布置點位置及相應(yīng)的無人機為輸出，不但考慮了使用的中繼無人機數(shù)量，還考慮了構(gòu)建中繼鏈路花費的時間?？紤]到該問題是難以求解的混合整數(shù)多目標(biāo)優(yōu)化問題，同時在緊急應(yīng)用情形下，要求求解算法快速有效，建立了一種多項式時間中繼節(jié)點布置算法(PTRPA)。仿真實驗驗證了所提模型確實能夠在更短的時間內(nèi)完成有效中繼鏈路構(gòu)建；通過Monte-Carlo方法對比和分析不同因素對PTRPA算法、隨機抽樣算法、遺傳算法求解該問題的結(jié)果性能和時間性能的影響，驗證了PTRPA算法不但能夠給出接近最優(yōu)的解，且快速有效，滿足戰(zhàn)場決策需求。

無人機；中繼；無線通信；節(jié)點布置；多項式時間算法；多目標(biāo)優(yōu)化

現(xiàn)代作戰(zhàn)具有高度信息化、網(wǎng)絡(luò)化的特點，實現(xiàn)與保持作戰(zhàn)節(jié)點間的信息交互十分重要。在信息交互的諸多實現(xiàn)方法中，無線通信是作戰(zhàn)環(huán)境下最為重要的通信方式之一。然而，隨著無線信號傳輸距離的增加，接收信號功率不斷下降，并且易受到地形等因素的阻礙，導(dǎo)致節(jié)點與節(jié)點間無法通信[1]，解決該問題的一種有效方法是在合理的位置布置新的節(jié)點作為通信中繼來轉(zhuǎn)發(fā)節(jié)點間消息。因此，如何選擇中繼節(jié)點數(shù)量和位置成為其中的關(guān)鍵問題，即中繼節(jié)點布置(Relay Node Placement, RNP)問題。

中繼節(jié)點布置問題研究中，由于中繼節(jié)點(Relay Node, RN)類型和應(yīng)用背景不同，中繼布置的目標(biāo)也存在差異，現(xiàn)有的研究中主要包括：使用最少數(shù)量的中繼節(jié)點實現(xiàn)網(wǎng)絡(luò)的連通(Connectivity)或容錯(Fault-Tolerance)[2-4]、盡可能地降低能耗(Energy Consumption)以最大化網(wǎng)絡(luò)壽命[5-7](Lifetime)、提升網(wǎng)絡(luò)的通信服務(wù)質(zhì)量[8](Quality of Service, QoS)、平均覆蓋率[9-10](Average Coverage)、容量[11-12](Capacity)和安全性[13](Safety)。

本文以布置多無人機作為中繼在急需通信的兩節(jié)點間構(gòu)建通信鏈路為背景，研究RNP問題，這在一些作戰(zhàn)情形下具有較大意義，如遠處執(zhí)行戰(zhàn)場態(tài)勢收集任務(wù)的節(jié)點與指控中心通信突發(fā)中斷。此外，無人機作為空中移動平臺，具有以下優(yōu)點：① 相對于地面中繼平臺，部署周期短、靈活性高且通信質(zhì)量好；② 相對于有人機平臺，戰(zhàn)場生存能力強、效費低；③ 相對于衛(wèi)星中繼平臺，抗干擾能力強、延遲低[14-17]。因此，使用無人機作為中繼具有重要應(yīng)用價值。

從無人機研究角度看，無人機RNP問題也是無人機中繼任務(wù)規(guī)劃問題，考慮的因素包括使用的無人機數(shù)量[13]、中繼質(zhì)量[14,18]、連通性[19]、無人機安全性指標(biāo)[13]。無論是RNP問題研究領(lǐng)域[2-13]，還是無人機中繼任務(wù)規(guī)劃研究領(lǐng)域[13-14,18-19]，尚未有研究考慮如何縮短構(gòu)建中繼鏈路花費的時間，而在急需構(gòu)建中繼鏈路的情形下，縮短構(gòu)建中繼鏈路花費的時間往往比追求更高的通信質(zhì)量更有意義。因此，本文RNP建模與優(yōu)化重點考慮的是在能夠通信的前提下，如何通過確定中繼布置點位置及對應(yīng)的無人機來使使用的無人機數(shù)量盡可能少和構(gòu)建中繼鏈路花費的時間盡可能短。本文研究屬于無人機中繼任務(wù)規(guī)劃決策層[20]。

基于無人機的RNP問題研究中，考慮的因素除通信距離約束、視線(Line of Sight, LoS)通信約束外，還包括節(jié)點安全約束。文獻[13]考慮了環(huán)境中存在的地形因素對無人機的安全威脅，戰(zhàn)場環(huán)境下往往還存在敵方防空覆蓋區(qū)域，因此也要避免將中繼無人機布置在這些區(qū)域，值得注意的是，無線信號往往可以穿越這些區(qū)域。

綜上所述，針對以無人機作為RN在兩節(jié)點間緊急構(gòu)建中繼鏈路情形，需要同時考慮到無人機數(shù)量最少和構(gòu)建中繼鏈路時間最短，且需要考慮通信距離、地形障礙和敵方防空威脅約束。該問題是一個混合整數(shù)多目標(biāo)優(yōu)化問題，且求解難度NP-hard[21]。求解此類問題的傳統(tǒng)優(yōu)化方法包括遍歷求解空間以獲得均衡解，以及將多目標(biāo)函數(shù)轉(zhuǎn)化為單目標(biāo)函數(shù)。前者決策時間過長，不符合緊急情形下的實時決策要求，后者又帶來加權(quán)、約束等新的復(fù)雜問題。另一類是以遺傳算法、粒子群算法等為代表的智能優(yōu)化算法[22]，但是該類算法仍然需要花費較長時間，同樣難以滿足要求。文獻[23-24]針對多無人機多目標(biāo)優(yōu)化問題，給出了一種兩階段算法，通過排序和刪減的方式得到無人機聯(lián)盟成員，然而該類文獻中各無人機目標(biāo)位置點相同，而本文中各無人機的中繼布置點不同，且相鄰無人機間存通信距離約束，使得上述方法難以適用于本文的RNP問題。本文建立了一種滿足多項式時間中繼節(jié)點布置算法(Polynomial Time Relay Placement Algorithm,PTRPA)，該方法先通過廣度優(yōu)先搜索的方法求取最少中繼無人機數(shù)量并縮小求解空間，再通過貪婪策略優(yōu)化構(gòu)建中繼鏈路花費的時間。一旦無人機到達各自中繼布置點并實現(xiàn)構(gòu)建中繼鏈路，需要繼續(xù)控制中繼無人機運動以保證中繼效果，Dixon和Frew在文獻[25]中對此做了一定程度的研究。

本文針對緊急情況下的中繼無人機布置問題，建立了相應(yīng)的優(yōu)化模型，不但考慮了使用的中繼無人機數(shù)量，而且考慮了構(gòu)建中繼鏈路花費的時間。針對該問題求解難度NP-hard，本文給出了一種多項式時間求解算法，并分析了算法的計算復(fù)雜度。本文的組織結(jié)構(gòu)如下：第1節(jié)建立了基于多無人機的中繼節(jié)點布置問題數(shù)學(xué)模型；第2節(jié)通過對問題空間進行離散處理，使得此問題由連續(xù)的混合整數(shù)規(guī)劃問題變?yōu)榭山獾碾x散整數(shù)規(guī)劃問題；第3節(jié)詳述了本文提出的兩階段多項式時間中繼節(jié)點布置算法PTRPA；第4節(jié)通過仿真檢驗了算法的可行性和有效性并研究了不同因素對算法性能的影響；第5節(jié)是對全文的總結(jié)。

1 基于多無人機的中繼布置問題建模

為了研究問題的方便，假設(shè)所有的節(jié)點處于同樣的海拔高度，戰(zhàn)場區(qū)域為D?R2,待中繼的目標(biāo)節(jié)點為s和t,考慮到中繼無人機多為中小型無人機，最大飛行高度有限，無人機以一定高度在該區(qū)域內(nèi)執(zhí)行中繼任務(wù)，區(qū)域內(nèi)可能存在敵方防空威脅和地形障礙威脅，并分別記其覆蓋區(qū)域為Y={y1,y2,…,yb}和Z={z1,z2,…,za},有m架無人機U={u1,u2,…,um}可用作中繼節(jié)點。

(1)

式中：

f1(N)=k

(2)

(3)

需要指出的是，s和t之間的RNP研究與s到t的航路規(guī)劃研究存在本質(zhì)區(qū)別：① 飛行航路需要考慮無人機飛行特性，航路曲線是平滑的，而中繼鏈路是由多條直線段組成的折線；② 研究目的不同，前者是給出中繼布置點位置和對應(yīng)的無人機，后者是生成兩點間的可飛航路。

接下來，中繼節(jié)點布置過程中，還需要考慮到中繼無人機的安全性、通信鏈路有效性以及一個無人機只能被布置到一個中繼布置點，具體來說：

1) 中繼無人機安全性約束：為了保證無人機安全，同時也是為了保證中繼鏈路持續(xù)可靠工作，首先要求中繼布置點避開地形障礙和敵方防空威脅覆蓋區(qū)域，即

(4)

(5)

?pi∩Z=?i=1,2,…,k

(6)

?pi∩Y=?i=1,2,…,k

(7)

考慮到地形障礙容易阻隔無線信號傳播，而敵方防空武器卻難以阻隔無線信號傳播，于是要求:

(8)

(9)

3) 中繼無人機唯一性約束：中繼節(jié)點布置中，任意無人機只能被布置在唯一的布置點，即

?ri≠?rji=1,2,…;k,j=1,2,…,k

(10)

本文基于多無人機的中繼節(jié)點布置問題式(1)～式(10)是一個難以求解混合整數(shù)多目標(biāo)優(yōu)化問題，不僅是因為該問題中存在整數(shù)變量，還因為區(qū)域內(nèi)可能存在多組可行的中繼布置點、中繼布置點與中繼無人機組合方式不同帶來不同的f2(N)、以及存在的地形障礙和敵方防空威脅覆蓋區(qū)域可能會產(chǎn)生多極值。

本文接下來工作的目標(biāo)是給出一種針對上述RNP問題的快速有效求解算法，以滿足戰(zhàn)場決策要求?？紤]到該問題屬于連續(xù)空間優(yōu)化問題，為便于問題求解，首先對問題空間進行離散化處理。

2 空間離散化

為求解中繼節(jié)點布置問題式(1)～式(10)，將中繼節(jié)點布置范圍限制在等間距的離散點D′?D,如圖1所示，γ為布置點間距，淺色區(qū)域為地形障礙覆蓋區(qū)域，深色區(qū)域為敵方防空威脅覆蓋區(qū)域，黑色點為不可行布置點，白色點為可行布置點。令Z′=Z∩D′及Y′=Y∩D′,于是可以得到可行布置點位置集合X=D′-Z′∪Y′。

令矩陣C=[cij]|X|×|X|表示可行布置點間通信連接關(guān)系，|X|表示X中可行布置點數(shù)目，cij=1表示可行布置點xi∈X和可行布置點xj∈X之間存在視線路徑且距離小于無人機最大通信距離dmax,即

(11)

圖1 空間離散化示意圖Fig.1 Sketch map of spatial discretization

類似地，令T=[tij]|X|×|X|,其中tij為從xi飛行到xj的最短到達時間。為了降低求解的難度和不失研究重點，本文在假設(shè)無人機飛行速度v相同且不考慮無人機動力學(xué)特性基礎(chǔ)上，采用如下方法估計tij值：從xi到xj的最短飛行路徑包括兩種情形：① 從xi到xj不穿越任何類型障礙和威脅覆蓋區(qū)域的視線路徑；② 由于從xi到xj的視線路徑上存在地形障礙或敵方防空威脅而經(jīng)過其他點xw∈X的折線路徑。對任意xi,xj∈X,令tij=∞,通過下述兩個步驟計算tij。

步驟1估計存在視線路徑的所有xi、xj間的最短到達時間:

(12)

式中：‖xi,xj‖為從xi到xj的歐式距離。

步驟2基于步驟1的結(jié)果，通過Floyd算法[28]計算任意從xi到xj的估計最短到達時間。

空間離散化可事先利用已獲取的環(huán)境信息和無人機最大通信距離信息完成，一旦給出s和t位置、可用作中繼的無人機及初始位置信息，即可快速求解出中繼節(jié)點布置結(jié)果N*。

3 多項式時間中繼節(jié)點布置算法

空間離散化完成后，本文RNP問題求解復(fù)雜度仍然NP-hard。考慮到戰(zhàn)場環(huán)境下快速決策需求，本節(jié)建立了一種能夠滿足多項式時間的中繼節(jié)點布置算法,在滿足此要求前提下，能夠給出本文RNP問題接近最優(yōu)的解。算法具體可分為兩個階段;第1階段決策出需要使用的中繼無人機的最少數(shù)量和中繼鏈路各跳(hop)所能包含的可行布置點集合;第2階段通過貪婪策略優(yōu)先滿足最難以到達的跳來減小構(gòu)建中繼鏈路花費的時間。

3.1 PTRPA算法第1階段(PTRPA-Stage 1)

算法偽代碼見表1。

定理1PTRPA-Stage 1保證了中繼鏈路跳數(shù)最少(即使用的無人機數(shù)量最少)。

證明令G=(X,C),則G為無向無權(quán)圖，文獻[29]中已證明，通過BFS搜索到的G中從節(jié)點s到t的路徑一定為最短路徑，即對應(yīng)本文中的中繼跳數(shù)。定理1得證。

定理2經(jīng)過PTRPA-Stage 1，不存在經(jīng)過其他可行布置點xw∈X且xw?L使跳數(shù)最少的鏈路。

證明假設(shè)存在這樣一條鏈路w,根據(jù)定理1，易知該鏈路跳數(shù)為|L|-1。不妨假設(shè)xw為w中從s到t的第i跳，即圖G中通過BFS從s經(jīng)過i跳必然能搜索到xw,因此經(jīng)過表1中步驟4～步驟13，xw必然在L中。接下來只要證明步驟14～步驟20沒有將xw從L中刪除，即可說明經(jīng)過PTRPA-Stage 1，必有xw∈L,與假設(shè)矛盾。鏈路w中跳數(shù)為|L|-1,xw是從s到t的第i跳，那么從xw通過BFS經(jīng)過|L|-1-i跳必然能夠搜索到節(jié)點t,由于G為無向圖，那么從t通過BFS經(jīng)過|L|-1-i跳也必然能夠搜索到節(jié)點，因此xw不會從L中被刪除。定理2得證。

本階段算法基于BFS方法，從所有可行布置點中，選擇出在最少中繼無人機數(shù)量要求下的每跳所有可能的布置點?？紤]到每跳中可能包括多個可能布置點，以及對應(yīng)不同的中繼無人機可能帶來不同的到達時間，因此還需進一步明確每跳布置點及對應(yīng)的中繼無人機。

表1 PTRPA算法第1階段偽代碼Table 1 Pseudo code of PTRPA-Stage 1

3.2 PTRPA算法第2階段(PTRPA-Stage 2)

在PTRPA第1階段結(jié)果基礎(chǔ)上，確定每跳的唯一布置點及對應(yīng)的無人機。令δ={0}k×1表示li(i=1,2,…,k)尚未確定唯一中繼布置點，η={0}m×1表示無人機ui(i=1,2,…,m)未被選為中繼節(jié)點，重復(fù)執(zhí)行以下步驟，直到δi=1(i=1,2,…,k):

該階段算法的偽代碼見表2。

本階段算法通過優(yōu)先滿足最難到達的跳的策略確定了各跳中的唯一布置點及對應(yīng)的中繼無人機，這是一種按步尋求局部最優(yōu)的貪婪策略，最終結(jié)果可能無法全局最優(yōu)，因為每次決策沒有能夠從全局考慮所有可能“布置點-無人機”對應(yīng)方案。仿真實驗表明，PTRPA最終給出的結(jié)果接近全局最優(yōu)，而花費的計算卻遠小于全局尋優(yōu)算法。

PTRPA算法第1階段在找到t點并去除無效布置點后或搜索完X中所有布置點即終止，算法第2階段在執(zhí)行|L|-2次后即終止，PTRPA算法最終只給出唯一中繼布置求解結(jié)果“N*”或“無法構(gòu)建有效鏈路”。

一旦無人機獲得中繼布置點位置，即可采用A*、人工勢場等方法[30]規(guī)劃安全且滿足自身動力學(xué)特性的可飛航跡，并控制自身飛向中繼布置點。

表2 PTRPA算法第2階段偽代碼Table 2 Pseudo code of PTRPA-Stage 2

3.3 計算復(fù)雜度分析

PTRPA第1階段基于BFS算法，算法復(fù)雜度為O(|X|2)[29]，其中X為所有可行布置點集合。PTRPA第2階段步驟5～步驟8找局部最難到達的跳的復(fù)雜度不超過O(‖L‖m+|L|),此處令‖L‖表示L中包含的所有可行布置點數(shù)目，步驟10的復(fù)雜度不超過O(‖L‖2),步驟4～步驟11最多重復(fù)m次，因此PTRPA第2階段復(fù)雜度不超過O(m(‖L‖m+|L|+‖L‖2))。PTRPA算法總時間復(fù)雜度為

O(|X|2)+O(m(‖L‖m+|L|+‖L‖2)≈

O(|X|2+m‖L‖2+m2‖L‖)

(13)

容易得出，本文PTRPA是一種多項式時間算法，考慮到一般情況下，無人機的使用數(shù)量遠遠少于戰(zhàn)場區(qū)域中可行布置點的數(shù)量，因此整體上PTRPA算法的復(fù)雜度約為O(|X|2)。據(jù)此推測算法花費的計算時間受可用中繼無人機數(shù)量影響很小，而受可行布置點數(shù)量的影響較大，第4節(jié)將通過仿真來驗證推測的正確性。

4 仿真與分析

本節(jié)中，通過仿真實驗驗證算法的可行性、研究不同因素對算法性能的影響，并與其他算法進行對比分析。仿真平臺的CPU為酷睿i7-3770，3.4 GHz，仿真軟件為MATLAB R2015b。

4.1 算法可行性驗證

檢驗PTRPA算法是否能夠給出中繼節(jié)點布置問題(11)的可行解。設(shè)置仿真區(qū)域長寬均為30 km，可行布置點間距為1 km，無人機最大通信距離為8 km，無人機飛行速度為50 m/s，待中繼的節(jié)點位置坐標(biāo)見表3，區(qū)域存在的地形障礙和敵方防空威脅見表4，可用作中繼節(jié)點的無人機集合見表5。

表3 待中繼作戰(zhàn)節(jié)點位置Table 3 Position of combat node to be relayed

仿真結(jié)果如圖2所示，其中，淺灰色區(qū)域表示地形障礙覆蓋區(qū)域，深灰色區(qū)域表示敵方防空威脅覆蓋區(qū)域，綠色‘×’表示可用中繼無人機初始位置，紅色‘+’表示PTRPA算法給出的中繼布置位置點，藍色實線表示用于估計最短到達時間的簡化航路，青色實線表示構(gòu)建的中繼通信鏈路。各中繼布置點位置及對應(yīng)的無人機見表6。

表4 地形障礙及敵方防空威脅參數(shù)

表5 中繼無人機初始位置Table 5 Initial position of relay UAVs

圖2 中繼無人機布置結(jié)果示意圖Fig.2 Sketch map of result of relay UAV placement

表6 中繼無人機布置結(jié)果Table 6 Results of relay UAV placement

中繼布置點(紅色‘+’)坐標(biāo)x/m坐標(biāo)y/m對應(yīng)的無人機(綠色‘×’)花費的時間/s(青色實線)L165008500U144．7L21150014500U5127．2L31950014500U4188．6L42250021500U7215．4花費的總時間/s215．4

為實現(xiàn)點s和t間的有效通信，至少需要布置4架無人機作為中繼。圖2中：① 距離中繼布置點L2最近的無人機為U7，然而實際是由無人機U5飛往L2，而U7飛往L4，這是因為只有當(dāng)所有中繼無人機均到達對應(yīng)的中繼布置點時，中繼鏈路才能發(fā)揮功能；② 中繼鏈路s-L1-L2-L3-L4-t中任意相鄰節(jié)點間視線通信路徑均避開了地形障礙，而L3-L4卻穿越了敵方防空威脅覆蓋區(qū)域； ③ RNP問題給出的中繼鏈路s-L1-L2-L3-L4-t顯然不是從s到t最短可飛航路。

通過該仿真實驗，驗證了本文建立的RNP問題模型和給出的PTRPA算法能夠在無法直接通信的兩點間通過布置多架無人機作為中繼來實現(xiàn)有效中繼鏈路的構(gòu)建。

4.2 考慮構(gòu)建中繼鏈路花費時間必要性驗證

為了進一步驗證本文考慮構(gòu)建中繼鏈路花費最短時間的必要性，與以鏈路質(zhì)量(通過鏈路容量[25](Link Capacity)來評價)和最小無人機數(shù)量為目標(biāo)函數(shù)的中繼布置結(jié)果(圖3)比較，其中，參數(shù)設(shè)定同4.1節(jié)，結(jié)果見表7。

圖3 最大鏈路容量下的中繼布置結(jié)果示意圖Fig.3 Sketch map of result of relay UAV placement by optimizing link capacity

表7 最大鏈路容量下中繼無人機布置結(jié)果

Table 7 Results of relay UAV placement byoptimizing link capacity

中繼布置點(紅色‘+’)坐標(biāo)x/m坐標(biāo)y/m對應(yīng)的無人機花費的時間/sL155006500U10121．66L21050012500U1156．22L31650017500U5238．70L42250022500U7223．62花費的總時間/s238．70

與表6數(shù)值對比發(fā)現(xiàn)，最優(yōu)鏈路質(zhì)量指標(biāo)下中繼布置點位置和對應(yīng)的中繼無人機均發(fā)生了變化，且最短需要花費238.7 s才能完成鏈路構(gòu)建，而在本文模型和算法下，最短只需要215.4 s即可完成鏈路組建，少花費23.3 s(約10%)時間，而這在戰(zhàn)場應(yīng)急情形下，可能非常重要。驗證了RNP建模時有必要考慮構(gòu)建中繼鏈路花費的時間。

4.3 中繼布置結(jié)果對比與分析

本文建立的RNP問題(11)是難以求解的整數(shù)多目標(biāo)優(yōu)化問題(離散化處理后)，且目標(biāo)函數(shù)難以同時最優(yōu)，本節(jié)在最小化無人機數(shù)量條件下，從中繼布置結(jié)果和算法時間性能兩個方面對比分析PTRPA算法與以下兩種算法的性能：

1) 隨機抽樣方法[31](Stochastic Sample, SS)。該方法在求解空間內(nèi)隨機的選取可行解，求取這些解中構(gòu)建中繼鏈路花費時間最少的解。

2) 遺傳算法[32](Genetic Algorithm, GA)。遺傳算法是一種隨機進化算法，通過模擬生物遺傳的方式，將問題的可行解通過編碼的方式表示為遺傳的載體，即染色體，每條染色體表示一個個體，即問題的一個解，多個個體組成種群，基于適者生存、優(yōu)勝劣汰的原則，使用選擇、交叉、變異算子不斷生成新的種群，使得種群不斷趨向獲取問題的最優(yōu)解。算法借助于gatbx工具箱，采用排序選擇、單點交叉和單點變異算子。

基于Monte-Carlo方法重復(fù)100組實驗對比與分析不同因素對PTRPA、SS和GA算法構(gòu)建中繼布置平均花費的最短時間的影響，實驗中每次隨機給出無人機的初始位置及待中繼點s和t的位置，仿真區(qū)域、無人機飛行速度和防空威脅、地形障礙設(shè)置同前，SS算法初始解規(guī)模為500。具體包括：

1) 無人機數(shù)量對構(gòu)建中繼鏈路花費的最短時間的影響，設(shè)置布置點間距為1 km、無人機最大通信距離為8 km，結(jié)果如圖4(a)所示。

從圖4(a)中可以看出，隨著無人機數(shù)量的增長，構(gòu)建中繼鏈路花費的最短時間不斷減小，這是由于隨著無人機的增多，無人機更有可能分布在最優(yōu)中繼布置點附近。另外，在無人機數(shù)量較少的情況下，GA和PTRPA算法給出的結(jié)果性能接近，GA結(jié)果稍優(yōu)于PTRPA；而當(dāng)無人機數(shù)量增多時，由于GA遺傳代數(shù)的限制，PTRPA往往能夠更穩(wěn)定地給出性能更優(yōu)的解，而SS算法性能明顯不足，不宜采用。

2) 無人機最大通信距離對構(gòu)建中繼鏈路花費的最短時間的影響，設(shè)置無人機數(shù)量為10、布置點間距為1 km，結(jié)果如圖4(b)所示。

從圖4(b)可以看出，隨著無人機通信能力的增強，構(gòu)建中繼鏈路花費的最短時間不斷減小，這是由于無人機可以飛至相對較近的位置點即可完成有效中繼鏈路構(gòu)建，且本文的PTRPA算法能夠給出與GA算法性能相近的結(jié)果。

3) 布置點間距對完成中繼布置花費的最短時間的影響，設(shè)置無人機數(shù)量為10、最大通信距離為8 km，結(jié)果如圖4(c)所示。

從圖4(c)可以看出，隨著空間離散過程中布置點間距縮小，構(gòu)建中繼鏈路花費的最短時間減少，這是由于隨著離散布置點間距的減小，離散域內(nèi)最優(yōu)中繼布置點位置更趨近于連續(xù)域內(nèi)最優(yōu)中繼布置點位置。

圖4 無人機數(shù)量、無人機最大通信距離以及布置點間距對構(gòu)建中繼鏈路花費的最短時間的影響Fig.4 Influence of UAVs’ number,UAVs’ maximum communication distance and interval distance of discretizational points on average relay placement time

綜合本節(jié)仿真結(jié)果來看，PTRPA算法給出的中繼布置結(jié)果性能與最優(yōu)結(jié)果性能接近，可滿足使用要求，接下來繼續(xù)討論算法時間性能是否滿足戰(zhàn)場快速決策要求。

4.4 算法時間性能對比與分析

從算法復(fù)雜度來看，使用SS和GA算法求解本文基于多無人機的中繼布置問題的時間復(fù)雜度分別為O(|X|2+mS‖L‖)和O(|X|2+g(S2+mS‖L‖)),其中g(shù)為遺傳代數(shù)，S為初始規(guī)模。通?！琇‖≥m,種群規(guī)模不少于20，遺傳代數(shù)不少于50，于是‖L‖通常小于gS,因此通常GA算法花費的計算時間比PTRPA算法花費的計算時間多；當(dāng)S>‖L‖時，SS算法的花費的計算時間較多，而為了保證解的質(zhì)量，通常會取較大S值。綜上，通常情況下，PTRPA算法時間性能要優(yōu)于GA和SS算法時間性能。

接下來基于Monte-Carlo方法重復(fù)進行100組實驗對比并分析不同因素對PTRPA，SS和GA算法花費的平均時間的影響，以檢驗算法的時間性能。實驗中每次隨機給出無人機的初始位置及待中繼點s和t的位置，仿真區(qū)域、無人機飛行速度、地形障礙和敵方防空威脅設(shè)置同前。設(shè)置GA初始種群規(guī)模為100，遺傳代數(shù)為200；設(shè)置SS初始解規(guī)模為500。具體包括：

1) 無人機數(shù)量對算法花費的時間的影響，設(shè)置布置點間距為1 km、無人機最大通信距離為8 km，結(jié)果如圖5所示。

從圖5可以看出，無人機數(shù)量對算法花費的時間的影響幾乎可以忽略，PTRPA算法的時間性能要明顯強于GA算法，略優(yōu)于SS算法，且PTRPA算法花費的時間始終控制在毫秒級，滿足戰(zhàn)場決策實時性要求。

然而根據(jù)算法分析，PTRPA算法第2階段時間復(fù)雜性為O(m(‖L‖m+|L|+‖L‖2)),無人機數(shù)量的增加會導(dǎo)致求解空間增大，算法花費的時間應(yīng)該呈現(xiàn)增長的趨勢。單獨討論無人機數(shù)量增長對PTRPA算法第2階段花費的時間的影響結(jié)果如圖6所示，與理論分析符合。

2) 無人機最大通信距離對算法花費的時間的影響，設(shè)置無人機數(shù)量為10、布置點間距為1 km，結(jié)果如圖7所示。

圖5 無人機數(shù)量對算法花費的計算時間的影響Fig.5 Influence of UAVs’ number on average computation time cost of algorithm

圖6 無人機數(shù)量對PTRPA第2階段花費的平均 計算時間的影響Fig.6 Influence of UAVs’ number on average computation time cost of PTRPA-Stage 2

圖7 無人機最大通信距離對算法花費的計算時間 的影響Fig.7 Influence of UAVs’ maximum communication distance on average computation time cost of algorithm

從圖7可以看出，無人機通信能力對算法花費的計算時間影響幾乎可以忽略，這是因為隨著無人機通信能力增強，需要使用的中繼跳數(shù)變少，即|L|變小，而PTRPA算法時間復(fù)雜度為O(|X|2+m(‖L‖m+|L|+‖L‖2)),|L|對其影響幾乎可以忽略。

3) 布置點間距對算法花費的時間的影響，設(shè)置無人機數(shù)量為10、最大通信距離為8 km，結(jié)果如圖8所示。

圖8 布置點間距對算法花費的平均計算時間的影響Fig.8 Influence of interval distance of discretizational points on average computation time cost of algorithm

從圖8可以看出，離散過程中增加離散布置點的間距，可以顯著地提升算法的時間性能，這是因為布置點間距的增加，使得可行布置點數(shù)量減小，即|X|減小，同時PTRPA算法時間復(fù)雜度接近O(|X|2),|X|減小會導(dǎo)致花費的計算時間快速減小。另外，PTRPA算法的時間性能依然高效可靠。然而，考慮到布置點間距對算法性能的影響相對來說要大于其他因素，因此在空間離散化過程中，應(yīng)當(dāng)在滿足需求的情況下，適當(dāng)?shù)脑黾硬贾命c間距。

另外，綜合圖5和圖7來看，無人機數(shù)量和無人機最大通信距離對算法的計算時間影響很小，這是因為|X|同時遠大于|L|和m,因此在|X|不變情況下，|L|和m的對算法花費的總時間影響幾乎可以忽略，仿真結(jié)果驗證了3.3節(jié)預(yù)測“PTRPA算法花費的計算時間受可用中繼無人機數(shù)量影響很小，而受可行布置點數(shù)量的影響較大”。同時本節(jié)仿真結(jié)果也驗證了前文結(jié)論，PTRPA算法在時間性能上優(yōu)于GA算法。另外，SS算法無論是時間性能，還是結(jié)果性能，都不如這二者，一般不可取。

4.5 中繼布置成功率影響因素分析

前文討論了不同因素對算法結(jié)果和時間性能的影響，然而中繼布置的最基本要求是能夠構(gòu)建有效地通信鏈路，能否構(gòu)建有效中繼鏈路通信鏈路與無人機數(shù)量、無人機最大通信距離存在直接關(guān)系，而與問題的求解算法無關(guān)。本節(jié)旨在通過仿真實驗給出實際應(yīng)用中提升構(gòu)建有效中繼鏈路成功率的方法和建議，其中，中繼布置能否成功的判斷方法可參考PTRPA-stage的步驟21～步驟24，本文定義中繼布置成功率為

中繼布置成功率=

(14)

實驗中，通信距離分別設(shè)置為2、5、8、11和14 km，每組進行1 000次仿真實驗，其他參數(shù)設(shè)定同前，結(jié)果如圖9所示。

分析圖9給出的結(jié)果可以得出，使用盡可能多數(shù)量的無人機、盡可能大的提升無人機的通信能力，能夠提升中繼節(jié)點布置的成功率。尤其是在節(jié)點通信能力較差的情況下，必須要有足夠的無人機可被用作中繼節(jié)點。

圖9 無人機數(shù)量和最大通信距離對中繼節(jié)點 布置成功率的影響Fig.9 Influence of UAVs’ number and maximum communication distance on success ratio of relay node placement

5 結(jié) 論

1) 針對戰(zhàn)場可能出現(xiàn)的緊急通信需求，建立了基于多無人機的中繼節(jié)點布置問題模型，不但考慮了使用最少數(shù)量的中繼無人機，同時考慮了在盡可能短的時間內(nèi)完成中繼鏈路構(gòu)建。

2) 針對本文RNP問題是難以求解的NP-hard問題，給出了一種多項式時間中繼節(jié)點布置算法(PTRPA)，并理論分析了算法的時間復(fù)雜度。

3) 通過與不考慮構(gòu)建中繼鏈路花費時間的方法的對比仿真表明，本文建立的RNP模型確實能夠在更短的時間內(nèi)完成有效中繼鏈路構(gòu)建。且通過仿真對比不同因素對PTRPA、遺傳算法和隨機抽樣算法的結(jié)果性能和時間性能影響，驗證了PTRPA算法不但能夠給出接近最優(yōu)的解，且更加快速，可以滿足戰(zhàn)場決策需求。

[1] GOLDSMITH A. Wireless communication[M]. New York: Cambridge University Press, 2005: 24-53.

[2] RANGA V, DAVE M, VERMA A K. Relay node placement to heal partitioned wire less sensor networks[J]. Computers and Electrical Engineering, 2015, 48: 371-388.

[3] CALINESCU G. Relay placement for two-connectivity[J]. Discrete Optimization, 2014, 14(14): 17-33.

[4] CHANDRASHEKAR K, DEKHORDI M R, BARAS J S. Providing full connectivity in large ad hoc networks by dynamic placement of aerial platforms[C]∥Proceedings of IEEE Military Communication Conference.Piscataway,NJ: IEEE Press, 2004: 1429-1436.

[5] LANZA-GUTIERREZ J M, GOMEZ-PULIDO J A, VEGA-RODRIGUEZ M A. A trajectory algorithm to solve the relay node placement problem in wireless sensor net-works[C]∥2nd International Conference on the Theory and Practice of Natural Computing. Berlin: Springer-Verlag Berlin Heidelberg，2013: 145-156.

[6] 陸克中, 劉剛, 陶耀東, 等. 無線傳感器網(wǎng)絡(luò)中繼節(jié)點的最小功耗布置算法[J]. 小型微型計算機系統(tǒng), 2011, 32(6): 1035-1040.

LU K Z, LIU G, TAO Y D, et al. Algorithm of minimum power relay node placement in wireless sensor networks[J]. Journal of Chinese Computer Systems, 2011, 32(6): 1035-1040 (in Chinese).

[7] YANG P, YANG L, XUE Y, et al. On the optimum placement and number selection of relay nodes in multi-hop routing for minimizing communication power con-sumption[M]∥WANG R, XIAO F. Advances in Wireless Sensor Networks. Berlin: Springer, 2012: 598-612.

[8] BHATTACHARYA A, RAO A, NAVEEN K P, et al. QoS constrained optimal sink and relay placement in planned wireless sensor networks[C]∥International Conference on Signal Processing and Communications (SPCOM).Berlin: Springer, 2014.

[9] LANZA-GUTIERREZ J M, GOMEZ-PULIDO J A, VEGA-RODRIGUEZ M A, et al. A parallel evolutionary approach to solve the relay node palcement problem in wireless sensor networks[C]∥Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation. New York: ACM, 2013: 1157-1164.

[10] CHEN G, CUI S. Relay node placement in two-tiered wireless sensor networks with base stations[J]. Journal of Combinatorial Optimization, 2013, 26(3): 499-508.

[11] HAN B, LI J, SU J. Optimal relay node placement for multi-pair cooperative communication in wireless networks[C]∥Proceedings of IEEE Wireless Communications and Networking Conference.Piscataway,NJ: IEEE Press, 2013: 4724-4729.

[12] ISLAM M, DZIONG Z, SOHRABY K, et al. Capacity-optimal relay and base station placement in wireless networks[C]∥The International Conference on Information Networking.Piscataway,NJ: IEEE Press, 2012: 358-363.

[13] BURDAKOV O, DOHERTY P, HOLMBERG K, et al. Optimal placement of UV-based communication relay nodes[J]. Journal of Global Optimization, 2010, 48(4): 511-531.

[14] RUBIN I, ZHANG R H. Placement of UAVs as communication relays aiding mobile Ad Hoc wireless networks[C]∥Proceedings of IEEE Military Communications Conference MILCOM. Piscataway, NJ: IEEE Press, 2007.

[15] 鄭鍇, 童利標(biāo), 陸文駿. 應(yīng)用無人機實現(xiàn)地面無線傳感器網(wǎng)絡(luò)通信中繼的探討[J]. 現(xiàn)代電子技術(shù), 2007, 23: 40-50.

ZHENG K, TONG L B, LU W J. Discussion on the communication relay of the wireless ground sensor network by using UAV[J]. Modern Electronics Technique, 2007, 23: 40-50 (in Chinese).

[16] 朱秋明, 周生奎, 霍帥珂, 等. 無人機中繼平臺區(qū)域覆蓋統(tǒng)計模型[J]. 航空學(xué)報, 2014, 35(1): 223-229.

ZHU Q M, ZHOU S K, HUO S K, et al. A statistical area coverage model for unmanned aerial vehicles as relay platforms[J]. Acta Aeranautica et Astronautica Sinica, 2014, 35(1): 223-229 (in Chinese).

[17] 歐陽鍵, 莊毅, 薛羽. 非對稱衰落信道下無人機中繼傳輸方案及性能分析[J]. 航空學(xué)報, 2013, 34(1): 130-140.

OUYANG J, ZHUANG Y, XUE Y. UAV relay transmission scheme and its performance analysis over asymmetric fading channels[J]. Acta Aeranautica et Astronautica Sinica, 2013, 34(1): 130-140 (in Chinese).

[18] BURDAKOV O, DOHERTY P, HOMBERG K, et al. Relay positioning for unmanned aerial vehicle surveillance[J]. International Journal of Robotics Research, 2010, 29(8): 1069-1087.

[19] HAN Z, SWINDLEHURST A L, LIU K J R. Optimization of MANET connectivity via smart deployment & movement of unmanned aerial vehicles[J]. IEEE Transactions on Vehicular Technology, 2009, 58(7): 3533-3546.

[20] BOSKOVIC J D, PRASANTH R, MEHRA R K. A multi-player autonomous intelligent control architecture for unmanned aerial vehicles[J]. Journal of Aerospace Computing, Information, and Communication, 2014, 1(12): 605-629.

[21] LAWLER E L. Combinatorial optimization: networks and matroids[M]. New York: Library of Congress Catalging in Publication Data, 1976: 182-214.

[22] 雷德明, 嚴(yán)新平. 多目標(biāo)智能優(yōu)化算法及其應(yīng)用[M]. 北京: 科學(xué)出版社, 2009.

LEI D M, YAN X P. Multi-objective intelligent optimization algorithms and its application[M]. Beijing: Science Publication, 2009 (in Chinese).

[23] MANATHARA J G, SUJIT P B, BEARD R W. Multiple UAV coalition formation for a search and prosecute mission[J]. Journal of Intelligent and Robotic Systems, 2011, 62(1): 125-158.

[24] GEORGE J M, SUJIT P B, SOUSA J B. Coalition formation with communication delays and maneuvering targets[C]∥AIAA Guidance, Navigation, and Control Conference. Reston, VA: AIAA, 2010.

[25] DIXON C, FREW E W. Optimizing cascaded chains of unmanned aircraft acting as communication relays[J]. IEEE Journal on Selected Areas in Communication, 2012, 30(5): 883-898.

[26] KOPEIKIN A, PONDA S, HOW J P. Control of communication networks for teams of UAVs[M]∥VALAVA-NIS K P, VACHTSEVANOS G J. Handbook of Unmanned Aerial Vehicles. Berlin: Springer, 2015: 1619-1654.

[27] YAN Y, MOSTOFI Y. Robotic router formation in realistic communication environments[J]. IEEE Transactions on Robotics, 2012, 28(4): 810-827.

[28] 王桂平, 王衍, 任嘉層. 圖論算法理論、實現(xiàn)及應(yīng)用[M]. 北京: 北京大學(xué)出版社, 2011: 131-192.

WANG G P, WANG Y, REN J C. Graph theory, implementation and application[M]. Beijing: Peking University Press, 2011: 131-192 (in Chinese).

[29] CORMEN T H, LEISERSON C E, RIVEST R L, et al. Introduction to algorithm[M]. 3rd ed. Cambridge: MIT Press, 2009: 589-64.

[30] 姚遠, 周興社, 張凱龍, 等. 基于稀疏A*搜索和改進人工勢場的無人機動態(tài)航跡規(guī)劃[J]. 控制理論與應(yīng)用, 2010, 27(7): 953-959.

YAO Y, ZHOU X S, ZHANG K L, et al. Dynamic trajectory planning for unmanned aerial vehicle based on sparse A* search and improved artificial potential field[J]. Control Theory and Applications, 2010, 27(7): 953-959 (in Chinese).

[31] 金暢. 蒙特卡洛方法中隨機數(shù)發(fā)生器和隨機抽樣方法的研究[D]. 大連: 大連理工大學(xué), 2006.

JIN C. Study on random number generator and random sampling in Monte Carlo method[D]. Dalian: Dalian University of Technology, 2006 (in Chinese).

[32] 雷英杰, 張善文. MATLAB遺傳算法工具箱及應(yīng)用[M]. 2版. 西安: 西安電子科技大學(xué)出版社, 2014: 62-105.

LEI Y J, ZHANG S W. MATLAB genetic algorithm toolbox and its application[M]. 2nd ed. Xi’an: Xidian University Press, 2014: 62-105 (in Chinese).

Modelingandoptimizationmethodofrelaynodeplacement>usingmulti-UAV

WUGaofeng,GAOXiaoguang*,FUXiaowei

SchoolofElectronicsandInformation,NorthwesternPolytechnicalUniversity,Xi’an710072,China

Inthebattlefieldenvironment,arelaycommunicationchainisurgentlyneededtobeformedbetweentwonodeswhichareunabletocommunicate.Inthispaper,UnmannedAerialVehicles(UAVs)areusedasrelaynodes,andamodelforrelaynodeplacementisgiven.TheobjectivefunctionsaretheminimumnumberofrequiredrelayUAVsandtheminimumtimecostforformingtherelaychain,andtheconstraintsarethesafetyofUAVsandtheeffectivenessoftherelaychain.Sincetheproblemismixedintegermulti-objectiveoptimizationwhichisknownhardtobesolved,andtherequirementforquickandeffectivedecisionisurgentlyneeded,aPolynomialTimeRelayPlacementAlgorithm(PTRPA)isgiventosolvetheproblemfastandprovideasub-optimalsolution.Thefeasibilityandeffectivenessofthealgorithmisvalidatedwithsimulation,andtheimpactsofdifferentfactorsonthealgorithmisstudiedwiththeMonte-Carlomethod.Theresearchfiguresoutanewrelaynodeplacementscenariointhecomingnetworkedwarfare,andprovidesareferablemodelingandsolvingmethod.

UnmannedAerialVehicle(UAV);relay;wirelesscommunication;nodeplacement;polynomialtimealgorithm;multi-objectiveoptimization

2017-02-27；Revised2017-06-14；Accepted2017-07-17；Publishedonline2017-07-311048

URL：http://hkxb.buaa.edu.cn/CN/html/20171123.html

NationalNaturalScienceFoundationofChina(61573285)

.E-mailcxg2012@nwpu.edu.cn

http://hkxb.buaa.edu.cnhkxb@buaa.edu.cn

10.7527/S1000-6893.2017.321195

V279；TP2

A

1000-6893(2017)11-321195-13

2017-02-27；退修日期2017-06-14；錄用日期2017-07-17；< class="emphasis_bold">網(wǎng)絡(luò)出版時間

時間：2017-07-311048

http://hkxb.buaa.edu.cn/CN/html/20171123.html

國家自然科學(xué)基金(61573285)

.E-mailcxg2012@nwpu.edu.cn

吳高峰，高曉光，符小衛(wèi).一種基于多無人機的中繼節(jié)點布置問題建模與優(yōu)化方法J． 航空學(xué)報,2017,38(11):321195.WUGF,GAOXG,FUXW.Modelingandoptimizationmethodofrelaynodeplacementusingmulti-UAVJ.ActaAeronauticaetAstronauticaSinica,2017,38(11):321195.

(責(zé)任編輯：蘇磊)