楊海峰 , 張勇波,2 , 黃裕梁 , 傅惠民

1(北京航空航天大學(xué) 小樣本技術(shù)研究中心,北京 100191)

2(北京航空航天大學(xué) 寧波創(chuàng)新研究院,浙江 寧波 315800)

在移動(dòng)技術(shù)蓬勃發(fā)展的今天,基于位置信息的服務(wù)在人們的日常生活中發(fā)揮的作用愈加重要,市場(chǎng)對(duì)于高精度室內(nèi)定位與導(dǎo)航服務(wù)等全新需求在不斷涌現(xiàn)[1,2].眾多公司已在各方面嘗試將室內(nèi)定位服務(wù)拓展并進(jìn)行大規(guī)模商業(yè)化運(yùn)營(yíng)[3,4].

截至目前,室內(nèi)定位尚未形成一套統(tǒng)一、成熟的解決方案[5,6],但是基于不同應(yīng)用場(chǎng)景與環(huán)境的各種室內(nèi)定位方法不斷被提出,其中主要包括基于微電子機(jī)械系統(tǒng)(micro-electro-mechanical system,簡(jiǎn)稱MEMS)的行人航跡遞推(pedestrian dead reckoning,簡(jiǎn)稱PDR)算法[7,8]、利用無(wú)線射頻識(shí)別(radio frequency identification,簡(jiǎn)稱RFID)技術(shù)的室內(nèi)定位方法[9,10]、基于偽衛(wèi)星網(wǎng)的室內(nèi)GPS 定位方法[11,12]以及基于WiFi 信號(hào)的室內(nèi)定位方法[13-18]等.然而,上述方法都面臨著各種各樣的問(wèn)題:由于MEMS 的誤差累計(jì),PDR 算法的定位精度會(huì)逐漸降低,以致完全失效;而RFID 定位和室內(nèi)偽衛(wèi)星定位則都需要鋪設(shè)大量外接設(shè)備以構(gòu)建導(dǎo)航網(wǎng)絡(luò),高昂的采購(gòu)與部署成本限制了其在商業(yè)領(lǐng)域的大規(guī)模推廣應(yīng)用.隨著移動(dòng)互聯(lián)網(wǎng)的飛速發(fā)展,WiFi 網(wǎng)絡(luò)迅速普及,遍布現(xiàn)代社會(huì)各個(gè)角落,因此,基于WiFi 的室內(nèi)定位技術(shù)以其部署成本低、易于推廣、精度較高等優(yōu)勢(shì),愈發(fā)引起研究人員的重視,逐漸成為室內(nèi)定位技術(shù)的熱點(diǎn)[19].

在基于WiFi 信號(hào)的室內(nèi)定位方法中,以指紋匹配法的位置估計(jì)精度更高、對(duì)復(fù)雜環(huán)境的適應(yīng)能力更強(qiáng),其包含離線采樣與在線匹配兩個(gè)階段.離線采樣階段是在目標(biāo)區(qū)域內(nèi)選取若干參考指紋點(diǎn)(reference point,簡(jiǎn)稱RP),記錄其位置、接收到各無(wú)線接入點(diǎn)(access point,簡(jiǎn)稱AP)的媒體訪問(wèn)控制(media access control,簡(jiǎn)稱MAC)地址以及相應(yīng)的WiFi 信號(hào)強(qiáng)度值(received signal strength indication,簡(jiǎn)稱RSSI)信息,通過(guò)對(duì)上述信息進(jìn)行分析和處理,得到目標(biāo)區(qū)域的指紋數(shù)據(jù)庫(kù).在線匹配階段是用戶使用設(shè)備在當(dāng)前位置接收到實(shí)時(shí)的測(cè)試數(shù)據(jù)(各AP的MAC 地址和相應(yīng)的RSSI 值),將其與指紋數(shù)據(jù)庫(kù)進(jìn)行匹配運(yùn)算,再利用庫(kù)中已知的RP 位置對(duì)用戶當(dāng)前位置進(jìn)行估計(jì)[20].

由于指紋匹配法具有較大的發(fā)展優(yōu)勢(shì),研究人員對(duì)其開(kāi)展了大量的研究.早期的Bahl 等人開(kāi)發(fā)了信號(hào)空間最接近K鄰近法(K-nearest neighbors in signal space,簡(jiǎn)稱KNN),該算法將篩選出的K個(gè)參考點(diǎn)坐標(biāo)的算數(shù)平均值作為最終的位置估計(jì)[21].Lionell 等人則在KNN 算法的基礎(chǔ)上提出了加權(quán)K鄰近算法(weightedKnearest neighbors,簡(jiǎn)稱WKNN),其對(duì)參考點(diǎn)的位置坐標(biāo)計(jì)算加權(quán)平均值,以得到更優(yōu)的位置估計(jì)[22].然而,無(wú)論是KNN算法還是WKNN 算法,它們的WiFi 指紋數(shù)據(jù)庫(kù)都是針對(duì)一整塊區(qū)域建立的,而工程實(shí)際要求處理面積較大的目標(biāo)區(qū)域,此時(shí)由于AP 的覆蓋范圍有限,上述算法無(wú)法根據(jù)目標(biāo)區(qū)域內(nèi)測(cè)得的WiFi 信息建立一套全區(qū)域都適用的指紋數(shù)據(jù)庫(kù).此外,WKNN 算法估計(jì)出的位置在空間上有時(shí)還會(huì)出現(xiàn)跳動(dòng)距離過(guò)大的情況,這是其在整個(gè)目標(biāo)區(qū)域內(nèi)選擇K個(gè)參考點(diǎn)所造成的固有缺陷.

針對(duì)上述問(wèn)題,本文提出了一種基于空間特征分區(qū)和前點(diǎn)約束的WKNN 室內(nèi)定位方法.該方法通過(guò)將面積較大的一整塊區(qū)域按照其空間特征劃分為多個(gè)分區(qū),解決了指紋數(shù)據(jù)庫(kù)全域覆蓋的問(wèn)題;又通過(guò)考慮行人前后位置之間空間約束關(guān)系,縮小了參考點(diǎn)的候選范圍,很好地提升了位置估計(jì)的平順性.大量真實(shí)環(huán)境下室內(nèi)定位實(shí)驗(yàn)的結(jié)果表明,本文方法可以有效地解決大面積區(qū)域內(nèi)的室內(nèi)定位問(wèn)題,且與傳統(tǒng)方法相比,定位精度有較大幅度的提升.

1 基于空間特征的室內(nèi)分區(qū)方法

傳統(tǒng)的WKNN 方法在建立WiFi 指紋數(shù)據(jù)庫(kù)的過(guò)程中,需要對(duì)目標(biāo)區(qū)域內(nèi)所有的指紋點(diǎn)所獲得各AP 的RSSI 數(shù)據(jù)進(jìn)行處理,具體處理方法是提取出全部RP 所共有的AP 對(duì)應(yīng)的強(qiáng)度信息.這樣做的前提是共有的AP存在且數(shù)量足夠,從另一方面來(lái)講,即要求有足夠多的AP 其信號(hào)可以覆蓋整個(gè)目標(biāo)區(qū)域.然而,當(dāng)目標(biāo)區(qū)域的面積足夠大時(shí),限于AP 的信號(hào)覆蓋能力,該條件顯然無(wú)法被滿足.

本文提出的基于空間特征的室內(nèi)分區(qū)算法可以很好地解決上述問(wèn)題,其基本做法為:首先將面積較大的目標(biāo)區(qū)域依據(jù)其空間特征(如是否貫通、有無(wú)遮擋等)劃分為多個(gè)面積較小的分區(qū),然后對(duì)每個(gè)分區(qū)分別獲取各自內(nèi)部RP 所共有的AP 信息作為該分區(qū)的標(biāo)識(shí)信息,同時(shí)建立分區(qū)指紋數(shù)據(jù)庫(kù);在在線匹配階段,通過(guò)比對(duì)測(cè)試點(diǎn)獲取的AP 信息與各分區(qū)的標(biāo)識(shí)信息,判斷該測(cè)試點(diǎn)所處的分區(qū);最后,使用相應(yīng)分區(qū)內(nèi)的指紋數(shù)據(jù)對(duì)測(cè)試點(diǎn)位置進(jìn)行估計(jì).具體處理方法如下.

?步驟1:劃分分區(qū).

根據(jù)目標(biāo)區(qū)域的面積大小,恰當(dāng)?shù)剡x取RP 的分布密度,記錄各RP 的位置信息.在每個(gè)RP 處獲取各AP 信息,并記錄相應(yīng)的RSSI 值.設(shè)目標(biāo)區(qū)域內(nèi)共有參考點(diǎn)m個(gè),第i個(gè)RP 的位置坐標(biāo)為(xi,yi),在該點(diǎn)可獲取ni個(gè)AP信息,其中,第j個(gè)AP 的MAC 地址為MAC_i_j,對(duì)應(yīng)的強(qiáng)度值為RSSI_i_j,則WiFi 信號(hào)的原始數(shù)據(jù)可以表示為

通過(guò)分析目標(biāo)區(qū)域的空間特征,將m個(gè)RP 分配到k個(gè)不同的分區(qū).設(shè)第i個(gè)分區(qū)內(nèi)有參考點(diǎn)im個(gè),則該分區(qū)內(nèi)的WiFi 信號(hào)數(shù)據(jù)可以表示為

由于每個(gè)RP 處能夠接受到的AP 信號(hào)數(shù)目各不相同,所以每條RP 數(shù)據(jù)的長(zhǎng)度不可能全部相同.為了后續(xù)計(jì)算的方便,需要對(duì)分區(qū)內(nèi)的WiFi 信號(hào)數(shù)據(jù)進(jìn)行預(yù)處理,使其長(zhǎng)度保持一致.具體做法是,截取分區(qū)內(nèi)所有RP 所共有的AP 信息,組裝成長(zhǎng)度統(tǒng)一的分區(qū)指紋數(shù)據(jù)庫(kù).設(shè)i分區(qū)內(nèi)im個(gè)RP 所共有的AP 數(shù)目為ni,則分區(qū)指紋數(shù)據(jù)庫(kù)可以表示為

?步驟2:提取分區(qū)標(biāo)識(shí)序列.

各分區(qū)的最主要區(qū)別在于其內(nèi)部信號(hào)較強(qiáng)的AP 各不相同,因此,將每個(gè)分區(qū)內(nèi)信號(hào)最強(qiáng)的q個(gè)AP 的MAC地址按照RSSI 由強(qiáng)到弱的順序排列組裝成一串特征序列,它就可以作為分區(qū)的標(biāo)識(shí)序列,簡(jiǎn)捷地反映出各分區(qū)的特征.具體做法如下.

(1)對(duì)i分區(qū)指紋數(shù)據(jù)庫(kù)內(nèi)對(duì)應(yīng)相同MAC 地址的RSSI 值進(jìn)行求和運(yùn)算,并按照由強(qiáng)到弱的順序進(jìn)行排列,得到強(qiáng)度和序列:

其中,

(2)若某AP 在分區(qū)內(nèi)部影響較大,則分區(qū)內(nèi)絕大部分RP 可以接收其RSSI,且數(shù)值較大.通過(guò)公式(4)和公式(5)的求和運(yùn)算后,該AP 對(duì)應(yīng)的強(qiáng)度和數(shù)值也較大,排序靠前.因此,可以截取公式(4)所示序列的前q個(gè)作為分區(qū)的標(biāo)識(shí)信息,組成新的強(qiáng)度和序列.

(3)將公式(6)中RSSI 值的和依照公式(3)所示的分區(qū)指紋數(shù)據(jù)庫(kù)替換為其各自對(duì)應(yīng)的MAC 地址,則可得到i分區(qū)的標(biāo)識(shí)序列:

?步驟3:分區(qū)判別.

由于對(duì)目標(biāo)區(qū)域進(jìn)行了分區(qū)處理,當(dāng)測(cè)試點(diǎn)數(shù)據(jù)獲得以后,首先需要執(zhí)行對(duì)其所處分區(qū)的判別,之后才能夠調(diào)取相應(yīng)分區(qū)內(nèi)的WiFi 指紋數(shù)據(jù)執(zhí)行WKNN 算法.設(shè)在測(cè)試點(diǎn)獲取的測(cè)試數(shù)據(jù)包含p個(gè)AP 信息,將其按信號(hào)強(qiáng)度從強(qiáng)到弱排序后,可以表示為

截取測(cè)試數(shù)據(jù)的前q個(gè)MAC 地址組成測(cè)試序列:

將公式(9)中的測(cè)試序列與公式(7)中每個(gè)分區(qū)的識(shí)別序列進(jìn)行比對(duì),記錄各組數(shù)據(jù)在2q個(gè)MAC 地址中重合的個(gè)數(shù),記作nums_amei,其中,1≤i≤k.

一般來(lái)說(shuō),選取{nums_ame}中數(shù)值最大的一個(gè),其所對(duì)應(yīng)的i即為當(dāng)前測(cè)試點(diǎn)所處的分區(qū)編號(hào).但是當(dāng)測(cè)試點(diǎn)處于兩分區(qū)交界線附近時(shí),其受到兩個(gè)分區(qū)的影響程度相當(dāng),便很容易出現(xiàn)nums_amei=nums_amej的情況.此時(shí),算法將無(wú)從判斷測(cè)試點(diǎn)所處的分區(qū).更嚴(yán)重時(shí),甚至?xí)斐煞謪^(qū)的誤匹配.為了盡可能減少匹配失效和誤匹配情況的發(fā)生,本文在采用識(shí)別序列進(jìn)行分區(qū)判別的基礎(chǔ)上,引入信號(hào)空間距離判定作為二級(jí)判定依據(jù),其具體做法如下.

(1)設(shè)定啟動(dòng)二級(jí)判據(jù)的閾值Δnums_ame,設(shè){nums_ame}中數(shù)值最大的兩個(gè)分別為nums_amei和nums_amej,且nums_amei≥nums_amej,如果兩者的差值大于Δnums_ame,則說(shuō)明i分區(qū)對(duì)測(cè)試點(diǎn)的影響力遠(yuǎn)大于j分區(qū),此時(shí)不需要啟動(dòng)二級(jí)判據(jù);如果兩者的差值小于或等于Δnums_ame,則說(shuō)明兩分區(qū)對(duì)測(cè)試點(diǎn)的影響力相當(dāng),此時(shí)就需要啟動(dòng)信號(hào)空間距離判據(jù).

(2)二級(jí)判據(jù)啟動(dòng)后,測(cè)試點(diǎn)需要依照WKNN 算法,分別與i,j兩個(gè)分區(qū)內(nèi)的指紋數(shù)據(jù)逐一計(jì)算信號(hào)空間距離,各空間距離可以表示為

在上式的計(jì)算過(guò)程中,由于測(cè)試數(shù)據(jù)和兩個(gè)分區(qū)指紋數(shù)據(jù)所包含的AP 信息不盡相同,因此需要截取各組數(shù)據(jù)所共有的AP 信息進(jìn)行計(jì)算.

(3)由于計(jì)算信號(hào)空間距離時(shí)對(duì)兩個(gè)分區(qū)指紋數(shù)據(jù)截取的維度不同,為了使空間距離具有可比性,將公式(10)中的空間距離分別除以各自對(duì)應(yīng)的維度,得到歸一化的信號(hào)空間距離,按距離從小到大排序后,可以表示為

其中,

(4)截取公式(11)中歸一化空間距離最小的K個(gè),記作:

對(duì)其進(jìn)行平均值的求取,得到K個(gè)歸一化歐式距離的均值:

如果mean_li≤mean_lj,則判定測(cè)試點(diǎn)處于i分區(qū);反之,則為j分區(qū).

綜上所述,本節(jié)給出了基于空間特征的室內(nèi)分區(qū)方法.方法流程圖如圖1 所示.它由兩部分組成.

?第1 部分是將目標(biāo)區(qū)域劃分為不同分區(qū),同時(shí)得到各分區(qū)的標(biāo)識(shí)序列和指紋數(shù)據(jù)庫(kù)

?第2 部分則給出了判斷測(cè)試點(diǎn)處于哪一分區(qū)的兩級(jí)判據(jù):標(biāo)識(shí)序列判別和歐氏距離判別.

通過(guò)分區(qū),在大面積目標(biāo)區(qū)域內(nèi)執(zhí)行室內(nèi)定位算法的困難得以解決,為后續(xù)基于前點(diǎn)約束的WKNN 定位算法的實(shí)現(xiàn)奠定了基礎(chǔ).

Fig.1 Spatial characteristics partition framework圖1 空間特征分區(qū)框架圖

2 基于前點(diǎn)約束的WKNN 定位算法

通過(guò)對(duì)目標(biāo)區(qū)域分區(qū)和分區(qū)判別算法,可以確定用戶所在測(cè)試點(diǎn)的分區(qū)編號(hào),進(jìn)而可以調(diào)用對(duì)應(yīng)分區(qū)內(nèi)的WiFi 指紋數(shù)據(jù)庫(kù),采用WKNN 算法得到最終的用戶位置估計(jì).傳統(tǒng)的WKNN 算法雖然較KNN 算法在定位精度上有了一定的提升,但是并沒(méi)有解決其定位結(jié)果在短時(shí)間內(nèi)往復(fù)跳動(dòng)、平順性不佳的問(wèn)題.造成該問(wèn)題的原因在于,這兩種算法對(duì)K個(gè)參考點(diǎn)的選取并不恰當(dāng).理論上講,兩條WiFi 數(shù)據(jù)的信號(hào)空間距離越小,其在真實(shí)空間中對(duì)應(yīng)位置的距離也就越近,這是WKNN 算法的理論基礎(chǔ).但是無(wú)論是在指紋數(shù)據(jù)庫(kù)的錄入過(guò)程中,還是在測(cè)試數(shù)據(jù)的獲取過(guò)程中,WiFi 信號(hào)都不可避免地受到來(lái)自外界各種因素的干擾;同時(shí),由于AP 發(fā)射的WiFi 信號(hào)本身就存在很大的波動(dòng)性,因此實(shí)測(cè)得到的指紋數(shù)據(jù)與測(cè)試數(shù)據(jù)都不可能完全準(zhǔn)確.所以在WKNN 算法的計(jì)算過(guò)程中,通過(guò)比對(duì)信號(hào)空間距離篩選出的K個(gè)參考點(diǎn)很有可能并不是在實(shí)際空間上距離測(cè)試點(diǎn)最近的K個(gè).又由于WKNN 算法對(duì)于K個(gè)參考點(diǎn)的篩選范圍并沒(méi)有限制,所以篩選出的某一個(gè)或幾個(gè)參考點(diǎn)與測(cè)試點(diǎn)實(shí)際距離較遠(yuǎn)的極端情況也有可能發(fā)生,而這無(wú)疑會(huì)對(duì)位置估計(jì)的平順性和精度造成負(fù)面影響.

用戶在室內(nèi)行進(jìn)過(guò)程中,在比較短的時(shí)間段內(nèi)行進(jìn)的距離并不會(huì)很遠(yuǎn),因此可以認(rèn)為行人的位置在空間和時(shí)間上具有連續(xù)型,即,其受到空間與時(shí)間的約束限制.本文所采用的前點(diǎn)約束法正是基于室內(nèi)定位的這一特征,利用行人前一時(shí)刻獲得的位置估計(jì)來(lái)對(duì)當(dāng)前時(shí)刻的位置估計(jì)進(jìn)行約束.其基本做法為:首先,通過(guò)WKNN 算法在整個(gè)分區(qū)內(nèi)選出K個(gè)候選參考點(diǎn);然后,以前一時(shí)刻的位置為圓心,選取恰當(dāng)?shù)腞為半徑做圓,以圓內(nèi)作為約束條件對(duì)K個(gè)候選指紋點(diǎn)進(jìn)行篩選,得到用以進(jìn)行位置估計(jì)的最終參考點(diǎn);再通過(guò)WKNN 算法計(jì)算出最終的位置估計(jì).與傳統(tǒng)的WKNN 算法相比,基于前點(diǎn)約束法的WKNN 算法縮小了參考點(diǎn)的候選范圍,強(qiáng)制它們聚集到測(cè)試點(diǎn)實(shí)際位置的周?chē)?在根本上杜絕了由于WiFi 信號(hào)數(shù)據(jù)不準(zhǔn)確造成參考點(diǎn)距離實(shí)際位置較遠(yuǎn)情況的出現(xiàn),從而增強(qiáng)了定位結(jié)果的平順性,提高了位置估計(jì)的精度.基于前點(diǎn)約束的WKNN 算法的具體步驟如下所示.

?步驟1:計(jì)算信號(hào)空間距離.

用戶使用設(shè)備在測(cè)試點(diǎn)獲取如公式(8)所示的測(cè)試數(shù)據(jù),簡(jiǎn)記作序列A.

設(shè)測(cè)試點(diǎn)通過(guò)分區(qū)判別以被確認(rèn)屬于i分區(qū),則將序列A與公式(3)所示i分區(qū)指紋逐一進(jìn)行信號(hào)空間距離的計(jì)算,得到一組歐式距離的集合B.

其中,

其中,nj為序列A與分區(qū)指紋RP_ij所重合的AP 個(gè)數(shù).

?步驟2:加權(quán)得到位置估計(jì).

截取集合B的前K個(gè)元素,組成候選參考點(diǎn)歐氏距離集合C.

將集合C中的每個(gè)元素替換為其所對(duì)應(yīng)的RP 位置坐標(biāo),則可得到候選參考點(diǎn)位置集合D.

設(shè)行人在t-1 時(shí)刻的位置估計(jì)為(xt-1,yt-1),以其為圓心、以Rt-1為半徑做圓,記作圓o.以處于圓o內(nèi)部作為約束條件,獲取集合D的子集E,即為最終參考點(diǎn)位置集合.

其中,iO為使用前點(diǎn)約束篩選出的參考點(diǎn)的個(gè)數(shù).

相應(yīng)地,可以得到集合C的子集F,即為最終參考點(diǎn)歐氏距離集合.

基于WKNN 算法,根據(jù)公式(22)中的歐氏距離,可以計(jì)算最終參考點(diǎn)各自的權(quán)重:

則當(dāng)前時(shí)刻,t的位置估計(jì)(xt,yt)為

對(duì)于前點(diǎn)約束法,有兩點(diǎn)需要特殊說(shuō)明.

(1)對(duì)初始位置進(jìn)行估計(jì)時(shí),由于其沒(méi)有前一時(shí)刻的位置估計(jì),因此需要采用標(biāo)準(zhǔn)的WKNN 方法計(jì)算;

(2)在公式(21)與公式(22)所示的最終參考點(diǎn)篩選過(guò)程中,仍有小概率出現(xiàn)篩選結(jié)果為空集的情況,此時(shí)也采用標(biāo)準(zhǔn)的WKNN 方法進(jìn)行位置估計(jì).

前點(diǎn)約束法的流程圖如圖2 所示.

Fig.2 Former location restriction framework圖2 前點(diǎn)約束框架圖

3 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)設(shè)備與環(huán)境

選擇北京航空航天大學(xué)新主樓C 座9 層環(huán)形走廊作為實(shí)驗(yàn)場(chǎng)地進(jìn)行定位實(shí)驗(yàn),使用MI 5 手機(jī)(MEID:990********129)對(duì)參考點(diǎn)RP 處的WiFi 信號(hào)強(qiáng)度進(jìn)行采集,通過(guò)空間特征分區(qū)算法獲取指紋數(shù)據(jù)庫(kù)后,實(shí)驗(yàn)員手持該設(shè)備沿走廊中線繞實(shí)驗(yàn)場(chǎng)一周,實(shí)時(shí)獲取測(cè)試數(shù)據(jù)并與指紋數(shù)據(jù)庫(kù)進(jìn)行匹配,通過(guò)基于前點(diǎn)約束的WKNN 算法得到室內(nèi)位置的估計(jì)結(jié)果.

3.2 實(shí)驗(yàn)過(guò)程

(1)設(shè)置參考點(diǎn)并獲取原始數(shù)據(jù)

首先需要針對(duì)實(shí)驗(yàn)區(qū)域設(shè)置一定數(shù)量的參考點(diǎn),考慮到本實(shí)驗(yàn)中的目標(biāo)區(qū)域形狀為矩形,因此采用四邊形法,以1.2m 間隔進(jìn)行參考點(diǎn)的獲取,并在同一坐標(biāo)系下記錄各參考點(diǎn)的位置坐標(biāo),最終在目標(biāo)區(qū)域內(nèi)獲得158 個(gè)指紋點(diǎn),如圖3 所示.

Fig.3 Map of experimental environment圖3 實(shí)驗(yàn)環(huán)境示意圖

隨后,實(shí)驗(yàn)員手持MI 5 手機(jī)在所有參考點(diǎn)處對(duì)WiFi 信號(hào)進(jìn)行測(cè)量,所需記錄的數(shù)據(jù)包括所有接收到的AP的MAC 地址及其對(duì)應(yīng)的信號(hào)強(qiáng)度RSSI,經(jīng)編號(hào)后存儲(chǔ)為公式(1)所示的格式.在數(shù)據(jù)獲取過(guò)程中,為保證指紋數(shù)據(jù)的準(zhǔn)確性,盡量減少WiFi 信號(hào)波動(dòng)性造成的不利影響,在每個(gè)RP 處按照東西南北這4 個(gè)方向各進(jìn)行10 次測(cè)量,再對(duì)40 條數(shù)據(jù)取平均值作為最終的信號(hào)強(qiáng)度存入原始數(shù)據(jù)庫(kù)中.

(2)劃分分區(qū)并提取指紋數(shù)據(jù)庫(kù)

在參考點(diǎn)設(shè)置完畢的情況下對(duì)目標(biāo)區(qū)域進(jìn)行分區(qū),由于實(shí)驗(yàn)環(huán)境為一條環(huán)形走廊,按照分區(qū)內(nèi)部應(yīng)當(dāng)貫通的原則,在實(shí)驗(yàn)中將4 條直線型的走廊作為目標(biāo)區(qū)域的4 個(gè)分區(qū),如圖4 所示.

Fig.4 Target space partition圖4 目標(biāo)區(qū)域分區(qū)

在分區(qū)過(guò)程中需要注意:為了避免分區(qū)后形成定位盲區(qū)(即不被任何分區(qū)所覆蓋的室內(nèi)空間,如圖5 所示),相鄰的分區(qū)應(yīng)當(dāng)共享邊界處的指紋點(diǎn),使分區(qū)之間達(dá)到無(wú)縫連接.

Fig.5 Blind zone caused by wrong partition圖5 錯(cuò)誤分區(qū)造成的定位盲區(qū)

在分區(qū)劃分完成后,對(duì)各自分區(qū)內(nèi)部的WiFi 信號(hào)原始數(shù)據(jù)進(jìn)行共有AP 信息的截取,以建立分區(qū)指紋數(shù)據(jù)庫(kù)(如公式(3)所示),進(jìn)而提取出各分區(qū)的標(biāo)識(shí)序列(如公式(7)所示).分區(qū)指紋數(shù)據(jù)庫(kù)的建立過(guò)程與分區(qū)標(biāo)識(shí)序列的提取過(guò)程分別詳見(jiàn)第1 節(jié)的步驟1 與步驟2,此處不再贅述.

(3)在線測(cè)試并得到位置估計(jì)

建立分區(qū)指紋數(shù)據(jù)庫(kù)后可進(jìn)行在線測(cè)試階段,在該階段,實(shí)驗(yàn)員手持MI 5 手機(jī)沿走廊中線的規(guī)劃路徑勻速行走一圈,當(dāng)行走至測(cè)試點(diǎn)時(shí),通過(guò)操作實(shí)時(shí)獲取測(cè)試數(shù)據(jù),測(cè)試數(shù)據(jù)的存儲(chǔ)格式如公式(8)所示.實(shí)驗(yàn)過(guò)程中,共獲得155 個(gè)測(cè)試點(diǎn),測(cè)試點(diǎn)間隔0.6m,如圖6 所示.

Fig.6 True trajectory of positioning experiment圖6 定位實(shí)驗(yàn)真實(shí)軌跡

對(duì)于每一條測(cè)試數(shù)據(jù),首先通過(guò)分區(qū)判別算法確定實(shí)驗(yàn)員當(dāng)前位置所處的分區(qū)(詳見(jiàn)第1 節(jié)步驟3),進(jìn)而調(diào)用相應(yīng)分區(qū)的指紋數(shù)據(jù)庫(kù)與該條數(shù)據(jù)進(jìn)行匹配,最終通過(guò)基于前點(diǎn)約束的WKNN 算法計(jì)算得到位置估計(jì)結(jié)果(詳見(jiàn)第2 節(jié)).

3.3 實(shí)驗(yàn)結(jié)果與分析

基于上述已獲取的指紋數(shù)據(jù)庫(kù)和測(cè)試數(shù)據(jù),分別采用傳統(tǒng)的WKNN 算法、融合軌跡外推信息的WKNN 算法與本文基于空間特征分區(qū)與前點(diǎn)約束的WKNN 算法進(jìn)行對(duì)比運(yùn)算.實(shí)驗(yàn)中,對(duì)前兩種算法取K=5,對(duì)本文方法取K=10,R=2.7m.而對(duì)于前文所述兩種特殊情況,K取值與傳統(tǒng)WKNN 算法保持一致,記作KW.為保證分區(qū)判別算法的準(zhǔn)確性,對(duì)其所需參數(shù)取q=20,Δnums_ame=0.用戶在目標(biāo)區(qū)域行進(jìn)一圈,3 種方法位置估計(jì)的對(duì)比圖如圖7 所示,其各自的位置估計(jì)誤差見(jiàn)表1.

從圖7 中的對(duì)比可以看出,使用本文方法的位置估計(jì)軌跡更加平順.與使用傳統(tǒng)WKNN 方法的位置估計(jì)軌跡相比,往復(fù)跳動(dòng)的現(xiàn)象得到了很好地抑制,也更加貼合圖6 所示用戶真實(shí)的行進(jìn)軌跡.結(jié)合表1 所示兩種方法位置估計(jì)誤差的數(shù)值,其最小估計(jì)誤差都保持在0.02m,但是WKNN 方法的最大估計(jì)誤差達(dá)到了7.92m,而本文方法的最大估計(jì)誤差只有2.63m.

從全程的平均誤差來(lái)看,本文方法的平均估計(jì)誤差保持在1m 以內(nèi),達(dá)到了0.88m,與WKNN 方法1.66m 的平均誤差相比,估計(jì)精度提升了47%.融合軌跡外推信息的WKNN 方法則是在傳統(tǒng)WKNN 方法結(jié)果的基礎(chǔ)上,通過(guò)對(duì)前兩個(gè)時(shí)刻的位置估計(jì)外推得到當(dāng)前時(shí)刻位置估計(jì)的預(yù)測(cè)值,再將該預(yù)測(cè)值與WKNN 方法所得當(dāng)前時(shí)刻的位置估計(jì)進(jìn)行融合,從而得到最終的估計(jì)結(jié)果.該方法由于在估計(jì)過(guò)程中利用了用戶的歷史位置信息,因此精度與傳統(tǒng)的WKNN 方法相比有小幅度的提升,但是與本文方法的位置估計(jì)精度相比仍有非常巨大的差距(如表1 所示),這說(shuō)明本文方法對(duì)于歷史位置信息的挖掘和應(yīng)用更加深入和充分.此外,通過(guò)對(duì)155 個(gè)測(cè)試點(diǎn)分區(qū)判定結(jié)果的統(tǒng)計(jì),由識(shí)別序列與信號(hào)空間距離所組成的兩級(jí)分區(qū)判別算法,其準(zhǔn)確率達(dá)到了96.4%,顯示出判別算法在實(shí)際應(yīng)用中的可靠性.

Fig.7 Comparation of estimated trajectories圖7 位置估計(jì)對(duì)比

Talbe 1 Comparison of estimation errors表1 估計(jì)誤差對(duì)比

圖8 進(jìn)一步給出了本文方法和傳統(tǒng)WKNN 方法位置估計(jì)誤差的累計(jì)概率對(duì)比圖.從圖中可以看出,在采用本文方法對(duì)全程155 個(gè)測(cè)試點(diǎn)進(jìn)行位置估計(jì)時(shí),有80%以上的估計(jì)結(jié)果精度都保持在1.5m 以內(nèi);而在同樣的精度范圍內(nèi),傳統(tǒng)WKNN 方法估計(jì)結(jié)果達(dá)到標(biāo)準(zhǔn)的還不足60%.這也可以從另一個(gè)方面說(shuō)明,本文方法相對(duì)于WKNN 方法的提升是全方位的.

Fig.8 Cumulative probability of location estimation errors圖8 位置估計(jì)誤差的累計(jì)概率

3.4 參數(shù)優(yōu)化

在第3.2 節(jié)中已知,對(duì)本文方法所需要的參數(shù)取K=10,R=2.7m,KW=5.對(duì)于一個(gè)確定的目標(biāo)區(qū)域,選取不同的參數(shù)值得到最終的估計(jì)結(jié)果也有所不同.為了最大限度地發(fā)揮本文方法的優(yōu)勢(shì),實(shí)驗(yàn)中對(duì)參數(shù)進(jìn)行了最優(yōu)化計(jì)算.具體考慮了KW∈{4,5,6},R∈{2.5,2.6,…,3},K∈{5,6,…,15}下所有的組合方案,得到的計(jì)算結(jié)果如圖9～圖11所示.

在這3 種情況下,最優(yōu)參數(shù)組合均為K=10,R=2.7m,而其中以KW=5 時(shí)的位置估計(jì)精度最高,因此在本實(shí)驗(yàn)環(huán)境下,選取其作為實(shí)驗(yàn)參數(shù).需要說(shuō)明的是,該參數(shù)組合僅在當(dāng)前目標(biāo)區(qū)域下為最優(yōu)參數(shù),當(dāng)實(shí)驗(yàn)環(huán)境、測(cè)量工具發(fā)生變化時(shí),需要重新運(yùn)行參數(shù)優(yōu)化過(guò)程以獲得相應(yīng)條件下的最優(yōu)參數(shù).

Fig.9 Average estimation error distribution when KW=4圖9 KW=4 時(shí)平均估計(jì)誤差分布

Fig.10 Average estimation error distribution when KW=5圖10 KW=5 時(shí)平均估計(jì)誤差分布

Fig.11 Average estimation error distribution when KW=6圖11 KW=6 時(shí)平均估計(jì)誤差分布

4 結(jié) 論

傳統(tǒng)的WKNN 方法無(wú)法解決一套指紋數(shù)據(jù)庫(kù)覆蓋整個(gè)目標(biāo)區(qū)域的難題,同時(shí)還存在估計(jì)結(jié)果跳動(dòng)跨度較大的問(wèn)題,嚴(yán)重影響室內(nèi)定位精度.針對(duì)上述問(wèn)題,本文提出了一種基于空間特征分區(qū)和前點(diǎn)約束法的WKNN室內(nèi)定位方法.通過(guò)將面積較大的目標(biāo)區(qū)域按照其空間特征劃分為多個(gè)分區(qū),同時(shí)引入識(shí)別序列和歐氏距離的組合分區(qū)判據(jù),解決了指紋數(shù)據(jù)庫(kù)無(wú)法實(shí)現(xiàn)全域覆蓋的問(wèn)題;又通過(guò)考慮行人在相鄰時(shí)刻所處位置之間的空間約束關(guān)系,縮小了最終參考點(diǎn)的篩選范圍,很好地提升了位置估計(jì)的精度.在北京航空航天大學(xué)新主樓C 座9 層環(huán)形走廊進(jìn)行的室內(nèi)定位實(shí)驗(yàn)結(jié)果表明,與傳統(tǒng)的WKNN 方法相比,本文方法極大地提升了位置估計(jì)軌跡的平順性,分區(qū)判別正確率達(dá)到96.4%,室內(nèi)定位精度則提升了47%,達(dá)到了0.88m,進(jìn)而證明了本文方法的有效性.