劉 影 賈 迪 王和章

(遼寧工程技術(shù)大學(xué)電子與信息工程學(xué)院，遼寧葫蘆島 125105)

1 引言

隨著移動互聯(lián)網(wǎng)和智能終端的蓬勃發(fā)展，位置信息服務(wù)已受到研究人員廣泛關(guān)注。盡管傳統(tǒng)的GPS(global positioning system)定位和蜂窩定位技術(shù)在室外開闊環(huán)境中能達(dá)到較高的定位精度，但在室內(nèi)和惡劣環(huán)境下無法進(jìn)行有效定位，隨著Wi-Fi網(wǎng)絡(luò)的普及和高速發(fā)展，利用無線Wi-Fi實(shí)現(xiàn)室內(nèi)定位已成為研究熱點(diǎn)[1-3]。其中，基于位置指紋的Wi-Fi定位被廣泛研究。

位置指紋算法[4-5]是一種兩個(gè)階段的定位算法，可分為訓(xùn)練階段(離線)和定位階段(在線)。離線階段主要為數(shù)據(jù)采集階段，在定位區(qū)域內(nèi)選擇一些位置點(diǎn)作為采樣點(diǎn)，從附近的AP獲取RSSI (received signal strength indication)形成指紋，并創(chuàng)建位置指紋庫，其中每個(gè)指紋都對應(yīng)于唯一位置。在線階段為實(shí)時(shí)定位階段，需要待測目標(biāo)測量的指紋與指紋庫中的指紋進(jìn)行匹配，從而估計(jì)出待測目標(biāo)對應(yīng)的位置信息。在以往的眾多研究中，提出了許多基于統(tǒng)計(jì)學(xué)習(xí)的方法，如聚類、貝葉斯、核函數(shù)等位置預(yù)測方法，用來提高位置指紋的準(zhǔn)確性及接入點(diǎn)(Access Point，AP)的選擇。例如，Wei Zhang[6]等人針對AP的選擇問題，給出了一種基于WKNN和樸素貝葉斯域聚類室內(nèi)位置估計(jì)策略，有效的解決了AP的可靠性問題。李華亮[7]等人提出一種基于核的數(shù)據(jù)處理方法訓(xùn)練位置指紋數(shù)據(jù)，將位置指紋映射到高維空間進(jìn)行分析，挖掘出更多位置指紋特性。田洪亮[8]等人采用K-Means聚類算法對位置指紋進(jìn)行聚類，以減少在線階段指紋的匹配次數(shù)。

然而由于室內(nèi)布局的復(fù)雜性，Wi-Fi信號在傳輸過程中，容易受到障礙物等因素的影響，導(dǎo)致散射、反射、衍射現(xiàn)象和多徑效應(yīng)的發(fā)生，使終端所收集到的信號強(qiáng)度具有較大的隨機(jī)性和不穩(wěn)定性[9-11]。因此，每個(gè)采樣點(diǎn)上所采集到AP的RSS信號往往表現(xiàn)出不穩(wěn)定，而基于確定性的指紋算法，如K近鄰(KNN，k-nearest neighbor)算法以及加權(quán)k近鄰(WKNN，weight k-nearest neighbor)算法都是通過接收來自附近AP的RSS信號建立指紋數(shù)據(jù)庫，所以這兩種算法中實(shí)時(shí)的定位點(diǎn)不能自適應(yīng)的獲取穩(wěn)定且有效AP的RSS值。王磊[12]等人提出一種自適應(yīng)獲取WKNN有效接入點(diǎn)，解決了WKNN匹配準(zhǔn)確度不高的問題。

不同的基于指紋的室內(nèi)定位算法，多數(shù)是針對離線階段指紋庫的濾波處理以及對在線階段的匹配算法進(jìn)行優(yōu)化，而很少討論目標(biāo)在定位區(qū)域內(nèi)的行為特征。例如計(jì)算出目標(biāo)與AP之間的直線距離，可縮小對比指紋數(shù)據(jù)庫的范圍，減少比較次數(shù)。因此，建立良好的室內(nèi)距離估計(jì)數(shù)學(xué)模型是實(shí)現(xiàn)高精度定位的重中之重。當(dāng)模擬無線電傳播時(shí)，人們總是簡化假定遮蔽衰落是一個(gè)靜態(tài)值。事實(shí)上，遮蔽衰落是用來反映環(huán)境復(fù)雜性的，在實(shí)驗(yàn)過程中會對物理環(huán)境中微小的變化很敏感。因此，傳統(tǒng)的理論信號衰減模型難以滿足真實(shí)復(fù)雜的室內(nèi)傳播環(huán)境[13]。為確保算法設(shè)計(jì)的準(zhǔn)確性和高效率，性能分析、系統(tǒng)優(yōu)化和良好的數(shù)學(xué)模型必不可少[14]。

綜合以上分析，本文主要研究在復(fù)雜環(huán)境下的指紋定位方法。利用CFSFDP[15](Clustering by Fast Search and Find of Density Peaks)聚類方法訓(xùn)練原始位置指紋，即有效的處理指紋中“離群點(diǎn)”，且可以把采集到的指紋數(shù)據(jù)進(jìn)行分簇，分析其指紋的內(nèi)在相似性和外在差異性，進(jìn)而尋找出最優(yōu)指紋數(shù)據(jù)點(diǎn)，在此基礎(chǔ)上構(gòu)建正六邊形指紋地圖；在線階段提出一種自適應(yīng)距離傳播模型，用于指導(dǎo)待定位目標(biāo)搜索指紋庫區(qū)域，從而減少指紋搜索范圍。本文算法實(shí)驗(yàn)均來自于真實(shí)的環(huán)境，實(shí)驗(yàn)數(shù)據(jù)表明本文算法的定位誤差和時(shí)間復(fù)雜度優(yōu)于KNN和WKNN，并且在室內(nèi)復(fù)雜環(huán)境下具有良好的性能。

2 復(fù)雜環(huán)境下的自適應(yīng)室內(nèi)定位方法——ALCCE

本文提出一種復(fù)雜環(huán)境下基于CFSFDP的自適應(yīng)室內(nèi)定位方法，命名為ALCCE(Adaptive indoor localization algorithm of based on CFSFDP in complex environment)定位算法，具體方案如圖1所示。離線階段和在線階段所采集到的RSS數(shù)據(jù)需要進(jìn)行預(yù)處理，主要是對原始數(shù)據(jù)進(jìn)行去噪。在離線階段根據(jù)處理后的數(shù)據(jù)建立指紋地圖，并建立指紋數(shù)據(jù)庫。在線階段，采用自適應(yīng)信號傳播模型計(jì)算出待定位目標(biāo)與AP的距離d，將待定位目標(biāo)采集的指紋與指紋庫中與AP距離為d的指紋進(jìn)行匹配，最后將距離匹配度最高的指紋對應(yīng)的位置作為移動目標(biāo)的位置。

圖1 ALCCE方案

2.1 原始指紋經(jīng)CFSFDP的處理方法

通過大量的測試發(fā)現(xiàn)，無線Wi-Fi信號很容易受到環(huán)境的影響，使得RSS存在時(shí)變特性，從而在同一通信節(jié)點(diǎn)一段時(shí)間內(nèi)獲取的RSS信號存在較大差異性，很難準(zhǔn)確估計(jì)出到達(dá)AP之間的距離。因此，單個(gè)數(shù)據(jù)包產(chǎn)生RSS數(shù)據(jù)無法準(zhǔn)確反映出有效信息，如圖2所示。圖中橫坐標(biāo)表示采樣點(diǎn)與AP的距離，單位為m；縱坐標(biāo)表示單個(gè)數(shù)據(jù)包的方差，每個(gè)采樣點(diǎn)連續(xù)采集RSS數(shù)據(jù)3分鐘作為一個(gè)RSS數(shù)據(jù)包。為了解決信號時(shí)變對定位誤差的影響，本文在建立指紋庫之前先采用CFSFDP聚類算法對RSS數(shù)據(jù)進(jìn)行統(tǒng)計(jì)分布分析，以確保數(shù)據(jù)的穩(wěn)定性和有效性，作為后續(xù)指紋庫的構(gòu)建和進(jìn)行指紋匹配的基。

圖2 單個(gè)數(shù)據(jù)包的方差圖

CFSFDP[15]是一種綜合考慮局部密度和距離的聚類算法，其核心思想在于對聚類中心的刻畫。聚類中心應(yīng)具有兩個(gè)特點(diǎn)：與周圍節(jié)點(diǎn)相比自身密度最大；與其他聚類中心之間有足夠大的距離。利用這兩個(gè)特點(diǎn)將在同一個(gè)通信節(jié)點(diǎn)處的RSS數(shù)據(jù)點(diǎn)進(jìn)行歸類，進(jìn)而識別出離群點(diǎn)。

步驟1為了使數(shù)據(jù)集適合于該聚類算法首先將RSSi映射到二維空間，計(jì)算出任意兩個(gè)數(shù)據(jù)點(diǎn)的距離dij=dist(RSSi,RRSj)，表示數(shù)據(jù)點(diǎn)RSSi和RSSj之間的距離，令dij=dji，i

d1≤d2≤…≤dK

(1)

取dc=df(Kt)，f(Kt)表示對Kt進(jìn)行四舍五入運(yùn)算，t取經(jīng)驗(yàn)值0.02，詳見參考文獻(xiàn)[15]。dc決定聚類算法的成敗，如果dc過大，使得每個(gè)數(shù)據(jù)點(diǎn)的局部密度值都很大以至于區(qū)分度不高，當(dāng)dc大于距離dij最大值時(shí)，則所有數(shù)據(jù)點(diǎn)都?xì)w為一個(gè)簇，當(dāng)dc小于距離dij最小值時(shí)，每個(gè)數(shù)據(jù)點(diǎn)都單獨(dú)成為一個(gè)簇，導(dǎo)致無法對數(shù)據(jù)集S分類。

步驟3根據(jù)dij和dc計(jì)算出局部密度ρi，ρi主要用來刻畫聚類中心的鄰居節(jié)點(diǎn)個(gè)數(shù)。鄰居節(jié)點(diǎn)個(gè)數(shù)越多，其局部密度越大；反之，其局部密度越小。根據(jù)局部密度的含義，其表達(dá)式為：

(2)

其中，dc為截?cái)嗑嚯x。對于(2)可知，與數(shù)據(jù)點(diǎn)RSSi的距離小于dc的節(jié)點(diǎn)數(shù)越多，ρi越大。

ρq1≥ρq2≥…≥ρqN

(3)

(4)

δqi越大，說明數(shù)據(jù)點(diǎn)RSSi作為聚類中心時(shí)與其他聚類中心的距離越大。根據(jù)局部密度ρ和距離δ的含義可以得出，當(dāng)某一數(shù)據(jù)點(diǎn)的ρ值越大，且δ值越大，其該點(diǎn)成為聚類中心的可能性越大。

(5)

(6)

cqi=cnqi

(7)

定位區(qū)域內(nèi)每個(gè)節(jié)點(diǎn)通過連續(xù)收集多個(gè)數(shù)據(jù)包，根據(jù)步驟1～步驟4計(jì)算出所有數(shù)據(jù)點(diǎn)的局部密度ρ和距離δ，畫出關(guān)于ρ和δ決策圖，根據(jù)聚類個(gè)數(shù)選出聚類中心點(diǎn)，再根據(jù)步驟5對數(shù)據(jù)進(jìn)行分類，確定非聚類中心點(diǎn)歸屬于哪一個(gè)簇，進(jìn)而可分析出離群點(diǎn)。

圖3 聚類流程圖

2.2 室內(nèi)采樣點(diǎn)選擇方案

基于指紋的Wi-Fi室內(nèi)定位方法通常將定位區(qū)域劃分為網(wǎng)格狀，將當(dāng)前收集的指紋數(shù)據(jù)與指紋庫中所有項(xiàng)進(jìn)行比較，并以最高匹配度的指紋位置作為待定位目標(biāo)位置。

本文提出一種基于步長r的室內(nèi)采樣點(diǎn)選取方案，假設(shè)選定的定位區(qū)域?yàn)檎叫危鐖D4所示，在正方形中心設(shè)置一個(gè)采樣點(diǎn)A1，另外分別放置兩個(gè)采樣點(diǎn)A2和A3構(gòu)成邊長為r的正三角形。當(dāng)初始采樣點(diǎn)確定后，以順時(shí)針方向進(jìn)行轉(zhuǎn)動，當(dāng)?shù)谝粚愚D(zhuǎn)動完成之后，位于中心位置的采樣點(diǎn)A1繼續(xù)向第二層轉(zhuǎn)動，3個(gè)采樣點(diǎn)重復(fù)第1層的轉(zhuǎn)動步驟逐層外移，直到形成的正六邊形恰能覆蓋整個(gè)監(jiān)測區(qū)域[16]，如圖4所示。獲得定位區(qū)域內(nèi)的所有采樣點(diǎn)，遍歷所有采樣點(diǎn)便可得到l個(gè)指紋，每個(gè)采樣點(diǎn)的指紋利用2.1節(jié)方法進(jìn)行處理后，保存入庫，即如公式(8)所示，同時(shí)記錄每個(gè)指紋到達(dá)AP的距離Dl。

圖4 采樣點(diǎn)選取方案

(8)

(9)

最終指紋數(shù)據(jù)庫包括：距離Dl、指紋對應(yīng)的位置loc、采樣點(diǎn)的指紋FP。

此方案中r值選取與具體的定位區(qū)域大小有關(guān)，r值越小采樣點(diǎn)數(shù)量就越多定位精度越高，反之采樣點(diǎn)越稀疏定位精度越差。但是采樣點(diǎn)越多，構(gòu)建指紋地圖所需要的代價(jià)也越高，同時(shí)會造成很大的模糊度，一般幾十米內(nèi)的定位區(qū)域內(nèi)取值為1～2 m[7-8,17]。

2.3 在線位置指紋的處理

在線階段指紋匹配過程中引入了距離的限制，計(jì)算出待定位目標(biāo)與AP的距離，將要匹配的指紋限定在距離Dl上，縮小指紋匹配范圍，提升指紋匹配速度。

2.3.1距離的計(jì)算

通常，采用公式(10)所示的路徑損耗模型[18]進(jìn)行距離計(jì)算：

(10)

d=p1×RSS3+p2×RSS2+p3×RSS+p4

(11)

其中，d表示采樣點(diǎn)與AP之間的距離，單位m；RSS表示采集信號強(qiáng)度，單位為dBm，p1、p2、p3以及p4為擬合所獲參數(shù)，值為：p1=-0.00014、p2=-0.00767、p3=-0.1662、p4=-1.112。

圖5 信號強(qiáng)度與距離的擬合曲線

圖中縱坐標(biāo)表示距離，單位m；橫坐標(biāo)表示信號強(qiáng)度，單位dBm。此測距模型相比于自由空間衰減模型可以準(zhǔn)確反映當(dāng)前信號的衰減情況。

2.3.2指紋匹配

根據(jù)ASPM方案計(jì)算出待定位目標(biāo)和AP之間的距離d后，從指紋數(shù)據(jù)庫中匹配出與距離d最近的點(diǎn)，將待匹配的指紋數(shù)據(jù)庫范圍縮小至某一個(gè)指紋采樣點(diǎn)Γ上，其采樣點(diǎn)Γ到達(dá)AP的距離DΓ與待測目標(biāo)到AP的距離d最近。Γ滿足：

(12)

然而ASPM模型存在誤差，所以依據(jù)最近采樣點(diǎn)計(jì)算出的目標(biāo)位置存在較大偏差，因此將待匹配的指紋數(shù)據(jù)庫匹配范圍擴(kuò)大至[DΓ-low,DΓ+high](low和high值選取和ASPM模型誤差有關(guān))，將一個(gè)匹配點(diǎn)變?yōu)槎鄠€(gè)，提升匹配度。

從指紋數(shù)據(jù)庫中搜索出距離[DΓ-low,DΓ+high]對應(yīng)的指紋記錄Fs=(F1,F2,…,Fs)，假設(shè)待定位目標(biāo)檢測到AP信號強(qiáng)度為RSSU，將待測目標(biāo)測得的信號強(qiáng)度RSSU與Fs指紋進(jìn)行匹配，即計(jì)算RSSU與Fs指紋的歐式距離。

(13)

然后對這些距離進(jìn)行升序排序，取前k個(gè)與待測目標(biāo)指紋歐氏距離最小的指紋，將這些指紋對應(yīng)的位置坐標(biāo)求平均作為待測目標(biāo)的位置，如公式(14)所示：

(14)

此方法，待測目標(biāo)與指紋庫匹配時(shí)無需和指紋庫中所有的指紋進(jìn)行對比，因此降低了指紋的匹配時(shí)間，提高了效率。

指紋匹配算法：

(1)輸入FPl，RSSU，Dl，Dmax

(2)計(jì)算待測目標(biāo)到達(dá)AP的距離du

∥p1、p2、p3、p4擬合參數(shù)，RSSU表示待測目標(biāo)的指紋

fori=1 tol∥l表示指紋數(shù)量

(3)計(jì)算指紋庫中與待測目標(biāo)最近的采樣點(diǎn)?！桅！?1,2,…,l)

end for

(4)在Γ采樣點(diǎn)基礎(chǔ)上擴(kuò)大指紋匹配范圍

Ds=(Ds|low-DΓ

if low-DΓ<0

low-DΓ=0

end if

ifDΓ+high>Dmax

DΓ+high=Dmax∥Dmax表示定位區(qū)域內(nèi)采樣點(diǎn)到AP的最大距離

end if

fori=1 tos

(5)待測目標(biāo)與距離Ds所對應(yīng)的指紋匹配方法

d=norm((FP(:,S)-RSSU),2)

end for

d1=sort(d)∥對d值進(jìn)行升序排列

d2=d1(1:k)∥d2表示前k個(gè)最小的歐式距離

(6)取出前k個(gè)指紋對應(yīng)坐標(biāo)的平均值作為待測目標(biāo)位置

forj=1 tok

index(j)=find(d==d2(j))

Loc(j,:)=FP(index(j))

end for

UL=sum(Loc)/k∥待測目標(biāo)位置

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

3.1 實(shí)驗(yàn)設(shè)置

為了驗(yàn)證算法的性能，在MATLAB2016a編程工具下對算法進(jìn)行仿真分析，仿真過程中所使用的RSS信號均來源于真實(shí)環(huán)境測試。測試地點(diǎn)選在教學(xué)樓的走廊進(jìn)行，面積20 m×2.4 m。這個(gè)區(qū)域，人員走動頻繁，干擾復(fù)雜，AP放置于走廊兩側(cè)，采用圖6所示的采樣點(diǎn)方案，r取值為2 m，在AP左右側(cè)各選擇25個(gè)采樣點(diǎn)，共計(jì)50個(gè)采樣點(diǎn)。

3.2 指紋聚類對算法的影響

為了克服RSS信號本身的不穩(wěn)定性即環(huán)境的變動帶來的影響，體現(xiàn)信號的統(tǒng)計(jì)規(guī)律，本文在每個(gè)采樣點(diǎn)處連續(xù)采集100個(gè)數(shù)據(jù)，將采集到的RSS數(shù)據(jù)取絕對值后映射到二維平面，為了接近原始數(shù)據(jù)分布，將100個(gè)數(shù)據(jù)點(diǎn)的x軸坐標(biāo)除以10000，如圖7所示。

圖6 采樣點(diǎn)布置方案

圖7 節(jié)點(diǎn)分布圖

以圖7中100個(gè)節(jié)點(diǎn)為例，然后計(jì)算出局部密度ρi和距離δi，其決策圖如圖8所示。決策圖中同時(shí)具有較大ρ值和δ值的點(diǎn)恰好是圖7中所示數(shù)據(jù)的聚類中心。此外，δ值很大，但ρ值很小的數(shù)據(jù)點(diǎn)在原始數(shù)據(jù)點(diǎn)中是“離群點(diǎn)”。

圖8 決策圖

3.3 ASPM測距模型性能

3.3.1標(biāo)準(zhǔn)測距模型性能分析

本文在指紋匹配的過程中用到了測距模型，為了驗(yàn)證測距模型的準(zhǔn)確性，分別距離AP為2 m、4 m、6 m上隨機(jī)選3個(gè)點(diǎn)，在每個(gè)采樣點(diǎn)連續(xù)采集100次，然后采用公式(11)計(jì)算得到距離d，測量結(jié)果如圖10所示。可以發(fā)現(xiàn)，圖中線條波動比較劇烈，這是因?yàn)闊o線信號的不穩(wěn)定，導(dǎo)致計(jì)算結(jié)果有一定的差異。當(dāng)待測目標(biāo)距離AP為2 m時(shí)，測量距離的平均值為1.95 m，接近于真實(shí)距離；待測目標(biāo)距離AP為4 m時(shí)，測量距離的平均值為4.86 m；待測目標(biāo)距離AP為6 m時(shí)，測量距離的平均值為5.57 m。因此，該測距模型的平均測距誤差控制在1 m以內(nèi)。

圖9 聚類結(jié)果圖

圖10 ASPM測距結(jié)果值

ASPM測距模型的誤差累計(jì)密度函數(shù)分布如圖11所示。從圖中可以看出在100次測量中90%以上的結(jié)果誤差可以控制在2.5 m以內(nèi)，且距離AP越近誤差越小，距離AP為2 m以內(nèi)的誤差大概0.5 m左右。本文在指紋匹配的過程給出了由于測距誤差導(dǎo)致指紋匹配失敗方法，因此，容許測距有一定的誤差，那么在2.3.2節(jié)中的low和high取值為2.5。

圖11 ASPM誤差的累計(jì)概率函數(shù)

根據(jù)經(jīng)典測距模型，如公式(10)，分別計(jì)算距離AP 2 m、4 m、6 m上隨機(jī)3個(gè)點(diǎn)的測距結(jié)果，測距結(jié)果如圖12所示。公式(10)中的d0取值為1 m，室內(nèi)路徑損耗系數(shù)n=3。

圖12 公式(10)測量結(jié)果值

圖12中當(dāng)待測目標(biāo)距離AP為2 m時(shí)，測量距離的平均值為1.15 m；待測目標(biāo)距離AP為4 m時(shí)，測量距離的平均值為2.86 m；待測目標(biāo)距離AP為6 m時(shí)，測量距離的平均值為2.78 m。經(jīng)典測距模型的誤差累計(jì)密度函數(shù)分布如圖13所示，在100次測量中距離AP為4 m遠(yuǎn)時(shí)60%的結(jié)果誤差可以控制在2.5 m以內(nèi)，距離AP為6 m遠(yuǎn)時(shí)只有30%的結(jié)果誤差可以控制在3 m內(nèi)，距離AP為2 m以內(nèi)的節(jié)點(diǎn)誤差控制在1 m左右。從圖11和圖13中可以看出隨著距AP的距離增加，兩種測距模型的累計(jì)誤差概率都在增大，但本文提出的ASPM測距模型的準(zhǔn)確率要優(yōu)于其他方法。

圖13 經(jīng)典測距誤差的累計(jì)概率函數(shù)

3.3.2改變測距模型參數(shù)對測距結(jié)果的影響

當(dāng)把不同環(huán)境下測得的ASPM模型應(yīng)用于本次實(shí)驗(yàn)中，對定位性能會有一定的影響，如圖14所示。

圖14 改變測距模型參數(shù)后得到的測距結(jié)果

其中圖14(a)是對原始模型參數(shù)的微調(diào)，與圖10相比整體誤差變化不是很大；圖14(b)是在寢室樓走廊測得的模型參數(shù)，用于教學(xué)樓走廊試驗(yàn)，誤差變化超過10 m，因此要根據(jù)實(shí)際環(huán)境來建立測距模型。

3.4 AP數(shù)量對定位的影響

圖15是平均定位誤差的變化情況，隨AP數(shù)量增加，本文方法ALCCE與KNN、WKNN定位算法的平均定位誤差逐漸變小。當(dāng)定位區(qū)域只有1個(gè)AP時(shí)，指紋定位算法無法進(jìn)行定位[7]，根據(jù)本文的采樣點(diǎn)布置方案可以實(shí)現(xiàn)定位。

圖15 隨AP數(shù)量增加平均定位誤差的變化

隨著AP數(shù)量增加，定位誤差并不一定變小，因?yàn)榇ㄎ还?jié)點(diǎn)可能會選取距離較遠(yuǎn)的AP，如距離較遠(yuǎn)，信號較弱，RSS數(shù)值較小，受環(huán)境影響嚴(yán)重，不利于定位。

3.5 參數(shù)k對定位性能的影響

參數(shù)k是確定ALCCE定位算法所使用的近鄰數(shù)，當(dāng)AP=10，平均定位誤差與k之間的關(guān)系如圖16所示，此圖的測量結(jié)果是100次仿真的平均值。因?yàn)殡Sk值變大，定位所需的近鄰數(shù)變多，平均定位誤差也會整體變小。但經(jīng)過大量仿真發(fā)現(xiàn)k值并非越大越好，如果k值很大，會把對稱的采樣點(diǎn)或距離待定位目標(biāo)很遠(yuǎn)的采樣點(diǎn)納入到近鄰數(shù)中，進(jìn)而引起較大波動反而會影響定位結(jié)果。從圖16中可以看出k取6時(shí)平均定位誤差相對最小。

圖16 平均定位誤差隨參數(shù)k的變化

3.6 算法時(shí)間復(fù)雜度分析

ALCCE算法的時(shí)間復(fù)雜度由兩部分組成，即CFSFDP的時(shí)間復(fù)雜度和在線階段指紋匹配時(shí)間復(fù)雜度。假設(shè)定位區(qū)域內(nèi)有N個(gè)采樣點(diǎn)，每個(gè)采樣點(diǎn)采集的RSS數(shù)據(jù)為n個(gè)，移動目標(biāo)節(jié)點(diǎn)為M個(gè)，則ALCCE算法的時(shí)間復(fù)雜度為O(n2)。

證明：利用CFSFDP算法對采樣點(diǎn)數(shù)據(jù)進(jìn)行聚類時(shí)，首先計(jì)算參數(shù)ρi，dij，δi，時(shí)間復(fù)雜度均為O(n2)；其次，節(jié)點(diǎn)需要計(jì)算其作為簇首時(shí)的ci，時(shí)間復(fù)雜度為O(n)；然后，計(jì)算每個(gè)簇內(nèi)包含的節(jié)點(diǎn)nqi，時(shí)間復(fù)雜度為O(n)。因此，CFSPDF的時(shí)間復(fù)雜度為：

O(n2+n2+n2+n+n)=O(n2)

(15)

在線指紋匹配過程中，移動目標(biāo)定位時(shí)需要和離線指紋庫的數(shù)據(jù)進(jìn)行匹配，首先要計(jì)算距離AP距離，時(shí)間復(fù)雜度為O(M)；其次，移動目標(biāo)根據(jù)計(jì)算得到的距離將搜索范圍縮小至Ds=(Ds|low-DΓ

O(M+s×M)=O(M)

(16)

根據(jù)以上分析，由于n?M，因此整個(gè)算法的時(shí)間復(fù)雜度為O(n2)。

4 結(jié)論

本文針對現(xiàn)實(shí)Wi-Fi環(huán)境中由于RSS信號的不穩(wěn)定性，提出了一種基于CFSFDP分類的自適應(yīng)定位算法。該算法首先對采集的指紋數(shù)據(jù)使用CFSFDP進(jìn)行預(yù)處理，作為位置指紋數(shù)據(jù)，在此基礎(chǔ)上建立離線階段的指紋地圖方案，在線階段將建立的自適應(yīng)測距模型和指紋方案相結(jié)合，以降低指紋匹配次數(shù)。實(shí)驗(yàn)表明本文提出的算法具有更好的性能，降低了定位誤差，并且在只有1個(gè)AP的情況下也可實(shí)現(xiàn)定位。但本文采用的算法還不能很好實(shí)現(xiàn)對AP的挑選，下一步將研究其自適應(yīng)的AP挑選方法，為進(jìn)一步定位求精做準(zhǔn)備。

[1] 金培權(quán),汪娜,張曉翔,等.面向室內(nèi)空間的移動對象數(shù)據(jù)管理[J]. 計(jì)算機(jī)學(xué)報(bào),2015,38(9):1777-1795.

Jin Peiquan,Wang Na,Zhang Xiaoxiang,et al. Moving object data management for indoor spaces[J].Chinese Journal of Computers, 2015,38(9):1777-1795.(in Chinese)

[3] Schmidt E, Akopian D. Indoor positioning system using WLAN channel estimates as fingerprints for mobile devices[C]∥IS&T/SPIE Electronic Imaging, International Society for Optics and Photonics 2015: 94110R-94110R-9.

[4] Kaemarungsi K, Knshnamurthy P. Modeling of indoor positioning systems based on location fingerprinting[C]∥Proceedings of the 23rdAnnual Joint Conference of the IEEE Computer and Communications Societies.Los Alamitos,USA,2004:1012-1022.

[5] Li Qiyue, Li Wei, Sun Wei. Fingerprint and assistant nodes based Wi-Fi localization in complex indoor environment[J].IEEE Journals & Magazines,2016,4:2993-3004.

[6] Zhang Wei, Hua Xianghong, Yu Kegen. Domain Clustering Based WiFi Indoor Positioning Algorithm[C]∥2016 International Conference on Indoor Positiong and Indoor Navigation(IPIN).2016:1-5.

[7] 李華亮,錢志鴻,田洪亮.基于核函數(shù)特征提取的室內(nèi)定位算法研究[J].通信學(xué)報(bào)，2017,38(1):158-167.

Li Hualiang, Qian Zhihong, Tian Hongliang. Research on indoor localization algorithm based on kernel principal component analysis[J].Journal of Communications, 2017,38(1):158-167. (in Chinese)

[8] 田洪亮,錢志鴻,梁蕭.離散度WKNN位置指紋Wi-Fi定位算法[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào),2017,49(5):94-99.

Tian Hongliang, Qian Zhihong,Liang Xiao. Discrete degree WKNN location fingerprinting algorithm based on Wi-Fi[J]. Journal of Harbin Institute of Technology, 2017,49(5):94-99. (in Chinese)

[9] Chai X Y,Yang Q.Reducing the calibration effort for probabilistic indoor location estimation[J].IEEE Trans Mobile Computing,2007,6(6):649- 662.

[10] Jin Y Y,Soh W S,Wong W C.Error analysis for fingerprint-based localization[J].IEEE Communications Letters,2010,14(5):393-395.

[11] Lee M Y,Han D S.Voronoi tessellation based interpolation method for wi-fi radio map construction[J].IEEE Communications Letters,2012,16(3):404- 407.

[12] 王磊,周慧,蔣國平.基于WiFi的自適應(yīng)匹配預(yù)處理WKNN算法[J].信號處理,2015,31(9)：1067-1074.

Wang Lei, Zhou Hui, Jiang Guoping. WiFi-based Self-adaptive Matching and Preprocessing WKNN Algorithm[J].Journal of Signal Processing, 2015,31(9):1067-1074. (in Chinese)

[13] Kuo S P,Tseng Y C.A scrambling method for fingerprint positioning based on temporal diversity and spatial dependency[J].IEEE Trans Knowledge and Data Engineering,2008,20(5):678- 684.

[14] Davide Dardari,Andrea Conti,Ulric Ferner.Ranging with ultrawide bandwidth signals in multipath environments[C]∥IEEE Journal & Magazines, 2009, 97(2):404- 426.

[15] Rodriguez A, Laio A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191):1492-1496.

[16] 史庭俊,桑霞,徐力杰.WSN中一種基于移動錨節(jié)點(diǎn)的節(jié)點(diǎn)定位算法[J].軟件學(xué)報(bào),2009,20(Supplement):278-285.

Shi Tingjun, Sang Xia, Xu Lijie.A localization algorithm in wireless sensor networks with mobile anchor nodes[J].Journal of Software, 2009,20(Supplement):278-285. (in Chinese)

[17] 趙聘,陳建新.利用現(xiàn)有無線局域網(wǎng)進(jìn)行室內(nèi)定位算法研究[J].信號處理,2014,30(11):1413-1418.

Zhao Pin,Chen Jianxin.A study on indoor localization algorithm using existing wireless local area network[J]. Journal of Signal Processing, 2014,30(11):1413-1418.(in Chinese)

[18] Zhuang Y, Li Y, Lan H.Smartphone-based WiFi access point localization and propagation parameter estimation using crowdsourcing[J].Electronics Letters, 2015,51(17):1380-1382.