POSITIONING TECHNIQUE FOR WIRELESS COMMUNICATION SYSTEM

• US 20130148514A1
• Filed: 12/08/2011
• Published: 06/13/2013
• Est. Priority Date: 12/08/2011
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm Atheros Incorporated (Qualcomm, Inc.)
• Inventors: Zhang, Xiaoxin, Zhang, Ning
• Granted Patent: US 8,824,325 B2
• Time in Patent Office: Days
• US Class Current: 370/252
• 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/0257 Hybrid positioning by coordinating position lines of different shape G01S5/12
• CPC Class Codes: G01S 5/14 Determining absolute distances from a plurality of spaced points of known location

Abstract

A hybrid positioning system can be implemented to improve location estimation of a wireless network device when reference network devices can have different distance calibration constants. For each of a plurality of positions at which the wireless network device is placed and for each reference network device, a distance between the wireless network device and the reference network device is determined. A first positioning algorithm is executed to determine an intermediate location (corresponding to each position) of the wireless network device and a distance calibration constant for each reference network device based, in part, on a corresponding initial location of the wireless network device. A second positioning algorithm is executed to estimate a subset of the positions of the wireless network device based on the intermediate location (corresponding to the position) of the wireless network device and the distance calibration constant of each of reference network devices.

Claims

1. A method comprising:

at each of a plurality of positions at which a wireless network device of a communication network is placed,

for each of a plurality of reference wireless network devices of the communication network, determining a distance between the wireless network device and the reference wireless network device;

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

executing a first set of positioning computations for determining an intermediate location of the wireless network device associated with each of the plurality of positions at which the wireless network device is placed and for determining a target distance calibration constant associated with each of the plurality of reference wireless network devices based, at least in part, on the initial location of the wireless network device and the distance between each of the plurality of positions associated with the wireless network device and each of the plurality of reference wireless network devices; and

for each of one or more of the plurality of positions associated with the wireless network device, iteratively executing a second set of positioning computations for estimating the position of the wireless network device based, at least in part, on the intermediate location of the wireless network device associated with the position of the wireless network device and the distance calibration constant associated with each of the plurality of reference wireless network devices.

2. The method of claim 1, wherein said executing the first set of positioning computations for determining the intermediate location of the wireless network device associated with each of the plurality of positions at which the wireless network device is placed and for determining the target distance calibration constant associated with each of the plurality of reference wireless network devices comprises:

executing, for each of the plurality of positions associated with the wireless network device, a Taylor series based time difference of arrival (TDOA) positioning algorithm to determine a first estimate of the 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, the location of each of the plurality of reference wireless network devices, and an initial distance calibration constant associated with each of the plurality of reference wireless network devices; and

executing, for each of the plurality of reference wireless network devices, the Taylor series based TDOA positioning algorithm to determine a first estimate of the distance calibration constant based, at least in part, on the first estimate of the intermediate location of the wireless network device for each of the plurality of positions associated with the wireless network device, the distance between the wireless network device and the reference wireless network device, and the location of the reference wireless network device.

3. The method of claim 2, wherein said executing, for each of the plurality of reference wireless network devices, the Taylor series based TDOA positioning algorithm to determine the first estimate of the distance calibration constant comprises:

for each of the plurality of reference wireless network devices,

for each of the plurality of positions associated with the wireless network device, determining an intermediate distance calibration constant associated with the reference wireless network device when the wireless network device is at the position based, at least in part, on the first estimate of the intermediate location of the wireless network device, the distance between the wireless network device and the reference wireless network device, and the location of the reference wireless network device; and

combining the intermediate distance calibration constants associated with each of the plurality of positions of the wireless network device to determine the first estimate of the distance calibration constant associated with the reference wireless network device.

4. The method of claim 3, wherein for each of the plurality of reference wireless network devices and for each of the plurality of positions associated with the wireless network device, said determining the intermediate distance calibration constant associated with the reference wireless network device when the wireless network device is at the position comprises:

for each of the plurality of reference wireless network devices,

for each of the plurality of positions associated with the wireless network device,

calculating a first distance between the wireless network device at the position and the reference wireless network device based, at least in part, on a round trip transit time between the wireless network device and the reference wireless network device;

calculating a second distance between the wireless network device and the reference wireless network device based, at least in part, on the location of the reference wireless network device and the first estimate of the intermediate location of the wireless network device at the position; and

calculating the intermediate distance calibration constant associated with the reference wireless network device and the position of the wireless network device as a difference between the first distance and the second distance.

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

6. The method of claim 2, further comprising:

executing, for each of the plurality of positions associated with the wireless network device, the Taylor series based TDOA positioning algorithm to determine a second estimate of the intermediate location of the wireless network device based, at least in part, on the first estimate of the intermediate location of the wireless network device, the distance between the wireless network device and each of the plurality of reference wireless network devices, the location of each of the plurality of reference wireless network devices, and the first estimate of the distance calibration constant associated with each of the plurality of reference wireless network devices; and

executing, for each of the plurality of reference wireless network devices, the Taylor series based TDOA positioning algorithm to determine a second estimate of the distance calibration constant based, at least in part, on the second estimate of the intermediate location of the wireless network device for each of the plurality of positions associated with the wireless network device, the distance between the wireless network device and the reference wireless network device, and the location of the reference wireless network device.

7. The method of claim 2, wherein for each of one or more of the plurality of positions associated with the wireless network device, said iteratively executing the second set of positioning computations for estimating the position of the wireless network device comprises:

for each of one or more of the plurality of positions associated with the wireless network device,

iteratively executing a Taylor series based time of arrival (TOA) positioning algorithm to estimate the position of the wireless network device based, at least in part, on the intermediate location of the wireless network device that corresponds to the position of the wireless network device, the distance calibration constant associated with each of the plurality of reference wireless network devices, the location of each of the plurality of reference wireless network device, and the distance between the wireless network device and each of the plurality of reference wireless network devices.

8. The method of claim 1, wherein the first set of positioning computations are iteratively executed until:

for each of the plurality of positions associated with the wireless network device, an error between a current estimate of the intermediate location of the wireless network device and a preceding estimate of the intermediate location of the wireless network device is less than a predetermined location error threshold,

for each of the plurality of reference wireless network devices, an error between a current estimate of the distance calibration constant and a preceding estimate of the distance calibration constant is less than a predetermined distance calibration error threshold, or

a predetermined number of iterations of the first set of positioning computations are executed.

9. The method of claim 1, wherein said executing the first set of positioning computations for determining the intermediate location of the wireless network device associated with each of the plurality of positions at which the wireless network device is placed and for determining the target distance calibration constant associated with each of the plurality of reference wireless network devices comprises:

executing, for each of the plurality of positions associated with the wireless network device, a first Taylor series based time of arrival (TOA) positioning algorithm to determine a first estimate of the 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, the location of each of the plurality of reference wireless network devices, and an initial distance calibration constant associated with each of the plurality of reference wireless network devices; and

executing, for each of the plurality of reference wireless network devices, the first Taylor series based TOA positioning algorithm to determine a first estimate of the distance calibration constant based, at least in part, on the first estimate of the intermediate location of the wireless network device for each of the plurality of positions associated with the wireless network device, the distance between the wireless network device and the reference wireless network device, and the location of the reference wireless network device.

10. The method of claim 9, wherein for each of one or more of the plurality of positions associated with the wireless network device, said iteratively executing the second set of positioning computations for estimating the position of the wireless network device comprises:

for each of one or more of the plurality of positions associated with the wireless network device,

iteratively executing a second Taylor series based TOA positioning algorithm to estimate the position of the wireless network device based, at least in part, on the intermediate location of the wireless network device that corresponds to the position of the wireless network device, the distance calibration constant associated with each of the plurality of reference wireless network devices, the location of each of the plurality of reference wireless network device, and the distance between the wireless network device and each of the plurality of reference wireless network devices.

11. The method of claim 1, wherein the one or more of the plurality of positions associated with the wireless network device to be estimated comprise:

a current position of the plurality of positions associated with the wireless network device,

all of the positions of the plurality of positions associated with the wireless network device, or

a subset of the plurality of positions associated with the wireless network device.

12. The method of claim 1, further comprising:

at each of the plurality of positions at which the wireless network device of the communication network is placed,

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

wherein at each of the plurality of positions at which the wireless network device of the communication network is placed and for each of the plurality of reference wireless network devices of the communication network, said determining the distance between the wireless network device and the reference wireless network device is based, at least in part on the round trip transit time between the wireless network device and each the reference wireless network device.

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

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

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

14. The method of claim 1, wherein at each of the plurality of positions at which the wireless network device of the communication network is placed, said calculating the initial location of the wireless network device comprises:

for each of the plurality of positions associated with the 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 the initial location of the wireless network device;

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

determining a coefficient matrix as a product of the distance difference 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.

15. The method of claim 1, wherein at each of the plurality of positions at which the wireless network device of the communication network is placed, said calculating the initial location of the wireless network device comprises:

for each of the plurality of positions associated with the 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 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 a 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.

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

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

18. A wireless network device comprising:

a network interface; and

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

at each of a plurality of positions at which the wireless network device of a communication network is placed,

determine for each of a plurality of reference wireless network devices of the communication network, a distance between the wireless network device and the reference wireless network device;

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

execute a first set of positioning computations for determining an intermediate location of the wireless network device associated with each of the plurality of positions at which the wireless network device is placed and for determining a target distance calibration constant associated with each of the plurality of reference wireless network devices based, at least in part, on the initial location of the wireless network device and the distance between each of the plurality of positions associated with the wireless network device and each of the plurality of reference wireless network devices; and

for each of one or more of the plurality of positions associated with the wireless network device, iteratively execute a second set of positioning computations for estimating the position of the wireless network device based, at least in part, on the intermediate location of the wireless network device associated with the position of the wireless network device and the distance calibration constant associated with each of the plurality of reference wireless network devices.

19. The wireless network device of claim 18, wherein the location calculation unit operable to execute the first set of positioning computations for determining the intermediate location of the wireless network device associated with each of the plurality of positions at which the wireless network device is placed and for determining the target distance calibration constant associated with each of the plurality of reference wireless network devices comprises the location calculation unit operable to:

execute, for each of the plurality of positions associated with the wireless network device, a Taylor series based time difference of arrival (TDOA) positioning algorithm to determine a first estimate of the 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, the location of each of the plurality of reference wireless network devices, and an initial distance calibration constant associated with each of the plurality of reference wireless network devices; and

execute, for each of the plurality of reference wireless network devices, the Taylor series based TDOA positioning algorithm to determine a first estimate of the distance calibration constant based, at least in part, on the first estimate of the intermediate location of the wireless network device for each of the plurality of positions associated with the wireless network device, the distance between the wireless network device and the reference wireless network device, and the location of the reference wireless network device.

20. The wireless network device of claim 19, wherein the location calculation unit operable to execute, for each of the plurality of reference wireless network devices, the Taylor series based TDOA positioning algorithm to determine the first estimate of the distance calibration constant comprises the location calculation unit operable to:

for each of the plurality of reference wireless network devices,

for each of the plurality of positions associated with the wireless network device, determine an intermediate distance calibration constant associated with the reference wireless network device when the wireless network device is at the position based, at least in part, on the first estimate of the intermediate location of the wireless network device, the distance between the wireless network device and the reference wireless network device, and the location of the reference wireless network device; and

combine the intermediate distance calibration constants associated with each of the plurality of positions of the wireless network device to determine the first estimate of the distance calibration constant associated with the reference wireless network device.

21. The wireless network device of claim 20, wherein for each of the plurality of reference wireless network devices and for each of the plurality of positions associated with the wireless network device, the location calculation unit operable to determine the intermediate distance calibration constant associated with the reference wireless network device when the wireless network device is at the position comprises the location calculation unit operable to:

for each of the plurality of reference wireless network devices,

for each of the plurality of positions associated with the wireless network device,

calculate a first distance between the wireless network device at the position and the reference wireless network device based, at least in part, on a round trip transit time between the wireless network device and the reference wireless network device;

calculate a second distance between the wireless network device and the reference wireless network device based, at least in part, on the location of the reference wireless network device and the first estimate of the intermediate location of the wireless network device at the position; and

calculate the intermediate distance calibration constant associated with the reference wireless network device and the position of the wireless network device as a difference between the first distance and the second distance.

22. The wireless network device of claim 19, wherein for each of one or more of the plurality of positions associated with the wireless network device, the location calculation unit operable to iteratively execute the second set of positioning computations for estimating the position of the wireless network device comprises the location calculation unit operable to:

for each of one or more of the plurality of positions associated with the wireless network device,

iteratively execute a Taylor series based time of arrival (TOA) positioning algorithm to estimate the position of the wireless network device based, at least in part, on the intermediate location of the wireless network device that corresponds to the position of the wireless network device, the distance calibration constant associated with each of the plurality of reference wireless network devices, the location of each of the plurality of reference wireless network device, and the distance between the wireless network device and each of the plurality of reference wireless network devices.

23. The wireless network device of claim 18, wherein the location calculation unit operable to execute the first set of positioning computations for determining the intermediate location of the wireless network device associated with each of the plurality of positions at which the wireless network device is placed and for determining the target distance calibration constant associated with each of the plurality of reference wireless network devices comprises the location calculation unit operable to:

execute, for each of the plurality of positions associated with the wireless network device, a first Taylor series based time of arrival (TOA) positioning algorithm to determine a first estimate of the 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, the location of each of the plurality of reference wireless network devices, and an initial distance calibration constant associated with each of the plurality of reference wireless network devices; and

execute, for each of the plurality of reference wireless network devices, the first Taylor series based TOA positioning algorithm to determine a first estimate of the distance calibration constant based, at least in part, on the first estimate of the intermediate location of the wireless network device for each of the plurality of positions associated with the wireless network device, the distance between the wireless network device and the reference wireless network device, and the location of the reference wireless network device.

24. The wireless network device of claim 23, wherein for each of one or more of the plurality of positions associated with the wireless network device, the location calculation unit operable to iteratively execute the second set of positioning computations for estimating the position of the wireless network device comprises the location calculation unit operable to:

for each of one or more of the plurality of positions associated with the wireless network device,

iteratively execute a second Taylor series based TOA positioning algorithm to estimate the position of the wireless network device based, at least in part, on the intermediate location of the wireless network device that corresponds to the position of the wireless network device, the distance calibration constant associated with each of the plurality of reference wireless network devices, the location of each of the plurality of reference wireless network device, and the distance between the wireless network device and each of the plurality of reference wireless network devices.

25. 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:

at each of a plurality of positions at which a wireless network device of a communication network is placed,

for each of a plurality of reference wireless network devices of the communication network, determining a distance between the wireless network device and the reference wireless network device;

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

executing a first set of positioning computations for determining an intermediate location of the wireless network device associated with each of the plurality of positions at which the wireless network device is placed and for determining a target distance calibration constant associated with each of the plurality of reference wireless network devices based, at least in part, on the initial location of the wireless network device and the distance between each of the plurality of positions associated with the wireless network device and each of the plurality of reference wireless network devices; and

for each of one or more of the plurality of positions associated with the wireless network device, iteratively executing a second set of positioning computations for estimating the position of the wireless network device based, at least in part, on the intermediate location of the wireless network device associated with the position of the wireless network device and the distance calibration constant associated with each of the plurality of reference wireless network devices.

26. The machine-readable storage media of claim 25,

wherein said operation of executing the first set of positioning computations for determining the intermediate location of the wireless network device associated with each of the plurality of positions at which the wireless network device is placed and for determining the target distance calibration constant associated with each of the plurality of reference wireless network devices comprises:

executing, for each of the plurality of positions associated with the wireless network device, a Taylor series based time difference of arrival (TDOA) positioning algorithm to determine a first estimate of the 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, the location of each of the plurality of reference wireless network devices, and an initial distance calibration constant associated with each of the plurality of reference wireless network devices; and

executing, for each of the plurality of reference wireless network devices, the Taylor series based TDOA positioning algorithm to determine a first estimate of the distance calibration constant based, at least in part, on the first estimate of the intermediate location of the wireless network device for each of the plurality of positions associated with the wireless network device, the distance between the wireless network device and the reference wireless network device, and the location of the reference wireless network device; and

wherein for each of one or more of the plurality of positions associated with the wireless network device, said operation of iteratively executing the second set of positioning computations for estimating the position of the wireless network device comprises;

for each of one or more of the plurality of positions associated with the wireless network device, iteratively executing a Taylor series based time of arrival (TOA) positioning algorithm to estimate the position of the wireless network device based, at least in part, on the intermediate location of the wireless network device that corresponds to the position of the wireless network device, the distance calibration constant associated with each of the plurality of reference wireless network devices, the location of each of the plurality of reference wireless network device, and the distance between the wireless network device and each of the plurality of reference wireless network devices.

27. The machine-readable storage media of claim 26, wherein said operation of executing, for each of the plurality of reference wireless network devices, the Taylor series based TDOA positioning algorithm to determine the first estimate of the distance calibration constant comprises:

for each of the plurality of reference wireless network devices,

for each of the plurality of positions associated with the wireless network device,

calculating a first distance between the wireless network device at the position and the reference wireless network device based, at least in part, on a round trip transit time between the wireless network device and the reference wireless network device;

calculating a second distance between the wireless network device and the reference wireless network device based, at least in part, on the location of the reference wireless network device and the first estimate of the intermediate location of the wireless network device at the position;

determining an intermediate distance calibration constant associated with the reference wireless network device and the position of the wireless network device as a difference between the first distance and the second distance; and

combining the intermediate distance calibration constants associated with each of the plurality of positions of the wireless network device to determine the first estimate of the distance calibration constant associated with the reference wireless network device.

28. The machine-readable storage media of claim 25,

wherein said operation of executing the first set of positioning computations for determining the intermediate location of the wireless network device associated with each of the plurality of positions at which the wireless network device is placed and for determining the target distance calibration constant associated with each of the plurality of reference wireless network devices comprises:

executing, for each of the plurality of positions associated with the wireless network device, a first Taylor series based time of arrival (TOA) positioning algorithm to determine a first estimate of the 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, the location of each of the plurality of reference wireless network devices, and an initial distance calibration constant associated with each of the plurality of reference wireless network devices; and

executing, for each of the plurality of reference wireless network devices, the first Taylor series based TOA positioning algorithm to determine a first estimate of the distance calibration constant based, at least in part, on the first estimate of the intermediate location of the wireless network device for each of the plurality of positions associated with the wireless network device, the distance between the wireless network device and the reference wireless network device, and the location of the reference wireless network device; and

wherein for each of one or more of the plurality of positions associated with the wireless network device, said operation of iteratively executing the second set of positioning computations for estimating the position of the wireless network device comprises;

for each of one or more of the plurality of positions associated with the wireless network device, iteratively executing a second Taylor series based TOA positioning algorithm to estimate the position of the wireless network device based, at least in part, on the intermediate location of the wireless network device that corresponds to the position of the wireless network device, the distance calibration constant associated with each of the plurality of reference wireless network devices, the location of each of the plurality of reference wireless network device, and the distance between the wireless network device and each of the plurality of reference wireless network devices.