Channel allocation for wireless mesh networks
View Patent ↗An example embodiment includes determining a cut of a graph to obtain a bi-partite sub-graph, where the graph represents a plurality of nodes and links between the plurality of nodes in a wireless mesh network. A channel is assigned to the bi-partite graph, and the obtained bi-partite subgraph is removed from the graph. The determining, assigning and removing steps are repeated until the graph has been divided into k bi-partite subgraphs, where k is the number of channels being used for scheduling.
1. A method of channel allocation in a wireless mesh network, comprising:
determining, by a gateway, a cut of a graph to obtain a mesh bi-partite subgraph, the graph representing a plurality of nodes and links between the plurality of nodes in the wireless mesh network;
assigning, by the gateway, a channel to the mesh bi-partite subgraph;
removing, by the gateway, the obtained mesh bi-partite subgraph from the graph; and
repeating, by the gateway, the determining, assigning and removing steps until the graph has been divided into k mesh bi-partite subgraphs, where k is the number of channels being scheduled;
scheduling, by the gateway, different flows over the links between the plurality of nodes in each mesh bi-partite subgraphs based on demands from the plurality of nodes, wherein if the demand is asymmetric, the gateway reassigns the links in the mesh bi-partite subgraphs based on intervals of the links and median intervals of the links in each mesh bipartite subgraph, wherein the interval of the link is a range of allowed fraction of a capacity of the link;
bi-partite subgraphs based on demands from the plurality of nodes.
2. The method of claim 1 , further comprising:
scheduling, by the gateway, the mesh bi-partite subgraphs on the k channels.
3. The method of claim 2 , wherein the scheduling is performed by a 2-Phase (2-P) medium access control (MAC) protocol.
4. The method of claim 2 , further comprising:
determining, by the gateway, flows over the links between the plurality of nodes in each mesh bi-partite subgraphs based on demands from the plurality of nodes.
5. The method of claim 4 , wherein the flow is determined by running a linear program.
6. The method of claim 4 , wherein if the demand is asymmetric, the determining flows step performs a greedy algorithm to re-assign links to the mesh bi-partite subgraphs.
7. The method of claim 1 , further comprising:
determining, by the gateway, flows over the links between the plurality of nodes in each mesh bi-partite subgraphs based on demands from the plurality of nodes.
8. The method of claim 7 , wherein the flow is determined by running a linear program.
9. The method of claim 7 , wherein if the demand is asymmetric, the determining flows step performs a greedy algorithm to re-assign links to the mesh bi-partite subgraph.