Method for channel assignment and routing for multi-radio wireless mesh networks
First Claim
1. A method for making joint channel and routing assignments in a wireless mesh network, said wireless mesh network having a plurality of nodes, a plurality of channels and a plurality of radios, said method comprising the steps of:
- generating a flow graph of said wireless mesh network as function of said plurality of nodes, said plurality of channels and said plurality of radios;
identifying, as a function of a throughput of said wireless mesh network and a set of fairness constraints, a first routing of said plurality of channels and said plurality of radios from a flow from said flow graph;
a first adjusting of said flow to ensure a feasible channel assignment among said plurality of channels in said first routing, said first adjusting resulting in a second routing of said plurality of channels and said plurality of radios;
a second adjusting of said flow as a function of a maximum interference level across each channel of said plurality of channels in said second routing;
scaling said adjusted flow to eliminate all interference over said plurality of channels;
generating an interference free link schedule from said scaled, adjusted flow; and
applying said interference free link schedule across said wireless mesh network for exchanging communications between said plurality of nodes.
3 Assignments
0 Petitions
Accused Products
Abstract
A methodology for making joint channel and routing assignments in multi-radio wireless mesh networks that takes into account interference constraints, the number of channels in a network and the number of radio available at each mesh router, and maximizes bandwidth allocation subject to fairness constraints. In particular, the methodology provides for routing, channel assignment and link scheduling in multi-radio mesh wireless networks utilizing a constant factor approximation technique that models the interference and fairness constraints and is able to account for the number of radios at each of the wireless nodes of a wireless mesh network.
-
Citations
20 Claims
-
1. A method for making joint channel and routing assignments in a wireless mesh network, said wireless mesh network having a plurality of nodes, a plurality of channels and a plurality of radios, said method comprising the steps of:
-
generating a flow graph of said wireless mesh network as function of said plurality of nodes, said plurality of channels and said plurality of radios;
identifying, as a function of a throughput of said wireless mesh network and a set of fairness constraints, a first routing of said plurality of channels and said plurality of radios from a flow from said flow graph;
a first adjusting of said flow to ensure a feasible channel assignment among said plurality of channels in said first routing, said first adjusting resulting in a second routing of said plurality of channels and said plurality of radios;
a second adjusting of said flow as a function of a maximum interference level across each channel of said plurality of channels in said second routing;
scaling said adjusted flow to eliminate all interference over said plurality of channels;
generating an interference free link schedule from said scaled, adjusted flow; and
applying said interference free link schedule across said wireless mesh network for exchanging communications between said plurality of nodes. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17)
-
-
18. An article of manufacture comprising a machine-readable medium storing one or more programs for use in making joint channel and routing assignments in a wireless mesh network, said wireless mesh network having a plurality of nodes, a plurality of channels and a plurality of radios, said one or more programs when executed in a processor performing the steps of:
-
generating a flow graph of said wireless mesh network as function of said plurality of nodes, said plurality of channels and said plurality of radios;
identifying, as a function of a throughput of said wireless mesh network and a set of fairness constraints, a first routing of said plurality of channels and said plurality of radios from a flow from said flow graph;
a first adjusting of said flow to ensure a feasible channel assignment among said plurality of channels in said first routing, said first adjusting resulting in a second routing of said plurality of channels and said plurality of radios;
a second adjusting of said flow as a function of a maximum interference level across each channel of said plurality of channels in said second routing;
scaling said adjusted flow to eliminate all interference over said plurality of channels;
generating an interference free link schedule from said scaled, adjusted flow; and
applying said interference free link schedule across said wireless mesh network for exchanging communications between said plurality of nodes. - View Dependent Claims (19, 20)
-
Specification