Speaker: Magnus Halldorsson
Title: Algorithmic models of wireless communication
Wireless communication continues to have tremendous social impact. From an algorithmic point of view, a major challenge in wireless computing is to find general models of interference that are both realistic and analytically feasible. The previously studied graph models lack the fading and the additivity properties of real-world wireless communication.
We survey recent work on algorithms in the SINR or physical model, focusing on the core MAC-layer problems of link scheduling and throughput maximization. These can be viewed as vertex subset and partitioning problems on directed edge-weighted graphs, with "independence" denoting sufficiently low weighted-indegree. We find that these graphs satisfy a small "weighted inductive independence", allowing for good throughput approximations. With appropriate power control, we show that we can actually achieve locality in the SINR model, leading to efficient solution of certain scheduling problems as well.
Parts of this research are joint work with Pradipta Mitra, Stephan Holzer and Roger Wattenhofer.