基于移動Sink的自組織視頻傳感網絡目標跟蹤算法*

盧旭，劉軍，袁飛

（廣東技術師范學院自動化學院，廣州510665）

基于移動Sink的自組織視頻傳感網絡目標跟蹤算法*

盧旭*，劉軍，袁飛

（廣東技術師范學院自動化學院，廣州510665）

基于自組織視頻傳感網絡的目標跟蹤方法利用節點的分布式觀測能力，實現目標的精確跟蹤。在研究視頻節點觀測投射模型和通信模型的基礎上，提出一種基于移動Sink的自組織視頻傳感網絡目標跟蹤算法MSTTA。該算法包括感知信息聚合和目標位置評估兩個部分，利用節點分類機制周期性地更新網絡拓撲以適應Sink位置的變化，根據目標運動狀態預測目標位置的評估節點小組。仿真實驗表明，MSTTA算法能夠適應Sink移動帶來的網絡拓撲變化，具有較高的目標跟蹤精度。

視頻傳感網絡；目標跟蹤；數據聚合；移動Sink

EEACC：6150doi：10.3969/j.issn.1004-1699.2016.09.023

傳統無線傳感器網絡由大量具有通信能力的傳感器節點構成［1］，自組織視頻傳感網絡ACSN（Ad-Hoc Camera Sensor Networks）是其中特殊的一種，其由大量具有一定通信能力的可以觀測感知環境的視頻節點組成，可以實現細粒度、精準信息的圖像信息采集和目標跟蹤［2-3］，在環境、交通、軍事、建筑及其他商業領域中具有廣闊的應用前景。

在面向目標跟蹤應用的自組織視頻傳感網絡中，為提高跟蹤的精度、速度和廣度，視頻傳感節點通常利用相互通信來實現分布式跟蹤，節點間通過各種不同視角的目標信息的交換和融合，再經過綜合運算獲得目標的移動軌跡信息［4］。在視頻傳感網絡目標跟蹤算法中，當前已有的研究成果大都是基于固定Sink完成的。Alaei等［5］基于固定Sink提出一種高能效的視頻傳感網絡協同節點管理算法，該算法中基于節點的視野重疊感知區域設計了一種新型節點分簇方法。Alberto等［6］提出一種基于分簇的視頻傳感網絡目標跟蹤算法，包含觀測數據整合、簇成員選取和簇頭輪換等三個步驟。Tezcan等［7］提出一種通過調整視頻傳感節點的觀測方向來最優化覆蓋質量的檢測算法，該算法通過調整視頻節點的觀測方向來減小障礙物對目標檢測的影響。Ercan等［8］研究了在傳感器網絡框架下的多視頻節點最優化部署及面向單目標跟蹤的節點最優集選取問題。蔣一波等［9］分析可旋轉的視頻傳感器節點有向感知模型，定義了最小旋轉角度的移動目標K級覆蓋問題并給出了對應的數學描述，提出一種基于移動目標軌跡預測的分布式貪心K級覆蓋算法。

以上視頻傳感網絡節點調度及目標跟蹤算法均在固定Sink的網絡模型下實現，算法性能和應用有一定局限性。Shaw等［10］在移動Sink環境下研究了視頻傳感網絡的多目標跟蹤問題，基于節點分簇機制提出了針對目標跟蹤的節點調度模型，并對單個和多個移動目標時的目標跟蹤精度進行了分析比較，結果顯示所提出算法對目標的跟蹤精度較低。本文擬提出一種基于移動Sink的自組織視頻傳感網絡目標跟蹤MSTTA（Mobile Sink based Target Tracking for ACSN）算法，采用節點分類機制和預測評估節點小組的方法，提高目標跟蹤精度和效率。本文的算法支持移動sink，算法復雜度較低，是一種能夠快速適應拓撲變化的魯棒、高效的算法，在大規模節點和移動sink的網絡應用中具有高能效和低開銷的特點。

1　網絡模型

1.1節點觀測投射模型

本文采用的視頻傳感節點觀測投射模型參考文獻［11］中的模型，如圖1所示。

圖1　視頻節點投射模型

假設所有節點和目標均分布在一個平面上，圖中Li（t）與視頻節點對目標的觀測坐標的關系為：

其中F為視頻傳感節點的焦距，θi為節點鏡頭相對于坐標X軸的角度，（xi，yi）為視頻傳感節點的坐標，兩個視頻傳感節點同時觀測到目標即可確定目標坐標（xt，yt）。

1.2通信模型

我們的目標定位和跟蹤算法要求適應Sink移動的環境，還要求對目標檢測有快速響應，實時反饋目標位置以達到跟蹤目的。因此，我們提出的通信模型應該是一個綜合性的、多層次的結構。本文采用的通信模型如圖2所示。

視頻傳感節點的通信棧的物理層和MAC層采用IEEE 802.15.4標準［12］，無線通信損耗的計算采用自由空間損耗模型。我們提出的MSTTA算法設置在通信棧的應用層中，由于信道擁塞是影響低帶寬環境下網絡通信性能的主要因素，因此MSTTA算法在本文通信模型中還兼備了一些網絡層的路由功能，以適應Sink移動帶來的拓撲變化。因此應用層又包含兩個子層：數據聚合子層和目標定位子層，分別用于感知信息的聚合和目標位置的評估。

圖2　通信模型

2　MSTTA算法描述

2.1感知信息聚合

在信息感知階段，采用多跳方式傳輸數據，我們將一個節點的鄰居節點分為3類：上級節點、同級節點和下級節點。上級節點指相對于該節點離Sink的距離更近即到Sink的跳數更少的節點，同級節點指到Sink的跳數相等的節點，下級節點指到Sink的跳數更多的節點。

每個節點都維護一張節點類型列表，列表中的數據根據監聽各節點發送的廣播信息中的跳數來更新。Sink節點通過發送路由請求信息來更新節點的路由信息，節點中存儲的數據的結構為：＜Sink請求序號，跳數，下一跳，上級節點［］，同級節點［］，下級節點［］＞，Sink的路由請求包的結構為：＜Sink請求序號，跳數，生存時間，源節點＞，其中生存時間表示該信息的有效傳播時間。

MSTTA算法執行數據聚合的具體步驟如下：

①Sink生成第一條信息向全網廣播，各節點接收到廣播信息后分別生成指向sink節點的路徑的向量組。由于Sink節點是移動的，其必須周期性地發送路由請求信息來更新各節點的路由信息，其發送頻率和Sink的移動速度成正比。移動速度越快，路由信息變化也越快，因此需要更快的發送頻率。之后每次收到Sink的路由請求信息后，所有節點都生成并存儲自己的跳數值、收到的最后的Sink請求信息的序號以及鄰居節點的級別信息。Sink的路由請求信息中請求序號是逐次增加的，生存時間預先設定。

②處理完Sink發來的路由請求信息后，所有節點將有條件地重新廣播這些消息，以更新跳數和序號。具體運行方式是：如果請求信息序號大于或等于當前節點中的序號，則比較請求信息和節點信息中的跳數，如果前者較小，節點根據Sink的請求信息更新自身的跳數和下一跳，然后為避免產生沖突在一個隨機延時后重新發送路由請求信息；如果請求信息中的源節點是當前節點的上級節點，則將當前節點的下一跳和跳數更新為請求信息的下一跳和跳數，然后在一個隨機延時后重發路由請求信息；如果當前節點中的下一跳和請求信息中的下一跳不相同，但其跳數和請求信息中的跳數相等，則將節點的下一跳更新為請求信息中的下一跳，并將請求信息中的生存時間置1，限制該信息的傳播時間，然后再等待一個隨機延時后重發該信息。除滿足上述條件外，其他情況均丟棄路由請求信息，即當前節點不改變自身數據。

③當到達某節點的連接連續失敗5次以上，則移除該節點的路由記錄，然后從下級和同級節點列表中選擇所有可能的下一跳節點，再從中挑選出一個到Sink的跳數最少的節點，然后該節點生成一個廣播消息，把新的跳數和下一跳廣播給鄰居節點。如果沒有有效的下一跳節點存在，為了避免資源浪費，該節點將停止發送數據直到Sink再次刷新路由信息。

2.2目標位置評估

本文假設視頻傳感節點在正方形平面感知區域內隨機稠密分布，網絡覆蓋率達100%，唯一的Sink節點和目標均在感知區域內隨機運動，如圖3所示。

圖3　網絡分布圖

MSTTA算法支持單目標定位跟蹤，信息聚合采用前文所述方法，通過各視頻傳感節點上傳的報告，每一個報告都包含一個唯一的序列號，組成目標位置評估數據組，數據組中節點報告的目標位置不斷更新，從而實現目標定位。目標位置評估步驟如圖4所示。

圖4　目標位置評估步驟

首先，所有視頻傳感節點監測目標在感知區域中出現的位置，一旦有節點檢測到目標出現則立刻廣播全網，開始執行初始化程序，創建第1個目標位置評估數據組，通過視頻節點的觀測投射模型來評估目標狀態。

從第2組起，所有位置評估數據組都通過計算分成若干分組，每個分組由兩個可監控到目標的視頻節點組成。選取其中到Sink的跳數和最小的一個分組，利用該分組來計算目標的位置、速度和方向，位置依然由節點觀測投射模型來確定，速度通過當前位置與前一個分組評估位置之間的距離以及兩個小組采樣時間之差來確定，方向由當前位置與前一個小組評估位置的坐標關系確定。

通過位置、速度和方向，評估下一輪目標可能出現的位置，從而預測下一輪的評估節點小組。再根據預測評估節點小組的實際觀測情況，調整實際小組，確定目標位置，由此生成目標的跟蹤軌跡。該算法既能準確跟蹤目標，又能有效減少不必要能耗。

由于MSTTA算法在程序上至多執行基本的遍歷及迭代操作，因此算法的時間復雜度和空間復雜度均較低。

3　仿真結果與分析

我們采用VC++設計一個網絡模擬平臺，在該平臺上進行實驗評估MSTTA算法的目標跟蹤性能。默認實驗參數如表1所示。本文采用的圖像處理方法參考文獻［13］中的方法，是一種基于FPGA的適用于無線視頻傳感網絡的圖像壓縮方法。

表1　默認實驗參數

3.1評估組

依照上述實驗參數通過仿真實驗后，得出的目標跟蹤軌跡和視頻傳感節點評估組選取情況如圖5所示。由圖5可看出，節點評估組整體情況合理，評估組節點選取受Sink位置的影響，靠近Sink的節點成為評估節點的概率更大，由此可有效節約網絡能量。

圖5　節點評估組情況

3.2跟蹤精度

為了評估算法對移動目標的跟蹤精度，我們設計兩種不同類型的目標移動線路，分別是直線和曲線，其目標跟蹤情況分別如圖6（a）、6（b）所示。

圖6　目標跟蹤精度

由圖6可看出，算法整體目標定位效果較好，相比于目標移動路線為曲線，在目標移動路線為直線時其目標跟蹤精度更高，這是由于MSTTA算法對直線運動目標的評估和預測更準確。我們將上述直線和曲線實驗分別重復10次，在每次實驗過程中依據時間取14個固定采樣點，計算每一次實驗過程中采樣點的平均絕對誤差，為作比較，我們對文獻［10］中提出的基于分簇的目標跟蹤算法（以下簡稱CTTA）進行同樣實驗，其結果如圖7所示?？梢钥闯?，MSTTA算法在目標直線移動時的整體目標跟蹤精度上比曲線移動時的目標跟蹤精度高出40%左右，而相對于CTTA算法，MSTTA算法的目標跟蹤精度平均高出50%左右。

圖7　目標跟蹤誤差

3.3Sink速度的影響

我們將Sink的移動速度分別取4個不同值：2 m/s、3 m/s、4 m/s和5 m/s，測試Sink移動速度對MSTTA算法的目標跟蹤精度的影響，誤差取值方式和圖7相同，Sink移動采用隨機運動方式，目標移動采用直線運動方式，結果如圖8所示。

圖8　不同Sink速度下的跟蹤誤差

由圖8可見，不同Sink移動速度下目標跟蹤精度的平均值均相近，由此可知Sink移動速度的變化對目標跟蹤精度的影響很小，這是由于MSTTA算法采用了三級節點的數據聚合方式，且路由更新速度和Sink移動速度成正比，使其路由形成不受Sink位置和速度的影響，具有較好的自適應性，因此MSTTA算法是一種對基于移動Sink的視頻傳感網絡具有良好適用性和魯棒性的目標跟蹤算法。

3.4目標速度的影響

我們將目標的移動速度改變，也分別取4個不同值：2 m/s、3 m/s、4 m/s、5 m/s，其他參數采用初始默認值，測試目標移動速度對跟蹤精度的影響，目標移動采用直線和曲線兩種方式，結果如圖9（a）、9（b）所示。

可見，在目標是直線運動的情況下，目標移動速度對跟蹤精度的影響很小，基本可以忽略不計。但在目標曲線運動的情況下，目標移動速度對精度的影響相對較大，目標速度越大，跟蹤精度越低。這是由于目標曲線移動時，其運動速度越大，MSTTA算法對視頻傳感節點評估分組的預測準確性越低，從而導致跟蹤精度下降。

圖9　不同目標速度下的跟蹤誤差

4　結論和展望

本文對基于移動Sink的自組織視頻傳感網絡目標跟蹤算法進行研究，提出一種有效的網絡通信模型，利用跨層設計思想在算法中實現了網絡路由和目標跟蹤功能。實驗結果表明所提出算法對Sink移動帶來的網絡拓撲變化具有良好適應性，對于不同移動速度和方向的目標也能夠精確跟蹤，尤其在目標沿直線運行時，算法的目標跟蹤精度基本不受Sink和目標的移動速度變化的影響。

本項目組目前在研發帶視頻傳感和通信功能的移動節點，采用輪式機器人作為自主移動裝置，下一步將在實際網絡環境下研究和驗證基于移動Sink的目標跟蹤算法。

［1］陳東海，李長庚.基于簇頭功能分化的無線傳感器網絡成簇算法［J］.傳感技術學報，2015，28（2）：244-248.

［2］Liu X.A Survey on Wireless Camera Sensor Networks［M］//Fron?tier and Future Development of Information Technology in Medi?cine and Education.Springer Netherlands，2014：1085-1094.

［3］Serik M R，Kaddour M.Optimizing Deployment Cost in Camera-Based Wireless Sensor Networks［J］.Ifip Advances in Information &Communication Technology，2015，456：454-464.

［4］Wang Y，Wang D，Fang W.Automatic Node Selection and Target Tracking in Wireless Camera Sensor Networks［J］.Computers& Electrical Engineering，2014，40（2）：484-493.

［5］Alaei M，Barcelo-Ordinas J M.A Collaborative Node Management Scheme for Energy-Efficient Monitoring in Wireless Multimedia Sensor Networks［J］.Wireless Networks，2013，19（19）：639-659.

［6］Alberto D S B，Ramiro M D D J，Ollero A.Efficient Cluster-Based Tracking Mechanisms for Camera-Based Wireless Sensor Net?works［J］.Mobile Computing IEEE Transactions on，2015，14：1820-1832.

［7］Tezcan N，Wang W.Self-Orienting Wireless Multimedia Sensor Networks for Occlusion-Free Viewpoints［J］.Computer Networks，2008，52（13）：2558-2567.

［8］Ercan A O，Yang D B，Gamal A E，et al.Optimal Placement and Selection of Camera Network Nodes for Target Localization［M］// Distributed Computing in Sensor Systems.Springer Berlin Heidel?berg，2006：389-404.

［9］蔣一波，陳瓊，王萬良，等.視頻傳感器網絡中基于移動目標軌跡預測的K級覆蓋增強算法［J］.傳感技術學報，2014，27（7）：956-963.

［10］Shaw W，He Y，Lee I.Mobile Sink to Track Multiple Targets in Wireless Visual Sensor Networks［C］//International Symposium on Ubiquitous Multimedia Computing.2008：51-56.

［11］Liu L，Zhang X，Ma H.Localization-Oriented Coverage in Wire?less Camera Sensor Networks［J］.Wireless Communications IEEE Transactions on，2011，10（2）：484-494.

［12］Ahmed A A，Latiff A，Fisal N.Real-Time Routing Protocol with Load Distribution in Wireless Sensor Network Based on IEEE 802.11 and IEEE 802.15.4［J］.Jurnal Teknologi，2014，47（1）.

［13］Kaddachi M L，Makkaoui L，Soudani A，et al.FPGA-Based Image Compression for Low-Power Wireless Camera Sensor Networks［C］//International Conference on Next Generation Networks& Services.2011：68-71.

盧旭（1986-），男，工學博士，副教授，主要研究方向為無線傳感器網絡、物聯網，bruda@126.com；

劉軍（1986-），男，工學博士，講師，主要研究方向為物聯網、無線傳感器網絡，liujun7700@163.com；

袁飛（1984-），男，工學博士，講師，主要研究方向為無線傳感器網絡，eric_f_y@foxmail.com。

Mobile Sink Based Target Tracking Algorithm for Ad-Hoc Camera Sensor Networks*

LU Xu*，LIU Jun，YUAN Fei
（College of Automatization，Guangdong Polytechnic Normal University，Guangzhou 510665，China）

Target tracking based on Ad-hoc Camera Sensor Networks using the distributing observed function of nodes to track targets accurately.Based on the model analysis of camera sensor perspective projection and communi?cation，a Mobile Sink based Target Tracking algorithm for Ad-hoc Camera Sensor Networks（MSTTA）is proposed.There are two parts in the algorithm：sensor data gathering and target location evaluating，which using nodes classify?ing scheme to update the network topology periodically for the change of Sink’s location，and forecasting target loca?tion evaluating group of nodes according to the target’s status of motion.Experiment results show that the proposed MSTTA algorithm can adapt to the change of network topology caused by mobile Sink，and tracks the target accurately.

camera sensor networks；target tracking；data gathering；mobile Sink

TP393

A

1004-1699（2016）09-1430-05

項目來源：廣東省科技計劃項目（2015A010103014，2015A070710022）；廣東普通高校青年創新人才項目（2014KQNCX178）

2016-03-13修改日期：2016-05-17