一种基于非现场勘测的无线室内定位方法

摘要

本发明涉及一种基于非现场勘测的无线室内定位方法，属于无线定位技术领域。本方法首先利用智能手机自动采集指纹数据，形成数据集；基于数据集中无线信号的二阶差分值，利用K平均算法生成虚拟房间；根据传感器读数提取用户移动路径，从而获得虚拟房间的连通关系，构建逻辑平面图；将逻辑平面图映射到实际平面图上，得到指纹-位置关系；匹配用户提交的位置请求所在的虚拟房间，并检索指纹-位置关系数据库，判断用户所在位置。本发明方法无需对定位区域进行人工的现场勘测，无需无线接入点的位置、功率等信息，充分利用人的移动信息，实现房间级别的逻辑定位，给出用户当前位置，既提高了定位的精度与实时性，又节约了使用者的时间。

主权项

1.一种基于非现场勘测的无线室内定位方法，其特征在于该方法包括以下各步骤：（1）通过手机采集无线网络的信号以及手机中的加速度传感器和方向传感器的读数，组成一个指纹数据集：D＝{F，S}，其中F为采集的无线信号，F＝[f₁，f₂，f₃，......，f_n]，f_i表示无线网络中第i个无线接入点的信号强度值，S为手机中的加速度传感器和方向传感器的读数，i＝1,2,3，......，n，n为无线网络中无线接入点的个数；（2）设指纹数据集中的任意两条无线信号分别为：F＝[f₁，f₂，f₃，......，f_n]和F’＝[f’₁，f’2，f’3，...，f’n]，两个无线信号之间的区分度用无线信号强度的二阶差分值表示为：$\phi (F,F^{\prime })=\sqrt{{\Sigma }_{i=1}^n{(\omega \left(f_i\right)-\omega \left({f^{\prime }}_i\right))}^2}$$\omega \left(f_i\right)=\underset{j=1}{\overset{n}{\Sigma }}I(f_i-f_j>0)(f_i-f_j)$其中，I为指示型函数；（3）根据步骤（2）中的二阶差分值，采用K平均聚类方法将指纹数据集中的无线信号划分为N类，即N个虚拟房间从K平均聚类结果中得到每个虚拟房间R的平均指纹F[R]和指纹阈值ξ，其中平均指纹F[R]为虚拟房间R所包含的所有无线信号指纹的平均值，指纹阈值ξ为该虚拟房间R所包含的所有无线信号中与平均指纹F[R]的最大的二阶差分值，（4）构建一个逻辑平面图G＝(V，E)，使逻辑平面图G＝(V，E)中的每一个顶点R₁∈V代表一个虚拟房间，每一条边e＝(R₁，R₂)∈E表示虚拟房间R₁与R₂相连通，构建过程包括如下步骤：（4-1）根据步骤（1）中的连续采集的传感器读数A，形成手机在移动过程中的连续移动轨迹，移动轨迹上的无线信号强度依次记为与该连续无线信号强度相对应的步骤（3）的多个相连续的虚拟房间记为（4-2）根据步骤(4-1)中的连续虚拟房间序列将每个虚拟房间简化为一个点，在任意两个相邻的虚拟房间R_i、R_i+1之间连接出一条边；（4-3）遍历步骤（1）的指纹数据集中的所有连续采集的传感器读数，重复步骤（4-1）和（4-2），得到逻辑平面图G＝(V，E)；（5）将上述逻辑平面图映射到需无线室内定位区域的实际平面图，得到逻辑平面图中每一个顶点与实际平面图的对应关系，即指纹-位置关系数据库，包括如下步骤：（5-1）将需无线室内定位区域的实际平面图简化为一个无向图G′＝(V′，E′)，其中每个顶点A₁∈V′代表需无线室内定位区域的实际平面图中的一个功能区域，每条边e＝(A₁，A₂)∈E′表示两个功能区域A₁和A₂相连通；（5-2）根据介数中心性，建立上述逻辑平面图G＝(V，E)和实际平面图G′＝(V′，E′)中居于中心的顶点的相互映射关系，逻辑平面图G＝(V，E)中顶点R的介数中心性C_b(R)为：$C_b\left(R\right)=\underset{s\ne t\ne R\in V}{\Sigma }\frac{{\sigma }_{\mathrm{st}}\left(R\right)}{{\sigma }_{\mathrm{st}}}$其中，σ_st为逻辑平面图G＝(V，E)中顶点s到顶点t的最短路径数，σ_st(R)为穿过顶点R的顶点s到顶点t的最短路径数，按介数中心性从大到小排列得到逻辑平面图G＝(V，E)的中心顶点序列{r₁，r₂，......，r_k}；实际平面图G′＝(V′，E′)中顶点A的介数中心性C_b(A)为：$C_b\left(A\right)=\underset{s\ne t\ne A\in V^{\prime }}{\Sigma }\frac{{\sigma }_{\mathrm{uv}}\left(A\right)}{{\sigma }_{\mathrm{uv}}}$其中，σ_uv为实际平面图G′＝(V′，E′)中顶点u到顶点v的最短路径数，σ_uv(A)为穿过顶点A的顶点u到顶点v的最短路径数，按介数中心性从大到小排列得到实际平面图G′＝(V′，E′)的中心顶点序列{a₁，a₂，......，a_k}；将上述中心顶点序列{r₁，r₂，......，r_k}与中心顶点序列{a₁，a₂，......，a_k}按照序号一一对应，得到逻辑平面图G＝(V，E)和实际平面图G′＝(V′，E′)的中心顶点的映射关系；（5-3）设逻辑平面图G＝(V，E)中非中心顶点v到所有其他顶点的最短路径长度的和为该顶点v的权值，即：w(v)＝∑_{u∈V，u≠v}d(v，u)其中，d(v，u)为顶点v到u的最短路径长度，重复本步骤，得到逻辑平面图G＝(V，E)中所有非中心顶点的权值；实际平面图G′＝(V′，E′)中非中心顶点v′到所有其他顶点的最短路径长度的和为该顶点v′的权值，即：w(v′)＝∑_{u′∈V，u′≠v′}d(v′，u′)其中，d(v′，u′)为顶点v′到u′的最短路径长度，重复本步骤，得到实际平面图G′＝(V′，E′)中所有非中心顶点的权值；根据上述得到的所有非中心顶点的权值，利用KM算法求解带权最小二分图匹配模型，使得所有匹配顶点之间的权值之差最小，即使得W＝∑_v∈V|w(v)-w(v′)|最小，其中v′为v的映射，得到逻辑平面图和实际平面图中的非中心顶点的映射关系；（5-4）根据步骤（5-2）和（5-3）中得到的映射关系，实施以下步骤加以纠正：设逻辑平面图G＝(V，E)中顶点p被映射到实际平面图G′＝(V′，E′)中的顶点p′，定义顶点v的邻居集合N_G(p)为逻辑平面图G＝(V，E)中与顶点p直接相连的顶点集合，定义顶点p′的邻居集合N_G′(p′)为实际平面图G′＝(V′，E′)中与顶点p′直接相连的顶点集合，设N′_G(p)为与顶点p的邻居集合N_G(p)中的所有节点相映射的实际平面图G′＝(V′，E′)中的节点集合，若N′_G(p)与N_G′(p′)中的相同节点数少于N_G(p)所包含节点数的一半，则判定p到p′的映射不正确；遍历实际平面图G′＝(V′，E′)除p′以外的所有顶点，寻找新顶点q，使得N′_G(p)与q的邻居集合N_G′(q)的相同顶点数最多，并确定顶点q与顶点p的映射关系；（5-5）重复步骤（5-4），得到逻辑平面图G＝(V，E)与实际平面图G′＝(V′，E′)之间的映射关系；（6）根据步骤（5）得到的指纹-位置关系数据库，实现对用户的定位，包括以下步骤：（6-1）根据用户提交的无线信号为F，若存在满足以下条件的虚拟房间R：与$\phi (F,F[R\left]\right)<\xi$其中为步骤（2）中定义的二阶差分值，R_i为任意一个虚拟房间，为步骤（3）中的虚拟房间集合，F[R]为虚拟房间R的平均信号强度，ξ为步骤（2）中的与虚拟房间R对应的信号强度阈值，则判定用户所在虚拟房间为R；（6-2）根据上述判定的用户所在虚拟房间R，检索步骤（5）中指纹位置数据库，得到与上述虚拟房间R所对应的实际平面图中的功能区域，即为用户所在的位置。