小 型 微 型 计 算 机 系 统
Ｊｏｕｒｎａｌ ｏｆ Ｃｈｉｎｅｓｅ Ｃｏｍｐｕｔｅｒ Ｓｙｓｔｅｍｓ
２０１０年 １月 第 １期
Ｖｏ１．３１ Ｎｏ．１ ２０１０
Ａｄ Ｈｏｃ网络 中基于捕食逃逸 ＰＳＯ 的 ＱｏＳ多播路 由算法
姚金涛 ，孔宇彦 ，杨 波
（华南农业 大学 信息学院，广东 广州 ５１０６４２）
（南海东软信息技术学院 ，广东 佛山 ５２８２２５）
Ｅ－ｍａｉｌ：ｊｕｓｔｉｌｌ—ｙｊｔ＠ １６３．ｔｏｍ
摘 要 ：求解两个或 多个限制参数 的 ＱｏＳ多播路 由问题 ，已被证 明为ＮＰ—ｃｏｍｐｌｅｔｅ问题 ，而随着 Ａｄ ｈｏｃ网络 中多媒体和 实时应
用需求的不断提 升 ，有效的 ＱｏＳ多播路 由算法成为重要研 究内容．针对 Ａｄ ｈｏｃ网络 的动态性和 ＱｏＳ参数 的 多样性 ，给 出一种
解决该问题的捕食逃逸 ＰＳＯ方法，算法通过对 ＭＡＯＤＶ路 由发现过程发现 的 ＱｏＳ有效路径进行编码和 寻优 处理，借助 于捕食
逃选行为使算法能够以较 大概率获取全局最优 ＱｏＳ多播 路 由．在 ＮＳ２平 台上 的仿真 结果表 明 了捕食 逃逸 ＰＳＯ解 决 Ａｄ ｈｏｃ网
络 ＱｏＳ多播路 由 问题 的 可 胜任 性 ．
关 键 词 ：粒子群优化算法 ；捕食逃逸 ；ＭＡＮＥＴ；ＱｏＳ多播 路由
中图分类号 ：ＴＰｌ８ 文献标识码 ：Ａ 文 章 编 号 ：１０００．１２２０（２０１０）Ｏ１－００６２－０５
ＱｏＳ Ｍｕｌｔｉｃａｓｔ Ｒｏｕｔｉｎｇ Ａｌｇｏｒｉｔｈｍ Ｂａｓｅｄ ｏｎ Ｐｒｅｄａｔｏｒｙ Ｅｓｃａｐｉｎｇ ＰＳＯ ｉｎ Ａｄ Ｈｏｃ Ｎｅｔｗｏｒｋｓ
ＹＡＯ Ｊｉｎ—ｔａｏ。
，
ＫＯＮＧ Ｙｕ—ｙａｎ 。ＹＡＮＧ Ｂｏ。
（Ｃｏｌｌｅｇｅ ｏｆｌｎｆｏｒｍａｔｉｃｓ．Ｓｏｕｔｈ ＣｈｉｎａＡｇｒｉｃｕｌｔｕｒａｌ Ｕｎｉｖｅｒｓｉｔｙ。Ｇｕａｎｇｚｔ￣ｕ ５１０６４２，Ｃｈｉｎａ）
（ＮａｎｈａｉＮｅｕｓｏｆｔＩｎｓｔｉｔｕｔｅ ｏｙＩｎｆｏｒｍａｔｉｏｎ。Ｆｏｓｈａｎ ５２８２２５．Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｔｏ ｓｏｌｖｅ ＱｏＳ—ｂａｓｅｄ Ｍｕｌｔｉｃａｓｔ ｒｏｕｔｉｎｇ ｐｒｏｂｌｅｍ ｗｉｔｈ ｍｕｌｔｉｐｌｅ ｃｏｎｔｒａｉｎｔｓ ｈａｓ ｂｅｅｎ ｐｒｏｖｅｄ ａｓ ＮＰ ｃｏｍｐｌｅｔｅ ｐｒｏｂｌｅｍ．Ｗ ｉｍ ｔｈｅ
ｉｎｃｒｅａｓｉｎｇ ｏｆ ｍｕｌｔｉｍｅｄｉａ ａｎｄ ｒｅａｌ－ｔｉｍｅ ａｐｐｌｉｃａｔｉｏｎｓ ｒｅｑｕｉｒｅｍｅｎｔ ｉｎ Ａｄ ｈｏｃ ｎｅｔｗｏｒｋｓ－ｅｆｆｅｃｔｉｖｅ ＱｏＳ—ｂａｓｅｄ Ｍｕｌｔｉｃａｓｔ ｍｕｔｉｎｇ ａｌｇｏｒｉｌｍｓ
ｂｅｃｏｍｅ ｉｍｐｏｒｔａｎｔ ｒｅｓｅａｒｃｈ ｉｓｓｕｅｓ．Ｂｅｃａｕｓｅ ｏｆ Ａｄ ｈｏｃ ｎｅｔｗｏｒｋｓ Ｓ ｄｙｎａｍｉｃｓ ａｎｄ ＱｏＳ ｐａｒａｍｅｔｅｒｓ ｓ ｄｉｖｅｒｓｉｔｙ。ｔｈｉｓ ｐａｐｅｒ ｐｒｏｐｏｓｅｓ ａ
ＱｏＳ ｍｕｌｔｉｃａｓｔ ｒｏｕｔｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｐｒｅｄａｔｏｒｙ ｅｓｃａｐｉｎｇ ＰＳＯ，ｗｈｉｃｈ ｅｎｃｏｄｅｓ ｔｈｅ ｅｆｆｅｃｔｉｖｅ ＱｏＳ ｍｕｌｔｉｃａｓｔ ｐａｔｈｓ ｆｏｕｎｄ ｏｕｔ ｂｙ
ＭＡＯＤＶ Ｓ ｒｏｕｔｅｓ—ｆｉｎｄｉｎｇ ｐｒｏｃｅｄｕｒｅ ａｎｄ ｔｈｅｎ ｏｐｄｍｉｚｅｓ ＱｏＳ ｍｕｌｔｉｃａｓｔ ｔｒｅｅ．Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｏｎ ＮＳ２ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏ－
ｒｉｔｈｍ ｉｓ ｃｏｍｐｅｔｉｔｉｖｅ ｏｎ ＱｏＳ—ｂａｓｅｄ Ｍｕｌｔｉｃａｓｔ ｍｕｔｉｎｇ ｐｒｏｂｌｅｍ ｉｎ Ａｄ ｈｏｃ ｎｅｔｗｏｒｋｓ．
Ｋｅｙ ｗｏｒｄｓ：ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ；ｐｒｅｄａｔｏｒｙ ｅｓｃａｐｉｎｇ；ＭＡＮＥＴ；ＱｏＳ ｍｕｌｔｉｃａｓｔ ｍｕｔｉｎｇ
１ 引 言
移动 Ａｄ ｈｏｃ网络 （Ｍｏｂｉｌｅ Ａｄ ｈｏｃ Ｎｅｔｗｏｒｋｓ，简称 ＭＡ－
ＮＥＴ）是一种特殊 的通 信网络 ，网络 中所有节 点的地位平 等 ，
作为 自组织和无 中心的网络形式 ，Ａｄ Ｈｏｃ网络克服了传统移
动通信 网络需要通信基础设 施的 限制 ，可用于临时 和不可预
测 的场 合 ，在军 事 和 民用方 面具有 良好 的应 用前景 ” Ｊ．目
前 ，Ａｄ Ｈｏｃ网络 的研究 已取 得 了一 定 的成果 ，并有越 来越多
的研究者开始对相关 内容进行研究．随着现场视频会议 、视频
点播等实时多媒体多播 通信需求 的增 长 ，要求路 由必须具有
严格的 ＱｏＳ保证 ，主要包 括带宽、时延 、时延差别 、代价 、丢包
率等 ，而实现 ＱｏＳ保 证的关键 之一 就是多播路 由机制 ，其 最
主要 目标就是 能够对 网络资源进行有效分配以找到满足不同
ＱｏＳ要求下的最佳路 由方案 ．然而 ，基于多个不相关可加度量
的 ＱｏＳ组播路 由问题 已被证 明为 ＮＰ—ｃｏｍｐｌｅｔｅ问题” ，近 年
来 ，研 究者对此类问题做 了大量 的研 究工作 ，提 出了多种解 决
方法 ，如 基 于 模 拟 退 火 、禁 忌 搜 索 、神 经 网络 和 遗 传 算 法
等 。 路 由策略．目前 ，一类新兴的模拟生 物群体行 为的集群
智能算法被引入到此类优化 问题 中 ，如蚁 群算法 和粒 子群优
化（Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ，简称 ＰＳＯ）算 法 等．ＰＳＯ算
法最初 由 Ｋｅｎｎｅｄｙ和 Ｅｂｅｒｈａｒｔ提出 ，是一种基 于迭代 的优化
方法 ，因其概念简单、实现容易，而引起学术 界 的广泛重视 ，
已被广泛应用于多 目标优化 、模式识 别、信 号处 理和决策支持
等领域Ｌ９ ．与遗传算法 比较 ，ＰＳＯ没有 如交叉 和变异 等遗
传操作 ，而是通过所 有粒子在解空间追 随最优粒子进行搜 索 ；
同时 ，信息共享机制也不 同，在遗传算法 中 ，染 色体 互相共享
信息 ，整个种群 比较均 匀的 向最优区域移动 ，而在 ＰＳＯ中，只
有 ｇＢｅｓｔ把信息单 向流 动给其它粒 子 ，即整个 搜索更 新是跟
随当前最优解 的过程 ，因此在大多数情况下 ，所有粒子则可能
更快的收敛于最优解．通过比较发现 ，ＰＳＯ算法与 Ａｄ Ｈｏｃ网
络路 由算法在应用环境和性能要求 上有着惊人 相似之处．借
鉴 ＰＳＯ算法 的思想 ，将路 由信息分 布于网络 当中，利用适 应
度函数来判定路 由方 向 ，这 种随机统计 的算 法在结构 多变的
场合下更能获得较高的综合效能 ，并将 可望突破传统 Ａｄ Ｈｏｃ
收稿 日期：２００８－０８－１９ 基金项 目：国家 自然科学基金项 目（６０６７３０７７；６０７７３１７５）资助 ；现代通信国家重点实验室基金（９１４０Ｃ１１０８０２０９０６）资
助． 作者简介 ：姚金涛．男 ，１９７８年生 ，博士研究生 ，讲师 ，研究方向为进化计算 、通信与信息安全 ；孔字彦，女 ，１９７８年生 ，硕士 ，讲师 ，研究方 向
为数据挖掘、数据库技术 ；杨 波 。男，１９６３年生 ，博士，教授 ，博士生导师，研究方向为信任管理 ，信息安全．
资源评论
