Please use this identifier to cite or link to this item:
Title: K Bipartite Partitioning Algorithm for Channel Allocation Problem in Wireless Mesh Networks
Authors: Misra, R.
Shukla, A.
Keywords: Wireless Mesh Networks
Issue Date: Jan-2010
Publisher: IEEE Xplore
Abstract: 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-topoint 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.
Appears in Collections:2009

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.