基于多目标优化的AP选取新算法

张　伟,花向红,邱卫宁,吴　帮,畅　鑫

(1．武汉大学 测绘学院,湖北 武汉 430079；2.武汉大学 灾害监测与防治研究中心，湖北 武汉 430079)



基于多目标优化的AP选取新算法

张伟1,2,花向红1,2,邱卫宁1,2,吴帮1,2,畅鑫1

(1．武汉大学 测绘学院,湖北 武汉 430079；2.武汉大学 灾害监测与防治研究中心，湖北 武汉 430079)

讨论基于RSS的Wi-Fi室内定位中基于多目标优化的AP选取问题。综合考虑信息增益(JIG)和互信息(MI)的多目标优化函数的推导过程，同时利用基因算法(GA)寻求多目标函数的最优解。两种差异明显的环境下的实验结果表明：复杂环境中信息增益和互信息最佳权重分别为0.3和0.7，稳定环境中互信息的最佳权重分别为0.7和0.3，同时位置估计结果分析表明：不同AP个数下的位置误差的方差和平均值之间存在明显的线性相关性。

多目标优化；AP选取；信息增益；互信息；GA算法

由于GPS在室内不能很好地工作[1-2]，近年来，国内外学者进行了大量的室内定位和室内导航的研究，尤其是基于IEEE802.11 或 802.15标准的Wi-Fi定位追踪系统[3-4]。Wi-Fi室内定位系统利用现有的无线局域网基础设施，是一种多功能、低成本的定位技术[5]。Wi-Fi定位存在基于指纹和基于模型的两种定位方法，基于指纹的定位与线下阶段建立的指纹库进行匹配定位，基于模型的定位方法构建接收信号强度(RSS)和距离之间的关系[6]。由于多径的影响[7]，基于指纹的Wi-Fi室内定位精度较低，如何选取观测质量较好的无线访问接入点(AP)对于Wi-Fi室内定位至关重要[8]。

由于Wi-Fi网络的广泛部署，在一个单一的位置观察10～20的AP且在一个单一的建筑观测到50多个AP是很常见的[9]。AP选择的目的是从所有可用的AP中选择一个子集，从而减少计算量和提高定位的精度。文献[8]中提出了一种基于位置信息增益的AP选取方法，但是该方法没有考虑AP之间的相关性。文献[10]进一步提出了利用联合信息增益改进的AP选取方法，从而考虑不同AP集合的判别能力的相关性。Han Zou等[11]提出了基于互信息的线上AP选取策略，从而提取最有价值的特征成分并减小冗余。互信息是随机变量独立性的自然信息理论测度，因此，较小的互信息表示较小的相关性[12]。基于联合信息增益的AP选取策略和基于互信息的AP选取策略都是重要的信息熵指标，两种方法都有各自的优势且他们的定位结果受环境变化的影响较大。一般而言，由于无法考虑RSS测量的综合信息，基于单目标优化的AP选择方法往往对Wi-Fi室内定位系统产生不利影响。

本文提出了一种新的基于多目标优化的AP选择方法用于Wi-Fi室内定位，同时考虑AP子集的判别能力、AP子集的相关性以及冗余。多目标优化通常用一个固定的权重将不同的目标聚合成一个目标函数[13-14]。本文推导了一个新的目标函数实现，同时使得AP子集的联合信息增益最大且互信息最小。基因算法被用来计算多目标优化问题的最优标量适应值[15-17]。利用多目标优化选取AP子集后，用 WKNN方法进行位置估计。在不同的环境下进行实验并对实验中的线性回归模型的显著性进行假设检验。利用F检验对回归方程整体显著性进行检验，同时，t检验被用于回归参数显著性的检验[18-19]。结果表明：联合信息的增益和相互信息最佳的权重与环境有关，且不同AP个数下的位置精度的标准方差和平均值之间存在线性相关性。

1　基于多目标优化的AP选择策略

考虑基于联合信息增益和互信息的两种AP选取策略各自不同的优势，本文利用加权求和的方法提出一个新的多目标优化函数，实现两种信息量融合的AP选取：

(1)

式中：fitness表示多目标优化函数的适应度，即目标函数，fitness越小对应的AP组合观测质量越好，wIG和wMI分别表示联合信息增益和简化互信息对应的权重，且满足wIG≥0,wMI≥0,wIG+wMI=1，IGSta和MISta分别表示标准化后的联合信息增益和互信息。

1.1联合信息增益计算

基于RSS的Wi-Fi指纹定位AP子集对于位置区分度的贡献可以采用信息增益的大小表示，考虑N个AP之间的相关性的联合信息增益计算公式

(2)

式(2)中的信息增益IG满足不等式IG≥0，考虑信息熵的不等式[20-21]有

(3)

信息增益的单位化公式

(4)

1.2互信息计算

AP子集选取除了需要考虑信息增益量化指标外，互信息也是衡量AP集合质量好坏的一个指标，下面给出简化互信息计算公式

(5)

对于N个AP中的任意NSub个AP组合，满足MI(AP1,AP2,…,APNsub)=min的AP组合即最优的AP组合。考虑信息熵满足不等式以及信息熵的定义[20]，有

(6)

式中：Nmax表示N个AP中，观测值不同取值个数最大的AP对应的观测值不同取值个数。则有简化互信息单位化公式

(7)

1.3多目标优化函数解算

GA(基因算法)是一种受自然界优胜劣汰的生物进化论启发而提出的目标搜索算法。基于GA的AP选取算法的伪代码如下:

Initialize (产生父代种群)

While (迭代收敛)

{

Selection (选取父代种群的优良个体)

Reproduction (产生子代种群)

Mutation (子代种群变异)

Evaluate (子代群体择优产生新的父代种群)

}

Decode(解码)

第一步：在Initialize阶段，将问题解决方案表示为二进制编码。对于N个AP的优化子集选取问题，二进制编码组合的长度为N，即种群中个体的染色体序列长度为N，且每个染色体对应于一个AP。当染色体编码为1时表示其对应的AP作为最优AP，编码为0时则表示对应的AP并非最优的AP。个体随机编码示意图如图1所示。

图1　个体随机编码(与AP一一对应)

为了通过GA算法搜索最优目标个体，需要在Initialize阶段产生一定数量的个体，即产生种群。

第2步：按照式(1)计算种群中所有个体的适应值(即目标函数值)。获取所有个体的适应度后，按照轮盘赌法选取NS个优良个体。个体选中的概率采用与适应度成反比的加权法，每个个体的权重计

算公式为

(8)

式中：wi表示第i个个体选中的概率，fitnessi表示第i个个体的适应度，NP表示父代群体的个体数。

第3步：利用变异算子对选取的子代个体进行变异操作。由于最优AP子集的个数设置为NSub，因此，变异算子需要交换个体的两个染色体编码完成个体变异操作。个体的染色体编码交换示意图如图2所示。

图2　编码变异示意图

变异算子在变异前需要计算是否产生变异的概率，个体的染色体变异的概率与当前位置染色体编码有关。假定当前位置染色体的编码为1，则计算NS个优良个体中当前位置编码为1的个数N1；若当前位置染色体的编码为0，则计算NS个优良个体中当前位置编码为0的个数N0。该位置编码变异的概率计算公式为

(9)

式中：wi(1≤i≤N)表示个体当前位置染色体的变异概率。为了避免某个染色体的变异概率为0而弱化新群体的多样性，式中分母、分子同时加1使得其变异概率永远大于0。则个体的变异操作发生的概率计算公式为

(10)

式中：wm表示染色体交换算子的概率，即个体的第i个染色体和第j个染色体编码互换的概率，wi，wj分别表示其变异概率。

第4步：计算变异后新产生个体的适应值，与父代群体进行比较，按照个体适应度的大小选取适应度最小的N个个体作为新的父代群体，完成种群进化，记录当前种群的最小适应值。

第5步：循环执行步骤2～4，直到满足迭代终止条件，即群体的最小适应度不再变化为止。

第6步：对具有最小适应度的个体进行解码，找出其编码为1的染色体对应的AP，从而获取最终需要的最优AP子集。

1.4位置估计及精度分析

利用GA算法找出最优AP子集后，利用典型的WKNN算法进行位置估计。位置估计的误差计算公式为

(11)

(12)

式中：σ表示位置估计的精度，NT表示所有定位点的个数，di表示第i个点位置估计的误差。

由于不同AP子集个数会对位置估计的精度产生影响，为了分析多目标优化函数中联合信息增益和互信息的最佳权重方案，在每个权重方案下分别计算多种不同AP子集个数情况下的位置估计精度，同时按照式(13)计算其精度的平均值和方差。

(13)

式中：σk表示AP子集个数为k时的位置估计精度(文中考虑了k取4～10的7种情况)，Ave表示设置不同AP子集个数时位置估计精度的均值，Var表示其对应的方差。一次线性回归模型被用来分析精度均值和方差之间关系，其拟合模型为

(14)

式中：β0为回归方程常数项，β1为回归方差一次性系数。

2　实验分析

为了分析基于多目标优化的AP选取策略对Wi-Fi位置估计的精度影响，本文在两个不同的环境下进行了两组实验。实验1在11 m×7 m大小的办公室进行，该房间存在多个AP且实验时段存在人员任意走动的情况。实验2在11 m×10 m大小的会议室进行，该房间内部不存在AP且实验在没有人员走动的情况下进行。两种不同环境下的实验点位分布相同，分别采集6个指纹点和9个定位点的Wi-Fi接收信号强度数据，数据点之间的间隔为2 m。实验信号接收器采用小米手机，并采用全站仪获取校准点的点位坐标。实验不考虑AP分布的影响，采用实际环境中可用的AP进行实验分析。建立两种不同环境的实验方案分布如图3所示。

图3　实验方案分布

图3中，‘●’表示指纹点，‘▇’表示定位点。为了分析不同权重配比方案时的AP选取策略对位置估计精度的影响，本文分别计算了11种不同权重方案时的位置估计精度，用于分析位置估计精度的变化。不同权重方案见表1。

考虑到AP子集个数对位置估计的影响，本文同时分析了AP子集个数,分别设置为4～10的多种情况，即4≤NSub≤10。图4和图5分别给出两种不同环境下设置不同AP子集个数时，定位精度随着权重配比方案的变化曲线。

表1　不同的权重配比方案

图4　实验场景1下定位精度变化曲线

图5　实验场景2下定位精度变化曲线

从图4和图5可以看出，在指定AP子集个数的情况下，位置估计的精度随着权重方案的改变没有明显的关系。由于信息增益和互信息均是信息熵的一种度量指标，因此，在指定AP个数的情况下，位置估计精度随着权重方案(信息增益权重逐渐增大、互信息权重逐步减小)变化呈现一种波动趋势，二者权重调整的优劣无法通过位置估计精度衡量。然而，通过观察指定权重方案下精度随着AP子集个数的变化可以看出：场景1采取D权重方案(信息增益权重0.3，互信息权重0.7)时，精度随着不同AP个数变化的波动最小，即位置估计精度随着最优子集个数变化产生的差异最小，而场景2采取H方案时精度随着不同AP个数变化的波动最小。表2给出了不同精度权重方案下，AP个数分别取4～10时位置估计精度的平均值和方差。

表2　不同权重方案下4～10个AP的位置

从表2可以看出,场景1中选取D权重方案时，AP个数取4～10的位置估计精度变化的方差最小，且其平均值优于除H方案之外的任意其他方案；场景2中选取H权重方案时，AP个数取4～10

的位置估计变化的方差最小，然而，其E方案的位置估计精度平均值最小，为了进一步分析位置估计精度平均值与方差的关系，图6给出了精度平均值随方差变化的曲线。

图6　方差与精度均值散点图

图6分别显示了场景1中方差与精度均值的离散点示意图和场景2中方差与精度均值的离散点示意图，图中直线为基于最小二乘的一次线性回归结果。从图中可以看出，精度均值与方差存在一定的正线性相关关系，即方差越小，精度均值越小，位置估计精度整体性越好。表3给出了一次线性回归系数及其显著性检验。

表3　回归系数及其显著性检验

3　结束语

本文提出了一种新的基于GA的多目标优化的AP选取算法，制定了基于联合信息增益和简化互信息的多目标优化AP选取的完整步骤，为多目标优化的AP选取提供了参考。同时，通过分析位置估计精度与不同权重配比方案以及不同AP子集个数设置发现：在指定AP个数的情况下，位置估计精度与权重方案没有明显的关系，随着联合信息增益权重的增加以及互信息权重的减少，位置估计精度呈现波动的特性。然而在指定的权重方案下，通过求取不同AP子集个数位置估计精度的平均值和方差发现，位置估计精度的平均值与方差呈现明显的线性相关性，即方差越小，位置估计精度的平均值越小，位置估计的精度越好。因此，可以在不同权重配比情况下，通过设置不同的AP子集个数，计算该环境下位置估计精度的方差，选取方差最小的权重方案作为该环境下的最优权重方案。

[1]DJUKNICGM,RICHTONRE.GeolocationandassistedGPS[J].Computer, 2001, 34(2):123-125.

[2]WOOS,JEONGS,MOKE,etal.ApplicationofWiFi-basedindoorpositioningsystemforlabortrackingatconstructionsites:AcasestudyinGuangzhouMTR[J].AutomationinConstruction, 2011, 20(1):3-13.

[3]ABOODIA,WANTC.EvaluationofWiFi-BasedIndoor(WBI)PositioningAlgorithm[C]. 2012ThirdFTRAInternationalConferenceonMobile,Ubiquitous,andIntelligentComputing.IEEEComputerSociety, 2012:260-264.

[4]KANANR,ELHASSANO.AcombinedbatterylessradioandWiFiindoorPositioningSystem[C].SoftCOM2015 23rdInternationalConferenceonSoftware,TelecommunicationsandComputerNetworks,IEEE, 2015: 101-107.

[5]KULG, ÖZYERT,TAVLIB.WLANBasedRealTimeIndoorPositioning:LiteratureSurveyandExperimentalInvestigations[J].ProcediaComputerScience, 2014, 34(34):157-164.

[6]LEW,WANGZ,WANGJ,etal.AnovelWIFIindoorpositioningmethodbasedonGeneticAlgorithmandTwinSupportVectorRegression[C]. 第26届中国控制与决策会议论文集. 2014:4859-4862.

[7]YANGC,SHAOHR.WiFi-basedindoorpositioning[J].IEEECommunicationsMagazine, 2015, 53(3):150-157.

[8]CHENY,YANGQ,YINJ,etal.Power-efficientaccess-pointselectionforindoorlocationestimation[J].IEEETransactionsonKnowledge&DataEngineering, 2006, 18(7):877-888.

[9]EISAS,PEIXOTOJ,MENESESF,etal.RemovinguselessAPsandfingerprintsfromWiFiindoorpositioningradiomaps[C]. 2013InternationalConferenceonIndoorPositioningandIndoorNavigation,IEEE, 2013:1-7.

[10]DENGZ,MAL,XUY.IntelligentAPselectionforindoorpositioninginwirelesslocalareanetwork[C].Proceedingsofthe9thWorldRabbitCongress, 2011:257-261.

[11]ZOUH,LUOY,LUX,etal.AmutualinformationbasedonlineaccesspointselectionstrategyforWiFiindoorlocalization[C]. 2015IEEEInternationalConferenceonAutomationScienceandEngineering,Gothenburg.IEEE, 2015: 180-185.

[12]HYVRINENA,KARHUNENJ,OJAE.IndependentComponentAnalysis[M].TokyoDenkiUniversityPress,Tokyo, 2002.

[13]DEBK.Multi-ObjectiveOptimization[M].SearchMethodologies.SpringerUS, 2005.

[14]DEBK.MultiobjectiveOptimization[J].DecisionEngineering, 2008, 31(6):193-262.

[15]KONAKA,COITDW,SMITHAE.Multi-objectiveoptimizationusinggeneticalgorithms:Atutorial[J].ReliabilityEngineering&SystemSafety, 2006, 91(9):992-1007.

[16]MURATAT,ISHIBUCHIH,TANAKAH.Multi-objectivegeneticalgorithmanditsapplicationstoflowshopscheduling[J].Computers&IndustrialEngineering, 1996, 30(4):957-968.

[17] 杨巍巍, 宋海峰, 高巍巍,等. 基于遗传算法的自动组卷技术[J]. 黑龙江工程学院学报(自然科学版), 2013, 27(2):72-74.

[18]DAVIDSONR,MACKINNONJG.EconometricTheoryandMethods[M].OxfordUsaTrade, 2004.

[19]SHELDONMR.IntroductiontoProbabilityandStatisticsforEngineersandScientists[M].Elsevier, 2009.

[20]DAVIDE.AnIntroductiontoLogicalEntropyandItsRelationtoShannonEntropy[J].InternationalJournalofSemanticComputing, 2013, 07(02): 121-144.

[21]COVERTM,THOMASJA.ElementsofInformationTheory[M].JohnWiley&Sons,2012.

[责任编辑：郝丽英]

A new AP selection algorithm based on multi-objective optimization

ZHANG Wei1,2,HUA Xianghong1,2,QIU Weining1,2,WU Bang1,2,CHANG Xin1

(1. School of Geodesy & Geomatics, Wuhan University, Wuhan 430079,China; 2. Hazard Monitoring & Prevention Research Center, Wuhan 430079,China)

This paper explores a new access point (AP) selection algorithm based on multi-objective optimization for Wi-Fi indoor localization. A derivative process of multi-objective optimization function which involves both joint information gain (JIG) and mutual information (MI) is described in detail.The genetic algorithm (GA) is used to find the optimal solution. Experiments are conducted under different environments and the localization results suggest that the best weights of joint information gain and mutual information are 0.3 and 0.7 respectively in the complex environment while in the stable environment the best weights of joint information gain and mutual information are 0.7 and 0.3. And the results also show a linear relationship between the variance of error values of different AP numbers and the average value.

multi objective optimization; AP selection; joint information gain; mutual information; genetic algorithm

10.19352/j.cnki.issn1671-4679.2016.04.001

2016-03-29

国家自然科学基金资助项目(41374011)；江西省数字国土重点实验室开放研究基金资助项目(DLLJ201605)

张伟(1989-)，男，博士研究生，研究方向：多传感器室内外无缝定位； 数据处理.

P2

A

1671-4679(2016)04-0001-06