基于网络的定位算法研究*

陶 峥

（解放军91550部队，辽宁 大连 116023）

0 引 言

随着电脑网络的兴起，用户共享诸如打印机、磁盘存储器等设备的需求随之增多。过去，这些共享需求基于有线连接，以以太网为最流行的手段。然而，自从无线连接问世以来，从方便性、可购性、移动性及生产力优势的角度分析，无线局域网（Wireless Local Area Networks，WLAN）被推到了网络应用的前列[1]。现今，通过改善安全性，管理和安装的方便，无线热点的日益增加，WLAN已经成为极为普遍的应用，合理替代了有线网络。很多企事业单位通过在他们已有的有线网络中加入WLAN热点，极大地改善了员工的工作效率。本文聚焦WLAN其中的一项服务进行阐述，即如何在复杂多变的室内环境下高效定位人和物。

1 网络指纹定位技术

一般来说，基本的位置指纹定位系统划分为两个阶段，离线训练阶段和在线定位阶段。在离线训练阶段，将每一个参考点处采集来自各AP的一组RSS值作为一条位置指纹信息存入数据库；在在线定位阶段，利用模式匹配算法对用户移动终端实时采集的位置指纹信息和数据库中的位置指纹信息进行比较来获得用户的实际物理坐标[2]。

1.1 离线网络

在离线训练阶段，系统执行位置指纹信息的采集和训练，具体步骤如下。

步骤1：从定位区域内的各AP上采集RSS值。首先，用户移动终端在每一个参考点处从参与定位的R个AP上获取一组RSS值，将在第j（j=1,2,…,M）个参考点上采集到的RSS值和时间τ表示为dj(τ)=[d1,j(τ),…,dR,j(τ)]T,τ=1,…,t，t＞1，其中 di,j(τ)为第j个参考点在时间点τ上接收到第i个AP的RSS值，t为采样时段。

步骤2：将位置指纹信息发送至数据库。在这一步，将每一个参考点在采样时段各时间点的RSS值 求 平 均， 记 为 dj=[d1,j,d2,j…,dR,j]T， 其 中并将dj发送给服务器，同时服务器会接收到第j个参考点的相关物理位置信息Locj=[xj,yj]T。因此，位置指纹地图可以表示为D=[d1,d2,…,dM]。

步骤3：训练。在离线训练阶段的最后，服务器根据模式匹配算法的要求，将在定位区域内各参考点上采集的RSS信息训练成指定的位置指纹格式，将位置指纹信息的训练结果存入数据库。

1.2 在线网络

在在线定位阶段，待定位点用户移动终端通过模式匹配算法比较实时的位置指纹信息和数据库中的位置指纹信息获得待定位点的实际物理坐标，具体步骤如下。

步骤1：实时采集RSS值。当用户请求获取物理位置信息时，用户移动终端先在未知位置点[x,y]T上从参与定位的各AP上采集实时RSS值。

步骤2：将实时采样发送至服务器。服务器接收到来自用户移动终端的实时RSS信息，并将实时RSS信息训练成指定的指纹格式。

步骤3：执行模式匹配算法。服务器通过模式匹配算法比较用户实时的位置指纹信息和数据库中的位置指纹信息估算用户的实际物理坐标。

步骤4：发送物理坐标信息给用户移动终端。一旦服务器完成了用户物理坐标的估算，服务器便将估算结果[x,y]T发送至用户移动终端，物理位置信息将在用户移动终端上通过可视界面显示。

2 模式匹配算法

模式匹配算法是位置指纹定位系统中最重要的组成部分。一个好的模式匹配算法不仅需要精确的描绘位置指纹信息和实际物理位置信息之间的映射关系，还需要有低复杂度、低能耗等特点来满足用户实时定位的需要。因此，下面将介绍三种典型的模式匹配算法。

2.1 加权K近邻法

经典的加权K近邻法[3]通常使用欧式距离作为距离的度量。欧式距离给出两个点之间的绝对距离，如果在二维空间表示欧式距离，则为：

其中(x1,y1)和(x2,y2)是二维空间内的两点坐标。

当欧式距离应用于定位用户，式（1）可改进为：

其中si为待定位点用户移动终端测到第i个AP的信号强度，dij为位置指纹库中第j个参考点接收到第i个AP的信号强度。

在离线训练阶段，在定位区域内布置M个参考点并获取各参考点的位置指纹信息，利用这些参考点的位置指纹信息构建位置指纹库。

在在线定位阶段，欧式距离通过搜索位置指纹数据库中每一个参考点的位置指纹信息找到距离待定位点位置指纹信息最近的那个参考点，即找到最小的Lj，此法称为最近邻法。

如果选取Lj值较小的K(K≥2)个参考点为预定位参考点，并计算其对应坐标的平均值作为定位结果，即为K近邻法。计算方法为：

与原始的最近邻法相比，该法引入了K个估计位置坐标来计算待定位点的位置。从理论上讲，对定位精度会有一定提升，但是如果室内环境有较大噪声，定位误差会明显加大。

进一步根据不同预定位参考点对定位结果的贡献不同计算预定位参考点坐标加权后的和作为定位结果，即为加权K近邻法，如式（4）所示：

其中wj为预定位参考点j的权重因子，其值主要取决于预定位参考点位置指纹信息和待定位点位置指纹信息之间的欧式距离Lj， 计算方法为：

如果wj的计算结果为即为K近邻法。

加权K近邻法因其简单性和实用性等特点，目前已经成为非常流行的一种定位算法。

2.2 概率分布法

在室内无线局域网覆盖范围内，室内环境的多变使得某一点处的RSS值并不是恒定不变的，而是带有一定程度的波动。从实测来看，RSS值基本上呈现高斯分布[4]。所以，可以使用概率分布法进行匹配定位，计算待定位点的位置。

在离线训练阶段，获取每一个参考点处接收来自各AP的RSS的平均值e_rssi_i和方差d_rssi_i，其中i为AP的序号，将上述数据连同各参考点的物理坐标一同构建位置指纹库。

在在线定位阶段，在待定位点测量来自各AP的RSS值命名为rssi_AP_i，并将其与位置指纹库中的数据进行匹配运算。根据式（6）的高斯分布公式，可以获得rssi_AP_i在位置指纹库中点(x,y)处的概率pi(x,y)：

随后将每个AP的RSS分布的概率相乘，如式（7）所示，求得待定位点在参考点(x,y)处总的分布概率：

最后，将最大的p(x,y)所代表参考点的物理坐标作为定位结果。

和加权K近邻法一样，也可以在计算完待定位点在各参考点处总的分布概率p(x,y)后，取值较大的K(K≥2)个参考点作为预定位参考点，对待定位点在预定位参考点处总的分布概率p(x,y)取自然对数。如果预定位参考点有3个lnp(x1,y1)、lnp(x2,y2)和 lnp(x3,y3)， 随 后 令 a=|lnp(x1,y1)|、b=lnp(x2,y2)、c=lnp(x3,y3)，则加权后的定位算法如式（8）和式（9）所示：

类似加权K近邻法，通过添加合适的权重系数，可以有效降低定位误差。

2.3 人工神经网络法

神经网络是解决模式分类问题的强有力的数学工具，最初为了模拟人脑的运作而被提出。神经网络可以起到一个复杂的、非线性并行处理的计算机的作用。人脑由无数个神经元组成，这些神经元以某种方式组合起来进行复杂的运算（如模式识别），并同现今的计算机解法具有相同的速度和准确性。

根据神经网络的特性，可以将其应用到WLAN位置指纹定位工程应用领域。神经网络法同样分为离线训练和在线定位两个阶段。

在离线训练阶段，输入定义为每一个参考点接收来自各AP的RSS值组成的位置指纹信息(RSSAP1,RSSAP2,…,RSSAPN-1,RSSAPN)，输出定义为相对应参考点的物理坐标(x,y)。利用这些数据对神经网络进行训练，期间不断调整相关参数。

在在线定位阶段，将待定位点的位置指纹信息输入神经网络，得到的输出即为待定位点的物理坐标。

以三层前馈神经网络[5]为例，定位算法结构图如图1所示。

图1 三层前馈神经网络定位法

一般来说，三层网络即可实现位置指纹定位中各变量之间的学习和拟合，获得较准确的定位精度。但是，如果网络多于三层，就会导致网络结构复杂、网络训练耗时、易陷入局部最小点，并可导致结果不收敛问题。因此，在位置指纹定位的实际工程应用中，选取三层的网络模型即可（输入层、隐藏层和输出层）。输入层的单位数为定位区域内AP的总数目，利用定位区域内每一个参考点的位置指纹信息作为神经网络的一个输入向量；隐藏层单元数量的确定目前还缺乏清晰的理论指导，不过可以通过测试网络性能好坏的方式确定，如可以先选取较多的隐藏层单元，然后逐一减少隐藏层的单元数量，一直到网络性能显著变坏[6]。

用于WLAN位置指纹定位工程应用领域最常见的神经网络是BP神经网络[7]。

3 网络定位面临的挑战

本文将从定位精度、复杂度和可扩展性三个方面分析位置指纹定位技术面临的挑战。

3.1 定位精度

定位精度是面对一个定位系统首先应该考虑的因素之一。所有的位置指纹定位方法都要面对复杂室内环境带来的影响，如多径效应、阴影衰落、以及环境温度、人员走动包括手持设备方位等因素都能引起RSS向量之间的错误匹配，导致定位误差的增大。因此，复杂室内环境是对定位精度的首要挑战。其中，根据不同AP对定位的贡献不同给各AP加权，可以有效抵抗环境因素带来的负面影响。

3.2 复杂度

定位系统的复杂度主要和定位系统的成本相关联。复杂度主要取决于诸如硬件体系结构、计算复杂性和易用性等因素。成本主要包括产品研发、定位运算时间和电量损耗。一般来讲，定位系统越复杂，成本就越高。一个好的位置指纹定位系统设计应该做到低复杂度、低成本、运算时间快以及方便易用，尤其是在在线定位阶段。但是，很多时候高精度和低复杂度在一个系统里不能同时实现。针对这个问题，可以用聚类算法在维持定位精度的前提下，降低定位系统在在线定位阶段的复杂度。

3.3 可扩展性

在可扩展性方面，位置指纹定位系统面临的一个最重要的挑战，是当环境改变时重建位置指纹数据库的工作量过大且耗费时间。

4 结 语

本文研究基于RSS的位置指纹定位系统，首先概览位置指纹定位系统的架构，根据以往文献总结评价定位系统优劣的重要指标，其次分析经典的模式匹配算法，包括加权K近邻法、概率分布法和人工神经网络法，最后分析位置指纹定位技术面临的挑战。从本文的分析可以看出，在基于RSS的位置指纹定位技术的研究中，如何有效提高定位精度和降低在线定位阶段的算法复杂度是最具挑战性的问题。