无线传感器网络的路由算法与仿真实现概要.docx

1、无线传感器网络的路由算法与仿真实现概要124 无线传感器网络的路由算法与仿真实现屠燕春,郭爱煌(同济大学电子与信息工程学院信息与通信工程系,上海 200092摘 要:无线传感器网络能够协作地实时监测、感知和采集各种环境或监测对象的信息,并对其进行处理,传送到信息接收者,其关键技术之一是路由算法及实现。分析了Directed Diffusion 路由算法,用UML 统一建模语言对该路由算法进行了建模,在网络模拟工具NS 的模块上实现了对该路由算法的模拟仿真,分析了其时延、能耗、数据发送率等网络性能,并与Flooding 路由算法作比较。仿真结果表明Directed Diffusion 路由算法在

2、某些方面有较好的特性。 关键词:无线传感器网络;UML ;路由算法;仿真实现Routing Algorithms and Simulation of Wireless Sensor NetworkTU Yanchun, GUO Aihuang(Department of Information and Communication Engineering, College of Electronics and Information Engineering,Tongji University, Shanghai 200092【Abstract 】Wireless sensor network c

3、an be used for testing, sensing, collecting and processing information of monitored objects and transferring the processed information for receivers, and its key technique is the routing algorithms. This paper analyzes the Directed Diffusion routing algorithm, and it is modeled by the unified modeli

4、ng language and simulated by the network simulator. According to the simulation results, the performances of the Directed Diffusion routing algorithm such as delay, average dissipated energy, and distinct event delivery ratio are evaluated. It indicates that the Directed Diffusion routing algorithm

5、has better characteristics in some aspects. 【Key words 】Wireless sensor network; Unified modeling language; Routing algorithm; Simulation计 算 机 工 程Computer Engineering 第32卷 第22期Vol.32 No.22 2006年11月November 2006网络与通信文章编号:10003428(200622012403文献标识码:A 中图分类号:TP393无线传感器网络是由大量传感节点通过无线通信技术自组织构成的网络,它集成了传感器、

6、微机电系统、现代网络和无线通信等技术,目的是感知、采集和处理网络覆盖范围内感知对象的信息,并转发给观察者,是以数据处理为中心的系统。无线传感器网络由3个主要部分组成:传感节点(Sensor,终端节点(Sink和观察对象。传感节点以自组织形式构成网络,通过多跳中继方式将监测数据传到Sink ,最终借助长距离或临时建立的Sink 链路将整个区域内的数据传送到远程中心进行集中处理。传感器网络在军事、环境、健康、家庭和其他商业领域有着广阔的应用前景,在空间探索和灾难拯救等特殊的领域,也有其得天独厚的技术优势1,2。无线传感器网络涉及多学科交叉的研究领域,有许多关键技术有待发现和研究,其中路由协议的设计

7、极富挑战性,它与无线Ad hoc 网络有着许多不同的特色。针对无线传感器网络中数据传送的特点和难题,许多新的路由协议得到了提出,这些路由协议可以大致分为4类:洪泛式路由协议,典型代表有Flooding 协议;层次式路由协议,典型代表是低功耗自适应聚类路由算法;以数据为中心的路由协议,代表有Directed Diffusion 协议;基于位置信息的路由协议,代表有GEAR 协议3。本文在Directed Diffusion 协议分析描述的基础上,通过建模和仿真对Directed Diffusion 路由算法的性能进行评价。1 Directed Diffusion 协议分析与建模1.1 Direc

8、ted Diffusion 协议的算法分析Directed Diffusion 是Chalermek Intanagon- wiwat 等提出的一种新的数据扩散算法4。在无线传感器网络中,终端节点(Sink向整个网络发送传感任务,该任务被称为interest ,即需要网络中的传感器探测的目标的描述。当传感节点知道了这个任务,即开始探测网络区域,寻找探测目标。探测到符合interest 要求的目标的节点将生成数据向Sink 发送。不同的路由协议将在interest 信息在网络内的扩散方式、数据传送方式、路由的建立和去除等方面有所不同,这些不同也将导致网络在某些性能要求方面的差异。Directed

9、 Diffusion 算法的主要特点是在数据传送过程中,会计算出几条代价较低的数据通路,进行比较直接的、方向明确的数据传输。可以按查询扩散、目标感测和数据传播3条不同的路径来简单描述Directed Diffusion 算法。 1.1.1 查询扩散被命名的任务描述构成了一个查询interest ,通过Sink 注入到网络中。Sink 周期性地向邻节点广播interest ,让它到网络中搜寻是否有适当的响应节点。网络的每个节点都有一个任务缓冲区interest cache 。Cache 中的条目都是不同的interest 值。当一个节点B 收到从邻节点A 传送过来的一个interest 后,它会

10、搜寻自己的interest cache 里是否存在着与之对应的任务入口interest entry 。如果没有匹配的entry ,那么就为新收到的查询建立一个新的entry ,这时该interest entry 将有唯一的一个指向interest 发送方A 节点的gradient(梯度,并附带着数据发送率和时限信息。如果存在与该interest 匹配的entry ,可分两种情况:一种是该interest entry 包含指向A作者简介:屠燕春(1983-,女,硕士生,主研方向:Ad Hoc 网络,无线传感器网络技术及其实现;郭爱煌,博士、副教授 收稿日期:2005-12-08 E-mail :

11、pumpkin2002的梯度,这时只需要将interest entry中的interest建立时间和匹配梯度中的interest持续时限字段更新;另一种情况是该entry中没有指向A的梯度,这时就需要在梯度列表中增加指向A的一项,并更新interest entry的建立时间。当interest entry 中的梯度项的时限过期后,该梯度项将会被从interest entry 中删除。节点B收到一个interest之后,它要能够判断是否要将该interest再传给它的邻接点。对于它的邻节点来说,这个interest仅仅是来自B这个数据源的,而不管它是否是从很远以外的某个Sink发出的。因此int

12、erest entry中不包含Sink 的信息。并不是所有的interest都会被重传,节点应该有记忆功能,节点B如果发现自己已经对该interest进行过了广播,它就不再对该interest进行重传。interest扩散的同时对网络进行了配置,建立了若干条从Sink到信源的通道,用于将需要的数据送回Sink。1.1.2 目标感测处于某区域的传感节点收到interest之后,就启动自己的功能系统,收集环境信息。没有任务时,让节点处于半休眠状态。当传感节点发现了目标,它就会搜寻它的interest cache,寻找匹配的interest entry,若能找到,就计算所有的输出梯度中的最高的数据发

13、送率。这样做是因为节点观测的发送率必须要满足对数据发送率要求最高的任务。然后该工作节点就以这个速率向它的interest entry中记录的梯度所指的目标邻节点发送观测到的事件。1.1.3 数据传播当一个节点从它的邻节点处收到某条数据以后,它会在它的cache中寻找一条与该数据相匹配的interest entry,若找不到,说明该节点己经不再需要这个数据了,就将该条数据扔掉;若找到,则再查看与该interest entry相关联的数据cache,这里记录了该节点收到并处理过的对应该interest entry的数据。若在该数据cache中找到了与收到的数据匹配的项,就将收到的数据扔掉,因为本节

14、点己收到过该数据。否则,将接收的数据添加到相应的数据cache中,并将其转发给匹配interest entry的梯度中记录的目标邻节点。通过对自己的数据cache进行分析,节点可以计算出它所收到的数据的发送率。在转发一个数据之前,节点需要检查相应的interest entry中的各个梯度中的数据发送率。对于要求的发送率等于或高于节点实际收到的发送率的梯度,节点只需将收到的数据全部转发给该梯度中记录的目标邻节点便可。而对于要求的发送率比接收到的实际的数据发送速率低的梯度,节点就需要对收到的数据按照一定的比例转发。Interest在传播的过程中建立了许多梯度,这些梯度连通起来构成了Sink与信源之

15、间的许多条通路。信源发现目标后,它会发送试探性的数据,这些数据沿上述的若干条通道返回给Sink,发送的速率较低。当Sink收到这些试探性的数据后,它会根据从不同的通路接收数据的效果,选出一条或几条“高效”的通路,在这些通路上传送数据。这个对路径进行筛选的过程,称之为对合适通路的“加强”。1.2 Directed Diffusion协议的建模UML是一种标准化的建模语言,用UML的活动图对Directed Diffusion协议进行建模,依据建模进行仿真分析。UML建模首先确定一个传感节点,然后分析其可能遇到的所有情况。初始状态的传感节点可能遇到的情况有3种:接收到查询信息,感测到目标对象以及接

16、收到数据信息。对于这3种情况,活动图通过相应的3个流程来表示,根据每个流程的具体情况继续做出判断,采取不同的措施,进而得出不同的最终状态。2 仿真与结果分析2.1 仿真环境仿真实验中,为了测试网络规模对Directed Diffusion协议的性能影响,设置5个不同规模的网络场景,分别是50、100、150、200、250个节点。在50个节点的网络中,节点随机分布在160160m2的区域内。随着节点数的增加,场景的大小也将随着增大,从而保持场景内节点的密度不变。这样可以避免其他参数的变化对网络造成的影响。仿真时,设定网络中有一个信源和一个Sink,通过仿真观察interest的扩散、路由的建立

17、,并分析延时、能耗、数据发送率等体现协议性能的参数。2.2 仿真结果2.2.1 网络静态情况网络中随着节点数量的增加和场景的增大,interest从Sink扩散到信源的时延也随之增加(图1。在Directed Diffusion协议中,interest的扩散过程是向所有的相邻节点扩散的过程,相邻节点在接收到interest后,作相应的处理后继续转发该节点,此时的interest是在整个网络中扩散的。interest扩散过程其实是对网络进行了配置,建立了若干条从Sink到信源的通道图。0501001502002503000.10.20.30.40.50.60.70.80.91diffusion

18、Sink将interest发送到信源的时延(s节点数图1 查询扩散时延节点数增加场景增大时,信源和Sink间建立连接所需要的时间也增大(图2,网络的路由的跳数也增大(图3。节点数050100150200250300 00.511.5diffusion 路由建立时间(s图2 路由建立时延节点数05010015020025030012345678910diffusion 路由跳数(跳图3 平均路由跳数125126信源探测到符合要求的数据后,会转发给该interest 对应的符合要求的所有相邻节点;当下一级节点接收到该数据后也是按相同的规则进行转发,直到数据被转发到Sink ,此时数据发送是洪泛式的

19、,数据从信源转发到Sink 的时延要比已经进行过通路的加强的时延要大很多,并且随着网络的规模的增大,这个路由建立的时延也会增大。图4是以数据为中心的Directed Diffusion 路由协议和洪泛式Flooding 路由协议在同样的测试场景下发送一个数据的平均时延,可以看到Directed Diffusion 协议在时延方面比Flooding 协议性能更优越。这是因为Flooding 算法使用扩散法发送数据,信源首先将数据传送给它的每一个邻节点,每一个邻节点又将其传输给各自的每一个邻节点,除了刚给它们发送数据的节点外。如此继续下去,直到将数据传输到Sink 或者为该数据所设定的生命期限变为

20、零或者所有的节点拥有此数据为止,这样的数据传播没有特定的路由。而Directed Diffusion 协议中规定,数据在被传送到Sink 后,Sink 就会加强一条或几条通路,此后信源发送的数据就不需要在整个网内进行传送,而是通过加强的通路进行传送。节点数5010015020025030000.050.10.150.20.250.3diffusionflooding平均时延(s 图4 网络平均时延图5是在传感节点的发送功率为660mW ,接收功率为395mW ,空闲时功率为35mW 的情况下,不同的路由协议在信源和Sink 间成功发送一个数据,网络中所有节点平均消耗的能量。节点数0501001

21、50*00.050.10.150.20.250.3diffusion flooding平均能耗(焦耳图5 平均能耗(焦耳/节点/收到一个数据图6是在空闲时节点能耗极低的情况下成功传送一个数据的节点平均能耗,可以看到使用Directed Diffusion 协议时网络中节点的平均能耗要比使用Flooding 协议时网络节点的平均能耗低很多。5010015020025030000.0020.0040.0060.0080.010.0120.0140.0160.0180.02diffusionflooding节点数平均能耗(焦耳图6 平均能耗(焦耳/节点/收到一个数据在Directed Diffusi

22、on 协议中,数据沿着“高效的”通路传送,能耗集中在几个通路上的节点,且节点在发送一个数据后就会拒绝发送并丢弃接收到的同样的数据,这样有效避免了冗余数据消耗网络的资源。Flooding 协议中,数据是在全网范围内广播的,网络中的能耗相对较大。由仿真结果,在仿真过程中,网络节点没有变化(节点位置固定,有效节点数不变且网络没有拥塞的情况下,使用Directed Diffusion 协议和Flooding 协议,数据成功发送率都是100%。2.2.2 网络动态情况当部分节点在仿真过程中失效时,数据发送也会发生相应的变化。设置部分节点的初始能量为0.5焦耳,这部分节点将在能量耗尽后失效,在这种情况下会

23、有一定的数据丢失(图7,失效的节点数量越多,丢失的数据也随之增多。节点数05010015020025030000.10.20.30.40.50.60.70.80.91数据成功发送率(%10%的节点失效20%的节点失效图7 网络动态情况下的数据成功发送率3 结论无线传感器网络有着十分广阔的应用前景,尽管它还不十分成熟,但随着越来越多的关注和研究,会有更多的技术方案为其提供各种支持。本文对Directed Diffusion 协议进行了分析,并使用UML 统一建模语言进行建模。通过网络模拟软件NS 对该协议进行模拟,从中可以看到网络中的时延随着网络规模的增大而增大,平均时延比使用Flooding

24、协议时小;网络中的平均能耗也随节点数的增加而变化,节点空闲时刻的能耗极低时,使用Directed Diffusion 协议的网络能耗要比使用Flooding 协议小很多,能源有效性较高;当网络动态变化时,随着失效节点数量的增加,数据成功发送率将降低。这些结果表明Directed Diffusion 路由算法在某些方面有较好的性能。参考文献1 任丰源, 黄海宁, 林 闯. 无线传感器网络J. 软件学报, 2003, 14(7: 1282-1291.2 李建中, 李金宝, 石胜飞. 传感器网络及其数据管理的概念、问题与进展J. 软件学报, 2003, 14(10: 1717-1727.3 郑增威, 吴朝晖. 若干无线传感器网络路由协议比较研究J. 计算机工程与设计, 2003, 24(9: 28-31.4 Intanagonwiwat C, Govindan R, Estrin D, et al. Directed Diffusion for Wireless Sensor NetworkingJ. IEEE/ACM Transactions onNetworking, 2003, 11(1: 2-15.