林宇生，蒋洪磊，董彦磊，耿纪昭，刘玥霄

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

基于遗传算法的通信卫星资源动态调度方法研究

林宇生，蒋洪磊，董彦磊，耿纪昭，刘玥霄

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

随着卫星通信技术的持续发展，基于卫星通信的实际应用需求也日益复杂。为了更高效地处理不同体制网系之间的资源竞争，提高通信卫星资源的利用率，更大限度地满足卫星通信任务需求，提出了一种基于遗传算法的通信卫星资源动态调度方法。介绍了卫星资源动态调度所基于的通信任务的基本约束，并结合遗传算法阐述了资源动态调度具体实施过程，通过仿真实验将通信卫星资源的动态调度使用方式与静态分配使用方式进行了对比分析。仿真结果表明，在相同任务数和不同任务数的条件下，资源动态调度的使用方式都可以达到更高的资源利用率。

通信卫星资源；动态调度；遗传算法

0 引言

近年来，卫星通信技术不但在军事领域发挥着重要的作用[1]，其商业市场的需求也不断增长[2]。随着卫星资源的日益丰富，使用情况呈现多样化的特点，对卫星通信网的运行管理也变得更加复杂[3]。目前在面向多网系、多任务共享卫星资源实际需求的条件下，采用何种有效的资源调度技术以有限的频率资源更大限度地满足通信保障任务已经成为了卫星通信中的一个需要解决的重要问题。

目前通常以通信任务的形式来对通信卫星的资源进行调度管理[4]，通信任务可以表示为在某一段特定时间内为某一些特定用户分配一定带宽的卫星频率资源。当前广泛应用的资源静态分配(或称预规划)方式将资源按需地分配给某些任务[5-6]，对于新增的任务只能在剩余可用的资源范围内予以分配，而非在全局的角度统一调度。另外静态分配方式缺乏资源回收机制，资源分配不够灵活，导致其资源利用率不高。本文采用基于生物学的遗传算法研究了一种卫星资源动态调度方法，可有效提高卫星频率资源的利用率。

1 遗传算法原理

遗传算法[7]基于模仿生物界遗传学的遗传过程，通过不断进化和迭代寻找问题的最优解，主要适用于规划类问题如工件排样[8]、波束成形[9]和路径规划[10]等，以及调度类问题如资源运用[11]、计划编制[12]和任务调度[13]等的求解。

遗传算法首先把问题的参数用基因来表示，把问题的解用染色体来表示，从而得到一个由具有不同染色体组成的群体。将这个群体放到特定的问题环境里进行生存竞争，适者有最好的机会生存和产生后代，后代随机化地继承父代的最好特征，并也在生存环境的控制支配下继续这一过程。随着进化的不断进行，群体的染色体都将逐渐适应环境，最后收敛到一组最适应环境的染色体，即得到问题的最优解。其核心过程可描述如下：① 染色体编码；② 初始化种群；③ 设计适应度函数；④ 选择；⑤ 交叉；⑥ 变异。遗传算法的主要流程如图1所示。

图1 遗传算法流程

2 通信卫星资源动态调度方法

2.1 通信任务约束分析

卫星资源的动态调度是通过在一定的时间范围和频率范围内将通信任务进行有效排列而实现的[14]。根据通信任务的使用特征，可以分析得到其基本约束：时间约束和频率约束。

时间约束：① 任务所需时长固定；② 任务所需时间范围连续；③ 任务存在最小开始时间和最晚结束时间。最晚结束时间和最小开始时间之差必须大于或等于任务所需时长。

频率约束：① 任务所需带宽固定；② 任务所需频率范围连续。

根据以上描述，多通信任务的排列方式可以采用二维坐标系的方法予以表征，排列示意如图2所示。

图2 通信任务排列示意

2.2 设计思路

在卫星通信过程中，由于各通信任务的时间需求和带宽需求各不相同，在有限的时间和带宽范围内，它们不同的排列顺序会导致不同的资源利用率。通信卫星资源动态调度是通过制定一系列的最优调度原则来最终得到一组最优的通信任务排列序列。

设给定的时间范围为0～T(此时T应大于或等于所有任务的最晚结束时间中的最大值)，给定的频率范围为0～F，则最优调度原则如下：

① 频率轮廓线表示的频率值(即任务排样图的最大高度值)应该尽量低；

② 时间轮廓线表示的时间值(即任务拍样图的最大宽度值)应该尽量低；

根据以上原则，卫星资源动态调度的过程设计如下：

① 随机初始化一个有n个通信任务的排序序列；

② 按照序列的顺序依次取出每个通信任务，对于每一个任务，设其最早开始时间为t0，最晚开始时间为t1，持续时长为t，则在t0～t0+t的时间段内，寻找是否存在空闲的频率资源支持该任务。如果存在，则将该任务块排列在该时间段内相应的频率范围内上；如果不存在，则将搜索时间段的起始时间加一个偏移量t′，重复以上搜索过程。如果当t0+t′+t>t1时仍未找到可用的频率资源，则将该任务标记为不可分配任务。

③ 计算所有排入的任务块的总面积Area0，计算排列完成后形成的频率轮廓线和时间轮廓线之内的面积Area，最终计算f=Area0/Area。

④ 交换任务位置，调整任务排列，找出f的最大值，并直到f收敛或满足叠代次数，输出f最大时的任务排列结果。

2.3 遗传算法

从理论上看，提出的卫星资源动态调度问题属于具有最高计算复杂性的优化计算问题——NP完全问题。对于这类问题，在全局空间上搜索最优解是很困难的，甚至是不可能的[15]。因此引入遗传算法来求解任务排序的最优解，该算法可以以最小的计算代价最大限度地得到问题的最优解，提高计算效率。下面给出遗传算法的求解过程。

2.3.1 染色体编码和群体初始化

采用互换编码，如1，2，3，4，……，n，这些数字代表通信任务的编号，n为任务数量。初始化时，根据初始群体的大小M，随机初始化M个任务序列，每一个序列的表达式如下所示：

Q={q1,q2,q3,…,qn}。

2.3.2 适应度函数

适应度函数是种群中染色体适应能力的衡量标准，适应度函数值越大，解的质量就越好。

根据2.2节阐述的卫星资源动态调度过程对种群中的每一个染色体进行排列，并根据最优调度原则确定适应度函数为f=Area0/Area，其中Area0为排入的任务块的总面积，Area为排列完成后形成的频率轮廓线和时间轮廓线之内的面积，f值最大为1。

2.3.3 选择

选择操作是根据适应度值的大小将染色体选择进入下一代种群的过程。选择操作可以避免种群中有用的遗传信息丢失，从而使得种群慢慢向最优染色体种群靠近。

对初始种群中的每一个染色体，计算其适应度函数值的大小，之后根据染色体适应度函数值大小，采用轮盘赌算法进行比例选择运算。选择概率公式为：

2.3.4 交叉

交叉是模拟自然界进化的过程中，2条染色体的某些基因位互换，从而形成新的染色体，增加种群多样性。遗传算法中的交叉操作就是从某个位置互换2条染色体的基因位，从而形成新的染色体。交叉操作首先对进行了选择运算的群体中的染色体以随机的概率两两配对，然后选择单点交叉算子进行交叉操作，产生M个染色体构成子辈群体。

基于互换编码的单点交叉操作的过程如下：设2个进行交叉的染色体为X和Y，在1～n范围内随机生成一个交叉位b，从X中将位于b之前的元素拷贝至一个新的子辈染色体newX中作为前面的元素，剩余元素按Y中出现的先后顺序拷贝至newX；同样的方法可以产生另一个新染色体newY。一种单点交叉操作示例如图3所示。

图3 单点交叉操作示例

2.3.5 变异

遗传算法中的变异是将种群中某个或几个的基因位的值进行变换，从而形成新的染色体，变异操作使得种群避免收敛于局部次优解，使得算法向更优的方向进化。

对进行了交叉操作的子辈染色体，采用位置变异算子进行变异操作。在1～n范围内随机生成2个变异位b1、b2，以较小的概率对子辈的染色体中位于b1、b2的2个任务对调。

2.3.6 精英保留

为了加快算法的收敛速度，引入精英保留策略对该遗传算法进行优化[16]。精英保留策略是指为了防止进化过程中产生的最优解被交叉和变异所破坏，将每一代中的最优解原封不动地复制到下一代中。

对于进行了变异操作的子辈染色体，依次进行排样并计算相应的适应度，然后将子辈染色体中具有最低适应度的染色体替换为选择操作中所记录的最优染色体，得到修正后的子辈种群。

将生成的子辈种群在本遗传算法中继续迭代，循环这一算法过程直到适应度函数完成收敛或者达到要求的最大迭代周期。此时，取出种群中最优的染色体作为最终的任务排列结果。

3 实验结果分析

本文基于上述算法开发了通信卫星资源动态调度程序，并在相同任务数和不同任务数的条件下分别模拟仿真了资源静态分配过程和资源动态调度过程，最后对资源静态分配方式和动态调度方式下的资源利用率分别进行了对比。

3.1 相同任务数

通过在45天的时间段内设计35个具有不同开始时间和结束时间的通信任务，在65 MHz的频率带宽范围内分别仿真了资源静态分配过程和资源动态调度过程，其资源利用率的对比图如图4所示。

图4 相同任务数下资源利用率对比曲线

由图4可以看出，在前期由于运行任务较多，资源使用密集，动态调度方式的资源利用率会明显高出静态分配方式；而到了后期由于较多任务已结束，正在运行的任务数变少，静态分配方式与动态调度方式的资源利用率趋于相近。

3.2 不同任务数

通过分别随机生成5、10、15、20、25、30、35、40、45、50、55、60、65和70个通信任务在65 MHz的频率带宽范围内仿真了资源静态分配过程和资源动态调度过程，统计不同任务数下的资源利用率得到的对比图如图5所示。

图5 2种方式下资源占有率对比曲线

从图5中可以看出，静态分配的资源利用率整体低于动态分配的资源利用率，当任务数大于30时，静态分配的资源利用率基本保持在28%左右，而动态分配的资源利用率基本保持在60%左右。

4 结束语

本文探讨了如何在通信任务的时间和资源约束下，如何利用遗传算法进行卫星资源动态调度的问题，并且进行了设计和仿真。遗传算法的引入对于通信卫星的资源使用效能的提高具有很大的现实应用价值。

另外，本文所提出的卫星资源动态调度方法中考虑的约束因素和优化目标还可以进行进一步的细化和补充，例如考虑任务优先级、频率质量等需求，使卫星资源动态调度方法更符合实际应用环境。

[1] 王晓杰,罗健欣,郑成辉,等.基于任务等级的卫星资源分配算法研究[J].计算机时代,2016(2):11-13.

[2] 黄 睿.卫星通信技术的应用体会及未来趋势展望[J].科技创新与应用,2013(20):38-42.

[3] 李斌成.FDMA/DAMA卫星通信网资源分配策略研究[J].无线电通信技术,2014，40(6):50-53.

[4] 赵 静,赵尚弘,李勇军,等.中继卫星资源调度问题研究现状与展望[J].电讯技术,2012，52(11):1 837-1 843.

[5] 于 佳,宗 鹏.中国业务模型的建立和低轨卫星资源分配的研究[C]∥第七届卫星通信新技术、新业务学术年会论文集.北京:中国通信学会,2011:195-207.

[6] 李 斗,王 峰.宽带卫星Mesh网多址接入信道预测分配方案研究[J].电子与信息学报,2008,30(4):763-767.[7] 王小平,曹立明.遗传算法—理论、应用与软件实现[M].西安:西安交通大学出版社,2002.

[8] 李 明,黄平捷,周泽魁.基于小生境遗传算法的矩形件优化排样[J].湖南大学学报,2009,36(1):46-49.

[9] 申建华,郑晓冬,赵 麟.基于遗传算法的波束形成算法研究[J].无线电通信技术,2015,41(3):83-85.

[10] 徐丽佳,蒲海波,蒋宏健.改进遗传算法的路径规划研究[J].微计算机信息,2006,2(5):251-253.

[11] 张 航,孟 艳,陈 乾,等.基于遗传算法的通信卫星频谱资源运用研究[J].军事通信技术,2007,28(3):1-5.[12] 高朝晖,岳群彬,李 伟.遗传算法在成像卫星计划编制中的应用[J].无线电工程,2013,43(12):37-40.

[13] 刘 伟,李 斌.一种改进的基于遗传算法的测试调度方法[J].无线电通信技术,2016,42(2):37-40.

[14] 杨 力,吴志涛,王延春.一种解决卫星网络通信冲突的调度算法[J].计算机工程,2012,38(21):59-62.

[15] 杜立智,陈和平,符海东.NP完全问题研究及前景剖析[J].武汉工程大学学报,2015,37(10):73-78.

[16] 黄务兰,张 涛.基于改进遗传算法的带时间窗车辆路径问题研究[J].微型机与应用,2016,35(13):21-24.

Research of Dynamic Scheduling Method for CommunicationSatellite Resources Based on Genetic Algorithm

LIN Yu-sheng,JIANG Hong-lei,DONG Yan-lei,GENG Ji-zhao,LIU Yue-xiao

(The54thResearchInstituteofCETC,ShijiazhuangHebei050081,China)

With the continuous development of satellite communication technology,the practical application requirement for satellite communication becomes more and more complex.In order to deal with the resource competition among networks of different communication systems,improve the utilization of satellite resources and satisfy the requirement of satellite communication to a greater extent,a dynamic scheduling method for communication satellite resources based on genetic algorithm is proposed.This paper introduces the basic constraints of communication task which is the basis of satellite resource dynamic scheduling,and describes the specific implementation process of the dynamic scheduling method combined with the genetic algorithm.At last,the dynamic scheduling method is compared with the static scheduling method through simulation experiments.The simulation results show that the dynamic scheduling method achieves higher resource utilization under the conditions of both same number and different number of tasks.

communication satellite resources；dynamic scheduling；genetic algorithm

2017-03-07

国家高技术研究发展计划(“863”计划)基金资助项目(2015AA015701)。

10.3969/j.issn.1003-3106.2017.06.05

林宇生，蒋洪磊，董彦磊，等.基于遗传算法的通信卫星资源动态调度方法研究[J].无线电工程,2017,47(6):20-23.[LIN Yusheng, JIANG Honglei, DONG Yanlei,et al.Research of Dynamic Scheduling Method for Communication Satellite Resources Based on Genetic Algorithm[J].Radio Engineering,2017,47(6):20-23.]

TN915

A

1003-3106(2017)06-0020-04

林宇生 男，(1978—)，博士，高级工程师。主要研究方向：卫星通信。

蒋洪磊 男，(1982—)，博士，高级工程师。主要研究方向：卫星通信。