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

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

Структуры в виде графа характерны для больших территориально распределенных коммуникационных сетей. Под коммуникационной сетью в работе понимается любая сеть, узлы которой соединяются между собой каналами, способными передавать из узла в узел потоки различной природы: информацию (сообщения, данные), энергию (электрическую). При анализе сети одной из основных является задача оценки ее надежности. Выбор исследуемого показателя надежности зависит от особенностей конкретной сети и ее назначения [26,35]. Важным показателем надежности является связность сети. Существуют различные характеристики связности. Так в работе [54] надежной считается Ксвязная сеть для некоторого целого числа К > 2. В работах [9,59] в качестве показателя надежности используется математическое ожидание числа несвязных пар узлов. Основные характеристики связности и связанные с ними задачи анализа надежности сети приведены в монографии Попкова В. К. [25]. Одним из наиболее исследуемых показателей надежности сети является вероятность связности выделенного подмножества узлов [13,17,20,30,44,46,51,60].

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

В качестве математической модели сети в главе 1 используется граф Н — (У, Е), где V — множество абсолютно надежных вершин, а Е — множество ребер. Каждое ребро может находиться в одном из двух состояний — исправное или неисправное. Ребру е Е Е приписана вероятность исправного функционирования ре? [0,1], которую будем называть надежностью ребра. Предполагаем, что состояния ребер — это независимые события. Под надежностью сети с источником и и множеством стоков V' С {V и} понимается вероятность того, что для каждой вершины V € V' существует хотя бы один путь из вершины и в вершину V, состоящий из исправных ребер. Вершины множества {и U V'} назовем терминалами сети. Проблема вычисления надежности сети в общем случае является NP-трудной [11].

Первая научная публикация, посвященная анализу надежности сети, появилась в 1956 году, ее авторы Мур Э. Ф. (Moore E.F.) и Шеннон К. Э. (Shannon С.Е.) [22]. К настоящему времени опубликовано значительное количество работ, в которых рассматриваются задачи вычисления надежности сети, а также задачи оценки надежности сети. Прежде всего отметим результаты следующих ученых. Ломоносов М. В. и Полесский.

В.П. одни из первых предложили полиномиально вычислимые верхние и нижние оценки надежности сети [19,20,24]. Прован Дж.С. (Provan J.S.) и Болл М. О. (Ball М.О.) доказали NP-трудность некоторых частных случаев задачи вычисления надежности сети, в частности, когда множество терминалов состоит из всех вершин сети, а надежности ребер одинаковые, получили полиномиально вычислимые оценки надежности сети для данного случая [34,55,56]. Родионовым A.C. и Родионовой O.K. разработаны методы расчета надежности сети, применимые к задачам малой и средней размерности [27,28]. Многие работы Колбурна Ч.Дж. (Colbourn C.J.) посвящены задачам оценки надежности сети [35,39,43].

Среди точных способов вычисления надежности сети выделим метод ветвления Мура-Шеннона, а также его модификации [22,27]- подходы, основанные на эквивалентных преобразованиях сети [28,62]. Наиболее известным точным методом вычисления надежности сети является метод Мура-Шеннона. В силу формулы полной вероятности [10] надежность сети можно представить в виде.

Р (Н) = реР (Н*(е)) + (1 — ре) Р (Н (е)), (1) где Н*{е) — сеть, в которой вероятность исправности ребра е равна ре = 1, Н{е) — сеть, в которой вероятность исправности ребра е равна ре = 0. Метод Мура-Шеннона, заключается в рекурсивном применении формулы (1). С помощью этого метода или другого точного метода можно посчитать надежность любой сети, но трудоемкость таких методов является экспоненциальной. Поэтому многие работы посвящены эффективному (имеющему полиномиальную трудоемкость) построению оценок надежности сети.

Одну из первых полиномиально вычислимых нижних оценок надежности сети предложил Полесский В. П. [24]. В его работе рассматривается случай, когда сеть является неориентированной, и множество терминалов состоит из всех вершин сети. Оценка Полесского имеет вид.

Р (Н) /.

Р{Н)> 1- П 1- ЦРе.

1 V ее#г где @(Н) — максимальное число ребсрно непересекающихся остовов сети Н, Н{ - г-ый остов из некоторой максимальной системы остовов.

Обзор по эффективно вычислимым оценкам надежности сети можно найти в работах [35,43]. Многие известные полиномиально вычислимые оценки основаны на перечислении подграфов или получены с помощью реберной упаковки сети [35]. Опишем кратко суть таких методов. .

1. Методы, основанные на перечислении подграфов [34,42,64]. Пусть надежности ребер сети одинаковые и равны р. В этом случае надежность сети можно представить в виде полинома от р, называемого полиномом надеэюности. Полином надежности может быть записан несколькими способами, например,.

Е г=0 где N1 — количество подграфов с числом ребер, равным г, в каждом из которых множество терминалов связное. Различные формы полинома надежности можно найти в работе [35]. Нижняя (верхняя) оценка коэффициентов полинома надежности дает нижнюю (верхнюю) оценку надежности всей сети.

2. Методы, основанные на реберной упаковке сети [18,19,24,32,38,65]. Пусть {Яь ., Нк} ~ множество реберно непересекающихся подграфов сети Н, связывающих терминалы. Очевидно, что для надежности сети Н справедлива следующая нижняя оценка: к.

Р (Н)>1-Ц (1-Р (Н,)). (2) г=1.

В настоящее время оценка (2) достаточно исследована только для случая связывающих деревьев Щ. Аналогично оценке (2), используя множество разрезов, можно выписать верхнюю оценку надежности сети: I.

ПЩ<�Ц (1−1[(1-ре)1 где {Сх,., С1} - множество реберно непересекающихся разрезов для множества терминалов.

В ряде приложений сеть имеет регулярную топологию, и представляет интерес задача построения специально разработанных оценок надежности для такой сети. Обозначим через ./V2 множество всех точек на плоскости с целыми координатами. Под решеткой С с источником й = (0,0) и стоком? = (а, Ъ) € А" 2 (а, Ъ > 0) понимается неориентированный граф, вершинами которого являются точки {(г^) € А" 2|0 < а, 0 < 2 < &}, две вершины = (ц^г) и у2 = (?21.72) соединены ребром, если ??2 — ч + — 2\ = 1, т. е. расстояние между ними в метрике Ь равно единице. Надежность каждого ребра равна р 6 [0,1]. Требуется построить нижнюю оценку надежности решетки (7. Такая постановка моделирует проблему оценки вероятности передачи потока из одного терминального узла в другой в сети с решетчатой топологией, каналы связи которой однотипны, находятся в одинаковых условиях и могут выходить из строя с равной вероятностью..

Математическая модель второй рассматриваемой в диссертационной работе системы сетевой структуры следующая. Конечное множество элементов М случайно распределено в плоской выпуклой области О. Элемент г Е М расположен в точке Д 6 О, Областью покрытия элемента г Е М является круг с центром в точке Р{ и радиусом Я{ Е [0,Лшаа-]. Величина Я{ называется радиусом покрытия. Под покрытием в работе понимается подмножество С = {(г, Рг, Дг)|г Е М', М' С М, Дг Е (0,Ятаж]} расположенных в области О элементов с назначенным для каждого из них радиусом покрытия. Требуется построить совокупность покрытий, удовлетворяющих заданным требованиям. Первые подобные задачи рассматривались в рамках дискретной геометрии [29]. Отдельные публикации появились в первой половине двадцатого века. Основным критерием качества покрытия является его плотность. Плотность покрытия С определяется величиной Е геМ'.

11(0) где 1)(г, Е4) — круг с центром в точке Р{ и радиусом ц (Х) — площадь области X. В работе [50] Кешнер Р. (КегэЬпег Я.) предложил наименее плотное покрытие, в котором используются элементы с одинаковыми радиусами покрытия. В 1953 году появилась монография Тота Л. Ф. (То^ Ь.Р.) [29], посвященная вопросам дискретной геометрии, в которой, в частности, рассматриваются экстремальные задачи покрытия плоских областей..

В диссертационной работе предполагается, что каждому элементу приписан некоторый ресурс, потребление которого зависит от времени функционирования элемента и покрываемой им площади. Функционирование системы определяется множеством {(Сь ?1),., (С/, ¿-г)}, где С к — некоторое покрытие, а > 0 — время функционирования покрытия С к. В работе рассматривается два показателя качества покрытия, для чего вводятся понятия сильного (^-покрытия и ф-покрытия. Говорим, что точка, а Е О покрыта, если, а находится в области покрытия хотя бы одного элемента. Для заданной величины С} € (0,1) покрытие называется сильным (^-покрытием, если вероятность того, что все точки области О покрыты, не меньше ф. И покрытие называется ф-покрытием, если математическое ожидание доли области, состоящей из всех покрытых точек области О, не меньше ф. Представляет интерес нахождение аналитических оценок максимального времени функционирования системы..

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

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

Исследуемая в диссертационной работе модель представляет подход к математическому моделированию, в частности, сенсорных сетей, сетей радиосвязи, различных телеметрических систем. Покажем адекватность модели на примере сенсорной сети. Сенсорная сеть представляет собой совокупность компактных электронных устройств — сенсоров, каждое из которых может осуществлять сбор и первичную обработку собранной информации, а также обмениваться информацией с другими сенсорами посредством радиосвязи. Проблема рационального расходования энергии является одной из основных при проектировании сенсорной сети [33], и из-за автономности сенсоров задача получения аналитических оценок максимального времени функционирования для сенсорной сети стоит особенно остро. Наиболее энергоемкими функциями сенсора являются мониторинг и обмен данными. В силу того, что во многих приложениях мониторинг осуществляется непрерывно, а обмен даннымилишь эпизодически, во многих работах, посвященных анализу времени функционирования сенсорной сети, рассматривается только первая составляющая энергопотребления, и расходование энергии одним сенсором зависит от времени его функционирования и площади мониторинга. При мониторинге труднодоступных или опасных для человека областей не всегда удается разместить сенсоры в заданных местах, поэтому сенсоры распределяются случайно, и в описывающих сенсорную сеть моделях местоположения сенсоров рассматриваются как случайные величины [45,67]. Часто предполагается, что областью покрытия сенсора является круг с центром в месте расположения сенсора [66]..

В большинстве работ, посвященных вопросам функционирования сенсорной сети, исследуется задача максимизации времени жизни [14,36,41]. Проблема получения оценок времени жизни сенсорной сети исследована недостаточно, и результаты получены лишь для нескольких моделей сенсорной сети [37,53,70]..

Целью диссертационной работы является разработка методов оценивания вероятностных показателей качества функционирования систем сетевой структуры..

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

Разработаны новые модели случайных покрытий плоской области кругами, обеспечивающие эффективное (ресурсосберегающее) использование элементов системы..

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

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

Диссертационная работа состоит из введения, трех глав, заключения и списка литературы..

Основные результаты работы заключаются в следующем. •.

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

2. Разработаны новые модели случайных покрытий плоской области кругами, обеспечивающие эффективное (ресурсосберегающее) использование элементов системы..

3. Впервые получены аналитические нижние оценки максимального времени функционирования совокупности случайных покрытий в условиях ограниченности ресурсов элементов системы..

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

Заключение.

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