Determining device locations using movement, signal strength

• US 9,244,152 B1
• Filed: 05/31/2013
• Issued: 01/26/2016
• Est. Priority Date: 06/01/2012
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Thiagarajan, Arvind
• Primary Examiner(s): Sivji, Nizar
• Application Number:
  US13/907,706
• Time in Patent Office: 970 Days
• Field of Search: 340/539.13, 455/456.3, 455/456.2, 455/456.5, 455/456.6, 455/456.1
• US Class Current: 1/1
• CPC Class Codes: G01S 5/02521 using a radio-map
• CPC Class Codes: G01S 5/0264 at least one of the systems being a non-radio wave positioning system
• CPC Class Codes: G01S 5/0294 Trajectory determination or predictive filtering, e.g. target tracking or Kalman filtering
• CPC Class Codes: G01S 5/10 Position of receiver fixed by co-ordinating a plurality of position lines defined by path-difference measurements , e.g. omega or decca systemsG01S5/12 takes precedence ; beacons and receivers cooperating therewith G01S1/306, G01S1/308
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Abstract

Techniques for precisely determining a location of a mobile computing device based on both wireless signal strengths measured at the mobile computing device and movement of the device. The wireless signal strengths may represent the strength of a connection between the device and wireless access points (WAPs), cellular towers, or the like. Furthermore, the techniques described herein may utilize movement data provided by the device. For instance, the device may include an accelerometer, a gyroscope, and/or any other components configured to recognize when a device is moving, a direction that the device is moving, or the like. In one example, the accelerometer reports when the device has moved by a certain amount, while the gyroscope reports a direction in which the device is moving. The techniques then utilize this information in addition to the wireless signal strengths to estimate locations of the device as the device moves over time.

Claims

1. A device comprising:

an accelerometer;

one or more processors; and

one or more non-transitory computer-readable media storing computer-executable instructions that, when executed by the one or more processors, cause the one or more processors to perform acts comprising;

determining a possible location of a device;

determining, at a first time, a first received signal strength indication RSSI representing a strength of a connection between the device and a wireless access point (WAP) at the first time;

analyzing the first RSSI determined at the first time and a previously determined RSSI at the possible location;

determining, based at least in part on the analyzing of the first RSSI determined at the first time and the previously determined RSSI at the possible location, a first likelihood that the device is located at the possible location;

receiving an indication from the accelerometer that the device has moved since the determining of the first RSSI at the first time;

at least partly in response to receiving the indication;

determining a new possible location;

determining, at a second time, a second RSSI representing a strength of a connection between the device and the WAP at the second time;

analyzing the second RSSI determined at the second time and previously determined RSSI at the new possible location; and

determining, for the new possible location, a second likelihood that the device is located at the new possible location, the second likelihood based at least in part on the first likelihood and the analyzing of the second RSSI determined at the second time and the previously determined RSSI at the new possible location; and

providing the new possible location.

2. The device as recited in claim 1, wherein determining the second likelihood comprises updating the first likelihood based at least in part on the analyzing of the second RSSI determined at the second time and the previously determined RSSI at the new possible location.

3. The device as recited in claim 1, further comprising at least one of a gyroscope, a compass, or a barometer, the acts further comprising receiving an indication of a direction that the device has moved from the at least one of the gyroscope, the compass, or the barometer, and wherein the determining of the new possible location comprises selecting a location that are adjacent to the possible location in a direction corresponding at least in part to the indication of the direction that the device has moved.

4. A computer-implemented method comprising:

determining possible locations of a device;

determining for a first possible location of the possible locations, a first likelihood that the device resides at the first possible location;

receiving motion data from a motion sensor;

determining a second possible location of the device based at least in part on updating the first possible location based at least in part on the motion data;

receiving an indication of signal strength between the device at the second possible location and a wireless access point (WAP);

analyzing the indication of signal strength and data representing a second signal strength at the second possible location;

determining a second likelihood that the device resides at the second possible location based at least in part on the first likelihood and the analyzing; and

providing the second possible location.

5. The computer-implemented method as recited in claim 4, wherein the determining of the possible locations comprises:

determining an initial signal strength between the device and the WAP when the device is at an initial location; and

estimating the initial location by;

(i) analyzing the initial signal strength and previously determined signal strengths associated with the WAP, (ii) identifying a closest matching signal strength based at least in part on the analyzing of the initial signal strength and the previously determined signal strengths associated with the WAP and (iii) determining a location associated with the closest matching signal strength, each of the previously determined signal strengths corresponding to a different location;

and wherein the possible locations of the device are based at least in part on the estimated initial location.

6. The computer-implemented method as recited in claim 4, the acts further comprising receiving an indication from an accelerometer of the device that the device has moved.

7. The computer-implemented method as recited in claim 4, the acts further comprising receiving an indication of a direction in which the device has moved, and wherein the determining of the second possible location comprises selecting a location that is adjacent to the first possible location and in the indicated direction.

8. The computer-implemented method as recited in claim 7, wherein the indication of the direction is received from at least one of a gyroscope, a compass, or a barometer of the device.

9. The computer-implemented method as recited in claim 4, the acts further comprising:

continuing to determine new additional possible locations of the device based at least in part on movement of the device; and

re-determining a new additional likelihood that the device resides at a new additional possible location of the new additional possible locations based at least in part on a respective signal strength between the device and the WAP.

10. The computer-implemented method as recited in claim 9, wherein the re-determining is based at least in part on determining an end of a path determined via a Hidden Markov Model (HMM) or a current location determined by a particle filter.

11. The computer-implemented method as recited in claim 4, the acts further comprising:

determining new possible locations of the device including the second possible location based at least in part on updating the possible locations based at least in part on the motion data;

determining whether any of the new possible locations are on an opposite side of a wall from a location determined in a previous possible location; and

determining a likelihood for each new possible location that is not on the opposite side of the wall.

12. The computer-implemented method as recited in claim 4, wherein the determining the second likelihood comprises updating the first likelihood based at least in part on the analyzing of the indication of signal strength and the data representing the second signal strength at the second possible location.

13. A method comprising:

determining a first wireless signal strength at a device;

determining, based at least in part on the first wireless signal strength, a first likelihood that the device is at a first location;

receiving an indication from an accelerometer that the device has moved since the determining of the first wireless signal strength;

at least partly in response to receiving the indication;

determining a second location of the device, the second location being associated with the first location;

determining a second wireless signal strength at the device at the second location;

analyzing the second wireless signal strength and a previously determined signal strength at the second location; and

determining a second likelihood that the device resides at the second location based at least in part on the first likelihood and the analyzing; and

providing the second location.

14. The method as recited in claim 13, wherein determining the first likelihood comprises:

analyzing the first wireless signal strength and each previously determined wireless signal strength of a first set of previously determined wireless signal strengths, each previously determined wireless signal strength of the first set corresponding to a particular location.

15. The method as recited in claim 13, wherein

determining the second likelihood that the device resides at the second location is further based at least in part on analyzing the first wireless signal strength and previously determined wireless signal strengths at the first location.

16. The method as recited in claim 13, wherein the indication comprises a direction in which the device has moved, and wherein the determining of the second location is based at least in part on the indication.

17. A device comprising:

one or more processors; and

one or more non-transitory computer-readable media storing computer-executable instructions that, when executed by the one or more processors, cause the one or more processors to perform acts comprising;

determining a likelihood that the device resides at a first location based at least in part on a first signal strength;

determining a likelihood that the device resides at a second location based at least in part on the first signal strength;

receiving an indication that the device has moved;

at least partly in response to receiving the indication;

determining a third location and a fourth location, the third location and the fourth location being respectively associated with the first location and the second location;

determining a second signal strength;

analyzing the second signal strength and respective previously determined signal strengths at the third location and the fourth location;

determining a likelihood that the device resides at the third location based at least in part on the likelihood that the device resided at the first location and the analyzing; and

determining a likelihood that the device resides at the fourth location based at least in part on the likelihood that the device resided at the second location and the analyzing; and

providing the third location and the fourth location.

18. The device as recited in claim 17, further comprising an accelerometer to provide the indication that the device has moved.

19. The device as recited in claim 17, further comprising at least one of a gyroscope, a compass, or a barometer to provide an indication of a direction of that the device has moved, and wherein the determining the third and fourth locations occurs based at least in part on the indication of the direction.

20. The device as recited in claim 17, wherein the first and second signal strengths comprise respective received signal strength indications (RSSIs) between the device and a wireless access point (WAP).

21. The device as recited in claim 17, wherein the first and second signal strengths comprise respective received signal strengths between the device and a cellular tower or satellite.