Scheduling packet flows in multi-rate wireless local area networks

• US 7,403,488 B2
• Filed: 02/17/2004
• Issued: 07/22/2008
• Est. Priority Date: 02/17/2004
• Status: Expired due to Fees

• Current Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Inventors: Zhang, Jinyun, Gu, Daqing, Yuan, Yuan
• Primary Examiner(s): Ohgad; Edan
• Assistant Examiner(s): LEE, ANDREW CHUNG CHEUNG
• Application Number:
  US10/780,357
• Publication Number:
  US 20050180444A1
• Time in Patent Office: 1,617 Days
• Field of Search: 370/252, 370/338, 370/328, 370/329, 370/330, 370/337, 370/238, 370/230, 370/237, 455436-443
• US Class Current: 370/252
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/522 Dynamic queue service slot or variable bandwidth allocation
• CPC Class Codes: H04L 47/564 Attaching a deadline to packets, e.g. earliest due date first
• CPC Class Codes: H04L 47/6265 past bandwidth allocation
• 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/22 Negotiating communication rate
• CPC Class Codes: H04W 72/535 based on resource usage policies
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]
• CPC Class Codes: H04W 84/12 WLAN [Wireless Local Area Networks]

Abstract

A system and method schedule series of packets for transmission between terminals in a single wireless channel of a packet-switched local area network. The local area network can operate in an ad hoc mode or in infrastructure mode. A transmission rate is assigned to each of the terminals. The terminals can be mobile. Different terminals can be assigned different transmission rates, depending on a quality of the channel. That is, terminals transmitting via an error-free channel are assigned a higher transmission rate than terminals transmitting via an error-prone channel. Then, the series of packets are scheduled for transmission between the terminals such that each terminal receives a substantially equal amount of transmission time over an extended period of time.

Claims

1. A method for scheduling a plurality of series of packets for transmission between a plurality of terminals in a single wireless channel of a packet-switched local area network, comprising:

assigning a transmission rate to each of a plurality of terminals;

assigning a start tag S_k^ƒ

=max {V (A(t_k^ƒ

)), F<sub>k−

1</sub>⁷¹ }and a finish tag F_k^ƒ

=S_k^ƒ

+L_p/(r<sub>ƒ

·

Cƒ</sub>

(t)) to each packet, where k is a sequence number of the packet, in a particular series of packets ƒ

, A(t_k^ƒ

) is an arrival time of the packet, L_p is a size of the packet in bits, V(·

) is a virtual time for the start tag, rƒ

is a base transmission rate, and C_ƒ

(t) is a current transmission rate; and

scheduling the series of packets for transmission between the terminals such that each terminal receives a substantially equal amount of transmission time over an extended period of time.

2. The method of claim 1, in which the local area network operate in an ad hoc mode.

3. The method of claim 1, in which the local area network operates is in an infrastructure mode.

4. The method of claim 1, further comprising:

assigning different transmission rates to the plurality of terminals such that at least one terminal is transmitting at a different rate than all other terminals.

5. The method of claim 1, in which some of the plurality of terminals are mobile.

6. The method of claim 1, in which the assigned transmission rate is dependent on a quality of the channel.

7. The method of claim 6, in which a particular terminal transmitting via an error-free channels is assigned a higher transmission rate than another terminal transmitting via an error-prone channel.

8. The method of claim 1, further comprising:

normalizing the current transmission rate with respect to the base transmission rate.

9. The method of claim 1, further comprising:

scheduling the particular packet with a smallest start tag to transmit first.

10. The method of claim 1, further comprising:

associating a credit counter E_ƒ

(t) with each series of packets ƒ

such that when E<sub>ƒ

(t) ></sub>

0 the series of packets is leading, and when E<sub>ƒ

(t) <</sub>

0 the series of packets is lagging, where t is a time unit.

11. The method of claim 10, further comprising:

incrementing the credit counter for a particular leading series of packets by a number of time units relinquished by a particular lagging series of packets while decrementing the credit counter of the particular lagging series of packets by the number of time units.

12. The method of claim 11, in which the time units are expressed in terms of transmitted bytes, normalized with respect to the transmission rate.

13. The method of claim 11, further comprising:

relinquishing time units from a selected leading series of packets having a maximum credit counter to lagging series of packets.

14. The method of claim 13, in which the time units are relinquished to the lagging series of packets proportional to normalized credit counters of the lagging series of packets.

15. The method of claim 1, further comprising:

estimating a state of the channel in each terminal to determine whether the terminal schedules packets for transmission.

16. The method of claim 1, in which scheduling mechanism is implemented with a hybrid coordinator according to an IEEE 802.11e standard.

17. A system for scheduling a plurality of series of packets for transmission between a plurality of terminals in a single wireless channel of a packet-switched local area network, comprising:

an error-free service model configured to define ideal packet flows that transmit at different rates over an error-free channel;

a lead and lag model configured to determine leading packet flows and lagging packet flows, and to determine amounts of leading and amounts of lagging for the leading packet flows and the lagging packet flows, respectively; and

a compensation model configured to compensate the lagging packet flows at an expense of the leading packet flows; and

means for scheduling the series of packets for transmission between the terminals such that each terminal receives a substantially equal amount of transmission time over an extended period of time.

18. The system of claim 17, further comprising:

a channel estimation module; and

a channel access module.

19. A system for scheduling a plurality of series of packets for transmission between a plurality of terminals in a single wireless channel of a packet-switched local area network, comprising:

means for assigning a transmission rate to each of a plurality of terminals;

means for assigning a start tag S_k^ƒ

=max {V (A(t_k^ƒ

)), F<sub>k−

1</sub>^ƒ

}and a finish tag F_k^ƒ

=S_k^ƒ

+L_p/(r_ƒ

·

C_ƒ

(t)) to each packet, where k is a sequence number of the packet, in a particular series of packets ƒ

, A(t_k^ƒ

) is an arrival time of the packet, L_p is a size of the packet in bits, V(·

) is a virtual time for the start tag, r_ƒ

is a base transmission rate, and C_ƒ

(t) is a current transmission rate; and

means for scheduling the series of packets for transmission between the terminals such that each terminal receives a substantially equal amount of transmission time over an extended period of time.