Параметрический синтез плана распределения частотных диапазонов эвристическими поисковыми алгоритмами

Abstract

Развитие спутниковых телекоммуникационных систем приводит к необходимости решения задач распределения частотных диапазонов для используемых каналов связи, с учетом требований по пропускной способности сети. При этом необходимо учитывать неравномерность распределения трафика, а также зависимость пропускной способности от используемых частотных диапазонов. Требования к качеству обслуживания создают необходимость динамической настройки параметров сети, причем не только перераспределения потоков в ней, но и перераспределения доступных частотных диапазонов, а также переопределения их количества. Цель данного исследования – разработать алгоритмы синтеза плана распределения частотных диапазонов с учетом целевых запросов и структуры телекоммуникационной сети. Для этого реализован алгоритм определения минимального количества различных каналов связи путем раскраски графа, при этом определение потоков на ребрах графа определяется при помощи жадного градиентного алгоритма, оптимизирующего время задержки и коэффициент пропускной способности. Кроме этого, реализован генетический алгоритм для тонкой подстройки полученного изначального плана распределения частот. Проведенные вычислительные эксперименты показали способность разработанного алгоритма находить решения для сетей размерностью до 1000 узлов за приемлемое время. Для сетей небольшой размерности показано, что генетический алгоритм способен улучшать найденные решения с точки зрения пропускной способности сети. The development of the telecommunication systems leads to the need of solving frequencies ranges distribution problems for the used communication channels, considering the network throughput. The non-even distribution of the traffic, as well as the dependence of the throughput on the used frequency ranges should be considered. The requirements to the quality of service require dynamic tuning of the network parameters, and not only the redistribution of data flows in it, but also the redistribution of available frequency ranges, as well as their number. The aim of this study is to develop the algorithms of frequency ranges distribution synthesis, considering the target requests and the structure of the telecommunication network. For this an algorithm for determining the minimum number of different communication channels is implemented, which works by coloring the graph, and the flows on the edges of the graph are determined using greedy gradient algorithm, which optimizes the delay time and throughput coefficient. Moreover, the genetic algorithm for fine-tuning the initially designed frequency distribution plan is implemented. The performed computational experiments have shown the ability of the developed algorithm to find solutions for networks with up to 1000 nodes at a reasonable time. For networks of small dimension it is shown, that the genetic algorithm is able to improve the found solutions in terms of network throughput.