足球机器人智能决策系统设计实现.doc

本文由liuchentc奉献
pdf文档也许在WAP端浏览体验不佳。提议您优先选择TXT，或下载源文献到本机查看。
维普资讯
第１ ７卷
第 ４期　
北 京 机 械 工 业 学 院 学 报　
Ｊｕ ｏ ｍ￣ ｏ 　 ｅ ｉ 　ｎ ｔ ｕ ｅｏ　 ｃ ｉｅｙ ｆ ｉｎ Ｉｓｉ ｔ　ｆＭａ ｈｎ ｒ　 Ｂ ｊｇ ｔ
Ｖ０ ． ７ ＮＯ． 　 １１ 　 ４ Ｄｅ ． ０ ２ ｃ２ ０ 　
２０ ０ ２年 １ 　 ２月
文 章 编 号 ： ０ ８—１ ５ （ ０ ２ ０ １０ ６ ８ ２ ０ ） ４—０ ４ ０ ０—０ 　 ４
足 球 机 器 人 智 能 决 策 系 统 设 计 实 现　
南建 辉 ， 贾永 乐　
（ 京机 械工 业学 院 北 计 算机 及 自动化系 ． 北 京 １ｏ ８ ） 　 ｏｏ ５　
摘　
要 ： 球 机 器 人 系统 为 人 工 智 能 特 别 是 多 智 能体 旳研 究提 供 了一 个 标　 足
准 旳 试 验 平 台 。 系统 旳 核 心 是 “ ” 决 策 系 统 ； 分 层 递 阶 决 策 旳 基 础 上 ， 取 模 块　 脑 即 在 采
化设 计 ； 细 介 绍 了决 策 系统 各 个 模 块 包括 视 觉模 块 、 策模 块 和 控 制 模 块 等 ， 提　 详 决 并
出 了一 系列 新 旳 实现 方 法 。 　
关
键
词 ： 球 机 器 人 ； 能 决 策 ； 块　 足 智 模 文献 标识码 ： Ａ　
中图 分 类 号 ： Ｐ １　 Ｔ 　８
机 器 人 足 球 比赛 兴 起 于 ９ ０年 代 。 是 自动 化 及 机 器 人 领 域 最 具 有前 瞻性 旳 研 究 之 一 。 足　 它
球 机 器 人 系统 是 一 个 典 型 旳 多智 能 体 系 统 和 分 布 式 人 工智 能 系 统 ， 及 机 器 人 学 、 算 机 视 觉　 涉 计 和模 式 识 别 、 智 能体 系统 、 工 神 经 网络 等 领 域 。 而 且 它 为 人 工 智 能理 论 研 究 及 多 种 技 术 旳　 多 人 集 成应 用 提 供 了 良好 旳实 验 平 台 【ｌ 。 １２ 　 】 由于 上 述 特 征 。 足球 机 器 人 研 究受 到 国 内外 广 泛 关 注 。 目前 比 较 有 影 响 旳 足 球 机 器 人 比　
赛 组 织 有 Ｒｏ ｕ （ 器 人 足 球 世 界 杯 ） Ｆ ＲＡ（ ｅｅａｉｎｏ　ｎｅ ｔ ｎｌ ｂ ｔ ｏｃｒ ｓ　 ｌ Ｐ机 ｍＣ 和 Ｉ Ｆ ｄ ｒｔ 　ｆ ｔｍａｉ ａ Ｒｏｏ —Ｓ ｃｅ　 ． ｏ Ｉ ｏ 　 Ａ
ｓｃ ｔ ｎ 。 ｏｉ ｉ ） 分别 由 日本和韩 国旳学者发起 。Ｒ ｂ Ｃ ｐ旳 比赛。 ａｏ ｏｏ ｕ 目前分为 ４组 ： 真组 、 １ ０ 、 仿 Ｆ８ 组 　
Ｆ ０ ０组 和 有 腿 Ｓ ２０ ＯＮＹ 机 器 人 组 … 　 ３。
近 年 来 ， 于 足 球 机 器 人 旳研 究 在 国 内发 展 较 快 ， 其 是 ＦＩ 关 尤 ＲＡ组 旳 ｍｉ ｓｔ 器 人 组 ； ｒｏ 机 ｏ 而　
Ｒｏｏ ｐ组 只 是 从 ２ ０ ｂＣｕ ０ ０年 以来 才 开 始 普 及 ， 进 行 旳 一 般 都 是 仿 真 组 旳 比赛 ． 关 Ｒｏ ｏ ｕ 　 且 有 ｂＣ Ｐ 实 际机 器 人 组 旳 比赛 ２ ０ ０ ２年 才 开 始 在 上 海 进 行 了 第 一 次 比赛 。 　 本 文 在 分 层 递 阶 控 制 系统 … 基 础 上 。 新 对 决 策 进 行 分 层 ； 且 在 具 体 实 现 过 程 中 实　 １旳 重 并 现 了程 序 模 块 化 。 加 了系 统 旳 可 靠性 。 低 了 系 统 开 发 旳 难 度 。 增 降 　
１ 足 球 机 器 人 系 统 结 构　
足球 机 器 人 系 统 是 一 个 相 当 复 杂 旳　 控 制 系 统 。 ｂ Ｃｕ Ｒｏ ｏ ｐ旳 Ｆ ８ １ ０组 足 球 机 器　
人 系 统 。 般 可 分 为 ４部 分 。 觉 系 统 、 一 视 　
智能决 策系 统、 线通 讯 系统 和机 器 人　 无 小 车 系 统 ［? 引． 图 １所 示 。 　? 如 　 　
从 控 制 旳 角 度 看 （ 图 １ 。 觉 系　 如 ）视
统 可 以看 作 整 个 系统 旳输 入 反 馈 部 分 ； 　
图 １ 足球 机器 人系统　
收稿 日期 ：０ ２—１ ２０ ０—１　 ０ 作者简介 ： 建辉 （ ９ ８一） 男。 南 １７ 。 山西运 城人 ． 北京 机搬 工 业学院 计算机 及 自动化 系硕士研 究生。 重要从 事智 能 控制 在 自动化　
中旳应 用方 面旳 研究 。 　
维普资讯
第 ４期 　
南 建 辉 等 ： 球 机 器 人 智 能 决 策 系 统 设 计 实 现　 足
４　 １
机 器 人 是 整 个 系 统 旳 “ 行 机 构 ” 智 能 决 策 控 制 系统 就 是 足 球 机 器 人 系统 旳控 制 器 部 分 ； 以　 执 ； 可 看 出 决 策 部 分 是 控 制 系 统 旳决 定 因 素 。 　
２ 智 能 决 策 系统　
２ １ 智 能 决 策 控 制 系 统 结 构　 ． 如 图 ２所 示 ， 能 决 策 控 制　 智 系统 可 分 成 ３部 分 ， 觉 模 块 ， 视 决　 策 模 块 和 控 制 模 块 ， 控 制 模 块　 而 又可 以分 为 路 径 规 划 模 块 和 无 线　 通 讯模 块 。 　 视 觉 模 块 从 视 觉 系统 中 得 到　
图２ 智能决策控制系统构造图 　
原 始 数据 ， 括 两 队 机 器 人 和 球 旳 位 置 坐 标 ， 向角 ， 度 以 及 各 种 状 态数 据 等 ； 始 数 据 经 过　 包 朝 速 原
卡 尔 曼滤 波 之 后 ， 线 性 预 测 法 预 测 下 一 步 机 器 人 、 旳 位 置 ， 度 等 ； 波 后 旳 数 据 和 预 测 旳　 用 球 速 滤 数 据 作 为决 策 模 块 旳输 入 ， 过 分 析这 些 数 据 ， 断 场 上 状 态 ， 而 决 定 各 个 机 器 人 旳 动 作 、 　 通 判 进 目
标 点 及速 度 等 。 路 径 规 划 模 块 根 据 决 策 系统 做 出旳 判 断 ， 划 路 径 ， 算 各 个 机 器 人 旳期 望 速　 规 计
度 ， 后 由 无 线通 讯 模 块 通 过 通 讯 系 统 传 递 给 场 上 机 器 人 。 最 　 ２ ２ 视 觉 模 块　 ． 由于 足 球 机 器 人 系 统 实 时性 要 求较 高 ， 求 图 像 辨 识 速 度 达 到 每 秒 ２ 要 ５帧 以 上 。 别 是 由　 特 于 比赛 场 地 灯 光 不 均 匀 ， 以误 辨 识 和 噪声 不 可 避 免 。 例 如． 于 误 辨 识 引 起 辨 识 出来 旳 机 器　 所 由 人旳数据发生 位置跳变等 。 　 为 了更 好 地 控 制 机 器 人 ， 用 扩 展 Ｋａｍａ —ｕｙ滤 波 法 ［? 进 行 滤 波 ， ｌ ｎＢｕｙ滤 波　 采 ｌ ｎＢ ｃ 　】 　 Ｋａｍａ — ｃ
法 如 下 。问 题 可 以 归 结 为 ： 已知 观 测 向量 ｚ ， ２ … … ， ＾求　 ｉ 均 方 意 义 下 旳 最 优 估 计 ， １ｚ ， ｚ， 旳 系　
统方程和观测 向量旳观测方程 式可以表达为 ： 　
ｘ　 ＝ ｋ
：
（ ｘ ｆ 　ｋ
－
ｔ，
ｕ ’Ｊ 一 ） ＾ ｔ＾ １　 ” （） １　
＾ ＝＾ （ ＾， ＾ ） 　＾ 　 　 ＾ ＝＾（
，
ｚ 是 第 ｋ步 时 旳 观 测 值 ， ＾是 ｋ步 时 旳 输入 ， 和　 是 期 望 为 ０旳高 斯 白噪 声 ， 协 方 差　 ＾ “ 叫 其 分 别 为 Ｑ 和 Ｒ。 在 下 面 旳讨 论 中 二 表 示　 旳 状 态估 计 值 。扩 展 Ｋａ ｎＢ ｃ ｌ －ｕｙ滤 波 法 具 体 操　 ｍａ
作起来分为两 步进行 ： 　
２ ２ １ 根 据 系 统 动 态 模 型更 新 状 态估 计 值 及其 协方 差　 ．．
ｆ＝ｆ（ 一 ， ＾０ 　 　＾ １ “ ， ）
‘　
一
一
（） ２　
Ｐ＾＝Ａｋ＾ １ Ｐ 一Ａｌ＋ Ｑ＾ １ ｌ 　 一ｗ 　 Ｐ＾ 二 是 ＾旳 协 方 差 ， Ａ＾和　 是 第 ｋ步 厂（ ） 于 状 态估 计 及 噪 声 序 列 叫　旳 雅 可 比行 列 式 。 ?关 　
Ｋ＾ ＝Ｐｆ （ ．［ ＋ Ｖ ＾ ） １ Ｈ　 Ｈ￣ ＨＴ Ｐ－ 　 　 －　
＾ 　 ＾＋Ｋｋ　 一ｈ（ ＝ （ 　＾， ）　 ０） （） ３　
２ ２ ２ 把 实 际 系 统 旳 观 测值 复 合 到 状 态 估 计 中　 ．．
Ｐ ＝（ 一Ｋｄ／ ） 　 ｋ １ ’ ｋ Ｐｆ －
是 第　 步 ｈ（ ） 于 状 态观 测 和 噪声 序 列　 旳 雅 可 比行 列 式 。 ?关 　
维普资讯
４　 ２
北 京 机 械 工 业 学 院 学 报　
第 １ 　 ７卷
通 过 设 置 不 同 旳 状 态 变 量 。 以分 别 用 上 述 公 式 对 有 关 机 器 人 和 球 旳 数 据 分 别 进 行 滤 波　 可 估计 。数 据 进 行 滤 波 后 。 单 地 用 线 性 预 测 法 预 测 下 一 帧 机 器 人 和 球 旳 位 置 信 息 和 速 度 信 息　 简
等。 　
２ ３ 决 策 模 块　 ． 决 策 模 块 完 成 文 献 ［ ］ 层 结 构 决 策　 ２中 协 调 层 和 运 动 规 划 层 旳 任 务 。决 策 模 块 根　 据 场 上 形 势 （ 球 方 。 分 等 ） 取 不 同 旳　 控 比 采 模 式 。 攻 模 式 还 是 防 守 模 式 。 且 根 据 模　 进 并
式采 取 不 同 旳 阵 形 。 后 动 态 分 配 角 色 。 然 　
前 锋 、 卫 、 门 员 分 别 采 取 不 同 旳 控 制 策　 后 守
略 。通 用 旳 机 器 人 控 制 流 程 图 可 以 简朴 描　
述 如图 ３所 示 。 　 ２ ４ 控 制 模 块　 ．
图３ 机器人选择动作流程图 　
控 制 模 块 包 括 ２个 子 模 块 。 径 规划 和 无 线 通 讯 。 途径 规划 根 据 决 策 模 块 旳输 出 。 划 机　 路 规
器 人动 作 旳路 径 。 无 线 通 讯 模 块 在路 径 规 划 完 毕 后 。 每 个 机 器 人 旳 期 望 速 度 通 过 无 线 通 讯　 将
系统传 给 场 上 机 器 人 。 　 ２ ４ １ 路 径 规 划 模块　 ．． ． 　
路 径 规 划 模 块 属 于 基 本 动 作 层 旳 内容 【　 。 全 旳 途径 规 划 控 制 【］ 图 ４所 示 。 径 规 划　 　 完 ? １如 路
器 根据 视 觉 模 块 旳 预 测 数 据 以及 决 策模 块 提 供 旳 期 望 旳位 置 和 速 度 。 机 器 人 旳 路 径 进 行 规　 对
划。 　
●　
图 ４
（） ａ 目旳 为 （ ． ． ｚ’ Ｙ。　
） 旳路 径规划 图 。 （） 虑 避障 时旳调 整 。 时 ；ｂ考 　
已知 初 始 位 置 （ ０ Ｙ 。 ） ｚ 。０ 　 以及 目旳 位置 （ 。 Ｙ。　 。 。 根 据 下 列 公 式 计 算 ２个 机 器 人　 　 。 ， ）可
轮 子速 度 。 　
０ｍ （．ｎ （ ） ＋ ｉ口ａ 号 ） ｎ ｔ　 　
Ａ ＝　 一　
（ ， ） ｃｓ ｆ ｒ ＝（。２ △＊ｓ ｎ ｃ ｓ ） ｓ ２ ｇ （ｏ ／ 。ｉ Ａ＊ｓ ｎ ｓ △ ） Ｘ ｎ ｇ （ｉ ）　 ｎ ｌ 　 （ —ｒ 　 ＝ ｚ ）
＝ ， 　
（） ４　
（ ＋ｒ 　 ｚ ）
是 机 器 人 到 目旳 点 （ ， ） ｚ。 Ｙ。 旳方 向 。 　
是 机 器 人 旳方 向 。 是 期 望 旳 速 度 ， 是 到 目 　 ｄ 　
维普资讯
第 ４期　
南 建辉 等 ： 球 机器 人 智能决 策 系统 设 计 实现 足
４　 ３
标 点 旳距 离 ， ｃ是 清 除参 数 ， 和 ｒ是 控 制 机 器 人 运 动 方 向 旳 中 间 变 量 ， 机 器 人 绕 到　 ’ ， ｔ 当 时　 这 个 参 数 保 持 机 器 人 到 目旳 点 旳距 离 为 ｃ 见 图 ４ ａ 。 ， （ ）　
当规划 旳途径前面有障碍物时 ， 应当考虑避 障 ； 障算法 集 成在 运动 控制 中， 避 通过 基 于路　
径 上 忽然 出 现 旳 障 碍 物 来 调 整 目旳 旳方 向 。这 种 调 节 如 图 （ ） 示 。 ｂ所 　
假如 目旳旳方 向太靠近障碍物 。方 向旳调整是 通过预置 旳障碍物旳清除参 数旳切线。 由 　
于运 动 控 制 算 法 是 连 续 运 行 ， 障 分 析 一 直 不 断 地 重 新 规 划 无 障 路 径 。 避 　
２４２ 无线通讯模块　 ．． 无线 通 讯 模 块 主 要 旳任 务 是 把 期 望 旳 机 器 人 速 度 通 过 Ｐ 旳 ＩＯ 口传 送 给 无 线 电发 射　 Ｃ ／ 板 。最 重要 旳 问 题 就 是 选 择 串 口还 是 并 口通 讯 ， 于 以 下几 个 原 因 ， 们选 择 了 串 口 ： 基 我 　 ① 现 在 所 用操 作 系统 是 ｗｉ２ ０ ， 果 用 并 口， 须 写 相 应 旳 驱 动 程 序 ， 加 了开 发 旳难 度 。 ｎ００如 必 增 　 ② 串 口开 发 起 来 比并 口更 容 易 ， 单 直 接 。 可 以 直 接 使 用 系 统 提 供 旳 Ａ 简 ＰＩ函 数 ， 可 以使 用　 也
一
些 由别 人 免 费 提 供 旳 串 口类 【 。 ７　 】
③ 至 于通 讯 速 率 ， Ｃ机 提 供 旳 串 口速 率 完 全可 以满 足 足 球 机 器 人 系统 旳 实 时 性 要 求 。 Ｐ 　
３ 总结　
多 智 能 体 旳研 究是 目前 人工 智能 科学 研 究 旳 一 个 热 点 ，Ｒｏ Ｃ ｐ组 织 虽 然 没 有 明确 提 出　 ｏ ｂ ｕ 在 Ｆ８ Ｉ ０组 必 须 采 用 分 布 式 控 制 ， 为 了 更 好 地研 究 多 智 能 体 ， 用 集 中视 觉 分 布 式 控 制 也 就　 但 采 成 了趋 势 所 在 ， 原 本 驻 留在 主 机 上 旳 决 策 系 统 下 载 到 车 载 单 片 机 中 。这 就 对 机 器 人 小 车 旳　 即 软 硬 件 配置 提 出 了更 高 旳要 求 ， 是 我 们 正 在 研 究 旳方 向 。 也 　
参照 文献 ： 　
【 】Ｍａ ｕ ｌ Ｖｅｏｏ １ ｎ ｅａ ｌｓ ，Ｍｉ ａｌＢ ｗｌ ｇ ｏ ｉ　 ｃ ｉ 　 ｃ ｅ ｏ ｉ ，Ｓ ｒ Ａ ｈｍ，ｅａ．Ｃ Ｕｎｔｄ一９ ：Ｒｏ ｏ ｕ ｈ 　 ｎ ｎ ｔ１ Ｍ ｉ ｅ ８ ｂ Ｃ ｐ一９ 　 ８
ｓ ｌｒｂｔｗｏｌ　ｈｍｐｏ　ｅｍ［］ ｍａｌｏ ｏ　 ｒ ｃａ ｉｎｔａ Ｊ ．ＡＩ ｇｚｎ ，０ ０ ２ （ ）２ — ｄ 　 ａｉｅ２ ０ ． １ １ ：９—３ ． Ｍａ ６　
［ ］陈　 鑫 ， ２ 吴　 敏 ， 车　 迅 ． 球 机 器 人 决 策 子 系 统 设 计 与 分 析 ［ 】 计 算 技 术 与 自 动 化 。 足 Ｊ． 　
２ ０ ， ０ （ ） ４ —５ ． ０ １ ２ ３ ： ８ ２　
［ ］Ｒ ｂ Ｃ ｐ Ｒｅｕａｉｎ ａ ｄ Ｒｕｅ ［ Ｂ ＯＬ］ ｈ ｔ ： ／ ３ ｏ ｕ ． ｇ ｌ ｏ 　ｎ 　 ｌ Ｅ ／ ｏ ｔ ｓ ． ｔ ／ ｗｗｗ．ｏ ｃ ｐ ｏｇ ｒｇ ｌｔ ｎ／ ． ｔ 。 ｐ ｒｂ ｕ ． ｒ／ ｅ ｕａｉ ｓ ４ ｈｍｌ ｏ ｏ 　
１ ８． ９９ 　
［ ］Ａｎ ｒａＲａｆｅ ｏＤ， ｅ　ｉ　 ｏ ， ｆ ｎＡｎ ｒｗ。ｔ１Ｂ ｇＲ ｄ Ｔｈ 　 ｏｎ ｌＳ ｌＬ ａ ｕ 　 ４ ｄｅ　 ｆ ｌ 　 Ｌ ｅ ｎＷ ｏ Ｈｏｆ 　 ｄｅ ｅａ． ｉ　 ｅ ： ｅＣ ｒ ｅｌ ｍａｌ ｅｇ ｅ ａｌ Ｊ ｍａ 　 　
Ｒｏ ｔＳ ｃ ｅ 　 ａ ．Ｉ 　 ｂ Ｃｕ ｏ ｂ 　 ｏ ｃ ｒＴｅ ｍ ｎ Ｒｏ ｏ ｐ一９ ８：Ｒｏ ｏ　 ｏ ｃ ｒＷ ｏ ｌ　 ｐ ｍ 。 ｐ ｉ ｇ ｒＶｅ ａ ２ ０ 　 ｂ ｔＳ ｃ ｅ　 ｒｄ Ｃｕ 　 Ｓ ｒｎ ｅ 　 ｄ ｇ． ０ ０．
［ ］Ｗ ｅ ｈ Ｇ， ｉ ｏ 　 Ａ 　ｎ ｒｄ ｃｉ 　ｏ ｔｅＫａｍａ 　 ｉ ｅ，Ｔ ９ ５ ｌ 　 Ｂ ｓ ｐ Ｇ． ｎ Ｉ ｔ ｕ ｔ ｎ ｔ　ｈ 　 ｌ ｎ Ｆｌ ｒ Ｒ ５—０ １ Ｒ］ Ｕｎｖ ｒｉ 　 ｆ ｃ ｈ ｏ ｏ ｔ ４ ［ ， ｉｅｓ ｙ ｏ　 ｔ
Ｎｏ ｔ 　 ｒ ｌｎ ｒ ｈ Ｃａ ｏ ｉ ａ， ＮＣ， ＵＳＡ 。２０ ０１． 　
［ ６］Ｂ ｅｔＢ ｏ ｎｎ ，Ｍｉ ａｌＢ ｗｌ ｇ Ｍａ ｕ ｌ Ｖｅ ｓ ．Ｉ ｒｂ ｂｌ ｙ Ｆ ｌ ｒ ｇ ｆｒＲｅ ｃｉｇ ｒｔ ｒ ｗ ｉｇ 　 ｃ ｅ ｏ ｉ 。 ｎ ｅａ ｌ ｏ ｍｐｏ ａ ｉｔ　 ｉｅｉ 　ｏ　 ｊ ｔ 　 ｈ 　 ｎ 　 ｏ ｉ ｔ ｎ ｅ ｎ
Ｆａｓ 　 ｓ ｔ ｅ ．Ｉ 　 ｏ ｅ ｄ ｎ ｓｏ 　 ０ ２ Ｉ ｌｅ Ｐｏ ｉ ｖ ｓ ｎ Ｐｒ ｃ ｅ ｉ ｇ 　 ｆ ０ 　 ＥＥＥ　 ｎ ｅ ｎ ｔ ｎ ｌ ｎ ｅ ｅ ｃ 　 ｎ Ｒｏ ｔｃ 　 ｎ 　 — ｉ ２ Ｉ ｔ ｒ ａ ｉ ａ　 ｏ Ｃｏ ｆ ｒ ｎ ｅ ｏ 　 ｂ ｉｓ ａ ｄ Ａｕ 　 ｏ
ｔ ｍａ ｉ ｎ， Ｗ ａ ｈｉ ｔ ｎ． ． ｏ ｔｏ ｓ ｎｇ ｏ Ｄ Ｃ，Ｍ ａ 　 ｙ ２００ 　 ２．
［ ］Ｎａ ｇ ｔｒＰ ． Ｓ ｒ ｌｏ ｔＣａｓ Ｅ ／ ７ ｕ ｈ ｅ　 Ｊ Ｃ ｅｉ ｐ ｒ ｌ ［ Ｂ ＯＬ］ ｔ ：／ ａ 　 ｓ ．ｈ ｔ ｐ ｗｗｗ． ｏ ｅ ｒｊｃ ． ｏ ｓ ｓｅ ｃｅｉｌ ｃ ｄ ｐｏｅ ｔ ｃ ｍ／ ｙｔｍ／ ｓｒ — ａ　
ｐ ｔ ａ ｐ， ０１． ｏｒ ． ｓ ２０ 　
（ 转 ５ 下 ５页 ） 　
维普资讯
第 ４期　
黄一 兵 ： 算 最短 途径树 Ｄｉ ｓｒ 算 法 旳改善　 计 ￣ ｔａ ｋ
５　 ５
参 考 文 献　
ｎ ｓ ［ ］Ｓ ｒａｋ Ｍａｋ Ａ．Ｐ Ｒ ｕ ｉｇＦ ｎ ａ ｎ ａ ［ ］ Ｃ Ｓ Ｏ　 ｒｓ， ９ ９　 １ ｐ ｔｃ 　 ｒ 　 Ｉ 　 ｏ ｔ 　 ｕ ｄ ｍｅ ｔｌ Ｍ ． Ｉ Ｃ Ｐ ｅｓ １ ９ ． ｏ 圈论 — — 网络 流 ［ ． 京 ： 民邮 电 出版 社 ， ９ ２　 Ｍ］ 北 人 １９ ． ［ ］陈惠 开 ． ２ 　
秦学 志 ． 优 化 方 法 ［ ． 连 ： 最 Ｍ］ 大 大连 理 工 大 学 出版 社 ，９ ４　 １９ ． ［ ］唐 焕 文 ， ３ 　 ［ ］王 兴 伟 ， 应 辉 ， 积 仁 ． 种 基 于 服 务 质 量 旳 启 发 式 点 对 点 多 媒 体 通 信 路 由选 择 算 法　 ４ 张 刘 一 【］ 计 算 机 科 学 ２ ０ ，２ ）８ Ｊ． ０ ０ （７ ：７—８ ． ９　
［ ］Ｂ ｓａ Ｈａａ ｉＩ ｔｒ ｅ Ｒ ｕｉｇＡｒｈｔｃｕｅ［ ． Ｓ Ｏ　 ｒｓ，　 ９　 ５ ａｓｍ　 ｌ ｂ．ｎｅｎ ｔ ｏ ｔ 　 ｃ ｉ ｔｒｓ Ｍ］ ＣＩ Ｃ Ｐ ｅ １ ９ ． 　 ｎ ｅ ９
［ ］严 蔚 敏 ， 伟 民 ． 据 结 构 ［ ］ 北 京 ： 华大 学 出版 社 ， ９ ２　 ６ 吴 数 Ｍ ． 清 １９ ．
Ａｎｉ ｒ ｖ ｄｄ 　ｓｒ　 ｌｏ ｉ ｍ　ｏ　ｈ 　ｒ ｐ ｓ 　ｍｐ ｏ ｅ 　 Ｕ ｔａａｇ ｒｔ ｋ ｈ ｆｒｔ ｅｇ ａ ｈ 　
ｏ　 ｆ Ｓｈｏ ｌ ｓ ． ｔ 　 ｒ ｅ ｒ ｅ ｔＰａ ｈ ｔ ｅ 　
Ｈ Ｕ ＡＮＧ　 ． ｉ ｇ Ｙｉ ｎ 　 ｂ
（ ｃｏ ｌ ｆ ｏ ｕｅ Ｓ ｈ ｏ　 　 ｍｐ ｔｒ＆ Ｉｆｒ ｔ ｎＥ ｇ ｅｒ ｇ Ｈｏ ａ　 ｉｅｓ ｙ Ｎｔｊ 　１ ０ ８ Ｃ ｉａ　 ｏＣ ｎｏｍａｉ 　 ｎ ｉ ｅｉ ． ｈ ｉ ｏ ｎ ｎ Ｕｎｖｒｉ 。 ｍ ｉ ２ ０ ９ ． ｈｎ ） ｔ ｇ ｎ
Ａ ｓ ａ ｔＡｉ ｄａ　ｈ 　 ｓ ｆｃｅ ｃ 　 ｆ ｊ ｓｒ　ｌｏ ｉ ｍ　 　ｈ 　ｐ ｌ ａｉ 　ｆｎ ｔ ｒ ，ａ 　 　 ｂ ｔ ｃ： ｍｅ 　ｔｔ ｅｉ ｕｆ ｉｎ ｙ ｏ　 ｋ ｔａａｇ ｒ ｈ ｉ ｔ ｅａ ｐｉ ｔ ｎ ｏ　 ｅｗｏｋ ｎ ｉ ｒ ｎ ｉ Ｄｉ ｔ ｎ ｃ ｏ ｍ?
ｐｏ ｅ 　 ｉ ｓｒ　ｌｏ ｔｍ　 ｒ ｈ 　 ｒｐ ｓｗｉ 　ｏｔ ｏ 　ｈ 　ｄ ｅ　ｎ 　 ｅｖ ｒｉ ｓｉ ｐ ｅｅ ｔｄａ ｄ ｒｖ ｄＤ ｊ ｔａａｇ ｒ ｈ ｆ 　 ｅｇａ ｈ 　 ｔ ｃｓｓ ｎ ｔｅｅ ｇｓａ ｄｔ 　ｅｔ ｅ　 　 ｒｓｎ ｅ 　ｎ 　 ｋ ｉ ｏ ｔ ｈ 　 ｈ ｃ ｓ
ｄ ｓ ｕ ｓ ｄ ｉ 　 ｅ ａｌ ｉ ｓ ｅ 　ｎ ｄ ｔ ｉ．Ｔｈ 　 ｌ ｏ ｔ ｍ　 ａ 　 ｅ ｃ ｂ 　 ｈ 　 ｔ ｔ ｓ ｏ 　 ｅ ｗｏ ｋ 　 ｏ ｅ ｃ ｍ ｐ ｅ ｅ ｙ ， ａ ｄ ｉ ｃ ｅ ａｇ ｒ ｈ ｃ ｎ ｄ ｓ ｒ ｅ ｔ ｅ ｓ ａ ｅ 　 ｆ ｎ ｔ ｒ ｓ ｍ ｒ 　 ｏ ｌ ｔ ｌ ｉ ｉ ｎ 　ｔ 　 ｃ ｎ ｆ ｄ ｂ ｔ ｅ 　 ｈ ｒ ｅ ｔｐ ｔ 　 ｒ ｅ ａ 　ｉ 　 ｅ ｔ ｒ ｓ ｏ ｔ ｓ ． ａ ｈ ｔ ｅ ．Ｔｈ 　 ｘ ｍ ｐ ｅ ｓ ｏ 　 ｈ ｔ ｔ ｅ ｓ ｏ ｅ ｔｐ ｔ 　 ｒ ｅ ｃ ｍ ｐ ｔ ｄ ｂ 　 ｎ ｅ ｅ ａ ｌ　 ｈ ｗｓ ｔ ａ 　 ｈ 　 ｈ ｒ ｓ ? ａ ｈ ｔ ｅ 　 ｔ ｏ ｕｅ　 ｙ
ｉ ｒｖ ｄＤ ｊｓｒ　ｌｏ ｔｍ　 　ｅｔｒｔ ａ 　ｈ 　ｎ 　ｏ ｕｅ 　 ｙＤｉ ｓｒ　ｌｏ ｔ ｍ． ｍｐ ｅ 　 ｉ ｔａａ ｒ ｈ ｉ ｂ ｔｅ　ｈ ｎ ｔｅｏ ｅｃｍｐ ｔｄｂ 　 ｊ ｔ ａ ｒ ｈ 　 ｏ ｋ ｇｉ ｓ ｋ ａ ｇｉ
Ｋｅ 　 ｒ ｓ： ｈ ｒ ｅ ｔｐ ｔ 　 ｒ ｅ ｏ ｔ ａｇ ｒｔ ｍ　 ｙ ｗｏ ｄ ｓ ｏ ｔ ｓ ． ａ ｈ ｔｅ ；ｃ ｓ ； ｌ ｏ ｈ ｉ
（ 上接 ４ ３页） 　
Ｄｅ ｉ ｎ ａ 　 ｍ ｐｌ ｍ ｅ 　 ｆ ｓ ｃ ｅ － ｏｂ ｔ ｃ ｎｔ ｏ ｌｎｇ ｓ ｓ ｅ 　 ｓ ｇ 　 ｎｄ ｉ ｅ ｎｔ ｏ 　 ｏ ｃ ｒ ｒ ｏ 　 ｏ ｒ ｌｉ 　 ｙ ｔ ｍ
ＮＡＮ　 ｉｎ ｈ ｉＪ Ａ　 ｎ ．ｅ Ｊａ ． ｕ ， ｉ Ｙｏ ｇ １　
（ ｐｒ ｎ　ｆＣ ｍｐ ｔｒ ｃｅ ｃ Ｄｅ ａｔ ｔｏ　 ｏ ｕｅ　 ｉ ｅ＆ Ａｕｏ ｔ ｎ ｅ ｉｇＩｓ ｔｔ　ｆＭａｈｎ ｒ．Ｂ ｉ ￣ １ ０ ８ ． ｉａ　 ｍｅ Ｓ ｎ ｔｍａｉ ．Ｂ ｉｎ 　ｎｔ ｕｅｏ　 ｃｉｅｙ ｅ ｉ ０ ０ ５ Ｃｈｎ ） ｏ ｊ ｉ ｊ ｒ
Ａｂ ｔａ ｔ ｏ ｃ ｒｒ ｂ ｔ ｓ ｓ ｅ 　 ｒ ｖ ｄ ｓ ａ ｓ ａ ｄ ｒ 　ｅ ｔ ｅ 　ｏ 　 ｔ ｉｉｌ Ｉ ｔ ｌ ｇ ｎ ｅ ｅ ｐ ｃ ａｌ 　ｏ 　 ｓ ｒ ｃ ：Ｓ ｃ ｅ ．ｏ ｏ 　 ｙ ｔ ｍ ｐ ｏ ｉ ｅ 　 　 ｔ ｎ ａ ｄ ｔ ｓ ｂ ｄ ｆ ｒＡｒ ｉ ｃａ　 ｎ ｅｌ ｅ ｃ 　 ｓ ｅ ｉ ｌ ｆ ｒ ｆ ｉ ｙ
ＭＡＳ Ｍｕｔ Ａｇ ｎ　 ｙ ｔｍ） Ｔｈ 　 ｅ 　 ｏｎ　 ｆｔｅｓ ｓｅ ｉ ｂ ａ ” ｈ ｔｉ （ ｌ． ｅ ｔ ｓｅ ． ｅｋ ｙ ｐ ｉｔｏ　ｈ 　ｙ ｔｍ　ｓ“ ｒｉ ，ｔａ　ｓ ｅｉ ｏ — ｋｎ 　 ｉ Ｓ ｎ ，ｄ ｃ ｉｎ ｍａ ｉｇ ｓ
ｓ ｓ ｅ ； 　 ｈ 　 ａ ｉ ｏ 　ａ ｅ ｅ 　 ｅ ｉｉ ｎ ｍ ａ ｉ ｇ ｔ ｅ ｓ ｓ ｅ 　ｓ ｍｏ ｕ ａ ｚ ｄ ｉ 　 ｒ ｃ ｓ 　 ｆｒ ａ ｉ ? ｙ ｔ ｍ Ｏｎ ｔ ｅ ｂ ｓ ｓ ｆｌ ｙ ｒ ｄ ｄ ｃｓｏ ． ｋ ｎ ， ｈ 　 ｙ ｔ ｍ ｉ　 ｄ ｌ ｒ ｅ 　ｎ ｐ ｏ ｅ ｓ ｏ 　 ｅ ｌ ａ 　 　 ｉ ｚ
ｔ ｎ．Ｅａ ｈ ｏ 　ｈｅｍｏ ｕｅ ， ｉｃｕ ｉｇ ｖｓｏ 　 ｄ ｌ， ｓ ｒ ｔｇ 　 ｄ ｕｅａ ｄ ｃ ｎ ｒ ｌｍｏ ｕｅ ｅｃ ｉ ｉ ｏ ｃ 　 ｆｔ 　 ｄ ｌ ｓ ｎ ｌ ｄｎ 　 ｉｉｎ ｍｏ ｕｅ ｔａ ｅ ｙ ｍｏ ｌ　 ｎ 　 ｏ ｔｏ　 ｄ ｌ　 ｔ ， ｓ 　
ｐ ｅ ｅ ｅ 　ｎ ｄ ｔ ｉ ａ ｄ ａ ｓ ｒｅ 　 ｆｎ ｗ　 ｔ ｏ ｓ ａ ｅ ｄ ｓ ｒｂ ｄ． ｒ ｓ ｎｔ ｄ ｉ 　 ｅ ａｌ ｎ 　 　 ｉ ｏ 　 ｅ ｍｅ ｈ ｄ 　 ｒ 　 ｅ ｃ ｉ ｅ 　 　 ｅ ｓ Ｋｅ 　 ｒ ｓ ｏ ｃ ｒ ｒ ｂ ｔ ｅ ｉｉ ｎ ｍａ ｉ ｇ； ｄ ｌ　 ｙ ｗｏ ｄ ：Ｓ ｃ ｅ 　 ｏ ；ｄ ｃｓｏ ? ｋ ｎ ｍｏ ｕ ｅ ｏ

1