传感器网络定向扩散机制中梯度生成算法的研究.

1、收稿日期：2006-07-03基金项目：卫星综合信息网网络管理技术(2003AA712032资助.作者简介：廖先林,男，1963年生,博士研究生,高级工程师，研究方向为计算机网络；赵林亮，男，1956年生，博士，教授，研究方向为 计 算机网络、智能系统；王光兴，男，1937年生，教授，博士生传感器网络定向扩散 机制中梯度生成算法的研究廖先林，张志伟，门云会，赵林亮，王光兴(东北大学 信息科学与工程学院,辽宁沈阳110004 E-mail:zh aolinliangise.n eu. edu. cn摘要:如何生成优化的梯度是传感器网络定向扩散中的一个关键问题，本文在分析一种基本梯度生成算法的问题

2、基础之上，利用兴趣包的转发次数对其进行 改进，设计了一种分布式的最短路 径梯度生成算法.该算法极大的 降低了邻居节 点间建立平行梯度”和 逆向梯度”的概率，可构建从源节点到sink节点的多条 最短路径.仿真表明，改进的算 法可建立更为有效 的梯度，从而使得定向扩散中 数据报文沿着更短的 路径传输，无线传感器网络的能量利用率更高.关键词：传感器网络；定向扩散；梯度生成；最短路径中图分类号:T P 393文献标识码:A文章编号:1000-1220(2007 10-1735-05Research on Gradie nts Set up Algorithm for Directed Diffusio

3、 n in WSNL IA O X ian -lin , Z HA N G Z hi -w ei , M EN Yun -hui , ZHA O L in -lia ng , WA NG Gua ng -x ing(S chool of I nf or mati on Scie nee &E ng inee ring , N ortheaster n Un iv ersity , S heny ang 110004, Ch inaAbstract :How to set up go od gr adie nts is cr ucial for directed diffusi on i

4、n w ir eless senso r net wo rks. Based on t he resear ch of one ba sic g radie nts set up alg or distr ibut ed shor test -p ath gr adie nts set up algo rithm for directed diffusi on. T he impro ved alg or ithm g r ea tly decr eases t he pr obability tobuild " pa rallel g radie nts " and &q

5、uot; rev erse g r adie nts ", and con str uct mult iple shor test p aths fr om sour ce node to sink no de . T he simula tio n result s sho w , this shor test -p ath gr adie nts set up algo rithm can set up mo re efficie nt gr adie nt s, t hen data p acket s w ill be deliv ered alo ng shor ter p

6、at hs , and dir ect ed diffusi on fo r w ir eless senso r netw or ks is mor e energ y efficie nt . Key words :se nso r netw or ks; directed diffusi on; g ra die nts set up; shor test -p ath以数据为中心的定 向扩散协议（Directed Diffusio n是无线传感器网络中 平 面路由协 议中的一项 重要内容，它既完成了路由的功能，又提供了对应用层的支 持，较之其它一些路由协议3, 4, 8,它具有良好的体

7、系结构.有关仿真证明定向扩散在传输时延、能量消耗等方面都有不错的性能1.定向扩散主要包括兴趣发布、梯度建立、数据传输、路径加强和修复等 内容.兴趣描述了需要采集的数据的特征，一个梯度至少描述了邻居节点之 间数 据传输 的方向.因为多个 梯度可以构建 从源节点（source到网关节点（sink的数 据传输路径，所以梯度表示了网络的路径1.对于一种特定类型 的兴趣，一个节 点之上可以存在多个梯度与其对应，这就保证了从 这个节点到sink节点有多条 路径来传输与这个兴趣对应的数据，这样当一个邻居节点损坏的时候，仍然会有 其它的邻居节点来传输数据，所以一个节点上的多个梯度保证了网络的健壮性.同时梯度在

8、网络 的能量利 用率方面也 起到了重要 的作用，因为好的梯度可以构建较短的路径，这样在数据报文从 源节点传输到网关节点时就会消耗较少的能量.可见，梯度与网络的健壮性和能量利用率都有着密切 的关系.在定向扩散中，梯度是在兴趣发布的过程中建立起来的.其大体过程是，网关 节点首 先向自己的邻居节点广播兴趣.当一个中间 节点从邻居 节点收到 兴趣之 后，它会建立指向兴趣 转发者的梯度，然后这个节点再对兴趣执行广播.这样重复 进行，兴趣报文被 广播到整个 网络.当广播周期 结束之后，整个网络中也就建立 了相应的梯度.在本论文中，将会研究 梯度生成的具体细节.首先介绍一种基本的梯度生成算 法，分析它的关键

9、之处和效果之后，将对其构造的路径过长问 题来改进 这种基本 算法，设计一种最短 路径梯度生成 算法来建立 更为有效的梯度.最后，利用ns22分别对两种算法进行仿真,并就网络的性能进行比较.2基本梯度生成算法2. 1算法描述这个基本的梯度生成算法在ns2. 29的定向扩散协议中已经实现,仿真结果表明，这个算法能在较短的时间内以较少的能量建立比较有效的梯度.算法的有 限状态机描 述如图1（见下页所示.注意图中只标注了算 法中节点主要状态间的 转换.首先，sink节点会生成一个兴 趣报文，这个兴趣描述了所小型微型计算 机系统 Jour nal o f Chinese Computer Systems

10、 200年 10 月 第 10 期 V ol. 28N o. 102007要查询的数据的属性，然后把兴趣注入”到网络当中去.对于sink节点而言，在兴趣广播 出去之后，它将会等待接收数据.如果sink节点收到邻居的兴 趣， 而自己正好是这个兴趣的 源节点，sink节点将会丢弃这个兴趣报文霞兴趣，韻兴®丢笄图1基本梯度生成算法的有限状态机描述Fig. 1 Basic g r adie nts set up algor ithm descri pti onwith fin ite sta te machi ne中间节点对于兴趣报文的处理是这个算法的关键之处.当中间节点第一次 收到这个 兴

11、趣报文的 时候，它把这个兴 趣报文放置到兴趣缓冲区当中，建立指向 兴趣转发者的梯度，进行一个服从某个 均匀分布的 很小的随机 延时，延时结束后 再把兴趣报文广播到自己的邻居.在这段随机延时的过程中，如果节点又一次从 其它的邻居收到了这个兴趣，那么节点还会建立梯指向转发者的梯度.而当延时 完毕兴趣已经转发之后，又一次收到这个兴趣报文的时候，这个兴趣报文会被丢弃, 节点不会进行梯度的建立.这样可以保证对于同一种兴趣，邻居节点之间不会有直接的环路 存在，因为邻居节 点只有一个 梯度，而且这个梯度的方向 是从兴趣 转发时间晚的节点指向 兴趣转发时间早的节点.这样兴趣报文就 会在整个网络当中进 行广播，

12、到达广播域中的每一个节 点.需要强调一点，在一次兴趣 传播过程当中，对于同一个兴趣报文，每个传感 器节点只是转 发一次.源节点在产生数 据之后，如果发现 兴趣缓冲 区中有相 应 的兴趣，它会沿着与这个 兴趣相对 应的梯度所建立的路径 来传输数据.如果有多 个梯度与这个兴趣相对应，节点可以随机 选择一个梯度进行数据传输，也可以向 所有的梯度都发送 数据.关于数据如何沿梯度进行传输不属于本论文研究的范围2. 2算法分析节点上兴趣转发的随机延时和中间节点对一个兴趣包只转发一次决定了该基 本梯度生成算法不会产生环路，代价小，不容易在链路层产生冲突.由于邻居节 点之间总是会建立 后转发兴趣 节点指向先转

13、发兴 趣节点的梯度，而且离sink节 点越远，转发时间越晚的概率就越大，所以从整体的 梯度拓扑来 看，这个算法会满 足基本的梯度生成要求,整个网 络会利用梯 度建立从sour ce指向sink的多条路2. 2. 1环路问题分析前面已经解释过在一对邻居节点之间只能存在一个梯度.对于两个邻居， 节点C和节点D,如果存在从C指向D的C D ,>那么,两个节点对兴趣的转 发时间(节点C要晚：T (C >T (D .假设在节点A和节点B之间存在环路,那么就有:A X 对于兴趣的转发时间，也就有:T (A >T (X >>T (B >T (Y > >所:以:

14、T (A >T (A显然，这是矛盾 的.所以我们的假 设是错误 的，所以使用这种基本的梯度生 成算法，在一次兴趣传播的过程当中，任意的两个传感器节点之间不会形成环路2. 2. 2能量消耗分析对无线传感器网络而言，特别是对于大规模的网络，将兴趣报文广播到整个网 络当中去是一个很大的能量消耗.但在不知道网络中哪个节点会采集到与兴趣 对应的数据的情况 下,这又是唯一的一种选择.有关研究是利用地理位置对兴趣 的广播进行控制，但现在还没有廉价而又准确的方法来获取无线传感器网络节点 的地理位置.在这个算法当中，每个节点对于同一个兴趣报文只是转发一次，所 以兴趣报文被转发的次数等于网络中广播域的节点个

15、数.这种情况下，能量消耗相 对较小.2. 2. 3媒体接入层的冲突避免传感器网络使用的是无线通信方式，无线通信过程中进行冲突检测是一件 困难的事情，所以在进行无线ma c设计的时候经常采用的策略是冲突避免和一 些调度机制5.传感器网络上三 层在进行分 布式协议 设计的时候，应该考虑避 免数据报文在mac层发生冲突，也就是邻居节点尽量避免在同一时刻发送数据.这个算法利 用兴趣报文 的随机延 时转发来避 免广播 过程中兴趣报 文在mac层 发生冲突.如图2所示，当节点0把兴趣报文广播之后，节点1和节点2几乎会 同时收到这个兴趣报文，如果节点1和节点不进行随机的延时，而是直接将兴 趣 转发出去，那么

16、兴趣报文将 会有很大 的可能性在 两者的共 同邻居节 点3上面发 生冲突，导致节点3接收不到兴趣报文.图2 节点无延时兴趣转发冲突 示意图Fig. 2 lllustr atio n o f collision o n no de w ithno time delay to pro pag ate int er est在这个算法当中，随机 延时服从一个从0到0. 05秒的均匀分布.假设兴 趣报 文的大小是50字节,无线信道数据传输速率是1M /S .经过计算,如果使用了随机延时,图2中在节点3上面发生兴趣报文冲突 的概率是1.6%.如果ma c层使，1736小型微型计算机系统2007 年个更小的

17、CT S报文,这样发生冲突的概率更是会小于1.6%所以如果我们使用了随 机延时，在真实网络中发生 广播冲突的概率很小.2. 2. 4梯度拓扑结果由于随机延时的 存在，生成的梯度 拓扑的结 果也就带 有随机性.利用上述 算法形成的梯度拓扑的主要特征是邻居节点之间必然存在单向的梯度,而 且整体的梯度走向是从source节点指向sink节点，这已经符合定向扩 散梯度 建立的要求.基本的梯度生成算法存在的问题之 一是这个算法没有解 决过长路径的问题.在接下来的部分中，我们会对 这个基本算 法进行改进，来生成一个更为优化的梯度 拓扑.3最短路径梯度生成算法为了使得数据报 文在传输过程中消耗 的能量最 少

18、，我们改进基本的梯度 生 成算法，设计了这种最短路 径梯度生成 算法，来生成可构建最短路径的梯度.3. 1问题分析：平行梯度和逆向梯度为了保证传输数据报文消耗的能量最少，那就要保证从源节点到sink节点 的路径最 短，那么就应该保证节点上的 每个梯度都是最优的，每个梯度构建的路 径都是通往sink节点的最短路径.也可以说，经过一个梯度,数据报文就越 接近sink ,反之，梯度的存在就会过多消耗网络的能量在利用基本的梯度生成 算法得到的梯度拓 扑图3(a中，因为节点1可以直接把数据报文转发给sink节点，而无须再用节点3进行转发,所以从节点1指向 节点3的梯度是多余的.因为这两个节点距离sink

19、节点的跳数值是一样的，所以这两个节点间的梯度会浪费 网络的能量，称具有相同跳数 值的节点间的梯度为平行梯度.这种平行梯度是应该去掉的(a 平行梯度和逆向梯度，兴趣转发时间：节点3节点1节点4节点2(b 最优梯度拓扑图3 一般梯度拓扑与最优梯度拓扑 F ig . 3 Ge ner al g radie nts to po lo g y w ithbest g radie nts to po Io gy更为严重的情况是梯度从具有跳数值小的节点指向了跳 数值大的节点，例如图3(a中的从节点2指向节点4的梯度就是这种情况，如果节点2使用这个梯度 来发送数据报文，那么至少要经过多余的两跳才 能把数据报文

20、发送 到sink节点.在图3(a拓扑中,如果使用基 本的梯度建立算 法,节点2将会有16. 67%的概率拥有指向节点4的梯度.我们称这种完SihkSink樹始化节点醴数囲1NYFT>NH逹弃兴报文IN收Yt£斷节点全背离Sink节点方向、从跳数值小的节 点指向跳数值大的 节.在新的算法当 中，我们认为可以构建从源节 点到sink节点的最短路径的梯 度是最优的梯度，并以此为标准来生成梯度.在一次兴趣广播的过程 中，如果一 个中间节点对兴趣报文 进行了转发，那么这个节点 就是正常的节点，包括能量和链 路状况，我们可以使用这个节 点来发送数据.尽管在兴趣失效之 前节点可 能坏掉, 然

21、而通过兴趣的周期性广播可以使得这个损坏节点在下一次兴趣传播过程中被忽 视.所以，我们认为可 以构建 从源节点到sink节点的最短路 径的梯 度可以使得 网络使用最少的能量来进行数据传送，并且认为这种梯度是最好的梯度.图3(b 是最佳梯度的一个拓扑示意.接下来，我们将会改进基本算法来降低在梯度生成过程中建立平行梯度和 逆向梯度的 概率，从而得到一个更为接近 于最优化结果的梯度拓扑，使得网络的 能量利用率更高.我们称这个改进的算法为 最短路径梯度生成算 法，因为这个算 法可以确立从源节点到sink节点的多条最短路径.3. 2使用兴趣报文的转发次数改进基本算法平行梯度和逆向梯度存在的根本原因是基本算

22、法只是利用兴趣报文转发时间 的早晚来确定梯度方向，而这个算法却不能完全保证离sink节点远的节点总是 会先于离sink节点近的节点晚一些转发兴趣报文,如图3(a.解决的方法是使用兴趣报文的转发次数来修改基本算法.对每一种兴趣，节点设置一个称为节点跳数的变量与其对应，并利用节点收到的兴趣 报文的转 发次数对其进行更新.Sink节点的节点跳数是0.当一个中间节点第一次收到某种类型的兴趣报文的时候，它会将兴趣报 文放置到 兴趣缓冲区当中，建立指向兴趣转 发者的梯度，并利用兴趣报 文的转发 次数来初始化本节点与FT:兴趣报文转发次数NH :节点跳数值RS :兴趣报文是否转发图4新算法兴趣报文处理流程F

23、 ig . 4 Op ti ons on the new r eceived in ter est pa cke 这种兴趣对应的节点跳数 , 然后准备进行延时转发.如果节点，173710期廖先林等:传感器网络定向扩散机制中梯度生成算法的研究己的节点跳数值与兴趣报文里面的转发次数进行比较.如果转发次数小于 节点跳数，那么这个节点将会删 除以前建立 的关于这种兴趣的所有梯度，建立新 的指向这个转发者的梯度，使用这个更小的兴趣报文的转发次数更新它的节点跳 数.如果此时节点还没有把兴趣报文转发出去，那么还要用这个兴趣报文的转发次数加一来更新待转发的兴趣报文的转发次数值.如果转发次 数跟节点跳数值相等，

24、那么节点只是添加一个新的梯度.如果转发次数大，那么这个兴趣报文将会被丢弃.注意的是不论节点将兴趣报文转发与否，节点都会进 行上面的比较和操作.图4(见上页说明了新算法对于兴趣报文的处理流程.3. 3 算法分析改进的算法利用了兴 趣报文的转发次数来去掉平行梯度、修改逆向梯 度.举例来 说,在图3（a中，尽管节点4比节点2要早一些转 发兴趣报文，但是 节点2不会建立指向节 点4的梯度，因为节点2会发现它的节 点跳数（本图中是1 要小于节点4发送来的兴趣报 文的转发次数（本图中是3.相反，节点4会建立指 向节点2的梯度，尽管节点4在收到节点2转发来的兴趣报文的时候节点 4已经 进行过了兴 趣报文的转

25、 发，因为兴趣报文里面的转发次数等于节点的跳数值 ，本图 中都是2.这样的比较和操作 会极大的去除平行 梯度，修改逆向梯度，使得局部的 梯度更为合理，最终会得到一个接近于最佳梯度的梯度拓扑.注意的是我们还 是不能完 全得到最优 化的梯度，因为中间节点只能转发一 次兴趣报文，所以关于自己的跳数值，它可能对自己的邻居 说谎”我们的算法 还是一种尽最 大努力的情况（best -effor tease，我们所能保证的就是每个节点只是 保留指向 看起来”具有最小跳数值节点的梯度.在下面的仿真部分中，我们将 会看到新算法对于梯度的建立 结果有了很 大的改进.4仿真我们用ns-2进行新协议设计6, 7,实现

26、了最短路径梯度生成算法,并进 行了仿真.我们的仿 真工作主要包括两个方面，一个是关于梯度生成结果的分 析，一个是关于整个网络节能效果的分析.4. 1梯度生成结果分析首先，我们设计了一个集中式的算法（一个用java来实现的宽度优先搜索算法来计算理想的最佳梯度拓扑，这个最佳的梯度拓扑包括从源节点 到sink节点 的所有最短路径.然后分别使用基本的梯度生成算法和最短 路径梯度生成算法进 行仿真，在仿真过程中提取各个中间节点上面 的梯度.最后，用仿真结果与最佳 结果进行比较.为了便于比较，特进行如下的定义.如果一个 梯度出现在 仿真结果集中，同时 也出现在理想最佳梯度集中，我们称之为一个命中（HI T

27、 ,如果一个 梯度出现在仿真结果集中而没有在最佳结果集 中,我们称之为一个错误（ERRO R ,另外一 种6ainkJy情况是一个梯度在最佳梯度集中而没有出现在仿真结果集中，（路径，而错误会使得网络使 用过多的能量来传输数据报文.所以命中数量越多越好，而错 误和丢失越少越好.1738小型微型计算机系统(a梯度命中个数比较我们用不同规模大小的传感器网络来进行仿真,从50个节点到250个节点.50个节点 的场地 是随机的把50个节点 放置在长和宽都 是800米的场地中.每 个传感器节点的通信图5 一个改进算法的梯度拓扑结果Fig. 5 O ne g r adie nt s t opo log y

28、r esults w ithimpro ved alg or ithm半径是250米俄们采用了 802. 11协议的默认通信半径,对于W SN可能大了 一点，但这不影响仿 真比较.其它大小的场地，包括100个节点、150个节 点、200个节点、250个节点,分别通过 调整场地的 大小来保 持节点的密 度不 变.在每种大小的场地上仿真都进行两次，分别采用不同的梯度生成算法，基本的 梯度生成算法和最短路径梯度生成算法.图5是一个使用了最短路径梯度生成算法的梯度拓扑结果(使用jav a绘制，图6是两种算法梯度生成结果的一个比较(a(b梯度错误个数比较Co mp ariso n of g radie

29、nts HIT nu mbers(b比较Co mpa riso n o f g radie nts ERRO R numbers图 6 两种算法梯度生成结果F ig. 6 Co mpar iso n o f gr adie nts set up r esultsw ith tw o alg or ithms从图6的比较中可以 看出，最短路径生 成算法有 更多的 命中和很明显更少 的错误，这就说明使 用了最短 路径梯度生2007 年能量节省来说是很重要的，在4. 2中我们将会看到最短路径梯度生成算法的这个优势会 使得网络更 节能.需要解释的一点是，与基本算法相比较，最短路 径梯度生成算法会有更多

30、的丢失，但是丢失一般是发生在有多个梯度存在的节点 上的，所以某几个最佳梯度的丢失对网络性能的 影响不大.4. 2网络能量利用率的提高在这一部分，我们将会比较基本算法和最短梯度生成算法在网络能耗方面 的表现.在ns2. 29实现的定向扩散协议中，在路径加强之前，数据是按照随 机选择的梯度进行传输的.如果一个节点上的梯度都是最佳的，那么数据报文将 会总是沿着 最短的路径进行传输，这样整个网络就 会使用更少 的能量.我们使 用两个标准来评价网络的能量利用情况 总、的数 据报文转发次数和总的网络能量消sink节点在0. 14秒进行兴趣的广播，当源节点接收 到兴趣的时候 它会以恒 定的速率进行数据回传.

31、为了保证sink节点和源节点之间是多跳传输，我们将sink节点和源节点放 置在网络的两端.因为源节点是以恒定的速率产生数据的，那 么在恒定的仿真时间内，sink节点所收到的数据报文的个数几乎是一样的.所 以整个网 络进行总 的数据报文 的转发次数 越少，整个网络 就会利用较 少的能量 来传递相同的有效的数 据报文，网络的能量利用率就越高.比较结果如图7所示(a(b数据报文的总转发次数比 较(aCompar ison of data p ackets re-se nt times总能量消耗比较(bCo mpar iso n o f tot al ener gy co st7两种算法能量消耗比较F

32、 ig. 7 Compar ison of ener gy co st w ith tw o alg or ithms 因为改进的算法有更高的概率使得 数据报文沿着最短的 路径进行传输，所以它很大的降低了总的数据 报文的转发次数,如图7(a所示,这样就使得网络消耗了更少的能量,如图7(b 所示.从图7(b可以看出,250个节点的网络的节能效果没有200个节点的网络的 节能效果好.这是因为 网络的规 模越大，网络的兴趣广播能量消耗越大.特别是 当数据传输速率很低而兴趣广播的频率较高的情况下，兴趣广播的能耗将会.网络定向扩散协议的一个关键点，这个问题应该进行进一步的研究.5结论为了使得 无线传感

33、器网络的定 向扩散更 简单有效，我们设计了这种最短路 径梯度生成算法.这个算法是在基本的梯 度生成算法的基础之上,利用兴趣报 文的转发次 数来去掉平 行梯度、修改逆向梯度，最终得到了一个更接近于最优结 果的梯度拓扑，这个结果几乎包括从源节点到sink节点的所有最短路径.仿真结 果表明，梯度建立结果已经相当接近于最优化 的结果，数据报文的传输会 沿着更短 的路径进行，整个网络的 能量利用率更高.我们下一步的工作是研究如何利用已生成的最短路径梯度来进一步简化和改 进定向扩散的其它步骤.例如，我们可以考虑去掉 路径加强的 步骤，因为使用最 短路径梯度生成算法之后，所有的路径都是最佳的，这样会使得协议

34、更为简单.不过需要注意的是，最短路径梯度生成算法牺牲了 一定的网络的健壮性来获得 更高的能量利 用率，所以关于网 络的健壮性 研究也是我们下一步工作的一个重 点.Refere nces :1 C halerm ek Intanagon wiw at, Rames h Govindan , Deborah Es-trin, et al.Directed diffusi on for w ireless s ens or n etw orking C . lEEE/ACM T rans actions onNetw orkin g, Novemb er, 2003:2-16.2 NS-2Netw ork Simu lator EB/OL . htt p:/w ww. isi. edu. cn/nsnam/ns.3 De ng J, Han R, M ish ra S. A robus t an d light-w eight rout ingmecha n ism for w irele