Distributed Opportunistic Scheduling For Ad-Hoc Communications Under Delay Constraint
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 a; or 2) individual user constraints where the average delay per user should be no greater than a m, 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 a*. If a is less than a*, the optimal rate threshold depends on a; 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 2010
- Accession Number
- ADA515840
Entities
People
- Dongqi Zheng
- James Zeidler
- Junsham Zhang
- Sheu-sheu Tan
Organizations
- University of California, San Diego