Новости

Необходимость в расчёте и оценке показателей надёжности возникает, прежде всего, при структурной оптимизации сетей, как на этапе проектирования, так и при расширении существующих структур. При этом задача точного расчёта надёжности сети с 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

Имитационная модель для расчета эффективности мониторинга в сетях с движущимися объектами Версия 3

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

2019-12-29

Метод расстановки стоков для повышения надёжности сбора информации в сети с ненадёжными элементами. Версия №2

Назначение - оптимизация сетей различного назначения с целью повышения надёжности.

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

Используемый алгоритм - генетический алгоритм. Программа позволяет для заданной структуры сети с ненадёжными вершинами определить оптимальное количество необходимых стоков (узлов, предназначенных для сбора информации с остальных) и их расстановку. Предполагается, что стоки могут быть размещены в узлах сети. Для каждого узла сети задаются значения надёжности и стоимости установки стока в этом узле. Под надёжностью сети понимается вероятность связности заданной доли (Т) узлов с каким-либо из стоков. Этот показатель подробно описан в статье [1], наряду с методом его расчёта. Алгоритм расстановки представлен в работе [2].

[1] D. Migov, V. Shakhov. Reliability of Ad Hoc Networks with Imperfect Nodes // Springer Lecture Notes in Computer Science (in MACOM 2014). Vol. 8715, 2014, p. 49-58. (http://link.springer.com/chapter/10.1007%2F978-3-319-10262-7_5)

[2] Волжанкина К.А., Мигов Д.А. Генетический алгоритм размещения стоков в беспроводной сенсорной сети с ненадёжными узлами для повышения вероятности успешного мониторинга // Материалы Межд. конференции "Актуальные проблемы вычислительной и прикладной математики", Новосибирск, 2019. Новосибирск: ИВМиМГ СО РАН, 2019, стр. 328-332.

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

Входные данные программы: структура сети в виде графа, пример входных данных предоставлен в сопутствующих файлах (массивы KAO FO или полный файл предшественников), значения надёжности для всех узлов связи (числа от 0 до 1), параметры генетического алгоритма (размер популяции, кол-во поколений, размер турнира, вероятность мутации), количество устанавливаемых узлов, Т - доля узлов сети, которые должны быть связны с каким-либо из стоков, условия остановки алгоритма: количество поколений, ограничение на время работы алгоритма и стагнация (задаётся количество поколений, в которых вырождается решение).

Инструментальные средства создания - Delphi.

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

2019-12-27

Оптимизация расписания работы светофорных объектов в условиях городского трафика

Назначение - установление оптимальных значений длин фаз на светофорных объектах в городской транспортной сети.
Область применения - оптимизация и увеличение эффективности транспортной сети мегаполисов.
Используемый алгоритм - в основе программы лежит эвристический алгоритм роя частиц, позволяющий осуществлять эффективный поиск решений с малой или нулевой относительной погрешностью. Для определения качества получаемых решений используется пакет микросимуляционного моделирования SUMO.
Функциональные возможности - расчет длин фаз и сдвигов фаз для заданного участка городской транспортной сети. Размерность решаемых задач - до 50 светофорных объектов (до 5 фаз на каждом СО).
Инструментальные средства создания - среда разработки VisualStudio 12.0, язык программирования C#, микросимуляционный пакет SUMO

2019-06-18

Программа для кластеризации конформационных состояний аминокислотных остатков и фрагментов полипептидной цепи (пептидов) по значениям торсионных углов (Condense)

Назначение - Программа Condense предназначена для кластеризации наборов конформационных состояний аминокислотных остатков и/или фрагментов полипептидной цепи (пептидов) по значениям торсионных углов. На вход программы подается специальным образом структурированная информация о величинах торсионных углов аминокислот/пептидов.

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

Дополнительно можно выводить все элементы, попавшие в данный кластер.

Область применения - молекулярная динамика белков и пептидов, структурная биология
Используемый алгоритм - метод невзвешенного попарного центроидного усреднения (невзвешенный центроидный метод, UPGMC ). В этом методе расстояние между двумя кластерами определяется как расстояние между их центрами тяжести (Sneath, P. H., & Sokal, R. R. (1973). Numerical taxonomy. The principles and practice of numerical classification).
Функциональные возможности - результатом кластеризации являются центральные структуры кластеров и, в зависимости от параметров, полный список элементов кластера. Программа была использована для анализа подвижности пентапептидов методом молекулярной динамики (Nekrasov, A.N., Alekseeva, L.G., Pogosyan, R.А., Dolgikh, D.A., Kirpichnikov, M.P., de Brevern, A.G. and Anashkina, A.A., 2019. A minimum set of stable blocks for rational design of polypeptide chains. Biochimie, 160, pp.88-92). Возможен анализ до 10000 пространственной структур пептидов и фрагментов полипептидных цепей.
Инструментальные средства создания - языкеС++

Алгоритм разработан в рамках выполнения работ по теме "Фундаментальные проблемы математического моделирования" Программы № 43 фундаментальных исследований Президиума РАН по стратегическим направлениям развития науки, грант «Математическая модель пространственной организации природных полипептидных цепей на основе информационного контента первичной структуры»

Программа запускается командой condense *.ang *.out

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

out-файл содержит результаты кластеризации.

Параметры, определяющие режимы работы программы, задаются в файле condense.cfg

Во вложении - файл с инструкцией по использованию программы readme_condense.doc