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

На правах рукописи

ДОЛГОВ Артём Анатольевич

НЕЧЕТКАЯ ЛОГИКО-ЛИНГВИСТИЧЕСКАЯ МОДЕЛЬ И АЛГОРИТМЫ РАСЧЕТА ОЦЕНКИ ЖИВУЧЕСТИ ИНФОРМАЦИОННЫХ СТРУКТУР

Специальность 05.13.17 «Теоретические основы информатики» (технические науки)

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

11 2014

Тамбов-2014

005556679

005556679

Работа выполнена в федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Тамбовский государственный технический университет» (ФГБОУ ВПО «ТГТУ»),

Научный руководитель Доктор технических наук, профессор

Громов Юрий Юрьевич

Официальные оппоненты: Душкин Александр Викторович,

доктор технических наук, доцент, ФКОУ ВПО «Воронежский институт ФСИН России», кафедра управления и информационно-технического обеспечения, начальник

Зарубин Владимир Сергеевич, доктор технических наук, профессор, ФГКОУ ВПО «Воронежский институт Министерства внутренних дел Российской Федерации», кафедра вневедомственной охраны, профессор

Ведущая организация Фрязинский филиал ФГБУН Института

радиотехники и электроники им. В. А. Котель-никова РАН

Защита диссертации состоится 25 декабря 2014 г. в 15.30 на заседании диссертационного совета Д 212.038.24 при ФГБОУ ВПО «Воронежский государственный университет» по адресу: 394006, г. Воронеж, Университетская пл., д. 1, ауд. 226.

С диссертацией можно ознакомиться в библиотеке и на сайте ФГБОУ ВПО «Воронежский государственный университет», http://www.science.vsu.ru.

Автореферат разослан « ¿У » ноября 2014 г.

Ученый секретарь диссертационного совета

Воронина Ирина Евгеньевна

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы исследования. В инфраструктуре современного информационно-индустриального общества информационные структуры (ИС) занимают одно из ключевых мест. Типовыми задачами, которые возникают перед инженерами и аналитиками, являются: расчет распределения потоков внутри ИС при влиянии на ее структуру негативных воздействий (НВ) для поддержания ее функционирования; выявление «узких мест» каналов, которые подвержены перегрузке, узлов, отказывающих в обслуживании при увеличении нагрузки и т.д.

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

Живучесть системы — ее способность выполнять основные функции во время атак, повреждений и аварийных ситуаций (ГОСТ 27.002-89). В последние годы повышается интерес к данной характеристике как в теоретическом, так и в практическом отношении. Различные НВ способны выводить из строя отдельные участки ИС, причем на достаточно длительный срок. Живучесть определяет работоспособность ИС под влиянием таких воздействии. Таким образом, живучесть проявляется как свойство ИС адаптироваться к новой ситуации и противостоять НВ, при этом выполнять свою целевую функцию. Это можно обеспечить за счет соответствующего изменения структуры и поведения системы, даже в том случае, если ее части подвержены серьезным повреждениям. НВ рассматривается как определенный вид воздействия, параметры которого превышают допустимые значения, на которые рассчитан элемент системы при его разработке и эксплуатации. В нашем случае такими элементами являются узлы и связи между ними.

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

Степень разработанности темы исследования. Подход к оценке качества работы ИС с точки зрения живучести является относительно новым в России. Проблеме оценки живучести ИС посвящен ряд работ как отечественных авторов (А. Г. Додонов, В. Ф. Крапивин, М. Г. Кузнецова, В. М. Вишневский, Ю. М. Парфенов, Д. JI. Белоцерковский, Ю. Е. Мельников, Ж. С. Сарыпбеков, Ю. Е. Малашенко, И. А. Рябинин, Б. С. ФлеГппман, Ю. Ю. Громов, Д. В. Ландэ, И. Ю. Стекольников и др.), так и зарубежных (С. J. Colbourn, Y. Li, К. Sekine, Н. Imai, М. X. Cheng, D.-Z. Du, A. E. Smith, S. Tani и др.), в которых разработаны аналитические модели, адекватно описывающие процесс расчета оценки живучести ИС. Однако в настоящее время особое значение представляет задача разработки аналитического описания, которое обобщает полученные ранее результаты и позволяет не только осуществить разработку новых методов анализа и проектирования ИС, но и решить задачи расчета живучести ИС сложной структуры и большой размерности (более 50-ти узлов).

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

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

Объект исследования: информационные структуры.

Предмет исследования: нечеткая логико-лингвистическая модель и алгоритмы расчета оценки живучести ИС.

Цель и задачи. Целью исследования являлось повышение эффективности расчета оценки живучести ИС при влиянии НВ в условиях отсутствия информации о вероятности разрыва связей и их статистических характеристиках с помощью разработанных нечеткой логико-лингвистической модели и алгоритмов последовательного и параллельного (распределенного) расчета. Для достижения цели были поставлены следующие задачи:

1) выполнить анализ существующих подходов к оценке живучести ИС;

2) построить нечеткую логико-лингвистическую модель расчета оценки живучести ИС при влиянии НВ, которая базируется на полиноме Татта, теории графов, теории возможностей и теории нечетких множеств;

3) разработать на основе построенной модели алгоритмы последовательного и параллельного (распределенного) расчета оценки живучести ИС, синтезированного на основе комбинаторных формул (свертка Вандермонда) и технологии распределенных вычислений;

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

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

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

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

ния (свертка Вандермонда) и технологии распределенных вычислений, отличающегося параллельным выполнением алгоритма расчета полинома Татта и, следовательно, применяемого при GRID- и кластерных вычислениях.

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

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

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

Положения, выносимые на защиту:

- разработанная нечеткая логико-лингвистическая модель расчета оценки живучести ИС, базирующаяся на предложенных продукционных правилах с лингвистическими переменными (время реакции, пропускная способность, топология, размер, доступность, надежность, среда передачи), позволяет определять и использовать возможность разрыва связи ИС при полиномиальном расчете;

- предложенные алгоритмы последовательного и параллельного (распределенного) расчета оценки живучести ИС, основанного на комбинаторной свертке Вандермонда и СЛЮ-технологиях, способного распараллелить алгоритм вычисления полинома Татта, позволяют повысить эффективность расчета.

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

Основные результаты работы представлены и обсуждены на: Всероссийской конференции с элементами научной школы для молодежи «Математическое моделирование в технике и технологии» (г. Воронеж, 2011); II Международной кластерной научно-практической конференции «Аспекты ноосферной безопасности в приоритетных направлениях деятельности человека» (г. Тамбов, 2011); Всероссийской научно-практической конференции «Актуальные проблемы деятельности подразделений УИС» (г. Воронеж, 2012); Всероссийской научно-практической конференции «Математические методы и информационно-технические средства» (г. Краснодар, 2012); XIII Международной научно-методической конференции «Информатика: проблемы, методология, технологии» (г. Воронеж, 2013); семинарах кафедры ИСиЗИ ФГБОУ ВПО «ТГТУ».

В 2011 г. получен грант на основе результатов диссертационной работы по программе «Участник молодежного научно-инновационного конкурса» («У.М.Н.И.К»), В 2012 г. результаты исследования использовались при выполнении НИОКР по программе «СТАРТ».

Внедрение результатов исследования. Основные положения диссертационной работы использованы при обучении студентов кафедры «Информационные системы и защита информации» Института автоматики и информационных технологий ФГБОУ ВПО «ТГТУ». Результаты диссертационной работы приняты к внедрению на кафедре «Информационные системы и защита информации» ФГБОУ ВПО «ТГТУ», в войсковой части 61460 (г. Тамбов), ОАО «Медтехника» (г. Тамбов), ООО «КОНУС-ИТ» (г. Тамбов), что подтверждено актами о внедрении результатов исследований.

Публикации. По теме диссертации опубликовано 29 работ, в том числе 5 статей в изданиях, рекомендованных ВАК при Минобрнауки России, получено 6 свидетельств о государственной регистрации программы для ЭВМ.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка использованных источников, содержащего 159 наименований, и приложений. Общий объем диссертации составляет 148 страниц, из них список использованных источников — 16 страниц. Основной текст работы содержит 66 рисунков и 4 таблицы.

Работа соответствует п. 2. «Исследование информационных структур, разработка и анализ моделей информационных процессов и структур» Паспорта специальности 05.13.17 «Теоретические основы информатики».

Работа выполнена в рамках научных школ ФГБОУ ВПО «ТГТУ» и МГУ имени М. В. Ломоносова (механико-математический факультет), плана стратегического развития Института автоматики и информационных технологий ФГБОУ ВПО «ТГТУ».

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В главе 1 «Проблема оценки живучести информационных структур и ее изложение в научной литературе» рассмотрены способы формализации ИС в виде графов и матриц, понятия живучести в различных областях и применительно к ИС, представлены существующие подходы к оценке живучести ИС.

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

При исследовании функциональной живучести ИС особенности топологии межкомпонентных связей учитываются опосредовано. Предполагается, что в ИС обеспечивается необходимая связность работоспособных компонентов. В процессе функционирования ИС ее компоненты могут находиться в одном из состояний: работоспособном, не работоспособном, частично работоспособном, т.е. работоспособном, но при частичном снижении (в допустимых пределах) значения каких-либо показателей качества функционирования. 4

Учитывая, что задачи анализа и синтеза ИС средней (10 — 50 узлов) и большой (свыше 50 узлов) размерности являются ЛТ-сложными, а для их решения часто приходится строить отдельную модель, объемы затрачиваемого на расчеты времени различных физических ресурсов могут быть велики. Исследования в данной области ведутся с середины XX в., и выработано множество подходов для решения задачи оценки живучести, основными из которых являются:

1) вероятностные полиномиальные процедурные модели расчета;

2) процедурные модели, построенные с использованием элементов искусственного интеллекта (так называемая искусственная нейронная сеть (ИНС);

3) потоковые модели, основанные на критерии допустимости.

В процессе анализа данных подходов к оценке живучести ИС были выявлены следующие недостатки:

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

— при вероятностном полиномиальном подходе вероятность разрыва связи ИС на практике, как правило, невозможно получить, проводя многочисленные эксперименты. Это требует зачастую колоссальных материальных и временных затрат, и не является целесообразным. Иногда проведение подобных экспериментов вовсе неприемлемо;

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

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

Глава 2 «Нечеткая логико-лингвистическая модель расчета оценки живучести информационных структур» посвящена разработке модели расчета оценки живучести ИС, которая позволила уйти от вероятностного подхода к оценке живучести ИС, обладающего существенным недостатком — сложностью, а зачастую невозможностью определения вероятности разрыва связи ИС. Модель базируется на теории возможностей, позволяя определить искомое значение возможности разрыва связи ИС исходя из опыта экспертов, заранее заложивших в нее свои знания.

Вводятся лингвистические переменные (время реакции (X]), пропускная способность (х2), размер (хз), доступность (хД надежность (х5), топология (хб), среда передачи (х7), возможность разрыва связи (у)) с соответствующими им терм-множествами. Например, <хь Тх,Хъ 6'ь М,>, гдех! - «время реакции» ИС; Т\ - {«низкое», «среднее», «высокое»}; Хх - [0, 1000] (мс); - процедура образования новых термов с помощью различных связок и модификаторов; М\ — процедура задания на Х\ = [0, 1000] нечетких подмножеств А и = «низкое», А\2 = «среднее», А и = «высокое» (рис. 1), а также нечетких множеств для термов из О] (7",).

А 1

0,8 0,6 0,4 0,2

\ А /

\ у /\ /

А,, А и !

х У

А А

0

200

400

600

800

1000 Хь мс

Рис. 1. Формализация лингвистической переменной л^ («время реакции»)

Затем формируется база нечетких правил с ЛЖЮ-структурой (рис. 2) из множества отдельных нечетких продукционных правил вида «ЕСЛИ А, ТО В» (где А и В — предпосылка и заключение правила).

к

9 К

X] ->

Характеристики ИС

М180-структура базы нечетких правил

1 У

Возможность разрыва связи ИС

Рис. 2. Л//50-структура базы правил нечеткой продукционной модели

Фрагмент правил нечеткой логико-лингвистической модели имеет следующий вид:

П]: ЕСЛИ «время реакции» ЕСТЬ «низкое» И «пропускная способность» ЕСТЬ «высокая» И «размер» ЕСТЬ «малый» И «доступность» ЕСТЬ «отличная» И «надежность» ЕСТЬ «высокая» И «топология» ЕСТЬ «звезда» И «среда передачи» ЕСТЬ «кабель подземный», ТО «возможность разрыва связи» ЕСТЬ «низкая»

(П]: ЕСЛИ XI ЕСТЬ А„Их2 ЕСТЬ А23 И х3 ЕСТЬ А3[ Их4 ЕСТЬ А44 И х5 ЕСТЬ А53 И х6 ЕСТЬ А62 И х7 ЕСТЬ А71, ТО у ЕСТЬ В{)

П2: ЕСЛИ х, ЕСТЬ Л12 И х2 ЕСТЬ А22 И х3 ЕСТЬ АЪ2 И х4 ЕСТЬ А43 И х5 ЕСТЬ А52 И х6 ЕСТЬ Абз И х7 ЕСТЬ А1Ъ ТО у ЕСТЬ В2

П20: ЕСЛИ X) ЕСТЬ А13 И х2 ЕСТЬ А2Х И х3 ЕСТЬ А33 И х4 ЕСТЬ А41 И х5 ЕСТЬ А51 И х6 ЕСТЬ А61 И х7 ЕСТЬ А13, ТО у ЕСТЬ В3.

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

- используем сформированную базу нечетких правил;

— задаем декартово произведение нечетких множеств выражением:

*Л2*Я'б*л;7 (Xl' Х2 > *3 > > *5, , ) = (^ШЦ^

(.Гз),Г{цл. (х4),Г{ц~. (х5),Г{цл, (*6),ц . (х7)}}}}}}, (1)

л/3 л14 л/5 А:6 АЦ

где А'цj 7) - нечеткое множество, отражающее фактическое значение переменной Xj 7 (х[ 1), определенное на X, с функцией принадлежности Hj (дГ] 7) g [0,1], / = 1...20 - номер правила вывода.

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

"i i=1-20 л/->«1 = S sup {Tip.J {X\),T{\\7 (x2),T(ii~. (x3),T(p-. (x4), (2)

Г(ц~. (х5),Г(ц~. (*6),r(Hj (х7),цй Ы)))))))}.

у'/6 у'/7

Этап 1. Для заданных значений входных переменных u~ (jcr,) (/ = 1...20,

А,у J

j= 1...7) определяем степени срабатывания (истинности) каждой предпосылки каждого правила.

Этап 2. По каждому из правил а, производим агрегирование степеней истинности предпосылок:

а, = (х[),7>, (х'2),(хз),T{yi2 (х'4),

11 ^12 л13 л14 хлч

ЭтапЗ. По каждому из правил а, производим активизацию (определение степеней истинности) заключений |i (у) :

И g; 00 = , Ц й] О')} , • • •, Ц5-о (у) = ^{«20, Ив20 00} • (5)

На рисунке 3 представлена активизация заключений для двух лингвистических переменных Xj и х2.

Этап 4. По всем правилам ai производим аккумулирование полученных на предыдущем этапе заключений р. (у) . В итоге для выходной переменной формируется нечеткое множество с функцией принадлежности

V*(у) = S{ng>(y), SO^OO,..., ¿{ц^ОО, 00}}}.

На рисунке 4 представлено аккумулирование заключений по правилам, проиллюстрированным на рис. 3. Объединение найденных усеченных нечетких множеств проводится с использованием ¿"-операции.

Правило 1: Я1И.1)

^12(^23)

влв,)

Правило 20:

Ц1

М 1

0,5

0,5 ■

Ц1

0,5

500

1000 0 -V], мс х'2

50

100

х2, Мбит/с

Д2о(вз)

50

100

У, %

Рис. 3. Иллюстрация активизации заключений алгоритма нечеткого вывода

Этап 5. Полученное нечеткое множество приводится к четкому виду с помощью операции, в которой используется центроидный метод дефаззифи-

кации. В этом случае четкое значение выходной переменной у' ^¡л (см. рис. 4) определяется как

" \ «центр тяжести» для (у):

ц 1

0,8 0,6 0,4 0,2

0

20

40

60

80

100

Рис. 4. Иллюстрация аккумулирования заключений

тах

/л^'ООФ

гтп у

1 тах

(6)

где Ппт, — границы интервала носителя нечеткого множества выходной переменной у.

В данном алгоритме нечеткого вывода использовались следующие операции:

— нечеткая импликация — Г-импликация;

— активизация заключений правил — min-активизация (sup-min-композиция);

- аккумулирование активизированных заключений правил - ^-операция;

- Г-норма - min-конъюнкция, iS-норма — шах-дизъюнкция; Полученное значение возможности разрыва связи у используем для вычисления оценки живучести с помощью полинома Татта. Данный полином рассчитывается по формуле

па,х,у)= ХОс-ц^-л^^и-дл) (7)

AqE

где f. 2е —> Z — это функция ранжирования графа G, т.е./(А) — это ранг подграфа G'=(V(A),A): количество вершин \V(Á)\ минус количество компонентов связности G'.

Оценка живучести ИС рассчитывается с помощью полинома Татта по формуле

А^Е,р{А)=р(Е)

Г i 1 , , ( 1 \ ^

х Z а-/')1 =р^-р(Е\1-руЫса,-\

А^Е,р(А)=р(Е) 1 Р J V PJ

где р — возможность разрыва связи (ребра) графа G (у1), определяемая по логико-лингвистической модели; А — множество ребер подграфа G'; Е- множество ребер графа G.

В главе 3 «Разработка алгоритмов оценки живучести информационных структур» представлены алгоритмы: последовательного расчета оценки живучести ИС, работы серверной части ПО оценки живучести, параллельного (распределенного) расчета оценки живучести ИС. Для представления алгоритмов выбран язык UML.

Для решения задачи распараллеливания алгоритма вычисления полинома Татта представлен алгоритм построения ¿-элементных подмножеств множества {1, ..., п} в лексикографическом порядке, а также алгоритм построения сочетаний с помощью индексации. Алгоритм последовательного расчета оценки живучести с помощью полинома Татта представлен на рис. 5.

Точный расчет живучести ИС представляет собой W-сложную задачу, затраты на решение которой возрастают экспоненциально с ростом числа узлов и связей ИС. Для расчета оценки живучести полинома графа, состояще-

" " п\

го из п ребер, необходимо пройтись по /Сп = -:-= 2"-1 подгра-

ых *!("-*)!

фам, т.е. по всем остовным подграфам графа G, множество ребер которых

представляет собой всевозможные выборки сочетаний из п по к = \, п ребер

графа О. То есть речь идет о миллиардах вычислений и разумно использовать параллельные или СЛ/О-вычисления.

1

(вычислить возможность разрыва связи)

(вычислить количество итераций для расчета)

_Í_

(полином Татта=0, счетчик итератора=(количество вершин графа G)-lj

[счетчик> количество ребер графа G]

[счетчик<=количество ребер графа G]

£

(Увеличить счетчик на l) (построить матрицу смежности подграфа н)

(вычислить количество компонент связности подграфа Н, графа й и ребер н)

(добавить к полиному Татта вычисленное значение)

[Возможных комбинаций нет]

[Еще есть возможные комбинации]

(получить следующую комбинацию подграфа~н)

JL

(произвести расчет оценки живучести r)

Рис. 5. Алгоритм последовательного расчета оценки живучести ИС

При выполнении СЛ/О-вычислеиий возникает одна из самых сложных проблем — распараллеливание алгоритма решения задачи. Некоторые алгоритмы вообще не поддаются распараллеливанию. В нашем случае необходимо распараллелить алгоритм генерации сочетаний без повторений.

Алгоритм оценки живучести ИС на основе распределенных вычислений представлен на рис. 6.

Иццексом сочетания назовем порядковый номер I этого сочетания в последовательности всех сочетаний, расположенных в лексикографическом порядке,

1 </<С„ . Индекс I сочетания фх, Ь2, ..., Ьк) из л по А: может быть вычислен по

к 6,-1

формуле свертки Вандермонда 7 = 1 + ^ ^ Ск„2), где Ь0 = 0 и С°_у = 1.

/=1 У=4/_1+1

(вычислить возможность разрыва связи)

С

Полином Татта:

2)

_ЗГ_

(ввести номер первой и последней порции, размер порции для клиента)

Зк_

V

(отправить начальную и конечную позиции для расчета клиенту)

VI/ ~~

(вычислить стартовое количество ребер и индекс сочетания)

Клиентская часть полинома Татта

3

[стартовое количество ребержоличество ребер графа С или достигнута конечная позиция расчета]

Ж

[Первая генерация подграфа Н]

(построить сочетание с помощью индексации) (счетчик итератора=стартовое количество ребер)

~1

V

ж

(построить подмножество в лексикографическом порядке

(получить подграф н)

VI/

(построить матрицу смежности подграфа н)

-Ж-

Увеличить счетчик на 1

Вычислить количество компонент

связности подграфа Н, графа 6 и ребер н)

Ж

(добавить к части полинома Татта вычисленное значение)

[Еще есть возможные комбинации]

_* _

(передать полученное значение части полинома Татта серверу)

(добавить к полиному Татта полученное значение от клиента) [Еще есть порции задачи]

(произвести расчет оценки живучести 1^)

Рис. 6. Алгоритм параллельного (распределенного) расчета оценки живучести ИС

11

Рассмотрим теперь, как сочетание (6Ь Ь2, ..., Ьк) строится по его номеру I. Пусть 1 < ? < к и 0 = ¿о < ¿1 < Ь2 < ... < ь Для любого] в + 1, + 2,..., п - к + (} через ^ обозначим число всех сочетаний с префиксами (6Ь Ь2, ...,

¿><-ь>*), где ге {¿,-1 + 1, Ь,-1 + 2, - 1}. В каждом из этих сочетаний недостающие к — / элементов берутся из п —г элементов г + 1, ..., п, поэтому

7-1 _ /-1

5у= ^Сп_'г. Положим также 5'= . Это есть число всех сочетаний с

г-Ь,_ 1+1 /=1

префиксами {Ьи Ь2, ..., Ь,-и а,) для / < í — 1 иа, < Ь„ т.е. всех сочетаний, предшествующих сочетаниям с префиксом (6Ь Ь2,..., Ь, ,).

Пусть 1 < ? < к и (¿1, Ь2, ..., Ь, ]) есть префикс сочетания с индексом /, тогда /-й элемент Ь, этого сочетания равен наименьшему из таких у, что

Ь,. 1 <]< п - к + I » I < ^ + , если такие у существуют, и6'=я — £ + /в противном случае.

Клиент, получив от сервера начальную /\,аг1 и конечную А^р позиции для расчета, производит генерирование топологий ИС с помощью алгоритма построения сочетаний с применением индексации. Вычислив значение Т для необходимых топологий, клиент передает результат серверу, где происходит суммирование данной величины в общее значение полинома Татта.

Алгоритм расчета оценки живучести на стороне клиента аналогичен представленному алгоритму на рис. 5 за исключением того, что данный алгоритм учитывает построение сочетаний с помощью индексации.

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

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

Была рассмотрена топология ИС (55 рабочих станций), выделены особо значимые узлы ИС, выход из строя которых приведет к отказу части или всей ИС. Данная ИС содержит 7 значимых связей, которые соединяют 8 значимых узлов. Для повышения живучести ИС добавим связи между 1-м и 6-м, 7-м и 8-м узлами. Добавление двух связей было обусловлено принятыми экономическими ограничениями на затраты резервных каналов.

Результаты оценки живучести исходной и новой ИС для различных возможностей разрыва связи представлены на рис. 7.

Из графика видно, что добавление двух резервных каналов связи значительно повысило уровень живучести исходной ИС (примерно на 35...40%).

Возможность разрыва связи, % а) исходная ИС ~~" — б) новая ИС

Рис. 7. Оценка живучести для различных возможностей разрыва связи ИС

Для оценки эффективности разработанных модели и алгоритмов был проведен вычислительный эксперимент. Было использовано 20 компьютеров с одинаковыми характеристиками. Результаты эксперимента представлены на рис. 8.

Таким образом, проведенный эксперимент показал повышение эффективности расчета оценки живучести ИС с точки зрения времени с помощью разработанных модели и алгоритмов (перед алгоритмом на основе вероятностного полиномиального подхода эффективность расчета выше в среднем на 10... 15%), тем самым обеспечив решение поставленной научной задачи и достижение цели исследования.

В заключении сформулированы основные результаты работы:

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

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

15 20 25 30 Количество узлов ИС, шт. Ш Алгоритм на основе вероятностного подхода

■ Разработанный ОЯЮ-алгоритм

Рис. 8. Затраты времени на расчет оценки живучести ИС

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

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

4. На основе разработанных модели и алгоритмов проведены различные имитационные исследования, опытные эксплуатации, которые свидетельствуют о достоверности и повышении эффективности расчетов оценки живучести И С с точки зрения времени в среднем на 10... 15% перед алгоритмом на основе вероятностного полиномиального подхода. Представлены результаты эксперимента, показывающие повышение уровня живучести ИС примерно на 35...40%.

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

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в изданиях, рекомендованных ВАК при Минобрнауки России:

1. Алгоритм оценки живучести сетевых информационных систем / Ю. Ю. Громов, Ю. В. Минин, М. А. Хорохорин, А. А. Долгов // Промышленные АСУ и контроллеры. - 2014. - № 4. - С. 40 - 46.

2. Применение кластерных вычислений для оценки живучести сетевых информационных структур / Ю. Ю. Громов, А. А. Долгов, М. А. Хорохорин, В. Е. Дидрих // Информация и безопасность. - Воронеж : Изд-во ВГУ, 2014. -Т. 17, № 1.-С. 56-61.

3. Использование теории возможностей при оценке живучести сетевых информационных структур / Ю. Ю. Громов, А. А. Долгов, М. А. Хорохорин, Ю. В. Минин // Информация и безопасность. - Воронеж : Изд-во ВГУ, 2014. -Т. 17, №1.-С. 62-67.

4. Применение распределенных информационных систем для оценки живучести нечетких графов / М. А. Хорохорин, А. А. Долгов, М. Ауад, X. Д. Лыонг // Информация и безопасность. - Воронеж : Изд-во ВГУ, 2012. -Т. 15, №2.-С. 245-248.

5. К вопросу оценки живучести сетевых структур с использованием Grid-технологий / А. А. Долгов, М. А. Хорохорин, Ю. В. Минин, А.Б.М.П.Б. Шихук // Информация и безопасность. - Воронеж : Изд-во ВГУ, 2012. - Т. 15, № 2. -С. 249-252.

Статьи и материалы конференций:

6. Решение задачи оценки живучести локальных вычислительных сетей с целью повышения устойчивости их функционирования / А. А. Долгов, М. А. Хорохорин, А. И. Елисеев, Ю. В. Минин // Информатика: проблемы, методология, технологии : сб. науч. тр. XIII Междунар. науч.-метод. конф.: в 4 т. - Воронеж : Изд-во ВГУ, 2013. - Т. 1. - С. 387 -390.

7. Выбор видов средств парирования негативных внешних воздействий на информационную систему / Ю. В. Минин, А. И. Елисеев, А. А. Долгов [и др.] // Информатика: проблемы, методология, технологии : сб. науч. тр. XIII Междунар. науч.-метод. конф. : в 4 т. - Воронеж : Изд-во ВГУ, 2013. -Т. 2.-С. 353 -357.

8. Хорохорин, М. А. Моделирование и оценка нечетких сетевых информационных систем с нахождением оптимальных путей в направленных нечетких графах / М. А. Хорохорин, А. А. Долгов // Проблемы управления, информатизации и моделирования. - Москва : НПЦ «Модуль», 2012. - № 3. -С. 51-59.

9. Долгов, А. А. Применение распределенных вычислений для оценки живучести систем, обладающих сетевой структурой / А. А. Долгов, М. А. Хорохорин // Актуальные проблемы деятельности подразделений УИС : сб. науч. тр. Всерос. науч.-практ. конф. - Воронеж : ООО ИПЦ «Научная книга», 2012.-С.61.

10. Хорохорин, М. А. Применение распределенных систем для оценки живучести сетевых структур в условиях неопределенности / М. А. Хорохорин, А. А. Долгов // Актуальные проблемы деятельности подразделений УИС: сб. науч. тр. Всерос. науч.-практ. конф. - Воронеж : ООО ИПЦ «Научная книга», 2012. -С. 62.

11. Структуризация характеристик живучести сетевых информационных систем / А. И. Елисеев, М. А. Хорохорин, А. А. Долгов, М. П. Аль-Балуши // Математические методы и информационно-технические средства : сб. науч. тр. VIII Всерос. науч.-практ. конф. — Краснодар : Краснодарский университет МВД России, 2012. - 278 с. - С. 72.

12. Системный анализ в обеспечении живучести сетевых информационных систем / А. И. Елисеев, М. А. Хорохорин, А. А. Долгов, М. Ауад // Математические методы и информационно-технические средства : сб. науч. тр. VIII Всерос. науч.-практ. конф. - Краснодар : Краснодарский университет МВД России, 2012. - 278 с. - С. 73.

13. К вопросу о показателях живучести сетевых информационных систем / А. И. Елисеев, М. А. Хорохорин, А. А. Долгов, Хак Д. Лыонг // Математические методы и информационно-технические средства : сб. науч. тр. VIII Всерос. науч.-практ. конф. - Краснодар : Краснодарский университет МВД России, 2012.-278 с.-С. 74.

14. Методы обеспечения и повышения живучести сетевых информационных систем / А. И. Елисеев, М. А. Хорохорин, А. А. Долгов, К. М. Копылов // Математические методы и информационно-технические средства : сб. науч. тр. VIII Всерос. науч.-практ. конф. - Краснодар : Краснодарский университет МВД России, 2012. - 278 с. - С. 75.

15. К вопросу исследования живучести информационных систем в рамках механики катастроф / А. И. Елисеев, А. А. Долгов, М. А. Хорохорин, М. Аль Балуши // Прикладная математика, управление и информатика : сб. науч. тр. -Белгород : БелГУ, 2012. - Т. 1. - С. 122 - 125.

16. Использование системы Х-СОМ для оценки живучести сетевых структур / А. И. Елисеев, А. А. Долгов, М. А. Хорохорин, М. К. Силла // Прикладная математика, управление и информатика : сб. науч. тр. — Белгород : БелГУ, 2012. - Т. 2. - С. 72 - 76.

17. К вопросу оценки живучести сложных систем с использованием распределенных систем на основе графовой модели / А. И. Елисеев, А. А. Долгов, М. А. Хорохорин, Хак Д. Лыонг // Прикладная математика, управление и информатика : сб. науч. тр. - Белгород : БелГУ, 2012. - Т. 2. - С. 287 - 292.

18. Оценка живучести сетевых структур с использованием системы Matlab / А. А. Долгов, О. Г. Иванова, X. Д. Лыонг, М. Ауад // Вестник Воронежского института ФСИН России. - Воронеж : ООО ИПЦ «Научная книга», 2011. — № 1.-С. 56-59.

19. Долгов, А. А. Синтез программного обеспечения моделирования и оценки живучести сетевых информационных систем / А. А. Долгов, М. А. Хорохорин // Аспекты ноосферной безопасности в приоритетных направлениях деятельности человека : сб. науч. тр. II Междунар. кластерной науч.-практ. конф. - Тамбов : Изд-во «TP-принт», 2011. - С. 92-94.

20. Долгов, А. А. Исследование живучести сетевых информационных систем с использованием нейросетевых моделей / А. А. Долгов // Вестник Воронежского института высоких технологий. - Воронеж. - 2010. - Вып. 6. -С. 241 -244.

Свидетельства о государственной регистрации программы для ЭВМ:

21. Свидетельство о государственной регистрации программы для ЭВМ 2011614063 Российская Федерация. Программа: Аудит сетевых систем с использованием полиномиальной оценки живучести / А. А. Долгов, М. А. Хорохорин ; № 2011612184 ; заявление 04.04.11 ; зарегистрировано в реестре программ для ЭВМ 25.05.11.

22. Свидетельство о государственной регистрации программы для ЭВМ 2011610917 Российская Федерация. Программа: Алгоритм оценки живучести сетевых информационных систем с использованием полинома Татта / А. А. Долгов, Ю. Ю. Громов, М. А. Хорохорин ; № 2010617463 ; заявление 29.11.10 ; зарегистрировано в реестре программ для ЭВМ 24.01.11.

23. Свидетельство о государственной регистрации программы для ЭВМ 2011610919 Российская Федерация. Программа: Алгоритм оценки живучести нечетких сетевых информационных систем с использованием полинома Татта / М. А. Хорохорин, Ю. Ю. Громов, А. А. Долгов ; № 2010617465 ; заявление 29.11.10 ; зарегистрировано в реестре программ для ЭВМ 24.01.11.

Подписано в печать 24.10.2014. Формат 60х 84/16. 0,93 усл. печ. л. Тираж 100 экз. Заказ № 496

Издательско-полиграфический центр ФГБОУ ВПО «ТГТУ» 392000, г. Тамбов, ул. Советская, д. 106, к. 14 Тел. 8(4752) 63-81-08. E-mail: izdatelstvo@admin.tstu.ru