Maximizing Utility via Random Access without Message Passing

It has been an intensively sought-after goal to achieve high throughput and fairness in wireless scheduling through simple and distributed algorithms. Many recent papers on the topic have relied on various types of message passing among the nodes. The following question remains open: can scheduling without any message passing guarantee throughput-optimality and fairness? Over the last year, it has been suggested in three papers [1]–[3] that random access without message passing may be designed and proved to be optimal in terms of throughput and utility. In this paper, we first extend the algorithm in [2] and provide a rigorous proof of utility-optimality for random access without message passing for Poisson clock model. Then we turn to the more di cult discrete contention and backo model with collisions, study its optimality properties, and control a tradeo between long-term e ciency and short-term fairness that emerges in this model.

tr-2008-128.pdf
PDF file

Details

TypeTechReport
NumberMSR-TR-2008-128
Pages23
InstitutionMicrosoft Research
> Publications > Maximizing Utility via Random Access without Message Passing