Алгоритм статистических испытаний для определения параметров структур сетей связи по методу Монте-Карло

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

Следует иметь в виду, что любое воздействие носит случайный характер. Используемая в алгоритме вероятность воздействия говорит лишь о его силе (степени этого воздействия), но исключает такие его параметры как место применения и распределение по узлам и линиям сети. Это означает, что в данный конкретный момент времени мы ничего не можем сказать о повреждении любой территориальной части сети и является ли воздействие равномерно распределенным или имеет направленное воздействие на какие-либо линии и узлы. Отсюда следует, что результат характеризует случайное событие — либо сеть останется связной, либо нет.

Для решения задачи о связности структуры сети статистическим методом необходимо многократное повторение такого воздействия. Современные компьютеры позволяют набирать статистику, моделируя различные воздействия и в любом количестве. Простая структура вычислительного алгоритма метода Монте-Карло позволяет производить одно случайное испытание заданное количество раз, причем каждый опыт не зависит от всех остальных, а результаты всех опытов усредняются. Это еще одна особенность, выступающая в пользу метода Монте-Карло.

От количества испытаний зависит точность — чем больше испытаний, тем выше точность. Ошибка вычислений пропорциональна величине , где J — некоторая постоянная, а N — число испытаний. Метод Монте-Карло особенно эффективен при решении тех задач, в которых результат нужен с точность (5–10 %), что в нашем случае не требуется лучше. В программе NET точность вычислений для 750 испытаний по среднеквадратическому отклонению составляет 6. Как показали исследования, вероятностная модель оказалась весьма удобной при сравнительной оценке множества структур сетей задаваемых в виде графа.

Рассмотрим подробно работу алгоритма статистических испытаний по методу Монте-Карло.

Наиболее удобным способом формального описания структуры сети связи с n узлами и m линиями является использование теории графов. Структуру сети связи представим в виде графа G=(B,H), где В=(,…)- совокупность узлов (станций) сети (вершин графа), а H=()- множество ребер, соединяющих узлы  и , и соответствующих всем линиям передачи.

Поскольку каналы транспортной сети связи являются каналами двухстороннего действия, то соответствующие им ребра будут ненаправленными (неориентированными). В программе NET разработанной для оценки структур транспортных сетей связи предполагается, что веса всех ребер графа одинаковы =1 (ребра единичной длины). С точки зрения связи это означает, что в исследованиях пропускная способность узлов и линий сети не задана; поток информации мог передаваться из одного узла в другой по любой исправной линии через любой узел; отказы всех узлов и линий сети взаимно независимы; расстояния между узлами связи одинаковые.

Для графов существует несколько способов представления исходных данных в машинной памяти. Для нас более интересно представление графов в виде матрицы связности, поскольку определяемые параметры связаны с оценкой структуры сети и нам важно иметь сведения о наличии ребер в графе, а время, необходимое для определения наличия ребра, фиксировано и не зависит от размерности графа. Такое представление графов требует памяти порядка  единиц. Изначальной матрицей связности в алгоритме оценки структуры сети выступает матрица Кирхгофа K= [] (своеобразный аналог матрицы связности), определяемая как квадратичная матрица порядка n (n- число узлов связи в сети), элементы которой записываются по следующему правилу:

                                                                 (1)

Связь между матрицей связности A и матрицей Кирхгофа K имеет вид: K=D-A, где D=diag(deg, deg,… deg), т. е. матрица K является матрицей, диагональные элементы которой равны степеням (валентностям) вершин графа.

Изначальная матрица связности структуры сети задается следующим образом. В ячейках по диагонали выставляется количество подходящих к узлу линий связи. По горизонтали и вертикали, проходящих через узел связи, наличие линии связи обозначается -1по уровню того узла, к которому эта линия подходит (т. е. имеет место зеркальное отображение элементов матрицы относительно главной диагонали). Алгоритм статистических испытаний является универсальным и позволяет оценивать структуры транспортных сетей связи любой размерности. В работе использовалась программа с n =29, но при необходимости может быть задано другое количество узлов.

Поскольку метод Монте-Карло предусматривает многократное повторение одной и той же вычислительной процедуры, то рассмотрим одно отдельное испытание.

При оценке связности сети в качестве исходных данных алгоритм Монте-Карло (программа NET, разработанная в Microsoft Office Excel 2007) использует значения вероятности повреждения узла и вероятности повреждения линии, вычисленных или измеренных с учетом тех факторов, влияние которых мы хотим учесть. Кроме того используется изначальная матрица связности исследуемой сети (при необходимости алгоритм позволяет учесть зависимость вероятности повреждения линий от их длины).

Вероятность повреждения узла Р_уз и линии Р_лин задаются в ячейках С69 и С70 соответственно в случае, когда они равновероятны для всех узлов (всех линий). Значение из ячейки С69 будет продублировано в строке С72:АЕ72. Эти вероятности можно задавать индивидуально для каждого узла и каждой линии вручную. Вероятность повреждения узла — в строке С72:АЕ72, а вероятность повреждения линии — в матрице связности исследуемой сети выше главной диагонали в ячейках со значениями -1 путем замены в строке формул выражения 1-СТЕПЕНЬ(1-….;L/100) на необходимую для исследования вероятность повреждения линии. Таким образом, мы получаем возможность оценить работу сети, как в среднем, так и при ее функционировании в других условиях. На данном этапе имеется возможность учесть зависимость вероятности повреждения линии (Р_лин) от ее длины. Поскольку исходные данные для работы алгоритма являются вероятностными величинами, то результат с необходимой точностью может быть получен только при выполнении некоторого множества испытаний. Результат отдельного эксперимента будет случайным образом определять поврежден (не поврежден) узел и линия в этот раз при заданных вероятностях Р_уз и Р_лин.

Количество генераторов случайных чисел, запускаемых в программе при расчете конкретной сети, определяется количеством узлов и линий связи сети и равно их сумме n+m. т. е. вероятности повреждения узлов и линий связи в каждом эксперименте будут задаваться от разных датчиков. Это позволяет избежать (существенно уменьшить) взаимную корреляцию результатов, что повышает их точность и ускоряет процесс вычислений. Блочная схема алгоритма вычислений по методу Монте-Карло изображена на рисунке 1.

Назначение блоков алгоритма:

1.                  Генераторы случайных чисел (ГСЧ) (датчики) вырабатывают случайные числа для узлов и для линий связи.

2.                  Вычислители состояний элементов сети в рамках алгоритмапроводят сравнение значений элементов сети, полученных после испытаний, с заданными исходными данными.

3.                  Анализаторы состояний элементов сети принимают решения: если элемент сети имеет значение -1 — узел (линия) сохранился, если он имеет значение 0 — узел (линия) не сохранился.

Рис.1 Блочная схема алгоритма вычислений по методу Монте-Карло

Результат работы анализаторов для узлов связи отображается в строке (С74;АЕ74). Расчет состояния узла связи производится по формуле:

ЕСЛИ(ABS(СЛУЧ())$$;-1;0), (2)

где $$ — наименование ячейки соответствующего узла в строке (С72;АЕ72).

Формула означает, что если заданная в исходных данных вероятность поражения узла (Р_уз) окажется меньше случайного числа, выданного датчиком, то анализатором будет принято решение о сохранении узла в сети, в противном случае узел будет поврежден (неисправен). Наличие хотя бы одного нуля в строке (С74;АЕ74) будет свидетельствовать о потере связности сети в связи с уничтожением узла.

Результат работы анализаторов для линий связи можно оценить в поле матрицы связности исследуемой сети после воздействия (С77;АЕ105) в ячейках выше главной диагонали. Вычислитель для линии связи работает по формуле: ЕСЛИ(И(СЛУЧ()L/100);$$2= -1;$$3= -1;$$4= -1);-1;0). (3)

Анализатор линий связи принимает решение о ее сохранности при одновременном выполнении 3 условий:

1)                 Вероятность уничтожения линии L/100) будет меньше случайного числа от датчика (здесь $C$70-фиксированное число, задаваемое в исходных данных, а L-длина линии в определенной ячейке матрицы расстояний между узлами). В нашем случае L=1;

2)                 В исходной матрице связности сети линия была задана как: $$2= -1;

3)                 Узлы связи, соединяемые этой линией (вершины графа, соединяемые ребром) не были повреждены, т. е. сохраняется $$3= -1;$$4= -1.

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

Поскольку воздействие на сеть связи носит случайный характер, то связность сети выступает некоторой случайной величиной, принимающей значение 0 или 1 при различных вероятностях воздействия.

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

ЕСЛИ(МОПРЕД(С77;$$5)0,5;1;0), (4)

где: $$5 — предпоследний элемент в диагонали матрицы связности исследуемой сети после проведения всех испытаний; МОПРЕД(С77;$$5) — определитель матрицы связности размером (n-1)×(n-1) (минор матрицы связности исследуемой сети, образованной после проведения всех испытаний).

Как показано в [1], количество остовных деревьев исследуемого графа может быть найдено через значение этого определителя. Доказано, что в графе G без петель число различных деревьев представляющих собой частичные графы G равно минору любого из элементов главной диагонали квадратичной матрицы () порядка n, где

Общая формула для составления полного списка остовных деревьев любого произвольного n-вершинного графа G без петель представлена в теореме [2]. Согласно этой теореме, число остовных деревьев равно определителю , где - матрица инциденции графа G с одной удаленной строкой (т. е. с n-1 независимыми строками), а - транспонированная матрица к .

Число остовных деревьев в алгоритме (программе NET) статистических испытаний по методу Монте-Карло вычисляется как минор последнего элемента диагонали в матрице связности исследуемой сети после воздействий.

Таким образом, в случае, если минор окажется меньше 0,5, то граф не будет иметь ни одного остовного дерева (в ячейке А99 будет записан ноль), и анализатор связности сети примет решение, что сеть несвязна (в ячейке А103 также будет записан 0). Если минор будет больше 0,5, то анализатор посчитает, что граф имеет хотя бы одно остовное дерево, соответственно сеть будет связной. Количество остовных деревьев будет выставлено в ячейке А99. В ячейке А103 будет записана единица.

Поскольку число остовных деревьев в сети большое, то при сравнении структур сетей по параметру их связности число остовных деревьев можно получать (анализировать) в логарифмическом масштабе. Натуральный логарифм от количества остовных деревьев пересчитывается в ячейке А102.

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

—СУММЕСЛИ(С35:АЕ63;-1)/2+СУММЕСЛИ(С77:АЕ105;-1)/2, (5)

где: (С35:АЕ63) — массив ячеек, занятых изначальной матрицей связности исследуемой сети; (С77:АЕ105) — массив ячеек, занятых матрицей связности исследуемой сети после проведения всех испытаний. Результат записывается в ячейку А101.

Таким образом, в результате одного испытания алгоритм определяет состояние сети связи (связна она или нет), вычисляет количество остовных деревьев графа этой сети и количество поврежденных линий связи. Методом прямого перебора состояний элементов сети алгоритм Монте-Карло анализирует 750 возможных вариантов воздействия на сеть связи с заданными исходными данными. В результате 750 испытаний все данные обобщаются и усредняются. Рассмотрим процесс получения финальных оценок.

1. Вероятность связности сети (Р_сс) определяется вычислителем вероятности сохранения связности сети, как среднее значение массива (AI159:BL183):

СРЗНАЧА(AI159:BL183). (6)

Массив, размерностью 3025 в каждой своей ячейке содержит значение связности (0 или 1) для одной реализации. Результат усреднения записывается в ячейку ВО162 и дублируется в А123.

Нужно отметить, что параметр P_ссоценивает структуру непосредственно на основе всех испытаний при заданных величинах Р_уз и Р_лин.

2. Косвенным показателем, позволяющим более «тонко» оценивать структуры по связности является среднее количество остовных деревьев K_{ост дер}. Для этих целей можно использовать усредненное количество остовных деревьев в массиве (AI129:BL153) (в том числе и с изменением масштаба):

СРЗНАЧА(AI129:BL153), (7)

а само количество остовных деревьев выводится в ячейку ВО134.

3. Среднее количество уничтоженных противником ребер определяется из массива (AI99:BL123):

СРЗНАЧА(AI99:BL123), (8)

и выводится в ячейку ВО102.

Таким образом, по завершению 750 статистических испытаний алгоритм Монте-Карло определяет следующие параметры структуры сети: вероятность сохранить связность сети P_cc; среднее количество остовных деревьев графа; число ребер структуры (среднее количество, максимально возможное, минимально возможное), которые будут повреждены и сохранены при данном воздействии; графы сетей которые образуются при каждом конкретном воздействии. Все результаты выводятся в таблицу, расположенную в массиве (AJ14:BM60). При необходимости алгоритм и программа может выдавать гистограмму зависимости частоты уничтожения того или иного количества линий от их общего количества, т. е. программа определяет сколько раз из 750 попыток удалось повредить 1 линию связи, сколько раз 2 линии, 3 линии и т. д. до 20 линий связи. Разрушения свыше 20 линий не представляют интереса, поскольку сеть перестает быть связной. Сравнивать структуры сетей возможно при фиксированной Р_сс.

4. Имея значения Р_сс полученное при определенных воздействиях на сеть (Р_уз и Р_лин), мы можем оценивать количество поврежденных линий связи в среднем. Понятно, что конкретные значения числа поврежденных линий, а также места их включения метод будет выдавать каждые 750 раз проведенных испытаний. С целью определения структур сети с конкретными удаленными ее линиями будем обращаться к одной любой реализации из тех, в которых число поврежденных линий связи приблизительно равно среднему их значению по всем 750 испытаниям. Сеть в таком испытании должна оставаться связной, т. е. любой из узлов должен остаться соединенным с остальными узлами сети, несмотря на некоторые уничтоженные линии. Таким образом, мы получим конкретный вид структуры сети, которая близка к структурам со средним значением числа повреждаемых линий.

Для оценки параметров структур транспортных сетей в работе используется программа NET, разработанная специалистом кафедры «Многоканальной связи» Кольцовым Валерием Викторовичем. Расчеты по программе NET проводились на компьютере с тактовой частотой процессора 3,4 ГГц и объемом оперативной памяти (ОЗУ) 4 Гбайт. Время работы программы по одной паре заданных вероятностей воздействий на узел и линию составляет 30сек. Это время является фиксированным для расчета структур сетей связи любого размера максимум до 29 узлов включительно.

Литература:

1.                  Берж К. Теория графов и ее применение: Пер. с франц. — М.: Издательство иностранной литературы,1962г 320с.

2.                  Кристофидес Н. Теория графов. Алгоритмический подход: Пер. с англ. — М.: Мир, 1987. — 432с.