Deterministic Scheduling Algorithm With Priority Classification for Industrial Wireless Networks
-
摘要: 确定性调度技术对于工业无线网络数据的实时性和确定性传输有着重要意义.本文针对工业无线网络数据流本身存在优先级分类属性的情况, 基于多信道时分多址接入(TDMA)技术, 在分析高优先级数据流对低优先级数据流造成的链路冲突延时和信道竞争延时基础上, 对网络进行调度预处理, 进而排除参数不合理的网络, 并向网络管理者反馈.对于通过预处理的网络, 调度算法优先为高优先级数据流的链路分配时隙和信道资源, 而对属于同一类优先级的数据流, 提出一种基于比例冲突空余时间的调度方案, 在满足可调度性条件的前提下, 根据各链路的比例冲突空余时间值从小到大依次分配时隙和信道资源.实验结果表明, 所提出的调度算法可以取得较高的网络调度成功率.Abstract: Deterministic scheduling technology has a significant impact on the real-time and deterministic data transmission in industrial wireless networks. This paper considers the case that end-to-end flows in industrial wireless networks have a property of priority classification, and adopt multi-channel time division multiple access (TDMA) technology. On the basis of analyzing the delays of lower priority flows due to both link conflict and channel contention caused by higher priority flows, there is a pre-processing scheduling for testing networks firstly. Therefore, some networks with unreasonable parameters can be excluded, and this will inform network administrator for further processing. For networks passing the test of pre-processing scheduling, the scheduling algorithm gives preference to allocate time slots and channels to link with higher priority flows. For the flows with the same priority, a scheduling scheme based on proportional deadline and conflict is also presented, which allocates the time slots and channels according to the values of proportional deadline and conflict in ascending order for flows that meet the schedulability condition. Results show that the proposed scheduling method can achieve a higher schedulable ratio.
-
Key words:
- Industrial wireless networks /
- deterministic scheduling /
- priority classification /
- pre-processing scheduling
-
无人飞行器集群技术是指多个具有共同任务目标的无人飞行个体, 借助现代控制与决策手段, 维持无人飞行器以群体形式有序执行任务的智能技术.随着控制技术、通讯技术、传感器技术和智能调度技术的快速发展, 无人飞行器集群技术在区域测控与搜索、军事侦察与打击、信息通讯、气象监测和物流运输等民用与军事领域得到广泛应用[1-4].无人飞行器集群技术能够在极少人为干预的情况下做出智能决策, 具有自组织性、协同性、并行性和安全性的优点, 是未来飞行器技术信息化、智能化发展的必然趋势.
从无人飞行器的飞行高度与工作环境看, 目前无人飞行器集群的对象主要为无人机和卫星两类.无人机和卫星集群具有诸多相同的特点:飞行运动约束强、速率大; 集群任务中响应频繁、容错率低; 受天气等环境因素及动态因素影响显著等.而随着无人机和卫星技术的蓬勃发展, 在任务需求、任务规模、任务与资源约束和工作环境等方面, 无人机和卫星集群的复杂性和不确定性也急剧增长, 严重影响着集群任务执行的效率与可靠性.因此, 如何通过调度技术为无人飞行器个体分配任务和有限的资源、避免任务和资源冲突、实现全局任务收益的最大化, 成为无人飞行器集群技术的关键.
考虑到无人飞行器集群调度问题的任务复杂性、强约束性和NP (Non-deterministic polynomial)难特性, 合理的任务特征分析、准确的资源与约束建模, 以及针对性的智能求解方法尤为重要.由此, 本文分别基于无人机群和多星任务调度问题的特点, 按图 1分类介绍了无人机群和多星的任务类型, 梳理了无人机群和多星任务调度问题的主要约束, 总结并阐述了智能优化算法在无人机群和多星任务调度中的应用.最后, 面向未来无人飞行器技术应用需求, 指出了无人飞行器集群智能调度技术进一步的研究方向.
1. 无人机群任务智能调度技术
无人机群在执行民用任务(如监测、救援)和军用任务(如侦察、打击)方面具有广阔的应用前景, 特别是在偏远、危险或人员不可达的工作环境中已逐步取代有人系统.随着任务需求、规模和复杂度的不断提升, 无人机群任务调度技术已成为无人机研究领域的热点之一.无人机群任务调度技术是在满足各项约束条件的前提下, 以实现收益最大化为目的, 为无人机合理安排任务和有限的任务资源, 对提高任务执行效率和资源利用率具有重要意义.针对无人机群调度技术的应用领域, 本节将梳理无人机群任务调度的类型和主要约束条件, 并结合不同类型的任务调度问题介绍常用的几种无人机群任务智能调度算法.
1.1 无人机群任务类型
根据无人机资源利用与任务目标的不同, 可将无人机任务分为访问任务和打击任务.前者是利用无人机能量资源, 根据任务需求对目标点逐一进行覆盖或侦测; 后者则是利用机载武器资源, 对目标进行攻击.同时, 在现代无人机作战任务中, 侦察与打击任务往往密不可分、同步进行, 具有一体化的调度需求.由此, 本节将分类阐述一些代表性的无人机群任务调度研究.
1.1.1 访问任务
无人机群访问任务调度是在主要满足侦测设备与能量约束的条件下, 通过对机群进行合理的任务分配, 有效覆盖、搜索或评估访问目标, 实现访问收益最大化的过程.
1) 覆盖任务
无人机群覆盖任务主要体现于对区域目标的持续监控和确定性的侦测搜索.根据无人机覆盖任务是否依赖于某种行为, 任务的执行策略又可分为行为式覆盖策略和非行为式覆盖策略, 如图 2所示.
行为式覆盖策略是基于某种无人机行为, 优化各无人机的初始方向和飞行时长, 以实现对任务区域最大化覆盖的目的.例如, 罗木生等[5]考虑了反潜无人机吊放雷达的搜索特点, 设计了"回字型"拓展方阵覆盖策略, 并对比了单机覆盖与多机协同覆盖的效果. Lee等[6]设计了一种"内旋式"无人机覆盖策略, 通过引入机器人边界跟随行为的分段启发式算法实现了不规则区域的有效遍历.针对大规模区域目标覆盖任务, 陈海等[7]通过对目标区域的分割与任务分配, 建立了无人机"牛耕式"覆盖任务的约束满足模型. Kolling等[8]设计了无人机"并列推扫"策略, 通过优化并列数量、搜索角度和高度完成了不规则2.5D环境区域的持续覆盖.行为式覆盖策略具有较小的问题规模和良好的可执行性, 是覆盖问题的主要优化策略.
非行为式覆盖策略则不拘泥于无人机的某种行为, 直接优化无人机飞行路径, 在覆盖问题中也表现了出色的优化效果.例如Barrientos等[9]将待搜索区域进行栅格化处理, 在网格轨迹优化的基础上辅以飞行动力控制修正, 提升了无人机群分布式协同覆盖的效果.晋一宁等[10]针对区域目标持续覆盖问题, 以每个网格单元最短未覆盖时间为优化目标, 借助无人机群局部感知和通信策略, 实现了无人机系统对动态目标持续涌现的覆盖行为.
2) 搜索任务
无人机群搜索任务主要体现于对不确定性或动态目标的搜索需求.民用方面, 针对海上失事人员搜索问题, Varela等[11]设计了基于约束采样的进化算法, 使得搜索过程具备自组织性和引导性, 表现出较高的发现概率和鲁棒性. Lanillos等[12]研究了不确定环境中失踪目标的搜索问题, 通过预期观测信息有效引导机群搜索, 并基于滚动时域不断更新观测信息, 极大程度地提升了目标发现概率和机群搜索效率. Wang等[13]将无人机群搜索任务分为航迹规划与任务分配两个阶段, 分别采用了无障碍图搜索算法和混合线性整数规划方法进行求解.
军用方面, 符小卫等[14]研究了无人机对地移动目标协同侦察任务调度问题, 在无人机群成员通讯交互的基础上, 基于预测控制思想考虑了无人机当前搜索代价和长期搜索代价, 提高了无人机群协同搜索效能.为降低目标不确定性运动的影响, Ru等[15]通过机载传感器探测和敌机潜在运动范围分析, 基于贝叶斯理论对敌机运动概率图进行实时更新, 有效提升了三维战场环境中敌机的发现概率.针对通用战术网络环境下的无人机群协同侦察问题, 马纯超等[16]将无人机群的控制任务分配给不同的地面管控中心, 并基于无人机网络信息通讯实现了对随机动态目标的搜索与遍历.
3) 评估任务
无人机群评估任务主要来源于军用无人机在完成作战行动后对目标毁伤效果的评估需求.评估任务是一种通过具备评估功能的无人机对目标实施遍历的访问任务, 但由于其与无人机打击任务存在严格的时序约束, 故通常在打击任务或察打一体化任务中执行.
1.1.2 打击任务
无人机群打击任务调度是指在获得目标属性、位置和速度的情况下, 分配无人机及其机载武器资源, 在满足一定约束条件的情况下对目标完成打击任务的过程.例如, 倪谣等[17]建立了满足时序约束的打击任务混合整数规划模型, 实现了6架无人机对4个地面固定目标的攻击任务分配.在动态任务频繁到达的情况下, 周小程等[18]研究针对动态打击目标的无人机群实时调度问题, 并借助分布式的竞拍机制提升了任务调度效率.
不过, 随着无人机作战任务要求和作战对象不确定性程度的不断提升, 无人机打击任务与侦察任务已经密不可分, 而独立的打击任务已经很难应对复杂多变的战场环境.因此, 侦察与打击任务一体化的调度模式是现代无人机群军事作战任务的必然趋势.
1.1.3 察打一体化任务
现代无人机的作战任务流程一般为侦察、打击和评估, 即战前目标搜索、战时目标打击和战后毁伤评估三个步骤.针对这一任务流程, 为实现无人机作战"看得到, 打得到, 打得好"的战术指标, 现代无人机作战任务向着察打一体化的格局发展.然而, 察打一体化任务具有多样化的任务需求, 对参战无人机群的功能要求也较高.由此, 无人机群存在着两种不同的察打一体化任务协同方式.
传统的协同方式为同构协同, 即无人机群内所有成员的属性与功能一致, 该协同方式具有统一的问题描述方法与约束条件, 单机失效后其功能也较容易及时补充.例如, 美国航天航空研究院[19]借鉴带有时间窗约束的车辆路径规划问题, 综合分析了无人机最大续航时间和优先级任务需求, 建立了混合整数规划模型, 研究了双无人机察打一体任务调度问题. Zhen等[20]为无人机定义了能量耗尽前自主返回基地充能的工作策略, 直接提升了机群侦察与打击任务的续航能力.常一哲等[21]针对先进战斗机特点和未来中远距协同空战发展需求, 将空战能力划分为攻击能力与防御能力, 前者包括先敌发现、先敌打击与先敌摧毁能力, 后者包括机动能力、隐身能力与干扰能力, 实现了复杂任务环境中的无人机群侦察与攻击决策.
另一种协同方式是异构协同, 即无人机群内成员属性与功能存在差异, 该协同方式具有良好的功能多样性和任务适应性, 但约束性更强, 对任务调度的要求也更高.例如, 陈洁钰等[22]研究了无人攻击机和电子干扰机协同动态调度问题, 当攻击机探测到敌方雷达时则迅速触发干扰机的电子干扰.刘重等[23]研究了不确定环境下异构无人机群协同察打一体化的任务调度, 在满足机群同时打击目标的前提下提出了一种分阶次优联盟快速组建算法, 并采用Monte-Carlo仿真分析了无人机数量与目标数量对任务效果的影响.考虑到侦察机具备更远的雷达测距而攻击机拥有更强的挂弹能力, Deng等[24]建立了侦察机与攻击机混合的异构机群任务调度约束满足模型.吴蔚楠等[25]构建了侦察机、攻击机和察打一体机的异构协同无人机编队, 完成了对敌防空阵地识别、攻击和评估一体化的任务调度.戚泽旸等[26]考虑了无人机隐身性能和侦察代价, 分析了具备不同隐身能力、武器挂载能力和打击毁伤能力的异构无人机群协同任务执行效能.
可见, 无人机群任务调度技术已得到诸多研究与应用, 对提升无人机群智能化水平和多样化任务执行能力具有重要意义.同时, 现有研究也存在调度问题与通讯机制简化程度较高、异构协同多样性不足、大规模任务调度与调度系统研发涉猎较少等问题, 暴露出对无人机执行能力与策略、复杂需求、异构系统等约束描述能力不足的现状.由此, 下文对各类无人机集群调度问题中的关键性约束进行分类阐述, 为相关调度问题研究中的约束建模过程提供参考.
1.2 无人机群任务约束条件
无人机群在执行任务过程中的各类约束条件是限制任务收益的根本因素, 故无人机群任务约束的准确描述是开展优化调度的前提.无人机群智能调度问题的常见约束如图 3所示, 其中收益约束反映了无人机群执行任务的收益需求, 通常作为软约束或直接作为收益函数.除图中所示的通用任务收益外, 还包括无人机群侦察发现概率与覆盖率、毁伤与战损概率、战役全局价值等实际工程应用背景下的收益指标.
图 3 无人机群智能调度问题常见约束Fig. 3 Common constraints in intelligent scheduling for unmanned aerial vehicles1) 无人机资源约束
无人机资源约束是无人机群任务调度问题的基本约束, 主要包括无人机所携带的电量、油量及其续航能力等能源资源约束, 目标侦察、打击等机载设备资源约束, 以及通讯天线、频道及容量等通讯资源约束.
能源与续航约束是无人机执行任务的首要前提. Zeng等[27]规定了无人机油量耗尽前必须返回基地. Franco等[28]根据真实无人机单位时间功率曲线计算了飞行能耗约束值.李炜等[29]将无人机航行时间与最大航行时间的比值作为任务分配的影响因子, 达到航行极限的无人机将不再获得任务.韩国科学技术院[30]引入了无人机在服务点补充能量并继续执行任务这一实际工况, 从根本上提升了无人机群执行任务的可持续性.
在侦察与武器资源约束方面, 罗德林等[31]基于攻击目标至少分配一枚导弹的约束条件, 将无人机协同多目标攻击决策问题转化为导弹目标攻击配对的优化问题.陈洁钰等[22]研究了基于无人攻击机携弹量约束和电子干扰机雷达功率约束的异构协同动态调度问题. Kim等[32]将无人机携带的军事资源抽象为不同类型的资源单元, 设计了资源平衡、资源预留和资源分享策略引导了无人机群的任务调度.
在通讯资源约束方面, 张民强等[33]研究了通信距离受限情况下的无人机群协同目标搜索问题. Sujit等[34]考虑了无人机群通讯故障的不确定性情况, 并基于Monte-Carlo仿真模拟了机群通讯对任务调度效果的影响.针对通信延迟情况下的无人机群协同搜索问题, Mirzaei等[35]对通信不一致情况进行补偿, 减轻了延迟带来的影响.马纯超等[16]指出传统无人机任务调度很少考虑无人机基地通信链路约束, 故引入了地面站及通信覆盖范围约束、地面站最大可控无人机数等实际约束, 实现了8架无人机由3个地面站跨域联合控制指挥的任务调度仿真.此外, 无人机群的通信链路还需满足带宽、功率等现实约束.
无人机集群调度问题中对资源约束描述通常较为完备, 但大多基于确定性资源消耗的前提.而在无人机群实际的任务执行环境中, 机群的资源消耗往往具有一定的不确定性, 故针对资源不确定性的无人机群任务资源预测、调度鲁棒性研究也具有现实意义.
2) 时序约束
任务可执行时间窗、任务时效性和任务序列约束也是无人机群任务调度问题最常见的约束, 反映了无人机群任务调度问题的时序特征.美国国家航空航天局[36]很早就开展了多时间窗与资源约束下的无人机群调度问题研究.伍思远[37]以上海市杨浦区无人机安保任务调度问题为背景, 基于区域人口密度定义了无人机巡查周期的时间约束. Ramirez-Atencia等[38]考虑了无人机连续侦察任务中前序任务的时间与顺序约束.针对无人机群自主协同调度问题, 曹文静等[39]考虑了无人机感知、战场态势同步、决策与决策传递过程中的时间消耗与序列约束, 分析了基于工作流和基于多Agent技术的无人机群协同性能.
时序约束反映了无人机群调度场景中待执行任务的执行机会和逻辑关系, 但目前时间窗、任务截止时间和执行顺序等约束的提取往往较为简单, 以人为规划为主, 缺乏科学依据, 故此类约束建模过程还需要完备任务属性与需求的分析, 以及充分工程实践经验的支持.
3) 几何与动力学约束
在几何约束方面, Shima等[40]考虑了机载传感器探测距离和角度约束.仲筱艳等[41]考虑了无人机作战高度与作战半径约束. Khosiawan等[42]研究了区域目标成像捕获和货物投送等复杂任务调度问题, 并通过预处理技术将真实的室内房间结构转化为无人机可执行任务的区域模型.赵明等[43]借助数字高程模型(Digital elevation model, DEM)描述了区域空间的地貌形态, 在满足地形跟随和飞行高度约束的前提下开展了无人机群协同目标分配研究.
在飞行动力学方面, 晋一宁等[10]考虑了无人机飞行航向角和最大转弯角约束, 通过分散航向图引导机群规避碰撞, 实现了无人机群对目标区域的持续覆盖. Wang等[44]考虑了无人机航迹连续性因素, 借助Dubins路径连接模型求解了无人机群侦察点状与区域目标的混合优化问题.
在编队与协同方面, Zhen等[20]考虑了无人机群规避相互碰撞和障碍物的安全距离约束, 设计了飞行姿态调整规则, 完成了编队协同打击任务调度.针对异构无人机群对不同类型目标的侦察、打击与评估任务, 尹高扬等[45]建立了一体化协同任务分配的约束满足模型, 实现了敌机"发现即毁"的仿真战术目标. Gyeongtaek等[46]针对无人机物流配送问题, 考虑到货物重量超过单机配送承载极限, 设计了多无人机协同抓取货物的配送策略, 在任务调度中灵活地组合与调整无人机编队, 取得了满意的调度效果.
不过, 目前无人机群调度问题中的几何与动力学约束简化程度较高, 且受无人机类型及属性(如固定翼和旋翼无人机)影响显著, 故相关研究还应针对异构无人机行为与能力特点, 结合相关学科知识对转向半径、航速变化、编队结构保持、三维运动连续性等约束进行准确描述, 进一步提升问题建模的可靠性.
4) 收益约束
无人机群任务调度问题的收益约束主要包括时间收益、能耗收益和任务收益等.结合不同工程或军事需求, 收益约束通常以组合的形式作为调度问题的收益函数.
在时间与能耗收益方面, Gyeongtaek等[47]以最小化任务完成时间为优化目标.赵宏伟等[48]则对机群损耗和任务耗时赋予了不同的权重.李炜等[29]优化了无人机群对各类敌对目标打击的代价总和. Ramirez-Atencia等[38]以最低油耗、最短飞行时间和最小无人机出动架次为优化目标设计了约束满足优化模型, 对比了无人机数量、任务前序约束等对调度效率的影响.
在任务收益方面, Zhang等[49]以任务完成率和无人机群平均资源占有率为收益函数, 在基本任务合成与分层处理的基础上取得了良好的求解效果.郑晓辉[50]基于我方攻击态势和敌方抗击能力两个方面, 以单机对敌的优先权为基础约束, 以最大化无人机协同作战的效能和我方飞机总体优势为收益目标.刘毅等[51]以目标优先程度、目标打击效果上下限作为收益约束, 并以打击效果最大化作为收益目标, 开展了无人机群任务双层协同调度. Wu等[52]以毁伤不同属性的异构敌方目标为收益函数, 完成了动态环境中的无人机群最大作战效能优化.不过, 任务收益的量化及定义也需要充分的科学论证, 针对无人机群需求筹划与任务预处理的相关研究也应得到关注.
1.3 无人机群任务调度智能算法
针对小规模的无人机群任务调度问题, 启发式方法得到广泛运用并取得满意的优化效果.但在当今任务调度规模不断增加、任务需求和约束条件更加严格的背景下, 启发式方法很难取得满意的求解效果.而实践表明, 智能优化算法具有良好的收敛速率和优化能力, 是解决NP难问题的有效方法, 适合于解决无人机群任务调度中出现的"组合爆炸"问题.由此, 针对无人机群访问任务与察打一体化任务调度问题, 本节介绍一些常用的智能优化算法.
1) 蚁群算法
无人机群任务调度问题通常包含无人机航段的规划与调度, 故蚁群算法在此类问题中具有良好的适用性和拓展性.在访问任务方面, Zhang等[49]对基本任务进行合成并分层分配给无人机群, 再利用引入启发式规则的蚁群算法调度单机的任务序列. Perez-Carabaza等[53]通过栅格化无人机群的搜索空域, 将无人机运动划分为8个不同权重等级的方向, 并在迭代过程中引导无人机向累计概率权重高的区域移动.该算法取得了优于单一蚁群算法的收敛速度和优化质量. Gao等[54]设计了一种基于蚂蚁通讯的分布式蚁群算法, 分别设计了局部、全局和发现目标后的信息素更新策略, 提升了算法在无人机群大规模密集搜索问题中的自组织能力和收敛效果.
在察打一体化任务方面, Cekmez等[55]构建了无人机群执行任务过程中的无线传感网络, 结合CUDA (Compute unified device architecture)平台构建了一种并行蚁群算法.该算法在求解多目标复杂任务调度问题时表现出出色的收敛性. Zhen等[20]设计了一种自组织的分布式蚁群算法, 当无人机发现目标后立即实施打击活动, 同时更新全局信息素以引导无人机向未知区域搜索.针对无人机群作战任务环境的动态性、非线性和强对抗性特点, Wu等[52]提出了一种基于动态劳动分配的蚁群算法(Dynamic ant colony$ ' $s labor division, DACLD).算法在动态任务、不确定威胁和重调度任务中表现出高度的自组织性、快响性和灵活性.
2) 遗传算法
遗传算法以概率化的寻优方式获取和优化搜索空间, 具有良好的环境适应性、隐并行性和全局寻优能力, 适合于求解资源受限的强约束调度问题[56].
在访问任务方面, 美国国家航空航天局[36]混合使用了遗传算法和梯度投影法(Gradient projection method, GPM), 对带有时间窗约束的无人机群任务调度问题开展了早期研究. Ramirez-Atencia等[57]设计了一种多目标遗传算法, 基于多目标的适应度函数优化了无人机群在执行多区域目标访问任务中的油耗和任务完成时间. Wang等[44]设计了一种基于双染色体编码和多段变异的遗传算法, 有效增强了算法种群多样性, 提升了算法在大规模无人机访问任务中的收敛效果.
在察打一体化任务方面, Shima等[40]通过遗传算法实现了无人机群执行动态打击任务的仿真调度, 详细讨论了变异与交叉算子对收敛速度和效果的影响.针对无人机跨域飞行、信息共享而导致任务区域与规模扩大、引发任务分配难度增加的问题, 马纯超等[16]首先根据目标属性进行分组, 有效降低问题复杂度, 随后利用遗传算法生成局部最优解.该方法在较大规模的无人机目标分配问题中取得了良好的时效性和适应性.
3) 模拟退火算法
模拟退火算法是一种源于固体退火原理的概率演化算法, 受初始解质量和问题规模影响较小, 具有良好的渐进收敛性.在访问任务方面, 为提升模拟退火算法在大规模问题中的优化速率, Turker等[58]基于并行计算平台CUDA加速了模拟退火算法优化进程, 完成了高复杂性无人机群任务的有效调度.美国空军研究实验室[59]针对无人机群电磁作战场景, 应用模拟退火算法对机群任务进行了分配, 指出模拟退火算法虽然优化时间普遍长于遗传算法, 但在各类规模问题中均能取得满意结果.
同时, 模拟退火算法与遗传算法有良好的组合优化效果.赵宏伟等[48]考虑到无人机战场环境发生改变时, 任务收益和约束也随之改变的现实特点, 提出了一种基于在线仿真的无人机群任务调度方法, 并通过结合遗传策略的模拟退火算法完成求解.针对无人机群协同多目标导弹攻击决策问题, 罗德林等[31]对遗传算法中的子代个体进行模拟退火操作, 验证了该混合算法优于单一算法的收敛速率和收益效果.
4) 粒子群算法
粒子群算法在无人机群任务调度研究中应用广泛, 并常与其他启发式或智能算法混合使用.在访问任务方面, Gyeongtaek等[47]通过在粒子群算法中引入全局贪心策略, 有效缩短了无人机群任务调度时间.为避免粒子群算法陷入局部最优, 施蓉花等[60]在算法中引入交叉变异策略, 取得了显著优于使用单一算法的任务优化结果. Zhang等[61]还在算法中加入了自适应惯性因子, 在无人机群军事侦察任务中取得出色的调度效果.
在察打一体化任务方面, 刘毅等[51]设计了一种基于粒子群算法的交互式策略, 同时在迭代过程中引入定期初始化和保留历史最优值的机制, 有效摆脱了局部最优解的吸引, 完成了机群打击顺序、投弹量和打击时间的多目标优化.尹高扬等[45]通过矩阵编码的方式设计了一种多目标离散粒子群算法, 在协同任务分配的复杂约束环境下取得了良好的调度效果. Cao等[62]基于粒子群–鱼群算法和分布式拍卖策略, 实现了复杂时序约束和通讯约束条件下的分布式无人机群动态调度.石岭[63]针对粒子群算法易陷入早熟的缺陷, 在算法引入模拟退火策略, 验证了算法求解静态无人机群协同攻击任务的优越性, 并结合博弈论设计了复杂战场环境下的动态资源分配方案.梁国强等[64]设计了一种混合遗传策略的离散粒子群算法, 并将任务时序约束和多机协同约束融入到算法的粒子矩阵编码中, 有效求解了无人机群广域察打一体化任务的协同调度问题.
5) 分布式算法
在无人机群任务调度过程中, 基于并行、协同、通信和多Agent策略的分布式算法具备较强的问题导向性和可拓展性, 对降低无人机群任务调度规模, 提升优化速度和鲁棒性起到重要作用.
周小程等[18]考虑到无人机打击任务的强时效性, 设计了一种不公开出价的分布式拍卖策略, 出价高者直接赢得拍品, 有效缩短了动态任务到达后的调度响应时间.针对无人机通讯延迟问题, 曹攀峰等[65]提出了一种基于分布式预测模型(Decentralized model predictive control, DMPC)的分布式算法, 该算法通过引入缓冲周期和协商机制, 在恶劣多变的任务环境中表现出强鲁棒性和灵活性. Kingston等[66]设计了一种基于共识与协商策略的分布式算法, 算法在求解过程中可以灵活地增减执行任务的无人机数量, 具有较好的动态收敛性和优化能力.晋一宁等[10]提出了基于局部感知和局部通信策略的在线分布式覆盖算法, 算法促进了无人机系统对动态目标覆盖行为的持续涌现, 在机群和任务规模持续增加的情况下仍保持了良好的稳定性和调度效果.
除此以外, 还有人工鱼群算法[67]、狼群算法[68]、烟火算法[69]、合同网协议算法[70]等诸多智能优化算法应用于无人机群调度技术研究中.综上可见: a)智能优化算法在无人机群任务调度技术中应用广泛, 极大提升了无人机群任务调度问题求解效率; b)结合无人机群任务调度特点, 引入启发式、自适应、多种群、通讯交互和算法混合策略的智能优化算法在避免算法早熟、增强局部寻优能力和提升收敛速率方面起到重要作用; c)分布式算法缩小了无人机群调度问题规模、降低了问题复杂性, 实现了无人机由单智能体向智能集群的涌现行为.与此同时, 智能优化算法的鲁棒性问题也一直是影响其推广应用的重要因素, 而目前针对无人机群智能调度的鲁棒性研究还较少.未来研究应更多地关注无人机集群调度算法的鲁棒性特点, 为复杂任务调度问题的求解和机群调度系统的研发提供优质、可靠的算法支撑.
无人机调度与卫星调度在任务目的、约束类型与求解方法方面有不少相似之处.例如, 二者均包括以成像、侦察为主要目标的任务需求; 均需要满足几何与飞行约束、各类时间窗与时序约束以及飞行器所能携带的资源约束; 均需要通过智能优化方法求解集群带来的大规模任务调度问题等.由此, 结合本节无人机群任务调度问题与约束的分析思路, 下面本文将介绍多星任务智能调度技术.
2. 多星任务智能调度技术
编队或组网的卫星工作方式具有协同性能好、运行成本低、飞行效率高、执行任务可靠性高和适应性强等优点, 是卫星在轨服务形式的必然趋势.但卫星管理数量与类型的持续增长也带来了更大的问题规模和更多的约束冲突, 对卫星任务调度技术提出了新的挑战.本节梳理了多星任务调度的类型和主要约束条件, 并针对不同类型的调度问题介绍一些常见的多星智能调度算法.
2.1 多星任务调度类型
目前, 卫星任务调度通常分为成像任务调度和数传任务调度两类, 二者以独立调度为主.但考虑到卫星数储容量和任务时效性等实际约束, 为进一步发挥多星成像任务和数传任务的执行效率, 成像与数传联合的天地一体化任务调度技术也逐渐得到学者们的重视.
2.1.1 成像任务
多星成像任务调度是针对目标成像需求, 合理安排卫星及星载传感器、数储、能量等载荷资源, 有效消解任务与约束冲突, 以获得最大成像收益的过程.成像任务调度是多星任务调度技术的重要组成部分, 也是开展数传任务调度的重要前提.根据成像卫星轨道机动能力的不同, 卫星成像任务可以分为传统卫星成像任务和敏捷卫星成像任务两种.
1) 传统卫星成像任务
传统卫星是相对敏捷卫星而言, 只具备侧摆机动能力的一种卫星, 是目前成像卫星的主要形式.目前, 传统卫星在各类轨道上承担了大部分成像观测任务, 故基于传统卫星的多星成像任务调度依然十分重要.
传统卫星成像任务通常针对点目标和条带目标开展成像活动.点目标和条带目标相对于卫星成像幅宽较小, 能够被卫星单次成像的视场所覆盖, 常用于标识区域范围较小的重要目标.点目标与条带目标成像任务简单、可以一次性完成, 故许多成像目标常被简化为点目标、条带目标或其合成形式, 如图 4(a)和4(b)所示.由此, 传统卫星成像任务调度问题本质上是点目标与条带目标成像窗口与资源分配的问题.
图 4 敏捷卫星与传统卫星成像策略对比Fig. 4 Comparison on observation strategies between agile satellites and traditional satellites传统卫星成像任务调度问题中成像目标、资源和环境都是静态的, 但随着近年来成像任务中不确定性的不断增加, 以优先安排紧急任务、最小化任务总延迟为目标的动态任务调度和重调度策略也尤为重要.针对动态任务到达的问题, 刘洋等[71]研究了多星成像动态约束满足问题与求解方法, 以任务调整最少为优化目标实现了多星成像任务的动态调度, 但星群和目标规模均较小, 未能表现出大规模任务调度的适用性调度策略. Qiu等[72]在时域内周期性或基于事件地触发重调度, 并对比了不同优先级和启发策略影响下的算法求解效果.不过, 基于优先级的调度策略牺牲了低优先级的任务收益, 在动态事件触发频繁的情况下会影响调度效果.面向自然灾害等突发性成像任务需求, Niu等[73]基于动态分割策略划分成像区域目标, 对汶川地震灾区开展了仿真调度试验, 在自然灾害成像方面具有较强的应用价值. Skobelev等[74]结合Multi-agent技术, 将对地遥感星群成像任务调度问题划分为控制、数储、规划、轨道和可视化模块, 基于贪婪算法设计了考虑事件变化的动态任务调度系统.
国内外学者已针对传统卫星成像任务调度开展广泛研究, 但同时也暴露出传统卫星单次过境成像形式单一、对区域目标成像能力有限、资源利用率低、受轨道约束影响较大等问题.虽然多星联合成像调度技术的发展可以一定程度上避免上述弊端, 但仍很难满足如今不断增长的成像任务规模和多样化需求.所以, 在日益成熟的多星成像调度研究基础上, 发展轨道机动与成像能力更加灵活的敏捷卫星调度技术是未来多星任务调度研究与应用的必然趋势.
2) 敏捷卫星成像任务
与传统卫星相比, 敏捷卫星具有侧摆、俯仰、偏航三个轴向的快速机动能力, 在成像任务中表现出以下优势: a)成像时间窗口更长; b)任务与约束冲突消解方式更多; c)姿态转换更加灵活、快速.由此, 敏捷卫星在单次过境中具备更强的任务执行能力和执行效率, 其针对区域目标的成像方式与传统卫星有本质差别, 如图 4(b)和4(d)所示.对同一区域目标而言, 传统卫星必须借助多次过境或多星协同成像的方式, 而敏捷卫星可以在单次过境中通过多次姿态调整实现对其成像, 表现出强大的任务执行效率和多星联合执行任务的兼容性.另一方面, 敏捷卫星灵活机动的优势也增加了成像任务观测时间与序列的不确定性, 为敏捷卫星任务调度带来了新的挑战. Lemaitre等[75]最早提出了敏捷卫星调度问题, 考虑了敏捷卫星在对条带目标成像时的角度约束和姿态转换时间约束, 建立了数学模型, 对比了贪婪搜索、动态规划等启发式算法的优化效果.现有的敏捷卫星成像调度研究较多地基于单星单轨的形式[76], 而多敏捷卫星联合成像调度可以最大限度发挥敏捷卫星的轨道机动优势, 使成像任务收益获得更大提升.同时, 许多研究采用固定宽度的条带对区域目标进行分解, 但忽略了敏捷卫星频繁姿态调整过程中成像幅宽的变化.针对这一问题, 章登义等[77]设计了一种基于动态幅宽的区域目标平行条带动态分割方法, 取得了更高的条带拼接精度与综合成像效果.
由于在敏捷卫星成像任务调度问题中, 任务可见时间窗的选择属于离散决策问题, 而窗口内任务执行时刻的选择则是连续决策问题.故多数研究中依旧采用传统卫星的调度方式来调度敏捷卫星, 即优化过程仅决策到时间窗层面, 再利用启发式或约束消解策略决定任务在窗口内的开始时间[78-79].这样虽然降低了敏捷成像卫星任务调度问题规模, 但也限制了解的提升空间.实际工程中也有将任务可见时间窗进行离散处理的做法, 将问题转换为完全离散决策问题, 但离散化的程度也影响着调度精度与效率.此外, 敏捷卫星的高机动性同时也伴随着很强的时间依赖性[79-80], 准确描述敏捷卫星在不同情况下的姿态转换时间也是获取高质量、可靠调度解的必要条件.
2.1.2 数传任务
数传任务调度指卫星与地面测控中心分别分配天线传输资源, 将星上储存的信息数据通过天地链路传输给地面测控中心的调度问题.随着卫星技术的发展和任务需求的日益增加, 如今多星数传调度问题面临以下难点: a)卫星数量和任务数量较多; b)地面测控中心资源和可见时间窗有限; c)天地链路的数据传输带宽和允许传输的任务类型有限.可见, 多星数传任务调度也是一个具有NP难计算特性的复杂优化问题.所以, 合理的建模方法和有效的智能算法在求解多星数传调度难题中常常发挥着重要作用.下面, 介绍几种最常用的多星数传任务调度模型.
1) 整数规划模型
上世纪90年代起, 美国空军技术学院[81]就开始通过混合整数规划模型研究空军卫星控制网络(Air force satellite control network, AFSCN)的调度问题, 给出了多星数传任务调度问题的标准测试集.朱小满等[82]基于0-1整数规划模型, 通过启发式算法有效消解了多星数传调度问题的任务冲突, 实现了动态任务调度的快速求解, 但优化效果有待进一步提高.王沛[83]对多星调度问题中卫星耦合、地面站分离等约束条件进行了简化, 建立了累计收益最大化的整数规划模型.为求解大规模多星多站数传调度问题, Marinelli等[84]建立了基于时间指数的0-1整数规划模型, 并通过拉格朗日松弛算法取得了良好的调度效果, 该模型成功运用于欧洲航天局伽利略导航系统的数传任务调度中.
2) 约束满足模型
约束满足模型以决策变量的函数表达式作为约束条件, 对大规模多约束问题的简化和描述起到重要帮助.基于这一特点, Pemberton等[85]将卫星调度问题描述为包含任务、事件、约束和资源四个模块的约束满足模型, 得到了学者们的广泛认可.李云峰等[86]充分考虑了用户需求和问题约束, 在单数传任务模型的基础上建立了多星联合数传调度的约束满足优化模型, 并基于单数传任务和卫星数传的综合优先度有效求解了多星数传调度任务的优化问题.
3) 图论模型
图论模型通过点和线的方式简单而直观地描述问题本质, 处理方式多样、灵活, 在多星数传调度中运用广泛.针对意大利高分辨率雷达卫星星座COSMO-SkyMed, Bianchessi等[87]构建了基于有向无圈图的任务调度模型, 通过前瞻和回溯功能实现了大规模冲突消解和任务快速调度.针对同步轨道卫星群数传任务调度, Xu等[88]建立了最小生成树的图论模型.陈祥国等[89]构建了基于任务调度关系(弧模式)和基于任务调度位置(结点模式)的解构造图. Corrao等[90]提出了包含图论理论、混合遗传算法和线性规划模型的多星数传任务组合调度系统, 系统体现出良好的算法耦合效果, 在大规模数传任务调度中取得出色的优化结果.
除此以外, 还有Multi-agent模型[91]、Petri网模型[92]等应用于多星数传调度的研究中.不过, 数传调度问题往往建立在成像方案的基础上, 两者常常独立调度, 成像任务的调度结果作为数传任务的调度输入.考虑到成像任务与数传任务的高耦合性, 全局考虑成像与数传的天地一体化任务调度应当成为卫星任务调度科学研究与工程系统设计的首要调度形式.
2.1.3 天地一体化任务
卫星数传任务的调度依赖于成像任务的执行结果, 而成像任务的最终目的是通过数传调度的途径传输给用户, 故两者是密切相关、相辅相成的.传统的卫星成像与数传任务是独立考虑的, 而近年来随着星上存储技术和卫星调度技术的不断发展, 以及天地综合资源管控的迫切需求, 综合考虑卫星成像与数传活动的天地一体化任务调度问题得到了越来越多的重视.一体化任务调度的主要优势有: a)已成像的任务选择性数传, 有效缓解卫星存储容量的压力; b)先成像的任务拥有更多的数传窗口, 易满足时效性的任务需求; c)多圈次、阶段性或重复成像任务分批次数传, 可缓解任务与时间窗的约束冲突.但与此同时, 多星天地一体化任务带来了更庞大的任务规模、更多的时间窗约束和更加频繁的卫星姿态转换, 无疑对卫星任务调度技术提出了更高的要求.
Wang等[93]针对我国"环境一号"环境与灾害监测预报卫星, 研究了多星天地一体化调度混合整数规划模型, 基于一种启发式求解算法实现了多星成像与数传任务的一体化调度, 并在此基础上设计了任务与有效载荷管理系统. Li等[94]设计了多星天地一体化调度系统, 该系统可以同时对中轨道卫星、同步轨道卫星和倾斜同步轨道卫星进行联合任务调度, 体现出良好的适用性和鲁棒性.针对电磁探测卫星天地一体化调度问题, Chen等[95]以任务优先级、紧急任务完成率等为优化目标, 基于约束冲突消解和遗传算法对成像与数传任务实现了有效调度. Sun等[96]针对敏捷卫星的功能特点, 综合考虑了"实拍实传"、"立体成像"等复杂任务模式约束, 建立了多星多站成像与数传调度一体化约束满足优化模型, 并通过引入启发式规则的遗传算法取得了理想的调度结果. Zhu等[97]针对我国高分、风云、遥感和资源卫星异构协同问题, 建立了成像、数传和中继多星一体化任务调度约束满足模型, 并通过一种遗传退火算法完成了密集任务的有效调度.
天地一体化任务调度技术刚刚起步, 在学者们的共同推动下已取得一定的研究成果.但随着未来航天技术的不断发展, 还将有更多的具备各式各样功能和任务目标的卫星发射升空.这样一来, 持续增加的卫星与任务规模、更加拥挤的天地链路通道和各式各样的任务需求与约束条件将成为天地一体化任务调度技术未来发展的重要挑战.针对各类多星调度场景, 下文对多星任务调度问题中的关键性约束进行分类阐述, 为相关调度问题研究中的约束提取与建模过程提供参考.
2.2 多星任务约束条件
多星智能调度问题的常见约束与无人机调度问题类似, 如图 5所示, 其中收益约束反映了多星执行任务的收益需求, 通常作为软约束或收益函数.下面举例说明多星智能调度问题中典型的约束类型.
图 5 多星智能调度问题常见约束Fig. 5 Common constraints in intelligent scheduling for multi-satellites1) 卫星资源约束
与无人机资源约束相似, 卫星固存、电量, 以及任务执行时间、次数等约束是任务调度中最基本、最常见的约束形式.例如, Dilkina等[98]考虑了星上存储、能量限制等实际约束, 混合使用了基于排序策略的调度方法和约束传播方法, 求解了大规模点目标成像任务调度问题. Xu等[99]考虑了星上存储和连续工作时长等约束, 基于调度收益和资源消耗的优先级指标求解了敏捷卫星调度问题.针对可变轨卫星成像任务调度问题, Zhu等[100]优化了卫星最小变轨燃料消耗和最大成像覆盖率.邱涤珊等[101]基于卫星开机功率、开关机及状态调整耗能, 准确计算了卫星单圈次能量需求, 并在满足能量和固存资源约束的情况下对多星密集任务完成了有效调度.
同时, 卫星在执行数传任务的时候还存在地面数传中心及数传天线资源的约束问题. Wang等[93]综合考虑了地面站位置与天线资源等约束, 将多星成像与数传任务的一体化调度系统成功应用于我国环境与灾害监测卫星的调度中.
考虑到卫星可控时间短、重访周期长、太空环境未知性大等特点, 卫星资源的不确定性将对任务调度结果产生更大的影响.工程实践表明, 卫星在轨资源消耗常常与地面仿真结果相差较大, 造成部分任务调度方案无法执行的结果.故考虑资源不确定的卫星任务调度问题应得到重点关注.
2) 时间依赖性约束
多星任务调度具有很强的时间依赖性, 一方面体现在卫星成像与数传任务的时间窗口约束和任务序列约束中, 例如在条带拼接或立体成像任务中, 部分任务必须依次连续执行[76]; 在天地一体化任务调度中, 数传任务必须安排在成像活动之后[94], 且任务必须满足目标与用户的时效性需求等.
另一方面, 卫星成像相机、数传天线在执行任务过程中都需要调整和对准的过程, 故时间依赖性还体现在卫星连续执行任务的时间间隔上, 即卫星姿态转换时间受前序任务与后续任务状态的约束[102].例如Liu等[79-80]通过下式描述敏捷卫星成像任务的时间间隔:
$$ \begin{align} \Delta t = \frac{\Delta g}{v} + C(\Delta g) \end{align} $$ (1) 其中, $ \Delta g $为卫星前序任务与后续任务的综合姿态转角, $ v $为姿态转速, $ C(\Delta g) $为根据$ \Delta g $所计算的额外转换时间.可见, 在卫星执行任务过程中, 任意两个任务之间的转换约束均严格依赖于卫星执行任务的时间.不过, 目前研究中卫星姿态转换时间的计算以分段线性函数为主, 还不能准确地反映卫星机动过程中加速、均速机动、减速、稳定的四个过程, 且缺乏轨道动力学知识的验证[103], 故相关研究还需进一步深入.
3) 轨道与模式约束
与无人机不同, 卫星只能沿着既定的轨道飞行, 故卫星任务调度问题具有极强的轨道约束性.卫星调度问题中的轨道约束通常体现在时间窗口约束中, 即时间窗口中已包含卫星所属轨道信息.但为提升在轨执行任务的能力, 卫星通常具备多种工作模式.
针对高轨对地观测卫星多数传模式和长可见时间窗的服务特点, 经飞等[104]建立了基于最大收益比的约束满足模型, 采用启发式方法对一周内数传任务完成了多次调度. Chen等[105]考虑了成像卫星任务中"实拍实传"和"储存转发"两种实际工作模式, 有效消解了任务资源冲突, 在10颗卫星的联合调度试验中取得出色的调度结果. Sun等[96]针对敏捷卫星的功能特点, 综合考虑了"实拍实传"、"立体成像"等复杂任务需求, 求解了多星多站成像与数传一体化调度问题.
同时, 受卫星机动能力的限制和在轨稳定性的影响, 卫星姿态调整的幅度、频率、功率均应控制在额定范围内, 且不同工作模式的任务之间也需要一定的模式转换时间.此外, 由于卫星在轨服务周期长, 其飞行轨道会随着时间的推移发生变化, 故在轨道预报的基础上引入一定的不确定性因素有助于提升卫星长周期任务调度的可靠性.
4) 收益约束
收益约束代表用户对卫星完成任务效果和服务效率的基本要求, 也常直接作为调度问题的收益函数.最大限度完成任务、提升任务综合优先级、避免冲突始终是任务调度的根本目的.故与无人机群任务收益相似, 绝大部分研究中均将任务完成率、任务综合优先级或权重作为多星调度的首选收益指标.
在任务完成时间方面, Kim等[106]针对合成孔径雷达(Synthetic aperture radar, SAR)星座区域目标重复成像的调度问题, 以最小化系统响应时间为优化目标, 有效规避了约束冲突和目标成像重叠的问题. Zhang等[107]以最小化任务完成总时间为优化目标, 求解了多星、多轨多站的数传调度问题.
在成像质量方面, Verfaillie等[108]考虑了区域目标形状、面积和立体成像需求, 简化了Pleiades敏捷卫星区域目标成像调度数学模型. Liu[79]等针对用户成像质量的要求, 假设卫星成像质量是关于成像开始时间和最佳成像时间的分段线性函数, 开展了大规模任务场景下的敏捷卫星成像调度研究.成像质量还常与任务完成度、任务优先级同时作为收益约束或组合收益函数.
在动态任务影响方面, Li等[109]指出大部分数传调度问题集中关注约束冲突消解和调度收益最大化等问题, 他们针对紧急任务插入的动态数传任务调度问题, 控制了由紧急任务插入引起的总体任务延误, 实现了10颗卫星紧急数传任务的快响式调度. Wu等[110]将成像任务分为普通任务和紧急任务, 在确保紧急任务优先级的同时实现任务总收益的最大化. Chen等[95]以任务优先级、紧急任务完成率等为目标优化了多星天地一体化任务调度问题.
此外, 姜维等[111]还考虑了多星组网的任务风险要素, 对卫星在轨使用寿命进行了优化.现有的多星任务调度研究中, 通常对卫星各类约束条件进行了一定的简化.结合不同的实际工程需求, 还有诸多特殊的约束条件, 例如:出于用户特定要求, 某目标只能由指定卫星或在指定轨道内进行观测; 受限于传统卫星固存技术, 无法随时更新任务内存, 只能一次性格式化处理; 卫星存在"对日充能"和"对地定向"不同的能量消耗模式等.这些复杂的约束对研究者们提出了更高的问题描述与建模要求, 带来了更强的约束性和问题复杂性.为了应对上述问题, 智能调度算法发挥着不可或缺的作用.
2.3 多星任务智能调度算法
研究表明, 对于小规模的卫星任务调度问题, 启发式算法通常可以在较短的时间内获得满意解, 是工程系统中的常用方法.但随着问题规模的不断增长, 传统的启发式方法很难取得理想的求解效果[112].由此, 大规模的多星任务调度问题通常依赖于智能优化算法进行求解.常用的智能优化算法包括蚁群算法、遗传算法、模拟退火算法和粒子群算法等.
1) 蚁群算法
蚁群算法基于正反馈的搜索机制易于获得全局最优解, 在大规模、多目标的多星任务调度问题中得到很好的应用.
在成像任务方面, 邱涤珊等[101]针对密集点目标成像任务调度问题, 使用了一种借鉴蚁群系统和最大最小蚂蚁系统思想的蚁群算法, 并通过任务优先级、成像时间窗等因素调整转移概率, 实现了多星密集点目标成像任务的快速有效调度.针对双敏捷卫星成像调度问题, 严珍珍等[113]通过优化蚁群算法组件对问题进行了求解, 在大规模成像任务调度中取得了出色的调度速率和效果.陈宇宁等[114]针对双敏捷卫星成像任务调度问题, 在蚁群算法中加入信息素限制策略避免陷入局部最优, 实现了大规模点目标任务95 %以上的调度完成率.朱新新等[115]针对蚁群算法响应时间长, 易陷入局部最优的问题, 在初始种群中选择一种综合启发信息和扰动机制来生成任务链, 并用分类消减的方法进行时间窗更新, 验证了算法在成像任务调度中的可行性和优越性.此外, Gao等[116]设计了一种带有迭代局部搜索策略的蚁群算法. Wu等[110]在蚁群算法中引入迭代局部搜索策略, 在确保紧急任务优先级的同时实现了任务总收益的最大化.
在数传任务方面, Zhang等[117]提出了一种合作型蚁群算法(Cooperative ant colony optimization, CACO), 通过蚂蚁间的交流机制提高算法向更优解的转移概率.邢立宁等[118]在数传任务调度问题中混合使用了蚁群算法和导向局部搜索算法, 充分发挥了蚁群算法的全局搜索能力和导向搜索算法的局部寻优能力, 以最大化综合任务权重为目标完成了多天线地面站系统的数传任务调度.陈祥国等[89]在蚂蚁转移规则中引入伪随机概率, 通过划分数传任务的冲突集来限制蚁群的搜索邻域, 并限制信息素浓度在一定范围内以避免算法早熟现象.姚锋等[119]设计了一种演化学习型蚁群算法(Learnable ant colony optimization, LACO), 实现了知识模型和蚁群优化模型优势互补, 通过优化过程的知识挖掘进一步指导后续优化工作, 极大提高了算法寻优能力, 在大规模多星数传调度实例中取得出色的调度结果. Li等[94]针对蚁群算法优化初期信息素缺乏和早熟收敛的现象, 设计了一种基于遗传策略的蚁群算法, 很好地求解了多星天地一体化任务调度问题.
2) 遗传算法
在成像任务方面, Kim等[106]针对SAR星座区域目标重复成像的调度问题, 利用改进的遗传算法有效规避了约束冲突和目标成像重叠的问题, 取得了理想的求解速率和调度完成率. Hosseinabadi等[120]通过非沿轨的区域目标条带划分方式, 设计了多星成像重叠区域优先级调度策略, 减少了多星成像任务的重叠, 并通过遗传算法的求解显著降低了调度资源的消耗.孙凯等[121]建立了多敏捷卫星多圈次成像任务调度约束满足模型, 并将问题分解为任务资源匹配和单星任务处理两个模块, 分别通过学习型遗传算法和最优插入位置策略解决了这一问题.针对自然灾害的突发任务观测需求, Niu等[122]利用多目标遗传算法NSGA-Ⅱ (Nondominated sorting genetic algorithm-Ⅱ)对汶川地震灾区完成了多星多轨成像与条带拼接任务调度, 与历史数据对比取得了显著的成像效率提升.
在数传任务方面, 美国空军技术学院[81]针对空军卫星控制网络(AFSCN), 利用遗传算法完成了多星数传任务96 %的调度完成率, 该算法目前依然是求解该标准测试问题最为有效的算法之一. Xhafa等[123]设计了一种基于竞争策略的遗传算法(Struggle genetic algorithm, SGA), 通过在遗传过程中淘汰种群中的劣势个体, 并生成新的种群, 保持了进化过程中种群的多样性. Li等[109]混合使用了遗传算法和$ K $条最短路径算法($ K $-shortest path selection, KSPS), 有效控制了由紧急任务插入引起的任务总延误, 实现了多星紧急数传任务的快响式调度.针对数传调度中地面测控中心位置集中、资源争用冲突显著的问题, 周毅荣等[124]设计了一种免疫遗传算法(Immune genetic algorithm, IGA), 通过免疫记忆机制记录了周期性数传任务中的历史信息, 很好地求解了多星重访飞行中的数传调度问题; 并进一步提出了基于学习策略的遗传算法(Genetic algorithm with rote learning operator, GARLO), 算法在大规模多星多站数传调度中表现出优越的搜索效率、收敛速度和鲁棒性[125].
3) 模拟退火算法
在成像任务方面, 贺仁杰等[126]针对卫星成像任务合成特点, 在模拟退火算法中设计了随机扰动、重排列和重启动三种分化策略, 以实现对局部最优值的逃逸.黄瀚等[127]构建了多星天地一体化任务调度图论模型, 并在模拟退火算法中加入了精英解保持和二次搜索策略, 显著提升了算法的收敛性.
在数传任务方面, Xhafa等[128]指出模拟退火算法能够在多星数传调度问题中快速获得可行解, 在各类规模的任务场景中具有良好的适用性.他们还设计了考虑窗口、冲突、需求和资源的多目标禁忌搜索策略, 并验证了算法的时效性和鲁棒性[129].张超等[130]考虑了敏捷卫星大角度侧摆、同轨立体观测、多条带拼接等成像模式特点, 引入了基于观测质量的成像选择策略, 通过基于相似度和聚集度的遗传退火算法求解了10颗敏捷卫星成像任务调度问题, 并设计了交互式调度软件.
4) 粒子群算法
粒子群算法结构简洁、易于实现, 在多维问题求解中表现出寻优速度快、鲁棒性好等特点, 但也存在易早熟、易陷入局部最优的不足.
在成像任务方面, Chen等[131]提出了一种遗传粒子群算法, 求解了5颗对地观测卫星成像任务调度问题, 取得了显著优于传统粒子群算法的调度结果.汤绍勋等[132]针对7星4轨预警卫星侦察任务调度问题, 设计了一种离散粒子群算法, 采用基于优先级的粒子群初始化机制, 有效提高了算法对可行解空间的搜索效率, 取得了良好的调度效果. Zhu等[100]针对变轨多星多目标成像任务调度问题, 混合使用了粒子群算法和差分进化算法(Differential evolution, DE), 算法表现出显著优于单一算法的优化性能.
在数传任务方面, 常飞等[133]设计了一种自适应规模的粒子群算法(Adaptive scale particle swarm optimization, ASPSO), 根据种群多样性的变化对算法粒子自动增减, 并与传统的先到先服务算法进行了对比, 结果表明自适应机制显著提升了算法求解速度和优化质量. Chen等[105]提出了一种基于量子行为的粒子群算法(Quantum discrete particle swarm optimization, QDPSO), 并引入变异算子有效避免算法陷入局部最优, 算法在多星实时数传任务调度中表现出良好的寻优能力和收敛速度.针对分布式中继卫星系统的数传调度问题, 国晓博等[134]在粒子群算法中引入交叉、变异算子和方向回溯机制, 综合考虑了系统与中低轨卫星的时间窗、卫星剩余资源和数传任务属性等约束条件, 获得了良好的调度结果.
此外, Zhang等[135]以最小化地面站参与度为目标, 采用烟火算法对动态卫星数传任务进行了有效调度.经飞等[136]建立了考虑时间窗调整的多星数传调度模型, 设计了一种吱呀轮优化算法(Squeaky-wheel optimization, SWO), 在大规模数传任务调度中表现出大邻域导向式搜索特点, 在时间性、优化度等方面取得满意效果.针对敏捷卫星前摄式多目标优化调度问题, 李志亮等[137]在差分进化算法的基础上引入了遗传策略和外部存档更新策略, 降低了任务调度时间, 取得了显著优于使用NSGA-Ⅱ算法的优化结果.
可见, 智能优化算法在多星成像、数传及一体化任务调度中发挥着重要作用, 主要体现为: a)良好的全局寻优能力和问题求解效率, 适合于当前多星任务调度密集、大规模和强约束的问题特点; b)改进的智能优化算法在多星任务调度, 特别是动态任务调度中具有出色的可拓展性和鲁棒性; c)基于工程经验的启发式策略和基于约束推理的约束消解策略能够在有限时间内提升解的质量, 对引导算法寻优空间、提升求解速率起到重要帮助.同时, 智能优化算法在工程应用中也面临着鲁棒性与大规模场景优化能力欠佳等问题.由此, 结合调度任务工程背景, 有针对性地选择智能优化算法, 以及启发式、自适应、分布式和约束消解策略, 着力提升智能优化算法的鲁棒性, 对缩小多星任务调度问题求解空间、推动卫星管理系统的算法应用、提高大规模任务优化效率和任务调度的智能化水平起到十分重要的作用.
3. 结束语
以无人机和卫星为主的无人飞行器集群调度是复杂的NP难问题.通过本文对无人机群和多星任务调度问题特点、约束条件和智能优化算法的综述, 可见智能调度技术为无人飞行器集群任务带来了: a)更高的资源利用率、任务完成率和多目标的优化质量; b)更快的调度速率; c)更好的并行性、协同性和鲁棒性; d)更强的自主响应、动态响应和自适应能力等.由此, 智能调度技术对充分发挥无人飞行器集群优势、增强任务执行能力、提高任务执行率和资源利用率起到了举足轻重的作用.
同时, 未来日益增长的环境复杂性、需求多样性和任务复杂性也不断对无人飞行器集群调度技术提出更高的要求.对此, 未来无人飞行器集群智能调度的研究可以向以下方向发展.
1) 进一步提升调度技术智能化水平
虽然智能调度技术在无人飞行器集群调度研究中已得到充分应用, 但与未来无人机和卫星的集群管控要求仍有一定差距.例如, 目前文献中无人机或卫星集群数量普遍小于10, 而现阶段蜂群调度和数十颗卫星联合调度的实际需求已不在少数.无人飞行器集群调度问题的NP难特性决定了其很难在短时间内通过精确算法求解, 而关于不确定环境下无人飞行器集群智能调度方法的鲁棒性、实时性研究还不足.
针对上述现状, 无人飞行器集群调度的智能化水平还需进一步提升.无人飞行器集群智能化水平应包括集群任务的鲁棒性、自主性、自适应性、协同性和并行性等诸多方面.目前无人飞行器集群调度技术的鲁棒性问题是制约其工程应用与推广的关键因素.同时, 无人飞行器集群调度技术在大规模、长时效的任务调度中还大多保持着"人在回路"的调度模式, 特别是任务预处理和动态任务处理等方面尚不能完全离开人的决策.因此, 未来无人飞行器集群调度研究应进一步提升目标识别与预处理水平、分层调度和应急调度等方面的技术, 减少人为干涉程度, 提升人为决策的调度层级, 充分发挥低层级任务的智能调度水平, 进一步增强无人飞行器集群整体的智能化程度.
2) 提升异构无人飞行器集群协同能力
目前无人飞行器集群调度仍以同构飞行器调度或单一任务调度为主, 例如, 无人机察打一体化调度的文献中, 调度对象通常为具有侦察功能的侦察机、导弹攻击机和兼具侦察与打击功能的一体机等, 但真实情况下的空中指挥预警、电子对抗等关联任务调度通常被忽略, 涉及到的异构飞行器及其功能调度也被很大程度地简化.
针对日益增长的多样化、复杂化任务需求, 在目前无人机群与多星任务调度技术的基础上, 应充分发挥二者的任务执行能力与优势, 拓展资源与协同空间, 推动异构无人飞行器集群协同调度技术发展.现有的无人飞行器集群较多地集中于同构协同的方式, 虽然同构协同具有问题描述简单统一、飞行器失效后其功能较容易及时补充等优势, 但个体成员一致的功能属性也限制了集群全局功能的发展.相反, 以预警机、侦察机、攻击机和加油机组成的无人机混合作战编队就能够实现单一机群无法完成的远距离侦察、打击和保障任务.因此, 发挥异构成员的独有优势、实现成员间优劣互补、发展多元化的无人飞行器集群调度问题具有非常重要的价值.未来, 对遥感卫星与导航卫星、侦察机与轰炸机、攻击梯队与保障梯队等异构协同无人飞行器集群调度将成为现实需求.
3) 发展空天地一体化任务调度技术
空天地一体化任务调度技术与异构无人飞行器集群协同能力是相辅相成的.在现有研究中, 无人飞行器集群调度的一体化水平仍需提高, 例如卫星天地一体化调度的文献中常采取以成像任务序列为基础, 再安排数传任务的一体化决策模式, 分段式调度的思维仍然存在.同时, 由于无人机与卫星信息侦察与数据传输的共性, 二者存在一体化调度的基础和应用价值, 但目前尚无文献开展关于二者的一体化调度研究.
针对目前无人飞行器集群调度一体化水平不足、无人机与卫星协同应用较少等的现状, 全局考虑无人机侦察与打击任务、卫星成像与数传任务及相关不确定性的空天地一体化任务框架对提升集群任务的执行能力与可靠性具有重要意义.无人机群在执行任务的过程中, 数据信息也常通过卫星、地面站等途径进行传输, 故以无人机群构成的空域集群、由多星构成的天基集群, 与地面指挥控制集群具有联合运作的实际应用基础和发展前景.例如, 在未来信息化军事斗争中, 无人机群、卫星群、地面指挥与打击群必然是密切联动的, 对实时掌握战场态势、索取战场优先权和主动权起到十分重要的作用.由此, 综合考虑空域、天域、地域和时域的资源与约束条件, 降低各类约束中不确定性因素的影响, 发挥多装备、多平台耦合效应, 发展面向未来信息化工业与军事需求的空天地一体化智能调度技术势在必行.
4) 开发通用式任务规划与调度管理系统
通过本文对无人飞行器集群调度问题特点、约束条件和优化方法的综述, 各类无人飞行器集群调度模型与算法实际上具有很大的共性.但无人飞行器集群调度的工程应用背景促使了其调度模型与问题特征、邻域结构与算法改进措施紧耦合的现状, 在调度过程中缺乏统一的建模框架与模块化的系统设计思维.
将具有共性特性的无人飞行器集群调度问题纳入统一的建模与求解方法, 开发通用式任务规划与调度管理系统, 是无人飞行器集群调度智能化水平、异构协同能力和空天地一体化发展的出发点和落脚点.通用式的任务规划与调度管理系统区分问题建模与算法求解两个重要模块, 前者通过合理的简化与预处理技术将问题抽象为经典、常用的形式化问题模型, 后者则有针对性地选择、混合各类智能优化算法对问题模型进行解算与优化.建模与算法的分离设计有利于降低两者之间的依赖程度、提升系统的集成性、适用性和可拓展性.此外, 任务规划与调度的综合管理和支持人机交互的系统模式也是未来无人飞行器集群任务管理发展的重要趋势.
-
图 3 不同优先级数据流发生链路冲突情况一
Fig. 3 The first case of link conflict caused by data flows with different priorities
图 4 不同优先级数据流发生链路冲突情况二
Fig. 4 The second case of link conflict caused by data flows with different priorities
图 6 三种调度方法关于截止时间和实际调度平均时延数据对比图
Fig. 6 Comparisons between the deadlines and the actual scheduled average delays for three scheduling methods
图 7 不同网络规模下三种调度方法的调度成功率
Fig. 7 Success probabilities of scheduling for the three scheduling schemes in different network sizes
图 8 不同丢包情况下三种调度方法的调度结果
Fig. 8 Successful scheduling ratios of data flows for the three scheduling methods in different packet loss cases
表 1 模型中参数符号代表的意义
Table 1 Notations used in the considered model
符号 意义 Fi 第i条数据流 Ti 第i条数据流的周期 hp(Fi) 优先级高于Fi的所有数据流集合 Di 数据流Fi受到hp(Fi)影响造成的总延时 Ci 数据流Fi完成传输的截止时隙 Hi 数据流Fi端到端传输路径上的路由跳数 Li 数据流Fi的端到端传输延时 rHt 某条数据流在时隙t下剩余未传输的链路个数 
下载: 导出CSV
表 2 三种调度方法的平均执行时间(ms)
Table 2 Average execution time of three scheduling methods (ms)
网络规模 10个节点,
5条数据流20个节点,
10条数据流30个节点,
15条数据流40个节点,
20条数据流50个节点,
25条数据流60个节点,
30条数据流70个节点,
35条数据流EPD-C 21.4 89.9 195.6 311.6 491.4 737.9 973.9 LLF 24.7 100.5 215.6 391.6 625.5 943.9 1 215.5 RM 26.5 113.3 269.4 483.6 859.3 1 340 2 084
下载: 导出CSV
-
[1] Sha M, Gunailaka D, Wu C J, Lu C Y. Empirical study and enhancements of industrial wireless sensor-actuator network protocols. IEEE Internet of Things Journal, 2017, 4(3): 696-704 doi: 10.1109/JIOT.2017.2653362 [2] Begum K, Dixit S. Industrial WSN using IoT: a survey. In: Proceedings of the 2016 International Conference on Electrical, Electronics, and Optimization Techniques (ICEEOT). Palnchur, Chen Nai, India: IEEE, 2016. 499-504 [3] Wang Q, Jiang J. Comparative examination on architecture and protocol of industrial wireless sensor network standards. IEEE Communications Surveys & Tutorials, 2016, 18(3): 2197-2219 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=7b14c25bc9010a525f25c11d6c1db59d [4] Toscano E, Lo Bello L. Multichannel superframe scheduling for IEEE 802.15.4 industrial wireless sensor networks. IEEE Transactions on Industrial Informatics, 2012, 8(2): 337-350 doi: 10.1109/TII.2011.2166773 [5] Saifullah A, Xu Y, Lu C Y, Chen Y X. Real-time scheduling for wirelessHART networks. In: Proceedings of the 31st IEEE Real-Time Systems Symposium (RTSS). San Diego, CA, USA: IEEE, 2010. 150-159 [6] Kim Y G, Lee M J. Scheduling multi-channel and multi-timeslot in time constrained wireless sensor networks via simulated annealing and particle swarm optimization. IEEE Communications Magazine, 2014, 52(1): 122-129 doi: 10.1109/MCOM.2014.6710073 [7] Kang H, Zhao Y N, Mei F. A graph coloring based TDMA scheduling algorithm for wireless sensor networks. Wireless Personal Communications, 2013, 72(2): 1005-1022 doi: 10.1007/s11277-013-1052-9 [8] Kang B, Nguyen P K H, Zalyubovskiy V, Choo H. A distributed delay-efficient data aggregation scheduling for duty-cycled WSNs. IEEE Sensors Journal, 2017, 17(11): 3422-3437 doi: 10.1109/JSEN.2017.2692246 [9] 贾杰, 代恩亮, 陈剑, 王兴伟, 赵林亮.无线传感器网络中联合路由优化的高能效链路调度.电子学报, 2014, 42(6): 1118-1124 doi: 10.3969/j.issn.0372-2112.2014.06.013Jia Jie, Dai En-Liang, Chen Jian, Wang Xing-Wei, Zhao Lin-Liang. Energy-efficient link scheduling combined with routing optimization in wireless sensor network. Acta Electronica Sinica, 2014, 42(6): 1118-1124 doi: 10.3969/j.issn.0372-2112.2014.06.013 [10] 牛建军, 邓志东.基于马尔可夫链的无线传感器网络分布式调度方法.自动化学报, 2010, 36(5): 685-695 doi: 10.3724/SP.J.1004.2010.00685Niu Jian-Jun, Deng Zhi-Dong. Markov chain-based distributed scheduling approach for wireless sensor network. Acta Automatica Sinica, 2010, 36(5): 685-695 doi: 10.3724/SP.J.1004.2010.00685 [11] Sgora A, Vergados D J, Vergados D D. A survey of TDMA scheduling schemes in wireless multihop networks. ACM Computing Surveys, 2015, 47(3): 1-39 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=84249ad24dcfe9401e41c7781eade0a7 [12] 张晓玲, 梁炜, 于海斌, 封锡盛.无线传感器网络传输调度方法综述.通信学报, 2012, 33(5): 143-157 doi: 10.3969/j.issn.1000-436X.2012.05.019Zhang Xiao-Ling, Liang Wei, Yu Hai-Bin, Feng Xi-Sheng. Survey of transmission scheduling methods in wireless sensor networks. Journal on Communications, 2012, 33(5): 143-157 doi: 10.3969/j.issn.1000-436X.2012.05.019 [13] Rao S, Keshri S, Gangwar D, Sundar P, Geetha V. A survey and comparison of GTS allocation and scheduling algorithms in IEEE 802.15.4 wireless sensor networks. In: Proceedings of the 2013 IEEE Conference on Information and Communication Technologies (ICT). Thuckalay, Tamil Nadu, India: IEEE, 2013. 98-103 [14] 李金宝, 王蒙, 郭龙江. MR-MC无线传感器网络最小延迟数据聚集调度研究.通信学报, 2014, 35(10): 192-199 doi: 10.3969/j.issn.1000-436x.2014.10.022Li Jin-Bao, Wang Meng, Guo Long-Jiang. Minimum latency data aggregation scheduling in MR-MC wireless sensor networks. Journal on Communications, 2014, 35(10): 192-199 doi: 10.3969/j.issn.1000-436x.2014.10.022 [15] 牛建军, 邓志东, 李超.无线传感器网络分布式调度方法研究.自动化学报, 2011, 37(5): 517-528 doi: 10.3724/SP.J.1004.2011.00517Niu Jian-Jun, Deng Zhi-Dong, Li Chao. Distributed scheduling approaches in wireless sensor network. Acta Automatica Sinica, 2011, 37(5): 517-528 doi: 10.3724/SP.J.1004.2011.00517 [16] 王恒, 陈鹏飞, 王平.面向WIA-PA工业无线传感器网络的确定性调度算法.电子学报, 2018, 46(1): 68-74 doi: 10.3969/j.issn.0372-2112.2018.01.010Wang Heng, Chen Peng-Fei, Wang Ping. Deterministic scheduling algorithms for WIA-PA industrial wireless sensor networks. Acta Electronica Sinica, 2018, 46(1): 68-74 doi: 10.3969/j.issn.0372-2112.2018.01.010 [17] 王恒, 李敏, 刘其琛, 王平.一种基于确定性调度的工业无线网络路由算法.仪器仪表学报, 2011, 32(9): 1921-1928 http://d.old.wanfangdata.com.cn/Periodical/yqyb201109001Wang Heng, Li Min, Liu Qi-Chen, Wang Ping. Routing algorithm for industrial wireless network based on deterministic scheduling. Chinese Journal of Scientific Instrument, 2011, 32(9): 1921-1928 http://d.old.wanfangdata.com.cn/Periodical/yqyb201109001 [18] Saifullah A, Xu Y, Lu C Y, Chen Y X. End-to-end communication delay analysis in industrial wireless networks. IEEE Transactions on Computers, 2015, 64(5): 1361-1374 doi: 10.1109/TC.2014.2322609 [19] Industrial networks - Wireless communication network and communication profiles - WIA-PA, IEC 62601, 2015 [20] Leung J Y, Whitehead J. On the complexity of fixed-priority scheduling of periodic, real-time tasks. Performance Evaluation, 1982, 2(4): 237-250 doi: 10.1016/0166-5316(82)90024-4 [21] 王永吉, 陈秋萍.单调速率及其扩展算法的可调度性判定.软件学报, 2004, 15(6): 799-814 http://d.old.wanfangdata.com.cn/Periodical/rjxb200406002Wang Yong-Ji, Chen Qiu-Ping. On schedulability test of rate monotonic and its extendible algorithms. Journal of Software, 2004, 15(6): 799-814 http://d.old.wanfangdata.com.cn/Periodical/rjxb200406002 [22] Ayele A A, Rao V S, Dileep K G, Bokka R K. Combining EDF and LST to enhance the performance of real-time task scheduling. In: Proceedings of the 2016 International Conference on ICT in Business, Industry, and Government (ICTBIG). Indore, India: IEEE, 2016. 期刊类型引用(10)
1. 裘莹，张敬宣，柯杰，方梦园，徐伟强. 工业无线网络实时传输调度算法研究综述. 自动化学报. 2024(11): 2102-2127 . 
本站查看2. 王忠锋，张楠，夏长清，尚志军，田宇，金曦，许驰. 面向工业无线系统的实时聚合调度方法. 小型微型计算机系统. 2023(01): 204-210 . 百度学术3. 王恒，余蕾，谢鑫. 基于信息年龄的工业无线传感器网络混合数据调度方法. 电子与信息学报. 2023(03): 1065-1073 . 百度学术4. 郑静雅，安军社. SpaceFibre星载数据网络低延时确定性调度算法. 国防科技大学学报. 2023(02): 179-187 . 百度学术5. 程楠，朱国超. 考虑阴影衰落的无线网络拓扑离散优化算法. 计算机仿真. 2023(06): 435-438+503 . 百度学术6. 徐会彬. 一种基于链路信任的无线网络安全路由. 湖州师范学院学报. 2023(08): 62-68 . 百度学术7. 王恒，彭政岑，马文巧，李敏. 免时间戳交互的无线传感网隐含节点同步参数估计算法. 自动化学报. 2022(11): 2788-2796 . 本站查看8. 李兰英，蒋维成，周玲，黄静. 传感器网中基于角度的移动目标跟测方法. 计算机工程与设计. 2021(12): 3310-3315 . 百度学术9. 王恒，刘清华，李敏，谭帅. 考虑链路重传的工业无线网络确定性调度算法. 自动化学报. 2021(11): 2664-2674 . 本站查看10. 罗伟华. 面向5G的车载无线通信低时延信道节点调度方法. 贵阳学院学报(自然科学版). 2021(04): 12-15 . 百度学术其他类型引用(6)
-
下载:
计量
- 文章访问数: 1913
- HTML全文浏览量: 425
- PDF下载量: 224
- 被引次数: 16
