Разработки СО РАН - каталоги программ и БД

Поиск по каталогам:

2020-12-25

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

Основные характеристики модели:

•          Построение транспортной сети на заданной пользователем карте. Подложкой может быть карта, взятая из открытых источников.

•          Моделирование динамическое, можно отслеживать дорожную обстановку с помощь настраиваемого модуля симуляции дорожного движения.

•         Тонкая настройка движения как для автомобилей, так и для маршрутного транспорта

•          Получение отчетов по проделанным этапам движения и передачи данных от движущихся узлов.

•          Сохранение и загрузка конфигураций, заданных пользователем.

[1] К. В. Ткачёв, Корсаков С. П., Мишуков В. И. Возможности имитационной модели сбора информации о состоянии атмосферы с помощью датчиков, установленных на общественном транспорте / Тезисы Международной конференции, посвященной 95-летию со дня рождения акад. Г. И. Марчука, Новосибирск, 19-23 октября 2020 , стр.157,DOI: 10.24411/9999-017A-2020-10361

[2] К. В. Ткачёв Имитационная модель сбора информации о состоянии атмосферы используя технологию VANET / Тезисы Международной конференции, посвященной 95-летию со дня рождения акад. Г. И. Марчука, Новосибирск, 19-23 октября 2020 стр. 156, DOI: 10.24411/9999-017A-2020-10360

Инструментальные средства создания - Программа разработана на платформе Visual Studio, с использованием языка С# и современных библиотек отрисовки различных объектов.

Работа поддержана проектом РФФИ № 19-01-00562 и проектом РФФИ и правительства Новосибирской области № 19-47-540007. 

В прилагаемых файлых - скриншоты работы системы моделирования.

В архиве citymonitoring-master.zip все необходимые для работы системы файлы.

 

2020-12-18

Назначение - поиск оптимальной укладки вторичной сети в первичную сеть для модели гиперсети.
Область применения - анализ и проектирование сетей различного назначения.

Используемый алгоритм - В программе реализован классический алгоритм Флойда и  разработанные авторами и описанные в [1-3]  алгоритмы.  

Среди использованных алгоритмов выделены те, которые не учитывают ограничение на надежность:
Floyd — классический Алгоритм Флойда
Greedy — жадный алгоритм
MetrRand, Metr1, Metr2  — В качестве начального решения берется решение Алгоритма Флойда. С помощью некоторой метрики производится сортировка ветвей первичной сети и оптимизация решения для улучшения. 

Следующие алгоритмы учитывают ограничение на надежность:
MaxProb - алгоритм Флойда ведет поиск самых надежных путей (по вероятности)
AntColony – алгоритм муравьинной колонии
Алгоритм k-кратчайших путей (k-path) - последовательное удаление из путей самых дорогих ветвей позволяет найти более дешевые пути, удовлетворяющие ограничение на надежность
Алгоритм k-кратчайших путей - 2 (k-path 2) -это вариация предыдущего алгоритма, только поиск ведется не от самых надежных путей, а от самых дешевых.
AntColony+ k-path - это алгоритм AntColony, в котором для ненайденных путей, используются пути, найденные алгоритмом k-path.

Функциональные возможности

  1. генерация первичной сети или загрузка ее из текстового файла
  2. укладка вторичной сети в первичную несколькими алгоритмами.

Описание программы:

Программа состоит из формы, в верхней части которой есть 3 вкладки: 

  • Graph PS, на которой рисуется первичная сеть
  • На вкладке Generate PS представлены поля в котроых задаются парметры для генерации графа первичной сети PS (решетка):
  • Вкладка AntColony — позволяет выбрать параметры для Алгоритма AntColony и увидеть промежуточные результаты его работы.

В нижней части формы можно задать параметры вторичной сети WS и выбрать алгоритм.

Кнопка FindWS — запускает один из алгоритмов и справа в текстовом поле показывается решение: стоимость укладки ребер, вероятность существования каждого ребра и вершины по которым оно проходит.

[1]. Попков В.К.,Токтошов Г.Ы., Юргенсон А.Н. Об одном подходе к оптимизации инфраструктуры инженерных сетей // Вестник СибГУТИ. – 2012. Т. 3 — С.11–28.
[2]. Guljigit Toktoshov, Anastasiya Yurgenson, Denis Migov. Design of Utility Network Subject to Reliability Constraint // Proc. of International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON), Novosibirsk, Russia, 18-22 Sept. 2017, DOI: 10.1109/SIBIRCON.2017.8109864, P. 172-175
[3]. Токтошов Г.Ы., Юргенсон А.Н., Мигов Д.А. Исследование эффективности применения метода k-кратчайших путей для оптимизации топологии иерархических сетей // Труды XVI международной азиатской школы-семинара «Проблемы оптимизации сложных систем», 25-29 августа 2020 г.- С. 38-42 - DOI: 10.24411/9999-018A-2020-100007

Подробное описание программы в прилагаемом файле.

Инструментальные средства создания -Lazarus (OS Linux).

Разработка программы осуществлялась при финансовой поддержке гранта РФФИ № 18-07-00460.

2019-12-30

Назначение - программа предназначена для проверки сверхбольших чисел Мерсенна на принадлежность их к простым числам.
Область применения - теория чисел, тестирование производительности вычислительных систем.

Используемый алгоритм - Используется алгоритм теста Люка-Лемера, в котором сверхбольшие числа представлены в виде динамических линейных массивов в двоичной системе счисления. Арифметические операции над числами выполняются по алгоритмам длинной арифметики. Поиск очередного самого большого простого числа Мерсенна вида 2^PM - 1 , где РM, в свою очередь, простое число, принимающее значения более 57 млн, является весьма трудоемкой задачей. В соответствии с тестом Люка-Лемера выполняется (PM -2) итераций цикла, на каждой из которых определяется целочисленный остаток от деления на число Мерсенна. Эта операция и определяет в основном трудоемкость теста. Только при представлении чисел в двоичной системе счисления представляется возможность упростить эту операцию до одной элементарной операции сложения.

В программе реализован разработанный авторами алгоритм вычисления целочисленного остатка при делении на сверхбольшое чисто Мерсенна в двоичной системе счисления. Целочисленный остаток в двоичной системе счисления определяется как сумма двух частей в записи делимого. Первая часть записи от разряда единиц (нулевой разряд) до разряда с номером (PM - 1), где PM - показатель степени числа Мерсенна. Вторая часть записи от разряда с номером PM и до старшего разряда в записи делимого. Использование данного алгоритма позволяет существенно снизить трудоемкость теста Люка-Лемера и время работы программы. Дополнительно к ранее зарегистрированному алгоритму "Тест Люка-Лемера для сверхбольших чисел Мерсенна" в два раза сокращено количество итераций вложенных циклов при вычислении квадрата целочисленного остаттка с предыдущей итерации теста. При возведении числа в квадрат в двоичной системе счисления сочетание цифр множимого и множителя с одинаковыми номерами разрядов встречаются однократно и в итог сносится 1, а с разными - дважды и в итог сносится 2. Учет этого обстоятельства во фрагменте программы позволил в два раза снизтить общую трудоемкость теста. 
Функциональные возможности - Функциональные возможности могут быть ограничены размером свободной динамической памяти ЭВМ. Размер используемых в программе двух динамических линейных массивов равен значению степени PM числа Мерсенна, которое в современных вычислениях принимает значение более 57 млн. В программе предусматривается проверка достаточности оперативной памяти для текущих вычислений.
Инструментальные средства создания - Microsoft  Visual Studio 2010, Visual C++.

2019-12-30

Назначение – программа предназначена для точного расчета надежности сети с использованием на суперЭВМ с распределённой памятью.

Область применения - анализ надёжности и живучести сетей различного назначения

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

Данная программа позволяет осуществлять параллельный точный расчёт надёжности сетей с ненадёжными каналами связи, под надёжностью понимается вероятность связности всех узлов сети. Распараллеливание расчёта основано на известном методе факторизации (ветвления, Мура-Шеннона), соответствующий алгоритм опубликован в [1]. По сравнению с первой версией программы оптимизированы параметры, повышающие масштабируемость программы. Рост производительности является линейным вплоть до 1000 вычислительных ядер. Однако, для структур разной плотности возможны разные оптимальные значения параметров [1].

Входные данные программы – структура сети в виде графа, значения надёжности каналов связи (т.е. вероятности их присутствия).

Выходные данные программы – значение надёжности сети, время расчёта.

Программа работает с представлением графов при помощи полного файла предшественников (списки KAO,FO). Информация в файле должна располагаться следующим образом: первая строка – количество вершин, вторая строка – количество рёбер, третья и четвёртая строка – списки представления графа (элементы списка разделяются запятыми).

[1] Denis A. Migov. Parallel Methods for Network Reliability Calculation and Cumulative Updating of Network Reliability Bounds // Proceedings of the IEEE 3rd Russian-Pacific Conference on Computer Technology and Applications. 2018. P. 1-5.  (DOI: 10.1109/RPC.2018.8482197)

Функциональные возможности – расчёт надёжности сетей с количеством элементов в несколько сотен.

Инструментальные средства создания – C++, MPI .

Алгоритм разработан в рамках гранта РФФИ № 18-07-00460

2019-12-30

Третья, расширенная версия системы имитационного моделирования ИМОДО, разработанной для решения задач, связанных с транспортной сетью (зарегистрирована в ФАП СО РАН, № PR18002).

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

Работа частично поддержана грантом РФФИ и правительства Новосибирской области № 19-47-54007.

Назначение Расчет эффективности расстановки устройств на транспортных средствах, с целью определения наиболее точного уровня загрезнения.
Область применения Современные и перспективные сети передачи данных, например, VANET.

Используемый алгоритм

Поиск оптимальной расстановки устройств сбора данных осуществляется с помощью генетического алгоритма с учетом основных характеристик модели:

– скорость движения транспорта;

–  маршруты движения транспортных средств, на которых размещены устройства мониторинга;

– предельное количечство автомобилей на каждом участке дороги (пробки, возникающие в "узких" местах);

– источники загрязнения.

В качестве модели транспортной сети рассматривается граф с взвешенными ребрами.

Редактирование графа можно производить непосредственно в системе.

Подложкой является карта, взятая из открытых источников. Алгоритм описан в [1].

[1] TKACHEV K.V., VOLZHANKINA K.A., SOKOLOVA O.D. On a problem of the monitoring device placement on transport networks, Novosibirsk. https://cloud.mail.ru/public/4Tsd/NymmFx5wP

[2] TKACHEV K.V., VOLZHANKINA K.A., MIGOV D.A. Comparison of the Work of Algorithms for Arranging Message Distribution Devices in Transport Networks, Novosibirsk. https://cloud.mail.ru/public/4Tsd/NymmFx5wP

[3] TKACHEV K.V. The Interaction Interface Between the Model and the Observer Agent in the Simulation System, Novosibirsk. https://cloud.mail.ru/public/4Tsd/NymmFx5wP

В прилагаемом архиве находится проект для запуска на Visual Studio.