## DIMACS TR: 98-17

## Online Channel Allocation in FDMA Networks with Reuse Constraints

### Authors: Tomás Feder and Sunil M. Shende

**
ABSTRACT
**

The topology of an FDMA network is modeled by a subdivision of a planar region
into hexagonal cells; this defines a graph where every node has at most six
neighbors. For channel allocation, every node has a weight that indicates the
number of channels that must be assigned to it; the reuse distance defines the
minimum distance between nodes that can use the same channel without
radio interference. It is known that with reuse distance 2, the number of channels
needed and their allocation can be approximated within a factor of $4/3$ both
offline and online. We describe an online algorithm for the case of reuse
distance 3 that achieves an approximation factor of $7/3$.

### Keywords:

Analysis of Algorithms, Combinatorial Problems, Design of
Algorithms, Distributed Computing

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1998/98-17.ps.gz

DIMACS Home Page