Determining a location of a device

Patent metadata

Field	Value
Publication number	US-10330772-B2
Application number	US-201415500337-A
Country	US
Kind code	B2
Filing date	Nov 14, 2014
Priority date	Nov 14, 2014
Publication date	Jun 25, 2019
Grant date	Jun 25, 2019

Abstract

Described herein are techniques for determining a location of a device. In an example, a group of access points may be selected. Time-of-flight (ToF) measurements relative to the device may be received from each of the access points in the group. A respective distance of the device from each access point may be determined using the ToF measurements and a baseToF value. Location coordinates of the device and a new baseToF value may be determined based on the determined distances and the location coordinates of each access point in the group.

First claim

What is claimed is:

1. A method for determining a location of a device, comprising, by a
processor:
selecting a group of access points;
receiving, from each access point in the group, a time-of-flight (ToF) measurement relative to the device;
determining a respective distance of the device from each access point in the group using the ToF measurements and a baseToF value; and
determining (1) location coordinates of the device and (2) a new baseToF value, based on the determined distances and the location coordinates of each access point in the group, wherein the location coordinates of the device and the new baseToF value are determined by solving a system of equations, the system of equations including an equation for each access point n (AP n ) as follows:
m n −e=∥<AP n,x ,AP n,y >−<L x ,L y >∥

where m n is the determined respective distance of the device from AP n , e is the error value proportional to the difference between the new baseToF value and the baseToF value, <AP n,x ,AP n,y > are the location coordinates of AP n , and <L x ,L y > are the location coordinates of the device.

2. The method of claim 1 , wherein the selected group of access points comprises four access points, and wherein the group of access points are selected from a larger group of more than four access points.

3. The method of claim 2 , wherein the group of access points are selected because they are determined to form a convex quadrilateral around the device based on the location coordinates of the access points and previously determined location coordinates of the device.

4. The method of claim 3 , wherein the group of four access points are selected over a second group of four access points that are determined to form a second convex quadrilateral around the device because the convex quadrilateral formed by the group of access points is determined to be smaller than the second convex quadrilateral.

5. The method of claim 1 , wherein the baseToF value is a default value.

6. The method of claim 1 , wherein the baseToF value is a previously determined new baseToF value from a previous iteration.

7. The method of claim 1 , wherein the respective distance of the device from each access point in the group is determined for each access point n (AP n ) as follows:
m n =(ToF n −baseToF)* c

where m n is the determined respective distance of the device from AP n , ToF n is the ToF measurement from the device to AP n , and c is a constant representing the speed of light.

8. The method of claim 1 , comprising:
receiving, from each access point in the group, a second ToF measurement relative to the device;
determining a second respective distance of the device from each access point in the group using the second ToF measurements and the new baseToF value; and
determining (1) second location coordinates of the device and (2) a second new baseToF value, based on the determined second distances and the location coordinates of each access point in the group.

9. The method of claim 8 , comprising:
based on the second location coordinates of the device, selecting a new group of access points that are determined to form a convex quadrilateral around the device;
receiving, from each access point in the new group, a third ToF measurement relative to the device;
determining a third respective distance of the device from each access point in the new group using the third ToF measurements and the second new baseToF value; and
determining (1) third location coordinates of the device and (2) a third new baseToF value, based on the determined third distances and the location coordinates of each access point in the new group.

10. A location determination system for determining a location of a device, comprising:
a group selector to select a group of access points;
a communication interface to receive, from each access point in the group, a time-of-flight (ToF) measurement relative to the device; and
a location determination module to determine:
a respective distance of the device from each access point in the group using the ToF measurements and a baseToF value; and
location coordinates of the device and a new baseToF value, based on the determined distances and the location coordinates of each access point in the group, wherein the location coordinates of the device and the new baseToF value are determined by solving a system of equations, the system of equations including an equation for each access point n (AP n ) as follows:
m n −e=∥<AP n,x ,AP n,y >−<L x ,L y >∥

where m n is the determined respective distance of the device from AP n , e is the error value proportional to the difference between the new baseToF value and the baseToF value, <AP n,x ,AP n ,y> are the location coordinates of AP n , and <L x ,L y > are the location coordinates of the device.

11. The location determination system of claim 10 , wherein the group selector is to select the group of access points from a larger group of access points based on a determination that the group of access points form a smallest convex quadrilateral around the device.

12. The location determination system of claim 10 , wherein the system is configured to iteratively determine new location coordinates of the device and additional new baseToF values based on newly received ToF measurements.

13. A non-transitory computer-readable storage medium storing instructions that, when executed by a processor, cause the processor to:
select a group of four access points that form a convex quadrilateral around a device;
receive, from each access point in the group, a time-of-flight (ToF) measurement relative to the device;
determine a respective distance of the device from each access point in the group using the ToF measurements and a baseToF value; and
determine (1) location coordinates of the device and (2) a new baseToF value, based on the determined distances and the location coordinates of each access point in the group, wherein the location coordinates of the device and the new baseToF value are determined by solving a system of equations, the system of equations including an equation for each access point n (AP n ) as follows:
m n −e=∥<AP n,x ,AP n,y >−<L x ,L y >∥

where m n is the determined respective distance of the device from AP n , e is the error value proportional to the difference between the new baseToF value and the baseToF value, <AP n,x ,AP n,y > are the location coordinates of AP n , and <L x ,L y > are the location coordinates of the device.

Assignees

• Hewlett Packard Entpr Dev Lp

Inventors

• Sen Souvik
• Kim Dongho

Classifications

• G01S5/10

  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

• H04W64/00

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

• G01S5/0268

  by deriving positions from different combinations of signals or of estimated positions in a single positioning system · CPC title

• G01S13/74

  Systems using reradiation of radio waves, e.g. secondary radar systems; Analogous systems · CPC title

• G01S5/14 Primary

  Determining absolute distances from a plurality of spaced points of known location · CPC title