Mobile device positioning in dynamic groupings of communication devices

• US 9,363,783 B2
• Filed: 05/29/2015
• Issued: 06/07/2016
• Est. Priority Date: 07/09/2010
• Status: Active Grant

• Current Assignee: Digimarc Corporation
• Original Assignee: Digimarc Corporation
• Inventors: Rhoads, Geoffrey B.
• Primary Examiner(s): Khan, Suhail
• Application Number:
  US14/726,226
• Publication Number:
  US 20150341893A1
• Time in Patent Office: 375 Days
• Field of Search: None
• US Class Current: 1/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 wi-fi based mobile positioning system determines mobile device positioning by count stamped packets communicated between the mobile device and access points according to a standard wifi protocol. Ad-hoc groups of wifi network nodes are formed and then broken with a mobile device as that mobile devices moves relative to fixed nodes, such as access points. Within an ad-hoc group, the nodes count stamp packets by latching a local counter within each node. Count-stamps are collected and used to generate ranges for a mobile device relative to nodes in an ad hoc group. A positioning services determines the position of the mobile device from the ranges.

Claims

1. A wifi based mobile device positioning system, the system comprising:

an access point device for receiving 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 a transmission of the receive message from a corresponding other communication device, wherein the access point is further operable to generate a receive count stamp for each receive message corresponding to a local counter value at receipt of a receive message from the other communication devices and for messages received from a mobile communication device;

a node in communication with the access point, the node including a processor programmed to dynamically associate and disassociate the mobile communication device with a plurality of sub-groups of the plurality of other communication devices, based at least in part on receiving receive messages from a predetermined number of other communication devices for each sub-group; and

a programmed processor executing to generate range estimates between the mobile communication device and 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 count stamps previously communicated between the mobile device and other communication devices in the plurality of sub-groups.

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

3. The system of claim 1 wherein the mobile communication device is operable to transmit messages, each transmit message including a transmit count stamp corresponding to the local counter value at the transmission of the transmit message.

4. The system of claim 1 comprising:

a programmed processor executing to propagate relationships among local clocks in the communication devices in the plurality of the sub-groups, including;

for each of the sub-groups, the programmed processor executing to gather 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, the programmed processor executing to determine 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, the programmed processor executing to determine differential clock solutions for corresponding clocks in nodes of the second sub-group; and

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

5. The system of claim 4 wherein a programmed processor executes to directly reference a local time of at least one of the sub-groups to a standard time reference, and executes to use the standard time reference to compute timing solutions for other nodes by relating differential solutions for the other nodes to the standard time reference.

6. The system of claim 4 wherein a programmed processor executes to use existence and differential time solutions of shared nodes belonging to both of the first and second sub-groups to combine the two separate groups into a singular larger group of differential timing solutions.

7. The system of claim 4 further including a programmed processor executing to determine a timing solution for a node as a weighted combination of differential timing solutions for nodes connected through message hops to a reference node.

8. The system of claim 7 wherein the reference node is directly referenced to a standard time reference.

9. The system of claim 4 wherein each of the sub-groups includes a managing node corresponding to the sub-group, the managing node having a programmed processor executed to maintain a list of active nodes participating in communicating count stamped messages in the corresponding sub-group.

10. The system of claim 4 wherein each of the sub-groups include nodes with corresponding ping drivers, the ping drivers executed on programmed processors to count stamp messages upon transmission or receipt of the messages with a counter value from a local, independent counter within a corresponding node.

11. The system of claim 4 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.

12. The system of claim 4 comprising a programmed processor executed to formulate 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.

13. A wifi based mobile device positioning system, the system comprising:

an access point device for receiving receive messages transmitted from a plurality of other communication devices, each receive message including a transmit identification datum which identifies a remote device creating the transmission of the receive message, wherein the access point is further operable to generate a receive count stamp for each receive message corresponding to a local counter value at receipt of a receive message from the other communication devices, at least one of which is a mobile communication device;

a node in communication with the access point, the node including a processor programmed to dynamically associate and disassociate the mobile communication device with a plurality of sub-groups of the plurality of other communication devices, based at least in part on receiving receive messages from a predetermined number of other communication devices for each sub-group; and

a programmed processor executing to generate range estimates between the mobile communication device and other communication devices in the sub-group currently associated with the mobile communication device, the range estimates based on a combination of the transmit identification datum 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 count stamps previously communicated between the mobile device and other communication devices in the plurality of sub-groups.

14. The system of claim 13, wherein each sub-group includes at least one non-mobile communication device.

15. The system of claim 13 wherein the mobile communication device is operable to transmit messages, each transmit message including a transmit count stamp corresponding to the local counter value at the transmission of the transmit message.

16. The system of claim 13 comprising:

a programmed processor executing to propagate relationships among local clocks in the communication devices in the plurality of the sub-groups, including;

for each of the sub-groups, the programmed processor executing to gather 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, the programmed processor executing to determine 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, the programmed processor executing to determine differential clock solutions for corresponding clocks in nodes of the second sub-group; and

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

17. The system of claim 16 wherein a programmed processor executes to directly reference a local time of at least one of the sub-groups to a standard time reference, and executes to use the standard time reference to compute timing solutions for other nodes by relating differential solutions for the other nodes to the standard time reference.

18. The system of claim 16 wherein a programmed processor executes to use existence and differential time solutions of shared nodes belonging to both of the first and second sub-groups to combine the two separate groups into a singular larger group of differential timing solutions.

19. The system of claim 16 further including a programmed processor executing to determine a timing solution for a node as a weighted combination of differential timing solutions for nodes connected through message hops to a reference node.

20. The system of claim 19 wherein the reference node is directly referenced to a standard time reference.

21. The system of claim 16 wherein each of the sub-groups includes a managing node corresponding to the sub-group, the managing node having a programmed processor executed to maintain a list of active nodes participating in communicating count stamped messages in the corresponding sub-group.

22. The system of claim 16 wherein each of the sub-groups include nodes with corresponding ping drivers, the ping drivers executed on programmed processors to count stamp messages upon transmission or receipt of the messages with a counter value from a local, independent counter within a corresponding node.

23. The system of claim 16 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.

24. The system of claim 16 comprising a programmed processor executed to formulate 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.