Содержание к диссертации
Введение
1 Проблема оценки живучести информационных структур и ее изложение в научной литературе 11
1.1 Информационная структура 11
1.2 Способ формализации информационных структур в виде графа 12
1.3 Матричный способ формализации информационных структур 14
1.4 Анализ понятия живучести в различных областях 18
1.5 Живучесть информационных структур 23
1.6 Анализ существующих подходов к оценке живучести информационных структур 26
1.7 Возможность как мера семейства неопределенности 28
1.8 Выводы по первой главе. Постановка цели и задач исследования 33
2 Нечеткая логико-лингвистическая модель расчета оценки живучести информационных структур 35
2.1 Нечеткая продукционная модель 35
2.2 Лингвистические переменные, характеризующие информационные структуры 40
2.3 Формирование базы нечетких правил 45
2.4 Алгоритм нечеткого вывода 49
2.5 Полиномиальный расчет оценки живучести информационных структур 54
2.6 Выводы по второй главе 55
3 Разработка алгоритмов оценки живучести информационных структур 57
3.1 Выбор языка моделирования 57
3.2 Разработка алгоритма полиномиального расчета оценки живучести информационных структур 60
3.3 Распараллеливание алгоритма расчета оценки живучести информационных структур для GRID-вычислений 61
3.4 Использование кластера для вычисления оценки живучести информационных структур 71
3.5 Построение диаграммы классов 75
3.6 Выводы по третьей главе 77
4 Программная реализация алгоритмов оценки живучести информационных структур 78
4.1 Анализ и выбор языка программирования 78
4.2 Выбор средства разработки 81
4.3 Программная реализация алгоритмов 84
4.4 Тестовый расчет оценки живучести 95
4.5 Оценка достоверности полученных результатов 98
4.5 Оценка эффективности модели и алгоритмов 99
4.6 Опытная эксплуатация ПО оценки живучести 100
4.7 Выводы по четвертой главе 110
Заключение 111
Список использованных источников
- Способ формализации информационных структур в виде графа
- Возможность как мера семейства неопределенности
- Полиномиальный расчет оценки живучести информационных структур
- Использование кластера для вычисления оценки живучести информационных структур
Способ формализации информационных структур в виде графа
Основное значение структуры – это внутреннее устройство чего-либо. Внутреннее устройство находится в связи с категориями целого и его частей. Для выявления аналогов в организации различных по своей природе объектов, изучения их структуры абстрактно без связи с реальными объектами необходимо выявить связи, изучить взаимодействия и соподчиненность составных частей таких объектов. Например, мы занимаемся исследованием и выявлением в иерархической структуре объектов общих свойств, не рассматривая их природу [3]. Сетевая структура есть ничто иное, как комплекс узлов, находящихся между собой в определенной связи. В конкретной сетевой структуре имеются свои узлы с конкретным содержанием, зависящим от характера той конкретной сетевой структуры, о которой идет речь. Если узлы имеют аналогичные коммуникационные коды, то они обладают способностью к коммуникации в рамках данной структуры. В этом случае проявляется свойство открытости сетевых структур, их возможность неограниченно расширяться с помощью включения новых узлов [4].
Информационная структура (ИС) – это сетевая структура, между узлами которой «циркулирует» информация. То есть ей присущи все те проблемы, с которыми сталкиваются аналитики и инженеры-проектировщики при проектировании и обслуживании таких систем. Такой конструкции присуще свойство уязвимости, более того, как правило, сбой в каком-либо одном месте провоцирует перегрузки и выход из строя многих других элементов ИС [1].
В настоящее время происходит интенсивное развитие информационных систем, что приводит к усложнению ИС. Массовое применение ИС в различных областях экономики требует решения вопросов повышения качества функционирования на каждом этапе их жизненного цикла [1].
Для исследования вопросов живучести ИС принимается, что структура формализована графом [5-9], состоящим из множества вершин – узлов связи и множества ребер – линий связи. ИС представляется в виде графа G = (V, E), где V – множество узлов G, E – множество ребер G.
Узлом ИС может быть точка, являющаяся источником или стоком некоторого потока [10], а также точка, в которой величина этого потока изменяется. Поэтому узел можно рассматривать как точку ветвления в ИС. Иногда ребра не имеют физического смысла, а используются для того, чтобы направить поток через узлы в нужной логической последовательности или чтобы выполнялись определенные отношения предшествования.
Обычно узлам приписываются номера, чтобы различать их или иметь возможность ими оперировать в процессе анализа. Очевидно, что нумерацию узлов можно осуществлять произвольным образом. Однако исследования могут упроститься, если их занумеровать в определенном порядке. Ребра графа могут быть неориентированными, ориентированными и биориентированными (рисунок
Очевидно, что биориентированное ребро, соединяющее два произвольных узла i и j, можно заменить двумя ориентированными ребрами (рисунок Ребра графа можно рассматривать как каналы, по которым протекает поток некоторого обобщенного продукта. Чистая величина этого продукта в заданном узле равна разности величин потока, втекающего в узел, и потока, вытекающего из него. Если эта разность положительна, то узел называется источником, а если отрицательна - стоком или конечным узлом графа. Для удобства источником называют каждый узел, из которого поток только вытекает, а стоком - каждый узел, в который поток только втекает.
Например, в ИС, представленной в виде графа на рисунке 1.3, узлы 1 и 2 являются источниками, а узлы 6 и 7 - стоками.
Пример ИС, представленной в виде графа При сведении практических задач к потоковым задачам нередко бывает полезно разбить ИС на составные части исходя из направления потока. Цепью из узла i в узел j называется последовательность ребер и узлов, в которой конечный узел каждого ребра является начальным узлом следующей (исключая первый и последний узлы последовательности). Следовательно, каждое ребро в такой последовательности ориентировано по направлению от узла i к узлу j. Путь отличается от цепи лишь тем, что в нем одно или несколько ребер могут быть направлены не к узлу j, а к узлу i. На рисунке 1.4 последовательность ребер (1, 3), (3, 5), (5, 3), (3, 6) образует цепь, а последовательность ребер (2, 4), (3, 4), (3, 6) – путь.
ИС является неориентированной, если в соответствующем ей графе ни одно из ребер не имеет ориентации. Именно такие ИС и будут рассматриваться в данной работе для оценки живучести.
ИС называется связной, если для любых двух различных узлов ее графа существует, по крайней мере, один соединяющий их путь или цепь [11].
Для дальнейших исследований потребуется оперирование понятием «подграф» исходного графа. Это граф, содержащий некоторое подмножество вершин и ребер данного графа. В частности, остовным подграфом (остовом) называется подграф, содержащий все узлы исходного графа.
Для машинного представления ИС удобно воспользоваться матричным представлением соответствующих графов с помощью матриц смежности и инцидентности [6]. С точки зрения же человеческого восприятия данный метод имеет существенный недостаток – сложность визуализации ИС с помощью данных матриц.
Возможность как мера семейства неопределенности
Теория вероятностей как математическая модель феномена случайности используется в теоретических и прикладных исследованиях благодаря двум ее фундаментальным аспектам [56]: математическому, который основан на теории меры и интеграла; эмпирическому, который основан на простых, математически обоснованных процедурах, которые позволяют при определенных условиях, с одной стороны, на основе данных событийно-частотных наблюдений получить сколь угодно точную аппроксимацию их вероятностной модели, а с другой – при известной вероятностной модели наблюдений предсказать их событийно-частотные результаты.
Вместе с тем при моделировании сложных технических, физических и экономических объектов, субъективных суждений и пр. вероятностные методы де-факто оказались неэффективными. Поэтому с середины прошлого века наблюдается повышенный интерес к моделям случайности, нечеткости и неопределенности, базирующимся на невероятностных теориях.
Существует много факторов, которыми обусловлены причины неэффективности вероятностных методов. Прежде всего, «эмпирический аспект» теории вероятностей далеко не так фундаментален, как математический, поскольку не содержит критерия вероятностной природы наблюдаемого феномена случайности и, как следствие, критерия упомянутых «определенных условий» наблюдения. Поэтому, возможно, что неточность и нечеткость, которые свойственны формулировкам моделей названных объектов, зачастую невозможно охарактеризовать в терминах вероятности. Данная теория (вероятностей) не позволяет ни подтвердить это, ни опровергнуть. С другой стороны, при эмпирическом построении и верификации вероятностной модели сложного, но заведомо стохастического объекта, как правило, возникают принципиальные трудности. Дело в том, что в этом случае требуются большие объемы данных наблюдений. Такие данные, в конечном счете, как правило, оказываются неполными и противоречивыми, в силу того, что объект заметно эволюционирует за время проведения экспериментом, его вероятностные характеристики могут непредсказуемо изменяться. Как результат, их оценки, естественно, оказываются неадекватными. В подобных случаях эмпирическое построение стохастической модели объекта невозможно, если данные наблюдений не позволяют оценить эволюцию его стохастических свойств [56].
Рассмотренные в работе [57] варианты теории возможностей существенно лучше, чем теория вероятностей, приспособлены для моделирования упомянутых выше, в том числе стохастических, объектов, поскольку в то время как при эмпирическом построении вероятностной модели (, P(), Pr) стохастического объекта последняя должна быть неизменна в течение всего времени наблюдений, при эмпирическом построении возможностной модели этого же объекта его вероятностная модель во время наблюдений может произвольно эволюционировать в пределах одного из классов {(, P(), Pr), Pr Pr(e)}, e Pr[0,1] [57]. Это отличие существенно расширяет множество стохастических объектов, математические модели которых могут быть построены эмпирически, расширяет за счет включения стохастических объектов, возможностные модели которых могут быть построены эмпирически, а вероятностные - нет.
Разумеется, не следует думать, что возможностное моделирование непременно ориентировано на исследование недоопределенных стохастических объектов. На самом деле, возможностные модели характерны для нечетких, но не стохастических объектов. Вместе с тем возможностное моделирование оказалось весьма эффективным в областях, характерных для вероятностного моделирования, таких, например, как оптимальные решения, прогнозирование, анализ и интерпретация данных измерительного эксперимента и т. п. [57-60].
В работе [61] Д. Дюбуа рассматривает новое семейство мер неопределенности, которое тесно связано с теорией ошибок, - меры возможности. Меры теории вероятностей полностью отличаются от этих функций множества. Меры возможности в отличие от вероятностных мер с их приспособленностью к обработке противоречивых, но точных результатов испытаний явились естественным средством для построения согласованных, но неточных баз знаний.
При определении функции множества g наиболее слабой аксиомой, которую можно себе представить, обеспечивающей некоторый минимум согласованности, является монотонность по включению
Такие функции множества носили название нечеткие меры. Их предложил Сугено [150] для того, чтобы оценивать неопределенность. В свою очередь, А. Кофман [62] предложил термин «оценка». В работе мы будем принимать название «мера неопределенности».
Из представленной аксиомы монотонности (1.1) непосредственно вытекают следующие неравенства, характеризующие пересечение An В или объединение А и В событий некоторых А и В:
Данные меры называются мерами возможности по Заде [151]. Когда речь идет о неполноте информации, рассматриваются две противоположные точки зрения на одну и ту же реальность – неопределенность и неточность. Д. Дюбуа определил единицу информации четверкой – объект, признак, значение, уверенность. Признаку соответствует функция, которая задает значение (множество значений) объекта или предмета, о котором идет речь в единице информации. Это значение соответствует некоторому предикату (подмножеству универсального множества, связанного с данным признаком). Уверенность – это показатель, определяющий надежность единицы информации. Эти четыре компонента, образующие единицу информации, могут быть составными. Например, множество объектов, множество признаков, n-местный предикат, разные степени уверенности. В том случае, когда информация содержит квантификаторы, возможен ввод переменных, особенно на уровне объектов.
В данном контексте возможно четкое различие понятий «неточность» и «неопределенность». Неточность относят к содержанию информации (составляющая «значение» в четверке единицы информации), а неопределенность – к ее истинности, которая понимается, как соответствие действительности («уверенность»).
Для отражения степени неопределенности информации используют квалификаторы (модальности), такие как «необходимо», «вероятно», «возможно», «правдоподобно» и др. Уже на протяжении двух веков исследовали квалификатор «вероятно». Существуют две различные интерпретации вероятности. 1. Физическая (статистическая), связанная с определением частоты появления события и проведением статистических испытаний. 2. Эпистемологическая, которая относится к субъективному суждению. Еще Аристотель изучал квалификаторы «необходимо» и «возможно». Он подчеркнул их двойственность, т.е если некоторое событие является необходимым, то противоположное ему событие невозможно. Понятия «необходимо» и «возможно» в противоположность понятию «вероятно» часто рассматривали в рамках двузначной логики, в смысле категорий «все» или «ничего».
Полиномиальный расчет оценки живучести информационных структур
Для представления алгоритмов воспользуемся унифицированным языком моделирования UML (англ. Unified Modeling Language). В области разработки программного обеспечения, в частности в объектном моделировании, UML является лидером среди языков графического описания. UML разрабатывался, чтобы иметь возможность определять, визуализировать, проектировать и документировать, как правило, программные системы. UML, являясь языком широкого профиля, представляет собой открытый стандарт. В нем имеется возможность использования графических обозначений для создания абстрактной модели системы, называемой UML-моделью. UML – это не язык программирования, однако помощью разработанных UML-моделей возможно генерировать программный код [82].
Выделим основные преимущества данного языка моделирования [83]: - UML объектно-ориентированный язык, поэтому методы описания результатов проектирования и анализа являются семантически близкими к методам, которые предоставляют современные объектно-ориентированные языки программирования; - UML предоставляет возможность описывать систему практически со всех возможных точек зрения, а также служит для наглядного представления различных аспектов поведения системы; - после достаточно быстрого ознакомления с синтаксисом UML диаграммы сравнительно просты для чтения; - благодаря расширению и возможности ввода собственных графических и текстовых стереотипов UML возможно применять не только в сфере программной инженерии; - UML получил всеобщую известность и динамично развивается.
В частности, рассмотрим диаграммы вариантов использования, деятельности и классов, так как необходимо показать общую структуру взаимодействия всех элементов ПО, рассмотреть алгоритмы, а также представить программную структуру разрабатываемого ПО.
Диаграмма вариантов использования (Use case diagram) или прецедентов – диаграмма, которая отражает отношения между прецедентами и актёрами и является составной частью модели прецедентов, которая позволяет описывать систему на концептуальном уровне. Пользователь может получить конкретный, измеримый и нужный ему результат благодаря прецеденту – возможности моделируемой системы (часть её функциональности). Прецедент соответствует отдельному сервису системы, описывает типичный способ взаимодействия пользователя с системой и определяет один из вариантов её использования. Для спецификации внешних требований к системе, как правило, применяют варианты использования [84].
Еще одним немаловажным типом UML диаграмм является диаграмма деятельности (Activity diagram). Некоторая деятельность на этой диаграмме раскладывается на ее составные части. Деятельность – это спецификация исполняемого поведения, которая представляется как координированное параллельное и последовательное выполнение подчинённых элементов, т.е. – отдельных действий и вложенных видов деятельности. Эти элементы соединяются между собой потоками, идущими от выходов одного узла ко входам другого [85].
Диаграммы деятельности используют при моделировании технологических процессов, последовательных вычислений, параллельных вычислений, бизнес-процессов.
В качестве аналога диаграмм деятельности предлагаются схемы алгоритмов по ГОСТ 19.701-90 [86] и дракон-схемы [87].
Разработка логической модели системы в объектно-ориентированном программировании занимает одно из ключевых мест. Как правило, данная модель представляется в виде диаграммы классов (Class diagram) – статической структурной диаграммы, описывающей структуру системы. Она представляет классы системы, зависимости между ними, их методы и атрибуты [88]. Диаграммы классов можно строить с разных точек зрения [88]: концептуальная – диаграмма классов описывает модель предметной области, здесь представляются лишь классы прикладных объектов; спецификации – диаграмма классов используется при проектировании информационных систем; - реализации – диаграмма классов включает в себя классы, которые используются непосредственно в программном коде при использовании объектно-ориентированных языков программирования.
Использование кластера для вычисления оценки живучести информационных структур
Для расчета была установлена возможность удаления ребра 10%. Результат был получен приблизительно через 11 дней непрерывного расчета. На каждом серверном узле модуль для удобства контроля времени расчета создает лог-файл со следующим содержимым: Time: 904681 sec, Operations: 2773000000 from 2773060536, Ramains: 0.00548602 hours То есть прошедшее время расчета в секундах, количество выполненных операций из общего числа и примерное оставшееся время расчета в часах.
В итоге оценка живучести составила 76,3%, что удовлетворяет заданному порогу живучести в технической документации ОАО «Ростелеком».
В результате разработано ПО оценки живучести ИС, которое включает в себя четыре модуля, обеспечивающих определение возможности разрыва связи ИС, последовательный полиномиальный расчет оценки живучести на одном процессоре и параллельный расчет (GRID, кластер).
Проведен тестовый расчет оценки живучести области ИС ОАО «Ростелеком», опытная эксплуатация на примере топологии ИС НОУ «Региональный центр управления и культуры» г. Тамбова и ИС в энергетике Ржаксинского района Тамбовской области. Также в итоге проведен кластерный расчет оценки живучести целой ИС ОАО «Ростелеком» Тамбовской области, что было ранее невозможно выполнить в рамках одного персонального компьютера.
Результаты экспериментов доказывают, что применение разработанных модели и алгоритмов в реализованном ПО, предназначенных для оценки живучести ИС, позволяет повысить эффективность расчетов при влиянии различных НВ. Таким образом, можно считать, что цель исследования достигнута.
Результаты исследования: Выполнен анализ существующих подходов к оценке живучести ИС. Показано, что существующие модели и методы не могут обеспечить высокий уровень эффективности оценки живучести, так как используют вероятностный подход, который практически невозможно адекватно связать с различными характеристиками ИС, влияющими на живучесть. Предложен полиномиальный подход к оценке живучести, базирующийся на теории возможностей.
Разработана нечеткая логико-лингвистическая модель расчета оценки живучести ИС, которая базируется на теории нечетких множеств и графов. Введены логико-лингвистические переменные, определяющие различные характеристики ИС, которые влияют на ее живучесть (время реакции, пропускная способность, топология, размер, доступность, надежность, среда передачи). Составлена база правил нечеткого вывода. Полученное с помощью алгоритма нечеткого вывода значение возможности разрыва связи используется для полиномиального расчета оценки живучести. Модель позволяет уйти от вероятностного подхода при оценке живучести ИС, который обладает существенным недостатком – сложностью, а зачастую невозможностью определения вероятности разрыва связи ИС.
На основе построенной модели разработаны алгоритмы оценки живучести ИС. На основе комбинаторных формул (свертка Вандермонда) и технологии распределенных вычислений разработан GRID-алгоритм, позволяющий распараллеливать алгоритм расчета полинома Татта. На основе данного алгоритма реализован алгоритм для кластерных вычислений оценки живучести
На основе разработанных модели и алгоритмов проведены различные имитационные исследования, опытные эксплуатации, которые свидетельствуют о достоверности и повышении эффективности расчетов оценки живучести ИС с точки зрения времени в среднем на 10-15% перед алгоритмом на основе вероятностного полиномиального подхода. Представлены результаты эксперимента, показывающие повышение уровня живучести ИС примерно на 35-40%.
В диссертации решена научная задача – разработаны нечеткая логико-лингвистическая модель и алгоритмы расчета оценки живучести ИС, базирующиеся на полиноме Татта, теории графов, теории возможностей, комбинаторики, теории нечетких множеств и технологии распределенных вычислений.
Рекомендации и перспективы дальнейшей разработки темы. Разработанные модель и алгоритмы целесообразно применять в организациях и учреждениях, которые занимаются анализом живучести ИС, а также при разработке систем исследования живучести ИС в различных областях народного хозяйства.
