Name
Abstract | ||
|---|---|---|
We consider a widely applicable model of resource allocation where two sequences of events are coupled: on a continuous time axis (t), network dynamics evolve over time. On a discrete time axis [t], certain control laws update resource allocation variables according to some proposed algorithm. The algorithmic updates, together with exogenous events out of the algorithm's control, change the network dynamics, which in turn changes the trajectory of the algorithm, thus forming a loop that couples the two sequences of events. In between the algorithmic updates at [t - 1] and [t], the network dynamics continue to evolve randomly as influenced by the previous variable settings at time [t - 1]. The standard way used to avoid the subsequent analytic difficulty is to assume the separation of timescales, which in turn unrealistically requires either slow network dynamics or high complexity algorithms. In this paper, we develop an approach that does not require separation of timescales. It is based on the use of stochastic approximation algorithms with continuous-time controlled Markov noise. We prove convergence of these algorithms without assuming timescale separation. This approach is applied to develop simple algorithms that solve the problem of utility-optimal random access in multi-channel, multiradio wireless networks. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1109/INFCOM.2010.5462201 | INFOCOM |
Keywords | Field | DocType |
Markov processes,channel allocation,multi-access systems,radio networks,continuous time controlled Markov noise,exogenous events,multiradio wireless networks,network dynamics,resource allocation,stochastic approximation algorithms,timescale separation,utility optimal random access | Approximation algorithm,Wireless network,Mathematical optimization,Markov process,Network dynamics,Computer science,Markov chain,Resource allocation,Discrete time and continuous time,Stochastic approximation,Distributed computing | Conference |
ISSN | Citations | PageRank |
0743-166X | 32 | 1.23 |
References | Authors | |
9 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alexandre Proutiere | 1 | 558 | 40.94 |
| Yung Yi | 2 | 1557 | 104.55 |
| Tian Lan | 3 | 126 | 25.44 |
| Mung Chiang | 4 | 7303 | 486.32 |