基于多目標(biāo)優(yōu)化的AP選取新算法

張　偉,花向紅,邱衛(wèi)寧,吳　幫,暢　鑫

(1．武漢大學(xué) 測繪學(xué)院,湖北 武漢 430079；2.武漢大學(xué) 災(zāi)害監(jiān)測與防治研究中心，湖北 武漢 430079)

?

基于多目標(biāo)優(yōu)化的AP選取新算法

張偉1,2,花向紅1,2,邱衛(wèi)寧1,2,吳幫1,2,暢鑫1

(1．武漢大學(xué) 測繪學(xué)院,湖北 武漢 430079；2.武漢大學(xué) 災(zāi)害監(jiān)測與防治研究中心，湖北 武漢 430079)

討論基于RSS的Wi-Fi室內(nèi)定位中基于多目標(biāo)優(yōu)化的AP選取問題。綜合考慮信息增益(JIG)和互信息(MI)的多目標(biāo)優(yōu)化函數(shù)的推導(dǎo)過程，同時利用基因算法(GA)尋求多目標(biāo)函數(shù)的最優(yōu)解。兩種差異明顯的環(huán)境下的實(shí)驗(yàn)結(jié)果表明：復(fù)雜環(huán)境中信息增益和互信息最佳權(quán)重分別為0.3和0.7，穩(wěn)定環(huán)境中互信息的最佳權(quán)重分別為0.7和0.3，同時位置估計結(jié)果分析表明：不同AP個數(shù)下的位置誤差的方差和平均值之間存在明顯的線性相關(guān)性。

多目標(biāo)優(yōu)化；AP選取；信息增益；互信息；GA算法

由于GPS在室內(nèi)不能很好地工作[1-2]，近年來，國內(nèi)外學(xué)者進(jìn)行了大量的室內(nèi)定位和室內(nèi)導(dǎo)航的研究，尤其是基于IEEE802.11 或 802.15標(biāo)準(zhǔn)的Wi-Fi定位追蹤系統(tǒng)[3-4]。Wi-Fi室內(nèi)定位系統(tǒng)利用現(xiàn)有的無線局域網(wǎng)基礎(chǔ)設(shè)施，是一種多功能、低成本的定位技術(shù)[5]。Wi-Fi定位存在基于指紋和基于模型的兩種定位方法，基于指紋的定位與線下階段建立的指紋庫進(jìn)行匹配定位，基于模型的定位方法構(gòu)建接收信號強(qiáng)度(RSS)和距離之間的關(guān)系[6]。由于多徑的影響[7]，基于指紋的Wi-Fi室內(nèi)定位精度較低，如何選取觀測質(zhì)量較好的無線訪問接入點(diǎn)(AP)對于Wi-Fi室內(nèi)定位至關(guān)重要[8]。

由于Wi-Fi網(wǎng)絡(luò)的廣泛部署，在一個單一的位置觀察10～20的AP且在一個單一的建筑觀測到50多個AP是很常見的[9]。AP選擇的目的是從所有可用的AP中選擇一個子集，從而減少計算量和提高定位的精度。文獻(xiàn)[8]中提出了一種基于位置信息增益的AP選取方法，但是該方法沒有考慮AP之間的相關(guān)性。文獻(xiàn)[10]進(jìn)一步提出了利用聯(lián)合信息增益改進(jìn)的AP選取方法，從而考慮不同AP集合的判別能力的相關(guān)性。Han Zou等[11]提出了基于互信息的線上AP選取策略，從而提取最有價值的特征成分并減小冗余?；バ畔⑹请S機(jī)變量獨(dú)立性的自然信息理論測度，因此，較小的互信息表示較小的相關(guān)性[12]?；诼?lián)合信息增益的AP選取策略和基于互信息的AP選取策略都是重要的信息熵指標(biāo)，兩種方法都有各自的優(yōu)勢且他們的定位結(jié)果受環(huán)境變化的影響較大。一般而言，由于無法考慮RSS測量的綜合信息，基于單目標(biāo)優(yōu)化的AP選擇方法往往對Wi-Fi室內(nèi)定位系統(tǒng)產(chǎn)生不利影響。

本文提出了一種新的基于多目標(biāo)優(yōu)化的AP選擇方法用于Wi-Fi室內(nèi)定位，同時考慮AP子集的判別能力、AP子集的相關(guān)性以及冗余。多目標(biāo)優(yōu)化通常用一個固定的權(quán)重將不同的目標(biāo)聚合成一個目標(biāo)函數(shù)[13-14]。本文推導(dǎo)了一個新的目標(biāo)函數(shù)實(shí)現(xiàn)，同時使得AP子集的聯(lián)合信息增益最大且互信息最小。基因算法被用來計算多目標(biāo)優(yōu)化問題的最優(yōu)標(biāo)量適應(yīng)值[15-17]。利用多目標(biāo)優(yōu)化選取AP子集后，用 WKNN方法進(jìn)行位置估計。在不同的環(huán)境下進(jìn)行實(shí)驗(yàn)并對實(shí)驗(yàn)中的線性回歸模型的顯著性進(jìn)行假設(shè)檢驗(yàn)。利用F檢驗(yàn)對回歸方程整體顯著性進(jìn)行檢驗(yàn)，同時，t檢驗(yàn)被用于回歸參數(shù)顯著性的檢驗(yàn)[18-19]。結(jié)果表明：聯(lián)合信息的增益和相互信息最佳的權(quán)重與環(huán)境有關(guān)，且不同AP個數(shù)下的位置精度的標(biāo)準(zhǔn)方差和平均值之間存在線性相關(guān)性。

1　基于多目標(biāo)優(yōu)化的AP選擇策略

考慮基于聯(lián)合信息增益和互信息的兩種AP選取策略各自不同的優(yōu)勢，本文利用加權(quán)求和的方法提出一個新的多目標(biāo)優(yōu)化函數(shù)，實(shí)現(xiàn)兩種信息量融合的AP選?。?/p>

(1)

式中：fitness表示多目標(biāo)優(yōu)化函數(shù)的適應(yīng)度，即目標(biāo)函數(shù)，fitness越小對應(yīng)的AP組合觀測質(zhì)量越好，wIG和wMI分別表示聯(lián)合信息增益和簡化互信息對應(yīng)的權(quán)重，且滿足wIG≥0,wMI≥0,wIG+wMI=1，IGSta和MISta分別表示標(biāo)準(zhǔn)化后的聯(lián)合信息增益和互信息。

1.1聯(lián)合信息增益計算

基于RSS的Wi-Fi指紋定位AP子集對于位置區(qū)分度的貢獻(xiàn)可以采用信息增益的大小表示，考慮N個AP之間的相關(guān)性的聯(lián)合信息增益計算公式

(2)

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

(3)

信息增益的單位化公式

(4)

1.2互信息計算

AP子集選取除了需要考慮信息增益量化指標(biāo)外，互信息也是衡量AP集合質(zhì)量好壞的一個指標(biāo)，下面給出簡化互信息計算公式

(5)

對于N個AP中的任意NSub個AP組合，滿足MI(AP1,AP2,…,APNsub)=min的AP組合即最優(yōu)的AP組合?？紤]信息熵滿足不等式以及信息熵的定義[20]，有

(6)

式中：Nmax表示N個AP中，觀測值不同取值個數(shù)最大的AP對應(yīng)的觀測值不同取值個數(shù)。則有簡化互信息單位化公式

(7)

1.3多目標(biāo)優(yōu)化函數(shù)解算

GA(基因算法)是一種受自然界優(yōu)勝劣汰的生物進(jìn)化論啟發(fā)而提出的目標(biāo)搜索算法?；贕A的AP選取算法的偽代碼如下:

Initialize (產(chǎn)生父代種群)

While (迭代收斂)

{

Selection (選取父代種群的優(yōu)良個體)

Reproduction (產(chǎn)生子代種群)

Mutation (子代種群變異)

Evaluate (子代群體擇優(yōu)產(chǎn)生新的父代種群)

}

Decode(解碼)

第一步：在Initialize階段，將問題解決方案表示為二進(jìn)制編碼。對于N個AP的優(yōu)化子集選取問題，二進(jìn)制編碼組合的長度為N，即種群中個體的染色體序列長度為N，且每個染色體對應(yīng)于一個AP。當(dāng)染色體編碼為1時表示其對應(yīng)的AP作為最優(yōu)AP，編碼為0時則表示對應(yīng)的AP并非最優(yōu)的AP。個體隨機(jī)編碼示意圖如圖1所示。

圖1　個體隨機(jī)編碼(與AP一一對應(yīng))

為了通過GA算法搜索最優(yōu)目標(biāo)個體，需要在Initialize階段產(chǎn)生一定數(shù)量的個體，即產(chǎn)生種群。

第2步：按照式(1)計算種群中所有個體的適應(yīng)值(即目標(biāo)函數(shù)值)。獲取所有個體的適應(yīng)度后，按照輪盤賭法選取NS個優(yōu)良個體。個體選中的概率采用與適應(yīng)度成反比的加權(quán)法，每個個體的權(quán)重計

算公式為

(8)

式中：wi表示第i個個體選中的概率，fitnessi表示第i個個體的適應(yīng)度，NP表示父代群體的個體數(shù)。

第3步：利用變異算子對選取的子代個體進(jìn)行變異操作。由于最優(yōu)AP子集的個數(shù)設(shè)置為NSub，因此，變異算子需要交換個體的兩個染色體編碼完成個體變異操作。個體的染色體編碼交換示意圖如圖2所示。

圖2　編碼變異示意圖

變異算子在變異前需要計算是否產(chǎn)生變異的概率，個體的染色體變異的概率與當(dāng)前位置染色體編碼有關(guān)。假定當(dāng)前位置染色體的編碼為1，則計算NS個優(yōu)良個體中當(dāng)前位置編碼為1的個數(shù)N1；若當(dāng)前位置染色體的編碼為0，則計算NS個優(yōu)良個體中當(dāng)前位置編碼為0的個數(shù)N0。該位置編碼變異的概率計算公式為

(9)

式中：wi(1≤i≤N)表示個體當(dāng)前位置染色體的變異概率。為了避免某個染色體的變異概率為0而弱化新群體的多樣性，式中分母、分子同時加1使得其變異概率永遠(yuǎn)大于0。則個體的變異操作發(fā)生的概率計算公式為

(10)

式中：wm表示染色體交換算子的概率，即個體的第i個染色體和第j個染色體編碼互換的概率，wi，wj分別表示其變異概率。

第4步：計算變異后新產(chǎn)生個體的適應(yīng)值，與父代群體進(jìn)行比較，按照個體適應(yīng)度的大小選取適應(yīng)度最小的N個個體作為新的父代群體，完成種群進(jìn)化，記錄當(dāng)前種群的最小適應(yīng)值。

第5步：循環(huán)執(zhí)行步驟2～4，直到滿足迭代終止條件，即群體的最小適應(yīng)度不再變化為止。

第6步：對具有最小適應(yīng)度的個體進(jìn)行解碼，找出其編碼為1的染色體對應(yīng)的AP，從而獲取最終需要的最優(yōu)AP子集。

1.4位置估計及精度分析

利用GA算法找出最優(yōu)AP子集后，利用典型的WKNN算法進(jìn)行位置估計。位置估計的誤差計算公式為

(11)

(12)

式中：σ表示位置估計的精度，NT表示所有定位點(diǎn)的個數(shù)，di表示第i個點(diǎn)位置估計的誤差。

由于不同AP子集個數(shù)會對位置估計的精度產(chǎn)生影響，為了分析多目標(biāo)優(yōu)化函數(shù)中聯(lián)合信息增益和互信息的最佳權(quán)重方案，在每個權(quán)重方案下分別計算多種不同AP子集個數(shù)情況下的位置估計精度，同時按照式(13)計算其精度的平均值和方差。

(13)

式中：σk表示AP子集個數(shù)為k時的位置估計精度(文中考慮了k取4～10的7種情況)，Ave表示設(shè)置不同AP子集個數(shù)時位置估計精度的均值，Var表示其對應(yīng)的方差。一次線性回歸模型被用來分析精度均值和方差之間關(guān)系，其擬合模型為

(14)

式中：β0為回歸方程常數(shù)項(xiàng)，β1為回歸方差一次性系數(shù)。

2　實(shí)驗(yàn)分析

為了分析基于多目標(biāo)優(yōu)化的AP選取策略對Wi-Fi位置估計的精度影響，本文在兩個不同的環(huán)境下進(jìn)行了兩組實(shí)驗(yàn)。實(shí)驗(yàn)1在11 m×7 m大小的辦公室進(jìn)行，該房間存在多個AP且實(shí)驗(yàn)時段存在人員任意走動的情況。實(shí)驗(yàn)2在11 m×10 m大小的會議室進(jìn)行，該房間內(nèi)部不存在AP且實(shí)驗(yàn)在沒有人員走動的情況下進(jìn)行。兩種不同環(huán)境下的實(shí)驗(yàn)點(diǎn)位分布相同，分別采集6個指紋點(diǎn)和9個定位點(diǎn)的Wi-Fi接收信號強(qiáng)度數(shù)據(jù)，數(shù)據(jù)點(diǎn)之間的間隔為2 m。實(shí)驗(yàn)信號接收器采用小米手機(jī)，并采用全站儀獲取校準(zhǔn)點(diǎn)的點(diǎn)位坐標(biāo)。實(shí)驗(yàn)不考慮AP分布的影響，采用實(shí)際環(huán)境中可用的AP進(jìn)行實(shí)驗(yàn)分析。建立兩種不同環(huán)境的實(shí)驗(yàn)方案分布如圖3所示。

圖3　實(shí)驗(yàn)方案分布

圖3中，‘●’表示指紋點(diǎn)，‘▇’表示定位點(diǎn)。為了分析不同權(quán)重配比方案時的AP選取策略對位置估計精度的影響，本文分別計算了11種不同權(quán)重方案時的位置估計精度，用于分析位置估計精度的變化。不同權(quán)重方案見表1。

考慮到AP子集個數(shù)對位置估計的影響，本文同時分析了AP子集個數(shù),分別設(shè)置為4～10的多種情況，即4≤NSub≤10。圖4和圖5分別給出兩種不同環(huán)境下設(shè)置不同AP子集個數(shù)時，定位精度隨著權(quán)重配比方案的變化曲線。

表1　不同的權(quán)重配比方案

圖4　實(shí)驗(yàn)場景1下定位精度變化曲線

圖5　實(shí)驗(yàn)場景2下定位精度變化曲線

從圖4和圖5可以看出，在指定AP子集個數(shù)的情況下，位置估計的精度隨著權(quán)重方案的改變沒有明顯的關(guān)系。由于信息增益和互信息均是信息熵的一種度量指標(biāo)，因此，在指定AP個數(shù)的情況下，位置估計精度隨著權(quán)重方案(信息增益權(quán)重逐漸增大、互信息權(quán)重逐步減小)變化呈現(xiàn)一種波動趨勢，二者權(quán)重調(diào)整的優(yōu)劣無法通過位置估計精度衡量。然而，通過觀察指定權(quán)重方案下精度隨著AP子集個數(shù)的變化可以看出：場景1采取D權(quán)重方案(信息增益權(quán)重0.3，互信息權(quán)重0.7)時，精度隨著不同AP個數(shù)變化的波動最小，即位置估計精度隨著最優(yōu)子集個數(shù)變化產(chǎn)生的差異最小，而場景2采取H方案時精度隨著不同AP個數(shù)變化的波動最小。表2給出了不同精度權(quán)重方案下，AP個數(shù)分別取4～10時位置估計精度的平均值和方差。

表2　不同權(quán)重方案下4～10個AP的位置

從表2可以看出,場景1中選取D權(quán)重方案時，AP個數(shù)取4～10的位置估計精度變化的方差最小，且其平均值優(yōu)于除H方案之外的任意其他方案；場景2中選取H權(quán)重方案時，AP個數(shù)取4～10

的位置估計變化的方差最小，然而，其E方案的位置估計精度平均值最小，為了進(jìn)一步分析位置估計精度平均值與方差的關(guān)系，圖6給出了精度平均值隨方差變化的曲線。

圖6　方差與精度均值散點(diǎn)圖

圖6分別顯示了場景1中方差與精度均值的離散點(diǎn)示意圖和場景2中方差與精度均值的離散點(diǎn)示意圖，圖中直線為基于最小二乘的一次線性回歸結(jié)果。從圖中可以看出，精度均值與方差存在一定的正線性相關(guān)關(guān)系，即方差越小，精度均值越小，位置估計精度整體性越好。表3給出了一次線性回歸系數(shù)及其顯著性檢驗(yàn)。

表3　回歸系數(shù)及其顯著性檢驗(yàn)

3　結(jié)束語

本文提出了一種新的基于GA的多目標(biāo)優(yōu)化的AP選取算法，制定了基于聯(lián)合信息增益和簡化互信息的多目標(biāo)優(yōu)化AP選取的完整步驟，為多目標(biāo)優(yōu)化的AP選取提供了參考。同時，通過分析位置估計精度與不同權(quán)重配比方案以及不同AP子集個數(shù)設(shè)置發(fā)現(xiàn)：在指定AP個數(shù)的情況下，位置估計精度與權(quán)重方案沒有明顯的關(guān)系，隨著聯(lián)合信息增益權(quán)重的增加以及互信息權(quán)重的減少，位置估計精度呈現(xiàn)波動的特性。然而在指定的權(quán)重方案下，通過求取不同AP子集個數(shù)位置估計精度的平均值和方差發(fā)現(xiàn)，位置估計精度的平均值與方差呈現(xiàn)明顯的線性相關(guān)性，即方差越小，位置估計精度的平均值越小，位置估計的精度越好。因此，可以在不同權(quán)重配比情況下，通過設(shè)置不同的AP子集個數(shù)，計算該環(huán)境下位置估計精度的方差，選取方差最小的權(quán)重方案作為該環(huán)境下的最優(yōu)權(quán)重方案。

[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] 楊巍巍, 宋海峰, 高巍巍,等. 基于遺傳算法的自動組卷技術(shù)[J]. 黑龍江工程學(xué)院學(xué)報(自然科學(xué)版), 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.

[責(zé)任編輯：郝麗英]

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

國家自然科學(xué)基金資助項(xiàng)目(41374011)；江西省數(shù)字國土重點(diǎn)實(shí)驗(yàn)室開放研究基金資助項(xiàng)目(DLLJ201605)

張偉(1989-)，男，博士研究生，研究方向：多傳感器室內(nèi)外無縫定位； 數(shù)據(jù)處理.

P2

A

1671-4679(2016)04-0001-06