Method and apparatus for broadcast in an AD HOC network with dynamic selection of relay nodes

• US 20070121521A1
• Filed: 11/30/2005
• Published: 05/31/2007
• Est. Priority Date: 11/30/2005
• Status: Active Grant

• Current Assignee: ARRIS Enterprises LLC (CommScope Holding Company, Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Joshi, Avinash, Kotzin, Michael, Muthuswamy, Sivakumar, D'Amico, Thomas
• Granted Patent: US 7,697,450 B2
• Time in Patent Office: Days
• US Class Current: 370/252
• CPC Class Codes: H04B 7/155 Ground-based stations H04B7/204 takes precedence
• CPC Class Codes: H04W 40/00 Communication routing or communication path finding
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

Techniques are provided for allowing a node (300) in an ad hoc network to deterministically decide whether to relay broadcast information to another node in the ad hoc network. The node (300) receives broadcast information and measures received signal strength (RSS) of the broadcast information. The node (300) may determine if the measured RSS is below a low threshold, and if so, can relay the broadcast information to neighbor nodes. Otherwise, the node (300) can also determine if the measured RSS is above a high threshold, and if not, wait for a waiting period before relaying the broadcast information to the neighbor nodes. The node (300) may dynamically adjust the low threshold by decreasing the low threshold as the number of neighbor nodes increases and may dynamically adjust the high threshold by increasing the high threshold as the number of neighbor nodes decreases.

Claims

1. A method for deterministically deciding whether to relay broadcast information to another node in an ad hoc network including a backbone network including at least one relay node, comprising:

receiving broadcast information;

measuring a received signal strength (RSS) of the broadcast information; and

deciding whether to relay the broadcast information based on the RSS of the broadcast information.

2. The method according to claim 1, wherein deciding whether to relay the broadcast information based on the RSS of the broadcast information, comprises:

determining if the measured RSS of the received broadcast information is below a low threshold.

3. The method according to claim 2, further comprising:

relaying the broadcast information to neighbor nodes if the measured RSS of the broadcast information is below the low threshold.

4. The method according to claim 2, further comprising:

dynamically adjusting the low threshold based on the number of neighbor nodes by decreasing the low threshold as the number of neighbor nodes increases.

5. The method according to claim 4, wherein decreasing the low threshold as the number of neighbor nodes increases, comprises:

monitoring the number of neighbor nodes;

decreasing the low threshold as a function of the number of neighbor nodes, wherein the low threshold decreases as the number of neighbor nodes increases to decrease the likelihood of collisions with broadcast information from other neighbors.

6. The method according to claim 5, further comprising:

determining whether broadcast information has been received within a time interval; and

attempting to repair the backbone network by discovering at least one intermediate node that has received the broadcast information within the time interval if the broadcast information is not received within the time interval.

7. The method according to claim 6, wherein attempting to repair the backbone network, comprises:

initiating route discovery through neighbor nodes to try to discover a route to an intermediate node that has received the broadcast information within a time interval; and

determining at least one intermediate node connected to a relay node if a route was found to an intermediate node that has received the broadcast information within a time interval; and

requesting that the intermediate node increase its value of the high threshold for a time period and thereafter incrementally decrease the increased value of high threshold during each subsequent time period.

8. The method according to claim 2, further comprising:

determining if the measured RSS of the broadcast information is below a high threshold if the measured RSS of the broadcast information is greater than or equal to the low threshold; and

waiting for a waiting period before relaying the broadcast information to the neighbor nodes if the measured RSS of the broadcast information is less than or equal to the high threshold to provide the node an opportunity to receive an indication from other neighbor nodes an that the broadcast information was received with a lower RSS during the waiting period; and

receiving broadcast information during the waiting period.

9. The method according to claim 8, further comprising:

dynamically adjusting the high threshold based on the number of neighbor nodes by increasing the high threshold as the number of neighbor nodes decreases.

10. The method according to claim 9, wherein increasing the high threshold as the number of neighbor nodes decreases, comprises:

monitoring the number of neighbor nodes;

increasing the high threshold as a function of the number of neighbor nodes, wherein the high threshold increases as the number of neighbor nodes decreases.

11. The method according to claim 10, further comprising:

determining whether broadcast information has been received within a time interval; and

attempting to repair the backbone network by discovering at least one intermediate node that has received the broadcast information within the time interval if the broadcast information is not received within the time interval.

12. The method according to claim 11, wherein attempting to repair the backbone network, comprises:

initiating route discovery through neighbor nodes to try to discover a route to an intermediate node that has received the broadcast information within a time interval; and

determining at least one intermediate node connected to a relay node if a route to an intermediate node that has received the broadcast information within a time interval was found and

requesting that the intermediate node increase its value of the high threshold for a time period and thereafter incrementally decrease the increased value of the high threshold during each subsequent time period.

13. The method according to claim 9, further comprising:

receiving other broadcast information if the measured RSS of the broadcast information is above the high threshold; and

measuring the RSS of the other broadcast information.

14. The method according to claim 9, wherein a duration of the waiting period is proportional to the measured RSS of the broadcast information.

15. The method according to claim 14, further comprising:

determining whether the same broadcast information was received during the waiting period with a RSS above the high threshold.

16. The method according to claim 15, further comprising:

canceling relay of the broadcast information if the same broadcast information was received during the waiting period with a RSS above the high threshold.

17. The method according to claim 15, further comprising:

relaying the broadcast information if the same broadcast information was not received during the waiting period with a RSS above the high threshold;

receiving another broadcast information; and

measuring the RSS of the other broadcast information.

18. A node configured to deterministically decide whether to relay broadcast information to another node in an ad hoc network, comprising:

a receiver configured to receive broadcast information; and

a processor configured to;

measure a received signal strength (RSS) of the broadcast information, and

decide whether to relay the broadcast information based on the RSS of the broadcast information.

19. The node according to claim 18, wherein the processor is further configured to:

determine if the measured RSS of the received broadcast information is below a low threshold, and

generate a relay command when the measured RSS of the broadcast information is below the low threshold, and further comprising;

a transmitter configured to receive the relay command and transmit the broadcast information to neighbor nodes.

20. The node according to claim 19, wherein the processor is further configured to monitor the number of neighbor nodes and to decrease the low threshold as the number of neighbor nodes increases.

21. The node according to claim 19, wherein the processor is further configured to:

determine if the measured RSS of the broadcast information is below a high threshold when the measured RSS of the broadcast information is greater than or equal to the low threshold, and

wait for a waiting period before relaying the broadcast information to the neighbor nodes when the measured RSS of the broadcast information is less than or equal to the high threshold, and

cancel the relay the broadcast information if the same information is received during the waiting period with a RSS above the high threshold.

22. The node according to claim 21, wherein the processor is further configured to monitor the number of neighbor nodes, determine whether broadcast information has been received within time interval, and increase the high threshold as a function of the number of neighbor nodes if the broadcast information is received within the time interval, wherein the high threshold increases as the number of neighbor nodes decreases.

23. The node according to claim 21, wherein the duration of the waiting period is proportional to the measured RSS of the broadcast information, and wherein the processor is further configured to determine whether the same broadcast information was received during the waiting period with a RSS above the high threshold, and

wherein the processor is further configured to cancel relay of the broadcast information if the same broadcast information was received during the waiting period with a RSS above the high threshold, and to relay the broadcast information if the same broadcast information was not received during the waiting period with a RSS above the high threshold.