DELAY AND JITTER WIRELESS MESH NETWORK SCHEDULING

• US 20110222506A1
• Filed: 10/14/2009
• Published: 09/15/2011
• Est. Priority Date: 10/14/2008
• Status: Active Grant

• Current Assignee: Tadeusz H. Szymanksi
• Original Assignee: Tadeusz H. Szymanksi
• Inventors: Szymanksi, Tadeusz H.
• Granted Patent: US 8,619,566 B2
• Time in Patent Office: Days
• US Class Current: 370/330
• CPC Class Codes: H04L 1/0042 Encoding specially adapted to other signal generation operation, e.g. in order to reduce transmit distortions, jitter, or to improve signal shape H04L1/0067 takes precedence
• CPC Class Codes: H04L 27/2601 Multicarrier modulation systems
• CPC Class Codes: H04L 49/40 Constructional details, e.g. power supply, mechanical construction or backplane
• CPC Class Codes: H04L 5/0037 Inter-user or inter-terminal allocation
• CPC Class Codes: H04W 16/28 using beam steering
• CPC Class Codes: H04W 28/0268 using specific QoS parameters for wireless networks, e.g. QoS class identifier [QCI] or guaranteed bit rate [GBR] negotiating SLA or negotiating QoS H04W28/24
• CPC Class Codes: H04W 28/26 Resource reservation
• CPC Class Codes: H04W 52/20 using error rate
• CPC Class Codes: H04W 52/265 taking into account the quality of service QoS
• CPC Class Codes: H04W 52/46 in multi hop networks, e.g. wireless relay networks
• CPC Class Codes: H04W 72/044 based on the type of the allocated resource
• CPC Class Codes: H04W 72/0446 Resources in time domain, e.g. slots or frames
• CPC Class Codes: H04W 72/541 using the level of interference
• CPC Class Codes: H04W 72/543 based on requested quality, e.g. QoS
• CPC Class Codes: H04W 84/12 WLAN [Wireless Local Area Networks]
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: H04W 88/16 Gateway arrangements

Abstract

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 a 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.

Claims

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 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.

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 least one node in a wireless mesh network causes at least one processor to execute the method of claim 1.

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.