Delay and jitter limited wireless mesh network scheduling

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.

What is claimed is: 
     
         1 . A method of scheduling transmission of traffic in a wireless mesh network comprising n nodes, said method comprising:
 forming an n×n rate matrix, wherein entries of said n×n matrix define the bandwidth of links between said n nodes;   forming a representation of a sequence of permutation matrices whose sum equals at least said rate matrix, from said rate matrix, wherein each of said permutation matrices represent radio links between said n nodes, and wherein said sequence of permutation matrices defines a sequence of radio links to provide the bandwidth of links between said n nodes;   forming a representation of a sequence of partial permutation matrices, wherein each of said permutation matrices can be decomposed into groups of partial permutation matrices in said sequence of partial permutation matrices, each one of said partial permutation matrices in a group representing non-interfering radio links between said n nodes;   in each timeslot, configuring said n nodes for radio transmission and reception in accordance with at least one of said partial permutation matrices in each group of partial permutation matrices to transmit traffic between said n nodes.   
     
     
         2 . The method of  claim 1 , further comprising repeating said configuring in accordance with sequential ones of said sequence of partial permutation matrices until said n nodes have been configured in accordance with all of said partial permutation matrices in said sequence of partial permutation matrices. 
     
     
         3 . The method of  claim 2 , further comprising repeating said configuring by re-using said sequence of partial permutation matrices. 
     
     
         4 . The method of  claim 1 , wherein at least some of said permutation matrices are represented as a 1×n vector. 
     
     
         5 . The method of  claim 1 , wherein at least some of said partial permutation matrices is represented as a 1×n vector. 
     
     
         6 . The method of  claim 1 , wherein at least some of said permutation matrices are represented as bipartite graphs, graphs, sets or lists of interrelated elements. 
     
     
         7 . The method of  claim 3 , where said forming said representation of said sequence of permutation matrices comprises decomposing said rate matrix using a recursive fair stochastic matrix decomposition algorithm. 
     
     
         8 . The method of  claim 1 , wherein said forming a representation of a sequence of partial permutation matrices comprises forming each group of partial permutation matrices by representing one of said permutation matrices as a graph, and coloring said graph to form said each group of partial permutation matrices. 
     
     
         9 . The method of  claim 1 , where said configuring said n nodes for radio transmission and reception in accordance with at least one of said partial permutation matrices, comprises assigning transmit and receive Frequency Division Multiple Access (FDMA) channels. 
     
     
         10 . The method of  claim 1 , where said configuring said n nodes for radio transmission and reception in accordance with at least one of said partial permutation matrices, comprises assigning transmit and receive Orthogonal Frequency Division Multiple Access (OFDMA) channels. 
     
     
         11 . The method of  claim 1 , where said configuring said n nodes for radio transmission and reception in accordance with at least one of said partial permutation matrices, comprises assigning transmit and receive Code Division Multiple Access (CDMA) channels. 
     
     
         12 . The method of  claim 1 , where said configuring said n nodes for radio transmission and reception in accordance with at least one of said partial permutation matrices, comprises assigning transmit and receive Space Division Multiple Access (SDMA) channels. 
     
     
         13 . The method of  claim 1 , wherein said forming said representation of a sequence of permutation matrices; said forming said representation of a sequence of partial permutation matrices; and said configuring is performed by one control processor. 
     
     
         14 . The method of  claim 1 , said forming said representation of a sequence of permutation matrices; said forming said representation of a sequence of partial permutation matrices; and said assigning is performed at at least one of said m nodes. 
     
     
         15 . The method of  claim 1 , wherein said forming said representation of a sequence of partial permutation matrices comprises, for each represented radio link in a permutation matrix identifying interfering radio links from a channel conflict set, to form one of said partial permutation matrices. 
     
     
         16 . The method of  claim 1  wherein said forming said representation of said sequence of partial permutation matrices, comprises processing radio links represented in permutation matrix according to an augmenting path, to form each partial permutation matrix. 
     
     
         17 . The method of  claim 1 , wherein said forming said representation of a sequence of partial permutation matrices comprises, for each represented radio link in a permutation matrix, processing a channel interference matrix indicating interference between other radio links, to form one of said partial permutation matrices. 
     
     
         18 . A wireless mesh network comprising n nodes, and a control processor, said control processor in communication with said n nodes, said control processor operable to:
 form a representation of a sequence of permutation matrices whose sum equals at least said rate matrix, from an n×n rate matrix, wherein entries of said n×n matrix define the bandwidth of links between said n nodes, wherein each of said permutation matrices represent radio links between said n nodes, and wherein said sequence of permutation matrices defines a sequence of radio links to provide the bandwidth of links between said n nodes;   form a representation of a sequence of partial permutation matrices, wherein each of said permutation matrices can be decomposed into groups of partial permutation matrices in said sequence of partial permutation matrices, each one of said partial permutation matrices in a group representing non-interfering radio links between said n nodes;   configure in each timeslot, said n nodes for radio transmission and reception in accordance with at least one of said partial permutation matrices in each group of partial permutation matrices to transmit traffic between said n nodes.   
     
     
         19 . A wireless mesh network comprising n nodes, configured in accordance with the method of  claim 1 . 
     
     
         20 . A control processor in a wireless mesh network for performing the method of  claim 1 . 
     
     
         21 . A computer readable medium storing processor executable instructions that when loaded at at least one node in a wireless mesh network causes at least one processor to execute the method of  claim 1 .