DDRLD_支持局部扩散的定向扩散算法

1、第25卷第5期2008年5月 计算机应用研究ApplicationResearchofComputersVo.l25No.5May2008DDRLD:支持局部扩散的定向扩散算法李志宇,史浩山(西北工业大学,西安710072)*摘 要:在定向扩散协议中,中间节点以泛洪的机制向网络中的所有邻居节点转发接收到的兴趣报文,导致网络能源的浪费。为此,提出一种支持局部扩散的定向扩散算法DDRLD。它通过设置梯度扩散深度阈值,缩小了兴趣报文扩散的范围,降低了网络中传输的数据量;通过设置节点剩余能量门限值,增加了每个节点被选取为转发节点的概率,延长了节点的平均工作时间,改善了网络负载平衡。仿真结果表明DDRL

2、D大大缩短了数据报文端到端的平均延迟,降低了网络功耗,增加了网络生存时间。关键词:无线传感器网络;数据融合;定向扩散;扩散深度;剩余能量中图分类号:TP301 文献标志码:A 文章编号:1001 3695(2008)05 1330 03DDRLD:directeddiffusionroutingsupportinglocaldetectionforWSNLIZhi yu,SHIHao shan(NorthwesternPolytechnicalUniversity,Xi an710072,China)Abstract:Inthedirecteddiffusionroutingprotoco,l

3、theintermediatenodesretransmittheirreceivedinterestmessagetoalloftheneighbornodesbyflooding,whichcanbringaboutgreatpowerconsumptiontothenetwork.Thispaperproposedawirelesssensornetworkdataaggregationalgorithmcalleddirecteddiffusionroutingsupportinglocaldetection(DDRLD).Firstlyintro ducedthebackground

4、oftheresearch,thenprovidedtheanalysisofDD,andpointedoutthedisadvantagesofDDandtoavoidthedisadvantages,proposedDDRLD,inwhichbysettingthemaxmiumgradientdiffusiondepthandtheminmiumnoderemai ningenergy,thetmiesforeachnodetoretransmitinterestmessageatthepropagationstagewereoptmiized.Itfocusedonthesmiulat

5、ionandtheresultsanalysis.ThesmiulationresultsindicatethatDDRLDgreatlycutsdowntheaverageend to enddelayofdatamessage,reducesnetworkpowerconsumptionandprolongsthenetworklifetmie.Keywords:wirelesssensornetwork(WSN);dataaggregation;directeddiffusion(DD);diffusiondepth;remainingenergy 在无线传感器网络中,每个传感器节点的监

6、测范围及能量都是有限的。为了增强整个网络所能获得的信息鲁棒性和准确性,放置节点时必须使节点的监测范围互相交叠。这样,节点所采集到的数据就存在一定的冗余信息,网络负载会随之增加。在网络层中将路由协议和数据融合机制结合起来,可以减少传送的数据量,从而节约网络功耗,延长网络的生存时间。数据融合技术是WSN研究中的重要部分1。定向扩散(directeddiffusion,DD)是针对无线传感器网络而设计的,提供了一种以数据为中心的路由协议体系结构。DD采用泛洪的机制建立路径,不具有网内数据融合功能,导致了网络能源的浪费。本文以传统DD协议为基础,设计了一种支持局部扩散、以数据为中心的路由协议 DDRL

7、D,对兴趣报文的扩散范围和节点被选取为转发节点的概率进行了优化。1)初始梯度建立阶段在DD中,梯度(gradients)的概念非常重要。梯度概念的提出是为了按成本最小化的原则引导数据扩散的方向,它定义了一个数据的发送方向和传输速率。当节点从邻居节点接收到查询兴趣报文时,若当前的cache中没有相同查询记录,则DD是基于查询的路由机制2,它由查询扩散阶段、梯度建立阶段、路径加强和数据传输阶段组成,如图1所示。在WSN中,sink节点无法获得目标数据源节点的地理信息。DD中,在查询扩散阶段,sink节点采用泛洪的机制周期性收稿日期:2007 05 21;修回日期:(20050699037)作者简介

8、:李志宇(1977 ),男,博士研究生,主要研究方向为计算机控制与智能控制、无线传感器网络(lizhiyu);史浩山(),、.地向所有传感器节点发送兴趣报文(即描述目标数据报文的属性值);接收到的节点会缓存信息到cache,查找所有匹配的目标数据(即目标数据报文,以下简称数据报文),如图1(a)所示。1 定向扩散算法分析加入新记录,记录中包含了邻居节点指定的数据传输速率即梯度,如图1(b)所示。初始梯度的建立阶段实际上是与查询扩散阶段同时双向进行的。Sink节点发送兴趣报文,而源节点发送数据报文。当网络中的任意节点收到兴趣报文和数据报文2007 07 27 基金项目:国家自然科学基金资助项目(

9、60273009);教育部博士点基金资助项目第5期李志宇,等:DDRLD:支持局部扩散的定向扩散算法#1331 #时,查询成功。采用与单向查询相同的传输方式,可以通过增加兴趣报文和数据报文的数目来提高路径质量。2)路径加强与数据传输阶段在数据传输阶段,源节点将会沿着初始建立的梯度方向将数据报文传输给sink节点,sink节点会对最先收到目标数据的邻居节点发送一个加强信息;接收到加强选择的邻居节点同样加强选择它最先收到新数据的邻居节点,最后形成一条梯度值的最大路径。这样以后收集到的数据报文就会沿着这条最大的路径传输,如图1(c)所示。在定向扩散中,兴趣报文扩散的同时对网络进行了配置,建立了兴趣报

10、文从sink节点到源节点的通道,同时建立了数据报文从源节点到sink节点的通道。兴趣扩散的规则是基于本地信息的,无须对网络拓扑有完整的了解。一个兴趣报文传遍整个网络后,从源节点到sink节点之间的梯度(加强路径)就建立起来了。散兴趣报文在退出网络之前,最多可被转发四次。如果在此之前节点的剩余能量低于设置的能量门限值,就提前终止该节点,继续转发兴趣报文,选择其他符合条件的节点作为下一跳节点。2 2 DDRLD分析DDRLD假定运行在理想的MAC协议之上,在任意连接的节点对之间提供冲突避免的点对点的双工通信。所以,在网络层计算能源消耗时,可以根据网络中的数据传输量来计算3。假定N个传感器节点均匀分

11、布在半径为R,节点传输范围为r的区域,则每个节点都具有r2N/R2-1个邻居节点。节点的发送消耗功率为Ps,接收消耗功率为Pr。在传统DD算法中,兴趣报文以泛洪的机制向整个网络扩散,所有网络消耗的能源为N!Ps+N(r2N/R2-1)!Pr=O(N2)(1)由此可见,传统DD中网络能耗与节点数目的平方同阶。2 支持局部扩散的定向扩散算法:DDRLD传统DD中,当中间节点第一次收到转发的兴趣报文时,便以泛洪的机制向所有邻居节点进行扩散。随着扩散深度的增加,网络中转发的兴趣报文的数目也呈指数增长。当节点密度较大时,会造成网络负载的急剧膨胀,网络性能也迅速下降;而且,WSN中源节点个数有限,对全网进

12、行扩散会造成极大的浪费。因此,在查询扩散阶段和更新查询信息阶段合理减少兴趣报文的扩散范围是十分必要的。另外,传统DD采用兴趣报文的传输速率来建立梯度的模式,容易造成某些靠近sink节点或处于某些关键位置节点的能量很快耗尽,而另外一些节点还有剩余较多的能量。为了增加其他节点被选取为转发节点的概率,改善网络负载平衡,加入节点剩余能量的门限值也是十分必要的。2 1 DDRLD描述a)在兴趣报文扩散的过程中,利用转发节点的剩余能量和到邻居节点的最小跳数来建立梯度。在源节点处,某个邻居节点梯度大小表明了从该邻居节点转发兴趣报文到sink节点的最小跳数。最小跳数是sink节点到源节点多条路径跳数的最小值,

13、反映了路径的最优延迟指标。节点的剩余能量体现了转发节点所在路径最长可能持续的时间。b)梯度的建立过程。兴趣报文携带上一跳节点的最小跳数和节点剩余能量等信息。当兴趣报文通过多条路径到达某节点时,如果该节点同时满足以下三个条件才可以被选取为下一跳节点,即与sink节点建立梯度:(a)节点自身能量高于设置的节点剩余能量门限值;(b)节点所在的路径跳数最小;(c)兴趣报文的扩散深度低于设置的梯度扩散深度阈值。c)梯度的建立过程实质。通过设置梯度扩散深度阈值来减少兴趣报文扩散范围或转发次数;通过设置节点剩余能量的门限值来增加每个节点被选取为转发节点的概率,用来延长节点的平均工作时间和改善网络负载平衡;同

14、时还要满足传统DD中对梯度的要求。d)在DDRLD中,每个兴趣报文最多进行设置的扩散深度,果扩阈值4,DDRLD在一次建立路径的过程中,假定sink节点和源节点发送的报文数目为K,其扩散深度阈值为H,则网络中消耗的能源最大值为KH(Ps+Pr)(2)即DDRLD中网络的消耗和应用程序的性能需求(发送的报文数目与设置的报文扩散深度有关)与传输距离有关,而与网络中的节点数目没有直接关系。由此可以推断出,网络中节点数目越大,DDRLD的优越性就越明显。下面分析DDRLD与传统DD中节点被选取为转发节点的概率。在分析之前先给出相关定义4。定义1 节点Nj转发数据报文由节点Ni路径到达sink节点时,该

15、路径的通信代价为CN,N=cost(Ni)+metric(Nj,Ni)ji(3)其中:CN,jNi表示节点Nj转发数据报文经由节点Ni路径到达sink节点的代价;cost(Ni)表示节点Ni到sink节点的通信代价;metric(Nj,Ni)表示Nj到Ni的通信能量消耗。定义2 metric(Nj,Ni)与节点的能量消耗和节点的剩余能量有关。其计算式为metric(Nj,Ni)=e ijRi(4)其中:e ij表示Nj到Ni直接通信的能量消耗;Ri表示节点Ni的剩余能量; 、 是常量。定义3 节点Nj将Ni加入本地路由表FTj,即把节点Ni选取为转发节点的条件是FTj=i|CN,Nmin(CN

16、,N)jijk(5)下面比较DDRLD与传统DD中节点被选取为转发节点的概率大小。在DDRLD中,由于设定了节点剩余能量的门限值E/X(E为节点初始能量):min(CN,N)=cost(Nk)+e XkjE/jk(6)而在传统DD中,由于没有设定节点剩余能量的门限值,节点Nj将Ni加入本地路由表FTj中的机会就多,在局部的范围内,降低了其他节点被选取为转发节点的概率。通过设定节点剩余能量的门限值可以增加其他节点被选取为转发节点的,#1332#3 仿真实验与结果分析计算机应用研究 第25卷点的初始能量为10J。从图3中可以看出,在相同的仿真场景下,在DDRLD中,整个网络的剩余能量要高于在传统D

17、D下整个网络的剩余能量。这是因为DDRLD中,通过增设梯度的扩散深度阈值,在查询扩散阶段和更新查询信息阶段,减少了兴趣报文扩散范围,从而大大减少网络中传输的数据量;通过设置节点剩余能量的门限值,增大了每个节点被选取为转发节点的概率,延长了节点的平均工作时间,改善了网络负载平衡,降低了网络功耗,从而延长了整个网络生存的时间。仿真基于CMU的NS 2平台。在网络仿真性能评价指标中,主要在端到端的平均延迟和整个网络的剩余能量两个方面对DDRLD进行评估。端到端的平均延迟是指一个数据报文从源节点发送到sink节点所花费的平均时间。整个网络的剩余能量反映了一个传感器网络的生命周期。仿真环境中,节点随机分

18、布在670m!670m的矩形区域,1个sink节点,8个源节点;梯度的扩散深度阈值为4,节点剩余能量的门限值为初始能量的1/32;配置节点的传输范围为R=20m,采用S MAC协议(USC/ISI于2005年在NS 2中成功实现了S MAC);采用较真实的节点能源消耗模型,兴趣报文的发送间隔设为30s。节点其他配置与文献2相同。下面对两种算法进行统计比较。3 1 平均延迟分析在两种算法模式下,节点数目N的变化对数据传输平均延迟的影响如图2所示。每个源节点单位时间生成一个数据报文。随着N的增加,两种算法模式下的平均延迟都有所增大。当N为50100时,DDRLD中,数据传输平均延迟从0 05s上升

19、到0 2s;而传统DD中,平均延迟却从0 2s上升到0 65s。DD中的平均延迟增长的幅度比较大,这是因为在传统DD中,需要更多的节点建立的梯度以接收数据,导致了较大的延迟。可以认为在DDRLD中,网络性能比较稳定,不容易受网络规模的影响。随着节点数目的增大,DDRLD的性能就越明显。3 2 剩余能量分析在两种算法模式下,整个网络中的剩余能量随时间变化的情况如图3所示。设置网络中节点的数目N为100,设每个节(上接第1329页)参考文献:1BOULISA,GANERIWALS,SRIVASTAVAMB.Aggregationinsensornetworks:anenergy accuracyt

20、rade offJ.ElsevierJournalofAdhocNetworks,2003,1(2 3):317 331.2INLANAGONWIWATC,GOVINDANR,ESTRIND,etal.Direc teddiffusionforwirelesssensornetworkingJ.IEEE/ACMTransNetworking,2003,11(1):2 16.3HOURong hu,iSHIHao shan,YANGShao jun.RPDDP:anenergy efficientroutingprotocolsupportingdistributeddataprocessing

21、forwirelesssensornetworksJ.JournalofNorthwesternPolytechn icalUniversity,2006,24(10):614 618.4SHAHRC,RABAEYJM.EnergyawareroutingforlowenergyAdhocsensornetworksC/ProcofIEEEWirelessCommunicationsandNetworkingConference.S.l:IEEE,2002:17 21.量与控制,2004,12(10):932 934,978.7张全海,叶晨洲,施鹏飞.基于multi agents分布式医学诊断系统研究J.信息与控制,2003,32(1):23 27.8赵卫东,盛昭瀚,杜雪寒.基于神经网络的案例推理医疗诊断J.东南大学学报:自然科学版,2000,30(3):46 50.9徐定杰,周远东,桑育黎,等.模糊神经网络控制的医疗诊断系统研究J.中医药学刊,2005,23(5):781 783.10张惠康,钱宗才,屈景辉,等.专家系统及其在医疗诊断中的应用J.第四军医大学学报,2002,23(B12):73 76.11李凡,蔡立晶,田应忠.基于Vague集的医疗诊断系统J.华中科技大学学报:自然科学版,2002,30(10):47 49.12蔡航.基于神经网络的医疗诊断专家系统J.数理医