problem of radio frequency assignment

Help | Advanced Search

Computer Science > Networking and Internet Architecture

Title: frequency assignment problem with net filter discrimination constraints.

Abstract: Managing radio spectrum resources is a crucial issue. The frequency assignment problem (FAP) basically aims to allocate, in an efficient manner, limited number of frequencies to communication links. Geographically close links, however, cause interference, which complicates the assignment, imposing frequency separation constraints. The FAP is closely related to the graph-coloring problem and it is an NP-hard problem. In this paper, we propose to incorporate the randomization into greedy and fast heuristics. As far as being implemented, the proposed algorithms are very straight forward and are without system parameters that need tuned. The proposed algorithms significantly improve, quickly and effectively, the solutions obtained by greedy algorithms in terms of the number of assigned frequencies and the range. The enhanced versions of proposed algorithms perform close to the lower bounds while running for a reasonable duration. Another novelty of our study is its consideration of the net filter discrimination effects in the communication model. Performance analysis is done by synthetic and measured data, where the measurement data includes the effect of the real 3-dimensional (3D) geographical features in the Daejeon region in Korea. In both cases, we observe a significant improvement by employing randomized heuristics.

Submission history

Access paper:.

• Other Formats

References & Citations

• Google Scholar
• Semantic Scholar

DBLP - CS Bibliography

Bibtex formatted citation.

Bibliographic and Citation Tools

Code, data and media associated with this article, recommenders and search tools.

• Institution

arXivLabs: experimental projects with community collaborators

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs .

Academia.edu no longer supports Internet Explorer.

To browse Academia.edu and the wider internet faster and more securely, please take a few seconds to  upgrade your browser .

Enter the email address you signed up with and we'll email you a reset link.

• We're Hiring!
• Help Center

Radio Link Frequency Assignment

1999, Constraints - An International Journal

Related Papers

Cornelis Roos

The frequency assignment problem (FAP) is the problem of assigning frequencies to transmission links such that no interference occurs, and such that the number of used frequencies is minimized. We present an algorithm for the FAP that employs row generation and polyhedral techniques, primal heuristics, and branch-and-bound to obtain good lower and upper bounds to a vertex packing formulation of the problem. The valid inequalities added to the linear formulation are all based on cliques that can be found in an associated graph. We develop an efficient heuristic to identify two types of cliques. Moreover, we suggest two branching strategies. We report on computational experience with real-life instances. Table of contents 1 Introduction 3 2 Problem formulation 3 3 The branch-and-cut algorithm 5 3.1 Preprocessing: Reducing the Problem Size : : : : : : : : : : : : : 5 3.1.1 Technique 1 : : : : : : : : : : : : : : : : : : : : : : : : : : 5 3.1.2 Technique 2 : : : : : : : : : : : : : : :...

Handbook of Combinatorial Optimization

Robert Murphey

Operations Research

Harry Dimitropoulos

. In this paper Tabu Search has been compared with random search on solving a constraint satisfaction problem, namely the Radio Links Frequency Assignment Problem (RLFAP). The effect of Arc-Consistency has been demonstrated. Search Heuristics have been optimised. Results on scaling behaviour and performance of the algorithm under perturbation of a problem are presented. A method for reducing the number of distinct frequencies used, as well as satisfying constraints, is described. Furthermore, a method of constraint variation has been shown to halve processing times and secure solutions to harder problems. 1 Introduction Tabu Search is a modern heuristic method which was introduced by Glover [1, 2] as an efficient way of finding high quality solutions to hard combinatorial optimisation problems, such as the Radio Links Frequency Assignment Problem (RLFAP). The radio links frequency assignment problem occurs in many civil and military applications [3, 4]. The main objective is to assi...

European Journal of Operational Research

Roberto Montemanni

Research Report WP-CO0003, University of …

Antonio Sassano

Wireless communication is used in many different situations such as mobile telephony, radio and TV broadcasting, satellite communication, andmilitary operations. In each of these situations a frequency assignment problem arises with application specific characteristics. Researchers have developed different modeling ideas for each of the features of the problem, such as the handling of interference among radio signals, the availability of frequencies, and the optimization criterion. This survey gives an overview of the models and methods that the literature provides on the topic. We present a broad description of the practical settings in which frequency assignment is applied. We also present a classification of the different models and formulations described in the literature, such that the common features of the models are emphasized. The solution methods are divided in two parts. Optimization and lower bounding techniques on the one hand, and heuristic search techniques on the oth...

A Quarterly Journal of Operations Research

Wireless communication is used in many different situations such as mobile telephony, radio and TV broadcasting, satellite communication, and military operations. In each of these situations a frequency assignment problem arises with application specific characteristics. Researchers have developed different modeling ideas for each of the features of the problem, such as the handling of interference among radio signals, the availability of frequencies, and the optimization criterion. This survey gives an overview of the models and methods that the literature provides on the topic. We present a broad description of the practical settings in which frequency assignment is applied. We also present a classification of the different models and formulations described in the literature, such that the common features of the models are emphasized. The solution methods are divided in two parts. Optimization and lower bounding techniques on the one hand, and heuristic search techniques on the other hand. The literature is classified according to the used methods. Again, we emphasize the common features, used in the different papers. The quality of the solution methods is compared, whenever possible, on publicly available benchmark instances.

Joost Warners

Annals of Operations Research

Carlo Mannino

RELATED PAPERS

dong shijie

TRI SULISTYANI

Mustafa Bisri

Surgical Endoscopy

Nicole Bouvy

A Matter of Design Making Society Through Science and Technology

Hannele Palukka

Journal of the American Oil Chemists' Society

Roque Evangelista

Physical Review B

Francesc Alzina

Jurnal Ilmiah Akuntansi Rahmaniyah

muhammad luthfi

Administración de Parques Nacionales (APN)

Silvia Chalukian

Fernando Garcia

Alpha (Osorno)

Alex Espinoza

Gelson Silva

Proceedings of the Bulgarian Academy of Sciences

Alexander Tashev

Contrast Media & Molecular Imaging

Silvia Hilt

Erin Twyford

SN Comprehensive Clinical Medicine

Abhishek Shankar

TOTBID Dergisi

gökçer uzer

Children and Youth Services Review

Sandra Ortega

Alzheimer's & Dementia

George Heckman

Regional anesthesia and pain medicine

RAJNISH DINESH GUPTA

Turkiye Klinikleri Journal of Dermatology

Arif Turkmen

Optics Express

Ivan smalyukh

Ibnu Subagiyo

Ecotoxicology (London, England)

Karina Lima Reis Borges

SFU毕业证成绩单offer 西蒙菲莎大学一手制作’

RELATED TOPICS

•   We're Hiring!
•   Help Center
• Find new research papers in:
• Health Sciences
• Earth Sciences
• Cognitive Science
• Mathematics
• Computer Science
• Academia ©2024

• Help & FAQ

Algorithms for the radio link frequency assignment problem

• Stochastic Operations Research
• Combinatorial Optimization

Research output : Book/Report › Report › Academic

Publication series

Access to document.

• 532379 Final published version, 1.13 MB

Fingerprint

• Radio Link Engineering 100%
• Algorithm Engineering 100%
• Satisfaction Biochemistry, Genetics and Molecular Biology 100%
• Satisfies Engineering 33%
• Real Life Engineering 33%
• Reduction Engineering 33%
• Optimization Engineering 33%
• Research Group Engineering 33%

T1 - Algorithms for the radio link frequency assignment problem

AU - Aardal, K.I.

AU - Hurkens, C.A.J.

AU - Lenstra, J.K.

AU - Tiourine, S.R.

N2 - The radio link frequency assignment problem occurs when a network of radio links has to be established. Each link must be assigned an operating frequency from a given domain. The assignment has to satisfy certain restrictions so as to limit the interference between links. The number of frequencies used is to be minimized. Problems of this type were investigated by a consortium consisting of research groups from Delft, Eindhoven, London, Maastricht, Norwich, and Toulouse. The participants developed optimization algorithms based on branch-and-cut and constraint satisfaction, and approximation techniques including a variety of local search methods, genetic algorithms, neural networks, and potential reduction. These algorithms were tested and compared on a set of real-life instances.

AB - The radio link frequency assignment problem occurs when a network of radio links has to be established. Each link must be assigned an operating frequency from a given domain. The assignment has to satisfy certain restrictions so as to limit the interference between links. The number of frequencies used is to be minimized. Problems of this type were investigated by a consortium consisting of research groups from Delft, Eindhoven, London, Maastricht, Norwich, and Toulouse. The participants developed optimization algorithms based on branch-and-cut and constraint satisfaction, and approximation techniques including a variety of local search methods, genetic algorithms, neural networks, and potential reduction. These algorithms were tested and compared on a set of real-life instances.

M3 - Report

T3 - Memorandum COSOR

BT - Algorithms for the radio link frequency assignment problem

PB - Technische Universiteit Eindhoven

CY - Eindhoven

Artificial Neural Nets and Genetic Algorithms pp 37–40 Cite as

Using Genetic Algorithms to Solve the Radio Link Frequency Assignment Problem

• A. Kapsalis 4 ,
• V. J. Rayward-Smith 4 &
• G. D. Smith 4  
• Conference paper

234 Accesses

7 Citations

The Radio Link Frequency Assignment Problem (RLFAP) is that of assigning frequencies to a number of radio links in such a manner as to simultaneously satisfy a large number of constraints and use as few distinct frequencies as possible. This problem is known to be NP-complete. We describe the application of a genetic algorithm to the solution of the RLFAP. The standard crossover operators were found to be of limited use due to the highly epistatic nature of the problem and a range of new (crossover and mutation) operators are described. Dynamically modifying the weights used in the fitness function has also proved to be effective in improving the performance of the standard genetic algorithm. This work is being undertaken as part of the EUCLID CALMA Project - RTP 6.4 , Combinatorial Algorithms for Military Applications.

This is a preview of subscription content, log in via an institution .

Buying options

• Available as PDF
• Read on any device
• Instant download
• Own it forever
• Compact, lightweight edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Unable to display preview.  Download preview PDF.

R.H. Berry and G.D. Smith. Using a genetic algorithm to investigate taxation-induced interactions in capital budgeting. In Proceedings of the International Conference on Neural Networks and Genetic Algorithms , Innsbruck, 1993. Springer-Verlag.

Google Scholar  

W. Crompton, S. Hurley, and N.M. Stephens. Frequency assignment using a parallel genetic algorithm. In Proceedings of Natural Algorithms in Signal Processing . IEE, 1993.

UEA CALMA Group. Genetic algorithm approaches to solving the radio link frequency assignment problem. Technical report, University of East Anglia, 1994.

A. Kapsalis, V.J. Rayward-Smith, and G. D. Smith. Solving the graphical Steiner tree problem using genetic algorithms. J. Oper. Res. Soc. , 44 (4): 397–406, 1993.

MATH   Google Scholar  

A. Kapsalis, V.J. Rayward-Smith, and G.D. Smith. Fast sequencial and parallel implementation of genetic algorithms using the gameter toolkit. In Proceedings of the Int. Conf. on Artificial Neural Nets and Genetic Algorithms . Springer Verlang, 1993.

T.A. Lanfear. Graph theory and radio frequency assignment. Technical report, NATO EMC Analysis Programme, 1989. Project No. 5.

Download references

Author information

Authors and affiliations.

School of Information Systems, University of East Anglia, Norwich, NR4 7TJ, UK

A. Kapsalis, V. J. Rayward-Smith & G. D. Smith

You can also search for this author in PubMed   Google Scholar

Rights and permissions

Reprints and permissions

Copyright information

© 1995 Springer-Verlag/Wien

About this paper

Cite this paper.

Kapsalis, A., Rayward-Smith, V.J., Smith, G.D. (1995). Using Genetic Algorithms to Solve the Radio Link Frequency Assignment Problem. In: Artificial Neural Nets and Genetic Algorithms. Springer, Vienna. https://doi.org/10.1007/978-3-7091-7535-4_12

Download citation

DOI : https://doi.org/10.1007/978-3-7091-7535-4_12

Publisher Name : Springer, Vienna

Print ISBN : 978-3-211-82692-8

Online ISBN : 978-3-7091-7535-4

eBook Packages : Springer Book Archive

Share this paper

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Publish with us

Policies and ethics

• Find a journal
• Track your research