张 行 功 等 : 率 失 真 优 化 的 无 线 多 跳 网 络 多 路 径 选 择 算 法 2413 预 测 失 真 为 尺 度, 选 择 失 真 近 似 最 小 的 多 路 径 作 为 路 由. 通 过 在 NS-2 网 络 模 拟 环 境 中 的 大 量 实 验, 验 证 了 模 型 的 有

Transcription

1 软 件 学 报 ISSN , CODEN RUXUEW Journal of Software,211,22(1): [doi: /SP.J ] 中 国 科 学 院 软 件 研 究 所 版 权 所 有. Tel/Fax: 率 失 真 优 化 的 无 线 多 跳 网 络 多 路 径 选 择 算 法 + 张 行 功, 郭 宗 明 ( 北 京 大 学 计 算 机 科 学 技 术 研 究 所, 北 京 1871) Rate-Distortion Optimized Multi-Path Selection for Video Streaming over Wireless Multi-Hop Networks ZHANG Xing-Gong, GUO Zong-Ming + (Institute of Computer Science and Technology, Peking University, Beijing 1871, China) + Corresponding author: zhangxg@icst.pku.edu.cn, guozongming@pku.edu.cn Zhang XG, Guo ZM. Rate-Distortion optimized multi-path selection for video streaming over wireless multihop networks. Journal of Software, 211,22(1): Abstract: With the increase in bandwidth and computing power of wireless devices, video applications over wireless ad-hoc networks are expected to become widespread in intelligent vehicles, emergency communication, and battlefield command. However, a crucial problem is how to select the best paths for video streaming of qualify-on-service (QoS) in multi-hop wireless networks. Most of the existing research done on this topic tend to ignore the impacts of time- varying channel and wireless interference on the quality of multi-path video streaming. This paper proposes an optimized multi-path selection algorithm which takes not only network congestion into account, but also interference. Packet collision and delay in a MAC layer is predicted using the interference model. Each node is modeled as an M/M/1/K queuing system. Packet delay and loss, due to congestion, are predicted using the queuing theory. The distortion of path is defined as a function of packet losses and delays along the path. The paths with the minimum estimated distortion are selected as the optimal routings. Extensive experiments in NS-2 simulation environment have been carried out. The experimental results show that this algorithm achieves a certain level of satisfaction in the QoS of video streaming. Key words: multi-hop wireless network; multi-path routing; QoS of video streaming; rate-distortion; path selection 摘 要 : 随 着 无 线 网 络 技 术 的 发 展, 基 于 无 线 多 跳 网 的 视 频 通 信 在 智 能 交 通 灾 难 应 急 和 军 事 指 挥 等 多 个 领 域 得 到 越 来 越 广 泛 的 应 用. 但 是, 如 何 保 证 无 线 视 频 的 传 输 质 量, 是 亟 待 解 决 的 一 个 关 键 问 题. 已 有 多 路 径 视 频 传 输 研 究 忽 略 了 信 道 变 化 和 路 径 间 干 扰. 针 对 该 问 题, 提 出 一 种 基 于 率 失 真 预 测 的 多 路 径 选 择 优 化 算 法. 该 算 法 不 仅 分 析 了 网 络 拥 塞 对 传 输 质 量 的 影 响, 而 且 考 虑 了 路 径 传 输 干 扰 等 影 响 因 素. 首 先, 通 过 对 无 线 信 道 建 模, 计 算 干 扰 条 件 下 MAC 层 数 据 包 碰 撞 概 率 和 处 理 时 间 ; 其 次, 将 无 线 节 点 建 模 为 M/M/1/K 排 队 系 统, 利 用 排 队 论 预 测 网 络 拥 塞 导 致 的 延 迟 和 丢 包 ; 最 后, 通 过 建 立 视 频 传 输 与 MAC 层 性 能 以 及 网 络 拥 塞 之 间 的 率 失 真 函 数 关 系, 预 测 传 输 路 径 的 视 频 失 真. 并 以 基 金 项 目 : 国 家 自 然 科 学 基 金 (6924); 国 家 重 点 基 础 研 究 发 展 计 划 (973)(29CB3297); 国 家 发 改 委 高 技 术 计 划 ([21]344) 收 稿 时 间 : ; 修 改 时 间 : ; 定 稿 时 间 :

2 张 行 功 等 : 率 失 真 优 化 的 无 线 多 跳 网 络 多 路 径 选 择 算 法 2413 预 测 失 真 为 尺 度, 选 择 失 真 近 似 最 小 的 多 路 径 作 为 路 由. 通 过 在 NS-2 网 络 模 拟 环 境 中 的 大 量 实 验, 验 证 了 模 型 的 有 效 性. 仿 真 分 析 结 果 表 明, 该 算 法 能 够 显 著 提 高 无 线 多 跳 网 络 中 的 视 频 传 输 质 量. 关 键 词 : 无 线 多 跳 网 络 ; 多 路 径 路 由 ; 视 频 传 输 质 量 保 证 ; 率 失 真 ; 路 径 选 择 中 图 法 分 类 号 : TP393 文 献 标 识 码 : A 随 着 无 线 网 络 的 发 展 和 硬 件 成 本 的 降 低, 面 向 移 动 自 组 网 (MANET) 的 多 媒 体 应 用 得 到 越 来 越 多 的 关 注. 它 具 有 自 组 网 无 需 固 定 基 础 设 施 实 时 传 输 音 视 频 数 据 等 优 点, 在 智 能 交 通 灾 难 应 急 通 信 多 媒 体 传 感 器 视 频 监 控 和 战 场 指 挥 通 信 等 领 域 得 到 广 泛 应 用. 但 是,MANET 同 时 也 存 在 信 道 窄 干 扰 强 误 码 率 高 和 节 点 移 动 等 问 题, 而 音 视 频 传 输 要 求 高 带 宽 对 延 迟 和 丢 包 敏 感. 因 此, 如 何 在 无 线 多 跳 网 络 上 保 证 视 频 服 务 质 量 (QoS), 是 一 个 亟 待 解 决 的 关 键 问 题. [1 6] 国 内 外 已 经 开 展 的 大 量 研 究 工 作 表 明, 多 路 径 流 传 输 (multi-path streaming) 是 一 种 提 高 无 线 视 频 传 输 质 量 的 有 效 方 法. 由 于 多 条 路 径 的 可 靠 性 和 传 输 带 宽 优 于 单 一 路 径, 因 此, 通 过 在 源 节 点 和 目 标 节 点 之 间 构 建 多 条 传 输 路 径, 可 以 减 少 路 径 损 坏 对 视 频 传 输 质 量 的 影 响 [1,2]. 而 且, 无 线 信 道 具 有 广 播 特 性, 适 合 构 建 多 路 径 路 由. 目 [7 11] 前 已 有 大 量 多 路 径 路 由 协 议 方 面 的 研 究, 主 要 包 括 主 动 路 由 协 议 [1] [9] [12] 按 需 路 由 协 议 等. 国 内 相 关 研 究 也 提 出 一 种 基 于 簇 的 多 路 径 路 由 算 法, 以 减 少 路 由 查 找 和 维 护 代 价. 但 这 些 协 议 多 侧 重 于 多 路 径 查 找 和 维 护 过 程, 忽 略 了 对 备 选 路 径 的 选 择. 多 路 径 选 择 主 要 研 究 如 何 从 候 选 路 径 中 选 择 满 足 应 用 需 求 的 多 路 径. 已 有 多 路 径 路 由 算 法 大 都 基 于 简 单 网 络 参 数 ( 如 延 迟 丢 包 跳 数 等 ) [3 6,9 11] 进 行 路 径 选 择.Lee 在 DSR [7] 协 议 的 基 础 上, 于 21 年 提 出 SMR [11] 多 路 径 路 由 协 议. 通 过 选 择 链 路 或 节 点 最 小 相 交 的 多 条 路 径, 建 立 最 大 分 离 路 径 路 由. 但 该 协 议 没 有 针 对 视 频 传 输 [1,2] 优 化, 也 没 有 考 虑 无 线 网 干 扰 网 络 拥 塞 的 影 响.Apostolopoulos 提 出 Internet 多 路 径 视 频 传 输 方 法, 但 却 没 有 论 述 如 何 进 行 路 径 选 择. 针 对 该 问 题,Begen [3] 提 出 一 种 穷 举 搜 索 多 路 径 选 择 算 法 ESMR(exhaustive search multipath routing), 遍 历 所 有 路 径 组 合 从 而 得 到 最 优 路 径.Mao [4,5] 提 出 一 种 启 发 式 遗 传 算 法, 减 少 了 ESMR 算 法 的 复 杂 度. 但 是, 这 些 研 究 均 假 设 网 络 参 数 为 静 态, 算 法 复 杂 度 高, 很 难 满 足 无 线 信 道 实 时 动 态 变 化 的 要 求. 同 时, 他 们 也 没 有 考 虑 路 径 间 的 干 扰 网 络 拥 塞 和 延 迟 的 影 响. 针 对 无 线 多 跳 网 络 的 多 路 径 视 频 传 输,Wei [13] 提 出 一 种 干 扰 感 知 的 多 路 径 选 择 算 法 IWM(interference aware multipath routing). 根 据 无 线 信 道 干 扰 模 型, 建 立 链 路 竞 争 图 (contention graph) [14]. 所 有 相 互 干 扰 的 无 线 链 路 构 成 一 个 竞 争 群 (clique). 通 过 计 算 竞 争 群 中 链 路 的 丢 包 率, 可 以 得 到 端 到 端 路 径 的 丢 包 率. 以 路 径 并 发 丢 包 率 为 尺 度, 选 择 相 互 干 扰 最 小 的 多 条 路 径 传 输 MDC 多 路 码 流. 但 是, 该 方 法 没 有 考 虑 网 络 拥 塞 和 延 迟 对 视 频 传 输 失 真 的 影 响. 针 对 网 络 拥 塞 问 题,Zhang [15] 提 出 一 种 基 于 拥 塞 模 型 的 路 径 选 择 方 法. 根 据 交 叉 层 信 息, 利 用 MAC 层 的 排 队 论 模 型 预 测 拥 塞 导 致 的 视 频 失 真. 但 是, 这 些 研 究 均 未 综 合 考 虑 路 径 干 扰 网 络 拥 塞 以 及 延 迟 对 无 线 视 频 传 输 失 真 的 影 响. 本 文 提 出 一 种 基 于 率 失 真 预 测 的 多 路 径 选 择 优 化 (optimized multi-path selection, 简 称 OMS) 算 法. 通 过 对 无 线 链 路 干 扰 和 网 络 拥 塞 建 模, 预 测 路 径 的 视 频 传 输 失 真. 并 以 率 失 真 为 尺 度, 选 择 失 真 最 小 的 多 路 径 路 由. 算 法 充 分 考 虑 了 多 跳 网 络 的 路 径 干 扰 网 络 拥 塞 和 视 频 编 码 等 因 素 对 视 频 传 输 的 影 响. 通 过 建 立 视 频 传 输 与 网 络 丢 包 延 迟 之 间 的 率 失 真 函 数 关 系, 预 测 路 径 的 传 输 失 真. 利 用 无 线 链 路 竞 争 模 型 对 干 扰 建 模, 计 算 MAC 层 的 数 据 包 碰 撞 概 率 和 信 道 冻 结 时 间. 并 将 无 线 节 点 建 模 为 M/M/1/K 排 队 系 统, 利 用 排 队 理 论 预 测 网 络 拥 塞 导 致 的 延 迟 和 丢 包. 本 文 主 要 有 两 个 贡 献 : (1) 通 过 建 立 节 点 干 扰 和 排 队 系 统 模 型, 对 无 线 多 跳 网 络 中 的 视 频 传 输 失 真 进 行 预 测. 该 方 法 不 仅 考 虑 了 路 径 干 扰, 也 考 虑 了 网 络 拥 塞 对 传 输 质 量 的 影 响, 模 拟 真 实 无 线 网 络 环 境 ; (2) 充 分 考 虑 到 网 络 传 输 延 迟 对 视 频 失 真 的 影 响. 由 于 视 频 数 据 具 有 延 迟 敏 感 性, 超 时 数 据 包 同 样 也 导 致 失 真.

3 2414 Journal of Software 软 件 学 报 Vol.22, No.1, October 网 络 率 失 真 模 型 视 频 压 缩 数 据 具 有 丢 包 敏 感 和 延 迟 敏 感 的 特 性. 目 前, 主 流 视 频 压 缩 方 法 一 般 采 用 混 和 运 动 补 偿 (hybird motion compensate) 编 码, 视 频 序 列 被 编 码 为 帧 内 预 测 (I) 前 向 预 测 (P) 和 双 向 预 测 (B), 前 后 帧 之 间 存 在 依 赖 关 系. 在 网 络 传 输 过 程 中, 每 一 帧 数 据 被 封 装 到 一 个 或 多 个 网 络 数 据 包. 一 个 网 络 数 据 包 的 丢 失, 将 会 影 响 到 当 前 帧 及 后 序 帧 的 解 码, 从 而 导 致 视 频 质 量 下 降. 此 外, 视 频 是 按 时 间 顺 序 排 列 的 数 据, 数 据 包 需 要 在 规 定 延 迟 内 抵 达. 如 果 某 一 帧 数 据 在 播 放 时 刻 尚 未 完 整 到 达 解 码 器, 则 该 数 据 将 被 解 码 器 丢 弃, 从 而 产 生 视 频 抖 动 等 质 量 问 题. [16] 无 线 多 跳 网 络 中 延 迟 和 丢 包 的 原 因 主 要 有 两 种 : 信 道 干 扰 和 网 络 拥 塞. 在 IEEE 标 准 中, 无 线 节 点 采 用 载 波 侦 听 和 碰 撞 避 免 (CSMA/CA) 机 制 进 行 信 道 竞 争. 当 发 生 数 据 包 碰 撞 或 物 理 层 信 号 错 误 时, 发 送 端 将 重 传 该 数 据 包. 当 重 传 次 数 超 过 最 大 允 许 失 败 次 数 时, 数 据 包 丢 失. 如 果 发 生 网 络 拥 塞, 缓 冲 区 溢 出 也 会 导 致 丢 包. 而 网 络 延 迟 主 要 由 数 据 包 处 理 和 排 队 等 待 时 间 组 成. 数 据 包 处 理 时 间 是 MAC 层 信 道 竞 争 和 数 据 包 发 送 所 需 的 时 间, 而 排 队 等 待 时 间 是 指 数 据 包 在 缓 冲 区 中 等 待 发 送 的 时 间. 我 们 采 用 Stuhlmuller [17] 提 出 的 一 种 经 验 性 率 失 真 模 型, 建 立 视 频 传 输 失 真 与 网 络 参 数 之 间 的 函 数 关 系. 该 模 型 针 对 混 和 运 动 补 偿 编 码 标 准, 将 失 真 定 义 为 编 码 码 率 网 络 丢 包 延 迟 的 函 数. 对 于 一 个 编 码 码 率 为 R 的 视 频 序 列, 其 视 频 传 输 失 真 由 3 部 分 组 成 : 编 码 失 真 D enc, 丢 包 失 真 D error 和 超 时 失 真 D delay. 公 式 表 示 为 enc error delay D = D + D + D ω (1) error error delay = D + + κp + κ(1 P ) P R R 其 中,D,R,ω,κ 是 与 编 码 器 和 视 频 序 列 相 关 的 常 量,P error 为 网 络 丢 包 概 率,P delay 为 数 据 包 超 时 概 率. 针 对 指 定 视 频 序 列 和 编 解 码 器, 编 码 失 真 D enc 主 要 由 编 码 码 率 决 定. 由 于 Mao [5] 已 经 讨 论 了 多 路 径 的 码 率 分 配 问 题, 本 文 重 点 讨 论 视 频 传 输 的 后 两 部 分 失 真 : 丢 包 失 真 和 超 时 失 真. 我 们 利 用 MAC 层 的 干 扰 模 型 和 网 络 拥 塞 的 队 列 模 型, 预 测 无 线 多 跳 网 络 的 丢 包 率 和 超 时 概 率. 2 IEEE 数 据 包 处 理 分 析 [16] IEEE 分 布 式 协 同 机 制 (DCF) 的 工 作 模 式 有 两 种 : 基 本 模 式 和 RTS/CTS 模 式. 其 中,RTS/CTS 模 式 采 用 4 次 握 手, 缓 解 隐 藏 终 端 (hidden-station) 和 暴 露 终 端 (exposed-station) 问 题 的 影 响. 本 文 主 要 讨 论 在 RTS/CTS 模 式 下 的 路 径 选 择. 在 RTS/CTS 模 式 中, 发 送 方 首 先 监 听 信 道 是 否 空 闲. 如 果 空 闲 时 间 超 过 t DIFS ( 分 布 式 帧 间 时 间 ), 回 退 计 时 器 开 始 计 时. 当 计 数 器 为 时, 发 送 节 点 先 发 送 一 个 RTS 数 据 包, 用 于 请 求 发 送 ; 接 收 节 点 收 到 RTS 包 后 等 待 一 个 t SIFS ( 短 帧 时 间 ), 然 后 回 送 一 个 CTS 数 据 包, 确 认 信 道 可 用. 发 送 方 收 到 CTS 包 后, 确 认 可 以 发 送 数 据. 在 t SIFS 时 间 后 发 送 数 据 ( 发 送 时 间 为 t DATA ); 当 接 收 节 点 接 收 数 据 成 功 后, 等 待 t SIFS 时 间 后 发 送 一 个 ACK 确 认 消 息. 从 而, 接 收 双 方 确 认 进 行 了 一 次 成 功 的 数 据 传 输. 因 此, 一 次 成 功 的 数 据 传 输 所 占 用 信 道 时 间 T s 可 表 示 为 T s =t DIFS +t RTS +t CTS +t DATA +t ACK +3t SIFS (2) 在 RTS/CTS 模 式 中, 发 生 数 据 传 输 失 败 的 情 况 有 两 种 : 一 种 是 RTS/CTS 握 手 不 成 功, 另 一 种 是 数 据 发 送 过 程 中 发 生 失 败. 发 送 方 发 送 数 据 后, 如 果 t CTSTimeout 时 间 内 没 有 收 到 ACK 消 息, 则 认 为 发 送 失 败. 发 送 方 将 侦 听 信 道, 重 新 开 始 新 一 轮 的 数 据 发 送. 因 此, 一 次 失 败 数 据 发 送 所 占 用 的 时 间 T c 可 以 表 示 为 T c =t DIFS +t RTS +t CTSTimeout (3) 在 上 述 公 式 中,t DIFS,t SIFS,t RTS,t CTS,t ACK,t CTSTimeout 均 是 与 信 道 参 数 相 关 的 常 量.t DATA 为 数 据 本 身 占 用 信 道 时 间, 由 数 据 包 大 小 和 信 道 带 宽 决 定. 本 文 中 假 设 所 有 传 输 数 据 包 大 小 均 为 固 定 长 度. IEEE 采 用 载 波 侦 听 多 路 访 问 (CSMA) 机 制. 当 发 生 传 输 错 误 时, 发 送 方 需 要 不 断 地 竞 争 信 道 进 行 重 传. 在 碰 撞 避 免 (CA) 协 议 中, 采 用 二 进 制 指 数 回 退 机 制 降 低 数 据 包 碰 撞 概 率. 每 次 发 送 之 前, 发 送 方 都 会 随 机 从

4 张 行 功 等 : 率 失 真 优 化 的 无 线 多 跳 网 络 多 路 径 选 择 算 法 2415 竞 争 窗 口 (,CW) 之 间 选 择 一 个 随 机 数 作 为 回 退 计 数 器. 当 计 数 器 回 退 到 时, 开 始 发 送 数 据.CW 为 竞 争 窗 口 大 小, 其 最 小 值 为 W. 每 次 发 送 重 试,CW 的 值 都 会 增 加 1 倍. 因 此, 第 i 次 发 送 的 CW 取 值 为 2 i 1 W. 假 设 系 统 设 定 发 送 重 传 次 数 上 限 为 m 次, 如 果 发 生 m 次 数 据 传 输 失 败, 则 该 数 据 包 被 丢 弃. 假 设 数 据 发 送 失 败 概 率 为 p c, 则 发 送 [18] 重 试 过 程 的 Markov 状 态 链 如 图 1 所 示. p c p c 1 m Loss 1 p c 1 p c Succ 1 p c 1 p c Fig.1 Markov process of MAC retransmission 图 1 数 据 发 送 重 试 的 Markov 链 根 据 该 模 型, 可 以 得 到 MAC 层 数 据 包 期 望 处 理 时 间 E[X]: m 1 i m EX [ ] = pc(1 pc)[ it ( c + Tb) + ( Ts + Tb)] + pmt c ( c + Tb) (4) i= 其 中,T b 为 回 退 等 待 时 间, 它 包 括 回 退 计 时 器 时 间 和 信 道 冻 结 时 间. 在 回 退 等 待 过 程 中, 发 送 节 点 监 听 信 道 繁 忙 程 度. 当 信 道 空 闲 时, 计 时 器 启 动 计 数 ; 当 信 道 繁 忙 时, 计 时 器 冻 结. 我 们 定 义 信 道 冻 结 时 间 比 例 为 信 道 冻 结 时 间 与 回 退 等 待 时 间 的 比 值, 假 设 为 p f, 则 在 第 i 次 发 送 的 回 退 等 待 时 间 T b 为 i 1 回 退 计 时 器 大 小 (2 w 1)/ 2 Tb = = (5) 1 信 道 冻 结 比 例 1- p E[X] 值. 在 上 述 公 式 中,T s,t c,m,w 均 为 系 统 相 关 常 量. 只 要 得 到 数 据 发 送 失 败 概 率 p c 信 道 冻 结 比 例 p f, 就 可 以 计 算 2.1 无 线 信 道 干 扰 模 型 [14] 本 节 通 过 对 无 线 链 路 干 扰 建 模, 采 用 竞 争 图 模 型 分 析 MAC 层 数 据 包 的 碰 撞 和 信 道 冻 结 时 间. 假 设 无 线 节 点 的 数 据 发 送 速 率 为 u, 即 每 个 数 据 包 的 平 均 发 送 时 间 为 1/u. 由 公 式 (4) 可 知, 一 个 数 据 包 的 发 送 时 间 包 括 回 退 时 间 信 道 冻 结 时 间 碰 撞 时 间 和 数 据 传 输 占 用 信 道 时 间. 其 中, 数 据 传 输 占 用 信 道 时 间 为 T s. 由 于 RTS/CTS 数 据 包 较 小, 可 以 忽 略 RTS/CTS 数 据 包 碰 撞 导 致 的 信 道 占 用 时 间. 因 此, 成 功 发 送 一 个 数 据 包 所 占 用 信 道 时 间 的 比 例 可 近 似 为 成 功 发 送 占 用 信 道 时 间 θ = μt s (6) 数 据 包 平 均 发 送 时 间 在 IEEE 网 络 中 存 在 两 种 距 离 : 传 输 距 离 (RX_Range) 和 干 扰 距 离 (IF_Range). 通 常, 干 扰 距 离 大 于 传 输 距 离. 例 如, 在 Lucent WaveLAN 网 卡 中,RX_Range 为 25m, 而 IF_Range 为 55m. 传 输 距 离 是 数 据 包 在 两 个 节 点 间 成 功 传 输 的 最 大 距 离, 它 由 发 射 能 量 和 信 道 传 播 特 性 决 定. 干 扰 距 离 是 指 在 此 距 离 范 围 内 的 所 有 节 点 都 可 以 收 到 发 射 源 的 信 号. 通 常, 干 扰 距 离 也 是 载 波 侦 听 距 离, 无 线 节 点 可 以 探 测 到 该 范 围 内 其 他 节 点 是 否 在 占 用 信 道. 针 对 一 条 无 线 数 据 链 接, 可 将 其 邻 居 节 点 划 分 为 载 波 侦 听 区 域 (CS) 和 干 扰 区 域 (IF). 假 设 发 送 节 点 为 s, 接 收 节 点 为 d.cs 区 域 是 指 到 发 送 节 点 s 距 离 小 于 IF_Range 的 区 域, 发 送 节 点 可 以 侦 听 到 此 区 域 所 有 节 点 发 出 的 信 号. 干 扰 区 域 是 指 距 离 发 送 节 点 s 大 于 IF_Range 但 到 接 收 节 点 d 小 于 IF_Range 的 区 域. 当 此 区 域 的 节 点 发 送 数 据 时, 发 送 节 点 s 检 测 不 到 信 号, 但 接 收 节 点 d 会 受 到 信 号 干 扰, 从 而 导 致 数 据 包 碰 撞, 也 即 隐 藏 终 端 问 题 (hidden stations problem).cs 区 域 和 IF 区 域 分 别 如 图 2 所 示. 定 义 所 有 落 在 CS 区 域 的 节 点 集 合 为 CS(s,d), 所 有 落 在 IF 区 域 的 节 点 集 合 为 IF(s,d). 对 于 集 合 中 的 任 意 两 f

5 2416 Journal of Software 软 件 学 报 Vol.22, No.1, October 211 个 节 点 i,j, 假 设 其 距 离 为 d(i,j). 如 果 d(i,j) 小 于 IF_Range, 两 个 节 点 可 以 检 测 到 彼 此 的 信 号. 根 据 载 波 侦 听 机 制, 两 个 节 点 不 能 同 时 发 送 数 据. 如 果 d(i,j) 大 于 IF_Range, 则 两 个 节 点 可 以 同 时 发 送 数 据. 因 此, 任 意 两 点 组 成 的 集 合 所 占 用 信 道 的 比 例 为 θi + θ j θθ i j, d( i, j) > IF _ Range θij = θi θ j = (7) θi + θ j, d( i, j) IF _ Range CS area IF area IF_Range RX_Range s d Fig.2 Carrier-Sensing area and interference area 图 2 CS 区 域 和 IF 区 域 划 分 由 公 式 (7), 我 们 可 以 得 到 CS(s,d) 集 合 所 占 用 信 道 的 时 间 比 例, 记 为 θ CS. 同 样, 得 到 IF(s,d) 集 合 所 占 信 道 的 时 间 比 例 为 θ IF. 当 CS 集 合 节 点 发 送 数 据 时, 发 送 节 点 检 测 到 信 道 繁 忙, 将 冻 结 回 退 计 时 器. 因 此,CS 节 点 集 合 发 送 数 据 的 时 间 就 是 发 送 节 点 s 的 信 道 冻 结 时 间. 如 果 发 送 节 点 占 用 信 道 的 时 间 比 例 为 θ s, 则 信 道 冻 结 时 间 比 例 p f 可 表 示 为 p θ CS f = (8) 1 θs 当 IF 区 域 节 点 和 发 送 节 点 同 时 发 送 时, 在 接 收 节 点 上 会 导 致 数 据 包 发 生 碰 撞. 由 于 发 送 节 点 s 随 机 选 择 回 退 窗 口 中 的 任 意 时 刻 发 送 数 据, 数 据 包 碰 撞 概 率 等 于 IF 节 点 占 用 信 道 时 间 与 回 退 时 间 的 比 值. 因 此, 数 据 包 碰 撞 导 致 的 数 据 发 送 失 败 概 率 可 以 表 示 为 p θ IF c = (9) 1 θs 将 公 式 (8) 公 式 (9) 带 入 公 式 (4) 中, 我 们 就 可 以 计 算 得 到 每 个 数 据 包 的 平 均 处 理 时 间 E[X]. 2.2 网 络 拥 塞 的 延 迟 和 丢 包 分 析 基 于 前 述 MAC 层 数 据 包 期 望 处 理 时 间, 本 节 利 用 排 队 模 型 分 析 网 络 拥 塞 导 致 的 数 据 包 延 迟 和 丢 包. 无 线 节 点 发 送 数 据 前, 先 将 数 据 包 缓 存 至 发 送 队 列 (IFQ), 等 待 MAC 层 处 理. 当 MAC 层 空 闲 时, 按 照 先 进 先 出 (FIFO) 原 则, 取 出 队 列 头 第 1 个 数 据 包 处 理. 只 有 当 队 列 中 前 面 的 数 据 包 被 处 理 完 毕, 新 到 达 的 数 据 包 才 能 被 处 理. 因 此, 无 线 节 点 的 数 据 包 延 迟 包 括 两 部 分 : 排 队 等 待 延 迟 和 MAC 层 处 理 时 间. 无 线 节 点 的 IFQ 队 列 长 度 通 常 为 固 定 大 小. 当 MAC 层 处 理 速 度 慢 于 数 据 包 到 达 速 度 时, 队 列 将 发 生 溢 出, 从 而 导 致 网 络 丢 包. 可 将 无 线 节 点 的 IFQ 队 列 建 模 为 一 个 M/M/1/K 排 队 系 统 [19]. 假 设 到 达 数 据 包 按 照 泊 松 (Possion) 分 布 依 次 进 入 队 列, 即 单 位 时 间 内 到 达 的 数 据 包 个 数 是 完 全 随 机 的. 数 据 进 入 节 点 后, 在 一 个 长 度 为 K 的 队 列 中 缓 存 等 待. 同 时, 假 设 MAC 层 的 数 据 包 处 理 时 间 满 足 独 立 指 数 随 机 分 布, 即 前 后 两 个 数 据 包 处 理 时 间 没 有 关 系. 因 此, 无 线 节 点 的 M/M/1/K 模 型 如 图 3 所 示. 对 于 一 条 无 背 景 流 量 的 无 线 路 径, 任 一 节 点 的 数 据 包 到 达 速 率 均 由 其 前 一 跳 的 输 出 码 率 和 丢 包 率 来 决 定. 对 于 路 径 的 第 1 个 节 点, 其 数 据 包 到 达 速 率 为 编 码 器 输 出 的 视 频 码 率. 对 于 路 径 上 第 n 个 节 点, 如 果 λ n 1 为 前 一 error 节 点 的 数 据 包 到 达 码 率, Pn 1 和 Pn 1 delay 为 前 一 节 点 的 排 队 丢 包 率 和 超 时 概 率, 则 节 点 n 的 数 据 包 到 达 速 率 为 error delay λn = λn 1 (1 Pn 1 )(1 Pn 1 ) (1)

6 张 行 功 等 : 率 失 真 优 化 的 无 线 多 跳 网 络 多 路 径 选 择 算 法 2417 由 公 式 (4) 可 知, 节 点 n 的 MAC 层 数 据 包 平 均 处 理 时 间 为 E[X n ]. 在 队 列 长 度 为 K 的 发 送 缓 存 队 列 中, 其 队 列 溢 出 概 率 也 是 数 据 包 的 丢 包 概 率. 根 据 M/M/1/K 的 排 队 论 公 式, 节 点 n 的 排 队 丢 包 率 可 以 表 示 为 (1 λ EX [ ]) λ EX [ ] π = K K n n n n K 1 K 1 (1 λ + n EX [ n] + ) 数 据 包 的 平 均 延 迟 包 括 MAC 层 处 理 时 间 和 队 列 等 待 时 间. 根 据 排 队 论 的 Little 公 式, 我 们 可 以 得 到 在 节 点 n 上 的 数 据 包 平 均 延 迟 E[T] 为 EX [ ] λ KEX [ ] ET [ ] = 1 λ [ ] 1 [ ] K K+ 1 n n n K K nexn λn EXn 由 此, 我 们 得 到 由 于 网 络 拥 塞 导 致 的 数 据 包 延 迟 和 丢 包 率. Buffer length K (11) (12) λ n E[X] Node n Fig.3 Queueing model of wireless node 图 3 无 线 节 点 的 排 队 模 型 2.3 路 径 传 输 失 真 估 计 一 条 路 径 的 视 频 传 输 失 真, 是 其 上 所 有 链 接 的 传 输 失 真 之 和. 因 此, 通 过 分 析 无 线 节 点 的 失 真, 就 可 以 得 到 路 径 的 传 输 失 真. 由 公 式 (1) 可 知, 数 据 包 丢 失 和 传 输 超 时 都 会 导 致 视 频 传 输 失 真. 下 面 分 别 讨 论 如 何 得 到 无 线 节 点 的 网 络 丢 包 率 P error 和 传 输 超 时 概 率 P delay. 无 线 节 点 上 发 生 数 据 包 丢 失 的 原 因 主 要 有 两 种 : 发 送 缓 存 队 列 IFQ 溢 出 MAC 层 传 输 失 败 导 致 丢 包. 其 中 : IFQ 的 队 列 溢 出 概 率 可 由 公 式 (11) 得 到 ;MAC 层 发 生 m 次 重 传 失 败 后, 也 会 导 致 丢 包. 因 此, 无 线 节 点 的 丢 包 率 可 以 表 示 为 error m P = π + (1 π) p c (13) 网 络 延 迟 也 会 导 致 视 频 失 真. 视 频 是 顺 序 播 放 的 流 媒 体 数 据, 如 果 数 据 包 传 输 时 间 超 时, 则 解 码 器 将 不 处 理 该 数 据 包. 假 设 视 频 解 码 器 的 延 迟 上 限 为 Δ, 数 据 包 到 达 该 无 线 节 点 的 平 均 延 迟 为 t. 无 线 节 点 的 数 据 包 处 理 时 间 E[X] 平 均 延 迟 时 间 E[T] 和 数 据 包 达 到 速 率 可 分 别 由 公 式 (4) 公 式 (12) 公 式 (1) 得 到. 根 据 排 队 延 迟 的 长 尾 分 布 理 论 [2,21], 无 线 节 点 的 超 时 概 率 可 近 似 为 P delay λe[ X]( Δ t) ET [ ] λe[ X]e (14) 假 设 一 条 无 线 路 径 上 有 N 个 节 点, 每 个 节 点 的 数 据 丢 包 率 和 超 时 概 率 由 上 述 公 式 可 得. 路 径 的 视 频 传 输 失 真 是 其 上 所 有 节 点 的 失 真 之 和. 因 此, 该 路 径 的 传 输 失 真 为 D D ω P P P N N error error delay path = + + κ i + κ (1 i ) i R R i= i= (15) 3 多 路 径 选 择 优 化 算 法 根 据 上 述 公 式, 可 采 用 ESMR(exhaustive search multipath routing) 穷 举 法 进 行 多 路 径 选 择. 通 过 枚 举 计 算 所 有 路 径 组 合 的 率 失 真, 从 中 选 择 失 真 最 小 的 路 径 组 合 作 为 多 路 径 路 由. 该 方 法 可 以 找 到 最 优 的 多 路 径, 但 计 算 复 杂 度 较 高. 其 遍 历 所 有 路 径 组 合, 算 法 复 杂 度 为 O(N 2 )(N 为 备 选 路 径 数 ), 无 法 满 足 无 线 网 络 实 时 动 态 变 化 的 要 求. 因 此, 我 们 提 出 一 种 OMS 近 似 算 法, 以 降 低 路 径 选 择 复 杂 度. 首 先, 在 不 考 虑 路 径 间 干 扰 的 情 况 下 计 算 每 条 无 线 路 径 的 传 输 失 真, 选 择 失 真 最 小 的 路 径 作 为 第 1 条 路 径. 然 后, 在 考 虑 第 1 条 路 径 干 扰 的 条 件 下, 估 计 剩 余 路

7 2418 Journal of Software 软 件 学 报 Vol.22, No.1, October 211 径 的 传 输 失 真, 从 中 选 择 失 真 最 小 的 路 径 作 为 第 2 条 路 径. 依 此 类 推, 得 到 次 优 的 多 路 径 路 由. 该 算 法 的 复 杂 度 为 O(N), 计 算 量 小. 在 动 态 变 化 的 无 线 网 络 中, 可 以 快 速 找 到 视 频 传 输 路 径. OMS 算 法 虽 然 不 是 最 优 的 路 径 选 择 算 法, 但 在 实 际 无 线 多 跳 网 络 中, 其 结 果 与 ESMR 算 法 接 近. 首 先, 视 频 失 真 与 路 径 长 度 (HOPS 跳 数 ) 有 直 接 关 系, 路 径 越 长, 失 真 也 越 大. 因 此, 最 优 多 路 径 算 法 一 般 会 选 择 距 离 较 小 的 路 径. 而 OMS 算 法 优 先 选 择 失 真 最 小 的 路 径, 一 般 也 是 最 小 距 离 的 那 条 路 径, 它 属 于 最 优 路 径 集 合 的 概 率 较 高. 其 次, 在 无 线 多 跳 网 中, 干 扰 距 离 远 远 大 于 传 输 距 离, 长 度 较 小 的 路 径 之 间 一 般 都 存 在 重 合 节 点 或 干 扰. 而 且, 这 些 路 径 大 都 在 最 短 路 径 附 近, 它 们 的 失 真 与 它 们 对 最 短 路 径 导 致 的 失 真 差 异 不 大. 因 此,OMS 算 法 选 择 的 路 径 与 最 优 多 路 径 产 生 的 失 真 比 较 接 近. OMS 算 法 流 程 见 表 1. Algorithm OMS. Parameters: CS_IF_SET: Set of wireless nodes; PATH_SET: Set of candidate paths; path_distortion[i]: Distortionof path[i]; multi_path[k]: Output results; Table 1 OMS path selection algorithm 表 1 OMS 路 径 选 择 算 法 1: for k= do 2: for path i PATH_SET do 3: CS_IF_SET all nodes belong to path i 4: CS_IF_SET all nodes on multi_path[,,k 1] 5: for node j path i do 6: p c [j] Collision probability by Equ.(9); 7: p f [j] Channel freezing probability by Equ.(8); 8: X[j] Computing expected proc. time by Equ.(4); 9: D[j] Computing distortion by Equ.(1); 1: end for node j 11: Path_Distortion[i] D[ j] ; j path[] i 12: end for path i; 12: multi_path[k] MinDistortion(PATH_SET); 14: PATH_SET PATH_SET multi_path[k]; Omitting nodes in multi_path[k] from PATH-SET 15: end for k [7] 我 们 在 动 态 源 地 址 路 由 (DSR) 协 议 的 基 础 上, 实 现 了 OMS 路 径 选 择 算 法.DSR 协 议 是 一 种 源 地 址 路 由 协 议, 路 由 信 息 保 存 在 数 据 包 头. 当 有 数 据 发 送 时, 无 线 节 点 从 包 头 的 路 由 表 信 息 查 找 下 一 跳 节 点.OMS 多 路 径 路 由 包 括 两 个 步 骤 : 路 由 查 找 过 程 和 路 径 选 择 过 程. 首 先 经 过 路 由 查 找 过 程 发 现 多 条 候 选 路 径, 然 后 采 用 路 由 选 择 算 法 确 定 适 合 视 频 传 输 的 多 路 径. 路 由 查 找 模 块 采 用 传 统 的 按 需 路 由 协 议 [8], 它 仅 在 源 节 点 有 数 据 发 送 时 才 发 起 路 由 查 找 过 程. 源 节 点 首 先 发 起 路 由 请 求 过 程, 向 所 有 领 居 节 点 广 播 路 由 请 求 消 息 (RREQ); 中 间 节 点 收 到 RREQ 消 息 后, 判 断 目 标 地 址 是 否 为 自 己 ; 如 果 自 己 不 是 目 标 节 点, 则 中 间 节 点 继 续 广 播 RREQ 消 息. 当 消 息 到 达 目 标 节 点 后, 则 开 始 路 由 确 认 过 程. 目 标 节 点 回 送 路 由 确 认 消 息 (RREP), 按 照 RREQ 消 息 的 接 收 路 径, 逆 向 传 输 给 源 节 点. 当 源 节 点 收 到 RREP 消 息 后, 确 认 从 源 节 点 到 目 标 节 点 的 路 径 搭 建 完 毕. 路 由 查 找 过 程 可 以 形 成 从 源 节 点 到 目 标 节 点 的 多 条 候 选 路 径, 发 送 端 选 择 合 适 路 径 发 送 数 据. 对 DSR 协 议 进 行 修 改, 保 留 其 路 由 查 找 模 块. 增 加 信 道 侦 听 模 块 路 径 选 择 模 块, 并 修 改 数 据 包 头 数 据 结 构, 从 而 实 现 了 OMS 协 议 : (1) 信 道 侦 听 模 块. 在 无 线 节 点 MAC 层 添 加 信 道 侦 听 模 块, 侦 听 处 于 IF_Range 范 围 内 的 领 居 节 点 状 态 以 及 它 们 的 数 据 包 发 送 速 率. 这 些 节 点 构 成 了 该 节 点 的 CS 节 点 集 合 ; (2) 路 径 选 择 模 块. 修 改 DSR 协 议 的 路 由 选 择 模 块, 将 原 有 的 最 短 路 径 算 法 替 换 为 OMS 算 法. 当 有 数 据 包

8 张 行 功 等 : 率 失 真 优 化 的 无 线 多 跳 网 络 多 路 径 选 择 算 法 2419 发 送 时, 利 用 OMS 算 法 选 择 最 优 路 径. 将 路 径 选 择 结 果 添 加 至 包 头, 发 送 该 数 据 包 ; (3) 包 头 信 息. 在 RREP 数 据 包 头 增 加 CS 节 点 集 合 节 点 发 送 码 率 信 息. 通 过 RREP 包 将 这 些 信 息 回 送 到 源 节 点. 4 模 拟 与 性 能 评 估 4.1 模 拟 环 境 与 参 数 配 置 本 文 在 NS-2 [22] 无 线 网 络 模 拟 环 境 中 对 失 真 估 计 模 型 和 路 径 选 择 算 法 进 行 了 评 估. 网 络 模 拟 节 点 的 物 理 层 采 用 共 享 式 物 理 信 道 模 型, 通 信 距 离 为 25m, 干 扰 距 离 为 55m. 无 线 信 道 的 带 宽 是 1Mbps, 无 线 节 点 的 MAC 层 基 于 IEEE 协 议, 使 用 RTS/CTS 模 式 的 无 线 局 域 网 分 布 协 作 机 制 (DCF). 模 拟 节 点 的 缺 省 参 数 见 表 2, 其 基 本 性 能 类 似 于 Lucent WaveLan 网 卡. Table 2 Parameters of wireless simulation networks 表 2 无 线 模 拟 环 境 缺 省 参 数 Parameters Values Parameters Values Packet payload bits Channel bit rate 1M bit/s MAC header 272 bits Slot time 2 μs PHY header 128 bits SIFS 28 μs ACK 112 bits+phy DIFS 128 μs RTS 16 bits+phy Retransmission limit 4 CTS 112 bits+phy MAC queue size 5 CW min 32 bits T s bits CW max 1 24 bits T c bits 我 们 在 1m 1m 的 空 间 中 创 建 一 个 具 有 16 个 无 线 节 点 的 拓 扑. 随 机 地 从 16 个 节 点 中 选 择 两 个 节 点 作 为 发 送 方 和 接 收 方, 其 他 节 点 随 机 选 择 一 个 目 标 节 点 发 送 背 景 流 量. 背 景 流 量 的 数 据 包 大 小 为 512 字 节, 流 量 码 率 从 kbps~2kbps. 实 验 采 用 Foreman 视 频 序 列, 使 用 基 于 JVT/H.264 [23] 视 频 编 码 压 缩 标 准 的 JM14 软 件 对 其 编 码. 序 列 格 式 为 CIF( ), 编 码 帧 率 为 1fps. 我 们 设 置 GOP 大 小 为 15 帧, 编 码 方 式 为 IBBPBBP. 编 码 后 的 码 率 为 5kbps. 视 频 序 列 长 度 为 1 帧, 每 一 帧 封 装 成 一 个 或 多 个 UDP 数 据 包, 每 个 数 据 包 长 度 不 大 于 1 24 字 节. 从 编 码 序 列 中 提 取 奇 偶 帧, 在 不 同 路 径 上 传 输 奇 数 帧 和 偶 数 帧, 从 而 实 现 多 路 径 传 输. 接 收 端 播 放 缓 冲 区 大 小 设 置 为 5s, 用 于 平 滑 数 据 包 延 迟 抖 动, 提 高 播 放 流 畅 性. 视 频 数 据 按 RTP 格 式 封 包, 采 用 UDP 协 议 在 无 线 多 跳 网 络 中 传 输. 播 放 缓 冲 区 收 到 UDP 数 据 包 后, 按 照 RTP 包 序 号 和 时 间 戳 对 数 据 包 进 行 排 序, 保 证 视 频 数 据 播 放 的 顺 序 性. 在 实 验 中, 首 先 对 无 线 信 道 干 扰 模 型 和 拥 塞 排 队 模 型 进 行 验 证. 比 较 模 型 结 果 和 NS-2 模 拟 器 的 实 验 结 果, 验 证 模 型 的 正 确 性. 其 次, 我 们 在 网 络 模 拟 器 中 生 成 2 个 随 机 拓 扑, 测 试 静 态 拓 扑 下 算 法 的 性 能. 最 后, 在 移 动 环 境 下 比 较 算 法 与 传 统 路 径 选 择 算 法 的 性 能 差 异. 4.2 模 型 验 证 测 试 无 线 网 络 模 拟 器 中 的 数 据 丢 包 率 和 延 迟, 并 与 模 型 计 算 结 果 进 行 比 较, 从 而 验 证 排 队 模 型 的 正 确 性. 实 验 随 机 选 择 两 个 节 点 作 为 发 送 方 和 接 收 方, 发 送 方 持 续 向 接 收 方 发 送 UDP 数 据 包. 发 送 数 据 包 大 小 固 定 为 1 24 字 节, 产 生 数 据 流 量 从 1kbps 增 加 到 1 kbps. 总 共 进 行 3 轮 测 试, 每 轮 测 试 时 间 为 1s. 在 发 送 端 和 接 收 端 同 时 记 录 数 据 包 的 发 送 时 间 和 接 收 时 间, 对 数 据 包 传 输 延 迟 和 丢 包 率 进 行 统 计. 计 算 不 同 传 输 码 率 下 的 平 均 时 延 和 丢 包 率, 所 得 实 验 结 果 如 图 4 所 示 ( 其 中, 横 坐 标 为 输 入 码 率 ). NS-2 网 络 模 拟 结 果 如 图 4 所 示. 当 发 送 码 流 达 到 8kbps 左 右 时, 数 据 包 传 输 时 延 开 始 急 剧 增 加. 平 均 时 延 从.1s 增 加 到.5s 左 右, 达 到 峰 值 后 就 基 本 保 持 不 变. 而 网 络 丢 包 率 随 着 发 送 码 率 的 增 加 而 呈 线 性 增 加, 如 图 2 所 示, 没 有 峰 值. 导 致 这 种 现 象 的 原 因 为 : 当 网 络 带 宽 饱 和 时, 数 据 包 处 理 速 度 慢 于 输 入 码 率, 导 致 无 线 节 点 的 发

9 242 Journal of Software 软 件 学 报 Vol.22, No.1, October 211 送 数 据 缓 冲 队 列 溢 出. 新 到 达 数 据 包 必 须 等 待 队 列 中 所 有 数 据 处 理 完 毕 才 能 够 被 处 理. 由 于 缓 冲 队 列 长 度 固 定, 因 此 每 个 数 据 包 的 平 均 延 迟 都 等 于 队 列 中 所 有 数 据 包 处 理 完 毕 的 时 间. 而 当 发 生 缓 冲 区 溢 出 时, 后 续 到 达 的 数 据 包 都 将 全 部 丢 弃. 因 此, 网 络 丢 包 率 将 随 着 发 送 码 率 的 增 长 而 呈 线 性 增 长. 同 时, 我 们 计 算 了 网 络 干 扰 模 型 和 M/M/1/K 排 队 模 型 中 的 理 论 延 迟 和 丢 包 率. 根 据 公 式 (11)~ 公 式 (13) 计 算 的 理 论 结 果 如 图 4 所 示. 显 然, 模 型 得 到 的 理 论 延 迟 和 丢 包 率 与 NS-2 实 验 结 果 曲 线 能 够 很 好 地 吻 合, 从 而 验 证 了 本 文 模 型 能 够 有 效 估 算 无 线 网 络 的 传 输 延 迟 和 丢 包 率. Delay (s) Simulation Model Packet loss (%) Simulation Model Bit rate (kbps) Bit rate (kbps) (a) Delay (a) 传 输 延 迟 比 较 (b) Packet loss (b) 网 络 丢 包 率 比 较 Fig.4 Comparison of modeling results and simulation results 图 4 模 型 结 果 与 NS-2 网 络 模 拟 结 果 比 较 4.3 性 能 评 价 对 象 在 NS-2 模 拟 环 境 下, 对 OMS 路 径 优 化 选 择 算 法 的 性 能 进 行 了 测 试, 并 与 分 离 多 路 径 路 由 (split multi-path routing, 简 称 SMR) 算 法 和 IWM(interference aware multipath routing) 干 扰 感 知 多 路 径 算 法 进 行 比 较. 性 能 评 价 指 标 包 括 平 均 峰 值 信 噪 比 (PSNR) 丢 帧 率 (frame lost ratio) 和 平 均 帧 延 迟 (frame delay). [11] SMR 算 法 是 一 种 按 需 路 由 (on-demand) 算 法, 它 优 先 选 择 节 点 或 链 接 最 大 不 相 交 的 多 条 路 径 作 为 路 由. 该 算 法 缺 省 认 为, 不 相 交 路 径 具 备 最 大 的 路 径 冗 余 和 带 宽 资 源. 算 法 的 路 径 选 择 过 程 如 下 : (1) 接 收 端 等 待 接 收 端 回 送 的 多 个 路 由 请 求 (RREQ) 消 息, 获 取 尽 可 能 多 的 候 选 路 径 ; 然 后, 发 送 端 选 择 最 短 路 径 作 为 第 1 条 路 径 ; (2) 接 收 端 从 候 选 路 径 集 合 中 选 出 第 2 条 路 径, 使 其 与 第 1 条 路 径 在 节 点 或 链 路 上 重 合 得 最 少. 如 果 所 有 候 选 路 径 重 合 度 相 同, 则 选 择 跳 数 (HOP) 最 小 的 路 径 ; 如 果 HOP 数 也 相 同, 则 选 择 RREQ 消 息 传 输 最 快 的 路 径. [13] IWM 算 法 是 一 种 针 对 多 描 述 (MDC) 视 频 传 输 的 路 径 选 择 算 法, 其 无 线 多 跳 网 络 的 干 扰 建 模. 首 先 估 计 每 一 条 链 接 的 丢 包 率, 其 次 计 算 传 输 路 径 的 丢 包 估 计, 最 后 寻 找 并 发 丢 包 最 小 的 多 跳 路 径 作 为 传 输 路 径. 在 相 同 拓 扑 相 同 码 率 的 条 件 下, 传 输 相 同 的 视 频 序 列, 统 计 接 收 到 视 频 的 平 均 峰 值 信 噪 比 平 均 丢 帧 率 和 平 均 帧 延 迟. 4.4 静 态 拓 扑 下 的 性 能 比 较 利 用 NS-2 的 Setdest 工 具 随 机 生 成 2 组 静 态 网 络 拓 扑, 测 试 OMS,IWM 和 SMR 算 法 在 静 态 拓 扑 中 的 性 能. 首 先 从 16 个 无 线 节 点 中 随 机 选 择 两 个 节 点 作 为 源 节 点 和 目 标 节 点 ; 源 节 点 和 目 标 节 点 记 录 每 一 帧 的 发 送 时 间 和 接 收 时 间 ; 最 后 统 计 每 一 帧 的 延 迟 以 及 整 段 视 频 的 丢 帧 率. 总 共 进 行 了 2 轮 测 试, 按 照 源 节 点 和 目 标 节 点 的 距 离 (HOP) 对 实 验 结 果 进 行 排 序. 对 相 同 HOP 数 的 测 试 结 果 取 平 均 值, 并 剔 除 偶 然 因 素 的 影 响. 所 得 实 验 结 果 如 图 5 所 示 ( 其 中, 横 坐 标 为 源 节 点 与 目 标 节 点 距 离 ). 图 5(a) 给 出 静 态 拓 扑 下 视 频 传 输 的 丢 帧 率. 随 着 源 节 点 到 目 标 节 点 距 离 的 增 加,3 种 算 法 的 平 均 丢 帧 率 延 迟

10 张 行 功 等 : 率 失 真 优 化 的 无 线 多 跳 网 络 多 路 径 选 择 算 法 2421 逐 渐 变 大. 原 因 是, 随 着 中 转 节 点 的 增 加, 端 到 端 带 宽 急 剧 下 降. 而 当 路 径 长 度 大 于 4 跳 后, 平 均 丢 帧 率 的 增 长 趋 向 平 缓. 这 是 由 于 实 验 中 设 置 信 道 干 扰 范 围 为 55m, 有 效 传 输 距 离 为 25m 所 致. 对 于 简 单 线 性 拓 扑, 每 个 节 点 周 围 最 多 有 4 个 干 扰 节 点. 即 使 路 径 长 度 大 于 4 跳, 干 扰 节 点 数 量 也 不 会 随 着 路 径 长 度 的 增 加 而 变 大. 因 此, 当 路 径 长 度 达 到 一 定 跳 数 时, 传 输 路 径 的 有 效 带 宽 基 本 保 持 不 变, 从 而 使 平 均 丢 帧 率 的 增 长 变 缓. 在 相 同 拓 扑 下, 本 文 提 出 的 OMS 算 法 具 有 最 小 丢 帧 率 和 延 迟, 如 图 5(a) 所 示. 当 源 节 点 和 目 标 节 点 距 离 较 近 时, 大 多 数 路 径 均 互 相 干 扰, 因 此,3 种 算 法 的 丢 包 率 相 近. 但 是, 由 于 SMR 算 法 没 有 考 虑 干 扰, 因 此 其 丢 包 率 最 大. 而 IWM 算 法 优 先 选 择 互 相 不 干 扰 路 径, 导 致 路 径 长 度 和 传 输 延 迟 增 加. 因 此,IWM 算 法 的 平 均 帧 延 迟 最 大. 当 距 离 大 于 6 跳 以 后, 相 互 不 干 扰 的 可 选 路 径 数 量 增 加.IWM 算 法 和 OMS 算 法 所 选 择 的 路 径 趋 同, 两 者 的 丢 包 率 和 延 迟 逐 渐 接 近. 但 是, 由 于 IWM 算 法 没 有 考 虑 路 径 拥 塞, 导 致 其 丢 包 率 和 延 迟 大 于 OMS 算 法. 而 SMR 算 法 始 终 选 择 节 点 不 相 交 路 径, 而 不 考 虑 路 径 间 干 扰, 导 致 其 丢 包 率 和 延 迟 最 大. Average frame loss ratio (%) OMS SMR IWM Hops Average frame delay (s) OMS SMR IWM Hops (a) Average frame loss ratio (a) 平 均 丢 帧 率 (b) Average frame delay (b) 平 均 帧 延 迟 Fig.5 Performance comparisions in static topology 图 5 静 态 拓 扑 下 OMS 和 SMR 的 性 能 比 较 对 接 收 端 收 到 的 视 频 质 量 进 行 了 比 较, 如 图 6 所 示 ( 其 中, 横 坐 标 是 视 频 帧 序, 纵 坐 标 是 接 收 端 的 视 频 质 量 (PSNR 值 )). 随 机 选 取 一 个 预 先 创 建 的 静 态 拓 扑 ( 本 例 为 Scen_17), 用 3 种 算 法 分 别 传 输 相 同 的 视 频 序 列. 对 收 到 的 视 频 数 据 进 行 解 码, 逐 帧 计 算 PSNR, 比 较 传 输 过 程 中 的 视 频 质 量 变 化. 显 然,SMR 算 法 的 质 量 最 差, 平 均 PSNR 仅 为 26.23db.IWM 算 法 的 PSNR 值 较 高, 平 均 为 32.99db. 但 由 于 其 未 考 虑 路 径 拥 塞 和 延 迟, 受 网 路 突 发 丢 包 (burst loss) 影 响 较 大, 从 而 使 其 PSNR 低 于 OMS 算 法. PSNR (db) IWM SMR OMS Frame number Fig.6 PSNR comparisions of received video 图 6 接 收 视 频 接 收 质 量 比 较

11 2422 Journal of Software 软 件 学 报 Vol.22, No.1, October 211 OMS 算 法 能 够 检 测 路 径 间 的 干 扰 和 网 络 拥 塞, 从 而 切 换 到 延 迟 较 低 的 路 径. 因 此, 当 发 生 网 络 拥 塞 时,OMS 算 法 的 视 频 质 量 能 够 很 快 恢 复 到 3db 以 上. 其 平 均 PSNR 达 到 36.68db, 接 收 端 具 有 更 好 的 接 收 质 量. 4.5 移 动 拓 扑 下 的 性 能 比 较 我 们 在 移 动 环 境 下 对 3 种 算 法 的 性 能 也 进 行 了 比 较. 网 络 拓 扑 采 用 了 通 用 的 Random Waypoint 移 动 模 型, 每 个 节 点 随 机 选 择 一 个 初 始 位 置, 然 后 随 机 选 择 一 个 目 标 位 置 和 速 度, 向 目 标 位 置 移 动. 到 达 目 标 地 点 后, 节 点 停 留 一 段 固 定 时 间, 然 后 重 新 开 始 运 动. 实 验 中, 设 置 节 点 停 顿 时 间 为 1s, 节 点 最 大 速 度 从 2m/s~2m/s, 模 拟 城 市 中 手 持 设 备 和 汽 车 的 移 动 速 度. 在 每 种 速 度 设 置 下, 节 点 随 机 选 择 小 于 该 最 大 速 度 的 一 个 数 值, 作 为 该 次 移 动 速 度. 我 们 创 建 了 2 个 移 动 场 景, 计 算 不 同 最 大 速 度 情 况 下 的 平 均 丢 帧 率 和 帧 延 迟. 如 图 7 所 示 ( 横 坐 标 为 最 大 移 动 速 度 ): 当 最 大 移 动 速 度 小 于 6m/s 时,3 种 算 法 的 平 均 丢 帧 率 和 延 迟 随 着 速 度 的 增 加 而 减 少 ; 而 当 最 大 移 动 速 度 大 于 6m/s 时, 算 法 性 能 随 着 速 度 增 加 而 增 加. 这 是 由 于 当 移 动 速 度 较 慢 时, 速 度 对 路 由 变 动 的 影 响 不 大, 反 而 增 加 了 候 选 路 径 的 数 量, 从 而 使 多 路 径 路 由 能 够 选 择 更 优 的 路 径 ; 而 当 移 动 速 度 较 快 时, 路 径 中 断 频 率 增 加. 频 繁 的 路 由 修 复 过 程 将 导 致 网 络 拥 塞 加 重, 从 而 使 平 均 丢 帧 率 和 延 迟 增 加. Average frame loss ratio (%) 1 IWM SMR OMS Speed (m/s) (a) Average frame loss ratio (a) 平 均 丢 帧 率 Average frame delay (s) 2.5 IWM SMR OMS Speed (m/s) (b) Average frame delay (b) 平 均 帧 延 迟 Fig.7 Performances in mobile topology 图 7 移 动 拓 扑 下 平 均 丢 帧 率 和 帧 延 迟 由 图 7 可 知, 在 相 同 移 动 速 度 下,SMR 算 法 的 丢 帧 率 和 延 迟 最 大. 尤 其 是 当 移 动 速 度 在 8m/s~12m/s 之 间 时, 由 于 路 由 频 繁 更 改, 导 致 丢 包 率 急 剧 增 加.IWM 算 法 优 先 选 择 互 不 干 扰 路 径, 在 低 速 移 动 时, 其 丢 帧 率 与 OMS 算 法 接 近 ; 但 当 移 动 速 度 较 大 时, 由 于 其 未 考 虑 路 径 变 化 导 致 的 拥 塞, 丢 帧 率 高 于 OMS 算 法. 但 在 高 速 运 动 时,IWM 算 法 的 延 迟 与 OMS 算 法 接 近. 这 是 由 于 高 速 运 动 时 的 延 迟 主 要 由 路 由 修 复 时 间 组 成, 因 此 对 两 种 算 法 的 影 响 相 同. 5 结 论 本 文 提 出 一 种 面 向 无 线 多 跳 网 络 的 基 于 率 失 真 估 计 的 路 径 选 择 优 化 算 法. 通 过 建 立 视 频 失 真 和 网 络 丢 包 延 迟 间 的 函 数 关 系, 预 测 无 线 视 频 传 输 失 真. 以 失 真 为 尺 度, 选 择 传 输 失 真 最 小 的 路 径 作 为 多 路 径 路 由. 该 算 法 综 合 考 虑 无 线 干 扰 和 网 络 拥 塞 的 影 响, 建 立 信 道 干 扰 和 网 络 拥 塞 模 型. 利 用 MAC 层 干 扰 模 型, 预 测 数 据 包 碰 撞 概 率 和 信 道 冻 结 时 间. 同 时, 用 M/M/1/K 排 队 模 型 对 无 线 节 点 建 模, 预 测 网 络 拥 塞 下 的 延 迟 和 丢 包 率. 根 据 链 路 丢 包 率 和 延 迟 估 计, 预 测 路 径 的 视 频 传 输 失 真. 在 NS-2 网 络 模 拟 环 境 中 进 行 了 大 量 实 验, 实 验 结 果 验 证 了 模 型 的 正 确 性. 表 明 该 算 法 优 于 IWM 算 法 和 SMR 算 法, 视 频 传 输 质 量 得 到 明 显 提 高. 下 一 步 我 们 将 对 多 路 径 传 输 的 干 扰 模 型 进 一 步 优 化, 并 搭 建 WiFi 实 验 床, 在 实 际 无 线 多 跳 网 环 境 下 优 化 多 路 径 选 择 算 法.

12 张 行 功 等 : 率 失 真 优 化 的 无 线 多 跳 网 络 多 路 径 选 择 算 法 2423 References: [1] Apostolopoulos J, Tan WT, Wee S, Wornell GW. Modeling path diversity for multiple description video communication. In: Mercer B, ed. Proc. of the IEEE ICASSP. Piscataway: IEEE Press, [doi: 1.119/ICASSP ] [2] Apostolopoulos JG. Reliable video communication over lossy packet networks using multiple state encoding and path diversity. In: Girod B, Steinbach EG, eds. Proc. of the Visual Communications and Image Processing. SPIE Press, [3] Begen A, Altunbasak Y, Ergun O, Ammar M. Multi-Path selection for multiple description encoded video streaming. EURASIP Signal Processing: Image Communication, 25,2(1):39 6. [4] Mao SW, Hou YT, Cheng X, Sherali H, Midkiff S, Zhang YQ. On routing for multiple description video over wireless ad hoc networks. IEEE Trans. on Multimedia, 26,8(5): [doi: 1.119/TMM ] [5] Mao SW, Kompella S, Hou YT, Sherali HD, Midkiff SF. Routing for multiple concurrent video sessions in wireless ad hoc networks. In: Proc. of the IEEE Conf. on Communications. Piscataway: IEEE Press, [doi: 1.119/ICC ] [6] Shiang HP, van der Schaar M. Multi-User video streaming over multi-hop wireless networks: A distributed, cross-layer approach based on priority queuing. IEEE Journal on Selected Areas in Communications, 27,25(4): [doi: 1.119/JSAC ] [7] Johnson DB, Maltz DA, Hu YC, Jetcheva JG. The dynamic source routing protocol for mobile ad hoc networks. IETF Internet Draft (draft-ietf-manet-dsr-3.txt), [8] Perkins CE, Royer EM, Dos SR. Ad hoc on-demand distance vector (AODV) routing. IETF Internet Draft (draft-ietf-manetaodv- 6.txt), 2. [9] Marina MK, Das SR. On-Demand multipath distance vector routing in ad hoc networks. In: Titsworth FM, ed. Proc. of the IEEE ICIP. Piscataway: IEEE Press, [1] King PJB, Etorban A, Ibrahim IS. A DSDV-based multipath routing protocol for mobile ad hoc networks. In: Proc. of the 8th Annual Postgraduate Symp. on the Convergence of Telecommunications, Networking and Broadcasting [11] Lee SJ, Gerla M. Split multipath routing with maximally disjoint paths in ad hoc networks. In: Proc. of the IEEE ICC. Piscataway: IEEE Press, [doi: 1.119/ICC ] [12] An HY, Lu XC, Peng W. A cluster-based multipath routing algorithm in mobile ad hoc networks. Journal of Software, 27,18(4): [doi: 1.136/jos18987] [13] Wei W, Zakhor A. Interference aware multipath selection for video streaming in wireless ad hoc networks. IEEE Trans. on Circuits and Systems for Video Technology, 29,19(2): [doi: 1.119/TCSVT ] [14] Gupta P, Kumar PR. The capacity of wireless networks. IEEE Trans. on Information Theory, 2,46(2): [doi: 1.119/ ] [15] Zhang XG, Pang Y, Guo ZM. Rate-Distortion based path selection for video streaming over wireless ad-hoc networks. In: Lin CY, Cox I, eds. Proc. of the IEEE Int l Conf. on Multimedia & Expro. (ICME). IEEE Press, [doi: 1.119/ICME ] [16] IEEE Part11: Wireless LAN medium access control (MAC) and physical layer (PHY) specifications. ANSI/IEEE Std.82.11, 1999(E), ISO/IEC, , [17] Stuhlmuller K, Farberand N, Link M, Girod B. Analysis of transmission over loss channels. IEEE Journal on Selected Areas in Communications, 2,18(6): [doi: 1.119/ ] [18] Bianchi G. Performance analysis of the IEEE distributed coordination function. IEEE Journal on Selected Areas in Communications, 2,18(3): [doi: 1.119/ ] [19] Yang WD, Ma JF, Li YH. Performance analysis based on packet arrival rate for the IEEE DCF. Journal of Software, 28,19(1): [doi: /SP.J ]

13 2424 Journal of Software 软 件 学 报 Vol.22, No.1, October 211 [2] Jiang T, Tham CK, Ko CC. An approximation for waiting time tail probabilities in multiclass systems. IEEE Communication Letters, 21,5(4): [doi: 1.119/ ] [21] Abate J, Choudhury GL, Whitt W. Exponential approximations for tail probabilities in queues I: Waiting times. Operations Research, 1995,43(5): [doi: /opre ] [22] NS2: Network simulator [23] ITU-T Rec. H.264/ISO/IEC AVC, Telecom. Standardization Sector of ITU, 23. 附 中 文 参 考 文 献 : [12] 安 辉 耀, 卢 锡 城, 彭 伟. 移 动 自 组 网 中 一 种 基 于 簇 的 多 路 径 路 由 算 法. 软 件 学 报,27,18(4): /18/987.htm [doi: 1.136/jos18987] [19] 杨 卫 东, 马 建 峰, 李 亚 辉. 基 于 分 组 到 达 率 的 DCF 性 能 分 析. 软 件 学 报,28,19(1): [doi: /SP.J ] 张 行 功 (1973-), 男, 湖 北 宜 昌 人, 博 士, 副 研 究 员, 主 要 研 究 领 域 为 无 线 网 络, 多 媒 体 通 信, IPTV. 郭 宗 明 (1966-), 男, 博 士, 研 究 员, 博 士 生 导 师,CCF 会 员, 主 要 研 究 领 域 为 视 频 处 理, 多 媒 体 通 信.