基于粒子群的无线传感器网络移动节点覆盖优化方法

摘要

本发明针对基本粒子群算法在求解无线传感网络覆盖优化问题的不足，结合最大覆盖算法，提出了一种基于粒子群的无线传感器网络移动节点覆盖优化方法。该算法以移动节点位置向量为输入参数，网络覆盖率为目标函数，同时利用最大覆盖算法中所提到的远离和靠近模块，对节点间的位置进行调整，如果节点间分布过密，则让节点远离；如果节点分布松散，则让节点靠近。结合位置调节和粒子群算法，在粒子群算法速度更新公式中考虑了节点与其最近节点的位置调整，指导粒子进化，这样做有助于扩大节点的覆盖范围，增强粒子群算法搜索全局最优解的能力，即提高了网络覆盖率。最后应用基于位置调节的粒子群算法求解无线传感网络覆盖优化问题。

主权项

1.一种基于粒子群的无线传感器网络移动节点覆盖优化方法，其特征在于包括如下步骤：步骤1：搜索空间为j维，种群规模为M，初始化粒子位置，随机产生每个粒子的位置和速度，同时设定节点的距离阈值，当节点与最近邻居节点之间的距离小于所设距离阈值，则远离；当这个距离大于距离阈值时，则靠近；远离模块：节点A在n时刻的坐标为(x_n，y_n)，而离节点A最近的邻节点b在n时刻的坐标为(x_bn，y_bn)，节点A在n+1时刻的目标位置为(x_n+1，y_n+1)，设节点间距离阈值为L_th，单位时间的步长为d，传感半径R_s，通信半径R_c，其中L_th≤R_c-d，可知$\frac{x_{n+1}-x_n}{x_n-x_{\mathrm{bn}}}=\frac{y_{n+1}-y_n}{y_n-y_{\mathrm{bn}}}=\frac{d}{L_n}---\left(1\right)$其中，$L_n=\sqrt{{(x_n-x_{\mathrm{bn}})}^2+{(y_n-y_{\mathrm{bn}})}^2}$根据式(1)计算出节点A远离节点b的情况下，节点A的目标位置：$\left[\begin{array}{c}{x}_{n+1}\\ y_{n+1}\end{array}\right]=\left[\begin{array}{c}d·\frac{(x_n-x_{\mathrm{bn}})}{\sqrt{{(x_n-x_{\mathrm{bn}})}^2+{(y_n-y_{\mathrm{bn}})}^2}}+x_n\\ d·\frac{(y_n-y_{\mathrm{bn}})}{\sqrt{{(x_n-x_{\mathrm{bn}})}^2+{(y_n-y_{\mathrm{bn}})}^2}}+y_n\end{array}\right]---\left(2\right)$靠近模块：节点A和节点b之间大于距离阈值，在下一个时刻，节点A应向节点B的方向移动，同远离模块一样，建立类似的数学模型，节点A的目标位置：$\left[\begin{array}{c}{x}_{n+1}\\ y_{n+1}\end{array}\right]=\left[\begin{array}{c}-d·\frac{(x_n-x_{\mathrm{bn}})}{\sqrt{{(x_n-x_{\mathrm{bn}})}^2+{(y_n-y_{\mathrm{bn}})}^2}}+x_n\\ -d·\frac{(y_n-y_{\mathrm{bn}})}{\sqrt{{(x_n-x_{\mathrm{bn}})}^2+{(y_n-y_{\mathrm{bn}})}^2}}+y_n\end{array}\right]---\left(3\right)$步骤2：计算整个区域的初始有效覆盖率，并初始化每个粒子的局部最优位置pbest，以及对应覆盖率最大时粒子的全局最优位置gbest；步骤3：计算粒子i中各节点之间的距离，和设定的距离阈值比较，并根据公式(2)和(3)对节点间的位置进行调整，计算粒子i中节点与其最近节点的距离改变值步骤4：根据公式(4)和(5)更新粒子位置和速度，并重新根据式(6)～(9)计算每个粒子更新位置后的网络覆盖率；速度和位置更新公式如式(4)：$v_{\mathrm{ij}}^{k+1}=w\left(k\right)\times v_{\mathrm{ij}}\left(k\right)+c_1{r}_{1j}({\mathrm{pbest}}_{\mathrm{ij}}^k-x_{\mathrm{ij}}^k)+c_2{r}_{2j}({\mathrm{gbest}}_{\mathrm{gj}}^k-x_{\mathrm{ij}}^k)+c_3{r}_3{\Delta }_{\mathrm{ij}}^k---\left(4\right)$$x_{\mathrm{ij}}^{k+1}=x_{\mathrm{ij}}^k+v_{\mathrm{ij}}^{k+1}---\left(5\right)$其中，c₁为微粒自身加速度权重系数，c₂为全局加速度权重系数，c₃为位置调节的加速权重系数，r_1j和r_2j为0～1内的随机数，和分别为粒子i在第k次迭代中第j维的位置和速度，二者均被限制在一定范围内；是粒子i在第j维的个体极值的位置；是群体在第j维的个体极值的位置；w为惯性权重系数；是粒子i中节点与其最近节点的距离改变值；设无线传感器网络中的节点s_i的坐标为(x_i，y_i)，一个二维平面监测区域中任意点p的坐标为(x_p，y_p)，则节点s_i对目标点p的检测概率为：其中，d(s_i，p)为传感器节点s_i与目标点p的欧式距离；R_e(0<R_e<R_s)是传感节点测量可靠性参数；α₁=R_e-R_s+d(s_i，p)，α₂=R_e+R_s-d(s_i，p)；λ₁、λ₂、β₁、β₂是与传感节点特性有关的测量参数；因此，整个二维平面监测区域内的n个传感器节点对目标点p的联合检测概率为：$C_p(s_{\mathrm{all}},p)=1-\underset{i=n}{\Pi }(1-C_p(s_i,p))---\left(7\right)$其中，s_all为测量目标点的传感器节点集合；为了满足覆盖要求，通常要求联合检测概率不低于根据网络需求所设定的阈值c_th，则目标点能被有效检测到的条件为：$\underset{x_p,y_p}{\min }\left\{C_p(s_{\mathrm{all}},p)\right\}\ge C_{\mathrm{th}}---\left(8\right)$将待测区域划分成m×n个网格，再将单元格简化为像素点，网络覆盖率定义为满足式(7)要求的单元格数量占总的单元格数量的比例，即：$C_r=\frac{\underset{x_p=1}{\overset{m}{\Sigma }}\underset{y_p=1}{\overset{n}{\Sigma }}{C}_p(s_{\mathrm{all}},p)}{m\times n}---\left(9\right)$步骤5：将每个粒子更新位置后的覆盖率与每个粒子的局部最优位置pbest对应的覆盖率比较，如果较大，则更新pbest；步骤6：将群体中的每个粒子的个体最优pbest对应的覆盖率与gbest对应的覆盖率比较，如果较大，则更新gbest；步骤7：如果达到预设的最大迭代数，则结束，并返回群体最优分布，否则返回步骤2。