Randomized Mesh Network Routing

• US 20170353259A1
• Filed: 06/06/2016
• Published: 12/07/2017
• Est. Priority Date: 06/06/2016
• Status: Active Grant

• Current Assignee: Huawei Technologies Canada Co., Ltd (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Huawei Technologies Canada Co., Ltd (Huawei Investment & Holding Co., Ltd.)
• Inventors: McCormick, William Carson, Kelly, Francis Patrick
• Granted Patent: US 9,967,045 B2
• Time in Patent Office: Days
• CPC Class Codes: H04J 3/1694 Allocation of channels in TDM/TDMA networks, e.g. distributed multiplexers Passive Optical Networks H04Q11/0062
• CPC Class Codes: H04L 1/002 Algorithms with memory of the previous states, e.g. Markovian models
• CPC Class Codes: H04W 40/16 based on interference
• CPC Class Codes: H04W 72/1263 Mapping of traffic onto schedule, e.g. scheduled allocation or multiplexing of flows
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A time domain multiplexed (TDM) routing schedule for a wireless mesh network can be generated using a Markov chain process. In particular, synchronized paths between access nodes and gateways in the mesh network can be added to, and removed from, the TDM routing schedule in an iterative fashion according to each individual state in a state progression of a Markov chain, with each state of the Markov chain mapping a different combination of synchronized paths to the TDM routing schedule. In some embodiments, transitioning between states of a Markov chain is performed according to a proportionally fair transition rate.

Claims

1. A method for scheduling wireless transmissions, the method comprising:

selecting routes between access nodes and one or more gateways in a wireless mesh network, each of the routes including one or more wireless links;

mapping wireless links in at least some of the routes to timeslots of a frame to form a plurality of synchronized paths between the access nodes and the gateways;

iteratively adding, or removing, an individual one of the plurality of synchronized paths to, or from, a TDM routing schedule according to each individual state in a state progression of a Markov chain, the TDM routing schedule including a different subset of synchronized paths for each state in the Markov chain; and

instructing the access nodes and the one or more gateways to communicate messages over the wireless links according the TDM routing schedule.

2. The method of claim 1, wherein the state progression through the Markov chain progresses through fewer than all states in the Markov chain.

3. The method of claim 1, wherein each state in the progression through states of the Markov chain maps a different combination of synchronized paths to the TDM routing schedule.

4. The method of claim 3, wherein iteratively adding, or removing, an individual one of the plurality of synchronized paths to, or from, the TDM routing schedule according to each individual state in the state progression of the Markov chain comprises:

transitioning from a previous state in the Markov chain to a subsequent state in the Markov chain based on a proportionally fair transition rate.

5. The method of claim 4, wherein transitioning from the previous state in the Markov chain to the subsequent state in the Markov chain comprises:

adding a first synchronized path to the TDM routing schedule when the first synchronized path is mapped to the TDM routing schedule by the subsequent state of the Markov chain without being mapped to the TDM routing schedule by the previous state of the Markov chain.

6. The method of claim 3, wherein iteratively adding, or removing, an individual one of the plurality of synchronized paths to, or from, the TDM routing schedule according to each state during a progression through states of a Markov chain comprises:

determining whether a first synchronized path mapped to the TDM routing schedule by the subsequent state of the Markov chain is feasible based on an interference model of the mesh network; and

adding the first synchronized path to the TDM routing schedule if the first synchronized path is feasible.

7. The method of claim 6, wherein the interference model is a protocol interference model between the wireless links, the protocol interference model prohibiting transmissions from being scheduled over two or more interfering links during the same timeslot of the frame.

8. The method of claim 6, wherein the interference model is a physical interference model between the wireless links, the physical interference model permitting transmissions to be scheduled over two or more interfering links during the same timeslot of the frame when an interference cost associated with the transmissions is less than a threshold.

9. The method of claim 8, wherein the interference costs vary based on the amount of interference experienced between transmissions performed over the two or more interfering links during the same period.

10. The method of claim 1, wherein iteratively adding, or removing, an individual one of the plurality of synchronized paths to, or from, the TDM routing schedule according to each individual state in the state progression of the Markov chain comprises:

transitioning from a previous state in the Markov chain to a current state in the Markov chain based on a transition rate of the Markov chain; and

adjusting the transition rate of the Markov chain based on a ratio of users to synchronized paths specified by the subsequent state in the Markov chain.

11. The method of claim 10, wherein the ratio of users to synchronized paths includes a summation of ratios between users accessing each of the access nodes and synchronized paths assigned to the corresponding access point in the TDM routing schedule.

12. The method of claim 10, wherein the transition is decreased when the ratio of users to synchronized paths specified by the subsequent state in the Markov chain exceeds a ratio of users to synchronized paths specified by the previous state in the Markov chain.

13. An apparatus comprising:

a processor; and

a non-transitory computer readable storage medium storing programming for execution by the processor, the programming including instructions to;

select routes between access nodes and one or more gateways in a wireless mesh network, each of the routes including one or more wireless links;

map wireless links in at least some of the routes to timeslots of a frame to form a plurality of synchronized paths between the access nodes and the gateways;

iteratively add, or remove, an individual one of the plurality of synchronized paths to, or from, a TDM routing schedule according to each individual state in a state progression of a Markov chain, the TDM routing schedule including a different subset of synchronized paths for each state in the Markov chain; and

instruct the access nodes and the one or more gateways to communicate messages over the wireless links according the TDM routing schedule.

14. The apparatus of claim 13, wherein the state progression through the Markov chain progresses through fewer than all states in the Markov chain.

15. The apparatus of claim 13, wherein each state in the progression through states of the Markov chain maps a different combination of synchronized paths to the TDM routing schedule.

16. The apparatus of claim 15, wherein the instructions to iteratively add, or remove, an individual one of the plurality of synchronized paths to, or from, the TDM routing schedule according to each individual state in the state progression of the Markov chain includes instructions to:

transition from a previous state in the Markov chain to a subsequent state in the Markov chain based on a proportionally fair transition rate.

17. The apparatus of claim 16, wherein the instructions to transition from the previous state in the Markov chain to the subsequent state in the Markov chain include instructions to:

add a first synchronized path to the TDM routing schedule when the first synchronized path is mapped to the TDM routing schedule by the subsequent state of the Markov chain without being mapped to the TDM routing schedule by the previous state of the Markov chain.

18. The apparatus of claim 16, wherein the instructions to iteratively add, or remove, an individual one of the plurality of synchronized paths to, or from, the TDM routing schedule according to each individual state in the state progression of the Markov chain includes instructions to:

determine whether a first synchronized path mapped to the TDM routing schedule by the subsequent state of the Markov chain is feasible based on an interference model of the mesh network; and

add the first synchronized path to the TDM routing schedule if the first synchronized path is feasible.

19. The apparatus of claim 18, wherein the interference model is a protocol interference model between the wireless links, the protocol interference model prohibiting transmissions from being scheduled over two or more interfering links during the same timeslot of the frame.

20. The apparatus of claim 18, wherein the interference model is a physical interference model between the wireless links, the physical interference model permitting transmissions to be scheduled over two or more interfering links during the same timeslot of the frame when an interference cost associated with the transmissions is less than a threshold.

21. The apparatus of claim 20, wherein the interference costs vary based on the amount of interference experienced between transmissions performed over the two or more interfering links during the same period.

22. A computer program product comprising a non-transitory computer readable storage medium storing programming, the programming including instructions to:

select routes between access nodes and one or more gateways in a wireless mesh network, each of the routes including one or more wireless links;

map wireless links in at least some of the routes to timeslots of a frame to form a plurality of synchronized paths between the access nodes and the gateways;

iteratively add, or remove, an individual one of the plurality of synchronized paths to, or from, a TDM routing schedule according to each individual state in a state progression of a Markov chain, the TDM routing schedule including a different subset of synchronized paths for each state in the Markov chain; and

instruct the access nodes and the one or more gateways to communicate messages over the wireless links according the TDM routing schedule.

23. The computer program product of claim 22, wherein the state progression through the Markov chain progresses through fewer than all states in the Markov chain.

24. The computer program product of claim 22, wherein each state in the progression through states of the Markov chain maps a different combination of synchronized paths to the TDM routing schedule.