Wireless Localisation System

• US 20110188389A1
• Filed: 07/03/2009
• Published: 08/04/2011
• Est. Priority Date: 07/04/2008
• Status: Abandoned Application

• Current Assignee: Commonwealth Scientific & Industrial Research Organisation (Commonwealth Of Australia As Represented By Department Of Industry, Innovation, Climate Change, Science, Research And Tertiary Education)
• Original Assignee: Commonwealth Scientific & Industrial Research Organisation (Commonwealth Of Australia As Represented By Department Of Industry, Innovation, Climate Change, Science, Research And Tertiary Education)
• Inventors: Humphrey, David Eric, Hedley, Mark
• Application Number:
  US13/002,640
• Publication Number:
  US 20110188389A1
• 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 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/017 Detecting state or type of motion
• CPC Class Codes: G01S 5/0218 Multipath in signal reception
• CPC Class Codes: G01S 5/0226 Transmitters
• 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

Disclosed is method of computing a round trip delay between a pair of nodes, the method comprising transmitting at least one beacon at a known transmit time from each of the nodes; measuring the times-of-arrival of the beacons at other of the nodes; and estimating a round trip delay between the nodes from the measured times-of-arrival and the transmit times; and correcting the round trip delay for either or both of a frequency offset between the nodes and relative motion between the nodes.

Claims

1. A method of computing a round trip delay between a pair of nodes, the method comprising:

transmitting at least one beacon at a known transmit time from each of said nodes;

measuring the times-of-arrival of said beacons at another of said nodes;

estimating a round trip delay between said nodes from said measured times-of-arrival and said transmit times; and

correcting said round trip delay for either or both of a frequency offset between the nodes and relative motion between the nodes.

2. The method according to claim 1, wherein said correcting comprises:

estimating a frequency difference from times-of-arrival of at least two beacons transmitted between said nodes;

using an estimated or predetermined time delay between transmissions of a beacon from each of said nodes; and

computing a correction term to be removed from the estimated round trip delay using the estimated frequency difference and the time delay.

3. The method according to claim 1, wherein a pseudo-range is determined from the corrected round trip delay and a propagation delay of any one of said nodes.

4. The method according to claim 1, wherein a range is determined from the corrected round trip delay and a propagation delay of both said nodes.

5. The method according to claim 1, wherein terms due to said frequency offset and to said relative motion are computed from said correction.

6. The method according to claim 5, further comprising estimating the velocity of one of said nodes from said relative motion term.

7. The method according to claim 6, wherein said pair of nodes comprises one mobile node and a stationary anchor node at a known location.

8. A method according to claim 1, further comprising:

computing the round trip delays between further pairs of nodes; and

computing a propagation delay at each said node using said computed round trip delays.

14. The method according to claim 9, wherein said ranges are computed using the method in claim 4.

9. A method of estimating the location of a mobile object using a plurality of ranges between a node associated with said object and respective anchor nodes, the method comprising:

estimating, for a current said range, the location of said object and an error in said location estimate from said range excluding said current range;

discarding the range whose exclusion gave the lowest error estimate, if said lowest error estimate is less than a threshold;

repeating said estimating and said discarding until said lowest error estimate is not less than said threshold or the number of undiscarded ranges reaches a minimum number; and

estimating the location of said object from the undiscarded ranges.

10. The method according to claim 9, wherein said threshold is a predetermined constant times the error in the location estimate from all undiscarded ranges.

11. The method according to claim 9, wherein said estimating comprises minimising a weighted sum over said anchor nodes of the squared difference between each range and the distance between a candidate location and the location of a corresponding anchor node.

12. The method according to claim 9, wherein said error in location estimate comprises an estimate of the range error and a term relating range error to location error.

13. The method according to claim 9, wherein said estimating further comprises estimating an offset common to all said ranges.

15. The method according to claim 13, wherein said ranges are pseudo-ranges determined from the corrected round trip delay and a propagation delay of any one of the nodes, with the propagation delay of the mobile node being unknown.

24. The method according to claim 22, wherein said estimating comprises:

subtracting respective propagation delays from each of said plurality of measured times-of-arrival to give respective pseudo-ranges; and

using said pseudo-ranges and the method in claim 13 to estimate said location.

16. A method of estimating the location of a mobile object using a plurality of ranges between a node associated with said object and respective anchor nodes, the method comprising:

projecting a starting point onto a sequence of constraint sets in turn, each said constraint set being a circle centred on one said anchor node with radius equal to the corresponding range, to obtain an end point;

increasing, if said end point is not less than said corresponding range from each said anchor node, at least one said range, and

repeating said projecting and said increasing until said location is less than said corresponding range from each said anchor node,

wherein said end point is said estimated location of said mobile object.

17. The method according to claim 16, further comprising performing said projecting, increasing, and repeating for at least one other starting point, wherein said estimated location is an average of said end points.

18. The method according to claim 17, further comprising:

determining whether said end points are widely dispersed, and if so,

decreasing at least one said range, and

repeating said performing.

19. The method according to claim 16, wherein ranges are computed from the corrected round trip delay and a propagation delay of both said nodes.

20. A method of time synchronising a plurality of anchor nodes, the method comprising:

measuring a plurality of trip delays of beacons transmitted between said anchor nodes;

correcting said trip delays for propagation delays at said anchor nodes and frequency offsets between local clocks at respective said anchor nodes; and

determining a time offset of each said local clock from said corrected trip delays.

21. The method according to claim 20, where said ranges are determined from the corrected round trip delay and a propagation delay of both said nodes.

22. A method of estimating the location of a mobile object using a plurality of anchor nodes, the method comprising:

synchronising said plurality of anchor nodes;

measuring a plurality of times-of-arrival of beacons transmitted from said object to respective said anchor nodes; and

estimating the location of said object relative to said anchor nodes using said measured times-of-arrival, corrected for a propagation delay at each said anchor node.

23. The method according to claim 22, wherein said synchronising comprises

measuring a plurality of trip delays of beacons transmitted between said anchor nodes;

correcting said trip delays for propagation delays at said anchor nodes and frequency offsets between local clocks at respective said anchor nodes; and

determining a time offset of each said local clock from said corrected trip delays.

25. A system for estimating the location of one or more objects, the system comprising:

a plurality of anchor nodes;

one or more mobile nodes coincident with respective said objects;

beacons transmitted by some or all of said nodes according to a predetermined or dynamically determined schedule; and

data capability to send measured times-of-arrival of said beacons, and transmit times of said beacons, to a location server adapted to compute the location of said objects.

26. The system of claim 25 wherein the location server is further adapted to pre-filter-range or pseudo-range values prior to said computation of location.

27. The system of claim 25 in which:

round trip measurements are performed between anchor nodes and mobile nodes;

the propagation delay of the anchor nodes, if not known, comprises computing the round trip delays between further pairs of nodes, and computing a propagation delay at each said node using said computed round trip delays; and

said computation of location comprises one of

estimating, for a current said range, the location of said object and an error in said location estimate from said range excluding said current range;

discarding the range whose exclusion gave the lowest error estimate, if said lowest error estimate is less than a threshold;

repeating said estimating and said discarding until said lowest error estimate is not less than said threshold or the number of undiscarded ranges reaches a minimum number; and

estimating the location of said object from the undiscarded ranges, or

projecting a starting point onto a sequence of constraint sets in turn, each said constraint set being a circle centred on one said anchor node with radius equal to the corresponding range, to obtain an end point,

increasing, if said end point is not less than said corresponding range from each said anchor node, at least one said range, and

repeating said projecting and said increasing until said location is less than said corresponding range from each said anchor node,

wherein said end point is said estimated location of said mobile object, for each mobile node for which the propagation delay is known, otherwise said computation of location uses a method wherein said ranges are pseudo-ranges computed determined from the corrected round trip delay and a propagation delay of any one of the nodes, with the propagation delay of the mobile node being unknown.

28. The system of claim 25 in which:

said plurality of anchor nodes is adapted to measure the times-of-arrival of beacon signals from the mobile nodes; and

said computation of location comprises

synchronising said plurality of anchor nodes;

measuring a plurality of times-of-arrival of beacons transmitted from said object to respective said anchor nodes; and

estimating the location of said object relative to said anchor nodes using said measured times-of-arrival, corrected for a propagation delay at each said anchor node.

29. The system of claim 25 in which said location server is adapted to use more than one method for computation of location, and the method employed for each mobile node depends upon one or more attributes of the mobile node.

30. (canceled)

31. A system for estimating the location of an object, the system comprising:

a plurality of anchor nodes adapted to communicate wirelessly with each other by either transmitting or receiving beacons;

a mobile node coincident with said object, the mobile node being adapted to communicate wirelessly with said anchor nodes by either receiving or transmitting said beacons; and

a localisation server adapted to;

receive measurements of time-of-arrival of said beacons at said nodes,

select one of a plurality of localisation algorithms dependent on attributes of said anchor nodes and said mobile node, and

estimate the location of said object using said measured times-of-arrival using said selected localisation algorithm.