能量异构无线传感器网络分簇路由改进算法*

李安超,陈桂芬

(长春理工大学电子信息工程学院,长春 130022)

能量异构无线传感器网络分簇路由改进算法*

李安超,陈桂芬*

(长春理工大学电子信息工程学院,长春 130022)

路由算法作为无线传感器网络的核心技术,对延长网络生命周期,提高网络效率起到了至关重要的作用。针对分布式能量有效成簇算法未考虑节点位置和对节点保护、利用不充分的问题,提出了一种改进的能量异构分簇路由算法。该算法引入边缘度的概念,使距离基站近的节点优先担任簇头,减少了网络能量消耗;设立了双能量阈值,提高节点能量利用,延长节点生命周期;综合考虑节点、簇头、基站三者的位置分布,提出了更合理的入簇机制。仿真结果显示,在小面积检测(10 m×10 m到100 m×100 m)与大面积检测(100 m×100 m到500 m×500 m)环境下改进算法与原算法相比,网络生命周期分别提高了18.7%到36.2%,24.4%到66.5%。

异构无线传感器网络;路由算法;边缘度;双能量阈值;入簇机制

无线传感器网络WSNs(Wireless Sensor Networks)作为信息技术的三大支柱之一,凭借其独特的学科交叉性,已经成为国际上备受关注的关键技术。无线传感器网络由部署在检测区域内的大量微型、廉价、低功耗的传感器节点组成,传感器通过相互协作的方式感知和采集检测环境的信息,并对数据进行预处理然后将处理后的信息传送给用户[1-2]。无线传感器网络的应用领域十分广阔,目前已经可以广泛应用于环境检测、医疗护理、军事、环境科学等其他一些商业应用领域[3]。无线传感器网络可以根据传感器节点的异同,分为同构型无线传感器网络和异构型无线传感器网络,其中仅初始能量不同的节点所组成的能量异构型无线传感器网络符合现实情况,更具有研究价值。

路由算法是无线传感器网络的核心技术之一,直接决定了传感器节点在传输数据时的效率。由于传感器节点能量微小且随机分布,远距离传输数据会大量消耗能量,不合理的路由算法很容易引发局部节点快速死亡而产生的能量黑洞现象,因此研究合理有效的路由算法具有现实与科研的意义。

目前,国内外学者提出了多种路由算法,其中分簇型路由算法凭借良好的可扩展性和优异的网络性能,已经成为无线传感器网络路由算法的研究重心。典型的分簇型路由算法有低能量自适应分群算法LEACH(Low Energy Adaptive Clustering Hierarchy)[4]、门限敏感的传感器网络节能算法TEEN(Threshold sensitive Energy Efficient sensor Network protocol)[5]、分布式能量有效成簇算法DEEC(Distribute Energy-Efficient Clustering Algorithm)[6]等。LEACH算法使每个节点轮番担任簇头,平均网络负载,但节能性一般;TEEN算法提出双门限值减少数据传输量,但实时性很差。

DEEC算法作为LEACH算法的改进,在其优点的基础上,动态的调整每个节点当选簇头的概率,提高了能量效率,因此受到国内外学者的关注。文献[7]改进了DEEC算法中最佳簇头个数与每轮平均能量公式,使整体网络能量更加清晰明了,但没有考虑节点位置因素;文献[8]考虑了节点的位置分布,使靠近基站的节点更易当选簇头,却没有对低能量节点进行保护,很容易造成基站附近的节点因反复当选簇头而迅速死亡。

针对上述问题,本文首先分析了DEEC算法的优缺点并在其基础上提出了一种改进能量异构分簇路由分布式能量有效成簇改进算法RDEEC(Reformative Distribute Energy-Efficient Clustering Algorithm),综合考虑了节点位置、剩余能量、入簇机制等方面对网络生命周期的影响,引入了边缘度与双能量阈值,优化了入簇机制,延长了网络的生命周期。

1 相关研究

1.1 异构传感器网络

1.1.1 异构传感器网络分类

异构传感器网络可以根据节点感测能力、计算能力、通信能力和能量等不同而分为4种类型:计算能量异构型、节点能量异构型、链路异构型和网络协议异构型[9]。本文研究节点能量异构型传感器网络,即节点配置不同的初始能量,这一特征也具有现实意义。

1.1.2 多级能量异构传感器网络

在多级能量异构传感器网络中,节点的能量值是在一个区间随机分布的,我们区分节点为普通节点和高能节点两种,普通节点的初始能量为Eo,高能节点的初始能量为Eo(1+ai),ai表示高能节点超过普通节点能量的倍数,因此节点的初始能量可以描述为在[Eo,Eo(1+amax)]的区间内随机分布[10]。其中amax为所有能量倍数ai的最大值。因此网络的整体能量可以描述为式(1):

(1)

1.1.3 异构无线传感器网络能耗模型

异构无线传感器网络中的能耗模型如下[11]。

节点的能耗公式主要有3种,分别为发送数据能耗ETx(l,d),接收数据能耗ERx(l),数据融合能耗Ec。具体公式如式(2)～式(5):

(2)

ERx(l)=lEelec

(3)

Ec=(M+1)lEDA

(4)

(5)

式中:l为发送的数据大小;Eelec为发射电路的能耗;εfs和εmp为功率放大的能耗;d0为节点有效距离的阈值;EDA为单位数据融合的能耗,M为簇内成员的节点数。

1.2 DEEC算法

DEEC算法以LEACH算法为基础并改进了其未考虑节点剩余能量的缺点,使高初始能量及高剩余能量节点当选簇头的概率增加,从而均衡网络负载,延长了网络生命周期。算法原理与LEACH算法相似,网络周期性的按轮(round)运行。每个轮循环分为簇的建立(set-up)阶段和稳定工作(steady-state)阶段,稳定工作阶段也即为数据传输阶段[12]。算法实现原理如下:

①簇的建立阶段:

在能量异构无线网络中,每个节点的初始能量不同[13]。节点当选簇头的概率为式(6)所示:

(6)

(7)

式中:G为当前普通节点的集合。

②稳定工作阶段:

簇头节点确立后,该簇头节点便会向邻居节点通过广播的方式发送“入簇”的消息,非簇头节点收到此消息时,就根据收到消息信号的强弱,选择最强信号的簇头节点加入。

1.3DEEC算法的缺点

DEEC算法在LEACH算法的基础上考虑到了节点的剩余能量,使高剩余能量节点更高概率当选簇头,但DEEC算法的缺点如下:①低剩余能量节点仍有可能当选簇头。②高剩余能量节点不能重复当选簇头,利用率很低。③簇头选举时未考虑到节点的位置分布因素。④在入簇机制上选择最近的簇头点加入,考虑因素太片面。

2 RDEEC算法

针对DEEC算法的缺点,提出了一种改进的节能分簇路由算法RDEEC,该算法适用于多级能量异构传感器网络。具体实现过程如下:

①簇的建立阶段:

首先,向检测区域随机部署N个节点,节点能量服从多级能量异构传感器网络设定,每个节点当选为簇头的概率如式(8):

(8)

(9)

式中:Etotal为多级能量异构传感器网络整体能量,见式(1),r为当选循环轮数,rmax为设定的最大循环轮数。

记录每个节点到基站的距离dis(i),引入边缘度edge(i)的概念,边缘度的计算公式如下(10):

(10)

式中:dismax为节点到基站的最远距离。

引入边缘度之后的当选簇头概率pi为式(11):

pi=piedge(i)

(11)

簇头的当选不仅要考虑节点的剩余能量,还要考虑节点的位置分布,使靠近基站的高能量节点更易当选为簇头。

RDEEC算法的阈值同式(7),同时引入最低当选能量阈值Elow如式(12):

Elow=0.2Etotal(1-r/rmax)2/N

(12)

只有当节点的剩余能量大于Elow时才能参与簇头选取过程,从而避免了低能量节点当选为簇头的情况,保护了低能量节点。

在第一轮簇头选取中,每个节点产生一个0～1的随机数,若该随机数小于式(7)设定的阈值,则该节点当选为簇头。

从第二轮开始,上一轮中未当选簇头且剩余能量大于Elow的普通节点参与簇头选取,同时,上一轮中当选过簇头且剩余能量大于重复当选能量阈值的节点也被允许参与簇头选取。重复当选阈值如式(13):

Erep=1.5Etotal(1-r/rmax)/N

(13)

这样,可以使高能量节点反复充当簇头,提高高能量节点的利用率。

②稳定工作阶段:

簇头选定后,普通节点执行入簇选择,传统入簇是选择距离最近的簇头加入,但由于异构传感器网络发送数据如式(2),在d0范围内功率放大能耗采用自由空间模型,传输距离大于等于d0时,采用多路径衰减模型。假设节点分布如图1所示,计算普通节点选择不同簇头加入并发送lbit数据至基站所消耗的能量,其中εfs,εmp参数如式(14)、式(15):

εfs=10 pJ(bit·m2)

(14)

εmp=0.001 3 pJ(bit·m4)

(15)

图1 节点分布示意图

当节点选择簇头A加入后,传输lbit所需要消耗的能量为:

Econ1=lEelec+l×10×152+lEelec+l×0.001 3×804=2lEelec+55 498l

当节点选择簇头B加入后,传输lbit所需要消耗的能量为:

Econ2=lEelec+l×10×252+lEelec+l×0.001 3×704=2lEelec+31 213l

通过对比两者消耗的能量,可以看出,当节点选择距离自己最近的簇头加入后,消耗的能量增加,说明传统的入簇机制没有充分考虑所有因素。

因此RDEEC算法改进后的入簇机制为式(16)

(16)

式中:dtoCH为节点到簇头节点的距离,dtoBS为簇头节点到基站的距离。a为设定的权重,属于[0,1]区间内,可以根据不同的应用环境进行设定,最后选择使D最小的簇头节点加入。RDEEC算法流程如图2所示。

图2 RDEEC算法流程图

3 仿真结果分析

在仿真环节,根据节点传输数据方式的不同设立了两组实验环境,分别是以自由空间方式传输为主的小面积检测环境(10 m×10 m到100 m×100 m)和以多路径衰减传输方式为主的大面积(100 m×100 m到500 m×500 m)检测环境,并利用MATLAB仿真软件比较在不同应用环境下,DEEC算法与RDEEC算法性能,仿真实验参数如表1所示,基站设定为检测区域中心。

表1 仿真参数

3.1 小面积检测环境下仿真结果分析

从图3可以看出在小面积检测环境下,RDEEC算法比DEEC算法网络生命周期更长,增长比例为18.7%～36.2%,其中检测区域面积为100 m×100 m环境下,RDEEC算法比DEEC算法增加了36.2%的生命周期,提升最为明显。

图3 小面积检测环境下生命周期对比

从整体趋势来看,在检测区域面积为10 m×10 m 到90 m×90 m的区间内,两种算法网络生命周期曲线都平缓下降,因为此时节点间传输距离小于有效传输距离d0,节点间以自由空间方式传输数据,耗能较少,随着检测面积的不断增大,整体网络剩余能量下降速度稳定;在检测区域面积为100 m×100 m时,两种算法的网络生命周期曲线迅速下降,因为此时节点间传输距离出现大于d0的情况,有部分节点以多路径损耗方式传输数据,大量消耗网络能量,从而使整体网络生命周期迅速减少。

为了更加直观体现出在小面积检测环境下RDEEC算法与DEEC算法的差异,本文在检测区域面积为100 m×100 m环境下进行仿真,主要考虑以下参数:网络生命周期,网络能量消耗和网络传输数据。

图4为100 m×100 m环境下网络生命周期对比。仿真结果显示,DEEC算法网络生命周期为1 254轮,RDEEC算法网络生命周期为1 708轮,比DEEC算法提高了36.2%。这是由于RDEEC算法设立了双能量阈值,保护了低能量节点,提高了高能量节点的利用率,增加了网络生命周期;同时更长的网络生命周期也就意味着更多的传输数据,如图5所示,RDEEC算法网络整体传输数据为110 947 bit,而DEEC算法仅传输了48 718 bit的数据,效果提升明显。

图5 100 m×100 m环境下网络数据传输对比

图6为100 m×100 m环境下网络能量消耗对比。DEEC算法与RDEEC算法两者总能量相同,但DEEC算法却比RDEEC算法在更短时间内将网络能量消耗殆尽,反映出RDEEC算法比DEEC算法更加节约能量。

图6 100 m×100 m环境下网络能量消耗对比

3.2 大面积检测环境下仿真分析

在该类环境中,检测区域面积大大增加,使节点间数据传输以多路径衰减方式为主,两种算法的网络生命周期都大大缩减,如图7所示。

图7 大面积检测环境下生命周期对比

仿真结果显示,RDEEC算法比DEEC算法增加了24.4%～66.5%的生命周期,提升效果比小面积检测环境更为明显,因为RDEEC算法通过引入边缘度来考虑节点位置因素,在大面积检测环境下性能更加优异。

我们可以以图7中曲线斜率作为下降速度的指标,以数值的方式直观体现出两种算法的性能。两种算法下降速度如表2所示。

表2 网络生命周期下降速度

从表2可以看出检测区域面积从250 m×250 m到500 m×500 m的区间内,RDEEC算法生命周期下降速度大于DEEC算法,且在检测区域面积为500 m×500 m时,两种算法生命周期差距不大,说明RDEEC算法不再适合更大面积的检测环境。

为了更加直观体现出在大面积检测环境下RDEEC算法与DEEC算法的差异,在检测区域面积为300 m×300 m的环境下再次进行仿真,仿真结果如下:

图8为300 m×300 m环境下网络生命周期对比,仿真结果显示DEEC算法的网络生命周期为885轮,而RDEEC算法的生命周期为1 474轮,比DEEC算法提高了66.5%,提升效果明显。因为随着检测区域面积的扩大,RDEEC算法一方面引入边缘度使高能量且靠近基站的节点当选为簇头,另一方面双能量阈值又保护了因反复充当簇头的低能量节点,从而提高了网络生命周期。

图8 300 m×300 m环境下网络生命周期对比

图9 300 m×300 m环境下数据传输对比

图9为300 m×300 m环境下网络数据传输对比,RDEEC算法网络传输数据为35 324 bit,DEEC算法仅传输7 007 bit数据,可以看出RDEEC算法比起DEEC算法而言,传输数据量更大,更适合于大面积检测环境,同样如图10所示可以直观的看出,RDEEC算法比起DEEC算法更加节能。

图10 300 m×300 m条件下网络能量消耗对比

3.3 入簇机制改进仿真

针对不同的应用环境,新的入簇机制中的权重a也不同。图11为100 m×100 m环境下不同权重a的RDEEC算法生命周期。可以看出,网络生命周期随着权重a的增大而增加,在a=0.9的情况下网络生命周期达到最大,因为该环境下,节点间距离小于do,节点间传输多采用自由空间损耗方式传输数据,入簇机制中的前一项所占权重更高,因此权重a大约在0.9时入簇机制达到最优,网络生命周期最长。与此产生鲜明对比的是300 m×300 m的环境。

图11 100 m×100 m环境下不同权重a的网络生命周期

图12 300 m×300 m环境下不同权重a的网络生命周期

如图12所示,在该环境下,权重a=0.4时网络生命周期达到最大,因为随着检测区域的扩大,簇头与基站间传输多采用多路径衰减方式传输数据,在入簇机制中后一项成为关键因素,增加其权重会增加网络的生命周期。

4 结束语

本文在DEEC算法的基础上提出了一种改进的能量异构分簇算法RDEEC:通过设定双能量阈值,保护了低能量节点,提高了高能量节点的利用率,延长了网络生命周期;引入边缘度,使簇头选取过程中充分考虑了节点的位置因素;改进了入簇机制,使入簇机制更加合理。通过对小面积检测环境和大面积检测环境的仿真结果分析,RDEEC算法在网络生命周期、网络数据传输、网络能量损耗方面比DEEC算法更加优秀,且在大面积检测环境下比DEEC算法改善明显,为100 m×100 m到500 m×500 m范围内检测区域提供了一种更加节能有效的路由算法;但该改进算法不适用于500 m×500 m以上的检测环境,后续研究将利用多跳机制解决远距离传输问题,与RDEEC算法实现优势互补。

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

[2] 龙胜春,卢定乾,池凯凯. 基于同构传感器网络的能量空洞避免策略[J]. 传感技术学报,2016,29(1):103-108.

[3] 司海飞,杨忠,王珺. 无线传感器网络研究现状与应用[J]. 机电工程,2011(1):16-20,37.

[4] 彭蕾,吕敬祥,刘秋平. 大规模无线传感网络的混合LEACH协议研究[J]. 传感技术学报,2016,29(11):1737-1741.

[5] Chauhan T,Nayyer M. Review on Energy Efficient Protocol Based on LEACH,PEGASIS and TEEN. 2016 International Conference on Emerging Trends in Communication Technologies(ETCT),Dehradun,India,2016:1-5.

[6] Tiwari T,Roy N R. Modified DEEC:A Varying Power Level Based Clustering Technique for WSNs. 2015 International Conference on Computer and Computational Sciences(ICCCS),Noida,2015:170-176.

[7] Divya C,Krishnan N,Krishnapriya P. Modified Distributed Energy-Efficient Cluster for Heterogeneous Wireless Sensor Networks. 2013 IEEE International Conference ON Emerging Trends in Computing,Communication and Nanotechnology(ICECCN),Tirunelveli,2013:611-615.

[8] Shaji M. Distributed Energy Efficient Heterogeneous Clustering in Wireless Sensor Network. 2015 Fifth International Conference on Advances in Computing and Communications(ICACC),Kochi,2015:30-134.

[9] 潘巨龙,闻育. 无线传感器网络的异构性研究[J]. 航空计算技术,2007(2):124-126,130.

[10] 蔡海滨,琚小明,曹奇英. 多级能量异构无线传感器网络的能量预测和可靠聚簇路由协议[J]. 计算机学报,2009(12):2393-2402.

[11] 魏春娟,杨俊杰,张志美. 一种分布式能量有效的无线传感器网络分簇路由算法[J]. 传感技术学报,2013,26(7):1014-1018.

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

[13] 梁英. 基于能量异构网络环境下的WSN优化成簇算法[J]. 沈阳理工大学学报,2009(2):57-61.

李安超(1993-),男,山东人,硕士研究生,2016年于长春理工大学获得学士学位,主要研究方向为无线通信,WSNs技术,lac1105@163.com;

陈桂芬(1964-),女,吉林人,博士,教授,1991于吉林工业大学获得硕士学位,2009年于长春理工大学获得博士学位,2004年～2005年作为访问学者在华沙理工大学学习,主要从事光通信技术、信息理论及编码技术、信息检测及信号处理方面的研究,chenguif@163.com。

AnImprovedClusteringRoutingAlgorithmforEnergyHeterogeneousWirelessSensorNetworks*

LIAnchao,CHENGuifen*

(School of Electronic and Information Engineering,Changchun University of Science and Technology,Changchun 130022,China)

As core technology of wireless sensor net,routing algorithm plays a crucial role in prolonging net life circle and improving net efficiency. The article puts forward an improved energy isomerism cluster routing algorithm aiming at troubles of distributed energy effective cluster algorithm in lack of consideration of node position,node protection and insufficient utilization. The algorithm introduces concept of margin degree,so as to enable node near to base station act as cluster head in priority,reduce net energy consumption;establishes double-energy threshold value,improves node energy utilization,prolongs node life circle;and the article puts forward more reasonable in-cluster mechanism under the comprehensive consideration of position distribution of node,cluster head and base station. The simulation results showed that compared with former algorithm,the net life circle of improved algorithm increased 18.7% to 36.2%,24.4% to 66.5% under the condition of small area detection(10 m×10 m to 100 m×100 m)and large area detection(100 m×100 m to 500 m×500 m).

heterogeneous wireless sensor networksrouting protocol;edge degree;dual energy threshold;join cluster mechanism

TN92

A

1004-1699(2017)11-1712-07

项目来源:吉林省发改委项目(2016C089)

2017-05-04修改日期2017-06-28

10.3969/j.issn.1004-1699.2017.11.017