第 32卷 第 20期 、勺L32 A自 20 ·网络 与 通 伯 · 计 算 机 工 程 Computer Engineering 2006年 10月 October 2006 文盆幼号:1000-3428(2006)20--0123--03 文做标识码.A 中.分类号:TP393 无线传感器网络路 由协议及仿真 王永玲 ，郭爱煌 (同济 人学 电 r-与信 息工程 学院 ， 卜海 200092) 摘 要:路山协议是无线传感器网络研究的关键技术之一，以数据为中心的路由协议是目前研究的热点。摧于局域性更新机制的原理，改 迸了以数据为中心的 Directed Diffusion协议，用C++语言描述了协议的算法，在 NS2仿真平台 卜根据不同参数设置场景，进行了仿真; 与Directed Diffusion协议的性能做 了比较，结果表明改进后的路山协议其有较少的时延和开销· 关健侧 :无线传感器网络;路由协议;局域性;仿真 Routing Protocol and Simulation of Wireless Sensor Network WANG Yongling, GUO Aihuang (Electronics ,aid Information Engineering School, Tongji University, Shanghai 200092) [Abstract] The routing protocol is one of the key researching techniques for wireless sensor network, and the data-centric routing proh,eol is the hotspot of study at present. Based on locality u间acing mechanism, the data-centric Directed Diffusion protocol is improved. In different simulation .scenes of different parameters, the improved protocol depicted by C++.，simulated on the NS2 platform. Compared with the performance of Directed Diffusion protocol, the improved protocol has less delay and overhead [Key words] Wireless sensor network; Routing protocol; Locality; Simulation 无线传感 器 网络 是以数据 为中心 的网络 ，根 据这 一特 有 个称为 “梯 度” 的变量 与整个业务请求的扩散过程相联 性 ，提 出的路 山协议主 要有 Flooding 协 议、SPIN(Sensor Protocols for Information via Negotiation)协 议 hl和 DD(Directed Diffusion)协议iii等，其中 DD协议是以数据为中 心的路由协议发展过程中的里程碑曰口 无线传感器 网络 由许 多功能相 同或不同的传 感器 W点组 系，它用数据发送率来标识。终端节点和其它收到查询信息 的 节点通过请求更高的数据发送率来增加 “梯度“值 ，从而 选择特定数据发送频繁的路径来接收数据，而其它数据发送 率停留在较低水平的 节点组成的路径可以作为备选路径。 在路 由更新 匕 DD 协议采用积极加强和反加强的方式 成，W点可 以传送数据，也可以具有移动性。节点移动时， 来实现。积极加强的方式是通过本地的数据驭动规则选出经 路山要不断地 更新才能完成通 信任务;山 H 专感器节点的能 验性的低延时路径 ;反加强是利 用 “梯度”的有效期性 ，姗 最很有限，节点在能景较少的状态下影响网络的通信能力 ， 除过期 “梯度”。反加强采取主动和被动 两种方式 。当节点 也需要进行路由更新，这是无线传感器网络进行路山更新的 两个上要原因。并 几，无线传感器网络节点不同于 计算机网 络终瑞的固定性，也有别于移动 Ad Hoc网络节点的频繁移 动性 ，因此无线传感器网络路 山更新不能完全依据现有的方 式来实现。DD 协议中的路山更新符合无线传感器 网络的特 性，但在路由更新时因采川洪泛(Flooding)在整个网络中没有 范围限制地进行 ，将会存在较大 的时延和开铂 。本文运 用局 域性原理 ，改进 了DD 协议路 山更新机 制，使得路 由更新 在 一定的区域内进行，并在 NS2网络仿真jai中用C十+语言实 现改进路 由协议 的算法 ，然 后设计仿 真环境进行 了仿 真，最 后将仿真结果与 DD协议进行了比较分析 1 DD协议和局城性 1.1 DD协说 DD 协议通过数据命 名的方式来扩散数据， 节点用一组 属性值来命名它所生成的数据，终端节点发出的杳询业务也 用属性 的组合如 :对象的名称、间隔时间、持续时问、位置 等着经过的梯度过期就属干被动 方式加强 ，而当节点 明确地 发送反加强信息就 是主动 方式加强。不管积极加强还是反加 强 ，路 由更新都没有在一 定的区域内进行 ，路 由加强 的信 息 有大量 的过 剩，同时网络 巾的时延加大开销 增多。 1.2月城性 局域性就是事物根据所处的情况 ，在 一定范围或是有选 择地 处理任 务的性质 这 可以运用数学 I:集合的观点来解释。 个事物，是个独立事件，无论它有多大的影响力或者多大 的包含性，都要存在一定的范围之中 ，这样就可以给它划定 一个范围。设定 3个事物 A. B和 C(图 1).事物之间的关系 用朴式丧示为:(AnB)=C,C二A, C二B 。 - 一一 叫一 ‘~- 一 - 碑，一 - 一 圈1月 幼且 示 范围等来表示。查询倍息通过广播逐级扩散 ，每个收到查询 信息的节点能缓存信息 ，并且能通过最小生成树等算法聚巢 作者筒介:王永玲(19ri0一)，女，硕士生，主研方IN: Ad H-网络， 无线传感器网络技术及其实现;郭爱0 ,博十·副教授 数据，最终查询信息遍历 全网，找到所有匹配的原始数据 收稿 日翔 :2005-II-07 E-mail: ylingwCyahoo.com.cn — 】23- 

事物 C是事物 A和 B相 交的部分。尽杆 事物 A 的局域 范围包含事物 C的局域范围，事物 B的局域范闹包含事物 C 的局域范围 ，可是事物 C的局域范围不同于事物 A的范围 ， 也不同 于事物 B的范围 ，远小 卜事物 A和事物 B的局域范 围 同样 ，在路 由协议设计时 ，路 由更新 时可 以选择在松个 网络 ROR数据包作 用下节点产 生的 RRQ数据包 ，这些 节点就从 它的记录 里面产生 个新的 RRQ 数据包并发送 出去 ，以便 RRQ 数据包能够传 到更远 的日的节点 。当这个 RDR数据包 在 旧的区域 内遇到 旧路 由中的 竹点 ，它的 下TL值减 1，来缩 小路 由发现 区域。 巾进行 ，也可 以选择在 1定 的范围内进行 。 定的局域下进 2.1.3路由更新实例 行路 由更新 ，就是依据 局域性 更新机制 设计璐 山协议 2签于局城性更新机创的DD协议墓本思想和算法 2.1基本思姐 无线传撼器 网络 中，节点的能 录低于 ‘个设定的门限值 ， 汇节点可能移 动到另 一个位置，这样就把原来的路由定义为 “问题路 由”。依据局域性原理 ，把能量低的(或者移动)的 竹 点定义 为 “问题节点”，距离 “问题节点”n跳路径的节点的 范围属干 “间题 区域”，其中 n的数值依靠问题节点的邻节点 来选取。 一旦节点成为 “间题节点”， 首先沿着旧的路由广 播路由发现区域(R()uteDiscoveryRcgi〔、n，RDR)数据包来定 义 “问题区域”，然后在 “问题区域”内建立新的路 由。 2卜1定义问题 区域 在路由更新的过程中，问题 节点 先发送 RDR数据包 ，这 个数据包带一个初始 Tr L(TimeI()Live)值 ，其 中 TTL的初值 是指定的，然 后 TTL的值依据该节点找到邻居节点所要的跳 数确定。当问题路山中的节点收到 RDR数据包时，它重新设 置 RDR的 TTL值，并发送 RDR数据包。若接收到 RDR数 据包的节点不是原来问题路 山中的节点 ，该节点 重新 设置 的 TTL值大于 TTL初值。节点发送 RDR数据包后，TTL要 自 动减 {。所有接收到 RDR数据包的节点 ，都拥有 ·个 TTL 值 ，就把所有带有 竹 L值的节点所在的区域作为“问题区域” 如果 问题路 由 L的 节点发送 RDR 数据 包后，发现 RDR 数据包或者是后来路由杳询(Route Requcst，RRQ)数据包不 能在 设定 的跳数 内找到邻居 节点 ，这时节点将增加 RDR数据 包 中的 Tr L值 重新确 定 “问题 区域” 2.12建立新的路由 “问题 节点”传送 ROR数据包后，就会发送一个 RRQ 旧的路 由由源节点 srC、中间节点 A、中间节点 B和 Sink 节点组 成，如图 2所示。 省点 sink 移动后 ，便找不到下一跳 邻居节点 A。Sink沾点就作为 “间题 节点"广播一个 TTL值 为 2的 ROR数据包，邻居 节点接 收到 RDR数据包，知道 TTL 值大于 1，所有的邻居节点就重新广播 RDR数据包。A 竹点 收到 A 节点发送的 RDR数据包，A节点重新广播 TTL值为 1的 RDR数据包，沿着 A节点 的邻居 节点 ，只有 B节点可 以转发 RDR数据包 ，于是便找到源节点 Src，建立 了新的路 由:sink一AI一A一B一src。图2标出了节点发送RDR数据 包中的 TTL值 ，也就是表示出路 由发现 夙域 厂 ) 璐 澎 .曝 sillk (()Id po斌 i(ln) 娜’_，路由 夕 碱。_ 旧璐由 .卜 R RC 圈2 路 由更 断过 租 2.2算法 实现 结合使用的仿真平台，在原有 DD 协议算法的基础上 ， 依据基于局域性更新机制 DD路山协议的基本思想，用 C+十 语言重新描述路 由协 议的算法 。算法主要部分摘录如下 2之.1节点门限值的设定 数据 包，查 询通往 口的节点 的路径 。为 了避免隐藏终端出现 ， ClassEnergyTi了ncr:puhlicTimerHandcr l/从NSZ中时间 RRQ 数据包应在 RDR数据包发送后立即发送 ，并且 ，只有 1/类 中派 生新 类 问题区域范围内的节点和能量低干门限值的节点 可以重新发 送 RRQ数据包 ，至于接收到 RRQ数据包却不能在发送 RRQ 的节点，要保留 RRQ的一个暂时记录 ，以便 问题 区域 的扩展 。 若有许多传感器节点密集分布在问题路 由附近 ，并且这 些节点有足够的能量来完成转发任务，RRQ数据包就能够经 过多跳路 山到达 目的节点。这时 。目的节点就选择最好 的 转 点 ，反 向发送路 由应答(RouteRePly，RPP)数据包 ，完成路 由 更新 的过程 。 如果 区域中的传感器 节点比较稀少 ，影响 RDR数据包 或 者RRQ数据包向目的节点的传送，这时位于定义为 “问题区 域”边界 上的节点发送数据包，来扩展间题区域。在改进 DD 协议中，节点接收到一个 RRQ数据包 ，该 节点就认为它所在 范围内的节点有能 力传送 RDR数据包和 RRQ数据包，并且 该节点 铅着反向 RDR 路径 发送一 个路 由查询确 认(Roule RequestC0ntlrlllation，RRC)数据包，同时，该节点还设置一 个时间段去等待下面路 由送 来的 RRC。 一段时间后若节点仍 没有收到 RRC数据包，该节点就 认为这个区域影响问题路由 的发现 ， 一个新的 RDR数据 包就被 发送 出去，重新定义问题 路 由区域 ，原来 问题区域以外 的节点 旦接 收到在 被新的 一 124一 { Publlc: Init多ng_二node_一>ene吧y_model(j一>cnergy(); thresh01d一二in.t_eng_卒07 1 刀设定门限值 至于移 动点在 节点查 找时会 白动 发现。 222 路由更新 算法描述 刀定义查询局城名称 char *MsgSLr[1 二 {’.’.， ’INTEREST‘，， ”DA不、1’ ”DATA_READY”， ‘’DAI城_REQUEST”， ”POS_REINFORCE” ”IN_REG10N”，”INHIB互T”，”TX_FA ILED”，”DAI减_STOP‘’1 voidDlffu si‘，nProb::SendNc伙Rcint() Packe吸率Pkt=Bcast_In_region(0，bcast_addr，IN_REGION) 1/定义广播数据包函数 MACprePar。(pkL，MAC_BROADCAST，NS_AF--ILINK，(1) MACsend(pkL，0); re[urn; 1 1/RDR函数描 述 

Packet 'DiffusionProb::Bcast_ In- egion(unsigned int dtype ns_ addr t to_ addr, ins msg type) Packet* pkt=crease-packet() hdr_ cdiff' dth = HDR_ CDIFF(pkt) hdr_ ip-iph=HDR_ IP(pkt) int TTL=2 刀定义TTL变量 return pkl; } //路由更新函戮 void DiffusionProb::consider_ new(Packet "pkl) switch (msg_ type){ case INTEREST : case POS REINFORCE 的 j 洲 盆 绷 略 exam 图3 不 同橄 节点 数 目下 的 平均 时延 图 4(a)为不 同网络 密度下的开销。随着网络 中放置节点 数 目的增加，两种协议下的开销都在增加 ，但改进 OD协议 下的曲线比较平缓 ，DD 协议情况绘制的 曲线 比较陡峭 。这 case IN REGION : //调用问 皿 区城函橄 就说明改进 DD协议受 网络密度的影响较少了。图 4(b)为不 } 3基于局域性更新机制的 DD协议仿真 在 NS2平白下仿真基于局域性 更新机 制的 DD协议 ，首 先将写好的协议算法描述扩展成为 NS2的仿真组件，然后设 置仿真场景编写 TCL脚本进行仿 真。 3.1仿 真参数 和场景设 里 针对无线传感器网络的特点 ，仿真 时考 虑反映网络协议 有效性和可行性的平均时延 ，即测 试数据 包从源节点传送到 目的节点需要的平均时间 ;同时还考虑 反映路由更新消耗能 盆的开销，即路由建立时发送 的查 询数据包的个数 。 对于平均时延 ，考虑源节点数 目不同下的路由更新平均 时延。将 100节点分散在 230m X 200m的长方形区域内，每 个源节点的最大移动速率为 2m/s，分 别在 设定 1, 2, 4, 6, 8个源节点数目下的场景中进行仿真 。 对于开销 ，考虑不同 网络密 度下的开销和不同源节点移 动速度下的开销。网络密度下的仿真 ，分 别放置 100, 400, !11f和 1 600个节点在 250m X 250m的区域内，源节点的移动 速率为 2m/s，设定 1个源节点和 I个 Sink节点。源节点不 同 移动速率下的仿真 ，放置 841个节点在 250m X 250m 区域 内， 设定I个源节点和I个Sink节点，源节点分别以0 m/s, 1 m/s, 2 m/s, 3 m/s, 4 m/s, 5 m/s的速率移动。为7评价基于局域 性更新机制的 DD协议的性能 ，在相 同的仿 真场 景中也对 DD 协议进行 了仿 真。 3.2仿真结果及分析 通 过仿真 ，分析仿真数据 结果中的 trace文件，选取 一些 数据来做统计，并以图示的形式表现 出来 。 图3显示源节点数目不同情况下网络的平均时延。可以 看出两种协议在单个硕节点数 目下的 平均 时延 没有差别，随 着源节点数目增加，协 议在平均 时延 上的差别就越来越明显， 并且看出改进后 DD协议 的性能受源 节点数 目的影响不大， 整体来看改进 DD 协议有着较少的平均时延。这是因为改进 DD协议在路由更新时采用局域性更新机制，减少了数据包 传送时受到的干扰。低的平均时延显示出改进 DD协议的有 同节点移动速率下的开销 。节点移 动速 率增加时，网络变化 也更加频繁 .统计结果显示节点在 高速 率移 动时有较 多的开 销。可改进的 DD协议表明有着较少的影响 。 护 、 s 0 之加 月创 6口 翻田 1口以 1会以 1和引.‘比 节直 .目 t.t不 网门招口度 下的开 晌 节成移动目率tM,t 山，不目公动口率卜的开悯 图4 网络开悄性能比较 4 结论 局域性 更新机 制有 利于路由协议设计方式的拓展，它适 合无线传感器 网络 的特性，在无线传感器 网络的实现上具有 重要作用 。本文运 用局城性 更新机制改进 了以数据为中心的 DD 协议，通 过了 NS2仿真平台上仿真模拟 ，并与 DD协议 下 的仿真结果进 行了比较。结果表明在时延和开悄方面 ，运 用局域性 更新机制 的 DD协议 具有 较大的优 势。局域性在无 线传感器 网络 . Ad hoc无线 网络等无 中心 自组织 网络中应用， 具有较好的前景，也有很多问题和技 术需耍进一 步解决 。 参 考文 献 I Heinzelman W R, Kulik 1, Balakrishnan H, et al. Adaptive Protocols for Information Dissemination in Wireless Sensor Networks[C] Proceedings of the ACM MobiCom '99. Seattle, Washington, USA: ACM Press, 1999: 174-185 2 Intanagonwiwat C, Govindan R, Estrin D. Directed Diffusion for Wireless Sensor Networking[J]. IEEEIACM Transactions on Networking,2003,It(]):2-16 3于海斌，曾 日，王忠锋等 分布式无线传感器网络通信协议研 究〔J]通信学报，2004,25(10):102-110 4徐雷鸣，庞 博，赵 胭 NS与网络模拟[M]北京二人民邮电出 效性和可行性 。 版社，2003 - 125-