基于EKF的無(wú)線傳感器網(wǎng)絡(luò)移動(dòng)信標(biāo)定位算法

占 宏，黎善斌，胥布工

（華南理工大學(xué)自動(dòng)化科學(xué)與工程學(xué)院，廣東廣州 510640）

無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的位置對(duì)于監(jiān)測(cè)信息至關(guān)重要，沒(méi)有位置信息的監(jiān)測(cè)數(shù)據(jù)通常毫無(wú)意義［1］。同時(shí)，傳感器網(wǎng)絡(luò)的布局、覆蓋以及目標(biāo)跟蹤等操作均取決于節(jié)點(diǎn)的有效定位。因此，節(jié)點(diǎn)位置的確定是無(wú)線傳感器網(wǎng)絡(luò)重要問(wèn)題之一。常用的基于靜態(tài)信標(biāo)的定位算法需要較高的信標(biāo)節(jié)點(diǎn)密度，增加了網(wǎng)絡(luò)定位成本。為此，一些研究者提出了使用移動(dòng)信標(biāo)節(jié)點(diǎn)輔助未知節(jié)點(diǎn)的定位機(jī)制以降低成本［2］。移動(dòng)信標(biāo)節(jié)點(diǎn)在移動(dòng)過(guò)程中產(chǎn)生眾多虛擬信標(biāo)點(diǎn)輔助定位，從而實(shí)現(xiàn)對(duì)未知節(jié)點(diǎn)更加精確的位置估計(jì)。

基于移動(dòng)信標(biāo)定位思想，文獻(xiàn)［3］中Ssu等由幾何學(xué)中“弦的垂直平分線通過(guò)圓心”這一性質(zhì)，提出了一種非測(cè)距的移動(dòng)信標(biāo)輔助定位機(jī)制，但該方法需滿足移動(dòng)信標(biāo)節(jié)點(diǎn)剛好通過(guò)未知節(jié)點(diǎn)的通信圓周，不能實(shí)現(xiàn)大范圍的節(jié)點(diǎn)定位，定位效率低。Hu等在文獻(xiàn)［4］中提出移動(dòng)信標(biāo)沿螺旋線軌跡運(yùn)動(dòng)，采用質(zhì)心定位算法得到未知節(jié)點(diǎn)的估計(jì)位置坐標(biāo)。螺旋線模型是一種簡(jiǎn)單可行的信標(biāo)移動(dòng)路徑，但是因其無(wú)法有效地覆蓋全部傳感區(qū)域，易出現(xiàn)信標(biāo)覆蓋盲區(qū)，降低了定位精度?？锱d紅等［5］提出一種新的分布式節(jié)點(diǎn)定位算法——移動(dòng)錨節(jié)點(diǎn)極大似然算法（MAP-MLE），該算法中移動(dòng)信標(biāo)節(jié)點(diǎn)采用可調(diào)參數(shù)多、靈活性很大、網(wǎng)絡(luò)覆蓋度高的高斯-馬爾可夫（Gauss-Markov）模型，但其信標(biāo)節(jié)點(diǎn)移動(dòng)路徑較長(zhǎng)，功耗大。為此，本文根據(jù)等距三重覆蓋思想確定矩形傳感區(qū)域中虛擬信標(biāo)的位置分布，利用蟻群算法得到遍歷虛擬信標(biāo)的最優(yōu)路徑，同時(shí)引入擴(kuò)展卡爾曼濾波（EKF）以提高算法定位精度。

1 移動(dòng)信標(biāo)定位原理

1.1 虛擬信標(biāo)位置分布

虛擬信標(biāo)的選擇需要考慮傳感區(qū)域中未知節(jié)點(diǎn)均可接收到3個(gè)以上不同虛擬信標(biāo)數(shù)據(jù)包，以保證各節(jié)點(diǎn)實(shí)現(xiàn)定位，同時(shí)虛擬信標(biāo)位置應(yīng)盡可能少以減少定位時(shí)間，降低能量消耗［6-7］。

根據(jù)等距三重優(yōu)化覆蓋思想，當(dāng)傳感區(qū)域?yàn)榫匦吻掖笮锳×B，節(jié)點(diǎn)通信半徑為r時(shí)，可得到虛擬信標(biāo)發(fā)射位置坐標(biāo)，步驟如下［6］。

1） 根據(jù)A和B分別計(jì)算每行中虛擬信標(biāo)的數(shù)量行數(shù)imax。

2） 計(jì)算第i行和第j列虛擬信標(biāo)位置橫坐標(biāo)xij、縱坐標(biāo)yij

如計(jì)算出的坐標(biāo)超出了區(qū)域（A×B）邊界時(shí)，則直接用相應(yīng)邊界線坐標(biāo)替換其坐標(biāo)。

1.2 最優(yōu)路徑獲取

獲取遍歷所有虛擬信標(biāo)點(diǎn)最優(yōu)路徑問(wèn)題可看成是典型的旅行商問(wèn)題（Traveling Salesman Problem，TSP），虛擬信標(biāo)點(diǎn)相當(dāng)于TSP中的城市，確定一條經(jīng)過(guò)各虛擬信標(biāo)點(diǎn)當(dāng)且僅當(dāng)一次的最短路線，可采用蟻群算法來(lái)求解［8-9］。

設(shè)m為虛擬信標(biāo)點(diǎn)數(shù)量，dij為虛擬信標(biāo)點(diǎn)i和j的距離，τij（t）為t時(shí)刻殘留在i與j連線上的信息素量。t=0時(shí)，將m只螞蟻隨機(jī)放置在n個(gè)虛擬信標(biāo)點(diǎn)中的m個(gè)點(diǎn)上，設(shè)τij（0）=C（C為常數(shù)）。螞蟻k（k=1，2，…，m） 根據(jù)各條路徑上的信息素量決定轉(zhuǎn)移方向。設(shè)Pkij（t）為t時(shí)刻螞蟻k由虛擬信標(biāo)點(diǎn)i轉(zhuǎn)移到j(luò)的概率

式中:ηij為啟發(fā)函數(shù)，由兩個(gè)虛擬信標(biāo)點(diǎn)間的距離dij決定，表達(dá)式為

式（5）中:α和β為參數(shù)因子;allowedk是tabuk中除虛擬信標(biāo)點(diǎn)之外的信標(biāo)點(diǎn)，tabuk為螞蟻k的禁忌表，記錄了t時(shí)刻螞蟻k已走過(guò)的虛擬信標(biāo)點(diǎn)，防止其在本次循環(huán)中再次訪問(wèn)這些信標(biāo)點(diǎn)，循環(huán)結(jié)束時(shí)禁忌表將被清空。τij（t+n）為t+n時(shí)刻螞蟻殘留在路徑（i，j）上的信息素量;Δτij（t）為信息素量增量;（1－ρ）為信息素軌跡殘留因子，為避免路徑上信息素量的無(wú)限累積，通常設(shè)ρ＜1。螞蟻完成一次循環(huán)，各路徑上的信息素量根據(jù)以下兩式進(jìn)行調(diào)整

式中，Δ的計(jì)算采取Ant cycle system模型

1.3 擴(kuò)展卡爾曼濾波模型

1.3.1 狀態(tài)方程模型

式中:Xk=［xkyk］T為未知節(jié)點(diǎn)在第k－1個(gè)信標(biāo)位置進(jìn)行濾波后的坐標(biāo)向量。wk是測(cè)量過(guò)程噪聲，A為二階單位矩陣。

1.3.2 觀察方程模型

文中采用未知節(jié)點(diǎn)接收到移動(dòng)信標(biāo)信號(hào)時(shí)的RSSI值作為EKF的觀察量。觀察方程為

式中:

H為g（Xk）的Jacobian矩陣，即

式中:dk為未知節(jié)點(diǎn)到第k個(gè)虛擬信標(biāo)的距離，P為發(fā)射功率，G為天線接收增益，n為路徑衰減因子，范圍為2～5，（xbk，ybk）為未知節(jié)點(diǎn)收到第k個(gè)信標(biāo)的坐標(biāo)，vk為觀察噪聲，根據(jù)文獻(xiàn)［10］設(shè)σ1為4～10。

根據(jù)狀態(tài)方程和觀察方程，得EKF計(jì)算過(guò)程［11］。

1）利用系統(tǒng)上一狀態(tài)預(yù)測(cè)現(xiàn)在的狀態(tài)

2）更新系統(tǒng)現(xiàn)在狀態(tài)的協(xié)方差矩陣

3）計(jì)算EKF增益

4）結(jié)合預(yù)測(cè)值和觀察值，估計(jì)現(xiàn)在狀態(tài)的最優(yōu)估計(jì)值

5）更新現(xiàn)在最優(yōu)估計(jì)值的協(xié)方差

6）循環(huán)迭代，返回步驟1。

式中:Q為過(guò)程噪聲協(xié)方差矩陣，Q=0，R=為觀察噪聲協(xié)方差矩陣，σ1為高斯分布vk的標(biāo)準(zhǔn)差。

2 算法設(shè)計(jì)

根據(jù)上述移動(dòng)信標(biāo)輔助定位機(jī)制，本文算法具體步驟如下。

1）由式（1）（2）確定傳感器區(qū)域（A×B）虛擬信標(biāo)位置的分布;

2）采用蟻群算法得到最優(yōu)遍歷路徑;

3）移動(dòng)信標(biāo)按照最優(yōu)路徑遍歷傳感區(qū)域，并在虛擬信標(biāo)點(diǎn)發(fā)送定位數(shù)據(jù)包;

4）未知節(jié)點(diǎn)接收信標(biāo)信息，并只存儲(chǔ)RSSI值最高的前 s個(gè)信標(biāo)點(diǎn)位置信息，［（xi，yi）;RSSIi］;

5）未知節(jié)點(diǎn)對(duì)收到的信標(biāo)節(jié)點(diǎn)信號(hào)依其RSSI值從大到小排序，并建立以下3個(gè)集合:

（1） 信標(biāo)點(diǎn)RSSI集合，Beacon_set={RSSI1，RSSI2，…，RSSIs}，RSSI1≥RSSI2≥…≥RSSIs;

（2）未知節(jié)點(diǎn)與各信標(biāo)點(diǎn)的距離集合，Distance_set={d1，d2，…，ds};

（3）信標(biāo)點(diǎn)位置坐標(biāo)集合:Position_set={（xb1，yb1），（xb2，yb2），…，（xbs，ybs）}。

6）采用加權(quán)質(zhì)心算法得到未知節(jié)點(diǎn)的近似估計(jì)坐標(biāo)（xest，yest） ，即

7）將該近似估計(jì)坐標(biāo)作為EKF的初始狀態(tài)，采用EKF得出未知節(jié)點(diǎn)的精確估計(jì)坐標(biāo)。

3 仿真結(jié)果與分析

3.1 虛擬信標(biāo)分布及最優(yōu)路徑

設(shè)傳感器區(qū)域S（50 m×50 m），節(jié)點(diǎn)通信半徑為r=10 m時(shí)，由1.1中的方法得到42個(gè)虛擬信標(biāo)點(diǎn)。采用蟻群算法得到移動(dòng)信標(biāo)最優(yōu)遍歷路徑如圖1所示，路徑總長(zhǎng)度為391.25 m。

本文對(duì)不同的節(jié)點(diǎn)通信半徑所對(duì)應(yīng)的虛擬信標(biāo)節(jié)點(diǎn)數(shù)目和遍歷路徑長(zhǎng)度進(jìn)行了比較，結(jié)果如表1所示。從該表中可以得出，節(jié)點(diǎn)通信半徑越大，虛擬信標(biāo)點(diǎn)的數(shù)目越少，遍歷路徑越長(zhǎng)。

圖1 移動(dòng)信標(biāo)最優(yōu)遍歷路徑圖

表1 虛擬信標(biāo)點(diǎn)和遍歷路徑長(zhǎng)度比較

3.2 定位誤差分析

圖2 定位結(jié)果示意圖

圖3是傳感器節(jié)點(diǎn)通信半徑取不同值時(shí)，加入EKF后的算法與普通加權(quán)質(zhì)心定位算法的平均定位誤差比較。從圖中可以看出，對(duì)于相同的節(jié)點(diǎn)通信半徑，本文算法的定位誤差明顯小于加權(quán)質(zhì)心算法的誤差;由于節(jié)點(diǎn)通信半徑越小，虛擬信標(biāo)點(diǎn)越多，即信標(biāo)節(jié)點(diǎn)密度高，因此其定位誤差越小。

圖3 不同通信半徑時(shí)的定位誤差比較

由于EKF的精度與迭代次數(shù)有關(guān)，本文通過(guò)仿真得出了s的取值對(duì)算法定位精度的影響，結(jié)果如圖4所示。由圖可知，加權(quán)質(zhì)心算法由于不能消除測(cè)量RSSI值誤差的影響，其定位誤差隨s的增大而增大。而迭代次數(shù)s的取值越大，本文算法的平均定位誤差越小，當(dāng)s=7時(shí)，定位誤差最小為1.04 m;當(dāng)s＞7時(shí)，定位誤差由于受測(cè)量RSSI值的影響，誤差增大。

圖4 迭代次數(shù)與平均定位誤差的比較

4 小結(jié)

本文采用等距三重覆蓋思想得出矩形傳感區(qū)域的虛擬信標(biāo)點(diǎn)的位置分布，提高了網(wǎng)絡(luò)覆蓋度，利用蟻群算法獲取移動(dòng)信標(biāo)最優(yōu)遍歷路徑，降低了網(wǎng)絡(luò)成本及功耗，同時(shí)采用擴(kuò)展卡爾曼濾波方法提高了定位精度。當(dāng)?shù)?次時(shí)，其定位誤差最小為1.04 m。

由于移動(dòng)信標(biāo)節(jié)點(diǎn)的路徑規(guī)劃是保證定位效果和效率的關(guān)鍵所在，因此基于本文下一步的研究主要是確定更優(yōu)的移動(dòng)信標(biāo)運(yùn)動(dòng)模型，同時(shí)降低算法復(fù)雜度。

：

［1］章浩，李萍萍，張西良.無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位機(jī)制研究［J］.電視技術(shù)，2006，30（10）:71-73.

［2］SUN GuoLin，GUO Wei.Comparison of distributed localization algorithms for sensor network with a mobile beacon，in Networking［C］//Proc.2004 IEEE International Conference on Sensing and Control.［S.l.］:IEEE Press，2004:536-540.

［3］SSU K F，OU C H，JIAU H C.Localization with mobile anchor points in wireless sensor networks［J］.IEEE Transactions on Vehicular Technology，2005，54（3）:1187-1197.

［4］HU Zhen，GU Dongbing，SONG Zhengxun，et al.Localization in wireless sensor networks using a mobile anchor node［C］//Proc.IEEE/ASME International Conference on Advanced Intelligent Mechatronics.［S.l.］:IEEE Press ，2008:602-607.

［5］匡興紅，邵惠鶴.一種新的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法研究［J］.傳感技術(shù)學(xué)報(bào)，2008，21（1）:174-177.

［6］李石堅(jiān)，徐從富，楊旸，等.面向傳感器節(jié)點(diǎn)定位的移動(dòng)信標(biāo)路徑獲?。跩］.軟件學(xué)報(bào)，2008，19（2）:455-467.

［7］SICHITIU M L，RAMADURAI V.Localization of wireless sensor networks with a mobile beacon［C］//Proc.2004 IEEE International Conference on Mobile Ad-hoc and Sensor Systems.［S.l.］:IEEE Press，2004:174-183.

［8］徐云劍，彭沛夫，郭艾寅，等.基于蟻群算法的WSN移動(dòng)信標(biāo)路徑獲取研究［J］.計(jì)算機(jī)工程與應(yīng)用，2008，44（28）:113-116.

［9］QIN F，CHEN W，LIU K Z，et al.，Study on mobile beacon trajectory for node localization in wireless sensor networks［C］//Proc.2010 IEEE International Conference on Information and Automation.Harbin，China:IEEE Press，2010:1577-1581.

［10］陳維克，李文鋒，首珩，等.基于卡爾曼濾波的WSNs節(jié)點(diǎn)定位研究［J］. 武漢理工大學(xué)學(xué)報(bào)，2007，29（8）:112-116.

［11］付夢(mèng)印，鄧志紅，張繼偉.Kalman濾波理論及其在導(dǎo)航系統(tǒng)中的應(yīng)用［M］.北京:科學(xué)出版社，2003.

［12］RAPPAPORT T S，RAPPAPORT T.Wireless communications:Principles and practice［M］.2nd Ed.New Jersey:Prentice Hall PTR，2002.