Delay and jitter limited wireless mesh network scheduling

摘要

Schedule and channel assignment (SCA) in a wireless mesh network (WMN) is disclosed. A method includes: forming a representation of a sequence of permutation matrices from an n×n rate matrix. The entries of the rate matrix define the bandwidth of links between the n nodes of the WMN. Each of the permutation matrices represents active radio links between the n nodes. The sequence of permutation matrices defines a sequence of radio links to provide the desired bandwidth of links between said n nodes. Further, a representation of a sequence of partial permutation matrices corresponding to the sequence of permutation matrices is formed in such a way that each of the permutation matrices can be decomposed into a group of partial permutation matrices. Each of the partial permutation matrices in a group represents non-interfering radio links between the n nodes. In each timeslot, the n nodes are configured for radio transmission and reception in accordance with at least one of the partial permutation matrices in each group to transmit traffic between the n nodes. Example SCA can be used to provision longer-term guaranteed-rate backhaul traffic flows supporting multimedia services such as VOIP or IPTV between base-stations in a WMN, with near-minimal delay and jitter and near-perfect Quality-of-Service for every provisioned traffic flow.

主权项

1. A wireless switch for transmitting a plurality of guaranteed rate (GR) traffic flows over a scheduling frame comprising a plurality of F time-slots, where each GR traffic flow is associated with a guaranteed data rate, comprising:
N input ports and M output ports, wherein each input port has access to a wireless receiver configurable to receive data over one wireless channel selected from a plurality of K wireless channels, and wherein each output port has access to a wireless transmitter configurable to transmit data over one wireless channel selected from said plurality of K wireless channels; M queues, wherein each queue is associated with one of said M output ports, and wherein each GR traffic flow is associated with one input port and one queue, and wherein data associated with a GR traffic flow is buffered in its associated queue; memory for storing a transmission-schedule, wherein the transmission-schedule specifies which of said M queues, if any, have a reservation to transmit data during each time-slot in said scheduling frame; memory for storing a channel-schedule, wherein the channel-schedule specifies for each transmitting queue, if any, in a time-slot in said scheduling frame, which of said plurality of K wireless channels is reserved for the transmission; wherein the transmission-schedule provides each of said M queues with a guaranteed rate of transmission from the switch in one scheduling frame, sufficient to satisfy the cumulative data rate requirement of the GR traffic flows associated with that queue, wherein the channel-schedule provides each of said M queues with a reservation to a wireless channel to enable transmissions with a Bit Error Rate (BER) less than a specified BER to be achieved over said scheduling frame, and wherein the transmission-schedule provides any selected one of said M queues with a guaranteed rate of transmission corresponding to R time-slot reservations for transmission in said scheduling frame, for integer R<=F, and wherein said transmission-schedule provides said one of said M queues with a relatively equal number of time-slot reservations for transmission in each half of said scheduling frame.