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

Используемый алгоритм: Вычисление вероятности блокировки пакета и средней задержки пакета в сетевом узле проводится с использованием СМО специального вида, разработанных с учетом специфики различных типов сетей (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.)

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

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

Назначение - Противодействие разрушающим воздействиям DoB (Depletion of Battery), направленным на быструю разрядку батареи сенсора в беспроводных сенсорных сетях.
Область применения - Обеспечение безопасности информационных технологий.

Используемый алгоритм - опубликован в статье: Vladimir V. Shakhov: Protecting Wireless Sensor Networks from Energy Exhausting Attacks. Lecture Notes in Computer Science, Volume 7971, 2013, pp 184-193. (ISSN0302-9743). Алгоритм основан на методе кумулятивных сумм для обнаружения «разладки» случайного процесса. 

Функциональные возможности -  Требуется настройка параметров алгоритма, в частности порогового значения, для того, чтобы запаздывание в обнаружении "разладки" было приемлемым в конкретном случае.  Априорная информация о характере распределения моментов возникновения «разладки» не требуется. Уменьшение порогового значения приводит к более быстрому обнаружению атаки, однако при этом увеличивается вероятность ложной тревоги. Во вложении имеется график зависимости оценики математического ожидания времени до объявления ложной тревоги от величины порога. Кроме того, в прилагаемом архиве содержится С++ файл (example_alg.cpp), демонстрирующий возможности программы  (создание потока случайных наблюдений, по которым делается вывод о наличии атаки, инициализация параметров атаки, вычисление порогового значения, обнаружение атаки)  и скриншот с результатом работы.  

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

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

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

Программа производит точный расчет вероятности связности подмножества вершин в случайном графе с ненадёжными ребрами. Расчёт данной характеристики представляет собой 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) внесены следующие изменения:

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

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

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

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

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

Используемый алгоритм - Программа реализует алгоритм  сегментации изображения с предварительным выделением областей, связных в плоскости изображения и однородных по признакам  [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.

Назначение - программа предназначена для точного расчета надежности сети с использованием ресурсов кластера НКС-30Т ССКЦ КП СО РАН.
Область применения - анализ надёжности и живучести сетей различного назначения.

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

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

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

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

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

[1] Мигов Д.А. Параллельный метод для расчета структурной надежности сети // Тезисы докладов XIV Всероссийской конференции молодых ученых по математическому моделированию и информационным технологиям, Томск, ТНЦ СО РАН, 2013. Новосибирск, ИВТ СО РАН, 2013, с. 42.

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

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

Назначение - программа предназначена для точного расчета надежности сети с  ограничением на диаметр.

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

При анализе надёжности сетей обычно используется такой показатель надёжности, как вероятность связности сети. Однако во многих случаях требуется обеспечить не просто существование пути между каждой парой выбранных узлов, а существование пути, проходящего через ограниченное число транзитных узлов (p2p-сети, ad hoc-сети). В таких случаях может быть использован другой показатель надёжности – вероятность связности сети с ограничением на диаметр [1], т.е. вероятность того, что любые два полюса сети соединены путём, состоящим из ограниченного количества каналов связи.

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

Для двухполюсной сети, с целью ускорения расчётов в программе осуществляется предварительная декомпозиция сети на двусвязные компоненты, для каждой из которых проводится декомпозиция по двухвершинным сечениям. Данный алгоритм опубликован в [2,3]. В случае если сеть многополюсная, расчёт осуществляется по методу, опубликованному в [1].

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

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

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

[1] Cancela H., Petingi L. Reliability of communication networks with delay constraints: computational complexity and comlete topologies // Int. J. of Mathematics and Mathematical Sciences. 2004. V. 29. P. 1551-1562.

[2] Мигов Д.А. Расчет надежности сети с ограничением на диаметр с применением точек сочленения // Автоматика и телемеханика. 2011. – № 7. – С. 69-74.

[3] Migov D.A., Rodionov A.S. Decomposing Graph with 2-node cuts for Diameter Constrained Network Reliability Calculation // Proc. of the 7th Int. Conference on Ubiquitous Information Management and Communication (ACM ICUIMC 2013), Kota Kinabalu, Malaysia, 2013. ACM New York, USA, 2013. Article No. 39, ISBN 978-1-4503-1958-4.

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

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

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

Точный расчет надёжности сети представляет собой NP-трудную задачу. Однако при анализе надёжности сети знать точное значение надёжности не всегда необходимо, иногда достаточно установить факт, превосходит ли надёжность исследуемой сети величину заданного порога. Основываясь на известном методе ветвления (factoring method), можно организовать итерационный процесс уточнения верхней и нижней границы надёжности и остановить его при достижении одной из границ значения заданного порога. Данный подход был предложен в [1].

Программа позволяет устанавливать, является ли сеть достаточно надёжной по отношению к заданной величине надежности (порогу) для двух показателей надёжности: вероятности связности сети, и среднему значению (по всем парам узлов) для вероятности связности пары узлов сети.

Если в качестве показателя надёжности сети выбрана вероятность связности, то для ускорения расчетов осуществляется предварительная декомпозиция сети на двусвязные компоненты, для каждой из которых проводится декомпозиция по двухвершинным сечениям. После этого запускается процесс уточнения оценок надёжности для каждого из полученных в процессе декомпозиции графов. Данный алгоритм опубликован в [2]. 

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

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

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

[1] Won J.-M., Karray F. Cumulative Update of All-Terminal Reliability for Faster Feasibility Decision // IEEE Trans. On Reliability. September 2010. Vol 59, no 3. P. 551-562.  

[2] A. Rodionov, D. Migov, and O. Rodionova. Improvements in Efficiency of Cumulative Updating of All-Terminal Network Reliability // IEEE Transactions on Reliability. Vol. 61, issue 2. June 2012. - P. 460-465.

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

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

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

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

- добавлена возможность устанавливать ограничение на время расчёта. Если расчёт не был окончен за отведённое время, выводятся полученные к данному моменту значения границ надёжности;

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

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

Назначение:

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

   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.)

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

Назначение - генерация псевдо-случайных Unit Disk Graphs (UDG-графов)
Область применения - моделирование сенсорных и Mesh сетей

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

Граф G=(V,E) называется UDG-графом (unit disk graph), если ребро (u,v)  существует тогда и только тогда, когда расстояние между вершинами u и v меньше либо равно 1 (в общем случае - d).Программа генерирует на заданной области случайные UDG-графы с наперед заданными свойствами (связность, ограничение на степень вершин, ограничение на количество хопов).

Реализованы три способа генерации UDG-графов::

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

Функциональные возможности - Во вложении приведена таблица времени генерации UDG-графов в зависимости от количества вершин и способа генерации.
Инструментальные средства создания - Lazarus.

[1] Furuzan Atay Onat, Ivan Stojmenovic, Halim Yanikomeroglu Generating random graphs for the simulation of wireless ad hoc, actuator, sensor, and internet networks. Pervasive and Mobile Computing, 4:597-615, 2008.

[2] Шахов В.В., Соколова О.Д., Юргенсон А.Н. "Эффективный метод для генерации псевдо-случайных UDG-графов" // Труды конференции «Информационные технологии и системы — 2013», Светлогорск, ISBN 978-5-901158-23-4, стр. 411-414.

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

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

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

[1] R.M. Haralick, K. Shanmugam, I. Dinstein. Textural Features for Image Classification // IEEE Trans. Syst. Man. Cybern. 1973,Vol. SMS-3, pp. 610 -621.

[2] Sidorova V.S. Unsupervised Classification of Image Texture. // Pattern Recognition and Image Analysis. – 2008 - . Vol. 18,  N 4. - P. 694-700..

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