# Channel assignment for digital networks: a bound and an algorithm

Abstract:

The problem of channel assignment in digital networks can be formulated as follows. Services to be broadcast at a transmitter must be packed into blocks, and each block must be assigned a frequency channel. This assignment must satisfy bandwidth and interference constraints. The objective is to minimize spectrum use.

Mathematically, the problem corresponds to a generalized graph colouring problem with a flavour of bin packing. In this paper, we give a new lower bound on spectrum use for this problem, derived from intersecting cliques. We also give a near-optimal, efficient algorithm to assign frequency channels to blocks for the case where the interference graph is a cycle.

Tech Report Number:

CS-2002-03

Report Date:

May 1, 2002

Attachment | Size |
---|---|

CS-2002-03.pdf | 247.14 KB |