张晓红，黄继海

(中州大学 信息工程学院，郑州 450005)

1 引言

对于运营商而言，提供网络服务的成本越来越高。考虑到当前网络的复杂性，即使是针对突发需求而实施的简单升级，也可能需要数月甚至数年的时间才能完成。然而，在计算技术的进步和IT 环境中虚拟技术成功的鼓舞下，网络运营商正努力推动类似的技术，希望以此作为解决扩展性问题的一种办法。网络功能虚拟化(Network Function Virtualization，NFV)［1］便是此类选择中的一种。它利用标准的IT 虚拟化技术，将多种类型的网络设备合并到业界标准的高容量服务器、交换机和存储设备中，并将其置于数据中心、网络节点等地。

NFV 的重要技术支撑是服务功能链(Service Function Chain，SFC)的构建。通过将特定的网络服务抽象为一系列有序的报文处理功能实体，可以实现新网络服务的灵活部署与服务隔离。然而，现有研究对NFV 中的SFC 构建技术依然停留在资源分配［2－3］和标准建立［4－5］阶段，无法实现SFC 的服务最优组合。

在计算机网络中，针对服务组合优化问题的研究主要集中在基于构件的软件工程(Component－Based Software Engineering，CBSE)和面向服务体系结构(Service－Oriented Architecture，SOA)等领域。虽然一个抽象的服务功能对应的所有具体服务实体在功能上是等价的，但在其他属性上是存在差异的，所以可以根据非功能属性进行服务实体选择和组合优化。在不同领域，非功能属性具有不同含义，基于这些属性约束建立服务组合优化模型并求解，已成为CBSE 和SOA 中的热点问题。比如QoS 感知［6］的Web Services 组合问题的研究，文献［7－8］针对顺序、并发、分支、循环等4 种控制结构的Web Services 组合模型，建立了包括费用、响应时间、信誉、可用性等参数的评价体系来评价组合的效果，并利用整数规划方法从全局角度进行最优化求解。文献［9－10］的研究思路与文献［7－8］类似，提出了遗传算法来解决QoS 感知的Web Services 组合问题。此外，文献［11－13］以云计算系统为背景，建立基于QoS 的服务组合模型，并提出各种启发算法。文献［14］将信任概念和信任度引入到Web Services 组合中，分别基于信任感知和信任增强建立数学模型，并采用蚁群算法求解之。

上述研究主要针对Web Services 的组合优化问题，其考虑的QoS 属性并不适用于NFV 体系，且忽略了属性的匹配约束。为此，本文提出一种适合于NFV 架构的服务实体性能模型，并根据服务实体间的性能匹配和资源总量约束，形式化分析服务组合优化问题;在求解过程中，为减轻大量无效解的干扰，提出了改进的模拟退火算法SCM－SA，该算法包含基于层次属性的产生函数和基于偏离度的目标函数。

本文的后续部分组织如下:第2 节提出一种针对服务实体的性能模型，并在此基础上分析基于性能的服务组合优化问题;第3 节提出改进的模拟退火算法SCM－SA 及其相关函数设定;第4 节对提出的SCM－SA 算法进行实验评估;第5 节为结束语。

2 问题描述

2.1 服务功能链模型

定义1 服务拓扑。在NFV 体系中，服务功能链可以抽象为服务拓扑Gc=(V，E，s，t)。其中，V 为服务功能集合，E 为服务间的连接关系，s 为该服务功能链的源节点，t 为该服务功能链末节点。

服务功能链的构建过程分为两步:服务拓扑映射和服务组合优化。对于第一步，我们通过虚拟网映射技术［2－3］，将服务拓扑嵌入到底层网络中，并为其分配节点资源和带宽资源。对于第二步，我们需要描述服务组合的实体和约束条件。

定义2 服务实体。提供具体服务的功能实体称之为服务实体。每个服务对应大量的服务实体，虽然它们的服务属性相同，但是具有多样化的性能参数，所以我们将服务i 的第j个服务实体抽象为

式中，Configin为服务实体的输入性能矢量，Configout为服务实体的输出性能矢量，Res 为服务实体运行时所占用的系统资源矢量，k 为所考虑的资源类型数，分别为第i个输入性能属性和输出性能属性，m 为所考虑的性能属性个数。特别地，若为，则说明服务实体不受该性能属性的约束;若为，则说明服务实体不对外提供该性能属性的信息。

性能属性是指服务实体在运行时所需要的或表现出的某一性能方面的特性。例如某一报文分类实体在运行时输入报文的到达速率需小于10 Gb/s，而输出的分类结果速率为125 Mb/s。

两个同种类型的性能属性c1和c2进行叠加，记为c1c2。根据性能属性类型不同，叠加符号对应的数学运算可以是交集运算、并集运算、求和运算或最小(大)值运算等。例如，当性能属性为传输速率时，c1c2=c1+c2;当性能属性为最大时延时，c1c2=max(c1，c2);当性能属性为执行时间时，c1和c2均为取值区间，c1c2=c1∪c2。特别地，若c2=，则c1c2=c1;若c1=，则c1c2=c2。

定义3 性能矢量叠加。两个性能矢量Config1和Config2进行叠加，记为Config1Config2=［c11，c12，…，c1m］［c21，c22，…，c2m］。具体表达式为

2.2 服务组合优化

服务组合优化问题就是从每个服务i 对应的候选服务实体集合Si中挑选出合适的实体eij，从而得到成本最优的服务组合模式SCMbest，且满足性能约束和资源约束。图1 中的SCM1={e11，e21，e31，e41，e51}和SCM2={e13，e22，e32，e42，e52}即为两种可能的服务组合模式。

图1 服务组合优化问题Fig.1 Service composition optimization problem

服务组合优化问题的关键在于使所有服务实体的性能需求得到满足。

定义4 性能满足。若服务实体eij的输入性能矢量Configin被所依赖的服务实体{e1，e2，…，el}所满足，则下式成立:

此外，在虚拟网构建过程中，Resource=［R1，R2，…，Rk］是服务组合的资源约束条件;服务组合后的服务功能链也需要满足虚拟网的整体性能需求Configreq=［c1，c2，…，cm］，所以末节点候选服务实体的输出性能矢量需要与Configreq相匹配。

综合上述设定，服务组合优化问题可以描述为:寻找一个服务组合模式SCMbest=，n 表示候选实体集合个数，ai表示第i个候选服务实体集合中选择的实体序号，1≤i≤n，1≤ai≤M，使其满足

(1)除源节点外，其他服务实体的性能需求均得到满足;

(3)组合模式中所有实体占用的资源不超过虚拟网限定的资源阈值Resource;

(4)在满足上述3个条件下，选取成本最低的服务组合模式。

形式化描述如下:

式(2)表示组合模式中所有服务实体的总成本，而每个服务实体的成本=所占各种资源的成本+实体的固有成本，其中wj为资源属性rj的单位成本;pi为候选服务实体的固有成本，为了便于描述，式(3)中将作为源节点、作为末节点，分别描述了上文中(1)、(2)和(3)三种约束条件;M为候选服务实体集合大小的上界。

服务组合优化问题是一个具有复杂约束的整数规划问题，其复杂性为NP－hard。如果采用遍历方式，则最坏情况下搜索的模式数为O(Mn)，模式的有效性判别时间复杂度为O(n2)，所以总的时间复杂度为O(Mnn2)，仅适用于小规模服务组合。为适应不同规模的服务组合，需要采用启发算法。

现有启发式算法如模拟退火算法、遗传算法、粒子群算法等主要采用罚函数方法或者松弛方法消除约束条件，但考虑到本文提出的服务组合优化问题的约束条件属于整数约束而且较为复杂，上述方法均难以保证能以较大概率收敛到有效解。因此，本文提出一种改进的启发式算法，能够有目的性地产生新解，从而提高算法收敛到有效解的概率。然而，遗传算法和粒子群算法的新解产生过程相对受限，因此后文对模拟退火算法进行改进，利用解的性能需求约束的分层特性，设计适合服务组合优化问题的新解产生函数和目标函数。

3 服务组合优化算法

模拟退火算法是一种适合解决NP－hard 问题的通用有效的全局优化算法，其基本思想是从任意解出发，每次产生一个邻居解，直接接受使目标函数更优的邻居解，或以一定概率接受使目标函数变差的邻居解，不断迭代上述过程，最终得到使目标函数全局最优的近似解。采用改进的模拟退火算法解决服务组合优化问题，关键在于确定新解的产生函数(Generation Function)和目标函数(Cost Function)的计算公式，以便克服无效解的干扰。

3.1 基于层次属性的产生函数

首先，需要对问题的解进行编码。服务组合优化问题的解(即服务组合模式)使用了一个整数数组来表示，数组的长度为组成服务功能链的服务实体数n，数组中的每个元素为该服务实体所对应的索引号，比如服务组合模式SCMi={e13，e21，e32，e42，e54}可以被编码为［3，1，2，2，4］的数组。然后，算法的初始化过程就是对数组中的元素赋予随机的正整数值，并且取值范围不超过相应候选服务实体集合的大小。

成立金融改革工作领导小组，政府主要领导任组长，驻地金融监管部门和相关部门为成员单位，建立健全跨行业、跨部门的工作联动机制，加强统筹协调，整体推进和监督落实，协调重大金融项目和金融改革政策落地实施；领导小组下设办公室在政府金融办，政府金融办主任兼任办公室主任负责领导小组日常工作；领导小组及其办公室不刻制印章，如因工作需要由市政府金融办代章；各地也要建立相应的工作推进机制，形成上下齐抓共管的金融改革工作新格局。

为了更好地逼近有效解，模拟退火算法设计了具有记忆性的新解产生函数。所谓有记忆性是指新解产生函数能够记录当前解的层次属性(见定义5)，并且根据具体情况产生三种类型的新解:具有相同层次属性的新解;具有更高层次属性的新解;具有更低层次属性的新解。下面给出解的层次属性定义。

定义5 解的层次属性。根据图论中的反向拓扑排序算法，解数组中的每个元素所代表的候选服务实体都存在唯一的层次编号。新解是通过随机改变旧解数组中的若干元素得到的，并且这些元素所代表的候选服务实体具有相同的层次编号，所以每个解的产生都与一个层次编号相关联，该编号称为解的层次属性。

在对候选服务实体的层次编号进行预计算后，新解产生函数的处理流程如下所示:

GenFunc 函数每次只针对首先出现性能约束不匹配的一层进行随机改变生成新解;如遇有效解，则随机从某一层开始新解的生成。经过逐层推进，解的性能约束条件逐渐得到满足，从而趋近有效解。这种方式有利于避免普通随机生成方式的盲目性，提高有效解的搜索效率。

3.2 基于偏离度的目标函数

对于当前解Mold和新产生的解Mnew，若目标函数值f(Mnew)＜f(Mold)，则直接接受Mnew为当前解;若f(Mnew)≥f(Mold)，则依接受概率接受Mnew。接受概率P(Mold，Mnew，t)的计算公式如下:

根据公式(4)，定义如下的目标函数计算公式:

式(5)中的Cost 函数用来计算当前解(服务组合模式)所消耗的成本值，具体见公式(2);Conflict.size()表示当前层次的服务实体集合中违反与上层服务实体性能依赖关系的个数，1 +Conflict.size()即为解的偏离度。

3.3 基于模拟退火的服务组合模式搜索

基于上述函数设计，可以得到基于模拟退火的服务组合模式搜索算法(Service Composition Mode search algorithm based on Simulated Annealing，SCM－SA)的完整处理流程如下:

3.4 复杂度分析

由于SCM－SA 算法是基于模拟退火算法，因此新解的迭代产生次数是受参数影响的，如果将算法参数视作常数，则迭代次数的复杂度是O(1)。对于新解产生函数GenFunc，其计算复杂性主要体现在第8步“while j ＜L do”中，其复杂度为O(n2)，而该步的执行次数由服务拓扑的最大节点度D 和最大层次数H决定，最坏情况下次数为O(D +H)，因此函数Gen-Func 的最坏情况复杂度为O(n2(D+H))。

4 实验评估

4.1 实验设置

通过C++编程模拟服务组合优化问题并实现模拟退火算法。实验方案主要为了评估SCM－SA算法相比于其他启发式算法在服务组合成功率和组合代价上的优势。服务组合成功率CSR 是指所有服务组合请求中成功的比例。

在实验数据上，利用TGFF［15］工具随机生成具有指定节点数的服务拓扑，且只考虑有向无环图(DAG)。利用C++语言生成候选服务实体集合，其中每个候选服务实体集合大小在［3，10］内均匀分布。每个候选服务实体的性能矢量长度为3，且性能属性的取值为0 或1，叠加符号对应最小值运算，其中1 的概率为90%。候选服务实体的资源属性个数为3，且取值在［10，100］内均匀分布，各资源属性的单位成本w1、w2和w3分别设为1.0、1.0 和1.0，总量均设为4000。此外，候选服务实体的固有成本取值在［10，15］内均匀分布。

4.2 性能评估

实验中，SCM－SA 算法的主要参数取值如下:初始温度Ts=1000，终止温度Te=10，降温比例a=0.9，每个温度下迭代的次数L=5 ×n(n 为服务拓扑节点数)，收敛条件R=50。在不同服务组合规模下(n=10，15，20，25，30，35，40)，分别进行60 次服务组合问题求解，计算不同算法的服务组合成功率CSR，结果如图2 所示。可以看出，随着服务组合规模的扩大，服务间的性能依赖关系更加复杂化，从而使各种算法的CSR 值逐渐降低。其中，SCM－ SA算法的CSR 值保持在46.7%以上，高于其他算法;单纯考虑有效解的模拟退火算法Feasible－ SA 的CSR 值始终低于SCM－SA 算法，且随组合规模n 的扩大而下降至16.7%;不考虑解有效性的基本遗传算法GA 的CSR 值最低，不超过10%。上述结果表明，单纯考虑有效解方式会使部分搜索陷入僵局，降低CSR 值，基本启发式算法(GA)则很难在复杂约束条件下收敛到有效解，所以CSR 值最低。

图2 不同算法的服务组合成功率(CSR)比较Fig.2 CSR comparison among different algorithms

相同实验环境下，比较不同算法的最优服务组合模式成本值，如图3 所示。从实验结果可以看出，不同算法的服务组合模式成本值的大小关系为CSCM－SA＜ CFeasible－SA＜ CGA，其中Feasible－ SA 和GA 算法的成本值比较接近。随着服务组合规模n的扩大，不同算法的成本值差距逐渐增大。上述结果表明，单纯考虑有效解方式会使结果陷入局部最优，而基本启发式算法又易受无效解的干扰，从而使算法得到的成本值偏大。

图3 不同算法得到的最优组合代价Fig.3 Composition cost comparison among different algorithms

比较不同算法的时间消耗，如图4 所示。从实验结果可以看出，基本遗传算法GA 的时间消耗最小且波动不明显，单纯考虑有效解的模拟退火算法Feasible－SA 的时间消耗最大，且随问题规模呈非线性增长，而SCM－SA 算法的时间消耗低于Feasible－SA，原因在于，GA 的新解产生函数跟问题规模无关，而Feasible－SA 和SCM－SA 的新解产生函数跟问题规模有关，并且Feasible－SA 只考虑有效解，导致调用新解产生函数的次数多于SCM－SA，因此时间消耗大于SCM－SA。

图4 不同算法的时间消耗Fig.4 Time cost comparison among different algorithms

上述实验在不同组合规模和仿真数据下重复进行，结果表明SCM－SA 算法在服务组合成功率和服务组合成本上优于其他算法。

5 结束语

本文对网络功能虚拟化中的服务功能链构建和服务组合优化问题进行了论述。首先，针对服务实体的性能描述需求和匹配约束特性，给出了一种服务实体性能模型，并在此基础上形式化分析服务组合优化问题。然后，为减轻大量不满足性能约束的无效解对搜索过程的干扰，提出了改进的模拟退火算法SCM－SA。最后，通过仿真实验验证了SCMSA 算法在服务组合成功率和组合成本上具有明确的优势。

本文对单一服务组合请求下的优化问题进行了研究，而实际的服务组合请求可以是在线到达的，所以下一步需对在线模式下的服务组合优化问题进行研究。

［1］Network Functions Virtualisation(NFV).Network Operator Perspectives on Industry Progress，ETSI ［EB/OL］.2014－04－ 01［2015－ 01－ 05］.http://portal.etsi.org/NFV/NFV_White_Paper2.pdf.

［2］Yu M，Yi Y，Rexford J，et al.Rethinking virtual network embedding:substrate support for path splitting and migration［J］.ACM SIGCOMM Computer Communication Review，2008，38(2):17－29.

［3］Chowdhury M，Rahman M R，Boutaba R.Vineyard:Virtual network embedding algorithms with coordinated node and link mapping［J］.IEEE/ACM Transactions on Networking，2012，20(1):206－219.

［4］Boucadair M，Jacquenet C，Parker R，et al.Service Function Chaining:Framework ＆ Architecture［EB/OL］.2014－08－16［2015－01－05］.http://tools.ietf.org/html/draft－boucadair－sfc－framework－02.

［5］Quinn P，Beliveau A.Service Function Chaining(SFC)Architecture［EB/OL］.2014－02－04［2015－01－05］.http://tools.ietf.org/html/draft－merged－sfc－architecture－01.

［6］Menasce D.QoS issues in Web service［J］.Internet Computing，2002，6(6):72－75.

［7］Zeng L，Benatallah B，Ngu A H H，et al.Qos－aware middleware for web services composition［J］.IEEE Transactions on Software Engineering，2004，30(5):311－327.

［8］Zeng L，Benatallah B，Dumas M，et al.Quality driven web services composition［C］//Proceedings of the 12th International Conference on World Wide Web.New York:ACM，2003:411－421.

［9］张成文，苏森，陈俊亮.基于遗传算法的QoS 感知的Web服务选择［J］.计算机学报，2006，29(7):1029－1037.ZHANG Chengwen，SU Sen，CHEN Junliang.Genetic algorithm on web services selection supporting QoS［J］.Chinese Journal of Computers，2006，29(7):1029－1037.(in Chinese)

［10］蒋哲远，韩江洪，王钊.动态的QoS 感知Web 服务选择和组合优化模型［J］.计算机学报，2009(5):1014－1025.JIANG Zheyuan，HAN Jianghong，WANG Zhao.An Optimization Model for Dynamic QoS－Aware Web Services Selection and Composition［J］.Chinese Journal of Computers，2009(5):1014－1025.(in Chinese)

［11］Ma H，Bastani F，Yen I L，et al.QoS－ driven service composition with reconfigurable services［J］.IEEE Transactions on Services Computing，2013，6(1):20－34.

［12］Xiang F，Hu Y，Yu Y，et al.QoS and energy consumption aware service composition and optimal－ selection based on Pareto group leader algorithm in cloud manufacturing system［J］.Central European Journal of Operations Research，2014，22(4):663－685.

［13］Tao F，LaiLi Y，Xu L，et al.FC－PACO－RM:a parallel method for service composition optimal－selection in cloud manufacturing system［J］.IEEE Transactions on Industrial Informatics，2013，9(4):2023－2033.

［14］王勇，代桂平，侯亚荣.信任感知的组合服务动态选择方法［J］.计算机学报，2009，32(8):1668－1675.WANG Yong，DAI Guiping，HOU Yarong.Dynamic methods of trust－aware composite service selection［J］.Chinese Journal of Computers，2009，32(8):1668－1675.(in Chinese)

［15］Dick R P，Rhodes D L，Wolf W.TGFF:task graphs for free［C］//Proceedings of the 6th International Workshop on Hardware/Software Codesign.Seattle:IEEE，1998:97－101.