Routing and Topology Control in Multi-Hop, Multi-Channel, and Multi-Radio Wireless Mesh Networks

This dissertation investigates important problems in Wireless Mesh Networks (WMN). We first conduct a comprehensive survey of routing algorithms for wireless networks. This survey provides a classification to categorize these routing algorithms and analyzes as well as compares them based on the main characteristics of these algorithms.;Good link-aware routing metrics are important for multi-hop WMNs. Channel-to-link assignments impact the distribution of co-channel links and contribute to inter-flow and intra-flow interference. We present A Location-Aware Routing Metric (ALARM) that better captures the resulting co-channel interference as a function of channel assignments in the multi-channel and multi-radio environment. The link metrics used are sensitive to the location of co-channel links within interference or carrier-sensing range; these can be pre-calculated and used with any routing algorithm. ALARM's performance is compared to the Weighted Cumulative Expected Transmission Time metric (WCETT) over a range of network parameters for linear and grid topologies.;Next, we develop an interference-aware link-capacity model that selects the optimal set of routes for the existing traffic workload. In this model, we categorize the interferers of each link, based on their location and influence on the reference link, to measure the reference-link's available capacity. This model, which is compatible with the IEEE-802.11 protocol, is evaluated by comparing its performance with the performance of a non-interference-aware routing algorithm.;Finally, we present a design solution for Topology, Capacity, and Flow Assignment (TCFA) in a WMN. We focus on minimizing the number of links in the topology and overall network traffic subject to interference, capacity, and flow constraints. First, we study different interference models: the combined single-equation model (where all interfering links are active at the same time), the separate-equation model (where each interfering link is modeled in a separate equation), and the multi-equation model (where interfering links are distributed into groups of non-overlapping interfering links). Then, we study the relation between the number of links in the topology and the overall network delay.