无线传感器网络中面向动态多跳的非均匀分簇路由
李超良1, 2,胡春华1
(1. 湖南商学院 计算机与电子工程学院,湖南 长沙,410205;
2. 中南大学 信息科学与工程学院,湖南 长沙,410083)
摘要:针对无线传感器网络中因均匀分簇而导致任务重的簇过早耗尽能量、整个网络失效的问题,提出一种自适应的动态多跳非均匀分簇方法,将传感器网络中的簇根据实际需要进行不均匀划分,承担任务较轻的簇划分得较小,而承担任务较重的簇则较大。通过均衡簇能量与其所承担的任务,有效地延长网络的生命周期。然后,将该方法应用于2种典型的路由算法LEACH和HEED。研究结果表明:在采用这种非均匀的分簇算法后,传感器网络的生存时间平均减小5%左右。
关键词:无线传感器网络;非均匀分簇;路由;多跳
中图分类号:TP393 文献标志码:A 文章编号:1672-7207(2011)07-2048-06
A dynamic multi-hop non-uniform clustering routing protocol in wireless sensor networks
LI Chao-liang1, 2, HU Chun-hua1
(1. School of Computer and Electronic Engineering, Hunan University of Commerce, Changsha 410205, China;
2. School of Information science and Engineering, Central South University, Changsha 410083, China)
Abstract: Aimed at the problem that the wireless sensor networks (WSNs) can be disabled easily because the WSNs are clustered evenly and thus the clusters can be out of work easily owing to heavy tasks, a kind of adaptive dynamic multiple hops non-uniform clustering algorithm was put forward, in which those clusters that had heavy tasks contained more nodes, while other clusters contained less nodes. Through balancing the energy of clusters with the tasks, the WSNs’ lifetime was prolonged effectively. The algorithm was applied in two typical routing algorithms LEACH and HEED. The results show that the network's survival time reduces by about 5%.
Key words: wireless sensor networks; un-uniform clustering; routing; multi-hop
随着微型传感器技术、无线通信技术以及嵌入式计算技术的发展,无线传感器网络现已得到越来越广泛的关注[1-2]。无线传感器网络是由大量廉价的微型传感器节点组成的无线自组织网络。每个传感器节点通常由传感单元、计算单元、无线通信单元和存储单元等构成。无线传感器网络可以使人们在任何时间、任何地点和任何环境下获取大量详实、可靠的信息,应用于国防、环境监测、交通管理、医疗卫生、制造业、反恐、抗灾等许多领域。路由是无线传感器网络的关键技术之一,目前,无线传感器网络中的路由协议主要可以分为3类:以数据为中心的路由协议、层次式路由协议、基于位置的路由协议[3]。以数据为中心的路由协议主要包括以下几种:Leach-E[4],Rumor[5],Cadr[6]和Acquire[7]等。层次型路由协议主要包括Dbs[8]。还有一些独立发展的层次路由协议[9-10],如RCR[11],Sop[12],Hmrp[13],Ehrp[14],Lrp[15]和RESEE[16]等。层次式路由协议与单层的路由协议相比具有更好的可扩展性,更易于进行数据之间的融合,从而减少网络中能量的消耗,提高网络的生存周期。基于位置的路由协议主要有M&S[17]和Dgr[18]等。由于有位置信息,根据这些信息计算节点之间的距离,预先估计节点能量的消耗情况,从而构建更加高效的路由协议,有利于网络生命周期的延长。LEACH协议是最早出现的一种分簇路由算法,它的执行过程是周期性地循环进行,每轮循环分为2个阶段,即簇的建立阶段和稳定的数据通信阶段。LEACH通过随机地选择簇头,平均分担中继通信业务,网络生命周期有所延长,但它仍然存在一些缺陷:(1) 节点等概率地担当簇头的这种簇头选择机制,没有充分地考虑节点能量的使用情况及剩余能量,也没有考虑节点的地理位置;(2) 在向汇聚节点的数据传输过程中,所有簇头都是直接向汇聚节点进行发送,这样簇头消耗的能量很大,容易导致网络分割。基于以上这些缺点,Heinzelman等[19]在LEACH协议的基础上加以改进提出了基于汇聚节点控制的协议LEACH-C。通过对分簇方案进行改进,延长网络生命周期。但该方案也存在簇头产生方式开销较大、算法不够健壮等缺点。传感器网络运行中不是所有节点消耗的能量都相同,在每一轮中每个簇的簇头消耗的能量是最多的,若簇头可以根据节点的能量消耗而不是随机地选择进行动态调整形成非均匀的簇,则可以均衡簇之间的能量消耗,延长整个网络的生存时间。李成法等[20]提出了一种非均匀分簇的网络路由协议,靠近汇聚节点的簇较小,而远离汇聚节点的簇则较大。簇头除了发送本簇中的节点收集的数据外,还需为其他的簇头转发信息,采用这种方式,在一定程度上可以延长网络的生存周期。但该文献中每个簇的竞争半径是固定的,而事实上,某些靠近汇聚节点的簇头可能会由于转发过多的簇间信息而耗尽能量,导致网络失效。基于上述考虑,本文作者提出一种多跳模式下的动态非均匀分簇路由协议(Dynamic non-uniform clustering routing protocol, DNCRP)。DNCRP算法在簇内采用单跳方式通信,而在簇间采用多跳通信,由簇头向汇聚节点转发信息。在网络运行过程中,根据网络的能量状况,动态地选举簇头,自适应地根据网络中簇的能量状况改变簇的大小,这样就可以在整个网络中均衡节点能量,而不只是在簇中均衡节点的能量消耗。由于充分利用了整个网络中所有节点的能量,所以,可以大幅度延长传感器网络生命周期。
1 系统模型
1.1 网络结构模型
对网络模型进行较通用的假设:
(1) 传感器网络部署之后,节点都不移动;
(2) 节点同构,初始能量相同;
(3) 汇聚节点位于离传感器网络较远的区域,某些簇中的数据需要靠近汇聚节点的簇头通过多跳才能提交信息;
(4) 传感器节点的发射功率可以进行调节;
(5) 簇头可以根据节点能量动态地进行选取;
(6) 簇的大小可以根据能量状况自适应、动态地调整。
1.2 能量消耗模型
在分析传感器节点的能量消耗时,采用如图1所示的无线传输能量消耗模型(REDM)[21]。
无线传感器网络中的节点经过分簇以后,形成了多个大小不一的簇,簇内的节点与簇头通过单跳方式进行通信,而远离汇聚节点的簇则需要通过多个簇头经过多跳之后才能向汇聚节点传递信息,这样,靠近汇聚节点的簇头就有可能由于转发过多的数据而过早死亡,从而导致整个网络不可用。本文采取一种动态非均匀的分簇方式来克服上述问题:一方面,在簇中选择能量最大的节点充当簇头;另一方面,根据簇头的能量消耗情况动态地调整簇的大小,能量消耗较小的簇头所在的簇较大,而能量消耗较多的簇则较小。实验表明,采用该方法后,网络的生存时间明显延长。
这样的网络具有以下2个主要特征:
(1) 在网络分簇过程中,离汇聚节点较近的簇划分得较小(转发数据较多、任务较重),而远离汇聚节点的簇则可以划分得较大(转发数据较少、任务较轻)。
(2) 随着网络的运行,簇的大小、簇头的选取可以自适应地根据簇头能量的消耗情况实时地调整,以实现整个网络生命周期的最大化。
![](/web/fileinfo/upload/magazine/11744/287204/image002.jpg)
图1 无线传输能量模型
Fig.1 Energy model of wireless transmission
2 DNCRP路由算法
2.1 簇头选取
在网络部署时,由于节点的初始能量是相同的,所以,对于首轮中簇头的选取采用LEACH 协议随机地产生簇头,再根据簇头离汇聚节点的远近产生非均匀的簇,离汇聚节点近的簇划分得较小,而远离汇聚节点的簇则较大。
2.2 簇的形成
每一轮中,当某个节点当选簇头之后,就在本簇内广播一个hello消息,该消息中包含阈值LT,用于确定簇的大小。第1轮的LT固定,设定为LT=6。每个簇中的节点收到该广播消息就保存,然后,将该阈值减小1后传给下其邻居节点,如此循环,直到阈值减少至0为止。若在成簇过程中节点收到多个消息,则只保存第1次的值作为本节点与簇头的距离。
2.3 下一轮簇头的选取
第1轮的簇的大小由LT决定。从第2轮开始,每个簇中的簇头由该簇中能量最高的节点担任,而簇的大小则根据簇头的能量消耗情况自动地进行调整。
簇头的能量消耗EC主要包括处理数据消耗的能量ED和通信消耗的能量EP。而通信消耗能量EP包含节点接收数据消耗的能量ER和传输数据能量ET。
为了准确地描述簇,根据簇头的剩余能量自动调整簇的大小的过程,给出如下簇头剩余能量因子ρ,用于描述节点的能量消耗情况,作为下一轮簇大小调整的依据。
![](/web/fileinfo/upload/magazine/11744/287204/image004.gif)
其中:EOC为节点的初始能量;EC为节点已经消耗的能量。
节点的能量因子ρ包含在交换的消息中。当节点接收其他节点的数据时,将其中的ρ存储下来,并更新ρ表格。在每一轮的簇形成阶段,当选簇头会将本节点的ρ与它的一跳邻居节点的ρ比较,若簇头节点的ρ最小,则说明节点在上一轮网络运行中消耗的能量较小,在下一轮中可以增大簇的范围,即将LT增大;反之,若簇头的ρ最大,则表示在上一轮中簇头消耗的能量较小,减小簇的范围,即LT减小。通过这样的簇头筛选方法以及簇的半径动态调整机制,使得每个簇中簇头的能量是最大的,这样可以确保簇既能收集本簇中其他节点的信息,也能转发其他簇头的信息。网络运行后,有的簇可能比较大,有的簇可能比较小,这是符合网络运行的实际情况的。因为网络运行中节点收集信息量是随机的,并不一定完全均匀,有些热点地区数据可能比较多,相应地消耗的簇头能量也比较多,而有些地区就比较少。为了有效地提高网络的生存时间,网络在转发信息时应该根据簇头节点能量来选择路径,而不仅仅是严格按照簇头离汇聚节点的远近来进行信息转发。在这样的簇头及簇半径的形成机制下,在网络运行的下一轮选举中,转发数据较多的节点周围自然会形成较小的簇,而转发数据较少的簇头周围相应地就会形成一个比较大的簇,半径较小的簇在本轮中会转发较少的信息,而半径较大的簇则会转发较多的信息,于是,簇的大小会随着簇能量的大小而呈现一种“大小相间”变化的趋势,充分利用整个网络中每个节点的能量,从而最大限度地利用节点的剩余能量,延长网络的生命周期。
2.4 算法描述
算法的伪代码如下:
① LT=6;/*设定簇的最大跳数阈值为6*/
② while(LT≠0) /*第1轮分簇*/
{
③ Broadcast(“hello”);/*簇头节点向周围节点广播*/
④ Receive(node_Msg); /*接收信息存储在自己的邻表NT[ ]中,这些节点构成1个簇*/
⑤ if (Nd.LTT) /*如果节点收到的阈值大于自身的阈值*/
{
⑥ Nd.LT=hello.LT; /*将收到的阈值存储为自身的阈值*/
⑦ LT=LT-1; /*将消息的阈值减小1*/
}}
⑧ while(ND. ρ
⑨ LT=LT+1; /*如果簇头p小于其邻居的p,将LT的值增大1,扩大簇的范围*/
⑩ else LT=LT-1;/*否则,不作调整*/
3 仿真及性能分析
对所提出的模型采用OPNET进行仿真实验,具体的实验参数如表1所示。如果节点的剩余能量小于或等于10-4 J,则节点宣布死亡。节点的最大通信半径为100 m,每个数据包长度为100 byte。
表1 实验参数设置表
Table 1 Experimental parameters table
![](/web/fileinfo/upload/magazine/11744/287204/image005.jpg)
将文中提出的动态多跳非均匀分簇机制(DNCRP)应用在LEACH和HEED上,分别比较对固定簇、单跳簇和动态多跳非均匀分簇(DNCRP) 3种方式对LEACH和HEED协议的性能的影响。
single(单跳模式)、fixed(固定模式)、DNCRP(动态非均匀分簇模式) 3种不同机制与LEACH结合后的网络生存时间和节点数的关系如图2所示。
从图2可以看出:多跳模式(固定模式和动态非均匀分簇模式)的网络生存时间多于单挑模式下的网络生存时间,大约多40%。这主要是因为在单跳模式下,簇头的数量较多,每次交互信息时广播次数和应答次数也较多,导致节点能量消耗较多,因此,网络生存时间是最短的。LEACH-fixed模式的生存时间要比LEACH-DNCRP模式下的网络生存时间大约低10%。其主要原因在于后者在选择簇头时每次选择的是簇中能量最大的节点,并且在每轮中簇头会根据能量的多少动态地调整簇的大小。如果能量较多,就扩大簇的半径,反之,就缩小簇的半径,这样就使得能量在整个监测区域内得到均衡,最大限度地利用所有节点的能量,从而使得网络的生命周期得到最大限度地延长。
![](/web/fileinfo/upload/magazine/11744/287204/image006.jpg)
图2 LEACH结合不同机制的生存时间比较
Fig.2 Comparison of survival time in network based on LEACH combining different mechanisms
单跳模式、固定模式、非均衡分簇模式与HEED结合后的网络生存时间和节点数的关系如图3所示。
从图3可以看出:在多跳模式(固定模式和动态非均匀分簇模式)下,网络生存时间都要长于单跳模式,而动态非均匀分簇同HEED结合后,网络的生存时间是最长的。主要原因如下:在单跳模式下,簇头在网络运行时,需要发送和接收数据的次数较多,从而消耗了节点较多的能量,网络的生命周期也缩短很多。而在多跳模式下(包括多跳和动态非均匀分簇),节点的能量能在网络监测区域较大范围内得到均衡,在一定程度上延长了网络的生存周期。
![](/web/fileinfo/upload/magazine/11744/287204/image007.jpg)
图3 HEED在3种模式下生存时间比较
Fig.3 Comparison of survival time in network based on HEED combining three mechanisms
从上述2个实验结果可以看出:动态非均匀分簇机制能够均衡整个网络的能量消耗,延长网络的生存时间。
固定模式(fixed)、动态非均匀分簇模式与2种典型的算法LEACH和HEED相结合后,网络生存时间性能的对比情况如图4所示。
从图4可以看出:动态非均匀分簇模式(DNCRP)与两者结合可以最大程度地延长网络的生存时间;此外,由于HEED本身的性能要优于LEACH的性能;因此,从整体上来说,HEED与2个机制(固定模式和动态非均匀分簇)结合后的性能也要优于LEACH与上述2种模式结合后的网络性能。
![](/web/fileinfo/upload/magazine/11744/287204/image008.jpg)
图4 2种不同模式应用于LEACH和HEED生存时间比较
Fig.4 Survival time of network based on two mechanisms applying in LEACH and HEED
在网络运行过程中,节点剩余能量也能反映系统模式的性能。图5所示为2种状态即固定模式和动态非均匀分簇模式与HEED进行结合后,节点剩余能量的变化情况。
从图5可以看出:随着网络的运行,网络中节点的能量在不断地减少,节点的失效率也在不断地增加,HEED-fixed协议和HEED-DNCRP协议的节点失效率也随着增加;当运行时间达到20 s左右时,HEED-fixed模式的节点失效率将近17%,而HEED-DNCRP模式的节点失效率为14%左右;而当运行时间为60 s时,HEED-fixed模式的节点失效率为40%左右,HEED- DNCRP模式的节点失效率为35%;随着运行时间的延长,采用动态非均匀分簇协议的节点失效率总是比固定模式下的节点失效率要低。可见:动态非均匀分簇协议的节能效果优于固定模式以及单跳模式的节能效果。
![](/web/fileinfo/upload/magazine/11744/287204/image009.jpg)
图5 节点失效比率与运行时间关系
Fig.5 Relationship between node disability rate and run-time
从上述几种典型的路由协议与LEACH和HEED 2种模式相结合后的节能效果以及网络生存时间的比较可以看出:动态非均匀分簇协议具有较好的性能。
4 结论
(1) 采用动态、非均匀的分簇路由方式,提出了一种自适应的DNCRP算法,与传统的一些算法相比,网络的能量消耗大幅度降低,网络的生存时间有较大提高。
(2) 本研究所提出的策略协作能从网络的整体来平衡节点的能量,充分利用了每一个节点的剩余能量。这也是DNCRP协议具有较好的节能效果的直接原因。
(3) 由于算法预置了一些参数如网络监测范围、节点初始能量、簇阈值,这些参数的设置具有一定经验性,如何优化这些配置参数以提高网络性能,一方面需要从理论上进行系统研究,另一方面也需要更精确的模拟测试。这有待于进一步研究。
参考文献:
[1] Yick J, Mukherjee B, Ghosal D. Wireless sensor network survey[J]. Computer Networks, 2008, 52(12): 2292-2330.
[2] 孙利民, 李建中, 陈渝, 等. 无线传感器网络[M]. 北京: 清华大学出版社, 2005: 1-3.
SUN Li-min, LI Jian-zhong, CHEN Yu, et al. Wireless sensor networks[M]. Beijing: Tsinghua University Press, 2005: 1-3.
[3] Keremal A, Mohamed Y. A survey on routing protocols for wireless sensor networks[J]. Ad Hoc Networks, 2005, 3(3): 325-349.
[4] PENG Duo, ZHANG Qiu-yu. An energy efficient cluster- Routing protocol for wireless sensor networks[C]//Proceedings of the International Conference on Computer Design and Applications. Qinhuangdao, China, 2010: 2530-2533.
[5] Bragomsky D, Estrin D. Rumor routing algorithm for sensor networks[C]//Proceedings of the First Workshop on Sensor Networks and Applications (WSNA). Atlanta, United States, 2002: 22-31.
[6] Chu M, Haussecker H, Zhao F. Scalable information-driven sensor querying and routing for ad hoc heterogeneous sensor networks[J]. The International Journal of High Performance Computing Applications, 2002, 16(3): 293-313.
[7] Ssdagopan N. The acquire mechanism for efficient querying in sensor networks[C]//Proceedings of the First International Workshop on Sensor Network Protocol and Applications. Anchorage, USA, 2003: 149-155.
[8] Amini N, Miremadi D, Seyde G, et al. A hierarchical routing protocol for energy load balancing in wireless sensor networks[C]//Proceedings of Canadian Conference on Electrical and Computer Engineering. Vancouver, Canada, 2007: 1086-1089.
[9] Youssef M, Younis M, Arisha K. A constrained shortest-path energy-aware routing algorithm for wireless sensor networks[C]//Proceedings of the IEEE Wireless Communication and Networks Conference. Orlando, USA, 2002: 794-799.
[10] Younis M, Munshi P, Al-Shere E. Architecture for efficient monitoring and management of sensor networks[C]//Proceedings of the IFIP/IEEE Workshop on End-to-End Monitoring Techniques and Services. Belfast, Ireland, 2003: 488-502.
[11] 蔡海滨, 琚小明, 曹奇英. 多级能量异构无线传感器网络的能量预测和可靠聚簇路由协议[J]. 计算机学报, 2009, 32(12): 2393-2402.
CAI Hai-bing, JU Xiao-ming, CAO Qi-ying. Energy prediction and reliable clustering routing protocol for multilevel energy heterogeneous wireless sensor networks[J]. Chinese Journal of Computers, 2009, 32(12): 2393-2402.
[12] Younis M, Youssef M, Arisha K. Energy-aware routing in cluster-based sensor networks[C]//Proceedings of the 10th IEEE International Symposium on Modeling, Analysis Simulation of Computer and Telecommunication Systems. Fort Worth, USA, 2002: 129-136.
[13] WANG Ying-hong, Tsai C H, HUANG Hui-min. A hierarchy-based multi-path routing protocol for wireless sensor networks[J]. International Journal of Information and Management Sciences, 2008, 19(2): 353-366.
[14] Mollanejad A, Khanli L M, Zeynali M. EHRP: Novel energy-aware hierarchical routing protocol in wireless sensor network[C]//Proceedings of the International Congress on Ultra Modern Telecommunications and Control Systems and Workshops. Moscow, Russia, 2010: 970-975.
[15] Huruiala M, Petre C, Urzoca A. Hierarchical routing protocol based on evolutionary algorithms for wireless sensor networks[C]//Proceedings of 9th RoEduNet IEEE International Conference. Sibiu, Romania, 2010: 387-392.
[16] 李戈阳, 曹阳, 冯浩, 等. 基于节点剩余能量调配的无线传感器网络能量均衡路由协议[J]. 中南大学学报: 自然科学版, 2009, 40(6): 1642-1648.
LI Ge-yang, CAO Yang, FENG Hao, et al. Residual energy scheming based energy equilibrium routing protocol for wireless sensor network[J]. Journal of Central South University: Science and Technology, 2009, 40(6): 1642-1648.
[17] Yan Y, Estrin D, Govindan R. Geographical and energy-aware routing: a recursive data dissemination protocol for wireless sensor networks. UCLA Computer Science Department Technical Report[R]. Cos Angeles, USA, UCLA-CSD TR-O1-0023, 2001.
[18] ZHANG Jian, BAI Yan, LI Yu-kai. A state-free directional geographical routing protocol in dynamic wireless sensor networks[C]//Proceedings of the Second International Intelligent Computation Technology and Automation. Changsha, 2009: 430-433.
[19] Heinzelman W. An application-specific protocol architecture for wireless microsensor networks[J]. IEEE Transactions on Wireless Communications, 2002, 1(4): 660-670.
[20] 李成法, 陈贵海, 叶懋, 等. 一种基于非均匀分簇的无线传感器网络路由协议[J]. 计算机学报, 2007, 30(1): 27-36.
LI Cheng-fa, CHEN Gui-hai, YE Mao, et al. An uneven cluster-based routing protocol for wireless sensor networks[J]. Chinese Journal of Computer, 2007, 30(1): 27-36.
[21] Oberg l, XU You-zhi. A complete energy dissipation model for wireless sensor networks[C]//Proceedings of the International Conference on Sensor Technologies and Applications. Valencia, Spain, 2007: 531-540.
(编辑 陈灿华)
收稿日期:2011-03-21;修回日期:2011-05-11
基金项目:湖南省自然科学基金重点项目(11JJ2033);教育部人文社会科学研究青年基金资助项目(10YJC630080);湖南省科技计划项目(2010JT4053)
通信作者:李超良(1972-),男,湖南湘潭人,博士研究生,讲师,从事无线传感器网络、物联网研究;电话:0731-88689238;E-mail:li_chaoliang@163.com