Randomized mesh network routing
First Claim
Patent Images
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
24 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
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. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20, 21)
-
-
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. - View Dependent Claims (23, 24)
-
Specification