基于四叉树多层次数据融合的无线传感网络路由协议研究*

聂云峰,汪 涛,鄢化鹏,吴文波

(南昌航空大学信息工程学院,南昌 330063)

在无线传感网络WSNs(Wireless Sensor Networks)应用中,为准确获取监测区域内的感知信息,通常密集部署大量的感知节点[1],节点的密集部署在增加网络冗余信息的同时加剧了节点的能量消耗。对于大规模无线传感网络而言,如何减少冗余信息传输、延长网络的生命周期,是当前研究无线传感网络路由协议的重点内容[2-3]。无线传感网络路由协议可分为平面路由和层次路由两类[4],由于分簇路由具有拓扑管理方便、数据融合简单等优点,逐渐成为当前研究的热点[5]。分簇路由协议可分为以下两类:

①非均匀分簇路由协议:整个网络被划分为网格大小不均等的簇,每个簇的节点数目和簇半径不一致。典型的非均匀分簇路由协议有:文献[6]中提出的UCS模型,首次明确提出采用非均匀分簇的思想来均衡各簇间簇首节点的能量损耗,簇间数据传输采用多跳方式,并依据簇首的期望转发负载来对簇的大小进行调整,从而使得网络中各簇首节点具有相近的能量损耗,实现了整个网络的能耗均衡。文献[7]提出的EEUC有效的将非均匀分簇思想和多跳的路由机制进行结合,依据节点剩余能量和节点位置,在基站附近选举多个簇头,利用簇首之间的竞争半径在基站区域形成多个非均匀的簇群,由于簇头数目增多,簇群规模必然减少,在保证当选的簇头能顺利完成簇间通信任务的同时,均衡簇头的能量消耗。文献[8]提出的ACOUC协议的成簇方式来源于EEUC的非均匀成簇思想,但在簇首选举方式上,除首轮选举时,所有节点根据选举条件随机且周期性的激活选举策略外,后续选举策略采取簇群内部调整的方式进行。文献[9]提出的CEB-UC采用的分簇方式是給划分的不同区域分配不同的簇群,各分区通过节点间的局部竞争产生簇头,簇头数目根据各分区的能耗相等的原则计算确定,这种方式能有效保证网络的节点能耗,延长网络的部署半径,降低簇头能耗。

虽然非均匀分簇路由协议通过调整簇群结构,均衡了簇群中节点的能耗,但不均匀的分簇方式加大了成簇的成本、网络拓扑管理难度。此外,由于分簇的不均匀,导致各个簇群分配的能量不一致,极易引发网络能量空洞问题的发生[10-12]。

②均匀分簇路由协议:整个网络被划分为若干个大小均等的簇,每个簇内的节点数目和簇的半径近似相等。典型的均匀分簇路由协议如:文献[13]提出的EADEEG协议是一种基于簇的完全分布式算法和节能的WSNs数据收集协议,它采用计时广播的方式来产生簇头,降低了簇首选举过程中的通信消耗,同时为减少与基站直接通信簇头的数量以降低网络的整体能耗,EADEEG协议采用多跳的传输方式在簇头集合间构建路由。文献[14]提出的PSO-C是一种具有能量感知能力的分簇协议,通过PSO算法选择分簇方式,并采用轮回成簇机制形成簇群,簇的形成由基站采用集中控制策略,将分簇信息广播至所有节点,簇内和簇间通信采用单跳的方式。文献[15]提出的CDAT也是一种按轮运行的分簇协议,其簇头的选举是基于一种期望值,而这种期望值是由节点的剩余能量结合网络覆盖率所需要的最优簇头数决定的。

对比非均匀分簇路由协议,均匀分簇路由协议具有成簇方便、簇群结构稳定、拓扑管理方便等优点。此外,在大规模无线传感网络中,减少节点冗余信息的传输,对于延长网络的生命周期至关重要。虽然分簇路由协议均具有数据融合[16-17]的能力,相比非均匀分簇,均匀分簇更加有利于路由协议的时空查询和网络信息的融合。基于此,提出一种基于四叉树均匀分簇的无线传感网络路由协议——(Quad-tree Uniform Clustering Routing Protocol),并对QUCRP的冗余信息传输、网络生命周期进行仿真分析。

1 GeoGrid及其改进协议

GeoGrid[18-19]协议是一种经典的均匀分簇路由协议,将整个监测区域划分成若干个大小相等的网格,单个网格构成一个簇,选取距离网格中心最近的节点作为簇首,具有成簇简单,网络拓扑清晰等优点。但GeoGrid簇群间的通信完全由簇首节点负责,这种做法极易引发能量空洞,缩短网络的生命周期。

针对上述问题,文献[20]提出的QuadGrid从成簇方式、簇首选举、网络拓扑层次构建及路由策略等方面对GeoGrid进行改进。首先依据四叉树层次递归分解原理,将监测区域迭代进行四等份分割,并采用二进制Morton码对网格进行编码;然后在簇首选举时,综合考虑节点的剩余能量、节点与其所在网格中心距离以及节点与周围簇首的通信距离等因素;最后综合节点的剩余能量和传输距离两方面因素,作为节点在下一跳路由时的选择依据。

对比GeoGrid,QuadGrid降低了节点的能量消耗,减少了洪范路由的损耗,一定程度上减少了冗余信息的传输。但QuadGrid也存在一些不足:①如图1中的QuadGrid路由过程所示,QuadGrid在四叉树相应的层次上增设父节点,父节点间的数据转发采取逐网格的传输方式而未遵循四叉树结构,丧失了四叉树结构在数据融合方面的优势;②在簇首选举时,需获取相邻8个簇首的位置信息,计算量较大。

图1 QuadGrid路由过程

图2 监测区域扩张

2 QUCRP路由协议

本文针对QuadGrid存在的问题,从3个方面对QuadGrid协议进行改进:①在簇首节点选取时,综合考虑候选节点选举时的能量、候选节点与路由层中心(网格中心)的距离、以及候选节点的通信功率等三方面因素;②在四叉树相应层次上增设路由中间节点,路由中间节点由上一级簇首节点担任,相邻路由层间的数据转发完全由路由中间节点负责;③为减少冗余信息的传输量,采用多层次多途径的融合策略对数据进行融合。

2.1 簇的划分和编码

2.1.1 划分监测区域和节点通信半径

如图2所示,为构建四叉树层次结构,QUCRP路由协议首先以Sink节点为中心,将监测区域G(红色线条围成的区域)扩展成一个正方形区域。

接着Sink节点向网络发布成簇的命令和划分层次,并以自身为根节点,采用区域四叉树递归分解原理,对整个监测区域进行四叉树迭代划分,划分层次依据空间分辨率设定,假设划分层次为4,结果如图3所示。

图3 簇的划分

网格R(图3中灰色区域所示)为划分最小簇,设其边长为l,网络边长为L,可计算出:

L=24×l

(1)

根据式(1),可计算出位于网络第zi层的簇群边长li与网络划分层次z的关系,如式(2)所示:

li=L/2zi,zi∈z

(2)

为保证簇首同成员节点之间能够进行正常的通信,第zi层感知节点的通信半径ri与网格的边长li应满足式(3):

(3)

2.1.2 网格编码

依照划分的层次,对簇群进行二进制编码,簇群对应的编码序列长Mz与所在网络层次z有Mz=2z。簇群编码采用逐层叠加的方式,低层簇群依据其在上一层簇群的方位(左上、右上、左下、右下4个方位),对应方位编码分别为00、01、10、11,将方位编码添加到上一级簇群编码后面,叠加后的编码作为自身的簇群编码。列如网络划分层次为4,则最大序列长为8,如图4簇群对应编码所示。

网格编码、补位码、分隔码以及簇内节点id共同组成节点标识号。节点标识号共占用32比特,网格编码占用2Z比特,补位码占用16-2Z比特,分隔码占用4比特,节点id占用12比特,节点标识号组成如图5所示。

图4 簇群对应编码

图5 节点标识号组成

簇群编码采用叠加方式,便于建立四叉树的层次结构。当簇首向上还是向下路由时,只选择与其簇群编码高位序列相同的簇群;通过节点标识号,更好的定位感知节点所在的层次,簇头在融合数据时,只融合与其簇群编码一致或高位序列相同节点转发来的数据,在保证路由过程严格遵循四叉树层次结构的同时,也便于利用四叉树在数据融合/压缩方面的优势。

2.2 簇首选举算法

为保障簇首选举的合理性,QUCRP路由协议从感知节点选举时的能量、感知节点与网格中心的距离大小、以及节点通信功率等三方面出发,作为簇首节点选举的依据。为简化表达,簇首的选举阈值用字母ch表示,将选举阈值最小的节点作为簇首节点,其计算公式如下:

(4)

式中:α,β,γ为平衡系数,α+β+γ=1且α>0,β>0,γ>0;ecurrent为候选簇首节点当前剩余能量;einitial为该感知节点的初始能量;dzi为感知节点与栅格中心的距离,k为簇群内节点的个数,pi为节点的通信功率,zi为网络对应的层次。

QUCRP路由协议采用轮换方式对簇首节点进行更替,并将具有最小ch的感知节点作为新的簇首节点。每经过一轮簇首选举,能量消耗过大的簇首节点会被新的节点所取代。因而QUCRP路由协议可以有效的均衡簇内节点的能量损耗,延长整个网络的寿命。

2.3 路由过程

QUCRP路由协议路由过程严格遵循四叉树层次结构,除叶子簇群外,其余层次的簇首节点均只需管理着4个子簇首,QUCRP拓扑结构如图6所示。

图6 QUCRP拓扑结构

QUCRP针对上述网络拓扑结构,在四叉树对应层次上添加路由中间节点,路由中间节点由转发节点对应的上一级簇首节点担任,路由中间节点与簇首对应关系如图7所示。

图7 路由中间节点与簇首对应关系

图8 数据转发

相邻路由层间的数据转发完全交由路由中间节点负责,QUCRP数据转发如图8所示。簇群中的所有普通节点将所收集到的数据交付给本群簇首,簇首节点收到数据后,对数据进行初步融合处理,将融合后的结果发送给对应的路由中间节点,路由中间节点收到其子簇首转发来的数据信息后,对接收到的数据进行再融合处理,得到融合精度更高的数据,接着向上一级路由中间节点转发,直至Sink节点。

由图8路由过程可知,簇首节点融合数据的能力决定着路由过程中冗余信息的传输量。

2.4 数据融合策略

QUCRP针对其网络拓扑结构和路由中间节点与簇首的对应关系,对数据融合也分两部分:叶子簇群融合和路由中间节点融合。

(1)叶子簇群融合:由式(2)和式(3)可知,当网络层次加深时,叶子簇群所在网格边长变小,簇群内节点通信范围的覆盖程度增大,节点采集到的数据冗余度增加。文献[21]采用置信距离测度来表示两个节点数据间的偏差大小,置信距离测度的值越小则测量值越接近,置信距离测度值与设定的阀值进行判断,获取节点间的支持度,构建椭圆矩阵表示节点间的关系矩阵。

叶子簇群内的簇首节点采用文献[21]的融合策略对数据进行初步融合,获取节点支持度高的数据,减少簇群内部数据的冗余。

(2)路由中间节点融合:由图8中QUCRP路由协议拓扑结构可知,路由中间节点只需融合其4个子簇首转发过来的数据,数据量相对减少但重要程度变大,为减少SInk节点接收到的网络数据失真概率,路由中间节点需对其子簇首转发来的数据进行详细的分析,文献[22]提出一种基于相关性函数和模糊综合函数的数据融合策略,先由相关性函数得到传感器节点的相互支持度,然后由隶属函数得到每个传感器提供信息的可信度,最后用模糊综合函数得到融合结果。

路由中间节点采用文献[22]的融合策略,各级路由中间节点对其下4个子簇首数据先进行相关性的判断,接着由隶属函数获取各簇首数据的可信度,最后采用模糊综合函数对子簇首数据进行融合。

QUCRP路由过程中,数据转发严格遵循四叉树的层次结构,数据逐级转发,边转发边融合,融合策略依据簇头所在的路由层次,进行多层次多方式的融合,降低接地冗余信息传输。

3 仿真分析

3.1 仿真环境和评价标准

采用MATLAB仿真,设监测区域被扩张成一大小为128 m×128 m的正方形区域,传感器个数为800,Sink节点位于网络正中心。初始数据包大小为2 kbit,数据包头长度为50 bit;节点初始能量为0.5 J;簇首每10轮重新选举,仿真结果取每100轮的平均值。

定义数据融合比例ρ,为路由协议数据融合的评价标准,计算方法如式(5)所示:

(5)

L为网络边长、z为网络划分层次、n为叶子簇群内节点个数,ki为节点i采集到的数据量。

对任意节点i,设E0为节点初始能量,Er为第r轮节点消耗的总能量;其生命周期LTi满足式(6):

(6)

3.2 仿真结果与分析

由图9可知,QUCRP相比GeoGrid平均融合比例增加幅度为1%～43.1%,与QuadGrid相比平均融合比例增加幅度为1%～7.1%。QUCRP对监测区域采用四叉树的迭代分簇方式,将网络依层次均匀划分为若干个簇群,各级路由层增设路由中间节点,路由中间节点选择比路由节点高一级簇群的簇首节点担任,保证了路由过程严格遵循四叉树的层次结构。节点采集的初始数据经所在簇群的簇首节点初步融合->路由中间节点再融合(网络划分层次越大,再融合次数相应增加)->Sink节点,多层次的融合策略大幅度减少了路由节点的数据冗余,大大降低了冗余信息传输比例。

由图10可知,QUCRP对比其他两个协议,网络生命周期有着一定的延长。QUCRP仿真轮数为(1 226 轮),相比QuadGrid(1 161轮)延长了5.6%,与GeoGrid(923轮)相比则延长了32.8%。

节点间的通信是无线传感网络能量消耗最大的部分。相比GeoGrid和QuadGrid,QUCRP通过对数据采用多层次的融合策略,减少网络中冗余信息的传输,降低节点的额外通信消耗,延长了网络的生命周期。

图9 平均融合比例对比

图10 网络节点存活情况

4 结论

本文提出一种基于四叉树多层次数据融合的均匀分簇路由协议QUCRP,从簇首选举、路由过程、数据融合等方面对QuadGrid进行了改进。首先在簇首节点选举时综合考虑节点的剩余能量、节点与网格的中心距离以及节点的通信功率等因素,使网络具有更好的负载均衡度。接着,在各级路由层上增设路由中间节点,相邻路由层间的数据转发完全交由路由中间节点负责,保证路由过程严格遵循四叉树结构。最后,采用数据的相关性和综合支持度等融合策略,对数据边转发边融合,实现数据的多层次融合。仿真结果表明,QUCRP路由协议,有效降低了冗余信息的传输,延长了网络的生命周期。下一步工作,将把QUCRP路由协议运用于现实的系统上进行验证,并在冗余精度和节点能耗效率等方面做进一步研究。