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

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

2013-12-31

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

Используемый алгоритм: Вычисление вероятности блокировки пакета и средней задержки пакета в сетевом узле проводится с использованием СМО специального вида, разработанных с учетом специфики различных типов сетей (IP сети, WSNs, OBS).

В программах реализованы алгоритмы оценки вероятностно-временных характеристик, описанные в публикациях: 

  1. Vladimir V. Shakhov, Sangyep Nam, Hyunseung Choo: Flooding attack in energy harvesting wireless sensor networks. Proceedings of the 7th International Conference on Ubiquitous Information Management and Communication, ACM New York, USA 2013, Article No. 49, ISBN: 978-1-4503-1958-4; 
  2. Vladimir V. Shakhov: Experiment Design for Parameter Estimation in Sensing Models. Springer Lecture Notes in Computer Science, Volume 8072, 2013, pp 151-158, ISSN0302-9743; 
  3. Шахов В.В. К вопросу обеспечения дифференцированного качества обслуживания в мультисервисных сетях // Проблемы информатики, 2011, № 3. С. 64-78; 
  4. Vladimir Shakhov and Hyunseung Choo // An Efficient Method for Proportional Differentiated Admission Control Implementation. EURASIP Journal on Wireless Communications and Networking, vol. 2011, Article ID 738386, 5 pages, 2011. doi:10.1155/2011/738386; 
  5. Vladimir V. Shakhov. DDoS flooding attacks in OBS networks // IEEE 7th International Forum on Strategic Technologies (г. Томск, 18-21 сентября 2012 г.), P.704-707; 
  6. Vladimir V. Shakhov, Sangyep Nam, Seung-Jung Shin, Hyunseung Choo. Potential intrusions in wireless networks. Proceedings of the 6th International Conference on Ubiquitous Information Management and Communication (ACM ICUIMC 2012), Kuala Lumpur, Malaysia, 2012;
  7. V.V. Shakhov, Hyunseung Choo: On Modeling Counteraction against TCP SYN Flooding. Springer Lecture Notes in Computer Science, vol. 5200, 2008, pp 574-583; 
  8. Vladimir V. Shakhov, Jahwan Koo, Hyunseung Choo: On Modelling Reliability in RED Gateways. Springer Lecture Notes in Computer Science, Volume 3991, 2006, pp 948-951.

Кроме того, для тестирования алгоритмов реализованы формулы расчета характеристик некоторых СМО (см. Клейнрок Л. Теория массового обслуживания. — М.: Машиностроение, 1979. — С. 432.)

Функциональные возможности - предполагается, что буфер сетевого узла содержит не более 231 пакетов

Инструментальные средства создания - MSVC, библиотека libRNGnet

2013-12-30

Назначение – программа для точного расчёта вероятности связности случайного графа с ненадёжными рёбрами.

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

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

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

Входные данные программы – граф, вероятности присутствия рёбер.

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

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

[1] Migov D.A., Rodionova O.K., Rodionov A.S., Choo H. Network Probabilistic Connectivity: Using Node Cuts // EUC Workshops, Springer-Verlag LNCS, vol. 4097, 2006. - P.702-709.

[2] Мигов Д.А. Формулы для быстрого расчета вероятности связности подмножества вершин в графах небольшой размерности // Проблемы информатики, № 2(6), 2010. –  С.10-17.

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

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

По сравнению с 1 версией программы (№ PR10003) внесены следующие изменения:

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

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

- граф структуры сети может задаваться (вручную или загружаться из файла) списком рёбер и полным списком преемников.

2013-12-25

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

Область применения - Программа может быть использована для исследования и автоматизации сегментации по текстурным признакам черно-белых изображений в химии, биологии, медицине, аэрокосмических изображений в сельском хозяйстве, лесничестве при оценке площадей, занятых различными культурами, типами и фазами развития лесов, их картировании и инвентаризации.
Используемый алгоритм -разработанный автором дивизимный гистограммный иерархический алгоритм [1].  В результате работы алгоритма отыскиваются унимодальные кластеры с отделимостью ниже заданной и  предельно детальная сеть квантования векторного пространства текстурных признаков.  Алгоритм не требует задания числа кластеров и никакой информации о распределениях a priory, а находит их автоматическми .  Алгоритм учитывает особенности сбора статистических текстурных признаков по окну конечных размеров: он позволяет  автоматически выбрать этот размер и избавиться от ложных кластеров, возникающих на границах текстур. В [1] показано  применение  алгоритма к неконтролируемой классификации изображений лесных ландшафтов на аэроснимках и их сегментации по текстурным признакам.  На сайте можно посмотреть дополнительную информацию и иллюстрации - результат работы программы: http://loi.sscc.ru/lab/RFFI2013/RU/sidorova_separability_TEXTURA.htm 

[1] Sidorova V.S. Segmentation of image textures using well separated clusters //The 11th International Conference "Pattern recognition and image analysis: new information technologies" PRIA-11-2013, Samara, The Russian Federation, 2013,Vol.II, – P.731-734.

Функциональные возможности - Может быть использовано до десяти статистических текстурных признаков, файл входного изображения объемом до 5 мегабайт.

 Инструментальные средства создания - Алгоритм реализован в программной среде системы объектно-ориентированного программирования Visual C++ версии 5.0 фирмы Microsoft c библиотекой классов MFC, разработанной для ОС Windows. При разработке программы  использовался механизм многодокументного интерфейса MDI.

2013-12-25

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

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

Используемый алгоритм - Программа реализует алгоритм  сегментации изображения с предварительным выделением областей, связных в плоскости изображения и однородных по признакам  [1].  Входной файл может содержать спектральные или текстурные признаки. Он должен быть представлен как многоспектральное изображение в формате BMP (если признаков не больше трех) или RAW. Алгоритм является параметрическим. При последовательном однократном просмотре исходного изображения производится его предварительная локальная  сегментация на связные области, дисперсия в которых не превосходит заданные пороги d1 по строке изображения и d2  между строками. Средние вектора признаков областей затем объединяются кластерным алгоритмом с заданием  еще двух порогов внутрикластерного расстояния с учетом площадей кластеров. Характеристики областей и кластеров могут быть выведены на экран в виде таблиц и сохранены в файл. Алгоритм был применен для автоматизации  распознавания   лесных ландшафтов на аэроснимках с использованием текстурных признаков Харалика [2]. Файл вложения иллюстрирует результаты работы алгоритма, адаптированного  к персональному компьютеру.

[1] В.И.Борисенко, Л.С.Чесалин. Алгоритмы тематического дешифрирования многоспектральной аэрокосмической видеоинформации. // Ж.: Космические исследования, т. XVI, вып. 3, Москва 1978, С. 388 - 393.

[2] Алексеев А.С., Васильев С.В., Мозалевский В.Г., Пяткин В.П., Седых В.Н., Сидорова В.С. Автоматизация процесса обработки аэрокосмических снимков в целях инвентаризации лесов // Ж.: Исследование Земли из космоса. АН СССР. 1981. № 6. С. 93-100.

Функциональные возможности - Может быть использовано до десяти спектральных или текстурных признаков, файл входного изображения объемом до 5 мегабайт.
Инструментальные средства создания - Алгоритм реализован в программной среде системы объектно-ориентированного программирования Visual C++ версии 5.0 фирмы Microsoft c библиотекой классов MFC, разработанной для ОС Windows. При разработке программы  использовался механизм многодокументного интерфейса MDI.

2013-12-24

Назначение:

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

   dY(t) = A(Y(t))*dt + B(Y(t))*dW(t),  где

    Y(t) - вектор состояния системы (размерности n);

    W(t) - вектор независимых стандартных винеровских процессов (размерности m);

    A(Y) - известная векторная функция размерности n (снос);

    B(Y) - известная матричная функция размерности n x m (диффузия).

Область применения: Программа может быть использована для моделирования   динамических систем, модели которых заданы системой СДУ, в различных областях: радиотехнике, статистической механике, автоматическом управлении, химии, медицине, теории надежности и т.д.  

Используемый алгоритм: Для моделирования решений автономных систем СДУ в смысле Стратоновича используется асимптотически несмещенный с любым шагом интегрирования обобщенный двух-стадийный метод типа Розенброка, описанный в работах [1, 2], а для моделирования решений автономных систем СДУ  в смысле Ито используется устойчивый обобщенный двух-стадийный метод типа Розенброка, описанный в работах [3.4]. Предполагается, что в начальный момент времени Т0 известно распределение вектора состояния системы Y(T0).

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

1. Т.А. Аверина, С.С. Артемьев. Новое семейство численных методов  решения стохасти-ческих дифференциальных уравнений// Докл. АН СССР, 1986, т.288, N 4, с. 777-780.

2. . Т.А. Аверина, С.С. Артемьев. Некоторые вопросы построения и использования численных методов для решения систем стохастических дифференциальных уравнений. Новосибирск. 1987. – 32 с. – (Препринт / АН СССР Сиб. Отд.-ние, ВЦ; №728).

3. С.С. Артемьев. "Устойчивость численных методов решения стохастических дифференциальных уравнений." Сибирский математический журнал, 1994, т. 35, №6, 1210-1214.

4. Artemiev S.S., Averina T.A. Numerical Analysis Systems of Ordinary and Stochastic Differential Equations. VSP, Utrecht, The Netherlands, 1997 (176 p.)

Инструментальные средства создания - Язык программирования Фортран