基于簇首负载均衡的无线传感器网络分层路由协议

贺道德，徐 计，黄正鹏

(贵州工程应用技术学院信息工程学院,毕节 551700)

无线传感器网络(wireless sensor networks, WSN)是由无线传感器组成的一种自组织无线通信网络,一般用于物联网中的底层数据采集,特别是将其置于如矿产开采安全、军事情报收集等领域[1]。WSN首先将大量无线传感器节点置于需采集数据的网络区域,然后使用相关组网通信技术以形成一个网络系统,最后在网络区域外围置汇聚节点(Sink)来接收并处理数据[2]。由于无线传感器网络的任务及环境需求,无线传感器一般为能量有限的一次性设备；因此,其网络能耗的性能指标是学者们研究的重要方向之一[3-4]。分层无线传感器网络因其节能备受学者关注；它将网络分成若干个簇,簇由簇首和子节点组成；网络中的子节点采集数据后通过簇首间相互转发至Sink；从而优化了网络通信量而节省了网络能耗[5-6]。但这类分层网络具有网络初始化时,选举簇首的开销大；且离Sink越近,簇首的负载越重；并且还存在簇首单点失效的问题,以及在数据传输时,子节点采集到数据后,需通过多级簇首路由而导致时延大等问题。

为解决上述分层无线传感器网络因簇首带来的网络问题,本文从均衡簇首负载的角度提出基于簇首负载均衡的WSN分层路由协议CHLBRP(cluster head load balancing routing protocol)；将从汇聚节点作用域的划分、网络的梯度分簇、移动节点收发数据等方面来分析和设计协议；从而均衡网络簇首的负载,降低网络能耗,减少路由时延,解决网络单点失效等问题。

1 相关研究

围绕降低网络能耗,提高无线传感器网络的生存周期,国内外学者展开了大量研究。Heinzelman等[7]提出了最具代表的无线传感器网络协议LEACH(low-energy adaptive cluster hierarchy)；它将网络分为若干个簇,普通节点通过簇首直接与网络外围的Sink节点进行通信；该协议为降低网络能耗且控制单点失效,采用周期随机轮换选举节点为簇首；但因簇首选举的随机性使得簇首性能不够好且分布不均匀；另外,簇首的频繁选举也会产生大量额外开销；簇首单跳与Sink通信使得离Sink越远的节点,对射频功率的要求越高且能耗速度越快。文献[8]提出的LEACH-C协议是LEACH的改进协议,它由Sink节点挑选位置最佳且能量充足的节点担任簇首,但最优簇首的界定是一个NP完全问题。文献[9]提出了PEGASIS(power-efficient gathering in sensor information system)协议,它采用多级分簇的方式将网络中的节点形成一个簇链,但由于通信时采用簇间多级接力,使得离Sink越近的节点,其能耗越大,且其单点失效产生的后果非常严重。从上述研究来看,簇首的性能以及分簇的算法决定着分层WSN的性能,基于此,文献[10]使用人工蜂群算法来选择最优簇首,首要考虑能量效率,并权衡网络链接质量、扩展性及吞吐量来建立网络模型；但仍然采用多跳路由算法使得各簇首的负载不均衡。文献[11]则采用非均匀分簇思想设计最优簇数,使用改进的凝聚嵌套算法来分簇,从而降低网络能耗,提高网络生存周期；但非均匀分簇的簇首不一定是网络中的最优节点；且其数据融合技术只考簇内数据融合,而不考虑簇间融合；因此,不能从根本上解决簇首不均衡的问题。

针对上述研究问题,本文在文献[12]中提出基于单向多汇聚节点的路由算法OWMSRP(one-way and multi-sink routing protocol),采用多Sink节点将网络划分为若干区域,然后利用RSSI(received signal strength indication)将网络中的节点分级,并确定Sink的作用域；当数据传输时,各簇首单跳将数据传递给所属Sink节点；但因采用簇首单跳与所属Sink传递数据,使得网络大小受限,且整个网络能耗较大。为降低网络能耗,文献[13]中提出DMNRP(distance and mobile node routing protocol)协议,采用移动节点在簇首与Sink间传递数据从而降低簇首负载；但网络采用移动节点传递数据势必会增大网络延迟,从而降低路由效率。

结合文献[12-13]的优缺点,本文从簇首负载均衡出发,在考虑网络路由效率的基础上提出CHLBRP路由协议；在网络观测区域外围放置多个Sink节点,并采用RSSI划分各汇聚节点的作用域；在数据传输时,运用移动节点在簇首与Sink间收发数据,从而降低簇首负载,提高网络生存时间。

2 CHLBRP协议

2.1 网络架构条件

为实现簇首负载均衡的WSN分层路由协议CHLBRP,基于如下网络架构条件。

(1) 为便于研究,本网络局限考虑在平面结构进行,即观测区域为二维平面,且无线传感器节点随机分布在观测区域。

(2) 在观测区域外围均匀分布适量的Sink(汇聚节点),以确保观测区中的传感器节点能有一个合理的接收信号强度指示(RSSI)梯度。

(3) Sink节点可依据实际情况更换电池,即不考虑其能耗问题。

(4) 无线传感器节点的通信模块的能耗远远大于其计算模块的能耗,即在进行测试时,仅考虑通信能耗,以降低研究复杂性。

(5) 在网络中配额一定数量的移动节点用于在Sink节点与普通无线传感器节点间进行数据传输,且其可更换电池,即其为永久生存节点。

2.2 基于多Sink与RSSI梯度分簇

提出的基于多Sink与RSSI的梯度分簇分为两个过程:确定Sink节点作用域和RSSI梯度量化标识与簇的建立。为完成上述过程,需给出下列定义。

定义1从属移动节点集MobileSet,由汇聚节点维护,包含的内容为汇聚节点的从属移动节点的标识MobileId等信息。

定义2移动节点的所属Sink域MPreSink,由移动节点维护,包含的内容为各移动节点的所属Sink节点的标识SinkId等信息。

定义3从属节点集SubNodeSet,由汇聚节点维护,包括四个域,分别为从属节点标识NodeId,从属节点的剩余能量值NodeEN,到该从属节点的距离值Dista,以及该节点是否为簇首的标志IsCHD等内容。

定义4所属Sink域PreSink,由传感器节点维护,包括所属汇聚节点的标识SinkId,到该所属Sink节点的距离值Dista等内容。

定义5簇成员域MemberTable,包括成员节点标识NodeId,成员节点的剩余能量值NodeEN等内容。

定义6簇首能量阈值ENhold,各传感器节点的剩余能量值超过此值才能竞选簇首,该值由Sink节点定期计算并发布到其作用域,用于初始构建网络或网络维护。

定义7节点层级NdLevl,本协议采用多汇聚节点下的分层结构来构建网络,各节点依据到其所属Sink节点的距离划分层次。任意节点的层级值1≤n.NdLevl≤MaxNdLevl,其中MaxNdLevl为最大层级值,n为节点标识。本协议的层级值计算方法:n.NdLevl=[n.PreSink.Dista/ΔDista],其中ΔDista为设定的量化距离宽度，且最大距离Rmax=ΔDista*MaxNdLevl,最小距离Rmin=ΔDista。

2.2.1 确定Sink节点的作用域

在CHLBRP网络的外围均匀布局一定数量Sink节点,并给每个汇聚节点配置一定数量的移动节点,用以在其所属Sink节点的作用域内传递数据,从而形成多汇聚-移动节点的传感网络,网络初始结构如图1所示。

图1 CHLBRP网络初始架构图Fig.1 Initial architecture of CHLBRP network

在图1中有一矩形无线传感网观测区,在该区域内随机分布一定量的无线传感器节点,并在其外围四个边上各分配一个Sink节点；另外,给每个Sink分配一定量的移动节点,以构成基于多Sink-移动节点的无线传感网络拓扑。在实际应用场景下,本协议支撑二维平面的任意观测区域结构,只需在观测区域外围均匀分布若干数量的汇聚节点即可；而Sink的数量则依据其观测区域的规模而定。

在CHLBRP网络初态确定后,采用接收信号强度指示(RSSI)测出各无线传感节点与各Sink节点之间的距离,并根据此距离值来为各传感节点确定其所属Sink节点,以实现确定各Sink的作用域。为确定各Sink的作用域,各Sink节点发射信号到观测区域,其参数为其节点标识SinkId。各传感器节点通过到各Sink的RSSI确定它们之间的距离,选择距离最近的Sink为其所属Sink节点,并根据其收到的信号维护所属Sink域；然后反馈信息给所属Sink节点,其内容包括节点标识NodeId、剩余能量值NodeEN等信息。当Sink节点收到其从属节点的信息后,用其信息维护从属节点集,最终完成作用域的确定,具体算法如下所示。

(1)S. SinkHello(S.SinkId) to all node;

/*任意Sink节点S发送广播消息SinkHello给观测区域中的传感器节点,参数为Sink的节点标识*/

(2)for(nin all node){/*任意传感器节点n收到SinkHello后执行下列操作*/

(3)n.PreSink.SinkId=Null;

n.PreSink.Dista=infinity;

/*初始化任意传感器节点n的所属Sink节点域为空,将距离设置为infinity无穷大*/

(4)设置确定作用域的时间值为t;

(5)for(j=0;j<=t;j++){/*在时间t内,各传感器节点确定其所属Sink节点*/

(6)任意传感器节点n获得任意Sink节点S的SinkHello消息;

(7)运用RSSI值计算S.Dista;/*Dista为节点n到Sink节点S的距离*/

(8)if(S.Dista

(9){/*更新n节点的所属Sink节点域*/

(10)n.PreSink.SinkId=S.SinkId;

n.PreSink.Dista=S.Dista; } }

(11)SinkNodePs=new SinkNode();

Ps=n.PreSink.SinkId;

(12)n. nodeReply(n.nodeId,n.NodeEN,n.Dista) toPs

(13)/*任意传感器节点n单向发回应消息给其所属Sink节点Ps*/}

(14)for(Psin all Sink){/*任意Sink节点Ps依据其从属节点信息确定作用域*/

(15)SubNodek=new SubNode();/*新建k节点来记录n的相关数据*/

(16)k.NodeId=n.NodeId;k.NodeEN=n.NodeEN;k.Dista=n.Dista;

/*k节点记录n的节点标识、能量值和距离值*/

(17)k.IsCHD=0;/*所属子节点初始加入时均以非簇首标志进行初始化*/

(18)Ps. addSub(k) toSubNodeSet;/*汇聚节点Ps将其从属节点n的信息写入其从属节点集*/}

通过上述算法确定了CHLBRP网络中各汇聚节点的作用域,各个传感器节点依据RSSI选择距离最近的汇聚节点为其所属Sink,最终确立好作用域的网络拓扑图如图2所示。

图2 划分作用域后的CHLBRP拓扑图Fig.2 CHLBRP topology after scope partition

图2为划分好作用域后的网络拓扑图,半圆弧为各Sink节点的作用域,在一般情况下,各作用域交汇处分布有传感器节点,但这些节点只有一个所属Sink节点；这是因为在算法运行时,依据先后顺序来比较距离远近来确定其汇聚节点。

2.2.2 基于多Sink多层级的网络分簇

确定好各汇聚节点的作用域后,各Sink节点应在其作用域内多级梯度分簇。为完成此任务,①各Sink节点依据其从属节点的能量值计算出簇首能量阈值,以确定能量值超过此值的节点才能选举簇首；②对各节点进行多级量化分层标识,各节点依据到其所属Sink节点距离值Dista进行量化分层级；③在各层级内,依据其所属Sink节点计算好的能量阈值进行簇首选举；④在完成簇首选举后,各传感器节点在同一层级内就近加入各簇以完成基于多Sink多层级梯度分簇的任务,具体算法如下所示。

(1)for(S=1;S<=Num;S++){/*该算法遍历网络中所有Sink节点,Num为网络中Sink节点总数*/

(2)S.ENhold=0;/*在算法运行初期,将任意Sink节点的能量阈值赋初始值为0*/

(3)S.ΔDista=infinity;/* infinity为无穷大,ΔDista为量化分级的距离宽度*/

(4)for(i=0;i

(5){/*遍历Sink节点S的从属节点集,计算ENhold与ΔDista */

(6)S.ENhold=S.ENhold+S.SubNodeSet[i].NodeEN;

(7)if(S.ΔDista>S.SubNodeSet[i].Dista)S.ΔDista=S.SubNodeSet[i].Dista;}

(8)S.ENhold=S.ENhold/i; /*计算出能量阈值为各子节点的能量平均值*/

(9)S.pushCluPar(S.SinkId,S.ENhold,S.ΔDista) toS.SubNodeSet;

/*汇聚节点S发布它的能量阈值和距离量化宽度等建簇参数给其从属节点*/

(10)for(nin all node){/*任意传感器节点n收到Sink节点的建簇参数后,执行下列操作

(11)n.IsCHD=0;/*初始设置节点n的簇首标志为0*/

(12)if(S.SinkId==n.PreSink.SinkId){

(13)n.NdLevl=[n.PreSink.Dista/S.ΔDista];/*计算出节点n的层级值*/

(14)if(n.nodeEN>S.ENhold){/*若节点n能量值大于能量阈值,发布簇首竞争消息*/

(15)n.ClusterHD(n.NodeId,n.PreSink.SinkId,n.NdLevl,n.nodeEN)}}

(16)设置簇首选举计时器t1;

(17)while(t1){/*簇首选举*/

(18)收到任意其他结点n1的簇首竞争消息;

(19)if(n.PreSink.SinkId==n1.PreSink.SinkId&&n.NdLevl==n1.NdLevl)

(20){/*同一所属汇聚节点且同一层级*/

(21)if(n.NodeEN

(22)n.IsCHD=1;/*节点n竞选簇首成功,设置簇首标志为1*/

(23)n.myIsCHD(n.NodeId) ton.PreSink.SinkId/*告知其所属Sink其为簇首*/

(24)n节点的所属Sink节点修改关于n节点的簇首信息;

(25)n.myIsCHD(n.NodeId,n.PreSink.SinkId,n.NdLevl) to other;/*发布建簇消息*/

(26)设置最大成员数maxMEM;

(27)设置建簇周期计时器t2;

(28)while(t2&&maxMEM){/*建簇*/

(29)接收到任意节点n2的入簇消息;

(30)if(n.PreSink.SinkId==n2.PreSink.SinkId&&n.NdLevl==n2.NdLevl)

(31){将n2节点加入到n簇首的簇成员域MemberTable;

(32)n. ACK(n.NodeId) ton2;/*n节点给n2节点入簇回应*/

(33)maxMEM--;}}

(34)retrun 1;/*量化分簇结束*/}}

通过上述算法,网络在不同Sink节点的作用域下进行梯度分层建簇；在分簇过程中,将能量值最高的节点选举为簇首,从而确保簇首节点的健壮性好；基于多Sink多层级的网络分簇后,在Sink1作用域下的部分网络拓扑图如图3所示。

图3 Sink1作用域内部分网络拓扑图Fig.3 Partial network topology in the scope of sink1

从图3中可以看出,在该作用域内,网络被分为多个层次,各个层次都分布一定数量的簇；这是因为本协议采用梯度分层的方式来建簇,从而确保簇的均匀分布；另外,簇的选举限制在各Sink节点的作用域和各层级之内,从而大幅减少网络通信量,降低网络能耗。

2.3 基于移动节点的数据传输

本协议为降低簇首负载,不采用簇链方式多级接力传输数据,而是采用在网络中给各Sink节点配备一定数量的移动节点在汇聚节点与簇首间传递数据。各移动节点以其所属Sink节点为中心,在其作用域内来回移动；因此,各Sink节点需根据其作用域确定移动节点的移动半径,具体算法如下所示。

(1)for(S=1;S<=Num;S++){/*该算法遍历网络中所有Sink节点,Num为网络中Sink节点总数*/

(2)S.MovRd=0;/*移动半径MovRd赋初始值为0*/

(3)for(i=0;i

(4){

/*遍历Sink节点S的子节点集,求移动半径*/

(5)if(S.MovRd

(6)S.MovRd=S.SubNodeSet[i].Dista;}

(7)S.pushMovRd (S.SinkId,S.MovRd) toS.MobileSet;

/*汇聚节点S发布移动半径给其从属移动节点*/

(8)for(min allmobileNode){

/*任意传感器节点m收到Sink节点的移动半径后,设置其移动半径*/

(9)if(S.SinkId==m.MPreSink.SinkId)

(10)m.MovRd=S.MovRd;}

通过上述算法,各移动节点将其移动半径设置为其所属Sink节点作用域覆盖的最大距离值,以确保移动节点能覆盖到其所属汇聚节点内的每一个传感节点。移动节点在传输数据时,通过匹配传感器节点的簇首标志、所属Sink的节点标识等来判定是否接收其数据,图4为在Sink1的作用域内,移动节点传输数据的拓扑图。

图4 移动节点传输数据拓扑图Fig.4 Data transmission topology of mobile nodes

在图4中,普通传感器节点N首先将数据传输给其簇首节点,簇首节点运用文献[14]的移动节点定位算法,定位到移动节点Mob,并将数据传递给该移动节点,再由Mob将数据传输给Sink1。由于此路由过程不需要簇首进行簇间转发,且数据传输局限在Sink1的作用域内；从而降低了簇首的负载与网络传输通信量,提高了网络性能。

3 仿真与性能分析

为验证本文提出协议的有效性,采用MATLAB平台设计了仿真实验来分别测试LEACH、CHLBRP以及其先期协议OWMSRP和DMNRP。在实验时,确定无线传感器观测区的场地大小为1 200 m×1 000 m,在该区域内部随机分配500个传感器节点；在测试CHLBRP协议时,在观测区外围均匀分布4个汇聚节点,并为每个Sink节点配备6个移动节点,移动节点以Sink节点为中心成30°角旋转分布,分6个方向以2 m/s的速度来回移动。

首先,网络能耗是无线传感器网络的一项非常重要的性能指标,因此,仿真实验测试了传统的LEACH协议以及本协议和其先期协议OWMSRP、DMNRP的网络能耗随时间变化的情况,具体如图5所示。

图5 不同协议能耗比较Fig.5 Energy consumption comparison of different protocols

图5展示了LEACH、OWMSRP、DMNRP和CHLBRP协议随时间变化的能耗情况,可以看出,后三种协议因采用了相应优化算法,使其能耗明显低于LEACH协议；而CHLBRP协议因结合OWMSRP和DMNRP相关技术的优点来构建网络,从而使其能耗得以进一步降低。

另外,生命周期是无线传感器网络的另一重要性能指标；因此,提出的路由协议以均衡簇首负载并提高网络生命周期为目标。为验证协议的有效性,仿真实验测试了上述不同协议的生命周期并进行了比较,具体如图6所示。

图6 不同协议生存时间比较Fig.6 Lifetime comparison of different protocols

从图6可以看出,本文协议及先期协议的生存时间较传统的LEACH协议有大幅提高,并且本文协议因结合先期协议的优点而构建,使得簇首负载问题得到进一步的改善,从而提高了网络生存时间。

4 结论

本文协议从簇首节点负载均衡的角度出发,采用在无线传感器网络的观测区外围均匀分布多个Sink节点的方法来构建网络；并使用RSSI进行各Sink节点的作用域划分与节点的梯度分簇；采用移动节点在各簇首节点与Sink节点间进行数据传输；从而达到克服簇首节点负载过重的问题,减少了网络通信量,均衡了网络中各簇首节点的负载,从而提高了网络生存时间。下一步将重点研究移动节点的移动算法及将本文协议应用于更复杂的网络环境。