Methods and devices for scheduling the transmission of packets in configurable access wireless networks that provide Quality-of-Service guarantees

• US 20060002341A1
• Filed: 06/30/2004
• Published: 01/05/2006
• Est. Priority Date: 06/30/2004
• Status: Abandoned Application

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Bejerano, Yigal, Kumar, Amit
• Application Number:
  US10/879,063
• Publication Number:
  US 20060002341A1
• Time in Patent Office: Days
• US Class Current: 370/329
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/46 Cluster building
• CPC Class Codes: H04W 40/10 based on available power or energy
• CPC Class Codes: H04W 72/543 based on requested quality, e.g. QoS
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

A more energy efficient, medium access control (MAC) layer of a multi-hop wireless network is provided using scheduling techniques which reduce packet collisions, and therefore the need for packet re-transmissions, while ensuring both bandwidth and delay, Quality-of-Service (QoS) guarantees. The techniques are used in conjunction with the formation of a multi-hop, configurable access wireless network (CAN).

Claims

1. A method for scheduling the transmission of packets in a configurable, Time Division, Multiple Access (TDMA) wireless network that ensures both bandwidth and delay Quality-of-Service (QoS) guarantees comprising:

dividing a time period into one or more superframes, each superframe consisting of a plurality of slots, each slot having a duration substantially equal to the time required to transmit a single packet; and

generating a packet transmission schedule for one or more wireless stations in the TDMA network such that only a single packet is transmitted during each slot assigned to each of the one or more stations to reduce collisions between transmitted packets.

2. The method as in claim 1 further comprising generating the schedules to provide both bandwidth and delay, QoS guarantees.

3. The method as in claim 1 further comprising generating a scheduling graph.

4. The method as in claim 3 further comprising:

identifying a Hamiltonian cycle in the scheduling graph; and

generating a schedule for one or more wireless stations in the TDMA network that allocates one or more slots to the one or more stations according to the identified cycle.

5. The method as in claim 1 further comprising:

identifying a Hamiltonian cycle, based on a scheduling graph representative of a cluster, C, of stations in the TDMA network such that each station, υ

, in the cluster is connected via one or more shortest paths to an access point, a, also in the cluster that meets an aggregated bandwidth demand Σ

<sub>v ε

C−

{a}</sub>d_v≦

W/2, where d_υ

is the demand of every station υ

in C and W is a wireless link capacity; and

generating packet transmission schedules for the one or more wireless stations in the TDMA network that allocate one or more slots to the one or more stations based on the identified cycle.

6. The method as in claim 5 further comprising:

modifying a scheduling graph by adding one or more additional slots to the superframe;

identifying a Hamiltonian cycle in the modified scheduling graph; and

generating packet transmission schedules for the one or more wireless stations in the TDMA network that allows the transmission of packets during each original and additional slot according to the identified cycle.

7. The method as in claim 5 further comprising:

modifying a scheduling graph by relaxing the aggregate bandwidth demand Σ

<sub>v ε

C−

{a}</sub>d_v≦

W/2;

identifying a Hamiltonian cycle in the modified scheduling graph; and

generating packet transmission schedules for the one or more wireless stations in the TDMA network that allows the transmission of packets during each slot according to the identified cycle.

8. A controller, for generating one or more packet transmission schedules for one or more wireless stations in a configurable TDMA wireless network that ensures both bandwidth and delay QoS guarantees, operable to:

divide a time period into one or more superframes, each superframe consisting of a plurality of slots, each slot having a duration substantially equal to the time required to transmit a single packet; and

generate a packet transmission schedule for one or more wireless stations in the TDMA network such that only a single packet is transmitted during each slot assigned to each of the one or more stations to reduce collisions between transmitted packets.

9. The controller as in claim 8 further operable to generate the schedules to provide both bandwidth and delay, QoS guarantees.

10. The controller as in claim 8 further operable to generate a scheduling graph.

11. The controller as in claim 10 further operable to:

identify a Hamiltonian cycle in the scheduling graph; and

generate a schedule for one or more wireless stations in the TDMA network that allocates one or more slots to the one or more stations according to the identified cycle.

12. The controller as in claim 8 further operable to:

identify a Hamiltonian cycle, based on a scheduling graph representative of a cluster, C, of stations in the TDMA network such that each station, υ

, in the cluster is connected via one or more shortest paths to an access point, a, also in the cluster that meets an aggregated bandwidth demand Σ

<sub>vε

C−

{a}</sub>d_v≦

W/2, where d_υ

is the demand of every station υ

in C and W is a wireless link capacity; and

generate packet transmission schedules for the one or more wireless stations in the TDMA network that allocate one or more slots to the one or more stations based on the identified cycle.

13. The controller as in claim 12 further operable to:

modify a scheduling graph by adding one or more additional slots to the superframe;

identify a Hamiltonian cycle in the modified scheduling graph; and

generate packet transmission schedules for the one or more wireless stations in the TDMA network that allows the transmission of packets during each original and additional slot according to the identified cycle.

14. The controller as in claim 12 further operable to:

modify a scheduling graph by relaxing the aggregate bandwidth demand Σ

<sub>vε

C−

{a}</sub>d_v≦

W/2;

identify a Hamiltonian cycle in the modified scheduling graph; and

generate packet transmission schedules for the one or more wireless stations in the TDMA network that allows the transmission of packets during each slot according to the identified cycle.

15. One or more wireless stations comprising a configurable, TDMA wireless network, each station operable to transmit only a single packet during each slot assigned to each of the one or more stations to reduce collisions between transmitted packets.

16. The one or more wireless stations as in claim 15 wherein each station is further operable to transmit the single packet during an allocated slot associated with an identified Hamiltonian cycle.

17. The one or more wireless stations as in claim 16, wherein the Hamiltonian cycle is identified based on a scheduling graph representative of a cluster, C, of wireless stations in the TDMA network such that each station, υ

, in the cluster is connected via one or more shortest paths to an access point, a, also in the cluster that meets an aggregated bandwidth demand Σ

<sub>vε

C−

{a}</sub>d_v≦

W/2, where d_υ

is the demand of every station υ

in C and W is a wireless link capacity.