無線傳感器網絡中基于虛擬點優化的追蹤算法

劉彬彬，韓光潔，孫洪文

（河海大學物聯網工程學院，常州213022）

無線傳感器網絡中基于虛擬點優化的追蹤算法

劉彬彬，韓光潔，孫洪文

（河海大學物聯網工程學院，常州213022）

針對利用無線傳感器網絡進行大范圍連續目標追蹤過程中，追蹤精度較低及邊界失真的問題，提出一種有效的基于虛擬節點優化VNOE(virtual node optimization effectively)的追蹤算法，該方法利用虛擬化的距離真實邊界更近的位置信息去構造所需的目標邊界，從而對連續目標形狀以及位置進行追蹤。算法首先確定了連續目標邊界點BN信息，然后依據相關邊界節點信息確定虛擬點VN位置。實驗表明，提出的算法一定程度上提高了追蹤精度并改善了邊界失真。

連續目標；目標追蹤；虛擬化位置；形狀與位置；追蹤精度;邊界失真

1 引言

無線通信與智能化節點的優勢使得無線傳感器網絡的應用越來越廣泛，例如將大量微型智能化多功能傳感器節點布置于一個大范圍區域當中對移動的目標進行監測與追蹤。在傳統的關于移動目標探測與追蹤的算法設計中，主要假設的目標為覆蓋區域較小的單個目標，例如對動物、士兵、敵軍坦克等的位置追蹤。隨著傳感器網絡的工業應用以及安全智慧城市理念的普及，傳感器網絡對于大范圍連續目標的探測與追蹤已經開始被學者們廣泛研究，例如大范圍區域街道車流量信息的采集、海洋面油類液體泄漏、工業制油過程中有毒氣體的探測、高速道路山區山體大面積滑坡的探測等研究。

2 相關文獻回顧

2.1 目標追蹤的應用

利用傳感器網絡進行目標追蹤即利用節點間的信息交互去探測目標出現、位置移動、形狀變化等相關信息，并將探測到的信息連續播報給基站。

應用的目標對象，根據其相關特點的不同，大致可以分為兩類：單個目標與連續目標。單個目標與連續目標相比通常尺寸較小，覆蓋范圍較小，形狀變化差異不大，例如單個動物、汽車等。而連續目標往往蔓延于大范圍區域，并且受到環境等因素影響其形狀會發生不斷變化，例如有毒氣體泄漏蔓延的過程，擴散區域較廣，隨著風或者其他因素影響其形狀會發生一定的動態改變。表1給出了單個目標與連續目標的相關比較。

表1 單個目標與連續目標對比

2.2 連續目標追蹤算法分析

在連續目標追蹤算法中，一般均是通過有選擇的播報邊界處附近節點的信息，根據邊界信息去確定連續目標的形狀與位置。例如在算法[1-2]當中，作者主要通過在邊界節點當中選擇一定的代表節點去播報邊界信息，這樣可以減少播報節點個數，相應的減少播報信息量，以此來減少能量開銷。在此類算法中，每個節點會保存其所有鄰居節點序列表，當一個節點探測到目標時會立即播報其探測信息給其所有的鄰居節點。信息內容為節點ID號及地理位置信息。節點接收其鄰居節點傳來的探測信息后其相應的鄰居列表當中對應的鄰居節點探測狀態標記也會發生改變（感知到目標即為1，未感知為0）。如果一個節點的鄰居序列號中存在不同探測狀態的節點信息,則可以將此節點確定為邊界處節點。

算法[3-4]選取RBN（代表邊界節點）時依據節點所接收到的信息數即邊界節點的鄰居節點個數，算法[5]利用選取為邊界所需的條件優先級為每個節點設計倒計時，然后依據一定的距離范圍均勻的去選擇代表節點。算法[6]中考慮到目標擴散與收縮（呼吸）問題，利用調節節點感知范圍去選擇部分節點作為代表節點，這主要考慮了連續目標形狀的變化。

3 算法原理

3.1 能量模型

本文采用文獻[7]中的一級模型作為能量模型，通過距離d傳輸或接收m比特的數據包所消耗的能量為

節點在閑置廣播與接收廣播模式下近似有相同的能量消耗[8]。

3.2 節點狀態調度

算法當中采用的節點調度思想如下：

（1）初始網絡中所有節點處于偵聽狀態，感知網絡當中是否存在目標出現。

（2）節點周期性的在偵聽與睡眠狀態之間進行狀態轉換，當切換為偵聽狀態時，感知到目標，則節點狀態會立即轉變為活動。而當切換為偵聽狀態時，無法感知到目標，則節點會立即進入休眠狀態，從而進行下一周期切換的準備。

（3）當節點此刻覆蓋目標則處于活動狀態，與周圍節點進行通信，只有當節點無法感知到目標或者節點自身無法感知到目標并且節點的鄰居節點當中不存在感知節點后，則此節點重新進入休眠狀態。

（4）當節點處于休眠或者處于活動狀態過程中能量耗盡，則節點會進入死亡狀態，無法再進行新一輪周期性的狀態轉換。

相關節點的狀態轉換關系如下圖1所示。

圖1 節點狀態調度圖

3.3 候選邊界節點選擇

CBN（候選邊界節點）的選擇主要基于鄰居信息描述表NDT。當一個節點初始布置于網絡中，其并不存有任何鄰居節點的信息，布置完后開始交互信息，構建相應的NDT。CBN選擇過程如下：

（1）初始忙碌感知步驟：一個節點u拓撲于網絡當中，首先會初查其初始的標記，如果標記為空，則其廣播一個通知信息包給其鄰居節點，包中包含其自身ID，地理位置坐標，候選邊界點標記b及時間標記t。

（2）更新步驟：如果一個節點接收到通知包，與自身感知狀態進行比較，如果存在差異并且節點的自身狀態標記為未感知狀態。則更新自身為CBN。圖2(a)、(b)以連續目標邊界線移動的形式給出了目標進入與離開時CBN的選擇方法。如圖(a)所示，當目標邊界從a移動到c的過程中，隨著不斷的有節點被覆蓋，例如長方形中代表新加入的感知節點集合，所有淡藍色節點接收到鄰居通知包，并且此類節點未被感知，則此類節點在本文中被選為CBN。如圖(b)所示，當目標離開的情況下,黑色節點從被感知到未被感知，其同樣被認作CBN。

圖2 候選邊界節點選擇

3.4 邊界節點選擇

當CBN確定后，進入從CBN集當中篩選邊界節點的過程。首先邊界感知節點依據其地理位置坐標以及其所有對應ID號的鄰居節點所對應的地理位置坐標信息進行地理距離的排序計算，假設邊界感知節點U坐標為其對應的鄰居候選邊界節點集合坐標對應距離為：

如圖3所示，波浪線代表此時刻邊界線，A、B等黑色節點代表邊界感知節點，I、O等所有非黑色節點代表候選邊界節點，節點I、J、L、M、O代表選出的邊界節點。

例如A、B、E、F、H對應只有一個候選邊界鄰居節點，則對應I、J、M、O則選為其對應邊界節點。而例如 C節點，其對應候選邊界節點有 J與 K，而則節點C對應邊界節點為J。

圖3 邊界節點選擇

3.5 虛擬邊界節點選擇

此部分，將對引入的虛擬節點做詳細描述，主要依據邊界不失真與考慮邊界失真兩種情況給予分析。不考慮邊界失真的情況下，僅僅考慮在邊界感知節點PBN與其對應的邊界節點BN之間引入虛擬節點；而在考慮邊界失真的情況下，不僅考慮PBN與BN之間的虛擬節點，同時考慮PBN與其鄰居PBN之間加入虛擬節點。具體分析如下陳述。

（1）不考慮邊界失真

當PBN接收到其對應邊界節點PBN-BN的反饋信息后，說明其PBN-BN已經知道各自相關位置信息，如下圖4所示。以A邊界感知節點與其PBN-BN為例，假設A坐標其對應節點I坐標則對應虛擬位置節點a坐標為同理不考慮邊界失真時，其它對應的虛擬節點位置信息為

不考慮邊界失真情形時，以目標邊界線為例，通過虛擬節點坐標（如圖4所示)，坐標相互連接，可以得出一段虛擬化的靠近真實邊界線的邊界（如圖中節點所示）。這樣設計的目的是在原先距離較近的邊界節點選取的基礎之上對邊界信息更精確的確定。

圖4 不考慮失真虛擬邊界線

證明：假設兩節點相鄰，真實邊界線位于此兩節點之間，假設節點位置坐標分別為兩節點連線與真實邊界交點坐標為則若分別以兩節點作為邊界點得到的誤差距離分別為由于此兩節點等概率選為邊界節點，則根據概率等分思想計算得誤差距離為：

（2）考慮邊界失真

如圖5節點A依據鄰居列表信息（地理位置與感知標記）計算出再將其與比較是否滿足公式(7)：

圖5 考慮邊界失真虛擬點構造圖

4 仿真結果分析

此部分用于分析比較設定不同閾值R0時，對平均誤差、虛擬點個數的影響。假設網絡區域大小為2000m? 2000m的二維網絡,節點個數4000，節點通信半徑為 75m,每輪采樣時間為5s，擴散中心坐標(1000,1000)，節點通信半徑75m,數據包大500Bytes。

4.1 閾值變化的影響

4.1.1 仿真環境

4.1.2 比較分析

圖6（a）(b)給出了閾值不同情況下對精度與虛擬節點個數的影響，如6（a）顯示每個折線呈現波形變動，特別是開始進程當中隨著邊界線不斷擴大，平均誤差突然遞增，隨著采樣的進行誤差趨于平穩，當目標不斷擴大到接近網絡邊界處，由于節點隨機分布于網絡，邊界處網絡密度不斷變小，出現誤差的驟變。總體趨勢看出當閾值為所得到的平均誤差較其他閾值相比更加平穩，同時也相比于閾值即無虛擬感知節點加入時的平均誤差較小。

圖6 閾值的影響

圖6（b）給出了閾值不同情形下所得到的虛擬點統計結果，首先綠色折線表示閾值情形下虛擬點個數的變化，可以看出較其他閾值下，其所構造出的虛擬點個數較少，同時其變化幅度較小，這是由于隨著擴散目標邊界線不斷擴大，其構造出的虛擬點個數僅與邊界線長度近似成線性關系，而其余閾值下，虛擬點個數不僅與邊界線長度相關還與產生的邊界感知節點個數相關，所以變化幅度較大。對于每個閾值下對應的折線，初始隨著擴散的進行，目標邊界線不斷擴大，同時節點密度不斷增大，虛擬點個數會發生顯著增加，而隨著目標區域不斷擴散接近網絡邊界區域，節點密度會驟降，雖然此時目標邊界線仍然在增大，但節點密度影響更大，從而導致虛擬點個數仍然不斷減少。

5 結束語

研究了利用智能化無線傳感器網絡探測與追蹤大范圍目標的問題，從提高追蹤精度的角度出發思考解決方案，與其他一些算法采用客觀存在的節點位置去表示邊界線不同，此算法創新性的提出了基于虛擬化的節點位置信息去確定目標邊界的思想。從候選邊界節點選取到邊界節點信息確定再到最終考慮邊界失真的影響因素出發，不斷改善虛擬點位置的引入，并且在數據匯聚與傳送階段采用網格思想將網絡劃分，利用頭節點對數據匯聚發送到Sink，盡而進一步減少數據傳遞量。最終形成了相對高精度追蹤與低能耗的連續目標追蹤策略。

[1]Jin,X.Lu,M.Park,Dynamic clustering for object tracking in wireless sensor networks[C].Proc.Ubiquitous Computing Systems(UCS)2006,Seoul,October 2006：200–209.

[2]Sajida Imran,Ozgur Ercetin,Young-Bae Ko.Continuous Phenomena Boundary Detection and Tracking in Wireless Sensor Networks through Optimized monitoring[C].IEEE Pacific Rim Conference on Communications,Computers and Signal Processing,2015.

[3]Lee,Euisin;Park,Soochang;Kim,Sang-Ha;Nam,Ki-dong; Noh,Sungkee；Reliability Support Protocol for Continuous Object Detection in Large-Scale Wireless Sensor Networks [C].IEEE International Conference on Advanced Information Networking and Applications,2011.

[4]Chang,H.Lin,Z.Cheng,CODA:a continuous object detection and tracking algorithm for wireless ad hoc sensor networks [C].IEEE ConsumerCommunicationsand Networking Conference(CCNC),2008:168–174.

[5]Luan Haoli,Zhang Yiying,Gao Dequan,Zhen Yan,Ma Xiyuan.Continuous objecttracing in wireless sensor networks[C].International Conference on Electrical and Control Engineering,2011.

[6]Jin Dong-Xu,Chauhdary Sajjad,Ji Xu,Zhang Yi-Ying.Lee, Myong-Soon，Energy-Efficiency Continuous Object Tracking Via Automatically Adjusting Sensing Range in Wireless the Sensor Network[C].Fourth International Conference on Computer Sciences and Convergence Information Technology(ICCIT 09),11/2009.

[7]R Heinzelman,A Chandrakasan,H Balakrishman.Energy efficient communication protocol for wireless microsensor networks[C].in Proc.HICSS'OO,Hawaii,USA,2000: 3005-3014.

[8]Raghunathan,C.Schurgers,S.Park,M.Srivastava,and B. Shaw,Energy-aware wireless microsensor networks[J]. IEEE Signal Processing Magazine,2002,19(2):40-50.

VNOE-based Algorithm for Continuous Target Tracking in Wireless Sensor Networks

Liu Binbin,Han Guangjie,Sun Hongwen
（College of Internet of Things Engineering,Hohai University,Changzhou 213000,China）

Aiming at the problems,low tracking precision and boundary distortion during wireless sensor network for continuous target tracking,a tracking algorithm based on VNOE(virtual node optimization effectively)is proposed in this paper,which takes advantage of virtual node location information to real boundary closer location information to construct the target boundary.It firstly determines the continuous target boundary point.Secondly,according to the related boundary node information,the virtual point location is determined.The experiment result indicates that the algorithm improves the tracking accuracy and the edge distortion.

Continuoustarget；Targettracking；Virtualposition；Shape and position；Tracking accuracy；Boundary distortion

10.3969/j.issn.1002-2279.2017.01.013

TN014

A

1002-2279-（2017）01-0053-04

劉彬彬（1990-），男，江蘇省南通市人，碩士研究生，主研方向：智能化無線傳感器網絡理論與技術。

2016-08-05