Simultaneous localization and RF modeling

• US 8,077,090 B1
• Filed: 06/15/2010
• Issued: 12/13/2011
• Est. Priority Date: 06/15/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chintalapudi, Krishna Kant, Padmanabhan, Venkata N., Iyer, Anand Padmanabha
• Primary Examiner(s): Tarcza, Thomas
• Assistant Examiner(s): MCGUE, FRANK J
• Application Number:
  US12/815,973
• Publication Number:
  US 20110304503A1
• Time in Patent Office: 546 Days
• Field of Search: 342/451, 342/450
• US Class Current: 342/451
• CPC Class Codes: G01S 11/06 using intensity measurements
• CPC Class Codes: G01S 5/0252 Radio frequency fingerprinting

Abstract

The simultaneous localization and RF modeling technique pertains to a method of providing simultaneous localization and radio frequency (RF) modeling. In one embodiment, the technique operates in a space with wireless local area network coverage (or other RF transmitters). Users carrying Wi-Fi-enabled devices traverse this space while the mobile devices record the Received Signal Strength (RSS) measurements corresponding to access points (APs) in view at various unknown locations and report these RSS measurements, as well as nay other available location fix to a localization server. A RF modeling algorithm runs on the server and is used to estimate the location of the APs using the recorded RSSI measurements and any other available location information. All of the observations are constrained by the physics of wireless propagation. The technique models these constraints and uses a genetic algorithm to solve them, thereby providing an absolute location of the mobile device.

Claims

1. A computer-implemented process for performing localization of one or more mobile devices, comprising:

using a computing device for;

recording measurements of received signal strength indication (RSSI) from each Radio Frequency (RF) transmitter reported by a mobile device;

recording measurements of any available location fix by the mobile device;

using a RF propagation model, prepared without prior knowledge of the physical space in which the mobile device is located or the location and power of the RF transmitters, to estimate parameters comprising;

the location of the mobile device, the transmit power of each RF transmitter, and the location of each RF transmitter based on the recorded measurements of received signal strength indication and any available location fixes; and

using trilateration to determine the location of the mobile device from the estimated location of the RF transmitters and the estimated parameters.

2. The computer-implemented process of claim 1, wherein determining the location of the mobile device further comprises:

translating the RSSI measurements reported by the mobile device into distances from the corresponding RF transmitters whose locations are estimated with the RF propagation model, and

using the distances from at least three RF transmitters to compute the location of the mobile device.

3. The computer-implemented process of claim 1 further comprising creating the RF propagation model using a log distance path loss model.

4. The computer-implemented process of claim 1, further comprising using a combination of a gradient descent approach and a genetic algorithm to estimate the parameters using the RF propogation model.

5. The computer-implemented process of claim 1 wherein the location of any available location fix is obtained by a global positioning system device.

6. A computer-implemented process for performing localization, comprising:

using a computing device for,

recording at one or more mobile devices, RSSI measurements corresponding to RF transmitters received by the one or more mobile devices at various unknown locations;

reporting the recorded RSSI measurements to a remote server;

recording any available GPS lock at the one or more mobile devices;

reporting any GPS lock to the remote server;

using the RSSI measurements and any GPS locks recorded at the one or more mobile devices to determine the location of the one or more mobile devices, without prior knowledge of the physical space in which the mobile devices are located or the location and power of the RF transmitters, using the constraints of the physics of RF propagation at the remote server; and

reporting the determined location of the one or more mobile devices.

7. The computer-implemented process of claim 6 wherein the RF transmitters are located in an indoor environment.

8. The computer-implemented process of claim 6 wherein the RF transmitters are located in an outdoor environment.

9. The computer-implemented process of claim 6 wherein only one mobile device traversing the environment over time is used to obtain the location of the mobile device.

10. The computer-implemented process of claim 6, wherein the constraints are modeled using a log distance path loss model.

11. The computer-implemented process of claim 10 wherein the constraints modeled using the log distance path loss model are solved using a genetic algorithm.

12. The computer-implemented process of claim 9, wherein the constraints further comprise:

location of each RF transmitter;

transmit power of each RF transmitter; and

a decay constant of the log distance path loss model.

13. A system for determining locations of a Wi-Fi capable device in an indoor environment, comprising:

a general purpose computing device;

a computer program comprising program modules executable by the general purpose computing device, wherein the computing device is directed by the program modules of the computer program to,

periodically scan for Wi-Fi access points using a Wi-Fi enabled mobile device;

transmit a list of discovered Wi-Fi access-points and associated received signal strength indication (RSSI) measured by the mobile device to a remotely located server;

transmit any GPS locations discovered by the mobile device to the remotely located server;

use a RF model of the indoor environment, created without prior knowledge of the space the mobile device is located in or the location and power of the Wi-Fi access points, using the list of discovered Wi-Fi access points and associated received RSSI and the discovered GPS locations to provide the location of the mobile device to user of the mobile device.

14. The system of claim 13 wherein the location of the mobile device is provided to the user without action by the user.

15. The system of claim 13 wherein the location of the mobile device is determined without any prior knowledge of the location of the mobile device, the location of the Wi-Fi access points or knowledge of the RF power of the Wi-Fi access points.

16. The system of claim 13 wherein the RSSI values are used to determine relative distances between Wi-Fi access points and wherein the relative locations between the Wi-Fi access points are used to determine the location of the mobile devices.

17. The system of claim 13 wherein determined locations of the Wi-Fi access points are used to find unknown locations of the Wi-Fi access points.

18. The system of claim 17 wherein only a subset of the determined locations are selected for use to find the unknown locations, wherein the subset of the selected locations are selected by removing redundant determined locations.

19. The system of claim 13 further comprising a module for using a subset of the list of discovered access points that do not provide redundant information when using the created RF model to provide the location of the mobile device to a user.

20. The system of claim 13 wherein gains of the mobile devices are estimated by using RSS readings of pairs of mobile devices that are most likely at the same location.