Wireless Localisation System

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.

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.   
     
     
         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. 
     
     
         14 . The method according to  claim 9 , wherein said ranges are computed using the method in  claim 4 . 
     
     
         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. 
     
     
         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.   
     
     
         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.   
     
     
         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.