一種基于WiFi信號特征的聚類過濾定位算法研究

蔡炯炯，沈涵生，張文輝，王子輝，袁 琳

(1.浙江科技學院 自動化與電氣工程學院，浙江 杭州 310023；2.浙江大學 電氣工程學院， 浙江 杭州 310013；3.浙江大學 蘇州工業(yè)技術(shù)研究院，江蘇 蘇州 215010)

0 引 言

隨著大型室內(nèi)車庫的增加，研究室內(nèi)車庫實時定位與引導技術(shù)，具有重大現(xiàn)實意義和較大的市場價值.WiFi技術(shù)因為基礎設施完善，普遍應用于現(xiàn)代生活中.近年來，定位在生活中廣泛應用，基于移動通信網(wǎng)定位技術(shù)的緊急救援服務[1]；通過衛(wèi)星通信定位對海洋環(huán)境的監(jiān)測[2]；針對WiFi室內(nèi)定位更多的是對定位算法的研究及改進.文獻提出一種改進的RSSI多維標度室內(nèi)定位算法，通過平面四參數(shù)模型進行坐標轉(zhuǎn)換，運用粒子優(yōu)化參數(shù)，該算法能夠滿足室內(nèi)定位跟蹤及低成本定位系統(tǒng)的需求[3]；陳斌濤等根據(jù)用戶使用狀況和定位參考點的布置情況動態(tài)更新WiFi指紋數(shù)據(jù)庫，解決了環(huán)境動態(tài)變化對信號強度值的影響[4]；鄭學理提出PDR和RSSI的室內(nèi)定位算法，該算法在在RSSI定位抗噪聲能方面，以及融合定位精度和濾波實時性方面取得良好的效果，降低定位誤差[5]；張文學在WiFi室內(nèi)指紋定位方案中根據(jù)WiFi信號強度的區(qū)間變化，提出一種指紋過濾方案，該文獻中并未考慮WiFi傳播信號強度與傳播距離之間的關系，對定位精度產(chǎn)生一定的影響[6].

綜述，文獻資料顯示更多的是采用不同的定位方法用以改善定位精度，而未改善定位速度.本文基于此方面，根據(jù)研究了信號特征變化，采用信號聚類對指紋數(shù)據(jù)庫進行指紋數(shù)據(jù)歸類劃分，確定了定位目標在一個初選區(qū)域；其次對該區(qū)域內(nèi)不同RSSI區(qū)域波動進行了對比，提出了過濾區(qū)間的自適應方法，將該過濾區(qū)間取值方法應用于多次篩選的指紋數(shù)據(jù)庫匹配算法，篩選過后指紋庫中剩下少量的數(shù)據(jù)組；最終計算采樣點與少量數(shù)據(jù)組之間的最小歐氏距離得出目標精確位置.

1 信號特征分析

由于室內(nèi)車庫環(huán)境復雜，采集RSSI信號強度時，RSSI存在不同幅度的波動.實驗中對不同RSSI均值進行多次測量后作出以下數(shù)據(jù)統(tǒng)計,分別對均值為-35 dBm、-40 dBm、-45 dBm、-50 dBm、-55 dBm、-60 dBm、-65 dBm、-70 dBm分別進行變化統(tǒng)計(見圖1)，其中，β代表信號波動幅度，α代表不同信號強度均值.

圖1 不同RSSI均值的波動幅度變化

實驗中根據(jù)大量數(shù)據(jù)統(tǒng)計得出：接收信號強度值在不同RSSI均值的波動范圍不同，具體如圖1所示.說明在不同信號強度值時，其波動范圍也是不同的，當信號強度值逐漸變小時，其波動逐漸增大.

2 信號聚類過濾算法

2.1 信號聚類過濾算法流程

基于上述信號波動規(guī)律，本文提出一種信號聚類過濾算法.算法步驟如下：第一步，信號聚類，采用距離作為相似性的評價指標，即認為兩個對象的距離越近，其相似度就越大，算法認為簇是由距離靠近的對象組成的，因此把得到緊湊且獨立的簇作為最終目標，根據(jù)采樣AP的最強信號強度和距離之間關系，本文以每個信號接入點(AP，access point)所采集的信號強度區(qū)間為(-65 dBm，-35 dBm)作為聚類中心，在該信號區(qū)間內(nèi)信號波形相對穩(wěn)定，以此劃分指紋數(shù)據(jù)庫為初選區(qū)域，進而在線定位階段減少位置指紋數(shù)據(jù)庫搜索量；第二步根據(jù)不同RSSI波動幅度在初選區(qū)域中進行指紋點多次過濾得到少量指紋數(shù)據(jù)；最終計算少量指紋點與采樣點之間的最小歐式距離，完成位置匹配，具體流程(見圖2).

圖2 信號聚類算法流程圖

2.2 信號聚類

在給出n個數(shù)據(jù)樣本中，隨機選擇K個初始聚類中心Zj，j=1,2,3,…,K.K值決定了初始質(zhì)心的數(shù)量.選擇最優(yōu)的K值沒有固定的公式或方法，需要根據(jù)實際情況決定，需要注意的是選擇較大的K值可以降低數(shù)據(jù)的誤差，但是會增加擬合的風險.

以下是不同信號強度均值的波動幅度，將K值定義為2進行聚類，并隨機選擇3和5作為兩個類別的初始質(zhì)心.

(2)求解每個數(shù)據(jù)樣本與初始類中心的距離D(xi,Z)，i=1,2,3，…，n，若滿足D(xi,Z)=min{D(xi,Z),i=1,2,…,n}，那么xi∈wk；

(4)判斷：如果|Jc(I+1)-Jc(I)|<ξ，那么表示算法結(jié)束，反之重返第(2)步驟執(zhí)行.

(5)算法終止條件：將兩組中數(shù)據(jù)的均值作為新的質(zhì)心，并重復之前的方法計算每個信號強度波動幅度到質(zhì)心的距離.

在算法開始的第一步中提到迭代計算每個數(shù)據(jù)到質(zhì)心的距離，直到新的質(zhì)心和原質(zhì)心相等，算法結(jié)束，在使用上一步分組的均值3.5和12.5作為質(zhì)心，并計算波動幅度到質(zhì)心的距離.以表1為算出的結(jié)果列表.

表1 算法終止條件

按照波動幅度到新質(zhì)心的距離進行分組，并計算每組的均值作為新質(zhì)心.這里兩組的均值新質(zhì)心與原質(zhì)心相等，則算法終止.

本文采用了聚類算法對不同信號強度值的信號波動進行分類，得到對信號波動的了分成兩類，即信號波動值在2 dBm到5 dBm范圍內(nèi)為第一類，信號波動值在12 dBm分為第二類.從信號波動幅度角度可以得出，波動范圍有大小之分，而不同波動范圍對應了不同信號強度，當波動幅度進行分類，即對應的不同信號強度值也隨之分類.信號強度值越大，其波動范圍越小，信號強度值變化相對穩(wěn)定；信號強度值越小，其波動范圍越大，信號強度值變化相對較大.

在線定位階段，本文首先隨機采樣得到六個不同信號強度值，根據(jù)信號波動進行分類，下一步根據(jù)不同信號強度的波動范圍設置過濾區(qū)間，最終完成快速定位.

2.3 自適應閾值調(diào)整

實驗中采集信號強度值時產(chǎn)生一定的波動，但波動存在一定的范圍，在該范圍內(nèi)不會出現(xiàn)偏離過大的值.實驗中大量數(shù)據(jù)分析得出：RSSI采樣值在(-65 dBm，-35 dBm)為有效區(qū)間內(nèi)，該區(qū)間內(nèi)RSSI波動相對平穩(wěn)，當RSSI值小于-65 dBm時波動幅度較大，對指紋數(shù)據(jù)庫過濾效果不佳，所以選擇(-65 dBm，-35 dBm)內(nèi)的數(shù)值作為有效信號強度值[7].

實驗中對每個采樣點(本實驗采用六個接入點，故每個采樣點可采集6個RSSI數(shù)值)中取其中最大的3個在有效區(qū)間內(nèi)的RSSI值進行過濾，接收AP信號強度的個數(shù)小于3，對定位精度有一定的影響[8].若該組有效信號強度值個數(shù)小于3，則需進行重新采樣.在一定的波動區(qū)間[RSSI-t,RSSI+t)，來找出指紋數(shù)據(jù)庫中相關性的點，其中t為波動范圍，根據(jù)不同時間段的t值變化對指紋數(shù)據(jù)庫進行過濾，t值(見表2).

表2 不同信號強度區(qū)間t取值

通過上述方法，信號過濾能夠快速得到與測試位置相關性較大的一組或者若干組的指紋數(shù)據(jù)，用這些數(shù)據(jù)輔以基本的定位算法，可以減少基本算法匹配時所需的點，同時剔除大部分與定位無關點，在保證定位精度不變的同時，減少了大量的計算過程.

2.4 自適應閾值的算法流程

(1)設置自適應過濾區(qū)間的波動范圍t值；

(2)判斷采樣點A中6個數(shù)據(jù)中是否在(-65 dBm，-35 dBm)之間，采樣值在該區(qū)間為有效值，采樣值中有效值個數(shù)小于3，則重新采樣，若6個數(shù)據(jù)中存在該區(qū)間的個數(shù)大于或等于3，則進行下一步；

(3)將A中有效值賦予R，將指紋數(shù)據(jù)庫中的對應AP維度的數(shù)據(jù)組進行過濾，過濾區(qū)間為(R-t,R+t)，過濾次數(shù)和采樣點有效值個數(shù)有關，過濾次數(shù)至少3次，最多6次；

圖3 自適應閾值的算法流程圖

(4)經(jīng)多次過濾后得出滿足條件的一組或若干組數(shù)據(jù)組；

(5)通過計算這些數(shù)據(jù)組與采樣點之間的最小歐氏距離[9]，即可得出數(shù)據(jù)庫中關系相近的匹配點.

3 實驗驗證與分析

3.1 實驗環(huán)境

在面積約為2 000 m2的室內(nèi)地下車庫環(huán)境中，完成對AP點部署及數(shù)據(jù)采樣點的規(guī)劃，另外除了參與測試的隨機移動的兩實驗人員及信號采集設備外，其它物體位置保持不變動，儀器正常運作.

(1)架設無線路由器，無線路由器統(tǒng)一架設在離地高度為2 m的掛袋中，固定放置6個編號為AP1-AP6(路由型號為TP-Link TL-WR802N外置全向天線，全向天線垂直地面放置，并設置無線路由工作于無線AP模式，命名每一個路由SSID名稱,設置路由工作于不同信道，發(fā)射統(tǒng)一穩(wěn)定功率的無線信號；

(2)建立室內(nèi)二維平面坐標系，以室內(nèi)每個車位為基點，以室內(nèi)較長的一側(cè)為坐標系X軸,另一邊為Y軸，對室內(nèi)所測范圍進行區(qū)域劃分，在室內(nèi)車庫區(qū)域x,y方向上每隔2 m進行網(wǎng)格劃分，即每4平方米為一個網(wǎng)格，以每一個網(wǎng)格的中心點作為實驗觀測采樣點;

(3)華碩F456U筆記本(Intel CORE i5處理器)內(nèi)置無線網(wǎng)卡作為無線信號接收端,為保障實驗的統(tǒng)一性,無線信號接收端的架設高度為1m,獲取無線信號強度的檢測軟件Homedale1.5對每一個無線路由所發(fā)射的無線信號的RSSI 值進行采集，測試接收端每5 s進行一次信號采集，每個采樣點采集時間為100 s,即連續(xù)采集RSSI信號20次；

(4)WiFi信號接收裝置(筆記本)放置離地高1 m左右，整個采集的過程在白天7:00到晚上11:00進行，持續(xù)測試1個月，真實有效的反應正常生活狀態(tài)下的實際測量情況.

實驗中除了隨機移動的實驗人員及信號采集設備外，其他物體位置保持不動.實驗中首先以每隔兩米劃分，即為4 m2為一個網(wǎng)格點；下一步實驗中每隔5 s采集一次RSSI值，每個采樣點采集40次；其次采用均值法完成對采樣數(shù)據(jù)的處理；最終將采樣點的位置坐標與RSSI均值一一對應，完成指紋庫的建立.

3.2 實驗過程

實驗中指紋數(shù)據(jù)[10]庫包含192個點的RSSI數(shù)據(jù)組，同時根據(jù)實驗流程圖使用C#編寫的地下車庫定位軟件，實驗中采用了6個AP并以此分為6個聚類中心，每個中心的信號強度區(qū)間為[-65 dBm，-35 dBm]，以采集的最大RSSI數(shù)值為指向.

在室內(nèi)車庫任一點采集一組RSSI值R=(-64，-70，-68，-46，-43，-50)，其中最大值為AP5=-43 dBm，可知該點指向AP5的聚類中心附近；下一步進行多次過濾，第一次過濾目的是形成一個環(huán)形初始區(qū)域，其過程由采樣點中的最大值可知該點在AP5附近，根據(jù)-43 dBm所對應的最大波動范圍是3 dBm，即在指紋庫中AP5所對應的信號區(qū)域間[-46 dBm，-40 dBm]以內(nèi)的區(qū)域作為環(huán)形初選區(qū)域，在該區(qū)域以外的將被剔除，保留環(huán)形區(qū)域內(nèi)的數(shù)據(jù).后面3個信號強度值-46 dBm，-50 dBm，-64 dBm進行3次信號過濾類似于第一步過濾方法，先確定波動幅度，再確定過濾區(qū)間，最終過濾得到指紋庫中少量數(shù)據(jù)組(見圖4).

圖4 四次過濾示意圖

根據(jù)表1中數(shù)據(jù)，對采集點A在指紋庫中設置有效信號值對應的波動范圍、過濾區(qū)間，然而此過程只能確定一個環(huán)形初選區(qū)域并不能確定采樣點的準確位置，下一步對該區(qū)域內(nèi)指紋點進行信號波動多次過濾和匹配計算，得到精確位置信息.

3.3 復雜度和運算量分析

本文采用先聚類后過濾的方法，確保在定位過程如果出現(xiàn)某個路由器的損壞，即存在有個別AP無法接收信號，不會導致整個定位系統(tǒng)失效或者癱瘓.

中本文算法相對于最近鄰算法進行了算法復雜度分析.設用于計算一次開方運算的復雜度為A，計算加減法的復雜度為M，過濾算法的復雜度為N(過濾在某種程度上復雜度可與加減運算相同)，其中A復雜度遠大于M與N.

運算次數(shù)分布(見表3)，最近鄰法執(zhí)行了193次開方運算和192次的加減法運算，即可認為復雜度K1=193×A+192M；同理可知K近鄰法(K=2)的復雜度K2=193×A+383M.本文的算法進行了337次的過濾運算和3次的加減運算，以及剩余剩下4個點進行的4次開方運算，即復雜度可認為K2=4×A+3×M+383×N，由于過濾算法與加減運算復雜度相同，下表二中對不同算法的運算次數(shù)進行統(tǒng)計.

表3 不同算法運算次數(shù)統(tǒng)計

4 結(jié) 論

本文以室內(nèi)車庫為定位為研究對象，提出了一種基于信號特征的聚類過濾算法，詳細的闡述了整個算法.

本文采用的算法在總運算次數(shù)相對最近鄰法減少了10.6%，相對于K近鄰法(K=2)減少了40.3%；開放運算復雜度遠高于加減運算，本文的算法在降低了運算總次數(shù)的同時，極大的降低了開方運算次數(shù)，即降低了運算復雜度.