CN102625443B - 终端定位方法及装置 - Google Patents

Abstract

本发明公开了终端定位方法及装置。方法包括：对于任一小区，在小区中设置第一预设数目个聚类终端，获取每个聚类终端的位置数据：到达角AOA、到达时间TOA、信噪比SNR和物理坐标，将每个聚类终端的位置数据放入历史数据库；对于任一待测终端，测量该待测终端的AOA、TOA和SNR，根据该待测终端的AOA、TOA和SNR，在历史数据库中查找与该待测终端最匹配的聚类终端，根据该聚类终端的物理坐标确定该待测终端的初始估计位置；根据待测终端的初始估计位置和该待测终端与其它待测终端之间的距离，计算该待测终端的最终位置。本发明只需一个基站就可实现对终端的定位。

Description

终端定位方法及装置

技术领域

本发明涉及定位技术领域，具体涉及终端定位方法及装置。

背景技术

随着移动通信的发展，移动通信系统中的移动定位业务越来越受到关注。目前有3种常用的定位方法：

1、基于时间测量的定位方法，如：到达时间（TOA，Time of Arrival）法、到达时间差（TDOA，Time Different Of Arrival）法。主要通过检测电波从发射机到接收机的传播时间，算出二者间的距离，进而通过某种方法计算出移动台的估计位置。

2、信号到达角（AOA，Angle of Arrival）法：通过基站接收机天线阵列检测出移动台发射电波的AOA，该AOA可以构成一条从基站到移动台的径向连线，即方位线，利用多个基站提供的AOA测量值，可以画出多条方位线，其交点就是移动台的估计位置。

3、辅助全球卫星定位系统（AGPS，Assisted Global Positioning System）定位法：一种结合了网络基站信息和GPS信息对移动台进行定位的技术。移动台利用网络提供的GPS辅助信息接收GPS原始信号，通过对原始信号的解调获得GPS伪距信息，网络根据伪距信息和其它定位设备的辅助信息完成对GPS信息的处理，并估算移动台的位置。

现有技术的缺点如下：

基于时间测量的定位方法：其定位精度受系统定时精度的影响，基站间必须严格同步，以确保系统本身的定时误差不会给定位结果造成明显的影响；而且终端必须最少观察到三个基站信号才能定位。

信号到达角（AOA）法：两个基站就可实现定位，但基站需要有接收天线阵列，精度受信道影响较大，在建筑物密集区定位困难。

AGPS定位法：为了定位要求至少接收四颗卫星的信号，在密集的市区高楼之间、在建筑物内以及只能见到4个以下卫星的任何地区，GPS系统一般不起作用，无法实现精确的定位。

发明内容

本发明提供终端定位方法及装置，以达到只需一个基站就可实现对终端的定位。

本发明的技术方案是这样实现的：

一种终端定位方法，该方法包括：

对于任一小区，在小区中设置第一预设数目个聚类终端，获取每个聚类终端的位置数据：到达角AOA、到达时间TOA、信噪比SNR和物理坐标，将每个聚类终端的位置数据放入历史数据库；

对于任一待测终端，测量该待测终端的AOA、TOA和SNR，根据该待测终端的AOA、TOA和SNR，在历史数据库中查找与该待测终端最匹配的聚类终端，根据该聚类终端的物理坐标确定该待测终端的初始估计位置；

根据待测终端的初始估计位置和该待测终端与其它待测终端之间的距离，计算该待测终端的最终位置。

所述在小区中设置第一预设数目个聚类终端，获取每个聚类终端的位置数据：到达角AOA、到达时间TOA、信噪比SNR和物理坐标，将每个聚类终端的位置数据放入历史数据库包括：

在小区中设置第一预设数目个初始聚类终端，并设置第二预设数目个样本终端；

根据样本终端与聚类终端的距离，对所有样本终端进行聚类，聚类完成，得到第一预设数目个新聚类终端，计算每个新聚类终端的位置数据：AOA、TOA、SNR和物理坐标，将每个新聚类终端的位置数据放入历史数据库。

所述根据样本终端与聚类终端的距离，对所有样本终端进行聚类包括：

初始化迭代次数为0；

对于每个样本终端，寻找与该样本终端最近的聚类终端，将该样本终端归属于该聚类终端，将归属于同一聚类终端的所有样本终端作为一聚类群，将每个聚类群的质心作为一个新聚类终端，计算当前迭代得到的所有新聚类终端的物理坐标与上一次迭代得到的所有聚类终端的物理坐标的均方误差；若均方误差小于预设值，则确定聚类完成；否则，返回执行所述对于每个样本终端，寻找与该样本终端最近的聚类终端的动作。

所述在小区中设置第一预设数目个初始聚类终端为：

将小区均匀划分为第一预设数目个子区域，将每个子区域的中心作为一个初始聚类终端所在位置。

所述计算该待测终端的最终位置之后进一步包括：

当计算出该待测终端的最终位置后，将该待测终端作为新的样本终端，与已有样本终端进行聚类，聚类完成，以得到的各新聚类终端的位置数据：AOA、TOA、SNR和物理坐标更新历史数据库。

所述根据该待测终端的AOA、TOA和SNR，在历史数据库中查找与该待测终端最匹配的聚类终端包括：

根据该待测终端的AOA、TOA和SNR，在历史数据库中查找与该待测终端的欧式距离最小的聚类终端；

所述根据该聚类终端的物理坐标确定该待测终端的初始估计位置为：

计算所述待测终端的AOA与所述聚类终端的AOA之差α，将该聚类终端的物理坐标旋转α，将旋转后得到的物理坐标作为所述待测终端的初始估计位置。

所述根据待测终端的初始估计位置和该待测终端与其它待测终端之间的距离，计算该待测终端的最终位置之前进一步包括：

通过如下步骤计算所述待测终端与任一其它待测终端之间的距离：

计算β＝AOA_i-AOA_k，其中，AOA_i为所述待测终端的AOA，AOA_k为所述任一其它待测终端的AOA；

计算所述待测终端与基站的距离计算所述任一其它待测终端与基站的距离其中，为根据SNR_i计算到的所述待测终端与基站的距离，为根据TOA_i计算到的所述待测终端与基站的距离，为根据SNR_k计算到的所述任一其它待测终端与基站的距离，为根据TOA_k计算到的所述任一其它待测终端与基站的距离，SNR_i为所述待测终端的SNR，TOA_i为所述待测终端的TOA，SNR_k为所述任一其它待测终端的SNR，TOA_k为所述任一其它待测终端的TOA；

计算所述待测终端与所述任一其它待测终端间的距离d_ik：

$d_{\mathrm{ik}}=\sqrt{d_i^2+d_k^2-2d_i{d}_k\·\cos \mathrm{\β}}.$

所述根据待测终端的初始估计位置和该待测终端与其它待测终端之间的距离，计算该待测终端的最终位置包括：

设所述待测终端的位置分布服从以初始估计位置为中心的二维高斯分布，则根据所述待测终端的初始估计位置确定该待测终端的初始位置概率分布；

初始化迭代次数为0；

根据所述待测终端与任一其它待测终端之间的距离，计算本次迭代过程中任一其它待测终端对所述待测终端的位置概率分布的更新值；

根据所述待测终端的初始位置概率分布以及本次迭代过程中其它待测终端对所述待测终端的位置概率分布的更新值，得到所述待测终端的最新位置概率分布；

判断迭代次数是否小于预定次数，若是，返回执行所述计算本次迭代过程中任一其它待测终端对所述待测终端的位置概率分布的更新值的动作，继续下一次迭代过程；否则，将待测终端的最新位置概率分布作为其最终位置概率分布，根据该最终位置概率分布计算所述待测终端的最终位置。

所述计算本次迭代过程中任一其它待测终端对所述待测终端的位置概率分布的更新值为：

计算

其中，k为任一其它待测终端的序号，i为所述待测终端的序号，q为当前迭代次数，为本次迭代过程中任一其它待测终端k对所述待测终端i的位置概率分布的更新值，(s,t)为任一其它待测终端k的物理坐标，为任一其它待测终端k在上一次迭代后的位置概率分布；

$p\left(d_{\mathrm{ik}}\right|(x,y),(s,t))=\frac{1}{{2\mathrm{\π\σ}}^2}\exp \{-\frac{{(d_{\mathrm{ik}}-\sqrt{{(x-s)}^2+{(y-t)}^2})}^2}{2{\mathrm{\σ}}^2}\}$

该公式的物理意义为：当所述任一其它待测终端k在物理位置(s,t)上时，所述待测终端i在物理位置(x,y)上的概率；d_ik为所述任一其它待测终端k与所述待测终端i间的距离；

所述根据所述待测终端的初始位置概率分布以及本次迭代过程中其它待测终端对所述待测终端的位置概率分布的更新值，得到所述待测终端的最新位置概率分布为：

其中，p_i(x,y)为所述待测终端的初始位置概率分布；

所述根据该最终位置概率分布计算所述待测终端的最终位置为：

${\hat{x}}_i=\underset{x,y}{\mathrm{\Σ}}x\·P_i^{\′}(x,y)$

${\hat{y}}_i=\underset{x,y}{\mathrm{\Σ}}y\·P_i^{\′}(x,y)$

其中，(x,y)的取值范围为小区的覆盖区域。

一种终端定位装置，该装置包括：

第一单元：对于任一小区，在小区中设置第一预设数目个聚类终端，获取每个聚类终端的位置数据：到达角AOA、到达时间TOA、信噪比SNR和物理坐标，将每个聚类终端的位置数据放入历史数据库；

第二单元：对于任一待测终端，测量该待测终端的AOA、TOA和SNR，根据该待测终端的AOA、TOA和SNR，在历史数据库中查找与该待测终端最匹配的聚类终端，根据该聚类终端的物理坐标确定该待测终端的初始估计位置，将该待测终端的初始估计位置发送给第三单元；

第三单元：根据待测终端的初始估计位置和该待测终端与其它待测终端之间的距离，计算该待测终端的最终位置。

所述第一单元包括：

第一模块：在小区中设置第一预设数目个初始聚类终端，并设置第二预设数目个样本终端；

第二模块：初始化迭代次数为0；对于每个样本终端，寻找与该样本终端最近的聚类终端，将该样本终端归属于该聚类终端，将归属于同一聚类终端的所有样本终端作为一聚类群，将每个聚类群的质心作为一个新聚类终端，计算当前迭代得到的所有新聚类终端的物理坐标与上一次迭代得到的所有聚类终端的物理坐标的均方误差；若均方误差小于预设值，则确定聚类完成；否则，返回执行所述对于每个样本终端，寻找与该样本终端最近的聚类终端的动作。

所述第三单元进一步用于，当计算出该待测终端的最终位置后，将该待测终端的位置数据：AOA、TOA、SNR及物理坐标发送给第一单元；

所述第一单元接收到所述待测终端的位置数据后，将该待测终端作为新的样本终端，重新对所有样本终端进行聚类，聚类完成，以得到的各新聚类终端的位置数据：AOA、TOA、SNR和物理坐标更新历史数据库。

所述第二单元包括：

第三模块：对于任一待测终端，测量该待测终端的AOA、TOA和SNR；

第四模块：根据该待测终端的AOA、TOA和SNR，在历史数据库中查找与该待测终端的欧式距离最小的聚类终端，计算所述待测终端的AOA与所述聚类终端的AOA之差α，将该聚类终端的物理坐标旋转α，将旋转后得到的物理坐标作为所述待测终端的初始估计位置。

所述第三单元包括：

第五模块：计算所述待测终端与任一其它待测终端间的距离，将计算得到的各距离发送给第六模块；

第六模块：设所述待测终端的位置分布服从以初始估计位置为中心的二维高斯分布，则根据所述待测终端的初始估计位置确定该待测终端的初始位置概率分布；初始化迭次次数为0；根据所述待测终端与任一其它待测终端间的距离，计算本次迭代过程中任一其它待测终端对所述待测终端的位置概率分布的更新值；根据所述待测终端的初始位置概率分布以及本次迭代过程中其它待测终端对所述待测终端的位置概率分布的更新值，得到所述待测终端的最新位置概率分布；判断迭代次数是否小于预定次数，若是，返回执行所述计算本次迭代过程中任一其它待测终端对所述待测终端的位置概率分布的更新值的动作，继续下一次迭代过程；否则，将待测终端的最新位置概率分布作为其最终位置概率分布，根据该最终位置概率分布计算所述待测终端的最终位置。

所述第五模块包括：

第一子模块：计算β＝AOA_i-AOA_k，其中，AOA_i为所述待测终端的AOA，AOA_k为所述任一其它待测终端的AOA，将β发送给第三子模块；

第二子模块：计算所述待测终端与基站的距离计算所述任一其它待测终端与基站的距离其中，为根据SNR_i计算到的所述待测终端与基站的距离，为根据TOA_i计算到的所述待测终端与基站的距离，为根据SNR_k计算到的所述任一其它待测终端与基站的距离，为根据TOA_k计算到的所述任一其它待测终端与基站的距离，将d_i、d_k发送给第三子模块；

第三子模块：计算所述待测终端与所述任一其它待测终端间的距离d_ik：

$d_{\mathrm{ik}}=\sqrt{d_i^2+d_k^2-2d_i{d}_k\·\cos \mathrm{\β}}.$

所述装置位于基站上。

与现有技术相比，本发明中，无需多个基站进行协同，只需一个基站测量得到待测终端的AOA、TOA和SNR，就可实现对终端的定位；且，在一次定位过程中，可同时实现对多个终端的定位；且，不需现有协议外的参数数据，就可实现对终端的定位，具有较好的兼容性和使用性。

附图说明

图1为本发明实施例提供的终端定位方法流程图；

图2为本发明实施例提供的建立历史数据库的方法流程图；

图3为本发明实施例提供的小区划分示意图；

图4为本发明实施例提供的聚类点的位置的示意图；

图5为本发明实施例提供的根据历史数据库对待测终端定位的方法流程图；

图6为本发明实施例提供的确定待测终端i初始估计位置的方法流程图；

图7为本发明实施例提供的根据匹配聚类点的位置确定待测终端位置的示意图；

图8为本发明实施例提供的根据待测终端的初始估计位置和待测终端两两之间的距离，采用和积算法获得待测终端的最终估计位置的方法流程图；

图9为本发明实施例提供的待测终端的位置分布示意图；

图10为应用本发明实施例根据待测终端的初始估计位置和待测终端两两之间的距离，采用和积算法获得待测终端的最终估计位置的示意图；

图11为本发明实施例提供的终端定位装置的组成图。

具体实施方式

图1为本发明实施例提供的终端定位方法流程图，如图1所示，其具体步骤如下：

步骤101：对于任一小区，在小区中设置第一预设数目个样本点，根据样本点的位置，对所有样本点进行聚类，得到第二预设数目个聚类点，计算每个聚类点的位置数据：AOA、TOA、SNR和物理坐标，将每个聚类点的位置数据放入历史数据库。

每个样本点为一个物理坐标已知的移动终端。

步骤102：对于任一待测终端，基站测量该待测终端的AOA、TOA和SNR，根据该待测终端的AOA、TOA和SNR，在历史数据库中查找与该待测终端最匹配的聚类点，根据该聚类点的物理坐标确定该待测终端的初始估计位置。

步骤103：计算两两待测终端之间的距离，根据待测终端的初始估计位置和该待测终端与其它待测终端之间的距离，计算该待测终端的最终位置。

步骤104：将该待测终端作为新的样本点，与已有样本点进行聚类，聚类完成，以得到的各聚类点的位置数据：AOA、TOA、SNR和物理坐标更新历史数据库。

以下给出上述步骤101的具体实施方式：

图2为本发明实施例提供的建立历史数据库的方法流程图，如图2所示，其具体步骤如下：

步骤201：对于任一小区，基站将该小区均匀划分为预设数目：M（M>1）个区域，将每个区域的中心作为一个初始聚类点，基站初始化迭代次数l＝0，记录每个初始聚类点的位置且，基站在该小区中设置预设数目个样本点。

例如：对于任一小区，如图3中的小区0所示，先将该小区划分为6个正三角形，然后将每个正三角形再划分为4个正三角形，得到24个正三角形，再将每个正三角形划分为4个正三角形，这样，该小区共包含了M=96个正三角形，将该M个正三角形中每个正三角形的中心作为一个初始聚类点，共得到M个初始聚类点，每个聚类点的位置表示为其中，表示第ｊ个聚类点的初始横坐标，表示第ｊ个聚类点的初始纵坐标。

步骤202：对于该小区中的每个样本点，基站在上一次迭代后得到的M个聚类点中寻找与该样本点距离最近的聚类点，将该样本点归属于该聚类点，将归属于同一聚类点的所有样本点作为一聚类群，这样得到M个聚类群，将各个聚类群表示为D_j,j＝0,1,...,M-1。

步骤203：基站计算每个聚类群的质心，将每个质心作为一个新聚类点，这样共得到M个新聚类点，记录M个新聚类点的位置

任一聚类群D_j的质心的计算公式如下：

${\text{s}}_j^{l+1}=\frac{1}{\mathrm{num}\left(D_j\right)}\underset{(x_i,y_i)\∈D_j}{\mathrm{\Σ}}{x}_i,t_j^{l+1}=\frac{1}{\mathrm{num}\left(D_j\right)}\underset{(x_i,y_i)\∈D_j}{\mathrm{\Σ}}{y}_i$

其中，l+1为当前迭代次数，为当前迭代后得到的第j个聚类点的横坐标，为当前迭代后得到的第j个聚类点的纵坐标，num(D_j)为当前迭代后得到的聚类群D_j中的样本点的个数，x_i为聚类群D_j中的第i个样本点的横坐标，y_i为聚类群D_j中的第i个样本点的纵坐标。

步骤204：基站计算M个新聚类点的物理坐标与上一次迭代后得到的M个聚类点的物理坐标的均方误差E：

$E=\frac{1}{M}\underset{j=1}{\overset{M}{\mathrm{\Σ}}}({(s_j^{l+1}-s_j^l)}^2+{(t_j^{l+1}-t_j^l)}^2)$

为上一次迭代后得到的第j个聚类点的横坐标，为上一次迭代后得到的第j个聚类点的纵坐标

步骤205：基站判断E是否小于预设阈值，若是，执行步骤206；否则，返回步骤202，开始新一轮迭代即，第l+2次迭代。

步骤206：基站确定聚类完成，根据信道传播模型以及当前迭代后得到的M个聚类点的位置，得到各个聚类点的AOA，TOA及SNR，将每个聚类点的AOA，TOA、SNR及物理坐标(x,y)作为该聚类点的位置数据，以(AOA,TOA,SNR,(x,y))的形式存储在历史数据库中。

图4为本发明实施例提供的聚类点的位置的示意图，如图4所示，设基站位置为(0,0)，则对于任一聚类点(x_r,y_r),r＝0,1,...,M-1，聚类点(x_r,y_r)的AOA及TOA为：

${\mathrm{AOA}}_r=\arctan \frac{y_r}{x_r}\±\mathrm{\π}$

${\mathrm{TOA}}_r=\frac{\sqrt{{x_r}^2+{y_r}^2}}{c}$

其中，c为光速。

图5为本发明实施例提供的根据历史数据库对待测终端定位的方法流程图，如图5所示，其具体步骤如下：

步骤501：对于小区内的任一待测终端i，基站根据待测终端i发来的导频信号，测得该终端的测量位置数据AOA_i，TOA_i及SNR_i，在历史数据库中查找与(AOA_i,TOA_i,SNR_i)最匹配的聚类点s的位置数据，根据聚类点s的物理坐标(x_s,y_s)确定待测终端i的初始估计位置(x_ui,y_ui)。

步骤502：基站根据测量的各个待测终端的AOA及TOA，计算任意两个待测终端i、k之间的距离d_ik。

设待测终端i、k的测量位置数据分别为(AOA_i,TOA_i,SNR_i)、(AOA_k,TOA_k,SNR_k)，则待测终端i、k之间的距离可通过如下过程得到：

步骤01：基站计算β＝AOA_i-AOA_k。

步骤02：基站根据信道传播模型，计算待测终端i与基站的距离 $d_i=(d_{{\mathrm{SNR}}_i}+d_{{\mathrm{TOA}}_i})/2,$ 计算待测终端k与基站的距离 $d_k=(d_{{\mathrm{SNR}}_k}+d_{{\mathrm{TOA}}_k})/2.$

其中，为采用现有技术根据SNR_i计算到的待测终端i与基站的距离，为采用现有技术根据TOA_i计算到的待测终端i与基站的距离，为采用现有技术根据SNR_k计算到的待测终端k与基站的距离，为采用现有技术根据TOA_k计算到的待测终端k与基站的距离。

步骤03：基站利用余弦定理计算待测终端i、k间的距离d_ik：

$d_{\mathrm{ik}}=\sqrt{d_i^2+d_k^2-2d_i{d}_k\·\cos \mathrm{\β}}$

步骤503：设每个待测终端的位置分布都符合以步骤201中得到的初始估计位置为中心的二维高斯分布，结合步骤202中得到的各个待测终端之间的距离，基站采用和积迭代算法，获得各个待测终端的最终估计位置。

以下给出上述步骤501的具体实施方式：

图6为本发明实施例提供的确定待测终端i初始估计位置的方法流程图，如图6所示，其具体步骤如下：

步骤601：设(AOA_i,TOA_i,SNR_i)为待测终端i的测量位置数据，(AOA_r,TOA_r,SNR_r,(x_r,y_r))为历史数据库中第r个聚类点的位置数据，基站根据信道传播模型，通过SNR_i和TOA_i计算得到待测终端i与基站的距离此时，待测终端i的测量位置数据表示为

本实施例中，以欧氏距离来量度待测终端i的测量位置数据和历史数据库中各聚类点的位置数据的相近程度，但是由于AOA、TOA、SNR的量纲不同，无法直接进行计算，因此，这里统一将各个值转换为距离长度。

步骤602：对于任一聚类点r，基站根据聚类点r的物理坐标(x_r,y_r)，计算得到聚类点r与基站的距离d_r，则聚类点r的位置数据表示为(AOA_r,d_r,d_r)。

由于聚类点r的位置和基站的位置都已知，因此，聚类点r与基站的距离d_r可以计算得到。

步骤603：基站分别计算待测终端i与任一聚类点r之间的AOA距离

$l_{\mathrm{AOA}}^r=|{\mathrm{AOA}}_i-A{\mathrm{OA}}_r|(((d_{{\mathrm{SNR}}_i}+d_{{\mathrm{TOA}}_i})/2+d_r)/2)$

步骤604：基站分别计算待测终端i的测量位置数据与历史数据库中的任一聚类点r的位置数据之间的欧式距离，寻找欧式距离最小的聚类点s。

待测终端i的测量位置数据与任一聚类点r的位置数据间的欧氏距离的计算公式如下：

$\mathrm{\ϵ}={l_{\mathrm{AOA}}^r}^2+{(d_{{\mathrm{SNR}}_i}-d_r)}^2+{(d_{{\mathrm{TOA}}_i}-d_r)}^2$

步骤605：基站令α＝AOA_i-AOA_s，将聚类点s的物理坐标旋转α，得到新的物理坐标(x_ui,y_ui)，即为待测终端i的初始估计位置，其中：

x_ui＝x_s·cosα-y_s·sinα

y_ui＝x_s·sinα+y_s·cosα

图7给出了根据匹配聚类点的位置确定待测终端位置的示意图。

本步骤605中，将聚类点s的物理坐标旋转α的目的是为了将待测终端i的初始位置估计得更为准确。在实际应用中，也可直接将(x_s,y_s)作为待测终端i的初始估计位置。

以下给出上述步骤503的具体实施方式：

图8为本发明实施例提供的根据待测终端的初始估计位置和待测终端两两之间的距离，采用和积算法获得待测终端的最终估计位置的方法流程图，如图8所示，其具体步骤如下：

步骤801：设小区内共有N个待测终端，对于任一待测终端i，设待测终端i的位置分布服从以初始估计位置(x_ui,y_ui)为中心的二维高斯分布，则待测终端i的初始位置概率分布P_i(x,y)可以表示为：

$P_i(x,y)=\frac{1}{{2\mathrm{\π\σ}}^2}\exp \{-\frac{{(x-x_{\mathrm{ui}})}^2+{(y-y_{\mathrm{ui}})}^2}{{2\mathrm{\σ}}^2}\}$

其中，σ的取值可根据需要和经验确定。

例如：若待测终端i的初始估计位置为（5，8），则待测终端i的初始位置概率分布P_i(x,y)如图9所示。

步骤802：基站初始化迭代次数q＝0，对于任一待测终端i，初始化待测终端i的位置概率分布，即，令

步骤803：基站计算本次迭代过程中任一其它待测终端k对待测终端i的位置概率分布的更新值

其中，(s,t)为待测终端k的物理坐标，(s,t)的取值范围与小区的覆盖范围相同，为待测终端k第q-1次迭代后的位置概率分布，

$p\left(d_{\mathrm{ik}}\right|(x,y),(s,t))=\frac{1}{{2\mathrm{\π\σ}}^2}\exp \{-\frac{{(d_{\mathrm{ik}}-\sqrt{{(x-s)}^2+{(y-t)}^2})}^2}{2{\mathrm{\σ}}^2}\}$

该公式的物理意义为：当待测终端k在物理位置(s,t)上时，待测终端i在物理位置(x,y)上的概率。表示：以待测终端k第q-1次迭代后的位置概率分布对待测终端i的位置概率分布的更新值。

步骤804：基站根据待测终端i的初始位置概率分布P_i(x,y)以及本次迭代过程中其它待测终端对待测终端i的位置概率分布的更新值，得到待测终端i的最新位置概率分布

$b_i^{\left(q\right)}(x,y)=p_i(x,y)\·\underset{k\≠i}{\mathrm{\Π}}{u}_{k->i}^{\left(q\right)}(x,y)$

步骤805：基站判断迭代次数q是否小于预定次数Q，若是，令q=q+1，返回步骤803，继续下一次迭代过程；否则，执行步骤806。

Q的取值可根据经验确定。

步骤806：基站确定待测终端i的最终位置概率分布为：则待测终端i的最终估计位置为：

$\begin{array}{c}{\hat{x}}_i=\underset{x,y}{\mathrm{\Σ}}x\·P_i^{\′}(x,y)\\ {\hat{y}}_i=\underset{x,y}{\mathrm{\Σ}}y\·P_i^{\′}(x,y)\end{array}$ 其中，(x,y)的取值范围与小区的覆盖范围相同。

在得到待测终端i的最终估计位置后，将待测终端i作为新的样本点，采用图2所示实施例，与已有样本点重新进行聚类以更新历史数据库。

图10给出了一个根据待测终端的初始估计位置和待测终端两两之间的距离，采用和积算法获得待测终端的最终估计位置的示意图，其中，P_i,i＝0,1,...,N-1为待测终端i的初始位置概率分布，为第q次迭代后待测终端i的位置概率分布，为第q次迭代过程中待测终端k的传递给待测终端i的的更新值。每次迭代时，两两待测终端间相互传递这样的更新值，结合各终端自己的初始位置概率分布P_i，得到新的更加准确的位置概率分布。例如：对于图10中的待测终端1，第一次迭代时，其它任一待测终端k的传递给待测终端1的更新值为这样待测终端1第一次迭代后的位置概率分布不仅包括了自己的初始位置概率分布，也包括了其它待测终端的传递给它的更新值，从而可以获得更加准确的结果，然后再进行第二次迭代，由于其它待测终端的概率分布经过迭代也更加准确了，传递给待测终端1的更新值也更加准确，待测终端1第二次迭代的结果相比第一次就更加准确了。如此迭代若干次后，各个待测终端即可充分利用其它待测终端的信息，获得较准确的结果，从而达到协作定位的目的。

图11为本发明实施例提供的终端定位装置的组成图，如图11所示，其主要包括：历史数据建立单元111、初始位置估计单元112、最终位置估计单元113和历史数据库单元114，其中：

历史数据建立单元111：对于任一小区，在小区中设置第一预设数目个聚类终端，获取每个聚类终端的位置数据：AOA、TOA、SNR和物理坐标，将每个聚类终端的位置数据放入历史数据库单元114。

初始位置估计单元112：对于任一待测终端，测量该待测终端的AOA、TOA和SNR，根据该待测终端的AOA、TOA和SNR，在历史数据库单元114中查找与该待测终端最匹配的聚类终端，根据该聚类终端的物理坐标确定该待测终端的初始估计位置，将该待测终端的初始估计位置发送给最终位置估计单元113。

最终位置估计单元113：根据初始位置估计单元112发来的待测终端的初始估计位置和该待测终端与其它待测终端之间的距离，计算该待测终端的最终位置。

在实际应用中，历史数据建立单元111可包括：第一模块和第二模块，其中：

第一模块：在小区中设置第一预设数目个初始聚类终端，并设置第二预设数目个样本终端。

第二模块：初始化迭代次数为0；对于每个样本终端，寻找与该样本终端最近的聚类终端，将该样本终端归属于该聚类终端，将归属于同一聚类终端的所有样本终端作为一聚类群，将每个聚类群的质心作为一个新聚类终端，计算当前迭代得到的所有新聚类终端的物理坐标与上一次迭代得到的所有聚类终端的物理坐标的均方误差；若均方误差小于预设值，则确定聚类完成；否则，返回执行所述对于每个样本终端，寻找与该样本终端最近的聚类终端的动作。

在实际应用中，最终位置估计单元113进一步用于，当计算出该待测终端的最终位置后，将该待测终端的位置数据：AOA、TOA、SNR及物理坐标发送给历史数据建立单元111；

且，历史数据建立单元111接收到最终位置估计单元113发来的待测终端的位置数据后，将该待测终端作为新的样本终端，重新对所有样本终端进行聚类，聚类完成，以得到的各新聚类终端的位置数据：AOA、TOA、SNR和物理坐标更新历史数据库单元114中的历史数据。

在实际应用中，初始位置估计单元112可包括：第三模块和第四模块，其中：

第三模块：对于任一待测终端，测量该待测终端的AOA、TOA和SNR，将该待测终端的AOA、TOA和SNR发送给第四模块。

第四模块：根据第三模块发来的待测终端的AOA、TOA和SNR，在历史数据库单元114中查找与该待测终端的欧式距离最小的聚类终端，计算所述待测终端的AOA与所述聚类终端的AOA之差α，将该聚类终端的物理坐标旋转α，将旋转后得到的物理坐标作为所述待测终端的初始估计位置。

在实际应用中，最终位置估计单元113可包括：第五模块和第六模块，其中：

第五模块：计算待测终端与任一其它待测终端间的距离，将计算得到的各距离发送给第六模块。

第六模块：接收初始位置估计单元112发来的待测终端的初始估计位置，设所述待测终端的位置分布服从以初始估计位置为中心的二维高斯分布，则根据所述待测终端的初始估计位置确定该待测终端的初始位置概率分布；初始化迭次次数为0；根据所述待测终端与任一其它待测终端间的距离，计算本次迭代过程中任一其它待测终端对所述待测终端的位置概率分布的更新值；根据所述待测终端的初始位置概率分布以及本次迭代过程中其它待测终端对所述待测终端的位置概率分布的更新值，得到所述待测终端的最新位置概率分布；判断迭代次数是否小于预定次数，若是，返回执行所述计算本次迭代过程中任一其它待测终端对所述待测终端的位置概率分布的更新值的动作，继续下一次迭代过程；否则，将待测终端的最新位置概率分布作为其最终位置概率分布，根据该最终位置概率分布计算所述待测终端的最终位置。

其中，第五模块可包括：第一子模块、第二子模块和第三模块，其中：

第一子模块：计算β＝AOA_i-AOA_k，其中，AOA_i为所述待测终端的AOA，AOA_k为所述任一其它待测终端的AOA，将β发送给第三子模块。

第二子模块：计算所述待测终端与基站的距离计算所述任一其它待测终端与基站的距离其中，为根据SNR_i计算到的所述待测终端与基站的距离，为根据TOA_i计算到的所述待测终端与基站的距离，为根据SNR_k计算到的所述任一其它待测终端与基站的距离，为根据TOA_k计算到的所述任一其它待测终端与基站的距离，将d_i、d_k发送给第三子模块。

第三子模块：计算所述待测终端与所述任一其它待测终端间的距离d_ik：

$d_{\mathrm{ik}}=\sqrt{d_i^2+d_k^2-2d_i{d}_k\·\cos \mathrm{\β}}.$

本发明实施例中的终端定位装置可位于基站上。

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

Claims (16)

1.一种终端定位方法，其特征在于，该方法包括：

对于任一小区，在小区中设置第一预设数目个聚类终端，获取每个聚类终端的位置数据：到达角AOA、到达时间TOA、信噪比SNR和物理坐标，将每个聚类终端的位置数据放入历史数据库；

对于任一待测终端，测量该待测终端的AOA、TOA和SNR，根据该待测终端的AOA、TOA和SNR，在历史数据库中查找与该待测终端最匹配的聚类终端，根据该聚类终端的物理坐标确定该待测终端的初始估计位置；

根据待测终端的初始估计位置和该待测终端与其它待测终端之间的距离，计算该待测终端的最终位置。

2.根据权利要求1所述的方法，其特征在于，所述在小区中设置第一预设数目个聚类终端，获取每个聚类终端的位置数据：到达角AOA、到达时间TOA、信噪比SNR和物理坐标，将每个聚类终端的位置数据放入历史数据库包括：

在小区中设置第一预设数目个初始聚类终端，并设置第二预设数目个样本终端；

根据样本终端与聚类终端的距离，对所有样本终端进行聚类，聚类完成，得到第一预设数目个新聚类终端，计算每个新聚类终端的位置数据：AOA、TOA、SNR和物理坐标，将每个新聚类终端的位置数据放入历史数据库。

3.根据权利要求2所述的方法，其特征在于，所述根据样本终端与聚类终端的距离，对所有样本终端进行聚类包括：

初始化迭代次数为0；

对于每个样本终端，寻找与该样本终端最近的聚类终端，将该样本终端归属于该聚类终端，将归属于同一聚类终端的所有样本终端作为一聚类群，将每个聚类群的质心作为一个新聚类终端，计算当前迭代得到的所有新聚类终端的物理坐标与上一次迭代得到的所有聚类终端的物理坐标的均方误差；若均方误差小于预设值，则确定聚类完成；否则，返回执行所述对于每个样本终端，寻找与该样本终端最近的聚类终端的动作。

4.根据权利要求2所述的方法，其特征在于，所述在小区中设置第一预设数目个初始聚类终端为：

将小区均匀划分为第一预设数目个子区域，将每个子区域的中心作为一个初始聚类终端所在位置。

5.根据权利要求2所述的方法，其特征在于，所述计算该待测终端的最终位置之后进一步包括：

当计算出该待测终端的最终位置后，将该待测终端作为新的样本终端，与已有样本终端进行聚类，聚类完成，以得到的各新聚类终端的位置数据更新历史数据库，所述新聚类终端的位置数据包括：AOA、TOA、SNR和物理坐标。

6.根据权利要求1所述的方法，其特征在于，所述根据该待测终端的AOA、TOA和SNR，在历史数据库中查找与该待测终端最匹配的聚类终端包括：

根据该待测终端的AOA、TOA和SNR，在历史数据库中查找与该待测终端的欧式距离最小的聚类终端；

所述根据该聚类终端的物理坐标确定该待测终端的初始估计位置为：

计算所述待测终端的AOA与所述聚类终端的AOA之差α，将该聚类终端的物理坐标旋转α，将旋转后得到的物理坐标作为所述待测终端的初始估计位置。

7.根据权利要求1所述的方法，其特征在于，所述根据待测终端的初始估计位置和该待测终端与其它待测终端之间的距离，计算该待测终端的最终位置之前进一步包括：

通过如下步骤计算所述待测终端与任一其它待测终端之间的距离：

计算β＝AOA_i-AOA_k，其中，AOA_i为所述待测终端的AOA，AOA_k为所述任一其它待测终端的AOA；

计算所述待测终端与基站的距离计算所述任一其它待测终端与基站的距离其中，为根据SNR_i计算到的所述待测终端与基站的距离，为根据TOA_i计算到的所述待测终端与基站的距离，为根据SNR_k计算到的所述任一其它待测终端与基站的距离，为根据TOA_k计算到的所述任一其它待测终端与基站的距离，SNR_i为所述待测终端的SNR，TOA_i为所述待测终端的TOA，SNR_k为所述任一其它待测终端的SNR，TOA_k为所述任一其它待测终端的TOA；

计算所述待测终端与所述任一其它待测终端间的距离d_ik：

$d_{\mathrm{ik}}=\sqrt{d_i^2+d_k^2-2d_i{d}_k\·\cos \mathrm{\β}}.$

8.根据权利要求1所述的方法，其特征在于，所述根据待测终端的初始估计位置和该待测终端与其它待测终端之间的距离，计算该待测终端的最终位置包括：

设所述待测终端的位置分布服从以初始估计位置为中心的二维高斯分布，则根据所述待测终端的初始估计位置确定该待测终端的初始位置概率分布；

初始化迭代次数为0；

根据所述待测终端与任一其它待测终端之间的距离，计算本次迭代过程中任一其它待测终端对所述待测终端的位置概率分布的更新值；

根据所述待测终端的初始位置概率分布以及本次迭代过程中其它待测终端对所述待测终端的位置概率分布的更新值，得到所述待测终端的最新位置概率分布；

判断迭代次数是否小于预定次数，若是，返回执行所述计算本次迭代过程中任一其它待测终端对所述待测终端的位置概率分布的更新值的动作，继续下一次迭代过程；否则，将待测终端的最新位置概率分布作为其最终位置概率分布，根据该最终位置概率分布计算所述待测终端的最终位置。

9.根据权利要求8所述的方法，其特征在于，所述计算本次迭代过程中任一其它待测终端对所述待测终端的位置概率分布的更新值为：

计算

其中，k为任一其它待测终端的序号，i为所述待测终端的序号，q为当前迭代次数，为本次迭代过程中任一其它待测终端k对所述待测终端i的位置概率分布的更新值，(s,t)为任一其它待测终端k的物理坐标，为任一其它待测终端k在上一次迭代后的位置概率分布；

$p\left(d_{\mathrm{ik}}\right|(x,y),(s,t))=\frac{1}{{2\mathrm{\π\σ}}^2}\exp \{-\frac{{(d_{\mathrm{ik}}-\sqrt{{(x-s)}^2+{(y-t)}^2})}^2}{2{\mathrm{\σ}}^2}\}$

该公式的物理意义为：当所述任一其它待测终端k在物理位置(s,t)上时，所述待测终端i在物理位置(x,y)上的概率；d_ik为所述任一其它待测终端k与所述待测终端i间的距离；

所述根据所述待测终端的初始位置概率分布以及本次迭代过程中其它待测终端对所述待测终端的位置概率分布的更新值，得到所述待测终端的最新位置概率分布为：

其中，p_i(x,y)为所述待测终端的初始位置概率分布；

所述根据该最终位置概率分布计算所述待测终端的最终位置为：

${\hat{x}}_i=\underset{x,y}{\mathrm{\Σ}}x\·P_i^{\′}(x,y)$

${\hat{y}}_i=\underset{x,y}{\mathrm{\Σ}}y\·P_i^{\′}(x,y)$

其中，(x,y)的取值范围为小区的覆盖区域。

10.一种终端定位装置，其特征在于，该装置包括：

历史数据建立单元：对于任一小区，在小区中设置第一预设数目个聚类终端，获取每个聚类终端的位置数据：到达角AOA、到达时间TOA、信噪比SNR和物理坐标，将每个聚类终端的位置数据放入历史数据库；

初始位置估计单元：对于任一待测终端，测量该待测终端的AOA、TOA和SNR，根据该待测终端的AOA、TOA和SNR，在历史数据库中查找与该待测终端最匹配的聚类终端，根据该聚类终端的物理坐标确定该待测终端的初始估计位置，将该待测终端的初始估计位置发送给最终位置估计单元；

最终位置估计单元：根据待测终端的初始估计位置和该待测终端与其它待测终端之间的距离，计算该待测终端的最终位置。

11.根据权利要求10所述的装置，其特征在于，所述历史数据建立单元包括：

第一模块：在小区中设置第一预设数目个初始聚类终端，并设置第二预设数目个样本终端；

第二模块：初始化迭代次数为0；对于每个样本终端，寻找与该样本终端最近的聚类终端，将该样本终端归属于该聚类终端，将归属于同一聚类终端的所有样本终端作为一聚类群，将每个聚类群的质心作为一个新聚类终端，计算当前迭代得到的所有新聚类终端的物理坐标与上一次迭代得到的所有聚类终端的物理坐标的均方误差；若均方误差小于预设值，则确定聚类完成；否则，返回执行所述对于每个样本终端，寻找与该样本终端最近的聚类终端的动作。

12.根据权利要求11所述的装置，其特征在于，所述最终位置估计单元进一步用于，当计算出该待测终端的最终位置后，将该待测终端的位置数据发送给历史数据建立单元，所述待测终端的位置数据包括：AOA、TOA、SNR及物理坐标；

所述历史数据建立单元接收到所述待测终端的位置数据后，将该待测终端作为新的样本终端，重新对所有样本终端进行聚类，聚类完成，以得到的各新聚类终端的位置数据更新历史数据库，所述新聚类终端的位置数据包括：AOA、TOA、SNR和物理坐标。

13.根据权利要求10所述的装置，其特征在于，所述初始位置估计单元包括：

第三模块：对于任一待测终端，测量该待测终端的AOA、TOA和SNR；

第四模块：根据该待测终端的AOA、TOA和SNR，在历史数据库中查找与该待测终端的欧式距离最小的聚类终端，计算所述待测终端的AOA与所述聚类终端的AOA之差α，将该聚类终端的物理坐标旋转α，将旋转后得到的物理坐标作为所述待测终端的初始估计位置。

14.根据权利要求10所述的装置，其特征在于，所述最终位置估计单元包括：

第五模块：计算所述待测终端与任一其它待测终端间的距离，将计算得到的各距离发送给第六模块；

第六模块：设所述待测终端的位置分布服从以初始估计位置为中心的二维高斯分布，则根据所述待测终端的初始估计位置确定该待测终端的初始位置概率分布；初始化迭次次数为0；根据所述待测终端与任一其它待测终端间的距离，计算本次迭代过程中任一其它待测终端对所述待测终端的位置概率分布的更新值；根据所述待测终端的初始位置概率分布以及本次迭代过程中其它待测终端对所述待测终端的位置概率分布的更新值，得到所述待测终端的最新位置概率分布；判断迭代次数是否小于预定次数，若是，返回执行所述计算本次迭代过程中任一其它待测终端对所述待测终端的位置概率分布的更新值的动作，继续下一次迭代过程；否则，将待测终端的最新位置概率分布作为其最终位置概率分布，根据该最终位置概率分布计算所述待测终端的最终位置。

15.根据权利要求14所述的装置，其特征在于，所述第五模块包括：

第一子模块：计算β＝AOA_i-AOA_k，其中，AOA_i为所述待测终端的AOA，AOA_k为所述任一其它待测终端的AOA，将β发送给第三子模块；

第二子模块：计算所述待测终端与基站的距离计算所述任一其它待测终端与基站的距离其中，为根据SNR_i计算到的所述待测终端与基站的距离，为根据TOA_i计算到的所述待测终端与基站的距离，为根据SNR_k计算到的所述任一其它待测终端与基站的距离，为根据TOA_k计算到的所述任一其它待测终端与基站的距离，将d_i、d_k发送给第三子模块；

第三子模块：计算所述待测终端与所述任一其它待测终端间的距离d_ik：

$d_{\mathrm{ik}}=\sqrt{d_i^2+d_k^2-2d_i{d}_k\·\cos \mathrm{\β}}.$

16.根据权利要求10至15任一所述的装置，其特征在于，所述装置位于基站上。