面向感知任務(wù)的無人機(jī)數(shù)量編配與頻譜資源聯(lián)合規(guī)劃方法

廖乃穩(wěn) 錢鵬智 陳勇，2 張余*

（1.國防科技大學(xué)第六十三研究所, 南京 210007；2.陸軍工程大學(xué)通信工程學(xué)院, 南京 210007）

0 引 言

無人機(jī)具有機(jī)動性強(qiáng)、部署快速和攜帶載荷靈活等特點(diǎn)[1-2]，廣泛應(yīng)用于環(huán)境勘察、災(zāi)情搜救和中繼通信[3-5]等任務(wù).隨著任務(wù)量和任務(wù)類型的增多，單架無人機(jī)已經(jīng)難以勝任，需要多無人機(jī)相互協(xié)作以滿足任務(wù)需求[6].多無人機(jī)系統(tǒng)相比單無人機(jī)，有更好的任務(wù)適應(yīng)性和應(yīng)用潛力[7]，更適合執(zhí)行復(fù)雜任務(wù).盡管多無人機(jī)系統(tǒng)有很大的優(yōu)勢，但也面臨著頻譜資源使用沖突等問題.多無人機(jī)系統(tǒng)需要確定合理的數(shù)量編配并形成高效的協(xié)同關(guān)系.不合理的數(shù)量編配會增加無人機(jī)的資源浪費(fèi)和頻譜沖突概率；不合理的頻譜分配可能會延長任務(wù)的時(shí)間，進(jìn)而增加無人機(jī)的能耗.無人機(jī)的數(shù)量編配、目標(biāo)感知順序和頻譜資源分配相互耦合，共同決定最優(yōu)的感知任務(wù)規(guī)劃方案.

編配多架無人機(jī)的協(xié)同感知會涉及任務(wù)分配問題，這是近幾年一個活躍的研究領(lǐng)域，已有大量的研究成果可供借鑒.一些研究工作從能耗的角度研究無人機(jī)的任務(wù)分配.文獻(xiàn)[8]研究了無人機(jī)群的多任務(wù)協(xié)作問題，考慮了任務(wù)類型的重疊和互補(bǔ)關(guān)系，將無人機(jī)的任務(wù)分配問題建模為聯(lián)盟形成博弈問題，提出了一種異構(gòu)多無人機(jī)的節(jié)能任務(wù)協(xié)作方案，最小化聯(lián)盟能量消耗.文獻(xiàn)[9]研究了自組織網(wǎng)絡(luò)中的分層無人機(jī)任務(wù)調(diào)度問題，其中一些無人機(jī)執(zhí)行區(qū)域覆蓋任務(wù)，另一些無人機(jī)提供邊緣計(jì)算服務(wù)，通過塊坐標(biāo)下降法和連續(xù)凸逼近技術(shù)，最小化無人機(jī)的整體能耗.文獻(xiàn)[10]研究了有人機(jī)與無人機(jī)聯(lián)合執(zhí)行任務(wù)的編隊(duì)方法，引入了無人機(jī)對受限資源和非受限資源的需求，提出了一種多目標(biāo)優(yōu)化算法減少資源冗余.文獻(xiàn)[11]研究了多無人機(jī)的任務(wù)分配和路徑規(guī)劃問題，在路徑規(guī)劃中利用遺傳算法獲得無人機(jī)與任務(wù)相互之間的偏好列表，并用匹配算法解決了多無人機(jī)的任務(wù)分配問題.文獻(xiàn)[12]以提高能源效率為目標(biāo)，研究了多無人機(jī)接力輔助通信的優(yōu)化策略，基于粒子群算法提出了無人機(jī)的部署與循環(huán)充能算法.

多無人機(jī)系統(tǒng)中的網(wǎng)絡(luò)優(yōu)化是影響性能發(fā)揮的關(guān)鍵，現(xiàn)有研究也對頻譜資源的優(yōu)化做了大量工作.為避免無人機(jī)集群的通信自干擾，文獻(xiàn)[13-15]研究了任務(wù)驅(qū)動的無人機(jī)通信網(wǎng)絡(luò)頻譜資源分配問題，將任務(wù)與頻譜分配的耦合關(guān)系建模為博弈模型，提出了聯(lián)盟形成博弈算法，聯(lián)合優(yōu)化任務(wù)選擇與頻譜資源分配.文獻(xiàn)[16]針對傳統(tǒng)聯(lián)盟形成中無人機(jī)只能加入一個聯(lián)盟而導(dǎo)致效益不高的問題，提出了一種重疊聯(lián)盟形成博弈算法，通過重疊聯(lián)盟成員的部分合作優(yōu)化任務(wù)資源的分配.

無人機(jī)任務(wù)規(guī)劃的現(xiàn)有研究主要集中在給定無人機(jī)數(shù)量時(shí)優(yōu)化任務(wù)的能耗和提高頻譜資源效益上，而忽略了完成任務(wù)需要的無人機(jī)數(shù)量編配及多無人機(jī)共存帶來的頻譜使用沖突問題.在實(shí)際規(guī)劃中，往往需要根據(jù)任務(wù)計(jì)算無人機(jī)的數(shù)量編配需求，并為每架無人機(jī)規(guī)劃合理的任務(wù)量和頻譜資源保障.頻譜共享能夠有效提高多無人機(jī)系統(tǒng)的頻譜效率和網(wǎng)絡(luò)性能，但同時(shí)也對頻譜沖突消解技術(shù)提出了更高的要求.本文在多無人機(jī)共享頻譜資源條件下，研究協(xié)同感知任務(wù)的無人機(jī)數(shù)量編配需求、感知順序和頻譜使用的聯(lián)合優(yōu)化問題.主要工作總結(jié)如下：

1)提出了一種無人機(jī)數(shù)量編配需求、目標(biāo)關(guān)聯(lián)和頻譜分配的聯(lián)合規(guī)劃方法，其中無人機(jī)協(xié)同感知多個分布的目標(biāo)并將感知信息回傳至決策中心.該方法可以根據(jù)無人機(jī)電池容量和任務(wù)量自行調(diào)整參與感知的無人機(jī)數(shù)量，并為每架無人機(jī)規(guī)劃目標(biāo)感知順序和頻譜使用時(shí)間，在消除信息傳輸干擾的同時(shí)，有效減少了完成任務(wù)所需的能耗.

2)提出了一種改進(jìn)的遺傳禁忌混合算法，有效增強(qiáng)了全局尋優(yōu)能力.所提算法結(jié)合遺傳算法的大范圍探索能力與禁忌搜索算法的局部搜索優(yōu)勢，既可以在解空間內(nèi)大范圍探索，又能夠進(jìn)行小范圍精細(xì)搜索，不斷突破歷史局部最優(yōu)解，進(jìn)一步降低完成協(xié)同感知任務(wù)的能耗.同時(shí)所提算法受初始值的隨機(jī)影響較小，具有更好的魯棒性.

1 系統(tǒng)模型和問題建模

圖1 所示為考慮運(yùn)用無人機(jī)執(zhí)行感知任務(wù)的場景，無人機(jī)從決策中心出發(fā)逐個飛至目標(biāo)上空懸停進(jìn)行信息感知，并將收集的感知數(shù)據(jù)回傳到?jīng)Q策中心進(jìn)行處理.無人機(jī)的電池容量一般較小，無法支撐長時(shí)間工作的能量消耗，當(dāng)目標(biāo)比較多時(shí)，一架無人機(jī)可能無法完成所有目標(biāo)的感知任務(wù)，需要多架無人機(jī)協(xié)同感知.假設(shè)有M架無人機(jī)前往K個分布在地面的固定目標(biāo)執(zhí)行協(xié)同感知任務(wù)，無人機(jī)和目標(biāo)的集合分別表示為M0={1,···,M}和K0={1,···,K}.

地面感知目標(biāo)的水平坐標(biāo)用qk∈R2×1表示，并且是已知的.目標(biāo)k與決策中心的距離可表示為

式中：qc表 示決策中心的水平坐標(biāo)； //·//表示歐氏距離.我們假設(shè)使用小型旋翼無人機(jī)執(zhí)行任務(wù)，其可以懸停在空中以獲得穩(wěn)定的通信傳輸質(zhì)量.無人機(jī)的能量消耗分為運(yùn)動能耗和通信能耗兩部分，一般來說，通信能耗比運(yùn)動能耗低幾個數(shù)量級[17]，經(jīng)常被忽略不計(jì)，因此主要考慮無人機(jī)的運(yùn)動能耗[18].當(dāng)無人機(jī)以速度v勻速運(yùn)動時(shí)，其功率消耗可表示為[19]

式中：P0和Pi分別表示懸停狀態(tài)下的葉片輪廓功率和感應(yīng)功率；Utip和v0分別表示懸停狀態(tài)下的旋翼尖端速度和旋翼平均速度；d0和s分別表示機(jī)身阻力比和旋翼實(shí)心度； ρ和A分別表示空氣密度和旋翼圓盤面積.當(dāng)目標(biāo)間距離較遠(yuǎn)時(shí)，無人機(jī)的加速和減速時(shí)間相比目標(biāo)間機(jī)動的時(shí)間很短，可以忽略無人機(jī)的加速減速過程[20]，無人機(jī)在目標(biāo)間機(jī)動時(shí)采用勻速飛行，執(zhí)行感知任務(wù)時(shí)懸停.無人機(jī)在不同飛行速度下的能耗并不相同，由式(2)可以驗(yàn)證，無人機(jī)的飛行功率消耗隨速度的遞增先減小后增大[19]，存在最大續(xù)航時(shí)間速度Vme和最大續(xù)航里程速度Vmr.在相同的能量消耗下，Vme是無人機(jī)續(xù)航時(shí)間最長的飛行速度，Vmr是無人機(jī)巡航距離最遠(yuǎn)的飛行速度.為節(jié)省能量開支，我們假設(shè)無人機(jī)在目標(biāo)之間飛行時(shí)使用速度Vmr，因此無人機(jī)完成目標(biāo)k的感知任務(wù)后飛到下一個目標(biāo)k′所需的最小飛行能耗為

無人機(jī)采用光學(xué)成像或者邊感知信息邊回傳等方式，信息感知時(shí)間忽略不計(jì)，懸停時(shí)間以無人機(jī)的信息回傳時(shí)間計(jì)算.得益于無人機(jī)的升空增益，空對地的信道功率增益主要由視距鏈路決定，可以基于自由空間路徑損耗模型表示為[21]

式中， β0表示參考距離為1 m 的信道功率增益.無人機(jī)在目標(biāo)間機(jī)動時(shí)不占用頻譜資源，只有懸停在目標(biāo)上空回傳感知信息時(shí)才需要頻譜資源的保障，多架無人機(jī)共享同一段頻譜資源，會造成頻譜沖突，合理的頻譜規(guī)劃至關(guān)重要.當(dāng)兩架無人機(jī)同時(shí)需要使用頻譜資源時(shí)，圖2 給出了不同頻譜資源分配比例時(shí)的無人機(jī)總能耗.由圖2 可知獨(dú)占式的頻譜分配是最節(jié)能的方式，即將頻譜資源全部分配給占用時(shí)間最短的無人機(jī)m1使用，其余無人機(jī)以最小能耗速度Vme盤旋等待.無人機(jī)m1完成信息回傳后，再將頻譜資源全部分配給剩余的占用時(shí)間最短的無人機(jī)使用，以此類推，直至所有無人機(jī)完成信息回傳.

圖2 不同頻譜分配比例的無人機(jī)總能耗Fig.2 Total energy consumption of UAVs with different spectrum allocation ratios

但這種頻譜共享方式也可能導(dǎo)致正在傳輸?shù)男畔⒅袛啵⒉贿m合語音、視頻等需要連續(xù)傳輸?shù)娜蝿?wù).為此，我們以同一目標(biāo)的信息回傳不間斷為基礎(chǔ)，設(shè)計(jì)了能耗最小的無人機(jī)頻譜使用時(shí)間分配方法.圖3 展示了兩架無人機(jī)頻譜使用時(shí)間存在沖突的情況之一及能耗最小的頻譜調(diào)整方法.在調(diào)整之前，兩架無人機(jī)頻譜使用時(shí)間存在重疊，會在t2時(shí)間內(nèi)相互干擾.無人機(jī)1 先傳輸時(shí)，無人機(jī)2 的等待時(shí)間為t2，反之則無人機(jī)1 的等待時(shí)間為t1.由于t2

圖3 能耗最小的頻譜時(shí)間調(diào)整示例Fig.3 Example of spectrum time adjustment with minimum energy consumption

可用頻譜資源的帶寬為W、目標(biāo)k感知的信息量為Ck時(shí)，無人機(jī)m的懸停時(shí)間為

式中：pm表示無人機(jī)m的發(fā)射功率； σ2表示環(huán)境噪聲功率譜密度.無人機(jī)在目標(biāo)k的懸停能耗為

式中，P(0)表示無人機(jī)速度為0 時(shí)飛行功率消耗，即懸停時(shí)的功率消耗.

假 設(shè) 無 人機(jī)m以順 序πm=(πm(0),···,πm(Km+1))完成目標(biāo)集合中所有目標(biāo)的感知任務(wù)，Km表示無人機(jī)m分 配 的 目 標(biāo) 數(shù).為 方 便 書 寫 形 式， πm(0)和πm(Km+1)(?m∈M0)都表示無人機(jī)決策中心.由于共享頻譜資源，當(dāng)存在頻譜沖突時(shí)根據(jù)頻譜使用時(shí)間分配方法會產(chǎn)生等待時(shí)間，假設(shè)無人機(jī)m總的等待時(shí)間為，因等待頻譜而產(chǎn)生的能耗為

因此無人機(jī)m的總能耗為

一個目標(biāo)只需要一架無人機(jī)進(jìn)行感知，目標(biāo)k與無人機(jī)m的關(guān)聯(lián)關(guān)系表示為

無人機(jī)m按照感知順序 πm， 在第km(1 ≤km≤Km)個目標(biāo)上空懸停的時(shí)間為

由于無人機(jī)的頻譜資源采用獨(dú)占的方式使用，不同無人機(jī)的頻譜使用時(shí)間不能有重疊，否則將會在決策中心的接收機(jī)處產(chǎn)生干擾.無人機(jī)的懸停時(shí)間不能有重疊，即

本文的優(yōu)化目標(biāo)是在給定頻譜資源條件下，利用最少的無人機(jī)完成信息感知任務(wù)，并為每架無人機(jī)規(guī)劃目標(biāo)感知順序和頻譜使用時(shí)間.多無人機(jī)協(xié)同完成信息感知任務(wù)，本質(zhì)上是一個帶約束的多旅行商問題(multiple traveling salesmen problem, MTSP)，所有無人機(jī)都從決策中心出發(fā)，每個目標(biāo)只需一架無人機(jī)進(jìn)行感知.圖4 展示了一種多無人機(jī)協(xié)同感知規(guī)劃方案，其中，無人機(jī)1 完成目標(biāo) π1(K1)后回到?jīng)Q策中心，目標(biāo) π2(1)分配給無人機(jī)2.無人機(jī)的總路程為

圖4 多無人機(jī)協(xié)同感知方案示例Fig.4 Example of a multi-UAV cooperative perception solution

式 中：sπ1(K1),π1(K1+1)和sπ2(0),π2(1)分別 表 示目 標(biāo) π1(K1)至 決 策中 心 和 決 策 中 心 至 目 標(biāo) π2(1) 的 距 離；s-表 示 除sπ1(K1),π1(K1+1)和sπ2(0),π2(1)之外的其他路程.若將無人機(jī)2 的目標(biāo)都分配給無人機(jī)1，則無人機(jī)的總路程為

式中，sπ1(K1),π2(1)表 示目標(biāo) π1(K1)至 目標(biāo) π2(1)的距離.由于 π1(K1+1)和 π2(0)都表示決策中心，因此有

即s≥s′.因此，參與感知的無人機(jī)數(shù)量越少，則總路程越短，能耗也越少.

但是單架無人機(jī)無法完成大規(guī)模的感知任務(wù)，需要多架無人機(jī)協(xié)同配合.合理的無人機(jī)感知順序和頻譜使用時(shí)間，能夠提高任務(wù)效率，減少無人機(jī)的頻譜等待時(shí)間，進(jìn)而降低無人機(jī)的能耗.因此優(yōu)化目標(biāo)實(shí)質(zhì)上可以轉(zhuǎn)化為在給定頻譜資源條件下，優(yōu)化無人機(jī)的數(shù)量、每架無人機(jī)的感知順序和頻譜使用時(shí)間，使多無人機(jī)系統(tǒng)的總能耗最小.優(yōu)化問題的數(shù)學(xué)模型表示為

式中： π={π1,···,πM}表示不同無人機(jī)的感知順序集合；Th={···,}表示不同無人機(jī)的頻譜使用時(shí)間集合，={T,···,Km}； C1表示無人機(jī)任務(wù)量的能量需求必須在電池容量范圍之內(nèi)； C2和 C3表示每個目標(biāo)都必須有一架無人機(jī)進(jìn)行感知，允許所有任務(wù)都由一架無人機(jī)完成； C4表示無人機(jī)的頻譜使用時(shí)間不能重疊，否則會相互干擾，影響信息的正常接收.這是一個混合整數(shù)非線性規(guī)劃(mixed-integer nonlinear programming, MINLP)難題，待優(yōu)化變量相互耦合，難以用現(xiàn)有優(yōu)化方法求解，最優(yōu)方案的求解具有挑戰(zhàn)性.

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

2.1 算法流程

遺傳算法[22]具有很強(qiáng)的全局探索能力，能在解空間中的大部分區(qū)域進(jìn)行廣泛搜索.禁忌搜索[23]具有較強(qiáng)的局部搜索能力，能與遺傳算法形成互補(bǔ)關(guān)系.本文設(shè)計(jì)改進(jìn)的遺傳禁忌搜索混合算法，首先利用遺傳算法的交叉、變異操作產(chǎn)生解空間內(nèi)差異較大的個體，確保種群多樣性；然后再利用禁忌搜索算法的局部搜索能力，使個體不斷突破已經(jīng)達(dá)到的局部最優(yōu)解.遺傳算法的分布式搜索和禁忌算法的集中式搜索相互作用，最終收斂到近似最優(yōu)解.算法的流程如圖5 所示.

圖5 算法流程Fig.5 Algorithm process

種群經(jīng)過交叉和變異后，產(chǎn)生新的無人機(jī)感知方案，但因?yàn)榻徊孀儺惖碾S機(jī)性，可能產(chǎn)生超出解空間的個體.為解決這個問題，所提算法增加了無人機(jī)數(shù)量調(diào)整和頻譜時(shí)間調(diào)整兩個模塊，以確保新解的正確性.在進(jìn)化的后期，為突破已有的局部最優(yōu)解，利用禁忌搜索算法增加獲得全局最優(yōu)解的概率.

算法采用兩條染色體表示無人機(jī)的感知方案，其中一條長度為K的染色體表示各目標(biāo)的感知順序，另一條長度為M的染色體表示各無人機(jī)的感知目標(biāo)數(shù)量.圖6 展示了3 架無人機(jī)感知10 個目標(biāo)的兩條染色體方案例子，其中無人機(jī)1 按4、2 和5 的順序感知3 個目標(biāo)，其余無人機(jī)分配的任務(wù)類似.

圖6 兩條染色體感知方案Fig.6 Two chromosomes solution

2.2 交叉操作

交叉是結(jié)合兩個父代信息產(chǎn)生子代的方法，它可以結(jié)合父代不同的優(yōu)秀基因而產(chǎn)生更優(yōu)秀的子代個體.但由于目標(biāo)編號的唯一性和感知順序的有向性，傳統(tǒng)的交叉方法容易產(chǎn)生目標(biāo)的遺漏和重復(fù)，為了解決這個問題，本文對交叉算子進(jìn)行了調(diào)整，在傳承不同父代特征的同時(shí)，也保證了子代的正確性.具體的交叉方法如圖7 所示，兩條父代染色體經(jīng)過傳統(tǒng)交叉算子后，產(chǎn)生的子代c1中目標(biāo)1 和2 重復(fù)出現(xiàn)，且目標(biāo)3 和7 被遺漏，在去除重復(fù)的目標(biāo)后，按原先的順序補(bǔ)齊遺漏的目標(biāo)，以產(chǎn)生正確的子代.

圖7 交叉算子Fig.7 Crossover operator

2.3 變異操作

變異是為防止較好的個體占領(lǐng)整個種群而過早地收斂于局部最優(yōu)解，它增加了算法的全局搜索能力.本文關(guān)注協(xié)同感知任務(wù)的無人機(jī)數(shù)量編配，需要分別考慮對無人機(jī)數(shù)量、每架無人機(jī)任務(wù)量和感知順序的變異.

為探索最少無人機(jī)數(shù)量的感知方案，在無人機(jī)數(shù)量的變異中，任務(wù)量最少的兩架無人機(jī)合并，生成減少一架無人機(jī)執(zhí)行任務(wù)的方案.在無人機(jī)任務(wù)量的變異中，隨機(jī)選取兩架無人機(jī)，將其中一架無人機(jī)一個目標(biāo)分配給另外一架.在感知順序的變異中，隨機(jī)選取兩個目標(biāo)，將其順序進(jìn)行互換.經(jīng)過變異后，可能產(chǎn)生更好的新方案，能在遺傳算法的選擇操作中以更大的概率保留至下一代.

2.4 無人機(jī)數(shù)量調(diào)整

為滿足無人機(jī)能耗和頻譜的要求，需要對交叉變異產(chǎn)生的新方案進(jìn)行可行性處理，其中頻譜使用時(shí)間調(diào)整已在系統(tǒng)模型和問題建模中進(jìn)行了具體敘述，下面描述無人機(jī)數(shù)量調(diào)整方案.

對能耗不滿足約束的方案，采用增加無人機(jī)分擔(dān)部分任務(wù)的方式，直至所有無人機(jī)都滿足約束.具體操作如圖8 所示，假設(shè)無人機(jī)2 所需的能耗超出，增加1 架無人機(jī)分擔(dān)部分任務(wù)，直到所有無人機(jī)的能耗都不超過.

圖8 無人機(jī)數(shù)量調(diào)整Fig.8 Adjustment of the number of UAVs

2.5 禁忌搜索

隨著遺傳算法進(jìn)化代數(shù)的增加，種群中不同個體的差異也逐步減小，導(dǎo)致遺傳算法進(jìn)化速度變緩.本文引入禁忌搜索算法，當(dāng)遺傳算法的進(jìn)化代數(shù)達(dá)到最大代數(shù)的一定比例后，以種群的部分個體作為初始解，利用禁忌搜索算法進(jìn)行局部搜索，尋求更優(yōu)的感知方案.禁忌搜索算法的具體流程如圖9所示.本文采用2-opt 的鄰域搜索算子[24]，以個體為初始解，隨機(jī)選擇兩個目標(biāo)并交換他們的順序，以搜尋更優(yōu)的感知順序.

圖9 禁忌搜索流程Fig.9 Tabu search process

3 仿真與分析

為驗(yàn)證所提改進(jìn)的遺傳禁忌混合算法的效率和有效性，將其與遺傳算法、禁忌搜索算法、模擬退火算法和粒子群算法等啟發(fā)式算法進(jìn)行對比.仿真還展示了不同任務(wù)參數(shù)下的算法性能.為使仿真參數(shù)設(shè)置更為合理，參考文獻(xiàn)[16, 19, 25]，關(guān)鍵參數(shù)設(shè)置如表1 所示.

表1 仿真參數(shù)設(shè)置Tab.1 Simulation parameter setting

圖10 和圖11 展示了任務(wù)數(shù)為10 和14 時(shí)的無人機(jī)數(shù)量規(guī)劃與頻譜使用時(shí)間劃分結(jié)果.由兩圖可知，算法會根據(jù)任務(wù)規(guī)模的變化，派遣不同數(shù)量的無人機(jī)，并為每架無人機(jī)規(guī)劃合理的感知順序和頻譜使用時(shí)間，消除通信干擾.此外，算法并不只是以最小飛行距離為目標(biāo)，而是綜合考慮無人機(jī)的電池容量、目標(biāo)距離和感知順序所產(chǎn)生的頻譜等待時(shí)間的能量消耗，合理安排每架無人機(jī)的任務(wù)量與目標(biāo)感知順序，并規(guī)劃相應(yīng)的頻譜使用時(shí)間.當(dāng)有10 個目標(biāo)時(shí)，需要有3 架無人機(jī)，總消耗能量237.93 kJ.隨著任務(wù)量增加到14 個，需要的能量為288.01 kJ，超過了3 架無人機(jī)的電池容量，算法將無人機(jī)的數(shù)量增加到4 架.圖11 展示了優(yōu)化后的無人機(jī)頻譜使用時(shí)間，在“頻譜時(shí)間調(diào)整”步驟，算法以最小能耗消耗為準(zhǔn)則調(diào)整各無人機(jī)的頻譜使用時(shí)間，消除信息傳輸?shù)母蓴_.

圖10 不同任務(wù)規(guī)模的任務(wù)規(guī)劃結(jié)果Fig.10 Mission planning results for different mission numbers

圖12 展示了五種算法分別在任務(wù)量為10 和14 兩種場景下的對比結(jié)果.由于迭代次數(shù)相差較大，圖12 采用了上下雙橫坐標(biāo)表示不同算法的迭代次數(shù).其中上橫坐標(biāo)表示模擬退火算法的進(jìn)化代數(shù)，下橫坐標(biāo)表示其他算法的進(jìn)化代數(shù).為消除隨機(jī)性，每種算法均運(yùn)行100 次取其平均值作為比較結(jié)果.禁忌搜索算法全局搜索能力較差，模擬退火算法受初值影響較大，容易陷入局部最優(yōu)解，經(jīng)過同樣的進(jìn)化代數(shù)，所得方案的無人機(jī)能耗明顯高于其他算法.粒子群算法雖然在一定程度上克服了初值依賴性問題，但在進(jìn)化的后期，其向自身歷史最優(yōu)和慣性方向的趨勢可能會阻礙粒子對更多空間的搜索，優(yōu)化趨勢難以為繼.所提算法在前250 代利用遺傳算法大范圍搜索較優(yōu)的可行解，而后將遺傳算法與禁忌搜索算法相結(jié)合，增強(qiáng)了算法的尋優(yōu)能力.由圖12 可知，在250 代后，所提算法開始明顯優(yōu)于遺傳算法，這是由于所提算法局部搜索能力的優(yōu)勢開始凸顯，它能夠改善遺傳算法收斂速度變慢的缺陷，進(jìn)一步降低了無人機(jī)的能耗需求.完成相同的任務(wù)量時(shí)，所提算法實(shí)現(xiàn)了最低的能耗，說明了所提算法的有效性.

圖12 不同算法的能耗結(jié)果對比Fig.12 Comparison of the energy consumption results for different algorithms

圖13 展示了任務(wù)量為10 時(shí)不同算法運(yùn)行100 次的能耗優(yōu)化統(tǒng)計(jì)結(jié)果.箱圖的紅色橫線為算法結(jié)果的中位數(shù)，箱圖低邊和頂邊分別為第25%和75%分位數(shù)，虛線覆蓋了結(jié)果的大部分范圍.由箱圖可知，禁忌搜索算法、模擬退火算法和粒子群算法結(jié)果較為分散，這是由于三種算法對初值的依賴性較大，且聯(lián)合優(yōu)化問題既要考慮無人機(jī)數(shù)量，也要規(guī)劃合理的頻譜使用時(shí)間，較差的初值難以優(yōu)化出最優(yōu)解.所提算法受初始值隨機(jī)性的影響最小，所得優(yōu)化結(jié)果性能最好.所提算法增加了無人機(jī)數(shù)量調(diào)整和頻譜時(shí)間調(diào)整兩個模塊，其復(fù)雜度均為O(M)，M為無人機(jī)數(shù)量.在前g1/2 次 迭代中(g1為遺傳禁忌混合算法的迭代次數(shù))只使用了遺傳算法，復(fù)雜度為O(g1pM)，其中p為種群規(guī)模.而后抽取20%作為禁忌搜索算法的初始解進(jìn)一步優(yōu)化，禁忌搜索算法的復(fù)雜度為O(2g2(+2Kl)M)，其中g(shù)2為禁忌搜索算法迭代次數(shù)，K為感知目標(biāo)數(shù)，l為禁忌表長度.因此所提算法總的復(fù)雜度為O(2g1pM+0.1g1p(2g2(+2Kl)M)).雖然相比于其他算法在復(fù)雜度上有所增加，但作為無人機(jī)任務(wù)執(zhí)行前的規(guī)劃是可行的，且規(guī)劃結(jié)果穩(wěn)定，即算法魯棒性好，說明了所提算法的有效性.

圖13 任務(wù)量為10 時(shí)不同算法能耗優(yōu)化結(jié)果統(tǒng)計(jì)Fig.13 Statistics of energy consumption optimization results for different algorithms with 10 missions

圖14 展示了不同算法在任務(wù)量變化時(shí)的能耗和無人機(jī)數(shù)量需求結(jié)果.當(dāng)任務(wù)量較少時(shí)，解空間規(guī)模較小，五種算法都能夠得到最優(yōu)解.隨著任務(wù)量的增加，解空間規(guī)模呈指數(shù)式增長，算法的差距也隨之增大.所提算法相比其他算法，需要的無人機(jī)數(shù)量最少，即使與其他算法有相同的無人機(jī)數(shù)量需求，完成任務(wù)的能耗也最少.同時(shí)，任務(wù)量越大，無人機(jī)的數(shù)量需求越多，解空間的復(fù)雜度也越大，所提算法具有較好的全局探索與局部搜索能力，能夠在解空間范圍內(nèi)大范圍搜索最優(yōu)解，且隨著復(fù)雜度的提升，算法的優(yōu)勢也更明顯.所提算法相比禁忌搜索算法的能耗有20.7%的降低，說明了所提算法的有效性.

圖14 不同算法在任務(wù)量變化時(shí)的能耗和無人機(jī)數(shù)量需求結(jié)果Fig.14 Results of energy consumption and UAV number requirements for different algorithms with varying mission numbers

4 結(jié) 論

從頻譜資源管理的角度，以能耗最小為原則研究了感知任務(wù)的無人機(jī)數(shù)量編配與頻譜資源聯(lián)合規(guī)劃問題，以求解最少的無人機(jī)數(shù)量編配和無干擾頻譜資源使用規(guī)劃.利用待優(yōu)化變量與能耗的耦合關(guān)系，將問題轉(zhuǎn)化為無人機(jī)的能耗優(yōu)化，并設(shè)計(jì)了遺傳禁忌混合算法.首先利用遺傳算法的全局尋優(yōu)能力，產(chǎn)生廣泛分布的候選解，再利用禁忌搜索算法的集中搜索特點(diǎn)，進(jìn)行精細(xì)化局部搜索，得到最優(yōu)解.所提算法能夠根據(jù)任務(wù)量的變化，自動調(diào)整參與感知任務(wù)的無人機(jī)數(shù)量，并為每架無人機(jī)規(guī)劃目標(biāo)感知順序和頻譜使用時(shí)間.仿真結(jié)果證明了所提算法的有效性與魯棒性，它能夠減少無人機(jī)的數(shù)量需求和能耗.此外，仿真結(jié)果還證明了任務(wù)量越多，所提算法的優(yōu)勢越明顯，可以支持無人機(jī)的集群使用.