肖 剛，鄒永顯，王 雷，鄒浩彥

(1.中國電子科技集團公司第二十研究所，陜西 西安 710068；2.解放軍63963部隊,北京 100072；3.中航飛機股份有限公司特設(shè)技術(shù)室，陜西 西安 710089；4.解放軍駐西飛公司軍事代表室，陜西 西安 710089)

0 引 言

無人機集群具有協(xié)同能力強、任務(wù)執(zhí)行單元多、成本相對低等特點，適合在復雜環(huán)境下完成搜索、偵察、打擊等任務(wù)[1]。但無人機受限于其單機抗毀性差和覆蓋范圍有限等缺點，需要無人機集群數(shù)據(jù)鏈通信解決。在任務(wù)執(zhí)行期間，無人機集群位置有隨機性、分散性等特征，某些無人機平臺在任務(wù)中會出現(xiàn)遠離集群、獨立執(zhí)行任務(wù)的情況，因此，無人機集群分散機動中通信問題成為無人機集群通信領(lǐng)域的一個研究方向[2]。隨著無人機的種類逐漸豐富，出現(xiàn)了續(xù)航能力長、通信距離遠的無人機機型，可以有效解決以上問題。具有中繼無人機的無人機數(shù)據(jù)鏈網(wǎng)絡(luò)，可以顯著擴展集群執(zhí)行任務(wù)的通信范圍，靈活建立編隊子網(wǎng)，有效控制孤立的無人機單元，實現(xiàn)整個集群態(tài)勢資源共享，增強集群編隊協(xié)同能力[3]。本文綜合考慮，以無人機集群協(xié)作執(zhí)行任務(wù)為背景，構(gòu)建了無人機集群數(shù)據(jù)鏈中繼網(wǎng)絡(luò)，設(shè)計基于文化算法的改進克隆蟻群算法解決無人機數(shù)據(jù)鏈中繼節(jié)點選擇問題。

1 中繼節(jié)點選擇相關(guān)研究

無人機中繼節(jié)點的通信區(qū)域主要取決于中繼節(jié)點飛行高度、通信區(qū)域高度和最大通信距離[4]。假設(shè)最大通信距離為R,中繼節(jié)點飛行高度為H，通信區(qū)域高度為h，則通信最大覆蓋半徑為：

(1)

在實際作戰(zhàn)中，無人機集群節(jié)點間高度差一般在數(shù)十米到數(shù)千米間，而中繼節(jié)點的最大通信距離往往高達幾百千米以上，節(jié)點間的高度差對比與通信最大距離可以忽略不計?？紤]到無人機間的高度差對于信號的通信范圍和集群拓撲結(jié)構(gòu)的影響可以忽略，故為便于建模分析問題，本文將節(jié)點選擇問題從三維空間降維到二維空間進行研究。

1.1 通信覆蓋率

本文將任務(wù)區(qū)域按照網(wǎng)格形式分解，并將每一個網(wǎng)格簡化為點，成為像素點，設(shè)任務(wù)區(qū)域有m×n個像素點，節(jié)點集S通信覆蓋率Rarea(S)為S覆蓋像素點的總和與任務(wù)區(qū)域總像素點的比值公式如下：

(2)

1.2 聚集度

聚集度的衡量標準是節(jié)點之間的平均最短路徑和網(wǎng)絡(luò)中的節(jié)點數(shù)目[5]。聚集度是用于評估在中繼節(jié)點數(shù)量有限和通信距離有限的情況下，如何部署可以既滿足覆蓋和通信的需求，又可以最大限度地提升網(wǎng)絡(luò)抗毀性。在無人機集群中，每個中繼無人機除了對本身通信范圍內(nèi)的無人機進行中繼，同時要考慮為相鄰無人機轉(zhuǎn)發(fā)消息。因此，本文定義中繼無人機的聚集度βi：

(3)

1.3 分布評估函數(shù)

在中繼無人機數(shù)量和覆蓋半徑確定的條件下，基于集群連通性、魯棒性和覆蓋率，在保證集群最佳通信覆蓋的情況下，為增強數(shù)據(jù)鏈網(wǎng)絡(luò)的魯棒性，各中繼無人機的聚集度需要盡量小。3個條件間相互制約，綜合衡量得到數(shù)據(jù)鏈中繼網(wǎng)絡(luò)的分布評估函數(shù)為：

Edis=l1×Rarea(S)-l2×var(βi)

(4)

式中：l1和l2為權(quán)重系數(shù)。

2 CA-CSACA算法設(shè)計

2.1 蟻群算法

假設(shè)螞蟻k由當前節(jié)點i移動到節(jié)點j的移動規(guī)則為:

(5)

式中：α為第k只螞蟻移動中信息素濃度；β為啟發(fā)因子在螞蟻挑選節(jié)點中的重要度；dk為螞蟻k可以下一步選擇的節(jié)點子集；ηij(t)為挑選節(jié)點的啟發(fā)信息；τij(t)為在t時刻路徑(i,j)上的信息素量。

為防止信息素殘留引起啟發(fā)信息作用被削弱，當螞蟻選擇下一步節(jié)點后，要對信息素進行局部更新，更新公式如下：

τi,j(t+Δt)=(1-ρ1)τi,j(t)+Δτi,j(t)

(6)

(7)

(8)

式中：0

當沒有局部更新時，螞蟻將在上一次選擇的最佳路徑的相鄰區(qū)域內(nèi)搜索。

2.2 克隆選擇算法

克隆選擇算法基本操作如下：

(1) 復制操作：將Ai(k)復制qi次，生成qi個抗體，這一操作表示為：

(9)

式中：Ei為qi×1的單位陣。

抗體適應(yīng)度qi為：

qi(k)=g(N，f(Ai(k)))，1≤i≤n

(10)

(11)

式中：Int(·)為取最小整數(shù)的函數(shù)；N(N>n)表示克隆數(shù)目。

由此可見qi與f(Ai(k))成正比例關(guān)系。通過克隆復制操作后，種群變?yōu)閅(k)，形式如下：

Y(k)={Y1(k)，Y2(k)，…，Yn(k)}

(12)

式中：Yi(k)={Ai1(k)，…Aij(k)，…，Aiqi(k)}，且Aij(k)=Ai(k)，j=1，2，…，qi。

(13)

(14)

一般使用概率選擇的方法，進行進化操作。

具體地，?i=1,2,…,n，則：

Bi(k)=max{Zi(k)}=

{zij(k)|max(f(Zij))，j=1，2，…，qi}

(15)

Bi(k)取代Ai(k)成為Ai(k+1)的概率Ps為：

(16)

其中根據(jù)計算種群中各抗體適應(yīng)度值，挑選出適應(yīng)度值最大的抗體作為最優(yōu)抗體。

2.3 文化算法

文化算法模擬人類知識積累的歷程，在普通種群空間的基礎(chǔ)上構(gòu)建有知識積累、進化和傳播的信仰空間，形成雙層進化機制[7]。文化算法主要包括三部分，分別是種群空間、信仰空間與溝通渠道。其中溝通渠道可具體劃分為接受函數(shù)、影響函數(shù)和更新函數(shù)。而信仰空間則主要包括規(guī)范知識、拓撲知識、領(lǐng)域知識等[4]。接受函數(shù)提取每一個代種群中適應(yīng)度高的個體，并送入樣本庫進行演化。

2.4 CA-CSACA算法

蟻群算法求解過程中容易過早得到局部最優(yōu)解并局部收斂?？寺∵x擇算法通過免疫和克隆操作，可以不斷給種群引入新的優(yōu)秀個體，有利于跳出局部收斂，而得到全局最優(yōu)解。2種算法通過文化算法的雙層進化機制有機結(jié)合，建立以克隆選擇算法優(yōu)化的信仰空間和以蟻群算法優(yōu)化的種群空間。經(jīng)克隆選擇算法初始化信仰空間、蟻群算法優(yōu)化種群空間處理后，采用適應(yīng)度函數(shù)評估種群中個體適應(yīng)度優(yōu)劣，通過接收函數(shù)將迭代中產(chǎn)生的最優(yōu)個體保存在信仰空間，信仰空間使用克隆選擇算法定期將保存的優(yōu)良個體通過影響函數(shù)反饋到種群空間，種群空間在更新后的新種群基礎(chǔ)上繼續(xù)進化，重復整個進化過程，直到滿足結(jié)束條件，得到最優(yōu)解。

算法流程描述如下：

步驟1：種群空間初始化，采用蟻群算法進化，設(shè)置基本參數(shù)，如螞蟻數(shù)量、信息素揮發(fā)系數(shù)、迭代次數(shù)等。根據(jù)適應(yīng)度公式評估抗體的優(yōu)劣。

步驟2：信仰空間初始化，采用克隆選擇算法進化，形成抗體的種群，針對抗體種群，分別進行交叉和變異操作，操作數(shù)量占種群空間個體數(shù)量的15%到25%。

步驟3：定義接受函數(shù)，在每輪進化結(jié)束后，信仰空間用種群空間中當前最優(yōu)解替換信仰空間內(nèi)當前最劣解。

步驟4：定義影響函數(shù)，每迭代N次，用信仰空間中適應(yīng)度最優(yōu)的T個個體將種群空間中適應(yīng)度最差的T個個體進行替換。

步驟5：迭代求解：

(1) 種群空間更新。當滿足條件時，運行影響函數(shù)，然后利用蟻群算法對種群空間進行進化。

(2) 信仰空間更新。運行接受函數(shù)，然后利用克隆選擇算法對信仰空間進行進化。

步驟6：更新記錄冊。每次迭代完成后比較當前記錄冊的值和種群空間中的最優(yōu)值，并將兩者中的較優(yōu)值賦給記錄冊。

步驟7：比較終止條件和記錄冊上的值，直至滿足終止條件，輸出解集；否則，轉(zhuǎn)步驟5。

3 仿真分析

仿真過程中，假定任務(wù)區(qū)域600 km×600 km，中繼無人機的覆蓋半徑R=100 km，變異概率pm=0.8，交叉概率pc=0.4，克隆算法迭代次數(shù)500次，蟻群算法中螞蟻數(shù)量為20，最大迭代次數(shù)為500。

驗證無人機聚集度對集群魯棒特性評估的有效性，在試驗區(qū)域內(nèi)部署12個節(jié)點，對比分析2種算法的部署效果。由圖1可以得出，基于文化算法的改進克隆蟻群算法(CA-CSACA)部署的節(jié)點聚集度優(yōu)于克隆蟻群算法(CSACA)。由此證明節(jié)點聚集度可以有效評估無人機集群數(shù)據(jù)鏈網(wǎng)絡(luò)中各個節(jié)點的作用。

圖1 CSACA和CA-CSACA下節(jié)點聚集度

表1為50 次實驗的平均結(jié)果對比?？梢钥闯?，在集群數(shù)據(jù)鏈網(wǎng)絡(luò)中成員較多情況下，算法間覆蓋率的區(qū)別不明顯，但CA-CSACA對比CSACA算法在計算聚集度方差上明顯占有優(yōu)勢。這表示若只對優(yōu)化目標做更改，而不對算法本身的運行機理做調(diào)整，很難明顯提高解空間質(zhì)量。

表1 CSACA和CA-CSACA算法 50次試驗性能對比

算法迭代過程中，適應(yīng)度函數(shù)值迭代情況如圖2所示，其中X軸坐標為迭代次數(shù)。由圖2可知，隨著算法運行，迭代次數(shù)增加，求解空間逐漸收斂，對比CSACA算法，CA-CSACA有更好的尋優(yōu)能力。

4 結(jié)束語

針對無人機集群的數(shù)據(jù)鏈中繼節(jié)點選擇問題，本文提出一種基于改進克隆蟻群算法的中繼節(jié)點選擇算法。本算法在克隆蟻群算法基礎(chǔ)上結(jié)合文化算法的雙層進化機制，明顯提高全局最優(yōu)解的收斂速度。仿真結(jié)果表明，基于文化算法的改進克隆蟻群算法能提高解集搜索速度，更有效解決無人機集群的數(shù)據(jù)鏈中繼節(jié)點選擇問題。

圖2 CSACA和CA-CSACA算法適應(yīng)度函數(shù)值