一种基于地理指纹的室内被动定位方法

一种基于地理指纹的室内被动定位方法
【技术领域】
[0001] 本发明涉及室内定位技术领域，具体地说，涉及一种基于地理指纹的室内被动定 位方法。
【背景技术】
[0002] 随着基于位置服务技术的发展，传统的室内定位系统如GPS等已经得到普遍的发 展和运用。由于GPS信号在室内的微弱性，使得其并不能运用于室内定位服务中。因此，涌 现出一大批室内定位技术，如射频识别技术（RFID)，蓝牙技术（BlueTooth)以及室内WLAN 定位技术。随着无线通信技术的发展，目前室内普遍部署着无线局域网，因此，低成本低风 险使得室内WLAN定位技术成为目前最为主流的技术。
[0003] 现有的WLAN网络通常利用最近邻（NearestNeighborhood,NN)分类算法在室内 进行主动定位。但是，在利用最近邻分类算法在室内主动定位的过程中，由于环境改变，如 障碍的距离、人体的活动以及周围附近的其他WLAN设备产生的干扰等使得接收到的RSS值 产生非正态分布，甚至产生双峰值以及三峰值分布。而传统的最近邻算法中仅仅采用接入 点AP(AccessPoint)接收到的信号强度RSS(ReceivedSignalStrength)的均值进行计 算，因此，具有较高的定位误差。
[0004] 在公开号为CN101657014A，发明名称为"基于近邻概率法的WLAN室内定位方法" 的专利申请中公开了一种基于近邻概率法的WLAN室内定位方法。其主要是利用K近邻法（K NearestNeighborhood,KNN)首先确定前q个具有较小欧几里得距离的参考点，而后根据 这q个不同参考点的欧式距离差异来确定其不同位置的先验概率，从而解决现有室内概率 定位方法中，先验概率不确定带来的定位偏差问题。这种根据计算定位点与参考点处的欧 式距离，后根据欧式距离的差异性来得到不同参考点处的位置先验信息，仅仅是考虑到前q 个参考点处的概率性但是没有将所有参考点纳入概率范围。因此，在室内复杂环境和人员 流动场景中的RSS概率分布异常情况下，会导致的真实位置可能产生更大的欧式距离，因 此可能会导致定位误差偏离。
[0005] 这是由于在室内定位系统中，由于室内复杂变化环境和周围诸多同频段信号的干 扰，基于地理指纹匹配采集的RSS值并不总是服从其真实分布，数据采集上的偏差导致算 法精度性的下降。
[0006] 因此，亟需一种能够在RSS值为非高斯分布的复杂环境中进行室内定位的方法。

【发明内容】

[0007] 本发明的目的在于解决现有技术中在复杂环境下RSS值为非高斯分布时，室内定 位不够精确的缺陷。
[0008] 本发明提供一种基于地理指纹的室内被动定位方法，包括：
[0009] 在移动终端为离线状态的情况下，利用接入点设备采集移动终端位于参考点处的 接收信号强度值RSS，统计在一段时间内接入点设备采集到RSS值的先验概率；
[0010] 根据各参考点处的坐标位置、RSS值和先验概率构建地理指纹数据库；
[0011] 在移动终端为在线状态的情况下，测试移动终端在测试点处的RSS值；
[0012] 根据移动终端在测试点处的RSS值，基于先验概率最近邻算法将测试点与地理指 纹数据库中的参考点进行匹配，确定移动终端的定位位置。
[0013] 在一个实施例中，在利用接入点设备采集移动终端位于参考点处的接收信号强度 值RSS的步骤中，
[0014] 使接入点设备工作在侦听模式，监听由移动终端在参考点处发送的探测请求帧， 提取探测请求帧中的时间戳和RSS值。
[0015] 在一个实施例中，在构建地理指纹数据库之前还包括预处理步骤：
[0016] 将参考点处不满足预设接收强度阈值标准的RSS值删除，且将低于预设概率阈值 的先验概率值删除。
[0017] 在一个实施例中，预设接收强度阈值标准为-90dBm〈RSS〈-ldBm，所述预设概率阈 值为3%。
[0018] 在一个实施例中，在确定移动终端的定位位置的步骤中，
[0019] 选择地理指纹数据库的参考点中与测试点差别最小的K个参考点，计算K个参考 点的平均坐标得到定位位置。
[0020] 在一个实施例中，在将测试点与地理指纹数据库中的参考点进行匹配的步骤中，
[0021] 根据移动终端在测试点处的RSS值、参考点处的RSS值和先验概率，通过P-KNN算 法计算测试点与参考点的欧式距离；
[0022] 提取欧式距离最短的前K个参考点，作为地理指纹数据库中的参考点与测试点差 别最小的K个参考点。
[0023] 在一个实施例中，测试点与参考点的欧式距离表示为：
[0024]
[0025] 其中，m为无线接入点设备AP的数量，n为离线阶段每个AP获取的RSS离散数值 的数量，P#表示第j个AP获取的第i个RSS离散数值的先验概率，RSSt为在线阶段实时测 量的RSS数值，RSSm为第j个AP获取的第i个RSS离散数值。
[0026] 在一个实施例中，所述移动终端具有Wi-Fi收发模块。
[0027] 在一个实施例中，所述地理指纹数据库包括各个参考点的特征集，其中，表示参考 点特征的数据结构包括每个AP在离线阶段获取的RSS值的离散数值和先验概率。
[0028] 本发明的实施例提供一种基于地理指纹的室内被动定位方法，将先验概率应用于 K最近邻算法中来实现定位，与现有的室内定位技术相比，实现在同样时间复杂度和空间复 杂度下的定位精度提升。另一方面，还提供一种新型的获取RSS技术来监督无线终端。在 获取RSS值时，移动终端并未和接入点设备连接，在移动终端仅仅打开Wi-Fi功能，即可实 现移动终端的RSS捕获，同时对于在更加复杂室内环境下以及在室内变化波动较大的下也 能够较好地实现定位和监督功能。
[0029] 本发明的其它特征和优点将在随后的说明书中阐述，并且，部分地从说明书中变 得显而易见，或者通过实施本发明而了解。本发明的目的和其他优点可通过在说明书、权利 要求书以及附图中所特别指出的结构来实现和获得。
【附图说明】
[0030] 附图用来提供对本发明的进一步理解，并且构成说明书的一部分，与本发明的实 施例共同用于解释本发明，并不构成对本发明的限制。在附图中：
[0031] 图1是根据本发明实施例的基于地理指纹的室内被动定位方法的原理性示意图；
[0032] 图2是根据本发明实施例的基于地理指纹的室内被动定位方法的步骤流程图；
[0033] 图3是根据本发明实施例的Wi-Fi被动检测的原理性示意图；
[0034] 图4是根据本发明实施例的地理指纹数据库的数据结构示意图；
[0035] 图5是RSS统计分布图的一个示例；
[0036] 图6是RSS双峰高斯统计分布图的一个示例；
[0037] 图7是KNN算法与P-KNN算法测试点定位结果示意图；
[0038] 图8是KNN算法与P-KNN算法室内定位结果的⑶F曲线图。
【具体实施方式】
[0039] 为使本发明的目的、技术方案和优点更加清楚，以下结合附图对本发明作进一步 地详细说明。
[0040] 对于室内定位而言，确定性定位算法与概率性定位算法是两个主要的室内定位算 法。但是，由于在离线采集接收信号强度值阶段，由于室内复杂环境和同频段的无线干扰 等，RSS统计分布并不是服从理想的高斯分布。更有甚者，可能会出现双峰高斯的情况。因 此在现有技术的最近邻定位算法中，存在以下两个方面的问题。第一，在离线阶段采集到的 数据如何预处理，以及对于RSS统计分布特性不服从高斯分布的采样点，不能简单的利用 它的统计平均值来进行欧式距离计算。第二，对于概率性定位算法，算法复杂度较高，例如 贝叶斯分类，神经网络等，在利用到接收信号强度的先验概率的同时，如何避免在概率性定 位算法中降低算法复杂度。
[0041] 本发明的申请人发现，先验概率会在较大程度上影响最近邻算法所需的距离值。 同时，由于目前主流室内主动定位方法普遍存在，因此，本发明的实施例提供一种被动定 位数据采集方法，移动终端MT(mobileterminal)具有Wi-Fi收发模块，使移动终端打开 Wi-Fi功能，利用移动终端发出的扫描信号，由室内部署的AP检测该扫描信号，通过服务器 端捕获移动终端的接收信号强度值RSS。在此过程中，移动终端与AP没有连接。本发明的 实施例通过加入先验概率来进行最近邻分类算法来定位，并在AP端直接获取没有连接的 移动终端RSS值，在进一步提高室内定位精度的同时，能够将室内定位算法用于具有Wi-Fi 功能终端的检测。
[0042] 如图1所示，本发明的实施例首先在离线阶段在室内各个参考点处检测移动终端 的RSS离散值，每个AP获取的RSS组成一个向量，同时计算在一段时间内每个AP上RSS值 对应的先验概率。这些概率值和RSS数值组成一个矩阵叫做离线地图，也叫做指纹库。然 后，在在线阶段实时获取的来自移动终端的RSS数值，通过先验概率最近邻算法与指纹库 里的每个参考点的RSS值做匹配运算，取出差别最小的前K个参考点，最终利用这些选出的 参考点的坐标取平均值得到最终的定位结果。
[0043] 下文通过具体的实施例进行详细说明。
[0044] 实施例
[0045] 图2是本实施例提供的基于地理指纹的室内被动定位方法的步骤流程图。
[0046] 首先，在移动终端为离线状态的情况下，利用接入点设备采集移动终端位于参考 点处的接收信号强度值RSS，统计在一段时间内接入点设备采集到RSS值的先验概率（步骤 S210)〇
[0047] Wi-Fi移动终端首先需要通过主动/被动扫描发现周围的无线服务，再通过认证 和关联两个过程后，才能和AP建立连接，最终接入无线局域网。
[0048]Wi-Fi移动终端有两种方式可以获取到周围的无线网络信息：一种是被动扫描， 移动终端只是通过监听周围AP发送的Beacon(信标帧），该帧提供了AP以及RSS信息 等；另外一种为主动扫描，移动终端在扫描的时候，同时主动发送一个探测请求帧（Probe Request帧），通过收到探测响应帧（ProbeResponse)获取网络信号。与现有技术不同的 是，本步骤中利用移动终端MT主动扫描方式来连接无线接入点AP，对AP而言是被动接收 RSS〇
[0049] 如图3所示，Wi-Fi被动检测过程包括移动终端MT发送和无线接入点AP监听两 个过程。
[0050] 现有技术中定位算法中都是利用移动终端连接到无线接入点，继而通过无线接入 点或者移动终端来获取所需要的信号强度值。本发明的申请人通过研宄发现，移动终端发 出的探测请求帧里面包含有MAC地址，网络地址Address，时间戳Timestamp等值。使接入 点工作在侦听模式，监听由移动终端在参考点处发送的探测请求帧，提取探测请求帧中的 MAC地址、时间戳和RSS值。
[0051] 预 先设定每个参考点的位置坐标数值，在各个AP端捕获到移动终端的接收信号 强度值，并形成矩阵（表格）形式。表1为离线阶段在一段时间内，在某个参考点处每个AP 获取移动终端的接收信号强度值。其中，无线接入点AP的数量为m个，在一段时间内每个 AP共获取到n个RSS数值。表2为在一段时间内，某参考点处的RSS值以及其对应的概率 值。其中，1彡j彡m，j，m和n均为正整数。
[0052] 表1离线阶段各AP获取的RSS值统计
[0053]
[0054] 表2离线阶段各AP获取的RSS值先验概率
[0055]
[0056] 在构建地理指纹数据库之前，对?在离线阶段检测到的RSS数值和计算的先验概率 数值进行预处理，将参考点处不满足预设接收强度阈值标准的RSS值删除，且将低于预设 概率阈值的先验概率值删除。
[0057] 例如，预设接收强度阈值标准为-90dBm〈RSS〈-ldBm，所述预设概率阈值为3%。则 预处理过程包括离散点去掉过程，即RSS〈-90dBm以及RSS>-ldBm等坏点，直接去掉。由于 室内复杂环境不断变化以及其他无线信号干扰等产生的一系列低于3%的先验概率值，也 直接删除。
[0058] 接下来，根据各参考点处的坐标位置、RSS值和先验概率构建地理指纹数据库（步 骤S220)。图4是地理指纹数据库的一个示例。地理指纹数据库为在离线阶段经过预处理 后各个参考点的特征集，用于在线阶段通过定位算法进行在线匹配得出移动终端的定位结 果。在图4中显示了参考点k的特征的数据结构。该数据结构中包括对于参考点k来说， 每个AP在离线阶段获取的RSS值的离散数值和先验概率。
[0059] 在移动终端为在线状态的情况下，实时测试移动终端在测试点处的RSS值（步骤 S230)。根据移动终端在测试点处的RSS值，基于先验概率最近邻算法将测试点与地理指纹 数据库中的参考点进行匹配，确定移动终端的定位位置（S240)。具体来说，选择地理指纹数 据库中的参考点与测试点差别最小的K个参考点，计算K个参考点的平均坐标得到定位位 置。
[0060] 在步骤S240中，根据移动终端在测试点处的RSS值、参考点处的RSS值和先验概 率，通过概率性K近邻算法P-KNN(probabilistic_k nearest neighbor algorithm)算法 计算测试点与参考点的欧式距离，提取欧式距离最短的前K个参考点，作为与地理指纹数 据库中参考点差别最小的K个参考点。
[0061] 现有技术中利用KNN算法计算测试点与参考点的欧式距离，表达式为：
[0062]
[0063] 其中，RSSjt表示移动终端位于测试点处，第j个AP在时间t时刻的接收信号强度 值，m为AP的个数，^^表示在第j个AP处某时间段内的RSS平均值。
[0064] KNN算法是数据挖掘和机器学习中比较常见的也是很普通的算法。其主要思想是 根据需要分类的点与测试训练集中点做距离计算，有欧式距离，曼哈顿距离等计算方法。上 面的表达式采用欧式距离计算。
[0065] 计算出不同类别的欧式距离，然后将前K个距离最小的参考点取出来，通过计算 他们的平均坐标就得到我们实际定位的位置。在室内定位算法中，KNN中将每个点在不同 AP处一段时间内的RSS平均值（瓦反；）作为计算欧式距离的输入值。
[0066] 然而，在实际室内复杂环境下，RSS统计分布并不是服从高斯分布的，因此在表达 式（1)中利用简单的RSS统计平均值来作为计算初始值，会产生较大的定位误差。
[0067]图5是某个参考点在特定AP下，在某段时间内的接收信号强度的统计分布图。由 图5可以看出，在实际室内复杂环境下，RSS统计分布并不是服从高斯分布的，大多数情况 下是左偏。这是因为在室内条件下诸如移动终端与AP间的视距条件等产生的。
[0068] 同时，在更加恶劣的情况下甚至更加严重的会出现2个峰值的情况，如图6所示。 此时，若再利用简单的RSS统计平均值来作为计算初始值，会产生较大的定位误差。
[0069] 因此，本实施例的步骤S240中，通过P-KNN算法计算测试点与参考点的欧式距离。 对于离线阶段得到的每个RSS值的先验概率，将其运用到计算欧式距离中。这主要是为了 解决获取的RSS并不服从正态分布而导致的RSS平均值不能很好的凸显采样点的特征。在 步骤S240中，测试点与参考点的欧式距离表示为：
[0070]
[0071] 其中，m为无线接入点设备AP的数量，n为离线阶段每个AP获取的RSS离散数值 的数量，P#表示第j个AP获取的第i个RSS离散数值的先验概率，RSSt为在线阶段实时测 量的RSS数值，RSSm为第j个AP获取的第i个RSS离散数值。
[0072] 下文对步骤S210中实现被动检测的一个示例进行说明。通过一款基于Linux系 统的无线路由器Openwrt，利用改进的软件airodump能够在移动终端并未连接到无线接入 点时，在无线接入点获取RSS等值。这样就为利用移动终端来实现监控定位给出了硬件和 技术支持。Openwrt是一款基于Linux下的无线路由器，Openwrt具有高度模块化和高度 自动化的优势，同时还能进行网络组件的扩展由于源码开放式，能够很好的进行软件移植。 airodump本来是一款用于破解无线802. 11WPA-PSK和WEP的加密工具，可通过源代码编写 改变其功能。同时在windows系统中利用串口调试取出其数据，并通过辅助软件如putty 等控制无线路由器。
[0073]结果比较
[0074] 图7是KNN算法与P-KNN算法测试点定位结果示意图。从图7中可以看出，本实 施例的概率性定位算法能够产生更小的定位误差，在有些测试点出会出现超过1米的优良 性。在取K值后可以很好的看出在P-KNN算法下具有更加好的定位效果。
[0075] 从表3可以看出在不同K取值下的KNN与P-KNN比较，在平均定位精度上，P-KNN 有着更加好的定位效果，并且在最大定位误差相对KNN比较小。
[0076] 表3不同K值定位结果
[0077]
[0078] 图8是KNN算法与P-KNN算法室内定位结果的Q)F(cumulativedistribution function)累积分布函数曲线图（K= 4)。从图中可以看出，P-KNN定位误差能够比KNN展 示了更加好的效果。
[0079] 因此，本发明的实施例将接收信号强度值的先验概率引入到确定性匹配定位算法 中。在最近邻算法中，在计算欧式距离时通过利用先验概率值取代信号强度平均值。能够 同时将确定性定位算法和概率性定位算法结合起来，提高定位精度。在室内定位中，利用移 动终端主动扫描方式来连接无线接入点，在服务器端通过捕获接收信号强度值来完成定位 形成检测和监督功能。
[0080] 虽然本发明所公开的实施方式如上，但所述的内容只是为了便于理解本发明而采 用的实施方式，并非用以限定本发明。任何本发明所属技术领域内的技术人员，在不脱离本 发明所公开的精神和范围的前提下，可以在实施的形式上及细节上作任何的修改与变化， 但本发明的专利保护范围，仍须以所附的权利要求书所界定的范围为准。
【主权项】
1. 一种基于地理指纹的室内被动定位方法，其特征在于，包括： 在移动终端为离线状态的情况下，利用接入点设备采集移动终端位于参考点处的接收 信号强度值RSS，统计在一段时间内接入点设备采集到RSS值的先验概率； 根据各参考点处的坐标位置、RSS值和先验概率构建地理指纹数据库； 在移动终端为在线状态的情况下，测试移动终端在测试点处的RSS值； 根据移动终端在测试点处的RSS值，基于先验概率最近邻算法将测试点与地理指纹数 据库中的参考点进行匹配，确定移动终端的定位位置。2. 如权利要求1所述的基于地理指纹的室内被动定位方法，其特征在于，在利用接入 点设备采集移动终端位于参考点处的接收信号强度值RSS的步骤中， 使接入点设备工作在侦听模式，监听由移动终端在参考点处发送的探测请求帧，提取 探测请求帧中的时间戳和RSS值。3. 如权利要求1所述的基于地理指纹的室内被动定位方法，其特征在于，在构建地理 指纹数据库之前还包括预处理步骤： 将参考点处不满足预设接收强度阈值标准的RSS值删除，且将低于预设概率阈值的先 验概率值删除。4. 如权利要求3所述的基于地理指纹的室内被动定位方法，其特征在于，预设接收强 度阈值标准为-90dBm〈RSS〈-ldBm，所述预设概率阈值为3%。5. 如权利要求1所述的基于地理指纹的室内被动定位方法，其特征在于，在确定移动 终端的定位位置的步骤中， 选择地理指纹数据库的参考点中与测试点差别最小的K个参考点，计算K个参考点的 平均坐标得到定位位置。6. 如权利要求5所述的基于地理指纹的室内被动定位方法，其特征在于，在将测试点 与地理指纹数据库中的参考点进行匹配的步骤中， 根据移动终端在测试点处的RSS值、参考点处的RSS值和先验概率，通过P-KNN算法计 算测试点与参考点的欧式距离； 提取欧式距离最短的前K个参考点，作为地理指纹数据库中的参考点与测试点差别最 小的K个参考点。7. 如权利要求6所述的基于地理指纹的室内被动定位方法，其特征在于，测试点与参 考点的欧式距离表示为：其中，m为无线接入点设备AP的数量，η为离线阶段每个AP获取的RSS离散数值的数 量，P#表示第j个AP获取的第i个RSS离散数值的先验概率，RSS t为在线阶段实时测量的 RSS数值，RSS#为第j个AP获取的第i个RSS离散数值。8. 如权利要求1-7中任一项所述的基于地理指纹的室内被动定位方法，其特征在于， 所述移动终端具有Wi-Fi收发模块。9. 如权利要求1-7中任一项所述的基于地理指纹的室内被动定位方法，其特征在于， 所述地理指纹数据库包括各个参考点的特征集，其中，表示参考点特征的数据结构包括每 个AP在离线阶段获取的RSS值的离散数值和先验概率。
【专利摘要】本发明公开了一种基于地理指纹的室内被动定位方法，应用于室内定位技术领域。包括：在移动终端为离线状态的情况下，利用接入点设备采集移动终端位于参考点处的接收信号强度值RSS，统计在一段时间内接入点设备采集到RSS值的先验概率；根据各参考点处的坐标位置、RSS值和先验概率构建地理指纹数据库；在移动终端为在线状态的情况下，测试移动终端在测试点处的RSS值；根据移动终端在测试点处的RSS值，基于先验概率最近邻算法将测试点与地理指纹数据库中的参考点进行匹配，确定移动终端的定位位置。本发明将先验概率应用于K最近邻算法中来实现定位，能够在同样时间复杂度和空间复杂度下提高定位精度。
【IPC分类】H04W64/00
【公开号】CN104883734
【申请号】CN201510237661
【发明人】陈昊, 张轶凡, 冯志勇, 杨雷, 崔琪楣, 杨旭虹, 刘哲
【申请人】北京邮电大学
【公开日】2015年9月2日
【申请日】2015年5月12日