0 引言

无线网络的快速普及和移动智能终端的广泛应用，使得基于位置的服务(Location Based Service,LBS)的应用需求在社会生活和生产的各个领域呈现出快速、大幅增长趋势。例如团购服务、手机地图定位与导航、陌生人交友、打车软件等，以及在传统领域(如军事、抢险救灾、汽车导航等)的广泛应用。

LBS应用与发展的一个必要前提和重要基础就是良好的定位技术，但现有的定位技术在定位精度、系统成本、用户体验等方面存在较多不足，制约着LBS的发展，使得相关定位服务不能被广泛地推广使用。因此，研究不同性质的定位算法，从而提高定位系统的适用性，对于提高位置服务的质量有着重要的意义。

1 相关研究

定位技术发展过程中，由于无线定位技术具有低成本、高精确度、环境适应性强、实时性好等优点，被越来越多的人所关注。现有比较热门的无线定位技术有以下几种：基于到达时间(Time Of Arrival,TOA)等的三角定位、全球定位系统(Global Positioning System,GPS)、位置指纹定位(Location Fingerprinting Positioning,LFP)。各定位技术由于其自身的技术特点，有其独有的应用广泛、低成本、特定场合定位精度高等优点，但也有高成本、信号受建筑物影响严重而无法定位等局限性。

以目前应用较为广泛的GPS定位为例，虽然在绝大部分地区定位精度较为准确，是当前技术相对成熟、应用范围最广泛的定位导航系统^[1-2]，但由于其受环境影响较为严重，在高楼林立的都市或桥梁下面存在信号传播被阻隔或被分散开来的情况，使得定位精度较差甚至无法完成定位。TOA、到达时间差 (Time Difference of Arrival,TDOA)等定位基于三角测量技术，它们的一个共同点是发送机和接收机之间是基于视距传播的，而在实际环境中，接收机和发射机之间信号的到达时间和角度等参数会受多径影响，很难做到视距传播，算法的定位准确度因此会降低。另外还需要特别的硬件来测量信号到达的时间和角度等信息，所以用于定位的开销会很高^[3-7]。

位置指纹定位技术通过在目标地区采集的各个采样点，即指纹位置处的接收信号强度指示(Received Signal Strength Indication,RSSI)来创建一张“地图”，用于定位。位置指纹定位技术在非视距传播环境下的表现非常好，与其他定位算法不同的是位置指纹定位恰恰利用了多径效应，在非视距环境下能够进行准确定位，因此它非常适用于环境复杂地区、特殊地区以及室内环境的定位。另外，由于位置指纹定位技术本身不需要额外的硬件支持，只需要接收机能够反馈接收信号强度等信息，所以成本也相对较低^[3-7]。但缺点是越来越复杂的环境情况对接收信号强度产生变化多端的影响，使得信号强度值具有较强的动态性和随机性。

现有的无线定位技术，只有在特定的环境、定位精度要求不高或昂贵硬件支撑的条件下，才能够满足位置服务的需求而被应用。但又恰恰因为这些条件的限制，现有的无限定位技术不能被广泛地推广应用到实际的位置服务当中，在一定程度上制约着LBS的发展。目前国内一些单位和部门已经采集无线信号城区覆盖道路的路测数据，结合实际数据应用，本文提出了不依赖移动终端GPS信息的路测数据驱动的移动终端定位方法。

本文提出的无线终端定位方法与以往定位技术相比具备三大突出优点：1)以现有运营商基站作为信号发射节点，无需额外布置，节约了硬件成本；2)实验过程中，实验数据采集、实验环境选择、实验算法开发、实验结果验证等环节均基于真实环境进行，不依赖模拟环境，保证了实验的可靠真实；3)将实验结果结合电子地图展示，辅助LBS技术，提高了系统体验性。

2 路测数据驱动的移动终端定位原理 2.1 定位基本工作原理

现有位置服务技术的共性是：依据无线信号传递的信号强度等信息通过算法来确定移动终端当前单个点二维位置(经纬度)信息，而当移动终端移动时，这种定位方式并没有考虑定位的点与点之间的关联。实际上移动终端的运动是无数个点的集合，呈现出轨迹形态，而运行轨迹的无线信号变化将会体现遮挡物等影响因素，采用基于无线终端运行轨迹信号变化的特征来进行位置修正，将可以排除所有固定影响无线信号强度的因素。本文提出的移动终端定位方法摆脱了其他定位技术通过确定位置点来描述移动终端轨迹的思路，而是通过对城市无线信号覆盖数据分析将城市道路或某个区域网格划分的虚拟道路进行分割，通过线段比对来实现行为定位和位置修正。这种方法考虑了移动终端运行方向性和移动终端点与点之间的行为关联。

在一个城市，移动通信无线信号充斥着城市几乎任何角落，WiFi信号也覆盖了几乎所有重要场所。因为城市道路的地理环境各不相同，所以城市道路被移动通信运营商基站信号覆盖的强度分布也各不相同。假设城市所有道路的基站信号覆盖的强度信息建立了一个总数据库，在特定道路的基站覆盖强度信息可以分类成为一个子数据库的前提下，当移动终端实时发送基站信息(位置区码(Location Area Code,LAC)、小区识别(Cell Identity,CI)、RSSI等)给数据处理服务器，通过算法就可以判定出初始位置范围，然后通过移动终端的基站信息变化特征与道路的基站覆盖强度特征进行比对，就可以定位移动终端位置。虽然不同手机在相同地点驻留基站可能有所不同，接收相同移动通信基站信息所获取的接收信号强度信息也会有比较大差异，但在道路行进过程中驻留基站情况有规律可循，驻留相同基站时接收的信号强度变化趋势也是类似的。这种定位方式完全不依赖移动终端的GPS信息，可以避免GPS定位的不足，在移动通信无线信号覆盖完全的城市可以采用该方法单独进行位置定位，当然也可作为GPS定位方式的补充。

路测数据驱动的定位技术工作流程主要分为离线和在线两个阶段。离线阶段主要进行样本数据的采集和指纹地图数据库的建立；在线阶段依据所建立的指纹地图数据库进行移动终端的位置识别匹配工作。主要原理和流程如图 1所示。

2.2 指纹地图数据库

指纹地图，指采集点接收信号强度与采集点的二维或三维位置关系的数据库以指纹的形式在地图上进行展现。

基于路测数据的指纹地图，以专用路测设备采集城市道路数据信息后按照所采道路进行数据分类，然后将每类数据的信号强度与其经纬度位置信息进行相关映射，完成指纹数据库的建立。

在整个定位工程中，指纹地图数据库的构建对于提高定位的准确性和用户的体验性至关重要，基于城市路测数据，通过以下三个步骤建立一个完整的、可在地图上展现的指纹地图。

步骤一 基于路测数据运用基站位置定位算法确定当前通信基站物理位置：一方面可在运营商不提供基站物理位置时实现基站的主动定位；另一方面，对于步骤二中的信号覆盖范围修正可起到一定的指引作用。

步骤二 基于路测数据运用基站覆盖范围描绘算法描绘每个(LAC,CI)对应区域的信号覆盖范围，可在粗定位阶段估计移动终端初始位置点所属范围。

步骤三 在建立基于路测数据的指纹地图过程中，步骤三至为重要，直接影响着整个定位系统的定位准确性和有效性。该阶段主要构建一个包含所有采集点的所有参数信息的总数据库和三个子数据库。

其中，基于(LAC,CI)覆盖范围的子数据库1运用基站信号覆盖范围描绘算法，将当前所有采样点的(LAC,CI)覆盖范围描绘并存库。

基于道路分类的子数据库2运用基于道路分类的道路特征提取算法将采样数据点按照道路信息进行分类，并将每条道路上的(LAC,CI)变化特性进行提取保存。

基于道路基站覆盖RSSI变化的子数据库3依据子数据库2存储的单条道路(LAC,CI)变化特性，运用无线信号特征提取算法将道路上每一个(LAC,CI)覆盖段内数据的RSSI与经纬度进行相关映射，建立一个强度-位置模型库。

定位过程中，首先，依据子数据库1及当前时刻移动终端上传的(LAC,CI)参数值，确定移动终端当前时刻所处的位置范围。然后，随着移动终端实时数据的上报，依据子数据库2进一步确定移动终端所位于的城市道路信息。最后，运用终端信号特征比对算法将移动终端RSSI参数变化特征与子数据库3进行匹配，从而实时获得移动终端物理位置信息。

由于路测数据驱动的移动终端定位技术本身特性，定位结果很大程度上依赖于离线阶段建立的指纹地图数据库，所以保证指纹地图数据库的结构完善性和数据精确性是至关重要的。以下章节研究的基站位置定位和基站信号覆盖范围描绘算法，是建立整个指纹地图数据库算法集的基础。定位目标区域的基站物理位置，一方面，对于(LAC,CI)信号覆盖范围的精确刻画及信号衰减趋势等可起到重要的指引修正作用；另一方面，在实现道路数据分类、道路特征提取算法时，基站位置对于关键点的位置描述有比较好的修正。而基站信号覆盖范围描绘算法，又是构建子数据库1的关键算法，子数据库1应用在整个定位过程的粗定位阶段，也即定位的第一步。而后的定位精确与否直接依赖于第一步的定位结果，若第一步实验结果存在较大误差，则实验的最终结果将变得不可靠。

3 路测数据驱动的移动终端定位算法 3.1 路测数据特性分析

路测数据驱动的定位算法，以现有运营商基站作为信号发射节点，采集丰富的热点和重点目标区域(营业厅、地铁、学校、景点、交通枢纽、医疗机构、大型商场购物中心等)的运营商信令数据作为实验数据。图 2所示为城市部分区域道路数据采集情况，其中每一个箭头代表一个采样点。

这些数据包含移动、联通、电信的各制式数据以及WiFi数据信息，以电信4G为例，主要信息如表 1所示。

路测数据具备以下特性：

1) 一致性：不同的手机在相同地点接收相同移动通信基站信息所获取的接收信号强度信息有比较大的差异，而采用专用设备采集数据可把这种差异降到最低。

2) 连续性：数据采集过程中，设置设备采集时间间隔为3 s，保证了采集数据的密集性，易于分析基站数据连续变化特性。

3) 时效性：规定特定的采集周期，针对目标区域进行基站信号采集，保证数据的时效性，真实反映网络覆盖情况。

4) 完整性：在整个实验的数据采集过程中，运用专业的路测设备，同时采集主小区和邻小区的相关信令数据，保证数据的全面完整。

5) 可靠性：运用专用路测设备实时实地对城市道路信息进行采集，保证了数据的真实可靠性。

针对某条800 m道路的移动4G基站覆盖实测数据分析(见图 3)，图 3中上下两条轨迹分别为不同时刻的CI变化情况。可以看出一条道路可以根据基站(Base Station,BS)的(LAC,CI)覆盖情况被分割成N条线段，而针对不同方向，线段的排布是有规律可循的。据此规律可把城市道路按照不同的(LAC,CI)变化特征进行识别分类，针对不同的分段又可建立一个强度-位置映射模型。

3.2 基站定位算法

基站定位算法的主要思想是基站位于具有相同RSSI的采集点的垂直平分线上，可视为这些平分线交点分布的期望值。算法的主要步骤如下：

1) 依据(LAC,CI)值筛选出属于某一个(LAC,CI)区域的所有采集点；

2) 从上述筛选后的点集中找出所有具有相同RSSI值的采集点点对，设第i对采集点的垂直平分线方程为y=a_ix+b_i，为避免a_i、b_i出现极端情况，采用参数变换方法将垂直平分线转换为一个极坐标(r,θ)；

3) 基于所有(r,θ)坐标点进行聚类分析，计算基站坐标位置。

图 4为上述步骤2)中的参数变换示意图，其中，r为原点o到直线y=a_ix+b_i的距离，θ为射线与x轴之间的夹角。空间中的点(r,θ)对应于原坐标系中的一条直线,然后对参数空间中的所有(r，θ)点进行聚类分析。

所用到的K-means聚类算法^[8-10]主要步骤为：

1) 初始化: 随机选K个种子点作为聚类中心(c₁,c₂,…,c_K)。

2) 确定任意采集p的类别$i_{p}^{*}=\underset{i\in \left\{ 1,2,\cdots ,K \right\}}{\mathop{\operatorname{argmin}}}\,\left\{ \left\| p-{{c}_{i}} \right\| \right\}$。

3) 将属于第i类采集点集合S_i的聚类中心更新为c${{{c}'}_{i}}=\frac{1}{{{i}_{n}}}\sum\limits_{j=1}^{{{i}_{n}}}{{{p}_{j}}}$，其中p_j∈S_i，i_n为集合S_i的元素个数。

4) 如果‖c_i－c_i′‖＜σ，σ为某一给定的阈值，则程序终止；否则，重复步骤2)~4)，直到条件满足。

基站定位过程中，关键算法为K-means聚类算法，之前定位算法中的聚类分块没有考虑信号的相关性，导致分类精度不够高，从而致使基站定位精度不够高，本文提出将RSSI信号白化后再进行K-means聚类，去除数据之间的相关性，提高聚类中心的合理性和可信度，使得基站的定位精度有了一定程度的提高。

白化(Whitening)的目的是去除数据之间相关带来的冗余，保证数据的性质不变，降低相关性。数据的Whitening必须满足两个条件：一是不同特征间相关性最小，接近0；二是所有特征方差相等。常见的白化操作有主元分析(Principal Component Analysis Whitening,PCA Whitening)和零相位成分分析(Zero-phase Component Analysis Whitening,ZCA Whitening)。

PCA Whitening是保证数据各维度的方差为1，而ZCA Whitening是保证数据的各维度的方差相等即可；并且两种Whitening的用途也不一样，PCA Whitening主要用于降维且去相关性，而ZCA Whitening主要用于去除相关性，且尽量保持原数据^[11-12]。本文这里只是想去掉数据之间的相关性，因此采用ZCA Whitening。ZCA Whitening公式为式(1)~(2)：

${{x}_{PCAwhite}}_{,i}={{x}_{rot,i}}/\sqrt{{{\lambda }_{i}}}$

(1)

${{x}_{ZCAwhite}}=U{{x}_{PCAwhite}}$

(2)

式中：x_rot,i表示每个特征数据；$1/\sqrt{{{\lambda }_{i}}}$为缩放因子；x_PCAwhite表示经过PCA白化处理的数据；U表示一个特征向量矩阵。

3.3 基站信号覆盖范围描绘算法

获得单基站物理位置以后，结合所属该基站的采集数据，描绘该基站的信号覆盖范围。算法的主要流程如图 5所示。

参照流程图 5，描绘小区信号覆盖范围主要分为以下两个步骤：

步骤一 从上述筛选出的采样点点集中选取坐标极值点N个，并连成N多边形，同时，依据该初始边界多边形的每一条边将其外侧剩余数据点分成N组；

步骤二 以每一条边为判断基准，运用边界扩展算法逐步扩展已有多边形获得新的多边形，最终完成覆盖范围多边形的描绘。

其中边界描绘扩展示意如图 6所示。

假设开始时获取的N多边形为ABCD，以AB边为例，首先，从AB外侧点中选取距离线段AB最远的点E存入边界点集合中；然后从外侧剩余点中分别选取距离线段AE、BE最远的点F、G存入点集；接着再选取距离线段BG的最远点H、距离线段EF的最远点I并存入点集。至此AB边扩展为折线BHGEIFA，且其外侧不在包含数据点，即完成该边的扩展。

边界描绘扩展过程中，将每次更新后的点集重新逆时针排序后再连接相邻两点，保证多边形每条边的有向性，为判断点与直线的相对位置提供方便。如何将边界点逆时针排序，是描绘基站覆盖范围过程中的关键部分。

边界点逆时针排序的主要思想是：在x-y二维坐标系中，首先，找出边界点的坐标均值点P，做射线PQ，PQ沿x轴正方向；然后，以P点的y坐标为分界值，将所有边界点按照y值大小分为上下两部分，对于上部分的点，每个点连接P后与PQ有一个夹角，按照夹角的余弦值，由大到小排序。同理，下半部分的点按照其夹角余弦值由小到大排序；最后，合并上下点集，完成所有点的逆时针排序。算法示意如图 7所示。

4 实验结果与分析 4.1 聚类结果分析

图 8显示了聚类中心数目k从1到8变化时，白化前后的聚类精度。

由图 8可以看出，白化后的K-means算法在聚类准确度上优于白化之前的效果。而且，随着聚类中心k值的增加，效果更加明显，这是因为，在一定的定位区域内，k值越大，意味着将定位区域划分成了越多的子区域，与此同时相邻的子区域之间数据的相关性就越大，通过白化后去除数据之间的相关性带来的冗余，从而使得白化后的聚类精度有了明显的提升。由图 8也可以看出，k值过大或过小都不利于聚类精度的提高，以k等于4为分界点，k值过小，聚类精度没有明显的变化，k值过大，聚类精度下降很快。因此，k值的选取对于实验的结果有着直接的影响，为了提高实验的简易性和结果的精确性，本次实验将聚类中心值定为4。

4.2 基站定位结果分析

图 9为白化前后基站位置定位结果示意图。图中标识文字为“基站物理位置”的塔状标记表示基站的实际物理位置，另一塔状标记为算法定位的物理位置。

通过多次实验操作，白化前后基站位置定位精度统计结果如图 10所示。

由图 10可知，不同的定位精度下，对信号白化后再进行聚类，可明显提高定位精度。白化后的定位精度在2 m内的概率为60%，较RSSI无白化的定位精度提高了39%左右；在3 m内的定位精度概率为77%左右，提高了12%左右；而且，在1 m内的定位精度概率也有较为明显的提高。

分析图 9~10可知，当定位结果误差为8 m时，定位精度概率也接近100%。误差大小符合应用需求，也说明了白化对于基站位置定位精度提高的有效性。

4.3 基站信号覆盖范围描绘结果分析

运用基站覆盖范围描绘算法获得的基站单扇区信号覆盖范围如图 11(a)所示。该范围依赖于道路数据采集的完整性，所以保证定位区域采集数据的完整性、有效性，对于基站覆盖范围的定位精度至关重要。同样，也可以同时定位多个扇区的信号覆盖范围、扇区之间的公共覆盖范围，如图 11(b)所示。其中，中间重叠部分为当前两个扇区的公共信号覆盖范围。

获得的信号公共覆盖范围有以下作用：一方面，可用来分析移动信号的切换规律分析移动终端运动情况；另一方面，可进一步细化定位范围，为路测数据驱动的定位算法提供更精确的定位结果。

参考基站的物理位置，分析采集点距离基站的距离与该点信号强度值之间的变化规律，对所定位范围进行适当修正，尤其是在信号无法采集的区域，对其进行适当的扩展弥补，使得信号覆盖范围更加的精确可靠。

基站物理位置及基站信号覆盖范围将地理范围划分成以各个基站为核心的块级区域，作为整个路测数据驱动定位技术的可视化图层。在无线定位过程中，可将该层作为第一步的粗定位辅助层，参照移动用户端上传的LAC/CI参数，清晰地确定当前移动终端所处的物理位置范围，从而方便下一步的精确定位。所以定位基站物理位置和定位基站信号覆盖范围算法对于路测数据驱动的定位算法研究及基于位置的服务优化有着很重要的意义。同时，该图层还可以辅助分析信号盲区、覆盖空洞、越区覆盖等网络优化通信问题。

5 结语

路测数据驱动的无线定位技术，借助现有公共基础网络设施，不需增加任何硬件设备，只需进行软件开发即可实现移动终端位置定位。因此开展关于路测数据驱动的定位技术研究，有助于其应用推广。

本文提出了路测数据驱动的定位方法，并研究了基站定位和基站信号范围描绘两个基本算法。基站定位算法定位的所有运行商(移动、电信、联通)基站，作为实验中的信号发射节点，节省了硬件开发成本，同时对基站信号覆盖范围的分布情况和覆盖范围精确刻画起到了重要的修正参考作用。基站信号覆盖范围描绘算法，绘制基站扇区信号覆盖范围及扇区之间公共范围，作为指纹数据库的重要数据基础。

文中所述路测数据驱动的定位方法，虽然已经用实测数据人为验证了部分基本算法，但全面的算法体系尚不完善，随着基于位置的服务在实际生活中需求的不断增长，对相关定位技术及位置服务技术的优化也还有待进一步深入探讨研究。接下来可从以下方面进行研究：

1) 在定位基站扇区的覆盖范围时，需要采集大量的样本信息，对于大的目标定位区域来说，数据采集仍然是一项耗费时间耗费人力的工作。因此，在已有的定位基础上，以较小的成本，快速、准确地更新指纹地图数据库，提高定位准确性，是一件十分有意义的工作。

2) 本文实验所依据的样本数据都是采用同一型号的路测设备，没有考虑不同终端接收信号的差异性，下一步的工作考虑能否利用差分的办法，来解决定位结果受限于硬件特性的问题。

3) 由于整个定位算法体系的不完善，基于道路分类的道路特征提取算法、无线信号特征提取算法、终端信号比对算法将是下一步的主要研究工作。