基于果蝇优化的非均匀环境的无线AP部署优化方法

技术领域

本发明涉及无线AP技术领域，尤其涉及一种基于果蝇优化的非均匀环境的无线AP部署优化方法。

背景技术

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

目前，国内外的研究工作主要集中在无线传感器网络(WSN)的拓扑优化，而对非均匀环境下的WLAN的优化较少。例如，在2015年H.Zhao,Q.Zhang,L.Zhang Y.Wang等人提出了一种基于果蝇优化算法的无线传感器网络的传感器部署优化的方法，该方法通过利用果蝇优化算法对传感器的部署位置进行优化，使得其覆盖率具有了明显的提升，同时也大大的提高了网络的鲁棒性。又如，在2016年金鑫等学者提出了一种基于Ad Hoc无线传感网络的三维智能组网优化算法，通过对生成网络的簇头数及分簇平衡度进行分析，优化了分簇算法生成分级网络的过程，使得生成的分簇结构更加稳定。又如，2018年学者王月琴通过遗传算法对小型无线网络进行优化，将WLAN热点中的智能无线AP类比为分布在遗传算法模块的种群，通过对AP的遗传操作以求达到WLAN热点的网络达到最优化。

然而，上述网络拓扑优化方法中，因所用的模型都为均匀模型，且每个节点具有相同的覆盖半径，导致非均匀环境下的无线AP分析及部署存在偏差。上述无线AP分析及部署存在偏差的主要原因在于：实际无线信号传播过程中，信号的衰减与传播距离并不是线性关系，而且当传播当中遇到障碍物阻挡时，信号还会有比较明显的衰减。

发明内容

本发明实施例所要解决的技术问题在于，提供一种基于果蝇优化的非均匀环境的无线AP部署优化方法，在传播环境中引入不同类型的障碍物构成非均匀的传播环境，并将无线AP部署位置与功率进行联合优化，从而解决现有技术中非均匀环境下无线AP分析及部署偏差问题。

为了解决上述技术问题，本发明实施例提供了一种基于果蝇优化的非均匀环境的无线AP部署优化方法，包括以下步骤：

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

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

步骤S3、设置迭代次数maxgen，以及设置3n个果蝇种群为

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

其初始位置由下面的公式(3)和(4)给出：

其中，p_max为功率p的最大值；p_min为功率p的最小值；L为种群位置范围；

步骤S4、果蝇个体i通过嗅觉随机搜寻食物，利用公式(5)和(6)得到果蝇个体i的新位置，并根据果蝇个体i的新位置，利用公式(7)得到果蝇个体i距离原点的距离，以及进一步根据果蝇个体i距离原点的距离，利用公式(8)得到味道浓度判定值；

其中，σ₁＝1为果蝇i对应位置坐标更新的步长；σ₂＝0.5为果蝇i对应发射功率更新的步长；

步骤S5、将所得到的味道浓度判定值代入目标函数(9)中，求解函数的适应度；

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

min(∑_i∈np_i)+η

s.t.C₁:C_∑≥C_min

C₂:p_min≤p_i≤p_max；C_∑为目标区域的覆盖率，且c(AP_i,L_j)为第i个无线AP对第j个目标点的覆盖率，且β为传播路径中的信号衰减，且β_s是由障碍物引起的信号衰减，且当AP位置与覆盖目标点之间跨障碍物时加上相应的障碍物衰减值；

步骤S6、根据所求解函数的适应度，利用公式(10)选择群体中具有最佳味道浓度值的果蝇及其相应的位置并记录其味道浓度值；

步骤S7、判断果蝇的味道浓度值是否优于当前最优味道浓度值；

步骤S8、如果否，则返回步骤S4，直至迭代次数maxgen迭代完毕为止；

步骤S9、如果是，则将果蝇的味道浓度设为最优味道浓度值，并利用公式(11)得到对应果蝇位置信息，群体中的其他果蝇均利用视觉飞向此位置后，返回步骤S4，直至迭代次数maxgen迭代完毕为止；

步骤S10、输出最优味道浓度值的果蝇的位置，即得到无线AP最小的总功率以及相应的位置。

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

本发明提出一种无线网络拓扑的非均匀模型，在传播环境中引入不同类型的障碍物构成非均匀的传播环境，并将AP部署的位置与功率进行联合优化，使得网络部署方案的整体功耗达到最小，并对网络覆盖质量没有贡献作用的AP进行筛除，生成一个最优的部署方案，在保证覆盖范围的前提下尽可能的节约能耗以及网络部署成本，从而解决现有技术中非均匀环境下无线AP分析及部署偏差问题。

附图说明

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

图1为本发明实施例提出的一种基于果蝇优化的非均匀环境的无线AP部署优化方法的流程图；

图2为本发明实施例提出的一种基于果蝇优化的非均匀环境的无线AP部署优化方法与现有技术各自应用部署36个无线AP的对比图；

图3为本发明实施例提出的一种基于果蝇优化的非均匀环境的无线AP部署优化方法中36个无线AP的具体覆盖范围分布图；

图4为本发明实施例提出的一种基于果蝇优化的非均匀环境的无线AP部署优化方法与现有技术各自应用部署49个无线AP的对比图；

图5为本发明实施例提出的一种基于果蝇优化的非均匀环境的无线AP部署优化方法中49个无线AP的具体覆盖范围分布图。

具体实施方式

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

如图1所示，为本发明实施例中，提出的一种基于果蝇优化的非均匀环境的无线AP部署优化方法，包括以下步骤：

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

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

步骤S3、设置迭代次数maxgen，以及设置3n个果蝇种群为

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

其初始位置由下面的公式(3)和(4)给出：

其中，p_max为功率p的最大值；p_min为功率p的最小值；L为种群位置范围；

步骤S4、果蝇个体i通过嗅觉随机搜寻食物，利用公式(5)和(6)得到果蝇个体i的新位置，并根据果蝇个体i的新位置，利用公式(7)得到果蝇个体i距离原点的距离，以及进一步根据果蝇个体i距离原点的距离，利用公式(8)得到味道浓度判定值；

其中，σ₁＝1为果蝇i对应位置坐标更新的步长；σ₂＝0.5为果蝇i对应发射功率更新的步长；

步骤S5、将所得到的味道浓度判定值代入目标函数(9)中，求解函数的适应度；

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

min(∑_i∈np_i)+η

s.t.C₁:C_∑≥C_min

C₂:p_min≤p_i≤p_max；C_∑为目标区域的覆盖率，且c(AP_i,L_j)为第i个无线AP对第j个目标点的覆盖率，且β为传播路径中的信号衰减，且β_s是由障碍物引起的信号衰减，且当AP位置与覆盖目标点之间跨障碍物时加上相应的障碍物衰减值；

步骤S6、根据所求解函数的适应度，利用公式(10)选择群体中具有最佳味道浓度值的果蝇及其相应的位置并记录其味道浓度值；

步骤S7、判断果蝇的味道浓度值是否优于当前最优味道浓度值；

步骤S8、如果否，则返回步骤S4，直至迭代次数maxgen迭代完毕为止；

步骤S9、如果是，则将果蝇的味道浓度设为最优味道浓度值，并利用公式(11)得到对应果蝇位置信息，群体中的其他果蝇均利用视觉飞向此位置后，返回步骤S4，直至迭代次数maxgen迭代完毕为止；

步骤S10、输出最优味道浓度值的果蝇的位置，即得到无线AP最小的总功率以及相应的位置。

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

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

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

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

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

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

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

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

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

在步骤S7中，对比所找到味道浓度值是否优于当前最优味道浓度值，如果否，进入步骤S8，则返回重复步骤S4～步骤S6重新进行迭代，直至迭代次数结束；如果是，则进入步骤S9，将所找到果蝇的味道浓度设为最优味道浓度值，并得到对应果蝇位置信息后，返回重复步骤S4～步骤S6重新进行迭代，直至迭代次数结束。

在步骤S10中，输出步骤S8中最后迭代或者步骤S9中最优味道浓度值的果蝇的位置，即得到无线AP最小的总功率以及相应的位置。

如图2所示，为本发明实施例提出的一种基于果蝇优化的非均匀环境的无线AP部署优化方法与现有技术各自应用部署36个无线AP的对比图；图3为图2中36个无线AP的具体覆盖范围分布图。

如图4所示，为本发明实施例提出的一种基于果蝇优化的非均匀环境的无线AP部署优化方法与现有技术各自应用部署49个无线AP的对比图；图5为图4中49个无线AP的具体覆盖范围分布图。

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

本发明提出一种无线网络拓扑的非均匀模型，在传播环境中引入不同类型的障碍物构成非均匀的传播环境，并将AP部署的位置与功率进行联合优化，使得网络部署方案的整体功耗达到最小，并对网络覆盖质量没有贡献作用的AP进行筛除，生成一个最优的部署方案，在保证覆盖范围的前提下尽可能的节约能耗以及网络部署成本，从而解决现有技术中非均匀环境下无线AP分析及部署偏差问题。

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

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