Method and device for determining a location of a communications device

• US 7,783,301 B2
• Filed: 12/19/2006
• Issued: 08/24/2010
• Est. Priority Date: 12/19/2006
• Status: Expired due to Fees

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: Bornholdt, James M.
• Primary Examiner(s): Corsaro; Nick
• Assistant Examiner(s): PLATA, EDD RIANNE L
• Application Number:
  US11/612,674
• Publication Number:
  US 20080146246A1
• Time in Patent Office: 1,344 Days
• Field of Search: 455/404.2, 455/456.1, 455/456.5, 455/456.6, 701/207
• US Class Current: 455/456.1
• CPC Class Codes: G01S 5/0244 Accuracy or reliability of position solution or of measurements contributing thereto
• CPC Class Codes: G01S 5/0273 using multipath or indirect path propagation signals in position determination

Abstract

A method to determine a location of a communications device may include measuring a time of arrival for each pulse received at a receiver. The method may also include generating a set of possible hypothetical matches between each received pulse and a transmission path between a transmitter and the receiver, wherein the communications device being located is one of the transmitter and the receiver. The method may further include estimating the location of the communications device using the set of hypothetical matches.

Claims

1. A method to determine a location of a communications device, comprising:

measuring a time of arrival for each pulse received at a receiver;

generating a plurality of transmission path-time matching hypotheses, each transmission path-time matching hypothesis including a set of hypothetical matches between each received pulse and a possible transmission path between a transmitter and the receiver, wherein each hypothetical match corresponds to the received pulse being able to have traveled over the possible transmission path between the transmitter and the receiver based on a transmit time of the received pulse, wherein generating the plurality of transmission path-time matching hypotheses comprises;

determining possible transmission paths from the transmitter to the receiver including all combinations for any bounces or scattering from any scattering centers;

determining substantially all permutations of transmission paths grouped into sets of different transmission paths based on a number of pulses received by the receiver;

associating each transmission path in each set of different transmission paths with a unique pulse of the pulses received for each permutation; and

creating a hypothetical match between the unique pulse and the associated transmission path for each permutation, the unique pulse being able to have traveled over the associated transmission path, wherein each of the plurality of transmission path-time matching hypotheses includes a set of different hypothetical matches corresponding to each set of different transmission paths;

determining an intersection error for each transmission path-time matching hypothesis, wherein each hypothetical match defines a locus of possible communications device locations and an intersection of loci of the set of different hypothetical matches for each transmission path-time matching hypothesis provides an estimate of the location of the communications device for that transmission path-time matching hypothesis, the intersection error for each transmission path-time matching hypothesis providing an indication that the intersection of loci for each transmission path-time matching hypothesis being substantially at a single point to estimate the location of the communications device; and

estimating the location of the communications device as the intersection of loci for the transmission path-time matching hypothesis with a lowest intersection error.

2. The method of claim 1, wherein estimating the location of the communications device comprises determining the locus of possible communications device locations for each pulse using the hypothetical matches.

3. The method of claim 2, further comprising determining the estimated location of the communications device as the intersection of possible communications device location loci for each set of hypothetical matches for each pulse.

4. The method of claim 2, further comprising:

defining a hypothetical transmit time for each pulse in response to the transmit time for each pulse being unknown;

generating an additional set of hypothetical matches for each hypothetical transmit time and transmission path;

determining a locus of possible communications device locations using each set of hypothetical matches for each pulse and each hypothetical transmit time; and

determining an estimated location of the communications device as an intersection of possible communications device location loci for each set of hypothetical matches for each pulse and for each hypothetical transmit time.

5. The method of claim 2, wherein determining the locus of possible communications device locations comprises defining a circle centered at a first scattering center from the communications device in each hypothetical match including a NLOS transmission path, if the communications device to be located is the transmitter.

6. The method of claim 2, wherein determining the locus of possible communications device locations comprises defining a circle centered at a last scattering center before the communications device in each hypothetical match including a NLOS transmission path, if the communications device to be located is the receiver.

7. The method of claim 1, wherein determining the intersection error, comprises:

approximating each locus of possible communications device locations as a set of discrete points;

looping each discrete point over other loci for each possible communications device location;

determining a residual error for each discrete point in loci for each possible communications device location;

determining a sum of squares of residual error for each discrete point; and

selecting the estimated communications device location as a discrete point with a minimum sum of residual errors.

8. The method of claim 1, further comprising forming a set of possible transmission paths from the transmitter to the receiver.

9. The method of claim 8, wherein forming the set of possible transmission paths comprises:

forming a direct transmission path from the transmitter to the receiver;

forming all combinations for bounces from any scattering centers; and

determining all permutations of possible transmission paths grouped into sets of elements based on a number of pulses received by the receiver.

10. The method of claim 9, further comprising associating each set of elements with a unique received pulse for each permutation.

11. The method of claim 10, further comprising creating each hypothetical match associated with a unique pulse for each transmit time or hypothetical transmit time.

12. The method of claim 1, further comprising determining a location of any scattering centers.

13. The method of claim 12, further comprising:

estimating a location of the receiver if the communications device to be located is the transmitter; and

estimating a location of the transmitter if the communications device to be located is the receiver.

14. A method to determine a location of a communications device, comprising:

measuring a time of arrival for each pulse received at a receiver;

generating a plurality of transmission path-time matching hypotheses, wherein generating the plurality of transmission path-time matching hypotheses comprises;

determining possible transmission paths from the transmitter to the receiver including all combinations for any bounces or scattering from any scattering centers;

determining substantially all permutations of transmission paths grouped into sets of different transmission paths based on a number of pulses received by the receiver;

associating each transmission path in each set of different transmission paths with a unique of the pulses received for each permutation; and

creating a hypothetical match between the unique pulse and the associated transmission path for each permutation, the unique pulse being able to have traveled over the associated transmission path, wherein each of the plurality of transmission path-time matching hypotheses includes a set of different hypothetical matches corresponding to each set of different transmission paths;

determining an intersection error for each transmission path-time matching hypotheses, wherein each hypothetical match defines a locus of possible communications device locations and an intersection of loci of the set of different hypothetical matches for each transmission path-time matching hypothesis provides an estimate of the location of the communications device for that transmission path-time matching hypothesis, the intersection error for each transmission path-time matching hypothesis providing an indication that the intersection of loci for each transmission path-time matching hypothesis being substantially at a single point to estimate the location of the communications device; and

determining the estimated location of the communications device as an intersection of loci for the transmission path-time matching hypothesis with a lowest intersection error.

15. The method of claim 14, further comprising:

defining a hypothetical transmit time for each pulse in response to a transmit time for each pulse being unknown;

generating an additional set of hypothetical matches for each hypothetical transmit time, pulse and transmission path;

determining a locus of possible communications device locations using each set of hypothetical matches for each pulse and each hypothetical transmit time; and

determining an estimated location of the communications device as an intersection of possible communications device location loci for each set of hypothetical matches for each pulse and for each hypothetical transmit time.

16. The method of claim 15, wherein determining the locus of possible communications device locations comprises defining a circle centered at a first scattering center from the communications device in each hypothetical match including a NLOS transmission path if the communications device to be located is the transmitter.

17. The method of claim 15, wherein determining the locus of possible communications device locations comprises defining a circle centered around a last scattering center before the communications device in each hypothetical match including a NLOS transmission path if the communications device to be located is the receiver.

18. A device to determine a location of a communications device, comprising:

a processor;

a location determination module including a hypothetical match evaluation element operable on the processor to evaluate a match between each received pulse and a possible transmission path of the pulse to determine a location of the communications device, wherein the location determination module comprises;

means for measuring a time of arrival for each pulse received at a receiver;

means for generating a plurality of transmission path-time matching hypotheses, wherein the means for generating the plurality of transmission path-time matching hypotheses comprises;

means for determining possible transmission paths from the transmitter to the receiver including all combinations for any bounces or scattering from any scattering centers;

means for determining substantially all permutations of transmission paths grouped into sets of different transmission paths based on a number of pulses received by the receiver;

means for associating each transmission path in each set of different transmission paths with a unique pulse of the pulses received for each permutation; and

means for creating a hypothetical match between the unique pulse and the associated transmission path for each permutation, the unique pulse being able to have traveled over the associated transmission path, wherein each of the plurality of transmission path-time matching hypotheses includes a set of different hypothetical matches corresponding to each set of different transmission paths;

a module for determining an intersection error for each transmission path-time matching hypotheses, wherein each hypothetical match defines a locus of possible communications device locations and an intersection of loci of the set of different hypothetical matches for each transmission path-time matching hypothesis provides an estimate of the location of the communications device for that transmission path-time matching hypothesis, the intersection error for each transmission path-time matching hypothesis providing an indication that the intersection of loci for each transmission path-time matching hypothesis being substantially at a single point to estimate the location of the communications device; and

means for estimating the location of the communications device as the intersection of loci for the transmission path-time matching hypothesis with a lowest intersection error.

19. The device of claim 18, wherein the means for estimating the location of the communications device comprises means for determining the locus of possible communications device locations using the hypothetical matches for each pulse.

20. The device of claim 19, further comprising means for determining the estimated location of the communications device as the intersection of possible communications device location loci for each set of hypothetical transmission paths for each pulse.

21. The device of claim 19, further comprising:

means for defining a hypothetical transmit time for each pulse in response to a transmit time for each pulse being unknown;

means for generating an additional set of hypothetical matches for each hypothetical transmit time, pulse and transmission path;

means for determining a locus of possible communications device locations using the hypothetical matches for each pulse and each hypothetical transmit time; and

means for determining an estimated location of the communications device as an intersection of possible communications device location loci for the set of hypothetical matches for each pulse and for each hypothetical transmit time.

22. The device of claim 18, wherein the communications device comprises the device to determine the location of the communications device.

23. A computer program product to determine a location of a communications device, the computer program product comprising:

a computer usable storage medium having computer usable program code embodied therein, the computer usable program code comprising;

computer usable program code configured to measure a time of arrival for each pulse received at a receiver;

computer usable program code configured to generate a plurality of transmission path-time matching hypotheses wherein the computer usable program code configured to generate the plurality of transmission path-time matching hypotheses comprises;

computer usable program code configured to determine possible transmission paths from the transmitter to the receiver including all combinations for any bounces or scattering from any scattering centers;

computer usable program code configured to determine substantially all permutations of transmission paths grouped into sets of different transmission paths based on a number of pulses received by the receiver;

computer usable program code configured to associate each transmission path in each set of different transmission paths with a unique pulse of the pulses received for each permutation; and

computer usable program code configured to create a hypothetical match between the unique pulse and the associated transmission path for each permutation, the unique pulse being able to have traveled over the associated transmission path, wherein each of the plurality of transmission path-time matching hypotheses includes a set of different hypothetical matches corresponding to each set of different transmission paths;

computer useable program code configured to determine an intersection error for each transmission path-time matching hypothesis, wherein each hypothetical match defines a locus of possible communications device locations and an intersection of loci of the set of hypothetical matches for each transmission path-time matching hypothesis provides an estimate of the location of the communications device for that transmission path-time matching hypothesis, the intersection error for each transmission path-time matching hypothesis providing an indication of the intersection of loci for each transmission path-time matching hypothesis being substantially at a single point to estimate the location of the communications device; and

computer usable program code configured to estimate the location of the communications device as the intersection of loci for the transmission path-time matching hypothesis with a lowest intersection error.

24. The computer program product of claim 23, further comprising computer usable program code configured to determine the locus of possible communications device locations for each pulse using the hypothetical matches.

25. The computer program product of claim 24, further comprising computer usable program code configured to determining the estimated location of the communications device as the intersection of possible communications device location loci for each set of hypothetical matches for each pulse.

26. The computer program product of claim 25, further comprising:

computer usable program code configured to define a hypothetical transmit time for each pulse in response to the transmit time for each pulse being unknown;

computer usable program code configured to generate an additional set of hypothetical matches for each hypothetical transmit time and path;

computer usable program code configured to determine a locus of possible communications device locations using each set of hypothetical matches for each pulse and each hypothetical transmit time; and

computer usable program code configured to determine an estimated location of the communications device as an intersection of possible communications device location loci for each set of hypothetical matches for each pulse and for each hypothetical transmit time.

27. A vehicle, comprising:

a device to determine a location of the vehicle, wherein the device includes;

a processor;

a location determination module including a hypothetical match evaluation element operable on the processor to evaluate a match between each received pulse and a possible transmission path of the pulse to determine a location of the vehicle, wherein the location determination module comprises;

means for measuring a time of arrival for each pulse received at a receiver;

means for generating a plurality of transmission path-time matching hypotheses, wherein the means for generating the plurality of transmission path-time matching hypotheses comprises;

means for determining possible transmission paths from the transmitter to the receiver including all combinations for any bounces or scattering from any scattering centers;

means for determining substantially all permutations of transmission paths grouped into sets of different transmission paths based on a number of pulses received by the receiver;

means for associating each transmission path in each set of different transmission paths with a unique pulse of the pulses received for each permutation; and

means for creating a hypothetical match between the unique pulse and the associated transmission path for each permutation the unique pulse being able to have traveled over the associated transmission path, wherein each of the plurality of transmission path-time matching hypotheses includes a set of different hypothetical matches corresponding to each set of different transmission paths;

a module for determining an intersection error for each transmission path-time matching hypotheses, wherein each hypothetical match defines a locus of possible communications device locations and an intersection of loci of the set of hypothetical matches for each transmission path-time matching hypothesis provides an estimate of the location of the communications device for that transmission path-time matching hypothesis, the intersection error for each transmission path-time matching hypothesis providing an indication that the intersection of loci for each transmission path-time matching hypothesis being substantially at a single point to estimate the location of the communications device; and

means for estimating the location of the communications device as the intersection of loci for the transmission path-time matching hypothesis with a lowest intersection error.

28. The vehicle of claim 27, wherein the means for estimating the location of the communications device comprises means for determining a locus of possible communications device locations using the hypothetical matches for each pulse.