付云虹，李 尹

(1．国家超级计算长沙中心(湖南大学)，湖南 长沙 410082；2．中南大学 信息科学与工程学院，湖南 长沙 410083)

LEACH协议的簇首多跳与选择优化

付云虹1，李 尹2†

(1．国家超级计算长沙中心(湖南大学)，湖南 长沙 410082；2．中南大学 信息科学与工程学院，湖南 长沙 410083)

针对WSN层次型路由协议中簇首单跳传输数据至汇聚节点、而部分簇首因传输距离过长导致能量过早耗尽从而影响整个网络寿命问题，提出了基于剩余能量对簇首优化选择和簇首至汇聚节点间多跳数据传输的改进算法.对首个节点死亡轮数和能量图像方面进行了分析和仿真，结果表明该改进算法可使全网负载更加均衡，并进一步延长了网络整体寿命.

无线传感网络；层次型拓扑；簇首选择；多跳

无线传感网络(Wireless Sensor Networks，WSN)是大型的信息采集网络，传感器节点通常依靠电池供电，而电池能量有限，从而影响到整个无线网络的生存寿命，因此基于WSN的各种路由算法都会尽量节省能量，延长网络的整体寿命[1].路由协议的任务是将数据分组从源节点(传感器，sensor)通过无线网络转发到目的节点(汇聚节点，sink)[2-3].

无线传感网络中的路由协议从拓扑分布层面来看可分为平面型路由协议和层次型路由协议.由于平面型路由协议需要维护一个很大的路由表，从而会占用较大的存储空间与较多的计算资源，并不适用于规模巨大的无线传感网络，而层次型路由协议可以改善这一点.文章基于层次型路由中的LEACH协议[4]，致力于深入研究已有的针对LEACH协议的算法优化，以延长网络寿命和节省能量为目的，对其进一步优化和改进.

层次型拓扑控制利用分簇机制，选择一些节点作为簇头节点，由簇头节点生成处理和转发数据的骨干网，其余非骨干网节点可以暂时关闭通信信道，进入休眠状态以节省能量[5].层次型的拓扑协议有LEACH,HEED,GAF等.无线传感网络拓扑控制主要研究的问题是：在满足网络覆盖度和连通度的前提下，通过功率控制和骨干网节点的选择，剔除节点之间不必要的通信链路，生成优化的网络结构[6].LEACH协议是最初使用的协议，它的成簇思想对以后的协议改进影响很大.但是LEACH也有一些缺点，例如网络分簇不均匀、可扩展性差和容错性差等，因此后续的研究者根据其缺点进行了多方面的改进，下面是部分改进算法：

HEED算法针对LEACH算法簇头分布不均,以及簇的规模大小不均这一问题的改进[7].在此算法中，节点以不同的概率发送消息，剩余能量越大当选簇首的概率越大.非簇首节点使用簇内最小可达能量来衡量簇内节点的通讯成本并以此来选择合适的簇头,可以平衡簇内节点的个数[8].

基于节点的剩余能量选择簇首.考虑到无线传感网络的能耗问题，选取剩余能量较多的节点作为簇首.将节点的剩余能量作为选择簇首的一个重要衡量标准，以保证区域内剩余能量越多的节点，被选为簇首的概率越大.簇首与汇聚节点(Sink)或者说基站(Base Station, BS)之间的数据发送过程采用单跳的方式.由于汇聚节点距离数据采集区域距离不定，可能在区域内，也可能在区域外.即使是在区域内，根据成簇方式的不同，部分簇首离基站的距离也可能很远，因此这部分簇首将数据发送给基站时所消耗的能量较多[5].基于这一点，在簇首向基站发送数据的时候可考虑采用多跳的方式，这样可以使簇首节点能量的消耗相对减少.

另一种改进算法将原有的簇头选举分为两种情况：全网簇头选举和簇内簇头选举.在改进的LEACH算法中设置了一个阀值Va.每个簇周期开始时，首先检查簇头能量，如果所有节点的簇头能量中存在小于Va的簇头，则进行全网簇头选举，否则进行簇内选举[9].

本文在已有的LEACH改进协议基础上基于剩余能量对簇首进行优化选择和簇首至汇聚节点间多跳传输方面提出改进措施，并对第一个节点死亡轮数和能量图像开展分析和仿真，预期改进措施有3点：

1)根据距离汇聚节点远近对节点进行分类；

2)根据节点剩余能量不同进行簇首优化选择；

3)簇首间数据多跳传递至汇聚节点.

1 簇首个数最优化分析

采集区域内簇头最优个数的确定是对层次型路由算法进行改进的基础.设在M×M的区域内分布着N个节点，根据节点初始能量大小分为高级节点和普通节点两类，其中存在C个簇头，而C个簇头决定了在该区域内一共有C个簇，假定所有的节点均匀分布，因此每个簇内有N/C个节点，其中一个是簇首节点，其余节点有(N/C-1)个.下面对两类节点的能量消耗进行分析，首先分析簇首节点.

簇首能量消耗分为3部分：

1)接收非簇首节点传输数据的能量；

2)对接收到的数据进行融合处理的能量；

3)将融合后数据传输给汇聚节点的能量.

用公式表示为：

Ech=kEelec(N/C-1)+kEdaN/C+

kEelec+kεempd4

(1)

或

Ech=kEelec(N/C-1)+kEdaN/C+

kEelec+kεefsd2

(2)

式中Ech为簇首能量消耗；Eelec为射频接收或发射1bit数据所消耗的能量；Eda为数据融合的能量消耗；εemp为数据传输单位距离消耗能量(自由空间)；εefs为数据传输单位距离消耗能量(多径衰减)；N为节点总数量；C为簇头数量.

非簇首节点能量消耗分为接收周围相关信息消耗能量和将数据信息传输给簇首节点消耗的能量.用公式表示为：

Enonch=kEelec+kεempd4

(3)

或

Enonch=kEelec+kεefsd2

(4)

式中Enonch代表非簇首节点能量消耗.

总的能量消耗Etotal为：

Etotal=CEch+(N-C)Enonch

(5)

下面对式(1),(2)进行说明.由于传感区域很大，不同的节点传输数据到目标节点的距离有大有小，因而传输过程中衰减分为自由空间衰减和多径衰减[10].自由空间是一种理想介质，它不会吸收能量，但是随着传播距离的增大，发射天线的辐射功率密度与距离的平方成反比，因此自由空间传播损耗是一种扩散式的自然能量损耗.在非簇首节点传输信息给簇首节点时，一般距离比较近，可以用表示自由空间能量损耗的式(2)表示.多径衰落是指在微波信号的传播过程中，由于受地面或水面反射和大气折射的影响，会产生多个经过不同路径到达接收天线的信号，通过矢量叠加后合成时变信号.基于简化模型的思想，可认为远距离传输更容易发生多径衰落的现象.相对而言簇首节点和汇聚节点的距离较远，因此在后面计算中簇首节点的能量消耗用公式(1).以上是针对最优簇头个数进行计算，而决定其是属于自由空间衰减还是多径衰减具有一个临界距离，在仿真模拟时可更精确地进行判断.根据上述描述得到总的能量消耗公式：

Etotal=CEch+(N-C)Enonch=

(6)

总能量消耗Etotal对簇首个数C求导，并且令导数等于零，得到：

(7)

通过上述分析计算可以得到使数据采集区域总能量消耗最小的簇首最优个数的大小.决定节点是否为簇首的算法描述如图 1所示，其中R代表节点距离汇聚节点的距离，xm是传感区域的边长，其算法依据主要是考虑该节点离汇聚节点的距离以及是否是高级节点.

图1 簇首选举算法

Fig.1 Cluster head’s selection algorithm

2 簇首选择概率与多跳数据传输

根据距离大小可对节点进行细化分类，如果传感区域很大，使用单跳传输数据方式时，距离汇聚节点距离太大的簇首节点能量消耗将会非常快速.经典的LEACH算法采用的方式是每个节点不管距离汇聚节点的距离远近，其当选簇首节点的概率大小相同.而如果距离汇聚节点近的节点当选簇首的概率大，距离汇聚节点远的节点当选簇首的概率小，就会使节点数据尽量向靠近汇聚节点的方向传播，而不是先向远离汇聚节点的簇首传播，簇首再向汇聚节点传播.具体实现是以汇聚节点为圆心，以不同长度为半径将数据采集区域划分为多个区块，每个区块的节点当选簇首的概率不同.处于不同半径区域内的节点当选簇首的概率可通过设定不同的概率值进行仿真，根据仿真结果进行比对，以确定优化值.数据融合[11]方面，经典LEACH算法是非簇首节点把数据传输给簇首节点，簇首节点接收到数据后进行信息融合，再将数据传输给汇聚节点.在这过程中，簇首节点如果距离汇聚节点很远，那么单跳数据传输过程中的能量衰减会相对较大.簇首节点可以先比较自身与其他簇首节点和汇聚节点的距离哪个更近，如果是距离汇聚节点更近那么直接传输数据给汇聚节点；如果是距离另一个簇首节点更近则传输给该簇首节点，第二个接收到数据的簇首节点再将数据进行融合，进行比较，采用同样的方式对数据进行处理，直到传输给最后的汇聚节点.

之前也有学者对簇首节点多跳算法开展研究，但是数据采集区域面积大小与多跳算法改进效率的关系并未提及.簇首间采用多跳数据传输的出发点，在于离汇聚节点距离较远的簇首节点单跳传输数据给汇聚节点所耗费的能量太大，因此才考虑使用簇首间多跳.基于这一出发点，推测数据采集区域越大，其对整个网络生存寿命的改善效果应该越好.同时，中继簇首如果接收其他簇首的数据进行融合然后再传输也需要消耗能量，因此簇首多跳算法的改进效果与数据采集区域的大小是有密切关系的.

3 仿真结果与分析

使用Matlab工具开展仿真实验.本文所述的改进思路主要是在簇的建立阶段，因此考虑使用简化模型，只考虑簇建立阶段和数据传输阶段即稳定阶段的能量消耗，忽略节点数据具体内容和数据的融合方式.

将n个节点随机散布在传感区域内，sink节点分布在传感区域的中心，仿真用到的其他基础数据来自于文献[12].由于针对LEACH算法进行了两点改进，分析单独改进每一点后的仿真结果，最后再将两点综合起来分析仿真结果.

首先考虑根据节点距离汇聚节点远近选取不同的当选概率时的仿真结果，如表1所示.R是节点距离汇聚节点的距离，M为传感区域边长.在First-dead一列中代表网络中第一个节点死亡的轮数，该数据越大代表网络寿命越长，负载越均衡.如表中仿真结果所示，节点当选簇首概率选取数据⑥时，其第一个节点死亡轮数最长，性能最优，数据(①代表的是经典LEACH算法中簇首选择概率.由仿真结果可以算出，采用该改进方法，第一个节点死亡的轮数比经典算法优化：

(960-939)/939×100% = 2.24%

表1 以不同概率当选为簇首对网络寿命的影响

图2是上述数据的能量图像的对比，横轴代表传感网络运行的轮数，纵轴代表传感网络剩余的总能量.

由于节点是随机均匀分布，每次仿真时所得到的第一个节点死亡的轮数不尽相同，从图像和相关数据分析，改进后的算法在有节点死亡后的优势更加凸显，其能量下降得更慢一点，表明全网络的负载更加均衡一些.

下面分析使用簇首间多跳传输算法的仿真结果.

表2给出的是在数据采集区域大小取不同值时，对经典LEACH算法和改进簇首多跳传输算法(以LEACH-MH标示)第一个节点死亡轮数的比较，考虑到节点死亡数目达到一定比例后整个网络已不具备正常收集数据的能力，因此该对比过程仅以首个节点死亡时间作为参考.

轮数

轮数

表2 LEACH与LEACH-MH算法首个节点死亡轮数对比

根据表2中数据，可计算出不同的区域大小LEACH-MH算法对LEACH算法在延长全网络寿命的改善程度，直方图如图 3所示.

100 m×100 m：(965-939)/939=2.8%

200 m×200 m：(868-799)/799=8.6%

300 m×300 m：(315-221)/221=42.5%

由以上仿真结果可以看出，在其他条件相同的情况下，面积越大簇首多跳改进算法对全网生存周期的改善优势越明显，这与之前的推导结果是一致的.

将上文所述的改进点包括根据距离汇聚节点远近对节点进行分类、根据节点剩余能量不同进行簇首优化选择和簇首间信息多跳传递至基站综合起来，仿真得到与经典LEACH算法在延长全网生命期的数据如表3所示，仿真时采集区域大小为300 m×300 m.寿命相对提升率为：

(427-221)/ 221=93.2%

边长/(102 m)

表3 综合改进算法与LEACH生命期的比较

4 小 结

本文通过对经典LEACH算法及其改进算法进行研究，在综合节点与汇聚节点的距离、节点初始能量大小和传感区域面积这三点的基础上提出改进措施，延长第一个节点死亡时间即均衡网络负载延长网络寿命.通过Matlab对改进算法进行仿真后发现，改进程度的大小和传感区域面积大小有密切关系：面积越大多跳改进方案的优势越明显.虽然节点是随机分布的，簇头为随机选举，每次仿真时第一个节点死亡轮数不尽相同，但是从仿真结果看，对网络寿命还是有明显的延长.当然这其中还存在一些其他的问题，例如在距离越大当选簇头概率相对越小这部分改进措施适应性尚待加强，因为当区域面积改变或者节点数目改变时相应的概率大小也要随之调整；一些论文也提出多跳算法所用到的数据融合即将多级数据融合后压缩到原来的长度其实很难实现.下一步工作将会在以上不足之处再继续开展深入研究，进一步改善无线网络性能.

[1] OZEL Omur, TUTUNCUOGLU Kaya, YANG Jing,etal. Transmission with energy harvesting nodes in fading wireless channels: optimal policies[J]. IEEE Journal on Selected Areas in Communications, 2011,29(8):1732-1743.

[2] LIU A, ZHENG Z, ZHANG C,etal. Secure and energy-efficient disjoint multipath routing for WSNs[J]. Vehicular Technology, IEEE Transactions on, 2012, 61(7): 3255-3265.

[3] LONG H, QU Z H, FAN X,etal. Dynamic nearest neighborhood collaboration target tracking for WSN[J]. Energy Procedia, 2011, 11: 707-714.

[4] HEINZELMAN W B, CHANDRAKASAN A P, BALAKRISHNAN H. An application specific protocol architecture for wireless microsensor networks[J]. IEEE Transactions on Wireless Communications, 2002,1(4):660-670.

[5] RAZZAQUE M A, AHMED M H U, HONG C S,etal.QoS-aware distributed adaptive cooperative routing in wireless sensor networks[J]． Ad Hoc Netw,2014,19:28-42．

[6] LI Chang-le,WANG Li-ran, SUN Ting-ting,etal. Topology analysis of sireless sensor networks based on nodes’ spatial distribution[J]. IEEE Transactions on Wireless Communications, 2014,13(5): 2454-2467.

[7] YOUNIS O, FAHMY S. Distributed clustering in ad-hoc sensor networks: A hybrid, energy-efficient approach[C] // INFOCOM 2004, Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies. IEEE, 2004,1-5.

[8] 金鑫. 无线传感器网络层次型拓扑控制算法[D]. 合肥: 中国科学技术大学计算机科学与技术系，2008.

JIN Xin. A research on hierarchical topology control algorithms and the related problems of wireless sensor networks[D]. Hefei:Department of Computer Science& Technology, University of Science and Technology of China, 2008.(In Chinese)

[9] 唐甲东. 无线传感器网络路由协议研究-LEACH路由协议的改进[D]. 无锡: 江南大学物联网工程学院, 2013.

TANG Jia-dong. Research on routing protocol for wireless sensor networks-Improment of LEACH routing protocol[D]. Wuxi:College of Internet of Things Engineering, Jiangnan University, 2013. (In Chinese)

[10]LI Changle, WANG Liran, SUN Tingting ,etal. Topology analysis of wireless sensor networks based on nodes’ spatial distribution[J]. IEEE Transactions on Wireless Communications, 2014,13(5): 2454-2467.

[11]李嘉, 刘春华, 胡赛阳, 等. 基于交通数据融合技术的行程时间预测模型[J].湖南大学学报：自然科学版,2014,41(1):33-38.

LI Jia, LIU Chun-hua, HU Sai-yang,etal. A travel time prediction model based on traffic data fusion technology[J]. Journal of Hunan University: Natural Sciences, 2014,41(1):33-38. (In Chinese)

[12]SMARAGDAKIS Georgios, MATTA Ibrahim, BESTAVROS Azer. SEP: A stable election protocol for clustered heterogeneous wireless sensor networks[C]//Second International Workshop on Sensor and Actor Network Protocols and Applications (SANPA 2004).Boston MA,2004: 165-190.

Optimization of Cluster Head Multihop and Selection in LEACH

FU Yun-hong1, LI Yin2†

(1．National Supercomputing Center in Changsha, Hunan Univ, Changsha，Hunan 410082,China;2．School of Information Science and Engineering, Central South Univ, Changsha,Hunan 410083, China)

An improved algorithm in WSN hierarchical routing protocols was put forward, which considered the residual energy of cluster head selection and multi-hop data transmission from cluster heads to the sink node, to solve the problems of some cluster heads' premature depletion, which affect the whole life of the network, caused by part of the cluster heads over long distances with single hop data transmission to the sink node. Analyses and the simulations were conducted on the first node's death round number and the energy image.The results show that the improved algorithm can balance the network load better and extend the whole network life, compared with the traditional algorithms.

wireless sensor networks(WSN); hierarchical topology; cluster head selection; multi-hops

1674-2974(2015)02-0121-05

2014-08-05

国家科技支撑计划资助项目(2012BAH09B02);湖南省自然科学基金资助项目(14JJ5009)

付云虹(1968-)，女,贵州遵义人,湖南大学高级工程师†通讯联系人，E-mail:liyin2012@csu.edu.cn

TP391.9

A