劉彬彬，韓光潔，孫洪文

（河海大學物聯(lián)網(wǎng)工程學院，常州213022）

無線傳感器網(wǎng)絡(luò)中基于虛擬點優(yōu)化的追蹤算法

劉彬彬，韓光潔，孫洪文

（河海大學物聯(lián)網(wǎng)工程學院，常州213022）

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

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

1 引言

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

2 相關(guān)文獻回顧

2.1 目標追蹤的應(yīng)用

利用傳感器網(wǎng)絡(luò)進行目標追蹤即利用節(jié)點間的信息交互去探測目標出現(xiàn)、位置移動、形狀變化等相關(guān)信息，并將探測到的信息連續(xù)播報給基站。

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

表1 單個目標與連續(xù)目標對比

2.2 連續(xù)目標追蹤算法分析

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

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

3 算法原理

3.1 能量模型

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

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

3.2 節(jié)點狀態(tài)調(diào)度

算法當中采用的節(jié)點調(diào)度思想如下：

（1）初始網(wǎng)絡(luò)中所有節(jié)點處于偵聽狀態(tài)，感知網(wǎng)絡(luò)當中是否存在目標出現(xiàn)。

（2）節(jié)點周期性的在偵聽與睡眠狀態(tài)之間進行狀態(tài)轉(zhuǎn)換，當切換為偵聽狀態(tài)時，感知到目標，則節(jié)點狀態(tài)會立即轉(zhuǎn)變?yōu)榛顒?。而當切換為偵聽狀態(tài)時，無法感知到目標，則節(jié)點會立即進入休眠狀態(tài)，從而進行下一周期切換的準備。

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

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

相關(guān)節(jié)點的狀態(tài)轉(zhuǎn)換關(guān)系如下圖1所示。

圖1 節(jié)點狀態(tài)調(diào)度圖

3.3 候選邊界節(jié)點選擇

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

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

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

圖2 候選邊界節(jié)點選擇

3.4 邊界節(jié)點選擇

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

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

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

圖3 邊界節(jié)點選擇

3.5 虛擬邊界節(jié)點選擇

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

（1）不考慮邊界失真

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

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

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

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

（2）考慮邊界失真

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

圖5 考慮邊界失真虛擬點構(gòu)造圖

4 仿真結(jié)果分析

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

4.1 閾值變化的影響

4.1.1 仿真環(huán)境

4.1.2 比較分析

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

圖6 閾值的影響

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

5 結(jié)束語

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

[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-），男，江蘇省南通市人，碩士研究生，主研方向：智能化無線傳感器網(wǎng)絡(luò)理論與技術(shù)。

2016-08-05