占 宏，黎善斌，胥布工

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

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

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

1 移動信標定位原理

1.1 虛擬信標位置分布

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

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

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

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

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

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

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

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

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

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

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

1.3 擴展卡爾曼濾波模型

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

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

1.3.2 觀察方程模型

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

式中:

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

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

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

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

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

3）計算EKF增益

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

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

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

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

2 算法設計

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

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

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

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

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

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

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

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

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

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

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

3 仿真結果與分析

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

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

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

圖1 移動信標最優(yōu)遍歷路徑圖

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

3.2 定位誤差分析

圖2 定位結果示意圖

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

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

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

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

4 小結

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

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

：

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

［6］李石堅，徐從富，楊旸，等.面向傳感器節(jié)點定位的移動信標路徑獲?。跩］.軟件學報，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節(jié)點定位研究［J］. 武漢理工大學學報，2007，29（8）:112-116.

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

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