无线传感器网络能量均衡混合拓扑维护策略

耿 鹏,郝慧珍,柳 艳,叶子馨

(1.南京工程学院信息与通信工程学院,江苏 南京 211167;2.南京工程学院数理学院,江苏 南京 211167)

0 引言

无线传感器网络(wireless sensor networks,WSN)在军事领域里的应用环境通常十分恶劣,且是无人值守的[1-2]。WSN由大量的传感器设备组成,这些传感器设备由电池供电。在无人值守条件下,电池很难再次充电或更换。因此,采取相应措施进行能量均衡以延长网络生命周期是WSN面临的最重要挑战之一。在此方面的研究中,利用相应的拓扑控制策略来减少节点能量均衡是一种关键技术。以往的研究往往将拓扑控制看作一个单一的过程,注重了拓扑构建与重构,而忽略了拓扑维护的重要性。近年来,拓扑维护逐渐被重视,取得了一定的研究成果。文献[3]将功率控制技术引入到拓扑维护之中,提出了一种基于功率自适应的动态拓扑维护算法,该算法节省了传感器节点的平均发射功率,但由于需要实时维护全局网络的功率信息,其所产生的网络开销较大,且收敛时间较长。文献[4]首先基于节点剩余能量对网络进行拓扑构建,再利用收发控制消息来判断网络拓扑结构是否发生变化,最后根据变化的因素设计拓扑维护方法。该方法可以看作是基于能量触发的拓扑维护,触发条件较为单一。文献[5]通过自适应调整拓扑控制消息,提出了一种低开销的拓扑维护算法,提高了优化链路状态路由协议的性能。该算法在邻居发现策略方面产生了较多的冗余,对网络性能有一定的影响。文献[6]利用博弈算法在节点密度较大的区域进行再博弈、再分割,选出新的簇头,在节点密度较小区域进行多簇合并,以达到均衡节点能耗的目的。该算法可以看作是基于密度的拓扑维护,其既要实时探测瓶颈节点,又要判断区域密度,增加了网络开销。文献[7]分析了网络生命周期和节点剩余能量、节点间距离的关系,据此提出了一种网络拓扑结构动态演化的模型,提高了无标度网络的生命周期。该模型本质上是基于能量和节点密度的拓扑重构,无拓扑维护过程。文献[8—9]通过拓扑控制技术来增加网络幸存节点数和减少因级联失效而产生的故障节点数,此技术并没有考虑到在拓扑构建时简化网络结构。文献[10—12]在保证覆盖率的前提下,使部分节点处于休眠状态,以减少能量消耗,但此方法没有引入拓扑维护技术,在节点能量均衡方面较为缺乏。文献[13—15]研究了网络自愈技术,当发现网络中存在覆盖漏洞时,便启动相应算法进行修补,由于是一种查漏补缺策略,此类技术对于数据敏感度较高的军事应用并不适合。

从上述内容可以看出,目前对拓扑控制技术的研究一是存在将拓扑重构与拓扑维护相混淆的问题,二是存在拓扑构建阶段无简化过程的问题,三是存在拓扑维护算法复杂,增加了网络开销的问题。据此,本文在利用生成树算法进行拓扑简化的基础上,提出一种基于能量均衡的混合拓扑维护策略,以达到实现WSN节点能量均衡,延长生命周期目的。

1 拓扑构建算法与拓扑维护策略选择

通过对文献[3—15]的总结,可将恶劣环境下的无线传感器网络部署与拓扑控制分为三个阶段:第一,在目标区域中随机撒下多个传感器节点,并进入网络初始化阶段,在该阶段,考虑到位置未知网络,每个传感器节点发现邻居,然后建立通信路径,并形成初始拓扑结构;第二,创建一个新的简化拓扑,称之为拓扑构建阶段,在这一阶段,基于初始拓扑结构形成连接支配集(connection dominating set,CDS),以构建确保连接性和高覆盖率的虚拟骨干网络(virtual backbone network,VBN),VBN中的节点处于唤醒状态,而其他节点处于休眠状态;第三,VBN运行一定的时间,直到时间片到或某些节点的能量水平低于某个阈值时,网络返回到拓扑构建阶段以建立新的VBN。在WSN的生命周期内,此循环将重复多次,称之为拓扑维护阶段。

1.1 拓扑构建算法

在拓扑构建阶段,常用的算法包括:A3[16],A3Cov[17],EECDS[18]和CDS Rule K[19]。其中,A3和A3Cov基于生成树(spanning tree,ST)算法[20],EECDS基于最大独立集(maximum independent set,MIS)算法[21],CDS Rule K基于连通支配集(connected dominating set,CDS)算法[22]。在WSN的拓扑构建中,利用上述算法进行拓扑构建完成后,就形成了不同类型的VBN。从文献[23—24]的对比分析中可以看出,在相同网络初始化条件下,A3Cov在拓扑构建阶段激活了更多节点,使得覆盖率性能最佳,但带来的缺点是网络生命周期大大缩短。A3,EECDS和CDS Rule K的覆盖性能相似,但A3在同一时间段内的网络剩余能量性能最佳。根据图1所示的随机网络部署,将汇聚结点(Sink)置于矩形区域的中心,传感节点通信半径设置为100 m,感知半径设置为20 m,使用A3和A3Cov算法构建的VBN如图2和图3所示。

图1 随机网络部署Fig.1 Random network deployment

图2 利用A3算法构建的VBNFig.2 VBN constructed by A3 algorithm

图3 利用A3Cov算法构建的VBNFig.3 VBN constructed by A3Cov algorithm

将各算法挑选出来的骨干节点连接起来便形成了VBN,其他节点暂时处于休眠状态。图中黑色区域表示能量覆盖区域,白色区域表示能量空穴,浅色区域表示感知覆盖区域。可以看到,A3Cov算法在能量覆盖和感知覆盖方面表现最好,但其激活的节点数却远多于A3算法。A3利用较少的活动节点保证了区域基本覆盖,有利于生命周期的延长。本文将选择A3算法进行拓扑构建。

1.2 拓扑维护策略

在拓扑维护阶段,需要监控网络拓扑状态,并在适当时候触发新的拓扑构建。拓扑构建和拓扑维护之间的循环将在生命周期内重复多次。因此,拓扑维护可以定义为当拓扑结构不再最佳时,局部修改或全局重新创建网络拓扑的过程。

从拓扑构建阶段进入拓扑维护阶段所需要的触发条件包括时间片到、达到节点能量阈值、达到故障节点数和平均节点度触发等,具体描述如下。

1) 基于时间的拓扑维护:设置一个时间片,时间片到时,拓扑维护算法将终止当前简化拓扑,并调用拓扑构建算法来创建新的拓扑。定义拓扑构建集合中的节点处于就绪状态,显然,网络中有3种节点状态:就绪状态、运行状态和休眠状态。网络中每个节点状态描述如图4所示。

图4 节点状态转移图Fig.4 Node state transition

2) 基于能量的拓扑维护:每当节点达到临界能量阈值时,拓扑维护算法就会终止当前简化拓扑,并调用拓扑构建算法来创建新的拓扑。网络中仍然具有图4所示的3种节点状态,不同的是,节点的状态从“运行状态”转变为“休眠状态”的条件是“任一节点能量低于阈值”。

3) 基于故障的拓扑维护:当一个或多个节点发生故障时,会触发更改当前拓扑的过程。显然,此策略需要故障检测和通知方法的支持,将形成新的网络开销。

4) 基于密度的拓扑维护:节点度可用于描述网络密度,在网络节点平均度降低到一定程度后触发改变当前拓扑的过程。该方法需要实时计算网络的节点度,同样也增加了网络开销。

另外,拓扑维护的最终目标是延长网络寿命。在设计过程中,必须考虑以下方面。

1) 动态拓扑维护:拓扑维护可分为静态方法和动态方法。静态方法将拓扑信息存储在节点存储器中,并在需要时打开。动态方法是仅当网络运行中触发某个阈值条件时才构建拓扑。静态方法需要大量内存来存储所有预先计算的拓扑,但是WSN的节点设备内存是有限的,因此应考虑动态拓扑维护。

2) 低开销:拓扑维护不应包含太多控制数据包。如基于能量、故障和密度的拓扑维护方法,均需要实现通知机制。因此,为了降低网络开销,上述三种方法不能全部考虑。

3) 低复杂性:拓扑维护中使用的算法必须简单。显然,基于时间的拓扑维护算法是最简单的。

4) 能量均衡:当某些节点能量消耗到一定程度时,应该允许它们休眠一段时间,以便所有节点都能均衡地参与网络。在这方面,基于能量的拓扑维护算法是合适的。

2 基于能量均衡的混合拓扑维护策略

综上,本文选择A3算法进行拓扑构建,考虑到无线传感器网络在恶劣环境下的应用场景,提出一种时间和能量混合拓扑维护策略,以达到实现节点能量均衡的目的。

2.1 拓扑构建阶段

A3算法生成树的过程包括3个阶段:邻居发现、子节点选择和二次选择。其中在邻居发现阶段,节点的状态权值Mx,y描述为

(1)

式中:x是y的后一跳节点,WE是节点剩余能量权值,Ex是节点x的剩余能量,Emax是节点x初始化的最大能量,WD是上下跳节点之间的距离权值,Ry是节点x从节点y接收到的信号强度,Rmin为确保两个节点连接的最小信号强度。可以看出,该公式优先考虑那些具有更高能量且距离父节点更远的节点作为子节点,期望构建具有更少节点和更好覆盖的树。

2.2 基于时间和能量的混合拓扑维护

在恶劣环境中,节点能量是极为宝贵的资源,而拓扑维护作为一种能量管理策略,可以帮助节点有效地利用能量,延长网络生命周期,并提高网络性能和可靠性。基于时间和基于能量的拓扑维护算法是较为有效的拓扑维护方法。其中,基于时间的方法主要关注时间片的长度,在时间片结束时进行拓扑维护,维护网络的稳定性和效率。而基于能量的方法则主要基于节点的能量消耗情况来进行拓扑维护,及时使能量消耗过大的节点进入休眠状态,并重新构建拓扑结构,从而延长节点生命周期,提高网络性能和效率。

本文混合了基于时间和基于能量的方法进行拓扑维护,即当节点能量消耗到一定阈值或网络运行到时间片结束时,拓扑维护算法终止当前的拓扑结构,并再次调用拓扑构建算法以创建新的网络结构。其处理流程如图5所示。

图5 基于混合策略的拓扑维护流程图Fig.5 Hybrid-based topology maintenance flowchart

对于WSN,由普通节点收集的所有信息都以多跳形式传输到Sink节点,因此,Sink节点附近的普通节点的通信任务是最重的。本文在进行初始化时,网络处于全连接状态,并且生命周期被定义为从网络运行开始直到Sink节点成为孤立节点。基于时间和基于能量的拓扑维护的主要目的是构建简化的主干结构,以便可以用较少的活动节点来获取较大范围的数据收集。基于此,将“生命周期”、“活动节点数”和“通信覆盖率”的性能指标定义如下:

1) 生命周期:从网络运行开始到Sink节点成为孤立节点所经历的时间。

2) 活动节点数:可以与处于运行状态的Sink节点通信的普通节点数量。显然,它可以用来分析生命周期,当进行过新的拓扑构建后,活动节点数仍为零时,标志着生命周期的结束。

3) 通信覆盖率:该度量定义为活动节点的覆盖面积与目标区域面积的比率。

3 仿真分析

在600 m×600 m的区域内,于中心位置部署一个Sink节点,并另外随机部署100个普通节点。网络运行过程中,节点发送和接收1 bit数据所消耗的能量分别表示为ETbit和ERbit,具体描述为

ETbit=ERbit+Eamp·(π·r2),

(2)

ERbit=Eelect,

(3)

式中:r表示节点通信半径,Eamp是功率放大器消耗的能量密度,Eelect为电路损耗能量。

本文在Java平台下,基于时间和能量控制策略,对A3拓扑构建下的活动节点数和通信覆盖率进行了对比。其参数设置如表1所示。

表1 模拟参数Tab.1 Simulation parameters

在拓扑维护阶段,混合了基于时间和能量的策略,即当节点达到临界能量阈值200 mJ或网络在运行1 000 s时(即时间片设置为1 000 s),终止当前的拓扑结构并调用A3拓扑构建算法以创建新的拓扑。节点从“运行状态”变为“休眠状态”的条件是“时间片到或节点能量低于阈值”。在表1的模拟参数下,基于时间控制的A3、基于能量控制的A3和基于混合控制的A3性能比较如图6—图7所示。

图6 不同控制策略下的生命周期比较Fig.6 Lifetime comparison based on different control strategies

图7 不同控制策略下的通信覆盖率比较Fig.7 Communication coverage comparison based on different control strategies

图6显示的是网络活动节点数随时间的变化,当活动节点数完全降低到0时,生命周期结束。可以看出,基于时间控制的A3和基于能量控制的A3的寿命在大约8 300 s和9 500 s时结束。基于混合控制的A3在12 000 s时结束。同时,在网络运行中,基于混合控制的A3算法中的活动节点的数量总是比其他算法多。

图7显示的是通信覆盖率随时间的变化。在网络运行初期,基于混合控制的A3通信覆盖率达到97%,优于另外两种拓扑控制策略。WSN对目标区域的通信覆盖必须要达到一定比例,否则其采集的数据参考价值将降低很多。本文以实现90%以上的通信覆盖率作为标准。从图7可以看出,基于混合控制的A3算法在覆盖率阈值内的时间为4 800 s,优于基于时间控制的A3(大约2 000 s)和基于能量控制的A3(约4 000 s)。

仿真结果表明,本文所提出的混合拓扑维护策略使网络生命周期最大提升了44.6%,90%覆盖率结束时间最大增加了1.4倍,表明在基于时间和能量的混合拓扑维护策略下,网络性能有较大提升,具体如表2所示。

表2 不同策略下的网络性能Tab.2 Network performance based on different strategies

4 结论

本文针对现阶段无线传感器网络中降低能耗以延长网络生命周期的相关研究,指出了其在无人值守的特殊环境下应用的局限性。基于此,将恶劣环境下的无线传感器网络部署与拓扑控制分为网络初始化、拓扑构建和拓扑维护3个阶段。在随机部署和虚拟骨干网络构建的前提下,提出一种时间和能量混合拓扑维护策略。通过在Java平台上的仿真,对基于时间控制的A3、基于能量控制的A3和基于混合控制的A3算法进行活动节点数和通信覆盖率的性能比较。结果表明,基于混合控制的拓扑构建算法性能最优,能够更好地降低网络能量消耗,为诸如军事领域中恶劣环境下的无线传感器网络部署和拓扑控制提供了参考。