摘  要： 闡述了位置指紋定位算法在室內(nèi)WLAN環(huán)境中的應(yīng)用,，分析了KNN定位算法存在的不足,，提出一種模糊聚類KNN位置指紋定位算法。該算法首先選取與空間相關(guān)性較好的4個(gè)信號(hào)參數(shù),，構(gòu)成多徑紋信號(hào)數(shù)據(jù)庫(kù),；然后應(yīng)用主分量分析法（PCA）對(duì)原始信號(hào)數(shù)據(jù)庫(kù)作降維運(yùn)算，濾除奇異性接入點(diǎn)（AP）；最后用模糊C均值聚類算法（FCM）處理數(shù)據(jù),，進(jìn)一步濾除奇異性參考點(diǎn)（RP）,，實(shí)現(xiàn)提高定位算法效率與精度的目的。實(shí)驗(yàn)表明,，改進(jìn)后的定位算法產(chǎn)生的定位誤差明顯減小,。
關(guān)鍵詞： 位置指紋；室內(nèi)定位,；模糊聚類,；KNN定位算法；信號(hào)數(shù)據(jù)庫(kù)

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

　FCM算法是一個(gè)簡(jiǎn)單的迭代與優(yōu)化過(guò)程：用值在0~1間的隨機(jī)數(shù)初始化隸屬矩陣U,，或初始化聚類中心，通過(guò)反復(fù)的迭代運(yùn)算,，逐步降低目標(biāo)函數(shù)的誤差值,，當(dāng)目標(biāo)函數(shù)值收斂時(shí)，得到最終聚類結(jié)果,。該算法適合于正態(tài)分布的數(shù)據(jù)聚類,，對(duì)于奇異性孤立點(diǎn)數(shù)據(jù)有敏感性，因此,，可用于基于信號(hào)強(qiáng)度的定位算法,。
　FCM算法因算法簡(jiǎn)單，收斂速度快,，且能處理大批量數(shù)據(jù),，解決應(yīng)用性問(wèn)題廣。本文應(yīng)用FCM算法可以實(shí)現(xiàn)從待測(cè)點(diǎn)角度對(duì)相關(guān)數(shù)據(jù)進(jìn)行有效的處理,；聚類處理后可以濾除奇異性RP,。聚類處理前后數(shù)據(jù)比較如圖1所示,。實(shí)際上這類RP距離待測(cè)點(diǎn)較遠(yuǎn),，會(huì)引起較大的定位誤差。因此,，F(xiàn)CM算法能起到“數(shù)學(xué)聚焦”的功能,，有助于提高定位精度。所謂奇異性RP是指影響定位精度較大的參考點(diǎn),。

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

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

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

　實(shí)驗(yàn)采用定位服務(wù)器配置：CPU為4核處理器,，主頻2.4 GHz以上，內(nèi)存為8 GB以上,，硬盤為256 GB以上,。數(shù)據(jù)庫(kù)服務(wù)器按以上標(biāo)準(zhǔn)另行配置。定位服務(wù)器軟件運(yùn)行環(huán)境為：操作系統(tǒng)為Windows 2003/2008 Server 32 bit,，數(shù)據(jù)庫(kù)為Microsoft SQL server 2005/2008,，電子地圖采用JPG格式,。定位服務(wù)器軟件實(shí)現(xiàn)與定位器（AP）和標(biāo)簽（Tag）之間的指令,，以及相關(guān)數(shù)據(jù)的交互。根據(jù)標(biāo)簽發(fā)往AP的回傳信號(hào)數(shù)據(jù),，由定位算法分析標(biāo)簽（測(cè)試點(diǎn)）與預(yù)存信息（參考點(diǎn)）的匹配關(guān)系,，估算出標(biāo)簽的實(shí)際位置。AP定位器主要指標(biāo)為：2.4 GHz,，IEEE802.11b/g,，最高速率為54 Mb/s，天線增益2 dBi,，同時(shí)掃描標(biāo)簽128個(gè)/s,。胸卡式標(biāo)簽：2.4 GHz,，速率為1 Mb/s，雙向通信,，最大發(fā)射功率為20 dBm,，發(fā)射間隔為1 s，48 bit唯一ID號(hào),。
3.2 實(shí)驗(yàn)結(jié)果
　在定位實(shí)驗(yàn)區(qū),，當(dāng)處于離線訓(xùn)練學(xué)習(xí)階段時(shí)，在地面打好256個(gè)網(wǎng)格化參考點(diǎn)位（即網(wǎng)格的交叉點(diǎn)上）,，用胸卡式標(biāo)簽采集及回傳無(wú)線信號(hào),，由主機(jī)定位服務(wù)器進(jìn)行處理與存儲(chǔ)。當(dāng)在線定位階段,，采用人員配帶胸卡標(biāo)簽的方式進(jìn)行測(cè)試,，具體人數(shù)為25人，胸卡式標(biāo)簽為200只,。為了評(píng)估本文算法與KNN算法性能的優(yōu)劣,，收集標(biāo)簽數(shù)量與平均定位誤差比較圖。采樣點(diǎn)數(shù)據(jù)是通過(guò)電子地圖上顯示待測(cè)點(diǎn)位置與實(shí)際標(biāo)簽位置的比較計(jì)算得到的,，每個(gè)點(diǎn)位采樣為20次,，取平均值，獲得平均定位誤差數(shù)據(jù),。在采樣過(guò)程中,，忽略了因人員走動(dòng)時(shí)信號(hào)漂移等現(xiàn)象引起的明顯誤差。模糊聚類算法（改進(jìn)算法）與KNN算法比較如圖5所示,，可知改進(jìn)算法的定位精度有比較明顯的改善,，大約提高了5%左右。
　在KNN定位算法的基礎(chǔ)上,，通過(guò)本算法可以有效地克服KNN運(yùn)算中丟失位置信息的不足,，從而提高定位算法的定位精度。實(shí)驗(yàn)表明,，當(dāng)室內(nèi)人員較多且人員快速移動(dòng)時(shí),，還會(huì)出現(xiàn)無(wú)線信號(hào)的漂移和時(shí)延顯示等現(xiàn)象；這一類信號(hào)傳輸問(wèn)題有待于今后進(jìn)一步優(yōu)化定位算法,，實(shí)現(xiàn)能自適應(yīng)物理環(huán)境變化的定位算法,。
參考文獻(xiàn)
[1] 唐文勝，李?yuàn)?，匡旺?RF室內(nèi)定位指紋庫(kù)空間相關(guān)生成算法[J].計(jì)算機(jī)工程與應(yīng)用,，2008，44（23）：226-229.
[2] 盧恒惠,，劉興川,，張超,，等.基于三角形與位置指紋識(shí)別算法的WiFi定位比較[J].移動(dòng)通信，2010（10）：72-76.
[3] 湯麗,，徐玉濱,，周牧，等.基于K近鄰算法的WLAN室內(nèi)定位技術(shù)研究[J].計(jì)算機(jī)科學(xué),，2009,，36（4B）：54-55，92.
[4] 劉興川,，林孝康.基于聚類的快速Wi-Fi定位算法[J].計(jì)算機(jī)工程,，2011，37（8）：285-287.
[5] 李文杰,，李文明.基于K-近鄰算法的定位方法設(shè)計(jì)和仿真[J].計(jì)算機(jī)仿真,，2009，26（4）：194-196.
[6] 潘玉奇,，周勁,，楊秀麗.基于模糊聚類分析的數(shù)據(jù)檢索的應(yīng)用[J].微電子學(xué)與計(jì)算機(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] 戴立偉，李向陽(yáng),，程赟.無(wú)線傳感器網(wǎng)絡(luò)的RSSI定位技術(shù)研究[J].計(jì)算機(jī)工程與設(shè)計(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] 李昊.位置指紋定位技術(shù)[J].山西電子技術(shù),，2007（5）：84-87.