车联网定位方法与机制*

王 群，钱焕延

（1.南京理工大学 计算机科学与技术学院，江苏南京 210094;2.江苏警官学院 公安科技系，江苏南京 210031）

0 引言

车联网（Internet of vehicles，IoV）概念的提出，使智能交通系统（intelligent transport system，ITS）的轮廓逐渐变得清晰，已成为物联网（Internet of things，IoT）领域一个重要分支。车联网即车辆物联网，是以行驶中的车辆为信息感知对象，使人与车、车与车、车与道路基础设施之间实现高效的信息交换与共享，从而对人、车、路和交通设施进行智能管控，进而改善道路交通状况、提高出行效率、延伸信息化应用范围的综合信息服务与智能决策系统［1］。

综合了无线移动自组网（mobile Ad Hoc networks，MANET）和无线传感器网络（wireless sensor networks，WSNs）的通信特征，车辆节点通常有序地分布在道路交通环境中执行各种监测、通信和控制任务，以开放的无线自组织方式协调工作。与MANET相比，车联网具有自治性、多跳路由、网络拓扑动态变化、网络带宽受限等MANET所具有的各种特点，但节点的密集分布、道路通信环境的限制、节点的高速移动等特点是传统的MANET不具备的。车联网是在道路交通环境下使用的一种特殊的WSNs，它在沿袭了路由协议、MAC协议、拓扑控制、定位技术、时间同步、安全技术、数据融合与管理等WSNs所具有的成熟技术的同时，在较大程度上克服了传统WSNs节点存在的能耗、处理能力、存储能力、通信能力等方面的限制性。

车联网是一种特殊的MANET，也是一种在特定环境下使用的WSNs，还是一种特殊用途的物联网。为此，对于车联网这一新技术的研究，需要在充分考虑网络环境、节点移动规律、应用背景等特殊性的前提下，充分继承和借鉴已有的成果。其中，定位是车联网的关键技术之一，没有具体位置信息的车辆感知数据是没有实际意义和应用价值的。诚然，也可以通过为每一个车辆人工安装全球定位系统（global positioning system，GPS）或北斗卫星接收机的方式来实现车辆的实时定位，但GPS或北斗卫星系统的定位精度以及车辆行驶在城市高楼之间、林荫大道、隧道等特殊路段时接收机无法正常工作等问题，使GPS或北斗系统无法直接应用到车联网每个车辆的实时定位中，必须采用一定的机制与算法来解决相关的问题。

本文在综述MANET和WSNs中定位技术基本理论的基础上，针对车联网中车辆自身的定位要求，对比分析了适合车辆定位的理论与算法，并结合车联网技术的研究现状和发展趋势，对每一种算法在车联网中的应用特点给出了参考。

1 车联网定位方法与机制

1.1 基于测距技术的定位方法

1）RSSI:基于RSSI的定位原理是利用RSSI来判断节点间的距离。无线信号发射功率（PT）与接收功率（PR）之间的关系可以表示为PR=PT/dn，其中，d为收发单元之间的距离，n为与信号传播环境相关的传播因素。经对数运算，可得到PR=A-10nlgd，其中，常数A表示信号传输1m距离时接收信号的功率。A和n都是经验值，与具体使用的硬件和无线信号传播环境有关。

在车联网的具体实现算法中，根据RSSI测得的值，再利用三边测量法或极大似然估计法来对未知节点进行定位。因为计算接收到RSSI是商用无线芯片的基本功能，所以，基于RSSI的定位成本低，技术成熟，易于实现。但由于道路交通环境多变，信号具有较强的时变特性，经验值的确定较为复杂，导致基于RSSI的定位技术精度较低。为此，单一的RSSI定位方法在车联网中尚不适合使用。

2）TOA:TOA的定位原理是已知信号的传播速度，根据测量信号的传播时间来计算锚节点与未知节点之间的距离，未如节点在测得多个邻居节点（锚节点）的距离后，利用三边测量法或极大似然估计法计算出自身的位置。基于TOA技术的定位精度高，但对节点间的时间同步要求较高。目前，在车辆定位中使用的射频识别（radio frequency identification，RFID）定位技术就使用了TOA定位原理。

3）TDOA:TDOA的定位原理是通过计算2种不同传播速度的无线信号到达未知节点的时间差，来计算未知节点与锚节点间的距离。基于TDOA技术的定位算法很多，例如:AHLos（Ad Hoc localization system）［7］利用极大似然估计法，通过迭代计算，逐步对未知节点进行定位。另外，TDOA技术还可以与AOA，FDOA，TOA等技术结合，形成功能更加强大、应用更加广泛的定位方法。

TDOA技术具有抗干扰能力强，易于实现及定位精度较高等特点，在车联网定位中具有明显的优势。与TOA定位一样，应用环境对测距、定位精度的影响较大，这为在车联网中的具体应用带来了一定的困难。为此，如果建立基于TDOA技术的适应不同道路交通环境的数学分析模型，是推动TDOA技术在车联网中应用的一个方向。

4）AOA:AOA的定位原理是通过在接收节点（未知节点）上设置天线阵列或一组超声波接收机，用来感知发射节点（锚节点）信号的到达方向，计算节点之间的相对方位或角度，再通过三角测量法计算出未知节点的位置。

AOA定位可以同时确定节点的坐标和相对方位，在视距（line of sight，LOS）传播时的效果较好，但在非视距（NLOS）条件下，由于AOA测量值误差较大，定位效果不佳。

5）FDOA:FDOA的定位原理是利用移动节点上的2部无线信号接收机所侦测到信号的频率差来确定未知节点的位置。当2个节点之间存在相对运动时便会产生多普勒移频，它携带有移动节点的航向和速度信息，利用这些信息便可以实现对移动节点的定位和跟踪。

FDOA定位技术具有无模糊区、精度高等优点，它可以与TDOA等定位技术结合，实现更加完善的定位功能，成为车联网定位技术的一个发展方向。

基于测距技术的定位误差主要取决于节点之间的测量精度，就某一种具体测量方法而言其测量精度多与环境因素有关。在车联网具体应用中，单纯使用某一种定位方法都存在应用上的局限性，一般可通过多个定位方法的融合、多次测量求均、循环定位求精等方法提高定位精度，优化算法在具体应用过程中的可定位性。

1.2 基于非测距技术的定位方法

基于非测距技术的定位无需测量节点间的绝对距离或角度，通过对未知节点和锚节点之间距离的估算后，再利用三边测量法、三角测量法或极大似然估计法来对未知节点定位;也可以通过在网络中划定包含未知节点的虚拟区域，然后通过质心算法来确定未知节点的坐标。

1）质心算法:质心是指多边形的几何中心。质心算法的实现原理是网络中的锚节点周期性地广播用于标识节点自身身份和坐标位置的分组，当未知节点接收到的锚节点的分组达到一个门限值时，或接收锚节点分组的时间达到预设值时，将由这些锚节点组成一个多边形，该多边形的质心便是该未知节点的坐标。

质心算法本身是一个近似算法，其误差主要与无线信号的传播模型、分组数门限值或接收分组的时间、锚节点密度及分布等因素有关。例如:锚节点密度超高、分布越均匀，定位误差则越小。

2）凸规划定位估计（convex position estimation）算法［8，9］:凸规划定位算法是一种根据与锚节点的接近度（proximity）作为度量依据的粗粒度定位技术，它将节点间的通信连接视为节点位置的几何约束，进而把整个网络模型化为一个凸集，从而将节点定位问题转化为凸约束优化问题，然后使用线性规划（LP）和半定规划（SDP）方法得到一个全局优化的解决方案，确定未知节点的位置。如图1所示，未知节点存在于多个锚节点信号覆盖范围所形成的交集中（图中阴影部分），由该交集得到相应的矩形区域，然后利用质心算法计算该矩形的质心，便得到未知节点的位置。

图1 凸规划定位估计算法示意图Fig 1 Diagram of convex positioning estimation algorithm

凸规划定位算法的实现完全依赖于锚节点的信号覆盖范围与地理分布。理想状态下，算法的实现既要易于形成图中的阴影部分，又希望阴影部分的区域最小，这就要求在算法的具体设计中要充分考虑道路交通环境状态。在具体实施中，可将道路两侧的RSU作为锚节点，实现对车辆的准确、快速定位。

3）DV-Hop［10］:DV-Hop定位算法借鉴了传统网络中距离矢量（distance vector）路由协议的原理来估算未知节点与锚节点之间的距离，然后利用三边测量法或极大似然估计法对未如节点进行定位。DV-Hop定位算法的具体实现可分为3个阶段:第1阶段，通过传统的距离适量路由协议使网络中的所有节点获得到网络中不同锚节点的位置信息和最小跳数（hops）;第2阶段，每个锚节点利用第1阶段中获得的数据，通过下式估算平均每跳的距离

其中，（xi，yi），（xj，yj）分别为锚节点Si，Sj的坐标，hj为锚节点Si与Sj之间的最小跳数。每个锚节点将HopDisti值以泛洪方式在网络中广播，并使绝大多数节点从最近的锚节点接收HopDisti值。未知节点Sd根据收到的HopDisti值和到锚节点Si（xi，yi）之间的最小跳数hopsi，通过下式便可计算到该锚节点之间的距离distd→i

第3阶段，当未知节点Sd得到3个或以上到不同锚节点的距离时，利用三边测量法或极大似然估计法计算自身的位置Sd（xd，yd）。

除DV-Hop定位算法之外，文献［10］中基于距离矢量路由协议和 GPS的定位原理，提出了 DV-distance，Euclidean，DV-coordinate，DV-Bearing 和 DV-Radial定位算法，将这6种定位算法统称为APS（Ad Hoc positioning system）。例如:在DV-distance定位算法中利用RSSI测量相邻节点之间的距离，算法的其他环节与 DV-Hop相同;再如，在Euclidean定位算法中，未如节点需要同时与3个或以上的锚节点分别建立相隔2跳的关系，再通过RSSI或距离矢量路由算法确定邻居节点之间的距离，之后再通过计算未知节点到锚节点之间的距离，最后利用三边测量法或极大似然估计法来计算自身的位置。如图2所示，未知节点A分别与锚节点L，M，N建立了相隔2跳的关系，现以A与L之间的计算为例，其中节点B和C位于L的信号覆盖范围内，且利用距离矢量路由算法或RSSI算法已经确定了AC，AB，BC，BL和CL的距离，即在▱ABLC中，已知四条边的长度和一条对角线的长度，根据三角形的性质可以得到AL的长度当节点A获得了AL，AM，AN及更多与锚节点之间的距离时，就可以利用三边测量法或极大似然估计法来计算自身的位置。

图2 Euclidean定位算法示意图Fig 2 Diagram of Euclidean localization algorithm

基于APS的定位方法在车联网中具有广泛的应用前景，只要能够合理地规划锚节点的位置和数量，就可以获得较好的定位效果。但受城市道路交通环境的影响，如何使基于APS的定位算法适应各向异性网络的要求，还需要对算法进行相应的改进。

4）AHLos定位算法［7］:AHLos是一种基于 TDOA等测距技术的分布式定位算法，该算法实现的核心思想是通过迭代过程将未知节点不断升级为锚节点，新升级的锚节点从下一轮开始参与对其他未知节点的定位运算。AHLos定义了3种定位算法:原子多边（atomic multilateration，AM）算法、协作多边（collaboration multiateration，CM）算法和迭代多边（iterative multilateration，IM）算法。

AM算法即极大似然估计法，当未知节点的邻居节点中有3个及以上的锚节点时，可直接通过AM算法确定其坐标;CM算法是指当一个节点可以获得足够多的信息来形成一个由多个方程式组成并拥有唯一解的超定（over-determined）或适定（well-determined）系统时，就可以实现对同时连接多个节点的一组未知节点的定位。未知节点3和4的3个邻居节点中的锚节点都小于3，无法利用AM算法或三边测量法进行定位，但根据拓扑中的5条边可以建立拥有4个未知数（节点3和4的坐标）的5个二次方程，利用节点间协作计算出节点3和4的位置;IM算法是一个迭代过程，是指当邻居节点中的锚节点数小于3时，进入迭代过程:每一轮开始时首先通过AM算法和CM算法实现对未知节点的定位，随即将其升级为锚节点，并将此节点升级信息告知给邻居节点。每一轮操作结束后，未知节点的数量将下降，而锚节点的数量将上升。如此迭代，直到所有未知节点都被定位或没有符合AM算法和CM算法条件的节点存在时为止。

AHLos定位算法的最大优势是缓解了网络中锚节点密度较低时的节点定位问题，非常适合于车联网中信息基础设施不足或分布不均匀时的定位需求。例如:在郊外道路信息基础设施不够完善时，AHLos算法可发挥其定位优势。不过，迭代过程同时涉及到误差的累积，即产生累积误差，降低了整体的定位精度。同时，AHLos算法中并没有给出一组节点能否执行CM算法的充分条件，当执行CM算法时，节点x的解并不唯一。

在AHLos定位算法的基础上，作者又提出了n-hop multilateration primitive定位算法［11］，不仅给出了决定节点是否能够参与CM算法的条件，而且采用了卡尔曼滤波技术循环定位来减小累积误差，提高定位精度。

5）MDS-MAP定位算法［12］:MDS-MAP定位算法的实现采用了一种源自于心理测量学和精神物理学的数据分析技术——多维定标（multidimensional scaling，MDS）技术。

MDS技术利用各实体之间的相似（异）性来构造多维空间上点的相对坐标图。构造的多维空间上的点与各实体之间一一对应，通过实体的相似程度来反映空间上点的距离信息。MDS技术常用于探索性数据分析或信息可视化，现已成为一种通用的数据分析技术。

MDS-MAP定位算法由以下3个步骤组成:（1）在确定的网络区域内计算所有节点间的最短路径，利用最短路径构建MDS的距离矩阵。首先，生成整个网络的拓扑连通图，并为图中每条边赋予距离值。当节点间基于测距方式工作时，所赋值为实际测距结果;当节点间基于非测距方式工作时，节点间仅拥有连通性信息，所赋值均为1。然后，使用传统网络中的Dijkstra或Floyd最短路径算法生成节点间矩阵;（2）对距离矩阵应用MDS技术，通过保留最初的2个或3个特殊值和特殊向量，生成二维或三维的用于定位每个节点的相对坐标系统;（3）当锚节点的数量达到一定值时（二维至少3个，三维至少4个），使用线性变换，将相对坐标系统转换为绝对坐标系统，实现对节点的准确定位。

MDS-MAP是一种集中式定位算法，根据需要可在range-free和range-based 2种情况下运行，并可根据具体要求实现相对定位和绝对定位，可以实现车联网中车与车或车与道路设施之间的定位。MDS-MAP适合车联网应用的另一个优势是当锚节点密度或网络连通度较小时，能够实现对车辆节点的准确定位。

6）Cricket系统［13］:Cricket原本是用来确定移动或静止节点在建设物内部具体位置的空间定位系统，是一种典型的符号定位系统。在Cricket系统中，锚节点周期性地同时发射RF信号和超声波信号，其中RF信号中包含该锚节点的位置信息和节点ID，未知节点通过TDOA技术测量到锚节点之间的距离。当未知节点同时获得3个及以上的到不同锚节点的距离时，便可使用三边测量法确定自身的位置。

Cticket系统通过分布式定位方式提供了针对空间位置的符号定位功能，该系统对建设物内部具体空间位置（如房间号）的定位较为高效和准确，可应用于立体停车场的管理中，也可应用到具体的道路交通环境中。

2 综合分析与展望

虽然现在车联网中的绝大部分定位技术和算法都来自于WSNs，但由于应用环境和功能的特殊性，有部分在WSNs中已成熟应用的协议却不符合车联网的应用。例如:APIT（approximation point-in-triangulation test）［14］算法是 WSNs中一种典型的非距离式定位方法，它首先确定多个包含要定位的未知节点的三角形区域，再确定由这些三角形的交集所构成的多边形区域，最后计算这个多边形区域的质心，即为未知节点的位置。APIT算法的关键在于三角形区域的检测与融合，其定位精度在很大程度上取决于融合区域的大小，但受城市道路交通环境的约束，融合区域的形成较为困难，所以，APIT算法在车联网中的应用受到很大的限制。此类算法较多，不再一一列出。

虽然现在的基于WSNs的定位算法较多，但相当一部分是在本文已介绍的典型的定位算法的基础上的改进。例如:SHARP（simple hybrid absolute relative positioning）［15］算法综合了MDS-MAP和DV-distance算法的优点，它利用了MDS-MAP在确定参考节点相对坐标时具有的较高精度，并避免了计算所有节点组成的距离矩阵，同时借鉴了DV-distance算法的高效性。所以，在相同条件下，SHARP算法的精度要高于MDS-MAP和DV-distance;再如，MBAL（mobile beacon assisted localization）［16］算法的实现是利用一个安装有GPS接收机的可移动锚节点实现对网络中未知节点的定位。移动锚节点不断泛洪广播代表自身ID和位置的信息，当未知节点检测到3个或以上与该移动锚节点在不同位置的距离信息时，便可以利用三边测量法确定自身的位置。MBAL算法可在空旷区域或某些应急环境中对车辆进行定位，发挥其技术优势。另外，RFID，GSM，CDMA等定位技术也是基于本文所介绍的基本定位原理和算法的具体应用。

本文所分析的定位算法基本上针对的是二维平面系统，但在复杂的交通环境尤其是目前大量出现的立体交通系统中，必须研究适用于车联网环境的三维定位方法。目前，在WSNs领域针对三维定位算法的研究也非常活跃，也取得了一定的研究成果，如 Landscape-3D［17］，Constrained 3D［18］，SBL［19］等。不过，在目前的研究成果中，绝大部分三维定位只是在二维定位基础上的算法改进，完全独创的算法较少。例如:在Landscape-3D算法中，作为锚节点的定位辅助装置（location assistant，LA）周期性地广播其自身的位置信息，网络中未知节点通过接收到的位置信息以及RSSI来计算与LA之间的距离，再利用三边测量法等基础定位原理来确定自身位置。

车联网的定位技术源于MANET和WSNs，但长期制约MANET和WSNs应用的能耗、计算能力、通信能力、存储能力等问题在车联网中却成为非主要问题，这为车联网定位技术的研究和应用去除了一些限制。但车联网定位技术的研究不仅仅是解决车辆自身的定位问题，而是在此基础上解决人与车、车与车、车与路之间的协调通信，进而实现车辆安全行驶等实质问题。为此，在车联网中需要同时加强对绝对定位和相对定位技术的研究，以及对定位数据的融合和动态分析。

3 结束语

WSNs是近年来一个研究的热点和重点，大量的定位技术和算法不断涌现，然而现有大量定位算法都是基于基本的定位原理的应用或对典型定位算法的改进。改进也是一种创新，其创新思路和方法在车联网定位技术的研究中也值得借鉴。在车联网应用中，基于测距技术的定位方法虽然误差较小，但相对较低的定位效率与车联网部分应用要求的快速响应时间之间存在一定的矛盾。基于非测距技术的定位方法，虽然定位精度相对较低，但却能够满足车联网定位的一些要求，具有广泛的研究和应用前景。车联网虽然是一个全新的概念和应用，但与之相关的理论研究和技术应用可以在已有成果的基础上加以深入和创新。然而，目前对于WSNs和MANET的研究尚处于起步阶段，为此，对于车联网的研究还有大量的已知问题去解决和未知问题去探求。

［1］王 群，钱焕延.车联网体系结构及感知层关键技术研究［J］.电信科学，2012，28（12）:1-9.

［2］Bahl P，Padm anabhan V.Radar:An in-building RF-based user location and tracking system［C］//Proceedings of INFOCOM'2000，Israel，2000:775-784.

［3］Girod L，Estrin D.Robust range estmiation using acoustic and multmiodal sensing［C］//Proceedings IEEE/RSJ Int'1 Conf on Intelligent Robots and Systems（IROS'01），Hawaii:USA，2001:1312-1320.

［4］Ho K，Sun M.Passive source localization using time differences of arrival and gain ratios of arrival［J］.IEEE Transactions on Signal Processing，2008，56（2）:464-477.

［5］Yu H G，Huang G M，Gao J，et al.Practical constrained leastsquare algorithm for moving source location using TDOA and FDOA measurements［J］.Journal of Systems Engineering and Electronics，2012，23（4）:488-494.

［6］Gregoire D G，Singletary G B.Advanced ESM AOA and location techniques［C］//Proceedings of IEEE 1989 National AES Conference，Dayton:USA，1989:917-924.

［7］Savvides A，Han C C，Srivastava M B.Dynamic fingegrained localization in Ad Hoc networks of sensors［C］//Proceedings of 7th Annual Int'1 Conf on Mobile Computing and Networking（Mobi-Com），Rome:Italy，2001:166-179.

［8］Doherty L，Pister K S J，Ghaoui L E.Convex position estimation in wireless sensor networks［C］//Proceedings of the IEEE INFOCOM 2001，Anchorage:IEEE Computer and Communications Societies，2001:1655-1663.

［9］王福豹，史 龙，任丰原.无线传感器网络中的自身定位系统和算法［J］.软件学报，2003，16（5）:857-868.

［10］Niculescu D，Nath B.DV-based positioning in Ad Hoc networks［J］.Telecommunication Systems，2003，22（1-4）:267-280.

［11］Savvides A，Park H，Srivastava M B.The bits and flops of the N-hop multilateration primitive for node localization problems［C］//Proceesings of the lst ACM Int'1 Workshop on Wireless Sensor Networks and Applications，Atlanta:Georgia，USA，ACM，2002:112-121.

［12］Shang Y，Ruml W，Zhang Y.Localization from mere connectivity［C］//Proceedings of the 4th ACM International Smposium on Mobile Ad Hoc Networking ＆ Computing，Annapolis，Maryland:USA，ACM ，2003:201-212.

［13］Priyantha N B，Chakraborty A，Balakrishnan H.The cricket location-support system［C］//Proceedings of the 6th ACM International Conference on Mobile Computing and Networking（ACM MOBICOM），Boston:USA，ACM，2000:32-43.

［14］He T，Huang C，Brian M，et al.Range-free localization schemes for large scale sensor networks［C］//Proceedings of the 9th Annual Int'1 Conference on Mobile Computing and Networking（MobiCom'03），San Diego，USA，2003:81-95.

［15］Ahmed A A，Hongchi S，Shang Y.SHARP:A new approach to relative localization in wireless sensor networks［C］//Proceeding of 25th International Conference on Distributed Computing Systems Workshops，ICDCS 2005 Workshops，Columbus，OH，USA，2005:892-898.

［16］Kim K，Lee W.MBAL:A mobile beacon-assisted localization scheme for wireless sensor networks［C］//Proceedings of the 16th International Conference on Computer Communications and Networks（IC3N），2007:57-62.

［17］Hady S.Stephan O.A 3D-localization and terrain modeling technique for wireless sensor networks［C］//Proceedings of the 2nd ACM International Workshop on Foundations of Wireless Ad Hoc and Sensor Networking and Computing（FOWANC'09），New Orleans，Louisiana，USA:ACM，2009:37-46.

［18］Liang J，Shao J，Xu Y，et al.Sensor network localization in constrained 3D Spaces［C］//Proceedings of the 2006 IEEE International Conference on Mechatronics and Automation，Luoyang，Henan，China，2006:49-54.

［19］Yedavalli K，Krishnamachari B.Sequence-based localization in wireless sensor networks［J］.IEEE Transactions on Mobile Computing，2008，7（1）:81-94.