Оперативне управління телекомунікаційними системами та мережами на основі рангових методів рішення задач булевого програмування та теорії графів

Abstract

UA: Дисертація присвячена підвищенню оперативності рішення задач управління у телекомунікаційними системами та мережами, моделями яких є оптимізаційні задачі булевого програмування і теорії графів і розробці архітектури паралельних обчислювальних систем для їхньої реалізації. У роботі запропоновані методи рішення задач булевого лінійного і нелінійного програмування, а також задач оптимізації на графах на основі ідеї рангового підходу, що дозволили підвищити оперативність і точність рішення задач оптимального планування процесом управління в телекомунікаційних системах і мережах. Розроблено архітектуру циклічних ПОС, що дозволяють розпаралелити процес обчислень при оптимальному плануванні. RU: Диссертация посвящена повышению оперативности решения задач управления в телекоммуникационных системах и сетях, на основе использования ранговых методов решения задач булевого программирования и теории графов, а также разработке параллельных вычислительных структур для их реализации. В работе предложены методы решения задач булевого линейного и нелинейного программирования, а также задач оптимизации на графах на основе идей рангового подхода, позволивших повысить оперативность и точность решения задач оптимального планирования процессом управления в телекоммуникационных системах и сетях. Разработаны циклические параллельные вычислительные структуры (ПВС), позволяющие распараллелить процесс вычислений при оптимальном планировании выполнения задач управления. В первом разделе проведен анализ тенденций развития и особенностей построения телекоммуникационных и вычислительных сетей, работающих в системах реального времени. Выделен подкласс задач, решаемый в сети, при динамическом управлении потоками информации в сети, формальными моделями которых являются задачи булевого линейного и нелинейного программирования, а также оптимизационные задачи на графах. В разделе сформулирована проблема научного исследования. Второй раздел посвящен разработке теории решения задач ЦЛП с БП на основе идей рангового подхода, который рассмотрен на примерах решения задач 0,1-рюкзак и задачи определения минимального покрытия и их экспериментальному исследованию. В третьем разделе рассмотрен ранговый подход к решению задач булевого программирования на основе теории графов и булевой алгебры, а также к решению выделенного в разделе 1, с точки зрения решения задач управления в телекоммуникационных сетях, подкласса задач теории графов. В четвертом разделе рассмотрены параллельные алгоритмы определения оптимальных маршрутов и путей с максимальной пропускной способностью в телекоммуникационных сетях на основе рангового подхода с использованием перехода от исходного графа G к стянутому дереву всех путей D0. В пятом разделе рассмотрены формальные модели и алгоритмы решения комплекса задач динамического управления потоками информации в телекоммуникационных сетях на основе разработанного аппарата решения задач булевого программирования, к которым относятся: – управление решением задач и использованием вычислительных ресурсов сети в условиях изменения ее конфигурации ; – управление маршрутизацией сообщений в сети; – оценка пропускной способности в условиях изменения конфигурации сети; – обеспечение адаптивного, к изменяющимся потокам заданий, управления в узлах сети; – оценка состояния сети и восстановление сети в случаях отказов ее функциональных элементов; – адаптивное отображение логической структуры базы данных сети на ее физическую структуру и оптимального поиска информации в ней в условиях изменения конфигурации сети; – планирование размещения подвижных центров управления и коммутации сети при наличии подвижных пунктов управления. В шестом разделе предложены и проанализированы абстрактные модели организации параллельных вычислений на основе циклической обработки информации и адаптивности алгоритма вычислений к ширине алгоритма решаемой задачи. Разработаны параллельные вычислительные структуры для реализации алгоритмов, основанных на идеях рангового подхода. В приложении приведены: дополнительные сведения о сводимости задач класса NP, анализ состоянии вопроса исследования ПВС; анализ методов определения кратчайших путей и сводимости задачи динамического программирования к задаче определения кратчайших путей; оценка достоверности моделирования задач управления в телекоммуникационных сетях; результаты экспериментальных исследований разработанных алгоритмов. EN: The dissertation is devoted to increasing effectiveness of control solution in telecommunication systems and networks on the basis of using rank methods of solving Boolean programming problems and graphs theory as well as development of parallel computing structures for their implementation. In the research work methods of solving Boolean linear and non-linear programming problems are suggested, as well as optimization problems on graphs on the basis of rank approach ideas permitting to increase effectiveness and accurateness of solving problems in optimal planning the process control in telecommunication systems and networks. Cyclical parallels’ computing structures permitting to deparallelize the process of computations with optimal planning were developed.