软件系统自适应提供了应对动态变化的环境和不确定的需求的技术方案.在已有的软件系统自适应性的相关研究中,有一类工作将软件系统自适应性转换为回归、分类、聚类、决策等问题,并利用强化学习、神经网络/深度学习、贝叶斯决策理论和概率图模型、规则学习等机器学习算法进行问题建模与求解,并以此构造软件系统自适应机制.将其称为机器学习赋能的软件自适应性.通过系统化的文献调研,综述了该研究方向的前沿工作:首先介绍基本概念,然后分别从机器学习、软件自适应的视角对当前工作进行分类;按机器学习算法、软件对外交互、软件对内控制、自适应过程、自适应任务和学习能力的对应关系等方面进行分析;最后对未来的研究进行展望.
Software self-adaptation (SSA) provides a way of dealing with dynamic environment and uncertain requirement. There are existing works that transform the dynamic and uncertainty concerned by SSA into regression, classification, cluster, or decision problems; and apply machine learning algorithms, including reinforcement learning, neural network/deep learning, Bayesian decision theory and probabilistic graphical model, rule learning, to problem formulation and solving. These kinds of work are called as "machine learning enabled SSA" in this study. The survey is conducted on the state-of-the-art research about machine learning enabled SSA by firstly explaining the related concepts of SSA and machine learning; and then proposing a taxonomy based on current work from SSA perspective and machine learning perspective respectively; analyzing the machine learning algorithms, software external interaction, software internal control, adaptation process, the relationship between SSA task and learning ability under this taxonomy; as well as identifying finally deficiency of current work and highlighting future research trends.
软件系统自适应性(software self-adaptation)指系统能够在运行时(run-time), 根据其对环境和系统本身的感知, 自主地调整自身的行为, 以有效地应对动态变化的环境和不确定的需求, 从而使系统具有更好的灵活性、可靠性、鲁棒性等[
通过机器学习构建软件系统的自适应策略是一种有效手段, 其原理是将软件系统自适应行为转换为分类、回归、聚类、决策等机器学习擅长的问题, 利用监督学习、无监督学习、强化学习、贝叶斯网络等技术, 获取自适应策略.其优点是:(1)在预先缺少领域知识(domain knowledge)的情况下, 学习出满足性能要求的自适应策略; (2)借助高效的算法来解决软件系统自适应行为中隐含的搜索、最优化和不确定性分析等问题[
本文关注的3个问题如下.
(1) RQ1:现有机器学习赋能的软件系统自适应性研究有哪些关注点, 如何分别从自适应性和机器学习角度进行分类?目的是建立系统化的分类框架, 以概括相关工作所关注的话题和涉及的方向.
(2) RQ2:当前软件系统自适应任务的哪些方面采用了哪些机器学习技术?目的是在RQ1所概括的分类框架下, 建立机器学习技术和软件系统自适应任务的关联.
(3) RQ3:当前, 基于机器学习赋能的软件系统自适应性还存在哪些不足?未来发展趋势怎样?目的是在已有研究的基础上, 展望其发展趋势, 为进一步的研究提供参考.
本文第1节介绍相关的背景知识.第2节给出本文采用的综述方法以及获取、筛选相关工作的标准与过程.第3节提出分类框架, 并对现有工作进行分析与研究.第4节讨论机器学习赋能的软件系统自适应性存在的问题, 并展望未来的研究趋势.第5节对全文进行总结.
现代软件系统日趋复杂, 其交互环境和需求都可能动态变化, 并具有不确定性.这要求软件系统具有自适应性, 以应对运行场景的复杂性、动态变化性和不确定性.从概念上说, 自适应性是指系统能够在运行时, 根据对环境和系统本身的感知, 自主地调整自身行为[
就自适应软件系统设计而言, 其核心是软件系统的自适应策略的设计.最朴素的手段是依靠经验定义一组形为“条件-动作”的规则, 表达在某种“条件”下采取某种“动作”(即ad hoc方法).相当多的工作引入控制论方法, 基于经典控制论[
自适应系统:基于控制论的观点
Constituent parts of a self-adaptive system: Control theory perspective
自适应逻辑多由“收集(collect)-分析(analyze)-决策(decide)-动作(act)”的过程来实现, 用前馈(feedforward)或反馈(feedback)的方式进行应用逻辑的调控[
除MAPE-K外, 以反馈控制回路为基础设计的自适应软件系统架构还有Rainbow[
近年来, 很多工作将机器学习引入到自适应软件系统中, 比如把机器学习算法应用于软件系统自适应行为的部分过程中[
机器学习“研究让算法利用经验来改善系统自身性能”, Mitchell给出机器学习的定义[
(1) 强化学习
学习如何将环境状态映射到系统动作, 以获得最大奖励[
软件系统自适应性采用强化学习的原因是:(a)强化学习中, 系统和环境交互的机制可对应于自适应软件系统的反馈回路[
(2) 神经网络和深度学习
神经网络是由具有适应性的简单单元组成的并行互连网络[
(3) 贝叶斯决策理论和概率图模型
研究在不完全信息下变量的概率以及多个变量间的概率依赖关系等, 关注不确定性的建模.贝叶斯决策理论在概率框架下实施最优决策[
概率图模型用图表达变量间的关系, 把学习任务归结成对变量概率分布的计算[
其中,
目前, 这类工作的应用场景包括:(a)贝叶斯网络用于表达和分析环境或系统中和自适应相关的不同随机变量的关系; (b)隐马尔可夫链用来建模存在不确定性时的系统运行状态; (c)贝叶斯分类器或条件随机场用于刻画自适应系统的需求获取和系统设计时的不确定性; (d)马尔可夫过程(Markov decision process, 简称MDP)用于支持含不确定性的自适应策略的生成[46-48], 也有工作改进强化学习, 并加入高斯过程, 来应对存在不确定性时的自适应决策[
(4) 规则学习
“规则”指语义明确且能描述蕴含于数据分布背后的规律或者领域知识的逻辑规则[
(5) 迁移学习
迁移学习常用于数据不足的场景, 利用在训练数据充分的问题上训练好的模型, 通过迁移操作使模型适合于新的问题[
参考Kitchenham[
机器学习赋能的软件自适应性涉及机器学习与自适应软件系统两个研究方向, 本文以((machine learning) or (learning) or (learn)) and ((adaptation) or (adaptive) or (self-adaptive) or (self-adaptation) or (dynamic) or (uncertainty))为关键词, 在IEEE Xplore Digital Library、ACM Digital Library、Springer Digital Library、Elsevier Science Direct、Google Scholar、中国知网等文献数据库中检索, 并采取“滚雪球”的方法:(1)在已获取文献的作者的论文列表中发现新文献; (2)在已搜集文献的参考文献和引证文献中发现新文献; (3)将新发现的文献加入已获取的文献集合中, 继续方法(1)和方法(2), 直到不再发现新文献为止, 尽可能多地覆盖已有的相关工作.这些文献需要进一步筛选, 筛选标准如下.
(1) 文献发表时间在2003年~2019年之间.
(2) 文献采用了机器学习技术(包括线性模型、深度学习、决策树、支持向量机、贝叶斯决策理论、聚类、规则学习、强化学习、迁移学习等).
(3) 文献的贡献领域为自适应软件系统或软件系统自适应性.
(4) 文献的语言为英文或中文.
(5) 2018年及以前的文献, 其被引次数高于3.
经过以上步骤检索文献, 并按照上述标准进行筛选, 最后共收集到78篇文献(具体见附表A).其中有60篇会议论文、15篇期刊论文、3本专著.会议论文主要来自Int’l Conf. on Software Engineering(ICSE)、Int’l Symp. on Software Engineering for Adaptive and Self-managing Systems(SEAMS)、Int’l Conf. on Service-oriented Computing(ICSOC)、Int’l Conf. on Autonomic Computing(ICAC)、Int’l Conf. on Self-adaptive and Self-organizing Systems(SASO)等.其中, SASO与ICAC于2020年合并为Int’l Conf. on Autonomic Computing and Self-organizing Systems(ACSOS).期刊论文主要来自IEEE Trans. on Software Engineering等.
机器学习赋能的软件自适应相关工作分析
Analysis of related work about machine learning enabled software self-adaptation
文献 | 分类 | |||||||||
机器学习视角 | 软件自适应视角 | |||||||||
应用方式 | 学习算法 | 被控对象 | 监控内容 | 自适应目标 | 引起自适应学习的原因 | 决策方式 | 自适应操作 | 验证评价 | ||
端到端 | 阶段/过程 | |||||||||
表中符号的含义为:0未使用;unknown论文中不明确;E端到端方法;P1策略生成;P2策略演化;P3参数估计; P4效果预测;P5环境预测;L1强化学习;L2贝叶斯决策理论与概率图模型;L3神经网络/深度学习;L4规则学习; L5迁移学习;L6其他算法;C1面向服务的信息系统;C2机器人系统;C3信息物理系统;M1外部环境数据;M2系统自身数据;M3应用需求;G1保持系统稳态;G2最优化可变目标;G3最优化不可变目标;R1外部环境变化;R2系统自身变化;R3其他系统变化;R4需求不确定性;R5设计时不确定性;R6运行时不确定性;D1静态策略;D2动态策略;D3连续控制;E1调整参数;E2调整行为;E3调整结构;V1理论证明;V2案例研究;V3仿真模拟. | ||||||||||
[18] | 0 | P4 | L2 L6 | C1 | M2 M3 | G2 | R1 R4 R6 | D1 | E3 | V2 |
[22] | 0 | P1 P2 | L1 | C2 | M1 M2 | G3 | R3 R6 | D2 | E3 | V2 |
[55] | 0 | P4 | L5 | C2 | M1 M2 | G3 | R1 R2 R5 R6 | D1 | E2 E3 | V2 |
[28] | E | 0 | L1 | C1 | M2 | G3 | R1 R6 | D2 | E1 E2 | V2 |
[71] | E | 0 | L1 | C1 | M1 M2 | G3 | R1 R5 R6 | D2 | E2 | V2 |
[32] | 0 | P4 | L3 | C1 | M2 M3 | G2 | R1 R4 R6 | D1 | E3 | V2 |
[19] | 0 | P3 | L6 | C1 | M2 M3 | G1 G3 | R2 | D1 | E2 | V2 |
[56] | 0 | P4 | L5 | C2 | M1 M2 | G3 | R1 R2 R5 R6 | D1 | E2 E3 | V2 |
[72] | 0 | P3 P5 | L4 | C2 | M1 M2 | G3 | R5 R6 | D2 | E3 | V2 |
[62] | 0 | P1 P2 | L1 | C1 | M1 M2 | G3 | R1 R6 | D2 | E3 | V2 |
[67] | 0 | P5 | L4 | C2 | M1 | G3 | R1 R4 R5 R6 | D1 | E1 | V3 |
[76] | 0 | P1 | L4 L6 | C2 | M1 M2 M3 | G1 G2 | R1 R2 | D3 | E3 | V2 |
[89] | 0 | P1 | L4 L6 | C2 | M1 M2 M3 | G1 G2 | R1 R2 | D3 | E3 | V2 |
[50] | 0 | P1 | L4 | C3 | M2 M3 | G3 | R2 R4 | D1 | E1 | V2 |
[37] | 0 | P3 | L3 L4 | C2 | M1 M3 | G1 G3 | R1 R4 R6 | D1 | E1 | V2 |
[27] | E | 0 | L3 | C3 | M2 | G3 | R2 R6 | D2 | E1 | V3 |
[20] | 0 | P1 P2 | L4 L6 | C3 | M1 M2 | G3 | R1 R5 R6 | D1 | E1 E2 | V3 |
[106] | 0 | P1 P2 | L4 | C3 | M1 | G3 | R1 R2 | D3 | E2 E3 | V2 |
[66] | E | 0 | L1 | C3 | M1 | G3 | R1 R6 | D2 | E1 E2 | V2 |
[38] | E | 0 | L1 L3 | C3 | M1 | G3 | R1 | D2 | E2 | V2 |
[35] | 0 | P2 | L3 | C2 | M1 | G3 | R1 R5 | D1 | E1 | V2 |
[80] | 0 | P3 P5 | L3 L6 | unknown | M1 | unknown | R6 | D1 | E1 | V1 V3 |
[108] | E | 0 | L1 | C1 | M1 M2 | G3 | R1 R6 | D1 | E3 | V2 |
[21] | 0 | P1 P2 | L1 | C1 | M1 M2 | G3 | R1 | D2 | E2 | V3 |
[81] | 0 | P1 P4 | L1 | C1 | M1 M2 | G1 G3 | R1 R2 R6 | D2 | E1 E2 | V2 |
[74] | 0 | P4 | L3 | C1 | M2 | G2 | R2 | D1 | E1 | V2 |
[46] | E | 0 | L1 L2 | C1 | M1 M2 | G3 | R1 R6 | D1 | E2 | V3 |
[110] | E | 0 | L1 | C1 | M2 | G3 | R2 R6 | D2 | E2 | V2 |
[47] | E | 0 | L1 | C1 | M2 | G3 | R2 | D1 | E2 | V3 |
[23] | E | 0 | L1 | C1 | M2 | G3 | R2 | D2 | E2 | V3 |
[26] | 0 | P1 P2 P4 | L1 L3 | C1 | M1 M2 M3 | G2 | R1 R2 R4 R5 R6 | D2 | E1 | V3 |
[69] | 0 | P2 P3 | L2 | C2 | M1 M3 | G2 | R1 R4 R5 R6 | D2 | E1 | V2 |
[30] | 0 | P2 | L1 | C1 | M1 M2 | G3 | R1 R5 R6 | D1 | E1 E3 | V3 |
[29] | 0 | P1 | L1 L3 | C1 | M1 M2 | G3 | R1 R2 | D1 | E2 | V2 |
[97] | E | 0 | L1 | C1 | M1 | G3 | R1 R4 R5 R6 | D1 | E3 | V3 |
[39] | 0 | P1 P2 P3 | L3 | C1 | M1 M2 | G1 G3 | R1 R2 R5 R6 | D3 | E1 | V3 |
[40] | 0 | P1 P2 | L3 | C1 | M1 M2 | G3 | R1 R2 R6 | D3 | E1 E2 | V3 |
[70] | E | 0 | L2 | C1 | M1 M2 | G2 | R1 R4 R5 R6 | D2 | E2 | V2 |
[48] | 0 | P1 P5 | L2 | C1 | M1 M2 | G3 | R1 R5 R6 | D3 | E1 E2 | V3 |
[111] | 0 | P1 | L1 | unknown | M1 M2 | G3 | R1 R2 R6 | D2 | E3 | unknown |
[75] | 0 | P5 | L2 | C1 | M1 M2 | G3 | R1 R2 R4 R5 R6 | D3 | E1 | V3 |
[3] | 0 | P5 | L2 | C1 | M1 M2 | G3 | R1 R2 R6 | D1 | E1 | V3 |
[86] | 0 | P4 P5 | L2 L3 | C3 | M1 | G3 | R1 R5 R6 | D3 | E2 | V2 |
[109] | 0 | P3 P4 | L2 | C1 | M2 | G3 | R2 R6 | D3 | E1 | V3 |
[33] | 0 | P1 P2 | L1 L3 | C1 | M2 | G1 G3 | R2 R6 | D3 | E3 | V3 |
[112] | 0 | P1 P2 | L1 L3 | C1 | M2 | G3 | R2 R6 | D3 | E3 | V3 |
[83] | 0 | P1 P4 | L1 | C1 | M1 M2 | G3 | R1 R6 | D2 | E3 | V2 |
[88] | E | 0 | L1 | C1 | M1 M2 | G3 | R1 R2 R3 | D1 | E2 | V3 |
[34] | 0 | P4 | L3 | C1 | M2 | G3 | R2 | D3 | E1 | V3 |
[113] | 0 | P1 P4 | L1 | C1 | M2 M3 | G2 | R2 R4 | D1 | E1 | V3 |
[95] | 0 | P1 P4 | L3 | C1 | M2 | G3 | R2 R4 | D2 | E1 | V3 |
[114] | 0 | P1 | L1 | C1 | M1 M2 | G3 | R1 | D1 | E1 | V3 |
[93] | 0 | P1 P2 | L2 | C2 | M1 M2 M3 | G2 | R1 R2 R4 R5 R6 | D2 | E2 | V2 |
[115] | 0 | P1 | L1 L6 | C2 | M1 M2 M3 | G1 G2 | R1 R2 R3 | D3 | E1 | V3 |
[116] | 0 | P1 | L6 | C2 | M1 M2 M3 | G1 G2 | R1 R2 R3 | D3 | E2 | V3 |
[58] | 0 | P5 | L6 | C3 | M1 M2 | G1 | R1 R2 R3 | D3 | E2 E3 | V3 |
[60] | 0 | P2 | L6 | C3 | M1 M2 | G1 | R1 R2 R3 | D3 | E2 | V3 |
[59] | 0 | P1 | L1 L6 | C1 | M1 M3 | G2 | R1 R2 R3 | D1 | E1 | V3 |
[94] | 0 | P1 P2 | L1 L3 | C1 | M1 M2 M3 | G2 | R1 R2 R6 | D2 | E1 | V3 |
[117] | 0 | P1 | L1 | C1 | M1 | G1 G3 | R1 R6 | D1 | E2 | V2 |
[36] | 0 | P3 P4 | L3 | C3 | M1 | G1 G3 | R1 R4 R5 R6 | D3 | E1 | V2 |
[73] | 0 | P1 P2 | L1 | C1 | M1 M3 | G2 | R1 R4 R6 | D2 | E1 | V3 |
[77] | 0 | P4 | L6 | C1 | M1 M2 | G3 | R1 R2 | D1 | E3 | V3 |
[118] | 0 | P1 | L6 | C3 | M1 | G1 G3 | R1 R6 | D1 | E2 | V3 |
[68] | 0 | P1 P4 | L2 L3 | C2 | M1 M2 M3 | G1 G2 | R1 R2 R4 R5 R6 | D2 | E1 E2 | V3 |
[90] | 0 | P4 P5 | L4 L6 | C3 | M1 | G3 | R1 R5 R6 | D3 | E1 E3 | V2 |
[96] | 0 | P3 | L3 L6 | C1 | M1 M2 | G1 G3 | R2 R3 | D3 | E2 | V3 |
[103] | 0 | P1 P4 | L3 | C1 | M1 M2 | G1 G3 | R1 R5 R6 | D3 | E1 | V3 |
[119] | E | 0 | L1 L6 | C1 | M1 M2 | G3 | R1 R2 R3 | D1 | E2 | V3 |
[120] | 0 | P1 | L6 | C1 | M1 M2 | G3 | R1 R5 R6 | D3 | E3 | V2 |
[121] | 0 | P1 P2 | L3 L6 | C3 | M1 | G1 G3 | R1 R6 | D3 | E1 | V3 |
[107] | 0 | P1 | L1 L6 | C3 | M1 M2 | G3 | R1 R2 R3 R6 | D1 | E3 | V3 |
[82] | E | 0 | L1 L3 | C1 | M1 M2 | G1 G3 | R1 R4 R6 | D1 | E3 | V3 |
[122] | E | 0 | L3 L6 | C1 | M1 M2 | G3 | R1 R2 | D1 | E2 | V3 |
[85] | 0 | P1 P4 P5 | L2 L6 | C1 | M1 M2 | G1 G3 | R1 R2 | D1 | E2 | V3 |
[78] | 0 | P3 | L6 | C3 | M1 | G1 G3 | R1 R4 R6 | unknown | E1 | V2 |
[79] | 0 | P5 | L6 | C1 | M1 M2 | G3 | R1 R2 | D3 | E3 | V2 |
[123] | E | 0 | L1 | C1 | M2 | G3 | R2 R5 R6 | D1 | E1 E2 | V3 |
本节回答研究问题RQ1, 提出对现有文献的分类标准, 分软件系统自适应性和机器学习两个视角进行考察:软件系统自适应性视角重点在自适应软件系统的体系结构、行为、建模等方面; 机器学习视角侧重于从任务出发, 分析如何将软件系统自适应性的问题规约到机器学习任务.
软件系统自适应性可以从3个视角进行分类:外部特性视角、系统结构视角和功能部件视角.
● 外部特性视角
关注软件系统的输入/输出特性.输入是监控信息, 包括物理数据和应用需求.物理数据指软件系统运行过程中可感知的客观数据, 来自外部环境或系统自身.输出是软件系统的自适应操作, 按粒度从细到粗可分为参数调整、行为调整、结构调整等, 该层的结构如
软件自适应系统外部特性层
External characteristic layer of software self-adaptation
● 系统结构视角
关注软件系统的控制器和被控系统以及与环境间的交互, 用控制回路来表示.如
软件自适应系统结构层次
Architecture layer of software self-adaptation
大部分研究侧重“自适应逻辑”, 即控制器的设计, 关注自适应目标、原因和决策方式.保持系统稳态和最优化需求目标, 是两种典型的自适应目标.根据需求目标是否可变, 后者又可分为最优化可变目标和最优化不可变目标.自适应原因来自于动态性(dynamic)和不确定性(uncertainty), 前者包括外部环境变化、系统自身变化以及其他系统的变化.虽然其他系统可看作外部环境, 但外部环境变化和其他系统的变化有较大差异, 比如:外部环境的动态性一般是客观现象, 不会因为与系统的交互而改变; 而其他系统的动态性, 有可能会由于系统间的交互而发生改变[
● 功能部件视角
将系统结构层中的控制器和被控系统展开为具体的功能部件.大多数工作基于IBM的MAPE-K框架[
软件自适应功能部件层次MAPE-K控制回路
Functional component layer MAPE-K control loop of software self-adaptation
据此, 可以根据已有工作构建出机器学习赋能的软件自适应性的特征模型, 如
自适应软件系统特征模型
Feature model of self-adaptive software system
从自适应逻辑实现的角度, 可以从如下两个方面来分类:一是实现自适应逻辑的方法, 二是自适应逻辑的构造方式.其中, 实现自适应逻辑的方法分为规则/策略式和控制函数式两种.规则/策略式将自适应逻辑表达为事件或状态到动作的映射, 描述了软件系统在某个条件下应当采取某种措施.传统的规则/策略式一般用PDL策略描述语言[
控制函数式则采用PID(proportion-integral-differential)控制器实现自适应结构中的控制回路[
构造自适应逻辑的方法有人工设计和自动设计两种:人工设计主要根据专家经验来定义规则; 自动设计采用学习算法, 先获得自适应软件系统在需求、设计、运行时的相关数据, 提取出任务、经验、性能, 再利用学习算法获得规则/策略或控制函数.
除了上述3个层次和两个维度, 验证评价也是一个重要问题.验证评价指对方法的效果以及系统的运行性能进行评价分析.主要方法有理论证明、案例研究(case study)、模拟仿真(simulation).目前, 理论分析的工作几乎没有, 大部分验证评价都是采用后两种方法.案例研究指搭建基于特定场景的实验系统, 并进行实验评估.模拟仿真则借助于仿真工具对自适应算法进行评估.
软件系统自适应性本质上是应对不确定性, 含场景不确定性、环境和系统的动态变化性、效果的不确定性.这3类不确定性分别为机器学习方法限定了不同的问题域(problem domain).下面将根据面向目标的方法对此进行分析, 从问题域出发, 划分出不同的任务, 最终到具体的机器学习技术.
● 场景的不确定性:系统设计时, 对环境或系统的知识掌握不完整或存在不一致, 难以确定其环境变量的取值或系统的配置, 这是产生自适应需求的根本原因.这类不确定性包括需求缺失、需求二义性、需求改变、环境假设不准确或错误、传感器误差或错误、监控信息不完整等.
● 系统和环境的动态变化性:系统运行时, 其运行环境、交互环境或系统自身的状态都会发生动态改变, 这是产生系统自适应需求的运行时原因, 具体包括环境特性改变、环境行为改变、系统结构改变、系统行为改变、系统属性改变等.
● 操作效果的不确定性:系统运行时, 由于操作延迟、假设错误、外界干扰等, 导致系统行为的实际结果和预期结果不一致.
如果以“系统自适应性(G)”作为根目标, 根据上述3个关注点, 可分解出3个子目标, 即“应对场景的不确定性(G1)”、“应对系统和环境的动态变化性(G2)”和“应对操作效果的不确定性(G3)”.向下延伸构建系统自适应性的目标模型, 进而考察机器学习在其中发挥的作用.如
机器学习赋能的自适应软件目标模型
Goal decomposition of machine learning enabled self-adaptive software
机器学习赋能的自适应软件的目标分解
Goal decomposition of machine learning enabled self-adaptive software
一级子目标 | 二级子目标 | 任务功能说明 |
G1应对场景不确定性 | G1.1应对需求缺失 | 需求获取和分析阶段未成功提取出某些需求, 但这些需求同软件系统行为密切相关 |
G1.2应对需求二义性 | 某些需求表达不清晰, 存在不同的解释方式 | |
G1.3应对需求改变 | 一些需求没有反映出用户对系统真实需要和对需求约束 | |
G1.4应对假设不准确或错误 | 对无法提前获取的环境或系统特性的不准确或错误的主观估计, 不准确是指通过分析方法得到的估计值和真实值有差异, 错误是指分析估计的方法不正确 | |
G1.5应对感知误差或错误 | 行时监测器受限于其精度或性能, 导致测量值和真实值存在误差, 或者监测器损坏、真实值超出测量范围或被攻击导致测量结果错误 | |
G2应对系统和环境的动态变化性 | G2.1应对环境状态变化 | 环境特性发生改变, 系统可以观察到这些变化, 例如, 智能家居中, 白天、黄昏、夜晚等, 自动驾驶中, 晴天、雾天、雨天、雪天等 |
G2.2应对环境行为变化 | 环境行为是指环境对系统的主动交互, 例如, Web服务器系统中, 网站访问量、访问者浏览网页的偏好等, 机器人系统中, 人对机器人进行路径或者动作的干扰、允许机器人进入的区域改变等 | |
G2.3应对系统结构变化 | 系统构件或构件间的联系发生改变, 例如云计算系统中, 底层网络架构或信息存储架构发生改变等 | |
G2.4应对系统行为变化 | 运行过程中, 在内外因素的作用下, 系统的行为没有按照事前的规划执行, 包括了系统主动调整的行为变化、由于失效产生的错误行为等, 例如物联网系统中, 监控的时间周期改变、网络传输优先级改变等 | |
G2.5应对系统属性变化 | 系统属性指设计时对系统功能性或非功能性的需求和支撑系统的关键指标, 例如, Web服务器中, 通信网络的带宽、服务质量(QoS)、电能消耗等, 机器人系统中, CPU计算性能、传感器精度、内部系统总线的速度等 | |
G3应对操作效果的不确定性 | G3.1应对系统外部特性的不确定性 | 指系统的行为操作, 其实际的输入/输出和规划的输入/输出发生偏差, 例如机器人系统中, 控制器向动力系统发出动作指令并期望得到某个效果, 但其物理负载、机械误差、外部环境使动力系统执行的动作指令的效果发生偏差 |
G3.2应对内部影响的不确定性 | 系统行为导致系统自身产生了未经验证的改变, 这些系统和系统变化间的相互作用, 难以建立精确的联系, 例如, 物联网系统中, 降低CPU频率以降低系统功耗, 引发整个系统监控周期、通信延迟、响应时间等性质的改变 | |
G3.3应对延迟效应的不确定性 | 系统行为不能直接作用到系统或外部环境中, 会有一段延迟, 在行为到产生效果这段过程中, 系统处于不稳定的状态, 例如Web服务器, 从开启备用服务器到备用服务器成功运行服务有延迟, 且延迟时间取决于系统当前负载、网络带宽、延迟期间内外部服务请求数量、开启备用服务器的顺序等因素攸关 | |
G3.4应对需求指标的不确定性 | 对于系统行为, 很多情况下不能直接知道行为会给系统的需求指标(例如QoS, 安全性要求等)带来什么样的影响, 例如, Web服务器, 调整服务响应的优先级顺序后, 不能直接获得QoS指标 |
根据系统自适应目标模型, 对已有文献的工作进行任务分类, 可以提取出17类不同任务(
自适应任务及解决方法
Self-adaptation task and solution
编号 | 任务描述 | 解决方法 | 解决方法分类 | 采用的机器学习算法 |
需求反射机制 | ACon[ |
策略演化 | 深度学习, 马尔可夫决策过程 | |
需求估计 | 需求模糊逻辑[ |
参数估计 | 神经网络 | |
假设参数化 | 模型修正[ |
参数估计 | 马尔克夫决策过程, 迁移学习 | |
加工生数据 | ACon[ |
效果预测 | 深度学习, 聚类算法 | |
推测隐藏信息 | RE-STORM[ |
参数估计 | 部分可观测马尔可夫过程, 动态决策网络 | |
环境状态建模 | 环境状态自动机[ |
环境预测 | 强化学习 | |
环境行为预测 | 运行时环境模型[ |
环境预测 | 深度学习 | |
系统状态建模 | 系统服务组合规划[ |
效果预测 | 高斯过程, 强化学习 | |
触发事件分析 | 条件触发机制[ |
策略演化, 环境预测 | 强化学习, 马尔可夫过程, BAAM-WELCH算法 | |
操作延迟分析 | 时间敏感资源调度[ |
环境预测, 效果预测 | 强化学习 | |
操作到系统变化映射 | FUSION[ |
效果预测, 策略生成 | 深度学习, 迁移学习, 马尔克夫过程 | |
环境历史数据分析 | ACon[ |
环境预测 | 深度学习, 数据挖掘 | |
其他系统行为预测 | 面向服务的多智能体体系结构[ |
环境预测 | 多智能体强化学习 | |
外部特性分析 | 自适应策略生成演化[ |
策略演化 | 强化学习 | |
目标满意度分析 | FUSION[ |
效果预测 | 深度学习 | |
操作到系统性能映射 | FUSION[ |
策略生成 | 深度学习, 强化学习 | |
系统历史数据分析 | 自适应大数据分析[ |
效果预测 | 深度学习, 数据挖掘 |
(1) 端到端的方法
考虑系统的输入/输出的外部特性, 忽略系统内部各功能部件, 通过机器学习算法, 得到满足自适应目标的外部特性的自适应策略.采用端到端的场景通常具有“外部逻辑清晰、内部结构复杂”的特点:(a)系统的输入/输出的关联明晰, 且有足够的数据或者训练环境, 以便算法学习从环境数据到策略的直接映射; (b)系统内部结构相互关联, 非常复杂, 某些功能部件或者过程甚至无法有效观测.端到端的方法可以进一步细分为预测和控制:预测指输入是环境/系统运行数据, 输出是环境/系统未来状态; 控制指输入是环境/系统运行数据, 输出是当前时刻应采取的自适应操作.
强化学习、神经网络/深度学习是常用的端到端学习算法.强化学习中的智能体、策略、状态、动作、奖励、环境可以和自适应软件系统、自适应逻辑、环境或系统状态、自适应操作、效用、上下文(context)对应, 在构建自适应逻辑时, 只需考虑系统输入的状态、效用, 输出的自适应操作, 而不必关心系统内部对状态、效用、自适应操作的分析[
(2) 阶段/过程的方法
根据第3.1节的系统结构层和功能部件层, 自适应软件系统由多个功能部件组成, 其自适应过程分为多个阶段.阶段/过程方法就是指解决其中某个阶段上的分类、回归或决策任务.已有工作展示, 机器学习可以用在不同的阶段, 承担不同的角色, 大致分5种:策略生成、策略演化、参数估计、效果预测和环境预测.策略生成指在离线数据上进行训练得到自适应策略[
本节针对研究问题RQ2, 以软件系统自适应性为目标, 分析其与机器学习方法之间的关联, 讨论为实现系统自适应性而采用的各类机器学习赋能技术.
如
文献中的不同机器学习算法
Different machine learning algorithms in literature
● 采用强化学习的工作分为基于模型和免模型两类.
➢ 基于模型的方法用马尔可夫过程来建模实际环境, 比如传统的马尔可夫模型(MDP)[
➢ 免模型的算法不构造环境模型, 而是直接生成策略[
● 贝叶斯决策理论和概率图模型除了可以为自适应决策提供建模支持外[
● 神经网络/深度学习通常被应用于采用端到端方法进行效果建模、环境预测、效果预测等任务, 采用黑盒的方法, 只考虑所关注部分的输入/输出的外部特性, 不考虑该部分的内部结构或逻辑.适用的场景有两个特点:(1)系统或环境内部结构复杂或难以观测; (2)系统或环境的输入/输出的数据非常明确, 且容易获取.也有文献采用部分可观测马尔可夫决策过程(POMDP)[
● 规则学习以一阶逻辑或命题逻辑的形式表达自适应策略, 这样构造的系统具有较高的可验证性、可靠性、可理解性.MORPH[
每年发表的论文(2004~2018)
Papers published per year (2004~2018)
机器学习算法是和任务相关的, 不同的任务可以采用不同的方法.例如, 文献[
从系统外部特性视角出发, 自适应涉及系统的输入/输出.其中,
● 输入包含外部环境数据、系统自身数据和应用需求, 这些输入由系统的监测过程来收集.监测过程收集的这些未经处理的原始数据(即“生数据”), 可能是不准确的、模糊的、有噪音的、甚至是错误的, 系统需要对“生数据”作预处理, 以解决可能出现的需求缺失、需求二义、需求改变、传感器误差或错误等问题.这里涉及4类任务:
● 自适应系统的输出是自适应操作, 即对被控系统(自适应逻辑和应用逻辑完全分离时)或者环境(自适应逻辑和应用逻辑没有完全分离)的行为动作, 由执行过程实施.自适应操作按其粒度从细到粗可以分为:(1)参数调整, 改变应用逻辑中的参数设置; (2)行为调整, 改变应用逻辑中的方法、函数调用; (3)结构调整, 改变应用逻辑中的构件(component)或构件之间的关系.
自适应系统外部特性视角和端到端的机器学习方法联系紧密, 端到端的方法只考虑系统外部特性, 主要有强化学习和深度学习等方法, 自动建立从输入端的监测内容到输出端的自适应操作的映射.端到端的方法将在第4.5节详细分析.
文献中不同的监测数据
Different monitoring data in literature
文献中不同的自适应操作
Different self-adaptive execution in literature
自适应系统结构视角关注控制器和被控系统, 其中在控制器部分主要关注自适应目标、自适应原因和自适应决策方式.自适应目标有两种, 即保持系统稳态和最优化需求目标.
保持系统稳态的问题可描述为:对任意
最优化需求目标是一个优化问题, 可以描述为
其中,
文献中不同的自适应目标
Different self-adaptive goals in literature
触发系统自适应能力的原因是动态变化和不确定.能够应对动态变化和不确定, 且保持系统鲁棒性是自适应系统有别于其他软件系统的重要特征[
统计现有工作, 如
文献中不同的动态变化
Different dynamics in literature
文献中不同的不确定性
Different uncertainties in literature
自适应逻辑的实现又称决策方式, 分为反应/前摄式(reactive/proactive)和连续控制式:反应式是在自适应条件发生之后被实施的; 前摄式是在自适应条件发生之前根据模型进行预测而实施的; 连续控制式不涉及显式的自适应触发条件, 而是在整个控制过程中持续地进行调控.反应式和前摄式的概念分别源于控制论中的反馈控制和前馈控制:前馈控制系统是基于补偿原理, 根据系统外部环境的扰动量进行工作; 反馈控制系统是根据被控量和给定值之间的偏差进行工作[
反应/前摄式在编码阶段通常采用ECA范式[
文献中不同的决策方式
Different decision-making methods in literature
被控对象可分为面向服务的信息系统(service oriented information system)、机器人系统(robotic system)和信息物理系统(cyber physical system).不同的被控系统对自适应逻辑有不同的需求, 例如, 机器人系统一般对自适应决策的实时性有较高的要求, 机器人系统和信息物理系统一般对自适应决策的可靠性和风险控制能力有较高的要求.这些非功能性需求需要用不同的机器学习赋能技术来实现.可以利用目标模型(goal model)分析出目标间的关联性, 从而探索什么样的学习机制适宜于什么样的系统[
文献中不同的被控系统
Different controlled systems in literature
不同被控对象背后所涉及的是自适应软件系统的应用场景, 这些场景既有共通之处, 又各有其侧重.下面从自主性、安全性、实时性、动态变化、不确定性等方面对3类被控系统进行考察.
面向服务的信息系统的自主性体现在应用可能发生变化, 用户数量不断增加且其行为模式难以建模, 以及大量并发访问等, 需要系具有资源调整、服务优化等的自我管理能力[
机器人系统对自主性的要求较高, 许多机器人系统都以无人自主系统的形式出现; 同时, 机器人时刻与环境进行交互, 在实时性方面也有较高要求, 需要机器人对环境变化能迅速作出调整[
信息物理系统在自主性、实时性方面的需求同前两种被控系统类似, 但由于其系统内部结构复杂, 对外交互复杂, 兼具信息空间交互、物理空间交互; 系统故障容易对外界产生严重的影响, 使得它在安全性方面较前两种有着更高的要求, 也对机器学习算法在收敛性、稳定性、准确率方面有更高的要求.在信息物理系统中, 学习功能通常由系统所控制的智能体承担, 可以是机器人[
从功能部件视角进行分析, 目前的工作可以分为分离式架构和混合式架构:分离式架构指作为控制者的自适应逻辑独立于作为被控对象的应用逻辑的框架, 有Rainbow[
分离式和混合式框架都将自适应过程分为4个阶段:监测、分析、规划和执行.其中, 监测过程和执行过程在第4.2节已有详述.分析过程是自适应系统的核心, 涉及5个子任务, 包括
● 实现
● 实现
● 预测任务
统计现有的工作, 机器学习可以应用于功能部件层的多个过程, 结果如
文献中不同的应用机器学习的自适应过程
Different self-adaptive processes using machine learning in literature
除了这3个视角上的工作, 验证评价, 即“Verification & Validation”过程, 也是一个重要问题.主要手段有理论证明、案例研究(case study)、模拟仿真(simulation).目前, 理论分析的工作很少, 大部分采用后两种方法:案例研究指搭建特定场景的实验系统, 并进行实验评估; 模拟仿真则借助于仿真工具对自适应算法进行评估.统计现有工作, 结果如
文献中不同的验证评价
Different verification & validation in literature
http://rubis.ow2.org/)是一种Web服务领域的功能测试平台[
综上所述, 软件系统自适应性主要有如下3个关注点.
● 场景不确定.
这个不确定性贯穿于需求时、设计时和运行时, 任务
● 环境动态变化.
任务
● 效果不确定.
理想情况是, 所有自适应操作都能达到预期的效果.但实际效果常常不确定, 并可能和预期效果不一致, 这也是系统需要进行动态调整的原因.任务
针对上述3个关注点, 现有的机器学习赋能技术分为两类:端到端的方法和阶段/过程的方法.端到端方法(如
自适应软件端到端的学习方法
End-to-end learning method for self-adaptive software
理想的系统的外部特性为(
端到端方法中采用的算法为神经网络/深度学习、强化学习等.其中, 用强化学习来实现端到端的自适应逻辑设计比较直接, 通常是将强化学习中的智能体、环境、动作、状态、奖励同自适应中的自适应软件、环境、自适应操作、环境状态、效用一一对应起来, 可以用
强化学习的智能体-环境交互与自适应软件系统的系统-环境交互
Agent-environment interaction in reinforcement learning and the system-environment interaction in self-adaptive software system
阶段/过程的方法是将机器学习算法应用于软件自适应的不同过程(监控、分析、规划、执行), 在不同的阶段设计.按照任务的不同, 可以分为策略生成、策略演化、参数估计、效果预测、环境预测.
● 策略生成是静态的, 根据离线准备的数据得到运行时策略, 通常要求系统在设计时已经很清楚运行时的系统、环境的状态信息[
● 策略演化是在运行时随着系统或环境的变化而发生的策略改变, 即机器学习中的“在线学习”(on-line learning).为了提高系统初始化性能, 一般不直接让系统在没有任何先验知识的情况下从头学起, 通常会配合离线的策略生成或者利用领域知识得到初始自适应策略[
● 参数估计主要解决场景的不确定性, 对系统、环境的不确定用概率或者模糊逻辑的方法进行参数化, 从而得到一个可以评估的指标[
● 效果预测建立自适应操作到系统或环境的实际反应的映射.在系统的组件选择[
● 环境预测分为两种:一种是直接处理原始监测内容的“生数据”, 根据历史数据和当前数据, 预测将来的数据[
这5种方法可以在一个系统中同时部署.如
文献中不同的学习方法
Different learning methods in literature
文献中不同的阶段/过程方法
Different phase/process methods in literature
从软件自适应到机器学习赋能技术
From software self-adaptation to machine learning enabled techniques
从统计结果可以发现, 从自适应需求的3个子目标到6种自适应任务, 再到机器学习算法, 有其天然的对应关系.结合第3.2节的分类, 本文就软件自适应和机器学习赋能技术之间的关系做进一步的分析.就系统自适应性而言, 如果设计者对系统的知识是完备(complete)的, 那么可以通过排队模型、时间自动机模型、马尔可夫决策模型进行建模分析, 给出有效的自适应策略.若在完备的模型上求解自适应策略的计算复杂性高, 则会考虑一些启发式算法[
但是, 如果设计者对于系统的知识是不完备的(不完备可能来自于很多方面, 如设计者缺乏专家知识、系统难以精确建模、很多关键变量无法获得等), 则需引入学习机制.一般而言, 引入机器学习技术, 可以实现在不完备知识的情况下, 通过学习机制来赋予软件系统自适应能力, 即让系统通过对运行数据的自动分析, 提炼出自适应策略.从不同自适应需求目标的特性来看, 不同需求目标所对应的问题域不尽相同, 在不同的问题域上, 采用的机器学习技术也不同.通常, 场景不确定性蕴含的主要是存在隐变量的问题, 对于隐变量, 或是利用EM算法从系统的运行数据中学习得到, 或是利用贝叶斯方法给系统提供一种在含有不确定性情况下的决策机制[
本节在前文分析的基础上, 总结机器学习赋能的软件自适应性所存在的问题, 并对未来研究进行展望.本节回答研究问题RQ3.
过去10余年, 研究者将机器学习的方法应用于自适应软件系统, 提出了学习赋能的系统自适应机制及其算法和框架.但现有及其学习赋能的系统自适应性研究还存在以下主要问题.
● 缺乏对系统自适应性任务的提炼
正确应用机器学习的工具, 需要充分了解机器学习算法和模型的基本假设及其适用场景, 并了解软件自适应性的关注点和目标.例如, 强化学习往往适宜于效用明确的场景, 而在处理多目标问题上有所限制[
● 机器学习算法能力的不足
体现在两个方面:第一, 目前应用于自适应的机器学习算法, 大多着重于满足自适应软件的功能性需求, 实现具体的功能指标, 并没有考虑到自适应任务在系统可靠性、可用性、稳定性、安全性等非功能需求, 尤其在安全攸关的场景, 缺乏对采用机器学习的自适应系统的验证和测试; 第二, 采用机器学习算法有时会给自适应软件系统带来了一些负面效果, 包括:缺乏有效的训练数据, 从而影响机器学习模型的效果.包括:(1)端到端方法、环境预测、效果预测等方法将软件系统视为黑盒, 缺乏对系统内部的分析, 来自软件工程领域不熟悉机器学习算法的普通开发者很难对这类系统进行开发、分析、验证; (2)存在“在线-离线鸿沟”, 机器学习的模型选择很大程度依赖于设计者对数据分布的先验知识或基本假设, 而由于这些先验知识或基本假设在实际情况中可能并不成立, 因此在离线阶段设计、训练出的机器学习模型可能不适合在线的实际情况; (3)存在在线算法的缺陷, 机器学习算法本身具有不确定性(例如强化学习的
● 缺乏在机器学习赋能思想上的自适应系统框架
目前, 绝大多数研究工作, 其基本思想只是从软件自适应任务中找特定的问题, 把机器学习作为解决问题的工具, 机器学习思想没有对自适应软件系统的框架体系带来影响, 软件系统的自适应需求也没有引起机器学习技术的新的发展方向.缺乏从机器学习的角度分析, 是否应当把考虑学习能力作为自适应系统的一个需求目标、怎样赋予自适应系统学习的能力等问题.参考基于控制论的软件自适应性, 可以发现机器学习并没有影响或改变自适应软件系统本身的架构, 软件自适应性的研究并没有将机器学习中“通过经验来提升性能”的核心思想囊括在内, 仅仅是把自适应作为机器学习算法的背景问题, 把机器学习算法作为自适应的工具是远远不够的, 需要建立成熟的机器学习赋能的自适应软件系统的体系架构, 以及促进面向软件系统自适应性的在线学习技术的发展.
● 缺乏机器学习赋能的自适应软件系统开发方法学
现有的工作大都是“就事论事”的研究方法, 缺乏系统化的软件设计方法学, 缺少对系统的很多关键非功能需求的可满足性研究, 因而目前基本都仅仅在实验环境下的研究, 并没有真正应用到实践中.理想的从软件自适应问题到机器学习的过程应在系统的方法论的指导下, 建立起从软件自适应问题到学习任务的映射, 再根据提炼出的约束条件, 得到对于“在某种约束条件下, 进行某种学习任务”的最合适的机器学习赋能机制.
基于上述的分析总结, 学习赋能的系统自适应性的研究下一步急需的研究应侧重在如下几个方面.
● 更加适合系统自适应性的机器学习算法设计
基于现有的自适应任务, 改进或提出新的机器学习算法, 以更好地满足自适应任务的需求.机器学习的应用给软件自适应带来好处的同时也带来了诸多副作用, 因此, 要结合具体应用场景, 对机器学习算法进行改造, 使之更加适应于软件自适应的具体应用需求.有价值的研究问题包括:解决强化学习算法在线学习时, 探索策略空间的无效率的问题(学习效率、容易进入危险状态、没有利用已有的先验知识等); 提高机器学习算法鲁棒性, 使得系统中采用了学习算法的部分具有更高的可靠性; 提高学习算法的样本利用效率, 使得在缺乏数据的软件自适应场景下, 学习算法也能被很好地应用.
● 软件系统自适应性对机器学习的能力需求分析
基于现有的自适应软件系统体系结构, 对软件自适应性需求的本质进行更详细准确的分类和特性提炼, 进而更好地定位软件自适应亟待解决的具体问题, 从而更精准地将自适应问题映射为现有机器学习方法能解决的问题.软件自适应和机器学习领域存在知识和术语的鸿沟, 科学的自适应需求分析为两个领域搭建起桥梁, 有助于不熟悉机器学习方法的软件开发者使用机器学习方法解决自适应问题, 也有助于机器学习研究者改进机器学习算法, 以更好地满足自适应需求.
● 融合机器学习能力的自适应系统体系结构
随着自适应系统应用面的不断推广, 赋予软件系统“学习能力”使之能够充分应对复杂多变的环境, 根据运行时的经验, 自动地改进系统功能, 提升系统性能, 这将成为一大趋势.引入机器学习方法后, 需要一个新的自适应系统体系结构.需要回答包括如下问题:学习和自适应性的关系是什么?学习能力的具体需求是什么?需要在现有的体系结构下增加学习模块/层次吗?需要以机器学习为中心扩展出新的体系结构吗?学习模块内部应该如何设计?学习模块外部接口是什么?机器学习和其他层次或功能模块如何交互?等等一系列富有挑战性的问题.如同基于控制论的系统自适应提供了各种源自于标准控制系统的体系结构一样, 基于机器学习的系统自适应也应当推出带有学习特性的新的系统体系结构.
软件系统自适应性是当前软件领域的热点话题.本文综述现有的机器学习赋能的软件系统自适应的相关工作.围绕3个研究问题, 分别从自适应系统的角度和机器学习的角度对相关工作进行分类, 基于分类框架, 发掘从系统自适应性到机器学习问题求解的流程, 梳理二者的对应关系.最后, 在此基础上提出不足与展望.
De Lemos R, Giese H, Müller HA, et al. Software engineering for self-adaptive systems: A second research roadmap. In: Proc. of the Software Engineering for Self-adaptive Systems Ⅱ. Berlin, Heidelberg: Springer-Verlag, 2013. 1-32.
Yang QL, Ma XX, Xing JC, et al. Software self-adaptation:Control theory based approach. Chinese Journal of Computers, 2016, 39(11):2189-2215(in Chinese with English abstract).
杨启亮, 马晓星, 邢建春, 胡昊, 王平, 韩德帅.软件自适应:基于控制理论的方法.计算机学报, 2016, 39(11):2189-2215.
Patikirikorala T, Colman A, Han J, et al. A systematic survey on the design of self-adaptive software systems using control engineering approaches. In: Proc. of the 7th Int'l Symp. on Software Engineering for Adaptive and Self-managing Systems. IEEE, 2012. 33-42.
Salehie M, Tahvildari L. Self-adaptive software: Landscape and research challenges. ACM Trans. on Autonomous and Adaptive Systems, 2009, 4(2): Article No.14.
Shen J, Wang Q, Mei H. Self-adaptive software: Cybernetic perspective and an application server supported framework. In: Proc. of the Computer Software and Applications Conf. IEEE Computer Society, 2004. 92-95.
Silva Souza VE, Lapouchnian A, Robinson WN, et al. Awareness requirements for adaptive systems. In: Proc. of the 6th Int'l Symp. on Software Engineering for Adaptive and Self-managing Systems. Waikiki: ACM, 2011. 60-69.
Karlsson M, Karamanolis C, Zhu X. Triage:Performance differentiation for storage systems using adaptive control. ACM Trans. on Storage, 2005, 1(4):457-480.
Hu H, Jiang CH, Cai KY. Adaptive software testing in the context of an improved controlled Markov chain model. In: Proc. of the 32nd Annual IEEE Int'l Computer Software and Applications Conf. IEEE, 2008. 853-858.
Liu X, Zhu X, Padala P, et al. Optimal multivariate control for differentiated services on a shared hosting platform. In: Proc. of the 46th IEEE Conf. on Decision and Control. IEEE, 2007. 3792-3799.
Litoiu M, Woodside M, Zheng T. Hierarchical model-based autonomic control of software systems. ACM SIGSOFT Software Engineering Notes, 2005, 30(4):1-7.
Weyns D, Malek S, Andersson J. FORMS: A formal reference model for self-adaptation. In: Proc. of the 7th Int'l Conf. on Autonomic Computing. Washington: ACM, 2010. 205-214.
Zhang J, Cheng BHC. Model-based development of dynamically adaptive software. In:Proc. of the 28th Int'l Conf. on Software Engineering. Shanghai:ACM, 2006. 371-380.
Liu C, Jiang C, Hu H, et al. A control-based approach to balance services performance and security for adaptive service based systems (ASBS). In: Proc. of the 33rd Annual IEEE Int'l Computer Software and Applications Conf., Vol.2. IEEE, 2009. 473-478.
Brun Y, Serugendo GD, Gacek C, et al. Engineering self-adaptive systems through feedback loops. In: Proc. of Software Engineering for Self-adaptive Systems. Berlin, Heidelberg: Springer-Verlag, 2009. 48-70.
Kephart JO, Chess DM. The vision of autonomic computing. IEEE Computer, 2003, 36(1):41-50.
Garlan D, Cheng SW, Huang AC, Schmerl B, Steenkiste P. Rainbow:Architecture-based self-adaptation with reusable infrastructure. IEEE Computer, 2004, 37(10):46-54.
Müller H, Pezzè M, Shaw M. Visibility of control in adaptive systems. In: Proc. of the 2nd Int'l Workshop on Ultra-large-scale Software-intensive Systems. Leipzig: ACM, 2008. 23-26.
Elkhodary A, Esfahani N, Malek S. FUSION: A framework for engineering self-tuning self-adaptive software systems. In: Proc. of the 18th ACM SIGSOFT Int'l Symp. on Foundations of Software Engineering. Santa Fe: ACM, 2010. 7-16.
Baah GK, Gray A, Harrold MJ. On-line anomaly detection of deployed software: A statistical machine learning approach. In: Proc. of the 3rd Int'l Workshop on Software Quality Assurance. Portland: ACM, 2006. 70-77.
Rodrigues A, Caldas RD, Rodrigues GN, et al. A learning approach to enhance assurances for real-time self-adaptive systems. In: Proc. of the IEEE/ACM 13th Int'l Symp. on Software Engineering for Adaptive and Self-managing Systems (SEAMS). Gothenburg: IEEE, 2018. 206-216.
Tesauro G. Reinforcement learning in autonomic computing:A manifesto and case studies. IEEE Internet Computing, 2007, 11(1):22-30.
Kim D, Park S. Reinforcement learning-based dynamic adaptation planning method for architecture-based self-managed software. In: Proc. of the ICSE Workshop on Software Engineering for Adaptive and Self-managing Systems. Vancouver: IEEE, 2009. 76-85.
Wang H, Zhou X, Zhou X, et al. Adaptive service composition based on reinforcement learning. In: Proc. of the Int'l Conf. on Service-oriented Computing. Berlin, Heidelberg: Springer-Verlag, 2010. 92-107.
Mitchell T. Machine Learning. New York: McGraw Hill, 1997.
Sutton R, Barto A. Reinforcement Learning: An Introduction. MIT Press, 1998.
Zhao T, Zhang W, Zhao H, et al. A reinforcement learning-based framework for the generation and evolution of adaptation rules. In: Proc. of the IEEE Int'l Conf. on Autonomic Computing (ICAC). Columbus: IEEE, 2017. 103-112.
Schmid S, Gerostathopoulos I, Prehofer C, et al. Self-adaptation based on big data analytics: A model problem and tool. In: Proc. of the IEEE/ACM 12th Int'l Symp. on Software Engineering for Adaptive and Self-managing Systems (SEAMS). IEEE, 2017. 102-108.
Ho HN, Lee E. Model-based reinforcement learning approach for planning in self-adaptive software system. In: Proc. of the 9th Int'l Conf. on Ubiquitous Information Management and Communication. ACM, 2015.
Tesauro G, Jong NK, Das R, et al. A hybrid reinforcement learning approach to autonomic resource allocation. In: Proc. of the IEEE Int'l Conf. on Autonomic Computing. Dublin: IEEE, 2006. 65-73.
Pandey A, Moreno GA, Cámara J, et al. Hybrid planning for decision making in self-adaptive systems. In: Proc. of the IEEE 10th Int'l Conf. on Self-adaptive and Self-organizing Systems (SASO). Augsburg: IEEE, 2016. 130-139.
Lecun Y, Bengio Y, Hinton G. Deep learning. Nature, 2015, 521:436-444.
Esfahani N, Elkhodary A, Malek S. A learning-based framework for engineering feature-oriented self-adaptive software systems. IEEE Trans. on Software Engineering, 2013, 39(11):1467-1493.
Porter B, Rodrigues Filho R. Losing control: The case for emergent software systems using autonomous assembly, perception, and learning. In: Proc. of the IEEE 10th Int'l Conf. on Self-adaptive and Self-organizing Systems (SASO). Augsburg: IEEE, 2016. 40-49.
Bodík P, Griffith R, Sutton CA, et al. Statistical machine learning makes automatic control practical for internet datacenters. In: Proc. of the IEEE Int'l Conf. on Cloud Computing Technology and Science. IEEE, 2009.
Tanabe M, Tei K, Fukazawa Y, et al. Learning environment model at runtime for self-adaptive systems. In: Proc. of the Symp. on Applied Computing. Marrakech: ACM, 2017. 1198-1204.
Han D, Xing J, Yang Q, et al. Handling uncertainty in self-adaptive software using self-learning fuzzy neural network. In: Proc. of the IEEE 40th Annual Computer Software and Applications Conf. (COMPSAC), Vol.2. IEEE, 2016. 540-545.
Borges RV, Garcez AA, Lamb LC, et al. Learning to adapt requirements specifications of evolving systems (NIER track). In: Proc. of the 33rd Int'l Conf. on Software Engineering. Waikiki: ACM, 2011. 856-859.
Verstaevel N, Boes J, Nigon J, et al. Lifelong machine learning with adaptive multi-agent systems. In: Proc. of the Int'l Conf. on Agents & Artificial Intelligence. 2017. 275-286.
Lama P, Zhou X. Autonomic provisioning with self-adaptive neural fuzzy control for percentile-based delay guarantee. ACM Trans. on Autonomous and Adaptive Systems (TAAS), 2013, 8(2): No.9.
Lama P, Zhou X. Autonomic provisioning with self-adaptive neural fuzzy control for end-to-end delay guarantee. In: Proc. of the IEEE Int'l Symp. on Modeling, Analysis and Simulation of Computer and Telecommunication Systems. IEEE, 2010. 151-160.
Mnih V, Kavukcuoglu K, Silver D, et al. Playing atari with deep reinforcement learning. arXiv preprint arXiv: 1312.5602, 2013.
Lillicrap TP, Hunt JJ, Pritzel A, et al. Continuous control with deep reinforcement learning. In: Proc. of the Int'l Conf. on Learning Representations. San Diego, 2016.
Schulman J, Levine S, Abbeel P, et al. Trust region policy optimization. In: Proc. of the Int'l Conf. on Machine Learning. Lille: JMLR, 2015. 1889-1897.
Heckerman D. A Tutorial on Learning with Bayesian Networks. Dordrecht:Springer-Verlag, 1998. 301-354.
Koller D, Friedman N. Probabilistic Graphical Models: Principles and Techniques. MIT Press, 2009.
Wang H, Wu Q, Chen X, et al. Integrating gaussian process with reinforcement learning for adaptive service composition. In: Proc. of the Int'l Conf. on Service-oriented Computing. Berlin, Heidelberg: Springer-Verlag, 2015. 203-217.
Wang H, Wu Q, Chen X, et al. Adaptive and dynamic service composition via multi-agent reinforcement learning. In: Proc. of the IEEE Int'l Conf. on Web Services. IEEE, 2014. 447-454.
Moreno GA, Cámara J, Garlan D, et al. Efficient decision-making under uncertainty for proactive self-adaptation. In: Proc. of the IEEE Int'l Conf. on Autonomic Computing (ICAC). IEEE, 2016. 147-156.
Fürnkranz J, Gamberger D, Lavrač N. Foundations of Rule Learning. Springer Science & Business Media, 2012.
Alrajeh D, Kramer J, Russo A, et al. Learning operational requirements from goal models. In: Proc. of the 31st Int'l Conf. on Software Engineering. IEEE Computer Society, 2009. 265-275.
Ray O. Using abduction for induction of normal logic programs. In: Proc. of the 2nd Workshop on AIAI and Scientific Modelling. 2006. 28-31.
Muggleton SH, Bryant CH. Theory completion using inverse entailment. In: Proc. of the Int'l Conf. on Inductive Logic Programming. Berlin, Heidelberg: Springer-Verlag, 2000. 130-146.
Esposito F, Semeraro G, Fanizzi N, Ferilli S. Multistrategy theory revision:Induction and abduction in INTHELEX. Machine Learning, 2000, 38(1-2):133-156.
Pan SJ, Yang Q. A survey on transfer learning. IEEE Trans. on Knowledge and Data Engineering, 2009, 22(10):1345-1359.
Jamshidi P, Velez M, Kästner C, et al. Transfer learning for improving model predictions in highly configurable software. In: Proc. of the 12th Int'l Symp. on Software Engineering for Adaptive and Self-managing Systems. Buenos Aires: IEEE, 2017. 31-41.
Jamshidi P, Siegmund N, Velez M, et al. Transfer learning for performance modeling of configurable systems: An exploratory analysis. In: Proc. of the 32nd IEEE/ACM Int'l Conf. on Automated Software Engineering. Urbana: IEEE, 2017. 497-508.
Kitchenham B. Procedures for Performing Systematic Reviews. Keele: Keele University, 2004. 1-26.
Guivarch V, Camps V, Péninou A. AMADEUS:An adaptive multi-agent system to learn a user's recurring actions in ambient systems. ADCAIJ:Advances in Distributed Computing and Artificial Intelligence Journal, 2013, 1(3):1-10.
Liu Q, Sun Y, Zhang S. A scalable Web service composition based on a strategy reused reinforcement learning approach. In: Proc. of the 8th Web Information Systems and Applications Conf. IEEE, 2011. 58-62.
Nigon J, Gleizes MP, Migeon F. Self-adaptive model generation for ambient systems. In: Proc. of the 7th Int'l Conf. on Ambient Systems, Networks and Technologies (ANT). Elsevier, 2016. 675-679.
Ramirez AJ, Jensen AC, Cheng BHC. A taxonomy of uncertainty for dynamically adaptive systems. In: Proc. of the 7th Int'l Symp. on Software Engineering for Adaptive and Self-managing Systems. Zurich: IEEE, 2012. 99-108.
Gu X. IDES: Self-adaptive software with online policy evolution extended from rainbow. In: Proc. of the Computer and Information Science 2012. Berlin, Heidelberg: Springer-Verlag, 2012. 181-195.
Lobo J, Bhatia R, Naqvi S. A policy description language. In: Proc. of the National Conf. on Artificial Intelligence. AAAI, 1999. 291-298.
Fleurey F, Dehlen V, Bencomo N, et al. Modeling and validating dynamic adaptation. In: Proc. of the Int'l Conf. on Model Driven Engineering Languages and Systems. Berlin, Heidelberg: Springer-Verlag, 2008. 97-108.
Hu SS. Principles of Automatic Control. 6th ed., Beijing:Science Press, 2013(in Chinese).
胡寿松.自动控制原理.第6版, 北京:科学出版社, 2013.
Mahfoudh HB, Serugendo GDM, Boulmier A, et al. Coordination model with reinforcement learning for ensuring reliable on-demand services in collective adaptive systems. In: Proc. of the Int'l Symp. on Leveraging Applications of Formal Methods. Cham: Springer-Verlag, 2018. 257-273.
Knauss A, Damian D, Franch X, et al. ACon:A learning-based approach to deal with uncertainty in contextual requirements at runtime. Information and Software Technology, 2016, 70:85-99.
Zavala E, Franch X, Marco J, et al. SACRE:Supporting contextual requirements' adaptation in modern self-adaptive systems in the presence of uncertainty at runtime. Expert Systems with Applications, 2018, 98:166-188.
Paucar LHG, Bencomo N. RE-STORM: Mapping the decision-making problem and non-functional requirements trade-off to partially observable Markov decision processes. In: Proc. of the 13th Int'l Conf. on Software Engineering for Adaptive and Self-managing Systems. Gothenburg: ACM, 2018. 19-25.
Bencomo N, Belaggoun A, Issarny V. Dynamic decision networks for decision-making in self-adaptive systems: A case study. In: Proc. of the 8th Int'l Symp. on Software Engineering for Adaptive and Self-managing Systems. San Francisco: IEEE, 2013. 113-122.
Bahati RM, Bauer MA. Towards adaptive policy-based management. In: Proc. of the IEEE Network Operations and Management Symp. (NOMS). IEEE, 2010. 511-518.
Sykes D, Corapi D, Magee J, et al. Learning revised models for planning in adaptive systems. In: Proc. of the 35th Int'l Conf. on Software Engineering (ICSE). San Francisco: IEEE, 2013. 63-71.
Zhao T. The generation and evolution of adaptation rules in requirements driven self-adaptive systems. In: Proc. of the IEEE 24th Int'l Requirements Engineering Conf. (RE). Beijing: IEEE, 2016. 456-461.
Ganguly KK, Sakib K. A reusable adaptation component design for learning-based self-adaptive systems. In: Proc. of the 12th Int'l Conf. on Software Engineering Advances (ICSEA). Tahiti: IEEE, 2017. 244-249.
Epifani I, Ghezzi C, Mirandola R, et al. Model evolution by run-time parameter adaptation. In: Proc. of the 31st Int'l Conf. on Software Engineering. Vancouver: IEEE Computer Society, 2009. 111-121.
Braberman V, D'Ippolito N, Kramer J, et al. Morph: A reference architecture for configuration and behaviour self-adaptation In: Proc. of the 1st Int'l Workshop on Control Theory for Software Engineering. Bergamo: ACM, 2015. 9-16.
Ghahremani S, Adriano CM, Giese H. Training prediction models for rule-based self-adaptive systems. In: Proc. of the IEEE Int'l Conf. on Autonomic Computing (ICAC). IEEE, 2018. 187-192.
Rook A, Knauss A, Damian D, et al. A case study of applying data mining to sensor data for contextual requirements analysis. In: Proc. of the IEEE 1st Int'l Workshop on Artificial Intelligence for Requirements Engineering (AIRE). Karlskrona: IEEE, 2014. 43-50.
Huber N, Walter J, Bähr M, et al. Model-based autonomic and performance-aware system adaptation in heterogeneous resource environments: A case study. In: Proc. of the Int'l Conf. on Cloud and Autonomic Computing. IEEE, 2015. 181-191.
Filieri A, Grunske L, Leva A. Lightweight adaptive filtering for efficient learning and updating of probabilistic models. In: Proc. of the 37th Int'l Conf. on Software Engineering. Florence: IEEE, 2015. 200-211.
Jamshidi P, Sharifloo A, Pahl C, et al. Fuzzy self-learning controllers for elasticity management in dynamic cloud architectures. In: Proc. of the 12th Int'l ACM SIGSOFT Conf. on Quality of Software Architectures (QoSA). IEEE, 2016. 70-79.
Magableh B. A deep recurrent Q network towards self-adapting distributed microservices architecture. arXiv preprint arXiv: 1901. 04011, 2019.
Jamshidi P, Sharifloo AM, Pahl C, et al. Self-learning cloud controllers: Fuzzy q-learning for knowledge evolution. In: Proc. of the Int'l Conf. on Cloud and Autonomic Computing. IEEE, 2015. 208-211.
Sutton RS. Temporal credit assignment in reinforcement learning[Ph.D. Thesis]. Amherst: University of Massachusetts, 1984.
Canavera KR, Esfahani N, Malek S. Mining the execution history of a software system to infer the best time for its adaptation. In: Proc. of the ACM SIGSOFT 20th Int'l Symp. on the Foundations of Software Engineering. Cary: ACM, 2012.
Sharifloo AM, Metzger A. Mcaas: Model checking in the cloud for assurances of adaptive systems. In: Proc. of the Software Engineering for Self-adaptive Systems Ⅲ. Cham: Springer-Verlag, 2017. 137-153.
Bowling M, Veloso M. Multiagent learning using a variable learning rate. Artificial Intelligence, 2002, 136(2):215-250.
Wang H, Chen X, Wu Q, et al. Integrating on-policy reinforcement learning with multi-agent techniques for adaptive service composition. In: Proc. of the Int'l Conf. on Service-oriented Computing. Berlin, Heidelberg: Springer-Verlag, 2014. 154-168.
Braberman V, D'Ippolito N, Kramer J, et al. An extended description of MORPH: A reference architecture for configuration and behaviour self-adaptation. In: Proc. of the Software Engineering for Self-adaptive Systems Ⅲ. Cham: Springer-Verlag, 2017. 377-408.
Rodrigues A, Rodrigues GN, Knauss A, et al. Enhancing context specifications for dependable adaptive systems:A data mining approach. Information and Software Technology, 2019, 112:115-131.
Shoham Y, Leyton-Brown K. Multiagent Systems:Algorithmic, Game-theoretic, and Logical Foundations. London:Cambridge University Press, 2008.
Baresi L, Pasquale L. Adaptive goals for self-adaptive service compositions. In: Proc. of the IEEE Int'l Conf. on Web Services. IEEE, 2010. 353-360.
Bencomo N, Belaggoun A. Supporting decision-making for self-adaptive systems: From goal models to dynamic decision networks. In: Proc. of the Int'l Working Conf. on Requirements Engineering: Foundation for Software Quality. Berlin: Springer-Verlag, 2013. 221-236.
Zhao T, Zan T, Zhao H, et al. Integrating goal model into rule-based adaptation. In: Proc. of the 23rd Asia-Pacific Software Engineering Conf. (APSEC). IEEE, 2016. 289-296.
Berral JL, Gavalda R, Torres J. Adaptive scheduling on power-aware managed data-centers using machine learning. In: Proc. of the 2011 IEEE/ACM 12th Int'l Conf. on Grid Computing. IEEE Computer Society, 2011. 66-73.
Ding Z, Zhou Y, Zhou MC. Modeling self-adaptive software systems with learning Petri nets. IEEE Trans. on Systems, Man, and Cybernetics:Systems, 2015, 46(4):483-498.
Moustafa A, Zhang M. Multi-objective service composition using reinforcement learning. In: Proc. of the Int'l Conf. on Service-oriented Computing. Berlin, Heidelberg: Springer-Verlag, 2013. 298-312.
Richert W, Kleinjohann B. Adaptivity at every layer: A modular approach for evolving societies of learning autonomous systems. In: Proc. of the ICSE Workshop on Software Engineering for Adaptive and Self-managing Systems (SEAMS). ACM, 2008. 113-120.
Rudolph S, Tomforde S, Sick B, Hähner J. A mutual influence detection algorithm for systems with local performance measurement. In: Proc. of the IEEE 9th Int'l Conf. on Self-adaptive and Self-organizing Systems. IEEE, 2015. 144-149.
Petruzzi PE, Pitt J, Busquets D. Inter-institutional social capital for self-organising 'nested enterprises'. In: Proc. of the 10th IEEE Int'l Conf. on Self-adaptive and Self-organizing Systems (SASO). Augsburg: IEEE, 2016. 90-99.
D'Angelo M, Gerasimou S, Ghahremani S, Grohmann J, Nunes I, Pournaras E, Tomforde S. On learning in collective self-adaptive systems: State of practice and a 3D framework. In: Proc. of the IEEE/ACM 14th Int'l Symp. on Software Engineering for Adaptive and Self-managing Systems (SEAMS). Montreal: IEEE, 2019. 13-24.
Cecchet E, Marguerite J, Zwaenepoel W, et al. Performance and scalability of EJB applications. In: Proc. of 17th Conf. on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA). ACM, 2002. 246-261.
Chen T, Bahsoon R. Self-adaptive and online QoS modeling for cloud-based software services. IEEE Trans. on Software Engineering, 2016, 43(5):453-475.
Kitano H, Asada M, Kuniyoshi Y, et al. RoboCup: A challenge problem for AI and robotics. In: Proc. of the Robot Soccer World Cup. 1998. 1-19.
Quigley M, Gerkey B, Conley K, et al. ROS: An open-source robot operating system. In: Proc. of the Int'l Conf. on Robotics and Automation Workshop Open Source Software. 2009. 1-6.
Klös V, Göthel T, Glesner S. Comprehensible and dependable self-learning self-adaptive systems. Journal of Systems Architecture, 2018, 85:28-42.
Ismail A, Cardellini V. Decentralized planning for self-adaptation in multi-cloud environment. In: Proc. of the European Conf. on Service-oriented and Cloud Computing. Cham: Springer-Verlag, 2014. 76-90.
Amoui M, Salehie M, Mirarab S, et al. Adaptive action selection in autonomic software using reinforcement learning. In: Proc. of the 4th Int'l Conf. on Autonomic and Autonomous Systems (ICAS). IEEE, 2008. 175-181.
Calinescu R, Rafiq Y, Johnson K, et al. Adaptive model learning for continual verification of non-functional properties. In: Proc. of the 5th ACM/SPEC Int'l Conf. on Performance Engineering. New York: ACM, 2014. 87-98.
Yan Y, Zhang B, Guo J. An adaptive decision making approach based on reinforcement learning for self-managed cloud applications. In: Proc. of the IEEE Int'l Conf. on Web Services (ICWS). IEEE, 2016. 720-723.
Dowling J, Cahill V. Self-managed decentralised systems using K-components and collaborative reinforcement learning. In: Proc. of the 1st ACM SIGSOFT Workshop on Self-managed Systems. Newport Beach: ACM, 2004. 39-43.
Porter B, Grieves M, Rodrigues Filho R, et al. REX: A development platform and online learning approach for runtime emergent software systems. In: Proc. of the 12th USENIX Symp. on Operating Systems Design and Implementation (OSDI). USENIX, 2016. 333-348.
Bahati RM, Bauer MA. Reinforcement learning in policy-driven autonomic management. In: Proc. of the IEEE Network Operations and Management Symp. (NOMS). IEEE, 2008. 899-902.
Tesauro G. Online resource allocation using decompositional reinforcement learning. In: Proc. of the AAAI Conf. on Artificial Intelligence (AAAI), Vol.5. AAAI, 2005. 886-891.
Boes J, Migeon F, Glize P, et al. Model-free optimization of an engine control unit thanks to self-adaptive multi-agent systems. In: Proc. of the Enbedded Real Time Software and Systems. 2014.
Boes J, Nigon J, Verstaevel N, et al. The self-adaptive context learning pattern: Overview and proposal. In: Proc. of the Int'l and Interdisciplinary Conf. on Modeling and Using Context. Cham: Springer-Verlag, 2015. 91-104.
Dezfuli ZT, Nazemi E, Ziari M. An algorithm for online planning to improve availability and performance of self-adaptive websites. In: Proc. of the 5th Iranian Joint Congress on Fuzzy and Intelligent Systems (CFIS). IEEE, 2017. 213-218.
Klös V, Göthel T, Glesner S. Be prepared: Learning environment profiles for proactive rule-based production planning. In: Proc. of the 44th Euromicro Conf. on Software Engineering and Advanced Applications (SEAA). IEEE, 2018. 89-96.
Rao J, Bu X, Xu CZ, et al. A distributed self-learning approach for elastic provisioning of virtualized cloud resources. In: Proc. of the 19th Annual Int'l Symp. on Modelling, Analysis, and Simulation of Computer and Telecommunication Systems. IEEE, 2011. 45-54.
Gil R. Automated planning for self-adaptive systems. In: Proc. of the IEEE/ACM 37th IEEE Int'l Conf. on Software Engineering (ICSE). ACM, 2015. 839-842.
Krupitzer C, Pfannemüller M, Kaddour J, et al. SATISFy: Towards a self-learning analyzer for time series forecasting in self-improving systems. In: Proc. of the IEEE 3rd Int'l Workshops on Foundations and Applications of Self* Systems (FAS* W). IEEE, 2018. 182-189.
Leitner P, Hummer W, Dustdar S. Cost-based optimization of service compositions. IEEE Trans. on Services Computing, 2011, 6(2):239-251.
Barrett E, Howley E, Duggan J. Applying reinforcement learning towards automating resource allocation and application scalability in the cloud. Concurrency and Computation:Practice and Experience, 2013, 25(12):1656-1674.