Исследование связности ячеистых сетей и разработка алгоритмов имитационного моделирования

НА ТЕМУ:

Исследование связности ячеистых сетей и разработка алгоритмов имитационного моделирования

Аннотация

Рассматриваются два подхода к оценке живучести сетей: детерминированный и вероятностный. Анализируются модели гибели сетей и вероятности связности сетей. При детерминированном подходе получены модели гибели ряда структур, в том числе: линия, звезда, кольцо При исследовании живучести возникают трудности, связанные с большим количеством вычислений. Для автоматизации вычислений и наглядного представления результатов исследования, были разработаны алгоритмы и реализованы на языке Object Pascal. В программе используется удобный графический ввод, дано табличное представление результатов вычислений и построение графических зависимостей. Алгоритм реализует полный перебор различных вариантов повреждения сети и анализ параметров сети в этих состояниях. Для удобства просмотра в программе реализован сбор результатов исследования (графов сетей, цифровых значений, и графических зависимостей) в отдельный файл с возможностью вывода результатов на печать.

Введение

Глава 1. Оценка гибели сетей связи

1.1 Показатели гибели сети

1.2 Гибель звездообразной сети. Разрыв дуг

1.3 Гибель звезды при атаке на узлы

1.4 Гибель линейной сети. Разрыв дуг

1.5 Гибель линейной сети. Атака на узлы

1.6 Кольцевая сеть. Разрыв дуг

1.7 Кольцевая сеть. Гибель узлов

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

2.1 Оценка влияния размера ячеек на вероятность связности

2.2 Оценка влияния числа избыточных дуг на вероятность связности

2.3 Выводы ко второй главе Глава 3. Разработка и программная реализация алгоритмов гибели и живучести ячеистых сетей

3.1 Постановка задачи

3.2 Описание алгоритма программы

3.3 Результаты исследований гибели сетей при атаке на узлы

3.4 Результаты исследований гибели сетей при атаке на дуги

3.5 Результаты исследований по методу связности Выводы Список литературы Приложения

Важность сетей телекоммуникации для предприятия, города, государства заставляет владельцев сетей (или их доверенных организаций — операторов связи) заботиться об их живучести. Живучесть сетей телекоммуникаций (СТ) — способность оказывать услуги по перемещению сообщений в полном объеме или частично в условиях стихийных бедствий, при боевых или террористических актах, при преднамеренных и случайных повреждениях, связанных с человеческим фактором, а также восстанавливать свои функциональные качества [8,9,10]. Сеть телекоммуникаций — это динамическая система как по структуре (топологические характеристики могут получать положительное или отрицательное приращения), так и по потокам, которые нестабильны по интенсивности, случайны по местам зарождения и погашения.

Значительный вклад в разработку теории живучести систем различного назначения внесли работы как отечественных [11,12], так и зарубежных ученых [14,15]. Вместе с тем в монографии отмечается, что живучесть — свойства систем, которые оцениваются нерасчетными характеристиками: неуязвимостью, адаптивностью и восстанавливаемостью. Ячеистая сеть это множество ячеек, смежных общим узлом или дугами. Ячейка это кольцо размером три узла и более. Модели живучести сетей по вероятности связности узлов разрабатывались с середины прошлого века [8], и затем получили многочисленное развитие. При определении вероятности связности сети предполагается, что в сети имеются избыточные (по сравнению с деревом) дуги, допускающие их разрыв. Любые повреждения древовидной сети приводят к потере связности, и живучесть становится равной нулю. Выражение для оценки вероятности связности дерева имеет вид одночлена, в котором число множителей (вероятность разрыва дуги q или наоборот, рабочего состояния p=1-q) равно числу дуг независимо от структуры дерева. Различают два подхода к исследованию гибели и связности сетей сообщений — детерминированный и вероятностный. При анализе гибели сети размером n узлов на детерминированных моделях задается число пораженных дуг или узлов ш, причем 0

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

Глава 1. Оценка гибели сетей связи

1.1 Показатели гибели сети

При заданном числе m пораженных элементов анализ гибели и распада сети размером n узлов ведется по следующим показателям:

Si число погибших узлов для i-ro варианта поражения m элементов;

Ui-число выживших узлов для i-ro варианта поражения m элементов, очевидно, что Si+Ui=n;

w=Cn, rm число вариантов поражения m элементов сети;

?Ui — общая сумма выживших узлов для w вариантов поражения m элементов сети;

?Si — общая сумма погибших узлов для w вариантов поражения m элементов сети;

 — среднее число выживших узлов при поражении m элементов сети;

 — среднее число погибших узлов при поражении m элементов для всех w вариантов. Однако для сравнения сетей различных, размеров и структур на одном графике удобнее использовать относительные величины , — средняя доля погибших узлов при разрыве m дуг (гибели ш узлов) сети., средняя доля выживших узлов при поражении m элементов сети. d (Sp) + d ((Up) = 1; d (Sy) + d ((Uy) = 1. Средняя доля погибших узлов должна удовлетворять следующим условиям:

1.d (Sp), d (Sy) = 0, если m = 0

2.d (Sp), d (Sy) = 1, если m=r, m=n-1,n

3. d (S) = [0,1] при 0? m?n, r

1.2 Гибель звездообразной сети. Разрыв дуг

Наиболее просто зависимости среднего числа и доли погибших узлов при разрыве 0? m?r дуг определяются для звездообразной сети.

а)	б)	в)	г)	д)

Рисунок 1 Звездообразные сети

Разрыв каждой из 0? m?n-1 дуг одновременно означает гибель смежных с ними периферийных узлов. Размер выжившей части U=n-m.

При n=3 и m=0 (Рисунок 1а) сеть действует в нормальных условиях. Число погибших узлов равно нулю, число выживших U=n.

При m=1 сеть распадается на две части размером один (Sр = 1) и два узла (Uр = 2) два варианта. Первый фрагмент считается погибшим, второй — выжившим. Доля поражения дуг составляет dnp =1/3 Доля погибших узлов d (Sp) = 1/3. Доля выживших узлов d (Up) =2/3.

При m=2 сеть распадается на три части, каждая размером один узел, что означает гибель всей сети.

При n=4 узла, m=0 (Рисунок 1б) сеть действует в НУЭ (нормальных условиях эксплуатации). Погибших узлов нет. Число выживших Uр = n. d (Sp) = 0, d (Up) = 1.

Если m=1, то сеть распадается на две части размером Sp = 1 узел и три узла Uр=3. Первый считается погибшим, вторая — выжившей. Поэтому d (Sp) = ¼, d (Up) = ¾ при доле поражения dn, p = 1/3. Если m=2, то сеть распадается на три части размером Spi = 1, Sp = 1 и Up = 2.? Sp = 2, поэтому d (Sp)=2/4; d (Up)=2/4. При m=3 сеть распадается на четыре части, каждая размером единица. Общее число погибших узлов? Sp = 4. d (Sp) = 1

При n = 5 и m = 0 (Рисунок 1в) сеть действует в НУЭ погибших узлов нет. Число выживших узлов Up = n. d (Sp) = 0, d (Up) = 1.

Если m = 1 (dnp = ¼), то сеть распадается на две части размером единица Sp = 1 и четыре узла Up = 4, тогда d (Sp)=1/5; d (Up)=4/5.

Если m = 2 (dnp = ½), то сеть распадается на три части размером единица Spl = Sp2 = 1 и nр = 3. Общее число погибших узлов? Sp = 2, поэтому d (Sp)=2/5, d (Up)=3/5.

При m=3 (dnp = ¾) сеть распадается на четыре части при любом варианте разрыва трех дуг. Три части каждая размером один узел гибнут.? Sp = 3. Одна часть размером два узла выживает. Поэтому d (Sp)=3/5, d (Up)=2/5.

При m=4 (dnp = 1) сеть распадается на пять частей, каждая размером единица, поэтому все узлы гибнут? Sp = 5, d (Sp)=1, d (Up)=0.

Количество изымаемых дуг	а)	б)	в)	г)	д)
	1/3	¼	1/5	1/6	1/7
	1,000	2/4	2/5	2/6	2/7
		1,000	3/5	3/6	3/7
			1,000	4/6	4/7
				1,000	5/7
					6/7
					1,000

Из анализа таблицы становится очевидным, что числитель равен m, знаменатель — n. Поэтому доля погибших узлов при разрыве m дуг равна d (Sp)=m (n, доля выживших узлов d (Up)=(n-m)/n).

Графические зависимости d (Sp) = f (dnp, n) представлены на (Рисунок 2) Они начинаются с нуля в левом нижнем углу и заканчиваются в единице правого верхнего узла. При заданном значении dnp величина d (Sp) отсчитывается от нижней оси до линии d (Sp) тогда значение d (Ur) отсчитывается сверху вниз.

1.3 Гибель звезды при атаке на узлы

Последствия атаки на узлы существенно хуже по сравнению с разрывом дуг. Потеря периферийного означает уменьшение сети на один узел, а вот потеря центра приведет к распаду сети на n-1 часть, каждая размером единица, связи между узлами разорваны, сообщения передаются и не принимаются, сеть уничтожена.

При n=3 и m=0 сеть действует в НУЭ, потерь нет Sу = 0, Uy= n соответственно, d (Sy) = 0, d (Uy) = 1.

Если m=1, то атака может быть направлена на периферийные узлы Sу=1, выживает фрагмент размером Uy=2 узла. Вариантов такой атаки — два. При атаке на центр разрываются смежные с ним дуги, вся сеть рассыпается на части Sу = 1, ?Sy = 3.

Сумма погибших узлов при атаке на каждый из трех узлов? Sу = 5. Среднее число погибших узлов при m = 1 узел Sy = ?Sy / n = 5/3. Средняя доля погибших узлов d (Sy) = Sy/n = 5/9. Средняя доля выживших узлов

d (Uy) =? Uy / m*n = 4/9.

При m = 2 или 3 сеть полностью уничтожена (см. табл.2, n=3). При n=4 и m=0 сеть действует в НУЭ, потерь нет, Sу = 0, Uy = n, соответственно, d (Sy) = 0, d (Uy) = 1.

Если m=1 узлу и атака направлена на периферийные узлы, то сеть уменьшается на один узел, выживает фрагмент размером три узла. Периферийных узлов три, поэтому в сумме теряется три узла, выживает? Uy=3*3=9.

При атаке на центр гибнут все узлы сети. Для всех четырех вариантов атаки на один узел гибнет? Sy=3+4=7 узлов, среднее число погибших узлов =? Sy / w = 7/4. Среднее число выживших узлов = ?Uу / 4 = 9/4. Отсюда средняя доля погибших узлов при атаке на один из узлов

d (Sy) =/n =? Sy / (w*n)=7/16

при dny = ¼. Средняя доля выживших узлов при атаке на один из четырех узлов d (Uy) = /n =? Uy/(w*w) = 9/16.

В сумме d (Sy) + d (Uy) = 1.

При m=2 узла возможны шесть вариантов гибели узлов из них три, когда атака направлена на периферийные узлы — гибнут два узла, выживают также два узла. Возможны два варианта атак — на центр и периферийный узел. В этом случае гибнет целиком Sy = 4. Для всех шести вариантов гибнет? Sy = 2*3+4*3=18. Среднее число погибших узлов =?Sy/w = 18/6 =3 средняя доля потерянных узлов d (Sy) = S/(w * w) =18 (6*4) = ¾ при dny = 2/4. Общее число выживших узлов равно? Uy= 6, среднее число Uy=1. Отсюда средняя доля выживших узлов d (Uy)=¼.

При m=3 или 4 вся сеть уничтожена d (Sy) = 1 при dny = ¾ и 1. При n=5 и m=0 сеть действует в НУЭ, потерь нет Sy = 0, Uy= n, соответственно d (Sy) = 0, d (Uy)=1.

При m=1 узел (dny = 0,2) возможны пять вариантов атак, четыре на периферийные узлы.

Гибнет один из периферийных узлов, выживает четыре узла. При всех четырех атаках на периферийные узлы теряется четыре узла, выживает в сумме 16.

При атаке на центр гибнут все пять узлов, выживших нет. Итак, ?Sy = 4+5=9; = ?Sy/w=9/5; средняя доля погибших узлов d (Sy)= /n=9/25.

Общее число выживших узлов? Uy=16, среднее число =?Uy/w=16/5. Средняя доля выживших узлов d (Uy)= /n =16/25. В сумме d (Sy) + d (Uy) = 1.

При m=2 узла (dny = 0,4) возможны десять вариантов атак на сеть, шесть из них направлены на периферийные узлы, четыре — включая центр.

При атаке на периферийные узлы гибнут два узла, выживают три. После шести атак гибнет 12 узлов, выживает? Uy=3*6=18.

После атаки на центр и один из периферийных узлов гибнет вся сеть, теряется пять узлов, в сумме 20. Таким образом общие потери при всех десяти вариантах атак составят? Sy = 32 узла. Среднее число потерянных узлов на одну атаку Sy — ?Sy/w=32/10.Средняя доля потерь d (Sy)= 32/5. Среднее число выживших узлов =?Uy/w=18/10. Средняя доля выживших узлов d (Uy)= /n =18/(10*5).

При m=3 (dny = 0,6) также возможны десять вариантов атак, из них только в четырех вариантах выживают фрагменты в два узла, поэтому? Uy=8, =?/w=8/10. d (Uy)= /n=8/5. Гибнет в этих четырех вариантах? Sy=3*4=12 узлов. Шесть вариантов атак включают центр, что означает гибель всей сети и пяти узлов. В целом для шести атак гибнет 30 узлов, а для всех десяти итак гибнет 42 узла. Итак, ?Sy=42, =? Sy/w=4,2. d (Sy) = / n = 4,2 /5.

При m=4 или 5 сеть гибнет целиком Sy=5, d (Sy) = 1.

Замечаем, что числовые значения в формулах обладают общими свойствами: числитель равен квадрату разности (n=m), а знаменатель — квадрат размера сети.

d (Uy) = (n — m)2/n2 при гибели 0 < m < n — 2 узла.

Средняя доля погибших узлов

При m=n-1 выживает только один узел, что означает гибель всей сети, поэтому графики зависимости d (Sy) = f (dny) оканчиваются на линии d (Sy) = 1 в точках dny=(n-1)/n. С увеличением n график d (Sy) смещается в правый верхний угол

1.4 Гибель линейной сети. Разрыв дуг

При разрыве дуг погибшим считается узел, смежные дуги которого разорваны. Если узел висячий, то для его гибели достаточно разорвать единственную с ним дугу. Таких узлов в любой линейной сети два. Выжившими считаются узлы (два или более), содержащие связывающие их дуги. Поэтому в линейной сети весьма возможны случаи, когда число разорванных дуг может быть несколько, а общая сумма выживших фрагментов остается равной n. При любом значении n и разрыве одной дуги сумма погибших узлов равна двум, сумма выживших узлов образует арифметический ряд второго порядка с параметрами а1=4, Ь1=6, с=2. Поэтому доля погибших узлов при m=1 дуг. d (Sp1) = 2/(n (n — 1)), соответственно доля выживших узлов d (Up1) = 1 — 2/(n (n — 1)). Если m=n-2, то d (Up (n-2)) = 2/(m + 2). В общем случае d (Sp) = m (m+1)/(n (n — 1)). d (Up) = 1 — d (Sp) = 1 — m (m + 1)/(n (n — 1)). Зависимости доли погибших узлов от доли поражения дуг представлены на (Рисунок 4).

1.5 Гибель линейной сети. Атака на узлы

При атаке на узлы линейной сети средняя доля выживших узлов находится из соотношения d (Ump) — (n — m)/n; d (Smy) = 1 — d (Umy). После подстановки значений

d (Umy)= d (Ump) — (n-m)/n; d (Umy)=l-d (Umy)

После подстановки значений d (Umy) и упрощения получаем

Графические зависимости d (Sy) от n и dny показаны на (Рисунок 5). Они имеют выпуклый вид, то есть потери при гибели узлов существенно возрастают.

1.6 Кольцевая сеть. Разрыв дуг

Удаление одной избыточной дуги оставляет сеть связной размером п. Доля погибших узлов равна нулю в диапазоне доли поражения дуг различают 0 < dnp < n-1. С увеличением n этот диапазон сужается, приближаясь к левому нижнему углу (рис. 3). В общем случае доля погибших узлов при разрыве дуг d (Sp) = m (m — 1)/(n (n — 1)). Соответственно, доля выживших узлов d (Up) = 1 — d (Sp) = 1 — m (m-1)/(n (n-1)).При m=0 или 1 числитель d (Sp) обращается в нуль, соответственно, d (Sp) также равна нулю. С увеличением n при одинаковой доле поражения дуг значение d (Up) уменьшается, стремясь в пределе к (1 — m2/n2). На начальном участке зависимости d (Sp) проходят по оси X (d (Sp)=0), далее повторяют аналогичные зависимости линейных сетей со смещением равным n-1.

1.7 Кольцевая сеть. Гибель узлов

Кольцевая сеть при атаках на один из узлов трансформируется в линейную (замкнутую) сеть размером (n-1) узел. Среднее число выживших узлов Uy=?, d (Uy)=4/5. Среднее число погибших узлов Sy = 1. d (Sy) = 1/5. При значении 1 числа поврежденных узлов m>2, зафиксированная при m=1, умножается на долю выживших узлов линейной сети размером (n-1) при числе пораженных узлов, равном (m-1).

При m=1 правая скобка d (Uy) = (n — 1)/n; d (Sy) = 1/n.

Значения d (Sy) при гибели m узлов приведены в табл. 6. Графические зависимости d (Sy) для кольцевой сети при n=3,4,6 и 8 показаны на Рис. 3. На участке 0< dny<1/(n-1) графики совпадают с диагональю 0−1, при больших значениях образуют кабельную выпуклость относительно этой диагонали. Точка d (Sy)=1 по мере возрастания n приближается к правому верхнему углу.

Полносвязная сеть. Гибель узлов. При атаке на m узлов (при любом варианте) выжившая часть будет также полносвязной, но размером n-m. Поэтому доля погибших узлов при атаке на m узлов d (Sy)=. Доля выживших узлов d (Uy) = (nm) /n.

Полносвязная сеть при атаке на m узлов ведет себя как звезда такого же размера, но при разрыве m дуг.

На Рис. 4 дано сравнение d[Sp) и d (Sy) для звезды, линии и кольца размером п=8 узлов.

1.8 Выводы к первой главе

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

Глава 2. Исследование живучести ячеистых сетей по методу связности

При составлении полинома связности сети осуществляется полный перебор разрыва дуг от нуля до rизб. При нормальных условиях эксплуатации число прерванных дуг равно нулю. Это состояние, когда дуги целы. Вероятность этого состояния Pr-1. Далее разрываем одну дугу во всех вариантах (число их равно r). Вероятность этого состояния pr-1 q. При отсутствии висячих дуг и узлов и разрыве одной дуги сеть остается связной. Далее переходим к случаю разрыва двух дуг, вероятность этого состояния pr-2q2 при этом исключаем кольцо, так как в нем имеется всего одна избыточная дуга. Разрыв двух дуг в кольце в любом варианте приводит к потере связности сети и живучесть её становится равной нулю. Число вариантов разрыва двух дуг равно числу сочетаний r по 2. Так в сети вида «мостик» (n=4,r=5,rизб=2) число вариантов разрыва двух дуг равно 10. Из этих 10 исключаются два варианта разрыва двух дуг смежных с узлами, степень связности которых рана двум. Так как при этом сеть теряет этот узел и, соответственно теряет связность. После просмотра разрыва m дуг 0? m?rизб составляются, полином связности с переменными p и q, поскольку p+q=1, то приводим полином к одной переменной p. Очевидно, что такой метод требует большого объема вычислений и не исключает ошибок при расчете вручную. Требуется разработка программных средств.

При прокладке одной избыточной дуги, которые охватывают все узлы сети, получаем кольцо (ячейку), степень связности узлов кольца равна двум дугам (степенью связности называется число дуг, инцидентных данному узлу). В общем случае для кольца любого размера n вероятность связности равна. Для всех N выполняется граничные условия: если p=0, то Pc также равна нулю; если p=1, то и Pc=1 в диапазоне 0? p?1 функция непрерывна. Из анализа числовых графических зависимостей Pc=f (n, p) замечаем, что Рс падает с увеличением размеров кольца при одних и тех же значениях p. Верхнюю границу Pc дает кольцо размером три узла. Теперь предположим, что в сети имеются две ячейки и отсутствуют висячие узлы и дуги. При контакте двух ячеек дугой получаем «мостик», при распаде ячейки три узла (n=4,r=5). Полином связности имеет вид трехчлена. Минимальная связность равна 3, максимальная — 5 (это число дуг в исходном состоянии сети). Полином связности «мостика». Анализ числовых значений и графических зависимостей показывает, что с увеличением размера ячеек при одинаковых вероятностях разрыва дуг вероятность связности сети уменьшается. Верхнюю границу Pc дает «мостик» сеть с двумя треугольными ячейками смежных дугой. При контакте треугольных ячеек узлом получаются «песочные часы» (Рисунок 1б) (n=5,r=6) Полином связности такой сети имеет вид. По сравнению с «мостиком» эта структура менее прочна, т. е. она дает несколько меньшее значение Рс при одинаковой вероятности разрыва дуг.

При любом (но постоянном) числе избыточных дуг (ячеек) и одинаковой p увеличение размера ячеек приводит к уменьшению Pc, снижению её прочности. Верхнюю границу Pc дает сеть, состоящая из треугольных ячеек Число дуг связанного дерева этого же размера на единицу больше числа избыточных дуг (ячеек). Минимальная степень характеризует число дуг связанного дерева этого же размера. это размер (число узлов) сети. В полиноме, члены котрого расположены в порядке возрастания степеней, знаки чередуются, начиная с плюса.

Существенные значение на вероятность связанности оказывает число избыточных дуг. Последовательное их прибавление приводит к росту числа членов полинома связности, увеличению значений Pc при одинаковых p. Так в сети размером n=5 узлов возможны сети состояний:

а)	б)	в)

Рисунок 7 Варианты изображения сети а) кольцо б) мостик в) песочные часы

2.1 Оценка влияния размера ячеек на вероятность связности

Исследование связности кольца (rизб=const)

а)	б)	в)	г)	д)	е)

Теоретические зависимости:

а)PC=3p2−2p3	б)PC=4p3−3p4
в)PC=5p4−4p5	г)PC=6p5−5p6
д)PC=7p6−6p7	е)PC=8p7−7p8

Исследование связности «мостика» (rизб=2, n=var)

а)	б)	в)	г)	д)	е)

Теоретические зависимости:

а)PC=8p3−11p4+4p5	б)PC=11p4−16p5+6p6
в)PC=15p5−23p6+9p7	г)PC=14p5−21p6+8p7
д)PC=19p6−30p7+12p8	е)PC=24p7−39p8+16p9

Исследование связности «песочных часов» (rизб=2, n=var)

а)	б)	в)	г)	д)	е)

Теоретические зависимости:

а)PC=9p4−12p5+4p6	б)PC=12p5−17p6+6p7
в)PC=16p6−24p7+9p8	г)PC=20p7−31p8+12p9
д)PC=25p8−40p9+16p10	е)PC=15p6−22p7+8p8

Исследование связности сетей (rизб=3, n=var)

а)	б)	в)	г)	д)

Теоретические зависимости:

а)PC=16p3−33p4+24p5−6p6	б)PC=24p4−52p5+39p6−10p7
в)PC=30p5−65p6+48p7−12p8	г)PC=29p5−63p6+47p7−12p8
д)PC=41p6−92p7+70p8−18p9

2.2 Оценка влияния числа избыточных дуг на вероятность связности

Исследование связности сети размером (n=5)

а) Дерево	б) Кольцо	в) Домик	г) Кораблик	д) Четырехскатная крыша	е) Звезда без одной дуги	ж) Полносвязная звезда

Теоретические зависимости:

а)PC=p4	г)PC=5p4−4p5
б)PC=11p4−16p5+6p6	д)PC=21p4−44p5+32p6−8p7
в)PC=45p4−128p5+142p6−72p7+14p8	е)PC=75p4−264p5+388p6−294p7+114p8−18p9
ж)PC=125p4−528p5+970p6−980p7+570p8−180p9+24p10

Исследование связности равнопрочных сетей

а)	б)	в)	г)

Теоретические зависимости:

а)PC=75p5−223p6+255p7−132p8+26p9	б)PC=81p5−246p6+288p7−153p8+31p9
в)PC=384p5−1948p6+4368p7−5571p8+4344p9−2064p10+552p11−64p12	г)PC=384p5−1948p6+4368p7−5571p8+4344p9−2064p10+552p11−64p12

2.3 Выводы ко второй главе

1) В сети с постоянным числом избыточных дуг увеличение размера ячеек (размера сети) приводит к уменьшению вероятности связности. Максимальное значение Pc для дает ячейка в три узла.

2) Упрочнение сети постоянного размера прокладкой дополнительных избыточных дуг от нуля до (для полносвязной сети) приводит к увеличению вероятности связности.

3) Не отрицая значимости оценки живучести по методу связности сети, необходимо отметить его недостатки.

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

Глава 3. Разработка и программная реализация алгоритмов гибели и живучести ячеистых сетей

3.1 Постановка задачи

В первой главе представлены детерминированные модели трех типовых структур: линия, звезда и кольцо, как при разрыве дуг, так и при гибели узлов. Однако, структур значительно больше и это требует разработки алгоритма и программных средств.

Сеть сообщений формализована графом, содержащим n узлов, r дуг. Если сеть древовидная, то r=n-1. В ячеистой сети число дуг больше на число ячеек. Если r >m-1, то считаем, что сеть обладает избыточными дугами по сравнению с деревом.

Узлы сети полнодоступны как по исходящим, так и по входящим потокам. Узлы и дуги могут находиться только в двух состояниях: действовать (быть работоспособными) или отсутствовать. Гибель узла означает одновременно разрыв смежных с ним дуг и, наоборот, разрыв дуг инцидентных узлу означает его гибель. После разрыва одной и более дуг, гибели одного или нескольких узлов (0

Необходимо разработать программу отвечающую следующим требованиям:

· графический ввод сетей

· составление неприведённых уравнений связности

· приведение уравнений связности к p

· расчет вероятностей и вывод их в таблицу

· построение графических зависимостей вероятностей

· формирование отчета по результатам исследования

3.2 Описание алгоритма программы

живучесть модель сеть программа

Блок-схема основного алгоритма Рисунок 8

Ввод сети Рисунок 9

Формирование неприведённого уравнения связности Рисунок 10

Блок-схема алгоритма приведения коэффициентов Рисунок 11

Блок-схема алгоритма анализа гибели сети (разрыв дуг) Рисунок 12

Блок-схема алгоритма анализа гибели сети (атака на узлы) Рисунок 13

Процедура нахождения и сбора фрагментов сети Рисунок 14

Процедура получения списка доступных вершин Рисунок 15

Блок-схема функции реализующей алгоритм поисками минимального пути Дейкстеры Рисунок 16

Интерфейс программы

Для исследования связности сетей написана программа, позволяющая графическим методом задавать параметры сетей и получать наглядные числовые и графические зависимости.

Рисунок 17 Главное окно программы

Язык программирования: Object Pascal

Среда разработки: Lazarus IDE (GNU GPL)

Объем: 559 строчек, 3028 кб

Описание назначения основных переменных

· kord одномерный массив типа point размерностью 255 точек содержащий координаты точек возможного расположения вершин

· smez двухмерный динамический массив типа integer содержащий эталонную матрицу смежности исследуемой сети

· smez3 двухмерный динамический массив дублирующий эталонный smez, служит для исследования связности сети при разрыве 1,2.n дуг

· versh одномерный массив типа point размерностью 40 точек содержащий координаты вершин относительно границ поля отведенного для рисования

· form — одномерный массив строкового типа содержащий теоритические зависимости сети

· dug одномерный динамический массив содержащий все существующие в сети дуги. В формате «0102», где первые два числа первая вершина, а последние два — вторая вершина.

· nversh переменная численного типа содержащая сведения о количестве вершин сети.

· ndug переменная численного типа содержащая сведения о количестве дуг сети.

3.3 Результаты исследований гибели сетей при атаке на узлы

Исследование гибели кольца (rизб=const)

а)	б)	в)	г)	д)	е)

Количество изымаемых вершин	а)	б)	в)	г)	д)	е)
	0,333	0,250	0,200	0,167	0,143	0,125
	1,000	0,667	0,500	0,400	0,333	0,286
	1,000	1,000	0,800	0,650	0,543	0,464
		1,000	1,000	0,867	0,743	0,643
			1,000	1,000	0,905	0,804
				1,000	1,000	0,929
					1,000	1,000
						1,000

Исследование гибели «мостика» (rизб=2, n=var)

а)	б)	в)	г)	д)	е)

Количество изымаемых вершин	а)	б)	в)	г)	д)	е)
	0,250	0,200	0,167	0,167	0,143	0,125
	0,583	0,460	0,378	0,378	0,320	0,277
	1,000	0,760	0,617	0,617	0,518	0,446
	1,000	1,000	0,844	0,844	0,718	0,621
		1,000	1,000	1,000	0,891	0,786
			1,000	1,000	1,000	0,920
					1,000	1,000
						1,000

Исследование гибели «песочных часов»

а)	б)	в)	г)	д)	е)

Количество изымаемых вершин	а)	б)	в)	г)	д)	е)
	0,200	0,167	0,143	0,125	0,111	0,143
	0,480	0,389	0,327	0,281	0,247	0,327
	0,760	0,625	0,527	0,453	0,397	0,527
	1,000	0,844	0,722	0,627	0,551	0,722
	1,000	1,000	0,891	0,788	0,700	0,891
		1,000	1,000	0,920	0,833	1,000
			1,000	1,000	0,938	1,000
				1,000	1,000
					1,000

Исследование гибели сети с тремя ячейками

а)	б)	в)	г)	д)

Количество изымаемых вершин	а)	б)	в)	г)	д)
	0,250	0,200	0,167	0,167	0,143
	0,500	0,420	0,356	0,367	0,306
	1,000	0,720	0,583	0,592	0,494
	1,000	1,000	0,822	0,822	0,694
		1,000	1,000	1,000	0,878
			1,000	1,000	1,000
					1,000

Исследование влияния упрочнения сетей

а)	б)	в)	г)	д)	е)

Количество изымаемых вершин	а)	б)	в)	г)	д)	е)
	0,360	0,200	0,200	0,200	0,200	0,200
	0,640	0,500	0,460	0,440	0,400	0,400
	0,840	0,800	0,760	0,720	0,680	0,640
	1,000	1,000	1,000	1,000	1,000	1,000
	1,000	1,000	1,000	1,000	1,000	1,000

Исследование гибели равнопрочных сетей

a)	б)	в)	г)

Количество изымаемых вершин	а)	б)	в)	г)
	0,167	0,167	0,167	0,167
	0,333	0,333	0,333	0,333
	0,550	0,550	0,500	0,500
	0,800	0,800	0,733	0,733
	1,000	1,000	1,000	1,000
	1,000	1,000	1,000	1,000

3.4 Результаты исследований гибели сетей при атаке на дуги

Исследование гибели кольца (rизб=const)

а)	б)	в)	г)	д)

Количество изымаемых дуг	а)	б)	в)	г)	д)
	0,000	0,000	0,000	0,000	0,000
	0,333	0,167	0,100	0,067	0,048
	1,000	0,500	0,300	0,200	0,143
		1,000	0,600	0,400	0,286
			1,000	0,667	0,476
				1,000	0,714
					1,000

Исследование гибели «мостика» (rизб=2, n=var)

а)	б)	в)	г)	д)	е)

Количество изымаемых дуг	а)	б)	в)	г)	д)	е)
	0,000	0,000	0,000	0,000	0,000	0,000
	0,050	0,040	0,032	0,032	0,026	0,021
	0,200	0,140	0,105	0,105	0,082	0,065
	0,500	0,320	0,229	0,229	0,173	0,137
	1,000	0,600	0,413	0,413	0,306	0,238
		1,000	0,667	0,667	0,485	0,372
			1,000	1,000	0,714	0,542
					1,000	0,750
						1,000

Исследование гибели «песочных часов»

а)	б)	в)	г)	д)	е)

Вероятности связности

Количество изымаемых дуг	а)	б)	в)	г)	д)	е)
	0,000	0,000	0,000	0,000	0,000	0,000
	0,053	0,040	0,031	0,024	0,020	0,031
	0,160	0,119	0,092	0,073	0,059	0,092
	0,333	0,243	0,186	0,147	0,119	0,186
	0,600	0,421	0,316	0,248	0,200	0,316
	1,000	0,667	0,490	0,379	0,304	0,490
		1,000	0,714	0,545	0,433	0,714
			1,000	0,750	0,590	1,000
				1,000	0,778
					1,000

Исследование влияния упрочнения сетей

а)	б)	в)	г)	д)	е)

Количество изымаемых дуг	а)	б)	в)	г)	д)	е)
	0,200	0,000	0,000	0,000	0,000	0,000
	0,400	0,100	0,040	0,019	0,000	0,100
	0,600	0,300	0,140	0,069	0,014	0,300
	1,000	0,600	0,320	0,166	0,060	0,600
		1,000	0,600	0,333	0,157	1,000
			1,000	0,600	0,329
				1,000	0,600
					1,000

Исследование гибели сети с тремя ячейками

а)	б)	в)	г)	д)	е)

Количество изымаемых дуг	а)	б)	в)	г)	д)	е)
	0,200	0,000	0,000	0,000	0,000	0,000
	0,400	0,100	0,040	0,019	0,000	0,100
	0,600	0,300	0,140	0,069	0,014	0,300
	1,000	0,600	0,320	0,166	0,060	0,600
		1,000	0,600	0,333	0,157	1,000
			1,000	0,600	0,329
				1,000	0,600
					1,000

3.5 Результаты исследований по методу связности

Исследование связности кольца (rизб=const)

а)	б)	в)	г)	д)	е)

Теоретические зависимости:

а)PC=3p2−2p3	б)PC=4p3−3p4
в)PC=5p4−4p5	г)PC=6p5−5p6
д)PC=7p6−6p7	е)PC=8p7−7p8

Вероятности связности

Pc p	а)	б)	в)	г)	д)	е)
0,1	0,2 800	0,370	0,46	0,6	0,1	0,0
0,2	0,10 400	0,2 720	0,672	0,160	0,37	0,8
0,3	0,21 600	0,8 370	0,3 078	0,1 093	0,379	0,129
0,4	0,35 200	0,17 920	0,8 704	0,4 096	0,1 884	0,852
0,5	0,50 000	0,31 250	0,18 750	0,10 938	0,6 250	0,3 516
0,6	0,64 800	0,47 520	0,33 696	0,23 328	0,15 863	0,10 638
0,7	0,78 400	0,65 170	0,52 822	0,42 018	0,32 942	0,25 530
0,8	0,89 600	0,81 920	0,73 728	0,65 536	0,57 672	0,50 332
0,9	0,97 200	0,94 770	0,91 854	0,88 574	0,85 031	0,81 310
	1,0	1,0	1,0	1,0	1,0	1,0

Исследование связности «мостика» (rизб=2, n=var)

а)	б)	в)	г)	д)	е)

Теоретические зависимости:

а)PC=8p3−11p4+4p5	б)PC=11p4−16p5+6p6
в)PC=15p5−23p6+9p7	г)PC=14p5−21p6+8p7
д)PC=19p6−30p7+12p8	е)PC=24p7−39p8+16p9

Вероятности связности

Pc p	а)	б)	в)	г)	д)	е)
0,1	0,694	0,95	0,13	0,12	0,2	0,1
0,2	0,4 768	0,1 286	0,344	0,324	0,86	0,22
0,3	0,13 662	0,5 459	0,2 165	0,2 046	0,808	0,300
0,4	0,27 136	0,14 234	0,7 414	0,7 045	0,3 654	0,1 796
0,5	0,43 750	0,28 125	0,17 969	0,17 188	0,10 938	0,6 641
0,6	0,61 344	0,46 138	0,34 525	0,33 281	0,24 821	0,17 804
0,7	0,77 518	0,65 787	0,55 631	0,54 119	0,45 648	0,37 389
0,8	0,90 112	0,83 558	0,77 332	0,76 022	0,70 255	0,63 753
0,9	0,97 686	0,95 791	0,93 888	0,93 297	0,91 408	0,88 963
	1,0	1,0	1,0	1,0	1,0	1,0

Исследование связности «песочных часов» (rизб=2, n=var)

а)	б)	в)	г)	д)	е)

Теоретические зависимости:

а)PC=9p4−12p5+4p6	б)PC=12p5−17p6+6p7
в)PC=16p6−24p7+9p8	г)PC=20p7−31p8+12p9
д)PC=25p8−40p9+16p10	е)PC=15p6−22p7+8p8

Вероятности связности

Pc p	а)	б)	в)	г)	д)	е)
0,1	0,78	0,10	0,1	0,1	0,1	0,1
0,2	0,1 082	0,283	0,74	0,18	0,5	0,70
0,3	0,4 666	0,1 808	0,701	0,258	0,95	0,665
0,4	0,12 390	0,6 308	0,3 211	0,1 560	0,758	0,3 064
0,5	0,25 000	0,15 625	0,9 766	0,5 859	0,3 516	0,9 375
0,6	0,41 990	0,30 793	0,22 582	0,16 012	0,11 354	0,21 835
0,7	0,61 466	0,51 093	0,42 471	0,34 424	0,27 902	0,41 412
0,8	0,80 282	0,73 400	0,67 109	0,60 398	0,54 358	0,66 060
0,9	0,94 478	0,92 116	0,89 814	0,87 050	0,84 372	0,89 282
	1,0	1,0	1,0	1,0	1,0	1,0

Исследование связности сетей (rизб=3, n=var)

а)	б)	в)	г)	д)

Теоретические зависимости:

а)PC=16p3−33p4+24p5−6p6	б)PC=24p4−52p5+39p6−10p7
в)PC=30p5−65p6+48p7−12p8	г)PC=29p5−63p6+47p7−12p8
д)PC=41p6−92p7+70p8−18p9

Вероятности связности

Pc p	а)	б)	в)	г)	д)
0,1	0,1 293	0,192	0,24	0,23	0,3
0,2	0,8 250	0,2 413	0,602	0,582	0,162
0,3	0,21 865	0,9 428	0,3 523	0,3 403	0,1 401
0,4	0,40 038	0,22 528	0,11 174	0,10 805	0,5 836
0,5	0,59 375	0,40 625	0,25 000	0,24 219	0,16 016
0,6	0,76 550	0,60 653	0,44 230	0,42 986	0,33 182
0,7	0,89 249	0,78 753	0,65 615	0,64 102	0,55 601
0,8	0,96 666	0,91 750	0,84 410	0,83 100	0,78 224
0,9	0,99 581	0,98 415	0,96 368	0,95 777	0,94 490
	1,0	1,0	1,0	1,0	1,0

Исследование связности сети размером (n=5)

а) Дерево	б) Кольцо	в) Домик	г) Кораблик	д) Четырехскатная крыша	е) Звезда без одной дуги	ж) Полносвязная звезда

Теоретические зависимости:

а)PC=p4	г)PC=5p4−4p5
б)PC=11p4−16p5+6p6	д)PC=21p4−44p5+32p6−8p7
в)PC=45p4−128p5+142p6−72p7+14p8	е)PC=75p4−264p5+388p6−294p7+114p8−18p9
ж)PC=125p4−528p5+970p6−980p7+570p8−180p9+24p10

Вероятности связности

Pc p	а)	б)	в)	г)	д)	е)	ж)
0,1	0,0001	0,46	0,946	0,169	0,335	0,521	0,809
0,2	0,0016	0,672	0,12 864	0,2 146	0,3 924	0,5 687	0,8 194
0,3	0,0081	0,3 078	0,54 594	0,8 475	0,14 215	0,19 165	0,25 626
0,4	0,0256	0,8 704	0,142 336	0,205	0,31 412	0,39 419	0,48 965
0,5	0,0625	0,1875	0,28 125	0,375	0,52 343	0,61 328	0,71 093
0,6	0,1296	0,33 696	0,461 376	0,56 920	0,72 347	0,79 713	0,87 025
0,7	0,2401	0,52 822	0,657 874	0,75 295	0,87 526	0,91 817	0,95 751
0,8	0,4096	0,73 728	0,835 584	0,89 456	0,96 272	0,97 819	0,99 166
0,9	0,6561	0,91 854	0,957 906	0,97 627	0,99 556	0,99 765	0,99 949

Исследование связности равнопрочных сетей

а)	б)	в)	г)

Теоретические зависимости:

а)PC=75p5−223p6+255p7−132p8+26p9	б)PC=81p5−246p6+288p7−153p8+31p9
в)PC=384p5−1948p6+4368p7−5571p8+4344p9−2064p10+552p11−64p12	г)PC=384p5−1948p6+4368p7−5571p8+4344p9−2064p10+552p11−64p12

Вероятности связности

Pc p	а)	б)	в)	г)
0,1	0,55	0,59	0,228	0,228
0,2	0,1 267	0,1 349	0,4 188	0,4 188
0,3	0,6 730	0,7 105	0,17 706	0,17 706
0,4	0,19 269	0,20 154	0,40 308	0,40 308
0,5	0,38 672	0,40 039	0,64 844	0,64 844
0,6	0,61 101	0,62 594	0,83 921	0,83 921
0,7	0,80 953	0,82 087	0,94 733	0,94 733
0,8	0,93 900	0,94 424	0,98 979	0,98 979
0,9	0,99 238	0,99 326	0,99 939	0,99 939
	1,0	1,0	1,0	1,0

Выводы

Разработано и программно реализовано алгоритмы исследования гибели и связности ячеистых сетей с разными значениями числа ячеек

1) Установлено, что с увеличением размера ячейки доля поражения узлов уменьшается при постоянном числе изъятых дуг

2) Изменение размера ячеек при n=const практически не меняет значения доли поражения.

3) С увеличением числа избыточных дуг доля погибших узлов уменьшается

4) В сети с постоянным числом избыточных дуг увеличение размера ячеек (размера сети) приводит к уменьшению вероятности связности. Максимальное значение Pc для дает ячейка в три узла.

5) Упрочнение сети постоянного размера прокладкой дополнительных избыточных дуг от нуля до (для полносвязной сети) приводит к увеличению вероятности связности.

6) Не отрицая значимости оценки живучести по методу связности сети, необходимо отметить его недостатки.

7) Вероятность связности не допускает гибели даже одного из узлов, а это противоречит практической эксплуатации. Вероятность связности сети не допускает распада сети на фрагменты, которые продолжают действия, если их размер два узла или более. Вероятность связности не отвечает на вопрос: на сколько и где повышается нагрузка дуг после удаления избыточных дуг.

1. A contribution to the theory of chromatic polynomials. Tute, W.T. 6, Canada: Canadian Mathematical Society, 1954 г.

2. Синтез и анализ живучести сетевых систем. Громов Ю. Ю., Драчев В. О., Набатов К. А., Иванова О. Г. Тамбов: Издательство ТГТУ, 2007 г.

3. Отказоустойчивость распределенных систем. А.И., Никитин. 1987 г., Управляющие системы и машины.

4. Модель комплексной оценки и обеспечения живучести распределенных информационно-вычислительных систем. Ю.Е., Мельников. 1988 г., Материалы II Всесоюзной науч.-техн. конф.

5. Математическое программирование. М., Мину. 1990 г., Наука.

6. Design of reliable networks. Jan, R.-H. 1993 г., Computers and Operations Research.

7. Алгоритмы и программы решения задач на графах и сетях. Нечепуренко, М. И. Новосибирск: б.н., 1990 г., Новосибирск: Наука.

8. Войлоков В. И. Взаимосвязь показателей живучести многополюсных сетей без избыточности // Труды учебных институтов связи ТУИС /ЛЭИС, — 1990, № 151, с. 171−177.

9. Войлоков В. И., Птицын Г. А. Оценка живучести многополюсных сетей связи //Сборник материалов по проектированию. — М.: Гипросвязь, 1989. — ч.1,

10. Надежность и живучесть систем связи // Под ред. Дудника Б. Я. — М. Радио и связь, 1984. -216с.

11. Воробьев В. И., Меижовский КА Способ определения живучести связи //Электросвязь. -1988, № 12, с. 12−14.

12. Флейшман Б. С. и др. Исследование живучести экосистемы на основе ма-тематической модели. — Владивосток: Институт проблем управления, 1972

13. Стекольников Ю. И. Живучесть систем. — СПб.: Политехника, 2002. — 156с.

14. Птицын Г. А. Живучесть динамических сетей связи. Учебное пособие/Под редакцией проф. Петракова А. В. — М.: МТУСИ, 2008. — 96с

15. Zolfaghari Ali, Kaudel Fred J. / Framework for network survivability performance //IEEE J. Selec. Areas. Commun, 1994,12, № 1, c. 46−51.

Приложения

Программный код реализации графического ввода сети

procedure TForm1. Image1MouseDown (Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

var i, j, p, tek: integer;

begin

Image1.Canvas.Brush.Color:=clBlack;

Image1.Canvas.Pen.Color:=clBlack;

Image1.Canvas.Pen.Mode := pmMask;

//ShowMessage (inttostr (x)+' '+inttostr (y));

p:=0;

tek:=1;

for i:=0 to 225 do begin

if (x>kord[i]. x-10) and (xkord[i]. y-10) and (y

Image1.Canvas.EllipseC (kord[i]. x, kord[i].y, 3,3);

Image1.Canvas.Pen.Width:=4; //возвращаем все как было

for j:=0 to 40 do begin // проверка новая вершина или нет

if (versh[j]. x=kord[i].x) and (versh[j]. y=kord[i].y) then begin

p:=1;

tek:=j;

Break;

end;

end;

if p=0 then begin // добавление новой вершины

versh[nversh]: =kord[i];

tek:=nversh;

//Image1.Canvas.TextOut (kord[i]. x, kord[i].y, InttoStr (nversh));

nversh:=nversh+1;

end;

smez[pred, tek]: =1;

smez[tek, pred]: =1;

smez[tek, tek]: =0;

pred:=tek;

if prev. x<>0 then begin

p:=0;

Image1.Canvas.MoveTo (prev.x, prev. y);

Image1.Canvas.LineTo (kord[i]. x, kord[i].y);

end;

prev:=kord[i];

end;

end;

//перерисовка всех точек

for i:=0 to nversh-1 do begin

Image1.Canvas.Pen.Width:=14;

Image1.Canvas.EllipseC (versh[i]. x, versh[i].y, 3,3);

Image1.Canvas.Font.Color:=clWhite;

Image1.Canvas.Pen.Mode := pmMask;

Image1.Canvas.Brush.Color:=clBlack;

Image1.Canvas.TextOut (versh[i]. x-3,versh[i].y-6,InttoStr (i));

end;

end;

procedure TForm1. Button3Click (Sender: TObject); //очистка

var i, j: integer;

begin

jpg.Canvas.Clear;

prev.x:=0;

Form1.FormShow (Sender);

for i:=0 to 200 do begin // перебор

for j:=0 to 200 do begin

smez[i, j]: =-1;

end;

end;

for i:=0 to 40 do begin

versh[i]. x:=0 ;

versh[i]. y:=0 ;

dug[i]: ='';

end;

nversh:=0;

pred:=0;

ndug:=0;

nz:=0;

nraz:=0;

end;

Программный код формирования уравнения связности и нахождение численных значений

procedure TForm1. Button6Click (Sender: TObject);

var i, ig, j, n, g, g2,h, tek, pred, kk, p: integer;

html: TIpHtml;

ms:TMemoryStream;

MyString:AnsiString;

pr:real;

koef: array[0.40] of integer;

koef2: array[0.40] of integer;

s, str, ps, vr: string;

new:boolean;

res: Word;

begin

nraz:=2;

prev.x:=0;

n:=0;

h:=1;

kk:=0;

for i:=0 to 40 do begin

koef[i]: =0;

koef2[i]: =0;

end;

for i:=0 to nversh-1 do begin // заполнение массива дуг

for j:=i+1 to nversh-1 do begin

if smez[i, j]=1 then begin

dug[h]: =formatm (i)+formatm (j);

h:=h+1;

end;

end;

end;

n:=h-1;

Label2.Caption:='r='+inttoStr (n);

Label3.Caption:='n='+inttoStr (nversh);

str:='';

kk:=0;

res:=1;

if n>17 then begin // ограничение

res := MessageDlg ('Данная процедура может занять более '+FloattoStr (power (2,(n-17)))+' минут. Продолжить?', mtInformation, [mbOk, mbCancel], 0);

end;

if res<>2 then begin

for i:=1 to (1 shl n)-1 do begin

for j:=1 to n do if (i and (1 shl (j-1)))>0 then

begin

str:=str+dug[j];

end;

if true then begin //length (str)

g2:=1;

smez3:=smez; // дублируем исходную матрицу

for g:=0 to round (length (str)/4)-1 do begin // удаление дуг

smez3[strtoint (copy (str, g2,2)), strtoint (copy (str, g2+2,2))]: =-1;

smez3[strtoint (copy (str, g2+2,2)), strtoint (copy (str, g2,2))]: =-1;

g2:=g2+4;

//ShowMessage (str+' '+inttostr (connect));

end;

//if (length (str)/4)=2 then Memo1. Append (str+' '+inttostr (connect));

if connect=0 then begin

koef[round (length (str)/4)]: =koef[round (length (str)/4)]+1;

if round (length (str)/4)>kk then kk:=round (length (str)/4);

end;

str:='';

end;

end;

//обработка строки

koef[0]: =1;

h:=h-1;

vr:=vr+'+1*p^'+inttostr (h)+'+';

for i:=1 to kk do Memo1. Append (inttostr (koef[i])+'+p^');

for i:=1 to kk do vr:=vr+naq (koef[i], h-i, i)+'+';

for ig:=0 to h+1 do begin

p:=pos ('p^'+inttostr (h-ig), vr);

if p<>0 then begin

while pos ('p^'+inttostr (h-ig), vr)<>0 do begin

p:=pos ('p^'+inttostr (h-ig), vr);

j:=p;

str:='';

repeat

j:=j-1;

until (vr[j]='+') or (vr[j]='-') or (j=0);

for g:=j to p-2 do str:=str+vr[g];

koef2[h-ig]: =koef2[h-ig]+strtoint (str);

vr[p]: ='t';

end;

end;

end;

if not Otch. Checked then StringGrid1. ColCount:=2;

if Otch. Checked then StringGrid1. ColCount:=notch+2;

StringGrid1.Cells[0,0]: ='p';

StringGrid1.Cells[0,1]:='0';

StringGrid1.Cells[1+notch, 1]:='0';

StringGrid1.Cells[1+notch, 0]:=bukv[notch]+')';

for i:=1 to 10 do begin

pr:=0;

for ig:=1 to h+1 do

if koef2[ig]<>0 then begin

pr:=pr+koef2[ig]*power ((i/10), ig);

end;

StringGrid1.Cells[0,i+1]: =floattostr (i/10);

StringGrid1.Cells[1+notch, i+1]:=Format ('%.5n',[pr]); //вывод в таблицу

end;

MyString:='P_C='; // нормальное отображение

for ig:=1 to h+1 do

if koef2[ig]<>0 then begin

if koef2[ig]>0 then MyString:=MyString+'+'+inttostr (koef2[ig])+'p^{'+inttostr (ig)+'}'

else MyString:=MyString+inttostr (koef2[ig])+'p^{'+inttostr (ig)+'}';

end;

MyString:=MyString+'

';

html:=TIpHtml.Create;

ms:=TMemoryStream.Create;

ms.Write (MyString[1], Length (MyString));

if otch. Checked then begin /// отчет!

form[notch]: =MyString;

notch:=notch+1;

//Image1.Picture.SaveToFile (IntToStr (notch)+'.bmp');

jpg.Assign (Image1.Picture.Bitmap);

jpg.CompressionQuality:= 100;

jpg.SaveToFile (IntToStr (notch)+'.jpg');

if notch=6 then Button6. Enabled:=false;

end;

ms.Position:=0;

html.LoadFromStream (ms);

IpHtmlPanel1.SetHtml (html);

ms.free;

end;

end;

Программный код построения графиков вероятности связности

procedure TForm1. Button11Click (Sender: TObject);

var i, j, nox, noy, XI, Yi: integer;

Rect: TRect;

Points: Array[0.3] of TPoint;

begin

Image2.Canvas.Brush.Color:=clWhite; //присваиваем кисти цвет формы.

Image2.Canvas.FillRect (0,0,Width, Height); //заливаем Image выбранным цветом кисти.

Image2.Canvas.Pen.Width:=1;

Image2.Canvas.Pen.Color:=clBlack;

Image2.Canvas.Line (25,Image2.Height-15,Image2.Height-5,Image2.Height-15); // горизонтальная палка ох

Image2.Canvas.Line (Image2.Height-5,Image2.Height-15,Image2.Height-15,Image2.Height-11); // стрелочка

Image2.Canvas.Line (Image2.Height-5,Image2.Height-15,Image2.Height-15,Image2.Height-19); // ->

Image2.Canvas.Line (25,Image2.Height-15,25,10); // вертикальная палка оу

Image2.Canvas.Line (25,10,29,20); // cтрелка

Image2.Canvas.Line (25,10,21,20); // ^

Image2.Canvas.Font.Size:=7;

nox:=10;

noy:=10; // кол-во меток по Оу

noy:=maxoy;

nox:=maxoy;

for i:=0 to noy do begin { длина оси отступ } // черточки и цифры по осям

Image2.Canvas.TextOut (trunc ((Image2.Height-45)/nox)*i+25,Image2.Height-10,Form1.StringGrid1.Cells[0,i+1]);

Image2.Canvas.Line (trunc ((Image2.Height-45)/nox)*i+25,Image2.Height-10,trunc ((Image2.Height-45)/nox)*i+25,Image2.Height-20); // черточки |

Image2.Canvas.TextOut (5,Image2.Height-10-trunc ((Image2.Height-45)/noy)*i, Form1. StringGrid1.Cells[0,i+1]);

Image2.Canvas.Line (20,Image2.Height-15-trunc ((Image2.Height-45)/noy)*i, 30, Image2. Height-15-trunc ((Image2.Height-45)/noy)*i);

end;

Image2.Canvas.Pen.Color:=clGray;

for i:=1 to noy do begin // серые полоски

Image2.Canvas.Line (trunc ((Image2.Height-45)/nox)*i+25,Image2.Height-15,trunc ((Image2.Height-45)/nox)*i+25,10); // полосочки |

Image2.Canvas.Line (25,Image2.Height-15-trunc ((Image2.Height-45)/noy)*i, Image2. Height-15,Image2.Height-15-trunc ((Image2.Height-45)/noy)*i);

end;

Image2.Canvas.Pen.Width:=2;

Image2.Canvas.Pen.Mode := pmMask;

for j:=1 to StringGrid1. ColCount-1 do begin // по столбцам

Image2.Canvas.Pen.Color:=Colores[j mod 7];

Image2.Canvas.Brush.Color:=Colores[j mod 7];

for i:=2 to StringGrid1. RowCount-1 do begin // по строчкам

if StringGrid1. Cells[0,i]<>'' then begin { FloatToStr (10*(i-1)/skokan (j)) Grx (StringGrid1.Cells[0,i-1])}

Memo1.Append (StringGrid1.Cells[0,i]+' / '+InttoStr (skokan (j)));

Figur (Grx (StringGrid1.Cells[0,i]), Gry (StringGrid1.Cells[j, i]), j);

Image2.Canvas.Line (Grx (StringGrid1.Cells[0,i-1]), Gry (StringGrid1.Cells[j, i-1]), Grx (StringGrid1.Cells[0,i]), Gry (StringGrid1.Cells[j, i]));

end; // это нормальный график

end;

Image2.Canvas.Line (Image2.Height+20,25*j, Image2. Height+30,25*j);

Figur (Image2.Height+25,25*j, j);

Image2.Canvas.Pen.Mode := pmCopy;

Image2.Canvas.Brush.Color:=clWhite;

Image2.Canvas.TextOut (Image2.Height+35,25*j-7,bukv[j-1]);

end;

end;

Программный код расчета гибели сети детерминированным способом при разрыве дуг

procedure TForm1. Button10Click (Sender: TObject);

var i, ig, j, n, g, g2,h, tek, pred, kk, p: integer;

html: TIpHtml;

ms:TMemoryStream;

MyString:AnsiString;

pr:real;

koef: array[0.40] of integer;

koef2: array[0.40] of integer;

s, str, ps, vr: string;

new:boolean;

res: Word;

// для графика, которого нет

kff:real;

maxk:integer;

begin

kostgraph:=0;

nraz:=2;

prev.x:=0;

n:=0;

h:=1;

kk:=0;

for i:=0 to 40 do begin

koef[i]: =0;

koef2[i]: =0;

end;

for i:=0 to nversh-1 do begin // заполнение массива дуг

for j:=i+1 to nversh-1 do begin

if smez[i, j]=1 then begin

dug[h]: =formatm (i)+formatm (j);

h:=h+1;

end;

end;

end;

n:=h-1;

Label2.Caption:='r='+inttoStr (n);

Label3.Caption:='n='+inttoStr (nversh);

mnbu[notch]: ='(n='+inttoStr (nversh)+')';

str:='';

kk:=0;

res:=1;

if n>17 then begin // ограничение

res := MessageDlg ('Данная процедура может занять более '+FloattoStr (power (2,(n-17)))+' минут. Продолжить?', mtInformation, [mbOk, mbCancel], 0);

end;

if res<>2 then begin

for i:=1 to (1 shl n)-1 do begin

for j:=1 to n do if (i and (1 shl (j-1)))>0 then

begin

str:=str+dug[j];

end;

if true then begin //length (str)

g2:=1;

smez3:=smez; // дублируем исходную матрицу

for g:=0 to round (length (str)/4)-1 do begin // удаление дуг

smez3[strtoint (copy (str, g2,2)), strtoint (copy (str, g2+2,2))]: =-1;

smez3[strtoint (copy (str, g2+2,2)), strtoint (copy (str, g2,2))]: =-1;

g2:=g2+4;

end;

//ShowMessage (str+' '+inttostr (connect));

//if (length (str)/4)=2 then Memo1. Append (str+' '+inttostr (connect));

koef[round (length (str)/4)]: =koef[round (length (str)/4)]+Length (jivnew);

koef2[round (length (str)/4)]: =koef2[round (length (str)/4)]+1;

//Memo1.Append ('anton:'+IntToStr (anton2));

if round (length (str)/4)>kk then kk:=round (length (str)/4);

end;

str:='';

end;

end;

for i:=1 to kk do vr:=vr+InttoStr (koef[i])+' '+InttoStr (i)+'+';

Memo1.Append (vr);

if not Otch. Checked then StringGrid1. ColCount:=2;

if Otch. Checked then StringGrid1. ColCount:=notch+2;

StringGrid1.Cells[0,0]: ='Количество изымаемых дуг';

StringGrid1.Cells[1+notch, 0]: =bukv[notch]+')';

StringGrid1.Cells[0,1]:='0';

StringGrid1.Cells[1+notch, 1]:=IntToStr (0);

//koef[kk]: =0;

maxk:=0; // для графика

for i:=0 to 10 do begin

if koef2[i]<>0 then begin

pr:=0;

pr:=koef[i]/koef2[i];

StringGrid1.Cells[0,i+1]: =floattostr (i);

StringGrid1.Cells[1+notch, i+1]: =Format ('%.3n',[1-(pr/nversh)]); //вывод в таблицу (1-)

maxk:=maxk+1;

end

else StringGrid1. Cells[1+notch, i+1]: ='0';

end;

if otch. Checked then begin /// отчет

form[notch]: =MyString;

notch:=notch+1;

//Image1.Picture.SaveToFile (IntToStr (notch)+'.bmp');

jpg.Assign (Image1.Picture.Bitmap);

jpg.CompressionQuality:= 100;

jpg.SaveToFile (IntToStr (notch)+'.jpg');

if notch=6 then Button6. Enabled:=false;

end;

end;

function jivnew: string;

var uze: array[0.13] of boolean;

str, sum: string;

i, j, k, kf: integer;

begin

for i:=0 to 13 do uze[i]: =false;

sum:='';

kf:=0;

for i:=0 to nversh-1 do begin

if not uze[i] then begin str:=anton1(i);

if str<>'' then for j:=1 to Length (str) do uze[StrToInt (str[j])]: =true;

//str:=anton1(i);

if Length (str)<>1 then sum:=sum+str;

end;

end;

//Form1.Memo1.Append (sum);

jivnew:=sum;

end;

function anton1(q:integer):string;

var

b:array[0.25]of boolean;//список просмотренных вершин

d:array[0.25] of longint;//кротчайшие расстояния

i, j, m, v, n: integer;

s:string;

begin

//Ввод данных

n:=nversh-1;

// q := 0; //начальная вершина

if (q < 1) or (q > n) then q := 1;

for i := 0 to n do

for j := 0 to n do

//Расчет

fillchar (b, sizeof (b), 0);

fillchar (d, sizeof (d), 10 000);

d[q] := 0;//расстояние до начальной вершины

for i:=0 to n do

begin

m := 1000;

for j := 0 to n do

if ((d[j] <= m) and (not b[j])) then

begin

m:=d[j];

v:=j;

end;

b[v] := true;

for j := 0 to n do

if ((smez3[v, j]<>-1)and (not b[j]) and (d[v]+smez3[v, j]

d[j]: =d[v]+smez3[v, j];

end;

anton1:='';

for i := 0 to n do begin

if d[i]

anton1:=anton1+inttostr (i);

end;