WSN中的基于能量和邻居数的分层路由协议

韩冰 彭太乐 肖建于

摘要：为了完成数据的采集和传输的同时最小化能耗，无线传感器网络需要节能且健壮的通讯协议，国内外学者提出了一些基于能量的簇头选择算法。然而这些所提算法里面均未考虑簇头邻居的能量和数目。该文提出了一个基于能量的簇头选择算法EBC，该算法中簇头是基于节点和节点邻居的能量和节点的邻居数目来选择的。实验表明EBC相比LEACH 提高了无线传感器网络的生命周期。

关键词：EBC;LEACH协议;无线传感器网络;多跳通信;HEED

中图分类号：TP393        文献标识码：A

文章编号：1009-3044（2019）22-0045-03

开放科学（资源服务）标识码（OSID）：

A Hierarchical Routing Protocol based on Energy and Number of Neighbors for WSN

HAN Bing1，PENG Tai-le 2，XIAO jian-yu2

（1. College of  Management， Huaibei Normal University， Huaibei 235000，China; 2. College of  Computer Science，Huaibei Normal University， Huaibei 235000，China）

Abstract： Wireless sensor network requires robust and energy efficient communication protocols to minimize the energy consumption as much as possible. Numerous energy-based cluster head election algorithms have been proposed and implemented. However， the capacities and workloads of the neighbors of cluster heads have not been considered in large wireless sensor networks. A energy-based cluster （EBC） head selection scheme where cluster heads are elected based on the energy value of a node and the energy values of its neighbors and the number of its neighbors is proposed in this paper. Simulations in network simulator have proved that EBC cluster head selection scheme has improved the lifetime of the network compared to the LEACH protocol.

Key words： EBC;LEACH protocol; Wireless sensor network; Multi-hopcommunication; HEED

1 引言

無线传感器网络是由一组传感器节点构成的无线网络，其目的是感知并采集网络覆盖区域中感知对象的信息，并将感知信息发送给监测者。在无线传感器网络的研究中，能效一直是热点问题。为了延长网络生存周期，国内外学者得到了大量的研究。

分簇算法可以有效延长网络生存周期，在分簇算法中，簇头的选择对网络能耗有较大影响[1]。本文对分簇算法的簇头选择进行研究，提出了一种新的簇头选择算法。

2 相关工作

国内外学者在这个领域进行了大量的研究，一些比较优秀的可以有效延长网络生存周期的分簇算法出现。LEACH算法是最早出现的无线传感器网络分簇算法，在LEACH中，每一个簇头节点直接和基站通讯，这样当簇头节点和基站距离较远时它们之间的通讯会消耗簇头节点大量的能量。针对LEACH算法的缺点， Xiangning [2]提出了多跳LEACH（multi-hop LEACH）该协议通过其他簇头节点选择簇头和基站的最佳路径，通过这些簇头节点传输数据。簇头之间是通过多跳通信传输数据的，根据所选的最佳路径，这些簇头把数据传到一个距离基站最近的簇头。Younis and Fahmy [3]提出了HEED算法，HEED算法基于节点度和剩余能量从一组节点选择簇头节点，实验表明HEED相比LEACH进一步延长了无线传感器网络的生命周期。本文提出的算法EBC（energy-based cluster）选举簇头时充分考虑了节点的剩余能量，获得较好的性能。

3 EBC分簇算法

EBC分簇算法包括以下步骤： 数据收集，基于能量和基于节点度的簇头选择。下面分别介绍这两个步骤：

3.1 数据收集

在这个阶段，基站从所有节点获得节点的能量数据，然后我们获得每一个节点的邻居列表，我们考虑邻居列表中每一个节点的能量值以做出有效的簇头选择决定。所有这些节点都必须在簇头候选节点的一跳范围之内，我们考虑节点的能量和邻居数以决定把簇头候选节点变成簇头，还是再选一个簇头候选节点。

3.2 EBC簇头选择过程

簇头是比普通节点拥有更多能量的节点。簇头选择的过程分簇算法的一个核心过程，由于无线传感器网络资源有限，簇头选择不能太复杂，但还必须选出合适的簇头。簇头选择过程的第一步是发现具有最大能量的节点。数据收集过程完成后，我们获得了所有节点的能量，然后我们分析节点的能量已找到具有最大能量的节点。然后我们计算一个参数活跃能量值，该值是一个为了计算一个成为簇头的节点的能量和邻居节点能量的关系而设计的参数。该值是通过AvgE（j）和e（n）计算的。

Ce（n）=W1* AvgE（j）+W2*e（n）                        （1）

为了减少簇内通信的能耗，簇头应尽可能分布于节点密集的区域。在本文假设的网络中，每个簇的最佳覆盖面积 S =[L2p×N]，最佳簇半径 R = [L2p×N][9]。本文将到节点 i的距离小于 R的节点称为 i的邻节点，[ni] 为 i的邻节点数，根据式（2）设置竞争因子 η，即

[ηi] =1 -min[[ni]  ×p，1]              （2）

为了使[ni]  大的节点优先成为簇头，设置延时时间

[ti]=（[ηi] +γ）×[t0]                   （3）

式中[t0]为选定的时间;γ为随机数且 γ∈[0，1]。对于节点 i，若其可以成为簇头，则在簇头选取时首先延时[ti]。[ti]到时若簇头选取仍未结束，则 i成为簇头。节点的Ce（n）值找出来以后，如果该值大于一个阈值thresh，则该节点开始延迟。延时结束时该节点成为簇头，广播建簇信息，信息中包含自身的 ID。其他节点接收建簇信息，估算距离，按式（4）更自身延时时间。一般来说，簇头均匀分布可以减少能耗[9]，本文通过调整[ti] 来促使簇头均匀分布。若一个节点成为簇头，则以事先选定的强度发送建簇信息。其他节点接收该信息，根据接收信号的强度估算到该簇头的距离l。并按式（4）更新延时时间。

[ti=ti+t0 l≤Rti   l>R]                                  （4）

基站接收建簇信息，当收到 P ×N个建簇信息后广播簇头选举结束信息。未成为簇头的节点收到该信息后，根据收到的信号强度，加入最近的簇头，向其发送入簇信息并附上自身 ID。簇头接收入簇信息，向发出请求的节点返回一确认信息，完成簇的建立。节点采集信息，通过时分多址（TDMA）方式送给簇头并附上自身剩余能量信息。簇头进行数据融合后发给基站。基站接收采集的信息数据并收集和各个节点的剩余能量信息。一轮结束后返回步骤一循环执行。

4 仿真结果分析

模拟器使用的是NS2，NS2是一款用来分析网络性能的离散事件驱动的模拟器。在这个仿真中，有一个仿真区域1，420 × 500节点分布在其中，和AODV路由协议。EBC仿真用到的参数如表1所示。

4.1包递交速率

包递交比例（PDR）是一个测试网络性能的服务质量参数，低 PDR降低网络的性能。

图1表明随着仿真时间的增加，EBC算法比LEACH算法显著增加了PDR。

4.2 包丢失率

包丢失率是一个节点可能丢弃的最大数据包数目，如图2所示，EBC 分簇算法的包丢失率比LEACH要小。

4.3 剩余能量

一个节点的剩余能量是一个节点所剩的能量。图3表明 EBC的剩余能量比LEACH高许多。

5  总结

EBC 是一种簇头选择算法，该算法通过节点和节点邻居的能量和节点邻居的数目来选择簇头节点， 仿真表明 EBC scheme相比其他只考虑簇头能量的簇头选择算法提高了网络的生命周期，进一步的工作可以是简化一下EBC的过程。

参考文献：

[1] A.K. Thomas， R. Devanathan.Variable duty-cycle based efficient network discovery in WSN.Eur. J. Sci. Res. 2012， 93（2）： 266–278.

[2] F. Xiangning， S. Yulin.Improvement on LEACH protocol of wireless sensor network， inInternational Conference on Sensor Technologies and Applications （SensorComm '07）， IEEE，October 2007：260–264.

[3] O. Younis， S. Fahmy.HEED： a hybrid， energy-efficient， distributed clustering approach for adhoc sensor networks. IEEE Trans. Mob. Comput.2004， 3（4）：366–379 .

[4] A. Abbasi， M. Younis.A survey on clustering algorithms for wireless sensor networks.Comput. Commun， 2007，2826–2841.

[5] R. Tandon， B. Dey， S. Nandi.Weight based clustering in wireless sensor networks， in Proceedings of the IEEE National Conference on Communications （NCC），2013.

[6] S.H.N. Choi， K.O. Lee， K.W. Rim.A weight-based unequal clustering routing protocol in wireless sensor network， in Proceedings of IEEE International Conference on Information and Communication Technology （ICT4M），2010.

[7] L.H.M. Mercy， K. Balamurugan， M. Vijayaraj.Maximization of lifetime and reducing power consumption in wireless sensor network using protocol. Int. J. Soft Comput. Eng. （IJSCE） ，2013， 29（6）.

[8] D.G. Reina， S.L. Toral， P. Jonhson， F. Barrero.Hybrid flooding scheme for mobile ad hoc networks. IEEE Commun. Lett，2013： 17（3）.

[9] Su J S Guo W Z Yu C L， et al. Fault-tolerance clustering in algorithm with load-balance aware in wireless sensor networks[J]. Chinese Journal of Computers，2014 ，37（2）：445-456.

【通聯编辑：代影】