无线传感器网络的路由算法与仿真实现概要.docx
《无线传感器网络的路由算法与仿真实现概要.docx》由会员分享，可在线阅读，更多相关《无线传感器网络的路由算法与仿真实现概要.docx（11页珍藏版）》请在冰点文库上搜索。
无线传感器网络的路由算法与仿真实现概要
—124
—无线传感器网络的路由算法与仿真实现
屠燕春,郭爱煌
（同济大学电子与信息工程学院信息与通信工程系,上海200092
摘要:
无线传感器网络能够协作地实时监测、感知和采集各种环境或监测对象的信息,并对其进行处理,传送到信息接收者,其关键技术之一是路由算法及实现。
分析了DirectedDiffusion路由算法,用UML统一建模语言对该路由算法进行了建模,在网络模拟工具NS的模块上实现了对该路由算法的模拟仿真,分析了其时延、能耗、数据发送率等网络性能,并与Flooding路由算法作比较。
仿真结果表明DirectedDiffusion路由算法在某些方面有较好的特性。
关键词:
无线传感器网络;UML;路由算法;仿真实现
RoutingAlgorithmsandSimulationofWirelessSensorNetwork
TUYanchun,GUOAihuang
（DepartmentofInformationandCommunicationEngineering,CollegeofElectronicsandInformationEngineering,
TongjiUniversity,Shanghai200092
【Abstract】Wirelesssensornetworkcanbeusedfortesting,sensing,collectingandprocessinginformationofmonitoredobjectsandtransferringtheprocessedinformationforreceivers,anditskeytechniqueistheroutingalgorithms.ThispaperanalyzestheDirectedDiffusionroutingalgorithm,anditismodeledbytheunifiedmodelinglanguageandsimulatedbythenetworksimulator.Accordingtothesimulationresults,theperformancesoftheDirectedDiffusionroutingalgorithmsuchasdelay,averagedissipatedenergy,anddistincteventdeliveryratioareevaluated.ItindicatesthattheDirectedDiffusionroutingalgorithmhasbettercharacteristicsinsomeaspects.【Keywords】Wirelesssensornetwork;Unifiedmodelinglanguage;Routingalgorithm;Simulation
计算机工程ComputerEngineering第32卷第22期
Vol.32No.222006年11月
November2006
·网络与通信·
文章编号:
1000—3428（200622—0124—03
文献标识码:
A中图分类号:
TP393
无线传感器网络是由大量传感节点通过无线通信技术自
组织构成的网络,它集成了传感器、微机电系统、现代网络和无线通信等技术,目的是感知、采集和处理网络覆盖范围内感知对象的信息,并转发给观察者,是以数据处理为中心的系统。
无线传感器网络由3个主要部分组成:
传感节点（Sensor,终端节点（Sink和观察对象。
传感节点以自组织形式构成网络,通过多跳中继方式将监测数据传到Sink,最终借助长距离或临时建立的Sink链路将整个区域内的数据传送到远程中心进行集中处理。
传感器网络在军事、环境、健康、家庭和其他商业领域有着广阔的应用前景,在空间探索和灾难拯救等特殊的领域,也有其得天独厚的技术优势[1,2]。
无线传感器网络涉及多学科交叉的研究领域,有许多关键技术有待发现和研究,其中路由协议的设计极富挑战性,
它与无线Adhoc网络有着许多不同的特色。
针对无线传感器网络中数据传送的特点和难题,许多新的路由协议得到了提出,这些路由协议可以大致分为4类:
洪泛式路由协议,典型代表有Flooding协议;层次式路由协议,典型代表是低功耗自适应聚类路由算法;以数据为中心的路由协议,代表有DirectedDiffusion协议;基于位置信息的路由协议,代表有GEAR协议[3]。
本文在DirectedDiffusion协议分析描述的基础上,通过建模和仿真对DirectedDiffusion路由算法的性能进行评价。
1DirectedDiffusion协议分析与建模
1.1DirectedDiffusion协议的算法分析
DirectedDiffusion是ChalermekIntanagon-wiwat等提出的一种新的数据扩散算法[4]。
在无线传感器网络中,终端节点（Sink向整个网络发送传感任务,该任务被称为interest,
即需要网络中的传感器探测的目标的描述。
当传感节点知道了这个任务,即开始探测网络区域,寻找探测目标。
探测到符合interest要求的目标的节点将生成数据向Sink发送。
不同的路由协议将在interest信息在网络内的扩散方式、数据传送方式、路由的建立和去除等方面有所不同,这些不同也将导致网络在某些性能要求方面的差异。
DirectedDiffusion算法的主要特点是在数据传送过程中,会计算出几条代价较低的数据通路,进行比较直接的、方向明确的数据传输。
可以按查询扩散、目标感测和数据传播3条不同的路径来简单描述DirectedDiffusion算法。
1.1.1查询扩散
被命名的任务描述构成了一个查询interest,通过Sink注入到网络中。
Sink周期性地向邻节点广播interest,让它到网络中搜寻是否有适当的响应节点。
网络的每个节点都有一个任务缓冲区interestcache。
Cache中的条目都是不同的interest值。
当一个节点B收到从邻节点A传送过来的一个interest后,它会搜寻自己的interestcache里是否存在着与之对应的任务入口interestentry。
如果没有匹配的entry,那么就为新收到的查询建立一个新的entry,这时该interestentry将有唯一的一个指向interest发送方A节点的gradient（梯度,并附带着数据发送率和时限信息。
如果存在与该interest匹配的entry,可分两种情况:
一种是该interestentry包含指向A
作者简介:
屠燕春（1983-,女,硕士生,主研方向:
AdHoc网络,无线传感器网络技术及其实现;郭爱煌,博士、副教授收稿日期:
2005-12-08E-mail:
pumpkin2002@
的梯度,这时只需要将interestentry中的interest建立时间和匹配梯度中的interest持续时限字段更新;另一种情况是该entry中没有指向A的梯度,这时就需要在梯度列表中增加指向A的一项,并更新interestentry的建立时间。
当interestentry中的梯度项的时限过期后,该梯度项将会被从interestentry中删除。
节点B收到一个interest之后,它要能够判断是否要将该interest再传给它的邻接点。
对于它的邻节点来说,这个interest仅仅是来自B这个数据源的,而不管它是否是从很远以外的某个Sink发出的。
因此interestentry中不包含Sink的信息。
并不是所有的interest都会被重传,节点应该有记忆功能,节点B如果发现自己已经对该interest进行过了广播,它就不再对该interest进行重传。
interest扩散的同时对网络进行了配置,建立了若干条从Sink到信源的通道,用于将需要的数据送回Sink。
1.1.2目标感测
处于某区域的传感节点收到interest之后,就启动自己的功能系统,收集环境信息。
没有任务时,让节点处于半休眠状态。
当传感节点发现了目标,它就会搜寻它的interestcache,寻找匹配的interestentry,若能找到,就计算所有的输出梯度中的最高的数据发送率。
这样做是因为节点观测的发送率必须要满足对数据发送率要求最高的任务。
然后该工作节点就以这个速率向它的interestentry中记录的梯度所指的目标邻节点发送观测到的事件。
1.1.3数据传播
当一个节点从它的邻节点处收到某条数据以后,它会在它的cache中寻找一条与该数据相匹配的interestentry,若找不到,说明该节点己经不再需要这个数据了,就将该条数据扔掉;若找到,则再查看与该interestentry相关联的数据cache,这里记录了该节点收到并处理过的对应该interestentry的数据。
若在该数据cache中找到了与收到的数据匹配的项,就将收到的数据扔掉,因为本节点己收到过该数据。
否则,将接收的数据添加到相应的数据cache中,并将其转发给匹配interestentry的梯度中记录的目标邻节点。
通过对自己的数据cache进行分析,节点可以计算出它所收到的数据的发送率。
在转发一个数据之前,节点需要检查相应的interestentry中的各个梯度中的数据发送率。
对于要求的发送率等于或高于节点实际收到的发送率的梯度,节点只需将收到的数据全部转发给该梯度中记录的目标邻节点便可。
而对于要求的发送率比接收到的实际的数据发送速率低的梯度,节点就需要对收到的数据按照一定的比例转发。
Interest在传播的过程中建立了许多梯度,这些梯度连通起来构成了Sink与信源之间的许多条通路。
信源发现目标后,它会发送试探性的数据,这些数据沿上述的若干条通道返回给Sink,发送的速率较低。
当Sink收到这些试探性的数据后,它会根据从不同的通路接收数据的效果,选出一条或几条“高效”的通路,在这些通路上传送数据。
这个对路径进行筛选的过程,称之为对合适通路的“加强”。
1.2DirectedDiffusion协议的建模
UML是一种标准化的建模语言,用UML的活动图对DirectedDiffusion协议进行建模,依据建模进行仿真分析。
UML建模首先确定一个传感节点,然后分析其可能遇到的所有情况。
初始状态的传感节点可能遇到的情况有3种:
接收到查询信息,感测到目标对象以及接收到数据信息。
对于这3种情况,活动图通过相应的3个流程来表示,根据每个流程的具体情况继续做出判断,采取不同的措施,进而得出不同的最终状态。
2仿真与结果分析
2.1仿真环境
仿真实验中,为了测试网络规模对DirectedDiffusion协议的性能影响,设置5个不同规模的网络场景,分别是50、100、150、200、250个节点。
在50个节点的网络中,节点随机分布在160×160m2的区域内。
随着节点数的增加,场景的大小也将随着增大,从而保持场景内节点的密度不变。
这样可以避免其他参数的变化对网络造成的影响。
仿真时,设定网络中有一个信源和一个Sink,通过仿真观察interest的扩散、路由的建立,并分析延时、能耗、数据发送率等体现协议性能的参数。
2.2仿真结果
2.2.1网络静态情况
网络中随着节点数量的增加和场景的增大,interest从Sink扩散到信源的时延也随之增加（图1。
在DirectedDiffusion协议中,interest的扩散过程是向所有的相邻节点扩散的过程,相邻节点在接收到interest后,作相应的处理后继续转发该节点,此时的interest是在整个网络中扩散的。
interest扩散过程其实是对网络进行了配置,建立了若干条从Sink到信源的通道图。
050100150200250300
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
diffusionS
i
n
k
将
i
n
t
e
r
e
s
t
发
送
到
信
源
的
时
延
（
s
节点数
图1查询扩散时延
节点数增加场景增大时,信源和Sink间建立连接所需要的时间也增大（图2,网络的路由的跳数也增大（图3。
节点数
0501001502002503000
0.5
1
1.5
diffusion路
由
建
立
时
间
（
s
图2路由建立时延
节点数
050100150200250300
1
2
3
4
5
6
7
8
9
10
diffusion路
由
跳
数
（
跳
图3平均路由跳数
—125—
—126
—信源探测到符合要求的数据后,会转发给该interest对应的符合要求的所有相邻节点;当下一级节点接收到该数据后也是按相同的规则进行转发,直到数据被转发到Sink,此时数据发送是洪泛式的,数据从信源转发到Sink的时延要比已经进行过通路的加强的时延要大很多,并且随着网络的规模的增大,这个路由建立的时延也会增大。
图4是以数据为中心的DirectedDiffusion路由协议和洪泛式Flooding路由协议在同样的测试场景下发送一个数据的平均时延,可以看到DirectedDiffusion协议在时延方面比Flooding协议性能更优越。
这是因为Flooding算法使用扩散法发送数据,信源首先将数据传送给它的每一个邻节点,每一个邻节点又将其传输给各自的每一个邻节点,除了刚给它们发送数据的节点外。
如此继续下去,直到将数据传输到Sink或者为该数据所设定的生命期限变为零或者所有的节点拥有此数据为止,这样的数据传播没有特定的路由。
而DirectedDiffusion协议中规定,数据在被传送到Sink后,Sink就会加强一条或几条通路,此后信源发送的数据就不需要在整个网内进行传送,而是通过加强的通路进行传送。
节点数
50
100
150200
250
300
00.050.10.150.20.250.3diffusion
flooding
平均时延（s
图4网络平均时延
图5是在传感节点的发送功率为660mW,接收功率为395mW,空闲时功率为35mW的情况下,不同的路由协议在信源和Sink间成功发送一个数据,网络中所有节点平均消耗的能量。
节点数
050100
150********0
0.050.10.150.20.250.3diffusionflooding
平均能耗（焦耳
图5平均能耗（焦耳/节点/收到一个数据
图6是在空闲时节点能耗极低的情况下成功传送一个数据的节点平均能耗,可以看到使用DirectedDiffusion协议时网络中节点的平均能耗要比使用Flooding协议时网络节点的平均能耗低很多。
50
100
150200
250
300
00.0020.0040.0060.0080.010.0120.0140.0160.0180.02diffusion
flooding
节点数
平均能耗（焦耳
图6平均能耗（焦耳/节点/收到一个数据
在DirectedDiffusion协议中,数据沿着“高效的”通路传送,能耗集中在几个通路上的节点,且节点在发送一个数据后就会拒绝发送并丢弃接收到的同样的数据,这样有效避免了冗余数据消耗网络的资源。
Flooding协议中,数据是在全网范围内广播的,网络中的能耗相对较大。
由仿真结果,在仿真过程中,网络节点没有变化（节点位置固定,有效节点数不变且网络没有拥塞的情况下,使用DirectedDiffusion协议和Flooding协议,数据成功发送率都是100%。
2.2.2网络动态情况
当部分节点在仿真过程中失效时,数据发送也会发生相应的变化。
设置部分节点的初始能量为0.5焦耳,这部分节点将在能量耗尽后失效,在这种情况下会有一定的数据丢失（图7,失效的节点数量越多,丢失的数据也随之增多。
节点数
050100
150
200250300
00.10.20.30.40.50.60.70.8
0.91
数据成功发送率（%
10%的节点失效20%的节点失效
图7网络动态情况下的数据成功发送率
3结论
无线传感器网络有着十分广阔的应用前景,尽管它还不十分成熟,但随着越来越多的关注和研究,会有更多的技术方案为其提供各种支持。
本文对DirectedDiffusion协议进行了分析,并使用UML统一建模语言进行建模。
通过网络模拟软件NS对该协议进行模拟,从中可以看到网络中的时延随着网络规模的增大而增大,平均时延比使用Flooding协议时小;网络中的平均能耗也随节点数的增加而变化,节点空闲时刻的能耗极低时,使用DirectedDiffusion协议的网络能耗要比使用Flooding协议小很多,能源有效性较高;当网络动态变化时,随着失效节点数量的增加,数据成功发送率将降低。
这些结果表明DirectedDiffusion路由算法在某些方面有较好的性能。
参考文献
1任丰源,黄海宁,林闯.无线传感器网络[J].软件学报,2003,14（7:
1282-1291.
2李建中,李金宝,石胜飞.传感器网络及其数据管理的概念、问题与进展[J].软件学报,2003,14（10:
1717-1727.
3郑增威,吴朝晖.若干无线传感器网络路由协议比较研究[J].计算机工程与设计,2003,24（9:
28-31.
4IntanagonwiwatC,GovindanR,EstrinD,etal.DirectedDiffusionforWirelessSensorNetworking[J].IEEE/ACMTransactionson
Networking,2003,11（1:
2-15.
升级会员 