Association, routing and scheduling algorithms for enhancing throughput and fairness in wireless mesh networks

Wireless mesh networks (WMNs) have emerged as a promising step towards the goal of ubiquitous broadband wireless access due to the ease of deployment and its low cost. Current research on WMNs aims at a number of challenges, including capacity limitation and poor fairness.;In this thesis we carefully design association, routing and scheduling algorithms to enhance throughput and fairness in WMNs. The association mechanism specified by the IEEE 802.11 standard is based on the received signal strength. Employing this mechanism in WMNs may only achieve low throughput and low user transmission rates. We develop a new association framework in order to provide optimal association and network performance in WMNs. In this framework, we first propose two new access link metrics that are aware of channel condition, channel access contention as well as AP load. We then extend association mechanisms based on such metrics in a cross-layer manner taking into account information from the routing layer, in order to fit it in the operation of WMNs. We evaluate the performance of our system through simulations, and show that WMNs that use the proposed association mechanism can achieve up to 100% improvement in throughput and delay.;Contention-based MAC protocols such as 802.11 greatly limit the throughput and fairness of WMNs. Significantly higher throughput and fairness are achievable if bandwidth is carefully allocated and transmissions are scheduled. To study the performance limits of WMNs, we first optimally allocate bandwidth to each data flow, jointly computing the user-router association and backbone routing solutions, such that network throughput can be maximized while certain fairness is achieved. We then focus on the integral association, single-path routing case and investigate the optimal performance of a WMN on a given tree topology. We also develop an efficient scheduling algorithm to coordinate channel access and to enforce the allocated bandwidth. Our evaluation shows that association and routing have a great impact on bandwidth allocation, namely constructing a good topology can improve throughput while enhancing fairness.;Finally, multiple channel and Multiple-Input-Multiple-Output (MIMO) are two technologies being introduced into WMNs to mitigate interference and increase network capacity. Higher layer protocols need to be aware of these techniques in order to fully leverage their benefits, which makes cross-layer approach desirable. We first formulate a cross-layer optimization framework for maximizing an aggregate utility, which jointly allocates link bandwidth for data flows, and determines channel assignment and MIMO stream selection. We then present an efficient MIMO-aware scheduling algorithm called stream controlled multiple access (SCMA). SCMA determines a baseline schedule in the channel assignment stage where a set of non-interfering links are scheduled on each channel. The second stage of SCMA, link pairing, takes advantage of the performance gain of MIMO stream control. SCMA also incorporates a congestion control scheme at traffic sources to prevent the network from being overloaded. Simulation results show that the MIMO-aware scheduling algorithm leads to about 50%∼100% higher throughput while preserving fairness than the MIMO-oblivious algorithm. It achieves close-to-the-optimal performance in certain scenarios.