Backpressure scheduling in IEEE 802.11 wireless mesh networks: Gap between theory and practice

Abstract

Achieving efficient bandwidth utilization in wireless networks requires solving two important problems: (1) which packets to send (i.e., packet scheduling) and (2) which links to concurrently activate (i.e., link scheduling). To address these scheduling problems, many algorithms have been proposed and their throughput optimality and stability are proven in theory. One of the most well-known scheduling algorithms is backpressure scheduling which performs both link and packet scheduling assuming a TDMA (Time Division Multiple Access) MAC (Medium Access Control) layer. However, there has been limited work on realizing backpressure scheduling with a CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance) MAC layer (e.g., IEEE 802.11). In IEEE 802.11 networks, it is expected that the throughput optimality will not be achieved. In this paper, we investigate the extent of this throughput gap between theoretical TDMA-based backpressure scheduling and an approximation of it for IEEE 802.11 WMNs (Wireless Mesh Networks). Through extensive testbed measurements, we verify that there is indeed a non-negligible throughput gap. We present two main reasons behind this gap: Control inaccuracy that results from approximation of link scheduling and information inaccuracy that results from late or incorrect information, for instance, about queue lengths or network topology. Our results show that losses by MAC-layer collisions and backoff, which mainly occur due to control inaccuracy plays a major role for the throughput gap. On the other hand, while losses by queue drops, typically due to information inaccuracy, do occur, their effect can be tolerated. Nevertheless, both types of inaccuracies need to be mitigated in order to improve throughput. (C) 2012 Elsevier B.V. All rights reserved.