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

Аннотация

В работе рассматривается один из методов анализа и синтеза структур сетей связи, основанный на наиболее простом подходе к вопросу расчета вероятности связности — методе полного перебора типовых состояний сети. При этом под типовыми состояниями сети понимаются события связности и несвязности графа сети, представляющие собой простые цепи и сечения данного графа. Несмотря на существенный недостаток метода полного перебора типовых состояний, который заключается в значительной трудоемкости проводимых вычислений, он оказывается достаточно востребованным. Кроме того, на его основе возможно получать граничные оценки вероятности связности сети. Так, при расчете границ Эзари — Прошана используется полный набор несвязных (для верхней) и связных (для нижней) состояний сети связи. Данные границы основаны на утверждении, что вероятность связности сети при тех же условиях выше (ниже), чем у сети, составленной из последовательного (параллельного) соединения полного набора независимых несвязных (связных) подграфов. При расчете границ Литвака — Ушакова используются только реберно-непересекающиеся сечения (для верхней) и связные подграфы (для нижней), то есть подмножества элементов такие, в которых какой-либо элемент не встречается дважды. В данной границе учтено широко известное естественное свойство монотонности, заключающееся в уменьшении (увеличении) надежности сети при снижении (повышении) надежности любого элемента. С точки зрения сложности вычислительных процедур границы Эзари — Прошана имеют существенный недостаток: они предполагают определение всех связных подграфов для расчета верхней границы и минимальных разрезов для нижней, что само по себе нетривиально. Границы Литвака — Ушакова подобными недостатками не страдают: вычисляя их, можно ограничиться перебором необходимого числа вариантов наборов независимых связных и несвязных состояний графа.

Abstract

We consider one of communication network structure analysis and synthesis methods, based on the simplest approach to connectivity probability calculation – a method of full network typical state search. In this case, the typical states of the network are understood as the events of network graph connectivity and disconnection, which are simple graph chains and sections. Despite significant drawback of typical state enumeration method, which involves significant calculation complexity, it is quite popular at stage of debugging new analysis methods. In addition, on its basis it is possible to obtain boundary estimates of network connectivity probability. Thus, when calculating Asari–Proshana boundaries use full set of incoherent (top) and cohesive (bottom) communication network states. These boundaries are based on statement that network connectivity probability under same conditions is higher (lower) than that of network composed of independent disjoint (connected) subgraph complete set serial (parallel) connection. When calculating Litvak–Ushakov boundaries, only edge-disjoint sections (for upper) and connected subgraphs (for lower) are used, i.e. subsets of elements such that any element does not meet two-rods. This boundary takes into account the well-known natural monotonicity property, which is to reduce (increase) network reliability with decrease (increase) any element reliability. From a computational view point Asari–Proshana boundaries have huge drawback: they require references of all connected subgraphs to compute upper bounds and all minimal cuts for bottom, which in itself is non-trivial. Litvak–Ushakov boundaries are devoid of these drawback: by calculating them, we can stop at any searching step for variants of sets of independent connected and disconnected graph states.