Location estimation using radio scene signatures

• US 9,194,934 B2
• Filed: 03/09/2012
• Issued: 11/24/2015
• Est. Priority Date: 03/09/2012
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Blackberry Limited
• Inventors: Oka, Anand Ravindra, Simmons, Sean Bartholomew, Snow, Christopher Harris, Oliver, Robert George, Naddafzadeh Shirazi, Ghasem
• Primary Examiner(s): Phan, Dao
• Application Number:
  US13/416,698
• Publication Number:
  US 20130234894A1
• Time in Patent Office: 1,355 Days
• Field of Search: 342/451, 342/457, 342/463, 342/464, 455/456.1, 455/456.6
• US Class Current: 1/1
• CPC Class Codes: G01S 5/02521 using a radio-map

Abstract

Techniques for estimating a location of a portable electronic device are provided. The techniques represent radio scene information detected by a portable electronic device as a vector. The vector may then be used to retrieve similar vectors associated with known locations from a corpus. The known locations may then be used to estimate the location of the portable electronic device.

Claims

1. A method of estimating a location of a portable electronic device, the method comprising:

accessing a query signature vector of a radio scene identifying radio frequency transmitters and associated signal strengths detected at the portable electronic device, the query signature vector representing data from a high-dimensional space in a low-dimensional vector;

identifying one or more radio scene signature vectors based on a similarity with the query signature vector, each of the identified one or more radio scene signature vectors having an associated location, the one or more radio scene signature vectors representing data from the high-dimensional space in a respective low-dimensional vector; and

estimating the location of the portable electronic device based on the associated locations of the identified one or more signatures.

2. The method of claim 1, wherein the identified one or more radio scene signature vectors are within a threshold distance of the query radio scene signature vector.

3. The method of claim 1, wherein the identified one or more radio scene signature vectors are the k-closest radio scene signature vectors relative to the query radio scene signature vector,

where k>

=1.

4. The method of claim 1, wherein a plurality of radio scene signature vectors are identified and wherein estimating the location of the portable electronic device comprises averaging the locations associated with the plurality of identified radio scene signatures.

5. The method of claim 4, wherein estimating the location of the portable electronic device further comprises estimating an uncertainty associated with the average of the locations associated with the plurality of identified radio scene signatures.

6. The method of claim 5, wherein the uncertainty is estimated as an average absolute deviation between each of the retrieved locations and the estimation of the location.

7. The method of claim 1, further comprising generating the query radio scene signature vector comprising:

accessing a set of key-value pairs, each comprising a respective key, corresponding to a unique transmitter identifier and a value associated with a signal strength, from the respective transmitter, received at the portable electronic device; and

calculating each vector element of the query radio scene signature vector based on a summation of a plurality of terms each based on a respective pair in the received set of key-value pairs.

8. The method of claim 7, wherein each term is calculated from a respective key-value pair by:

generating a seed based on the key of the respective key-value pair and an element identifier associated with the vector element being calculated;

generating a pseudo-random number from the generated seed; and

multiplying the pseudo-random number by the value of the respective key-value pair.

9. The method of claim 7, wherein the query radio scene signature vector is generated at the portable electronic device.

10. The method of claim 7, wherein at least one of the keys of the plurality of key-value pairs is associated with one or more synonymous unique identifiers of transmitters located in close proximity to each other, wherein when the key of the respective key-value pair is associated with one or more synonymous unique identifiers, the term in the summation calculated by further adding one or more sub-terms, each calculated from a respective synonymous unique identifier of the one or more synonymous unique identifiers associated with the key of the respective key-value pair by:

generating a synonym seed based on the respective synonymous unique identifier and the element identifier associated with the vector element being calculated;

generating a synonym pseudo-random number from the generated synonym seed; and

multiplying the synonym pseudo-random number by the value of the respective key-value pair.

11. The method of claim 1, wherein the identified one or more radio scene signature vectors are located in a corpus of radio scene signatures and associated locations.

12. The method of claim 1, further comprising:

returning the estimated location to the portable electronic device from a server.

13. The method of claim 1, further comprising:

receiving location information comprising a known radio scene signature vector, or information for generating the known radio scene signature vector, and associated known location; and

updating a corpus of location information using the received location information.

14. The method of claim 1, wherein the radio frequency transmitters are identified in the composite radio scene signature by a unique radio frequency (RF) transmitter address comprising a media access control (MAC) address or cellular transmitter identifier.

15. A device for estimating a location of a portable electronic device, the device comprising:

a memory containing instructions; and

a processor for executing instructions, the instructions when executed configuring the device to;

access a query signature vector of a radio scene identifying radio frequency transmitters and associated signal strengths detected at the portable electronic device, the query signature vector representing data from a high-dimensional space in a low-dimensional vector;

identify one or more radio scene signature vectors based on a similarity with the query signature vector each of the identified one or more radio scene signature vectors having an associated location, the one or more radio scene signature vectors representing data from the high-dimensional space in a respective low-dimensional vector; and

estimate the location of the portable electronic device based on the associated locations of the identified one or more signatures.

16. The device of claim 15, wherein the identified one or more radio scene signature vectors are within a threshold distance of the query radio scene signature vector.

17. The device of claim 15, wherein the identified one or more radio scene signature vectors are the k-closest radio scene signature vectors relative to the query radio scene signature vector,

where k>

=1.

18. The device of claim 15, wherein a plurality of radio scene signature vectors are identified and wherein estimating the location of the portable electronic device comprises averaging the locations associated with the plurality of identified radio scene signatures.

19. The device of claim 18, wherein estimating the location of the portable electronic device further comprises estimating an uncertainty associated with the average of the locations associated with the plurality of identified radio scene signatures.

20. The device of claim 19, wherein the uncertainty is estimated as an average absolute deviation between each of the retrieved locations and the estimation of the location.

21. The device of claim 15, wherein the instructions, when executed further configure the device to generate the query radio scene signature vector by:

accessing a set of key-value pairs, each comprising a respective key, corresponding to a unique transmitter identifier and a value associated with a signal strength from the respective transmitter received at the portable electronic device; and

calculating each vector element of the query radio scene signature vector based on a summation of a plurality of terms each based on a respective pair in the received set of key-value pairs.

22. The device of claim 21, wherein each term is calculated from a respective key-value pair by:

generating a seed based on the key of the respective key-value pair and an element identifier associated with the vector element being calculated;

generating a pseudo-random number from the generated seed; and

multiplying the pseudo-random number by the value of the respective key-value pair.

23. The device of claim 21, wherein at least one of the keys of the plurality of key-value pairs is associated with one or more synonymous unique identifiers of transmitters located in close proximity to each other, wherein when the key of the respective key-value pair is associated with one or more synonymous unique identifiers, the term in the summation calculated by further adding one or more sub-terms, each calculated from a respective synonymous unique identifier of the one or more synonymous unique identifiers associated with the key of the respective key-value pair by:

generating a synonym seed based on the respective synonymous unique identifier and the element identifier associated with the vector element being calculated;

generating a synonym pseudo-random number from the generated synonym seed; and

multiplying the synonym pseudo-random number by the value of the respective key-value pair.

24. The device of claim 15, wherein the identified one or more radio scene signature vectors are located in a corpus of radio scene signatures and associated locations.

25. The device of claim 15, further comprising:

returning the estimated location to the portable electronic device from a server.

26. The device of claim 15, further comprising:

receiving location information comprising a known radio scene signature vector, or information for generating the known radio scene signature vector, and associated known location; and

updating a corpus of location information using the received location information.

27. A computer readable memory containing instructions for estimating a location of a portable electronic device, the instructions which when executed by a processor perform the method of:

accessing a query signature vector of a radio scene identifying radio frequency transmitters and associated signal strengths detected at the portable electronic device, the query signature vector representing data from a high-dimensional space in a low-dimensional vector;

identifying one or more radio scene signature vectors based on a similarity with the query signature vector each of the identified one or more radio scene signature vectors having an associated location, the one or more radio scene signature vectors representing data from the high-dimensional space in a respective low-dimensional vector; and

estimating the location of the portable electronic device based on the associated locations of the identified one or more signatures.