Evènement pour le groupe Algorithmique Distribuée
|Date|| 2009-06-29 14:00-15:00|
|Titre||Computing Geometric Spanners Locally |
|Résumé||In this talk, I will discuss a project to develop efficient local distributed algorithms for
wireless communication by exploiting the geometry of wireless systems. A wireless
system is often modeled as a graph in the Euclidean space -- such as the Unit
Disk Graph (UDG) -- and geometric techniques are used to obtain insights about
the structure of such graphs. So far, we obtained insights that have led us to the
development of the currently most efficient local algorithms to construct:
1) a bounded-degree plane spanner of a UDG (useful for unicasting) and
2) a bounded-degree *lightweight* plane spanner of a UDG (useful for
unicasting and broadcasting).
I will describe the insights and techniques we developed.
There are still questions left open. It is not clear, for example, that the geometry
has been fully exploited. Lower bound arguments have also not been made.
Finally, we have not dealt with the issue of interference -- critical for battery
powered mobile devices. I will finish the talk by bringing up those questions.
|Lieu||Salle 178 |
|Orateur||Ljubomir Perkovic |
|Url||School of Computing, DePaul University |
Aucun document lié à cet événement.RetourRetour à l'index