基于改进蚁群算法的遥感信息处理负载均衡任务调度算法研究

2021-12-01白建东

计算机测量与控制 2021年11期

赵斐,陈昊,白建东,刘铁

(北京跟踪与通信技术研究所，北京 100094)

0 引言

遥感信息处理服务组合面临的关键问题在于对用户需求、遥感信息及其处理服务语义关联的充分准确理解，并在组合过程中利用这些语义控制处理服务的选择和构成复杂结构的服务链。遥感信息多任务服务链在线整合是一个并发执行调度服务与分布处理服务的过程，在多源异构与时空分布不均衡、网络环境动态多变、处理节点负载不均衡的服务执行环境中，遥感信息处理调度策略对于系统执行的整体性能最优至关重要。

自适应负载均衡是指无论系统处于空闲、稳定还是繁忙状态，负载均衡算法都会自动评估系统的服务能力，进行合理的资源分配，使整个系统始终保持较好的性能，不产生饥饿或者过载、宕机。自适应负载均衡有两个主要目标：保持较短的请求响应时间和较小的请求阻塞概率；负载均衡算法在可控级别，不占用过多的 CPU、网络等资源。自适应负载均衡建立在现有网络结构之上，它提供了一种廉价有效透明的方法扩展网络设备和服务器的带宽、增加吞吐量、加强网络数据处理能力、提高网络的灵活性和可用性，使用自适应负载均衡能够更合理的利用资源，提高运行性能[1-4]。

现有的自适应负载均衡算法主要分为静态和动态两类。静态负载均衡算法以固定的概率分配任务，不考虑服务器的状态信息，如轮转算法、加权轮转算法等，所以静态负载均衡算法不适合遥感信息服务链的优化与服务资源配置。动态负载均衡算法以服务器的实时负载状态信息来决定任务的分配，如最小连接法[5-7]、加权最小连接法[8-10]等，但是上述算法考虑的影响输入因子比较少，而且权值无法自动选择确定，所以对遥感信息服务链的优化也不适合。

本文提出了一种改进蚁群算法(EXACO)的整合负载自适应分配算法进行遥感信息服务链的优化与服务资源配置。蚁群算法(ACO,ant colony optimization)是一种用来在图中寻找优化路径的随机搜索寻优技术，它由意大利学者Marco Dorigo于1992年在他的博士论文中引入，蚁群算法在求解多种组合优化问题中获得了广泛的应用，如在计算机技术应用中，它可以作为网络路由控制的工具；在交通控制中，它成功地解决了车辆调度问题；在图表制作中，它被用来解决颜色填充问题。而为了使蚁群算法在进行任务调度时在不陷入局部最优解的前提下尽可能加速收敛，本文提出了一种改进的蚁群算法，引入模拟退火算法的思想对原有的蚁群算法做出一定修改：当蚂蚁k发现了一条最优路径并形成最优解X*后，随机交换两个资源所执行的任务作为扰动，产生一个新解X，通过模拟退火算法的方式决定保留最优解X*还是用新解X替换最优解X*；同时将改进蚁群算法应用于遥感信息服务链处理系统中去，从而实现遥感信息服务在线协同调度优化执行。

1 蚁群算法

蚁群算法的诞生主要来源于自然界蚂蚁觅食行为。蚂蚁的视觉十分有限，但却能依靠蚁群中每只蚂蚁在路径上释放的“信息素”这种物质在“黑暗”的外界环境中寻找到从洞穴通向食物的最短路径。蚂蚁在行走过程中不断地释放信息素来标识自己的行径，在寻找食物的过程中不断根据信息素的浓度选择行走的方向，最终到达食物所在的地方。由于每一只蚂蚁都有着各自不确定的行动路径，这导致较短路径上爬行的蚂蚁数量会比较长路径上爬行的蚂蚁数量多，从而使得较短路径上被蚂蚁释放的信息素浓度越高，后出发的蚂蚁总是趋向于往信息素浓度高的地方爬行。随着时间的推移，越来越多的蚂蚁聚集到最短的路径上去，这种动态的正反馈机制使得蚁群算法具有很好的鲁棒性。

蚁群算法最早用于解决著名的旅行商问题[11-12]，该问题可被描述为：某商人从一座城市出发，途径n座城市，最后再回到出发的城市，并且每座城市必须且只能经过一次，求一种旅行方案使得所需路径最短。该问题的数学描述为：设n座城市组成的集合为C={c1,c2,...,cn}，每两座城市之间的道路为R={rij|ci,cj∈C}，G=(C,R)是一个有向图，求有向图G的一条最短汉密尔顿回路[13]。

当蚂蚁k(k=1,2,...,m)出发寻找城市之间的最短路径时，会根据每条邻近路径上的信息素浓度来确定下一步通过哪条路径前往下一座城市。为了防止蚂蚁重复经过已到达过的城市，引入禁忌表tabuk(k=1,2,...,m)来表示蚂蚁k已经经过的城市，集合allowedk={0,1,...,n-1}-tabuk表示蚂蚁k下一步允许选择的城市，这一约束在自然界中的蚂蚁身上并不存在。蚂蚁k根据以下公式选择下一个到达的城市：

为了防止信息素在路径上的过度积累导致算法提前达到终止条件而结束，需要不断更新信息素。在τ+n时刻，路径rij上的信息素更新依据以下公式：

τij(t+n)=ρ*τij(t)+Δτij

其中:Q为常数，Lk表示蚂蚁k在本次循环中途经的总路程，参数α,β表示蚂蚁在运动中积累的信息和启发式因子在蚂蚁选择路径时所起的不同作用。初始时刻τij(0)为常数C，并且Δτij=0。参数Q、C、α、β、ρ均可以用实验的方式确定最优的组合。至于算法的停止条件，则可以设定为超过固定的循环次数或进化趋势不明显。

相较于遗传算法等其他启发式算法，蚁群算法具有以下特点[14-16]：

1)鲁棒性强。在算法的运算过程中，如果系统的状态发生了改变，蚁群算法仍然可以进行自我调整。例如蚁群当前的路径上出现了不可逾越的障碍物，蚁群仍然能够在一段时间的调整后重新找到新的路径。

2)自组织。蚁群中的蚂蚁在刚开始觅食时随机并且无序地寻找各自的路径，但随着时间的推移，每只蚂蚁个体之间通过信息素的作用开始互相影响，最后趋向于最优化的路径。

3)可并行。蚁群中每个蚂蚁个体的行为互不干扰，仅仅通过路径上的信息素进行通信，因此蚁群算法从本质上具备并行性，易于并行实现以改善算法性能。

4)扩展性强。蚁群算法可以与模拟退火算法等多种启发式算法结合使用，因此具备多种拓展后的变种蚁群算法。

蚁群算法的基本流程如图1所示。

图1 蚁群算法流程图

2 基于改进蚁群算法的遥感信息处理服务负载均衡任务调度算法

用户通过终端发出任务指令以后，需要对用户的任务需求进行快速地分析处理，来帮助用户高效快速地获得所需要的遥感信息产品，而遥感信息服务链动态构建技术即是来解决这一问题。遥感信息处理服务链是指从终端提出需求、卫星获取、处理、传输、信息分发到终端的信息节点构成的一条动态链路。

服务链动态构建包含两方面内容：依据任务的重要性对单个节点的执行序列动态调整，根据各节点的能力状况对链路动态调整。满足遥感信息“按需保障、随时随地保障”的需求，需要动态构建服务链，包括对卫星、星群的调度完成数据获取，动态调度链路上计算资源对获取到的(光学、SAR)数据进行处理生成数据产品等。服务链动态构建技术难点在于遥感信息处理涉及的服务链中星上处理能力，中间节点计算、存储及处理能力，端群的计算处理能力，网络节点多，可用能力动态变化，如何高效、快速完成信息处理。

负载均衡主要是进行合理的资源分配，使整个系统始终保持较好的性能，不产生饥饿或者过载、宕机。负载均衡任务调度问题可以被描述为：求一种最优的任务分配策略，将n个长度不等的任务T={T1,T2,...,Tn}按照某一策略分配给m个处理能力不同的服务节点S={S1,S2,...,Sm}，并且使n个任务的总完成时间C=max{c1,c2,...cm}达到最短。每一种分配策略都对应着该问题的一个可行解X，而具有最小完成时间的分配策略就是该问题的最优解。

蚁群算法适合解决各种离散问题，但是当问题规模较大时，蚁群算法在实际运用中容易遇到收敛速度慢、易陷入局部最优解的情况。使用基本的蚁群算法能够较好地解决任务调度问题，但是在实际应用过程中，可以针对特定的任务调度问题进行一定的策略和算法优化。

因此，将完成任务的时间跨度和节点负载均衡度综合起来作为衡量指标的目标函数为F(X)=LB(X)*C(X)。

为了使蚁群算法在进行任务调度时在不陷入局部最优解的前提下尽可能加速收敛，引入模拟退火算法的思想对原有的蚁群算法做出一定修改。

模拟退火算法(simulated annealing algorithm)最早由S.Kirkpatrick等人于1983年提出，是一种通用概率演算法。模拟退火算法的思想来源于固体退火的场景：当一个固体被加热到很高的温度后，便进入缓慢的冷却。在其升温阶段，固体内部的粒子随着温度的不断升高而变得无序，同时内能也在不断增大；在降温阶段则恰恰相反，固体内部的粒子会逐渐趋于有序。当冷却时间足够长，冷却过程中的任一温度下固体都处于热平衡状态。最终固体冷却到最低温度时其内能也达到最小[17-19]。自然界总是趋于能量最低，而分子热运动则趋于破坏这种能量最低的状态。基于这一理论，通过热平衡状态把内能最小化作为优化目标的算法就是模拟退火算法[20]。

在当前状态i生成状态j后，如果新的状态j的内能小于原状态i的内能，即Ej

接受新状态j，其中k为玻尔兹曼常数，这一准则称为Metropolis准则。

若将温度T作为控制参数，待优化的目标函数f作为内能E，固体处于某一温度Tx下的状态对应一个解x，则可将固体退火的思想应用于求解优化问题中。通过控制参数T的逐渐降低，目标函数f也随之降低，直至趋于全局最小值[21]。

模拟退火算法的初始参数包括：

1)控制参数T的初始值T0，即冷却开始时的温度；

2)控制参数T的衰减函数，最常见的一种衰减函数为Tk+1=<λTk，k=0,1,2，…。其中λ为常数，也称为退火系数，通常其取值范围为[0.5，0.99]；

3)控制参数T的终止值；

4)马尔科夫链的长度L，即任一温度T下的迭代参数。

模拟退火算法的基本流程如图2所示。

图2 模拟退火算法流程图

引入模拟退火算法思想当蚂蚁k发现了一条最优路径并形成最优解X*后，随机交换两个资源所执行的任务作为扰动，产生一个新的解X，通过模拟退火算法的方式决定保留最优解X*还是用新解X替换最优解X*：若ΔF=F(X)-F(X*)<0，则用新解X替换最优解X*；否则若ΔF=F(X)-F(X*)>0，则在0～1分布上依概率e-ΔF/T,决定是否用新解X替换最优解X*。其中，T为退火温度，初始值为T0，终止值为Tend。退火温度T按照T(t+1)=αT(t)进行迭代，其中α为退火系数。退火温度衰减到终止值时结束模拟退火过程，并依照蚁群算法信息素更新公式利用模拟退火过程得出的最优解X*更新路径上信息素，结束本次循环。当循环执行次数达到蚁群算法的最大迭代次数上限时，结束整个循环并输出结果。

基于改进蚁群算法的任务调度算法流程如图3所示。

图3 基于改进蚁群算法的负载调度算法流程图

3 仿真实验

为验证基于蚁群算法的整合负载自适应分配算法在遥感信息多任务服务链在线优化场景中的应用效果，通过云计算仿真平台，设定贴近遥感信息多任务服务链处理场景的任务负载、系统资源和调度算法，验证本文提出的基于蚁群算法的整合负载自适应分配算法的优化效果，并与传统遥感信息多任务服务调度方法的效果进行比对。

3.1 仿真平台介绍

仿真实验是在云计算仿真平台CloudSim环境下进行的。云计算仿真平台CloudSim是一个基于离散事件的云计算仿真工具箱。CloudSim是在网格仿真平台GridSim的基础上开发的，提供各种异构云计算资源、用户、调度算法等的模拟与仿真。

基于CloudSim平台仿真的主要步骤如下：

1)仿真初始化；

2)创建云计算资源和任务；

3)编写任务调度算法；

4)仿真启动；

5)仿真结束，输出任务完成情况，对结果进行分析与评价。

3.2 实验场景设计

基于改进蚁群算法的任务调度算法中的a，b，c分别代表节点的计算能力、内存和磁盘容量的重要性。一般来说，任务的执行受CPU的处理能力的影响较大，因此将a，b，c三个参数的值分别设为0.6，0.2，0.2。算法中蚁群算法部分的信息素挥发系数影响着算法的全局搜索能力和收敛速度两项指标，综合考虑后将其确定为0.5。参数α与β分别决定了信息素和匹配因子的重要程度，蚂蚁数量m决定迭代的次数，退火系数λ决定退火的速度。根据经验取参数α=1，β=2，m=10，λ=0.95，T0=10 000，Tend=1 000。

表1 算法各项参数设置

为对比不同算法的任务调度效果，选择轮询算法、遗传算法和改进蚁群算法进行比较。在仿真开始前，利用CloudSim Plus创建20个节点。为模拟真实环境，每个节点具有的计算能力采用随机生成，分布于1 000至6 000 MIPS之间。根据任务数的不同，随机生成任务长度同样采用随机的方式生成，分布于50 M至200 M之间。根据任务数量的不同将实验分成五组，五组实验的任务数分别为100、200、300、400、500。为尽量降低随机数据的偶然性对实验结果的影响，多次进行实验并取平均值作为每组实验的结果。

表2 CloudSim属性设置

3.3 实验结果及分析

图4为使用不同种算法调度各组任务的总完成时间。

图4 各算法执行不同任务数的总完成时间

图4中横坐标表示每组实验的任务数，纵坐标表示各组任务在分别不同调度算法下的总完成时间。由图可知，基于改进遗传算法的调度结果较其他对比算法具有更低的总完成时间。同时，随着任务数的增多，该算法的优势越来越显著。

为比较各节点在执行任务中的负载情况，在实验过程中记录下每个节点运行任务的总长度，针对每个节点计算其负载的任务总长度与其计算能力的比值。以执行100个任务时产生的实验数据为例，将得出的结果绘制如下统计图：

图5中，以“■”标记的折线反映了使用轮询算法调度任务后各节点的负载情况，以“●”标记的折线反映了使用遗传算法调度任务后各节点的负载情况，以“▲”标记的折线反映了使用改进后的遗传算法调度任务后各节点的负载情况。由上图可知，轮询算法与蚁群算法在进行任务调度时由于没有充分考虑节点的负载均衡问题，各节点的负载水平相差很大，这一点在使用遗传算法后得到了些许改善，但我们可以很明显地看到使用改进后的蚁群算法时，各节点的负载程度相对均衡。为定量对比上述算法在负载均衡方面的表现，可以使用标准差来分析上述数据，如下公式：

图5 任务数为100个时各算法的节点负载均衡情况

分析以上实验结果可以得出，遗传算法和改进的蚁群算法相较于轮询算法而言，在任务总完成时间和节点负载均衡性上都有较好的表现。轮询算法由于其简单的策略，不可避免地会出现将较长的任务分配给计算能力较弱的节点的情况，造成任务的堆积，而延长了全部任务的总完成时间，这样还会造成系统中各节点负载不均衡。遗传算法相较于轮询算法能够在一定程度上优化任务的分配，使得全部任务的总完成时间减少。基于改进的蚁群算法较好地避免了蚁群算法容易陷入局部最优解的问题，并且进一步减少了任务总完成时间。同时，在任务分配时考虑了节点实际负载情况，使得系统中各节点的负载趋于平衡。实验结果表明，基于改进蚁群算法的负载调度算法在针对遥感信息服务链处理调度的场景下具备更优的效果。