Применение показателя конструктивных действий на сети связи в процессе проектирования при рассмотрении каких-либо решений, связанных с изменением структуры сети связи

УДК 614.8:621.39

Применение показателя конструктивных действий на сети связи в процессе проектирования при рассмотрении каких-либо решений, связанных с изменением структуры сети связи

В.Н. Кононенко

Аннотация

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

Ключевые слова: НЦУКС, случайный граф, двухполюсная сеть, простая цепь, простой разрез, Г-рельеф, показатель конструктивных действий, ребро графа, транзитная вершина, событие связности.

Application of the Functional Manipulation-Value on Trunk Network in the Course of Engineering Under the Review Process of Decision Which is Concerned with Trunk Network Structure Variance

V. Kononenko

Abstrakt

For the first time ever that the article forces into application the concept of the functional manipulation-value. This measures allows to confirm (or to refute) designer's correctness of intentions simply enough under the consideration of some kinds of decisions (in the course of project engineering) which are connected with changes of telecommunications structure there is a formula for calculation of the functional manipulation-value there. And there is an example of its application there.

Key words: NES, random graph, double-pole net, circuit, simple slit, t- relief, functional manipulation-value, tree edge, transit peak, coherence event.

Во исполнение поручений Президента Российской Федерации от 21 марта 2005 г. и Правительства Российской Федерации от 14 июля 2005 г. в МЧС России проводится работа по совершенствованию системы управления МЧС России. Созданное и функционирующее ФГУ «Национальный центр

управления в кризисных ситуациях» как основа единой, интегрированной вертикали «межведомственной» системы управления позволяет эффективно ре-ализовывать управленческие функции в чрезвычайных ситуациях. 30 мая 2007 г. коллегией МЧС России был утвержден План развития системы управления

МЧС России с учетом ресурса НЦУКС на период 2007—2010 годов.

В рамках этого плана ведется создание межрегиональных ЦУКС, в которых должен быть реализован по единым правилам весь комплекс управления системой РСЧС, гражданской обороной, а также ресурсным обеспечением. ЦУКСы должны быть наделены полномочиями по привлечению сил, определенных законодательством, и управлению ими при решении задач по защите населения и территорий от чрезвычайных ситуаций.

Система управления нового типа должна строиться как единая многоуровневая система иерархически подчиненных управленческих структур, накрывающая территорию Российской Федерации. Такая система должна быть представлена:

— на федеральном уровне — Национальным ЦУКС, являющимся головным в иерархии управленческих структур;

— на межрегиональном уровне — ЦУКСами региональных центров МЧС России;

— на региональном уровне — ЦУКСами в субъектах РФ, являющимися головными в иерархии управленческих структур системы РСЧС и ГО на региональном уровне;

— на муниципальном уровне — ЕДДС и «Системы-112» муниципальных образований.

К 2011 году интегрированная вертикаль управления НЦУКС в целом должна представлять собой функционирующую по единым правилам, в общем цифровом картографическом и информационном пространстве сеть ЦУКСов.

На данный момент в интегрированную вертикаль управления МЧС России, РСЧС и ГО включены НЦУКС и межрегиональные ЦУКСы ЮРЦ, СРЦ, ЦРЦ, частично ЦУКС Северо-Западного РЦ, а далее в вертикаль НЦУКС последовательно включены оставшиеся ЦУКСы региональных центров. К 2011 году единая сеть ЦУКСов включит ЦУКСы субъектов РФ, высокотехнологичные расчетные, прогнозные, мониторинговые центры системы РСЧС. Интегрированная вертикаль НЦУКС даст возможность не только управлять задачами РСЧС, но и моделировать социально-экономическое развитие территорий, управлять рисками и в целом сможет взять на себя все функции антикризисного управления жизнедеятельностью территорий.

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

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

Математическая модель сети связи. Поскольку выход из строя узлов и линий связи и их восстановление в общем случае носит случайный характер, то в качестве математической модели сети связи примем случайный граф. Под случайным графом О понимают [4] граф, элементы которого могут присутствовать или отсутствовать в нем с соответствующими вероятностями р и q такими, что р + q = 1. В теории надежности случайных бинарных систем величины р и q в приложении к практическим расчетам рассматриваются соответственно как коэффициенты готовности и простоя элементов.

Формально граф О чаще всего описывают таким образом [5]:

О = {у, Ь, Ф} .

Здесь в (1) используются условные обозначения: V = {у,} — множество вершин, число которых равно ту = VI ; Ь = {/, ]} — множество ребер, число которых равно тЬ = \Ь\ ; )= у & — отображение инци-

дентности и смежности элементов графа, в котором у и V] составляют вершины граничной пары (ВГП) ребра I ] , если оно соединяет эти вершины.

Граф О является перенумерованным, если его вершины перенумерованы как V = {у|г = 1,... , mV }, а ребра — как Ь = { = ту +1,...,ту + тЬ}. Поскольку все элементы в перенумерованном графе имеют индивидуальный номер, то это позволяет в логических выражениях с целью упрощения их представления символы V и / без необходимости не применять.

Конструкции и события на графе. Напомним [5] определения некоторых конструкций, формируемых на графе. Под гранью п = {,- 3,..., /к I} графа понимается любая замкнутая последовательность ребер, не содержащая внутри себя ни одного элемента графа. На графе О двухполюсная сеть (ДС) определена, если в нем задана пара вершин vs и V,, в которой вершина л является истоком (например, информации), а вершина , — стоком. Подмножество вершин УТ = V \ {л,,} назовем транзитными вершинами ДС.

Под простой цепью (ПЦ) ц = {,, 1 ,...,1к,} понимается последовательность ребер графа без петель и параллелей, соединяющая вершины л и , между собой. Поскольку У/^ ]) е Ь^ & = Ф (, ])), то при необходимости ВГП ребер в ПЦ могут быть перечислены.

В свою очередь, под простым разрезом (ПР) понимается минимальная по включению совокупность элементов графа, исключение которых из последнего приводит к разбиению исходного графа О на два его компонента О1 и О2 такие, что ле О1 , ,е О2 и О1 П О2 = 0, где 0 — символ пустого множества. Поскольку О1 П О2 =0, то вершины л и , разъединены. В общем случае различают реберные ПР г = {^ }, вершинные ПР г = {^ } и ПР смешанного типа.

Под высотой , -й вершины [6], обозначаемой как к1, понимается число ребер в кратчайшей ПЦ между вершиной и вершиной-стоком V,, принимая для , -й вершины И, = 0 . Если высоты всех вершин графа в ДС относительно V, известны, то говорят, что на графе ДС сформирован , -рельеф.

См! БесигШу Тес1ппо!оду, Уо!. 7, 2010, N0. 3

В общем случае в ДС могут быть сформированы множества ПЦ и ПР вида М= {цп|п = 1,...,шм}

и К,, ={г„\» = 1..^шя}, где шм=|М и шя = — мощности множеств. Конструкции ПЦ и ПР являются базовыми для исследования основополагающих свойств ДС — связности и несвязности вершин л и ,. Легко видеть, что в ДС для любой п-й ПЦ и любого п-го ПР из их множеств справедливо утверждение цп П гп Ф0 вплоть до случая цп П гп = цп или цп П гп = гп .

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

Если между л и , существует хотя бы одна исправная ПЦ, то в ДС наступает событие Ел, связности. Если между л и , существует хотя бы один исправный ПР, то в ДС наступает событие Е— несвязности. Заметим, что Ел, + Е— = I, где I — символ полной группы событий (ПГС).

Свойства л-рельефа и ,-рельефа Под ,-рельефом двухполюсной сети понимается упорядоченное размещение по зонам высот Н1 транзитных вершин случайного графа относительно вершины-стока , так, что заведомо (т. е. в исходном состоянии) вершина , имеет наименьшую высоту, равную И, = 0 , а вершина л — наибольшую высоту, равную И = ~ . В свою очередь, под высотой И транзитной I -й вер-

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

Аналогичным образом в двухполюсной сети случайного графа понимается и л-рельеф с той лишь разницей, что в исходном состоянии Ил = 0 , а И, = ~. Например ,-рельеф представлен на рис. 1а, а л-рельеф — на рис. 1, б.

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

Решим следующую задачу. Пусть имеется некоторый исходный граф ДС с шу = шь = 6 , элементы которого образуют две (Ы = 2) непересекающиеся (т. е. не имеющие общих элементов) равновеликие ПЦ. Например, так, как это показано на рис. 2.

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

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

э { 1

6 I f

Рис. 2

Из шести вариантов размещения дополнительных ребер выберем два, в которых между ^ и г можно сформировать наибольшее число ПЦ. Этому условию соответствуют такие размещения новых ребер: {2 3,14 5} и { 5,4 4}. Структуры перенумерованных графов выбранных двух вариантов представлены на рис. 3 (дополнительные ребра здесь выделены жирными линиями).

Сравним варианты между собой. При представлении каких-либо конструкций, событий и т. п. на графах, относящихся к тому или иному варианту, в верхнем индексе соответствующего символа (или их совокупности) при необходимости будем указывать номер анализируемого варианта. Например, размещения двух дополнительных ребер в 1-м и 2-м вариантах (см. рис. 3) обозначим таким образом: {2 3,4 5}

и (4,5>4,4} .

По числу элементов эти графы равновелики, поскольку в обоих случаях шг = 6 и шь = 8 . Высоты вершин по ,-рельефу [6] в обоих вариантах также одинаковы (см. рис. 3): к6 = 0 , к4 = к5 = 1 , к2 = к3 = 2 , к1 = 3 . Число граней в этих графах одинаково и равно трем: {П1 ={7,9,8},П2 ={9,10,12,11},Пз ={12,13,14}} ,

{г|1 ={7,9,11,8},п2 ={9,13,14,10},^ ={11,13,14,12}} . Заметим, что поскольку оба графа плоские [5], то у каждого из них есть еще и так называемая бесконечная грань.

Сформируем в этих ДС множества ПЦ:

М^, = {ц ={7,10,13}, ц ={7,10,12,14}, ц ={7,9,11,14}, Ц4 = {7,9,11,12,13}, Ц5 ={8,11,14}, Ц6 ={8,11,12,13},

ц7 ={8,9,10,13}, ц8 ={8,9,10,12,14}},

М 2,, ={Ц ={7,9,13}, Ц ={7,9,11,12,14}, Ц ={7,10,14},

Ц4 = {7,10,12,11,13}, ц5 ={8,11,13}, ц6 ={8,11,9,10,14},

Ц7 ={8,12,14}, Ц8 ={8,12,10,9,13}}.

Из (2) и (3) видно, что число ПЦ в обоих случаях также одинаково и равно шМ = шМ = 8 . Заметим, что максимально возможное число взаимно непересекающихся ПЦ в этих структурах осталось неизменным и равным N = 2 (см. рис. 2 и рис. 3).

Поскольку анализ сугубо структурных конструкций в силу их равновеликости не позволяет с позиций надежности бесспорно отдать предпочтение какому-либо одному из рассматриваемых вариантов, то прибегнем к численным методам оценки структурной надежности сложных (т. е. неприводимого вида [4]) систем.

Воспользуемся методом объединения ПЦ с учетом эффекта поглощения [8] и опишем события связности в исследуемых ДС. Для упрощения примем допущение о том, что в графе ненадежны только ребра, при этом выход из строя любого ребра наступает независимо от состояния других ребер.

Полное событие Е], связности ДС, изображенной на рис. 3, а, с учетом множества ПЦ (см. (2) описывается следующим образом:

Е!, = 7 • 10 • 13 + 7 • 10 • 12 • 14 • 13 + 7 • 9 • 11 • 14 • 10 • 13 • 12 +

+7 • 9 • 11 • 12 • 13 • 10 • 14 + 8 • 11 • 14 • 7 • 10 • 13 • 12 • 9 +

+8 • 11 • 12 • 13 • 7 • 10 • 9 • 14 + 8 • 9 • 10 • 13 • 7 • 11 • 14 • 12 + +8 • 9 • 10 • 12 • 14 • 7 • 11 • 13 .

На основании (4) точное значение вероятности P^t связности ДС 1-го варианта в общем случае можно вычислить по формуле следующего вида:

Plt = PlР10Р13 + PlЛ0Л2Л4913 + PiР9Р11Р14 С - P10

Аналогичным образом проанализируем 2-й вариант. С учетом множества ПЦ (см. (3) полное событие E2S t связности ДС 2-го варианта, представленной на рис. 3, б, описывается следующим образом:

E2, = 7 • 9 • 13 + 7 • 9 • 11» 12 • 14 • 13 + 7 • 10 • 14 • 9 • 13 • 11 • 12 +

+7 • 10 • 12 • 11 • 13 • 9 • 14 + 8 • 11 • 13 • 7 • 9 • 10 • 14 • 12 +

+8 • 11 • 9 • 10 • 14 • l • 13 + 8 • 12 • 14 l • 11 • 13 • 9 • 10 + +l • С • 11» 13 + 9 • 13 • !!)• 108 • 12 • 10 • 9 • 13 • l • 11 • 14.

Точное значение вероятности P^, связности ДС 2-го варианта согласно (6) в общем случае можно вычислить по формуле следующего вида:

Plt = PlР9Р13 + PlР9Р11Р12Р14913 + PlP10P14 С1 - P9 С1 - 913 С1 - P11P12 )))+ +PlP10P12P11Р139914 + P8P1 С1 - Pl С1 - 99 С1 - P10 С1 - 914912 ))))+ +P8P11P9P10P149l913 + P8P12P14 ^l С1 - P11 С - 913 С1 - P9P10)))+ +Pl 9 С1 - P11P13) + P9913911 )910)+ P8P12P10P9P\39l9u9i4 .

Для расчета и P^, примем простейшие исходные данные: пусть для всех ребер графа коэффициенты готовности будут одинаковы и равны Р^ц = 0 ,9 . Тогда согласно формулам (5) и (7) точные значения вероятностей связности анализируемых ДС будут соответственно равны:

P¿ = 0,9669l4l6l Ps2, = 0 ,9l624035 J .

На основании результатов расчета (8) теперь можно однозначно утверждать, что вариант размещения в графе ДС двух дополнительных ребер, представленный на рис. 3, б, при всех прочих равных условиях более надежен по сравнению с вариантом, изображенным на рис. 3, а.

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

Полное событие Ej- несвязности ДС этого варианта (см. рис. 3, а) методом двудольных графов описывается следующим образом:

Ej-t = 7 • 8 + 7 • 8 »11 +10 • 11» 13 • 14 +10 • 11» 12 • 13 »14 + +10 » 11.13 »12 »14)+ 7 < ' _ _ _

В общем случае точное значение вероятности р1 несвязности ДС согласно (9) можно вычислить по следующей формуле:

P¿ = 9798 + Р7Р8 (9ю9п + Р10РП913914 + 910Р11 С1 - Р12Р13 9 + Р10х Х9п913 С1 - Р12Р14 ))+ 97Р8 (С1 - Р9Р10 )911 + Р9РюРи913914 + + (1 -Р9Р10 )Р11 С1 - Р12Р13 )?14 + Р9Р10?11?13 С1 - Р12Р14 ))+ Р7?8 (?10 С1 -РчРи ) + + Р10Р9Р11913914 + 910Р9 Р11 С1 - Р12Р13 )914 + Р10 С1 - Р9Р11 )Х

х913

При принятых выше исходных данных р^ = — = 0,9 согласно (10) точное значение р1 будет равно:

р^ = 0,03302524 .

Поскольку в (4) и (9) представлены описания полных событий связности и несвязности одной и той же ДС, то Eh + Ej- = I, откуда следует, что должно выполняться P¿ + Pj-t = 1. Можно видеть, что р, = 0, 96697476 (см. (8) дополняет Pj-t = 0,03302524 (см. (11) точно до 1. Приходим к выводу о том, что метод объединения ПЦ с учетом эффекта поглощения используется корректно.

Оценка конструктивных действий на сети связи

Несмотря на равновеликость рассмотренных выше конструкций (граней, высот, ПЦ и т. п.), формируемых в анализируемых ДС (см. рис. 3), все-таки их структуры с позиций надежности существенно разнятся, поскольку < P^, . Видно, что размещение дополнительных ребер во 2-м варианте (см. рис. 3, б) более конструктивно по сравнению с 1-м вариантом (см. рис. 3, а).

Для оценки степени конструктивности (или рациональности) размещения дополнительных ребер на графе ДС введем показатель конструктивных действий (ПКД), который обозначим символом Qs, . Численное значение ПКД предлагается вычислять по следующей формуле:

Q,, = 11 \ - h„ ^

о=1

где: m+ — число дополнительных ребер, а h и h, — высоты ВГП о-го ребра, дополнительно встроенного в исходную структуру графа ДС, на котором сформирован t-рельеф. Заметим, что ПКД является детерминированным показателем, поскольку значения h.=— неслучайны.

Оценим ПКД в рассмотренном выше примере. Поскольку по t -рельефу (см. рис. 2) имеем h2 = h3 = 2 и h4 = h5 = 1 , то для 1-го и 2-го вариантов размещения ребер {23,/4 5} (см. рис. 3, а) и {/2 5,/3 4} (см. рис. 3, б) согласно (12) численные значения ПКД соответственно равны Q^ t = 0 и Q2 t = 2 . Можно видеть, что Q^ t < Q^ t так же, как и Plsl < Pj, . Будем говорить, что ПКД подобен вероятностному показателю Ps t .

Известно [9], что в общем случае вычисление точного значения вероятности Ps t связности ДС является ЛР-трудной задачей, а формирование t -рельефа и вычисление Qs t — линейной задачей. Помимо этого ПКД «оперирует» с характеристиками детерминированного (т. е. неслучайного) графа. Это обстоятельство относит-

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

Покажем на примере, что если выполняется < Ок,+1 , то выполняется и Р3к, < . В рассмотренной выше задаче четыре варианта размещения ребер

{^зЛЛ , {12,3 ,^3,4 } , {2,5,^4,5 } и {13,4,14,5} были проигнорированы по той причине, что в них формируется меньшее число ПЦ. Поскольку все эти варианты равновелики (в т. ч. и по числу ПЦ), то рассмотрим какой-либо один из них, например 3-й вариант размещения дополнительных ребер {/23,12 5} . Структура графа ДС этого варианта приведена на рис. 4.

Множество ПЦ в этой ДС имеет следующий вид:

М 3,, = {ц1 = {7,10,13}, Ц2 = {7,11,14}, Ц3 = {7,9,12,14}, Ц4 = {8,12,14}, ц5 ={8,12,11,10,13}, Ц6 ={8,9,10,13}, Ц7 ={8,9,11,14}},

в котором шМ = 7 . Видно (см. (2), (3) и (13), что

«м .

шМ < шМ

Поскольку к5 = 1 и к2 = к3 = 2 (см. рис. 2), то согласно (12) ПКД размещения дополнительных ребер в 3-м варианте равен О3, = 1. Видно, что Ц,, < ,, но в то же время О3 , >Ц] ,, хотя и шМ < шМ (см. (2) и (13). Можно предположить, что и Р^ > Р^ . Проверим это предположение.

При принятых выше исходных данных р^ =714 = 0 ,9 точное значение Р^ согласно (15) будет равно:

РД = 0,96842547.

Сравнивая РД = 0,96842547 из (16) с Р], = 0,96697476 из (8), видно, что предположение Р^ > Р^ подтверждается. Это, в свою очередь, дополнительно иллюстрирует справедливость свойства подобия ПКД в рассматриваемых вариантах О3 , > ,.

Для удобства обозрения результаты проведенных выше вычислений сведены в табл. 1.

Таблица 1

№ варианта ДС тм Ps,t

1 8 0,96697476 0

2 8 0,97624035 2

3 7 0,96842547 1

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

Литература

М 1

6 J t

12

3-й вариант

Рис. 4

Полное событие Е^, связности ДС 3-го варианта с использованием множества (13) методом объединения ПЦ с учетом эффекта поглощения описывается следующим образом:

E3, = 7 • 10 • 13 + 7 • 11 • 14 • 10 • 13 + 7 • 9 • 12 • 14 • 10 • 13 • 11 +

+8 • 12 • 14 • 7 • 10 • 13 • 11 • 9 + 8 • 12 • 11 • 10 • 13 • 7 • 14 + 8 • 9 •

• 10 • 13 • 7 • 12 • 14 • 11 + 8 • 9 • 11 • 14 • 7 • 12 • 10 • 13 .

Точное значение вероятности Р^ связности ДС 3-го варианта в общем случае согласно (14) можно вычислить по формуле следующего вида:

1. Махутов Н.А., Прангишвили И.В., Фролов К.В. и др. Безопасность России. М.: МГФ «Знание», 1998.

2. Годный В.Г., Мансуров В.В. Информационная безопасность сетей связи на базе цифровых УПАТС // Системы безопасности, 2002. № 3. С. 74—77.

3. Бельфер Р.А. Классификация угроз информационной безопасности сетей связи ВСС России (ISDN, IN, UMTS) и методы их количественной оценки // Электросвязь, 2002. № 7. С. 14—18.

4. Райншке К., Ушаков И.А. Оценка надежности систем с использованием графов. М.: Радио и связь, 1988.

5. Басакер Р., Саати Т. Конечные графы и сети. М.: Наука, 1974.

6. Бутрименко А.В. О поиске кратчайших путей по графу при его изменениях // Изв. АН СССР. Тех. кибернетика, 1964. № 6. С. 55—58.

7. Филин Б.П. О принципе дуальности в задачах анализа структурной надежности сложных систем // Автоматика и телемеханика, 1989. № 6. С. 158—172.

8. Филин Б.П. Методы анализа структурной надежности сетей связи. М.: Радио и связь, 1988.

9. Гэри М., Джонсон Д. Вычислительные машины и трудноре-шаемые задачи. М.: Мир, 1982.

10. Зацаринный А.А. Системный подход к проектированию, внедрению и развитию современных корпоративных телекоммуникационных сетей // Ведомственные корпоративные системы и сети, 2002. № 3. С. 110—116.

Сведения об авторе:

Ph = P7PWP13 + P7Р11Р14

Кононенко Виктор Николаевич, ФГУ ВНИИ ГОЧС (ФЦ), начальник направления, 121352, г Москва, ул. Давыдковская, 7.