Method and apparatus for scheduling data packet transmission over a multihop wireless backhaul network

• US 7,366,178 B2
• Filed: 09/13/2005
• Issued: 04/29/2008
• Est. Priority Date: 09/13/2005
• Status: Expired due to Fees

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Zhang, Yihao Lisa, Wilfong, Gordon Thomas, Narlikar, Girija J., Lee, Seungjoon
• Primary Examiner(s): Trost, William
• Assistant Examiner(s): Ewart, James D
• Application Number:
  US11/225,516
• Publication Number:
  US 20070058604A1
• Time in Patent Office: 959 Days
• Field of Search: 370/321, 370/329, 370/345, 370347-349, 370/395.4, 370/431, 370/437, 370/442, 370/458, 370/468, 455/450, 455/451, 455/453, 455/464
• US Class Current: 370/395.4
• CPC Class Codes: H04W 72/0446 Resources in time domain, e.g. slots or frames
• CPC Class Codes: H04W 84/22 with access to wired networks

Abstract

A method and apparatus for scheduling the transmission of data packets over a multihop wireless backhaul network in which delay guarantees through the network may be advantageously ensured. Illustratively, a novel packet scheduling scheme is provided which is advantageously based on an existing scheduling policy for wireline networks and for which a delay guarantee (based on the delay characteristics of the existing scheduling policy) can be advantageously ensured. In one embodiment, an even-odd link activation framework is defined for a given multihop wireless backhaul network, and an associated scheduling policy based on an arbitrary existing scheduling policy for wireline networks is derived and adopted. In such a case, the derived scheduling policy, when applied to the given multihop wireless backhaul network, advantageously ensures a worst-case delay guarantee of approximately twice that of the existing scheduling policy for wireline networks.

Claims

1. A method for communicating data packets over a period of time in a wireless communications network, the wireless communications network comprising a plurality of nodes for transmitting data packets to and receiving data packets from other ones of said plurality of nodes, the plurality of nodes comprising at least a first subset of said nodes and a second subset of said nodes wherein said first subset of said nodes and said second subset of said nodes are disjoint sets, the period of time being divided into a plurality of non-overlapping time slots, the method comprising the steps of:

(a) transmitting, during a first one of said time slots, one or more of said data packets from one or more of said nodes in said first subset of said nodes, each of said data packets transmitted from said nodes in said first subset of nodes being transmitted to and being received by one of said nodes in said second subset of nodes, wherein

(i) each of said nodes in said first subset of nodes transmitting one or more data packets during said first one of said time slots does not receive any data packets from any nodes comprised in said wireless communications network during said first one of said time slots,

(ii) each of said nodes in said second subset of nodes receiving one or more data packets during said first one of said time slots does not transmit any data packets to any nodes comprised in said wireless communications network during said first one of said time slots,

(iii) at least one of said nodes in said first subset of nodes transmits, during said first one of said time slots, a plurality of data packets to a corresponding plurality of said nodes in said second subset of nodes using a different subchannel for each of said nodes in said second subset of nodes to which said at least one of said nodes in said first subset of nodes transmits one or more data packets, and

(iv) at least one of said nodes in said second subset of nodes receives, during said first one of said time slots, a plurality of data packets from a corresponding plurality of said nodes in said first subset of nodes using a different subchannel for each of said nodes in said first subset of nodes from which said at least one of said nodes in said second subset of nodes receives one or more data packets; and

(b) transmitting, during a second one of said time slots subsequent to said first one of said time slots, one or more of said data packets from one or more of said nodes in said second subset of said nodes, each of said data packets transmitted from said nodes in said second subset of nodes being transmitted to and being received by one of said nodes in said first subset of nodes, wherein

(i) each of said nodes in said second subset of nodes transmitting one or more data packets during said second one of said time slots does not receive any data packets from any nodes comprised in said wireless communications network during said second one of said time slots,

(ii) each of said nodes in said first subset of nodes receiving one or more data packets during said second one of said time slots does not transmit any data packets to any nodes comprised in said wireless communications network during said second one of said time slots,

(iii) at least one of said nodes in said second subset of nodes transmits, during said second one of said time slots, a plurality of data packets to a corresponding plurality of said nodes in said first subset of nodes using a different subchannel for each of said nodes in said first subset of nodes to which said at least one of said nodes in said second subset of nodes transmits one or more data packets during said second one of said time slots, and

(iv) at least one of said nodes in said first subset of nodes receives, during said second one of said time slots, a plurality of data packets from a corresponding plurality of said nodes in said second subset of nodes using a different subchannel for each of said nodes in said second subset of nodes from which said at least one of said nodes in said first subset of nodes receives one or more data packets during said second one of said time slots.

2. The method of claim 1 wherein said first subset of nodes and said second subset of nodes together comprise all of said plurality of nodes in said wireless communications network.

3. The method of claim 1 wherein said plurality of non-overlapping time slots are continuous in time, and wherein steps (a) and (b) are each repeated in turn within successive time slots throughout said period of time, such that step (a) is performed within successively odd numbered timeslots and step (b) is performed within successively even numbered timeslots.

4. The method of claim 1 further comprising the step of:

(c) transmitting, during a third one of said time slots subsequent to at least said first one of said time slots, one or more of said data packets from one or more of said nodes in one of said first or second subset of said nodes which transmits one or more data packets to one or more nodes in said other one of said first or second subset of said nodes during one of said first or second ones of said time slots, to one or more other nodes in said other one of said first or second subset of nodes,

wherein said plurality of non-overlapping time slots are continuous in time, and wherein said steps (a), (b) and (c) are each repeated in a given order over said plurality of said time slots throughout said period of time.

5. The method of claim 1 wherein said data packets transmitted by said nodes in said first subset of nodes during said first time slot and said data packets transmitted by said nodes in said second subset of nodes during said second time slot are scheduled based on a predetermined wireline network scheduling policy.

6. The method of claim 5 wherein said data packets transmitted by said nodes in said first subset of nodes during said first time slot and said data packets transmitted by said nodes in said second subset of nodes during said second time slot are scheduled based on said predetermined wireline network scheduling policy as applied to an imaginary wireline network topology based on a topology of said wireless communications network.

7. The method of claim 6 wherein

(i) each of said plurality of non-overlapping time slots are continuous and of a predetermined length of time,

(ii) steps (a) and (b) are continuously repeated in order throughout said period of time,

(iii) said data packets transmitted by said nodes in said first subset of nodes are scheduled to be transmitted in a selected one of said repetitions of step (a) based on when said data packets would have been scheduled to be transmitted by corresponding ones of said nodes in said first subset of nodes in said imaginary wireline network topology in accordance with said predetermined wireline network scheduling policy as applied to said imaginary wireline network topology, and

(iv) said data packets transmitted by said nodes in said second subset of nodes are scheduled to be transmitted in a selected one of said repetitions of step (b) based on when said data packets would have been scheduled to be transmitted by corresponding ones of said nodes in said second subset of nodes in said imaginary wireline network topology in accordance with said predetermined wireline network scheduling policy as applied to said imaginary wireline network topology.

8. The method of claim 1 wherein said wireless communications network comprises a mutihop wireless backhaul network, wherein one of said nodes comprised therein comprises a gateway to a wireline network, and wherein one or more of all other nodes comprised therein comprise wireless access points thereof.

9. The method of claim 8 wherein the wireline network comprises the Internet.

10. The method of claim 8 wherein the wireless communications network communicates with use of a WiMAX communications protocol.

11. A wireless communications network for communicating data packets over a period of time divided into a plurality of non-overlapping time slots, the wireless communications network comprising:

a plurality of nodes for transmitting data packets to and receiving data packets from other ones of said plurality of nodes, the plurality of nodes comprising at least a first subset of said nodes and a second subset of said nodes wherein said first subset of said nodes and said second subset of said nodes are disjoint sets;

means for transmitting, during a first one of said time slots, one or more of said data packets from one or more of said nodes in said first subset of said nodes, each of said data packets transmitted from said nodes in said first subset of nodes being transmitted to and being received by one of said nodes in said second subset of nodes, wherein

(i) each of said nodes in said first subset of nodes transmitting one or more data packets during said first one of said time slots does not receive any data packets from any nodes comprised in said wireless communications network during said first one of said time slots,

(ii) each of said nodes in said second subset of nodes receiving one or more data packets during said first one of said time slots does not transmit any data packets to any nodes comprised in said wireless communications network during said first one of said time slots,

(iii) at least one of said nodes in said first subset of nodes transmits, during said first one of said time slots, a plurality of data packets to a corresponding plurality of said nodes in said second subset of nodes using a different subchannel for each of said nodes in said second subset of nodes to which said at least one of said nodes in said first subset of nodes transmits one or more data packets, and

(iv) at least one of said nodes in said second subset of nodes receives, during said first one of said time slots, a plurality of data packets from a corresponding plurality of said nodes in said first subset of nodes using a different subchannel for each of said nodes in said first subset of nodes from which said at least one of said nodes in said second subset of nodes receives one or more data packets; and

means for transmitting, during a second one of said time slots subsequent to said first one of said time slots, one or more of said data packets from one or more of said nodes in said second subset of said nodes, each of said data packets transmitted from said nodes in said second subset of nodes being transmitted to and being received by one of said nodes in said first subset of nodes, wherein

(i) each of said nodes in said second subset of nodes transmitting one or more data packets during said second one of said time slots does not receive any data packets from any nodes comprised in said wireless communications network during said second one of said time slots,

(ii) each of said nodes in said first subset of nodes receiving one or more data packets during said second one of said time slots does not transmit any data packets to any nodes comprised in said wireless communications network during said second one of said time slots,

(iii) at least one of said nodes in said second subset of nodes transmits, during said second one of said time slots, a plurality of data packets to a corresponding plurality of said nodes in said first subset of nodes using a different subchannel for each of said nodes in said first subset of nodes to which said at least one of said nodes in said second subset of nodes transmits one or more data packets during said second one of said time slots, and

(iv) at least one of said nodes in said first subset of nodes receives, during said second one of said time slots, a plurality of data packets from a corresponding plurality of said nodes in said second subset of nodes using a different subchannel for each of said nodes in said second subset of nodes from which said at least one of said nodes in said first subset of nodes receives one or more data packets during said second one of said time slots.

12. The wireless communications network of claim 11 wherein said first subset of nodes and said second subset of nodes together comprise all of said plurality of nodes in said wireless communications network.

13. The wireless communications network of claim 11 wherein said plurality of non-overlapping time slots are continuous in time, and wherein said means for transmitting during said first one of said time slots and said means for transmitting during said second one of said time slots are adapted to repeat transmitting in turn within successive time slots throughout said period of time, such that means for transmitting during said first one of said time slots is performed within successively odd numbered timeslots and said means for transmitting during said second one of said time slots is performed within successively even numbered timeslots.

14. The wireless communications network of claim 11 further comprising:

means for transmitting, during a third one of said time slots subsequent to at least said first one of said time slots, one or more of said data packets from one or more of said nodes in one of said first or second subset of said nodes which transmits one or more data packets to one or more nodes in said other one of said first or second subset of said nodes during one of said first or second ones of said time slots, to one or more other nodes in said other one of said first or second subset of nodes,

wherein said plurality of non-overlapping time slots are continuous in time, and wherein said means for transmitting during said first one of said time slots, said means for transmitting during said second one of said time slots, and said means for transmitting during said third one of said time slots, are adapted to repeat transmitting in turn within successive time slots throughout said period of time.

15. The wireless communications network of claim 11 wherein said data packets transmitted by said nodes in said first subset of nodes during said first time slot and said data packets transmitted by said nodes in said second subset of nodes during said second time slot are scheduled based on a predetermined wireline network scheduling policy.

16. The wireless communications network of claim 15 wherein said data packets transmitted by said nodes in said first subset of nodes during said first time slot and said data packets transmitted by said nodes in said second subset of nodes during said second time slot are scheduled based on said predetermined wireline network scheduling policy as applied to an imaginary wireline network topology based on a topology of said wireless communications network.

17. The wireless communications network of claim 16 wherein

(i) each of said plurality of non-overlapping time slots are continuous and of a predetermined length of time,

(ii) said means for transmitting during said first one of said time slots and said means for transmitting during said second one of said time slots are adapted to repeat transmitting in turn within successive time slots throughout said period of time,

(iii) said data packets transmitted by said nodes in said first subset of nodes are scheduled to be transmitted in a selected one of said repetitions of said means for transmitting during said first one of said time slots based on when said data packets would have been scheduled to be transmitted by corresponding ones of said nodes in said first subset of nodes in said imaginary wireline network topology in accordance with said predetermined wireline network scheduling policy as applied to said imaginary wireline network topology, and

(iv) said data packets transmitted by said nodes in said second subset of nodes are scheduled to be transmitted in a selected one of said repetitions of said means for transmitting during said second one of said time slots based on when said data packets would have been scheduled to be transmitted by corresponding ones of said nodes in said second subset of nodes in said imaginary wireline network topology in accordance with said predetermined wireline network scheduling policy as applied to said imaginary wireline network topology.

18. The wireless communications network of claim 11 wherein said wireless communications network comprises a mutihop wireless backhaul network, wherein one of said nodes comprised therein comprises a gateway to a wireline network, and wherein one or more of all other nodes comprised therein comprise wireless access points thereof.

19. The wireless communications network of claim 18 wherein the wireline network comprises the Internet.

20. The wireless communications network of claim 18 wherein the wireless communications network communicates with use of a WiMAX communications protocol.