Distributed mac protocol facilitating collaborative ranging in communications networks

• US 20040246903A1
• Filed: 06/04/2003
• Published: 12/09/2004
• Est. Priority Date: 06/04/2003
• Status: Active Grant

• Current Assignee: ARRIS Enterprises LLC (CommScope Holding Company, Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Huang, Jian, Huang, Yan, Kyperountas, Spyros, Niu, Feng
• Granted Patent: US 7,269,138 B2
• Time in Patent Office: Days
• US Class Current: 370/247
• CPC Class Codes: H04L 45/121 by minimising delays
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04W 28/06 Optimizing the usage of the radio link, e.g. header compression, information sizing , discarding information system modifying transmission characteristic according to link quality by modifying frame length H04L1/0007; dynamic adaptation of the packet size for flow control or congestion control H04L47/365
• 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 74/00 Wireless channel access
• CPC Class Codes: H04W 80/02 Data link layer protocols
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: H04W 92/18 between terminal devices

Abstract

A method for reducing communications in a peer-to-peer wireless network having nodes includes sending an RTS-TOA ranging communication from a first node (N₀) in a node group to another node (Nr, I) in the group, receiving the RTS-TOA communication with the second node (Nr, I) and sending a multi-cast CTS-TOA/RTS-TOA ranging communication from the second node (Nr, I) as a reply to the received RTS-TOA communication, and successively and sequentially repeating the multi-cast sending step for each of the nodes. A CTS-TOA message is a reply to the received RTS-TOA message and, simultaneously, is an RTS-TOA ranging communication to a new destination node (J). The method applies for a randomized communications approach when node identifications are not sequenced and to a sequential approach where nodes are sequenced, and also applies to completely connected and multi-hop networks. Also provided is a node for carrying out the method of the present invention.

Claims

1. A method for reducing communications in a peer-to-peer wireless network having nodes, which comprises:

sending an RTS-TOA ranging communication from a first node in a group of the nodes to a second different node in the group;

receiving the RTS-TOA ranging communication with the second node and sending a multi-cast CTS-TOA/RTS-TOA ranging communication from the second node as a reply to the received RTS-TOA ranging communication; and

successively and sequentially repeating the multi-cast sending step for each of the group of nodes.

2. The method according to claim 1, which further comprises carrying out the sending step by sending a CTS-TOA message of the multi-cast ranging communication from the second node to the first node as a reply to the received RTS-TOA message of the multi-cast ranging communication and sending the RTS-TOA ranging communication from the second node to a third node in the group different from the first node and the second node.

3. The method according to claim 2, which further comprises repeating the multi-cast sending step for all of the nodes in the group.

4. The method according to claim 3, which further comprises providing at least each node in the group with a memory to hold a Time-of-Arrival-status list, a range-status list, and a range list.

5. The method according to claim 4, which further comprises providing the network with M reference nodes and N unknown nodes.

6. The method according to claim 5, which further comprises:

providing the Time-of-Arrival-status list in each node with an individual entry for each of the other nodes in the group;

providing the range-status list in each node with an individual range-status entry for each of the other nodes in the group;

providing the range list in each node with an individual range entry for each of the other nodes in the group; and

setting a dimension of each of the Time-of-Arrival-status list, the range-status list, and the range list equal to M+N−

1.

7. The method according to claim 6, which further comprises carrying out the sending, receiving, and successively and sequentially repeating steps by:

starting determination of range between nodes from a source node and resetting each entry of the Time-of-Arrival-status list, the range-status list, and the range list in each node of the group;

randomly selecting a receiving node other than the source node with the source node;

transmitting a unicast RTS-TOA message from the source node to the receiving node;

setting a Time-of-Arrival-status of the receiving node in the Time-of-Arrival-status list of the source node;

storing a first transmission time stamp with the source node;

receiving the unicast RTS-TOA message with the receiving node and recording a first arrival time stamp with the receiving node;

determining if any entry of the Time-of-Arrival-status list of the receiving node is not set and, if any entry is not set, then;

selecting a random destination node that is not the source node with the receiving node, recording a second transmission time stamp with the receiving node, and sending the multi-cast ranging communication from the receiving node to the source node and to the destination node;

setting a Time-of-Arrival-status of the destination node in the Time-of-Arrival-status list of the receiving node;

receiving the CTS-TOA message from receiving node with the source node, recording a second arrival time stamp of the received CTS-TOA message with the source node, performing a round-trip-time calculation with the source node based upon the first transmission time stamp, the first arrival time stamp, the second transmission time stamp, and the second arrival time stamp;

after the source node finishes the round-trip-time calculation, setting a range status flag in the range-status list of the source node for the receiving node and recording the round-trip-time calculation in the range list of the source node;

upon receiving the RTS-TOA message from the receiving node with the destination node, repeating the CTS-TOA receiving, second arrival time stamp recording, round-trip-time calculating, flag setting, and calculation recording steps performed by the source node with the receiving node and repeating the RTS-TOA receiving, first arrival time stamp recording, list determining, random destination node selecting, second transmission time stamp recording, multi-cast sending, and status setting steps performed by the receiving node with the destination node.

8. The method according to claim 7, which further comprises carrying out the repeating steps with the receiving node and with the destination node until all of the nodes in the group have finished all round-trip-time calculations for all other nodes in the group.

9. The method according to claim 7, which further comprises carrying out the repeating steps with the receiving node and with the destination node until all of the nodes in the network have finished all round-trip-time calculations for all other nodes in the network.

10. The method according to claim 7, which further comprises carrying out the destination node selecting step by selecting the random destination node to be neither the source node of the immediately preceding step nor the destination node to which the CTS-TOA message was addressed in the immediately preceding step.

11. The method according to claim 7, which further comprises carrying out the repeating steps with the receiving node and with the destination node until all of the elements of a Time-of-Arrival-status list of a given receiving node are set.

12. The method according to claim 11, which further comprises calculating a range between each receiving node and each other node of the group.

13. The method according to claim 7, which further comprises carrying out the determining step by determining if any entry of the Time-of-Arrival-status list of the receiving node is not set and, if all entries are set, then:

sending a unicast CTS-TOA communication to the source node from the receiving node;

receiving the unicast CTS-TOA communication with the source node, and;

if the Time-of-Arrival-status list of the source node is not full, then selecting another random destination node with the source node not being the immediately preceding destination node; and

if the Time-of-Arrival-status list of the source node is full, then terminating transmission with the source node and broadcasting a Time-of-Arrival-status list full message with the source node to at least one other node in the group.

14. The method according to claim 13, which further comprises, if all nodes of the group have full Time-of-Arrival-status lists, then collecting all round-trip-time calculations and resolving unknown locations of at least one node in the group.

15. The method according to claim 13, which further comprises, if all nodes of the group do not have full Time-of-Arrival-status lists, then defining each non-filled node of the group not having a full Time-of-Arrival-status list to be the source node and repeating, in parallel, the selecting of the randomly selected receiving node other than the source node step with each non-filled node so defined as the source node.

16. The method according to claim 15, which further comprises:

repeating the non-filled node defining step until all ranging measurements are performed; and

collecting all round-trip-time calculations and resolving unknown locations of at least one node in the group.

17. The method according to claim 16, which further comprises defining the group as the entire network.

18. The method according to claim 17, which further comprises providing the network as a completely connected network.

19. The method according to claim 16, which further comprises providing the network as a multi-hop peer-to-peer network.

20. The method according to claim 6, which further comprises:

providing the nodes with identifications;

ordering the identifications in a single list; and

storing the ordered list in the memory of each of the nodes.

21. The method according to claim 20, which further comprises providing the nodes with unique, sequential integer identifications.

22. The method according to claim 20, which further comprises providing the nodes with unique Internet protocol address identifications.

23. The method according to claim 20, which further comprises broadcasting a reset command to each node of the group.

24. The method according to claim 23, which further comprises:

providing an integer flag in each node; and

carrying out the reset broadcasting step by broadcasting the reset command to set the integer flag of each node to be equal to 1.

25. The method according to claim 24, which further comprises carrying out the sending, receiving, and successively and sequentially repeating steps by:

starting a determination of range between nodes from an initialization node and resetting each entry of the Time-of-Arrival-status list, the range-status list, and the range list in each node of the group;

selecting a node at the initialization node according to the formula;

J=mod(I+m, X), where;

I is the identification of a current node to be initiating the next communication and the initialization node is the first current node;

J is the identification of the next node to receive the next communication;

m is the integer flag of the current round of round-trip-time measurement for the current node with identification I; and

X is the total number of nodes in the group;

transmitting a unicast RTS-TOA message from the initialization node to the next node, setting a Time-of-Arrival-status of the next node in the Time-of-Arrival-status list of the initialization node, storing a current transmission time stamp with the initialization node, and incrementing the integer flag m of the initialization node by 1;

defining the initialization node as a previous node, and defining the next node as the current node;

receiving the RTS-TOA message with the current node and performing the following steps with the current node;

recording a first arrival time stamp;

checking if the integer flag of the current node is equal to X, and;

if the integer flag of the current node is equal to X, then terminating the determination of range between the nodes of the group and calculating ranging data for all nodes in the group; and

if the integer flag of the current node is not equal to X, then;

selecting the next node to receive the next transmission according to the formula;

J=mod(I+m, X), incrementing the integer flag m of the current node by 1, recording a second transmission time stamp with the current node, and sending the multi-cast ranging communication from the current node to the previous node and to the next node;

setting a Time-of-Arrival-status of the next node in the Time-of-Arrival-status list of the current node;

receiving the CTS-TOA message of the multi-cast ranging communication with the previous node, recording a current local arrival time stamp of the received CTS-TOA message with the previous node, performing a round-trip-time calculation with the previous node based upon the current transmission time stamp, the current local arrival time stamp, the second transmission time stamp, and the first arrival time stamp, and, after the previous node finishes the round-trip-time calculation, setting a range status flag in the range-status list of the previous node for the current node and recording the round-trip-time calculation in the range list of the previous node; and

repeating with the next node the functionality of the current node upon receiving the RTS-TOA message, and repeating with the current node the functionality of the previous node upon receiving the CTS-TOA message.

26. The method according to claim 25, which further comprises carrying out the repeating steps by:

repeating the CTS-TOA receiving, current local arrival time stamp recording, round-trip-time calculating, flag setting, and calculation recording steps performed by the previous node with the current node; and

repeating the RTS-TOA receiving, first arrival time stamp recording, integer flag checking, ranging terminating and calculating, next node selecting, integer flag incrementing, second transmission time stamp recording, multi-cast sending, and status setting steps performed by the current node with the next node.

27. The method according to claim 25, which further comprises carrying out the range termination step by:

recording a second transmission time stamp with the current node, and sending a unicast CTS-TOA message from the current node to the previous node;

receiving the CTS-TOA message with the previous node, recording a current local arrival time stamp of the received CTS-TOA message with the previous node, performing a round-trip-time calculation with the previous node based upon the current transmission time stamp, the current local arrival time stamp, the second transmission time stamp, and the first arrival time stamp; and

after the previous node finishes the round-trip-time calculation;

setting a range status flag in the range-status list of the previous node for the current node;

recording the round-trip-time calculation in the range list of the previous node; and

collecting all round-trip-time calculations of the group and calculating ranging data for all nodes in the group based upon the round-trip-time calculations.

28. The method according to claim 25, which further comprises:

calculating a range between each respective pair of nodes of the group; and

resolving unknown locations of at least one node in the group based upon the calculated ranges.

29. The method according to claim 25, which further comprises:

collecting all round-trip-time calculations;

calculating a range between each respective pair of nodes of the group; and

resolving unknown locations of at least one node in the group based upon the calculated ranges.

30. The method according to claim 28, which further comprises defining the group as the entire network.

31. The method according to claim 28, which further comprises providing the network as a completely connected network.

32. The method according to claim 28, which further comprises providing the network as a multi-hop peer-to-peer network.

33. The method according to claim 24, which further comprises carrying out the sending, receiving, and successively and sequentially repeating steps by:

A) starting a determination of range between nodes from an initialization node and resetting each entry of the Time-of-Arrival-status list, the range-status list, and the range list in each node of the group;

B) selecting a node at the initialization node according to the formula;

J=mod(I+m, X), where;

I is the identification of the current node to be initiating the next communication and the initialization node is the first current node;

J is the identification of the next node to receive the next communication;

m is the integer flag of the current round of round-trip-time measurement for the current node with identification I; and

X is the total number of nodes in the group;

C) transmitting a unicast RTS-TOA message from the initialization node to the next node, setting a Time-of-Arrival-status of the next node in the Time-of-Arrival-status list of the initialization node, storing a current transmission time stamp with the initialization node, and incrementing the integer flag m of the initialization node by 1;

D) defining the initialization node as a previous node, and defining the next node as the current node;

E) receiving the RTS-TOA message with the current node and performing the following steps with the current node;

E1) recording a first arrival time stamp;

E2) checking if the integer flag of the current node is equal to X, and;

E2a) if the integer flag of the current node is equal to X, then terminating the determination of range between the nodes of the group and calculating ranging data for all nodes in the group; and

E2b) if the integer flag of the current node is not equal to X, then;

E2b1) selecting the next node to receive the next transmission according to the formula;

J=mod(I+m, X), incrementing the integer flag m of the current node by 1, recording a second transmission time stamp with the current node, and sending the multi-cast ranging communication from the current node to the previous node and to the next node;

E2b2) setting a Time-of-Arrival-status of the next node in the Time-of-Arrival-status list of the current node;

E2b3) receiving the CTS-TOA message of the multi-cast ranging communication with the previous node, recording a current local arrival time stamp of the received CTS-TOA message with the previous node, performing a round-trip-time calculation with the previous node based upon the current transmission time stamp, the current local arrival time stamp, the second transmission time stamp, and the first arrival time stamp, and, after the previous node finishes the round-trip-time calculation, setting a range status flag in the range-status list of the previous node for the current node and recording the round-trip-time calculation in the range list of the previous node; and

E2b4) repeating with the next node the functionality of the current node in steps E), E1), E2), E2a), E2b), E2b1), and E2b2) upon receiving the RTS-TOA message, and repeating with the current node the functionality of the previous node in step E2b1) and E2b3) upon receiving the CTS-TOA message.

34. A method for reducing communications in a peer-to-peer wireless network having nodes, which comprises:

sending an RTS-TOA ranging communication from an initialization node in a group of the nodes to another different node in the group;

receiving the RTS-TOA ranging communication with the other node and sending a multi-cast CTS-TOA/RTS-TOA ranging communication from the other node as a reply to the received RTS-TOA ranging communication; and

successively and sequentially repeating the multi-cast sending step for each of the group of nodes by separately and independently executing a selection algorithm with each node next receiving the RTS-TOA message of the multi-cast ranging communication, the algorithm selecting a new receiving node other than the initialization node with the other node according to the formula;

J=mod(I+m, X), where;

I is the identification of the current node to be initiating the next communication and the initialization node is the first current node;

J is an identification of the new receiving node to next receive a communication;

m is an integer flag of the current round of round-trip-time measurement for the current node with identification I;

X is the total number of nodes in the group; and

m is incremented by a respective node each time the multi-cast ranging communication is sent.

35. The method according to claim 34, which further comprises, if the integer flag of the current node is equal to X, then terminating the determination of range between the nodes of the group and calculating ranging data for all nodes in the group.

36. In a network of communications nodes, a communications node, comprising:

a receiver for receiving RTS-TOA and CTS-TOA ranging communications from other communications nodes in a group;

a transmitter for sending RTS-TOA and CTS-TOA ranging communications and multi-cast RTS-TOA/CTS-TOA ranging communications to other communications nodes in the group;

a memory storing a unique identification, an integer flag, and a total number of nodes in the group; and

a processor connected to said receiver, to said transmitter, and to said memory, said processor being programmed to;

transmit a multi-cast CTS-TOA/RTS-TOA ranging communication as a reply to a received RTS-TOA ranging communication from a first node;

select a new receiving node other than the first node to receive the RTS-TOA ranging communication according to the formula;

J=mod(I+m, X), where;

J is an identification of the new receiving node to next receive a communication;

I is the unique identification stored in said memory;

m is said integer flag of a current round of round-trip-time measurement for the node with identification I; and

X is the total number of nodes in the group; and

increment m each time said multi-cast ranging communication is sent.

37. The node according to claim 36, wherein said processor is programmed to transmit the CTS-TOA ranging communication to the first node as a reply to the received RTS-TOA ranging communication and to transmit the RTS-TOA ranging communication to the new receiving node.

38. The node according to claim 37, wherein said memory holds a Time-of-Arrival-status list, a range-status list, and a range list.

39. In a network of communications nodes, a communications node, comprising:

a receiver for receiving a reset communication, an RTS-TOA ranging communication from a node in a group of nodes, and a CTS-TOA ranging communication from a node in the group;

a transmitter for sending RTS-TOA and CTS-TOA ranging communications and multi-cast RTS-TOA/CTS-TOA ranging communications to other communications nodes in the group;

a memory storing a unique identification, an integer flag, a total number of nodes in the group, a Time-of-Arrival-status list, a range-status list, a range list, a dimension of each of said Time-of-Arrival-status list, said range-status list, and said range list being equal to a number of nodes in the group minus 1;

a processor connected to said receiver, to said transmitter, and to said memory, said processor being programmed to;

reset each entry of said Time-of-Arrival-status list, said range-status list, and said range list upon receipt of the reset communication;

receive an RTS-TOA ranging communication containing a first transmission time stamp and record a first arrival time stamp and set a Time-of-Arrival-status in the Time-of-Arrival-status list for a first node during receipt of the RTS-TOA ranging communication;

determine if any entry of the Time-of-Arrival-status list in said memory is not set and, if any entry is not set, then;

randomly select a destination node to receive a new RTS-TOA ranging communication, the destination node not being the first node or any other node to which a new RTS-TOA ranging communication has already been sent;

record a second transmission time stamp and transmit a multi-cast RTS-TOA/CTS-TOA ranging communication as;

a CTS-TOA reply to the received RTS-TOA ranging communication from the first node at least containing the second transmission time stamp and the first arrival time stamp; and

a new RTS-TOA ranging communication to the destination node containing the second transmission time stamp as a third transmission time stamp;

receive a CTS-TOA ranging communication from the destination node including a second arrival time stamp and a fourth transmission time stamp and record a third arrival time stamp of the received CTS-TOA ranging communication and set a Time-of-Arrival-status in the Time-of-Arrival-status list for the destination node;

perform a round-trip-time calculation based upon the third transmission time stamp, the second arrival time stamp, the fourth transmission time stamp, and the third arrival time stamp; and

set a range status flag, after finishing the round-trip-time calculation, in said range-status list for the destination node and record the round-trip-time calculation in said range list.

40. The node according to claim 39, wherein said processor is programmed to send a unicast CTS-TOA ranging communication to the first node if all entries of said Time-of-Arrival-status list are set.

41. The node according to claim 40, wherein said processor is programmed to select another random destination node that is not the immediately preceding destination node after receiving a unicast CTS-TOA ranging communication from the destination node if said Time-of-Arrival-status list in said memory is not full.

42. The node according to claim 41, wherein said processor is programmed to terminate transmission and broadcast a Time-of-Arrival-status list full message to at least one other node in the group if said Time-of-Arrival-status list is full.

43. The node according to claim 42, wherein said processor is programmed to transmit all round-trip-time calculations to at least one other node in the group to assist resolving unknown locations of at least one node in the group.

44. In a network of communications nodes, a communications node, comprising:

a receiver for receiving a reset communication, an RTS-TOA ranging communication from a node in a group of the nodes, and a CTS-TOA ranging communication from a node in the group;

a transmitter for sending RTS-TOA and CTS-TOA ranging communications and multi-cast RTS-TOA/CTS-TOA ranging communications to other communications nodes in the group;

a memory storing an ordered list of unique identifications for at least a group of the nodes, an integer flag, a total number of nodes in the group, a Time-of-Arrival-status list, a range-status list, a range list, a dimension of each of said Time-of-Arrival-status list, said range-status list, and said range list being equal to a number of nodes in the group minus 1;

a processor connected to said receiver, to said transmitter, and to said memory, said processor being programmed to;

reset each entry of said Time-of-Arrival-status list, said range-status list, and said range list upon receipt of the reset communication;

reset said integer flag to 1;

receive an RTS-TOA ranging communication containing a first transmission time stamp and record a first arrival time stamp and set a Time-of-Arrival-status in said Time-of-Arrival-status list for a first node during receipt of the RTS-TOA ranging communication;

select a destination node to receive a new RTS-TOA ranging communication according to the formula;

J=mod(I+m, X), where;

J is an identification of the destination node to next receive a communication;

I is the unique identification stored in said memory;

m is said integer flag of a current round of round-trip-time measurement for the node with identification I; and

X is the total number of nodes in the group;

record a second transmission time stamp, increment said integer flag by 1, and transmit a multi-cast CTS-TOA/RTS-TOA ranging communication as;

a CTS-TOA reply to the received RTS-TOA ranging communication from the first node at least containing the second transmission time stamp and the first arrival time stamp; and

a new RTS-TOA ranging communication to the destination node containing the second transmission time stamp as a third transmission time stamp;

receive a CTS-TOA ranging communication from the destination node including a second arrival time stamp and a fourth transmission time stamp and record a third arrival time stamp of the received CTS-TOA ranging communication and set a Time-of-Arrival-status in said Time-of-Arrival-status list for the destination node;

perform a round-trip-time calculation based upon the third transmission time stamp, the second arrival time stamp, the fourth transmission time stamp, and the third arrival time stamp; and

set a range status flag, after finishing the round-trip-time calculation, in said range-status list for the destination node and record the round-trip-time calculation in said range list.

45. The method according to claim 44, wherein said processor is programmed to transmit all round-trip-time calculations to at least one other node in the group to assist resolving unknown locations of at least one node in the group.