DOI: 10.3969/j.issn.1673-4785.201301035
,
2. 黄河科技学院 信息工程学院，河南 郑州 450099
,
2. College of Information Engineering, Huanghe Science & Technology College, Zhengzhou 450099, China
ZigBee无线传感器网络[1-6]由一定数量的无线模块组成，这些模块一般随机地分布在被监控的区域，且通常都采用电池供电方式。对于大规模网络来说，一般不对“死亡”节点进行电池更换[3]。在很多实际工程中，ZigBee节点处于侦听状态，能量利用效率很低，因此设计一种能量均衡有效的路由通信机制对延长网络的生存周期和提高网络稳定性是非常必要的。
多层分簇路由算法[7-13]可以在保证网络稳定性基础上，一定程度减少网络节点能耗，延长网络生存周期。诸类算法比较经典的分簇算法有文献[14, 19-20]中提出的LEACH算法，该算法是一种自适应分簇算法，它周期动态地形成簇。HEED[15]算法是对LEACH算法随机生成不均匀簇头的一种优化。SEP[16]算法是对LEACH算法竞选簇头的一种改进，文献[17]中提出的GAF算法是一种基于地理位置的分簇算法。文献[7, 18]采用了固定分区的方法进行区域分簇。
能量均衡多跳分簇路由算法(EBMHC)的基本思想为：虚拟单元格划分为集中式划分，生存簇头阶段为分布式方式，同时采用动态路由方式和轮转的方式实现数据的多跳传输和能量均衡。通过仿真结果表明，EBMHC算法均衡了网络节点能量，且没有影响网络数据传输，延长了网络生存寿命。
1 能量均衡多跳分簇路由算法在簇结构中，簇首不仅要收集簇内节点采集的数据，而且还负责数据融合、转发，路由生成与维护。簇头的这些功能决定了其必须处于高负荷工作状态，这就使得网络能量分布不平衡。
LEACH算法在一定程度上实现了网络能量均衡的目的，但随机簇头生成方式存在簇头分布不均匀的问题。HEED算法是对LEACH算法的改进，其考虑了簇内的通信开销，使得全网能量更均衡，但在生产簇头方式上采取迭代算法，这就加大了成簇的开销。GAF算法的思想是根据地理信息将网络划分为网格，网络节点能量均衡性差。SEP算法在LEACH算法的基础上,对不同剩余能量的节点采用不同的选举概率，但簇头分布不均匀的问题并没有得到改进。
本文提出一种ZigBee无线传感器网络能量均衡多跳分簇路由算法(EBMHC)，EBMHC算法在分簇阶段引入随机轮转θ角，避免某个扇区内节点数量过多，在竞争簇头阶段，引入能量因子，使剩余能量较多的节点优先成为簇头；簇路由阶段，采取数据融合方式，簇头节点将同类数据进行融合处理，从而实现无线传感器网络能耗均衡。
1.1 网络模型假设对ZigBee无线传感器网络模型作出如下假设：
1)ZigBee无线传感器网络中每个节点最初能量相等，且传感器节点具有相同的硬件平台；
2)传感器节点相对于基站的极坐标且放置后位置不变；
3)基站位于中心，不考虑基站的能耗，传感器节点随机放置在圆形区域中。
1.2 算法描述EBMHC算法执行过程分为每个周期3个阶段：分簇阶段、簇头竞争阶段和簇路由阶段。如图 1所示。分簇阶段类似于GAF算法里对虚拟单元格的划分，如图 2所示。
|
| 图 1 EBMHR算法执行过程 Fig. 1 EBMHR algorithm execution process |
|
| 图 2 EBMHR算法分簇示意 Fig. 2 EBMHR algorithm clustering diagram |
EBMHR的分簇思想以基站为中心的圆形区域建立极坐标系，然后进行环形分层，最后将每层的环等分。论文根据以上思想，且考虑算法的复杂度，确定第一层环四等分，第2和第3层环分布8等分，第4、5层环16等分，5层以外每增加2层环，等分数是新增较小环数的4倍。论文中传感器节点随机布置，为了生成的簇头节点功耗相当，划分的每个簇面积应接近。
设r0=0，基站到第一层环距离设为r1，则通过式(1)可计算基站到第n层环的距离rn。
 |
(1) |
由式(1)可得出每层到基站的距离：
 |
(2) |
记每层的距离宽度为Ln，显然L1=r1，则可得出：
 |
首次成簇轮转角设置为θ=0°，区域内每个节点设置的极坐标计算出簇号。记节点i的极坐标为(θi，di)，极坐标中的θi为节点i与x轴正方向的夹角，di为基站与节点i的距离，则节点i的簇号CID可由式(3)计算:
 |
(3) |
记其中式(3)中的“( ］ ”为取整求最大，θ为轮转角，首次不进行轮转，θ=0。节点极坐标(π/3，2r1)通过式(3)计算CID=302，即第三层环第二扇区。倘若CID/100=0，CID=CID+节点扇区。
“外右定则”：扇区的4个边界分别记为扇内边、扇外边、扇左与扇右，扇内外边为弧线，扇左右为直线，扇内边长度小于扇外边，以基站为中心往外，确定扇左与扇右；处于扇边上的节点，位于扇外边与扇右上的节点被划分到本扇区。
每个轮转周期由基站控制，并广播告知网络内节点，轮转角θ在(0，π/8)中随机选取，轮转的目的可以保证每个扇区内节点数量接近且扇内总能量相当。
簇头竞争阶段 通过扇区的划分，通过式(3)每个节点可计算出一个CID，为了避免簇头能量消耗过快而“死亡”且考虑算法复杂度，论文采用竞争方式来选择簇头，以节点剩余能量作为簇头竞争的主要因素，以达到能量均衡的目的。EBMHC算法簇头竞争方法为
1)扇内每个节点设置休眠时间Trand，Trand由式(4)得到:
 |
(4) |
式(4)中Er为节点当前剩余能量，参数t0为参考时间，参数Ec为参考能量，参数Ec大小小于节点截止工作能量。 自动唤醒的节点在等待一个随机的时间间隔内，如果没有接收到扇内簇头的广播帧，则该节点自动转变为候选簇头，执行2)，如果接收到扇内簇头广播帧，则执行4)；
2)候选簇头向扇内广播簇头声明帧，避免扇内节点变成候选簇头，在候选簇头声明期间如果接 收扇内其他候选簇头的声明帧，则两个簇头都比较节点能量，优势节点自动从候选簇头升级为簇头，执行3)，劣势节点降级为普通节点，并执行4)；
3)簇头节点以Tcid为周期向扇内节点广播声明帧，并执行5)；
4)普通节点更新簇头信息及路由，以通过簇头转发数据，并执行1)，休眠期间可通过事件中断进入工作模式；
5)簇头负责扇内数据收集、融合及向基站转发；
6)基站广播轮转帧，以告知网络所有节点进行周期轮转。
图 3是通过Matlab进行仿真的分簇结果图，图中星点为普通节点，圆圈为簇头，基站位于圆心，由五角星表示。
|
| 图 3 EBMHR算法分簇示意 Fig. 3 EBMHR algorithm clustering diagram |
簇路由阶段 簇头负责扇内节点数据融合发送以及簇头之间路由。论文利用文献[1, 3]中提到的AODVjr算法，通过AODVjr算法来完成网络路由的形成与维护，本文不再对AODVjr算法进行详述。
2 仿真及分析 2.1 能量消耗模型ZigBee无线传感器网络采用文献[14-17]中提到的自由空间模型与多径衰减模型，参数k为发送的比特个数，射频发送能耗可由下式得到：
 |
射频接收能耗可由式(5)得到:
 |
(5) |
处理器数据融合能耗由式(6)进行计算: 式中：Eelec表示发端电路运算和处理每个比特能耗；EDA表示融合每个比特数据的能耗；εfs和εmp分别为自由空间模型和多径衰减模型系数；d0为自由空间和多径衰减传播模型的门限距离，d0可由下式计算：
 |
若实际发送距离d<d0时，传输能耗采用自由空间模型；若实际发送距离d≥d0时，传输能耗采用多径衰减模型。
2.2 仿真参数考虑EBMHC算法环数的不同而对仿真结果的影响，论文分别将EBMHC网络划分3环(EBMHC-3)和6环(EBMHC-6)2种，并同SEP、LEACH算法进行性能比较，为了便于比较，EBMHC的参数同LEACH算法和SEP算法参数一致，利用Mtalab在区域面积为104m2的网络中随机生成数量为100的普通节点，生成后节点位置在仿真期间不变。EBMHC的其他Matlab仿真参数如表 1所示。
| 名称 | 数值 |
| 网络面积/ m2 | 104 |
| 节点数/个 | 100 |
| Eelec，Erx，Etx/nJ·bit-1 | 50 |
| 节点初始能量E0/J | 0.5 |
| εfs/ pJ·bit-1·m-2 | 10 |
| EDA/nJ·bit-1 | 5 |
| εmp/pJ·bit-1·m-2 | 0.0013 |
2.3 仿真结果及分析
论文通过网络生成周期与基站接收总数据包数量两个参数进行性能对比，在实际应用中，个别节点的损坏不会对网络产生太大冲击，但网络生成周期也不以网络内最后一个节点能量耗尽为基准，而是以网络内一部分节点死亡以及基站数据的大量减少为准，所以网络能耗均衡很重要，达到真正的延长网络生存周期。本来以网络内首次出现能量耗完节点的轮数为比较依据。
图 4的网络生成周期仿真结果显示，EBMHC-3同SEP、LEACH 2个算法比较，EBMHC-3延长了网络寿命，SEP在第1 042轮首次出现节点能量耗完，LEACH在第957轮首次出现节点能量耗完，而EBMHC-3首次‘死亡’节点出现在第1 244轮，相比SEP算法，网络寿命增加了19.39%，比LEACH寿命增加了29.98%。但EBMHC-6的优势不明显，因为对于100个节点的小网络，环数过多，扇区数量越大能量消耗越快。
|
| 图 4 网络生存周期对比 Fig. 4 Network lifetime contrast |
图 5为基站接收的总数据包数量的比较，EBMHC-3的数量为13 748个，EBMHC-6的数量为14 152个，SEP的数量为13 748个，LEACH的数量为13 620个，EBMHC-3和EBMHC-6的总数据包数量分别比SEP提高了1.58%和2.69%，分别比LEACH提高了2.44%和3.55%。通过基站接收总数据包个数比较，EBMHC网络性能更好。
|
| 图 5 基站收到的数据对比 Fig. 5 Comparison of the data received by the base station |
通过以上仿真结果可知，EBMHC网络对于节点数量不是太多的情况下，划分的环数不易过多；但EBMHC网络环数也不能太少，环数太少必然导致扇区以及簇头太少，最终使得信道拥塞，包接收率(PRR)过低。实际应用中，可以通过调节第一层环宽度r1的来调节网络的环数，以达到网络性能最佳。
3 结束语本文以延长ZigBee无线传感器网络寿命为目的，通过对相关协议的研究，提出了EBMHC算法，EBMHC算法利用网络区域划分虚拟扇区进行成簇，且采用集中成簇和分布式簇头竞争的方式，以节点节点剩余能量为簇头竞争参考因素，有效均衡网络节点能量。最后的仿真结果表明，EBMHC算法与SEP、LEACH两种算法相比，EBMHC算法不仅延长了网络寿命，而且没有影响网络的稳定性。
| [1] | 李文仲, 段朝玉. ZigBee2006无线网络与无线定位实战[M]. 北京: 北京航空航天大学出版社, 2008 : 26 -27. |
| [2] | 毕开春. 国外物联网透视[M]. 北京: 电子工业出版社, 2012 : 10 -19. |
| [3] | 孙利民, 李建中. 无线传感器网络[M]. 北京: 清华大学出版社, 2005 : 89 -108. |
| [4] | AKYILDIZ I F, WEILIAN S, SANKARASUBRAMANIAM Y. A survey on sensor networks[J]. IEEE Communications Magazine , 2002, 40 (8) : 102-114 DOI:10.1109/MCOM.2002.1024422 |
| [5] | NI L M, LIU Y H, ZHU Y M. China’s national research project on wireless sensor networks[J]. IEEE Wireless Communications , 2007, 14 (6) : 78-83 DOI:10.1109/MWC.2007.4407230 |
| [6] | SUNIL J, PRABHAT R. A survey: topology control for wireless sensor networks[C]//Proceedings of IEEE International Conference on Signal Processing Communications and Networking. Chennai, India, 2008: 422-427. |
| [7] | 毕晓伟, 郭文超, 冯文江. WSN中能量有效分簇多跳路由算法[J]. 电路与系统学报 , 2011, 16 (2) : 13-18 BI Xiaowei, GUO Wenchao, FENG Wenjiang. Energy-efficient clustering multi-hop routing algorithm for wireless sensor networks[J]. Journal of Circuits and Systems , 2011, 16 (2) : 13-18 |
| [8] | 任东海, 尚凤军, 王寅. 一种基于时间延迟机制的无线传感器网络分簇算法[J]. 传感技术学报 , 2009, 22 (11) : 1645-1649 REN Donghai, SHANG Fengjun, WANG Yin. A clustering hierarchy arithmetic based on time delay for wireless sensor networks[J]. Journal of Transduction Technology , 2009, 22 (11) : 1645-1649 |
| [9] | 雷磊, 薛小龙, 周进华, 等. 实现节点负载均衡的无线传感器网络能量高效分簇方法[J]. 应用科学学报 , 2010, 28 (3) : 551-560 LEI Lei, XUE Xiaolong, ZHOU Jinhua, et al. Load balancing energy efficient clustering for wireless sensor networks[J]. Journal of Applied Sciences , 2010, 28 (3) : 551-560 |
| [10] | 张荣博, 曹建福. 利用蚁群优化的非均匀分簇无线传感器网络路由算法[J]. 西安交通大学学报 , 2010, 44 (6) : 33-38 ZHANG Rongbo, CAO Jianfu. Uneven clustering routing algorithm for wireless sensor networks based on ant colony optimization[J]. Journal of Xi'an Jiaotong University , 2010, 44 (6) : 33-38 |
| [11] | 郭彬, 李喆. 无线传感器网络中基于剩余能量的联合选举动态成簇路由算法[J]. 电子与信息学报 , 2007, 29 (12) : 3006-3010 GUO Bin, LI Zhe. United voting dynamic cluster routing algorithm based on residual-energy in wireless sensor networks[J]. Journal of Electronics & Information Technology , 2007, 29 (12) : 3006-3010 |
| [12] | 蒋畅江, 石为人. 能量均衡的无线传感器网络非均匀分簇路由协议[J]. 软件学报 , 2012, 23 (5) : 1222-1232 JIANG Changjiang, SHI Weiren. Energy-balanced unequal clustering routing protocol for wireless sensor networks[J]. Journal of Software , 2012, 23 (5) : 1222-1232 DOI:10.3724/SP.J.1001.2012.04061 |
| [13] | 孟中楼, 王殊, 赵峰, 等. 分簇式无线传感器网络睡眠调度机制研究[J]. 微电子学与计算机 , 2009, 26 (7) : 9-16 MENG Zhonglou, WANG Shu, ZHAO Feng, et al. Research on sleeping scheduling in clustered wireless sensor networks[J]. Microelectronics and Computer , 2009, 26 (7) : 9-16 |
| [14] | HEINZELMAN W, CHANDRAKASAN A, BALAKRISHNAN H. An application-specific protocol architecture for wireless micro-sensor networks[J]. IEEE Transactions on Wireless Communications , 2002, 1 (4) : 660-670 DOI:10.1109/TWC.2002.804190 |
| [15] | YOUNIS O, FAHMY S. Distributed clustering in ad-hoc sensor networks: a hybrid energy-efficient approach[C]//Proc 13th Joint Conf on IEEE Computer and Communications Societies. Chicago, USA, 2004: 629-640. |
| [16] | SMARAGDAKIS G, MATTA I, BESTAVROS A. SEP: a stable election protocol for clustered heterogeneous wireless sensor networks[C]//Proc of Int’l Workshop on SANPA. Boston, USA, 2004: 146-173. |
| [17] | XU Y, HEIDEMANN J, ESTRIN D. Geography informed energy conservation for ad-hoc routing[C]//Proc 7th Annual Int’l Conf on Mobile Computing and Networking. Rome, Italy, 2001: 70-84. |
| [18] | XIANG M, SHI W R, JIANG C J, et al. Energy efficient clustering algorithm for maximizing lifetime of wireless sensor networks[J]. AEU-Int'l Journal of Electronic and Communication , 2010, 64 (4) : 289-298 DOI:10.1016/j.aeue.2009.01.004 |
| [19] | WANG A, HEINZELMAN W, CHANDRAKASAN A. Energy-scalable protocols for battery-operated microsensor networks[C]//Proc 1999 IEEE Workshop Signal Processing Systems. Taipei, China, 1999: 483-492. |
| [20] | DENG J, HAN Y, HEINZELMAN W, et al. Balanced-energy sleep scheduling scheme for high-density cluster-based sensor networks[J]. Computer Communications , 2005, 28 (14) : 1631-1642 DOI:10.1016/j.comcom.2005.02.019 |