автореферат диссертации по документальной информации, 05.25.05, диссертация на тему:Аналитические и процедурные модели распределения ресурсов в сетевых информационных системах с различной структурой

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

Ауад Максим Сами

АНАЛИТИЧЕСКИЕ И ПРОЦЕДУРНЫЕ МОДЕЛИ

РАСПРЕДЕЛЕНИЯ РЕСУРСОВ В СЕТЕВЫХ ИНФОРМАЦИОННЫХ СИСТЕМАХ С РАЗЛИЧНОЙ СТРУКТУРОЙ

Специальность 05.25.05 «Информационные системы и процессы»

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

1I НДП 2014

Тамбов-2014

005548597

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

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

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

Официальные оппоненты: Дубровин Анатолий Станиславович,

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

Панкин Олег Викторович,

доктор технических наук, доцент, Воронежский институт правительственной связи (филиал) Академии Федеральной службы охраны Российской Федерации, начальник кафедры общепрофессиональных дисциплин

Ведущая организация ФГБОУ ВПО «Воронежский государст-

венный технический университет»

Защита состоится 25 июня 2014 г. в 13 часов на заседании диссертационного совета Д 212.260.05 в ФГБОУ ВПО «ТГТУ» по адресу: г. Тамбов, ул. Советская, д. 106, Большой актовый зал.

С диссертацией можно ознакомиться в библиотеке и на сайте ФГБОУ ВПО «ТГТУ» http://tstu.ru.

Автореферат разослан «2-^» _ О 2014 г.

__ 6ц

диссертационного совета Г / /и Селиванова Зоя Михайловна

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

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

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

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

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

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

Степень разработанности темы исследования. Вопросам оценки качества функционирования сложных систем, к которым относятся СИС, посвящены работы В. Ф. Крапивина, И. А. Рябинина, Б. С. Флейшмана, Ю. М. Парфенова, Д. В. Ландэ, А. Г. Додонова, И. Ю. Стекольникова, Ю. Ю. Громова, М. X. Cheng, Y. Li, D.-Z. Du и др.

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

Анализ структур СИС, а также определение методов ее синтеза рассмотрены в работах Р. Бесслера, А. Дойча, Г. Т. Артамонова, В. Д. Тюрина. В работах В. Г. Лазарева, Г. Г. Савина, Г. Ф. Янбых, Б. А. Столярова, В. С. Лукьянова, L. R. Bahl и D. Т. Tang, A. W. Neebe и М. R. Rao, Н. G. Dysart и N. D. Georganas представлены эвристические методы синтеза структуры систем на основе заданного местоположения узлов.

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

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

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

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

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

Для достижения поставленной цели были решены следующие задачи:

1. Анализ существующих подходов к распределению ресурсов в СИС при ее синтезе и оценке качества функционирования СИС.

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

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

4. Проведение вычислительных экспериментов на разработанных моделях.

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

Научпая повпзна:

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

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

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

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

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

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

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

1. Аналитическая модель распределения ресурсов в СИС со структурой «звезда-дерево», при которых стоимость ее синтеза будет минимальна.

2. Процедурная модель нахождения допустимого решения задачи Лагранжа в аналитической модели распределения ресурсов в СИС со структурой «звезда—дерево».

3. Аналитическая модель распределения ресурсов в СИС со структурой «дерево-дерево», при которой стоимость ее синтеза будет минимальна.

4. Процедурная модель нахождения допустимого решения задачи Лагранжа в аналитической модели распределения ресурсов в СИС со структурой «дерево-дерево».

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

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

Основные результаты работы докладывались и обсуждались на Международной научно-практической конференции «Техника и безопасность объектов уголовно-исполнительной системы-2011» (Воронеж, 2011); Международной научно-технической конференции «Современные информационные технологии» (Пенза, 2014); XIV Международной научной конференции «Информатика: проблемы, методология, технологии» (Воронеж, 2014); а также на семинарах кафедры «Информационные системы и защита информации» ФГБОУ ВПО «ТГТУ».

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

Публикации. По теме диссертации опубликовано 19 работ, в том числе 5 статей в изданиях, рекомендованных ВАК РФ.

Структура работы. Диссертация, общий объем которой составляет 114 страниц, состоит из введения, четырех глав, заключения, списка использованной научной литературы, включающего 155 наименований научных трудов на русском и иностранных языках, и приложения. Диссертация содержит 16 иллюстраций и 18 таблиц.

Работа соответствует Паспорту специальности 05.25.05 «Информационные системы и процессы», п. 1 «Методы и модели описания, оценки, оптимизации информационных процессов и информационных ресурсов, а также средства анализа и выявления закономерностей в информационных потоках».

Работа выполнена в рамках приоритетных научных направлений Программы стратегического развития Института автоматики и информационных технологий ФГБОУ ВПО «ТГТУ» и исследований научно-образовательного центра моделирования и управления информационными процессами и системами и информационной безопасности в рамках научных школ ФГБОУ ВПО «ТГТУ» и ФГБУН «Институт радиотехники и электроники им. В. А. Котельникова» РАН. 4

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

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

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

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

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

Классическая задача о расположении узла концентрации была изучена L. R. Bahl и D. Т. Tang, A.W. Neebe и М. R. Rao, Н. G. Dysart и N. D. Georganas, P. McGregor и D. Shen, а также G. M. Schneider и M. N. Zastrow, которые представили различные алгоритмы для решения этой задачи.

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

Вторая глава «Аналитические модели распределения ресурсов в СИС с различной структурой» посвящена разработке аналитических

моделей распределения ресурсов в СИС в зависимости от ее информационной структуры, которая представляется одним из следующих типов: «звезда-дерево», «дерево—дерево».

Аналитическая модель распределения ресурсов в СИС со структурой «звезда-дерево», при которых стоимость ее синтеза будет минимальна, представлена следующим образом:

У У ,, С,,Х„ +У У С,гаУ,от —>шш (1)

при ограничениях

/ик < с1Х]к, V/ е I; V/ е IV, У к е Ж и С; (3)

У/,*е/; (4)

Ц^/ик * V/" е I, У к е Р и С; (5)

Е^Л^Е^Й^-У/"^; (6) й, V/, к е /, & е /;

" = О, V* и С, / е /; (7) - а, V/ е /, к = С;

VI б Л VI е/; (8)

те Я

(9)

Ху е {0,1}, V/ е еГ и С; Гуи е {0,1}, V/ еР, те Я; (10)

V/e/, уеЖ, Ле^ис, (11)

где Р - множество индексов, характеризующее расположение узлов, концентрирующих информационные потоки в СИС; I — множество индексов, характеризующее расположение конечных узлов СИС; Ж — множество индексов, где Ш = 1\]Р \С- центральный узел СИС; с1-трафик в каждом конечном узле; Я — дискретное множество уровней мощностей, доступных для каждого узла концентрации; QJm - мощность каждого узла концентрации информационного потока на узле ] на уровне т; К - мощность соединения конечных узлов друг с другом; Су - стоимость соединения узла /'

с узлом }\ Скс = 0 (Ук е Р) — стоимость соединения узла концентрации информационного потока с центральным узлом; С]т — стоимость открытия узла концентрации информационного потока _/ емкости т и соединения его с центральным узлом; /,]к - поток, идущий из конечного узла /

по связи (/', к), г е /,_/ е ЖД е Ж и С ; Ху - определяет наличие связи между

узлом г и у, ее значения определяются следующим образом: Х,у = 1, если

между узлами / и у есть связь, / е И7, / е ^ и Хц = 0 в противном случае;

У-т - служит для обозначения активности узла у концентрации, 7ут = 1,

если узел концентрации у активен и соединен с центральным узлом С, и Уу,,, = 0 в противном случае.

Критерием оптимизации (1) является функция стоимости соединения конечных узлов СИС друг с другом или с узлом, концентрирующим информационные потоки, а также с центральным узлом СИС. Ограничение (2) выделяет только одну исходящую дугу для каждого узла. Набор ограничений (3) подтверждает, что поток между двумя узлами существует -имеется в наличии связь. Выражения (4), (5) и (6) описывают ограничения на мощность информационных потоков в СИС между узлами. Сохранение информационного потока обеспечивает ограничение (7). Ограничение (9) подтверждает, что узел, концентрирующий информационные потоки, открыт, если для него существуют исходящие дуги.

Используя неотрицательные множители а\, сь, а3, а4, а5, а в, преобразуем задачу (1) - (11) к функции Лагранжа вида (12)

(12)

X

Задача (12) разбита на три подзадачи:

Е.С/Х«,« - Д/т - V - Аь

Не!

2' ССЧХЧ

.;< /."л цл ¡к

лКХ л +

(14)

3) для каждого I е /:

(15)

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

при ограничениях:

/ик < ах}к, V/ е /, У/ е Г, Ук е IVI) С; (18)

"£ы1/ик<(К-с1)ХА,у,ке1-, (19)

^ш1цк<КХ}к, У/'ЕДУ^еРиС; (20)

а, V/, & е /, Лег;

Е/еЖИ~ Е /с(С ^

0, V£ * /, к е ^и с, / е (22)

- с/, V/ е /, к = С\ Х, * сЕ^Л- Vi е Р, Vi е /; (23)

Z^PUcZ^^V^P; (24)

^•е{0,1}, VieW,eW{JC; YJkme{0,1}, V/eP, iePUC, m&R; (25) fijk > 0, V/ e /, j e fF, к e rUC. (26)

Задача Лагранжа для (16) - (26) принимает следующий вид:

+ Х/6/Z*6itис а2. vk Wm ~ dX]k > +

+ Х/с/ SA-cPUC У* iX/с/ fm - KXjk}+

+ ZyeP ePUC "5, jk {Z;e/ U ~ KX.ik }+ + SysP Sie/ YJk (Sie/ Л* ~ Smeß YJkm )+ + X/ep ij {Xij ~ XisPUC Smc/i ^ )+

Данная задача Лагранжа (27) разбита на три подзадачи.

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

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

На рисунке 1 представлен общий вид процедурной модели распределения ресурсов в СИС для каждого типа информационной структуры.

С

Рис. 1. Общий вид процедурной модели распределения ресурсов в СИС с различной структурой

При решении аналитической модели распределения ресурсов в СИС со структурой «звезда—дерево» в блоке 4 определяются решения подзадач (13), (14), (15). Процедура решения подзадачи (13) представлена на рис. 2. Выполнение данной процедуры определяет параметры вектора V . Оптимальным решением подзадачи (14) является ориентированное дерево минимального охвата с корнем в центральном узле С, которое представлено вектором X . Решением подзадачи (15) является кратчайший путь между определенным требуемым узлом / и центральным узлом С.

Для решения задачи Лагранжа использован метод субградиентной оптимизации для получения нижних границ оптимального значения.

На каждой итерации решения задачи Лагранжа применяется процедурная модель нахождения допустимого решения задачи Лагранжа

Рис. 2. Процедура решения подзадачи (14)

в аналитической модели распределения ресурсов СИС со структурой «звезда—дерево», которая представленй1а на рис. 3, в которой использованы следующие обозначения: Р{1) — конечная точка направленной связи из узла /, т.е. = 1; В,к —функция стоимости, определенная как дополнительная стоимость удаления связи (г, р(1)) и добавления связи (г, к), если дополнение к связи (г, к) приводит к циклу или нарушению мощности, тогда 0/к = со.

Ф

0 = и\]еР,теЯ,Гм=Ц

и = р-о ~г

к' = а^тт {Д4|, V; е &(./)}

*е/иоис

к" = агд тт {1, V; е }

хщп = о, хя.=\

| -

Обновить множество Т

I

Обновить множество V

1Г

Т= {(/■,«)\] е О, те Л, = 1, ЗД > &„}

6

е /, I 1 > К}

и' =а^тт{|5/(н)|: |5У(»)| > К, р(и) е Р\

Иб/

(г",<7*)= а^тт {Ог,} (е/иоис

- I

-У . . = О, Л". . = 1

Г ,<Г ) Л <,

[ конец |

Рис. 3. Процедурная модель нахождения допустимого решения задачи Лагранжа в аналитической модели распределения ресурсов в СИС со структурой «звезда-дерево»

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

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

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

Для проверки адекватности разработанных моделей была выполнена программная реализация разработанных в главах 2 и 3 аналитических и процедурных моделей, структура которой приведена на рис. 4. Посредством блоков 1.1 - 1.3 осуществляется взаимодействие с пользователем программного обеспечения, блок 2 реализует процедурную модель, приведенную на рис. 1. База данных необходима для хранения информации о параметрах использующихся моделей, промежуточных и окончательных результатах их работы.

Пользователь

решение

Гг

Интерфейс ввода информации об информационной структуре

Интерфейс ввода параметров узлов СИС

Рис. 4. Структура программного обеспечения распределения ресурсов в СИС с различной структурой

Функционал программного обеспечения представлен на диаграмме вариантов использования (рис. 5). Статическая структура классов программного обеспечения и их отношения представлены на диаграмме классов (рис. 6).

Рис. 5. Диаграмма вариантов использования программного обеспечения распределения ресурсов в СИС с различной структурой

Рис. 6. Диаграмма классов программного обеспечения распределения ресурсов в СИС с различной структурой

С использованием разработанного программного обеспечения проведены вычислительные эксперименты. Так, например, при решении аналитической модели распределения ресурсов в СИС со структурой «звезда-дерево», разработанная процедурная модель позволяет получить результаты с отклонением в пределах 7 — 14% от нижней границы. При проведении экспериментов координаты узлов были сгенерированы с нормальным распределением в квадрате размером 100x100 с количеством конечных узлов, равным 100, и 15 узлами концентрации информационных потоков в СИС. Время, затраченное на решение, равняется 2,5 часам. Несмотря на то, что это значение времени выглядит большим, следует помнить о сложности решаемой задачи.

Вычислительный эксперимент при решении аналитической модели распределения ресурсов в СИС со структурой «дерево-дерево» с много-пунктовыми линиями передачи информации состоял из генерации четырех случаев данной задачи с нормальным распределением координат узлов в квадрате размером 100x100. Полученные результаты указывают на то, что разработанный подход дает отклонение 8 — 15% от нижней границы, что является достаточно допустимым отклонением в условиях сложности данной задачи. Отклонение уменьшается вследствие уменьшения мощности соединения. Когда мощность соединения принимается равной 1, задача сводится к аналитической модели распределения ресурсов в СИС со структурой «звезда-дерево», решение которой существенно проще. Эффективность разработанных процедур для более простых случаев существенно возрастает, предоставляя отклонение от нижней границы от 3 до 5,5%.

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

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

2. Разработана процедурная модель распределения ресурсов в СИС со структурой «звезда-дерево», при которых стоимость ее синтеза будет минимальна.

3. Разработана процедурная модель нахождения допустимого решения задачи Лагранжа в аналитической модели распределения ресурсов в СИС со структурой «звезда-дерево», отличающаяся применением эвристического подхода, позволившая получить результаты с отклонением в пределах 7 - 14% от нижней границы.

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

5. Разработана процедурная модель распределения ресурсов в СИС со структурой «дерево-дерево» с многопунктовыми линиями передачи информации, при которых стоимость ее синтеза будет минимальна.

6. Разработана процедурная модель нахождения допустимого решения задачи Лагранжа в аналитической модели распределения ресурсов в СИС со структурой «дерево-дерево» с многопунктовыми информационными потоками, отличающаяся применением низкоскоростных линий передачи информации при взаимосвязи конечных узлов СИС и эвристического подхода, позволившая получить результаты с отклонением в пределах 8 — 15% от нижней границы.

При решении задач распределения ресурсов в СИС с различной структурой в научно-исследовательских и опытно-конструкторских работах, проводимых в ООО «Медтехника» и 000«К0НУС-ИТ», стоимость синтеза СИ С уменьшена на 7 — 15%, а время получения результатов сокращено на 30%.

В диссертации решена научная задача — построены аналитические и процедурные модели: определения параметров СИС со структурами «звезда—дерево» и «дерево—дерево», при которых стоимость ее синтеза будет минимальна, что позволяет сделать вывод о выполнении цели исследования.

Рекомендации и перспективы дальнейшей разработки темы.

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

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

1. Ауад, М. Процедура выбора и распределения ресурсов в информационных системах / М. Ауад, Ю. Ю. Громов, Ю. В. Минин, М. В. При-ходько // Приборы и системы. Управление, контроль, диагностика. — 2014. — № 1.-С. 18-26.

2. Ауад, М. Оптимизационные задачи выбора и распределения ресурсов в информационных системах / М. Ауад, В. В. Борщ, А. В. Лаза-ренко, Ю. В. Минин // Приборы и системы. Управление, контроль, диагностика.-2014.-№ 1. — С. 43 — 46.

3. Ауад, М. Модель распределения ресурсов в сетевых информационных структурах / М. Ауад, Ю. В. Минин, Ю. Ю. Громов // Вестник Воронежского института МВД России. —2013. — № 4. — С. 215 —220.

4. Подход к формированию набора информационных ресурсов образовательного назначения на основе нечетких сетей Петри / О. Г. Иванова, Т. О. Авдеева, Д. ЛыонгХак, М. Ауад, М. Аль-Балуши // Приборы и системы. Управление, контроль, диагностика. -2012. -№ 3 - С. 55 - 58.

5. Интеллектуальная система обучения с адаптивным построением курса обучения на ЬМБ МоосПе / Т. О. Авдеева, Д. ЛыонгХак, М. Ауад, М. Аль-Балуши // Приборы и системы. Управление, контроль, диагностика. - 2012.-№ 3 - С. 71 - 74

Статьи в рецензируемых журналах и материалах научно-практических конференций:

6. Задача поиска оптимальных параметров сетевой информационной структуры типа «звезда-дерево» / М. Ауад., А. А Долгов, М. А. Хоро-хорин, А. Ю. Гречушкина, Ю. В. Минин // Информатика: проблемы, методология, технологии: материалы XIV Международной конференции (6-8 февраля 2014 года): в 3-х т. - Воронеж: Издательско-полиграфи-ческий центр Воронежского государственного университета, 2014. — Т. 1. — С. 52-56.

7. Задача поиска параметров структуры типа «звезда—дерево» сетевой информационной системы при условии применения идентичных концентраторов / М. Ауад, С. В. Зайцев, С. А. Копылов, А. Ю. Гречушкина, Ю. В. Минин // Современные информационные технологии : тр. Между-нар. науч.-техн. конф. — Пенза: Пензенский государственный технологический университет, 2014. - Вып. 19. - С. 7 - 12.

8. Определение оптимальных параметров структуры типа «звезда-дерево» сетевой информационной системы / М. Ауад, С. В. Зайцев, Д. С. Соловьев, А. Ю. Гречушкина, Ю. В. Минин // Современные информационные технологии : тр. Междунар. науч.-техн. конф. — Пенза : Пензенский государственный технологический университет, 2014. — Вып. 19. -С. 12-16.

9. Определение оптимального расположения элементов в локальных сетевых информационных системах / М. Ауад, Е. В. Костерин, А. Ю. Гречушкина, Д. В. Поляков, Ю. В. Минин // Современные информационные технологии : тр. Междунар. науч.-техн. конф. - Пенза : Пензенский государственный технологический университет, 2014. - Вып. 19. -С. 16- 19.

10. Определение параметров структуры сетевой информационной системы с многопунктовыми линиями связи / М. Ауад, Н. А. Овчинников, А. С. Моисеев, А. Ю. Гречушкина, Ю. В. Минин // Современные информационные технологии : тр. Междунар. науч.-техн. конф. — Пенза : Пензенский государственный технологический университет, 2014. — Вып. 19. — С. 19-24.

11. Применение лингвистических переменных в задаче оценки рисков в информационных системах / С. В. Проскуряков, М. Аль-Балуши, Д. ЛыонгХак, М. Ауад // Методы и модели автоматизации и поддержки управленческих решений. Сборник научных трудов МАДИ. - 2011. -С. 48-56.

12. Использование нечетких множеств в задаче оценки сетевых информационных систем / С. В. Проскуряков, М. Аль-Балуши, Д. ЛыонгХак, М. Ауад // Методы и модели автоматизации и поддержки управленческих решений. Сборник научных трудов МАДИ. - 2011. - С. 56 - 63.

13. К вопросу о метриках в задачах оценки уязвимости сетевых информационных систем / С. В. Проскуряков, М. Аль-Балуши, Д. ЛыонгХак, М. Ауад // Методы и модели автоматизации и поддержки управленческих решений. Сборник научных трудов МАДИ. - 2011. - С. 63 - 72.

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

15. Управление информационными процессами при нечеткой га-формации / Ю. В. Минин, А. Ю. Громова, В. В. Родин, Д. ЛыонгХак, М. Ауад // Вестник Воронежского института ФСИН России. — Воронеж : ООО ИПЦ «Научная книга». - 2011. - № 1. - С. 71 - 75.

16. Управление информационными процессами в системах с использованием качественной информации / Ю. В. Минин, А. Ю. Громова,

B. В. Родин, Д. ЛыонгХак, М. Ауад // Вестник Воронежского института ФСИН России. - Воронеж : ООО ИПЦ «Научная книга». - 2011. - № 2 -

C. 64-68.

17. Интеллектуальная информационная система оценки устойчивости функционирования сетевых информационных систем / Н. Аль-Тамими, М. П. Аль-Балуши, М. Ауад, Д. ЛыонгХак, Ю. В. Минин // Техника и безопасность объектов уголовно-исполнительной системы-2011 : сб. матер. Междунар. науч.-практ. конф.: в 2 т. / ФКОУ ВПО «Воронежский институт ФСИН России». - Воронеж: ИПЦ «Научная книга». -Т. 1.-2011.-С. 382-388.

18. Некоторые вопросы интеллектуальной информационной системы оценки функционирования сетевых информационных систем / Н. Аль-Тамими, М. П. Аль-Балуши, М. Ауад, Д. ЛыонгХак, Ю. В. Минин // Техника и безопасность объектов уголовно-исполнительной системы-2011 : сб. матер. Междунар. науч.-практ. конф.: в 2 т. / ФКОУ ВПО «Воронежский институт ФСИН России». - Воронеж: ИПЦ «Научная книга». -Т. 1.-2011.-С. 388-394.

19. Оценка надежности средств парирования внешних воздействий / Н. Аль-Тамими, М. П. Аль-Балуши, М. Ауад, Д. ЛыонгХак, Ю. В. Минин // Техника и безопасность объектов уголовно-исполнительной системы-2011 : сб. матер. Междунар. науч.-практ. конф. : в 2 т. / ФКОУ ВПО «Воронежский институт ФСИН России». - Воронеж: ИПЦ «Научная книга».-Т. 1.-2011.-С. 394-399.

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

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

\

Министерство образования и науки Российской Федерации Федеральное государственное образовательное учреждение

высшего профессионального образования «Тамбовский государственный технический университет»

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

04201459712

АУАД МАКСИМ САМИ

АНАЛИТИЧЕСКИЕ И ПРОЦЕДУРНЫЕ МОДЕЛИ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ В СЕТЕВЫХ ИНФОРМАЦИОННЫХ СИСТЕМАХ С РАЗЛИЧНОЙ СТРУКТУРОЙ

Специальность 05.25.05 - Информационные системы и процессы

ДИССЕРТАЦИЯ на соискание учёной степени кандидата технических наук

Научный руководитель: доктор технических наук, профессор Ю.Ю. Громов

ТАМБОВ-2014

СОДЕРЖАНИЕ

ВВЕДЕНИЕ............................................................................... 4

1 Анализ современного состояния и вопросов распределения ресурсов в сетевой информационной системе при ее синтезе................................ 12

1.1 Современное состояние вопроса распределения ресурсов в сложных системах.................................................................................... 12

1.2 Современное состояние и вопросы распределения ресурсов в СИС...... 15

1.3 Применение информационных систем для решения задач распределения ресурсов в СИС....................................................... 20

1.4 Выводы по главе 1 .................................................................. 27

2 Аналитические модели распределения ресурсов сетевых информационных систем с различной структурой............................... 28

2.1 Аналитические модели распределения ресурсов в СИС со структурой «звезда-дерево»........................................................................... 28

2.1.1 Аналитическая модель распределения ресурсов в СИС со структурой «звезда-дерево» при условии идентичности параметров узлов концентрации информационных потоков.......................................... 28

2.1.2 Аналитическая модель распределения ресурсов в СИС со структурой «звезда-дерево» (общий случай)...................................................... 32

2.2 Аналитическая модель распределения ресурсов в СИС со структурой «дерево».................................................................................... 36

2.3 Аналитическая модель распределения ресурсов в СИС со структурой «дерево - дерево»........................................................................ 39

2.4 Выводы по главе 2.................................................................. 43

3 Процедурные модели распределения ресурсов в сетевых

информационных системах с различной структурой............................. 45

3.1 Процедурные модели распределения ресурсов в СИС со структурой

«звезда-дерево»................................................................................................................................................45

3.1.1 Процедурная модель распределения ресурсов в СИС со структурой

«звезда-дерево» при условии идентичности параметров узлов

концентрации информационных потоков.......................................... 45

3.1.2 Процедурная модель распределения ресурсов в СИС со структурой «звезда-дерево» (общий случай)...................................................... 51

3.2 Процедурная модель распределения ресурсов в СИС со структурой «дерево».................................................................................... '57

3.3 Процедурная модель распределения ресурсов в СИС со структурой «дерево-дерево».......................................................................... 61

3.4 Выводы по главе 3.................................................................. 68

4. Вычислительный эксперимент на разработанных моделях................................70

4.1 Описание моделей и схем информационной системы распределения ресурсов в СИС с различной структурой........................................... 70

4.2 Вычислительный эксперимент распределения ресурсов в СИС со структурой «звезда-дерево»........................................................... 74

4.2.1 Вычислительный эксперимент распределения ресурсов в СИС со структурой «звезда-дерево» при условии идентичности параметров узлов концентрации информационных потоков.......................................... 74

4.2.2 Вычислительный эксперимент распределения ресурсов в СИС со структурой «звезда-дерево» (общий случай)....................................... 80

4.3 Вычислительный эксперимент распределения ресурсов в СИС со структурой «дерево»..................................................................... 85

4.4 Вычислительный эксперимент распределения ресурсов в СИС со структурой «дерево-дерево»........................................................... 89

4.5 Выводы по главе 4.................................................................. 93

ЗАКЛЮЧЕНИЕ........................................................................... 94

СПИСОК ИСПОЛЬЗОВАНЫХ ИСТОЧНИКОВ................................. 97

Приложение А. Акты об использовании результатов исследования.......... 109

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

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

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

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

Применение аппарата математического программирования для распределения ресурсов в СИС является трудно вычисляемой задачей, т.к.

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

Степень разработанности темы исследования. Вопросам оценки качества функционирования сложных систем, к которым относятся СИС, посвящены работы В.Ф. Крапивина, И.А. Рябинина, Б.С. Флейшмана, Ю.М. Парфенова, Д.В. Ландэ, А.Г. Додонова, И.Ю. Стекольникова, Ю.Ю. Громова, М.Х. Cheng, Y. Li, D.-Z. Du и др.

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

Анализ структур СИС, а также определение методов ее синтеза рассмотрены в работах Р. Бесслера, А. Дойча, Г.Т. Артамонова, В.Д. Тюрина. В работах В.Г. Лазарева, Г.Г. Савина, Г.Ф. Янбых, Б.А. Столярова, B.C. Лукьянова, L.R. Bahl и D.T. Tang, A. W. Neebe и М. R. Rao, H.G. Dysart и N.D. Georganas представлены эвристические методы синтеза структуры систем на основе заданного местоположения узлов.

Таким образом, практическая задача заключается в необходимости повышения качества и эффективности функционирования СИС, за счет распределения ее ресурсов

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

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

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

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

Для достижения поставленной цели были решены следующие задачи:

1. Анализ существующих подходов к распределению ресурсов в СИС при ее синтезе и оценке качества функционирования СИС.

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

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

4. Проведение вычислительных экспериментов на разработанных моделях.

Методология и методы исследования. Методология исследования

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

Научная новизна:

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

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

3. Разработана аналитическая модель распределения ресурсов в СИС со структурой «дерево-дерево» с многопунктовыми линиями

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

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

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

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

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

1. Аналитическая модель распределения ресурсов в СИС со структурой «звезда-дерево», при которых стоимость ее синтеза будет минимальна.

2. Процедурная модель нахождения допустимого решения задачи Лагранжа в аналитической модели распределения ресурсов в СИС со структурой «звезда-дерево».

3. Аналитическая модель распределения ресурсов в СИС со структурой «дерево-дерево», при которой стоимость ее синтеза будет минимальна.

4. Процедурная модель нахождения допустимого решения задачи Лагранжа в аналитической модели распределения ресурсов в СИС со структурой «дерево-дерево».

Степень достоверности и апробация результатов.

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

Основные результаты работы докладывались и обсуждались на Международной научно-практической конференции «Техника и безопасность объектов уголовно-исполнительной системы-2011» (г. Воронеж, 2011г.); Международной научно-технической конференции «Современные

информационные технологии» (г.Пенза, 2014г.), XIV Международной научной конференции «Информатика: проблемы, методология, технологии» (г.Воронеж, 2014г.); а также на семинарах кафедры «Информационные системы и защита информации» ФГБОУ ВПО «ТГТУ».

По теме диссертации опубликовано 19 работ, в том числе 5 статей в изданиях, рекомендованных ВАК.

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

Объем и структура работы.

Диссертация, общий объем которой составляет 114 страниц, состоит из введения, четырех глав, заключения, списка использованной научной литературы,

включающего 155 наименований научных трудов на русском и иностранных языках, и приложения. Диссертация содержит 16 иллюстраций и 18 таблиц.

Работа соответствует п. 1 «Методы и модели описания, оценки, оптимизации информационных процессов и информационных ресурсов, а также средства анализа и выявления закономерностей в информационных потоках» Паспорта специальности 05.25.05 «Информационные системы и процессы».

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

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

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

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

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

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

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

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

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

2. Процедурная модель распределения ресурсов в СИС со структурой «звезда-дерево», при которых стоимость ее синтеза будет минимальна.

3. Процедурная модель нахождения допустимого решения задачи Лагранжа в аналитической модели распределения ресурсов в СИС со структурой «звезда-дерево», отличающаяся применением эвристического подхода, позволившая получить результаты с отклонением в пределах 7-14 % от нижней границы.

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

5. Процедурная модель распределения ресурсов в СИС со структурой «дерево», при которых стоимость ее синтеза будет минимальна.

6. Процедурная модель нахождения допустимого решения задачи Лагранжа в аналитической модели распределения ресурсов в СИС со структурой «дерево», отличающаяся применением эвристического подхода, позволившая получить результаты с отклонением в пределах 5% от нижней г�