组播 又 称 多 播 是 在 一 个 信 源 和 多个信宿之间实现一点对多点的网络通信方式 信 息包以组播树的形 式 向 各 信 宿 转 发与单播和广播方式相比组播具有 减 少 冗 余 流 量 节 约 网 络 带 宽 提高 服 务 质 量 等 优 点 组 播 路 由 技 术 是 计 算 机网络通信领域中多媒体信息传输的一个关键技术一些多媒体应用如 视 频 会 议远 程 教 育 等 需要组播技术的支持 在一个通信网络中可能会同时发生多个组播会 话 其 中 每 一 个 组 播 会 话 都 要 求 一棵组播树由于链路带宽容量的限制 这些组播树对某些链路产生竞 争 这 个 网 络 优 化 问 题 被 称 为 多 组播 路 由 问 题 或 群 组播 路 由 问 题 多 组 播路由问题的优化目标是求解一个在网络链路带宽容量约束下满足各个组播会话时延要求的具有最小代价的组播树集合 可 以 看 作 单 组 播 路 由 问 题 的 更 一般化形式它是一 个 比 单 组 播 路 由 问 题 更 加 复 杂 和困难的优化问题
　　目前研究如何解决多组播路由问题主要有 种思路一种是为所有源节点和目的节点构造一棵或多棵共享树即 有 核 树 技 术另一种是为每个组播会话分别构造一棵以源节点为根的 组 播 树由 于 在 源 节 点 比 较 多 时 将 导 致源节点与 连接的某些链路易产生拥塞和信息传送链路易 产 生 较 大 时 延而 且 的 确 定 也 是一个优化问题对 于 大 规 模 网 络 和 组 播 会 话 数 比 较多的情况求解最 优 共 享 树 是 非 常 困 难 的因 此本文以第 种思路研究求解多组播路由问题 对 于 多组播路由问题解 决 链 路 拥 塞 和 满 足 时 延 要 求 成 为求解问题的焦点 文献 提出了一种在每个组播需求的备选组播树集合中分别选出一棵组播树构成一个满足带宽要求的多组播树组合的方法 然 而该文献未阐述备选 组 播 树 的 产 生 方 法备 选 组 播 树 集合的质量和数量对求解质量和速度有较大影响文献 提出了基于 树的启发式算法和基于割集 的 种 启 发 式 算 法 前 者 是 先 分 别 求 出各个 组 播 会 话 的 树构 成 一 个 树 的 集 合 然后找出该集合超 出 带 宽 容 量 限 制 的 链 路 并 在 含 有该链路的所有树中不断地任意选出一棵去除该链路再用最短路径将树的两部分重新连接直到满足该链路的带宽容 量 限 制 而后者是从网络图中连续抽取一棵组播树 并 使 残 留 网 络 能 够 容 纳 尽 可 能 多的组播树不断地抽取 直到所需的组播树全部抽出文献 研究了 在 满 足 链 路 带 宽 约 束 情 况 下 的 组 播树带宽分配问题 提出了基于启发式的优化算法 上述文献主要针对链路拥塞问题而没有涉及组播树的时延约束问题文献 主要针对时延要求提出了一种启发式算法首先针对每个组播会话分别找出一棵最小时延组播树 构成一个组播树集合 如果该集合存在超出带宽容量的链路 则为非可行解执行下述操作即找出最拥塞的链路及含有该链路的组播树子集然后选择其中的一棵树 去除该链路后再用一条具有最小代价的路径将两部分连接形成一棵满足时延要求的新 树 重复进行直到组播树集合变为可行解文献 针 对 具 有 跳 数 约 束和带宽约束的多组播路由问题提出了一种基于分支截断 代 价 算 法该 算 法对于疏松网络在多数情况下可在合理时间内获得高质量的解但是对于密度较大的网络耗时比较严重由于基于确定性的启发式算法的时间复杂度比较高一般地对于大规模优化问题算法的求解质量不高且耗时严重
　　近 年 来基 于 仿 生 和 进 化 计 算 的 方 法 受 到 人 们的关注应用于求解单组播路由问题获得了较好的效果然而对于多组播路由问题相关的文献还比较少见文献 应用蚁群算法针对 的 各 项 约 束提出了一种求解 算 法 该算法采取在搜索的初级阶段蚂蚁主要选择时延约束和带宽较好的路由 在 中间阶段选择延时抖动约束满足程度高的路由 在 结束阶段对包丢失率约束的满足程度来更新对应路由上链路的信息量 当组播树中出现不满足跳数约束的路径时则以概 率 选 择 时 延延时抖动和成本等较高的链路进行替 换 该算法对于带宽容量充裕的情况具有较好的性 能 而对带宽竞争较为激烈的情况则难以找到最 优 解 文 献 分 别 提 出 了 基 于 遗传算法的两阶 段 求 解 方 法前 者 先 应 用 最短路径算法和启发式规则分别找出满足各组播会话时延要求的组播 树 集 合 然后利用遗传算法从各集合中挑选出满足带宽约束的组播树组合 而 后 者 则是在两个阶段均 采 用 遗 传 算 法 求 解 上 述 两 阶 段 算法存在的一个缺陷是难以确定合适的备选解集 若备选解集太小可能不含最优解或可行解 若 太 大 则增加搜索耗时粒子群优化算法是由 和 提出的一种 基 于 群体智能的优 化 算 法 具 有 收 敛 速 度 快 算 法 简 单等特点自基 本 提出后人们又提出了许多针对函数优化问题 的 改 进 算 法 使 的 寻 优马 炫 等多组播路由问题的粒子群优化算法性 能 得 到 大 幅 提 升 对 于 单 组 播 路 由 问 题 文 献采用节点序 列 的 编 码 方 法通过对点到点的路由采用一系列的 算 子 如 交 换插 入删 除 和 增 加 等实现了用 的求解文献 提出了 采 用 节 点 矩阵编 码 方 法 的 通 过 树 的 合 并 消 环 以 及 删 除无用的边 和 入 度 大 于 的 节 点 等 操 作 实 现 树 的 寻优上述文献对如何将基于函数优化 的 应 用 于树结构的优化做了开拓性的工作 目 前关 于 树 集合演化的 尚 未 见 到 报 道 本文提出一种基于树结构演化的多 组 播 路 由 粒 子 群 算 法 算 法 以 节 点连接关系表示一 棵 组 播 树 并将其作为粒子的一个分量通过设计新型的树结构演化的粒子飞行方法采用粒子的环状邻域结构并引入粒子视觉半径对粒子实施树结构 的 变 异 以及采用对粒子和粒子分量分别惩罚的策 略 处 理 非 可 行 解 等 方 法 实 现 了 具有带宽和时延约束的多组播路由问题求解 通 过 在多个网络拓扑上的数值实验结果验证了本文算法的有效性多组播路由问题给定一个无向赋权图 和 分 别表示 中所有节点的 集 合 和 所 有 边 的 集 合边 的 代价函数表示为 为边 的 代 价中存在一个源节点集合 和 相应的 个 目 的 节 点 集 合以 源 节 点 为根的 组 播 树 其 代价为边的时延函数表示为 为 数据包经过边 时 产 生 的 时 延 边的带宽函数为为 边 的 带 宽 容 量 如 果表示在树 中从源节 点 到 一 个 目 的 节 点 的路径则该路径的总时延为设组播 树 传 送 的 信 息 包 所 占 带 宽 为 则组播树 必须满足如下约束条件其中 表示时延约束多组播路由问题可描述为棵组播树构成 一 个 树 的 集 合确定一个使 最小的组播树集 即式 中 除了满足式 之外还要满足下述约束设同时经过 中边 的信息 包 有 个 表 示给定的带宽约束 则多组播路由 算法粒子群算法简介粒子群算法的基本原理是粒子通过向自身经验和群体经验不断学习实现在解空间的寻优 粒 子 在解空间中追踪两 个 极 值 即粒子本身迄今找到的最优解 和群 体 中 迄 今 找 到 的 最 优 解 假 设 粒 子群中第 个 粒 子 在 维 空 间 中 的 位 置 为飞行速度为 其 经历过的最好位置为 所 有 粒 子经历过的最好 位 置 为 每 一代粒子按式 和式 更新速度和位置式 被 广 泛 应 用 于 许 多 算 法 其 中表示第 个粒子第 维上的速度 为 惯 性 权 重是调节粒子飞向自身所经历最好位置方向的步长系数 是调节粒子向全局最好位置飞行的步长系数 为 之间均匀分布的随机数粒子编码和树的生成标准的 是针对连续函数优化 问 题 的 其 粒子编码的每一维 分 量 为 实 数粒子在解空间中的飞行通过式 和式 的数值运算实现 然而对于多组 播 路 由 问 题 由 于 解 是 一 个 组 播 树 集 合 标 准的 粒 子 编 码 与 飞 行 方 法 难 以 直 接 应 用 因 此如何设计新的粒子编码方式以及粒子飞行方法是需要解决的首要问题多组播路由问题的潜在解是由 个组播树构成的一个组播树集合 因此可将这 个组播树按序列表示成一个粒 子 记 为 其 中的 分 量 称 为 多 组 播 的一个成员组播树 这 样粒子编码的主要问题是如何表示成员组播树目前对一棵树的常用编码方法有 节点 矩 阵 表 示 法即将网络中节点赋以 或 分 别 表 示 连 接 节 点 和计算机研究与发展非连接节点该方法占用内存比较大 路径集合表示法 该方法编码比较复 杂 易 产 生 环 路 二 叉树表示法 该方法占用内存较大且算法复杂 文献 提出了一种从源节点建立网络搜索树和基于搜索树生成编码 的 方 法 对于大规模网络该方法建立搜索树耗时严重 针对已有方法的优缺点 本文以节点连接关系直 接 表 示 一 棵 树树的生成从目的节点向源节点回溯 产生一个分枝分枝的集合构成一棵树该方法具有 编 码 长 度 可 变占 用 内 存 少 直 观等优点树的生成步骤如下设定一个树的空集 将源节 点 添 加到选择一个目的节 点 目 的 节 点 到 树 枝并将其作为当前节点 从目 的 节 点 中删除从当前 节 点 的 邻 居 节 点 中 随 机 选 取 一 个 未添加到 的节点添加到 更 新 当前节点判断当前 节 点 是 否 属 于 若 是 则 将添加到 转步骤 否则转步骤若目的节点为空则 组 播 树 已 生 成 结 束否则返回步骤评价函数由于多组播路由问题描述中存在带宽和时延两个约束条件因而会导致产生非可行解的粒子粒子的评价 函 数 包 括 可 行 解 粒 子 和 非 可 行 解 粒 子 如式 所示对非可行解粒子 采 取 惩 罚 策 略 一 个 粒子可能存在两种超出约束的情况 成 员 组 播 树 超出式 的 时 延 约 束 多 个 组 播 树 由 于 共 享 一 条或几条链路导致超出式 的带宽约束当某个成员组播树超出时延导致整个粒子为非可行解 只 对 超出时延的成员组 播 树 进 行 惩 罚多棵组播树共享低代价链路造成超出限定带宽时则对粒子惩罚 粒 子的评价函数设计为可行解非可行解式中 为成员组播树 时 延 为 时 延 约 束 值 为时延惩罚因子 为带宽惩罚因子 表示粒 子中不满足带宽约束的链路数粒子飞行由于粒子的每一个分量采用树形结构 因 而 如何通过树的演化是实现粒子寻优飞行的关键 本 文依据 的思想采用将个体极值树 社 会 极 值 树 和当前树的部分结构组合成一棵新树的思路 方 法 如下设粒子 的第 维分量 其个体极值的分 量为 和全局极值分量为 它 们 都 是 一 棵 完 整 的组播树 将 和 中 不 同 于 的结构分别截取出来添加到 的树形结构上 此 时 产 生 一 个 有 环的结构图对这个图中的环路随机消环 可重新得到一棵完整的树记 为 其 结 构 具 有 和的部分结构 这一过程可表示为⊕ ⊕其中 和 表 示 系 数 和⊕分别表示截取和添加运算实际上式 与 式 具有相同的性质 说明如下由式 可得令则式 表明粒子的位置更新信息分别以不同比例来自于个体 极 值 信 息 社会极值信息和粒子当前位置信息 显然式 的树 结 构 粒 子 飞 行 方 法 与其具有相同 的 性 质 文 献 分析并证明了式的 的收敛性故式 的 也是收敛的粒子变异为 了 使 粒 子 能 够 产 生 具 有 新 的 节 点 和 边 的 树本文借鉴遗传算法的变异原理在算法中设计了树结构的变异操作变异操作可以看作是当前粒子向解空间中的某个随机生成的粒子的一次飞行 因 此可采用 节中粒子飞行的方法实现变异操作设随机 生 成 一 个 粒 子 将 其 第 维 分 量中不同于 的树形结构截取出来 添 加 到 的 树形结构上随机消环后得到 变异过程记为⊕马 炫 等多组播路由问题的粒子群优化算法本 文 算 法 中 以 变 异 率 在 粒 子 群 中 选 取 待变异粒子邻域环状结构为了改善由于选 取 全 局 极 值 为 社 会 学 习 对象导致算法 易 早 熟 收 敛 的 问 题 等 人 提 出了几种粒子群的邻域模 型 具 有 更 好 的 局 部 搜 索性能其中的环形 结 构 由 于 结 构 简 单容 易 实 现 常被采用但是这种结构存在收敛过慢的缺点本 文在环状邻域结构 中 引 入 粒 子 的 视 觉 半 径 以 兼 顾 全局社会结构收敛的快速性和邻域结构搜索的细致性给每 个 粒 子 设 置 一 个 视 觉 半 径 以 邻 域 内 所有粒子经历过的最 佳 位 置 作为粒子社会学习的对象这样 邻域环状结构的粒子飞行方式为⊕ ⊕由于粒子具 有 视 觉 半 径 当一个粒子要与邻域之外的粒子实现 信 息 交 流 时至少需要经过一个粒子作为媒介这样媒介粒子就会把自身的部分结构信息融入树的演 化 过 程 中 增强了粒子的局部学习能力多组播路由 算法初 始 化 粒 子 种 群 随 机 生 成 种 群 中 的 每 个粒子根据式 计算每个粒子的评价值对于每个粒子找出其 邻 域 内 各 粒 子 所 经 历过的最佳位置 根据式 执行粒子飞行操作以变异率 从粒子种群中选取粒子按照式进行变异将每个粒子与其经历过的最好位置 比较如果优于 则以其更新将各个 粒 子 的 最 好 位 置 与 整 个 种 群 经 历 的最佳位置 进 行 比 较 如 果 优 于 则 更 新 的索引号如果满足终止条件则输出 算 法 终 止 否则返回步骤算法的终止条件取为预先设置的迭代次数仿真实验实验 平 台 为算 法 采 用 编 程实现算例比较由于求解多组播路由问题的文献很少 而 且 已有的文献中没有提供网络拓扑 为此采用文献中的网络拓扑如图 所 示这是一个随机生成的具有 个节点 条 边 的 网 络 图中的每条边具有个属性代价带宽时延图 网 络 拓 扑取 个组播每 个 组 播 均 取 个 目 的 节 点 设每个组播传送的数据包所占带宽分别为取带宽约束 时 延约束 为了验证本文算法 的 有 效 性计算机研究与发展我们与没有粒子视觉半径 邻 域 学 习 机 制 的称为 和文献 的 两 阶 段 遗 传 算 法进行比较参数设置如下 粒子数 变异率时 延 罚 因 子 带 宽 罚 因 子 迭 代数 视觉 半 径 其 余 参 数 同第 阶段种 群 规 模 交 叉 率 变 异率 进化代 数 候 选 解 集 规 模 第 阶 段种群规模 交 叉 率 变 异 率 进 化 代 数上述参数值是多次实验中的最好经验值求解结果如表 所示计算表 中 组 播 树 集 的 总 代 价得出 为 为 为可以看 出 的 解 优 于 和 的 解 当没 有 变 异 操 作 时 搜 索 到 的 最 优 解 为 远远大于 表明了文中变异操 作 方 法 的 有 效 性种算法的计算耗时 为 为为 稍稍大于 这是由于比 多了 邻域环状结构的邻域搜索表 种算法的求解结果为了考察算法收敛性的稳定性将 和各运行 次分 别 得 到 平 均 进 化 曲 线 如 图所 示图 中 的 点 线 表 示 搜索到的最优解可 以 看 出 的 收 敛 性 和 解 的 质 量 明 显 优于 和 分别计算 种算法 次搜索结果的标准 差 为 为为 的方差远远小于其他的两种算法表明其收敛稳定性较好马 炫 等多组播路由问题的粒子群优化算法图 平 均 进 化 曲 线不同网络规模我们采 用 方 法 随 机 生 成 平 均 节 点 度为 节点数 分 别 为 和 的两种网络拓扑 考察算法在不同规模网络上的性能 对 表 的 前个组播需求分别运行算法 次其平均进化曲线如图 和图 所示取表 的前 组前 组组共构成 种多组播需求求得的最好解如图 和图 所示从图中结果可以看出 的 平 均 进 化曲线和最优解都明显优于视觉半径取表 中的前 个组播构成多组播路由问题来考察 视 觉 半 径 取 不 同 值 时 的 算 法 性 能 分 别 运 行算法 次其平均收敛曲线如图 所 示可 以 看 出当 时算法收敛速度随视觉半径 的 增 大 而 提高 时的收敛速度 明 显 快 于 为 和 时 的 收敛速度这是因为 的基本环状邻域模型收敛比 较 慢而 视 觉 半 径 越 小 邻 域 环 状 模 型 就 越 趋近于基本环状邻域模型 当视觉半径取 时算法收敛速度 最 慢当 时算 法 收 敛 精 度 随 着 视 觉 半径 的增大而下 降 时的收敛精度明显优于取 和 这是因为视觉 半 径 越 大 粒 子 的 社 会 学习就越趋近于全局学习 则算法越容易早熟收敛计算机研究与发展图 具 有 不 同 值 的 进 化 曲 线通过 邻域学 习 机 制 可以较好地解决粒子群算法中全局学习收敛速度快但易陷入局部解 环 状邻域模型搜索细致但收敛速度慢的问题
　　结束语
　　本文根据 的 基 本 原 理 提 出 了 一 种 求 解 时延和带宽约束的多组播路由优化问题的 算 法算法中采用基于树结构演化的粒子飞行方法实现了树集合的寻优在 粒 子 群 的 环 状 社 会 结 构 中 引 入 粒子视觉半径控制机制 增强了粒子的邻域学习能力可以提高粒子的全局探索和局部开发性能 对 粒 子实施的树结构变异提高了算法跳出局部解的可能性对于不满足约 束 条 件 的 粒 子 采 取 了 对 粒 子 和 粒子分量分别惩罚的策略 数值实验结果表明 本文提出的算法可以有效求解多组播路由问题的优化解收敛速度快且稳定性好
    参 考 文 献张 琨 王 珩 刘 凤 玉 一种时延约束的多共享组播树构造算法 南京理工大学学报秦 玲 姚 远 陈 崚 等一种求解成组多播路由问题新型优化 算 法 南 京 航 空 航 天 大 学 学 报潘 达 儒 杜 明 辉 基于粒子群优化的 组 播 路 由 算 法计算机工程与应用马 炫 等多组播路由问题的粒子群优化算法王 新 红 王 光 兴 基于遗传算法的时延受限代价最小组播路 由 选 择 方 法 通 信 学 报范 一 鸣 余 建 军 方 智 敏 融合小生境机制的 多 播 路由遗传模拟退火算法 通 信 学 报杨 云 徐 永 红 李 千 目 等一 种 路由多目标遗传算法通 信 学 报