基于禁忌搜索的战术通信网频率指配方法
2016-07-19张鹏,王凡
张 鹏,王 凡
(1. 91404部队，河北 秦皇岛 066000；2．中国电波传播研究所，山东 青岛 266107)
工程与应用
基于禁忌搜索的战术通信网频率指配方法
张鹏1,王凡2
(1. 91404部队，河北 秦皇岛066000；2．中国电波传播研究所，山东 青岛266107)
摘要：针对战场环境中部署的数量巨大的战术通信网的频率指配问题，提出一种基于禁忌搜索的频率指配方法。首先，根据应用场景建立了基于多约束关系的指配模型。其次，为适应战术通信网的特点以及战场快速反应的需求，引入在人工智能领域以计算速度快和灵活高效著称的禁忌搜索算法，设计了基于禁忌搜索的频率指配算法流程及涉及的各关键要素，核心是设置了综合禁忌策略和赦免策略的新解接受准则；并利用工程经验对算法作了提速改进。经仿真验证，该方法可以实现战术通信网频率灵活、高效地快速指配。
关键词：战术通信网；禁忌搜索(TS)；频率指配中图分类号：TN92
文献标识码：A
文章编号：1673-5692(2016)03-293-07
0引言
“网络中心战[1]”作为未来信息化作战的主要模式，将全面改变作战力量的作战方式，同时对通信网络的有效运转也提出了更高要求，从而导致频谱管理系统必须采用更加智能和高效的技术来满足通信网络的管理需求，以适应高技术条件下军事斗争的需要。“网络中心战”里起重要作用的军事通信网按通信联络保障范围分战略通信网和战术通信网。战略通信网主要为最高指挥当局、各军兵种和战区级指挥系统提供长途定点通信服务，以固定通信系统为主。战术通信网的主要任务是为数字化战术兵团和部队指挥提供通信保障，以移动(无线)通信为主。战术通信网的有效运转对于保障战场战术信息传递至关重要,世界上许多国家都给予了高度重视[2]。由于战术通信网应用场景复杂，种类繁多且功能各异、数量巨大且分布集中、拓扑形状不规则等原因，使得如何快速、高效、智能地为战术通信网进行频率指配成为频谱管理的难点问题之一。
为适应战术通信网的特点以及战场快速反应的需求，本文引入在人工智能领域以计算速度快和灵活高效著称的禁忌搜索(Tabu Search，简称TS)算法来解决战术通信网的频率指配问题，首先根据应用场景建立了数学模型，其次设计了基于TS的战术通信网频率指配算法和涉及的各要素，最后对算法进行了仿真验证。
1数学模型
战术通信网既不同于传统有线网络，也与纯粹的Ad Hoc网络不同，其无线网络成分较多，网络拓扑结构一般分为：总线形、星形、树形、网形等，本文以战术通信网中较常见且结构最为复杂的网型拓扑为例，进行建模仿真，具有较强的实际应用意义，如图1所示。
图1 子网网络节点拓扑图
频率指配数学模型是指将影响频率指配的各因素转化为可操作的数学描述，本文所建数学模型包含两个方面的内容：一方面来自于指配对象，一方面来自于频率资源。
指配对象考虑三种干扰，包括同频干扰、邻频干扰、共址干扰，分别建立了同频干扰约束矩阵A、邻频干扰约束矩阵B和共址干扰约束矩阵C，矩阵中的元素分别代表链路间的两两约束关系。各种约束关系的获得是进行频率指配的前提，具体来说，是将频率指配所涉及的地形地物信息、台站设备信息、天馈线信息、电波传播效应等因素通过兼容性分析转化为多重约束关系。
战场电磁环境高实时、强对抗的特殊性导致其频谱资源占用情况必然不是一成不变的，频率资源的质量对战术通信网在实际工作过程中的通信质量有着至关重要的影响。因此，在指配模型中引入根据电磁环境监测数据统计分析所得的频率占用度，作为表征指配频率解频谱资源质量优劣的参数之一。
代价函数[3]的设计对配结果的好坏起着至关重要的作用。针对所建模型，设计了下列代价函数cost，分别由违反同频约束、邻频约束、共址约束的链路数乘以各自的惩罚因子和指配解中各频点的频率占用度乘以资源贡献因子之和得到，它反映了该组指配解干扰的大小和频率质量的优劣，如下式所示：
(1)
其中，S代表一组指配解，N表示链路数，α、β、γ分别为同频干扰、邻频干扰、共址干扰的惩罚因子；δ为频谱资源贡献因子，若无法获得电磁环境监测数据，则该项因子取值为0，上述四项因子可以根据用户需求自定义设置；FOi表示第i条链路所指配频点的频率占用度，FOi取值范围在0到1之间。A(i,j)、B(i,j)、C(i,j)分别如下所示：
(2)
(3)
(4)
上述表达式是指若链路i和j具有同频约束关系(即aij=1)、邻频约束关系(即bij=1)或同址约束关系(即cij=1)，则当它们使用同频、邻频或频率间隔小于m时，即违反了同频、邻频或共址约束关系，将计算其干扰；否则，不计干扰。
将约束矩阵中非零元素在所有元素中所占比重定义为约束矩阵密度，可表征电磁环境及网络拓扑的复杂情况。若电磁环境或网络拓扑越复杂，则矩阵约束密度值越大。可知，约束矩阵密度取值范围在0到1之间。
应用该模型的核心是确定以上八个约束因子。算法的最终目标是使cost(s)达到最小，即min(cost(s))。本文侧重点是在假设各链路的约束关系已经得到的前提下，利用智能优化算法来设计高效、稳定的频率指配算法。
2基于TS的算法设计
TS由美国系统科学家Glover[4-5]教授于1986年正式提出，经过不断的研究与完善，已成为解决组合优化难题的有效工具。它是局部邻域搜索算法的推广，是一种全局逐步寻优的人工智能优化算法。TS模仿人类的记忆功能，它通过对一些局部最优解的禁忌(也可以说是记忆)达到接纳一部分较差解，从而跳出局部搜索的目的；同时赦免禁忌区域中的一些优良状态，进而保证搜索的多样性，从而达到全局最优[6]。
利用TS的思想设计了频率指配算法流程图，如图2所示。
图2 基于TS频率指配算法流程图
流程图中的核心要素包括：设置禁忌表、设计新解接受准则等。结合流程图，下面对TS应用到具体频率指配问题时的各要素设计进行详细阐述：
(1)可用频率
假设有M个可用频率，设当前指配中可用的频率资源为F=(f1,f2,…,fM)。
(2)指配解
用S=
(3)候选解集
给定一个当前解S0，它的候选解集Ne(S)中的解定义如下：给定一个新解Sn，Sn与S0相邻当且仅当
(5)
新解Sn是在当前解S0的基础上，选取链路v，为其改变频率，且该链路及其频率不处于禁忌表(tabu list)内，除此链路之外，其他链路的频率不变。
此候选解集中的候选解是由当前解有且仅有一条链路改变频率得到，故可知，当前解S0共有N(M-1)个邻域解。这样构造邻域结构能够提高效率，每次产生新解时只更新一个链路的频率，以免一次更新多个链路的频率，使得在某些链路找到最优频率的同时，其它一些已经处在最优频率的链路又更换了频率，很难使所有链路同时找到最优频率。
(4)新解产生方法
为了遍历所有邻域解，用一个随机搜索过程产生当前解S=
1)随机选择一条链路v(v∈[1,2,…,N])；
2)随机选择一个新频率fi(i∈[1,2,…,M])；
3)将新频率fi指配给链路v。
(5)禁忌表
禁闭表中的元素：(v,f)，其中v代表链路，f代表分配给v的频率。每次当某个f被分配给v之后，就将(v,f)插入禁闭表中，该值在之后的大约tl(禁闭表的长度)次迭代中将一直被禁忌[7]。
在编程实现中用一个N×M维矩阵T实现禁忌功能，矩阵中的每个元素T[i,j]记录迭代的次数直到该元素被禁忌(即给该元素加一个禁忌长度的数值)，其中i表示链路号，j表示频率号。该数据结构可以根据比较当前的迭代次数Iter和矩阵中所记录的元素的大小，很容易地判断一个行动是否被禁忌。
(6)赦免准则
若某个候选解的代价值优于历史最优值，那么无论这个候选解是否处于被禁忌的状态，都会被接受。
(7)新解接受准则
禁忌策略和赦免策略是禁忌搜索中的两大核心策略，两者是对立统一的。综合禁忌策略和赦免策略设计了本算法的新解接受准则：
1)赦免策略R：新解代价cost是否小于历史最优解的代价costbest，见表1。
表1 赦免策略判定表
2)禁忌策略P：新解采取的移动是否处于禁忌状态，见表2。
表2 禁忌策略判定表
3)新解和上次解关系判别策略X：新解代价值cost是否小于上次解代价值costx，见表3。
表3 新解和上次解的关系判定表
综合实际可能出现的情况将三种策略进行结合得到以下结果，见表4。
(8)终止准则
设一最大迭代步数MAX，当迭代次数Iter>MAX或当连续迭代W次代价值无改善时，算法终止。
表4 三种策略结合判定表
3算法提速设计
频率指配问题在本质上属于组合优化问题，是一个NPC问题[8]。NPC问题的一个特征是随着处理对象规模的扩大，算法运行时间会随对象规模成指数级“爆炸性”递增[8-9]。此时，确定性算法、贪婪算法、局部搜索算法已经难以奏效，而基于仿生学原理的智能优化算法可以很好的解决传统算法难以求解NPC的问题。
在工程实践中，我们发现跟确定性算法比起来，利用智能优化算法可大幅缩短算法运行时间，但处理对象的规模仍然是影响算法运行时间最大的因素。为了使设计的频率指配算法可以更好地满足应用需求，对算法进行了提速改进。改进思路为利用频谱的时空有效性特征，在TS智能优化频率指配算法执行之前，对频率指配对象进行预处理，分析空域、时域、频域复用关系，将指配对象进行分类，减小单次指配对象规模。
4仿真结果及分析
下面对所设计的基于TS的战术通信网频率指配方法进行仿真分析，首先，仿真了该算法运行过程中代价值(干扰)随迭代步数的变化曲线，分析了算法的寻优性能；其次分析了算法迭代次数对解的质量的影响；最后，分析了不同电磁环境复杂度、不同网络规模情况下算法的性能，对比了算法提速改进前后的运行时间、最优解代价值等。
(1) 算法性能分析
假设某战术通信网链路数为100、频率数为30，惩罚因子α、β、γ取值分别为50、20、10，频谱资源贡献因子δ取值为100，同频、邻频、共址约束矩阵密度分别为0.3、0.2、0.1时，图3为指配过程中的代价(干扰)随迭代步数的变化曲线。
图3 代价值随迭代步数变化曲线
由图3可知，初始指配解代价值为8 600，算法收敛后最优指配解代价值为1 560，算法运行时间为7.987s，可见算法在较短的时间内收敛到最优解。为了观察搜索过程，取上述图(a)中的一部分(迭代步数为56～70)放大，如图(b)所见，搜索过程接受了劣解，并不断跳出劣解，最终趋向于收敛，证明设计的禁忌赦免策略较成功的完成了搜索最优解的任务。
(2)迭代次数对解质量的影响
为了讨论迭代次数对解质量的影响，以100条链路，40个可用频率，同频、邻频、同址约束矩阵密度分别为0.5、0.4、0.3为例，分析算法在相同的初始指配解、相同约束矩阵的条件下，不同迭代次数对指配解及运行时间的影响(为避免单次运行的随机性，每个迭代次数运行50次，取平均值)，如图4所示。
图4 代价和运行时间随迭代次数的变化曲线
由仿真结果可知，将最大迭代步数MAX由300次增至3 500次过程中，代价值不断降低，解的质量由6 114改善到1 160，但运行时间也相应增加，由算法时间复杂度可知，运行时间和迭代次数成正比线性增加，由7.427 s增至115.242 s。由3 500次再增加迭代次数，解的质量将不再有较大的改善，但相应的运行时间还会增加。故此仿真结果可指导算法中迭代次数最大值的设立。实际中，可根据需要来权衡运行时间和解的质量。
(3) 不同复杂度指配结果分析
下面分析了在不同电磁环境复杂度情况下算法的性能，对比了算法提速改进前后的运行时间、最优解质量等，惩罚因子α、β、γ取值分别为50、20、10，频谱资源贡献因子δ取值为100。
由以上仿真结果可知：
1)所设计的TS频率指配算法可以在较短的时间内获得指配解，提速改进前平均时间15.636 s，最短、最长时间分别为9.920s、23.500 s，提速改进后平均时间2.183 s，最短、最长时间分别为3.156 s、1.102 s。
2)同频、邻频、同址约束矩阵密度代表网络电磁环境的复杂度，约束数越多，说明网络电磁环境越复杂。在相同链路数和频率数的前提下，所得最优解质量会随电磁环境复杂度增加而变差，运行时间也会略微增加，但增加幅度较小。
3)分析了100条链路在可用频率数分别为30、40、50情况下的指配结果，可知，增加可用频率数，可以降低频率指配难度，加快算法收敛时间，提升解的质量。
4)经提速改进后，算法运行时间有了较明显的缩短。
(4) 不同规模网络指配结果分析
下面对比分析了在不同规模网络情况下算法提速改进前后运行时间、代价值变化情况等，惩罚因子α、β、γ取值分别为50、20、10，频谱资源贡献因子δ取值为100。
表5 不同电磁环境复杂度情况下的指配结果
表6 不同网络规模情况下的指配结果
由上表可知，经提速改进后，当链路数分别为100、200、300、500、1000时，算法运行时间分别由12.934 s、47.273 s、109.959 s、254.152 s、1150.356 s缩短至8.456 s、29.364 s、60.487 s、106.367 s、198.459 s，由此可知，改进后的算法可大幅提升算法运行效率，缩短算法收敛时间，而且链路规模越大，提速效果越明显。由此可见，所设计算法解决了频率指配问题运算时间随指配对象规模增大成指数级递增的“爆炸性”不可接受增长。
5结语
针对未来信息化战场的战术通信网频率指配问题，首先，综合分析其应用场景，利用频谱监测数据，建立了基于多约束关系的指配模型；其次，引入在人工智能领域以计算速度快和灵活高效著称的禁忌搜索算法，设计了基于TS的频率指配算法，核心是设置了综合禁忌策略和赦免策略的新解接受准则，并根据工程化经验对算法进行了提速改进。经仿真验证，该方法在搜索过程中算法可接受劣解，并不断跳出劣解，最终趋向于收敛，证明所设计的禁忌赦免策略成功完成搜索最优解的任务；其次，分析了不同迭代次数、电磁环境复杂度、网络规模对解质量的影响，可知该方法可有效解决不同电磁环境复杂度及网络规模的战术通信网频率指配问题，并为算法的工程化应用提供了参数设置经验。
参考文献：
[1]U.S Department of Defense， Net-Centric Spectrum Management Strategy， August 3，2006
[2]U.S Department of Defense， Joint Spectrum Vision 2010， Washington， DC
[3]K.I.Aardal，S.P.M.van Hoesel， A.M.C.A.Koster， C.Mannino， and A.Sassano. Models and solution techniques for frequency assignment problems [J]. Quarterly Journal of the Belgian， French and Italian Operations Research Societies (4OR)， 2003
[4]Glover F. Tabu search: part I . ORSA Journal on Computing， 1989， 1:190-206
[5]Glover F. Tabu search: part II . ORSA Journal on Computing， 1990， 2:4-32
[6]汪定伟, 王俊伟, 王洪峰, 等. 智能优化方法[M]. 北京: 高等教育出版社, 2007: 81.
[7]Hao， J.-K.， & Perrier， L. Tabu search for the frequency assignment problem in cellular radio networks.Technical Report LGI2P， EMA-EERIE， Parc Scientifique Georges Besse， Nimes，France. 1999
[8]Smith D H, Allen S M, Hruley S, et al. Frequency Assignment: Methods and Algorithms[R]. 1999, 11.
[9]王凡.频率指配关键技术研究[D]. 电子科学研究院. 2010，5-6.
[10]王凡，董俊，卢冬鸣，等. 混合智能优化频率指配算法[J]. 电波科学学报，2013，28(5)：947-952.
A Method for Frequency Assignment of Tactical Communication Network Based on Tabu Search
ZHANG Peng1, WANG Fan2
(1. Unit 91404 of PLA, Qinhuangdao Hebei 066000, China；2. China Research Institute of Radiowave Propagation, Qingdao Shandong 266107, China)
Abstract:Aiming at the frequency assignment problem of tactical communication network with huge number in the battlefield environment, a method of frequency assignment is presented based on tabu search algorithm. First, the frequency assignment model with multi-constraint relations is established according to the application scenarios; secondly, in order to adapt to the characteristics of tactical communication network and the demand of the battlefield with rapid response, the tabu search algorithm which is famous for its flexible and efficient in the field of artificial intelligence is introduced, the flow and key elements of the algorithm is designed based on tabu search, a new solutions acceptance criteria synthesized with prohibition strategy and forgiveness strategy is set；and the algorithm is improved using engineering experience. The simulation results show that this method can realize the frequency assignment of tactical communication network flexibly and efficiently.
Key words:tactical communication network; tabu search; frequency assignment
doi:10.3969/j.issn.1673-5692.2016.03.014
收稿日期：2016-02-22
修订日期：2016-05-23
基金项目：国家863项目(2015AA7124068)、国家973项目(6133190102)、青岛自主创新重大专项(14-6-1-8-ZDZX)
作者简介
张鹏 (1974—)，男，山东利津人，副总工程师，主要研究方向为战术通信与电子对抗；
E-mail：wangfan_01@126.com
王凡(1982—)，女，河南温县人，工程师，主要研究方向为电磁频谱管理。
