无线自组网是一种多跳 无固定节点的动态网络 节 点常常处于移动状态 并且节点的运动 能量和带宽通常都是受限 的 如何提高节点和网络整体的正常工作时间 减 少 通 信干 扰是当前研究关注的热点 采用拓扑控制优化网络的拓扑结 构可以减少网络节点能量消耗
　　近 年 来国内外的研究人员提出了多种拓扑控制算法提 出 了 拓 扑 控 制 算 法 该 算 法 是 基 于 图 论 中 的在网络拓扑中的应用 提出使用最小流失率 和 条 件 最 小 流 失 率作为网络路由评价参数以扩展节点电池的使用时间和路径的工作时间在无线自组网中 节点通常是处于运动状态的相 邻 节 点之间的联通可能随着节点的运动而终止 链 路 发 生 断 裂 路 径失 效 目前的路由协议会重启路由发现机制 更 新 路 由表但这样会较大地增加分组延迟对网络的传输效率影响很大 如何保证有效路径可用时间文 献 提 出 使 用 备 份 节 点的 机 制在备份节点中保存一部分的路由信息可 用 于 链 路 出错 时 的 恢 复 文 献 也提出了通过接收传输功率的强度来计算链路的有效时间 通过预测链路的失效时间提 前 进 行路 由 重 建 操 作
　　现 有 的 算 法 为了减少能量消耗 缩短节点传输距离 从而延长网络工作时间关注节点的传输能量消耗 在 保 证 网络 连 通 的 前 提 下 考虑到节点移动对链路稳定性的影响和网络中节点能量的平衡消耗本文提出了一种基于能量均衡和节点移动预测的无线自组网拓扑控制算法该算法通过平衡网络节点能量和预测节点之间链路的 工 作 时 间 有效延长了网络的工作时间
　　能量损耗模型和节点移动模型
　　无线自组网模型设定为网络中有 个 节 点 这 个 节点构成了二维平面中的节点集 网络可以简化为一个有向图 其 中 是 点 集 合 是 边 集 合能 量 损 耗 模 型假设网络的每个节点都有唯一编号并且节点使用全向天线发 射 功 率 可 以 自 由 调 节 即 网 络 节 点 均具有相同的最大功率 每个节点都有初始能量并 可 以随时提供剩余能量信息 是 中 的 任 意一条 边 表 示 从 节 点 发送一个数据分组到节点 的 能 量消 耗 节 点 采 用 无 线 传 输 模 型 模 型 参 数发送数据节点和接收数据节点的功率关系为式 中 表示发射天线的增益 表示接收天线增益 天 线 之间 的 距 离 为 表 示 波 长 为系统损耗因子算法的目的是降低网络中节点的总能量消耗和通过对链路失效的预测来减少丢失发送的数据分组 节 点在 时 间 段 内的能量消耗为式 中 和 表 示 节 点 在当前时刻之前 时 刻和当前时刻的剩余能量节 点 在当前的能量剩余评价指数为式 中 表示当前时刻之前的 时 间 段 节 点 的 能 量 消耗 表示节点的初始能量 最 大 能 量节 点 运 动 模 型无线自组网络中的节点是自组织的移动节点假 设 每 个节点都有自己的运动方向和速度 任何两个相邻节点之间可以 依 据 式 创建数据链路的条件 只有在一定的距离范围内节点才可以直接通信 当链路建立以后 随 着 节 点 的 移 动相邻节点的距离随时发生变化当节点间相邻距离超过最大传 输 距 离 时 链 路 发 生 中 断 通 过 此 链 路 的 数 据 丢 失 因 此如果可以预测链路失效时间在链路失效之前就进行拓扑重建可以有效地提高数据传输效率如 图 所 示假 设 节 点 的 坐 标 为运 动 速 度 为 节 点 的 运 动 方 向 为 节 点 的移 动 方 向 为 节 点 的数据传送距离为 当 前 时 刻 节 点 之后 的 之 间 的 距 离 为图 节点运动模型图假设节点一直保持匀速运动 直到碰到测试区域的边界后改变方向继续运动 在当前时刻之后的 时 刻节 点 的 距离可 根 据 式 计 算如 果 节点之间的链路仍然 有 效否则链路将失效 需要重新建立路由拓扑控制算法算法的目标是均衡网络节点耗能和有效降低链路 失 效 在 构 建 拓 扑 时 综合考虑通信节点剩余能量和节点的运动速度和方向 对节点移动中发生的路径断裂进行预测在路径失效之前就使用备份路径或者重新建立链路 达 到 了能量均衡效果的同时避免了网络中某些关键节点担当数据转发任务时能耗过大的问题而且可以在较大程度上降低路径失 效 率从而延长了节点工作时间和网络生命期 降 低 了 数 据分组的传输时延定 义定 义 相邻节点链路稳定性指数设 节 点 分 别 以 均 匀 速 度 沿 着 固 定 的 方 向 移动节点之间的相对距离可能随着节点的运动发生变化 而 节点之间的距离的变化取决于节点的运动速度和运动方向 因此定义相邻节点链路稳定性指数是 关 于 时 间 节点运动速度和方向的函数 该 指 数越 大说明链路断裂的可能性越低定 义 相 邻 节 点 间 链 路 权 值 相 邻 节 点 间的链路权值取决于相邻节点的能量 相互位置以及相互运动的 趋 势在 式 中 是 权 值 是节点的初始能量节 点 的当前剩余能量用 表 示定 义 路 径 总 权 重 在 从 起 始 节 点 到 终 点 的 路 径上经 过 节 点 表 示 为该路径上的总权值可表示为各节点的链路权值的和算 法算法设计的目的是均衡无线自组网中节点的能量延长网络生命周期预测相邻节点之间的链路稳定性对将要失效的链路及时更新路由减少数据分组发送失败的数量降低端到端延时 在构建网络拓扑过程中 节 点 获 取 局 部网 络 拓 扑 信 息 以保证拓扑结构强连通性和最小代价特性 算法包括信息搜集 创建网络拓扑结构 网 络 拓 扑 优 化 和网络拓扑维护等 个 主 要 阶 段信 息 收 集 阶 段当节点加入网络时 首 先 广 播 数 据 分 组 该 数 据分组中有节点的主要信息 具体包含节点的位置 当 前 能 量 以及节点当前运动的方向和速度等 当网络中的其他节点收到数 据 分 组 后 返 回 数 据 分 组 并 将 节 点 信 息加入当前节点的邻节点信息表中 收 到 反 馈 的 数据 分 组 后源节点也将信息加入邻节点信息表中 这 两 个 节点的路径就可以建立 根据获取的节点信息和节点相互速度及位置计算节点间路径权重拓 扑 构 建算法的目标是构建能够预测链路失效和延长网络生命周期的网络拓扑节点使用最大发射功率发现物理邻节 点对 于 任 意 节 点 计 算 节 点 与 相 邻 节 点 的 权 值得到一个带权重的无向图 根 据 各条 边 的 权 重 每个节点构建本地最小生成树所 有 节 点 的 最 小生成树构成了网络的拓扑结构 对 中 的 每 一条边 计算在拓扑结构 中的最短路径的距离若 则 将 加 入 最 后 构 建 得到 符 合 属 性 的 网 络 拓 扑 构 架 拓 扑算法的伪代码如下拓 扑 优 化 阶 段拓扑优化阶段包括两方面 链路双向化和传输功率调节链路双向化是通过对拓扑构建中出现的单向链路进行双向化处 理传输功率调节是以相邻的一跳邻居节点最远的链路距离能够传输为标准 并 按 照 标 准 的 功 率 设 定 发 送 功 率其目的是为了保证在节点移动过程中 即使相邻节点的运动相 互 远 离 也仍然可以保证在一定时间阶段内其链路上能有效 地 传 输 数 据 而不会立刻发生链路断裂拓 扑 维 护 阶 段为了有效避免节点因能量耗尽无法与相邻节点通信或者相邻节点移动导致距离超出传输半径会使相邻链路断裂在拓扑结构中节点定期进行拓扑维护计 算 相 邻 链 路 的链 路 稳 定 指 数 和 链 路 权 值 根 据 链 路 权 值 链路的 稳 定 程 度 决定是否需要重新创建链路链 路 拓 扑 构 架链路权值的最低取值为 通 过 该 步 骤 可以预测将要失效的 链 路提前建立后备链路以保证拓扑结构中的节点之间的正 常 通 信链路维护策略伪代码仿真实验仿真场景和参数为 了 验 证 算 法 的 有 效 性 利 用 仿 真 算 法的 性 能在 该 网 络 模 拟 平 台 上 仿 真 考 察 了和 算 法 的 性 能仿真环境参数设置如表 所 列表 仿 真 参 数 设 置参 数 取 值区 域最 大 发 射 功 率初 始 能 量最 大 传 输 距 离数据分组发送速率节点最大运动速率数 据 分 组 大 小仿 真 时 间在 仿 真 环 境 中 随 机 产 生 个 业 务 流 仿 真 时 间为 算 法 周 期 设 为 在计算链路权值的式中仿真结果及分析仿 真 试 验 中 主要考察了节点平均传输功率网 络 生 命 周期分组投递率和路由开销等参数 为保证仿真结果的稳定性进 行 次 实 验以平均值作为最终结果统计节点平均传输功率是网络节点工作周期内平均消耗的能量表示网络的整体能耗情况 该 值 越 低 表 示 算 法 的 能 量 控制 越 好网络的正常生命周期也会越长 图 表 示 不 同 算 法在不同节点规模下的节点平均传输功率性能 种 主 要 拓 扑算法的平均传输功率均随着节点数量的增加而递减 原 因 是随 着 节 点 增 加 相邻节点之间的链路长度相应减小链 路 之 间传输数据所需的功率也随之降低 算法采用了能量均衡算法对链路的维持时间进行有效预测 降低了因节点运动产生链路断裂后重新创建链路的能量消耗因 此 平 均 节 点功 率 较 低通过有效的网络节点能量均衡 算 法 降 低 了 剩余能量较低的节点参与路由和数据传输的概率所 以 与 其 他算 法 相 比较好地实现了能量的均衡消耗使平均节点功率最小网络生命期是整个拓扑网络正常工作的周期在 本 算 法中将网络生命定义为直到网络中有 的 节 点 由 于 能 量 耗尽而停止工作的时间 从 图 的仿真结果看出 算法可以提高网络生命周期 暂 停 时 间 为 表 示 节 点 连 续 运 动暂停时间越长表示节点静止状态持续时间越长 算法基于节点运动预测和能量均衡策略 通过较低的节点平均发 射 功 率 避免了网络中某些节点过多参与数据收发而导致过早地耗尽能量 提高了网络的生命期图 节点数量与平均传输功率 图 暂停时间与网络生命时间分组平均投递率表示源节点发出的数据分组能被目的节点接收的数量比率 该 数 值 越 高 则网络的可靠行越好 图和 图 显示了分组投递率的数据 图 显示了随着网络工作时间变化的分组投递率网络开始工作时 节 点 的 能 量 充 足没 有 拥 塞 的 情 况 因此投递率非常高随 着 工 作 时 间 延 长种算法的投递率都逐步下降但 算法的投递率下降较 慢原因是该算法有效的能量均衡可以避免部分节点过早耗 尽 能 量 而 失 效 通过移动预测和链路重建机制算 法 采 用 主 动 式 修 复 策 略以有效地提高分组投递率 图显示了各种算法随着暂停时间变化的分组投递率算法的数据较平缓 原因也是该算法的能量均衡和移动预测机 制图 随时间变化的分组投递率 图 随暂停时间变化的平均分 组 投 递 率图 显示了节点数量与路由控制开销之间的关系 随 着节 点 数 量 增 加 链路复杂性急剧增加 因 此 路 由 开 销 也 增 加算法需要进行移动预测和能量均衡控制 因 此 所 需的路由开销也比其他算法多一些 算法的总平均路由 开 销 为 算法的总平均路由开销为虽 然 增 加 了 但是与平均传输功率网络生命期和分组投递率等其他性能提高相比较也 是 值 得 的图 不同算法的路由开销通过仿真不同节点规模下网络的性能比较 可 以 发 现具 备 比 较 优 秀 的 性 能 可以较好地适应移动网络拓扑 的 需 要 牺牲了一定的路由开销带来了网络平均生存周期和分组投递率的较大提升
　　结束 语
　　 节省节点的能量 延长网络工作时间是无线网 络 设 计 的 主 要 问 题 算法通过评价链路的稳定 性在路由选择过程中选取稳定性更高的链路和主动式路由 修 复有效地避免了由于节点移动导致的链路断裂对数据传 输 的 影 响 同时使用能量均衡机制避免了部分节点过度的能量 消 耗 通过仿真实验也表明 与其他算法相比 该 算 法 在更 好 地 适 应 网络节点移动变化和节点的能量有效使用 的 同 时减 少 了 链 路 失 效 提高了分组投递率 延 长 了 网 络的 生 命 周 期
　　参 考 文 献沈 中常 义 林无 线 网络中保留最小能量路径的拓扑控制算 法 西 安 电 子 科 技 大 学 学 报自 然 科 学 版王 文 艳王 东拓 扑 控 制 对 网络能耗及生存期的影响分析 计算机工程与应用王 炫李 建 东拓 扑 控 制 对 网 络 性 能 的 影 响 计 算 机工 程 与 应 用刘 少 伟罗 丹 彦能量均衡的无线传感器网络拓扑控制算法电子科技大学学报陈 辉巨 永 锋基 于 能 量 均 衡 的 网络拓扑控制技术研究计算机与数字工程彭 海 英蔚 承 英唐 红无线自组网分级结构的性能与可扩展性研 究 重庆邮电大学学报 自 然 科 学 版段 文 芳齐 建 东无线传感器网络最小跳数路由算法的研究计算机工程与应用李 应 娣单 志 龙无线传感器网络定向扩散路由协议研究 计算机技术与发展