一種基于CKF的無線傳感器網(wǎng)絡(luò)分布式定位算法

余木琪，鄧 平

（西南交通大學(xué)信息編碼與傳輸重點(diǎn)實(shí)驗(yàn)室，成都 610031）

一種基于CKF的無線傳感器網(wǎng)絡(luò)分布式定位算法

余木琪，鄧 平*

（西南交通大學(xué)信息編碼與傳輸重點(diǎn)實(shí)驗(yàn)室，成都 610031）

為提高無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位的精度，降低算法計(jì)算復(fù)雜性，提出了一種基于容積卡爾曼濾波的無線傳感器網(wǎng)絡(luò)分布式節(jié)點(diǎn)定位算法。該算法假定移動(dòng)錨節(jié)點(diǎn)按預(yù)定路徑在傳感區(qū)域移動(dòng)，并周期性廣播自身位置信標(biāo)信息；每個(gè)未知位置節(jié)點(diǎn)首先收集多個(gè)錨節(jié)點(diǎn)信標(biāo)信息及信號(hào)強(qiáng)度信息，然后估算出錨節(jié)點(diǎn)信標(biāo)位置與未知節(jié)點(diǎn)的距離，最后在未知節(jié)點(diǎn)上運(yùn)用容積卡爾曼濾波算法完成自身位置的分布式定位。仿真結(jié)果表明：本文所提算法具有優(yōu)良的定位性能，定位精度和無跡卡爾曼濾波算法相當(dāng)，明顯優(yōu)于極大似然估計(jì)定位算法，而計(jì)算復(fù)雜性則低于無跡卡爾曼濾波算法。

無線傳感器網(wǎng)絡(luò)；容積卡爾曼濾波；定位；移動(dòng)錨節(jié)點(diǎn)

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks，WSN）是由布置在監(jiān)測區(qū)域內(nèi)大量的廉價(jià)微型傳感器節(jié)點(diǎn)組成，通過無線通信方式形成的一個(gè)多跳自組織網(wǎng)絡(luò)，其目的是協(xié)作地感知、采集和處理網(wǎng)絡(luò)覆蓋區(qū)域中監(jiān)測對(duì)象的信息，并發(fā)送給觀察者［1］。無線傳感器網(wǎng)絡(luò)涉及傳感器技術(shù)、微機(jī)電系統(tǒng)、現(xiàn)代網(wǎng)絡(luò)和無線通信等技術(shù)，是21世紀(jì)最重要的新興技術(shù)之一，也是目前IT領(lǐng)域中的研究熱點(diǎn)之一［2］。在無線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)的位置信息對(duì)網(wǎng)絡(luò)的監(jiān)測活動(dòng)至關(guān)重要。

近年來，無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)得到飛速發(fā)展，主要的定位算法有測距定位、非測距定位、凸優(yōu)化、移動(dòng)錨節(jié)點(diǎn)定位、蒙特卡洛定位（Monte Caro localization，MCL）等算法［3-5］。文獻(xiàn)［5］中Lingxuan Hu和David Evans參考移動(dòng)機(jī)器人中的序列蒙特卡洛定位方法的思想，首次將MCL應(yīng)用于移動(dòng)傳感網(wǎng)的定位中，但是該算法需要很高的錨節(jié)點(diǎn)密度才能獲得比較好的定位精度，計(jì)算復(fù)雜度高，且不能應(yīng)用于節(jié)點(diǎn)靜止的無線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)定位。文獻(xiàn)［6］中Liqiang Zhang等人將目標(biāo)跟蹤的過程運(yùn)用于移動(dòng)錨節(jié)點(diǎn)的無線傳感器網(wǎng)絡(luò)分布式定位，提出一種新的分布式傳感器定位算法。該算法運(yùn)用無跡卡爾曼濾波（Unscented Kalman Filter，UKF）進(jìn)行定位，能取得較高的定位精度，但是UKF算法的可調(diào)參數(shù)選取不好會(huì)使其不穩(wěn)定。文獻(xiàn)［7］對(duì)文獻(xiàn)［6］的初始位置選取進(jìn)行改進(jìn)，首先接收三個(gè)不共線的錨節(jié)點(diǎn)信標(biāo)信息，運(yùn)用三邊測量法定位出未知節(jié)點(diǎn)的粗略初始位置，再運(yùn)用UKF算法完成定位。該算法在錨節(jié)點(diǎn)發(fā)送信標(biāo)信息密集時(shí)出現(xiàn)局部線性，使得該算法長時(shí)間選取不到不共線的信標(biāo)，無法及時(shí)得到初始位置，進(jìn)而使得運(yùn)行時(shí)間過長。

容積卡爾曼濾波（Cubature Kalman Filter，CKF）是Ienkaran Arasaratnam和Simon Haykin于2009年提出的一種濾波估計(jì)精度高、穩(wěn)定性好、計(jì)算量小的非線性濾波方法［8-9］。近年來有許多研究者對(duì)CKF算法進(jìn)行改進(jìn)，并應(yīng)用于列車導(dǎo)航定位、目標(biāo)跟蹤等領(lǐng)域，但目前還未見到研究者將其應(yīng)用于無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位中。

本文借鑒Liqiang Zhang等人所提算法的思想，將容積卡爾曼濾波運(yùn)用于無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位中，提出一種基于容積卡爾曼濾波的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)分布式定位算法。該算法的主要步驟為：移動(dòng)錨節(jié)點(diǎn)按預(yù)定路徑在傳感區(qū)域移動(dòng)，并周期性廣播自身位置信息；每個(gè)未知位置節(jié)點(diǎn)首先收集錨節(jié)點(diǎn)位置信息及對(duì)應(yīng)的信號(hào)強(qiáng)度信息，然后估算出錨節(jié)點(diǎn)與未知節(jié)點(diǎn)的距離，最后在未知節(jié)點(diǎn)上運(yùn)用CKF算法完成自身位置的定位。

本文首先給出移動(dòng)錨節(jié)點(diǎn)定位模型，然后分析了容積卡爾曼濾波算法的特點(diǎn)，給出了詳細(xì)的算法步驟，接著詳細(xì)介紹了基于CKF的WSN節(jié)點(diǎn)分布式定位的算法流程，最后建立仿真環(huán)境，仿真分析了測距誤差、錨節(jié)點(diǎn)信標(biāo)個(gè)數(shù)、初始位置對(duì)本文算法定位精度的影響，并與文獻(xiàn)［6］所提UKF算法及極大似然估計(jì)定位法的性能進(jìn)行了仿真比較。

1 移動(dòng)錨節(jié)點(diǎn)定位模型

假設(shè)無線傳感器網(wǎng)絡(luò)中有N個(gè)傳感器節(jié)點(diǎn)，第i （i=1,…,N）個(gè)傳感器節(jié)點(diǎn)在k時(shí)刻的系統(tǒng)狀態(tài)為Xi（k）=［Xi1（k）,Xi2（k）,Xi3（k）］T。本文考慮靜止的傳感器節(jié)點(diǎn)，則移動(dòng)錨節(jié)點(diǎn)定位系統(tǒng)的狀態(tài)方程和觀測方程如下：

取傳感器節(jié)點(diǎn)i在k時(shí)刻與移動(dòng)錨節(jié)點(diǎn)之間的距離作為觀測量，

2 容積卡爾曼濾波算法

卡爾曼濾波是最經(jīng)典的濾波估計(jì)方法，但只適用于線性觀測方程，擴(kuò)展卡爾曼濾波（Extended Kalman Filter，EKF）是傳統(tǒng)處理非線性方程的濾波估計(jì)方法，EKF能夠達(dá)到一階泰勒展式的精度，但在非線性度偏高的場合會(huì)出現(xiàn)濾波發(fā)散［10］。無跡卡爾曼濾波是一種求sigma點(diǎn)的非線性濾波方法，該算法精度高，能夠達(dá)到二階甚至三階泰勒展式的精度，但是該算法的主要弱點(diǎn)是不穩(wěn)定［11］。

容積卡爾曼濾波算法的基本思想仍然是一種“預(yù)測—校正”的經(jīng)典卡爾曼濾波結(jié)構(gòu)下的估計(jì)算法，它與EKF、UKF相同，同屬于高斯域貝葉斯濾波的結(jié)構(gòu)范疇，但是CKF因其實(shí)現(xiàn)簡單、非線性逼近特性強(qiáng)等優(yōu)點(diǎn)，在與傳統(tǒng)非線性算法策略的比較中具有極大的優(yōu)勢。CKF采用了UKF類似的點(diǎn)集近似分布方法，能夠獲得比EKF更高的非線性逼近性能［12］，當(dāng)UKF的參數(shù)κ=0時(shí)，CKF 與UKF的濾波性能一致［13-14］。相比于UKF，CKF具備的主要優(yōu)勢有［12］：對(duì)三維以上的狀態(tài)方程，濾波精度更高，可采用平方根策略求解，濾波穩(wěn)定性更優(yōu)。

容積卡爾曼濾波算法的基本步驟如下。

2.1 時(shí)間更新

①假設(shè)在k-1時(shí)刻的估計(jì)方差已知，對(duì)其分解得

②計(jì)算Cubature點(diǎn)

③計(jì)算更新后的Cubature點(diǎn)

④計(jì)算一步預(yù)測狀態(tài)

⑤計(jì)算一步預(yù)測誤差方差

2.2 測量更新

①對(duì)一步預(yù)測誤差方差進(jìn)行分解

②計(jì)算cubature點(diǎn)

③計(jì)算通過量測方程的Cubature點(diǎn)

④計(jì)算量測估計(jì)值

⑤計(jì)算更新后的量測誤差方差

⑥計(jì)算協(xié)方差

⑦計(jì)算卡爾曼濾波增益

⑧ 計(jì)算更新后的狀態(tài)

⑨ 計(jì)算相應(yīng)的估計(jì)誤差方差

3 基于CKF的WSN節(jié)點(diǎn)定位算法

在無線傳感器網(wǎng)絡(luò)中，移動(dòng)錨節(jié)點(diǎn)按規(guī)定的移動(dòng)路徑在傳感區(qū)域移動(dòng)，周期性廣播自身位置信息，每個(gè)未知節(jié)點(diǎn)收集錨節(jié)點(diǎn)位置信息并計(jì)算出錨節(jié)點(diǎn)與未知節(jié)點(diǎn)的距離，對(duì)每個(gè)未知節(jié)點(diǎn)獨(dú)立運(yùn)用容積卡爾曼濾波定位出自身位置坐標(biāo)。該算法的流程圖如圖1所示。

圖1 基于CKF的WSN節(jié)點(diǎn)定位算法流程圖

4 定位性能仿真分析

［6］的仿真場景，本文假設(shè)在1 000 m×1 000 m的傳感區(qū)域內(nèi)隨機(jī)布置N=200個(gè)傳感器節(jié)點(diǎn)。假設(shè)所有未知位置節(jié)點(diǎn)進(jìn)行迭代估計(jì)的初始位置設(shè)置為傳感區(qū)域的中心，即x（0）=（500,500），假設(shè)狀態(tài)過程噪聲方差矩陣為Q=diag（［0.001,0.001,0.001］），測 距 誤 差 為range_error=10%，觀測噪聲方差為 R=（700*2* range_error）2*sc，其中sc表示觀測噪聲方差放大因子，假設(shè) sc=0.01，初始位置噪聲方差矩陣為P=100*diag（［1,1,1］），取迭代次數(shù)，即移動(dòng)錨節(jié)點(diǎn)廣播信標(biāo)的個(gè)數(shù)為100，以下仿真中若未做特殊說明，初始條件不變。移動(dòng)錨節(jié)點(diǎn)在距離傳感區(qū)域100 m高的平面按圓心為（500 m，500 m）、半徑為700 m的圓形路徑移動(dòng)，該圓形覆蓋了整個(gè)傳感區(qū)域。錨節(jié)點(diǎn)每圈廣播信標(biāo)個(gè)數(shù)為beacons_per_round=15，在該仿真場景中，移動(dòng)錨節(jié)點(diǎn)在k時(shí)刻的坐標(biāo)表示為

假設(shè)距離測量值的誤差主要由高斯噪聲引起，則測量距離與真實(shí)距離之間的關(guān)系表示如下：

其中dˉ為測量距離，d為真實(shí)距離，range_error為［0,1］之間的一個(gè)固定值，randn（1）是標(biāo)準(zhǔn)的正態(tài)隨機(jī)變量。

本文選取平均定位誤差（Mean Positioning Error，MPE）作為定位精度評(píng)價(jià)標(biāo)準(zhǔn)，定義：位置節(jié)點(diǎn)的真實(shí)位置

算法的計(jì)算復(fù)雜性，即時(shí)間復(fù)雜度，是指執(zhí)行算法所需要的計(jì)算工作量，它定量描述了該算法的運(yùn)行時(shí)間，決定了算法的運(yùn)行時(shí)間長短，即計(jì)算復(fù)雜性越低，運(yùn)行時(shí)間越短，算法性能越優(yōu)。本文選取算法的運(yùn)行時(shí)間作為計(jì)算復(fù)雜性的評(píng)價(jià)標(biāo)準(zhǔn)。

4.1 測距誤差對(duì)定位精度的影響

測距的精確度對(duì)無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位有很大的影響，通常測距精度越高，定位的精度也越高，反之，測距精度越低，定位的精度也越低。本次仿真選取4種不同的測距誤差，range_error分別為5%、10%、15%、20%。仿真得出測距誤差對(duì)定位精度的影響如圖2所示。

圖2 測距誤差對(duì)定位精度的影響

由圖2可以看出錨節(jié)點(diǎn)信標(biāo)個(gè)數(shù)相同的情況下，隨著測距誤差的增加，定位精度降低。

4.2 錨節(jié)點(diǎn)信標(biāo)個(gè)數(shù)對(duì)定位精度的影響

由圖2可以看出，隨著錨節(jié)點(diǎn)信標(biāo)個(gè)數(shù)的增加，定位精度增高。然而，錨節(jié)點(diǎn)過多不僅會(huì)增加通信負(fù)荷，而且會(huì)加大每個(gè)傳感器節(jié)點(diǎn)的運(yùn)算量。本節(jié)研究錨節(jié)點(diǎn)信標(biāo)總數(shù)相同的情況下，錨節(jié)點(diǎn)每圈廣播信標(biāo)個(gè)數(shù)對(duì)定位精度的影響。設(shè)置錨節(jié)點(diǎn)每圈廣播信標(biāo)個(gè)數(shù)分別為15、60、240時(shí)，錨節(jié)點(diǎn)信標(biāo)個(gè)數(shù)與定位精度的關(guān)系如圖3。

圖3 錨節(jié)點(diǎn)每圈廣播信標(biāo)個(gè)數(shù)對(duì)定位精度的影響

由圖3可以看出錨節(jié)點(diǎn)總數(shù)固定的情況下，錨節(jié)點(diǎn)每圈廣播個(gè)數(shù)越少，定位精度越高，這主要是幾何精度因子對(duì)定位所產(chǎn)生的影響。

4.3 初始位置對(duì)定位精度的影響

初始參數(shù)對(duì)卡爾曼濾波的性能有著不可忽視的影響，不同的初始位置、位置方差、觀測噪聲方差、狀態(tài)噪聲方差都會(huì)對(duì)定位產(chǎn)生很大的影響。本次仿真取三邊測量法估計(jì)的初始位置、傳感區(qū)域的圓心（500，500）、圓外（1210，500）。圖4為不同的初始位置對(duì)定位精度的影響。

由圖4可以看出先運(yùn)用三邊測量法估計(jì)出未知位置節(jié)點(diǎn)的粗略初始位置，再進(jìn)行CKF迭代，其定位精度明顯高于于初始位置在圓心和圓外。

圖4 初始位置對(duì)定位精度的影響

4.4CKF、UKF、MLE定位算法比較

圖5仿真了CKF、UKF、MLE三種定位算法的定位精度比較。由圖5可以看出，CKF和UKF運(yùn)用于無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位，具有相同的定位精度，且高于MLE。圖6為對(duì)基于CKF的WSN節(jié)點(diǎn)定位算法和基于UKF的WSN節(jié)點(diǎn)定位算法分別進(jìn)行50次蒙特卡洛仿真，得出的運(yùn)行時(shí)間比較圖，本次仿真采樣的錨節(jié)點(diǎn)信標(biāo)總數(shù)為50個(gè)，仿真環(huán)境為Windows XP系統(tǒng)下的MATLAB R2010（a）。由圖6可以看出，CKF算法的運(yùn)行時(shí)間低于UKF算法，即CKF算法的計(jì)算復(fù)雜性低于UKF算法。

圖5 UKF、CKF、MLE的定位精度比較

圖6 CKF、UKF運(yùn)行時(shí)間比較

5 結(jié)論

本文研究無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位問題，提出一種基于容積卡爾曼濾波的無線傳感器網(wǎng)絡(luò)分布式定位算法。該算法無需節(jié)點(diǎn)間通信，具有較高的定位精度和較低的計(jì)算復(fù)雜性。仿真驗(yàn)證了本文算法的定位精度與UKF算法相同，明顯優(yōu)于極大似然估計(jì)定位算法，而計(jì)算復(fù)雜性則低于UKF算法。

參考文獻(xiàn)：

［1］ Akyildiz I F，Su W，Sankarasubramaniam Y，et al.Wireless Sensor Networks：A Survey［J］.Computer Networks，2002，38（4）：393-422.

［2］ Chong C Y，Kumar S P.Sensor Networks：Evolution，Opportunities，and Challenges［C］//Proceedings of the IEEE，2003：1247-1256.

［3］ 何國剛，鄧平.一種高斯噪聲下基于最大分散度的WSN半定規(guī)劃定位算法［J］.傳感技術(shù)學(xué)報(bào)，2012，25（8）：1004-1699.

［4］ 王靜，鄧平.一種基于邊松弛的大規(guī)模WSN分簇定位算法［J］.傳感技術(shù)學(xué)報(bào)，2013，26（5）：683-688.

［5］ Lingxuan Hu，David Evans.Localization for Mobile Sensor Networks［J］.MobiCom'04，2004：45-57.

［6］ Zhang Liqiang，Cheng Qiang，Wang Yingge，et al.A Novel Distributed Sensor Positioning System Using the Dual of Target Tracking ［J］.IEEE Transactions on Computers，2008，57（2）：246-260.

［7］ Hu Weiwei，Qin Huibin，Huang Haiyun.A Mobile Beacon Based Method for Wireless Sensor Networks Localization［C］//IEEE International Conference on Communication Technology Proceedings，2008：144-147.

［8］ Ienkaran Arasaratnam，Simon Haykin.Cubature Kalman Filters ［J］.IEEE Transaction on Automatic Control，2009，54（6）：1254-1269.

［9］ Ienkaran Arasaratnam，Simon Haykin，Thomas R Hurd.Cubature Kalman Filtering for Continuous-Discrete Systems：Theory and Simulations［J］.IEEE Transactions on Signal Processing，2010，58 （10）：4977-4993.

［10］Fred Daum.Nonlinear Filters：Beyond the Kalman Filter［J］. IEEE A&E Systems Magazine，2005，20（8）：57-69.

［11］Simon J Julier，Jeffrey K Uhlmann.Unscented Filtering and Nonlinear Estimation［C］//Proceedings of the IEEE，2004，92（3）：401-422.

［12］蔡伯根.低成本列控系統(tǒng)的列車組合定位理論與方法［D］.北京：北京交通大學(xué)，2010：54-58.

［13］Chang Lubin，Hu Baiqing，Li An，et al.Transformed Unscented Kalman Filter［J］.IEEE Transactions on Automatic Control，2013，58（1）：252-257.

［14］孫楓，唐李軍.Cubature卡爾曼濾波與Unscented卡爾曼濾波估計(jì)精度比較［J］.控制與決策，2013，28（2）：303-308.

余木琪（1989-），男，漢族，碩士研究生。主要從事無線傳感器網(wǎng)絡(luò)定位跟蹤技術(shù)的研究；

鄧 平（1964-），男，漢族，博士，教授。主要研究方向有無線網(wǎng)絡(luò)定位技術(shù)，現(xiàn)代信號(hào)處理，無線傳感器網(wǎng)絡(luò)等。

A Distributed Localization Algorithm Based on Cubature Kalman Filter in Wireless Sensor Networks

YU Muqi，DENG Ping*
（Key lab of information coding and transmission，Southwest JIAOTONG University，Chengdu 610031，China）

To improve the localization accuracy and decrease the computation complexity，a distributed node localization algorithm based on cubature kalman filter in wireless sensor networks is proposed.The algorithm supposes that a mobile beacon moves by predetermined trajectory around a sensor field，and periodically broadcasts its current location.Each sensor collects the location and RSS of beacons，measures the distance between itself and the beacon，and individually calculates their locations via a Cubature Kalman Filter algorithm.Simulations show that the proposed algorithm has a good localization performance，the localization accuracy is same to the UKF algorithm，better than the MLE localization algorithm，and the computation complexity is smaller than the UKF algorithm.

WSN；CKF；localization；moving beacon EEACC：7230

TP393

A

1004-1699（2015）07-1041-05

10.3969/j.issn.1004-1699.2015.07.017

2015-01-30 修改日期：2015-03-09