云边环境下微服务组合系统的动态演化方法

叶 盛，王 菁*，辛建峰，王桂玲，郭陈虹

（1.北方工业大学 信息学院，北京 100144；2.大规模流数据集成与分析技术北京市重点实验室（北方工业大学），北京 100144；3.中国网络安全审查技术与认证中心，北京 100013）

0 引言

微服务架构风格是应用程序被分解成小的独立构建块（微服务），每个构建块都专注于单个业务能力。微服务以轻量级机制相互通信，它们可以独立部署和维护。但是微服务分散性的风格无法独立满足一个完善的系统，需要组合微服务提供复杂而精细的功能。

微服务组合可以理解为：通过灵活组装多个高度自治的微服务给用户提供强大的功能或者满足上层的各种复杂的业务需求。本文的微服务系统基于云边环境下的微服务演化框架，并通过本文提出的方法进行微服务的组合和演化来满足用户的需求；但是，微服务组合的不确定性为云边环境的有效利用带来了新的挑战。用户需求具有不确定性，微服务组合逻辑会随着业务需求的变化而动态调整，微服务组合系统需要随着用户需求的变化而快速演化。为了支持微服务组合的高效执行，保证服务质量，本文提出了一种云边环境下的微服务组合系统的动态演化方法（Dynamic Evolution method for Microservice Composition system，DE4MC），通过业务流程中的发布/订阅通信手段使云边节点上的微服务之间建立协作，综合考虑微服务实例的迁移代价、微服务与用户的数据通信代价和微服务之间的数据流传输代价，支持业务流程的优化部署和动态调整。其中，包含了以业务流程运行时间和微服务系统演化开销为目标优化的两个阶段的云边调度算法：一是在业务流程部署阶段，通过业务流程部署算法对流程和微服务进行优化部署；二是在业务流程动态调整阶段，通过业务流程动态调整算法进行微服务组合系统的动态演化。这两个阶段的算法可保证微服务系统在演化开销低和业务流程运行时间短的条件下及时演化，并提供用户满意的服务质量。

1 相关工作

1.1 微服务组合相关工作

传统的服务组合风格有编制（Orchestration）和编排（Choreography）。很多微服务组合的相关研究借鉴了传统的Web 服务组合的思想和策略。

编制风格（Orchestration）Cocconi 等［1］提出了一种依靠中心协调器的协作业务流程（Collaborative Business Processes）的方法组合微服务。Oberhauser［2］提出了一种微流程的方法，通过使用代理编制语义注释的微服务。Ben Hadj Yahia 等［3］提出了基于事件驱动的轻量级服务编制平台——Medley。Monteiro 等［4］提出了基于事件驱动的轻量级微服务编制平台——贝多芬（Beethoven）。Gao 等［5］提出了一个微服务组的概念，用工作流的方式在多云环境下考虑服务质量和用户的偏好以组合微服务。本文借鉴了编制风格的一些组合微服务的思想。

编排风格（Choreography）Valderas 等［6］用业务流程建模与标注（Business Process Model and Notation，BPMN）可视化为微服务组合的大图，将大图拆成BPMN 片段的小图，允许每个微服务以解耦的方式运行，并采用BPMN2.0 原生自带的消息任务和事件通信。Safina 等［7］介绍了一个将实现的编排操作通过编译器转换为可执行代码并分发给参与者的程序。Decker 等［8］将BPMN 模型转换为业务可编排的流程执行语言（Business Process Execution Language for Choreographies，BPEL4Chor）描述以 执行编 排 。Gutiérrez-Fernández 等［9］采用BPM 语言开发微服务，用业务流程引擎执行它，并确定了业务流程集成到微服务体系结构的要求和流程引擎如何处理微服务之间的部署和通信。Ortiz 等［10］利用BPMN 可以描述控制流的方式编排组合微服务，并仔细描述了自底向上的方式，即对单个微服务进行改变会影响全局大图。Jayawardana 等［11］提出了一种新的方法，在统一的规范中对业务流程和领域知识进行建模，该规范可以生成与微服务体系结构兼容的样板代码。Valderas等［12］使用灵活的微服务架构执行BPMN 并促进它与物理设备的集成，实现了两者之间的解耦，并且不会增加BPMN 元模型的复杂性。Dai 等［13］提出了一种微服务编排分析方法，从给定的编排中生成参与复合服务的微服务。Giallorenzo等［14］讨论了编排的不同解释如何帮助开发正确的微服务系统架构，即那些真正实现所需的分布式交互，同时避免死锁和竞争的微服务系统架构。受上述工作启发，本文通过采用业务流程的方式编排微服务。

微服务组合方法［15］可分为三种：一是基于工作流模型的微服务组合方法，上述文献多为这种方法，是微服务体系结构中使用较多的一种服务组合方式；二是基于状态演化的微服务组合方法，本质上也是一种工作流的微服务组合方法，但主要完成微服务组合方案的可行性验证和对微服务的形式化建模；三是基于形式化语言的微服务组合方法，其思想是为微服务组合定义一种特殊语言，让用户在更深的抽象层次描述微服务组合并实现。采用面向服务的编程语言Jolie［16］作为描述微服务组合的语言，通过定义描述服务行为的语法结构和服务部署的端口等信息解决服务组合等问题。在组合服务实现过程中，需要对Jolie 进行一定的扩展完成服务组合调用所需的条件，如数据传输等，所以相较于工作流形式的微服务组合方法更复杂。但是基于本文的研究背景，尽管统 一建模语言（Unified Modeling Language，UML）、BPMN、BPEL、Medley、Jolie 等方法都可以创建微服务，但它们很少关注微服务的演化［10］，本文引入BPMN 片段解决这个问题，允许自上而下和自下而上的编排方式演化微服务。利用BPMN 建模的可视化性特点组合微服务的方式给开发者和用户带来良好的使用体验［6］。

1.2 微服务调度和演化相关工作

为了解决不同微服务之间不同版本的复杂依赖关系，贺祥等［17］提出面向演化的微服务编程框架和微服务系统自适应架构，并设计基于贪婪的优化算法找到最优的微服务系统演化方案以实现微服务系统的自适应演化。在这两个框架的基础上，He 等［18］提出了云边环境下的微服务自适应演化优化方法，满足移动端用户的质量需求。Wang 等［19］采用Java 中轻量级的方法实现了微服务演化编程框架，支持单个微服务的自适应演化。这些工作的自适应机制是由一个自适应控制回路参考模型MAPE-K（Monitor-Analyze-Plan-Execute-Knowledge）［20］实现的。但这些工作中并没有考虑微服务组合系统的特殊演化需求。本文在这些工作的基础上扩展了通过业务流程组合微服务的方法及技术。

微服务调度方面，Gao 等［21］提出了一种新的基于免疫记忆克隆和克隆选择算法的人工免疫算法，在大量候选微服务中组成复杂的工作流，该算法通过构造与用户相关的模糊权重将多最优问题转换成单最优问题。该工作结合了工作流和微服务，但是该工作没有考虑演化的问题。Lin 等［22］提出的一种蚁群算法，考虑物理节点的计算利用率、存储资源的利用率、微服务请求的数量和物理节点的故障率以提供最优路径的选择概率。该算法在集群服务可靠性、集群负载均衡和网络传输开销优化等方面取得了较好的效果，但也没有考虑微服务的演化问题，不过在服务可靠性和资源利用率等方面的部分工作可以借鉴。

以上的工作有结合微服务组合和调度、微服务组合和演化、微服务演化和调度，但是本文方法结合了微服务的组合、演化和调度。

2 DE4MC

本文提出了一种云边环境下的微服务组合系统的动态演化方法（DE4MC）去支持微服务组合和及时演化。

2.1 相关定义

一个云边环境下的微服务组合系统由一组逻辑服务组成，每个逻辑服务都有部署在不同云边节点的物理实例。一个业务流程是一组逻辑的特定服务，根据优化算法（详情见第3 章）选择这些服务的特定实例满足业务需求。

定义5 业务流程定向状态。业务流程定向状态BP（b）记录了业务流程片段与微服务实例之间的映射。对于∀r∈V(b)，假定r=s，u，c，为r选择一个请求的服务s的实例τ(s)和该服务相关的功能接口Ii（s），(τ(s)，Ij) ∈BP(b)。一个合法的业务流程定向状态必须满足微服务实例τ(s)提供的质量等级Li（s）必须大于等于用户的要求的条件。

定义6 微服务演化操作。

OPS={Composite，Split，Keep}：

1）Composite(…，Ii(si)，…) ⇒(s，I1(s))：表示把不同原子服务通过业务流程组合成一个新的服务。

2）Split(s，Ii(s))：表示把一个组合服务切成不同的原子服务。

3）Keep(s)：表示该服务的接口不改变。

定义7 微服务实例演化操作。

OPI={Adjust，Add，Remove，Retain}：

1）Adjust(τ(s)，Li(s)，Lj(s))：调整该微服务实例的质量等级。

2）Add(τ(s)，n，Lj(s))：在节点n上创建一个质量等级要求为Lj的微服务s的实例。

3）Remove(τ(s))：删除该实例。

4）Retain(τ(s))：保持该实例不发生改变。

定义8 业务流程定向状态的演化操作。

OPU={Deploy，Switch，Keep}，其中：Deploy(b，τ(s))表示把流程片段b跟微服务s实例建立映射；Switch(b，τi(s)，τj(s))表示业务流程片段b跟微服务s的实例τi的映射关系转移到另一个实例τj上。

定义9 部署状态。一个微服务系统在时间t的部署状态可以 表示为Θ(t)=S(t)，E(t)，N(t)，V(t)，BP(t)，S、E、N、V和BP分别是微服务集合、节点集合、微服务实例集合、业务流程集合和业务流程定向状态。

2.2 微服务组合系统演化框架

本文动态演化方法基于EI4MS 的微服务系统基础架构和EPF4M 微服务自适应编程框架的扩展，该架构有7 个组件如图1 所示。

图1 微服务系统的演化架构Fig.1 Evolution architecture of microservice system

1）控制中心。用户直接通过可视化建模工具创建新的业务流程或者修改已运行的微服务实例，该工具把用户建模或修改的信息直接提交给分析器，它能识别业务流程文件和业务流程实例并转化成算法需要的输入格式，再通过计划器中的两个算法计算得出一组系统演化操作，然后放到执行器上执行。

2）日志收集器。收集每个节点上微服务实例的运行日志，并把所有日志传递到边缘集群中的日志数据库。

3）微服务构建中心。把自动生成相关的流程片段描述信息、服务功能语义描述和流程引擎语义描述打包构建相应的Docker 镜像，为Composite 和Split 演化操作提供支持。它从控制中心接收Composite 和Split 的作业，生成 Docker 镜像并推送到镜像仓库进行添加操作。它部署在一个集中的云节点上。

4）集群代理。负责获取边缘节点的运行时信息并传递给控制中心，包括日志数据库的日志、注册表、Kubernetes API 服务器的信息和微服务的实例信息。Kubernetes API 服务器和网关能够接收控制中心的演化操作并部署到相应节点。它必须部署在一个边缘节点上。

5）网关。将用户请求重定向到服务实例，并依赖于用户请求的路由表。来源控制中心的Switch 演化操作会让路由表发生改变。它必须部署在边缘节点上。

6）用户可视化建模工具。用户可以在上面建模自己的业务流程，也可以动态修改业务流程。

7）通信总线。用通信总线的方式支持部署在云边节点上的业务流程的消息事件传递和消息任务的执行。

2.3 方法原理

如图2 所示，DE4MC 分为业务流程部署和业务流程动态调整两个阶段。

图2 微服务组合系统的动态演化方法Fig.2 Dynamic evolution method of microservice composition system

业务流程部署阶段 用户提交业务流程后，系统根据云边节点的状况采用业务流程部署调度算法（详见第3 章）合理切分业务流程并部署在相应的节点上，使业务流程运行的时间最短和微服务演化开销最低。

由于全国快递运输量巨大且每个快递公司各地的营业网点数量多，如果在云上部署相应的微服务会导致响应速度慢和云边节点信息不匹配。为了更好地安排人员和交通工具，应把相关的微服务部署到附近边缘节点进行准确且快速的计算。首先，快递公司在公司云节点收到用户寄快递的订单后会创建一个最初的流程，其中指派快递员、支付订单和货车运输服务都在同一个边缘节点且有连续的控制流和数据流关系；然后，演化系统根据微服务演化操作Composite 把这3 个功能组合成一个新的复合服务以减少数据流传输和缩短响应时间，通过Add 生成相应的实例；最后，通过Deploy 操作建立实例和流程片段的关系。系统对应的演化操作如表1所示。

表1 部署和调整阶段演化操作Tab.1 Evolution operations in deployment and adjustment stages

业务流程动态调整阶段 用户提交的业务流程已经部署运行，但是用户需求临时发生改变，用户想要修改正在运行的流程，系统需要及时演化响应用户修改后的流程。例如，由于原定的路线上北京通州区发生疫情导致快递公司不得不及时修改业务流程，把原定从广州白云区运到北京通州区的飞机服务和之后的货车运输服务删除，然后根据实际业务需求重新添加高铁服务、火车服务等。系统对应演化操作如表1 所示。

3 微服务组合系统演化算法

本章描述用户在建模业务流程和修改业务流程两个阶段下系统运行的演化算法，两种情况下的问题定义是一致的。

其中：A、B和C分别为OP(I)、OP(U)和OP（S）的数量。

进一步，整个流程的运行时间可以被定义为：

其中：n为该流程中服务实例的数量，rt(·)为每个微服务的运行时间，ct(·，·)为业务流程片段之间的通信时间。

本文算法优化的调度目标如下：

其中：eij是满足用户ui提交的业务流程wj需求的一个微服务实例；Q（）表示获得的服务级别协议（Service Level Agreement，SLA）；r（）用来计算资源的大小；rmax（）代表该节点所有的资源大小；ns（）代表当前使用该微服务实例用户的数量；nsmax（）表示该实例设定的最大用户数；δ表示自上次演化以来经过的时间间隔。

3.1 算法原理

本文方法由两个阶段的算法组成，两个算法由两个原子算法组成：一是追求反应快速但可能只得到局部最优解的启发式算法（Heuristic Algorithm，HA），二是能得到全局最优的遗传算法，该算法以系统的演化开销和业务流程的运行时间为优化目标。如式（4）所示，系统演化操作必须满足3 个约束，分别是节点上的资源不能被使用完、微服务的质量必须大于用户的要求和微服务的实例数量不能超过服务最大实例数。需要注意的是，由于本文采用业务流程的方式组合微服务，业务流程中各个元素之间可能存在数据流关系，在综合其他约束条件下，算法也会考虑把两个具有数据流关系的微服务部署在同一个物理节点上以降低通信传输的开销。如果一个微服务的输出是另外一个微服务的输入且两者都被频繁调用，根据本文提出的微服务演化框架，这两个微服务通过Composite 演化操作聚合成一个功能更强大的微服务，方便实例化和调度。

3.1.1 基于启发算法改造后的算法原理

本文针对业务流程具有数据流的特点改造了传统HA，提出了业务流程管理启发式算法（Business process management Heuristic Algorithm，BpmHA）算法，通过节点评估函数选择节点进行部署。评估函数如下：

该评估函数综合考虑三方面因素，分别是迁移代价（微服务实例从云边节点到另一个节点的代价，否则代价为0）、通信代价（微服务实例部署节点跟所分配用户通信的代价，如果该微服务不需要跟用户交互就为0）和微服务之间通信代价（微服务之间可能存在数据流交互的通信）。根据实际用户的需要或者经验分别配置权重，本文按照各占1/3的权重进行实验验证，后期通过不断实验得出经验再进行权重的合理分配。

算法1 BpmHA。

输入 业务流程文件或实例BP，所有节点的运行状态SN；

输出 业务流程定向状态的演化操作OP（U），微服务实例演化操作OP（I），微服务演化操作OP（S）。

如算法1 所示，系统首先把用户提交的业务流程文件分成一个个最小的微服务，遍历所有云边节点查找目标微服务加入微服务集合，并查找资源能满足目标微服务部署的节点放入备选节点（第3）～4）行），在这些备选节点上遍历计算NE，选最小值的节点与目标服务关联。如果满足算法1 所有IF 语句中的微服务演化操作要求，就进行相应的演化操作（第10）～23）行）。如果所需的目标服务是已组合服务的一部分且别的节点没有目标服务的镜像，就需要把目标服务从已组合的服务通过Split 操作拆解出来。如果目标微服务在目标节点已存在实例，就通过Switch 演化操作把相关流程片段与该实例形成映射。如果目标节点的资源不满足目标微服务所需要的资源，通过Adjust 操作进行资源的动态调整。如果目标服务需要被几个服务组合且满足定义6 的条件，就通过Composite 操作组合几个服务。如果目标节点没有该实例，则需要迁移目标服务镜像并重新通过Add 操作创建一个目标服务实例。

启发算法相较于遗传算法，执行时间较短。算法的时间复杂度为O（mn），m是需要部署的目标服务的数量，n是所有微服务的数量，如果边缘节点上没有相应的微服务实例，系统会去云端查找该实例，但是平均响应时间会变长。

3.1.2 基于遗传算法改造后的算法原理

本文使用第二代非支配排序遗传算法（Non-dominated Sorting Genetic Algorithm-Ⅱ，NSGA-Ⅱ）［23］，部署状态和运行实例转换成种群基因的详情请参考文献［18］。

算法2 NSGA-Ⅱ。

输入 所有节点的运行状态SN；

输出 业务流程定向状态的演化操作OP（U），微服务实例演化操作OP（I），微服务演化操作OP（S）。

NSGA-Ⅱ引入了精英策略，达到保留优秀个体淘汰劣等个体的目的。精英策略通过将父代与子代个体混合形成新的群体，扩大了产生下一代个体的筛选范围。P0表示最初的父代，Q0表示最初的子代，N代表个体数。算法具体步骤如下：将父代种群和子代种群形成新的群体，对新种群进行非支配排序，生成新的父代，先将Pareto 等级为1 的非支配个体放入新的父代集合中，之后将Pareto 等级为2 的个体放入新的父代种群中，以此类推。若等级为i的个体全部放入新的父代集合中后，集合中个体的数量小于N，而等级为i+1 的个体全部放入新的父代集合中后，集合中的个体数量大于N，则对i+1 等级的全部个体计算拥挤度并将所有个体拥挤度进行降序排列，之后将等级大于i+1 的个体全部淘汰。对生成后的父代种群计算适应度，fitness=θ1*T+θ2*C，其中演化开销和运行总时间的权重各占一半，选择适应度大的父代进行交叉、变异操作生成子代种群。最后判断代数是否等于最大进化代数，否则就继续执行循环迭代。最终的演化操作规则见算法2 第15）～29）行。

3.2 业务流程部署和动态调整算法

用户根据自己实际的业务需求建模自己需要的业务流程，通过该部署算法计算演化操作，交由执行器作微服务实例部署。两个算法的策略如图3 所示。

图3 算法策略Fig.3 Algorithmic strategy

业务流程部署算法 本文改进HA 提出了BpmHA，微服务实例的迁移代价、微服务与用户的数据通信代价和微服务之间的数据流传输代价是影响微服务部署效率的三大因素，因此在选择部署节点时综合计算三者代价来选择最优的部署方案，BpmHA 经过后期实验能得到一个近似全局最优的解，无需重复多次运行。如果BpmHA 不满足用户的服务质量（Quality of Service，QoS），系统会采用NSGA-Ⅱ迭代计算演化操作方案。算法的输入是用户提交的业务流程和各节点的部署状态（所有节点的状态），算法的输出是演化方案(OP(U)，OP(I)，OP(S))。

业务流程动态调整算法 与部署算法不同，该算法的输入是对云边节点上已有运行的业务流程实例动态调整后的实例；虽然已经运行完的流程片段不再经过算法重新部署，但是动态调整的部分仍会参考已部署的流程状态进行综合优化部署。动态调整算法在遗传算法上也作了改进，演化系统记录两个算法已运行计算出的一些较优解（使本文的两个优化目标效果不错的解集会被记录下来），NGSA-Ⅱ不需要从最初种群开始迭代计算，可以从记录的解集中挑选一批作为父代和子代，提高了种群的迭代速度，用户修改业务流程后演化系统能及时动态演化。

4 实验与结果分析

4.1 仿真平台介绍

本文使用仿真软件CloudSim 和WorkflowSim，其中CloudSim 提供了云计算相关的资源建模和任务调度方面的仿真；WorkflowSim 在CloudSim 基础上引入了工作流级别的仿真，通过模拟真实工作流的运行机制来调度任务。用户可以把设计好的调度算法放到该工具上执行，实现真实模拟云边环境下的工作流调度。WorkflowSim 被广泛应用于工作流调度的科研学习上。

WorkflowSim 中的工作流形式通过有向无环图（Directed Acyclic Graph，DAG）的形式表示，本文中的业务流程表示为有向无环图，其中业务流程中的每个活动表示为图中的一个活动，业务流程的控制流顺序相当于图上的边。

4.2 数据集准备

为了验证本文算法在业务流程微服务部署和调整两个阶段的可行性和效率，实验中需要使用大量不同的工作流。由于公共的数据集有限，为了模拟现实生活中各种需求的业务流程，本文实验中业务流程表示为带有数据流的DAG，参照文献［23］中提出的DAG 构造方法，本文设计了一种带有数据流的DAG 生成算法，通过添加一些约束并采用编码方式生成两组工作流，其中一组工作流在初始的一组工作流的基础上随机修改以模拟用户修改后的业务流程，再通过动态调整算法重新计算部署。简而言之，一组初始的工作流用于测试业务流程部署算法的效率，随机修改的工作流用于测试动态调整算法的效率。通过表2 所示的自定义参数，程序自动生成满足实验条件的工作流。

表2 工作流参数设置Tab.2 Workflow parameters setting

DAG 生成算法随机标注DAG 的每个节点的模拟地理位置，目的是模拟用户的移动。该算法首先随机生成节点与用户之间的传输开销，再生成一条最长路径的工作流，然后通过随机的最大并行度值将剩余的任务个数加入DAG 中，接着逐层连接下层节点，确保形成一个连通图。确定完DAG 所有节点后，该算法会在随机节点之间生成有输入输出指向性的数据访问关系和具体数据值，从而模拟出节点之间数据流关系。

4.3 实验环境配置

为了验证本文提出的业务流程动态演化算法的有效性，需要同其他算法进行比较。为了减少其他因素对实验结果的影响，实验环境均保持一致。本文实验环境如下。

实验所用的服务器操作系统版本为Windows 10，内存32 GB，实验仿真工具WorkflowSim1.0，Java 环境为JDK1.8，Python 版本3.6。WorkflowSim 模拟生成的10 个边缘节点的参数：CPU 运算法能力TOPS（Tera Operations Per Second）或者MIPS（Million Instructions Per Second）为3 000，内存5 GB，外存20 GB，通信带宽10 MB/s。WorkflowSim 模拟生成的1个云节点的参数：CPU 运算法能力：TOPS 或 者MIPS 为20 000，内存20 GB，外存100 GB，通信带宽20 MB/s。

为了简化实验，把DAG 的每个顶点当作WorkflowSim 工具中的一个虚拟机资源，它的大小和所需要的计算资源都一样，具体参数为：虚拟机所需CPU 运算能力资源TOPS 或者MIPS 为20，虚拟机所占外存大小区间0.5～1.0 MB。

4.4 算法性能分析

4.4.1 实验参数设置

本文的优化目标主要有两个，一个是最小化业务流程的运行时间，另一个是最小化微服务系统的演化开销。业务流程的运行时间包括算法的执行时间和业务流程的执行时间。具体演化操作开销如表3 所示。

表3 演化操作开销Tab.3 Evolution operation cost

4.4.2 对比实验设置

本文实验对比的算法包括GA，NGSA-Ⅱ，HA+NGSA-Ⅱ的算法组合，和本文提出的算法BpmHA+NSGA-Ⅱ的算法组合，表4 是实验中算法的相关参数设置。

表4 遗传算法参数设置Tab.4 Genetic algorithm parameter setting

算法1 和算法2 的输出是3 组具体的演化操作，每一种操作的演化开销都在表6 中具体表示。本文只需要把算法算出来的演化操作开销进行相加，就能计算得到总的演化开销。

4.4.3 实验结果展示

DAG 生成算法随机组成了1 000 个DAG，按照固定的顺序排列仿真业务流程部署的测试。另外1 000 个DAG 在原先的DAG 基础上进行微小的改变，用作动态修改业务流程的测试。本文通过仿真实验控制该调度环境中DAG 的数量规模，对比这几个主流算法的总运行时间（调度完所有的DAG 所用的总时间）和综合调度开销（调度完所有的DAG 所消耗的开销资源）。在部署阶段，部署算法（BpmHA+NSGA-Ⅱ）与HA+NSGA-Ⅱ的算法组合相比，各个规模的平均运行时间低9.7%，演化总开销低16.8%；在动态调整阶段，动态调整算法（BpmHA+NSGA-Ⅱ）与HA 加NSGA-Ⅱ的算法组合相比，各个规模平均运行时间低6.3%，演化总开销低21.7%。

为了更好地验证本文算法的有效性和效率，本文设置DAG 的规模为自变量，比较本文算法和对比算法在部署阶段和调整阶段的运行时间，如图4 所示。

图4 各算法在不同阶段的运行时间Fig.4 Running time of each algorithm in different stages

原因分析 GA 通过不断迭代产生最优解，需要一定的时间。NSGA-Ⅱ相较于GA 多了精英策略和寻找非支配解的过程，所以比GA 时间长。HA 较简单，会搜寻每个节点已在运行的DAG 部分活动，只要资源足够，就直接生成实例部署，不需要考虑综合调度代价，所以时间短；但是在该节点资源临界情况，该启发式算法没考虑负载均衡，导致执行时间变长。HA+NSGA-Ⅱ可以很好地解决这个问题，如果HA 导致运行时间变长，系统会启动NSGA-Ⅱ进行总的迭代部署，所以总运行时间比GA 短。而BpmHA 改进了HA，考虑到负载均衡和业务流程数据流的特性，综合选择最优节点部署，虽然需要一定的时间代价，但是真正执行的时间是所有算法中最短的。如果BpmHA 并没有使两个目标得到很好的优化，就会启动NSGA-Ⅱ进行总体优化，NSGA-Ⅱ不会从最初状态开始迭代，会从HA 产生的局部最优解中挑出一些作为初代，开始迭代计算，这样大幅缩短了演化时间。另外从图4 中可以明显看出，调整阶段的算法策略跟部署阶段的效果是差不多的，调整阶段在资源充足的情况下，BpmHA 的效果不错，因为只是局部改动，无须用NSGA-Ⅱ迭代计算最优解。如果NSGA-Ⅱ不考虑演化时间，整体的执行时间较短。

本文仿真了在云边环境协同下的业务流程微服务调度，相较于传统的DAG，本文生成的DAG 多活动之间会有数据传输，跟用户之间也有数据的交互。部署阶段和调整阶段的调度总开销如图5 所示，可以看出本文针对业务流程和微服务特性对启发式算法改进的BpmHA+NSGA-Ⅱ的组合算法的演化总开销较低，节省了资源。

图5 各算法在不同阶段上的总演化开销Fig.5 Total evolution cost of each algorithm in different stages

原因分析 GA 需要迭代找出最优解，不断迭代重新部署会导致迁移代价较大，会带来一定的开销。NSGA-Ⅱ通过引入精英策略得到较好的解，因此开销比GA 低。HA 为了追求更短的时间，遍历找到活动所在的节点直接部署，迁移代价低，但是没有综合考虑数据流的传输代价和微服务与用户之间的传输代价，所以最后产生的演化总开销通常较大。而HA+NSGA-Ⅱ的组合算法会在HA 无法缩短时间的时候启动NSGA-Ⅱ，负载均衡相关已部署节点，但是总开销跟GA 和NSGA-Ⅱ差不多。而本文针对HA 改进的BpmHA 考虑了业务流程多个节点存在数据流的特性和微服务的组合演化特性，综合计算NE后选出值最小的节点进行调度，确保总调度开销是最小的，从而缩短运行时间。

5 结语

相较于传统的服务，微服务更小、更敏捷。由于微服务功能单一，需要通过传统工作流、BPEL 和BPMN 等编排方式组合微服务。本文采用业务流程的方式组合微服务。本文针对云边下的微服务组合的动态演化的问题，结合了实验室对业务流程主动式探索和服务组合的研究上的积累和文献［18］中提出的微服务演化框架和基础架构，提出了一种在云边协同环境下基于业务流程的微服务组合的动态演化方法。该方法包含了支持业务流程部署和调整的动态演化算法，其中本文设计的启发式算法BpmHA 综合考虑微服务实例的迁移代价、微服务与用户的数据通信代价和微服务之间的数据流传输代价，能得到一个近似全局最优的解，无需多次运行，既缩短了算法的执行时间又提高了算法的效率。在NSGA-Ⅱ的基础上，增加了把节点上的状态转化种群基因的形式，并把两个算法已计算的较优解作为初始种群，加速迭代计算出最优解，及时演化满足用户的需求。通过实验验证了该算法在云边环境下微服务组合动态演化特定问题上有不错的表现，总运行时间和总演化开销均有所降低。

本文还存在以下不足之处。

1）由于实验设备等问题，并没有在真实集群环境上运行该演化框架和本文提出的演化算法，只是在仿真环境上验证了算法的合理性和效率。以后会逐步在真实的环境中去运行该算法。

2）本文采用特定的DAG 简单模拟业务流程，而DAG 业务流程复杂，有许多别的元素。本文只是用DAG 的活动表示了业务流程中的服务任务，并没有考虑别的任务、事件等元素。在以后的真实环境中，需要把业务流程其他元素考虑进去。