一種基于蟻群算法的海戰(zhàn)場(chǎng)分布式頻率分配方法?

王川 張劍

（武漢數(shù)字工程研究所 武漢 430205）

1 引言

在當(dāng)今的海軍編隊(duì)中各艦船的電磁環(huán)境十分復(fù)雜。艦船上裝載的雷達(dá)、電抗、武器系統(tǒng)等裝載著各種電磁設(shè)備，用頻設(shè)備的數(shù)量、種類、性能差異巨大。海戰(zhàn)場(chǎng)環(huán)境下的頻率資源十分有限，隨著電磁設(shè)備的不斷增多，戰(zhàn)場(chǎng)網(wǎng)絡(luò)的頻譜規(guī)劃會(huì)越來(lái)越難，各設(shè)備的工作頻率不可避免地出現(xiàn)了不同程度之間的相互干擾，對(duì)作戰(zhàn)造成較大的影響甚至導(dǎo)致作戰(zhàn)能力的喪失。因此，現(xiàn)代戰(zhàn)爭(zhēng)［1］中必須保障無(wú)線電頻譜資源等的合理有效利用，編隊(duì)中各電磁設(shè)備進(jìn)行合理有效的頻譜管理對(duì)編隊(duì)系統(tǒng)正常高效的相互協(xié)作起到重要的作用。頻譜管理［2］目前主要的研究方向?yàn)轭l率分配，即將有限的頻譜資源拆分為不同的頻率或頻段，將其分配給各用頻設(shè)備使用，防止其相互干擾，保證各用頻設(shè)備的通信暢通［3］。

目前常用的頻率分配方法［4］有遺傳算法、蟻群算法，模擬退火算法、粒子算法等等，這些算法各自有其優(yōu)點(diǎn)與不足。如遺傳算法［5］在全局內(nèi)隨機(jī)搜素，但沒(méi)有充分考慮到個(gè)體間的聯(lián)系，缺乏對(duì)個(gè)體多樣性和群體收斂動(dòng)態(tài)平衡等因素的調(diào)整。蟻群算法［6］往往會(huì)陷入局部?jī)?yōu)化，導(dǎo)致收斂時(shí)間過(guò)長(zhǎng)。模擬退火算法［7］能從絕大數(shù)局部點(diǎn)中脫離出來(lái)，同時(shí)具有全局搜索的特性，但其導(dǎo)致了過(guò)多的無(wú)用迭代和求解效率低下。粒子群算法［8］關(guān)鍵在于研究粒子的個(gè)體性與群體性之間的關(guān)系，其概念簡(jiǎn)單直觀，收斂速度快。

本文通過(guò)分析海戰(zhàn)場(chǎng)用頻設(shè)備具體特點(diǎn)，將問(wèn)題進(jìn)行分類轉(zhuǎn)化，采用分布式方法進(jìn)行處理，當(dāng)系統(tǒng)用頻設(shè)備數(shù)量發(fā)生變化時(shí)，可快速做出調(diào)整，最終通過(guò)仿真試驗(yàn)驗(yàn)證該方法的有效性。

2 頻率分配問(wèn)題建模

2.1 頻率分配問(wèn)題描述

設(shè)系統(tǒng)中一段頻率資源F可供使用，同時(shí)系統(tǒng)中有N個(gè)用頻設(shè)備，設(shè)備從1～N進(jìn)行編號(hào)，其中第k個(gè)用頻設(shè)備頻率使用范圍為(fkL，fkH)，帶寬Δfk。對(duì)于任意一對(duì)編號(hào)為i與 j的用頻設(shè)備1≤i≤j≤N ，設(shè)備 i與設(shè)備 j分配的頻率為 fi與fj，若這兩個(gè)設(shè)備在此工作頻率下收發(fā)相互無(wú)干擾，則稱設(shè)備i與 j可兼容工作。頻率分配問(wèn)題即使對(duì)于用頻設(shè)備k，通過(guò)一定的分配算法對(duì)其分配一段頻率資源 ak，使其滿足 fkL≤ak≤fkH，ak≥Δfk且ak?F，使得相互之間沖突的裝備數(shù)量最少，得到最終的分配結(jié)果 f={a1，a2，…，aN}? F 。

實(shí)際海戰(zhàn)場(chǎng)環(huán)境下電磁環(huán)境十分復(fù)雜，隨時(shí)都可能發(fā)生可用頻譜資源發(fā)生變化、加入新的用頻設(shè)備或有些用頻設(shè)備不在使用，這就要求當(dāng)戰(zhàn)場(chǎng)環(huán)境發(fā)生變化時(shí)，系統(tǒng)能快速進(jìn)行重新優(yōu)化計(jì)算，即當(dāng)頻譜資源從F變化為F′，用頻設(shè)備發(fā)生數(shù)量變化時(shí)，算法能快速得到新的分配結(jié)果f′=? F′。

即對(duì)于分配結(jié)果，有以下要求：

1）每個(gè)裝備都占有一定頻率，分配的頻率必須滿足該裝備基本工作；

2）每個(gè)裝備必須分配一定頻率資源，即使分配結(jié)果導(dǎo)致部分裝備使用發(fā)生沖突；

3）分配的最終目的是沖突裝備數(shù)量組最少；

4）整個(gè)頻率資源部分失效，或某些設(shè)備停止使用，或新增一些設(shè)備，整個(gè)系統(tǒng)能夠快速動(dòng)態(tài)作出調(diào)整。

2.2 分布式模型建立

對(duì)于海戰(zhàn)場(chǎng)編隊(duì)環(huán)境下用頻設(shè)備一般有雷達(dá)、衛(wèi)星導(dǎo)航、無(wú)線通信［8］等，它們主要分布在L、S、C、X、Ku、K、ka七個(gè)頻段［9］，不同頻段的設(shè)備占用頻率有巨大的差別，故需要對(duì)其進(jìn)行分類，對(duì)工作在不同頻段采用不同的分配標(biāo)準(zhǔn)，這樣可以充分利用頻率資源。對(duì)每一類分別進(jìn)行頻率分配，整個(gè)問(wèn)題最終的分配結(jié)果即為每一類子問(wèn)題分配結(jié)果的合集。將N個(gè)設(shè)備分為M組，將可用頻率亦劃分為M 組，第 m 組的可用頻率為 fm1，fm2，…，fmx，其中，此時(shí)m組第k個(gè)頻設(shè)備的用頻需求可表示為：頻率使用范圍 (fmkL，fmkH)，帶寬 Δfmk，從而對(duì)每組用頻設(shè)備分別采用分配算法進(jìn)行頻率分配。

3 解決頻率分配問(wèn)題的蟻群算法

3.1 蟻群算法介紹

蟻群算法的特點(diǎn)是模擬自然界中螞蟻覓食的群體行為。首先生成具有一定數(shù)量螞蟻的蟻群，讓每一只螞蟻代表一種頻率分配方案［10］，每只人工蟻從問(wèn)題的初始狀態(tài)出發(fā)，根據(jù)“信息素”濃度來(lái)選擇下一個(gè)裝備的使用頻率，直到建立起一個(gè)解，每只螞蟻根據(jù)所找到的解的好壞程度在所經(jīng)過(guò)的狀態(tài)上釋放與解的質(zhì)量成正比例的“信息素”［11］。之后，下一只螞蟻又開始新的求解過(guò)程，直到尋找到滿意的頻率分配方案。

3.2 基于蟻群算法的頻率分配方法

設(shè)第m個(gè)子系統(tǒng)中有l(wèi)只螞蟻，每只螞蟻依次為用頻設(shè)備1到設(shè)備選擇一個(gè)頻率，這樣每只螞蟻就構(gòu)成了一組分配方案。用(t)表示t時(shí)刻螞蟻k(1≤k≤l)在用頻設(shè)備i選擇頻率 j的概率：

反映了螞蟻選擇 j頻率的期望程度，其中Fk表示螞蟻k下一步選擇的頻率，α為信息啟發(fā)因子，表示軌跡的相對(duì)重要性，反映了螞蟻在運(yùn)動(dòng)過(guò)程中所積累的信息在螞蟻運(yùn)動(dòng)時(shí)所起到的作用，β表示期望啟發(fā)因子，表示能見(jiàn)度的相對(duì)重要性，反映了螞蟻在運(yùn)動(dòng)過(guò)程中啟發(fā)信息在螞蟻選擇路徑中的受重視程度，ηik(t)為啟發(fā)函數(shù)。τij(t)表示t時(shí)刻設(shè)備i在編號(hào)為 j的頻率上的信息量，每次螞蟻選擇頻率后都要對(duì)其進(jìn)行局部更新：

其中 Δτij(t)=(t)。是螞蟻k產(chǎn)生的信息增量，Δτij(t)是整個(gè)蟻群產(chǎn)生的信息增量。τij(t)是本次螞蟻迭代選擇得到的信息增量，τij(t+1)是下一只螞蟻迭代的信息初始量。

式中Lk是螞蟻k搜索到的頻組中總的干擾數(shù)量，常數(shù)P影響Lk對(duì)信息量增量的貢獻(xiàn)。

4 仿真實(shí)驗(yàn)

本次實(shí)驗(yàn)在CPU為Inter Core i5-4590，內(nèi)存為8g的計(jì)算機(jī)上進(jìn)行，采用Matlab 2012b進(jìn)行仿真實(shí)驗(yàn)。

設(shè)定海戰(zhàn)場(chǎng)區(qū)域有30個(gè)用頻設(shè)備正在開機(jī)工作，需要進(jìn)行頻率分配，這些設(shè)備頻段分布在L、S、C三個(gè)頻段，分配的頻段范圍亦為這三個(gè)頻段，且全部頻率資源均可參與分配。設(shè)定，參數(shù)設(shè)置：τ0=0.5，γ=0.1，ρ=0.1，P=1，α=4，圖1為不同蟻群規(guī)模下頻率分配結(jié)果。

圖1 干擾數(shù)目仿真圖

該結(jié)果顯示，兩種分配方法在經(jīng)過(guò)一定迭代后能夠快速收斂，用頻設(shè)備沖突數(shù)量顯著降低，但當(dāng)?shù)竭_(dá)一定程度后就區(qū)域平穩(wěn)，并且都無(wú)法達(dá)到無(wú)干擾情況，并且兩種算法的分配結(jié)果比較相似，改進(jìn)算法并沒(méi)有體現(xiàn)出很大的優(yōu)勢(shì)。

對(duì)于海戰(zhàn)場(chǎng)環(huán)境來(lái)說(shuō)，算法的時(shí)效性同樣十分重要，圖2給出了當(dāng)蟻群數(shù)目一定時(shí)，隨著用頻設(shè)備數(shù)量的增加，其計(jì)算時(shí)間變化的相對(duì)統(tǒng)計(jì)圖，其仿真結(jié)果顯示當(dāng)參與分配的用頻設(shè)備不段增多時(shí)，改進(jìn)算法相對(duì)于原算法，速率有較大的提升。

圖2 相對(duì)搜索速度比較圖

5 結(jié)語(yǔ)

本文通過(guò)分析海戰(zhàn)場(chǎng)編隊(duì)環(huán)境下用頻設(shè)備特性，模擬了海戰(zhàn)場(chǎng)復(fù)雜環(huán)境下設(shè)備的使用場(chǎng)景。該方法表明改進(jìn)后算法在計(jì)算速度上有明顯的提升，能在戰(zhàn)場(chǎng)環(huán)境發(fā)生變化時(shí)能迅速做出調(diào)整，迅速完成新環(huán)境下頻率指配的任務(wù)。然而由于自身能力的不足與時(shí)間的限制，對(duì)蟻群算法中的一些重要參數(shù)設(shè)定沒(méi)有深入的研究，導(dǎo)致對(duì)算法最終的分配結(jié)果干擾數(shù)量并沒(méi)有明顯的減少，分配結(jié)果與未改進(jìn)算法相比提升比較有限。因此今后仍應(yīng)該繼續(xù)深入研究。

［1］王強(qiáng).美軍海戰(zhàn)場(chǎng)頻率規(guī)劃分析［J］.艦船電子對(duì)抗，2007，30（6）：26-32.

WANG Qiang，F(xiàn)requency Planning Analysis for American Military Sea Battlefield［J］.Shipboard Electronic Counter?measure.2007，30（6）：26-32.

［2］吳小強(qiáng).未來(lái)海戰(zhàn)場(chǎng)電磁頻譜管理［J］.艦船電子對(duì)抗，2008，31（3）：10-12，16.

WU Xiaoqiang.Spectrum Management for future Sea Bat?tlefield［J］.Shipboard Electronic Countermeasure，2008，31（3）：10-12，16.

［3］古邦倫.電磁頻譜管理中的頻率分配技術(shù)研究［D］.長(zhǎng)沙：國(guó)防科學(xué)技術(shù)大學(xué)，2006：7-11.

GU Banglun.The Research of Freqency Assignment in Frequency Spectrum Management System［D］.Changsha：National University of Defense Technology，2006：7-11.

［4］王強(qiáng).頻率管理關(guān)鍵技術(shù)-頻率指配算法研究［M］.北京：北京交通大學(xué)，2009：17-23.

WANG Qiang.Key Technique of Spectrum Manage?ment-Research on FrequencyAssignmentAlgorithms［M］.Beijing：Beijing Jiaotong University，2009：17-23.

［5］王云璐，戴伏生，李懷遠(yuǎn).遺傳粒子群算法在頻率分配中的應(yīng)用［J］.信息技術(shù)，2016：15-32，38-45.

WANG Yunlu，DAI Fusheng，LI Huaiyuan.Application of gentic and particle swarm algorithm in frequency assign?ment［J］.Information Technology，2016：15-32，38-45.

［6］段海濱.蟻群算法原理及其應(yīng)用［M］.北京：科學(xué)出版社，2005：24-39.

DUAN Haibing.Ant Colony Algorithms：Theory and Appli?cations［M］.Beijing：Science press，2005：24-39.

［7］孟一冉.戰(zhàn)場(chǎng)通信網(wǎng)頻率分配專家系統(tǒng)研究［M］.西安：西安工業(yè)大學(xué)，2012：32-37.

MENG Yiran.Connunication Network Frequency Planning of Expert System in Battlefield［M］.Xi'an：Xi'an Techno?logical University，2012：32-37.

［8］Chert JK，de Veciana G，Rappaport TS.Improved mea?surement based frequency allocation algorithms for wire?less net-works［C］//IEEE GLOBECOM 2007，2007.

［9］李立芳，劉維國(guó)，高昂.艦艇通信電磁干擾評(píng)估及頻率支配研究［J］.艦船電子對(duì)抗，2007，30（1）：46-48.

LI Lifang，LIU Guowei，GAO Ang.Evaluation of Communi?cation Electromagnetic Interference and Research in Fre?quency Assignation in Warship［J］.Shipboard Electronic Countermeasure，2007，30（1）：46-48.

［10］李東海，王勇軍.基于粒子群優(yōu)化的蟻群算法在戰(zhàn)場(chǎng)電磁頻率分配中的應(yīng)用［J］.指揮控制與仿真，2016，38（2）：49-50.

LI Donghai，WANG Yongjun.Application of Ant Colony Algorithm Based on Particle Swarm in Frequency Assign?ment on Battlefield［J］.Command Control&Simulation，2016，38（2）：49-50.

［11］劉田間，高小玲.基于蟻群算法的無(wú)線通信頻率最優(yōu)指配策略［J］.信息技術(shù)，2016（4）：146-147.

LIU Tianjian，GAO Xiaoling.Optimum base frequency assignment of wireless communication network based on ant colony algorithm［J］.Information Technology，2016（4）：146-147.