Channel assignment for digital networks: a bound and an algorithm

Authors: 

Jeannette Janssen
Mark MacIsaac
Kyle Schmeisser

Author Addresses: 

Jeannette Janssen (janssen@mathstat.dal.ca)
Mark MacIsaac (macisaac@mathstat.dal.ca)
Kyle Schmeisser (kyle@mathstat.dal.ca)
Dept. of Mathematics and Statistics
Dalhousie University
B3H 3J5 Halifax, NS

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
AttachmentSize
PDF icon CS-2002-03.pdf247.14 KB