胡久松，劉宏立，徐 琨

(湖南大學(xué) 電氣與信息工程學(xué)院，長沙 410082)

0 引 言

隨著移動設(shè)備和移動通信技術(shù)的廣泛使用和移動互聯(lián)網(wǎng)的廣泛發(fā)展，人們對室內(nèi)定位服務(wù)(indoor positioning service，IPS)的需求不斷增加。由于WiFi網(wǎng)絡(luò)的普及，WiFi接入點(diǎn)可以在室內(nèi)環(huán)境中隨處可見，并且?guī)缀跛幸苿釉O(shè)備都具有內(nèi)置的WiFi接收模塊。因此，WiFi室內(nèi)定位已成為開發(fā)室內(nèi)定位的最有吸引力的研究課題。WiFi室內(nèi)定位已被廣泛研究，并且提出了許多解決方案[1-4]，其中，接收信號強(qiáng)度(received signal strength, RSS)作為位置的度量測定方法(位置指紋算法)被大多數(shù)室內(nèi)定位系統(tǒng)所采用，因?yàn)樗恍枰猈iFi接入點(diǎn)的位置。加權(quán)K-最近鄰(weighted K-nearest neighbor, WKNN)算法，通過獲取K個參考點(diǎn)位置(reference points, RPs)的加權(quán)平均進(jìn)行位置估計(jì)，是目前使用最廣泛的位置指紋算法之一[5-26]。由于很難獲取一個最優(yōu)的K值，大多數(shù)文獻(xiàn)采用的WKNN算法會選擇一個固定的K值或者考慮K為多個值的情況：文獻(xiàn)[6]選用了固定值K=4；文獻(xiàn)[7,23]選用了固定值K=3；文獻(xiàn)[27]選用了固定值K=4；文獻(xiàn)[8]對比了K=1,3,5,…,23的情況；文獻(xiàn)[14]提出了一種加強(qiáng)的WKNN算法，對比了K=2,…,5的情況；RADAR[22]討論了不同K值下WKNN算法對定位精度的影響，在其試驗(yàn)中隨著K值的增大，定位精度變高，但達(dá)到某個值時，定位會呈下降趨勢等。

需要繁瑣的不同K值的結(jié)果對比才能獲得一個較好的定位結(jié)果是選用固定K值的弊端。這是由于室內(nèi)環(huán)境的不同，參考點(diǎn)選取的位置不同，測試點(diǎn)所在的位置不同等原因，K取值過大，則有可能會將一些較遠(yuǎn)的無益鄰居也包含進(jìn)來，而K取值較小，則有可能會將一些較近的有益鄰居排除在外。因此，在線階段，需要動態(tài)選擇適當(dāng)?shù)腒值，以提高定位精度。文獻(xiàn)[13]提出了一種動態(tài)K的方案——EWKNN (enhanced weighted k-nearest neighbor)，通過相似度度量的均值作為閾值來動態(tài)判定K的取值。文獻(xiàn)[5]在文獻(xiàn)[13]的基礎(chǔ)上將閾值乘以參數(shù)c(c∈[0.1,2])。盡管這些動態(tài)K的方案在一定條件下使得WKNN算法的定位精度有了一定的提升，但存在著以下問題。

1)引入新的不確定性參數(shù)。文獻(xiàn)[13]中，通過RT進(jìn)行初步的參考點(diǎn)篩選結(jié)果對K的獲取影響較大，從而影響最終的定位精度；文獻(xiàn)[5]引入了參數(shù)c，某種程度上降低了文獻(xiàn)[13]中RT的影響，但等價于同時引入了RT和c這2個不確定性參數(shù)。

2)忽略K=1的情況。當(dāng)最優(yōu)K較小時，通過相似度度量的均值作為閾值來動態(tài)判定K的取值的方法會很難獲取到一個較小的K值，特別是最優(yōu)K值為1的情況(事實(shí)上，文獻(xiàn)[5，13]令K≥2,直接忽略了K=1的情況)，會導(dǎo)致定位精度下降。例如,當(dāng)測試點(diǎn)位置在臨近參考位置，甚至就在參考位置時，K=1的定位精度顯然是最好的。

針對以上問題提出了一種自適應(yīng)動態(tài)K的WKNN室內(nèi)定位方法——SAWKNN(self adaptive weighted K-nearest neighbor)。該算法在不引入新的不確定參數(shù)的前提下，采用“多雷達(dá)搜索策略”的方式自適應(yīng)選擇近鄰數(shù)K值進(jìn)行位置估計(jì)。實(shí)驗(yàn)結(jié)果表明，提出的算法可根據(jù)在線情況自適應(yīng)調(diào)整K值，獲得了較好的定位精度。

1 系統(tǒng)模型

1.1 基于指紋的室內(nèi)定位系統(tǒng)框架

基于指紋的室內(nèi)定位系統(tǒng)框架，包含離線和在線2個階段，如圖1所示。離線階段負(fù)責(zé)建立指紋數(shù)據(jù)庫。首先在規(guī)劃好的等距點(diǎn)使用移動設(shè)備收集WiFi信號；然后將搜集的WiFi信號求取平均值、標(biāo)準(zhǔn)差、處理丟失值等后形成指紋存儲在數(shù)據(jù)庫中；在線過程負(fù)責(zé)處理用戶的定位查詢服務(wù)。當(dāng)系統(tǒng)收到用戶的定位查詢時，系統(tǒng)對搜集的指紋與數(shù)據(jù)庫中的指紋進(jìn)行相似度度量計(jì)算。通過動態(tài)K算法選擇確定K的值，然后從中選出最可能的K個參考點(diǎn)，最后通過這K個的參考點(diǎn)位置加權(quán)和得到最終的位置估計(jì)。

圖1 基于指紋的室內(nèi)定位系統(tǒng)框架Fig.1 Block diagram of indoor location system

1.2 離線過程

(1)

?i={1,2,…,L},?j={1,2,…,N}

(2)

RSSo中的每個列向量代表每個參考點(diǎn)RPj在設(shè)備面向方向o時的指紋數(shù)據(jù)為

(3)

(3)式中，[]T表示向量的轉(zhuǎn)置。

1.3 在線定位過程

定位引擎在收到定位查詢后，首先根據(jù)AP選擇算法篩選出較強(qiáng)信號的AP，然后計(jì)算接收到的指紋與數(shù)據(jù)庫中參考位置的相似度度量。根據(jù)相似度度量，定位引擎確定K的值，最后從中選出K個最相似的指紋對應(yīng)的參考位置進(jìn)行加權(quán)求和得到位置估計(jì)。

1.3.1 相似度度量計(jì)算

定義在線過程在第r個測試點(diǎn)任意方向位置LOC(xr,yr)接收到的測量向量為

rssr=[rss1,r,rss2,r,…,rssL,r]T

(4)

試驗(yàn)過程中，整個樓層內(nèi)共檢測到L=339個AP信號,每個參考點(diǎn)分別被9～40個不同的AP信號所覆蓋。對于某一位置而言，并不是所有檢測到的AP信號對于定位都是有益的，事實(shí)上大多數(shù)都是無益的，這種現(xiàn)象在商場、寢室等覆蓋大量AP信號的公共區(qū)域特別常見，因此，需要對AP進(jìn)行選擇。這里通過大多數(shù)文獻(xiàn)常用的最強(qiáng)信號強(qiáng)度法[28]對AP進(jìn)行選擇。

定義一個1×L的行向量為

pm=[0,…,1,…,0],?m∈{1,2,…,M}

(5)

(5)式中：行向量中只有一位為1，其他位均為0，為1的位即代表該位對應(yīng)的AP被選中。將(4)式中信號強(qiáng)度值按序排列，選取信號強(qiáng)度最強(qiáng)的前M個，其中每個選擇均可用一個(5)式中的行向量表示。所有的行向量組成M×L的AP選擇矩陣P。因此，第r個測試點(diǎn)與第j個參考點(diǎn)間的相似度度量計(jì)算公式為

?j∈{1,2,…,N},o∈O

(6)

(6)式中，sim(r,j)o表示第r個測試點(diǎn)與朝向o的第j個參考點(diǎn)間的相似度度量?！?表示求取歐式距離。(6)式中除以M表示取歐式距離的均值作為對比對象。

1.3.2K的自適應(yīng)取值

由物理距離構(gòu)建的地圖稱之為物理地圖，而經(jīng)過計(jì)算相似度度量之后，由相似度度量構(gòu)建的地圖本文稱之為SIM地圖。K的自適應(yīng)取值是通過“多雷達(dá)搜索策略”的方式在SIM地圖上獲取的。在搜索策略中，需要首先獲取雷達(dá)的發(fā)射距離單元，并假設(shè)雷達(dá)是可以以成倍的發(fā)射距離單元發(fā)射信號搜索目標(biāo)的。這個發(fā)射距離單元，稱之為相似度鄰域半徑，每個參考點(diǎn)上的相似度鄰域半徑表示為simRj。雷達(dá)的搜索目標(biāo)為測試點(diǎn)。在計(jì)算相似度度量之后，每個參考點(diǎn)以b·simRj為發(fā)射距離發(fā)射信號搜尋目標(biāo)。顯然只有相似度度量在發(fā)射距離范圍內(nèi)的目標(biāo)才會被雷達(dá)發(fā)現(xiàn)。b是從值1開始的自然數(shù)，當(dāng)所有的雷達(dá)搜索不到信號時，將會擴(kuò)大發(fā)射距離，即b值增大。而同時搜索到目標(biāo)的雷達(dá)個數(shù)即為K值

K=count(sim(r,j)o<=b·simRj)，

?j∈{1,2,…,N}

(7)

(8)

求解為simRj=1，反應(yīng)了在SIM地圖上參考點(diǎn)之間“相互獨(dú)立”的相似度鄰域半徑平均范圍，即當(dāng)測試點(diǎn)落在某一參考點(diǎn)此相似度鄰域半徑范圍內(nèi)時，測試點(diǎn)發(fā)生在該參考點(diǎn)的可能性遠(yuǎn)大于其他參考點(diǎn)。顯然，這種獲取K值的方式?jīng)]有引入新的不確定性參數(shù)，僅只依賴于離線和在線數(shù)據(jù)。值得注意的是，simRj的值會根據(jù)參考點(diǎn)的布置不同而不同，但在同一場景下會發(fā)生微弱變化，可以視為是不變的。

相對于固定K值的WKNN算法，SAWKNN算法在在線定位階段只是增加了b×N次的判斷來自適應(yīng)選取K值。這種判斷的耗時幾乎可以忽略不計(jì)，因此，SAWKNN算法與固定K值的WKNN算法的耗時是差不多的。

1.3.3 位置估計(jì)

最后的位置估計(jì)采用K個最有可能的位置加權(quán)求和得到

(9)

(9)式中：ωl=1/sim(r,l)o；LOC(xj,yj)是第l個可能指紋的位置。

2 試驗(yàn)結(jié)果和分析

2.1 試驗(yàn)環(huán)境搭建

指紋采集是湖南大學(xué)電氣院13舍實(shí)驗(yàn)樓第7層進(jìn)行的，覆蓋面積50 m×18 m，總共測試了22間約8 m×4 m的房間和一個50 m×1.8 m的走廊如圖2所示。圖3為房間的大小信息和參考點(diǎn)(RPs)的位置信息(三角狀所示)的示意圖。RPs之間的間隔大部分為3塊瓷磚間距(0.9 m)，部分因?yàn)榉块g布局、障礙物等原因，分布和間距都進(jìn)行了調(diào)整?？偣苍O(shè)置了538個RPs和在RPs之間隨機(jī)選擇了924個測試點(diǎn)(test points，TPs)，其中，每個房間布置了16～23個RPs和26～48個TPs，走廊布置了112個RPs和172個TPs。

圖2 定位區(qū)域平面圖Fig.2 Plan of interest area

圖3 大小和位置示意圖Fig.3 Size and location of interest area

指紋采集使用的是安卓手機(jī)華為榮耀4c，配置如圖4所示。所有AP熱點(diǎn)都來自于已有安裝。

圖4 華為榮耀4c配置圖Fig.4 Configuration of Huawei glory 4c

每個RPs分別對東南西北4個方向搜集了40組數(shù)據(jù)，取平均值以及對應(yīng)坐標(biāo)存入數(shù)據(jù)庫中，共形成了2 152條參考指紋數(shù)據(jù)和924條測試數(shù)據(jù)。另在測試數(shù)據(jù)中混入隨機(jī)抽取的少量(16條)來自于參考位置的原始數(shù)據(jù)。

2.2 試驗(yàn)結(jié)果評估方法

(10)

誤差在1 m以內(nèi)的百分比即為R個TPs中ME≤1所占的比例。

2.3 手機(jī)朝向的影響

文獻(xiàn)[22,29]都討論了手機(jī)朝向的影響，其主要原因在于人體對信號的遮擋造成的信號衰減。采用WKNN算法，令K=4，M取參考點(diǎn)中AP覆蓋數(shù)的最小值9，對(E,W,S,N)4個方向上以及合并的庫Total進(jìn)行定位的結(jié)果，如圖5所示。由于測試點(diǎn)的方向隨意，在各個方向的表現(xiàn)略有差異，其中，Total的在平均定位誤差上表現(xiàn)最佳，但應(yīng)考慮的是，若選擇Total為參考庫，則算法的運(yùn)算時間是選擇單方向的將近4倍。之后的試驗(yàn)選擇單方向S和Total為代表作為參考庫進(jìn)行。

圖5 不同方向的參考庫定位的結(jié)果Fig.5 Position results using different orientation database

2.4 M的取值

每個參考點(diǎn)分別被9～40個不同的AP信號所覆蓋，因此，M的取值為9～40。采用WKNN算法，令K=4，M=9,10,…,40，對S和Total參考庫進(jìn)行定位的結(jié)果，如圖6所示。在S上，M=25平均定位誤差最小，而在Total上M=16為最小。由于M的取值為多少合適，沒有較好的判斷準(zhǔn)則，因此，為了減少計(jì)算量，之后的試驗(yàn)均采用M=9進(jìn)行試驗(yàn)(M的取值并不影響算法之間的優(yōu)劣比較結(jié)果)。

2.5 相關(guān)算法的局限性

2.5.1 固定K值

采用WKNN算法，令K=1,2,…,80，M=9，對S和Total參考庫進(jìn)行定位的結(jié)果，如圖7所示。試驗(yàn)結(jié)果與RADAR[22]結(jié)果一致：隨著K值的增大，定位精度變高，但達(dá)到某個值時，定位誤差轉(zhuǎn)而上升，其中，Total由于考慮了多個方向，下降趨勢要慢一些。這是由于K的取值過大，有可能則會將一些較遠(yuǎn)的無益鄰居也包含進(jìn)來，而K的取值較小，則有可能會將一些較近的有益鄰居排除在外。因此，在線階段，需要動態(tài)選擇適當(dāng)?shù)腒值，以提高定位精度。圖7中曲線最低端對應(yīng)的K值通常稱之為最優(yōu)固定K值。

圖6 不同的M值的定位結(jié)果Fig.6 Position results using different value of M

圖7 不同的K值的定位結(jié)果Fig.7 Position results using different value of K

2.5.2 參數(shù)RT的取值

文獻(xiàn)[13]提出的動態(tài)K方案——EWKNN是通過公式(6)計(jì)算相似度度量之后，通過閾值RT進(jìn)行初步篩選后，即將相似度度量大于RT的參考點(diǎn)去除后，將剩余相似度度量的均值作為閾值，計(jì)算小于該閾值的參考點(diǎn)個數(shù)即為K值。該方法受參數(shù)RT的影響較大。試驗(yàn)中，相似度度量為(0,15)。采用EWKNN算法，令M=9，RT={1，2,…,15}(根據(jù)文獻(xiàn)[13]描述，K最小值應(yīng)取2，因此，當(dāng)小于RT的個數(shù)小于2時，令K=2)，對S和Total參考庫進(jìn)行定位的結(jié)果，如圖8所示。顯然，不同RT值會導(dǎo)致不同的計(jì)算結(jié)果。RT=3的平均定位誤差是最小的，因此，之后的試驗(yàn)采用RT=3。

圖8 不同的RT值的定位結(jié)果Fig.8 Position results using different value of RT

2.5.3 參數(shù)c的取值

文獻(xiàn)[5,13]的基礎(chǔ)上將閾值乘以了參數(shù)c(c∈[0.1,2])，旨在通過調(diào)整閾值的程度使得定位精度有一定的提升。采用EWKNN算法，令M=9，RT=3，c={0.2,0.3,…,2}，對S和Total參考庫進(jìn)行定位的結(jié)果，如圖9所示。由試驗(yàn)結(jié)果可知，只有在c=1附近的值對定位精度有少量提升，其他范圍的值反而會降低定位精度。事實(shí)上要獲取參數(shù)c的值使得定位結(jié)果有提升有很大的不確定性。

圖9 不同的c值的定位結(jié)果Fig.9 Position results using different value of c

2.6 SAWKNN算法

動態(tài)K方案應(yīng)在不引入新的不確定參數(shù)的前提下，解決K的選擇問題，顯然文獻(xiàn)[5,13]的方案引入了新的不確定性參數(shù)。因此，不能滿足要求。SAWKNN的定位結(jié)果，如圖10所示。并與不同固定K值的情況進(jìn)行了比較。由圖10可知，SAWKNN的定位結(jié)果接近于最優(yōu)固定K值的結(jié)果。表1列舉了常用的WKNN-K=1，WKNN-K=2，WKNN-K=3，WKNN-K=4以及EWKNN-Rt=3,c=1和SAWKNN算法的定位結(jié)果詳細(xì)數(shù)據(jù)(橫向一組2個數(shù)據(jù)分別表示在S和Total上的定位結(jié)果)。由表1可知，SAWKNN在平均誤差和1 m內(nèi)誤差上都獲得了較好的定位結(jié)果。盡管EWKNN也同樣也能獲得較好的定位結(jié)果，但是需要較好的選擇RT和c的值，事實(shí)上RT和c具有不確定性。

圖10 SAWKNN的定位結(jié)果Fig.10 Position results of SAWKNN

算法平均誤差/m誤差在1 m內(nèi)的百分比/%STotalSTotalWKNN-K=11.82.03229WKNN-K=21.61.84034WKNN-K=31.61.84036WKNN-K=41.51.84136EWKNN-RT=3,c=11.51.84135SAWKNN1.51.73937

圖11 定位查詢來自于參考點(diǎn)的定位結(jié)果Fig.11 Position results of location query from RPs

顯然只有考慮了K=1的情況，才能獲得精準(zhǔn)的參考點(diǎn)定位結(jié)果(誤差為0)。這種對剛好來自于參考點(diǎn)本身的情況進(jìn)行精準(zhǔn)定位非常有利于動態(tài)追蹤算法的誤差校正、數(shù)據(jù)庫的指紋更新等應(yīng)用。WKNN的K的自適應(yīng)調(diào)整圖如圖12所示。

圖12 K值自適應(yīng)變化Fig.12 Adaptive change of K value

可見，K值會根據(jù)在線情況自適應(yīng)調(diào)整K值，且包含了K=1的情況。

3 結(jié) 論

使用WiFi無線技術(shù)獲取室內(nèi)定位信息作為位置服務(wù)的上下文，這對室內(nèi)定位應(yīng)用的發(fā)展具有重要意義。針對WKNN算法需要動態(tài)變化K值的問題上，在不引入不確定性參數(shù)的前提下，提出了自適應(yīng)動態(tài)K的SAWKNN定位方法。提出的算法僅依賴于離線和在線數(shù)據(jù)。在真實(shí)環(huán)境中采樣了大量數(shù)據(jù)進(jìn)行了試驗(yàn)。在平均定位誤差、誤差1 m內(nèi)的比例的評估標(biāo)準(zhǔn)上進(jìn)行了試驗(yàn)分析。試驗(yàn)結(jié)果表明，提出的算法相比其他算法，具有以下優(yōu)點(diǎn)。

1)在不引入新的不確定性參數(shù)的前提下，根據(jù)離線和在線情況自適應(yīng)調(diào)整K值；

2)定位精度上接近最優(yōu)固定K值的定位結(jié)果；

3)考慮了K=1的情況。

基于以上的優(yōu)點(diǎn)，提出的算法將能更好地應(yīng)用于實(shí)際中。