基于量子遗传算法的航空通信频率动态分配*

徐雪飞,李建华,沈 迪,郭 蓉

(1.空军工程大学信息与导航学院,西安710077;2.解放军95983部队,甘肃酒泉732750)

基于量子遗传算法的航空通信频率动态分配*

徐雪飞1,**,李建华1,沈 迪1,郭 蓉2

(1.空军工程大学信息与导航学院,西安710077;2.解放军95983部队,甘肃酒泉732750)

为了更加有效地对航空通信频率进行分配,提出了一种基于量子遗传算法的航空通信频率动态分配方法。通过对频率动态分配思路进行分析,建立了频率动态分配框架,给出了频率动态分配的具体流程。在此基础上,讨论了航空通信频率动态分配问题,定义了航空通信频率动态分配约束条件,建立了航空通信频率动态分配模型。最后,运用量子遗传算法和遗传算法对算例进行仿真对比。结果表明:量子遗传算法在种群适应度和收敛速度上具备明显的优越性,频率动态分配模型能够根据不同种群数量条件动态调整适应度,能够较好满足航空通信频率分配问题动态性、准确性、时效性等实践运用要求。

航空通信;频率动态分配;量子遗传算法

1 引 言

航空通信用频面临着高动态、大尺度和电磁环境复杂等一系列影响因素,有限的频率资源如何高效运用已经成为频率管理领域亟需解决的关键问题。频率分配(Frequency Assignment,FA)是频率管理的重要环节,是装备之间建立有效通信链路的关键阶段。频率分配问题本质是NP-hard问题,解决频率分配问题的核心在于找到有效的优化算法。遗传算法(Genetic Algorithm,GA)[1]通过模拟达尔文《物种起源》中所提出的遗传选择和优胜劣汰的生物进化模型,能够并行实现对参数空间的高效全局搜索。文献[2]提出了一种基于遗传算法的战场频率分配方法,通过改进传统遗传算法的选择、交叉变异过程来实现频率分配的特殊用途,但是遗传算法极易陷入局部最优。为此,将遗传算法和其他优化算法进行组合的混合优化算法逐渐被重视。文献[3]针对传统频率分配遗传算法存在问题,提出了基于种群迁移策略的战场频率动态分配新算法,算法同时考虑两种不同进化理论,能够较好地解决实际战场环境频率分配问题。文献[4]针对无线电台组网应用的特殊性,设计了频率指配模型,提出了基于模拟遗传退火的频率指配算法,并进行应用。量子遗传算法(Quantum Genetic Algorithm,QGA)[5-6]采用量子比特的概率幅对染色体进行编码,使得单个染色体可以表现出更多的状态,极大增强了算法的并行性。文献[7]在文献[6]基础上进行了修正,引入了种群迁移机制,更好地保证种群的多样性。文献[8]提出了一种新的量子遗传算法,其核心思想通过量子比特相位的对比更新从而自适应地改变搜索策略,对于典型函数的收敛效果较好。文献[9]提出了一种混沌更新量子旋转门转角的量子遗传算法,该算法较一般的量子遗传算法收敛速度更快。文献[10]提出了一种混合量子遗传算法框架,在此框架下分别提出了基于二进制编码和基于实数编码的混合量子遗传算法,最后通过仿真对两种算法进行对比,得出基于实数编码的混合量子遗传算法具备更佳的性能。此外,文献[11]提出了一种基于量子位Bloch球面坐标的量子进化算法,给出了一种新的简便型量子旋转门转角的确定方法。

本文针对航空通信频率分配问题,首先提出一种航空通信频率动态分配方法,分析其思路,给出其框架构成;然后,通过对航空通信动态频率分配问题进行分析,建立了航空通信频率动态分配模型;最后,运用量子遗传算法进行算例仿真分析,得出了有效的仿真结论。

2 频率动态分配方法

2.1 思路分析

频率动态分配思路包括以下三个层面,一是频率资源的分配,频率资源分配着重从频率资源属性特征进行分析考虑;二是作战平台的分配,作战平台分配着重从作战平台的价值和功能属性方面考虑;三是战场环境态势的影响,战场环境态势的影响着重从对抗和干扰的角度进行考虑,具体如图1所示。

图1 频率动态分配思路Fig.1 The thought of dynamic frequency assignment

2.2 框架构成

根据频率动态分配思路,将三个层面划归为3个子系统,即频率管理子系统、用户管理子系统和战场环境态势子系统,框架结构如图2所示。

图2 频率动态分配框架结构Fig.2 Architecture for dynamic frequency assignment

主要功能模块描述如下。

(1)用户优先级评价模块

用户优先级评价模块位于用户管理子系统,主要功能是根据用户担负的任务属性和类型,生成相关的优先级评价函数,然后将用户优先级属性和规则库进行对比,从而对用户的优先级别进行判定。

(2)用户优先级规则库

用户优先级规则库位于用户管理子系统,主要功能是根据用户固有的属性生成一套评价用户优先级的基本规则。现代战争样式和任务的复杂化、多样化导致优先级规则库处于不断的变化和更迭中。

(3)频率动态分配模块

频率动态分配模块位于频率管理子系统,是所有系统中的核心模块,主要功能是根据来自用户优先级评价模块、战场环境态势评级模块的反馈信息,结合来自于频率管理子系统内部的频率排序结果,运用匹配理论形成频率动态分配结论。

(4)战场环境态势评价模块

战场环境态势评价模块位于战场环境态势子系统,是用户优先级评价模块和频率动态分配模块的基础,主要功能是根据战场环境态势感知模块和战场环境态势分析模块反馈战场环境信息,通过战场环境态势评价分析,形成一套实时的频率使用规定。

2.3 流程描述

频率动态分配流程如下:

步骤1 获取战场环境态势情况,根据战场环境态势制订初步的用频规划;

步骤2 在获取并分析战场环境态势基础上,对频率进行预选择,选出满足战场环境态势以及业务所需的有效频段;

步骤3 根据用户属性以及所属的作战环境态势,运用一定方法对用户进行排序,得出用户在特定作战阶段下用频优先等级;

步骤4 根据用户优先级别对频率资源进行优化选择,选出能够满足用户需求的频率集合;

步骤5 根据一定的匹配法则将用户和频率进行匹配,形成频率动态分配具体方案。

3 频率动态分配模型

3.1 问题分析

频率分配问题通常可以分为4类[12],即最少频率分配(MO-FAP)、最小跨度频率分配(MS-FAP)、最小阻塞频率分配(MB-FAP)和最小干扰频率分配(MI-FAP)。其中,MO-FAP是指满足频率分配要求,使用频率最少的方法;MS-FAP是指使用最大频率和最小频率之间间隔最小的方法;MB-FAP是指找到一个局部最优分配使得全局的阻塞率最小的方法;MI-FAP是指找到一个分配使得相互之间的干扰最低的方法。

空中进攻作战可以分为作战准备、空中突防、空中突击和作战撤离4个阶段。作战准备阶段需要提前对航空通信频率进行预分配,此时频率分配在满足基本要求的基础上,需要对后续作战阶段预留较充裕的频率资源,故应尽量较少使用频率资源。空中突防阶段通常采取无线电静默的形式进行,此时也应谨慎使用频率资源。空中突击阶段通常是作战全面展开的阶段,各类武器装备开始大规模运用,此时战场环境复杂且频率的运用达到峰值,同时,武器装备的频繁加入或退出战斗进一步增加了频率运用的难度,故应采取动态的频率分配方式,实时对频率分配作出调整,确保武器装备之间频率运用有效且不发生干扰。作战撤离阶段频率进行释放和收回,频率运用将趋于正常。表1对空中进攻作战(AOC)频率分配问题进行了分析。

表1 空中进攻作战频率分配问题分析Table 1 Analysis of AOC frequency assignment problems

3.2 约束条件

本文从干扰角度构建频率动态分配模型。航空通信频率干扰主要存在3种情况,即同频干扰(Co-Channel Interference,CCI)、邻道干扰(Adjacent-Channel Interference,ACI)和互调干扰(Intermodulation Interference,IMI)[13-14]。

工作中，我用真诚、坦率的处事风格和扎实、厚重的业务功底，赢得了领导和同事的认可。1986年，机会再次降临到我的头上，通过筛选，我被海淀区教委选派到北京教育学院脱产学习两年，专业是教育管理。

(1)同频干扰

在移动通信系统中,为了提高频率利用率,在间隔一定距离后,要重复使用相同的频道,但由于相隔距离过近而产生干扰,即为同频干扰。

若链路i和链路j分配的频率分别为fi和fj,链路之间的距离为D,则其同频干扰约束关系可通过二元组进行表示:

式中,⋀表示且关系,dij为链路之间的实际距离。

(2)邻道干扰

由大量通信装备组成通信网络时,在收信机射频通带内或通带附近的信号,经变频后落入中频通带内造成的干扰称为邻道干扰。

若链路i和链路j分配的频率分别为fi和fj,则其邻道干扰约束关系可通过二元组进行表示:

式中,m为信道数,Δf为频道间隔。

由于两个或多个频率分量在传输信道中的非线性器件上相互作用而产生的无用频率分量引起的干扰称为互调干扰。

若链路i和链路j分配的频率分别为fi和fj,则其互调干扰约束关系可通过二元组进行表示:

式中,⋁表示或关系。

频率分配的干扰约束条件可以划归为硬性约束和软性约束两类[15]。硬性约束主要包括一些既定的通信频率设定规则,如上述3类干扰可以划归为硬性约束,一旦违背将会对正常通信造成比较严重的影响,甚至会阻断正常通信。软性约束通常包括一些不可控因素,如阻塞干扰(Blocking Interference,BI)和带外干扰(Out-Band Interference,OBI)等,这些干扰随机产生且难以控制,但这些干扰通常并不会对正常通信产生过于严重的影响。通常情况下,频率分配并不能找到满足于所有约束条件的频率组合,即完美的频率分配并不存在。

3.3 模型构建

假设对一定空域中的N架航空飞行器进行频率动态分配,为了保证N架航空飞行器的通信同时有效进行,每一架航空飞行器需要分配一个使用频段Fi=(),其中,为起始频点,为终止频点,且Fi∈F,F为由所有频段构成的域;每两个通信频率之间的最小频率间隔为Δf,故航空飞行器i在其可用频段Fi内的可用频点集为{+Δ,+ 2Δ,…,}。因此,为每一架航空飞行器分别分配一个频率,则集合(,…,)即为所求频率分配的解集。

根据3.1节分析可得,空中突击阶段频率的运用情况复杂且时变性强,属于频率动态分配的范畴,故频率动态分配模型构建采用MI-FAP较适合。MI-FAP的目标就是找到一组满足各类约束条件的频率集合,使得链路之间相互产生的干扰最小化。为此,引入干扰代价函数cost(f),表示为

式中,α为CCI的干扰代价值,β为ACI的干扰代价值,γ为IMI的干扰代价值。

显然,找到一组频率使得干扰代价函数值最小就是MI-FAP的最优解,即min[cost(f)]。QGA的本质是运用多样化的量子叠加态对GA中种群的交叉和变异进行表现,同时,利用GA将种群中不符合进化要求的个体逐渐剔除,从而找到最优解的集合。为此,干扰代价函数cost(f)可以变换为适应度函数fit(f),进一步可表示为

式中,C为适应度常数,通常取定值3.2[16]。从式(5)可以看出,干扰代价函数和适应度函数fit(f)成反比关系,即干扰较小的个体将拥有更强的适应能力进行遗传和进化。

4 量子遗传算法

QGA通过运用量子位的叠加对传统GA的染色体进行表现,拥有更加丰富的状态。在QGA中,量子位是最小的信息表现单位。一个量子位可以表示0、1两种状态以及其他叠加状态,即表示为

式中,α、β分别为复数,表示量子位相对应的概率幅,且满足归一化条件

下面给出QGA的运算基本流程。

步骤1 令t=0,生成初始量子种群Q(t)为

式中,n表示量子种群的规模,代表遗传进化的迭代数;qti表示一条量子染色体,即第t代种群中第i个个体的量子染色体为

式中,m表示量子染色体的长度,i=1,2,…,n。

步骤3 对解集P(t)中的每一个个体xti的适应度进行求解,存储最优解。若最优解满足一定适应度,则终止算法,否则继续。

步骤4 采用量子旋转门U(θ)更新种群Q(t),其中U(θ)为

步骤5 令t=t+1,并重新返回步骤2,直至完成所有迭代数的运算。

QGA的具体流程如图3所示。

图3 QGA流程图Fig.3 Flow chart of QGA

5 算例仿真与分析

对本文构建的航空通信动态频率分配模型进行仿真分析。分别对数量为40、80、120、160架飞机间进行频率分配,最小频率间隔为25 kHz,仿真计算机为Inter Core 2双核处理器,工作主频2.93 GHz,内存2 GB,仿真软件为Matlab7.10,具体仿真结果如图4～7所示。

图4 种群数量40条件下算法适应度值和运算代数Fig.4 The fitness of algorithm and calculation generation under population 40

图5 种群数量80条件下算法适应度值和运算代数Fig.5 The fitness of algorithm and calculation generation under population 80

图6 种群数量120条件下算法适应度值和运算代数Fig.6 The fitness of algorithm and calculation generation under population 120

图7 种群数量160条件下算法适应度值和运算代数Fig.7 The fitness of algorithm and calculation generation under population 160

从图4～7可以看出,随着种群数量的逐渐增加,运用改进量子遗传算法对其进行求解的最优适应度值逐渐增大。其中,在种群数量为40的条件下,最优适应度值稳定在60左右;在种群数量为80的条件下,最优适应度值稳定在70左右;在种群数量为120的条件下,最优适应度值稳定在90左右;在种群数量为160的条件下,最优适应度值稳定在130左右。这说明频率动态分配模型可以根据种群的数量动态对其适应度函数进行调整,因此能够满足不同种群数量条件下频率分配实时性需要。

根据图4～7,对不同种群数量条件下算法的运算效率进行分析可以得出,随着种群数量的逐渐增加,算法的运算效率逐渐下降。其中,在种群数量为40的条件下,算法在300代左右趋于稳定;在种群数量为80的条件下,算法在350代左右趋于稳定;在种群数量为120的条件下,算法在400代左右趋于稳定;在种群数量为160的条件下,算法在430代左右趋于稳定,且算法收敛度分别为0.53、0.37、0.27和0.16,说明随着种群数量的增加,算法的运算效率有所下降且收敛性能也逐渐降低。

为了进一步验证量子遗传算法的优越性,将量子遗传算法和遗传算法进行对比仿真。继续对数量为40、80、120、160种群数量条件下进行仿真,算法的收敛性对比和运算时长对比分别如图8和表2所示。

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

表2 算法运算时长对比Table 2 The contrast of duration between two algorithms

从图8可以看出,量子遗传算法和遗传算法的稳定代数随着种群数量的增加都分别上升。其中,量子遗传算法的稳定代数分别为300代、350代、400代和430代,遗传算法的稳定代数分别为380代、420代、495代和525代。故可以得出,量子遗传算法的收敛性优于遗传算法,尤其随着种群数量的增大,这种快速收敛性的优势更加明显。再对表2进行分析,在相同种群数量条件下,量子遗传算法的运算时长较之遗传算法也具有明显优势,特别随着种群数量的增大,量子遗传算法的运算时长增长幅度较小,运算效率较高。因此,量子遗传算法在收敛性和运算效率方面存在明显优势,故更加适合航空作战条件下频率动态分配的现实需求。

6 结束语

本文提出一种基于量子遗传算法的航空通信频率动态分配方法,主要结论如下:

(1)通过对频率动态分配思路进行分析,构建了频率动态分配框架,给出了频率动态分配的具体流程;

(2)对航空通信频率动态分配问题进行分析,定义了航空通信频率动态分配约束条件,构建了航空通信频率动态分配场景;

(3)通过运用量子遗传算法和遗传算法对不同种群数量条件下的频率动态分配问题进行计算分析,验证了量子遗传算法的优越性,进一步验证了航空通信频率动态分配模型的科学性和有效性,为军事航空频率管控有效实施提供了较好的技术支撑。

[1] HOLLAND J H.Adaptation in Nature and Artificial Systems [M].Ann Arbor:The University of Michigan Press,1975.

[2] 于江,张磊,沈刘平,等.一种基于遗传算法的战场频率分配方法[J].电讯技术,2011,51(7):90-96. YU Jiang,ZHANG Lei,SHEN Liuping,et al.A Battlefield Frequency Assignment Method Based on Genetic Algorithm[J].Telecommunication Engineering,2011,51 (7):90-96.(in Chinese)

[3] 喻歆.采用种群迁移策略的战场频率动态分配[J].电讯技术,2014,54(3):348-354. YU Xin.Dynamic Frequency Assignment Based on Immigrant Schemes in Battlefield Environment[J].Telecommunication Engineering,2014,54(3):348-354.(in Chinese)

[4] 罗林,陈砚圃,张长青,等.基于多信号干扰的无线电台频率指配算法[J].现代电子技术,2015,38(5):39-42. LUO Lin,CHEN Yanpu,ZHANG Changqing,et al.Radio station frequency assignment algorithm based on interference of multiple signals[J].Modern Electronic Technique,2015,38(5):39-42.(in Chinese)

[5] NARAYANAN A,MOORE M.Quantum-inspired genetic algorithms[C]//Proceedings of 1996 IEEE International Conference on Evolutionary Computation.Nagoya,Japan:IEEE,1996:61-66.

[6] HAN K H,KIM J H.Genetic quantum algorithm and its application to combinatorial optimization problem[C]// Proceedings of 2000 International Congress on Evolutionary Computation.La Jolla,CA:IEEE,2000:1354-1360.

[7] HAN K H,KIM J H.Quantum-inspired evolutionary algorithm for a class of combinatorial optimization[J].IEEE Transactions on Evolutionary Computation,2002,6(6): 580-593.

[8] ZHANG G X,JIN W D,HU L Z.A noval parallel quantum genetic algorithm[C]//Proceeding of 4th International Conference on Parallel and Distributed Computing,Applications and Technologies.Taipei:IEEE,2003:693-679.

[9] CHEN H,ZHANG J H,ZHANG C.Chaos updating rotated gates quantum-inspired genetic algorithm[C]//Proceedings of 2004 International Conference on Communications,Cuircuits and Systems.Chengdu:IEEE,2004:1108-1112.

[10] WANG L,TANG F,WH H.Hybrid genetic algorithm based on quantum computing for numerical optimization and parameter estimation[J].Applied Mathematics and Computation,2005,171(2):1141-1156.

[11] LI P C,LI S Y.Quantum-inspired evolutionary algorithm for continuous spaces optimization based on Bloch coordinates of qubits[J].Neurocomputing,2008,72: 581-591.

[12] AARDAL K I,HOESEL S M,MANNINO K C.Models and solution techniques for frequency assignment problems[J].Quarterly Journal of the Belgian,French and I-talian Operations Research Societies,2003(4):134-135.

[13] 寇明延,赵然.现代航空通信技术[M].北京:国防工业出版社,2011. KOU Mingyan,ZHAO Ran.Modern Aeronautical Communications Technology[M].Beijing:National Defense Industry Press,2011.(in Chinese)

[14] 翁木云,张其星,谢绍斌,等.频率管理与监测[M].北京:电子工业出版社,2009. WENG Muyun,ZHANG Qixing,XIE Shaobin,et al. Spectrum Management and Monitoring[M].Beijing: Eletronics Industry Press,2009.(in Chinese)

[15] 王强.频率管理关键技术——频率分配算法研究[D].北京:北京交通大学,2009. WANG Qiang.Key Technique of Spectrum Management—Research on Frequency Assignment Algorithms[D].Beijing:Beijing Jiaotong University,2009.(in Chinese)

[16] 陈浩.遗传算法在频率分配问题中的应用研究[D].北京:北京交通大学,2009. CHEN Hao.The Application of Genetic Algorithm in the Frequency Assignment Problem[D].Beijing:Beijing Jiaotong University,2009.(in Chinese)

XU Xuefei was born in Xi′an,Shaanxi Province,in 1986.He is currently working toward the Ph.D.degree.His research concerns aeronautical communication spectrum management and control.

Email:xxf19861128@sina.com

李建华(1965—),男,陕西白水人,2006年获博士学位,现为教授,主要研究方向为空天信息系统规划与建设;

LI Jianhua was born in Baishui,Shaanxi Province,in 1965. He received the Ph.D.degree in 2006.He is now a professor. His research concerns space information system planning and construction.

沈 迪(1986—),男,浙江德清人,2014年获博士学位,现为讲师,主要研究方向为空天信息系统规划与建设;

SHEN Di was born in Deqing,Zhejiang Province,in 1986. He received the Ph.D.degree in 2014.He is now a lecturer. His research concerns space information system planning and construction.

郭 蓉(1990—),女,陕西咸阳人,2014年获硕士学位,现为助理工程师,主要研究方向为电磁场与微波技术。

GUO Rong was born in Xianyang,Shaanxi Province,in 1990.She received the M.S.degree in 2014.She is now an assistant engineer.Her research concerns electromagnetic field and microwave technology.

Dynamic Aeronautical Communication Frequency Assignment Based on Quantum Genetic Algorithm

XU Xuefei1,LI Jianhua1,SHEN Di1,GUO Rong2
(1.Information and Navigation College,Air Force Engineering University,Xi′an 710077,China; 2.Unit 95983 of PLA,Jiuquan 732750,China)

For more efficient aeronautical communication frequency assignment,a method for dynamic aeronautical communication frequency assignment based on quantum genetic algorithm(QGA)is proposed. Through analyzing the thought of dynamic frequency assignment,the architecture of dynamic frequency assignment is constructed,then a flow chart for it is given.On this basis,the dynamic aeronautical communication frequency assignment problems are discussed,the constraint condition for dynamic frequency assignment is defined,and then the dynamic aeronautical communication frequency assignment model is established.Finally,the QGA and genetic algorithm(GA)are used to simulate the same examples and the result shows that the QGA has more advantages in population fitness and convergence rate,and the dynamic frequency assignment model can dynamically adjust fitness under the condition of different populations. The method meets the practice and application requirements of dynamics,accuracy and timeliness for aeronautical communication frequency assignment.

aeronautical communication;dynamic frequency assignment;quantum genetic algorithm

Project Supported by the National Social Science Fund and the Military Science(12GJ003-130);Project Supported by Military Science Fund for Graduate Students(2013JY-505)

date:2015-06-29;Revised date:2015-09-15

国家社科基金暨军事学资助课题(12GJ003-130);全军军事学研究生资助课题(2013JY-505)

**通讯作者:xxf19861128@sina.com Corresponding author:xxf19861128@sina.com

TN92

A

1001-893X(2015)12-1311-07

徐雪飞(1986—),男,陕西西安人,现为博士研究生,主要研究方向为航空通信频谱管理与控制;

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

徐雪飞,李建华,沈迪,等.基于量子遗传算法的航空通信频率动态分配[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.]

2015-06-29;

2015-09-15