本发明涉及一种基于wifi指纹和改进knn算法的住宅楼宇室内定位方法，包含步骤指纹采集点规划设置、指纹采集、设备定位扫描上报、指纹匹配计算、空间位置计算，该方法与原始KNN算法比较，采用多级聚合排序法，解决了传统定位算法受到空间干扰，定位不准的问题，本发明对室内复杂建筑结构和开放区域信号干扰具有更高的容忍度，定位准确度高。
1.一种基于wifi指纹和改进knn算法的住宅楼宇室内定位方法，其特征在于，包含以下步骤：
S1：指纹采集点规划设置，对住宅小区各楼栋做指纹采集点位规划设置，每一楼层按照面积均匀设置指纹采集点位；
S2：指纹采集，对每一个指纹采集点位进行环境Wifi指纹采集，并标记该指纹所属位置信息，上传云端服务器，并存储在位置指纹数据库；
S3：设备定位扫描上报，设备终端或者支持wifi扫描的智能手机定时扫描采集环境中的wifi信号,并生成定位指纹数据，上报云端定位计算系统，由定位计算系统做定位计算处理；
S4：指纹匹配计算，云端定位计算系统收到当前定位指纹数据，从位置指纹数据库提取本小区所有位置指纹信息，并筛选出能够匹配到当前定位指纹的位置指纹条目，并基于多级knn算法得到匹配位置指纹列表；
S5：空间位置计算，基于S4得到的匹配位置指纹列表，计算当前设备的位置；
S4.1: 位置指纹匹配选择，从位置指纹数据库提取本小区所有位置指纹信息，对于每一条位置指纹信息，如果其包含当前定位指纹的任意一条mac地址，则将其放入候选位置指纹列表(P1,P2…Pn)；
S4.2： 楼栋选择，第K栋楼值取Kb，从候选位置指纹列表(P1,P2…Pn)中选择前Kb个指纹点，并对该Kb个指纹点按照归属的楼栋位置做聚合(P11, P12..P1i), (P21,P22… P2j)… (Pm1,Pm2.. Pmx)，分别计算每一楼栋匹配的点位数量(B1, B2…Bx)， 选取匹配点位数量最大的楼栋作为候选楼栋 Bmax，候选匹配位置指纹列表为(Pb1, Pb2… Pbi)；
S4.3：单元选择，如果候选楼栋Bmax单元数多于1，则需要进行单元选择过程；否则将候选位置指纹列表(Pb1, Pb2… Pbi)标记为(Pu1, Pu2… Pui)并跳过此步骤，转到步骤S4.4；
将(Pb1, Pb2… Pbi)按照单元进行聚合，分别计算每一个单元的指纹点匹配数量(U1, U2.. Ui)，选择数量最大的单元作为候选单元Umax，候选匹配列表为(Pu1, Pu2… Pui)；
S4.4：楼层选择，如果候选单元Umax 楼层数多于1，则需要进行楼层选择过程；否则将(Pu1, Pu2… Pui)标记为Pf1, Pf2.. Pfi)并跳过此步骤，转到步骤S4.5；
将(Pu1, Pu2… Pui)按照楼层进行聚合，分别计算每一个单元的指纹点匹配数量(U1, U2.. Ui)，选择数量最大的楼层作为候选楼层Fmax, 候选匹配列表为(Pf1, Pf2.. Pfi)；
S4.5：指纹点位选择，指纹点位K值取Kf，如果候选楼层Fmax的匹配指纹点数多于Kf, 则需要进行位置指纹点位选择过程；否则将候选匹配列表为(Pf1, Pf2.. Pfi)标记为（P1，P2..Pi)跳过此步骤，转到步骤S5。
2.根据权利要求1所述的一种基于wifi指纹和改进knn算法的住宅楼宇室内定位方法，其特征在于：所述步骤S2中指纹采集包括使用手机APP，所述位置信息包括所属楼栋号、单元号、楼层号和层内位置号。
3.根据权利要求1所述的一种基于wifi指纹和改进knn算法的住宅楼宇室内定位方法，其特征在于：所述步骤S5中，如果候选位置指纹点列表(P1, P2… Pkf)列表长度Kf = 0，则定位失败，设备处于无wifi信号区域或未采集指纹的区域，如果Kf = 1, 则空间位置为该指纹点位置，如果Kf > 1, 则采用三角定位或最小二乘法估算设备在该楼层的平面位置。
4.根据权利要求1所述的一种基于wifi指纹和改进knn算法的住宅楼宇室内定位方法，其特征在于：所述位置指纹数据库用于根据匹配的指纹库查询定位的位置信息。
5.根据权利要求3所述的一种基于wifi指纹和改进knn算法的住宅楼宇室内定位方法，其特征在于：所述指纹点位K值取Kf， 将候选楼层指纹候选匹配列表(Pf1, Pf2.. Pfi)按照欧式距离从小到大排序，选择前Kf个点位作为候选指纹列表(P1, P2… Pkf)。
一种基于wifi指纹和改进knn算法的住宅楼宇室内定位方法
技术领域
[0001] 本发明涉及定位的技术领域，具体涉及一种基于wifi指纹和改进knn算法的住宅楼宇室内定位方法。
背景技术
[0002] 随着数字经济的发展，室内外定位技术做为一种基础技术能力，再各行各业有着越来越广泛的需求和应用。室外定位，gps已经基于gps衍生的高精度定位技术已经非常成熟，是事实上标准。而室内定位技术，由于信号的衰减和多径效用，gps无法正常工作。近年来，业界尝试了多种技术手段，有蓝牙信标定位、超宽带uwb定位、地磁定位、wifi定位等，以期在室内定位领域实现一种低成本高精度低技术方案。这些技术各有各的特点，但由于室内环境的多样性和不稳定性，始终没有一种技术能完全满足业界的需求。
[0003] 基于到达时间TOA，到达时间差TDOA，或到达角度AOA这类算法，由于对设备要求较高，无法有效利用广泛部署的wifi网络。而基于信号衰减的几何方位计算法受到室内结构的影响，无法建立广泛适用的距离衰减模型，可用的场景有限。位置指纹法因其不依赖特定设备，模型计算简单高效，容错性高等特点，使得该算法成为wifi室内定位最有可能广泛采用的算法。然而当前wifi指纹定位算法，在结构较为简单的室内空间，比如开阔平坦的环境下定位较为理想。如果直接用在住宅楼宇内的定位，由于住宅空间单层面积较小，结构较为复杂，上下楼层高度低，楼间距较短等原因， 存在诸多问题，主要有以下三点：（1）多楼层存在垂直空间的相互干扰， 垂直空间定位稍有偏差就会引起楼层定位不准确，对整体定位效果影响较大；（2）由于楼间距通常有限，并且楼宇内存在开放和半开放区域，从而导致楼栋间干扰很大，会出现楼栋或单元级的定位错误，于实际位置出现巨大偏差；（3）如果top k的指纹点出现非同一楼层，或非同一楼栋，经过几何位置计算后有可能定位在非室内的不合理区域。
发明内容
[0004] 为了解决现有基于KNN的wifi指纹算法在住宅楼宇内的定位偏差较大的问题，本发明提供了一种基于wifi指纹和改进knn算法的住宅楼宇室内定位方法，对室内复杂建筑结构和开放区域信号干扰具有更高的容忍度和定位结果的准确度。
[0005] 本发明提供基于wifi指纹和改进knn算法的住宅楼宇室内定位方法，包含以下步骤：
[0006] S1：指纹采集点规划设置：对住宅小区各楼栋做指纹采集点位规划设置，每一楼层按照面积均匀设置指纹采集点位；
[0007] S2：指纹采集：对每一个指纹采集点位进行环境Wifi指纹采集，并标记该指纹所属位置信息，上传云端服务器，并存储在位置指纹数据库；
[0008] S3：设备定位扫描上报：设备终端或者支持wifi扫描的智能移动终端定时扫描采集环境中的wifi信号，并生成定位指纹数据，上报云端定位计算系统，由云端定位计算系统做定位计算处理；
[0009] S4：指纹匹配计算：云端定位计算系统收到当前定位指纹数据，从位置指纹数据库提取本小区所有位置指纹信息，并筛选出能够匹配到当前定位指纹的位置指纹条目，并基于多级knn算法得到匹配位置指纹列表；
[0010] S5：空间位置计算：基于S4得到的匹配位置指纹列表，计算当前设备的位置。
[0011] 作为优选，所述步骤S2中指纹采集包括使用手机APP，所述位置信息包括所属楼栋号、单元号、楼层号和层内位置号。
[0012] 作为优选，所述步骤S4包括以下子步骤：
[0013] S4.1：位置指纹匹配选择，从位置指纹数据库提取本小区所有位置指纹信息，对于每一条位置指纹信息，如果其包含当前定位指纹的任意一条mac地址，则将其放入候选位置指纹列表(P1,P2…Pn) ，n为自然数；
[0014] S4.2：楼栋选择，楼栋K值取Kb，从候选位置指纹列表(P1,P2…Pn)中选择前Kb个指纹点，并对该Kb个指纹点按照归属的楼栋做聚合(P11,P12…P1i)， (P21,P22…P2j) …(Pm1,Pm2…Pmx)，m、i、j、x均为自然数，分别计算每一楼栋匹配的点位数量(B1, B2…Bx)， 选取匹配点位数量最大的楼栋作为候选楼栋 Bmax，候选匹配位置指纹列表为(Pb1, Pb2…Pbi)；
[0015] S4.3：单元选择，如果候选楼栋Bmax单元数多于1，则需要进行单元选择过程；否则将候选位置指纹列表(Pb1, Pb2…Pbi)标记为(Pu1, Pu2…Pui)并跳过此步骤，转到步骤S4.4；
[0016] 将(Pb1, Pb2…Pbi)按照单元进行聚合，分别计算每一个单元的指纹点匹配数量(U1, U2…Ui)，选择数量最大的单元作为候选单元Umax，候选匹配列表为(Pu1, Pu2…Pui)；
[0017] S4.4：楼层选择，如果候选单元Umax 楼层数多于1，则需要进行楼层选择过程；否则将(Pu1, Pu2…Pui)标记为(Pf1, Pf2…Pfi)并跳过此步骤，转到步骤S4.5；
[0018] 将(Pu1, Pu2…Pui)按照楼层进行聚合，分别计算每一个单元的指纹点匹配数量(U1, U2…Ui)，选择数量最大的楼层作为候选楼层Fmax，候选匹配列表为(Pf1, Pf2…Pfi)；
[0019] S4.5：指纹点位选择，指纹点位K值取Kf，如果候选楼层Fmax的匹配指纹点数多于Kf， 则需要进行位置指纹点位选择过程；否则将候选匹配列表为(Pf1, Pf2…Pfi)标记为（P1，P2…Pi)跳过此步骤，转到步骤S5。
[0020] 作为优选，所述步骤S5中，如果候选位置指纹点列表(P1, P2…Pkf)列表长度Kf = 0，则定位失败，设备处于无wifi信号区域或未采集指纹的区域；如果Kf = 1，则空间位置为该指纹点位置，如果Kf > 1，则采用三角定位或最小二乘法估算设备在该楼层的平面位置。
[0021] 作为优选，所述位置指纹数据库用于根据匹配的指纹库查询定位的位置信息。
[0022] 作为优选，所述指纹点位K值取Kf，将候选楼层指纹候选匹配列表(Pf1, Pf2…Pfi)按照欧式距离从小到大排序，选择前Kf个点位作为候选指纹列表(P1, P2…Pkf)。
[0023] 本发明的方法与原始KNN算法比较，采用多级聚合排序法，解决了传统定位算法受到空间干扰，定位不准的问题，本发明对室内复杂建筑结构和开放区域信号干扰具有更高的容忍度，定位准确度高。
附图说明
[0024] 图1为本发明的步骤流程图。
具体实施方式
[0025] 下面结合实施例对本发明的实施方案进行详细描述。本领域技术人员将会理解，以下实施例仅为本发明的优选实施例，以便于更好的理解本发明，因而不应视为限定本发明的范围。对于本领域的技术人员来说，本发明可以有各种变化和更改，凡在本发明的精神和原则之内，所做的任何修改，均应包含在本发明的保护范围之内。以下实施例中的实验方法，如无特殊说明，均为常规方法，所用的实验材料，如无特殊说明，均为常规生化试剂厂商处购买。
[0026] 如图1所示，一种基于wifi指纹和改进knn算法的住宅楼宇室内定位方法，包含以下步骤：
[0027] S1：指纹采集点规划设置：对住宅小区各楼栋做指纹采集点位规划设置，每一楼层按照面积均匀设置指纹采集点位；
[0028] S2：指纹采集：对每一个指纹采集点位进行环境Wifi指纹采集，并标记该指纹所属位置信息，上传云端服务器，并存储在位置指纹数据库；
[0029] S3：设备定位扫描上报：设备终端或者支持wifi扫描的智能移动终端定时扫描采集环境中的wifi信号，并生成定位指纹数据，上报云端定位计算系统，由云端定位计算系统做定位计算处理；
[0030] S4：指纹匹配计算：云端定位计算系统收到当前定位指纹数据，从位置指纹数据库提取本小区所有位置指纹信息，并筛选出能够匹配到当前定位指纹的位置指纹条目，并基于多级knn算法得到匹配位置指纹列表；
[0031] S5：空间位置计算：基于S4得到的匹配位置指纹列表，计算当前设备的位置。
[0032] 所述步骤S4包括以下子步骤：
[0033] S4.1：位置指纹匹配选择，从位置指纹数据库提取本小区所有位置指纹信息，对于每一条位置指纹信息，如果其包含当前定位指纹的任意一条mac地址，则将其放入候选位置指纹列表(P1,P2…Pn) ，n为自然数；
[0034] S4.2：楼栋选择，楼栋K值取Kb，从候选位置指纹列表(P1,P2…Pn)中选择前Kb个指纹点，并对该Kb个指纹点按照归属的楼栋做聚合(P11,P12…P1i)，(P21,P22…P2j) …(Pm1,Pm2…Pmx)，m、i、j、x均为自然数，分别计算每一楼栋匹配的点位数量(B1, B2…Bx)， 选取匹配点位数量最大的楼栋作为候选楼栋 Bmax，候选匹配位置指纹列表为(Pb1, Pb2…Pbi)；
[0035] S4.3：单元选择，如果候选楼栋Bmax单元数多于1，则需要进行单元选择过程；否则将候选位置指纹列表(Pb1, Pb2…Pbi)标记为(Pu1, Pu2…Pui)并跳过此步骤，转到步骤S4.4；
[0036] 将(Pb1, Pb2…Pbi)按照单元进行聚合，分别计算每一个单元的指纹点匹配数量(U1, U2…Ui)，选择数量最大的单元作为候选单元Umax，候选匹配列表为(Pu1, Pu2…Pui)；
[0037] S4.4：楼层选择，如果候选单元Umax 楼层数多于1，则需要进行楼层选择过程；否则将(Pu1, Pu2…Pui)标记为(Pf1, Pf2…Pfi)并跳过此步骤，转到步骤S4.5；
[0038] 将(Pu1, Pu2…Pui)按照楼层进行聚合，分别计算每一个单元的指纹点匹配数量(U1, U2…Ui)，选择数量最大的楼层作为候选楼层Fmax，候选匹配列表为(Pf1, Pf2…Pfi)；
[0039] S4.5：指纹点位选择，指纹点位K值取Kf，如果候选楼层Fmax的匹配指纹点数多于Kf，则需要进行位置指纹点位选择过程；否则将候选匹配列表为(Pf1, Pf2…Pfi)标记为（P1，P2…Pi)跳过此步骤，转到步骤S5。
[0040] 指纹点位K值取Kf，将候选楼层指纹候选匹配列表(Pf1, Pf2…Pfi)按照欧式距离从小到大排序，选择前Kf个点位作为候选指纹列表(P1, P2…Pkf)。
[0041] 所述步骤S5中，如果候选位置指纹点列表(P1, P2…Pkf)列表长度Kf = 0，则定位失败，设备处于无wifi信号区域或未采集指纹的区域；如果Kf = 1，则空间位置为该指纹点位置，如果Kf > 1，则采用三角定位或最小二乘法估算设备在该楼层的平面位置。
[0042] 实施例1
[0043] 在某个物业项目中有两栋楼1栋和2栋，每栋楼有两个单元一单元和二单元，每单元有10层。
[0044] 在S1阶段，我们规划每层均匀分布4个指纹采集点位，并在S2阶段在每一个指纹采集点位，采集wifi信号并上传到服务器并存储与指纹库，指纹库数据如下所示：
[0045]
[0046] 在S3阶段，定位设备上报用来定位的三条指纹信息：
[0047] p1(mac=1a:bb:cc:aa:bb:01,rssi=‑52)，p2(mac=1a:bb:cc:aa:bb:02,rssi=‑62)，p3(Mac=1a:bb:cc:aa:bb:03,rssi=‑58，p4(Mac=1a:bb:cc:aa:bb:04,rssi=‑68)，云端服务器收到该指纹信息后进行定位运算S4。
[0048] 在S4.1阶段，通过与指纹库匹配，我们选出所有匹配到对指纹条目作为后选条目，其中在本例中指纹id号1‑7皆为候选条目。
[0049] 在S4.2楼栋选择阶段，我们算出1栋指纹库mac地址字段与设备上报指纹mac地址相同的条目有指纹id1，id2，id3，id4，id5，id7，匹配数量为6。2栋指纹库mac地址字段与设备上报指纹mac地址相同的条目有指纹id6，匹配数量是1。从1栋和2栋中选取匹配数量最大的楼栋，则1栋为候选楼栋，2栋淘汰。
[0050] 在S4.3单元选择阶段，我们算出1栋1单元指纹库mac地址字段与设备上报指纹mac地址相同的条目有指纹id1，id2，id3，id4，id7，匹配数量为5。1栋2单元指纹库mac地址字段与设备上报指纹mac地址相同的条目有指纹id5，匹配数量是1。从1栋1单元和1栋2单元中选取匹配数量最大的单元，则1栋1单元为候选单元，1栋2单元淘汰。
[0051] 在S4.4楼层选择阶段，我们算出1栋1单元1层指纹库mac地址字段与设备上报指纹mac地址相同的条目有指纹id1，id2，id3，id7，匹配数量为4。1栋1单元2层指纹库mac地址字段与设备上报指纹mac地址相同的条目有指纹id4，匹配数量是1。从1栋1单元1层和1栋1单元2层中选取匹配数量最大的单元，则1栋1单元1层为候选楼层，1栋1单元2层淘汰。
[0052] 在S4.5定位点选择阶段，K值选取：由于在S4.4阶段1栋1单元1层匹配的指纹数量是4，K值取3。1栋1单元1层共有4个匹配指纹点位：id1，id2，id3和id7。需要通过欧式距离选取距离最短的前K个点位，公式如下：
[0053]
[0054] 其中N为该指纹点包含的不同mac地址数量，r为指纹点每个mac测得的rssi，p为设备上报点相同mac的rssi。在本例中对于指纹点id1（N=1，r=‑50，p=‑52）算得D1=2；id2（N=1，r=‑60，p=‑62）算得D2=2；id3（N=1，r=‑55，p=‑58）算得D3=3；id7（N=1，r=‑62，p‑68）算得D7=6。D1，D2，D3，D7排序后选择距离最短的前K=3个点为备选指纹点，这里选择结果为id1，id2和id3。
[0055] 在S5阶段，用1栋1单元1层的三个点位id1，id2，id3，采用三角定位对方法计算本次定位对最终物理空间位置。技术步骤为：
[0056] 计算上报点与各指纹库点位的距离。计算公式为d=10^((abs(RSSI)‑A)/(10*n))[0057] 其中，d‑计算所得距离，RSSI‑接收信号强度（负值），A‑发射端和接收端相隔1米时的信号强度我们取35，n‑环境衰减因子这里取2。
[0058] 三角定位计算。公式如下：
[0059]
[0060] 其中d1、d2、d3分别是三个点位id1，id2，id3在上一步计算的距离，x1、x2、x3分别为id1，id2，id3横坐标，y1、y2、y3分别为id1，id2，id3的纵坐标，求解方程得
[0061] 到(x0，y0 ) 即为设备上报点的坐标。
[0062] 以上所述仅为本发明的优选实施例而已，并不用于限制本发明，对于本领域的技术人员来说，本发明可以有各种更改和变化。凡在本发明的精神和原则之内，所做的任何修改、等同替换、改进等，均应包含在本发明的保护范围内。
