一种基于导向粒子群算法的节点部署方法

摘要

本发明公开了一种基于导向粒子群算法的节点部署方法，所述节点部署方法包括：步骤一：将多个传感器在待监测区域内随机部署；步骤二：在节点虚拟力与网格虚拟力的作用下，带动节点移动，获得对应节点的更新位置和更新速度；步骤三：计算在待监测区域内各节点的网络覆盖率及全局最优覆盖率；步骤四：通过重复交叉操作，生成新的节点群；步骤五：计算所述新的节点群的覆盖率；步骤六：判断所述新的节点群的覆盖率是否大于所述全局最优覆盖率，如果是，则根据所述新的节点群的覆盖率更新全局最优覆盖率；否则，执行步骤二。本发明节点部署方法可快速确定全局最优覆盖率，以实现对传感器的节点部署。

说明书

技术领域

本发明涉及传感器网络监测技术领域，特别是涉及一种基于导向粒子群算法的节点部署方法。

背景技术

无线传感器网络(wireless sensor networks,WSN)由部署在待监测区域内的大量微型、廉价、低功耗的传感器节点集合成，通过Ad-hoc方式形成一个多跳的网络系统，目的是协作的感知、采集和处理网络覆盖地理区域中感知对象的信息，并发布给观察者。为了增强无线传感器网络的监测质量、提高网络可靠性，必须保证传感器节点的部署能够有效地覆盖目标区域。然而，由于传感器节点的能量有限特性及其应用区域的特殊性，无线传感器网络大多通过飞机布撒等方式在待监测区域抛放高密度节点以消除覆盖盲区。然而，传感器节点的高密度部署通常会使得大量节点的待监测区域相互交叠，这种覆盖冗余直接导致共享无线信道的节点之间相互竞争和通信干扰，不仅影响数据传输的可靠性，而且会引发较大的能量开销。如何通过有效的覆盖控制与节点重部署策略改善网络的初始部署成为无线传感网络的研究中的关键问题。

虚拟力算法是由密歇根大学的Koren和Borenstein在20世纪80年代提出的可以让移动机器人在未知的环境中规避障碍物的算法。Zou等人首先将虚拟力算法应用于传感器网络。虚拟力算法是有关多目标的自组织算法。

单独将原始虚拟力算法应用于传感器网络部署问题上，由于传感器节点之间存在力的作用,不可避免的使区域覆盖中受力平衡的一些节点之间存在覆盖盲区,从而不能实现完全覆盖待监测区域，只能达到比较满意的覆盖要求。有些传感器节点按照算法在执行的时候可能在一定范围内来回移动，从而消耗大量不必要的能量。

此外，目前还有将PSO粒子算法应用待传感器网络中。其中，PSO初始化为一群随机粒子(随机解)，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个极值来更新自己：第一个就是粒子本身所找到的最优解，这个解称为个体极值；另一个极值是整个种群目前找到的最优解，这个极值是全局极值。另外也可以不用整个种群而只用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。假设在一个D维的目标搜索空间中，有N个粒子组成一个群落，其中第i个粒子为一个D维的向量X_i＝(x_i1,x_i2,...,x_iD),i＝1,2,...,N，第i个粒子的“飞行”速度也是一个D维的向量，记为V_i＝(v_i1,v_i2,...,v_iD),i＝1,2,...,N，第i个粒子迄今为止搜索到的最优位置称为个体极值，记为P_best＝(p_i1,p_i2,...,p_iD),i＝1,2,...,N，整个粒子群迄今为止搜索到的最优位置为全局极值，记为g_best＝(p_g1,p_g2,...,p_gD)，在找到这两个最优值时，粒子根据如下的公式来更新自己的速度和位置：

v_id＝w×v_id+c₁>1(p_id-x_id)+c₂r₂(p_gd-x_id)

x_id＝x_id+v

式中c₁、c₂为学习因子，r₁、r₂为[0,1]范围内的均匀随机数。线性递减的惯性权重w的更新公式为：

上式中，w_max为初始权重；w_min为最终权重；iter_max为最大迭代次数；t为当前迭代次数。

然而，单独将传统PSO算法应用于传感器网络部署问题上将导致收敛速度过慢并容易在非最优解上耗费过多的迭代次数导致从而导致节点计算量的增加，浪费有限的节点能量。并且前期的全局搜索能力也有限，使得粒子在后期没有良好的局部搜索性能，易陷入次最优解从而导致输出解不是节点最佳部署位置。

发明内容

本发明的目的是提供一种基于导向粒子群算法的节点部署方法，可快速确定全局最优覆盖率，以实现对传感器的节点部署。

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

一种基于导向粒子群算法的节点部署方法，所述节点部署方法包括：

步骤一：将多个传感器在待监测区域内随机部署，初始化n个传感器的节点，获得各个节点的初始位置和初始速度；

步骤二：在节点虚拟力与网格虚拟力的作用下，带动节点移动，获得对应节点的更新位置和更新速度；

步骤三：根据各节点的更新位置和更新速度计算在待监测区域内各节点的网络覆盖率，并从所述各节点的网络覆盖率中选出全局最优覆盖率；

步骤四：按照所述各节点的网络覆盖率的大小顺序，将各节点分为优势节点集合和劣势节点集合，通过重复交叉操作，生成新的节点群；

步骤五：根据所述新的节点群计算所述新的节点群的覆盖率；

步骤六：判断所述新的节点群的覆盖率是否大于所述全局最优覆盖率，如果是，则根据所述新的节点群的覆盖率更新全局最优覆盖率，以对传感器的节点部署；否则，执行步骤二，重复迭代。

可选的，在步骤六中，在返回步骤二之前，所述节点部署方法还包括：判断当前的迭代次数是否达到设置阈值，如果是，则按照当前的全局最优覆盖率对传感器的节点部署；否则返回步骤二。

可选的，所述节点虚拟力的计算方法包括：

根据以下公式计算节点s_i受到节点s_j的虚拟力F_ij1：

其中，d_ij表示节点s_i与节点s_j的距离，d_th表示阈值距离，R表示传感器节点的通信半径，α_ij为节点s_i与节点sj之间的方位角，α_ik为节点s_i与网格点间的方位角，w_a表示虚拟力的引力系数，w_r表示虚拟力的斥力系数；

根据以下公式计算节点s_i所受的全部节点作用的节点虚拟力

可选的，所述网格虚拟力的计算方法包括：

根据以下公式计算单个网格点k与节点s_i间的作用力F_ik2:

其中，d_ik表示节点s_i与未覆盖的网格点k的距离，r表示节点的感知半径；

根据以下公式确定节点s_i所受全部未覆盖的网格点的网格虚拟力

其中，l表示未覆盖的网格点的数量。

可选的，所述获得对应节点的更新位置和更新速度的方法包括：

步骤21：根据节点虚拟力确定节点水平分力F_x1和节点垂直分力F_y1；

步骤22：根据所述网格虚拟力确定网格水平分力F_x2和网格垂直分力F_y2；

步骤23：根据所述节点水平分力F_x1、节点垂直分力F_y1、网格水平分力F_x2和网格垂直分力F_y2确定节点的s_i的更新位置(x_newi,y_newi)和更新速度VF_id：

其中，(x_oldi,y_oldi)为节点s_i的初始位置，max_i_sensor为在节点虚拟力作用下节点的最大步长，max_i_step为在网格虚拟力作用下节点的最大步长。

可选的，所述在待监测区域内各节点的网络覆盖率的计算方法包括：

步骤31：计算节点s_i(x_newi,y_newi)对于二元感知模型平面上的任意目标点P(x,y)的欧式距离d(s_i,P)：

步骤32：根据所述欧式距离d(s_i,P)确定节点s_i对目标点P的感知质量C_xy(s_i)：

其中，r表示节点的感知半径；

步骤33：在二元感知模型下，计算目标点P被平面内所有传感器节点同时覆盖的联合概率C_xy(S)：

步骤34：根据所述联合概率C_xy(S)确定所述待监测区域的网络覆盖率P_area(S)：

其中，m表示被监测覆盖的网格点数，k₁×k₂表示将所述待监测区域分的区域。

可选的，所述成新的节点群及各节点的位置和速度的方法包括：

步骤41：从所述优势节点集合和劣势节点集合中分别随机选出一个节点；

步骤42：将两个节点的速度和位置按照设定权重进行交叉，生成一个新节点的速度和位置；

步骤43：判断劣势节点集合中是否还有节点，如果有则执行步骤41；否则，执行步骤44；

步骤44：将通过迭代生成的全部新节点替代所述劣势节点集合中对应选择的节点，形成新的节点群。

可选的，所述新的节点群的覆盖率的计算方法包括：

步骤51：计算新的节点群中新节点s′_i(x′_i,y′_i)对于二元感知模型平面上的任意目标点P(x,y)的欧式距离d(s′_i,P)：

步骤52：根据所述欧式距离d(s′_i,P)确定节点s′_i对目标点P的感知质量C_xy(s′_i)：

其中，r表示节点的感知半径；

步骤53：在二元感知模型下，计算目标点P被平面内新的节点群同时覆盖的联合概率C_xy(S′)：

步骤54：根据所述联合概率C_xy(S′)确定所述待监测区域的网络覆盖率P_area(S′)：

其中，m表示被监测覆盖的网格点数，k₁×k₂表示将所述待监测区域分的区域。

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

本发明基于导向粒子群算法的节点部署方法通过引入节点虚拟力与网格虚拟力，在节点虚拟力与网格虚拟力的共同作用下，带动节点移动，可加快节点的收敛速度；进一步的，根据各节点的网络覆盖率的大小将节点分组，通过重复交叉操作，生成新的节点群，进而根据所述新的节点群更新全局最优覆盖率，从而可快速准确的确定全局最优覆盖率，以实现对传感器的节点部署。

附图说明

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

图1为本发明基于导向粒子群算法的节点部署方法的流程图；

图2为节点最终覆盖的效果图；

图3为节点覆盖率的迭代曲线。

具体实施方式

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

本发明的目的是提供一种基于导向粒子群算法的节点部署方法，通过引入节点虚拟力与网格虚拟力，在节点虚拟力与网格虚拟力的共同作用下，带动节点移动，可加快节点的收敛速度；进一步的，根据各节点的网络覆盖率的大小将节点分组，通过重复交叉操作，生成新的节点群，进而根据所述新的节点群更新全局最优覆盖率，从而可快速准确的确定全局最优覆盖率，以实现对传感器的节点部署。

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

如图1所示，本发明基于导向粒子群算法的节点部署方法包括：

步骤100：将多个传感器在待监测区域内随机部署，初始化n个传感器的节点，获得各个节点的初始位置和初始速度。

步骤200：在节点虚拟力与网格虚拟力的作用下，带动节点移动，获得对应节点的更新位置和更新速度。

步骤300：根据各节点的更新位置和更新速度计算在待监测区域内各节点的网络覆盖率，并从所述各节点的网络覆盖率中选出全局最优覆盖率。

步骤400：按照所述各节点的网络覆盖率的大小顺序，将各节点分为优势节点集合和劣势节点集合，通过重复交叉操作，生成新的节点群。

步骤500：根据所述新的节点群计算所述新的节点群的覆盖率；

步骤600：判断所述新的节点群的覆盖率是否大于所述全局最优覆盖率，如果是，则根据所述新的节点群的覆盖率更新全局最优覆盖率，以对传感器的节点部署；否则，执行步骤700。

步骤700：判断当前的迭代次数是否达到设置阈值，如果是，则执行步骤800；否则返回步骤200，重复迭代；

步骤800：按照当前的全局最优覆盖率对传感器的节点部署。

其中，在步骤100中，基于PSO粒子算法随机部署传感器节点，其中一个粒子代表一个传感器节点。

在步骤200中，所述节点虚拟力的计算方法包括：

根据以下公式计算节点s_i受到节点s_j的虚拟力F_ij1：

其中，d_ij表示节点s_i与节点sj的距离，d_th表示阈值距离，R表示传感器节点的通信半径，α_ij为节点s_i与节点sj之间的方位角，α_ik为节点s_i与网格点间的方位角，w_a表示虚拟力的引力系数，w_r表示虚拟力的斥力系数。

根据以下公式计算节点s_i所受的全部节点作用的节点虚拟力

原始虚拟力算法只考虑目标节点间的作用力，而在本发明中加入虚拟网格点对节点的引力作用，当节点s_i与未覆盖的网格点k的距离d_ik大于节点的感知半径r且小于节点的通信半径R时，节点就受到虚拟网格点的引力作用。通过引入网格虚拟力，可以使节点快速的从密集的地方扩散开来，从而可大大加快算法的收敛速度。

其中，所述网格虚拟力的计算方法包括：

根据以下公式计算单个网格点k与节点s_i间的作用力F_ik2:

其中，d_ik表示节点s_i与未覆盖的网格点k的距离，r表示节点的感知半径；

根据以下公式确定节点s_i所受全部未覆盖的网格点的网格虚拟力

其中，l表示未覆盖的网格点的数量。

进一步的，在步骤200中，所述获得对应节点的更新位置和更新速度的方法包括：

步骤210：根据节点虚拟力确定节点水平分力F_x1和节点垂直分力F_y1；

步骤220：根据所述网格虚拟力确定网格水平分力F_x2和网格垂直分力F_y2；

步骤230：根据所述节点水平分力F_x1、节点垂直分力F_y1、网格水平分力F_x2和网格垂直分力F_y2确定节点的s_i的更新位置(x_newi,y_newi)和更新速度VF_id：

其中，(x_oldi,y_oldi)为节点s_i的初始位置，max_i_sensor为在节点虚拟力作用下节点的最大步长，max_i_step为在网格虚拟力作用下节点的最大步长。

在步骤300中，所述在待监测区域内各节点的网络覆盖率的计算方法包括：

步骤310：计算节点s_i(x_newi,y_newi)对于二元感知模型平面上的任意目标点P(x,y)的欧式距离d(s_i,P)：

步骤320：根据所述欧式距离d(s_i,P)确定节点s_i对目标点P的感知质量C_xy(s_i)：

其中，r表示节点的感知半径。

步骤330：在二元感知模型下，计算目标点P被平面内所有传感器节点同时覆盖的联合概率C_xy(S)：

步骤340：根据所述联合概率C_xy(S)确定所述待监测区域的网络覆盖率P_area(S)：

其中m表示被监测覆盖的网格点数，k₁×k₂表示将所述待监测区域分的区域。所述网络覆盖率P_area(S)评价WSN节点部署覆盖效果性能优劣的适应度函数。

本发明利用空间分割思想，通过不断分割搜索区域，以达到快速缩小收敛区域的目的。其中，将待监测区域进行网格划分，划分出k₁×k₂块小区域，把待监测区域覆盖离散为k₁×k₂个虚拟网格点的点覆盖问题。满足(8)式的值为1的网格点就认为是被覆盖到。所述网络覆盖率为被覆盖的总点数与总的虚拟网格点数的比值。当相邻网格间的距离为待监测区域大小的4％～0.25％时，覆盖率的计算值与精确值之间的绝对偏差约为0.5％～0.1％。

步骤400中，将整个待监测区域内的将当前最差节点到当前最优节点按网络覆盖率进行1—n(n为节点个数)排序，划分序号为n/2节点所处的位置为界，将节点区域分成两部分，即较劣区域与较优区域。其中较劣区域为劣势节点集合，较优区域为优势节点集合。

其中，所述成新的节点群及各节点的位置和速度的方法包括：

步骤410：从所述优势节点集合和劣势节点集合中分别随机选出一个节点。

步骤420：将两个节点的速度和位置按照设定权重进行交叉，生成一个新节点的速度和位置。

步骤430：判断劣势节点集合中是否还有节点，如果有则执行步骤410；否则，执行步骤440。

步骤440：将通过迭代生成的全部新节点替代所述劣势节点集合中对应选择的节点，形成新的节点群。

通过不断随机交叉，多次分割搜索区域，根据以下公式确定新节点的速度和位置：

其中，其中V_j为优势节点集合重随机选择的节点j的速度，V_k为劣势节点集合随机选择节点k的速度，V_i为新节点i的速度，a为权重，在[0,1]之间。X表示粒子位置，意义与V对应类似。由于采用了用较优和较劣节点交叉信息取代较劣节点措施，导致较劣节点很快获取较优节点的信息，从而使得待监测区域中快速收敛，克服了标准PSO算法中粒子受最大速度的限制而只能一步步向最优解靠近的不足，同时粒子的运动不再仅仅由个体最优和全局最优两个参数决定，随机选择用于交叉的两粒子信息也对粒子的运动产生重要影响。

通过节点之间和网格点间的虚拟力影响粒子群算法的速度更新过程，结合式(11)以及粒子群算法中粒子的速度更新公式，改进后的粒子进化过程如下式所示：

其中，c₁、c₂、c₃为学习因子，r₁、r₂、r₃为[0,1]范围内的均匀随机数，线性递减的惯性权重w。

节点在受到节点虚拟力和网格虚拟力影响后，搜索速度已经大大提升，但依然容易陷入局部最优，导致覆盖率不能进一步提高。结合本发明提出的空间分割改进PSO算法的思想，在节点速度每次迭代过程中，将最劣节点到最优节点的所有节点按照适应度值进行排序，将中间节点作为较优搜索空间和较劣搜索空间的分界，随机选择位于较劣和较优搜索空间的两个粒子按照(11)式进行交叉操作，生成新的较优节点，取代淘汰交叉过程中的较劣区域的一个节点。反复执行上述过程，生成新的较优节点群。上述操作避免了标准粒子群算法中粒子更新过程中仅仅由个体最优和全局最优的位置决定，增加了种群的多样性和跳出局部最优的能力。

在步骤500中，所述新的节点群的覆盖率的计算方法包括：

步骤510：计算新的节点群中节点s′_i(x′_i,y′_i)对于二元感知模型平面上的任意目标点P(x,y)的欧式距离d(s′_i,P)：

步骤520：根据所述欧式距离d(s′_i,P)确定节点s′_i对目标点P的感知质量C_xy(s′_i)：

其中，r表示节点的感知半径。

步骤530：在二元感知模型下，计算目标点P被平面内新的节点群同时覆盖的联合概率C_xy(S′)：

步骤54：根据所述联合概率C_xy(S′)确定所述待监测区域的网络覆盖率P_area(S′)：

其中，m表示被监测覆盖的网格点数，k₁×k₂表示将所述待监测区域分的区域。

本发明基于导向粒子群算法的节点部署方法通过加入节点部署区域划分出的虚拟网格点对节点的引力作用，可以大大加快算法的收敛速度；利用空间分割思想改进PSO算法，将改进后的虚拟力算法融合改进后的PSO算法，可提高节点覆盖率(如图2和图3所示)、收敛速度、降低复杂度以及提高执行效率。

通过表1和表2所示，可知：通过与传统虚拟力算法(VFA)、传统PSO算法、虚拟力导向PSO算法(VFPSO)在节点覆盖率和算法达到最大覆盖率时消耗的时间进行对比，可直接得到本发明有更高的节点覆盖率、收敛速度更快、较低的复杂度和较高的执行效率。

表1 节点覆盖率

表2：算法达到最大覆盖率时消耗的时间

本说明书中各个实施例采用递进的方式描述，每个实施例重点说明的都是与其他实施例的不同之处，各个实施例之间相同相似部分互相参见即可。

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