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

• US 20070204021A1
• Filed: 02/28/2006
• Published: 08/30/2007
• Est. Priority Date: 02/28/2006
• Status: Abandoned Application

• Current Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Johnson, Mark, Pandey, Aparna, Metke, Anthony, Phillips, Joseph, Ekl, Randy, Ware, Christopher
• Application Number:
  US11/363,756
• Publication Number:
  US 20070204021A1
• Time in Patent Office: Days
• US Class Current: 709/223
• CPC Class Codes: H04W 40/04 based on wireless node resources
• CPC Class Codes: H04W 40/10 based on available power or energy
• CPC Class Codes: H04W 40/12 based on transmission quality or channel quality
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 40/248 Connectivity information update
• CPC Class Codes: Y02D 30/70 in wireless communication networks

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 and at least one of a number of secondary factors associated with a particular node regarding capabilities of the particular node;

evaluating the number of primary factors associated with each node;

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

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.

2. The method according to claim 1, wherein the ad hoc network comprises the first node and a current root node,

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

receiving a message from the current root node at the first node, wherein each the message from the current root node comprises a number of primary factors associated with the current root node regarding capabilities of the current root node; and

wherein evaluating a number of primary factors associated with each node, comprises;

comparing, at the first node, first primary factors associated with the first node to second primary factors associated with the current root node.

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

selecting, at the first node, a new root node based on a result of comparing the first primary factors to the second primary factors.

4. The method according to claim 3, wherein the new root node comprises the current root node.

5. The method according to claim 3, wherein the new root node comprises the first node.

6. The method according to claim 3, wherein comparing, at the first node, first primary factors associated with the first node to second primary factors associated with the current root node, comprises:

determining, at the first node, if a first root configuration status of the first node is greater than a second root configuration status of a current root node; and

wherein selecting a new root node at the first node based on a result of comparing the first primary factors to the second primary factors, further comprises;

selecting, at the first node, the first node as the new root node if the first root configuration status is greater than the second root configuration status;

waiting for an evaluation period after asserting that the first node is the new root node, then attempting to select a new root node in the ad hoc network;

selecting, at the first node, the current root node as the root node if the first root configuration status is less than the second root configuration status;

waiting for an evaluation period after determine that the first root configuration status is less than the second root configuration status, then attempting to select a new root node in the ad hoc network.

7. A method according to claim 6, further comprising:

determining, at the first node, if a first power source of the first node is greater than a second power source of the current root node, if the first root configuration status is the same as the second root configuration status; and

wherein selecting the new root node, further comprises;

selecting, at the first node, the first node as the new root node if the first power source is greater than the second power source;

waiting for an evaluation period after asserting that the first node is the new root node, then attempting to select a new root node in the ad hoc network;

selecting, at the first node, the current root node as the root node if the first power source is less than the second power source;

waiting for an evaluation period after determining that the first power source is less than the second power source, then attempting to select a new root node in the ad hoc network.

8. A method according to claim 7, further comprising:

determining, at the first node, if a first mobility status of the first node is less than a second mobility status of the current root node, if the first power source is the same as the second power source; and

wherein selecting the new root node, further comprises;

selecting, at the first node, the first node as the new root node if the first mobility status is less than the second mobility status;

waiting for an evaluation period after asserting that the first node is the new root node, then attempting to select a new root node in the ad hoc network;

selecting, at the first node, the current root node as the root node if the first mobility status is greater than the second mobility status;

waiting for an evaluation period after determine that the first mobility status is greater than the second mobility status, then attempting to select a new root node in the ad hoc network.

9. A method according to claim 8, 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, at the first node, a first weighted metric associated with the first node and a second weighted metric associated with the current root node if the first mobility status of the first node is the same as the second mobility status of the current root node;

determining, at the first node, if a first weighted metric of the first node is greater than a second weighted metric of the current root node; and

wherein selecting the new root node, further comprises;

selecting, at the first node, the first node as the new root node if the first weighted metric is greater than the second weighted metric;

waiting for an evaluation period after asserting that the first node is the new root node, then attempting to select a new root node in the ad hoc network;

selecting, at the first node, the current root node as the new root node if the first weighted metric is less than the second weighted metric;

waiting for an evaluation period after determine that the first weighted metric is less than the second weighted metric, then attempting to select a new root node in the ad hoc network.

10. A method according to claim 9, wherein each weighted metric is determined based on an aggregate weighted value of secondary factors.

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.

12. A first node configured to select a root node in an ad hoc network comprising a plurality of other nodes, the first node comprising:

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

a processor configured to;

evaluate the number of primary factors associated with each node,

attempt to select the root node based on the primary factors associated with each node, and

select 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.

13. A first node according to claim 12, wherein the ad hoc network comprises a current root node, and

wherein the receiver is configured to receive a message from the current root node, wherein each the message from the current root node comprises a number of primary factors associated with the current root node regarding capabilities of the current root node, and

wherein the processor is configured to compare the first primary factors associated with the first node to second primary factors associated with the current root node.

14. A first node according to claim 13, wherein the processor is configured to select a new root node based on a result of comparing the first primary factors to the second primary factors.

15. A first node according to claim 14, wherein the processor is configured to determine if a first root configuration status of the first node is greater than a second root configuration status of a current root node, and to select the current root node as the root node if the first root configuration status is less than the second root configuration status, to select the first node is the new root node if the first root configuration status is greater than the second root configuration status, and

wherein the processor is further configured to wait for an evaluation period before

attempting to select a new root node in the ad hoc network.

16. A first node according to claim 15, wherein, if the processor determines that the first root configuration status is the same as the second root configuration status, the processor is further configured to:

determine if a first power source of the first node is greater than a second power source of the current root node, select the current root node as the root node if the first power source is less than the second power source, and select the first node as the new root node if the first power source is greater than the second power source, and

wherein the processor is further configured to wait for an evaluation period before attempting to select a new root node in the ad hoc network.

17. A first node according to claim 16, wherein, if the processor determines that the first power source is the same as the second power source, then the processor is configured to determine if a first mobility status of the first node is less than a second mobility status of the current root node, and to:

select the current root node as the root node if the first mobility status is greater than the second mobility status, and

select the first node as the new root node if the first mobility status is less than the second mobility status, and

wherein the processor is further configured to wait for an evaluation period before attempting to select a new root node in the ad hoc network.

18. A first node according to claim 17, wherein, if the first mobility status of the first node is the same as the second mobility status of the current root node, the processor is configured to:

determine a first weighted metric associated with the first node and a second weighted metric associated with the current root node, wherein each weighted metric is determined based on an aggregate weighted value of secondary factors,

select the first node as the new root node if the first weighted metric is greater than the second weighted metric, and to select the current root node as the new root node if the first weighted metric is less than the second weighted metric, and

wait for an evaluation period before attempting to select a new root node in the ad hoc network.

19. A first node according to claim 18, 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.

20. A first node configured to select a root node in an ad hoc network comprising a current root node and a plurality of other nodes, the first node comprising:

a receiver configured to receive a message from the current root node, wherein the message from the current root node comprises a number of primary factors associated with the current root node regarding capabilities of the current root node, and at least one of a number of secondary factors associated with the current root node regarding capabilities of the current root node; and

a processor configured to;

compare the first primary factors associated with the first node to second primary factors associated with the current root node,

attempt to select a new root node based on a result of comparing the first primary factors to the second primary factors, and

select 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.

21. A first node according to claim 20, wherein the first primary factors comprise at least one of a first root configuration status, a first power source, and a first mobility status of the first node, and

wherein the second primary factors comprise at least one of a second root configuration status, a second power source, and a second mobility status of the current root node.

22. A first node according to claim 21, wherein the processor is configured to determine if at least one of:

the first root configuration status of the first node is greater than the second root configuration status of the current root node,

the first power source of the first node is greater than the second power source of the current root node, or

the first mobility status of the first node is less than the second mobility status of the current root node.

23. A first node according to claim 22, wherein the processor is configured to select the current root node as the root node if at least one of:

the first root configuration status is less than the second root configuration status,

the first power source is less than the second power source, or

the first mobility status is greater than the second mobility status.

24. A first node according to claim 23, wherein the processor is configured to select the first node is the new root node if at least one of:

the first root configuration status is greater than the second root configuration status,

the first power source is greater than the second power source, or

the first mobility status is less than the second mobility status.

25. A first node according to claim 22, wherein if the processor determines that the first root configuration status of the first node is equal to the second root configuration status of the current root node, that the first power source of the first node is equal to the second power source of the current root node, and the first mobility status of the first node is equal to the second mobility status of the current root node, wherein the processor is further configured to:

determine a first weighted metric associated with the first node and a second weighted metric associated with the current root node, wherein each weighted metric is determined based on an aggregate weighted value of secondary factors,

select the first node as the new root node if the first weighted metric is greater than the second weighted metric, and

select the current root node as the new root node if the first weighted metric is less than the second weighted metric.

26. A first node according to claim 25, 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.

27. A first node according to claim 25, wherein the secondary factors comprise at least two 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.

28. A first node according to claim 25, wherein the secondary factors comprise at least three 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.

29. A first node according to claim 20, wherein the processor is further configured to wait for an evaluation period before attempting to select a new root node in the ad hoc network.