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

一种无线传感器网络网关优化部署方法
【技术领域】
[0001] 本发明涉及一种无线传感器网络中的网关优化部署方法。
【背景技术】
[0002] 为实现解决混合无线传感器网络互联及接入互联网的问题，通常采用网关设备将 不同类型的节点进行互联，网关设备由高带宽的网络连接，为节点担当转发数据的功能。由 于网络中大部分流量汇聚于网关，网关经常成为网络性能的瓶颈；离网关较近的节点得到 的服务质量较好，较远的节点得到的服务质量较差，各节点间存在服务质量的不公平性，因 此网关部署是否合理对网络性能有较大影响。
[0003] 目前，无线传感器网络的网关部署的方式主要分为两种：一种方式是从现有的网 络节点中选取K个节点作为网关节点，即网络的K个中心节点，称为节点K中心问题；另一 种方式是可在网络节点所在平面的任意位置部署K个节点作为网关节点，该K个节点不一 定从现有网络节点中选取，此类问题被归结为几何K中心问题。
[0004] 目前节点K中心问题的研宄成果较为丰富，几何K中心问题的网关部署方式要求 在给定平面内根据一定要求来部署一些新的节点作为网关节点，满足覆盖条件的同时尽量 提高服务质量，这种方式比前一种方式要复杂很多，因为节点K中心问题可以概括为离散 选址问题，而几何K中心问题是一个连续区域选址问题，对于该问题的处理比较复杂，而且 相关的研宄工作也比较少。现有的基于粒子群优化算法的网关节点部署方法容易陷入局部 最优陷阱，导致网关覆盖半径过大，网络服务质量下降。
[0005] 微分进化算法因其具有收敛速度快、可调参数少、鲁棒性好、算法简单，近些年逐 渐被人们所接受，成为目标优化领域研宄的热点之一。

【发明内容】

[0006] 本发明提出一种基于微分进化（DifferentEvolution,DE)算法的无线传感器网 络网关优化部署方法，利用微分进化算法较好的全局寻优能力寻找网关优化部署方案，解 决几何K中心下的无线传感器网络网关部署问题，以缩小覆盖半径，提高网络服务质量。
[0007] 本发明为解决上述技术问题采取的技术方案如下：
[0008] 通常情况下，在无线传感器网络中，传感器节点会选择距离其最近的网关作为其 服务网关，如图1所示。
[0009] 在传感器节点数量为n的无线传感器网络G中设置K个网关节点，G的邻接矩阵 为A= (eij)nXn，最短距离矩阵为D=(Hwdij表示从节点Vi路由到V」所需要的最小跳 数，最短距离矩阵可由Floyd算法求得。节点\选择网关uk作为其服务网关，则必须满足 式⑴的要求：
[0010] d(Vi,uk) ^d(Vi,ux),k, 1 ^K,j^ 1 (1)
[0011] 此时，称Vi包含在网关uk的服务集Uk中，即ViGUk，uk与服务集Uk中节点之间 的最大距离为，称为网关uk的覆盖半径。所有网关节点中的最大覆盖半径
称为网关集|uk}K的覆盖半径。
[0012] 网关集的覆盖半径是网关部署的重要评价指标，覆盖半径越小通信质量越高，网 络服务质量也会相应提高。因此，无线传感器网络网关部署的重要优化目标之一就是使得 网关集的覆盖半径最小，如式（2)所示：
[0013]
(2)
[0014] 为解决无线传感器网络网关优化部署问题，本发明提出使用微分进化算法进行上 述式（2)的寻优求解。对于K个网关节点，其在二维平面的坐标为：(ak，bk)，k= 1，2,. . .，K， 用网关坐标组成的目标向量为：X=(Xpx2, . . .，xm)，其中m= 2K，ak，x2k=bk，第t 组目标向量为Xt=(xt;1,xt，2, ? ? ?，xt，J。
[0015] 其具体过程如下：
[0016] (1)网关位置向量初始化
[0017] 在网络有效区域内，随机产生T组目标向量X2, . . .，&组成第一代种群，种群 中的每个目标向量表示一组可能的网关位置坐标。设置交叉因子F= 0. 8,交叉概率为CR =〇. 4,最大迭代次数P= 500,按照网络区域大小设置目标向量中各维数据的上下限范围 [down_limit,up_limit]〇
[0018] (2)网关位置向量变异操作
[0019] 对于由网关位置坐标组成的第p代种群任意一个目标向量 其中：p= 1，2, . . .，P，t= 1，2, . . .，T。根据微分进化算法按式（3)产生下一代网关位置坐 标组成的变异向量1 ?,vf，
[0020]
(3)
[0021] 其中，、（和为第p代种群中随机选择的3个个体目标向量第j位的元 素，并且为3个不同的个体。交叉因子F是一个实数，用于控制差值的放大倍数，F取值较 大时，DE算法的收敛速度会加快，但是可能会陷入到局部最优。在本发明中交叉因子取值 为F= 0? 8〇
[0022] 在按照式（3)进行元素变异操作之后，存在变异向量中某些元素位超过其有效界 限的情况，因此需要按照式（4)以初始化过程设定的目标向量中各维数据上下限（即无线 传感器网络的边界）为依据，将超过有效界限的元素拉回到边界处：
[0023
(4)
[0024] (3)交叉操作
[0025] 在完成网关位置向量的变异操作后，产生下一代由网关位置坐标组成的交叉向量
其中向量的每位元素按照式（5)进行计算
[0026]
[0027] 其中，rand为0~1之间的随机数，jrand为1~m中的随机整数。CR是交叉概率， 如果CR的值较大，DE算法的收敛速度会加快。如果CR的值较小，DE的鲁棒性会更好，同时 增加问题的执行时间，在本发明中交叉概率为CR= 0. 4。
[0028] (4)选择操作
[0029] (Kvi,uk)为传感器节点Vi到网关节点uk的跳数。对于第k个网关uk，其节点 位置为（ak，bk)，k= 1，2，...，K。距离该网关节点距离小于通信半径的传感器节点组 成的集合为?k，该网关节点到?k中任意节点的跳数均为1。节点vjlj0 k的距离为
则节点Vi到网关节点uk的跳数可按式（6)计算：
[0030]
(6)
[0031] 无线传感器网络网关优化部署的适应值计算函数为：
[0032]
(7)
[0033] 在交叉操作完成后，按照式（8)进行选择操作：
[0034]
⑶
[0035] 上述选择过程是指如果新产生的个体向量由于父代中相应位置的个体向量，则将 其取代父代中的个体向量，进入到新一代的种群中，使得无线传感器网络的网关位置坐标 种群能够得到持续的优化。
[0036] (5)重复步骤⑵到步骤⑷直到迭代次数到达P= 500,在第500代种群中分别 按照式⑵计算各个目标向量Zf'Zf，...，右?对应的适应值，适应值最小的一个目标向 量即为无线传感器网络中网关的最优部署位置坐标。
[0037] 本发明的有益效果是：
[0038] 本发明采用基于微分进化（DifferentEvolution,DE)算法实现无线传感器网络 网关优化部署，利用微分进化算法较好的全局寻优能力寻找网关优化部署方案，解决了几 何K中心下的无线传感器网络网关部署问题，缩小覆盖半径，提高了网络服务质量。
[0039] 通过以下方法进行实验验证本发明所提出方法的有效性（参见图2和图3)，在实 验中，无线传感器节点随机分布在长度为500*500的部署区域中。网络节点数量为200,网 络图为连通图，网络中节点最大节点度数为6,最小为1.网关的部署个数分为5,实验进行 100次。覆盖半径的值是P= 500时的种群最小适应值，算法收敛速度根据当代种群最小适 应值和第500代种群最小适应值进行比对得到的，即最早收敛到P= 500代种群最小适应 值的年代值代表收敛速度。
[0040] 实验结果表明，通过微分进化算法求解无线传感器网络中网关的部署位置，能够 比现有基于粒子群的算法收敛速度提高50%左右，覆盖半径缩小20%，因此该方法能够显 著提高网络服务质量。
【附图说明】
[0041] 图1是无线传感器网络结构图；
[0042] 图2是无线传感器网络结构图，其中圆圈表示无线传感器网络中的传感器节点， 连线表示传感器节点之间存在通信连接；
[0043] 图3为使用微分进化算法进行网关部署优化后得到的网络部署结构图，其中实心 点表示无线传感器网络中的传感器节点，方框表示部署的网关节点，虚线表示传感器节点 之间的通信关系，实线表示网关节点与传感器节点之间的通信关系。
【具体实施方式】
[0044] 本实施方式给出无线传感器网络网关优化部署方法，在传感器节点数量为n的无 线传感器网络G中设置K个网关节点，G的邻接矩阵为A= ( eij)nXn，最短距离矩阵为D= (djnXn，&表示从节点vi路由到v』所需要的最小跳数，最短距离矩阵由Floyd算法求得； 节点\选择网关uk作为其服务网关，则满足式（1)的要求：
[0045] d (v^ uk) ^ d (v^ ux), k, 1 ^ K, j ^ 1 (1)
[0046] 式中：Vi包含在网关uk的服务集Uk中，即ViGUk，uk与服务集Uk中节点之间的 最大距离为，称为网关uk的覆盖半径；所有网关节点中的最大覆盖半径
除为网关集{uk}K的覆盖半径；
[0047] 所述无线传感器网络网关优化部署方法使得网关集的覆盖半径最小，如式（2)所 示：
[0048]
(2)
[0049] 使用微分进化算法进行上述式⑵的寻优求解，定义对于K个网关节 点，其在二维平面的坐标为：（ak，bk)，k= 1，2，...，K，用网关坐标组成的目标向量 为：X= (X"x2,…，xm)，其中m= 2K，x2h=ak，x2k=bk，第t组目标向量为Xt = (Xt，1，Xt，2，? ? ?，Xt，m)；
[0050] 寻优求解的过程如下：
[0051] 步骤一、网关位置向量初始化
[0052] 在网络有效区域内，随机产生T组目标向量H...，&组成第一代种群，种群 中的每个目标向量表示一组可能的网关位置坐标；设置交叉因子F= 0. 8,交叉概率为CR =〇. 4,最大迭代次数P= 500,按照网络区域大小设置目标向量中各维数据的上下限范围 [down_limit,up_limit]；
[0053] 步骤二、网关位置向量变异操作
[0054] 对于由网关位置坐标组成的第p代种群任意一个目标向量
其中：p= 1，2,. . .，P，t= 1，2,. . .，T;根据微分进化算法按式（3)产生下一代网关位置坐 标组成的变异向量：^+1 ?, C1 ;
[0055]
(3)
[0056] 其中，和为第p代种群中随机选择的3个个体目标向量第j位的元 素，并且为3个不同的个体；交叉因子F是一个实数，用于控制差值的放大倍数，F= 0. 8 ;
[0057] 按照式（3)进行元素变异操作之后，再按照式（4)以初始化过程设定的目标向量 中各维数据上下限依据，将进行元素变异操作之后超过有效界限的元素拉回到边界处：
[0058]
(4)
[0059] 步骤三、交叉操作
[0060] 在完成网关位置向量的变异操作后，产生下一代由网关位置坐标组成的交叉向量 ,
^ ,其中向量的每位元素按照式（5)进行计算
[0061]
(5)
[0062] 其中，rand为0~1之间的随机数，jMnd为1~m中的随机整数；CR是交叉概率， CR= 0. 4 ；
[0063] 步骤四、选择操作
[0064] (Kvi，％)为传感器节点Vi到网关节点uk的跳数；对于第k个网关uk，其节点 位置为（ak，bk)，k= 1，2，...，1(;距离该网关节点距离小于通信半径的传感器节点组 成的集合为?k，该网关节点到?k中任意节点的跳数均为1 ;节点vjlj0 k的距离为
.....v；efc>t......则节点Vi到网关节点uk的跳数可按式（6)计算：
[0065]
(&)
[0066] 无线传感器网络网关优化部署的适应值计算函数为：
[0067]
(7)
[0068] 在交叉操作完成后，按照式（8)进行选择操作：
[0069]
(8)
[0070] 上述选择过程是指如果新产生的个体向量由于父代中相应位置的个体向量，则将 其取代父代中的个体向量，进入到新一代的种群中，使得无线传感器网络的网关位置坐标 种群能够得到持续的优化；
[0071] 步骤五、重复步骤二到步骤四直到迭代次数到达P= 500,在第500代种群中分别 按照式⑵计算各个目标向量1]5?1，^ :11)，...,1〗《对应的适应值，适应值最小的一个目标向 量即为无线传感器网络中网关的最优部署位置坐标。
【主权项】
1. 一种无线传感器网络网关优化部署方法，在传感器节点数量为η的无线传感器网络 G中设置K个网关节点，G的邻接矩阵为A= (eij)nXn，最短距离矩阵为D= 示从节点Vi路由到V」所需要的最小跳数，最短距离矩阵由Floyd算法求得；节点V i选择网 关Uk作为其服务网关，则满足式（1)的要求： d (Vi, uk)彡 d (Vi, U1)，k，1 彡 K，j 乒 I (1) 式中Wi包含在网关Uk的服务集Uk中，即V f U k，Uk与服务集Uk中节点之间的 最大距离为称为网关Uk的覆盖半径；所有网关节点中的最大覆盖半径 巴翌(外',，"*))称为网关集{%} κ的覆盖半径； 所述无线传感器网络网关优化部署方法使得网关集的覆盖半径最小，如式（2)所示：使用微分进化算法进行上述式（2)的寻优求解，定义对于K个网关节点，其在二维平面 的坐标为：(ak, bk)，k = 1，2, . . .，K，用网关坐标组成的目标向量为：X = (X1, x2, . . .，xm)，其 中= ak，X 2k= bk，第 t 组目标向量为Xt= (XtDXtW^xtni); 寻优求解的过程如下： 步骤一、网关位置向量初始化 在网络有效区域内，随机产生T组目标向量X1, X2, ...，&组成第一代种群，种群中的每 个目标向量表示一组可能的网关位置坐标；设置交叉因子F = 0. 8,交叉概率为CR = 0. 4， 最大迭代次数P = 500,按照网络区域大小设置目标向量中各维数据的上下限范围[down_ limit，up-limit]； 步骤二、网关位置向量变异操作 对于由网关位置坐标组成的第P代种群任意一个目标向量Z/7 =GyK:,...,其 中：P = 1，2,. . .，P，t = 1，2,. . .，T ;根据微分进化算法按式（3)产生下一代网关位置坐标 组成的变异向量C+1 - ;其中，和为第P代种群中随机选择的3个个体目标向量第j位的元素， 并且为3个不同的个体；交叉因子F是一个实数，用于控制差值的放大倍数，F = 0. 8 ; 按照式（3)进行元素变异操作之后，再按照式（4)以初始化过程设定的目标向量中各 维数据上下限依据，将进行元素变异操作之后超过有效界限的元素拉回到边界处：步骤三、交叉操作 在完成网关位置向量的变异操作后，产生下一代由网关位置坐标组成的交叉向量 ΨΓ 其中向量的每位元素按照式（5)进行计算其中，rand为O~1之间的随机数，jrand为1~m中的随机整数；CR是交叉概率，CR = 0. 4 ； 步骤四、选择操作 d (Vi, uk)为传感器节点Vi到网关节点u k的跳数；对于第k个网关u k，其节点位 置为（ak，bk)，k= 1，2，...，1(;距离该网关节点距离小于通信半径的传感器节点组成 的集合为?k，该网关节点到、中任意节点的跳数均为1 ;节点V $1」Θ 距离为 c/(v';，Oa. ) = @ (6/(1^))，则节点 '到网关节点u k的跳数可按式（6)计算：无线传感器网络网关优化部署的适应值计算函数为：在交叉操作完成后，按照式（8)进行选择操作：上述选择过程是指如果新产生的个体向量由于父代中相应位置的个体向量，则将其取 代父代中的个体向量，进入到新一代的种群中，使得无线传感器网络的网关位置坐标种群 能够得到持续的优化； 步骤五、重复步骤二到步骤四直到迭代次数到达P = 500,在第500代种群中分别按照 式⑵计算各个目标向量Zfxi,,Xf1对应的适应值，适应值最小的一个目标向量即 为无线传感器网络中网关的最优部署位置坐标。
【专利摘要】一种无线传感器网络网关优化部署方法，涉及一种网关优化部署方法。为了解决几何K中心下的无线传感器网络网关部署问题，以缩小覆盖半径，提高网络服务质量。主要步骤：网关位置向量初始化、网关位置向量变异操作、交叉操作、选择操作、重复上述步骤直到迭代次数到达P＝500，在第500代种群中分别计算各个目标向量对应的适应值，适应值最小的一个目标向量即为无线传感器网络中网关的最优部署位置坐标。实验结果表明，通过微分进化算法求解无线传感器网络中网关的部署位置，能够比现有基于粒子群的算法收敛速度提高50％左右，覆盖半径缩小20％，因此该方法能够显著提高网络服务质量。
【IPC分类】H04W84/18, H04W24/02
【公开号】CN104883702
【申请号】CN201510274852
【发明人】杨京礼, 许永辉, 姜守达
【申请人】哈尔滨工业大学
【公开日】2015年9月2日
【申请日】2015年5月26日