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

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

ШАМШЕВ АНАТОЛИЙ БОРИСОВИЧ

АВТОМАТИЗИРОВАННОЕ ТОПОЛОГИЧЕСКОЕ ПРОЕКТИРОВАНИЕ ВЫЧИСЛИТЕЛЬНЫХ СЕТЕЙ НА ОСНОВЕ БАЙЕСОВСКИХ СЕТЕЙ ДОВЕРИЯ

Специальность: 05.13.12 — Системы автоматизации проектирования по техническим наукам (промышленность)

Автореферат

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

Ульяновск - 2006

Работа выполнена в Ульяновском Государственном Техническом Университете

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

профессор Ярушкина Надежда Глебовна

Официальные оппоненты: д т н.,

профессор, зав. кафедрой "Вычислительная техника" УлГТУ Соснин Пётр Иванович

к.т.н,

директор по развитию ООО "Креативная разработка"

Вербиченко Дмитрий Станиславович

Ведущая организация: ФНПЦ ОАО НПО "Марс"

г. Ульяновск

Защита состоится 24 мая 2006 г. в 15 ч. 00 мин. на заседании диссертационного совета Д 212.277.01 при Ульяновском Государственном Техническом Университете по адресу: г. Ульяновск, ул. Северный Венец, 32.

С диссертацией можно ознакомиться в библиотеке Ульяновского Государственного Технического Университета.

Автореферат разослан "__"_ 2006 г.

Ученый секретарь

диссертационного совета Д 212.277.01 доктор технических наук, профессор Казаков М. К.

/)

/ -

Общая характеристика работы

Актуальность

Создание современных эффективных вычислительных сетей предприятия осуществляется при помощи систем автоматизированного проектирования вычислительных сетей (САПР ВС). Так как задача проектирования вычислительной сети является объёмной и сложной, САПР ВС должна обладать элементами интеллектуальности.

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

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

В решение данной задачи существенный вклад внесли следующие учёные: Р. А. Алиев, В. В Емельянов, В. И Захаров, А. В. Колесников, Ярушкина Н, Г., Ясиновский С. И. и др.

Объект и направление исследований

Объектом исследования является процесс проектирования вычислительной сети. Направление исследований связано с исследованием методов интеллектуализации процесса: использования байесовских сетей доверия, генетических алгоритмов.

Предмет исследований

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

Основные цели и задачи исследования

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

Задачи исследования сформулированы следующим образом:

1. Адаптировать механизм байесовских сетей доверия для принятия проектных решений на различных этапах проектирования ВС

2. Разработать структуру системы автоматизированного проектирования ВС,

позволяющую использовать механизм байеговских сетей доверия

3 Разработать систему автоматизированного проектирования ВС с использованием механизма байесовских сетей доверия для принятия проектных решений в процессе проектирования ВС

Метод исследований

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

Научная значимость работы

Автор защищает" методику и модели автоматизированного проектирования вычислительных сетей на базе байесовских сетей доверия, разработанные алгоритмы статического и динамического моделирования трафика, результаты теоретических и экспериментальных разработок.

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

1 Разработана методика моделирования рассуждений проектировщика на основе байесовской сети доверия в интеллектуальной САПР ВС.

2. Построены байесовские сети доверия для определения коммутационного оборудования и пропускной способности каналов

3 Модифицированы байесовские сети доверия для использования нечётких высказываний в качестве свидетельств.

4 Предложена новая архитектура САПР ВС на основе взаимодействия байесовских сетей доверия и генетических алгоритмов.

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

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

2. Модели рассуждений по выбору коммутационного оборудования и пропускной способности каналов, представляющие собой байесовские сети.

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

4 Архитектура интеллектуальной САПР ВС как система взаимодействующих генетических и байесовских компонент.

Достоверность

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

Практическая ценность

Практическую ценность работы составляет разработанная система автоматизированного проектирования САПР ВС "Проектировщик". Система реализована в среде Borland Delphi 5.

Для ФНПЦ ОАО НПО "МАРС'проведены расчёты, позволившие сформулировать проектные решения.

Реализация и внедрение результатов

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

Апробация работы

Содержание работы докладывалось и обсуждалось на следующих конференциях:

Международных: Interactive systems: The problems of computer - human interaction. Ulyanovsk, 2003 г.; Континуальные алгебраические логики, исчисления и нейроинформатика в науке и технике". Ульяновск, 2004 г.

Российских: Научная сессия МИФИ-2003; 9-я Национальная конференция по Искусственному Интеллекту - КИИ 2004; Оптимальные методы решения научных и практических задач. Таганрог, 2005 г.

Результаты неоднократно докладывались на конференциях Ульяновского Государственного Технического Университета: 37 научно - техническая конференция УлГТУ (Ульяновск, 2003), 38 научно - техническая конференция УлГТУ (Ульяновск, 2004), 39 научно-техническая конференция УлГТУ (Ульяновск, 2005)

Разработанный в рамках данной работы программный продукт (САПР ВС "Проектировщик") был зарегистрирован в отраслевом фонде алгоритмов и программ (ОФАП) (номер 3709 от 25 июня 2004 года), а также получено свидетельство о регистрации объекта интеллектуальной собственности РосПатента (номер 2005610664 от 17 марта 2005 года).

Структура и объём работы

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

В первой главе рассматриваются различные существующие САПР ВС и делается вывод о недостаточности их возможностей, а именно: отсутствие возможности обработки трафика, задаваемого в нечёткой или лингвистической форме,

отсутствие возможности учёта особенностей автоматизируемых производственных процессов

В качестве средств принятия проектных решений рассматриваются.

• Байесовские сети доверия Приводятся примеры их применения и краткий обзор программ для работы с ними (Хабаров С. П ,Тулупьев А Л , Николенко С И., Григорьев Р В., Синдеев А С, Частиков А. П , Леднева И. Ю., Мукаи-доно М., Аллен Б. и др.)

• Нечёткие нейронные сети. (Ярушюша Н.Г., Алиева Д.И., Крыжановский В.В , Крыжановский В.М., Баринов С В , Гладков Л А , Семенов Н А., Борисов А Л , Рожков А.А , Прохоров И.В., Синюк В.Г., Семернин С.П., Абу-Мустафа Я С . Псалтис Д. и др.)

• Сети Петри. Также рассматриваются нечёткие, цветные и синхронные сети Петри (Шайкин А.Н., Егоров А.Ф , Питерсон Дж, Каланов ГН, Петри К.А, Соколов В А.,Ломазова И А.,Рубцова Э. Е.,Сидорова Н. С., Юстинова Н Ю., Котов В.Е., Кулагин В.П. и др.)

• Генетические алгоритмы (Дж Холланд, Л. Дэйвис, Л Голдберг, Д. Фогель, Д И. Батищев, И Л Букатова, В. В Емельянов, В М Курейчик, В. В. Курейчик, И П Норенков и др.)

• Деревья решений (Брейман Л., Ховленд, Хаит Е. В., Мэрии Д, Стоун П. Д Квинлан Р., Мурти С., Бантине У., Шеннон К., С.А. Айвазян, В.С Мхитарян, Ходжаева И., Р. Куинлен и др.)

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

Таблица 1: Методы принятия проектных решений

Название метода Преимущества метода Недостатки метода

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

Нечёткие нейронные сети Скорость получения результатов Низкая объяснительная способность, сложности с построением структуры сети, необходимость обучающей выборки

Генетические алгоритмы Сравнительная простота реализации Нахождение минимума не гарантировано, отсутствие обоснования результата

В первой главе проанализированы основные существующие САПР ВС, а именно: Prophesy (American HYTech), COMNET III (CACI Product), NetMaker XA (Make System), StiessMagik (NetMagic System), MIND (Network Analysis Center), AutoNet Designer (Network Design and Analysis Group), AutoNet/ MeshNET, Auto-Net/ Performancel, AutoNet/ Performance3 (Network Design and Analysis Group), BONES (System & Networks), Opnet (MIL3). Подробно представлена open-source система моделирования ВС NS2 (VINT project network simulator).

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

Представлены основные источники информации о значениях трафика: измерения ВС и функциональные диаграммы.

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

Представление производственных процессов основано на дополненных DFD -диаграммах. Отличие дополненных DFD - диаграмм от стандартных заключается в том, что элементам стандартных DFD - диаграмм были назначены дополнительные атрибуты.

Трафик представлен в виде нечётких величин с функциями принадлежности трапециевидной формы, заданными в следующем виде: Т = (m,n,a,ß), где m, п - границы единичного интервала, а, ß - области нечёткости. Такое представление позволяет упростить реализацию операций с трафиком.

В САПР ВС для трафика задано четыре нечётких метки:"Крохотный", "Малый", "Средний", "Высокий". Эти нечёткие метки выбраны потому что они, с одной стороны, покрывают все возможные значения трафика, и, с другой стороны, обеспечивают достаточную гибкость для работы с ним.

Для нечётких значений трафика заданы следующие операции: сложение, вычитание, сравнение. Формула сложения нечётких меток Ml и М2 имеет следующий вид:

' rnm — mM\ + тМ2 п-мз ~ nMi + пмг (*мз = <*т + пМ1 . ßi43 — pMl + /?ЛГ2

Формула вычитания двух нечётких меток имеет вид:

тмз = mMi - ™>М2

пМЗ — пМ1 — пМ2

am — «Mi + лиг

. ßm — Аш + Am

Для сравнения двух нечётких меток используются типичные представители, вычисляемые по формуле центра тяжести:

¡ху,{х)<1х / ¡1{х)йх

В разработанной САПР ВС моделируется только статическая маршрутизация.

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

Модель ВС состоит из трёх множеств- множества компьютеров Мт = Мт и Ма, где Мш - подмножество рабочих станций и Ма - подмножество серверов данных, множества коммутационных узлов Мдг = М/, и Мш и Мт, где М), - подмножество концентраторов, М$и, - подмножество коммутаторов и Мт - подмножество маршрутизаторов и множества каналов Мсь, в которое входит всевозможная среда передачи данных Ограничения в данной модели определяются лишь параметрами компьютера, на котором производится имитационное моделирование

Основной характеристикой компьютера является уникальное в пределах сети имя С ¡и Дополнительными характеристиками компьютера являются его тип (рабочая станция или сервер), хранимые базы данных работающие на компьютере пользователи.

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

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

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

Определение параметров трафика на каналах ВС невозможно без моделирования ВС.

В работе реализовано два вида моделирования: динамическое и статическое. Цель статического моделирования - определение величины пикового трафика -трафика, проходящего по каналам ВС при одновременном выполнении пользователями всех своих задач. Цель динамического моделирования - определение времени, за которое по каналам вычислительной сети проходит трафик, порождаемый

действиями пользователей.

Основная идея статического моделирования заключается в определении влияния взаимодействия двух компьютеров ВС на глобальное распределение трафика по каналам ВС. Алгоритм статического моделирования можно представить следующим образом:

Для каждого взаимодействия в ВС:

Начать распространение трафика от компьютера - источника Распространять трафик до достижения

компьютера - получателя взаимодействия Продолжать распространение трафика до прекращения распространения

Конец цикла

Основным преимуществом такого решения является его независимость от структуры ВС.

Структура динамической модели представлена на рисунке 1.

1 - Таймер, отвечающий за генерацию разрешающих сообщаю**

2 - Таймер, отвечающий за обноепвте диаграмм динамики работы модели

Рис. X: Структура динамической модели ВС

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

• Объекты сети работают параллельно

• Компьютеры большую часть времени находятся в состоянии ожидания возможности посылки или приема данных

• Узлы сети работают тогда, когда в их каналах находятся данные, всё остальное время они находятся в состоянии ожидания

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

Данная модель реализована при помощи библиотеки параллельного программирования Gala в среде Borland Delphi 5.

Алгоритмы работы элементов модели могут быть представлены следующим образом: Канал ВС:

Получение данных от устройства на одном канале ВС Передача полученных данных устройству на другом канале ВС

Коммутационный узел ВС:

Ожидание прихода данных на любой порт узла

Получение пришедших данных

Определение портов узла, на которые необходимо

передать полученные данные Передача данных на определённые порты

Сервер ВС:

Ожидание получения данных Получение данных

ЕСЛИ данные элемента задачи получены полностью ТО Формирование данных ответа на элемент задачи Передача данных ответа на элемент задачи КОНЕЦ ЕСЛИ

Рабочая станция:

Ожидание сигнала начала выполнения задачи Формирование данных элемента первой задачи Передача данных

Ожидание прихода данных ответа на переданный элемент Получение данных ответа

ЕСЛИ переданный элемент не был последним ТОГДА Переход к передаче следующею элемента задачи ИНАЧЕ

Переход в состояние ожидания сигнала начала выполнения задачи КОНЕЦ ЕСЛИ

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

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

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

Рассмотрим процесс пересчёта вероятностей в БСД. Схематически алгоритм обновлеттия вероятностей представлен на рисунке 2. Пусть Ве1\А,} — р(Аг\0) есть

Рис. 2: Процесс обновления информации в БСД

вероятность, отражающая всевозможные доверия, связанные с предположением А = А, для всех полученных на данный момент свидетельств Б. Распределение доверия каждой переменной может быть получено если доступны три параметра:

• 7Г - текущее значение силы «причинной поддержки» тт^й) = р(й\Е{), где Е\ - множество всевозможных свидетельств всех предков узла (х). Этот параметр показывает доверие к тому факту, что данная причина свершилась при данных вероятностях сё предков.

• Л - текущее значение силы «диагностической поддержки» Л2 = р(£2|а;), где Е2 - множество всевозможных свидетельств всевозможных потомков узла х Этот параметр показывает доверие к тому факту, что свершились потомки данной причины при её конкретной вероятности.

• р(х\й, у) - фиксированный тензор условных вероятностей, который соотносит переменную х с её непосредственными родителями.

Алгоритм обновления вероятностей состоит в следующем:

Шаг 1. Обновление доверия При активизации узла для обновления параметров, то сразу же:

• проверяется ^(м), тгх(у) его родителей

• проверяется \{х), Л2(х) его потомков

Тогда мера доверия узла X вычисляется по формуле:

Ве1[х] = а\у{х)Аг(х) ^(р(х\йу)пх(й)тгх{у)),

йу

где а находится из условия нормализации.

Т.ВеЩ = 1

X

Шаг 2. Обновление Л Используя полученное сообщение, каждый узел вычисляет сообщение Л, которое будет послано его родителям:

Шаг 3. Обновление тт. Каждый узел вычисляет новое сообщение ж, которое будет послано его потомкам:

я-у(х) = аХ(х) £р(:г|й, ^¿(«^(й)

Процесс распространения вероятностей как начинается, так и заканчивается в конечных узлах сети, при этом:

• Ожидающий узел есть переменная с нсприсвоенным значением Для таких узлов х полагаем, что Апотомок(ё) = 0.5

Уровень 1 Ввод информации об интенсивностях взаимодействия

МУВ Таблица сложения »•четких величин

Уровень 2 Определение трафика на каждом канале ВС

МУВ'Таблица сложения нечётких величин

Уровень 3 Определение внутрисегментного и межсегментного трафика для каждого узла ВС

Для каждого параметра МУВ Критерии для типа узла и производи-задаётся экспертом отдельно плыдохв- производительность и | стоимость

Уровень 4. Определение типа узла, производительности и приоритетности для каждого узла ВС

Рис 3. Струкгура байесовской се!и доверия доя определения состава комму хационного оборудования

• Свидетельствующий узел есть означенная переменная. В этом случае ■^потомок (я) = 1> если х совпадает со значением переменной и Апотомок(^) = О в противном случае.

• Корневой узел представляет переменную без предков. Для каждой такой переменной вводим фиктивного предка и, постоянно представляющего значение й — и, и множество условных вероятностей на связи и —► х, каждая из которых равна априорной: р(х|й) = р(х).

Следует отметить следующие недостатки приведённого алгоритма - итераци-онность и сложность в реализации. Эти два недостатка приводят к резкому росту времени обновления вероятностей по мере увеличения размеров графа сети доверия.

Структура сети доверия для определения состава коммутационного оборудования, его пропускной способности и пропускной способности приведена на рисунке 3. Структура сети доверия для определения пропускной способности каналов приведена на рисунке 4.

Матрицы условных вероятностей для последних уровней сетей доверия определяются двумя параметрами: производительностью (пропускной способностью) и стоимостью. В разработанной САПР эти матрицы могут быть заданы двумя способами:

• Экспертом вручную. В этом случае эксперт полностью вручную устанавливал ет все значения условных вероятностей. Данный режим может быть использован в том случае, если для оптимизации применяются дополнительные критерии, помимо производительности и стоимости. Недостатком данного метода является сложность для эксперта формирования числовых значений матрицы вероятностей.

Уровень 1. Ввод информации об интенсивности взаимодействия

МУВ: Таблица сложения нечетких величин

Уровень 2. Определение трафика на каждом канале ВС

МУВ задаётся экспертом. Критерии -пропуская способность и стоимость

Уровень 3. Определение пропускной способности канала, достаточной для пропускания вычисленного на уровне 2 трафика

Рис 4 БСД для определения пропускной способности каналов сети

• Экспертом с учётом весов параметров производительности и стоимости. В этом случае эксперт устанавливает вручную матрицы условных вероятностей отдельно для параметра "производительность" и параметра "стоимость". Матрица условных вероятностей формируется из заданных экспертом матриц с учётом заданных экспертом весов параметров

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

В задаче оптимизации размещения коммутационного оборудования вводятся два типа ограничений:

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

• Ограничения на прохождение каналов. Данные ограничения представляют собой те места, в которых прокладка каналов по каким - либо причинам невозможна, например, стены, открытые места и т.д. Для определения возможности прокладки каналов ВС без нарушения ограничений используется трассировка волновым алгоритмом по 4 точкам с обратной трассировкой. В случае невозможности выполнения трассировки хромосома признаётся некорректной и дальше не обрабатывается.

Оба вида ограничений могут иметь любую геометрическую форму.

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

Целевая функция для задачи оптимизации размещения коммуникационного оборудования имеет вид:

Л/с л т—1

орИт = £ , £ (4 - я.о+и)2 + (у% - 2/.У+1)) * Ье/огран., 1=1 \

где ru - число ключевых точек, образующих капал ВС, хч,уц и ж,(т), | ij -координаты двух последовательных ключевых точек г-го канала ВС, кое foi ран -коэффициент, характеризующий нарушение узлами ВС ограничений на размещение Если ограничения не нарушены, коэффициент равен 1, в противном случае он равен 10 * (количество узлов вне ограничений).

В задаче оптимизации подключения рабочих станций имеются два ограничения:

• Компьютер может быть подключён только к одному узлу ВС

• Количество устройств, подключённых к узлу, не должно превышать количество его портов

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

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

optim - sup(max(T,)) * ¿¡польз,

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

Третья глава описывает программную реализацию САПР ВС с использованием байесовских сетей доверия. На рис. 5 представлена структура САПР ВС, состоящая из 7 модулей:

1. Визуальный DFD редактор, отвечающий за построение DFD - диаграмм описания производственных процессов. Также он отвечает за переход от DFD -диаграмм к черновому варианту вычислительной сети.

2. Модуль перехода от DFD - диаграмм к структуре ВС. Данный модуль получает' от пользователя САПР ВС дополнительные данные и производит построение первоначальной структуры ВС.

3. Редактор вычислительной сети. Отвечает за работу с оборудованием и структурой вычислительной сети

4. Модуль байесовских сетей доверия. Он предназначен для работы с байесовскими сетями доверия, при помощи которых происходит определение состава коммуникационного оборудования и пропускной способности каналов ВС.

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

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

6. Модуль статического моделирования. Он определяет пиковое значение трафика на каналах текущего варианта вычислительной сети.

7. Модуль динамического моделирования. Этот модуль определяет динамическое распределение трафика на каналах вычислительной сети с учётом нечёткого вероятностного характера трафика

Задача топологического проектирования решается модулями генетической оптимизации и байесовской оптимизации.

Переход от №0 к ВС

Модуль динамического моделирования

визуальное редасгфоаание СГО-дизгрэмм |ОРР-редактор!

моделирование динами» трафим ВС

Олределеше пмоюй нафуяи на ВС

олпииза^ия размещения «омм Оборудования

Рис. 5: Структура разработанной САПР ВС

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

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

Приведена реализация классов для генетической оптимизации с описанием полей и методов классов.

Также приведена реализация байесовских сетей доверия с использованием СОМ-интерфейсов библиотеки М81ДОх фирмы М1сго8ой. Приведены описания на задействованные при реализации поля и методы интерфейсов.

Задача проектирования вычислительной сети заключается в последовательном выполнении этапов, представленных на рисунке 6.

Рис 6 Этапы проектирования вычислительной сети

На рисунке б выделены те этапы проектирования ВС, на которых может применяться разработанная в рамках данной работы САПР.

В четвёртой главе представлены результаты, полученные при использовании разработанной САПР ВС для построения и оптимизации параметров гипотетической ВС и оптимизации параметров се!мента ВС ФНПЦ ОАО НПО "Марс".

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

Для вычислительного эксперимента была взята сеть третьего этажа ФНПЦ ОАО "НПО Марс". Данная ВС состоит из 34 рабочих станций, 1 сервера данных, 9 коммуникационных узлов. Все узлы ВС представлены коммутаторами.

Были предоставлены данные о объёме передаваемых данных и расписании выполнения задач на рабочих станциях

Вычислительные эксперименты проводились для следующих вариантов ВС'

• Исходный вариант ВС

• Оптимизированный вариант ВС при весе параметра Производительность равным 75'/,

• Оптимизированный вариант ВС при весе параметра Производительность равным 50'/,

• Оптимизированный вариант ВС при весе параметра Производительность равным 25'/,

• Утроенный вариант ВС при весе параметра Производительность равным 75'/,

• Утроенный вариант ВС при весе параметра Производительность равным 50'/,

• Утроенный вариант ВС при весе параметра Производительность равным 257,

Утроенный вариант ВС подразумевает утроение размера передаваемых по ВС данных.

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

Сводные таблицы результатов оптимизации состава коммуникационного оборудования для исходного варианта ВС НПО "МАРС":

Таблица 2: Состав коммутационного оборудования

Наименование узла Хаб, 75'/. Свил, 75% Роутер 75'/. Хаб, 50% Свитч, 50% Роутер 50% Хаб, 25% Свитч, 25% Роутер. 25%

изег_{10от325_Мос1е 0.425 0.725 0.15 0.55 0 45 0 0.68 0.32 0

иэе! .ИоотЗОЭ.Коёе 0125 0 725 0.15 0.25 0 65 0 1 0 38 0.572 0.048

и8ег_Яоот306_Ко<1е 0.125 0.725 0.15 0.25 0 65 0.1 0.38 0.572 0.046

Шег_йоот303_№х1е 0.125 0.725 0.15 0 25 0.65 01 0.38 0 572 0.048

1]8ег_йоот332_Коае 0.425 0.575 0 0.55 0.45 0 0.68 0 32 0

изег.йоотЗЗЗ.Моёе 0.425 Ó.S75 0 0.55 0.45 0 0.68 0.32 0

и8ег_Яоот3301о<1е 0.125 0.725 0.15 0 25 0.65 0.1 0.3ÍJ 0.572 0 048

User.Room301.Node 0.125 0.725 0.16 0.25 0.66' 0.1 0.38 0.572 0.048

Сеп1га1_1Чо(1е 0.125 0.5 0 375 025 05 0.25 0.38 05 012

Таблица 3: Пропускная способность коммутационного оборудования

Наименование узла Низ- Сред- Высо- Низ- Сред- Высо- Низ- Сред- Высо-

кая няя кая кая няя кая кая няя кая

75% 75% 75% 50% 50% 50% 25% 25% 25%

ивег_Яоот325_Моде 0.482 |0518 0 0.65 0.35 0 0.832 0.168 0

иье1_11оош309_Моае 0.5 Т)Г5 0 0.5 05 0 0.5 0.5 0

изег_1кюш306_№х1е 0.5 0.5 0 05 0.5 0 0.5 0.5 0

изег_11оот303_Ко<1е 0.5 0.5 0 0.5 0.5 0 0.5 0.5 0

ибег_Иоот332_Мо<1е 0.482 0.518 0 0.65 0 35 0 0-832 0.168 0

ивег.ШютЗЗЗ.Г'Ые 0.482 0.518 0 0.65 0.35 0 0.Й32 0.163 0

ибег_Яоот334_!Чо<1е 0.5 0.5 0 0.5 0.5 0 0.5 0.5 0

ивег.йоот301_Ко<1е 0.5 0.5 0 0.5 0.5 0 0.5 0.5 0

Сеп1га1_№)с1е 0.296 0.574 0.13 0.2 0.55 0.25 0.096 0.524 0.38

Таблица 4 Приоритетное 1Ь модерпимции способное]ь иоммудационлого оборудовании

Наименование узла Низ- Сред- Высо- Низ- Сред- Высо- Мил- Сред- Высо-

кая няя кая кая няя кая кал няя кая

75'/. 75'/. 757. 50% 50% 50% 25% 25% 25%

ияе1 _11оот325_Мос1е 0.475 0.525 0 0 65 0.35 0 0.825 0.175 0

User.Room309.Node 0.5 05 чг 05 0 5 0 0.5 05 0

Usei.Boom306.Node 0.5 05 ТГ 05 0.5 0 05 05 0

Usei.Room303.Node 0.5 05 0 0.5 05 0 0.5 0.5 0

User.Room332.Node 0.475 0.525 0 0.65 0.35 0 0.825 0.175 0

User_R00InЗЗЗ_N0de 0 475 0 525 0 0 65 0 35 0 0 825 0175 0

Ше1 _Еоот334_>) обе 0.5 05 0 05 н 05 0 05 05 0

User_Room301_Node 0.5 0.5 0 0.5 0.5 0 0.5 05 0

CentraLNode 03 0.575 0.125 0.2 0 55 0 25 0.1 Т) 525 0.375

Сводные таблицы результатов оптимизации состава коммуникационного оборудования для утроенного варианта ВС НПО "МАРС".

Таблица 5' Состав коммутационного оборудования

Наименование узла Хаб, 75% Свитч, 75% Роухер 75% Хаб, 50% Свитч, 50% Роугер 50% Хаб, 25% Свитч, 25% Роутер 25%

User.Room325.Node 0.13 0 722 0.148 0.25 0.65 0.1 0.375 0.575 0.05 0 05

User.Room309.Node 013 0.722 0148 0 25 0.65 0.1 0 375 0 575

User.Iloom306.Node 0.13 0 722 0148 0 25 0.65 0.1 Ó 375 0.575 0 05

User.Room303.Node 0.13 0.722 0.148 0 25 0 65 0.1 0.375 0.575 0.05

User.Room332.Node 0.13 0.722 0.148 0 25 0.65 I 0.1 0.375 0.575 0 05

User.Room333.Node 0.13 0.722 0148 0.25 0.65 0.1 0.375 0.575 0 05 0 05

User.Room334.Node 0.13 0.722 0.148 0.25 0.65 0.1 0.375 0.575

User.Room301.Node 0.13 0.722 0.148 0 25 0.65 01 0.375 0 575 0 05

Central_Node 0.13 0.5 0.37 0.25 0.5 0.25 0 375 0.5 0.125

Таблица 6: Пропускная способность коммутационного оборудования

Наименование узла Низ- Сред- Высо- Низ- Сред- Высо- Низ- Сред- Высо-

кая няя кая кая няя кая кая няя кая

75% 75% 75% 50% 50% 50% 25% 25% 25%

User.Room325.Node 0.5 05 0 0.5 0.5 0 0.5 05 0

User.Room309.Node "075 0.5 0 0.5 ТП5 0 0.5 0.5 0

User.Room306.Node 0.5 0.5 0 0.5 05 0 0.5 05 0

ивег.ЫоошЗОЗЛоёе 0.5 0.5 0 0.5 0.5 0 0.5 0.5 0

User.Room332.Node 0.5 0.5 0 0.5 0.5 0 0.5 05 0

User.Room333.Node 05 05 0 05 0.5 0 0.5 0.5 0

User_Room334_Node 0.5 0.5 0 Ó.S 05 0 0.5 0.5 0

User.Room301.Node 0.5 0.5 0 0.5 0.5 0 0.5 0.5 0

Сетга1_Ь^е 0.296 0.574 0.13 0.2 0.55 0.25 0.1 0.525 0 375

Таблица 7: Приоритетность модернизации коммутационного оборудования

Наименование узла Низ- Сред- Высо- Низ- Сред- Высо- Низ- Сред- Высо-

кая няя кая кая няя кая кая няя кая

75'/. 75'/. 75'/. 50'/, 50% 50У. 25'/, 25'/. 25'/.

User_iU>om325_Node 05 0.5 0 0.5 0.5 0 0.5 0.5 0

User_Room309_Node 0.5 0.5 0 0.5 0.5 0 0.5 0.5 0

Usei _Room306_Node 0.5 05 0 0.5 0.5 0 Ö.S 0.5 0

User_Room303_Node 0.5 0.5 0 0.5 0.5 0 0.5 0.5 0

User_Room332_Node 0.5 0.5 0 0.5 0.5 0 0.5 0.5 0

User_Room333_Node 0.5 05 0 05 05 0 05 0.5 0

User.Room334.Node 05 05 0 0.5 0.5 0 6.5 0.5 0

User.Room301.Node 0.5 0.5 0 0.5 05 0 05 05 0

Central.Node 0.3 0.575 0.125 02 0.55 0.25 0.1 0.525 Ö.375

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

Зависимость времени оптимизации от размера ВС

45

количестве рабочих сТанцйй

Рис. 7; Зависимость времени оптимизации от размера ВС

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

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

Основные результаты и выводы

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

2 Предложена структура байесовских сетей доверия для оптимизации параметров ВС

3 Разработана САПР ВС, использующая для оптимизации параметров ВС напряду с генетическими алгоритмами аппарат байесовских сетей доверия

4. На основе разработанной САПР ВС показана эффективность использования байесовских сетей доверия при оптимизации параметров ВС

5. Проведены вычислительные эксперименты.

Основные положения и результаты диссертации были опубликованы в следующих работах:

1. Шамшев, A.B. Система автоматизированного проектирования вычислительных сетей с использованием байесовских сетей доверия / А. Б. Шамшев // Научная сессия МИФИ 2003. Сборник научных трудов. - Москва: МИФИ, 2003. - Т. 3 - С. 142 - 143.

2 Шамшев, А. Б. Система автоматизированного проектирования вычислительных сетей с использованием байесовских сетей доверия / А. Б. Шамшев // Москва: ВИНИТИ № 374-В2003 - Дата депонирования: 27.02.03 - С 1-47.

3. Шамшев, А. Б. Система проектирования вычислительных сетей на основании описания бизнес - процессов / А. Б. Шамшев // Межвузовский сборник "Информатика и экономика Ульяновск: УлГТУ, 2003 - С. 41 - 46.

4. Шамшев, А. Б. Использование сетей доверия для моделирования рассуждений проектировщика / А Б. Шамшев // Тезисы докладов 37 научно - технической конференции УлГТУ "Вузовская наука в современных условиях Ульяновск: УлГТУ, 2003. - Часть 2 - С. 10.

5. Shamshev, А. В. Automating of Reasonings of The Designer Using Bayesian Belief Networks. / A. B. Shamshev // Proceedings of the International Conference "Interactive systems: the problems of human - computer interaction Ульяновск-УлГТУ, 2003 - С. 51 - 52.

6. Шамшев, А. Б. Структура системы автоматизированного проектирования вычислительных сетей с использованием байесовских сетей доверия / А. Б Шамшев // Системы искусственного интеллекта и нейроинформатика. Труды международной конференции "Континуальные алгебраические логики, исчисления и нейроинформатика в науке и технике". - Ульяновск: УлГТУ, 2004. - Т. 3 - С. 138 - 139.

7. Свидетельство об отраслевой регистрации разработки № 3709, выданное на САПР ВС "Проектировщик"/ А. Б Шамшев //Отраслевой фонд алгоритмов и программ, 26.08.2004.

8. Шамшев, А. Б. Байесовские сети доверия как модель рассуждений проектировщика / А. Б Шамшев //Тезисы докладов 38 научно - технической конференции УлГТУ "Вузовская наука в современных условиях". - Ульяновск: УлГТУ, 2004. - Часть 1 - С. 98.

9. Шамшев, А. Б. Структура системы автоматизированного проектирования вычислительных сетей с использованием байесовских сетей доверия / А Б. Шамшев // Труды девятой национальной конференции по искусственному интеллекту с международным участием. - Москва: Физматлит, 2004 - Т. 3 -С. 1074 - 1082.

10. Шамшев, А. Б Сравнительная эффективность генетических алгоритмов и байесовских сетей доверия в задачах оптимизации вычислительных сетей / А Б Шамшев // Материалы международной научной конференции "Оптимальные методы решения научных и практических задач" - Таганрог- ТГРУ, 2005 - Часть 2 - С. 86 - 87.

11. Свидетельство об официальной регистрации программы для ЗВМ № 2005610664 от 17 марта 2005 г / А. Б. Шамшев // Москва: Федеральная служба по интеллектуальной собственности, патентам и товарным знакам

12. Шамшев, А. Б. Алгоритм генерации топологии сети на основе потоковых диаг грамм / А. Б. Шамшев //Тезисы докладов 39 научно - технической конференции УлГТУ "Вузовская наука в современных условиях". - Ульяновск: УлГТУ - Часть 1 - С. 98.

13. Прикладные интеллектуальные системы, основанные на мягких вычислениях Под редакцией Н. Г Ярушкиной / М. С. Азов, А. С. Макеев, И. В. Сему-шин, А. С. Селяев, А. А. Стецко, М. С. Сунопля, В. Г. Тронин, М. А. Федорова, А. Б. Шамшев, Т. Р. Юнусов, Н. Г. Ярушкина // Ульяновск: УлГТУ, 2005 - С. 72 - 88.

Подписано в печать 20.04.2006. Формат 60x84/16. Бумага офсетная. Усл. печ. л. 1,40. Тираж 75 экз. Заказ 450

Типография УлГТУ, 432027, г. Ульяновск, ул. Сев. Венед, д. 32

тт

H? " 8 5 4 1

h С

Глава 1 Обзор и сравнительный анализ методов автоматизированного проектирования ВС

1.1 Задача проектирования ВС.

1.2 Выбор средства принятия проектных решений.

1.3 Модели вычислительных сетей.

1.4 Функции режима моделирования при автоматизированном проектировании ВС.

1.5 Обзор существующих средств имитационного моделирования ВС

1.6 Проект NS2/VINT

1.6.1 Архитектура NS2.

1.6.2 Возможности NS

1.6.3 Протоколы, реализованные на уровне ядра NS

1.6.4 Возможность построения САПР на основе NS2.

1.7 Представление знаний и моделирование рассуждений.

1.7.1 Представление знаний.

1.7.2 Формальные модели представления знаний.

1.7.3 Моделирование рассуждений.

1.8 Деревья решений . . .,.

1.8.1 Терминология .;.

1.8.2 Преимущества использования деревьев решений.

1.9 Нечёткие нейронные сети.

1.10 Сети Петри.

1.11 Нечёткие сети Петри

1.12 Байесовские сети доверия.

1.12.1 Виды байесовских сетей доверия.

1.12.2 Скрытая Модель Маркова (СММ).

1.12.3 Области применения байесовских сетей доверия.

1.12.4 Краткий обзор программ для работы с байесовскими сетями доверия.

1.13 Генетические алгоритмы.

1.13.1 Схема генетического алгоритма.

1.13.2 Сходимость ГА.

1.14 Основные трудности при автоматизированном проектировании ВС

1.15 Источники трафика при проектировании ВС.

1.15.1 Измерения ВС.

1.15.2 Функциональные диаграммы.

1.16 Нечёткий вероятностный характер динамики вычислительной сети . 61'

1.17 Постановка задачи.

1.18 Выводы.

Глава 2 Формализированные описания, модели, проектные решения автоматизированного проектирования ВС

2.1 Форма описания производственных процессов

2.1.1 Функциональные определения IDEF.

2.1.2 Стандартные DFD - диаграммы

2.1.3 Обоснование выбора DFD - диаграмм.

2.1.4 Дополненные DFD - диаграммы.

2.2 Модель трафика.

2.3 Байесовские сети как средство моделирования рассуждений с целью оптимизации ВС

2.3.1 Механизм работы байесовских сетей доверия.

2.3.2 Причинно - следственные связи для задачи определение коммутационного оборудования.

2.3.3 Байесовская сеть для определения состава коммутационного оборудования

2.3.4 Оценка размера БСД для определения состава коммутационного оборудования

2.3.5 Причинно - следственные связи для задачи определения пропускной способности каналов ВС.

2.3.6 Байесовская сеть для определения пропускной способности каналов сети

2.3.7 Оценка размера байесовской сети для определения пропускной способности каналов сети.

2.4 Формирование значений матриц условных вероятностей.

2.5 Моделирование маршрутизации

2.6 Матрица интенсивностей взаимодействий.

2.7 Модели сети.

2.7.1 Распараллеливание на основе асинхронного параллелизма

2.7.2 Модель сети для имитационного (динамического) моделирования

2.7.3 Модель сети для статического моделирования.

2.8 Сравнение моделей ВС с существующими аналогами

2.8.1 Статическая модель ВС.

2.8.2 Динамическая модель ВС.

2.9 Адаптация генетического алгоритма для задач проектирования ВС

2.9.1 Генетический алгоритм для оптимизации подключения рабочих станций.

2.9.2 Генетический алгоритм для определения размещения коммутационного оборудования.

2.10 Выводы.:.

Глава 3 Структурно - функциональное решение САПР ВС

3.1 Структура САПР ВС.

3.1.1 DFD - диаграммер.

3.1.2 Модуль построения ВС

3.1.3 Визуальный редактор вычислительной сети.

3.1.4 Модуль статического моделирования вычислительной сети

3.1.5 Модуль динамического моделирования вычислительной сети

3.1.6 Модуль байесовской оптимизации

3.1.7 Модуль генетической оптимизации.

3.2 Реализация представления трафика, операции над нечётким трафиком, форматы входных файлов САПР ВС.

3.3 Реализация байесовских сетей доверия.

3.3.1 Реализация БСД для определения состава коммутационного оборудования

3.3.2 Реализация БСД для определения пропускной способности каналов сети

3.4 Реализация механизма обновления вероятностей в узлах БСД

3.5 Реализация имитационного моделирования.

3.5.1 Классы, использованные в имитационной модели.

3.5.2 Алгоритмы динамического моделирования.

3.6 Реализация статического моделирования.

3.6.1 Классы, использованные в статической модели.

3.6.2 Алгоритм статического моделирования.

3.7 Реализация генетических алгоритмов.

3.7.1 Оптимизация подключения рабочих станций.

3.7.2 Оптимизация размещения коммутационного оборудования

3.8 Выводы.

Глава 4 Вычислительные эксперименты 4.1 Проверка адекватности реализованных в САПР ВС моделей.

4.1.1 Описание ожидаемого и полученного результата.

4.1.2 Описание полученного при помощи САПР ВС результата

4.2 Гипотетические сети и тестовые примеры.

4.2.1 Тестовая сеть с четырьмя рабочими станциями и сервером

4.3 Эксперименты с реальной сетью.

I 4.3.1 Структура и потоки данных в ВС ФНПЦ ОАО НПО Марс

4.4 Условия вычислительных экспериментов.

4.5 Результаты вычислительных экспериментов для исходного варианта

4.6 Сводные таблицы для оптимизированного варианта ВС.

4.7 Сводные таблицы для варианта ВС с утроенным трафиком.

4.8 Сравнение эффективности генетического алгоритма и байесовских сетей доверия.

Создание крупных высокоэффективных систем обработки данных связано с объединением средств вычислительной техники, обслуживающей подразделения предприятий и организаций, с помощью системы передачи данных в единую вычислительную сеть. В настоящее время при проектировании вычислительных сетей активно используются системы автоматизированного проектирования вычислительных сетей (САПР ВС). Так как задача проектирования вычислительной сети обладает большим объёмом и высокой степенью сложности, САПР ВС должна обладать элементами интеллектуальности. Существующие САПР ВС позволяют производить различные операции со структурой вычислительной сети (ВС), оптимизировать различные параметры и проводить моделирование заданных ВС. Но им присущи следующие недостатки: размер передаваемых пользователями данных должен иметь чёткую числовую размерность, построение структуры ВС производится пользователем - экспертом, при этом отсутствует возможность автоматизировать процесс построения структуры ВС, недостаточно развиты механизмы моделирования динамики трафика ВС.

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

Наряду с генетическими методами оптимизации в разработанной САПР ВС применяется аппарат байесовских сетей доверия. Данное решение позволит получать результаты оптимизации, обоснованные знаниями эксперта о структуре решаемой задачи, представленными в виде графа сети доверия и матрицами условных вероятностей узлов сети доверия. В разработанной САПР ВС сети доверия применяются для моделирования рассуждений проектировщика с целью определения состава коммуникационного оборудования и определения пропускной способности каналов ВС. Теоретическое описание механизма работы байесовских сетей доверия приведено в разделе 2.3.1, структура используемых сетей доверия приведена в разделах 2.3.3, 2.3.6, программная реализация сетей доверия приведена в разделе 3.3.

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

Преимуществами использования сетей доверия являются:

• обоснованность результатов моделирования рассуждений знаниями эксперта, представленными как структурой графа сети доверия, так и в форме матриц условных вероятностей в узлах сети доверия;

• скорость получения результата. Преимущества применения аппарата сетей доверия по сравнению с генетическими алгоритмами и ручным перебором вариантов представлены в 4.8;

• результат моделирования рассуждений проектировщика охватывает множество возможных решений и показывает уровень оптимальности каждого решения.

Основными недостатками использования сетей доверия являются:

Необходимость построения сети доверия для каждого варианта ВС

Сложность и длительность процесса заполнения таблиц условных вероятностей

3.8 Выводы

Согласно ГОСТ 34.003 - 90 системой автоматизированного проектирования называется: "Система, состоящая из персонала и комплекса средств автоматизации его деятельности, реализующая информационную технологию выполнения установленных функций". Таким образом, созданный в рамках данной работы программный продукт представляет собой САПР ВС, т.к. имеются все три необходимых компонента.

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

Согласно [1] жизненным циклом изделия называется (ЖЦИ) "совокупность этапов, через которые проходит изделие за время своего существования: маркетинговые исследования, составление технического задания, проектирование, технологическая подготовка производства, изготовление, поставка, эксплуатация, утилизация". Разработанная САПР ВС может применяться на различных этапах жизненного цикла ВС, а именно:

• Составление технического задания. На данном этапе в САПР ВС вводится информация о составе автоматизируемых производственных процессов и структуре проектируемой ВС.

• Проектирование. На данном этапе происходит построение структуры ВС и её оптимизация, определение различных топологических параметров ВС.

• Эксплуатация. САПР ВС позволяет определять узкие места существующей ВС и выяснять последствия расширения всей ВС или отдельных её сегментов.

Глава 4 Вычислительные эксперименты

4.1 Проверка адекватности реализованных в САПР ВС моделей

Для проверки адекватности реализованных моделей проведём эксперимент по статическому и динамическому моделированию тестовой ВС.

Пусть на диаграмме представлены два пользователя: Userl, имеющий 3 рабочих места, и User2, имеющий 2 рабочих места. Также на диаграмме представлена база данных DataBasel. Пользователь Userl передаёт в базу DataBasel документ размером 2 килобайта и получает от базы ответ размером 1 килобайт. Эта задача выполняется в следующие моменты времени: 9:0:0 и 9:0:10. Пользователь User2 передаёт в базу DataBasel документ размером 4 килобайта и получает от базы ответ размером 1 килобайт. Эта задача выполняется в следующие моменты времени: 9:0:5 и 9:0:15.

Рабочие места пользователей сгруппированы в две подсети. База данных находятся на отдельном сервере, подключённом к подсети пользователя Userl. Подсеть пользователя Userl построена на коммутаторе, подсеть пользователя User2 -на концентраторе. Модель ВС приведена на рисунке 4.1.

4.1.1 Описание ожидаемого и полученного результата

Ожидаемый результат статического моделирования представлен в таблице

4.1.

Заключение

В данной главе была продемонстрирована работа САПР ВС "Проектировщик'^ гипотетическими и реальными ВС. Показана эффективность применения БСД в задаче оптимизации коммуникационного оборудования. На примере НПО "Марс"проведение оптимизации с использованием сетей доверия позволило снизить трафик на отдельных каналах в 100 раз. Время проведения байесовской оптимизации несравненно меньше, чем время проведения генетической оптимизации той же ВС. Таким образом, преимуществами использования сетей доверия при решении задач оптимизации являются:

• существенное ускорение и; упрощение процесса оптимизации, сводящееся к установке начальных данных;

• получение ограниченного множества возможных решений с вероятностными оценками;

• обоснованность полученного множества решений как исходными данными, так и мнением эксперта;

Среди недостатков использования сетей доверия можно отметить следующие:

• необходимость построения отдельной сети доверия для каждой задачи оптимизации;

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

• проведение БСД оптимизации требует достаточно большого объёма оперативной памяти и быстродействия ЭВМ, на которой производится оптимизация.

Это связано с необходимость хранить в памяти как структуру БСД, так и матрицы условных вероятностей узлов;

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

В данной работе была продемонстрирована система автоматизированного проектирования вычислительных сетей на основании производственных процессов с использованием байесовских сетей доверия. Данная САПР ВС обладает следующими преимуществами:

• использование дополненных DFD - диаграмм позволяет полнее учитывать особенности автоматизируемых производственных процессов предприятия;

• оптимизация состава коммуникационного оборудования ВС и пропускной способности каналов ВС при помощи БСД позволяет за сравнительно небольшое время получить множество вариантов, обусловленное как структурой ВС, так и знаниями эксперта, представленными в виде графа БСД, оптимизация производится на основании заложенных в дополненной DFD - диаграмме, описывающей производственные процессы, данных;

• динамическое моделирование позволяет определить динамику трафика на каналах сети в режиме, близком к реальному времени

• статическое моделирование показывает максимально возможное значение трафика на каналах ВС.

Среди недостатков разработанной САПР ВС следует отметить следующие:

• использование для описания производственных процессов только дополненных DFD - диаграмм не позволяет полностью описать все особенности автоматизируемых производственных процессов; недостаточная функциональность мастера перехода к структуре ВС не позволяет сразу получить схему ВС, что приводит к необходимости её редактирования; Многопоточность динамического моделирования требует наличия мощного компьютера с большим объёмом оперативной памяти для повышения адекватности результатов; время, занимаемое статическим моделированием, квадратично зависит от размера моделируемой сети.

Таким образом, основными результатами работы являются:

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

Модели рассуждений по выбору коммутационного оборудования и пропускной способности каналов, представляющие собой байесовские сети;

Модификация байесовских сетей доверия, позволяющая использовать нечёткие высказывания в качестве исходных свидетельств. Построенные байесовские сети использовали представление трафика на основе трапециевидных функций принадлежности;

Архитектура интеллектуальной САПР ВС как система взаимодействующих генетических и байесовских компонент.

1. РД-50.1.031-2001. CALS технологии. Терминологический словарь. Часть 1.

2. Тулупьев A. Л. Алгебраические байесовские сети. Логико вероятностый подход к моделированию баз данных с неопределённостью. //Российская акадмия наук, Санкт - Петербургский институт информатики и автоматизации, Санкт - Петербург, 2000 г.

3. Кисляков А. В. , Генетические алгоритмы: операторы скрещивания и мутации./ / Академия ФСБ России, 2001 г.

4. Quinlan J. R. С4.5. Programs for Machine learning. // Morgan Kaufmann Publishers 1993.

5. Шеннон К. Работы по теории информации и кибернетике.// М. Иностранная литература, 1963

6. Коршунов Ю. М. . Математические основы кибернетики.// М. Энергоато-миздат, 1987

7. Информационные системы в экономике. Учебник // Под ред. проф. В. В. Дика. М.: Финансы и статистика, 1996

8. Якубайтис Э. А. Информационные сети и системы // М.: Финансы и статистика, 1996

9. Пирогов В. В. Исследование применимости генетических алгоритмов в автоматизированном проектировании вычислительных сетей и в задачах размещения. Автореферат диссертации на соискание ученой степени кандидата технических наук.// Ульяновск, 2000 г.

10. Мишенин А. И. Теория экономических информационных систем // М.: Финансы и статистика, 1999

11. Экономическая информатика и вычислительная техника. Учебник // Под ред. В. П. Косарева, А. Ю. Королева. М.: Финансы и статистика, 1996

12. Спиридонов И. А. Мировая экономика // М.: ИНФРА М, 1999

13. Марка Д. А., МакГоуэн К. JI. Методология структурного анализа и проектирования SADT.// М.:1993

14. Калянов Г.Н. CASE: структурный системный анализ (автоматизация и применение).// М.: ЛОРИ. 1996

15. Калянов Г.Н., Козлинский А.В., Лебедев В.Н. Сравнение и проблема выбора методов структурного системного анализа // PC WEEK/RE. 1996. N.34 (27 августа)

16. Введение в экспертные системы (URL: http: / / astu.secna.ru / russian / students / personal/22usv / prospec.htm)

17. Базовые понятия искусственного интеллекта ( URL: http://ге-tech.narod.ru/inf/ai/gll.htm)

18. Круглов В. В., Дли М. И., Голунов Р. Ю. Нечёткая логика и искусственные нейронные сети.//Физматлит, 2001 г.

19. Анисимов Н.А. Композициональная метода разработки протоколов на основе сетей Петри. // Диссертация на соискание учёной степени доктора технических наук. Владивосток 1994 г

20. Котов В.Е. Алгебра регулярных сетей Петри. // Кибернетика, 1980, N 5, с.10-18.

21. Котов В.Е. Сети Петри. // М.: Наука, 1984. 160 с

22. Теория вероятностей. Введение (URL: http://www.exponenta.ru/educat/ class / courses/t v/themeO /1. asp)

23. Гурин. С. Параллельное объектно ориентированное программирование в Delphi. URL: http.y/www.tomsk.net/2q/gurin/gala.html

24. Павловский Ю.Н. Имитационные модели и системы. //Москва:ФАЗИС, ВЦ РАН, 2000.-134 с.

25. Ярушкина Н.Г., Наместников А. М. Эффективность генетических алгоритмов для задач автоматизированного проектирования.//Теория и системы управления, №2, 2002 г.

26. Holland Y. Adaptation in Natural and Artificial Systems. // University of Michigan, Press, Ann Arbor,1975.

27. Скурихин A.H. Генетические алгоритмы // Новости искусственного интеллекта. 1995, № 4

28. Официальная страница International Fuzzy Systems Association. URL: http://www.pa.info.mie-u.ac.jp/ furu/ifsa/

29. Шайкин A.H., Егоров А.Ф. Встроенные предикаты в модели нечёткого логического вывода резолюционного типа на базе сетей Петри //Труды конференции "Математические методы в технике и технологиях (ММТТ 16)", СПбГТИ, Санкт - Петербург, 2003 г.

30. Олифер Н.А., Олифер В.Г. Средства анализа и оптимизации локальных сетей.// Центр Информационных Технологий, 1998

31. Лычкина Н.Н. Современные тенденции в имитационном моделировании. Опубликовано в BisComm

32. Частиков А. П., Леднева И. Ю. Использование байесовской сети при разработке экспертных систем с нечёткими знаниями. // Краснодар, КубГТУ, 2003 г.

33. B. Келдыша. Москва, 2001 г.

34. Коновалов С. Разработка имитационной модели сети Ethernet для её представления в сети Internet. URL: www.a-sys.ru/Articles/Article.aspx?ID=:4

35. Ярушкина Н. Г. Нечёткие нейронные сети. Часть 1. // Новости искусственного интеллекта, 2001 г., № 2-3

36. Ярушкина Н. Г. Нечёткие нейронные сети. Часть 2. // Новости искусственного интеллекта, 2001 г., № 4

37. Jensen К. A Brief Introduction to Coloured Petri Nets. Computer Science Department, University of Aarhus Ny Munkegade, Bldg. 540, DK-8000 Aarhus1. C, Denmark

38. Мартынов В. И. Распределение потоков с нечётко заданными интенсивно-стями в сетях с коммутацией каналов. Известия академии наук. //Теория и системы управления, 1999 г., №4, с. 101 110

39. Фурунжиев В. И., Бабушкин Ф. М., Варавко В. В. Применение математических методов и ЭВМ. Практикум. // Высшая школа, 1988

40. Березко М. П., Вишневский В. М., Левнер Е. В., Федотов Е. В. Математические модели исследования алгоритмов маршрутизации в сетях передачи данных. // Информационные процессы, Том 1,№2, 2001, стр. 103—125

41. Horvitz Е., Hovel D., Kadie С. MSBNx: A Component-Centric Toolkit for Modeling and Inference with Bayesian Networks. //MSDN, July 2001

42. Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. // БХВ Петербург, 2003 г., стр. 971 -998

43. Матвеев А. Сетевые нюхачи. URL:http://www.linuxcenter.ru/lib /security/sniffers.phtml

44. Тарнавский Г. А., Шпак С. И. Декомпозиция методов и распараллеливание алгоритмов решения задач аэродинамики и физической газовой динамики: вычислительная система "Поток-3"//Программирование. 2000. №6, стр. 45-57

45. Тарнавский Г. А., Тарнавский А. Г., Вшивков В. А. Параллелизация алгоритмов и кодов вычислительной системы "Поток-3"//Программирование, 2003, №1, 1-20

46. Стерне Т. Учимся моделировать. //Сети, 1998 г. №5. с. 130-135

47. Жожикашвили В. А., Вишневский В. М. Сети массового обслуживания. Теория и применение к сетям ЭВМ. // М.: Радио и связь, 1988. 192 с.

48. Краснов С. В. Автоматизированное проектирование вычислительных сетей промышленных предпритий в условиях нечётко заданного трафика. Автореферат диссертации на соискание учёной степени кандидата технических наук. //Ульяновск, 2001 г.51

49. Quinlan J. R. Programs for Machine learning. //Morgan Kaufmann Publishers 1993.

50. Шеннон К. Работы по теории информации и кибернетике. М. Иностранная литература, 1963

51. Коршунов Ю. М. Математические основы кибернетики. М. Энергоатом-издат, 1987

52. Репозиторий плагинов для использования с NS2.

53. URL:http://www.isi.edu/nsnam/repository/index.html

54. Хоар Ч. Взаимодействующие последовательные процессы.// М. Мир 1989

55. Научная сессия МИФИ-2003. V всероссийская научно техническая конференция Нейроинформатика - 2003: Лекции по нейроинформатике. Часть 1. // М.: МИФИ, 2003. - 188 с.

56. Murphy К. A Brief Introduction to Graphical Models and Bayesian Networks URL: www.cs.berkeley.edu/ murphyk/Bayes/bayes/html

57. Jaakkola Т., Jordan M. I. Variational probabilistic inferenceiand the QMR-DT database. URL: www.cs-structure.inr.ac.ru/cs-bin/findrefs2.py?keyl=385902&skip=0

58. Морозов М.Н. Курс лекций по дисциплине "Системы искусственного интеллекта" Марийский государственный технический университет, Лаборатория систем мультимедиа. URL: http://www.marstu.mari. ru:8101/mmlab/home/AI/index.html

59. Монтегю Р. Семантика модальных и интенсиональных логик.// Под ред. Смирнова В.А. М: "Прогресс", 1981, с. 254-279.

60. Скотт Д. Семантика модальных и интенсиональных логик.// Под ред. Смирнова В.А. М: "Прогресс", 1981, с. 280-317.

61. Крипке С.А. Семантический анализ модальной логики I. Нормальные модальные исчисления высказываний. в кн. Р. Фейс. Модальная логика. // М: "Наука", 1974, с. 254-303

62. Ружа И. Интенсиональная логика без интенсиональных переменных. в кн. Модальные и интенсиональные логики и их применение к проблемам методологии науки. Под ред. Смирнова В.А. // М: "Наука", 1984, с. 220-244

63. Тэис А. и др. Логический подход к искусственному интеллекту. От классической логики к логическому программированию. Пер. с фр.//М.:МИР, 1990

64. Поспелов Д.А. Моделирование рассуждений. Опыт анализа мыслительных актов. // М.: Радио и связь, 1989. 184 с

65. Финн В.К. Интеллектуальные системы: проблемы из развития и социальные последствия. // Будущее искусственного интеллекта. // М.: Наука, 1991. 302 с

66. Гаврилова Т.А., Червинская К.Р. Извлечение и структурирование знаний для экспертных систем. //М., "Радио и связь", 1992

67. Алексеева И.Ю. Человеческое знание и его компьютерный образ. // М.: Наука, 1992

68. Коов М.И., Мацкин В.В. Диалектика социального познания. // М.: Политиздат, 1988

69. Осипов Г. С. Искусственный интеллект: состояние исследования и взгляд в будущее. URL: ai.obrazec.ru/artint.htm

70. Jae Chung, Mark Claypool. NS by Example. URL: http://nile.wpi.edu/NS/

71. Ашманов И. Информация и знания: невидимая грань. URL: http: / /newasp .omskreg. ru/intellect/f5 .htm

72. Гейвин X. Когнитивная психология. //Изд-во Питер, 2003 г.

73. The Network Simulator ns-2: Validation Tests. URL: http: //www.isi.edu/risriam/iis/ns-tests.litrnl

74. Питерсон Дж. Теория сетей Петри и моделирование систем.// М. Мир, 1984.

75. Котов В.Е. Сети Петри.// М.: Наука, 1984.

76. Азов М. С. Автоматизированное топологическое проектирование вычислительных сетей на основе потоковой модели рабочей иагрузки. Автореферат диссертации на соискание учёной степени кандидата технических наук. // Ульяновск, 200G г.

77. Богуславский JI. Б., Дрожинов В. И. Основы построения вычислительных сетей для автоматизированных систем. //М.: Энергоатомиздат, 1990