王瑞錦，郭 祥，王佳昊，秦志光

?

無線傳感器網絡動態(tài)軌跡多目標跟蹤算法

王瑞錦，郭 祥，王佳昊，秦志光

(電子科技大學信息與軟件工程學院 成都 610054)

，該文提出了一種新的基于邊權值動態(tài)軌跡的多目標區(qū)域跟蹤算法EWDT。該算法首先，對該區(qū)域中目標的個數、身份及狀態(tài)等關鍵信息進行分析和確認；其次，并，以。，EWDT算法Forms和LLS方法相比，。

; 邊權值; 目標跟蹤; 無線傳感網絡

目標跟蹤是無線傳感器網絡(wireless sensor networks, WSN)的典型應用之一， 多目標跟蹤的目的是確定目標的位置、身份以及運動狀態(tài)等融合信息，涉及到WSN中的路由、定位、加密以及數據融合等關鍵技術[1-4]。在實際應用環(huán)境中，目標節(jié)點會受到多個因素的影響，機動性和隱蔽性都在不斷地增強，因而新形勢下的多目標跟蹤問題會變得越來越復雜。如何在復雜環(huán)境中實現快速定位和跟蹤多目標的動態(tài)軌跡成了研究的重點[5-8]。

WSN多目標跟蹤的方法有很多，目前的討論熱點是如何在系統(tǒng)跟蹤精度與網絡能量開銷之間做一個權衡關系，要求在盡量提高系統(tǒng)跟蹤精度的同時，也能有效節(jié)省節(jié)點的能量開銷，從而延長網絡的生命周期[9-10]。比如在跟蹤算法中加入節(jié)點的喚醒機制，處在監(jiān)控區(qū)域中的傳感節(jié)點均處于一種周期性的睡眠狀態(tài)，只有當節(jié)點檢測到有事件發(fā)生時，才會通過事件觸發(fā)的方式喚醒自己進行事件的跟蹤與監(jiān)控，有效地減少了節(jié)點的能量開銷。同時，基于區(qū)域查詢的跟蹤應用也越來越受到關注與重視。用戶指定任意一片監(jiān)控區(qū)域，可以對該區(qū)域中目標的個數、身份及狀態(tài)等信息進行查詢訪問。但現有的區(qū)域查詢算法能耗開銷大，查詢時延長，且能同時對目標進行區(qū)域查詢以及軌跡跟蹤的研究較少。

針對以上問題，本文提出了一種新的基于邊權值動態(tài)軌跡的多目標區(qū)域跟蹤算法EWDT。主要處理流程如下：

1) 構建系統(tǒng)模型，采用節(jié)點喚醒機制來有效降低系統(tǒng)的能耗開銷，延長網絡周期；

2) 采用網絡分割算法進行網絡平面劃分，并賦予網絡中每條劃分邊初始權值。實時更新邊權值，當權重為的監(jiān)測目標進入某個區(qū)域順時針跨過一條邊時，該邊的權值會自增。反之離開某塊區(qū)域，逆時針跨過一條邊時，該邊的權值則自減；

3) 設計節(jié)點邊權值狀態(tài)轉換策略和查詢統(tǒng)計機制，完成節(jié)點間狀態(tài)轉換和區(qū)域有效查詢；

4) 采用卡爾曼濾波技術設計軌跡跟蹤算法，實現動態(tài)跟蹤目標，確定目標當前的位置或者預測下一個時刻目標的位置。

1 相關研究

目標跟蹤在國內外已有較多的研究。文獻[9]提出了一種可以用于處理多種跟蹤問題的近似最優(yōu)方法—卡爾曼(KALMAN)濾波，該算法通過對含有噪聲數據的測量值進行遞歸性的融合，從而得出系統(tǒng)狀態(tài)的較為準確的估計。該算法具有較強的跟蹤精度，但只用于單目標跟蹤中，且系統(tǒng)所需的計算開銷較大。

文獻[10]提出了一種基于樹形的目標跟蹤算法 (scalable tracking using networked sensors, STUN)，用以對網絡中的移動目標進行跟蹤和監(jiān)控。該算法的實現非常簡單，路由結構也較為穩(wěn)定，節(jié)點的計算存儲開銷都較小。但需要網絡中的所有節(jié)點都一直處于工作狀態(tài)，能耗較大，跟蹤精度也不高。

文獻[11]對STUN算法進行了改進，提出了一種新的目標跟蹤算法(dynamic convoy tree based collaboration, DCTC)[11]。該算法的基本思想是在監(jiān)控目標的周圍建立一棵用于目標跟蹤的傳送樹，樹內節(jié)點的動作由樹根節(jié)點進行決策。DCTC算法通過建立傳送樹的機制，有效地節(jié)省了網絡中的能量消耗。但是基于樹狀的網絡結構，系統(tǒng)的可擴展性受到了限制。

文獻[12]提出了一種基于簇狀網絡結構的算法(dynamic cluster detection and tracking, DCDT)。該算法以檢測目標信息的所有網絡節(jié)點組成邊界節(jié)點構建動態(tài)跟蹤簇，而處于邊界處的節(jié)點可能會被劃分到多個簇里面。DCDT算法具有較高的跟蹤精度，系統(tǒng)的實時性也比較強，通常情況下可以有效地降低系統(tǒng)的計算以及通信開銷。但當網絡中目標的運動軌跡頻繁出現交叉相遇時，系統(tǒng)便會頻繁地進行動態(tài)跟蹤簇的合成與分解，這勢必會給系統(tǒng)造成嚴重的資源開銷，影響系統(tǒng)的性能。

文獻[13]提出了一種區(qū)域跟蹤算法(continuous objects tracking algorithm, COTA)。COTA算法是以一片連續(xù)的區(qū)域作為監(jiān)測目標，該目標具有覆蓋范圍廣、隨機性強、受環(huán)境因素影響大等特點，相比大多數傳統(tǒng)的目標跟蹤算法，該算法是一種較新型的算法，具有較強的實時性和穩(wěn)定性，所需的能量開銷較小。不過該算法是以火情監(jiān)控、化學氣體泄露、放射性物質輻射等為應用場景，這就需要對節(jié)點進行更好的物理保護，并且所涉及到的節(jié)點數量眾多，這可能會造成系統(tǒng)成本的增加。

文獻[14]提出的LLS算法將網絡劃分為網格結構，網絡中若干節(jié)點作為中心節(jié)點，中心節(jié)點周圍的鄰居節(jié)點作為其附屬節(jié)點。當目標進入某塊監(jiān)控區(qū)域時，附屬節(jié)點負責采集目標信息，而中心節(jié)點只負責信息的處理?？傮w上跟蹤精度較高，但該算法要求中心節(jié)點具有較強的處理能力，實際應用性不強，且算法的計算開銷也較大。

文獻[15]提出Forms算法，通過對任意指定的一塊區(qū)域進行邊權值計算，可以對該區(qū)域中目標的個數、身份以及狀態(tài)等關鍵信息進行分析和確認，能夠進行區(qū)域查詢。但該算法邊權值更新過程能耗過大，無法對目標進行軌跡跟蹤。

綜上分析，現有的多目標跟蹤算法雖然都取得了一定的效果，同時也存在著通信和計算開銷大、平均更新和查詢時間長等缺點。

2 系統(tǒng)構建模型

2.1 傳感模型

1) 節(jié)點模型：在傳感器節(jié)點中，其功能模塊與通訊模塊之間相互獨立，功能模塊主要負責環(huán)境信息的采集，而通信模塊主要用于數據的轉發(fā)與傳送，并且節(jié)點采集一次數據所消耗的能量遠遠大于節(jié)點進行一次信道偵聽所消耗的能量。

2) 節(jié)點喚醒機制：處在監(jiān)控區(qū)域中的傳感節(jié)點都處于一種周期性的睡眠狀態(tài)，在這種周期性的睡眠狀態(tài)下，節(jié)點的通訊模塊以時間作為周期進行信道偵聽，當接收到其鄰居節(jié)點發(fā)送的特定信息時，將會喚醒自己的功能模塊，并以時間為周期進行數據采集，當檢測到有事件發(fā)生時再進入喚醒狀態(tài)，并開始對目標事件進行監(jiān)控跟蹤。其中，這樣既可以保證網絡中的節(jié)點在沒有事件發(fā)生時能量消耗降到最低，也可以保證當節(jié)點采集到數據需要向周圍節(jié)點發(fā)送信息時，節(jié)點的通訊模塊也正好是開啟的。

2.2 網絡模型

在該方案中，網絡模型有如下假設：網絡中的所有節(jié)點間彼此同構對等，且隨機分布，節(jié)點部署后的坐標位置均已知。單個節(jié)點對環(huán)境的監(jiān)測范圍等于其通信半徑。系統(tǒng)中監(jiān)測目標根據各自的不同特征賦予不同的權重值，第個目標的權值為。對于算法中將要使用到的常量定義如下：

3 EWDT算法的設計

以下從系統(tǒng)初始化、邊權值更新、節(jié)點間的狀態(tài)轉換、區(qū)域查詢以及軌跡跟蹤這5個步驟詳細描述算法設計。

3.1 系統(tǒng)初始化

節(jié)點采用隨機部署的方式，并根據網絡分割算法[16-17]將網絡進行平面劃分，得到一個網絡節(jié)點的連通子圖如圖1所示。圖中，每個頂點表示一個節(jié)點，邊表示節(jié)點間可以單跳通信，所有邊初始權重值為0。

在最初部署系統(tǒng)時，所有的網絡節(jié)點都處于周期性的睡眠狀態(tài)。假設在某時刻發(fā)生了突發(fā)事件，這時事件周圍的某些節(jié)點必然會檢測到該目標信息，并且會修改自身所對應邊的權重值。這些節(jié)點將進入喚醒狀態(tài)，向其周圍鄰居節(jié)點傳播喚醒消息，記為W_Message，消息的具體格式如表1所示。

表1 W_Message格式

接收到喚醒消息的節(jié)點以及最初檢測到目標信息的節(jié)點此后都會周期性地檢測其通信范圍內多邊形邊的權重值，若權重值為0，則節(jié)點繼續(xù)保持等待狀態(tài)，并同時啟動一個定時器，這時可以分為兩種情況：

1) 若在定時器設定的時間內邊權重值始終為0，則節(jié)點進入睡眠狀態(tài)；

2) 若在定時器設定的時間內邊權重值不為0，則說明有目標在該節(jié)點的檢測范圍之內，此時節(jié)點開啟功能模塊對目標進行周期性的信息采集。

3.2 邊權值的更新

邊權值更新流程如圖2所示。每一塊區(qū)域都能表示成若干條有向邊的順時針連接，如圖中的區(qū)域、以及。方向相反的兩條邊的權值互為相反數，如邊的權值為，則邊的權值為。區(qū)域的權值統(tǒng)計結果為順時針方向組成該區(qū)域的各邊權值之和，。假設當權值為的監(jiān)控目標跨過一條邊進入某塊區(qū)域時，該邊的權值會相應的增加，相反當目標跨過一條邊離開某塊區(qū)域時該邊的權值會減少。

3.3 節(jié)點間的狀態(tài)轉換

1) 休眠節(jié)點的狀態(tài)轉換

處于休眠狀態(tài)的節(jié)點接收到W_Message消息后，將進入等待狀態(tài)，所有處于等待狀態(tài)的節(jié)點都將以為周期，對自己的檢測區(qū)域進行邊權重值的統(tǒng)計，根據檢測的結果不同，分為以下兩種情況：

① 區(qū)域統(tǒng)計的權值和不為0，則節(jié)點進入檢測狀態(tài)，對目標進行信息采集，并且向其周圍節(jié)點發(fā)送喚醒消息。

② 區(qū)域統(tǒng)計的權值和在一段時間內始終都為0，則進入睡眠狀態(tài)。

2) 喚醒狀態(tài)節(jié)點的狀態(tài)轉換

圖3 節(jié)點狀態(tài)轉移圖

3.4 區(qū)域查詢

由于系統(tǒng)初始化過程中，所有邊的權重值都初始化為0，并且當目標進入一塊區(qū)域后再離開該區(qū)域時不會造成區(qū)域權值的變化。所以可以通過對指定的一塊區(qū)域進行邊權值的統(tǒng)計判斷其結果是否為0，若為0則說明該區(qū)域中不存在監(jiān)控目標，否則說明該區(qū)域存在有監(jiān)控目標。在特定情況下還能對該區(qū)域中的目標個數以及身份信息進行確認。

區(qū)域查詢如圖4所示，每個監(jiān)控目標事先都根據其不同的重要特性按照2的冪次賦初始權值，對區(qū)域進行查詢：各邊權重值相加為，由此可以判斷該區(qū)域中含有權重值為2和4的兩個監(jiān)控目標。對區(qū)域進行查詢：，由此可見該區(qū)域中只含有權重值為1的監(jiān)控目標。對區(qū)域進行查詢：由于，則，因此各邊權重值相加為，說明該區(qū)域中不含監(jiān)控目標。

3.5 軌跡跟蹤

在邊權值的基礎上結合動態(tài)跟蹤簇以及卡爾曼濾波技術，除了可以對區(qū)域進行目標查詢外，還能對目標進行傳統(tǒng)的軌跡跟蹤。軌跡跟蹤如圖5所示。普通節(jié)點將目標的監(jiān)控信息發(fā)送給簇頭節(jié)點，簇頭節(jié)點對收集的信息進行濾波處理，以確定目標當前的位置或者預測下一時刻目標出現的位置。

假設用監(jiān)控目標的位置、速度以及加速度來表示其在每個時刻的狀態(tài)。而在目標跟蹤的整個過程中，節(jié)點的采樣周期很小，所以在一個周期內目標的運動近似為勻速運動。在此定義卡爾曼濾波器的系統(tǒng)狀態(tài)為：

EWDT軌跡跟蹤算法流程為：

輸出：預測的軌跡

步驟1:

//以及預測值與測量值之間的相關度

FOR=1:1:

END FOR

步驟2:

//選擇相關概率最大的軌跡進行關聯

步驟3:

步驟4:

步驟5:

步驟6:

FINISH() //結束計算

4 實驗及性能評估

從邊權值更新和目標查詢兩個過程中的平均能耗與時延方面，對本文提出的EWDT算法、Forms算法以及LLS算法進行性能分析與比較。

4.1 實驗參數設置

具體實驗參數如表3所示：

表3 實驗參數

4.2 平均查詢時間與能耗

圖6和圖7分別表示系統(tǒng)的平均查詢時間和查詢時的平均能量消耗，當網絡節(jié)點規(guī)模從1 000逐漸增加到10 000時，網絡規(guī)模越大則查詢區(qū)域離監(jiān)控中心的平均距離也越大，所以系統(tǒng)的平均查詢時間和查詢時的平均能量消耗也會顯著的增加。

由于在EWDT算法中采用了動態(tài)跟蹤簇對目標進行跟蹤，對于普通區(qū)域的查詢無需進行邊權值的統(tǒng)計，而只需對包含在跟蹤簇里的查詢區(qū)域進行權值統(tǒng)計，相比較Forms和LLS而言，EWDT算法能在較大程度上減少系統(tǒng)查詢時的處理開銷以及處理時延。通過計算比較分析后可知，在系統(tǒng)平均查詢時間上，EWDT算法相對于Forms算法以及LLS算法分別減少了21.8%和36.4%的查詢時間；而在系統(tǒng)平均查詢能耗上則分別減少了18.6%和30.5%。

4.3 平均更新時間與能耗

圖8和圖9分別表示系統(tǒng)平均更新時間以及更新過程中的平均能量開銷。

雖然網絡規(guī)模逐漸增大，但并不影響系統(tǒng)在局部區(qū)域進行邊權值更新時的平均能量開銷以及平均處理時延，因此幾乎不受網絡規(guī)模大小的影響。但在EWDT算法中加入了節(jié)點狀態(tài)轉換機制，并通過統(tǒng)計節(jié)點所在區(qū)域的邊權值是否為0這種最簡單的方式來進行節(jié)點的狀態(tài)轉換，從而大大的減少了節(jié)點采樣信息的頻率。因此相比Forms算法和LLS算法，在相同的網絡規(guī)模時EWDT算法可以在較大程度上減少系統(tǒng)的平均更新成本以及更新時延。通過比較分析可知，在系統(tǒng)更新上，EWDT算法相對于Forms算法以及LLS算法分別減少了12.3%和30.2%的更新時間；而在系統(tǒng)平均更新能耗上則分別減少了50.4%和78.6%。

5 結 束 語

通過實驗對比結果分析可知，EWDT算法在區(qū)域查詢和邊權值更新過程中，系統(tǒng)平均能耗和平均時延都能大大的減小，從而延長了網絡周期，增強了系統(tǒng)的實用性。

[1] QU H, HOU G, GUO Y, et al. Localization with single stationary anchor for mobile node in wireless sensor networks[J]. International Journal of Distributed Sensor Networks, 2013(1): 74-82.

[2] 王瑞錦, 秦志光, 包紅來, 等. 基于三角劃分的復雜3D凹/凸不平表面網絡定位算法[J]. 計算機應用研究, 2013, 30(9): 2823-2830.

WANG Rui-jin, QIN Zhi-guang, BAO Hong-lai, et al. Triangulation-based localization algorithm over complex 3D terrains[J]. Application Research of Computer, 2013, 30(9): 2823-2830.

[3] 王瑞錦, 秦志光, 王佳昊. 無線傳感器網絡分簇路由協(xié)議分析[J]. 電子科技大學學報, 2013, 42(3): 400-406.

WANG Rui-jin, QIN Zhi-guang, WANG Jia-hao. Analysis of wireless sensor network cluter routing protocol[J]. Journal of University of Electronic Science and Technology of China, 2013, 42(3): 400-406.

[4] ZHOU H, WU H, JIN M. A robust boundary detection algorithm based on connectivity only for 3D wireless sensor networks[C]//2012 Proceedings IEEE on International Conference on Computer Communications. Orlando, USA: IEEE, 2012.

[5] WANG R J, BAO H L, CHEN D J, et al. 3D-CCD: a novel 3D localization algorithm based on concave/convex decomposition and layering scheme in WSNs[J]. Ad hoc & Sensor Wireless Networks, 2014(23): 235-254.

[6] WANG J, HUANG L, LI X, et al. A collaborative localization scheme from connectivity in wireless sensor networks[C]//Wired/Wireless Internet Communications. Finland: Springer, 2008: 213-223.

[7] WANG R J, QIN Z G. A weighted 3D localization algorithm based on partial hop size in wireless sensor network[J]. International Journal of Advancementsin Computing Technology, 2012, 4(9): 504-513.

[8] WANG R J, QIN Z G, LI D F, et al. 3DT-PP: Localization and path planning of mobile anchors over complex 3D terrains[J]. High Technology Letters, 2014(4): 367-375.

[9] SHENG X, HU Y H, RAMANATHAN P. Distributed particle filter with GMM approximation for multiple targets localization and tracking in wireless sensor network[C]// Proceedings of the 4th International Symposium on Information Processing in Sensor Networks. [S.l.]: IEEE, 2005.

[10] 王瑞錦. 復雜環(huán)境下的無線傳感器網絡定位關鍵技術研究[D]. 成都: 電子科技大學, 2013.

WANG Rui-jin. Key techniques of localization in wireless sensor networks under complex environment[D]. Chengdu: University of Electronic Science and Technology of China, 2013.

[11] ZHANG W, CAO G. DCTC: Dynamic convoy tree-based collaboration for target tracking in sensor networks[J]. IEEE Transactions on Wireless Communications, 2004, 3(5): 1689-1701.

[12] JI X, ZHA H, METZNER J J, et al. Dynamic cluster structure for object detection and tracking in wireless ad-hoc sensor networks[C]//IEEE International Conference on Communications. [S.l.]: IEEE, 2004, 7: 3807-3811.

[13] 鮑微. 無線傳感器網絡中能量高效的目標跟蹤問題研究[D]. 合肥: 中國科學技術大學, 2009.

BAO Wei. Research on energy-efficient target tracking in WSNs[D]. Hefei: University of Science and Technology of China, 2009.

[14] ABRAHAM I, DOLEV D, MALKHI D. LLS: a locality aware location service for mobile Ad hoc networks[C]// Proceedings of the 2004 Joint Workshop on Foundations of Mobile Computing. [S.l.]: ACM, 2004.

[15] SARKAR R, GAO J. Differential forms for target tracking and aggregate queries in distributed networks[J]. IEEE/ ACM Transactions on Networking, 2013, 21(4): 1159- 1172.

[16] SARKAR R, YIN X, GAO J, et al. Greedy routing with guaranteed delivery using ricci flows[C]//International Conference on Information Processing in Sensor Networks, IPSN 2009. [S.l.]: IEEE, 2009: 121-132.

編 輯 葉 芳

Multi-Object Dynamic Trajectory Tracking in Wireless Sensor Network

WANG Rui-jin, GUO Xiang, WANG Jia-hao, and QIN Zhi-guang

(School of Information and Software Engineering, University of Electronic Science and Technology of China Chengdu 610054)

For solving multi-objective trajectory tracking problem by lower energy consumption costs and extending the network lifetime in wireless sensor networks, a new multi-target area tracking algorithm (EWDT) is presented based on edge weights dynamic trajectory.analyzes and confirms the number, identity and status of the target by calculating the value of edge weights in the any given area. To further reduce the energy consumption and latency, EWDT designs the node state transition mechanism and utilizes dynamic tracking clustering and Kaman filtering techniques to track the target trajectory. Experimental results show that EWDT can reduces the system power consumption and latency significantly comparing with the current Forms and locality aware location service (LLS) algorithm.

dynamic trajectory; edge weights; target tracking ; wireless sensor networks

TP309.3

A

10.3969/j.issn.1001-0548.2016.03.013

2014 - 04 - 30；

2014 - 12 - 08

國家自然科學基金(60903157)；四川省科技廳計劃項目(2015JY0178)；中央高?；究蒲袠I(yè)務費專項資金(ZYGX2014J051，ZYGX2011J066)

王瑞錦(1980 - )，男，博士，主要從事無線傳感網、信息安全、量子安全等方面的研究.