摘  要： 闡述了位置指紋定位算法在室內WLAN環境中的應用，分析了KNN定位算法存在的不足，提出一種模糊聚類KNN位置指紋定位算法。該算法首先選取與空間相關性較好的4個信號參數，構成多徑紋信號數據庫；然后應用主分量分析法（PCA）對原始信號數據庫作降維運算，濾除奇異性接入點（AP）；最后用模糊C均值聚類算法（FCM）處理數據，進一步濾除奇異性參考點（RP），實現提高定位算法效率與精度的目的。實驗表明，改進后的定位算法產生的定位誤差明顯減小。
關鍵詞： 位置指紋；室內定位；模糊聚類；KNN定位算法；信號數據庫

　隨著現代通信技術和網絡技術的發展，人們可攜帶計算設備的廣泛應用，以及國內城市開展無線城市試點工作，用戶可以通過計算設備隨時隨地接入互聯網，由此，基于位置的服務LBS（Location-based Services）也受到了社會越來越多的關注。與此同時，基于衛星導航定位技術的全球定位系統GPS（Global Position System）已在眾多領域得到普及。
　然而，在室內環境下，由于衛星信號被物體阻擋，無線信號不能正常傳輸，GPS的導航功能無法正常實現，且無線傳感定位系統要有專用傳感器和網絡支持，需化費較多人力和財力。因此，應用室內區域的WLAN網絡（如Wi-Fi）進行移動目標的定位管理是一個較適宜的解決方案。
1 定位算法
　基于Wi-Fi網絡的室內定位系統大多數是利用接收信號強度（RSS）的均值，其方法一般分為信號傳輸模型法和位置指紋識別法兩類。前者是利用待測點接收至少3個接入點之間的距離信息，由一定算法估計待測點的位置；后者是通過待測點多徑信號特征指紋信息與數據庫預存參考點多徑信息進行比對分析，系統需運行大量數據，用一定算法估計待測點坐標。
1.1 信號傳輸模型定位算法
　信號傳輸模型定位算法可以分為測距與定位兩個階段。首先，待測點接收來自3個不同已知位置接入點AP的信號強度值，通過中值濾波技術提取均值；然后，根據無線信號的室內傳輸損耗模型，將接收信號強度轉換為待測點與相應AP的距離；最后，應用三角形定位算法估算。
　無線信號的室內傳播模型[1，9]，一般簡化為：

　FCM算法是一個簡單的迭代與優化過程：用值在0~1間的隨機數初始化隸屬矩陣U，或初始化聚類中心，通過反復的迭代運算，逐步降低目標函數的誤差值，當目標函數值收斂時，得到最終聚類結果。該算法適合于正態分布的數據聚類，對于奇異性孤立點數據有敏感性，因此，可用于基于信號強度的定位算法。
　FCM算法因算法簡單，收斂速度快，且能處理大批量數據，解決應用性問題廣。本文應用FCM算法可以實現從待測點角度對相關數據進行有效的處理；聚類處理后可以濾除奇異性RP。聚類處理前后數據比較如圖1所示。實際上這類RP距離待測點較遠，會引起較大的定位誤差。因此，FCM算法能起到“數學聚焦”的功能，有助于提高定位精度。所謂奇異性RP是指影響定位精度較大的參考點。

2 模糊聚類KNN定位算法
2.1信號指紋數據庫
　為了克服信號強度RSS值對信道傳輸模型的依賴性，如多徑效應、墻壁阻擋和環境條件的變化等因素，提出了使用位置指紋定位算法。本文分析了信號強度各類特征參數與空間相關性的關系，認為選取4種參數構成數據庫較為合適，能更多地保留空間信道的相關信息，即信號強度的均值、中值、最大值和最小值為特征參數。
　由于室內多徑信號傳播對環境有很大的依賴性，某一位置上信道的多徑結構理論上是唯一的，終端無線信號經過反射和折射傳輸，產生與周圍環境密切相關的特定模式的多徑信號，這種多徑特征的信號可認為是某位置上的“信號紋”，因此選取網格化參考點RP，構建了多徑信號數據庫，進行離線訓練學習過程，用主分量分析法（PCA）降維和優化數據庫。由此建立了信號特征參數與空間位置的內在對應關系，為后續比對分析提供保障，并以主分量數據進行存儲，可以節省容量和提高運算效率。4×k維的多徑信號數據庫結構如圖2所示。

2.2 定位算法
2.2.1 主分量分析法PCA
　首先，從宏觀上，用主分量分析法（PCA）處理高維度數據庫，在不損失主要信息的基礎上，以低維度線性組合的數據進行運算，采用正交變換矩陣和拉格朗日乘子法[7]，根據估計坐標與參考坐標的均方差最小化原則，選取參考點RP對應的合適接入點AP和參數構成信號紋數據庫。其次，從微觀上，用模糊C均值聚類算法（FCM）處理待測點數據，通過設置相應的隸屬度和相似性的閾值，進行數學篩選；將大于隸屬度閾值及小于相似性閾值的奇異性數據識別與挖掘出來，濾除奇異性參考點RP；在數學運算上，通過模糊分類矩陣實現目標函數的最小化，以確保聚類的數據具有較好的相似性，以提高定位精度。

　在線定位階段是收集待測點在某一位置的信號特征參數，也是其收集周邊若干AP的信號及AP的宏地址，由待測點標簽再發回至定位服務器；通過模糊聚類KNN算法，將實測數據與預存數據進行對比分析，根據目標函數最小化原則，保留起主要作用的RP，提取待測點周邊的RP預存值，即確定聚類范圍；計算待測點與參考點的距離，選取相似性好的RP，即以距離為依據選取RP，從而估計待測點的實際坐標。具體步驟如圖3的下面3個方框所示。
3 定位實驗
3.1 實驗平臺
　為了評估本文定位算法的實際性能，設置的實驗環境是：警院安防科技園3樓5間100 m2的展示區，隔墻材料為輕質石膏板，層高為3.3 m。將12只定位AP均勻排列，安裝高度為2.4 m，實現Wi-Fi無線信號全覆蓋，定位主機設在第二展區內，用網線連接各AP至一臺交換機，組成定位系統局域網。網格化參考點RP間隔為2 m，呈方格排列[11]，待測點為雙向有源標簽。具體平面布局如圖4所示。

　實驗采用定位服務器配置：CPU為4核處理器，主頻2.4 GHz以上，內存為8 GB以上，硬盤為256 GB以上。數據庫服務器按以上標準另行配置。定位服務器軟件運行環境為：操作系統為Windows 2003/2008 Server 32 bit，數據庫為Microsoft SQL server 2005/2008，電子地圖采用JPG格式。定位服務器軟件實現與定位器（AP）和標簽（Tag）之間的指令，以及相關數據的交互。根據標簽發往AP的回傳信號數據，由定位算法分析標簽（測試點）與預存信息（參考點）的匹配關系，估算出標簽的實際位置。AP定位器主要指標為：2.4 GHz，IEEE802.11b/g，最高速率為54 Mb/s，天線增益2 dBi，同時掃描標簽128個/s。胸卡式標簽：2.4 GHz，速率為1 Mb/s，雙向通信，最大發射功率為20 dBm，發射間隔為1 s，48 bit唯一ID號。
3.2 實驗結果
　在定位實驗區，當處于離線訓練學習階段時，在地面打好256個網格化參考點位（即網格的交叉點上），用胸卡式標簽采集及回傳無線信號，由主機定位服務器進行處理與存儲。當在線定位階段，采用人員配帶胸卡標簽的方式進行測試，具體人數為25人，胸卡式標簽為200只。為了評估本文算法與KNN算法性能的優劣，收集標簽數量與平均定位誤差比較圖。采樣點數據是通過電子地圖上顯示待測點位置與實際標簽位置的比較計算得到的，每個點位采樣為20次，取平均值，獲得平均定位誤差數據。在采樣過程中，忽略了因人員走動時信號漂移等現象引起的明顯誤差。模糊聚類算法（改進算法）與KNN算法比較如圖5所示，可知改進算法的定位精度有比較明顯的改善，大約提高了5%左右。
　在KNN定位算法的基礎上，通過本算法可以有效地克服KNN運算中丟失位置信息的不足，從而提高定位算法的定位精度。實驗表明，當室內人員較多且人員快速移動時，還會出現無線信號的漂移和時延顯示等現象；這一類信號傳輸問題有待于今后進一步優化定位算法，實現能自適應物理環境變化的定位算法。
參考文獻
[1] 唐文勝，李姍，匡旺秋.RF室內定位指紋庫空間相關生成算法[J].計算機工程與應用，2008，44（23）：226-229.
[2] 盧恒惠，劉興川，張超，等.基于三角形與位置指紋識別算法的WiFi定位比較[J].移動通信，2010（10）：72-76.
[3] 湯麗，徐玉濱，周牧，等.基于K近鄰算法的WLAN室內定位技術研究[J].計算機科學，2009，36（4B）：54-55，92.
[4] 劉興川，林孝康.基于聚類的快速Wi-Fi定位算法[J].計算機工程，2011，37（8）：285-287.
[5] 李文杰，李文明.基于K-近鄰算法的定位方法設計和仿真[J].計算機仿真，2009，26（4）：194-196.
[6] 潘玉奇，周勁，楊秀麗.基于模糊聚類分析的數據檢索的應用[J].微電子學與計算機，2005，22（6）：167-172.
[7] Zhou Mu， Xu Yubin， Ma Lin. Radio-map establishment based on Fuzzy clustering for WLAN hybrid KNN/ANN indoor positioning[J]. China Communications，2010（7）：64-79.
[8] Yang Qiang， PAN S J， ZHENG V W. Estimating location using Wi-Fi[J]. IEEE Intelligent Systems， 2008，23（1）：8-13.
[9] 戴立偉，李向陽，程赟.無線傳感器網絡的RSSI定位技術研究[J].計算機工程與設計，2009，30（19）：4395-4397.
[10] TRAN Q， TANTRA J W， FOH C H， et al. Wireless indoor positioning system with enhanced nearest neighbors in signal space algorithm[C]. IEEE 64th Vehicular Technology Conference，2006：1-5.
[11] 李昊.位置指紋定位技術[J].山西電子技術，2007（5）：84-87.