基于蜂窝虚拟网格的WSN混合多跳分簇路由算法*

余修武,胡沐芳,刘 琴,3,刘 永

(1.南华大学环境与安全工程学院,湖南 衡阳 421001;2.湖南省铀尾矿库退役治理技术工程技术研究中心,湖南 衡阳 421001;3.金属矿山安全与健康国家重点实验室,安徽 马鞍山 243000)

无线传感器网络WSNs(Wireless Sensor Networks)应用广泛,能应用于海洋环境监测、矿山监测、医疗卫生监测等领域。而在无线传感器网络中节点是靠蓄电池进行供电的,所以整个网络使用寿命是有限的[1-2]。在WSNs关键技术中,路由技术占有重要地位,在该项技术中节点的能量多在数据传输过程中损耗且节点能耗不均匀[3-4]。因此,降低并均衡网络能耗是在进行路由设计时考虑的首要问题。基于地理位置的分簇路路由算法相对于其他平面路由来说,具有很强的扩展性和高效的数据融合性,能降低通信能耗[5]。而蜂窝式虚拟划分方案较其他多边形的虚拟单元格在网络覆盖性方面占有很大的优势,有利于节点调整信号发射功率[6-7]。大量学者以网格模型和分簇路由为基础提出了许多WSN路由协议。崔灿等人[8]利用混合压缩感知理论优化正六边形混合路由协议。同时利用数据传输次数和压缩比例以及分簇的大小,确定最优成簇数量,从而提高网络利用效率。刘壮等人[9]提出一种可调节网格改进的跨区域边界无状态贪婪路由协议。解决边界区域能量不均衡问题,但是该算法在簇头节点选举时并没有给出明确的选举机制,也没考虑簇头节点能耗问题。文献[10]提出一种区域划分的多跳分簇路由算法,将监测区域划分为等间距的圆环然后等夹角的二次划分区域。这种非均匀分区方式可以均衡网络能耗,延长网络生命周期。文献[11]提出的改进型分簇路由算法,考虑节点剩余能量以及与基站的距离因素优化簇头选择机制。引入超级簇头作为普通簇头与基站的通信中继,这在一定程度上缓解了能量均衡的问题,但未考虑到簇内节点的非均匀分布及由此带来的能耗不均衡问题。文献[12]提出EB-GAF算法,该算法引入均匀度模型,通过二次划分使得单元内节点分布均匀。同时在选举簇头节点时考虑节点的剩余能量和节点位置,利于选举出最优簇首节点,提高网络有效性。文献[13]提出了一种虚拟网格分簇路由算法(CRVB)。首先通过计算得出最优格距,然后节点自组织成簇,簇内节点构建近优生成路由树,簇首节点采用多跳与基站通信。仿真实验表明,CRVB算法能减少通信时延减少网络能耗。但由于CRVB算法采用正方形划分网格,导致簇间通信能耗较大,存在一定的弊端。

本文提出了一种基于蜂窝虚拟网格式混合多跳分簇的路由算法IHCRA(Improved Hexagon Cluster Routing Algorithm)。即把监测目标区域划分成若干个正六边形虚拟单元格。这些区域中的节点自组成簇,在簇头选举时综合考虑簇头剩余能量以及簇头位置与单元格网络扑拓区域质心的角度比和距离比,以此来均衡簇头节点的能量消耗和抑制孤立点的产生。在簇内通信时采用混合跳模式,在保证通信质量的情况下,提高网络的生命周期。

1 系统模型

传统GAF路由算法是将监测区域划分为多个正方形,如图1(a)所示。根据分析该结构只与4个虚拟格有公共边,而在正六边形虚拟网格中,每个单元格都与附近6个单元格相邻。并且正六边形虚拟网格中心节点到相邻格的距离都相等,说明与图1(a)模型相比图1(b)模型具有更好的网络覆盖性。根据相关资料分析,相比正方形的虚拟单元格,正六边形虚拟网格还在单跳覆盖面积和单元格内节点总数方面占有优势。

图1 虚拟网格模型结构

所以在IHCRA算法中,将监测区域划分为多个正六边形,节点随机布置在监测区域内。划分后的区域都将产生一个G-ID(Grid-ID),节点利用自身定位坐标得出所属的G-ID。WSNs中六边形网格通信模型如图2所示,设每个六边形的边长为R。现假设监测区域内节点具有如下性质:①普通节点和Sink节点一旦布置就固定,具有唯一的N-ID(node-ID)且随机布置在监测区域内。②对于所有的普通节点能量有限、相同,而Sink节点和基站能量不受限。③所有节点能够存储数据,具有相同的计算、转发功能且各节点地位相同都能参与簇头竞争。④区域内节点通过定位算法已知自身位置,并能计算之间距离。⑤区域内节点能够周期性的采集数据,并能保证数据成功发送至基站。

图2 传感网络模型

2 IHCRA路由算法

2.1 虚拟分区

通过几何约束计算易判断出平面区域内节点所属单元格。例如,判断某个节点(xi,yi)是否在该正六边形内。首先将正六边形划分为如图3所示的三段图形。

在该正六边形网格区域内,设6个顶点的坐标依次为(a,b)、(c,b)、(d,e)、(c,f)、(a,f)、(g,e)。由于区域划分是正规图形,则易得出上述顶点的坐标。同时,由节点定位算法易得出普通节点坐标位置为(xi,yi),那么判断节点的G-ID就变成对比三段分段函数值的大小。区域内所有节点通过计算依次判断出所属单元格。单元格内节点自组成簇,减少了成簇复杂度,降低能耗。

图3 节点区域分区

2.2 簇头选举算法

传感器节点向各邻居节点发送报文消息,交换各自的N-ID、G-ID和所处状态。节点相同的G-ID就将其N-ID记录在节点列表中,若不相同,就将消息丢弃。区域内各节点设置定时器,长度设置为TD。在定时器TD内,如果节点接收到其他节点竞选簇头成功的消息,则说明该节点竞选簇头节点失败,将自动进入休眠状态。在休眠期间只将自身的状态和监测数据上传给簇头节点。如果该节点未收到区域内节点发送簇头选举成功消息,则该单元内簇头节点就为此节点,并自动开启活动状态,收集消息。同时给休眠状态的节点设置长度为TS的定时器,当超过TS时间长度,则睡眠状态节点转为活动状态,反之则处于睡眠状态并关闭收发器。设置簇头节点定时器,时间长度设为TC,当簇头节点超过TC时,该簇头节点开始收集本单元内所有族成员节点的数据包。该数据包包括各节点N-ID、节点所属的G-ID、节点剩余能量Er、正六边形质心与节点的距离DI等。通过这一系列的参考数值,选出理想簇头。

首轮簇头节点由最靠近正六边形质心的节点担任。当该节点发现自身能量少于竞选时节点平均能量的70%时,则进行下一轮簇头节点竞选。首先节点采用式(1)计算出节点竞选簇头的概率。

(1)

式中,i∈(1,n),Er为节点i剩余能量,Ea为簇内节点剩余能量的平均值;a∈[0,1]为距离和剩余能量的权值;di为节点到正六边形中心坐标的距离;δij为节点i到节点j的距离。Pi概率越大成为簇头节点的机会就越大。

计算出簇头竞选概率后,另引入角度比作为理想簇头节点的参考值。如式(2)、(3)、(4)所示。

χ=(分簇轮数)mod(60),χ∈[0,60]

(2)

(3)

(4)

式中,χ为偏离角度,α为角度,η为角度比;(x1,y1)、(x2,y2)为两节点坐标。η越小说明与理想簇头的接近度越高,偏度角利于动态选举簇头节点。当首轮簇头节点剩余能量低于节点平均能量的70%时,启动簇头选举机制。在选举时先考虑参数Pi,挑选出Pi值为前三名的节点,然后计算出各自的角度比。同时,采用式(5)计算出每个节点在理想情况下的吞吐率。

(5)

式中,S表示监测区域面积;δ表示节点最高传输速率;l表示节点到基站距离;Δ任意大于0的常数;n表示节点个数;R表示节点传输半径。

最终引入簇头选择函数如下式(6)。

f=aλ-bη+cp

(6)

式中,a、b、c为大于0的影响因子且a+b+c=1。

各竞选节点计算出函数值后,比较函数值大小,最大者当选为簇头节点。竞选失败的节点自动进入休眠状态,当超过时间长度TS时,休眠状态转为发现状态准备参与下一轮簇头选举。选举成功的簇头节点进入活动状态,收集数据并进行数据融合发送给Sink节点。当簇头节点经过时间长度TC时,则进行下一轮的簇头选举。

2.3 数据传输阶段

在IHCRA算法中,数据传输采用簇内单跳和簇间混合多跳的方式。在蜂窝网格簇内节点通信时,源节点将采集到的数据直接发送给簇头节点;簇间通信时采用多跳机制,寻找一条能耗最优的路径进行数据传播。簇首节点首先接受从Sink节点转发的数据并收集信息。同时,记录簇首节点与Sink节点的最短跳数,将范围内的邻居节点的N-ID、G-ID、剩余能量、簇内成员节点数、与簇首的距离dij记录下来。建立指向Sink节点的反向路由梯度。在选择下一跳簇首节点时,利用式(7)计算代价函数,选择下一跳值簇首节点具有最小的代价函数,代价函数如式(7):

(7)

式中,dij代表节点i到j的距离,di,Sink表示节点i到Sink节点的距离,dj,Sink表示节点j到Sink节点的距离。如果簇首节点下一跳为本节点自身,则直接一跳将数据传输给Sink节点,反之,则寻找下一跳节点簇首节点。直至所有节点都寻找到下一跳簇首节点为止,则表明簇间路由已建立。

3 仿真结果与分析

本文以MATLAB为仿真平台,将IHCRA路由算法与LEACH算法[14]和GAF算法[15]和CRVB算法进行仿真,四者之间进行了性能的比较。分别分析比较了网络总能量消耗和网络剩余总节点数。仿真场景中详细的参数设置见表1。

表1 仿真参数设置

采用自由空间无线通信模型。已知传感器节点耗能部分分别是传感器模块、处理器模块和通信模块,其中耗能最大的是无线通信模块。该模型中,Erx和Etx分别表示节点发送abit数据至距离d处的发射耗能和接受数据能耗,计算公式如下:

Erx(a)=Erx-elec(a)=aEelec

(8)

Etx(a,d) =Etx-elec(a)+Etx-amp(a,d)

(9)

式中,Eelec为传感器收发单位数据(bit)的电路耗能;εfs、εmp为自由空间和多径衰弱时的衰减系数,d0=(εfs/εmp)1/2为距离阈值。

网络能耗是指网络在运行过程中消耗的总能量。网络能耗越小,说明算法在综合情况下(如网络冲突,信道竞争,控制开销等)的能量消耗越小,能量有效性越高。从图4可知,在运行时间超过200 s时,算法的网络总能量呈现快速下降趋势,说明能量消耗不断增加。LEACH算法在网络运行至800 s左右时网络总能量耗尽,而此时GAF算法剩余能量占总能量的40%,CRVB算法占50%,IHCRA算法占57%。说明IHCRA算法较前3种算法能减少网络能耗。当运行时间达到1 200 s后,IHCRA算法较前3种算法在减少网络能耗上占有明显优势,对比CRVB算法也占有相对优势。这是由于IHCRA算法利用蜂窝网格分簇,在簇首选举时综合考虑了节点能量、距离和偏度角。同时在传输数据时采用混合多跳机制,平衡了节点总能耗,提高了能量有效性。

图4 网络总能量随时间变化图

图5 节点存活个数变化图

无线传感器网络中,网络的生存时间通常用剩余节点存活数来衡量。在整个WSN中,随着运行时间的增加,剩余存活节点的数量就会减少,在某个时段内,剩余存活节点比例越高代表该算法的网络生存时间越长。从图5可以看出LEACH节点开始出现节点死亡时间最早,GAF次之,CRVB算法和IHCRA较晚。IHCRA和CRVB在节点出现失效后,其余节点的失效速度相对于LEACH和GAF较快,说明IHCRA和CRVB算法的网络节点能耗较为均衡。但由于IHCRA算法采用蜂窝网格分簇相对CRVB正方形来说有更好的网络覆盖性和较少的节点通信能耗,所以IHCRA算法节点存活个数较多。图5中IHCRA算法与其他3种算法节点存活个数的比较可以看出,LEACH算法在400 s左右第1次出现了死亡节点,GAF算法和CRVB算法在700 s左右就出现了死亡节点,而IHCRA算法在900 s左右。说明IHCRA算法相比较于LEACH、GAF和CRVB算法能延长节点死亡时间,这是由于IHCRA算法在蜂窝结构的基础上进行了虚拟单元格划分方法,并描述了一种有效的簇间混合跳的数据传输策略,有效地实现了全网的负载均衡。

4 结束语

本文提出了一种蜂窝虚拟网格划分混合多跳路由算法。该算法采用蜂窝网格式的虚拟分区的方法,让节点自组成簇。同时在簇头选举时,引入新的簇首选举概率公式并加入偏度角等参数,使簇首节点选举更合理。在数据传输时采用混合多跳的方式,均衡了节点能耗。仿真实验表明IHCRA与LEACH、GAF和CRVB算法比较,网络总能耗较低,能提高网络能量有效性。在剩余节点个数上,IHCRA算法有效的延长了网络的生存周期。