基于优化成簇多跳的LEACH协议改进

石美红　王臻跃　姜寿山　赵　辉

(西安工程大学计算机科学学院　陕西 西安 710048)



基于优化成簇多跳的LEACH协议改进

石美红王臻跃姜寿山赵辉

(西安工程大学计算机科学学院陕西 西安 710048)

针对无线传感器网络分簇路由协议因簇内和簇间的能耗不均带来的覆盖空洞和能量空洞的问题，提出一种基于优化成簇多跳的LEACH协议改进。依据通信射频能耗模型，在成簇时，采用优化分区和双簇首模式，避免因成簇空间和簇首分布不均带来的“覆盖空洞”问题；在簇间路由时，基于簇首能量和与基站的距离，选择代价最小的路由，弥补了因簇首能耗不均导致“能量空洞”的现象。经仿真实验测试，结果表明，与LEACH及同类改进算法相比，该算法有效地降低了网络能耗，延长了网络生命周期，同时提高了网络数据吞吐量。

无线传感器网络LEACH协议优化成簇双簇首多跳路由

0　引　言

无线传感器网络WSN[1-3]利用各种微型传感器节点进行实时监测和采集网络分布区域内待监测对象的各种信息。WSN因其构建不需要固定的基础设施，具备部署灵活、自组织能力强以及可靠性高等优势，已被广泛应用于军事、医疗和环境保护等众多邻域[4,5]。能量受限是WSN的显著特点，如何高效利用节点能量并最大化网络生存周期是WSN研究领域中始终面临的一个难点和实用性问题。

在WSN路由协议中，分簇路由协议[6,7]占据着重要的地位。LEACH[8]算法是最早提出的一种分簇路由协议。它根据设定的门限阈值从网络覆盖区域内所有节点中随机循环选择簇首，其他节点根据接收信号强度选择要加入的簇。簇结构形成后，由簇首负责收集簇内数据并向基站转发数据。LEACH协议的最大优势是自适应集簇。但也存在着明显的不足，诸如，因随机选择簇首和频繁成簇，致使簇内以及簇间的能耗不均；因采用单跳模式转发数据，致使簇首间的能耗不均。随后，人们提出了各种改进算法，如LEACH-C[9](LEACH-Centralized)算法由基站集中控制分簇，减少了分簇所产生的通信和计算开销；针对单跳路由的弊端，LEACH-M[10](LEACH-Multi-hop)算法采用距基站最短的优化路径转发数据，减少了通信能耗；RPCR[11](Regional Partitioned Clustering Routing)协议采用均匀分区的方法，降低了成簇的通信开销；EEUC[12](energy-efficient unequal clustering)算法通过非均匀分簇和多跳路由相结合，使得簇首间的能耗均衡；文献[13]依据节点的初始能量及剩余能量，改进了簇首选择机制，通过单跳和多跳相结合转发数据，降低了能耗。但是，这些算法存在的共性问题是没有从全局和局部相结合的角度综合考虑簇内、簇首间以及簇与簇间的能耗均衡，致使网络存在“覆盖空洞”和“能量空洞”的问题[14,15]，影响了网络的生存周期。

针对上述问题，本文基于LEACH协议，结合其改进算法的优势，提出一种基于优化成簇多跳的LEACH协议改进OCMR(Clustering and Multi-hop Routing)。该算法基于通信射频能耗模型和网络规模，通过优化分簇和基于位置与能量的双簇首竞选，均衡簇内和簇间的负载；依据簇首的能量和空间分布，以通信代价最小的多跳方式选择路由，均衡簇首间负载。经实验仿真测试，验证了OCMR算法的可行性和有效性。

1　OCMR算法

1.1网络分簇及其优化机制

在网络分簇的过程中，确保簇内覆盖度和簇间连接度是至关重要的。如果簇内覆盖度不足或过大，会出现“覆盖空洞”或“覆盖重叠”的问题。同样，簇间连接度不足或过大，会引起“能量空洞”或“能量浪费”的问题。因此，通过对网络的合理分簇和均衡能耗是解决上述问题的方法之一。

依据LEACH协议的通信射频能耗模型：

(1)

ERx=K×Eelec

(2)

式中，ETx为发送端消耗的能量，ERx为接收端消耗的能量，K是传输数据包的位数，Eelec是发送或者接收1 bit数据消耗的能量，εfs是近距离发射放大器参数，εmp是远距离发射放大器参数，d是发送端与接收端间射频信号传输距离，d0是收发端间射频信号传输的临界距离。由式(1)分析不难看出，通信射频能耗主要包括数据的收发能耗和通信能耗。

图1　网络优化分区后的示意图

图2　簇内节点覆盖半径示意图

规则1保证簇内节点在其子区域内覆盖区域最大、子区域外覆盖区域最小。

基于上述规则，可以得出簇首节点的覆盖半径Rc满足：

(3)

簇间连接度依赖于各簇首节点的分布位置及其通信距离Rt。假设CH2,CH3,…,CHi(i=2,3,…,DN)是簇首CH1的邻域簇首，分布位置如图3所示，其中，DN为分簇的数目。如果邻域簇首CHi与簇首CH1间的临界分布位置如图4所示，那么，由图可知：

(4)

图3　CH1簇首与其邻域簇首CHi分布的示意图

图4　CH1簇首与其邻域簇首CHi分布的临界距离

为了确保簇首与其邻域簇首间的稳定连接，同时避免能量浪费，Rt选取应遵循规则2。

规则2保证簇首CHi与CHj(i≠j)间连接覆盖它们所在簇的全部区域且通信能耗最小。

由此可得，簇首间的连接半径Rt应满足：

(5)

1.2分簇数目优化计算

假定在一个M×M的网络区域内随机均匀分布N个节点，其中基站位于区域中心。欲把其分成DN个簇，则每个簇包含的成员节点数为(N/DN)-1个。

对于成员节点，每轮中的能耗表现在发送数据以及将数据传输至簇首这两部分。因簇内的通信距离较短，一般使用自由空间信道模型，那么，每个成员节点的能耗Enon-CH为：

(6)

式中，dtoCH是成员节点到其簇首间的距离。如果簇内节点随机均匀分布，则节点分布密度p=1/(M2/DN)。依据规则1，若簇首位于子区域中心，那么，成员节点到簇首的距离平方定义为：

(7)

(8)

(9)

(10)

式中，C是以基站或邻域簇首为圆心、d0为半径的圆域，S是整个网络所覆盖的区域，(x,y)是簇首在网络中的位置。

在每一轮中，每个簇首的能耗ECluster为：

(11)

那么，网络的总能耗ETotal是：

ETotal=DN·ECluster

(12)

分别将式(7)、式(9)、式(10)和式(11)代入式(12)，并对ETotal的变量DN求偏导，令其导数为0，得到最优值为：

(13)

由式(13)分析不难看出，最佳分簇数目DNOPT主要与网络规模M、节点数目N密切相关。当网络规模和节点数目确定的情况下，DNOPT就唯一确定。为了让分区后簇结构区域形状更接近网络节点的覆盖区域，采用行与列等分的分区方式，则分区后为正方形子区域，故最终的分簇数目应该为DNOPT值附近的平方数。

1.3OCMR算法步骤

OCMR算法分为初始化网络、竞选簇首和构建簇间路由三个步骤。网络初始化后，按“轮”竞选簇首和构建簇间路由。

步骤1初始化网络

规则3由基站完成网络分区形成簇，并赋予每个簇唯一的标识ID，每个节点记录自己所在簇的ID。

(1) 基于LEACH协议的通信射频能耗模型，计算能耗最小的最佳分簇数目DNOPT。

(2) 根据确定的DNOPT对整个网络覆盖区优化分簇，每个子区域内节点形成一个簇，给每个簇i(i=1,2,…,DNOPT)赋予唯一的标识号ID。

(3) 计算每个簇i的中心位置(xic,yic)以及覆盖范围半径Rc。

(4) 计算每个簇i的节点平均能量Eai以及距簇中心(xic,yic)的平均距离Dai。

(5) 为每个簇构建一个结构体数组AreaStruct()，用于存储包括ID、(xic,yic)和Rc分区信息，并广播以上簇信息。

步骤2竞选簇首

规则4竞选簇首时，一旦簇内节点接收到其他节点作为簇首的身份信息时，立即退出竞选。

(1) 当簇i内的节点Nj(j=1,2,…)接收到簇信息后，计算自身与簇中心(xic,yic)的距离Sj。

(2) 每个Nj依据所在簇的Sj和自身的剩余能量Erj，按照式(14)计算广播时间tj：

(14)

式中，TCH是系统预定义的簇首竞选时间，其取值为簇内最远两端节点间信息传播时间，以避免簇内节点竞选簇首时因并发而产生的冲突。式(1)表明，如果节点Nj满足ErjDai条件时，则放弃竞选簇首；否则，距簇中心(xic,yic)的距离Sj越小，剩余能量Erj越大，因广播时间tj越短而成为簇首的机会就越大。

(3) 用tj时间启动定时器，若定时时间到还未接收到其他节点的簇首身份信息时，则节点Nj向簇内其他节点广播自己成为簇首的身份信息；否则，节点Nj为成员节点。

(4) 已选定为簇首的节点Nj，在其簇内，以节点Nj为中心，半径为Sj的区域Aj内，选择副簇首。如果节点Nk满足式(15)条件, 则作为副簇首。

(15)

步骤3构建簇间路由

规则5在簇内，主簇首负责簇内数据的收发及融合，副簇首承担簇间路由的数据转发。

(1) 记录参与多跳路由的簇首节点标识CHi(i = 1,2,…,DNOPT)及其对应位置(xi,yi)，并计算簇首节点CHi(i=1,2,…,DNOPT)到基站以及到其邻域簇首CHn(n=1,2,…,M，M为CHi的邻域簇首数目)间的距离。

(2) 根据式(16)计算CHi与其邻域簇首CHn间构建路由的代价函数cost(i,n)：

(16)

其中，dCHitoBS和dCHitoCHn分别表示簇首CHi到基站BS间、CHi到邻域簇首CHn间的距离；dCHntoBS表示邻域簇首CHn到基站BS间的距离；ECHn表示邻域簇首CHn的剩余能量。当i=n时，即簇首选择自身作为中继节点。

(3) 如果CHi的邻域簇首CHp满足式(17)条件，则选择CHp作为CHi的中继路由节点：

cost(i,p)=min{cost(i,n)}n=1,2,…,M

(17)

数据传输阶段，主簇首采用TDMA机制承担簇内节点数据的汇聚，并传送给副簇首；副簇首采用CSMA机制完成簇间路由和数据转发至基站，之后进入下一轮。

2　实验仿真及结果分析

2.1实验仿真的环境及其参数设定

假设网络具有如下属性：

(1) 基站BS惟一，部署在网络左下角，并有足够的能量；

(2) 所有传感器节点随机均匀分布在边长为M的正方形区域中，传感器节点部署后不再移动；

(3) 除BS外，所有传感器节点具有惟一的标识，且具有相同的计算和通信能力以及初始能量，但能量有限；

(4) 所有传感器节点都具有功率控制能力，可改变自己的传输功率。

本文在Matlab 7.6(R2008a)的平台下进行了大量数据的实验验证，仿真参数如表1所示。根据式(13)计算DN的最优值DNOPT为19.92，与其最近的平方数是16。为了检验DN值的最优性，图5是在连续选取不同的DN值，其平均每轮网络能耗的变化曲线。从图中不难看出，DN在最优值下其能耗最低。

表1　实验仿真参数

图5　不同DN值的能耗

2.2结果与分析

为了验证OCMR算法的有效性，分别与LEACH算法、RPCR、LEACH-M以及文献[13]算法进行了网络能耗和网络生命周期性能的对比。

图6(a)、(b)是经本文算法和LEACH算法处理得到的分簇结构。相对于LEACH算法，OCMR算法的簇结构分布更均匀，各簇内节点分布密度差异较小。这是因为LEACH是以随机选择的簇首作为分簇的依据，而OCMR算法是依据网络规模和节点分布划分簇结构。图7和图8是随着轮数的增加，不同算法的网络能耗和网络剩余节点数的变化曲线。从图7和图8的计算结果看，在相同时间轮数下，OCMR算法的网络能耗和第一个节点死亡时对应的轮数都优于其他算法。这是因为OCMR算法结合全局和局部的簇分布和节点能耗，均衡簇内节点、簇首间以及簇与簇间的负载，避免或缓解了网络“覆盖空洞”和“能量空洞”的问题。

图6　分簇结构比较

图7　网络能量消耗的变化　图8　网络存活节点数的变化

图9给出了随着轮数递增，不同算法的节点剩余能量均值的变化情况。结果表明，在相同时间轮数下，OCMR算法的网络节点剩余能量均值均高于其他算法，这表明该算法的网络能耗均衡性优于其他算法。图10是随着网络节点平均能耗的递增，不同算法的基站接收的数据包变化趋势。结果显示，在相同的网络节点平均能耗下，相对其他算法，本文算法可使得基站接收到更多的数据包，表明网络的吞吐量较高，这是因为OCMR算法使得簇内、簇首、簇间的能量分布均衡所致。

图9　网络剩余能量均值比较　图10　基站接收的数据包数目比较

为了验证OCMR算法的网络生命周期性能，当网络区域内分布不同规模的节点，分别统计网络中第一个节点死亡和全部节点死亡对应的轮数变化情况，如图11和图12所示。统计结果表明，从总体上看，各种算法都是随着节点数的增加，节点死亡对应的轮数趋于下降。但是，不难看出，OCMR算法的网络生命周期比其他算法更长。

图11　第1个节点死亡所对应的轮数变化　　图12　全部节点死亡所对应的轮数变化

3　结　语

在无线传感器网络中，分簇路由算法有着广泛的应用前景。然而，如何高效利用能量、降低能耗、延长网络生命周期一直是分簇路由算法面临的具有挑战性的研究内容之一。针对LEACH及其改进的分簇路由算法存在的问题，提出了一种基于优化成簇多跳的LEACH协议改进算法，其主要特点是：(1) 通过优化分簇和竞选簇首，均衡网络的能量分布，避免因成簇空间和簇首分布不均带来的“覆盖空洞”问题；(2) 采用双簇首模式和多跳路由，均衡网络中簇首间的负载，弥补了因簇首节点能耗不均导致“能量空洞”的问题。

[1] 马祖长,孙怡宁,梅涛.无线传感器网络综述[J].通信学报,2004,25(4):114-124.

[2] 李建中,高宏.无线传感器网络的研究进展[J].计算机研究与发展,2008,45(1):1-15.

[3] 钱志鸿,王义君.面向物联网的无线传感器网络综述[J].电子与信息学报,2013,35(1):215-227.

[4] 胡曦明,董淑福,王晓东,等.无线传感器网络的军事应用模式研究进展[J].传感器与微系统,2011,30(3):1-3.

[5] 马德新,徐鹏民,许金普,等.无线传感器网络在环境监测中的应用[J].电子元件与材料,2013,32(12):81-82.

[6] 沈波,张世永,钟亦平.无线传感器网络分簇路由协议[J].软件学报,2006,17(7):1588-1600.

[7] Sohrabi K,Gao J,Ailawadhi V,et al.Protocols for self-organization of a wireless sensor network[J].IEEE Personal Communications,2000,7(5):16-27.

[8] Heinzelman W,Chandrakasan A,Balakrishnan H.Energy efficient communication protocol for wireless micro sensor networks[C]//Proceedings of the 33rd Hawaii International Conference on System Sciences.Hawaii,USA:IEEE Computer Society,2000:3005-3014.

[9] Heinzelman W,Chandrakasan A,Balakrishnan H.An Application-Specific Protocol Architecture for Wireless Microsensor Networks[J].IEEE Transactions on Wireless Communication,2002,1(4):660-670.

[10] 李岩,张曦煌,李彦中.基于LEACH协议的簇头多跳(LEACH-M)算法[J].计算机工程与设计,2007,28(17):4158-4160.

[11] Duan C Q,Sun J J,Zhou D,et al.An Energy Efficient Regional Partitioned Clustering Routing Algorithm for Wireless Sensor Networks[C]//Second International Conference on Intelligent Networks and Intelligent Systems.Tianjin,China:IEEE Press,2009:205-208.

[12] Li C F,Ye M,Chen G H,et al.An energy-efficient unequal clustering mechanism for wireless sensor networks[C]//IEEE International Conference on Mobile Adhoc and Sensor Systems. Washington,DC:IEEE Press,2005:597-604.

[13] 李亚男,徐夫田,陈金鑫.基于LEACH的WSNs分簇优化策略[J].传感技术学报,2014,27(5):670-674.

[14] 王东方,齐小刚.无线传感器网络解决能量空洞问题综述[J].计算机科学,2010,37(12):18-21.

[15] 胥楚贵,邓晓衡,邹豪杰.无线传感器网络覆盖空洞修复策略[J].传感技术学报,2010,23(2):256-259.

IMPROVING LEACH PROTOCOL BASED ON OPTIMISED CLUSTERING AND MULTI-HOP ROUTING

Shi MeihongWang ZhenyueJiang ShoushanZhao Hui

(College of Computer Science,Xi’an Polytechnic University,Xi’an 710048,Shaanxi,China)

In light of the problems of coverage holes and energy holes of cluster-based routing protocol in wireless sensor networks (WSNs) caused by uneven energy consumption within the cluster heads and inter-cluster, the paper proposes an improved LEACH protocol based on optimised clustering routing. According to energy consumption model of communication radio frequency, when clustering it adopts the modes of partition optimisation and dual-cluster heads to avoid the “coverage hole” problem brought in by uneven distribution in clustering space and cluster heads; When inter-cluster routing it selects the route with least cost based on cluster heads energy and the distance to the base station, thus makes up the “energy hole” phenomenon led by uneven energy consumption of cluster heads. The improvement has been tested by simulation experiment, and results show that compared with LEACH and the similar improved algorithms, this one effectively reduces the energy consumption of network and prolongs WSNs lifetime, meanwhile it enhances the data throughput of networks as well.

Wireless sensor networksLEACH protocolOptimised clusteringDual-cluster headsMulti-hop routing

2015-05-22。国家科技支撑计划项目(2014BAF07B 01)。石美红，教授，主研领域：智能信息处理，图形图像处理。王臻跃，硕士生。姜寿山，教授。赵辉，硕士生。

TP393

A

10.3969/j.issn.1000-386x.2016.09.029