Содержание к диссертации
Введение
1. Методы расчета характеристик связности случайного графа 13
1.1. Определения и обозначения 15
1.1.1. Понятие случайного графа 15
1.2. Характеристики случайных графов 17
1.3. Метод ветвления и его модификация 23
1.4. Использование покрывающих деревьев при точном вычислении надежности графа 31
1.5. Редукция цепей 33
1.6. Расчет коэффициентов полинома связности 35
1.7. Приближенные методы вычисления вероятности связности графа 36
1.8. Выводы 39
2. Оптимизация структур сетей по критерию максимума вероятности связности 41
2.1. Оптимально-связные структуры сетей 41
2.2. Оптимальная достройка кольцевых структур 44
2.3. Оптимальное соединение кольцевых структур 48
2.3.1. Пересечение циклов 48
2.3.2. Соединение двух циклов 49
2.4. Оптимальное циклическое соединение циклов 53
2.5. Выводы 73
3. Программная реализация алгоритмов 75
3.1. Поиск цепи 75
3.2. Перенумерация вершин разрешающей цепи 76
3.2.1. Реализация перенумерации 77
3.3. Реализация расширенной формулы Мура-Шеннона . 79
3.3.1. Варианты результатов стягивания и удаления . 80
3.3.2. Оконечные рассчитываемые варианты графов . 82
3.4. Реализация редукции цепей 84
3.5. Реализация метода Чена-Ли 85
3.6. Реализация расчета коэффициентов полинома связности . 86
3.6.1. Оконечные состояния при расчете полинома связности 86
3.6.2. Ветвление по мультиребру 87
3.6.3. Использование ветвления по цепям 87
3.6.4. Учет "прикрепленных деревьев" 88
3.6.5. Учет "прикрепленных циклов" 88
3.7. Выводы 88
4. Экспериментальное исследование алгоритмов 89
4.1. Формула Мура-Шеннона 89
4.1.1. Классический вариант ветвления по ребрам . 90
4.1.2. Расширенная Формула Мура-Шеннона . 91
4.1.3. Применение последовательно-параллельной редукции 93
4.1.4. Метод Чена-Ли 96
4.2. Расчет и использование полинома связности .:... 97
4.2.1. Зависимость вероятности связности от типа графа 99
4.3. Выводы 105
Заключение 106
Литература 108
- Использование покрывающих деревьев при точном вычислении надежности графа
- Оптимальное соединение кольцевых структур
- Реализация расширенной формулы Мура-Шеннона
- Применение последовательно-параллельной редукции
Введение к работе
Задачи структурной оптимизации информационно-вычислительных сетей с точки зрения надежности и живучести, равно как задача расчета этих характеристик, являются одними из основных при проектировании подобных сетей [3, 6-8, 12, 23, 24, 28, 29, 38, 50, 56, 59-62, 68, 69, 72, 73, 75, 79, 80, 82]. Одним из важнейших показателей надежности работы сетей связи является их связность.
Существует много характеристик связности, что делает задачу не однозначной: реальным целям проектирования соответствуют различные целевые функции и ограничения [23]. В классической теории графов под связностью понимают либо реберную, либо вершинную связность. В зависимости от того, какая математическая модель описывает рассматриваемую задачу, различными авторами связность может трактоваться несколько иначе. Попытка систематизировать и классифицировать понятие связности и характеристик, связанных с ней, введенных за последние 30 лет, сделана в работе В.К. Попкова [31].
Одной из наиболее распространенных характеристик связности сети является вероятность связности заданного подмножества вершин vi,...,Vk, то есть вероятность того, что в конкретный момент времени между каждой парой этих вершин существует хотя бы один путь при заданных вероятностях присутствия ребер (эту вероятность для краткости часто называют надежностью ребра, в данном исследовании также используется этот термин). Существует два крайних варианта: к = 2 и к — п, где п — число вершин сети. Некоторые авторы (см., например, [51]) рассматривают в качестве основного показателя среднюю вероятность существования хотя бы одного пути по всем парам ребер. При рассмотрении сетей с равнонадежными каналами многие выводы, особенно при сравнении надежности различных структур, можно сделать с помощью так называемого полинома надежности или полинома свлзности, который показывает зависимость вероятности связности сети (графа) от надежности одного канала (ребра). Мы будем придер-
Введение 5 живаться термина "полином связности". На наш взгляд, он более точно соответствует смыслу.
Наряду с задачей вычисления вероятности связности сети ставится задача оптимизации ее структуры по этому показателю. При этом можно рассматривать как задачу построения сети оптимальной структуры, так и задачи оптимальных достройки сети или объединения сетей. Последние задачи имеют особую практическую значимость.
Вопросом вычисления или оценки вероятности связности сетей занимались и занимаются многие исследователи как в России, так и за рубежом. Прежде всего надо упомянуть Артамонова Г.Т., Вишневского В.М., Епихина В.В., Кауля СБ., Кельманса А.К., Литвака В.И., Ломоносова М.В., Нечепуренко М.И., Полесского В.П., Скоробогато-ва В.А., Толчана А.Я., Харкевича А.Д., Мура Э. [Moor Е.], Шеннона К. [Shennon К.], Ван Слайка P. [Van Slyke R.], Шумана A. [Shooman А.].
В данном исследовании в качестве модели сети рассматривается случайный граф.
Задача точного вычисления вероятности связности случайного графа с ненадежными ребрами относится к классу NP-трудных, поэтому ранее на практике использовали различные приближенные методы, тогда как точные методы расчета представляли в большей степени академический интерес. Однако развитие вычислительной техники привело к возрождению интереса к использованию этих методов на практике, так как появилась возможность за разумное время рассчитывать надежность сетей малой и средней размерности (до десятков узлов). Методы расчета можно кратко классифицировать следующим образом:
1. Приближенные методы: (а) метод Монте-Карло; (б) методы, основанные на рассмотрении остовов; (в) методы, основанные на рассмотрении разрезов.-
Введение
2. Точные методы: (а) методы ветвления, основанные на последовательном рассмо трении состояния ребер; (б) методы, основанные на алгебре событий (комбинаторные); (в) методы последовательной редукции, основанные на эквива лентных преобразованиях графа (методы последовательно- параллельной редукции).
Часто эти методы возможно комбинировать.
Необходимость разработки комбинированных алгоритмов вызвана по крайней мере следующими причинами [8]:
Крупномасштабные сети передачи данных обычно проектируются поэтапно, причем размерность сети на первых этапах невелика, что позволяет получать точное решение задачи топологической оптимизации с помощью комбинаторных алгоритмов. В то же время известные приближенные алгоритмы [12] не позволяют находить точное решение даже для сетей небольшой размерности. При этом лучшие эвристические алгоритмы по данным разработчиков дают погрешность до 10%.
Наличие точного решения позволяет оценить качество известных и вновь разрабатываемых.эвристических алгоритмов.
Комбинаторные алгоритмы представляют широкие возможности для изучения свойств оптимальных решений и оптимизируемой функции, что, в свою очередь, создает предпосылки для разработки новых эффективных алгоритмов.
В диссертационной работе экспериментально исследуются известные и собственные алгоритмы, основанные на ветвлении по состоянию ребер и последовательно-параллельной редукции, как в чистом виде, так и в комбинации с другими подходами.
Второй задачей является задача построения оптимально-связных структур графов по критерию максимальной вероятности связности.
Введение
При этом рассматриваются как задачи первичного синтеза, так и задачи оптимальной достройки или соединения сетей. Эти задачи также решаются точно или приближенно, перебором либо аналитически.
При рассмотрении оптимальных структур в качестве частного случая рассматриваются циклические (кольцевые) структуры, характерные для современных оптоволоконных сетей, построенных с использованием технологии SONET. Переход от классических SONET-архитектур к ячеистым также дает иерархические структуры, которые возможно оптимизировать предлагаемыми методами.
Изложение материала организовано следующим образом:
Использование покрывающих деревьев при точном вычислении надежности графа
Итак, рассмотрим алгоритм вычисления надежности графа с использованием покрывающих деревьев. Идея алгоритма проста: в графе строится произвольное покрывающее дерево То, после чего рассматриваются все возможные варианты его разрушения. Если удалить из этого дерева одно или несколько ребер, то связность может быть обеспечена только за счет остальных ребер, все возможные комбинации которых и рассматриваются. При этом может появиться возможность снижения размерности за счет учета параллельных ребер, связывающих подграфы, образованные разделенным деревом. Основная формула получения вероятности связности графа в рассматриваемом алгоритме имеет вид: где Ps(Ei) есть вероятность того, что рассматриваемый граф связен при удалении из То г ребер j-м способом, умноженная на вероятность такого удаления ребер (событие Ej, рассматриваются все возможные сочетания г ребер).
При расчете вероятности связности графа при условии события El возможно существенно снизить размерность задачи за счет следующих соображений. Удаление из дерева г ребер приводит к его распаду на не менее чем 2 и не более чем г + 1 часть (блок). Каждый из этих блоков содержит некоторое подмножество вершин графа, связанных между собой. Связность графа в целом может быть получена только за счет ребер, не входящих в дерево. Сопоставим каждому полученному подмножеству вершин некоторые псевдовершины вспомогательного графа Н. Ребро между двумя вершинами графа Н существует, только если множество ребер графа G\TQ, соединяющих вершины соответствующих блоков, не пусто. Пусть между некоторыми блоками существуют к ребер с вероятностями присутствия pi,P2, ,Рк- Тогда вероятность присутствия соответствующего ребра графа Н есть
При том, что данный метод позволяет существенно редуцировать рассчитываемые графы, он обладает тем недостатком, что число воз-можных комбинаций удаляемых ребер резко возрастает как с ростом числа вершин, так и числа удаляемых ребер. Так, для графа с 16 вершинами и числом ребер более 20, число комбинаций при удалении 6 ребер из покрывающего дерева составляет Cf5 = 5005, тогда как для графа с 21 вершиной и числом ребер более 25 аналогичное число комбинаций уже Со = 38760. Общее же число возможных удалений ребер из деревьев с 16 и 21 вершинами составляет 215 - 1 = 32767 и 220 - 1 = 1048575 соответственно. Тем самым метод эффективен либо для малых графов, либо для графов, в которых число ребер превышает число вершин на единицы. Однако для последних явно эффективнее использовать модифицированный метод Мура-Шеннона либо метод последовательно-параллельной редукции, рассмотренный ниже, в результате которой после редукции цепей получаются малые, легко рассчитываемые графы.
Однако, если прекращать рассмотрение вариантов удаления ребер из покрывающего дерева после некоторого малого числа ребер (обычно 2-4), получается нижняя оценка вероятности связности графа, тем более точная, чем выше надежность ребер.
Еще один альтернативный метод предложен в [81-83]. Он заключается в последовательной редукции графа заменой пары параллельных или последовательных ребер (в последнем случае речь идет о простой цепи длины 2) на одно ребро таким образом, чтобы вероятность связности всех оставшихся вершин графа, умноженная на некоторый однозначно вычисляемый фактор, равнялась вероятности связности всех вершин исходного графа. При отсутствии возможности редукции применяется простая формула Мура-Шеннона. Этот подход уменьшает количество ветвлений, но неэффективен при наличии длинных цепей. При этом вероятность присутствия ребра, заменяющего цепь длины 2, равна
Оптимальное соединение кольцевых структур
В этой главе рассматриваются вопросы программной реализации алгоритмов, предложенных в предыдущих главах. В силу повышенных требований большинства из них к используемой памяти, а также использования многочисленных рекурсий, задача их программирования нетривиальна. Поскольку основой предложенных алгоритмов является использование цепей, рассмотрение начнём с процедуры их нахождения. Интуитивно возникает желание использовать в качестве разрешающей самую длинную простую цепь графа, однако это требует нахождения всех цепей и сравнения их длин, что требует затрат как времени, так и памяти. Тем более, что если ветвление по самой длинной из цепей не приводит сразу к рассчитываемым графам малой размерности, все цепи все равно будут перебраны. Поэтому просто ищется цепь, включающая вершину степени 2 с минимальным номером (случай а) на рис. 3.1). Алгоритм поиска прост: Шаг 1. Ищется вершина степени 2. Если такой в графе нет, разрешающая простая цепь отсутствует. Пусть найденная вершина имеет номер ко. Этот номер заносится первым в список А номеров последующих вершин. Шаг 2. В строке ко матрицы смежности находится первый ненулевой элемент. Номер соответствующего столбца, &_i заносится первым в список Б номеров предшествующих вершин, і кладется равным 1. Шаг 3. Пока степень вершины к-І равна 2, список
В пополняется следующим образом: в строке матрицы смежности ищется ненулевой элемент с номером столбца, отличным от k-i+l. Номер соответствующего столбца заносится в В как k-i-i, г увеличивается на 1. Пусть номер последней вершины будет —s. Шаг 4. і кладется равным 0. Пока степень вершины / равна 2, список А пополняется способом, аналогичным предыдущему пункту. Пусть номер последней вершины будет t. Шаг 5. Имеем списки (вектора) номеров В = (A;_i,..., к-3) и А = (ко,... ,kt).
Инверсируем список В и присоединим к нему список А, получая искомый список вершин простой цепи, включая оконечные: Под разрешающей понимаем простую цепь, по которой производится ветвление в формулах (1.12), (1.13), 1.14) или редукция по формулам (1.19), (1.20). Цепь должна быть стянута к вершине с номером п — к (размерность редуцированного графа), поэтому этот номер назначается одной из оконечных вершин цепи. Номер п — к-\-1 назначается второй оконечной вершине, тем самым обеспечивая удаление вершин простым уменьшением размерности матрицы вероятностей. Соответственно, новые номера вершин разрешающей цепи после перенумерации должны быть равны п — d, п — d + 1,..., п, где d = t — s есть число рёбер цепи, an- число вершин графа после редукции. Таким образом необходимо произвести следующее изменение номеров вершин (старые номера соответствуют (3.1)): Возможно что Зг : (і Є {п - d, п - d + 1,..., тг}) Л (г Є N(G)\N(Ch)). Обозначим множество таких вершин как Sadd- Для каждой вершины vi\i Є Sadd назначается новый номер из множества U = N(Ch)\{n — d, п — d + 1,..., п}. Естественным способом упорядочения вершин В Sadd является возрастающий порядок их номеров и соответствующие новые номера из U также назначаются в порядке возрастания. Таким образом получаются списки старых и новых номеров для некоторых (возможно всех) вершин графа, необходимые для осуществления процедуры перенумерации (номера в N{Ch) упорядочены соответственно (3.1)): где U С U есть множество новых номеров, выбранных для вершин из badd- і Примеры перенумераций приведены на рис. 3.1.
В скобках указаны новые номера вершин. Если при перенумерации пары вершин графа изменение матрицы смежности заключается в последовательном переставлений соответствующих строк и столбцов, то перенумерацию многих вершин подоб Тем самым мы получили граф, хотя и изоморфный исх совершенно отличный от требуемого (см. Рис. 3.2, в скобкг старые номера вершин). При программировании алгоритма перенумерация провод] пользованием промежуточного представления графа списког есть множеством пар номеров вершин. При последовательно этих пар номера вершин в них меняются со старых на новы номера принадлежат множеству изменяемых). Затем восста ся v tce новая матпитта пмежттпг.ти.
Реализация расширенной формулы Мура-Шеннона
В этом пункте рассматривается программная реализация предложенного во второй главе алгоритма расчета вероятности связности графа по формулам (1.12), (1.13), (1-14). Основным требованием к последовательной (на однопроцессорной ЭВМ) реализации этого алгоритма является использование одной и той же области памяти для хранения матрицы смежности графа с подготовкой ее для входа в очередную рекурсию при ветвлении и восстановлением после выхода из нее. Такое использование памяти предусматривает перенумерацию вершин для обеспечения работы только с верхним левым квадратным блоком матрицы соответствующей размерности. Тогда уменьшению размерности графа при стягивании вершин по ребру или цепи, а так же удалению цепи вместе с вершинами, соответствует перенумерация, делающая номера остающихся в графе вершин первыми. То есть удаляемые (стягивае мые) вершины всегда имеют последние номера. Соответствующий алгоритм перенумерации рассмотрен выше. При выполнении ветвлений необходимо учитывать все возможные варианты результирующих графов. При использовании классической формулы Мура-Шеннона (1.8) возможно только 3 основных результата: (а) получение несвязного графа при удалении ребра, (б) рассчитываемого графа малой размерности при стягивании и (в) связного нерассчитыва-емого графа, к которому снова применяется операция ветвления. При использовании модифицированных формул (1.12), (1.13), (1.14) или при ветвлении по цепям нужно учитывать большее количество вариантов. 1. Разрешающая цепь есть цикл. Начальная вершина найденной цепи к-з совпала с конечной /. Это означает, что вершина k-s (kt) есть точка сочленения цикла и некоторого графа G . Соответственно, вероятность связности графа G рассчитывается далее как 2. Результирующий граф есть цикл. В результате удаления це пи остался цикл и степени всех вершин равны 2, что означает за цикливание алгоритма поиска разрешающей цепи.
Это означает необходимость проверки после каждого удаления цепи, не равны ли между собой максимальная и минимальная степени вершин. Если они при этом равны 2, то ветвление заканчивается и возвра . щается вероятность связности цикла по формуле (2.3). 3. Появилась висячая вершина. Пример такого стягивания при веден на рис. 3.2. Появление висячей вершины означает, что ми нимальная степень вершины равна 1. Результатом стягивания мо жет быть только одна висячая вершина, присоединенная ребром к вершине степени больше 2. Обработка ситуации очевидна, вероятность связности графа равна произведению вероятности присут-ствия ребра, соединяющего эту вершину с остальным G графом на вероятность связности этого графа R(G ). 4. Размерность рассчитываемого графа многовариантна: в результате стягивания может получиться граф не только из трех, но даже из двух вершин (рис. 3.3). Поэтому проверять нужно не только на количество вершин, равное 4, как для простой формулы Мура-Шеннона, но и на количество вершин 2 и 3. 5.
Результирующий граф несвязен. Это означает, что удаленная цепь есть мост. Соответственно, по линии стягивания получим точку сочленения и возможно рассматривать вероятность связности графа как произведение вероятностей связности двух графов и вероятности наличия разрешающей цепи (или ребра). Реализация этого варианта также не столь проста, как может показаться: простая реализация произведения вероятностей требует создания новой матрицы смежности (имеем два графа!), что недопустимо по соображениям памяти. Поэтому сначала вычисляем вероятность связности одной компоненты и лишь затем - второй. При этом снова нужно решить задачу перенумераций для использования только верхней левой части матрицы смежности. Перед этим же нужно определить списки вершин компонент. Последняя задача решается простым алгоритмом маркирования, начиная с оконечных вершин удаленной цепи (ребра). На самом же деле в проведении дополнительного поиска нет необходимости, если в случае несвязного графа возвращать из процедуры проверки связности список вершин связной компоненты, полученный при проверке. Список вершин второй компоненты связности элементарно получается как дополнение первого минус внутренние вершины удаленной цепи. При расчете вероятности связности графа по формулам (1.12), (1.13), (1.14) в процессе редукции рано или поздно получаются графы, для которых возможно непосредственно получить вероятность связности. Рассмотрим варианты таких графов. 1. Граф малой размерности. Простейшим вариантом является граф из одного ребра. В этом случае процедура должна вернуть вероятность его присутствия. Однако желательно рассчитывать вероятность связности напрямую, для возможно большей размерности графа, так как это избавляет от необходимости дальнейшей декомпозиции и, следовательно, снижает число рекурсивных вызовов процедуры. При этом, в силу многократного выполнения формулы расчета, необходимо построить ее оптимальным образом. Так, пусть для случая трех вершин вероятности присутствия ребер равны а, Ь и с. Тогда, по формуле вероятности связности цикла имеем: что требует 6 операций умножения-деления и б операций сложения-вычитания, тогда как применение промежуточной переменной позволяет обойтись четырьмя операциями умножения и тремя сложения: В случае 4-х вершинного графа обозначим вероятности существования ребер как тогда прямая формула после приведения подобных имеет вид
Применение последовательно-параллельной редукции
В этой главе анализируются результаты численных экспериментов по расчету надежности графов, проведенных с целью сравнения предложенных алгоритмов и их модификаций. Расчеты проводились на ПЭВМ с процессором AMD Athlon(tm), работающим на частоте 750 МГц. Расчеты проводились (кроме специальных примеров) на случайных связных по структуре графах с заданными числом вершин и ребер и заданной вероятностью присутствия ребра [36]. При этом фиксировалось время на момент входа в цикл "генерация графа — расчет его надежности" и после выхода из этого цикла. Поэтому в регистрируемых значениях времени счета присутствует и время генерации случайных графов. Однако, в большинстве случаев, это время пренебрежимо мало. Количество генерируемых случайных графов было ограничено 30 по причине того, что в простейшем случае расчет такого числа графов потребовал более 12 минут. Однако для больших размерностей графов такая выборка, очевидно, не является представительной и позволяет получить лишь сравнительные результаты. Этим определяется и "негладкость" некоторых графиков.
В этом пункте рассматриваются результаты применения различных вариантов формулы Мура-Шеннона: в чистом виде, с различными вариантами завершения, с предварительной редукцией цепей либо с ветвлением по цепям и пр. Оценивается вклад различных модификаций в сокращение времени расчетов.
Как и следовало ожидать, применение простого ветвления по ребрам с применением формулы Мура-Шеннона (1.8) требует максимального времени счета. Однако применение этой формулы позволяет заметить эффект от предложенных способов ускорения расчетов. В таблице 4.1 приведено время расчета по этой формуле, затраченное на расчет надежности 30 случайных графов с 12 вершинами и 17 ребрами, 15 вершинами и 20 ребрами, 15 вершинами и 24 ребрами и 20 вершинами и 30 ребрами соответственно для разных вариантов комбинаций проверок и прекращения редукций.
Рассматривались комбинации следующих приемов: А - Проверка связности только по ветви удаления ребра. В - Проверка на дерево. С - Проверка наличия прикрепленных цепей (предварительная). D - Завершение редукций по достижении 2 вершин. Е - Завершение редукций по достижении 4 вершин. F - Редукция цепей (предварительная).
Из приведенных в таблицах результатов видно, что наибольший эффект достигается от снижения размерности исходного графа, подаваемого на вход метода. При этом уменьшение количества вершин и ребер за счет отбрасывания "прикрепленных деревьев" и замены простых цепей ребрами тем значительней, чем разреженнее исходный граф, т.е. чем меньше средняя степень вершины. Программно удаление "прикрепленных деревьев" реализовано рекурсивным удалением висячих вершин. Заметное ускорение дает и проверка на то, что граф является деревом. Время, затраченное на предварительную редукцию графа, включено во время счета.
В таблицах 4.2-4.5 приводятся данные о среднем количестве рекурсий и причинах их завершения для тех же вариантов, что и в таблице 4.1. Из этих таблиц ясно видно, что определяющим для времени счета является количество рекурсий, хотя среднее время, затрачиваемое на рекурсию, отличается от варианта к варианту.
Рассмотрим эффект, который дает ветвление по цепям по формулам (1.13), (1.14) по сравнению с классическим методом Мура-Шеннона, реализованным в наиболее эффективном виде: с проверкой связности только по ветви удаления ребра, завершением по достижению размерности в 4 вершины и предварительной редукцией (последняя строка таблицы 4.1). К расчёту по этим формулам также подавались графы, предварительно редуцированные за счет удаления "прикрепленных деревьев". Время редукции включено во время счета. Пусть тестовый граф представляет собою решетку 4x4 (Рис. 4.1, пример предложен для сравнения методов расчета надежности в [57]).
Время расчета в первом варианте составило 0.55 с, тогда как в случае применения расширенной формулы Мура-Шеннона это время составило 0.1-7 с.
Сравним расчеты по другим показателям. Для формулы Мура-Шеннона количество рекурсий составило 5351, число завершений по несвязному графу - 652, по достижению 4-х вершин - 1004 и сведению к дереву - 1016. Для модифицированной же формулы Мура-Шеннона количество рекурсий составило только 407, завершений по несвязному
