CN103874015B - 一种识别Wi-Fi位置搬迁的方法和装置 - Google Patents

Abstract

本发明提供了一种识别Wi‑Fi位置搬迁的方法和装置，其中方法包括：S1、获取各个Wi‑Fi采集点所采集的数据；S2、依据所获取的采集数据将各个Wi‑Fi的采集点聚合成堆；S3、根据堆的分布情况识别出采集过程中位置发生搬迁的Wi‑Fi，并推算出该Wi‑Fi的新位置。本发明能够准确识别出采集过程中位置发生搬迁的Wi‑Fi，并推算出该Wi‑Fi的新位置，同时也能够识别并过滤具有同一个MAC地址的不同Wi‑Fi和用户用移动终端自建的Wi‑Fi。

Description

一种识别Wi-Fi位置搬迁的方法和装置

【技术领域】

本发明涉及无线定位技术，尤其涉及一种识别Wi-Fi位置搬迁的方法和装置。

【背景技术】

随着移动互联网应用的不断发展，基于位置的服务越来越受到人们的欢迎，在定位服务中，除了常用的GPS定位技术外，利用无线Wi-Fi进行定位也得到了越来越多的应用。通过Wi-Fi进行定位需要预先获取各个Wi-Fi接入点（AP）的位置，之后再进一步通过Wi-Fi的位置对用户所在位置定位。目前，构建Wi-Fi位置数据库的方法通常是根据采集点获得的Wi-Fi信息以及采集点的位置推算出Wi-Fi的位置。

在采集Wi-Fi信息的过程中，会出现一个Wi-Fi的采集点分布半径过大的情况，导致这种情况的原因主要有三种：一、部分无线路由器厂家生产的路由器不规范，存在多个无线路由器的MAC地址相同情况，导致同一个MAC地址的Wi-Fi分布在多个地方；二、用户利用移动终端自建的Wi-Fi接入点，这类Wi-Fi通常位置都不固定，经常发生变动；三、某一无线路由器的位置在采集过程中发生了变动。当某一Wi-Fi的采集点分布半径过大时，现有的做法通常是认为数据采集有误，直接过滤该Wi-Fi的采集数据。然而，分析上述三种原因可以看出，具有相同MAC地址的多个无线路由器以及用户利用移动终端自建的Wi-Fi接入点不适合用于提供定位服务，而位置发生变迁的无线路由器仍然可以利用其变迁后的新位置提供定位服务，若直接过滤采集点分布半径过大的Wi-Fi采集数据，则会丢失这部分可用的数据。

【发明内容】

有鉴于此，本发明提供了一种识别Wi-Fi位置搬迁的方法和装置，能够识别采集过程中位置发生搬迁的Wi-Fi。

具体技术方案如下：

一种识别Wi-Fi位置搬迁的方法，该方法包括：

S1、获取各个Wi-Fi采集点所采集的数据；

S2、依据所获取的采集数据将各个Wi-Fi的采集点聚合成堆；

S3、根据堆的分布情况识别出采集过程中位置发生搬迁的Wi-Fi，并推算出位置发生搬迁的Wi-Fi的新位置。

根据本发明一优选实施例，所述步骤S2具体包括：

将某一Wi-Fi的每一个采集点初始化为各个独立的堆，若两个堆之间的最小距离小于预先设定的阈值，则将这两个堆合并为一个堆，其中，两个堆之间的最小距离为两个堆的采集点之间的距离的最小值。

根据本发明一优选实施例，所述步骤S3具体包括：

若某一Wi-Fi的采集点聚合成两堆且该两堆各自最小外接圆的半径小于预先设定的阈值，且该两堆中采集点覆盖的采集时间无交叠，则判定该Wi-Fi的位置在采集过程中发生了搬迁，根据采集时间较新的采集点推算出该Wi-Fi搬迁后的位置。

根据本发明一优选实施例，该方法还包括下述步骤：

若某一Wi-Fi的采集点分为N堆且该N堆各自最小外接圆的半径小于预先设定的阈值，且该N堆中采集点覆盖的采集时间存在交叠，则判定所采集到的Wi-Fi数据为具有同一MAC地址的多个Wi-Fi，忽略该些数据，其中，N为大于或等于2的整数。

根据本发明一优选实施例，该方法还包括下述步骤：

若某一Wi-Fi的采集点分为N堆且该N堆中存在最小外接圆半径大于预先设定的阈值的堆，则判定所采集到的Wi-Fi数据为用户用移动终端自建的Wi-Fi，忽略该些数据，其中，N为大于或等于1的整数。

一种识别Wi-Fi位置搬迁的装置，该装置包括：

数据收集单元，用于获取各个Wi-Fi采集点所采集的数据；

整合单元，用于依据所获取的采集数据将各个Wi-Fi的采集点聚合成堆；

识别单元，用于根据堆的分布情况识别出采集过程中位置发生搬迁的Wi-Fi，并推算出位置发生搬迁的Wi-Fi的新位置。

根据本发明一优选实施例，所述整合单元具体执行：

将某一Wi-Fi的每一个采集点初始化为各个独立的堆，若两个堆之间的最小距离小于预先设定的阈值，则将这两个堆合并为一个堆，其中，两个堆之间的最小距离为两个堆的采集点之间的距离的最小值。

根据本发明一优选实施例，所述识别单元具体执行：

若某一Wi-Fi的采集点聚合成两堆且该两堆各自最小外接圆的半径小于预先设定的阈值，且该两堆中采集点覆盖的采集时间无交叠，则判定该Wi-Fi的位置在采集过程中发生了搬迁，根据采集时间较新的采集点推算出该Wi-Fi搬迁后的位置。

根据本发明一优选实施例，所述识别单元还执行：

若某一Wi-Fi的采集点分为N堆且该N堆各自最小外接圆的半径小于预先设定的阈值，且该N堆中采集点覆盖的采集时间存在交叠，则判定所采集到的Wi-Fi数据为具有同一MAC地址的多个Wi-Fi，忽略该些数据，其中，N为大于或等于2的整数。

根据本发明一优选实施例，所述识别单元还执行：

若某一Wi-Fi的采集点分为N堆且该N堆中存在最小外接圆半径大于预先设定的阈值的堆，则判定所采集到的Wi-Fi数据为用户用移动终端自建的Wi-Fi，忽略该些数据，其中，N为大于或等于1的整数。

由以上技术方案可以看出，本发明通过将各个Wi-Fi的采集点聚合成堆，能够根据堆的分布情况准确识别出采集过程中位置发生了搬迁的Wi-Fi，避免了误将这类可用的数据过滤，同时还能识别并过滤具有同一MAC地址的Wi-Fi以及用户利用移动终端自建的Wi-Fi。

【附图说明】

图1为本发明实施例一所提供的一种识别Wi-Fi位置搬迁的方法流程图；

图2为本发明实施例一所提供的采集点聚合成堆的示例图；

图3为本发明实施例二所提供的一种识别Wi-Fi位置搬迁的装置示意图。

【具体实施方式】

为了使本发明的目的、技术方案和优点更加清楚，下面结合附图和具体实施例对本发明进行详细描述。

由于采集点只能在Wi-Fi信号的覆盖范围内采集到Wi-Fi的信息，因此，采集点的分布情况能够反映出Wi-Fi的位置信息。本发明正是利用采集点的分布情况并将采集点聚合成堆后，来判断采集过程中某一Wi-Fi的位置是否发生了变动，以及过滤具有同一MAC地址的不同Wi-Fi和用户用移动终端自建的Wi-Fi的。

实施例一

图1为本发明实施例一所提供的一种识别Wi-Fi位置搬迁的方法流程图，如图1所示，该方法包括：

S101、获取在采集点采集的Wi-Fi数据。

在采集点采集的Wi-Fi数据包括Wi-Fi的MAC地址、采集点的GPS坐标，以及当前的采集时刻。Wi-Fi的采集可以通过利用采集车等工具主动进行采集，也可以从用户移动终端所提交的数据中来提取，这部分为现有技术，在此不过多赘述。

S102、将各个Wi-Fi的采集点聚合成堆。

由于Wi-Fi信号的只能覆盖一定的范围，所以只能在某一Wi-Fi周围采集到该Wi-Fi的数据，因此采集点的分布通常都是聚集在Wi-Fi周围。为了能够根据采集点的分布情况准确获得Wi-Fi的位置信息，需要将各个Wi-Fi的采集点聚合成堆，这一过程可以采用下述方法实现：

将某一Wi-Fi的每一个采集点初始化为各个独立的堆，若某两个堆之间的最小距离小于预先设定的阈值，则将这两个堆合并为一个堆，其中，两个堆之间的最小距离为两个堆的采集点之间的距离最小值。为了更好的理解将采集点聚合成堆的方法，下面结合图2所示示例对这一过程进行进一步说明。如图2所示，有A、B、C、D、E、F、G共7个采集点，首先将这7个采集点初始化为各个独立的堆，即每个点形成一个堆，之后开始依据两个堆之间的最小距离，即两个堆的采集点之间距离的最小值对堆进行聚合，例如，以A为例，A到B的距离小于预设的阈值，将A、B所在的堆合并，即A堆和B堆聚合，形成一个堆（为便于描述，可称为AB堆），以此类推，A到D的距离和A到E的距离均小于预设的阈值，将D堆、E堆并入A所在的堆（即AB堆），聚合成ABDE堆，A到C的距离大于预设的阈值，而C到D的距离小于预设的阈值，因此，C堆和ABDE堆的最小距离小于预设阈值，将这两个堆合并，即聚合成ABCDE堆，F堆与ABCDE堆的最小距离为F到E的距离，F到E的距离大于预设的阈值，因此，F堆不与ABCDE堆聚合，同理，G堆到ABCDE的距离大于预设的阈值，G堆不与ABCDE堆聚合，F与G的距离小于预设的阈值，将F堆与G堆聚合形成FG堆，至此，聚合完毕，形成如图2所示的两个堆。两个堆之间的最小距离阈值可以根据需要进行设定。

此外，上述将采集点聚合成堆的过程还可以用层次聚类算法等现有算法实现。

S103、若某一Wi-Fi的采集点聚合成两堆且该两堆各自最小外接圆的半径小于预先设定的阈值，且该两堆中采集点的采集时间无交叠，则判定该Wi-Fi的位置在采集过程中发生了搬迁，根据采集时间较新的采集点推算出该Wi-Fi搬迁后的位置。

将采集点聚合成堆后可以得到各个Wi-Fi的采集点的堆的分布信息，根据这一信息可以判断采集过程中位置发生搬迁了的Wi-Fi，具体判断方法为若某一Wi-Fi的采集点同时满足下述条件，则判定该Wi-Fi的位置发生了搬迁，所述条件具体为：

1）该Wi-Fi的采集点分为两个堆；

2）两个堆各自的最小外接圆的半径均小于预先设定的阈值；

3）两个堆中采集点的采集时间无交叠。

若某一Wi-Fi在采集过程中位置发生了搬迁，那么在其旧的位置处和新的位置处都会存在该Wi-Fi的采集点，根据上述条件便能准确识别这一情况，其中堆的最小外接圆的半径阈值可以根据需要设定，例如，可以设定为普通Wi-Fi的信号覆盖范围的最大值1km。之后再根据两个堆中的采集点的采集时间，利用采集时间较新的堆中采集点的位置信息推算出该Wi-Fi搬迁后的位置。根据采集点的位置信息推算出Wi-Fi的位置可以采用最小外接圆法，或算术平均法，或几何平均法等，这部分为现有技术，在此不过多赘述。

根据本发明实施例所提供的步骤S101-S103所述的方法，可以准确识别出在采集过程中位置发生搬迁的Wi-Fi，并推算出其新的位置，避免了现有方法导致的这部分可用数据的丢失。

更进一步地，本发明还可以包括下述步骤S104-S105，来过滤具有同一MAC地址的Wi-Fi和用户用移动终端自建的Wi-Fi。

S104、若某一Wi-Fi的采集点分为N堆且该N堆各自最小外接圆的半径小于预先设定的阈值，且该N堆中采集点的采集时间存在交叠，则判定所采集到的Wi-Fi数据为具有同一MAC地址的多个Wi-Fi，忽略该些数据，其中，N为大于或等于2的整数。

若有多个不同的Wi-Fi具有相同的MAC地址，则在采集过程中该多个Wi-Fi附近都会存在采集点，即采集点会形成多个堆，且采集时间存在交叠，根据这一特点，便能准确识别出采集数据中具有相同MAC地址的Wi-Fi的数据，由于在定位服务中通常将MAC地址视作是Wi-Fi的唯一身份标识，因此这类Wi-Fi不适合用于定位服务，过滤该些数据。在本步骤的判定中，堆的最小外接圆的半径阈值可以根据需要设定，例如，可以设定为普通Wi-Fi的信号覆盖范围的最大值1km。

S105、若某一Wi-Fi的采集点分为N堆且该N堆中存在最小外接圆半径大于预先设定的阈值的堆，则判定所采集到的Wi-Fi数据为用户用移动终端自建的Wi-Fi，忽略该些数据，其中，N为大于或等于1的整数。

用户利用移动终端自建的Wi-Fi通常位置都非常不固定，具有很强的移动性，若在采集过程中某一用户自建的Wi-Fi发生了移动，则采集点会分布在其移动轨迹的周围，这样的采集点往往跨度较大，即采集点聚合成的堆的最小外接圆的半径较大，根据这一特点，可以识别出采集数据中由用户利用移动终端自建的Wi-Fi的数据，同样，这类Wi-Fi不适合用于定位服务，过滤该些数据。

需要说明的是，上述步骤S103、S104和S105可以按任意顺序进行，也可以同时进行，即对采集过程中位置发生搬迁的Wi-Fi的识别、对具有同一个MAC地址的不同Wi-Fi的识别和对用户用移动终端自建的Wi-Fi的识别可以按任意先后顺序执行，也可以同时执行。

上述为对本发明实施例所提供的识别Wi-Fi位置搬迁的方法进行的描述，可以看出本发明所提供的方法能够准确识别在采集过程中位置发生搬迁的Wi-Fi，与现有技术相比，避免了该部分可用数据被误删除，同时能够识别并过滤具有同一个MAC地址的不同Wi-Fi和用户用移动终端自建的Wi-Fi。

实施例二

图3为本发明实施例二所提供的一种识别Wi-Fi位置搬迁的装置示意图，如图3所示，该装置包括：数据收集单元10、整合单元20、识别单元30。

数据收集单元10，用于获取各个Wi-Fi采集点所采集的数据。

数据收集单元10获取各个采集点采集的Wi-Fi数据，具体包括Wi-Fi的MAC地址、采集点的GPS坐标，以及当前的采集时刻。Wi-Fi的采集可以通过利用采集车等工具主动进行采集，也可以从用户移动终端所提交的数据中来提取，这部分为现有技术，在此不过多赘述。

整合单元20，用于依据所获取的采集数据将各个Wi-Fi的采集点聚合成堆。

为了能够根据采集点的分布情况准确获得Wi-Fi的位置信息，整合单元20需要将各个Wi-Fi的采集点聚合成堆，这一过程可以执行下述操作实现：

将某一Wi-Fi的每一个采集点初始化为各个独立的堆，若某两个堆之间的最小距离小于预先设定的阈值，则将这两个堆合并为一个堆，其中，两个堆之间的最小距离为两个堆的采集点之间的距离最小值。其中，两个堆之间的最小距离阈值可以根据需要进行设定。

此外，上述整合单元20将采集点聚合成堆的过程还可以用层次聚类算法等现有算法实现。

识别单元30，用于根据堆的分布情况识别出采集过程中位置发生搬迁的Wi-Fi，并推算出该Wi-Fi的新位置。

整合单元20将采集点聚合成堆后可以得到各个Wi-Fi的采集点的堆的分布信息，识别单元30可以根据这一信息判断采集过程中位置发生搬迁了的Wi-Fi，具体判断方法为若某一Wi-Fi的采集点同时满足下述条件，则判定该Wi-Fi的位置发生了搬迁，所述条件具体为：

1）该Wi-Fi的采集点分为两个堆；

2）两个堆各自的最小外接圆的半径均小于预先设定的阈值；

3）两个堆中采集点的采集时间无交叠。

若某一Wi-Fi在采集过程中位置发生了搬迁，那么在其旧的位置处和新的位置处都会存在该Wi-Fi的采集点，根据上述条件便能准确识别这一情况，其中堆的最小外接圆的半径阈值可以根据需要设定，例如，可以设定为普通Wi-Fi的信号覆盖范围的最大值1km。之后再根据两个堆中的采集点的采集时间，利用采集时间较新的堆中采集点的位置信息推算出该Wi-Fi搬迁后的位置。根据采集点的位置信息推算出Wi-Fi的位置可以采用最小外接圆法，或算术平均法，或几何平均法等，这部分为现有技术，在此不过多赘述。

更进一步地，识别单元30还可以执行下述两个操作，来过滤具有同一MAC地址的Wi-Fi和用户用移动终端自建的Wi-Fi：

1）若某一Wi-Fi的采集点分为N堆且该N堆各自最小外接圆的半径小于预先设定的阈值，且该N堆中采集点的采集时间存在交叠，则判定所采集到的Wi-Fi数据为具有同一MAC地址的多个Wi-Fi，忽略该些数据，其中，N为大于或等于2的整数。

若有多个不同的Wi-Fi具有相同的MAC地址，则在采集过程中该多个Wi-Fi附近都会存在采集点，即采集点会形成多个堆，且采集时间存在交叠，根据这一特点，便能准确识别出采集数据中具有相同MAC地址的Wi-Fi的数据，由于在定位服务中通常将MAC地址视作是Wi-Fi的唯一身份标识，因此这类Wi-Fi不适合用于定位服务，过滤该些数据。在本步骤的判定中，堆的最小外接圆的半径阈值可以根据需要设定，例如，可以设定为普通Wi-Fi的信号覆盖范围的最大值1km。

2）若某一Wi-Fi的采集点分为N堆且该N堆中存在最小外接圆半径大于预先设定的阈值的堆，则判定所采集到的Wi-Fi数据为用户用移动终端自建的Wi-Fi，忽略该些数据，其中，N为大于或等于1的整数。

用户利用移动终端自建的Wi-Fi通常位置都非常不固定，具有很强的移动性，若在采集过程中某一用户自建的Wi-Fi发生了移动，则采集点会分布在其移动轨迹的周围，这样的采集点往往跨度较大，即采集点聚合成的堆的最小外接圆的半径较大，根据这一特点，可以识别出采集数据中由用户利用移动终端自建的Wi-Fi的数据，同样，这类Wi-Fi不适合用于定位服务，过滤该些数据。

上述为对本发明实施例所提供的识别Wi-Fi位置搬迁的装置进行的描述，可以看出本发明所提供的装置能够准确识别在采集过程中位置发生搬迁的Wi-Fi，与现有技术相比，避免了该部分可用数据被误删除，同时能够识别并过滤具有同一个MAC地址的不同Wi-Fi和用户用移动终端自建的Wi-Fi。

通过本发明，能够准确识别在采集过程中位置发生搬迁的Wi-Fi，并推算出Wi-Fi搬迁后的位置，之后，可将该数据用于构建电子定位数据库来为用户提供定位服务，同时，本发明也可避免将具有同一个MAC地址的不同Wi-Fi和用户用移动终端自建的Wi-Fi这类不适合提供定位服务的数据加入电子定位数据库。

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

Claims (6)

1.一种识别Wi-Fi位置搬迁的方法，其特征在于，该方法包括：

S1、获取各个Wi-Fi采集点所采集的数据；

S2、依据所获取的采集数据将各个Wi-Fi的采集点聚合成堆；

S3、根据堆的分布情况识别出采集过程中位置发生搬迁的Wi-Fi，并推算出位置发生搬迁的Wi-Fi的新位置；

所述S2具体包括：

将某一Wi-Fi的每一个采集点初始化为各个独立的堆，若两个堆之间的最小距离小于预先设定的阈值，则将这两个堆合并为一个堆，其中，两个堆之间的最小距离为两个堆的采集点之间的距离的最小值；

所述S3具体包括：

若某一Wi-Fi的采集点聚合成两堆且该两堆各自最小外接圆的半径小于预先设定的阈值，且该两堆中采集点覆盖的采集时间无交叠，则判定该Wi-Fi的位置在采集过程中发生了搬迁，根据采集时间较新的采集点推算出该Wi-Fi搬迁后的位置。

2.根据权利要求1所述的方法，其特征在于，该方法还包括下述步骤：

若某一Wi-Fi的采集点分为N堆且该N堆各自最小外接圆的半径小于预先设定的阈值，且该N堆中采集点覆盖的采集时间存在交叠，则判定所采集到的数据为具有同一MAC地址的多个Wi-Fi，忽略该些数据，其中，N为大于或等于2的整数。

3.根据权利要求1所述的方法，其特征在于，该方法还包括下述步骤：

若某一Wi-Fi的采集点分为N堆且该N堆中存在最小外接圆半径大于预先设定的阈值的堆，则判定所采集到的数据为用户用移动终端自建的Wi-Fi，忽略该些数据，其中，N为大于或等于1的整数。

4.一种识别Wi-Fi位置搬迁的装置，其特征在于，该装置包括：

数据收集单元，用于获取各个Wi-Fi采集点所采集的数据；

整合单元，用于依据所获取的采集数据将各个Wi-Fi的采集点聚合成堆；

识别单元，用于根据堆的分布情况识别出采集过程中位置发生搬迁的Wi-Fi，并推算出位置发生搬迁的Wi-Fi的新位置；

所述整合单元具体执行：

将某一Wi-Fi的每一个采集点初始化为各个独立的堆，若两个堆之间的最小距离小于预先设定的阈值，则将这两个堆合并为一个堆，其中，两个堆之间的最小距离为两个堆的采集点之间的距离的最小值；

所述识别单元具体执行：

若某一Wi-Fi的采集点聚合成两堆且该两堆各自最小外接圆的半径小于预先设定的阈值，且该两堆中采集点覆盖的采集时间无交叠，则判定该Wi-Fi的位置在采集过程中发生了搬迁，根据采集时间较新的采集点推算出该Wi-Fi搬迁后的位置。

5.根据权利要求4所述的装置，其特征在于，所述识别单元还执行：

若某一Wi-Fi的采集点分为N堆且该N堆各自最小外接圆的半径小于预先设定的阈值，且该N堆中采集点覆盖的采集时间存在交叠，则判定所采集到的数据为具有同一MAC地址的多个Wi-Fi，忽略该些数据，其中，N为大于或等于2的整数。

6.根据权利要求4所述的装置，其特征在于，所述识别单元还执行：

若某一Wi-Fi的采集点分为N堆且该N堆中存在最小外接圆半径大于预先设定的阈值的堆，则判定所采集到的数据为用户用移动终端自建的Wi-Fi，忽略该些数据，其中，N为大于或等于1的整数。