Содержание к диссертации
Введение
1. Обоснование необходимости оптимизации топологической структуры локальных вычислительных сетей информационных систем 10
1.1. Анализ архитектуры информационных систем масштаба предприятия на базе локальных вычислительных сетей 1 0
1.2. Анализ существующих постановок и методов решения задачи оптимизации топологии вычислительных сетей распределенных информационных систем 25
1.3. Обобщенная постановка задачи оптимизации топологической структуры локальных вычислительных сетей информационных систем 41
Выводы 45
2. Модели оптимизации топологической структуры однородных лвс информационных систем
2.1. Постановка задачи оптимизации топологической структуры однородных ЛВС информационных систем на базе концентраторов 47
2.2. Алгоритмы решения задачи оптимизации топологической структуры ЛВС информационных систем на базе концентраторов и их анализ 50
2.3 Постановка задачи оптимизации топологической структуры однородных ЛВС информационных систем на базе коммутаторов 79
2.4 Алгоритмы решения задачи оптимизации топологической структуры ЛВС корпоративных информационных систем на базе коммутаторов и их анализ 82
Выводы
3. Модели оптимизации топологической структуры неоднородных лвс информационных систем
3.1. Постановка задачи оптимизации топологической структуры неоднородных звездообразных ЛВС 95
3.2. Анализ существующих постановок задачи оптимизации неоднородных ЛВС и выбор метода решения 99
3.3. Генетический алгоритм оптимизации топологической структуры неоднородных звездообразных ЛВС 103
3.4. Экспериментальное исследование модифицированного генетического алгоритма синтеза топологической структуры ЛВСИС 124
Выводы 133
4. Программная реализация алгоритмов оптимизации и их практическое применение для проектирования топологической структуры ЛВСИС 134
4.1. Реализация средств оптимизации топологической структуры ЛВС ИС в САПР "Модель" 134
4.2. Оптимизация топологической структуры ЛВС корпоративной информационной системы Шахтинских межрайонных электрических сетей 144
4.3. Оптимизация топологической структуры ЛВС информационной системы Шахтинского филиала гуманитаргого институра г.Москва 159
Заключение 174
Литература
- Анализ существующих постановок и методов решения задачи оптимизации топологии вычислительных сетей распределенных информационных систем
- Алгоритмы решения задачи оптимизации топологической структуры ЛВС информационных систем на базе концентраторов и их анализ
- Генетический алгоритм оптимизации топологической структуры неоднородных звездообразных ЛВС
- Оптимизация топологической структуры ЛВС корпоративной информационной системы Шахтинских межрайонных электрических сетей
Анализ существующих постановок и методов решения задачи оптимизации топологии вычислительных сетей распределенных информационных систем
В настоящее время происходят существенные изменения в деловой среде в результате слияния и появления большого числа новых информационных технологий, характеризующиеся переходом к широкому внедрению информационных систем (ИС) масштаба предприятия, которые представляют собой совокупность взаимодействующих территориально распределенных локальных подсистем, включающих программные, информационные и технические компоненты, и позволяющих реализовать автономную и распределенную обработку данных. На сегодняшний день существует ряд подходов к классификации подобных систем [29],[24], [38],[9]. В соответствии с существующей на данный момент времени классификацией информационных систем для предприятий можно выделить локальные системы, малые интегрированные системы, средние интегрированные системы и крупные интегрированные системы управления предприятием. К локальным системам относятся: Представителями малых интегрированных систем являются: Concorde XAL, Platinum PRO/MIS, БОСС-Корпорация, Галактика и другие. Средние интегрированные включают системы: JD Edwards {Robertson & Blums), MFG-Pro {QAD/BMS), SyteLine (COKAIL SYMIX). В качестве представителей крупных интегрированных систем наиболее значительными являются: SAP/R3 {SAP AG), Baan {Baari), BPCS {ITS/SSA), Oracle Applications {Oracle) iRenaissance. По функциональному назначению системы разделяются на две группы: финансово-управленческие и производственные системы.
Финансово-управленческие системы включают подклассы локальных и малых интегрированных систем. Они предназначены для ведения учета по одному или нескольким направлениям (бухгалтерия, сбыт, склады, учет кадров и т.д.). Системы этой группы могут использоваться на любом предприятии, где необходимо управление финансовыми потоками и автоматизация учетных функций. Для данной группы характерна универсальность, однако для обеспечения отраслевых проблем предлагаются специализированные решения, например, особые способы начисления налогов или управление персоналом с учетом специфики регионов. Финансово-управленческие системы позволяют выполнять адаптацию своих функций к требованиям конкретного предприятия, что может обеспечиваться при помощи "конструкторов", устанавливающих связи между таблицами баз данных или отдельными модулями. Реализация финансово-управленческих систем может быть выполнена на персональных компьютерах в составе локальных вычислительных сетей под управлением операционных систем Novell Netware или Windows NT. Они опираются на технологию выделенного сервера базы данных, которая, в зависимости от масштаба системы, характеризуется высокой либо низкой загрузкой сетевых каналов для передачи данных между сервером и рабочими станциями.
Производственные системы включают подклассы средних и крупных интегрированных программно-технических продуктов. Они, в первую очередь, предназначены для управления и планирования производственного процесса и покрывают потребности всего предприятия. Учетные функции выполняют вспомогательную роль и являются интегрированными в систему таким образом, что информация в бухгалтерские, складские и кадровые комплексы поступает автоматически из других подсистем. Основными механизмами управления являются планирование и оптимальное управление производственным процессом, а не учет количества счетов-фактур за период. Специализация данных систем отражается в наборе функций и в существовании бизнес-моделей данного типа производства и организации производственного процесса.
По типу производства бизнес-модели ориентированы на серийное сборочное (электроника, машиностроение), мелкосерийное и опытное (авиация, тяжелое машиностроение), дискретное (металлургия, химия, упаковка) а также непрерывное (топливно-энергетическая промышленность) производство. По типу организации производственного процесса бизнес-модели реализуют соответствующую специфику. Например, для дискретного типа бизнес-модели реализуют циклическое повторное производство (планирование выполняется на определенный срок - квартал, месяц, неделя), изготовление на заказ (планирование только при поступлении заказа), разработка на заказ (проектирование каждого нового заказа с последующим производством), изготовление на склад, а также модели смешанного производства.
В качестве основных компонентов выделены следующие бизнес-модели: управление финансами, управление персоналом, управление запасами, управление снабжением, управление сбытом, управление производством, техническое обслуживание, управление проектами, работа с торговым оборудованием.
Алгоритмы решения задачи оптимизации топологической структуры ЛВС информационных систем на базе концентраторов и их анализ
Таким образом, точных методов решения задач, входящих в первую группу, разработано ограниченное число. В силу того, что при подключении абонента по радиальной схеме происходила неполная загрузка канала, большее внимание уделялось моделям синтеза иерархических структур. Известны точные решения для ряда специальных задач, использующие метод ветвей и границ, а также эвристические алгоритмы.
Вторая группа моделей ориентирована на класс абонентских СПД, структура которых представляет собой дерево или совокупность деревьев с корнями, соответствующими местам размещения ВЦ. Абонентские пункты для повышения коэффициента использования канала подключаются друг к другу по многопунктовой схеме [37] с использованием мультиплексоров. Задача синтеза абонентской СПД в классе древовидных сетей формулируется следующим образом [16]. Заданы множество абонентов Х={ХІ} с координатами {8t щ} и объемами информации hh а также места размещения ВЦ {yj и привязки абонентов к ВЦ X , j = l,m. Известны приведенные затраты на передачу информации от пункта / к пункту у Ср = C(h.j,l ).
Требуется синтезировать древовидную структуру абонентской СПД минимальной стоимости при ограничениях на суммарный трафик в каждой ветви: fy dmax где dmax - пропускная способность многопунктовой линии связи; fy определяется как сумма информационных потоков от всех узлов, предшествующих узлу і на путях от концевых вершин к корню дерева, и потока hi, определяемого абонентом я,-.
Другой, характерной в этой группе постановкой, является задача, представленная в [23]: имеется N - пунктов, заданных декартовыми координатами (xbyi), i-1-N. Связь пунктов между собой задана матрицей тяготения \XJ,i,j = l,N. Требуется построить на заданных точках двухуровневую сеть минимальной стоимости, то есть, выбрать некоторое число L пунктов из заданных пунктов к одному из оставшихся УК. Между УК строится сеть полносвязной структуры. Находящийся в пункте размещения УК абонент привязывается только к этому узлу, а стоимость привязки равна нулю. Стоимость сети определяется выражением W=Si+S2+S3, где -стоимость абонентских линий связи; -стоимость узлов коммутации; -стоимость межцентровых линий связи. Заданы зависимость стоимости УК от производительности Л Сук(А) и также функция стоимости линии связи от потока Я по ней и длины г СКС(Х,г). Оценкой сверху X при Хо Х, где XQ необходимого числа каналов является величина Х0 значение N в качестве узлов коммутации (УК) и привязать каждый из оставшихся N-L - нагрузки, для обслуживания которой с заданным качеством достаточно одного канала.
В литературе описываются алгоритмы проектирования топологической структуры сетей связи, относящиеся к классу эвристических, наиболее характерной особенностью которых является поиск какого-либо допустимого решения задачи, затем это допустимое решение итерационно улучшается путем просмотра «окрестности» вектора значений переменных, определенных для начального допустимого решения [77]. В основе большинства алгоритмов этой группы лежат принципиальные положения, сформулированные Р. Примом: всякая изолированная вершина сети соединяется с ближайшим соседом, всякий изолированный фрагмент соединяется с соседом кратчайшей ветвью. При оптимизации многопунктовых соединений обычно предполагается, что имеется п терминалов, расположенных в заданных точках, и единственный центральный узел, положение которого также известно. Известны стоимости соединений между терминалами и между терминалом и центральным узлом. Задача состоит в построении дерева минимальной стоимости. Это известная задача о минимальном связывающем дереве (МСД), для построения которого существуют эффективные алгоритмы[25,36]. В связи с тем, что пропускная способность ветви, соединяющей группу вершин с центром, может оказаться недостаточной для передачи суммарной нагрузки, создаваемой всеми терминалами, включенными в линию, вводится ограничение на число терминалов, а также на нагрузку в каждой из многопунктовых линий. Полученная при этом топология представляет собой совокупность многопунктовых линий (МПЛ). Для построения МСД и МГОІ, как правило, используются следующие алгоритмы [23,30]. Алгоритм Прима. Из множества вершин, включая центральную, выбирается одна вершина, которая соединяется ребром с ближайшей к ней вершиной. Далее на каждом шаге к дереву присоединяется вершина, расстояние от которой до какой-либо точки дерева является наименьшим.
Алгоритм Краскала. Из множества ребер полного графа, построенного на заданном множестве вершин, в порядке увеличения длины выбираются ребра и включаются в МСД. При этом включаемое ребро не должно образовывать цикла с ранее выбранными ребрами.
Алгоритм Исау-Вильямса. Заданная радиальная структура преобразуется следующим образом: для каждой пары вершин вычисляется экономия от замены ребра, соединяющего одну из этих вершин с центром на ребро между этими вершинами; для пары вершин с максимальной экономией производится замена, если выполняется многопунктовое ограничение.
Генетический алгоритм оптимизации топологической структуры неоднородных звездообразных ЛВС
В качестве исходных данных используются (1),(2),(4), ограничениями являются qi , дз и q4. Требуется минимизировать следующую функцию: и т CjZj - min, где С С] +±YlfL .
На концептуальном уровне эта задача является задачей о покрытии, отличающаяся наличием дополнительного ограничения #4- На концептуальном уровне оно определяет максимальное использовать термин "покрытие" вследствие концептуальной близости этого понятия с целевой функцией поставленной задачи. Ограничение qj учитывается при задании матрицы коэффициентов покрытия ягу и задается следующим образом: 1, если і-я строка может быть покрыта -м концентратором; аи = \ [ О-в противном случае, где і-я строка может быть покрыта у -м концентратором, если Іу Ґаг, где Гаг -варьируемая величина, первоначально Гаг - Lmax; Яу=0 - в противном случае. п a&-z- l, i = \,m;j = \,n; CJ 0. Необходимо, чтобы каждая из т - строк матрицы количество ребер графа, которое может быть покрыто одной вершиной. Будем \\ау\\ была покрыта, по крайней мере, одним из п - столбцов (ограничение q3). Стоимость С, включает два компонента: стоимость оборудования места для размещения концентратора и среднюю стоимость подключения к концентратору в этом месте рабочих станций.
Для учета первого аспекта, определенного в предыдущем подразделе, при выборе количества и размещения концентраторов предлагается провести решение задачи итерационно с уменьшением на каждой итерации значения Гаг. Итерации выполняются до тех пор, пока не останется непокрытая вершина. Учитывается также максимальное количество ребер графа, которое может быть покрыто одной вершиной, что позволяет принимать во внимание второй аспект.
Задача о покрытии является задачей целочисленного программирования с булевыми переменными и может быть решена общими методами целочисленного программирования. Для известных алгоритмов решения универсальных переборных задач время счета растет экспоненциально с ростом размерности задачи [36,42]. Однако характер экспоненциальной зависимости существенно зависит от особенностей каждого алгоритма. Особенности поставленной задачи позволяют при применении метода ветвей и границ упростить процедуру вычисления нижней оценки решения путем использования двойственной задачи [2]. Для этого условие целочисленности Zje{0;l},j = \,n заменяется условием 0 zy l, у = 1,п. По отношению к поставленной задаче о покрытии двойственная задача имеет вид : Z = max jT v. при ограничениях: т а . С,., j = \,n; v—C0ij Q, i = l,m,j = \,n, где v, и %- переменные двойственной задачи.
Отличительной особенностью алгоритма является то, что на каждой итерации необходимо упорядочить строки матрицы коэффициентов покрытия в порядке возрастания сумм по строкам и выбирать первые NHp строк. Это позволит учесть ограничение q .
Задача решается итерационно при уменьшении значения Гаг до тех пор, пока не останется одна непокрытая вершина.
Для описания алгоритма вводятся следующие обозначения: G - множество индексов концентраторов, включенных в покрытие. Верхний индекс показывает номер итерации, а нижний индекс определяет вариант покрытия последнего покрываемого элемента, k = l,m, t = l,y, гдеу-количество вершин на к-м уровне ветвлений определяемое количеством концентраторов, которые могут покрывать рассматриваемую на к-й итерации рабочую станцию. U - множество индексов переменных концентраторов. S(Gf) - множество индексов концентраторов, включенных в исследуемую ветвь дерева возможных вариантов во множество G и покрывающих рабочие станции с индексами i = \,k, где к = \,т, t = l,y -определяет вариант покрытия к-п рабочей станции, где у - количество вершин на к-м уровне ветвлений определяется количеством концентраторов, которые могут покрывать к-ю рабочую станцию.
D(G )=U\S(Gj) - множество индексов концентраторов, не включенных в SfGfj. I - множество индексов рабочих станций, которые необходимо покрыть. l(G ) - множество индексов рабочих станций, которые покрываются концентраторами, индексы которых включены в S(Gf J. N(Gf )= I\l(G ) - множество индексов рабочих станций, которые не покрыты. B/(Gfc)={/ I %=1 7-1»л} - множество индексов концентраторов, которые могут покрывать і - ю рабочую станцию для множества G . A/(Gf ) {i I Щ—h i l,m} - множество индексов переменных, которые покрываютсяу -м концентратором для множества G .
Оптимизация топологической структуры ЛВС корпоративной информационной системы Шахтинских межрайонных электрических сетей
Исходя из того, что все переменные задачи являются булевыми, количество вариантов решений можно определить как V = 2л "я+4хл.
Решение задачи в такой постановке с использованием методов на основе перебора вариантов затруднено по причине «проклятия размерности». Известные подходы [30,36] к решению подобных задач заключаются в следующем: а) вводятся допущения в постановку задачи в целях её упрощения, уменьшения размерности и сведения к известным задачам комбинаторной оптимизации; б) выполняется разбиение задачи на этапы и для каждого этапа определяются частные подзадачи и целевые функции. Решение может быть получено в результате итерационного выполнения этапов и решения частных подзадач на каждом этапе.
Задачи такого типа рассматривались в работе [9]. Первоначально задача разбивается на три этапа. Для решения используется подход на основе метода ветвей и границ с применением трех стратегий ветвлений. На первом этапе применяется стратегия, согласно которой определяется подмножество используемых мест размещения пассивных концентраторов; на втором этапе определяется подмножество мест размещения активных концентраторов; на третьем этапе выполняется подключение рабочих станций к найденным местам подключения концентраторов. Требования к пропускной способности для этого метода не учитываются по причине значительного усложнения задачи. С целью учета интенсивности нагрузки на среду передачи информации в [9] предложен эвристический алгоритм балансировки нагрузки в топологической структуре, однако он применяется к элементарным топологическим структурам типа Ethernet-шша и Arcnet-итш, которые представляют минимальный набор технических средств, обеспечивающий функционирование ЛВС выбранного стандарта и предназначенный для многократного применения в качестве составного элемента при компоновке ЛВС в целом. Полученные в результате таких подходов решения являются приближенными, а процесс получения решения - достаточно трудоёмким и длительным.
Другим подходом является применение современных алгоритмов поиска, в частности генетических алгоритмов (ГА)[22,26,31,39], отжига, а также нейронных сетей.
В основе нейросетей лежат предложенные МакКаллоком и Питтсом в 1943 году идеи использования бинарного порогового элемента в качестве модели искусственного нейрона. Этот математический нейрон вычисляет взвешенную сумму п входных сигналов Хр j = l,n и формирует на выходе сигнал величины 1, если эта сумма превышает определенный порог и, и 0 - в противном случае. Порог и рассматривается как весовой коэффициент, связанный с постоянным входом. Нейросеть может рассматриваться как направленный граф с взвешенными связями, узлами которого являются искусственные нейроны. Отличительной особенностью нейросетей является способность обучения [88], заключающаяся в настройке архитектуры сети и весов связей для эффективного выполнения поставленной задачи. Обычно нейронная сеть должна настроить веса связей по имеющейся обучающей выборке. Функционирование сети улучшается по мере итеративной настройки весовых коэффициентов. Для конструирования процесса обучения, прежде всего, необходимо иметь модель внешней среды, в которой функционирует нейронная сеть. Для применения нейросетей к решению задачи оптимизации топологической структуры ЛВС, при формировании обучающей выборки, необходимо, с одной стороны, включить в неё достаточное количество "хороших" решений, а с другой стороны, охватить различные варианты реализации, причем невозможно определить, как сеть будет реагировать на данные, не включенные в обучающую выборку (какова способность сети к обобщению), и какой размер обучающей выборки необходим для достижения "хорошей" способности сети к обобщению.
Идея ГА заимствована у живой природы и состоит в организации эволюционного процесса, в результате которого синтезируется оптимальное или близкое к оптимальному решение сложной комбинаторной задачи. При разработке ГА необходимо установить законы эволюции таким образом, чтобы за приемлемое время получить эффективное решение. Впервые эти идеи были применены к решению оптимизационных задач в середине 70-х годов [80,40]. На сегодняшний день ГА успешно применяются при решении многих Л/Р-трудных задач [15,27] и в практических приложениях, где математические модели имеют сложную структуру и использование стандартных методов типа ветвей и границ, динамического или линейного программирования затруднено. Современный ГА представляет собой адаптивный поисковый метод, применимый к широкому классу оптимизационных задач. Характерной особенностью ГА является возможность использования целевой функции при оптимизации [27], а не её оценок или приближений, так как ГА не предъявляет требований к виду целевой функции и ограничений. В процессе работы ГА обрабатывает множества альтернативных решений, организуя поиск в направлении перспективных с точки зрения используемой целевой функции и ограничений вариантов решений.
