魏春娟，杨俊杰，张志美

(1.上海电力学院电子与信息工程学院，上海200090;2.沈阳师范大学，物理科学与技术学院，沈阳110034)

无线传感器网络WSN(Wireless Sensor Network)采用分布式处理，通过大量部署在监测区域内的传感器节点，采集网络覆盖区域内感知对象的信息。节点间通过多跳的无线通信方式，将收集、处理后的信息传送到基站进行处理，最终提供给终端用户［1］。由于无线传感器节点大多采用能量有限的电池供电，且节点数目多、分布广、所处环境复杂，通过更换电池来补充能源不易实现，而能量消耗直接决定了传感器网络的使用寿命，因此设计优化网络的整体能耗效率、延长网络寿命的路由协议是无线传感器网络的一项重要研究内容［2－3］。

本文提出了一种分布式能量有效的分簇路由协议DEEC(Distributed Energy-efficient Clustering Routing Protocol)。DEEC采用基于时间的簇首选择算法，广播时间取决于自身剩余能量和其邻居节点的剩余能量。在数据传输阶段，采用簇内单跳与簇间多跳相结合的方式，各簇首根据节点剩余能量、到基站的距离及簇内成员的个数计算权值，然后依据权值大小建立到达基站的路由树。仿真实验结果表明，与LEACH，PEGASIS协议相比，DEEC能够有效地节约单个节点能量、均衡网络能耗、延长网络生存周期。

1 相关工作

分簇路由协议将网络感知的数据进行融合后再进行传输，减少冗余数据传输产生的能量开销及增强网络的可扩展性，近年来已成为WSN中研究的热点。

LEACH (Low-Energy Adaptive Clustering Hierarchy)［4］是MIT 的Wendi B Heinzelman 等人为无线传感器网络设计的低功耗自适应聚类路由算法，它是第一个基于分簇结构的无线传感器网络路由协议。为了将能量负载均匀地分配到各节点上，LEACH协议按轮运行，并在每一轮中通过等概率地随机对簇首进行轮换。当簇生成以后，簇首将聚合其收到的各成员节点的采集信息，并将聚合信息直接单跳传输到基站。由于减少了与基站直接通信的节点数量以及通信量，LEACH协议可以有效地延长网络生命周期。然而，LEACH算法对以下几点没有考虑:①簇首数目的优化，LEACH每轮中任意节点成为簇首的概率为p，因此簇首的数目与节点的数量规模成正比;②所有簇首直接与基站通信，对于远离基站的簇首其能量损耗很快;③由于簇首是随机选取的，因此算法不能保证簇首在网络中的分布，而簇首的分布将决定该轮中传感器网络的能量损耗状况。

Lindsey等人提出的 PEGASIS(Power-Efficient Gathering in Sensor Information Systems)［5］协议，把所有的传感器节点视为一个簇，根据节点的地理位置通过贪婪算法形成一条相邻节点之间距离最短的链，数据在链上经融合处理，最后传输至汇聚点。Younis等人提出一种混合式的分簇协议HEED(a Hybrid Energy-Efficient Distributed Clustering Approach)［6］，算法首先根据节点的剩余能量来概率性地选取一些候选簇头，然后以簇内通信代价的高低来竞争产生最终簇头。与LEACH不同的是，它的簇生成算法需要在簇半径内进行多次消息迭代，由此带来的通信开销比较显著。TEEN［7］算法建立起多级分簇结构，在分簇过程完成之后，通过硬阀值和软阀值两个参数控制数据的发送次数，只有当监测到的数据大于硬阈值，并且与保存的监测值的差大于等于软门限值时才上传数据，通过这样的过程以达到节能的效果。APTEEN［8］算法在TEEN算法的基础上，通过计数器的方式周期性地采集数据并对突发事件做出快速反应。

此外，针对网络中部分簇首节点可能会承担较多的网络流量或者在单位时间内有较多的能耗引起“能量空洞”问题，提出了一些非均匀分簇策略。EECS［9］，EEUC［10］，EADEEG［11］、DEBUC［12］、DEEUC［13］等 协 议通过调节簇半径的大小实现能耗均衡，即在离基站较近的能耗较多的区域形成较小的簇，这样簇首节点有较多的剩余能量用于转发来自其他节点的数据。文献［14－15］分别采用蚁群算法和粒子群算法优化路径搜索。

本文提出一种基于LEACH的分布式能量有效的分簇路由协议DEEC，并从簇首选择、数据传输等方面对LEACH进行改进。在簇首竞争阶段，根据节点剩余能量与邻居节点平均剩余能量的比值计算广播时间;在数据传输阶段，采用簇内单跳与簇间多跳相结合的方式，各簇头在选择中继节点时综合考虑剩余能量、到基站的距离和簇内成员的个数等因素，然后依据权值大小建立到达基站的路由树。仿真结果显示，DEEC协议对LEACH有较大改进，可提高网络能效性能达37.5%。

2 系统模型

2.1 网络模型

考虑一个由N个随机部署的传感器节点形成的网络，其应用场景为周期性的数据收集。假设N个节点随机均匀分布在一个M×M的二维正方形区域A内，并具有如下性质:①传感器网络为高密度静态网络，即节点部署后不再移动。②基站部署在区域A以外的一个固定位置，且基站是唯一的。③所有节点都是同构的，即具有相同的数据处理能力、通信能力和初始能量等，并且地位平等，都能充当簇头节点或普通节点，每个节点都有一个唯一的标识(ID)。④节点不能获知其位置信息。节点获取位置信息需要依靠GPS、有向天线或定位算法等辅助设施或算法，必然增加其成本和能耗开销。⑤节点的无线发射功率可调，即节点可以根据距离远近来调整发射功率的大小。例如，Berkeley Motes节点具有100个发射功率等级。⑥通信链路是对称的，即节点间可以使用相同的传输能量进行通信。若已知对方发射功率，节点可以根据接收信号的强度RSSI计算出发送者到自己的近似距离。

2.2 能耗模型

我们采用与文献［4］相同的无线通信能量消耗模型，节点能耗包括3部分:发送数据能耗、接收数据能耗、数据融合能耗。各个模块的能耗如图1所示。

图1 传感器节点无线通信能耗模型

节点发射比特的数据到距离为d的位置，消耗的能量由发射电路损耗和功率放大损耗两部分组成，即

其中Eelec表示发射电路损耗的能量。若传输距离小于阈值d0，功率放大损耗采用自由空间模型;当传输距离大于等于阈值d0时，采用多径衰减模型。εfs、εmp分别为这两种模型中功率放大所需的能量。节点接收比特的数据消耗的能量为

此外，数据融合也消耗一定的能量，我们假设邻近节点采集的数据具有较高的冗余度，簇首可以将其成员的数据和自身的数据融合成一个长度固定的数据包，然后发送给汇聚点。融合过程中消耗的能量Ec由式(3)决定

式中，EDA表示融合单位数据信号消耗的能量，M为簇内成员的个数。

3 协议描述

由于簇首节点的能耗远大于普通的成员节点，为了均衡节点的能量负载并保持算法的分布性，DEEC按轮运行，每轮分为簇首的选择、簇的形成和数据传输3个阶段。在每一轮初始时重新构造簇，并根据节点剩余能量与邻居节点平均剩余能量的比值选择簇首，然后簇首融合簇内数据并多跳传递到基站。

3.1 簇首选择

DEEC采用分布式簇首竞争算法，簇首的选择以节点及其邻居节点的剩余能量为主要依据。为计算邻居节点的平均能量，每个节点需保存一张邻居节点信息表，以储存其邻居节点的ID及剩余能量。

每轮开始时，采取与LEACH相同的做法，每个节点随机产生介于0与1之间的数，如果这个数小于阈值，则该节点成为候选簇首;否则作为普通节点进入休眠状态直到簇首选举算法结束。对于每个候选簇首节点，首先以半径r广播包括自身ID和剩余能量的E_MSG消息。然后根据所有邻居节点发送来的E_MSG更新其邻居表，并求出其所有邻居节点的平均剩余能量。节点i的所有邻居节点的平均剩余能量为:

其中，m表示节点i的所有邻居节点的数量，Ej为节点j的剩余能量。

这里，k是一个随机均匀分布在［0.9，1］之间的实数值，T则是预先设置的簇首选择算法的最长时间，Ei表示节点i的剩余能量。

在DEEC协议中，若候选簇首节点在时刻t前没有收到任何邻居节点发出的HEAD_MSG消息，则该节点向邻居节点广播HEAD_MSG消息，申明其成功竞选为簇首。如果节点在其t时刻前已经收到了邻居广播的HEAD_MSG消息，则该节点放弃簇首竞争，成为普通节点，并向最近的簇首发送JOIN_MSG消息加入该簇。

根据式(5)，广播时间t取决于节点的剩余能量和其邻居节点的平均剩余能量。如果节点在其所处区域具有较大的能量，则它成为簇首的等待时间较短，概率较大。由于簇首竞争过程中只有少量节点发送一条HEAD_MSG消息，使得DEEC协议的控制消息开销非常小。

3.2 簇的形成

在簇首被选择出来后，采用与LEACH协议相同的簇生成方法，即每个簇首节点广播当选的HEAD_MSG消息到周围节点，其他非簇首节点根据接收到的信号强度选择离自己最近的簇首决定加入这个簇，并通过CSMA的MAC协议发送请求加入簇的JOIN_MSG消息到对应簇首。至此，网络的分簇完成。

3.3 簇的数据传输

DEEC协议采用簇内单跳和簇间多跳数据传输方式。每个簇首需要从邻居簇首中选择一个作为其中继节点，转发数据至基站。本文假设数据的冗余度有限，来自不同簇的数据无法进一步融合，中继簇首节点只是简单转发来自其他簇首的数据。

DEEC协议簇间多跳路由的建立也采用分布式策略。首先，簇首CHi向覆盖半径2r内的节点广播WEIGHT_MSG消息，这条消息包含簇首ID及权值W(CHi)。然后，各簇首将自身的权值与收到的WEIGHT_MSG中包含的权值进行比较:①若该节点权值大于所有邻居节点的权值，则该簇首节点直接发送数据至基站;②若该节点权值较小，则选取权值最大的节点作为父节点(中继节点)，并发送CHILD_MSG通知父节点，这样权值最大的节点将成为树的根节点，如此建立起一棵路由树;③若发生权值相等的情况，则进一步根据ID值大小选择下一跳节点。

接下来，簇首沿着构造好的多跳路由树将收集到的数据转发给父节点，一级一级传递到根节点，最后由根节点将融合后的数据传送到基站，即簇首与基站采用多跳路由方式进行通信。

在计算簇首权值时，综合考虑它的剩余能量、到基站的距离以及簇内成员的个数。簇首CHi的权值计算公式为:

式中:①ECHi为簇首CHi的当前剩余能量，ECH_max为簇首的最大能量。中继节点完成数据转发的任务，需要消耗更多的能量，故能量因素是首先需要考虑的，拥有更多剩余能量的簇首成为中继节点的概率较大。基于降低能耗，减少不必要的计算量的原则(以下选取参数也遵循此原则)，本文取ECH_max等于节点的初始能量。②dCHi_toBS表示簇首CHi到基站的距离，dCH_toBS_max表示簇首到基站的最大距离。距离基站越近的簇首承担的数据转发任务越重，其数据转发能耗越大。为了避免基站附近的簇首过早地耗尽能量而失效，簇首被选为父节点的概率与节点到基站的距离成反比，以增加基站附近父节点的数目。本文取dCH_toBS_max等于坐标原点到基站的距离。③Nnon_CHi表示以簇首CHi构建的簇中包含的成员节点的个数，Nnon_CH_max表示簇内成员个数的最大值。选择簇内成员节点较少的簇首作为中继节点。成员节点较少的簇首在簇内通信中消耗的能量较少，故有较多的能量保留下来用于簇间数据转发。本文取Nnon_CH_max等于网络中节点数N。④α、β、γ表示加权系数，且满足α+β+γ=1。这样，能量足够、距离基站较近且簇内成员较少的簇首将优先成为根节点。

4 性能分析

4.1 实验参数设置

为了验证协议的性能，利用MATLAB在相同条件下仿真 LEACH，PEGASIS和本协议 DEEC，并对比多项性能。仿真实验均基于同一实验场景:在100 m×100 m的区域内随机部署200个节点，Sink节点位于坐标(50，175)，所有节点一旦放置就不再移动。簇首权值计算公式中取 α=0.6，β=0.3，γ=0.1。簇半径r根据文献［15］取最优值，仿真实验的其他参数如见表1。

表1 实验参数

4.2 仿真结果分析

为了全面衡量协议性能，仿真分析了3种网络寿命:第一个节点死亡 first_dead，10%节点死亡teenth_dead，以及全部节点死亡all_dead。表2列出了LEACH，PEGASIS，DEEC协议的3种网络寿命及当时网络节点的平均剩余能量。与LEACH和PEGASIS相比，DEEC协议使得第一个节点死亡对应的网络生存周期分别提高了37.5%和13.5%。

表2 网络生存周期对比

图2显示了网络死亡节点数量随时间变化的情况。从图中可以看出，DEEC相对于 LEACH和PEGASIS明显提高了网络生存周期。由于LEACH以随机的方式选择簇头，簇头分布不均匀，导致一些节点与基站直接通信，节点很快死亡。PEGASIS协议由于要获得所有节点的全局消息，在节点数量较多的情况下控制开销较大，所以性能受到一定的影响。DEEC采用计时广播方式有效减小了簇头竞争阶段的通信能耗，簇间多跳路由更有效地平衡了不同位置簇头节点的能耗。

图2 死亡节点数随时间的变化

图3对比了3种协议的网络节点的平均剩余能量随仿真周期的变化曲线。较小的坡度显示较慢的能量消耗速度和较长的生存时间，DEEC协议的坡度明显小于LEACH和PEGASIS，并且DEEC的网络节点能量均值一直都比LEACH或者PEGASIS的高，表明DEEC协议能够更有效的节约节点能量。同时，从表2中可看出，DEEC中10%节点死亡时，节点平均能量已经很小(0.029 7 J)，而LEACH与PEGASIS此时节点平均能量分别为0.079 8 J和0.045 2 J。说明DEEC能够有效地平衡节点间的能耗。

图3 节点平均剩余能量随时间的变化

5 总结

基于较大规模WSNs应用，本文提出一种分布式能量有效的分簇路由协议DEEC，该协议基于网络局部信息实现簇首选择和簇间多跳路由。在簇首竞争阶段，采用计时广播机制，使得邻居节点平均剩余能量与自身剩余能量比值大的节点等待的时间更短，成为簇首的概率更大。在数据传输阶段，采用簇内单跳与簇间多跳相结合的方式，引入权值函数优化簇头中继节点的选择。仿真结果显示，DEEC协议可以有效地提高传感器网络的生存周期，均衡网络能耗。在下一步工作中，我们将考虑将DEEC协议引入异构传感器网络中，使DEEC协议具有更加广泛的应用场合。

［1］ 任丰原，黄海宁，林闯.无线传感器网络［J］.软件学报，2003，14(7):1282－1291.

［2］ 刘群，白全炜，曾宪华，等.能量感知的WSN节点分类控制路由算法［J］.传感技术学报，2011，24(7):1053－1059.

［3］ 李建奇，曹斌芳，王摇立，等.一种结合LEACH和PEGASIS协议的WSN的路由协议研究［J］.传感技术学报，2012，25(2):263－267.

［4］ Heinzelman W R.An Application-Specific Protocol Architecture for Wireless Microsensor Networks［J］.IEEE Trans on Wireless Communications，2002，1(4):660－670.

［5］ Lindsey S，Raghavendra C S.Pegasis:Power-Efficient Gathering in Sensor Information Systems［C］//Proc of the IEEE Aerospace Conf Montana:IEEE Aerospace and Electronic Systems Society，2002.1125－1130.

［6］ Younis O，Fahmy S.Heed:A Hybrid，Energy-Efficient，Distributed Clustering Approach for Ad-Hoc Sensor Networks［J］.IEEE Trans on Mobile Computing，2004，3(4):660－669.

［7］ Manjeshwar A，Grawal DP.TEEN:A Protocol for Enhanced Efficiency in Wireless Sensor Networks［C］//Proc.of the 15th Parallel and Distributed Processing Symp.San Francisco:IEEE Computer Society，2001.2009－2015.

［8］ Manjeshwar A，Agrawal D P.APTEEN:A Hybrid Protocol for Efficient Routing and Comprehensive Information Retrieval in Wireless Sensor Networks［C］//Proc of the 2nd Int’l Workshop on Parallel and Distributed Computing Issues in Wireless Networks and Mobile Computing.IEEE Computer Society，2002.195－202.

［9］ Ye M，Li C F，Chen G H，et al.EECS:An Energy Efficient Clustering Scheme in Wireless Sensor Networks［C］//Proc of the IEEE Int’l Performance Computing and Communications Cone NewYork:IEEE Press，2005.535－540.

［10］ Chen G H，Li C，Ye M，et al.An Unequal Cluster-Based Routing Protocol in Wireless Sensor Networks［J］.Wireless Networks，2007，15(2):193－207.

［11］刘明，曹建农，陈贵海，等.EADEEG:能量感知的无线传感器网络数据收集协议［J］.软件学报，2007，18(5):1092－1109.

［12］蒋畅江，石为人，唐贤伦，等.能量均衡的无线传感器网络非均匀分簇路由协议［J］.软件学报，2012，23(5):1222－1232.

［13］ 尚凤军，Mehran Abolhasan，Tadeusz Wysocki.无线传感器网络的分布式能量有效非均匀成簇算法［J］.通信学报，2009，30(10):34－43.

［14］张荣博，曹建福.利用蚁群优化的非均匀分簇无线传感器网络路由算法［J］.西安交通大学学报，2010，44(6):33－38.

［15］秦智超，周正，赵小川.利用粒子群优化的WSN环状簇路由协议［J］.北京邮电大学学报，2012，35(5):26－30.