Лаборатория системного моделирования и оптимизации

Зав. лабораторией: д.т.н. Алексей Сергеевич Родионов (alrod@sscc.ru). В составе лаборатории 10 кандидатов и 1 доктор наук.
 

Тематика: построение и исследование структурных моделей на основе теории графов, гиперграфов и гиперсетей; моделей динамики поведения информационных и коммуникационных сетей на основе методов теории случайных процессов и имитационного моделирования, алгоритмов и средств сжатия, хранения и обработки данных, методов анализа больших информационных массивов.
 

Моделирование беспроводных и мобильных сетей

Ведутся исследования по созданию методов расчета и оценки вероятностно-временных характеристик беспроводных сенсорных сетей (БСС) с учетом специфики их функционирования, в частности подверженности отказам сенсоров и каналов связи, ограничений на количество транзитных узлов при передаче информации между сенсором и стоком. С использованием теории марковских процессов построены математические модели, позволяющие оценить отказоустойчивость узла БСС с учетом специфики функционирования его аппаратной части и поведения окружающей среды. С использованием теории оптимального планирования экспериментов предложен подход к улучшению качества оценки мониторинга, осуществляемого сенсорами.

Разрабатываются и исследуются алгоритмы точного расчета и оценивания различных показателей надежности сетей, различного назначения, в том числе транспортных и мониторинга больших территорий. Исследуются методы оптимального по различным показателям построения таких сетей и их управления. В частности, разрабатываются алгоритмы маршрутизации мобильных источников и/или приёмников данных в системах мониторинга состояния окружающей среды, включая мониторинг загрязнения городской атмосферы и городского автомобильного трафика.

Разработан ряд алгоритмов для расчета и оценивания надежности линейных беспроводных сенсорных сетей, а также структурной оптимизации таких сетей для повышения их надежности.
 

Модели ненадежных структур

В лаборатории разрабатываются алгоритмы расчета и оценивания различных характеристик надежности сложных сетей с отказами компонентов и методы оптимизации структур сетей по этим показателям.

Разработаны точные алгоритмы расчета вероятности связности подмножеств узлов сетей, в том числе многоуровневых, учитывающие различные структурные особенности и ограничения, что позволяет достичь существенного ускорения расчетов, в частности при использовании параллельных алгоритмов.

Разработаны методы ускорения кумулятивного уточнения границ различных показателей надежности сети для скорейшего принятия решения о ее достаточной надежности/ненадежности по отношению к наперед заданному порогу.

На основе линейной аппроксимации границ получены приближенные значения показателей, в общем случае более точные, чем простое среднее границ. Применение кумулятивных границ и этих приближений позволяет существенно ускорить исполнение биоинспирированных алгоритмов структурной оптимизации, в частности генетического алгоритма и алгоритма клонирования.

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

Проектирование инженерных сетей

Анализ регулярных сетей

Ведутся исследования по построению регулярных сетей различного вида. В частности, на основетеории  циркулянтных сетей разработаны и экспериментально исследованы в сети на кристалле два вида алгоритмов парной маршрутизации константной сложности для оптимальных циркулянтных сетей степени четыре, позволяющие создавать серию алгоритмов маршрутизации для различных подклассов оптимальных сетей и сокращающие время работы и объем требуемой памяти по сравнению с известными алгоритмами. Построена новая серия семейств циркулянтных сетей степени шесть с общими структурными и коммуникационными свойствами, перспективная как масштабируемая модель топологий сетей на кристалле.
 

Имитационное моделирование

Ведутся работы над созданием эффективных средств имитационного моделирования, обеспечивающих проведение имитационной оптимизации и совмещение средств имитации со средствами искусственного интеллекта при моделировании больших недоопределенных систем, в том числе при использовании внешних данных реального времени.

Созданы программные средства и разработана методика имитационного моделирования процесса исполнения параллельных программ на гетерогенных вычислительных комплексах большой производительности. С использованием предложенных средств реализован ряд имитационных моделей вычислительных программ с целью исследования их масштабируемости на суперЭВМ будущих поколений.

Разработаны и протестированы модели социальных процессов, взаимодействия мобильных объектов, промышленного производства и др. Один из примеров –решение задачи оптимизации системы сбора данных о загрязнении городской атмосферы.

Пример работы системы City Monitoring