Новости

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

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

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

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

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

[1] Мигов Д.А. Об одном показателе надежности для сетей с отказами узлов // Труды 2-й Международной конференции молодых ученых "Математическое моделирование фрактальных процессов, родственные проблемы анализа и информатики", Нальчик, 2012. С. 172-175.

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

2012-12-29

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

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

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

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

[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 5.

По сравнению с 1 версией программы (зарегистрирована в Каталоге ФАП СО РАН, номер PR11074), в данной версии добавлена возможность анализа сетей по еще одному показателю надежности - среднему значению (по всем парам узлов) для вероятности связности пары узлов сети

2012-12-27

Поиск оптимальных потоков данных в системах обработки информации

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

Программа осуществляет поиск в сети:

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

Область применения - Информационные сети, сбор информации
Используемый алгоритм -поиск максимального многопродуктовго потока, поиск дополняющих путей. Алгоритм опубликован в: Томас Кормен и др. Алгоритмы: построение и анализ INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296.

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

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

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

2012-12-19

Вычисление текстурных признаков изображения, основанных на модели SAR

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

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

Используемый алгоритм - В каждой точке двумерного полутонового изображения вычисляется вектор статистических текстурных признаков, представляющих собой приближенные значения параметров модели SAR (Simultaneous Autoregressive). Применяется метод максимального правдоподобия и итеративная схема, предложенные в [1], [2], [3]. Различительная мощность признаков модели выше, чем признаков известной системы Харалика [4]. Это показано в [1] для контролируемой классификации, в [2] - для неконтролируемой классификации леса на аэроснимках. Использование признаков SAR для неконтролируемой классификации леса иллюстрировано на сайте http://loi.sscc.ru/lab/RFFI10/RU/svs10.htm.

[1] Kashyap R.L., Chellapa R., Estimation and Choice of Neighbors in Spatial Interaction Models of Images, IEEETrans. Inform. Theory., Vol. 1, 1983, 60-72.

[2] V.S. Sidorova, Unsupervised Classification of Forest’s Image by Texture Model Features, Pattern Recognitionand Image Analysis, 19(4), 2009, 698-703. http://link.springer.com/article/10.1134/S1054661809040208

[3] В.С. Сидорова. Модель текстуры SAR. Труды международного конгресса “ГЕО-СИБИРЬ - 2009”, Новосибирск, 2008, сс.121 - 126.

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

Функциональные возможности - Предлагаемый алгоритм [2,3] вычисляет признаки по модели SAR для всех точек изображения по квадратному окну заданного размера и сохраняет их как мультиспектральный файл в формате raw. Этот файл может быть использован как входной в программах классификации. В предлагаемой программе он может быть преобразован в BMP-файл, где цвет связан с тремя выбранными признаками, и показан на экране. Вычисленные параметры SAR могут интерпретироваться в точке изображения как некоторые визуальные свойства текстуры: направленность, зернистость.

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

2012-12-19

Гистограммный кластерный алгоритм поиска кластеров с отделимостью ниже заданной

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

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

Используемый алгоритм - использован разработанный автором гистограммный иерархический алгоритм. Целью иерархического деления кластеров является достижение предельной детальности для заданной разделимости кластеров. Алгоритм находит различную предельную детальность в подкластерах векторного пространства признаков, которая зависит от свойств области данных. Подробно описан в [1,2]. Приложение алгоритма к пятиспектральному спутниковому снимку иллюстрировано на сайте http://loi.sscc.ru/lab/RFFI10/RU/sidorova_separability.htm.

[1] V. S. Sidorova. Hierarchical Cluster Algorithm for Remote Sensing Data of Earth. // Pattern Recognition and Image Analysis, 2012, Vol. 22, No. 2, pp. 373–379. http://link.springer.com/static-content/0.5825/lookinside/259/art%253A10.1134%252FS1054661812020149/000.png

[2] Сидорова В.С. Новый гистограммный алгоритм с автоматическим выбором детальности кластеризации по заданной разделимости кластеров. Труды международного конгресса “ГЕО-СИБИРЬ - 2012”, Новосибирск, 2012, СС. 149-154

Функциональные возможности - Гистограммный алгоритм не требует задания числа кластеров и никаких предположений о функциях распределения. Требуется ввести изображение и задать значение максимальной разделимости кластеров. Алгоритм найдет кластеры с отделимостью, ниже заданной, и максимальные детальности квантования соответствующих подобластей векторного пространства признаков. Фильтрация кластеров по разделимости, встроенная в процесс иерархической кластеризации, позволяет в результате получить их небольшое число. Алгоритм автоматизирует выбор сеток квантования, совершенствуя метод Наредры [3,4]. Может быть использовано до 8 спектральных каналов, файл входного изображения объемом до 8 мегабайт. Обработка изображения {5 спектр. каналов, 1000*1000 пикселей}, требует около 3 минут для заданной отделимости 0.1 (при максимально возможной 1.), на ПК указанной ниже конфигурации (включая построение 5-мерной гистограммы входных данных). При построении многомерной гистограммы с числом спектральных каналов больше трех используется взаимодействие хэширования и сортировки Шелла, предложенное в [4]. Алгоритм позволяет подробно исследовать структуру данных. Строится карта кластеров (сегментация).

[3] Narendra P.M. and Goldberg M. A non-parametric clustering scheme for LANDSAT // Pattern Recognition. – 1977 – 9 – P. 207-215.

[4] V. S. Sidorova, Separating of the Multivariate Histogram on the Unimodal Clusters, Proceedings of the Second IASTED International Conference “Automation Control and Information Technology”, Novosibirsk, 2005, P. 267–274.

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