邵苏杰 吴 磊 钟 成 郭少勇 卜宪德

①(北京邮电大学网络与交换技术国家重点实验室 北京 100876)

②(国网河北省电力有限公司雄安新区供电公司 雄安 071600)

③(国网智能电网研究院有限公司 南京 210003)

1 引言

随着物联网的发展，边缘设备大规模普及，其数据逐渐呈现海量异构、处理复杂等特点，对业务的实时性和可靠性也提出了更高的要求[1]。云平台与边缘用户的远距离通信产生过大传输时延，业务时响应不及时，难以满足业务QoS[2]。边缘计算作为一种分布式的数据处理和存储架构被提出，协同云计算提供就近服务[3]，为处于边缘的业务提供更快的响应时间和更低的带宽成本以及更好的数据隐私性[4,5]。然而，与云服务器相比，边缘服务器在处理、存储和通信等方面的资源相对有限，难以在单独节点中承载复杂的物联网(Internet of Things)应用[6]。

随着微服务架构的提出[7]，复杂单体应用被分解为更细粒度且松散耦合的微服务集合，每个微服务集中实现一种功能，多个微服务结合成为工作流形式的组合服务，以提供完整的业务请求。为高效利用边缘侧资源，容器技术作为一种轻量级的虚拟化技术，成为微服务部署的绝佳选择[8]，它将微服务封装在容器中并实现资源隔离，可在资源受限和异构的边缘服务器中部署多个容器实例，为完成业务的并发请求提供多种服务选择方案。前驱微服务的选择策略将直接影响工作流中后续所有微服务的完成时间，请求中关键微服务的阻塞很有可能导致请求的整体执行时间超过预期，降低用户服务质量。此外，基于边缘计算的分布式特性，部署在网络距离较远的边缘服务器上容器实例之间的通信，将造成通信时延和网络资源消耗的增加。因此，相比线性结构的服务选择而言，边缘微服务选择问题需要考虑到微服务之间的依赖关系以及并发请求对容器实例的竞争关系，如何在边缘环境下为基于工作流的并发请求制定最优的服务选择策略成为难题。

近年来，国内外学者针对边缘环境中的服务选择问题做了研究，文献[9]提出一种感知延迟的微服务混搭方法，在移动边缘计算中为应用程序提供微服务的最佳配置，有效保证了时延并显著降低网络资源消耗，但只考虑了简单串行结构，未考虑复杂工作流形式的应用架构。 文献[10]采取工作流形式描述复合服务，结合实例处理速度和任务并发度，提出一种基于列表的微服务选择算法，能有效保障业务服务质量，但没有考虑边缘环境的特性。文献[11]提出一种基于最短路径的性能感知服务路径选择方法，综合了微服务实例的计算能力和微服务实例之间的传输条件以及任务特性，提高了整体效率，但无法满足并发场景。文献[12]基于带约束的多服务选择的基本模型，将问题转化为一系列等价线性规划子问题，提出一种公平感知的并发服务选择算法，通过有限次的线性规划迭代，为并发请求提供目标服务，并获得更高QoS，但同样只考虑了简单结构的服务请求。文献[13]基于李雅普诺夫优化以及马尔可夫近似提出一种CSS(Composite Service Selection)框架，在移动环境下优化网络服务的组合，最小化整体组合服务请求的总体响应时间，但没考虑单个服务实例的请求队列调度，难以实现全局优化。

基于此，本文提出一种基于优先级机制和改进蚁群算法的边缘微服务选择方案，本文的主要贡献如下：

(1)根据边缘计算场景特点，本文结合微服务依赖关系，构建基于容器的边缘微服务选择3层架构，并基于此建立了时延模型和网络资源消耗模型，以求最大化满足约束时延的请求数量，并减少网络资源消耗。

(2)考虑并发请求对容器实例的竞争性，引入优先级机制，利用工作流拓扑优化任务调度顺序，并采用改进蚁群算法的全局优化形成最优决策。利用真实的工作流对算法进行了评估，与基准方案相比，本文方案能有效满足并发请求QoS。

2 系统模型与问题表述

2.1 系统架构

基于容器的微服务选择架构如图1所示，该架构被划分为应用层、容器实例层及边缘节点层。

应用层包含一系列开发人员以微服务架构开发的边缘业务，这些业务被分解为一组互相依赖的轻量级独立微服务，并遵循工作流的执行逻辑，即后驱微服务必须等待其所有前驱微服务完成并传递数据才可开始执行[14]。依次执行该业务包含的所有微服务才视为一次请求的完成。

为避免单个节点宕机无法提供可靠服务，容器实例层抽象底层物理资源创建容器实例承载用户请求。同一业务的并发请求争用容器实例，容器实例同一时刻只能执行一个请求，选择该实例的其他请求将在该实例上排队[15]。当现有容器实例队列过长无法满足当前并发请求时延约束时，也可从云中镜像仓库下载微服务基础镜像，打包所需编译器、开发库和配置文件等组件创建新的容器实例扩展服务能力[16]。

边缘节点层旨在为用户提供分布广泛、快速高效的计算资源。节点分布在不同的地理区域，由各类异构设备组成，如无线接入点、网关或高性能服务器[17]，拥有不同容量的CPU、内存等资源。边缘节点内嵌容器管理平台，如docker和LXC，以管理本地容器实例[18]。

以图1为例，业务1包含的6个微服务[A,B,C,D,E,F]分别在不同边缘节点创建多个容器，当用户对业务1发起请求，经过决策为该请求包含的6个微服务分别选择[A2,B1,C3,D2,E1,F1]形成完整执行路径。

2.2 系统模型

2.2.1 应用模型

2.2.2 边缘节点模型

边缘集群定义为一组PM(Physics Machine)组成的物理网络，网络中的异构服务器可以抽象为具有不同资源容量的边缘节点EN ={EN1,EN2,...,ENN}，E Nn的 资源向量表示为={,,...,}，其中表示E Nn中第r类资源的容量。创建实例需要保证该节点的可用资源容量超过实例的各类资源需求，定义微服务的资源需求向量为=

2.2.3 时延模型

(1)传输时延。对于边缘环境中的服务请求，传输时延主要考虑用户上传数据的时间、选中容器实例之间的数据传输时间和返回结果的时间，用户上传数据的时延包括端口速率引起的传输时延和传播时延。假设请求上传的平均数据大小为din，用户与边缘节点的平均带宽为W，则用户将输入数据全部上传到边缘节点上的时延表示为

其中，TP代表用户设备的传输功率，H代表用户设备与边缘节点的信道增益，δ2代表噪声功率；D代表用户设备与边缘节点的物理距离，t ran(EN,U)代表无线信道的传播速度。而由于边缘节点的下行链路带宽通常远远大于上行链路带宽，且业务结果数据量较小，因此忽略返回结果的时间。

网络中的每对边缘节点彼此之间通过路由联通，很明显部署在不同节点上且具有依赖关系的容器实例之间数据传输时间由数据传输量和传输速率决定。

定义二元变量xikn

(2)执行时延。本文假设微服务处理的数据是其所有前驱微服务传输给它的数据之和。一般来说，相同微服务的不同容器实例在异构服务器上的执行时间与该服务器的CPU处理速度有关。假设容器实例I(a,i,k)所 在节点CPU处理速度为，则该实例上任务的执行时间定义为

(3)排队时延。容器实例同时只能执行一个请求，容器实例有一个请求队列来缓存选择实例的任务，队列中的这些任务按顺序执行。因此，在选择容器实例时，需要考虑实例的请求队列，如果选择实例I(a,i,k)，则必须等待队列中其他任务的执行，如果队列中没有其他任务，则无需等待，排队时间=0，否则队列中所有任务的排队时间可以迭代计算为

(4)总时延。每个任务都必须等到其所有前驱任务完成后才能执行，任务本身就绪时间是其所有前驱任务的完成时间和前驱任务之间的通信时间，计算如下

假设不消耗其他加载时间，则可以在获得实际开始时间后计算实际完成时间

由于业务由具有复杂拓扑结构的微服务组成，请求的完成时间不是每个任务的执行时间和传输时间的简单累积，而是取决于出口任务的完成时间，即F Tq=FT()。

2.2.4 网络消耗模型

用Dis(ENn1,ENn2)表示两个节点之间的最短跳数，源节点和目的节点之间跳数越多，数据将通过更多中间路由传输，从而消耗更多的网络资源。若是的前驱任务，则进行数据传输的网络消耗计算为

此外，创建新容器时从云端下载微服务镜像也会造成较大的网络资源消耗，假设选定边缘节点与云之间的距离为D is(ENn,cloud) ，为的镜像数据量大小，则创建新容器实例所消耗的网络资源为

综上，完成一个请求所消耗的网络资源为请求的所有任务之间的数据传输和新建容器的网络消耗之和

其中，c ta,i代 表是否创建新的容器实例。

2.3 问题描述

基于上述系统模型，本文希望找到一种合理的微服务容器实例选择策略，在考虑任务依赖性和高度并发的情况下，最大限度地保证用户QoS，提高在延迟约束下完成的请求数量，并减少网络资源的消耗。因此，边缘微服务选择问题可以定义为目标

约束条件C1和C2表示容器实例是任务分配的最小单元，每个任务只能由一个实例执行；C3表示所选边缘节点必须有足够的资源部署微服务实例，如果任一类资源不足，则无法放置容器实例；C4限制了每个任务的开始执行时间，任务必须等到其每个前驱任务都执行完毕，并将所需数据传输给它，才可开始执行。

3 本文算法

本文提出了一种基于优先级机制和改进蚁群的微服务路径选择算法(Microservice Selection algorithm based on Priority mechanism and improved Ant Colony, MS-PAC)。传统蚁群算法的收敛速度较慢，当搜索空间较大时，需要很大计算时间。考虑任务的紧迫性和容器实例的竞争性，本文添加任务优先级机制优化任务调度队列，再利用蚁群算法的正反馈机制寻找全局最优解。

3.1 微服务优先级机制

前驱任务的延迟会累计起来影响后续任务的开始时间，应使任务都尽可能在其子截止时间内完成，然而同一业务的并发请求彼此争用容器实例，无法确保任务始终能分配到最快的容器实例上执行。因此，添加并发系数conf代表并发程度，优化传统工作流任务截止时间计算公式为

由前文可得任务的最早开始时间取决于其自身就绪时间和所有容器实例的最早可用时间，则任务的最早完成时间(EFT)可以计算为

利用上述任务的截止时间和最早开始时间来定义任务的优先级hop()

其中， 指从当前任务到退出任务的路径上的任务数，其值越大，则表示该任务被延迟后影响的任务越多，其后续任务的执行受各种因素影响的风险也会越高，有必要尽快为当前任务分配容器实例，以减少排队时间。任务的优先级并非一直不变，每有一个任务被分配，则它的后续任务的最早开始时间必然会根据该任务的分配结果动态变化，并发系数也会随着容器实例数量改变而改变，因此优先级会随着任务分配的过程不断更新，保证越紧急的任务优先级越高。

3.2 容器部署策略

当已部署容器实例的等待队列太长，导致任务最早完成时间超过任务的截止时间时，需部署新的容器实例来执行任务。首先考虑边缘节点的资源容量，资源不足的节点无法部署实例，即需要满足以下约束

该约束保证了节点的各类资源满足创建实例的需求，满足约束的边缘节点将成为候选节点。网络资源消耗为选取节点的主要因素，计算候选节点与部署了的前驱及后驱容器实例的节点之间的平均网络距离

其中，K1表 示的每个前驱微服务的实例数，K2表示的每个后续微服务的实例数，选择平均网络距离最小的候选边缘节点作为部署新实例的节点。

3.3 基于优先级机制和改进蚁群的微服务选择算法

本文提出一种基于改进蚁群算法的微服务选择算法MS-PAC，以获得全局最优的微服务执行路径策略。除了保留基本蚁群算法的随机和并行搜索特性之外，为提高搜索过程的收敛性，利用前一节所述优先级机制优化任务调度顺序。与遗传算法[19]、粒子群算法[20]等元启发式算法相比，改进后的蚁群算法采用信息素策略，实现了不同群体之间的经验信息共享。

MS-PAC算法模拟蚂蚁的进食过程，各个蚂蚁通过启发式信息和信息素的指导为并发请求中的任务选择容器实例，保留它们走过的路径，并选取蚂蚁中的最优解以保留经验，从而在迭代过程中逐渐趋于全局最优解。其具体流程如下：

(1)首先必然存在多个没有前驱任务的起点任务，将这些任务添加进候选列表中，并将蚂蚁A ntl随机放置在候选列表中的一个任务上作为起点。

(2) Antl以 概率选择公式为当前任务选择一个映射元组,I(a,i,j)> ，即根据信息素τi,j和启发式信息ηi,j，将分配给容器实例I(a,i,j)或为任务创建一个新的容器实例，之后该任务将被放入蚂蚁禁忌列表T abul中，不再进行调度。

(3)对某个任务做出调度后，若该任务的后驱任务中存在所有前驱任务都已完成调度的任务，则将该任务将添加到候选列表中。

(4) 更新候选列表中任务的优先级，从优先级最高的前Top N任务中随机选择一个任务作为Antl下一个任务，重复上述过程，直到完成所有任务的容器实例分配。

(5)所有蚂蚁均完成全部任务的分配可以视作一次迭代，算法在达到最大迭代次数后终止。

蚁群算法的核心为概率选择和信息素更新，Antl倾向于选择期望值更高、信息素更多的容器实例，Antl选 择p athi,j的概率计算公式表达为

其中，α和β分别是信息素和启发信息的影响因子，反映了它们的相对重要性。α越大，信息素对蚂蚁的影响越大，蚁群搜索的随机性越小，β越大，蚂蚁陷入局部优化的可能性越大。

启发式信息ηi,j代表蚂蚁将任务分配给容器实例的期望，根据本文目标，提出了两类启发式信息，第1个目标是确保业务请求尽可能在约束时延内完成。因此，将候选实例上任务的实际完成时间作为衡量容器是否合适的标准之一，定义完成时间的启发式信息公式为

第2个目标是减少网络资源的消耗，定义为代表网络资源消耗的启发式信息

对于信息素的更新，本文提出一种结合局部和全局的信息素更新规则，局部更新通过蒸发蚂蚁走过的路径上的信息素，防止蚂蚁选择相同路径，增加算法的探索能力，防止陷入局部最优。全局更新则在所有蚂蚁完成微服务选择方案后，会根据目标函数评估当前所有方案的质量，并选择其中质量最高的方案增加该路径上的信息素，这可以促进蚂蚁保留全局最优解的经验，在下一次迭代中找到更好的路径。

在选择一个新的映射元组,I(a,i,j)>后，蚂蚁按如下方式进行局部信息素更新

其中，ρl为局部信息素蒸发参数，且ρl ∈[0,1]，ρl越大，则路径上剩余的信息素越少。

信息素初始化为任务数Q，则全局信息素的更新公式为

其中，ρg为 全局信息素更新参数，∆τij为一次迭代后信息素的增量，Lbest为 迭代中全局最优路径的目标函数值。

4 仿真实验与对比分析

4.1 仿真参数设置

文献[21]提供了4个基准工作流：Montage, LIGO,CyberShake和SIPHT，如图2所示。每个工作流都由DAX文件描述，代表一类业务，该文件提供了工作流的详细信息，包括任务名称、工作负载、数据传输量和任务之间的依赖关系。微服务之间的数据传输量定义为10～15 MB，镜像大小定义为30～50 MB，任务的工作量定义为文献[22]中标准计算服务的执行时间。在本文中业务的截止时间设置为工作流拓扑的关键路径中任务执行时间的ψ倍，以确保可以容忍一定的排队时间。本文采用批处理请求策略，即假设在一个调度周期中所有请求都将同时启动，并且所有请求都将被调度，每个调度周期彼此独立。边缘节点的CPU内核从[8, 16, 32]中随机选择，内存从[8, 16, 32] GB中随机选择，磁盘容量从[100, 200, 300, 400] GB中随机选择。边缘节点之间的数据传输速率服从N(3×103, 102)(kB/s)，微服务CPU需求从[0.1–0.4]选择，内存需求从0.1～0.4 GB选择，磁盘需求从0.3～0.6 GB选择。用户与边缘节点平均带宽W为20 MHz，用户传输功率TP为20 dBm，噪声功率δ2为2×10–13W，信道增益H=127+30lgd。算法的迭代次数和蚂蚁数量通过多次实验选取300和30。实验中的相关参数参照表1，除非另有规定，否则适用于模拟。

图2 基准工作流

表1 仿真参数设置

本文使用时延和网络资源消耗作为指标来衡量本文的方法与其他方法相比的性能。为了验证本文算法的性能优越性，选择贪婪算法和文献[10]中的MSS(Microservice Service Selection algorithm)算法进行比较。贪婪算法由延迟和网络资源消耗两个方面组成，前者会优先考虑队列时间最少的容器，或者创建一个新的容器；后者只在初始容器上分配任务，从不创建新容器。MSS算法考虑了实例的共享和竞争，根据任务子期限不断更新任务的紧迫性，调整任务执行顺序或放弃特定任务的执行，并寻求按时完成更多任务。

4.2 实验结果

(1)对比不同的截止期限。为了验证不同方法在不同的截止日期内完成请求的能力，本文将ψ的值从1.0变为5.0，步长为0.5。向每种应用发起相同次数的请求，总请求数量为80。图3显示相较于其他策略，本文所提策略能在不同截止期限内按时完成较多请求。尤其当ψ=3时，4种算法之间存在最明显的差距。这是因为本文策略通过优先级机制优先调度紧急任务，减少关键任务的阻塞。图4显示随着ψ的增加，所有策略都降低了创建容器的网络资源消耗，与其他算法相比，本文算法在创建新容器时选取网络距离较小的边缘节点，并且将网络资源消耗作为改进蚁群的启发式信息之一，引导蚂蚁向网络资源消耗更小的微服务选择结果收敛。

图3 按时完成请求数量比较(ψ∈[1.0, 5.0])

图4 总体网络消耗比较(ψ∈[1.0, 5.0])

(2)对比不同请求数量。为了验证每个方法在不同并发度下满足截止期限约束的能力，本文将请求数量设置为20到100，步长为20。图5显示了不同请求数量下MS-PAC算法能有效降低时延。其能有效平衡时延和网络资源消耗，采用优先级机制优化任务调度顺序，并通过蚁群的自学习和正反馈机制，遏制非关键任务无限制创建新容器，从而避免挤占后续任务创建新容器资源，因此能更合理地实现任务到容器的映射以及节点资源的管理。

图5 不同请求数量下平均时延比较

图6展示了不同请求数量下网络资源的消耗，可以看出，除网络资源消耗贪婪算法外，其他3种算法中，MS-PAC在所有情况下均表现最好，通过容器部署策略，尽可能选择与该容器有最少网络资源消耗的边缘节点新建容器，同时在为任务选择容器实例时，会将网络资源消耗作为启发式信息，能在保证时延的基础上，最大限度地降低网络资源消耗。而时延贪婪算法和MSS算法没有考虑到选择实例时的网络消耗。

图6 不同请求数量下总体网络资源消耗

图7显示了不同算法在约束期限内完成请求的数量，MS-PAC在所有情况下均表现出良好的性能，尤其是在并发量高时也能保证较高的按时完成率，这是因为其通过优先级机制优先安排即将到截止期限的任务，保证这些任务尽快执行。MSS算法也会计算任务的紧急度，以安排任务的执行顺序，但是它会根据任务的子截止日期放弃超时任务。当请求数量为100时，与贪婪时延和MSS算法相比，本文按时完成的请求数量分别提高23.1%和8.9%。

图7 不同请求数量下按时完成请求数比较

5 结束语

复杂的物联网应用在资源有限的边缘节点以微服务的形式组合提供服务，针对高并发情况下难以选择合适服务实例的问题，本文提出了一种基于微服务优先级和改进蚁群的微服务选择策略，结合工作流机制，提高紧迫任务优先级，利用时延和网络成本指引蚁群收敛。通过在基准工作流上的实验，本文算法能有效降低时延，在提高按时完成请求率的同时降低网络成本。未来的研究将从云端协同、端端协同的角度探究如何高效执行复杂的微服务应用。