Patent ID: 8010121
Filing Date: 2011-08-30
Classification: H04W

Abstract:
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.