一种位置指纹库的建立方法及装置

摘要

本申请公开一种位置指纹库的建立方法及装置，属于通信技术领域，该方法包括：对待定位区域进行栅格划分，利用geo‑hash算法对每个栅格的地理位置信息进行编码，得到该栅格的地理编码；获取待定位区域内各终端上报的采样点，利用geo‑hash算法对该采样点对应的地理位置信息进行编码，得到该采样点的地理编码，若确定该采样点的地理编码的前N位与该采样点对应的基站的地理编码的前N位相同，则将具有该采样点的地理编码的栅格确定为该采样点落入的栅格，针对每个栅格，建立该栅格的地理编码与落入该栅格中的各采样点对应的基站的标识和信号强度之间的对应关系，对应关系保存在位置指纹库中。

权利要求

1.一种位置指纹库的建立方法，其特征在于，包括：对待定位区域进行栅格划分，利用geo-hash算法对每个栅格的地理位置信息进行编码，得到该栅格的地理编码；

获取所述待定位区域内各终端上报的采样点，每个采样点对应的采样信息至少包括上报该采样点时终端的地理位置信息、为该终端提供通信服务的基站的标识信息和信号强度信息，利用geo-hash算法对所述地理位置信息进行编码，得到该采样点的地理编码，若确定该采样点的地理编码的前N位与所述基站的地理编码的前N位相同，则确定所述基站的位置未发生变化，并将具有该采样点的地理编码的栅格确定为该采样点落入的栅格，其中，所述基站的地理编码根据所述基站在所述待定位区域中的位置预先估计，N为整数；

针对每个栅格，建立所述栅格的地理编码与落入该栅格中的各采样点对应的基站的标识和信号强度之间的对应关系，将所述对应关系保存在位置指纹库中。

2.如权利要求1所述的方法，其特征在于，将所述对应关系保存在位置指纹库中之后，还包括：

若再获取到所述待定位区域内终端新上报的采样点，则确定所述采样点落入的栅格；

根据所述采样点对应的采样信息，更新该栅格的地理编码与落入该栅格中的各采样点对应的基站的标识和信号强度之间的对应关系。

3.如权利要求1或2所述的方法，其特征在于，针对每个栅格，根据以下步骤建立或更新该栅格的地理编码与落入该栅格中的采样点对应的基站的标识和信号强度之间的对应关系：

对落入该栅格中的每个采样点，对所述采样点对应的每个基站，确定已获取到的包含所述基站的标识信息的采样点个数；

判断采样点个数是否大于预设值；

若是，则确定所述采样点对应的所述基站的信号强度在保存的所述基站所有的信号强度中的排名，当确定所述排名大于或者等于所述预设值时，建立该栅格的地理编码与所述基站的标识和信号强度之间的对应关系；

若否，则建立该栅格的地理编码与所述基站的标识和信号强度之间的对应关系。

4.如权利要求1所述的方法，其特征在于，还包括：若确定该采样点的地理编码的前N位与该采样点对应的任一基站的地理编码的前N位不相同，则将该采样点标记为所述基站的奇异点；

若为所述基站标记的奇异点的个数超过预设个数，则确定所述基站的位置已发生变化，删除所述位置指纹库中存储的包含所述基站的标识的对应关系，并针对为所述基站标记的每个奇异点，确定所述奇异点落入的栅格，建立该栅格的地理编码与所述基站的标识和所述奇异点对应的所述基站的信号强度之间的对应关系，将所述对应关系保存在所述位置指纹库中。

5.如权利要求1所述的方法，其特征在于，将所述对应关系保存在位置指纹库中之后，还包括：

接收定位请求，所述定位请求中携带有当前为终端提供通信服务的基站的标识信息和信号强度信息；

从所述位置指纹库中查询包含所述基站的标识信息和信号强度信息的至少一个栅格；

根据所述至少一个栅格对所述终端进行定位，并将定位结果发送给所述终端。

6.如权利要求5所述的方法，其特征在于，若对每个栅格记录有落入该栅格中的采样点个数，则根据所述至少一个栅格的地理位置对所述终端进行定位，包括：根据落入所述至少一个栅格中每个栅格中的采样点个数，利用Weiszfeld算法确定所述至少一个栅格的质心点；

将所述质心点所在的地理位置作为对所述终端的定位结果。

7.一种位置指纹库的建立装置，其特征在于，包括：编码模块，用于对待定位区域进行栅格划分，利用geo-hash算法对每个栅格的地理位置信息进行编码，得到该栅格的地理编码；

确定模块，用于获取所述待定位区域内各终端上报的采样点，每个采样点对应的采样信息至少包括上报该采样点时终端的地理位置信息、为该终端提供通信服务的基站的标识信息和信号强度信息，利用geo-hash算法对所述地理位置信息进行编码，得到该采样点的地理编码，若确定该采样点的地理编码的前N位与所述基站的地理编码的前N位相同，则确定所述基站的位置未发生变化，并将具有该采样点的地理编码的栅格确定为该采样点落入的栅格，其中，所述基站的地理编码根据所述基站在所述待定位区域中的位置预先估计，N为整数；

建立模块，用于针对每个栅格，建立所述栅格的地理编码与落入该栅格中的各采样点对应的基站的标识和信号强度之间的对应关系，将所述对应关系保存在位置指纹库中。

8.如权利要求7所述的装置，其特征在于，所述确定模块，还用于将所述对应关系保存在位置指纹库中之后，若再获取到所述待定位区域内终端新上报的采样点，则确定所述采样点落入的栅格；

所述建立模块，还用于根据所述采样点对应的采样信息，更新该栅格的地理编码与落入该栅格中的各采样点对应的基站的标识和信号强度之间的对应关系。

9.如权利要求7或8所述的装置，其特征在于，所述建立模块具体用于针对每个栅格，根据以下步骤建立或更新该栅格的地理编码与落入该栅格中的采样点对应的基站的标识和信号强度之间的对应关系：

对落入该栅格中的每个采样点，对所述采样点对应的每个基站，确定已获取到的包含所述基站的标识信息的采样点个数；

判断采样点个数是否大于预设值；

若是，则确定所述采样点对应的所述基站的信号强度在保存的所述基站所有的信号强度中的排名，当确定所述排名大于或者等于所述预设值时，建立该栅格的地理编码与所述基站的标识和信号强度之间的对应关系；

若否，则建立该栅格的地理编码与所述基站的标识和信号强度之间的对应关系。

10.如权利要求7所述的装置，其特征在于，所述确定模块，还用于若确定该采样点的地理编码的前N位与该采样点对应的任一基站的地理编码的前N位不相同，则将该采样点标记为所述基站的奇异点；

所述建立模块，还用于若为所述基站标记的奇异点的个数超过预设个数，则确定所述基站的位置已发生变化，删除所述位置指纹库中存储的包含所述基站的标识的对应关系，并针对为所述基站标记的每个奇异点，确定所述奇异点落入的栅格，建立该栅格的地理编码与所述基站的标识和所述奇异点对应的所述基站的信号强度之间的对应关系，将所述对应关系保存在所述位置指纹库中。

11.如权利要求7所述的装置，其特征在于，还包括：接收模块，用于在将所述对应关系保存在位置指纹库中之后，接收定位请求，所述定位请求中携带有当前为终端提供通信服务的基站的标识信息和信号强度信息；

查询模块，用于从所述位置指纹库中查询包含所述基站的标识信息和信号强度信息的至少一个栅格；

定位模块，用于根据所述至少一个栅格对所述终端进行定位，并将定位结果发送给所述终端。

12.如权利要求11所述的装置，其特征在于，若对每个栅格记录有落入该栅格中的采样点个数，所述定位模块具体用于：

根据落入所述至少一个栅格中每个栅格中的采样点个数，利用Weiszfeld算法确定所述至少一个栅格的质心点；

将所述质心点所在的地理位置作为对所述终端的定位结果。

13.一种电子设备，其特征在于，包括：至少一个处理器，以及与所述至少一个处理器通信连接的存储器，其中：

所述存储器存储有可被所述至少一个处理器执行的指令，所述指令被所述至少一个处理器执行，以使所述至少一个处理器能够执行如权利要求1至6任一权利要求所述的方法。

14.一种计算机可读介质，存储有计算机可执行指令，其特征在于，所述计算机可执行指令由电子设备的处理器执行时，所述电子设备能够执行如权利要求1至6任一权利要求所述的方法。

说明书

一种位置指纹库的建立方法及装置

技术领域

[0001] 本申请涉及通信技术领域，尤其涉及一种位置指纹库的建立方法及装置。

背景技术

[0002] 随着通信技术的快速发展和终端的普及，对终端进行定位的需求也越来越多。

[0003] 目前，常用的定位方法有卫星定位和基站定位，其中，卫星定位的定位精度比较高，但要求终端必须有GPS、北斗定位等模块支持，并且需要得到用户允许才可对终端进行
定位，对于通信运营商而言，这些条件较苛刻，很难实现；基于基站的定位要求基站与基站、
基站与终端等节点间都必须保持精确的时间同步，对各节点的硬件和功耗要求都比较高，
也难以开展，因此，急需一种适合通信运营商开展的定位方案。

发明内容

[0004] 本申请实施例提供一种位置指纹库的建立方法及装置，用以提供一种适合通信运营商开展的定位方案。

[0005] 第一方面，本申请实施例提供的一种位置指纹库的建立方法，包括：

[0006] 对待定位区域进行栅格划分，利用geo-hash算法对每个栅格的地理位置信息进行编码，得到该栅格的地理编码；

[0007] 获取所述待定位区域内各终端上报的采样点，每个采样点对应的采样信息至少包括上报该采样点时终端的地理位置信息、为该终端提供通信服务的基站的标识信息和信号
强度信息，利用geo-hash算法对所述地理位置信息进行编码，得到该采样点的地理编码，若
确定该采样点的地理编码的前N位与所述基站的地理编码的前N位相同，则确定所述基站的
位置未发生变化，并将具有该采样点的地理编码的栅格确定为该采样点落入的栅格，其中，
所述基站的地理编码根据所述基站在所述待定位区域中的位置预先估计，N为整数；

[0008] 针对每个栅格，建立所述栅格的地理编码与落入该栅格中的各采样点对应的基站的标识和信号强度之间的对应关系，将所述对应关系保存在位置指纹库中。

[0009] 采样上述方案，对待定位区域进行栅格划分，并获取待定位区域内各终端上报的采样点，之后，利用geo-hash算法确定每个采样点的地理编码，若确定该采样点的地理编码
的前N位与该采样点对应的基站的地理编码的前N位相同，则确定基站为发生移位，将具有
该采样点的地理编码的栅格确定为该采样点落入的栅格，针对每个栅格，建立栅格的地理
编码与落入该栅格中的各采样点对应的基站的标识和信号强度之间的对应关系，将对应关
系保存在位置指纹库中，对于通信运营商而言，采样点容易获取，因此，比较适于通信运营
商开展，并且，在位置指纹库建立阶段即考虑基站的移位情况，可较好地避免由于基站移位
而导致的定位精度低的问题。

[0010] 第二方面，本申请实施例提供的一种位置指纹库的建立装置，包括：

[0011] 编码模块，用于对待定位区域进行栅格划分，利用geo-hash算法对每个栅格的地理位置信息进行编码，得到该栅格的地理编码；

[0012] 确定模块，用于获取所述待定位区域内各终端上报的采样点，每个采样点对应的采样信息至少包括上报该采样点时终端的地理位置信息、为该终端提供通信服务的基站的
标识信息和信号强度信息，利用geo-hash算法对所述地理位置信息进行编码，得到该采样
点的地理编码，若确定该采样点的地理编码的前N位与所述基站的地理编码的前N位相同，
则确定所述基站的位置未发生变化，并将具有该采样点的地理编码的栅格确定为该采样点
落入的栅格，其中，所述基站的地理编码根据所述基站在所述待定位区域中的位置预先估
计，N为整数；

[0013] 建立模块，用于针对每个栅格，建立所述栅格的地理编码与落入该栅格中的各采样点对应的基站的标识和信号强度之间的对应关系，将所述对应关系保存在位置指纹库
中。

[0014] 第三方面，本申请实施例提供的一种电子设备，包括：至少一个处理器，以及与所述至少一个处理器通信连接的存储器，其中：

[0015] 存储器存储有可被至少一个处理器执行的指令，该指令被所述至少一个处理器执行，以使所述至少一个处理器能够执行上述位置指纹库的建立方法。

[0016] 第四方面，本申请实施例提供的一种计算机可读介质，存储有计算机可执行指令，所述计算机可执行指令用于执行上述位置指纹库的建立方法。

[0017] 另外，第二方面至第四方面中任一种设计方式所带来的技术效果可参见第一方面中不同实现方式所带来的技术效果，此处不再赘述。

[0018] 本申请的这些方面或其它方面在以下实施例的描述中会更加简明易懂。

附图说明

[0019] 此处所说明的附图用来提供对本申请的进一步理解，构成本申请的一部分，本申请的示意性实施例及其说明用于解释本申请，并不构成对本申请的不当限定。在附图中：

[0020] 图1为本申请实施例提供的位置指纹库的建立方法的流程图；

[0021] 图2为本申请实施例提供的建立每个栅格的地理编码与落入该栅格中的采样点对应的基站的标识和信号强度之间的对应关系的方法流程图；

[0022] 图3为本申请实施例提供的用于实现位置指纹库的建立方法的电子设备的硬件结构示意图；

[0023] 图4为本申请实施例提供的位置指纹库的建立装置的结构示意图。

具体实施方式

[0024] 为了提供一种适合通信运营商开展的定位方案，本申请实施例提供了一种位置指纹库的建立方法及装置。

[0025] 以下结合说明书附图对本申请的优选实施例进行说明，应当理解，此处所描述的优选实施例仅用于说明和解释本申请，并不用于限定本申请，并且在不冲突的情况下，本申
请中的实施例及实施例中的特征可以相互组合。

[0026] 实际应用中，基站在建立后其位置就固定下来了，基站的覆盖范围也可估计出来，但基站的实际位置以及基站的覆盖范围对通信运营商而言是非常重要的，不可能对外公
布，因此，目前，利用基站进行定位的方法都是预先估计基站的位置，之后，再利用估计的基
站位置来对终端进行定位，利用这种方式进行定位，一旦某个基站的位置发生了变化，定位
精度将大大折扣。

[0027] 为了提高基站的定位精度，发明人想到对待定位区域进行栅格划分，利用geo-hash算法对各栅格的地理位置信息进行编码，得到各栅格的地理编码，并获取待定位区域
内各终端上报的采样点，每个采样点对应的采样信息至少包括上报该采样点时终端的地理
位置信息、为该终端提供通信服务的基站的标识信息和信号强度信息。

[0028] 考虑到geo-hash算法的特性为：地理位置相近的两个区域对应的两个地理编码的前几位一定相同，所以，若基站的位置未发生变化，那么位于该基站下的终端上报的采样点
最终一定会落入预先确定的该基站的覆盖范围内，相反，如果位于该基站下的终端上报的
采样点却未落入预先确定的该基站的覆盖范围内，则说明该基站有可能发生了移位。

[0029] 为了辨别待定位区域内的基站是否发生移位，可预先估计每个基站的覆盖区域，然后利用geo-hash算法对该覆盖区域进行编码，得到该基站的地理编码，并且，针对每个采
样点，利用geo-hash算法对该采样点对应的地理位置信息进行编码，得到该采样点的地理
编码，之后，将该采样点的地理编码与该采样点对应的基站的地理编码的前N位进行比较，
若两者相同，则认为基站的位置未发生变化，进而将具有该采样点的地理编码的栅格确定
为该采样点落入的栅格。

[0030] 进一步地，针对每个栅格，建立该栅格的地理编码与落入该栅格中的各采样点对应的基站的标识和信号强度之间的对应关系，并将对应关系保存在位置指纹库中。

[0031] 这样，在建立位置指纹库阶段就考虑基站移位的情况，并且，位置指纹库可实时更新，后续再使用位置指纹库进行定位就可以较好地规避掉因基站位置发生变化而导致的定
位不准确的问题。

[0032] 下面结合具体的实施例对上述过程进行说明。

[0033] 离线建立位置指纹库阶段：

[0034] 首先，对待定位区域进行栅格划分，并可利用geo-hash算法对每个栅格的地理位置信息进行编码，得到该栅格的地理编码。

[0035] 进一步，获取待定位区域内各终端上报的采样点，每个采样点对应的采样信息至少包括上报该采样点时终端的地理位置信息、为该终端提供通信服务的基站的标识信息和
信号强度信息，进而利用geo-hash算法对地理位置信息进行编码，得到该采样点的地理编
码，将该采样点的地理编码的前3位与基站的地理编码的前3位进行比较，若两者相同，则确
定基站的位置未发生变化，将具有该采样点的地理编码的栅格确定为该采样点落入的栅
格，针对每个栅格，建立该栅格的地理编码与落入该栅格中的各采样点对应的基站的标识
和信号强度之间的对应关系，将对应关系保存在位置指纹库中。

[0036] 这样，对待定位区域中的每个基站，相当于形成了基站的信号强度与地理位置之间的关系，相当于描绘出了该基站覆盖范围内采样点的分布情况或者说是描绘出了基站的
画像，并且，为了提高后续的定位精度，还可限制对每个基站只记录200个其最强的信号强
度。

[0037] 后续，当再获取到待定位区域内终端新上报的采样点时，还可对上述初始的位置指纹进行更新。具体地，利用geo-hash算法对该采样点对应的地理位置信息进行编码，得到
该采样点的地理编码，确定该采样点落入的栅格，如果栅格内已存在相关数据，则可对比该
采样点对应的接收信号强度(Received Signal Strength，RSS)与已记录的该栅格中的RSS
大小，记录RSS较大者的指纹数据；若指纹库中未记录过这批基站的信息，则建立该采样点
落入的栅格的地理编码与该采样点对应的基站的标识和信号强度之间的对应关系，即在指
纹库中添加相关指纹信息。

[0038] 由于大多数基站覆盖范围较大，基站覆盖范围部分重合(尤其是在闹市区)，所以，指纹库中栅格与基站将形成多对多的关系，另外，考虑到不同地方的人流量不同，每个栅格
内的指纹数据量大小(采样点个数)定会存在差异，而人流量的多少能反映待定位点在该区
域出现的概率，因此，在建立位置指纹库时还可为每个栅格记录落入其中的采样点的个数。

[0039] 在线定位阶段：

[0040] 当接收到定位请求时，可从定位请求包含的基站信息中筛选出至少包含基站Cell-ID和RSS这两类数据的高质量信息，这里，可以RSS作为基站信息质量为标准，筛选出
RSS大于设定阈值的基站信息，之后，按照RSS降序排序，选取排名前三条的基站信息，若获
取的基站信息不足三条，则采用获取到的所有信息，之后，以Cell-ID和RSS作为关键字在指
纹库里面搜索出对应的栅格。

[0041] 其中，若只能收到一个基站的信号，则会搜索出包括该基站的标识和RSS的所有栅格；若收到2个及以上基站的信号，则会搜索出两个基站覆盖区域交叉处的栅格。

[0042] 进一步地，对搜索出的栅格按照其指纹数据数量从多到少的顺序排序，取排名靠前的几个区域，若获取到一个栅格，则将栅格的质心点作为待定位点的位置；若获取到的栅
格数大于1，则将多个栅格中的指纹数据用平均距离最小算法获得质心点，将质心点的位置
作为待定位点的位置。

[0043] 采用上述方式，若对单基站覆盖范围内的终端进行定位，可先获取基站覆盖范围内的全部栅格中的指纹数据，然后，从这些指纹数据中提取每个栅格中所存储的位置点的
位置和指纹数据量，最后，用平均距离最小算法获得质心点，质心点的位置即为对终端的定
位结果。

[0044] 如图1所示，为本申请实施例提供的位置指纹库的建立方法的流程图，包括以下步骤：

[0045] S101：对待定位区域进行栅格划分，利用geo-hash算法对每个栅格的地理位置信息进行编码，得到该栅格的地理编码。

[0046] 其中，栅格划分的越小，地理编码的位数越多，由于geo-hash算法的特性，地理位置比较近的栅格，其地理编码的前缀是相同的，这样比较便于后续快速确定出每个采样点
落入的栅格、确定发生移位的基站，因此，这里利用geo-hash算法对每个栅格的地理位置信
息进行编码。

[0047] S102：获取待定位区域内各终端上报的采样点，每个采样点对应的采样信息至少包括上报该采样点时终端的地理位置信息、为该终端提供通信服务的基站的标识信息和信
号强度信息。

[0048] 其中，每个包含精确地理位置的采样点可由通信运营商通过嵌入在其发布的基础软件(如咪咕)里面的SDK客户端获得。

[0049] S103：利用geo-hash算法对每个采样点对应的地理位置进行编码，得到该采样点的地理编码，若确定该采样点的地理编码的前N位与该采样点对应的基站的地理编码的前N
位相同，则确定基站的位置未发生变化，并将具有该采样点的地理编码的栅格确定为该采
样点落入的栅格。

[0050] 其中，基站的地理编码根据基站在待定位区域中的位置预先估计，比如，待定位区域为北京，已知北京有4个基站，分别位于海淀区、朝阳区、大兴区和通州区，设定基站的覆
盖半径为300米，此时，可估计出每个基站的覆盖范围，进而利用geo-hash算法对该覆盖范
围进行编码，得到该基站的地理编码，虽然，一开始知道的基站的位置比较模糊，但对每个
基站，随着搜集的采样点的增多，通过这些采样点可以得到越来越多的该基站的信号强度
与地理位置间的对应关系，通过这些对应关系可以学习出该基站的精确位置。

[0051] 对利用geo-hash算法得到的地理编码，只要两个基站的地理位置相邻，那么它们地理编码的前几位一定是相同的，代表这两个基站同属于一个比较大的区域，而对相邻的
栅格，这些栅格对应的地理编码中相同位数会更多，可能就会只有后面的1位不同，代表它
们同属于一个比较小的区域，因此，对同一个基站而言，如果其位置未发生变化，那么位于
该基站下面的终端上报的采样点一定会落入该基站的覆盖范围内，也就是说采样点的地理
编码的前几位一定会跟基站的地理编码的前几位相同，如果采样点的地理编码的前几位跟
基站的地理编码的前几位都不同，则说明基站有可能发生了移位。

[0052] 为了确保生成的每个基站的信号强度与地理位置之间的对应关系是准确的，在利用geo-hash算法得到每个采样点的地理编码后，可将该采样点的地理编码的前N位与该采
样点对应的基站的地理编码的前N位进行比对，确定两者相同时，再将具有该采样点的地理
编码的栅格确定为该采样点落入的栅格。

[0053] S104：针对每个栅格，建立该栅格的地理编码与落入该栅格中的各采样点对应的基站的标识和信号强度之间的对应关系，将对应关系保存在位置指纹库中。

[0054] 在具体实施时，随着采样点个数的增多，位置指纹库中的数据量也会增多，虽然采样点的量越大越能逼近真实的用户分布情况，但过多的数据会浪费数据库的存储空间，且
会拖慢定位速度，因此，对待定位区域中的每个基站，可以设置为其记录的信号强度的上
限，当终端上报的同一基站的信号强度的个数超过上限时，可删除较弱的信号强度，留下数
据价值比较高的较强的信号强度。

[0055] 具体地，针对每个栅格，可根据图2所示的步骤建立该栅格的地理编码与落入该栅格中的各采样点对应的基站的标识和信号强度之间的对应关系：

[0056] S201a：对落入该栅格中的每个采样点，对该采样点对应的每个基站，确定已获取到的包含该基站的标识信息的采样点个数。

[0057] 实际应用中，终端可能会接收到一个基站的信号，也可能会接收多个基站的信号，因此，终端上报的采样点可能只对应一个基站，也可能对应多个基站。

[0058] S202a：判断采样点个数是否大于预设值，若否，则进入S203a；若是，则进入S204a。

[0059] 这里，预设值如200。

[0060] S203a：建立该栅格的地理编码与该基站的标识和信号强度之间的对应关系。

[0061] S204a：确定采样点对应的该基站的信号强度在保存的该基站所有的信号强度中的排名。

[0062] 比如，对每个基站仅保留其最强的200个信号强度，后续，再获取到该基站的信号强度时，可以将此次获取到的该基站的信号强度与保存的该基站的200个信号强度进行比
较，确定此次获取到的该基站的信号强度在保存的该基站所有的信号强度中的排名。

[0063] S205a：判断排名是否大于预设值，若是，则进入S203a；否则，进入S206a。

[0064] 为了保证对该基站记录的信号强度的个数不超过预设值，当确定采样点对应的该基站的信号强度的排名大于或者等于预设值时，可用此次获取到的该基站的信号强度替换
已保存的该基站最弱的信号强度，具体地，先删除保存的该基站最弱的信号强度，之后，再
建立采样点落入栅格的地理编码与该基站的标识和信号强度之间的对应关系，即保存此次
获取到的该基站的信号强度。

[0065] S206a：不记录该基站的信号强度信息。

[0066] 同样地，为了保证对该基站记录的信号强度的个数不超过预设值，当确定采样点对应的该基站的信号强度的排名小于预设值时，即可舍弃此次获取到的该基站的信号强
度。

[0067] 另外，考虑到落入栅格中的采样点的个数可以反映出终端在栅格对应位置的出现概率，因此，对每个栅格还可记录落入其中的采样点个数。

[0068] S105：接收定位请求，其中，定位请求中携带有当前为终端提供通信服务的基站的标识信息和信号强度信息。

[0069] S106：从位置指纹库中查询包含基站标识信息和信号强度信息的至少一个栅格。

[0070] 在具体实施时，可对定位请求中携带的信号强度进行筛选，挑选大于设定阈值的基站的信号强度，之后，再从位置指纹库中查询包含这些基站的标识信息和信号强度信息
的栅格。

[0071] S107：根据查询到的栅格对终端进行定位，并将定位结果发送给终端。

[0072] 具体地，可根据落入各栅格中的采样点个数，利用Weiszfeld算法确定查询到的栅格的质心点，将质心点所在的地理位置作为对终端的定位结果，这里，质心点并不是查询到
的各栅格的中心点，而是根据查询到的各栅格中落入的采样点个数确定出的点，用于代表
当前最可能的定位位置，其概念可以类比物体的质量中心点。

[0073] 下面结合具体实施例对利用Weiszfeld算法确定查询到的栅格的质心点的过程进行说明。

[0074] 假设查询到j个栅格，j＝1,2,3,…,n，j和n均为整数，其中，栅格j对应一个点aj，aj在离线阶段通过对落在栅格j内的采样信息通过自学习计算得到，aj代表的是，若有一待定
位点落在栅格j中，则其所在的位置为aj的概率最大。

[0075] 在j个点中随机选择一个点为初始点，依次与每一个点迭代，经过k次计算后得到xk+1，即为到j个点平均距离最小的点，其中，每一次的迭代计算过程可参见参考文献：“A 
modified Weiszfeld algorithm for the Fermat-Weber location problem”，Yehuda 
Vardi&Cun-Hui Zhang《，Mathematical Programming》volume 90，pages559–566(2001)的
第一部分介绍。

[0076] 实际应用中，可实时更新位置指纹库，因此，建立位置指纹库之后，若再获取到待定位区域内终端新上报的采样点，还可确定该采样点落入的栅格，进而根据该采样点对应
的采样信息，更新该栅格的地理编码与落入该栅格中的各采样点对应的基站的标识和信号
强度之间的对应关系，更新方法同样可参照图2所示流程，在此不再赘述。

[0077] 此外，在具体实施时，针对每个采样点，若确定该采样点的地理编码的前N位与该采样点对应的任一基站的地理编码的前N位不相同，则可将该采样点标记为该基站的奇异
点，当确定为该基站标记的奇异点的个数超过预设个数，比如100个，则确定该基站的位置
已发生变化，此时，可以删除位置指纹库中存储的包含该基站的标识的对应关系，并针对为
该基站标记的每个奇异点，确定该奇异点落入的栅格，进而建立该栅格的地理编码与该基
站的标识和该奇异点对应的该基站的信号强度之间的对应关系，将对应关系保存在位置指
纹库中。

[0078] 一般地，一个基站有几个奇异点是属于正常的情况，但若为每个基站仅记录200个信号强度，为其记录的奇异点个数却高达100个，则可确定该基站确实发生了移位，需要重
新生成该基站的信号强度与地理位置之间的对应关系，此时，可以将为该基站记录的奇异
点反转为正常的采样点，并根据每个采样点重新生成该基站的信号强度与地理位置之间的
对应关系，因为位置指纹库是实时更新的，所以如果待定位区域中某个基站的位置发生了
变化，就可以及时地发现该基站，并更新该基站的画像，这样，即可很好地避免因为基站的
位置发生变化而导致的定位精度下降的问题。

[0079] 参见图3所示，为本申请实施例提供的一种电子设备的结构示意图，该电子设备包括收发器301以及处理器302等物理器件，其中，处理器302可以是一个中央处理单元
(central processing unit，CPU)、微处理器、专用集成电路、可编程逻辑电路、大规模集成
电路、或者为数字处理单元等等。收发器301用于电子设备和其他设备进行数据收发。

[0080] 该电子设备还可以包括存储器303用于存储处理器302执行的软件指令，当然还可以存储电子设备需要的一些其他数据，如电子设备的标识信息、电子设备的加密信息、用户
数据等。存储器303可以是易失性存储器(volatile memory)，例如随机存取存储器
(random-access memory，RAM)；存储器303也可以是非易失性存储器(non-volatile 
memory)，例如只读存储器(read-only memory，ROM)，快闪存储器(flash memory)，硬盘
(hard disk drive，HDD)或固态硬盘(solid-state drive，SSD)、或者存储器303是能够用
于携带或存储具有指令或数据结构形式的期望的程序代码并能够由计算机存取的任何其
他介质，但不限于此。存储器303可以是上述存储器的组合。

[0081] 本申请实施例中不限定上述处理器302、存储器303以及收发器301之间的具体连接介质。本申请实施例在图3中仅以存储器303、处理器302以及收发器301之间通过总线304
连接为例进行说明，总线在图3中以粗线表示，其它部件之间的连接方式，仅是进行示意性
说明，并不引以为限。所述总线可以分为地址总线、数据总线、控制总线等。为便于表示，图3
中仅用一条粗线表示，但并不表示仅有一根总线或一种类型的总线。

[0082] 处理器302可以是专用硬件或运行软件的处理器，当处理器302可以运行软件时，处理器302读取存储器303存储的软件指令，并在所述软件指令的驱动下，执行前述实施例
中涉及的位置指纹库的建立方法。

[0083] 当本申请实施例中提供的方法以软件或硬件或软硬件结合实现的时候，电子设备中可以包括多个功能模块，每个功能模块可以包括软件、硬件或其结合。具体的，参见图4所
示，为本申请实施例提供的位置指纹库的建立装置的结构示意图，包括编码模块401、确定
模块402、建立模块403。

[0084] 编码模块401，用于对待定位区域进行栅格划分，利用geo-hash算法对每个栅格的地理位置信息进行编码，得到该栅格的地理编码；

[0085] 确定模块402，用于获取所述待定位区域内各终端上报的采样点，每个采样点对应的采样信息至少包括上报该采样点时终端的地理位置信息、为该终端提供通信服务的基站
的标识信息和信号强度信息，利用geo-hash算法对所述地理位置信息进行编码，得到该采
样点的地理编码，若确定该采样点的地理编码的前N位与所述基站的地理编码的前N位相
同，则确定所述基站的位置未发生变化，并将具有该采样点的地理编码的栅格确定为该采
样点落入的栅格，其中，所述基站的地理编码根据所述基站在所述待定位区域中的位置预
先估计，N为整数；

[0086] 建立模块403，用于针对每个栅格，建立所述栅格的地理编码与落入该栅格中的各采样点对应的基站的标识和信号强度之间的对应关系，将所述对应关系保存在位置指纹库
中。

[0087] 在一种可能的实施方式下，确定模块402，还用于将所述对应关系保存在位置指纹库中之后，若再获取到所述待定位区域内终端新上报的采样点，则确定所述采样点落入的
栅格；

[0088] 建立模块403，还用于根据所述采样点对应的采样信息，更新该栅格的地理编码与落入该栅格中的各采样点对应的基站的标识和信号强度之间的对应关系。

[0089] 在一种可能的实施方式下，建立模块403具体用于针对每个栅格，根据以下步骤建立或更新该栅格的地理编码与落入该栅格中的采样点对应的基站的标识和信号强度之间
的对应关系：

[0090] 对落入该栅格中的每个采样点，对所述采样点对应的每个基站，确定已获取到的包含所述基站的标识信息的采样点个数；

[0091] 判断采样点个数是否大于预设值；

[0092] 若是，则确定所述采样点对应的所述基站的信号强度在保存的所述基站所有的信号强度中的排名，当确定所述排名大于或者等于所述预设值时，建立该栅格的地理编码与
所述基站的标识和信号强度之间的对应关系；

[0093] 若否，则建立该栅格的地理编码与所述基站的标识和信号强度之间的对应关系。

[0094] 在一种可能的实施方式下，确定模块402，还用于若确定该采样点的地理编码的前N位与该采样点对应的任一基站的地理编码的前N位不相同，则将该采样点标记为所述基站
的奇异点；

[0095] 建立模块403，还用于若为所述基站标记的奇异点的个数超过预设个数，则确定所述基站的位置已发生变化，删除所述位置指纹库中存储的包含所述基站的标识的对应关
系，并针对为所述基站标记的每个奇异点，确定所述奇异点落入的栅格，建立该栅格的地理
编码与所述基站的标识和所述奇异点对应的所述基站的信号强度之间的对应关系，将所述
对应关系保存在所述位置指纹库中。

[0096] 在一种可能的实施方式下，还包括：

[0097] 接收模块404，用于在将所述对应关系保存在位置指纹库中之后，接收定位请求，所述定位请求中携带有当前为终端提供通信服务的基站的标识信息和信号强度信息；

[0098] 查询模块405，用于从所述位置指纹库中查询包含所述基站的标识信息和信号强度信息的至少一个栅格；

[0099] 定位模块406，用于根据所述至少一个栅格对所述终端进行定位，并将定位结果发送给所述终端。

[0100] 在一种可能的实施方式下，若对每个栅格记录有落入该栅格中的采样点个数，定位模块406具体用于：

[0101] 根据落入所述至少一个栅格中每个栅格中的采样点个数，利用Weiszfeld算法确定所述至少一个栅格的质心点；

[0102] 将所述质心点所在的地理位置作为对所述终端的定位结果。

[0103] 本申请实施例中对模块的划分是示意性的，仅仅为一种逻辑功能划分，实际实现时可以有另外的划分方式，另外，在本申请各个实施例中的各功能模块可以集成在一个处
理器中，也可以是单独物理存在，也可以两个或两个以上模块集成在一个模块中。各个模块
相互之间的耦合可以是通过一些接口实现，这些接口通常是电性通信接口，但是也不排除
可能是机械接口或其它的形式接口。因此，作为分离部件说明的模块可以是或者也可以不
是物理上分开的，既可以位于一个地方，也可以分布到同一个或不同设备的不同位置上。上
述集成的模块既可以采用硬件的形式实现，也可以采用软件功能模块的形式实现。

[0104] 本申请实施例还提供了一种计算机可读存储介质，存储为执行上述处理器所需执行的计算机可执行指令，其包含用于执行上述处理器所需执行的程序。

[0105] 在一些可能的实施方式中，本申请提供的位置指纹库的建立方法的各个方面还可以实现为一种程序产品的形式，其包括程序代码，当所述程序产品在电子设备上运行时，所
述程序代码用于使所述电子设备执行本说明书上述描述的根据本申请各种示例性实施方
式的位置指纹库的建立方法中的步骤。

[0106] 所述程序产品可以采用一个或多个可读介质的任意组合。可读介质可以是可读信号介质或者可读存储介质。可读存储介质例如可以是——但不限于——电、磁、光、电磁、红
外线、或半导体的系统、装置或器件，或者任意以上的组合。可读存储介质的更具体的例子
(非穷举的列表)包括：具有一个或多个导线的电连接、便携式盘、硬盘、随机存取存储器
(RAM)、只读存储器(ROM)、可擦式可编程只读存储器(EPROM或闪存)、光纤、便携式紧凑盘只
读存储器(CD-ROM)、光存储器件、磁存储器件、或者上述的任意合适的组合。

[0107] 本申请的实施方式的用于位置指纹库的建立的程序产品可以采用便携式紧凑盘只读存储器(CD-ROM)并包括程序代码，并可以在计算设备上运行。然而，本申请的程序产品
不限于此，在本文件中，可读存储介质可以是任何包含或存储程序的有形介质，该程序可以
被指令执行系统、装置或者器件使用或者与其结合使用。

[0108] 可读信号介质可以包括在基带中或者作为载波一部分传播的数据信号，其中承载了可读程序代码。这种传播的数据信号可以采用多种形式，包括——但不限于——电磁信
号、光信号或上述的任意合适的组合。可读信号介质还可以是可读存储介质以外的任何可
读介质，该可读介质可以发送、传播或者传输用于由指令执行系统、装置或者器件使用或者
与其结合使用的程序。

[0109] 可读介质上包含的程序代码可以用任何适当的介质传输，包括——但不限于——无线、有线、光缆、RF等等，或者上述的任意合适的组合。

[0110] 可以以一种或多种程序设计语言的任意组合来编写用于执行本申请操作的程序代码，所述程序设计语言包括面向对象的程序设计语言—诸如Java、C++等，还包括常规的
过程式程序设计语言—诸如“C”语言或类似的程序设计语言。程序代码可以完全地在用户
计算设备上执行、部分地在用户设备上执行、作为一个独立的软件包执行、部分在用户计算
设备上部分在远程计算设备上执行、或者完全在远程计算设备或服务器上执行。在涉及远
程计算设备的情形中，远程计算设备可以通过任意种类的网络——包括局域网(LAN)或广
域网(WAN)—连接到用户计算设备，或者，可以连接到外部计算设备(例如利用因特网服务
提供商来通过因特网连接)。

[0111] 应当注意，尽管在上文详细描述中提及了装置的若干单元或子单元，但是这种划分仅仅是示例性的并非强制性的。实际上，根据本申请的实施方式，上文描述的两个或更多
单元的特征和功能可以在一个单元中具体化。反之，上文描述的一个单元的特征和功能可
以进一步划分为由多个单元来具体化。

[0112] 此外，尽管在附图中以特定顺序描述了本申请方法的操作，但是，这并非要求或者暗示必须按照该特定顺序来执行这些操作，或是必须执行全部所示的操作才能实现期望的
结果。附加地或备选地，可以省略某些步骤，将多个步骤合并为一个步骤执行，和/或将一个
步骤分解为多个步骤执行。

[0113] 本领域内的技术人员应明白，本申请的实施例可提供为方法、系统、或计算机程序产品。因此，本申请可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实
施例的形式。而且，本申请可采用在一个或多个其中包含有计算机可用程序代码的计算机
可用存储介质(包括但不限于磁盘存储器、CD-ROM、光学存储器等)上实施的计算机程序产
品的形式。

[0114] 本申请是参照根据本申请实施例的方法、装置(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流
程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序
指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产
生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实
现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。

[0115] 这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指
令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或
多个方框中指定的功能。

[0116] 这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或
其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一
个方框或多个方框中指定的功能的步骤。

[0117] 尽管已描述了本申请的优选实施例，但本领域内的技术人员一旦得知了基本创造性概念，则可对这些实施例作出另外的变更和修改。所以，所附权利要求意欲解释为包括优
选实施例以及落入本申请范围的所有变更和修改。

[0118] 显然，本领域的技术人员可以对本申请进行各种改动和变型而不脱离本申请的精神和范围。这样，倘若本申请的这些修改和变型属于本申请权利要求及其等同技术的范围
之内，则本申请也意图包含这些改动和变型在内。