基于遗传算法的短波分集通信网频率规划研究

Research on Frequency Planning of HF Diversity Communication Network Based on Genetic Algorithm

摘要: 短波分集通信网采用多个频率保障用户通信，以提高接收可靠性。当前，其采用“先到先得、用后释放”的方式为用户通信提供频率保障。在多用户并发接入时，存在频率资源消耗过大和频率资源浪费问题。本文提出对短波分集通信网频率资源进行规划，以满足给定用户需求情况下使用最少频率为优化目标进行建模，并利用遗传算法对模型进行求解。仿真结果表明，采用遗传算法对用户进行频率规划比“先到先得、用后释放”的方式具有更高的频率利用效率，证明了短波分集网服务大量用户时采用频率规划的必要性。

Abstract: HF diversity communication network adopts multiple frequencies to support user communication, in order to improve the reliability of receiving. At present, it adopts the method of “first come, first served, release after use” to provide a frequency guarantee for user communication. When multiple users access concurrently, there are problems of excessive consumption and the waste of frequency resources. In this paper, we propose the frequency resource planning of HF diversity communication network and model the optimization goal using the least frequency to meet the given user’s needs, and a genetic algorithm is used to solve the model. The simulation results show genetic algorithm has higher frequency utilization efficiency than the “first come, first served, release after use” method, which proves the necessity of frequency planning when the HF diversity network serves a large number of users.

1. 引言

短波通信是一种依靠电离层反射实现无中继远程通信的通信方式，而短波分集通信网是一种引入分集接收技术的短波通信网，它可将传统通信模式下的“点对点”快速衰落变参信道，转变为“多点对一点”或“一点对多点”的准恒参信道，大幅缓解由信道衰落带来的不利影响，提高信道可靠性[1] [2]。

但是，短波分集通信网主要采用“先到先得、用后释放”的方式为用户通信提供频率保障(以下简称无规划方式)，当大量用户并发接入时，这种方式存在频率资源消耗过大和频率资源浪费问题。本文研究多用户情况下频率规划对频率资源消耗的影响，以满足给定用户需求情况下使用最少频率为优化目标，通过建模仿真验证短波分集通信网频率规划的必要性。

2. 短波分集通信网现有频率保障方式

无规划方式为用户通信提供频率保障的具体保障流程如图1所示¹：如需接入一个保障用户，第一步，网络要从频率资源库里面随机选择一个(或多个)可用频率，若该频率(或频率集)已被占用，则再次进行随机选择，若该频率空闲，则直接分配给用户；第二步，检查该频率(或频率集)保障下的用户通信是否畅通，即用户接收到的信号信噪比(SNR))值是否满足通信基本阈值，若不满足，则继续转入第一步，通过随机选择的方式，增加一个保障频率(或频率集)，若满足，则终止选择。

基于这种保障方式，在固定频率资源和接入用户数量的情况下，可能会存在两类问题：假设短波分集通信网计划分配7台发信机来保障4个用户，已知用户1~4的最佳频率保障方案如图2所示。若采用无规划方式，第一，可能会发生频率资源消耗过大的问题，如图3所示。图中，4个用户同时接入，从用户1开始进行频率分配，可能会出现用户1和用户2过度占用频率资源，导致用户3和用户4无法得到足够的频率保障，若要保障需要消耗额外的其它频率资源。第二，可能会发生频率资源浪费的问题，如图4所示。图中，虽然4个用户都得到了足够的频率保障，但是比最佳方案多消耗了3台发信机和3个可用频率，导致频率资源浪费。基于上述分析，本文提出对短波分集网进行频率规划，即统一为用户分配频率，来提升频率利用效率，避免资源浪费。

Figure 1. Diagram of enabling process of unplanned mode

图1. 无规划方式保障流程示意图

Figure 2. Diagram of support plan of optimum frequency

图2. 最佳频率保障方案示意图

3. 短波分集通信网多用户保障频率规划建模

为研究短波分集通信网频率规划问题，本文以满足给定用户需求情况下使用最少频率为优化目标构建模型。首先设定该短波分集通信网含Num台发信机，需要保障的用户数量为K个，保障一个用户分配的最大发信机数量为N台，则短波分集通信网频率保障方案可以表示为：

$S=\left[\begin{array}{cccc}{T}_{11}& T_{12}& \cdots & T_{1N}\\ T_{12}& T_{22}& \cdots & T_{2N}\\ ⋮& ⋮& \ddots & ⋮\\ T_{K1}& T_{K2}& \cdots & T_{KN}\end{array}\right]$

其中，矩阵的第i行$\left\{T_{i1},T_{i2},T_{i3},\cdots ,T_{iN}\right\}$ 表示用于保障第i个用户的全部发信机，$T_{ij}$ 为对应发信机的序号，$i\in \left\{1,2,\cdots ,K\right\}$ ，$j\in \left\{1,2,\cdots ,N\right\}$ ，$T_{ij}\in \left\{1,2,\cdots ,Num\right\}$ 。

Figure 3. Diagram of the excessive consumption of frequency resources

图3. 频率资源消耗过大示意图

Figure 4. Diagram of the waste of frequency resources

图4. 频率资源浪费示意图

为便于模型求解，做如下假设：

假设1：点对点链路间均取某个固定不变的可用频率作为发射频率，且不同点对点链路间的可用频率不同；

假设2：将用户和发信机所在区域划分为区域格，区域格内距离较近的用户和发信机的频率可用性信息设定为同一信息(如方圆10公里范围内)；

假设3：每台发信机使用的发射频率之间不发生任何频率干扰，即不发生同频干扰、邻频干扰和互调干扰²。

通过以上假设条件，对每个用户来说，每台发信机唯一对应该用户的一个可用频率，选好了发信机也就等于选好了其对应的可用频率，这样可以将频率、发信机的联合资源调度简化为发信机资源调度。于是，短波分集通信网频率规划问题可以转化为如下组合优化问题：

$\begin{array}{l}\underset{S}{\min }f\left(S\right)=\underset{S}{\min }{\displaystyle \sum _{i=1}^K{\displaystyle \sum _{j=1}^{N}I\left(T_{ij}\ne 0\right)}}\\ \text{s}\text{.t}.,\forall i\in \left\{1,2,\cdots ,K\right\},都有{\displaystyle \sum _{j=1}^{N}SN{R}_{ij}}\ge SNR{t}_i,\\ \forall a,b\in \left\{1,2,\cdots ,K\right\},c,d\in \left\{1,2,\cdots ,N\right\},\\ 都有若T_{ac}=T_{bd}\ne 0,�a=b,c=d.\end{array}$

其中，$f\left(S\right)={\displaystyle \sum _{i=1}^K{\displaystyle \sum _{j=1}^{N}I\left(T_{ij}\ne 0\right)}}$ 为要优化的目标函数，表示S矩阵中不为0的个数(即给定用户数情况

下的频率消耗数量)，$SN{R}_{ij}$ 为使用编码为$T_{ij}$ 的发信机保障第i个用户时得到的SNR值，$SNR{t}_i$ 为第i个用户的SNR接收门限值，本文设定为固定值65 dB (可以满足绝大部分通信设备的通信要求)。两个约束条件要求：1) 必须确保每个用户通过分集接收后接收到的信号SNR值满足通信基本需求；2) 必须确保每台发信机至多只保障一个用户通信。

因为频率规划问题属于NP完全问题(可以在不确定性的多项式时间内找到答案，并且能在多项式时间内转化为另一个NP问题)，解空间随着用户和台站的增多呈指数级增长[3]，所以对于这类问题，通常采用启发式智能算法进行求解。目前常见的启发式智能算法有遗传算法、模拟退火算法、蚁群算法、粒子群算法、禁忌搜索等。

其中，模拟退火算法更适用于大型组合优化问题[4]，文献[5]通过模拟退火算法实现战场频率资源分配，该算法虽然能从绝大多数局部点中脱离出来，但导致了过多的无用迭代和求解效率低下；蚁群算法更适用于旅行商问题[6]，文献[7]将蚁群算法应用于解决海战场的频率分配问题，但蚁群算法往往会陷入局部优化，导致收敛时间过长；粒子群算法常用于研究粒子的个体性与群体性之间的关系，其概念简单直观，收敛速度快，但容易陷入局部寻优[8] [9]；禁忌搜索的优化过程在一定程度上受到初始解、邻域结构和禁忌属性的影响[10] [11]，而频率规划问题本质上是一个全局搜索最优解的问题，关键点是一定要能够找到可行解，在搜索过程中，既要保证优解能够保留，又要保证新解和劣解的存在和随机更新，不至于陷入局部最优，所以本文选用典型的遗传算法进行求解[12] [13]，遗传算法是模仿自然界优胜劣汰的一种高效、并行、全局搜索的优化方法，它的特点是能在搜索过程中自适应地控制搜索过程以求得最优解。文献[14]-[19]也同样表明，通过遗传算法可以有效解决频率分配方面的问题。

4. 短波分集通信网频率规划问题模型求解

利用遗传算法对模型求解的基本步骤为：

1) 种群初始化：随机生成一个初始数量为NIND的K × N维S矩阵种群G；

2) 适应度计算：首先，将种群G中K × N维的S矩阵转换为K × Num维的0~1矩阵种群H，然后，

对种群H制定统一的惩罚函数$v\left(S\right)={\displaystyle \sum _{i}Num\ast {\left[v_i\left(S\right)\right]}^2}$ ，其中$i\in \left\{1,2,\cdots ,K+Num\right\}$ ，$v_i\left(S\right)$ 为违反第i个

约束条件的程度，违反约束条件越多、程度越大的个体，惩罚函数值就越大，定义适应度函数$r\left(S\right)={\left\{Num/\left[f\left(S\right)+v\left(S\right)\right]\right\}}^4$ ，计算种群H中每个个体的适应度；

3) 执行遗传算子：对H矩阵种群按照适应度大小和轮盘赌规则进行重新选择，再按照一定的概率参数和随机位置进行交叉和变异，得到新的K × Num矩阵种群G'；

4) 记录最优解：记录新产生的G'矩阵种群中适应度函数最佳的矩阵个体M及其适应度值m，并记为精英个体；

5) 迭代运算：对新产生的G'矩阵种群按照3，4，5步骤进行迭代运算，若找出适应度函数值大于m的M矩阵精英个体，则进行记录，且更新m值，否则不记录；

6) 设定迭代终止条件：若连续迭代运算n次或者迭代运算到最大次数后，都没有再找到适应度更好的M矩阵精英个体，则认为当前适应度值m所对应的M矩阵精英个体就是模型的最优解，将最优解M矩阵再转换为相对应的S矩阵，即得到所求的短波分集通信网频率保障方案。如图5所示。

Figure 5. Diagram of the basic steps of genetic algorithm

图5. 遗传算法基本步骤示意图

5. 短波分集通信网频率规划问题仿真对比

本文仿真基于MATLAB软件进行，并利用所在团队基于ITU-RP533-12建议书(HF电路性能的预测方法)的多输入多输出频率预测程序软件计算短波通信链路SNR，可以得到每个接收机与发信机之间的最佳可用频率FOT及其对应SNR值，得到K × Num维SNR矩阵。

考虑到用户量的大小可能影响频率规划对频率资源消耗的优化效果，本文针对5种不同的用户量，仿真对比无规划方式和遗传算法之间的频率资源消耗。仿真实验环境为MATLAB软件，基本设置发信机数量Num = 90，单个用户最大保障台站数N = 3，交叉概率Pc = 0.9，变异概率Pm = 0.05，初始种群大小NIND = (K × Num)/2-1，最大迭代次数MAXGEN = NIND，即频率保障方案S越复杂，所需要的初始种群数量和最大迭代次数就越大。仿真结果如下。

当K分别为10、20、30、40、50时，通过连续20次仿真实验，结果对比如表1所示。

Table 1. Resulting data of simulation experiment

表1. 仿真实验结果数据

无规划方式
实验次数	1	2	3	4	5	6	7	8	9	10
K = 10	15	15	14	15	17	17	19	14	17	13
K = 20	29	30	31	30	34	33	31	30	31	31
K = 30	45	47	47	42	44	45	47	45	43	48
K = 40	56	60	61	62	62	60	61	57	58	65
K = 50	74	73	80	78	76	75	76	72	80	74
实验次数	11	12	13	14	15	16	17	18	19	20
K = 10	14	16	16	13	15	17	12	16	12	16
K = 20	30	27	30	29	30	32	33	28	29	32
K = 30	47	46	44	42	48	45	40	49	44	43
K = 40	63	60	62	61	57	59	61	64	62	59
K = 50	73	75	73	77	73	74	75	73	77	75
遗传算法
实验次数	1	2	3	4	5	6	7	8	9	10
K = 10	11	12	11	11	13	12	13	12	10	11
K = 20	25	24	24	22	26	25	28	25	24	24
K = 30	39	37	44	43	38	38	35	41	38	40
K = 40	50	52	49	49	47	48	51	52	50	54
K = 50	64	64	64	66	61	66	66	67	66	62
实验次数	11	12	13	14	15	16	17	18	19	20
K = 10	12	10	10	13	11	12	11	15	11	11
K = 20	23	24	23	26	23	25	25	26	21	24
K = 30	37	37	41	37	41	34	40	38	36	42
K = 40	50	56	50	50	50	52	54	50	52	54
K = 50	66	65	64	64	63	65	68	63	64	62

从表中我们可以看到，当K取5种不同的值时，绝大部分实验结果都表明无规划方式消耗的频点数比遗传算法消耗的更多，如图6所示，通过对比两种频率分配方式的平均占用频点数量，可以表明，采用遗传算法对用户进行频率分配比无规划方式占用的频点数量更少，即消耗的频率资源更少。如图7、图8所示，通过对比单个用户平均占用频点数量以及计算其优化率，可以表明，用户量的变化不改变频率规划的优越性，即用户量越大，能够节约的频率资源就越多，对短波分集通信网组织运用具有很好的实践借鉴意义。

Figure 6. Diagram of the average number of occupied frequency points

图6. 平均占用频点数量对比图

Figure 7. Diagram of the average number of frequency points occupied by single user

图7. 单个用户平均占用频点数量对比图

Figure 8. Diagram of the optimization rate of genetic algorithm

图8. 遗传算法优化率示意图

6. 小结与展望

本文主要通过分析当前短波分集通信网存在的频率资源消耗过大和频率资源浪费问题，立足于构建短波分集通信网频率规划模型，以满足给定用户需求情况下使用最少频率为优化目标，研究对比频率规划和“先到先得、用后释放”的无规划方式在消耗频率资源上的差别。为求解模型，本文采用了遗传算法，通过对比5种不同用户数量下的仿真实验结果，验证了频率规划对短波分集网用频保障的必要性和优越性。

可以看到，本文主要采用典型的罚函数遗传算法进行模型求解，仿真结果证明了频率规划对比无规划方式的优越性，但是在仿真实验过程中也发现了频率规划过程耗时较长、优化效果不佳等问题。下一步，论文还将继续研究通过改进遗传算法来求解频率规划模型，进一步缩短频率规划过程、增强稳定性、提高优化效果。同时，本文主要研究的是优化保障资源场景，构建以满足给定用户需求情况下使用最少频率为优化目标的数学模型，下一步，论文还将继续研究优化保障用户场景，构建以给定有限频率资源情况下保障最多用户数量为优化目标的数学模型，研究对比频率规划和“先到先得、用后释放”的无规划方式在保障用户数量上的差别，为短波分集通信网不同应用环境下频率保障提供参考。

致 谢

首先感谢我的指导老师徐坤老师。本文是在老师的指导和帮助下修改完成的，在此，我要向他的悉心帮助和指导表示由衷的感谢。在这段时间里，我从他身上不仅学到了专业知识，更感受到他工作中的兢兢业业和平易近人，值得我一生学习！

其次感谢我的爱人周梦柔和父母家人。感谢他们对我学业上的支持和生活上的帮助，当我工作疲惫、无心学业的时候，总能看到家人在背后默默支持鼓励，家人永远是我们温暖的港湾，在他们的帮助和督促下，我才能够全神贯注地投入到学业中，顺利完成论文写作，在此深表感谢！

NOTES

¹图1只显示了每次只规划一个频率的例子，每次规划一个频率集也可以采用类似方法；此外，无规划方式可基于频率库中的经验信息辅助选择分配频率，但依旧是采用先到先得方式。

²本文主要研究资源规划问题，暂未考虑频率干扰因素，如果考虑，只需要对可用频率进行微调或者在对规划问题求解过程中添加限制条件。