Routing and Channel Allocation in Rural Wireless Mesh Networks

IEEE 802.11 Wi-Fi equipment based wireless mesh networks have recently been proposed as an inexpensive approach to connect far-flung rural areas. Such networks are built using high-gain directional antenna that can establish long-distance point- point links. In recent work~cite{Raman05}, a new MAC protocol named {em 2P} has been proposed that is suited for the interference pattern within such a network. However, the 2P protocol requires the underlying graph (for each 802.11 channel) to be bi-partite. Under the assumption that 2P is the MAC protocol used in the mesh network, we make the following contributions in this paper. Given $K$ non-interfering 802.11 channels, we propose a simple cut-based algorithm to compute $K$ bi-partite sub-graphs (on each of which the 2P protocol can be run separately). We establish the class of graphs that can thus be completely covered by $K$ bi-partite subgraphs. For the remaining set of graphs, we look into the ``price'' of routing all end-to-end demands over {em only} the bi-partite subgraphs. We analytically establish what fraction of the max flow of the original mesh-graph can be routed over the bi-partite subgraphs. Finally we look into the problem of mismatch between the load on a link (as computed by max flow) and it's effective capacity under a given channel allocation. We propose heuristics to cluster links with similar loads into the same bi-partite graphs (channels) and through comprehensive numerical simulations show that our heuristics come very close to the best possible flow.