Method and apparatus for root node selection in an ad hoc network

• US 7,876,706 B2
• Filed: 02/28/2006
• Issued: 01/25/2011
• Est. Priority Date: 02/28/2006
• Status: Active Grant

• Current Assignee: ARRIS Enterprises LLC (CommScope Holding Company, Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Ware, Christopher G., Phillips, Joseph E., Pandey, Aparna, Metke, Anthony R., Johnson, Mark J., Ekl, Randy L.
• Primary Examiner(s): Pham, Chi H
• Assistant Examiner(s): Ng, Fan
• Application Number:
  US11/363,757
• Publication Number:
  US 20070201381A1
• Time in Patent Office: 1,792 Days
• Field of Search: 379/201.01, 379/201.06, 370/254, 370/255, 370/351, 370/357, 370/360, 370/384, 370/385, 370/389, 370/395.1, 370/395.5
• US Class Current: 370/254
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update
• CPC Class Codes: H04W 84/20 Master-slave selection or change arrangements

Abstract

Techniques are provided for selecting a root node in an ad hoc network comprising a plurality of nodes including a first node. According to one implementation of these techniques, a first node can receive a message from at least one of the other nodes. Each message includes a number of primary factors associated with a particular node regarding capabilities of the particular node. The primary factors associated with each node can then be evaluated, and an attempt can be made to select the root node based on the primary factors associated with each node. If the first node is unable to select the root node based on the primary factors associated with each node, then the root node can be selected based on secondary factors associated with each node.

Claims

1. A method for dynamically selecting a new root node in an ad hoc network comprising a current root node and a plurality of nodes, the method comprising:

nominating at each of the plurality of nodes a candidate root node by comparing an aggregate weighted value for that particular node to a low threshold (T_L) and a high threshold (T_H), and deciding at each of the plurality of nodes whether to nominate itself as the candidate root node depending on its relative likelihood of being selected as the new root node;

transmitting, from each of the plurality of nodes, a first status message associated with its nominated candidate root node when the aggregate weighted value for that particular node exceeds the high threshold (T_H);

receiving the first status messages at the current root node; and

selecting, at the current root node, the new root node from at least one of the candidate root nodes and the current root node based on the received first status messages.

2. A method according to claim 1, wherein nodes having the aggregate weighted value below the low threshold (T_L) do not transmit the first status message.

3. A method according to claim 1, wherein each of the first status messages comprises status information, wherein selecting, at the current root node, the new root node from at least one of the candidate root nodes and the current root node based on the received first status messages, further comprises:

selecting, at the current root node, the new root node from at least one of the candidate root nodes and the current root node based on at least some of the status information in the received first status messages.

4. A method according to claim 1, wherein each of the first status message comprises at least one of a number of primary factors associated with a corresponding candidate root node regarding capabilities of the corresponding candidate root node, and wherein selecting, at the current root node, the new root node from at least one of the candidate root nodes and the current root node, further comprises:

evaluating primary factors associated with each candidate root node; and

attempting to select the new root node based on the primary factors associated with each candidate root node.

5. A method according to claim 4, wherein each of the first status message comprises a number of primary factors associated with a corresponding candidate root node regarding capabilities of the corresponding candidate root node, and wherein evaluating a number of primary factors associated with each of the candidate root node, comprises:

comparing, at each of the plurality of nodes, primary factors associated with each of the candidate root nodes.

6. A method according to claim 4, wherein attempting to select the new root node based on the primary factors associated with each candidate root node, comprises:

selecting, at the current root node, the new root node based on a result of comparing the primary factors associated with each of the candidate root nodes.

7. A method according to claim 4, wherein the first status message from each of the candidate root nodes comprises a qualification status message indicating the configuration of the corresponding candidate root node as being capable of selection of the corresponding candidate node as the new root node, the method further comprising:

adding each of the candidate root nodes to a candidate list stored at each of the plurality of nodes.

8. A method according to claim 4, wherein comparing the primary factors associated with each of the candidate root nodes, further comprises:

determining, at each of the plurality of nodes, whether a number of candidate root nodes with a priority of being selected as the new root node in the candidate list is greater than, less than or equal to one; and

removing candidate root nodes other than the candidate nodes with the priority of being selected as the new root node from the candidate list, at each of the plurality of nodes, when the number of candidate root nodes with the priority of being selected as the new root node is greater than one.

9. A method according to claim 8, wherein selecting the new root node, further comprises:

choosing the candidate root node with the priority as the new root node, when the number of the candidate root nodes with the priority of being selected as the new root node is equal to one.

10. A method according to claim 9, wherein comparing the primary factors associated with each of the candidate root nodes further comprises:

determining a first number of the candidate root nodes in the candidate list that are powered ON, when the number of the candidate root nodes with the priority of being selected as the new root node is zero or more than one;

removing the candidate root nodes other than the candidate root nodes that are powered ON from the candidate list, when the number of the candidate root nodes that are powered ON is greater than one; and

wherein selecting the new root node, further comprises;

choosing the candidate root node that is powered ON as the new root node, when the number of the candidate root nodes that are powered ON is equal to one.

11. A method according to claim 10, wherein comparing the primary factors associated with each of the candidate root nodes further comprises:

determining a second number of the candidate root nodes in the candidate list that are fixed, when the number of the candidate root nodes that are powered ON is zero or more than one;

removing the candidate root nodes other than the candidate root nodes that are fixed from the candidate list, when the number of the candidate root nodes that are fixed is greater than one; and

wherein selecting the new root node, further comprises;

choosing the candidate root node that is fixed as the new root node, when the number of the candidate root nodes that are fixed is equal to one.

12. A method according to claim 11, wherein each of the first status messages further comprises at least one of a number of secondary factors associated with a corresponding candidate root node regarding capabilities of the corresponding candidate root node, and further comprising:

selecting the new root node based on at least one secondary factor associated with each candidate root node when the current root node is unable to select the new root node based on the primary factors associated with each candidate root node.

13. A method according to claim 12, wherein selecting the new root node based on the secondary factors associated with each candidate root node when the current root node is unable to select the new root node based on the primary factors associated with each candidate root node, further comprises:

determining a weighted metric for each of candidate root node that is powered OFF, mobile and is without a priority of being selected as the new root node, when the number of candidate root nodes that are fixed is zero or more than one;

determining which candidate root node among the candidate root nodes without a priority of being selected as the new root node and neither powered ON nor fixed has the highest weighted metric; and

wherein selecting the new root node, further comprises;

selecting the candidate root node among the candidate root node that is powered OFF, mobile and is without a priority of being selected as the new root node and have the highest weighted metric as the new root node, when the number of the candidate root nodes that are fixed is zero.

14. A method according to claim 13, wherein the secondary factors comprise:

(a) proximity of a corresponding candidate root node to infrastructure, (b) proximity quality of the corresponding candidate root node to the infrastructure, (c) stability of the corresponding candidate root node based on the number of route changes per unit time, (d) node battery level of the corresponding candidate root node which indicates the amount of power the corresponding candidate root node has remaining, (e) path battery level for the corresponding candidate root node and intervening nodes between the corresponding candidate root node and the infrastructure, (f) average cost to all other nodes, and (g) number of neighbor nodes, and

wherein each weighted metric is determined based on an aggregate weighted value of the secondary factors.

15. A method according to claim 1, wherein nominating at each of the nodes a candidate root node, further comprises:

transmitting a second status message from each of the plurality of nodes, wherein each of the second status messages comprises status information regarding the ability of the corresponding node to serve as a root node;

receiving at least some of the second status messages at each of the plurality of nodes; and

selecting, at each of the plurality of nodes, either itself or one of the plurality of nodes as the candidate root node based on the received second status messages.

16. A method according to claim 15, wherein transmitting a first status message associated with its nominated candidate root node, further comprises:

transmitting the first status message from each of the plurality of nodes to the current root node, wherein each of the first status messages identifies the corresponding candidate root node and status information associated with the corresponding candidate root node.

17. A method according to claim 16,

wherein selecting, at the current root node, the new root node based on the received first status messages, further comprises:

selecting, at the current root node, the new root node from at least one of the candidate root nodes and the current root node based on the status information associated with each candidate root node and a status information associated with the current root node.

18. A method according to claim 15, wherein selecting, at each of the nodes, either itself or one of the plurality of nodes as the candidate root node based on the received first status messages, further comprises:

comparing, at each of the plurality of nodes, the status information associated with each of the plurality of nodes with its status information; and

nominating, at each of the plurality of nodes, one of the plurality of nodes as the candidate root node based on the status information associated with a corresponding one of the plurality of nodes with its status information.

19. A method according to claim 15, wherein the status information associated with each of the plurality of nodes comprises at least one of one or more primary factors, one or more secondary factors and one or more aggregate weighted values associated with a corresponding one of the plurality of nodes, and wherein selecting, at each of the plurality of nodes, either itself or one of the plurality of nodes as the candidate root node based on the received second status messages, further comprises:

comparing, at each of the plurality of nodes, the at least one of the primary factors, the secondary factors and a highest aggregate weighted value associated with a corresponding one of the plurality of nodes with its; and

nominating, at each of the plurality of nodes, one of the nodes as the candidate root node based on the at least one of the primary factors, the secondary factors and the highest aggregate weighted value associated with a corresponding one of the plurality of nodes and its status information.

20. A method according to claim 17, wherein the status information associated with each of the plurality of nodes comprises at least one of one or more primary factors, one or more secondary factors and one or more aggregate weighted values associated with a corresponding one of the plurality of nodes, and

wherein selecting, at the current root node, the new root node from at least one of the candidate root nodes and the current root node based on the status information associated with the corresponding one of the candidate root node and status information associated with the current root node, further comprises:

selecting, at the current root node, the new root node from at least one of the candidate root nodes and the current root node based on the at least one of the primary factors, the secondary factors and the aggregate weighted values associated with the corresponding one of the candidate root node and the at least one of the primary factors, the secondary factors and the aggregate weighted values associated with the current root node.

21. A method according to claim 20, wherein each of the first status message comprises at least one of a number of primary factors associated with a corresponding node regarding capabilities of the corresponding node, and wherein selecting, at the current root node, the new root node from at least one of the candidate root nodes and the current root node based on the at least one of the primary factors, the secondary factors and the aggregate weighted values associated with each of the candidate root node and the at least one of the primary factors, the secondary factors and the aggregate weighted values associated with the current root node, further comprises:

selecting, at the current root node, the new root node from at least one of the candidate root nodes and the current root node based on the at least one primary factor associated with each candidate root node and the at least one primary factor associated with the current root node.

22. A method according to claim 20, wherein each of the first status message comprises a number of primary factors associated with a corresponding node regarding capabilities of the corresponding node, and wherein selecting, at the current root node, the new root node from at least one of the candidate root nodes and the current root node based on the at least one of the primary factors, the secondary factors and the aggregate weighted values associated with each of the candidate root node and the at least one of the primary factors, the secondary factors and the aggregate weighted values associated with the current root node, further comprises:

selecting, at the current root node, the new root node from at least one of the candidate root nodes and the current root node based on the primary factors associated with each particular candidate root node and the primary factors associated with the current root node.

23. A method according to claim 22, wherein selecting, at the current root node, the new root node from at least one of the candidate root nodes and the current root node based on the primary factors associated with each candidate root node and the primary factors associated with the current root node, further comprises:

comparing, at the current root node, primary factors associated with each of the candidate root nodes; and

attempting to select, at the current root node, a new root node based on a result of comparing the primary factors associated with each of the candidate root nodes.

24. A method according to claim 23, wherein the primary factors comprise:

whether the candidate root nodes are designated as at least one of the candidate root nodes with a priority of being selected as the new root node, the candidate root nodes that are powered ON, or the candidate nodes that are fixed, and further comprising;

determining whether the number of the candidate root nodes with the priority of being selected as the new root node is greater than, less than or equal to one;

determining a first number of the candidate root nodes that are powered ON, when the number of nominee root nodes with the priority of being selected as the new root node is zero or more than one; and

determining a second number of the candidate root nodes that are fixed, when the number of the candidate root nodes that are powered ON is zero or more than one.

25. A method according to claim 24, further comprising:

removing the candidate root nodes other than the candidate root nodes with the priority of being selected as the new root node from consideration when the number of the candidate root nodes with the priority of being selected as the new root node is greater than one,

removing the candidate root nodes other than the candidate root nodes that are powered ON from consideration, when the number of the candidate root nodes that are powered ON is greater than one, and

removing the candidate root nodes other than the candidate root nodes that are fixed from consideration, when the number of the candidate root nodes that are fixed is greater than one.

26. A method according to claim 25, further comprising:

selecting the candidate root node with the priority of being selected as the new root node as the new root node, when the number of the candidate root nodes with the priority of being selected as the new root node is equal to one,

selecting the candidate root node that are powered ON as the new root node, when the number of the candidate root nodes that are powered ON is equal to one, and

selecting the candidate root node that are fixed as the new root node, when the number of the candidate root nodes that are fixed is equal to one.

27. A method according to claim 26, wherein each of the first status message further comprises at least one of a number of secondary factors associated with a corresponding candidate root node regarding capabilities of the corresponding candidate root node, wherein the secondary factors comprise at least one of:

(a) proximity of a corresponding candidate root node to infrastructure, (b) proximity quality of the corresponding candidate root node to the infrastructure, (c) stability of the corresponding candidate root node based on the number of route changes per unit time, (d) node battery level of the corresponding candidate root node which indicates the amount of power the corresponding candidate root node has remaining, (e) path battery level for the corresponding candidate root node and intervening nodes between the corresponding candidate root node and the infrastructure, (f) average cost to all other nodes, and (g) number of neighbor nodes, and

further comprising;

selecting a new root node based on at least one secondary factor associated with each candidate root node when the current root node is unable to select the new root node based on the primary factors associated with each candidate root node.

28. A method according to claim 27, wherein, when the current root node is unable to select the new root node based on the primary factors associated with each candidate root node, further comprising:

determining a weighted metric for each of the candidate root node that is powered OFF, mobile and is without a priority of being selected as the new root node based on an aggregate weighted value of secondary factors associated with each candidate root node, and

determining which candidate root node among the candidate root nodes that are powered OFF, mobile and are without a priority of being selected as the new root node has the highest weighted metric, and

selecting the candidate root node that is powered OFF, mobile and is without a priority of being selected as the new root node and have the highest weighted metric as the new root node.