摘要 : 该文在 DD 协议的基础上 , 设计了一种基于跳 数值的 梯度建 立机制 , 使数 据沿着跳 数最小 的 路径传输。而且还设计了一 种当节点移 动时 , 梯度 域可以进 行自我 调整的 机制 , 尽量去 找一条 或 多条代价 小的路径 , 保证了网络传 输的健 壮性。通 过程序仿 真实验 , 证 明了改进 的方案 比传统 的 定向扩散路由协议减少了网络开销 , 延长了网络整体 的生存周期。 关键词 : 无线传感器网络 ; 定向扩散 ; 梯度 ; 节点移动 中图分类号 :TP393 文献标识码 : A 文章编号 : 1001- 9146( 2008) 05- 0135- 04
3
仿真及结果分析
采用 C+ + 程序来模拟、 比较和分析改进的方案与原 DD 协议的性能, 设计了 5 个不同规模的网络,
节点数分别从 50 到 250, 每次增加 50 个节点 , 所有的节点随机部署在一个 200m200m 的区域中。通过在 规定的仿真时间内, 所有节点转发数据包的次数进行评测, 并分为节点静止和节点移动两种情况。仿真 结果如图 3、 4 所示。
收稿日期 : 2008- 07- 20 基金项目 : 浙江省科技计划重点资助项目 ( C21G3230005) , 浙江省新 苗人才计划资助项目 ( R40G2040097) 作者简介 : 吴建荣 ( 1981- ) , 男 , 浙江湖 州人 , 在读研究生 , 计算机软件与理论 .
[ 4]
。LEACH 通过随机选择簇头节点 , 平均分担中继通信任务 , 实现网络生命周期的延
图 1 无线传感器网络结构 2. 2 支持节点移动 网络中节点的梯度信息依赖于拓扑结构, 任何拓扑的改变都会使得相关节点的梯度域发生错误。 本协议中当然可以通过周期性发送 interest 数据包来维护网络的路由信息 , 现在讨论的是数据发送阶 段, 某个节点发生位置的改变 , 如何通过局部信息的交换来维护网络的路由信息。 网络结构图如图 2 所示 , 在数据稳定传输时 , 突然发生某个节点移动, 如何让它与其邻居节点交换 信息来重构网络拓扑 , 并继续参与到数据传输的任务中来。图 2 中显示, 节点 E 发生了位置的改变 , 而 此时, 网络中正在针对某个 interest 进行数据传输。首先节点将停止数据传输的任务, 同时清空 interest 对应的所有梯度信息。节点一旦停止移动, 又一次确定了其位置, 则通过和其所有的邻居节点交换信 息, 来重新配置自己的梯度。 于是节点 E 通过向节点 A、 C、 F 发送 REQ 数据请求包 , 同时会有一个延时 , 来等待邻居节点的回复 包 REP, REP 是关于当前正在进行的 interest 相关的梯度信息 , 而节点 A 、 C、 F 只需回复其中跳数值最小 的梯度信息给节点 E 。节点 E 在延时结束之前 , 会将收到的 REP 进行一个比较 , 将其中跳数值最小的节 点作为其数据传输的下一跳, 并将跳数值加 1 后保存在自己的梯度域中。然后节点 E 会判断所有从邻 居节点收到的跳数值是否存在大于最小跳数值加 2, 如果存在, 则节点 E 发送带有自身跳数值和要求继 续转发信息的 REQu 数据包给这些节点, 这些节点会根据收到的数据包来建立指向 E 的梯度 , 并继续转 发该路径信息, 相当于告诉邻居节点这里有一条更好的路径 ; 否则, 节点 E 只是发送一个带有自身跳数 信息的数据包 REQh 给跳数值最大的节点 , 该节点会建立指向 E 的梯度 , 而不会继续转发。所以图中的
4
结
论
本文在 DD 协议的基础上, 提出了一种基于跳数的梯度机制, 并重点阐述了当数据稳定传输时 , 如 果发生节点移动 , 节点的梯度域是可以通过与邻居节点交换信息进行自我调整, 在下一次 interest 扩散 之前, 尽量去寻找一条代价小的路径 , 体现了网络健壮性的特点。下一步的工作 , 是在本方案的基础上 如何将分簇机制有效的结合进去, 并在路径选择过程中重点考虑节点剩余能量的情况。
第 5期
吴建荣等 : 定向扩散路由协议的改进分析
137
图 2 局部网络维护 节点 F 在收到节点 E 发来的带有跳数值的 REQh 后, 是不会进行转发的。通过这个局部的信息交换后, 建立了一个 F E A 新的数据传输路径。 图 2 中可以看出, 当节点 E 移动后, 凡是梯度列表中有指向该节点的梯度信息都必须删除, 所以节 点 G 和 H 要做这样的处理。当节点 G 和 H 发送数据给节点 E 时, 在等待一定的延时之后, 如果没有收 到回复 , 或者可以通过数据的重发机制, 来判断节点 E 可能发生了移动或者发生了故障, 从而需要将其 从梯度列表中删除。这样的话 , 节点 G 的最小跳数值没有改变, 而节点 H 的最小跳数值由原来的 3 改 为 4。
136
杭 州 电 子 科 技 大 学 学报
2008 年
上发。文献 5 是将分簇的思想引入到 DD 协议中, 以此来简化网络拓扑, 抑制洪泛的传播。DD 协议中 提到了一种很重要的概念 梯度, 文献 6 中定义的梯度有别于 DD, 它是指相邻节点跳数的差值作为两 节点间链路的梯度值 , 路由时 , 选取与该节点相连的最大梯度对应的路径进行数据转发。
第 28 卷第 5 期 2008 年 10 月
杭州电子科技大学学报
Journal of Hangzhou Dianzi University
Vol. 28, No. 5 Oct. 2008
定向扩散路由协议的改进分析
吴建荣, 万 健, 徐向华
( 杭州电子科 技大学网格与服务计算技术实验室 , 浙江 杭州 310018)
138
杭 州 电 子 科 技 大 学 学报
2008 年
情况下 , 如果发生移动的节点在被加强的路径上面 , 而且又没有梯度的自我配置机制, 就会使数据包沿 着跳数值比较大的路径转发, 如果能进行梯度的重新配置 , 还是会尽量去寻找一条代价小的路径 , 有利 于能量的有效利用。实验数据表明 , 在不同网络规模下, 改进方案比原 DD 协 议性能平均提高了 22. 32% 。
参考文献
[ 1] [ 2] [ 3] Akyildiz IF, Su W, Sankarasubramaniam Y, et al. Wireless sensor networks: a survey[ J] . Computer Networks, 2002, 38( 4) : 393- 422. Intanagonwiwat C , Govindan R , Estrin D, et al. Directed diffusion for wireless sensor networking[ J] . IEEE/ ACM Transaction on networking , 2003, 11( 1) : 2- 16. Kulik J, Heinzelman WR, Balakrishnan H. Negotiation based protocols for disseminating information in wireless sensor networks [ J] . Wireless Networks, 2002, 8( 2- 3) : 169- 185. [ 4] Heinzelman W, Chandrakasan A, Balakrishnan H. Energy - efficient communication protocol for wireless microsensor networks [ C] . Hawaii: Proc. of the 33rd Annual Hawaii Int l Conf. on System Sciences. Maui: IEEE Computer Society , 2000: 30053014. [ 5] [ 6] Xinhua L, Fangmin L, Hailan K, et al. The Study of Directed Diffusion Routing Protocol Based on Clustering for Wireless Sensor Network[ C] . Dalian: WCICA 2006, the Sixth World Congress on Intelligent Control and Automation, 2006: 5120- 5124. Ye F, Zhong G, Lu S, et al. GRAdient Broadcast: A Robust Data Delivery Protocol for Large Scale Sensor Networks[ J] . ACM Wireless Networks, 2005, 11( 2) : 285- 298.
0
引
言
[ 1]
无线传感器网络 ( wireless sensor networks, WSN) 由大量低成本、 低功耗和自组织的传感器节点组成, 能够协作地实时监测、 感知和采集各种环境或监测对象的信息 。在环境监测、 智能家居、 军事国防、 生 物医疗等领域均有广阔的应用前景。由于 WSN 自身在能量供应、 数据处理以及通信能力上的限制 , 其 路由协议与传统的路由协议有较大的不同, 能量的有效利用是 WSN 路由协议设计的重要目标。WSN 路由协议的研究经历了从传统的基于需求的路由机制到数据驱动的路由机制两个阶段, 出现了洪泛、 谣 传、 定向扩散( Directed Diffusion, DD) 等多种不同类型的路由协议 [ 2] 。本文在 DD 协议的基础上 , 提出了 一种基于节点跳数值的梯度机制, 重点讨论了在节点稳定传输数据时, 发生了节点移动 , 如何与其邻居 节点交换信息, 进行梯度域的自我调整。
图 3 节点静止的情况 图 4 节点移动的情况 图 3 表明在不同网络规模 , 节点保持静止的情况下, 原 DD 协议和改进的方案, 所有节点数据包转 发次数的比较。由于网络中未发生节点的移动, 只是改进的方案在加强路径后 , 数据包是沿着跳数值最 小的路径进行传输, 所以数据包的总的转发次数相对较小, 但相差不大。实验数据表明 , 在不同网络规 模下 , 改进方案比原 DD 协议性能平均提高了 9. 59% 。 图 4 也是在不同的网络规模下, 每隔一个时间段 , 就随机选择若干个节点使其发生移动, 在这样的
2
2. 1
梯度机制
梯度建立阶段 首先 , Sink 节点向全网发送一个 interest 数据包, 其中包含一个转发次数字段, 初始值为 0, 由 Sink 节
点设定。这里假设针对 Sink 节点的某一次 interest 洪泛过程。 interest 通过广播逐级扩散后, 大致过程如 图 1( a) 所示, 每个节点都在本地保存一个 interest 列表 , 收到 interest 的节点缓存信息 , 并建立与其对应的 梯度域, 梯度的建立过程如图 1( b) 所示。梯度值包括发送节点的标识符和对应节点的跳数值, 用 inter est 中的转发次数加 1 来设置跳数值 , 再用新的跳数值来更新 interest 中转发次数。在收到 interest 到将 其转发 , 其间有一个短暂的延时 , 当前节点会建立其各个邻居的梯度信息, 最后只是转发其中一个跳数 值最小的 interest 数据包。
1
相关研究
WSN 路由协议是当今的研究热点之一, 到目前为止, 已经提出了很多经典的路由协议。SPIN 是一
种以数据为中心的自适应路由协议 , 其目标是使用节点间的协商机制和资源的自适应机制, 解决洪泛中 出现的内爆 问题和 重叠 现象[ 3] 。节 点在 传送数 据之 前进 行协 商, 这个可 以确 保传 输有 用的 数据。 LEACH 协议 , 是第 一种基 于分簇 结构 和分层 技术的 路由协 议, 其他基 于分簇 的路 由协议 大多 是由 LEACH 发展而来 长。 文献 2 中提到的 DD 协议 , 是基于数据为中心的、 查询驱动的路由协议, 很多基于数据为中心的路 由协议都是在 DD 的基础上提出的。网络中的节点只需要保存邻居节点的信息, 而不用维护整个网络 的信息; 数据的发送是基于Fra Baidu bibliotek户的需求 , 由 sink 节点向全网广播查询任务 , 而不是监测区域有数据就会