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

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

0 引 言

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

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

1 信號(hào)特征分析

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

圖1 不同RSSI均值的波動(dòng)幅度變化

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

2 信號(hào)聚類過濾算法

2.1 信號(hào)聚類過濾算法流程

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

圖2 信號(hào)聚類算法流程圖

2.2 信號(hào)聚類

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

以下是不同信號(hào)強(qiáng)度均值的波動(dòng)幅度，將K值定義為2進(jìn)行聚類，并隨機(jī)選擇3和5作為兩個(gè)類別的初始質(zhì)心.

(2)求解每個(gè)數(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ì)心，并重復(fù)之前的方法計(jì)算每個(gè)信號(hào)強(qiáng)度波動(dòng)幅度到質(zhì)心的距離.

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

表1 算法終止條件

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

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

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

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

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

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

表2 不同信號(hào)強(qiáng)度區(qū)間t取值

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

2.4 自適應(yīng)閾值的算法流程

(1)設(shè)置自適應(yīng)過濾區(qū)間的波動(dòng)范圍t值；

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

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

圖3 自適應(yīng)閾值的算法流程圖

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

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

3 實(shí)驗(yàn)驗(yàn)證與分析

3.1 實(shí)驗(yàn)環(huán)境

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

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

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

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

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

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

3.2 實(shí)驗(yàn)過程

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

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

圖4 四次過濾示意圖

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

3.3 復(fù)雜度和運(yùn)算量分析

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

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

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

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

4 結(jié) 論

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

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