基于模拟退火算法的频率指配算法优化

王更辉

(中国电子科技集团公司第五十四研究所，河北 石家庄 050081)



基于模拟退火算法的频率指配算法优化

王更辉

(中国电子科技集团公司第五十四研究所，河北 石家庄 050081)

模拟退火算法是最早应用于频率指配的智能算法之一，具有设计简单、频率指配合理等优点。但在某些具体频率指配环境中，模拟退火算法存在运算时间较长的缺点。通过分析频率指配影响算法的条件，深入剖析模拟退火算法在频率指配中的运行机制，缩小邻域选择范围、引进贪婪原则改进新解产生方式、增加升温过程和初始解重新设置等方式，对模拟退火算法在频率指配中的应用进行了优化，在保证符合频率指配约束条件的情况下，提升了模拟退火算法的运算效率。

模拟退火；频率指配；贪婪原则

0 引言

随着现代无线通信技术的快速发展，各种新型无线通信系统不断涌现，通信网络结构日趋复杂，无线通信设备急剧增加，高速增长的无线频率的需求与有限的频率资源的矛盾变得更加突出。频率指配作为研究频率能够合理规划和有效利用的重要内容，就是为每个通信设备在规定的频率范围内指定一个合理的工作频率，使得频谱整体得以有效利用，并且各个通信设备的工作频率不互相干扰。频率指配算法作为频率指配的核心，决定了频率指配的工作效率和频率指配结果的合理性[1]。

1 频率指配简介

频率指配是优化频率利用、提高信道容量和减少干扰的主要手段，通过频率指配将无线电频率指定给相应的无线电设备，使其在规定的条件下使用。当前频率指配主要应用于无线通信网络，其最终目的是在保证网络中无线通信设备能够正常通信的情况下，最大限度地提高频率利用率[2-3]，影响频率指配的主要因素是频率干扰和可用频率。

1.1 频率干扰

频率干扰是频率指配考虑的重要因素，频率干扰的类型包括：同频干扰、互调干扰、杂散干扰和邻道干扰。同频干扰是指相邻2个或多个无线设备的覆盖重叠内，接收点场强是来自各无线设备信号场强之和，从而产生了互相干扰。互调干扰是由于不同频率的2个或多个射频信号在某台无线设备经非线性作用产生了新的等于另一频点的频率分量而引起的干扰，一般情况下，互调干扰主要考虑二阶互调干扰和三阶互调干扰。杂散干扰主要是指由于无线设备中的滤波特性不好，使得一些二次和三次谐波分量在输出时产生杂波辐射信号。邻道干扰是指相邻的或邻近波道之间的干扰。其中杂波干扰和邻道干扰主要因为无线设备的技术指标不合格引起的干扰，因此在频率指配过程中主要考虑同频干扰和互调干扰。

频率指配通过频率间隔合理利用频率，避免无线设备间的频率干扰。频率间隔由工作频率特性和无线设备的技术指标来决定，对可用频率的利用效率产生影响。一般情况下，无线设备的技术指标确定了该设备避免频率干扰的频率间隔。

干扰数据模型是描述无线设备之间频率干扰约束关系的模型[4-5]，主要以矩阵的方式进行表示。无线设备之间的干扰约束关系函数如下：

根据干扰约束关系，可以得到总的干扰数目[5]，干扰数目的目标函数如下：

当无线设备的数量确定后，干扰数目对频率指配算法产生影响，随着干扰数目的增大，频率指配算法的效率迅速降低。

1.2 可用频率

可用频率是指无线设备在指配频率时可以使用的频率。为了保证所有无线设备的正常工作，需要对每类无线设备的工作频率范围进行划分。并且根据电磁环境的复杂性和有意无意的电磁干扰，无线设备在频率指配之前需要提前将一些被干扰的频点进行剔除。

Fv=FD-Ff，

式中，Fv为频率指配时无线设备可以使用的频率，FD为无线设备的频率工作范围，Fv为频率指配时无线设备禁止使用的频率，包括电磁环境中被干扰的频率、已分配给其他无线设备的频率等。当无线设备的数量确定后，可用频率Fv越多，频率指配算法的效率越高。

2 基于模拟退火算法的频率指配算法

2.1 模拟退火算法概述

模拟退火算法最早由Metropolis等人于1953年提出，1983年Kirkpatrick将它应用于组合优化问题[6-7]，Duque等人在1993年首先使用模拟退火算法解决频率指配问题[8]。模拟退火算法是一种基于迭代求解策略的随机搜索算法[9]，用于在一个解空间内寻找问题最优解。模拟退火算法模拟了整个物理退火过程：将固体加热至足够高的温度，使固体内粒子变为随机无序状态；然后逐步降温冷却，使粒子在每个温度下渐趋有序状态，达到平衡；最后在常温时，固体粒子达到稳定状态。

模拟退火算法的核心是基于Metropolis接受准则[10]，避免模拟退火算法在搜索过程中陷入局部最优的同时趋向全局最优解，在解空间内随机选择最新解，再以Metropolis接受准则，判断是否接受最新解替代当前解，最终收敛于当前最优解。

Metropolis接受准则确定如下：

式中，P为温度tk下i状态向j状态转变时接受j状态的概率，f(i)为i状态下的能量函数，f(j)为j状态下的能量函数。

2.2 基于模拟退火算法频率指配

基于模拟退火算法的频率指配算法的主要结构如下。

2.2.1 解结构

模拟退火算法的解的结构如下：

2.2.2 评价函数

评价函数是判断算法取得解的判定标准[11]，主要用于判定解是否满足频率指配要求和比较2个解的优劣程度。模拟退火算法的评价函数如下：

2.2.3 邻域结构

在模拟退火算法中，邻域结构是最重要的概念之一 。频率指配中邻域结构的定义：有当前解v0，当解空间Vl0中任意解vi有且只有一个无线设备所指配的频率与当前解中的无线设备频率不同，Vl0就是v0的邻域。算法新解的产生就是在当前解的邻域中随机选择，并不断重复这个过程。

基于模拟退火算法的频率指配算法描述如下[12]：

① 初始化算法参数。设置初始温度T、降温衰减值K(一个接近于1的常数)、迭代次数N等参数。

② 随机产生初始解v0为当前解V=v0，并计算当前解的代价Cost(V)。

③ 在当前解的邻域中随机选择解vi，计算新解的代价Cost(vi) 。

④ 如果Cost(vi)

⑧若迭代次数n≥N，则T=T*K。

⑨ 算法是否结束，是则停止，否则转③。

基于模拟退火算法的频率指配算法的流程图如图1所示。

图1 基于模拟退火算法的频率指配算法流程图

3 算法的分析与优化

3.1 算法分析

模拟退火算法应用于频率指配时能够收敛到一个最优解，从而获得无干扰的频率解。然而，模拟退火算法是一个极其耗时的迭代计算过程,理论上算法需要访问无穷多个状态[13-14],在实际频率指配过程中发现了以下特性:

① 频率解的产生随机性太大，造成许多不必要的重复，在整个迭代过程中不能快速地收敛，成为算法运行耗时的主要原因。

② 当频率干扰密度较小且频率资源远远大于所需频率时，能够快速获得最优频率解。

③ 当频率干扰密度较大且频率资源不太充足时，算法运行时间较长，甚至陷入局部最优，不能获得最优频率解。

④ 当算法能够获取最优解的情况下，算法结束时间的温度都处于较高位置，即当温度降低到一定程度后算法能够获取最优解的概率大大降低。

试验表明，初始温度值为T=10，温度冷却衰减函数K=0.9。获取最优解的概率如表1所示。

表1 不同温度下获取最优解的概率

3.2 算法优化

3.2.1 频率新解的产生

模拟退火算法新解是从当前解的邻域中随机选择产生的，搜索的解空间很大，新解被拒绝的概率大大增加，在约束条件苛刻时产生新解将是一个耗时的过程。

本文针对频率新解产生进行了以下优化：

(1)优化邻域结构

针对上述问题，首先重新构建当前解的邻域，从而增加新解被接受的概率。

首先，计算每个无线设备的评价函数，即每个无线设备与其他无线设备的干扰评估。

式中，Cost(vi)为无线设备i的评估函数，hvi(j)为无线设备i与无线设备j的违约代价。

其次，根据每个无线设备的评价函数确定每个无线设备增加选择权重，就是增大评估函数大的无线设备的选择权重。

最后，随机选择一个无线设备，通过变换其频率解(其他无线设备的频率不变)组成当前解的邻域，缩小了邻域范围。

(2)优化新解产生方式

在新解产生过程中引进贪婪算法[15]，通过在邻域中多次随机选择频率解，根据Metropolis接受准则，接受选择的频率解。产生频率解的过程如下：

① 初始化新解为当前新解s0，计算当前解的代价Cost(s0)。

② 随机从邻域中选择新解si，计算当前解的代价Cost(si)。

③ 若Cost(s0)≥Cost(si)，则转⑤，否则在(0,1)区间上产生一个均匀分布的随机数ξ。

⑤s0=si，并令Cost(s0)=Cost(si)。

⑥若 完成M次选择，则将当前新解最为最终解返回，否则转②。

在优化的新解产生过程中，选择次数M尤其重要，如果M过大则使模拟退火算法迅速收敛到局部最优，M过小则使模拟退火算法收敛效果不明显。通过试验证明M值与可用频率数基本一致。

3.2.2 温度控制和初始解重置

模拟退火算法在温度较高时，接受大于当前解代价的新解的概率比较大，从而跳出局部极值，使当前状态落入包含最优解的全局中；而当温度降低时，接受的概率迅速减小。当温度降低到一定程度，算法只接受比当前干扰评估低的新解，算法最终退化为局部搜索。

初始解是模拟退火算法开始迭代的起点。模拟退火算法是一种“健壮”的算法，初始解的优劣不是使算法导出质量高的最优解必要条件。但初始解是模拟退火算法在解空间中随机选取的解，使得各无线设备的频率处于随机状态。在算法陷入局部最优时可以作为突发状态，重新设置初始解可以使算法跳出局部搜索。

依据以上特性，模拟退火算法运算过程中在陷入局域搜索时通过重置初始温度和初始解，使算法的状态跳出局部搜索，重新在全局搜索最优解，增加获取最优解的概率。

4 算法性能验证

为了验证优化后的算法的性能对比，本节将在相同的模拟环境下，通过运行2种算法分别进行试验。模拟环境的条件如下：选用相同的无线设备参数，无线设备的数量为50台；计算无线设备的干扰，选取干扰数目为20、60、100、150、180。

在相同模拟环境下，当无线设备的可用频率数量为50个时，2种算法计算8次的试验数据如表2所示。当无线设备的可用频率数量为75个时，2种算法计算8次的试验数据如表3所示。

表2 可用频率为50个的性能对比

表3 可用频率为75个的性能对比

从表3中可以看出，在相同模拟环境中进行频率指配时，优化的模拟退火算法虽然在干扰数目少时出现了性能略微下降，但随着干扰数目的增加，优化的模拟退火算法的性能比原有算法有了大幅提升，最终能够稳定在一个可接受的范围。通过对2个表中的数据进行对比，在频率资源不同的情况下，频率资源的多少对优化模拟算法的影响要小于对原有算法的影响。

5 结束语

针对基于模拟退火算法的频率指配算法，通过频率干扰模型对频率指配算法的影响，对基于模拟退火算法的频率指配算法进行了深入的分析，主要包括频率指配解的获取方法、模拟退火算法的温度控制和初始解对最终解的影响。根据模拟退火算法运行机制的特点，对基于模拟退火算法的频率指配算法进行了优化设计。仿真结果表明，优化后的频率指配算法效率大大提高，尽最大努力避免了频率指配算法陷入局部最优解的可能性。

[1] 丁鲜花,方箭,刘艳洁,等.无人机通信链路频率划分研究[J].无线电工程,2015,45(5):76-80.

[2] 李锐，周自力，刘松淘，等.一种提高频普利用率的航空导航台站频率指配算法[J].电讯技术，2016(12)：1359-1364.

[3] 李军芳,韩建敏.基于Bertrand博弈论的动态频谱分配算法[J].无线电工程,2011,41(8)：44-46.

[4] 谭云婷,熊珊.基于空间相邻分析的基站数据模型与算法研究[J].移动通信，2016,40(1)：34-38.

[5] 王海超,王乐,刘杰群,等.基于频率和时间的蜂窝间干扰管理方法研究[J].移动通信,2016,40(1)：54-58.

[6] 陈浩.遗传算法在频率指配问题中的应用研究[D].北京：北京交通大学，2009.

[7] Kirkpartrick S，Gelatt C D，Vecchi M P．Optimization by Simulated Annealing[J]．Science，1983，220：671-680．

[8] Duque-Ant on M，Kunz D，Ruber B.Channel Assignment for Cellular Radio Using Simulated Annealing[J].IEEE Transactions on Vehicular Technology,1993,42:14-21.

[9] 朱颢东,钟勇.一种改进的模拟退火算法[J].计算机技术与发展,2009,19(6):32-35.

[10]卢才武,唐晓灵,张志霞,等.计算智能[M].西安：陕西科学技术出版社，2008.

[11]肖剑.无线电磁频率管理中频率指配技术的研究[D].长沙：中南大学，2012.

[12]陈华根,吴建生,王家林,等.模拟退火算法机理研究[J].同济大学学报,2004,32(6):802-805.

[13]王强.模拟退火算法的改进及其应用[J].应用数学,1993,4(3):392-397.

[14]孙坪，吴建军.直接搜索模拟退火算法的自适应改进[J].计算机工程与应用，2015，51(23)：31-37.

[15]张超.基于贪婪算法的遥感地面站任务调度技术[J].无线电工程,2011,41(1)：58-60.

Frequency Assignment Algorithm Optimization Based on Simulated Annealing Algorithm

WANG Geng-hui

(The 54th Research Institute of CETC，Shijiazhuang Hebei 050081，China)

Simulated annealing algorithm is one of the earliest intelligent algorithms applied in frequency assignment，which has the advantages of simple design and reasonable frequency assignment.However，in some specific frequency assignment environments，simulated annealing algorithm has the disadvantage of long run time.In order to optimize the application of simulated annealing algorithm in frequency assignment，a variety of research methods are used in this paper，including analyzing the condition that affects the frequency assignment algorithm，making a deep analysis on the operating mechanism of annealing algorithm in frequency assignment，narrowing the range of neighborhood selection，introducing the greedy principle to improve the way of creating new solutions，adding the process of temperature rising and resetting the initial solution.The operating efficiency of simulated annealing algorithm is promoted while the compliance with frequency assignment constraint condition is ensured.

simulated annealing；frequency assignment；greedy principle

2017-05-18

王更辉(1977—)男，高级工程师，主要研究方向：通信网络管理。

10.3969/j.issn.1003-3114.2017.05.13

王更辉.基于模拟退火算法的频率指配算法优化[J].无线电通信技术,2017,43(5):57-61.

[ WANG Genghui.Frequency Assignment Algorithm Optimization Based on Simulated Annealing Algorithm[J].Radio Communications Technology，2017,43(5):57-61.]

TP393

A

1003-3114(2017)05-57-5