基于蜜源优化策略的频率分配方法*

吴 麒

(中国西南电子技术研究所，成都 610036)



基于蜜源优化策略的频率分配方法*

吴 麒**

(中国西南电子技术研究所，成都 610036)

为解决频率分配问题，提出了一种基于蜜源优化的频率分配方法。首先提出了评估干扰程度的计算方法，对传统人工蜂群算法的引领蜂搜索行为进行改进，并重新设计跟随蜂搜索行为，增加选择性变异操作，以达到增加蜜源多样性以及降低陷入局部最优解可能性的目的。仿真结果表明，所提算法在搜索效率和稳定性上具有明显优势，能够在有效时间内找到满足频率距离约束的频率分配方案。

频谱管理；频率指配；人工蜂群算法；蜜源交叉；选择性变异

1 引 言

现代战争中参与作战的各种电子设备越来越多，而这些设备也将面临着越来越复杂的战场电磁环境，因此加强电磁频谱管控在现代战争中至关重要。频谱管理的目标是从频域、时域、空域和能域上实现战场上所有设备都可兼容工作。合理高效的频率分配可以减少设备之间的相互干扰，是确保电磁频谱管控顺利实施的重要手段之一。因此，如何采用更加高效准确的方式来进行频率分配是当今频谱管理的一个重要研究课题。

频率分配问题本质上是个约束条件下的组合优化问题。作为解决最优化问题的有效工具，遗传算法[1-2]、模拟退火算法[3]、粒子群算法[4]已经被成功应用于频率分配。然而，上述算法在寻优过程中存在收敛时间过长以及极易陷入局部最优的缺点。有研究[5-6]结果表明，与上述算法相比，人工蜂群算法[7](Artificial Bee Colony Algorithm，ABC)不仅更擅长于全局搜索，而且其收敛性能更加优异。已有研究[8-9]利用改进蜂群算法对信道分配问题进行了研究，但其蜜源设计并没有很好地反映装备可用频率的特征，且其简单采用0或者1对设备间的干扰影响进行表示也不能准确量化频率以及距离对干扰程度的影响。

针对频率分配问题的特点以及现有研究的缺陷，本文对频率分配问题准确进行了建模和描述，然后提出了基于蜜源优化策略的人工蜂群算法(Artificial Bee Colony Algorithm based on Honey Source Optimization Strategy,ABCAHSOS)。该算法对引领蜂搜索机制进行了改进，以适应频率分配问题的特点，并设计了准确评估干扰程度影响的计算方法，然后利用交叉和选择性变异操作对蜜源进行优化，达到提高搜索效率的目的。仿真结果表明，该算法在迭代效率、时间效率以及搜索稳定性方面比传统人工蜂群算法更优，并能在有效时间内找到满足频率距离约束的频率分配方案。

2 问题描述

一般在解决频率分配时，需要考虑以下3类电磁兼容问题：同信道干扰影响、邻信道干扰影响、指定频率距离下的干扰影响[10-11]。同信道频率距离约束问题是指如果要保证信道间隔为0的两个无线设备同时兼容工作，那么其距离必须大于d0；邻信道频率距离约束问题是指如果要保证信道间隔为1的两个无线设备同时兼容工作，那么其距离必须大于d1；频率距离约束问题是指如果要保证信道间隔小于某些特定值st(st>1)的两个无线设备同时兼容工作，那么其距离必须大于dt(dt

假设存在n个无线设备，表示为E=(e1,e2,…,en)，ei表示潜在干扰源，ej表示接收机,dij表示设备i和j之间的距离，其中1≤i≤n，1≤j≤n，i≠j，当前可用信道资源表示为F=(f1,f2,…,fm)，分配给设备ei和ej的信道分别表示为fl和fk，其中1≤l≤m，1≤k≤m，且m≥n，那么分配信道l的干扰源ei对分配信道k的接收机ej的干扰余量表示为

I(i,l,j,k)=Pi+Gi+Gj-Lb(dij)+R(Δflk)-Sj。

(1)

式中：Pi表示潜在干扰源的发射功率(dB)；Gi表示在接收机方向的天线增益(dBi)；Gj表示接收机在干扰源方向上的天线增益(dBi)；Lb(dij)表示设备ei与ej之间距离间隔为dij时的传播损耗值(dB),dij表示设备ei与ej之间的距离(km)；Δflk表示设备ei与ej之间频率差值，Δflk=fl-fk；Sj表示设备ej的接收灵敏度值；

(2)

式中：P(fl)表示干扰源ei在分配信道fl时，其等效中频的功率谱密度；H(fk)表示接收机ej在分配频率fk时的频率响应。

一般而言，我们更关注设备的用频效能，即设备间的干扰程度，故应该使用设备间干扰程度而不是干扰余量来评估频率分配方案的好坏程度。此处，采用5级设定来对发射设备ei与接收设备ej之间干扰程度E(i,l,j,k)进行描述：

(3)

式中：E0、E1、E2、E3表示每级干扰所对应的阈值，E=0表示不存在干扰，E=1表示轻微干扰，E=10表示普通干扰，E=100表示较严重干扰，E=1 000表示严重干扰。对于阈值的具体取值，我们一般根据工程经验或者外场试验来进行确定。

频率分配的目标就是在一定的距离约束下，对n个无线设备(e1,e2,…,en)赋予一组信道，使得相互间的干扰影响最小化。形式化描述方法如下：

(4)

式中：E(i,k,j,l)由公式(3)根据无线设备ei和ej之间的频率距离约束计算得知，且当信道fk分配给设备ei时，a(i,k)的值取为1，否则其值取为0；a(j,l)的取值方式与a(i,k)相同。在公式(3)中，当无线设备ei和ej同为发射机或接收机时，设备间不会互相影响，那么直接设定两者间的干扰影响E(i,k,j,l)为0。对于频率分配问题而言，最佳频率分配方案的干扰影响程度E应等于0。

3 基于蜜源优化的频率分配方法

3.1 传统人工蜂群算法

传统人工蜂群算法[12]是一种模拟蜜蜂群通过协作行为寻找蜜源的过程来实现搜寻最优解的算法。该算法主要由引领蜂、跟随蜂、侦察蜂等3个基本角色组成。其基本原理如下：初始时刻，随机生成一定数量蜜源，而种群由与蜜源数量相等的引领蜂和跟随蜂组成。引领蜂在蜜源周边进行随机搜索并根据贪婪原则对优秀蜜源进行选择。待引领蜂回到蜂巢后，跟随蜂将根据引领蜂的跳舞行为获取蜜源信息，并通过在优秀食物源的周边进行领域搜索，获取优秀食物源。如果跟随蜂搜寻的新蜜源比之前引领蜂寻找的蜜源更好，那么旧蜜源将被新蜜源替代，同时跟随蜂将取代引领蜂；反之，则保持不变。当某个蜜源的优秀程度在指定次数内未被更新，那么该蜜源将被放弃，且相应的引领蜂将转变为侦察蜂，并开始随机搜寻新蜜源，待找到新蜜源后，该侦察蜂将转变为引领蜂，因此充当临时角色的侦察蜂的数量始终为1。整个算法的运行流程如图1所示。

图1 人工蜂群算法的基本流程Fig.1 The basic flow of artificial bee colony algorithm

3.2 算法设计

针对传统人工蜂群算法搜索机制简单、搜索易陷入局部最优解且其引领蜂行为不适应战场频率分配求解的问题，采用蜜源交叉和选择性变异机制实现蜜源优化，从而达到对传统人工蜂群算法进行改进的目的。基于蜜源优化策略的人工蜂群算法的流程与传统人工蜂群算法基本保持一致，仅在侦察蜂执行搜索后增加选择性变异操作。

3.2.1 编码以及初始化

3.2.2 蜜源质量评估

在评估一个蜜源(分配方案)质量时，需要根据发射机、接收机属性对编码进行解码操作，并计算蜜源中发射机与接收机两两之间的干扰程度，从而获取整个蜜源的干扰程度，即整个频率分配方案的干扰程度。

根据一般人工蜂群算法设定，用于某个蜜源质量评估的适应函数如下：

(5)

式中：E(Xi)表示蜜源Xi的优秀程度，可通过公式(3)对Xi中的两两设备进行适应度值计算得知。某个蜜源的适应度值越大，则该频率分配方案的干扰程度越小，即该蜜源的质量也就越优秀。

3.3.3 引领蜂行为

(6)

式中：q为整数，在[1,M]范围随机生成，且q≠i；jrand为整数，在[1,N]范围随机生成；rij为[-1,1]范围内的随机数。

(7)

3.3.4 跟随蜂行为

本文采用与普通人工蜂群算法同样的轮盘赌策略选择蜜源，但对跟随蜂搜索行为进行重新设计，通过蜜源交叉操作加强蜜源区域的搜索能力。此外，在进行选择操作之前，利用上代选择性变异蜜源对本代中的最差蜜源进行替换操作。

3.3.5 侦察蜂行为

假设存在引领蜂搜寻蜜源的优秀程度在l次循环后仍然没有更新，则可以认为该蜜源已经陷入局部最优，应该被放弃。此时，该引领蜂将转变角色为侦察蜂，并随机生成新蜜源，侦察蜂也将随之变为引领蜂。

3.3.6 选择性变异

对引领蜂对应的蜜源进行适应度评估，从中挑选适应度值最高的优秀蜜源并进行拷贝操作得到h。然后，执行以下搜索行为：

Step 1 利用公式(1)选出蜜源h中对其他设备干扰影响最大的设备d。

Step 2 从可用频率资源FN中随机选择一个信道分配给设备d，得到新蜜源h′。

Step 3 利用公式(4)评估新蜜源h′的优秀程度，如果新蜜源h′的优秀程度大于拷贝蜜源h，则执行替换操作，并结束选择性变异操作；否则，进入下一步。

Step 4 对Step 2是否执行10次以上进行判断，如果是，则不做任何操作并结束选择性变异操作；否则，返回Step 2。

3.3.7 终止条件

对目前已经搜索到的全局最优蜜源进行记录，并对该蜜源的优秀程度是否满足结束条件进行判断。如果满足，则结束循环并输出结果；否则,继续执行引领蜂、跟随蜂、侦察蜂、选择性搜索行为，直到到达最大迭代次数tm。

4 仿真实验

4.1 仿真场景与参数设置

测试时，设当前可用频率资源带宽为5 MHz，其中最小频率间隔为25 kHz。地面站点数量为100个，随机分布在300 km×300 km的区域内，且每个地面站点仅有一部无线设备，功率值在40～60 W之间随机选择。图2为100个设备位置随机分布图。

图2 设备位置分布Fig.2 The position of equipment

算法采用C++编码实现，开发环境为Microsoft Visual Studio 2010，平台环境为Windows XP Professional SP 3操作系统，Intel CoreTM2 Quad CPUQ8400 @2.66 GHz的CPU，内存为2 GB。

本文算法(ABCAHSOS)的参数为，蜜源数量M=30，迭代最大次数tm=500，侦察蜂转变为引领蜂的限制条件l=10，蜜源交叉概率Pc=0.2；对比测试算法为传统人工蜂群算法(ABC)，除不使用交叉概率外，其余参数与本文算法(ABCAHSOS)相同。为了测试方便，上述的参数主要根据已有研究成果进行设置。在实际应用过程中，可以针对蜜源数量M、限制条件l、交叉概率Pc不同取值对算法性能影响效果进行研究，并根据实际问题的规模、应用限制等进行参数最优设置，对于参数优化问题，将留到后续工作中进行。

在进行搜索稳定性以及时间消耗测试时，除无线设备位置、属性等参数随机设置外，其余算法参数设置与上述条件相同，以排除实验随机性对结果的影响。

4.2 实验结果

图3描述了在上述仿真场景下，100个设备的当前最优分配方案干扰程度值与迭代次数的关系。从图中可以看出，利用ABC算法开始进行频率分配时，当前最优方案干扰程度值随着迭代次数的增加快速下降。在迭代次数为82时，当前干扰程度值已经从最高7 150下降到241。此后，当前干扰程度值随着迭代次数的增加缓慢下降，直到迭代次数为207时，该值等于0，此时算法取得最优频率分配方案。对于ABCAHSOS算法而言，其当前干扰程度值在整个运行过程中都随着迭代次数的增加快速下降。当迭代次数为19时，当前干扰程度值已经从最高7 150快速下降到50；当迭代次数为31时，当前干扰程度值等于0，此时算法取得最优频率分配方案。从以上对比可以看出，ABCAHSOS比ABC算法有更高的迭代效率。

图3 干扰程度演化对比Fig.3 The evolutionary contrast of interference degree between two algorithms

为了对搜索最优方案的迭代次数稳定性以及时间效率进行分析，利用同样的参数设置重复实验100次，并对搜索最优方案的迭代次数和消耗时间进行记录。图4描述了在100次测试中两种算法搜索最优方案的收敛性对比情况。从图中可以看出，ABC算法找到最优分配方案的最小迭代次数为121，最大迭代次数为501，平均迭代次数为280.04，标准差为80.77；ABCAHSOS算法找到最优分配方案的最小迭代次数为31，最大迭代次数为65，平均迭代次数为47.49，标准差为7.97。

从以上数据可以看出，ABCAHSOS算法的平均迭代次数远远少于ABC算法，且标准差也远远低于ABC算法。综上所述，与ABC算法相比，ABCAHSOS算法在解决频率分配问题时不仅迭代效率更高，而且其搜索过程稳定性更好。

图4 算法收敛性对比Fig.4 The contrast of astringency between two algorithms

图5描述了在100次测试中两种算法搜索最优方案所消耗时间的对比情况。从图中可以看出，传统人工蜂群算法(ABC)找到最优分配方案的最短时间为13 s，最大时间为45 s，平均消耗时间为24.91 s，标准差为7.22；ABCAHSOS找到最优分配方案的最短时间为6 s，最大时间为14 s，平均消耗时间为10.39 s，标准差为1.75。

从以上数据可以看出，ABCAHSOS算法的平均消耗时间低于ABC算法的一半，其标准差更是远远低于ABC算法。综上所述，与ABC算法相比，ABCAHSOS算法在解决频率分配问题时不仅平均消耗时间更短，而且其所消耗时间的分布更加稳定。

图5 算法运算时间对比Fig.5 The contrast of duration between two algorithms

5 结束语

本文提出了一种基于蜜源优化策略的频率分配方法。该方法以传统人工蜂群算法为基础，对引领蜂搜索机制进行适应性改造，使之更加适合频率分配问题求解;然后，使用交叉机制对跟随蜂的搜索行为进行改进，并增加选择性变异操作，优化搜索蜜源过程，从而实现提高搜索效率的目的。仿真结果表明，本文算法可以快速得到最优解，其迭代效率、时间效率、稳定性皆优于传统人工蜂群算法，而且其蜜源设计以及干扰影响计算方法更适应频率分配的实际应用场景，可以为解决大量设备的频率分配问题提供参考。不过，本文算法性能依赖于算法参数设定，后续将根据实际问题的规模、应用限制等进行参数最优设置，以达到进一步提高算法性能的目的。

[1] 徐雪飞，李建华，沈迪，等.基于量子遗传算法的航空通信频率动态分配[J].电讯技术.2015,55(12):1311-1317. XU Xuefei，LI Jianhua，SHEN Di,et al.Dynamic aeronautical communication frequency assignment based on quantum genetic algorithm[J].Telecommunication Engineering,2015,55(12):1311-1317.(in Chinese)

[2] GHOSH S C,SINHA B P,DAS N. Channel assignment using genetic algorithm based on geometric symmetry[J].IEEE Transactions on Vehicular Technology,2003,52(4):860-875.

[3] MANUEL D,DIETMAR K,BERNHARD R. Channel assignment for cellular radio using simulated annealing[J].IEEE Transactions on Vehicular Technology,1993,42(1):14-21.

[4] 薛寒，刘培国，黄纪军. 基于混合粒子群优化的频率指配方法研究[J].现代电子技术，2015,38(16):1-3. XUE Han,LIU Peiguo,HUANG Jijun. Method for frequency assignment based on hybrid particle swarm optimization algorithm[J].Modern Electronics Technique,2005,38(16):1-3.(in Chinese)

[5] 向万里.混合群体智能优化算法及应用研究[D].天津：天津大学,2013. XIANG Wanli. Research on hybrid swarm intelligence optimization algorithms with applications[D].Tianjing:Tianjing University,2013.(in Chinese)

[6] 张超群.混合爆炸式人工蜂群算法及应用研究[D].上海：东华大学,2015. ZHANG Chaoqun. Research on hybrid explosion-based artificial bee colony algorithm and its applications[D].Shanghai:Donghua University，2015.(in Chinese)

[7] 宁爱平.人工蜂群算法及其在语音识别中的应用研究[D].太原：太原理工大学,2013. NING Aiping. Research on artificial bee colony algorithm and its application in speech recognition[D].Taiyuan:Taiyuan University of Technology，2013.(in Chinese)

[8] 刘俊霞，贾振红，覃锡忠，等.改进人工蜂群算法在信道分配上的应用[J].计算机工程与应用,2013,49(7):119-122. LIU Junxia，JIA Zhenhong，QIN Xizhong，et al.Application in channel assignment based on improved artificial bee colony algorithm[J].Computer Engineering and Application,2013,49(7):119-122.(in Chinese)

[9] 高珊，马良，张惠珍.改进人工蜂群算法求解信道分配问题[J].计算机与应用化学，2015,31(1):98-102. GAO Shan，MA Liang，ZHANG Huizhen. Solving frequency assignment problem using an improved bee algorithm[J].Computers and Applied Chemistry,2015,31(1):98-102.(in Chinese)

[10] SMITH D H,TAPLIN R K,HURLEY S. Frequency assignment with complex co-site constraints[J].IEEE Transactions on Electromagnetic Compatibility,2001,43(2):210-218.

[11] 熊健，喻歆.一种基于模因演算法的频率分配新策略[J].电讯技术,2012,52(5):748-754. XIONG Jian,YU Xin. A new frequency assignment strategy based on memetic algorithm[J].Telecommunication Engineering,2012,52(5):748-754.(in Chinese)

[12] 刘婷.改进人工蜂群算法及其在多用户检测中的应用[D].天津:天津大学,2013. LIU Ting. Research on improved artificial bee colony and its application in multiuser detection[D].Tianjing:Tianjing University,2013.(in Chinese)

A Frequency Assignment Method Based on Honey Source Optimization Strategy

WU Qi

(Southwest China Institute of Electronic Technology,Chengdu 610036,China)

In order to solve the frequency assignment problem,a frequency assignment method based on the honey source optimization strategy is proposed.To increase the diversity of the honey and reduce the possibility of falling into the local optimal solution,a traditional artificial bee colony algorithm is improved. Firstly,a method to evaluate the interference is proposed. Secondly,the searching behave of leading bee is improved,and searching behave of following bee is redesigned. Finally,selective mutation operation is added after the searching of reconnoitering bee. The simulation results show that the proposed algorithm has more advantages in searching efficiency and stability and can find frequency assignment strategy satisfying frequency-distance constraints with acceptable time consumption.Key words：spectrum management;frequency assignment;artificial bee colony;honey crossing;selective mutation

10.3969/j.issn.1001-893x.2017.07.008

吴麒.基于蜜源优化策略的频率分配方法[J].电讯技术，2017,57(7):778-783.[WU Qi.A frequency assignment method based on honey source optimization strategy[J].Telecommunication Engineering,2017,57(7):778-783.]

2017-03-17；

2017-06-05 Received date:2017-03-17；Revised date：2017-06-05

TN92

A

1001-893X(2017)07-0778-06

吴 麒(1985—)，男，四川眉山人，2012年于四川大学获博士学位，现为工程师，主要研究方向为数据挖掘、通信侦察、信号分选。

Email:acuteleopard@163.com

**通信作者：acuteleopard@163.com Corresponding author：acuteleopard@163.com