快速定位方法及系统

1.一种快速定位方法，其特征在于，包括：
接收移动终端的定位请求，所述定位请求中包含所述移动终端当前的信号强度值；
检查所述移动终端当前的信号强度值是否包含在根据其它移动终端上报的位置信息聚类得到的位置记录表中，所述位置记录表中包含信号强度值、以及与所述信号强度值对应的位置信息；
如果所述移动终端当前的信号强度值包含在所述位置记录表中，则从所述位置记录表中获取对应所述信号强度值的位置信息；
将所述位置信息发送给所述移动终端；
所述方法还包括：
接收其它移动终端上报的信号强度值与位置数据；
对接收到的位置数据中具有相同信号强度值的位置数据进行聚类处理，得到所述位置记录表；
所述对接收到的位置数据中具有相同信号强度值的位置数据进行聚类处理，得到所述位置记录表包括：
采用基于密度的聚类算法对接收到的位置数据中具有相同信号强度值的位置数据进行聚类处理，得到对应不同信号强度值的聚类；
采用最小覆盖圆算法确定各聚类的圆心的坐标及半径；
将所述圆心的坐标作为与所述信号强度值对应的位置数据，所述半径作为与所述信号强度值对应的误差范围，并与对应的所述信号强度值一起保存到所述位置记录表中。
2.如权利要求1所述的方法，其特征在于，所述方法还包括：
在对接收到的位置数据中具有相同信号强度值的位置数据进行聚类处理之前，将接收到的信号强度值与位置数据保存到初始历史数据表中；
在所述初始历史数据表中新的位置数据的个数达到第一阈值后，对所述初始历史数据表中新的位置数据进行筛选，得到筛选后历史数据表；
所述对接收到的位置数据中具有相同信号强度值的位置数据进行聚类处理包括：
对所述筛选后历史数据表中具有相同信号强度值的位置数据进行聚类处理；
所述对所述初始历史数据表中的数据进行筛选，得到筛选后历史数据表包括：
删除所述初始历史数据表中重复的数据；
如果删除后剩余的数据达到了基站所需的数量阈值，则对所述剩余的数据进行精炼处理，并将精炼处理后的数据存入所述筛选后历史数据表中；
所述对所述剩余的数据进行精炼处理包括：
根据时间及距离门限确定用户历史位置记录中的逗留点，所述逗留点为用户在一特定区域移动时的中心位置；
用逗留点代替其他的冗余位置数据。
3.如权利要求2所述的方法，其特征在于，所述方法还包括：
如果所述移动终端当前的信号强度值未包含在所述位置记录表中，则检查所述移动终端当前的信号强度值是否包含在所述初始历史数据表中；
如果否，则将基站的位置信息发送给所述移动终端，所述基站的位置信息包括基站坐标值及基站的覆盖半径；
如果是，则从所述初始历史数据表中获取与所述信号强度值对应的离散位置数据；
采用最小覆盖圆算法确定所述离散位置数据的最小覆盖圆；
将所述最小覆盖圆的圆心及半径分别作为所述移动终端的位置数据及误差范围发送给所述移动终端。
4.一种快速定位系统，其特征在于，包括：
报文接收单元，用于接收移动终端的定位请求，所述定位请求中包含所述移动终端当前的信号强度值；
第一检查单元，用于检查所述移动终端当前的信号强度值是否包含在根据其它移动终端上报的位置信息聚类得到的位置记录表中，所述位置记录表中包含信号强度值、以及与所述信号强度值对应的位置信息；
定位结果获取单元，用于在所述第一检查单元的检查结果为所述移动终端当前的信号强度值包含在所述位置记录表时，从所述位置记录表中获取对应所述信号强度值的位置信息；
发送单元，用于将所述定位结果获取单元获取的位置信息发送给所述移动终端；
所述报文接收单元，还用于接收其它移动终端上报的信号强度值与位置数据；
所述系统还包括：
聚类处理单元，用于对接收到的位置数据中具有相同信号强度值的位置数据进行聚类处理，得到所述位置记录表；
所述聚类处理单元包括：
聚类子单元，用于采用基于密度的聚类算法对接收到的位置数据中具有相同信号强度值的位置数据进行聚类处理，得到对应不同信号强度值的聚类；
误差估计子单元，用于采用最小覆盖圆算法确定各聚类的圆心的坐标及半径；
位置记录表生成子单元，用于将所述圆心的坐标作为与所述信号强度值对应的位置数据，将所述半径作为与所述信号强度值对应的误差范围，并与对应的所述信号强度值一起保存到所述位置记录表中。
5.如权利要求4所述的系统，其特征在于，所述系统还包括：
初始历史数据存储单元，用于在所述聚类处理单元对接收到的位置数据中具有相同信号强度值的位置数据进行聚类处理之前，将接收到的信号强度值与位置数据保存到初始历史数据表中；
筛选单元，用于在所述初始历史数据表中新的位置数据的个数达到第一阈值后，对所述初始历史数据表中新的位置数据进行筛选，得到筛选后历史数据表；
所述聚类处理单元，具体用于对所述筛选后历史数据表中具有相同信号强度值的位置数据进行聚类处理；
所述筛选单元包括：
删除子单元，用于删除所述初始历史数据表中重复的数据；
精炼处理子单元，用于在所述删除后剩余的数据达到了基站所需的数量阈值后，对所述剩余的数据进行精炼处理，并将精炼处理后的数据存入所述筛选后历史数据表中；
所述精炼处理子单元包括：
逗留点确定子单元，用于根据时间及距离门限确定用户历史位置记录中的逗留点，所述逗留点为用户在一特定区域移动时的中心位置；
筛选后历史数据存储单元，用于用所述逗留点代替其它的冗余位置数据，生成筛选后历史数据表。
6.如权利要求5所述的系统，其特征在于，所述系统还包括：
第二检查单元，用于在所述第一检查单元的检查结果为所述移动终端当前的信号强度值未包含在所述位置记录表时，检查所述移动终端当前的信号强度值是否包含在所述初始历史数据表中；
计算单元，用于在所述第二检查单元的检查结果为所述移动终端当前的信号强度值包含在所述初始历史数据表中时，从所述初始历史数据表中获取与所述信号强度值对应的离散位置数据，并采用最小覆盖圆算法确定所述离散位置数据的最小覆盖圆，将所述最小覆盖圆的圆心的坐标及半径分别作为所述移动终端的位置数据及误差范围传送给所述定位结果获取单元；
所述定位结果获取单元，还用于在所述第二检查单元的检查结果为所述移动终端当前的信号强度值未包含在所述初始历史数据表中时，获取基站的位置信息，所述基站的位置信息包括基站坐标值及基站的覆盖半径；
所述发送单元，还用于将所述基站的位置信息发送给所述移动终端，以及将所述计算单元传送给所述定位结果获取单元的移动终端的位置数据及误差范围发送给所述移动终端。
7.一种快速定位系统，其特征在于，包括：网络适配处理模块、历史位置数据处理模块、数据预处理模块、聚类处理模块和定位处理模块；
所述网络适配处理模块，用于接收移动终端发送的报文，并判断所述报文的类型，如果所述报文是定位请求报文，则将所述报文转发至所述定位处理模块；如果所述报文是移动终端上报的信号强度值与位置数据，则将所述报文转发至所述历史位置数据处理模块；
所述历史位置数据处理模块，用于将接收到的信号强度值与位置数据保存到初始历史数据表中；
所述数据预处理模块，用于调用所述初始历史数据表，对所述初始历史数据表中的数据进行预处理，生成筛选后历史数据表；
所述聚类处理模块，用于对所述筛选后历史数据表中的历史位置数据进行聚类处理，生成包含信号强度值及与所述信号强度值对应的位置信息的位置记录表；
所述定位处理模块，用于在接收到所述定位请求报文后，根据所述定位请求报文中的信号强度值，以及所述位置记录表、所述初始历史数据表、基站位置数据确定所述移动终端的位置信息，并将确定的位置信息返回给所述移动终端。

快速定位方法及系统\n技术领域\n[0001] 本发明涉及移动通信系统中的定位技术领域，更具体地说，涉及一种快速定位方法及系统。\n背景技术\n[0002] 随着移动通信系统和地理信息系统的发展，利用移动通信技术为手机用户提供基于位置的服务有着极为广阔的市场前景。目前，移动终端用户定位的方法主要有两种：\n[0003] 一种是使用GPS(Global Positioning System，全球定位系统)技术进行定位。但该技术需要在移动终端上安装GPS接收单元，这会导致移动终端电池消耗及用户成本的增加，而且在城市环境，受到建筑物阻挡及定位物体高速运动等影响，目前的GPS定位并不能满足随时随地快速定位需求。\n[0004] 另一种则是使用运营商网络提供的基站定位技术。在这种方案中，任意移动终端用户只要进入基站服务区域都能获得基站的位置坐标，并将它作为当前移动终端用户的参考坐标。由于基站一般由运营商事先进行部署，使得基站定位技术受到运营商的广泛欢迎，但由于基站覆盖范围较大，这种定位技术具有较大的误差范围，难以满足移动终端用户精准定位的需求。因此，对于移动通信运营商而言，如何以较低的成本为移动终端用户提供快速、准确的定位服务是基于位置的服务业务应用和普及的关键。\n发明内容\n[0005] 本发明实施例针对现有技术中存在的上述问题，提供一种快速定位方法及系统，无需移动终端增加任何额外定位设施，并提高定位速度和定位精度。\n[0006] 为此，本发明实施例提供如下技术方案：\n[0007] 一种快速定位方法，包括：\n[0008] 接收移动终端的定位请求，所述定位请求中包含所述移动终端当前的信号强度值；\n[0009] 检查所述移动终端当前的信号强度值是否包含在根据其它移动终端上报的位置信息聚类得到的位置记录表中，所述位置记录表中包含信号强度值、以及与所述信号强度对应的位置信息；\n[0010] 如果所述移动终端当前的信号强度值包含在所述位置记录表中，则从所述位置记录表中获取对应所述信号强度值的位置信息；\n[0011] 将所述位置信息发送给所述移动终端。\n[0012] 优选地，所述方法还包括：\n[0013] 接收其它移动终端上报的信号强度值与位置数据；\n[0014] 对接收到的位置数据中具有相同信号强度值的位置数据进行聚类处理，得到所述位置记录表。\n[0015] 优选地，所述对接收到的位置数据中具有相同信号强度值的位置数据进行聚类处理，得到所述位置记录表包括：\n[0016] 采用基于密度的聚类算法对接收到的位置数据中具有相同信号强度值的位置数据进行聚类处理，得到对应不同信号强度值的聚类；\n[0017] 采用最小覆盖圆算法确定各聚类的圆心的坐标及半径；\n[0018] 将所述圆心的坐标作为与所述信号强度值对应的位置数据，所述半径作为与所述信号强度值对应的误差范围，并与对应的所述信号强度值一起保存到所述位置记录表中。\n[0019] 优选地，所述方法还包括：\n[0020] 在对接收到的位置数据中具有相同信号强度值的位置数据进行聚类处理之前，将接收到的信号强度值与位置数据保存到初始历史数据表中；\n[0021] 在所述初始历史数据表中新的位置数据的个数达到第一阈值后，对所述初始历史数据表中新的位置数据进行筛选，得到筛选后历史数据表；\n[0022] 所述对接收到的位置数据中具有相同信号强度值的位置数据进行聚类处理包括：\n[0023] 对所述筛选后历史数据表中具有相同信号强度值的位置数据进行聚类处理；\n[0024] 所述对所述初始历史数据表中的数据进行筛选，得到筛选后历史数据表包括：\n[0025] 删除所述初始历史数据表中重复的数据；\n[0026] 如果删除后剩余的数据达到了基站所需的数量阈值，则对所述剩余的数据进行精炼处理，并将精炼处理后的数据存入所述筛选后历史数据表中；\n[0027] 所述对所述剩余的数据进行精炼处理包括：\n[0028] 根据时间及距离门限确定用户历史位置记录中的逗留点，所述逗留点为用户在一特定区域移动时的中心位置；\n[0029] 用逗留点代替其他的冗余位置数据。\n[0030] 优选地，所述方法还包括：\n[0031] 如果所述移动终端当前的信号强度值未包含在所述位置记录表中，则检查所述移动终端当前的信号强度值是否包含在所述初始历史数据表中；\n[0032] 如果否，则将基站的位置信息发送给所述移动终端，所述基站的位置信息包括基站坐标值及基站的覆盖半径；\n[0033] 如果是，则从所述初始历史数据表中获取与所述信号强度值对应的离散位置数据；\n[0034] 采用最小覆盖圆算法确定所述离散位置数据的最小覆盖圆；\n[0035] 将所述最小覆盖圆的圆心及半径分别作为所述移动终端的位置数据及误差范围发送给所述移动终端。\n[0036] 一种快速定位系统，其特征在于，包括：\n[0037] 报文接收单元，用于接收移动终端的定位请求，所述定位请求中包含所述移动终端当前的信号强度值；\n[0038] 第一检查单元，用于检查所述移动终端当前的信号强度值是否包含在根据其它移动终端上报的位置信息聚类得到的位置记录表中，所述位置记录表中包含信号强度值、以及与所述信号强度对应的位置信息；\n[0039] 定位结果获取单元，用于在所述第一检查单元的检查结果为所述移动终端当前的信号强度值包含在所述位置记录表时，从所述位置记录表中获取对应所述信号强度值的位置信息；\n[0040] 发送单元，用于将所述定位结果获取单元获取的位置信息发送给所述移动终端。\n[0041] 优选地，所述报文接收单元，还用于接收其它移动终端上报的信号强度值与位置数据；\n[0042] 所述系统还包括：\n[0043] 聚类处理单元，用于对接收到的位置数据中具有相同信号强度值的位置数据进行聚类处理，得到所述位置记录表。\n[0044] 优选地，所述聚类处理单元包括：\n[0045] 聚类子单元，用于采用基于密度的聚类算法对接收到的位置数据中具有相同信号强度值的位置数据进行聚类处理，得到对应不同信号强度值的聚类；\n[0046] 误差估计子单元，用于采用最小覆盖圆算法确定各聚类的圆心的坐标及半径；\n[0047] 位置记录表生成子单元，用于将所述圆心的坐标作为与所述信号强度值对应的位置数据，将所述半径作为与所述信号强度值对应的误差范围，并与对应的所述信号强度值一起保存到所述位置记录表中。\n[0048] 优选地，所述系统还包括：\n[0049] 初始历史数据存储单元，用于在所述聚类处理单元对接收到的位置数据中具有相同信号强度值的位置数据进行聚类处理之前，将接收到的信号强度值与位置数据保存到初始历史数据表中；\n[0050] 筛选单元，用于在所述初始历史数据表中新的位置数据的个数达到第一阈值后，对所述初始历史数据表中新的位置数据进行筛选，得到筛选后历史数据表；\n[0051] 所述聚类处理单元，具体用于对所述筛选后历史数据表中具有相同信号强度值的位置数据进行聚类处理；\n[0052] 所述筛选单元包括：\n[0053] 删除子单元，用于删除所述初始历史数据表中重复的数据；\n[0054] 精炼处理子单元，用于在所述删除后剩余的数据达到了基站所需的数量阈值后，对所述剩余的数据进行精炼处理，并将精炼处理后的数据存入所述筛选后历史数据表中；\n[0055] 所述精炼处理子单元包括：\n[0056] 逗留点确定子单元，用于根据时间及距离门限确定用户历史位置记录中的逗留点，所述逗留点为用户在一特定区域移动时的中心位置；\n[0057] 筛选后历史数据存储单元，用于用所述逗留点代替其它的冗余位置数据，生成筛选后历史数据表。\n[0058] 优选地，所述系统还包括：\n[0059] 第二检查单元，用于在所述第一检查单元的检查结果为所述移动终端当前的信号强度值未包含在所述位置记录表时，检查所述移动终端当前的信号强度值是否包含在所述初始历史数据表中；\n[0060] 计算单元，用于在所述第二检查单元的检查结果为所述移动终端当前的信号强度值包含在所述初始历史数据表中时，从所述初始历史数据表中获取与所述信号强度值对应的离散位置数据，并采用最小覆盖圆算法确定所述离散位置数据的最小覆盖圆，将所述最小覆盖圆的圆心的坐标及半径分别作为所述移动终端的位置数据及误差范围传送给所述定位结果获取单元；\n[0061] 所述定位结果获取单元，还用于在所述第二检查单元的检查结果为所述移动终端当前的信号强度值未包含在所述初始历史数据表中时，获取基站的位置信息，所述基站的位置信息包括基站坐标值及基站的覆盖半径；\n[0062] 所述发送单元，还用于将所述基站的位置信息发送给所述移动终端，以及将所述计算单元传送给所述定位结果获取单元的移动终端的位置数据及误差范围发送给所述移动终端。\n[0063] 一种快速定位系统，包括：网络适配处理模块、历史位置数据处理模块、数据预处理模块、聚类处理模块和定位处理模块；\n[0064] 所述网络适配处理模块，用于接收移动终端发送的报文，并判断所述报文的类型，如果所述报文是定位请求报文，则将所述报文转发至所述定位处理模块；如果所述报文是移动终端上报的信号强度值与位置数据，则将所述报文转发至所述历史位置数据处理模块；\n[0065] 所述历史位置数据处理模块，用于将接收到的信号强度值与位置数据保存到初始历史数据表中；\n[0066] 所述数据预处理模块，用于调用所述初始历史数据表，对所述初始历史数据表中的数据进行预处理，生成筛选后历史数据表；\n[0067] 所述聚类处理模块，用于对所述筛选后历史数据表中的历史位置数据进行聚类处理，生成包含信号强度值及与所述信号强度值对应的位置信息的位置记录表；\n[0068] 所述定位处理模块，用于在接收到所述定位请求报文后，根据所述定位请求报文中的信号强度值，以及所述位置记录表、所述初始历史数据表、基站位置数据确定所述移动终端的位置信息，并将确定的位置信息返回给所述移动终端。\n[0069] 本发明实施例快速定位方法及系统，由基站对用户的历史位置数据进行聚类处理，动态生成包含有信号强度值、以及与所述信号强度对应的位置信息的位置记录表，从而在接收到移动终端的定位请求后，可以快速向所述移动终端返回定位结果，所述定位结果不仅包含位置数据，而且还可进一步包含对应该位置数据的误差范围，有效地提高了定位的精度。\n附图说明\n[0070] 图1是本发明实施例快速定位方法的一种流程图；\n[0071] 图2是本发明实施例中利用最小覆盖圆算法确定聚类中心的流程图；\n[0072] 图3是本发明实施例中对位置数据进行精炼处理的流程图；\n[0073] 图4是本发明实施例快速定位方法的另一种流程图；\n[0074] 图5是本发明实施例快速定位系统的一种结构示意图；\n[0075] 图6是本发明实施例快速定位系统的另一种结构示意图；\n[0076] 图7是本发明实施例快速定位系统的另一种结构示意图；\n[0077] 图8是本发明实施例快速定位系统的一种实际应用结构示意图。\n具体实施方式\n[0078] 为了使本技术领域的人员更好地理解本发明实施例的方案，下面结合附图和实施方式对本发明实施例作进一步的详细说明。\n[0079] 本发明实施例快速定位方法及系统，为了实现对移动终端的快速准确定位，由基站对用户的历史位置数据进行聚类处理，动态生成包含有信号强度值、以及与所述信号强度对应的位置信息的位置记录表，从而在接收到移动终端的定位请求后，可以快速向所述移动终端返回定位结果，所述定位结果不仅包含位置数据，而且还可进一步包含对应该位置数据的误差范围，有效地提高了定位的精度。\n[0080] 如图1所示，是本发明实施例快速定位方法的一种流程图，包括以下步骤：\n[0081] 步骤101，接收移动终端的定位请求，所述定位请求中包含所述移动终端当前的信号强度值。\n[0082] 在所述定位请求中还可以包含以下信息：IMEI(International Mobile Equipment Identity，国际移动设备身份码)、IMSI(International Mobile Subscriber Identification Number，国际移动用户识别码)、MCC(Mobile Country Code，移动国家码)、MNC(Mobile Network Code，移动网络识别码)、LAC(Location Area Code，位置区域码)、CellID(小区标识)等信息。\n[0083] 步骤102，检查所述移动终端当前的信号强度值是否包含在根据其它移动终端上报的位置信息聚类得到的位置记录表中，所述位置记录表中包含信号强度值、以及与所述信号强度对应的位置信息。\n[0084] 步骤103，如果所述移动终端当前的信号强度值包含在所述位置记录表中，则从所述位置记录表中获取对应所述信号强度值的位置信息。\n[0085] 步骤104，将所述位置信息发送给所述移动终端。\n[0086] 在本发明实施例中，可以由基站接收其它移动终端上报的信号强度值与位置数据，当然，所述其它移动终端是指本身具有定位能力的移动终端，比如安装有GPS的移动终端。\n[0087] 需要说明的是中，所述位置记录表中包含的位置信息可以是具体的位置数据，还可进一步包含该位置数据的误差范围，对此将在后面详细说明。\n[0088] 在实际应用中，移动终端的上报报文可以包含以下信息：IMEI、IMSI、MCC、MNC、Lac、Cellid、RSS(Received Signal Strength，接收信号强度)、Lat、Lon，其中lat与lon分别对应用户当前的经、纬度值。\n[0089] 基站对接收到的用户的历史位置数据进行聚类处理，动态生成所述位置记录表，下面对本发明实施例中通过聚类处理生成所述位置记录表的过程进行详细说明。\n[0090] 所述聚类处理又称群分析，它是研究分类问题的一种统计分析方法。在本发明实施例中，可采用基于密度的聚类算法DBSCAN(Density-Based Spatial Clustering of Applications with Noise)对接收到的位置数据中具有相同信号强度值的位置数据进行聚类处理，得到所述位置记录表。基于密度的聚类算法能克服基于距离的算法只能发现“类圆形”的聚类的缺点，其核心思想就是：只要一个区域中的点的密度大过某个阈值，就将它加到与之相近的聚类中去。该算法能够将足够高密度的区域划分为簇，并根据历史位置数据的空间分布情况划分成任意形状的聚类。\n[0091] 基于历史位置的聚类分析算法包括：\n[0092] 算法输入：同一基站区域中相同信号强度值的历史位置点集P，邻域半径eps，邻域内最少节点数量minPts。\n[0093] 算法输出：点集P中每个历史位置点所归属的类别号码{pClass}。\n[0094] 算法过程如下：\n[0095] 1)初始化所有点的聚类id为0，取第一个历史位置点i为1；\n[0096] 2)如果i小于N(N为历史位置点的个数)，则对第i个点进行处理，i值加1；否则转12)；\n[0097] 3)如果该点被标记，转2)；\n[0098] 4)根据邻域半径eps求该点的邻域集；\n[0099] 5)如果邻域集中点的数量小于minPts，转2)；\n[0100] 6)标记该点为核心点，聚类id加1；\n[0101] 7)如果该核心点的邻域集中不存在未标记点，转2)；\n[0102] 8)依次选取未标记点，根据邻域半径eps求该点的邻域集；\n[0103] 9)如果该点的邻域集中点的数量小于minPts，转11)；\n[0104] 10)标记该点的聚类id，并标记其为核心点，转7)；\n[0105] 11)标记该点的聚类id，转7)；\n[0106] 12)算法结束。\n[0107] 所有的历史位置点被处理后的结果有三种情况：该点是核心点、或者是边界点、或者是噪声点，所述噪声点是指不属于任何聚类的位置点。当然，所述的核心点和边界点可能是针对不同的聚类而言的。\n[0108] 经过聚类处理后，排除其中的噪声点，可以得到多个对应不同信号强度值的聚类。\n[0109] 由于可能存在一个定位请求对应聚类中多个位置点的情况，因此还需要确定聚类的中心。由于聚类形状具有不规则性，常规求均值的方法可能导致聚类中心偏移聚类的情况发生。因此，在本发明实施例中，为了避免这种情况，可以优选采用最小覆盖圆算法包含这些聚类，即确定各聚类的圆心及半径。采用最小覆盖圆对聚类进行包围后，将得到的圆心的坐标作为位置数据，将半径作为该位置数据的误差范围。然后，将对应不同信号强度值的位置数据及误差范围保存到所述位置记录表中。\n[0110] 在求解最小覆盖圆算法中，首先需要对任意三个点求解最小覆盖圆。但由于三个点组成三角形形状的不同，相应的圆心与半径求解机制存在差异。令三个点的坐标值分别为(x1，y1)，(x2，y2)，(x3，y3)，圆半径为r，圆心为(x，y)。根据三点到圆心的距离相等，可以得到以下的方程组：\n[0111] \n[0112] 如果为锐角三角形，则可得到圆心的坐标和半径为：\n[0113] \n[0114] 如果为钝角或直角三角形，则可得到圆心和半径为：\n[0115] \n[0116] 本发明实施例中利用最小覆盖圆算法确定聚类中心的流程如图2所示，包括以下步骤：\n[0117] 步骤201，从属于同一个聚类的点集中随机选取三个点a，b，c；\n[0118] 步骤202，判断三个点a，b，c组成的三角形中两条短边的平方和是否大于最长边的平方，即判断所述三角形是否为锐角三角形；如果是，则执行步骤203；否则，执行步骤\n204；\n[0119] 步骤203，根据上述公式(2)确定半径r和圆心c；然后，执行步骤205；\n[0120] 步骤204，根据上述公式(3)确定半径r和圆心c；\n[0121] 步骤205，确定距离圆心最远的点p(x4，y4)；\n[0122] 步骤206，判断点p与圆心c的距离是否小于等于半径r，即判断是否dist(p，c)＜＝r；如果是，则执行步骤211；否则，执行步骤207；\n[0123] 步骤207，从a，b，c，p中选三个点做最小圆；\n[0124] 步骤208，判断第四个点是否在所述最小圆内；如果是，则执行步骤209；否则，执行步骤210；\n[0125] 步骤209，将从a，b，c，p中选取的三个点作为新的a，b，c；然后，返回步骤202；\n[0126] 步骤210，从a，b，c，p中另选三个点做最小圆；然后，返回步骤308；\n[0127] 步骤211，确定当前所做的圆为最小圆，即可得到对应聚类的圆心及半径。\n[0128] 可见，本发明实施例快速定位方法，由基站对用户的历史位置数据进行聚类处理，动态生成包含有信号强度值、以及与所述信号强度对应的位置信息的位置记录表，从而在接收到移动终端的定位请求后，可以快速向所述移动终端返回定位结果，而且，所述定位结果不仅包含位置数据，而且还可进一步包含对应该位置数据的误差范围，有效地提高了定位的精度。\n[0129] 由于基站接收到的其它移动终端上报的信号强度值与位置数据的优良程度不同，因此，为了进一步提高聚类的效果，在本发明实施例快速定位方法中，在对接收到的位置数据中具有相同信号强度值的位置数据进行聚类处理之前，还可以对这些历史位置数据进行预处理，主要包括：将接收到的信号强度值与位置数据保存到初始历史数据表中；在所述初始历史数据表中新的位置数据的个数达到第一阈值后，对所述初始历史数据表中新的位置数据进行筛选，得到筛选后历史数据表。\n[0130] 相应地，在对接收到的位置数据中具有相同信号强度值的位置数据进行聚类处理时，就只对所述筛选后历史数据表中具有相同信号强度值的位置数据进行聚类处理即可。\n[0131] 上述筛选过程主要包括以下两种处理过程：\n[0132] (1)删除所述初始历史数据表中重复的数据；\n[0133] (2)如果删除后剩余的数据达到了基站所需的数量阈值，则对所述剩余的数据进行精炼处理，并将精炼处理后的数据存入所述筛选后历史数据表中。其中，所述基站所需的数量阈值可以根据基站的覆盖范围计算得到，由于基站的覆盖范围不同，因此在后续进行聚类处理时所需的数据量也会不同。比如，在农村或城郊地区，基站覆盖范围可到上千米，此时需要较多的历史位置点反映整个区域的场强分布情况；而在城区或商业密集区域要求信号强度较高，因而要求基站以较小范围覆盖，通常在500～1000m之间，相应需要的历史位置点也较少。\n[0134] 需要说明的是，本发明实施例中对历史位置数据进行预处理可以按照上述方式，在所述初始历史数据表中新的位置数据的个数达到第一阈值后开始进行。除此之外，还可以按照预定的处理周期，定期对所述初始历史数据表中的位置数据进行预处理。对此本发明实施例不做限定，而且，如果删除初始历史数据表中重复的数据后剩余的数据超过了基站所需的数量阈值，则可以按照所述数据的接收时间的先后顺序保留最近接收的数据。\n[0135] 在本发明实施例中，针对在用户历史位置的积累中用户移动的无序性特点，对所述初始历史数据表中的位置数据进行精炼处理，以处理掉那些在定位过程中的冗余点位置，进一步提高定位的精度与速度。\n[0136] 下面对所述位置数据进行精炼处理的具体过程进行详细说明。\n[0137] 首先，可以按以下方式定义用户的历史位置数据：\n[0138] 用户i的历史位置数据以历史点序列{P1，P2，P3，...，Pn}表示，每个历史位置数据以三元组＜(xk，yk)，tk，RSSk＞表示，其含义为用户在tk时刻时，用户i的位置(xk，yk)及场强值RSSk。\n[0139] 在采用上述定义的情况下，用户i的历史位置数据轨迹可以表示为如下表1的形式。\n[0140] 表1：\n[0141] \n P1 (x1，y1) t1 RSS1\n ... ... ... ...\n Pi (xi，yi) ti RSSi\n ... ... ... ...\n Pn (xn，yn) tn RSSn\n[0142] 其次，将用户在某一特定区域移动时的中心位置定义为逗留点，以时间及距离门限(Tthreh，Dthreh)这两个因素来判断是否存在逗留点。\n[0143] 对一组连续的轨迹{pm，pm+1，...pi，...，pn}，m￡i￡n而言，如果距离Distance(pm，pi)＜Dthreh，且pn.t-pm.t＞Tthreh即用户在位置Pn和在位置Pm的时间间隔超过设定的时间门限Tthreh，则认为此时用户历史位置数据轨迹中存在逗留点S，且逗留点S中各属性的计算表达式为：\n[0144] \n[0145] 在对所述位置数据进行精炼处理的过程中，首先要发现用户历史位置记录中的逗留点，然后用逗留点代替其它的冗余位置数据，从而进一步精炼用户的历史位置数据。\n[0146] 如图3所示，是本发明实施例中对位置数据进行精炼处理的流程图，包括以下步骤：\n[0147] 步骤301，从位置点集P中依次选取第i个点作为当前点；\n[0148] 步骤302，判断是否已经选择至点集P中的最后一个点；如果是，则执行步骤303；\n否则，执行步骤309；\n[0149] 步骤303，选择第i+1个点，并将i+1赋值为j；\n[0150] 步骤304，判断dist(pj，pi)＜Dthreh，所述Dthreh为距离门限值；如果是，则执行步骤305，否则，执行步骤307；\n[0151] 步骤305，判断点j与点i的时间间隔是否满足(pj.t-pi.t)＞Tthreh，所述Tthreh为时间门限值；如果是，则执行步骤306；否则，执行步骤308；\n[0152] 步骤306，按照公式(4)计算逗留点S的位置、场强及时间值；从位置点集P中删除点i到点j之间的所有点；在位置点集P中插入逗留点S；\n[0153] 步骤307，将点j作为当前的点i；然后，执行步骤302；\n[0154] 步骤308，继续选择第j+1点，并用j+1赋值为j；然后执行步骤304；\n[0155] 步骤309，所有点都处理完毕。\n[0156] 在对所述剩余的位置数据进行精炼处理后，生成筛选后历史数据表。然后，对所述筛选后历史数据表中的位置数据进行密度聚类分析，生成与信号强度值对应的位置记录表，具体过程可参照前面的描述，在此不再赘述。\n[0157] 通过对历史位置数据进行筛选和精炼处理，可以提升后续聚类处理的速度及定位的精度。\n[0158] 如图4所示，是本发明实施例快速定位方法的另一种流程图，包括以下步骤：\n[0159] 步骤401，接收移动终端的定位请求，所述定位请求中包含所述移动终端当前的信号强度值。\n[0160] 步骤402，检查所述移动终端当前的信号强度值是否包含在根据其它移动终端上报的位置信息聚类得到的位置记录表中；如果是，则执行步骤403；否则，执行步骤404。\n[0161] 步骤403，从所述位置记录表中获取对应所述信号强度值的位置信息；然后，执行步骤409。\n[0162] 步骤404，检查所述移动终端当前的信号强度值是否包含在所述初始历史数据表中；如果是，则执行步骤406；否则，执行步骤405。\n[0163] 步骤405，获取基站的位置信息作为所述移动终端的定位结果，所述基站的位置信息包括基站坐标值及基站的覆盖半径，其中，基站坐标值可以作为所述移动终端的位置数据，基站的覆盖半径可以作为所述位置数据的误差范围；然后，执行步骤409。\n[0164] 步骤406，从所述初始历史数据表中获取与所述信号强度值对应的离散位置数据。\n[0165] 步骤407，采用最小覆盖圆算法确定所述离散位置数据的最小覆盖圆。\n[0166] 步骤408，将所述最小覆盖圆的圆心的坐标及半径分别作为所述移动终端的位置数据及误差范围。\n[0167] 步骤409，将所述位置数据及误差范围发送给所述移动终端，并保存定位结果信息，即创建定位日志。\n[0168] 需要说明的是，本发明实施例中，对历史位置数据的预处理及聚类处理可采用独立线程的处理机制，并将处理结果实时保存在相应的缓存中，这种离线的处理方式能极大地提高定位的速度。\n[0169] 本发明实施例快速定位方法，通过对基站中移动用户的位置数据进行聚类处理得到包含信号强度值、以及与所述信号强度对应的位置信息的位置记录表，在接收到移动终端的定位请求后，可以根据所述位置记录表中的信息立即返回定位结果，有效地提高了定位的精度。进一步地，通过对高热点位置的离线计算，在用户发起定位请求时快速返回定位结果，有效地提高了定位的速度。\n[0170] 由于目前移动终端大都支持RSS的采集功能，因此利用本发明实施例的方法，无需移动终端增加任何额外的定位设施，大大降低了本发明方案的实施成本。同时，在定位过程中充分利用移动用户的历史位置信息为定位提供辅助，有效避免了现有采用物理定位方式所面临的天气，建筑物阻挡等对定位的影响，通过离线化的数据收集与处理，以及在定位过程中考虑RSS、聚类中心与误差范围等因素，有效提高了定位速度与精度。\n[0171] 本领域普通技术人员可以理解实现上述实施例方法中的全部或部分步骤是可以通过程序来指令相关的硬件来完成，所述的程序可以存储于计算机可读取存储介质中，所述的存储介质，如：ROM/RAM、磁碟、光盘等。\n[0172] 相应地，本发明实施例还提供一种快速定位系统，如图5所示，是该系统的一种结构示意图。\n[0173] 在该实施例中，所述系统包括：\n[0174] 报文接收单元501，用于接收移动终端的定位请求，所述定位请求中包含所述移动终端当前的信号强度值；\n[0175] 第一检查单元502，用于检查所述移动终端当前的信号强度值是否包含在根据其它移动终端上报的位置信息聚类得到的位置记录表中，所述位置记录表中包含信号强度值、以及与所述信号强度对应的位置信息；\n[0176] 定位结果获取单元503，用于在所述第一检查单元的检查结果为所述移动终端当前的信号强度值包含在所述位置记录表时，从所述位置记录表中获取对应所述信号强度值的位置信息；\n[0177] 发送单元504，用于将所述定位结果获取单元获取的位置信息发送给所述移动终端。\n[0178] 所述位置记录表需要根据其它移动终端上报的位置信息聚类得到，为此，在本发明实施例中，所述报文接收单元501，还用于接收其它移动终端上报的信号强度值与位置数据。\n[0179] 相应地，如图5所示，所述系统还进一步包括：\n[0180] 聚类处理单元505，用于对所述报文接收单元501接收到的位置数据中具有相同信号强度值的位置数据进行聚类处理，得到所述位置记录表。\n[0181] 所述聚类处理单元505包括：聚类子单元、误差估计子单元和位置记录表生成子单元。其中：\n[0182] 所述聚类子单元，用于采用基于密度的聚类算法对接收到的位置数据中具有相同信号强度值的位置数据进行聚类处理，得到对应不同信号强度值的聚类；\n[0183] 所述误差估计子单元，用于采用最小覆盖圆算法确定各聚类的圆心的坐标及半径；\n[0184] 所述位置记录表生成子单元，用于将所述圆心的坐标作为与所述信号强度值对应的位置数据，将所述半径作为与所述信号强度值对应的误差范围，并与对应的所述信号强度值一起保存到所述位置记录表中。\n[0185] 所述聚类处理单元505中各子单元的具体处理可参照前面本发明实施例快速定位方法中的描述，在此不再赘述。\n[0186] 可见，本发明实施例快速定位系统，通过对用户的历史位置数据进行聚类处理，动态生成包含有信号强度值、以及与所述信号强度对应的位置信息的位置记录表，从而在接收到移动终端的定位请求后，可以快速向所述移动终端返回定位结果，而且，所述定位结果不仅包含位置数据，而且还可进一步包含对应该位置数据的误差范围，有效地提高了定位的精度。\n[0187] 由于其它移动终端上报的信号强度值与位置数据的优良程度不同，因此，为了进一步提高聚类的效果，在本发明实施例快速定位系统中，在对接收到的位置数据中具有相同信号强度值的位置数据进行聚类处理之前，还可以对这些历史位置数据进行预处理，主要包括：将接收到的信号强度值与位置数据保存到初始历史数据表中；在所述初始历史数据表中新的位置数据的个数达到第一阈值后，对所述初始历史数据表中新的位置数据进行筛选，得到筛选后历史数据表。\n[0188] 如图6所示，是本发明实施例快速定位系统的另一种结构示意图。\n[0189] 与图5所示实施例不同的是，在该实施例中，所述系统还包括：初始历史数据存储单元601和筛选单元602。其中：\n[0190] 所述初始历史数据存储单元601，用于在所述聚类处理单元505对接收到的位置数据中具有相同信号强度值的位置数据进行聚类处理之前，将接收到的信号强度值与位置数据保存到初始历史数据表中；\n[0191] 所述筛选单元602，用于在所述初始历史数据表中新的位置数据的个数达到第一阈值后，对所述初始历史数据表中新的位置数据进行筛选，得到筛选后历史数据表。\n[0192] 相应地，所述聚类处理单元505，具体用于对所述筛选后历史数据表中具有相同信号强度值的位置数据进行聚类处理，聚类处理的详细过程可参照前面的描述，在此不再赘述。\n[0193] 在本发明实施例中，所述筛选单元602包括：删除子单元和精炼处理子单元，其中：\n[0194] 所述删除子单元，用于删除所述初始历史数据表中重复的数据；\n[0195] 所述精炼处理子单元，用于在所述删除后剩余的数据达到了基站所需的数量阈值后，对所述剩余的数据进行精炼处理，并将精炼处理后的数据存入所述筛选后历史数据表中。\n[0196] 优选地，所述精炼处理子单元包括：逗留点确定子单元和筛选后历史数据存储单元，其中：\n[0197] 所述逗留点确定子单元，用于根据时间及距离门限确定用户历史位置记录中的逗留点，所述逗留点为用户在一特定区域移动时的中心位置；\n[0198] 所述筛选后历史数据存储单元，用于用所述逗留点代替其它的冗余位置数据，生成筛选后历史数据表。\n[0199] 如图7所示，是本发明实施例快速定位系统的另一种结构示意图。\n[0200] 与图6所示实施例不同的是，在该实施例中，所述系统还包括：第二检查单元701和计算单元702。其中：\n[0201] 所述第二检查单元701，用于在所述第一检查单元502的检查结果为所述移动终端当前的信号强度值未包含在所述位置记录表时，检查所述移动终端当前的信号强度值是否包含在所述初始历史数据表中；\n[0202] 所述计算单元702，用于在所述第二检查单元701的检查结果为所述移动终端当前的信号强度值包含在所述初始历史数据表中时，从所述初始历史数据表中获取与所述信号强度值对应的离散位置数据，并采用最小覆盖圆算法确定所述离散位置数据的最小覆盖圆，将所述最小覆盖圆的圆心的坐标及半径分别作为所述移动终端的位置数据及误差范围传送给所述定位结果获取单元。\n[0203] 相应地，所述定位结果获取单元503，还用于在所述第二检查单元701的检查结果为所述移动终端当前的信号强度值未包含在所述初始历史数据表中时，获取基站的位置信息，所述基站的位置信息包括基站坐标值及基站的覆盖半径。所述发送单元504，还用于将所述基站的位置信息发送给所述移动终端，以及将所述计算单元702传送给所述定位结果获取单元503的移动终端的位置数据及误差范围发送给所述移动终端。\n[0204] 本发明实施例快速定位系统，通过对基站中移动用户的位置数据进行聚类处理得到包含信号强度值、以及与所述信号强度对应的位置信息的位置记录表，在接收到移动终端的定位请求后，可以根据所述位置记录表中的信息立即返回定位结果，有效地提高了定位的精度。进一步地，通过对高热点位置的离线计算，在用户发起定位请求时快速返回定位结果，有效地提高了定位的速度。\n[0205] 本说明书中的各个实施例之间相同相似的部分互相参见即可，每个实施例重点说明的都是与其它实施例的不同之处。尤其，对于系统实施例而言，由于其基本相似于方法实施例，所以描述得比较简单，相关之处参见方法实施例的部分说明即可。以上所描述的系统实施例仅仅是示意性的，其中所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部单元来实现本实施例方案的目的。本领域普通技术人员在不付出创造性劳动的情况下，即可以理解并实施。\n[0206] 例如，如图8所示，是本发明实施例快速定位系统在实际应用中的一种变形结构示意图。\n[0207] 在该实施例中，所述系统包括：网络适配处理模块801、历史位置数据处理模块\n802、数据预处理模块803、聚类处理模块804和定位处理模块805。其中：\n[0208] 所述网络适配处理模块801，用于接收移动终端发送的报文，并判断所述报文的类型，如果所述报文是定位请求报文，则将所述报文转发至定位处理模块805；如果所述报文是移动终端上报的信号强度值与位置数据，则将所述报文转发至所述历史位置数据处理模块802；\n[0209] 所述历史位置数据处理模块802，用于将接收到的信号强度值与位置数据保存到初始历史数据表中；\n[0210] 所述数据预处理模块803，用于调用所述初始历史数据表，对所述初始历史数据表中的数据进行预处理，生成筛选后历史数据表；\n[0211] 所述聚类处理模块804，用于对所述筛选后历史数据表中的历史位置数据进行聚类处理，生成包含信号强度值及与所述信号强度值对应的位置信息的位置记录表，以供所述定位处理模块805查询；\n[0212] 所述定位处理模块805，用于在接收到所述定位请求报文后，根据所述定位请求报文中的信号强度值，以及所述位置记录表、所述初始历史数据表、基站位置数据确定所述移动终端的位置信息，并将确定的位置信息返回给所述移动终端。\n[0213] 在本发明实施例中，各功能模块的具体实现方式与前面具有相同功能的一个单元(或子单元)、或者多个单元(或子单元)的组合类似，比如所述定位处理模块805就融合了多个单元和子单元的功能，其根据所述定位请求报文中的信号强度值，以及所述位置记录表、所述初始历史数据表、基站位置数据确定所述移动终端的位置信息的具体过程可参照图4所示实施例中的描述，在此不再赘述。\n[0214] 本发明实施例快速定位系统，通过对基站中移动用户的位置数据进行聚类处理得到包含信号强度值、以及与所述信号强度对应的位置信息的位置记录表，在接收到移动终端的定位请求后，可以根据所述位置记录表中的信息立即返回定位结果，有效地提高了定位的精度。进一步地，通过对高热点位置的离线计算，在用户发起定位请求时快速返回定位结果，有效地提高了定位的速度。\n[0215] 以上公开的仅为本发明的优选实施方式，但本发明并非局限于此，任何本领域的技术人员能思之的没有创造性的变化，以及在不脱离本发明原理前提下所作的若干改进和润饰，都应落在本发明的保护范围内。