一種基于卡爾曼和線性插值濾波的改進三角質(zhì)心定位算法*

趙大龍，白鳳山，董思宇，李洪書

（內(nèi)蒙古大學電子信息工程學院，呼和浩特 010021）

一種基于卡爾曼和線性插值濾波的改進三角質(zhì)心定位算法*

趙大龍，白鳳山*，董思宇，李洪書

（內(nèi)蒙古大學電子信息工程學院，呼和浩特 010021）

基于RSSI的目標定位技術(shù)，由于復雜度低、定位精度較高，被廣泛用于無線傳感網(wǎng)絡(luò)節(jié)點定位中。為進一步提高無線移動定位精度，首先利用CC2530構(gòu)成的參考節(jié)點的RSSI實測數(shù)值得到無線信道模型中優(yōu)化射頻參數(shù)A和傳播因子n，通過卡爾曼濾波和線性插值法對隨機誤差進行補償以獲得較精確的定位節(jié)點與參考節(jié)點間的估計距離；然后采用一種改進的三角質(zhì)心定位算法進行測試與仿真。通過仿真證明，采用的改進算法較傳統(tǒng)的加權(quán)質(zhì)心算法在定位精度上有較明顯的提高，在所測試環(huán)境下平均定位精度為0.7米左右，獲得了較好的效果。

無線移動定位；RSSI；卡爾曼濾波；線性插值；三角質(zhì)心定位

隨著無線傳感器網(wǎng)絡(luò)和物聯(lián)網(wǎng)技術(shù)的蓬勃發(fā)展，基于無線傳感網(wǎng)絡(luò)的定位技術(shù)［1］被廣泛應(yīng)用到眾多領(lǐng)域。無線傳感器網(wǎng)絡(luò)定位系統(tǒng)［2］是指自組織網(wǎng)絡(luò)通過特定方法確定節(jié)點位置信息的系統(tǒng)。在無線傳感器網(wǎng)絡(luò)中，按照是否依靠測距定位分為基于測距［3］（range-based）和非基于測距［4］（range-free）的定位算法。前者是利用測量和估計得到節(jié)點間的距離，然后通過幾何關(guān)系來估算節(jié)點位置，如接收信號強度（RSSI）、信號傳播時間/時間差/往返時間（TOA［5］/TDOA/RTOF）、接收信號相位差（PDOA）等方法。后者是利用節(jié)點間的跳數(shù)與參考節(jié)點位置等信息估計出每一跳的距離，從而估計出節(jié)點的位置［6］。從定位精度方面分析，基于測距的定位算法可獲得較高定位精度，大多數(shù)現(xiàn)有的定位系統(tǒng)均采用基于測距的定位算法。

RSSI測距是利用信號在傳播中存在信號強度衰減的方法，通過信道傳播模型計算距離。但是，這種計算方法容易受到各種傳播因素的影響。因此，對測量數(shù)據(jù)進行數(shù)據(jù)處理、校正尤為重要?？柭↘alman）濾波算法是一種比較好的數(shù)字濾波方法，該方法不僅有效地抑制了距離數(shù)據(jù)信息的誤差發(fā)散，而且能充分利用線性插值法對隨機誤差進行補償。

在濾波算法中［7-9］，文獻［9］利用卡爾曼濾波算法，對RSSI進行濾波，并估測出移動節(jié)點的運動軌跡，較其他處理方法可獲得較高的測距精度［10-11］。但是，這種方法的缺點是在測距階段沒有充分利用信標節(jié)點的信息，使得RSSI測距值存在較大誤差。

在無線移動定位算法中［12-16］，文獻［12］提出一種實用的加權(quán)三角質(zhì)心RSSI定位算法，即通過RSSI測距技術(shù)測量節(jié)點間的距離，并優(yōu)選信標節(jié)點，最后用三角加權(quán)質(zhì)心方法進行定位。該方法的優(yōu)點是計算簡單，定位過程中無需增加節(jié)點間額外通信開銷。但是，該方法存在的缺點是在圓周定位模型中沒有充分利用距離d信息，定位誤差精度較低。

本文對文獻［9］和文獻［12］算法的漏洞進行修改，通過卡爾曼濾波和線性插值法修正RSSI值，并采用傳統(tǒng)的距離損耗模型計算d；在基于改進的加權(quán)三角質(zhì)心RSSI測距［17-18］的基礎(chǔ)上計算未知節(jié)點坐標。通過MATLAB仿真表明，此算法進一步提高了節(jié)點定位精度，具有較好的實用價值。

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

1.1 RSSI測距

基于RSSI測距的定位方法是無線傳感網(wǎng)絡(luò)節(jié)點定位的主要方法之一，大多數(shù)無線傳感網(wǎng)絡(luò)CCx系列芯片均提供RSSI測量數(shù)據(jù)。RSSI測距算法的基本思想是指在發(fā)射節(jié)點的發(fā)射功率確定的情況下，可以根據(jù)接收節(jié)點接收的功率，得出能量損耗與距離的關(guān)系。通常采用的信號傳播模型如公式（1）所示［19］。

式中，RSSI為接收信號強度（dBm）；A常取距離發(fā)射結(jié)點1 m時的接收信號強度；d是收發(fā)節(jié)點之間的距離（m）；n表示信號傳播常量，也叫信號傳播因子。因此，定位前合理選取A和n是提高距離測量精度的前提。

本實驗選擇空曠的操場上測試，節(jié)點芯片為CC2530，天線為2.4 G全向天線，增益為3 dBi，天線長度為109 mm。首先將用于接收數(shù)據(jù)的定位節(jié)點1固定好，發(fā)射結(jié)點在距其1 m位置以功率為0 dBm連續(xù)發(fā)射功率信號，測量一組20個數(shù)據(jù)；為減少天線方向性產(chǎn)生的輻射偏差，將發(fā)射節(jié)點沿著順時針方向再轉(zhuǎn)90°，進行第二組20個數(shù)據(jù)的測試，這樣旋轉(zhuǎn)一周將所測得的同一距離內(nèi)的80個數(shù)據(jù)信號強度求平均值，作為該距離內(nèi)的接收信號實測值，測試節(jié)點分布如圖1所示。

圖1 測試節(jié)點分布

接著距定位節(jié)點每增加0.5 m重復上述測量過程，最后繪制成圖2中的點畫曲線作為RSSI實測曲線。取距離1 m時的接收信號強度的平均值-30 dBm作為參數(shù)A的取值，再通過變化n，由公式1利用MATLAB可以繪制出多條RSSI與d關(guān)系曲線，如圖2所示。

圖2 RSSI與d對應(yīng)關(guān)系

通過對比擬合曲線與n取不同值時的曲線的擬合度來確定n。由表1中可以看出n取20的擬合曲線的擬合度為0.99，表明RSSI均值和距離之間存在確定的函數(shù)關(guān)系，而且在20 m內(nèi)，RSSI實測值與理論分析比較接近。

圖3 RSSI數(shù)據(jù)修正前后對比

表1 擬合度對比表

有了A和n，接收節(jié)點根據(jù)接收到信號的強度RSSI就可以利用式（1）估算出與幾個發(fā)射節(jié)點的距離d，從而利用定位算法計算出未知節(jié)點的位置。

1.2 卡爾曼濾波

RSSI數(shù)據(jù)容易受到各種干擾噪聲的影響，為了滿足對定位精度的進一步要求，還需要對上述數(shù)據(jù)進行處理。文獻［19］中給出了幾種不同數(shù)據(jù)濾波方法的效果對比，其中卡爾曼濾波算法表現(xiàn)出良好特性。

卡爾曼濾波是以最小均方誤差為估計的最佳準則來尋求一套遞推估計的算法。其基本思想是：采用信號與噪聲的狀態(tài)空間模型，利用前一時刻的估計值和現(xiàn)時刻的觀測值來更新對狀態(tài)變量的估計，求出現(xiàn)時刻的估計值。當對象模型足夠準確且系統(tǒng)狀態(tài)和參數(shù)不發(fā)生突變時，性能較好。該方法簡單，數(shù)據(jù)存貯量小，具有很強的實時性。

本文采用卡爾曼濾波方法對各信標節(jié)點的RSSI測距數(shù)據(jù)進行處理，以達到快速收斂，減少噪聲影響和誤差目的，卡爾曼算法原理詳見參考文獻［7-10］。

1.3 線性插值

線性插值是數(shù)學、計算機圖形學等領(lǐng)域廣泛使用的一種簡單插值方法。假設(shè)已知坐標（x0，y0）與（x1，y1），要得到［x0，x1］區(qū)間內(nèi)某一位置xi在線上的yi值，可由線性插值法的求得：

這種在一組點（x0，y0）、（x1，y1），…，（xn，yn）中插值的方式可被定義為點對之間的線性連續(xù)插入，可產(chǎn)生一條實線。本文中將經(jīng)卡爾曼濾波處理的RSSI數(shù)據(jù)用線性插值方法來預測已知的多對點對之間的未知點的信號強度。數(shù)據(jù)處理結(jié)果對比如圖3所示。從圖3可以看出，處理后的RSSI可減小波動，說明卡爾曼濾波和線性插值法對提高無線定位穩(wěn)定性和準確性有很大作用。

2 三角質(zhì)心定位算法的改進

2.1 傳統(tǒng)的質(zhì)心定位算法

傳統(tǒng)的質(zhì)心定位算法是距離加權(quán)質(zhì)心定位算法，即找出距未知節(jié)點最近的三個參考節(jié)點（未知節(jié)點接收到RSSI最強的三個節(jié)點），并按照公式（1）將計算出這三個參考節(jié)點與未知節(jié)點之間的距離作為權(quán)值引入到定位算法中，然后求這三個參考節(jié)點的質(zhì)心作為未知節(jié)點的位置估計，見圖4（a）。

圖4 基于圓周模型的三角質(zhì)心算法

一般來說，已知無線傳感器網(wǎng)絡(luò)N個固定信標節(jié)點Bi的位置坐標（xi，yi），其中（1≤i≤N），未知節(jié)點的估計位置坐標為（x，y），那么傳統(tǒng)基于RSSI的加權(quán)質(zhì)心定位算法計算公式為：

這里權(quán)值是未知節(jié)點到固定信標節(jié)點的距離函數(shù)和的倒數(shù)。傳統(tǒng)的質(zhì)心定位算法最簡單，但定位精度較低，使用較少。

2.2 改進的質(zhì)心定位算法

根據(jù)文獻［12］提到的傳統(tǒng)加權(quán)質(zhì)心定位算法的原理可知，權(quán)值這一部分對于整個算法定位精度有著至關(guān)重要的作用，合理選取權(quán)值可以避免信息淹沒現(xiàn)象。加權(quán)質(zhì)心定位算法中對于權(quán)值選擇可以采用不同的方式，本文中采用距離倒數(shù)之和代替?zhèn)鹘y(tǒng)算法中距離和的倒數(shù)的算法。

首先將接收到的RSSI數(shù)據(jù)利用卡爾曼濾波和線性插值修正，并利用公式（1）轉(zhuǎn)化為距離。再將這些距離從小到大進行排序，選距離最小所對應(yīng)的3個信標節(jié)點用于對未知節(jié)點定位。然后分別以這3個信標節(jié)點為圓心，以未知節(jié)點到信標節(jié)點之間的距離為半徑畫圓，由于實際測量結(jié)果每次都有誤差，這樣3個圓不會交于一點，而會產(chǎn)生公共相交部分，如圖4（b）所示。此時，未知節(jié)點就認為位于所有圓的交集部分。以上述提到的質(zhì)心算法為基礎(chǔ)，對3個圓的共同交點（ABC）組成的三角形進行分析，利用優(yōu)選的參考節(jié)點和未知節(jié)點之間的距離為每一個坐標增加了權(quán)值，以體現(xiàn)不同頂點的貢獻。

修正后的加權(quán)質(zhì)心公式為式（5）和式（6）。其中（xA，yA）、（xB，yB）、（xC，yC）為三個交點坐標可以容易求出，式（5）和式（6）不僅在質(zhì)心運算中增加了RSSI數(shù)據(jù)的信息，還在權(quán)值的選取中合理的安排了信息權(quán)重，并采用了修正系數(shù)的概念，使得整個定位精度得到了很大的提高。

但是在實際的測試中，由于測距誤差，三個圓往往無法交于一點。假設(shè)移動節(jié)點只在參考節(jié)點的區(qū)域內(nèi)活動，則可能產(chǎn)生的情況如圖5所示。

圖5 三邊定位測算中可能發(fā)生的四種情況

實際操作中，首先要判斷3個圓之中有幾個相交，采用的方法可以是把3個圓的方程兩兩聯(lián)立，判斷有沒有解。

如果方程（7）有解（x12，y12）和（x21，y21），判斷其中哪個點與點（x3，y3）的距離近，選取該點作為點D；如果方程（8）有解（x13，y13）和（x31，y31），判斷其中哪個點與點（x2，y2）的距離近，選取該點作為點F；如果方程（9）有解（x23，y23）和（x32，y32），判斷其中哪個點與點（x1，y1）的距離近，選取該點作為點E，則△DEF的重心就是我們所需要定位的移動節(jié)點的位置。如果其中方程（7）無解，則連接兩圓圓心，和圓相交兩點的中心就是點D；對于式（8）和式（9）無解的情況下，可采用相同方式來得到點E、F的坐標。因此，無論圓相交與否，我們都可以獲得3個點D、E、F，并且通過求重心來獲得移動節(jié)點的坐標。

3 算法實現(xiàn)與仿真

3.1 算法實現(xiàn)過程

改進定位算法實現(xiàn)流程如下：

（1）各信標節(jié)點周期性發(fā)送自身信息：節(jié)點ID、自身位置信息；

（2）未知節(jié)點收到信息后，記錄信標節(jié)點ID對應(yīng)的RSSI值，并利用卡爾曼濾波和線性插值法對RSSI數(shù)據(jù)進行修正；

（3）未知節(jié)點接收到一定的坐標信息后，不再接收新信息，對信標節(jié)點依其RSSI值從大到小排序，并建立RSSI值與未知節(jié)點到信標節(jié)點距離的映射，建立3個集合：

①信標節(jié)點集合：Beacon=｛a1，a2，…，am｝；

②未知節(jié)點到信標節(jié)點距離集合：Distance= ｛d1，d2，…，dm｝，d1＜d2…＜dm；

③信標節(jié)點位置集合：

（4）在Beacon集合中依據(jù)前述對傳播路徑損耗模型的分析結(jié)論，優(yōu)先選擇RSSI值中最大的三個信標節(jié)點組合成下面的集合：

（5）將Beacon中的RSSI值轉(zhuǎn)換為距離d，并從大到小排序：

（6）分別對三組數(shù)據(jù)進行計算產(chǎn)生三個定位點A、B、C的坐標，如圖4（b）。再用修正的加權(quán)質(zhì)心算法式（5）、式（6）求得三角形質(zhì)心（x，y）作為未知節(jié)點的位置坐標。

3.2 算法仿真

為了對本文采用的基于卡爾曼濾波和線性插值法的改進三角質(zhì)心定位算法進行驗證，我們采用MATLAB軟件，利用Shadowing模型進行仿真。仿真實驗的初始條件為：無線傳感器網(wǎng)絡(luò)位于30 m×30 m的區(qū)域內(nèi)，4個信標節(jié)點等間距分布在正方形區(qū)域四個角上，為了驗證簡單性，本文把未知節(jié)點初始化為（0，15），未知節(jié)點在中線上以勻速向右移動。路徑損耗系數(shù)n設(shè)為20，節(jié)點的通信半徑為30 m，仿真環(huán)境如圖6所示。

圖6 仿真環(huán)境

另外，所有的仿真實驗環(huán)境中都加入了均值為零，標準差為0.5的高斯分布隨機噪聲，來代替實際環(huán)境中的反射、多徑、物體移動、氣候等帶來的影響。

圖7給出了濾波前、單獨卡爾曼濾波、濾波與線性插值結(jié)合三種情況下改進三角質(zhì)心定位算法的有效性。在周圍信標節(jié)點總數(shù)為4時，該算法平均定位誤差在0.7 m左右。由此可見，相對于傳統(tǒng)的基于RSSI的質(zhì)心定位算法，首先通過卡爾曼濾波和線性插值法對隨機誤差進行補償以；然后采用改進的三角質(zhì)心定位算法定位，有著明顯優(yōu)勢，大大的提高了算法的定位精度。

圖7 三種條件下定位算法測距誤差仿真

4 結(jié)論

本文采用通過卡爾曼濾波和線性插值對節(jié)點發(fā)射的RSSI修正，然后運用改進的三角質(zhì)心定位方法計算未知節(jié)點位置。實驗和仿真表明該定位算法不僅具有更好的定位精度，而且算法運算量較小，對硬件的要求不高，比較適合對節(jié)點定位精度要求不太高的大規(guī)模傳感器網(wǎng)絡(luò)應(yīng)用中，經(jīng)過進一步改進后將具有較高的實用價值。

［1］ 周雅琴，譚定忠.無線傳感器網(wǎng)絡(luò)應(yīng)用及研究現(xiàn)狀［J］.傳感器世界，2009（5）：35-40.

［2］ Liu Yunhao，Yang Zheng，Wang Xiaoping.Location，Localization and Localizability［J］.Journal of Computer Science and Technology，2010，25：274-297.

［3］ 吳曉平，陸炳斌，沈浩.基于RSSI定位模型的非視距關(guān)系識別方法［J］.傳感技術(shù)學報，2013，26（11）：1584-1589.

［4］ Zhang Shigeng，Cao Jiannong，Chen Lijun，et al.Accurate and Energy-Efficient Range-Free Localization for Mobile Sensor Networks［J］.IEEE Transactions on Mobile Computing，2010，9（6）：897-910.

［5］ Junyang Shen，Andreas F Molisch，Jussi Salmi.Accurate Passive Location Estimation Using TOA Measurements［J］.IEEE Transactions on Wireless Communications，2012，11（6）：2182-2192.

［6］ Yang Zheng，Liu Yunhao.Understanding Node Localizability of Wireless Ad Hoc and Sensor Networks［J］.IEEE Transactions on Parallel and Distributed Systems，2012，11：1249-1260.

［7］ 劉志華，馬征征，陳嘉興.無線傳感器網(wǎng)絡(luò)中移動節(jié)點的后驗信號濾波定位法［J］.傳感技術(shù)學報，2013，26（5）：739-744.

［8］ 朱明強，侯建軍，劉穎，等.一種基于卡爾曼數(shù)據(jù)平滑的分段曲線擬合室內(nèi)定位算法［J］.北京交通大學學報，2012，36（5）：95-99.

［9］ 鄧胡濱，張磊，吳穎，等.基于卡爾曼濾波算法的軌跡估計研究［J］.傳感器與微系統(tǒng)，2012，31（5）：4-7.

［10］Paul A S，Wan E A.RSSI-Based Indoor Localization and Tracking Using Sigma-Point Kalman Smoothers［J］.IEEE J of Selected Topics in Signal Processing，2009，3（5）：860-873.

［11］曹春萍，羅玲莉.基于卡爾曼濾波算法的室內(nèi)無線定位系統(tǒng)［J］.計算機系統(tǒng)應(yīng)用，2011，20（11）：76-79.

［12］楊博雄，倪玉華，劉琨，等.基于加權(quán)三角質(zhì)心RSSI算法的Zig-Bee室內(nèi)無線定位技術(shù)研究［J］.傳感器世界，2012，11：31-35.

［13］Wang Gang，Yang Kehu.A New Approach to Sensor Node Localization Using RSS Measurements in Wireless Sensor Networks［J］. IEEE Transactions on Wireless Communications，2011，10（5）：1389-1395.

［14］Bulusu N，Heidemann J，Estrin D.GPS-Less Low Cost Outdoor Localization for Very Small Devices［J］.IEEE Personal Communications Magazine，2000，7（5）：28-34.

［15］袁鑫，吳曉平，王國英.線性最小二乘法的RSSI定位精確計算方法［J］.傳感技術(shù)學報，2014，27（10）：1412-1417.

［16］劉志華，李改燕，劉曉爽.基于最小二乘法的蒙特卡洛移動節(jié)點定位算法［J］.傳感技術(shù)學報，2012，25（4）：541-544.

［17］呂振，趙鵬飛.一種改進的無線傳感器網(wǎng)絡(luò)加權(quán)質(zhì)心定位算法［J］.計算機測量與控制，2013，21（4）：1102-1104.

［18］劉運杰，金明錄，崔承毅.傳感器網(wǎng)絡(luò)修正加權(quán)質(zhì)心定位算法［J］.傳感技術(shù)學報，2010，23（5）：717-721.

［19］張橙，宋學瑞.基于ZigBee的RSSI測距方精度研究［J］.湖南工業(yè)大學學報，2011，25（5）：37-41.

趙大龍（1987-），男，河北省保定市人，碩士研究生，現(xiàn)就讀于內(nèi)蒙古大學電子信息工程學院，主要研究方向為無線傳感網(wǎng)絡(luò)，zhaodl1987@163.com；

白鳳山（1963-）男，教授，內(nèi)蒙古呼和浩特市人，現(xiàn)在內(nèi)蒙古大學電子信息工程學院工作，主要研究方向無線通信、無線傳感網(wǎng)絡(luò)等，eefs8015@163.com。

An Improved Triangle Centroid Location Algorithm Based on Kalman Filtering and Linear Interpolation*

ZHAO Dalong，BAI Fengshan*，DONG Siyu，LI Hongshu
（College of Electronic and Information Engineering，Inner Mongolia University，Hohhot 010021，China）

The target location technology based on RSSI with the features of low complexity and high locating accuracy has been widely applied to nodes location in WSN.For further improving moving target locating accuracy the optimized RF parameter A and signal transmission constant n in wireless channel model are calculated firstly through RSSI real values received from reference nodes made up of CC2530.Then a more precise estimated distance value between reference and location nodes can be achieved via Kalman filtering and linear interpolation for compensating random errors.Finally an improved triangle centroid location algorithm was tested and simulated on basis of above-mentioned distance value.The simulation results showed that the improved algorithm used in the paper achieved an average about 0.7 m location precision in the testing environment，which is markedly better than that of the existing location algorithms.

wireless moving target location；RSSI；Kalman filtering；linear interpolation；triangle centroid location EEACC：7230

TP212.9；TN393

A

1004-1699（2015）07-1086-05

10.3969/j.issn.1004-1699.2015.07.024

項目來源：內(nèi)蒙古自治區(qū)教育廳研究生科研創(chuàng)新項目（1402020201324）

2014-12-09 修改日期：2015-03-25