煤矿井下WSN能量均衡的节点部署算法研究*

崔丽珍,许凡非,王巧利,李丹阳

(内蒙古科技大学信息工程学院,内蒙古 包头 014010)

无线传感器网络WSN(Wireless Sensor Network)是由部署于目标监测场地内的大量传感器节点组成的网络系统,这些节点具有体型小、价格低、功耗低等特点。传感器节点的应用环境通常比较复杂,且节点能量有限,因此特定场景下网络的生存周期问题成为WSN研究的重要内容之一错误!未找到引用源。。通过WSN的节点部署和覆盖控制技术能够对节点进行灵活部署,满足不同应用场景的需求,可提高网络的覆盖率和连通性,减少网络的能量消耗,进一步延长网络的生存周期,将该技术应用到煤矿井下能够有效地提高信息传输的可靠性,减少事故发生隐患,保障煤矿井下生产人员的生命财产安全[1]。

Wadda等人的研究表明[2],在节点数量均匀部署中,由于距离Sink节点位置越近的节点能量消耗越快,当Sink节点一跳范围内的节点因能量耗尽而死亡时,整个网络的传感器节点仍然存在高达93%的能量没有使用。Perillo等人分析了均匀部署中能量消耗的两种情况[4],在第一种情况中,节点通过多跳的方式将感知到的信息发送给Sink节点,使得中间节点需要发送自身信息的同时还需要转发其他节点的感知信息,导致距离基站越近的节点负载越大,生存时间越短。在第二种情况中,网络中的节点都需要将自身感知到的数据直接传输给Sink节点,导致距离基站越远的节点的能量消耗越快。同时提出了一种节点通信半径可变机制,但是在实际应用中,节点的通信半径是是由硬件及环境条件决定的。Luo J等人提出一种采用移动Sink节点和数据路由结合的方法[5]来均衡网络的能量消耗,避免了网络中能耗的不均衡,但是该方法会导致费用的大量增加,并且移动Sink节点无法在井下环境中得到应用。

针对以上问题,本文提出了一种基于能量均衡的节点部署算法。该算法根据实际情况将煤矿井下的巷道划分成覆盖面积大小相等的若干个簇,通过计算每个簇的能量消耗来确定簇内节点的部署数量,同时利用分簇算法计算每个簇内的能量消耗情况,尽可能实现各个簇的能量同时耗尽,达到延长网络的生存周期的目的。

1 覆盖模型

传感器节点覆盖模型采用最基础的二元感知模型[6],该模型下节点的感知区域是一个以节点位置为圆心,半径为Rs的圆,Rs为节点感知半径。对于发生在感知圆范围内的事件的感知概率为1;发生在感知圆范围外的事件的感知概率为0,即

(1)

式中:P(i,s)代表节点i对目标s的监测概率,d(i,s)代表目标s发生地到节点i的欧氏距离。

2 分簇算法

针对LEACH算法经过多轮选举后节点剩余能量存在较大差异的问题,出现了LEACH-B、LEACH-C等改进的算法[8-9],本文根据节点剩余能量的多少来选取簇头,节点剩余的能量越多,当选簇头的机率越大;反之,当选簇头的机率越小[10-11]。节点在t时刻成为簇头的概率P(t)的计算公式为:

(2)

式中:c为簇头个数,Ei(t)是第i个节点的当前剩余能量,Etotal(t)是所有传感器节点的剩余能量之和,即

(3)

3 基于能量均衡的部署算法

在巷道节点均匀部署情况下,每个簇内的节点除了要感知自身所在区域的数据信息外,还需要接收后一个簇转发过来的数据,并且将所有的数据发送给前一个簇。因此,离基站越近位置的簇内,网络负载越大,能量消耗的就越快,容易出现能量空洞[12]。针对这一问题,本文设计了一种能量均衡的节点部署算法。该算法将煤矿井下巷道划分成面积大小相等的若干子区域,即划分成簇的形式,计算出每个簇中节点的能耗情况,依据各簇节点能耗比例确定各区域内需部署的节点数量,使得所有簇的能量消耗按比例下降,最后所有子区域中的网络能量同时耗尽,以此延长网络的生存周期。

如图1所示,将巷道等效为长带区域,设离基站最近的簇S1为起点,离基站最远的簇SM为终点,从起点到终点编号依次是S1,S2,…,SM。

图1 巷道分区模型图

网络中节点能量消耗分为三个部分,感知信息消耗Psense、发送信息消耗PTx、接收信息消耗PRx,基本计算公式如下:

Psense=EDAy

(4)

(5)

PRX=ERXy

(6)

设Ni,Ei,Ai,M分别表示簇内节点个数、单位时间内的能量消耗、面积以及簇的个数,c表示单位面积内产生的数据流量。每个簇分别由感知数据能量消耗、接收数据能量消耗和发送数据的能量消耗三部分构成,最后一个簇SM不需要接收数据,所以它消耗的能量为:

(7)

其他子区域中所消耗的能量为:

(8)

综合上面两个公式可以得到任意一个簇所消耗的能量为:

(9)

由于每个簇内放置的节点数目都不相同,依照每个簇内节点总消耗能量可确定各簇内节点的部署数量,因此,每个簇的网络生存时间应满足关系式:

(10)

(11)

式中:α是一个比例系数

(12)

由于所有簇的面积大小都相等,即Ai=A,有

(13)

4 簇内节点部署

根据上节中的方法可计算出每个簇内需部署的节点数量,节点的具体部署形式采用如图2所示的方法。

图2 节点部署模型图

图2中黑色实线为井下巷道边界,节点依次部署在巷道两侧,同时在巷道尽头处放置一个节点。其中,巷道两侧节点分别选用不同的通信频率(或不同的传输信道),可与同侧相邻节点直接通信。巷道中间节点为双频节点,可同时接收巷道两侧节点的信号。这种网络部署结构的优势一方面在于一旦某个节点失效,可以由巷道另一侧的节点继续通信,进而增强了网络的健壮性;另一方面由于巷道两侧节点采用了不同的通信频率,这样可以同时传输数据,提高了数据传输效率。

针对相邻两个节点间的位置部署可分为以下三种情况(图3中黑粗线轮廓为节点N1与N2对巷道的覆盖范围):

图3 相邻两个节点间的位置部署

图3(a)中,节点N1与N2的部署结构对巷道的覆盖存在盲区(阴影部分),针对井下环境,通常需要达到尽可能精确的监测,因此这种情况的部署结构不适合实际应用。

图3(b)中,节点的部署结构可以对巷道实现无缝覆盖。节点N1与N2的覆盖圆相交于一点p,且点p位于巷道边缘上,设巷道宽度为d,此时两节点对巷道的覆盖面积S包括3个部分:中间梯形面积S1和两端扇形面积S2与S3。即

(14)

(15)

α=arcsin(d/RS)

(16)

S2=S3

(17)

S=S1+S2+S3=3d×L+2S2

(18)

图3(c)中,节点的部署结构同样可以对巷道实现无缝覆盖。节点N1与N2的覆盖圆相交点位于巷道边缘外,相比图3(b),扇形面积S2与S3不变,但由于节点N1与N2的重叠面积增加导致梯形上底与下底长度缩小,梯形面积S1相应减小,因此总面积S小于图3(b)。

综合以上三种节点部署情况的分析,图3(b)中的部署结构最佳,在确保对巷道进行无缝覆盖的同时,节点对巷道的有效覆盖面积最大,覆盖效率最高。

由第2节中每个簇的能耗和节点数量比例关系可知,每个簇内的节点部署数量都不一样,而对于面积相等的各簇,按照图3(b)中固定的节点部署结构,每个簇内所需要部署的实际节点数量都相等。因此,针对这一问题,本文采用多个节点覆盖集的部署方式,即在最后一层子区域内巷道两侧部署的节点数量取图3(b)所示部署方式下一重覆盖所需的节点数,内层各簇依次按比例计算各自所需部署的节点数量,与最后一个簇的比值即为该层子区域的覆盖集数。同一时间,只允许其中一个覆盖集处于工作状态,其他覆盖集休眠,当前覆盖集节点能量全部消耗完毕时再唤醒下一个覆盖集工作,直至最后一个覆盖集工作停止。

图4 多覆盖集节点部署模型图

对于多个覆盖集的节点部署问题,本文采用错位部署方法,每个覆盖集中对应位置上的节点在实际部署中要错位部放,如图4所示,以三重部署为例,在某一个巷道子区域内,编号为1的节点表示第一重覆盖集,编号为2的节点表示第二重覆盖集,编号为3的节点表示第三重覆盖集。

5 算法实现

5.1 算法设计

根据井下巷道相关物理特性,将其等效成一个二维的长带区域,设定巷道长度L和宽度W。本文算法具体步骤如下:①结合巷道长度L及节点感知半径Rs对巷道进行均匀分区,每个子巷道都同构;②根据能量均衡推导公式计算各簇所需部署的节点数量比值;③计算在图3(b)节点部署模型下一个簇内所需部署的节点数,并将此数量作为最外层簇节点部署的实际数量;④将第③步求得的节点数作为一个数量单位,按照第②步的比值计算其他簇内对应的节点实际数量;⑤在每个簇内将固定数量的节点按照图3(b)所示结构进行单个覆盖集部放,多个覆盖集的子区域内各覆盖集中的节点实际位置按照图4所示形式进行部放。⑥根据式(2)、式(3)选取簇头,簇成员节点将感知到的信息发送给簇头节点,簇头节点将接收到的数据信息传输给下一个簇头,依次传递数据直到基站。

5.2 实验结果分析

本文算法以CC2530节点的基本参数为标准,使用MATLAB对混合算法进行仿真。在仿真实验中,设节点的初始能量为E0,数据包长度为ld,控制包长度为lc。各参数设置如表1所示。

表1 算法参数设置

图5 非均匀部署算法覆盖率变化趋势图

图5为采用均匀部署的分簇算法与本文基于能量均衡的分区部署分簇算法性能对比图,分析了两种算法覆盖率随着工作轮数的变化情况。

由图5可以看出,均匀部署分簇算法的覆盖率保持为100%的时间较短,而本文基于能量均衡的分区部署分簇算法的覆盖率持续为100%的时较长,说明了本文算法对于网络覆盖具有较好的稳定性,可增强网络的覆盖性能。其次,本文算法的覆盖率比均匀部署分簇算法的覆盖率的衰减幅度要大,由于本文算法根据各个簇的节点总体能量消耗比值来进行节点部署,使得负载越大的簇的节点数量越多,总体的能量越多,从而均衡了网络负载能耗、延长了网络的生存周期。

图6为均匀部署的分簇算法与本文基于能量均衡的分区部署分簇算法在网络节点能量均值方面的性能比较。由图6可以看出,随着网络工作轮数的增加,两种算法的能量均值都在下降,但本文算法的下降幅度相对较小,说明了本文算法在每轮工作中所需能耗较低,有效节约了网络能量,进而起到延长网络生存。

图6 非均匀部署算法覆盖率变化趋势图

6 结束语

本文提出了一种基于能量均衡的节点部署算法,该算法将煤矿井下巷道划分成覆盖面积大小相等的若干个簇,依照每个簇内节点总体消耗的能量决定簇内节点的部放数量,即各个簇的节点数量和簇内节点总体的能量消耗成正比,之后依据节点覆盖效率最大化原则在巷道两侧部署节点,在多个覆盖集的簇中采用错位多层覆盖的方法。实验结果表明,该算法可有效的延长网络的生存周期,具有较强的理论和应用价值。