基于WiFi的分級室內定位*

王行娟

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

0 引 言

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

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

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

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

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

1 方法步驟

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

圖1 WiFi分級室內定位結構

1.1 粗定位

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

圖2 粗定位中的分區過程示意圖

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

(1)

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

(2)

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

(3)

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

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

在本文的應用中手動劃分子區域的計算量可以看作是預處理過程，在建立信號指紋數據庫后計算單次即可。在子區域數目增多時，由于粗定位中漢明距離匹配計算速度更快，并且不需要在預處理后再進行RSS維度的對齊，因此粗定位所需的復雜度在縱向對比上雖然會提高，但是相比于傳統方法橫向對比仍然具有優勢。

1.2 精定位

假設在粗定位的過程中找到M個可能的子區域，這些子區域包含了人員可能存在的位置。假設在這些子區域內的信號指紋可以表示為{RSS1:N}，其中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 根據如下的公式計算兩個信號強度向量的距離：

(8)

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

(9)

(10)

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

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

1.3 復雜度分析

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

2 實驗與分析

2.1 實驗場景設置

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

圖3 錄取指紋地圖示意圖

表1 實驗場景參數

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

2.2 方法超參數確定

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

圖4 本文方法子區域數目與經典的KNN算法的定位誤差積累誤差密度分布函數比較

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

表2 不同子區域的數目對應的定位精度

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

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

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

2.3 方法對比

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

表4 不同方法平均誤差和單次定位時間統計

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

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

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

3 結束語

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

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