无线传感器网络簇间节能路由算法

1、2009年第11期,第42卷 通 信 技 术 Vol.42,No.11,2009 总第215期Communications Technology No.215,Totally无线传感器网络簇间节能路由算法胡 钢, 朱佳奇, 陈世志(河海大学 计算机及信息工程学院,江苏 常州 213000【摘 要】针对基于分簇网络的无线传感器网络簇间路由协议,让簇首和Sink节点直接通信或通过簇首节点转发数据造成能耗不均,节点过早死亡的缺陷。文中提出一种基于网关节点模型的无线传感器网络簇间路由算法,通过簇头与网关节点、网关节点自身建立虚电路,制定存储转发路由,将数据转发给Sink节点。并引入延时等待机制,增强了

2、簇间信息的融合度,此算法适用于大规模无线传感器网络,有良好的可扩展性。仿真表明在能量节省等性能上与传统簇间路由算法相较有较大提高。【关键词】无线传感器网络;网关节点模型;簇;簇间路由【中图分类号】TN92 【文献标识码】A【文章编号】1002-0802(200911-0135-03Study on Power-Scant Cluster-Level Routing Algorithm of WSNbased on Clustered NetworkHU Gang, ZHU Jia-qi, CHEN Shi-zhi(Computer & Engineering College, Hoha

3、i University, Changzhou Jiangsu 213000, China【Abstract】Cluster-level routing protocol of WSN based on clustered network forces cluster head nodes to directly communicate with Sink nodes or makes cluster head nodes transmit data, thus causing unequal energy consumption and early death of the nodes. T

4、his paper proposes a gateway nodes model-based cluster-level routing algorithm of WSN. In this model, the virtual circuit is built between cluster head nodes and gateway nodes, and in gateway nodes itself. The store-send routing is established by cluster head nodes and gateway nodes, so the data cou

5、ld transmit to Sink node efficiently. The time-delay mechanism is also introduced in this algorithm, thus to enhance interfusion degree of the cluster-level information. This algorithm is applicable to great-scale wireless sensor network, and has good expansibility. The simulation shows that the new

6、 algorithm is of great improvement on energy consumption as compared with traditional cluster-level routing protocol.【Key words】WSN; gateway nodes model; cluster; cluster-level routing0 引言无线传感器网络1-3集成了传感器技术、嵌入式计算技术、无线通信技术以及分布式信息处理技术4。无线传感器网络是其目的是协作地感知、采集和处理网络覆盖区域中感知对象的信息,并发送给观察者。预设监测区域内大量传感器节点通过自组织的

7、形式构成无线传感器网络,感知被测对象、采集监测数据并且进行处理后以无线的方式逐步发送到汇聚节点(Sink 节点,然后通过Sink节点连接至internet5。由于无线传感器网络的节点能量有限且能量不可补充,设计节能有效的路由机制能延长整个网络的生存周期,因此合理的路由协议是无线传感器网络研究的重点问题。1 现有算法分析传统的基于分簇网络的簇间通信方式有以下两种:(1单跳通信6-7分簇网络中各簇的簇首节点和Sink节点直接通信,提高自己的发射功率,扩大自己的通信半径将一段时间内收集的数据直接发送到Sink节点。簇间单跳通信方式要求所有节点都有与簇首直接通信的能力,这不利于大规模网络的建立。远距离

8、通信会使节点能量迅速损耗,距离Sink节点较远的簇首节点会很快死亡,从而降低了网络的连通性和减少了网络的生存周期。(2多跳通信6-7收稿日期:2008-11-06。基金项目:中国水利水电科学研究院开放研究基金资助(水科科技便函2008010号。作者简介:朱佳奇(1984-,男,硕士研究生,主要研究方向为无线传感器网络;胡钢(1958-,男,教授,主要研究方向为无线传感器网络;陈世志(1984-,男,硕士研究生,主要研究方向为无线传感器网络。135136 分簇网络中各簇的簇首节点通过多跳方式存储转发数据,向相邻簇的簇首节点发送数据,通过相邻簇的簇首节点将数据转发至Sink 节点。多跳通信方式,不

9、需要簇首节点有直接与Sink 节点通信的能力,避免了直接与Sink 节点通信所耗费的大量能量,能很好的减少各个簇首在簇间通信时的能量损耗。但是通过簇首转发数据选择的路径并不一定是最优路径,簇间通信的能量损耗并不一定最小。2 网络模型提出无线传感器网络可以用无向图来表示:G =(V ,E 。V 表示传感器节点的集合,E 表示无线双向通信链路的集合。对于i s V ,R 为其最大通信半径,i S A 表示i s 的射频覆盖范围。发送节点i s 和接收节点j s 之间的距离,用(,i j d s s 表示。在节点i s 的射频覆盖范围i S A 内节点的集合用(,i i s i S RF s A =

10、表示。簇首(CH的集合用H 表示,H V 。簇首i h 所在簇节点的集合用(,i i h i h C h M =表示,其中i h M 表示簇内成员节点的集合。根据以上的描述,在网络分簇的过程中s V ,j h i k h h s C s RF s RF 其中,k j h h H 。即s 是簇首i h 所在簇的成员节点,且其在簇首节点,.k j h h 的射频通信覆盖范围以内,也就是说在分簇过程中节点s 同时收到簇首节点,.k j h h 发出的簇首申明,并以相应判断准则最终选择加入簇首i h 所在的簇,成为其成员节点。定义这样的节点s 为簇,k j h h 的网关节点,定义网关节点的集合为GT

11、 V 。3 算法描述为减少簇内通信能量消耗,采用贪婪算法1,7进行多跳通信,节点在邻居节点中选择到事件区域代价最小的节点作为下一跳节点。但是由于节点只知道局部拓扑信息,会遇到路由空洞1-2的问题和重复路径传输问题,反而增加了能量的消耗。算法将重点解决以上问题。 无线传感器网络按照分簇算法进行分簇,确定各个簇的簇首节点和相应的成员节点; 按照上述网络模型,确定分簇后的网关节点集合,这些网关节点对向它发送簇首申明的所有簇首节点发送通知,申明其网关节点的身份; Sink 节点广播兴趣到达事件区域,节点集数据,并按照分簇网络的结构向簇首节点传输信息。在此传输过程中,将自己的剩余能量和地理位置坐标一并传

12、输给簇首节点; 各簇首节点收到簇内成员节点的剩余能量后,计算其平均值作为该簇的平均能量;之后,簇首节点将簇内各成员节点的位置信息、剩余能量以及该簇平均能量信息,备份并发送给网关节点。这样网关节点就拥有了相邻簇的簇内信息; 事件区域内的簇首节点,在其射频通信范围内寻找距Sink 节点最近的网关节点作为目的节点,并按照贪婪算法多跳发送数据;按此方法在网关节点之间建立一条虚电路。之后根据虚电路建立网关节点的等待时序。如图1所示,簇首节点A、B、C、D、E、F 分别选择符合条件的网关节点111111a b c d e f 、各自目的节点发送数据。而在网关节点之间建立起端到端的逻辑信道1111a b f

13、 e ,111c d e 同样按照贪婪算法多跳发送数据。由于多跳路由,是由具有全局拓扑信息的节点制定的,所以可以避免贪婪算法带来的路 由空洞的问题; 1b图1簇间通信数据转发示意 解决重复路由传输问题,在簇间通信阶段网关节点接收到数据后引入延时等待机制。为了实现各个簇采集的数据进行数据融合,从距离Sink 节点最远的簇首节点开始,越靠近Sink 节点的网关节点延时越长。当网关节点延时结束后,立刻以下一个网关节点为目的节点,多跳传输数据。如图1中,当网关节点1a 收到距离Sink 节点最远的簇首节点A 发来的数据后,直接以网关节点1b 为目的节点按贪婪算法制定路由,并多跳传输数据;而当1b 收到

14、来自簇首B 发来的信息时,则等待T (2R 时间,在此时间段中等待下级节点发来的数据,其中R 为无线传感器节点的最大通信半径,T (2R 为数据包传到2R 距离所需要的时间。以此类推1b 的上级网关节点1f 等待延时为2T (2R ,1e 为3T (2R ,1d 为2(2T R ,1c 为(2T R 。延时等待机制减少簇间传输时网络路由的重复使用次数,达到节约能量的目的。4 网络仿真网络仿真采用NS2仿真软件,仿真环境参考相关文 献8。仿真中将101个节点(1个Sink 节点随机分布在500 m×500 m 的区域中.,节点的默认通信半径100 m,节点的最大传输半径为500 m,节

15、点的初始能量为1J,传输功率设置为37.2e J/bit,接收功率设置为33.5e J/bit,空闲等待功率消耗为0.0025J/s,规定每10s 为一个周期,簇首节点向Sink 节点传输数据,并忽略多跳通信时存储转发带来的延时,网络分簇基于LEACH 路由协议。改进后的簇间通信路由算法通过建立簇间网关节点间端到端的虚电路,建立了一条将数据发送到Sink 节点的逻辑信道。数据存储转发的路由,由具有全局路由信息的网关节点和簇首节点制定,减少了发生路由空洞的可能性。通过137引入延时等待机制,不但可完成簇间数据融合,而且减少了重复路由使用的次数。从图2、图3中可以看出,改进后的簇间路由算法比传统的

16、直接与Sink 节点通信和局部贪婪算法,在性能上有明显的提升。图2 剩余能量图3 存活节点5 结语本文提出了一种基于分簇网络的簇间路由算法的改进方案,针对传统的簇间路由算法的不足,建立了带网关节点的无线传感器网络的网络模型,同时在网络模型中引入建立了虚电路,增加了延时等待机制。本改进算法不受无线传感器规模限制,适用于大规模无限传感器网络,并具有良好的扩展性。参考文献1 孙利民,李建中,陈渝,等.无线传感器网络M. 北京:清华大学出版社,2006.2 Holger Karl, Andreas Willig. Protocols and Architectures forWireless Sens

17、or NetworkM. 第一版,北京:电子工业出版社,2007.3 Di Wu, Gang Hu. Research and Modifications on ClusteringAlgorithm of Routing Protocols for Wireless Sensor NetworksR. 深圳: International Conference on Informatics and Control Technologies ,2006.4 郭强,孙强,李雪,等.无线传感器网络LEACH 协议的研究J.通信技术, 2008,41(12:155-157.5 罗玥,李雷.无线传感器网

18、络路由问题探讨J.通信技术,2007,40(12:361-362.6 吴迪,胡钢.无线传感器网络多路径簇头链分簇式路由算法J.计算机工程与科学,2008,30(06:101-105.7 刘志杰,张华忠,于鹏程.WSN 中能耗均衡的自组织多跳聚类协议研究J.计算机工程与应用,2007,43(26:129-131.8 王春雷,柴乔林.基于分簇的无线传感器网络节能路由算法J.计算机应用, 2007,27(02:342-345.(上接第134页服务率图1 平均时延分析服务率图2 丢包率分析3 结语联系理论公式和仿真结果,得出:在缓冲区既定的情况下,要有效地减少平均时延和丢包率,就必须提高服务率的结论。这就为提高多媒体服务的QOS 及改善丢包现象提供了很好的理论依据。对于本课题而言,今后可以在以下方面加强与创新: 在各种新兴的ATM 交换网络的结构以及新兴的业务前提下,