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

• US 20070201382A1
• 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, Inc. (Motorola Solutions, Inc.)
• Inventors: Johnson, Mark, Pandey, Aparna, Metke, Anthony, Phillips, Joseph, Ekl, Randy, Ware, Christopher
• Granted Patent: US 7,697,456 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: H04W 28/18 Negotiating wireless communication parameters
• 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 of selecting a root node in an ad hoc network comprising a plurality of nodes including a first node, the method comprising:

receiving a message from at least one of the nodes at a first node, wherein each message comprises at least one of a number of primary factors associated with a particular node regarding capabilities of the particular node;

evaluating the number of primary factors associated with each node; and

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

2. A method according to claim 1, wherein receiving a message from at least one of the nodes at a first node, comprises:

receiving a message from each of the nodes at each of the other nodes, wherein each 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.

3. A method according to claim 2, wherein attempting to select the root node based on the primary factors associated with each node, comprises:

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

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

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

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

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

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

6. A method according to claim 5, wherein selecting the root node, further comprises:

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

7. A method according to claim 6, wherein comparing primary factors associated with each of the nodes further comprises:

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

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

wherein selecting the root node, further comprises;

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

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

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

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

wherein selecting the root node, further comprises;

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

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

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

10. A method according to claim 9, wherein selecting the root node based on secondary 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, further comprises:

determining a weighted metric for each remaining candidate node, if the number of fixed nodes is zero or more than one;

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

wherein selecting the root node, further comprises;

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

11. A method according to claim 10, wherein the secondary factors comprise:

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

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

12. A method according to claim 10, wherein the plurality of nodes further comprises a current root node, and wherein the new root node comprises the current root node.

13. A method according to claim 10, wherein the new root node comprises one of the nodes.

14. In an ad hoc network comprising a plurality of nodes configured to select a root node for the ad hoc network, wherein each node comprises:

a receiver configured to receive a message from each of the other nodes, wherein each message comprises at least one of a number of primary factors associated with a particular node regarding capabilities of the particular node; and

a processor configured to compare primary factors associated with each of the nodes, and to attempt to select a new root node based on a result of comparing the primary factors associated with each of the nodes.

15. The nodes according to claim 14, wherein the message from each node to each of the other nodes comprises a qualification message from each of the nodes which is configured to be a root node candidate;

and

wherein the processor is further configured to;

store each of the nodes which is a root node candidate in a candidate list at each of the nodes, determine whether the number of priority nodes in the candidate list is greater than, less than or equal to one, remove nodes other than the priority nodes from the candidate list if the number of priority nodes is greater than one, and select the priority node as the new root node, if the number of priority nodes is equal to one.

16. The nodes according to claim 15, wherein, if the number of priority root nodes is zero or more than one, the processor is further configured to:

determine from a first number of nodes in the candidate list which ones are powered nodes, remove nodes other than the powered nodes from the candidate list, if the number of powered nodes is greater than one, and select the powered node as the root node, if the number of powered nodes is equal to one.

17. The nodes according to claim 16, wherein, if the number of powered nodes is zero or more than one, the processor is further configured to:

determine a second number of nodes in the candidate list which are fixed nodes, remove nodes other than the fixed nodes from the candidate list, if the number of fixed nodes is greater than one, and select the fixed node as the root node, if the number of fixed nodes is equal to one.

18. The nodes according to claim 17, wherein each message further comprises at least one of a number of secondary factors associated with a particular node regarding capabilities of the particular node,

wherein the processor is further configured to select a new root node based on at least one secondary factor associated with each node if the processor is unable to select the root node based on the primary factors associated with each node.

19. The nodes according to claim 18, wherein the secondary factors comprise at least one of:

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

20. The nodes according to claim 18, wherein, if the first node is unable to select the root node based on the primary factors associated with each node, the processor is configured to:

determine a weighted metric for each remaining candidate node based on an aggregate weighted value of secondary factors associated with each remaining candidate node;

determine which remaining candidate node has the highest weighted metric, and select the remaining candidate node having the highest weighted metric as the root node.

21. The nodes according to claim 18, wherein the new root node that is selected comprises one of the nodes.

22. The nodes according to claim 18, wherein the ad hoc network further comprises a current root node, and wherein the new root node that is selected comprises the current root node.

23. The nodes according to claim 18, wherein each of the nodes is configured to wait for an evaluation period after selecting the new root node before attempting to select another new root node in an ad hoc network.

24. In an ad hoc network comprising a plurality of nodes configured to select a root node for the ad hoc network, wherein each node comprises:

a receiver configured to receive a message from each of the other nodes, wherein each message comprises at least one of a number of primary factors associated with a particular node regarding capabilities of the particular node; and

a processor configured to compare primary factors associated with each of the nodes, and to attempt to select a new root node based on a result of comparing the primary factors associated with each of the nodes.

25. The nodes according to claim 24, wherein the message from each node to each of the other nodes comprises a qualification message from each of the nodes which is configured to be a root node candidate;

and wherein the processor is further configured to store each of the nodes which is a root node candidate in a candidate list at each of the nodes.

26. The nodes according to claim 25, wherein the primary factors comprise:

whether the nodes in the candidate list are designated as at least one of priority root nodes, powered nodes, or fixed nodes, and wherein the processor is further configured to determine whether;

the number of priority nodes in the candidate list is greater than, less than or equal to one,

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

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

27. The nodes according to claim 26, wherein the processor is further configured to remove nodes other than:

the priority nodes from the candidate list if the number of priority nodes is greater than one,

the powered nodes from the candidate list, if the number of powered nodes is greater than one, and

the fixed nodes from the candidate list, if the number of fixed nodes is greater than one.

28. The nodes according to claim 27, wherein the processor is further configured to select the:

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

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

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

29. The nodes according to claim 24, wherein each message further comprises at least one of a number of secondary factors associated with a particular node regarding capabilities of the particular node, wherein the secondary factors comprise at least one of:

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

wherein the processor is further configured to select a new root node based on at least one secondary factor associated with each node if the processor is unable to select the root node based on the primary factors associated with each node.

30. The nodes according to claim 29, wherein, if the first node is unable to select the root node based on the primary factors associated with each node, the processor is configured to:

determine a weighted metric for each remaining candidate node based on an aggregate weighted value of secondary factors associated with each remaining candidate node, and

determine which remaining candidate node has the highest weighted metric, and

select the remaining candidate node having the highest weighted metric as the new root node.