Gegnerische Modelle für drahtlose Kommunikation (Adversarial Models for Wireless Communication)
Final Report Abstract
Funknetze setzen sich zunehmend gegenüber herkömmlichen Datennetzen durch. Allerdings sind Funknetze sehr verwundbar gegenüber Interferenzproblemen, so dass bereits einige Anstrengungen unternommen worden sind, diese in den Griff zu bekommen. In der Theorie sind Interferenzprobleme bisher nur sehr vereinfacht modelliert worden, so dass die Modelle nicht sonderlich realistisch sind und bestenfalls einen kleinen Teil der Ursachen für Interferenzprobleme abdecken konnen. Ziel des Projektes war es, Modelle für Interferenzprobleme zu entwickeln, die ein möglichst breites Spektrum an Ursachen, von elektrischen Geräten und coexistierenden Funknetzen bis hin zu gegnerischem Jamming, abdecken konnen. Weiterhin sollten Protokolle für den Austausch von Botschaften zwischen Systemen in Funkreichweite, sogenannte MAC Protokolle, entworfen werden, die einen beweisbar guten Durchsatz für diese Interferenzmodelle haben. Wir haben dabei verschiedene Modelle betrachtet, die verschiedene Aspekte berücksichtigen: • Interferenzen werden durch coexistierende Funknetze, adaptive Gegner (die den Funkkanal bewusst ausgehend vom Zustand der Knoten am Anfang einer Kommunikationsrunde stören konnen), oder sogar reaktive Gegner (welche Informationen über aktuelle Sendeaktivitäten nutzen konnen, um gezielt zu jammen) verursacht. • Interferenzen durch die Kommunikation von Teilnehmern betreffen alle anderen Teilnehmer (singlehop Netze), nur einen beschrankten Teilnehmerkreis (multi-hop Netze), oder schwächen sich mit der Distanz ab (SINR Modelle). Das Ergebnis dieses Projekts ist eine Reihe von Modellen und MAC Protokollen, die für diese unterschiedlichen Szenarien beweisbar robust sind in dem Sinne, dass diese einen konstanten Bruchteil der Zeitschritte, in denen der Funkkanal verfügbar ist, für erfolgreiche Botschaftsübertragungen nutzen können. Die theoretischen Analysen sind dabei durch Simulationen untermauert worden. Unsere Arbeiten haben bereits viele andere Arbeiten nach sich gezogen.
Publications
- Competitive and fair throughput for co-existing networks under adversarial interference. In Proc. 31st Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 291-300, 2012
Andrea W. Richa, Christian Scheideler, Stefan Schmid, and Jin Zhang
- Special Issue on Algorithmic Aspects of Wireless Sensor Networks. Theoretical Computer Science 453, 2012
Shlomi Dolev and Christian Scheideler
- An Efficient and Fair MAC Protocol Robust to Reactive Interference. IEEE/ACM Transactions on Networking 21(3): 760-771, 2013
Andrea W. Richa, Christian Scheideler, Stefan Schmid, and Jin Zhang
(See online at https://doi.org/10.1109/TNET.2012.2210241) - Competitive throughput in multi-hop wireless networks despite adaptive jamming. Distributed Computing 26(3): 159-171, 2013
Andrea W. Richa, Christian Scheideler, Stefan Schmid, and Jin Zhang
(See online at https://doi.org/10.1007/s00446-012-0180-x) - Competitive MAC under adversarial SINR. In 2014 IEEE Conference on Computer Communications (INFOCOM), pages 2751-2759,2014
Adrian Ogierman, Andrea W. Richa, and Christian Scheideler, Stefan Schmid, Jin Zhang
(See online at https://doi.org/10.1109/INFOCOM.2014.6848224) - Principles of Robust Medium Access and an Application to Leader Election. ACM Transactions on Algorithms 10(4), Article no. 24, 2014
Baruch Awerbuch, Andrea W. Richa, Christian Scheideler, Stefan Schmid and Jin Zhang
(See online at https://doi.org/10.1145/2635818) - Jamming-Resistant MAC Protocols for Wireless Networks. Encyclopedia of Algorithms 2015
Andrea W. Richa and Christian Scheideler
