Название: автоматизированное проектирование вычислительных сетей промышленных предприятий в условияхнечетко заданного трафика(Краснов С. В.)

Жанр: Информационные системы и технологии

Просмотров: 1196


Содержание работы

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

Вторая глава " Модели оптимизации топологии вычислительных сетей в САПР в условиях неопределенности" посвящена изложению моделей методов и алгоритмов автоматизированного проектирования и перепроектирования ВС.При автоматизированном проектировании и перепроектированиии ВС аналитическая  детерминированная  модель  не  применима,  так  как необходимо учесть не только специфику структуры и функционирования ВС,но   и  поведение  людей,  возможности  эволюционного  развития  ВС  во времени. Одним из перспективных направлений для решения возникшей проблемы является новое научное направление - теория возможностей.В диссертации рассматривается и развивается подход к проблеме оптимизации с позиций аксиоматики теории возможностей. Этот подход предложен А.В. Язениным (90-е годы). В рамках этого подхода разработаныметоды решения задач возможностного программирования. Эти методы, к1ассифицируемые как непрямые, состоят в замене исходных задач эквивалентными детерминированными. Язениным А.В. предлагается использование  аппарата  возможностного  программирования  для оптимизации экономических систем. В диссертации обосновывается применение  аппарата  возможностного         программирования         при оптимизации   размещения коммуникационного оборудования в ВС.Рассматриваются два способа представления нечеткости функциями формы:трапециевидные функции;квазивогнутые функции.При трапециевидной функции нечеткое число представляет собой четверку чиселх~ = (m--d-, m-, m+, m++d+)где d-   левый разброс, m-  - левая граница единичной области , m+  -правая граница единичной области, d+ - правый разброс.Представление нечеткого числа с квазивогнутой функцией принадлежности - это двойка чисел (с, σ) , где с - центр колоколообразной фигуры, аσ - ширина фигуры.Иногда  фактор  неполноты  данных  включает  кроме  нечеткости  ивероятность события. Такие величины называют нечеткими случайными величинами. В этом случае первый элемент пары - это нечеткий исход, а второй элемент - значение вероятности - pk  (pk  - вероятность k-ого исхода). Значит представление   одного   значения   нечеткой   случайной   величины при трапециевидной функции принадлежности - пятерка чисел х`= (m--d-, m-, m+, m++d+, pk), а при квазивогнутой - тройка чисел х= (с, σ , pk)Каждая из нечетких величин характеризуется несколькими термами. В случае использования нечетких случайных величин каждый нечеткий терм- исход характеризуется заданной вероятностью.Задача линейного программирования в канонической форме

АХ<В, Х>0, СХ-> min в общем виде сводится к следующему:А~ Х < В~, σ min(C~X))->max,  где А~ , В~ , С~ - нечеткие вектора коэффициентов, искомых величин, ограничений и коэффициентов целевой функции, аσ - степень уверенности в результате.Формулы преобразования нечеткой задачи линейного программирования к детерминированному аналогу имеют вид:

 

 
с трапециевидными функциями принадлежности(1) (2) (3) (4) (5) (6)где i=0,…..m;j=1,…..nДетерминированный аналог:                                                                      (7)Необходимо учесть, что при переводе нечетких данных в детерминированный аналог в 2 раза увеличивается количество строк в матрице и размерность векторов ограничений и коэффициентов целевой функции. При этом количество столбцов в матрице не увеличивается.Приведенная схема возможностного программирования приложена к задаче размещения коммуникационного оборудования. Приложение заключается в построении матриц А~  , X, В~, С~  , задающих структуру ВС и расстояния размещения коммуникационного оборудования.В главе сформулирована постановка задачи для оптимизации размещения коммуникационного оборудования ВС в условиях неопределенности. Для заданных координат расположения рабочих станций множества U найти координаты хj, уj, zj концентраторов (коммутаторов) множества Q, при которых достигается минимум функции F

 

 

 

 
при следующих ограничениях:где U={u1, и2, ..., un}- множество рабочих станций; (8)(9)

{хi   уi   zi}  -  вектор  координат  расположения  рабочих  станций  и,  впространстве;Q={q1, q2,...,qm}   -            множество     концентраторов        (коммутаторов),определенным образом соединенных друг с другом;каждая  рабочая  станция  ui   связана  только  с  одним концентратором(коммутатором) qj.количество рабочих станций, подключаемых к одному концентратору(коммутатору), ограничено его характеристиками;b - максимально возможная длина кабеля, соединяющего рабочую станцию с концентратором (коммутатором);Н = ||hij|| - матрица связности между концентраторами (коммутаторами) и углами, элементы которой характеризуют соответствующий канал связи, если таковой имеется (в противном случае hij== 0);G- стоимость коммуникационного оборудования в ВС.Решение задачи возможностного программирования позволяет определить "начальные" координаты.Предложен            следующий    алгоритм        оптимального            размещениякоммуникационных устройств в условиях неопределенности.Приведем описание алгоритма.Шаг 1. Провести разбиение узлов по группам с учетом технических возможностей  коммуникационных  устройств  и  уточнить  матрицу связанности Н.Шаг  2.  Перевести  нечеткие  значения  исходных  данных  в  четкие,используя соответствующие формулы, если нечеткие числа представлены трапециевидными функциями принадлежности, нечеткими исходами с заданной вероятностью и трапециевидными функциями принадлежности или квазивогнутыми функциями принадлежности. Решить задачу линейного программирования классическими методами.Шаг            3.         Выбрать         начальные      координаты   хj0,      уj0,      zj0концентраторов(коммутаторов)  в  "центре  тяжести"  тех  рабочих  станций,которые имеют связь с концентратором (коммутатором) qj, по формуле (для каждой координаты)

где nj - количество рабочих станций, подключенных к j-му концентратору; хi, уi, zi - координаты i-й рабочей станции, которая подключена к j-му концентратору.Шаг 4. Определить значение целевой функции F=?Шаг 5. Изменить значение координаты хj.Величина шага выбирается такой, чтобы обеспечить минимум функцииF при движении по данной переменной х.

 

 
Процесс выбора величины шага сводится к последовательному изменению значения хjЗначение δхj, определяется с учетом максимально возможных длин канала связи.На каждом (η+1)-м шаге подсчитывается значение функции Fη+1(xj), которое сравнивается со значением Fη(xj). При выполнении условия Fη+1(xj)< Fη(xj) процесс выбора шага прекращается. В качестве нового значения переменной хj, принимается значение хj(η).

 

 
Процесс минимизации заканчивается при выполнении условиягде β - заданная точность получаемых результатов.Шаг 6. Выполнить шаг 5 для yj.Шаг 7. Выполнить шаг 5 для zj.Шаг 8. Сохранить найденные значения хj, уj, zj.Шаг 9. Конец.В ходе проектирования сети, необходимо определиться какой вид коммуникационного        оборудования        следует        установить.        Видкоммуникационного  оборудования  значительно  влияет  на  загруженностьканала связи. Каждый канал k характеризуется пропускной способностью - реальной Рk  и максимальной Рmaxk  (бит/сек). Интенсивность взаимодействия (передачи сообщений) любой пары узлов - это величина Вij (бит/сек). Величина Вij измеряется в течении длительного промежутка времени Т и усредняется. Усреднение может быть представлено вычислением среднего значения Вijср или построением на основе гистограммы распределения вероятностей или построением функции принадлежности на основе распределения возможностей. Суммарный трафик, приходящийся на канал связи, зависит от типа канала. Будем рассматривать только каналы типа<коммутатор/концёнтратор>- <коммутатор/концентратор>.Тогда можно выделить следующие подвиды каналов:<коммутатор > ——<коммутатор ><концентратор> ——< концентратор><коммутатор > ——< концентратор>Суммарный трафик выражается по-разному для 3-х подвидов каналов связи. Суммарный трафик канала типа <коммутатор > —— <коммутатор > может быть представлен как

 

 
(10) где множество вершин Ml и множество вершин М2 - это множества узлов по одну и другую стороны от канала связи <коммутатор > —— <коммутатор>.Суммарный трафик канала <концентратор> —— < концентратор> измеряется по-другому, так как канал образованный концентраторами образует общую магистраль                                                                    (11)Суммарный трафик канала <концентратор> —— <коммутатор> может быть вычислен следующим образом                                                                      (12)Интенсивности взаимодействия рабочих станций ВС, величины Вij могут быть охарактеризованы как нечеткие, так как измерения могут выявить лишь интервал с распределением возможности степени достоверности вычисленного суммарного трафика. Такие величины можно представить с помощью трапециевидных или колоколообразных (в виде кривой Гаусса) функций распределения возможностей. Реальные пропускные способности каналов связи также нечеткие величины, то есть в теоретическом плане сравнение значений пропускных способностей и суммарного трафика - это сравнение двух нечетких интервалов. Поэтому, задача выбора коммуникационного  оборудования  ВС  при  нечетких  исходных  данных может быть сформулирована следующим образом:

 

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

коммутационных модулей и уровень узлов.(рис. 1) Параметры сети, закладываемые в программу: количество коммутационных модулей; количество рабочих станций;топология сети (описание коммутационных модулей):номер коммутационного модуля;количество подключенных к нему станций (узлов сети);тип модуля (коммутатор или концентратор);«география» сети (описание координат узлов сети):номера рабочих станций;координаты узла на плоскости;

 

 
матрица интенсивностей взаимодействия узлов сети.Рис. 1. Вариант структуры проектируемой сети.Интенсивность  взаимодействия  узлов  задается  с  учетом  нечеткого представления. В данном случае применены определения «очень низкая»,«низкая», «средняя», «высокая», «очень высокая». Перед началом работы самого алгоритма закладываются функции принадлежности, соответствующие этим определениям. Перевод этих значений в четкие осуществляется  выбором  представителя    из    функции    принадлежности.Программа  написана  с использованием программного пакета Borland Delphi4.      Программа   позволяет   вводить   данные   о   вычислительной   сети,   и оптимизировать вычислительную сеть по направлениям уменьшения суммарного  трафика,  уменьшение  суммарной  длины  сетевого  кабеля  и выбора коммуникационного оборудования.Четвертая             глава   посвящена      результатам    экспериментальных исследований  в  области  оптимизации  топологии  вычислительных  сетейразличного уровня сложности с помощью разработанной программы.Для         проведения    экспериментов          по        оптимизации графика          в вычислительной сети были выбраны различные типы гипотетических сетей:«малая сеть», включающая в себя до 50 узлов; «средняя сеть», включающая в себя от 50 до 350 узлов; «крупная сеть», включающая в себя от 350 до 1000 узлов.Для     проведения    экспериментов          производилось          увеличение интенсивности  каждого  узла  с  каждым  узлом, то  есть сначала  первого  с

 

 
остальными, затем второго с остальными, далее третьего с остальными и так далее.   После   каждого   изменения   интенсивности   получаем   суммарный трафик Pk1. После проведения оптимизации получим суммарный трафик Р k2.Рис. 2. График изменения суммарного трафика "малой" сети при изменении интенсивности узлов.В результате проведенных исследований по изменению трафика получаем результаты, сведенные в таблицу. По результатам таблицы составляем   график   изменения   суммарного   трафика   на   магистральных каналах сети с увеличением интенсивности взаимодействия узлов при "ручном" проектировании сети и с использованием алгоритма оптимизации сетевого  трафика  (рис.  2).  Эксперименты  по  размещению коммуникационного оборудования проводились на первом этапе с использованием известных математических методов оптимизации — линейного и нелинейного программирования, интегрированные в пакет программ   Quatropro.   На   втором   этапе   эксперименты   по   размещению

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