|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
|
|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Методические указания к контрольному заданиюСтр 1 из 13Следующая ⇒
Методические указания к контрольному заданию Общие методические указания Контрольное задание выполняется в отдельной тетради, страницы которой должны быть пронумерованы. Задачи решаются в том же порядке, в каком при-ведены в задании. Перед решением задачи записываются ее условия и исходные данные для требуемого варианта. Решения должны быть снабжены краткими пояснениями. В конце работы приводятся список используемой литературы. Номер варианта задания выдается преподавателем. Методические указания к задаче 1 Вначале необходимо усвоить ряд терминов и определений, относящихся к теоретической модели сети. Сеть связи отображается в виде графа, вершины которого сопоставляются с узлами (узлами первичной или узлами коммутации вторичной сети), а ребра (ветви), соединяющие узлы, линиям связи первичной сети или пучкам каналов вторичной сети. В зависимости от свойств линий связи, ребра могут быть ориентированными (направленными) или неориентированными (ненаправленными). Как вершине, так и ребру может быть приписан вес или сово-купность весов, характеризующих их свойства, например надежность, пропускная способность, длина линии связи и т.п. Для передачи информации в сети от узла коммутации УК i к УК j должен быть использован путь Путь может записываться перечнем ребер. При этом будем считать, что, если ребро в данном пути направлено от узла с меньшим индексом к узлу с большим большим индексом, то оно обозначается символами, например, a, b, c…. В про- тивном случае - Сечением сети по отношению к узлам i и j называется минимальная совокуп-ность ребер, которые нужно изъять из сети с тем, чтобы узлы УК i к УК j оказались в разных, не связанных между собой, частях сети. Существуют различные методы отыскания путей в графе сети. Рассмотрим графический и матричный метод отыскания путей. Графический метод является одним из наиболее простых и поддающихся машинизации способов построения дерева путей. Этот способ позволяет опреде-лить все простые пути от одного заданного узла ко всем остальным узлам сети и состоит из построения дерева путей и просотру по этому дереву каждого пути. Дерево путей для заданного узлу i строится по графу сети с использованием следующего алгоритма: 1. Отмечаем узел i и выбираем смежные с данным узлом узлы графа сети. 2. Получаем узлы узлы первого яруса по отношению к узлу i. 3. Для образования узлов r-го яруса (r = 2, 3, …, h, где h – максимально допустимое число переприемных участков в пути): а) поочередно рассматриваем узлы (r – 1)-го яруса; б) для каждого узла k в (r – 1) –ом ярусе выбираем поочередно смежные узлы; в) исключаем номера узлов, относительно которых были образованы подмножества узлов в предыдущих ярусах, связанных узлом k. Оставшиеся узлы соответствуют подмножеству узлов r-го яруса, образованного узлом k. 4. Построение дерева путей продолжается до заданного h-го яруса. Имея дерево путей относительно узла i, легко проследить любой из возможных путей с заданным числом переприемных участков r (рангом пути) между фиксированным узлом i и произвольным узлом j. Для этой цели: 1. В r-ом ярусе дерева, образованного относительно узла i, находим заданный конечный узел j. 2. Выписываем номера узлов, относительно которых образованы подмножества, связанные с выбранным узлом j. Выписанные узлы принадлежат пути от узла i к узлу j.
Пример В качестве примера построим дерево путей для узла 6 сети, представленной виде графа на рисунке 5.
Рис.5. Структура сети
Определим множество путей от узла 6 к другим узлам сети графическим мето-дом. Выписываем исходный узел 6, который относится к нулевому ярусу. По графу сети определяем смежные с узлом 6 узлы – 1, 2, 4 и 5, которые образуют узлы первого яруса. Для узла 1 выбираем узлы 2 и 6. Так как узел 1 связан с узлом 6 нулевого яруса, то во втором ярусе записываем только узел 2. Для узла 2 в под-множество узлов второго яруса попадают узлы 3 и 5. Для узла 4 в подмножество узлов второго яруса попадает узлы 3. Для узла 5 в подмножество узлов второго яруса попадает узел 4. Аналогичным образом определяются подмножество узлов третьего и последующих ярусов. Узлы смежных ярусов связываются между собой соответствуюшими ребрами графа сети с учетом исключения путей с повторяю-щимися узлами в этих путях. На рисунке 7 приведено дерево путей для узла 6. Используя данное дерево путей, запишем пути не более третьего ранга от узла 6 до узла 5:
Рис.6. Дерево путей ранга r ≤ 3 для узла 6
Матричный метод основан на составлении структурной матрицы B, с последующим ее разложением. Матрица B – квадратная матрица, строки и столб-цы которой сопоставлены узлам сети. Связь внутри узла отображается единицей (1). Если связи между узлами нет, то вхождение матрицы равно нулю (0). Значения матрицы B рассматриваются как элементы булевой алгебры с двумя значениями: 1- соединение есть, 0 – соединения нет. Поэтому матрицу B преобра-зуют как булеву матрицу, применяя к ней аппарат булевой алгебры. При этом будем использовать следующие основные правила и законы булевой алгебры. 1) 2) 1 3) 0 4) 5) В дальнейшем знак логического умножения Множество путей mij может быть найдено раскрытием минора структурной матрицы B, путем вычеркивания i-го столбца и j-ой строки в матрице В, и последующим разложением полученного определителя. При вычислении определителей матриц учитываем следующее: а) если в каждой строке (столбце) определителя есть хотя бы одна единица, то определитель равен 1; б) если в определителе строка (или столбец) состоит из одних нулей, то опреде- литель равен нулю; в) если строка (столбец) содержит одну единицу, а остальные нули, то ее (его) можно вычеркнуть; г) для определения номера строки на последующем шаге разложения определи-теля, необходимо выбрать любое ребро графа сети из строки определителя, соот-ветствующей рассматриваемому узлу на данном шаге разложения определителя. Номер строки на следующем шаге разложения определяется номером узла, с которым выбранное ранее ребро связывает рассматриваемый узел графа сети. Рассмотрим пример определения путей в сети от узла i до узла j матричным методом.
Пример Определим совокупность путей от узла 6 до узла 5 матричным методом, используя структуру сети представленную на рисунке 5. Структурная матрица B для рассматриваемого примера имеет вид:
B=
Для определения множества путей m65 из матрицы B вычеркнем столбец 6 и строку 5, поскольку узел 6 является исходящим, а узел 5 – входящим. Получаем определитель, представленный на рис. 7а. Обращаемся к строке 6 определителя (рис.7а), так как узел 6 является исходящим. Анализ строки 6 показывает, что узел 6 связан с узлами 1, 2, 4 и 5 соответственно ребрами Далее проведем разложение определителей 7б, 7в и 7г по ненулевым членам соответственно 1-ой, 2-ой и 4 ой строкам. Определители 7ж, 7е равны нулю, так как в каждой строке и столбце указанных определителей имеются нули. Опреде-литель 7и равен единице, так как в каждой строке определителя имеется по одной единицы. Разложение определителей 7е и 7к осуществим соотетственно по ненулевым членам 2-ой строки и 3-ей строки. Получаем определители 8л и 8м. После разложения определителя 7л получаем 0, а после разложения определителя 7м получаем 1. Окончательно получим выражение: m65= Таким образом, от узла 6 к узлу 5 могут быть использованы четыре простых пути: Следовательно, множество путей ранга не более 3-его (r ≤ 3) от узла 6 к узлу 5, полученных как графическим, так и матричным методами, совпадают. Последовательность разложения структурной матрицы B при определении путей от узла 6 к узлу 5 представлена на рис. 7.
m65 = =
а)
= б) в)
г) д)
=
е) ж)
з) и)
к) л)
м) =
Рис.7. Определение путей от узла 6 до узла 5 матричным методом.
Для нахождения сечений (квазисечений, т.е. сечения, рассекающие пути до определенного ранга), следует заменить функцию mij на двойственную, заменив операции логического сложения (коньюнкции) на операции логического умноже-ния (дизъюнкции) и наоборот. Затем произвести упрощение полученного выраже-ния. Каждое слагаемое данного выражения и будет искомое сечение.
Пример Определим множество квазисечений для множества путей r ≤ 3 от узла 6 до узла5. Из рассмотренного выше примера имеем:
m65=
Заменим функцию m65 на двойственную S65 и, произведя операции умножения и сложения, получим слагаемые, определяющие квазисечения между узлами 6 и5. S65 = ( = Удаление ребер из графа сети, входящих в любое из полученных слагаемых, делает сеть несвязанной по отношению к узлам 6 и 5 при использовании путей ранга не более трех.
Емкость нумерации Емкость системы нумерации это – предельная, теоретически воз-можная суммарная емкость всех местных сетей страны при данной сис- теме нумерации. Общее число индивидуальных абонентов на местных сетях, следовательно, не может превысить емкость нумерации. Емкость системы нумерации зависит от принятой системы нумерации. Если обозначить емкость нумерации через N, число знаков в номере через k, а число цифр, используемых для каждого знака через
N = где При решении задачи 2 не следует забывать, что в некоторых вариантах заданным условиям могут удовлетворять несколько значений B и b. Необходимо выбрать такое сочетание используемых в качестве B и b цифр, чтобы получить максимальную величину емкости нумерации.
Пример Определить максимальную емкость открытой системы нумерации национа-льной сети, если междугородный номер типа ABCabxxxxx (десятизначный) и зоновый номер типа abxxxxxx (семизначный). При этом междугородный номер и зоновый номера различаются по второй цифре, т.е. B и b не должны совпадать. Кроме того, в таблице 2 указаны значения цифр, которые не могут принимать знаки: A ≠ 1, 9, 0; a ≠ 1, 0 и b ≠ 3, 5, 7. Так как B и b не должны совпадать, а b не может принимать значения 3, 5 и 7, для определения максимального значения сочетания B и b построим таблицу.
Максимальная величина mB* mb = 25 соответствует третьему варианту. Используя полученный результат и формулу N = рассчитаем максимальную емкость нумерации при заданных выше условиях.
N = 7*5*10*8*5*10*10*10*10*10 = 1.4*
Модели сети связи При исследовании структурной надежности можно рассматривать две модели сети: детерминированная сеть или сеть стохастическая (случайная) в зависи-мости от того, учитывается или игнорируется случайный характер внешних или внутренних воздействий на элементы моделируемой реальной сети связи. Элементы детерминированной сети принимают абсолютно надёжными эле-ментами или абсолютно ненадежными. В стохастическойсети некоторые или все элементы (узлы или линии связи) обладают конечной надежностью pi (0< pi < 1), где pi вероятностный показатель надежности i - ого элемента сети. Теоретической основой для исследования сетей, как первого, так и второго типа, является теория графов, теория вероятностей, булева алгебра. Теория графов позволяет разработать формальные приемы исследования стру-ктурной надежности сетей связи не зависимо от их сложности. Информацию, со-держащую в графе, можно представить алгебраической матрицей для последую-щей автоматизации исследований на ЭВМ. Для исследования детерминированной сети в качестве математической модели можно использовать простой, конечный ориентированный или неориентированный или смешанный граф G = (A, B), где A – множество вершин графа, а B – множество ребер графа. Каждому ребру сопоставляется не более двух вершин, которые называются концевыми. При этом вершины графа поставлены в соответствие узлам сети связи, а ребры графа – линиям связи. Для исследования стохастической сети в качестве математической модели используется простой, конечный ориентированный или неориентированный или смешанный взвешенный граф G'=(A, B, K). Как и в случае детерминированной сети, вершины графа поставлены в соответствие узлам сети связи, а ребры графа – линиям связи. Веса злементов графа (множество K ) представляют собой пока-затели надежности элементов сети связи, например, коэффициенты готовности соотвествующих элементов сети (рис.17).
Рис. 17. Математические модели стохастической сети
Пример 1
Определить надежность связи (вероятность связности) узла 1 с узлом 3 - Р13 в сети, граф которой показан на рисунке 18. При этом для связи указанных узлов 1 и 3 используются пути:
Рис. 18. Граф сети
Для определения Р13 воспользуемся выше приведенным алгоритмом расчета на- дежности связи. Поскольку пути заданы, реализацию алгоритма начнем со второго шага. 1. Поставим каждому из указанных путей случайные события Аi, соответствующие исправным состояниям этих путей. Событие А1 поставим в соответствие путь 3. Определим вероятность наступления событий Аi, зная маршруты путей и коэффициенты готовности узлов и линий связи сети, а также, в качестве примера, вероятность совместного наступления событий А1 и А2 - P (Аi Аj). Р(А1) = К1 К12 К2 К23 К3; Р(А2) = К1К14 К4 К42К2 К23 К3; Р(А3) = К1К14 К4 К43 К3. P (А1 А2) = P (А1) P ( А2 | А1), где Р (А1) = К1 К12 К2 К23 К3; P (А2 | А1) = К14 К4 К42. Таким образом: P (А1 А2) = К1 К12 К2 К23 К14 К4 К42 К3. Аналогичным способом определяются вероятности совместного наступления дру- гих событий - P (А1 А3), P (А2 А3) и P (А 1 А 2 А 3 ). 4. Используя формулу (4), определим надежность связи Р13. Р13 = К1 К12 К2 К23 К3 + К1К14 К4 К42 К2 К23 К3 + К1К14 К4 К34 К3 К1 К12 К2 К23 К14 К4 К42 К3 К1 К12 К2 К23 К14 К4 К34 К3 - К1К14 К4 К42К2 К23 К34 К3 + + К1 К12 К2 К23 К14 К42 К4 К34 К3 Если узлы абсолютно надежны, т.е. коэффициенты готовности узлов сети рав- ны 1, то имеем: Р13 = К12 К23 + К14 К42 К23 + К14 К34 К12 К23 К14 К42 К12 К23 К14 К34 - - К14 К42 К23 К34 + К12 К23 К14 К42 К34. Подставляя конкретные значения коэффициентов готовности Кij, рассчитаем Р13. Если коэффициенты готовности для всех линий связи одинаковые и равны 0.9, по- лучим Р13 = 0.97119. Для определения математического ожидания числа связей в сети М (Х) вос-пользуемся основными положениями теории вероятности. Пусть случайная величина Х поставлена в соответствие общему числу межузловых связей в сети. При наличии n взаимодействующих друг с другом узлов, случайная величина X, в зависимости от надежности узлов или линий связи, будет изменяться в пределах от 0 до n(n – 1) (0 ≤ X ≤ n(n – 1)). Если каждой связи в сети поставить в соответствие случайную величину где M – число рассматриваемых связей в сети. Тогда В соответствии с теоремой сложения математических ожиданий случайных вел- чин, имеем Величина 1, если i-ая связь существует в сети, или 0, если i-ая связь отсутствует, т.е. данные события образуют полную группу. Пусть Pi – вероятность того, что случайная ве- личина
m (xi) = 1Pi + 0(1- Pi) = Pi
Следовательно
ВероятностьPi эквивалентна надежности связи (вероятности связности) узлов, обра-зующих i-ую связь. С учетом выше сказанного, для определения математического ожидания чи-сла связей в сети М (Х) предлагается использовать следующий алгоритм: 1. Сформировать список корреспондирующих пар узлов сети. 2. Определить пути, которые могут быть использованы для связи каждой пары узлов сети из заданного списка. 3. Для каждой пары узлов, с учетом надежности элементов сети и используемых для связи путей, определим вероятность связности. 4. Произведем суммирование значений вероятностей связности различных пар узлов сети из заданного списка. В результате получим абсолютное значение мате-матического ожидания числа связей в сети – М (Х). Удобнее и нагляднее число связей в сети выразить в относительных единицах. В этом случае величина М (Х)отн. может быть рассчитана по формуле:
М (Х)отн. = (М (Х)/Mmax)·100%, (9)
где Mmax – число связей в сети из заданного списка корреспондирующих пар узлов, при условии, что все элементы сети абсолютно надежны.
Пример 2 Определить математическое ожидание числа связей М (Х)отн. для сети, пред-ставленной на рисунке 19, при условии, что используются все возможные пути для связи узлов сети и коэффициент готовности каждой линии связи (вес ребра графа сети) равен К = 0, 9. Узлы сети абсолютно надежны.
Рис. 19. Граф сети
Для решения задачи используем алгоритм расчета математического ожидания числа связей М (Х), приведенный выше,
1. Используя графический метод, изложенный в МУ к задаче 1, определим список путей, связывающих узлы сети. Для связи i – го узла с j – ым могут быть исполь-зованы по два пути. Ранг путей в сети изменяется от 1 до 3. m112={b12}, m212 = {b13, b23}; m113 = {b13}, m213 = {b12, b23}; m114 = {b13, b34}, m214 = {b 12, b23, b34}; m121 = {b21}, m221 = {b23, b31}; m123 = {b23}, m223 = {b21, b13}; m124 = {b23, b34}, m224 = {b21, b13, b34}; m131 = {b31}, m231 = { b32, b21 }; m132 = {b32}, m232 = {b31, b12}; m134 = {b34}; m141 = { b43, b31}, m241 = {b12, b23, b34}; m142 = {b23, b34}; m242 = {b12, b13, b34}; m143 = {b43}.
2. Определим надежность каждого из указанных путей в общем виде с учетом коэффициентов готовности линий связи сети (весов ребер графа сети), используя формулу (1). P (m112) = P (m121) = К12; P (m212) = P (m221) = К13 К23; P (m113) = P (m131) = К13; P (m213) = P (m231) = К12 К23; P (m114) = P (m141) = К13 К34; P (m214) = P (m241) = К12 К23 К34; P (m123) = P (m132) = К23; P (m223) = P (m232) = К12 К13 ; P (m124) = P (m142) = К23* К34; P (m224) = P (m242) = К12 К13 К34; P (m134) = P (m143) = К34
3. Определим вероятности связности для каждой пары вершин графа (узлов сети), используя выражение (4). Р12 = Р21 = К12 + К13 К23 – К12 К13 К23; Р13 = Р31 = К13 + К12 К23 – К12 К13 К23; |
Последнее изменение этой страницы: 2017-05-05; Просмотров: 229; Нарушение авторского права страницы
, который представляется упорядоченным набором ребер и узлов, входящих в данный путь. Рангом пути г( 
, 
….
= 
; 
= 
h; 
= 
h.
( 
b) = 
= 0; 
h 
h 
= 
, то
, 
номеров
= {а1, b12, а2, b13, а2}, 
= {а1, b14, а4, b42, а2, b23, а3} и
= {а1, b14, а4, b43, а3}. Элементы сети (узлы и линии связи) являются статистически независимыми. Показатели надежности элементов сети представляют их коэффици-енты готовности.
, то случайная величина X может быть определена как: 
, (5)
(6)
(7) 
(8)