Анализ вероятности связности телекоммуникационной сети на основе инверсий ее состояний | Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2022. № 59. DOI: 10.17223/19988605/59/10

Анализ вероятности связности телекоммуникационной сети на основе инверсий ее состояний

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

Network connectivity probability analysis based on its states inversion.pdf Известно, что для больших и сложных по структуре телекоммуникационных сетей расчет вероятности связности оказывается весьма громоздким и трудоемким процессом вследствие огромного числа элементов в результирующем выражении. Наиболее целесообразным выходом из подобной ситуации является подход, основанный на представлении события связности сети в виде сумм произведений несовместных событий (SDP - Sum of Disjoint Product) [11], представляющих собой форму перехода к замещению [2-6], допускающую непосредственный переход к вероятностной функции заменой логических переменных (множеств) вероятностями, а логических операций (операций над множествами) соответствующими арифметическими операциями [7-9]. Данное представление приводит к достаточно компактной форме записи результирующего уравнения связности и, как следствие, к снижению вычислительной сложности и уменьшению результирующей ошибки округления [10, 11]. Отметим, то данный подход рекомендован отечественным ГОСТом для расчета устойчивости функционирования сетей [12] и в научной литературе получил название метода объединения с учетом эффекта поглощения [13]. Само представление события связности сети в виде сумм произведений несовместных событий [11] базируется на методе многопеременных инверсий, являющемся расширением алгоритма однопеременной инверсии (SVI - Single Variable Inversion). На основе наборов типовых подграфов (простая цепь, остовое дерево) данный алгоритм рекурсивно генерирует непересекающиеся подмножества для каждого из наборов. Алгоритм построен по принципу цикл в цикле. Во внутреннем цикле произведения инвертируются целиком, а не последовательно по каждой из переменных в отдельности. В результате формируется значительно меньше составляющих относительно SVI вследствие рассмотрения большего количества переменных за один такт. Внешний цикл перебирает последовательно все отдельные типовые подграфы и рекурсивно перебирает инверсии с ранее выполненными преобразованиями. В подобном алгоритме требуется на каждом шаге внешнего цикла проводить сравнение текущего выражения связности типового подграфа с ранее полученными соотношениями, причем необходимо проанализировать обязательно их все. В настоящей работе предлагается снизить сложность данной рутинной процедуры за счет рассмотрения не события связности исходного графа, а события несвязности. В результате каждый шаг внешнего цикла в ряде случаев будет анализировать меньшее количество слагаемых в ранее полученном выражении, что сократит вычислительную сложность расчета вероятности связности. 92 Батенков А.А., Батенков КА., Фокин А.Б. Анализ вероятности связности телекоммуникационной сети 1. Общий подход к расчету вероятности связности на основе инверсий состояний сети Известно несколько трактовок понятия связности, обобщением которого является многополюсная связность, включающая и двухполюсную, и всеполюсную. При этом целесообразно рассматривать событие связности как существование некоторого подграфа Si в конкретной реализации графа G, содержащего заданные вершины, исходного случайного графа G и однозначно являющегося деревом, листьями которого могут быть только эти заданные вершины [14]. Для общего случая многополюсной сети этими подграфами Si оказываются деревья, имеющие заданный набор вершин, для двухполюсной сети - деревья, содержащие заданную пару вершин, по сути, являющиеся путями, для всеполюсной сети - остовые деревья, включающие все вершины случайного графа G [15]. Таким образом, множество S графов, для которого выполняется свойство связности, имеет следующий вид: S = {G: 3S, с G}, (1) т.е. множество S состоит из всех графов G, для которых существует хотя бы один подграф Si, содержащийся в графе G [16]. Следует отметить, что даже наиболее совершенным модификациям метода, использующим многопеременную инверсию (MVI - Multiple Variable Inversion), свойствен существенный недостаток, связанный с необходимостью сравнительного анализа каждого слагаемого со всеми ранее рассмотренными на предмет уникальности содержащихся ребер, а также выполнения в ряде случаев дополнительных операций над множествами [1, 17, 18]. Для устранения подобных повторяющихся рутинных процедур целесообразно рассматривать не объединение событий связности (несвязности), вырождающееся в сумму несовместных произведений, а пересечение противоположных событий, также приводящее к подобной сумме, но для получения которой нет необходимости выполнять многопеременную инверсию для каждого из слагаемых над всеми ранее проанализированными. Так, согласно формуле (1 ) событие S связности графа G следует трактовать как объединение событий связности всех его подграфов, что приводит к справедливости следующего выражения для события S связности сети: s = \\jst, і=\\ где Si, i = 1,...,s, - событие связности i-го типового подграфа (пути, остового, а в общем случае многополюсного дерева) случайного графа G. Каждое событие Si связности типового подграфа является сложным и происходит только при условии связности (работоспособности) содержащихся в этом подграфе ребер, т.е. = ГК, где lj, j = 1,...,/, - событие связности (работоспособности) j-го ребра графа G. По условию формулировки обобщенной модели Эрдеша-Реньи все данные события независимы, следовательно, вероятность связности подграфа [19, 20] P (S )=№ (Г )■ l eS Отметим, что для события S связности графа G данная мультипликативная формула в общем случае несправедлива, поскольку события Si связности типовых подграфов могут быть зависимы вследствие присутствия одинаковых ребер в данных подграфах. Именно в этом и заключается основная проблема расчета вероятности связности, так как отдельные подграфы оказываются взаимозависимыми, а получаемые выражения не являются формами перехода к замещению. Хорошо известный принцип двойственности [22] позволяет записать событие S несвязности графа G как пересечение событий S несвязности типовых подграфов _ 5 _ s = ns(. Z=1 93 Информатика и программирование / Informatics and programming В результате на основе формулы полной вероятности вероятность P (S) связности графа выражается на основе вероятностей событий несвязности: /-ч ( s -\\ P(s) = \\-P{s) = \\-P Рі^ . Ѵ/=1 У Главным достоинством данного выражения является то, что дальнейший переход к вероятностной форме не потребует рассмотрения во всех суммах инверсии всех ранее учтенных подграфов [16, 21]. Достаточно просто на основе принципа двойственности формализуется выражение для события S несвязности графа на основе событий /; работоспособности ребер: 1 gS 1 gS 2. Процедура приведения двух событий несвязности к объединению независимых событий Для наглядности дальнейших упрощений целесообразно первоначально рассмотреть процедуру упрощения для двух произвольных подграфов. Пересечение событий связности этих двух подграфов (рис. 11) ЗД = ПП= ППП /су 1IGS1 1igSi 1iGSi l eS l «S l eS где a,k = P| / , - событие связности ребер, входящих одновременно в /-й и к-й подграфы; аѵк = Q / , - IgS, lpSt событие связности ребер, входящих в /-й и не входящих в к-й подграфы; акИ = р| /. - событие СВЯЗ ЕЙ S l eS, ности ребер, входящих в к-й и не входящих в /-й подграфы. Отметим, что с целью устранения громоздкости используемых обозначений операция П пересечения событий пропускается, если не возникает неоднозначности толкований [11, 22]. Рис. 1. Разбиение двух событий связности подграфов на независимые Fig. 1. Splitting of two subgraph connectivity events into independent Поскольку все полученные события независимы, то P ( StSk ) = P (alJk ) P (allk ) P (ak „ ). В результате события связности Si = ai,kailk ,Sk = ai,kakli. 94 Батенков А.А., Батенков КА., Фокин А.Б. Анализ вероятности связности телекоммуникационной сети Тогда пересечение событий несвязности этих двух подграфов представимо в форме объединения двух независимых событий: Si Sk = aikai/k ai.kakU = ai,k ^ (ai,k ai/k ak/i )• i,k i/k k/i / Полученное выражение является, по сути, классической формой перехода к замещению, т.е. р (Sisk)=р (ahk)+p (ahk)p (ai / k)p (ak/i )• 3. Процедура приведения трех событий несвязности к объединению независимых событий Для трех произвольных подграфов пересечение событий несвязности представимо в форме объединения тоже двух, но зависимых событий: Si SkSj = ai,k Sj ^ (ai,k ai/k ak/i Sj )• События aik и S связности возможно зависать как пересечение двух событий (рис. 22): ai,k = ai,k, jai,k/ j, Sj = ai,k, jaj/i,k , где aik, j - событие связности ребер, входящих одновременно в i-й, k-й и j-й подграфы; aikt j - событие связности ребер, входящих в i-й и k-й и не входящих в j-й подграфы; a Уі к - событие связности ребер, входящих в j-й и не входящих в i-й и k-й подграфы. Тогда ai,kSj = ai,k, jai,k/ jai,k, jaj/i,k = a, i,k ,j ^( ai k,j ai,k/ j aj/i,k ai,kSj = ai,k, ja,,k / ja,,k, jaj/,,k = a,,k aj/,,k • Рис. 2. Разбиение трех событий связности подграфов на независимые Fig. 2. Splitting the three connectivity events of subgraphs into independent 95 Информатика и программирование / Informatics and programming В результате пересечение событий несвязности имеет вид двух независимых объединений и одного зависимого: Si SkSj=a,,k, j ^ (a,,k, j a,,k / j aj n,k) ^ (a,,k aj n,k a/ k ak/i )• При этом в третьем объединении первые два события ai k и aj/i k , а также события ai k, ailk и aM являются независимыми, в то время как события a Уі k и aj/lc, а также a Уі k и ak/i - нет. Последующее упрощение аналогично ранее описанному и заключается в последовательной процедуре разложения пересечения обратных событий в виде объединений [14]. Поскольку aj/i,k = ai, j/kaj/i, ai/k = ai, j/kai/ j/k, то aj/i,kai/k = ai, j/kaj/iai, j /kai/j /k = a /k ^( ai,j /k aj /i ai/j /k), Si SkSj = a,,k,j ^ (a,,k,j a,,k/j ajn,k ) ^ (a,,k ai,j/k ak/i ) ^ (a,,k ai,j/k aj/i ai/j/k aka \\ Оставшиеся зависимые события aj/i и akli раскладываются подобным образом: aj/i = aj,k/iaj/i/k, ak/i = aj,k/iak/i/ j ■ U(aj,k/i aj/i/k ak/i/j )• aj/i ak/i = aj,k/iaj/i/k aj,k/iak/i/ j = aj,k/i В результате образуется совокупность объединений независимых событий Si SkSj = a,,k,j ^ (a,,k,j a,,k/j aj/,,k ) ^ (a,,k a,,j/k ak/i ) ^ (a,,k ai,j/k a,/j/k aj,k/i ) ^ (a,,k a, i,k ai, j/k aj,k/i ai/ j/k aj/i/k ak/i/ j i/ j ) ’ которая является формой перехода к замещению, т.е. P (Si SkSj) = P (ai,k, j) + P (ai,k, j)P (ai,k / j)P (aj/i,k) + P (ai,k)P (ai, j/k)P (ak/i) + +P (ai,k)P (ai,j/k)P (ai / j / k)P (aj,k/i) + P (ai,k)P (ai,j / k)P (aj,k/i)P (ai / j / k)P (aj/i/k)P (ak/i/j) • Заключение В работе представлен вариант устранения основного недостатка наиболее совершенных модификаций метода, использующих многопеременную инверсию, - необходимости проведения сравнительного анализа каждого слагаемого со всеми ранее рассмотренными на предмет уникальности содержащихся ребер, а также в ряде случаев дополнительных операций над множествами [1, 23, 24]. Согласно данному варианту целесообразно рассматривать не объединение событий связности (несвязности), вырождающееся в сумму несовместных произведений, а пересечение противоположных событий, также приводящее к подобной сумме, но для получения которой нет необходимости выполнять многопеременную инверсию для каждого из слагаемых над всеми ранее проверенными. В итоге результирующее выражение для вероятности исходного графа, получающееся на основе стандартной формы перехода к замещению, задается путем рекурсивной процедуры, анализирующей на каждом шаге не все ранее полученные соотношения, а лишь часть из них.

Ключевые слова

сеть связи, граф, вероятность связности, многопеременная инверсия

Авторы

ФИООрганизацияДополнительноE-mail
Батенков Александр АлександровичОрловский государственный университет им. И.С. Тургеневапрофессор, доктор технических наук, профессорbatenkovl957@mail.ru
Батенков Кирилл АлександровичАкадемия Федеральной службы охраныдоцент, доктор технических наук, сотрудникpustur@yandex.ru
Фокин Александр БорисовичАкадемия Федеральной службы охранысотрудникtatarin57ru@mail.ru
Всего: 3

Ссылки

Chaturvedi S.K.Network Reliability Measures and Evaluation. Scrivener Publishing LLC, 2016. 237 p.
Рябинин И.А., Черкесов Г.Н. Логико-вероятностные методы исследования надежности структурно-сложных систем. М. : Радио и связь, 1981. 264 с.
Батенков К.А. Числовые характеристики структур сетей связи // Труды СПИИРАН. 2017. № 4 (53). С. 5-28.
Батенков К.А., Батенков А.А. Анализ и синтез структур сетей связи по детерминированным показателям устойчивости // Труды СПИИРАН. 2018. № 3 (58). С. 128-159.
Shengjie Xu, Yi Qian, Rose Qingyang Hu. Reliable and resilient access network design for advanced metering infrastructures in smart grid // IET Smart Grid. 2018. V. 1 (1). P. 24-30.
Xu S., Qian Y., Hu R.Q. A data-driven preprocessing scheme on anomaly detection in big data applications // Proc. in 2017 IEEE Conf. on Computer Communications Workshops (INFOCOM WKSHPS), Atlanta, GA, USA, May, 2017. doi: 10.1109/INFCOMW.2017.8116481
Ye F., Qian Y., Hu R.Q., et al. Reliable energy-efficient uplink transmission for neighborhood area networks in smart grid // IEEE Trans. Smart Grid. 2015. V. 6 (5). P. 2179-2188.
Ye F., Qian Y., Hu R.Q. Energy efficient self-sustaining wireless neighborhood area network design for smart grid // IEEE Trans. Smart Grid. 2015. V. 6 (1). Р. 220-229.
Ye F., Liang Y., Zhang H. et al. Design and analysis of a wireless sensor based monitoring network for transmission lines in smart grid // Wirel.Commun. Mob.Comput. 2016. V. 16 (10). P. 1209-1220.
Xu S., Qian Y. Quantitative study of reliable communication infrastructure in smart grid NAN // Proceedings in Design of Reliable Communication Networks. Kansas City, MO, USA, 2015. doi: 10.1109/DRCN.2015.7148994
Zuev K.M., Wu S., Beck J.L.Network reliability problem and its efficient solution by Subset Simulation // Probabilistic Engineering Mechanics. 2015. V. 40. P. 25-35.
ГОСТ Р 53111-2008. Устойчивость функционирования сети связи общего пользования. Требования и методы проверки. Введ. 2008-12-18. М. : Стандартинформ, 2009. 16 с.
Филин Б.П. Методы анализа структурной надежности сетей связи. М. : Радио и связь, 1988. 208 с.
Zhang H.C., Xu D.L., Lu C., Qi E.R., Tian C., Wu Y.S. Connection effect on amplitude death stability of multi-module floating airport // Ocean Eng. 2017. V. 129. P. 46-56.
Pino W., Gomes T., Kooij R. A Comparison between Two All-Terminal Reliability Algorithms // Journal of Advances in Computer Networks. 2015. V. 3 (4). P. 284-290.
Paredes R., Duenas-Osorio L., Meel K.S., Vardi M.Y.Network Reliability Estimation in Theory and Practice : Preprint submitted to Reliability Engineering & System Safety. 2018. 26 p.
Батенков А.А., Батенков К.А., Фокин А.Б. Методы формирования множеств состояний телекоммуникационных сетей для различных мер связности // Труды СПИИРАН. 2020. № 3 (19). C. 644-673.
Батенков К.А. Точные и граничные оценки вероятностей связности сетей связи на основе метода полного перебора типовых состояний // Труды СПИИРАН. 2019. Т. 18, № 5. С. 1093-1118.
Райгородский А.М. Модели случайных графов и их применения // Труды МФТИ. 2010. Т. 2, № 4. С. 130-140.
Lin M., Ting C. A polynomial-time algorithm for computing K-terminal residual reliability of d-trapezoid graphs // Inf. Process. Lett. 2015. V. 115 (2). Р. 371-376.
Housni K. An Efficient Algorithm for Enumerating all Minimal Paths of a Graph // International Journal of Advanced Computer Science and Applications, 2019. V. 10. P. 450-460. doi: 10.14569/IJACSA.2019.0100159
Bai G.H., Tian Z.G., Zuo M.J. An improved algorithm for finding all minimal paths in a network // Reliability Engineering and System Safety. 2016. V. 150. P. 1-10.
Pino W., Gomes T., Kooij R. A Comparison between Two All-Terminal Reliability Algorithms // Journal of Advances in Computer Networks. 2015. V. 3 (4). P. 284-290.
Silva J., Gomes T., Tipper D. et al. An effective algorithm for computing all-terminal reliability bounds // Networks, 2015. V. 66 (4). P. 282-295.
 Анализ вероятности связности телекоммуникационной сети на основе инверсий ее состояний | Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2022. № 59. DOI: 10.17223/19988605/59/10

Анализ вероятности связности телекоммуникационной сети на основе инверсий ее состояний | Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2022. № 59. DOI: 10.17223/19988605/59/10