Навигация
Значения vi необходимо изменять не всегда, например, в алгоритме Краскала
66737
знаков
3
таблицы
15
изображений
4. Значения vi необходимо изменять не всегда, например, в алгоритме Краскала.
Связь между унифицированным алгоритмом и частными алгоритмами синтеза КСД отображается в таблице 1, где указаны решающие правила для вычисления начальных весов vi и их коррекция при вводе связи (i, j). Меняя правило задания и коррекции весов vi, можно получить любой из алгоритмов, причем одни правила во многих случаях дают лучшие результаты, чем другие. Однако пока не найдено такое универсальное правило, которое бы давало наилучшие результаты во всех случаях. Поэтому применяют параметрический способ определения весов. Рассмотрим один из таких способов. Запишем веса узлов в виде
vt= a(bci0 + (l — b)ci2),
где ci0, ci2 — стоимости соединения терминала i с центральным узлом и с его ближайшим соседним терминалом соответственно; а и b — некоторые константы, причем а ≥ 0, 0 ≤ b ≤ 1. При а = 0 получаем алгоритм Краскала; при а = b = 1 — алгоритм Исау — Вильямса; при а = 1, b = 0 — алгоритм Фогеля. Наконец, придавая а и b некоторые промежуточные значения, можем получить одновременно свойства всех вышеперечисленных алгоритмов.
На практике обычно параметрам а и b придают некоторые начальные значения и затем, варьируя их по очереди и оценивая получаемые результаты, последовательно приближаются к наилучшему. Такой способ позволяет получить результаты на 1—5 % лучше, чем при использовании алгоритмов Исау— Вильямса и Фогеля. Указанный способ параметризации можно применять для одновременного решения задач группирования и размещения терминалов, если в выражении для vi под сi0 понимать стоимость соединения терминала i с ближайшим центральным узлом. При этом никакого предварительного разбиения терминалов на группы не производится, а оно выполняется автоматически в процессе работы алгоритма.
Рассмотрим эффективность реализации унифицированного алгоритма синтеза КСД. Сложность алгоритма — время вычислений и необходимый объем памяти — зависит от размерности графа N. В общем случае граф должен быть полным, что требует просмотра всех пар узлов. Однако при большом количестве терминалов можно без значительного снижения точности результатов решать задачу с помощью разреженного графа, в котором каждый терминал связан лишь с некоторым ограниченным числом соседних терминалов. Например, в сети с 40 узлами достаточно рассматривать соединения каждого терминала с пятью соседними. Дальнейшее увеличение числа терминалов К лишь незначительно улучшает результаты. Для сети терминалов, однородно распределенных вокруг центрального узла, можно игнорировать около 75 % возможных соединений. Для быстрой оценки приближенного значения К всю область, содержащую терминалы, разбивают на прямоугольники, в пределах каждого из которых находят К ближайших соседей заданного терминала. Благодаря такому правилу число операций для повторного вычисления Eij при включении новой ветви в дерево можно снизить с N (N — 1)/2 до N х К. Кроме того, учитывая, что Еij =vi-cij, где cij — константа, пересчет Еij можно свести к пересчету vi, т. е. вместо N х К повторных вычислений Eij достаточно пересчитать N раз значение vi.
В общем случае сложность алгоритма оценивается выражением: AN2 + BKN + CKN log2K, где А ,В и С — константы. При этом предполагается, что программа обеспечивает возможность реализации любого правила v. Однако, если правило v таково, что не требуется пересчет vi для каждого терминала, то членом AN2 можно пренебречь. Для многих практических целей сложность алгоритма имеет вид BKN + CKN log2К. Время работы ЭВМ и требуемый объем оперативной памяти при реализации алгоритма экспериментально оценены в сетях, содержащих 20, 40, 60, 80, 120, 200 узлов при учете только пяти соседних терминалов, использовании правила изменения v по алгоритму Исау — Вильямса и суммарном графике в ветви, ограниченном значением Н ≤ N/4.
Результаты экспериментов показали, что зависимость логарифма времени работы ЭВМ от логарифма числа терминалов имеет линейный характер с наклоном кривой, который свидетельствует о квадратичной зависимости вычислительной сложности унифицированного алгоритма от размерности задачи N. В результате исследований выявлено, что время решения задачи почти не изменяется при переходе от одного правила v к другому и при изменении ограничений, в то же время оно сильно зависит от числа соседних терминалов, подключаемых к данному (т. е. числа новых линий, подключаемых к дереву). Зависимость времени работы унифицированного алгоритма синтеза КСД от числа соседних терминалов для сети с 40 терминалами приведена в таблице 2.2.
Таблица 2.2 – Зависимость времени работы терминала
| Число соседних терминалов, К | Время работы алгоритма, мин | Относительная стоимость связи |
| 1 | 0,434 | 7,77 |
| 2 | 0,491 | 5,26 |
| 3 | 0,522 | 4,54 |
| 4 | 0,557 | 4,50 |
| 5 | 0,589 | 4,48 |
| 8 | 0,691 | 4,45 |
| 10 | 0,767 | 4,45 |
| 15 | 0.985 | 4,45 |
| 20 | 1,240 | 4,45 |
| 25 | 1,503 | 4,45 |
| 30 | 1,767 | 4,45 |
| 39 | 2,245 | 4,45 |
В модели многопунктовой ЛС, используемой как в унифицированном алгоритме Кершенбаума — Чжоу, так и в алгоритмах Исау — Вильямса, Мартина, Краскала и других, учитывают следующее допущение: при подключении очередного АП к многопунктовой сети стоимость канала передачи данных между узлами i и j 
не зависит от объема информации hi, при этом вводится лишь одно ограничение: fij ≤ d, где fij— суммарный поток (трафик) в любой ветви (i, j). Такое допущение справедливо в случае, когда по всей длине многопунктовой связи ее пропускная способность d остается постоянной. Вместе с тем использование модемов, работающих с различными скоростями передачи данных, позволяет организовать многопунктовые связи, в которых пропускная способность постепенно изменяется по мере приближения линии к центру обработки данных.
Таким образом, для многопунктовых связей с изменяемой (регулируемой) пропускной способностью традиционно используемое допущение 
(hi) = const оказывается неверным, что исключает возможность использования унифицированного алгоритма Кершенбаума—Чжоу.
Для решения задачи синтеза структуры древовидной сети при переменной скорости передачи данных предложен алгоритм D-структур. Важной особенностью алгоритма D-структур является то, что на шаге 1 определяются оптимальные места размещения РЦ и радиальная структура СДО, а затем она преобразуется в древовидную структуру. Рассмотрим описание алгоритма. Введем следующие обозначения: Хi, Xj — подграфы графа X, Xi = {xi*, xi2, ... , Xin}; xi* — направляющая вершина подграфа Хi т. е. его концевая вершина на данной итерации, куда сходятся информационные потоки из всех хЄХi. Будем предполагать, что подключить Xi к Xj можно введением ветви (i*, j), исходящей только из направляющей вершины xi*, причем хjЄХj, и на Xj ограничения не накладываются; Hi — суммарный объем ИВР подграфа Xi, 
,hij — суммарный поток в ветви (i, j); С(Хi)— стоимость передачи информации во всех ветвях подграфа Xi.
1.Применяем алгоритм синтеза R-структур, находим размещение РЦ Y* = {yi*} и привязки абонентов к РЦ Хyi.Далее предполагаем, что РЦ размещен в пункте 1.
2.Определяем начальные веса всех вершин vi = 
(hi,li1) и выполняем переход на подпрограмму «Оценка» (шаги 3—20).
Подпрограмма «Оценка». В подпрограмме «Оценка» определяем стоимость передачи объема информации Hi от подграфа Xi к подграфу Xj при наилучшем варианте подключения. Пусть к началу итерации построено К. подграфов X1, Х2 , … Хк.
3.Выбираем изолированный подграф Хi.
4.Проверяем возможность введения ветви (i, j)
Нi + Нj ≤dmax
Если условие выполняется, то переходим к шагу 5, в противном случае полагаем, что экономия Еij = ∞, переходим к шагу 4 и выбираем другую пару подграфов Хr, Хl для анализа.
5.Отыскиваем вершину xj1, (xj1 Є Хj), ближайшую к xi*:
6. Проверяем, является ли xj1 направляющей в подграфе Xj. Если — да, то запоминаем дугу (i*, j*), вычисляем = Ci*j*(Hi,li*j*), Н’j=Нj + Нi и переходим к шагу 21, иначе — к шагу 7. Шаги 7—20 предназначены для нахождения наилучшего варианта подключения Хi к Xj.
Похожие работы
... вся сетевая деятельность, кроме предусмотренных правилами исключений, которые определяются самим пользователем. 2.4 Выводы по проектной части По итогам проведенных этапов по реорганизации схемы управления и оптимизации сети были достигнуты следующие результаты: снижена загрузка процессорной мощности оборудования рисунок 2.6, 2.7 Рисунок 2.6 –загрузка процессора до ...
... ориентированы на 32 разрядные шинные архитектуры компьютеров с процессорами 80386, 80486 или Pentium. Фирма Novell также подготовила варианты сетевой ОС NetWare, предназначенные для работы под управлением многозадачных, многопользовательских операционных систем OS/2 и UNIX. Версию 3.12 ОС NetWare можно приобрести для 20, 100 или 250 пользователей, а версия 4.0 имеет возможность поддержки до 1000 ...
... могут быть реализованы в виде сортирующих сетей Батчера, расширенных сетей или параллельных Баньяновидных плоскостей [12,14]. 2. КОММУТАЦИЯ В СЕТЯХ АТМ 2.1 ПРИНЦИПЫ ПРОЕКТИРОВАНИЯ КОММУТАТОРОВ Технология асинхронного режима передачи (Asynchronous Transfer Mode, ATM) наилучшим образом подходит для построения широкополосных цифровых сетей с интеграцией служб (Broadband Integrated ...
... информационные технологии, является пакет Visual Basic 5.0 Professional. Построенный на основе объектно-ориентированного расширения языка программирования 4-го поколения, он содержит средства визуального проектирования, доступ к объектам управления технологии связывания и внедрения объектов и предназначен для быстрой разработки сложных приложений, активно взаимодействующих с пользователем и ...
0 комментариев