Given an integer $\sigma &gt; 1$, a vector $(\delta_1, \delta_2, \ldots, \delta_{\sigma-1})$ of nonnegative integers, and an undirected graph $G=(V,E)$, an $L(\delta_1, \delta_2, \ldots,\delta_{\sigma-1})$-coloring of $G$ is a function $f$ from the vertex set $V$ to a set of nonnegative integers such that $| f(u) -f(v) | \ge \delta_i$, if $d(u,v) = i, \ 1 \le i \le \sigma-1, \$ where $d(u,v)$ is the distance (i.e. the minimum number of edges) between the vertices $u$ and $v$. An optimal $L(\delta_1, \delta_2, \ldots,\delta_{\sigma-1})$-coloring for $G$ is one using the smallest range $\lambda$ of integers over all such colorings. This problem has relevant application in channel assignment for interference avoidance in wireless networks, where channels (i.e. colors) assigned to interfering stations (i.e. vertices) at distance $i$ must be at least $\delta_i$ apart, while the same channel can be reused in vertices whose distance is at least $\sigma$. In particular, two versions of the coloring problem -- $L(2,1,1)$, and $L(\delta_1, 1, \ldots,1)$ -- are considered. Since these versions of the problem are $NP$-hard for general graphs, efficient algorithms for finding optimal colorings are provided for specific graphs modeling realistic wireless networks including rings, bidimensional grids, and cellular grids.

Channel Assignment with Separation for Interference Avoidance in Wireless Networks / Bertossi, Alan; Tan, Richard; Pinotti, Cristina M.. - ELETTRONICO. - (2002), pp. 1-30.

### Channel Assignment with Separation for Interference Avoidance in Wireless Networks

#### Abstract

Given an integer $\sigma > 1$, a vector $(\delta_1, \delta_2, \ldots, \delta_{\sigma-1})$ of nonnegative integers, and an undirected graph $G=(V,E)$, an $L(\delta_1, \delta_2, \ldots,\delta_{\sigma-1})$-coloring of $G$ is a function $f$ from the vertex set $V$ to a set of nonnegative integers such that $| f(u) -f(v) | \ge \delta_i$, if $d(u,v) = i, \ 1 \le i \le \sigma-1, \$ where $d(u,v)$ is the distance (i.e. the minimum number of edges) between the vertices $u$ and $v$. An optimal $L(\delta_1, \delta_2, \ldots,\delta_{\sigma-1})$-coloring for $G$ is one using the smallest range $\lambda$ of integers over all such colorings. This problem has relevant application in channel assignment for interference avoidance in wireless networks, where channels (i.e. colors) assigned to interfering stations (i.e. vertices) at distance $i$ must be at least $\delta_i$ apart, while the same channel can be reused in vertices whose distance is at least $\sigma$. In particular, two versions of the coloring problem -- $L(2,1,1)$, and $L(\delta_1, 1, \ldots,1)$ -- are considered. Since these versions of the problem are $NP$-hard for general graphs, efficient algorithms for finding optimal colorings are provided for specific graphs modeling realistic wireless networks including rings, bidimensional grids, and cellular grids.
##### Scheda breve Scheda completa Scheda completa (DC)
2002
Trento, Italia
Università degli Studi di Trento. DEPARTMENT OF INFORMATION AND COMMUNICATION TECHNOLOGY
Channel Assignment with Separation for Interference Avoidance in Wireless Networks / Bertossi, Alan; Tan, Richard; Pinotti, Cristina M.. - ELETTRONICO. - (2002), pp. 1-30.
Bertossi, Alan; Tan, Richard; Pinotti, Cristina M.
File in questo prodotto:
File
78.pdf

accesso aperto

Tipologia: Versione editoriale (Publisher’s layout)
Dimensione 716.91 kB
Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11572/358616