周 瑞，魯 翔，李志強，武 悅，桑 楠

(電子科技大學 信息與軟件工程學院， 成都 610054)

1 引 言

定位服務給人們日常生活帶來了諸多方便.衛(wèi)星定位已能夠滿足各種室外基于位置服務的需求，而室內環(huán)境中由于衛(wèi)星信號易受遮擋且存在多徑效應，衛(wèi)星定位系統(tǒng)無法提供高精度定位服務，導致室內基于位置的服務無法獲得大規(guī)模應用.利用聲音[1]、光[2]等信號源可以實現高精度室內定位，但其信號受環(huán)境影響較大，不具有普適性.胡等[3]融合GPS與WiFi實現室內外無縫定位模型.WiFi指紋匹配是室內定位的常用方法.WiFi指紋由若干接入點(Access Point, AP)及其信號接收強度指示(Received Signal Strength Indication, RSSI)組成.通過離線建立目標定位區(qū)域的WiFi指紋地圖，采用確定性或隨機性指紋匹配算法，能夠實現離散或連續(xù)的位置估計.然而由于室內環(huán)境的復雜性以及WiFi信號的不穩(wěn)定性，WiFi指紋定位往往不夠精確，特別是大范圍應用時誤差較大.為提高大范圍定位的精度，本文采用兩級定位算法，第一級定位確定目標所在子區(qū)域，第二級定位在已確定子區(qū)域中進行精確定位.其關鍵在于：1) 如何劃分定位空間；2) 如何進行子區(qū)域確定；3) 如何在子區(qū)域內精確定位.

空間劃分的思想由Borenovic等[4]首先提出，將定位區(qū)域人工劃分成固定網格.定位時首先通過人工神經網絡(Artificial Neural Network, ANN)根據WiFi指紋確定子區(qū)域，然后在子區(qū)域內應用ANN確定精確位置.該方法人工固定劃分空間，沒有考慮WiFi信號特征，對提高定位精度貢獻不明顯.Vahidnia等[5]使用支持向量機(Support Vector Machines, SVM)對定位空間進行網格劃分，將相似WiFi指紋劃分到同一網格內.定位時首先通過SVM算法對WiFi指紋進行分類確定子區(qū)域，然后在子區(qū)域內通過ANN或貝葉斯概率模型(Bayesian Probabilistic Modeling, BPM)進行精確定位.該方法能夠提高定位精度，但實驗場景較小，測試點較少.Lee等[6]提出一種基于SVM和K-means的聚類算法(SVM-C)來劃分信號空間.定位時首先確定聚類簇，然后在該聚類簇中采用最大似然(Maximum Likelihood, ML)或核方法估計精確位置.該方法能明顯提高定位精度，但沒有對離群點進行處理.為解決空間劃分中的離群點問題，Mo等[7]提出一種在物理距離約束下進行信號指紋聚類的空間劃分聚類(Spatial Division Clustering, SDC)方法.定位時該方法使用遺傳算法和支持向量機(Genetic Algorithm and Support Vector Machine, GA-SVM)來確定子區(qū)域，然后使用加權K近鄰算法(Weighted K-Nearest Neighbors, WKNN)確定精確位置.其實驗未考慮房間，僅在走廊進行.

以上研究表明有效的空間劃分可以提高WiFi指紋定位精度[5-7].在此基礎上我們提出一種優(yōu)化的基于K-means聚類的空間劃分算法.空間劃分后實施兩級定位：第一級是粗略定位，采用SVM分類(Support Vector Classification, SVC)確定子區(qū)域；第二級是精確定位，采用SVM回歸(Support Vector Regression, SVR)確定精確位置坐標.在室內包括走廊和多個房間的較大范圍實驗中，獲得的子區(qū)域分類正確率為95.42%，平均定位誤差2.51米.本文主要貢獻包括：

1) 提出優(yōu)化K-means聚類的空間劃分算法，該算法考慮到WiFi信號的相似性和物理位置的鄰近性，能去除聚類產生的離群點，并尋找最優(yōu)聚類模型，實現最優(yōu)空間劃分；

2) 提出采用SVM分類和回歸相結合的兩級定位，一級定位采用SVM分類確定子區(qū)域，二級定位采用SVM回歸在子區(qū)域內進行精確定位，每個子區(qū)域建立各自專有的SVM回歸模型，能更精確地描述本子區(qū)域中信號和位置之間的關系；

3) 實驗證明提出的空間劃分算法優(yōu)于現有空間劃分算法(平面圖劃分法和SVM-C算法)；

4) 實驗證明提出的基于SVM分類和回歸的兩級定位算法優(yōu)于常用單級定位算法.

2 基于空間劃分的兩級定位

2.1 基本算法

基于空間劃分的兩級定位的基本流程如圖1所示，包括訓練階段和定位階段.訓練 階段采集每個參考位置點的WiFi指紋，采用優(yōu)化K-means聚類空間劃分算法，根據WiFi指紋相似性和參考點鄰近性對參考點進行聚類，每一個聚類簇形成一個子區(qū)域，從而將大的定位區(qū)域劃分成若干小的子區(qū)域，完成空間劃分.根據WiFi指紋及其對應的子區(qū)域標簽，訓練并建立子區(qū)域SVC分類模型，用于兩級定位中的第一級，即確定目標所在子區(qū)域.根據每個子區(qū)域內采集的WiFi指紋及其采樣位置坐標，針對每個子區(qū)域建立各自的SVR回歸模型，用于兩級定位中的第2級，即精確計算目標的位置坐標.定位階段分別采用SVM分類和回歸來實現兩級定位.第1級定位根據在線測得的WiFi指紋，利用訓練階段建立的子區(qū)域SVC分類模型確定目標所在子區(qū)域，第2級定位通過對應子區(qū)域的SVR回歸模型計算出目標的精確位置坐標.

圖1 基于空間劃分的兩級定位Fig.1 Two-layer localization based on space partitioning

2.2 優(yōu)化K-means聚類的空間劃分算法

空間劃分可以簡單地根據室內平面圖進行，但該方法不夠靈活，特別是在大型開放的室內空間或缺少平面圖的情況下，不能有效劃分空間區(qū)域.在局部鄰近的物理空間采集的WiFi指紋，通常在信號空間也相似.根據該原理，可以通過各參考點的信號特征相似度來劃分目標區(qū)域.K-means聚類[8,9]是一種無監(jiān)督學習算法，能夠對參考位置點的WiFi指紋進行聚類，并將聚類結果作為子區(qū)域劃分的依據.本文提出優(yōu)化的基于K-means聚類的空間劃分算法，包括三部分：

1) 由于在每個參考位置點會采集多個WiFi指紋，因此首先計算每個參考位置點的WiFi指紋均值，然后根據WiFi指紋均值對這些參考位置點進行K-means聚類，分成K個聚類簇，作為空間劃分的初步結果，K是預定義的聚類簇數；

2) 采用K-means算法在指紋信號空間聚類往往產生離群點，即一個本應屬于聚類簇i的點p被劃分到另一個聚類簇j中，因此需要對離群點進行處理，將其標記到正確的聚類簇中，即劃分到正確子區(qū)域中；

3) 提出并定義空間劃分評估函數，采用該函數評估每次空間劃分的結果，經過多次迭代后得到最優(yōu)空間劃分.

2.2.1 基于K-means聚類的空間劃分

(1)

其中l(wèi)表示信號指紋的維度，即AP的數量.通過K-means聚類進行空間劃分就是解決以下問題[8,9]：

(2)

(3)

在M步，固定γik，最小化公式(2)中的J，得到：

(4)

M步中得到的μk(k=1,2,…,K)作為新的聚類簇中心代入到E步中，迭代，直到J收斂.

2.2.2 離群點處理

采用K-means聚類算法對參考位置點的信號指紋均值聚類后，結果中存在離群點.例如圖2所示，聚類結果顯示位置點q被劃分到較遠的子區(qū)域Q里，而實際上該點在空間劃分后應屬于子區(qū)域P，那么參考位置點q就是離群點.離群點是空間劃分中的錯誤點，需要對它們進行重新標定，以獲得合理的空間劃分結果.對離群點的處理需要首先找到離群點，然后重新標定它們所屬的子區(qū)域.

1) 離群點識別：比較每個參考位置點和其鄰近的參考位置點所屬子區(qū)域.例如某一參考位置點所屬的子區(qū)域為d，其鄰近的參考位置點所屬的子區(qū)域分別為{d1,d2,…,dm}，m為鄰近參考點的數量.若所有鄰近參考位置點所屬子區(qū)域與該參考點不同，即?i,di≠d，則該參考點為離群點.

圖2 離群點處理Fig.2 Outlier removal

2) 離群點重標定：找出該離群點的鄰近參考點極大子區(qū)域，假設為dmax，將該離群點所在子區(qū)域重標定為dmax.

如圖2,三角形q為一個參考位置點，聚類后其所屬子區(qū)域為Q，而q的4個鄰居參考點{p1,p2,p3,p4}都被劃分到同一個子區(qū)域P，q是離群點，它會被重新劃分到P子區(qū)域.

2.2.3 聚類模型尋優(yōu)

由于K-means聚類算法的初始簇中心是隨機的，導致每次聚類的結果不同，空間劃分結果也不相同.為獲得最優(yōu)空間劃分結果，本文提出并定義空間劃分評估函數來評估每次K-means聚類的優(yōu)劣，迭代若干次后，尋找出最優(yōu)聚類結果，即最佳空間劃分.空間劃分評估函數f定義為：

(5)

2.3 基于SVM的兩級定位

空間劃分后，實際定位采用兩級定位方式.首先通過SVM[8,9]分類確定子區(qū)域，然后在該在區(qū)域內進行SVM回歸獲得精確位置.相對于針對整個定位區(qū)域的統(tǒng)一的回歸模型，針對每個子區(qū)域建立專有回歸模型能更加精確地表達子區(qū)域中信號指紋和位置之間的關系，因此更適合精確定位.

2.3.1 基于SVC的子區(qū)域確定

子區(qū)域確定采用分類方式，因此需要在訓練階段建立子區(qū)域分類模型.假設整個定位區(qū)域的AP集合為A={a1,a2,…,al}，l為AP數量，子區(qū)域集合為D={d1,d2,…,dK}，K表示子區(qū)域數目，一個子區(qū)域di中的AP集合可表示為Ai={ai1,ai2,…,aim}?A,m≤l，一個WiFi指紋樣本可表示為(di,(xi,xj),ri)，其中di∈D表示樣本采集位置所在的子區(qū)域，ri=(ri1,ri2,…,rij,…,rim)表示采集的信號指紋，rij表示AP集合Ai中第j個AP的RSSI值，j≤m≤l，(xi,xj)為樣本采樣位置的物理坐標.

訓練階段，采集定位區(qū)域中所有參考位置點的WiFi信號指紋并記錄其物理位置坐標.整個定位區(qū)域經過空間劃分后，分為若干各子區(qū)域，同時所有的WiFi指紋會被標記上其所屬的子區(qū)域.這時的WiFi指紋樣本集可以表示為{(di,ri)|i=1,2,…,n}，n為樣本數量.對于每個子區(qū)域的樣本，可分為兩種類型：一類是樣本采集區(qū)域屬于該子區(qū)域的樣本，標記為+1；另一類則是樣本采集區(qū)域不屬于該子區(qū)域的樣本，標記為-1.這樣，針對每一個子區(qū)域的訓練樣本集可表示為{(ci,ri)|i=1,2,…,n}，ci∈{-1,+1}.使用該樣本集，就可以訓練每個子區(qū)域的SVC分類器.

第一級定位時，根據實時采集的WiFi信號指紋，由子區(qū)域SVC分類器判定屬于哪個子區(qū)域.假設r∈Rl代表一個實時信號指紋，將其提交給所有子區(qū)域SVC分類器，如果c=+1，則r屬于該子區(qū)域，否則不屬于該子區(qū)域.

2.3.2 基于SVR的精確定位

精確定位需要確定目標的位置坐標，可以作為連續(xù)問題通過回歸來解決.本文通過SVR建立每個子區(qū)域中位置坐標與WiFi信號指紋之間的依賴關系，進行每個子區(qū)域中的精確定位.SVR建模的目標就是確定函數fx和fy，分別描述信號指紋r與位置坐標x和y之間的依賴關系.訓練每個子區(qū)域各自的SVR回歸模型時，只需要使用各子區(qū)域中的信號指紋樣本集{(dk,(xi,xj),ri|i=1,2,…,nk}，其中dk代表子區(qū)域k，nk代表該子區(qū)域的訓練樣本數量.WiFi信號指紋r與位置坐標x分量之間的函數關系fx使用樣本集{(dk,xi,ri)|i=1,2,…,nk}進行建模，而信號指紋r與位置坐標y之間的依賴關系fv使用樣本集{(dk,yi,ri)|i=1,2,…,nk}進行建模.精確定位時，將實時信號指紋r提交給所屬子區(qū)域d的x軸回歸模型fx得到目標位置的坐標x分量，同時指紋r代入所屬子區(qū)域的y軸回歸模型fy得到坐標y分量，獲得目標的精確位置(x,y).

3 實 驗

實驗環(huán)境為學校第三教學樓的二樓整層，包括多個房間和走廊，定位區(qū)域為64m×16m.實驗采用校園無線網中已經安裝部署的AP，沒有額外增加AP.實驗步驟分為數據采集、空間劃分、分類和回歸模型訓練、兩級定位四部分.數據采集階段，借助于采集軟件，實驗者采集并記錄每個參考位置點的WiFi指紋信息及其位置坐標.參考位置點共計200個，每個參考位置點采樣32次，對應4個不同方向，采樣率為1Hz.用同樣的方法采集240個測試位置點的信號指紋，每個測試位置點采樣3次，其均值作為測試樣本.參考位置點和測試位置點的詳細分布如圖3(a)和圖3(b)所示.訓練數據和測試數據的采集分別在不同時段進行，分兩天完成，總計花費約4小時.空間劃分階段，采用提出的優(yōu)化K-means聚類的空間劃分方法對圖3(a)所示的參考位置點的訓練樣本進行聚類和空間劃分，形成若干子區(qū)域.模型訓練階段，分別建立基于SVC的子區(qū)域分類模型和針對每個子區(qū)域的基于SVR的回歸模型.實時定位階段，通過訓練的的分類和回歸模型，根據實時WiFi信號指紋，分類確定子區(qū)域并在子區(qū)域內回歸確定精確位置坐標.

圖3 實驗環(huán)境Fig.3 Experimental environment

3.1 空間劃分結果

為了說明本文提出的空間劃分方法的有效性，比較了本文提出的優(yōu)化K-means聚類的空間劃分方法和其它空間劃分方法，即基于平面圖和基于SMV-C聚類的空間劃分.

室內環(huán)境中，墻體是天然的空間邊界，WiFi信號穿透它們時會有顯著衰減.通常同一房間內的信號特征具有較強相似性，而不同房間的信號特征相似性較弱.因此可根據室內建筑結構將室內空間劃分成多個子區(qū)域，如一個房間或者一段走廊代表一個子區(qū)域.這種空間劃分可根據室內平面圖來進行.該方法簡單有效，但是精確的平面圖不易獲得，導致無法進行劃分，另外對于室內較大面積的連通區(qū)域，由于缺少墻體等天然邊界，也無法進行有效空間劃分.圖4(a)是采用基于平面圖的空間劃分方法對實驗環(huán)境的空間劃分：整個定位區(qū)域被劃分為15個子區(qū)域，編號1-5和12-15按房間分為9個子區(qū)域，編號6-11按走廊分為6個子區(qū)域.

使用本文提出的優(yōu)化K-means聚類的空間劃分結果如圖4(b)所示.8個聚類簇在經過信號聚類、離散點處理和模型尋優(yōu)后得出.聚類結果根據WiFi信號相似性和物理位置鄰近性共同決定.聚類結果將整個定位區(qū)域劃分為8個子區(qū)域.在一定程度上，優(yōu)化K-means聚類的空間劃分結果和基于平面圖的空間劃分有些相似，但在門附近和走廊區(qū)域有些不同，房間和相鄰走廊常被劃分到同一個子區(qū)域.這是由于這些區(qū)域的信號相似性決定的.

作為比較，我們實現了基于SVM-C聚類的空間劃分方法[6].該方法本質上是一種改進的K-means聚類算法，但兩點之間的距離采用的是兩點各自指紋空間上的SVM超平面之間的距離，距離越小表示相似度越高.采用同一套數據集，基于SVM-C聚類的空間劃分結果如圖4(c)所示.在一定程度上，該劃分結果和平面圖也有相似之處，但是該算法有合并房間為同一子區(qū)域的情況，導致整個空間劃分不均衡.

圖4 空間劃分結果Fig.4 Results of space partitioning

3.2 定位結果

空間劃分后分別建立SVC子區(qū)域分類模型和每個子區(qū)域的SVR回歸模型.由于存在多個子區(qū)域，子區(qū)域確定是多分類問題，本文采用一對一方法來解決[10].如果有K個子區(qū)域，則需要訓練K(K-1)/2個SVC模型，因此本實驗中優(yōu)化K-means聚類的空間劃分和基于SVM-C聚類的空間劃分各需要28個SVC模型，而基于平面圖的空間劃分則需要105個SVC模型.由于位置是二維坐標，需要2K個SVR回歸模型，因此優(yōu)化K-means聚類和SVM-C聚類各需要16個SVR回歸模型，而平面圖法則需要30個SVR回歸模型.SVM算法的實現采用libSVM1，核函數選擇徑向基函數(Radical Basis Function, RBF)，SVC算法采用C-SVC[8,9]，SVR算法采用v-SVR[11].

3.2.1 子區(qū)域確定

對于提到的3種空間劃分方法，對其子區(qū)域確定和精確定位結果做了對比.評估標準包括子區(qū)域分類正確率、平均定位誤差和累計定位誤差分布.具體結果見表1.采用本文提出的優(yōu)化K-means聚類的空間劃分的子區(qū)域分類正確率達到96.67%(240個測試點中有8個分類錯誤)；使用基于SVM-C聚類的空間劃分的子區(qū)域分類正確率為92.92%，有17個測試點分類錯誤；而基于平面圖的空間劃分的分類正確率為94.85%，有13個測試點分類錯誤.從分類效果來看，本文提出的優(yōu)化K-means聚類的空間劃分算法最優(yōu).詳細分類結果如圖5所示，小圓圈代表正確分類的測試點，叉叉為錯誤分類的測試點.

圖5 子區(qū)域確定結果Fig.5 Results of subregion determination

3.2.2 精確定位

在子區(qū)域確定的基礎上，在子區(qū)域內進行位置坐標(x,y)的確定，即精確定位.本文比較了三種空間劃分方法在經過兩級定位后的平均誤差和累計誤差分布.優(yōu)化K-means聚類的空間劃分的兩級定位的平均誤差為2.51米，相比基于SVM-C聚類的空間劃分的兩級定位誤差3.02米，精度提高了16.9%，相比平面圖法的兩級定位誤差2.58米，精度提高了2.7%.詳細定位結果如圖6所示，三張圖中，箭頭尾部為目標實際位置，箭頭頭部指向估計位置.從最終定位結果看，優(yōu)化K-means聚類的空間劃分優(yōu)于基于SVM-C聚類的空間劃分和基于平面圖的空間劃分.兩級定位的平均定位誤差和定位誤差累積分布顯示在表1中.

圖6 基于空間劃分的兩級定位結果Fig.6 Two-layer localization based on space partitioning

3.2.3 兩級定位與單級定位

我們將提出的基于空間劃分和SVC-SVR的兩級定位和多種主流單級定位算法進行比較，包括SVR，近鄰算法(Nearest Neighbor, NN)和K近鄰算法(K- Nearest Neighbor, KNN).比較結果列在表2中.從表中可以看出，兩級SVC-SVR算法平均定位誤差最小，為2.51米，明顯優(yōu)于單級的SVR(3米)、NN(3.93米)和K=4時的KNN(3.57米).四種算法的累計誤差分布也顯示在表2中，兩級SVC-SVR定位算法精度最高，累積定位誤差小于1米的百分比為14.58%，小于2米的為40%，小于3米70%，小于4米85.42%，小于5米94.59%，明顯優(yōu)于SVR、NN和KNN.

表1 SVM子區(qū)域確定和定位結果Table 1 Subregion determination and localization with SVM

表2 SVC-SVR，SVR，NN和KNN定位精度對比Table 2 Comparison of SVC-SVR, SVR, NN and KNN

4 結束語

本文提出了一種基于空間劃分和支持向量機的兩級室內WiFi指紋定位算法，包括3部分：

1) 提出一種優(yōu)化的基于K-means聚類的空間劃分方法，在考慮空間特征和信號特征的情況下，對定位區(qū)域進行空間劃分產生子區(qū)域；

2) 采用SVM分類進行一級定位，確定目標所在子區(qū)域；

3) 提出采用SVR回歸進行二級定位，在子區(qū)域內進行精確定位.

實驗結果表明，由于空間劃分后針對每個子區(qū)域建立的回歸模型能夠更加精確地反映該區(qū)域內的信號特征，因此兩級定位算法的定位性能明顯優(yōu)于單級定位；本文提出的空間劃分方法同時兼顧信號特征和物理空間特征，因此定位效果優(yōu)于其它空間劃分方法.在包含多個房間和走廊的較大實際環(huán)境進行的實驗中，本算法達到96.67%的子區(qū)域分類正確率和2.51米的平均定位精度.