Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
Static frequency assignment in cellular networks
Autore:
Narayanan, L; Shende, SM;
Indirizzi:
Concordia Univ, Dept Comp Sci, Montreal, PQ H3G 1M8, Canada Concordia Univ Montreal PQ Canada H3G 1M8 i, Montreal, PQ H3G 1M8, Canada Rutgers State Univ, Dept Comp Sci, Camden, NJ 08102 USA Rutgers State Univ Camden NJ USA 08102 ept Comp Sci, Camden, NJ 08102 USA
Titolo Testata:
ALGORITHMICA
fascicolo: 3, volume: 29, anno: 2001,
pagine: 396 - 409
SICI:
0178-4617(200103)29:3<396:SFAICN>2.0.ZU;2-D
Fonte:
ISI
Lingua:
ENG
Soggetto:
PERFORMANCE ANALYSIS;
Keywords:
frequency assignment; cellular networks; approximation algorithms; graph multicoloring; distributed algorithms;
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
Engineering, Computing & Technology
Citazioni:
9
Recensione:
Indirizzi per estratti:
Indirizzo: Narayanan, L Concordia Univ, Dept Comp Sci, Montreal, PQ H3G 1M8, Canada Concordia Univ Montreal PQ Canada H3G 1M8 PQ H3G 1M8, Canada
Citazione:
L. Narayanan e S.M. Shende, "Static frequency assignment in cellular networks", ALGORITHMIC, 29(3), 2001, pp. 396-409

Abstract

A cellular network is generally modeled as a subgraph of the triangular lattice. In the static frequency assignment problem, each vertex of the graphis a base station in the network, and has associated with it an integer weight that represents the number of calls that must be served at the vertex by assigning distinct frequencies per call. The edges of the graph model interference constraints for frequencies assigned to neighboring stations. The static frequency assignment problem can be abstracted as a graph multicoloring problem. We describe an efficient algorithm to multicolor optimally any weighted even or odd length cycle representing a cellular network. This result is further extended to any outerplanar graph. For the problem of multicoloring an arbitrary connected subgraph of the triangular lattice, we demonstrate an approximation algorithm which guarantees that no more than 4/3times the minimum number of required colors are used. Further, we show that this algorithm can be implemented in a distributed manner, where each station needs to have knowledge only of the weights at a small neighborhood.

ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 04/04/20 alle ore 02:53:54