基于改进蚁群算法的卫星数传调度

黄双临，马冬青，方冬梅，崔 涛

（1.北京卫星导航中心，北京 100094；2.华北计算技术研究所，北京 100083）

基于改进蚁群算法的卫星数传调度

黄双临1，马冬青2，方冬梅2，崔 涛2

（1.北京卫星导航中心，北京 100094；2.华北计算技术研究所，北京 100083）

卫星数传调度的目标是利用有限的资源合理地安排卫星数传任务。由于卫星数传任务众多而资源有限，且卫星数传受星地可见性条件以及任务、资源等多方面约束，导致调度问题十分复杂。针对卫星数传任务的特点，建立了卫星数传调度问题模型，以最大化的加权调度任务成功率作为调度的优化目标，提出了基于改进蚁群系统的卫星数传调度算法。算法采用任务直接排列的编码方式，以蚁群系统为基础，提出自适应的偏向探索概率，动态地调整蚂蚁探索比率。实验结果表明，该算法有效提高了卫星数传调度任务的加权调度任务成功率。

卫星数传调度；蚁群算法；自适应

0 引言

卫星数传调度的目标是利用有限的天线、信道、记录设备和传输链路等资源，尽可能地安排卫星数据接收和传输任务。其核心是解决多星、多站条件下的数据接收任务与天线资源的冲突问题。

卫星数传调度涉及多颗卫星，这些卫星按照各自的轨道运行，它们经过各地面站的时间长度和进入时刻不同，而各地面站的天线设备的能力不同，如仰角限制不同，因而各天线设备对各卫星有不同的可见时间窗。要完成数据接收任务，必须满足卫星可见和天线空闲2个基本条件。另外，卫星数传调度还要满足指定的规则和约束条件。在多星、多站、多设备和多任务条件下，卫星数传调度存在以下2种情况：①任务冲突，即一个资源，要完成多个任务。在同一时间，有多个任务要使用同一天线设备。②资源冲突：也称作竞争，即一个任务可由多个资源之一完成。在同一时间，有多个任务天线设备都可以完成某个任务。概括起来，数传任务调度是有时间约束的资源调度，是一个有约束的组合优化问题。

国外对卫星任务调度展开了许多研究。Gooley采用混合整数规划算法解决美国空军卫星控制网的低、中高轨卫星调度问题［1］。Pemberton提出了贪婪算法和分支定界法相结合的优先级分割算法［2］。Frank提出了基于约束的卫星观测调度算法。Parish提出了采用遗传算法解决多星测控调度问题的方法［3］。国内在建模方面对多种卫星调度问题模型进行细分，融入多种约束，针对各种不同限制及优化目标的卫星任务调度问题提出了多种解决方案［4－8］。

本文针对卫星数传任务的特点，建立了卫星数传调度问题模型，以最大化的加权调度任务成功率作为调度的优化目标，提出了基于改进蚁群系统的卫星数传调度算法。算法采用任务直接排列的编码方式，以蚁群系统为基础，提出自适应的偏向探索概率，动态地调整蚂蚁探索比率。

1 卫星数传调度模型分析

卫星数传系统是一个多星、多站、多设备、多任务和多环节的复杂系统。地面网资源由多个接收站、多个接收天线、多个信道、多套记录设备、多条光纤传输链路以及其他相关系统及设备构成。各接收站数据接收系统内接收天线、信道、记录设备的连接相对固定，通过人工设置可对信道和记录设备进行调配。卫星数传调度主要是根据卫星观测预报、任务要求、资源情况和系统状态等条件，合理安排地面资源，制定作业任务。卫星数传调度的核心是解决多星、多站条件下的数据接收任务与天线资源的冲突问题。如何利用有限的天线资源尽可能地安排数据接收任务，是卫星数传调度要解决的关键问题。

一项数据接收任务对应单个天线的一次跟踪。需要多个接收站针对某一轨道的卫星接力跟踪时，卫星数传调度将任务转换为多项任务。一项数据接收任务包含如下要素：

①卫星：表示对哪颗卫星的数据接收任务；

②地面站：表示系统中的地面站；

③天线：表示部署在各地面站的天线；

④可见区间：表示天线对卫星的可见时间窗口；

⑤天线设置的时间限制：表示天线执行操作所需的准备时间；

⑥优先级：用户在接收计划中指定的卫星数据时效性与重要性要求，分为重要、加急和常规；

⑦任务执行的最少时间长度。

由于任务涉及诸多因素，经过预处理和分析整理，可以对任务进行如下归纳：

①根据资源条件和约束，将地面站和天线、信道、记录器等资源归纳为可完成任务的实体，即天线设备；将用户在接收计划中指定的地面站和任务调配原则作为实体限制；

②将设备对卫星的可见区间、设备限制以及用户在接收计划中指定的开始时间和接收结束时间，任务执行的时间范围，任务执行的最少时间长度归纳为可行时间窗口。

这样，天线设备及其可行时间窗口就构成了任务安排的一个备选项，任务可以选择安排在任意一个备选项。

在任务集合中，如果一个任务有多个备选项，则发生竞争；如果多个任务之间的备选项重叠（同一设备，可行时间窗口重叠），则发生冲突。为了尽可能地安排任务，采取最大化加权调度任务成功率作为调度目标，如式（1）所示。

式中，wi为实际安排任务权值；maxwi为任务i的最大可能权值。本文采用优先级和接收时间长度作为权值的设置因素。

2 基于改进蚁群系统的卫星数传调度

2.1 蚁群算法

蚁群算法是模拟自然届蚂蚁觅食过程的一种随机搜索算法。蚂蚁在觅食过程中释放一种特殊的信息素，蚂蚁感知信息素浓度信息，倾向于往信息素浓度高的方向行进。在较短路径上，蚂蚁往返时间短，经过的蚂蚁数量多，信息素积累快，使得后续蚂蚁倾向于选择较短路径。这种正反馈机制，使得蚂蚁个体之间相互协作，寻找到从蚁穴到食物源的最短路径［9］。

1991年意大利的Dorigo等人提出蚁群算法，用来解决TSP问题［10］。蚁群算法模拟蚁群协作，根据信息素浓度采用随机比例规则构建路径，并对所有路径进行全局信息素更新，通过正反馈机制多次迭代，得到问题的满意解。在基本蚁群算法的基础上，提出了多种改进方法，包括：精华蚂蚁系统、最大最小蚂蚁系统和基于排列的蚂蚁系统，这些方法在搜索控制方面进行改进，调整信息素更新方式。1997年Dorigo提出新的蚁群系统，采用伪随机比例规则构建路径，调整信息素全局更新规则，新增局部更新规则。这些改进使蚁群算法收敛性能得到改善［11－13］。

本文基于改进蚁群系统的卫星数传调度算法，采用任务直接排列的编码方式，以蚁群系统为基础，提出自适应的偏向探索概率，动态地调整蚂蚁探索比率，避免算法收敛过快或算法停滞。

本文采用改进蚁群算法求解卫星数传调度问题，算法步骤如下：

①初始化信息素；

②初始化蚁群，用随机法为蚁群中各蚂蚁确定初始任务；

③采用伪随机比例规则进行状态转移，生成任务序列，即每只蚂蚁根据当前任务依据信息素浓度确定下一任务，直到确定所有任务；

④按照信息素局部更新规则，对每只蚂蚁的任务序列更新信息素；

⑤按照信息素全局更新规则，令当前最优蚂蚁释放信息素；

⑥转到步骤②进行逐步迭代。当任务序列满足优化准则或达到迭代次数时，结束迭代。将蚁群中的最优任务序列作为近似最优解。

2.2 编码与解码

利用蚁群算法解决卫星数传调度问题时，首先要确定解的表示形式［14］。卫星数传调度需要确定出各任务分配的资源及任务的开始和结束时间。本算法采用任务号直接排列的表示方法构成蚂蚁路径的编码，采用1～N（N是任务数）的不重复的自然数编码形式，表示调度序列。在这种编码中，1，2，…，N表示各卫星数传任务，安照编码顺序逐一安排各任务。

解码过程根据编码序列所表示的任务顺序转换生成实际的调度方案。解码时，逐一对任务分配资源和执行时间。资源分配策略是：根据已安排任务情况和剩余可用资源情况安排支持最大任务时间的资源执行。解码过程中，冲突消解是一个重要的环节，编码序列中的各项任务必须满足星地可见约束及任务资源约束，资源分配时进行约束检查及裁剪处理，满足条件的任务纳入数传调度表。具体包括：

①在资源与任务弧段不对应的情况下，解码消除该任务；

②在任务弧段与该星的已分配任务有重叠的情况下，将任务弧段进行裁剪，不重叠部分作为剩余弧段，当剩余弧段有多个时间段时，选择时间最长部分作为任务项；

③在资源与已分配时间有重叠的情况下，裁剪任务弧段；

④当剩余任务弧段大于任务执行的最少时间时，将其纳入数传调度表，并记录资源分配时间。资源分配时间包括执行任务的时间和资源设置时间。

在本文研究的卫星数传调度问题中，采用数传调度表的加权调度任务成功率作为数传调度的目标函数值，用于评判解的优劣。加权调度任务成功率高的数传调度优于加权调度任务成功率低的数传调度。

加权调度任务成功率可表示为：

式中，psum为加权调度任务成功率；n为任务数；ti为任务i的安排时间长度；Ti为任务i的最大可能安排时间长度；ai为任务i的优先级系数［15］。

2.3 状态转移规则

算法中每只蚂蚁随机选择一个任务作为开始任务，随后按照特定规律选择下一任务。在本算法中，执行某任务i的蚂蚁k，根据式（3）所示的伪随机比例规则选择下一个任务j。

式中，Jk（i）为蚂蚁k尚未执行的任务集合；τ（i，j）为从任务i转到任务j的信息素量；η( i，j)为启发式信息，η（i，j）＝1／（tc＋tij），tc为任务执行时间下限，tij为在执行i任务后执行j任务的损失时间；α为信息素浓度权重；β为启发式信息权重；q0为自适应参数，如式（5）所示，0≤q0≤1；q为在［0，1］区间均匀分布的随机数。当q≤q0时，蚂蚁直接执行信息素浓度高和损失时间小的最优任务，这种情况下，蚂蚁根据当前已知的状态确定地选择任务。当q＞q0时，采用轮盘赌选择策略来选择蚂蚁的下一任务，这种情况下，选择任务j的概率为：

2.4 信息素更新规则

在基于改进蚁群系统的卫星数传调度算法中，用信息素来表示某任务作为另一任务后续任务的优劣程度。算法初始化时，所有任务相对另一任务的信息素都被初始化为τ0，τ0＝1／（mTsum），m为蚂蚁数量，Tsum为数传任务时间最大可能调度时间。

2.4.1 信息素全局更新规则

信息素全局更新规则是指最优蚂蚁按全局更新规则来更新信息素。当蚂蚁完成所有任务后，算法对各任务进行信息素更新。在全局更新规则中，只有至今最优的蚂蚁才被允许释放信息素，其他蚂蚁不释放信息素。这个策略以及伪随机比例规则的使用，使搜索过程具有更强的指导性。在每次迭代中，在蚂蚁完成所有任务后，对最优任务调度序列中的任务更新信息素，信息素全局更新公式为：

式中，ρ为信息素挥发参数，代表信息素挥发速率；Δ τb（i，j）为新增加的信息素，Δ τb（i，j）＝1／（Tsum－Tb）；Mb为最优任务调度序列；Tb为最优任务调度时间。

2.4.2 信息素局部更新规则

信息素局部更新规则是指完成任务的每一只蚂蚁均释放信息素。信息素局部更新公式为：

式中，ξ为信息素局部挥发参数，0＜ξ＜1；τ0为信息素初始值，τ0＝1／（mTsum）。

3 算法改进

基于改进蚁群系统的卫星数传调度算法的改进，主要体现在以下两方面：

①提出任务直接排列的编码方式，采用任务直接排列的表示方法构成蚂蚁路径的编码。这种改进有效地避免了采用组合编码的大量非法解，从而提高了算法的搜索效率。

在现有算法中，多数参照解决车辆路径问题VRP的任务与资源组合排列的方法进行编码。这种编码方法在应用于解决卫星数传调度问题时，由于星地可见要求等约束限制，使得求解过程中面临大量无效编码，效率较低。本算法采用任务号直接排列的表示方法构成蚂蚁路径的编码。解码过程逐一对任务分配资源和执行时间，并根据星地可见约束及任务资源约束进行冲突消解。由于本算法的编码方式避免了大量非法解，有效地提高了算法的搜索效率。

②提出自适应的偏向探索概率，动态地调整蚂蚁探索比率。这种方法在算法趋向停滞的情况下，增大了在全局范围内搜索比例，避免算法收敛到局部最优解。

在蚂蚁群系统中，状态转移规则中的q0是一个很重要的控制参数，蚂蚁以q0为概率选择当前最优任务，以（1－q0）的概率进行偏向探索。本算法提出自适应的偏向探索概率，动态地调整蚂蚁探索比率，避免算法停滞。算法初期，采用预设的q0，保证算法较快地收敛。在迭代多次问题解没有改进的情况下，算法按照式（5）减小q0，从而增大偏向探索概率。这种方法在算法趋向停滞的情况下，增大了在全局范围内搜索比例，避免算法收敛到局部最优解。

4 实验验证

为验证本算法的调度能力，本文采用模拟生成的实验样本进行解算。在实验样本中，卫星数传任务涉及12颗卫星和3个地面站。12颗卫星分布在3个轨道面，构成walker星座，轨道倾角56°，轨道周期为12 h，偏心率为0，近地点幅角为0°，卫星和地面站参数如下表1和表2所示。每个站有2套设备。设备的工作仰角大于10°，设备的设置时间为2 min。卫星数传调度的时间范围为2012年4月17日12时至2012年4月18日12时，根据卫星与地面站的可见关系生成60个任务。每个任务最少执行时间为5 min，任务优先级均为1。

表1 实验样本卫星参数

表2 实验样本地面站参数

本文实验分别用先到先服务FCFS算法、贪婪算法、最短任务优先算法和改进蚁群算法对上述实验样本进行解算，计算结果如表3所示。表中改进蚁群算法中蚂蚁数为20，迭代次数设为100，运行20次，统计平均值作为统计数据。实验样本的最大可能加权任务时间为406 531 s。

表3 实验结果

从数据中可以看出：采用改进蚁群算法得到的优化调度的加权调度任务成功率为93．8%，优于其他几个算法。

改进蚁群算法由于算法相对复杂，与其他启发式算法相比，较为耗时。算例中计算时间在3 s之内，不算过长，可以用于实际的卫星数传调度。

5 结束语

通过分析和实验验证可知，本文的基于改进蚁群系统算法有效地解决了卫星数传调度问题，提高了加权调度任务成功率。本算法采用任务直接排列的编码方式，有效地提高了算法的搜索效率。提出的自适应的偏向探索概率，动态地调整蚂蚁探索比率，在算法趋向停滞的情况下增大了在全局范围内搜索比例，避免算法收敛到局部最优解。

［1］陈祥国．卫星数传调度的蚁群优化模型及算法研究［D］．长沙：国防科学技术大学博士学位论文，2010：7－16．

［2］PEMBERTON Joseph C，FLAVIUS Galiber．A Constraint-Based Approach to Satellite Scheduling［C］∥Boston，MA，USA：Proceedings of Constraint Programming and Large Scale Discrete Optimization，2001：101－114．

［3］李云峰，武小悦．遗传算法在卫星数传调度问题中的应用［J］．系统工程理论与实践，2008（1）：124－131．

［4］李云峰，武小悦．基于试探性的卫星数传任务调度算法研究［J］．系统工程与电子技术，2007，29（5）：764－766．

［5］凌晓冬，武小悦．一种求解多星测控调度问题的启发式算法［J］兵工自动化，2008（1）：71－73．

［6］孙 兵，陈祥国．混合蚁群优化算法求解卫星数传调度问题［J］．计算机应用研究，2012（11）：4 065－4 068．

［7］张 超．基于贪婪算法的遥感地面站任务调度技术［J］．无线电工程，2011，41（1）：58－60．

［8］徐雪仁，宫 鹏，黄学智．资源卫星（可见光）遥感数据获取任务调度优化算法研究［J］．遥感学报，2007，11（1）：109－114．

［9］赵天男，王晓红．蚁群算法及其应用研究［J］．软件导刊．2010（6）：34－35．

［10］COLORNIA，DORIGO M，MANIEZZO V．Distributed Op-timization by Ant Colonies［C］∥Proceedings of 1st Euro-pean conference on Artificiial Life，1991：134－142．

［11］DORIGO M，MANIEZZO V，COLONI A．The Ant System：Optimization by a Colony of Cooperating Agents［J］．IEEE Transactions on Systems，Man，and Cybemetics-Part B，1996，26（1）：29－41．

［12］胡银厚．求解TSP算法的研究与改进［D］．郑州：郑州大学硕士学位论文，2012：29－44．

［13］王海波，徐敏强，王日新．基于IP-ACO算法的航天器测控资源调度技术［J］．系统工程与电子技术，2012（4）：719－725．

［14］BARBULESCU L，HOWE A．AFSCN Scheduling：How the Problem and Solution Have Evolved［J］．Mathematical and ComputerModeling，2006，43（9）：1 023－1 037．

［15］SOLOMON M．Algorithms for Vehicle Routing and Sched-uling Problems with Time Window Constraints［J］．Opera-tions Research，1987，35（2）：254－266．

Satellite Data Transmission Scheduling Based on Improved Ant Colony System

HUANG Shuang-lin1，MA Dong-qing2，FANG Dong-mei2，CUI Tao2
（1．Beijing Satellite Navigation Centre，Beijing 100094，China；2．North China Institute of Computing Technology，Beijing 100083，China）

Satellite data transmission scheduling is to program the missions scientifically using limited resources．Because of the conflict between large task numbers and limited resources and restrictions in terms of satellite visibility，the scheduling for satellite data transmission is very complex．In this paper，a mathematical model of the satellite data transmission scheduling is established，considering the features of the missions，setting a goal to maximize the weighted scheduling success rate．And an improved ant colony optimization algorithm is presented to solve the scheduling problem，which introduces mission-straight permutation coding．Based on ant colony system，the algorithm introduces an adaptive probabilistic decision model for biased-exploration to adjust ant exploration ratio dynamically．Experimental data demonstrate that the algorithm effectively improves the weighted scheduling success rate of satellite data transmission．

satellite data transmission scheduling；ant colony system；adaptive

TP39

A

1003－3106（2015）07－0027－04

10．3969／j．issn．1003－3106．2015．07．08

黄双临，马冬青，方冬梅，等．基于改进蚁群算法的卫星数传调度［J］．无线电工程，2015，45（7）：27－30，58．

黄双临女，（1975—），硕士。主要研究方向：卫星导航。

2015-04-02

马冬青女，（1972—），硕士。主要研究方向：卫星应用。