Seminar Christian Betstetter: Synchronization

Synchronization and Dissemination in Self-Organizing Communication Networks




Christian Bettstetter
University of Klagenfurt and Lakeside Labs GmbH


ECCO Seminars: Thu Oct. 1, 2009, 2 pm,

Duration: 35-40 minutes



Communication networks interconnect an increasing number and diversity of entities, such as mobile devices, wearable computers, sensors, and embedded systems. This trend poses new challenges to the design and operation of networking algorithms and protocols. In particular, the increased system dynamics demands for adaptability, distributed operation, and autoconfiguration. One approach to these challenges is to increase the level of self-organization in networks, i.e. to design network functions in a way that centralized control is avoided and the desired behavior of the overall system emerges from local interactions between the individual entities. In this talk, we present two issues in self-organizing communication networks: synchronization and information dissemination.

The first part of the talk is about synchronization in wireless networks, more precisely on the synchronization of periodically repeating “time slots”. Such slot synchronization is an essential building block for medium access, scheduling of sleep phases, and collaborative sensing, to give some examples. Having been inspired by the biological phenomenon of synchronous flashing of fireflies, we have developed a method for self-organizing slot synchronization in wireless systems. It is based on the theory of pulse-coupled oscillators, but goes beyond this theory — from an engineering perspective — by taking into account inherent characteristics and capabilities of radio communications. The talk presents the basic ideas and shows some performance results.

The second part of the talk is about information dissemination in networks. A fundamental technique for information dissemination is flooding, used e.g. in wireless ad hoc networks and peer-to-peer networks. In its most simple form, flooding leads to many redundant and unnecessary transmissions. An optimization goal is to minimize the number of transmissions while still achieving “global outreach” of the sent message. Modeling a network as a random graph with given link probability between nodes, we ask: What is the minimum message forwarding probability of the nodes such that a flooding message reaches each network node with high probability? We show how to derive this probability using techniques from stochastics and graph theory.


Speaker bio:

Christian Bettstetter is professor and head of the Networked and Embedded Systems institute at the University of Klagenfurt. His main interests are in mobile wireless networking, network theory, and self-organization. He is also scientific director and founder of Lakeside Labs GmbH, a research and technology platform on self-organizing networked systems.

He studied electrical engineering and information technology at the Technische Universität München (TUM), receiving the Dipl.-Ing. degree in 1998. After a research stay at the University of Notre Dame, Christian joined the institute of communication networks at TUM, where he was a staff member until 2003. His doctoral thesis on ad hoc networks was awarded the Dr.-Ing (summa cum laude) degree in 2004. Before becoming a professor, Christian was a senior researcher at DoCoMo Euro-Labs for two years, doing research on medium access and ad hoc networks. Publications received the 2008 best paper award at the IEEE Vehicular Technology Conference and the 2004 outstanding paper award from the German ITG. He also co-authored the Wiley textbook 'GSM - Architecture, protocols and services.'


Five most relevant publications:

Alexander Tyrrell, Gunther Auer, and Christian Bettstetter. Emergent Slot Synchronization in Wireless Networks. Accepted for publication in IEEE Transactions on Mobile Computing.

Sérgio Crisóstomo, Udo Schilcher, Christian Bettstetter, and João Barros. Analysis of Probabilistic Flooding: How do we Choose the Right Coin? In Proc. IEEE Intern. Conf. on Communications (ICC), Dresden, Germany, June 14-18, 2009.

Alexander Tyrrell, Gunther Auer, and Christian Bettstetter. Biologically Inspired Synchronization for Wireless Networks. In Advances in Biologically Inspired Information Systems: Models, Methods, and Tools, Eds. Falko Dressler and Iacopo Carreras, in Series: Studies in Computational Intelligence, Springer, vol. 69, pp. 47-62, 2007.

Christian Prehofer and Christian Bettstetter. Self-Organization in Communication Networks: Principles and Design Paradigms. IEEE Communications Magazine, Feature Topic on Advances in Self-Organizing Networks, vol. 43, no. 7, pp. 78-85, July 2005.

Christian Bettstetter. On the Connectivity of Ad Hoc Networks. The Computer Journal, Special Issue on Mobile and Pervasive Computing, vol. 47, no. 4, pp. 432-447, Oxford University Press, July 2004.