Capacity Characterization in Wireless Mesh Networks with 802.11a/b/g Multi-Mode Radios

The wireless mesh network (WMN) is designed as an economical solution for last-mile broadband Internet access. Some commercial applications have emerged, such as “community wireless networks”. These WMNs offer increased reliability, coverage and reduced infrastructure costs over their single-hop counterpart, namely wireless LANs. Providing broadband access to Internet is their major objective. Equipping mesh nodes with multiple radios can further improves the network capacity by transmitting over multiple radios simultaneously using orthogonal channels. Efficient channel assignment and routing are essential to capture the benefits of them. However, most previous studies only focus on heuristic approaches. In this thesis, our objective is to investigate the capacity region of 802.11 based multi-radio multi-channel wireless mesh networks for network designers to plan network deployment. First, we present a network model which captures the characteristics of 802.11 MAC mechanism and 802.11 a/b/g multi-mode radio, including RTS/CTS/DATA/ACK handshake, wireless interference, adaptive data rates, orthogonal channels, multi-mode radios, and evaluate the performance. Then, we formulate the problem as a linear programing (LP) in wireless mesh networks with 802.11 a/b/g multi-mode radios. And we evaluate the performance in the three different topologies to analyze the affects of each parameter. Finally, we extend our formulation and discuss the impact of gateway placement, wired bandwidth limitation and fairness schemes on the performance of wireless mesh networks. Our work can be used for planning of wireless mesh networks with respect to the performance trade-offs of different important deployment parameters.ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii LIST OF TABLES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi LIST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii CHAPTER 1 INTRODUCTION . . . . . . . . . . . . . . . . . . . . . 1 CHAPTER 2 BACKGROUND . . . . . . . . . . . . . . . . . . . . . . 4 2.1 IEEE 802.11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.1.1 IEEE 802.11 Architecture . . . . . . . . . . . . . . . . . . . . 4 2.1.2 Physical Layer . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1.3 Medium-Access Control (MAC) Layer . . . . . . . . . . . . . 6 2.2 Wireless Mesh Networks . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2.1 A Case Study of MIT Roofnet . . . . . . . . . . . . . . . . . 11 2.2.2 WMNs in Taiwan . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3 Exploiting Multiplicity in Wireless Mesh Networks . . . . . . . . . . 12 2.3.1 Using Multi-Radio and Multi-Channel . . . . . . . . . . . . . 13 2.3.2 Multi-Radio Multi-Channel Protocols . . . . . . . . . . . . . 16 2.4 Capacity Characterization in Wireless Mesh Networks . . . . . . . . 20 2.4.1 Asymptotic Approaches . . . . . . . . . . . . . . . . . . . . . 20 2.4.2 Optimization Approaches . . . . . . . . . . . . . . . . . . . . 21 CHAPTER 3 OPTIMIZATION FRAMEWORK . . . . . . . . . . . 26 3.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.1.1 Node Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.1.2 Network Model . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.1.3 Interference Model . . . . . . . . . . . . . . . . . . . . . . . . 29 3.2 LP Formulation (I) . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.2.1 Upper Bound Using Maximal Cliques . . . . . . . . . . . . . 33 3.2.2 Lower Bound Using Maximal Independent Sets . . . . . . . . 36 3.2.3 Issues with Maximal Independent Sets and Maximal Cliques 37 3.3 LP Formulation (II) . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.3.1 Upper Bound Using Node Interference Pairs . . . . . . . . . 40 3.3.2 Lower Bound Using Link Interference Sets . . . . . . . . . . 40 CHAPTER 4 SIMULATION RESULTS AND ANALYSIS . . . . . 43 4.1 Chain Topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.1.1 Impact of Number of Channels . . . . . . . . . . . . . . . . . 43 4.1.2 Impact of Interference Range . . . . . . . . . . . . . . . . . . 44 4.1.3 Impact of Number of Radios . . . . . . . . . . . . . . . . . . 45 4.2 Grid Topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 4.2.1 Starvation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 4.2.2 Effect of number of MISs and cliques . . . . . . . . . . . . . 47 4.2.3 Impact of Number of Flows . . . . . . . . . . . . . . . . . . . 49 4.2.4 Impact of Number of Radios . . . . . . . . . . . . . . . . . . 50 4.2.5 Heterogeneous Radio Systems . . . . . . . . . . . . . . . . . 51 4.2.6 Impact of Gateway Placement . . . . . . . . . . . . . . . . . 51 4.3 Roofnet Topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.3.1 Impact of Number of Radios . . . . . . . . . . . . . . . . . . 53 4.3.2 Interference between 802.11b and 802.11g . . . . . . . . . . . 56 4.3.3 Impact of Number of Gateways . . . . . . . . . . . . . . . . . 56 CHAPTER 5 EXTENSION OF THE OPTIMIZATION FRAMEWORK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 5.1 Gateway Placement . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 5.1.1 Simulation Setup and Results . . . . . . . . . . . . . . . . . . 60 5.2 Wired Bandwidth Limitation . . . . . . . . . . . . . . . . . . . . . . 62 5.2.1 Simulation Setup and Results . . . . . . . . . . . . . . . . . . 64 5.3 Fairness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 5.3.1 Simulation Setup and Results . . . . . . . . . . . . . . . . . . 66 5.4 Other Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 CHAPTER 6 CONCLUSIONS AND FUTURE WORK . . . . . . . 69 REFERENCES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7