融合差分改正的RSSI指紋庫室內(nèi)定位研究

張愛國，鄔群勇，孫海信，韓李濤，林聰仁

(1.廈門理工學(xué)院 計算機(jī)與信息工程學(xué)院，福建 廈門 361024； 2.福州大學(xué) 數(shù)字中國研究院(福建)，福建 福州 350003；3.廈門大學(xué) 信息科學(xué)與技術(shù)學(xué)院，福建 廈門 361002； 4.山東科技大學(xué) 測繪科學(xué)與工程學(xué)院，山東 青島 266590)

近年來，室內(nèi)位置服務(wù)需求不斷增長，催生了定位技術(shù)的不斷發(fā)展[1-2]。室內(nèi)復(fù)雜的環(huán)境給定位帶來了困難，使定位精度也遠(yuǎn)遜于室外的全球衛(wèi)星導(dǎo)航系統(tǒng)(global navigation satellite system,GNSS)。目前廣泛應(yīng)用的室內(nèi)定位系統(tǒng)主要有：基站定位、偽衛(wèi)星定位、指紋定位、UWB(ultra wide band，超寬帶)定位、地磁定位、視覺定位、機(jī)會信號定位、組合定位、協(xié)同定位和導(dǎo)航通訊一體化定位等[3-4]，這些定位各具優(yōu)點，共同為基于位置的服務(wù)提供了定位基礎(chǔ)。

為消除定位誤差，特別是RSSI(received signal strength indicator，接收信號強(qiáng)度指示)指紋庫室內(nèi)定位中的誤差，常見的兩類消除誤差途徑為指紋庫濾波[5-6]和實時RSSI向量值的差分改正[7]。

為確立RSSI位置指紋定位技術(shù)中定位誤差與主要影響參數(shù)的關(guān)系，容曉峰等[8]提出了表示定位平均誤差的數(shù)學(xué)模型，通過計算整個定位區(qū)域誤差的期望，公式化地表示了接入點個數(shù)、接入點擺放位置、采樣點間距、最鄰近點個數(shù)各因素取值不同對定位精度的影響。

為抑制RSSI 誤差對無線傳感器節(jié)點自身定位精度的影響，許多學(xué)者以RSSI測距及三邊定位算法為基礎(chǔ)，提出多種基于RSSI測距誤差修正的差分定位算法[9-10]。任維政等[11]在不增加節(jié)點硬件設(shè)計的情況下，通過RSSI的測量得到節(jié)點距離相關(guān)信息，以三邊測量定位算法為理論基礎(chǔ)，提出了基于RSSI的無線傳感器網(wǎng)絡(luò)距離差分修正定位算法?；赗SSI的指紋庫定位是目前廣為使用的室內(nèi)定位方法[12]，祝正元等[13]為消除指紋庫定位中不同終端之間在相同位置接收到相同接入點的RSSI信號值誤差，提出采用差分信號強(qiáng)度作為數(shù)據(jù)庫指紋計算定位結(jié)果，該方法在差分非采樣終端取得了一定的效果，但只是優(yōu)化和調(diào)整了指紋庫，并沒有校正實時定位過程中的RSSI誤差。

圖1 融合差分改正的RSSI指紋庫定位原理圖

室外GNSS定位與室內(nèi)RSSI定位過程均受到信號傳播過程中的環(huán)境因素影響。為此，基于RSSI指紋庫的室內(nèi)定位可參考GNSS RTK的差分改正思想[14-15]來消除公共誤差，即融合差分改正的RSSI指紋庫室內(nèi)定位。

如圖1所示，融合差分改正的RSSI指紋庫定位技術(shù)是在定位區(qū)域選擇參考點，根據(jù)參考點已知坐標(biāo)，計算出參考點的坐標(biāo)改正數(shù)或RSSI向量元素改正數(shù)，并由參考點實時將這一改正數(shù)發(fā)送出去。流動站在進(jìn)行指紋定位的同時，也接收到參考點的改正數(shù)，并對其定位結(jié)果進(jìn)行改正，從而提高定位精度。

GNSS定位屬于測距后方定位，而RSSI指紋庫定位為信號特征定位，這兩種方法的定位原理完全不同。在借鑒GNSS RTK差分定位過程中，還需要解決參考點的選擇、基于RSSI的差分改正數(shù)計算等問題。

1 基于泰森多邊形的參考點選擇

根據(jù)路徑因素對誤差影響的相關(guān)性，距離近則相關(guān)性強(qiáng)，所以盡量選擇距離待定點較近的參考點參與每次的誤差改正數(shù)計算。同時，RSSI 越大的參考點，對待定點位置的影響力越大，對待定點位置有更大的決定權(quán)。氣候?qū)W家Thiessen[16]為計算離散分布?xì)庀笳镜钠骄涤炅克岢龅奶┥噙呅慰捎糜诮鉀Q最近點、最小封閉圓以及許多空間分析問題。為此，基于泰森多邊形能夠選擇出兼容數(shù)量[17-18]且距離合理的參考點。

通過泰森多邊形的構(gòu)建，定位區(qū)域被分割成大小不等的多邊形，它們之間具有明確的鄰接性，便于可達(dá)性分析。為此，給定任意一個初始點，首先判斷其與泰森多邊形之間的所屬關(guān)系。只要能夠確定初始點包含于某個多邊形，則利用泰森多邊形之間的鄰接關(guān)系，就能夠找到所有的鄰接多邊形，多邊形內(nèi)的原始三角點即為要選擇的定位參考點。

圖2 基于泰森多邊形的參考點選擇

如圖2所示的泰森多邊形網(wǎng)中有參考點A、B、C、D、E、F、G、H、J、K、L、M、O……，并且P為初始定位點，其所在的泰森多邊形的外接圓圓心為O，將其作為本次定位的最近參考點。同時，該多邊形有5條邊，也即對應(yīng)有5個外接泰森多邊形，它們的外接圓圓心按順時針方向分別為A、B、C、F、G、H，這些點將作為本次定位的較近參考點。不同的最近參考點對應(yīng)的泰森多邊形可能具有不同數(shù)量的外接多邊形，比如圖2中的參考點H所在的泰森多邊形具有6條邊，因此有6個較近的周邊參考點A、O、G、J、K、L。

通常情況下，初始點包含于泰森多邊形之內(nèi)，但也會出現(xiàn)另外兩種特殊情況：一是初始點落在兩個相鄰泰森多邊形的公共邊上；二是初始點位于三個及以上的相鄰泰森多邊形的交點上。在處理這些情況時，須堅持信息不遺漏原則，將盡量多的參考點用于改正數(shù)的計算。對第一種情況，選擇包含公共邊的兩個泰森多邊形為核心多邊形，然后查找與其鄰接的所有外接多邊形。此時最近參考點有兩個，鄰近參考點為兩個泰森多邊形的所有鄰接多邊形的外接圓圓心。同理，對于第二種情況，此時的核心多邊形為包含該點的所有泰森多邊形，其外接圓圓心為最近參考點，相應(yīng)地，這些泰森多邊形的所有鄰接多邊形的外接圓圓心作為鄰接參考點。

2 誤差改正數(shù)計算

在定位過程中，首先進(jìn)行初始定位，即未經(jīng)過參考點改正。由該初始定位結(jié)果根據(jù)包含關(guān)系確定其所在的泰森多邊形區(qū)域，將得到該多邊形的中心作為最近的參考點。然后，以此多邊形為核心，通過其每條邊外接的所有多邊形，找到所有外接多邊形的中心，這些中心所對應(yīng)的參考點為距離最近參考點的鄰接參考點。

選擇參考點的目的是計算誤差改正數(shù)，在基于RSSI的指紋庫定位中，由初始點出發(fā)，經(jīng)實時RSSI向量與指紋庫向量的匹配計算等一系列過程，得到待定點的最終坐標(biāo)。為此，差分改正數(shù)可出現(xiàn)在不同的環(huán)節(jié)，也相應(yīng)地得到不同的定位結(jié)果。本研究分設(shè)計坐標(biāo)改正數(shù)與RSSI向量元素改正數(shù)兩種情況予以敘述。

2.1 坐標(biāo)改正數(shù)

對最后的定位坐標(biāo)進(jìn)行改正，此時為坐標(biāo)改正數(shù)計算。坐標(biāo)改正數(shù)將依據(jù)初始定位結(jié)果所選擇到的所有最近參考點和鄰接參考點來求取。對于每一個參考點而言，其位置坐標(biāo)都是已知的，同時，在參考點上的無線設(shè)備也可實時采集RSSI信息。為此，參考點位置利用RSSI實時數(shù)據(jù)的指紋匹配方法同樣可得到實時定位坐標(biāo)結(jié)果，只是該結(jié)果必定含有路徑誤差。那么，運(yùn)用參考點含有誤差的實時定位結(jié)果減去該點的已知坐標(biāo)，即可得到參考點對應(yīng)的誤差改正數(shù)。坐標(biāo)改正數(shù)的計算過程中，根據(jù)每個參考點實時RSSI向量，運(yùn)用RSSI指紋庫定位法，得到其定位結(jié)果，并將其已知結(jié)果比較，求得誤差，然后取誤差的平均值作為最后的坐標(biāo)誤差改正數(shù)，每個初始定位結(jié)果的坐標(biāo)改正數(shù)計算公式如(1)。

(1)

其中，n為參考點的個數(shù)，x′i為第i個參考點的RSSI指紋向量定位結(jié)果，xi為第i個參考點已知坐標(biāo)結(jié)果，ex、ey為待定點坐標(biāo)改正數(shù)。

2.2 RSSI向量元素改正數(shù)計算

圖3 差分修正定位算法示意圖

除了從整體上改正定位結(jié)果的坐標(biāo)，還可以從底層改正實時RSSI向量元素。每個RSSI向量對應(yīng)點位置由無線AP數(shù)量相等的RSSI值構(gòu)成。

如圖3所示，參考點為N1(RSSI1,RSSI2,…,RSSIm),N2(RSSI1,RSSI2, …,RSSIm),N3(RSSI1,RSSI2, …,RSSIm),Q1(RSSI1,RSSI2, …,RSSIm),Q2(RSSI1,RSSI2, …,RSSIm),…,Q5(RSSI1,RSSI2, …,RSSIm)，待定點O。N1、N2、N3是離待定點O最近的參考點，參考點N1到參考點Q1,Q2, …,Q5的距離分別為d11,d12, …,d15；待定點O到參考點Q1,Q2, …,Q5的測量距離分別為d1,d2, …,d5。RSSI向量元素改正數(shù)依據(jù)外部環(huán)境對每個無線AP信號影響大小的不同，從細(xì)節(jié)層次上采取不同的實時RSSI向量元素值進(jìn)行改正。

定義1由RSSI向量表示的A、B兩點之間距離RD計算公式為：

(2)

其中，RSSIA1為A點RSSI向量的第1個元素，RSSIB1為B點RSSI向量的第1個元素，RSSIA2為A點RSSI向量的第2個元素，RSSIB2為B點RSSI向量的第2個元素，以此類推，m為向量元素個數(shù)。

定義2RSSI 向量元素差分修正系數(shù)

(3)

其中，RD′ij為第i個最近參考點到第j個鄰近參考點的測量距離，RDij為第i個最近參考點到第j個鄰近參考點的已知距離，λ為調(diào)節(jié)系數(shù)，n為對應(yīng)最近參考點的鄰近參考點個數(shù)，k為最近參考點個數(shù)。

定義3待定點的RSSI向量元素差分改正方程為：

RSSIt=RSSI′t-α(RSSI′i-RSSI′it)，i=1,2,…,m。

(4)

其中，RSSIi為待定點RSSI向量中的第i個元素的修正值，RSSI′i為待定點RSSI向量中的第i個元素的觀測值，RSSI′it為k個最近參考點第t個元素的測量平均值，m為參與定位的參考點個數(shù)。

3 融合差分改正的RSSI指紋庫定位

在定位區(qū)域設(shè)置好參考點，并運(yùn)用第1部分介紹的方法選擇參考點之后，配合第2部分的兩類誤差改正數(shù)計算方法，為融合差分改正的RSSI指紋庫定位提供了算法基礎(chǔ)。依據(jù)誤差改正數(shù)的生成類型，其定位方式也分為基于坐標(biāo)改正數(shù)的定位和基于RSSI向量元素改正數(shù)的定位，下面分別予以介紹。

3.1 基于坐標(biāo)改正數(shù)的定位

基于坐標(biāo)改正數(shù)的定位思路簡單，易于理解。其核心思想是用初始定位坐標(biāo)結(jié)果減去坐標(biāo)改正數(shù)，同時，該坐標(biāo)改正數(shù)依據(jù)初始定位結(jié)果所選定的參考點綜合確定?；谧鴺?biāo)改正數(shù)的定位流程如圖4所示。

圖4 基于坐標(biāo)改正數(shù)的定位流程

首先獲得終端的實時RSSI向量數(shù)據(jù)，并對該數(shù)據(jù)運(yùn)用指紋庫進(jìn)行定位，得到初始定位結(jié)果。配合泰森多邊形網(wǎng)和地理空間的拓?fù)浞治龇椒?，找到包含該初始定位結(jié)果的泰森多邊形以及與該多邊形相鄰的所有鄰接泰森多邊形。選擇這些泰森多邊形的外接圓圓心作為參考點計算坐標(biāo)的差分改正數(shù)。由于所有參考點都是固定在定位區(qū)域的某個位置，可以隨時接收無線定位信息。這些接收到的參考點實時無線RSSI向量數(shù)據(jù)運(yùn)用指紋庫進(jìn)行定位，得到參考點含有誤差的坐標(biāo)定位結(jié)果。由于參考點的位置固定，即其坐標(biāo)為已知的值，為此，每個參考點含有誤差的定位結(jié)果減去其相應(yīng)的已知值，得到參考點的誤差改正數(shù)。然后，求取這些選擇參考點的誤差改正數(shù)平均值，作為待定點的坐標(biāo)誤差改正數(shù)用于修正初始定位值，即得到待定點剔除誤差后的最終結(jié)果。

3.2 基于RSSI向量元素改正數(shù)的定位

基于RSSI向量元素改正數(shù)的定位流程與基于坐標(biāo)改正數(shù)的定位相比，在參考點的選擇以前的部分完全相同，只是在參考點之后的改正數(shù)計算方法和途徑有明顯差異，如圖5所示。

圖5 基于RSSI向量元素改正數(shù)的定位流程

同樣地，從終端實時RSSI數(shù)據(jù)出發(fā)，可以得到包含初始定位結(jié)果的一個或多個最近參考點，進(jìn)而獲得所有鄰接參考點。由第2部分中的RSSI向量元素改正數(shù)計算公式，得出對應(yīng)初始點的改正系數(shù)進(jìn)而得到每個無線AP對應(yīng)的RSSI值差分改正數(shù)，再分別對RSSI向量元素進(jìn)行實時修正，得到新的RSSI向量數(shù)據(jù)。最后，重新運(yùn)用指紋庫定位方法，對終端再次定位，得到最終定位結(jié)果。

4 實驗及分析

采集某校體育館數(shù)據(jù)建立RSSI指紋庫，在Eclipse編程環(huán)境下，運(yùn)用Java+PostgreSQL+PostGIS+Mybatis開發(fā)工具制作算法程序，實驗驗證了提出的融合差分改正的RSSI指紋庫定位算法的可行性和準(zhǔn)確率。

4.1 實驗場景及數(shù)據(jù)準(zhǔn)備

實驗場景設(shè)置了如圖6所示的36個參考點，其坐標(biāo)如表1所示，然后，采用QGIS軟件的QGIS geo-algorithms-Vector geometry tools-Voronoi polygons功能構(gòu)建的泰森多邊形如圖6所示。

表1 參考點坐標(biāo)表

圖6 參考點的泰森多邊形

為了能夠快速有效地對這些泰森多邊形進(jìn)行空間關(guān)系計算，將圖6中的參考點和多邊形均作為空間對象存儲于PostgreSQL/PostGIS中，其存儲效果如圖7所示，st、astext字段為泰森多邊形幾何對象。

4.2 實驗過程

給定實時RSSI向量數(shù)據(jù)(-54,-54,-77,-53,-59,-61,-65,-65,-65,-66,-66,-63,-76,-76,-51,-54,-72,-62,-54)，運(yùn)用張愛國等[19]提出的方法得到其初始定位結(jié)果為(5, 6)。從空間數(shù)據(jù)關(guān)系操作到差分改正數(shù)計算的整個實驗過程為：

1) 根據(jù)PostGIS的空間拓?fù)浒P(guān)系函數(shù)st.contains(Geometry,point)，給定初始定位結(jié)果(5，6)，得到包含該點的泰森多邊形對應(yīng)的id為12。

圖7 泰森多邊形在PostGIS中的幾何對象存儲

2) 運(yùn)用PostGIS的空間拓?fù)溧徑雨P(guān)系函數(shù)st-intersects(Geometry,Geometry)，確定與id為12的泰森多邊形相鄰接的多邊形id集合{11，12，14，16，21，24，26，32，36}。

3) 運(yùn)用PostGIS的空間拓?fù)渌鶎訇P(guān)系函數(shù)st-within(Geometry,Geometry),獲得2)中相鄰接多邊形對應(yīng)的參考點id集合{24，12，11，4，1，19，14，20，7}。

4) 坐標(biāo)改正數(shù)計算

在Eclipse編程環(huán)境下，開發(fā)Java功能類，實現(xiàn)坐標(biāo)改正數(shù)的計算。

空間數(shù)據(jù)表設(shè)計：數(shù)據(jù)表的字段結(jié)構(gòu)如表2。

表2 空間數(shù)據(jù)表結(jié)構(gòu)設(shè)計

在QGIS軟件中，用labels功能找到參考點與對應(yīng)id的多邊形，然后，把各自的參考點與多邊形原始數(shù)據(jù)合成一個包含參考點和多邊形的空間數(shù)據(jù)文件。最后，采用插入方式得到該數(shù)據(jù)表數(shù)據(jù)。

5) RSSI向量元素改正數(shù)計算

在坐標(biāo)改正數(shù)的基礎(chǔ)上，添加了RSSI向量元素改正系數(shù)的計算，通過逐次定位改正每個元素的值。

4.3 實驗效果及分析

為了體現(xiàn)本算法的定位效果，運(yùn)用如下方法，在已有實測420條指紋數(shù)據(jù)基礎(chǔ)上，構(gòu)建了21 000條實時指紋數(shù)據(jù)。

根據(jù)實時指紋數(shù)據(jù)主要受距離遠(yuǎn)近和其他綜合因素的影響，即距離影響誤差的大小，距離越遠(yuǎn)RSSI值越不穩(wěn)定。為此，實時RSSI數(shù)據(jù)由指紋庫中RSSI數(shù)據(jù)+距離d+正態(tài)分布隨機(jī)數(shù)δ，該實時RSSI數(shù)據(jù)

RSSIrealtime=RSSIfingerprint+λD+δ，

(5)

其中，距離D=10|RSSI-RSSI0|/(10×n)。

RSSI0為1 m處的信號強(qiáng)度，取值為-37 db，n為路徑損耗指數(shù)，取值3。

正態(tài)分布隨機(jī)數(shù)δ表示綜合因素的影響，δ服從正態(tài)分布N(μ,σ2)，本實驗取值μ=0、σ=1.0。將實時數(shù)據(jù)代入系統(tǒng)運(yùn)算，運(yùn)行硬件為DELL Inspiron137000 Series筆記本電腦，軟件環(huán)境為Linux+Eclipse+PostgreSQL/PostGIS+Mybatis。在選定5個參考點的情況下，坐標(biāo)改正數(shù)計算耗時0.282 s，RSSI向量元素改正數(shù)計算耗時0.083 s。同時，本算法與WKNN算法的運(yùn)行結(jié)果對比如表3所示。

基于Wi-Fi RSSI指紋庫的室內(nèi)定位算法時間復(fù)雜度為O(6mn+6n2)，WKNN的時間復(fù)雜度為O(6mn+6n2+3k+1)[20]，其中m表示RSSI元素個數(shù)，n表示區(qū)域網(wǎng)格個數(shù)，k表示W(wǎng)KNN中取的k個最小樣值。本定位算法相對于初始的指紋庫而言，坐標(biāo)差分方法增加了參考點的定位，向量元素差分方法在坐標(biāo)差分的基礎(chǔ)上增加了每個元素的計算，為此，坐標(biāo)差分方法的時間復(fù)雜度為O((6mn+6n2)×r)，向量元素差分方法的時間復(fù)雜度為O((6mn+6n2)×r+m)，其中r表示每次定位泰森多邊形確定的參考點個數(shù)。本實驗各參數(shù)取值情況為m=20、n=420、k=4、r≈6。從表3可以看出，本算法在耗時方面，向量元素差分>坐標(biāo)差分>WKNN，這是由于差分改正需要泰森多邊形的判定操作所致。另外，基于向量元素的改正計算公式相比坐標(biāo)改正復(fù)雜，所以耗時也有少量增加。在算法的定位準(zhǔn)確率上，基于坐標(biāo)或向量元素的改正WKNN算法均有一定的提高。

表3 定位實驗效果表

5 結(jié)論

在基于RSSI的指紋庫室內(nèi)定位中，由于信號傳播等環(huán)境因素的影響，造成實時RSSI向量數(shù)據(jù)的不穩(wěn)定，從而降低了指紋庫的定位精度。依據(jù)在定位區(qū)域中實時RSSI傳播的地理相關(guān)性，提出融合差分定位的RSSI指紋庫定位方法。設(shè)計了基于鄰接泰森多邊形用于計算差分?jǐn)?shù)據(jù)的參考點選擇；然后，分別敘述兩種情況下的差分改正數(shù)的求解，即差分坐標(biāo)改正數(shù)和RSSI向量元素改正數(shù)；接著，給出了融合差分改正的RSSI指紋庫定位流程；最后，用Java+PostgreSQL+PostGIS+Mybatis設(shè)計了算法程序，并使用實時數(shù)據(jù)進(jìn)行了測試。從實驗效果看出，提出的算法具有可行性，在定位準(zhǔn)確性上相較于WKNN算法有一定的提高。