Joint routing and scheduling in wireless mesh networks

Abstract

Spatial Time Division Multiple Access (STDMA) networks are immune from the hidden-and exposed-terminal problems inherent in a multi-hop Carrier Sensing Multiple Access/Collision Avoidance (CSMA/CA) network. In this thesis, we study three important issues in the design of an STDMA wireless mesh network. We first study slot assignment, routing and scheduling schemes for SISO and MIMO wireless mesh networks respectively. Conventional algorithms are usually link-based and scheduling in each slot is fixed and done for links. When the scheduled link is in deep fade or has no traffic, the slot given to that link will be wasted. In this thesis, we present a node-based scheme in which scheduling in each slot is done for nodes. Since a node has multiple links, it allows the exploitation of multi-user diversity. For SISO networks, the proposed scheme can achieve a throughput gain between 35% and 70% for some typical topologies tested in our study. For MIMO networks, the throughput gain is 33% to 45%. As new network applications have arisen rapidly in recent years, it is becoming more difficult to predict the exact traffic matrix of a network. The second topic we explore is how to use oblivious routing techniques to handle traffic uncertainty in a wireless mesh network. Oblivious routing intends to use one routing scheme to achieve a predicable performance for a set of traffic matrices. Prior works on the design of oblivious routing and slot assignment fail to exploit a key feature of a wireless network that can be used to tackle traffic uncertainty: link capacities can be dynamically assigned as the traffic demand changes. Based on this insight, we propose a new oblivious-routing framework for STDMA wireless mesh networks. Our simulation results indicate that the oblivious ratios of the proposed node-based scheme can be 61% and 57% lower than that of the conventional link-based scheme for the tested grid and the random topology respectively. We also present a new approach for energy conservation routing, which is an important design issue for battery-powered wireless mesh networks. We study the problem when traffic demand uncertainties are present. Our new approach does not suffer from the two problems prevalent in conventional oblivious routing designed for energy conservation networks: the inaccuracy caused by the adoption of the protocol interference model and the instability caused by the assumption of unbounded transmission power and data rate. Our approach intends to fix these problems. We propose two energy conservation routing frameworks: one is node based and the other link based. The node-based framework can explore the dynamic bandwidth sharing feature of a wireless network and leads to a higher throughput and longer network lifetime. For the gateway traffic model, which is a common assumption for studying mesh networks, the gains of a node based scheme in throughput and network lifetime over those of a link-based scheme are 14% and 24% respectively. However, regarding to the mesh traffic model, the two frameworks allow comparable network lifetime and system throughput.

Date of Award	2013
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology