网络软件动态演化的元胞自动机模型研究

摘要: 通过分析网络软件的动态演化,提出将元胞自动机理论引入到网络软件演化过程的模拟中,建立元胞模型来预防和监控演化趋势。并针对服务构件替换和连接件替换,提出一系列算法和规则。研究结果表明该模型能较好地模拟网络软件演化现象,对于web形式的服务监控、替换以及维护重要服务等工作具有指导意义。

关键词:元胞自动机;网络软件;动态演化;web服务;服务监控

中图分类号:TP311文献标识码:A文章编号:1009-3044(2010)05-1090-03

Study on Network Software's Dynamic Evolution Based on Cellular Automata

WU Yan1, GAO Hong-hao2

(1.College of Information Technology, Zhejiang Chinese Medical University, Hangzhou 310053, China;2.College of Computer Engineering and Science, Shanghai University, Shanghai 200072, China)

Abstract: Based on the analysis of dynamic evolution of Network Software, this paper elaborates on the application of the theory of cellular automata into the simulation of the evolution of Network Software, as well as on the prevention and monitoring of the evolution of Network Software by establishing cellular models. A series of algorithms and rules about replacement of Network Software's component and connectors are proposed. The results show that the model can well simulate the evolution of Network software, it is essential to web service monitoring, replacement and maintenance, just to name a few.

Key words: cellular automata; network software; dynamic evolution; web services; service monitoring

面向服务的可计算资源(Service-Oriented Computing Resource, SOCR)组合而成的“网络计算机”成为下一代分布式计算和软件开发的研究热点,其将分布在不同网络节点的构件有机地组成一个全新的复杂软件系统。使得开发、部署、运行和维护的环境开始从封闭、静态、可控逐步走向开放、动态、难控,面临问题域和解空间的不停变迁,尤其是运行时周围环境和构件内部的突发和紧急的事件,网络软件系统需进行整体或局部的动态演化。

1 网络软件演化问题

网络技术的迅猛发展,出现了如网格、普适计算、P2P等以网络为载体的新技术,在这种开放、动态、多变的新一代软件运行环境下,要求软件逐步向跨网络的互联、互通、协同和联盟来构建应用集成,即实现从信息Web到Software Web的跨越,并能够根据网络环境的变化和业务需求动态适应的新型应用图景;特别是服务计算技术的兴起与不断应用,软件系统开始呈现出一种柔性可演化、连续反应式、多目标适应的新系统形态---网络软件(Network Software) [1]。

传统的软件开发流程基于自顶向下的方式,即程序员先选择问题场景,接着对其问题进行分解,实施分而治之的策略,使整个系统开发过程处于有序控制之下。而网络软件在开放、动态、多变的网络环境平台下,其无统一控制的“真”分布性,节点的高度自治性,节点链接的开放性和动态性等特征,其开发过程是将这些丰富的基础软件资源从“无序”状态组合成为“有序”的软件系统;随着网络环境的变迁和时间的推移,这些系统和资源在功能、非功能性、数量、质量上的变化导致它们再次呈现出“无序”的状态。因此,这种由“无序”到“有序”的变迁过程循环往复的自组织形式,呈现出一种自底向上、由内向外的螺旋方式的动态变迁演化。

动态演化作为网络软件的基本特性,其研究重点是如何预测其发生故障和演化的趋势,发掘至关重要的和需监控并维护的失效构件,以及对安全的可替换的备份构件的识别等问题日益重要和急迫,尤其是为生命攸关(Life-Security)的软件提供保障,确保软件的可靠性等研究备受关注。

2 相关研究

目前软件动态演化的研究从不同粒度和层次出发提出了各自相应的动态演化方法和技术,其中围绕软件体系结构的研究成果有:文献[1-3]提出的基于软件体系结构SA的研究和实践,从系统的结构和交互行为角度,展示在运行期间进行网络构件的删除、添加、替换、迁移,连接件的建立、删除、重定向,以及构件属性设置等演化过程。文献[4-6]提出的 演算、构件运算、接口模型等形式化方法描述软件的约束和验证功能性一致性,行为一致性研究动态演化。文献[7-8]结合J2EE 规范的构件运行支撑平台为例讨论了该方案的实现.借助JAVA 平台的反射技术的类装载机制,实现了以构件为粒度的软件演化。文献[9]使用了一种利于约束检查和属性刻画的属性图文法,对属性图文法系统AGG的图形解析器进行定制和改进的基础上,设计并实现了体系结构自动检查器。文献[10-11]中实现了一个基于深度优先算法的体系结构检查器Armani原型系统,以及Wright、Darwin等方法。

元胞自动机(Cellular Automaton,简称CA)最早是由Ulam和Von Neumann在20 世纪40年代提出的。此后被广泛应用于社会、经济、军事和科学研究的各个领域。CA将散布在规则格网 (Lattice Grid)中的网格点称为元胞(cell),每一元胞(Cell)取有限的离散状态,在遵循同样的作用规则下,依据确定的局部规则作同步更新。大量元胞通过简单的相互作用而构成动态系统的演化。S. Wolfrarm将其动力学行为归为四大类:变换到空间平稳构形;变换到简单的周期结构;变换到混沌型;变换到复杂的局部结构。总之,CA在空间、时间、状态都是离散,演化的运算规则是局部关联的特性,以及变换趋势的四种类型十分符合研究和模拟网络软件的动态演化过程的要求。

3 网络软件模型

发生动态演化时的网络软件情况可能由于某一构件节点由于自身需求的变更或升级,前驱构件的失效等周围环境因素,如功能性业务流程迁移或服务机器故障发生而引起的对当前构件强制性变化的需求。需要研究以下情形:1) 根据构件语义相似度进行计算判别可替换构件,2) 前驱构件的变迁,可能导致已有的约束条件不再适用,需在空间上进行整体的体系结构的调整,3) 也有可能始终没有找到一个合适的可操作的情况(替换、删除、增加等操作),整个系统需要人工干预。

网络软件的本质是通过接口进行关联,针对接口Port的名字、参数类型、返回值类型进行匹配调用以处理服务请求和响应;使用连接件Link方式封装调用返回和消息驱动方式的将服务构件调用者和被调用者进行连接。基于此,本文提出一种基于元胞自动机理论来研究和模拟网络软件在发生异常时的状态变迁过程。研究的内容包括:基于元胞自动机研究网络软件的自动调节能力,通过监控构件的行为和状态,实现动态演化过程的动态演化平台,即模拟不停机条件下,感知和自动化处理外部环境和需求的变化内容,在自适应机制支持下由系统正确性约束和动态演化策略,实施状态变迁。

3.1 网络构件替换方法及模拟

首先,提出网络构件模型的四元组表示< id,S,L,∮>,其中1) id表示标识符;2) S代表构件的集合,S=;3) L描述连接件的集合,L=; 4) ∮映射函数S × SL表明两个构件与连接件之间的映射关系。

处理异常网络构件方法是替换新的构件,利于网络构件在本体中的映射描述,领域本体模型是网络构件进行组织和维护的基础,计算其领域模型上的语义相似值可用于替换概率。领域本体在抽象上一树状结构,每个节点或叶子代表着某一个领域分类信息,其实例则代表着网络软件,是一对多的关系,如文献[12]提出了如下公式来计算两个实例C1与C2之间的相似度:

该方法主要考虑两个实例在本体树中的最短路径,树高度,层次节点的密度等内容,其中α,β≥0是参数值α=0.2且β=0.6,其中l是最短路径,h是两个实例在树中最近的相同上层语义节点在树中的高度。公式表明两个概念的相似度随着路径l增加而递减,随着高度h增加而递增。

以图l所示的语义树为例,计算网络构件实例“快递”和“快递结算业务”的相似度时:两者之间的最短路径为:快递-发货管理-货到付款-快递结算业务,其长度l=3;两个实例在树中最近的相同上层语义节点是“发货管理”,其高度h=2。代入公式得:。

3.2 连接件替换算法及模拟

WSDL的针对不同操作类型分:One-Way类型的操作从外部获得输入消息;而Notification类型的操作则是向外发出消息;Request-Response类型的操作从外部获得一个请求消息之后向外发出一个响应消息;Solicit-Response类型的操作向外发出一个请求之后从外部获得一个响应消息。因此,连接件的稳定是整个系统稳定、有序的基石。

其次,提出连接件模型的四元组表示< P,C,T,￡,Φ> ,其中(1) P端口集合;(2) C约束条件,C=;(3) T接件类型(4) ￡ 映射函数(P×2C)×(P×2C)T;(5) Φ(i,j):Pi×Pj[0……1]代表某一类型的连接件实例之间转换的概率。

在连接件替换法则引入Shannon(香农)理论的信息熵来描述,,Pi=Φ(i,j)得:来描述信息“噪音”, 香农指出:信息熵是信息论中用于度量信息量的一个概念,变量的不确定性越大,熵也就越大。

约束条件其主要体现在功能性(所含的功能),行为性(接口模型) ,调用 (顺序、并发、互斥)等在逻辑、语义等方面的关系,Φ(i,j)是通过约束条件之间描述的相似程度计算。这里我们采用扩展Levenstein[13]编辑距离算法来计算其概率数值。

1) 矩阵W是w1=[c1,……,cn],w2=[c1',……,cn']相乘的矩阵W=w1×w2-1,其中如果则W[i,j]=0反之则W[i,j]=1。

2) Fun=Min{(W[i-1,j],(W[i,j-1]+1),Wi-1,j-1)}为选取最小值进行填充。

3) 循环直至在W[n,n]所得的数值即为失效距离,最后得出相似度。

4) 因此得到转换概率:

如表1所示,描述的是系统中Request-Response类型的连接件含有5个实例间的转化概率,其中实例编号为2的转化为其他的实例的信息熵为H=-1/4{0.12*log0.12+0.20*log0.20+0.27*log0.27+0.41*log0.41}≈0.14

在遇到异常发生变更后,构件的约束条件也随之作改变,通过重新计算Levenstein'(wi,wj)和Φ(i,j),如图假如编号为3的实例“消失”,则转化概率重分配如表2。

此时,H’=-1/4{0.42*log0.42+0.37*log0.37+0.21*log0.21}≈0.11

显然,此时可以看出 ,表明被替换的元胞所含的信息熵大于替换后新元胞在系统中的信息熵,表明新的“组织”是有序度大,“系统”比较稳定。

4 元胞模型与模拟

模型空间的模拟是按均匀的划分网格平面,每个网格节点上代表网络构件或称为服务,其代表的元胞分为3类:1) 使用中的服务;2) 未使用的服务;3) 空。如图2所示的在整个二维网格(元胞)中横向、纵向坐标上元胞的排列是按语义相关所进行的排列,每个节点上元胞的3中状态在每个时刻元胞有且只有一种颜色代表,黑色代表使用中的服务,灰色代表未使用的服务,白色代表无服务存在。

演化时,异常的元胞发出一个要求替换的指令,并开始随机选取一个方向进行计算,如果当前的节点在概率数值上大于原始元胞,开始检测连接件的信息熵,确保整个系统处于稳态的状态下。否则继续查找,直到到达为空的边界,返回选择其他方向掩护,重复上述操作,直至找到一个合适地、可用于替换的元胞。

当黑色节点的元胞演化时,发生异常的元胞可被其他语义上相关的元胞所替换,即可在横,纵方向“延伸”,其自身节点变为“灰色”,四个方向上其他节点有且只有一个点变为黑色,即替换为该节点所代表的服务。同时,还存在发生元胞并不影响整个系统的功能,可以默认失效不做处理。因此得概率分布:1) 向上演化概率φ/4;2) 向下演化概率φ/4;3) 不发生变化1-(φ/4);4) 向右演化概率φ/4;5) 向左演化概率φ/4。结合构件模型和全概率公式,将其展开得到,i代表每一个方向上标号不大于n的元胞,sim(i,o)代表i元胞和o目标元胞语义相似度,v表明属于四个方向上的情况,对于每一个方向上成功被替换元胞的数学期望为,进而方差为:它们都反映离散随机变量偏离于均值的平均程度的两,它们的值越小,则随机变量偏于均值的平均程度越小,即越集中于均值。最后结合信息熵理论,判别演化点用:f(Pi≥P0)∨(H'≥H)true,即当且演化模型全概率公式所得的值大于原始发生异常的元胞点仅当连接件后状态的信息熵大于发生变迁以前的值,此时认为发生的演化是稳定。

图3 模拟电子商务的演化图

如图3是在本文的网络软件模拟演化的原型系统(evolution of internet software simulation system, EI3S)上模拟一个电子商务的购物系统的发生异常的演化图,EI3S是基于Eclipse平台,结合EMF和GEF[14]开发的可视化插件工程。在左边图形中,黑色节点代表可利用的网络构件,虚线代表服务之间的连接件,该流程包含:用户通过系统登入并选择相应操作后,可完成交易结算、下订单、货物管理等处理流程;发生异常时,系统登录服务被替换后找到的购物车身份验证服务,其网络软件体系结构随之发生变迁,得到如右图所示的模拟结果。系统变迁后的实际运行响应时间结果均符合“7s原则”。

5 结论

本文将元胞自动机理论引入到网络软件演化过程的模拟中,该研究可以预防和减少对系统和平台的损害。结合“二八理论”发现用于替换异常元胞的其他元胞大都集中于部分20%的元胞中,这一现象对发现和挖掘元胞(构件)的内在关联,保证和维护这些“备用”元胞(网络构件)的工作将是系统维护人员处理异常工作的重要组成部分。今后还需进一步研究的工作有:1) 如何有效地、方便地建立网络服务的领域本体模型和其模型映射的机制。2) 对于网络软件的约束条件的描述也是一项重要的研究方向,包括如何形式化地描述、形式化的推理等。

参考文献:

[1] 梅宏,陈锋,冯耀东,等.ABC:基于体系结构面向构件的软件开发方法[J].软件学报,2003,14(4):721-732.

[2] 李长云.基于体系结构的软件动态演化研究[D].杭州:浙江大学,2005.

[3] 符进强,汪泮,钱乐秋.基于动态构件框架的构件演化[J].计算机科学,2001,28(1).

[4] 龚洪泉,赵文耘,徐如志,钱乐秋.基于Pi演算的构件演化研究[J].电子学报,32(12).

[5] 张友生.构件运算与软件演化研究[J].计算机应用,2004,24(4):20-22.

[6] 陈振邦,王戟,董威,等.面向服务软件体系结构的接口模型,软件学报,2006,17(6):1459-1469.

[7] 黄罡,王千祥,梅宏,等.基于软件体系结构的反射式中间件研究[J].软件学报,2003,14(11):1819-1826.

[8] 王晓鹏,王千祥,梅宏.一种面向构件化软件的在线演化方法[J].计算机学报,2005,28(11):1890-1908.

[9] 石兵,冉平,马晓星,等.软件体系结构的属性图文法描述及其约束验证[J].计算机应用研究,2007,24(3):163-169.

[10] GARLAND, MONROER T, WILED. Acme: architectural descrip2tion of component based systems[C].//LEAVENS G T, SITARAMANM. Foundations of component2based systems. Cambridge: CambridgeUniversity Press, 2000: 47268.

[11] MONROE R T. Cap turing software architecture design expertise with armani, CMU2CS2163 [R]. Pittsburgh: Carnegie Mellon University,1998.

[12] Y. Li, Z. Bandar. An Approach for Measuring Semantic Similarity between Words Using Multiple Information Sources. IEEE Transactions on Knowledge and Data Engineering, 2003. 15(4): p871-882.

[13] Kleiweg P. L evenshtein [EB/O L]. http: //www. let.rug. nl/～kleiweg/lev/levenshtein. html. 2003.

[14] The Eclipse Foundation. Graphical Editing Framework (GEF) Documentation. [EB/OL]. /gef/reference/documentation.php, 2005.