T-SL, T-LF i T-DSATUR - nowe heurystyki dla problemu przydziału częstotliwości

• Autorzy: Janczewski R. , Małafiejski M.

Warianty tytułu

EN

T-SL, T-LF and T-DSATUR - new heuristic alorithms for the frequency assignment problem

• Konferencja: XIII Krajowa Konferencja Automatyzacji Procesów Dyskretnych
• Języki publikacji: PL

Abstrakty

PL

Problem przydziału częstotliwości to zagadnienie, które formułuje się zazwyczaj następująco: na pewnym obszarze znajduje się grupa nadajników radiowych, którym trzeba przydzielić częstotliwości w taki sposób, żeby nie zakłócały się podczas nadawania i aby szerokość wykorzystanego przez nie pasma częstotliwości była minimalna. Zagadnienie to modeluje się zazwyczaj na gruncie teorii grafów za pomocą trzech pojęć: grafów interferencji, kontrastowych pokolorowań i T-rozpiętości. Niniejszy artykuł zawiera opis tego modelu, podstawowe informacje o jego złożoności obliczeniowej oraz opis trzech nowych heurystyk - algorytmów, które są bardzo efektywne, ale generują przybliżone rozwiązania problemu przydziału częstotliwości. Algorytmy te zostały zbadane zarówno metodami teoretycznymi - wskazano, dla jakich klas grafów interferencji zachowują się dobrze, a dla jakich źle, jak i doświadczalnymi - przytoczono wyniki testów, jakim zostały poddane na małych i średnich losowych grafach interferencji.

EN

Frequency assignment problem (FAP) can be formulated as follows: there is a group of transmitters situated in a certain region of a plane; a channel is to be assigned to each of them in such a way that there is no interference during transmitting and the span of used frequency band is minimal. The paper is devoted to the graph-theoretical model of FAP based on three notions: interference graphs, T-colorings and the T-span. We describe the model, provide basic information about its computational complexity and present three new heuristic approximate algorithms. Results of the theoretical analysis and computer tests of these algorithms are also included.

Słowa kluczowe

PL

przydział częstotliwości; grafy; algorytmy

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 2002
• Tom: z. 136
• Strony: 97--105
• Opis fizyczny: Bibliogr. 5 poz.

Twórcy

autor

Janczewski R.

autor

Małafiejski M.

• Politechnika Gdańska, Gdańsk