Method and apparatus for link transmission scheduling for handling traffic variation in wireless mesh networks

• US 20070237081A1
• Filed: 03/30/2006
• Published: 10/11/2007
• Est. Priority Date: 03/30/2006
• Status: Active Grant

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Inventors: Lakshman, Tirunell, Kodialam, Muralidharan, Sengupta, Sudipta
• Granted Patent: US 7,729,257 B2
• Time in Patent Office: Days
• US Class Current: 370/235
• CPC Class Codes: H04L 43/0882 Utilisation of link capacity
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS
• CPC Class Codes: H04W 28/0933 based on load-splitting ratios
• CPC Class Codes: H04W 40/12 based on transmission quality or channel quality
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

The invention includes a method and apparatus for generating a link transmission schedule for handling traffic variation in wireless networks without dynamic scheduling or routing. The method includes determining fixed traffic capacities associated with respective wireless links of a wireless network according to a routing algorithm, and generating, using the routing algorithm and the fixed traffic capacities, a link transmission schedule including at least one condition by which traffic is transmitted using each of the network links. The link transmission schedule is adapted to remain substantially fixed during dynamic traffic changes. The routing algorithm may be a two-phase routing algorithm in which traffic is distributed by each node in the wireless network to every node in the wireless network using traffic split ratios. For two-phase routing, fixed traffic capacities may be determined using ingress and egress traffic capacities and traffic split ratios associated with respective nodes in the wireless network.

Claims

1. A method for generating a link transmission schedule, comprising:

determining fixed traffic capacities associated with each of a respective plurality of wireless links according to a routing algorithm; and

generating, using the routing algorithm and the determined fixed traffic capacities, the link transmission schedule comprising at least one condition by which traffic is transmitted using each of the wireless links, wherein the link transmission schedule is adapted to remain substantially fixed during dynamic traffic changes.

2. The method of claim 1, wherein determining the fixed traffic capacities comprises:

determining at least one routing parameter adapted for configuring the routing algorithm to establish the fixed traffic capacities on the respective network links.

3. The method of claim 2, wherein the at least one routing parameter is determined in a manner for satisfying at least one scheduling constraint.

4. The method of claim 3, wherein the at least one scheduling constraint comprises at least one of a utilization commitment vector constraint, a transmission power constraint, a cross-provider conflict constraint, a radio transmit/receive diversity constraint, or a link interference constraint.

5. The method of claim 2, wherein the routing algorithm is a two-phase routing algorithm comprising a first phase during which each of a plurality of nodes distributes traffic to each of the nodes according to a respective plurality of traffic split ratios.

6. The method of claim 5, wherein the two-phase routing algorithm comprises a second phase during which each of the nodes routes traffic received during the first phase to selected ones of the node comprising destination nodes of the traffic.

7. The method of claim 5, wherein determining the at least one routing parameter comprises determining the respective traffic split ratios associated with each of the nodes.

8. The method of claim 1, wherein determining the fixed traffic capacities comprises:

determining an ingress traffic capacity associated with each node;

determining an egress traffic capacity associated with each node;

determining a plurality of traffic split ratios associated with each node; and

determining the fixed traffic capacities using the ingress traffic capacities, the egress traffic capacities, and the traffic split ratios.

9. The method of claim 1, wherein the link transmission schedule is generated using a link scheduling algorithm.

10. The method of claim 1, wherein the at least one condition by which each of the network links transmits traffic comprises at least one of a time slot, a transmission frequency, a transmission power, and a receiver.

11. An apparatus for generating a link transmission schedule, comprising:

means for determining fixed traffic capacities associated with each of a respective plurality of wireless links according to a routing algorithm; and

means for generating, using the routing algorithm and the determined fixed traffic capacities, the link transmission schedule comprising at least one condition by which traffic is transmitted using each of the wireless links, wherein the link transmission schedule is adapted to remain substantially fixed during dynamic traffic changes.

12. The apparatus of claim 11, wherein the means for determining the fixed traffic capacities comprises:

means for determining at least one routing parameter adapted for configuring the routing algorithm to establish the fixed traffic capacities on the respective network links.

13. The apparatus of claim 12, wherein the at least one routing parameter is determined in a manner for satisfying at least one scheduling constraint.

14. The apparatus of claim 13, wherein the at least one scheduling constraint comprises at least one of a utilization commitment vector constraint, a transmission power constraint, a cross-provider conflict constraint, a radio transmit/receive diversity constraint, or a link interference constraint.

15. The apparatus of claim 12, wherein the routing algorithm is a two-phase routing algorithm comprising a first phase during which each of a plurality of nodes distributes traffic to each of the nodes according to a respective plurality of traffic split ratios.

16. The apparatus of claim 15, wherein the two-phase routing algorithm comprises a second phase during which each of the nodes routes traffic received during the first phase to selected ones of the node comprising destination nodes of the traffic.

17. The apparatus of claim 15, wherein the means for determining the at least one routing parameter comprises means for determining the respective traffic split ratios associated with each of the nodes.

18. The apparatus of claim 11, wherein the means for determining the fixed traffic capacities comprises:

means for determining an ingress traffic capacity associated with each node;

means for determining an egress traffic capacity associated with each node;

means for determining a plurality of traffic split ratios associated with each node; and

means for determining the fixed traffic capacities using the ingress traffic capacities, the egress traffic capacities, and the traffic split ratios.

19. The apparatus of claim 11, wherein the link transmission schedule is generated using a link scheduling algorithm.

20. The apparatus of claim 11, wherein the at least one condition by which each of the network links transmits traffic comprises at least one of a time slot, a transmission frequency, a transmission power, and a receiver.

21. A method, comprising:

receiving a link transmission schedule determined using a routing algorithm and a plurality of fixed traffic capacities associated with a respective plurality of network links, wherein the link transmission schedule defines at least one condition by which traffic is transmitted over each of the network links, wherein the link transmission schedule is adapted to remain substantially fixed during dynamic traffic changes; and

transmitting traffic over the network links using the routing algorithm and the link transmission schedule.