無線傳感器網絡動態軌跡多目標跟蹤算法

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

?

無線傳感器網絡動態軌跡多目標跟蹤算法

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

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

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

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

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

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

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

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

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

3) 設計節點邊權值狀態轉換策略和查詢統計機制，完成節點間狀態轉換和區域有效查詢；

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

1 相關研究

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

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

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

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

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

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

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

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

2 系統構建模型

2.1 傳感模型

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

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

2.2 網絡模型

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

3 EWDT算法的設計

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

3.1 系統初始化

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

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

表1 W_Message格式

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

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

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

3.2 邊權值的更新

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

3.3 節點間的狀態轉換

1) 休眠節點的狀態轉換

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

① 區域統計的權值和不為0，則節點進入檢測狀態，對目標進行信息采集，并且向其周圍節點發送喚醒消息。

② 區域統計的權值和在一段時間內始終都為0，則進入睡眠狀態。

2) 喚醒狀態節點的狀態轉換

圖3 節點狀態轉移圖

3.4 區域查詢

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

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

3.5 軌跡跟蹤

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

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

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分別表示系統的平均查詢時間和查詢時的平均能量消耗，當網絡節點規模從1 000逐漸增加到10 000時，網絡規模越大則查詢區域離監控中心的平均距離也越大，所以系統的平均查詢時間和查詢時的平均能量消耗也會顯著的增加。

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

4.3 平均更新時間與能耗

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

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

5 結 束 語

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

[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] 王瑞錦, 秦志光, 王佳昊. 無線傳感器網絡分簇路由協議分析[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] 王瑞錦. 復雜環境下的無線傳感器網絡定位關鍵技術研究[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務費專項資金(ZYGX2014J051，ZYGX2011J066)

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