基于锚节点－边框的非测距车辆跟踪算法

杨秀萍，崔 强，廖朝辉

（广东工业大学 计算机学院，广东 广州510003）

0 引 言

车辆跟踪技术关键在于如何实施目标定位［1－3］。目前，主要有基于测距 （range－based）和非测距 （range－free）的两大类定位算法［4］。基于测距定位算法是通过测量锚节点（已知位置的传感节点）与未知节点的角度、距离值，从而估计未知节点的位置。经典的基于测距定位算法有：到达角度测量 法AOA （angel of arrival）［5］、到 达 时 间 测 量 法TOA （time of arrival）［6］、到达时间差测量法TDOA （time difference of arrival）［7］和 基 于 接 收 信 号 强 度 测 量 法RSSI（received signal strength indicator）［8］。非测距的定位算法是通过网络拓扑结构等信息估计未知节点的位。尽管非测距方案无需测距设备，成本低，但是其定位精度低于基于测距方案。为此，本文仅考虑基于测距定位方案。在基于测距定位方案中，利用含有噪声的位置数据去估计目标节点位置。为了实现这个目标，节点间需进行节点通信。依据节点通信范围的不同，又可将定位方案分为合作式和非合作式。所谓非合作式是指源节点仅能与锚节点通信，而合作式是指源节点能与网络内所有节点 （源节点、锚节点）通信，这两种方式均可通过分布式或集中式模式实现。尽管分布式方案具有低复杂度、高可扩展性，但是其对传播模型错误很敏感，并且处理时延长。因此，本文仅考虑集中式的非合作式定位算法。

测距方面的研究，可采取多种方式测距，如接收信号强度RSS （received signal strength）、到达时间差TDOA、到达时间TOA、往返路径时间RTT （round－trip－time）以及到达角度AOA。在应用这些测距方案，必须权衡该方案的定位精度和复杂度间的关系。例如，基于TOA 或TDOA的测距定位方案，具有高的定位精度，但是要求收／发两端具有严格的时间同步，需添加额外的设备，提高定位成本［9，10］。尽 管 基 于RSS 测 距 定 位 的 定 位 精 度 低 于TOA、TDOA，但是其不需要特殊的硬件设备，降低了系统成本［10］。基于RSS测距定位技术受到广泛关注，且常采用最大似然估计ML （maximum likelihood），然而，由于基于RSS测距定位问题是非线性和凸性，求解的ML 估计是一项挑战工作，其存在多个局部最优解。

为此，面对不同的VANET 环境，提出基于分布式的非测距车辆跟踪算法。分布式的策略提高了算法的可扩展性，同时采用非测距定位，降低了成本。该算法在实施过程中，节点观察邻居节点的信息，并将锚节点进行归类，随后建立Anchor box，再利用车辆的行驶速度对Anchor box进行抽样［12］，进一步缩小目标区域位置，最后再基于离散－抑制技术的滤波策略，跟踪车辆的位置［13］。

1 系统模型

网络区域的大小由（xmin，ymin）和（xmax，ymax）表示。车辆的行驶最大速度为υmax，且为已知参数。锚节点和车辆行驶的最大通信范围分别为Ra、Rv。在每个瞬时t，车辆观察锚节点，从而产生N 个可能状态。每个状态关联车辆所在的可能位置。依据文献 ［5］，可将其称为样本Samples，如式 （1）所示

其中，N 为样本Samples集的大小。

通过对锚节点的观察，可产生两个集合：一跳集 、二跳集 ，其定义如下［10］：

（1） ：能直接与车辆通信的车辆。即锚节点与车辆的欧式距离dav≤Ra。

（2） ：通过邻居节点间接地与车辆通信的锚节点，即锚节点与车辆的欧式距离Ra＜dav≤Ra＋Rv。

2 基于非测距的车辆跟踪

本节，将分析提出非测距的车辆跟踪算法。提出的算法可分为观察 （observation）、预测 （prediction）和滤波（filter）阶段。每个车辆可能被一个或多个锚节点覆盖，并估计自己所在的可能区域 （region），再利用Monte－Carlo算法进一步缩小自己 （车辆）所在位置点 （points）。最后通过离群－抑制技术 （outlier rejection technique）进行滤波，剩余的Points就是车辆最终的位置估计值。

（1）Observation

首先，锚节点周期地广播ID 以及位置信息。同时，每个车辆将自己的一跳锚节点的位置信息传递给邻居车辆。在最初时刻，车辆监听所有锚节点以及邻居车辆，并存储所监听到的锚节点位置信息，存储格式如式 （2）所示

式中：AP——邻居列表，Ij——锚节点j的ID 号。（xj，yj）为节点j的位置。

给定车辆υ，列表中的锚节点j可分为两类：一类属于一跳集 、一类属于二跳集 ，如式 （3）、式 （4）所示

（2）建立锚节点边框Anchor box

所谓锚节点边框Anchor box就是一个区域，即一跳和二跳锚节点覆盖的重叠区域。因此，box所在位置很大可能就是车辆所在的区域位置。在时刻t，Anchor box区域如式 （5）所示

若锚节点j的位置为（xj，yj），j＝1，2，…，N ，则一跳锚节点的Anchor box的参数如式 （6）所示

对于二跳锚节点

式 （6）、式 （7）中的min、max 表示求最小、最大运算。

图1显示了由3个锚节点构成的Anchor box，黑实点表示锚节点，圆圈表示锚节点通信范围，阴影矩形表示Anchor box。若只有一个锚节点，那整个锚节点通信范围就为Anchor box。

图1 Anchor box

（3）Box抽样

一旦建立了Anchor box，需对其进行抽样。前一时刻t的样本集如式 （8）所示

考虑节点行驶速度vmax，则抽样后的Anchor box的边缘长度为2 vmax。经第ith抽样后，Anchor box表示为Si

其中，式 （9）的4个参数如式 （10）所示

抽样后的Anchor box如图2所示。经抽样后，缩小了区域范围，降低计算复杂度，也节省了车辆能量。

图2 抽样后的Anchor box

（4）位置估计

在建立了由车辆所在的可能位置所构成的抽样集后，估计车辆的位置（xest，yest），利用式 （8）可得

提出的整个算法的流程如图3所示。

图3 算法流程

3 性能分析

本节，分析提出非测距的跟踪算法。

3.1 仿真环境

考虑面积为500m×500 m 网络区域，共425个节点，其中锚节点数85个。车辆行驶的最大速度、最小速度分别为10m／s、0m／s。节点间依据IEEE 802.15.4协议进行通信。为了显示提出算法的有效性，与文献 ［10］提出MCL方案进行对比仿真。

3.2 仿真数据及仿真

在仿真过程中，考虑由通信范围归一化的平均跟踪误差 （normalized by radio range average tracking error）评估性能。同时考虑离群－抑制技术。在每一时刻，计算所有跟踪误差E 的均值M 和标准方差S。若满足

就丢弃跟踪误差E，不进入计算跟踪误差的平均值，其中E、M 、S 分别表示跟踪误差、跟踪误差的均值和方差。

为了分析采用Outlier rejection 技术的有效性，图4、图5显示了有、无采用Outlier rejection技术的平均跟踪误差曲线。若采用了，在图中标识为with outlier rejection；否则标识为without outlier rejection。

图4 提出算法的归一化的平均跟踪误差

图4显示所提出算法的平均跟踪误差。从图4 可知，随着仿真时间的增长，平均跟踪误差呈稳定的趋势。当时间大于15s后，without outlier rejection的归一化的平均跟踪误差为0.09，而with outlier rejection的归一化的平均跟踪误差仅为0.07，下降了20%。这说明outlier rejection技术的有效性。

图5显示MCL 的平均跟踪误差。与图4 相似，通过Outlier rejection降低了平均跟踪误差约20%。将图4与图5进行比较可知，提出的算法极大降低平均跟踪误差。例如，在时间大于15s，MCL 方案在有、无采用Outlier re－jection技术的归一化的平均跟踪误差分别为0.2、0.3，而提出算法的仅为0.07、0.09，提出的算法有效地降低了平均跟踪误差。

图5 MCL归一化的平均跟踪误差

图6显示了比较了MCL和提出的算法的归一化平均跟踪误差随车辆速度的变化情况，且车辆速度从10m／s变化至60m／s。

图6 归一化平均跟踪误差随车辆速度的变化情况

从图6可知，随着车辆速度的提升，跟踪误差呈增加的趋势。图6的数据再次验证了Outlier rejection技术能够有效地降低跟踪误差。此外，与MCL方案相比，提出算法在整个车辆速度变化范围内的平均跟踪误差得到有效的下降，并且车速越大，下降地越明显。当车速为50 m／s时，下降了约50%。

图7显示了两个方案的平均跟踪误差的偏差 （average tracking error deviation）情况。从图7可知，Outlier rejection技术使误差更稳定。而提出的算法的偏差都集中于－0.05至0.05范围内，这也说明提出的算法能够有效地降低平均跟踪误差。

4 结束语

图7 平均跟踪误差的偏差

针对智能城市的车辆跟踪问题，提出基于非测距的分布式目标跟踪算法。分布式的策略提高了算法的可扩展性，同时采用非测距定位，降低了成本。该算法在实施过程中，节点观察邻居节点的信息，并将锚节点进行归类，随后建立Anchor box，再利用车辆的行驶速度对Anchor box进行抽样，进一步缩小目标区域位置，再基于离散－抑制技术的滤波策略，跟踪车辆的位置。与MCL方案相比，提出的基于非测距的分布式目标跟踪算法能够有效地跟踪车辆，归一化的平均跟踪误差约为0.09。

［1］Sahinoglu Z，Gezic S I，Guvenc I.Ultra－wideband positioning sytems：Theoretical limits，ranging algorithms and protocols［M］.English：Cambridge University Press，2008.

［2］Patwari N，Hero A，Perkins M，et al.Relative location estimation in wireless sensor networks［J］.IEEE Transactions on Signal Processing，2013，51 （8）：2137－2148.

［3］Cheung KW，So HC，Ma WK，et al.A constrained least squares approach to mobile positioning：Algorithms and optimality ［J］.EURASIP Journal on Applied Signal Processing，2006：1－6.

［4］Lazos L，Poovendran R.Serloc：Secure range in dependent localization for wireless sensor networks ［C］／／Proceedings of the 3rd ACM Workshop on Wireless Security.ACM，2004：21－30.

［5］Hu L，Evans D.Localization for mobile sensor networks［C］／／Proceedings of the 10th Annual International Conference on Mobile Computing and Networking.ACM，2004：45－57.

［6］Zhang Y，Liu S，Jia Z.Localization using joint distance and angle information for 3d wireless sensor networks ［J］.Communications Letters.IEEE，2012，16 （6）：809－811.

［7］Zhou Y，Li J，Lamont L.Multilateration localization in the presence of anchor location uncertainties［C］／／Global Communications Conference.IEEE，2012：309－314.

［8］Kumar S，Sharan V，Hegde R M.Energy e＿cient optimal node－source localization using mobile beacon in Ad－Hoc sensor networks［C］／／Globecom Ad Hoc and Sensor Networking Symposium，2013：509－514.

［9］Ekim P O，Gomes J，Xavier J，et al.Robust localization of nodes and time－recursive tracking in sensor networks using noisy range measurements ［J］.IEEE Transactions on Signal Processing，2011，59 （8）：3930－3942

［10］Baggio A，Langendoen K.Monte carlo localization for mobile wireless sensor networks ［J］.Ad Hoc Networks，2008，6（5）：718－733.

［11］Saleet H N，Langar R，Naik K.Intersection－based geogra－phical routing protocol for VANETs：A proposal and analysis［J］.IEEE Transactions on Vehicular Technology，2011，60（9）：4560－4575.

［13］Vaghefi R M，Gholami M R，Buehrer R M.Cooperative received signal strength－based sensor localization with unknown transmit powers［J］.IEEE Trans Signal Process，2013，61（6）：1389－1403.