于 江,张 磊,沈刘平,秦爱祥,王春岭

(1.解放军73691部队,南京 210014;2.解放军理工大学 通信工程学院,南京 210007;3.解放军73681部队,南京 210042)

1 引 言

未来高科技条件下的局部战争,将向着“陆、海、空、天、电”五维一体的空间立体式方向发展,而与之相配套的电子信息技术的不断更新及其在军事领域中的广泛应用,使得大量电子装备被投入到战场中,遍及指挥通信、情报侦察、武器制导、预警探测、导航定位等多种领域[1],涉及地面、海上、空中和特种作战力量及各种武器系统。

在这纷繁的战场环境下,众多用频装备对有限的频谱资源展开了激烈的争夺,导致战场电磁环境异常复杂。因此,对于作战部队来说,怎样才能掌控好所配备的用频装备,进一步提高频率资源的使用效率,就成为亟待解决的问题。基于此,本文提出了一种以遗传算法为核心的启发式战场频率分配方法,并对具体的频率分配过程进行模拟仿真,然后采用3种选取策略对生成的频率分配结果进行质量评估,以便向作战用频单位提供比较优化的频率分配方案。

2 遗传算法的原理及其应用

2.1 遗传算法的基本原理

遗传算法(Genetic Algorithm,GA)的操作对象是群体,群体由若干个体组成,个体的具体特征又是由组成个体的一条基因链决定。群体经过多次选择、交叉、变异操作后,可以得到质量越来越高的个体[2]。遗传算法的基本运作流程如图1所示。

图1 遗传算法的基本流程Fig.1 The basic flow of Genetic Algorithm

遗传算法是一种不依赖于具体问题的直接搜索方法,其主要目的是借助生物进化中的“适者生存”规律来说明自然和人工系统的自适应过程,适合数值求解那些带有多参数、多变量、多目标和多区域,但连通性较差的NP-Hard优化问题[3]。目前,遗传算法在模式识别、神经网络、图像处理、机器学习、工业优化控制等方面都得到了广泛应用,在频率分配技术领域中,也有很多成功的应用案例,这为遗传算法在战场频率分配中的应用铺平了道路。

2.2 遗传算法在战场频率分配领域中的应用

在战场电磁环境下的频率分配算法中,任何一个频点(信道)就是一个基因,所有频点按照一定顺序排列成一条基因链就组成了一个个体,每个个体都反映出战场上按地理环境划分的某一个小区域的频率分配情况,若干个体再组成一个群体,这就是所研究的整个战场电磁环境(在后期算法的描述中把它定义为“研究空间”)。初始群体是随机产生的,它是一个以频率分配方案为参考对象的基因组库(在后期算法的描述中把它定义为“样本空间”),后代的群体则是由这个基因组库中择优选取的父体和母体通过交叉、变异产生的[4]。算法终止的评判标准有3种:一是得到了所求解;二是遗传到了一定的代数;三是经过若干代后,适应度一直没有变化。算法输出的结果是一个最优频率分配方案。

3 启发式战场频率分配算法

将遗传算法应用到战场频率资源分配领域,并形成符合战场电磁环境具体特点和实际需求的启发式频率分配算法,需要考虑如下几个方面的问题。

3.1 战场频率分配算法的约束条件

通常,军用通信系统的频率分配问题可以表述为:对于给定的一组无线发射机,找到一种受干扰最小的频率配置方案,满足所有的频率约束关系。这些约束一般分为两类:操作约束和电磁约束。前者随着具体问题不同而不同,而后者可以用有用信号的最低信噪比或最大允许的干扰噪声比来衡量。根据实际系统要求,这类约束又可以细分为同信道约束、邻道约束和共址约束[5]3种情况。

(1)同信道约束

同信道约束(Co-channel Constraint,CCC)是指为了避免同频干扰,分别处于不同位置的一对发射机不能分配相同的频率,除非它们相隔足够远的距离。设fi和fj是分配给发射机i和j的频率,则同信道约束要求满足如下条件:fi≠fj。

(2)邻道约束

邻频干扰是指一对发射机即使工作频率相隔几个信道,仍然可能造成相互之间干扰的情形。邻道约束(Adjacent-channel Constraint,ACC)就是为了避免邻频干扰,发射机之间至少要间隔m个频道,即满足如下条件:︱fi-fj︱>m。

(3)共址约束

共址约束(Co-site Constraint,CSC)是指同一个小区分配的信道之间必须有一个最小的频率间隔。具体地说,就是处于相同位置的发射机为了保证能够正常工作,必须间隔 m个信道的频率,即满足如下条件:︱fi-fj︱≥m。

3.2 战场频率分配算法的数学模型

(1)频率分配方案矩阵F[6]

频率分配方案矩阵F采用二进制的编码方式,F矩阵由n×m个元素组成,其中n是待规划的小区数目,m则是可以使用的频点个数。

F矩阵中每一个元素fik的取值由式(1)决定:

当确定了频率分配方案矩阵F以后,位于战场环境下的各个小区就可以按照该矩阵中各行划分的特定信道来部署所在地域的作战用频装备。

(2)电磁兼容矩阵 C

结合3.1节涉及到的3个干扰约束条件,这里引入电磁兼容(EMC)矩阵C。假设某一战场环境的电磁空间被划分成了n个小区,一般可用一个n×n的对称矩阵C来描述EMC,表现形式如下:

C矩阵中的每个元素cij表示了i小区和j小区所分配的频点集合间最小的频率间隔[7]。由此可以看出,在 C矩阵中,对角线上的元素cii代表同一小区所分配频点的最小频率间隔,即CSC约束;同理,cij=1表示CCC约束,即小区i中的频率fi和小区j中的频率fj是不可以相等的,它们之间的频率间隔至少为1;而cij=2则表示ACC约束,即小区i中的频率fi和小区j中的频率fj不可以相邻,它们之间的频率间隔至少为2。对于可以复用同一频率的两个小区,cij=0,即小区 i中的频率fi和小区j中的频率fj可以相等。

另外,还涉及到频点(信道)需求数组

数组中的元素a1,a2,…,an分别对应第1,2,…,n个小区实际需要的频点个数。

3.3 战场频率分配算法的具体构造

战场频率分配算法的实现主要通过对遗传算法加以改进来实现,也就是说该算法中同样会涉及到适应度函数生成、选择操作、交叉操作以及变异操作等基本步骤。下面对算法的设计进行详细说明。

(1)战场频率分配算法的适应度函数

结合频率分配算法的具体特点,可以设置出如下的适应度函数,分别拿需求数组needarray[n]中的每个元素值(即某一小区实际需要的频点数)与样本空间(即前面提到的频率分配方案基因库)中的各个个体中1的个数进行比对,若两者在数值上越接近,即它们的差值越小,则认为该个体的适应度越高。因此,适应度函数的具体形式为

式中,fitness(j)为样本空间中第j个个体的适应度值,ind-length为样本空间中各个个体的总长度,needarray[i]为第 i个小区实际需要的频点数,value(j)为样本空间中第j个个体中1的个数。

(2)战场频率分配算法的选择操作

战场电磁环境下的频率分配算法采用适应度比例选择方式来进行个体的选择,在该方法中,每个个体的选择概率与其适应度成正比。

设种群规模为N,种群中第i(i=1,2,…,N)个个体的适应度为fi,则第i个个体的选择概率pi如式(3)所示:

(3)战场频率分配算法的交叉操作

由于频率分配算法操作的对象和输出的结果是一个个频率分配方案,即每个个体中1的个数等于所分配的频点数,所以在交叉过程中如果改变了原有个体的结构而使个体中1的个数变多或变少,将导致算法给出的频率分配方案出现信道闲置或无法满足用频需求,这显然不是期望看到的结果。

为确保交叉操作后每行个体中l的个数固定不变,算法提出一种调整措施对遗传算法的基本交叉操作加以改进。具体步骤如下:假设A和B是两个待交叉父体,并且有一个后进先出的堆栈,As、Bs代表两个父体染色体的第s位上的数值,若As、Bs两位相异,则暂时先不互换这两位,而是把它们放到堆栈中存储起来,然后继续搜索A和B的后续位,若发现还存在 Ai、Bi这对相异位,且 As和Ai也是相异的,则同时交换 As、Bs和Ai、Bi两组基因位,这样就可以确保A和B两个个体在交叉操作以后仍能保证个体中l的个数固定不变。

(4)战场频率分配算法的变异操作

同样,这里也不希望遗传算法的变异操作破坏原有频率分配方案个体在信道容量上的稳定性,为确保变异操作后每个个体中1的个数固定不变,就必须采用特殊的变异方法。具体步骤如下:根据给定的变异概率决定一行个体基因序列的某一位s是否发生变异,如果是,则在同一行选取另外一个随机位i,假设这两位也是相异的,就将s和i直接交换,否则不交换,从而达到变异的效果。这与传统遗传算法0、1互换的变异模式有所不同。

3.4 战场频率分配算法分配结果的代价评估[8]

经3.2节定义,F矩阵代表一组频率分配方案。第i行元素的和,即代表小区i所分配到的信道总数,设di为i小区实际需要的频点数,那么如果这种频率分配方案违背了该设计,则会造成以下代价:

式中,q为小区i的待分配频点。

其次,用F矩阵来对照给定的C矩阵可得到以下结论:对于CSC,假设以待分配频点q与被分配给了小区i的已有频点p为研究对象,如果p与q之间的间隔小于cii,即,那么根据CSC约束,频点q就不能被分配给i小区,否则就会造成如式(5)的代价:

注意这里的频点 p、q仅用来标识实际分配到小区i中的两个频点(应有其具体的数值)在F矩阵中的位置,通过查找 F矩阵,可以知道这两个频点的频率间隔是否满足上面所述的约束条件。

同理,对于CCC和ACC,假设频点p已经分配给了i小区,频点q等待分配给j小区,如果根据 C矩阵,cij>0(i≠j),那么一旦p与q之间的间隔小于cij,即,根据CCC或者ACC,频点q就不能分配给小区 i,否则就会造成以下代价:

综上所述,对于某个频率分配方案,都能产生一个F矩阵,衡量这个 F矩阵优劣的标准可以综合考虑上述各种代价,得到函数

式中,α、β、γ分别为第i个小区的同信道/邻道约束(CCC&ACC)、共址约束(CSC)和需求差异因素的权重。对于不同的战场环境,这三个方面的因素对代价函数所造成的影响各不相同,因此,需要根据实际情况对α、β、γ进行合理配置。

4 案例仿真与方案效能评估

假设围绕某作战地域,频管部门根据己方用频装备的部署情况将战场划分为4个面积相等的小区域,如图2所示。与此同时,分别处在4个小区中的作战部队向频管部门提出用频需求,且所有的用频申请都集中在频率范围为Fmin～Fmax的有限频段内,根据当前频段的无线电业务类型,现将频段Fmin～Fmax分成若干个等间隔的小信道,假定划分为10个信道。在经过战场电磁环境测试的辅助决策以后,频管部门就可以生成频率需求数组needarray[4]={8,3,9,4}(为简化算法实现的复杂性,needarray[4]中的4个元素值为随机产生的数值)。

图2 战场环境下的小区划分示意图Fig.2 The sketch map of cell partition in battlefield environment

此时,通过对战场监测分队上报的重点频段(Fmin～Fmax)监测数据进行数学分析和计算,并结合己方用频部队上报的干扰申诉情况,可以生成电磁兼容矩阵 C。在本课题中,算法随机生成一个4×4的矩阵,用来反映各小区间的干扰情况。

另外,还有存储频率分配方案的样本空间群体,算法中也是随机生成一个10×10的二进制矩阵,作为频率分配方案的初始化提取库。这里需要注意,由于样本空间的群体规模比较小,为了能够快速搜索到最优分配方案,算法在进行遗传代数循环时,每一代都会重新生成随机样本空间群体,这与传统遗传算法只对选择、交叉、变异操作进行遗传代数循环有所差异。

有了频率需求数组needarray[4]、电磁兼容矩阵C以及初始化样本空间群体,再结合战场频率分配算法,就可以迅速给出比较理想的频率分配方案矩阵F。算法的实现采用C++语言,通过n代循环,可以得出n个不同的频率分配方案,再借助代价函数C(F)对这些频率分配方案进行质量评估,选择其中代价最小的那个方案作为最终分配方案下发给频率使用单位。本课题将通过3个实验对不同选择策略的频率分配方案进行性能比较。

4.1 代价函数权值完全相同的分配方案选取策略

利用频率分配算法产生200个频率分配方案矩阵F,再选取3.4节中定义的代价函数 C(F)对这200个频率分配方案进行代价评估,显然当权值 α、β、γ选择不同的数值时,C(F)所反映的频率分配方案的代价信息是不同的。首先令 α、β、γ均为1,来看一下这些频率分配方案的代价分别为多少,并给出频率分配方案在算法遗传了100代和遗传了200代以后的代价分布情况,如图3和图4所示。

图3 算法执行100代后得出的代价最小频率分配方案(α=β=γ=1)Fig.3 The smallest cost of frequency assignment project after the algorithm has been executed for 100 generations(α=β=γ=1)

图4 算法执行200代后得出的代价最小频率分配方案(α=β=γ=1)Fig.4 The smallest cost of frequency assignment project after the algorithm has been executed for 200generations(α=β=γ=1)

对照图3和图4不难得出以下结论:

(1)随着遗传代数的增加,该分配算法可以产生代价更小的频率分配方案,如图中显示在算法执行了100代以后产生的最优频率分配方案代价为68,200代以后产生的最优频率分配方案代价为51,后者的代价比前者更小。

其中,第134代结果为最优频率分配方案:

该矩阵需求约束的代价为13,CSC的代价为10,CCC和ACC的代价为28,总代价 C(F)值为51。

(2)矩阵F134各行中1的个数反映了该频率分配算法分配给每个小区的信道数,比如第1区分得2个频点(2<8)、第2区分得3个频点、第3区分得3个频点(3<9)、第4区分得3个频点,这与频率需求数组needarray[4]={8,3,9,4}显示的各小区实际需求的频点数有巨大差异。

也就是说,采用 α、β、γ均为1的代价评估策略得到的最优频率分配方案是以降低频点使用量为代价来减少干扰影响的。显然,这违背了信息化条件下的现代战场上电子装备的使用密度越来越大的总趋势,因此,必须加大对需求约束的代价权重。

4.2 增强型需求约束代价的分配方案选取策略

为避免出现前一节中选择的频率分配方案给出的各小区频点容量过低的问题,本次试验中将代价函数的权值分别设置为 α=1、β=1、γ=100,以提高需求约束对方案选取的影响效果,这样就得出了如图5所示的代价分布结果。

图5 算法执行200代后得出的代价最小频率分配方案(α=β=1,γ=100)Fig.5 The smallest cost of frequency assignment project after the algorithm has been executed for 200 generations(α=β=1,γ=100)

其中,第191代结果为最优频率分配方案:

该矩阵需求约束的代价为3,CSC的代价为72,CCC和ACC的代价为180,总代价值 C(F)为552。

在矩阵F191各行中1的个数(第1区分得8个频点、第2区分得4个频点、第3区分得8个频点、第4区分得 5个频点)基本与频率需求数组needarray[4]={8,3,9,4}中的对应数值相当,所以在需求约束方面,该频率分配方案取得的效果是不错的(3<13)。但是由于提高了各小区的频点供应量,使得小区间干扰陡然增高,比如矩阵F191的CSC代价为72,远高于前一节中的10;CCC和ACC的代价为180,远高于前一节中的28。因此,对于权值 α、β、γ的处理,应该科学设置以便均衡这三方面代价对频率分配方案选择的影响。

4.3 均衡型代价的分配方案选取策略

基于权值的均衡性考虑,本次试验做如下处理:

(1)确定频率分配算法在执行了200代以后,给出的200个频率分配方案的相应需求约束、CSC,以及CCC和ACC的代价数值;

(2)确定这三者之间的比例关系(1∶a1∶b1,1∶a2∶b2,…,1∶a200∶b200);

(3)对需求约束与CSC的代价比例值做一个均方根得到值a,对需求约束与CCC/ACC的代价比例值也做一个均方根得到值b,如式(8)所示,这样就产生了一个最终的均方根比例值1∶a∶b[10];

(4)最后对得到的均方根比例1∶a∶b取最小公倍数,从而确定 α、β、γ的最终分配关系(α=1×a,β=1×b,γ=a×b)。

经过上述处理以后,得到均方根比例1∶a∶b=1∶6.80∶16.06,则实际代价函数的权值就设置为 α=6.8、β=16.06、γ=109.208,这样就得出如图6所示的代价分布结果。

图6 算法执行200代后得出的代价最小频率分配方案(α=6.8,β=16.06,γ=109.208)Fig.6 The smallest cost of frequency assignment project after the algorithm has executed for 200 generations(α=6.8,β=16.06,γ=109.208)

为了验证本策略的均衡性所在,这里首先列出其中的最优频率分配方案矩阵:

该矩阵需求约束的代价为7,CSC的代价为28,CCC和ACC的代价为76,总代价值为1730.94。

现将该策略(策略3)所付出的这3个代价值分别与4.1节中的策略(策略1)、4.2节中的策略(策略2)产生的最佳频率分配方案所付出代价的对应值进行比较,可以得出如表1所示的比较结果。

表1 3种策略之间的代价对比情况Table 1 Cost contrast of three strategies

从表1可以看到,策略3的需求约束代价介于策略1和策略2之间,比策略1小,比策略2稍大;而策略3的CSC约束代价以及CCC和ACC约束代价也介于策略1和策略2之间,比策略2小,比策略1稍大。实验得到预期结果,可将F189作为最终分配方案下发给作战用频单位。

5 结 语

战场频谱资源科学分配是现代战争中作战决策部门必须考虑的重要环节,而战场频谱分配效率的高低将直接影响作战方案中各个进程的有效实施,对最后战争的成败意义深远。本文以传统的遗传算法为基础,结合战场电磁环境的具体特点,对其进行改进优化,最后生成启发式战场频率分配算法,并对采用不同策略得出的频率分配结果进行代价评估。仿真结果表明,采用均衡型权重配置的评估策略选择出来的频率分配方案相对比较理想,但仍需结合实际战场电磁环境所反映的不同特性,进一步研究频率分配算法的优化问题,以及分配方案选取的科学性问题。

[1] 李楠,张雪飞.战场复杂电磁环境构成分析[J].装备环境工程,2008,5(1):16-19.LI Nan,ZHANG Xue-fei.Constitution Analysis of Complicated Electromagnetic Environment in Battlefield[J].Equipment Environmental Engineering,2008,5(1):16-19.(in Chinese)

[2] Karen I Aardal.Models and solution techniques for frequency assignment problems[EB/OL].Maastricht:Maastricht research school of Economics of Technology andOrganization in its series,2003[2010-07-23].http://ideas.repec.org/p/dgr/umamet/2002002.html.

[3] 司小江.数据链规划技术的研究[D].南京:解放军理工大学,2003:12.SI Xiao-jiang.The Research of Tactical Data Link Planning Technique[D].Nanjing:PLA University of Science and Technology,2003:12.(in Chinese)

[4] 古邦伦.电磁频谱管理中的频率分配技术研究[D].长沙:国防科学技术大学,2006:5.GU Bang-lun.The Research of Frequency Assignment in Frequency Spectrum Management System[D].Changsha:National University of Defense Technology,2006:5.(in Chinese)

[5] 贺志强,牛凯,林雪红,等.频率分配与管理算法研究[C]//2007年通信理论与信号处理学术年会论文集.北京:电子工业出版社,2007:427-433.HE Zhi-qiang,NIU Kai,LIN Xue-hong,et al.The Study of Algorithms for Frequency Assignment and Management[C]//Proceedings of 2007 Annual Conference on Communication Theory and Signal Processing.Beijing:Publishing House of Electronics Industry,2007:427-433.(in Chinese)

[6] 章春芳,陈陵,陈娟.求解频率分配问题的自适应的多种群蚁群算法[J].小型微型计算机系统,2006,27(5):837-841.ZHANG Chun-fang,CHEN Ling,CHEN Juan.Solving Frequency Assignment Problem Using an Adaptive Multi Colony Ant Algorithm[J].Mini-Micro Computer Systems,2006,27(5):837-841.(in Chinese)

[7] 薛学猛.一种面向工程应用的启发式频率分配算法研究与应用[D].北京:北京邮电大学,2008:2.XUE Xue-meng.Research and Application of An Engineering-Oriented Heuristic Algorithm for Frequency Assignment[D].Beijing:Beijing University of Posts and Telecommunications,2008:2.(in Chinese)

[8] 谢珊.遗传算法在无线频率规划的应用[D].广州:中山大学,2007:9.XIE Shan.The Genetic Algorithm Application of The Wireless Frequency Plan[D].Guangzhou:SUN Yat-sen University,2007:9.(in Chinese)