Random Access Without Message Passing
Professor of Information Engineering, CUHK
Oct 30, 2008 (Thursday)
4:30pm - 5:30 pm
Rm. 121, Ho Sin Hang Engineering Building, CUHK
over thirty years, researchers have studied how good
can simple random access protocols work. Since 1992,
some of the distributed scheduling algorithms for
throughput maximization take the form of random access
as well, although message passing among the nodes
is required. Similarly, utility optimization with
infinite backlog has been achieved with the help of
message passing. Very recently, people have developed
a CSMA-type random access algorithm without message
passing that is proved to be utility-optimal. However,
it remains open whether even simpler ones, such as
Aloha-type random access, can achieve utility-optimality.
In this talk, we provide the first positive answer
to this question.
develop the first Aloha-type random access algorithm
that has no message passing yet is provably utility-optimal.
Rather than using the standard dual decomposition
and subgradient method, our development leverages
the broadcast nature of wireless medium and the idea
that distributed learning by each node of the history
of contention may be as effective as message passing.
Details on the optimality, convergence, and robustness
of the algorithms will be discussed in this talk.