Method and Apparatus for On-Device Positioning Using Compressed Fingerprint Archives

• US 20110269479A1
• Filed: 07/13/2010
• Published: 11/03/2011
• Est. Priority Date: 12/04/2009
• Status: Active Grant

• Current Assignee: RPX Corporation
• Original Assignee: Nokia Corporation
• Inventors: Ledlie, Jonathan
• Granted Patent: US 8,660,577 B2
• Time in Patent Office: Days
• US Class Current: 455/456.1
• CPC Class Codes: G01S 11/06 using intensity measurements
• CPC Class Codes: G01S 5/0081 Transmission between base stations
• CPC Class Codes: G01S 5/02529 not involving signal parameters, i.e. only involving identifiers
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Abstract

A method and apparatus are provided for on-device positioning using compressed fingerprint archives. The method and apparatus may be configured to provide compression of localization fingerprints, to facilitate efficient on-device positioning based on the RF fingerprint model, and to estimate the physical distance between two or more devices. Embodiments of the method may receive a space-to-access point histogram that corresponds to an access point as observed in a space. The histogram may be normalized and a mean and standard deviation may be calculated from the histogram. A weight may be assigned to the access point corresponding to the frequency with which the access point is observed within the space. A mean, standard deviation, and weight may be calculated and assigned for each of a plurality of access points as observed within a space. The mean, standard deviation, and weight of each access point may be combined to form a data triple. The data triples may be combined to form a fingerprint of access points observed from that space. The data triple or plurality of data triples with the lowest assigned weight(s) may be removed from the fingerprint.

Claims

1. A method comprising:

receiving a space-to-access point histogram corresponding to an access point as observed in a space;

normalizing the space-to-access point histogram;

calculating parameters of the normalized space-to-access point histogram; and

applying a feature selection function to the access point to assign a value to the access point.

2. A method according to claim 1, wherein the feature selection function is a weighting function and wherein the value is a weight that corresponds to the frequency with which the access point is observed within the space.

3. A method according to claim 1, wherein the parameters include the mean of the normalized space-to-access point histogram and the standard deviation of the normalized space-to-access point histogram.

4. A method according to claim 3, wherein each of the mean, the standard deviation, and the value are combined to form a data triple that represents the access point as observed in the space.

5. A method according to claim 4, wherein the method is repeated for each access point observed in the space such that a plurality of access points observed in the space are each represented by a data triple.

6. A method according to claim 5, wherein the plurality of data triples comprise a fingerprint.

7. A method according to claim 6, wherein at least one data triple, corresponding to the least significant value, is removed from the fingerprint creating a compressed fingerprint.

8. A method according to claim 7, wherein the compressed fingerprint is sent to a mobile device.

9. An apparatus comprising at least one processor and at least one memory including computer program code, the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to:

receive a space-to-access point histogram corresponding to an access point as observed in a space;

normalize the space-to-access point histogram;

calculate parameters for the normalized space-to-access point histogram; and

apply a feature selection function to the access point to assign a value to the access point.

10. An apparatus according to claim 9, wherein the computer program code, with the at least one processor, is further configured to cause the apparatus to

receive a plurality of space-to-access point histograms corresponding to a plurality of access points as observed in the space;

normalize each of the plurality of space-to-access point histograms;

calculate parameters for each of the plurality of normalized space-to-access point histograms; and

apply a feature selection function to each of the plurality of access points to assign a value to each of the plurality of access points.

11. An apparatus according to claim 10, wherein the feature selection function is a weighting function and wherein the value is a weight that corresponds to the frequency with which the access point is observed within the space.

12. An apparatus according to claim 10, wherein calculating the parameters for the plurality of normalized space-to-access point histogram includes calculating the mean of each of the plurality of normalized space-to-access point histogram and calculating the standard deviation for each of the plurality of normalized space-to-access point histogram.

13. An apparatus according to claim 12, wherein, each of the mean, standard deviation, and value corresponding to an access point are combined to form a data triple that represents the access point as observed in the space.

14. A method according to claim 13, wherein the plurality of data triples comprise a fingerprint.

15. A method according to claim 14, wherein at least one data triple, corresponding to the least significant value, is removed from the fingerprint creating a compressed fingerprint.

16. A method according to claim 15, wherein the compressed fingerprint is sent to a mobile device.

17. A computer program product comprising at least one computer-readable storage medium having computer-executable program code instructions stored therein, the computer-executable program code instructions comprising:

program code instructions for receiving a space-to-access point histogram corresponding to an access point as observed in a space;

program code instructions for normalizing the space-to-access point histogram;

program code instructions for calculating parameters of the normalized space-to-access point histogram; and

program code instructions for applying a feature selection function to the access point to assign a value to the access point.

18. A computer program product according to claim 17, wherein the computer-executable program code instructions further comprise:

program code instructions for receiving a plurality of space-to-access point histograms corresponding to a plurality of access points as observed in the space;

program code instructions for normalizing each of the plurality of space-to access point histograms;

program code instructions for calculating parameters for each of the plurality of normalized space-to-access point histograms; and

program code instructions for applying a feature selection function to each of the plurality of access points to assign a value to each of the plurality of access points.

19. A computer program product according to claim 18, wherein the feature selection function is a weighting function and wherein the value is a weight that corresponds to the frequency with which the access point is observed within the space.

20. A computer program product according to claim 18, wherein the program code instructions for calculating parameters of the plurality of normalized space-to-access point histograms includes program code instructions for calculating the mean of each of the plurality of normalized space-to-access point histograms and calculating the standard deviation of each of the plurality of normalized space-to-access point histograms.

21. A computer program product according to claim 20, wherein each of the mean, standard deviation, and weight corresponding to an access point are combined to form a data triple that represents the access point as observed in the space

22. A computer program product according to claim 21, wherein the plurality of data triples comprise a fingerprint.

23. A computer program product according to claim 22, further comprising program code instructions for removing from the fingerprint at least one data triple corresponding to the least significant value, creating a compressed fingerprint.

24. A computer program product according to claim 23, further comprising program code instructions for sending the compressed fingerprint to a mobile device.

25. A method comprising:

determining the access points of a first fingerprint

determining the access points of a second fingerprint;

calculating the similarity in signal strengths of access points that are common to both the first fingerprint and the second fingerprint;

determining access points that are exclusive to each of the first fingerprint and the second fingerprint; and

calculating the distance between the first fingerprint and the second fingerprint by using the similarity in the signal strengths of access points that are common to the first fingerprint and the second fingerprint to indicate proximate, and exclusive access points to indicate distant.

26. A method according to claim 25, wherein the first fingerprint is observed by a first mobile device and wherein the second fingerprint is observed by a second mobile device.

27. A method according to claim 26, the method further comprising estimating if the first mobile device and the second mobile device are occupying the same space.

28. A method according to claim 26, the method further comprising assigning permissions to the first mobile device and the second mobile device based upon the distance between the first mobile device and the second mobile device.

29. A method according to claim 26, the method further comprising preventing an exchange of information between the first mobile device and the second mobile device if the distance between the first mobile device and the second mobile device exceeds a threshold value.

30. A method according to claim 25, wherein the first fingerprint is observed by a mobile device and wherein the second fingerprint is observed at a location associated with a virtual message.

31. A method according to claim 30, the method further comprising:

determining when the distance is within a radius of the location associated with the virtual message; and

causing, at least in part, alerting of the mobile device based, at least in part, on the determination.

32. A method according to claim 31, the method further comprising:

receiving an input for specifying one or more criteria,

wherein the alerting of the mobile device is further based, at least in part, on the one or more criteria.

33. A method according to claim 30, the method further comprising:

determining a first named location based, at least in part, on the first fingerprint;

determining a second named location based, at least in part, on the second fingerprint;

determining whether the first name location substantially matches the second named location; and

causing, at least in part, alerting of the mobile device based on substantial matching.

34-86. -86. (canceled)