Positioning systems for wireless networks

• US 9,891,307 B2
• Filed: 03/07/2016
• Issued: 02/13/2018
• Est. Priority Date: 03/21/2012
• Status: Active Grant

• Current Assignee: Digimarc Corporation
• Original Assignee: Digimarc Corporation
• Inventors: Bradley, Brett A.
• Primary Examiner(s): Agosta, Steve D
• Application Number:
  US15/063,158
• Publication Number:
  US 20160291125A1
• Time in Patent Office: 708 Days
• Field of Search: 455 412, 455 413, 4554561-457
• CPC Class Codes: G01S 5/0081 Transmission between base stations
• CPC Class Codes: G01S 5/02216 Timing or synchronisation of the receivers
• CPC Class Codes: G01S 5/0273 using multipath or indirect path propagation signals in position determination
• CPC Class Codes: G01S 5/0289 of multiple transceivers, e.g. in ad hoc networks
• CPC Class Codes: G01S 5/06 Position of source determined by co-ordinating a plurality of position lines defined by path-difference measurements G01S5/12 takes precedence
• CPC Class Codes: G01S 5/10 Position of receiver fixed by co-ordinating a plurality of position lines defined by path-difference measurements , e.g. omega or decca systemsG01S5/12 takes precedence ; beacons and receivers cooperating therewith G01S1/306, G01S1/308
• CPC Class Codes: G01S 5/145 Using a supplementary range measurement, e.g. based on pseudo-range measurements
• CPC Class Codes: H04W 24/00 Supervisory, monitoring or testing arrangements
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management
• CPC Class Codes: H04W 84/12 WLAN [Wireless Local Area Networks]

Abstract

The invention provides a method of computing positioning of a mobile device in a wireless network. This positioning method exchanges packets between pairs of wi-fi nodes. The packets include count stamps of packet transmit and receipt. Differential ranges between a mobile device and plural pairs of wi-fi nodes are used to locate the mobile device.

Claims

1. A method of computing positioning of a wi-fi device in a wi-fi network, the method comprising:

exchanging wi-fi packets among plural pairs of wi-fi nodes by transmission of the wi-fi packets through RF radios in the wi-fi nodes, including assigning local clock values, from local clocks in the wi-fi nodes, to packets upon sending and receiving the packets from each of the wi-fi nodes in the pair, and communicating the local clock values in wi-fi packets exchanged between the pairs of wi-fi nodes;

capturing at least a receipt count stamp from a local clock of a wi-fi node in wi-fi packet communication between a mobile device and wi-fi nodes in the plural pairs;

determining from the local clock values and the receipt count stamps, differential ranges between the mobile device and each of plural pairs of wi-fi nodes;

estimating a path delay for a packet communication with a wi-fi node from the differential ranges and known distances between wi-fi nodes, the path delay comprising a delay in time of flight due to multipath;

determining range estimates between the mobile device and wi-fi nodes from the differential ranges and the path delay;

determining location of the mobile device by finding a candidate location that minimizes differences between the range estimates and the candidate location; and

determining pseudo ranges from the differential ranges, and searching for a candidate location where the pseudo-ranges have minimum error;

wherein the path delay is estimated for the wi-fi nodes and removed from the differential ranges; and

wherein the path delay is estimated by evaluating differential range estimates of wi-fi nodes to the mobile device computed from packets transmitted between mobile device and the pairs of wi-fi nodes, and assigning path delay to the pairs of wi-fi nodes.

2. The method of claim 1 wherein the plural pairs of wi-fi nodes comprise infrastructure nodes and at least some of the exchanging of wi-fi packets among the infrastructure nodes is performed with regularity in a pair-wise manner according to a full duplex mode.

3. The method of claim 2 wherein full duplex exchanges between the plural pairs of wi-fi nodes are used to determine path delays by determining a round trip time of a full duplex exchange between first and second wi-fi nodes in a first pair and deriving a path delay associated with the first pair from the round trip time and distance between the first and second wi-fi nodes.

4. The method of claim 1 wherein the wherein the path delay is estimated for the wi-fi nodes and compensated for in the determining of the location of the mobile device.

5. The method of claim 1 including evaluating clock value differences between pairs of wi-fi nodes over time to determine the clock differences of local clocks within the wi-fi nodes.

6. The method of claim 1 wherein the mobile device operates in a transmit only mode, sending a packet to the plural pairs of wi-fi nodes, which count stamp the packet upon receipt, and including deriving differential ranges of the wi-fi nodes to the mobile device from count stamps of the packet at the wi-fi nodes.

7. The method of claim 1 wherein the path delay is used to compensate for multipath error in computing the pseudo-ranges.

8. The method of claim 1 wherein the path delay is estimated by determining areas with similar estimated multipath error and assigning multipath errors corresponding to the areas to the wi-fi nodes within the areas.

9. The method of claim 1 wherein estimates of the path delay are refined by averaging estimates of the path delay from un-correlated conditions, and using the refined estimates to compensate for error due to the path delay in the determining of the mobile device location.

10. A non-transitory computer readable medium, on which is stored instructions, which when executed by one or more computers, perform a method of computing positioning of a wi-fi device in a wi-fi network, the method comprising:

exchanging wi-fi packets among plural pairs of wi-fi nodes by transmission of the wi-fi packets through RF radios in the wi-fi nodes, including assigning local clock values, from local clocks in the wi-fi nodes, to packets upon sending and receiving the packets from each of the wi-fi nodes in the pair, and communicating the local clock values in wi-fi packets exchanged between the pairs of wi-fi nodes;

capturing at least a receipt count stamp from a local clock of a wi-fi node in wi-fi packet communication between a mobile device and wi-fi nodes in the plural pairs;

determining from the local clock values and the receipt count stamps, differential ranges between a mobile device and each of plural pairs of wi-fi nodes;

estimating a path delay for a packet communication with a wi-fi node from the differential ranges and known distances between wi-fi nodes, the path delay comprising a delay in time of flight due to multipath;

determining range estimates between the mobile device and wi-fi nodes from the differential ranges and the path delay; and

determining location of the mobile device by finding a candidate location that minimizes differences between the range estimates and the candidate location;

the method including;

determining pseudo ranges from the differential ranges, and searching for a candidate location where the pseudo-ranges have minimum error;

wherein the plural pairs of wi-fi nodes comprise infrastructure nodes and at least some of the exchanging of wi-fi packets among the infrastructure nodes is performed with regularity in a pair-wise manner according to a full duplex mode;

wherein full duplex exchanges between the plural pairs of wi-fi nodes are used to determine path delays by determining a round trip time of a full duplex exchange between first and second wi-fi nodes in a first pair and deriving a path delay associated with the first pair from the round trip time and distance between the first and second wi-fi nodes; and

wherein the path delay is used to compensate for multipath error in computing the pseudo ranges.

11. The computer readable medium of claim 10, wherein the method of the instructions on the medium includes determining locations of plural mobile devices in the network, and the associated packets are sorted into data structures on a computer readable medium based on mobile device ID and message ID and the data structures are processed by instructions executing on one or more computers to provide location for each of the mobile devices.

12. The computer readable medium of claim 10 on which is stored instructions, which when executed by one or more computers, perform a method of computing positioning of a wi-fi device in a wi-fi network, the method comprising:

estimating the path delay due to multipath of packet communication with a first wi-fi node based on differential ranges obtained for pairs of nodes including the first wi-fi node, and removing the path delay from pseudo ranges derived from differential ranges to produce the range estimates.

13. The computer readable medium of claim 10, wherein the mobile device operates in a transmit only mode, sending a packet to the plural pairs of wi-fi nodes, which count stamp the packet upon receipt, and including deriving differential ranges of the wi-fi nodes to the mobile device from count stamps of the packet at the wi-fi nodes.

14. The computer readable medium of claim 10, wherein the path delay is estimated by evaluating differential range estimates of wi-fi nodes to the mobile device computed from packets transmitted between mobile device and the pairs of wi-fi nodes, and assigning multipath error estimates to the pairs of wi-fi nodes.

15. A method of computing positioning of a wi-fi device in a wi-fi network, the method comprising:

exchanging wi-fi packets among plural pairs of wi-fi nodes by transmission of the wi-fi packets through RF radios in the wi-fi nodes, including assigning local clock values, from local clocks in the wi-fi nodes, to packets upon sending and receiving the packets from each of the wi-fi nodes in the pair, and communicating the local clock values in wi-fi packets exchanged between the pairs of wi-fi nodes;

capturing at least a receipt count stamp from a local clock of a wi-fi node in wi-fi packet communication between a mobile device and wi-fi nodes in the plural pairs;

determining from the local clock values and the receipt count stamps, differential ranges between the mobile device and each of plural pairs of wi-fi nodes;

estimating a path delay for a packet communication with a wi-fi node from the differential ranges and known distances between wi-fi nodes, the path delay comprising a delay in time of flight due to multipath;

determining range estimates between the mobile device and wi-fi nodes from the differential ranges and the path delay; and

determining location of the mobile device by finding a candidate location that minimizes differences between the range estimates and the candidate location;

the method including;

determining pseudo ranges from the differential ranges, and searching for a candidate location where the pseudo-ranges have minimum error;

wherein the plural pairs of wi-fi nodes comprise infrastructure nodes and at least some of the exchanging of wi-fi packets among the infrastructure nodes is performed with regularity in a pair-wise manner according to a full duplex mode;

wherein full duplex exchanges between the plural pairs of wi-fi nodes are used to determine path delays by determining a round trip time of a full duplex exchange between first and second wi-fi nodes in a first pair and deriving a path delay associated with the first pair from the round trip time and distance between the first and second wi-fi nodes; and

wherein the path delay is used to compensate for multipath error in computing the pseudo ranges.

16. The method of claim 15 wherein the wherein the path delay is estimated for the wi-fi nodes and compensated for in the determining of the location of the mobile device.

17. The method of claim 15 wherein the path delay is estimated by determining areas with similar estimated multipath error and assigning multipath errors corresponding to the areas to the wi-fi nodes within the areas.

18. The method of claim 15 wherein estimates of the path delay are refined by averaging estimates of the path delay from un-correlated conditions, and using the refined estimates to compensate for error due to the path delay in the determining of the mobile device location.

19. The method of claim 15 wherein the path delay is estimated by evaluating differential range estimates of wi-fi nodes to the mobile device computed from packets transmitted between mobile device and the pairs of wi-fi nodes, and assigning multipath error estimates to the pairs of wi-fi nodes.

20. The method of claim 15 comprising:

estimating the path delay due to multipath of packet communication with a first wi-fi node based on differential ranges obtained for pairs of nodes including the first wi-fi node, and removing the path delay from pseudo ranges derived from differential ranges to produce the range estimates.