一种基于区域分割和曲面拟合的室内定位方法

摘要

本发明公开了一种基于区域分割和曲面拟合的室内定位方法，包括：在给定目标区域中设置M个信号源和N个参考点，保证每个参考点能够接受来自至少一个信号源的信号强度，同时记录每个参考点的二维坐标信息，对于每个参考点进行信号强度采样，然后对样本取均值，得到第i个参考点的指纹，将给定目标区域划分为K个区域，并根据每个区域内的参考点的指纹，建立相应的区域指纹，并存到指纹数据库，在每个区域内，针对每一个信号源，利用该区域内参考点的指纹，建立一个曲面拟合函数来表示该信号源在该区域内的信号强度分布。本发明能够解决现有指纹定位技术中，定位性能受参考点粒度的制约，定位结果只能从有限个参考点中提取，导致定位精度有限的问题。

说明书

技术领域

本发明属于通信和无线网络技术领域，更具体地，涉及一种基于区域 分割和曲面拟合的室内定位方法。

背景技术

随着数据业务和多媒体业务的快速发展，人们对室内定位与导航等位 置信息的需求日益增加。目前已经开发出多种室内定位技术，并且不同的 技术有不同的定位性能和硬件需求。比如，红外定位、蓝牙定位、超宽带 定位、WLAN定位等等。其中基于WLAN的室内定位技术得到了广泛的研究， 因为随着城市的智能化发展，城市的大多数区域已经实现了WLAN信号覆盖， 从而节省了硬件成本。而且，市场上许多移动设备都能够检测到WLAN热点 的信号强度（Received Signal Strength，简称RSS）。所以基于RSS的WLAN 室内定位成了许多研究人员的首选方案。

基于RSS的室内定位技术大致可以分为两种：基于测距定位和非基于 测距定位。前者通过观测到的RSS，根据信号传播模型计算移动目标与各信 号源的距离，然后推测目标所在位置。但是，由于室内环境的复杂多样， 包括墙壁、走廊、门窗、橱柜、玻璃等障碍物，使得传播模型不容易精确 得到，导致定位精度的下降。

指纹定位是一种最常用的非基于测距的定位方法。该方法工作在两个 阶段：离线训练阶段和在线定位阶段。对于一个给定的室内环境，在一些 已知位置的参考点处采样来自各信号源的信号强度，通过处理得到每个参 考点的指纹向量，并存储在指纹数据库中。定位阶段，将移动设备所观测 到的指纹与数据库参考点指纹进行对比，然后得到设备定位位置。一种常 用的定位算法就是最近邻法（Nearest Neighbor，简称NN）。然而，传统的 指纹定位算法性能受参考点的粒度制约。一般而言，参考点粒度越大，定 位精度越高，反之越差。但是，参考点的信号强度采样非常耗时耗力，所 以，为了得到较高的定位精度，常常会带来大量的采样工作和计算工作。

近年来有些研究学者提出了一些方法，期望能够减少训练阶段采样工 作量，同时维持较好的定位精度。有的方法建议使用一些未知位置的采样 点作为补偿点，比如说一条人的运动轨迹，来校正信号强度的分布模型参 数，如果这些参数因为参考点的采样数据不够而变得不准确。还有的方法 建议使用插值算法，插值产生一些虚拟参考点，并且这些参考点的指纹可 以从周围实测参考点指纹推测得到，从而丰富了指纹数据库。然而这些方 法都是离散的定位机制，定位效果受补偿点数目或者虚拟参考点数目的制 约，指纹对比只能工作在一个有限的数据空间集合里。

发明内容

针对现有技术的以上缺陷或改进需求，本发明提供了一种基于区域分 割和曲面拟合的室内定位方法，其目的在于解决现有指纹定位技术中，定 位性能受参考点粒度的制约，定位结果只能从有限个参考点中提取，导致 定位精度有限的技术问题。

为实现上述目的，按照本发明的一个方面，提供了一种基于区域分割 和曲面拟合的室内定位方法，包括以下步骤：

（1）在给定目标区域中设置r:I/个信号源和八i'个参考点，保证每个参考 点能够接受来自至少一个信号源的信号强度，同时记录每个参考点的二维 坐标信息(x_i，y_i)，i=1，2，…，N，I表示参考点的编号，x_i和y_i分别表示第i个 参考点的横坐标和纵坐标；

（2）对于每个参考点进行信号强度采样，然后对样本取均值，得到第 个参考点的指纹其中表示第i个参考点所接收到 的来自第j个信号源的平均信号强度，j=1，…,M;

（3）将给定目标区域划分为K个区域，并根据每个区域内的参考点的 指纹，建立相应的区域指纹F_k=(S_k1，S_k2，…，S_kM)，k=1，2，…，K，并存到指 纹数据库；

（4）在每个区域内，针对每一个信号源，利用该区域内参考点的指纹， 建立一个曲面拟合函数φ(x，y)来表示该信号源在该区域内的信号强度分布；

（5）利用移动终端扫描M个信号源的信号强度，以获得待定位点的指 纹并上传到服务器；其中表示待定位点观察到的来 自第j个信号源的信号强度；

（6）计算待定位点的指纹s^o与K个区域中各区域指纹的指纹差异度D_k， 以初步判断待定位点所在区域的位置；

（7）利用以下公式在步骤（6）确定的区域内进行位置搜索，以寻找 一个空间点，使得该空间点的指纹与待定位点的指纹s^o具有最小的指纹差异 度J，将该空间点作为最终定位结果：

$(\hat{x},\hat{y})=\arg \underset{(x,y)}{\min }J\equiv \underset{j=1}{\overset{M}{\Sigma }}{({\phi }_{\mathrm{kj}}(x,y)-\stackrel{-o}{s_j})}^2---\left(9\right)$

其中，是该空间点的坐标，J表示任意空间点的指纹与待定位点的 指纹s^o具有的指纹差异度，表示在第k个区域，为第j个信号源所建立 的信号强度分布拟合函数。

优选地，步骤（3）中，区域指纹S_kj是根据以下公式获得：

$S_{\mathrm{kj}}\stackrel{·}{=}\frac{1}{\left|R_k\right|}\underset{i^{\text{'}}=1}{\overset{\left|R_k\right|}{\Sigma }}{\stackrel{-}{s}}_{i^{\text{'}}j,}{i}^{\text{'}}=1,...,\left|R_k\right|,j=1,...,M,$

其中|R_k|表示第k个区域中参考点的数量，i'表示第k个区域内参考点的编 号。

优选地，步骤（4）包括以下子步骤：

（4-1）采用二元多项式来建立拟合函数φ(x，y)如以下公式（2）所示：

$\phi (x,y)=\underset{c=1}{\overset{p}{\Sigma }}\underset{d=1}{\overset{q}{\Sigma }}{a}_{\mathrm{cd}}{x}^{c-1}{y}^{d-1}---\left(2\right)$

其中，a_cd称为拟合系数，并且d_cd={a₁₁，…，a_er，…，a_pq}，e=1…，p， r=1，…，q。p，q为多项式拟合参数，且均为正整数；

（4-2）利用最小二乘准则构建目标函数h，以使拟合函数总的误差平 方和最小，其中目标函数的表达式如公式（3）；

$h=\underset{i^{\text{'}}=1}{\overset{n}{\Sigma }}{({\phi }_{\mathrm{kj}}(x_{i^{\text{'}}},y_{i^{\text{'}}})-{\stackrel{-}{s}}_{i^{\text{'}}})}^2---\left(3\right)$

其中，φ_kj(x，y)表示在第k个区域，为第j个信号源所建立的信号强度分 布拟合函数，(x_i'，y_i')表示在第k个区域内第i'个参考点的坐标，表示第i'个参 考点从第j个信号源所接受到的信号强度；

（4-3）将拟合函数φ(x，y)以矩阵的形式表示为φ(x，y)=x^TAy。其中，

X=[1xx²…x^p-1]^T，y=[1yy²…y^q-1]^T，对于任意空间点(x，y)，该点 的接收信号强度可通过计算φ（x，y)得到；

（4-4）目标函数h对每一个拟合系数a_cr求偏导，并令其为0，得到公 式（4）

$\frac{\partial h}{{\partial a}_{\mathrm{er}}}=\frac{\partial }{{\partial a}_{\mathrm{er}}}\underset{i^{\text{'}=1}}{\overset{n}{\Sigma }}{[\phi (x_{i^{\text{'}}},y_{i^{\text{'}}})-{\stackrel{-}{s}}_{i^{\text{'}}}]}^2$$=\underset{i^{\text{'}}=1}{\overset{n}{\Sigma }}\left\{2\right[\phi (x_{i^{\text{'}}},y_{i^{\text{'}}})-{\stackrel{-}{s}}_{i^{\text{'}}}\left]\frac{\partial }{{\partial a}_{\mathrm{er}}}\right[\phi (x_{i^{\text{'}}},y_{i^{\text{'}}})\left]\right\}---\left(4\right)$$=\underset{i^{\text{'}}=1}{\overset{n}{\Sigma }}\left\{2\right[\phi (x_{i^{\text{'}}},y_{i^{\text{'}}})-{\stackrel{-}{s}}_{i^{\text{'}}}\left]x_{i^{\text{'}}}^{e-1}{y}_{i^{\text{'}}}^{r-1}\right\}$$=0$

（4-5）对公式（4）变换，得到以下公式（5）

$\left(\begin{array}{c}\underset{i^{\text{'}}=1}{\overset{n}{\Sigma }}{x}_{i^{\text{'}}}^{e-1}{y}_{i^{\text{'}}}^{r-1}\phi (x_{i^{\text{'}}},y_{i^{\text{'}}})=\underset{i^{\text{'}}=1}{\overset{n}{\Sigma }}{x}_{i^{\text{'}}}^{e-1}{y}_{i^{\text{'}}}^{r-1}{\stackrel{-}{s}}_{i^{\text{'}}}\\ \underset{i^{\text{'}}=1}{\overset{n}{\Sigma }}{x}_{i^{\text{'}}}^{e-1}{y}_{i^{\text{'}}}^{r-1}\underset{c=1}{\overset{p}{\Sigma }}\underset{d=1}{\overset{q}{\Sigma }}{a}_{\mathrm{cd}}{x}_{i^{\text{'}}}^{c-1}{y}_{i^{\text{'}}}^{d-1}=\underset{i^{\text{'}}=1}{\overset{n}{\Sigma }}{x}_{i^{\text{'}}}^{e-1}{y}_{i^{\text{'}}}^{r-1}{\stackrel{-}{s}}_{i^{\text{'}}}\\ \underset{c=1}{\overset{p}{\Sigma }}\underset{d=1}{\overset{q}{\Sigma }}\left[a_{\mathrm{cd}}\underset{i^{\text{'}}=1}{\overset{n}{\Sigma }}\left(x_{i^{\text{'}}}^{e-1}{y}_{i^{\text{'}}}^{r-1}{x}_{i^{\text{'}}}^{c-1}{y}_{i^{\text{'}}}^{d-1}\right)\right]=\underset{i^{\text{'}}=1}{\overset{n}{\Sigma }}{x}_{i^{\text{'}}}^{e-1}{y}_{i^{\text{'}}}^{r-1}{\stackrel{-}{s}}_{i^{\text{'}}}\end{array}\right)---\left(5\right)$

（4-6）引入公式（6）

$\left(\begin{array}{c}{u}_{\mathrm{cd}}(e,r)=\underset{i^{\text{'}}=1}{\overset{n}{\Sigma }}\left(x_{i^{\text{'}}}^{c-1}{y}_{i^{\text{'}}}^{d-1}{x}_{i^{\text{'}}}^{e-1}{y}_{i^{\text{'}}}^{r-1}\right)\\ u(e,r)=\underset{i^{\text{'}}=1}{\overset{n}{\Sigma }}{x}_{i^{\text{'}}}^{e-1}{y}_{i^{\text{'}}}^{r-1}{\stackrel{-}{s}}_{i^{\text{'}}}\end{array}\right)---\left(6\right)$

则拟合系数a_cd便可通过a=U^-1V计算得到。

优选地，步骤（6）中，当待定位点的指纹s^o与某个区域的指纹差异度 最小时，则断定待定位点目标位于该区域。

优选地，步骤（7）中的公式是采用穷举位置搜索法或者梯度下降位置 搜索法进行位置搜索。

优选地，穷举位置搜索法的实现过程如下：

（a）采用格子框架来代表定位的目标区域，以一定步长为单位，将目 标区域划分成多个格子；

（b）对于区域内的任意格子点(x，y)，其指纹可以根据拟合函数

φ_k1(x，y)，…，φ_kj(x，y)，…，φ_km(x，y)，计算得到；

（c）将s^o与目标区域内每个格子点的指纹进行对比，满足步骤（7）中 公式的格子点作为定位结果。

优选地，梯度下降位置搜索法的实现过程如下：

（a’）梯度下降法通过迭代搜索的方式，每一步迭代都能减小J的值， 从而逐步逼近最优解。让l^(t)代表第t次迭代所到达的空间点，其中，t=1，2，…。 迭代搜索的过程定义如公式（10）；其中，α^(t)为搜索步长，d^(t)称为搜索方向，

l^(t+1)=l^(t)+α^(t)×d^(t)   (IO);

（b’）确定初始搜索点l⁽⁰⁾其可以随机选择。或将传统近邻定位法的 定位结果作为初始点；

（c’）确定搜索方向d^(t)。以l^(t)的负梯度方向作为搜索方向，即满足公 式（11）；

$d^{\left(t\right)}=-▿J\left(l^{\left(t\right)}\right)={[\frac{\partial J\left(l^t\right)}{\partial x},\frac{\partial J\left(l^t\right)}{\partial y}]}^T---\left(11\right)$

（d’）确定搜索步长α^(t)，α^(t)可以是固定步长，或者为可变步长且满 足公式（12）

${\alpha }^{\left(t\right)}=\arg \underset{\alpha }{\min }J(l^{\left(t\right)}-\alpha ▿J\left(l^{\left(t\right)}\right))---\left(12\right)$

（e’）当满足以下任一条件时，迭代终止：

第一，当迭代次数超过最大值t_max时；

第二，当相邻两次迭代点的位置相距小于阈值d_min时；

第三，当l^(t+1)超出定位区域的边界时。

优选地，步骤（6）具体是采用以下公式：

$D_k\stackrel{·}{=}\left|\right|F_k-s^o\left|\right|=\sqrt{\underset{j=1}{\overset{M}{\Sigma }}{(S_{\mathrm{kj}}-{\stackrel{-}{s}}_j^o)}^2}.$

总体而言，通过本发明所构思的以上技术方案与现有技术相比，能够 取得下列有益效果：

（1）定位精度高：由于采用了步骤（4），可以通过建立的信号强度分 布拟合函数，估计任意空间点的指纹，丰富了指纹数据库的信息。由于采 用了步骤（7），可以在连续的物理空间内寻找一点作为定位结果，突破了 传统的指纹定位结果只能从有限个参考点中提取的缺点，进而提高了定位 精度。

（2）减少了指纹对比工作量：由于采用了步骤（6），定位阶段首先将 待定位点指纹与区域指纹进行对比，将待定位点定位到一个区域内，而不 必与全部参考点指纹进行对比，因此减少了指纹对比工作量。

（3）可以提供粗糙的区域定位结果：由于采用了步骤（3），定位场景 根据建筑格局被划分为多个子区域，每个子区域都是一个独立的空间。对 于定位要求不高的场景，区域定位的结果也很实用。

附图说明

图1是本发明基于区域分割和位置搜索定位方法的流程图。

图2是使用梯度下降法进行位置搜索的算法流程图。

图3是本发明应用实例的定位场景图。

图4是三个参考点相对于一个信号源的接受信号强度分布图。

图5和图6示出本发明方法在不同拟合参数下，利用图3的301房间 内所有的参考点所建立的关于信号源3的信号强度拟合曲面，其中图5使 用的(p，q)=(2，2)，图6使用的(p，q)=(5，5)。

图7示出本发明方法在不同拟合参数下，参考点的实测信号强度和拟 合信号强度的数据对比。

图8示出每个房间使用不同参考点数目时，穷举位置搜索法、梯度下 降位置搜索法、传统近邻法的定位效果对比。

图9示出使用不同信号源数目时，穷举位置搜索法、梯度下降位置搜 索法、传统近邻法的定位效果对比。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图 及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体 实施例仅仅用以解释本发明，并不用于限定本发明。此外，下面所描述的 本发明各个实施方式中所涉及到的技术特征只要彼此之间未构成冲突就可 以相互组合。

本发明基于区域分割和位置搜索定位方法的整体思路在于，该方法在 训练阶段首先根据建筑的自然格局进行区域分割，并建立每个区域的指纹。 然后在每个区域内针对每个信号源，建立该区域内的信号强度分布拟合函 数。在定位阶段先对目标进行区域定位，确定目标的所在区域，然后在目 标区域内利用位置搜索算法，进行精确坐标定位。

如图1所示，本发明基于区域分割和曲面拟合的室内定位方法包括以 下步骤：

（1）在给定目标区域中设置M个信号源和N个参考点（Reference  point，简称RP），保证每个参考点能够接受来自至少一个信号源的信号强 度。同时记录每个参考点的二维坐标信息(x_i，y_i)，i=1，2，…，N，i表示参考点 的编号，x_i和y_i分别表示第i个参考点的横坐标和纵坐标；在本实施方式 中，信号源是无线接入点（Access point，简称AP）；

（2）对于每个参考点进行信号强度采样，然后对样本取均值，得到第 i个参考点的指纹其中表示第i个参考点所接收到 的来自第j个信号源的平均信号强度，j=1，…，M;需要注意的是，如果第i 个参考点没有从某个信号源接收到信号强度，则将对应的信号强度设为一 个很小的值，比如-100dB;

（3）将给定目标区域划分为K个区域，并根据每个区域内的参考点的 指纹，建立相应的区域指纹F_k=(S_kl，S_k2，…，S_kM)，k=1，2，…，K，并存到指 纹数据库；其中，K的取值大小取决于给定目标区域覆盖的房间数量，区域 指纹的实现过程如下：

将位于第k个区域的所有参考点组合成集合R_k，那么S_kj的获得方式如公 式（1）所示：

$S_{\mathrm{kj}}\stackrel{·}{=}\frac{1}{\left|R_k\right|}\underset{i^{\text{'}}=1}{\overset{\left|R_k\right|}{\Sigma }}{\stackrel{-}{s}}_{i^{\text{'}}j},i^{\text{'}}=1,...,\left|R_k\right|,j=1,...,M---\left(1\right)$

其中|R_k|表示第k个区域中参考点的数量，i'表示第k个区域内参考点的编 号；

（4）在每个区域内，针对每一个信号源，利用该区域内参考点的指纹， 建立一个曲面拟合函数φ(x，y)来表示该信号源在该区域内的信号强度分布。

本步骤的优点在于：通过建立信号强度分布的曲面拟合函数，可以估 计空间内任意空间点的指纹，从而极大的丰富了指纹数据库的信息。

本步骤包括以下子步骤：

（4-1）采用二元多项式来建立拟合函数φ(x，y)，如公式（2）所示

$\phi (x,y)=\underset{c=1}{\overset{p}{\Sigma }}\underset{d=1}{\overset{q}{\Sigma }}{a}_{\mathrm{cd}}{x}^{c-1}{y}^{d-1}---\left(2\right)$

其中，a_cd称为拟合系数，并且a_cd={a₁₁，…，aer，…,apq}，e=1…，p， r=1，…，q。p，q为多项式拟合参数，且均为正整数，优选地，p和q的取值范 围是2至5；

（4-2）利用最小二乘准则构建目标函数h，以使拟合函数总的误差平 方和最小，其中目标函数的表达式如公式（3）；

$h=\underset{i^{\text{'}}=1}{\overset{n}{\Sigma }}{({\phi }_{\mathrm{kj}}(x_{i^{\text{'}}},y_{i^{\text{'}}})-{\stackrel{-}{s}}_{i^{\text{'}}})}^2---\left(3\right)$

其中，φ_kj(x，y)表示在第k个区域，为第j个信号源所建立的信号强度分 布拟合函数，(x_i'，y_i')表示在第k个区域内第i'个参考点的坐标，表示第i'个参 考点从第j个信号源所接受到的信号强度，为方便起见，用n取代|R_k|来表示 第k个区域内参考点的数量。

（4-3）将拟合函数φ(x，y)以矩阵的形式表示为φ(x，y)=x^TAy。其中，

x=[1xx²…x^p-1]^T，y=[1yy²…y^q-1]^T，对于任意空间点(x，y)，该点 的接收信号强度可通过计算φ(x，y)得到；

（4-4）目标函数h对每一个拟合系数a_cr求偏导，并令其为0，得到公 式（4）

$\frac{\partial h}{{\partial a}_{\mathrm{er}}}=\frac{\partial }{{\partial a}_{\mathrm{er}}}\underset{i^{\text{'}=1}}{\overset{n}{\Sigma }}{[\phi (x_{i^{\text{'}}},y_{i^{\text{'}}})-{\stackrel{-}{s}}_{i^{\text{'}}}]}^2$$=\underset{i^{\text{'}}=1}{\overset{n}{\Sigma }}\left\{2\right[\phi (x_{i^{\text{'}}},y_{i^{\text{'}}})-{\stackrel{-}{s}}_{i^{\text{'}}}\left]\frac{\partial }{{\partial a}_{\mathrm{er}}}\right[\phi (x_{i^{\text{'}}},y_{i^{\text{'}}})\left]\right\}---\left(4\right)$$=\underset{i^{\text{'}}=1}{\overset{n}{\Sigma }}\left\{2\right[\phi (x_{i^{\text{'}}},y_{i^{\text{'}}})-{\stackrel{-}{s}}_{i^{\text{'}}}\left]x_{i^{\text{'}}}^{e-1}{y}_{i^{\text{'}}}^{r-1}\right\}$$=0$

（4-5）通过对公式（4）变换，得到公式（5）

$\left(\begin{array}{c}\underset{i^{\text{'}}=1}{\overset{n}{\Sigma }}{x}_{i^{\text{'}}}^{e-1}{y}_{i^{\text{'}}}^{r-1}\phi (x_{i^{\text{'}}},y_{i^{\text{'}}})=\underset{i^{\text{'}}=1}{\overset{n}{\Sigma }}{x}_{i^{\text{'}}}^{e-1}{y}_{i^{\text{'}}}^{r-1}{\stackrel{-}{s}}_{i^{\text{'}}}\\ \underset{i^{\text{'}}=1}{\overset{n}{\Sigma }}{x}_{i^{\text{'}}}^{e-1}{y}_{i^{\text{'}}}^{r-1}\underset{c=1}{\overset{p}{\Sigma }}\underset{d=1}{\overset{q}{\Sigma }}{a}_{\mathrm{cd}}{x}_{i^{\text{'}}}^{c-1}{y}_{i^{\text{'}}}^{d-1}=\underset{i^{\text{'}}=1}{\overset{n}{\Sigma }}{x}_{i^{\text{'}}}^{e-1}{y}_{i^{\text{'}}}^{r-1}{\stackrel{-}{s}}_{i^{\text{'}}}\\ \underset{c=1}{\overset{p}{\Sigma }}\underset{d=1}{\overset{q}{\Sigma }}\left[a_{\mathrm{cd}}\underset{i^{\text{'}}=1}{\overset{n}{\Sigma }}\left(x_{i^{\text{'}}}^{e-1}{y}_{i^{\text{'}}}^{r-1}{x}_{i^{\text{'}}}^{c-1}{y}_{i^{\text{'}}}^{d-1}\right)\right]=\underset{i^{\text{'}}=1}{\overset{n}{\Sigma }}{x}_{i^{\text{'}}}^{e-1}{y}_{i^{\text{'}}}^{r-1}{\stackrel{-}{s}}_{i^{\text{'}}}\end{array}\right)---\left(5\right)$

（4-6）引入公式（6）

$\left(\begin{array}{c}{u}_{\mathrm{cd}}(e,r)=\underset{i^{\text{'}}=1}{\overset{n}{\Sigma }}\left(x_{i^{\text{'}}}^{c-1}{y}_{i^{\text{'}}}^{d-1}{x}_{i^{\text{'}}}^{e-1}{y}_{i^{\text{'}}}^{r-1}\right)\\ u(e,r)=\underset{i^{\text{'}}=1}{\overset{n}{\Sigma }}{x}_{i^{\text{'}}}^{e-1}{y}_{i^{\text{'}}}^{r-1}{\stackrel{-}{s}}_{i^{\text{'}}}\end{array}\right)---\left(6\right)$

（4-7）将公式（6）带入公式（4），则公式（4）可表示为公式（7）：

则拟合系数a_cd便可通过a=U^-1V计算得到。

（5）利用移动终端扫描M个信号源的信号强度，以获得待定位点的指 纹并上传到服务器；其中表示待定位点观察到的来 自第j个信号源的信号强度，需要注意的是，如果待定位点没有从某个信号 源接收到信号强度，则将其对应的信号强度设为一个很小的值，比如 -100dB；

（6）利用公式（8）计算待定位点的指纹s^o与K个区域中各区域指纹的 指纹差异度D_k，以初步判断待定位点所在区域的位置；具体而言，当待定 位点的指纹s^o与某个区域的指纹差异度最小时，则断定待定位点目标位于该 区域；

$D_k\stackrel{·}{=}\left|\right|F_k-s^o\left|\right|=\sqrt{\underset{j=1}{\overset{M}{\Sigma }}{(S_{\mathrm{kj}}-{\stackrel{-}{s}}_j^o)}^2}---\left(8\right)$

本步骤的优点在于通过将目标预先定位到一个区域，大大缩小目标可 能位于的区域，减小指纹对比工作量。此外，区域定位结果对定位要求不 高的场景也很实用。

（7）根据位置搜索算法并利用以下公式（9）在步骤（6）确定的区域 内进行位置搜索，以寻找一个空间点，使得该空间点的指纹与待定位点的 指纹s^o具有最小的指纹差异度J，将该空间点作为最终定位结果。

$(\hat{x},\hat{y})=\arg \underset{(x,y)}{\min }J\equiv \underset{j=1}{\overset{M}{\Sigma }}{({\phi }_{\mathrm{kj}}(x,y)-\stackrel{-o}{s_j})}^2---\left(9\right)$

其中，是该空间点的坐标，在本实施方式中，位置搜索算法采用穷 举位置搜索法或者梯度下降位置搜索法。

本步骤的优点在于：可以在连续的物理空间内寻找一点作为定位结果， 突破了传统的指纹定位结果只能从有限个参考点中提取的缺点，进而提高 了定位精度。

其中，穷举位置搜索法的实现过程如下：

（a）采用格子框架来代表定位的目标区域，以一定步长为单位，将目 标区域划分成多个格子。步长大小和精度要求成反比，步长越小精度越高。

（b）对于区域内的任意格子点(x，y)，其指纹可以根据拟合函数

φ_k1(x，y)，…，φ_kj(x，y)，…φ_km(x，y)，计算得到。

（c）将s^o与目标区域内每个格子点的指纹进行对比，满足公式（9）的 格子点作为定位结果。

如图2所示，梯度下降位置搜索法的实现过程如下：

（a’）梯度下降法通过迭代搜索的方式，每一步迭代都能减小J的值， 从而逐步逼近最优解。让l(t)代表第t次迭代所到达的空间点，其中，t=1，2，…。 那么迭代搜索的过程定义如公式（10）；其中，α^(t)称为搜索步长，d^(t)称为搜 索方向。 l^(t+1)=l^(t)+α^(t)×d^(t)   (10)

（b’）确定初始搜索点l⁽⁰⁾初始点可以随机选择。为了提高搜索效率， 也可以将传统近邻定位法的定位结果作为初始点。

（c’）确定搜索方向d^(t)以l^(t)的负梯度方向作为搜索方向，即满足公 式（11）；

$d^{\left(t\right)}=-▿J\left(l^{\left(t\right)}\right)={[\frac{\partial J\left(l^t\right)}{\partial x},\frac{\partial J\left(l^t\right)}{\partial y}]}^T---\left(11\right)$

（d’）确定搜索步长α^(t)。α^(t)可以是固定步长，为了达到较高的定位 精度，建议采用可变步长，这时α^(t)满足公式（12）

${\alpha }^{\left(t\right)}=\arg \underset{\alpha }{\min }J(l^{\left(t\right)}-\alpha ▿J\left(l^{\left(t\right)}\right))---\left(12\right)$

如果采用固定步长，则其取值是由需要的定位精度决定，定位精度越 高，则固定步长的取值越小。

（e’）确定迭代终止条件。1、当迭代次数超过最大值t_max时，t_max由 定位精度要求决定，精度要求越高，t_max越大；2、当相邻两次迭代点的位 置相距小于阈值d_min时，d_min由定位精度要求决定的，精度要求越高，d_min越 小；3、当l^(t+1)超出定位区域的边界时。

应用实例

如图3所示，本发明的场景根据自然格局可以划分为6个房间，每个 房间长6.9m，宽6.8m。在场景内共放置8个信号源，150个参考点，每个 参考点处都可以收到来自8个信号源的信号强度。

使用戴尔平板电脑作为终端进行信号强度的采样。采样数据分为两部 分：一部分用来建立参考点的指纹数据库；一部分用来测试。在每个参考 点处进行150次信号采样，每秒钟采样两次；我们随机选择78个测试点来 验证所提出的算法。在每个测试点进行5秒钟的信号采样，每秒钟采样两 次。参考点指纹和测试点指纹通过对采样信号取均值得到。

表1示出每个房间使用不同的参考点数目，以及使用不同的信号源数 目与区域定位命中率之间的关系。

参考点数目 6 10 15 20 25 命中率 94.87% 92.31% 93.59% 92.31% 93.59% 信号源数目 4 5 6 7 8 命中率 92.31% 91.03% 94.87% 96.15% 93.59%

表1

图4示出三个参考点相对于一个信号源的接受信号强度分布图。其中， 参考点a和参考点b在301房间内，参考点c在隔壁303房间内。从该图 可以看出，在同一个区域内物理空间相近的点所观察到的信号强度也很相 近，而对于不同区域内的空间点，由于墙壁的阻隔因素，观察到的信号强 度相差很大。这也为基于区域分割进行曲面拟合和区域定位提供了有利条 件。

图5和图6示出在不同拟合参数下，利用301房间内所有的参考点所 建立的关于信号源3的信号强度分布拟合曲面。图5使用(p，q)=(2，2)，图 6使用(p，q)=(5，5)。

图7示出本发明方法在不同拟合参数下，参考点的实测信号强度和拟 合信号强度的数据对比。

结合图5至图7可以看出，采用较大的(p，q)值可以得到精确地拟合信 号强度值，而较小的(p，q)值主要反映信号强度的变化趋势。如果拟合数目 不足，较大的p和q值可能会导致过拟合现象。而且考虑到计算量问题， 建议采用较小的p和q。

图8示出每个房间使用不同参考点数目时，穷举位置搜索法、梯度下 降位置搜索法、传统近邻法的定位效果对比。

图9示出使用不同信号源数目时，穷举位置搜索法、梯度下降位置搜 索法、传统近邻法的定位效果对比。

通过图8、图9的对比结果可以看出，很明显，本发明提出的基于区域 分割和位置搜索的定位算法，无论使用穷举搜索，还是梯度下降搜索，都 较传统近邻定位算法有明显提高。这是由于通过曲面拟合，我们建立了更 为详细的信号强度分布函数，可以估计任意空间点的指纹，从而丰富了定 位阶段的位置搜索空间，所以提高了定位精度。

本领域的技术人员容易理解，以上所述仅为本发明的较佳实施例而已， 并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等 同替换和改进等，均应包含在本发明的保护范围之内。