TIME OF ARRIVAL BASED POSITIONING FOR WIRELESS COMMUNICATION SYSTEMS

• US 20130100850A1
• Filed: 10/21/2011
• Published: 04/25/2013
• Est. Priority Date: 10/21/2011
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm Atheros Incorporated (Qualcomm, Inc.)
• Inventors: Zhang, Xiaoxin, Zhang, Ning
• Granted Patent: US 8,755,304 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: G01S 13/74 Systems using reradiation of radio waves, e.g. secondary radar systems; Analogous systems
• CPC Class Codes: G01S 13/878 Combination of several spaced transmitters or receivers of known location for determining the position of a transponder or a reflector G01S13/874 takes precedence
• CPC Class Codes: G01S 5/14 Determining absolute distances from a plurality of spaced points of known location

Abstract

A TOA positioning system can be implemented to improve location estimation of a wireless network device. A first subset of a plurality of reference wireless network devices for determining potential locations of the wireless network device and a second subset of the plurality of reference wireless network devices for determining an estimated location of the wireless network device can be selected. The first and the second subsets can be selected based on a plurality of distance measurements and an average distance and associated with each of the plurality of reference wireless network devices. The potential locations of the wireless network device can be determined based on the first subset of the plurality of reference wireless network devices. The estimated location of the wireless network device can be determined from the potential locations of the wireless network device based on the second subset of the plurality of reference wireless network devices.

Claims

1. A method comprising:

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

determining, for each of the plurality of reference wireless network devices, a plurality of distance measurements between the wireless network device and the reference wireless network device based on a corresponding plurality of round trip transit time measurements between the wireless network device and the reference wireless network device;

calculating, for each of the plurality of reference wireless network devices, an average distance between the wireless network device and the reference wireless network device based on a corresponding plurality of distance measurements between the wireless network device and the reference wireless network device;

selecting a first subset of the plurality of reference wireless network devices for determining one or more potential locations of the wireless network device based, at least in part, on the average distance between the wireless network device and each of the plurality of reference wireless network devices and on the plurality of distance measurements between the wireless network device and each of the plurality of reference wireless network device;

selecting a second subset of the plurality of reference wireless network devices for determining an estimated location of the wireless network device based, at least in part, on the first subset of the plurality of reference wireless network devices, the average distance between the wireless network device and each of the plurality of reference wireless network devices, and the plurality of distance measurements between the wireless network device and each of the plurality of reference wireless network device;

determining the one or more potential locations of the wireless network device based, at least in part, on the first subset of the plurality of reference wireless network devices; and

determining the estimated location of the wireless network device from the one or more potential locations of the wireless network device based, at least in part, on the second subset of the plurality of reference wireless network devices.

2. The method of claim 1, wherein said selecting the first subset of the plurality of reference wireless network devices for determining the one or more potential locations of the wireless network device comprises:

comparing each of the average distances between the wireless network device and each of the plurality of reference wireless network devices;

identifying a predetermined number of the plurality of reference wireless network devices associated with the smallest average distances based on said comparing each of the average distances between the wireless network device and each of the plurality of reference wireless network devices; and

designating the predetermined number of the plurality of reference wireless network devices associated with the smallest average distances as the first subset of the plurality of reference wireless network devices.

3. The method of claim 1, wherein said selecting the first subset of the plurality of reference wireless network devices for determining the one or more potential locations of the wireless network device comprises:

for each of the plurality of reference wireless network devices, calculating a distance variance associated with the reference wireless network device based, at least in part, on the plurality of distance measurements between the wireless network device and the reference wireless network device and the average distance between the wireless network device and the reference wireless network device;

comparing the distance variances associated with each of the plurality of reference wireless network devices;

identifying a predetermined number of the plurality of reference wireless network devices associated with the smallest distance variances based on said comparing the distance variances associated with each of the plurality of reference wireless network devices; and

designating the predetermined number of the plurality of reference wireless network devices associated with the smallest distance variances as the first subset of the plurality of reference wireless network devices.

4. The method of claim 1, wherein said selecting the second subset of the plurality of reference wireless network devices for determining the estimated location of the wireless network device comprises:

selecting the second subset of the plurality of reference wireless network devices that is distinct from the first subset of the plurality of reference wireless network devices.

5. The method of claim 1, wherein said selecting the second subset of the plurality of reference wireless network devices for determining the estimated location of the wireless network device comprises:

identifying a remainder of the plurality of reference wireless network devices that do not include the first subset of the plurality of reference wireless network devices;

comparing each of the average distances between the wireless network device and each of the remainder of the plurality of reference wireless network devices;

identifying a predetermined number of the remainder of the plurality of reference wireless network devices associated with the smallest average distances based on said comparing each of the average distances between the wireless network device and each of the remainder of the plurality of reference wireless network devices; and

designating the predetermined number of the remainder of the plurality of reference wireless network devices associated with the smallest average distances as the second subset of the plurality of reference wireless network devices.

6. The method of claim 1, wherein said selecting the second subset of the plurality of reference wireless network devices for determining the estimated location of the wireless network device comprises:

identifying a remainder of the plurality of reference wireless network devices that do not include the first subset of the plurality of reference wireless network devices;

for each of the remainder of the plurality of reference wireless network devices, calculating a distance variance associated with the reference wireless network device based, at least in part, on the plurality of distance measurements between the wireless network device and the reference wireless network device and the average distance between the wireless network device and the reference wireless network device;

comparing the distance variances associated with each of the remainder of the plurality of reference wireless network devices;

identifying a predetermined number of the remainder of the plurality of reference wireless network devices associated with smallest distance variances based on said comparing the distance variances associated with each of the remainder of the plurality of reference wireless network devices; and

designating the predetermined number of the remainder of the plurality of reference wireless network devices associated with the smallest distance variances as the second subset of the plurality of reference wireless network devices.

7. The method of claim 1, wherein said determining the one or more potential locations of the wireless network device comprises:

executing a minimum mean square error based time of arrival positioning algorithm to determine the one or more potential locations of the wireless network device based, at least in part, on the average distance between the wireless network device and each of the first subset of the plurality of reference wireless network devices, a location of each of the first subset of the plurality of reference wireless network devices, and a distance calibration constant, or

executing one or more iterations of a Taylor series based time of arrival positioning algorithm to determine a first of the one or more potential locations of the wireless network device based, at least in part, on the average distance between the wireless network device and each of the first subset of the plurality of reference wireless network devices, the location of each of the first subset of the plurality of reference wireless network devices, the initial location of the wireless network device, and the distance calibration constant.

8. The method of claim 1, wherein said determining the estimated location of the wireless network device from the one or more potential locations of the wireless network device comprises:

selecting the estimated location of the wireless network device from the one or more potential locations of the wireless network device based, at least in part, on the average distance between the wireless network device and each of the second subset of the plurality of reference wireless network devices, a location of each of the second subset of the plurality of reference wireless network devices, and a distance calibration constant.

9. The method of claim 1, wherein said determining the estimated location of the wireless network device from the one or more potential locations of the wireless network device comprises:

for each of the one or more potential locations of the wireless network device, computing a distance error associated with the potential location of the wireless network device based, at least in part, on the average distances between the wireless network device and each of the second subset of the reference wireless network devices, on the potential location of the wireless network device, and on a location of each of the second subset of the reference wireless network devices;

comparing the distance errors associated with each of the one or more potential locations of the wireless network device;

identifying a first of the one or more potential locations of the wireless network device associated with the smallest distance error based on said comparing the distance errors associated with each of the one or more potential locations of the wireless network device; and

designating the first of the one or more potential locations of the wireless network device associated with the smallest distance error as the estimated location of the wireless network device.

10. The method of claim 1, wherein said determining the estimated location of the wireless network device from the one or more potential locations of the wireless network device comprises

for each of the one or more potential locations of the wireless network device, computing a squared distance error associated with the potential location of the wireless network device based, at least in part, on the average distances between the wireless network device and each of the second subset of the reference wireless network devices, on the potential location of the wireless network device, and on a location of each of the second subset of the reference wireless network devices;

comparing the squared distance errors associated with each of the one or more potential locations of the wireless network device;

identifying a first of the one or more potential locations of the wireless network device associated with the smallest squared distance error based on said comparing the squared distance errors associated with each of the one or more potential locations of the wireless network device; and

designating the first of the one or more potential locations of the wireless network device associated with the smallest squared distance error as the estimated location of the wireless network device.

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

12. 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 plurality of round trip transit time measurements between a wireless network device and each of a plurality of reference wireless network devices;

determine, for each of the plurality of reference wireless network devices, a plurality of distance measurements between the wireless network device and the reference wireless network device based on a corresponding plurality of round trip transit time measurements between the wireless network device and the reference wireless network device;

calculate, for each of the plurality of reference wireless network devices, an average distance between the wireless network device and the reference wireless network device based on a corresponding plurality of distance measurements between the wireless network device and the reference wireless network device;

select a first subset of the plurality of reference wireless network devices for determining one or more potential locations of the wireless network device based, at least in part, on the average distance between the wireless network device and each of the plurality of reference wireless network devices and on the plurality of distance measurements between the wireless network device and each of the plurality of reference wireless network device;

select a second subset of the plurality of reference wireless network devices for determining an estimated location of the wireless network device based, at least in part, on the first subset of the plurality of reference wireless network devices, the average distance between the wireless network device and each of the plurality of reference wireless network devices, and the plurality of distance measurements between the wireless network device and each of the plurality of reference wireless network device;

determine the one or more potential locations of the wireless network device based, at least in part, on the first subset of the plurality of reference wireless network devices; and

determine the estimated location of the wireless network device from the one or more potential locations of the wireless network device based, at least in part, on the second subset of the plurality of reference wireless network devices.

13. The wireless network device of claim 12, wherein the location calculation unit operable to select the first subset of the plurality of reference wireless network devices for determining the one or more potential locations of the wireless network device comprises the location calculation unit operable to:

compare each of the average distances between the wireless network device and each of the plurality of reference wireless network devices;

identify a predetermined number of the plurality of reference wireless network devices associated with the smallest average distances based on the location calculation unit comparing each of the average distances between the wireless network device and each of the plurality of reference wireless network devices; and

designate the predetermined number of the plurality of reference wireless network devices associated with the smallest average distances as the first subset of the plurality of reference wireless network devices.

14. The wireless network device of claim 12, wherein the location calculation unit operable to select the first subset of the plurality of reference wireless network devices for determining the one or more potential locations of the wireless network device comprises the location calculation unit operable to:

for each of the plurality of reference wireless network devices, calculate a distance variance associated with the reference wireless network device based, at least in part, on the plurality of distance measurements between the wireless network device and the reference wireless network device and the average distance between the wireless network device and the reference wireless network device;

compare the distance variances associated with each of the plurality of reference wireless network devices;

identify a predetermined number of the plurality of reference wireless network devices associated with the smallest distance variances based on the location calculation unit comparing the distance variances associated with each of the plurality of reference wireless network devices; and

designate the predetermined number of the plurality of reference wireless network devices associated with the smallest distance variances as the first subset of the plurality of reference wireless network devices.

15. The wireless network device of claim 12, wherein the location calculation unit operable to select the second subset of the plurality of reference wireless network devices for determining the estimated location of the wireless network device comprises the location calculation unit operable to:

select the second subset of the plurality of reference wireless network devices that is distinct from the first subset of the plurality of reference wireless network devices.

16. The wireless network device of claim 12, wherein the location calculation unit operable to select the second subset of the plurality of reference wireless network devices for determining the estimated location of the wireless network device comprises the location calculation unit operable to:

identify a remainder of the plurality of reference wireless network devices that do not include the first subset of the plurality of reference wireless network devices;

compare each of the average distances between the wireless network device and each of the remainder of the plurality of reference wireless network devices;

identify a predetermined number of the remainder of the plurality of reference wireless network devices associated with the smallest average distances based on the location calculation unit comparing each of the average distances between the wireless network device and each of the remainder of the plurality of reference wireless network devices; and

designate the predetermined number of the remainder of the plurality of reference wireless network devices associated with the smallest average distances as the second subset of the plurality of reference wireless network devices.

17. The wireless network device of claim 12, wherein the location calculation unit operable to select the second subset of the plurality of reference wireless network devices for determining the estimated location of the wireless network device comprises the location calculation unit operable to:

identify a remainder of the plurality of reference wireless network devices that do not include the first subset of the plurality of reference wireless network devices;

for each of the remainder of the plurality of reference wireless network devices, calculate a distance variance associated with the reference wireless network device based, at least in part, on the plurality of distance measurements between the wireless network device and the reference wireless network device and the average distance between the wireless network device and the reference wireless network device;

compare the distance variances associated with each of the remainder of the plurality of reference wireless network devices;

identify a predetermined number of the remainder of the plurality of reference wireless network devices associated with smallest distance variances based on the location calculation unit comparing the distance variances associated with each of the remainder of the plurality of reference wireless network devices; and

designate the predetermined number of the remainder of the plurality of reference wireless network devices associated with the smallest distance variances as the second subset of the plurality of reference wireless network devices.

18. The wireless network device of claim 12, wherein the location calculation unit operable to determine the estimated location of the wireless network device from the one or more potential locations of the wireless network device comprises the location calculation unit operable to:

for each of the one or more potential locations of the wireless network device, compute a squared distance error associated with the potential location of the wireless network device based, at least in part, on the average distances between the wireless network device and each of the second subset of the reference wireless network devices, on the potential location of the wireless network device, and on a location of each of the second subset of the reference wireless network devices;

compare the squared distance errors associated with each of the one or more potential locations of the wireless network device;

identify a first of the one or more potential locations of the wireless network device associated with the smallest squared distance error based on the location calculation unit comparing the squared distance errors associated with each of the one or more potential locations of the wireless network device; and

designate the first of the one or more potential locations of the wireless network device associated with the smallest squared distance error as the estimated location of the wireless network device

19. 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 a plurality of round trip transit time measurements between a wireless network device and each of a plurality of reference wireless network devices;

determining, for each of the plurality of reference wireless network devices, a plurality of distance measurements between the wireless network device and the reference wireless network device based on a corresponding plurality of round trip transit time measurements between the wireless network device and the reference wireless network device;

calculating, for each of the plurality of reference wireless network devices, an average distance between the wireless network device and the reference wireless network device based on a corresponding plurality of distance measurements between the wireless network device and the reference wireless network device;

selecting a first subset of the plurality of reference wireless network devices for determining one or more potential locations of the wireless network device based, at least in part, on the average distance between the wireless network device and each of the plurality of reference wireless network devices and on the plurality of distance measurements between the wireless network device and each of the plurality of reference wireless network device;

selecting a second subset of the plurality of reference wireless network devices for determining an estimated location of the wireless network device based, at least in part, on the first subset of the plurality of reference wireless network devices, the average distance between the wireless network device and each of the plurality of reference wireless network devices, and the plurality of distance measurements between the wireless network device and each of the plurality of reference wireless network device;

determining the one or more potential locations of the wireless network device based, at least in part, on the first subset of the plurality of reference wireless network devices; and

determining the estimated location of the wireless network device from the one or more potential locations of the wireless network device based, at least in part, on the second subset of the plurality of reference wireless network devices.

20. The machine-readable storage media of claim 19, wherein said operation of selecting the first subset of the plurality of reference wireless network devices for determining the one or more potential locations of the wireless network device comprises:

comparing each of the average distances between the wireless network device and each of the plurality of reference wireless network devices;

identifying a predetermined number of the plurality of reference wireless network devices associated with the smallest average distances based on said comparing each of the average distances between the wireless network device and each of the plurality of reference wireless network devices; and

designating the predetermined number of the plurality of reference wireless network devices associated with the smallest average distances as the first subset of the plurality of reference wireless network devices.

21. The machine-readable storage media of claim 19, wherein said operation of selecting the first subset of the plurality of reference wireless network devices for determining the one or more potential locations of the wireless network device comprises:

for each of the plurality of reference wireless network devices, calculating a distance variance associated with the reference wireless network device based, at least in part, on the plurality of distance measurements between the wireless network device and the reference wireless network device and the average distance between the wireless network device and the reference wireless network device;

comparing the distance variances associated with each of the plurality of reference wireless network devices;

identifying a predetermined number of the plurality of reference wireless network devices associated with the smallest distance variances based on said comparing the distance variances associated with each of the plurality of reference wireless network devices; and

designating the predetermined number of the plurality of reference wireless network devices associated with the smallest distance variances as the first subset of the plurality of reference wireless network devices.

22. The machine-readable storage media of claim 19, wherein said operation of selecting the second subset of the plurality of reference wireless network devices for determining the estimated location of the wireless network device comprises:

selecting the second subset of the plurality of reference wireless network devices that is distinct from the first subset of the plurality of reference wireless network devices.

23. The machine-readable storage media of claim 19, wherein said operation of selecting the second subset of the plurality of reference wireless network devices for determining the estimated location of the wireless network device comprises:

identifying a remainder of the plurality of reference wireless network devices that do not include the first subset of the plurality of reference wireless network devices;

comparing each of the average distances between the wireless network device and each of the remainder of the plurality of reference wireless network devices;

identifying a predetermined number of the remainder of the plurality of reference wireless network devices associated with the smallest average distances based on said comparing each of the average distances between the wireless network device and each of the remainder of the plurality of reference wireless network devices; and

designating the predetermined number of the remainder of the plurality of reference wireless network devices associated with the smallest average distances as the second subset of the plurality of reference wireless network devices.

24. The machine-readable storage media of claim 19, wherein said operation of selecting the second subset of the plurality of reference wireless network devices for determining the estimated location of the wireless network device comprises:

identifying a remainder of the plurality of reference wireless network devices that do not include the first subset of the plurality of reference wireless network devices;

for each of the remainder of the plurality of reference wireless network devices, calculating a distance variance associated with the reference wireless network device based, at least in part, on the plurality of distance measurements between the wireless network device and the reference wireless network device and the average distance between the wireless network device and the reference wireless network device;

comparing the distance variances associated with each of the remainder of the plurality of reference wireless network devices;

identifying a predetermined number of the remainder of the plurality of reference wireless network devices associated with smallest distance variances based on said comparing the distance variances associated with each of the remainder of the plurality of reference wireless network devices; and

designating the predetermined number of the remainder of the plurality of reference wireless network devices associated with the smallest distance variances as the second subset of the plurality of reference wireless network devices.

25. The machine-readable storage media of claim 19, wherein said operation of determining the estimated location of the wireless network device from the one or more potential locations of the wireless network device comprises:

for each of the one or more potential locations of the wireless network device,

computing a distance error associated with the potential location of the wireless network device based, at least in part, on the average distances between the wireless network device and each of the second subset of the reference wireless network devices, on the potential location of the wireless network device, and on a location of each of the second subset of the reference wireless network devices;

comparing the distance errors associated with each of the one or more potential locations of the wireless network device;

identifying a first of the one or more potential locations of the wireless network device associated with the smallest distance error based on said comparing the distance errors associated with each of the one or more potential locations of the wireless network device; and

designating the first of the one or more potential locations of the wireless network device associated with the smallest distance error as the estimated location of the wireless network device.