SODA

Automatic frequency assignment for cellular telephones using constraint satisfaction techniques

Carlsson, Mats and Grindal, Mats (1993) Automatic frequency assignment for cellular telephones using constraint satisfaction techniques. In: ICLP'93, 10th International Conference on Logic Programming, 21-25 June 1993, Budapest, Hungary.

[img]
Preview
PDF
154Kb

Abstract

We study the problem of automatic frequency assignment for cellular telephone systems. The frequency assignment problem is viewed as the problem to minimize the unsatisfied soft constraints in a constraint satisfaction problem (CSP) over a finite domain of frequencies involving co-channel, adjacent channel, and co-site constraints. The soft constraints are automatically derived from signal strength prediction data. The CSP is solved using a generalized graph coloring algorithm. Graph-theoretical results play a crucial role in making the problem tractable. Performance results from a real-world frequency assignment problem are presented. We develop the generalized graph coloring algorithm by stepwise refinement, starting from DSATUR and augmenting it with local propagation, constraint lifting, intelligent backtracking, redundancy avoidance, and iterative deepening.

Item Type:Conference or Workshop Item (Paper)
Uncontrolled Keywords:frequency assignment, constraints, graph coloring, intelligent backtracking, iterative deepening
ID Code:3072
Deposited By:Vicki Carleson
Deposited On:07 Sep 2009
Last Modified:18 Nov 2009 16:17

Repository Staff Only: item control page