CN111818535B - 一种融合多种群优化算法的无线局域网三维优化部署方法 - Google Patents

Abstract

本发明提供一种融合多种群优化算法的无线局域网三维优化部署方法，包括获取无线AP布置范围，设定障碍物及信号衰减值；设置计算变量；初始化参数；获取果蝇个体新位置、距离及味道浓度判定值；代入目标函数中求解适应度；根据适应度，计算种群中每行果蝇的适应度分别与最优及最差果蝇之间的味道浓度差值；对比两个味道浓度差值，划分到以最差果蝇为中心的较差子群中按照粒子群搜索策略进行搜索并更新位置；或划分到以最优果蝇为中心的较优子群中围绕全局最优信息做Levy飞行并更新位置；待迭代结束，得到无线AP最小的总功率以及相应的位置。实施本发明，在保证覆盖范围的前提下，给出最优的AP位置分布和发射功率，节约能耗及降低网络部署成本。

Description

一种融合多种群优化算法的无线局域网三维优化部署方法

技术领域

本发明涉及无线局域网技术领域，尤其涉及一种融合多种群优化算法的无线局域网三维优化部署方法。

背景技术

近年来，随着移动互联网的快速发展以及学习办公地点的多样化，传统的网线接入互联网方式变得越来越不方便，特别是在人员流动性较大的公共性办公场所其局限性尤为突出。大量的无线局域网(Wireless Local Area Networks，WLAN)被部署于校园、工厂和公司等人群密集的地方，各种不同的无线接入点在我们的日常生活中随处可见。无线AP(无线接入点)拥有中继、桥接、主从模式控制等基本功能，但工作范围有限，未经合理安排放置的AP会造成一系列的问题，同时分布位置过于松散可能导致信号接收与发送的不稳定，过于紧密又可能造成资源的浪费，并带来严重的信道间干扰。

目前工程部署实施中的大部分AP部署方案都是传统的统一AP均匀分布的部署方案。例如，在酒店中每个客房部署一个无线AP，在学校中每间教室部署一个无线AP，且每个AP型号与发射功率均相同。在稍大一些场合，为了保证通信质量，所需要的基础设备更多。没有进行适当优化的情况下，这便会造成能源的浪费与设备的冗余。

优化的AP部署可以消除覆盖漏洞，减轻同信道干扰，降低能耗并降低部署预算，因此AP部署优化一直是WLAN优化中必不可少的主题。例如，早在2013年L.Ma等人就提出了一种针对高密度AP的部署和发射功率的优化方案，以节省能量并减少频率干扰。文中使用模糊K均值算法的绿色AP群集，旨在使用较少AP来保证整个覆盖范围，以及旨在节省更多能量并更好地减少频率干扰的AP发射功率优化，以节省能量并减少频率干扰。又如，随着人工智能的发展，Y.Zheng等学者又提出了一种针对WLAN的QoS优化的多智能体优化算法，该算法的多智能体系统由一组共同执行协作任务的智能体组成，在多智能体优化算法中，一个AP被视为一个智能体，并且通信区域中的所有AP组成一个分布式多智能体系统。一方面，agent可以感知其环境并采取合理的措施来改善本地环境的QoS；另一方面，系统可以全局控制代理的数量以增强优化能力并避免过早收敛。多智能体的协同搜索不仅有效的提高了搜索效率，而且有效的保证了局域网的QoS。又如，2019年，韩珍珍、徐川、王倩云、王新恒、赵国锋等人针对无线局域网中高密度的AP导致的能耗和同频干扰问题，提出了一种基于贝叶斯博弈的节能机制进行优化，通过对通用AP设备的能耗进行测量与分析，构建AP发射功率-负载-能耗的关系模型，再利用该关系模型及软件定义网络控制器实时收集的网络状态信息，设计基于贝叶斯博弈的能耗优化模型，最后利用社会选择函数求解能耗优化模型，获得干扰限制下最优的休眠AP集合和发射功率配置规则，完成用户流量卸载和AP发射功率的调整，同时保证AP参与博弈的诚实性。

但是，现有的AP部署优化存在缺点及不足，主要在于因所用的模型都为均匀模型，且每个节点具有相同的覆盖半径，导致非均匀环境下的无线AP分析及部署存在偏差，且AP位置分布考虑的因素并不全面，使发射功率并不是最优，造成AP能耗及部署成本有一定的浪费。

因此，亟需一种分层异构无线传感器网络优化方法，能在保证覆盖范围的前提下，给出最优的AP位置分布和发射功率，节约了能耗以及降低网络部署成本。

发明内容

本发明实施例所要解决的技术问题在于，提供一种融合多种群优化算法的无线局域网三维优化部署方法，能在保证覆盖范围的前提下，给出最优的AP位置分布和发射功率，节约了能耗以及降低网络部署成本。

为了解决上述技术问题，本发明实施例提供了一种融合多种群优化算法的无线局域网三维优化部署方法，所述方法包括以下步骤：

步骤S1、获取无线AP布置范围，并将所述无线AP布置范围进行网格离散化处理后，在网格离散化处理后的无线AP布置范围中，设定三种类型障碍物及每一种类型障碍物对应的信号衰减值；

步骤S2、将无线AP的位置坐标x，y、z以及功率p均设置为计算变量；

步骤S3、设置算法相关参数，包括定义4n个果蝇群体，每个果蝇种群的大小S_p和最大迭代次数I_max；其中，

果蝇种群表示如下：

4n个果蝇群体中每个个体的位置信息由公式(2)中对应的(X,Y)二维坐标给出：

其中，下标字母f代表果蝇优化中引入的变量；

初始化果蝇群位置，由下面的公式(3)、(4)和(5)计算得出：

其中，p_max为AP发射功率p的最大值；p_min为AP发射功率p的最小值；rand()是产生一个位于区间[0,1]上的随机数的函数；

初始化果蝇搜索时的飞行速度：

步骤S4、首先计算第k次迭代时，果蝇个体j到原点的距离：

其中，由公式(8)计算第k次迭代时第j个种群中所有果蝇个体的位置：

然后计算出相应的味道浓度判断值：

步骤S5、将所得到的味道浓度判定值代入目标函数(10)中，计算每一行的适应度：

其中，η_l为不满足约束条件下的惩罚函数，其约束优化问题表示为

C_∑为无线AP对目标点的覆盖率，且

c(AP_i,L_j)为第i个无线接入点AP_i对第j个目标测试点L_j的覆盖概率，且

β为传播路径中的信号衰减，且

其中，

为AP_i到测试点位置(x，y，z)的距离，γ为路径损耗指数，表示路径损耗随距离的增长率，它依赖于周围环境和建筑物类型；d₀为参考距离；α是基准距离d₀的功率；β_s是由室内障碍物引起的功率损耗，且当AP与被覆盖目标点之间跨障碍物时加上相应的障碍物衰减值；

步骤S6、根据所求解函数的适应度，利用公式(11)分别找到并记录群体中具有最佳味道浓度值的果蝇

及其相应的位置

以及群体中具有最差味道浓度值的果蝇

及其相应的位置

步骤S7、分别计算种群中每行果蝇F_l的适应度与最优果蝇

之间的味道浓度差值

和与最差果蝇

之间的味道浓度差值

步骤S8、若

则将第l行果蝇划分到以最差果蝇

为中心的较差子群中，然后转步骤S9；否则将第l行果蝇划分到以最优果蝇

为中心的较优子群中，然后转步骤S10；

步骤S9、较差子群中的果蝇利用视觉向最优果蝇位置飞去，在最优个体的指导下按照粒子群搜索策略进行搜索，在第k次(k>0)迭代中，第j个种群的第l个果蝇首先按公式(13)来更新自己的飞行速度，然后按照公式(14)来更新自己的位置。

其中，w为非负惯性权重，随着迭代次数的增加而递减，且w利用公式(15)计算：

w_max为最大惯性权重，w_min为最小惯性权重，k是当前的迭代次数，I_max为算法迭代总次数；c₁,c₂为粒子的学习因子，调节学习的最大步长；r₁,r₂是区间[0,1]上的随机数；x_{f,j,l_pbest},y_{f,j,l_pbest}是第j个种群的第l个果蝇记录的自身经过的最优位置坐标；

步骤S10、较优子群中的果蝇个体围绕着全局最优信息做Levy飞行，在第k次(k>0)迭代中，第j个种群的第l个果蝇位置更新如公式(16)所示：

其中，a为控制果蝇个体步长的参数；Levy(λ)是产生Levy飞行距离的函数；

步骤S11、进入迭代寻优，重复执行步骤S4到步骤S10，直到迭代次数达到最大迭代次数I_max或者满足其他条件后退出迭代；

步骤S12、输出具有全局最优味道浓度的果蝇信息，即得到无线AP最小的总功率以及相应的位置。

实施本发明实施例，具有如下有益效果：

本发明从信号强度、覆盖范围、空间环境等多角度出发，建立数学仿真模型，融合了粒子群搜索策略和Levy飞行机制的双子群果蝇优化算法来求取问题的最优解，生成一个最优的网络部署方案，从而在保证覆盖范围的前提下，给出最优的AP位置分布和发射功率，节约了能耗以及降低网络部署成本。

附图说明

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

图1为本发明实施例提供的融合多种群优化算法的无线局域网三维优化部署方法的流程图；

图2为本发明实施例提供的融合多种群优化算法的无线局域网三维优化部署方法中融合了粒子群搜索策略和Levy飞行机制的双子群果蝇优化算法的示意图；

图3为本发明实施例提供的融合多种群优化算法的无线局域网三维优化部署方法应用之前未限定AP部署高度的部署示意图；

图4本发明实施例提供的融合多种群优化算法的无线局域网三维优化部署方法应用于图3中限定AP部署于楼层顶部的部署示意图。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚，下面将结合附图对本发明作进一步地详细描述。

如图1所示，为本发明实施例中，提出的一种融合多种群优化算法的无线局域网三维优化部署方法，所述方法包括以下步骤：

步骤S1、获取无线AP布置范围，并将所述无线AP布置范围进行网格离散化处理后，在网格离散化处理后的无线AP布置范围中，设定三种类型障碍物及每一种类型障碍物对应的信号衰减值；

步骤S2、将无线AP的位置坐标x，y、z以及功率p均设置为计算变量；

步骤S3、设置算法相关参数，包括定义4n个果蝇群体，每个果蝇种群的大小S_p和最大迭代次数I_max；其中，

果蝇种群表示如下：

4n个果蝇群体中每个个体的位置信息由公式(2)中对应的(X,Y)二维坐标给出：

其中，下标字母f代表果蝇优化中引入的变量；

初始化果蝇群位置，由下面的公式(3)、(4)和(5)计算得出：

其中，p_max为AP发射功率p的最大值；p_min为AP发射功率p的最小值；rand()是产生一个位于区间[0,1]上的随机数的函数；

初始化果蝇搜索时的飞行速度：

步骤S4、首先计算第k次迭代时，果蝇个体j到原点的距离：

其中，由公式(8)计算第k次迭代时第j个种群中所有果蝇个体的位置：

然后计算出相应的味道浓度判断值：

步骤S5、将所得到的味道浓度判定值代入目标函数(10)中，计算每一行的适应度：

其中，η_l为不满足约束条件下的惩罚函数，其约束优化问题表示为

C_∑为无线AP对目标点的覆盖率，且

c(APi,L_j)为第i个无线接入点AP_i对第j个目标测试点L_j的覆盖概率，且

β为传播路径中的信号衰减，且

其中，

为AP_i到测试点位置(x，y，z)的距离，γ为路径损耗指数，表示路径损耗随距离的增长率，它依赖于周围环境和建筑物类型；d₀为参考距离；α是基准距离d₀的功率；β_s是由室内障碍物引起的功率损耗，且当AP与被覆盖目标点之间跨障碍物时加上相应的障碍物衰减值；

步骤S6、根据所求解函数的适应度，利用公式(11)分别找到并记录群体中具有最佳味道浓度值的果蝇

及其相应的位置

以及群体中具有最差味道浓度值的果蝇

及其相应的位置

步骤S7、分别计算种群中每行果蝇F_l的适应度与最优果蝇

之间的味道浓度差值

和与最差果蝇

之间的味道浓度差值

步骤S8、若

则将第l行果蝇划分到以最差果蝇

为中心的较差子群中，然后转步骤S9；否则将第l行果蝇划分到以最优果蝇

为中心的较优子群中，然后转步骤S10；

步骤S9、较差子群中的果蝇利用视觉向最优果蝇位置飞去，在最优个体的指导下按照粒子群搜索策略进行搜索，在第k次(k>0)迭代中，第j个种群的第l个果蝇首先按公式(13)来更新自己的飞行速度，然后按照公式(14)来更新自己的位置。

其中，w为非负惯性权重，随着迭代次数的增加而递减，且w利用公式(15)计算：

w_max为最大惯性权重，w_min为最小惯性权重，k是当前的迭代次数，I_max为算法迭代总次数；c₁,c₂为粒子的学习因子，调节学习的最大步长；r₁,r₂是区间[0,1]上的随机数；x_{f,j,l_pbest},y_{f,j,l_pbest}是第j个种群的第l个果蝇记录的自身经过的最优位置坐标；

步骤S10、较优子群中的果蝇个体围绕着全局最优信息做Levy飞行，在第k次(k>0)迭代中，第j个种群的第l个果蝇位置更新如公式(16)所示：

其中，a为控制果蝇个体步长的参数；Levy(λ)是产生Levy飞行距离的函数；

步骤S11、进入迭代寻优，重复执行步骤S4到步骤S10，直到迭代次数达到最大迭代次数I_max或者满足其他条件后退出迭代；

步骤S12、输出具有全局最优味道浓度的果蝇信息，即得到无线AP最小的总功率以及相应的位置。

具体过程为，在步骤S1中，将无线AP布置范围(如100m*100m*10m的三维立体空间)进行网络离散化处理(如，三维立体空间被离散化为100个网格，网格中心被视为覆盖目标点)，然后，在目标区域引入了三种不同类型的障碍物(如承重墙、砖墙和隔断层)，不同的障碍物对应不同的信号衰减值。

在步骤S2中，设置AP的位置坐标x，y，z以及功率p都是计算变量，为了计算方便，采用比值法将数据变量进行统一。具体如下：

x_k＝(x_k-x_min)/(x_max-x_min)

y_k＝(y_k-y_min)/(y_max-y_min)

z_k＝(z_k-y_min)/(z_max-z_min)

p_k＝(p_k-p_min)/(p_max-p_min)

在步骤S3中，对果蝇种群、种群位置以及迭代次数等参数进行初始化。

在步骤S4中，执行果蝇嗅觉搜索过程，当群体中的每一只果蝇利用其嗅觉搜索时，赋予它一个随机的飞行方向和距离。因为食物(指代参数)味道的来源位置是未知的，因此先计算果蝇个体距离原点的距离，然后计算其味道浓度判定值。

在步骤S5中，设置包括信号覆盖率及传播路径中信号衰减值的目标函数，求解适应度更优的果蝇作为当前进行搜索的果蝇。

在步骤S6中，找到具有最佳味道浓度值的果蝇及其相应的位置，以及最差味道浓度值的果蝇及其相应的位置。

在步骤S7中，计算每行果蝇F_l的适应度与具有最佳味道浓度值的果蝇之间的味道浓度差值，以及每行果蝇F_l的适应度与具有最差味道浓度值的果蝇之间的味道浓度差值。

在步骤S8中，对比上述两个味道浓度差值，如果前者大于后者，将第l行果蝇划分到以最差果蝇

为中心的较差子群中后，进入步骤S9；如果前者小于等于后者，则将第l行果蝇划分到以最优果蝇

为中心的较优子群中后，进入步骤S10。

在步骤S9中，较差子群中的果蝇利用视觉向最优果蝇位置飞去，在最优个体的指导下按照粒子群搜索策略进行搜索，并更新飞行速度及位置。

在步骤S10中，较优子群中的果蝇个体围绕着全局最优信息做Levy飞行，并更新位置。

在步骤S11中，进入迭代寻优，重复执行步骤S4到步骤S10，直到迭代次数达到最大迭代次数I_max或者满足其他条件后退出迭代。

在步骤S12中，输出步骤S11中最后迭代输出的具有全局最优味道浓度的果蝇信息，即得到无线AP最小的总功率以及相应的位置。

应当说明的是，本发明融合了粒子群搜索策略和Levy飞行机制的双子群果蝇优化算法(Levy_PSO_FOA)。该算法以FOA算法为主体，在果蝇群体迭代过程中，分别计算种群中果蝇个体i与当代种群中最优个体和最差个体的距离Dist_{i_best}和Dist_{i_worst}，若Dist_{i_best}＞Dist_{i_worst}则将果蝇个体i划分到以最差个体为中心的较差子群中，否则将其划分到以最优个体为中心的较优子群中(每次迭代时重新划分较优子群与较差子群，两个子群动态变化)。然后根据两个子群的不同特点，较差子群在最优个体的指导下以粒子群搜索策略进行搜索，较优子群则围绕全局最优信息做Levy飞行，两个子群通过最优个体的更新和子群的重组进行信息的交换。如图2所示，为Levy_PSO_FOA示意图。

如图3所示，为本融合多种群优化算法的无线局域网三维优化部署方法应用之前未限定AP部署高度的部署示意图；图4本发明实施例提供的融合多种群优化算法的无线局域网三维优化部署方法应用于图3中AP部署于楼层顶部的部署示意图。从图3和图4中对比可知，图4在保证图3中覆盖范围的前提下，给出最优的AP位置分布和发射功率，节约了能耗以及降低网络部署成本。

实施本发明实施例，具有如下有益效果：

本发明从信号强度、覆盖范围、空间环境等多角度出发，建立数学仿真模型，融合了粒子群搜索策略和Levy飞行机制的双子群果蝇优化算法来求取问题的最优解，生成一个最优的网络部署方案，从而在保证覆盖范围的前提下，给出最优的AP位置分布和发射功率，节约了能耗以及降低网络部署成本。

本领域普通技术人员可以理解实现上述实施例方法中的全部或部分步骤是可以通过程序来指令相关的硬件来完成，所述的程序可以存储于一计算机可读取存储介质中，所述的存储介质，如ROM/RAM、磁盘、光盘等。

以上所揭露的仅为本发明一种较佳实施例而已，当然不能以此来限定本发明之权利范围，因此依本发明权利要求所作的等同变化，仍属本发明所涵盖的范围。

Claims (1)

1.一种融合多种群优化算法的无线局域网三维优化部署方法，其特征在于，所述方法包括以下步骤：

步骤S1、获取无线AP布置范围，并将所述无线AP布置范围进行网格离散化处理后，在网格离散化处理后的无线AP布置范围中，设定三种类型障碍物及每一种类型障碍物对应的信号衰减值；

步骤S2、将无线AP的位置坐标x，y、z以及功率p均设置为计算变量；

步骤S3、设置算法相关参数，包括定义4n个果蝇群体，每个果蝇种群的大小S_p和最大迭代次数I_max；其中，

果蝇种群表示如下：

4n个果蝇群体中每个个体的位置信息由公式(2)中对应的(X,Y)二维坐标给出：

其中，下标字母f代表果蝇优化中引入的变量；

初始化果蝇群位置，由下面的公式(3)、(4)和(5)计算得出：

其中，p_max为AP发射功率p的最大值；p_min为AP发射功率p的最小值；rand()是产生一个位于区间[0,1]上的随机数的函数；

初始化果蝇搜索时的飞行速度：

步骤S4、首先计算第k次迭代时，果蝇个体j到原点的距离：

其中，由公式(8)计算第k次迭代时第j个种群中所有果蝇个体的位置：

然后计算出相应的味道浓度判断值：

步骤S5、将所得到的味道浓度判定值代入目标函数(10)中，计算每一行的适应度：

其中，η_l为不满足约束条件下的惩罚函数，其约束优化问题表示为

C_∑为无线AP对目标点的覆盖率，且

c(AP_i,L_j)为第i个无线接入点AP_i对第j个目标测试点L_j的覆盖概率，且

β为传播路径中的信号衰减，且

其中，

为AP_i到测试点位置(x，y，z)的距离，γ为路径损耗指数，表示路径损耗随距离的增长率，它依赖于周围环境和建筑物类型；d₀为参考距离；α是基准距离d₀的功率；β_s是由室内障碍物引起的功率损耗，且当AP与被覆盖目标点之间跨障碍物时加上相应的障碍物衰减值；

步骤S6、根据所求解函数的适应度，利用公式(11)分别找到并记录群体中具有最佳味道浓度值的果蝇

及其相应的位置

以及群体中具有最差味道浓度值的果蝇

及其相应的位置

步骤S7、分别计算种群中每行果蝇F_l的适应度与最优果蝇

之间的味道浓度差值

和与最差果蝇

之间的味道浓度差值

步骤S8、若

则将第l行果蝇划分到以最差果蝇

为中心的较差子群中，然后转步骤S9；否则将第l行果蝇划分到以最优果蝇

为中心的较优子群中，然后转步骤S10；

步骤S9、较差子群中的果蝇利用视觉向最优果蝇位置飞去，在最优个体的指导下按照粒子群搜索策略进行搜索，在第k次(k>0)迭代中，第j个种群的第l个果蝇首先按公式(13)来更新自己的飞行速度，然后按照公式(14)来更新自己的位置：

其中，w为非负惯性权重，随着迭代次数的增加而递减，且w利用公式(15)计算：

w_max为最大惯性权重，w_min为最小惯性权重，k是当前的迭代次数，I_max为算法迭代总次数；c₁,c₂为粒子的学习因子，调节学习的最大步长；r₁,r₂是区间[0,1]上的随机数；x_{f,j,l_pbest},y_{f,j,l_pbest}是第j个种群的第l个果蝇记录的自身经过的最优位置坐标；

步骤S10、较优子群中的果蝇个体围绕着全局最优信息做Levy飞行，在第k次(k>0)迭代中，第j个种群的第l个果蝇位置更新如公式(16)所示：

其中，a为控制果蝇个体步长的参数；Levy(λ)是产生Levy飞行距离的函数；

步骤S11、进入迭代寻优，重复执行步骤S4到步骤S10，直到迭代次数达到最大迭代次数I_max或者满足其他条件后退出迭代；

步骤S12、输出具有全局最优味道浓度的果蝇信息，即得到无线AP最小的总功率以及相应的位置。

Images