Содержание к диссертации
Введение
ГЛАВА 1. Иерархические информационные системы и системы видеоконференцсвязи на беспроводной ячеистой сети 13
1.1 Особенности организации беспроводных ячеистых сетей 13
1.2 Исследование подходов к организации информационных систем 16
1.3 Исследование организации и принципов работы иерархических информационных систем
1.4 Вопросы живучести информационных иерархических систем и систем видеоконференцсвязи 26
1.5 Постановка задачи исследования 30
1.6 Выводы по главе 1 35
ГЛАВА 2. Разработка модели информационной иерархической системы, базирующейся на беспроводной ячеистой сети с мобильными узлами 37
2.1 Выбор и обоснование математического аппарата для разработки модели 37
2.2 Структурный уровень модели информационной иерархической системы 39
2.3 Функциональный уровень модели информационной иерархической системы 43
2.4 Модель внешнего воздействия на информационную иерархической системы 47
2.5 Проверка основных свойств модели 50
2.6 Выводы по главе 2 51
ГЛАВА 3. Разработка метода обеспечения функциональной живучести иерархических информационных систем на беспроводных ячеистых сетях 53
3.1 Задача разработки метода обеспечения эффективности функционирования объекта исследования по показателю функциональная живучесть 53
3.2 Обоснование метода обеспечения эффективности функционирования объекта исследования по показателю функциональная живучесть 55
3.3 Описание метода обеспечения эффективности функционирования объекта исследования по показателю функциональная живучесть 60
3.4 Алгоритм функциональной перестройки узла верхнего уровня иерархии информационной системы. 65
3.5 Свойства алгоритма функциональной перестройки узла верхнего уровня иерархии информационной системы. 74
3.4.1 Оценка корректности алгоритма 74
3.4.2 Оценка сложности алгоритма 76
3.4.3 Оценка точности алгоритма 76
3.4.4 Оценка вычислительной устойчивости алгоритма 77
3.6 Алгоритм функциональной перестройки узлов иерархической информационной системы реального времени 78
3.7 Свойства алгоритма функциональной реконфигурации иерархической информационной системы 84
3.7.1 Оценка корректности алгоритма 84
3.7.2 Оценка сложности алгоритма 84
3.7.3 Оценка точности алгоритма 85
3.8 Выводы по главе 3 85
ГЛАВА 4. Результаты имитацинного моделирования процесса функционирования систем видеоконференцсвязи на беспроводной ячеистой сети с мобильными узлами 87
4.1 Особенности имитационной модели 87
4.2 Выбор показателя и критерия оценки эффективности процесса обеспечения функциональной живучести 88
4.3 Настройка имитационной модели 93
4.4 Разработка имитационной модели системы видеоконференцсвязи 96
4.4.1 Построение модели 97
4.5 Результаты экспериментов имитационной модели 102
4.6 Выводы по главе 4 105
Заключение 106
Список использованных источников
- Исследование организации и принципов работы иерархических информационных систем
- Модель внешнего воздействия на информационную иерархической системы
- Описание метода обеспечения эффективности функционирования объекта исследования по показателю функциональная живучесть
- Настройка имитационной модели
Исследование организации и принципов работы иерархических информационных систем
Согласно ГОСТ 34.321-96 [3], под информационной системой (ИС) понимается система, которая организует хранение и манипулирование информацией о предметной области, в то же время в ГОСТ Р 53622-2009 [5], дается определение информационно-вычислительной системы (ИВС): совокупность баз данных и программ, функционирующих на вычислительных средствах как единое целое для решения определенных задач. В работе в дальнейшем под ИС будем понимать исключительно программную часть, которая не включает в себя средства электронно-вычислительной техники (ЭВТ), на которой она функционирует. Именно этим признаком будем отличать ИС от ИВС.
В зависимости от расположения ИС их можно разделить на локальные, которые находятся на одном средстве ЭВТ, и распределенных – в которых компоненты ИС расположены более, чем на одном средстве ЭВТ.
В настоящий момент большинство ИС, в том числе базы данных или подсистемы управления, по способу организации принято классифицировать на централизованные, иерархические и децентрализованные (Рисунок 1.2) Типы информационных систем
В литературе можно встретить классификацию, в которой под децентрализованными системами подразумевают частично распределенные[24], в то же время под распределенными – полностью распределенные.
Децентрализованные информационные системы не смотря на свою сложность, имеют широкое применение. Примером могут выступать распределенные базы данных, grid – системы, децентрализованные пиринговые сети. По степени децентрализации системы с полной децентрализацией так же называются одноранговые, в то же время у систем с частичной децентрализацией сохраняется элементы централизованной или иерархической структурой.
Одним из полных определений иерархии дается в работах Менькова А.В.: иерархия – это упорядоченность компонентов по степени важности (многоступенчатость, служебная лестница). Между уровнями иерархической структуры могут существовать взаимоотношения строгого подчинения компонентов (узлов) нижележащего уровня одному из компонентов вышележащего уровня, т. е. отношения так называемого древовидного порядка. Такие иерархии называют сильными или иерархиями типа «дерево». В дальнейшем в работе речь будет идти только о таком типе иерархических систем.
В работе [50] выделяют основные особенности иерархических систем, к которым можно отнести: - последовательное вертикальное расположение подсистем (вертикальная декомпозиция; - приоритет действий или право вмешательства подсистем верхнего уровня; - зависимость действий подсистем верхнего уровня от фактического исполнения нижними уровнями своих функций; - элементы более высокого уровня с более широкими аспектами поведения системы в целом, следовательно они не могут реагировать на изменения в элементах более низкого уровня; - чем выше уровень управления, тем больше времени необходимо для формирования управляющего воздействия. Классификация иерархий можно разделить на три уровня: 1) уровень описания (абстрагирования); 2) уровень сложности принимаемого решения; 3) организационный уровень.
Среди множества различных типов иерархических информационных систем с клиент-серверной, проект-менеджерной архитектурой наиболее сложным случаем являются системы видеоконференцсвязи (ВКС), так как они обладают наиболее высокими требованиями к пропускной способности каналов связи, вычислительным ресурсам узлов и времени реакции на внутренние и внешние изменения, обусловленные свойствами системы реального времени.
К иерархическим информационным системам можно отнести и большинство систем видеоконференцсвязи (ВКС), которые в последнее время переживают бурное развитие.
Исследование организации и принципов работы иерархических информационных систем Развитие мультимедийных технологий в последнее время обусловило бурное развитие систем видеоконференцсвязи (ВКС), которому способствовало: - увеличение вычислительных мощностей терминального и серверного оборудования; - развитие телекоммуникационных технологий и совершенствованием протоколов связи на различных уровням эталонной модели МВОС; - экономическая выгода от внедрения систем ВКС; - постоянно увеличивающимися требованиями пользователей к системам ВКС; - эффективность от общения по системам ВКС превосходит аналогичные решения голосового общения, например VoIP или через электронную почту e-mail.
В соответствии с озвученными факторами, начиная с 80-х годов прошлого столетия, успешно развиваются системы ВКС, их архитектура, принципы организации. В настоящий момент системы ВКС принципиально разделяются на две группы по типу организации сервера ВКС:
В состав любой системы ВКС входят следующие элементы: - терминал ВКС – любое устройство, поддерживающее передачу аудио и видео: аппаратные, мобильные, сложные системы телеприсутствия; - сервера ВКС – устройства организующие взаимодействие терминалов ВКС и обеспечение обмена аудио и видеоинформации; - инфраструктура системы ВКС – каналы связи, устройства для передачи данных, вспомогательное оборудование.
Модель внешнего воздействия на информационную иерархической системы
На основе данных, приведенных в таблице 1 , сделаем вывод, что для функционального уровня систем видеоконференцсвязи необходимо рассматривать в первую очередь такую характеристику, как адаптация.
В ГОСТ 34.003-90 [2] указано, что живучесть автоматизированной системы - это свойство АС, характеризуемое способностью выполнять установленный объем функций в условиях воздействий внешней среди и отказов компонентов системы в заданных пределах.
Согласно [60], система, обладающая свойством живучести, способна: локализовать отказы функциональных элементов, обусловленных недостаточной их надежностью; - локализовать отказы отдельных функциональных элементов или их совокупности, обусловленных преднамеренными или стихийными вредными воздействиями окружающей среды; - обеспечить постепенную деградацию показателей качества функционирования системы при прогрессирующем накоплении неработоспособных функциональных элементов. Характеристики живучести представлены на рисунке 1.13.
В настоящее время выделяют структурную и функциональную живучесть [31]. При оценке функциональной живучести основное внимание уделяется цели функционирования системы, топология и структурные связи учитываются опосредованно. Детальная классификация живучести хорошо описана в работах [31, 66, 52, 28].
Применительно к системам ВКС живучесть практически не исследована в силу того, что на этапе проектирования таких систем закладываются высокие надежностные показатели (производительные ЭВМ, каналы связи в высокой пропускной способностью, резервирование оборудование).
На функциональный уровень возлагают выполнение определенного объема задач по предоставлению комплекса услуг ВКС, которые могут быть представлены в общем виде следующим образом: F = \JieiFt = {f1,f2 - fn} (1) где п- общее количество функций, выполняемых системой. К функциям системы можно отнести:
Представление задачи Z в виде N-дольного графа координация взаимодействия узлов видеоконференцсвязи; передача потокового видео; передача потокового аудио; передача мгновенных сообщений. Выполнение функции / может быть обеспечено множеством узлов V}, в котором каждый функциональный узел множества Vj принадлежит одному из уровней иерархии, на котором выполняются функция / Пусть kv - уровень иерархии узла vfi Є V/ функционального уровня к Є [0 ...kZaf - 1] , kZaf -1 -нижний уровень иерархии, нумерация уровней начинается с 0.
В графе маршрут от узла нижнего уровня иерархии к узлу верхнего уровня является задачей, которая реализует функцию/в иерархической информационной системе. Обозначим через zaj - а-ую задачу в реализации функции /, Zj— число задач, обеспечивающих выполнение функции / (Рисунок 1.14).
Выполнение zaf на vfi определяется конфигурацией (набором управляющих параметров). Каждая задача обладает надежностными характеристиками, в совокупности определяющие свойство живучести информационной системы.
Тогда задача обеспечения функциональной живучести сводится к структурно-параметрическому синтезу информационной системы, которая бы обладала более высокой функциональной живучестью.
Под функциональной компонентой Фк будем понимать ветвь дерева Gf, включающую себя листок и вершину этого дерева и состоящую из п функциональных узлов vfиn-l функциональных связей ef между ними, где п определяет количество уровней иерархий, участвующих в образовании верви.
Причем функциональная компонента Фк потенциально может выполнять множество функций pn:{l,2,...,n}- P(F) , где P(F) - множество всех подмножеств F. При этом если Рп№) = {fkl,fk2,-,fkj},l к п (2) то функциональная компонента Фк может выполнять функции /fcl,/fc2,..., fk.
Для осуществления ВКС необходимо минимум два пользователя, поэтому предоставления услуги ВКС рассматривается как взаимодействие двух функциональных компонент Ф; и Ф;, при этом если они имеют больше, чем один общий функциональный элемент, то используется функциональный элемент с максимальным уровнем иерархии при условии, что (рп(ї) и (pn(J) достаточно для выполнения соответствующей функции из множества F. Для h пользователей рассматривается соответствующее количество компонент. pt:{l,2,...,n}- P(F) (3) где (pt(k) для Фк представляет собой набор функций, выполняемых функциональной компонентой в момент времени t. При этом если (pt(k) = 0, то функциональная компонента Фк неработоспособна, а если pt(k) срп{ї), то частично работоспособна. Каждой функции ft Є F соответствует характеристика q , которая представляет собой некоторую эффективность выполнения (время выполнения, объем аудитории и т.п.). Тогда можно определить функцию эффективности для системы как Per(fuk, Pt(k)) = cik Эта функция означает, что функциональная компонента Ф , предназначенная для выполнения функций Pt(k) = {fi1,fi2,...,fi] , имеет эффективность выполнения ft Є [filtfi2, ...Jij] равной сік. Примером функций ft функциональной компоненты Фк могут выступать функции MCU-сервера по сшивке аудио и видеопотоков, администрирования, обмена файлами, хранения и распространения информации о присутствии абонентов в сети.
1. Самоорганизующаяся беспроводная вычислительная сеть (БЛВС) с ячеистой топологией (ЯТ) в виде мобильных узлов и связей между ними, описанная графом = (, ) . Для каждого узла из множества определена производительность узла, а так же информационная скорость каналов связи, которые он может образовать;
2. Развернутая на БЛВС иерархическая информационная система на примере системы ВКС, описанная графом = (, ). Для каждого узла известны его функциональные возможности, а так же в разрезе конкретной задачи его уровень иерархии и номер узла, которому подчинен данный узел в рамках выполняемой задачи;
3. Система ВКС описана множеством функций F, множеством задач Z и возможных конфигураций для каждой задачи, которые выполняет система ВКС;
4. На систему ВКС воздействует внешнее воздействие X, вызывающее одиночные функциональные отказы узлов.
Используя научно-обоснованные методы разработать адекватную модель, описывающую иерархическую систему ВКС на БЛВС с ЯТ и мобильными узлами, учитывающую структуру сети, функциональные возможности системы ВКС, внешнее нежелательное воздействие и позволяющую проверить применимость иерархического маршрута от нижнего узла иерархии к верхнему в условиях требуемой суммарной максимальной скорости передачи и наличия свободных вычислительных ресурсов. На основе математической модели разработать метод, включающую в себя комплекс алгоритмов, позволяющий обеспечить живучесть системы ВКС. Разработанную модель и метод реализовать в виде имитационной модели и исследовать результаты имитационного моделирования.
Описание метода обеспечения эффективности функционирования объекта исследования по показателю функциональная живучесть
Матрица функционирования MF , в некоторых источниках может называться матрицей текущей конфигурации [31], описывает выполнение функций узлами и иерархичность системы. Для этого элементу матрицы присваивается номер узла более высокого уровня иерархии. Для узла, выполняющему функции верхнего уровня иерархии задачи zaf элементу присваивается значение равное -1: П, если zaf выполняется на vfi, kv О MF(zafl vfi) = I 0, если zaf не выполняется на vfi (23) (-1, если zaf выполняется на vfi, kVf. = О где vfi Є Vf, Nv - количество функциональных узлов. Такой тип иерархии в литературе называется деревом.
Матрица функционирования описывает структуру иерархических деревьев для задач zaf в текущий момент времени. Предполагается, что функции управления параметрами zaf для каждой ветви возлагаются на верхний узел иерархии.
Для описания существующих возможностей узла, опишем матрицу MFp -матрицу потенциальных возможностей: противном случае Матрица функциональных возможностей описывает, способен ли в текущий момент времени узел выполнять задачу zaj в текущий момент времени t. В зависимости от воздействия внешних или внутренних воздействий элементы матрицы MFp могут менять значения с 1 на 0. Смена значений с 0 на 1 не возможна по причине того, что рассматривается система без восстановления. маршрутизации, которая возвращает множество путей Ец , по которым обеспечивается связь между узлами сети vfi и vfj. При этом каждый путь Ец определяет порядок прохождения трафика по ребрам сети. рт - множество возможных путей доставки трафика, предложенные протоколом маршрутизации. В зависимости от протокола маршрутизации может возвращаться наилучший путь или множество путей.
Применительно к протоколам ad-Hoc с табличной маршрутизацией -выбирается наилучший путь с минимальным числом переходов и скоростью не ниже требуемой. Каждый узел в сети вносит дополнительную задержку, что влияет на качество передаваемой информации, поэтому для работы системы ВКС необходимо минимальное количество узлов из того множество маршрутов в сети, которыми может выполнить доставку протокол маршрутизации.
Запишем выражение, определяющее множество ветвей иерархической структуры функционального уровня, которое может организовать система. Маршруты в графе между узлом верхнего уровня иерархии Vji и нижнего гуубудут определяться:
Следует отметить, что для задания пути в графе могут использоваться различные обозначения, которые состоят из последовательного перечисления только вершин, только ребер или и вершин и ребер. В формуле (25) используется наиболее подробное описание.
Введем понятие относительной единицы производительности вычислительных средств ж и определим требуемую для обеспечения необходимого времени выполнения производительность вычислительных ресурсов для задачи zaj как
Производительность вычислительных ресурсов определяется сочетанием быстродействия процессора, объема оперативной памяти, быстродействием каналов ввода-вывода и т.д. Однако на практике достаточно просто опытным путем определить коэффициенты оj и Ь, сравнив производительность всех задач в каждом узле. [32]
Для каждой задачи на узле каждого уровня вводится матрица табличных данных производительностей MI (zaf, kz , con) для задачи zaf , где con порядковый номер, соответствующий заданной конфигурации (набору управляющих параметров), con = О, con z В зависимости от количества управляющих параметров и их возможных значений количество конфигураций может быть различным. Как правило, список доступных конфигураций определяет оператор на этапе настройки. Таким образом, необходимая производительность узла vt в текущий момент времени будет определяться как: дтреб = /=11 =1в(\МР(гарУП)\) Ml(zaflkVfi,con) (28) где 000 - функция Хевисайда, определенная как
Таким образом получаем множество путей между двумя узлами нижнего и верхнего уровня иерархии, а так же ограничения, накладываемые на узлы. Выбор узла для функциональной реконфигурации будет основан на множестве узлов того же уровня иерархии в рамках одной функции.
Модель внешнего воздействия на информационную иерархической системы В работах по исследованию вопросов живучести существует множество подходов по формированию воздействия на систему. Упрощенная классификация представлена на рисунке (Преднамеренных) (Не преднамеренных")
Применительно к исследуемому объекту рассмотрим оба типа воздействия: внутреннее (непреднамеренное) и внешнее (преднамеренное).
К внутреннему воздействию у данного объекта относится переменная структура и пропускная способность каналов связи, которая обусловлена мобильность узлов. Чем более подвижны узлы, тем больше каналов связи может быть образовано и прекращено, а так же тем более переменной является пропускная способность.
Природа данного воздействия основана на физических свойствах радиоволн, которые затухают с увеличением дальности распространения в среде. В том случае, когда в сети отсутствуют мобильные узлы, данное внешнее воздействие не рассматривается.
Объект исследования представляет собой иерархическую информационную систему, поэтому внешнее преднамеренное должно учитывать особенности функционирования информационной системы и ее строения.
В ряде работ выдвигаются перечень возможных внешних преднамеренных воздействий, при этом, как правило, выдвигаются гипотезы о их природе и характере действий. В работе выдвинем гипотезу, согласно которой ярусы иерархической системы равноуязвимы, а узлы одного яруса имеют равную вероятность внешнего воздействия. Данная гипотеза основана на том, что беспроводные сети являются слабозащищенными, а следовательно, возможно наличие злоумышленника внутри сети. Наиболее худшим случаем в таком случае является приведение информационной системы в неработоспособное состояние. Учитывая особенности иерархических информационных систем типа дерево, необходимо, чтобы каждая ветвь иерархической системы перешла в неработоспособное состояние. Кроме того, если учесть, что в системе возможна функциональная перестройка, необходимо полностью вывести из строя ярус узлов функции системы. Тогда вероятность того, что произойдет функциональный отказ модуля, который решает задачу zaj на узле v будет обратно пропорциональна уровню количеству уровней иерархии в информационной системе К + 1, количеству узлов на уровне, а так же количеству функций, которые выполняет система:
Настройка имитационной модели
Алгоритм называется корректным, если выполняются следующие условия: 1. Алгоритм позволяет получить решение за конечное число элементарных операций 2. Алгоритм является устойчивым по входным данным; 3. Алгоритм обладает вычислительной устойчивостью. Доказательство корректности алгоритма состоит из следующих этапов: 1. Выделяются критические фрагменты. Для алгоритма функциональной перестройки узла верхнего уровня иерархии информационной системы критическими фрагментами будут являться: - блок 15, определяющий условие завершения работы генетического алгоритма решения задачи двумерной упаковки ранца генетическим методом; - блоки 13-15, представляющий собой цикл с постусловием; - блоки 24-31, представляющие собой три вложенных цикла с постусловием.
Определяются постусловия для выделенных фрагменты. Корректность выполнения блока 15 обусловлена условием: Для обеспечения условия (57) в блоке 12 переменной ген присваивается значение 0, после чего в блоке 14 данное значение увеличивается на единицу. Таким образом при первом проходе цикла значение ген = 1, в дальнейшем ген будет только увеличиваться, следовательно ген будет принимать значения на луче [1, ), что не противоречит условию (57).
Применительно к циклу с постусловием в блоке 30 корректным предусловием будет Zf 0 иZfEN, а для цикла с постусловием в блоке 31: п 0 и Zf Є N. Таким образом система может быть записана следующим образом:
Систему U можно описать словестно следующим образом: условием корректности работы алгоритма является использование его в иерархической системе, выполняющей хотя бы одну функцию, реализованной множеством задач, заданной неотрицательным числом. Данная проверка реализована в блоке 2. При этом каждая задача должна иметь минимум два уровня иерархий, что соответствует понятию иерархической системы. 3.4.2 Оценка сложности алгоритма
Задача нахождения наилучшей конфигурации для задачи zaf является NP-полной. В худшем случае сложность ее решения блоке 10 полным перебором определяется как 0(2П), что применимо при малых п, а следовательно и малом времени выполнения части алгоритма. В случае большой размерности п, определяемую как произведение множества задач функций системы на множество узлов и множества возможных конфигураций, реализуется часть алгоритма, в которой используется генетический метод. Сложность его вычислений зависит от размерности исходных данных и количества мутаций. Так как в алгоритме накладывается ограничение по времени, то вычислительная сложность будет обратно пропорциональна вычислительной мощности узла. Оценка минимальной сложности не представляет интереса, так ка для любого эволюционно-генетического алгоритма эта сложность одинакова и равна 0(1).
Дополнительные этапы и ввод/вывод данных не оказывает существенного влияния на алгоритм ]. 3.4.3 Оценка точности алгоритма Оценка точности выполняется в следствии того, что в ходе выполнения алгоритма могут возникать погрешности различного рода, снижающие точность получаемого результата[39]. Общая погрешность вычислений обусловлена: 1. Погрешностью расчетов ЭВМ; 2. Неточность исходных данных; 3. Погрешностью, обусловленной не точностью соотношения реального объекта и его модели, исследуемой в системе. Как следствие, в системе возникают следующие типы погрешностей: - вычислительная погрешность 5В; - неустранимая погрешность 5Н; - погрешность метода 8М. Согласно [16], для удовлетворительной точности алгоритма значение отношения неустранимой погрешности 8Н и 8М погрешности метода должно лежать в интервале [2,10]. Соотношение вычислительной погрешности 8В и погрешности метода 8М должно составлять не менее одного порядка:
Погрешности в исходных данных возникают при определении максимальной скорости между узлами физического уровня и связано это с тем, пакеты с информацией в системе передаются дискретно. Не смотря на это, в соотношении данного окна к среднему времени сеанса ВКС 8Н « 10-6.
Относительно же погрешности метода, которая определяется заданной точностью проверки условий выполнения поиска оптимального решения генетическим методом, что в свою очередь определяется заданной точностью, а именно 5М« 10-5.
Вычислительная погрешность алгоритма определяется архитектурой вычислительного узла. Как правило, точность вычислений в настоящий момент значительно превышает 10-6, следовательно 8М « 10-6.
Данные погрешностей и их отношение в (62) позволяет сформулировать вывод о том, что алгоритм обладает достаточной точностью.
Оценка вычислительной устойчивости алгоритма Физический смысл вычислительной устойчивости сводится к вероятности того, что погрешность результата вычислений не превысит заданное значение при пессимистической оценке числа шагов алгоритма.
Применительно к исследуемому алгоритму, погрешность метода будет линейно расти от количества шагов, что представлено на рисунке Рисунок 3.10 - Аппроксимация линейной функцией зависимости погрешности результатов от количества шагов алгоритма Для оценки вычислительной устойчивости вычисляется косинус угла р, который и характеризует скорость роста погрешности. Отношение разностей ($тах дтіп) и Ohnax птіп) составляет несколько порядков, следовательно косинус угла /? будет стремиться к единице, что говорит о достаточной устойчивости предложенного алгоритма.
Алгоритм функциональной перестройки узлов иерархической информационной системы реального времени. Для того, чтобы в случае внешних и внутренних воздействий на систему они не приводили к нарушению функционирования, предусматривается резерв сетевых, вычислительных и временных резервов, для систем реального времени -временной резерв исключается. Механизмы, которые реализуют компенсационные меры, называют компенсационными механизмами. [19]
Для того, чтобы применить компенсационные механизмы к иерархической системе реального времени, развернутой на ячеистой сети, необходимо предусмотреть следующие моменты
