Maximum throughput and fair bandwidth allocation in multi-channel wireless mesh networks

Wireless mesh network is designed as an economical solution for last-mile broadband Internet access. In this paper, we study bandwidth allocation in multi-channel multihop wireless mesh networks. Our optimization goals are to maximize the network throughput and, at the same time, to enhance fairness. First, we formulate and present an Linear Programming (LP) formulation to solve the Maximum throughput Bandwidth Allocation (MBA) problem. However, simply maximizing the throughput may lead to a severe bias on bandwidth allocation among wireless mesh nodes. In order to achieve a good tradeoff between fairness and throughput, we consider a simple max-min fairness model which leads to high throughput solutions with guaranteed maximum minimum bandwidth allocation values, and the well-known Lexicographical Max-Min (LMM) model. Correspondingly, we formulate the Max-min guaranteed Maximum throughput Bandwidth Allocation (MMBA) problem and the Lexicographical Max-Min Bandwidth Allocation (LMMBA) problem. For the former one, we present an LP formulation to provide optimal solutions and for the later one, we propose a polynomial time optimal algorithm.