Содержание к диссертации
Введение
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], а также точка, в которой величина этого потока изменяется. Поэтому узел можно рассматривать как точку ветвления в ИС. Иногда ребра не имеют физического смысла, а используются для того, чтобы направить поток через узлы в нужной логической последовательности или чтобы выполнялись определенные отношения предшествования.
Обычно узлам приписываются номера, чтобы различать их или иметь возможность ими оперировать в процессе анализа. Очевидно, что нумерацию узлов можно осуществлять произвольным образом. Однако исследования могут упроститься, если их занумеровать в определенном порядке. Ребра графа могут быть неориентированными, ориентированными и биориентированными (рисунок
Замена биориентированного ребра двумя противоположно направленными ребрами Ребра графа можно рассматривать как каналы, по которым протекает поток некоторого обобщенного продукта. Чистая величина этого продукта в заданном узле равна разности величин потока, втекающего в узел, и потока, вытекающего из него. Если эта разность положительна, то узел называется источником, а если отрицательна - стоком или конечным узлом графа. Для удобства источником называют каждый узел, из которого поток только вытекает, а стоком - каждый узел, в который поток только втекает.
Например, в ИС, представленной в виде графа на рисунке 1.3, узлы 1 и 2 являются источниками, а узлы 6 и 7 - стоками. Рисунок 1.3 – Пример ИС, представленной в виде графа При сведении практических задач к потоковым задачам нередко бывает полезно разбить ИС на составные части исходя из направления потока. Цепью из узла i в узел j называется последовательность ребер и узлов, в которой конечный узел каждого ребра является начальным узлом следующей (исключая первый и последний узлы последовательности). Следовательно, каждое ребро в такой последовательности ориентировано по направлению от узла i к узлу j. Путь отличается от цепи лишь тем, что в нем одно или несколько ребер могут быть направлены не к узлу j, а к узлу i. На рисунке 1.4 последовательность ребер (1, 3), (3, 5), (5, 3), (3, 6) образует цепь, а последовательность ребер (2, 4), (3, 4), (3, 6) – путь.
ИС является неориентированной, если в соответствующем ей графе ни одно из ребер не имеет ориентации. Именно такие ИС и будут рассматриваться в данной работе для оценки живучести.
ИС называется связной, если для любых двух различных узлов ее графа существует, по крайней мере, один соединяющий их путь или цепь [11].
Для дальнейших исследований потребуется оперирование понятием «подграф» исходного графа. Это граф, содержащий некоторое подмножество вершин и ребер данного графа. В частности, остовным подграфом (остовом) называется подграф, содержащий все узлы исходного графа.
Для машинного представления ИС удобно воспользоваться матричным представлением соответствующих графов с помощью матриц смежности и инцидентности [6]. С точки зрения же человеческого восприятия данный метод имеет существенный недостаток – сложность визуализации ИС с помощью данных матриц.
Очевидно, что ИС, которые графически представлены различным образом, могут соответствовать одним и тем же элементам (частям) некоторой системы. Однако установить эквивалентность двух ИС большой размерности иногда бывает чрезвычайно сложно. В теории графов два графа, между дугами и узлами которых может быть установлено взаимно однозначное соответствие, называют изоморфными [11].
Нередко некоторые общие формы представления ИС позволяют упростить расчет или установить такие свойства исследуемого объекта, благодаря которым отпадает необходимость в выполнении части вычислений или проведении дальнейшего анализа. Количественные характеристики дуг ИС, а также взаимосвязь между ее узлами могут быть представлены с помощью матрицы стоимостей [12] или матрицы расстояний [13]. Кроме того, взаимосвязь между узлами задается либо с помощью матрицы смежности, либо матрицы инцидентности узлы-дуги.
Для простоты изложения вопросов, связанных с матричным представлением [11] ИС, рассмотрим соответствующий ей граф G = (V, Е), в котором узлы из множества V занумерованы числами 1, 2,..., и, а каждой дуге (i, j) из множества Е поставлен в соответствие количественный параметр су, который обычно называют обобщенной стоимостью, или длиной дуги. Матрица стоимостей задается массивом С = [су] (для всех (i, j)eE).
Элементы матрицы С определяют возможности рассматриваемой системы или естественные ограничения, накладываемые на нее. Если G -неориентированная ИС, то су = ср для всех (i, j)eE. В этом случае матрица С является симметричной.
Формирование базы нечетких правил
При формировании базы нечетких правил используются как априорные данные, которые поступают от экспертов, так и данные, получаемые в результате измерений. Учтем и рассмотрим эти два случая в разрабатываемой нечеткой логико-лингвистической модели. В первом случае, если мнения экспертов являются согласованными, то подразумевается, что полнота и непротиворечивость базы нечетких правил обеспечена заранее. Во втором случае для формирования базы правил, которая учитывает всевозможные комбинации значений входных и выходной переменных, необходимо l = l1-l2-...-lm-ly = нечетких правила, где l1,l2,..Jm - число функций принадлежности для задания входных переменных, / - выходной [66]. При возрастании числа входов, количества функций принадлежности для входов и выхода происходит настолько стремительный рост числа правил, что в литературе его иногда называют «проклятием размерности» [77]. Если записать в базу всевозможные правила, то потеряется весь смысл логического вывода. Любую ситуацию будет возможно найти перебором всех правил. Кроме того, логично рассматривать те ситуации, результат которых известен, поэтому первоначально в базу заносятся только такие правила. Воспользуемся следующим подходом [66]. Изначально каждому примеру из выборки ставится в соответствие отдельное правило. Множество таких примеров обучающей выборки задается следующим образом:
Далее каждому обучающему примеру в соответствие ставятся нечеткие множества, к которым у соответствующих значений переменных из данного примера степени принадлежности являются максимальными.
Фрагмент правил нечеткой логико-лингвистической модели имеет следующий вид: П1: ЕСЛИ «время реакции» есть «низкое» И «пропускная способность» есть «высокая» И «размер» есть «малый» И «доступность» есть «отличная» И «надежность» есть «высокая» И «топология» есть «звезда» И «среда передачи» есть «кабель подземный», ТО «возможность разрыва связи» есть «низкая» «время реакции» есть «среднее» И «пропускная способность» есть «средняя» И «размер» есть «средний» И «доступность» есть «хорошая» И «надежность» есть «средняя» И «топология» есть «кольцо» И «среда передачи» есть «кабель надземный», ТО «возможность разрыва связи» есть «средняя» A71 A72 A73 x5
Сформированные таким образом правила и составляют начальную базу нечетких правил. Иногда начальная база может являться избыточной, содержать противоречия (правила с одинаковыми предпосылками, но разными заключениями). В этом случае набор правил необходимо оптимизировать. Это можно сделать на основе эмпирической информации от экспертов, либо путем адаптации обучающей выборки. Одним из простых способов сокращения базы нечетких правил, основанных на экспериментальных данных, является подход, рассмотренный в работе [156]. Все примеры из обучающей выборки (x{fc), xf\ xf\ xf\ xf\ xf\ x7k\ y ) (k=\, ..., К) «предъявляются» каждому правилу. Вводится понятие рейтинга, который определяется для каждого правила: нечеткое множество переменной Xi 7, определенное на Х\..7, с функцией принадлежности // (х17)є[0,1], Bt - нечеткое множество переменной у, определенное на Ху, с функцией принадлежности jus (у) є [0,1],
После вычисления рейтингов из базы удаляются правила с наименьшими значениями rt. Итоговая база нечетких правил формируется из оставшихся правил.
Далее необходимо проверить сформированную базу нечетких правил на полноту и непротиворечивость. Это необходимый элемент исследования, результатом которого является нечеткая система. Нечеткая модель является полной, если с каждым входным состоянием х = принадлежащим области входных значений X, она может связать некоторое выходное состояние у [77]. Полнота нечеткой модели зависит от полноты базы правил. Для определения полноты базы нечетких правил воспользуемся численной полнотой. Численно полной называется база правил, для которой каждое четкое входное состояние (x1,..., xn ) приводит к активизации хотя бы одного правила (его заключения). База правил является непротиворечивой, если она не содержит несовместные правила, т.е. правила, имеющие одинаковые условия, но разные заключения. Если в базе правил возникают такие противоречия, удобно воспользоваться операцией усреднения [77].
Компоненты нечетких продукционных моделей могут реализовываться по-разному. Реализации описанных выше компонентов нечеткой продукционной модели в различных отдельных совокупностях определяют алгоритм нечеткого вывода. Наиболее широко распространены в настоящее время алгоритмы: Мамдани (Mamdani), Цукамото (Tsukamoto), Такаги-Сугэно (Takagi-Sugeno), Ларсена (Larsen) [66]. Общий принцип работы данных алгоритмов представлен на рисунке 2.11.
База правил Приведение кнечеткости (фаззификатор) Приведение кчеткости(дефаззификатор) x - четкая у - четкая величина к Нечеткий j логичвы] еский вод Рисунок 2.11 – Алгоритм нечеткого вывода Введем необходимые определения и понятия из теории возможностей [78, 79]. Пусть имеется множество Г (модельное множество), у є Г - его элементы, Р(Г) - множество всех подмножеств множества Г.
Использование кластера для вычисления оценки живучести информационных структур
При выборе языка программирования весомым критерием стал выбор объектно-ориентированного языка, который поддерживается средами для написания кроссплатформенных приложений, которые будут рассмотрены далее. Поэтому из всего многообразия остались C++ [104], C# и Java. Скриптовые языки Perl, Python и PHP, являющиеся по большей части языками веб-программирования, были исключены из рассмотрения, т.к. имеют недостаточно возможностей для работы с классами и реализовывать графический интерфейс с возможностью визуального рисования ИС достаточно трудоемкий процесс в веб-приложениях.
Язык C# обладает гораздо меньшими возможностями наследования в отличие от C++. Java имеет слабые возможности в области метапрограммирования. Также важным критерием стала возможность работы с массивами, в том числе многомерными динамическими (таблица 4.1).
Многомерные массивы + + +/- +/- +/- +/ Динамические массивы + +/- +/- +/- +/- +/ Как видно из сводной таблицы [105], полноценную работу с динамическими массивами предоставляет только C++.
Рассмотрим мировую популярность языков программирования. На основании анализа данных статистики поисковых запросов в таких системах, как Google, Google Blogs, Yahoo!, Wikipedia, MSN, YouTube, Bing, Amazon и Baidu компания «TIOBE Software» [159] составила список популярности языков программирования по состоянию на март 2014 года (таблица 4.2). Таблица 4.2 – Рейтинг языков программирования по данным TIOBE
Учитывая во внимание вышесказанное, для реализации алгоритмов программы был выбран язык программирования С++, который стал едва ли не стандартом для написания любых достаточно сложных программ. Это чрезвычайно мощный язык, содержащий средства создания эффективных программ практически любого назначения, от низкоуровневых утилит и драйверов до сложных программных комплексов самого различного назначения [106].
Рассмотрим детальнее преимущества и недостатки языков C и C++. Учитывая, что данные языки перекрывают основную долю потребностей человека в программном коде, как следствие можно подчеркнуть наличие наиболее совершенных, постоянно развивающихся компиляторов для этих языков, широкую известность в массах.
Язык C позволяет получить наиболее компактный/быстрый код, уступая только ассемблеру. Наловчившись, можно довольно точно оценивать количествово тактов процессора, требуемых для исполнения той или иной конструкции. 90% переносимость кода на другие системы/компиляторы.
Язык C++ немного уступает C по эффективности программного кода, зато дает гораздо более гибкие возможности, особенно проявляющиеся при написании сложных программ, включающих интерфейс с пользователем, база данных и т.п. Множество языковых лексем дает необычайно интересные возможности написания кода, защищенного от возможных ошибок, например концепция «умных указателей». Одна из наиболее полных реализаций принципов объектно-ориентированного программирования (ООП).
Недостатки языка C: долгий процесс обучения, прежде чем появляется возможность написать что-либо реальное. Необходимость четкого понимания архитектуры процессора, организации памяти, знание API [107] операционной системы и т.п. Велика вероятность ошибки, часто сложно обнаруживаемой, такой как утечка памяти. С++ предоставляет некоторые возможности борьбы с такого рода ошибками, но путем следования достаточно сложным правилам и соглашениям, что только увеличивает время на обучение.
Недостатки языка C++: совместимость с C на уровне синтаксиса привела к огромной путанице в языке. Чтобы определить четко, как интерпретировать ту или иную конструкцию языка, необходимо иметь большой опыт проб и ошибок, обращаться к стандартам и руководству по среде программирования. Некоторый дополнительный относительно языка C объем программного кода в конечной программе для реализации концепции ООП. Но по относительным затратам ресурсов грамотный компилятор C++ конечно с большим преимуществом обойдет иные ООП-языки, отчасти благодаря тому, что совершенствование компиляторов C++ происходит гораздо чаще.
Таким образом, язык C – хорошая замена ассемблеру в случае реализации критичных к эффективности задач, язык C++ – огромная гибкость, наряду с совместимостью со стандартом C, позволяет его применять во всех областях, где применим C, с возможностью дальнейшего развития проекта, написания программы несколькими программистами, возможностью, как было отмечено выше, легко разрабатывать под данный язык среды быстрого программирования, как например Borland Builder, Qt.
Какие-либо другие языки программирования – это либо специфичные вещи, встраиваемые в большие пакеты программ, как средство написания макросов (например, Lisp в Autocad), либо языки, ориентированные на Web, либо языки для обучения программированию (Pascal), либо чисто академические языки, как модели для отработки каких-то идей в области программного искусства.
После выбора языка программирования перейдем к выбору среды разработки программного обеспечения.
В качестве средства разработки программного обеспечения оценки живучести ИС была выбрана библиотека Qt. Qt [108] – это кроссплатформенная библиотека, целью которой является вытеснение нативных API из ваших программ. Сейчас Qt представляет собой огромный объектно-ориентированный комплекс, который в большинстве случаев позволяет обойтись без привлечения посторонних библиотек. В первую очередь Qt является отличным средством создания графического пользовательского интерфейса (GUI). Qt включает в себя основной компонент – дизайнер, который позволяет легко создавать графические интерфейсы для разрабатываемых приложений.
При написании программ на Qt не приходится заботиться о написании файлов сборки для каждой из платформ – это делает сам Qt.
Достаточно написать файл проекта, внести в него все используемые файлы, и файл сборки можно будет создать одним вызовом утилиты qmake [109] (естественно, под управлением целевой платформы). Конечно, иногда этот файл приходится править вручную.
О значимости данной библиотеки говорит хотя бы то, что она используется в таких успешных проектах, как Borland C++ Builder и Opera.
Существует много различных IDE, которые очень эффективно используют при разработке Qt-проектов (Microsoft Visual Studio, IBM Eclipce, QDevelop и др.). Но, пожалуй, самая яркая среда разработки – это Nokia Qt Creator (рисунок 4.1). Данная среда обладает рядом особенностей [110]:
Интегрированная среда разработки Qt Creator В состав Qt Creator [110, 112, 113] входит программа Qt Designer [113] (рисунок 4.2). Прежде всего, этот инструмент предназначен для дизайнеров и принцип его работы отвечает принципу WYSIWYG (What You See Is What You Get, «что видишь, то и получишь»). Он включает в себя множество прототипов приложений, содержащих разные наборы элементов интерфейса (диалоговые окна, меню, панель инструментов, главное окно), которые становится возможным создавать быстро и просто [114].
Рисунок 4.2 – Средство создания интерфейса Qt Designer Важным преимуществом Qt является хорошо продуманный, логичный и стройный набор классов, предоставляющий программисту очень высокий уровень абстракции. Благодаря этому программистам, использующим Qt, приходится писать значительно меньше кода, чем это имеет место при использовании, например, библиотеки классов MFC [115]. Сам же код выглядит стройнее и проще, логичнее и понятнее, чем аналогичный по функциональности код MFC или код, написанный с использованием «родного» для X11 тулкита Xt. Его легче поддерживать и развивать.
Программная реализация алгоритмов
Высокопроизводительный кластер [128] состоит из 9 компьютеров на базе процессоров Intel Pentium 4 3.0 ГГц и 2 Гб ОЗУ, один из которых, является сервером, на котором установлен процессор Intel Pentium 4 3.2 ГГц и 4 Гб ОЗУ.
Технические характеристики главного сервера: процессор - Intel Pentium 4 3200 МГц, ОЗУ - 4096 Мб, жесткий диск - 2 SATA 80 Гб, объединены в RAID 1. Технические характеристики узлов: процессор - Intel Pentium 4 3000 МГц, ОЗУ - 2048 Мб, жесткий диск - 2 SATA 80 Гб, объединены в RAID 1. Операционная система - Scientific Linux (на базе Red Hat Enterprise Linux). Кластерный пакет - MPICH2.
Для работы на кластере был разработан специальный отдельный модуль, базирующийся на ранее разработанном GRID-модуле. Взаимодействие модулей между собой осуществляется с помощью интегрированного программного API интерфейса MPI, работа которого была рассмотрена в главе 3. Основными используемыми функциями MPI стали [129]:
То есть прошедшее время расчета в секундах, количество выполненных операций из общего числа и примерное оставшееся время расчета в часах.
В итоге оценка живучести составила 76,3%, что удовлетворяет заданному порогу живучести в технической документации ОАО «Ростелеком».
В результате разработано ПО оценки живучести ИС, которое включает в себя четыре модуля, обеспечивающих определение возможности разрыва связи ИС, последовательный полиномиальный расчет оценки живучести на одном процессоре и параллельный расчет (GRID, кластер).
Проведен тестовый расчет оценки живучести области ИС ОАО «Ростелеком», опытная эксплуатация на примере топологии ИС НОУ «Региональный центр управления и культуры» г. Тамбова и ИС в энергетике Ржаксинского района Тамбовской области. Также в итоге проведен кластерный расчет оценки живучести целой ИС ОАО «Ростелеком» Тамбовской области, что было ранее невозможно выполнить в рамках одного персонального компьютера.
Результаты экспериментов доказывают, что применение разработанных модели и алгоритмов в реализованном ПО, предназначенных для оценки живучести ИС, позволяет повысить эффективность расчетов при влиянии различных НВ. Таким образом, можно считать, что цель исследования достигнута.
1. Выполнен анализ существующих подходов к оценке живучести ИС. Показано, что существующие модели и методы не могут обеспечить высокий уровень эффективности оценки живучести, так как используют вероятностный подход, который практически невозможно адекватно связать с различными характеристиками ИС, влияющими на живучесть. Предложен полиномиальный подход к оценке живучести, базирующийся на теории возможностей.
2. Разработана нечеткая логико-лингвистическая модель расчета оценки живучести ИС, которая базируется на теории нечетких множеств и графов. Введены логико-лингвистические переменные, определяющие различные характеристики ИС, которые влияют на ее живучесть (время реакции, пропускная способность, топология, размер, доступность, надежность, среда передачи). Составлена база правил нечеткого вывода. Полученное с помощью алгоритма нечеткого вывода значение возможности разрыва связи используется для полиномиального расчета оценки живучести. Модель позволяет уйти от вероятностного подхода при оценке живучести ИС, который обладает существенным недостатком – сложностью, а зачастую невозможностью определения вероятности разрыва связи ИС.
3. На основе построенной модели разработаны алгоритмы оценки живучести ИС. На основе комбинаторных формул (свертка Вандермонда) и технологии распределенных вычислений разработан GRID-алгоритм, позволяющий распараллеливать алгоритм расчета полинома Татта. На основе данного алгоритма реализован алгоритм для кластерных вычислений оценки живучести
4. На основе разработанных модели и алгоритмов проведены различные имитационные исследования, опытные эксплуатации, которые свидетельствуют о достоверности и повышении эффективности расчетов оценки живучести ИС с точки зрения времени в среднем на 10-15% перед алгоритмом на основе вероятностного полиномиального подхода. Представлены результаты эксперимента, показывающие повышение уровня живучести ИС примерно на 35-40%.
В диссертации решена научная задача – разработаны нечеткая логико-лингвистическая модель и алгоритмы расчета оценки живучести ИС, базирующиеся на полиноме Татта, теории графов, теории возможностей, комбинаторики, теории нечетких множеств и технологии распределенных вычислений. Рекомендации и перспективы дальнейшей разработки темы. Разработанные модель и алгоритмы целесообразно применять в организациях и учреждениях, которые занимаются анализом живучести ИС, а также при разработке систем исследования живучести ИС в различных областях народного хозяйства.
