张 品，姜亚光，陈 磊

(杭州电子科技大学通信工程学院，杭州310018)

无线传感器网络(WSN)被各国军事部门、业界和学术界认为是21世纪最重要的技术之一，该领域的研究工作得到了极大的关注[1－2]。WSN是一种能在事先没有构建网络基础设施的环境下，由传感器节点临时组成的一种自组织、自管理的网络[3]。WSN节点通常使用容量有限、不可更换的电池，因此节约网络的能量，最大限度地延长网络生存时间成为衡量WSN的路由协议是否优越的重要标准之一。分簇路由协议在节能方面相比平面协议有着较大的优势，因此得到了广泛的研究。其中典型的代表为自适应聚类算法(Low Energy Adaptive Clustering Hierarchy，LEACH[4])，它的成簇思想对后来提出的很多重要分簇路由算法影响深远;文献[5]提出的算法首先根据节点的剩余能量来概率性地选取一些备选簇头，然后以簇内通信代价的高低来竞争产生最终的簇头;文献[6]中提出的GSEN路由算法，其主要思想是簇内节点和簇头节点都利用贪婪算法组成链，数据经过处理后沿着链传输信息，有效提高了网络的生存时间。本文以LEACH与GSEN算法为基础提出了一种新型的路由算法TL-WCA(Two Levels-Weighted Clustering Algorithm)，该算法首选通过LEACH的算法将网络分成若干个簇，簇头选择考虑节点的剩余能量、度及离簇的质心的距离。簇头选出后以最短路径为原则，采用贪婪算法将簇头形成一条链。然后以簇头的能量不小于簇头间的平均能量及离基站的距离最近为原则，在链中选出一个簇头节点为高级簇头，融合其它簇头的数据后转发给基站。该算法不仅做到了簇内节点的能量均衡同时也兼顾了簇头之间的能量均衡，有效延长了网络的稳定期。

1 LEACH与GSEN算法概述

1．1 LEACH路由算法

LEACH协议是MIT学者A．Chandrakasan等人为无线传感器网络设计的低功耗自适应聚类路由协议。该协议的特征主要有:动态的选举簇头、本地协调以产生簇群。LEACH定义了“轮”(Round)的概念，每一轮存在初始化阶段和稳定阶段两个状态。

初始化阶段是簇头的形成阶段。每个节点决定在当前“轮”中是否成为簇头，成为簇头的概率是一个建议的固定值，需要根据网络中节点的数目而定。在初始化阶段，每一个节点从0～1中选取一个随机数，如果这个随机数小于这一“轮”所设定的门限值T(n)，那么这个节点就成为簇头。随机性确保簇头与网关节点之间数据传输的高能耗成本均匀地分摊到所有传感器节点上。T(n)的计算公式如下所示:

式中:p是节点成为一个簇头的期望百分比;r为当前的轮数;G为在最后的1/p轮中还没有成为簇头的节点集。在第0“轮”中，即r=0时，每一个节点都有概率为p的可能性成为簇头。在第0“轮”中成为簇头的节点，再接下来的1/p轮中不会再成为簇头，在经过1/p－1轮后，T值变为1，这时还没有成为簇头的节点就被选择为簇头节点;再经过1/p轮后，所有节点再次开始平等地竞争是否当选簇头。成为簇头的节点再向网络广播分簇信息，告知其他节点产生了一个新的簇头。其他节点接收到消息后，根据信号强度来选择它要加入的簇，并通知相应的簇头。

与平面路由算法相比，LEACH算法可以将网络生命周期延长30%，但是在簇头选择算法、簇类形成以及最优簇数的确定方面仍存在着不足。首先，成簇策略和簇头选择中未考虑节点的剩余能量。如果选择了剩余能量不足的节点作为簇头，将会加快该节点能量消耗，不能有效提高网络的生命周期;再次，静态地确定最优簇头数以及簇头所占总节点数的百分比。节点根据固定的最优簇头K来估算成为簇头的概率，在整个网络运行阶段，K值不再改变。由于网络中节点数随网络运行而减少，K值也将变小，若采用固定的K值，必将严重影响网络生命周期和稳定性;最后，在传输阶段，采用单跳方式与基站通信，远距离簇头能量消耗过快，尤其不适合大型网络或基站相对较远的情况。

1．2 GSEN路由算法

在PEGASIS和LEACH协议的基础上，Nahida等人结合了两种协议的优点提出了基于簇的传感器路由网络(Group-based Sensor Network，GSEN)路由方案，在成簇阶段，利用LEACH协议将网络中的节点组成几个簇，簇内节点根据贪婪算法组成链，链中的节点通过数据融合沿着链传输信息到簇头，簇头间又形成高一级的链，该链又选出一个簇头，将整个网络的数据融合后转发给基站。与LEACH不同的是，GSEN每5轮重新组成簇和链，而每轮都随机选出一个簇头担当链头，因此该算法没有考虑节点的剩余能量、节点位置、邻居节点、链头能量消耗过快等因素。

2 基于权值优化的两级簇头选择协议

该协议的基本思想基于多权值优化选取簇头，两级簇头融合网络数据。在簇的建立阶段采用两个步骤，首选通过LEACH的算法将网络分成若干个簇，簇头选择考虑节点的剩余能量、度及离簇的质心的距离。然后以距离最近为原则采用贪婪算法将簇头组成一条链，以簇头的能量不小于簇头间的平均能量及离基站的距离最近为原则，在链中选出一个簇头节点为高级簇头，链上的每个节点发送信息给最近的节点，且每个节点将数据融合后，通过hop-by-hop的方式发送给高级簇头节点，该节点将信息融合后发送给基站，其中初级簇头每五轮重新选择一次簇头。由于高级簇头节点耗能更大每一轮都要重新选择簇头。该算法不仅做到了簇内节点的能量均衡同时也兼顾了簇头之间的能量均衡，有效延长了网络的稳定期。

2．1 算法设计过程

2．1．1 初级簇头的选择

分簇路由协议中，簇头的选择将至关重要，一种好的簇头选举方法将有效平衡WSN负载，延长网络的生存周期。TL-WCA在初级簇头选择过程中，每个节点都要产生一个0到1之间的随机数，与相应的阈值T(n)进行比较，若该随机数小于阈值T(n)，则当选为簇头，反之则为非簇头节点。接下来在已经划分好的簇中重新选择簇头。簇头的选择以节点的剩余能量E，节点离质心的距离D和节点的度偏差Δ作为计算权值的参数。根据不同的应用环境，选取适当的加权系数ωj，在节点能量不小于簇内平均节点能量的前提下计算出每个节点的最终权值，为节点成为簇头的依据。给出的权值计算方法如下:

其中，Ei=(S(i)·EO－S(i)·E)/S(i)·EO，表示节点消耗的能量与初始能量的比值，S(i)·EO为节点的初始能量，S(i)·E对应节点的剩余能量。Di=S(i)·d/D·max，表示节点到簇内质心的距离 S(i)·d与簇内节点到质心的最大距离 D·max的比值。Dav(xav，yav)为簇内质心的坐标，表示节点度的偏差，其中Δ0为节点的度(邻居数)，在计算时取邻居中非簇头的节点数，δ为预设的簇规模，可以根据环境作出调整。Eg为是节点能量大于Eav的节点集合，加权系数ωj要求满足，即必须是归一化的，ωj可根据环境调整。当然节点的参数包括很多例如数据传输的差错率，本文没有提到的参数默认为0，即忽略这个参数。通过计算比较Wi选出簇头。

2．1．2 高级簇头的选择

LEACH中每个簇头汇集簇内节点的信息并进行融合后发送到远程基站，而新的TL-WCA协议中通过改进簇头信息的传输方式来节省能耗。如图1所示，TL-WCA算法以最短路径原则采用贪婪算法将簇头形成一条链，成链后以簇头的能量不小于簇头间的平均能量及离基站的距离最近为原则，选出一个簇头节点为高级簇头，每个簇头节点发送信息给最近的簇头节点，且每个簇头节点将数据融合后，通过hop-byhop的方式发送给高级簇头节点，该节点将信息融合后发送给基站(Sink节点)。当过高级簇头的节点不再当选高级簇头，均衡了簇头间的能量。

图1 簇头路由示意图

2．2 无线网络模型和能量公式

对WSN网络模型假设如下:节点始终有数据发送，相邻节点信息高度相关;基站固定，且有无限能量供应。节点能量有限，具有功率控制和定位功能，所有节点都不移动。在LEACH路由算法中，使用的能量消耗公式是一阶无线电模式[7]，如图2所示。

图2 无线通信模型

根据图2这种模式，传感器节点发送k bit数据所消耗的能量为:

传感器节点接收k bit数据所消耗的能量为:

其中Efs、Emp是信号放大器的放大倍数，d是发送节点和接收节点之间的距离，定义 d为β是由无线电通道决定的常量，在发送距离较近时，适用自由空间信道模型，取β=2;而当发送距离较远时，适用多径衰落信道模型，取β=4，也称之为双路径模型。当传输距离大于d0时数据传输的消耗相当大。

3 仿真结果分析

实验采用MATLAB7．0进行仿真，模拟实现了LEACH，GSEN，LEACH-C及其新的 TL-WCA协议，并进行了性能比较。仿真场景如下:100个节点随机分布在100 m×100 m的区域中，基站位于(50，175)。节点初始能量为0．5 J，当能量低于0时，视为死亡，假设转发过程中无数据丢失，数据融合率为100%。ω1，ω2，ω3的值分别是 0．5，0．3，0．2。根据文献[8]，最优簇头数K值的计算公式为，N为网络中节点总数;M为正方形区域边长;Efs为自由空间放大倍数;Emp为多径衰减信道信号放大倍数;d2为簇头距基站的距离。结合本文所提出的网络应用环境推算出K的取值范围，然后在仿真软件中进行能耗分析，找出使网络能耗最小的K值，即为最优簇头数。进而根据网络中的节点总数得出簇头在所有节点中所占的百分比p，采用该方法并结合本文的实际网络环境确定p为0．05。其它仿真环境参数如表1所示。

表1 仿真环境参数

图3给出了 TL-WCA与 LEACH、GSEN、LEACH-C路由协议的网络生存周期比较，以仿真轮数代表网络运行时间，观察它与剩余存活的节点数的关系 LEACH，GSEN，LEACH-C，TL-WCA 协议的第一个节点死亡时间(FND)分别为 712，1040，1175，1678;LEACH，GSEN，LEACH-C，TL-WCA 协议的半数节点死亡时间(HND)分别为901，1116，1631，1909;LEACH，GSEN，LEACH-C，TL-WCA 协议的最后一个节点死亡时间(LND)分别为1235，1222，2023，2107。可以看到 TL-WCA协议无论是FND、HND还是 LND都比其它三种协议长。TLWCA的首节点死亡时间比LEACH调高了135%，比GSEN调高了61%，比LEACH-C提高了43%;半数节点死亡时间比LEACH调高了111%，比GSEN提高了71%，比LEACH-C提高了17%;最后节点死亡时间比 LEACH提高了71%，比 GSEN提高了72%比LEACH-C提高了4%。可见，新算法由于在选举初级簇头时充分考虑到了簇头的多个权值，高级簇头又考虑到节点的剩余能量及位置，从而使网络分簇、数据传输更加合理，这样节点在通信时有效节省了能量，进而延长网络的生命周期。为便于对比，消除一些偶然性，现对算法仿真10次，分别取统计平均值，表2给出了TL-WCA与GSEN，LEACH-C算法统计结果。

图3 网络生存周期比较

表2 节点死亡时间比较

在WSN中，稳定期[9]一般指的是从仿真开始到第一个节点死亡的时间为止，稳定期越长，该网络的性能越好，因为一旦出现节点死亡，网络就变的不稳定，数据传输也就出现不可靠。不稳定期是指从出现第一个节点死亡的时间到最后一个节点死亡的时间为止，不稳定期的长短表明了网络的收敛性，不稳定期越长，收敛性越差，反之越好。在无线传感器网络中要求算法具有快速的收敛性。GSEN，LEACH-C，TL-WCA的稳定期分别为1 023轮，1 157轮，1 655轮，不稳定期分别为207轮，875轮，445轮。可以看出，TL-WCA的稳定期在三种算法中最长，而不稳定期要比LEACH-C短，但比GSEN的长。相比较而言，TL-WCA比其它两种算法的网络性能好，但是在快速收敛性方面GSEN优于TL-WCA。从图中还可以看出，TL-WCA的后一半节点死亡较快，因此更符合WSN个别节点死亡并不影响网络整体性能，但当大部分节点都已失效，网络的存在就毫无意义。

图4所示的是LEACH协议、GSEN协议和TLWCA协议的网络能耗的比较。仿真图中横坐标表示网络工作的轮数，纵坐标表示当前轮中整个网络中所有节点所消耗的能量。可见，在相同环境下，LEACH协议和GSEN协议所消耗的能量都要大于TL-WCA协议，因此能够有效延长网络的生存时间。具体来说，比如有100个节点随机分布在一个区域中，每个节点的能量相同，初始值都为0．5 J，则网络中所有节点的总能量为50 J。以第一个节点死亡的时间为基准，如果采用LEACH算法，此时消耗的总能量为37．369 1 J，而在该时间时对应的GSEN算法和TL-WCA算法，此时的能耗分别为29．726 3 J和18．089 7 J，如果以第一个节点死亡时间为网络的生命周期，则在这一网络生命周期内能量消耗分别降低了21．6%和51%，由此发现，TL-WCA协议在能量节省上具有极大的优越性。从图中还可以看出TL-WCA斜率最小，其次是 GSEN，最大的是LEACH，这说明TL-WCA中节点每轮消耗的能量都比LEACH和GSEN协议少。TL-WCA协议能够使得簇内节点能耗均匀，而且簇头之间的能耗也均匀，而LEACH的簇内节点能耗与簇首位置分布数目相关，当簇首均匀时簇内节点能耗均衡，反之不均衡，因此每轮的性能十分不稳定，这从图中曲线也可以看出。

图4 总能耗比较

4 结束语

本文分析了LEACH和GSEN两种路由协议，在两种算法的基础上提出了一种新的路由协议TLWCA。通过仿真结果表明，新的协议无论是在网络的第一个节点死亡时间还是最后一个节点死亡时间上都比LEACH，GSEN，LEACH-C有较大的改善，做到了普通节点之间、簇头之间的能量均衡，有效延长网络的生存周期。

[1]Sung Y，Tong L．A New Metric for Routing in Multi-Hop Wireless Senior Networks for Detection of Correlated Random Fields[C]//Newark:Military Communications Conference，2005:2327 －2332．

[2]Lindsey S，Raghavendra C S．Pegasis:Power Efficient Gathering in Sensor Information Systems[C]//Proc of the IEEE Aerospace Conf San Francisco:IEEE Computer Society，2002:1 －6．

[3]张品，徐智福，孙岩．一种新的基于簇头优化的WSN路由协议[J]．传感技术学报，2009，7(22):1013 －1017。

[4]Heinzelman W，Chandrakasan A，Balakrishnan．Energy Efficient Communication Protocol for Wireless Microsensor Networks[J]．IEEE Computer society，2002:3005 －3014．

[5]Younis O，Fahmy S．Heed:A Hybrid，Energy Efficient，Distributed Clustering Approach for Ad Hoc Sensor Networks[J]．IEEE Transactions on Mobile Computing，2004，3(4):660 －669．

[6]Tabassum N，Ahsanul Haque AKM，Urano Y．Gsen:An Efficient Energy Consumption Routing Scheme for Wireless Sensor Network[C]//Proceeding of IEEE International Conference on Systems and International Conference on Mobile Communication and Learning Technologies，2006:117 －112．

[7]Heinzelman W，Chandrakasan A，Balakrishnan．Energy Efficient Communication Protocol for Wireless Microsensor Networks[J]．IEEE Computer society，2002:3005 －3014．

[8]Heinzelman W，Chandrakasan A，Hari Balakrishnan．An Application-Specific Protocol Architecture for Wireless Microsensor Networks[J]．IEEE Trans on Wireless Communications，2002，1(4):660 －670．

[9]Smaragdakis G，Matta I，Bestavros A．Sep:A Stable Election Protocol for Clustered Heterogeneous Wireless Sensor Networks[C]//Proc of the 2nd international Workshop on SANPA 2004．Massachusetts，US，2004:1 －11．