基于能量和距离加权的WSNs簇头选择算法*

王 进， 邵玉斌， 龙 华， 杜庆治

(昆明理工大学 信息工程与自动化学院，云南 昆明 650500)

0 引 言

多年来，无线传感器网络(wireless sensor networks，WSNs)技术得到了长足的发展[1]，利用其自身的优势，广泛应用于环境检测、智能家居、公共交通等领域[2,3]。但由于受到其自身软硬件条件的限制，存储、运算和通信能力较弱[4]，特别是能量有限，不能实时补给，因此,传统的路由协议不适用于无线传感器网络，如何平衡能耗、延长网络寿命就成为了设计无线传感器网络路由协议的重点和难点。

由于分簇路由协议相比于平面路由协议具有更大的优势，近年来已成为研究的热点。文献[5]提出以虚拟化的多输入多输出(MIMO)为基础的用户合作通信方式，在每个簇内选取一个簇头和若干个协作簇头；DAIC[6]协议将整个网络分为若干层，各层中运用模拟退火算法选取簇头并形成相应的簇；文献[7]将节点能量和节点的邻近数目作为簇头选择的参考因素；BCDCP[8]协议均匀分配耗能，传感器节点间利用最小生成树，建立基站到簇头间的多跳路由。但是,以上协议存在未对簇头数目和簇头选取后进一步优化的问题。

本文在LEACH协议的基础上，将节点能量和节点到基站的距离作为参考因素引入阈值公式，目的是为了降低能量较少或离基站较远的节点被选为簇头的可能性，避免一些节点过早死亡；簇头选择时，依据新的阈值公式使每轮选出的簇头数达到预设的最优值，这样可以减少因簇结构不合理所产生的额外能量消耗，从而延长网络的生命周期；针对分簇结束后已有的簇头可能并非该分簇最佳簇头的问题，提出了簇头的二次优化算法，从而最终确定最佳的簇头。

1 基于LEACH协议的改进算法

1.1 LEACH协议的簇头选择算法

在LEACH协议的簇结构建立阶段，每个节点产生一个(0～1)随机数，如果该数小于阈值T(n)，则该节点就被选为当轮的簇头节点。T(n)的表达式如式(1)所示

(1)

其中,r为当前的轮数；p为网络中簇头数与节点总数的比值；G为最近1/p轮中未当选簇头的节点集。

LEACH协议未考虑以下几个方面：1)簇头的数目未优化；2)假定簇头与基站直接通信，距离基站越远的簇头传输能耗越大；3)簇头是随机选出的，因而未考虑簇头的剩余能量，若能量很低的节点被选为簇头，会使得该节点过快死亡，从而影响网络生命周期。本文就是在LEACH的基础上进行改进，优化路由算法。

1.2 簇头选择的改进算法

1.2.1 阈值公式的改进

将当前节点能量和网络中节点平均能量作为参考因素，同时将节点到基站的距离作为因子引入阈值公式，从而提高剩余能量较高或离基站较近的节点被选为簇头的可能性，将网络能量消耗均衡到每个节点上，得到改进后的阈值公式

T(n)=

(2)

式中Ecurr为节点的剩余能量，Eaver为每一轮结束后节点的平均能量，dtoBS为簇头到基站的距离，dmax为所有节点中到基站的最大距离。

1.2.2 簇头的选择

簇头选择前，先计算出该轮的最优簇头数，这是因为LEACH中簇头是随机产生的，每轮的簇头数波动较大，如果事先将每轮的簇头数设为最优值，可以达到合理优化网络拓扑结构的目的，进而减少因结构不合理所产生的能量消耗。最优簇头数公式如下[9]

(3)

式中kopt为最优簇头数；εfs为在自由空间模型下信号的放大倍数；εmp为在多径衰减信道模型下信号的放大倍数；N为整个网络中节点的数量；M为网络中节点所在区域的边长。

使用改进后的阈值公式选取簇头，并将选出的簇头加入到初始簇头集中，如果初始簇头集中的簇头数少于最优簇头数kopt，继续使用改进后的阈值公式选取簇头并加入到初始簇头集中，直到选出的簇头数达到最优值；如果初始簇头集中的簇头数多于最优簇头数kopt，先将初始簇头集中簇头按剩余能量从高往低排序，从初始簇头集中选择前kopt个簇头加入到新的初始簇头集中，选取剩余能量较大的节点当选簇头，这样可以将网络中消耗的能量尽可能的平均分配到每个节点上，从而延长整个网络的生命周期。

1.2.3 簇头的二次优化

当簇头位于簇的几何中心点时，簇内成员节点到簇头的距离平方和最小，又由于节点间的通信能耗主要与节点间的距离有关，因此，当簇头位置越靠近簇的几何中心时，簇内节点间通信时的总能耗也应该越小。分簇结束后，为了进一步减少簇内通信时的总能耗，需要对簇头进行二次优化选择。先将每个簇中剩余能量大于平均能量的节点加入到该簇的候选簇头集中，这样是为了均衡每个节点上的能量消耗，然后基站根据簇中节点的位置信息，计算每个分簇的几何中心位置，最后从候选簇头集中选择距离几何中心位置最近的节点作为该簇新的簇头。

2 仿真与性能分析

本文所用的仿真参数如下：网络监测区域为100 m×100 m，监测区域内随机分布了100个传感器节点，假定基站的位置为(50,175)m，每个节点初始能量相同，均为0.5 J，数据包长度为4 000 bit，距离阈值为87.705 8 m，发送/接收电路能量Eelec为50 nJ/bit，数据融合消耗能量EDA为5 nJ/bit/signal，自由空间放大倍数εfs为10 pJ/bit/m2，多径衰减信号放大倍数εmp为0.001 3 pJ/bit/m2，仿真时忽略无线碰撞和信道干扰的影响。

如图1所示，改进后的LEACH延长了网络生命周期，相比于未改进的LEACH协议，网络的整体生存时间延长了9.4%，同时LEACH协议在第731轮出现第一个死亡节点，改进后的LEACH协议的第一个死亡节点出现在第858轮，说明改进后的LEACH算法稳定性更好。从图2可以看出:改进后的LEACH算法使得网络中的能耗更为均衡。由于将节点能量和节点到基站的距离作为选取簇头的参考因素，这样就避免了能量较低和离基站较远的节点过多的能量消耗，但是，改进后的算法需要考虑节点的能量和位置信息，也会消耗少量的能量。

图1 LEACH和改进后的LEACH存活节点数的对比

图2 LEACH和改进后的LEACH网络总能耗的对比

3 结束语

本文针对LEACH协议存在的问题加以改进，将当前节点能量和网络中节点平均能量作为参考因素，并将节点到基站的距离作为因子引入阈值公式，在选取簇头时，依据改进后的阈值公式使所选取的簇头数达到最优值，减少不必要的簇头能耗，并通过簇头的二次选择，最终确定最佳的簇头。仿真结果表明：改进后的LEACH算法延长了整个网络的生命周期，同时也使网络负载更为均衡。

参考文献:

[1] AKyildiz I F,Su W,Cayirci E.A survey on sensor network[J].IEEE Communication Magazine,2009,40(8):102-114.

[2] Alwan H,Aqarwal A.A survey on fault tolerant routing techniques in wireless sensor networks[C]∥2009 3rd International Conference on Sensor Technologies and Applications,Athens,Greece,2009:366-371.

[3] Jiang C,Yuan D,Zhao Y.Towards clustering algorithms in wireless sensor networks—A survey[C]∥2009 IEEE Wireless Communication and Networking Conference,Budapest,Hungary,2009:1-6.

[4] 孙利民,李建中,陈 渝,等.无线传感器网络[M].北京:清华大学出版社,2005.

[5] Asaduzzaman,Kong Hyung Yun.Energy efficient cooperative LEACH protocol for wireless sensor networks[J].Journal of Communication and Networks,2010,12(4):358-365.

[6] Gautam Navin,Pyun JaeYoung.Distance aware intelligent clustering protocol for wireless sensor networks[J].Journal of Communication and Networks,2010,12(2):122-129.

[7] 胡 刚,谢东梅,吴元忠.无线传感器网络路由协议LEACH的研究与改进[J].传感技术学报,2007,20(6):1391-1396.

[8] Muruganathan S D,Ma D C F,Bhasin P I.A centralized energy-efficient routing protocol for wireless sensor networks[J].IEEE Communications Magazine,2005,43(3):8-13.

[9] Heinzelman W R,Chandrakasan A,Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communications,2002,1(4):660-670.