Format:
Online-Ressource
Content:
Zusammenfassung: All over the globe there is a tendency towards using more and more small electronic devices to coordinate and support our daily lives. The standard way of communication of these autonomous units is wireless, i.e., broadcasted signals can be received by all devices within reach. Whether a receiving device can actually decode a signal by another device does, however, depends on a variety of factors other than the distance and the signal strength. Among them, environmental interference—either stemming from other sending devices or simply white noise—is the most significant one.In this thesis we investigate how such devices can work together in a distributed manner to compute basic hierarchical structures among themselves based on the restrictions imposed by constrained communication such as wireless signaling.The radio network model tries to capture above mentioned dependencies. It pessimistically assumes that signals can only be decoded if there is no interference, while in every other case signals received under collisions are indistinguishable from silence or white noise. Lots of research has been done for this model, but it is commonly assumed that only one channel for communication is available, while in reality a broad spectrum of frequencies can be exploited.The main theme of this thesis is to study multiple important ad hoc structure-building problems for the radio network model, under the assumption that a multitude of communication channels is available. It is analyzed which benefits can be reaped in such an environment, and where multichannel networks have their limitations. The main problems we study are leader election, wake-up, minimum dominating set, maximal independent set and connected dominating set. If we denote with n the size of the network and with F the number of communication channels, then for all the above mentioned problems we can show a speed-gain roughly in the order of minF, log n} compared to prevailing single channel algorithms.While the radio network model is pessimistic in its assumptions and therefore a good model for developing robust algorithms, some desired physical properties that are actually prevalent in wireless communication are not reflected in it. However, this is the case for the signal-to-interference-and-noise-ratio model (SINR), which in return is harder to analyze. In addition, while this model has been analyzed a lot from a central perspective, the theory for distributed algorithms in this area is not as well developed as the radio network model. For these two reasons we drop the multichannel aspect and study possibilities and limitations for the core problem of information dissemination in the ad hoc SINR model.At last we turn our focus to another network that works on a peer-to-peer basis, i.e., in a wired network. We introduce a new constrained variant for gossip communication models, trying to close the gap between prevalent theory and reality. In this model we investigate again the possibilities and limitations for disseminating information
Note:
Dissertation Albert-Ludwigs-Universität Freiburg 2015
Language:
English
URN:
urn:nbn:de:bsz:25-freidok-102924
