一种适用于带状区域的WSN节点覆盖优化方法

郝占军,侯姣姣,党小超,曲南江

(1.西北师范大学 计算机科学与工程学院,兰州 730070; 2.甘肃省物联网工程研究中心,兰州 730070)

0 概述

在无线传感器网络(Wireless Sensor Network,WSN)中,将多个传感器节点有组织地部署在待监测区域内,这些节点协同有序进行信息监测并把收集到的信息周期性地发送至基站。然而传感器节点通常需要部署在野外环境中,难以进行充电或替换,当电池电量不足时节点会失效或者由于非人为因素[1-2]节点遭到破坏时会严重影响网络的运行。

在隧道、矿井、大型桥梁等带状区域中部署传感器网络时,由于其形态特殊,节点通常会被部署为狭长分布的状态且需要将收集的数据定期发送至一侧的基站,而实际应用中传感器节点通信距离有限,因此需采用多跳的方式进行数据传输。此时,靠近基站区域的节点需要负责更多的转发任务,因此靠近基站的网络所转发的数据量大幅增加,消耗能量也增多。但节点自身能量有限,容易过早耗尽能量从而导致节点死亡,并且使得基站周围形成“网络能量空洞”[3-4]。这些失效节点所收集的数据不能转发至基站,网络提前结束运行,但此时网络中仍有大量能量未被使用,严重降低了网络使用效率。传统部署方法和路由协议在带状区域结构下有较大的局限性,因此需要考虑如何有效部署传感器节点来解决能量空洞问题,在保证无线网络实现有效覆盖和连通的同时,均衡网络能耗,延长网络生命周期。

为均衡网络能耗,研究人员提出了网络分簇层次模型并针对线型区域网络中的部署问题做了进一步的研究。文献[5]根据簇头节点的竞争范围构造规模不同的簇及簇头节点进行多跳通信来均衡簇头节点的能量消耗。文献[6]基于经典LEACH算法,在监测区域中将簇内节点数控制在一定范围内,并合并规模极小的簇来均衡各分簇能量。文献[7]提出簇头竞争算法将网络划分为几何尺寸不同的簇,并结合簇间路由来节约网络能量。但上述方法的簇间路由均未考虑节点的部署情况,因此不适用于带状区域的网络部署。文献[8]提出一种DEBUC协议来均衡簇内和簇间能耗,采用簇头竞争算法控制不同距离簇的大小,但不适用于距离较长的带状区域网络。文献[9]在线型无线传感器网络中采用等腰三角形划分的方式,实现对区域的K重覆盖,并对传感器节点分组以均衡网络整体能耗。文献[10]针对矿井巷道环境提出一种分层路由协议,采用分簇的方式在数据转发量较大的区域进行较大规模的簇划分,但由于簇头节点间距离的不同使得无线传感器网络能量的消耗速度达不到最优。本文提出一种以菱形分区方式划分带状区域的节点部署方法,利用等距多跳传输降低网络能耗,并在等距分簇后进一步计算得出各簇所需簇头节点的数量,通过簇头节点非均匀部署均衡带状区域的网络能耗并延长网络生命周期。

1 能量模型

1.1 传感器节点能量模型

本文采用文献[11]中的传感器节点能量消耗模型,设置阈值d0(d0为常数,取值与节点应用环境有关),根据发送节点和接收节点之间的距离与d0的关系计算能耗,当两者之间距离小于d0时,符合自由空间模型,发送节点消耗的能量与两者之间距离的平方成正比;否则使用多路衰减模型,即与距离的4次方成正比。在数据传输过程中,发送节点的能耗ETx(l,d)主要是发送无线电路和放大器的能耗[12-13]。在节点间距为d时,传送lbit信息的能耗为:

(1)

接收节点的能耗ERx(l)主要是无线电路中用于数据传输的能耗Eelec。当接收lbit数据时,传感器节点的能耗为:

ERx(l)=lEelec

(2)

其中,εfs和εamp分别表示接收节点和发送节点在不同距离区间范围内,发送放大器传送每比特数据所需的能量。

1.2 簇头节点能量模型

本文中的数据通过簇头节点进行多跳传输,其能耗包含接收簇内节点信息以及数据转发两部分。假设簇内m个节点中只有1个簇头节点和(m-1)个簇内节点,在一次节点传输过程中的数据量簇头节点为l,则簇头节点接收簇内数据的能耗为:

ECH=(m-1)lEelec

(3)

簇头节点在数据转发时消耗的能量ECHtoCH中包含接收上一级簇头节点数据的能耗ETx和转发数据至下一级簇头节点的能耗ERx两部分,具体为:

ECHtoCH=ERx+ETx=

(4)

其中,dCHtoCH表示两个簇头节点的间距。

所有的簇头节点分为两类:第1类簇头节点,负责簇内数据传输;第2类簇头节点,充当中继节点转发其他簇数据[14]。第1类簇头节点的能耗由接收簇中节点数据的能耗ECH和发送簇中数据的能耗ECHto组成,第2类簇头节点的能耗由接收和转发其他簇头节点的数据能耗ECHtoCH和第1类簇头节点的能耗组成,具体为:

(5)

其中,Ech代表簇头节点能耗,ECHto根据式(1)计算得到。

2 节点部署方法与量化分析

在无线传感器网络中,通过节点部署对网络结构进行优化设计是延长网络实际应用寿命和扩大网络可延展性[15-16]的重要方法之一,尤其在带状区域中,通过设计传感器节点的部署结构能有效平衡网络能量消耗不均匀引起的能量空洞问题,延长网络生命周期。本节主要介绍了等距网络分簇方法,以菱形划分带状区域部署节点实现网络覆盖,并通过进一步计算验证了簇头节点的非均匀部署在延长网络生命周期方面的有效性。

2.1 基于菱形划分的节点部署方法

2.1.1 节点部署方法原理

针对带状区域的特殊结构,基于菱形划分区域并固定部署传感器节点,以等距分簇的方式来降低网络在数据传输过程中的能量消耗。

定义1(基本监测区域) 基本监测区域(Basic monitoring Area,BA)是以菱形为基本单元划分带状区域,在边界菱形顶点处部署传感器节点得到的带状监测区域如图1所示,其中两个节点只负责感知所在区域内的数据。

图1 菱形区域模型

定义2(一般监测区域) 一般监测区域(General monitoring Area,GA)是指只考虑通过两侧传感器节点的联合感知能有效覆盖的带状区域(如图2所示),且由BA线性组合而成。

图2 带状区域模型

定义3(簇) 簇可以划分为多个菱形,包括簇头节点和簇内节点两部分。簇内节点负责感知数据,簇头节点负责转发数据,且簇头节点初始部署在簇的中心位置。

定理1设两个簇头节点间的距离为di,基站与最远簇头节点间的距离为D,当d1=d2=…=dk=D/k时,网络中传输lbit数据的能耗Ek取值最小。

证明根据能量模型,在网络中传输lbit数据的能耗Ek为:

(6)

本文提出将带状区域划分为多个菱形后根据定理1所证结果等距分簇并部署传感器节点。假设基站部署在带状区域的左侧,将距离基站最远的簇定义为第一个簇,其簇头节点为一级簇头节点,根据与基站距离的变化依次为二级簇头节点、三级簇头节点、……、靠近基站最近的k级簇头节点,令整个带状区域具有分簇层次结构,且这k个簇头节点将距离D依次划分为d1,d2,…,dk。在这些簇头节点中,一级簇头节点产生的数据需经过剩余簇头节点的多跳转发,中间第i级簇头需要接收i-1级簇头节点所转发的数据,同时需要向i+1级簇头节点转发数据。

2.1.2 节点部署方法描述

基于菱形划分的节点部署方法具体步骤如下:

步骤1初始化长为a、宽为b的带状区域。

步骤3网络等距分簇,根据定理1可得,当d1=d2=…=dk=D/k时,网络中传输lbit数据的能耗Ek取值最小,因此对带状区域进行等距分簇。计算最佳分簇间距dopt和分簇后簇的最佳数目n,根据菱形大小得出簇内菱形个数。

步骤5在带状区域边界菱形顶点处部署簇内节点,在菱形对角线上线性部署簇头节点,网络工作初期选择中心位置作为簇头节点的初始位置,将其余簇头节点设为休眠状态。

步骤6在网络运行过程中,当簇头节点的能量低于可进行工作的最小值时,选择簇内的休眠簇头节点作为新的簇头节点进行替换,并广播新簇头节点的位置信息,代替失效节点继续工作。

2.2 节点部署的量化分析

上文利用等距分簇降低网络能耗的节点部署方法,本节主要通过计算并分析带状区域网络部署时的分簇个数和各簇内的最优簇头节点数量,实现监测区域的有效覆盖。

2.2.1 最佳分簇间距分析

(7)

图3 带状区域节点覆盖效果

当簇内节点A、B、C、D处部署的节点感知半径r=AG时,感知区域正好可以相交于菱形位于带状区域内的顶点G、I、F处,依此类推,即可对带状区域实现网络覆盖。证毕。

根据定理2求出带状区域可划分的菱形个数为:

(8)

结合定理1,簇头节点将菱形划分后的带状区域等距划分为相等的簇。对式(6)的能耗公式进行求导得到:

(9)

令E′k=0,可得最佳分簇间距dopt为:

(10)

在得到分簇结果后,网络中簇的最佳数目为:

(11)

在计算确定了网络监测区域的分簇个数和具体的菱形划分个数后部署传感器节点,在带状区域边界交汇的菱形顶点处部署簇内节点,在菱形对角线上部署簇头节点,并将簇头节点有选择地放在每个等间隔簇区间的几何中心上。

2.2.2 簇头节点数量的优化分析

为进一步均衡网络能耗,下文将分析并优化各簇内簇头节点的数量。在带状区域网络中簇头节点的数据转发量受到其与基站距离的影响,如果一个簇中只有一个簇头节点,各簇内簇头节点的能量消耗不均,靠近基站的簇中簇头节点无法长时间转发大量数据。因此,在靠近基站的簇内部署更多数量的簇头节点,会延长网络工作时间。

依据式(4)的能量模型,可计算簇i的能量消耗速度为:

(12)

簇i中耗尽所有簇头节点能量所需的时间为:

(13)

其中,Ni为簇i中的簇头节点数目,Einit为簇头节点初始状态下所具有的能量,E0为可进行工作的能量最小值。

令各簇能量耗尽的时间相等,即Ti=Ti-1,则有:

(14)

化简式(14)得到:

(15)

(16)

递推式(16)得到:

(17)

化简式(17)得到:

(18)

(19)

(20)

由式(20)可得越靠近基站的簇,i值越大,簇头节点的数量越多,如图4所示。在计算出不同簇内簇头节点的数目后,将这些簇头节点线性部署在各自的簇内。

图4 簇头节点非均匀部署效果

因此,在菱形划分的基础上对带状区域进行簇划分,确定等距分簇的最佳间距,计算得出每个簇内的最优簇头节点数量,将簇头节点在菱形对角线上进行线性部署。网络工作初期选择中心位置作为簇头节点的初始位置并将其余簇头节点设为休眠状态,当簇头节点的能量低于可供节点工作的最小值时更换簇头节点的位置。

2.3 网络能耗分析

在带状区域网络数据的发送和接收过程中,能耗主要由簇头节点产生,为有效降低和平衡网络能耗,本文在等距分簇的基础上,进一步在不同簇内部署非均匀数目的节点,并与簇头节点均匀部署方法进行对比,同时对分别采用两种方法的网络生命周期进行分析[17]。

根据本文能量模型,距离基站最远的簇头节点在接收和转发簇内节点数据的过程中会产生能耗,其进行一次数据接收并转发的总能耗为:

(21)

由于第i个簇头节点为中继节点,负责中继转发数据,因此在簇i中进行一次数据传输的能耗为:

Ei=(m-1)lEelec+(i-1)lEelec+

(22)

由式(22)可得在靠近基站的簇n中进行一次数据传输的能耗为:

En=(m-1)lEelec+(n-1)lEelec+

(23)

令各簇能量耗尽的时间相等,计算各个簇内非均匀的节点数目可知,整个带状区域网络的生命周期等同于第n个簇内簇头节点的生命周期,即:

(24)

在采用各簇内均匀部署簇头节点的部署方法时,每个簇内簇头节点的个数为N/n,靠近基站的簇数据传输量会直接影响网络的生命周期。在该簇中簇头节点接收数据的能耗为:

ETx=(m-1)lEelec+(n-1)lEelec

(25)

簇头节点转发所有数据的能耗为:

ERx=nl(Eelec+εfsdn2)

(26)

当均匀部署簇头节点时,簇n的总能耗En2为:

En2=ERx+ETx

(27)

由此可得网络生命周期为:

(28)

定理3在带状区域无线传感器网络等间距分簇的情况下,根据簇与基站的关系,簇头节点非均匀部署时网络生命周期大于簇头节点均匀部署时的网络生命周期。

证明根据式(23)和式(27)可得,在等距部署时,均匀和非均匀部署条件下靠近基站的簇内簇头节点进行数据传输的能量消耗相同,即:

En1=En2

(29)

(30)

由式(24)得到非均匀部署簇头节点时的网络生命周期Tnon-uniform为:

(31)

(32)

由此得到Tnon-uniform>Tuniform,证毕。

由定理3的证明得出本文提出的簇头节点非均匀部署方法相比簇头节点均匀部署方法更能延长网络生命周期,提高网络利用率。

3 实验设置与结果分析

3.1 实验环境与参数设置

为验证本文方法的有效性,在Matlab2016a中进行仿真实验,在具有理想MAC协议的假设前提下,忽略数据转发中的丢包问题[18]。仿真基本参数设置如表1所示。

表1 仿真参数设置

3.2 结果分析

本文主要是针对带状区域提出的节点部署方法,将带状区域网络划分为规模相同的簇,簇头节点分布在一条直线上,根据簇与基站间的距离非均匀部署簇头节点。

3.2.1 等距分簇方法性能分析

为得到等距分簇规模与网络存活节点数目及网络剩余能量的关系,在Matlab中仿真1 200 m×30 m的带状区域,簇内节点的感知半径为20 m,分别设置3种实验场景:场景1中簇间距d1为80 m,分簇个数n1为15,其小于最佳分簇个数;场景2中簇间距d2为60 m,分簇个数n2为20,其接近最佳分簇个数;场景3中簇间距d3为48 m,分簇个数n3为25,其大于最佳分簇个数。在仿真时,由式(20)计算簇头节点个数。

分析网络运行时的能耗情况,是评价节点部署方法的重要手段。图5表示在以上3种不同分簇场景中,带状区域内网络存活节点数目与网络工作时间的关系,可以看出随着网络工作时间的延长,存活节点数目不断减少。图6表示网络剩余能量与网络工作时间的关系,网络剩余能量随着时间的增长处于持续减少的状态。从图5曲线变化情况来看,网络运行至100轮时,3种实验场景中存活的节点数目几乎相同,这时网络消耗的总能量为最少状态。从100轮开始,在场景1中节点数目开始减少,以缓慢趋势减小到网络工作时间为500轮后,节点数目急剧下降,在670轮时网络结束工作。在场景3中,在工作时间为400轮时网络节点出现消耗并从700轮开始节点数目减少幅度加大,网络总体工作时间大于场景1下的网络工作时间。与场景1和场景3中的情况相比,在场景2中网络节点出现消耗的时间延后至650轮,当场景1和场景3中网络结束运行时,此场景中仍有大部分节点在继续工作,且网络工作时间几乎延长至1 000轮,远远大于场景1和场景3下的网络工作时间。结合图6曲线进行分析,在场景2中网络剩余能量高于其他两种场景,代表了在初始能量相同的状况下,在场景2中的网络能量消耗最小,有效节约了网络总体能量且延长了网络工作时间。实验结果表明:当1 200 m×30 m的带状区域分为20个大小相等的簇且间距取60 m时得到最优覆盖结果,可以有效降低整个带状区域网络的能量消耗。

图5 网络存活节点数随网络工作时间的变化情况

图6 网络剩余能量随网络工作时间的变化情况

3.2.2 簇头节点部署方法性能分析

网络生命周期和网络剩余能量是评价网络性能的重要指标[19]。为验证簇头节点非均匀部署方法的性能优势,选取长度为600 m、900 m、1 200 m、1 500 m、1 800 m、2 100 m、2 400 m,宽度为30 m的带状区域进行仿真实验。图7为不同带状区域长度内簇头节点数目在均匀和非均匀部署两种情况下的生命周期对比结果。图8为在实验进行500轮后,不同带状区域长度下两种部署方法的剩余能量百分比。

图7 网络生命周期随带状区域长度的变化情况

图8 网络剩余能量随带状区域长度的变化情况

从图7可以看出,当簇头节点非均匀部署时,网络生命周期明显更长。在不同长度的带状区域中,转发数据所需消耗的能量与簇头节点到基站的距离有关。通过簇头节点的计算公式可以得出,非均匀部署簇头节点时,靠近基站的第一个簇内簇头节点的数目最多,因此当各簇内簇头节点数目均匀且相等时,容易出现网络负载不均的问题从而影响网络整体的生命周期。该问题在带状区域长度为1 800 m时最为明显,非均匀部署的生命周期是均匀部署生命周期的1.8倍。采用非均匀部署方法时通过计算在越靠近基站的簇内部署更多的簇头节点,令各簇内能量耗尽时间保持一致,从而有效延长网络生命周期。从图8可以看出,在实验进行500轮后不同部署方法下的网络剩余能量百分比,当不同长度的带状区域中簇头节点数目非均匀部署时,各个簇的能量消耗速度较均衡,网络剩余能量百分比的变化稳定保持在20%左右。当簇头节点数目均匀部署时,由于簇头节点转发数据所需消耗的能量不均,更容易使网络提前结束,减少网络工作时间,并且有较多的剩余能量。随着带状区域长度的变化,非均匀部署方法在网络能耗均衡方面的优势越来越明显,并且网络剩余能量较为稳定,明显优于均匀部署方法。因此,本文采用簇头节点非均匀部署方法更为合理。

3.2.3 节点覆盖方法性能分析

为进一步验证本文节点覆盖方法在带状区域内的能量有效性,从存活节点数目、网络总能耗两方面与EDNU、EECS方法进行比较。为尽可能考虑实际应用情况,选取1 500 m×30 m的带状区域进行仿真,结果如图9和图10所示。

图9 网络存活节点数对比

图10 网络总能耗对比

图9和图10分别比较了在3种方法下网络工作时间变化和节点存活数目、网络总能耗的关系,可以看出在带状区域网络中,本文方法与其他两种方法相比更有优势。从图9可以看出,在分别使用3种方法时,网络开始运行至工作时间为400轮时,存活节点数目保持不变。从网络工作时间为400轮开始,EECS方法下的网络存活节点数目开始减少,在500轮～630轮减少幅度加大,当网络工作时间最长运行至800轮时,大部分节点已经死亡,网络结束工作[20]。EDNU方法在网络时间为540轮时存活节点数目发生变化,网络工作时间持续到900轮结束。而在本文方法中,节点数目的变化曲线更加平缓且网络工作时间更长,其中存活节点数目开始减少的时间发生在620轮时,当网络工作时间超过900轮时,网络仍有较多的存活节点,直至网络运行时间为1 000轮时才结束运行。本文方法与EDNU方法都是针对网络能耗不均衡且容易出现网络空洞问题提出的改进方法,两者都采用等距分簇和簇间多跳方式,但本文方法中网络工作时间相对EDNU方法显著延长。结合图10曲线分析可知,随着工作时间的增加和节点数目的减少,网络能量一直处于消耗状态,但在3种方法中,本文方法保证了最少的网络总能耗和更长的网络运行时间,性能优于其他两种方法。

图11比较了在网络工作时间不断增加时3种方法的网络数据传输时延。可以看出,本文方法的数据传输时延明显较小。在EECS方法中数据传输时延范围为0.6 s～0.8 s,EDNU方法保持在0.4 s左右,而本文方法数据传输时延始终保持在0.2 s以内,加快了带状区域中网络的数据传输速度,与其他两种方法相比更具优势。图12统计了3种方法在6次仿真实验中的网络数据传输成功率,可以看出本文方法的数据传输成功率明显高于其他两种方法。将6次实验结果进行对比分析可知,使用本文方法时数据传输成功率最高达到97%,最低为94%,EDNU方法的数据传输成功率为90%～93%,而使用EECS方法时的传输成功率低于88%。因此,在带状区域中本文方法在数据传输方面更具稳定性与可靠性。

图11 网络数据传输时延对比

图12 网络数据传输成功率对比

4 结束语

本文提出一种以菱形分区方式划分带状区域的WSN节点覆盖方法,通过等距分簇后在菱形固定位置部署传感器节点,实现对带状区域的网络覆盖。根据簇头节点与基站的距离计算不同簇内的簇头节点数量,从而尽可能均衡网络负载并提高网络利用率。理论分析与实验结果表明,本文节点覆盖方法能有效提高网络生命周期。后续将研究WSN节点部署方法中的覆盖冗余问题,进一步均衡网络能耗并延长网络生命周期。