Abstract:
At the heart of wireless network operation is the fundamental question of their capacity:
How much communication can be achieved in a network, utilizing all the tools and diversity available: power control, scheduling, routing, channel assignment and rate adjustment?
The obvious aims of obtaining general purpose algorithms to solve this question run into two challenges:
- How to model communication and interference faithfully, and
- How to reason algorithmically in the more accurate models, which are also more intricate and harder to analyze.
We overview recent progress in developing algorithms for capacity and scheduling in the physical (or SINR) model with good performance guarantees on arbitrary networks. In particular, we indicate how many of the complications of the physical models can be abstracted away, at a small cost in performance. We also outline various efforts to add additional realism to the models, while maintaining generality and algorithmic tractability. We conclude with open questions and challenges. This is based on joint work with Tigran Tonoyan.
Bio: Magnús M. Halldorsson is a professor in the School of Computer Science of Reykjavik University, where he is the Director of Icelandic Center of Excellence in Theoretical Computer Science (ICE-TCS). He received his Ph.D. in 1991 from Rutgers University and worked at Tokyo Institute of Technology, Japan Advanced Institute of Science and Technology, University of Iceland, and Iceland Genomics. For the last decade, he has focused on algorithms for wireless scheduling with provable performance guarantees. He founded the Workshop on Realistic Models and Algorithms for Wireless Networks (WRAWN) series that is a leading venue for algorithm theory in wireless networking. Along with his coauthors, he received Best Paper Awards from SIROCCO and ICALP this year.
Detailed information can be found online on the Frankel Center website.
Please be sure to spread the word to anyone you think may be interested.
Looking forward to seeing you on 27/11 at 14:00 in the Harry and Carol Saal Auditorium, Alon Building for Hi-Tech (37/202).
The Frankel Center for Computer Science
