Adaptive adjustment of backoff times in wireless network communications

• US 20040100936A1
• Filed: 11/26/2002
• Published: 05/27/2004
• Est. Priority Date: 11/26/2002
• Status: Active Grant

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Shoemake, Matthew B., Ho, Jin-Meng, Liu, Yonghe
• Granted Patent: US 7,209,467 B2
• Time in Patent Office: Days
• US Class Current: 370/345
• CPC Class Codes: H04W 74/006 in the downlink, i.e. towards the terminal
• CPC Class Codes: H04W 74/0833 Random access procedures, e.g. with 4-step access
• CPC Class Codes: H04W 74/085 collision avoidance
• CPC Class Codes: H04W 84/12 WLAN [Wireless Local Area Networks]

Abstract

A wireless network, including a plurality of network elements such as a wireless access point (9), and computer stations (2, 4, 6), is disclosed. The wireless network operates so that each network element (2, 4, 6, 9) waits for a pseudo-randomly selected duration, after the end of a frame on the channel, before initiating transmission. One of the network elements, such as the wireless access point (9), measures the performance of the network over a measurement period (T), and adjusts a minimum value of the upper limit of the range from which the random duration is selected, according to the performance of the network over the measurement period. The times measured may be the successful transmission time (T_s), which is maximized in adjusting the minimum value, or the idle and collision times (T_1,T_c), which are equated in the optimization of the minimum value.

Claims

1. A method of controlling network elements in a wireless network to schedule transmissions over a channel, comprising the steps of:

measuring a transmission time duration within a measurement period, the transmission time duration indicating results of transmissions over the channel in the measurement period;

adjusting a minimum value of a limit of a random number range responsive to the measured transmission time duration;

broadcasting the adjusted minimum value of the limit of the random number range to at least one other network element in the wireless network, wherein the adjusted minimum value of the limit of the random number range controls the random number range from which the at least one other network element selects a random number that determines when the at least one other network element initiates a transmission over the channel after the end of a prior transmission over the channel; and

repeating the measuring, adjusting, and broadcasting steps.

2. The method of claim 1, wherein the transmission time duration comprises a successful transmission time duration, the successful transmission time duration corresponding to the time during the measurement period during which successful transmissions occurred over the channel.

3. The method of claim 2, wherein the adjusting step comprises:

deriving a new minimum value of the limit of the random number range by modifying a prior minimum value of the limit of the random number range with a value corresponding to a product of a step length factor with a difference in most recent measured successful transmission time durations and with a difference in most recent minimum values of the limit of the random number range.

4. The method of claim 3, further comprising:

after the measuring step and before the adjusting step, filtering the measured successful transmission time duration, by adjusting the measured successful transmission time duration with a value corresponding to a product of a forgetting factor with a difference in most recent measured successful transmission time durations;

wherein the adjusting step uses the filtered measured successful transmission time duration.

5. The method of claim 1, wherein the transmission time duration comprises a collision time duration corresponding to the time during the measurement period during which colliding transmissions occurred over the channel, and an idle time duration corresponding to the time during the measurement period during which no transmissions occurred over the channel.

6. The method of claim 5, wherein the adjusting step comprises:

deriving a new minimum value of the limit of the random number range by modifying a prior minimum value of the limit of the random number range with a value corresponding to a product of a step length factor with a difference between the measured collision time duration and the measured idle time duration.

7. The method of claim 6, further comprising:

after the measuring step and before the adjusting step, filtering the measured collision time duration, by adjusting the measured collision time duration with a value corresponding to a product of a forgetting factor with a difference in most recent measured collision time durations; and

after the measuring step and before the adjusting step, filtering the measured idle time duration, by adjusting the measured idle time duration with a value corresponding to a product of a forgetting factor with a difference in most recent measured idle time durations;

wherein the adjusting step uses the filtered measured collision and idle time durations.

8. The method of claim 1, wherein the measuring, adjusting, broadcasting, and repeating steps are performed by a wireless access point in the wireless network.

9. The method of claim 8, further comprising:

operating at least one network element in the network to transmit a frame over the channel, by performing a sequence of operations comprising;

preparing a frame for transmission over the channel;

probing the channel to determine whether it is busy or available;

responsive to the probing step determining that the channel is busy with a current frame, waiting for completion of an interframe space after the completion of the current frame;

receiving the broadcast adjusted minimum value of the limit of the random number range;

then selecting a pseudo-random value within the random number range having a limit at the adjusted minimum value of the limit of the random number range;

storing the selected pseudo-random value in a counter;

incrementing the counter until it reaches a terminal value; and

responsive to the counter reaching a terminal value, initiating transmission of the prepared frame over the channel.

10. The method of claim 9, wherein the adjusted minimum value of the limit of the random number range is an upper limit of the random number range;

wherein the incrementing step counts the counter down toward a terminal value of zero;

and further comprising;

after the counting down step, probing the channel to determine whether it is busy or available;

responsive to the probing step determining that the channel is busy, increasing the upper limit of the random number range; and

then repeating the selecting, storing, and counting down steps.

11. The method of claim 10, further comprising:

responsive to the probing step determining that the channel is busy, and prior to the increasing step, comparing the upper limit of the random number range to a maximum value of the upper limit of the random number range; and

responsive to the comparing step indicating that the upper limit of the random number range is equal to the maximum value of the upper limit, then repeating the selecting, storing, and counting down steps without performing the increasing step.

12. The method of claim 11, further comprising:

responsive to receiving the adjusted minimum value of the limit of the random number range, adjusting the maximum value of the upper limit of the random number range responsive to the adjusted minimum value.

13. A wireless network element, comprising:

RF circuitry, for transmitting and receiving wireless signals;

media access control and physical layer circuitry, coupled to the RF circuitry, for processing signals to be transmitted by the RF circuitry as radio signals, and for processing radio signals received by the RF circuitry;

interface circuitry;

programmable logic, coupled to the media access control and physical layer circuitry, and to the interface circuitry, for executing program instructions; and

program memory, for storing program instructions to be executed by the programmable logic, including a sequence of program instructions for controlling the scheduling of transmissions over a wireless network channel, the sequence comprising the steps of;

measuring a transmission time duration within a measurement period, the transmission time duration indicating results of transmissions over the channel in the measurement period;

adjusting a minimum value of a limit of a random number range responsive to the measured transmission time duration;

broadcasting the adjusted minimum value of the limit of the random number range to at least one other network element in the wireless network, wherein the adjusted minimum value of the limit of the random number range controls the random number range from which the at least one other network element selects a random number that determines when the at least one other network element initiates a transmission over the channel after the end of a prior transmission over the channel; and

repeating the measuring, adjusting, and broadcasting steps.

14. The wireless network element of claim 13, wherein the transmission time duration comprises a successful transmission time duration, the successful transmission time duration corresponding to the time during the measurement period during which successful transmissions occurred over the channel.

15. The wireless network element of claim 14, wherein the adjusting step comprises:

deriving a new minimum value of the limit of the random number range by modifying a prior minimum value of the limit of the random number range with a value corresponding to a product of a step length factor with a difference in most recent measured successful transmission time durations and with a difference in most recent minimum values of the limit of the random number range.

16. The wireless network element of claim 15, wherein the sequence of operations further comprises:

after the measuring step and before the adjusting step, filtering the measured successful transmission time duration, by adjusting the measured successful transmission time duration with a value corresponding to a product of a forgetting factor with a difference in most recent measured successful transmission time durations;

wherein the adjusting step uses the filtered measured successful transmission time duration.

17. The wireless network element of claim 13, wherein the transmission time duration comprises a collision time duration corresponding to the time during the measurement period during which colliding transmissions occurred over the channel, and an idle time duration corresponding to the time during the measurement period during which no transmissions occurred over the channel.

18. The wireless network element of claim 17, wherein the adjusting step comprises:

deriving a new minimum value of the limit of the random number range by modifying a prior minimum value of the limit of the random number range with a value corresponding to a product of a step length factor with a difference between the measured collision time duration and the measured idle time duration.

19. The wireless network element of claim 18, wherein the sequence of operations further comprises:

after the measuring step and before the adjusting step, filtering the measured collision time duration, by adjusting the measured collision time duration with a value corresponding to a product of a forgetting factor with a difference in most recent measured collision time durations; and

after the measuring step and before the adjusting step, filtering the measured idle time duration, by adjusting the measured idle time duration with a value corresponding to a product of a forgetting factor with a difference in most recent measured idle time durations;

wherein the adjusting step uses the filtered measured collision and idle time durations.

20. The wireless network element of claim 13, wherein the wireless network element is a wireless access point;

and wherein the interface circuitry comprises a network transceiver, for communicating signals to and from a network backbone.