基于三點定位與加權(quán)坐標(biāo)的三角定位算法

徐 樂，韋玉科

廣東工業(yè)大學(xué) 計算機學(xué)院，廣州510006

1 引言

由于人類大部分時間都在室內(nèi)活動，所以室內(nèi)定位技術(shù)的研究變得更加重要。而在室內(nèi)定位技術(shù)的研究中，室內(nèi)定位算法的選擇將會直接影響定位結(jié)果的精準(zhǔn)度。

目前，室內(nèi)定位算法[1]主要分為基于測距和非測距兩種。典型的基于測距定位算法有：基于接收信強度指標(biāo)RSSI[2]、基于到達時間TOA[3]、基于到達角度[4]、基于到達時間差TDOA[5]等。典型的基于非測距定位算法有：Amorphous 算法[6]、質(zhì)心算法[7]。而基于測距定位算法較于基于非測距定位算法，具有更高的定位精度。其中，基于RSSI測距定位算法[8]由于開銷最小而被廣泛應(yīng)用于室內(nèi)定位系統(tǒng)。

基于RSSI 測距定位算法是利用節(jié)點從定位點接收到的功率，并通過功率距離轉(zhuǎn)換和定位算法，推算出定位點的位置。因此，對于基于RSSI 測距定位算法的改進方向主要為：降低RSSI數(shù)據(jù)集的不穩(wěn)定性，提高RSSI測距模型的準(zhǔn)確性和提高定位算法的精度。文獻[9]提出了一種基于多屬性代價函數(shù)的WiFi 與藍牙TLS 融合定位算法，該算法以多屬性代價函數(shù)評估信標(biāo)的定位能力，同時利用TLS對待定位節(jié)點進行最優(yōu)位置估計。文獻[10]提出一種基于特征匹配和距離加權(quán)的藍牙定位算法，該算法在離線狀態(tài)生成指紋數(shù)據(jù)庫，在在線狀態(tài)根據(jù)排序特征向量完全匹配算法、排序特征向量最相似匹配算法和基于距離的最優(yōu)加權(quán)KNN 定位算法實現(xiàn)定位。但是該算法在實際操作時需要采集大量指紋點，工作量較大。文獻[11]提出一種基于藍牙RSSI 的貝葉斯區(qū)域判別定位算法，該算法接收信號強度劃分區(qū)域并對區(qū)域內(nèi)進行定位，但是該算法運算較為復(fù)雜。文獻[12]提出基于RSSI 測距校正的擬牛頓定位算法，該算法通過引用高斯函數(shù)對RSSI 值進行篩選和對剩余的RSSI 數(shù)據(jù)進行加權(quán)操作，來獲取最優(yōu)的RSSI 數(shù)據(jù)，后采用最小二乘法估計和擬牛頓法迭代來確定目標(biāo)結(jié)點的位置。

現(xiàn)有的基于RSSI 測距定位算法的改進算法[13]雖然提高了定位結(jié)果的精確度，但是算法過程都過于復(fù)雜。因此，本文提出一種基于三點定位與加權(quán)坐標(biāo)的三角定位算法。該算法在RSSI測距階段通過多次測量獲取適合的RSSI-距離模型，同時針對RSSI 值波動性大的缺點，對同一定位目標(biāo)的RSSI 數(shù)據(jù)集進行卡爾曼濾波操作。本文的定位算法將三點定位與三角定位算法結(jié)合。首先經(jīng)過基于RSSI 選取的三點定位算法獲取三個粗定位結(jié)果坐標(biāo)；然后給這三個定位坐標(biāo)賦予相應(yīng)的權(quán)值得到加權(quán)坐標(biāo)；最后通過三角定位運算得到最終定位坐標(biāo)結(jié)果。實驗結(jié)果表明，本文提出的算法在實際應(yīng)用中能有效地降低定位誤差。

2 RSSI 測距原理與RSSI數(shù)據(jù)處理

2.1 RSSI測距原理

RSSI 測距原理是基于漸變模型的[14]，即隨著距離的增加信號強度有規(guī)律的衰減。在進行定位時，根據(jù)接收信號強度、發(fā)射信號強度、接收端和發(fā)射端之間的距離構(gòu)建信號強度-距離衰減模型，將測量過程中獲取的RSSI 數(shù)據(jù)集轉(zhuǎn)換為到待定位點的距離數(shù)據(jù)集，用于計算待定位點的位置。

已知無線信號的發(fā)射功率與接收功率之間的關(guān)系如方程式（1）所示：

其中，RSSI 為無線信號的接收功率，P 為無線信號的發(fā)射功率，d 為接收端與發(fā)射端之間的距離，n為環(huán)境衰減因子，大小由無線信號傳播環(huán)境決定。

對方程式（1）兩端進行取對數(shù)操作并化簡，得到方程式（2）：

因為發(fā)射功率是已知，所以接收端信號強度RSSI與傳輸距離d 之間的關(guān)系可用方程式（3）表示：

其中，n表示環(huán)境衰減因子，A表示發(fā)射端與接收端相隔1 m時的信號強度。在實驗環(huán)境中，通過大量測試，得出實驗環(huán)境下的RSSI-距離衰減模型。如圖1 所示，根據(jù)RSSI 原始數(shù)據(jù)與衰減模型計算結(jié)果對比可知，在RSSI原始數(shù)據(jù)與衰減模型計算結(jié)果之間的相似擬合度為96%的條件下，A=-87.074 0，10n=-8.6，所以RSSI-距離衰減模型公式如方程式（4）所示：

圖1 信號衰減模型測試結(jié)果圖

由圖1 可知，RSSI-距離衰減模型中，原始數(shù)據(jù)與擬合數(shù)據(jù)之間相似度很高，同時模型近似服從對數(shù)分布模型。

2.2 卡爾曼濾波

在實際測試場景中，RSSI 數(shù)據(jù)易受到各種干擾噪聲的影響，同時無線信號受到多徑反射傳播、非視距等影響，這些影響會使獲取到的RSSI 數(shù)據(jù)存在著很大的波動性和誤差。為了使獲取到的RSSI 數(shù)據(jù)的波動性和誤差降低，同時為了提高定位精度，本文在進行定位運算之前對獲取到的RSSI 數(shù)據(jù)先進行濾波處理。文獻[15]中對幾種不同數(shù)據(jù)濾波方法的效果進行了比較，其中卡爾曼濾波算法的效果相對較好。

卡爾曼濾波算法是以最小均方誤差作為估計的最佳準(zhǔn)則來尋求一套遞推估計的算法。其基本思想是：采用信號與噪聲的狀態(tài)空間模型，利用前一時刻的估計值和當(dāng)前時刻的觀測值來更新對狀態(tài)變量的估計，求出當(dāng)前時刻的估計值。當(dāng)對象模型足夠準(zhǔn)確且系統(tǒng)狀態(tài)和參數(shù)不發(fā)生突變時，性能較好。且該方法操作簡單，數(shù)據(jù)存貯量小，具有很強的實時性。同時，卡爾曼濾波算法能在一定程度上削弱由于噪聲疊加造成的RSSI 觀測值偏離，經(jīng)過卡爾曼濾波算法處理后的RSSI值，具有更好的穩(wěn)定性。

本文采用卡爾曼濾波方法對獲取的RSSI 數(shù)據(jù)進行處理，以達到降低RSSI 值波動性和減少RSSI 值誤差的目的。對獲取的RSSI 數(shù)據(jù)進行卡爾曼濾波前后的效果圖如圖2所示。

圖2 RSSI數(shù)據(jù)濾波前后效果圖

由圖2可看出，卡爾曼濾波后的RSSI數(shù)據(jù)的波動性變小了，說明卡爾曼濾波對提高基于RSSI 測距定位算法的穩(wěn)定性和準(zhǔn)確性有一定的效果。

3 改進的三角定位算法

3.1 三角定位算法

三角定位算法[16]是RSSI 測距定位算法中常用的定位算法之一。三角定位算法原理是對平面上的三個已知位置的點和未知位置的目標(biāo)點，測出已知點到目標(biāo)點的距離，以已知點為圓心，到目標(biāo)點的距離為半徑畫出相交的三個圓，三圓的相交點即為目標(biāo)點的位置。如圖3所示。

圖3 三角定位算法原理圖

由RSSI-距離衰減模型可知RSSI 轉(zhuǎn)換為距離公式如方程式（5）所示：

假設(shè)在一個平面區(qū)域內(nèi)，安放了三個藍牙Beacon節(jié) 點 分 別 為A(x1,y1)、B(x2,y2)、C(x3,y3)，待 定 位 終 端D(x,y)，RSSIA、RSSIB、RSSIC為接收到A、B、C 三點的信號強度值，根據(jù)方程式（5）可求得A、B、C 到D 的距離為d1、d2、d3。故三角定位算法的表達式可用方程式（6）表示：

3.2 改進的三角定位算法

在實際場景中，由于無線信號傳播易受干擾，獲取到的RSSI值存在著波動性，通過RSSI-距離衰減模型求得的距離與實際距離具有一定的誤差，導(dǎo)致三圓相交出現(xiàn)多個交點，所以通過三角定位運算得出的定位結(jié)果存在著誤差。因此，本文提出一種基于三點定位與加權(quán)坐標(biāo)的三角定位算法，該算法將三點定位與三角定位算法相結(jié)合。首先分別通過三種不同的基于RSSI選取方式的三點定位算法得到三個粗定位結(jié)果坐標(biāo)；然后給這三個定位結(jié)果坐標(biāo)賦予相應(yīng)的權(quán)值得到加權(quán)坐標(biāo)；最后加權(quán)坐標(biāo)經(jīng)過三角定位運算得到待定位目標(biāo)點坐標(biāo)。

3.2.1 基于RSSI選取的三點定位算法

基于RSSI 選取的三點定位算法主要是利用不同的選取方式獲得三個藍牙Beacon 節(jié)點，通過三點定位算法得到粗定位結(jié)果。本文所用的RSSI選取方式可分為基于功率的、基于距離的和基于功率與距離結(jié)合的三種。下面分別介紹這三種選取方式。

（1）基于功率的RSSI選取方式

基于功率的RSSI 選取方式主要是選取獲取的數(shù)據(jù)包中RSSI值最大的三個藍牙Beacon節(jié)點。其具體步驟如下：

步驟1 獲取所有藍牙Beacon節(jié)點數(shù)據(jù)包中的RSSI數(shù) 據(jù) 集 合RSSI={RSSI1,RSSI2, …,RSSIn}，n 為 藍 牙Beacon節(jié)點個數(shù)。

步驟2 選取RSSI集合中值最大的三個藍牙Beacon節(jié)點，并獲取相應(yīng)的X，Y 軸坐標(biāo)值集合X={x1,x2,x3}和Y={y1,y2,y3}。

（2）基于距離的RSSI選取方式

基于距離的RSSI 選取方式主要是選取經(jīng)過RSSI-距離轉(zhuǎn)換后的距離數(shù)據(jù)集中最小的三個藍牙Beacon 節(jié)距離轉(zhuǎn)換后的距離數(shù)據(jù)集中最小的三個藍牙Beacon 節(jié)點。其具體步驟如下：

步驟1 根據(jù)方程式（5），對獲取的所有藍牙Beacon節(jié)點數(shù)據(jù)包中的RSSI值進行RSSI-距離轉(zhuǎn)換，得到距離集合d={d1,d2,…,dn}，n為藍牙Beacon節(jié)點個數(shù)。

步驟2 選取距離集合d={d1,d2,…,dn}中距離值最小的三個點

步驟3 獲取對應(yīng)的藍牙Beacon節(jié)點的X，Y 軸坐標(biāo)值集合X={x1,x2,x3}和Y={y1,y2,y3}。

（3）基于功率與距離結(jié)合的RSSI選取方式

基于功率與距離結(jié)合的RSSI 選取方式主要是選取獲取的數(shù)據(jù)包中RSSI 值最大的藍牙Beacon 節(jié)點，和距離該節(jié)點的距離值最小的兩個藍牙Beacon 節(jié)點。其具體步驟如下：

步驟1 獲取所有藍牙Beacon節(jié)點數(shù)據(jù)包中的RSSI數(shù) 據(jù) 集 合RSSI={RSSI1,RSSI2,…,RSSIn}，n 為 藍 牙Beacon 節(jié)點個數(shù)，選取RSSI 集合中最大的一個藍牙Beacon節(jié)點RSSImax。

步驟2 計算除RSSImax之外的所有藍牙Beacon 節(jié)點 到 RSSImax的 距 離 ，并 得 到 距 離 集 合d={d1,d2,…,dm-1}，m 為藍牙Beacon節(jié)點個數(shù)。

步驟3 選取d={d1,d2,…,dm-1}中值最小的兩個點，獲取RSSImax和對應(yīng)的藍牙Beacon 節(jié)點X，Y 軸坐標(biāo)值集合X={x1,x2,x3}和Y={y1,y2,y3}。

通過上述的選取方式中的任意一種方式均可獲取到需要的三個藍牙Beacon 節(jié)點X，Y 軸坐標(biāo)值集合X={x1,x2,x3}和Y={y1,y2,y3}，通過方程式（8）可得到粗定位結(jié)果坐標(biāo)。

其中，p、q、t 為權(quán)值。

方程式（8）中的權(quán)值p、q、t 是根據(jù)選取的三個藍牙Beacon 節(jié)點數(shù)據(jù)包中的RSSI 值之間差距的大小來設(shè)置的。具體權(quán)值的設(shè)置過程可以用偽代碼描述，如下所示。

描述：方程式（8）中權(quán)值的設(shè)置

輸入：RSSI={rssi1,rssi2,rssi3}

X={x1,x2,x3}

Y={y1,y2,y3}

輸出：(x,y)

算法過程：

針對方程式（8）的權(quán)值的設(shè)定是經(jīng)過大量測試后確定的。

3.2.2 基于加權(quán)坐標(biāo)的三角定位算法

基于加權(quán)坐標(biāo)的三角定位算法主要是對經(jīng)過基于RSSI 選取的三點定位算法后的三個定位結(jié)果坐標(biāo)賦予不同的權(quán)值，然后通過三角定位運算得到待定位點坐標(biāo)。其具體步驟如下：

步驟1 經(jīng)過基于RSSI 選取的三點定位算法，得到三個粗定位結(jié)果坐標(biāo)A(x1,y1),B(x2,y2)和C(x3,y3)。

步驟2 根據(jù)方程式（9），給A，B，C 坐標(biāo)賦予相應(yīng)的權(quán)值，得到加權(quán)坐標(biāo)和

其中，α、β、γ為權(quán)值。

步驟3 根據(jù)方程式（5）計算A、B、C 對應(yīng)的藍牙Beacon節(jié)點到待定位目標(biāo)的距離。

步驟4 根據(jù)方式（10）可得到待定位點的坐標(biāo)(x,y)。

在基于坐標(biāo)加權(quán)的三角定位算法中，坐標(biāo)加權(quán)流程如圖4所示。

圖4 坐標(biāo)加權(quán)流程圖

3.2.3 基于三點定位與加權(quán)坐標(biāo)的三角定位算法

基于三點定位與加權(quán)坐標(biāo)的三角定位算法先對待定位點進行三點定位運算，得到三個粗定位結(jié)果坐標(biāo)，然后對這三個粗定位結(jié)果坐標(biāo)進行加權(quán)操作，得到加權(quán)坐標(biāo)，最后將這三個加權(quán)坐標(biāo)經(jīng)過三角定位運算得到待定位點坐標(biāo)。

基于三點定位與加權(quán)坐標(biāo)的三角定位算法的流程如圖5所示。

圖5 基于三點定位與加權(quán)坐標(biāo)的三角定位算法流程圖

基于三點定位與加權(quán)坐標(biāo)的三角定位算法的具體步驟如下：

步驟1 獲取所有藍牙Beacon節(jié)點數(shù)據(jù)包。

步驟2 對獲取的數(shù)據(jù)中的RSSI數(shù)據(jù)進行卡爾曼濾波處理，得到處理后的新RSSI數(shù)據(jù)RSSIK。

步驟3 對RSSIK分別進行三種不同的基于RSSI選取的三點定位算法得到三個粗定位結(jié)果坐標(biāo)A( x1,y1),B( x2,y2),C( x3,y3)。

步驟4 給A( x1,y1),B( x2,y2),C( x3,y3)賦予相應(yīng)的權(quán)值的到加權(quán)坐標(biāo)

步驟5 對加權(quán)坐標(biāo)進行三角定位運算，得到待定位點坐標(biāo)(x,y)。

4 實驗與結(jié)果分析

本文的實驗環(huán)境為：一個布設(shè)了室內(nèi)無線藍牙定位環(huán)境的辦公室，該辦公室面積為50 m×50 m，在該場景內(nèi)布設(shè)26 個藍牙Beacon 節(jié)點，每個藍牙Beacon 節(jié)點之間相距8 m。測試規(guī)則為：藍牙Beacon 節(jié)點每隔3 s 上報RSSI 數(shù)據(jù)包，測試時測試人員在每個測試點測試30次。當(dāng)90%的誤差值低于某一個值時，則該值即為該點的定位誤差值；計算區(qū)域誤差值時，當(dāng)整個區(qū)域內(nèi)誤差值有90%低于某一個值時，則該值為這個區(qū)域內(nèi)的定位誤差（即算法平均誤差）。同時，選擇文獻[12]中的最小二乘定位算法和改進的四點質(zhì)心定位算法進行比較，分別記為傳統(tǒng)三角定位算法和四點定位算法。

本文采用方程式（11）來計算定位結(jié)果的精度。方程式（11）表示如下：

其中，(x,y)為實際待定位點的二維坐標(biāo)，(xi,yi)為算法計算出的待定位點的估計二維坐標(biāo)。

從表1 中可以看出：傳統(tǒng)三角定位算法的定位誤差在1.908 m 內(nèi)，平均定位誤差為0.970 m，運行時間為0.690 ms；四點定位算法的定位誤差在1.709 m 內(nèi)，平均定位誤差為0.897 m，運行時間為0.640 ms；本文提出的定位算法也存在著定位誤差，但是定位誤差在1.602 m內(nèi)，平均定位誤差為0.880 m，運行時間為0.590 ms。與傳統(tǒng)三角定位算法和四點定位算法相比，本文提出的算法具有更高的定位精度。

表1 不同定位算法的性能比較

同時，將本文提出的定位算法應(yīng)用于實際的定位系統(tǒng)中，在定位系統(tǒng)的導(dǎo)航模塊，進行導(dǎo)航過程的定位測試。測試規(guī)則為：選取起點與終點，規(guī)劃多條路徑，并在路徑中設(shè)定測試點，在每條路徑中測試多次，每個測試點的平均誤差值作為該測試點的定位誤差值，將整個區(qū)域內(nèi)所有測試點的定位誤差值的平均值作為該區(qū)域內(nèi)定位系統(tǒng)導(dǎo)航模塊的定位誤差值。測試過程：在測試區(qū)域內(nèi)部署多個藍牙Beacon 節(jié)點，測試人員佩戴藍牙手環(huán)，每2 s 上報一次RSSI 數(shù)據(jù)，服務(wù)器端收集到5 組RSSI 數(shù)據(jù)后才開始進行定位計算。測試結(jié)果如圖6所示。

圖6 導(dǎo)航模塊測試結(jié)果圖

從圖6 中可以知道：本文定位算法在導(dǎo)航過程中的定位誤差主要出現(xiàn)在[0，1]之間，在行走過程中因為測試點進入定位系統(tǒng)覆蓋邊緣時會出現(xiàn)較大的誤差，但是整個過程定位誤差將控制在4 m 內(nèi)，平均定位誤差為1.097 7 m。

5 結(jié)束語

為了降低傳統(tǒng)的基于接收信號強度指示（Received Signal Strength Indication，RSSI）的三角定位算法產(chǎn)生的定位誤差和和定位結(jié)果存在波動性的問題，本文提出一種基于三點定位與加權(quán)坐標(biāo)的三角定位算法。該算法先對RSSI 數(shù)據(jù)進行卡爾曼濾波操作，降低RSSI 數(shù)據(jù)的波動性；然后將濾波后數(shù)據(jù)經(jīng)過基于RSSI 選取的三點定位算法，獲取粗定位坐標(biāo)；最后將獲取的三個粗定位坐標(biāo)經(jīng)過基于加權(quán)坐標(biāo)的三角定位算法得到待定位點坐標(biāo)。本文從理論原理和實驗測試方面驗證了算法的可行性，并通過實驗結(jié)果分析可知該算法能有效地提高定位精度。