基于分级邻近节点的无线传感器网络分簇路由算法

李洪兵,刘子路,陈 强,2,刘 莎,刘小龙,梁裕巧,杨 震,陈立万

(1.三峡库区地质环境监测与灾害预警协同创新分中心,重庆 404120;2.智能信息处理与控制重庆高校市级重点实验室,重庆 404120; 3.物联网与智能控制技术重庆市工程研究中心,重庆 404120)

0 概述

随着泛在信息社会的到来,无线传感器网络[1](Wireless Sensor Network,WSN)已成为目前研究的热点之一,其通常由大量的低能耗低成本的微型传感器节点构成,通过这些传感器组成无线网络实现对各种环境的监控。作为泛在信息社会的基础,无线传感器网络被应用于军事领域、医疗领域、安防领域、智能家居[2]领域等。然而,其有限的能量资源和恶劣的环境为无线传感器网络的应用带来了巨大的挑战[3]。其中,网络的生存周期是无线传感器网络的主要问题,严重影响着网络的服务质量,因此,高效的路由协议[4]成为目前重要的研究方向。

无线传感器网络的路由协议根据拓扑结构可以分为平面路由协议[5]和层次路由协议[6]。平面路由协议中节点间没有等级划分且作用相同,然而网络中节点间距离比较小使得同一范围内节点的采集数据出现了大量重叠,在信息传输时浪费了大量能量[7],同时其网络拓补灵活性也很差,随着无线传感器网络规模的扩大,这些问题更加严重,导致平面路由协议不再适合大规模网络,层次路由协议[8]开始占据主导地位。层次路由协议是将网络分为不同层次的簇,由簇首管理簇群,同时可以采用轮循的方式优化簇的形成。其中LEACH[8-11](Low Energy Adaptive Clustering Hierarchy)协议是第一个层次性路由协议,通过根据概率选取簇首,并依据簇首建立簇群的方式将整个网络分成了多个子网络。

本文提出一种基于分级邻近节点的分簇路由(Clustering Routing Based on Hierarchical Neighbor Nodes,CRBHNN)算法。该算法考虑邻近节点状态对初步选取的簇首进行再优化,节点间通信采用中继的方式,选取中继节点对数据传输路径进行优化,以避免远处孤立节点能耗过大的问题,同时通过中继节点的选取均衡网络能耗。

1 相关研究

在所有的分簇路由协议中,LEACH协议是第一个层次型路由协议,其轮循成簇的思想被诸多层次型路由协议所引用。

PROPOSED[12]协议是一种基于粒子群算法聚类的路由协议,该协议通过粒子群算法先对网络节点进行聚类分簇,再对已形成的簇群进行簇首选取,仿真结果表明该协议提高了网络的能量利用率,延长了网络寿命。然而先成簇后选取簇首的操作使得簇首成为其邻近节点的最优簇首,但未必是其他簇群成员节点的最优簇首,本文通过先选取簇首再成簇的方式,优化簇群的形成来提高簇首的优越性。NR-LEACH[13]协议是一种基于节点排序的改进LEACH协议,该协议通过节点间路径开销和节点间链路数来确定簇首,克服了簇首依概率选取的缺点,仿真结果表明该协议延长了网络寿命。然而,该协议过于倚重特殊节点会导致网络能耗均衡上的劣势,本文通过对簇首进行再选取的方式来避免簇首选取的完全随机性,在提高网络寿命的同时有效地均衡了网络能耗。SEPFL[14]协议是一种基于模糊逻辑控制的分级路由协议,通过对节点到基站的位置、节点密度以及节点能量这3个变量进行模糊逻辑控制,提高了网络寿命和吞吐量,然而因为该算法使用了模糊控制导致感知节点计算量增大,本文通过对这些变量进行分级排序来进行控制,有效地减低了感知节点的计算量。

OCRP[15]协议是一种基于最优分簇的能量异构路由协议,该协议通过最优簇首数K将待测区域划分为K个固定分区,改进簇头选举机制,减少了网络能耗,提高了网络寿命,然而该算法的固定分区导致了整个网络成簇的固定,一定程度上限制了网络拓扑结构的变化,本文通过簇首的轮循选取对簇群进行调整,使簇群的形成更加多样和灵活,有效地提高了网络拓扑结构的灵活性。ABC[16]协议是一种基于蜂群算法的能量优化路由协议,该协议通过蜂群算法计算出传感器网络中能量最优的簇首节点组合,同时簇首节点轮流选择最近的簇内节点构建路由,仿真结果表明该协议具有能量消耗速度慢、能量均衡等优点,有效地延长了无线传感器网络寿命,然而该算法需要整合整个网络的信息并应用蜂群算法计算,使得该网络需要极大的计算能力,本文通过依据概率选取簇首,并使每个节点可以借助邻近节点信息进行分布式计算的方式,有效地降低了整个网络的计算负载。

2 网络模型

2.1 部署模型

场景部署模型[17-18]是由一个基站和部署在一片区域内的多个传感器节点构成,如图1所示,传感器感知节点从监测区域内收集数据,然后将数据发送给基站。其中节点的位置是随机固定的,并且每个传感器节点都是相同的,所有的传感器节点具有相同的初始能量,当初始能量耗尽后传感器节点死亡,基站的能量是无限的,传感器节点可以依据传输距离调整传输功率。

图1 部署模型

2.2 能耗模型

本文使用一种简单的无线电模型[19]作为能耗模型,如图2所示,在发射数据时,节点使用发射电路发射数据,同时使用放大电路对信号进行功放;在接收数据时,节点使用接收电路接收数据。

图2 能耗模型

传输[20]d距离的k比特数据的能耗ETx(k)为:

(1)

门限距离d0为:

(2)

接收k比特数据的能耗ERx(k)为:

ERx(k)=kEelec

(3)

融合k比特数据的能耗Ef(k)为:

Ef(k)=kEda

(4)

因此,节点发射控制报文的能耗ETx_CM为:

(5)

节点接收控制报文的能耗ERx_CM为:

ERx_CM=CMEelec

(6)

簇首节点接收本簇内n个簇成员节点(不经过中继,直接向簇首通信的成员节点)的数据并融合的能耗ERx_f_CH(k,n)为:

ERx_f_CH(k,n)=nkEelec+(n+1)kEda

(7)

簇首向上一级节点发射数据的能耗ETx_CH(k)为:

(8)

成员节点向上一级节点发射数据的能耗ETx_non_CH(k)为:

(9)

中继节点接收n个下级成员节点的数据并融合的能耗ERx_f_RE(k,n)为:

ERx_f_RE(k,n)=nkEelec+(n+1)kEda

(10)

其中,Eelec表示运行发射机和接收机(ETx和ERx)所消耗的能量,εfs和εmp分别为发射机放大器的自由空间模型和多径衰减模型功率能耗。数据发送低于d0距离时使用自由空间模型,否则使用多径模型,Eda为融合1 bit数据的能耗。

为了分析和验证本文算法的优越性、有效性和合理性,从簇首分布密度、网络能量利用率、节点剩余能量等因素对算法进行评价。

以簇首间距来映射,间距越大密度越小,n个簇首的簇首间距dCH(n)为:

(11)

第n轮后i节点剩余能量Ei_n为:

Ei_n=Ei_n-1-Ei_ues

(12)

其中,Ei_ues为节点i在本轮中消耗的能量。

以网络剩余总能量映射,相同周期内网络剩余总能量越大,利用率越高,网络剩余总能量Etotal为:

Etotal=∑Ei_n

(13)

2.3 模型参数

本文仿真分析所用的模型参数如表1所示。

表1 模型参数

依据n、M、εfs和εmp可得簇首最优个数kopt[21-22]为:

(14)

其中,dtoBS为节点到基站的距离。

由n和kopt得到簇首选簇概率p为:

(15)

3 无线传感器网络分簇路由算法

3.1 分簇优化

3.1.1 LEACH分簇算法

经典LEACH协议是通过阈值T(n)随机选取网络簇首,并通过已选取的簇首形成簇群,再通过簇首调度自身簇群成员节点,最终将数据传输到基站,这样网络工作一轮。LEACH协议通过这样不断轮循来均衡和节约网络能耗,延长网络寿命。

阈值T(n)为:

(16)

其中,p为簇首在网络总节点中存在的数量百分比,r为当前进行的轮数,G为上一个1/p轮中没有成为过簇首的感知节点集合。

3.1.2 分簇优化思路

通过最优簇首个数kopt可以知道理想的簇群数量,假设感知区域是M×M,则理想中的最优簇群面积SCH为:

SCH=M2/kopt

(17)

进而得到理想中每个簇首节点所管理的簇群半径R为:

(18)

本文算法中将距离某个簇首节点R0(设R0=3R/4)距离的普通节点视为一级簇群成员节点,如图3所示。其中,A、B、C为3个簇首节点,理论上其最优簇群范围分别对应图3中的3个虚线线圈。可以看到,簇首A、B的一级簇群成员节点范围(实线圈)出现了重叠区(AB区,2个实线圈的重叠部分)。通过避免这种重叠区的出现来避免簇首选取过密造成的簇群不均匀,进而提高簇首节点的工作效率。

图3 簇首和理想簇群分布

3.1.3 分簇算法描述

算法1分簇算法

输入n个感知节点随机部署在M×M的感知区域上,基站位于感知区域的中心

输出簇首分布位置和簇群成员

步骤1在每轮开始时,采取和LEACH协议相同的方法确定候选簇首,其中簇首概率为2p(避免候选簇首选取过少)。

步骤2候选簇首节点与邻近的候选簇首节点通信,如果2个邻近簇首节点距离小于3R/2,则表示不同簇内的一级成员节点出现重合,将其中一个候选簇首节点定为一级簇首节点,另一个定为二级簇首节点,确定一级簇首的簇成员范围和二级簇首的簇成员范围,其中一级成员确定有更高的优先级,即如果一个普通节点是一级簇首的成员同时也是一个二级簇首的成员,则视其为一级簇首的成员。

步骤3如果存在二级簇首的成员节点,则这些二级簇首的成员节点进行第一步操作,即再次进行候选簇首选取,新选取的候选簇首节点和已确定的一级候选簇首进行邻近簇首间通信,根据步骤2的规则对新的候选簇首节点进行一级簇首节点和二级簇首节点的分类,同时确定相应的成员节点范围。重复步骤3直到不存在二级簇首的成员节点或无法选出新的候选簇首节点。

步骤4确定一级簇首为优化后的最终簇首,进行成簇操作。

步骤5轮循前4步操作,实现簇首和簇群的不断更新。

3.1.4 分簇优化仿真分析

为分析和验证分簇优化的合理性和有效性,下面从簇首的分布位置、簇首分布密度、网络剩余总能量分析其合理性,从网络寿命验证其有效性。

图4为CRBHNN算法30轮时的簇首分布示意图,图4(a)为依据CRBHNN算法的初次候选簇首分布(簇首概率为2p),图4(b)为依据CRBHNN算法优化完成后的簇首分布,图5为LEACH算法在30轮时的簇首分布(簇首概率为p)。由图4(b)与图5的对比可知,LEACH算法因为簇首是完全随机选择的,所以造成有些簇首间相互距离过近,而CRBHNN算法将簇首的成员节点进行了分级,对某些密集的簇首进行再选举,使得新算法得到的簇首分布更加均匀。图6为簇首间距随周期的变化,簇首间距映射簇首密度的变化。从图6可以看出,实线大部分分布于虚线上方,表明CRBHNN算法生成的簇首密度明显小于LEACH算法,验证了图4、图5的分析结果,证实了CRBHNN算法生成的簇首分布更加均匀;同时图6中周期的最后不再出现实线线条并不是CRBHNN算法没有产生簇首,可能是只产生了一个簇首,这主要是因为大量节点死亡,存活节点过少,使得簇首出现的概率大幅下降。

图4 CRBHNN算法在30轮时的簇首分布

图5 LEACH算法在30轮时的簇首分布

图6 簇首间距随周期的变化

图7为网络剩余总能量随周期的变化,网络剩余总能量映射网络能量利用率。由图7可知,实线在初始时位于虚线的上方并保持较长的周期,表明CRBHNN算法在相同的周期内消耗的能量更少,证实了CRBHNN算法的网络能量利用率比LEACH算法更高,说明CRBHNN的成簇更加合理,簇内成员通信的能耗更少;同时周期的最后实线与虚线出现相交,一部分实线处于虚线的下方,这是因为节点大量死亡后,节点成为簇首的概率大幅下降,使得一部分节点直接向基站通信,LEACH算法中这些节点集中在基站附近,RBHNN算法则分布比较均匀,表明了RBHNN算法选取的簇首更加合理,网络能量更加均衡。

图7 网络剩余总能量随周期的变化

图8为节点生存周期。从图8可以看出,实线在初始时位于虚线的上方并保持了很长的周期,由此可知,在CRBHNN算法中第一个节点(First Node,FND)死亡和半数节点 (Half of all Node,HND) 死亡的出现比在LEACH中更晚,这验证了算法优化的有效性,证明CRBHNN算法的簇首选取优于LEACH算法;同时在周期的最后实线与虚线出现相交,实线出现在了虚线的下方,主要是因为节点存活过少,并且LEACH算法中存活节点大部分都分布在基站附近,进一步证明了RBHNN算法选取的簇首更加均匀,基站附近的节点选为簇首的概率大于LEACH算法。该算法优化的局限性是远处的节点向簇首或者基站通信时会造成能耗的不必要浪费。

图8 分簇算法节点生存周期

3.2 路由优化

3.2.1 LEACH路由优化方法

在经典的LEACH算法中,簇首节点与基站之间和成员节点与簇首之间是直接通信的,不存在中继节点。

本文算法通过将邻近节点进行分级来确定节点的中继节点。将距离某个节点小于d的节点视为该节点的邻近节点,将节点剩余能量划分为6个等级,大于E1(E1=0.8×E0,E0为节点初始能量)的为一级,小于E1大于E2(E2=0.6×E0)的为二级,小于E2大于E3(E3=0.4×E0)的为三级,小于E3大于E4(E4=0.2×E0)的为四级,小于E4大于E5(E5=0.1×E0)的为五级,小于E5的为六级。同时将节点i的邻近节点中所有Ei_j(Ei_j为节点i向节点j通信的能耗)与Ej_BS(Ej_BS为节点j向基站通信的能耗)的和小于Ei_BS(Ei_BS为节点i向基站通信的能耗)的节点j视为节点i的前向节点,否则视为后向节点。

3.2.2 路由算法描述

算法2路由算法

输入n个感知节点随机部署在M×M的感知区域上,基站位于感知区域的中心

输出每个节点的中继节点

步骤1节点进行邻近节点广播并接收邻近节点(通过信号强度确定距离)的广播信息。

步骤2根据邻近节点信息确定前向节点和后向节点,同时对节点剩余能量进行分级,建立包含前后向节点标识、能量等级、节点间距离的邻近节点信息表。

步骤3在邻近节点中依据一定的规则确定自身的中继节点或确定自身直接向基站通信。最小能级节点拥有一级优先权,前继节点拥有二级优先权,自身拥有三级优先权,后继节点拥有四级优先权,节点距离(中继节点离自身的距离)为五级优先权,其中距离越短优选级越高。以此规则确定中继节点,若最终确定为自身则直接向基站通信,否则向中继节点通信。

步骤4轮循前3步操作,实现中继节点的不断更新。

3.2.3 路由优化仿真分析

为分析和验证路由优化的合理性和有效性,下文从路由路径、网络剩余能量分析其合理性,从网络寿命验证其有效性。

图9和图10分别为CRBHNN和LEACH算法的路由路径。从图9和图10可以看出,CRBHNN算法中远处的节点都是通过多个中继节点向基站进行通信,而LEACH算法中簇群成员节点是经过簇首向基站通信,簇首节点是直接向基站通信,因此LEACH算法中远处的节点能耗更大;同时CRBHNN算法中数据在众多中继节点处进行数据融合,进一步提高了能量利用效率。

图9 CRBHNN算法路由路径

图10 LEACH算法路由路径

图11为网络剩余总能量随周期的变化。从图11可以看出,实线在初始时位于虚线的上方并保持了较长的周期,由此可知,CRBHNN算法的能量利用率比LEACH算法更高,进一步证实了图9和图10的分析结果,同时图中实线与虚线发生相交后,虚线处在了实线上方,这是因为节点大量死亡后LEACH算法中留下的节点大部分位于基站附近,进一步证实了RBHNN算法能量均衡性优于LEACH算法。

图11 路由算法中网络剩余总能量随周期的变化

图12为第一个节点死亡时的节点剩余能量。从图12可以看出,虚线大部分位于实线上方并且虚线起伏明显大于实线,由此可知,CRBHNN算法的能量均衡性明显优于LEACH算法,这是由于CRBHNN算法在选取中继节点时对节点剩余能量进行了分级,使高能量节点有更大的概率为负载的中继节点工作,通过增大高能量节点的负载、减少低能量节点的能耗来均衡网络能耗,而LEACH算法是完全随机选取的簇首,并未考虑能耗方面,进一步证实了图11的分析结果。

图12 第一个节点死亡时的节点剩余能量

图13为节点生存周期。从图13可以看出,实线在初始时位于虚线的上方并保持了很长的周期,由此可知,CRBHNN算法的FND和HND比LEACH算法晚出现很多,这验证了CRBHNN算法可以更有效地均衡节点能耗,提高节点的能量利用率,延长网络寿命,证实了CRBHNN算法在路由方面优于LEACH算法;同时在网络后期实线与虚线出现相交并且实线处于虚线的下方,这是因为节点大量死亡后,LEACH算法中存活的节点大部分位于基站附近,使其死亡速度减缓,而CRBHNN算法存活的节点更加均匀,进一步证实了RBHNN算法有更好的能量均衡性。该路由优化的局限性是当邻近节点范围定义过大时会造成一定程度的通信延迟。

图13 路由算法节点生存周期

3.3 CRBHNN算法

3.3.1 CRBHNN算法优化方法

本文算法综合考虑簇首优化算法和路由优化算法的优缺点,通过整合这2种算法来达到最优化。在簇首选取阶段是通过改进的分簇优化方法对整个无线传感器网络中的节点进行分簇,通过限定簇群范围来限定邻近节点范围;在簇内成员与簇首的通信阶段是依据路由优化算法对数据传输路径进行优化,如图14所示,将图10中的虚线路径优化为图14中的虚线路径,使远处的成员节点通过中继节点向簇首通信;在簇首与基站间通信阶段同样是依据路由优化算法对数据传输路径进行优化,如图14所示,将图10中的虚点线路径优化为图14中的虚点线路径,使远处的簇首通过中继节点向基站通信,最终达到延长网络寿命的目的。

图14 CRBHNN算法的数据传输路径

3.3.2 CRBHNN算法描述

算法3CRBHNN算法

输入n个感知节点随机部署在M×M的感知区域上,基站位于感知区域的中心

输出簇首分布位置、簇群成员和每个节点的中继节点

步骤1依据CRBHNN分簇算法选取簇首同时确定各自的簇群成员。

步骤2依据CRBHNN路由算法确定每个簇群中成员节点的中继节点,簇群成员以此路径向簇首传输数据;依据CRBHNN路由算法确定每个簇首的中继节点,簇首以此路径向基站传输数据。

步骤3轮循步骤1、步骤2的操作,实现网络拓扑的不断更新。

3.3.3 仿真结果与分析

为验证本文CRBHNN算法的有效性、可行性和优越性,从网络剩余总能量、节点剩余能量和节点生存周期来对算法进行评价,并与LEACH算法、LEACHC算法、DEEC算法和CECA算法进行对比。

图15为网络剩余总能量随周期的变化。从图15可以看出,无标记的实线在初始时位于其他线的上方并保持了很长的周期,在网络能量利用率上CRBHNN算法明显优于其他算法,这是因为在数据传输阶段,数据的传输经过了大量的中继节点,只需相对短的路径就可以完成传输,同时数据也在中继节点进行了融合,进一步减少了数据传输的能耗,明显优于其他算法的直传方式,同时在后期无标记的实线与其他线相交后处于其他线下方,也是因为其他算法的存活节点大部分位于基站附近,进一步证明了CRBHNN算法的能量均衡性优于其他算法。

图15 不同算法网络剩余总能量随周期的变化

图16为首节点死亡时的节点剩余能量。从图16可以看出,无标记的实线大部分位于其他线的下方并且无标记的实线的起伏明显小于其他线,由此可知,在能量负载均衡上CRBHNN算法明显优于其他算法,这是因为对节点剩余能量进行了分级,使得剩余能量多的节点更易于成为中继节点,减少剩余能量少的节点的通信负载,对节点能量进行了一定程度的均衡,而其他算法只在簇首选取时考虑了能量这一因素,并未进行全面考虑。

图16 首节点死亡时的节点剩余能量

图17为节点生存周期。从图17可以看出,无标记的实线在初始时位于其他线的上方并保持了很长的周期,由此可知,CRBHNN算法的FND和HND比其他算法晚出现很多,证实了其生存周期明显优于其他算法,这也充分证明了CRBHNN算法的有效性和优越性,这主要是因为CRBHNN算法在进行随机选取簇首后又对其分布位置进行优化,使其分簇更加均匀,实现了簇首选取的优化,同时考虑能量等因素采用中继方式进行信息传输,均衡了网络负载,提高了能量利用率;同时在后期无标记的实线与其他线相交后处于其他线的下方,也是因为其他算法的存活节点大部分位于基站附近,这进一步证明了CRNHNN算法能量均衡性优于其他算法。

图17 CRBHNN算法节点生存周期

4 结束语

为延长网络寿命提高网络服务质量,本文对无线传感器网络的数据传输能耗模型进行研究,提出一种基于分级邻近节点的分簇路由算法。在分簇阶段通过对簇群成员进行分级,对不合理的簇首进行再选举,解决了簇首分布的完全随机性问题,使得簇首可以更均匀地分布在感知区域中。在数据传输阶段通过对邻近节点进行分级,确立各个节点对应的中继节点,解决远处孤立节点传输能耗过大和网络能量不均衡的问题,同时多次的数据融合也提高了能量利用率。仿真结果表明,与LEACH、CECA、DEEC等算法进行对比,该算法可以有效减少和均衡网络负载能耗,提高能量利用率,最终达到延长网络寿命的目的。CRBHNN为分布式路由算法,是基于一定范围内的邻近节点信息进行的优化,可能会导致部分范围内的优化在整体上不够突出,下一步将与集中式算法结合来优化路由算法。