Non-bifurcated routing and scheduling in wireless mesh networks

Abstract

Multi-hop wireless mesh networks (WMNs) provide a cost-effective means to enable broadband wireless access (BWA) services to end users. Such WMNs are required to support different classes of traffic where each class requires certain quality of service (QoS) levels. The research direction undertaken in this thesis considers the development of enhanced routing and scheduling algorithms that enable WMNs to support various QoS metrics for the served traffic. A fundamental class of routing problems in WMNs asks whether a given end-to-end flow that requires certain bandwidth, and benefits from routing over a single path (also called non-bifurcated routing), can be routed given that some ongoing flows are being served in the network. In the thesis, we focus on the development of combinatorial algorithms for solving such incremental non-bifurcated problems for two types of WMNs:

WMNs where mesh routers use contention-based protocol for medium access control (MAC), and WMNs where mesh routers use time division multiple access (TDMA) for MAC. For WMNs employing contention-based MAC protocols, we present a novel non-bifurcated routing algorithm that employs techniques from the theory of network flows. The main ingredient in our algorithm is a method for computing interference-constrained flow augmenting paths for routing subscriber demands in the network. For WMNs employing TDMA, we develop a number of joint routing and scheduling algorithms, and investigate the use of such algorithms to maximize the number of served flows. In chapter 4, we consider a throughput maximization problem in the well-known class of grid WMNs. We present an iterative algorithm that strives to achieve high throughput by considering routing and scheduling a pair of distinct flows simultaneously to the gateway in each iteration. In chapter 5, we explore joint routing and scheduling in TDMA-based WMNs with arbitrary topologies, and devise an algorithm that can deal with arbitrary interference relations among pairs of transmission links. In particular, our devised algorithm solves a generalized problem where a cost value is associated with using any possible time-slot on any transmission link, and a minimum cost route is sought along which a new flow can be scheduled without perturbing existing slot assignments.