Hybrid time of arrival based positioning system

• US 8,457,655 B2
• Filed: 09/19/2011
• Issued: 06/04/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): Ngo, Chuong A
• Application Number:
  US13/236,232
• Publication Number:
  US 20130072219A1
• Time in Patent Office: 624 Days
• Field of Search: 4554561-457, 455/422.1, 455/427, 455/440, 370328-338
• US Class Current: 455/456.1
• CPC Class Codes: G01S 5/021 Calibration, monitoring or correction G01S5/0252 takes precedence
• CPC Class Codes: G01S 5/0289 of multiple transceivers, e.g. in ad hoc networks
• CPC Class Codes: G01S 5/14 Determining absolute distances from a plurality of spaced points of known location

Abstract

A hybrid TOA positioning system can be implemented to improve location estimation of a wireless network device. An initial location of the wireless network device can be calculated based on locations of a plurality of reference network devices. A first intermediate location of the wireless network device and an intermediate distance calibration constant can be determined based, at least in part, on the initial location of the wireless network device and distance between the wireless network device and each of the reference network devices. A second intermediate location of the wireless network device and a target distance calibration constant can be calculated based on the locations of the reference network devices, the first intermediate location, and/or the intermediate distance calibration constant. The location of the wireless network device can be iteratively estimated based, at least in part, on the second intermediate location and the target 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;

determining an initial location of the wireless network device based, at least in part, on a known location of each of the plurality of reference wireless network devices;

determining a first intermediate location of the wireless network device and an intermediate distance calibration constant based, at least in part, on the initial location of the wireless network device and the distance between the wireless network device and each of the plurality of reference wireless network devices;

determining a second intermediate location of the wireless network device based on at least one of the known location of each of the plurality of reference wireless network devices and the first intermediate location of the wireless network device;

determining a target distance calibration constant associated with the plurality of reference wireless network devices based on at least one of the first intermediate location of the wireless network device, the intermediate distance calibration constant, and the distance between the wireless network device and the plurality of reference wireless network devices; and

iteratively estimating a current location of the wireless network device based, at least in part, on the second intermediate location of the wireless network device and the target distance calibration constant.

2. The method of claim 1, wherein said determining the first intermediate location of the wireless network device comprises:

executing a single iteration of a first Taylor series based time of arrival positioning algorithm to estimate the first intermediate 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, an initial distance calibration constant, and the known location of each of the plurality of reference wireless network devices.

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

4. The method of claim 2, wherein said determining the first intermediate location of the wireless network device further comprises determining an intermediate 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 known location of each of the plurality of reference wireless network devices in response to said executing the single iteration of the first Taylor series based TOA positioning algorithm.

5. The method of claim 2, wherein said iteratively estimating the current location of the wireless network device comprises:

iteratively executing a second Taylor series based time of arrival positioning algorithm to estimate the current location of the wireless network device based, at least in part, on the second intermediate location of the wireless network device, the target distance calibration constant, the distance between the wireless network device and each of the plurality of reference wireless network devices, and the known location of each of the plurality of reference wireless network devices.

6. The method of claim 1, wherein said determining the target distance calibration constant associated with the plurality of reference wireless network devices comprises:

designating the intermediate distance calibration constant as the target distance calibration constant.

7. The method of claim 1, wherein said determining the target distance calibration constant associated with the plurality of reference wireless network devices comprises:

for each of the plurality of reference wireless network devices,

determining a first 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 second distance between the wireless network device and the reference wireless network device based, at least in part, on the known location of the reference wireless network device and the first intermediate location of the wireless network device;

determining a distance difference associated with the reference wireless network device as a difference between the first distance and the second distance; and

determining the distance calibration constant associated with the plurality of reference wireless network devices as a combination of the distance difference associated with each of the plurality of reference wireless network devices.

8. The method of claim 7, wherein said determining the distance calibration constant associated with the plurality of reference wireless network devices as the combination of the distance difference associated with each of the plurality of reference wireless network devices comprises:

multiplying the distance difference associated with each of the plurality of the reference wireless network devices with a corresponding weighting factor associated each of the plurality of the reference wireless network devices to yield a plurality of weighted distance differences associated with corresponding each of the plurality of reference wireless network devices; and

combining the plurality of weighted distance differences to yield the distance calibration constant associated with the plurality of reference wireless network devices.

9. The method of claim 8, further comprising:

determining, for each of the plurality of reference wireless network devices, the weighting factor associated with the reference wireless network device as an inverse of a total number of the plurality of the reference wireless network devices, or

determining, for each of the plurality of reference wireless network devices, the weighting factor associated with the reference wireless network device based, at least in part, on a distance between the wireless network device and the reference wireless network device.

10. The method of claim 1, wherein said determining the second intermediate location of the wireless network device comprises one of:

determining the second intermediate location of the wireless network device as an average of the known location of each of the plurality of reference wireless network devices;

determining the second intermediate location of the wireless network device as a weighted average of the known location of each of the plurality of reference wireless network devices;

or

designating the first intermediate location of the wireless network device as the second intermediate location of the wireless network device.

11. The method of claim 1, wherein said determining the initial location of the wireless network device based, at least in part, on the known location of each of the plurality of reference wireless network devices comprises:

determining the initial location of the wireless network device as an average of the known location of each of the plurality of reference wireless network devices, or

determining the initial location of the wireless network device as a weighted combination of the known location of at least a subset of the plurality of reference wireless network devices.

12. The method of claim 1, wherein said determining the initial location of the wireless network device based, at least in part, on the known location of each of the plurality of reference wireless network devices comprises:

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 the 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 known 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

determining 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.

13. 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.

14. 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.

15. 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 an initial location of the wireless network device based, at least in part, on a known location of each of the plurality of reference wireless network devices;

determine a first intermediate location of the wireless network device and an intermediate distance calibration constant based, at least in part, on the initial location of the wireless network device and the distance between the wireless network device and each of the plurality of reference wireless network devices;

determine a second intermediate location of the wireless network device based on at least one of the known location of each of the plurality of reference wireless network devices and the first intermediate location of the wireless network device;

determine a target distance calibration constant associated with the plurality of reference wireless network devices based on at least one of the first intermediate location of the wireless network device, the intermediate distance calibration constant, and the distance between the wireless network device and the plurality of reference wireless network devices; and

iteratively estimate a current location of the wireless network device based, at least in part, on the second intermediate location of the wireless network device and the target distance calibration constant.

16. The wireless network device of claim 15, wherein:

the location calculation unit operable to determine the first intermediate location of the wireless network device and the intermediate distance calibration constant comprises the location calculation unit operable to;

execute a single iteration of a first Taylor series based time of arrival positioning algorithm to estimate the first intermediate location of the wireless network device and the intermediate 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, an initial distance calibration constant, and the known location of each of the plurality of reference wireless network devices; and

the location calculation unit operable to iteratively estimate the current location of the wireless network device comprises the location calculation unit operable to;

iteratively execute a second Taylor series based time of arrival positioning algorithm to estimate the current location of the wireless network device based, at least in part, on the second intermediate location of the wireless network device, the target distance calibration constant, the distance between the wireless network device and each of the plurality of reference wireless network devices, and the known location of each of the plurality of reference wireless network devices.

17. The wireless network device of claim 15, wherein the location calculation unit operable to determine the target distance calibration constant associated with the plurality of reference wireless network devices comprises the location calculation unit operable to:

for each of the plurality of reference wireless network devices,

determine a first 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 second distance between the wireless network device and the reference wireless network device based, at least in part, on the known location of the reference wireless network device and the first intermediate location of the wireless network device;

determine a distance difference associated with the reference wireless network device as a difference between the first distance and the second distance; and

multiply the distance difference associated with each of the plurality of the reference wireless network devices with a corresponding weighting factor associated each of the plurality of the reference wireless network devices to yield a plurality of weighted distance differences associated with corresponding each of the plurality of reference wireless network devices; and

combine the plurality of weighted distance differences to yield the distance calibration constant associated with the plurality of reference wireless network devices.

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

determine, for each of the plurality of reference wireless network devices, the weighting factor associated with the reference wireless network device as an inverse of a total number of the plurality of the reference wireless network devices, or

determine, for each of the plurality of reference wireless network devices, the weighting factor associated with the reference wireless network device based, at least in part, on a distance between the wireless network device and the reference wireless network device.

19. The wireless network device of claim 15, wherein the location calculation unit operable to determine the second intermediate location of the wireless network device comprises one of:

the location calculation unit operable to determine the second intermediate location of the wireless network device as an average of the known location of each of the plurality of reference wireless network devices;

the location calculation unit operable to determine the second intermediate location of the wireless network device as a weighted average of the known location of each of the plurality of reference wireless network devices;

or

the location calculation unit operable to designate the first intermediate location of the wireless network device as the second intermediate location of the wireless network device.

20. The wireless network device of claim 15, wherein the location calculation unit operable to determine the initial location of the wireless network device based, at least in part, on the known location of each of the plurality of reference wireless network devices comprises the location calculation unit operable to:

determine the initial location of the wireless network device as an average of the known location of each of the plurality of reference wireless network devices, or

determine the initial location of the wireless network device as a weighted combination of the known location of at least a subset of the plurality of reference wireless network devices.

21. 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;

determining an initial location of the wireless network device based, at least in part, on a known location of each of the plurality of reference wireless network devices;

determining a first intermediate location of the wireless network device and an intermediate distance calibration constant based, at least in part, on the initial location of the wireless network device and the distance between the wireless network device and each of the plurality of reference wireless network devices;

determining a second intermediate location of the wireless network device based on at least one of the known location of each of the plurality of reference wireless network devices and the first intermediate location of the wireless network device;

determining a target distance calibration constant associated with the plurality of reference wireless network devices based on at least one of the first intermediate location of the wireless network device, the intermediate distance calibration constant, and the distance between the wireless network device and the plurality of reference wireless network devices; and

iteratively estimating a current location of the wireless network device based, at least in part, on the second intermediate location of the wireless network device and the target distance calibration constant.

22. The non-transitory machine-readable storage media of claim 21, wherein:

said operation of determining the first intermediate location of the wireless network device and the intermediate distance calibration constant comprises;

executing a single iteration of a first Taylor series based time of arrival positioning algorithm to estimate the first intermediate location of the wireless network device and the intermediate 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, an initial distance calibration constant, and the known location of each of the plurality of reference wireless network devices; and

said operation of iteratively estimating the current location of the wireless network device comprises;

iteratively executing a second Taylor series based time of arrival positioning algorithm to estimate the current location of the wireless network device based, at least in part, on the second intermediate location of the wireless network device, the target distance calibration constant, the distance between the wireless network device and each of the plurality of reference wireless network devices, and the known location of each of the plurality of reference wireless network devices.

23. The non-transitory machine-readable storage media of claim 21, wherein said operation of determining the target distance calibration constant associated with the plurality of reference wireless network devices comprises:

for each of the plurality of reference wireless network devices,

determining a first 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 second distance between the wireless network device and the reference wireless network device based, at least in part, on the known location of the reference wireless network device and the first intermediate location of the wireless network device;

determining a distance difference associated with the reference wireless network device as a difference between the first distance and the second distance; and

determining the distance calibration constant associated with the plurality of reference wireless network devices as a combination of the distance difference associated with each of the plurality of reference wireless network devices.

24. The non-transitory machine-readable storage media of claim 21, wherein said operation of determining the second intermediate location of the wireless network device comprises one of:

determining the second intermediate location of the wireless network device as an average of the known location of each of the plurality of reference wireless network devices;

determining the second intermediate location of the wireless network device as a weighted average of the known location of each of the plurality of reference wireless network devices;

or

designating the first intermediate location of the wireless network device as the second intermediate location of the wireless network device.

25. The non-transitory machine-readable storage media of claim 21, wherein said operation of determining the initial location of the wireless network device based, at least in part, on the known location of each of the plurality of reference wireless network devices comprises:

determining the initial location of the wireless network device as an average of the known location of each of the plurality of reference wireless network devices, or

determining the initial location of the wireless network device as a weighted combination of the known location of at least a subset of the plurality of reference wireless network devices.