Анализ вероятностных характеристик некоторых систем сетевой структуры тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Алдын-оол, Татьяна Андреевна

• Алдын-оол, Татьяна Андреевна
• кандидат физико-математических наук
• 2011

Оглавление диссертации кандидат физико-математических наук Алдын-оол, Татьяна Андреевна

Введение

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 Расписание М1£

2.4 Расписание М2£

2.5 Расписание М3е

2.6 Решение задачи I. Модели покрытия области (условие 1) . 50 2.6.1 Расписание М1£1.

2.6.2 Расписание М2£2.

2.6.3 Расписание М3£з.

2.6.4 Нижняя оценка максимального времени функционирования сенсорной сети (условие 1)

2.7 Решение задачи II. Модели покрытия области (условие 2)

2.7.1 Расписание МIе*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 Сравнение моделей VIе\ V2а и 73е*.

3.2.2 Проверка точности нижних оценок Ьмг°ч, Ьмзаз максимального времени функционирования сенсорной сети.

Введение диссертации (часть автореферата) на тему «Анализ вероятностных характеристик некоторых систем сетевой структуры»

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

Структуры в виде графа характерны для больших территориально распределенных коммуникационных сетей. Под коммуникационной сетью в работе понимается любая сеть, узлы которой соединяются между собой каналами, способными передавать из узла в узел потоки различной природы: информацию (сообщения, данные), энергию (электрическую). При анализе сети одной из основных является задача оценки ее надежности. Выбор исследуемого показателя надежности зависит от особенностей конкретной сети и ее назначения [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 <i< < а, 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. Разработан комплекс программ для оценки времени функционирования совокупности случайных покрытий. Проведены численные эксперименты, подтвердившие точность полученных оценок.

Заключение

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

Список литературы диссертационного исследования кандидат физико-математических наук Алдын-оол, Татьяна Андреевна, 2011 год

1. Алдын-оол Т.А., Ерзин А.И, Шамардин Ю.В. Анализ надежности решетчатых графов // Материалы Российской конференции "Дискретная оптимизация и исследование операций" (Владивосток,2007). Новосибирск: Изд-во Ин-та математики, 2007. С. 117.

2. Алдын-оол Т.А., Ерзин А.И. О надежности последовательно-параллельных сетей в решетчатых графах // Труды XIV Байкальской межд. школы-семинара "Методы оптимизации и их приложения" (Северобайкальск, 2008). Иркутск: ИСЭМ СО РАН, 2008. Т. 1. С. 312-321.

3. Алдын-оол Т.А., Ерзин А.И. О надежности последовательно-параллельных сетей в решетчатых графах // Вестник НГУ. Серия: Математика, механика, информатика. 2009. Т. 9, вып. 2. С. 3-14.

4. Алдын-оол Т.А., Ерзин А.И. Максимизация времени жизни сенсорной сети при случайном распределении сенсоров // Материалы

5. Всероссийской конференции "Проблемы оптимизации и экономические приложения" (Омск, 2009). Омск: Полиграфический центр КАН, 2009. С. 108.

6. Алдын-оол Т.А., Ерзин А.И, Залюбовский В.В. Покрытие плоской области случайно распределенными сенсорами // Вестник НГУ. Серия: Математика, механика, информатика. 2010. Т. 10, вып. 4. С. 7-25.

7. Астраков С.Н, Ерзин А.И., Залюбовский В.В. Сенсорные сети и покрытие плоскости кругами // Дискретный анализ и исследование операций. 2009. Т. 16, № 3. С. 3-19.

8. Гадяцкая O.A. Применение EDP-полиномов при выборе оптимальных структур // Вестник НГУ. Серия: Математика, механика, информатика. 2008. Т. 8, вып. 1. С. 3-14.

9. Гнедеико Б.В. Курс теории вероятностей. М.: Наука, 1988. 448 с.

10. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.

11. Дискретная математика и математические вопросы кибернетики. Т. 1 / Под общ. ред. Яблонского C.B., Лупанова О.Б. М.: Наука, 1974. 312 с.

12. Ерзин А.И., Паршин Г.Г. Задача синтеза надежной сети связи ограниченного веса // Управляемые системы. 1993. Вып. 31. С. 3-9.

13. Ерзин А.И., Залюбовский В.В. Максимизация времени функционирования беспроводных сенсорных сетей // Труды XIV Байкальской межд. школы-семинара "Методы оптимизации и их приложения". Иркутск: ИСЭМ СО РАН, 2008. Т. 1. С. 363-369.

14. Забудский Г.Г. О задаче линейного упорядочения паралельно-по-следовательных графов // Дискретный анализ и исследование операций. 2000. Т. 7, № 1. С. 61-64.

15. Калиткин H.H. Численные методы. М.: Наука, 1978. 512 с.

16. Кельманс А.К. Некоторые вопросы анализа надежности сетей // Автоматика и телемеханика. 1965. Т. 26, № 3. С. 567-574.

17. Кривулец В.Г., Полесский В.П. Квазиупаковочные оценки характеристик надежности сетей // Информационные процессы. 2001. Т. 1, № 2. С. 126-146.

18. Ломоносов М.В., Полесский В.П. Верхняя граница, надежности информационных сетей // Проблемы передачи информации. 1971. Т. 7, вып. 4. С. 78-81. ;

19. Ломоносов М.В., Полесский В.П. Нижняя оценка надежности сетей // Проблемы передачи информации. 1972. Т. 8, вып. 2. С. 47-53.

20. Мигов Д.А. Формулы для быстрого расчета вероятности связности подмножества вершин в графах небольшой размерности // Проблемы информатики. 2010. № 2. С. 10-17.

21. Мур Э., Шеннон К. Надежные схемы из ненадежных реле // Кибернетический сборник. М.: ИЛ, 1960. Вып. 1. С. 109-148.

22. Надежность технических систем: справочник / Под ред. Ушакова И.А. М.: Радио и связь, 1985. 608 с.

23. Полесский В.П. Об одной нижней границе надежности информационных сетей // Проблемы передачи информации. 1971. Т. 7, вып. 2. С. 88-96.

24. Попков В.К. Математические модели связности. Новосибирск: Изд. ИВМиМГ СО РАН, 2006. 490 с.

25. Райншке К., Ушаков И.А. Оценка надежности систем с использованием графов. М.: Радио и связь, 1988. 208 с.

26. Родионова O.K. Некоторые методы ускорения расчета надежности информационных сетей // Материалы XXX Международной конференции "Информационные технологии в науке, образовании, телекоммуникации и бизнесе" (Гурзуф, Украина, 2003). С. 215-217.с

27. Тот Л.Ф. Расположения на плоскости, на сфере и в пространстве. М.: Физматлит, 1958. 364 с.

28. Филин Б.П. Методы анализа структурной надежности сетей связи. М: Радио и связь, 1988. 208 с.

29. Цициашвили Г.Ш. Асимптотические формулы для вычисления надежности решеток // Дальневосточный математический журнал. 2010. Т. 10, № 1. С. 86-90.

30. Aboelfotoh Н.М., Colbourn C.J. Series-parallel bounds for the two-terminal reliability problem // ORSA Journal on Computing. 1989. Vol. 1, № 4. P. 209-222.

31. Anastasi J., Conti M., Di Francesco M., Passarella A. Energy-conservation in wireless sensor networks: a survey // Ad Hoc Networks. 2009. Vol. 7, № 3. P. 537-568.

32. Ball M.O., Provan J.S. Calculating bounds on reachability and connectedness in stochastic networks // Networks. 1983. Vol. 13. P. 253-278.

33. Ball M.O., Colbourn C.J., Provan J.S. Network reliability // Handbooks in Operation Research and Management Science. 1995. Vol. 7. P. 673762.

34. Berman P., Galinescu G., Shan C., Zelikovsky A. Power efficient monitoring management in sensor networks // Proceedings of IEEE Wireless Communications and Networking Conference. 2004. P. 23292334.

35. Brecht T.B., Colbourn C.J. Lower bounds on two-terminal network reliability // Discrete Applied Mathematics. 1988. Vol. 21, № 3. P. 185198.

36. Brown J.I., Colbourn C.J., Nowakowski R.J. Chip firing and all-terminal network reliability bounds // Discrete Optimization. 2009. Vol. 6, № 4. P. 436-445.

37. Cardei M., Thai M.T., Li Y., Wu W. Energy-efficient target coverage in wireless sensor networks // Proceedings of the 24th Conference of the IEEE Communications Society (INFOCOM 2005). 2005. P. 1976-1984.

38. Cardei M., Wu J., Ku M. Improving network lifetime using sensors with adjustable sensing ranges // International Journal of Sensor Networks. 2006. Vol. 1, № 1. P. 41-49.

39. Chari M.K., Provan J.S. Calculating ^-connectedness reliability using steiner bounds // Mathematics of Operations Research. 1996. Vol. 21, № 4. P. 905-921.

40. Colbourn C.J. The combinatorics of network reliability. New York: Oxford University Press, 1987. 160 p.

41. Deeter D.L., Smith A.E. Economic design of reliable networks // IEEE Transactions on Reliability. 1998. Vol. 30. P. 1161-1174.

42. Fan G., Wang R., Huang H., Sun L., Sha C. Coverage-guaranteed sensor node deployment strategies for wireless sensor networks // Sensors. 2010. Vol. 10, № 3. P. 2064-2087.

43. Jan R.-H., Hwang F.-J., Chen S.-T. Topological optimization of a communication network subject to a reliability constraint // IEEE Transactions on Reliability. 1993. Vol. 42. P. 63-70.

44. Johnson D.S. The NP-completeness column: an ongoing guide // Journal of Algorithms. 1982. Vol. 3, № 4. P. 381-395.

45. Johnson D.S. The NP-completeness column: an ongoing guide // Journal of Algorithms. 1985. Vol. 6, № 1. P. 145-159.

46. Kaustov V.A., Litvak Ye.I., Ushakov I.A. The computational effectiveness of reliability estimates by the method of nonedge-intersecting chains and cuts // Soviet Journal on Computing and Systems Science. 1986. Vol. 24. P. 59-62.

47. Kershner R. The number of circles covering a set // American Journal of Mathematics. 1939. Vol. 61, № 3. P. 665-671.

48. Koide Т., Shinmori S., Ishii H. Topological optimization with a network reliability constraint // Discrete Applied Mathematics. 2001. Vol. 115, № 1-3. P. 135-149.

49. Liskiewicz M., Ogihara M., Toda S. The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes // Theoretical computer science. 2003. Vol. 304, № 1-3. P. 129-156.

50. Pierre S., Hyppolite M.-A., Bourjolly J.M., Dioume O. Topological design of computer communication networks using simulated annealing // Engineering Applications of Artificial Intelligence. 1995. Vol. 8, № 1. P. 61-69

51. Provan J.S., Ball M.O. The complexity of counting cuts and of computing the piobability that a graph is connected // SIAM Journal on Computing. 1983. Vol. 12, № 4. P. 777-788.

52. Provan J.S. The complexity of reliability computations in planar and acyclic graphs // SIAM Journal on Computing. 1986. Vol. 15, № 3. P. 694-702.

53. Raman V. Finding the best edge-packing for two-terminal reliability is NP-hard // Journal of Combinatorial Mathematics and Combinatorial Computing. 1991. Vol. 9. P. 91-96.

54. Robbins H.E. On the measure of a random set // The Annals of Mathematical Statistics. 1944. Vol. 15, № 1. P. 70-74.

55. Rodionov A.S., Rodionova O.K., Choo H. On the expected value of a number of disconnected pairs of nodes in unreliable networks

56. International Conference on Computational Science and Its Applications (ICCSA 2007) (Kuala Lumpur, Malaysia, 2007). Springer, Lecture Notes in Computer Science, 2007. Vol. 4707. P. 534-543.

57. Satyanarayana A., Wood R.K. A linear time algorithm for computing ¿-terminal reliability in series-parallel networks // SIAM Journal on Computing. 1985. Vol. 14, № 4. P. 818-832.

58. Shooman A.M. Algorithms for network reliability and connection availability analysis // Electro/95 International Professional Program Proceedings. 1995. P. 309-333.

59. Takamizawa K., Nishizeki T., Saito N. Combinatorial problems on series-parallel graphs // 17th Symposium of Research Institute of Electrical Communication (Sendai, Japan, 1980). Springer, Lecture Notes in Computer Science, 1981. Vol. 108. P. 79-94.

60. Van Slyke R., Frank H. Network reliability analysis: part I // Networks. 1972. Vol. 1. P. 279-290.

61. Wagner D.K. Disjoint (s,t)~cuts in a network // Networks. 1990. Vol. 20, № 4. P. 361-371.

62. Wu J., Yang S. Energy-efficient node scheduling models in sensor networks with adjustable ranges // International Journal of Foundations of Computer Science. 2005. Vol. 16, № 1. P. 3-17.

63. Yen L.-H., Yu C.W., Cheng Y.M. Expected k-coverage in wireless sensor networks //Ad Hoc Networks. 2006. Vol. 5, № 4. P. 636-650.

64. Zalyubovskiy V., Erzin A., Astrakov S., Choo H. Energy-efficient area coverage by sensors with adjustable ranges // Sensors. 2009. Vol. 9, № 4. P. 2446-2460.

65. Zhang H., Hou J. On deriving the upper bound of a-lifetime for large sensor networks // Proceedings of the 5th ACM International Symposium on Mobile Ad Hoc Networking and Computing (Tokyo, Japan, 2004), 2004. P. 121-132.