基于WiFi的分級室內(nèi)定位*

王行娟

(武漢華夏理工學院 信息工程學院，武漢 430223)

0 引 言

隨著室內(nèi)環(huán)境中基于位置的服務(Location-based Service，LBS)的需求不斷增加，室內(nèi)環(huán)境中的定位成為了研究的熱點[1-6],而基于WiFi的定位在室內(nèi)環(huán)境中有較大的優(yōu)勢，原因如下：第一，室內(nèi)環(huán)境中，衛(wèi)星導航信號被遮蔽，無法提供室內(nèi)的服務，因此通常將室內(nèi)環(huán)境歸于衛(wèi)星導航拒止環(huán)境；第二，基于WiFi的定位不需要額外的硬件，僅需要含有WiFi功能的設備，隨著智能手機的普及，這一點也容易滿足；第三，許多需要室內(nèi)定位的場景，如機場、火車站和商場等，都普遍存在許多WiFi信號，不用額外安裝。

基于WiFi的室內(nèi)定位可以分為兩個步驟：離線指紋地圖(Fingerprint Map,FM)的建立和在線的定位過程。這里的指紋表示在某位置的從不同WiFi接入口(Access Point,AP)的接收信號強度(Received Signal Strength,RSS)。簡單來說，信號指紋可以看作一個向量，其中的元素為不同AP的接收信號強度。指紋地圖為一個數(shù)據(jù)庫，包含了不同室內(nèi)幾何位置測量得到的信號指紋。獲取離線指紋地圖的方法在文獻[7-9]中有詳細的敘述，由于其生成過程一般是事后的離線處理，因此該過程稱為離線指紋地圖建立。本文主要描述在線的定位過程，將采集的信號指紋與指紋地圖中的信號指紋進行匹配，根據(jù)匹配結(jié)果解算人員的位置。

為了能夠快速得到室內(nèi)的位置，在定位過程中，對實時性的要求很高。然而，一般的匹配過程，如K最近鄰法(K-Nearest Neighbors,KNN)算法的復雜度與指紋地圖中的樣本數(shù)目和區(qū)域內(nèi)的AP數(shù)目的乘積相關(guān)[10]。如果待定位區(qū)域范圍較大(如商場)，并且其總的AP數(shù)據(jù)較大，可達1 000以上，KNN算法無法達到實時定位的要求。另外，KNN算法需要對不同維度的信號指紋進行補齊，使其維度相同，從而計算信號指紋間的距離，這帶來了額外的計算量。

為了減小定位過程中的計算量，達到實時定位的要求，文獻[11-15]提出將定位的過程分級，分為粗定位和精定位，其中粗定位一般通過聚類的方法將當前信號指紋歸于某一類。這里，一類表示一個較小區(qū)域內(nèi)的所有信號指紋。如果采集到的信號指紋歸于某類，說明人員位于這個子區(qū)域內(nèi)，因此叫粗定位。粗定位后，再將信號指紋與該子區(qū)域內(nèi)的指紋進行匹配，從而獲取更加精確的位置估計(精定位)。在這些方法中，文獻[11-12]提出了用AP(Affine Propagation)聚類算法進行粗定位，文獻[13-15]提出用k均值聚類的方法進行粗定位。然而，這些方法中仍然存在計算量較大的問題。每次定位中，新采集到信號指紋被放入指紋地圖中的所有信號指紋中進行聚類，相當于每次定位都需要完成一次聚類。文獻[16-18]同樣利用了粗定位和精定位的框架，其中文獻[16]通過當前估計得到的位置對KNN搜索的范圍進行對應的縮小，可以有效提高平均定位精度和縮小定位時間。該方法的缺點是，在當前位置估計不準確時可能導致下一次定位誤差增大，從而存在較多定位異常值。文獻[17]方法同樣擁有粗定位和精定位的框架，粗定位中通過編輯距離實現(xiàn)。編輯距離在算法實現(xiàn)上，需要遞歸地實現(xiàn)，在AP數(shù)目較大時，其運算速度仍然較慢。文獻[18]利用DS證據(jù)理論進行粗定位，為了緩解DS證據(jù)理論中的 “指數(shù)爆炸”問題，將信號指紋庫分成了多個層級，又導致了指紋庫生成過程中復雜度大大提高。

本文提出一種基于WiFi的分級定位方法，同樣分為粗定位和精定位。粗定位中，手動將定位區(qū)域劃分為更小的幾個固定的子區(qū)域，將子區(qū)域內(nèi)的所有信號指紋并集作為新的信號指紋，通過漢明距離(Hamming distance)找到最近的幾個子區(qū)域后(粗定位)，再通過KNN的方法在這些子區(qū)域內(nèi)進行匹配定位。由于該方法的子區(qū)域劃分固定，可以在定位前一次性完成，相比于基于聚類的方法，不需要每次定位重新進行聚類過程(子區(qū)域劃分)。實驗結(jié)果表明，本文的分級定位框架具有延遲低的優(yōu)點。

1 方法步驟

為了提高WiFi定位的速度和精度，將定位的流程分為粗定位和精定位，圖1為整體流程圖。首先對原始的指紋地圖進行分區(qū)，獲得子區(qū)域的指紋地圖合集。

圖1 WiFi分級室內(nèi)定位結(jié)構(gòu)

1.1 粗定位

粗定位的過程中，通過漢明距離匹配采集到的信號指紋和子區(qū)域內(nèi)的指紋得到可能的子區(qū)域集合。這里的匹配過程中每個子區(qū)域的信號指紋經(jīng)過處理僅含一個指紋，將在后面詳細敘述。精定位中，將采集到的信號指紋和可能子區(qū)域集合內(nèi)的信號指紋進行匹配，這里的信號指紋為指紋地圖內(nèi)的原始信號指紋，最終得到定位結(jié)果。本節(jié)主要描述粗定位的過程(包含分區(qū)的過程)。

圖2 粗定位中的分區(qū)過程示意圖

信號指紋可以用一個哈希表(Hash map)鍵值表示，如式(1)所示(這里忽略掉上下標的索引)：

(1)

表示信號指紋為一個哈希表，哈希表的鍵(key)為不同AP的MAC地址，可用于區(qū)分不同的AP，哈希表的值為從該AP的接收信號強度。進行分區(qū)后，通過該子區(qū)域內(nèi)(如索引i的子區(qū)域)所有信號指紋的鍵值的并，得到該區(qū)域內(nèi)的所有MAC地址集合：

(2)

式中：M為該子區(qū)域內(nèi)的信號指紋的樣本數(shù)目，函數(shù)keys(.)表示從某哈希表中取出所有鍵值。注意在實際應用中，分區(qū)過程和對每個子區(qū)域求MAC地址集合的過程中僅需要進行一次。當新的WiFi信號指紋需要被用于粗定位時，仍然可以用之前的分區(qū)結(jié)果。

(3)

利用漢明距離的原因可以看作將不同AP的WiFi信號的可見性進行01編碼，從而生成可見性向量。此處漢明距離給出的物理意義是兩個信號指紋中的WiFi可見性不同的AP數(shù)目。在粗定位中選擇漢明距離的原因是該距離的計算可以轉(zhuǎn)換為與或的運算，不需要實際的信號強度相關(guān)運算，因此計算復雜度低。漢明距離相比于利用真實信號強度值的相關(guān)距離度量，用到的信息更少，導致精度更低。但是利用漢明距離進行粗定位能夠達到縮小待定位區(qū)域的目的，因此最終選擇漢明距離作為粗定位階段的距離度量。

本文在粗定位的過程中，雖然看起來是手動劃分子區(qū)域，但其本質(zhì)是依照幾何位置對子區(qū)域進行劃分。從原理上看，通過幾何位置進行子區(qū)域劃分相比于傳統(tǒng)的分級定位中按照信號空間聚類對子區(qū)域劃分的方法擴展性更強，具體原因如下：傳統(tǒng)的分級定位方法中，需要按照信號指紋進行聚類，因此需要所有信號指紋的先驗信息，進行維度對齊，當定位區(qū)域較大時信號指紋的維度可能很高，從而影響定位的拓展性和實時性。本文方法通過位置直接劃分子區(qū)域，并且在粗定位過程中直接通過漢明距離確定子區(qū)域，不需要對所有信號指紋的RSS進行維度的對齊，即不需要所有定位區(qū)域信號指紋的先驗信息，因此拓展性更強。

在本文的應用中手動劃分子區(qū)域的計算量可以看作是預處理過程，在建立信號指紋數(shù)據(jù)庫后計算單次即可。在子區(qū)域數(shù)目增多時，由于粗定位中漢明距離匹配計算速度更快，并且不需要在預處理后再進行RSS維度的對齊，因此粗定位所需的復雜度在縱向?qū)Ρ壬想m然會提高，但是相比于傳統(tǒng)方法橫向?qū)Ρ热匀痪哂袃?yōu)勢。

1.2 精定位

假設在粗定位的過程中找到M個可能的子區(qū)域，這些子區(qū)域包含了人員可能存在的位置。假設在這些子區(qū)域內(nèi)的信號指紋可以表示為{RSS1:N}，其中N表示信號指紋的個數(shù)。

在精定位中，循環(huán)計算集合{RSS1:N}中的信號指紋與當前信號指紋的RSScurr的距離。本文的KNN精定位方法中，嘗試利用兩種不同的距離度量進行定位，分別為歐氏距離和高斯距離。下面分別對兩種不同的距離度量進行詳細介紹。

歐氏距離按照如下步驟進行計算：

Step1 首先從兩個信號指紋RSSk和RSSq中取出其信號強度的值，分別可以寫為

Veck=value(RSSk)，

(4)

Vecq=value(RSSq)。

(5)

Step2 將兩個向量補成相同的長度，使得兩個向量中，每個維度對應的信號強度值來自于相同的AP。如果一個向量中存在來源于某AP的信號強度，而另一個不存在，則將AP的信號強度在另一個向量中設置為默認值-100 dBm。補齊后，兩個向量可以分別表示為

(6)

(7)

式中：V表示補齊后的向量長度。

Step3 根據(jù)如下的公式計算兩個信號強度向量的距離：

(8)

高斯對數(shù)距離的計算步驟的前兩步與歐氏距離相同，都需要信號強度值的取出與對齊，然后根據(jù)下面的公式進行高斯對數(shù)距離的計算：

(9)

(10)

式中：σ2表示方差，方差的取值可以表示室內(nèi)環(huán)境中不同的AP對應的信號強度的噪聲波動水平。因此，從準確的角度來說，不同的AP需要設置不同噪聲波動水平，因此需要不同的方差。但是這樣設置會大大增強計算量，不適合實際定位情況的應用，因此本文將σ2設置為典型值。

根據(jù)傳統(tǒng)的KNN算法完成精定位，這里近鄰數(shù)取3。根據(jù)上面的步驟找到信號強度距離最近的3個信號指紋，并且找到其對應的幾何位置，人員的最終估計位置為3個幾何位置的算數(shù)平均值。

1.3 復雜度分析

在傳統(tǒng)的部分級定位算法中，一次定位需要對所有的信號強度指紋進行比較(假設有N個)，并且每個信號強度指紋的維度包含了區(qū)域內(nèi)所有不同MAC地址的個數(shù)(此處假設有M個)，因此其復雜度為O(NM)。而本文提出的方法中，一次定位的復雜度為O(nm)，其中n表示精定位中子區(qū)域信號強度指紋的數(shù)目，m表示精定位中的子區(qū)域不同MAC地址的個數(shù)。子區(qū)域中的n與m通常遠小于所有區(qū)域的N和M，因此從理論上進行分析，本文所提方法的定位復雜度更低。

2 實驗與分析

2.1 實驗場景設置

為了獲取WiFi定位的精度，首先利用Google Nexus手機作為WiFi掃描工具獲取環(huán)境中的WiFi信號指紋。采用Nexus的原因是其系統(tǒng)為Android的原生系統(tǒng)，能夠更方便地通過編寫手機APP錄取WiFi指紋信號。在約50 m2的室內(nèi)環(huán)境中，利用室內(nèi)環(huán)境中已經(jīng)存在的方形地板磚的交點作為已知的室內(nèi)位置，地板磚的尺寸為60 cm×60 cm。在這些位置中錄取WiFi信號指紋，從而生成了一個小型的WiFi信號指紋地圖。在錄取信號指紋的過程中，筆者開發(fā)了對應的安卓APP，可以將不同位置掃描得到的WiFi信號指紋進行離線存儲，從而在實驗中使用。如圖3所示，人員在這些位置分別朝四個方向錄取5個信號指紋。實驗中用到的指紋地圖含2 600個WiFi信號指紋。在該場地中，根據(jù)面積計算，大致包含了50/0.36≈139塊地磚，若每塊地磚不重復計算交點，大概在139個位置進行了測量，每個位置存在4個方向，每個方向錄取5個信號指紋，總計信號指紋個數(shù)約為139×4×5=2 780個信號指紋。由于某些測量點靠近墻面，無法進行測量，因此最終得到的信號指紋約為2 600。在該實驗中，根據(jù)測量得到的信號指紋，總共發(fā)現(xiàn)了12個AP。其中，人為在定位區(qū)域周圍設置了5個AP，由于實驗中不要求AP的具體位置，因此實驗中未對其精確位置進行測量，只是大致在定位區(qū)域周邊均勻設置。另外7個AP是室內(nèi)環(huán)境中本來就存在的，其具體位置也未進行測量。本文實驗設置的參數(shù)如表1所示。

圖3 錄取指紋地圖示意圖

表1 實驗場景參數(shù)

在定位過程中，通過全站儀跟蹤人員(同時攜帶手機)的位置作為真實的位置，從而計算WiFi定位的誤差。

2.2 方法超參數(shù)確定

為了能得到更好的定位精度，首先對方法中不同的超參數(shù)進行對比。根據(jù)獲得的指紋地圖和人員的真實位置，可以統(tǒng)計WiFi定位的誤差。圖4為不同的粗定位過程中選取不同的可能子區(qū)域的數(shù)目(上文中的參數(shù)M)的定位結(jié)果和經(jīng)典的KNN定位方法的誤差的積累密度分布函數(shù)(Accumulative Distribution Function,CDF),可以看出，在子區(qū)域的數(shù)目選擇10時能夠獲得較好的定位精度，并且隨著子區(qū)域繼續(xù)增大，本文的分級定位方法逼近于傳統(tǒng)的KNN方法；當子區(qū)域增大到所有子區(qū)域的數(shù)目時，本文的分級定位方法完全退化為經(jīng)典的KNN方法。

圖4 本文方法子區(qū)域數(shù)目與經(jīng)典的KNN算法的定位誤差積累誤差密度分布函數(shù)比較

表2為本文分級定位方法取不同的子區(qū)域數(shù)目對應的定位精度的統(tǒng)計值，可以看出，當子區(qū)域數(shù)目為10時存在最小的誤差均值與最大誤差。

表2 不同子區(qū)域的數(shù)目對應的定位精度

本文算法中另一個超參數(shù)是L，表示劃分的子區(qū)域的大小。不同的L對最終的定位性能有影響，需要通過實驗確定其最佳值。下面對不同的L取值(分別為1 m、3 m、5 m、7 m、9 m)進行定位精度的對比。注意，此處用到的子區(qū)域數(shù)目為通過上文確定的最佳子區(qū)域數(shù)目，也就是10。如表3所示，當L=5 m時本文方法有著最小的定位誤差，因此本文取L=5 m。

表3 不同的L長度對定位性能的影響

上述的L和子區(qū)域的定位數(shù)目M都是本方法中的超參數(shù)，即在方法實施前就需要確定的參數(shù)，實驗中通常通過參數(shù)搜索的方法尋找最好的超參數(shù)配置。在工程實踐中，往往不能像該實驗這樣每次尋找最佳的超參數(shù)，不同的應用場景中最佳的超參數(shù)不同。直接選擇相同的超參數(shù)可能會造成精度損失，該損失可以看成工程實現(xiàn)造成的精度損失。在后續(xù)的工作中，筆者將會進一步研究本文方法在不同應用場景中進行遷移的問題，如最佳超參數(shù)不準造成的精度損失問題。

2.3 方法對比

本文主要提出了分級定位的框架，粗定位過程通過基于幾何位置的子區(qū)域劃分實現(xiàn)，精定位中既可以利用經(jīng)典的KNN也可以利用對應的最大后驗估計的方法。因此，本文方法的對比主要存在四種情況的對比，即分級定位(KNN精定位)、分級定位(最大后驗精定位)、KNN直接定位和最大后驗直接定位。在方法對比中，用到的測試數(shù)據(jù)中包含的信號指紋數(shù)目為500個，因此定位精度和定位時間是500次的平均。對比結(jié)果如表4所示。

表4 不同方法平均誤差和單次定位時間統(tǒng)計

從表4中可以看出，不管利用經(jīng)典的KNN定位算法還是利用最大后驗概率算法，加入分級定位框架后，從定位精度上看并沒有明顯提升，僅有少量提升。其原因是，分級定位中，由于在粗定位中縮小了待匹配的范圍，導致了匹配異?；蝈e誤匹配的情況，從而導致定位異常值的出現(xiàn)。另外，通過分級定位的框架后，平均單次定位時間在KNN算法下下降了約95%，在最大后驗算法下下降了約96%，體現(xiàn)出了本文分級定位框架延遲低的優(yōu)點。

上述實驗中的距離度量(包含經(jīng)典KNN方法和本文精定位中的度量)都采用了基于對數(shù)高斯距離的度量。下面對本文方法中精定位階段采用不同的距離度量、含歐氏距離度量和對數(shù)高斯距離度量進行效果對比。在該實驗中，控制其他的變量相同，如子區(qū)域數(shù)目選擇為10，區(qū)域劃分中的方格長度選擇為5 m，最后的定位精度結(jié)果如表5所示?？梢钥闯觯捎脤?shù)高斯距離的定位精度更高，其平均定位誤差和最大定位誤差分別減小了8.3%和27.4%。

表5 精定位階段不同距離度量的定位精度對比

3 結(jié)束語

本文提出了一種基于WiFi的分級定位方法。該方法分為粗定位和精定位兩個步驟。粗定位中，利用漢明距離找到人員可能的子區(qū)域，在精定位階段中利用經(jīng)典的KNN算法利用信號指紋的歐氏距離獲取人員的精確位置。實驗結(jié)果證明了該方法在子區(qū)域數(shù)目為10并且利用對數(shù)高斯距離的條件下，平均單次定位時間在KNN算法下下降了約95%，在最大后驗算法下下降了約96%，體現(xiàn)出了本文分級定位框架延遲低的優(yōu)點。

為了能夠更加充分地對本文方法進行驗證，未來工作主要分為兩個方面：一是設置更大場景、AP數(shù)目更多的實驗場景，對本文方法和其他的分級定位方法進行充分對比；二是設置多種不同的實驗場景，研究方法中不同超參數(shù)的設置對定位精度的影響。