摘要:在路由协议中利用分簇技术可以提高无线传感器网络的可扩展性。针对无线传感器网络(WSN)中分簇算法的不足，提出了基于备份节点策略的EDC(energy.efficient, dual.pathed, clustering)算法，传感器节点在其簇头失效后仍可以通过其备份路径传输数据。通过OMNeT++平台上的仿真实验表明，EDC在网络重建时间、失效节点数量较其他WSN协议有明显的改善。
关键词:
无线传感器网络；簇头节点选择；备份节点；分簇算法；网络生命周期
中图分类号: TP393 文献标志码:A
Clustering algorithm based on backup path in wireless sensor network DING Ding1,2*, LIU Fang.ai1,2, LI Qian.qian1,2, YANG Guang.xu1,2
1.School of Information Science and Engineering, Shandong Normal University, Jinan Shandong 250014, China
;
2.Shandong Provincial Key Laboratory for Novel Distributed Computer Software Technology, Jinan Shandong 250014, ChinaAbstract:
Clustering can be used in the routing algorithm to enhance the scalability in Wireless Sensor Network (WSN). Arming at the defects of traditional clustering algorithm ,a new strategy EDC(energy.efficient, dual.pathed, clustering) is proposed, in which the member node have a optimal backup path. The strategy guarantee that member node can still transmit data through its backup path when its cluster head dying in the WSN.The results of the simulation experiment on the platform OMNeT++ indicate that EDC performs much better than the other protocols of WSN in network reconstruction time and energy consumption.
Clustering can be used in the routing algorithm to enhance the scalability of Wireless Sensor Network (WSN). Concerning the defects of traditional clustering algorithm, a new strategy EDC (Energy.efficient, Dual.path, Clustering) was proposed, in which the member node has an optimal backup path. The strategy guaranteed that member node can still transmit data through its backup path when its cluster head was dying in the WSN. The results of the simulation experiment on the platform OMNeT ++ indicate that EDC performs much better than other protocols of WSN in terms of network reconstruction time and number of failed nodes.
Key words:
Wireless Sensor Network (WSN); cluster.head node selection; backup node; clustering hierarchy algorithm; network lifetime
0引言
无线传感器网络(Wireless Sensor Network, WSN)［1］由部署在监测区域内的大量廉价微型传感器节点组成，通过无线通信方式形成的一个多跳自组织网络系统，其目的是协作地感知、采集和处理网络覆盖区域中感知对象的信息，并发布给观察者。它在环境监测、军事、医疗健康、家庭智能监控和其他商业领域有着广泛的应用前景，因此受到了学术界和工业界越来越广泛的关注［2］。由于节点资源的限制，人们对WSN的研究侧重在提高能量利用率，延长网络生命周期。
文献［3］的研究结果表明，随着网络节点数目的增多，节点实际使用的带宽以1/n的速度减少，n为节点总数。n到达一定规模时，会用尽绝大多数的通信资源。而基于分簇的算法是解决无线传感器网络管理及扩展性问题的一个重要途径。网络拓扑如图1
所示，标记簇头为CH(Cluster.Head)、簇内节点为MN(Member Node)。现有的分簇算法从结构上可以分为以下两类［4-5］。
1)层次分簇算法［6］。按簇将网络划分为多个小区域，不需要维护复杂的路由信息，从而降低通信量，具有较好的扩展性，该类分簇算法多用于异构网络。异构无线传感器网络的稳定选举协议SEP算法［7］是其中典型代表，根据节点初始能量的不同，节点设置不同的簇头选举概率，从而均匀能耗。
2)平面分簇算法［8］。网络中所有节点的地位都是平等
的，无任何管理节点，无须进行任何结构的维护工作。其核心思想是：通过循环选举簇头，将网络的能量负担平均分配到每个传感节点，从而使得网络中的能量消耗尽可能均匀，延长网络的生命周期。LEACH(Low.Energy Adaptive Clustering Hierarchy)［9］与HEED(Hybrid Energy.Efficient Distributed clustering)［10］是这类算法的典型代表。
本文提出的EDC(Energy.efficient, Dual.pathed, Clustering )，通过在分簇阶段分布式收集的信息，基于能量优先算法对每个MN分配一条备份路径，使其在簇头死亡后仍能通过备份路径继续通信，显著减少了网络重建的轮数。并在此基础上优化算法的执行效率，有效地减少了网络重建所需要的时间。
1理论分析
1.1网络模型
假设网络中所有的传感器节点具有相同的初始能量，并且所有节点都是静止的。Sink位于网络区域的中心位置，节点的最大传输距离为r，距离Sink大于r的节点产生的数据通过多跳路由的方式转发Sink。网络被划分为多个相邻的层。到sink跳数相同的节点属于同一层。每一层又可以分为若干簇。
1.2能量模型
假设Sink节点不受能量限制，每个节点都可能被选作簇头。传感器节点的能量消耗主要包含以下四部分：
1)Es,传送本簇节点产生的数据以及转发来自外层的数据所消耗的能量；
2)Er,接收来自外层的数据所消耗的能量；
3)El,空闲侦听的能量消耗；
4)Ec,网络构建过程中接收和发送控制分组所消耗的能量。
本文采用文献［11］的自由空间信道模型，在距离为r的范围传送l位数据所消耗能量为：
l(Eelec+ε・rα)
(1)相应的，接收l位数据所消耗能量为：
lEelec
(2)
系统参数Eelec、ε和α的取值与文献［7］相同，即Eelec=50nJ/bit,ε=10pJ/(bit・m2),α=2。
第4期
丁鼎等：无线传感器网络备份路径分簇算法计算机应用 第32卷
1.3理论分析
假设半径为R的圆形区域内分布着密度为ρ的静态传感器节点，Sink节点位于区域的中心位置，随机选择部分传感器节点负责感应数据，称为源节点。假设源节点占节点总数的比例为μ,每个源节点每隔单位时间产生并发送λ位数据。簇头数占节点总数的比例为δ,根据式(2)，在第i层的簇头节点在单位时间内接收数据时所消耗的能量为Eir：
(4)
由于节点的位置不变，其i值固定。当源节点所占总节点的比例一定且单位时间内产生的数据量恒定时，即μ与λ不变。观察式(3)、(4)可知，随着层内簇头数量的增多，即δ变大时，每个簇头所分担的能量消耗将会减少。换言之，当层内某个簇头失效后，如果不采取任何措施，该层内的其他簇头在单位时间内能量消耗将会增多，随之加快其失效的速度，形成恶性循环。
为解决上述问题，本文提出了EDC算法，为MN提供了备份节点容错。使WSN内的每一个MN除了与其簇头直接通信外，还有一条最优的备份路径。当簇头失效后，MN仍然可以通过其备份节点传输数据，这样避免了CH死亡所造成MN暂时性失效，导致同层内其余CH的Es与Er变大，从而解决消耗能量过快的问题,有效地增加了节点的能量利用率，从而达到了延长网络生命周期的效果。
2EDC算法
2.1EDC算法设计方案
与多数的分簇算法相同，节点的剩余能量是网络重建所参考的因素之一，标记为Eexist。本文引入节点作为CH的能量使用率，即单位时间内的能量消耗，记为η：
η=x・Es+y・Er+(1－x－y)・El
(5)
其中x、y为簇头节点在单位时间内发送数据与接收数据所占的比例。由式(3)、(4)可知，Es、Er为网络内节点在位置不变的情况下，假定自身为簇头时所计算的单位时间内发送、接收数据所消耗的能量。故节点在网络重建的初始化阶段估算出其η值。
节点作为簇头的工作时长即为两者比值：
tCH=Eexist/η
(6)
tCH越大，则节点成为簇头的概率越大。
2.2EDC算法描述
使用标签‘MN’、‘CH’作为标记，以区别每个节点当前的状态。
算法的伪代码描述如下。
第一阶段，网络重建的初始化阶段，每个节点独立执行EDC算法。初始化各个参数并标记自身为‘MN’，计算tCH,最后广播其ID号、tCH、标签‘MN’。
第二阶段，每个节点将其邻居节点发出的广播包汇总，并形成一个邻居集合，记为SMN。若SMN为空，则节点自身成为簇头，将标签从‘MN’置为‘CH’；否则在SMN 里选tCH值最大的节点作为簇头，广播自身ID，簇头ID，标签‘MN’，并以单播包的方式通知其簇头将标签从‘MN’置为‘CH’。若其簇头标签已置为‘CH’，则收到单播包后不做任何改动。这一阶段的末期，所有标签为‘CH’的节点发出广播包，通知其他节点将自己从集合SMN中移除，形成新的集合SCH。第二阶段结束后，每个节点维护着两个集合。SMN是其通信范围内簇内节点的集合； SCH是其通信范围内簇头的集合。集合所维护的每个节点的属性如表1、2所示。
IDtCH标签CH第三阶段，为每个MN选择备份节点。如果节点为MN(簇头不设置备份路径)，且集合SCH的节点数目大于1，则选择tCH值次大的CH作为其备份路径的下一跳。若节点通信范围内簇头只有一个，则将集合SMN中非本簇的MN且tCH最大的节点作为备份。如果SMN中的节点都为本簇MN，取tCH最大值作为其备份节点。在最坏的情况下，节点的唯一邻居是其簇头，即上面三种假设都不成立，节点将自己成为自身的备份。这一阶段最后，节点广播其ID，CH，与备份节点。
EDC算法的备份路径选择结果如图2所示。
图片
图2EDC算法的备份路径选择策略2.3EDC算法执行效率
由于EDC是分布式成簇算法，即算法在每个节点上分布式独立执行。统计可得，该算法的三个阶段总共发出5条广播，1条单播。这将很大程度地减少网络重建所消耗的时间，并在一定程度上节省了因网络重建所耗费的能量。这点在第3章仿真实验中得到证实。
3仿真分析
为了验证本文提出的EDC算法的有效性，仿真实验将分别从网络重构时间、失效节点数量两个方面分别与DED［12］(Distributed, Energy.efficient, and Dual.homed clustering)、HEED算法比较。并使用OMNeT++平台上的Castalia［13-14］仿真器对其进行仿真实验［15］。其中DED算法是Mohammad M.Hasan提出的一种基于随机备份路径策略的分布式成簇算法，其不足之处将在实验中验证。
本实验设计了无线传感器网络的仿真场景，其主要参数如表3所示。
3.1失效节点数量分析
本节主要研究节点失效的数目与网络工作时间的关系，即节点的能量消耗情况。如图3所示，当35000s后，DED与EDC网络内仍然剩余半数以上的有效节点，而HEED协议的网络由于没有备份策略的支持，导致簇头节点失效后，其簇内节点在网络下次重建之前无法正常地传输数据，所造成的其他簇头单位时间内能量消耗增大，从而引起网络内节点能量利用不均衡的问题。网络过快的重建，缩短了整个网络的生命周期。
图片
图3失效节点数量比较曲线当45000s后，DED剩余4个有效节点，远小于EDC的17个。由于DED的路径备份策略是随机地选择节点，并没有考虑到节点的剩余能量。这种随机的选择方式会使网络内节点能量分布不均，致使部分节点死亡速度加快。在网络重建阶段DED繁琐的迭代步骤所带来的额外的节点能量消耗也是节点死亡过快的原因之一。下一节实验将会从网络的重建时间来证明这一论点。
3.2网络重建时间分析分区
图片
图4网络重构时间比较曲线从图4可以看出，DED的网络重构时间一直维持在40个时间单位左右，是EDC的两倍还多。这是由于在网络构建阶段，每个节点执行DED算法总共发出「lb1Pmin�+3条广播［11］，其中Pmin是为了控制迭代次数而设置的一个门限值。在2.3节所提及，EDC在整个网络重建的三个阶段中，总共发送5条广播，相对于DED算法少了一个迭代过程，将会明显地减少发送广播包的数量。这不仅会减少了网络构建的时间，更对降低能量消耗起到了重要的作用。因为两个算法都是在节点上独立执行，随着节点增多，都没有显著地提高或降低其重建时间，说明EDC与DED算法相同，是基于分布式，不依赖于节点密度的分簇算法。
4结语
本文提出的EDC协议，是针对传统的传感器网络成簇算法中，簇头节点死亡后MN暂时性失效的问题，提出一种全新的备份路径解决方案。其核心思想是，在网络重建过程中，通过分簇阶段所收集到的信息，使每个非簇头节点有一条最优备份路径。当其簇头失效后，下次网络重建之前，可以通过该备份路径继续数据传输。此方案不依赖冗余节点支持，且节点无需GPS功能，在一定程度上减少了网络重建的次数，有效地延长了网络的生命周期。
参考文献:
[1]
ESTRIN D, GOVINDAN R, HEIDEMANN J, et al. Next century challenges: Scalable coordinate in sensor network ［C］// Proceedings of the 5th ACM/IEEE International Conference on Mobile Computing and Networking. New York: ACM, 1999: 263-270.
[2]
马祖长,孙怡宁,梅涛,等. 无线传感器网络综述［J］.通信学报,2004, 25,(4):114-124.
[3]
GUPTA P, KUMAR P R. The capacity of wireless networks［J］. IEEE Transactions on Information Theory,2000,46(2):388-404.
[4]
沈波,张世永,钟亦平.无线传感器网络分簇路由协议［J］.软件学报，2006，17(7)：1588-1600.
[5]
刘林峰,金杉.无线传感器网络的拓扑控制算法综述［J］.计算机科学，2008， 35(3):6-12.
[6]
LIU AN.FENG, WU XIAN.YOU, CHEN ZHI.GANG, et al. Research on the energy hole problem based on unequal cluster.radius for wireless sensor networks［J］. Computer Communications, 2010,33（3）:302-321.
[7]
SMARAGDAKIS G, MATTA I, BESTAVROS A. SEP: A stable election protocol for clustered heterogeneous wireless sensor networks [C]// SANPA 2004: Second International Workshop on Sensor and Actor Network Protocols and Applications. Boston: [s.n.], 2004：251-261.
[8]
CHAMAM A, PIERRE S. A distributed energy.efficient clustering protocol for wireless sensor networks［J］. Computers and Electrical Engineering, 2010,36:303-312.
[9]
HEINZELMAN W, CHANDRAKASAN A, BALAKRISHNAN H. Energy.efficient communication protocol for wireless microsensor networks [C]// Proceedings of the 33rd Annual Hawaii International Conference on System Sciences. Maui: IEEE Computer Society, 2000： 3005-3014.
[10]
YOUNIS O, FAHMY S. HEED: A hybrid, energy.efficient, distributed clustering approach for Ad.Hoc sensor networks [J]. IEEE Transactions on Mobile Computing, 2004,3(4):366-379.http://www.cs.purdue.edu/homes/fahmy/papers/tmc04.pdf
[11]
HASAN M M, JUE J P.省略anization for prolonged lifetime in wireless sensor networks［J］. International Journal of Distributed Sensor Networks, 2011，2011: 257156.
[12]
MEEL R, ANAN R. Performance evaluation of cluster.based routing protocols used in heterogeneous wireless sensor ［J］. International Journal of Information Technology and Knowledge Management, 2011, 4(1):227-231.
[13]
Castalia: A simulator for WSN ［EB/OL］ . ［2011-04-10］ . http://castalia.npc.省略.au/.
[14]
PHAM N, PEDIADITAKIS D, BOULIS A. From simulation to real deployments in WSN and back［C］// WoWMoM 2007: IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks. Piscataway: IEEE, 2007: 1-6.
[15]
冯友宏,关可.基于OMNET的无线传感器网络算法的改进［J］.传感技术学报,2010, 23(6):859-862.