基于能量高效動態分簇的目標跟蹤算法

陸 嫻,彭 勇

(江南大學物聯網工程學院,江蘇無錫214122)

基于能量高效動態分簇的目標跟蹤算法

陸 嫻,彭 勇

(江南大學物聯網工程學院,江蘇無錫214122)

目標跟蹤是無線傳感器網絡中的一項基本應用,如何在保證高跟蹤精度的前提下降低網絡能耗、延長網絡生命周期是目標跟蹤的核心問題。為此,提出一種基于能量高效動態分簇的目標跟蹤算法。從最大限度節省能量的角度出發,設計動態簇生成方法,利用無跡粒子濾波算法對目標進行跟蹤,預測下一時刻目標的位置坐標,并根據預測結果給出簇頭更換策略。仿真結果表明,與PPF和DPF算法相比,該算法不僅具有較高的目標跟蹤精度,而且能有效降低網絡能耗,延長網絡壽命。

無線傳感器網絡;目標跟蹤;無跡粒子濾波算法;動態分簇;接收信號強度指示模型;無跡卡爾曼濾波算法

1 概述

無線傳感器網絡(Wireless Sensor Network, WSN)由大量具有信息感知、采集、處理和無線通信能力的傳感器節點組成[1]。由于傳感器組成的網絡具有自組織性、魯棒性和隱蔽性等特點,使得無線傳感網非常適合移動目標的跟蹤,同時其也為目標跟蹤技術提供了一種全新的解決方案和研究方向。

無線傳感器網絡有集中式和分布式 2種結構[2-3]。集中式跟蹤[4]是全部參與目標跟蹤的傳感器節點將局部量測信息傳送到計算中心,再由計算中心完成對目標的狀態估計;分布式跟蹤[5]是參與目標跟蹤的傳感器節點之間相互交換和協調局部量測信息,并在本地完成對目標的狀態估計。前者結構簡單但易使單個節點能量耗盡,導致網絡節點分布不均勻而影響整個網絡的跟蹤性能;后者結構復雜但能均衡網絡能耗,因此本文在分布式結構的基礎上提出一種新的動態簇生成方法,從而降低網絡能耗。

在通常情況下,目標跟蹤系統是非線性非高斯的,并且大部分傳統的目標跟蹤算法存在對參數過于敏感的缺點[6-7],而粒子濾波不受線性化誤差和高斯噪聲假設的限制,適用于大多數環境下的狀態轉換或測量模型[8],因此粒子濾波算法應用在目標跟蹤中的思想應運而生。雖然粒子濾波算法適合處理非線性非高斯系統的狀態估計問題,但它存在著粒子退化的缺陷。針對粒子濾波的缺陷,目前處理較好的是無跡粒子濾波(Unscented Particle Filtering,UPF)算法,本文采用該算法來實現簇對目標的跟蹤。

為進一步提高網絡能量利用率、延長網絡壽命,本文提出一種基于能量高效動態分簇的目標跟蹤算法,設計動態簇生成方法和簇頭更換策略,從而在確保較高跟蹤精度的基礎上,降低整個網絡能耗。

2 模型與假設

2.1 網絡模型

由于無線網絡中的傳感器節點受到資源限制和環境噪聲的影響,因此為了更好模擬現實環境,本文采用了接收信號強度指示(Received Signal Strength Indications,RSSI)模型[9]。假設無線傳感器網絡中的傳感器節點是隨機部署在監測區域內的,并且每個傳感器節點都裝有接收信號強度指示器。感知節點可以通過接收的信號強度值來探測目標并估計自身到目標的距離?，F假設運動目標在監測區域內運動,則在k時刻第i個傳感器節點從目標接收的信號強度為:

2.2 目標運動模型

目標運動模型是跟蹤算法的基礎,跟蹤的目的是估計出目標的狀態。對于無線傳感器網絡中的單目標跟蹤,本文采用狀態空間模型來表示目標運動模型[9]:假設隨機部署N個傳感器節點在網絡中,每個節點的位置坐標已知,為(xi,yi),i∈{1,2,…,N},則目標運動模型可以表示為:

其中,Xk為目標在k時刻的狀態向量,Xk=(xk,yk,vx,k,vy,k)T;(xk,yk)為目標在k時刻的位置坐標; (vx,k,vy,k)表示目標在k時刻的速度;F為狀態轉移矩陣,即表示目標在k時刻與k+1時刻的狀態轉換關系;wk為系統噪聲。

傳感器節點對目標的觀測方程為:

其中,Zk為k時刻節點對目標的觀測向量;H為觀測模型矩陣;vk表示觀測噪聲。

3 能量高效的動態分簇

3.1 新的動態簇生成方法

傳統網絡動態分簇的基本思想是[10]:當多個感知節點檢測到運動目標時,感知節點之間通過相互交換信息選取出離運動目標最近的節點作為簇頭,并以簇頭為中心,簇頭最大通信距離為半徑的范圍內的所有感知節點組成一個簇。雖然傳統動態簇結構可以降低網絡能耗,但并不是一種能量高效的方法,并沒有最大限度的節省網絡節點能量。傳統動態分簇方法易產生對運動目標跟蹤無實際貢獻的感知節點仍處于工作狀態而浪費能量的問題,從而使得網絡能量利用率低,如圖1所示。其中,L為感知節點跟蹤目標達到跟蹤精度要求的一個距離閾值;D為簇頭到運動目標的距離;R為簇頭節點最大的通信半徑,以簇頭為中心;R為半徑的圓內所有的感知節點組成一個簇。

圖1 傳統動態分簇策略

可以看出,節點1～節點4到運動目標的距離超過了閾值L,這些節點實質上對目標的跟蹤無意義,甚至會降低跟蹤的精度。從節省能量的角度出發,這些節點也不應該處于工作狀態,浪費能量。文獻[11-12]是通過設定閾值來降低能耗的,但閾值的選取本身就有難度,取得偏大或偏小都會影響跟蹤性能,針對以上問題,本文提出了新動態簇生成方法。

新動態簇生成方法使得對目標跟蹤無實際貢獻的感知節點不被劃分在動態簇內,從而節省網絡能量。該方法設計思路如下:當運動目標進入監測區域時,多個感知節點均能檢測到運動目標,感知節點間通過相互交換信息,選取出從運動目標接收的信號強度最大和次大的節點作為主簇頭和次簇頭,再分別以主簇頭和次簇頭為中心,感知節點的最大通信距離為半徑,作2個圓,最后使兩圓的相交區域內的所有感知節點組成一個簇,如圖2所示。其中,S1為主簇頭從目標接收的信號強度;S2為次簇頭從目標接收的信號強度;R為網絡中感知節點的最大通信半徑;虛線表示的區域為以S1,S2為中心,R為半徑的兩圓的交集,該區域內的所有感知節點組成一個簇,該簇使得跟蹤節點只占所有能探測到目標節點的一部分,從而減少了無貢獻節點的能耗和通信能量。

圖2 動態分簇方法示意圖

上述新的動態分簇方法從節省能量的角度避免了在目標跟蹤過程中無實際意義的感知節點仍處于工作狀態的問題,生成了一個能量高效的動態簇結構。該結構使得跟蹤節點只占所有能探測到目標節點的一部分,降低了跟蹤簇的能量消耗,從而提高了整個網絡的能量利用率,同時在一定程度上也提高了跟蹤精度。

3.2 簇頭更換策略

假設在時刻k,動態簇結構為:

Cluster(k)={FCH(k),SCH(k),cn1,cn2,…,cnn}其中,FCH(k)為主簇頭;SCH(k)為次簇頭;其余節點為簇內成員,當簇結構處于跟蹤狀態時,次簇頭等同于普通簇成員。在目標跟蹤時,簇內各成員節點分別利用UPF算法估計目標的狀態信息,并把估計結果傳遞給主簇頭節點,主簇頭對這些數據進行融合,估計出目標的位置坐標和運動速度等狀態信息,并預測出k+1時刻目標的位置坐標,最后根據預測的位置值決定簇頭節點是否更換。

假設預測的目標位置坐標為Tk+1(Txk+1,Tyk+1),則根據以下規則來更新簇頭:

規則1 如果Tk+1既位于主簇頭的覆蓋范圍之內,又位于次簇頭的覆蓋范圍之內,則不更新主簇頭和次簇頭,仍在當前簇內對目標進行跟蹤。

規則2 如果Tk+1位于主簇頭的覆蓋范圍之外,則不考慮預測的目標位置與次簇頭的關系,直接喚醒與k+1時刻目標位置最近和第二近的節點,作為新的主簇頭節點FCH(k+1)和次簇頭節點SCH(k+1),并按3.1節介紹的方法重新構建簇結構,選擇新的簇成員節點。同時當前主簇頭FCH(k)將當前時刻的跟蹤參數傳遞給新的主簇頭節點FCH(k+1)。

規則3 如果Tk+1位于主簇頭的覆蓋范圍之內但位于次簇頭的覆蓋范圍之外,則不更換主簇頭,但要更新次簇頭,以及重新構建簇結構。即喚醒在主簇頭覆蓋范圍內離目標位置最近的節點作為新的次簇頭節點SCH(k+1),并按3.1節介紹的方法生成新簇來更新當前簇結構。新的簇結構在k+1時刻對目標進行跟蹤。

圖3給出了簇頭更換策略的具體情況,其中,圖3(a)表示規則1發生的情況;圖3(b)表示規則2發生,主次簇頭更換的情況;圖3(c)表示規則3發生,次簇頭更新的情況。

圖3 簇頭更換策略示意圖

本文給出的簇頭更換策略能隨著目標的運動,及時地更新簇頭和選擇新的簇成員節點,從而能夠對目標進行準確、連續的跟蹤。

4 動態分簇目標跟蹤算法

上文詳細論述了能量高效的動態分簇方法,本節重點介紹基于該方法的目標跟蹤算法。由3.1節生成的動態簇采用UPF算法對目標進行跟蹤。UPF算法[13-14]利用無跡卡爾曼濾波(Unscented Kalman Filtering,UKF)算法[15]產生重要性分布函數來改進粒子濾波,從而得到更為接近真實結果的后驗概率分布。

假設k時刻分配到簇成員節點i上的粒子數目為N,Xj表示粒子j的狀態值,Wj為粒子j的權值,Zj表示粒子j的觀測值,則動態分簇目標跟蹤算法具體實現流程如下:

(1)初始化

假設k=0時刻,目標進入傳感器網絡,網絡中檢測到該目標的感知節點通過相互交換信息選取出主簇頭和次簇頭,并按3.1節介紹的方法生成簇。在簇處于跟蹤狀態時,次簇頭節點等同于普通簇成員節點,探測目標并將數據傳遞給主簇頭。假設當前簇內有n個成員節點,主簇頭節點分配給每個成員節點的粒子數目為N,則有:

(2)粒子重要性采樣

從重要性分布函數中抽取粒子,即新樣本:

計算k時刻每個粒子的權值:

(3)成員節點狀態估計

第i個成員節點根據得到的新樣本的序列和樣本權值分別計算出N個樣本的加權和、協方差以及權值和:

(4)節點信息上傳

(5)重采樣

如果有效粒子數低于指定閾值時,則重采樣粒子集,各成員節點收到重采樣消息后,獨立進行采樣過程:

(6)簇頭節點數據融合

主簇頭將每個簇成員節點傳送來的狀態信息進行融合處理:

(7)預測k+1時刻的目標位置

主簇頭節點在完成數據融合后,計算k+1時刻目標位置的預測值xk+1|k:

(8)簇的動態更新

主簇頭節點根據預測的目標位置值xk+1|k和3.2節介紹的簇頭更換策略來判定簇是否需要更新。如果簇結構不需要更新,轉到步驟(2)繼續在當前簇內對目標進行跟蹤,否則更換主次簇頭節點并在新建的簇結構內跟蹤目標。同時,當前簇的主簇頭節點將狀態信息{xk,wk}傳送給新的主簇頭節點,并解散簇,簇成員節點關閉通信模塊,轉入休眠狀態,新的簇在下一時刻對目標進行跟蹤。

整個算法的框架如圖4所示,其中,(Lx1,Ly1), (Lx2,Ly2)分別表示主簇頭、次簇頭的坐標。

圖4 基于能量高效動態分簇的目標跟蹤算法框架

5 仿真實驗與結果分析

仿真實驗中,仿真場景為在1 000 m×1 000 m的方形區域中隨機部署200個傳感器節點組成無線傳感網,并假設網絡中的所有節點具有相同的功能和性能,節點的通信半徑為50 m。假設存在一目標節點,該目標運動符合2.2節介紹的模型,則目標節點X軸方向上的運動狀態為:

Y軸方向上的運動狀態為:

其中,t為采樣間隔,取1 s;Xk-1′(t),Yk-1′(t)分別為X,Y方向上的狀態更新方程;a(t),v(t)分別表示加速度和速度;ω取0.02;αk-1,βk-1為運動過程產生的噪聲,其中αk-1～N(0,10),βk-1～N(0,5)。目標起始位置的狀態向量為[x0,y0]=[600,100],傳感器節點測量模型如 2.2節所述,測量噪聲vk服從N(0,1)分布。

利用Matlab仿真工具對本文算法、分布式粒子濾波(Distributed Particle Filtering,DPF)跟蹤算法以及并行粒子濾波(Parallel Particle Filtering,PPF)跟蹤算法[16]進行仿真實驗和對比。研究了目標跟蹤過程中3種跟蹤算法在不同步長和傳感器節點個數下的跟蹤精度和網絡能耗,其中跟蹤精度用平均均方根誤差(Root Mean Square,RMS)[16]來描述。對于不同情況,本文分別進行50次仿真,然后對仿真結果進行統計,取平均值作為最后的結果。節點分布和目標軌跡如圖5所示。

圖5 節點分布和目標軌跡

在不同步長下,本文提出的算法與DPF和PPF算法在x,y軸上的誤差對比如圖6所示。其中,圖6(a)表示x方向的誤差對比;圖6(b)為y方向的誤差對比。可以看出,3種算法在x,y方向上的的估計誤差整體上隨著步長的增長而減小,但本文算法的估計誤差明顯小于其他2種算法。

圖6 位置估計誤差對比

圖7為3種算法的均方根誤差對比。可以看出,DPF算法的RMS誤差值最大,本文算法的RMS誤差值最小。在目標作直線運動時,本文提出的算法與PPF算法的RMS誤差相差不大,但在目標轉彎處,本文算法的RMS明顯小于PPF算法,因而跟蹤精度更高。

圖7 均方根誤差對比

圖8所示是不同傳感器節點個數下,不同算法的目標跟蹤延遲時間對比。這幾種算法的跟蹤延遲時間均隨著節點個數的增加而增長,但由圖可見, DPF算法的反應時間呈指數增長,本文算法和PPF算法的反應時間呈線性增長。在同樣的節點個數下,本文算法的平均反應時間是PPF算法的60%,是DPF算法的45%,因而節省了網絡能量,提高了能量使用率。

圖8 跟蹤延遲對比

圖9表示主簇頭節點在不同傳感器節點個數情況下的能量消耗對比?？梢钥闯?本文算法、DPF算法和PPF算法的主簇頭節點能量消耗均隨著節點個數增加而增多,但本文算法的簇頭能量消耗最少,這是由本文簇結構算法所引起的,相比于DPF的簇結構,本文算法減少了簇頭與無貢獻節點的通信量。PPF的簇頭能耗與本文算法相差不大,是由其并行性所引起的。

圖9 主簇頭能量消耗對比

6 結束語

由于無線傳感器網絡中的傳感器節點能量有限并且部署隨機,因此如何獲得高跟蹤精度并且在高精度的基礎上降低網絡能耗,提高能量的利用率是WSN中目標跟蹤的核心問題。本文針對該問題提出了一種基于能量高效動態分簇的目標跟蹤算法,從動態簇生成方法和簇頭更換策略2個方面對動態分簇算法進行了描述,并結合無跡粒子濾波算法對目標進行跟蹤,從而提高了跟蹤精度,降低了整個網絡能耗。

[1] 王 殊,閻毓杰,胡富平,等.無線傳感器網絡的理論及應用[M].北京:北京航空航天大學出版社,2007.

[2] Sheng X,Hu Y H.Distributed ParticleFiltersfor Wireless Sensor Network Target Tracking[C]//Proc.of 2005 IEEE InternationalConferenceon Acoustics, Speech,and Signal Processing.Philadelphia,USA:IEEE Press,2005:845-848.

[3] Chen Weipeng,Hou J C,Sha L.Dynamic Clustering for Acoustic Target Tracking in Wireless Sensor Networks [J].IEEE Transactions on Mobile Computing,2004, 3(3):258-271.

[4] Djuric P M,Vemula M,Bugallo M F.Target Tracking by Particle Filtering in Binary Sensor Networks[J]. IEEE Transactions on Signal Processing,2008,56(6): 2229-2237.

[5] 鄧克波,劉 中.基于無線傳感器網絡動態簇的目標跟蹤[J].兵工學報,2008,29(10):1197-1202.

[6] Baggio A,Langendoen K.Monte-Carlo Localization for MobileWirelessSensorNetworks[J].Ad Hoc Networks,2008,6(5):718-733.

[7] Míguez J,Artés-Rodríguez A.Particle Filtering Algorithms for Tracking a Maneuvering Target Using a Network of Wireless Dynamic Sensors[J].EURASIP Journal on Applied Signal Processing,2006,2006:1-16.

[8] 張軍輝.粒子濾波跟蹤算法研究[D].開封:河南大學,2009.

[9] Teng Jing,Snoussi H,Zhou Rong,et al.Distributed Variational Filtering for Simultaneous Sensor Localization and Target Tracking in Wireless Sensor Networks[J].IEEE Transactions on Vehicular Technology,2012,61(5):2305-2318.

[10] 李 迅,李洪峻.基于簇結構的無線傳感器網絡移動目標精確跟蹤[J].傳感技術學報,2009,22(12): 1813-1817.

[11] 劉立陽,張金成,吳中林.基于分布式動態簇結構的WSN自適應目標跟蹤算法[J].傳感技術學報,2012, 25(1):111-113.

[12] 林金朝,李國軍,周曉娜,等.基于動態能量管理的無線傳感網絡動目標定位跟蹤方法[J].通信學報, 2010,31(12):91-93.

[13] Payne O,Marrs A.An Unscented Particle Filter for GMTI Tracking[C]//Proc.of 2004 IEEE Aerospace Conference.[S.l.]:IEEE Press,2004:1869-1875.

[14] Rui Yong,Chen Yunqiang.BetterProposalDistributions:Object Tracking Using Unscented Particle Filter [C]//Proc.of 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.[S.l.]: IEEE Press,2001:786-793.

[15] Angrisani L,Baccigalupi A,Meriel-lo R S L.On the Use of Unscented Kalman Filter for Improving UItrasonic Timeof-flight Measurement[C]//Proc.of Instrumentation and Measurement Technology Conference.Ottawa,Canada: [s.n.]:17-19.

[16] 屈劍鋒,柴 毅,郭茂耘.無線傳感器網絡下的并行粒子濾波目標跟蹤算法[J].電子科技大學學報,2011, 40(2):232-233.

編輯 金胡考

Target Tracking Algorithm Based on Energy-efficient Dynamic Clustering

LU Xian,PENG Yong
(School of Internet of Things Engineering,Jiangnan University,Wuxi 214122,China)

Target tracking is a basic application in Wireless Sensor Network(WSN).It is a core problem to make a high tracking precision with low energy consumption and prolong the network’s life cycle.Aiming at this problem,a target tracking algorithm based on energy-efficient dynamic clustering is proposed.It firstly presents a new method of generating the dynamic cluster from the view of greatly saving energy.Then,the generated cluster structure uses the Unscented Particle Filtering(UPF)algorithm to track the target and predict the location coordinates in next moment. Finally,according to the predicted results,this paper puts forward a cluster head replaced policy.Simulation results show that,compared with PPF algorithm and DPF algorithm,this algorithm not only has higher target tracking precision,but also effectively reduces the network energy consumption and extends the network lifetime.

Wireless Sensor Network(WSN);target tracking;Unscented Particle Filtering(UPF)algorithm;dynamic clustering;

Signal Strength Indications(RSSI)model;Unscented Kalman Filtering(UKF)algorithm

1000-3428(2014)10-0098-06

A

TP393

10.3969/j.issn.1000-3428.2014.10.019

江蘇省交通運輸廳基金資助項目(2012X08-2)。

陸 嫻(1988-),女,碩士研究生,主研方向:WSN目標定位與跟蹤;彭 勇,副教授。

2013-10-08

2013-11-28E-mail:youmeiluxian@163.com

中文引用格式:陸 嫻,彭 勇.基于能量高效動態分簇的目標跟蹤算法[J].計算機工程,2014,40(10):98-103,108.

英文引用格式:Lu Xian,Peng Yong.Target Tracking Algorithm Based on Energy-efficient Dynamic Clustering[J]. Computer Engineering,2014,40(10):98-103,108.