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

Развитие спутниковых телекоммуникационных систем приводит к необходимости решения задач распределения частотных диапазонов для используемых каналов связи, с учетом требований по пропускной способности сети. При этом необходимо учитывать неравномерность распределения трафика, а также зависимость пропускной способности от используемых частотных диапазонов. Требования к качеству обслуживания создают необходимость динамической настройки параметров сети, причем не только перераспределения потоков в ней, но и перераспределения доступных частотных диапазонов, а также переопределения их количества. Цель данного исследования – разработать алгоритмы синтеза плана распределения частотных диапазонов с учетом целевых запросов и структуры телекоммуникационной сети. Для этого реализован алгоритм определения минимального количества различных каналов связи путем раскраски графа, при этом определение потоков на ребрах графа определяется при помощи жадного градиентного алгоритма, оптимизирующего время задержки и коэффициент пропускной способности. Кроме этого, реализован генетический алгоритм для тонкой подстройки полученного изначального плана распределения частот. Проведенные вычислительные эксперименты показали способность разработанного алгоритма находить решения для сетей размерностью до 1000 узлов за приемлемое время. Для сетей небольшой размерности показано, что генетический алгоритм способен улучшать найденные решения с точки зрения пропускной способности сети.

1. Yan D., Guo J., Wang L., Zhan P. SADR: Network status adaptive QoS dynamic routing for satellite networks. In: 2016 IEEE 13th International Conference on Signal Processing, 06–10 November 2016, Chengdu, China. IEEE; 2016. P. 1186–1190. https://doi.org/10.1109/ICSP.2016.7878015

2. Kasan H., Kim J. The case for dynamic bias in global adaptive routing. IEEE Computer Architecture Letters. 2021;20(1):38–41. https://doi.org/10.1109/LCA.2021.3061408

3. Bertsekas D.P., Gallager R.G. Data Networks. London: Prentice-Hall; 1992. 556 p.

4. Yen J.Y. Finding the k shortest loopless paths in a network. Management Science. 1971;17(11):712–716. https://doi.org/10.1287/mnsc.17.11.712

5. Arbelaez A., Mehta D., O’Sullivan B., Quesada L. A Constraint-Based Local Search for Edge Disjoint Rooted Distance-Constrained Minimum Spanning Tree Problem. In: Integration of AI and OR Techniques in Constraint Programming, 18–22 May 2015, Barcelona, Spain. Cham: Springer; 2015. P. 31–46. https://doi.org/10.1007/978-3-319-18008-3_3

6. Kuipers F., Van Mieghem P., Korkmaz T., Krunz M. An overview of constraint-based path selection algorithms for QoS routing. IEEE Communications Magazine. 2002;40(12):50–55. https://doi.org/10.1109/MCOM.2002.1106159

7. Taft-Plotkin N., Bellur B., Ogier R. Quality-of-service routing using maximally disjoint paths. In: 1999 Seventh International Workshop on Quality of Service, 31 May – 04 June 1999, London, UK. IEEE; 1999. P. 119–128. https://doi.org/10.1109/iwqos.1999.766485

8. Huang G.M., Zhu Sh. A fast distributed optimal routing algorithm for multicommodity large data networks. In: Proceedings of 9th International Parallel Processing Symposium, 25–28 April 1995, Santa Barbara, CA, USA. IEEE; 1995. P. 551–555. https://doi.org/10.1109/IPPS.1995.395985

9. Jain A., Chaudhari N.S. Genetic algorithm for optimizing network load balance in MPLS network. In: 2012 Fourth International Conference on Computational Intelligence and Communication Networks, 03–05 November 2012, Mathura, India. IEEE; 2012. P. 122–126. https://doi.org/10.1109/cicn.2012.119

10. Zhu Sh., Huang G.M. A new packet-loss minimization routing algorithm for ATM high-speed data networks. In: Proceedings of 35th IEEE Conference on Decision and Control, 13 December 1996, Kobe, Japan. IEEE; 2012. P. 287–292. https://doi.org/10.1109/CDC.1996.574317

11. Gaipov K., Tausnev D., Khodenkov S., et al. Heuristic Greedy-Gradient Route Search Method for Finding an Optimal Traffic Distribution in Telecommunication Networks. Algorithms. 2024;17(1):7. https://doi.org/10.3390/a17010007

12. Karakostas G. Faster approximation schemes for fractional multicommodity flow problems. ACM Transactions on Algorithms. 2008;4(1):13. https://doi.org/10.1145/1328911.1328924

13. Stanovov V., Akhmedova Sh., Semenkin E. Genetic Algorithm with Success History based Parameter Adaptation. In: Proceedings of the 11th International Joint Conference on Computational Intelligence, 17–19 September 2019, Vienna, Austria. SciTePress; 2019. P. 180–187. https://doi.org/10.5220/0008071201800187

14. Diestel R. Graph Theory. Berlin, Heidelberg: Springer; 2025. 455 p.