元胞自动机建模的网构软件自适应方法研究

1、元胞自动机建模的网构软件自适应方法研究摘 要：网构软件的自适应性是目前网构软件研究的重要方向之一。本文提出了一种元胞自动机建模的网构软件自适应方法，该方法结合元胞自动机理论，对软件体系结构（SA）进行行为建模，反映自适应过程中的变化；设计了适合分布式环境特点的两层系统架构；同时在以往工作的基础上进行了改进.在不良模式检测过程中，为了减少管理员失误带来的损失，建立不良模式库，方便根据运行时刻的系统信息找到真正的不良模式。关键词：自适应；软件体系结构；元胞自动机；网构软件中图分类号：TP1 引言随着网络环境的开放与动态性，以及用户使用方式的个性化要求，要求软件能感知外部网络环境的动态变化，并随着这

2、种变化按照功能指标、性能指标和可信性指标等进行静态的调整和动态的演化，以使系统具有尽可能高的用户满意度。这样一种新的软件形态就是网构软件，其具有自主性、协同性、反应性、演化性和多态性等特点1。这些特性在技术上的共性之一可归结为自适应性，即，软件能够感知环境的变化，并根据环境的变化改变自身行为，采取适应性动作，以适应资源的可变性、用户需求的变化以及系统错误2。简单来说，是指在系统运行时刻没有人工参与，完全由软件来监控和调整自身。近年来，关于网构软件自适应方面已做了一些研究，主要包括：通过构件实体之间的协同模式以及演化的方式来动态地适应外部环境变化3，这里所说的环境变化是广义的，包含了资源变化与需

3、求变化的语义。文献3是这方面的代表工作，提出了一种以服务实体与协同部分分离、基于第三方面服务实体的协同聚合、协同模式的设计与演化适应环境变化为特征的开放协同软件模型作为网构软件的基础模型。使用智能Agent,从软件实体协同方式的动态调整角度来构建网构软件的自适应性质和自演化功能。另外一类重要工作是基于软件体系结构的网构软件自适应研究。文献4是这方面的代表工作，提出了一种以体系结构为中心的网构软件自适应方法，即监测、分析、规划、实施等自适应活动均围绕软件体系结构展开，其中，网构软件运行状态和行为以运行时软件体系结构的方式实时展现和在线调整；自适应相关知识通过软件体系结构记录、组织和加工，以实现系

4、统状态和行为的自动分析和调整规划。但是总的来看，目前对于网构软件在自适应过程中自动化水平、复用性方面还存在一定的缺陷。比如：文献4中要求管理员事先建立不良模式（描述带来负面影响的模式）和良好模式（描述无影响或带来正面影响的模式），这个对管理员的要求比较高，并且要有丰富的经验，能够准确去预测系统中可能存在的不良模式，来指导整个自适应活动；另一方面，将自适应调整映射为中间件的实际操作，由中间件去实现自适应。但中间件只能针对特定的软件体系结构去调整，复用性不是很高。针对以上问题，本文提出了一种元胞自动机建模的网构软件自适应方法。首先，运用软件体系结构对网构软件基本形态建模，然后，使用元胞自动机对软件

5、体系结构的行为建模，实现自适应。同时，本文还在以往的研究基础之上进行了改进。为了减少因管理员预测失误导致自适应失败带来的损失，采用自动检测：对系统增加了触发设施。并且单独建立了不良-2-模式库，事先预存一些不良模式，然后定期由管理员进行维护（修改和更新）。本文余下的部分组织为：第二节概述整个方法；第三节介绍关键技术；第四节实验与评估；第五节结论。2 方法概述网构软件的自适应能力一般包括两方面的含义：其一是对外部环境的变化作出适当的反应；其二是对系统需求的变化作出适当相应的反应；从而使得系统所提供的服务功能或性能等维持在一个令人满意的、具有一定可信度的水平上5。本文的研究工作就是系统如何能够应开

6、发环境和需求的动态变化对自身进行动态调整以适应变化。本文利用元胞自动机对SA 的行为建模，此时SA 是一个分布共享的对象，作为自适应的驱动因素（带来负面影响的SA 形成的不良模式），进行自适应的依据（根据不良模式进行合适的适应性动作），以及自适应的载体。具体的自适应系统采用两层系统架构，如图1所示：图1 自适应系统架构用户层 用户层是系统的接口，主要包括两项内容：1）监测器本系统的监控机制，对运行系统进行监控，负责应用系统状态信息的采集，并在产生变化时抛出事件。2）可视化建模建立不良模式模型。向不良模式库中添加新的不良模式，由管理员维护，负责对不良模式库进行定期的更新。系统层 系统层是整个实现

7、自适应的核心，由其完成系统自适应的过程，其中包括库（不良模式库、动作库、规则库），以及对SA 建模的元胞自动机总控制程序。管理员更新不良模式库时，也将该不良模式对应的动作和规则分别添加到动作库和规则库中。首先监测器抛出事件，元胞自动机进行捕获；然后进行不良模式检测，根据采集到的应用系统相关信息与不良模式库进行匹配，找到存在的不良模式，也就找到了匹配该事件的规则；接着，在规则库中找到不良模式对应的动作，最后将适应性动作反映到运行时刻体系结构对象中，譬如：增加（Add）构件、删除（Del）构件等，完成整个自适应行为。本系统的自适应逻辑在系统中的执行流程，也正是自适应的触发设施：事件-规则-动作。-

8、3-其减少了人工参与，从而减少失误，实现对系统中不良模式的自动检测。由事件的抛出，引发元胞自动机总控制程序在规则库中找寻匹配该事件的规则，从规则中提取出动作，执行之，完成一次自适应行为。其中，规则和动作以元组的形式存放。规则表示为（事件，不良模式名称，动作），动作表示为（动作类型，动作名称，参数序列，实现变化动作的类）。而元胞自动机总控制程序就是捕获事件，匹配应用系统中的不良模式，根据不良模式找到相应的适应规则，并执行规则中指定的适应性动作，完成系统的适应过程。因此元胞自动机部件是系统的核心部分之一，除此之外，对不良模式库的管理和不良模式的检测也是本系统的核心部分，具体细节见第三节。3 关键技

9、术软件体系结构作为自适应的载体，对于其定义，目前学术界还未形成统一的意见，根据本系统模型，采用Garlan&Show 的定义：SA = components, connectors, constrains。其中，构件（component）可以是一组代码，如程序模块，也可以是一个独立的程序，如数据库服务器。连接件（connector）可以是过程调用、管道、远程过程调用等，用于构件之间的相互作用。约束（constrains）一般为对象连接时的规则，或指明构件连接的势态和条件。3.1 不良模式库为了查询到应用系统中的不良模式，需要与不良模式库中的不良模式进行匹配，那么定义不良模式时要有严格的规范标准

10、。具体由管理员进行管理，主要分为两个步骤：1.建立不良模式：利用用户层中的可视化建模工具建立不良模式。方便管理员去更新不良模式库，也便于管理员更直观地了解不良模式。同时，管理员也要编写相应的规则和动作，一起存放到系统层的相应库中。2.不良模式注册：要将不良模式存储在计算机中，那么一个完整的不良模式记录应该包括：应用系统状态（用于识别应用系统中存在的不良模式）、造成该状态的原因、该状态引发的不良后果（用于匹配抛出事件）、相应的调整方案（指导应用系统的调整）。其中，应用系统状态又包含三类信息：1）构件信息：包括构件类型（如EJB/Servlet等）、构件方法（如方法名称、方法个数等）、构件配置（如

11、实例池大小等）和构件操作（如构件回调方法等）。2）构件的交互信息：包括方法调用类型（如同步/异步调用等）、方法调用参数（如参数大小等）、方法调用序列。3）境信息：包括中间件服务配置信息与底层硬件信息。在上述信息中，除了某些与应用逻辑相关的构件操作以外，其余信息都是可以由中间件自动获取，因此，大部分的不良模式都可以自动检测。这部分也是由监测器去完成，监测器是一个广义的概念，完成对系统性能的监测以及应用系统信息的采集。3.2 不良模式检测在进行不良模式检测之前，需要先采集应用系统相关的信息，包括静态信息和运行时刻的动态信息。这个由监测器抛出事件后开始进行采集。应用系统的静态信息，比如构件名称、构件

12、类型等可以从部署描述符里得到。而运行时刻信息，可以通过给中间件添加截取器的方式来进行采集。截取器会把用户关心的运行时刻信息写到日志文件中，可以在不被应用感知的情况下添加、删除，而且可以动态的触发。在采集到应用系统信息之后，就可以进行不良模式的检测工作：将采集到的应用系统信-4-息与不良模式库中的不良模式进行匹配，以检测出当前运行系统中存在的不良模式。其中对于构件信息的匹配，可以通过简单的遍历来查找与模式匹配的状态信息。对于构件交互信息匹配，由于一般情况下构件之间的调用数目都很庞大，采用数据挖掘技术中的相关规则算法6来完成任务，可以查找出符合一定条件的调用序列，从而完成不良模式的检测7。3.3

13、元胞自动机的SA 建模为了能够全面准确地描述所感知的变化和实施的调整，本文应用元胞自动机对SA 的行为建模，实现SA 的动态性，并利用面向对象的方法完成整个自适应动作。其中，按照SA模型中元素的种类，SA 的动态性可以分解为实体调整、实体间关系调整和实体属性调整。实体包括构件和连接件。实体的调整包括Add 和Delete（增加一个实体、删除一个实体）两种操作；实体间关系调整可以看成是改变元胞的邻居；实体属性调整就是改变实体的属性值，例如：实体类型、名称等。元胞自动机（Cellular Automata，简称CA）8由最基本的四部分组成：元胞、元胞空间、邻居及规则。其是一类模型的总称，或者说是一

14、个方法框架。特点是时间、空间、状态离散，每个变量按照一定的局部规则在离散的时间维上演化。正好能很好地描述软件体系结构在自适应过程中的动态变化，即，一组离散地分布在系统中的各个构件，按照特定的自适应规则进行动态演化。要利用元胞自动机建立SA 动态模型，需要扩展现有的标准元胞自动机模型。根据Garlan&Show 模型的定义，本文采用了如图2 所示的SA 简化模型（假设：一个系统的SA 由4 个构件和4 个连接件构成）。对该SA 简化模型形式化后得到一个有向图G4=(V(G4),E(G4),FG4),其中V(G4)为系统构件集合，E(G4)为系统连接件集合，FG4 为V(G4) 到E(G4)上的函

15、数，即构件和连接件之间的关系。针对该SA 简化模型图，可以构造对应的元胞自动机模型（CA 模型）M=(L,S,N,F),其中L、S、N 和F 的定义如下：L 为元胞空间：本文将元胞分布的二维空间作为元胞空间，并定义了元胞构型（configuration），即在某个时刻元胞空间上所有元胞状态的空间分布组合，这里将SA 产生的模型（良好模型和不良模型）等同于该时刻的元胞构型。用多维的整数矩阵来保存，如图3 所示，为SA 关系邻接矩阵图。每个椭圆关联着两个具有直接交互方向关系构件，其方向性由行和列分别表示，行为被关联方向的末尾构件，列为被关联方向的起始构件。三角形表示构件的自交互关系，这种关系隐藏在

16、构件自身内部，本系统中不予考虑。将椭圆用1表示，其余用0 表示，便得到了 SA 模型的整数矩阵。S 为元胞的状态：严格意义上,元胞自动机的元胞只能有一个状态变量，但在本文中进行了扩展，可以拥有多个状态变量。N 为元胞邻居：本文定义与元胞有语义关系的元胞为该元胞的邻居。对图2 所示SA 模型而言，元胞component1 的邻居是 component2、component3，其他的元胞邻居依此类推。F为动态规则：以上的元胞及元胞空间只表示了系统的静态成分，为将“动态”引入系统，必须加入动态规则。本文的动态规则将元胞自动机状态的变化看成是对数据或信息的判断和处理。-5-图2 SA 简化模型图3 S

17、A 关系邻接矩阵根据上述元胞的特点可以抽象为面向对象的思想。从面向对象的角度来讲，本系统的对象就是元胞，所有的运算都是围绕着元胞来进行的，元胞有自己的状态属性和动作行为。这完全符合面向对象的思维。元胞的状态就相当于对象的属性，元胞的演化规则就相当于对象的行为，这样就可以定义一个元胞类。根据SA 的动态性调整，属性包括邻居节点的元胞编号、实体名称和实体类型。元胞类的动作包括Add 或Delete 实体，改变元胞邻居编号和更改属性值。当系统违反了事先的约束，监测器就可以检测到相应的事件，然后匹配不良模式，根据该不良模式找到所包含的实体，也就是找到需要进行动态调整的元胞空间，接着按照规则查找到相应的

18、动作，最后映射到各个元胞类的动作，完成整个自适应调整。4 实验与评估为了展示这种基于元胞自动机建模的网构软件自适应方法，开发了一个简单的模拟实验，并对该系统在不进行自适应动态调整和根据性能约束指标作动态调整两种情况下的性能表现进行了测量和比较。模拟一个网上书店的部分实现，主要是客户端从服务器端获取图书信息，然后将这些信息显示在web 页面上。客户端和服务器部署在不同的机器上，当客户需要获取多本书的信息包括书名、作者和单价时，需要若干次调用远程的CartSesEJB 中的addItem()方法。由于客户端和服务器部署在不同的机器上，因此函数调用都必须通过网络，调用参数与返回值都需要进行序列化与反

19、序列化的操作，而且还花费时间通过网络传输数据。随着用户的增多，这种采用多次远程调用获取一组属性值的方法会增加网络上的时间消耗，极大地降低性能，是应用中存在的一个性能不良模式。为去除该不良模式带来的性能影响，需要对系统进行自适应调整。调整方案就是，通过-6-一次远程调用将需要显示的书本信息全部发送给CartSesEJB,而不是每显示一次书本信息就进行一次远程调用。可以在服务器端增加一个会话外观构件，客户端通过一次远程调用将所需要显示的书本信息全部发送给会话外观构件，然后再由该构件调用CartSesEJB 中的相应方法，通过一次远程调用完成所有的数据传输。对于上述不良模式， 相应的规则和动作就是： rule1(event1,fine-grained remotecalls,action1),action1(add,disposepreformance,null,stratage1)。总控制程序根据stratage1（实现变化动作的类）找到具体的实现变化动作的方法：增加会话外观构件，然后调整三个构件之间的调用关系。本实验以客户获取一