引言
　　随着传感器技术和无线通信技术的不断发展无 线 传 感器网络 的 相 关 研 究 备 受 人 们的关注 无线传感器网络具有十分广阔的应用前景在 军 事国防工农业城市 管 理生 物 医 疗环 境 监 测抢 险 救 灾远 程控制等许多领域都有重要的理论价值和巨大的实用价值
　　能源严格受限以及网络结构的动态拓扑性是无线传感器网络的两个特点 基于以上因素设计的路由协议 一 方 面 要求在网络能耗和数据可靠传输之间达到最佳平衡另 一 方 面要求节点在付出最小代价的前提下拥有动态组网能力 使 其进一步服务于数据的有效传输 无线传感器网络路由协议可以分为泛洪式路由协议 层次式路由协议 以 数 据 为 中 心 的路 由 协 议基于位置信息的路由协议和基于 的 路 由 协 议种 类 型 最 短 路 径 分层和方位路由等思想都广泛应用于 路由算法的设计 其中以寻求最短路径为目标的基于最小跳数的设计思想是近年来研究的热点方向
　　本文在分析原始最小跳数 路由协议的特点和存在的问题基础上 提出了一种基于跳数的无线传感器网络路由算法 该路由算法继承最小跳数路由协议 的 分 阶 段 方 法 将网络分为初始化阶段和数据传输阶 段 在 初 始 化 阶 段 延迟发送初始化分组避 免 冗 余 发 包减 少 组 网 能 耗 在 数 据 传 输 阶 段 以 父兄 弟 节 点 表 为 选 择 集选 取 唯 一 下 一 跳 通过自定义的权值计算公式来维持网络负载均 衡避免特殊节点过早死亡 在动态组网方面 节 点 实 时探测数据分组中的跳数字段当跳数值不在合理范围时 立 即重 置 自 身 跳 数 触 发 路 由 更 新 并有效地利用数据分组充当部分 路 由 功 能 在及时更新路由信息的同时最大程度地减小网络路由维护的开销 仿真验证了改进后的最小跳数路由协议在延长网络生命期负 载 均 衡低 路 由 开 销 等 方面 的 优 越 性
　　相关工作
　　无线传感器网络的路由算法研究是一个非常活跃的研究领 域基于跳数选择最优方案的路由思想是其中比较重要的研 究 方 向 目前国内外提出了许多基于跳数的路由协议及其改 进 思 想
　　最小跳数路由协议
　　最小跳数路由协议是在定向扩散算法和 洪 泛 算 法 的 基 础 上 引入跳数的概念而 发 展 起 来 的 由于其新颖的构思而备受关注 该 路 由 协 议在传 输 数 据 时 以 源 节 点 到 达 节点的跳数为根本依据确定 传 输 路 径 并且将路由过程理论性地分为梯度建立阶段和数 据 传 输 阶 段 为后续的一些改进思想奠定了基础
　　在梯度建立阶段 首 先 由 节 点 以 方 式 向 传感器网络发送查询分组查询分组中包含 节 点 和 距离 节点的最小跳数 等 相 邻 节 点 收 到节点的查询分组后 将 分 组 中 的 值 加 与 自 身 值初始 值 为 无 穷 大 进 行 比 较 如 果 新 的 值 小 于 原 来 存 储 的值则用新值替换原来存储的 值然后修改查询分组中的 节 点 和 值并将修改后的查询分组以 方式转 发 出 去若新值大于自身 值则 不 作 处 理 经 过 上 述处 理 过 程最终建立的最小跳数场如图 所 示在数据传输阶段 节点采集到数据之后 数 据 以 受 控方 式 传 向 节 点只 有 父 节 点 值 小 的 节 点 才 会 转发 数 据 分 组 这样数据在网络中就向着 节 点 的 方 向 移动如 图 所 示图 梯 度 建 立 阶 段 图 数 据 传 输 阶 段最小跳数路由协议以 节点周期性洪泛发起路由更新网络拓扑维护的开销巨大 并且在下次更新路由前新加入的节点不能及时有效地组网 在数据传输阶段 通 过 全 部 父节点 转 发 数 据 例 如 图 中 点产生的数据分组会由 节点转 发会在网络中产生过多冗余分组 加速了全网能量消耗 针对最小跳数路由协议的优点和存在的问题 国 内 外 研究者从多个角度提出了相关的改进方法相 关 改 进 方 案文 献 针 对 协 议在梯度建立阶段加以优化即节点接收到初始化分组后并不立即转发分组而 是 等 待 特 定时间后广播包含自身跳数信息的初始化分组从 而 减 少 该 阶段全网的冗余分组 但在数据传输阶段和动态组网方面没有提 出 优 化 策 略 文 献 在节点中使用邻居表来记录所有邻居 节 点 信 息 节点依照父节点 跳 数 比 自 身 小 兄 弟 节 点跳数与自身相等 子 节 点跳 数 比 自 身 大 顺 序 的 优 先 级随机挑选下一跳节点并转发数据分组 该策略虽然减少了数据传输阶段的冗余分组 增强了网络后期的数据传输质量但采用随机挑选中继节点的机制会减弱网络的负载均衡能力并且缺乏保证数据传输可靠性的机制 文 献 提 出 在 每 个节 点 打 开 时 向周围节点发送 报 文周围节点接收到报 文 后将各自的跳数值返回给新加入的节点来完成梯度的建 立 与 更 新 该算法能避免通过周期性洪泛实现网络组建而造成的不必要的资源消耗并解决节点实时加入网络的问题但 同 时 回 复 报文也增加了周围节点的能量消耗 文 献揭示了无线传感网中存在着热 点 区 域 以 及 瓶 颈 节 点这些节点由于承担过多转发任务而过早死亡影 响 了 整 个 网络的数据传输能力 该文献提出两次梯度重建机制 第 二 次梯 度 建 立 过 程 中 节点根据周围邻居的平均跳数来确立自身归 为 哪 一 梯 度 该设计思想避免了同一层节点能耗不均的情况但使用两次洪泛组网耗 能 较 大 无形中增加了数据到达的 跳 数虽然减少了瓶颈节点的负载 但数据传输中消耗的能量在一定程度上是增加的综 上 所 述针对目前基于跳数的无线传感器路由设计思想数据传输阶段的选路策略还可以继续优化 尽 可 能 地 选 择最优下一跳中继节点 在处理路由更新问题上以 往 的 设 计思想中并无过多提及 大 多 使 用 节点周期性洪泛或者普通节点维护路由更新 使得网络维护的开销很大改进算法设计改进后的算法称为 其适用环境是区域内均匀随机分布的一定数量的传感器节点唯 一 的 节 点 连 接 终端设 备 的 网 关 全网其他普通节点以 节点为最终数据接收 端 算法分为初始化阶段和数据传输阶段初 始 化 阶 段算法的初始化阶段主要完成梯度场的首次建立梯 度 场建立之前初始化 节 点 其 他 节 点 的 值 置 为 无穷 大并 建 立 父兄 弟 节 点 表 初始化阶段的流程描述如下节 点 发 起 组 网 过 程 广播发送一次初始化分组分组中包含主要字段 节 点 节 点 距 离 节 点 的 最 小 跳数 值节 点 当 前 剩 余 能 量 链 路 质 量 指 标 和接 收 信 号 强 度若节点首次接收到初始化分组则开启延时计时器将 分 组 放 入 备 选 队 列分 组 中 值 加 后 得 到 新值如果新值小于自身 则将新值赋予自身 否 则不做 处 理计 时 器 超 时 立即广播包含自身节点的 值 和 节 点信息的初始化分组查 看 备 选 队 列 将 队 列 中 值 比 自 身 值 小 的节点信息存入父节点表将 队 列 中 值 与 自 身 值 相 同的节点信息存入兄弟节点表对其他情况的节点信息则自动丢 弃 其 中父兄弟节点表中属性字段包含节点 值节 点 剩 余 能 量 值 值 等数 据 传 输 阶 段在数据传输阶段引入数据报文缓存和 机 制通 过数据分组标识机制来完成梯度的维护和更新进入数据传输阶段后 节点将周期性采集相关数据并 且转发 数 据 分 组 源节点首先以跳数衡量 即 父 节 点 优 先 在 跳数相同的情况下综合考虑节点剩余能量 链路状态和接收信号 强 度 的 因 素 并 通 过 权 值 公 式选出权值最大的父节点为最优中继节点来转发数据分组 使网络负载比较均衡 中 继 节 点 在 转 发数据分组后回复给源节点 分 组 节 点 收 到 父 节 点 的后将数据报文丢弃 更 新 父 节 点 表 否则从父节点表中选择另一个父节点或者从兄弟节点中选择一个节点来转发数据 如果节点转发数据分组之后的能量低于 则 将 该 节点从邻居节点表中删除该节点进入睡眠状态 在 数 据 传 输阶段选择唯一路径转发数据 避免了冗余分组 机 制 既是协议可靠性的保证 也可以协助及时更新路由表项由于节点能量消耗 新节点的加入等原因导致拓扑改变节点最初维护的路由梯度表不能有效地适用于整个网络生存期 在 算法中针对路由梯度维护更新方面设计了数据分组标识机制即在数据分组中设立布尔类型字段默 认 设 置 为 在进入数据传输阶段后 当 节 点接收到数据分组后 则 查 看 如 果 自 身 或 者自 身 表明节点接收到了父节点 兄 弟 节 点 子节点以外节点的数据网络拓扑已经发生了改变 此 时 触 发路 由 更 新从节点表中选择下一跳 设置下一待发送数据分组的 字 段 为 广播发送该分组 清 空 自 身 父 兄 弟节 点 表 邻 居 节 点 在 接 收 到 字 段 设 置 为 的 数据 分 组 后均 会 回 复 标明自己的邻居身份而 只 有 唯 一中继节点会转发该数据分组 以上路由维护和更新机制不仅可以有效保证路由的及时更新还可以有效处理新加入节点和节点梯度改变的动态组网问题 若有新节点加入 此 时 的情况是全网的初始化梯度建立阶段已经完成全 网 已 不 存 在初 始 化 分 组 但数据分组会在网络中流动由于新加入节点的值 设 为 无 穷 大 因此一定满足触发更新路由的条件所 以根据触发更新机制重新入网数据传输阶段的流程描述如图 所 示图 改进算法的数据传输阶段流程图仿真实验结果分析为对改进的路由算法设计进行验证 采 用仿 真 工 具 对 原 始 最 小 跳 数 算 法 定 向 扩 散 算 法和 算法进行了分析比较仿 真 实 验 中 测 试 区 域 节 点 数 目 为 个其 随 机 分 布 于节 点 周 围 节 点 信 道 延 迟 数 据 分 组 长 度节 点 丢 包 率 信息包最大路由跳数为 设置节点初始化能量为 个 单 位 量发 送 一 个 信 息 包 消 耗个 单 位 量接收一个信息包消耗 个 单 位 量节 点 能 量 小 于个单位量则失去通信能力图 的仿真结果反映在不同的发包频率下 种 算 法 的 数据包平均能耗情况 即网络中数据分组到达 节 点 平 均 所消 耗 的 能 量 协议采取受控的洪泛方式 使 得 数 据 流向 节 点能 耗 较 大 协议通过网络控制消息建立梯度后选择最佳路径传递数据 能 耗 方 面 较 协 议 有 所 优 化协议采用了父节点 兄弟节点双向传递 在 选 路 方 面加入了新的负载均衡机制 与其他两种协议相比 在 数 据 包 平均能耗上达到最优图 种算法平均能耗情况对比图 的仿真结果反映在不同的发包频率下 种 算 法 的 数据包网络维护代价情况 即全网产生的维护性分组 如 初 始 化分 组路 由 分 组 等 与全网产生的数据分组的比例值协议通过周期性的洪泛方式维护网络 代 价 较 高 协 议 采用请求驱动式的数据传送模式 网络维护代价较 协 议有 所 优 化 协议在梯度建立阶段采用延时发送初始化分组避免冗余 组 网 后通过侦听接收到的数据分组中的跳数 信 息触 发 路 由 更 新 并且以数据分组作为路由更新包的一部 分最大程度上降低了路由维护代价图 种算法网络维护代价情况对比图 的仿真结果反映在不同的发包频率下 种 算 法 的 网络 生 存 时 间 综合评定各个协议性能 协 议 在 增 加网络生存时间上优于其他两种协议但 同 时 也 看 到 随 着 发 包频 率 的 增 加 各个协议所维持的网络生存时间趋于相同 原 因在于网络中信息包密度过大各种保障机制的优势不再明显图 种算法网络生存时间对比结束 语 本文通过分析以往基于最小跳数的无线传感器路由协议的优点和不足 提出了自己的改进方案 最 后 通 过 仿真实验在协议性能上与 协议进行了对比 仿 真 结果表明改进算法在延长网络生命期负 载 均 衡低 路 由 开 销 等方面具有优越性 针对大规模网络环境以及网络拓扑实时变化的动态网络环境的可靠路由协议设计 将是下一阶段的研究 重 点参 考 文 献谭 励无线传感器网络理论与技术应用 北 京机 械 工 业 出版 社余 勇 昌韦 岗无线传感器网络路由协议研究进展及发展趋势计算机应用研究赵 强 利蒋 艳 凰徐 明无线传感器网络路由协议的分析与比较计 算 机 科 学算 法 采 用 主 动 式 修 复 策 略以有效地提高分组投递率 图显示了各种算法随着暂停时间变化的分组投递率算法的数据较平缓 原因也是该算法的能量均衡和移动预测机 制图 随时间变化的分组投递率 图 随暂停时间变化的平均分 组 投 递 率图 显示了节点数量与路由控制开销之间的关系 随 着节 点 数 量 增 加 链路复杂性急剧增加 因 此 路 由 开 销 也 增 加算法需要进行移动预测和能量均衡控制 因 此 所 需的路由开销也比其他算法多一些 算法的总平均路由 开 销 为 算法的总平均路由开销为虽 然 增 加 了 但是与平均传输功率网络生命期和分组投递率等其他性能提高相比较也 是 值 得 的图 不同算法的路由开销通过仿真不同节点规模下网络的性能比较 可 以 发 现具 备 比 较 优 秀 的 性 能 可以较好地适应移动网络拓扑 的 需 要 牺牲了一定的路由开销带来了网络平均生存周期和分组投递率的较大提升
    结束 语
    节省节点的能量 延长网络工作时间是无线网 络 设 计 的 主 要 问 题 算法通过评价链路的稳定 性在路由选择过程中选取稳定性更高的链路和主动式路由 修 复有效地避免了由于节点移动导致的链路断裂对数据传 输 的 影 响 同时使用能量均衡机制避免了部分节点过度的能量 消 耗 通过仿真实验也表明 与其他算法相比 该 算 法 在更 好 地 适 应 网络节点移动变化和节点的能量有效使用 的 同 时减 少 了 链 路 失 效 提高了分组投递率 延 长 了 网 络的 生 命 周 期
    参 考 文 献沈 中常 义 林无 线 网络中保留最小能量路径的拓扑控制算 法 西 安 电 子 科 技 大 学 学 报自 然 科 学 版王 文 艳王 东拓 扑 控 制 对 网络能耗及生存期的影响分析 计算机工程与应用王 炫李 建 东拓 扑 控 制 对 网 络 性 能 的 影 响 计 算 机工 程 与 应 用刘 少 伟罗 丹 彦能量均衡的无线传感器网络拓扑控制算法电子科技大学学报陈 辉巨 永 锋基 于 能 量 均 衡 的 网络拓扑控制技术研究计算机与数字工程彭 海 英蔚 承 英唐 红无线自组网分级结构的性能与可扩展性研 究 重庆邮电大学学报 自 然 科 学 版段 文 芳齐 建 东无线传感器网络最小跳数路由算法的研究计算机工程与应用李 应 娣单 志 龙无线传感器网络定向扩散路由协议研究 计算机技术与发展