一种基于蚁群算法的海战场分布式频率分配方法∗

王川 张剑

（武汉数字工程研究所 武汉 430205）

1 引言

在当今的海军编队中各舰船的电磁环境十分复杂。舰船上装载的雷达、电抗、武器系统等装载着各种电磁设备，用频设备的数量、种类、性能差异巨大。海战场环境下的频率资源十分有限，随着电磁设备的不断增多，战场网络的频谱规划会越来越难，各设备的工作频率不可避免地出现了不同程度之间的相互干扰，对作战造成较大的影响甚至导致作战能力的丧失。因此，现代战争［1］中必须保障无线电频谱资源等的合理有效利用，编队中各电磁设备进行合理有效的频谱管理对编队系统正常高效的相互协作起到重要的作用。频谱管理［2］目前主要的研究方向为频率分配，即将有限的频谱资源拆分为不同的频率或频段，将其分配给各用频设备使用，防止其相互干扰，保证各用频设备的通信畅通［3］。

目前常用的频率分配方法［4］有遗传算法、蚁群算法，模拟退火算法、粒子算法等等，这些算法各自有其优点与不足。如遗传算法［5］在全局内随机搜素，但没有充分考虑到个体间的联系，缺乏对个体多样性和群体收敛动态平衡等因素的调整。蚁群算法［6］往往会陷入局部优化，导致收敛时间过长。模拟退火算法［7］能从绝大数局部点中脱离出来，同时具有全局搜索的特性，但其导致了过多的无用迭代和求解效率低下。粒子群算法［8］关键在于研究粒子的个体性与群体性之间的关系，其概念简单直观，收敛速度快。

本文通过分析海战场用频设备具体特点，将问题进行分类转化，采用分布式方法进行处理，当系统用频设备数量发生变化时，可快速做出调整，最终通过仿真试验验证该方法的有效性。

2 频率分配问题建模

2.1 频率分配问题描述

设系统中一段频率资源F可供使用，同时系统中有N个用频设备，设备从1～N进行编号，其中第k个用频设备频率使用范围为(fkL，fkH)，带宽Δfk。对于任意一对编号为i与 j的用频设备1≤i≤j≤N ，设备 i与设备 j分配的频率为 fi与fj，若这两个设备在此工作频率下收发相互无干扰，则称设备i与 j可兼容工作。频率分配问题即使对于用频设备k，通过一定的分配算法对其分配一段频率资源 ak，使其满足 fkL≤ak≤fkH，ak≥Δfk且ak⊂F，使得相互之间冲突的装备数量最少，得到最终的分配结果 f={a1，a2，…，aN}⊂ F 。

实际海战场环境下电磁环境十分复杂，随时都可能发生可用频谱资源发生变化、加入新的用频设备或有些用频设备不在使用，这就要求当战场环境发生变化时，系统能快速进行重新优化计算，即当频谱资源从F变化为F′，用频设备发生数量变化时，算法能快速得到新的分配结果f′=⊂ F′。

即对于分配结果，有以下要求：

1）每个装备都占有一定频率，分配的频率必须满足该装备基本工作；

2）每个装备必须分配一定频率资源，即使分配结果导致部分装备使用发生冲突；

3）分配的最终目的是冲突装备数量组最少；

4）整个频率资源部分失效，或某些设备停止使用，或新增一些设备，整个系统能够快速动态作出调整。

2.2 分布式模型建立

对于海战场编队环境下用频设备一般有雷达、卫星导航、无线通信［8］等，它们主要分布在L、S、C、X、Ku、K、ka七个频段［9］，不同频段的设备占用频率有巨大的差别，故需要对其进行分类，对工作在不同频段采用不同的分配标准，这样可以充分利用频率资源。对每一类分别进行频率分配，整个问题最终的分配结果即为每一类子问题分配结果的合集。将N个设备分为M组，将可用频率亦划分为M 组，第 m 组的可用频率为 fm1，fm2，…，fmx，其中，此时m组第k个频设备的用频需求可表示为：频率使用范围 (fmkL，fmkH)，带宽 Δfmk，从而对每组用频设备分别采用分配算法进行频率分配。

3 解决频率分配问题的蚁群算法

3.1 蚁群算法介绍

蚁群算法的特点是模拟自然界中蚂蚁觅食的群体行为。首先生成具有一定数量蚂蚁的蚁群，让每一只蚂蚁代表一种频率分配方案［10］，每只人工蚁从问题的初始状态出发，根据“信息素”浓度来选择下一个装备的使用频率，直到建立起一个解，每只蚂蚁根据所找到的解的好坏程度在所经过的状态上释放与解的质量成正比例的“信息素”［11］。之后，下一只蚂蚁又开始新的求解过程，直到寻找到满意的频率分配方案。

3.2 基于蚁群算法的频率分配方法

设第m个子系统中有l只蚂蚁，每只蚂蚁依次为用频设备1到设备选择一个频率，这样每只蚂蚁就构成了一组分配方案。用(t)表示t时刻蚂蚁k(1≤k≤l)在用频设备i选择频率 j的概率：

反映了蚂蚁选择 j频率的期望程度，其中Fk表示蚂蚁k下一步选择的频率，α为信息启发因子，表示轨迹的相对重要性，反映了蚂蚁在运动过程中所积累的信息在蚂蚁运动时所起到的作用，β表示期望启发因子，表示能见度的相对重要性，反映了蚂蚁在运动过程中启发信息在蚂蚁选择路径中的受重视程度，ηik(t)为启发函数。τij(t)表示t时刻设备i在编号为 j的频率上的信息量，每次蚂蚁选择频率后都要对其进行局部更新：

其中 Δτij(t)=(t)。是蚂蚁k产生的信息增量，Δτij(t)是整个蚁群产生的信息增量。τij(t)是本次蚂蚁迭代选择得到的信息增量，τij(t+1)是下一只蚂蚁迭代的信息初始量。

式中Lk是蚂蚁k搜索到的频组中总的干扰数量，常数P影响Lk对信息量增量的贡献。

4 仿真实验

本次实验在CPU为Inter Core i5-4590，内存为8g的计算机上进行，采用Matlab 2012b进行仿真实验。

设定海战场区域有30个用频设备正在开机工作，需要进行频率分配，这些设备频段分布在L、S、C三个频段，分配的频段范围亦为这三个频段，且全部频率资源均可参与分配。设定，参数设置：τ0=0.5，γ=0.1，ρ=0.1，P=1，α=4，图1为不同蚁群规模下频率分配结果。

图1 干扰数目仿真图

该结果显示，两种分配方法在经过一定迭代后能够快速收敛，用频设备冲突数量显著降低，但当到达一定程度后就区域平稳，并且都无法达到无干扰情况，并且两种算法的分配结果比较相似，改进算法并没有体现出很大的优势。

对于海战场环境来说，算法的时效性同样十分重要，图2给出了当蚁群数目一定时，随着用频设备数量的增加，其计算时间变化的相对统计图，其仿真结果显示当参与分配的用频设备不段增多时，改进算法相对于原算法，速率有较大的提升。

图2 相对搜索速度比较图

5 结语

本文通过分析海战场编队环境下用频设备特性，模拟了海战场复杂环境下设备的使用场景。该方法表明改进后算法在计算速度上有明显的提升，能在战场环境发生变化时能迅速做出调整，迅速完成新环境下频率指配的任务。然而由于自身能力的不足与时间的限制，对蚁群算法中的一些重要参数设定没有深入的研究，导致对算法最终的分配结果干扰数量并没有明显的减少，分配结果与未改进算法相比提升比较有限。因此今后仍应该继续深入研究。

［1］王强.美军海战场频率规划分析［J］.舰船电子对抗，2007，30（6）：26-32.

WANG Qiang，Frequency Planning Analysis for American Military Sea Battlefield［J］.Shipboard Electronic Counter⁃measure.2007，30（6）：26-32.

［2］吴小强.未来海战场电磁频谱管理［J］.舰船电子对抗，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］古邦伦.电磁频谱管理中的频率分配技术研究［D］.长沙：国防科学技术大学，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］王强.频率管理关键技术-频率指配算法研究［M］.北京：北京交通大学，2009：17-23.

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

［5］王云璐，戴伏生，李怀远.遗传粒子群算法在频率分配中的应用［J］.信息技术，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］段海滨.蚁群算法原理及其应用［M］.北京：科学出版社，2005：24-39.

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

［7］孟一冉.战场通信网频率分配专家系统研究［M］.西安：西安工业大学，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］李立芳，刘维国，高昂.舰艇通信电磁干扰评估及频率支配研究［J］.舰船电子对抗，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］李东海，王勇军.基于粒子群优化的蚁群算法在战场电磁频率分配中的应用［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］刘田间，高小玲.基于蚁群算法的无线通信频率最优指配策略［J］.信息技术，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.