DIMACS TR: 98-17

Online Channel Allocation in FDMA Networks with Reuse Constraints

Authors: Tomás Feder and Sunil M. Shende


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$.


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