深井无线传感器网络非均匀分簇路由协议*

余修武,刘 琴,刘 永,李向阳,梁北孔(.南华大学环境与安全工程学院,湖南 衡阳 4200;2.金属矿山安全与健康国家重点实验室,安徽 马鞍山 243000;3.湖南省铀尾矿库退役治理技术工程技术研究中心,湖南 衡阳 4200)

为保证国民经济的持续发展,需要对矿井进行深部开采。然而随着井下开采工作的推进,其环境也愈加恶劣,存在高温、高湿、通风性差等问题,因此在井下建立完善的的安全监控监测系统是十分必要的。有线安全监控系统并不能很好地适应此复杂环境,一是系统易腐蚀,设备遭到破坏,会导致整个系统瘫痪;二是需要铺设较多的电缆,使得整个系统的成本偏高。

无线传感器网络[1-3]WSNs(Wireless Sensor Networks)是一种自组织网络,能实时监控对象,且具有强抗毁性,灵活易于扩展,可以部署在复杂恶劣甚至是危险的环境中,因此将WSNs应用于深井安全监控系统中[4-5],可以保障网络通信的有效性与可靠性。无线传感器节点一旦部署就无法充电或进行电源更换,如何有效均衡能耗,延长网络寿命就是WSNs路由协议设计的关键[6-7]。

基于分簇的层次式路由方式能有效减少节点对Sink节点的数据转发次数,减少网络冗余信息,降低能耗,延长网络生存周期。LEACH算法[8-9]是最早采用均匀分簇的路由算法,各个节点等概随机担任簇首,但离Sink节点近的簇首能量消耗较快,易造成能量空洞。PEGASIS协议[10]是对LEACH算法的改进,减小节点间的平均通信距离来降低网络通信能耗,然而却不能对低能量的节点进行筛选。EEUC算法[11]引入了非均匀竞选半径的概念,使靠近Sink节点的簇规模相对较小,这样Sink节点附近簇首转发数据的能耗相应降低,该算法在一定程度上可以解决簇首能耗不均导致的“热区”问题。李鉴等[12]提出了一种能量均衡的非均匀分簇的路由算法(EBUC-M),根据新的阈值公式来选择簇首,以此均衡簇首间能耗。

根据深井WSNs路由的特点以及应用需求,提出一种无线传感器网络非均匀分簇的路由协议UCRP(Uneven Clustering Routing Protocol)来均衡簇首间的能耗,并保证数据传输的有效性与可靠性,延长网络生存周期。

1 网络与能耗模型

1.1 网络模型

根据深井巷道线型特征,进行WSNs布设时采用人工部署,节点一旦部署就不再移动。假设有N个无线传感器节点均匀布设在长为L,宽为M的矩形监测区域内(L≫M),根据文献[13],网络遵从以下原则:①Sink节点位于巷道的出口或入口处,其能量和计算能力不受限制且始终处于苏醒状态;②节点布署在巷道内,且都是同构的,能感知自己的剩余能量,并且每个节点具有唯一ID;③可根据距离来调整安装好的节点的发射和接收功率。

1.2 无线通信模型

能量消耗[14]是设计WSNs路由算法时的重要部分,无线通信模型如图1所示。

图1 无线通信模型

无线信号能量消耗模型由发送电路能耗和发送放大电路能耗两部分组成。当节点发送l bit数据时,节点接收1 bit信息所需能耗为Ee,发送放大电路能耗与发送距离d有关,在自由空间中n通常取为2,在多径衰落区域n通常取4。发送放大模块消耗的能量系数为εm,节点每次发送数据能耗ETx和接收数据能耗ERx分别如式(1)所示:

ETx=lEe+lεmdn
ERx=lEe

(1)

信号在深井巷道中多径效应尤为明显,应采用多径衰减信号模型,即n应取4。

2 UCRP协议

整个无线网络的能量消耗主要在集中在信息转发阶段,均衡此阶段的能耗就尤为重要。UCRP协议按照周期采集数据(即轮循环机制),每一轮分为2个阶段:①非均匀分簇阶段。传感器节点考虑自身到Sink节点的距离并计算出距离因子,保证数据传输路径的最优性,同时考虑节点的剩余能量因子,使剩余能量高的候选簇首担任最终簇首;②数据转发阶段。分为簇内单跳和簇间多跳通信两部分,当簇首与Sink节点距离小于一定范围时,就可以直接将数据发送至Sink节点。

首先介绍与UCRP协议相关的定义。

定义1距离因子。距离因子df表示节点当前位置与Sink节点的位置关系,0≤df≤1。

定义2剩余能量因子。剩余能量因子Er(i)表示节点i当前剩余能量与簇内平均剩余能量的关系,0≤Er(i)≤1。

定义3全网平均剩余能量估计。对分布式路由算法而言统计全网的平均剩余能量是非常困难的,因此只能对其进行一个粗略的估计,如式(2)所示:

(2)

式中:N表示节点数,E0为全网初始总能量E0=0.5N,r为仿真轮数,Erd为每一轮消耗的能量。

2.1 非均匀分簇阶段

非均匀分簇阶段包括簇首竞选、非均匀竞争半径和簇的形成。

①簇首竞选

(3)

式中:ω为调节参数,ω∈[0,1],E(i)表示节点i当前剩余能量。该权值W综合考虑了节点剩余能量以及距离因子。节点的剩余能量越高,权值也越大;距离因子越大,就越容易成为簇首。

②非均匀竞争半径

簇首节点越靠近Sink节点,需要承担转发数据的任务越重,这样会引起簇首节点过早死亡而导致的“热区”问题。为了避免这种情况的发生,UCRP协议设计时,使距离Sink节点近的簇规模减小,簇数增多,这样可以由多个簇首分担路由数据至Sink节点,为此需要为簇首节点设定竞争半径Rc。假设最大的竞争半径为Rmax,这里先给出邻居节点和邻居节点数的定义。

定义4节点si的最大竞争半径Rmax内的所有其他节点称为邻居节点。si的邻居节点集合如式(4)所示:

si.Vic={sj|d(si,sj)

(4)

邻居节点数为Num=|si.Vic|。

簇首根据距离因子、剩余能量因子和邻居节点数计算其竞争半径Rc,如式(5)所示:

(5)

式中:c1、c2、c3为调节参数,用来调节距离、能量和节点密度对竞争半径的影响程度,且c1+c2+c3=1。由于簇首是各个簇中剩余能量最大的节点,故调节参数c2取值可以较小。c1、c3的取值则需要综合考虑基站的位置和网络的范围大小,仿真中c1和c3取值相等。

③簇的形成

簇首确定后,在其竞争半径内广播信息,等待成员节点的加入。普通节点接收信息强度并确定自身与簇首的近似距离,选择信息经过最短距离的簇首加入。

簇的形成过程也是为了均衡能耗,让更多的节点加入到剩余能量因子较大的簇首中,同时还需考虑信息的传输距离。图2给出UCRP的路由协议示意图,其中大小不等的圆表示簇首节点的非均匀竞争半径,带箭头的线表示簇首间的多跳数据转发。

图2 UCRP的路由协议

2.2 数据转发阶段

UCRP协议采用单跳与多跳的相结合的路由方式转发数据。簇首先采集簇内成员的信息并且进行数据融合,然后进行数据转发,选择距离优化的路径进行发送。

簇内通信采取单跳路由方式,成员节点直接将数据发送至所属簇的簇首,减少路径能量损耗;簇间通信采用多跳路由方式,一是可以减少链路总能耗,二是可以有效避免低能量节点成为簇首,过早耗尽网络寿命;当簇首与Sink节点距离小于一定范围时,就可以直接将数据传输至Sink节点。

非均匀分簇可以有效均衡节点能耗,平衡网络负载。根据距离因子、剩余能量因子和节点密度成簇,使剩余能量较高的节点成为簇首,同时使得簇首通信代价最小化。

2.3 算法分析

①在UCRP协议中,网络广播信息量的复杂度为O(N)。

证明:在非分均匀分簇阶段,共有RT个候选簇首,因此需要广播了RT条Compete_Msg,竞选成功的候选簇首发出成功信号,设有n个簇首,那么需要广播n条Head_Msg和n条Ch_Adv_Msg,而其余簇成员节点则广播R-n条Join_Msg;在簇间路由建立时,n个簇首需要广播n条Route_Msg,因此网络的总信息开销如式(6)所示:

RT+2n+R-n+n=(T+1)R+2n

(6)

所以,UCRP协议信息量的复杂度为O(N)。

②Rmax、c1、c2、c3对路由算法的影响。

Rmax的取值影响生成簇的数量。Rmax越大,簇半径也随之增大,则生成簇的数目减少。c1、c2、c3的取值体现了距离、能量和节点密度对簇半径的影响,当三者变化时,簇半径也要明显变化。

3 仿真实验与参数分析

3.1 仿真实验

为了验证UCRP协议对深井巷道的监测应用效果,假定在一个L×M为1 000 m×10 m的巷道内,采用MATLAB进行仿真测试,与LEACH、EEUC以及EBUC-M算法与UCRP算法进行比较,仿真参数设置如表1所示。

图3对比了4种协议的网络生存时间变化的情况。从图3可以看出,UCRP相比于其他3中协议有较长的网络生存时间。而UCRP与EBUC-M的网络生存时间相差不大,主要是这两种算法都构造了新的簇首选举公式来选取簇首,降低了簇首转发数据能耗,而UCRP的网络生存时间略优于EBUC-M是由于UCRP协议选取簇首时不仅对节点剩余能量进行考虑,还加入了距离因子,保证了簇首选择的最优性。

表1 仿真参数

图3 死亡节点与生存周期关系

图4 节点平均剩余能量与生存周期关系

3.2 参数分析

UCRP协议中所生成簇的数目和规模由Rmax和c1、c2、c3共同决定。Rmax决定了网络中簇的最大规模。为确定Rmax对算法的影响,令Rmax从70按步长5增加到110时,第1个节点死亡时间(轮数)的变化,如图5所示。

图5 第1个节点死亡时间随Rmax变化图

从图5可知,当Rmax=90 m时,第1个节点死亡时间(轮数)值最大。由于在深井下信号多径效应明显,为了达到较好数据传输,保证数据可靠性与实时性,需要合理布设传感器节点。当布设节点数较少时,可能会导致得到的数据不可靠;布设节点过多时,会增加传感器设备的成本,也会产生较多冗余数据,造成网络带宽拥堵,使得距离Sink节点近的簇首过早死亡,降低网络生存周期。

调节参数c1、c2、c3的取值决定了簇规模大小的非均匀程度,综合考虑3方面因素(距离、能量和节点密度)的权重。实验中c1、c2、c3的取值,观察第1个节点死亡时间(轮数)随之变化的情况,结果如表2所示。

表2 第1个节点死亡时间随参数c1,c2,c3变化的趋势

从表2可知,当c1=0.4、c2=0.2和c3=0.4时,第1个死亡节点死亡时间(轮数)最大,因为此时网络分簇的非均匀程度最优,节点间的能耗较为平衡。

4 结束语

根据深井巷道线型拓扑结构,提出了一种非均匀分簇路由协议,利用一个权值公式来进行簇首竞选,权值越大越易成为簇首,有效均衡了网络节点能耗;数据传输采用单跳与多跳结合的路由方式,不仅减少了链路能耗,还能平衡负载。仿真实验表明,UCRP协议具有较好的网络鲁棒性,能有效降低节点能量开销,均衡网络能耗,延长网络寿命。

虽然本算法在仿真实验环境下有较好的性能,但实际环境中存在异构网络和移动的节点,为了改善网络能耗,需要根据深井巷道的实际情况,对算法做出合理改进。