一种无线传感器网络网关优化部署方法

摘要

一种无线传感器网络网关优化部署方法，涉及一种网关优化部署方法。为了解决几何K中心下的无线传感器网络网关部署问题，以缩小覆盖半径，提高网络服务质量。主要步骤：网关位置向量初始化、网关位置向量变异操作、交叉操作、选择操作、重复上述步骤直到迭代次数到达P＝500，在第500代种群中分别计算各个目标向量对应的适应值，适应值最小的一个目标向量即为无线传感器网络中网关的最优部署位置坐标。实验结果表明，通过微分进化算法求解无线传感器网络中网关的部署位置，能够比现有基于粒子群的算法收敛速度提高50％左右，覆盖半径缩小20％，因此该方法能够显著提高网络服务质量。

主权项

一种无线传感器网络网关优化部署方法，在传感器节点数量为n的无线传感器网络G中设置K个网关节点，G的邻接矩阵为A＝(e_ij)_n×n，最短距离矩阵为D＝(d_ij)_n×n,d_ij表示从节点v_i路由到v_j所需要的最小跳数，最短距离矩阵由Floyd算法求得；节点v_i选择网关u_k作为其服务网关，则满足式(1)的要求：d(v_i,u_k)≤d(v_i,u_l),k,l≤K,j≠l          (1)式中：v_i包含在网关u_k的服务集U_k中，即v_i∈U_k，u_k与服务集U_k中节点之间的最大距离为称为网关u_k的覆盖半径；所有网关节点中的最大覆盖半径称为网关集{u_k}_K的覆盖半径；所述无线传感器网络网关优化部署方法使得网关集的覆盖半径最小，如式(2)所示：$\begin{array}{c}\begin{array}{cc}\min & \underset{1\le k\le K}{\max }\underset{v_i\in U_k}{\max }\left(d(v_i,u_k)\right)\end{array}\\ \begin{array}{cc}s.t.& {\left\{u_k\right\}}_K⋐R^2\end{array}\end{array}---\left(2\right)$使用微分进化算法进行上述式(2)的寻优求解，定义对于K个网关节点，其在二维平面的坐标为：(a_k,b_k)，k＝1,2,...,K，用网关坐标组成的目标向量为：X＝(x₁,x₂,...,x_m)，其中m＝2K，x_2k‑1＝a_k，x_2k＝b_k，第t组目标向量为X_t＝(x_t,1,x_t,2,...,x_t,m)；寻优求解的过程如下：步骤一、网关位置向量初始化在网络有效区域内，随机产生T组目标向量X₁,X₂,...,X_T组成第一代种群，种群中的每个目标向量表示一组可能的网关位置坐标；设置交叉因子F＝0.8，交叉概率为CR＝0.4，最大迭代次数P＝500，按照网络区域大小设置目标向量中各维数据的上下限范围[down_limit,up_limit]；步骤二、网关位置向量变异操作对于由网关位置坐标组成的第p代种群任意一个目标向量其中：p＝1,2,...,P，t＝1,2,...,T；根据微分进化算法按式(3)产生下一代网关位置坐标组成的变异向量${V_t}^{p+1}=(v_{t,1}^{p+1},v_{t,2}^{p+1},...,v_{t,m}^{p+1});$$v_{t,j}^{p+1}=x_{r_1,j}^p+F(x_{r_2,j}^p-x_{r_3,j}^p),j=\mathrm{1,2},...,m---\left(3\right)$其中，和为第p代种群中随机选择的3个个体目标向量第j位的元素，并且为3个不同的个体；交叉因子F是一个实数，用于控制差值的放大倍数，F＝0.8；按照式(3)进行元素变异操作之后，再按照式(4)以初始化过程设定的目标向量中各维数据上下限依据，将进行元素变异操作之后超过有效界限的元素拉回到边界处：$v_{t,j}^{p+1}=\left\{\begin{array}{ccc}\mathrm{down}\_\mathrm{limit}& \mathrm{if}& v_{t,j}^{p+1}<\mathrm{down}\_\mathrm{limit}\\ v_{t,j}^{p+1}& \mathrm{if}& \mathrm{down}\_\mathrm{limit}\le v_{t,j}^{p+1}\le \mathrm{up}\_\mathrm{limit}\\ \mathrm{up}\_\mathrm{limit}& \mathrm{if}& v_{t,j}^{p+1}>\mathrm{up}\_\mathrm{limit}\end{array}\right.---\left(4\right)$步骤三、交叉操作在完成网关位置向量的变异操作后，产生下一代由网关位置坐标组成的交叉向量其中向量的每位元素按照式(5)进行计算${\psi }_{t,j}^{p+1}=\left\{\begin{array}{cc}{v}_{t,j}^{p+1}& \mathrm{rand}\le \mathrm{CR}\left|\right|j=j_{\mathrm{rand}}\\ x_{t,j}^{p+1}& \mathrm{rand}>\mathrm{CR}\left|\right|j\ne j_{\mathrm{rand}}\end{array}\right.,j=\mathrm{1,2},...,m---\left(5\right)$其中，rand为0～1之间的随机数，j_rand为1～m中的随机整数；CR是交叉概率，CR＝0.4；步骤四、选择操作d(v_i,u_k)为传感器节点v_i到网关节点u_k的跳数；对于第k个网关u_k，其节点位置为(a_k,b_k)，k＝1,2,...,K；距离该网关节点距离小于通信半径的传感器节点组成的集合为Θ_k，该网关节点到Θ_k中任意节点的跳数均为1；节点v_i到Θ_k的距离为则节点v_i到网关节点u_k的跳数可按式(6)计算：$d(v_i,u_k)=\left\{\begin{array}{cc}1& v_i\in {\Theta }_k\\ \underset{v_l\in {\Theta }_k}{\min }\left(d(v_i,v_l)\right)+1& v_i\notin {\Theta }_k\end{array}\right.---\left(6\right)$无线传感器网络网关优化部署的适应值计算函数为：$f\left({\left\{u_k\right\}}_K\right)=\underset{1\le i\le n}{\max }\underset{1\le k\le K}{\min }d(v_i,{\Theta }_k)+1---\left(7\right)$在交叉操作完成后，按照式(8)进行选择操作：$X_y^{p+1}=\left\{\begin{array}{cc}{\Psi }_t^{p+1}& f\left({\Psi }_t^{p+1}\right)<f\left(X_t^p\right)\\ X_t^p& f\left({\Psi }_t^{p+1}\right)\ge f\left(X_t^p\right)\end{array}\right.---\left(8\right)$上述选择过程是指如果新产生的个体向量由于父代中相应位置的个体向量，则将其取代父代中的个体向量，进入到新一代的种群中，使得无线传感器网络的网关位置坐标种群能够得到持续的优化；步骤五、重复步骤二到步骤四直到迭代次数到达P＝500，在第500代种群中分别按照式(7)计算各个目标向量对应的适应值，适应值最小的一个目标向量即为无线传感器网络中网关的最优部署位置坐标。