基于移动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