Determining device locations using movement, signal strength

Patent metadata

Field	Value
Publication number	US-9244152-B1
Application number	US-201313907706-A
Country	US
Kind code	B1
Filing date	May 31, 2013
Priority date	Jun 1, 2012
Publication date	Jan 26, 2016
Grant date	Jan 26, 2016

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.

First claim

What is claimed is:

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

Assignees

• Amazon Tech Inc

Inventors

• Thiagarajan Arvind

Classifications

• H04W64/00 Primary

  Locating users or terminals {or network equipment} for network management purposes, e.g. mobility management · CPC title

• G01S5/02521 Primary

  using a radio-map · CPC title

• G01S5/0264

  at least one of the systems being a non-radio wave positioning system · CPC title

• G01S5/0294

  Trajectory determination or predictive filtering, e.g. target tracking or Kalman filtering · CPC title

• G01S5/10 Primary

  Position of receiver fixed by co-ordinating a plurality of position lines defined by path-difference measurements {, e.g. omega or decca systems}(G01S5/12 takes precedence {; beacons and receivers cooperating therewith G01S1/306, G01S1/308}) · CPC title