软件体系结构动态演化的元胞自动机模型研究

2015 ， 51 （9 ） 软 件 体 系 结 构SA （Software Architecture ） 作 为 软 件 的 宏 伟 蓝 图 和 支 撑 骨 架 ， 在 软 件 体 系 中 起 着 决 定 性 的 作 用 ， 逐 渐 成 为 软 件 的 研 究 热 点 之 一 。 它 是 软 件 设 计 的 高 层 抽 象 和 概 括 ， 为 人 们 宏 观 把 握 软 件 的 整 体 结 构 提 供 了 一 条 途 径 1-3 。 在 软 件 生 命 周 期 中 ， SA 起 着 关 键 性 的 作 用 。 早 期 ， 起 初 认 为SA 担 当 着 从 需 求 到 实 现 的 桥 梁 4 ， 解 决 了 软 件 需 求 向 软 件 实 现 （ 包 括 代 码 ） 的 平 坦 过 渡 问 题 ， 是 软 件 生 命 周 期 中 开 发 、 集 成 、 测 试 及 维 护 阶 段 的 基 软 件 体 系 结 构 动 态 演 化 的 元 胞 自 动 机 模 型 研 究 刘 晓 斌 ， 杨 贯 中 ， 欧 阳 柳 波 ， 李 勇 军 LIU Xiaobin,YANG Guanzhong,OUYANG Liubo,LIYongjun 湖 南 大 学 信 息 科 学 与 工 程 学 院 ， 长 沙 410082 College ofInformation Science extended cellular automata model; steady-state transfer of moving-point; application of constraint;software architecture 摘 要 ： 目 前 软 件 体 系 结 构 动 态 演 化 的 元 胞 自 动 机 模 型 存 在 描 述 单 一 、 元 胞 间 关 系 不 明 确 、 没 有 详 细 阐 述 动 态 演 化 过 程 应 用 约 束 条 件 的 缺 点 。 针 对 这 些 不 足 进 行 相 关 的 研 究 ， 重 新 定 义 了 软 件 体 系 结 构 动 态 演 化 的 扩 展 元 胞 自 动 机 模 型 ， 基 于 扩 展 元 胞 自 动 机 模 型 结 合 演 化 应 用 约 束 条 件 ， 分 析 了 软 件 体 系 结 构 的 动 态 演 化 过 程 ， 运 用 元 胞 间 控 制 约 束 条 件 和 行 为 相 关 约 束 条 件 来 正 确 地 指 导SA 动 态 演 化 。 提 出 了 动 点 稳 态 转 移 的 概 念 ， 对 演 化 程 度 和 一 致 性 进 行 定 义 分 析 ， 此 方 法 比 以 往 的 元 胞 自 动 机 模 型 更 能 准 确 指 导SA 动 态 演 化 ， 促 进SA 动 态 演 化 的 进 一 步 研 究 。 通 过 案 例 验 证 了 该 方 法 的 应 用 价 值 和 可 行 性 ， 可 以 更 全 面 地 应 用 于 软 件 体 系 结 构 的 动 态 演 化 。 关 键 词 ： 动 态 演 化 ； 扩 展 元 胞 自 动 机 模 型 ； 动 点 稳 态 转 移 ； 应 用 约 束 条 件 ； 软 件 体 系 结 构 文 献 标 志 码 ： A 中 图 分 类 号 ： TP311 doi ： 10.3778/j.issn.1002-8331.1306-0367 基 金 项 目 ： 国 家 核 高 基 重 大 专 项2012 年 应 用 类 课 题 （No.2012ZX01045-004-005-002 ） ； 国 家 科 技 支 撑 计 划 项 目 （No.2012BAF12B20 ） ； 国 家 自 然 科 学 基 金 （No.60901080 ） 。 作 者 简 介 ： 刘 晓 斌 （1986 ） ， 男 ， 硕 士 ， 主 要 研 究 方 向 为 软 件 体 系 结 构 、 软 件 工 程 ； 杨 贯 中 （1963 ） ， 男 ， 教 授 ， 主 要 研 究 方 向 为 网 络 教 育 、 计 算 机 网 络 工 程 与 分 布 式 计 算 、 多 媒 体 通 信 、 软 件 工 程 、 领 域 工 程 ； 欧 阳 柳 波 （1972 ） ， 男 ， 博 士 ， 副 教 授 ， CCF 会 员 ， 主 要 研 究 方 向 为 智 能 信 息 处 理 、 软 件 工 程 ； 李 勇 军 （1979 ） ， 男 ， 硕 士 研 究 生 ， 主 要 研 究 方 向 为 人 工 智 能 、 模 式 识 别 、 软 件 工 程 。E-mail ： 收 稿 日 期 ： 2013-07-01 修 回 日 期 ： 2013-08-19 文 章 编 号 ： 1002-8331 （2015 ） 09-0087-06 CNKI 网 络 优 先 出 版 ： 2013-10-17 ， /kcms/detail/11.2127.TP.20131017.1526.006.html Computer Engineering and Applications 计 算 机 工 程 与 应 用 87Computer Engineering and Applications 计 算 机 工 程 与 应 用 2015 ， 51 （9 ） 础 。 随 后 ， SA 的 研 究 扩 展 到 整 个 生 命 周 期 ， 如 文 献5 将 SA 作 为 贯 穿 整 个 软 件 生 命 周 期 的 核 心 制 品 。 软 件 体 系 结 构 描 述 了 软 件 系 统 的 结 构 组 成 ， 构 件 之 间 的 交 互 、 连 接 及 约 束 等 4 。SA 从 全 局 的 角 度 为 系 统 提 供 结 构 组 成 、 交 互 等 信 息 ， 为 人 们 宏 观 把 握 软 件 演 化 提 供 了 一 条 有 效 途 径 。 软 件 演 化 分 为 静 态 演 化 与 动 态 演 化 两 方 面 ， 目 前 一 些 软 件 体 系 结 构 描 述 语 言 如SADL （Software Architecture Description Language ） 可 通 用 于 软 件 演 化 的 表 述 ， 其 中Darwin 和C2 都 支 持SA 的 动 态 体 系 结 构 演 化 ， CHAN ， Wright ， Rapide 支 持SA 的 动 态 语 义 演 化 6-10 。 这 些 形 式 化 描 述 不 是 以 演 化 为 目 标 ， 用 来 刻 画 “ 演 化 ” 存 在 不 足 。 对 静 态 演 化 的 分 析 与 阐 述 在 文 献11 中 已 有 比 较 完 善 的 说 明 ， 但 此 文 并 未 给 出 具 体 的 动 态 演 化 模 型 。 如 何 在SA 层 次 上 建 模 、 分 析 动 态 演 化 并 保 证SA 演 化 的 正 确 性 ， 已 成 为 当 前 研 究 软 件 动 态 演 化 的 关 键 问 题 。 关 于 软 件 体 系 结 构 的 动 态 演 化 ， 研 究 者 们 在 此 方 面 做 出 了 很 多 贡 献 。 王 映 辉 等 人 11 结 合 动 态 语 义 网 及 其 浸 润 理 论 来 描 述 和 刻 画SA 的 动 态 演 化 ， 但 没 有 具 体 确 定SA 动 态 演 化 相 关 约 束 ； 程 淑 玉 12 提 供 了 使 用 元 胞 自 动 机 理 论 建 立SA 动 态 演 化 模 型 ， 但 只 是 将 元 胞 自 动 机 思 想 引 入 到SA 动 态 演 化 的 分 析 当 中 ， 没 有 具 体 涉 及 动 态 演 化 的 演 化 规 则 和 演 化 过 程 的 约 束 条 件 ； 吴 彦 等 人 13 讨 论 了 网 络 软 件 的 元 胞 自 动 机 模 型 的 动 态 演 化 ， 但 不 适 用 于 非 网 络 软 件 的 动 态 演 化 ， 此 文 献 模 拟 网 络 软 件 在 发 生 异 常 时 状 态 变 迁 过 程 ， 即 在 适 应 机 制 下 的 动 态 演 化 ， 依 赖 于 网 络 软 件 的 自 动 调 节 能 力 ， 但 对 于 软 件 因 其 他 原 因 （ 例 如 外 界 需 求 的 扩 充 等 ） 而 进 行 的 动 态 演 化 情 况 没 有 考 虑 ， 且 没 有 考 虑 人 工 干 预 的 动 态 演 化 以 及 演 化 规 则 约 束 条 件 不 是 很 具 体 完 善 ； 徐 洪 珍 等 人 14 运 用 左 右 应 用 约 束 条 件 刻 画 动 态 演 化 的 前 断 言 与 后 断 言 ， 构 建 条 件 超 图 文 法 应 用 于 软 件 体 系 结 构 的 动 态 演 化 ， 但 此 左 右 应 用 约 束 条 件 限 于 基 于 超 图 文 法 的 软 件 体 系 结 构 动 态 演 化 ， 不 适 用 于 元 胞 自 动 机 的 软 件 体 系 结 构 动 态 演 化 规 则 约 束 条 件 。 本 文 将 在 文 献12-13 的 基 础 上 ， 针 对 以 上 的 不 足 进 行 研 究 ， 基 于 软 件 体 系 结 构 动 态 演 化 的 扩 展 元 胞 自 动 机 模 型 ， 首 次 具 体 分 析 元 胞 间 的 约 束 关 系 ， 结 合 带 有 应 用 约 束 条 件 的 动 态 演 化 规 则 应 用 于SA 动 态 演 化 过 程 当 中 。 1 动 态 演 化 阐 述 1.1 基 础 理 论 软 件 在 运 行 过 程 中 其 体 系 结 构 动 态 地 发 生 着 改 变 ， 发 生 的 变 化 主 要 包 括 两 类 ： （1 ） 软 件 内 部 执 行 引 起 的 体 系 结 构 变 化 ； （2 ） 软 件 系 统 外 部 的 请 求 对 软 件 进 行 的 重 配 置 。 内 部 执 行 引 起 的 体 系 结 构 变 化 的 情 况 很 多 ， 如 当 前 的WEB 服 务 器 大 都 使 用 连 接 池 技 术 响 应 客 户 端 请 求 ， 请 求 到 达 时 创 建 新 的 构 件 。 在 高 安 全 性 软 件 系 统 中 ， 升 级 或 修 改 运 行 状 态 的 软 件 ， 运 行 过 程 中 完 成 体 系 结 构 的 修 改 ， 就 属 于 第 二 类 变 化 。 运 行 过 程 中 的 修 改 过 程 通 常 称 为 在 线 演 化 或 动 态 演 化 。 演 化 涉 及 到 软 件 体 系 结 构 的 结 构 、 属 性 、 风 格 、 系 统 行 为 等 等 内 容 ， 在 实 施 演 化 过 程 中 ， 同 时 需 要 保 持 系 统 的 结 构 化 层 次 上 的 “ 一 致 性 ” 和 “ 完 整 性 ” 。 满 足 此 条 件 才 能 进 行 动 态 演 化 ， 可 以 保 障SA 动 态 演 化 的 正 确 进 行 。 1.2 规 则 算 法 软 件 体 系 结 构 的 动 态 演 化 主 要 涉 及 到 运 行 过 程 特 定 语 义 环 境 情 景 下 软 件 构 件 、 连 接 件 的 增 加 、 删 除 、 替 换 ， 以 及 构 件 之 间 交 互 关 系 、 拓 扑 结 构 的 改 变 等 等 。 动 态 演 化 遵 循 一 定 的 演 化 规 则 ， 具 体 总 结 分 为 以 下 几 种 ： （1 ） 消 除 软 件 缺 陷 的 正 确 性 演 化 ； （2 ） 扩 展 软 件 需 求 的 完 整 性 演 化 ； （3 ） 适 应 新 环 境 的 重 配 置 。 这 些 演 化 规 则 包 含 着 演 化 实 施 过 程 中 ， 对 软 件 体 系 结 构 构 件 的 增 加 、 删 除 、 替 换 ， 以 及 结 构 的 重 配 置 。 增 加 构 件 属 于 扩 展 软 件 而 进 行 完 整 性 的 演 化 ， 为 保 持 结 构 的 一 致 性 要 求 ， 系 统 应 保 持 原 有 风 格 不 变 或 为 旧 风 格 的 子 风 格 ， 同 时 满 足 相 连 构 件 的 规 则 而 进 行 必 要 的 完 整 性 检 查 ， 简 易 的 算 法 描 述 为 ： do orign=getOrignStyle （ ） ； If insertComp=true find the conn and place ； If statify completeness conn.insert （place ， comp ） ； change status for consistence ； ； getStyle （ ） ； while （style isn t orign or subOrign ） ； 删 除 构 件 存 在 于 消 除 缺 陷 的 正 确 性 演 化 及 适 应 性 演 化 两 者 中 ， 要 删 除 的 构 件 必 定 不 在 运 行 的 执 行 栈 中 ， 否 则 是 不 能 够 进 行 删 除 的 ， 同 时 与 其 他 构 件 或 连 接 件 构 成 特 定 间 接 关 系 的 构 件 ， 也 是 不 允 许 删 除 的 ， 删 除 的 构 件 会 对 其 他 构 件 的 关 系 如 可 达 性 造 成 影 响 ， 系 统 结 构 和 语 义 造 成 一 定 改 变 。 简 易 算 法 可 表 示 为 ： If comp not in Stack If relatedcomp not in Stack Find the place of conn ； conn.Delete （p ， comp ） ； Refine s ； 消 除 软 件 缺 陷 时 进 行 的 正 确 性 演 化 过 程 常 常 要 替 换 构 件 ， 替 换 构 件 前 就 考 虑 构 件 的 状 态 是 否 被 其 他 构 件 882015 ， 51 （9 ） 调 用 等 等 ， 新 构 件 的 接 口 与 被 替 换 构 件 接 口 应 保 持 一 致 性 ， 替 换 后 重 新 改 变 系 统 结 构 。 简 易 的 算 法 可 以 作 以 下 说 明 ： If comp not called getStatus （ ） ； find the conn and place of old comp c1 ； conn.replace （place ， c1 ， c2 ） ； change status for consistence ； if c1 port not match c2 port chang c2 port ； 适 应 新 的 环 境 下 运 行 需 要 ， 进 行 的 变 更 构 件 间 连 接 关 系 ， 对 体 系 结 构 重 新 配 置 ， 此 项 操 作 引 起 的 结 构 演 化 变 动 过 大 ， 一 般 会 花 费 巨 大 的 成 本 。 重 新 配 置 操 作 要 把 原 有 的 体 系 结 构SA 进 行 分 解 ， 分 别 放 入 构 件 集 和 连 接 件 集 ， 然 后 根 据 新 环 境 需 求 重 新 组 装 系 统 体 系 结 构 。 简 易 算 法 可 描 述 为 ： collect all conns ， comps which involve ； decompose S1 into conn1 ， comp1 ； getSome from conn1 ， comp1 ； if som not conn1 ， comp1 find conns ， comps combine to S2 ； delete rest cons ， comps ； 2 SA 动 态 演 化 的 元 胞 自 动 机 模 型 软 件 体 系 结 构 的 组 成 元 素 在 任 何 时 刻 仅 处 于 一 种 状 态 之 中 ， SA 动 态 演 化 过 程 涉 及 到 构 件 的 状 态 变 化 可 以 很 好 地 使 用 元 胞 自 动 机 来 形 象 化 地 刻 画 ， 另 外 单 纯 的 状 态 变 迁 无 法 深 入 地 阐 述 和 刻 画SA 动 态 演 化 约 束 。 本 文 提 出 使 用 带 有 上 下 文 环 境 约 束 验 证 的 限 定 条 件 来 描 述SA 动 态 演 化 过 程 ， 通 过 构 建 扩 展 元 胞 自 动 机 模 型 建 模SA 动 态 演 化 过 程 。 2.1 构 件 的 相 关 性 从 动 态 演 化 的 软 件 体 系 结 构 构 件 的 相 关 性 进 行 分 析 ， 对 于 正 确 构 建 软 件 体 系 结 构 的 元 胞 自 动 机 模 型 具 有 重 要 的 意 义 。 构 件 相 关 包 括 结 构 相 关 和 行 为 相 关 ， 结 构 相 关 指 构 件 之 间 连 接 方 式 决 定 的 静 态 相 关 性 ； 行 为 相 关 是 具 有 相 关 能 力 的 构 件 在 特 定 的 系 统 状 态 下 表 现 的 一 种 行 为 上 相 互 制 约 和 影 响 的 相 关 。 行 为 相 关 不 仅 与 结 构 相 关 ， 还 与 所 处 状 态 相 关 ， 在 对 一 个 构 件 实 施 动 态 演 化 时 ， 需 要 驱 动 此 构 件 处 于 静 止 状 态 ， 这 样 会 影 响 与 之 行 为 相 关 的 其 他 构 件 ， 因 此 下 面 着 重 分 析 行 为 相 关 。 定 义2.1 （ 行 为 相 关 矩 阵 ） 对 于 软 件 体 系 结 构 模 型 SAM =(COM CON) ， 各 个 构 件 之 间 的 行 为 相 关 关 系 可 以 用 行 为 相 关 矩 阵 C relation 表 示 ：C relation =(c ij ) n n ， 其 中 c ij 表 示 软 件 体 系 结 构SAM 中 第i 个Com i 与 第 j 个 构 件 Com j 之 间 的 行 为 相 关 性 关 系 ， 并 且C ij 满 足 ： C ij = 1 Com i 与Com j 之 间 行 为 相 关 0 Com i 与Com j 之 间 行 为 无 关 矩 阵 的 每 一 行 或 每 一 列 都 是 一 个 向 量 ， 表 示 空 间 中 与 构 件 存 在 行 为 相 关 性 关 系 的 数 学 表 示 。 由 行 为 相 关 矩 阵 ， 产 生 行 为 相 关 的 构 件 必 然 存 在 于C ij =1 的 构 件 关 系 之 中 ， 也 就 是 C ij =0 表 示 构 件 之 间 不 可 能 存 在 行 为 相 关 。 定 义2.2 （ 行 为 相 关 构 件 集 ） 待 演 化 的 构 件 集 C com 及 其 与 之 行 为 相 关 的 构 件 集 组 合 产 生 的 构 件 并 集 称 为 行 为 相 关 构 件 集 RC coms 。 当 一 个 构 件 （ 或 构 件 集 合 ） 进 行 动 态 演 化 时 ， 其 动 态 演 化 的 影 响 范 围 比 本 身 实 施 对 象 要 大 ， 分 析 实 施 对 象 的 行 为 相 关 构 件 集 对 软 件 体 系 结 构 的 正 确 动 态 演 化 具 有 指 导 性 作 用 ， 行 为 相 关 是 演 化 约 束 条 件 的 重 要 组 成 部 分 。 2.2 扩 展 的 元 胞 自 动 机 元 胞 自 动 机 （Cellular Automata ， CA ） 是 由 一 定 数 量 的 元 胞 组 成 的 自 治 的 有 限 状 态 机 15 。 结 合 元 胞 自 动 机 的 相 关 理 论 知 识 ， 本 文 提 出 了 软 件 体 系 结 构 的 元 胞 自 动 机 模 型 ， 其 中 体 系 结 构 中 的 一 个 部 件 的 状 态 可 用 图1 表 示 。 组 成 体 系 结 构 的 部 件 可 以 为 构 件 或 连 接 件 ， 在SA 元 胞 自 动 机 模 型 中 的 一 个 元 胞 代 表 体 系 结 构 中 的 一 个 部 件 ， 元 胞 的 状 态 S(t) 表 示 某 元 胞 在 t 时 刻 的 状 态 ， 软 件 体 系 结 构 的 演 化 形 象 化 成 元 胞 在 有 限 的 状 态 集 之 间 的 变 化 过 程 。 定 义2.3 （ 扩 展 元 胞 自 动 机 模 型 ） 软 件 体 系 结 构 可 抽 象 为 有 向 图 G(V E F) ， 构 造 该 有 向 图 的 扩 展 元 胞 自 动 机 模 型 A =(L d S N f C) ， 其 中 ，A 代 表 一 个 扩 展 元 胞 自 动 机 模 型 ， 也 即 动 态 的 软 件 体 系 结 构 ；L d 表 示 元 胞 空 间 ，L d =(D 1 D 2 D k ) ； 状 态 集 ：S =S 1 S 2 S k ， 有 限 个 状 态 的 集 合 ；N 表 示 所 有 邻 域 内 元 胞 的 集 合 ， 即 包 含 n 个 不 同 元 胞 状 态 的 一 个 空 间 矢 量 ， 记 为 N = (S 1 S 2 S n ) ；f 表 示 将 S 映 射 到 S 上 的 一 个 状 态 演 化 规 则 ； C 为 f 上 的 约 束 验 证 条 件 集 。 定 义2.4 （ 元 胞 状 态 演 化 ） 一 个 部 件 从 一 个 状 态 S(t) 演 化 成 另 一 个 状 态 ， 必 须 遵 循 一 定 的 演 化 规 则 ， 也 依 赖 于 它 自 己 的 当 前 状 态 及 邻 域 内 部 件 的 状 态 ， 可 用 公 式 表 示 为 ： S i (t +1) =f(S i (t) S G (t) 其 中 ，S G (t) 表 示 元 胞 i 的 邻 域 内 元 胞 的 状 态 集 合 ，S i (t) 表 示 第 i 个 元 胞 在 t 时 刻 的 状 态 ，f 是 一 个 元 胞 状 态 的 图1 状 态 演 化 示 意 图 S(t -1) S(t) S(t +1) 刘 晓 斌 ， 杨 贯 中 ， 欧 阳 柳 波 ， 等 ： 软 件 体 系 结 构 动 态 演 化 的 元 胞 自 动 机 模 型 研 究 89Computer Engineering and Applications 计 算 机 工 程 与 应 用 2015 ， 51 （9 ） 映 射 函 数 ， 被 称 为SA 元 胞 自 动 机 的 自 动 转 换 规 则 。 体 系 结 构 中 元 胞 部 件 的 状 态 S 取 值 为S-I S-S S-C S-T ，S-I 状 态 表 示 部 件 没 有 被 调 用 ， 部 件 在 体 系 结 构 中 没 有 起 任 何 作 用 ， 处 于 “ 静 止 ” 状 态 ；S-S 表 示 部 件 处 于 内 部 运 作 过 程 中 ， 已 经 被 其 他 部 件 触 发 或 者 内 部 策 动 源 起 动 时 刻 ， 它 的 下 一 个 状 态 将 会 到 达 S-C ； S-C 表 示 部 件 内 部 的 策 动 因 子 已 通 过 映 射 函 数 影 响 其 他 部 件 ， 信 息 函 数 传 播 着 部 件 的 数 据 ， 辐 射 出 去 的 过 程 ； S-T 表 示 部 件 已 经 通 过 其 邻 域 的 部 件 影 响 ， 信 息 数 据 将 在 此 部 件 处 终 止 流 动 映 射 。 定 义2.5 （ 元 胞 状 态 演 化 规 则 ） 体 系 结 构 的 部 件 在 动 态 演 化 中 状 态 的 变 化 代 表 着 元 胞 从 一 个 状 态 子 集 迁 移 到 另 一 个 状 态 子 集 ， 状 态 的 变 化 遵 循 特 定 演 化 规 则 f ， 其 中 f 可 以 描 述 如 下 ： （1 ） 如 果 S i 是 S-I 状 态 ， 它 邻 域 内 部 件 都 处 于 S-I 状 态 ， 则 它 的 状 态 将 不 会 改 变 ， 如 果 它 邻 域 内 部 件 处 于 S-C 状 态 ， 该 部 件 将 受 到 邻 域 内 部 件 的 影 响 传 播 ， 而 在 t +1 时 刻 转 为 S-S 状 态 。 （2 ） 如 果 S i 是 S-S 状 态 ， 表 示 元 胞 部 件 正 在 发 生 着 部 件 内 部 的 演 化 ， 该 时 刻 的 下 一 时 间 将 影 响 其 邻 域 内 部 件 。 （3 ） 如 果 S i 是 S-C 状 态 ， 表 示 元 胞 部 件 辐 射 出 去 ， 影 响 着 其 邻 域 内 的 部 件 ， 邻 域 内 部 件 将 会 受 到 激 发 。 （4 ） 如 果 S i 是 S-T 状 态 ， 表 示 元 胞 部 件 节 点 处 的 信 息 到 达 终 点 ， 信 息 流 在 此 部 件 内 结 束 流 动 。 定 义2.6 （SA 演 化 规 则 ） 软 件 体 系 结 构 对 应 的 扩 展 元 胞 自 动 机 模 型 为 A =(L d S N f C) ， 给 定 一 个 动 态 演 化 的 约 束 规 则 p:A A* ，A* 为 体 系 结 构 对 应 的 另 一 个 扩 展 的 元 胞 自 动 机 模 型 ， 则 称 p 为 一 个SA 演 化 规 则 。 运 用 演 化 规 则 ， 对 软 件 体 系 结 构 进 行 动 态 演 化 过 程 ， 可 以 表 示 为 原 有 的 扩 展 元 胞 自 动 机 模 型 A ， 通 过 给 定 的 动 态 演 化 的 约 束 规 则 p ， 寻 找 另 一 个 满 足 最 终 需 求 的 扩 展 元 胞 自 动 机 模 型 A* ， 当 删 除 、 添 加 、 更 换 构 件 或 连 接 件 时 ， 可 能 涉 及 到 扩 展 元 胞 自 动 机 模 型 中 元 素 的 改 变 和 调 整 。 在 特 定 的 状 态 环 境 下 ， 使 用 动 态 演 化 规 则 进 行SA 动 态 演 化 存 在 一 定 的 上 下 文 环 境 条 件 约 束 限 定 ， 下 面 主 要 讨 论 这 类 上 下 文 环 境 约 束 条 件 ， 称 为 扩 展 元 胞 自 动 机 动 态 演 化 应 用 约 束 条 件 。 为 刻 画 这 些 应 用 约 束 条 件 ， 为 此 下 面 进 行 了 如 下 的 分 类 定 义 。 定 义2.7 （ 演 化 控 制 约 束 条 件 ） 使 用 演 化 规 则 p 对 元 胞 自 动 机 模 型 进 行 演 化 时 ， 存 在 控 制 关 系 作 用 于 p ， 使 p 在 此 关 系 的 约 束 下 进 行 选 择 性 的 演 化 ， 那 么 称 为SA 演 化 控 制 约 束 条 件 。 当 演 化 规 则 p 作 用 于SA 元 胞 部 件 a 时 ， 首 先 根 据 元 胞 部 件 a 的 关 系 得 到 控 制 该 元 胞 部 件 的 元 胞 （ 或 元 胞 集 ）b 和 该 元 胞 部 件 的 所 控 制 元 胞 （ 或 元 胞 集 ）c ， 只 有 保 证 b 在 演 化 规 则 p 之 后 无 任 何 影 响 以 及 c 在 元 胞 a 运 用 演 化 规 则 p 时 允 许 相 应 演 化 ， 才 能 使 用 此 演 化 规 则 。 即 演 化 控 制 约 束 条 件 刻 画 的 是 演 化 规 则 之 前 所 控 制 元 胞 部 件 及 演 化 之 后 被 受 控 元 胞 部 件 必 须 满 足 的 条 件 。 控 制 关 系 一 般 有 控 制 相 关 的 双 方 存 在 ， 一 方 为 控 制 方 ， 另 一 方 为 受 控 方 ， 此 处 控 制 关 系 包 含 演 化 的 规 则 p 作 用 于 模 型 时 的 控 制 方 和 受 控 方 的 约 束 条 件 。 控 制 关 系 所 约 束 范 围 的 受 控 元 胞 部 件 同 时 进 行 相 应 的 演 化 ， 由 于 控 制 关 系 是 单 向 的 ， 还 应 保 持 控 制 部 件 在 此 情 况 下 不 产 生 任 何 相 应 的 影 响 。 为 了 简 单 直 观 ， 使 用 了 如 图2 的 方 式 表 示 控 制 约 束 条 件 下 的 演 化 ， 中 间 深 色 元 胞 a 在 p 下 进 行 演 化 ， 被 元 胞 a 控 制 的 其 他 元 胞 也 要 进 行 相 应 的 演 化 ， 同 时 黑 色 元 胞 b 和 c 在 受 到 元 胞 a 控 制 同 时 受 其 他 元 胞 的 控 制 ， 会 不 进 行 演 化 活 动 或 者 演 化 更 加 剧 烈 。 定 义2.8 （ 演 化 行 为 相 关 约 束 条 件 ） 基 于SA 扩 展 元 胞 自 动 机 模 型 进 行 动 态 演 化 的 元 胞 部 件 ， 它 的 行 为 相 关 构 件 集 为 RC coms ， 运 用 演 化 规 则 p 时 ， 由 行 为 相 关 演 化 传 递 性 可 知 RC coms 被 迫 使 进 行 相 应 的 动 态 演 化 ， 如 果 允 许 RC coms 随 着 而 进 行 动 态 演 化 ， 才 能 运 用 演 化 规 则 p ， 即 p 受 行 为 相 关 构 件 集 的 约 束 。 元 胞 部 件 进 行 动 态 演 化 时 ， 根 据 行 为 相 关 约 束 条 件 ， 应 先 得 出 其 行 为 相 关 构 件 集 RC coms ， 尽 量 缩 小 行 为 相 关 的 构 件 集 合 ， 即 行 为 不 相 关 的 构 件 不 应 被 包 含 在 内 ， 以 降 低 动 态 演 化 实 施 的 效 率 。 另 一 方 面 ， 演 化 规 则 p 只 有 在 行 为 相 关 的 传 递 性 约 束 条 件 下 正 确 地 进 行 。 定 义2.9 （ 动 态 演 化 应 用 约 束 条 件 ） 扩 展 元 胞 自 动 机 模 型 A ， 对 A 运 用 动 态 演 化 规 则 p:A A* 时 ， =( rc ) 称 为 p 的 一 个 应 用 约 束 条 件 ， 其 中 是 p 的 控 制 约 束 条 件 ， rc 是 p 的 行 为 相 关 约 束 条 件 ， 运 用 演 化 规 则 p 从 A 到 A* 的SA 动 态 演 化 满 足 应 用 条 件 =( rc ) ， 当 恒 满 足 时 ， 记 = rc ； 当 rc 恒 满 足 时 ， = 。 以 上 详 细 描 述 了 扩 展 元 胞 自 动 机 动 态 演 化 过 程 中 ， 使 用 动 态 演 化 规 则 p 时 存 在 的 上 下 文 环 境 约 束 条 件 ， 即 SA 动 态 演 化 应 用 约 束 条 件 。 相 应 地 ， 对 基 于 扩 展 元 胞 自 动 机 模 型 的 软 件 体 系 结 构 动 态 演 化 ， 运 用 动 态 演 化 规 则 p 的 过 程 可 描 述 为 ： 假 定 有 一 软 件 体 系 结 构 ， 它 相 图2 演 化 控 制 约 束 条 件 示 意 图 p 902015 ， 51 （9 ） 对 应 的 扩 展 元 胞 自 动 机 模 型 为 A ， 给 定 满 足 需 求 的 一 个 演 化 规 则 p:A A* ， =( rc ) 为 p 的 一 个 应 用 约 束 条 件 ， 那 么 运 用 p 进 行 动 态 演 化 的 步 骤 为 ： （1 ） 构 建 软 件 体 系 结 构 相 应 地 扩 展 元 胞 自 动 机 模 型 A ， 使 用 状 态 演 化 规 则 f 上 的 约 束 条 件 集C 对 元 胞 状 态 进 行 验 证 ， 若 不 满 足 C ， 则 不 能 运 用 此 动 态 演 化 p ， 否 则 进 入 下 一 步 ； （2 ） 检 验SA 动 态 演 化 应 用 约 束 条 件 是 否 满 足 ， 也 就 是 检 验 是 否 符 合 作 用 于 演 化 规 则 p 的 控 制 约 束 条 件 ， 以 及 运 用 p 时 演 化 的 行 为 相 关 约 束 条 件 rc 是 否 恒 满 足 ； （3 ） 若 动 态 演 化 应 用 约 束 条 件 =( rc ) 恒 成 立 ， 则 运 用 p 进 行 动 态 演 化 产 生 另 一SA 扩 展 元 胞 自 动 机 模 型 A* ， 即 由 原 始 的 扩 展 元 胞 自 动 机 模 型 A 演 化 到 新 的 扩 展 元 胞 自 动 机 模 型 A* 。 否 则 禁 止 运 用 p 进 行 动 态 演 化 。 3 案 例 研 究 下 面 使 用 一 个 基 于 网 上 银 行 系 统 作 为 案 例 ， 阐 述 和 讨 论 了 如 何 运 用 动 态 演 化 应 用 约 束 条 件 于 系 统 的 动 态 演 化 中 。 网 上 银 行 原 系 统 由 用 户 信 息 管 理 、 余 额 查 询 、 历 史 记 录 查 询 、 网 上 转 账 等 功 能 组 成 ； 对 于 转 账 功 能 ， 系 统 在 转 账 之 前 应 自 动 向 用 户 手 机 发 送 验 证 信 息 ， 验 证 成 功 之 后 才 可 进 行 转 账 ， 即 由 网 上 转 账 和 短 信 验 证 两 个 行 为 特 征 复 合 而 成 的 短 信 验 证 转 账 功 能 。 目 前 通 过 原 网 银 系 统 增 加 代 缴 电 费 功 能 模 块 实 现 网 上 银 行 与 电 力 收 费 的 整 合 ， 构 成 网 银 系 统 的 新 需 求 。 用 户 在 网 上 银 行 账 户 中 使 用 转 账 将 网 银 账 户 金 额 转 入 电 力 经 销 商 账 户 上 ， 涉 及 到 新 旧 功 能 模 块 的 关 联 。 网 银 系 统 在 总 体 结 构 上 包 含 客 户 、 服 务 代 理 、 服 务 器 三 类 元 胞 集 ， 客 户 登 录 通 过 服 务 代 理CS 向 服 务 器 组 发 出 服 务 活 动 请 求 ， 经 传 输 协 议 及 分 配 机 制 ， 服 务 器 组 S 中 的 某 服 务 器 S i 负 责 处 理 客 户 的 请 求 活 动 ， 返 回 信 息 再 由 服 务 代 理CS 传 给 客 户 。 服 务 器 组 中 任 一 服 务 器 由 公 共 元 胞 部 件 集 S 0 、 用 户 信 息 管 理 元 胞 部 件 集 S 1 、 余 额 和 历 史 记 录 查 询 元 胞 部 件 集 S 2 、 代 缴 电 费 元 胞 部 件 集 S 3 、 短 信 验 证 转 账 元 胞 部 件 集 S 4 五 部 分 组 成 。 其 中 代 缴 电 费 元 胞 部 件 集 S 3 属 于 新 增 元 胞 部 件 集 ， 需 要 通 过SA 扩 展 元 胞 自 动 机 模 型 的 动 态 演 化 得 到 。 最 终 形 成 的 网 上 银 行 系 统 软 件 体 系 结 构 的 扩 展 元 胞 自 动 机 模 型 中 ， 各 个 元 胞 部 件 集 的 形 象 化 图 形 表 示 ， 如 图3 所 示 。 其 中 ，c 1 c 2 c n 为 远 程 连 接 元 胞 ， 与 信 息 代 理 服 务 元 胞 间 结 构 上 存 在 相 关 ， 功 能 行 为 上 产 生 交 互 ， 最 下 层 的 图 示 表 示 一 服 务 器 中 服 务 功 能 软 件 在SA 上 的 元 胞 部 件 组 成 情 况 ， 它 与 信 息 代 理 服 务 元 胞 存 在 行 为 关 联 ， 其 内 部 各 个 元 胞 部 件 集 也 有 着 相 互 协 调 和 制 约 的 关 系 。 为 提 高 网 上 银 行 系 统 的 处 理 效 率 ， 系 统 可 根 据 用 户 负 载 情 况 动 态 调 整 在 线 服 务 器 的 数 量 ， 本 文 定 义 以 下 的 约 束 条 件 ： （1 ） 用 户 数 量 是 一 个 不 确 定 数 目 ， 可 以 任 意 多 ， 服 务 器 数 目 可 根 据 用 户 数 目 进 行 动 态 确 定 ， 最 大 数 目 为 2 ； （2 ） 服 务 代 理 运 行 系 统 的 数 目 始 终 保 持 为2 ； （3 ） 每 位 客 户 在 任 何 时 刻 都 只 能 连 接 到 其 中 一 台 服 务 器 上 ； （4 ） 两 台 服 务 器 在 功 能 上 具 有 等 效 的 关 系 。 3.1 系 统 中 演 化 应 用 约 束 分 析 通 过 构 建 网 上 银 行 系 统 的 扩 展 元 胞 自 动 机 模 型 ， 该 模 型 的 短 信 验 证 转 账 元 胞 部 件 集 S 4 包 含 转 账 元 胞 cella 、 验 证 元 胞 cellb 及 检 查 用 户 登 录 元 胞 等 等 元 胞 ， 代 缴 电 费 元 胞 集 是 在 原 网 银 系 统SA 的 扩 展 元 胞 自 动 机 模 型 中 将 要 新 添 加 的 元 胞 部 件 集 。 此 扩 展 元 胞 自 动 机 模 型 的 动 态 演 化 ， 涉 及 到 扩 展 元 胞 自 动 机 模 型 中 已 有 的 元 胞 部 件 集 与 新 添 加 元 胞 部 件 集 间 的 协 调 约 束 关 系 ， 同 时 新 添 加 的 元 胞 部 件 集 内 部 各 元 胞 间 也 存 在 着 上 面 分 析 的 应 用 约 束 条 件 。 下 面 着 重 分 析 代 缴 电 费 子 系 统 功 能 所 包 含 元 胞 集 的 相 关 约 束 条 件 。 代 缴 电 费 元 胞 部 件 集 S 3 将 实 现 用 户 账 上 的 金 额 转 入 电 力 营 销 厂 商 的 账 户 上 的 过 程 ， 涉 及 到 缴 费 预 处 理 、 短 信 验 证 、 转 账 及 缴 费 实 施 等 四 个 主 要 元 胞 集 ， 其 中 可 以 复 用 元 胞 部 件 集 S 4 中 的 相 应 的 转 账 元 胞 。 缴 费 预 处 理 元 胞 集 包 含 检 查 用 户 登 录 元 胞 c_log 和 系 统 安 全 扫 描 元 胞 c_saf ； 缴 费 实 施 元 胞 集 由 获 取 信 息 权 限 元 胞 cgt 、 查 看 缴 费 项 元 胞 clk 、 确 认 缴 费 元 胞 cok 、 生 成 缴 费 清 单 元 胞 ck 和 缴 费 记 录 归 档 元 胞 组 成 。 代 缴 电 费 元 胞 集 的 图 示 表 示 如 图4 所 示 。 缴 费 预 处 理 元 胞 集 是 缴 费 实 施 、 短 信 验 证 和 转 账3 元 胞 集 的 前 提 基 础 ， 控 制 着 以 下 过 程 中 的 元 胞 ，c_log 和 c_saf 元 胞 与 这3 类 元 胞 集 存 在 控 制 约 束 关 系 。 短 信 验 证 元 胞 c_vify 将 会 影 响 到 缴 费 实 施 元 胞 集 和 转 账 元 胞 图3 网 上 银 行 系 统 元 胞 部 件 示 意 图 c 1 c 2 c 3 c 4 c n CS 1 CS 2 S 0 S 1 S 2 S 3 S 4 图4 代 缴 电 费 元 胞 集 示 意 图 c_trs cok clk cgt c_saf c_log mk c_vify 刘 晓 斌 ， 杨 贯 中 ， 欧 阳 柳 波 ， 等 ： 软 件 体 系 结 构 动 态 演 化 的 元 胞 自 动 机 模 型 研 究 91Computer Engineering and Applications 计 算 机 工 程 与 应 用 2015 ， 51 （9 ） c_trs ， 即 保 持 行 为 相 关 的 关 系 ， 而 转 账 元 胞 c_trs 不 会 影 响 到 短 信 验 证 元 胞 c_vify ， 即 不 产 生 行 为 相 关 。 同 时 获 取 信 息 权 限 元 胞 cgt 控 制 着 短 信 验 证 元 胞 c_vify ， 短 信 验 证 元 胞 c_vify 控 制 着 查 看 缴 费 项 元 胞 clk ， 确 认 缴 费 元 胞 cok 控 制 着 转 账 元 胞 c_trs ， 转 账 元 胞 c_trs 控 制 着 生 成 缴 费 清 单 元 胞 mk 。 转 账 元 胞 c_trs 是 原 网 银 系 统 的 扩 展 元 胞 自 动 机 模 型 已 有 的 短 信 验 证 转 账 元 胞 部 件 集 S 4 所 包 含 的 元 胞 ， 以 上 分 析 存 在 着 与 代 缴 电 费 元 胞 集 中 mk 、cok 、c_vify 元 胞 之 间 的 约 束 关 系 。 代 缴 电 费 元 胞 集 S 3 中 c_log 、c_saf 元 胞 控 制 着 元 胞 集 S 3 内 余 下 操 作 关 联 的 元 胞 ， 属 于 元 胞 集 内 约 束 关 系 。 3.2 应 用 约 束 条 件 演 化 为 在SA 动 态 演 化 过 程 中 运 用 演 化 应 用 约 束 条 件 ， 本 文 定 义 了 以 下 约 束 条 件 ： （1 ） 对 上 述 描 述 的 代 缴 电 费 子 系 统 运 用 应 用 约 束 条 件 动 态 演 化 时 ， 由 于 c_log 和 c_saf 元 胞 与 余 下 三 类 元 胞 集 存 在 控 制 约 束 关 系 ， 故 对 c_log 和 c_saf 元 胞 进 行 修 改 时 ， 应 先 检 查 是 否 满 足 缴 费 转 账 和 短 信 验 证 过 程 中 的 安 全 性 要 求 及 用 户 账 户 合 理 性 问 题 ， 只 有 满 足 它 受 控 元 胞 部 件 的 约 束 条 件 ， 才 可 能 进 行 动 态 修 改 。 （2 ） 当 增 加 短 信 验 证 元 胞 c_vify 时 ， 应 考 虑 系 统 中 为 系 统 效 率 问 题 允 许 的 短 信 验 证 元 胞 数 量 ， 及 实 施 增 加 元 胞 后 对 控 制 约 束 关 系 的 查 看 缴 费 项 元 胞 clk 的 影 响 ， 是 否 可 以 进 行 此 项 操 作 等 等 。 另 一 方 面 对 短 信