TY - GEN
T1 - Distributed opportunistic scheduling for ad-hoc communications under delay constraints
AU - Tan, Sheu Sheu
AU - Zheng, Dong
AU - Zhang, Junshan
AU - Zeidler, James
PY - 2010
Y1 - 2010
N2 - 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 α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 α*. If α is less than α*, the optimal rate threshold depends on α; otherwise it does not depends on α 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 {αm*}, in the sense that when αm ≥ αm* for all users, the Nash equilibrium becomes the same one as if there were no delay constraints.
AB - 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 α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 α*. If α is less than α*, the optimal rate threshold depends on α; otherwise it does not depends on α 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 {αm*}, in the sense that when αm ≥ αm* for all users, the Nash equilibrium becomes the same one as if there were no delay constraints.
UR - http://www.scopus.com/inward/record.url?scp=77953296722&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77953296722&partnerID=8YFLogxK
U2 - 10.1109/INFCOM.2010.5462120
DO - 10.1109/INFCOM.2010.5462120
M3 - Conference contribution
AN - SCOPUS:77953296722
SN - 9781424458363
T3 - Proceedings - IEEE INFOCOM
BT - 2010 Proceedings IEEE INFOCOM
T2 - IEEE INFOCOM 2010
Y2 - 14 March 2010 through 19 March 2010
ER -