Method and system for efficient network formation and maintenance of node routing databases in a mobile ad-hoc network

• US 7,787,450 B1
• Filed: 10/11/2006
• Issued: 08/31/2010
• Est. Priority Date: 10/11/2006
• Status: Expired due to Fees

• Current Assignee: Stingray IP Solutions LLC (Acacia Research Corporation)
• Original Assignee: ITT Manufacturing Enterprises, Inc. (ITT, Inc.)
• Inventors: Patel, Amit, Chan, Chi Chiu
• Primary Examiner(s): Ton, Dang T
• Assistant Examiner(s): Kaur, Pamit
• Application Number:
  US11/545,587
• Time in Patent Office: 1,420 Days
• Field of Search: 370/389, 370/236, 370/238
• US Class Current: 370/389
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/028 Dynamic adaptation of the update intervals, e.g. event-triggered updates
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update

Abstract

An efficient network formation technique for mobile ad-hoc wireless networks according to the present invention overcomes bandwidth overhead due to generation of database update or Link State Advertisement (LSA) messages in response to changes in certain parameters (e.g., node group size, etc.) with respect to both single and plural node group scenarios. The present invention controls flooding of LSA messages triggered by changes in these parameters (e.g., node group size), thereby reducing overhead traffic during network start-up. This is achieved without impact on message delivery capability and group merge operations. After network start-up is complete and the network is formed, the present invention continues to reduce LSA flooding in a mobile scenario when radios or nodes move into and out of range with one another.

Claims

1. A communication unit to transmit and receive information within a communications network and to control transference of said information to reduce network overhead traffic comprising:

a transmitter to transmit outgoing information to at least one other communication unit within said network;

a receiver to receive incoming information from at least one other communication unit within said network;

a storage unit to store routing information; and

a processor to control said transmission and reception of said outgoing and incoming information, wherein said processor includes;

a traffic control module to facilitate transmission of a network message based on occurrence of a first type of network condition indicating a change in at least one of routing and topology within said communications network and to selectively facilitate transmission of said network message in response to occurrence of a second type of network condition, wherein said network message includes an update message to synchronize said routing information within storage units of said communication units of said communications network, wherein transmission of said network message to synchronize said routing information is performed upon occurrence of said first type of network condition, wherein transmission of said network message to synchronize said routing information in response to occurrence of said second type of network condition is performed upon the earlier of expiration of a maximum allowable time interval for transmission of said network message and a rate of occurrence of said second type of network condition attaining a desired level, and wherein said traffic control module includes;

a rate compare module to compare a quantity of occurrences of said second type of network condition within a predetermined time interval to a rate threshold value to determine attainment of said desired level by said rate of occurrence.

2. The unit of claim 1, wherein said communications network includes an ad-hoc wireless network.

3. The unit of claim 1 further including:

a transmission timer to measure a predetermined time interval for transmissions; and

an interval timer to measure elapsed time;

wherein said processor further includes;

a recordation module to maintain a quantity of occurrences of said first and second types of network conditions and a quantity of expirations of said interval timer, wherein entries stored in said storage unit are associated with update messages received from other communication units and corresponding quantities of occurrence of said first and second types of network conditions; and

a retrieval module to retrieve entries from said storage unit associated with said received update messages.

4. The unit of claim 3, wherein said update message includes a Link State Advertisement.

5. The unit of claim 1, wherein said communications network includes at least one group each including at least one said communication unit, and wherein said second type of network condition includes a change in a size of a group.

6. The unit of claim 3, wherein said traffic control module includes:

a transmission module to examine each retrieved entry and to facilitate transmission of a corresponding update message in accordance with said quantity of occurrences of said first type of network condition associated with that entry indicating an occurrence of said first type of network condition.

7. The unit of claim 6, wherein said traffic control module further includes:

a delay transmission module to examine each retrieved entry and to selectively facilitate transmission of a corresponding update message in response to one of said expiration of said maximum allowable time interval and said rate of occurrence of said second type of network condition attaining said desired level.

8. The unit of claim 7, wherein said delay transmission module further includes:

a time compare module to compare said quantity of timer expirations to a timer threshold value to determine said expiration of said maximum allowable time interval.

9. The unit of claim 8, wherein said delay transmission module further includes said rate compare module, and wherein said rate compare module is configured to perform said determination of attainment of said desired level in response to determining that said maximum allowable time interval has not expired.

10. The unit of claim 3, wherein said processor further includes:

a reset module to reset said quantity of occurrences of said first and second types of network conditions and said quantity of interval timer expirations in response to transmission of said network message.

11. The unit of claim 1, wherein said incoming and outgoing information is in the form of Radio Frequency (RF) signals.

12. A method of controlling transference of information between a communication unit and other units within a communications network to reduce network traffic comprising:

(a) transmitting a network message from a communication unit upon occurrence of a first type of network condition indicating a change in at least one of routing and topology within said communications network, wherein said network message includes an update message to synchronize routing information within storage units of said communication units of said communications network; and

(b) selectively transmitting said network message from said communication unit in response to occurrence of a second type of network condition, wherein transmission of said network message to synchronize said routing information in response to occurrence of said second type of network condition is performed upon the earlier of expiration of a maximum allowable time interval for transmission of said network message and a rate of occurrence of said second type of network condition attaining a desired level, and wherein a quantity of occurrences of said second type of network condition within a predetermined time interval is compared to a rate threshold value to determine attainment of said desired level by said rate of occurrence.

13. The method of claim 12, wherein said communications network includes an ad-hoc wireless network.

14. The method of claim 12, wherein said communication unit includes:

a transmission timer to measure a predetermined time interval for transmissions; and

an interval timer to measure elapsed time;

wherein step (a) further includes;

(a.1) maintaining a quantity of occurrences of said first and second types of network conditions and a quantity of expirations of said interval timer, wherein entries stored in said storage unit are associated with update messages received from other communication units and corresponding quantities of occurrence of said first and second types of network conditions; and

(a.2) selectively retrieving entries from said storage unit associated with said received update messages.

15. The method of claim 14, wherein said update message includes a Link State Advertisement.

16. The method of claim 12, wherein said communications network includes at least one group each including at least one said communication unit, and wherein said second type of network condition includes a change in a size of a group.

17. The method of claim 14, wherein step (a) further includes:

(a.3) examining each retrieved entry and transmitting a corresponding update message in accordance with said quantity of occurrences of said first type of network condition associated with that entry indicating an occurrence of said first type of network condition.

18. The method of claim 17, wherein step (b) further includes:

(b.1) examining each retrieved entry and selectively transmitting a corresponding update message in response to one of said expiration of said maximum allowable time interval and said rate of occurrence of said second type of network condition attaining said desired level.

19. The method of claim 18, wherein step (b) further includes:

(b.1.1) comparing said quantity of timer expirations to a timer threshold value to determine said expiration of said maximum allowable time interval.

20. The method of claim 19, wherein step (b) further includes:

(b.1.2) determining attainment of said desired level in response to determining that said maximum allowable time interval has not expired.

21. The method of claim 14 further including:

(c) resetting said quantity of occurrences of said first and second types of network conditions and said quantity of interval timer expirations in response to transmission of said network message.

22. The method of claim 12, wherein said information transferred between said communication units is in the form of Radio Frequency (RF) signals.

23. A communications network comprising:

a plurality of communication units for transferring information therebetween, wherein each communication unit includes a storage unit to store routing information, wherein network messages are transmitted based on occurrence of a first type of network condition indicating a change in at least one of routing and topology within said communications network and selectively transmitted in response to occurrence of a second type of network condition, wherein said network message includes an update message to synchronize said routing information within storage units of said communication units of said communications network, wherein transmission of said network message to synchronize said routing information is performed upon occurrence of said first type of network condition, wherein transmission of said network messages to synchronize said routing information in response to occurrence of said second type of network condition is performed upon the earlier of expiration of a maximum allowable time interval for transmission of said network messages and a rate of occurrence of said second type of network condition attaining a desired level, and wherein said communication units compare a quantity of occurrences of said second type of network condition within a predetermined time interval to a rate threshold value to determine attainment of said desired level by said rate of occurrence.

24. The network of claim 23, wherein said communications network includes an ad-hoc wireless network.

25. The network of claim 23, wherein each communication unit further includes:

a transmission timer to measure a predetermined time interval for transmissions; and

an interval timer to measure elapsed time;

wherein said communication units maintain a quantity of occurrences of said first and second types of network conditions and a quantity of expirations of said interval timer, and entries stored in said storage unit are associated with update messages received from other communication units and corresponding quantities of occurrence of said first and second types of network conditions.

26. The network of claim 25, wherein said update message includes a Link State Advertisement.

27. The network of claim 23, wherein said communications network includes at least one group each including at least one said communication unit, and wherein said second type of network condition includes a change in a size of a group.

28. The network of claim 25, wherein said communication units examine each entry associated with a received update message within a corresponding storage unit and transmit a corresponding update message in accordance with said quantity of occurrences of said first type of network condition associated with that entry indicating an occurrence of said first type of network condition.

29. The network of claim 25, wherein said communication units examine each entry associated with a received update message within a corresponding storage unit and selectively transmit a corresponding update message in response to one of said expiration of said maximum allowable time interval and said rate of occurrence of said second type of network condition attaining said desired level.

30. The network of claim 29, wherein said communication units compare said quantity of timer expirations to a timer threshold value to determine said expiration of said maximum allowable time interval.

31. The network of claim 30, wherein said communication units determine attainment of said desired level in response to determining that said maximum allowable time interval has not expired.

32. The network of claim 25, wherein said communication units reset said quantity of occurrences of said first and second types of network conditions and said quantity of interval timer expirations in response to transmission of said network message.

33. The network of claim 23, wherein said transferred information is in the form of Radio Frequency (RF) signals.