基于最小生成树的非均匀分簇路由协议*

廖福保,张文梅

(1.广东农工商职业技术学院计算机系,广州 510507;2.广东农工商职业技术学院机电系,广州 510507)

基于最小生成树的非均匀分簇路由协议*

廖福保1,张文梅2*

(1.广东农工商职业技术学院计算机系,广州 510507;2.广东农工商职业技术学院机电系,广州 510507)

针对无线传感器网络中利用分簇技术,簇首到Sink节点通信采用多跳路由方式容易引起“能量空洞”的问题,提出了基于最小生成树的非均匀分簇路由协议。该协议在簇首选举阶段,以节点剩余能量、节点度、节点能量消耗速度为权重计算簇首竞争等待时间,选用簇首竞争等待时间小的节点为簇首,以均衡能量;簇形成后,以剩余能量、簇间的距离和能量消耗为参数构建基于最小生成树的最优传输路径通过多跳方式将数据发送到Sink节点。仿真结果表明,该路由协议能有效均衡能耗,延长网络生命周期,延缓“能量空洞”的形成。

无线传感器网络;非均匀分簇;能量均衡;最小生成树

无线传感器是由大量的传感器节点和一个或多个Sink节点组成,传感器节点采集数据上传到Sink节点。这些传感器节点采用电池供电,能量有限且不能被补充。因此如何降低传感器能耗,在网络层提供节能算法是无线传感器网络研究的热点[1-3]。

有研究表明先将传感器进行分簇,通过簇首多跳方式上传数据到Sink节点有利于节省能量[4-5]。然而采用多跳方式,离Sink节点越近的传感器,由于要转发其他簇首数据,其能量消耗越快,从而形成“能量空洞”,这时其他传感器节点将不能上传数据到Sink节点,造成能量的浪费和网络生命周期的缩短。

为解决“能量空洞”问题,很多研究者提出了不同的簇首选举和多跳路由选择方法。文献[6]提出的EEUC算法、文献[7]提出的DEBUC算法采用非均匀分簇,靠近Sink节点的簇小、簇内节点少,可以减少簇内能量消耗而节省能量用于转发数据,从而能有效均衡能量消耗,延长网络生命周期,但两个算法都是根据概率和门限值来选举簇首,并不能确保选举出来的簇首最优。文献[8]提出了EBUCA算法,也采用非均匀分簇,该算法根据剩余能量和节点密度来设置簇首选举的阈值,并没有考虑能量消耗速度问题。

另外,在多跳路由的选择方面,文献[9-10]采用最小生成树算法来进行路径选择,但在构造最小生成树时只考虑了簇首的剩余能量或到Sink节点的距离。

基于以上存在的问题,本文提出了基于最小生成树的非均匀分簇路由协议。协议在簇首选举时以节点的剩余能量、节点度、节点能量消耗速度等参数构建节点的簇首竞争时间,竞争时间短的节点获得簇首的机会大。簇首选举完成后,以簇首剩余能量、簇间的距离、簇首能量消耗为参数构造出以Sink节点为根节点的最小生成树。数据传输时,簇内数据传输采用单跳方式,簇首到Sink节点的通信通过最小生成树组织的路由采用多跳方式。该算法能较好地均衡各个节点的能耗,从而延长传感器网络生命周期。

1 相关模型

1.1 网络模型

本文假定各个传感器节点随机分布于监控区域,且具有如下特征:①节点部署后不再移动且能量不能补充,Sink节点位置固定且唯一,能量也不受限;②节点能够根据接收的信号强度计算发出信号节点到本节点的距离,且可以自由调整发射功率;③传感器节点初始能量相同,具有相同的通信和数据处理能量;④传感器节点都在Sink节点的通信范围之内;⑤每个节点都有唯一的标识ID。

1.2 能耗模型

由于无线传感器网络中节点通信所耗的能量远大于其他的能耗[11],本文采用与文献[12]一样的无线通信模型,节点发送k比特数据所消耗的能量如下:

(1)

ERx(k)=k×Eelec

(2)

2 基于最小生成树的非均匀分簇路由协议

与LEACH协议类似,本文协议也采用“轮”方式,每轮分为簇建立阶段和数据传输阶段。在簇的建立阶段,以剩余能量、节点度、节点能量消耗速度等因素计算簇首竞争等待时间,采用时序的方式选择簇首。在数据传输阶段,以簇首剩余能量、簇首能量消耗和簇间距离为权重构建基于最小生成树的最优传输路径。

2.1 簇的形成

把在节点半径Ri范围内的所有其他节点当作该节点的邻居节点,Ri通过式(3)计算得到。

(3)

每个节点保存一个邻居节点表以存储邻居节点的相关信息,如表1所示。

表1 节点的邻居表内容

开始阶段,Sink节点先全网广播PAR_MSG消息,每个传感器节点根据接收到的消息强度计算出该节点到Sink节点的距离d(i,DS),然后根据式(3)计算出节点半径R。

每轮开始时,进入邻居节点信息获取时段(事先规定邻居节点信息获取的时长为T1),每个传感器节点以半径Ri广播消息Comp_MSG,该消息包括有节点ID和剩余能量e、节点能耗ec。

当T1时间到,邻居节点表更新完毕,每个节点根据邻居节点表计算出邻居节点平均剩余能量Eavg、邻居节点度(邻居节点个数)m、平均能耗ECavg、能耗速度Vec。节点能耗、平均剩余能量、平均能耗和能耗速度的计算公式如式(4)～式(7)所示。

ec=er-1-er

(4)

(5)

(6)

Vec=eci/ECavg

(7)

式(4)中:er为第r轮节点剩余能量,er-1为第r-1轮节点的剩余能量。由式(7)可知能耗速度为该轮中节点消耗的能量与平均消耗的能量之比。

然后进入簇首选举时间,每个节点根据式(8)计算自己的簇首竞争时间t。

(8)

式中:α为一个在(0,1)之间的随机实数值,表示剩余能量和能耗速度的权重;T2为事先规定的簇首竞争时间。如果能耗速度过快,簇首会过早死亡,也会造成能量空洞,因此本文引入能耗速度,并作为簇首竞争时间的主要参数。

从式(8)可以看出,簇首竞争时间t由Eavg/ei和Vec决定。Eavg/ei表明节点相对于邻居节点的剩余能量越高,被选中作为簇首的机会越大,保证有更多的能量用于簇间多跳数据传输。Vec作为簇首竞争时间的主要参数,如果第r轮能耗速度Vec小,下一轮该节点簇首竞争时间t小,被选中作为簇首的机会就大;如果第r轮能耗速度Vec大,下一轮该节点簇首竞争时间t大,被选中作为簇首的机会就小,从而可以避免能耗速度快的节点成为簇首造成能量空洞现象。

在本协议中,如果一个节点在t时刻到来前没有收到邻居节点的Suc_MSG消息,则该节点在节点半径Ri范围内广播Suc_MSG消息,宣布簇首选举成功。如果一个节点在t时刻到来前收到了邻居节点的Suc_MSG消息,则广播竞选失败的消息Fai_MSG,放弃簇首竞选,进入休眠状态。

当T2时间到,簇首选举完成,进入普通节点加入簇的时间,非簇首节点选择邻居节点中第1个被选簇首发出JOIN_MSG消息,申请加入到该簇,并在邻居节点表中删除其他节点。对于簇首节点,接收来自邻居节点的JOIN_MSG消息,将不在本簇内的邻居节点从邻居节点表中删除,至此该轮的分簇过程完成。

图1 簇首选举流程图

本文在非均匀分簇的基础上进行簇首选择,网络中所有节点都参与簇首竞争,采用时序的方式选择簇首。簇首选举流程如图1所示。

具体描述如下:

①Sink节点先全网广播PAR_MSG消息,网络中各节点收到PAR_MSG消息,根据式(3)计算出节点半径Ri。

②在T1时段内,各节点以半径Ri广播消息Comp_MSG,该消息包括有节点ID和剩余能量e、节点能耗ec,每个节点根据收到的Comp_MSG消息更新邻居表。

③T1时间到,各节点根据邻居表计算平均剩余能量Eavg、邻居节点度(邻居节点个数)m、平均能耗ECavg、能耗速度Vec,最后计算出簇首竞争时间ti。

④进入T2时间段,对于节点i有:

⑤if当前时间

⑥if收到邻居节点j的簇首成功消息Suc_CLU

⑦节点i广播竞选失败的信息Fai_CLU

⑧节点i进入休眠状态

⑨end if

⑩end if

本协议分簇算法将整个网络划分为非均匀的多个簇,靠近Sink节点的簇半径更小,有利于均衡能耗;簇首竞争时间考虑了剩余能量、节点度、节点能量消耗速度等因素,能够保证选举出来的簇首综合性能最优。

2.2 簇间路由树构造

分簇完成后,为保证簇首间的跳转,各簇首以2Ri为半径广播簇首消息CLU_MSG(ID,e,ec),并收集其他簇首广播的消息,计算簇首间距离,修改路由表信息。

簇间路由以Sink节点为树根,采用最小生成树方式来组织簇首到Sink节点的通信,通过多跳方式将数据传输到Sink节点。开始时将每个簇首抽象为点,把相邻簇首用边连接起来,把无线传感器网络构造为一个带权的连通图G=(V,E),其中V是点集(包括所有簇首,不含Sink节点),E为边集。

点i到点j的边的权值wij,综合考虑两者间的距离、簇首j剩余能量和簇首j的能量消耗,其计算公式如下:

(9)

式中:wij为簇首i到簇首j的边的权值,dij为簇首i到簇首j之间的距离,ej为簇首j剩余能量,ecj为簇首j的能耗,ρ为可变参数。为保证数据能逐步往Sink节点传递,簇首j到Sink节点的距离大于或等于簇首i到Sink节点的距离,则wij的值为无穷大。从式(9)中可以看出,wij值由dij、ej和ecj决定,簇首j剩余能量低、距离远、能耗又大时,wij的取值越大,则簇首被选为数据转发的概率越小,从而该簇首可以节省能量,数据通信时又可以节省通信能耗,延长生命周期,达到整个网络能量均衡。

每轮簇间路由采用最小生成树方式来构建,设T为最小生成树边的集合,具体描述如下:

①将到Sink节点距离d(i,DS)≤d1的簇首添加到集合U中,该部分簇首的汇聚数据直接传递给Sink节点,设置这部分簇首到Sink节点的边的权值为0并添加到集合T中。

②计算G=(V,E)中所有边的权值。

③while(U!=V)

④从u∈U,v∈V-U的边中选取权值wuv最小的边,将其加入到T,将簇首v加入到U

⑤endwhile

最后的生成树MT=(U,T)即为连通图G的最小生成树。各簇首根据最小生成树MT,调整发射功率,调整为能够到达其最小生成树的所有一跳邻居,从而节省能耗。

2.3 数据通信

簇首选举和簇首路由树构建完成后,进入数据通信阶段。簇内节点采用TDMA方式将数据传输到簇首,然后簇首将数据融合,最后根据构建的最小生成树,以多跳通信方式将数据传输到Sink节点。

2.4 算法分析

假设在无线传感器网络中的节点数共有N个,生成的簇首节点有H个,下面分析本文算法的消息复杂度。

在簇的形成算法中,Sink节点广播PAR_MSG信息,共1条;每个节点以半径R广播消息Comp_MSG,共N条;竞选成功的节点发送Suc_CLU消息共H条,竞选失败的节点发送Fai_CLU消息共N-H条;竞选失败的节点发送JOIN_MSG消息加入到最近的簇首,共N-H条。

簇间路由树构造算法中,簇首以2Ri为半径广播簇首消息CLU_MSG共H条。因此每轮网络中消息总开销为:

1+N+H+(N-H)+(N-H)+H=3N+1

即消息复杂度为O(N),说明本文算法的消息开销较小,能量高效。

3 仿真实验与结果分析

本文协议选用OPNET进行仿真实验,与EEUC协议、CSMST协议进行比较。在实验中预先设定传感器节点数量100个,传感器节点随机分布于100 m×100 m的矩形区域中,Sink节点位于中央位置。各仿真参数:Eelec=50 nJ/bit,εmp=0.001 3 pJ/(bit·m4),εfs=10 pJ/(bit·m2),初始能量e=0.5 J,数据包大小600 bit。为了比较,本实验取c=0.5,α=0.4,d1=10 m,而ρ=0.5,簇首数据融合的能耗忽略不计。

3.1 网络生存周期

图2为网络中总存活节点数随轮数的变化情况,从图2可以看出出现首次死亡节点的轮数本文协议比EEUC和CSMST都滞后;从整个网络的存活时间看,本文协议存活了1 620轮左右,相比EEUC协议提高了约450轮、比CSMST算法提高了约200轮。本文协议在选举簇首不仅考虑剩余能量,还考虑节点能量消耗速度等因素,根据时序方式选择簇首;在数据传输阶段,EEUC考虑剩余能量进行多跳传输,CSMST算法考虑剩余能量和节点传输能耗构造最小生成树多跳传输,而本文算法综合考虑中继簇首剩余能量、簇间距离和能量消耗等因素构造最小生成树寻求最优路由,节点死亡速度要慢很多,能有效延长网络生存周期。

图2 存活节点随运行轮数变化对比

图3 网络总能耗随运行轮数变化对比

3.2 网络能耗

图3为网络消耗总能量随轮数的变化情况,从图中可以看出3种算法能耗有异,开始都成线性状态,但本文协议能耗更平缓,能耗速度更慢。

在相同轮次下,本文协议的能量消耗比EEUC协议和CSMST都明显更低,本文算法在以剩余能量和能耗速度进行非均匀分簇,然后考虑剩余能量、簇间距离和能量消耗等因素构造最小生成树寻求最优路由传输数据到Sink节点,能量消耗要慢很多,而且整个网络的生命周期更长。

4 结语

本文借鉴非均匀分簇的思想计算节点半径,提出了基于最小生成树的非均匀分簇路由协议,该协议以剩余能量、节点度、节点能量消耗速度作为权重计算簇首选举时间,通过时序方式选择簇首;在簇首与Sink节点的数据通信阶段采用多跳方式,综合考虑中继簇首剩余能量、簇间距离和能耗建立最小生成树,找到一条最优的数据传输路径,减少通信能耗。仿真结果表明,本文协议可以有效均衡网络能耗,延长网络生命周期。

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

[2] 李建洲,王海涛,陶安. 一种能耗均衡的WSN分簇路由协议[J]. 传感技术学报,2013,26(3):396-401.

[3] 苏金树,郭文忠,余朝龙,等. 负载均衡感知的无线传感器网络容错分簇算法[J]. 计算机学报,2014,37(2):445-456.

[4] Mhatre V,Rosenberg C. Design Guidelines for Wireless Sensor Networks:Communication,Clustering and Aggregation[J]. Ad Hoc Networks,2004,2(1):45-63.

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

[6] 李成法,陈贵海,叶懋,等. 一种基于非均匀分簇的无线传感器网络路由协议[J]. 计算机学报,2007,30(1):27-36.

[7] 蒋畅江,石为人,唐贤伦,等. 能量均衡的无线传感器网络非均匀分簇路由协议[J]. 软件学报,2012,23(5):1222-1232.

[8] 卢先顺,王莹莹,王洪斌,等. 无线传感器网络能量均衡的非均匀分簇算法[J]. 计算机科学,2013,40(5):78-81.

[9] 陆晶,马悦,吴晓军. 一种基于最小生成树的非均匀分簇路由算法[J]. 小型微型计算机系统,2012,33(10):2293-2296.

[10] 张明才,薛安荣,王伟. 基于最小生成树的非均匀分簇路由算法[J]. 计算机应用,2012,32(3):787-790.

[11] Estrin D. Wireless Sensor Networks Tutorial Part Ⅳ:Sensor Network Protocols//Proc of the ACM Mobil Computing and Networking. New York:ACM,2002. 1-5.

[12] Heinzelman W,Chandrakasan A,Balakrishnam H. Energy-Efficient Communication Protocol for Wireless Microsensor Networks[C]//Proc of the 33rd Conf on System Sciences. Piscataway. NJ:IEEE. 2000:3005-3014.

廖福保(1976-),男,硕士,副教授,研究方向为计算机应用、无线传感器网络与路由,fbliao2000@163.com;

张文梅(1978-),女,硕士,副教授,研究方向为计算机应用、物联网,zwm200718@126.com。

UnevenClusteringRoutingProtocolBasedonMinimumSpanningTree*

LIAOFubao1,ZHANGWenmei2*

(1.Department of Computer,Guang Dong AIB Polytechnic College,Guangzhou 510507,China; 2.Department of Mechanics and Electronics,Guang Dong AIB Polytechnic College,Guangzhou 510507,China)

When the data is transmitted from cluster heads to Sink node via multi-hop communication,the energy hole may be caused. In order to solve the problem,an uneven clustering routing protocol based on minimum spanning tree is proposed. In the cluster heads selection stage,the protocol calculates the cluster head selection time of each node based on the residual energy,the node degree and the energy consumption rate. The protocol selects the cluster head by the cluster head selection time. In the stage of routing establishment,the protocol builds the optimal transmission path based on minimum spanning tree,according to the residual energy of cluster heads,the distance between cluster heads and energy consumption. The cluster heads send the data to Sink node through the nodes of the tree by multi-hop. The simulation shows that the routing protocol can effectively balance energy consumption,prolong the wireless sensor network survival period and delay the forming speed of energy hole.

wireless sensor networks;unequal clustering;energy balance;minimum spanning tree

项目来源:科技部国家星火计划项目(2013GA780003)

2017-02-09修改日期:2017-04-13

TP393

:A

:1004-1699(2017)09-1412-05

10.3969/j.issn.1004-1699.2017.09.019