The world is becoming increasingly more interconnected, and much of that connectivity is wireless. The operation of wireless equipment is expected to become more and more software controlled, requiring > advanced algorithms. Algorithmic work on wireless networks have until recently been largely confined to graph-based models that don't respect the physical properties of the medium, including fading, additivity, and non-locality.
We survey in this talk work of the last three years on algorithms for the physical (or SINR) model of wireless communication. We examine the main algorithmic strategies that have led to provable performance guarantees, and pinpoint the properties and intuition that has been uncovered.
We conclude with results appearing in the upcoming SODA 2012 (joint work with Pradipta Mitra) that show that any set of $n$ points in the plane can > be strongly connected using $(log n) slots. This implies that the worst-case capacity of wireless sensor networks computing compressible functions is $Omega(1/log n)$.
Magnus M. Halldorsson received his Ph.D. from Rutgers University in1991. He worked at different universities in Japan before returning to his native country of Iceland in 1995. He worked at University of > Iceland in different position, becoming full professor in 2001.
Since 2007 he has been a full professor at Reykjavik University, wherehe currently also serves as vice-dean of the School of Computer Science and chairman of the Reykjavik University's Research Council.
He received the primary research award (the Motivation Award for young scientists) in Iceland in 2001 and the Reykjavik University's first > research award in 2010.