Method and Apparatus for Early Warning of Congestion in Ad-Hoc Wireless Networks

• US 20110044169A1
• Filed: 04/07/2008
• Published: 02/24/2011
• Est. Priority Date: 04/07/2008
• Status: Active Grant

• Current Assignee: Stingray IP Solutions LLC (Acacia Research Corporation)
• Original Assignee: ITT Manufacturing Enterprises, Inc. (ITT, Inc.)
• Inventors: Liu, Yu-Jih
• Granted Patent: US 8,089,884 B2
• Time in Patent Office: Days
• US Class Current: 370/235
• CPC Class Codes: H04L 45/026 Details of "hello" or keep-alive messages
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04W 28/021 in wireless networks with changing topologies, e.g. ad-hoc networks self-organizing networks H04W84/18
• CPC Class Codes: H04W 28/0231 based on communication conditions dynamic wireless traffic scheduling definition based on channel quality criteria H04W72/54
• CPC Class Codes: H04W 28/0284 detecting congestion or overload during communication monitoring arrangements H04L43/00
• CPC Class Codes: H04W 40/248 Connectivity information update
• CPC Class Codes: H04W 40/30 for proactive routing
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]

Abstract

The present invention embodiments bypass congested links in a multi-hop Ad-Hoc wireless network. Initially, congestion is measured at each network node based on channel utilization for both transmission and reception of TDMA and CSMA messages. The measured utilization is quantized to conserve transmission bandwidth. Non-uniform quantization is applied to enable the measured utilization to be quantized to the highest value within the quantization range prior to occurrence of congestion, thereby effectively providing early notification of the congestion. The quantized utilization is distributed with the original use costs of a communication link to the remaining network nodes by a Link State Advertisement (LSA) flood and supplemental ACK and/or HELLO packets. After a network node receives the quantized utilization, the link cost is updated and used to select a routing path that minimizes the total costs from the source node to the destination node for a multi-hop network.

Claims

1. A communication unit to transmit and receive information within a communications network and to measure congestion 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; and

a processor to control said transmission and reception of said outgoing and incoming information, wherein said information is conveyed within a series of time slots and said processor includes;

a congestion module to determine a congestion value for said communication unit based on an amount of utilization of said time slots for communication within a predetermined time interval; and

a transmission module to facilitate transmission of said determined congestion value to at least one other communication unit within said network.

2. The communication unit of claim 1, wherein said network employs a plurality of communication protocols, and said congestion module includes:

a protocol module to determine an amount of time slot utilization for each communication protocol, wherein said protocol utilization amounts are combined to produce said utilization amount for communication.

3. The communication unit of claim 2, wherein said protocol module includes:

a utilization module to determine an amount of time slot utilization for respective transmissions and receptions of information for each communication protocol, wherein said utilization amounts for transmission and reception for each communication protocol are combined to produce said utilization amount for that protocol.

4. The communication unit of claim 2, wherein said communication protocols include Time Division Multiple Access (TDMA) and Carrier Sense Multiple Access (CSMA).

5. The communication unit of claim 4, wherein said CSMA protocol includes control packets and data packets, and said protocol module includes:

a CSMA module to determine an amount of time slot utilization for respective control packets and data packets, wherein said utilization amounts for said control and data packets are combined to produce said utilization amount for said CSMA protocol.

6. The communication unit of claim 1, wherein said processor further includes:

a quantization module to quantize said amount of utilization for communication to a value within a quantization range, wherein said congestion value is based on said quantized utilization.

7. The communication unit of claim 6, wherein said quantization module includes:

a quantization level module to apply a non-uniform quantization to said amount of utilization to produce said quantized utilization within said quantization range, wherein said non-uniform quantization includes at least two quantization steps with different values.

8. The communication unit of claim 7, wherein said non-uniform quantization produces said quantized utilization with a value within said quantization range representing the presence of congestion prior to said amount of utilization indicating actual occurrence of congestion to provide early notification of said congestion.

9. The communication unit of claim 6, wherein said processor further includes:

an encode module to encode said quantized utilization to produce said congestion value for transference to at least one other communication unit within said network.

10. The communication unit of claim 1, wherein said transmission module transmits said congestion value within one or more of a database update packet, a neighbor discovery packet and an acknowledgment packet.

11. The communication unit of claim 1, wherein said processor further includes:

a cost module to determine a cost for a communication link associated with said communication unit based on a product of a quantized utilization amount and a current cost to update a routing table within said communication unit with said determined cost.

12. The communication unit of claim 1, wherein said processor further includes:

a reception module to receive said congestion value from another communication unit, to determine a cost for a communication link associated with said other communication unit based on a product of a current cost and a quantized utilization amount within said received congestion value, and to update a routing table within said communication unit with said determined cost.

13. The communication unit of claim 12, wherein said processor further includes:

a routing module to determine a path through said network avoiding congested communication units for transmission of information by selecting said path through said network based on a minimum cost from a source to a destination.

14. The communication unit of claim 1, wherein said incoming and outgoing information are in the form of radio signals.

15. The communication unit of claim 1, wherein said network includes a wireless Ad-Hoc communications network.

16. A method of measuring congestion of a communication unit within a communications network and enabling other communication units to avoid congested communication units, wherein information is conveyed in said network within a series of time slots, said method comprising:

(a) determining a congestion value for said communication unit based on an amount of utilization of said time slots for communication within a predetermined time interval; and

(b) transmitting said determined congestion value to at least one other communication unit within said network.

17. The method of claim 16, wherein said network employs a plurality of communication protocols, and step (a) further includes:

(a.1) determining an amount of time slot utilization for each communication protocol, wherein said protocol utilization amounts are combined to produce said utilization amount for communication.

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

(a.1.1) determining an amount of time slot utilization for respective transmissions and receptions of information for each communication protocol, wherein said utilization amounts for transmission and reception for each communication protocol are combined to produce said utilization amount for that protocol.

19. The method of claim 17, wherein said communication protocols include Time Division Multiple Access (TDMA) and Carrier Sense Multiple Access (CSMA).

20. The method of claim 19, wherein said CSMA protocol includes control packets and data packets, and step (a.1) further includes:

(a.1.1) determining an amount of time slot utilization for respective control packets and data packets, wherein said utilization amounts for said control and data packets are combined to produce said utilization amount for said CSMA protocol.

21. The method of claim 16, wherein step (a) further includes:

(a.1) quantizing said amount of utilization for communication to a value within a quantization range, wherein said congestion value is based on said quantized utilization.

22. The method of claim 21, wherein step (a.1) further includes:

(a.1.1) applying a non-uniform quantization to said amount of utilization to produce said quantized utilization within said quantization range, wherein said non-uniform quantization includes at least two quantization steps with different values.

23. The method of claim 22, wherein said non-uniform quantization produces said quantized utilization with a value within said quantization range representing the presence of congestion prior to said amount of utilization indicating actual occurrence of congestion to provide early notification of said congestion.

24. The method of claim 21, wherein step (a) further includes:

(a.2) encoding said quantized utilization to produce said congestion value for transference to at least one other communication unit within said network.

25. The method of claim 16, wherein step (b) further includes:

(b.1) transmitting said congestion value within one or more of a database update packet, a neighbor discovery packet and an acknowledgment packet.

26. The method of claim 16, wherein step (a) further includes:

(a.1) determining a cost for a communication link associated with said communication unit based on a product of a quantized utilization amount and a current cost and updating a routing table within said communication unit with said determined cost.

27. The method of claim 16, further including:

(c) receiving said congestion value from another communication unit;

(d) determining a cost for a communication link associated with said other communication unit based on a product of a current cost and a quantized utilization amount within said received congestion value; and

(e) updating a routing table within said communication unit with said determined cost.

28. The method of claim 27, further including:

(f) determining a path through said network avoiding congested communication units for transmission of information by selecting said path through said network based on a minimum cost from a source to a destination.

29. The method of claim 16, wherein said communication unit transmits and receives information in the form of radio signals.

30. The method of claim 16, wherein said network includes a wireless Ad-Hoc communications network.

31. A communications network comprising:

a plurality of communication units for transferring information therebetween, wherein said information is conveyed within a series of time slots, and wherein said communication units each determine a respective congestion value based on a corresponding amount of utilization of said time slots for communication within a predetermined time interval and transmit said congestion value to other communication units in order to avoid congested communication units within said network.

32. The communications network of claim 31, wherein said network employs a plurality of communication protocols, and said communication units each determine a corresponding amount of time slot utilization for each communication protocol, wherein said protocol utilization amounts are combined to produce said corresponding utilization amount for communication.

33. The communications network of claim 32, wherein said communication units each determine a corresponding amount of time slot utilization for respective transmissions and receptions of information for each communication protocol, wherein said utilization amounts for transmission and reception for each communication protocol are combined to produce said utilization amount for that protocol.

34. The communications network of claim 32, wherein said communication protocols include Time Division Multiple Access (TDMA) and Carrier Sense Multiple Access (CSMA).

35. The communications network of claim 34, wherein said CSMA protocol includes control packets and data packets, and said communication units each determine a corresponding amount of time slot utilization for respective control packets and data packets, wherein said utilization amounts for said control and data packets are combined to produce said utilization amount for said CSMA protocol.

36. The communications network of claim 31, wherein said communication units each quantize said corresponding amount of utilization for communication to a value within a quantization range, wherein said respective congestion value is based on said quantized utilization.

37. The communications network of claim 36, wherein said communication units each apply a non-uniform quantization to said corresponding amount of utilization to produce said quantized utilization within said quantization range, wherein said non-uniform quantization includes at least two quantization steps with different values.

38. The communications network of claim 37, wherein said non-uniform quantization produces said quantized utilization with a value within said quantization range representing the presence of congestion prior to said corresponding amount of utilization indicating actual occurrence of congestion to provide early notification of said congestion.

39. The communications network of claim 36, wherein said communication units each encode a corresponding quantized utilization to produce said respective congestion value for transference to other communication units within said network.

40. The communications network of claim 31, wherein said communication units each transmit said respective congestion value within one or more of a database update packet, a neighbor discovery packet and an acknowledgment packet.

41. The communications network of claim 31, wherein said communication units each determine a cost for a communication link associated with that communication unit based on a product of a quantized utilization amount and a current cost and update a routing table within said communication unit with said determined cost.

42. The communications network of claim 31, wherein said communication units each receive said congestion value from another communication unit, determine a cost for a communication link associated with said other communication unit based on a product of a current cost and a quantized utilization amount within said received congestion value, and update a routing table within said communication unit with said determined cost.

43. The communications network of claim 42, wherein said communication units each determine a path through said network avoiding congested communication units for transmission of information by selecting said path through said network based on a minimum cost from a source to a destination.

44. The communications network of claim 31, wherein said transferred information is in the form of radio signals.

45. The communications network of claim 31, wherein said network includes a wireless Ad-Hoc communications network.