一种基于区域划分的室内定位方法

摘要

本发明公开了一种基于区域划分的室内定位方法，涉及室内定位技术领域，本发明首先利用移动设备对信号进行采集，利用采集到的信息将其和地理位置一一对应，建立离线位置指纹数据库，然后进行分区，并从离线指纹数据库提取对应区域参考点指纹数据构建区域指纹数据库，利用区域内部生成的随机参考点和测试点指纹相似度进行最优区域选择，实现粗定位，并在粗定位区域内部采用KNN算法得到K个参考点，利用信号传播模型对参考点进行缩减得到最优参考点，最终利用最优参考点实现精准定位。本发明利用信号强度进行实时定位，成本低，鲁棒性好，定位系统稳定，精度高，操作简单方便。

权利要求

1.一种基于区域划分的室内定位方法，其特征在于：包括以下步骤：步骤1，利用智能设备在室内定位区域对AP信号进行采集，构建离线指纹数据库；

步骤1中包括：

步骤1.1，根据定位区域大小和参考点间隔以及相对位置，对参考点进行布局；

步骤1.2，离线阶段确定参考点二维地理坐标，并利用智能设备对参考点处AP进行感应，并多次收集信号强度信息；将地理位置以及信号强度一一对应，并将AP的地理位置单独记录；

离线参考点记录为：L＝{I1,I2,I3...In}每个参考点的位置记录为：Ii＝{xi,yi}参考点信号强度记录为：RSS＝{MAC1,rss1,MAC2,rss2,...MACm,rssm}每个AP的位置记录为：APm＝{Xm,Ym}；

步骤1.3，先筛选出共有AP，然后将AP在定位区域产生的信号强度值转换成图形进行分析，二次筛选出整体信号强度值较大的AP用于实验；利用信号强度针对不同AP绘制三维曲面，x和y轴数据为二维位置坐标，z轴数据为信号强度，对整体定位区域信号强度较高AP进行筛选，选取整体信号强度较高的AP作为最终选用的AP，并用于离线数据库的构建；

步骤1.4，根据经典统计方法拉伊达法则进行异常值的剔除并进行填充；

步骤2，进行区域划分，根据曲线平滑度指数确定区域内部针对每个AP和信号强度观测量选用的特征值，并构建区域指纹数据库；

步骤2中包括：

步骤2.1，对整体定位区域选取间隔进行区域划分，并对相接部分扩展，从而形成边缘区域；将定位平面划分为M个区域，生成(M‑1)个边缘区域，共存在(2M‑1)个有效定位区域，并根据步骤1.3的离线指纹数据库进行区域指纹数据库的构建；

步骤2.2，在步骤2.1生成的(2M‑1)个区域内部针对不同AP选取不同特征值：针对不同AP，分别将多次信号强度测量结果的平均数、众数、中位数、最大值的作为信号强度观测量，并计算针对此AP不同特征值作为信号强度观测量产生的曲线平滑度指数；将曲线平滑度指数较小的特征值作为针对此AP最终信号强度观测量，曲线平滑度指数计算公式如下所示：其中，N代表构建数据库时参考点的数目，RSSIi代表第i个参考点信号强度；将S值的大小作为最终RSS的观测量；

步骤3，利用随机数表法分别从(2M‑1)个区域分别抽取3个参考点，利用欧式距离度量测试点和三个参考点的信号强度相似性，选取使得ED*最小的区域确定为粗定位最终的定位区域；

步骤4，确定粗定位区域之后，对测试点和此区域各个参考点根据信号强度欧式距离进行指纹相似度度量，选取k个指纹相似度最高的参考点，取测试点接收到的最强信号AP，利用实验数据确定信号传播模型，并利用信号传播模型计算测试点到此AP距离记为r；以AP为圆心，将所得距离r与δ之差及和为半径做圆，利用圆环对K个参考点进行约束，圆环内部的参考点和KNN算法得到的K个参考点重合部分作为缩减之后的最终参考点；对缩减以后的参考点采用欧式距离度量其与测试点的相似度，依据相似度赋予位置坐标权重，最终位置坐标即为测试点位置坐标；

步骤5，用欧式距离度量最优参考点与测试点之间的相似性，依据欧式距离对其二维位置坐标赋予权重，最终实现精准位置估计。

2.根据权利要求1所述的一种基于区域划分的室内定位方法，其特征在于：所述步骤3中包括：

步骤3.1，利用随机数表法分别从(2M‑1)个区域分别抽取3个参考点；

步骤3.2，将随机选取的三个参考点记为ai‑1、ai、ai+1，将测试点记作a*，利用欧式距离度量信号强度相似性：

ED*＝EDi‑1,*+EDi,*+EDi+1,*第i个参考点在第u个AP采集到的信号强度值；

测试点在第u个AP采集到的信号强度值；

选取使得ED*最小的区域确定为粗定位最终的定位区域。

3.根据权利要求2所述的一种基于区域划分的室内定位方法，其特征在于：所述步骤4中包括：

步骤4.1，根据步骤3进行最优区域选择确定粗定位区域之后，对测试点和此区域各个参考点根据信号强度欧式距离进行指纹相似度度量，选取k个指纹相似度最高的参考点：步骤4.2，取测试点接收到的最强信号AP，利用实验数据确定信号传播模型，并利用信号传播模型计算测试点到此AP距离记为r：PL(d)(dB)＝PL(d0)+10nlg(d/d0)+X0步骤4.3，以AP为圆心，将步骤4.2所得距离r与δ之差及和为半径做圆，利用圆环对K个参考点进行约束，圆环内部的参考点和KNN算法得到的K个参考点重合部分作为缩减之后的最终参考点；

步骤4.4，对缩减以后的参考点采用欧式距离度量其与测试点的相似度，依据相似度赋予位置坐标权重，最终位置坐标即为测试点位置坐标：其中，wi为对第i个指纹位置赋予的权重。

说明书

一种基于区域划分的室内定位方法

技术领域

[0001] 本发明涉及室内定位技术领域，特别是一种基于区域划分的室内定位方法。

背景技术

[0002] 强烈的市场需求为定位和导航提供了广阔的发展空间，随着互联网行业的蓬勃发展，智能化定位也越来越深入人们的生活。GPS多用于室外定位，室内难以接收GPS信号，故
在室内进行定位时不能使用GPS技术。北斗导航定位系统安全可靠，保密性强，但星座发射
的信号过于微弱并且难以穿透墙壁，在室内定位并不适用。随着人们的需求日益强烈室内
定位在生活中扮演着越来越重要的角色。医院对患者进行定位，防止患者出现意外情况；化
工厂对工作人员进行定位，确保其远离高危化工区；养老院对老人进行定位，对其实施安全
监护。除此之外，若遇到人员被困等紧急情况时，通过进行定位还可以加快救援速度。

[0003] 目前，人们对于基于WIFI的室内定位技术的研究也日益深入。室内定位方法层出不穷，各种室内定位技术都有其优点，但均不如利用WIFI进行定位操作简单方便，可靠性强
并且应用更为广泛。例如，利用红外传感器进行定位时，需要对传感器进行部署，成本较高，
并且红外技术容易受到障碍物干扰，定位不够精确。利用惯性传感器进行定位时，容易出现
累积误差，累积误差的存在将极大降低定位精度。WIFI定位以其成本低，穿透性强，稳定性
高在室内定位中广为应用，利用现有的无线网络产生的信号强度即可实现精准并且鲁棒性
良好的定位。

发明内容

[0004] 本发明目的在于提供一种基于区域划分的室内定位技术，利用信号强度进行实时定位，成本低，鲁棒性好，定位系统稳定，精度高，操作简单方便。

[0005] 一种基于区域划分的室内定位方法，包括以下步骤：

[0006] 步骤1，利用智能设备在室内定位区域对AP信号进行采集，构建离线指纹数据库；

[0007] 步骤2，进行区域划分，根据曲线平滑度指数确定区域内部针对每个AP和信号强度观测量选用的特征值，并构建区域指纹数据库；

[0008] 步骤3，在各区域随机生成参考点，度量其与测试点相似度，并进行最优区域选择，实现粗定位；

[0009] 步骤4，采用KNN算法，根据实验数据，构建信号传播模型，利用信号传播模型对KNN算法产生的结果进行约束，确定最优参考点；

[0010] 步骤5，用欧式距离度量最优参考点与测试点之间的相似性，依据欧式距离对其二维位置坐标赋予权重，最终实现精准位置估计。

[0011] 本发明技术方案的进一步改进在于：所述步骤1中包括：

[0012] 步骤1.1，根据定位区域大小和参考点间隔以及相对位置，对参考点进行布局；

[0013] 步骤1.2，离线阶段确定参考点二维地理坐标，并利用智能设备对参考点处AP进行感应，并多次收集信号强度信息；将地理位置以及信号强度一一对应，并将AP的地理位置单
独记录；

[0014] 离线参考点记录为：L＝{I1,I2,I3...In}

[0015] 每个参考点的位置记录为：Ii＝{xi,yi}

[0016] 参考点信号强度记录为：RSS＝{MAC1,rss1,MAC2,rss2,...MACm,rssm}

[0017] 每个AP的位置记录为：APm＝{Xm,Ym}；

[0018] 步骤1.3，先筛选出共有AP，然后将AP在定位区域产生的信号强度值转换成图形进行分析，二次筛选出整体信号强度值较大的AP用于实验；利用信号强度针对不同AP绘制三
维曲面，x和y轴数据为二维位置坐标，z轴数据为信号强度，对整体定位区域信号强度较高
AP进行筛选，选取整体信号强度较高的AP作为最终选用的AP，并用于离线数据库的构建；

[0019] 步骤1.4，根据经典统计方法拉伊达法则进行异常值的剔除并进行填充。

[0020] 本发明技术方案的进一步改进在于：所述步骤2中包括：

[0021] 步骤2.1，对整体定位区域选取间隔进行区域划分，并对相接部分扩展，从而形成边缘区域；将定位平面划分为M个区域，生成(M‑1)个边缘区域，共存在(2M‑1)个有效定位区
域，并根据步骤1.3的离线指纹数据库进行区域指纹数据库的构建；

[0022] 步骤2.2，在步骤2.1生成的(2M‑1)个区域内部针对不同AP选取不同特征值：针对不同AP，分别将多次信号强度测量结果的平均数、众数、中位数、最大值的作为信号强度观
测量，并计算针对此AP不同特征值作为信号强度观测量产生的曲线平滑度指数；将曲线平
滑度指数较小的特征值作为针对此AP最终信号强度观测量，曲线平滑度指数计算公式如下
所示：

[0023]

[0024] 其中，N代表构建数据库时参考点的数目，RSSIi代表第i个参考点信号强度；将S值的大小作为最终RSS的观测量。

[0025] 本发明技术方案的进一步改进在于：所述步骤3中包括：

[0026] 步骤3.1，利用随机数表法分别从(2M‑1)个区域分别抽取3个参考点；

[0027] 步骤3.2，将随机选取的三个参考点记为ai‑1、ai、ai+1，将测试点记作a*，利用欧式距离度量信号强度相似性：

[0028]

[0029]

[0030]

[0031] ED*＝EDi‑1,*+EDi,*+EDi+1,*

[0032] 第i个参考点在第u个AP采集到的信号强度值；

[0033] 测试点在第u个AP采集到的信号强度值；

[0034] 选取使得ED*最小的区域确定为粗定位最终的定位区域。

[0035] 本发明技术方案的进一步改进在于：所述步骤4中包括：

[0036] 步骤4.1，根据步骤3进行最优区域选择确定粗定位区域之后，对测试点和此区域各个参考点根据信号强度欧式距离进行指纹相似度度量，选取k个指纹相似度最高的参考
点：

[0037]

[0038] 步骤4.2，取测试点接收到的最强信号AP，利用实验数据确定信号传播模型，并利用信号传播模型计算测试点到此AP距离记为r：

[0039] PL(d)(dB)＝PL(d0)+10nlg(d/d0)+X0

[0040] 步骤4.3，以AP为圆心，将步骤4.2所得距离r与δ之差及和为半径做圆，利用圆环对K个参考点进行约束，圆环内部的参考点和KNN算法得到的K个参考点重合部分作为缩减之
后的最终参考点；

[0041] 步骤4.4，对缩减以后的参考点采用欧式距离度量其与测试点的相似度，依据相似度赋予位置坐标权重，最终位置坐标即为测试点位置坐标：

[0042]

[0043]

[0044] 其中，wi为对第i个指纹位置赋予的权重。

[0045] 本发明成本低，鲁棒性好，定位系统稳定，精度高，操作简单方便。本发明对定位区域进行划分，粗定位时把测试点先定位在某个区域，减少了指纹匹配时的参考点数目；在精
定位过程中，首先利用KNN算法计算K个最为相似的参考点，然后利用信号传播模型进行第
二次约束，得到最优参考点，降低了计算复杂度节约了指纹匹配时间；在区域内部形成自己
的指纹数据库，并且针对不同AP根据曲线平滑度指数选取不同特征值作为信号强度观测量
相比于传统方法将信号强度均值作为观测量而言，鲁棒性较好并且提升了信号强度质量，
进一步提升了定位精度。
附图说明：

[0046] 图1为基于WiFi指纹定位系统原理图；

[0047] 图2为本发明研究内容和方法示意图；

[0048] 图3为基于信号传播模型约束的KNN算法示意图；

[0049] 其中，

[0050] △为测试点，

[0051] 为信号强度最大AP，

[0052] ○为最终用于定位AP，

[0053] ●为约束条件下缩减的AP，

[0054] r2为由模型计算得到的测试点和最近AP之间的距离，

[0055] r3为由模型计算得到的测试点和最近AP之间的距离和δ之差，

[0056] r1为由模型计算得到的测试点和最近AP之间的距离和δ之和。

具体实施方式

[0057] 为了对本发明进行更为详细的描述，将提供具体实施方式，这些实例仅仅是对本发明的阐述，不限制本发明的范围。

[0058] 本发明首先利用移动设备对信号进行采集，利用采集到的信息将其和地理位置一一对应，建立离线位置指纹数据库，然后进行分区，并从离线指纹数据库提取对应区域参考
点指纹数据构建区域指纹数据库，利用区域内部生成的随机参考点和测试点指纹相似度进
行最优区域选择，实现粗定位，并在粗定位区域内部采用KNN算法得到K个参考点，利用信号
传播模型对参考点进行缩减得到最优参考点，最终利用最优参考点实现精准定位。

[0059] 具体实施实例如下：

[0060] 一种基于区域划分的室内定位方法，具体实施方法如下：

[0061] 步骤1，利用智能设备在室内定位区域对AP信号进行采集，构建离线指纹数据库。

[0062] 步骤2，进行区域划分，根据曲线平滑度指数确定区域内部针对每个AP，信号强度观测量选用的特征值，并构建区域指纹数据库。

[0063] 步骤3，在各区域随机生成参考点，度量其与测试点相似度，并进行最优区域选择，实现粗定位。

[0064] 步骤4，采用KNN算法，根据实验数据，构建信号传播模型，利用信号传播模型对KNN算法产生的结果进行约束，确定最优参考点。

[0065] 步骤5，用欧式距离度量最优参考点与测试点之间的相似性，依据欧式距离对其二维位置坐标赋予权重，最终实现精准位置估计。

[0066] 为详细描述本发明的内容，将对发明步骤做进一步说明：

[0067] 以上步骤1具体实施过程为：

[0068] 步骤1.1，根据定位区域大小和参考点间隔以及相对位置，对参考点进行布局。确保参考点在各个区域均存在并且分布较为均匀。

[0069] 步骤1.2，离线阶段确定参考点二维地理坐标，并利用智能设备对参考点处AP进行感应，并多次收集信号强度信息。将地理位置以及信号强度一一对应，并将AP的地理位置单
独记录。

[0070] 离线参考点记录为：L＝{I1,I2,I3...In}

[0071] 每个参考点的位置记录为：Ii＝{xi,yi}

[0072] 参考点信号强度记录为：RSS＝{MAC1,rss1,MAC2,rss2,...MACm,rssm}

[0073] 每个AP的位置记录为：APm＝{Xm,Ym}

[0074] 步骤1.3，相比于较小的信号强度，RSS值较大的会在定位过程中起到决定性作用，故首先筛选出共有AP，然后将AP在定位区域产生的信号强度值转换成图形进行分析，二次
筛选出整体信号强度值较大的AP用于实验。利用信号强度针对不同AP绘制三维曲面，x和y
轴数据为二维位置坐标，z轴数据为信号强度，对整体定位区域信号强度较高AP进行筛选，
选取整体信号强度较高的AP作为最终选用的AP，并用于离线数据库的构建。

[0075] 所构建的数据库形式如表1所示。

[0076] 表1离线指纹数据库

[0077](x1,y1) {MAC1,rss1,MAC2,rss2...,MACm,rssm}
(x2,y2) {MAC1,rss1,MAC2,rss2...,MACm,rssm}
...... ......
(xi,yi) {MAC1,rss1,MAC2,rss2...,MACm,rssm}

[0078] 步骤1.4，由于室内环境复杂多样，收集到的信号强度质量参差不齐，存在大量异常值和信号强度值缺失等问题，室内环境信号强度数据大多为正态分布，根据经典统计方
法拉伊达法则进行异常值的剔除并进行填充。

[0079] 以上步骤2具体实施过程为：

[0080] 步骤2.1，对整体定位区域选取适当间隔进行区域划分，并对相接部分扩展，从而形成边缘区域，若将定位平面划分为M个区域，则生成(M‑1)个边缘区域，共存在(2M‑1)个有
效定位区域。并根据步骤1.3的离线指纹数据库进行区域指纹数据库的构建。

[0081] 步骤2.2，在步骤2.1生成的(2M‑1)个区域内部针对不同AP选取不同特征值：针对不同AP，分别将多次信号强度测量结果的平均数，众数，中位数，最大值的作为信号强度观
测量，并计算针对此AP不同特征值作为信号强度观测量产生的曲线平滑度指数。将曲线平
滑度指数较小的特征值作为针对此AP最终信号强度观测量。曲线平滑度指数计算公式如下
所示：

[0082]

[0083] N代表构建数据库时参考点的数目,RSSIi代表第i个参考点信号强度。S值的大小可以作为衡量RSSI质量的依据，针对某AP能产生较小S值的特征可以使RSSI质量较好，即可
作为最终RSS的观测量。

[0084] 以上步骤3具体实施过程为：

[0085] 步骤3.1，利用随机数表法分别从(2M‑1)个区域分别抽取3个参考点。

[0086] 步骤3.2，将随机选取的三个参考点记为ai‑1、ai、ai+1，将测试点记作a*，利用欧式距离度量信号强度相似性：

[0087]

[0088]

[0089]

[0090] ED*＝EDi‑1,*+EDi,*+EDi+1,*

[0091] 第i个参考点在第u个AP采集到的信号强度值；

[0092] 测试点在第u个AP采集到的信号强度值。

[0093] 选取使得ED*最小的区域确定为粗定位最终的定位区域。

[0094] 以上步骤4具体实施过程为：

[0095] 步骤4.1，根据步骤3进行最优区域选择确定粗定位区域之后，对测试点和此区域各个参考点根据信号强度欧式距离进行指纹相似度度量，选取k个指纹相似度最高的参考
点。

[0096]

[0097] 步骤4.2，取测试点接收到的最强信号AP，利用实验数据确定信号传播模型，并利用信号传播模型计算测试点到此AP距离记为r。

[0098] PL(d)(dB)＝PL(d0)+10nlg(d/d0)+X0

[0099] 步骤4.3，以AP为圆心，步骤4.2所得距离r与δ之差及和为半径做圆，利用圆环对K个参考点进行约束，圆环内部的参考点和KNN算法得到的K个参考点重合部分作为缩减之后
的最终参考点。

[0100] 步骤4.4，对缩减以后的参考点采用欧式距离度量其与测试点的相似度，依据相似度赋予位置坐标权重，最终位置坐标即为测试点位置坐标。

[0101]

[0102]

[0103] wi对第i个指纹位置赋予的权重。

[0104] 下面将结合附图对本发明作更为详细的说明：

[0105] 1.基于WiFi指纹的定位系统原理图：

[0106] 基于WiFi指纹的定位系统原理图如图1所示。在离线阶段主要是首先根据合适的距离和相对关系确定参考点布局，确保参考点在各个区域均存在并且较为均匀。其次在参
考点处利用智能设备对周围存在的AP进行感应，不同AP用MAC地址进行区分，将参考点位置
以及来自不同AP的信号强度一一对应，将信号信息和地理位置信息对应记录形成离线指纹
数据库。在线阶段是在测试点处使用移动设备对周围信号强度进行感应，形成信号强度指
纹信息，将其输入预先设计好的算法或者构建的模型，和离线阶段形成的位置指纹数据库
里的信息进行匹配，对位置进行估计得到最终定位结果。

[0107] 2.本发明研究内容和方法示意图：

[0108] 首先，离线阶段根据合适的距离和相对关系确定参考点布局，确保参考点在各个区域均存在并且较为均匀，在参考点处利用移动设备进行信号强度值采集，一共确定78个
参考点，参考点之间间距为1.2米，将参考点位置以及来自不同AP的信号强度一一对应，信
号强度指纹信息和位置指纹信息共同构建成指纹数据库。然后对这78个参考点进行分区，
这里依据地理位置进行分区，将其均分为三部分，对于区域交接处，将其进行扩展，扩展成
边缘区域，均分形成的区域和边缘区域共同组成有效定位区域，从之前生成的指纹数据库
中依据区域提取本区域参考点同时生成区域指纹数据库。在线阶段，将新观测到的RSS向量
输入区域指纹库，并从每个区域随机选取三个参考点，将随机选取的三个参考点记为ai‑1、
ai、ai+1，将测试点记作a*，分别用欧式距离衡量ai‑1、ai、ai+1和a*的相似度，选取使得ED*最小
的区域确定为粗定位最终的定位区域，具体计算过程如下所示：

[0109]

[0110]

[0111] ED*＝EDi‑1,*+EDi,*+EDi+1,*

[0112] 粗定位完成以后即可确定本测试点所在区域。在粗定位区域将测试点和本区域参考点采用KNN算法，选取k个指纹相似度最高的参考点。之后，根据实验数据构建信号传播模
型，由于较强信号强度具有更大参考价值并且信号强度被障碍物遮挡的几率相对较小故选
取测试点接收到的最强信号AP,并计算此AP信号到测试点的距离记为r，并设置一个较小量
δ用于增强定位系统的容错性，以最强AP为圆心，传播半径r和δ之和以及之差为半径做圆
环，对K个参考点进行约束，圆环和先前生成的K个参考点重合的参考点即为精细定位需要
用到的参考点。在精细定位时，利用上一步骤生成的参考点计算其与测试点的欧式距离，根
据欧式距离对参考点坐标赋予权重，最终实现精确位置估计。

[0113] 3.基于信号传播模型约束的KNN算法示意图。

[0114] 利用信号信号传播模型在KNN算法的基础上进行进一步约束，获取更为精确的参考点，缩减了参考点的数量，极大节省了算法时长，提高了定位效率。如图所示，根据实验数
据构建信号信号传播模型：

[0115] PL(d)(dB)＝PL(d0)+10nlg(d/d0)+X0

[0116] 在传统的KNN算法基础上使用信号传播模型对参考点进行进一步缩减：

[0117] (1)选取测试点接收到的最强信号AP；

[0118] (2)利用模型计算测试点到此AP距离r；

[0119] (3)设定δ用于加强系统的容错性，以AP为圆心，所得距离r与δ之差及和为半径做圆；

[0120] (4)利用(3)产生的圆环对KNN得到的K个参考点进行约束和缩减，确定最优参考点。

[0121] 如图所示，圆环约束将进一步缩减参考点数目。圆环内参考点即可作为最优参考点。将最优参考点和测试点依次进行欧式距离度量，根据度量结果赋予不同权重，最终得到
精确位置估计。

[0122]

[0123] 在第i个参考点第u个AP产生的信号强度值；

[0124] 测试点在第u个AP收集到的信号强度值。

[0125]

[0126]

[0127] wi：对第i个参考点位置坐标。