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 min{F, 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 th ...
Note:
Freiburg i. Br., Univ., Diss., 2015
Additional Edition:
Erscheint auch als Druck-Ausgabe Daum, Sebastian, 1981 - The power of frequency hopping and information dissemination in constrained communication models 2015
Additional Edition:
Erscheint auch als Druck-Ausgabe Daum, Sebastian: The power of frequency hopping and information dissemination in constrained communication models
Language:
English
Keywords:
Ad-hoc-Netz
;
Funknetz
;
Hochschulschrift
URN:
urn:nbn:de:bsz:25-freidok-102924
URL:
Volltext
(kostenfrei)
URL:
Volltext
(kostenfrei)
Bookmarklink
