Wireless local area network-based position locating systems and methods

• US 9,014,162 B2
• Filed: 05/28/2013
• Issued: 04/21/2015
• Est. Priority Date: 12/07/2006
• Status: Active Grant

• Current Assignee: Digimarc Corporation
• Original Assignee: Digimarc Corporation
• Inventors: Brundage, Trent J., Rhoads, Geoffrey B.
• Primary Examiner(s): Lai, Andrew
• Assistant Examiner(s): SHIH, ALBERT K
• Application Number:
  US13/903,709
• Publication Number:
  US 20140036894A1
• Time in Patent Office: 693 Days
• Field of Search: 370/312, 370/328, 370/338
• US Class Current: 370/338
• CPC Class Codes: G01S 5/0289 of multiple transceivers, e.g. in ad hoc networks
• 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 64/003 locating network equipment

Abstract

The location of one or more mobile nodes in a wireless local area network (WLAN) is determined. Nodes in the WLAN include respective ping drivers to generate ping event values related to transmit count stamps and receive count stamps for wireless messages exchanged between the nodes. Each wireless message is associated with a transmit offset corresponding to an expected transmit time. A sorting module groups the ping event values and produces a difference between the respective receive count stamps and the transmit count stamps for each wireless message. Based on the sorted ping event values, the sorting module generates transmit offset values relating to the transmit offsets. A space-time calibration unit generates, from the sorted differences and the transmit offset values, a clock rate solution and a location solution for at least one of the nodes in the WLAN.

Claims

1. A method for determining location and timing information of one or more nodes in a wireless local area network (WLAN), the method comprising:

generating ping event values corresponding to ping events related to transmit count stamps and receive count stamps for wireless messages exchanged between nodes in the WLAN;

sorting the ping event values corresponding to multiple ones of the ping events that occur within a first predetermined time period;

for ping event values within the first predetermined time period, producing differences between the respective receive count stamps and the transmit count stamps for each wireless message, and generating transmit offset values; and

generating, from the produced differences and the transmit offset values, a clock rate solution and a location solution for at least one of the nodes in the WLAN.

2. The method of claim 1, wherein each node includes a receive delay corresponding to a difference between a first time at which the node records a receive count stamp corresponding to a particular wireless message and a second time at which the particular wireless message is received at an antenna of the receiving node, wherein generating the clock rate solution and the location solution further comprises:

generating receive delay values, based on the produced differences and the transmit offset values, relating to the receive delays for each of the nodes.

3. The method of claim 2, wherein generating the transmit offset values comprises, for each ping event within the first predetermined time period:

determining a first transmit offset value at a beginning of the first predetermined time period; and

determining a second transmit offset value at an end of the first predetermined time period.

4. The method of claim 3, further comprising:

for each node, generating a model of the transmit offset values based on the corresponding first transmit offset values and the corresponding second transmit offset values in the first predetermined time period;

determining observed differences between the receive count stamps and corresponding transmit count stamps for the ping events that occur during a second predetermined time period after the first predetermined time period;

determining errors between the observed differences and corresponding estimated differences for the ping events that occur during the second predetermined time period, the estimated differences being based on the model for each node;

based on the determined errors, generating an average error for each pair of transmitting nodes and receiving nodes;

for each pair of transmitting nodes and receiving nodes, generating a reference clock offset as a difference between the transmit offset values from the model in the first predetermined time period and an estimate of offset values obtained in the second predetermined time period; and

for each pair of transmitting nodes and receiving nodes with a ping event that occurs during the first predetermined period of time, removing the generated reference clock offset values from the average error.

5. The method of claim 4, wherein generating the location solution comprises:

based on an initial estimate of the at least one node'"'"'s position, determining the location solution using a search algorithm to minimize the average error.

6. The method of claim 1, wherein generating the ping event values comprises:

generating, at a transmitting node, a beacon packet that includes a corresponding transmit count stamp;

upon receiving the beacon packet at a receiving node, latching a register; and

determining a corresponding receive count stamp from the latched register.

7. The method of claim 6, wherein generating and receiving the beacon packet comprises:

operating each node simultaneously in an access point mode and a station mode, wherein each node transmits beacon packets in the access point mode and detects other beacon packets in the station mode.

8. The method of claim 1, wherein generating the ping event values comprises:

generating, at a transmitting node, a user datagram protocol (UDP) packet that include a corresponding transmit count stamp; and

upon receiving the UDP packet at a receiving node, associating the transmit count stamp with a receive count stamp.

9. The method of claim 1, wherein sorting the ping event values comprises:

grouping the ping event values into pingcasts corresponding to each wireless message, each pingcast comprising a transmit count stamp produced by a node that transmitted the wireless message and plurality of receive count stamps produced by each node that received the wireless message; and

grouping the pingcasts into pingsets, each pingset comprising a pingcast corresponding to a node that transmits a wireless message.

10. A system for determining location and timing information in a wireless local area network (WLAN), the system comprising:

a plurality of nodes to communicate wirelessly through the WLAN, each node comprising a respective ping driver to generate ping event values corresponding to ping events related to transmit count stamps and receive count stamps for wireless messages exchanged between the nodes in the WLAN;

a sorting module to;

sort the ping event values corresponding to multiple ones of the ping events that occur within a first predetermined time period;

based on the sorted ping event values, produce differences between the respective receive count stamps and the transmit count stamps for each wireless message; and

based on the sorted ping event values, generate transmit offset values; and

a space-time calibration unit to generate, from the produced differences and the transmit offset values, a clock rate solution and a location solution for at least one of the nodes in the WLAN.

11. The system of claim 10, wherein each node includes a receive delay corresponding to a difference between a first time at which the node records a receive count stamp corresponding to a particular wireless message and a second time at which the particular wireless message is received at an antenna of the receiving node, wherein the space-time calibration unit is configured to generate the clock rate solution and the location solution by generating receive delay values, based on the produced differences and the transmit offset values, relating to the receive delays for each of the nodes.

12. The system of claim 11, wherein, for each ping event within the first predetermined time period, the sorting module is further configured to:

determine a first transmit offset value at a beginning of the first predetermined time period; and

determine a second transmit offset value at an end of the first predetermined time period.

13. The system of claim 12, wherein the space-time calibration unit is further configured to:

for each node, generate a model of the transmit offset values based on the corresponding first transmit offset values and the corresponding second transmit offset values in the first predetermined time period;

determine observed differences between the receive count stamps and corresponding transmit count stamps for the ping events that occur during a second predetermined time period after the first predetermined time period;

determine errors between the observed differences and corresponding estimated differences for the ping events that occur during the second predetermined time period, the estimated differences being based on the model for each node;

based on the determined errors, generate an average error for each pair of transmitting nodes and receiving nodes;

for each pair of transmitting nodes and receiving nodes, generate a reference clock offset as a difference between the transmit offset values from the model in the first predetermined time period and an estimate of offset values obtained in the second predetermined time period; and

for each pair of transmitting nodes and receiving nodes with a ping event that occurs during the first predetermined period of time, remove the generated reference clock offset values from the average error.

14. The system of claim 13, wherein the space-time calibration unit is configured to generate the location solution by:

based on an initial estimate of the at least one node'"'"'s position, determining the location solution using a search algorithm to minimize the average error.

15. The system of claim 10, wherein each ping driver is configured to:

generate, at a transmitting node, a beacon packet that includes a corresponding transmit count stamp;

upon receiving the beacon packet at a receiving node, latch a register; and

determine a corresponding receive count stamp from the latched register.

16. The system of claim 15, wherein each ping driver is further configured to:

operate each node simultaneously in an access point mode and a station mode, wherein each node transmits beacon packets in the access point mode and detects other beacon packets in the station mode.

17. The system of claim 10, wherein each ping driver is further configured to:

generate, at a transmitting node, a user datagram protocol (UDP) packet that include a corresponding transmit count stamp; and

upon receiving the UDP packet at a receiving node, associate the transmit count stamp with a receive count stamp.

18. The system of claim 10, wherein the sorting module is configured to:

group the ping event values into pingcasts corresponding to each wireless message, each pingcast comprising a transmit count stamp produced by a node that transmitted the wireless message and plurality of receive count stamps produced by each node that received the wireless message; and

group the pingcasts into pingsets, each pingset comprising a pingcast corresponding to a node that transmits a wireless message.