基于概率阈值通信感知的WSNs目标跟踪算法*

沈才樑， 杜焕强

(1.浙江大学 计算机科学与技术学院，浙江 杭州310027； 2.浙江工业职业技术学院 设计与艺术分院， 浙江 绍兴 312000)

计算与测试

基于概率阈值通信感知的WSNs目标跟踪算法*

沈才樑1,2， 杜焕强2

(1.浙江大学 计算机科学与技术学院，浙江 杭州310027； 2.浙江工业职业技术学院 设计与艺术分院， 浙江 绍兴 312000)

针对移动Sink节点目标跟踪定位时间长，能耗大等问题，提出基于概率阈值通信感知的WSNs目标跟踪算法。采用离散数据传输方式，并定义目标信息传输概率阈值来确定是否将节点当前位置信息由传感器节点传输到Sink节点。若当前位置信息不传输到Sink节点中，则使用最近一次通报的目标位置信息进行目标定位。然后开启目标周围相关传感器节点来有效降低算法数据传输量，并保持足够的定位精度。仿真结果显示：该方法比预测跟踪算法降低数据传输量87 %左右，比动态目标跟踪算法降低跟踪时间33.7 %左右。

概率阈值； 通信感知； 无线传感器网络； 目标跟踪； 能耗节省

0 引 言

无线传感器网络(wireless sensor networks，WSNs)常用作目标探测，如战场监测，野生动物监测等[1,2]。移动Sink节点跟踪目标是最小化跟踪时间和数据传输消耗[3～4]。传统方法多基于连续时域，此方法会短期内消耗大量能量，降低网络寿命[5～6]。

目前，仅有较少文献对移动Sink节点WSNs定位进行研究，如 Kosut O等人[7]以目标二维晶格随机游走方式，大幅降低数据传输量，但由于数据沟通不及时，存在Sink节点移动的盲目性。Tsai H W等人[8]提出更加复杂的定位跟踪模型，首先目标节点位置信息被传递到信标节点处，然后引导Sink节点移向目标。文献[9]中也提出类似方法，并且考虑了目标速度和方向变化，但模型过于复杂，反而不利于节省能耗。

为进一步提高算法性能，在启发式优化规则[10]和不确定性方法[11]基础上，结合预测跟踪方法[12]，本文提出一种基于概率阈值通信感知的WSNs目标跟踪(PTCP-WSNs)算法，通过仅开启能探测预测目标位置的传感器节点，在根本上降低能耗。

1 PTCP-WSNs算法

1.1 算法描述

该算法基于离散时间序列，目标和Sink节点各自向某个方向移动，最大移动速度vmax已知，目标运动方向随机，Sink节点移动方向根据WSNs信息确定。在每个时段内，Sink节点可到达位置(xS,yS)满足速度约束

(1)

d[(xS,yS),(xD,yD)]=min,

(2)

令(xC,yC)为当前探测目标位置，由于仅在特定时段才将目标信息传递到Sink节点，因此，若在坐标(xD,yD)更新时，信息被传送，那么,(xD,yD)=(xC,yC)。而其他情况下，Sink节点移向坐标(xD,yD)，此时,(xD,yD)≠(xC,yC)。令dir(x,y)为Sink节点移向(x,y)的方向，P[dir]为Sink节点移向该方向时与最近通报目标位置(xD,yD)距离减小概率。给定条件

P[dir(xC,yC)]-P[dir(xD,yD)]≥threshold.

(3)

若满足条件，坐标(xC,yC)传入Sink节点，并计算P[dir]，给出目标可能出现位置

A={(x,y):tT(x,y)≤tS(x,y)},

(4)

式中tT(x,y)为目标移向(x,y)最短时间，tS(x,y)为Sink节点移向(x,y)最短时间。

令(xS,yS)C,(xS,yS)D为Sink节点下一刻分别沿dir(xC,yC),dir(xD,yD) 进入的区段。区域A可定义两子集：AC为与(xS,yS)C更近区域，AD为与(xS,yS)D更近区域,可表示为

(5)

则概率值P[dir]的计算公式为

(6)

如图1，目标和Sink节点分别为“T”和“S”。目标速度1格/每时段，Sink节点速度2格/每时段。灰色为Sink节点可跟踪区域 。方向箭头1为dir(xC,yC)，方向箭头2为dir(xD,yD)，则Sink节点分别沿方向1，2的下一时刻坐标为

(7)

图1中，灰色1区域为子集AC，灰色2区域为子集AD,则在该图例中，|A|=26,|AC|=11，|AD|=10。根据公式(6)可得P[dir(xC,yC)]=0.42，P[dir(xD,yD)]=0.38。

图1 概率值算例

1.2 对比算法选取与设计

预测跟踪算法[12]和动态目标跟踪算法[13]是控制移动Sink节点移向移动目标较有效的控制策略，选取作为对比算法。跟踪操作伪代码与传输条件如表1所示。

表1 对比算法

(8)

预测跟踪算法目标位置信息在每个时段都会传递给Sink节点，这种方式存在问题是数据传输量大。动态目标跟踪算法中，Sink节点会移向信标节点(xD,yD)，并将当前探测到的目标位置(xC,yC)设为新信标节点，此方式数据传输量相比预测算法小。

2 仿真实验与分析

2.1 模拟环境实验

仿真区域为100m×100m方形区域，在1m×1m小方格中设置1只无线传感器，则共有10 000只无线传感器，每个传感器可达覆盖周围4个方格。目标速度1方格/每时段，Sink节点速度2方格/每时段。基于9个随机目标，如图2。Sink节点初始位置(5，5)m，目标初始位置(50,50)m。选取信息传输最短路径来计算跳数(hop)。

选取跟踪时间和hop数为评价指标，概率阈值范围threshold∈[0,0.9]，如图3所示。

图3 仿真对比数据

图3可看出:本文算法在平均hop数和跟踪时间上均优于对比算法，并且图中给出了概率阈值变化对评价指标影响情况：随概率阈值增大，算法平均hop数先减小，后达到饱和，而平均跟踪时间先不变，在达到触发点后(threshold≈0.3)，随着概率阈值增大而增大。与预测跟踪算法相比，动态目标跟踪算法能够降低平均hop数87 %左右，而本文算法在threshold=0.2时，平均hop数也相比降低87 %左右，但动态目标跟踪算法所需跟踪时间要高出预测跟踪算法52 %左右。总体上，在threshold∈[0,0.9]范围内，本文算法在上述两个指标均要明显优于所对比算法。

图4(a),(b)分别给出各算法在随机移动目标中的跟踪时间和hop数分布情况。根据图3仿真结果，选取概率阈值为threshold=0.2，从图中可看出:本文算法的hop数都是最少的，和动态目标跟踪算法所需hop数基本一致，而所需跟踪时间与预测跟踪算法近似，互有高低。这说明本文算法在有效降低通信消耗的前提下，并未增加跟踪算法的执行时间，相比对比算法优势明显。

图4 各目标仿真结果

2.2 真实环境实验

考虑到成本等因素(共需10 000只传感器)，上述实验是模拟实现的，为对比少量节点网络和实际环境条件下的目标跟踪结果，构建实际仿真环境如图5所示。

图5 实验环境构建

表2 评价指标对比数据

从表2可看出:本文算法在平均跟踪时间上，略差于预测跟踪算法，而在平均hop数上略差于动态目标跟踪算法，但差距不明显。在少量节点情况下，本文算法的平均跟踪时间相比动态目标跟踪算法降低39 %左右，而平均hop数相比预测跟踪算法降低77 %左右，因此，本文算法在综合评价指标全面性上要好于对比算法。图6给出本文算法在实际环境下的跟踪路线，图中点画线为目标移动轨迹，实线(图中抖动曲线)为Sink节点移动轨迹，跟踪轨迹抖动是由小车的晃动引起的。从图中可看出:Sink节点能够快速有效地跟踪到目标轨迹，从而验证了算法有效性。

图6 移动Sink节点跟踪轨迹

3 结束语

本文提出一种基于概率阈值通信感知的WSNs目标跟踪算法，通过目标信息传输概率阈值，来确定Sink节点开启的目标位置传感器，以此来降低开启传感器数量和降低数据传输量，有效解决了移动Sink节点目标跟踪定位时间过长，能耗较大的问题。由于实验条件所限，仅实现少量无线传感器条件下的实际环境测试。

WSNs target tracking algorithm based on probability

threshold communication perception*SHEN Cai-liang1,2, DU Huan-qiang2

(1.School of Computer Science and Technology,Zhejiang University,Hangzhou 310027,China; 2.Department of Design and Art,Zhejiang Industry Polytechnic College,Shaoxing 312000,China)

Aiming at problem of long time of target tracking and localization and high energy consumption of mobile sink node,WSNs target tracking algorithm based on probability threshold communication perception is proposed.Adopt discrete data transmission mode,and define probability threshold of target information transmission to determine whether transmit current location information of node from sensor nodes to sink node or not.If current position information is not transmitted to the Sink node,the recent notification of target positioning information is used.Then the related wireless sensor nodes around the target are opened,through this way the amount of data transmission is reduced,and sufficient positioning precision is maintained.The simulation results show that,the method can reduce data transmission quantity about 87 %,compared with the forecast tracking algorithm,and reduce the tracking time about 33.7 %,compared with the dynamic target tracking algorithm.

probability threshold; communication perception; wireless sensor networks(WSNs); target tracking; energy saving

2015—01—15

国家自然科学基金资助项目(60970076)

10.13873/J.1000—9787(2015)04—0111—04

TP 212

A

1000—9787(2015)04—0111—04

沈才樑(1973-)，男，浙江绍兴人，硕士，教授，主要研究方向为无线传感器网络、无线信息安全。