标题

Transcription

1 第 34 卷 第 9 期 西 南 大 学 学 报 ( 自 然 科 学 版 ) 2012 年 9 月 Vol.34 No.9 JournalofSouthwestUniversity (NaturalScienceEdition) Seṗ 2012 文 章 编 号 : (2012) 基 于 认 知 无 线 电 的 MANET 1 网 络 中 虚 拟 骨 干 网 的 建 立 刘 昌 明 1, 李 林 1, 冯 文 江 2, 吴 迪 2 1. 重 庆 电 子 工 程 职 业 学 院, 重 庆 ;2. 重 庆 大 学 通 信 工 程 学 院, 重 庆 摘 要 : 将 认 知 无 线 电 技 术 融 入 MANET 网 络, 利 用 认 知 节 点 的 频 谱 感 知 功 能, 实 施 基 于 动 态 信 息 的 簇 首 和 网 关 选 择. 以 簇 首 为 锚 点, 通 过 选 择 受 主 用 户 影 响 较 小 的 网 关 节 点 寻 求 连 通 支 配 集, 建 立 虚 拟 骨 干 网. 由 此 生 成 的 虚 拟 骨 干 网 以 簇 首 为 接 入 点, 簇 首 间 的 网 关 承 担 簇 间 连 接 功 能. 基 于 权 值 比 较, 通 过 对 主 用 户 的 位 置 感 知, 划 分 认 知 节 点 的 空 间 分 布 区 域 并 赋 以 不 同 的 权 值 设 计, 实 现 对 网 络 的 分 区 处 理, 一 方 面 维 持 运 动 中 的 分 簇 相 对 稳 定, 另 一 方 面 减 少 干 扰 链 路 存 在 的 概 率. 最 后 通 过 仿 真 分 析 进 行 了 算 法 的 有 效 性 验 证. 关 键 词 : 移 动 无 线 自 组 网 ; 认 知 无 线 电 ; 虚 拟 骨 干 网 ; 拓 扑 ; 分 簇 中 图 分 类 号 :TN929.5 文 献 标 志 码 :A 移 动 无 线 自 组 网 (MobileAdhoc WirelessNetworks:MANET) 是 一 种 小 范 围 部 署, 无 固 定 基 础 设 施 的 无 线 通 信 系 统 [1], 广 泛 应 用 于 军 事 通 信 应 急 通 信 紧 急 服 务 等 特 殊 领 域.MANET 网 络 具 有 灵 活 部 署 快 速 机 动 等 优 点, 但 也 存 在 带 宽 和 成 员 电 池 能 量 有 限 拓 扑 变 化 快 可 扩 展 性 和 安 全 性 差 等 不 足. 将 认 知 [2] 无 线 电 技 术 融 入 MANET 网 络, 通 过 对 主 用 户 工 作 状 态 的 监 测 和 自 适 应 资 源 调 整, 能 实 现 频 谱 资 源 共 享, 满 足 用 户 的 QoS 需 求. MANET 网 络 结 构 分 为 平 面 结 构 和 分 层 结 构 [3], 平 面 结 构 由 于 没 有 骨 干 基 础 设 施 的 支 撑, 处 理 能 力 和 扩 展 性 较 弱, 数 据 交 换 时, 若 采 用 泛 洪 会 造 成 大 量 的 重 复 消 息, 浪 费 有 限 的 带 宽 资 源 ; 若 采 用 按 需 路 由 也 会 加 重 控 制 开 销. 而 分 层 结 构 则 具 有 更 高 的 管 理 效 能, 同 时 也 可 以 为 数 据 交 换 提 供 路 由 建 议. 分 簇 是 建 立 分 层 结 构 管 理 平 面 的 核 心 技 术 之 一 [4], 通 过 特 定 的 选 举 方 式, 在 对 等 网 中 选 出 相 对 固 定 的 簇 首 节 点 (clusterhead:ch), 簇 首 节 点 辅 助 簇 内 通 信, 而 簇 间 通 过 网 关 节 点 (Gateway:GW) 建 立 链 路. 这 种 机 制 通 过 簇 首 协 调 簇 内 通 信, 抑 [5] 制 了 簇 内 消 息 的 泛 洪 (Flooding), 但 在 较 稠 密 的 网 络 中, 依 旧 大 量 存 在 冗 余 簇 间 链 路. 在 保 证 簇 连 通 的 前 提 下, 通 过 建 立 一 个 包 含 最 少 节 点 数 目 的 虚 拟 骨 干 网 作 为 短 期 的 基 础 设 施 服 务 网 络, 是 有 效 降 低 全 网 通 信 负 荷 的 方 式 之 一. 尽 管 这 个 想 法 很 吸 引 人, 但 是 从 图 论 角 度 看, 寻 找 最 小 连 通 支 配 集 是 一 个 著 名 的 NP 难 问 题. 目 前, 有 关 虚 拟 骨 干 网 的 构 造 算 法 大 致 分 为 集 中 式 和 分 布 式 两 类. 文 献 [5] 提 出 了 一 种 稠 密 自 组 网 中 通 过 单 跳 网 关 的 选 举 形 成 连 通 支 配 集 的 分 布 式 近 似 算 法 ; 文 献 [6] 提 出 了 控 制 平 面 的 网 状 模 式 (Mesẖlike) 和 树 状 (Treeḻike) 模 式, 设 计 了 在 分 区 内 建 立 连 通 支 配 集 再 将 其 连 接 起 来 的 骨 干 网 建 设 方 法 ; 文 献 [7] 提 出 了 融 合 了 认 知 无 线 电 技 术 的 无 线 自 组 织 网 络 的 体 系 结 构 ; 但 是, 目 前 针 对 认 知 无 [8] 线 电 MANET 网 络 的 拓 扑 管 理 研 究 比 较 少. 认 知 无 线 电 作 为 一 种 智 能 频 谱 共 享 技 术, 依 靠 人 工 智 能 的 支 持, 感 知 无 线 通 信 环 境, 根 据 一 定 的 学 习 1 收 稿 日 期 : 基 金 项 目 : 国 家 自 然 科 学 基 金 ( ); 重 庆 市 自 然 科 学 基 金 重 点 项 目 (CSTC2009BA2064); 国 家 211 工 程 三 期 建 设 项 目 (S 09102); 重 庆 市 教 委 科 技 项 目 (KJ102201); 重 庆 市 教 委 科 技 项 目 (KJ102203) 资 助. 作 者 简 介 : 刘 昌 明 (1956 ), 男, 重 庆 人, 副 教 授, 主 要 从 事 计 算 机 网 络, 软 件 工 程 方 面 的 研 究.

2 2 西 南 大 学 学 报 ( 自 然 科 学 版 ) htp://xbbjb.swu.cn 第 34 卷 和 决 策 算 法, 实 时 自 适 应 的 改 变 系 统 工 作 参 数, 动 态 的 检 测 和 有 效 的 利 用 空 闲 频 谱, 理 论 上 允 许 在 时 域 频 域 和 空 域 上 进 行 多 维 的 频 谱 复 用 和 共 享, 被 认 为 是 缓 解 目 前 日 益 增 长 的 频 谱 需 求 与 有 限 的 频 谱 资 源 之 间 矛 盾 的 一 种 有 效 手 段. 在 MANET 网 络 中 融 合 认 知 无 线 电 技 术 和 拓 扑 管 理 技 术, 在 保 留 固 有 工 作 频 段 的 同 [9] 时, 通 过 认 知 无 线 电 技 术 对 空 闲 授 权 频 段 的 临 时 借 用, 获 取 额 外 的 MANET 网 络 通 信 带 宽, 并 频 谱 感 知 到 主 用 户 工 作 时 及 时 让 出 该 频 谱 资 源, 避 免 对 主 用 户 造 成 干 扰. 如 果 工 作 在 一 个 授 权 频 率 的 主 用 户 被 发 现, 认 知 用 户 应 该 立 刻 停 止 占 用 这 个 频 点, 切 换 到 另 一 个 可 用 频 点 上 继 续 当 前 的 通 信. 因 为 这 个 要 求 的 存 在, 新 频 点 的 选 择 和 被 占 频 点 的 出 让 是 一 个 整 体 过 程. 这 项 工 作 需 要 频 谱 感 知 链 路 层 的 邻 居 发 现 以 及 路 由 协 议 这 三 部 分 的 整 合, 在 过 程 中, 对 网 络 的 实 时 性 会 造 成 一 定 损 失, 协 议 做 到 对 上 层 透 明, 但 是 传 输 延 迟 是 不 可 避 免 的. 但 是, 频 谱 让 出 会 带 来 一 定 延 迟, 比 如, 认 知 用 户 需 要 重 配 置 发 射 机 工 作 频 率 和 调 制 方 [10] 式, 需 要 对 当 前 的 通 信 进 行 保 持, 可 能 还 需 要 更 新 路 由. 因 此, 避 免 干 扰 链 路 的 存 在 是 有 效 提 升 认 知 网 络 性 能 的 方 式 之 一, 若 当 前 链 路 所 连 接 的 两 个 节 点 之 一 或 全 部 是 位 于 以 主 用 户 位 置 为 圆 心, 认 知 用 户 天 线 覆 盖 范 围 为 半 径 的 圆 形 区 域 的 干 扰 节 点, 则 认 为 该 链 路 会 对 主 用 户 造 成 潜 在 干 扰. 因 此, 在 主 用 户 工 作 时, 该 链 路 需 要 切 换. 因 为 簇 首 节 点 或 者 是 网 关 节 点 所 维 持 的 链 路 数 目 多 于 普 通 节 点. 为 此, 本 文 利 用 认 知 节 点 的 频 谱 感 知 功 能, 在 基 于 动 态 信 息 的 簇 首 和 网 关 选 择 的 基 础 上, 以 簇 首 为 锚 点, 通 过 选 择 受 主 用 户 影 响 较 小 的 网 关 节 点 寻 求 连 通 支 配 集 (ConnectedDominatingSet:CDS), 建 立 MA- NET 的 虚 拟 骨 干 网, 以 此 生 成 的 虚 拟 骨 干 网 可 以 看 成 是 认 知 网 格 网 中 的 AP(AccessPoint) 集, 其 中 簇 首 是 AP, 簇 首 间 的 网 关 承 担 簇 间 的 连 接 功 能. 基 于 权 值 比 较, 通 过 对 主 用 户 的 位 置 感 知, 在 空 间 上 对 认 知 节 点 分 布 的 区 域 进 行 划 分, 赋 以 不 同 的 权 值 设 计, 实 现 对 网 络 的 分 区 处 理, 一 方 面 维 持 运 动 中 的 分 簇 相 对 稳 定, 另 一 方 面 减 少 干 扰 链 路 存 在 的 概 率. 1 相 关 约 定 和 数 学 模 型 图 的 基 本 定 义 : 邻 接 : 一 个 图 G 定 义 为 一 个 偶 对 G=(V,E), 其 中 V 是 顶 点 集,E 是 边 集. 对 于 节 点 u, 若 存 在 节 点 v, 当 且 仅 当 e=(u,v) E 时, 则 称 之 为 相 邻,u,v 互 为 邻 居 节 点. 连 通 : 设 u,v 是 图 G 中 的 两 个 顶 点, 若 在 G 中 存 在 一 条 (u,v) 路 径, 则 称 顶 点 u 和 v 是 连 通 的 (connected). 如 果 图 G 中 每 一 对 不 同 的 顶 点 u,v 都 有 一 条 (u,v) 路 径, 则 称 图 G 是 连 通 的. 支 配 集 : 设 图 G=(V,E) 是 一 个 简 单 无 向 图, 若 能 找 到 一 个 V 的 子 集 S,S V, vx V -S 至 少 和 S 中 的 一 个 节 点 相 邻, 则 称 S 是 图 G 的 支 配 集,S 中 的 节 点 称 为 支 配 节 点, 不 在 集 中 的 节 点 称 为 受 支 配 节 点. 若 S 的 任 何 真 子 集 都 不 是 支 配 集, 称 S 为 极 小 支 配 集. 独 立 集 : 对 于 图 G=(V,E),I V,I 中 任 意 两 点 都 不 相 邻, 则 I 是 图 G 的 一 个 独 立 集 ; 任 意 vx I,I vx 不 是 独 立 集, 称 I 为 极 大 独 立 集. 单 位 圆 图 : 设 图 G=(V,E) 是 一 个 简 单 无 向 图, 对 于 点 u,v, 当 且 仅 当 dist(u,v) R 时, 存 在 边 e= (u,v) E, 则 称 该 图 是 单 位 圆 图 (UnitDiskGraph:UDG). 其 中 函 数 dist 表 示 求 距 离. 假 定 MANET 网 络 中 的 所 有 节 点 都 分 布 在 二 维 平 面 上, 每 个 节 点 具 有 全 向 天 线, 节 点 的 覆 盖 范 围 是 以 该 [11] 节 点 为 中 心, 半 径 等 于 节 点 传 输 距 离 R 的 圆. 当 所 有 节 点 的 传 输 距 离 相 同 时, 网 络 就 具 有 单 位 圆 图 特 性. 用 单 位 圆 图 G=(V,E) 表 示 认 知 无 线 电 MANET 网 络, 其 中 V 是 点 集 合, 每 一 个 节 点 表 示 一 个 终 端 设 备 ;E 是 边 集 合, 对 于 点 u,v, 若 dist(u,v) R 则 存 在 边 e=(u,v) E, 表 明 u,v 间 存 在 双 向 链 路, 称 其 互 为 邻 居. 此 外, 每 个 节 点 初 始 化 时 被 分 配 唯 一 表 示 符 ID(Identification). 建 立 虚 拟 骨 干 网 可 以 抽 象 为 在 单 位 圆 图 中, 寻 求 连 通 支 配 集 问 题. 尽 管 在 实 际 网 络 中, 两 个 节 点 之 间 除 距 离 之 外 还 有 很 多 因 素 决 定 能 否 直 接 通 信, 但 是 在 拓 扑 理 论 研 究 中, 仍 假 设 距 离 是 节 点 之 间 能 否 直 接 通 信 的 唯 一 条 件. 2 虚 拟 骨 干 网 的 建 立 2.1 权 值 计 算 基 于 认 知 无 线 电 主 用 户 定 位 技 术 [12], 认 知 节 点 可 以 判 断 自 己 是 否 对 主 用 户 造 成 潜 在 干 扰. 基 于 此, 将

3 第 9 期 刘 昌 明, 等 : 基 于 认 知 无 线 电 的 MANET 网 络 中 虚 拟 骨 干 网 的 建 立 3 终 端 集 合 V 划 分 为 非 干 扰 节 点 集 合 Vn 和 干 扰 节 点 集 合 Vi,Vi+Vn=V. 在 分 簇 阶 段 和 网 关 选 择 阶 段 都 分 区 处 理, 对 于 处 于 非 干 扰 区 的 节 点 或 网 关, 选 举 稳 定 性 好 的 节 点 作 为 簇 首 或 网 关 ; 而 对 于 存 在 潜 在 干 扰 的 节 点, 则 干 扰 越 小 越 优 先. 为 了 对 干 扰 区 和 非 干 扰 区 节 点 进 行 权 值 比 较, 需 要 保 证 干 扰 区 内 最 优 节 点 的 权 值 小 于 非 干 扰 区 内 最 差 节 点 的 权 值, 干 扰 区 内 最 优 网 关 的 权 值 小 于 非 干 扰 区 内 最 差 网 关 的 权 值. 为 此, 定 义 如 下 权 值 计 算 表 达 式 : 在 分 簇 阶 段 : 在 网 关 选 择 阶 段 : vx Vn { vx Vi (vx) wc = fnode interfn(vx) v {g},v Vn { i wg = fgw (g) interfgw (g) v {g},v V 其 中 vch 表 示 簇 首 节 点,g 表 示 网 关.fnode 和 fgw 分 别 求 节 点 与 网 关 的 权 值,interfn 和 interfgw 分 别 求 节 点 和 网 关 对 主 用 户 的 干 扰 程 度. 本 文 设 计 fnode 函 数 表 征 运 动 中 当 前 节 点 与 邻 居 节 点 的 链 路 稳 定 性 [13], 反 映 了 当 前 节 点 与 所 有 k 个 邻 居 节 点 的 k 条 链 路 可 用 度 Ii 之 和 : k-1 fnode Ii (3) = i=0 为 了 区 分 节 点 同 向 运 动 和 反 向 运 动, 链 路 可 用 度 Ii 定 义 为 : Ii = ìæ R-Sm,n ö æ ç1-1- ΔSm,n ö ç ΔSm,n >0 íè Δt 2 v max ø è 2 vmax Δτ ø î1 ΔSm,n 0 式 中 R 表 示 天 线 的 覆 盖 半 径,Sm,n 和 ΔSm,n 分 别 为 节 点 m 和 n 之 间 的 距 离 和 距 离 改 变 量 ;vmax 为 节 点 最 大 运 动 速 度 ;Δt 为 两 次 速 度 改 变 之 间 的 时 间 间 隔 ;Δτ 表 示 用 于 测 算 相 对 速 度 和 距 离 而 进 行 的 相 邻 两 次 控 制 信 息 交 互 的 时 间 间 隔. 因 为 链 路 存 在 的 条 件 是 两 个 节 点 间 距 离 小 于 或 者 等 于 天 线 覆 盖 的 半 径 R, 可 见, 链 路 存 在 于 节 点 间 距 离 和 相 对 位 移 相 关 联.Ii 整 合 了 两 点 间 距 离 和 相 对 运 动, 反 映 了 链 路 的 稳 定 程 度,Ii 值 越 大, 表 明 链 路 稳 定 度 越 高, 最 高 为 1.ΔSm,n 0 表 示 在 Δt 时 间 段 维 持 同 向 运 动, 链 路 会 保 持 稳 定 ; ΔSm,n >0 表 示 在 Δt 时 间 段 维 持 反 向 运 动, 此 时 Ii (0,1), 表 征 稳 定 程 度. 在 空 间 内 某 点 的 干 扰 功 率 与 信 号 传 播 模 型 有 关. 为 了 验 证 方 便, 只 考 虑 由 于 距 离 所 引 起 的 传 播 损 耗. 设 定 干 扰 区 内 节 点 的 干 扰 值 为 : 1 interfn = dist(vx,vpu ) 就 网 关 而 言,fgw 函 数 用 网 关 通 信 距 离 表 征 权 值,interfgw 函 数 用 认 知 用 户 与 主 用 户 距 离 的 倒 数 表 征 网 关 对 主 用 户 的 潜 在 干 扰 程 度. 其 中 :V2hop 表 示 两 跳 网 关 集 合,V3hop 表 示 三 跳 网 关 集 合. 式 中 dist 表 示 求 距 离, [14-15] min 表 示 取 最 小 值, 当 然 也 可 以 根 据 关 注 问 题 的 不 同, 设 计 不 同 的 权 值 计 算 方 法. 2.2 算 法 设 计 fgw = ì dist(gx,vchs)+dist(gx,vchd) í, min(dist(gi,vchs)+dist(gj vchs))+ î, min(dist(gi,vchd)+dist(gj vchd)) ì 1 dist(gx,vpu ) interfgw = í 1 dist(gi,vpu ) + 1 î, dist(gj vpu ) gx V2hop gx V3ho p gx V2hop gi,gj V3ho p 基 于 认 知 无 线 电 的 MANET 网 络 中 虚 拟 骨 干 网 的 建 立 以 极 大 独 立 集 为 基 础, 寻 求 连 通 支 配 集. 算 法 分 为 两 个 过 程 : 第 一 阶 段 建 立 极 大 独 立 集, 第 二 阶 段 进 行 非 支 配 点 选 择, 构 建 连 通 支 配 集. 基 于 染 色 方 式 的 分 簇 算 法 实 际 上 是 一 种 建 立 极 大 独 立 集 的 方 法, 网 络 中 的 节 点 状 态 分 为 : 簇 首 状 态, (1) (2) (4) (5) (6) (7)

4 4 西 南 大 学 学 报 ( 自 然 科 学 版 ) htp://xbbjb.swu.cn 第 34 卷 簇 成 员 状 态 和 未 定 状 态. 建 立 极 大 独 立 集 的 算 法 流 程 如 下 : 1) 在 初 始 状 态 下, 所 有 节 点 都 处 于 未 定 状 态, 以 标 准 功 率 周 期 性 发 送 并 接 收 基 本 控 制 消 息, 并 计 算 权 值. 2) 同 时, 节 点 根 据 主 用 户 经 验 位 置 信 息 判 断 自 己 是 否 位 于 潜 在 干 扰 区, 并 计 算 出 权 值. 3) 节 点 间 权 值 交 互 比 较, 在 权 值 相 等 时 进 行 ID 值 比 较. 若 当 前 节 点 的 权 值 最 大 ( 权 值 越 大 则 说 明 越 适 合 成 为 簇 首 ), 则 升 级 成 为 簇 首. 并 要 请 邻 居 节 点 加 入 这 个 簇. 4) 若 当 前 节 点 处 于 未 定 状 态, 得 到 了 邀 请, 则 选 择 权 值 加 入 最 大 的 节 点 所 支 配 的 簇, 状 态 升 级 为 簇 成 员, 并 广 播 自 己 的 状 态 信 息. 5) 重 复 进 行 3) 和 4), 直 到 所 有 非 特 出 标 记 节 点 都 不 处 于 初 始 状 态. 构 造 连 通 支 配 集 的 算 法 流 程 如 下 : 1) 簇 首 获 取 与 邻 近 簇 首 的 所 有 网 关 信 息. 2) 对 网 关 进 行 排 序, 按 照 不 受 干 扰 网 关 优 先 于 受 干 扰 网 关 相 交 网 关 优 先 于 相 邻 网 关 的 类 型 顺 序 排 列. 若 同 属 于 一 类 网 关, 则 比 较 其 权 值, 如 上 面 描 述 的 那 样. 3) 网 关 选 择 与 信 息 通 告, 算 法 结 束, 直 到 每 个 簇 首 与 所 有 邻 近 簇 首 都 有 且 仅 有 一 个 网 关. 2.3 算 法 正 确 性 证 明 定 义 1 对 于 属 于 簇 C1 的 一 个 非 簇 首 节 点 u, 存 在 一 个 簇 C2 的 节 点 v 是 其 邻 居, 若 v 是 簇 首 节 点, 则 该 节 点 u 可 以 作 为 2 跳 网 关 ; 若 v 是 簇 成 员, 则 u,v 可 以 构 成 且 是 连 接 C1 与 C2 的 三 跳 网 关. 定 义 2 对 于 簇 C1 与 C2, 若 存 在 定 义 1 中 描 述 的 网 关, 也 就 是 簇 首 间 最 多 三 跳 可 达, 称 之 为 相 邻 簇, C1 与 C2 互 为 邻 居 簇. 定 义 3 对 于 节 点 v, 若 其 与 主 用 户 之 间 的 欧 氏 距 离 小 于 其 天 线 覆 盖 范 围 R, 表 示 可 能 对 主 用 户 造 成 潜 在 干 扰, 称 为 干 扰 节 点. 反 之, 若 与 主 用 户 之 间 的 欧 氏 距 离 大 于 其 天 线 覆 盖 范 围 的 节 点, 称 为 非 干 扰 节 点. 干 扰 节 点 构 成 的 集 合 称 为 干 扰 节 点 集 合, 非 干 扰 节 点 构 成 的 集 合 称 为 非 干 扰 节 点 集 合. 定 理 1 一 个 独 立 集 是 极 大 独 立 集, 当 且 仅 当 它 是 支 配 集, 极 大 独 立 集 必 为 极 小 支 配 集. 证 I 是 独 立 集 合, v I, 则 v 与 I 中 某 个 节 点 相 邻, 是 支 配 集, 反 之, 若 I 是 支 配 集 也 是 独 立 集, 则 对 于 任 何 v I 都 与 I 中 某 个 节 点 相 邻, 故 I vx 不 是 独 立 集, 所 以 I 是 极 大 独 立 集. v I,v 与 I- {v } 中 任 意 节 点 不 相 邻, 可 见 I 是 极 小 支 配 集. 引 理 1 任 意 一 个 节 点 都 属 于 且 只 能 属 于 一 个 分 簇. 证 一 个 节 点 所 属 簇 的 簇 首 要 么 是 它 本 身, 要 么 是 其 邻 居 节 点 中 具 有 最 优 权 值 排 序 的 节 点. 因 为 非 干 扰 区 内 节 点 是 全 序 集 合, 每 个 节 点 一 定 具 有 唯 一 的 权 值 排 序, 且 该 权 值 排 序 在 算 法 进 行 过 程 中 是 不 变 的. 当 其 成 为 本 地 最 优 权 值 排 序 节 点 时, 升 级 为 簇 首 并 对 邻 居 节 点 广 播. 若 节 点 在 干 扰 区 内, 且 是 非 干 扰 区 内 簇 首 节 点 的 邻 居, 则 属 于 其 邻 近 的 具 有 最 优 权 值 排 序 非 干 扰 区 内 簇. 若 节 点 在 干 扰 区 内, 且 不 邻 近 非 干 扰 区 内 簇 首 节 点, 由 于 干 扰 区 内 节 点 是 全 序 集 合, 而 全 序 集 合 的 子 集 带 有 整 个 集 合 的 次 序 限 制, 此 类 节 点 所 属 簇 的 簇 首 要 么 是 它 本 身, 要 么 是 其 邻 居 同 类 型 节 点 中 具 有 最 优 权 值 排 序 的 节 点. 若 两 个 节 点 权 值 恰 好 相 等, 则 认 定 具 有 lowerid 的 节 点 更 优 先. 引 理 2 簇 内 任 意 两 个 节 点 之 间 为 两 跳 可 达. 证 本 算 法 采 用 分 布 式 局 部 权 值 比 较 和 单 跳 染 色 方 式 进 行 分 簇, 若 存 在 节 点 v, 且 v 不 是 簇 首, 则 v 一 定 被 与 之 相 邻 的 一 个 簇 首 节 点 染 色, 即 v 必 然 邻 近 于 一 个 簇 首 节 点 u. 若 存 在 另 一 个 同 簇 的 节 点 v, 同 理, v 与 u 的 距 离 为 单 跳. 则 v 与 v 之 间 最 多 为 两 跳 可 达. 引 理 3 算 法 会 在 有 限 时 间 内 结 束. 证 认 知 无 线 电 MANET 网 络 中 任 意 一 个 节 点 要 么 是 干 扰 节 点, 要 么 是 非 干 扰 节 点, 算 法 开 始 时, 必 然 属 于 干 扰 节 点 初 始 状 态 集 合 Γi 或 者 非 干 扰 节 点 初 始 状 态 集 合 Γn, 由 引 理 1 可 知, 任 意 一 个 节 点 都 属 于 且 只 能 属 于 一 个 分 簇. 因 此, 集 合 Γi 最 终 会 成 为 空 集 合 Φ. 对 于 集 合 Γn, 一 部 分 节 点 被 相 邻 的 非 干 扰 节 点 集 合 中 的 簇 首 染 色, 另 一 部 分 经 过 簇 首 选 举, 也 必 然 成 为 簇 首 或 者 簇 成 员. 所 以, 分 簇 过 程 是 收 敛 的,Γi+Γn =Φ 时 停 止. 分 簇 阶 段 结 束 后, 转 入 网 关 选 择 阶 段, 由 邻 接 簇 具 有 较 小 ID 的 簇 首 选 取 最 优 的 网 关 在 候 选 网 关 集 合 中, 并 进 行 标 记 和 广 播. 网 络 中 节 点 数 量 是 给 定 的, 所 以 簇 首 数 量 是 有 限 的. 每 一 对 邻 接 簇 有 且 仅 有 唯 一

5 第 9 期 刘 昌 明, 等 : 基 于 认 知 无 线 电 的 MANET 网 络 中 虚 拟 骨 干 网 的 建 立 5 的 网 关.Γj 表 示 由 未 进 行 网 关 选 择 的 邻 近 簇 组 成 的 集 合,Γj 会 成 为 空 集 合, 因 此 网 关 选 择 阶 段 会 结 束. 引 理 4 算 法 能 构 建 连 通 支 配 集. 证 G=(V,E) 是 连 通 图. 先 证 明 簇 首 集 合 I 是 一 个 极 大 独 立 集. 利 用 反 证 法 : 假 使 簇 首 集 合 I 不 是 一 个 极 大 独 立 集, 即 存 在 节 点 v,u,v,u I, 并 且 v,u 相 邻. 根 据 簇 首 选 举 原 则, 处 于 初 始 状 态 的 节 点 集 合 中, 局 部 排 序 最 优 的 节 点 成 为 簇 首, 并 且 对 其 邻 居 节 点 染 色 使 其 成 为 簇 成 员. 不 存 在 v,u 同 时 最 优, 即 I 是 一 个 独 立 集.S=V -I, w S, 则 w 必 属 于 一 个 分 簇, 即 必 与 I 中 一 个 节 点 相 邻. 则 w I 不 是 独 立 集. 由 引 理 1 可 知 I 是 极 大 独 立 集 极 小 支 配 集. 令 S g 为 网 关 集 合,S g V -I, 再 证 明 SCDS =I+S g 是 连 通 支 配 集. 设 存 在 v,v I, 分 别 是 C1 C2 簇 的 簇 首, 若 v,v 间 最 多 两 跳 可 达, 由 定 义 2,C1 与 C2 簇 是 相 邻 的, 算 法 结 束 后, 相 邻 簇 间 有 且 仅 有 一 个 网 关, 即 簇 间 通 路 总 是 存 在 的 S g 是 连 通 支 配 集. 簇 首 集 合 I 是 极 大 独 立 集 合, 根 据 前 述 定 理 1,I 是 一 个 支 配 集. 任 何 节 点 v V -I, 必 然 与 I 中 的 某 个 节 点 u 相 邻. 假 设 G 是 一 个 简 单 连 通 图, 对 于 任 何 一 个 节 点 v I, 必 然 存 在 一 个 节 点 u I, 它 们 是 3 跳 可 达 的. 本 文 设 计 的 网 关 选 择 算 法 在 所 有 的 邻 接 簇 簇 首 之 间 加 入 网 关. 所 以, 对 于 三 跳 以 内 可 达 的 邻 接 网 关 对, 必 然 存 在 且 仅 存 在 一 个 网 关 使 之 连 通. 可 见, 图 G 的 导 出 子 图 G 是 连 通 的, 其 中 G 的 顶 点 集 合 V = I+S g. 这 表 明 算 法 不 会 改 变 连 通 性. 节 点 集 合 Scds=I+S g 是 一 个 连 通 支 配 集. 3 仿 真 设 计 与 结 果 分 析 由 于 常 用 的 网 络 系 统 仿 真 软 件 OPNET NS2 等 中 没 有 整 合 分 簇 算 法 和 认 知 无 线 电 模 块, 本 文 基 于 visualc++6.0 开 发 平 台 设 计 了 专 用 的 仿 真 程 序. 3.1 移 动 模 型 与 节 点 模 型 [16] 假 设 所 有 移 动 节 点 基 于 随 机 方 向 模 型 (Random Direction Model:RDM) 运 动, 并 在 固 定 时 间 段 内 Δt 内 维 持 方 向 和 速 度 不 变. 每 个 认 知 终 端 配 备 了 频 谱 感 知 模 块, 可 以 获 得 主 用 户 工 作 状 态 和 绝 对 位 置 信 息, 并 且 终 端 节 点 采 用 全 向 天 线, 网 络 中 不 存 在 单 向 链 路. 3.2 测 试 参 数 50 个 认 知 移 动 节 点 随 机 均 匀 分 布 在 m 区 域 内, 运 动 速 度 范 围 为 [2,18]m/s, 天 线 覆 盖 范 围 的 变 化 区 间 是 [0,60]m. 主 用 户 节 点 较 稀 疏 的 分 布 在 仿 真 区 域 内, 具 体 数 据 如 表 1 所 示. 表 1 仿 真 参 数 参 数 含 义 值 N 节 点 数 50 X*Y/m 仿 真 区 域 Vmax/(m s -1 ) 节 点 运 动 速 度 2~18 R/m 天 线 半 径 10~60 PU_number 主 用 户 数 1~5 干 扰 链 路 数 量 : 若 当 前 链 路 所 连 接 的 两 个 节 点 之 一 或 全 部 是 干 扰 节 点, 则 认 为 该 链 路 会 对 主 用 户 造 成 潜 在 干 扰. 潜 在 干 扰 链 路 意 味 着 当 主 用 户 工 作 时 候 需 要 出 让 临 时 占 用 的 主 用 户 授 权 频 段, 频 谱 切 换 不 仅 与 硬 件 有 关, 也 影 响 到 频 谱 发 现 算 法, 链 路 层 和 路 由. 因 此 会 带 来 明 显 的 延 迟 影 响 到 正 在 进 行 的 通 信. 重 入 簇 次 数 : 表 征 在 单 位 时 间 内 发 生 逻 辑 位 置 关 系 变 化 的 移 动 节 点 数. 虚 拟 骨 干 网 节 点 总 量 : 算 法 完 成 后, 构 成 虚 拟 骨 干 网 络 的 簇 首 集 合 和 网 关 集 合 所 包 含 的 节 点 数 之 和. 在 仿 真 测 试 中, 干 扰 链 路 数 量 越 低 说 明 通 过 优 化 拓 扑 减 少 了 认 知 用 户 对 主 用 户 的 影 响 ; 3.3 试 验 结 果 和 分 析 假 设 存 在 单 一 频 谱 空 穴, 图 1 描 述 的 4 种 拓 扑 形 成 算 法 自 上 而 下 分 别 是 : 算 法 1: 最 大 功 率 ; 算 法 2: [17] LiṉGerla 算 法 分 簇 且 簇 间 通 信 采 用 广 播 方 式 拓 扑 ; 算 法 3:LiṉGerla 算 法 分 簇 且 根 据 ID 号 选 择 网 关 方 式 ; 算 法 4: 本 文 新 算 法. 相 对 于 算 法 1 和 算 法 2, 因 为 引 入 了 簇 结 构, 删 除 了 同 簇 成 员 节 点 间 的 链 路, 链 路 总 数 减 少, 所 以 干 扰 链 路 数 量 有 明 显 下 降, 但 是 由 于 算 法 2 在 簇 间 保 留 了 冗 余 网 关, 所 以 相 对 于 采 用 了 网

6 6 西 南 大 学 学 报 ( 自 然 科 学 版 ) htp://xbbjb.swu.cn 第 34 卷 关 选 择 算 法 3 和 算 法 4 仍 然 有 较 多 的 干 扰 链 路. 本 文 算 法 在 簇 划 分 和 簇 间 网 关 的 选 择 上 都 考 虑 了 对 主 用 户 [18-20] 的 干 扰, 所 以 相 对 于 LiṉGerla 算 法 有 更 好 的 效 果. 图 2 给 出 了 虚 拟 骨 干 网 节 点 数 目 随 节 点 总 数 变 化 情 况, 由 此 可 见, 在 分 簇 完 成 后, 通 过 构 建 虚 拟 骨 干 网 的 方 式 进 行 簇 间 通 信 比 簇 首 广 播 方 式 可 以 显 著 减 少 参 与 转 发 的 节 点 数, 本 文 新 算 法 生 成 的 骨 干 网 节 点 数 目 与 基 于 最 小 ID 号 原 则 选 择 网 关 方 式 所 得 到 的 虚 拟 骨 干 网 节 点 数 目 基 本 一 致. 图 1 干 扰 链 路 数 随 主 用 户 数 变 化 情 况 图 2 虚 拟 骨 干 网 节 点 数 随 节 点 总 数 变 化 情 况 图 3 给 出 了 重 入 簇 次 数 伴 随 速 度 变 化 的 情 况, 反 映 了 网 络 拓 扑 的 稳 定 性. 从 图 中 可 以 看 出, 相 比 于 LiṉGerla 算 法, 节 点 高 速 运 动 时 基 本 一 致, 而 在 低 速 运 动 区 域, 本 文 新 算 法 的 性 能 更 优 越, 这 是 因 为 在 低 速 区 域, 可 以 通 过 选 择 相 对 稳 定 的 节 点 作 为 簇 首 来 减 少 运 动 对 逻 辑 位 置 的 改 变 造 成 的 影 响. 新 算 法 为 干 扰 节 点 集 合 和 非 干 扰 节 点 集 合 设 计 不 同 的 权 值 计 算 方 法 可 以 在 增 加 链 路 稳 定 性 与 降 低 对 主 用 户 的 干 扰 之 间 取 得 平 衡. 图 4 和 图 5 分 别 给 出 了 50 个 认 知 节 点 在 3 个 主 用 户 场 景 下 全 功 率 和 新 方 法 产 生 的 拓 扑 实 例. 图 中 用 图 3 节 点 重 入 簇 次 数 随 速 度 变 化 情 况 三 角 形 表 示 主 用 户 节 点, 圆 点 表 示 认 知 用 户 节 点, 图 中 圆 圈 表 示 簇 首, 十 字 星 表 示 网 关. 两 个 认 知 用 户 之 间 的 链 路 用 直 线 表 示. 由 图 可 知, 新 算 法 所 生 成 的 拓 扑 保 持 了 连 通 性, 结 构 更 稀 疏, 而 且 在 主 用 户 附 近 的 认 知 节 点 所 维 持 的 链 路 更 少. 这 说 明 新 算 法 生 成 的 拓 扑 结 构 可 以 尽 可 能 在 不 影 响 连 通 性 的 基 础 上 减 小 认 知 链 路 对 主 用 户 造 成 潜 在 干 扰 的 概 率, 从 而 避 免 主 用 户 开 机 所 触 发 的 频 率 移 交 所 带 来 的 延 迟 等 问 题. 同 时, 稀 疏 的 拓 扑 也 可 以 有 效 减 少 链 路 间 干 扰. 网 状 结 构 有 一 定 的 冗 余, 可 以 在 路 由 层 面 选 择 合 适 的 路 径. 图 4 最 大 功 率 拓 扑 图 图 5 新 算 法 拓 扑 图

7 第 9 期 刘 昌 明, 等 : 基 于 认 知 无 线 电 的 MANET 网 络 中 虚 拟 骨 干 网 的 建 立 7 4 总 结 认 知 无 线 电 技 术 是 未 来 无 线 通 信 的 发 展 方 向, 本 文 针 对 具 有 认 知 无 线 电 技 术 的 MENAT 网 络 共 享 主 用 户 频 段 的 通 信 方 式, 从 拓 扑 角 度 分 析 问 题, 融 合 了 认 知 无 线 电 特 点 和 MENAT 网 络 拓 扑 管 理. 整 个 拓 扑 构 建 以 簇 结 构 为 基 础, 针 对 处 于 干 扰 区 和 非 干 扰 区 的 节 点, 自 适 应 地 采 用 不 同 簇 首 选 举 和 网 关 选 择 方 案. 通 过 构 建 最 连 通 支 配 集 构 建 全 网 的 虚 拟 骨 干 网. 实 验 结 果 表 明, 在 维 持 分 簇 稳 定 性 的 同 时 降 低 了 对 主 用 户 的 干 扰, 具 有 一 定 的 实 用 价 值 和 前 瞻 性. 本 文 重 点 研 究 认 知 移 动 自 组 织 网 络 中 分 簇 式 拓 扑 管 理 模 式. 针 对 认 知 移 动 自 组 织 网 络, 提 出 利 用 认 知 节 点 的 频 谱 感 知 与 定 位 功 能, 建 立 基 于 主 用 户 工 作 状 态 等 空 间 和 时 间 信 息 的 虚 拟 骨 干 网. 虚 拟 骨 干 网 建 立 包 括 簇 首 选 举 和 网 关 选 择 两 部 分, 以 簇 首 为 锚 点, 通 过 选 择 受 主 用 户 影 响 较 小 的 网 关 节 点 寻 求 连 通 支 配 集, 建 立 虚 拟 骨 干 网. 参 考 文 献 : [1] BHARGHAVAN V,DASB.RoutinginadhocNetworksUsing Minimum ConnectedDominatingSets[C].IEEEICC 97,Montreal,Canada,Jun08-12,1997, [2] JMITOLA I,GQ MAGUIREJR.CognitiveRadio:MakingSoftwareRadiosMorePersonal[J].IEEEPersonalCommunications,1999,6(4): [3] FABRICETHEOLEYRE,FABRICE VALOIS.ASelf-OrganizationStructureforHybridNetworks[J].AdHocNeṯ works,2008,6: [4] JAMALN,ALKARAKI,AHMEDEK.EficientVirtuaḻBackboneRoutinginMobileadhocNetworks[J].Compuṯ ernetworks,2008,52(2): [5] 赵 春 晓, 王 光 兴. 稠 密 自 组 网 的 网 关 选 举 策 略 [J]. 计 算 机 学 报,2005,28(2): [6] HAN BO.Zone-Based VirtualBackboneFormationin WirelessadhocNetworks [J].Ad HocNetworks,2009,7: [7] IAN F AKYILDIZ,WON-YEO LEE,KAUSHIK R CHOWDHURY.CRAHNs:CognitiveRadioadhocNetworks [J].AdHocNetworks,2009,7(5): [8] BAO L,JJGARCIA-LUNA-ACEVES.Topology ManagementinadhocNetworks [C].Fourth ACM International Symposiumon MobileAdHocNetworkingandComputing (MobiHoc2003),Annapolis,Maryland,USA.June1-3, 2003: [9] CabricD,TkachenkoA,BrodersenR W.SpectrumSensingMeasurementsofPilot,Energy,andColaborativeDetection [C].MilitaryCommunicationsConference,2006.(MILCOM2006)Washington,DC,USA.Oct23-25,2006:1-7. [10] 李 洋, 董 育 宁, 赵 海 涛. 认 知 Mesh 网 络 的 动 态 分 层 图 路 由 模 型 及 路 由 策 略 [J]. 电 子 与 信 息 学 报,2009,3(8): LIYANG,DONGYU-NING,ZHAO HAI-TAO.YnamicLayereḏGraphRoutingModelandRoutingPolicyinCognitiveRadio MeshNetworks[J].JournalofElectronics&InformationTechnology,2009,3(8): [11] WEILIWU,HONGWEIDU.MinimumConnectedDominatingSetsandMaximalIndependentSetsinUnitDiskGraphs [J].TheoreticalComputerScience,2006,352(3):1-7. [12] 马 志 垚, 陈 巍, 曹 志 刚. 认 知 无 线 电 网 络 中 基 于 检 测 概 率 的 主 用 户 定 位 算 法 [J]. 北 京 邮 电 大 学 学 报,2009,32(2): [13] 王 建 新, 朱 贤 曼, 罗 玉 宏, 等. 移 动 自 组 网 中 任 意 时 刻 链 路 可 用 性 计 算 方 法 [J]. 电 路 与 系 统 学 报,2009,15(7):1-7. [14]GUO-XINGJIANG,ZHI-YAYANG.ADistributedClusteringAlgorithmBasedonClusterStabilityforMobileAdHoc Networks[C].2008IEEE4thInternationalConferenceon WirelessCommunications,Networkingand MobileComputing(WiCOM2008),Dalian,China,Oct,12-14,2008,1-6. [15]DHURANDHERSK,SINGH G V.WeightBased AdaptiveClusteringin WirelessAd HocNetworks [C].ICPWC

8 8 西 南 大 学 学 报 ( 自 然 科 学 版 ) htp://xbbjb.swu.cn 第 34 卷 2005.New Delhi,India,Jan,23-25,2005, [16]PAOLO SANTI.TopologyControlin WirelessAd HocandSensorNetworks [M].Hoboken:John Wiley & Sons, 2005: [17]STOJMENOVICI,SEDDIGH M,ZUNICJ.DominatingSetsandNeighborEliminatioṉBasedBroadcastingAlgorithms in WirelessNetworks[J].IEEETransactionsonParalelandDistributedSystems,2002,13(1): [18] 赵 宗 兵, 王 佰 胜. 智 能 天 线 在 空 空 导 弹 无 线 电 引 信 抗 干 扰 中 的 应 用 [J]. 四 川 兵 工 学 报,2010(6):17. [19] 江 振 华. 无 线 电 台 抗 复 杂 电 磁 干 扰 的 几 点 措 施 [J]. 四 川 兵 工 学 报,2010(6):4. [20] 胡 智 伦, 何 世 彪, 张 新 春. 认 知 无 线 电 中 基 于 干 扰 温 度 的 信 道 容 量 及 中 断 概 率 [J]. 重 庆 理 工 大 学 学 报 : 自 然 科 学 版, 2010(6): TheFormationofVirtualBackboneNetwork in MANETsBasedonCognitiveRadio LIU Chang-ming 1, LI Lin 1, FENG Weṉjiang 2, WU Di 2 1. ChongqingColegeofElectronicEngineering,Chongqing401331,China; 2. ColegeofCommunicationEngineering,ChongqingUniversity,Chongqing400030,China Abstract:Selectionsofclusteṟheadsandgatewayscanbemadeonthebasisofdynamicinformationbyiṉ tegratingcognitiveradiotechnologieswith MANETnetworkandadoptingthespectrumsensingfunction ofcognitivenodes.avirtualbackbonenetworkisestablishedwiththeclusteṟheadastheanchorpointby choosinggatewaynodesthatarelessafectedbyprimaryuserinquestofconnecteddominatingset.thus, thegeneratedvirtualbackbonenetworktakesclusteṟheadastheaccesspoint,withthegatewaybetween adjacentclustersbeingresponsiblefortheinteṟclusterconnectivity.basedonthecomparisonofweights, throughthesensingofthelocationoftheprimaryuser,thespatialdistributionareasofthecognitivenodes aredividedandassigneddiferent weights,thusrealizingpartitionprocessinginthenetwork.onone hand,thismaintainsarelativestabilityofthesuḇclustersin motion;ontheotherhand,itreducesthe probabilityofinterferencelinks.intheend,thevalidityofthealgorithmisverifiedbyasimulationanalysis. Keywords:mobileAdHocnetwork;cognitiveradio;virtualbackbonenetwork;topology;clustering 责 任 编 辑 汤 振 金

9 第 9 期 刘 昌 明, 等 : 基 于 认 知 无 线 电 的 MANET 网 络 中 虚 拟 骨 干 网 的 建 立 9