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

• US 20070201381A1
• Filed: 02/28/2006
• Published: 08/30/2007
• Est. Priority Date: 02/28/2006
• Status: Active Grant

• Current Assignee: ARRIS Enterprises LLC (CommScope Holding Company, Inc.)
• Original Assignee: Motorola Solutions, Inc.
• Inventors: Johnson, Mark, Pandey, Aparna, Metke, Anthony, Phillips, Joseph, Ekl, Randy, Ware, Christopher
• Granted Patent: US 7,876,706 B2
• Time in Patent Office: Days
• 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 nodes a candidate root node;

transmitting a status message associated with each of the candidate root nodes;

receiving the status messages at the current root node; and

selecting, at the current root node, the new root node based on the status messages received from each of the candidate root nodes.

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

deciding at each of the nodes whether to nominate that particular node as a candidate root node; and

wherein transmitting a status message associated with each of the candidate root nodes, further comprises;

transmitting a status message from each of the nodes which decides to nominate that particular node as the candidate root node; and

wherein selecting, at the current root node, the new root node based on the status messages received from each of the candidate root nodes, 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 messages received from each of the candidate root nodes.

3. A method according to claim 2, wherein deciding at each of the nodes whether to nominate that particular node as a candidate root node, further comprises:

deciding at each of the nodes whether to nominate that particular node as a candidate root node depending on the relative likelihood of that node being selected as a root node.

4. A method according to claim 3, wherein each of the nodes decides whether to nominate that particular node as a candidate root node depending on the relative likelihood of that node being selected as a root node by:

comparing an aggregate weighted value for the particular node to a low threshold (T_L) and a high threshold (T_H).

5. A method according to claim 4, wherein transmitting a status message from each of the nodes which decides to nominate that particular node as the candidate root node, further comprises:

transmitting a status message from each of the nodes having an aggregate weighted value which exceeds the high threshold (T_H) to nominate those nodes as the candidate root nodes.

6. A method according to claim 5, wherein nodes having an aggregate weighted value below the low threshold (T_L) do not transmit a status message.

7. A method according to claim 2, wherein each status message 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 status messages received from each of the candidate root nodes, 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 status messages received from each of the candidate root nodes.

8. A method according to claim 2, wherein each status message comprises at least one of a number of primary factors associated with a particular candidate root node regarding capabilities of the particular 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.

9. A method according to claim 8, wherein each status message comprises a number of primary factors associated with a particular node regarding capabilities of the particular node, and wherein evaluating a number of primary factors associated with each node, comprises:

comparing, at each node, primary factors associated with each of the nodes.

10. A method according to claim 9, 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, a new root node based on a result of comparing the primary factors associated with each of the candidate root nodes.

11. A method according to claim 8, wherein the status message from each node to each of the candidate root nodes comprises a qualification status message from each of the candidate root nodes which is configured to be a root node candidate, and further comprising:

adding each of the candidate root nodes which is a root node candidate to a candidate list stored at each of the nodes.

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

determining, at each of the nodes, whether a number of priority candidate root nodes in the candidate list is greater than, less than or equal to one; and

removing candidate root nodes other than the priority nodes from the candidate list, at each of the nodes, if the number of priority candidate root nodes is greater than one.

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

choosing the priority candidate root node as the new root node, if the number of priority candidate root nodes is equal to one.

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

determining a first number of candidate root nodes in the candidate list which are powered candidate root nodes, if the number of priority candidate root nodes is zero or more than one;

removing candidate root nodes other than the powered candidate root nodes from the candidate list, if the number of powered candidate root nodes is greater than one; and

wherein selecting the new root node, further comprises;

choosing the powered candidate root node as the new root node, if the number of powered candidate root nodes is equal to one.

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

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

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

wherein selecting the new root node, further comprises;

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

16. A method according to claim 15, wherein each status message further comprises at least one of a number of secondary factors associated with a particular candidate root node regarding capabilities of the particular candidate root node, and further comprising:

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

17. A method according to claim 16, wherein selecting the new root node based on secondary factors associated with each candidate root node if 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 remaining candidate root node, if the number of fixed candidate root nodes is zero or more than one;

determining which remaining candidate root node has the highest weighted metric; and

wherein selecting the new root node, further comprises;

selecting the remaining candidate root node having the highest weighted metric as the new root node, if the number of fixed candidate root nodes is zero.

18. A method according to claim 17, wherein the secondary factors comprise:

(a) proximity of a particular candidate root node to infrastructure, (b) proximity quality of the particular candidate root node to the infrastructure, (c) stability of the particular candidate root node based on the number of route changes per unit time, (d) node battery level of the particular candidate root node which indicates the amount of power the particular candidate root node has remaining, (e) path battery level for the particular candidate root node and intervening nodes between the particular 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 secondary factors.

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

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

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

selecting, at each of the nodes, either the particular node or one of the other nodes as a nominee root node based on the status messages received from the other nodes.

20. A method according to claim 19, wherein transmitting a status message associated with each of the candidate root nodes, further comprises:

transmitting a nomination message from each of the nodes to the current root node, w herein each nomination message identifies the particular nominee root node each nodes has decided to nominate and status information associated with that particular nominee root node;

21. A method according to claim 20, wherein receiving the status messages at the current root node, further comprises:

receiving the nomination messages at the current root node; and

wherein selecting, at the current root node, the new root node based on the status messages received from each of the candidate root nodes, further comprises;

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

22. A method according to claim 19, wherein selecting, at each of the nodes, either the particular node or one of the other nodes as a nominee root node based on the status messages received from the other nodes, further comprises:

comparing, at each particular node, status information associated with each node that the particular node receives a status message from and status information associated with the particular node; and

nominating, at each particular node, one of the nodes as a nominee root node based on the status information associated with each node that the particular node receives a status message from and status information associated with the particular node.

23. A method according to claim 19, wherein the status information associated with each particular node comprises primary factors, secondary factors and/or aggregate weighted value associated with each particular node, and wherein selecting, at each of the nodes, either the particular node or one of the other nodes as a nominee root node based on the status messages received from the other nodes, further comprises:

comparing, at each particular node, primary factors, secondary factors and/or the highest aggregate weighted value associated with each node that the particular node receives a status message from and status information associated with the particular node; and

nominating, at each particular node, one of the nodes as a nominee root node based on the primary factors, secondary factors and/or the highest aggregate weighted value associated with each node that the particular node receives a status message from and status information associated with the particular node.

24. A method according to claim 21, wherein the status information associated with each node comprises primary factors, secondary factors and/or aggregate weighted values associated with each node, and

wherein selecting, at the current root node, the new root node from at least one of the nominee root nodes and the current root node based on the status information associated with each particular nominee 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 nominee root nodes and the current root node based on the primary factors, secondary factors and/or aggregate weighted values associated with each particular nominee root node and the primary factors, secondary factors and/or aggregate weighted values associated with the current root node.

25. A method according to claim 24, wherein each status message comprises at least one of a number of primary factors associated with a particular node regarding capabilities of the particular node, and wherein selecting, at the current root node, the new root node from at least one of the nominee root nodes and the current root node based on the primary factors, secondary factors and/or aggregate weighted values associated with each particular nominee root node and the primary factors, secondary factors and/or 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 nominee root nodes and the current root node based on the at least one primary factor associated with each particular nominee root node and the at least one primary factor associated with the current root node.

26. A method according to claim 24, wherein each status message comprises a number of primary factors associated with a particular node regarding capabilities of the particular node, and wherein selecting, at the current root node, the new root node from at least one of the nominee root nodes and the current root node based on the primary factors, secondary factors and/or aggregate weighted values associated with each particular nominee root node and the primary factors, secondary factors and/or 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 nominee root nodes and the current root node based on the primary factors associated with each particular nominee root node and the primary factors associated with the current root node.

27. A method according to claim 26, wherein selecting, at the current root node, the new root node from at least one of the nominee root nodes and the current root node based on the primary factors associated with each particular nominee 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 nominee 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 nodes.

28. A method according to claim 27, wherein the primary factors comprise:

whether the nominee root nodes are designated as at least one of priority nominee root nodes, powered nominee root nodes, or fixed nominee root nodes, and further comprising;

determining whether the number of priority nominee root nodes is greater than, less than or equal to one;

determining a first number of nominee root nodes which are powered nominee root nodes, if the number of priority nominee root nodes is zero or more than one; and

determining a second number of nominee root nodes which are fixed nominee root nodes, if the number of powered nominee root nodes is zero or more than one.

29. A method according to claim 28, further comprising:

removing nominee root nodes other than the priority nominee root nodes from consideration if the number of priority nominee root nodes is greater than one,

removing nodes other than the powered nominee root nodes from consideration, if the number of powered nominee root nodes is greater than one, and

removing nodes other than the fixed nominee root nodes from consideration, if the number of fixed nominee root nodes is greater than one.

30. A method according to claim 29, further comprising:

selecting the priority nominee root node as the new root node, if the number of priority nominee root nodes is equal to one,

selecting the powered nominee root node as the new root node, if the number of powered nominee root nodes is equal to one, and

selecting the fixed nominee root node as the new root node, if the number of fixed nominee root nodes is equal to one.

31. A method according to claim 30, wherein each status message further comprises at least one of a number of secondary factors associated with a particular nominee root node regarding capabilities of the particular nominee root node, wherein the secondary factors comprise at least one of:

(a) proximity of a particular nominee root node to infrastructure, (b) proximity quality of the particular nominee root node to the infrastructure, (c) stability of the particular nominee root node based on the number of route changes per unit time, (d) node battery level of the particular nominee root node which indicates the amount of power the particular nominee root node has remaining, (e) path battery level for the particular nominee root node and intervening nodes between the particular nominee 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 nominee root node if the current root node is unable to select the new root node based on the primary factors associated with each nominee root node.

32. A method according to claim 31, wherein, if the current root node is unable to select the new root node based on the primary factors associated with each nominee root node, further comprising:

determining a weighted metric for each remaining nominee root node based on an aggregate weighted value of secondary factors associated with each remaining nominee root node, and

determining which remaining nominee root node has the highest weighted metric, and

selecting the remaining nominee root node having the highest weighted metric as the new root node.