de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch

Hilfe Wegweiser Impressum Kontakt Einloggen

# Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Bericht

#### Distributed list coloring: how to dynamically allocate frequencies to mobile base stations

##### MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44477

Garg,  Naveen
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45161

Papatriantafilou,  Marina
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45640

Tsigas,  Philippas
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

##### Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
##### Volltexte (frei zugänglich)

1996-1-010
(beliebiger Volltext), 11KB

##### Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
##### Zitation

Garg, N., Papatriantafilou, M., & Tsigas, P.(1996). Distributed list coloring: how to dynamically allocate frequencies to mobile base stations (MPI-I-1996-1-010). Saarbrücken: Max-Planck-Institut für Informatik.

To avoid signal interference in mobile communication it is necessary that the channels used by base stations for broadcast communication within their cells are chosen so that the same channel is never concurrently used by two neighboring stations. We model this channel allocation problem as a {\em generalized list coloring problem} and we provide two distributed solutions, which are also able to cope with crash failures, by limiting the size of the network affected by a faulty station in terms of the distance from that station. Our first solution uses a powerful synchronization mechanism to achieve a response time that depends only on $\Delta$, the maximum degree of the signal interference graph, and a failure locality of 4. Our second solution is a simple randomized solution in which each node can expect to pick $f/4\Delta$ colors where $f$ is the size of the list at the node; the response time of this solution is a constant and the failure locality 1. Besides being efficient (their complexity measures involve only small constants), the protocols presented in this work are simple and easy to apply in practice, provided the existence of distributed infrastructure in networks that are in use.