基于分区的能耗均衡路由协议*

翟春杰，徐建闽，刘永桂*（.华南理工大学自动化科学与工程学院，广州5064；.华南理工大学土木与交通学院，广州5064）



基于分区的能耗均衡路由协议*

翟春杰1，徐建闽2，刘永桂1*
（1.华南理工大学自动化科学与工程学院，广州510641；2.华南理工大学土木与交通学院，广州510641）

摘要：为了均衡无线传感器网络的节点能耗，增强网络稳定性，设计并实现了一种基于分区的能耗均衡路由协议。该协议设计了一种优化的分区算法，将节点基于分区划分而形成簇，解决了先前协议中簇的个数和分布的随机性问题；在选举簇首时，综合考虑了节点剩余能量、簇内节点能耗均衡、簇内部总能耗三个方面，采用三级簇首选择机制，选择的簇首既能均衡节点能耗，又可以降低簇群总能量消耗；在数据转发时，普通节点选择距离最近的簇首，在不超过通信距离阀值时，簇首可以隔层选择下一跳簇首，有利于缓解无线传感器网络的“热区效应”。仿真结果表明：相比MEET和DREEM-ME路由协议，该协议能更好地均衡节点能耗、增强网络稳定性、改善网络服务质量。

关键词：无线传感器网络；能耗均衡；分区算法；簇首选择机制

无线传感器网络与应用高度相关，单一的路由协议不能满足各种应用需求。针对不同应用的特点，人们研究了众多的路由协议，这些路由协议主要分为两类：平面型路由协议和层次型路由协议。

层次型路由协议将网络划分成许多簇，每个簇会选出一个簇首来执行不同的任务，而簇内其它节点则会成为簇成员，簇成员将感知到的数据传送给簇首，由簇首执行数据汇聚、融合来减少数据的重复性以及所需传送的数据量，最后通过多跳的路由方式传送给基站［1］。

LEACH［2］为最早提出的层次型路由协议，它可以有效降低节点能耗和延长网络寿命，但是由于节点等概率地随机担任簇首，能量较低的节点也有可能成为簇首，造成节点能耗不均，影响网络寿命；数据转发采用簇首到基站的单跳方式，这会导致距离基站远的节点会消耗过多能量。

首先，在簇首选择方面，文献［3-4］为了避免能量较低的节点担任簇首，采用设定固定的最小能量阈值的方法来筛去剩余能量较少的节点，然而采用固定的最小能量阈值缺乏应用灵活性，为了解决这个问题，文献［5］采用了随着网络整体能量下降而动态变化的节点剩余能量阈值。

然后，在数据转发方面，为了解决LEACH中数据以单跳方式传输造成距离基站远的节点消耗过多能量的问题，文献［6-8］在簇首和基站之间的通信采用多跳方式，这样有利于节约簇首能量，延长网络周期。

为了均衡节点能耗、延长网络寿命，在选择簇首时尽量避免剩余能量较低的节点［3-5］，在数据转发时多采用多跳方式［6-8］，但是这仍然无法改变簇分布不均和网络“热区效应”的现象，针对这一问题，文献［9-10］分别提出了MEET和DREEM-ME协议，为了使簇首分布均匀，在簇形成方面，它们将随机分布的节点根据位置进行分区，同一个分区中的节点构成一个簇，选择簇中剩余能量最大的节点作为簇首；在数据转发方面，仍然采用多跳方式，普通节点可选择距离最近的簇首，而不只是所属簇的簇首，同时簇首选择下一层级最近的簇首。所建立的簇，分布比较均匀，节点能耗更加均衡，但是分区不够合理，簇首选择标准单一，“热区效应”尚未有效地缓解。

本文在研究LEACH、MEET、DDR［11］等协议的基础上，提出了基于分区的能耗均衡路由协议。该协议吸取了MEET、DREEM-ME等协议的分区思想，提出了一种更加合理的、可扩展的分区算法，分区更加科学、均匀；在簇首选择方面，综合考虑节点剩余能量、簇内节点能耗均衡、分区总能量消耗三个方面，选择的簇首更加优化；在数据转发方面，普通节点不受所属簇的限制，可选择距离最近的簇首，同时所设计的下一跳簇首选择算法可进一步均衡节点能耗，有效地缓解了“热区效应”。

1　建立簇首竞争簇

根据概率选择簇首，由于簇首的分布随机性很大，簇群的分布不均匀，导致节点能耗不均衡，影响网络的寿命，本协议的关键之一在于将节点基于位置划分，建立若干分布均匀的簇，这里的簇成员只参与竞争簇首，称为簇首竞争簇，每一个竞争簇只能选出一个簇首，这样保证了簇首的分布达到较优的状态，有效地延长了网络的寿命。实现竞争簇的划分，要经过两个步骤，首先对区域分区，然后节点根据自身所处的位置确定所属的分区，也就确定了所属的竞争簇。

1.1区域划分

区域划分的基本思想：根据邻层簇首间以及簇首和竞争簇内普通节点之间的最大距离约束，将一个区域以基站为中心划分成若干个层，再将每个层均匀地划分成若干个分区。如图1所示，将一个区域划分为4层，每层又均匀地划分出6或12个分区，下面说明以基站为中心的各圆半径之间的关系。

设以基站由内而外的圆的半径分别为r1、r2、r3、r4，以基站由内而外的层分别为A层、B层、C层和D层；由于节点通信时，能耗会随着节点间的距离而变化，设d0为节点间通信距离门限值，距离小于d0的节点通信，能耗则符合慢衰落模型，反之，大于或等于d0的节点通信，其能耗则符合快衰落模型[12]。为使节点通信降低能耗，区域划分有三大原则：其一，B层簇首距离基站的最大距离为d0；其二，相邻两层最邻近竞争簇的簇首间的最大距离为d0；其三，每层竞争簇的普通节点与该竞争簇簇首的最大距离小于d0。这样在数据转发时，就保证了普通节点与簇首、簇首与簇首、簇首与基站之间通信的距离均小于d0，通信能耗符合慢衰落模型。

如图2所示，基于以上3个划分原则，在ΔPOQ中，由三角形面积公式可得

图2　参数分析示意图

同时由海伦公式可得

由式（1）和式（2）可得

从而得出了r1，r3，d0，θ之间的关系式

在ΔMON中，同理由三角形面积公式可得

由海伦公式可得

由式（4）和式（5）可得

从而得到了r4，d0，θ之间的关系。

同时由于第一条划分原则可得

综上，基于3个划分原则基础上所得到的区域划分为四层的约束方程为：

1.2建立簇首竞争簇

记S(i，j)为区域中第i层的第j个分区，i∈{A，B，C，D}，j∈{Ⅰ，Ⅱ，…，Ⅻ}，S(i，j).angle为该分区在以基站为圆心的角度区间，S(i，j).dista为该分区相对基站的轴向分布区间，其中

S(i，j).angle=(S(i，j).angle.orig，S(i，j).angle.end]

S(i，j).dista=(S(i，j).dista.orig，S(i，j).dista.end]

这里的S(i，j).angle.orig，S(i，j).angle.end，分别为该分区相对于基站的起始角度和终止角度，S(i，j).dista.orig，S(i，j).dista.end分别为该分区相对于基站轴向的起始距离和终止距离。

如图3所示可以清楚地获悉S(C，Ⅱ).angle.orig，S(C，Ⅱ).angle.end，S(C，Ⅱ).dista.orig，S(C，Ⅱ).dista.end的具体含义。

设有N个节点随机分布在区域内，通过TSTOA[13]定位算法，可以得到每个节点相对于基站的方位，并进一步获取节点相对于基站的角度和距离的信息，记s(k)为第k个节点，s(k).angle和s(k).dista分别为该节点相对于基站的距离和角度，s(k).layer 和s(k).sec为该节点所属的层和在该层的分区，若节点的方位满足

则s(k).layer=i，s(k).sec=j即确定了节点所属的分区，该分区的所有节点就构成了簇首竞争簇，竞争簇形成算法如图4所示。

图3　距离、角度概念的示意图

图4　传感节点划分算法流程图

2　簇首选择

节点随机分布在区域后，根据它们的方位信息就可以确定其所属的分区，这样分区中所有的节点组成一个簇，如何选择簇首以便增强网络的稳定性，提升网络的服务质量是本协议的第2个关键。

2.1能耗模型

节点的能耗集中在节点工作期间，节点休眠时的能耗很小，在建立能耗模型时，主要考虑节点工作能耗，而工作能耗包括接收数据时的接收能耗和发送数据时的发送能耗；考虑发射端与接收端受距离影响的信号衰落，包括自由空间衰落和多径效应，便得到如下发送和接收单位比特的节点能耗表达式［12］

其中Tenergy为节点发送单位比特数据的能耗，Renergy为节点接收单位比特数据的能耗，Eelec为发送电路和接收电路的能耗，d0为收发两端距离的门限值，εfs，εamp为相应衰落的恒定参数。

在数据转发时，普通节点根据距离最近的原则选择加入某个簇首，这样就建立了基于簇首的数据转发簇，若数据转发簇中至少存在一个普通节点，可以建立下面的数据转发能耗模型，这里只是考虑数据转发簇内的能耗模型。

若簇首为区域第j个簇首，其所在的数据转发簇就记为j个数据转发簇，则簇内普通节点s(i)向簇首发送li比特数据的能耗为

簇首接收节点s(i)发来的li比特数据的能耗为

则所有普通节点向簇首发送数据的能耗为

其中Noj为第j个数据转发簇内普通节点的个数。簇首接收数据的能耗为

则该数据转发簇总能耗为

一般情况下，普通节点向簇首发送的数据包相同，设定为l比特，那么簇首便收到Noj×l比特数据，普通节点的发送能耗

簇首的接收能耗

数据转发簇总能耗

2.2簇首选择机制

选择簇首是在簇首竞争簇中进行的，也就是每个分区中所有节点参与竞争该分区的簇首，而分区节点数目固定，由能耗模型可知，普通节点的能耗取决于距离簇首的距离，簇首的能耗不变，竞争簇总能耗取决于普通节点到簇首的距离平方和。

本协议所解决的问题在于，一要选择竞争簇中剩余能量较大的节点作为簇首，二要保证竞争簇中节点能耗均衡，三要保证竞争簇总能耗较小。能耗均衡与竞争簇总能耗较小与竞争簇的拓扑结构有关，当节点随机分布后，其位置一般不会改变，不同的节点担任簇首，就形成了不同的竞争簇的拓扑结构。

若要保证普通节点能耗均衡，就是要把普通节点到簇首的距离的方差限制在一定范围内，而要保证竞争簇总能耗较小就要使普通节点到簇首的距离平方和较小。

在选择簇首时，本文综合考虑簇首的剩余能量，普通节点到簇首距离的方差和普通节点到簇首距离的平方和3个方面，采用下面的3级簇首选择机制：

第1级：保证簇首的剩余能量较高。将竞争簇的节点按照剩余能量降序排列，设该竞争簇的存活节点数目为N1，若1≤N1≤2，则将排在第一的节点设置为簇首；若N1≥3，若取出排名前的节点作为候选簇首，n1∈[2，N1]；

第2级：保证普通节点的能耗均衡。第一级获取的候选簇首，分别假设为簇首，求出每个候选簇首对应的能耗方差，把候选簇首按照方差进行升序排序，若N2=2，则将排在第一的候选簇首设置为簇首，若N2≥3，取出排名前的候选簇首作为待定簇首，n2∈[2，N2]；

第3级：保证竞争簇总能耗较小。分别计算第二级获取的待定簇首为簇首时对应的总能耗，并将待定簇首按照总能耗进行升序排列，取出能耗最小的待定簇首作为该竞争簇的簇首。

所采用的3级簇首选择机制，兼顾了簇首剩余能量、普通节点的能耗均衡、竞争簇总能耗3个方面，但这3个方面的优先程度不同，首先保证簇首剩余能量处于竞争簇的较高水平，其次保证待定簇首所对应的能耗方差较小，最后保证所选簇首对应的最小总能耗较小。

3级簇首选择机制在选择簇首方面十分灵活，它可以通过调整n1和n2的值，合理地分配给簇首剩余能量、簇内节点能耗均衡和竞争簇总能耗相应的权重，从而有利于满足多种应用需求，本文后面的仿真中取n1=n2=2。

3　数据转发

本文提出的路由协议具有可扩展性，这就意味着某一节点可能距离基站很远，直接向基站传输数据会产生很大的能耗，因此本协议采用了3层通信架构，即普通节点到簇首、簇首到簇首和簇首到基站的数据转发［10］。首先，普通节点将感知的数据转发给距离最近的簇首，然后该簇首对接收的数据进行融合后选择下一跳簇首转发，最终数据会到达基站，因此在数据转发时，如何选择下一跳簇首则是本文协议的第3个关键，本文设计了下一跳簇首选择算法，既均衡了节点能耗，又减少了网络总能耗。

由于节点的随机分布，网络数据转发时会出现热区效应，即内层节点能量消耗要比外层节点要快，之所以出现这种现象，原因在于内层簇首不仅要处理簇内节点的数据，还要接收、融合、转发外层簇首转发来的数据。本文提出的下一跳簇首选择算法，一方面，为了缓解“热区效应”隔层选择簇首，确保内层节点的能耗速度不要过快，另一方面，在隔层选择下一跳簇首上加入d0条件约束，确保隔层节点的数据转发能耗符合慢衰落能耗模型，减少了能量消耗。

下一跳簇首选择算法

if S（i）. Energy>0 & S（i）.IsHeader==0//存活着的普通节点

S（i）. NextHop=min{dis.CHAI，...，dis.CHAVI，dis.CHBI，dis.CHBII，...，dis.CHBXII，...，dis.CHDXII}

//选择距离最近的簇首作为数据转发的下一跳节点

else if S（i）. IsHeader==1//簇首节点

if S（i）. Layer==D//该簇首节点位于D层

if min{dis.CHBI，dis.CHBII，...，dis.CHBXII}

//该簇首节点距B层簇首节点的最小距离小于等于d0

S

（i）. NextHop=min{dis.CHBI，dis.CHBII，...，dis.CHBXII}

//选择距离该簇首最近的B层簇首作为数据转发的下点

else

S（i）. NextHop=min{dis.CHCI，dis.CHCII，...，dis.CHCXII}

//选择距离该簇首最近C层簇首作为数据转发的下一跳节点

if S（i）. NextHop==0//C层传感节点全部死亡

S（i）. NextHop=min{dis.CHBI，dis.CHBII，...，dis.CHBXII}

//选择距离该簇首最近B层簇首作为数据转发的下一跳节点

endif

if S（i）. NextHop==0//B层传感节点全部死亡

S（i）. NextHop=min{dis.CHAI，dis.CHAII，...，dis.CHAVI}

//选择距离该簇首最近B层簇首作为数据转发的下一跳节点

endif

if S（i）. NextHop==0//A层传感节点全部死亡

S

（i）. NextHop=BS//传输数据直接送基站

endif

endif

endif

if S（i）. Layer==C

if min{dis.CHAI，dis.CHAII，...，dis.CHAVI}

S（i）. NextHop=min{dis.CHAI，dis.CHAII，...，dis.CHAVI}

else

S（i）. NextHop=min{dis.CHBI，dis.CHBII，...，dis.CHBXII}

if S（i）. NextHop==0

S（i）. NextHop=min{dis.CHAI，dis.CHAII，...，dis.CHAVI}

endif

if S（i）. NextHop==0

S（i）. NextHop=BS

endif

endif

endif

if S（i）. Layer==A|| S（i）. Layer==B

S（i）. NextHop=BS

endif

endif

endif

4　算法仿真分析

本文采用MATLAB对MEET、DREEM-ME和本文协议进行仿真，在节点存活数目、簇首数据包接收数量、网络剩余总能量三个方面进行比较，以此检验本文协议的性能。在仿真时，与MEET和DREEM-ME协议最初均匀分布节点不同，为更加贴近实际，本文在三种协议的仿真中，均使用相同随机分布的节点，同时扩大了最初MEET和DREEMME协议的仿真规模。

4.1仿真参数设置

仿真是在相同的随机节点分布、相同的数据包大小、相同的能耗模型等的基础上，分别采用MEET、DREEM-ME和本文协议，创造路由协议仿真的唯一差异性，从而使仿真结果具有很强的说服力，具体仿真参数设置如表1所示。

表1　协议仿真相关参数设置

4.2仿真结果

4.2.1网络存活节点数量

稳定期是以网络第一个节点死亡的时间计算，如图5所示，本文协议的第一个死亡节点是在第425个周期，而MEET和DREEM-ME协议第一个死亡节点则分别在第4个和第10个周期。显而易见，在保持网络的稳定性上，本文协议要远比MEET 和DREEM-ME协议优越。

就所有节点死亡的时间看，MEET和DREEMME协议相同，比本文协议要长。在第1600个周期时，三种协议的存活节点数量相近，约有30个，约占总节点的6%，并且主要分布在基站附近，覆盖面积极小，从某种程度上可以说，网络有效寿命已尽，这说明了同MEET和DREEM-ME协议相比，本文协议基本上不改变网络有效生存期。

图5　网络存活节点数量对比

4.2.2簇头接收的数据包

如图6所示，MEET和DREEM-ME协议分别在1096个周期、1105个周期后就只剩下直接与基站进行通信的节点，而本文协议在1871个周期后才只剩下直接与基站通信的节点，这都说明了在整个网络的有效生存期内，本文协议簇头接收的数据包数量要远大于MEET和DREEM-ME协议，通常簇头接收的数据包越多，越表明网络的有效监测覆盖率就越大，网络的服务水平就越高。

图6　簇头接收的数据包对比

4.2.3网络剩余能量

如图7所示，在整个网络有效生命期间内，本文协议的网络剩余能量要大于MEET和DREEMME协议，说明了本文协议在节省网络总能耗方面要优于MEET和DREEM-ME协议，这对于提高网络的服务质量很有帮助。

图7　网络剩余能量对比

5　结论

为了能够使网络节点能耗均衡，增强网络稳定性，提高网络服务水平，本文提出了更加优化的分区算法、三级簇首选择机制和下一跳簇首选择算法。其中，分区算法解决了网络中簇首分布随机性的问题，使得簇首均匀分布在整个区域范围内；三级簇首选择机制，综合考虑了节点剩余能量、簇内节点能耗均衡、簇内部总消耗三个方面，选出的簇首既有利于均衡网络节点的能耗，同时在一定程度上可以减小总的网络能耗；下一跳簇首选择算法，则用来解决距离基站较远的节点通过多跳的方式向基站传输数据，缓解了网络的热区效应。

对本文的路由协议进行了MATLAB仿真，评价其相关指标，并将其与MEET和DREEM-ME协议进行对比，仿真结果表明，在网络存活节点、簇头接收的数据包数量和网络剩余能量等方面，基于分区的能耗均衡路由协议要明显优于MEET和DREEM-ME协议。

参考文献：

［1］许韵.无线传感器网络中层次型链式路由协议的研究［D］.安徽：安徽大学，2011.

［2］Heinzelman W R，Chandrakasan A，Balakrishnan H. Energy-Effi⁃cient Communication Protocol for Wireless Microsensor Networks ［C］//Proceedings of the 33rd Hawaii International Conference on System Sciences，2000. IEEE，2000：10.

［3］曹建玲，刘文朋，彭双，等.一种基于能耗均衡的ZigBee网络高效混合路由算法［J］.电讯技术，2013，53（10）：1352-1356.

［4］董亮，张灵，陈云华.基于限制广播的ZigBee分布式动态能量均衡协议［J］.传感技术学报，2014，27（8）：1120-1124.

［5］何杏宇，周亦敏，杨桂松，等.无线传感器网络能量感知增强树型路由协议研究［J］.传感技术学报，2015，28（4）：551-556.

［6］刘庆，王培康.无线传感器网络的安全分簇路由协议［J］.计算机仿真，2009，26（4）：167-171.

［7］张文祥，马银花，郭继坤.无线传感器网络路由算法的研究［J］.计算机测量与控制，2009，17（3）：617-619.

［8］童梦军，关华丞.基于蚁群算法的能量均衡多路径路由算法的研究［J］.传感技术学报，2013，26（3）：425-434.

［9］Saleem F，Javaid N，Moeen Y，et al. MEET：Multi-Hop Energy Ef⁃ficient Protocol for Energy Hole Avoidance using Variable Trans⁃mission Range in Wireless Sensor Networks［C］//9th International Conference on Broadband and Wireless Computing，Communica⁃tion and Applications. IEEE. 2014：478-484.

［10］Amjad N，Javaid N，Haider A，et al. DREEM-ME：Distributed Re⁃gional Energy Efficient Multi-Hop Routing Protocol based on Max⁃imum Energy in WSN［C］//8th International Conference on Broad⁃band and Wireless Computing，Communication and Applications. IEEE. 2013：43-48.

［11］Ahmad A，Latif K，Javaid N，et al. Density Controlled Divide-and-Rule Scheme for Energy Efficient Routing in wireless sensor net⁃works［C］// 26th IEEE Canadian Conference Of Electrical And Computer Engineering（CCECE）. IEEE. 2013：1-4.

［12］唐毅，梁晓曦，武俊.无线传感器网络最优簇首节点数量研究［J］.通信技术，2007（6）：30-32.

［13］卢翔，涂时亮，陈章龙.对无线传感器网络定位算法的比较和分析［J］.计算机应用与软件，2009，26（12）：199-201，285.

翟春杰（1989-），男，安徽亳州，硕士研究生，主要研究领域为智能控制理论与应用，auchunjiezhai@mail.scut.edu.cn；

刘永桂（1978-），男，湖南邵阳，博士，副教授，主要研究领域为无线传感器网络，auygliu@scut.edu.cn。

徐建闽（1960-），男，山东招远，博士，教授，博士生导师，主要研究领域为智能控制理论与应用、交通信息工程及控制、智能交通系统等，aujmxu@scut.edu.cn；

Minimum Transmit Power Based Distributed Relay Selection in Wireless Networks*

WU Hang1，QIAN Liping1*，CHEN Qingzhang1，LU Weidang2
（1.College of Computer Science and Technology，Zhejiang University of Technology，Hangzhou 310023，China；2.College of Information Engineering，Zhejiang University of Technology，Hangzhou 310023，China）

Abstract：Relay cooperation has been proposed as a promising solution to improve the energy efficiency and service quality of edge users. In this regard，this work proposes a distributed auction-based relay selection algorithm to mini⁃mize the total transmit power consumption for dual-hop decode-and-forward relay networks over Rayleigh fading channels. In particular，we first provide the optimal power consumption of any cooperative transmission in the closed-form expression. Then，we design a distributed relay selection algorithm that assigns every user to the appro⁃priate relay node based on the idea of auction. Simulation results show that every user node can find its best coopera⁃tive relay through limited message passing with relay nodes.

Key words：wireless network；relay selection；auction algorithm；multi-user multi-relay

doi：EEACC：6150P10.3969/j.issn.1004-1699.2016.01.016

收稿日期：2015-08-13修改日期：2015-10-12

中图分类号：TN92

文献标识码：A

文章编号：1004-1699（2016）01-0080-08

项目来源：国家自然科学基金项目（61573153）；广州市科技计划项目（201510010132）