Upper and lower bounds for the fixed spectrum frequency assignment problem

The frequency assignment problem involves the assignment of discrete channels (frequencies) to the transmitters of a radio network. A separation between the frequencies assigned to transmitters close to each other is required to avoid interference. Unnecessary separation causes an excess requirement for spectrum, which is a valuable resource. Consequently good assignments minimise both interference and the spectrum required.<br/><br/>The subject of this thesis is the fixed spectrum frequency assignment problem, where the spectrum available is given and the target is to minimize the total interference of the system. <br/><br/>Interference is modelled through binary constraints, and consequently the problem, which is treated as a combinatorial optimisation problem, can be represented by an undirected weighted graph.<br/><br/>A summary of some of the integer programming formulations which model the problem is presented, together with a brief dimensional study of them. <br/><br/>An efficient implementation of two well-known metaheuristic algorithms, adapted to the problem treated, is described.<br/><br/>Some novel lower bounding techniques which, given a problem, work by combining lower bounds calculated for some of its clique-like subproblems are presented. The key idea is that it is quite easy to calculate tight lower bounds for problems represented by complete graphs (cliques). The lower bounds for clique-like subproblems are produced by two different methods, the first of which is based on the solution of a linear program, while the second is based on a closed formula. The most effective method to generate estimates for general problems is based on a linear program which is reinforced with inequalities derived from the lower bounds calculated on its clique-like subproblems.<br/><br/>The last part of the thesis is dedicated to improvements to the lower bounding techniques, both for those working on general problems and for those developed for cliques only. <br/><br/>Detailed computational results, obtained on a wide range of benchmarks, are reported.

Name dc:type.qualificationname

Doctoral Thesis

Level dc:type.qualificationlevel

Student thesis

Year dc:date.issued

2001

Author dc:creator

• Montemanni, Robert

• Wireless communication systems

Language dc:language

eng

Identifier

oai:pure.atira.dk:studenttheses/c8ea4370-907d-4082-a90f-b0f8854b169e

OAI identifier oai:identifier

oai:pure.atira.dk:studenttheses/c8ea4370-907d-4082-a90f-b0f8854b169e