基于转移概率热点映射的室内WLAN增广流形对齐定位方法

摘要

本发明公开了一种基于转移概率热点映射的室内WLAN增广流形对齐定位方法，对定位目标区域进行划分以得到物理环境图，同时通过对用户运动行为的观测，得到所划分物理子区域间的转移分布；在定位目标区域内采集RSS序列并利用相关性测序方法得到信号图，同时统计所有RSS序列在信号图中的转移分布；利用所得转移分布得到概率转移矩阵，以建立信号图到物理环境图的热点映射关系；对于新采集的RSS，根据热点映射关系判断其所属的物理子区域；根据所属物理子区域的标记点指纹及定位目标区域中的位置坐标集，利用增广流形对齐方法进行定位。本发明无需在离线阶段采集每个参考点处来自不同AP的RSS且不依赖于运动传感器，同时具有较高的定位精度。

说明书

技术领域

本发明属于无线电通信技术，具体涉及一种基于转移概率热点映射的室内WLAN增广 流形对齐定位方法。

背景技术

随着WLAN在室内环境中的大规模部署，基于WLAN的室内定位技术受到了越来越 多的关注，在室内WLAN定位系统中，位置指纹定位方法的精度较高且不需要添加额外的 设备，从而得到了较为广泛的应用。基于位置指纹的定位方法主要分为两个阶段：离线阶 段和在线阶段。在离线阶段，通过在目标区域内选择合适的参考点，并在每个参考点处测 量来自不同接入点AP(AccessPoint)的信号强度值，建立位置指纹数据库。在在线阶段， 利用相应的定位方法对终端实时测量得到的信号值与指纹数据库中的信号数据进行匹配， 实现对终端位置的估计。

由于位置指纹定位方法的离线阶段需要在定位目标区域内每个参考点处采集来自不同 AP的信号强度值，因此在定位系统建设前期需要投入大量的人力与时间开销，以完成位置 指纹数据库的构建，特别是在参考点数目较多的情况下，离线阶段指纹采集的工作量会大 大增加。同时，基于即时映射与定位SLAM(SimultaneousLocalizationAndMapping)技术 的定位方法需要额外运动传感器的辅助，终端成本较高。

因此，有必要开发一种基于转移概率热点映射的室内WLAN增广流形对齐定位方法。

发明内容

本发明的目的是提供一种基于转移概率热点映射的室内WLAN增广流形对齐定位方 法，它无需在离线阶段采集每个参考点处来自不同AP的RSS且不依赖于运动传感器，同 时具有较高的定位精度。

本发明所述的基于转移概率热点映射的室内WLAN增广流形对齐定位方法，包括以下 步骤：

A、对定位目标区域进行划分以得到物理环境图，同时通过对用户运动行为的观测， 得到所划分物理子区域间的转移分布；

B、在定位目标区域内采集RSS序列并利用相关性测序方法得到信号图，同时统计所 有RSS序列在信号图中的转移分布；

C、利用所得转移分布得到概率转移矩阵，以建立信号图到物理环境图的热点映射关系；

D、对于新采集的RSS，根据热点映射关系判断其所属的物理子区域；

E、根据所属物理子区域的标记点指纹及定位目标区域中的位置坐标集，利用增广流形 对齐方法进行定位。

所述步骤A包括：

步骤一、将定位目标区域划分为a个物理子区域，同时在定位目标区域中均匀标记位 置坐标点，记位置坐标点集合为{(h_p1,v_p2)}(1≤p≤V)，其中，h_p1为第p个位置坐标的横坐 标，v_p2为第p个位置坐标的纵坐标，V为位置坐标的数目；

步骤二、根据各物理子区域的邻接关系，将定位目标区域表示为各物理子区域连通的 物理环境图；

步骤三、对定位目标区域中用户的运动行为进行观测，得到用户在各个物理子区域间 的运动分布T_kl(1≤k,l≤a)，其中，T_kl表示用户从第k个物理子区域运动到第l个物理子区域 的统计次数；

所述步骤B包括：

步骤四、在定位目标区域中采集j条RSS序列其中， L_i为第i条RSS序列的长度，即包含RSS样本的 个数，RSS_im＝(rss_im1,rss_im2,...,rss_ims)(1≤m≤L_i)，s为AP个数，rss_ims"(1≤s"≤s)为第i条RSS 序列内第m个RSS样本中来自第s"个AP的RSS值；

步骤五、在第n(1≤n≤a)个物理子区域A_n中均匀标记l_n个标记点，标记点的位置坐标 包含于位置坐标点集{(h_p1,v_p2)}(1≤p≤V)中，并在每个标记点处采集N个RSS样本，将N 个RSS样本的均值作为该标记点的指纹，记每个区域内标记点的指纹集合为 {RSS_nq＝(rss_nq1,rss_nq2,...,rss_nqs)}(1≤q≤l_n)，其中，RSS_nq表示第n个物理子区域中第q个标 记点的指纹；

步骤六、建立相关性测序函数，对集合中两两不同的RSS序列 进行相关性测序，确定不同RSS序列间的相关位置对集合{L_rt}(1≤r≠t≤j)，其中，L_rt为 第r条和第t条RSS序列间的相关位置对，L_rt＝{(R_ru,R_rv,R_tx,R_ty)}(1≤u,v≤L_r,1≤x,y≤L_t) 表示第r条RSS序列中第u个和第v个RSS样本与第t条RSS序列中第x个和第y个RSS样 本之间具有相关性，L_r和L_t分别为第r条和第t条RSS序列的长度；

步骤七、对于{L_rt}中相关位置对(R_ru,R_rv,R_tx,R_ty)所对应的RSS相关类 {RSS_ru,RSS_rv,RSS_tx,RSS_ty}，若存在相关位置对 (R_r'u',R_r'v',R_t'x',R_t'y')(1≤r'≠t'≤j,1≤u',v'≤L_r',1≤x',y'≤L_t')所对应的RSS相关类 {RSS_r'u',RSS_r'v',RSS_t'x',RSS_t'y'}中包含相同的RSS样本，即 其中，L_r'和L_t'分别为第 r'条和第t'条RSS序列的长度，则将RSS相关类{RSS_ru,RSS_rv,RSS_tx,RSS_ty}和 {RSS_r'u',RSS_r'v',RSS_t'x',RSS_t'y'}进行合并，直至所有RSS相关类间不存在非空交集，记 C_w(1≤w≤z)表示最终得到的第w个RSS相关类，z为最终得到的RSS相关类的数目；

步骤八、在RSS序列中，将每一段连续采集且不包含于任意RSS相关类的RSS 样本{RSS_ic'}(1≤c'≤L_i)构成一个RSS类，记表示中第e个RSS类，g为 RSS类的数目；

步骤九、将所对应的RSS相关类和RSS类统称为类 在类集合中，两个类存在连接关系当且仅当 某条RSS序列内存在两个连续的RSS样本分别包含于这两个类中；

步骤十、将类集合中的每一个类作为节点，类之间的连接关系 作为边，构建信号图；

步骤十一、统计类集合中不同类之间的转移次数，其中，存在 一次类到类的转移当且仅当某条RSS序列内两个连续的RSS 样本先后分别包含于和中，记为类 到类的转移次数；

所述步骤C包括：

步骤十二、根据所述步骤三所得T_kl与所述步骤十一所得分别构建概率转移矩阵P_A与P_S，并按热度从大到小准则，分别得到物理环境图和信号图中各个节点的热度排序，同 时，将信号图中的每个节点映射到物理环境图中热度排序相同的节点；

所述步骤D包括：

步骤十三、对于新采集的RSS样本(rss₁,rss₂,...,rss_s)，计算其与类集合 中所有类的类心的欧氏距离，其中，类的类心 定义为类包含的个RSS样本的均值，得到与其具有最小欧氏 距离的类心，并将新采集的RSS样本归属到该类心所对应的类，同时，根据信号图到物理 环境图的热点映射关系，确定目标所在的物理子区域；

所述步骤E包括：

步骤十四、根据所属物理子区域中的标记点指纹 {RSS_nq＝(rss_nq1,rss_nq2,...,rss_nqs)}(1≤q≤l_n)和定位目标区域的位置坐标集 {(h_p1,v_p2)}(1≤p≤V)，利用增广流形对齐方法，估计目标位置。

所述步骤十二包括：

步骤12a、令用户在tz≥0时刻位于物理子区域A_n的概率为P_tz(A_n)，定义如下递推式：

$P_{tz+1}\left(A_n\right)={\Sigma }_{\eta =1}^a{P}_{tz}\left(A_{\eta }\right)\left(P_{A_{\eta }\to A_n}/M_{A_{\eta }}\right);$

其中，T_ηl为用户从第η个物理子区域运动到第l个物理子区 域的统计次数，区域指示函数表示如下：

步骤12b、构建概率转移关系：

P_tz+1＝P_AP_tz；

其中，P_tz＝[P_tz(1),P_tz(2),...,P_tz(a)]^T，且 P_A＝θ(M+ec^T/a)+(1-θ)ee^T/a；

其中，0≤θ≤1，M为a×a的矩阵且对于M中第k行第l列的元素 c＝[in₁,in₂,...,in_a]^T且

步骤12c、由于所以P＝lim_tz→∞P_tz＝[P(1),P(2),...,P(a)]^T，于是得到各个 物理子区域的热度P(n)，其中，当P(n)值越大，物理子区域A_n的热度也就越大；

步骤12d、同理，令用户采集信号样本(rss₁,rss₂,...,rss_s)在tz时刻与的类心的 欧式距离最小的概率为定义如下递推式：

${P^{\prime }}_{tz+1}\left({\mathrm{Cluster}}_{c_3}\right)={\Sigma }_{c_4=1}^{z+g}{P^{\prime }}_{tz}\left({\mathrm{Cluster}}_{c_4}\right)({P^{\prime }}_{c_4\to c_3}/{M^{\prime }}_{{\mathrm{Cluster}}_{c_4}});$

其中，${M^{\prime }}_{{\mathrm{Cluster}}_{c_4}}={\Sigma }_{c_5=1}^{z+g}{T}_{c_4{c}_5}^R(1\le c_4\le z+g),$类指示函数表示如下：

步骤12e、构建概率转移关系：

P'_tz+1＝P_sP'_tz；

其中，P'_tz＝[P'_tz(1),P'_tz(2),...,P'_tz(z+g)]^T，且 P_s＝θ(M'+e'c'^T/(z+g))+(1-θ)e'e'^T/(z+g)；

其中，M'为(z+g)×(z+g)的矩阵且对于M'中第c₃行第c₄列的元素 ${M^{\prime }}_{c_3{c}_4}={P^{\prime }}_{{\mathrm{Cluster}}_{c_4}\to {\mathrm{Cluster}}_{c_3}}/{M^{\prime }}_{{\mathrm{Cluster}}_{c_4}},$c'＝[in'₁,in'₂,...,in'_(z+g)]^T且

步骤12f、由于所以P'＝lim_tz→∞P'_tz＝[P'(1),P'(2),...,P'(z+g)]^T，于是得 到信号图中各个类的热度P'(c₃)，其中，当P'(c₃)值越大，类c₃的热度也就越大；

步骤12g、分别将P和P'中的元素从大到小排序，记排序后的P和P'分别为P_Rank和 P'_Rank，其中，P_Rank＝[P_Rank(1),P_Rank(2),...,P_Rank(a)]^T， P'_Rank＝[P'_Rank(1),P'_Rank(2),...,P'_Rank(z+g)]^T，且分别满足P_Rank(1)≥P_Rank(2)≥...≥P_Rank(a)， P'_Rank(1)≥P'_Rank(2)≥...≥P'_Rank(z+g)，将P'_Rank(c₃)映射到与其具有相同热度排序的 P_Rank(n)，即类c₃在信号图中的排序等于子区域n在物理环境图中的排序。

所述步骤十四包括：

步骤14a、将位置坐标集{(h_p1,v_p2)}(1≤p≤V)中元素的顺序进行调整，使得标记点指 纹{RSS_nq＝(rss_nq1,rss_nq2,...,rss_nqs)}(1≤q≤l_n)所对应的位置坐标依次为 记调整后的位置坐标集为{(h'_p1,v'_p2)}(1≤p≤V)；

步骤14b、将用户新采集RSS样本(rss₁,rss₂,...,rss_s)与 {RSS_nq＝(rss_nq1,rss_nq2,...,rss_nqs)}(1≤q≤l_n)构成新的指纹集 {RSS'_nQ＝(rss'_nQ1,rss'_nQ2,...,rss'_nQs)}(1≤Q≤l_n+1)，其中，RSS'_nQ＝RSS_nQ(1≤Q≤l_n)， ${{\mathrm{RSS}}^{\prime }}_{n(l_n+1)}=({\mathrm{rss}}_1,{\mathrm{rss}}_2,...,{\mathrm{rss}}_s);$

步骤14c、对位置坐标集{(h'_p1,v'_p2)}(1≤p≤V)进行增广处理，使得集合元素的维度由 2维增加至s维，得到增广位置坐标集，增广后的位置坐标集为

步骤14d、构建增广位置坐标集所对应的V×V权重矩阵W，其中，W中元素 $W_{v_1{v}_2}=\exp (-{\Sigma }_{v_3=1}^s{\left({h^{\prime \prime }}_{v_1{v}_3}-{h^{\prime \prime }}_{v_2{v}_3}\right)}^2)(1\le v_1\ne v_2\le V)$且$W_{v_1{v}_2}=0(1\le v_1=v_2\le V);$

步骤14e、构建指纹集{RSS'_nQ}(1≤Q≤l_n+1)所对应的(l_n+1)×(l_n+1)权重矩阵W'，其 中，W'中元素${W^{\prime }}_{v_4{v}_5}=\exp (-{\Sigma }_{v_6=1}^s{\left({{\mathrm{rss}}^{\prime }}_{{\mathrm{nv}}_4{v}_6}-{{\mathrm{rss}}^{\prime }}_{{\mathrm{nv}}_5{v}_6}\right)}^2)(1\le v_4\ne v_5\le l_n+1)$且 ${W^{\prime }}_{v_4{v}_5}=0(1\le v_4=v_5\le l_n+1);$

步骤14f、计算关于W的对角矩阵D，其中，D中元素且 $D_{v_1{v}_2}={\Sigma }_{v_3=1}^V{W}_{v_1{v}_3}(1\le v_1=v_2\le V);$

步骤14g、计算关于W'的对角矩阵D'，其中，D'中元素且 ${D^{\prime }}_{v_4{v}_5}={\Sigma }_{v_6=1}^{l_n+1}{W^{\prime }}_{v_4{v}_6}(1\le v_4=v_5\le l_n+1);$

步骤14h、得到矩阵L＝D-W和L'＝D'-W'；

步骤14i、将矩阵L进行分块，具体形式为：

$L=\left(\begin{array}{cc}{B}_{l_n{l}_n}& B_{l_n(V-l_n)}\\ B_{(V-l_n)l_n}& B_{(V-l_n)(V-l_n)}\end{array}\right);$

其中，

$B_{l_n{l}_n}=\left(\begin{array}{cccc}{L}_{11}& L_{12}& \mathrm{...}& L_{1l_n}\\ L_{21}& L_{22}& \mathrm{...}& L_{2l_n}\\ \mathrm{...}& \mathrm{...}& \mathrm{...}& \mathrm{...}\\ L_{l_{n}1}& L_{l_{n}2}& \mathrm{...}& L_{l_n{l}_n}\end{array}\right),B_{l_n\left(V-l_n\right)}=\left(\begin{array}{cccc}{L}_{1\left(l_n+1\right)}& L_{1\left(l_n+2\right)}& \mathrm{...}& L_{1V}\\ L_{2\left(l_n+1\right)}& L_{2\left(l_n+2\right)}& \mathrm{...}& L_{2V}\\ \mathrm{...}& \mathrm{...}& \mathrm{...}& \mathrm{...}\\ L_{l_n\left(l_n+1\right)}& L_{l_n\left(l_n+2\right)}& \mathrm{...}& L_{l_{n}V}\end{array}\right),$

$B_{\left(V-l_n\right)l_n}=\left(\begin{array}{cccc}{L}_{\left(l_n+1\right)1}& L_{\left(l_n+1\right)2}& \mathrm{...}& L_{\left(l_n+1\right)l_n}\\ L_{\left(l_n+2\right)1}& L_{\left(l_n+2\right)2}& \mathrm{...}& L_{\left(l_n+2\right)l_n}\\ \mathrm{...}& \mathrm{...}& \mathrm{...}& \mathrm{...}\\ L_{V1}& L_{V2}& \mathrm{...}& L_{{\mathrm{Vl}}_n}\end{array}\right),B_{\left(V-l_n\right)\left(V-l_n\right)}=\left(\begin{array}{cccc}{L}_{\left(l_n+1\right)\left(l_n+1\right)}& L_{\left(l_n+1\right)\left(l_n+2\right)}& \mathrm{...}& L_{\left(l_n+1\right)V}\\ L_{\left(l_n+2\right)\left(l_n+1\right)}& L_{\left(l_n+2\right)\left(l_n+2\right)}& \mathrm{...}& L_{\left(l_n+2\right)V}\\ \mathrm{...}& \mathrm{...}& \mathrm{...}& \mathrm{...}\\ L_{V\left(l_n+1\right)}& L_{V\left(l_n+2\right)}& \mathrm{...}& L_{VV}\end{array}\right),$且 $L_{v_1{v}_2}=D_{v_1{v}_2}-W_{v_1{v}_2};$

步骤14j、将矩阵L'进行分块，具体形式为：

$L^{\prime }=\left(\begin{array}{cc}{B^{\prime }}_{l_n{l}_n}& {B^{\prime }}_{l_{n}1}\\ {B^{\prime }}_{1l_n}& {B^{\prime }}_{11}\end{array}\right);$

其中，

${B^{\prime }}_{l_n{l}_n}=\left(\begin{array}{cccc}{L^{\prime }}_{11}& {L^{\prime }}_{12}& \mathrm{...}& {L^{\prime }}_{1l_n}\\ {L^{\prime }}_{21}& {L^{\prime }}_{22}& \mathrm{...}& {L^{\prime }}_{2l_n}\\ \mathrm{...}& \mathrm{...}& \mathrm{...}& \mathrm{...}\\ {L^{\prime }}_{l_{n}1}& {L^{\prime }}_{l_{n}2}& \mathrm{...}& {L^{\prime }}_{l_n{l}_n}\end{array}\right),{B^{\prime }}_{l_{n}1}=\left(\begin{array}{c}{L^{\prime }}_{1\left(l_n+1\right)}\\ {L^{\prime }}_{2\left(l_n+1\right)}\\ \mathrm{...}\\ {L^{\prime }}_{l_n\left(l_n+1\right)}\end{array}\right);$

${B^{\prime }}_{1l_n}=\left(\begin{array}{cccc}{L^{\prime }}_{(l_n+1)1}& {L^{\prime }}_{(l_n+1)2}& \mathrm{...}& {L^{\prime }}_{(l_n+1)l_n}\end{array}\right),{B^{\prime }}_{11}=\left({L^{\prime }}_{(l_n+1)(l_n+1)}\right),$且${L^{\prime }}_{v_4{v}_5}={D^{\prime }}_{v_4{v}_5}-{W^{\prime }}_{v_4{v}_5};$

步骤14k、构造新矩阵L”，其形式为：

$L^{\prime \prime }=\left(\begin{array}{ccc}{\mathrm{\lambda B}}_{l_n{l}_n}+{\lambda }^{\prime }{B^{\prime }}_{l_n{l}_n}& {\mathrm{\lambda B}}_{l_n(V-l_n)}& {\lambda }^{\prime }{B^{\prime }}_{l_{n}1}\\ {\mathrm{\lambda B}}_{(V-l_n)l_n}& {\mathrm{\lambda B}}_{(V-l_n)(V-l_n)}& 0_{(V-l_n)1}\\ {\lambda }^{\prime }{B^{\prime }}_{1l_n}& 0_{1(V-l_n)}& {\lambda }^{\prime }{B^{\prime }}_{11}\end{array}\right);$

其中，λ＝(l_n+1)/(V+l_n+1)，λ'＝V/(V+l_n+1)，及分别为1×(V-l_n)和 (V-l_n)×1的零矩阵；

步骤14l、计算L”的di个非零特征值λ”₁,λ”₂,...,λ”_di>0，满足 L”x_U＝λ”_Ux_U(1≤U≤di)，其中，x_U为特征值λ”_U对应的(V+1)×1的矢量；

步骤14m、构建降维后矩阵x'＝[x₁,x₂,...,x_di]，记x'_Z(1≤Z≤V+1)为x'的第Z行；

步骤14n、计算x'_V+1与的欧氏距离 其中，x'_Zdi'为x'中第Z行第di'列元素，令x' 的前V行中与x'_V+1欧式距离最小的mi个行矢量依次位于第m₁,m₂,...,m_mi行，则将增广位置 坐标集{(h'_p1,v'_p2)}(1≤p≤V)中元素的均值作为用户 的估计位置(est,est')，即$est=\frac{{\Sigma }_{m^{\prime }=m_1}^{m_{mi}}{h^{\prime }}_{m^{\prime }1}}{mi},{\mathrm{est}}^{\prime }=\frac{{\Sigma }_{m^{\prime }=m_1}^{m_{mi}}{v^{\prime }}_{m^{\prime }2}}{mi}.$

本发明具有以下优点：本发明无需在离线阶段对大量参考点处的信号强度进行采集， 也无需运动传感器的辅助，仅需在定位目标区域内采集若干条RSS序列及记录少量标记点 指纹，从而大大降低了系统所需的人力及时间开销，同时还具有较高的定位精度。

附图说明

图1为本发明的流程图；

图2为本发明的仿真环境；

图3(a)到图3(l)为两两不同RSS序列的相关性测序结果；

图4为经相关性测序后所形成的信号图；

图5为信号图中16个类到物理环境图中3个物理子区域的热点映射关系图；

图6为在仿真环境下关于新采集RSS样本的正确区域判断概率结果图；

图7为本发明中定位精度随标记点数目变化的曲线图；

图8为本发明与KNN(KNearestNeighbor)方法的定位精度对比图。

具体实施方式

下面结合附图对本发明作进一步说明。

本发明所述的基于转移概率热点映射的室内WLAN增广流形对齐定位方法，A、对定 位目标区域进行划分以得到物理环境图，同时通过对用户运动行为的观测，得到所划分物 理子区域间的转移分布；B、在定位目标区域内采集RSS(ReceivedSignalStrength)序列并 利用相关性测序方法得到信号图，同时统计所有RSS序列在信号图中的转移分布；C、利 用所得转移分布得到概率转移矩阵，以建立信号图到物理环境图的热点映射关系；D、对于 新采集的RSS，根据热点映射关系判断其所属的物理子区域；E、根据所属物理子区域的标 记点指纹及定位目标区域中的位置坐标集，利用增广流形对齐方法进行定位。

如图1所示，本发明所述的基于转移概率热点映射的室内WLAN增广流形对齐定位方 法，具体包括以下步骤：

步骤一、本发明的仿真环境中假定信号传播特性服从Keenan-Motley多墙传播模型， 即接收端接收到的信号强度值P^R的计算表达式如下：

P^R＝P^R(d₀)-10β'log(d^P)-N_wall·L_wall-N_floor·L_floor-χ公式一；

其中，d₀为参考距离；β'表示路径损耗指数，其反映了信号强度损耗与信号传播距离的关 系；d^P为信号接收端与AP之间的距离；N_wall和N_floor分别表示信号在从AP到接收端的整 个传播路径中，信号所穿过的墙和地板的个数；L_wall和L_floor分别表示墙壁和地板的损耗系 数，在本发明选择的仿真环境中，由于定位目标区域在同一楼层，于是不考虑地板损耗， 即令L_wall＝3、L_floor＝0；χ为服从高斯分布的随机变量。将目标区域划分为a个 物理子区域，同时在目标区域中均匀标记位置坐标点，记目标区域中的所有位置坐标点集 为{(h_p1,v_p2)}(1≤p≤V)，h_p1为第p个位置坐标的横坐标，v_p2为第p个位置坐标的纵坐标， V为位置坐标的数目。图2为本发明的仿真环境；共放置3个AP且划分了3个物理子区域， 图2中左下角的黑点即为坐标原点；仿真中β'＝2.2，d₀＝1，a＝3， V＝184，位置坐标点间的间隔为1米。

步骤二、根据各物理子区域的邻接关系，将定位目标区域表示为各物理子区域连通的 物理环境图。

步骤三、对定位目标区域中用户的运动行为进行观测，得到用户在各个物理子区域间 的运动分布T_kl(1≤k,l≤a)，其中，T_kl表示用户从第k个物理子区域运动到第l个物理子区域 的统计次数；仿真中，T₂₁＝10，T₃₁＝7，T₁₂＝14，T₁₃＝4。

步骤四、在定位目标区域中采集j条RSS序列其中， L_i为第i条RSS序列的长度，即包含RSS样本的 个数，RSS_im＝(rss_im1,rss_im2,...,rss_ims)(1≤m≤L_i)，s为AP个数，rss_ims"(1≤s"≤s)为第i条RSS 序列内第m个RSS样本中来自第s"个AP的RSS值，仿真中j＝35，s＝3。

步骤五、在第n(1≤n≤a)个物理子区域A_n中均匀标记l_n个标记点，标记点的位置坐标 包含于位置坐标点集{(h_p1,v_p2)}(1≤p≤V)中，并在每个标记点处采集N个RSS样本，将N 个RSS样本的均值作为该标记点的指纹，记每个区域内标记点的指纹集合为 {RSS_nq＝(rss_nq1,rss_nq2,...,rss_nqs)}(1≤q≤l_n)，其中，RSS_nq表示第n个物理子区域中第q个标 记点的指纹且其中，为第n个物理子区域中的第q个标 记点上第T'次采集的来自第s'个AP的信号强度；仿真中，在全标记点的情况下，l₁＝126， l₂＝28，l₃＝30。

步骤六、建立相关性测序函数，对集合中两两不同的RSS序列 进行相关性测序，确定不同RSS序列间的相关位置对集合{L_rt}(1≤r≠t≤j)，其中，L_rt为 第r条和第t条RSS序列间的相关位置对，L_rt＝{(R_ru,R_rv,R_tx,R_ty)}(1≤u,v≤L_r,1≤x,y≤L_t) 表示第r条RSS序列中第u个和第v个RSS样本与第t条RSS序列中第x个和第y个RSS样 本之间具有相关性，L_r和L_t分别为第r条和第t条RSS序列的长度；具体步骤为：

步骤6a、计算与中的RSS间的得分，形成得分矩阵H_rt，其具体形式为：

$H_{rt}\left(i^{\prime },j^{\prime }\right)=max\left(\begin{array}{c}0\\ H_{rt}\left(i^{\prime }-1,j^{\prime }-1\right)+s^{\prime }({\mathrm{RSS}}_{{\mathrm{ri}}^{\prime }},{\mathrm{RSS}}_{{\mathrm{tj}}^{\prime }})\\ max\{H_{rt}\left(i^{\prime }-k^{\prime },j^{\prime }\right)+W_{k^{\prime }}\}\\ max\{H_{rt}\left(i^{\prime },j^{\prime }-l^{\prime }\right)+W_{l^{\prime }}\}\end{array}\right)\begin{array}{c}1\le i^{\prime }\le L_r,\\ 1\le j^{\prime }\le L_t\end{array}$公式二；

$\left(\begin{array}{c}{H}_{rt}(0,j^{\prime })=0,1\le j^{\prime }\le L_t\\ H_{rt}(i^{\prime },0)=0,1\le i^{\prime }\le L_r\\ H_{rt}(0,0)=0\end{array}\right)$公式三；

其中，max{·}为取最大值操作，且

$s^{\prime }\left({\mathrm{RSS}}_{{\mathrm{ri}}^{\prime }},{\mathrm{RSS}}_{{\mathrm{tj}}^{\prime }}\right)=\left(\begin{array}{c}\alpha >0\left({\mathrm{RSS}}_{{\mathrm{ri}}^{\prime }}={\mathrm{RSS}}_{{\mathrm{rj}}^{\prime }}\right)\\ \beta <0\left({\mathrm{RSS}}_{{\mathrm{ri}}^{\prime }}\ne {\mathrm{RSS}}_{{\mathrm{rj}}^{\prime }}\right)\end{array}\right),$公式四；

W_k'＝-(α-β)k'

其中，仿真中图3(a)到图3(l)为两两不同RSS序列的相关性测 序结果(共595幅相关性测序结果图)，两个RSS样本的相关性越大，对应图中像素点的灰 度值也越大，即像素颜色越白，图中“RSSIDs”表示RSS样本标号。

步骤6b、确定H_rt中的最大元素H_rt(i',j')。

步骤6c、将H_rt(i',j')在H_rt中的位置(i',j')保存在位置矩阵L_o中，同时确定下一得分值 H_rt(c”,d”)＝max{H_rt(i',j'-1),H_rt(i'-1,j'),H_rt(i'-1,j'-1)}，并令i'＝c”且j'＝d”。

步骤6d、重复步骤6c直到下一得分值为0；令L_o中记录了t”个位置，则L_o(r”)(1≤r”≤t”) 表示L_o中第r”个位置，L_o(r”)(1)表示第r”个位置所对应的横坐标值，L_o(r”)(2)表示第r”个位 置所对应的纵坐标值。

步骤6e、令r”＝t”。

步骤6f、比较L_o(r”)与L_o(r”-1)的位置，若L_o(r”-1)(1)＝L_o(r”)(1)+1且 L_o(r”-1)(2)＝L_o(r”)(2)+1，则将L_o(r”)及L_o(r”-1)作为一组位置对 (L_o(r”)(1),L_o(r”-1)(1),L_o(r”)(2),L_o(r”-1)(2))，并且保存在关于与的相关位置对集合 L_rt中，且记(L_o(r”)(1),L_o(r”-1)(1),L_o(r”)(2),L_o(r”-1)(2))＝(R_ru,R_rv,R_tx,R_ty)，表示第r条RSS 序列中的第u个RSS(即是第L_o(r”)(1)个RSS)，和第v个RSS(即是第L_o(r”-1)(1)个RSS) 与第t条RSS序列中的第x个RSS(即是第L_o(r”)(2)个RSS)，和第y个RSS(即是第 L_o(r”-1)(2)个RSS)具有相关性。

步骤6g、令r”＝r”-1。

步骤6h、重复步骤6f和步骤6g，直到r”＝2。

步骤6i、对于{L_rt}中相关位置对(R_ru,R_rv,R_tx,R_ty)所对应的RSS相关类 {RSS_ru,RSS_rv,RSS_tx,RSS_ty}，若存在相关位置对 (R_r'u',R_r'v',R_t'x',R_t'y')(1≤r'≠t'≤j,1≤u',v'≤L_r',1≤x',y'≤L_t')所对应的RSS相关类 {RSS_r'u',RSS_r'v',RSS_t'x',RSS_t'y'}中包含相同的RSS样本，即 其中，L_r'和L_t'分别为第 r'条和第t'条RSS序列的长度，则将RSS相关类{RSS_ru,RSS_rv,RSS_tx,RSS_ty}和 {RSS_r'u',RSS_r'v',RSS_t'x',RSS_t'y'}进行合并，直至所有RSS相关类间不存在非空交集，记 C_w(1≤w≤z)表示最终得到的第w个RSS相关类，z为最终得到的RSS相关类的数目。

步骤八、在RSS序列中，将每一段连续采集且不包含于任意RSS相关类的RSS 样本{RSS_ic'}(1≤c'≤L_i)构成一个RSS类，记表示中第e个RSS类，g为 RSS类的数目。

步骤九、将所对应的RSS相关类和RSS类统称为类 在类集合中，两个类存在连接关系当且仅当 某条RSS序列内存在两个连续的RSS样本分别包含于这两个类中。

步骤十、将类集合中的每一个类作为节点，类之间的连接关系 作为边，构建信号图。图4为经相关性测序后所形成的信号图，从图4中能看出该信号图 包含16个类。

步骤十一、统计类集合中不同类之间的转移次数，其中，存在 一次类到类的转移当且仅当某条RSS序列内两个连续的RSS 样本先后分别包含于和中，记为类 到类的转移次数。

步骤十二、根据所述步骤三所得T_kl与所述步骤十一所得分别构建概率转移矩阵P_A与P_S，并按热度从大到小准则，分别得到物理环境图和信号图中各个节点的热度排序，同 时，将信号图中的每个节点映射到物理环境图中热度排序相同的节点；具体步骤为：

步骤12a、令用户在tz≥0时刻位于物理子区域A_n的概率为P_tz(A_n)，定义如下递推式：

$P_{tz+1}\left(A_n\right)={\Sigma }_{\eta =1}^a{P}_{tz}\left(A_{\eta }\right)\left(P_{A_{\eta }\to A_n}/M_{A_{\eta }}\right)$公式五；

其中，T_ηl为用户从第η个物理子区域运动到第l个物理子区域的 统计次数，区域指示函数表示如下：

公式六。

步骤12b、构建概率转移关系：

P_tz+1＝P_AP_tz公式七；

其中，P_tz＝[P_tz(1),P_tz(2),...,P_tz(a)]^T，且

P_A＝θ(M+ec^T/a)+(1-θ)ee^T/a公式八；

其中，0≤θ≤1，M为a×a的矩阵且对于M中第k行第l列的元素 c＝[in₁,in₂,...,in_a]^T且

公式九；

仿真中θ＝0.8。

步骤12c、由于所以P＝lim_tz→∞P_tz＝[P(1),P(2),...,P(a)]^T，于是得到各个 物理子区域的热度P(n)，其中，当P(n)值越大，物理子区域A_n的热度也就越大。

步骤12d、同理，令用户采集信号样本(rss₁,rss₂,...,rss_s)在tz时刻与的类心的 欧式距离最小的概率为定义如下递推式：

${P^{\prime }}_{tz+1}\left({\mathrm{Cluster}}_{c_3}\right)={\Sigma }_{c_4=1}^{z+g}{P^{\prime }}_{tz}\left({\mathrm{Cluster}}_{c_4}\right)({P^{\prime }}_{c_4\to c_3}/{M^{\prime }}_{{\mathrm{Cluster}}_{c_4}})$公式十；

其中，${M^{\prime }}_{{\mathrm{Cluster}}_{c_4}}={\Sigma }_{c_5=1}^{z+g}{T}_{c_4{c}_5}^R(1\le c_4\le z+g),$类指示函数表示如下：

公式十一。

步骤12e、构建概率转移关系：

P'_tz+1＝P_sP'_tz公式十二；

其中，P'_tz＝[P'_tz(1),P'_tz(2),...,P'_tz(z+g)]^T，且

P_s＝θ(M'+e'c'^T/(z+g))+(1-θ)e'e'^T/(z+g)公式十三；

其中，M'为(z+g)×(z+g)的矩阵且对于M'中第c₃行第c₄列的元素 ${M^{\prime }}_{c_3{c}_4}={P^{\prime }}_{{\mathrm{Cluster}}_{c_4}\to {\mathrm{Cluster}}_{c_3}}/{M^{\prime }}_{{\mathrm{Cluster}}_{c_4}},$c'＝[in'₁,in'₂,...,in'_(z+g)]^T且

公式十四。

步骤12f、由于所以P'＝lim_tz→∞P'_tz＝[P'(1),P'(2),...,P'(z+g)]^T，于是得 到信号图中各个类的热度P'(c₃)，其中，当P'(c₃)值越大，类c₃的热度也就越大。

步骤12g、分别将P和P'中的元素从大到小排序，记排序后的P和P'分别为P_Rank和 P'_Rank，其中，P_Rank＝[P_Rank(1),P_Rank(2),...,P_Rank(a)]^T， P'_Rank＝[P'_Rank(1),P'_Rank(2),...,P'_Rank(z+g)]^T，且分别满足P_Rank(1)≥P_Rank(2)≥...≥P_Rank(a)， P'_Rank(1)≥P'_Rank(2)≥...≥P'_Rank(z+g)，将P'_Rank(c₃)映射到与其具有相同热度排序的 P_Rank(n)，即类c₃在信号图中的排序等于子区域n在物理环境图中的排序。图5为信号图中 16个类到物理环境图中3个物理子区域的热点映射关系，从图5中能看出信号图中类1映 射到物理子区域1，信号图中类2、3、4、5、7、9、11、12、14、15和16映射到物理子区 域2，信号图中类6、8、10和13映射到物理子区域3。

步骤十三、对于新采集的RSS样本(rss₁,rss₂,...,rss_s)，计算其与类集合 中所有类的类心的欧氏距离，其中，类的类心 定义为类包含的个RSS样本的均值，满足${\mathrm{rss}}_{s^{\prime }}^{c_3}=\frac{{\Sigma }_{T^{\prime \prime }=1}^{n_{c_3}}{\mathrm{rss}}_{{\mathrm{ims}}^{\prime }}^{T^{\prime \prime }}}{n_{c_3}},$其中为中第T"个来自第s'个AP的接收信号强度，得到与其具有最小欧氏距 离的类心，并将新采集的RSS样本归属到该类心所对应的类，同时，根据信号图到物理环 境图的热点映射关系，确定目标所在的物理子区域。图6为在仿真环境下关于新采集RSS 样本的正确区域判断概率结果图，从图6中能看出，物理子区域1中83.3％的新采集RSS 样本区域判断正确，物理子区域2和3中所有的新采集RSS样本区域判断正确，由此可知， 本发明方法具有较高的区域判断精度。

步骤十四、根据所属物理子区域中的标记点指纹 {RSS_nq＝(rss_nq1,rss_nq2,...,rss_nqs)}(1≤q≤l_n)和定位目标区域的位置坐标集 {(h_p1,v_p2)}(1≤p≤V)，利用增广流形对齐方法，估计目标位置；具体包括：

步骤14a、将位置坐标集{(h_p1,v_p2)}(1≤p≤V)中元素的顺序进行调整，使得标记点指 纹{RSS_nq＝(rss_nq1,rss_nq2,...,rss_nqs)}(1≤q≤l_n)所对应的位置坐标依次为 记调整后的位置坐标集为{(h'_p1,v'_p2)}(1≤p≤V)。

步骤14b、将用户新采集RSS样本(rss₁,rss₂,...,rss_s)与 {RSS_nq＝(rss_nq1,rss_nq2,...,rss_nqs)}(1≤q≤l_n)构成新的指纹集 {RSS'_nQ＝(rss'_nQ1,rss'_nQ2,...,rss'_nQs)}(1≤Q≤l_n+1)，其中，RSS'_nQ＝RSS_nQ(1≤Q≤l_n)， ${{\mathrm{RSS}}^{\prime }}_{n(l_n+1)}=({\mathrm{rss}}_1,{\mathrm{rss}}_2,...,{\mathrm{rss}}_s).$

步骤14c、对位置坐标集{(h'_p1,v'_p2)}(1≤p≤V)进行增广处理，使得集合元素的维度由 2维增加至s维，得到增广位置坐标集，增广后的位置坐标集为

步骤14d、构建增广位置坐标集所对应的V×V权重矩阵W，其中，W中元素 $W_{v_1{v}_2}=\exp (-{\Sigma }_{v_3=1}^s{\left({h^{\prime \prime }}_{v_1{v}_3}-{h^{\prime \prime }}_{v_2{v}_3}\right)}^2)(1\le v_1\ne v_2\le V)$且$W_{v_1{v}_2}=0(1\le v_1=v_2\le V).$

步骤14e、构建指纹集{RSS'_nQ}(1≤Q≤l_n+1)所对应的(l_n+1)×(l_n+1)权重矩阵W'，其 中，W'中元素${W^{\prime }}_{v_4{v}_5}=\exp (-{\Sigma }_{v_6=1}^s{\left({{\mathrm{rss}}^{\prime }}_{{\mathrm{nv}}_4{v}_6}-{{\mathrm{rss}}^{\prime }}_{{\mathrm{nv}}_5{v}_6}\right)}^2)(1\le v_4\ne v_5\le l_n+1)$且 ${W^{\prime }}_{v_4{v}_5}=0(1\le v_4=v_5\le l_n+1).$

步骤14f、计算关于W的对角矩阵D，其中，D中元素且 $D_{v_1{v}_2}={\Sigma }_{v_3=1}^V{W}_{v_1{v}_3}(1\le v_1=v_2\le V).$

步骤14g、计算关于W'的对角矩阵D'，其中，D'中元素且 ${D^{\prime }}_{v_4{v}_5}={\Sigma }_{v_6=1}^{l_n+1}{W^{\prime }}_{v_4{v}_6}(1\le v_4=v_5\le l_n+1).$

步骤14h、得到矩阵L＝D-W和L'＝D'-W'。

步骤14i、将矩阵L进行分块，具体形式为：

$L=\left(\begin{array}{cc}{B}_{l_n{l}_n}& B_{l_n(V-l_n)}\\ B_{(V-l_n)l_n}& B_{(V-l_n)(V-l_n)}\end{array}\right)$公式十五；

其中，

$B_{l_n{l}_n}=\left(\begin{array}{cccc}{L}_{11}& L_{12}& \mathrm{...}& L_{1l_n}\\ L_{21}& L_{22}& \mathrm{...}& L_{2l_n}\\ \mathrm{...}& \mathrm{...}& \mathrm{...}& \mathrm{...}\\ L_{l_{n}1}& L_{l_{n}2}& \mathrm{...}& L_{l_n{l}_n}\end{array}\right),B_{l_n\left(V-l_n\right)}=\left(\begin{array}{cccc}{L}_{1\left(l_n+1\right)}& L_{1\left(l_n+2\right)}& \mathrm{...}& L_{1V}\\ L_{2\left(l_n+1\right)}& L_{2\left(l_n+2\right)}& \mathrm{...}& L_{2V}\\ \mathrm{...}& \mathrm{...}& \mathrm{...}& \mathrm{...}\\ L_{l_n\left(l_n+1\right)}& L_{l_n\left(l_n+2\right)}& \mathrm{...}& L_{l_{n}V}\end{array}\right),$

$B_{\left(V-l_n\right)l_n}=\left(\begin{array}{cccc}{L}_{\left(l_n+1\right)1}& L_{\left(l_n+1\right)2}& \mathrm{...}& L_{\left(l_n+1\right)l_n}\\ L_{\left(l_n+2\right)1}& L_{\left(l_n+2\right)2}& \mathrm{...}& L_{\left(l_n+2\right)l_n}\\ \mathrm{...}& \mathrm{...}& \mathrm{...}& \mathrm{...}\\ L_{V1}& L_{V2}& \mathrm{...}& L_{{\mathrm{Vl}}_n}\end{array}\right),B_{\left(V-l_n\right)\left(V-l_n\right)}=\left(\begin{array}{cccc}{L}_{\left(l_n+1\right)\left(l_n+1\right)}& L_{\left(l_n+1\right)\left(l_n+2\right)}& \mathrm{...}& L_{\left(l_n+1\right)V}\\ L_{\left(l_n+2\right)\left(l_n+1\right)}& L_{\left(l_n+2\right)\left(l_n+2\right)}& \mathrm{...}& L_{\left(l_n+2\right)V}\\ \mathrm{...}& \mathrm{...}& \mathrm{...}& \mathrm{...}\\ L_{V\left(l_n+1\right)}& L_{V\left(l_n+2\right)}& \mathrm{...}& L_{VV}\end{array}\right),$且$L_{v_1{v}_2}=D_{v_1{v}_2}-W_{v_1{v}_2}.$

步骤14j、将矩阵L'进行分块，具体形式为：

$L^{\prime }=\left(\begin{array}{cc}{B^{\prime }}_{l_n{l}_n}& {B^{\prime }}_{l_{n}1}\\ {B^{\prime }}_{1l_n}& {B^{\prime }}_{11}\end{array}\right)$公式十六；

其中，

${B^{\prime }}_{l_n{l}_n}=\left(\begin{array}{cccc}{L^{\prime }}_{11}& {L^{\prime }}_{12}& \mathrm{...}& {L^{\prime }}_{1l_n}\\ {L^{\prime }}_{21}& {L^{\prime }}_{22}& \mathrm{...}& {L^{\prime }}_{2l_n}\\ \mathrm{...}& \mathrm{...}& \mathrm{...}& \mathrm{...}\\ {L^{\prime }}_{l_{n}1}& {L^{\prime }}_{l_{n}2}& \mathrm{...}& {L^{\prime }}_{l_n{l}_n}\end{array}\right),{B^{\prime }}_{l_{n}1}=\left(\begin{array}{c}{L^{\prime }}_{1\left(l_n+1\right)}\\ {L^{\prime }}_{2\left(l_n+1\right)}\\ \mathrm{...}\\ {L^{\prime }}_{l_n\left(l_n+1\right)}\end{array}\right),$

${B^{\prime }}_{1l_n}=\left(\begin{array}{cccc}{L^{\prime }}_{(l_n+1)1}& {L^{\prime }}_{(l_n+1)2}& \mathrm{...}& {L^{\prime }}_{(l_n+1)l_n}\end{array}\right),{B^{\prime }}_{11}=\left({L^{\prime }}_{(l_n+1)(l_n+1)}\right),$且${L^{\prime }}_{v_4{v}_5}={D^{\prime }}_{v_4{v}_5}-{W^{\prime }}_{v_4{v}_5}.$

步骤14k、构造新矩阵L”，其形式为：

$L^{\prime \prime }=\left(\begin{array}{ccc}{\mathrm{\lambda B}}_{l_n{l}_n}+{\lambda }^{\prime }{B^{\prime }}_{l_n{l}_n}& {\mathrm{\lambda B}}_{l_n(V-l_n)}& {\lambda }^{\prime }{B^{\prime }}_{l_{n}1}\\ {\mathrm{\lambda B}}_{(V-l_n)l_n}& {\mathrm{\lambda B}}_{(V-l_n)(V-l_n)}& 0_{(V-l_n)1}\\ {\lambda }^{\prime }{B^{\prime }}_{1l_n}& 0_{1(V-l_n)}& {\lambda }^{\prime }{B^{\prime }}_{11}\end{array}\right)$公式十七；

其中，λ＝(l_n+1)/(V+l_n+1)，λ'＝V/(V+l_n+1)，及分别为1×(V-l_n)和 (V-l_n)×1的零矩阵。

步骤14l、计算L”的di个非零特征值λ”₁,λ”₂,...,λ”_di>0，满足：

L”x_U＝λ”_Ux_U(1≤U≤di)公式十八；

其中，x_U为特征值λ”_U对应的(V+1)×1的矢量。

步骤14m、构建降维后矩阵x'＝[x₁,x₂,...,x_di]，记x'_Z(1≤Z≤V+1)为x'的第Z行。

步骤14n、计算x'_V+1与的欧氏距离 其中，x'_Zdi'为x'中第Z行第di'列元素，令x' 的前V行中与x'_V+1欧式距离最小的mi个行矢量依次位于第m₁,m₂,...,m_mi行，则将增广位置 坐标集{(h'_p1,v'_p2)}(1≤p≤V)中元素的均值作为用户 的估计位置(est,est')，即图7为定位精度随标记点数目 变化的曲线图，从图7中能看出本发明的定位精度随标记点数目的增加而提高，且当标记 点比例大于70％时，本发明的定位精度优于KNN方法，这说明本发明能够在较少指纹采集 开销的条件下达到较高的定位精度。

此外，将本发明所述方法与KNN方法进行了定位精度比较，KNN方法步骤如下：

步骤一、在位置坐标集{(h_p1,v_p2)}(1≤p≤V)中的每一个位置处采集col_p个RSS样本， 并col_p个RSS样本均值作为该位置处的指纹，记为指纹集，其中，为第p个位置所对应的指纹；

步骤二、对于新采集的RSS样本(rss₁,rss₂,...,rss_s)，计算其与指纹集中每个指纹的欧氏距离其中，E'_p为新采集RSS样本 (rss₁,rss₂,...,rss_s)与第p个位置处指纹间的欧式距离，rss_F'和rss_pF'分别为新采集RSS样本 (rss₁,rss₂,...,rss_s)与第p个指纹中来自第F'个AP的RSS值，s为AP数目；

步骤三、记指纹集中与新采集RSS样本(rss₁,rss₂,...,rss_s)具有最小 欧氏距离的mi'个指纹标号为m'₁,m'₂,...,m'_mi'，则得到用户的估计位置(es,es')，其中， $es=\frac{{\Sigma }_{M^{\prime }={m^{\prime }}_1}^{{m^{\prime }}_{{\mathrm{mi}}^{\prime }}}{h}_{M^{\prime }1}}{{\mathrm{mi}}^{\prime }},{\mathrm{es}}^{\prime }=\frac{{\Sigma }_{M^{\prime }={m^{\prime }}_1}^{{m^{\prime }}_{{\mathrm{mi}}^{\prime }}}{h}_{M^{\prime }2}}{{\mathrm{mi}}^{\prime }}.$仿真中，令mi'＝3。

图8为本发明与KNN(KNearestNeighbor)方法的定位精度对比，从图8中能看出， 本发明具有较高的定位精度，相比于KNN方法，误差4米内的置信概率提高约20％，图中 “100％标记点”表示KNN方法中标定的参考点均作为本发明所述方法的标记点。