Wireless Mesh Network Routing Under Uncertain Demands

Traffic routing plays a critical role in determining the performance of a wireless mesh network. Recent research results usually fall into two ends of the spectrum. On one end are the heuristic routing algorithms, which are highly adaptive to the dynamic environments of wireless networks yet lack the analytical properties of how well the network performs globally. On the other end are the optimal routing algorithms that are derived from the optimization problem formulation of mesh network routing. They can usually claim analytical properties such as resource use optimality and throughput fairness. However, traffic demand is usually implicitly assumed as static and known a priori in these problem formulations. In contrast, recent studies of wireless network traces show that the traffic demand, even being aggregated at access points, is highly dynamic and hard to estimate. Thus, to apply the optimization-based routing solution in practice, one must take into account the dynamic and uncertain nature of wireless traffic demand. There are two basic approaches to address the traffic uncertainty in optimal mesh network routing (1) predictive routing that infers the traffic demand with maximum possibility based in its history and optimizes the routing strategy based on the predicted traffic demand and (2) oblivious routing that considers all the possible traffic demands and selects the routing strategy where the worst-case network performance could be optimized. This chapter provides an overview of the optimal routing strategies for wireless mesh networks with a focus on the above two strategies that explicitly consider the traffic uncertainty. It also identifies the key factors that affect the performance of each routing strategy and provides guidelines towards the strategy selection in mesh network routing under uncertain traffic demands.