虛擬AP支持的室內(nèi)非線(xiàn)性約束區(qū)域定位

薛衛(wèi)星，李清泉，周寶定

1. 深圳大學(xué)廣東省城市空間信息工程重點(diǎn)實(shí)驗(yàn)室，廣東 深圳 518060； 2. 深圳大學(xué)土木與交通工程學(xué)院，廣東 深圳 518060

位置信息服務(wù)[1]已經(jīng)成為人們?nèi)粘Ｉ畹幕A(chǔ)需求。室外環(huán)境中，全球?qū)Ш叫l(wèi)星系統(tǒng)(Global Navigation Satellite System，GNSS)為精確的位置服務(wù)提供了保障[2-6]。而當(dāng)進(jìn)入室內(nèi)環(huán)境時(shí)，信號(hào)視距傳播難以實(shí)現(xiàn)，基于GNSS的室內(nèi)位置服務(wù)變得十分困難。相關(guān)研究表明，人們?nèi)粘Ｉ罟ぷ鞯?0%以上是在室內(nèi)[7-9]進(jìn)行的，通過(guò)智能手機(jī)進(jìn)行導(dǎo)航定位[10-11]已經(jīng)逐漸成為人們不可或缺的生活方式。對(duì)于具有線(xiàn)性約束的室內(nèi)狹窄區(qū)域，如室內(nèi)走廊或狹窄通道，行人移動(dòng)方向受到墻體等障礙物約束，只能沿著走廊或通道方向移動(dòng)而不能橫向穿越，使用行為地標(biāo)和地圖輔助的方法[12-17]，定位精度可以得到明顯提高。但在開(kāi)闊的室內(nèi)非線(xiàn)性約束區(qū)域，如辦公室或商鋪，行人移動(dòng)方向不受約束，可以向任何平面方向移動(dòng)，慣性的累積誤差無(wú)法根據(jù)約束進(jìn)行修正，從而嚴(yán)重影響定位精度，很難使用行為地標(biāo)和地圖輔助的方法進(jìn)行定位。由于無(wú)線(xiàn)信號(hào)的非視距傳播和多路徑傳播，基于到達(dá)時(shí)間、到達(dá)時(shí)間差和到達(dá)角度的室內(nèi)定位技術(shù)同樣也遇到了巨大的挑戰(zhàn)。而隨著智慧城市[18]的建設(shè)，Wi-Fi網(wǎng)絡(luò)快速普及，為基于Wi-Fi的室內(nèi)定位[19-26]創(chuàng)造了有利條件。

對(duì)于非線(xiàn)性約束的室內(nèi)區(qū)域，如何有效提高定位的精度，是技術(shù)研究的重點(diǎn)，也是實(shí)際應(yīng)用的基礎(chǔ)。具體而言，如何對(duì)位置指紋數(shù)據(jù)庫(kù)進(jìn)行聚類(lèi)分隔，以更合理地反映出指紋點(diǎn)之間的空間幾何關(guān)系；如何篩選出高質(zhì)量AP，以顯著減少在線(xiàn)定位的計(jì)算量并提高定位的精度。

指紋點(diǎn)聚類(lèi)算法方面。為了減少在線(xiàn)階段的搜索范圍，文獻(xiàn)[27—30]提出了基于指紋點(diǎn)聚類(lèi)的Wi-Fi定位方法。但是，傳統(tǒng)的指紋點(diǎn)聚類(lèi)算法只在離線(xiàn)階段對(duì)指紋點(diǎn)(reference points，RP)的幾何鄰近性進(jìn)行分析；而且聚類(lèi)的個(gè)數(shù)需要直接或間接地預(yù)先定義，用戶(hù)需要仔細(xì)地調(diào)整參數(shù)以選擇合適的聚類(lèi)的個(gè)數(shù)，而不合適的聚類(lèi)個(gè)數(shù)將會(huì)導(dǎo)致定位結(jié)果的估計(jì)誤差。基于指紋點(diǎn)位置的聚類(lèi)(reference points location clustered，RPLC)算法[28]，只在離線(xiàn)階段對(duì)指紋點(diǎn)的幾何鄰近性進(jìn)行聚類(lèi)分析，聚類(lèi)結(jié)果與在線(xiàn)階段的測(cè)試點(diǎn)無(wú)關(guān)。而基于信號(hào)距離的聚類(lèi)(signal distance clustered，SDC)算法[29]，僅根據(jù)Wi-Fi接收信號(hào)強(qiáng)度(received signal strength indication，RSSI)在信號(hào)空間的歐氏距離進(jìn)行指紋點(diǎn)聚類(lèi)，不考慮指紋點(diǎn)和測(cè)試點(diǎn)之間的幾何距離。文獻(xiàn)[30]利用K均值(K-means)聚類(lèi)算法[30]提高了K鄰近(K nearest neighbor，KNN)算法的性能，但仍然根據(jù)RSSI信號(hào)空間的距離進(jìn)行近鄰指紋點(diǎn)的選取。然而，RSSI在室內(nèi)空間傳播時(shí)，會(huì)存在RSSI信號(hào)空間的距離近而幾何距離遠(yuǎn)的問(wèn)題，所以，基于RSSI信號(hào)空間距離聚類(lèi)的方法也可能存在錯(cuò)誤選取鄰近指紋點(diǎn)的問(wèn)題。

AP選取算法方面。基于最大均值的AP選取算法[21]選取RSSI平均值最大的AP。但是，RSSI平均值只能在一定程度上反映該AP理論上的信號(hào)質(zhì)量；RSSI平均值大的AP，也可能信號(hào)強(qiáng)度起伏較大而導(dǎo)致定位效果不佳。基于位置信息增益(information gain，InfoGain)的AP選取算法[31]選擇最具位置辨別力的AP。基于在線(xiàn)互信息(online MI)的AP選取算法[32]采用在線(xiàn)互信息來(lái)度量AP之間的集體辨別能力。但是，AP位置識(shí)別能力高并不一定代表該AP的RSSI質(zhì)量高；RSSI質(zhì)量差的AP，由于信號(hào)微弱而更不穩(wěn)定，可能會(huì)導(dǎo)致更多的位置差異。基于主成分分析(principal component analysis，PCA)的AP選取算法[24]采用主成分分析法的方法進(jìn)行AP選取。但是，在Wi-Fi RSSI非視距傳播和多徑干擾嚴(yán)重的室內(nèi)場(chǎng)景中，RSSI信號(hào)很可能無(wú)法形成主成分。近年來(lái)，一些新的AP選擇算法被提出[33-36]。基于誤差分析的AP選擇算法[33]通過(guò)對(duì)用戶(hù)定位結(jié)果的誤差分析選擇AP子集用于定位。基于RSSI區(qū)間重疊度(interval overlap degree，IOD)的AP選擇算法[34]通過(guò)對(duì)指紋點(diǎn)的幾何位置分析來(lái)選取AP。基于無(wú)須標(biāo)定(AP selection based calibration-free，ASCF)的AP選擇算法[35]選擇RSSI差異較大的AP來(lái)構(gòu)建指紋數(shù)據(jù)庫(kù)。基于主梯度方向的算法[36]估計(jì)了每個(gè)AP的主梯度衰減方向。但是，無(wú)線(xiàn)信號(hào)經(jīng)過(guò)反射、折射或衍射后，AP的傳播方向會(huì)發(fā)生改變。因此，同一個(gè)AP在不同區(qū)域的衰減方向是不同的。

針對(duì)以上問(wèn)題，本文提出了虛擬AP支持的室內(nèi)非線(xiàn)性約束區(qū)域的定位方法。

1 虛擬AP定位

一般說(shuō)來(lái)，傳播模型法需要以不同定位場(chǎng)景的路徑衰減因子為基礎(chǔ)，而位置指紋法則不考慮路徑衰減因子。本文提出的虛擬AP定位，是位置指紋法和傳播模型法的綜合。虛擬AP定位，首先，需要解決不同定位場(chǎng)景中路徑衰減因子簡(jiǎn)化的問(wèn)題；然后，借鑒光反射、折射或衍射后形成虛擬光源，計(jì)算定位小區(qū)域AP的虛擬坐標(biāo)；以Wi-Fi信號(hào)到達(dá)定位小區(qū)域視距傳播前最后一次反射、折射或衍射的地方為起點(diǎn)，計(jì)算定位小區(qū)域AP的衰減方向；以定位小區(qū)域AP的視距傳播為依據(jù)，采用RSSI計(jì)算指紋點(diǎn)和定位點(diǎn)到虛擬AP的幾何距離。

1.1 不同定位場(chǎng)景中路徑衰減因子的簡(jiǎn)化

對(duì)于傳播模型法，為了確定具體定位場(chǎng)景中的路徑衰減因子，需要大量的數(shù)據(jù)采集和處理；而且，某一定位場(chǎng)景中訓(xùn)練得到的路徑衰減因子又很難應(yīng)用到另一個(gè)類(lèi)似的定位場(chǎng)景中。以定位點(diǎn)為中心的定位小區(qū)域的室內(nèi)空間是在同一介質(zhì)(即空氣里，既不在墻里，也不在窗戶(hù)里)的范圍內(nèi)，因此，本文首先對(duì)室內(nèi)區(qū)域進(jìn)行劃分，當(dāng)將室內(nèi)區(qū)域劃分為較小的區(qū)域后，定位空間中便只有一種傳播介質(zhì)，在該區(qū)域內(nèi)就可以使用同一個(gè)路徑衰減因子。

1.2 定位小區(qū)域AP的虛擬坐標(biāo)和衰減方向

根據(jù)光的直線(xiàn)傳播的定律，在同一種均勻的介質(zhì)中光線(xiàn)是沿直線(xiàn)方式傳播的。而當(dāng)光線(xiàn)由一種介質(zhì)傳播到另一種介質(zhì)時(shí)，會(huì)發(fā)生光線(xiàn)的反射和折射；當(dāng)光線(xiàn)在傳播過(guò)程中遇到障礙物時(shí)，它的傳播方式將從該障礙物的縫隙或邊界偏離直線(xiàn)傳播，形成衍射。光的反射、折射和衍射具有一個(gè)共同特點(diǎn)：根據(jù)光線(xiàn)的直線(xiàn)傳播定律推算出來(lái)的光源不是真實(shí)的光源，而是虛擬光源。

同樣，無(wú)線(xiàn)信號(hào)在室內(nèi)環(huán)境中傳播，一般會(huì)經(jīng)過(guò)反射、折射或衍射，然后到達(dá)定位小區(qū)域。而Wi-Fi信號(hào)在定位小區(qū)域信號(hào)視距傳播的起始點(diǎn)，則是其最后一次反射、折射或衍射的地方(也可能是AP的實(shí)際位置)。這里，主要研究Wi-Fi信號(hào)經(jīng)過(guò)最后一次反射、折射或衍射后，在定位小區(qū)域的傳播情況。根據(jù)定位小區(qū)域Wi-Fi信號(hào)的視距傳播情況，按照無(wú)線(xiàn)信號(hào)衰減公式和簡(jiǎn)化后的路徑衰減因子推算AP的“虛擬位置”，稱(chēng)為定位小區(qū)域AP的虛擬坐標(biāo)。根據(jù)定位小區(qū)域Wi-Fi信號(hào)的視距傳播情況，按照定位小區(qū)域臨近指紋點(diǎn)的聚類(lèi)結(jié)果推算AP的衰減方向，稱(chēng)為定位小區(qū)域AP的衰減方向。接下來(lái)，就可以根據(jù)定位小區(qū)域AP的虛擬坐標(biāo)進(jìn)行指紋點(diǎn)的聚類(lèi)，根據(jù)定位小區(qū)域AP的衰減方向進(jìn)行AP的選取。虛擬AP支持的室內(nèi)非線(xiàn)性約束區(qū)域定位流程如圖1所示。

圖1 虛擬AP支持的室內(nèi)非線(xiàn)性約束區(qū)域定位流程Fig.1 Flowchart of the virtual AP based positioning method

2 基于虛擬AP坐標(biāo)的指紋點(diǎn)聚類(lèi)

基于AP虛擬坐標(biāo)的指紋點(diǎn)聚類(lèi)算法主要針對(duì)無(wú)線(xiàn)性約束區(qū)域的室內(nèi)定位，該算法不需要預(yù)先設(shè)置聚類(lèi)個(gè)數(shù)，不僅能實(shí)現(xiàn)聚類(lèi)過(guò)程自動(dòng)化，而且能保證離線(xiàn)階段聚類(lèi)方法與在線(xiàn)階段定位方法的一致性。算法主要包括基于KNN算法的指紋庫(kù)自檢，定位小區(qū)域AP虛擬坐標(biāo)的計(jì)算和基于AP虛擬坐標(biāo)的指紋點(diǎn)聚類(lèi)3部分。基于KNN算法的指紋庫(kù)自檢是為了獲取該房間或大廳內(nèi)定位誤差最小時(shí)對(duì)應(yīng)的K值。定位小區(qū)域AP虛擬坐標(biāo)的計(jì)算是將簡(jiǎn)化后的路徑衰減因子代入到無(wú)線(xiàn)信號(hào)衰減公式中來(lái)推算每個(gè)指紋點(diǎn)對(duì)應(yīng)的AP的虛擬坐標(biāo)。當(dāng)路徑衰減因子變化時(shí)，AP虛擬坐標(biāo)總是以相同組群的方式同時(shí)變化；因此可以基于此組群分類(lèi)的方式對(duì)指紋點(diǎn)進(jìn)行聚類(lèi)。

2.1 基于KNN算法的指紋庫(kù)自檢

在同一個(gè)非線(xiàn)性約束的室內(nèi)區(qū)域，所有的指紋點(diǎn)依次作為測(cè)試點(diǎn)進(jìn)行定位測(cè)試，從身份編號(hào)(identity，ID)最小的指紋點(diǎn)開(kāi)始。所有的指紋點(diǎn)都分配了不同的ID號(hào)，并將指紋點(diǎn)ID編號(hào)與指紋點(diǎn)位置、AP名稱(chēng)和接收信號(hào)強(qiáng)度相關(guān)聯(lián)。需要說(shuō)明的是，指紋點(diǎn)ID編號(hào)的編號(hào)方式對(duì)算法的聚類(lèi)結(jié)果沒(méi)有影響，因?yàn)槊總€(gè)指紋點(diǎn)都將逐個(gè)獨(dú)立地被作為測(cè)試點(diǎn)進(jìn)行定位測(cè)試。此外，文獻(xiàn)[37]使用眾包的Wi-Fi RSSI數(shù)據(jù)來(lái)識(shí)別不同房間的指紋點(diǎn)從而實(shí)現(xiàn)了房間級(jí)的定位。這里，本文假設(shè)不同房間的指紋點(diǎn)已被成功識(shí)別，本節(jié)提出的聚類(lèi)算法將主要針對(duì)某一房間內(nèi)的指紋點(diǎn)的聚類(lèi)。當(dāng)某一指紋點(diǎn)被視為測(cè)試點(diǎn)時(shí)，而同一房間內(nèi)的其他指紋點(diǎn)仍然是指紋點(diǎn)。

首先，設(shè)置不同的K值，如K=3、K=4或K=5。對(duì)于某一K值，例如，當(dāng)K=3時(shí)，“測(cè)試點(diǎn)”的位置用KNN算法逐個(gè)估算。然后，得到相應(yīng)的定位誤差統(tǒng)計(jì)。對(duì)K的其他值，重復(fù)該過(guò)程。最后，以均方根誤差(root mean square error，RMSE)為指標(biāo)，選擇定位誤差最小的K值。

2.2 定位小區(qū)域AP虛擬坐標(biāo)的計(jì)算

以1號(hào)指紋點(diǎn)為例。當(dāng)RP1作為測(cè)試點(diǎn)時(shí)，同一房間內(nèi)的其余指紋點(diǎn)仍作為指紋點(diǎn)使用。根據(jù)2.1節(jié)中確定的K值，用KNN算法得到該測(cè)試點(diǎn)對(duì)應(yīng)的K個(gè)鄰近指紋點(diǎn)。根據(jù)無(wú)線(xiàn)信號(hào)衰減模型[38]，Wi-Fi RSSI衰減公式為

(1)

式中，RSSI(d0)和RSSI(di)分別是距離AP信號(hào)源d0和di處的接收信號(hào)強(qiáng)度；η是路徑衰減因子。d0和RSSI(d0)一般通過(guò)經(jīng)驗(yàn)建模預(yù)先設(shè)定，本文中d0取值1 m，RSSI(d0)取值為-20 dB。因此，未知幾何距離di可以通過(guò)RSSI(di)和η計(jì)算得到

(2)

同時(shí)，未知幾何距離di也可以通過(guò)AP信號(hào)源的坐標(biāo)和指紋點(diǎn)的坐標(biāo)計(jì)算得到

(3)

式中，(xj，yj)是第j個(gè)AP的虛擬位置(virtual position，VP)；(xi，yi)是第i個(gè)RP的位置坐標(biāo)。這里假設(shè)總共有M個(gè)AP和N個(gè)指紋點(diǎn)。把式(3)代入式(2)，然后把方程兩邊都平方。由于式(3)的右側(cè)只是距離的估計(jì)值，引入用φi(xj,yj)表示的坐標(biāo)殘差

(4)

將路徑衰減因子的數(shù)值設(shè)為固定值，簡(jiǎn)化無(wú)線(xiàn)信號(hào)衰減公式；使用這K個(gè)鄰近指紋點(diǎn)，結(jié)合線(xiàn)性最小二乘平差，計(jì)算AP的虛擬坐標(biāo)。對(duì)未知坐標(biāo)參數(shù)(xj，yj)分別求偏導(dǎo)，系數(shù)矩陣B的元素為

(5)

使用線(xiàn)性最小二乘平差，得到坐標(biāo)殘差平方和并將其最小化

(6)

測(cè)試完該室內(nèi)非線(xiàn)性約束區(qū)域內(nèi)所有N個(gè)指紋點(diǎn)后，每個(gè)AP可以得到N個(gè)虛擬坐標(biāo)，M個(gè)AP就有N×M個(gè)虛擬坐標(biāo)。在同一個(gè)房間內(nèi)，每個(gè)指紋點(diǎn)都可以接收房間內(nèi)所有AP的信號(hào)；如果一個(gè)AP的信號(hào)無(wú)法被所有指紋點(diǎn)都接收，則剔除AP。指紋點(diǎn)與所有AP虛擬位置的對(duì)應(yīng)關(guān)系見(jiàn)表1。

表1 指紋點(diǎn)與AP虛擬坐標(biāo)的對(duì)應(yīng)關(guān)系

2.3 基于AP虛擬坐標(biāo)的指紋點(diǎn)聚類(lèi)

圖2為101房間試驗(yàn)點(diǎn)分布示意。由圖2中第1列AP1開(kāi)始，計(jì)算虛擬坐標(biāo)VP11和與剩余N-1個(gè)虛擬坐標(biāo)VPi1之間的距離。如果N-1個(gè)距離中的任何一個(gè)小于預(yù)先定義的閾值，則選擇相應(yīng)的RP，所有選定的RP和RP1都形成一個(gè)RP聚類(lèi)。然后，在未聚類(lèi)的其余RP中，選擇ID號(hào)最小的RP(例如RPmid)，并計(jì)算VPmid1與剩余RP對(duì)應(yīng)的VPi1之間的距離。同樣，將距離小于閾值的VP相應(yīng)的RP與RPmid形成第2個(gè)聚類(lèi)。重復(fù)該過(guò)程，直到所有N個(gè)RP聚類(lèi)結(jié)束。該過(guò)程是自動(dòng)進(jìn)行的，聚類(lèi)的個(gè)數(shù)不需要預(yù)先設(shè)置。請(qǐng)注意，到目前為止，只完成了AP1對(duì)應(yīng)的第1列的指紋點(diǎn)的聚類(lèi)。繼續(xù)從AP2對(duì)應(yīng)的第2列開(kāi)始，重復(fù)上述聚類(lèi)過(guò)程。直到所有M列都聚類(lèi)完成為止。

圖2 101房間試驗(yàn)點(diǎn)分布示意Fig.2 Schematic diagram of test point distribution in room 101

在完成聚類(lèi)過(guò)程后，將在每個(gè)聚類(lèi)內(nèi)的所有指紋點(diǎn)的RSSI取平均值，形成一個(gè)單獨(dú)的RSSI，作為該聚類(lèi)的代表

(7)

3 基于八陣圖的AP選取

在室內(nèi)傳播的無(wú)線(xiàn)信號(hào)，經(jīng)過(guò)墻壁、門(mén)窗和室內(nèi)大型家具等障礙物后會(huì)發(fā)生反射、折射或衍射現(xiàn)象，其傳播方向會(huì)發(fā)生變化。而在測(cè)試點(diǎn)周?chē)男《ㄎ粎^(qū)域內(nèi)，AP信號(hào)可以認(rèn)為是視距傳播，其衰減方向可以通過(guò)該測(cè)試點(diǎn)鄰近指紋點(diǎn)的RSSI信號(hào)聚類(lèi)來(lái)計(jì)算。這樣，同一個(gè)AP在房間內(nèi)不同測(cè)試點(diǎn)的AP衰減方向就可能不同，因此，不同測(cè)試點(diǎn)的AP子集的選取情況也可能不同，這就是本文方法與傳統(tǒng)AP選取算法的主要區(qū)別。

八陣圖由均勻間隔45°的8個(gè)基本方向組成。定位誤差可分解為X軸定位誤差和Y軸定位誤差，通過(guò)最小二乘估計(jì)可以使X軸和Y軸方向的殘差最小。為了嚴(yán)格控制定位誤差，本文采用八陣圖的8個(gè)基本方向的45°間隔為標(biāo)準(zhǔn)，選取定位小區(qū)域衰減方向組合最優(yōu)的4個(gè)AP用于在線(xiàn)定位。主要包括定位小區(qū)域AP衰減方向的計(jì)算和基于八陣圖方向組合的AP選取兩部分。

3.1 定位小區(qū)域AP衰減方向的計(jì)算

首先，根據(jù)KNN算法選擇K個(gè)鄰近指紋點(diǎn)；然后，用K-means算法對(duì)RSSI值聚類(lèi)，將這K個(gè)鄰近指紋點(diǎn)聚成兩類(lèi)。最后，用這兩個(gè)聚類(lèi)的坐標(biāo)中心來(lái)計(jì)算AP的衰減方向。AP衰減方向計(jì)算的具體過(guò)程如下：

(1) 選擇一個(gè)AP。

(2) 隨機(jī)選擇兩個(gè)不相鄰的指紋點(diǎn)，取該AP在這兩個(gè)指紋點(diǎn)處的RSSI(如RSSI1和RSSI2)作為聚類(lèi)中心。

(3) 計(jì)算其余(K-2)指紋點(diǎn)的RSSI值與這兩個(gè)RSSI中心之間的差值，記為ΔRSSI1i和ΔRSSI2i

(8)

比較ΔRSSI1i和ΔRSSI2i的大小，并將對(duì)應(yīng)的鄰近指紋點(diǎn)分配到差值較小的那一類(lèi)，直到所有鄰近指紋點(diǎn)及其RSSI分配完畢；

(4)重新計(jì)算并更新聚類(lèi)中心

(9)

式中，假設(shè)第1個(gè)聚類(lèi)中有L1個(gè)鄰近指紋點(diǎn)；第2個(gè)聚類(lèi)中有L2個(gè)鄰近指紋點(diǎn)；C1和C2分別是這兩個(gè)RSSI聚類(lèi)的聚類(lèi)中心。

(5) 重復(fù)步驟(3)—(4)，直到兩個(gè)聚類(lèi)中心不再變化為止。

(10)

(7) 計(jì)算該AP的衰減方向

(11)

(8)選擇下一個(gè)AP并重復(fù)步驟(2)—(7)，直到所有M個(gè)AP的衰減方向都計(jì)算出來(lái)。

3.2 基于八陣圖方向組合的AP選取

(1)計(jì)算每?jī)蓚€(gè)AP衰減方向之間的夾角

(12)

第3個(gè)軸的方向可以根據(jù)這兩個(gè)軸的方向來(lái)初步確定

(13)

(2) 計(jì)算其余M-3個(gè)AP衰減方向和axis3′之間的差，選取與axis3′差值最小的AP衰減方向作為axis3。同理，根據(jù)axis4和axis3的垂直關(guān)系來(lái)確定axis4

(14)

(3) 選擇這4個(gè)軸對(duì)應(yīng)的4個(gè)AP進(jìn)行在線(xiàn)定位。

4 試驗(yàn)驗(yàn)證

為了驗(yàn)證基于虛擬AP坐標(biāo)的指紋點(diǎn)聚類(lèi)算法和基于八陣圖的AP選取算法的性能，分別在武漢大學(xué)測(cè)繪學(xué)院和深圳大學(xué)科技樓進(jìn)行了試驗(yàn)驗(yàn)證。試驗(yàn)分析時(shí)，RSSI濾波均采用基于最大平均值的算法[39]對(duì)RSSI數(shù)據(jù)進(jìn)行預(yù)處理，定位計(jì)算采用經(jīng)典的加權(quán)K近鄰(weighted k nearest neighbor，WKNN)算法。

4.1 基于虛擬AP坐標(biāo)的指紋點(diǎn)聚類(lèi)算法定位效果分析

為了驗(yàn)證基于虛擬AP坐標(biāo)的指紋點(diǎn)聚類(lèi)算法的性能，在武漢大學(xué)測(cè)繪學(xué)院一樓101房間進(jìn)行了試驗(yàn)。圖2顯示了101房間的平面圖，定位區(qū)域?yàn)?.65 m×0.65 m的網(wǎng)格，其中6個(gè)AP用三角形表示，63個(gè)指紋點(diǎn)用圓點(diǎn)表示。然后在101房間的定位區(qū)域內(nèi)隨機(jī)選擇63個(gè)測(cè)試點(diǎn)。每個(gè)指紋點(diǎn)用1 s的采樣率采集RSSI約5 min，每個(gè)測(cè)試點(diǎn)用0.2 s的采樣率采集RSSI 5 s。為了確保一致性，所有數(shù)據(jù)都是使用同一部手機(jī)收集的。為方便起見(jiàn)，在每個(gè)房間也建立了獨(dú)立的坐標(biāo)系。

4.1.1 不同K值對(duì)定位精度的影響

當(dāng)K值取不同值時(shí)，會(huì)對(duì)定位精度產(chǎn)生影響。為了選擇最佳K值，表2顯示了不同K值對(duì)WKNN算法的定位誤差統(tǒng)計(jì)，K值范圍從2到10。從表2可以看出，當(dāng)K值從2到10變化時(shí)，WKNN定位誤差的平均誤差和均方根誤差RMSE均隨K的增大先減小后增大；當(dāng)K等于5時(shí)，RMSE和平均定位誤差均為最小值。因此K設(shè)為5。

表2 K值從2到10變化時(shí)對(duì)WKNN算法的定位誤差統(tǒng)計(jì)

4.1.2 不同路徑衰減因子對(duì)定位精度的影響

根據(jù)式(4)，當(dāng)路徑衰減因子取值不同時(shí)，可能會(huì)對(duì)AP的虛擬坐標(biāo)產(chǎn)生影響。一般來(lái)說(shuō)，無(wú)線(xiàn)信號(hào)在空氣中的路徑衰減因子是2，在有混凝土墻和走廊隔開(kāi)的辦公樓中的路徑衰減因子大約是3。表3顯示了路徑衰減因子范圍從2到4變化時(shí)對(duì)AP的虛擬坐標(biāo)(以AP1的X坐標(biāo)為例)的影響。

表3 路徑衰減因子從2到4變化時(shí)對(duì)虛擬AP1的X坐標(biāo)的影響

由表3可以看出，當(dāng)路徑衰減因子取不同值時(shí)，路徑衰減因子對(duì)AP的虛擬坐標(biāo)的影響是顯著的。然而，當(dāng)路徑衰減因子在2到4之間變化時(shí)，AP虛擬坐標(biāo)總是以相同組群的方式同時(shí)變化，因此可以基于此組群分類(lèi)的方式對(duì)相應(yīng)的指紋點(diǎn)(視為測(cè)試點(diǎn))進(jìn)行聚類(lèi)分隔。

4.1.3 定位精度比較

采用位置誤差的累積分布函數(shù)(cumulative distribution function，CDF)，分析4種不同算法對(duì)定位精度的影響，即WKNN算法、指紋點(diǎn)位置聚類(lèi)算法(RPLC)[28]、信號(hào)距離聚類(lèi)算法(SDC)[29]和基于AP虛擬坐標(biāo)(virtual AP coordinates，VAPC)的指紋點(diǎn)聚類(lèi)算法。分別選擇了0.3 m、0.5 m、0.8 m、1 m、1.5 m、2 m、2.5 m和3 m等8個(gè)不同的位置誤差閾值。

由圖3所示的結(jié)果可以看出，基于AP虛擬坐標(biāo)的指紋點(diǎn)聚類(lèi)算法的定位誤差也比其他算法小得多。例如，當(dāng)誤差閾值為1 m和2 m，該定位算法的CDF分別為50.79%和93.65%，高于WKNN算法的30.16%和74.60%，RPLC算法的31.75%和69.84%，以及SDC算法的30.16%和71.43%。表4顯示了相應(yīng)的定位誤差的統(tǒng)計(jì)結(jié)果。

圖3 4種算法定位精度比較Fig.3 Comparison of location accuracy of four different algorithms

表4 4種算法的定位誤差統(tǒng)計(jì)

由表4中可以看到，基于AP虛擬坐標(biāo)的指紋點(diǎn)聚類(lèi)算法定位結(jié)果定位誤差的RMSE為0.63 m，優(yōu)于WKNN算法的0.83 m、RPLC算法的0.94 m和WKNN算法的0.88 m。

4.2 基于八陣圖的AP選取算法定位效果分析

為了驗(yàn)證基于八陣圖的AP選取算法的性能，在深圳大學(xué)科技樓14樓進(jìn)行了試驗(yàn)，如圖4所示。手機(jī)接收了超過(guò)50個(gè)Wi-Fi熱點(diǎn)的RSSI數(shù)據(jù)。科技樓14樓整體建立了指紋點(diǎn)數(shù)據(jù)庫(kù)，相鄰指紋點(diǎn)間距約為2 m，定位區(qū)域內(nèi)63個(gè)測(cè)試點(diǎn)采用1 m×1 m格網(wǎng)采用。采用1 s的采樣率，每個(gè)指紋點(diǎn)采集RSSI約60 s，每個(gè)測(cè)試點(diǎn)采集RSSI約25 s。

圖4 科技樓14樓大廳的試驗(yàn)平面圖Fig.4 Floor plan of two halls in the fourteenth floor

4.2.1 不同AP數(shù)量對(duì)定位精度的影響

為了獲得良好的定位性能，需要根據(jù)平均定位誤差為每種算法選擇合適數(shù)量的AP個(gè)數(shù)。圖5顯示了當(dāng)AP數(shù)量從1到20變化時(shí)，北大廳和南大廳中MaxMean、InfoGain、PCA、online MI、IOD和ASCF 6種AP選取算法的平均位置誤差。通過(guò)對(duì)比分析可知，MaxMean、InfoGain、PCA、online MI、IOD和ASCF算法在不同的試驗(yàn)區(qū)域中的最優(yōu)AP數(shù)目是不同的(表5)。以PCA算法為例，在2個(gè)大廳中最優(yōu)AP數(shù)目分別為11和17。而本文提出的基于八陣圖的AP選取算法只需要4個(gè)AP，因此在實(shí)際應(yīng)用中具有更好的場(chǎng)景適應(yīng)性。

表5 6種算法在南北兩個(gè)大廳最合適的AP個(gè)數(shù)統(tǒng)計(jì)

圖5 MaxMean、InfoGain、PCA、online MI、IOD和ASCF算法在不同大廳的平均誤差Fig.5 Mean error of MaxMean, InfoGain MaxMean、InfoGain、PCA、online MI、IOD and ASCF in different halls

4.2.2 定位精度比較

分析7種不同算法對(duì)定位精度的影響，即MaxMean[20]、InfoGain[31]、PCA[24]、online MI[32]、IOD[34]和ASCF[35]算法和基于八陣圖(Eight-Diagram，ED)的AP選取算法。7種算法在南北大廳定位的位置誤差CDF如圖6所示。由圖6所示的結(jié)果可以看出，基于八陣圖的AP選取算法的性能明顯優(yōu)于其他算法。以北大廳為例，當(dāng)誤差閾值為1 m和2 m時(shí)，基于八陣圖的AP選取算法的誤差CDF分別為50.00%和82.50%，優(yōu)于MaxMean算法的30.00%和72.50%，InfoGain算法的27.50%和72.50%，PCA算法的22.50%和72.50%，online MI算法的32.50%和80.00%，IOD算法的27.50%和65.00%，以及ASCF算法的20.00%和62.50%。同樣，在南大廳，當(dāng)誤差閾值為1 m和2 m時(shí)，基于八陣圖的AP選取算法的誤差CDF分別為35.56%和80.00%，優(yōu)于MaxMean算法的28.89%和68.89%，InfoGain算法的20.00%和71.11%，PCA算法的22.22%和62.22%，online MI算法的28.89%和80.00%，IOD算法的17.78%和64.44%，以及ASCF算法的22.22%和57.78%。

圖6 7種不同AP選取算法定位精度比較Fig.6 Location accuracy comparison of sevendifferent AP selection algorithms

相應(yīng)的位置誤差統(tǒng)計(jì)結(jié)果見(jiàn)表6。表6所示的北大廳結(jié)果表明，基于八陣圖的AP選取算法定位結(jié)果定位誤差的RMSE為1.52 m，優(yōu)于MaxMean算法的1.82 m、InfoGain算法的1.82 m、PCA算法的1.83 m、online MI算法的1.66 m、IOD算法的1.87 m和ASCF算法的2.15 m。同樣，基于八陣圖的AP選取算法在南大廳定位結(jié)果定位誤差的RMSE為1.56 m，優(yōu)于MaxMean算法的1.94 m、InfoGain算法的1.85 m、PCA算法的2.08 m、online MI算法的1.60 m、IOD算法的1.99 m和ASCF算法的2.20 m。

表6 7種算法的定位誤差統(tǒng)計(jì)

4.3 虛擬AP支持的室內(nèi)非線(xiàn)性約束區(qū)域定位效果分析

為了驗(yàn)證虛擬AP支持的定位算法在室內(nèi)非線(xiàn)性約束區(qū)域的綜合定位性能，將離線(xiàn)階段的基于虛擬AP坐標(biāo)的指紋點(diǎn)聚類(lèi)算法和在線(xiàn)階段的基于八陣圖的AP選取算法用在同一個(gè)定位場(chǎng)景進(jìn)行定位分析。以深圳大學(xué)科技樓14樓大廳的兩個(gè)試驗(yàn)為例，基于虛擬AP坐標(biāo)的指紋點(diǎn)聚類(lèi)算法(VAPC)、基于八陣圖的AP選取算法(ED)以及二者融合后的算法(VAPC-ED)在南北大廳定位的位置誤差CDF如圖7所示。從圖7所示的結(jié)果可以看出，二者融合后算法的性能優(yōu)于VAPC和ED算法。當(dāng)誤差閾值為1 m和2 m時(shí)，二者融合后算法在北大廳的誤差CDF分別為80.00%和90.00%，在南大廳的誤差CDF分別為64.44%和91.11%，表現(xiàn)出了良好的定位效果。

圖7 3種不同算法定位精度比較Fig.7 Location accuracy comparison of three different algorithms

相應(yīng)的位置誤差統(tǒng)計(jì)結(jié)果見(jiàn)表7。表7所示的北大廳結(jié)果表明，融合后的算法定位結(jié)果定位誤差的RMSE為1.10 m，優(yōu)于VAPC算法的1.70 m和ED算法的1.52 m。同樣，融合后的算法在南大廳定位結(jié)果定位誤差的RMSE為1.17 m，優(yōu)于VAPC算法的1.62 m和ED算法的1.56 m。

表7 3種算法的定位誤差統(tǒng)計(jì)

5 結(jié) 論

針對(duì)目前室內(nèi)非線(xiàn)性約束區(qū)域的定位精度較低、存在大量冗余AP、無(wú)法使用行為地標(biāo)和室內(nèi)地圖校正等問(wèn)題，本文提出虛擬AP定位。離線(xiàn)階段，以定位小區(qū)域AP的虛擬坐標(biāo)為依據(jù)，提出一種基于虛擬AP坐標(biāo)的指紋點(diǎn)聚類(lèi)算法；算法無(wú)須預(yù)先設(shè)定聚類(lèi)個(gè)數(shù)即可實(shí)現(xiàn)指紋點(diǎn)聚類(lèi)的自動(dòng)化，提高了定位精度并降低了在線(xiàn)階段指紋匹配的計(jì)算量。在線(xiàn)階段，以定位小區(qū)域AP的衰減方向?yàn)橐罁?jù)，提出了一種基于八陣圖的AP選取算法；算法利用AP方向組合控制約束信息進(jìn)行AP選取，顯著減少在線(xiàn)定位的AP數(shù)量，提高了定位精度并降低了用戶(hù)定位的計(jì)算量。虛擬AP支持的兩種算法融合后，在室內(nèi)非線(xiàn)性約束區(qū)域表現(xiàn)出了更好的定位效果。從而提高室內(nèi)非線(xiàn)性約束區(qū)域定位的精度和穩(wěn)健性，促進(jìn)室內(nèi)定位技術(shù)在行人導(dǎo)航、智能交通及智慧城市等領(lǐng)域的應(yīng)用。