K Bipartite Partitioning Algorithm for Channel Allocation Problem in Wireless Mesh Networks

Providing low-cost broadband internet access in rural area use either IEEE 802.11/802.16 based optimized network topology. Even using directional antenna, the point-to-point links at a transmitting node suffer from Mix-Tx-Rx interference when simultaneously receiving on another link due the presence of side lobes. Existing 2P MAC protocol allocate channels to the links assuming the network topology as bipartite graph. Thus, channel allocation problem can be modeled as partition of graph into bipartite subgraphs to run the 2P MAC protocol independently within each subgraph for the channels. Finding an optimal channel allocation that minimizes the mismatch between desired and achieved link capacities is NP-hard. If K channels are available then the heuristic to select K bipartite subgraphs to run 2P MAC simultaneously improves channel allocation problem. This paper proposes a new algorithm for partitioning the underlying graph into K bipartite sub graphs for channel allocation problem. The application of this technique lies in rural mesh network in providing low-cost internet access in the rural areas. Our K bipartite partition algorithm identifies K bipartite partitions and improves the approximation close to the optimal.