一种基于LEACH 协议改进的簇间多跳路由协议

赵　静，吕红芳，渠帅军

(上海电机学院 电气学院， 上海 201306)



一种基于LEACH 协议改进的簇间多跳路由协议

赵静，吕红芳，渠帅军

(上海电机学院 电气学院， 上海 201306)

针对无线传感器网络(WSN)路由协议中能量消耗不均衡问题，研究了一种基于LEACH协议改进的簇间多跳路由协议LEACH-D算法。在分簇过程中，簇头选择增加了节点剩余能量和节点的“度”的因素；在簇间通信阶段，簇头节点按照Dijkstra算法形成的簇头间的最优路径以多跳的方式将信息传递给sink节点，其中权值综合考虑了下一跳簇头的能量和距离因素。通过对LEACH-D、LEACH-C和LEACH算法的网络剩余能量和网络生存时间进行仿真比较，结果表明LEACH-D算法可有效均衡网络的能量消耗，延长WSN的生命周期。

无线传感器网络； LEACH； 度； Dijkstra算法

无线传感器网络(Wireless Sensor Network， WSN)是集信息采集、信息传输、信息处理于一体的综合智能信息处理系统，被广泛用于农业、军事、医疗、环境监测等领域[1]。WSN中，节点一般采用电池供电，由于其一般都在人员很难接近的场所，能源不能及时供给；另外，目前可再生能源技术的应用还不够成熟[2]，故节能一直是WSN研究的重点之一。对于WSN中路由协议设计而言，一直都以均衡网络能量损耗、延长网络生存时间作为WSN路由协议设计的重要性能指标。目前，WSN路由协议分为平面路由和分簇路由两种[1]。平面路由不适合大规模网路应用，为了能在运行中维持较大的路由表，对分簇路由做了一定改进。LEACH路由协议是第一个提出分簇路由的协议，此后又做了许多改进。文献[3]中提出了一种基于LEACH的改进节能路由协议LEACH-PSOC，通过对簇头选择算法的改进，利用粒子群算法良好的收敛性和全局优化能力，将整个网络区域合理地分割成多个子区域，使网络能量均衡消耗，也减少了能量损耗，延长了网络的生存时间。文献[4]中提出一种改进的Q-LEACH路由协议，通过非均匀分簇以及自适应竞争半径的应用，有效地减少了能量消耗，通过Q-LEACH路由协议的子区间划分机制，改善了簇首间的多跳通信，更加减少了能量消耗，生命周期得到延长。文献[5]中针对LEACH协议中簇头选择不合理、多个簇头与基站远距离通信能量消耗过多的问题，运用PEGASIS协议中节点成链思想构造了簇头间的多跳路由，最后由链上担任Leader的节点完成了与基站的数据通信，均衡了能量消耗，延长了网络生存时间。文献[6]中提出一种基于稳定性的S-HEED分簇算法，以稳定性作为参数来决定节点的所属簇，针对节点移动性带来的簇内节点和簇头能量消耗过高问题，减少了簇头的消耗，延长了网络寿命。文献[7]中提出了一种基于能量均衡的分簇多跳路由协议EB-LEACH，通过增设中继节点协助数据转发、分担簇首节点工作的方式来节省节点能量，延长了整个网络的生命周期。文献[8]中提出了一种基于LEACH协议改进的簇间多跳路由协议，通过引入能量因子和距离因子修正了LEACH协议的阈值函数；在簇间通信过程中，簇头节点与sink节点之间采用多跳通信方式，簇头与簇头之间形成一条通向sink节点的优化路径，延长了网络的生存时间。

本文在已有文献研究的基础上，研究了一种基于LEACH协议改进的簇间多跳路由协议LEACH-D算法。该算法修正了簇头选择的阈值函数，增加了节点剩余能量、节点“度”的考虑；簇间通信采取多跳形式，簇头按照Dijkstra算法形成的最优路径来选择传输路径，权值考虑了下一跳簇头的距离和能量因素。通过仿真比较，表明该算法能均衡网络的能量消耗，延长网络的生存时间。

1　LEACH协议分析

LEACH协议运行流程以轮为周期[9-10]，分为簇结构形成和稳定工作两个阶段。簇结构形成阶段，全部节点按簇划分，节点当选簇头是随机的。簇头选举过程如下：每个节点随机生成1个在[0，1]间的数，若该节点n生成的随机值小于阈值T(n)，该节点为簇头节点；否则，为非簇头节点，

(1)

式中，p为当选簇头的节点数和所有节点数的比值；G为在剩余1/p轮中没有当选为簇头节点的节点集；r为协议的轮数。

节点当选为簇头节点后，在簇内广播信息(信息包括簇头信息和簇首ID等)，宣布自己当选为簇首。非簇首节点根据收到信号的强弱，加入信号强的簇中。簇头节点根据收到的加入簇请求的节点数生成相应的时分多址(Time Division Multiple Access， TDMA)时隙表，簇内的信息就按此TDMA时隙表传递，以避免信息堵塞。簇头节点收到簇内的数据，融合后直接发送到sink节点，每轮回一次，整个网络就重新分簇。

LEACH-D算法和LEACH算法的数据传递都采用一阶无线电模型[11]，如图1所示。图中，Etx和Erx分别为发射机和接受机处理数据所损耗的能量；Eelec为电路处理单位比特信号所损耗的能量，J/bit；εamp为放大器的放大系数。

图1　无线电模型Fig.1　Radio model diagram

当两个簇头的间距为d时，发射端发送k bit信息所损耗的能量为

(2)

接受端的能量损耗为

Erx=Etx(k)=k Eelec

(3)

此外，簇头节点对信号进行融合也要消耗一定的的能量EDA[12]。

2　改进的分簇算法LEACH-D

2.1成簇过程

LEACH算法运行中，簇头节点负责融合簇内节点的信息;融合后还需要传递给sink节点，故选择合适的簇头节点对减少网络损耗、提高传递信息的效率、延长网络生命周期非常必要。但LEACH算法采用随机选取簇头节点的方式，导致簇头分布不均匀和某些节点过早死亡，缩短了网络生命周期。为此，本文研究的LEACH-D算法在簇头选择时考虑了节点的剩余能量和节点的“度”(以节点为圆心、Tr为半径范围内所包含的节点数)，使选出的节点不仅有较高的剩余能量，且节点更趋于簇中心。修正后，

(4)

式中，T′(n)的调节函数为

(5)

式中，α和β为调节因子；Emax(r)为第r轮节点剩余能量的最大值；Ei(r)为第r轮节点i的剩余能量值;N(i)为节点i在半径Tr范围的节点数;Nmax(i)为节点的“度”的最大值。从式(5)可见，当剩余能量越大，节点的“度”越大，阈值T′(n)也相应变大，节点当选为簇头的概率也会增加；反之，T′(n)减小，节点当选簇头的概率也会减小。

2.2簇间通信

簇头融合簇内信息后，采取直接传输方式传递给sink节点。这样的传递方式使距离sink节点远的簇头节点的能量损耗加大，过大的传输损耗将导致节点过早死亡，缩短网络生存周期。LEACH-D算法采取多跳的方式传递数据。协作簇头的选取，即路径选择，按照Dijkstra算法形成最优路径。Dijkstra算法是典型最短路径算法，用于计算一个节点到其他所有节点的最短路径，其特点是以起始点为中心向外逐层扩展，直到扩展到终点为止[12-13]。

设Q=(V，E)是一个带权有向图，假设簇头节点和sink节点含有n个节点，用V={v0，v1，v2，…，vn}(j=0，1，2，…，n)表示。将集合V分成两组：第1组为已求出最优路径的顶点集合，用S表示。初始时，S中只有一个源点，即sink节点，以后每求得一条最优路径，就将其加入到集合S中，直到全部簇头节点都加入到S中，算法即结束。第2组为其余未确定最短路径的簇头集合，用U表示，按最小路径权值的递增次序依次将第2组的簇头节点添加到S中，期间，总保持v0到S中其他节点的权值都不大于从v0到U中任何簇头的最短权值。LEACH-D算法就是由sink节点出发寻找到各簇头节点的最小权值和的方法。

设每轮簇头数与sink节点数之和为NCH，建立簇头间的路径权矩阵

(6)

式中，a(i，j)为簇头节点i到簇头节点j的权，Dijkstra 算法中表示点与点之间的距离。

很显然，簇头在选择下一跳簇头时，不仅要考虑距离，还要兼顾到两方面：① 下一跳簇头的能量；② 与下一跳簇头间的距离，即

(7)

式中，

a(i，j)=Md(i，j)+N/E(j)

(8)

式中，M、N为权值函数的调节因子，且M+N=1；d(i，j)为簇头节点i到簇头节点j的距离；E(j)为簇头节点j的剩余能量值。由此可见，当i≠j或j≠i时，A(i，j)和d(i，j)成正比，与E(j)成反比。因此，M、N的取值影响了权值函数的大小，导致最佳路径的选取有所不同。

本文用少量的簇头节点来说明算法具体步骤，网络节点权向图如图2所示。

图2　网络结构权向图Fig.2　Right diagram of network structure

(1)初始时，S只包含源点sink节点，即S={v0}，v0的权值为0。U包含除v0外的其他簇头节点，U={v1，v2，v3}，U中簇头节点与v0的距离为两点之间的权值(若v0与U中簇头节点能连通)。由簇头间权的定义可知，由于2个簇头方向不同，权也不同，故增加了算法的复杂度。

(2)从U中选取一个距离v0最小的簇头节点v1，将v1加入到S中，路径权为3，故v1的权值为3。

(3)将v1作为中间点，修改U中各簇头节点的距离，即v1到v2、v3的权，则有U={1，5}；若从源点v0到顶点v3的距离(经过簇头v1)比原权值(v0到v3)短，则修改簇头节点v3的权值，修改后的权值是顶点v1的权值加上v1到v3边的权，把节点v3放入集合S中。

(4)重复步骤(2)、(3)直到所有顶点都包含在S中。按照算法运行得到的最优路径网络权向图如图3所示。

图3　最优路径网络权向图Fig.3　Right diagram of optimal path of the network

当sink点与各簇头间的最优路径确定后，按照路径(v0，v1，v3)以反向、多跳的形式传输信息至sink节点，此时发送节点为v3。对v3而言，在簇头节点间的信息传递阶段，其能量损耗包括信息的发送损耗和传递损耗，而中间的簇头节点能量损耗为接受和发送信息的能量损耗与传输信息的能量损耗之和。

3　仿真实验及性能分析

本文利用MATLAB软件，先通过仿真实验选取最佳的α、β和M、N取值，以分析LEACH-D分簇算法的性能。仿真环境设置如下[14-15]：100个点随机部署在200m×200m的区域内，sink节点坐标安置于中心位置(100，100)。仿真参数如表1所示。

表1　仿真参数

(1)调节因子(α，β)取值。实验通过设置不同的(α，β)来比较LEACH-D算法的不同生命周期曲线，得出最佳的(α，β)取值。

本文对(α，β)的取值采取经验取值法，即针对α>β、α<β和α=β这3种情况进行了大量的实验比较，最后得到当(α，β)为(0.9，0.1)、(0.5，0.5)、(0.3，0.7)时，分别在它们所在的取值范围内最优。图4给出了(α，β)为(0.9，0.1)、(0.5，0.5)、(0.3，0.7)时，LEACH-D分簇算法的生命周期曲线比较。

图4　不同(α，β)取值下，LEACH-D分簇算法的生命周期曲线比较Fig.4　Comparison of life-cycle curves of LEACH-D clusteringalgorithm with different values of α and β

由图4可见，当(α，β)=(0.9，0.1)时，LEACH-D分簇算法的生命周期最大，其次是(α，β)=(0.5，0.5)，当(α，β)=(0.3，0.7)时，生命周期最小。这说明当α>β时，LEACH-D分簇算法的生命周期曲线较α<β、α=β时都要理想。同时，也最终确定(α，β)的最佳取值为(0.9，0.1)。

(2)调节因子(M，N)取值。由于不同的(M，N)取值影响了最优路径的选取，进而对网络的能量损耗产生影响，使LEACH-D分簇算法的生命周期也发生改变。本文同样对(M，N)的取值采取经验取值法，即针对M>N、M

图5　不同(M，N)取值下，LEACH-D分簇算法的生命周期曲线比较Fig.5　Comparison of life-cycle curves of LEACH-D clusteringalgorithm with different values of M and N

由图5可见，当(M，N)=(0.8，0.2)时，LEACH-D分簇算法的生命周期最大，其次是(M，N)=(0.5，0.5)，当(M，N)=(0.3，0.7)时，生命周期最小。这说明当M>N时，LEACH-D分簇算法的生命周期曲线较M

(3)LEACH-D、LEACH-C和LEACH算法性能对比。利用表1的数据分别对LEACH-D算法、LEACH算法以及LEACH-C算法[12]进行性能比较，其中，LEACH-D算法选取最佳调节因子(M，N)=(0.8，0.2)、(α，β)=(0.9，0.1)。图6给出了LEACH-D、LEACH-C和LEACH 3种算法的生命周期曲线比较。由图可见，当算法运行至20轮左右，3种算法的存活节点数开始逐渐减少，其中，LEACH算法存活的节点数最少，LEACH-C算法次之，LEACH-D算法存活的节点数最多；且由图可见，LEACH-D算法的生命周期为36，LEACH算法的生命周期为18，LEACH-D算法的生命周期相比于LEACH算法提高了1倍，较LEACH-C算法提高了33.3%。

图6　3种算法的生命周期曲线比较Fig.6　Comparison of life cycles of three kind of algorithms

图7给出了3种算法每轮节点的剩余能量比较。由图可见，LEACH-D算法的剩余能量最大，其次是LEACH-C算法，LEACH算法的剩余能量最小。这是由于LEACH-D算法在选择簇头时，选择了靠近簇中心位置的簇头，使剩余能量更大的节点当选为簇头，减少了簇内的通信消耗，也均衡了能量损耗；同时，在簇间通信过程中，按照Dijkstra算法形成的最优多跳路径，不仅考虑到了距离因素，而且兼顾到了下一跳的簇头能量，从而减少了总能量损耗，也均衡了各簇头的能量损耗，延长了网络的生命周期。

图7　每轮节点剩余能量总和比较Fig.7　Total remaining energy consumption of all nodes in each round

3　结　语

本文在研究LEACH协议的基础上，对算法进行了改进，形成LEACH-D分簇算法。该算法对簇头的选择阈值函数进行了修正，增加了剩余能量和节点“度”的因素，使得剩余能量大、周围节点数多的节点更加容易当选为簇头节点，均衡了网络能量消耗，减少了簇内通信开销；并且，在簇间通信过程中，簇头节点采取簇间多跳的方式传递数据，按照Dijkstra算法形成的最优多跳路径，考虑了下一跳簇头节点的距离以及剩余能量。仿真结果表明，LEACH-D算法可大幅度减少单跳能耗，均衡了能量损耗，延长了网络生存周期。

[1]叶继华，王文，江爱文.一种基于LEACH的异构WSN能量均衡成簇协议[J].传感技术学报，2015，28(12)：1853-1860.

[2]NAYL A A，ALY H F.Solvent extraction of V(Ⅴ)and Cr(Ⅲ)from acidic leach liquors of ilmenite using aliquat 336 [J].Transactions of Nonferrous Metals Society of China，2015，25(12)：4183-4191.

[3]陈晓娟,王卓,吴洁.一种基于LEACH的改进 WSN 路由算法[J].传感技术学报，2013，26(1)：116-121.

[4]王东东，崔宝同.基于非均匀分簇多跳通信的改进Q-Leach研究[J].计算机技术与发展，2015，25(2)：212-215，220.

[5]胡峰松，肖球.一种基于 LEACH的能耗均衡多跳路由算法[J].小型微型计算机系统，2014，35(1)：70-73.

[6]杨梦宁，杨丹，黄超.无线传感器网络中改进的HEED分簇算法[J].重庆大学学报，2012，35(8)：101-106.

[7]周方，李腊元，戴佳佳，等.一种基于能量均衡的分簇多跳路由协议EB-LEACH[J].中北大学学报(自然科学版)，2013，34(4)：413-418.

[8]陈炳才，么华卓，杨明川，等.一种基于LEACH协议改进的簇间多跳路由协议[J].传感器技术学报，2014，27(3)：373-377.

[9]胡艳华，张建军.LEACH 协议的簇头多跳(LEACH-M)改进算法[J].计算机工程与应用，2009，45(34)：107-109.

[10]蒋华，刘伟强，王鑫.无线传感器网络中Leach-C路由协议的研究与改进[J].微电子学与计算机，2014，31(12)：43-47.

[11]杨永健，贾冰，王杰.无线传感器网络中LEACH协议的改进[J].北京邮电大学学报，2013，36(1)：105-109.

[12]王树西，李安渝.Dijkstra算法中的多邻接点与多条最短路径问题[J].计算机科学，2014，41(6)：217-224.

[13]刘春年，邓青菁.应急决策信息系统最优路径研究：基于路阻函数理论及Dijkstra算法[J].灾害学，2014，29(3)：18-23.

[14]马建乐，杨军.基于位置和剩余能量的局部集中式LEACH算法研究[J].传感技术学报，2013，26(3)：1147-1151.

[15]吕涛，朱清新，张路桥.一种基于LEACH协议的改进算法[J].电子学报，2011，39(6)：1405-1409.

Improved Inter-Cluster Multi-Hop Routing Protocol Based on LEACH Protocol

ZHAO Jing，LÜ Hongfang，QU Shuaijun

(School of Electrical Engineering， Shanghai Dianji University， Shanghai 201306， China)

To solve the problem of imbalance in energy consumption of routing protocols for wireless sensor networks(WSN)， an improved multi-hop routing protocol LEACH-D algorithm is proposed based on the LEACH algorithm.In clustering， the algorithm takes into account a factor of “degree” and the residual energy of nodes.In inter-cluster communications， cluster head nodes pass information to the sink through an optimal path according to the Dijkstra algorithm.By simulation， LEACH-D， LEACH-C and LEACH algorithms are compared in terms of network lifetime and residual energy of all nodes.The results show that the LEACH-D protocol can effectively keep balance in network energy consumption， and prolong life span of WSN.The weight function of the algorithm between cluster head nodes is modified by considering energy and the distance.

wireless sensor network(WSN); LEACH protocol; degree; Dijkstra algorithm

2016-06-25

赵静(1990-)，女，硕士生，主要研究方向为无线传感器网络通信协作，E-mail：2643894096@qq.com

2095-0020(2016)04-0221-06

TP 212.9

A