Time of arrival based positioning system

• US 8,521,181 B2
• Filed: 09/19/2011
• Issued: 08/27/2013
• Est. Priority Date: 09/19/2011
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Zhang, Xiaoxin, Zhang, Ning
• Primary Examiner(s): Batista, Marcos
• Assistant Examiner(s): DONADO, FRANK E
• Application Number:
  US13/236,172
• Publication Number:
  US 20130072217A1
• Time in Patent Office: 708 Days
• Field of Search: 455/456
• US Class Current: 455/456.1
• CPC Class Codes: G01S 13/876 Combination of several spaced transponders or reflectors of known location for determining the position of a receiver G01S13/874 takes precedence
• CPC Class Codes: G01S 5/021 Calibration, monitoring or correction G01S5/0252 takes precedence
• CPC Class Codes: G01S 5/14 Determining absolute distances from a plurality of spaced points of known location
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/029 Location-based management or tracking services

Abstract

A TOA positioning system can be implemented that employs a calculated initial location of a wireless network device. For each of a plurality of reference wireless network devices, a distance between the wireless network device and the reference wireless network device is determined based, at least in part, on a round trip transit time between the wireless network device and the reference wireless network device. An initial location of the wireless network device can be calculated based, at least in part, on a location of each of the plurality of reference wireless network devices. A location of the wireless network device can be estimated based, at least in part, on the calculated initial location, the distance to each of the reference wireless network devices, and an initial distance calibration constant.

Claims

1. A method comprising:

determining, at a wireless network device of a communication network, a round trip transit time between the wireless network device and each of a plurality of reference wireless network devices of the communication network;

for each of the plurality of reference wireless network devices, determining a distance between the wireless network device and the reference wireless network device based, at least in part, on the round trip transit time between the wireless network device and the reference wireless network device;

obtaining location coordinates associated with each of the plurality of reference wireless network devices; and

performing time of arrival (TOA) computations for estimating a location of the wireless network device by executing an iteration of a Taylor series based TOA positioning algorithm based, at least in part, on an initial location of the wireless network device, the distance between the wireless network device and each of the plurality of reference wireless network devices, and an initial distance calibration constant, wherein the initial location is based, at least in part, on an average of the location coordinates associated with each of the plurality of reference wireless network devices.

2. The method of claim 1, wherein the initial distance calibration constant is one of a zero value, a predetermined value, and a dynamically selected random value.

3. The method of claim 1, wherein said performing the TOA computations for estimating the location of the wireless network device further comprises determining a distance calibration constant based, at least in part, on the initial location of the wireless network device, the distance between the wireless network device and each of the plurality of reference wireless network devices, the initial distance calibration constant, and the location coordinates associated with each of the plurality of reference wireless network devices in response to said executing the single iteration of the Taylor series based TOA positioning algorithm.

4. The method of claim 1, further comprising:

calculating the initial location of the wireless network device as a non-weighted average of the location coordinates associated with each of the plurality of reference wireless network devices.

5. The method of claim 1, further comprising:

calculating the initial location of the wireless network device as a weighted average of the location coordinates of at least a subset of the plurality of reference wireless network devices.

6. The method of claim 5, wherein weights used in the weighted average are based upon a confidence metric associated with the location coordinates associated with the plurality of reference wireless network devices.

7. The method of claim 1, further comprising:

identifying the plurality of reference wireless network devices based, at least in part, on analyzing one or more performance measurements associated with at least each of the plurality of reference wireless network devices.

8. The method of claim 1, wherein said for each of the plurality of reference wireless network devices, said determining the distance between the wireless network device and the reference wireless network device based, at least in part, on the round trip transit time between the wireless network device and the reference wireless network device further comprises:

for each of the plurality of reference wireless network devices,

recording a first time instant at which a first control message is transmitted from the wireless network device to the reference wireless network device;

recording a second time instant at which a second control message is received at the wireless network device from the reference wireless network device in response to the first control message;

subtracting the first time instant from the second time instant to determine the round trip transit time between the wireless network device and the reference wireless network device; and

multiplying round trip transit time between the wireless network device and the reference wireless network device by a speed of light factor to yield the distance between the wireless network device and the reference wireless network device.

9. The method of claim 1, wherein the wireless network device and the plurality of reference wireless network devices comprise wireless local area network (WLAN) communication capabilities.

10. The method of claim 1, wherein said obtaining location coordinates associated with each of the plurality of reference wireless network devices comprises:

transmitting a request for the location coordinates to each of the plurality of reference wireless network devices; and

receiving the location coordinates from each of the plurality of reference wireless network devices.

11. The method of claim 10, wherein the request for the location coordinates is included in a control message that is also used to determine the round trip transmit time between the wireless network device and each of the plurality of reference wireless network devices.

12. The method of claim 1, wherein said obtaining location coordinates associated with each of the plurality of reference wireless network devices comprises:

transmitting a request for the location coordinates to a centralized server; and

receiving the location coordinates associated with each of the plurality of reference wireless network devices from the centralized server.

13. The method of claim 1, wherein said obtaining location coordinates associated with each of the plurality of reference wireless network devices comprises:

receiving a periodic broadcast message from each of the plurality of reference wireless network devices, the periodic broadcast message including the location coordinates from a corresponding one of the plurality of reference wireless network devices.

14. The method of claim 1, wherein the location coordinates associated with each of the plurality of reference wireless network devices comprises one of two-dimensional (2-D) coordinates, three-dimensional (3-D) coordinates, geographic latitude and longitude coordinates, or spherical coordinates.

18. The wireless network device of claim 11, wherein the location calculation unit is further operable to:

calculate the initial location of the wireless network device as a non-weighted average of the location coordinates associated with each of the plurality of reference wireless network devices, or

calculate the initial location of the wireless network device as a weighted average of the location of at least a subset of the plurality of reference wireless network devices.

15. A method comprising:

determining, at a wireless network device of a communication network, a round trip transit time between the wireless network device and each of a plurality of reference wireless network devices of the communication network;

for each of the plurality of reference wireless network devices, determining a distance between the wireless network device and the reference wireless network device based, at least in part, on the round trip transit time between the wireless network device and the reference wireless network device;

determining a location error matrix, wherein each element of the location error matrix represents a difference between an estimated location coordinate of the wireless network device and a corresponding initial location coordinate of an initial location of the wireless network device;

determining a distance error matrix, wherein each element of the distance error matrix represents a difference between a measured distance between the wireless network device and one of the plurality of reference wireless network devices and an estimated distance between the wireless network device and the one of the plurality of reference wireless network devices, wherein the measured distance is determined based, at least in part, on the round trip transit time between the wireless network device and the one of the plurality of reference wireless network devices, wherein the estimated distance is determined based, at least in part, on the location of the one of the plurality of reference wireless network devices and the initial location of the wireless network device;

determining a coefficient matrix as the product of the distance error matrix and an inverse of a transpose of the location error matrix;

calculating the initial location of the wireless network device based, at least in part, on maximizing the determinant of the product of the coefficient matrix and a transpose of the coefficient matrix; and

performing time of arrival (TOA) computations for estimating a location of the wireless network device based, at least in part, on the initial location of the wireless network device, the distance between the wireless network device and each of the plurality of reference wireless network devices, and an initial distance calibration constant.

16. A wireless network device comprising:

a network interface; and

a location calculation unit coupled with the network interface, the location calculation unit operable to;

determine a round trip transit time between the wireless network device and each of a plurality of reference wireless network devices of a communication network;

for each of the plurality of reference wireless network devices, determine a distance between the wireless network device and the reference wireless network device based, at least in part, on the round trip transit time between the wireless network device and the reference wireless network device;

obtain location coordinates associated with each of the plurality of reference wireless network devices; and

perform time of arrival (TOA) computations to estimate a location of the wireless network device by executing an iteration of a Taylor series based TOA positioning algorithm based, at least in part, on an initial location of the wireless network device, the distance between the wireless network device and each of the plurality of reference wireless network devices, and an initial distance calibration constant, wherein the initial location is based, at least in part, on an average of the location coordinates associated with each of the plurality of reference wireless network devices.

17. The wireless network device of claim 16, wherein the location calculation unit operable to perform the TOA computations to estimate the location of the wireless network device further comprises the location calculation unit operable to determine a distance calibration constant based, at least in part, on the initial location of the wireless network device, the distance between the wireless network device and each of the plurality of reference wireless network devices, the initial distance calibration constant, and the location coordinates associated with each of the plurality of reference wireless network devices in response to the location calculation unit executing the single iteration of the Taylor series based TOA positioning algorithm.

19. A wireless network device comprising:

a network interface; and

a location calculation unit coupled with the network interface, the location calculation unit operable to;

determine a round trip transit time between the wireless network device and each of a plurality of reference wireless network devices of a communication network;

for each of the plurality of reference wireless network devices, determine a distance between the wireless network device and the reference wireless network device based, at least in part, on the round trip transit time between the wireless network device and the reference wireless network device;

determine a location error matrix, wherein each element of the location error matrix represents a difference between an estimated location coordinate of the wireless network device and a corresponding initial location coordinate of an initial location of the wireless network device;

determine a distance error matrix, wherein each element of the distance error matrix represents a difference between a measured distance between the wireless network device and one of the plurality of reference wireless network devices and an estimated distance between the wireless network device and the one of the plurality of reference wireless network devices, wherein the measured distance is determined based, at least in part, on the round trip transit time between the wireless network device and the one of the plurality of reference wireless network devices, wherein the estimated distance is determined based, at least in part, on the location of the one of the plurality of reference wireless network devices and the initial location of the wireless network device;

determine a coefficient matrix as the product of the distance error matrix and an inverse of a transpose of the location error matrix;

calculate the initial location of the wireless network device based, at least in part, on maximizing the determinant of the product of the coefficient matrix and a transpose of the coefficient matrix; and

perform time of arrival (TOA) computations to estimate a location of the wireless network device based, at least in part, on the initial location of the wireless network device, the distance between the wireless network device and each of the plurality of reference wireless network devices, and an initial distance calibration constant.

20. One or more non-transitory machine-readable storage media having instructions stored therein, which when executed by one or more processors causes the one or more processors to perform operations that comprise:

determining, at a wireless network device of a communication network, a round trip transit time between the wireless network device and each of a plurality of reference wireless network devices of the communication network;

for each of the plurality of reference wireless network devices, determining a distance between the wireless network device and the reference wireless network device based, at least in part, on the round trip transit time between the wireless network device and the reference wireless network device;

obtaining location coordinates associated with each of the plurality of reference wireless network devices; and

performing time of arrival (TOA) computations for estimating a location of the wireless network device by executing an iteration of a Taylor series based TOA positioning algorithm based, at least in part, on an initial location of the wireless network device, the distance between the wireless network device and each of the plurality of reference wireless network devices, and an initial distance calibration constant, wherein the initial location is based, at least in part, on an average of the location coordinates associated with each of the plurality of reference wireless network devices.

21. The non-transitory machine-readable storage media of claim 20, wherein said operation of performing the TOA computations for estimating the location of the wireless network device further comprises determining a distance calibration constant based, at least in part, on the initial location of the wireless network device, the distance between the wireless network device and each of the plurality of reference wireless network devices, the initial distance calibration constant, and the location coordinates associated with each of the plurality of reference wireless network devices in response to said executing the single iteration of the Taylor series based TOA positioning algorithm.

22. The non-transitory machine-readable storage media of claim 20, wherein the instructions stored therein, which when executed by one or more processors causes the one or more processors to further perform operations that comprise:

calculating the initial location of the wireless network device as a non-weighted average of the location coordinates associated with each of the plurality of reference wireless network devices, or

calculating the initial location of the wireless network device as a weighted average of the location of at least a subset of the plurality of reference wireless network devices.

23. One or more machine-readable storage media having instructions stored therein, which when executed by one or more processors causes the one or more processors to perform operations that comprise:

determining, at a wireless network device of a communication network, a round trip transit time between the wireless network device and each of a plurality of reference wireless network devices of the communication network;

for each of the plurality of reference wireless network devices, determining a distance between the wireless network device and the reference wireless network device based, at least in part, on the round trip transit time between the wireless network device and the reference wireless network device;

determining a location error matrix, wherein each element of the location error matrix represents a difference between an estimated location coordinate of the wireless network device and a corresponding initial location coordinate of an initial location of the wireless network device;

determining a distance error matrix, wherein each element of the distance error matrix represents a difference between a measured distance between the wireless network device and one of the plurality of reference wireless network devices and an estimated distance between the wireless network device and the one of the plurality of reference wireless network devices, wherein the measured distance is determined based, at least in part, on the round trip transit time between the wireless network device and the one of the plurality of reference wireless network devices, wherein the estimated distance is determined based, at least in part, on the location of the one of the plurality of reference wireless network devices and the initial location of the wireless network device;

determining a coefficient matrix as the product of the distance error matrix and an inverse of a transpose of the location error matrix; and

calculating the initial location of the wireless network device based, at least in part, on maximizing the determinant of the product of the coefficient matrix and a transpose of the coefficient matrix; and

performing time of arrival (TOA) computations for estimating a location of the wireless network device based, at least in part, on the initial location of the wireless network device, the distance between the wireless network device and each of the plurality of reference wireless network devices, and an initial distance calibration constant.