耿蓉, 张昭, 牛天水, 王宇飞
东北大学 计算机科学与工程学院，辽宁 沈阳 110169
收稿日期：2021-12-16
基金项目：中央高校基本科研业务费专项资金资助项目(N2116015，N2116020)；辽宁省医工交叉基金资助项目(2021-YGJC-24)。
作者简介：耿蓉(1979-)，女，辽宁沈阳人，东北大学副教授。

摘要：天基信息网中卫星资源有限，在轨升级难度大，链路间通信时延高，导致大规模并发任务处理效率低下.针对任务简单并发且每个任务由一个节点处理的情况，构建基于动态优先级的任务模型，对天基信息网计算与存储资源构建基于模糊聚类理论的资源模型.提出基于改进蚁群算法的天基资源调度策略，引入负载均衡因子，改变信息素更新规则，调整任务分配策略，结合Min-Min算法促进任务执行及资源分配.仿真结果表明，本文算法和对比算法相比，任务完成时间缩短29.2 %，任务累积价值高出37.9 %，资源负载均衡度缩小75.5 %，资源利用率高出22.4 %，验证了本文算法的优异性.
关键词：天基信息网任务动态排序资源聚类蚁群算法资源调度
Research and Simulation of Space-based Resource Scheduling Based on Improved Ant Colony Algorithm
GENG Rong, ZHANG Zhao, NIU Tian-shui, WANG Yu-fei
School of Computer Science & Engineering, Northeastern University, Shenyang 110169, China
Corresponding author: WANG Yu-fei, E-mail: yfwang@stumail.neu.edu.cn.

Abstract: The satellite resources of the space-based information network are limited.It is difficult to upgrade in orbit and the delay of inter-link communication is high, which results in inefficient processing of large-scale concurrent tasks. A dynamic priority-based task model is constructed for situations where the task is simple and concurrent and each task is handled by one node. A resource model based on fuzzy clustering theory is constructed for computing and storage resources in space-based information network. Space-based resource scheduling strategy based on improved ant colony algorithm is proposed. Load balancing factor is introduced. Pheromone update rule is changed. Task allocation strategy is adjusted. Min-Min-algorithm is combined to promote task execution and resource allocation. Simulation results show that compared with the comparison algorithm, the task completion time is 29.2 % shorter, the task cumulative value is 37.9 % higher, the resource load equilibrium degree is 75.5 % smaller, and the resource utilization rate is 22.4 % higher, which verifies the excellence of the algorithm.
Key words: space-based information networktask dynamic sortingresource clusteringant colony algorithmresource scheduling
天基信息网又称天基网络信息系统，由空间站、卫星等天基资源作为节点，构建网络系统，承载调度系统进行管理，将多种计算资源集和天基信息综合为一个整体信息系统^[1].
在天基信息网提出以前，各个卫星彼此割裂，能力有限，所有卫星数据通过星地链路传至地面处理后再反馈给用户^[2].该方式通信时间长，数据占用链路带宽大，任务时效性得不到满足，因此，提出天基资源调度策略，该策略可以减少地面接收和处理数据的时间，实现高效信息服务处理.天基信息网资源调度可分为以下4步：任务申请、任务预处理、资源预处理、调度策略实施^[3].
随科学技术的持续发展，各国之间不断制定战略和采用科技创新成果优化天基信息网，进而提高天基网络系统的稳定性和服务能力^[4].在天基信息网发展的同时，关于天基资源调度的研究也随之不断演进创新，成为该领域的重要研究课题.
早期卫星数量不多，调度算法相对简单，主要将重心放在优化调度技术的适应能力和效果上.Tiglao^[5]指出优先级队列调度能够为不同任务提供数量恒定的优先级，但在低优先级任务中会出饥饿问题，作者在路由器上打标记，确保高优先级任务得到执行的前提下，提高低优先级任务执行频率.Petraki等^[6]针对数字广播-频道返回卫星设计资源计算和资源分配两部分策略，设计确定最大吞吐量的高效算法，提升网络吞吐能力.Wang等^[7]设计一种适合低轨卫星的自适应资源分配策略，采用带宽预留共享设计和带宽自适应算法，动态预留带宽，实现带宽高效分配，保证带宽利用率，减少连接、断开率.
天基信息网逐步发展和完善，卫星数量逐年增加，大量任务并发执行，复杂性也逐渐增大，因此，多维性协同工作调度策略被提出，其中群智能优化算法^[8]脱颖而出.赵卫虎等^[9]提出基于自适应遗传算法的卫星资源调度技术，通过信息动态更新选择资源并开展调度，将适应度函数定义为与任务完成时间和权重有关的公式，利用遗传算法求解最优调度策略.Wang等^[10]针对共享卫星处理大规模任务时，基于遗传算法，在规定时间和频率内对任务进行排列，求解排序结果，实现求解低计算代价的优化方案，提升计算速度和资源利用率.
随研究不断深入，各****开始在调度时加入不确定条件.Dai等^[11]提出了一种实时动态调度(RTDS)方案，通过调度顺序调整和任务管理保证紧急任务的传输，提高调度效率.Mi等^[12]构建任务资源偏好函数，在双边偏好下提出一对一匹配模型，引入T - O GS和ATSM算法动态实现稳定匹配，降低计算复杂度，提高资源利用率.部分****提出了卫星资源虚拟化方案^[13].网络虚拟化^[14]和软件定义网络^[15]正逐步进入大众视野.Hasan等^[16]利用软件定义网络和网络虚拟化实现天基信息网中资源的多维融合.
近几年来，启发式算法也常被应用于调度研究中，蚁群算法由于采用正反馈机制、良好的鲁棒性、并行搜索且适应能力强等优点受到众多****的关注^[17].Qing^[18]将遗传算法和蚁群算法相结合进行车辆调度模型设计和参数选择，提高应急物流配送效率.孙頔等^[19]提出一种基于蚁群算法的舰船网络云资源调度方法，提高调度任务总效用，提升调度性能.Liu^[20]设计了一种基于蚁群算法的自适应云计算任务调度算法，在多态蚁群算法基础上，增加信息素自适应更新调整机制，提高算法收敛速度，有效避免出现局部最优解.天基环境中任务需求爆炸式增长，大量简单任务并发执行，资源有限且异构，对于将蚁群算法应用于天基资源调度的研究仍有缺口.面向天基环境特点对蚁群算法过于依赖初始参数设置、易陷入局部最优且收敛速度较慢^[21]等问题进行改进.综上，本文的主要研究内容概括如下：
1) 任务预处理阶段提出基于动态优先级的任务排序策略.按照任务的多维信息对任务动态优先级划分，根据天基信息网目标要求实现任务排序，保障任务高效执行.
2) 资源预处理阶段提出基于聚类理论的二次聚类策略.分析天基环境资源，对资源进行聚类，缩小资源搜索范围，降低时间开销.
3) 资源调度阶段提出基于改进蚁群算法的天基资源调度策略(IACO-RSO).包括引入负载均衡因子，改变信息素更新规则，调整任务分配策略，引入Min-Min算法等，从而减少任务完成时间、降低资源负载均衡度、提高资源利用率.
1 面向天基环境的任务和资源建模随天基用户持续增加，天基任务种类数量也在不断增大，而天基环境资源有限且异构，任务与资源匹配不均，难以实现高效资源调度.为实现不同区域卫星的计算、存储等资源合理调配，提高天基环境平台服务能力，需要根据天基信息网自身优势和用户需求，设计出面向多种任务并发的资源调度模型，如图 1所示.
图 1(Fig. 1)

图 1 资源调度模型Fig.1 Resource scheduling model

对天基环境下资源调度模型进行分析，应从任务建模^[22]和资源建模^[23]两个角度着手.在任务建模阶段，不同用户根据自身需求提交任务，如态势感知、情报获取、卫星接入、数据融合等，按照任务种类划分优先级，随后按顺序执行；在资源建模阶段，由于天基资源的差异性与独立性，对其进行分析和聚类划分，实现面向不同任务需求的高效动态资源管理.最后使用相关算法实现资源调度.
1.1 基于动态优先级的任务模型构建通过划分任务优先级，确定任务执行顺序，体现任务重要程度，大多数调度算法只考虑单一标准^[24]，如最短执行时间、最短空闲时间、最短截止期等.考虑到天基信息网复杂的工作环境，针对并发执行的简单任务，每个任务只被一个节点处理，为了满足用户提交的任务需求，减少任务完成时间的同时尽可能提高资源利用率.在满足任务截止时间约束基础上提出基于任务价值和紧迫程度的动态优先级排序策略.
1.1.1 任务模型用户随机提交多个任务，可以表示为任务集合T_all={T₁, T₂, ?, T_i, ?, T_n}，通过多维度定义单一任务T={T_id, T_deadline, T_value, T_preference, T_size, T_state}，分别代表任务id、最终截止时间、任务价值、对资源偏好情况、任务工作量大小及任务状态.
给定资源集合R_all={R₁, R₂, ?, R_j, ?, R_m}，其中，R_j={id_j, resource_j}，表示第j个资源节点.
时间矩阵表示任务i在资源节点j上预计需要的执行时间time_ij={t_ij|t_ij≥0, 0 < i≤n, 0 < j≤m, i?j}，其中，n为任务总数，m为资源节点个数.由于天基环境资源有限，任务数量与虚拟机数量相差悬殊.资源平均能力表示为resource_avg={mips_avg, stor_avg}，任务预计执行时间time_pre：

(1)

给定任务集合T_all和资源集合R_all，定义任务资源节点映射函数，每个任务只能被唯一资源节点处理：

(2)

通过1个n×m的二维矩阵表现函数的映射关系，如图 2所示.若某一行出现多次true，则该资源节点承担了大部分任务处理工作；若某一行出现多次false，则该资源节点在大部分时间处于空闲工作状态.资源节点会因为true和false分布不均而发生负载不均衡现象，进而降低天基资源使用效率.
图 2(Fig. 2)

图 2 任务与资源映射关系Fig.2 Mapping relationship between task and resource

天基环境资源有限，大量任务并发执行.定义F_time为所有任务中最大执行时间，F_j为第j个资源节点的执行时间，f_ij为任务i在资源节点j上的执行时间：

(3)

(4)

1.1.2 任务动态优先级划分1) 任务价值分析：是指任务被分配到资源节点上，处理后为整个天基信息网带来收益，价值越大，优先级越高.价值随任务执行而不断累积，若任务在截止时间前被处理，则其为系统带来的价值就是任务自身的固有价值；否则，其累积价值将作废，价值收益清零.
本文任务价值属于累积价值value(t)，随任务执行时间增加而增高：

(5)

式中：t_start为所有任务开始提交的时刻；t为当前时刻.任务在截止时间前被成功处理，那么该任务创造的价值就是T_value，ω为任务价值调节因子：

(6)

任务累积价值value(t)：

(7)

失败的任务不会为系统带来价值，还会浪费系统资源，甚至其他任务会因为等待而错过截止时间.因此，对即将执行的任务，应当考虑任务能否在截止时间之前完成执行，避免资源浪费.
2) 任务紧迫程度分析：天基信息网处理任务时，既要考虑网络价值收益，又要考虑任务执行成功率.因此，需要分析在截止时间的约束下，任务即将开始处理的进度情况，即任务紧迫程度.为了更加准确反映任务即将开始处理的紧迫程度，定义任务紧迫程度urgency(t)：

(8)

式中：time_pre为任务预计执行时间；T_deadline为任务截止时间；t为当前时刻.
任务未执行时，处于等候状态.任务紧迫程度会随时间推移而提高.如果任务预计执行时间与任务剩余可用时间相同，应当立即执行，否则会由于时间而执行失败，此时任务紧迫程度为1.对于未能在截止时间内完成的任务，产生的价值不计入系统总价值收益，对于任务执行失败而造成的资源浪费，本文不作考虑.
3) 任务动态优先级分析：任务执行前，优先级会随累积价值和紧迫程度发生变化.t时刻任务的优先级p(t)为

(9)

式中：θ为任务紧迫程度调节因子.任务被用户提交并对任务解析之后，按照优先级划分结果等待调度执行.根据天基信息网倾向不同，调整ω，θ因子改变任务优先级划分策略，使任务得到有效执行，因此，任务优先级排序是一个动态调整的过程.
1.2 基于模糊聚类理论的资源模型构建天基信息网资源具有差异性与独立性，实现高效的资源调度极具挑战^[25].在模糊聚类基础上提出资源二次聚类，使资源划分合理化，加快任务与资源匹配速度，促进资源调度.
1.2.1 资源模型定义资源集合R_all={R₁, R₂, ?, R_j, ?, R_m}，其中R_j={id_j, resource_j}，分别代表唯一表示号和工作能力.定义资源节点能力R_ability，由计算能力、存储能力综合计算可得：

(10)

式中：a，b为任务对资源性能指标的偏好系数，均不能为负，且a，b的和为1；mips为计算能力；stor为储存能力.为体现某一类资源综合能力，定义资源节点能力均值R_avg：

(11)

式中，n为该类内部资源总数.
定义类间相似度S_pq，表示聚类p和q之间的相似情况，可通过类间距离计算得出：

(12)

1.2.2 资源二次聚类分析1) 数据预处理：获取资源数据，构建天基资源数据矩阵，对资源矩阵进行无量纲化和归一化处理：

(13)

(14)

(15)

在式(13)~式(15)中：i=1, 2, ?, m；j=1, 2, ?, n；x_ij为资源节点i的第j个性能指标；x_j为第j个性能指标的均值；σ_j为该列上的资源标准差：

(16)

(17)

2) 模糊聚类：首先构建模糊相似矩阵，使用相关系数法处理归一化后的矩阵：

(18)

该矩阵只具备对称性和自反性，缺少传递性，因此采用闭包传递法求解模糊等价矩阵r_ij^*，进而求出聚类结果.传递闭包采用平方法求解：由n阶模糊相似矩阵r开始，依次求解r→r²→r⁴→?，直到满足r²ⁱ*r²ⁱ= r²ⁱ(2i≤n, i≤1b‖n)，r²ⁱ即为所求结果.设置不同的置信系数η，可以获得不同的聚类结果，η∈[0, 1]，η越靠近1，表示类内资源相似度越大.
3) 二次聚类：随实验数据增多，聚类结果随之增多，天基资源的异构环境导致模糊聚类效果下降，因而需要基于模糊聚类进行二次聚类，当两类资源相似度S_pq小于某阈值λ时，可将这两类资源归为一类，进而获得更加优质的资源聚类结果.
引入聚类调节函数f：

(19)

在聚类时需要不断调节η和λ，改变类内距和类间距的大小，得到更优的聚类结果.
2 天基信息网资源调度算法天基资源调度复杂度高、不确定性强.蚁群算法采用并行工作模式，通过传递信息素交流，仍存在局部最优和负载不均等问题^[26].本文在传统蚁群算法的基础上进行改进，提出能够满足资源调度目标的调度策略IACO-RSO.
2.1 任务分配策略蚁群算法工作时，蚂蚁先期随机搜索并分泌信息素，以正反馈机制完成天基资源调度.然而，算法前期信息素浓度不足，资源匹配效率下降，难以寻找最优解.本文将蚁群算法与Min-Min算法融合，Min-Min算法资源搜索速度快、复杂性低、可靠性高，降低蚁群算法前期搜索的盲目性.
经典蚁群算法任务分配存在局部最优问题.蚂蚁在完成任务与资源节点匹配时，信息素浓度越高的资源节点越容易被分配更多的任务，从而发生停滞现象，过早收敛到某个局部最优解.改进任务分配策略，在计算蚂蚁状态转移概率时，部分蚂蚁按照信息素浓度大小匹配，剩余蚂蚁随机分配.由表 1可知，将二者之比设置为8∶ 2，可以得到更好的全局最优概率.
表 1(Table 1)

表 1 不同比例下的全局最优概率Table 1 Global optimal probabilities at different proportions 测试函数 a∶b 实验次数 收敛到全局最优次数 全局最优概率 1 5∶5 50 12 0.24 6∶4 50 17 0.34 7∶3 50 20 0.40 8∶2 50 24 0.48 9∶1 50 21 0.42 2 5∶5 50 14 0.28 6∶4 50 19 0.38 7∶3 50 23 0.46 8∶2 50 30 0.60 9∶1 50 4 0.48 注：a∶ b为按照信息素浓度分配的蚂蚁数量和随机分配的蚂蚁数量之比.

表 1 不同比例下的全局最优概率 Table 1 Global optimal probabilities at different proportions

任务分配还涉及分配概率问题，本文采用轮盘赌算法.首先计算任务被分配至各个资源节点的状态转移概率，将其按照比例大小映射到转盘扇形位置上.转盘转动得到一个随机结果，该结果作为本轮迭代中蚂蚁给任务分配资源节点的最终结果.从而完成任务与资源节点映射，具体过程如图 3所示.
图 3(Fig. 3)

图 3 任务与资源节点匹配图Fig.3 Matching graph of task and resource node

2.2 负载均衡策略经典蚁群算法存在负载不均问题，因此改进负载均衡策略.根据蚁群算法每轮迭代过程中资源节点的负载情况，负载均衡因子L_j为

(20)

式中：T_j为资源节点j处理任务所需时间；T_avg为m个资源节点处理任务所需平均时间；T_max与T_min分别为m个资源节点中最大和最小任务处理时间.通过衡量T_avg与T_j的大小关系，决定下一轮迭代时该节点的分配概率，以提升资源利用率.
算法中蚂蚁的状态转移概率与路径信息素浓度和启发函数有关，启发函数η_ij(t)表示任务匹配到资源节点的预期程度.计算时引入负载均衡因子，作用于状态转移概率，减少资源节点过载和闲置情况发生，优化启发函数η_ij(t)为

(21)

用负载均衡度(LB)表征资源节点负载状况：

(22)

2.3 信息素更新策略蚁群算法凭借独特的正反馈机制，提高了收敛速度.每只蚂蚁完成一次匹配后，均应进行信息素局部更新：

(23)

式中：τ_ij(t)为资源节点原有信息素浓度大小；1/time_ij为信息素浓度变化增量.由于天基环境中链路时延较大，计算time_ij时还要考虑传输时延.
在本次迭代中，全部蚂蚁完成匹配后，需要对最优匹配方案更新信息素，增加优质路径信息素含量增强正反馈效果，即信息素全局更新：

(24)

(25)

式中：(1-ρ)×τ_ij(t)为信息素经过挥发后的剩余浓度；Δτ_ij(t)为本轮迭代中所有蚂蚁在任务i与资源节点j之间分泌信息素浓度之和.
信息素浓度随迭代次数增加不断增大，当达到一定阈值时，会覆盖启发函数的作用，造成正反馈过度.在后期加入正反馈抑制，强化算法搜索能力，找出优质解.
2.4 算法框架基于以上改进，算法伪代码如下：
IACO-RSO算法

输入：蚂蚁数量、资源节点数量、信息素浓度因子α、启发函数因子β、信息素挥发因子ρ、信息素常量、最大迭代次数. 输出：任务资源匹配列表及评价指标. 1.procedure IACO-RSO 2.antNum=k, TaskNum=m, ResourceNum=n, NC=0 3.利用Min-Min算法求出匹配方案局部最优解 4.根据局部最优解初始化任务与资源间信息素τij 5.将k只蚂蚁随机置于任务上 6.while NC < NCmax 7.while(antNum > 0) 8. ?????while(TaskNum > 0) 9. ????????计算蚂蚁状态转移概率，选出下一个执行的任务 10. ??????????????更新蚂蚁禁忌表(尚未执行任务列表)tabuk 11. ????????TaskNum—— 12. ????AntNum—— 13. ????记录蚂蚁匹配方案，更新局部信息素 14. ????NC++ 15. ????选出本轮迭代最优匹配方案 16. ????更新负载均衡因子和全局信息素 17.输出最优匹配方案和各项评价指标 18.end procedure

3 仿真与分析为检验改进蚁群算法在天基资源调度中的性能，基于CloudSim，IntelliJIDEA，MATLAB仿真软件进行实验.具体参数如表 2所示.
表 2(Table 2)

表 2 仿真参数配置Table 2 Simulation parameter configuration 参数 值 资源节点数量 20 任务数量 100~600 任务大小/MB 5 000~20 000 任务价值 0-1 计算能力/MIPS 500~1 500 存储能力/MB 512~2 048 最大迭代次数 200 蚂蚁数量/只 80 α 1.5 β 2.5 ρ 0.3 ω 2 θ 1

表 2 仿真参数配置 Table 2 Simulation parameter configuration

3.1 蚁群算法改进前后测试对比为了验证改进蚁群算法与传统蚁群算法的寻优效果的差异，同时判断改进点是否对算法性能有所提升，将改进蚁群算法和传统蚁群算法应用到同一测试函数中进行分析验证.选用两种测试函数进行对比实验.
测试函数1：

(26)

式中：x, y∈[-2, 2]；点(0, 0)为测试函数全局最优解，全局最优解周围存在多个局部最优解，该函数是典型的多极值函数，能够较好验证改进蚁群算法全局最优解搜索能力.设置蚁群总数为50，迭代次数为100.仿真50次求均值，绘制目标函数值随迭代次数的变化如图 4所示.对比发现：传统与改进蚁群算法目标均值分别为-0.093 32，-0.030 01；收敛到全局最优解次数分别为2，24.即传统蚁群算法信息素浓度随迭代次数增加不断累积，达到一定阈值后，覆盖启发函数的作用，陷入局部最优；改进蚁群算法修整了任务分配策略与信息素更新规则，搜索能力强，寻优能力提升.
图 4(Fig. 4)

图 4 蚁群算法改进前、后寻优能力对比Fig.4 Comparison of optimization ability before and after improvement of ant colony algorithm

测试函数2：

(27)

式中，x, y∈[-2, 2]，此函数的全局极小值为点(0, 0)，无局部极小值，整体变化较为平缓，该函数是典型的单极值函数.虽然无法检测算法寻优能力，但可以通过逼近测试函数最优解所需的迭代次数和最终算法获取的目标值求出收敛速度与精度.设置蚁群总数为30，迭代次数为300，仿真50次求均值，绘制目标函数值随迭代次数变化如图 5所示.对比发现：传统与改进蚁群算法目标均值分别为0.057 38，0.045 36；最优值分别为0.053 24，0.041 73；收敛至全局最优解次数相同, 均为30次，最终函数目标值十分接近，二者分别在156，75次收敛到全局最优解附近.说明在引入Min-Min算法后，弥补了算法初期信息素浓度较低的问题，降低算法前期搜索盲目性.
图 5(Fig. 5)

图 5 蚁群算法改进前、后收敛能力对比Fig.5 Comparison of convergence ability before and after improvement of ant colony algorithm

综上，改进蚁群算法在寻优能力与收敛速度均高于传统蚁群算法.
3.2 基于改进蚁群算法的天基资源调度仿真分析首先对二次聚类加以验证，然后对比先到先出算法(FIFO)、传统蚁群算法(ACO)及改进蚁群算法(IACO-RSO)，分别从多个性能指标验证算法性能优、劣.
1) 任务完成时间：在同一算法下，不同聚类的任务调度完成时间的对比如图 6所示.经计算二次聚类完成时间比普通模糊聚类减少17.8 %，因为二次聚类后，资源搜索范围变小，降低调度期间的搜索时间开销. 图 7展示了3种算法任务完成时间对比情况，经计算，IACO-RSO在完成时间上比两种对比算法平均值减少29.2 %.因为该算法引入负载均衡因子，资源节点负载更加合理，调整信息素更新规则和任务分配策略，搜索能力提高，任务完成时间最短.
图 6(Fig. 6)

图 6 不同聚类方式下任务完成时间对比Fig.6 Comparison of task completion time under different clustering methods

图 7(Fig. 7)

图 7 不同算法任务完成时间对比Fig.7 Comparison of task completion time of different algorithms

2) 任务累积价值：3种算法任务累积价值对比情况如图 8所示.经计算，IACO-RSO在累积价值上比两种对比算法平均值高出37.9 %.因为当任务数量增加时，FIFO保证部分任务及时执行，累积价值适中；ACO由于任务大量涌向资源性能较好的节点，导致错过截止期，累积价值较低，而改进后IACO-RSO引入负载均衡因子，避免大量任务因等待而错过截止时间，其累积价值最高.
图 8(Fig. 8)

图 8 不同算法任务累积价值对比Fig.8 Comparison of task cumulative value of different algorithms

3) 资源负载均衡度：3种算法负载均衡度的对比情况如图 9所示.经计算，IACO-RSO在负载均衡度上比两种对比算法平均值减少75.5 %.因为ACO多次迭代后，性能较优的资源节点负载过重，而性能较差的资源节点接近空闲，造成负载失衡，表现最差；FIFO按照先到先分配原则，每个资源节点的任务量相当，表现尚可；而IACO-RSO按照上一轮迭代的结果评估资源节点负载状况，根据资源能力大小分配合适任务，表现最佳.
图 9(Fig. 9)

图 9 不同算法负载均衡度对比Fig.9 Comparison of load balance of different algorithms

4) 资源利用率：3种算法资源利用率的对比情况如图 10所示.经计算，IACO-RSO资源利用率比两种对比算法平均值高出22.4 %.因为FIFO按任务到来顺序分配，各资源节点处理任务不均，无法有效利用全部资源，资源利用率最低；ACO多次迭代后，任务多数被分配至性能较优的资源节点，单个任务处理速度提高，但性能较差的资源处于闲置，资源利用率适中；而IACO-RSO根据资源性能及负载情况进行调配，保证资源利用率处于最高水平.
图 10(Fig. 10)

图 10 不同算法资源利用率对比Fig.10 Comparison of resource utilization of different algorithms

综上，本文提出的改进蚁群算法IACO-RSO在任务完成时间、任务累积价值、资源负载均衡度以及资源利用率多个指标均优于先到先出算法(FIFO)和传统蚁群算法(ACO).
4 结论1) 建立了与天基信息网体系结构相对应的调度模型.任务建模阶段，提出了基于动态优先级的任务排序策略；资源建模阶段，提出了基于聚类理论的资源二次聚类策略.
2) 改进蚁群算法，引入Min-Min算法，调整任务分配策略；引入负载均衡因子，改变信息素更新规则，给出改进蚁群算法的伪代码.
3) 仿真验证了改进蚁群算法的性能.由测试函数验证改进蚁群算法在寻优能力及收敛速度的高效性；从任务完成时间、累积价值、资源负载均衡度、资源利用率等方面验证了改进算法的优势.
参考文献

[1]	Lai J Z, Yu H Z, Zhang Z N. Research on multi-agent modeling method of space based network information system[J]. Journal of Physics: Conference Series, 2021, 1986(1): 1-7. DOI:10.3969/j.issn.1003-6148.2021.01.001
[2]	Chi L H, Lin C W, Lin W H, et al. Research on development of space-ground integration information network[C]// 2020 International Conference on Urban Engineering and Management Science(ICUEMS). Zhuhai: IEEE, 2020: 29-32.
[3]	汤勇. 面向云制造的服务组合与资源调度的优化研究[D]. 南京: 南京邮电大学, 2020. (Tang Yong. Research on service composition and resource scheduling optimization for cloud manufacturing[D]. Nanjing: Nanjing University of Posts and Telecommunications, 2020. )
[4]	Zong P, Kohani S. Design of LEO constellations with inter-satellite connects based on the performance evaluation of the three constellations SpaceX, OneWeb and Telesat[J]. Korean Journal of Remote Sensing, 2021, 37(1): 23-40.
[5]	Tiglao N. Utility-based enhanced priority scheduler for differentiated services[C]// First Asia International Conference on Modelling & Simulation. Diliman: IEEE, 2007: 187-192.
[6]	Petraki D, Anastasopoulos M, Cottis P. Dynamic resource allocation for DVB-RCS networks[J]. International Journal of Satellite Communications and Networking, 2008, 26(3): 189-210. DOI:10.1002/sat.908
[7]	Wang H Y, Gu X M. An adaptive bandwidth resource management scheme for multimedia LEO satellite networks[C]// 2010 Global Mobile Congress. Harbin: IEEE, 2010: 1-6.
[8]	Fei W, Liu C, Hu S. Research on swarm intelligence optimization algorithm[J]. Journal of China Universities of Posts and Telecommunications, 2020, 27(3): 1-20.
[9]	赵卫虎, 赵静, 赵尚弘, 等. 自适应遗传算法的数据中继卫星光网络资源调度算法[J]. 红外与激光工程, 2015, 44(4): 1311-1316. (Zhao Wei-hu, Zhao Jing, Zhao Shang-hong, et al. Adaptive genetic algorithm for data relay satellite optical network resource scheduling algorithm[J]. Infrared and Laser Engineering, 2015, 44(4): 1311-1316.)
[10]	Wang W J, Wei Z. Computational offloading with delay and capacity constraints in mobile edge[C]// 2017 IEEE International Conference on Communications(ICC). Paris: IEEE, 2017: 1-6.
[11]	Dai C Q, Li C, Fu S, et al. Dynamic scheduling for emergency tasks in space data relay network[J]. IEEE Transactions on Vehicular Technology, 2020, 70(1): 795-807.
[12]	Mi X R, Yang C G, Song Y B, et al. A distributed matching game for exploring resource allocation in satellite networks[J]. Peer-to-Peer Networking and Applications, 2021, 5(14): 3360-3371.
[13]	Gardikis G, Koumaras H, Sakkas C, et al. Towards SDN/NFV-enabled satellite networks[J]. Telecommunication Systems, 2017, 66(4): 615-628.
[14]	赵瑾. 天地一体化网络虚拟化资源管理技术研究[D]. 西安: 西安电子科技大学, 2020. (Zhao Jin. Research on virtualization resource management technology of space-ground integrated network[D]. Xi 'an: Xi 'an University of Electronics and Technology, 2020. )
[15]	Qin P, Liu H J, Zhao X N, et al. Software-defined space-based integration network architecture[C]// International Conference in Communications, Signal Processing, and Systems. Singapore: Springer, 2018: 449-458.
[16]	Hasan M, Dahshan H, Abdelwanees E, et al. Satellite ground station site diversity by optimizing SDN-enabled handover[J]. Journal of Engineering Science and Military Technologies, 2021, 4(1): 152-161.
[17]	熊超文. 蚁群算法的改进及其在路径规划中的应用研究[D]. 重庆: 重庆邮电大学, 2020. (Xiong Chao-wen. The improvement of ant colony algorithm and its application in path planning[D]. Chongqing: Chongqing University of Posts and Telecommunications, 2020. )
[18]	Qing C. Vehicle scheduling model of emergency logistics distribution based on Internet of things[J]. International Journal of Applied Decision Sciences, 2018, 11(1): 36-54.
[19]	孙頔, 王睿. 基于蚁群算法的舰船网络云资源调度[J]. 舰船科学技术, 2021, 43(3): 160-162. (Sun Di, Wang Rui. Ship network cloud resource scheduling based on ant colony algorithm[J]. Ship Science and Technology, 2021, 43(3): 160-162.)
[20]	Liu H J. Research on cloud computing adaptive task scheduling based on ant colony algorithm[J]. Optik, 2022, 258: 168677.
[21]	Yi N, Xu J J, Yan L M, et al. Task optimization and scheduling of distributed cyber-physical system based on improved ant colony algorithm[J]. Future Generation Computer Systems, 2020, 109: 134-148.
[22]	覃俊祥. 天基网络iSAT卫星体系架构设计及实现[D]. 长沙: 国防科技大学, 2018. (Qin Jun-xiang. Space-based network iSAT satellite system architecture design and implementation[D]. Changsha: National University of Defense Technology, 2018. )
[23]	Cao S Z, Wei J Y, Han H, et al. Space edge cloud enabling network slicing for 5G satellite network[C]// 2019 15th International Wireless Communications & Mobile Computing Conference(IWCMC). Beijing: IEEE, 2019: 787-792.
[24]	Khorsand R, Ramezanpour M. An energy-efficient task-scheduling algorithm based on a multi-criteria decision-making method in cloud computing[J]. International Journal of Communication Systems, 2020, 33(9): 1-17.
[25]	Wei C F, Zhang Y, Wang R Y, et al. Key technologies of space-air-ground integrated network: a comprehensive review[C]// International Conference on Mobile Multimedia Communications. Cham: Springer, 2021: 63-80.
[26]	Deng W, Xu J J, Zhao H M. An improved ant colony optimization algorithm based on hybrid strategies for scheduling problem[J]. IEEE Access, 2019, 7: 20281-20292.