基于EKF的無線傳感器網絡移動信標定位算法

占 宏，黎善斌，胥布工

（華南理工大學自動化科學與工程學院，廣東廣州 510640）

無線傳感器網絡中節點的位置對于監測信息至關重要，沒有位置信息的監測數據通常毫無意義［1］。同時，傳感器網絡的布局、覆蓋以及目標跟蹤等操作均取決于節點的有效定位。因此，節點位置的確定是無線傳感器網絡重要問題之一。常用的基于靜態信標的定位算法需要較高的信標節點密度，增加了網絡定位成本。為此，一些研究者提出了使用移動信標節點輔助未知節點的定位機制以降低成本［2］。移動信標節點在移動過程中產生眾多虛擬信標點輔助定位，從而實現對未知節點更加精確的位置估計。

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

1 移動信標定位原理

1.1 虛擬信標位置分布

虛擬信標的選擇需要考慮傳感區域中未知節點均可接收到3個以上不同虛擬信標數據包，以保證各節點實現定位，同時虛擬信標位置應盡可能少以減少定位時間，降低能量消耗［6-7］。

根據等距三重優化覆蓋思想，當傳感區域為矩形且大小為A×B，節點通信半徑為r時，可得到虛擬信標發射位置坐標，步驟如下［6］。

1） 根據A和B分別計算每行中虛擬信標的數量行數imax。

2） 計算第i行和第j列虛擬信標位置橫坐標xij、縱坐標yij

如計算出的坐標超出了區域（A×B）邊界時，則直接用相應邊界線坐標替換其坐標。

1.2 最優路徑獲取

獲取遍歷所有虛擬信標點最優路徑問題可看成是典型的旅行商問題（Traveling Salesman Problem，TSP），虛擬信標點相當于TSP中的城市，確定一條經過各虛擬信標點當且僅當一次的最短路線，可采用蟻群算法來求解［8-9］。

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

式中:ηij為啟發函數，由兩個虛擬信標點間的距離dij決定，表達式為

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

式中，Δ的計算采取Ant cycle system模型

1.3 擴展卡爾曼濾波模型

1.3.1 狀態方程模型

式中:Xk=［xkyk］T為未知節點在第k－1個信標位置進行濾波后的坐標向量。wk是測量過程噪聲，A為二階單位矩陣。

1.3.2 觀察方程模型

文中采用未知節點接收到移動信標信號時的RSSI值作為EKF的觀察量。觀察方程為

式中:

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

式中:dk為未知節點到第k個虛擬信標的距離，P為發射功率，G為天線接收增益，n為路徑衰減因子，范圍為2～5，（xbk，ybk）為未知節點收到第k個信標的坐標，vk為觀察噪聲，根據文獻［10］設σ1為4～10。

根據狀態方程和觀察方程，得EKF計算過程［11］。

1）利用系統上一狀態預測現在的狀態

2）更新系統現在狀態的協方差矩陣

3）計算EKF增益

4）結合預測值和觀察值，估計現在狀態的最優估計值

5）更新現在最優估計值的協方差

6）循環迭代，返回步驟1。

式中:Q為過程噪聲協方差矩陣，Q=0，R=為觀察噪聲協方差矩陣，σ1為高斯分布vk的標準差。

2 算法設計

根據上述移動信標輔助定位機制，本文算法具體步驟如下。

1）由式（1）（2）確定傳感器區域（A×B）虛擬信標位置的分布;

2）采用蟻群算法得到最優遍歷路徑;

3）移動信標按照最優路徑遍歷傳感區域，并在虛擬信標點發送定位數據包;

4）未知節點接收信標信息，并只存儲RSSI值最高的前 s個信標點位置信息，［（xi，yi）;RSSIi］;

5）未知節點對收到的信標節點信號依其RSSI值從大到小排序，并建立以下3個集合:

（1） 信標點RSSI集合，Beacon_set={RSSI1，RSSI2，…，RSSIs}，RSSI1≥RSSI2≥…≥RSSIs;

（2）未知節點與各信標點的距離集合，Distance_set={d1，d2，…，ds};

（3）信標點位置坐標集合:Position_set={（xb1，yb1），（xb2，yb2），…，（xbs，ybs）}。

6）采用加權質心算法得到未知節點的近似估計坐標（xest，yest） ，即

7）將該近似估計坐標作為EKF的初始狀態，采用EKF得出未知節點的精確估計坐標。

3 仿真結果與分析

3.1 虛擬信標分布及最優路徑

設傳感器區域S（50 m×50 m），節點通信半徑為r=10 m時，由1.1中的方法得到42個虛擬信標點。采用蟻群算法得到移動信標最優遍歷路徑如圖1所示，路徑總長度為391.25 m。

本文對不同的節點通信半徑所對應的虛擬信標節點數目和遍歷路徑長度進行了比較，結果如表1所示。從該表中可以得出，節點通信半徑越大，虛擬信標點的數目越少，遍歷路徑越長。

圖1 移動信標最優遍歷路徑圖

表1 虛擬信標點和遍歷路徑長度比較

3.2 定位誤差分析

圖2 定位結果示意圖

圖3是傳感器節點通信半徑取不同值時，加入EKF后的算法與普通加權質心定位算法的平均定位誤差比較。從圖中可以看出，對于相同的節點通信半徑，本文算法的定位誤差明顯小于加權質心算法的誤差;由于節點通信半徑越小，虛擬信標點越多，即信標節點密度高，因此其定位誤差越小。

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

由于EKF的精度與迭代次數有關，本文通過仿真得出了s的取值對算法定位精度的影響，結果如圖4所示。由圖可知，加權質心算法由于不能消除測量RSSI值誤差的影響，其定位誤差隨s的增大而增大。而迭代次數s的取值越大，本文算法的平均定位誤差越小，當s=7時，定位誤差最小為1.04 m;當s＞7時，定位誤差由于受測量RSSI值的影響，誤差增大。

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

4 小結

本文采用等距三重覆蓋思想得出矩形傳感區域的虛擬信標點的位置分布，提高了網絡覆蓋度，利用蟻群算法獲取移動信標最優遍歷路徑，降低了網絡成本及功耗，同時采用擴展卡爾曼濾波方法提高了定位精度。當迭代7次時，其定位誤差最小為1.04 m。

由于移動信標節點的路徑規劃是保證定位效果和效率的關鍵所在，因此基于本文下一步的研究主要是確定更優的移動信標運動模型，同時降低算法復雜度。

：

［1］章浩，李萍萍，張西良.無線傳感器網絡節點定位機制研究［J］.電視技術，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］匡興紅，邵惠鶴.一種新的無線傳感器網絡節點定位算法研究［J］.傳感技術學報，2008，21（1）:174-177.

［6］李石堅，徐從富，楊旸，等.面向傳感器節點定位的移動信標路徑獲取［J］.軟件學報，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移動信標路徑獲取研究［J］.計算機工程與應用，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節點定位研究［J］. 武漢理工大學學報，2007，29（8）:112-116.

［11］付夢印，鄧志紅，張繼偉.Kalman濾波理論及其在導航系統中的應用［M］.北京:科學出版社，2003.

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