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

• Автор: Алдын-оол, Татьяна Андреевна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Новосибирск
• Количество страниц: 100 с. : ил.

Оглавление
Введение

1 Построение максимально надежных последовательнопараллельных сетей на решетке

1.1 Постановка задами.

1.2 Вспомогательные утверждения.

1.3 Основные утверждения.

1.4 Сравнение оценок надежности решетки

1.4.1 Модифицированная оценка КраскалаКатоны .

1.4.2 Оценка БрехтаКолбурн а

1.4.3 Метод МураШеннона.

2 Покрытие плоской области случайно распределенными элементами

2.1 Математическая модель на примере сенсорной сети.
Постановка задач.
2.2 Детерминированные регулярные покрытия А1, АЗ и ВЗ .
2.3 Расписание М Iе .
2.4 Расписание М2
2.5 Расписание М3
2.6 Решение задачи I. Модели покрытия области условие 1 .
2.6.1 Расписание М 1х.
2.6.2 Расписание М2е2
2.6.3 Расписание М3з
2.6.4 Нижняя оценка максимального времени функционирования сенсорной сети условие 1 . . .
2.7 Решение задачи II. Модели покрытия области условие 2 .
2.7.1 Расписание М 1х.
2.7.2 Расписание М2С2.
2.7.3 Расписание МЗПз
2.7.4 Нижняя оценка максимального времени функционирования сенсорной сети условие 2 . . .
3 Программные средства оценки эффективности случайных покрытий сенсорами с регулируемыми радиусами мониторинга
3.1 Расчет времени функционирования сенсорной сети
3.1.1 Построение сенсорной сети
3.1.2 Программная реализация расчета времени функционирования сенсорной сети
3.2 Результаты численных экспериментов.
3.2.1 Сравнение моделей У1а, У2а и УЗа.
3.2.2 Проверка точности нижних оценок л22,
Ьмуч максимального времени функционирования сенсорной сети
Заключение
Список литературы


К настоящему времени опубликовано значительное количество работ, в которых рассматриваются задачи вычисления надежности сети, а также задачи оценки надежности сети. Прежде всего отметим результаты следующих ученых. Ломоносов М. В.П. Прован Дж. С. (Provan J. S.) и Болл М. О. (Ball М. О.) доказали NP-трудность некоторых частных случаев задачи вычисления надежности сети, в частности, когда множество терминалов состоит из всех вершин сети, а надежности ребер одинаковые, получили полиномиально вычислимые оценки надежности сети для данного случая [,,]. Родионовым A. C. и Родионовой O. K. разработаны методы расчета надежности сети, применимые к задачам малой и средней размерности [,]. Многие работы Колбурна Ч. Дж. Colbourn C. J.) посвящены задачам оценки надежности сети [,,]. Среди точных способов вычисления надежности сети выделим метод ветвления Мура-Шеннона, а также его модификации [,]; подходы, основанные на эквивалентных преобразованиях сети [,]. Наиболее известным точным методом вычисления надежности сети является метод Мура-Шеннона. Н~(с) - сеть, в которой вероятность исправности ребра е равна Ре = 1, Н(е) - есть, в которой вероятность исправности ребра е равна ре = 0. Метод Мура-Шеннона заключается в рекурсивном применении формулы (1). С помощью этого метода или другого точного метода можно посчитать надежность любой сети, но трудоемкость таких методов является экспоненциальной. Поэтому многие работы посвящены эффективному (имеющему полиномиальную трудоемкость) построению оценок надежности ости. Одну из первых полиномиально вычислимых нижних оценок надежности сети предложил Полесский В. П. []. В его работе рассматривается случай, когда сеть является неориентированной, и множество терминалов состоит из всех вершин сети. Р(Н) - максимальное число реберно непересекающихся остовов сети Я, Ні - г-ый остов из некоторой максимальной системы остовов. Обзор но эффективно вычислимым оценкам надежности сети можно найти в работах [,]. Многие известные полиномиально вычислимые оценки основаны на перечислении подграфов или получены с помощью реберной упаковки сети []. Опишем кратко суть таких методов. Методы, основанные на перечислении подграфов [,,]. Пусть надежности ребер сети одинаковые и равны р. В этом случае надежность сети можно представить в виде полинома от р, называемого полиномом надеоіспости. Щ - количество подграфов с числом ребер, равным г, в каждом из которых множество терминалов связное. Различные формы полинома надежности можно найти в работе []. Нижняя (верхняя) оценка коэффициентов полинома надежности дает нижнюю (верхнюю) оценку надежности всей сети. Методы, основанные на реберной упаковке сети [,,,,,]. Я, связывающих терминалы. Р(Н) = ? Р(Я)<П(1-П(1-А)). Сь . С*} - множество реберно непересекающихся разрезов для множества терминалов. В ряде приложений сеть имеет регулярную топологию, и представляет интерес задача построения специально разработанных оценок надежности для такой сети. Обозначим через Лг'2 множество всех точек на плоскости с целыми координатами. Под решеткой (7 с источником 5 = (0,0) и стоком Ь = (а, Ь) ? N2 (а, Ь > 0) понимается неориентированный граф, вершинами которого являются точки {(г, 7) € №|0 < г < < а, 0 < з < 6}, две вершины ь = (гь^) и г>2 = (г2,^2) соединены ребром, если г2 — ч Л- ]2 — jl = 1, т. Ь равно единице. Надежность каждого ребра равна р 6 [0,1]. Требуется построить нижнюю оценку надежности решетки (7. Такая постановка моделирует проблему оценки вероятности передачи потока из одного терминального узла в другой в сети с решетчатой топологией, каналы связи которой однотипны, находятся в одинаковых условиях и могут выходить из строя с равной вероятностью. Математическая модель второй рассматриваемой в диссертационной работе системы сетевой структуры следующая. Конечное множество элементов М случайно распределено в плоской выпуклой области О. Элемент г 6 М расположен в точке 1 € О. Областью покрытия элемента г ? М является круг с центром в точке Р* и радиусом Рг € [0, Ятах- Величина Р* называется радиусом покрытия.