Efficient traffic diversion and load-balancing in multi-hop wireless mesh networks

Wireless Mesh Networks (WMNs) are one of the upcoming technologies which envision providing broadband internet access to users any where any time. WMNs comprise of Internet Gateways (IGWs) and Mesh Routers (MRs). They seamlessly extend the network connectivity to Mesh Clients (MCs) as end users by forming a wireless backbone that requires minimal infrastructure. For WMNs, frequent link quality fluctuations, excessive load on selective links, congestion, and limited capacity due to half-duplex nature of radios are some key limiting factors that hinder their deployment. Also, other problems such as unfair channel access, improper buffer management, and irrational routing choices are impeding the successful large scale deployment of mesh networks. Quality of Service (QoS) provisioning and scalability in terms of supporting large number of users with decent bandwidth are other important issues.In this dissertation, we examine some of the aforementioned problems in WMNs and propose novel algorithms to solve them. We find that the proposed solutions enhance the network's performance significantly. In particular, we provide a traffic differentiation methodology, Dual Queue Service Differentiation (DQSD), which helps in fair throughput distribution of network traffic regardless of spatial location of its nodes. We next focus on managing the IGWs in WMNs since they are the potential bottleneck candidates due to huge volume of traffic that has to flow through them. To address this issue, we propose a load balancing protocol, LoaD BALancing (LDBAL), which efficiently distributes the traffic load among a given set of IGWs. We then delve into the aspects of load balancing and traffic distribution over multiple traffic paths in WMNs. To achieve this, we propose a novel Adaptive State-based Multipath Routing Protocol (ASMRP) that provides reliable and robust performance in WMNs. We also employ four-radio architecture for MRs, which allows them to communicate over multiple radios tuned to non-overlapping channels and better utilize the available spectrum. We show that our protocol achieves significant throughput improvement and helps in distributing the traffic load for efficient resource utilization. Through extensive simulations, we observe that ASMRP substantially improves the achieved throughput (&sim5 times gain in comparison to AODV), and significantly minimizes end-to-end latencies. We also show that ASMRP ensures fairness in the network under varying traffic load conditions.We then focus on prudent user admission strategy for IGWs and other Wireless Service Providers (WSPs). WSPs typically serve diverse user base with heterogeneous requirements and charge users accordingly. In scenarios where a WSP is constrained in resources and have a predefined objective such as revenue maximization or prioritized fairness, a prudent user selection strategy is needed to optimize it. In this dissertation, we present an optimal user admission/allocation policy for WSPs based on yield management principles and discrete-time Markov Decision Process model to maximize its potential revenue. We finally conclude with a summary of our results and some pointers for future research directions.