无线传感器网络中基于虚拟点优化的追踪算法

刘彬彬，韩光洁，孙洪文

（河海大学物联网工程学院，常州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