Расчёт надежности сети с ограничением на диаметр

Назначение - программа предназначена для точного расчета надежности сети с  ограничением на диаметр.

Область применения - анализ надёжности и живучести сетей, в которых соединение между двумя узлами может быть установлено только при ограниченном количестве транзитных узлов.

При анализе надёжности сетей обычно используется такой показатель надёжности, как вероятность связности сети. Однако во многих случаях требуется обеспечить не просто существование пути между каждой парой выбранных узлов, а существование пути, проходящего через ограниченное число транзитных узлов (p2p-сети, ad hoc-сети). В таких случаях может быть использован другой показатель надёжности – вероятность связности сети с ограничением на диаметр [1], т.е. вероятность того, что любые два полюса сети соединены путём, состоящим из ограниченного количества каналов связи.

Как и задача расчёта надёжности сети, задача расчёта надёжности сети с ограничением на диаметр NP-трудна. Более того, наличие ограничения на диаметр делает расчёт надёжности существенно более трудоёмким, так как в случае отсутствия этого ограничения используются различные методы редукции, декомпозиции, направленное ветвление, и другие методы ускорения расчёта. В основном эти методы не адаптированы или в силу разных причин не могут быть применены для расчёта надёжности с ограничением на диаметр.

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

Входные данные программы – структура сети в виде графа, значения надёжности каналов связи (т.е. вероятности их присутствия), значение диаметра (целое число).

Выходные данные программы – значение надёжности сети.

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

[1] Cancela H., Petingi L. Reliability of communication networks with delay constraints: computational complexity and comlete topologies // Int. J. of Mathematics and Mathematical Sciences. 2004. V. 29. P. 1551-1562.

[2] Мигов Д.А. Расчет надежности сети с ограничением на диаметр с применением точек сочленения // Автоматика и телемеханика. 2011. – № 7. – С. 69-74.

[3] Migov D.A., Rodionov A.S. Decomposing Graph with 2-node cuts for Diameter Constrained Network Reliability Calculation // Proc. of the 7th Int. Conference on Ubiquitous Information Management and Communication (ACM ICUIMC 2013), Kota Kinabalu, Malaysia, 2013. ACM New York, USA, 2013. Article No. 39, ISBN 978-1-4503-1958-4.

Функциональные возможности - расчёт надёжности сетей с количеством элементов около  сотни.
Инструментальные средства создания - Delphi.