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

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

0 引 言

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

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

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

(1)

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

1.1 通信覆蓋率

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

(2)

1.2 聚集度

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

(3)

1.3 分布評(píng)估函數(shù)

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

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

(4)

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

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

2.1 蟻群算法

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

(5)

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

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

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

(6)

(7)

(8)

式中：0

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

2.2 克隆選擇算法

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

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

(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ù)目。

由此可見(jiàn)qi與f(Ai(k))成正比例關(guān)系。通過(guò)克隆復(fù)制操作后，種群變?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)

一般使用概率選擇的方法，進(jìn)行進(jìn)化操作。

具體地，?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ù)計(jì)算種群中各抗體適應(yīng)度值，挑選出適應(yīng)度值最大的抗體作為最優(yōu)抗體。

2.3 文化算法

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

2.4 CA-CSACA算法

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

算法流程描述如下：

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

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

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

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

步驟5：迭代求解：

(1) 種群空間更新。當(dāng)滿足條件時(shí)，運(yùn)行影響函數(shù)，然后利用蟻群算法對(duì)種群空間進(jìn)行進(jìn)化。

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

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

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

3 仿真分析

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

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

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

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

表1 CSACA和CA-CSACA算法 50次試驗(yàn)性能對(duì)比

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

4 結(jié)束語(yǔ)

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

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