Distributed Opportunistic Scheduling for Ad-Hoc Communications Under Delay Constraints

Abstract

With the convergence of multimedia applications and wireless communications, there is an urgent need for developing new scheduling algorithms to support real-time traffic with stringent delay requirements. However, distributed scheduling under delay constraints is not well understood and remains an under-explored area. A main goal of this study is to take some steps in this direction and explore the distributed opportunistic scheduling (DOS) with delay constraints. Consider a network with M links which contend for the channel using random access. Distributed scheduling in such a network requires joint channel probing and distributed scheduling. Using optimal stopping theory, we explore DOS for throughput maximization, under two different types of average delay constraints: 1) a network-wide constraint where the average delay should be no greater than ?; or 2) individual user constraints where the average delay per user should be no greater than a <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</sub> , m = 1,..., M. Since the standard techniques for constrained optimal stopping problems are based on sample-path arguments and are not applicable here, we take a stochastic Lagrangian approach instead. We characterize the corresponding optimal scheduling policies accordingly, and show that they have a pure threshold structure, i.e. data transmission is scheduled if and only if the rate is above a threshold. Specifically, in the case with a network-wide delay constraint, somewhat surprisingly, there exists a sharp transition associated with a critical time constant, denoted by ?*. If a is less than ?*, the optimal rate threshold depends on ?; otherwise it does not depends on a at all, and the optimal policy is the same as that in the unconstrained case. In the case with individual user delay constraints, we cast the threshold selection problem across links as a non-cooperative game, and establish the existence of Nash equilibria. Again we observe a sharp transition associated with critical time constants {? <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</sub> <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">*</sup> }, in the sense that when ? <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</sub> ? a <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</sub> <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">*</sup> for all users, the Nash equilibrium becomes the same one as if there were no delay constraints.