Аналитические и процедурные модели распределения ресурсов в сетевых информационных системах с различной структурой тема диссертации и автореферата по ВАК РФ 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% от нижней границы за время в 2 раза меньшее.

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

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

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

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

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

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

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

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

В процессе моделирования сложных систем общепризнанно фундаментальное понятие «ресурсы» системы. В настоящее время многими авторами разработаны различные математические подходы для формализации описания данного понятия в контексте системы [1-8].

Выбор ресурсов и их распределение в системе это два наиболее часто встречающихся видов действий над ресурсами [9]. Следует отметить, что чаще

всего задачи, соответствующие этим вида действий над ресурсами, формируются независимо друг [2, 7]. В общем случае эти задачи совместимы так как логически вытекают одна из другой, а следовательно их требуется решать в рамках общей ресурсной модели [9].

Выбор ресурсов можно осуществлять различными способами. Самые простейшие из этих способов - на «глазок» [10] и использование априорной информации [11]. В классе подобных методов отметим таксономические методы [10-14]. Это методы развивают совокупность данных на непустые и непересекающиеся множества.

В случае использования нечеткой информации можно применить следующие методы: по степени разделения функций принадлежности [15], сравнение с эталоном [16], построение нечетких классификаций [17, 18] и др. [9].

В литературе уделяется достаточное внимание методам, благодаря которым происходит выявление признаков объектов [5,11-13,19-21]. Они делятся на две группы [11], которые основаны на редукции признаков, характеризующих изучаемый объект. Методы, дающие неполную редукцию, относятся к первой группе, а ко второй - полную [11,22]. Стоит отметить, что факторный анализ, также позволяет получить , так полную, так и неполную редукции [23,24]. К другим методам относят метод потенциалов [14] и метод центра тяжести [25,26].

Методы, используемые при решении задач распределения ресурсов в системах, разделяются на простые переборные методы, и методы математического программирования [9]. В связи с тем, что эффективность переборочных методов крайне низка, поскольку задачи распределения ресурсов относятся к МР-полным задачам [27], то для ее решения используются в основном методы второго типа [1,2,4,8,10, 28-35].

В первые задачи распределения ресурсов, как элементы математической теории, были сформулированы Л.В. Канторовичем. Данный подход не нашел распространения и применения, чему послужили трудности проведения сложных вычислений, возникшие из-за отсутствия эффективных средств вычислений.

В 1947г. был разработан метод решения задачи линейного программирования с одним критерием, который получил широкое распространение и которому посвящено большое количество публикаций [9,36,37,38]. Следует отметить, что методы линейного программирования могут применяться только в ограниченной области решения задач распределения ресурсов, поскольку они требуют условия линейности критериальной функции и ограничений, чего во многих реальных задачах не наблюдается.

Существуют методы нелинейного программирования, которые подразделяются на методы условной и безусловной оптимизации [39, 38]. В [40] проведено сравнение методов безусловной оптимизации. В качестве основного метода, который базируется на градиентном подходе, остается метод наискорейшего спуска. Одними из самых эффективных методов безгрдиентного решения являются методы Зангвилла и Розенброка. Методы штрафных функций, барьеров и разного рода направлений применяются при решении задач нелинейного программирования, в которых ограничения имеют форму равенства и неравенства.

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

Решение подобных задач является более сложной проблемой, что и отмечается в [28], так как эта задача относится к ИР-полной, являясь комбинаторной задачей дискретной оптимизации, чья сложность точного решения является экспоненциальной.

Точные методы дискретной оптимизации существуют лишь для отдельных классов задач [41]. Для задач целочисленного линейного программирования и нелинейного дискретного программирования используются приближенные методы и метод ветвей и границ [42, 9].

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

Так как общая задача относится к классу NP-полных задач, большинство исследований предлагает способ декомпозиции задачи на более простые составные части, которые тоже, в свою очередь, могут быть разбиты на подзадачи, пока удовлетворяющее решение не достигнуто [63-64, 65].

Задача соединения конечных узлов с центральным посредством использования узлов концентрации может быть разбита на две подзадачи. Одна подзадача включает выбор лучшего местоположения для узла концентрации информационного потока, вторая предполагает поиск оптимального способа соединения конечных узлов с ближайшим узлом концентрации. При многократном решении двух вышеупомянутых задач может быть получено адекватное решение общей задачи. Также разработаны алгоритмы жадных эвристик для решения этой задачи рекурсивно. Данные алгоритмы достаточно просты, но решение по ним далеко от оптимального при рассмотрении общей задачи [66,43].

Классическая задача о расположении узла концентрации была изучена JT. Балом и М. Тангом; А. Ниби и М. Pao; Г. Дисартом и Н. Георганасом [67-69]. МакГрегор, Шеен, Шнейдер и Застров представили различные эвристические алгоритмы для решения этой задачи [70-71], при том что, исследования проводимые до них не предполагали способа оценки качества решения (такие, как расстояние от нижней границы).

Э. Мирзаян разработал алгоритм, основанный на применении релаксаций Лагранжа, благодаря чему была получена нижняя граница при условии, что

каждый конечный узел имеет одинаковую коммуникационную нагрузку на СИС [72]. Подобный алгоритм представили Клиенцевиц и Луссв, и Ло и Кершенбаум [73-74]. X. Пиркуль представил иную модель более эффективную и включающую в себя существенную оптимизацию по сравнению с ранее рассмотренными моделями [75]. Эту модель, позже, усовершенствовали в оригинальную модель Пиркуля с возможностью добавления возможности расширения покрытия, и поэтому в процессе проектирования появились задачи решения проблем надежности. Большинство перечисленных алгоритмов подразумевает соединение конечных узлов непосредственно с узлами концентрации или центральными узлами СИС [76-78].

В то время как эти методы требуют связи конечных узлов с узлом концентрации или центральным узлом СИС, уменьшение стоимости синтеза СИС может быть получено за счет разрешения множественных конечных узлов с целью использования низко- и среднескоростных линий связи и метода «опроса». Обычно эта задача решается независимо от задачи о расположении узла концентрации рекурсивно [79]. Большинство эвристик, разработанных для синтеза подобных систем, основано на фундаментальном решении, представленном Кляйнроком, который доказал, что при большом количестве запросов полная загрузка системы есть сумма средних загрузок ее подсистем [80]. Другой способ найти золотую середину, не загружая СИС запросами -корректировать мощность в формулировке задачи, снижая ее, для гарантирования стабильной работы в пиковые периоды, но при этом уровень загруженности СИС не будет максимальным. Таким образом, известный средний уровень загруженности может быть полезен при разработке большой локальной СИС. Именно поэтому проектирование доступа локальной СИС включает в себя задачу обхода дерева минимальной мощности (СМБТ) с одинаковыми значениями информационного потока на каждом конечном узле (рисунке 1.1). X. Пападимитриу доказал, что эта задача №>-полная [81].

Решение задачи СМ8Т было целыо большого количества научно-исследовательских работ. Учитывая тот факт, что задача КР-полная, Гэвиш

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

Центральный узел СИС

Узел концентрации информационных потоков в СИС Конечный узел СИС

Рисунок 1.1 - Сетевая информационная система со структурой «звезда-дерево»

Учитывая тот факт, что задача СМ8Т имеет много общего с задачей естественного минимального обхода дерева (но намного труднее для поиска оптимального решения), жадные алгоритмы решения этой задачи были представлены Крускалем и Примом, однако эти методы все равно дают решение, далекое от оптимального [83, 84]. Эссо и Уильяме представляют самую эффективную эвристику для этой задачи. Они заметили, что даже для больших СИС их алгоритм дает обоснованное решение за небольшое вычислительное время [85]. Подобные алгоритмы представили Шарма и Эль-Бар дай, Кершенбаум

и Слайк, Ченди и Рассел [86-90]. Однако, среди всех этих алгоритмов нет ни одного, который дает абсолютную гарантию правильности решения. Гэвиш и Эльтинкемер создали параллельно-вычисляющую эвристику, которая расходовала несколько больше времени, чем алгоритм Эссо и Уильямса, но давала худшую границу [85, 91, 92]. Паттерсон представил гибридную нейронную сетевую систему, основанную на алгоритмах для решения этой задачи [93]. Решения, полученные эти методом, успешно сравнились с полученными Каватрой при помощи эвристики, тестируемой на разреженной СИС [94].

Другой подход в получении эвристик для задачи СМБТ представлен в исследованиях Гэвиша, который представил различные формулировки и решения этой задачи, используя функции Лагранжа с переменными значениями эффективности. Такие методы дали преимущество в нахождении нижней границы с допустимым решением с таким условием, что качество решения может быть оценено за счет существенно большего вычислительного уровня [82,95-96]. Каватра представил множественную формулировку задачи СМЗТ с использованием метода релаксаций Лагранжа, чтобы решить достаточно большую часть случаев задачи с отклонениями 2-12% от нижней границы. Каватра сравнил свою эвристику с работами Гэвиша, Прима, Кершенбаума и Чоу, Эссо и Уильясма и получил хорошие результаты относительно погрешности между решением и границей. Но все равно попытки поиска оптимального алгоритма не увенчались успехом из-за его сложности [84,85,94,95,97]. Последнюю попытку предпринимали Малик и Ю, используя метод ветвей и границ. Однако в исследуемых ими СИС максимум конечных узлов составлял 40 [98].

Другой способ соединения узлов концентрации подобен задаче Штайнера о графах [99, 100]. Задача Штайнера рассматривает объединение подмножества узлов СИС топологией дерева (рисунки 1.2, 1.3). Эта задача достаточно давно известна в теории графов и, как это известно, является КР-полной. Как утверждали Хуань и Ричарде, наиболее оптимальные алгоритмы из

Центральный узел СИС Конечный узел СИС

Рисунок 1.2 - Сетевая информационная система со структурой «дерево»

▲

Центральный узел СИС

Узел концентрации информационных потоков в СИС Конечный узел СИС

Рисунок 1.3 - Сетевая информационная система со структурой «дерево - дерево»

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

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

В основном, решение задач состоит из двух основных этапов: представление и, собственно, решение. Представление включает преобразование описания задачи во внутреннее понимание исследователя. В этом случае система поддержки принятия решений (СППР) должна оказать помощь, представляя информацию в виде, наиболее близко соответствующему собственному представлению лица принимающего решения (ЛПР), а также предоставляя ему набор инструментов, которые могут оказать помощь в поиске оптимального решения. Эта информация должна содержать некоторую форму познавательного стимула, который даст ЛПР сигнал о том, какие идеи могут быть верными. ЛПР может затем создать собственные эвристики и затем выбрать из них наиболее подходящую по некоторым критериям. С того времени, как исследования показали, что стиль мышления, возраст, и т. д. ЛПР сильно влияют на эффективность всей системы, способ подачи этого стимула должен быть подходящим для среднего человека, чтобы снизить влияние индивидуальных различий на качество принятия решений [102-106]. Существует широко распространенное мнение, что большинство людей создает воображаемые образы и управляет ими во время структурирования и решения задач, как бы добавляет «графический режим» [107]. Более того проведенные исследования определяют,

что визуализация задачи расположения помогает в интуитивном понимании решения задачи [108-109].

Последние исследования подчеркивают важность влияния инструментов поддержки принятия решений на человеческое сознание. Чу и Элам изучили вопрос «вызванной системной ограниченности», из-за которой СППР может ограничить человеческое поведение при принятии решения до более узких рамок, нежели система физически позволяет [110]. Исследование Гэрлэйна показало, что человек, использующий инструмент поддержки принятия решений, должен четко понимать «стратегию» работы информационной системы и представление соответствующей модели в данной системе. Таким образом, если человек ясно представляет, с помощью каких средств информационная система выполняет определенные задачи, в этом случае задача принятия решения становится несколько проще. Также, пользователь не должен ограничивать себя в выборе эвристики для использования в решении поставленной задачи [111]. Следовательно, если инструмент поддержки принятия решений ограничен выполнением фундаментальных числовых операций (например, сортировка или поиск), а исследователь возлагает на себя образное представление проектируемой модели, в таком случае системная ограниченность из исследования Чу может быть преодолена в значительной степени [110].

Широко известен тот факт, что способность человека умственно охватывать комплексное представление задачи ограничена [112, 113]. Но в каком виде тогда должна быть подана задача для облегчения понимания? Многие исследователи оценивали использование графического представления задач.

Полич и Шварц показали, что графические средства делают задачу на использования дедуктивного мышления более понятной [78]. Также, визуальные методы дали более точное понимание задачи, улучшили производительность работы над задачей и более точное решение в некоторых областях [114]. Однако, Де Санктис в исследовании заметил, что конкретное решение зависит от эффективности использования графики в информационной системе [115]. Таким образом, важно учитывать и условия, при которых могут наиболее эффективно

использоваться графические средства. Использование графических возможностей информационных систем (по мнения большинства исследователей) может быть несколько избыточным [116]. Экспериментальные оценки эффективности использования графических средств для решения задач достаточно противоречивы и спорны [117-121]. Но важно учитывать, что виды графики, проанализированные Де Санктисом и Айвсом были в основном статическими (графики, таблицы, и т.д.) [115, 116]. До 1985 г. существовало техническое ограничение в использовании графических средств информационных систем, в современных же условиях хоть и возможно создать достаточно подробное представление модели (проектирование в трехмерном пространстве, и т. д.), нужно грамотно проработать систему отображения выполняющегося или выполненного процесса на устройстве вывода, и если такое отображение недостаточно ясно представлено, даже самый сложная графическая система передаст лишь необработанные данные.

Ларкин и Саймон подчеркивают, что диаграммы могут быть более наглядны, чем словесное описание, так как: на диаграмме вся уместная информация сгруппирована; помогает сделать легко воспринимаемые для людей выводы [122].

Однако для облегчения понимания информации диаграмма должна логически верно группировать информацию, дабы впоследствии она была способной привести к осмысленным выводам. Как утверждают многие исследователи этого вопроса, построение диаграмм без учета приведенных выше принципов приводит к тому, что диаграмма не является полезной. Следовательно, важно сохранить реального мира на экране таким образом, чтобы понимание конкретного примера задачи не занимало больших умственных усилий. Важность понимания отображения информации должна быть учтена [123, 124]. Кэррол, Томас и Малхотра обнаружили, что при решении изоморфной задачи объект, снабженный информацией о своем пространстве, нагляднее представлен, чем объект, снабженный только информацией о времени, иными словами, описание объекта в пространстве было более полезным, чем во времени [125]. Также, Весси

определил, что должно быть логичное соответствие между заданием и его представлением (в виде графика или таблицы). Отсюда можно сделать вывод, что работа над задачей будет улучшена, если это соответствие будет иметь место при графической реализации задачи [126].

Визуально-интерактивный подход к принятию решения следует логически из понятия СГТПР, сформулированного Кином и Мортоном [127]. Этот подход достаточно широко распространен в последнее время, ввиду повсеместного использования информационных систем, и, в частности, графических средств этих систем. Таким образом, применение графических средств в решении задач достаточно оправдано. Бэллоу и Мастере в обзоре программной среды определения местоположения подчеркивают важность использования графических способностей, в особенности, их простоты в использовании [128]. Именно визуальная графическая система является посредником между исследователем и информационной системой, тем самым инструментом, который помогает установить связь между человеком и вычислительными ресурсами. Белл добавил, что существует много разногласий в вопросе, что должна содержать Б88. Поэтому в данной работе будут использованы визуальные системы поддержки принятия решений в областях непосредственно решения задач, структурирования и моделирования [129].

Список литературы диссертационного исследования кандидат наук Ауад Максим Сами, 2014 год

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

решение

и

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

База Данных

1-2

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

Блок определения параметров СИС

1,3

Интерфейс

вывода информации

J

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

Статическая структура классов программного обеспечения и их отношения представлены на диаграмме классов (рисунке 4.3). Рассмотрим подробнее каждый из классов.

Класс NetworkIS представляет собой СИС, которая состоит из набора узлов и связей. Данный класс обладает функциями добавления узлов (addNode) и добавления связей между узлами (addLinkToNodes). Класс NetworkIS имеет потомков: NetworkIS_StarTree, NetworkIS_ Tree, NetworkIS_TreeTree, которые представляют собой СИС со структурами «звезда-дерево», «дерево» и «дерево-дерево» соответственно. Каждый из этих классов обладает следующими функциями: search_RA - реализация процедурной модели распределения ресурсов в СИС с соответствующей структурой; decision L - реализация решения задачи

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

Класс NetworkIS композиционно связан с классами Node и Link эти классы обладают функциями inputNodeParam и inputLinkParam дающие возможность ввода параметров узлов и связей СИС.

Класс Node имеет потомков MainNode, EndNode, StackNode -представляющие собой центральный узел, конечный узел и узел концентрации СИС соответственно.

NetworkIS StarTree

+search_RA() -decision_L() -decision_L1 () decision_L2() decision_L3()

WindowResult

+show() -showTextView() -showGrafViewQ

WindowNodeParam

+show()

NetworkIS Tree

+search_RA()

-decision_L()

-decision_L1()

-decision_L2()

-decision_L3()

Ш

NetworkIS

1 +addNode() +addLinkToNodes()

Node

+inputNodeParam()

NetworkIS TreeTree

+search_RA() -decision_L() -decision_L1 () -decision_L2() -decision_L3()

WindowLinkParam

+show()

Link

+inputLinkParam()

MainNode

EndNode

StackNode

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

Классы WindowNodeParam, WindowLinkParam и WindowResult реализуют графический интерфейс пользователя СИС. Классы WindowNodeParam и WindowLinkParam реализуют функции show, требующиеся для визуализации введенных параметров узлов и связей СИС. Класс WindowResult дает возможность визуализации результатов расчета СИС, имеет функции show -отображает общий результат, showTextView - отображает результат в текстовом виде, showGrafView - отображает результат в графическом виде.

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

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

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

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

Время на вычисление не связано в значительной мере с реализацией и заняло около 2,5 часов. Несмотря на то, что это значение времени выглядит большим, следует помнить о сложности решаемой задачи.

Структура затрат на узлы концентрации

Стоимость = \Л/1* эвклидово расстояние + фиксированная цена

Мощность = \Л/2*мощность связи

\Л/1 \Л/2 Фиксированная стоимость

А1 1,2 4,0 10,0

А2 1,2 4,0 30,0

\Л/1 \Л/2 Фиксированная стоимость

Б1 1,5 4,0 10,0

Б2 1,5 4,0 30,0

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

Мощность Количество Время Верхняя Нижняя Отклонение,

связи узлов (минуты) граница граница %

концентрации

4 6 161,7 1119,67 1007,41 11,14

4 6 162,6 1135,72 1031,26 10,13

4 7 164,8167 1164,76 1041,32 11,85

4 5 162,3833 1029,92 938,39 9,75

среднее 6 162,875 10,72

5 5 162,9833 1015,62 923,38 9,99

5 4 162,55 1038,58 947,38 9,64

5 5 165,4 1067,82 961,51 11,06

5 5 160,0333 947,52 874,16 8,39

среднее 4,75 162,7417 9,77

6 4 161,1167 954,47 870,76 9,61

6 3 128,2 951,61 881,11 8,00

6 5 160,496 1009,92 902,72 11,88

6 4 159,6333 899,50 830,49 8,31

среднее 4 152,3615 9,45

7 3 160,4 908,21 829,61 9,47

7 2 160,5667 931,34 841,08 10,73

7 3 163,2 926,42 846,75 9,41

7 2 164,3833 870,62 799,32 8,92

среднее 2,5 162,1275 9,63

8 2 162,9667 880,81 803,34 9,64

8 2 160,95 887,65 815,89 8,80

8 3 163,05 898,79 826,73 8,72

8 3 154,0833 846,02 770,84 9,75

среднее 2,5 160,2625 9,23

местоположений узлов концентрации - 15, структуре затрат Б1.

Мощность Количество Время Верхняя Нижняя Отклонение

связи узлов концентрации (мин.) граница граница %

4 6 163.93 1181.71 1043.47 13.25

4 5 154.47 1191.52 1088.197 9.49

4 5 158.82 1213.35 1079.93 12.35

4 5 163.05 1248.36 1096.92 13.81

среднее 5.25 160.07 12.23

5 5 152.30 1067.75 957.3 10.96

5 4 161.55 1098.82 982.62 11.83

5 3 158.98 1066.3 978.23 9.00

5 1Я7 3? 1178 Dfi 1ППП.9 17.70

среднее 3.75 158.79 11.12

б 3 157.05 987.8? 893.84 10.51

6 3 162.10 1008.53 912.16 10.57

б 3 158.38 977.13 906.43 7.80

6 5 158.17 1047.76 931.04 12.54

спелнее 3.5 158.93 10.35

7 7 163.83 977 9fi 845.4 9 77

7 2 158.15 963.05 861.59 11.78

7 2 159.17 932.99 862.97 8.11

7 3 154.17 965.62 879.67 9.77

среднее 2.25 158.95 9.86

8 2 163.20 898.82 815.44 10.23

8 2 160.65 892.83 826.45 8.03

8 1 162.13 893.35 827.88 7.91

8 1 161.50 888.64 824.34 7.80

Среднее 1.5 161.87 8.49

местоположений узлов концентрации - 10, структуре затрат А2.

Мощность Количество Время Верхняя Нижняя Отклонение,

связи открытых узлов концентрации (минуты) граница граница %

4 ^ 1G4 88 1994 ?Р 1П8Ч ЛЯ 14 44

4 5 162.70 1150.00 1027.41 11.93

4 4 163.95 1241.32 1107.44 12.09

4 4 151.38 1193.69 1076.65 10.87

среднее 4.50 160.73 12.08

3 1RS.38 1081.91 99?.68 8.99

5 3 156.48 1038.98 935.86 11.02

5 3 162.48 1100.39 1003.05 9.70

5 2 159.83 1088.47 981.74 10.87

среднее 161.05 10.15

к ? 1fi1 48 99? п? 9?1 91 7. КП

б 2 163.82 961.75 882.52 8.98

6 3 158.37 1017.74 930.08 9.42

6 2 161.53 1000.98 906.72 10.40

среднее 2.25 161.30 9.10

7 2 161.73 943.3? 871.38 8.?6

7 1 162.17 904.98 836.43 8.20

7 1 163.83 953.08 876.16 8.78

7 2 156.50 944.76 860.83 9.75

среднее 1.15 161.06 8.75

8 1 1fi?.1S 909.68 831.45 9.41

8 1 164.70 882.44 805.6 9.54

8 1 164.27 908.88 839.95 8.21

Я П 1RS 4S 9?=;.34 83?.47 11 1fi

среднее 0.75 164.14 9.58

местоположений узлов концентрации - 15, структуре затрат Б2.

Мощность Количество Время Допусти Нижняя Отклонени

связи открытых (минуты) мое граница е,

узлов решени %

концентрации е

4 4 163.98 1268.89 1115.21 13.78

4 4 160.50 1189.84 1062.88 11.94

4 2 162.47 1290.01 1140.04 13.15

4 4 165.67 1220.63 1100.95 10.87

среднее 3.50 163.15 12.44

Я 3 164.05 1115.76 1011.6? 10.29

5 2 162.07 1075.66 962.68 11.74

5 1 162.43 1131.90 1024.00 10.54

5 2 166.03 1104.63 998.26 10.66

среднее 2.00 163.65 10.81

б 2 164.55 1021.03 937.15 8.95

6 1 162.32 984.50 894.15 10.07

6 1 155.30 1020.82 940.36 8.56

6 ? 165.63 1016.73 9?4.45 9 98

среднее 1.50 161.95 9.39

7 2 158.22 973.04 882.9? 10.71

7 1 165.50 929.97 845.01 10.05

7 1 162.67 969.09 885.52 9.44

7 1 164.00 963.00 874.81 10.П8

среднее 1.25 162.60 9.94

8 1 164.22 923.32 838.22 10.15

8 0 163.20 868.18 807.33 7.54

8 0 163.18 909.73 843.24 7.89

8 0 165.53 928.52 836.86 10.95

Среднее 0.25 164.03 9.13

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

Таблица 4.6 - Структура затрат на узлы концентрации информационных потоков в СИС с разными уровнями мощности

Структура затрат на узлы концентрации Стоимость = \У1* евклидово расстояние + фиксированная стоимость Емкость =\У2* пропускной способности канала

Структура затрат А1

\У2 Фиксированная стоимость

1.2 4.0 10.0

1.4 4.5 10.0

1.6 5.5 10.0

Структура затрат А2

"\У1 Ш Фиксированная стоимость

1.2 4.0 30.0

1.4 4.5 30.0

1.6 5.5 30.0

Структура затрат Б1

Wl Ш фиксированная стоимость

1.5 4 10.0

2.1 5.55 10.0

3.8 7,5 10.0

Структура затрат Б2

>У1 \¥2 фиксированная стоимость

1.5 4 30.0

2.1 5.55 30.0

3.8 7.5 30.0

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

местоположений узлов концентрации - 15, структуре затрат А1.

Мощность Количество Время Верхняя Нижняя Отклонени

связи открытых (минуты) граница граница е,%

узлов

концентрации

4 5 168.35 1163.47 1042.04 11.68

4 4 165.38 1136.15 1046.67 8.55

4 6 166.53 1145.17 1038.9 10.23

4 5 167.15 110?.14 1001.03 10.10

среднее 5.00 166.85 10.14

5 4 168.15 1073.51 957.55 14.11

5 4 169.32 1030.19 962.72 7.01

5 5 169.72 1066.21 953.83 11.78

5 4 169 84 1П?8 44 9?5.87 11.П7

среднее 4.25 169.25 10.49

6 3 164.88 986.6? 897.1 9.98

6 4 166.90 985.24 906.85 8.64

6 4 167.32 999.44 899.59 11.10

6 7 168.87 954.08 874.87 9.06

среднее 3.25 166.98 9.70

7 7 170.07 932.96 856.68 8.90

7 3 165.47 947.69 859.3 10.29

7 3 166.40 964.12 857.06 12.49

7 7 164 83 973 33 833.53 10 77

среднее 2.50 166.68 10.61

8 7 166.63 890.63 871.86 8.37

8 2 164.17 901.45 833.5 8.15

8 3 170.50 906.45 826.27 9.70

8 7 169.63 905.34 801.47 17.97

среднее 2.25 167.73 9.80

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

местоположений узлов концентрации - 15, структуре затрат А2

Мощность Количество Время Верхняя Нижняя Отклонени

связи открытых узлов концентрации (минуты) граница граница е,%

4 4 168.80 1252.55 1119.08 11.93

4 4 165.63 1218.85 1122.12 8.62

4 3 166.37 1280.41 1122.21 14.10

4 7 167 00 1717.34 1066 17 14.18

среднее 3.25 166.95 12.21

5 3 168.68 1138.43 1016 76 11.97

5 3 165.33 1146.13 1029.76 11.30

5 2 168.35 1136.83 1022.51 11.18

5 7 163.77 1094.35 978 7 11 87

среднее 2.50 166.52 11.57

6 7 166.57 1054.81 939.7.3 17.31.

6 1 164.45 1074.84 958.86 12.10

6 2 165.03 1055.04 953.63 10.63

6 1 165.07 1010.51 906.8 11 йй

среднее 1.50 165.25 11.62

7 0 166.42 979.16 891.08 9.88

7 1 166.97 987.59 905.93 9.01

7 1 170.00 1013.25 901.83 12.35

7 1 168 40 97? ?4 863.1? 17.64

среднее 0.725 167.95 10.97

8 1 168.20 931.31 850.63 9.48

8 1 168.47 936.13 865.28 8.19

8 1 163.83 966.78 858.59 12.60

8 0 162.02 936.77 824.8 13.58

среднее 0.75 166.38 10.96

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

местоположений узлов концентрации - 15, структуре затрат Б1

Мощность Количество Время Верхняя Нижняя Отклонени

связи открытых (минуты) граница граница е,%

узлов

концентрации

4 4 169.10 1229.26 1094.62 10.95

4 4 169.17 1205.86 1093.63 9.31

4 6 171.55 1193.27 1097.87 7.99

4 3 168.7? 1163.00 1037.97 10.75

среднее 4.25 169.63 9.75

5 3 170.53 1127.69 992.34 12.00

5 4 167.80 1078.82 1002.82 7.04

5 4 170.70 1114.46 998.89 10.37

5 ? 167.0? 1061.13 956.83 9.83

среднее 3.25 169.01 9.81

6 3 168.93 1000.93 975.?7 7.56

6 3 167.65 1015.15 934.37 7.96

б 4 169.35 1029.52 930.08 9.66

6 2 168.67 978.75 888.99 9.17

среднее 3 168.65 8.59

7 2 164.68 948.86 973.05 7.99

7 2 162.10 970.88 885.18 8.83

7 2 163.63 971.54 880.22 9.40

7 ? 165.7? 941 61 849 88 9.74

среднее 2 163.9.1 8.99

я ? 167 93 90? 7Д 851 91 5.63

8 1 164.63 917.47 839.85 8.46

8 7 159.53 926.98 844.93 8.85

8 7 167.0? 917.33 810.33 11.37

среднее 1.75 164.78 8.58

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

местоположений узлов концентрации - 15, структуре затрат Б2

Мощность Количество Время Верхняя Нижняя Отклонени

связи открытых (минуты) граница граница е,%

узлов

концентрации

4 2 160.59 1320.24 1148.91 12.98

4 3 161.60 1296.68 1166.69 10.02

4 3 162.58 1311.14 1175.08 10.38

4 3 164.88 1238.74 1096.81 11.46

среднее 2.75 162.41 11.21

5 2 163.23 1171.90 1046.79 10.68

5 3 169.55 1160.43 1066.69 8.08

5 2 164.23 1176.21 1068.20 9.18

5 2 166.87 1104.63 997.36 9.71

среднее 2.25 165.97 9.41

6 2 165.20 1016.43 923.96 9.10

6 1 167.68 1070.27 982.61 8.19

6 2 162.97 1076.11 983.15 8.64

6 2 170.18 1013.29 920.95 9.11

среднее 1.75 166.51 8.76

7 1 164.90 983.08 897.88 8.67

7 1 162.50 1008.68 919.49 8.84

7 2 164.92 1029.92 920.55 10.62

7 1 165.03 963.96 870.28 9.72

среднее 1.25 164.34 9.46

8 0 165.12 929.96 859.88 7.54

8 0 162.00 948.66 873.27 7.95

8 0 164.87 974.57 871.71 10.55

8 0 163.15 926.79 833.54 10.06

среднее 0 163.78 9.02

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

Вычислительный эксперимент распределения ресурсов в СИС со структурой «дерево» проводился с изменением мощности соединения от 6 до 9. Сгенерированы разные случаи задачи с нормальным распределением значений мощности соединения в квадрате размерностью 100x100. Стоимости связи конечных узлов друг с другом приняты равными евклидовому расстоянию между узлами.

Центральный узел был размещен на пересечении диагоналей квадрата. Результаты решения представлены в таблице 4.11-4.12, в которой также приведены результаты вычислений других авторов при решении подобной задачи [94]. Таблицы 4.13. и 4.14 представляют результаты расчетов для случая, где центральный узел перемещен в угол квадрата. В таблицах 4.11-4.14 значение отклонения определяется по формуле

Верхняя граница—Нижняя граница „

Отклонение = —---* 100,

Нижняя граница

а также введены следующие обозначения Тг - время решения задачи распределения ресурсов в СИС с использованием разработанных процедурных моделей; Т2 - время решения аналогичной задачи в других исследованиях [94]; 01 - отклонение, полученное с использованием разработанных процедурных моделей; 0г - отклонение, полученное при решении аналогичной задачи в других исследованиях [94].

Таблица 4.11 - Сравнение результатов, полученных с использованием разработанной процедурной моделью распределения ресурсов в СИС со структурой «дерево», с результатами других авторов [94] для случая

расположения центрального узла СИС на пересечении диагоналей

Количество узлов Мощность соединения Верхняя граница из [33] Нижняя граница 1 из [33] О Верхняя граница Нижняя граница Г"! О

100 6 1084.20 990.31 9.48 123.25 1062. 964.8 10.07 64.53

100 6 1084.08 994.10 9.05 123.92 1083. 986.4 9.87 67.25

100 6 1041.25 971.10 7.22 124.87 1046. 970.6 7.83 67.0Ь

100 6 1001.92 915.74 9.41 122.33 1007. 915.3 10.02 66.15

100 7 981.61 899.69 9.10 120.91 975.7 911.4 7.04 55.03

100 7 994.81 928.19 7.17 118.91 1007. 928.7 8.44 64.82

100 7 967.414 900.51 7.42 124.89 968.4 903.6 7.17 60.28

100 7 919.83 853.15 7.81 117.26 921.4 853.9 7.90 67,12

100 8 922.76 857.48 7.61 121.34 924.2 861.2 7.31 63.66

100 8 944.64 869.72 8.61 120.88 943.0 880.5 7.10 65.65

100 8 921.53 858.54 7.33 121.80 925.5 860.1 7.60 63.83

100 8 873.04 803.73 8.62 115.84 862.6 809.7 6.53 68.04

100 9 880.07 815.55 7.91 119.30 886.3 825.1 7.41 64.00

100 9 903.59 833.21 8.44 121.16 900.7 843.7 6.74 63,66

100 9 871.83 810.23 7.60 115.37 878.9 825.5 6.46 68.44

100 9 827.07 764.88 8.13 119.97 827.3 776.0 6.61 67.20

Таблица 4.12 - Сравнение вычислительного времени и отклонений, полученных с использованием разработанной процедурной моделью распределения ресурсов в СИС со структурой «дерево», с результатами других авторов [94] для случая расположения центрального узла СИС на пересечении диагоналей

Количество узлов Мощность соединения 100,% т2 о2

100 6 52.35 1.06

100 6 54.27 1.09

100 6 53.70 1.08

100 6 54.07 1.06

100 7 45.51 0.77

100 7 54.51 1.17

100 7 48.26 0.96

100 7 57.2.4 1.01

100 8 52.46 0.96

100 8 54,31 0.82

100 8 52.40 1.03

100 8 58.74 0.75

100 9 53.62 0.93

100 9 52.54 0.79

100 9 59.32 0.85

100 9 56.02 0.81

среднее 53.71 0.95

Таблица 4.13 - Сравнение результатов, полученных с использованием разработанной процедурной моделью распределения ресурсов в СИС со структурой «дерево», с результатами других авторов [94] для случая

расположения центрального узла СИС в углу

Количество узлов Мощность соединения Верхняя граница I из [331 1 Нижняя граница из [33] см о Верхняя граница Нижняя граница 1 тН о

100 6 1693,82 1443.65 1733 119.48 1708,02 1473,70 15.90 66,45

100 6 165536 1441.94 14.80 117.42 1643.66 1456.46 12.85 64.90

100 6 1658.77 1427.57 1620 121.49 1644.16 1448,43 13.51 67.42

100 6 1592.96 1368.13 16.43 П 622 1604.73 140537 14.19 65.91

100 7 151631 133023 13.99 11726 1526.08 1349.00 13.13 64.46

100 7 1490.43 1327.54 1227 119.72 1526.06 1330.09 14.73 64.87

100 7 148825 1317.65 12.95 116.58 1484.94 1326.51 11.94 6428

100 7 1436.60 1373.52 12.81 116.61 1464.09 1289.03 13.58 65.57

100 8 1393.12 1229.13 1334 115.70 1388.94 1247.58 1133 6821

100 8 1379.14 122328 12.74 116.94 137729 124225 10.87 66.46

100 8 1369.85 1209.16 1329 117.67 1357.06 1221.51 11.10 67.16

100 8 131936 1179.76 11.83 11632 1323.18 1190.48 11.15 6932

100 9 1281.48 1141.99 1221 118.38 1302.63 1156.90 12.60 65.40

100 9 127322 1140.91 11.60 117.02 127126 1147.58 10.78 65.11

100 9 1285.55 111333 15.47 11838 1269,42 1120.48 1329 66.42

100 9 1232.00 1096.89 1232 117.69 1253.69 1109.02 13 04 67.11

Таблица 4.14 - Сравнение вычислительного времени и отклонений, полученных с использованием разработанной процедурной моделью распределения ресурсов в СИС со структурой «дерево», с результатами других авторов [94] для случая расположения центрального узла СИС в углу

Количество узлов Мощность соединения - * 100, % т2 100,% о2

100 6 55.61 0.91

100 6 55.2.7 0.86

100 6 55.49 0.83

100 6 56.71 0.86

100 7 55.82 0.93

100 7 54.18 1.20

100 7 55.13 0.92

100 7 56.22 1.06

100 8 58.95 0.84

100 8 56.83 0.85

100 8 57.07 0.83