US2017135124A1PendingUtilityA1

Delay and jitter limited wireless mesh network scheduling

53
Individually held — no corporate assignee on recordPriority: Oct 14, 2008Filed: Sep 14, 2016Published: May 11, 2017
Est. expiryOct 14, 2028(~2.2 yrs left)· nominal 20-yr term from priority
Inventors:Tadeusz H. Szymanski
H04W 72/543H04W 72/541H04W 84/18H04W 72/1236H04L 1/0042H04W 28/0268H04W 52/265H04L 49/40H04L 27/2601H04W 52/20H04W 28/26H04W 16/28H04W 72/0446H04W 52/46H04L 5/0037H04W 84/12H04W 88/16H04W 72/044
53
PatentIndex Score
0
Cited by
0
References
0
Claims

Abstract

Schedule and channel assignment in a wireless mesh network (WMN) 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 nodes of the WMN. Each permutation matrix represents active radio links between nodes. The sequence of permutation matrices defines a sequence of radio links to provide desired bandwidth between nodes. Further, a representation of a sequence of partial permutation matrices corresponding to the sequence of permutation matrices is formed so that each of the permutation matrices can be decomposed into a group of partial permutation matrices. Each partial permutation matrix represents non-interfering radio links between the nodes. In each timeslot, the 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 nodes.

Claims

exact text as granted — not AI-modified
1 . (canceled) 
     
     
         2 . A deterministic wireless network for transmitting a plurality of traffic flows over a scheduling-frame comprising F time-slots,
 said deterministic wireless network comprising a plurality of wireless switches and a plurality of directed wireless links between pairs of said plurality of wireless switches;   wherein each one of said plurality of wireless switches comprises a memory to store a schedule for configuring the switch; a plurality of wireless transmitters and a plurality of wireless receivers; a plurality of buffers to store data to transmit, each associated with one of said directed wireless links which can transmit data from said one of said wireless switches and is assigned a guaranteed data-rate equal to a number of bits to transmit in said scheduling-frame;   wherein each of said traffic flows traverses a path comprising one or more of said plurality of wireless switches and one or more of said plurality of directed wireless links, and wherein the data of a traffic flow is stored in one of said plurality of buffers in each of said wireless switches that it traverses;
 wherein for each of said plurality of wireless switches, the schedule for that switch:
 specifies which of said plurality of wireless transmitters in that switch, if any, are enabled to transmit data for each time-slot of said scheduling-frame, and for each of said wireless transmitters which is enabled to transmit, which wireless channel is used for the transmission; and 
 specifies which of said plurality of wireless receivers in that switch, if any, are enabled to receive data for each time-slot of said scheduling-frame, and for each receiver which is enabled to receive, which wireless channel is used for the reception; 
 
 and wherein the schedule for that switch:
 provides each of said buffers within that switch with a guaranteed number of time-slot reservations for transmission in said scheduling-frame, sufficient to satisfy its guaranteed data-rate requirement; and 
 
 provides each of said buffers with a relatively equal number of time-slots reservations for transmission, in each half of said scheduling-frame. 
   
     
     
         3 . The deterministic wireless network of  claim 2 ,
 wherein for each wireless switch, the guaranteed data-rate assigned to each of said buffers in that switch includes an extra guaranteed data-rate R>=0, to compensate for occasional errors in the wireless transmissions.   
     
     
         4 . The deterministic wireless network of  claim 3 ,
 wherein for each of said buffers with a guaranteed rate of transmission equal to R time-slot reservations per scheduling frame, the number of time-slot reservations for transmission for that buffer in either half of said scheduling-frame differs from R/2 by at most K, for K=3.   
     
     
         5 . The deterministic wireless network of  claim 4 ,
 wherein for each wireless switch, the schedule for that switch provides each of said buffers in that switch with a relatively equal number of time-slot reservations for transmission, in each quarter of said scheduling-frame.   
     
     
         6 . The deterministic wireless network of  claim 5 ,
 wherein for each of said buffers with a guaranteed rate of transmission equal to R time-slot reservations for transmission in said scheduling-frame, said schedule provides that buffer with at least (E/F)*R−K time-slot reservations for transmission in time-slots 1 . . . E of that scheduling-frame, where E and R are positive integers <=F, and where K=3.   
     
     
         7 . The deterministic wireless network of  claim 5 ,
 wherein each of said traffic flows is associated with a guaranteed data-rate equal to a guaranteed number of bits to transmit in said scheduling frame;   wherein for each wireless switch, the guaranteed data-rate assigned to each buffer is sufficient to satisfy the cumulative guaranteed data-rate requirement of the traffic flows which store data in that buffer.   
     
     
         8 . The deterministic wireless network of  claim 7 ,
 wherein for each of said traffic flows, the guaranteed data-rate assigned to that traffic flow includes an extra guaranteed data-rate >=0, to compensate for occasional errors in the wireless transmissions.   
     
     
         9 . The deterministic wireless network of  claim 8 ,
 wherein for each wireless switch, the schedule for that switch reserves sufficient time-slots to provide each of said traffic flows which traverse that switch with a relatively equal number of time-slot reservations for transmission, in each half of said scheduling-frame.   
     
     
         10 . The deterministic wireless network of  claim 9 ,
 wherein said schedule reserves sufficient time-slots to provide each of said traffic flows which traverse said switch with a relatively equal number of time-slots reservations for transmission, in each quarter of said scheduling-frame.   
     
     
         11 . The deterministic wireless network of  claim 10 ,
 wherein for each of said traffic flows with a guaranteed rate of transmission equal to R time-slot reservations for transmission in said scheduling-frame, said schedule reserves sufficient time-slots to provide that traffic flow with at least (E/F)*R−K time-slot reservations for transmission in time-slots 1 . . . E of that scheduling frame, where E and R are positive integers<=F, and where K=3.   
     
     
         12 . The deterministic wireless network of  claim 5 ,
 wherein for each wireless switch, and for each wireless transmitter of that switch, said transmitter uses a Directional-Antenna which comprises a plurality of antennas; and   wherein the schedule for that switch specifies a plurality of beamforming parameters for said Directional-Antenna in each time-slot, to configure said Directional-Antenna to improve the quality of the transmission.   
     
     
         13 . The deterministic wireless network of  claim 5 ,
 wherein for each wireless switch, and for each wireless receiver of that switch, said receiver uses a Directional-Antenna which comprises a plurality of antennas; and   wherein the schedule for that switch specifies a plurality of beamforming parameters for said Directional-Antenna in each time-slot, to configure said Directional-Antenna to improve the quality of the reception.   
     
     
         14 . The deterministic wireless network of  claim 5 ,
 wherein the deterministic wireless switches have a geographically fixed location.   
     
     
         15 . The deterministic wireless network of  claim 14 ,
 wherein for each wireless switch, and for each wireless transmitter of that switch which is enabled to transmit in a time-slot, said schedule for that switch specifies a transmission power level to be used to improve the quality of the transmission in said time-slot.   
     
     
         16 . The deterministic wireless network of  claim 15 ,
 wherein said transmission power level allows a sufficiently low bit error rate to be achieved for said transmission.   
     
     
         17 . The deterministic wireless network of  claim 5 ,
 wherein for each wireless switch, and for each wireless transmitter of that switch which is enabled to transmit in a time-slot, said schedule for that switch specifies a forward error correcting code to be used to improve the quality of the transmission in said time-slot.   
     
     
         18 . The deterministic wireless network of  claim 5 ,
 wherein the wireless channels use Orthogonal Frequency Division Multiple Access (OFDMA).   
     
     
         19 . The deterministic wireless network of  claim 5 ,
 wherein the deterministic wireless network comprises N wireless switches for positive integer N; and   wherein said schedules for said network identify at least (0.7)*N*F directed wireless links for transmission in said scheduling frame.   
     
     
         20 . The deterministic wireless network of  claim 5 ,
 wherein at least one of said plurality of wireless switches, called a ‘gateway switch’, can send packets to and receive packets from the Internet network;   wherein at least one of said plurality of traffic flows has a path which originates at said gateway switch and ends at another wireless switch with index K;   wherein that traffic flow transports packets for a plurality of end-users; and   wherein that wireless switch with index K will deliver said packets to said end-users using wireless transmissions.   
     
     
         21 . The deterministic wireless network of  claim 20 ,
 wherein at least one of said plurality of traffic flows has a path which originates at that wireless switch with index K and ends at said gateway switch;   wherein that traffic flow transports packets from a plurality of end-users; and   wherein said gateway switch will transmit said packets from said end-users to the Internet network.   
     
     
         22 . The deterministic wireless network of  claim 10 ,
 wherein at least one of said plurality of wireless switches, called a ‘gateway switch’, can send packets to and receive packets from the Internet network;   wherein at least one of said plurality of traffic flows has a path which originates at said gateway switch and ends at another wireless switch with index K;   wherein that traffic flow transports packets for a plurality of end-users; and   wherein that wireless switch with index K will deliver said packets to said end-users using wireless transmissions.   
     
     
         23 . The deterministic wireless network of  claim 22 ,
 wherein at least one of said plurality of traffic flows has a path which originates at that wireless switch with index K and ends at said gateway switch;   wherein that traffic flow transports packets from a plurality of end-users; and   wherein said gateway switch will transmit said packets from said end-users to the Internet network.   
     
     
         24 . The deterministic wireless network of  claim 20 ,
 wherein a subset of said plurality of wireless channels is used exclusively for the transmitting packets for traffic flows which original at said gateway switch, or which end at said gateway switch;   and wherein a subset of that plurality of wireless channels is used exclusively for delivering packets to end-users.   
     
     
         25 . The deterministic wireless network of  claim 20 ,
 wherein said wireless switch with index K uses substantially an IEEE 802.11 WiFi wireless network to deliver said packets to said end-users.   
     
     
         26 . The deterministic wireless network of  claim 22 ,
 wherein said wireless switch with index K uses substantially an IEEE 802.11 WiFi wireless network to deliver said packets to said end-users.   
     
     
         27 . A controller for the deterministic wireless network of  claim 3 , wherein the deterministic wireless network comprises N wireless switches for integer N>0, comprising:
 memory to store a schedule for each of said wireless switches;   memory to store a matrix D of guaranteed data-rates, with N rows and N columns;   wherein each element D(J,K) specifies a guaranteed data-rate for a traffic flow which traverses a path which starts at wireless switch J and which ends at wireless switch K, for positive integers J and K which are less than or equal to N;   a processor to process said matrix D, and for each traffic flow in said matrix D with a guaranteed data-rate greater than 0, said processor will assign a path through said network for said traffic flow;   wherein said processor will process the plurality of traffic flows which traverse each wireless switch, and determine a schedule for that wireless switch.   
     
     
         28 . The controller of  claim 27 ,
 wherein said deterministic wireless network further satisfies the requirements of  claim 5 .   
     
     
         29 . The controller of  claim 28 ,
 wherein said deterministic wireless network further satisfies the requirements of  claim 6 .   
     
     
         30 . The controller of  claim 27 ,
 wherein said deterministic wireless network further satisfies the requirements of  claim 10 .   
     
     
         31 . The controller of  claim 30 ,
 wherein said deterministic wireless network further satisfies the requirements of  claim 11 .   
     
     
         32 . The controller of  claim 27 ,
 wherein said controller will compute a set of directed wireless links which are enabled to transmit in each time-slot of said scheduling-frame;   wherein for each directed wireless link which is enabled to transmit in a time-slot, that controller will determine a wireless channel for the transmission; and   wherein said wireless channel is selected according to a criterion which will improve the overall quality of the transmissions in said time-slot.   
     
     
         33 . The controller of  claim 27 ,
 wherein said controller further satisfies the requirements of  claim 10 ;   wherein said controller will determine a set of directed wireless links which are enabled to transmit in each time-slot of said scheduling-frame;   wherein for each directed wireless link which is enabled to transmit in a time-slot, that controller will determine a plurality of beamforming parameters to control the Direction-Antenna used in the transmission over said directed wireless link;   wherein said beamforming parameters are selected according to a criterion which will improve the overall quality of the transmissions in said time-slot.   
     
     
         34 . The controller of  claim 27 ,
 wherein said deterministic wireless network further satisfies the requirements of  claim 20 .   
     
     
         35 . The controller of  claim 27 ,
 wherein said deterministic wireless network further satisfies the requirements of  claim 22 .   
     
     
         36 . The controller of  claim 27 ,
 wherein said deterministic wireless network further satisfies the requirements of  claim 24 .   
     
     
         37 . The controller of  claim 27 ,
 wherein said deterministic wireless network further satisfies the requirements of  claim 25 .   
     
     
         38 . The controller of  claim 27 ,
 wherein said deterministic wireless network further satisfies the requirements of  claim 26 .

Join the waitlist — get patent alerts

Track US2017135124A1 — get alerts on status changes and closely related new filings.

We store only your email — no account needed. See our privacy policy.