Techniques for wireless transmitter location detection

• US 9,838,834 B2
• Filed: 12/21/2012
• Issued: 12/05/2017
• Est. Priority Date: 12/21/2012
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Hofleitner, Aude, Moreels, Pierre
• Primary Examiner(s): Wang-Hurst, Kathy
• Assistant Examiner(s): ELNOUBI, SAID M
• Application Number:
  US13/724,758
• Publication Number:
  US 20140179339A1
• Time in Patent Office: 1,810 Days
• Field of Search: 4554561, 4554566, 4554562, 4554565
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/029 Location-based management or tracking services

Abstract

Techniques for wireless transmitter location detection are described. An apparatus may comprise a processor circuit and a location database generator component. The location database generator component may comprise: a logging component operative on the processor circuit to receive a plurality of location data packages, the location data packages comprising locations and associated wireless transmitter identifiers, and to log the location data packages into a location database, the location database comprising a plurality of tuples of the locations and the wireless transmitter identifiers; and an analysis component operative on the processor circuit to construct a transmitter mapping from wireless transmitter identifiers to locations based on the plurality of tuples of the location database. Other embodiments are described and claimed.

Claims

1. An apparatus, comprising:

a processor circuit;

a storage medium arranged to store a location database generator component comprising;

a logging component operative on the processor circuit to receive multiple location data packages each comprising one or more locations and associated wireless transmitter identifiers, and log the location data packages into a location database comprising tuples of locations and wireless transmitter identifiers; and

an analysis component operative on the processor circuit to;

create an initial cluster of one or more tuples, each tuple in the initial cluster comprising a same wireless transmitter identifier;

estimate an initial location of a first wireless transmitter based on the locations of the tuples in the initial cluster;

identify a candidate tuple from the initial cluster that falls outside a defined distance from the initial location, the defined distance corresponding to an estimated maximum range for a type of the first wireless transmitter;

create a new cluster comprising the identified candidate tuple and estimate a second location of a second wireless transmitter based on the location of the identified candidate tuple;

assign tuples from the initial cluster to the new cluster when a distance from a tuple from the initial cluster is closer to the second location than to the estimated initial location of the first wireless transmitter, wherein a tuple assigned to the new cluster is removed from the initial cluster;

estimate a new location of the first wireless transmitter based on any tuples remaining in the initial cluster; and

construct a transmitter mapping from the wireless transmitter identifier to the new location of the first wireless transmitter and to the second location of the second wireless transmitter; and

a location estimation component operative on the processor circuit to receive a request for location assistance from a mobile device, the request comprising the first wireless transmitter identifier and a second wireless transmitter identifier, determine a third location for the second wireless transmitter identifier, select one of the locations mapped to the first wireless transmitter identifier according to which of the first wireless transmitter identifier locations is closer to the third location, and send the selected location to the mobile device.

2. The apparatus of claim 1, one or more of the locations of the received location data packages comprising global positioning system locations of mobile devices.

3. The apparatus of claim 1, one or more of the wireless transmitter identifiers of the received location data packages comprising identifier numbers for cell sites to which mobile devices were connected when determining one or more of the locations.

4. The apparatus of claim 1, one or more of the wireless transmitter identifiers of the received location data packages comprising identifier numbers for Institute of Electrical and Electronics Engineers (IEEE) 802.11 access points to which mobile devices were connected when determining one or more of the locations.

5. The apparatus of claim 1, the analysis component operative to determine an estimated transmitter location for a cluster of tuples as a center of locations of tuples assigned to the cluster of tuples.

6. The apparatus of claim 5, the analysis component operative to create an additional new cluster in the clusters of tuples when a candidate tuple within a current cluster falls outside a predefined distance of any existing cluster, assign the candidate tuple to the additional new cluster, determine an estimated transmitter location for the additional new cluster, and assign tuples to the additional new cluster when the tuples are closer to the estimated transmitter location for the additional new cluster than any existing estimated transmitter location associated with each of the tuples.

7. The apparatus of claim 6, the analysis component operative to repeatedly iterate through creating clusters, assigning tuples to clusters, and determining estimated transmitter locations until an iteration results in a stable assignment of tuples to clusters;

and construct the transmitter mapping from wireless transmitter identifiers to locations constructed based on the resulting stable assignment of tuples to clusters.

8. A computer-implemented method, comprising:

logging a plurality of location data packages into a location database, the location data packages comprising locations and wireless transmitter identifiers, the location database comprising tuples of the locations and the wireless transmitter identifiers;

creating an initial cluster of one or more tuples, each tuple in the initial cluster comprising a same wireless transmitter identifier;

estimating an initial location of a first wireless transmitter based on the locations of the tuples in the initial cluster;

identifying a candidate tuple from the initial cluster that falls outside a defined distance from the initial location, the defined distance corresponding to an estimated maximum range for a type of the first wireless transmitter;

creating a new cluster comprising the identified candidate tuple and estimate a second location of a second wireless transmitter based on the location of the identified candidate tuple;

assigning tuples from the initial cluster to the new cluster when a distance from a tuple from the initial cluster is closer to the second location than to the estimated initial location of the first wireless transmitter, wherein a tuple assigned to the new cluster is removed from the initial cluster;

estimating a new location of the first wireless transmitter based on any tuples remaining in the initial cluster;

constructing a transmitter mapping from the wireless transmitter identifier to the new location of the first wireless transmitter and to the second location of the second wireless transmitter;

receiving a request for location assistance from a mobile device, the request comprising the first wireless transmitter identifier and a second wireless transmitter identifier;

determining a third location for the second wireless transmitter identifier;

selecting one of the locations mapped to the first wireless transmitter identifier according to which of the first wireless transmitter identifier locations is closer to the third location; and

sending the selected location to the mobile device.

9. The computer-implemented method of claim 8, one or more of the locations of the received plurality of location data packages comprising global positioning system locations of mobile devices.

10. The computer-implemented method of claim 8, one or more of the wireless transmitter identifiers of the received plurality of location data packages comprising identifier numbers for cell sites mobile devices were connected to while determining one or more of the locations.

11. The computer-implemented method of claim 8, comprising:

determining an estimated transmitter location for a cluster of tuples as a center of locations of tuples assigned to the cluster of tuples.

12. The computer-implemented method of claim 11, comprising:

creating an additional new cluster in the clusters of tuples when a candidate tuple within a current cluster falls outside a predefined distance of any existing cluster;

assigning the candidate tuple to the additional new cluster;

determining an estimated transmitter location for the additional new cluster; and

assigning tuples with to the additional new cluster if the tuples are closer to the estimated transmitter location for the additional new cluster than any existing estimated transmitter location associated with each of the tuples.

13. The computer-implemented method of claim 12, comprising:

iterating repeatedly through creating clusters, assigning tuples to clusters, and determining estimated transmitter locations until an iteration results in a stable assignment of tuples to clusters; and

constructing the transmitter mapping from wireless transmitter identifiers to locations constructed based on the resulting stable assignment of tuples to clusters.

14. At least one non-transitory computer-readable storage medium comprising instructions that, when executed, cause a system to:

receive a plurality of location data packages from a plurality of mobile devices, the location data packages comprising locations and wireless transmitter identifiers;

log the plurality of location data packages into a location database, the location database comprising tuples of locations and wireless transmitter identifiers;

create an initial cluster of one or more tuples, each tuple in the initial cluster comprising a same wireless transmitter identifier;

estimate an initial location of a first wireless transmitter based on the locations of the tuples in the initial cluster;

identify a candidate tuple from the initial cluster that falls outside a defined distance from the initial location, the defined distance corresponding to an estimated maximum range for a type of the first wireless transmitter;

create a new cluster comprising the identified candidate tuple and estimate a second location of a second wireless transmitter based on the location of the identified candidate tuple;

assign tuples from the initial cluster to the new cluster when a distance from a tuple from the initial cluster is closer to the second location than to the estimated initial location of the first wireless transmitter, wherein a tuple assigned to the new cluster is removed from the initial cluster;

estimate a new location of the first wireless transmitter based on any tuples remaining in the initial cluster; and

construct a transmitter mapping from the wireless transmitter identifier to the new location of the first wireless transmitter and to the second location of the second wireless transmitter;

receive a request for location assistance from a mobile device, the request comprising the first wireless transmitter identifier and a second wireless transmitter identifier;

determine a third location for the second wireless transmitter identifier;

select one of the locations mapped to the first wireless transmitter identifier according to which of the first wireless transmitter identifier locations is closer to the third location; and

send the selected location to the mobile device.

15. The non-transitory computer-readable storage medium of claim 14, one or more of the locations of the received plurality of location data packages comprising global positioning system locations of the mobile devices.

16. The non-transitory computer-readable storage medium of claim 14, one or more of the wireless transmitter identifiers of the received plurality of location data packages comprising identifier numbers for cell sites the mobile devices were connected to while determining one or more of the locations.

17. The non-transitory computer-readable storage medium of claim 14, one or more of the wireless transmitter identifiers of the received plurality of location data packages comprising identifier numbers for Wi-Fi access points the mobile devices were connected to while determining one or more of the locations.

18. The non-transitory computer-readable storage medium of claim 14, comprising instructions that when executed cause the system to:

determine an estimated transmitter location for a cluster of tuples as a center of locations of tuples assigned to the cluster of tuples.

19. The non-transitory computer-readable storage medium of claim 18, comprising instructions that when executed cause the system to:

create an additional new cluster in the clusters of tuples when a candidate tuple within a current cluster falls outside a predefined distance of any existing cluster;

assign the candidate tuple to the additional new cluster;

determine an estimated transmitter location for the additional new cluster; and

assign tuples to the additional new cluster if the tuples are closer to the estimated transmitter location for the additional new cluster than any existing estimated transmitter location associated with each of the tuples.

20. The non-transitory computer-readable storage medium of claim 19, comprising instructions that when executed cause the system to:

iterate repeatedly through creating clusters, assigning tuples to clusters, and determining estimated transmitter locations until an iteration results in a stable assignment of tuples to clusters; and

construct the transmitter mapping from wireless transmitter identifiers to locations constructed based on the resulting stable assignment of tuples to clusters.