CN113242562A - 一种WSNs覆盖增强方法及系统 - Google Patents

Abstract

本发明涉及一种WSNs覆盖增强方法及系统，该方法包括：根据监测区域中传感器节点和网格点计算WSNs覆盖率；将所述WSNs覆盖率最大作为适应度函数；在所述适应度函数的约束下，采用改进的蚁狮优化算法对蚂蚁种群位置和蚁狮种群位置进行特定次数迭代更新；在迭代结束后，将所述改进的蚁狮优化算法中的精英蚁狮对应的传感器节点最佳部署策略输出。通过采用改进的蚁狮优化算法计算二维部署环境下传感器节点最佳部署策略，使监测区域中的传感器节点分布更加均匀，避免覆盖空洞和节点的大量冗余，降低了传感器节点布置成本和能耗，提高了WSNs网络覆盖率，实现了利用尽量少的传感器节点对指定监测区域的感知覆盖和通信覆盖的最大化部署。

Description

一种WSNs覆盖增强方法及系统

技术领域

本发明涉及无线传感网络技术领域，特别是涉及一种WSNs覆盖增强方法及系统。

背景技术

WSNs(Wireless SensorNetworks，无线传感器网络)由部署在指定区域的大量微型、智能、低功耗的传感器节点组成，其功能是协作地感知、采集和处理网络覆盖区域中的信息和数据，并发送给网络的所有者。近年来，WSNs已经融入到社会的方方面面，被广泛用于农业生产、智能家居、城市交通和环境监测等领域。

随机部署WSNs的方式存在一些传感器节点分布不均匀而导致覆盖空洞和节点的大量冗余的缺点，因此需要将随机部署的传感器节点进行移动实现二次部署。现有技术中常常利用传统的蚁狮优化算法解决传感器节点二次部署中的最优部署问题，然而这些算法在优化过程中存在陷入局部最优解、全局寻优能力弱等缺点，从而导致WSNs的覆盖效果并没有大的提高。

因此，亟需一种WSNs覆盖增强方法及系统。

发明内容

本发明的目的是提供一种WSNs覆盖增强方法及系统，以解决二维部署环境下的WSNs覆盖控制问题，提高网络覆盖率。

为实现上述目的，本发明提供了如下方案：

一种WSNs覆盖增强方法，包括：

根据监测区域中传感器节点和网格点计算WSNs覆盖率；

将所述WSNs覆盖率最大作为适应度函数；

在所述适应度函数的约束下，采用改进的蚁狮优化算法对蚂蚁种群位置和蚁狮种群位置进行特定次数迭代更新；

在迭代结束后，将所述改进的蚁狮优化算法中的精英蚁狮对应的传感器节点最佳部署策略输出。

可选的，所述采用改进的蚁狮优化算法对蚂蚁种群位置和蚁狮种群位置进行特定次数迭代更新，具体包括：

初始化蚂蚁种群和蚁狮种群的种群规模，将初始化的所述传感器节点位置作为初始蚂蚁种群和初始蚁狮种群任一个体的位置，并在所述任一个体周围产生其余个体的位置；

根据初始化的蚂蚁种群和蚁狮种群的种群规模，分别计算蚂蚁种群初始覆盖率和蚁狮种群初始覆盖率；

比较所述蚂蚁种群初始覆盖率和所述蚁狮种群初始覆盖率，将两者中最优的种群初始覆盖率对应的种群重新赋值给初始化的蚁狮种群，得到赋值后的蚁狮种群；

将所述赋值后的蚁狮种群中初始覆盖率最大的蚁狮个体作为初始精英蚁狮；

采用轮盘赌策略在设定的竞争蚁狮中选择被围绕蚁狮；

根据所述被围绕蚁狮和所述初始精英蚁狮控制蚂蚁游走，更新蚂蚁种群位置；

根据更新位置后的蚂蚁种群的适应度值更新赋值后的蚁狮种群位置，得到新的蚁狮种群；

将所述新的蚁狮种群适应度值与所述初始精英蚁狮的适应度值比较，选择两者中适应度值最大的对应的蚁狮位置为本次迭代的精英蚁狮位置；

判断迭代次数是否达到特定迭代次数；

若所述迭代次数达到所述特定迭代次数，则输出精英蚁狮位置以及所述精英蚁狮位置对应的传感器节点最佳部署策略；

若所述迭代次数没有达到所述特定迭代次数，则返回“比较所述蚂蚁种群初始覆盖率和所述蚁狮种群初始覆盖率，将两者中最优的种群初始覆盖率对应的种群重新赋值给初始化的蚁狮种群，得到赋值后的蚁狮种群”步骤。

可选的，所述设定的竞争蚁狮计算公式为：

其中，pop(t)表示第t代设定的竞争蚁狮数量；round表示取整函数；T表示特定迭代次数；[pop_min,pop_max]表示参与竞争的蚁狮范围。

可选的，所述根据所述被围绕蚁狮和所述初始精英蚁狮控制蚂蚁游走，更新蚂蚁种群位置，具体包括：

根据所述被围绕蚁狮位置和自适应边界收缩因子，更新蚂蚁游走边界；

在所述蚂蚁游走边界约束下，根据精英蚁狮位置和所述被围绕蚁狮位置控制蚂蚁游走，得到第一更新公式；

根据所述第一更新公式更新蚂蚁种群位置；

判断当前种群的蚂蚁只数是否达到上限值；

若当前种群的蚂蚁只数达到上限值，则蚂蚁种群位置更新任务完成，输出当前蚂蚁种群位置；

若当前种群的蚂蚁只数没有达到上限值，则返回“采用轮盘赌策略在设定的竞争蚁狮中选择被围绕蚁狮”步骤。

可选的，所述自适应边界收缩因子的表达式为：

其中，I表示自适应边界收缩因子；t表示当前迭代次数；T表示特定迭代次数。

可选的，所述第一更新公式的表达式为：

其中，Ant_i(t)表示第t代第i只蚂蚁的位置；R_Aj(t)表示蚂蚁在第t代围绕被围绕蚁狮随机游走；R_E(t)表示蚂蚁在第t代围绕精英蚁狮随机游走；t表示当前迭代次数，服从均值为0、方差为σ²的正态分布概率密度函数；n表示第n个传感器节点。

可选的，所述蚂蚁种群位置还可以根据第二更新公式更新；

所述第二更新公式根据精英蚁狮位置、所述被围绕蚁狮位置和虚拟力扰动因子计算得到，所述虚拟力扰动因子为所述传感器节点与相邻传感器节点、所述网格点和所述监测区域的边界之间的合力；

所述第二更新公式的表达式为：

其中，Ant_i(t)表示第t代第i只蚂蚁的位置；R_Aj(t)表示蚂蚁在第t代围绕被围绕蚁狮随机游走；R_E(t)表示蚂蚁在第t代围绕精英蚁狮随机游走；t表示当前迭代次数，服从均值为0、方差为σ²的正态分布概率密度函数；g_in(t)表示第t代第i只蚂蚁的第n个传感器节点受到所述虚拟力扰动因子作用后的移动距离。

可选的，所述根据精英蚁狮位置和所述被围绕蚁狮位置控制蚂蚁游走时，蚂蚁的游走范围为两倍的传感器节点感知半径。

一种WSNs覆盖增强系统，包括：

覆盖率计算模块，用于根据监测区域中传感器节点和网格点计算WSNs覆盖率；

适应度函数确定模块，用于将所述WSNs覆盖率最大作为适应度函数；

位置更新模块，用于在所述适应度函数的约束下，采用改进的蚁狮优化算法对蚂蚁种群位置和蚁狮种群位置进行特定次数迭代更新；

输出模块，用于在迭代结束后，将所述改进的蚁狮优化算法中的精英蚁狮对应的传感器节点最佳部署策略输出。

根据本发明提供的具体实施例，本发明公开了以下技术效果：

本发明公开的一种WSNs覆盖增强方法及系统，通过采用改进的蚁狮优化算法计算二维部署环境下传感器节点最优部署方案，使监测区域中的传感器节点分布更加均匀，避免覆盖空洞和节点的大量冗余，降低了传感器节点布置成本和能耗，提高了WSNs网络覆盖率，实现了利用尽量少的传感器节点对指定监测区域的感知覆盖和通信覆盖的最大化部署。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1为本发明实施例1提供的一种WSNs覆盖增强方法流程图；

图2为本发明实施例1提供的一种WSNs覆盖增强方法中最佳部署策略示意图；

图3为本发明实施例1提供的一种WSNs覆盖增强方法中VFPSO和VF-IALO两种算法的初始覆盖效果图；

图4为本发明实施例1提供的一种WSNs覆盖增强方法中VFPSO和VF-IALO两种算法的移动轨迹图和最终覆盖效果图；

图5为本发明实施例1提供的一种WSNs覆盖增强方法中VFPSO和VF-IALO两种算法的覆盖率与迭代次数关系图；

图6为本发明实施例2提供的一种WSNs覆盖增强方法中VFPSO和VF-IALO两种算法中各节点的移动距离对比图；

图7为本发明实施例2提供的一种WSNs覆盖增强方法中VFPSO和VF-IALO两种算法的节点平均移动距离对比图；

图8为本发明实施例2提供的一种WSNs覆盖增强方法中节点平均移动距离与节点数量的关系图；

图9为本发明实施例3提供的一种WSNs覆盖增强系统框图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

本发明的目的是提供一种WSNs覆盖增强方法及系统，以解决二维部署环境下的WSNs覆盖控制问题，提高网络覆盖率。

为使本发明的上述目的、特征和优点能够更加明显易懂，下面结合附图和具体实施方式对本发明作进一步详细的说明。

实施例1：

覆盖控制和节点部署是WSNs的关键问题之一，它决定了传感器节点对周围环境的感知能力，是衡量网络服务质量(Quality ofService,QoS)的重要指标。由于感知节点一般随机部署在监测区域，容易造成节点分布不均匀而导致覆盖空洞等问题，进而影响网络的服务质量。因此如何通过合理部署节点实现网络资源的均衡分配，从而改善网络的感知、采集、处理和通信等服务质量，是目前国内外学者研究的难点之一。WSNs的覆盖控制和节点部署问题本质上是利用尽量少的节点实现对指定监测区域的感知覆盖和通信覆盖的最大化部署。

WSNs的部署主要有两种方法：确定部署和随机部署。确定部署是指根据实际监测区域的需求，在预先知道传感器节点数量和节点位置的前提下进行的确定性部署，此方法适合人工部署、规模小的场景以及在已知环境中部署传感器节点；而随机部署恰好与确定部署相反，它能够让传感器节点工作在孤岛、战场等危险的恶劣环境中，人们通过飞机抛撒等方式来随机部署传感器节点，这种随机部署的方式使监测区域中的传感器节点分布不均匀，导致覆盖空洞和节点的大量冗余，从而不能提供可靠的覆盖需求，并且会造成能耗和成本的过度浪费。为了改善WSNs的覆盖性能，以及传感器节点传输数据的可靠性，通常需要综合考虑节点自身特性以及监测区域的特点，将随机部署的传感器节点进行移动实现二次部署，在此过程中，传感器节点的移动会造成能量的消耗。

现有技术中往往采用优化算法实现对传感器节点的二次移动，传统的蚁狮优化算法在解决传感器节点二次部署中的最优部署问题的过程中，往往存在陷入局部最优解、全局寻优能力弱等缺点，从而导致WSNs的覆盖性能并没有改善。

对此，为解决现有技术中的问题，本发明对传统的蚁狮优化算法进行了改进，如图1所示，提供了一种WSNs覆盖增强方法，包括：

S1：根据监测区域中传感器节点和网格点计算WSNs覆盖率，具体包括：

步骤一：初始化二维监测区域的大小和无线传感器网络模型；

优选地二维监测区域的大小为L×L。

为了提升L×L的监测区域A的覆盖性能并降低二次部署过程的移动距离，对无线传感器网络模型中的参数进行如下假设：

①所有传感器节点均具有相同的性能；

②所有传感器节点均具有充足的能量，使节点可以移动到最优位置；

③所有传感器节点都配有GPS或其他定位系统，可以准确获取每一个节点的位置信息；

④所有传感器节点都可以感知并获取其通信半径内的其他节点的位置。

在监测区域A内随机抛撒N个移动传感器节点，传感器节点的集合为S＝{s₁,s₂,…,s_N}，节点s_i的坐标为(x_i,y_i)，传感器节点的感知半径为R_s，通信半径为R_c，并满足R_c≥2R_s。为了方便计算网络覆盖率，将监测区域A划分为m×n个网格点，记为P_k＝(x_k,y_k),k∈{1,2,…m×n}。

步骤二：根据初始化后的无线传感器网络模型，计算传感器节点和网格点之间的欧式距离，该欧式距离的表达式为：

步骤三：根据所述欧式距离和所述传感器节点的感知半径，计算所述传感器节点对所述网格点的联合感知概率，具体包括：

采用布尔感知模型，判断欧氏距离d(s_i,P_k)与感知半径R_s的大小d(s_i,P_k)≤R_s；

若欧式距离小于等于感知半径(d(s_i,P_k)≤R_s)，则说明网格点P_k(x_k,y_k)被传感器节点s_i覆盖，且传感器节点s_i对网格点P_k的感知概率为1；否则传感器节点s_i对网格点P_k的感知概率为0，即：

利用感知概率计算联合感知概率，因此对于网格点P_k，所有传感器节点对其感知时的联合感知概率为：

步骤四：网格点P_k(x_k,y_k)只要被传感器节点集S中的一个节点覆盖，就说明该网格点被该节点集覆盖；如果S中所有传感器节点都没有检测到该网格点，则称该网格点未被覆盖。因此监测区域的覆盖率为传感器节点集覆盖网格点的总数与监测区域A的总网格点的比值，具体地可根据所述联合感知概率、传感器节点集覆盖网格点的总数和所述网格点总数，计算WSNs覆盖率R_cov：

网络中所有节点覆盖的监测区域面积与节点感知范围面积之和的比值称为覆盖效率。节点的覆盖效率C_e反映了网络中节点的冗余程度，C_e越大表示节点的冗余程度越小，节点分布越均匀。因此，节点的覆盖效率C_e表示为：

S2：将所述WSNs覆盖率最大作为适应度函数；

S3：在所述适应度函数的约束下，采用改进的蚁狮优化算法对蚂蚁种群位置和蚁狮种群位置进行特定次数迭代更新。

传统的蚁狮优化算法的核心思想是模拟蚁狮捕猎蚂蚁的狩猎机制以实现全局寻优。其算法原理如下：

蚂蚁在自然界中随机游走寻找食物的过程可以看作各搜索代理搜寻可行域的过程。随机游走的过程即蚂蚁随机游走的步数，可以表示为：

X(t)＝[0,cussum(2r(1)-1),…,cussum(2r(T)-1)] (6)

式中，cussum为计算累加和，T为最大迭代次数，r(t)为随机数0或1，定义为：

式中，rand为[0,1]的随机数。

为保证蚂蚁在搜索空间内随机游走，需对其位置进行归一化处理，表示为：

式中，a_i和b_i分别为第i个变量的下界和上界，c_i(t)和d_i(t)分别为第t代第i个变量的下界和上界。

轮盘赌选择的蚁狮位置影响着蚂蚁的游走边界，表示为：

c_i(t)＝Antlion_j(t)+c(t),d_i(t)＝Antlion_j(t)+d(t) (9)

式中，c(t)和d(t)分别为所有变量在第t代的下界和上界，Antlion_j(t)为第t代第j只蚁狮的位置。

当蚂蚁随机选择蚁狮陷阱进行游走时，蚁狮会继续深挖陷阱防止蚂蚁逃脱，使得蚂蚁的游走边界逐渐缩小，直至蚂蚁滑落陷阱底部，此过程可表示为：

式中，I为边界收缩因子，表示为：

式中，v为一个随着迭代次数增大而变化的数，表示为：

蚂蚁滑落至陷阱底部后，当蚂蚁种群中有适应度值大于蚁狮的个体时，则该蚂蚁被蚁狮捕获，并将该蚂蚁的位置作为新蚁狮的位置重筑陷阱，该过程表示为：

Antlion_j(t)＝Ant_i(t)if f(Ant_i(t))＞f(Antlion_j(t)) (13)

式中，Antlion_j(t)为第t代时第j只蚁狮的位置，Ant_i(t)为第t代时第i只蚂蚁的位置，f为适应度函数。

每次迭代后，选择适应度最好的蚁狮作为精英蚁狮，和轮盘赌选择的蚁狮一起引导蚂蚁的位置更新，表示为：

式中，R_Aj(t)为蚂蚁在第t代围绕轮盘赌选择的第j只蚁狮随机游走，R_E(t)为蚂蚁在第t代围绕精英蚁狮随机游走。

基于上述传统蚁狮优化算法的思想，本实施例对其进行改进，将改进的蚁狮优化算法应用于传感器节点二次部署问题中，具体包括：

初始化蚂蚁和蚁狮种群的规模和位置，基于上述初始化的二维监测区域和无线传感器网络模型，本实施例中将蚂蚁和蚁狮种群的规模初始化为pop，将初始化的所述传感器节点位置作为初始蚂蚁个体和初始蚁狮个体的位置，具体地将初始化的传感器节点位置作为蚂蚁和蚁狮某一个体的位置，并在该个体的周围产生其余pop-1个蚂蚁和蚁狮的个体位置，优选地在该个体两倍感知半径范围内初始化其他蚂蚁和蚁狮的个体位置；

根据初始化的蚂蚁和蚁狮的种群规模，分别计算蚂蚁种群初始覆盖率和蚁狮种群初始覆盖率；

在蚁狮优化算法中，蚂蚁个体和蚁狮个体即代表一种优化方案。蚁狮代表算法局部最优解，精英蚁狮代表算法的全局最优解。算法通过蚂蚁围绕蚁狮和精英蚁狮的随机游走实现对解空间的搜索。在初始化蚂蚁和蚁狮位置后，可根据公式(4)计算蚂蚁和蚁狮的覆盖率。

在传统蚁狮优化算法中，蚂蚁通过围绕轮盘赌选择的蚁狮和精英蚁狮随机游走实现对求解空间的搜索，但由于算法前期蚁狮种群中可能存在适应度值较差的个体，若蚂蚁轮盘赌选择该蚁狮进行随机游走，会导致算法陷入局部最优解邻域，从而不利于算法寻找全局最优解，也不利于算法收敛速度。基于此，本实施对蚁狮种群的初始优化过程进行了改进：

比较所述蚂蚁种群初始覆盖率和所述蚁狮种群初始覆盖率，将两者中最优的pop个种群重新赋值给初始化的蚁狮种群，得到赋值后的蚁狮种群；

将所述赋值后的蚁狮种群中初始覆盖率最大的蚁狮个体作为初始精英蚁狮；

为了解决蚂蚁在所有蚁狮中选择个体随机游走时导致算法收敛速度较慢的问题，本实施例提出一种蚁狮数量随着迭代次数的增大而减小的策略。为了保证算法前期的全局寻优能力，应选取多个蚁狮参与轮盘赌竞争；在后期，为保证算法的收敛速度，应减少蚁狮的数量，同时，避免了较大的计算量。具体操作如下：

采用轮盘赌策略在设定的竞争蚁狮中选择一只被围绕蚁狮，所述设定的竞争蚁狮计算公式为：

其中，pop(t)表示第t代设定的竞争蚁狮数量；round表示取整函数；T表示特定迭代次数；[pop_min,pop_max]表示参与竞争的蚁狮范围；

轮盘赌策略又称比例选择方法，基本思想是：各个个体被选中的概率与其适应度值的大小成正比。设群体大小为m，个体x_i的适应度为f(x_i)，则个体x_i的选择概率为：

每个个体的累计概率为：

具体操作如下：

1)在[0,1]区间内产生一个均匀分布的伪随机数r；

2)若r≤q₁，则选择个体x₁；

3)若q_k-1＜r≤q_k(2≤k≤m)，则个体x_k被选中；

4)重复2)、3)共m次。

根据所述被围绕蚁狮和所述初始精英蚁狮控制蚂蚁游走，更新蚂蚁种群位置；

根据更新位置后的蚂蚁种群的适应度值更新赋值后的蚁狮种群位置，得到新的蚁狮种群；

将所述新的蚁狮种群适应度值与所述初始精英蚁狮的适应度值比较，选择两者中适应度值最大的对应的蚁狮位置为本次迭代的精英蚁狮位置；

判断迭代次数是否达到特定迭代次数；

若所述迭代次数达到所述特定迭代次数，则输出精英蚁狮位置以及所述精英蚁狮位置对应的传感器节点最佳部署策略；

若所述迭代次数没有达到所述特定迭代次数，则返回“比较所述蚂蚁种群初始覆盖率和所述蚁狮种群初始覆盖率，将两者中最优的种群初始覆盖率对应的种群重新赋值给初始化的蚁狮种群，得到赋值后的蚁狮种群”步骤。

S4：在迭代结束后，将所述改进的蚁狮优化算法中的精英蚁狮对应的传感器节点最佳部署策略输出。

在WSNs中，利用最少的传感器节点部署在监测区域并达到全覆盖，这样的节点部署为最佳部署。

如图2所示，3个相邻传感器节点S₁、S₂和S₃，相邻节点感知区域之间没有空隙，每一对相邻节点感知区域有恒定大小的重叠，3个相邻节点感知区域相交于一个点，连接3个节点位置形成一个等边三角形，节点间距离为

按照此策略部署传感器节点即为最佳部署。

在原始蚁狮优化算法中，蚂蚁随机选择蚁狮进行游走时，它的游走边界即搜索边界逐渐缩小，以便开发搜索到最优值。但在搜索的过程中边界收缩因子I呈跳跃式间断增大趋势，导致蚂蚁对求解区间的探索存在遗漏，且在每一次迭代中，所有蚂蚁的游走边界均相同，限制了算法的多样性，从而不利于算法寻找全局最优解。同时，由于边界收缩因子I间断式快速增大，导致搜索边界跳跃式缓慢衰减，严重影响了算法的收敛速度。因此，为了增强算法的全局寻优能力，并提高算法的收敛速度，本实施例提出一种自适应边界收缩因子I，表达式为：

其中，I表示自适应边界收缩因子；t表示当前迭代次数；T表示特定迭代次数。

在蚂蚁位置更新公式中，蚂蚁通过围绕蚁狮和精英蚁狮随机游走的方式，向当代较优值区域搜索。由于被围绕的蚁狮是由轮盘赌选择而来，而精英蚁狮具有最优的适应度值且它也属于蚁狮种群，因此如果轮盘赌选择的蚁狮是精英蚁狮，蚂蚁将只围绕精英蚁狮游走，从而降低算法的全局寻优能力，此过程可以表示为(也即蚂蚁种群位置更新过程)：

根据公式(19)可以看出，原始的蚂蚁种群更新公式的权重系数固定，在迭代过程中降低算法的全局寻优能力。针对上述问题，本实施例提出了一种改进的蚂蚁种群更新公式，即第一更新公式，动态化权重系数，用来平衡不同迭代时期蚁狮和精英蚁狮的权重。在迭代前期，轮盘赌选择的蚁狮权重较大，增强算法的全局寻优能力；而后期，逐渐增大精英蚁狮的权重，使蚂蚁在全局最优解的邻域内探索开发，提高算法的局部开发能力。

第一更新公式的表达式为：

其中，Ant_i(t)表示第t代第i只蚂蚁的位置；R_Aj(t)表示蚂蚁在第t代围绕被围绕蚁狮随机游走；R_E(t)表示蚂蚁在第t代围绕精英蚁狮随机游走；t表示当前迭代次数，服从均值为0、方差为σ²的正态分布概率密度函数。

为了提高算法的寻优能力，并提高算法的全局收敛速度，本实施例引入虚拟力算法。

现有技术中一名为《Virtual Force-DirectedParticle Swarm Optimizationfor Dynamic DeploymentinWireless SensorNetworks》的期刊论文中提出了虚拟力导向粒子群优化算法来增强二维部署环境的覆盖性能。虚拟力导向粒子群优化网络覆盖算法的基本原理为：在传统粒子群优化算法的基础上，利用传感器节点与相邻传感器节点、障碍物以及优先覆盖区域之间的虚拟力对粒子进行导向。因此，每个粒子的速度不仅根据历史的局部和全局最优解来更新，而且通过传感器节点之间的吸引力和排斥力的合理组合来确定粒子的虚拟运动路径和运动速率，从而达到提高WSNs覆盖性能的目的。

然而该算法主要缺点为：其虚拟力指的是传感器节点与相邻节点、障碍物以及优先覆盖区域之间的相互作用力，而没有考虑网格点对节点的吸引力和监测区域边界对节点的排斥力，导致WSNs存在覆盖空洞和传感器节点超出监测区域边界的问题，从而造成传感器节点成本和资源的浪费，降低了WSNs覆盖率。

基于此，本实施例经过分析传感器节点与相邻节点、网格点(优先覆盖区域)以及边界(障碍物)之间的相互作用力，将传感器节点所受的合力作为蚂蚁更新位置时的扰动因子，引导节点更新位置朝着存在覆盖空洞区域的方向移动，由于在算法前期，需要增加算法的全局寻优能力，而后期，为了防止算法的收敛速度变慢，需要使算法在全局最优解邻域内探索开发，虚拟力算法需要在此时发挥作用较大，因此虚拟力算法的权重选择与精英蚁狮具有相同的权重。

在本发明算法中，随机抛撒至监测区域的任何节点都受到三个虚拟力的影响：

1)监测区域中节点之间相互的作用力

在指定检测区域中，若节点分布不均匀，当两个节点之间距离小于距离阈值时，节点之间产生斥力；反之，产生引力，此作用力可表示为：

式中，d_ij为节点S_i与节点S_j之间的欧式距离，D_th为节点间的距离阈值，w_a和w_r分别为引力和斥力的度量，α_ij为节点S_i与节点S_i连接线段的方向角，R_c为节点的通信半径。

2)监测区域中每个像素点对节点的引力

在指定监测区域中，若没有被覆盖的像素点P_k(x_k,y_k)存在于节点S_i(x_i,y_i)的感知半径以外通信半径以内的区域，则该像素点对该传感器节点产生引力影响，此作用力可表示为：

式中，d_ik为节点S_i与像素点P_k之间的欧式距离，α_ik为节点S_i与像素点P_k连接线段的方向角，R_s为节点的感知半径。

3)监测区域边界对节点的斥力

在指定监测区域中，传感器节点因受到未覆盖像素点和周围节点的影响，会超出监测区域边界，转为无效节点，导致整个网络的性能受到影响。因此，引进监测区域边界对节点的斥力，以保证节点在指定监测区域范围内活动，此作用力可表示为：

式中，d_ib为节点S_i与边界的欧式距离，D_{th_b}为节点与边界的距离阈值。

在以上三种力的作用下，随机抛撒的传感器节点将会移动到最佳位置，达到最优的覆盖。因此，节点S_i所受的合力表示为：

最终，传感器节点会在虚拟力F_i的作用下，由原有位置(x_iold,y_iold)移动到最佳位置(x_inew,y_inew)，最佳位置表达式如下：

式中，F_ix和F_iy分别为合力F_i在x轴和y轴方向上的投影，Max_step为传感器节点单次移动的最大步长。

在此基础上，本实施例根据精英蚁狮位置、所述被围绕蚁狮位置和虚拟力扰动因子计算得到第二更新公式更新，根据第二更新公式更新所述蚂蚁种群位置。

所述第二更新公式的表达式为：

其中，Ant_i(t)表示第t代第i只蚂蚁的位置；R_Aj(t)表示蚂蚁在第t代围绕被围绕蚁狮随机游走；R_E(t)表示蚂蚁在第t代围绕精英蚁狮随机游走；t表示当前迭代次数，服从均值为0、方差为σ²的正态分布概率密度函数；g_in(t)表示第t代第i只蚂蚁的第n个传感器节点受到所述虚拟力扰动因子作用后的移动距离，其表达式如下：

其中，F_in为第i只蚂蚁的第n个传感器节点受到的合力，F_inx和F_iny分别为合力F_in在x轴和y轴方向上的投影。

本发明采用的虚拟力是传感器节点与相邻节点、网格点以及边界之间的相互作用力；其次，本发明对蚁狮优化算法进行改进，改进后的算法具有不易陷入局部最优解、全局寻优能力强以及收敛速度快等优点。因此与“虚拟力导向粒子群优化算法(VFPSO)”相比，本发明(VF-IALO)能够有效提高WSNs的覆盖性能。

当监测区域的大小为60m×60m，部署30个传感器节点时两种算法的初始覆盖效果图如图3所示。

两种算法的节点移动轨迹图和最终的覆盖效果图如图4所示，其中(a1)表示VFPSO的节点移动轨迹图；(a2)表示VFPSO的最终覆盖效果图；(b1)表示VF-IALO的节点移动轨迹图；(b2)表示VF-IALO的最终覆盖效果图。

针对三种不同大小的监测区域，使用最佳部署策略的节点数进行部署，两种算法的覆盖率曲线图如图5所示，其中图(a)表示监测区域为60m×60m，传感器节点数目为30个的覆盖率与迭代次数的关系；图(b)表示监测区域为120m×120m，传感器节点数目为120个的覆盖率与迭代次数的关系；图(c)表示监测区域为210m×210m，传感器节点数目为340个的覆盖率与迭代次数的关系。

考虑到部署传感器节点的实际情况，其数量有可能不是最优数量，因此通过在监测区域中，部署不同数量的传感器节点，以测试本发明算法的通用性，此时两种算法的最终覆盖率如表1所示：

表1不同区域大小不同节点数量的最终覆盖率

由此可以看出本实施例的方案较现有技术可有效提高二维环境中传感器网络覆盖率。

本实施例(1)在原始蚁狮优化算法的基础上，对蚁狮重新赋值并将参与轮盘赌竞争的蚁狮数量动态化，改善了算法易陷入局部最优的问题；

(2)连续化蚂蚁随机游走的边界收缩因子，提高了算法的全局寻优能力和收敛速度；

(3)动态化蚂蚁位置更新权重系数，并对传感器节点与网格点、邻居节点以及边界之间的虚拟力进行分析，利用动态权重来平衡蚁狮、精英蚁狮与节点虚拟力三者之间的关系，并以此来更新蚂蚁的位置，平衡了算法的全局寻优能力和局部开发能力。

实施例2：

实施例1中虚拟力导向粒子群优化算法还存在以下缺点：在WSNs中，传感器节点的移动能耗远远大于感知能耗和通信能耗，其中节点的移动能耗主要由移动距离决定，而该算法在二次部署的过程中没有考虑移动距离的问题。

并且利用蚁狮优化算法增强WSNs覆盖性能时，通过精英蚁狮的位置更新来最优化覆盖率值。而在原始蚁狮优化算法中，蚂蚁通过围绕蚁狮和精英蚁狮进行随机游走的方式寻找食物，蚁狮通过捕获蚂蚁更新位置，因此蚁狮位置更新过程也是随机的。这种随机更新位置的方式会导致传感器节点在二次部署时的移动距离过大，从而造成能量和资源的过度浪费。

在二次部署的过程中，传感器节点的移动能耗远远大于感知能耗和通信能耗，而节点的移动能耗主要由移动距离决定，传感器节点的移动距离越小，所消耗的能量越少，因此将节点的平均移动距离作为网络能量消耗的主要衡量指标。网络中节点的平均移动距离表示为：

式中，N为传感器节点总数量，d_i为传感器节点S_i二次部署过程中的移动距离。

因此，本实施例基于实施例1的技术方案，提出改进的蚂蚁随机游走策略，其主要思想为：蚂蚁在随机游走时，将其限制在蚁狮和精英蚁狮的2R_s范围之内。则第i只蚂蚁分别围绕第j只蚁狮和精英蚁狮的过程可以表示为：

式中，Antlion_j(t)为在第t代轮盘赌选择的第j只蚁狮的位置，Elite Antlion_j(t)为第t代精英蚁狮的位置，R_s为传感器节点的感知半径，rand为[0,1]之间的随机数。

当监测区域的大小为60m×60m，部署30个传感器节点时VFPSO和VF-IALO算法各节点的移动距离对比图如图6所示。

针对三种不同大小的监测区域，使用最佳部署策略的节点数进行部署，两种算法的节点平均移动距离如图7所示。

考虑到部署传感器节点的实际情况，其数量有可能不是最优数量，因此通过在监测区域中，部署不同数量的传感器节点，其节点的平均移动距离如图8所示，其中，图(a)表示60m×60m的监测区域中节点平均移动距离与节点数量的关系；图(b)表示120m×120m的监测区域中节点平均移动距离与节点数量的关系；图(c)表示210m×210m的监测区域中节点平均移动距离与节点数量的关系。

本实施例将蚂蚁游走范围限制在蚁狮和精英蚁狮的2R_s范围之内，有效降低了各传感器节点二次部署时的移动能耗。

实施例3：

参阅图9，本发明还提供了一种WSNs覆盖增强系统，包括：

覆盖率计算模块M1，用于根据监测区域中传感器节点和网格点计算WSNs覆盖率；

适应度函数确定模块M2，用于将所述WSNs覆盖率最大作为适应度函数；

位置更新模块M3，用于在所述适应度函数的约束下，采用改进的蚁狮优化算法对蚂蚁种群位置和蚁狮种群位置进行特定次数迭代更新；

输出模块M4，用于在迭代结束后，将所述改进的蚁狮优化算法中的精英蚁狮对应的传感器节点最佳部署策略输出。

本说明书中每个实施例重点说明的都是与其他实施例的不同之处，各个实施例之间相同相似部分互相参见即可。对于实施例公开的系统而言，由于其与实施例公开的方法相对应，所以描述的比较简单，相关之处参见方法部分说明即可。

本文中应用了具体个例对本发明的原理及实施方式进行了阐述，以上实施例的说明只是用于帮助理解本发明的方法及其核心思想；同时，对于本领域的一般技术人员，依据本发明的思想，在具体实施方式及应用范围上均会有改变之处。综上所述，本说明书内容不应理解为对本发明的限制。

Claims (10)

1.一种WSNs覆盖增强方法，其特征在于，包括：

根据监测区域中传感器节点和网格点计算WSNs覆盖率；

将所述WSNs覆盖率最大作为适应度函数；

在所述适应度函数的约束下，采用改进的蚁狮优化算法对蚂蚁种群位置和蚁狮种群位置进行特定次数迭代更新；

在迭代结束后，将所述改进的蚁狮优化算法中的精英蚁狮对应的传感器节点最佳部署策略输出。

2.根据权利要求1所述的一种WSNs覆盖增强方法，其特征在于，所述根据监测区域中传感器节点和网格点计算WSNs覆盖率，具体包括：

计算所述传感器节点和所述网格点之间的欧式距离；

根据所述欧式距离和所述传感器节点的感知半径，计算所述传感器节点对所述网格点的联合感知概率；

根据所述联合感知概率、传感器节点集覆盖网格点的总数和所述网格点总数，计算所述WSNs覆盖率。

3.根据权利要求1所述的一种WSNs覆盖增强方法，其特征在于，所述采用改进的蚁狮优化算法对蚂蚁种群位置和蚁狮种群位置进行特定次数迭代更新，具体包括：

初始化蚂蚁种群和蚁狮种群的种群规模，将初始化的所述传感器节点位置作为初始蚂蚁种群和初始蚁狮种群任一个体的位置，并在所述任一个体周围产生其余个体的位置；

根据初始化的蚂蚁种群和蚁狮种群的种群规模，分别计算蚂蚁种群初始覆盖率和蚁狮种群初始覆盖率；

比较所述蚂蚁种群初始覆盖率和所述蚁狮种群初始覆盖率，将两者中最优的种群初始覆盖率值重新赋值给初始化的蚁狮种群，并将所述最优的种群初始覆盖率值对应的传感器节点位置信息重新赋值给所述初始化的蚁狮种群，得到赋值后的蚁狮种群；

将所述赋值后的蚁狮种群中初始覆盖率最大的蚁狮个体作为初始精英蚁狮；

采用轮盘赌策略在设定的竞争蚁狮中选择被围绕蚁狮；

根据所述被围绕蚁狮和所述初始精英蚁狮控制蚂蚁游走，更新蚂蚁种群位置；

根据更新位置后的蚂蚁种群的适应度值更新赋值后的蚁狮种群位置，得到新的蚁狮种群；

将所述新的蚁狮种群适应度值与所述初始精英蚁狮的适应度值比较，选择两者中适应度值最大的对应的蚁狮位置为本次迭代的精英蚁狮位置；

判断迭代次数是否达到特定迭代次数；

若所述迭代次数达到所述特定迭代次数，则输出精英蚁狮位置以及所述精英蚁狮位置对应的传感器节点最佳部署策略；

若所述迭代次数没有达到所述特定迭代次数，则返回“比较所述蚂蚁种群初始覆盖率和所述蚁狮种群初始覆盖率，将两者中最优的种群初始覆盖率对应的种群重新赋值给初始化的蚁狮种群，得到赋值后的蚁狮种群”步骤。

4.根据权利要求3所述的一种WSNs覆盖增强方法，其特征在于，所述设定的竞争蚁狮计算公式为：

其中，pop(t)表示第t代设定的竞争蚁狮数量；round表示取整函数；T表示特定迭代次数；[pop_min,pop_max]表示参与竞争的蚁狮范围。

5.根据权利要求3所述的一种WSNs覆盖增强方法，其特征在于，所述根据所述被围绕蚁狮和所述初始精英蚁狮控制蚂蚁游走，更新蚂蚁种群位置，具体包括：

根据所述被围绕蚁狮位置和自适应边界收缩因子，更新蚂蚁游走边界；

在所述蚂蚁游走边界约束下，根据精英蚁狮位置和所述被围绕蚁狮位置控制蚂蚁游走，得到第一更新公式；

根据所述第一更新公式更新蚂蚁种群位置；

判断当前种群的蚂蚁只数是否达到上限值；

若当前种群的蚂蚁只数达到上限值，则蚂蚁种群位置更新任务完成，输出当前蚂蚁种群位置；

若当前种群的蚂蚁只数没有达到上限值，则返回“采用轮盘赌策略在设定的竞争蚁狮中选择被围绕蚁狮”步骤。

6.根据权利要求5所述的一种WSNs覆盖增强方法，其特征在于，所述自适应边界收缩因子的表达式为：

其中，I表示自适应边界收缩因子；t表示当前迭代次数；T表示特定迭代次数。

7.根据权利要求5所述的一种WSNs覆盖增强方法，其特征在于，所述第一更新公式的表达式为：

其中，Ant_i(t)表示第t代第i只蚂蚁的位置；R_Aj(t)表示蚂蚁在第t代围绕被围绕蚁狮随机游走；R_E(t)表示蚂蚁在第t代围绕精英蚁狮随机游走；t表示当前迭代次数，服从均值为0、方差为σ²的正态分布概率密度函数，n表示第n个传感器节点。

8.根据权利要求5所述的一种WSNs覆盖增强方法，其特征在于，所述蚂蚁种群位置还可以根据第二更新公式更新；

所述第二更新公式根据精英蚁狮位置、所述被围绕蚁狮位置和虚拟力扰动因子计算得到，所述虚拟力扰动因子为所述传感器节点与相邻传感器节点、所述网格点和所述监测区域的边界之间的合力；

所述第二更新公式的表达式为：

其中，Ant_i(t)表示第t代第i只蚂蚁的位置；R_Aj(t)表示蚂蚁在第t代围绕被围绕蚁狮随机游走；R_E(t)表示蚂蚁在第t代围绕精英蚁狮随机游走；t表示当前迭代次数，服从均值为0、方差为σ²的正态分布概率密度函数；g_in(t)表示第t代第i只蚂蚁的第n个传感器节点受到所述虚拟力扰动因子作用后的移动距离。

9.根据权利要求5所述的一种WSNs覆盖增强方法，其特征在于，所述根据精英蚁狮位置和所述被围绕蚁狮位置控制蚂蚁游走时，蚂蚁的游走范围为两倍的传感器节点感知半径。

10.一种WSNs覆盖增强系统，其特征在于，包括：

覆盖率计算模块，用于根据监测区域中传感器节点和网格点计算WSNs覆盖率；

适应度函数确定模块，用于将所述WSNs覆盖率最大作为适应度函数；

位置更新模块，用于在所述适应度函数的约束下，采用改进的蚁狮优化算法对蚂蚁种群位置和蚁狮种群位置进行特定次数迭代更新；

输出模块，用于在迭代结束后，将所述改进的蚁狮优化算法中的精英蚁狮对应的传感器节点最佳部署策略输出。

Images