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

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

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

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

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

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

無人機(jī)；中繼；無線通信；節(jié)點(diǎn)布置；多項(xiàng)式時(shí)間算法；多目標(biāo)優(yōu)化

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

中繼節(jié)點(diǎn)布置問題研究中，由于中繼節(jié)點(diǎn)(Relay Node, RN)類型和應(yīng)用背景不同，中繼布置的目標(biāo)也存在差異，現(xiàn)有的研究中主要包括：使用最少數(shù)量的中繼節(jié)點(diǎn)實(shí)現(xiàn)網(wǎng)絡(luò)的連通(Connectivity)或容錯(cuò)(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)。

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

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

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

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

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

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

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

(1)

式中：

f1(N)=k

(2)

(3)

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

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

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

(4)

(5)

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

(6)

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

(7)

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

(8)

(9)

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

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

(10)

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

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

2 空間離散化

為求解中繼節(jié)點(diǎn)布置問題式(1)～式(10)，將中繼節(jié)點(diǎn)布置范圍限制在等間距的離散點(diǎn)D′?D,如圖1所示，γ為布置點(diǎn)間距，淺色區(qū)域?yàn)榈匦握系K覆蓋區(qū)域，深色區(qū)域?yàn)閿撤椒揽胀{覆蓋區(qū)域，黑色點(diǎn)為不可行布置點(diǎn)，白色點(diǎn)為可行布置點(diǎn)。令Z′=Z∩D′及Y′=Y∩D′,于是可以得到可行布置點(diǎn)位置集合X=D′-Z′∪Y′。

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

(11)

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

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

步驟1估計(jì)存在視線路徑的所有xi、xj間的最短到達(dá)時(shí)間:

(12)

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

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

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

3 多項(xiàng)式時(shí)間中繼節(jié)點(diǎn)布置算法

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

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

算法偽代碼見表1。

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

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

定理2經(jīng)過PTRPA-Stage 1，不存在經(jīng)過其他可行布置點(diǎn)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é)點(diǎn)t,由于G為無向圖，那么從t通過BFS經(jīng)過|L|-1-i跳也必然能夠搜索到節(jié)點(diǎn)，因此xw不會(huì)從L中被刪除。定理2得證。

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

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

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

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

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

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

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

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

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

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

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

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

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

(13)

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

4 仿真與分析

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

4.1 算法可行性驗(yàn)證

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

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

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

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

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

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

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

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

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

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

4.2 考慮構(gòu)建中繼鏈路花費(fèi)時(shí)間必要性驗(yàn)證

為了進(jìn)一步驗(yàn)證本文考慮構(gòu)建中繼鏈路花費(fèi)最短時(shí)間的必要性，與以鏈路質(zhì)量(通過鏈路容量[25](Link Capacity)來評(píng)價(jià))和最小無人機(jī)數(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 最大鏈路容量下中繼無人機(jī)布置結(jié)果

Table 7 Results of relay UAV placement byoptimizing link capacity

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

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

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

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

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

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

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

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

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

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

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

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

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

圖4 無人機(jī)數(shù)量、無人機(jī)最大通信距離以及布置點(diǎn)間距對(duì)構(gòu)建中繼鏈路花費(fèi)的最短時(shí)間的影響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ù)討論算法時(shí)間性能是否滿足戰(zhàn)場快速?zèng)Q策要求。

4.4 算法時(shí)間性能對(duì)比與分析

從算法復(fù)雜度來看，使用SS和GA算法求解本文基于多無人機(jī)的中繼布置問題的時(shí)間復(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算法花費(fèi)的計(jì)算時(shí)間比PTRPA算法花費(fèi)的計(jì)算時(shí)間多；當(dāng)S>‖L‖時(shí)，SS算法的花費(fèi)的計(jì)算時(shí)間較多，而為了保證解的質(zhì)量，通常會(huì)取較大S值。綜上，通常情況下，PTRPA算法時(shí)間性能要優(yōu)于GA和SS算法時(shí)間性能。

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

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

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

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

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

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

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

圖7 無人機(jī)最大通信距離對(duì)算法花費(fèi)的計(jì)算時(shí)間 的影響Fig.7 Influence of UAVs’ maximum communication distance on average computation time cost of algorithm

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

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

圖8 布置點(diǎn)間距對(duì)算法花費(fèi)的平均計(jì)算時(shí)間的影響Fig.8 Influence of interval distance of discretizational points on average computation time cost of algorithm

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

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

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

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

中繼布置成功率=

(14)

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

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

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

5 結(jié) 論

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

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

3) 通過與不考慮構(gòu)建中繼鏈路花費(fèi)時(shí)間的方法的對(duì)比仿真表明，本文建立的RNP模型確實(shí)能夠在更短的時(shí)間內(nèi)完成有效中繼鏈路構(gòu)建。且通過仿真對(duì)比不同因素對(duì)PTRPA、遺傳算法和隨機(jī)抽樣算法的結(jié)果性能和時(shí)間性能影響，驗(yàn)證了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é)點(diǎn)的最小功耗布置算法[J]. 小型微型計(jì)算機(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)用無人機(jī)實(shí)現(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] 朱秋明, 周生奎, 霍帥珂, 等. 無人機(jī)中繼平臺(tái)區(qū)域覆蓋統(tǒng)計(jì)模型[J]. 航空學(xué)報(bào), 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] 歐陽鍵, 莊毅, 薛羽. 非對(duì)稱衰落信道下無人機(jī)中繼傳輸方案及性能分析[J]. 航空學(xué)報(bào), 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] 王桂平, 王衍, 任嘉層. 圖論算法理論、實(shí)現(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] 姚遠(yuǎn), 周興社, 張凱龍, 等. 基于稀疏A*搜索和改進(jìn)人工勢場的無人機(jī)動(dòng)態(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] 金暢. 蒙特卡洛方法中隨機(jī)數(shù)發(fā)生器和隨機(jī)抽樣方法的研究[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ò)出版時(shí)間

時(shí)間：2017-07-311048

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

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

.E-mailcxg2012@nwpu.edu.cn

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

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