### Skapa referens, olika format (klipp och klistra)

**Harvard**

Garg, N., Papatriantafilou, M. och Tsigas, P. (2002) *Distributed Long-Lived List Colouring: How to Dynamically Allocate Frequencies in Cellular Networks*.

** BibTeX **

@article{

Garg2002,

author={Garg, N. and Papatriantafilou, Marina and Tsigas, Philippas},

title={Distributed Long-Lived List Colouring: How to Dynamically Allocate Frequencies in Cellular Networks},

journal={Wireless networks},

issn={1022-0038},

volume={8},

issue={1},

pages={49-60},

abstract={To avoid signal interference in mobile communication it is necessary that the frequencies used for communication within each cell are allocated so that no signal interference occurs with neighbouring cells. We model this channel allocation problem as a generalised list colouring problem and we show how to analytically measure and provide worst-case guarantees regarding request satisfiability. To the best of our knowledge, this has not been done before and gives a now perspective to the problem, as well as a clear direction for further investigation. We propose distributed approaches for solving the problem, which are able to adapt fast to temporal variations in channel demands in different cells, as well as to cope with crash failures, by limiting the failure-locality - the size of the network that can be affected by a faulty station, in terms of the distance from that station. Our first approach is inspired by a relatively recent theorem relating graph colourings and orientations; it achieves the equivalent of the best known sequentially achievable upper bound for request satisfiability, implied by the theorem. It also employs a powerful synchronisation mechanism to achieve worst-case response time that depends only on A - the degree of the signal interference graph - and failure locality 4. Our second proposal is a first approach towards exploring what bound in request satisfiability is achievable without the use of extra synchronisation; by employing randomisation in frequency choices, in only one round of communication, a base station can expect to pick f/(4Delta) frequencies, where f is the size of the list at the node; the failure locality of this solution is only 1.},

year={2002},

keywords={cellular networks, distributed frequency allocation, dynamic frequency allocation, request satisfiability, failure locality},

}

** RefWorks **

RT Journal Article

SR Electronic

ID 173616

A1 Garg, N.

A1 Papatriantafilou, Marina

A1 Tsigas, Philippas

T1 Distributed Long-Lived List Colouring: How to Dynamically Allocate Frequencies in Cellular Networks

YR 2002

JF Wireless networks

SN 1022-0038

VO 8

IS 1

SP 49

OP 60

AB To avoid signal interference in mobile communication it is necessary that the frequencies used for communication within each cell are allocated so that no signal interference occurs with neighbouring cells. We model this channel allocation problem as a generalised list colouring problem and we show how to analytically measure and provide worst-case guarantees regarding request satisfiability. To the best of our knowledge, this has not been done before and gives a now perspective to the problem, as well as a clear direction for further investigation. We propose distributed approaches for solving the problem, which are able to adapt fast to temporal variations in channel demands in different cells, as well as to cope with crash failures, by limiting the failure-locality - the size of the network that can be affected by a faulty station, in terms of the distance from that station. Our first approach is inspired by a relatively recent theorem relating graph colourings and orientations; it achieves the equivalent of the best known sequentially achievable upper bound for request satisfiability, implied by the theorem. It also employs a powerful synchronisation mechanism to achieve worst-case response time that depends only on A - the degree of the signal interference graph - and failure locality 4. Our second proposal is a first approach towards exploring what bound in request satisfiability is achievable without the use of extra synchronisation; by employing randomisation in frequency choices, in only one round of communication, a base station can expect to pick f/(4Delta) frequencies, where f is the size of the list at the node; the failure locality of this solution is only 1.

LA eng

DO 10.1023/A:1012719525108

LK http://dx.doi.org/10.1023/A:1012719525108

OL 30