hide
Free keywords:
-
Abstract:
The Frequency Assignment Problem (FAP) in radio networks is the problem of
assigning frequencies to transmitters exploiting frequency reuse while keeping
signal interference to acceptable levels.
The FAP is usually modelled by variations of the graph coloring problem. The
Radiocoloring (RC) of a graph $G(V, E)$ is an assignment function $\Phi : V
\mapsto N$ such that $|\Phi(u) - \Phi(v)| \geq 2$, when $u, v$ are neighbors in
$G$, and $|\Phi(u) - \Phi(v)| \geq 1$ when the distance of $u, v$ in $G$ is
two. The range of frequencies used is called {\em span}. Here, we consider the
optimization version of the Radiocoloring
Problem (RCP) of finding a radiocoloring assignment of minimum span, called
{\em min span RCP}.
In this paper, we deal with a variation of RCP: that of satisfying frequency
assignment requests with some {\em periodic} behavior. In this case, the
interference graph is an (infinite) periodic graph. Infinite periodic graphs
model finite networks that accept periodic (in time, e.g. daily) requests for
frequency assignment. Alternatively, they may model very
large networks produced by the repetition of a small graph.
A {\em periodic graph $G$} is defined by an infinite two-way sequence of
repetitions of the same finite graph $G_i(V_i, E_i)$. The edge set of $G$ is
derived by connecting the vertices of each iteration $G_i$ to some of the
vertices of the next iteration $G_{i+1}$, the same for all $G_i$. The
model of periodic graphs considered here is similar to that of periodic graphs
in Orlin [13], Marathe et al [10]. We focus on planar periodic graphs, because
in many cases real networks are planar and also because of their independent
mathematical interest. We give two basic results:
- We prove that the min span RCP is PSPACE-complete for periodic planar graphs.
- We provide an $O(n(\Delta(G_i) + \sigma))$ time algorithm, (where $|V_i| =
n$, $\Delta(G_i)$ is the maximum degree of the graph $G_i$ and $\sigma$ is the
number of edges connecting each $G_i$ to $G_{i+1})$, which obtains a
radiocoloring of a periodic planar graph G that {\em approximates the minimum
span within a ratio which tends to 2 as $\Delta(G_i) + \sigma$ tends to
infinity}.
