基于种群阈值优化机制的WSN均衡覆盖算法

时间：2024-09-03

刘东旭

(滁州职业技术学院信息工程学院，安徽滁州 239500 )

0 前言

WSN(wireless sensor network，无线传感网)技术是大数据及人工智能技术发展的新方向[1]。WSN技术主要立足于智能传感技术，采取自组织方式组网并通过传感器将数据发送至基站节点(sink节点)，从而实现区域覆盖及数据感知[2]。由于传感节点同时具有易损特性，因此如何高效部署节点并提升节点均衡覆盖能力，成为当前研究的热点之一[3]。

实践中，主要采取策略部署、能量感知等方式提升节点的覆盖性能，在能量消耗可控的前提下尽量提高传感节点对区域的覆盖强度，以增强网络覆盖比例，减少因覆盖不到位而导致的区域空洞现象。文献[4]中提出一种基于节点分簇机制的WSN均衡覆盖算法，通过主备机制实现对区域的多重覆盖，采用周期交替休眠模式对区域进行重叠覆盖。采用该算法，可在很大程度上避免因节点失效而导致无法覆盖的问题，网络覆盖比例较高。但是，该算法因主备节点更换频繁而加剧能量消耗，易致节点受限，从而降低网络覆盖性能。文献[5]中提出一种基于聚类分簇机制的WSN均衡覆盖算法，对具有相似采集特性的节点进行聚类处理，以减少因区域分割而导致的重叠覆盖现象。该算法所选簇头节点的覆盖能力较强，能够适应链路抖动频繁的实际部署场景。但该算法也存在节点密度不均衡的特点，特别是网络传输率较高时易出现聚类冗余度较高的问题，使节点覆盖区域效果变差。文献[6]中提出一种基于链路切换机制的WSN均衡覆盖算法，对抖动频繁的所有链路进行主备节点变换处理，以减少因链路抖动而导致的节点覆盖能力下降问题。但由于链路切换过程中需要反复更换簇头节点，使得节点能量消耗问题难以控制，因而节点易出现大面积受限现象。

为了弥补上述方法的不足，本次研究将提出一种新算法 —— 基于种群阈值优化机制的WSN均衡覆盖算法。首先，在新算法中引入定位机制，对节点坐标及坐标漂移进行周期量化迭代，当传感节点覆盖度较高时即进行坐标更新处理，从而提高网络区域覆盖强度。同时，设计了基于阈值优化机制的节点均衡方法，引入簇内最低覆盖距离等参数，采取交叉判定方式降低节点迭代次数，改善重复覆盖现象，较好地起到了均衡覆盖的作用。最后，通过仿真实验验证算法的覆盖能力及节点离散性能。

1 WSN均衡覆盖算法设计

WSN均衡算法包括两部分：基于种群周期更新机制的定位覆盖和基于阈值优化机制的节点均衡。

1.1 基于种群周期更新机制的定位覆盖

首先，将网络节点视为粒子，各分区内的能量最优粒子即其区内能量最高的节点。将这些能量最优粒子设定为簇头节点(cluster head nodes，CH节点)，各粒子可根据定位算法[7]获取当前坐标X(x，y)和坐标漂移ΔX(x，y)。对所获取的坐标X(x，y)和坐标漂移ΔX(x，y)进行迭代，迭代模型为：

ΔX(x，y)[k+1]=X(x，y)[k]，

ΔX(x，y)[k]

(1)

ΔX(x，y)[k+1]=ΔX(x，y)[k]，

ΔX(x，y)[k]≥f[k+1]

(2)

式中：X(x，y)[k]表示第k个传输周期所获取的节点坐标；ΔX(x，y)[k]表示第k个传输周期所获取的坐标漂移；f[k+1]表示迭代裁决函数，获取模型为：

f[k+1]=min{f[k]，f[k-1]，…}

(3)

f[1]=ΔX(x，y)

(4)

对于迭代过程，需要考虑终止因素。这是因为，节点定位过程需要消耗能量，若频繁进行迭代将会导致节点能量受限而覆盖受阻[8]。在此，通过覆盖集中度(coverage concentration，CC)和覆盖次集中度(coverage sub concentration，CSC)函数对迭代过程进行控制。其相关定义满足以下模型：

(5)

(6)

当CC值接近于1时，说明各节点在第k次传输周期内均分布集中于簇头节点，此时需要进行迭代以便实现均衡覆盖。当CSC值接近于1时，说明各节点在第k次传输周期内均具有离散特性，分布较为均衡，无须进行迭代。图1所示为基于种群周期更新机制的定位覆盖流程。

按图1所示流程完成种群周期更新后，簇头节点即为能量最高的节点，其余节点可通过种群周期更新进一步实现分布离散化，从而扩大节点对区域的覆盖强度，提高网络覆盖质量。

sink节点为超级节点，因此其搜寻过程中的能量消耗可忽略不计，整个搜寻流程遵照模型(1)、(2)所示遍历算法。若种群中的粒子数为n，则搜索过程中的时间复杂度为o(n)，空间复杂度为T(n)。

1.2 基于阈值优化机制的节点均衡

由前述基于种群周期更新机制的定位覆盖方法可知，节点完成迭代过程后将围绕簇头节点并实现离散化分布。考虑到节点的移动特性[9]，进一步对其进行均衡处理，以便降低能耗及提高簇内覆盖比例。实现步骤如下：

Step1逐个获取簇内节点，按模型(7)获取覆盖阈值D(x，y)[k]：

(7)

式中：(x0，y0)表示簇头节点坐标；(x，y)表示当前节点坐标；l表示簇头节点最低覆盖距离。

Step2获取覆盖阈值D(x，y)[k]后，按模型(8)构建交叉判定阈值Δ[k]：

Δ[k]=D(x，y)[k]-D(x，y)[k-1]

(8)

Step3当且仅当Δ[k]大于0时，说明节点在第k个传输周期内可通过移动位置对簇内区域进行再覆盖，裁决方法如下：

Δ[k]>0，mov[k]

(9)

Δ[k]<0，mov[k-1]

(10)

式中：mov表示位移操作，位移距离lmov满足式(11)：

lmov=ΔX(x，y)

(11)

由此可知，节点在移动过程中的位移距离lmov将由交叉判定阈值Δ[k]决定，且节点移动过程均在簇内区域，移动的距离在数值上将不大于簇头节点最低覆盖距离；因此，节点与簇头之间的通信距离亦在1跳范围之内，节点在通信过程中的额外能量消耗将不会增加。但就簇头而言，其成员节点移动后的分布得到均衡，因此各节点间通信干扰亦得到缓解，从而使簇头的覆盖能力得到提高，实现与簇内节点通信整体能耗均衡。

Step4在获取节点位移后，算法将自动转入Step 1并获取下一个节点的覆盖阈值，本次流程结束。

在节点处于移动状态时，当且仅当其处于簇头覆盖范围内与簇头节点存在信息交互关系，按模型(9)、(10)进行裁决时将始终位于簇头节点的覆盖半径之内，因此通信过程中的能量消耗较为均衡。考虑到粒子覆盖过程具有周期特性，在能量最高节点的能量消耗增加时，可从剩余节点中选取能量较高的节点作为新簇头节点，并按模型(7)所示的阈值重新进行更新。因此，能量最优节点的更迭将不会影响到后续算法执行。

在实现了基于阈值优化机制的节点均衡之后，簇头节点将能发挥最大的覆盖作用，且其余传感节点与簇头节点间的距离较为均衡，节点间交叉覆盖现象出现的概率将显著降低，网络均衡覆盖效果得以提高，节点覆盖性能将始终保持较高的离散程度。此时，网络覆盖将达到最优状态。

2 仿真实验结果分析

以Matlab仿真平台作为实验环境验证算法的性能[10]，仿真参数如表1所示。对照组算法为当前无线传感网覆盖领域内常用的算法：基于对称探测机制的无线传感网空洞覆盖算法[11](symmetric algorithm for detection of coverage hole in wireless sensor network，SDCH算法)和基于最大目标匹配机制的无线传感网覆盖算法[12](maximum target coverage problem in mobile wireless sensor networks，MT算法)。选取2项仿真指标：网络区域覆盖率和离散节点数量。

表1 仿真参数表

2.1 网络区域覆盖率分析

对比本次算法与SDCH、MT算法在2种信道条件下的网络区域覆盖率测试结果，如图2所示。可以看出，本次算法具有网络区域覆盖率较高的特点，覆盖性能较优越。

图2 网络区域覆盖率测试

本次算法中，针对节点重复覆盖问题设计了基于种群周期更新机制的定位覆盖方法和基于阈值优化机制的节点均衡方法。其中节点可通过反复迭代的方式对目标区域进行多次覆盖，且能够通过阈值模式调节迭代次数及方位，网络区域覆盖强度较大，因而区域覆盖率较高。

SDCH算法中，根据网关性能参数、网关选择准则函数和对称函数，建立了基于对称网络模型的节点覆盖机制，利用多径传输优化因子计算相似度，采用加权平均法检测无线传感器网络的覆盖空洞，可消除因覆盖不完全而导致的节点失效现象。然而，该算法未通过再覆盖方式对节点进行移位处理，难以适应拓扑变动较快的部署环境，易发生节点失效现象，因此网络区域覆盖率相低于本算法。

MT算法中，采用启发模型对覆盖区域进行着色，降低了因拓扑变动较快而导致的覆盖失效现象。该算法所选簇头节点能量较低，未采用迭代机制对簇头节点进行更迭处理，所布节点分布较为集中。因此，该算法的网络区域覆盖率亦显著低于本算法。

2.2 离散节点数量分析

对比本次算法与SDCH、MT算法在两种信道条件下的离散节点数量测试结果，如图3所示。可以看出，本次算法具有离散节点数量较大的特点，显示出了较强的均衡覆盖特性。

图3 离散节点数量测试

本次算法中，针对拓扑变动较快而导致的网络区域覆盖性能下降现象，设计了基于种群周期更新机制的定位覆盖方法用以提升节点部署性能。特别是针对节点频繁迭代而出现的能量受限问题，设计了基于阈值优化机制的节点均衡方法，可在降低节点能量消耗水平的前提下提高节点离散性能。对比之下，本次算法的离散节点数量较高。

SDCH算法中，基于对称网络模型设计了一种新的节点覆盖机制，主要采用网关性能参数、网关选择准则函数和对称函数，并通过相似度模型监测覆盖空洞现象，以提高节点的覆盖性能。不过，该算法中未采取周期机制提升节点覆盖效率，所选簇头节点易因频繁监测而出现受限现象，节点覆盖性能较差且分布较为集中。因此，该算法的离散节点数量相对低于本次算法。

对于MT算法，其主要采用启发模型来完成网络覆盖，但是其所选择的簇头节点性能不佳，随着网络运行时间的延长，其能量被快速消耗，导致其覆盖效果较差，从而使得离散节点大幅增加。