Randomized mesh network routing

Patent metadata

Field	Value
Publication number	US-9967045-B2
Application number	US-201615174452-A
Country	US
Kind code	B2
Filing date	Jun 6, 2016
Priority date	Jun 6, 2016
Publication date	May 8, 2018
Grant date	May 8, 2018

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.

First claim

What is claimed:

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 m

Assignees

• Huawei Tech Canada Co Ltd

Inventors

• Mccormick William Carson
• Kelly Francis Patrick

Classifications

• H04J3/1694 Primary

  Allocation of channels in TDM/TDMA networks, e.g. distributed multiplexers (Passive Optical Networks H04Q11/0062) · CPC title

• H04L1/002

  Algorithms with memory of the previous states, e.g. Markovian models · CPC title

• H04W72/1263

  Mapping of traffic onto schedule, e.g. scheduled allocation or multiplexing of flows · CPC title

• H04W84/18

  Self-organising networks, e.g. ad-hoc networks or sensor networks · CPC title

• H04W40/16 Primary

  based on interference · CPC title