Method for channel assignment and routing for multi-radio wireless mesh networks
First Claim
1. 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, by a network element, 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 second adjusted flow to eliminate all interference over said plurality of channels;
generating an interference free link schedule from said scaled, second adjusted flow; and
sending said interference free link schedule said first routing, and said second routing to said plurality of nodes 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
27 Claims
-
1. 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, by a network element, 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 second adjusted flow to eliminate all interference over said plurality of channels; generating an interference free link schedule from said scaled, second adjusted flow; and sending said interference free link schedule said first routing, and said second routing to said plurality of nodes 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, by a network element, 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 second adjusted flow to eliminate all interference over said plurality of channels; generating an interference free link schedule from said scaled, second adjusted flow; and sending said interference free link schedule, said first routing, and said second routing to said plurality of nodes across said wireless mesh network for exchanging communications between said plurality of nodes. - View Dependent Claims (19, 20)
-
-
21. A method for making channel and routing assignments in a wireless mesh network comprising:
-
determining, by a network element, a set of possible data paths in a wireless mesh network based on information of a plurality of nodes, a plurality of channels, and a plurality of radios in the wireless mesh network; identifying first routing assignments of the plurality of channels and plurality of radios based on a possible data path from the set of possible data paths; adjusting the possible data path, based on channel assignment feasibility and maximum interference among the plurality of channels, to determine channel assignments and second routing assignments; scaling the adjusted possible data path to minimize interference over the plurality of channels; generating a link schedule for the wireless mesh network based on the adjusted possible data path and the scaled possible data path; and sending, by the network element, the channel assignments, the first and the second routing assignments, and the link schedule to the plurality of nodes. - View Dependent Claims (22, 23, 24, 25, 26, 27)
-
Specification