Mobile device positioning in dynamic groupings of communication devices

• US 8,463,290 B2
• Filed: 07/11/2011
• Issued: 06/11/2013
• Est. Priority Date: 07/09/2010
• Status: Active Grant

• Current Assignee: Digimarc Corporation
• Original Assignee: Digimarc Corporation
• Inventors: Rhoads, Goeffrey B.
• Primary Examiner(s): WANG-HURST, KATHY W
• Application Number:
  US13/179,807
• Publication Number:
  US 20120309414A1
• Time in Patent Office: 701 Days
• Field of Search: 455/456.1, 455/456.2, 455/456.3, 455/421, 455/422.1
• US Class Current: 455/456.1
• CPC Class Codes: G01S 5/0289 of multiple transceivers, e.g. in ad hoc networks
• CPC Class Codes: G08G 1/08 according to detected number or speed of vehicles
• CPC Class Codes: H04W 4/023 using mutual or relative location information between multiple location based services [LBS] targets or of distance thresholds
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 4/40 for vehicles, e.g. vehicle-to-pedestrians [V2P]
• 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]
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A mobile device positioning system determines ranges between a plurality of communication devices, including at least one mobile communication device. A method includes receiving receive messages transmitted from a plurality of other communication devices. Each receive message includes a transmit count stamp corresponding to a remote counter value. A first communication device generates a receive count stamp for each receive message. The method includes dynamically associating and disassociating the mobile communication device with a plurality of sub-groups of the plurality of other communication devices. The associating and disassociating are based at least in part on receiving receive messages from a predetermined number of other communication devices for each sub-group. For each sub-group currently associated with the mobile communication device, the method includes generating range estimates between the mobile communication device and the other communication devices in the particular sub-group. The range estimates are based on a combination of the transmit count stamps and the receive count stamps.

Claims

1. A method of determining ranges between a plurality of communication devices, the plurality of communication devices including at least one mobile communication device, the method comprising:

receiving, at a first communication device, receive messages transmitted from a plurality of other communication devices, each receive message including a transmit count stamp corresponding to a remote counter value at the transmission of the receive message from the corresponding other communication device, wherein the first communication device generates a receive count stamp for each receive message corresponding to a local counter value at receipt of the receive message from the other communication devices and for messages received from the mobile communication device;

as the mobile communication device travels along a path relative to the plurality of other communication devices, dynamically associating and disassociating the mobile communication device with a plurality of sub-groups of the plurality of other communication devices, wherein the associating and disassociating are based at least in part on receiving receive messages from a predetermined number of other communication devices for each sub-group; and

for each sub-group currently associated with the mobile communication device, generating range estimates between the mobile communication device and the other communication devices in the sub-group currently associated with the mobile communication device, the range estimates based on a combination of the transmit count stamps and the receive count stamps; and

wherein at least one of the range estimates is a mobile device range estimate between the mobile device and a second communication device that the mobile communication device is newly associated with in one of the sub-groups, and the mobile device range estimate is computed as a function of a local clock time of the second communication device, and a delta time relating the local clock time to a time for a group of communication devices computed based on count stamps previously communicated between the second communication device and other communication devices in the plurality of sub-groups.

2. The method of claim 1, wherein each sub-group includes at least one non-mobile communication device.

3. The method of claim 2, wherein the at least one non-mobile communication device is located in a traffic light at a street intersection.

4. The method of claim 2, wherein the range estimates are used to control the traffic light.

5. The method of claim 1, further comprising:

transmitting, from the mobile communication device, transmit messages, each transmit message including a transmit count stamp corresponding to the local counter value at the transmission of the transmit message.

6. The method of claim 1 comprising:

propagating relationships among local clocks in the communication devices in the plurality of the sub-groups, including;

for each of the sub-groups, gathering count stamps for messages transmitted between nodes in the sub-group over a period of time;

from the count stamps gathered for a first sub-group, determining differential clock solutions for corresponding clocks in nodes of the first sub-group, where the differential solutions provide a relative timing solution between nodes of the first sub-group;

from the count stamps gathered for a second sub-group, determining differential clock solutions for corresponding clocks in nodes of the second sub-group; and

diffusing a differential timing solution between nodes belonging only to the first sub-group and nodes belonging only to the second, through clock solutions for nodes shared between the first and second sub-groups.

7. The method of claim 6 wherein a local time of at least one of the sub-groups is directly referenced to a standard time reference, and the standard time reference is used to compute timing solutions for other nodes by relating differential solutions for the other nodes to the standard time reference.

8. The method of claim 6 wherein existence and differential time solutions of shared nodes belonging to both of the first and second sub-groups are used to combine the two separate groups into a singular larger group of differential timing solutions.

9. The method of claim 6 further including determining a timing solution for a node as a weighted combination of differential timing solutions for nodes connected through message hops to a reference node.

10. The method of claim 9 wherein the reference node is directly referenced to a standard time reference.

11. The method of claim 6 wherein each of the sub-groups includes a managing node corresponding to the sub-group, the managing node maintaining a list of active nodes participating in communicating count stamped messages in the corresponding sub-group.

12. The method of claim 6 wherein each of the sub-groups include nodes with corresponding ping drivers, the ping drivers count stamping messages upon transmission or receipt of the messages with a counter value from a local, independent counter within a corresponding node.

13. The method of claim 6 wherein at least one of the nodes in the sub-groups is the mobile communication device, which temporarily becomes a member of a sub-group as the mobile communication device moves relative to communication devices in the sub-groups.

14. The method of claim 6 wherein determining differential clock solutions comprises formulating a system of equations relating local clock counts of the nodes and associated error terms based on messages communicated between pairs of nodes in a sub-group over a time interval.

15. A method of positioning of a mobile device, the method comprising:

as the mobile device moves relative to first and second sub-groups of nodes and switches channels used to communicate with the nodes, tracking associations between the mobile device and nodes in the first and second sub-groups;

for each of the sub-groups, gathering count stamps for messages transmitted between nodes in the sub-group over a period of time;

from the count stamps gathered for the first sub-group, determining differential clock solutions for corresponding clocks in nodes of the first sub-group;

from the count stamps gathered for the second sub-group, determining differential clock solutions for corresponding clocks in nodes of the second sub-group;

wherein a differential clock solution for a local clock in a first node provides a relative timing between the local clock in the first node and timing computed for a group of nodes based on count stamps communicated between nodes in the group; and

based on local clock times and differential clock solutions for nodes in the first and second sub-groups, determining range estimates between the mobile device and nodes in the first and second sub-groups from which the position of the mobile device is determined.

16. The method of claim 15 wherein a local time of at least one of the sub-groups is directly referenced to a standard time reference, and the standard time reference is used to compute timing solutions for other nodes by relating differential solutions for the other nodes to the standard time reference.

17. The method of claim 15 wherein differential time solutions of shared nodes belonging to both of the first and second sub-groups are used to combine the two separate groups into a singular larger group of differential timing solutions.

18. The method of claim 15 further including determining a timing solution for a node as a weighted combination of differential timing solutions for nodes connected through message hops to a reference node.

19. The method of claim 15 wherein each of the sub-groups includes an alpha node corresponding to the sub-group, the alpha node maintaining a list of active nodes participating in communicating count stamped messages in a corresponding sub-group.

20. The method of claim 15 wherein determining differential clock solutions comprises formulating a system of equations relating local clock counts of the nodes and associated error terms based on messages communicated between pairs of nodes in sub-group over a time interval.