一种基于耦合模拟退火算法的无线网络覆盖优化方法

摘要

本发明公开了一种基于耦合模拟退火算法的无线网络覆盖优化方法，将区域覆盖率的问题转换为点覆盖问题，对传感区域的节点覆盖分布构建不同初始点但相互耦合的搜索粒子，以搜索粒子的区域覆盖率为优化目标函数，每个粒子并行地进行模拟退火过程，这些模拟退火过程通过一个接收概率函数相互耦合，退火过程中借助Metropolis准则选择性地接受每个粒子的新状态，并充分利用己试探过的区域引导搜索群体跳出局部最优；接收概率函数充分利用了搜索过程粒子间的演化信息，从而大大提高了优化搜索效率和性能，避免算法早熟收敛，增强了算法的全局搜索能力，并弥补了基本模拟退火算法对初始参数选取鲁棒性差的缺点，从而能实现协同化和智能化地探索空间区域。

主权项

1.一种基于耦合模拟退火算法的无线网络覆盖优化方法，其特征是，所述无线网络覆盖优化方法包括如下步骤：（1）、随机生成由m个粒子组成的初始搜索群体{S₁₀,…,S_m0}，每一个粒子代表一种N个传感节点位置分布方案；N个传感器节点分布于二维平面监测区域Q内，将二维平面监测区域Q数字离散化为a×b个格点；设第i个粒子对应无线传感器网络节点的初始分布为S_i0，确定初始温度和内循环的迭代次数K，初始迭代计数k＝0，降温的外循环开始，外循环初始迭代计数t＝0；（2）、利用公式R_i(S_ik)＝Σ_j ρ_j(S_ik)/(a×b)(j＝1,…,ab,i＝1,…,m)计算各个粒子的网络覆盖率，其中：${\rho }_j\left(S_{\mathrm{ik}}\right)=1-\underset{s_i\in S_{\mathrm{ik}}}{\Pi }(1-{\rho }_j(x,y,s_i)),$${\rho }_j(x,y,s_i)=\left\{\begin{array}{cc}1& d(s_i,A)\le r\\ 0& \mathrm{other}\end{array}\right.,$$d(s_i,A)=\sqrt{{(x_i-x)}^2+{(y_i-y)}^2};$其中，(x_i,y_i,r)表示以节点s_i的坐标(x_i,y_i)为圆心，感知半径为r的圆；为格点A(x,y)与节点s_i之间的距离；x,y分别表示格点A在监测区域的横、纵坐标；（3）、内循环开始，利用随机扰动机制，更新当前粒子产生新网络分布并计算新网络覆盖率（4）、计算和R_i(S_ik)的差，记利用Metropolis接收准则，若Δ≤0，则令否则，以概率$P_A(S_{\mathrm{ik}}\to {\hat{S}}_{\mathrm{ik}})=\alpha P_B(S_{\mathrm{ik}}\to {\hat{S}}_{\mathrm{ik}})+(1-\alpha )P_C(S_{\mathrm{ik}}\to {\hat{S}}_{\mathrm{ik}})$接收新状态（5）、更新迭代计数令k＝k+1；且当迭代计数等于K时，内循环结束，转下一步；否则，转步骤（3）；（6）、令迭代计数k＝0；如果未达到冷却状态，则根据降火策略，降低当前温度，并令t＝t+1，重复执行步骤（2）～步骤（6）；否则，转下一步；（7）、降火过程结束，返回近似最优解S_k以及网络覆盖率R_i(S_k)，结束搜索优化。