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

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

?

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

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

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

討論基于RSS的Wi-Fi室內(nèi)定位中基于多目標(biāo)優(yōu)化的AP選取問(wèn)題。綜合考慮信息增益(JIG)和互信息(MI)的多目標(biāo)優(yōu)化函數(shù)的推導(dǎo)過(guò)程，同時(shí)利用基因算法(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，同時(shí)位置估計(jì)結(jié)果分析表明：不同AP個(gè)數(shù)下的位置誤差的方差和平均值之間存在明顯的線(xiàn)性相關(guān)性。

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

由于GPS在室內(nèi)不能很好地工作[1-2]，近年來(lái)，國(guó)內(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ú)線(xiàn)局域網(wǎng)基礎(chǔ)設(shè)施，是一種多功能、低成本的定位技術(shù)[5]。Wi-Fi定位存在基于指紋和基于模型的兩種定位方法，基于指紋的定位與線(xiàn)下階段建立的指紋庫(kù)進(jìn)行匹配定位，基于模型的定位方法構(gòu)建接收信號(hào)強(qiáng)度(RSS)和距離之間的關(guān)系[6]。由于多徑的影響[7]，基于指紋的Wi-Fi室內(nèi)定位精度較低，如何選取觀測(cè)質(zhì)量較好的無(wú)線(xiàn)訪(fǎng)問(wèn)接入點(diǎn)(AP)對(duì)于Wi-Fi室內(nèi)定位至關(guān)重要[8]。

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

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

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

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

(1)

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

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

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

(2)

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

(3)

信息增益的單位化公式

(4)

1.2互信息計(jì)算

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

(5)

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

(6)

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

(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)良個(gè)體)

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

Mutation (子代種群變異)

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

}

Decode(解碼)

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

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

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

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

算公式為

(8)

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

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

圖2　編碼變異示意圖

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

(9)

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

(10)

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

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

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

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

1.4位置估計(jì)及精度分析

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

(11)

(12)

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

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

(13)

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

(14)

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

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

為了分析基于多目標(biāo)優(yōu)化的AP選取策略對(duì)Wi-Fi位置估計(jì)的精度影響，本文在兩個(gè)不同的環(huán)境下進(jìn)行了兩組實(shí)驗(yàn)。實(shí)驗(yàn)1在11 m×7 m大小的辦公室進(jìn)行，該房間存在多個(gè)AP且實(shí)驗(yàn)時(shí)段存在人員任意走動(dòng)的情況。實(shí)驗(yàn)2在11 m×10 m大小的會(huì)議室進(jìn)行，該房間內(nèi)部不存在AP且實(shí)驗(yàn)在沒(méi)有人員走動(dòng)的情況下進(jìn)行。兩種不同環(huán)境下的實(shí)驗(yàn)點(diǎn)位分布相同，分別采集6個(gè)指紋點(diǎn)和9個(gè)定位點(diǎn)的Wi-Fi接收信號(hào)強(qiáng)度數(shù)據(jù)，數(shù)據(jù)點(diǎn)之間的間隔為2 m。實(shí)驗(yàn)信號(hào)接收器采用小米手機(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)重配比方案時(shí)的AP選取策略對(duì)位置估計(jì)精度的影響，本文分別計(jì)算了11種不同權(quán)重方案時(shí)的位置估計(jì)精度，用于分析位置估計(jì)精度的變化。不同權(quán)重方案見(jiàn)表1。

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

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

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

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

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

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

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

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

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

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

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

3　結(jié)束語(yǔ)

本文提出了一種新的基于GA的多目標(biāo)優(yōu)化的AP選取算法，制定了基于聯(lián)合信息增益和簡(jiǎn)化互信息的多目標(biāo)優(yōu)化AP選取的完整步驟，為多目標(biāo)優(yōu)化的AP選取提供了參考。同時(shí)，通過(guò)分析位置估計(jì)精度與不同權(quán)重配比方案以及不同AP子集個(gè)數(shù)設(shè)置發(fā)現(xiàn)：在指定AP個(gè)數(shù)的情況下，位置估計(jì)精度與權(quán)重方案沒(méi)有明顯的關(guān)系，隨著聯(lián)合信息增益權(quán)重的增加以及互信息權(quán)重的減少，位置估計(jì)精度呈現(xiàn)波動(dòng)的特性。然而在指定的權(quán)重方案下，通過(guò)求取不同AP子集個(gè)數(shù)位置估計(jì)精度的平均值和方差發(fā)現(xiàn)，位置估計(jì)精度的平均值與方差呈現(xiàn)明顯的線(xiàn)性相關(guān)性，即方差越小，位置估計(jì)精度的平均值越小，位置估計(jì)的精度越好。因此，可以在不同權(quán)重配比情況下，通過(guò)設(shè)置不同的AP子集個(gè)數(shù)，計(jì)算該環(huán)境下位置估計(jì)精度的方差，選取方差最小的權(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屆中國(guó)控制與決策會(huì)議論文集. 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] 楊巍巍, 宋海峰, 高巍巍,等. 基于遺傳算法的自動(dòng)組卷技術(shù)[J]. 黑龍江工程學(xué)院學(xué)報(bào)(自然科學(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

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

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

P2

A

1671-4679(2016)04-0001-06