Method for synchronizing sleeping nodes in a wireless network

• US 8,593,991 B2
• Filed: 04/24/2009
• Issued: 11/26/2013
• Est. Priority Date: 04/24/2009
• Status: Active Grant

• Current Assignee: Digi International Inc.
• Original Assignee: Digi International Inc.
• Inventors: Byard, Robert P., George, Jay Douglas, Filoso, John P.
• Primary Examiner(s): Lai, Andrew
• Assistant Examiner(s): Nguyen, Chuong M
• Application Number:
  US12/429,358
• Publication Number:
  US 20100271993A1
• Time in Patent Office: 1,677 Days
• Field of Search: 370/254, 370/337, 370/338, 370/408, 370/442, 455/11.1, 455/255, 455/422.1, 455/423, 455/524, 455/561, 709208-211
• US Class Current: 370/254
• CPC Class Codes: H04J 3/0641 Change of the master or reference, e.g. take-over or failure of the master
• CPC Class Codes: H04W 52/0216 using a pre-established activity schedule, e.g. traffic indication frame
• CPC Class Codes: H04W 52/0219 where the power saving management affects multiple terminals
• CPC Class Codes: H04W 52/0229 where the received signal is a wanted signal
• CPC Class Codes: H04W 84/20 Master-slave selection or change arrangements
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

A system and method of operating a wireless network having a plurality of nodes. Each node determines whether to replace the beacon node. When a node determines that the beacon node is to be replaced, the node determines whether it should nominate itself as a potential replacement beacon node. The decision whether to nominate itself as a potential replacement beacon node is a function of a random number generated by the node. If the node determines that it should nominate itself as a potential replacement beacon node, the node sends out one or more beacon signals. Beacon signals are received by potential replacement nodes and, if the potential replacement beacon node has received a beacon signal from a higher ranking potential replacement beacon node, the node removes itself as a candidate for the replacement beacon node.

Claims

1. In a wireless network having a plurality of nodes, including a beacon node, a comprising:

determining, at each node, whether to replace the beacon node;

if a node determines that the beacon node is to be replaced, determining whether the node should nominate itself as a potential replacement beacon node, wherein determining whether the node should nominate itself as a potential replacement beacon node is a function of a nomination probability associated with the node;

if the node determines that it should nominate itself as a potential replacement beacon node, sending out one or more beacon signals;

receiving beacon signals from other nodes that have nominated themselves as potential replacement beacon nodes; and

selecting the replacement beacon node wherein the selecting includes;

determining, at each potential replacement beacon node, whether the potential replacement beacon node has received a beacon signal from a higher ranking potential replacement beacon node; and

if the potential replacement beacon node has received a beacon signal from a higher ranking potential replacement beacon node, removing itself as a candidate for the replacement beacon node;

wherein determining whether the node should nominate itself as a potential replacement beacon node includes generating a random number at the node and comparing the random number to a threshold value.

6. The method of claim 1, wherein the wireless network includes exterior nodes and interior nodes and wherein determining whether the node should nominate itself as a potential replacement beacon node includes reviewing if the node is an interior or exterior node and preventing nomination if the node is an exterior node.

9. The method of claim 1, wherein determining whether the potential replacement beacon node has received a beacon signal from a higher ranking potential replacement beacon node includes comparing a parameter stored on each node, wherein the parameter is stored by an operator.

10. The method of claim 9, wherein the parameter is a MAC address.

11. The method of claim 1, wherein determining whether the potential replacement beacon node has received a beacon signal from a higher ranking potential replacement beacon node includes comparing the node-hop tally of the potential replacement beacon node to the node-hop tally of each node that sent a beacon signal, wherein the node-hop tally of each node is the total number of node hops required for the node to reach each other node in the wireless network.

12. The method of claim 1, wherein the threshold value is selected to decrease nominations by nodes from the plurality of nodes as the number of the nodes in the network increases.

13. The method of claim 1, wherein the threshold value is selected to favor nomination of nodes close to the center of the network and disfavor nodes away from the center of the network.

14. The method of claim 1, wherein the threshold value is selected to favor nodes with better link-quality metrics.

2. In a wireless network having a plurality of nodes, including a beacon node, a method comprising:

determining, at each node, whether to replace the beacon node;

if a node determines that the beacon node is to be replaced, determining whether the node should nominate itself as a potential replacement beacon node, wherein determining whether the node should nominate itself as a potential replacement beacon node is a function of a nomination probability associated with the node;

if the node determines that it should nominate itself as a potential replacement beacon node, sending out one or more beacon signals;

receiving beacon signals from other nodes that have nominated themselves as potential replacement beacon nodes; and

selecting the replacement beacon node wherein the selecting includes;

determining, at each potential replacement beacon node, whether the potential replacement beacon node has received a beacon signal from a higher ranking potential replacement beacon node; and

if the potential replacement beacon node has received a beacon signal from a higher ranking potential replacement beacon node, removing itself as a candidate for the replacement beacon node;

wherein determining whether the node should nominate itself as a potential replacement beacon node includes generating a random number at the node and comparing the random number to a threshold value associated with the node.

3. The method of claim 2, wherein the threshold value associated with the node is a function of a link-quality metric associated with the node.

4. The method of claim 2, wherein the threshold value associated with the node is a function of the location of the node with respect to the other nodes in the wireless network.

5. The method of claim 2, wherein the threshold value associated with the node is a function of a node-hop tally, wherein the node-hop tally includes the total number of node hops required for the node to reach each other node in the wireless network.

7. The method of claim 2, wherein determining whether the potential replacement beacon node has received a beacon signal from a higher ranking potential replacement beacon node includes comparing accuracy of timekeeping apparatus of the potential replacement beacon node to accuracy of timekeeping apparatus of the node receiving the beacon signal.

8. The method of claim 2, wherein determining whether the potential replacement beacon node has received a beacon signal from a higher ranking potential replacement beacon node includes comparing a length of time parameter from each node measured from when each node'"'"'s sleeping parameters was last configured.

15. The method of claim 2, wherein sending out one or more beacon signals includes transmitting a beacon signal periodically as long as the node remains a potential replacement beacon node.

16. The method of claim 15, wherein transmitting a the beacon signal periodically includes determining how many beacon signals were received over a period of time and throttling back transmission of the beacon signals as a function of how many beacon signals were received over that period of time.

17. A wireless network comprising:

a plurality of nodes, wherein each node communicates wirelessly to one or more other nodes in the network and wherein one node operates as a beacon node to synchronize each of the remaining nodes;

wherein each node includes;

a detection mechanism for detecting when the beacon node should be replaced;

a self-nominating mechanism for determining when the node should nominate itself as a potential replacement beacon node; and

an election mechanism for removing the node as a candidate for the replacement beacon node;

wherein the self-nominating mechanism operates to determine whether the node should nominate itself as a potential replacement beacon node, wherein the node nominates itself as a function of a nomination probability associated with the node;

wherein the node transmits a beacon signal to other nodes in the network periodically as long as it remains a potential replacement beacon node; and

wherein the election mechanism removes the node as a candidate for the replacement beacon node when the node receives a beacon signal from a higher ranking potential replacement beacon node; and

wherein the node determines whether to nominate itself as a potential replacement beacon node by generating a random number at the node and comparing the random number to a threshold value associated with the node.

21. The network of claim 17, wherein the period for transmitting the beacon signal increases as a function of the number of beacon signals received by the node.

18. A wireless network comprising:

a plurality of nodes, wherein each node communicates wirelessly to one or more other nodes in the network and wherein one node operates as a beacon node to synchronize each of the remaining nodes;

wherein each node includes;

a detection mechanism for detecting when the beacon node should be replaced;

a self-nominating mechanism for determining when the node should nominate itself as a potential replacement beacon node; and

an election mechanism for removing the node as a candidate for the replacement beacon node;

wherein the self-nominating mechanism operates to determine whether the node should nominate itself as a potential replacement beacon node, wherein the node nominates itself as a function of a nomination probability associated with the node;

wherein the node transmits a beacon signal to other nodes in the network periodically as long as it remains a potential replacement beacon node; and

wherein the election mechanism removes the node as a candidate for the replacement beacon node when the node receives a beacon signal from a higher ranking potential replacement beacon node;

wherein the node nominates itself as a function of a random number generated by the node and a threshold value associated with the node;

wherein the threshold value associated with the node is a function of a link-quality metric associated with the node.

19. A wireless network comprising:

a plurality of nodes, wherein each node communicates wirelessly to one or more other nodes in the network and wherein one node operates as a beacon node to synchronize each of the remaining nodes;

wherein each node includes;

a detection mechanism for detecting when the beacon node should be replaced;

a self-nominating mechanism for determining when the node should nominate itself as a potential replacement beacon node; and

an election mechanism for removing the node as a candidate for the replacement beacon node;

wherein the self-nominating mechanism operates to determine whether the node should nominate itself as a potential replacement beacon node, wherein the node nominates itself as a function of a nomination probability associated with the node;

wherein the node transmits a beacon signal to other nodes in the network periodically as long as it remains a potential replacement beacon node; and

wherein the election mechanism removes the node as a candidate for the replacement beacon node when the node receives a beacon signal from a higher ranking potential replacement beacon node;

wherein the node nominates itself as a function of a random number generated by the node and a threshold value associated with the node;

wherein the threshold value associated with the node is a function of the location of the node with respect to the other nodes in the wireless network.

20. A wireless network comprising:

a plurality of nodes, wherein each node communicates wirelessly to one or more other nodes in the network and wherein one node operates as a beacon node to synchronize each of the remaining nodes;

wherein each node includes;

a detection mechanism for detecting when the beacon node should be replaced;

a self-nominating mechanism for determining when the node should nominate itself as a potential replacement beacon node; and

an election mechanism for removing the node as a candidate for the replacement beacon node;

wherein the self-nominating mechanism operates to determine whether the node should nominate itself as a potential replacement beacon node, wherein the node nominates itself as a function of a nomination probability associated with the node;

wherein the node transmits a beacon signal to other nodes in the network periodically as long as it remains a potential replacement beacon node; and

wherein the election mechanism removes the node as a candidate for the replacement beacon node when the node receives a beacon signal from a higher ranking potential replacement beacon node;

wherein the node nominates itself as a function of a random number generated by the node and a threshold value associated with the node;

wherein the threshold value associated with the node is selected to favor nomination of nodes close to the center of the network and disfavor nodes away from the center of the network.

22. An article comprising a non-transitory computer readable medium having instructions thereon, wherein the instructions, when executed by a machine, create a system for executing a method comprising:

determining, at each node in a wireless network having a plurality of nodes, whether to replace the beacon node;

if a node determines that the beacon node is to be replaced, determining whether the node should nominate itself as a potential replacement beacon node, wherein determining whether the node should nominate itself as a potential replacement beacon node is a function of a nomination probability associated with the node;

if the node determines that it should nominate itself as a potential replacement beacon node, sending out one or more beacon signals;

receiving beacon signals from other nodes that have nominated themselves as potential replacement beacon nodes; and

selecting the replacement beacon node, wherein the selecting includes;

determining, at each potential replacement beacon node, whether the potential replacement beacon node has received a beacon signal from a higher ranking potential replacement beacon node; and

if the potential replacement beacon node has received a beacon signal from a higher ranking potential replacement beacon node, removing itself as a candidate for the replacement beacon node;

wherein determining whether the node should nominate itself as a potential replacement beacon node includes generating a random number at the node and comparing the random number to a threshold value.