автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Анализ вероятностных характеристик некоторых систем сетевой структуры

На правах рукописи

Лт1"

УДК 519.718+519.87

Алдын-оол Татьяна Андреевна

АНАЛИЗ ВЕРОЯТНОСТНЫХ ХАРАКТЕРИСТИК НЕКОТОРЫХ СИСТЕМ СЕТЕВОЙ СТРУКТУРЫ

05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических паук

Новосибирск - 2011

2 ИЮН 2011

4048648

4848648

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования "Новосибирский государственный университет".

Научный руководитель:

доктор физико-математических наук, профессор Ерзин Адиль Ильясович

Официальные оппоненты: доктор физико-математических наук,

старший научный сотрудник Кельманов Александр Васильевич

доктор технических наук, старший научный сотрудник Родионов Алексей Сергеевич

Ведущая организация: Государственное образовательное

учреждение высшего профессионального образования "Омский государственный университет им. Ф.М. Достоевского"

Защита состоится 21 июня 2011 г. в 16 час. 30 мин. на заседании диссертационного совета Д 003.061.02 при Учреждении Российской академии наук Институте вычислительной математики и математической геофизики Сибирского отделения РАН по адресу: 630090, г. Новосибирск, проспект Академика Лаврентьева, 6.

С диссертацией можно ознакомиться в библиотеке Учреждения Российской академии наук Института вычислительной математики и математической геофизики Сибирского отделения РАН.

Автореферат разослан 19 мая 2011 г.

Ученый секретарь диссертационного совета д.ф.-м.н.

Сорокин С.Б.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Объектом исследования данной работы являются проблемы оценивания качества функционирования технических систем, имеющих сетевую структуру. Предмет исследования — модели технических систем, заданные в виде графов и случайных покрытий.

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

Структуры в виде графа характерны для больших территориально распределенных коммуникационных сетей. Под коммуникационной сетью в работе понимается любая сеть, узлы которой соединяются между собой каналами, способными передавать из узла в узел потоки различной природы: информацию (сообщения, данные), энергию (электрическую). При анализе сети одной из основных является задача оценки ее надежности. Одним из наиболее исследуемых показателей надежности сети является вероятность связности выделенного подмножества узлов, называемая далее для краткости надежностью. Первая научная публикация, посвященная анализу надежности сети, появилась в 1956 году, ее авторы Мур Э.Ф. (Moore E.F.) и Шеннон К.Э. (Shannon С.Е.). Проблема вычисления надежности сети в общем случае является NP-трудной, в связи с чем многие работы посвящены получению полиномиально вычислимых оценок надежности. К настоящему времени опубликовано значительное количество работ, в которых рассматриваются задачи оценки надежности сети в общем случае, тогда как задача оценки надежности сетей специального вида изучена мало. В ряде приложений сеть имеет регулярную топологию, поэтому представляет интерес построение оценок надежности для таких сетей. В диссертационной работе строится нижняя оценка надежности графагрешетки с одним источником и одним стоком, надежности ребер в котором одинаковые. Такая постановка моделирует проблему оценки вероятности передачи потока из одного терминального узла в другой в сети с решетчатой топологией, каналы связи которой однотипны, находятся в одинаковых условиях и могут выходить из строя с равной вероятностью.

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

вые подобные задачи рассматривались в рамках дискретной геометрии. Отдельные публикации по этой тематике появились в первой половине 20 века. Так, в 1939 году Кешнер P. (Kershner R.) предложил наименее плотное покрытие плоскости кругами одинакового радиуса. В 1953 году появилась монография Тота Л.Ф. (Toth L.F.) "Расположения на плоскости, на сфере и в пространстве", в которой, в частности, рассматриваются экстремальные задачи покрытия плоских областей. В диссертационной работе предполагается, что элементы системы распределены в области случайно, и каждому элементу приписан ресурс, потребление которого зависит от времени функционирования элемента и покрываемой им площади. Функционирование всей системы определяется совокупностью покрытий. При этом под покрытием понимается подмножество элементов с назначенной для каждого из них областью покрытия. Требуется, чтобы каждое покрытие удовлетворяло заданному критерию качества. Одной из важных задач является получение аналитических оценок максимального времени функционирования таких систем. Исследуемая в диссертационной работе модель представляет подход к математическому моделированию, в частности, сенсорных сетей, сетей радиосвязи, различных телеметрических систем. Для сенсорной сети, в силу ограниченности емкости элемента питания сенсора, задача получения аналитических оценок максимального времени функционирования стоит особенно остро. В большинстве работ, посвященных вопросам функционирования сенсорной сети, исследуется задача максимизации времени жизни в условиях ограниченности ресурсов сенсоров. В настоящее время проблема получения оценок времени жизни сенсорной сети исследована недостаточно, и результаты получены лишь для нескольких моделей. Поэтому разработка эффективных методов для получения аналитических оценок максимального времени функционирования совокупности случайных покрытий является актуальной задачей.

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

Методы исследования. В работе использовались методы теории вероятностей, комбинаторики, исследования операций, математического моделирования.

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

женной оценки осуществлено с известными эффективно вычислимыми оценками надежности сети в общем случае.

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

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

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

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

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

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

Апробация работы. Основные научные результаты диссертации докладывались и обсуждались на семинаре "Дискретные экстремальные задачи" (Новосибирск, 2008-2010) ИМ СО РАН, семинаре "Математические модели принятия решений" ИМ СО РАН (Новосибирск, 2010), объединенном семинаре кафедры Теоретической кибернетики Новосибирского Государственного Университета и отдела Теоретической кибернетики ИМ СО РАН (Новосибирск, 2011), семинаре "Моделирование инфо-коммуникационных систем" ИВМиМГ СО РАН (Новосибирск, 2011), семинаре "Математическое моделирование и дискретная оптимизация" ОФ ИМ СО РАН (Омск, 2011), Российских конференциях "Дискретная оптимизация и исследование операций" (Владивосток, 2007, и Алтай, 2010), VIII Всероссийской конференции молодых ученых по ма-

тематическому моделированию и информационным технологиям (Новосибирск, 2007), XIV Байкальской международной школе-семинаре "Методы оптимизации и их приложения" (Северобайкальск, 2008), IV Всероссийской конференции "Проблемы оптимизации и экономические приложения" (Омск, 2009), The 2nd International Conference on Internet (ICONI 2010) (Мактан, Филиппины, 2010).

Публикации. Основные результаты диссертации опубликованы в 8 работах, список которых приведен в конце автореферата. В число указанных работ входят две статьи, опубликованные в журналах, рекомендованных ВАК.

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

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения и списка литературы, включающего 70 наименований. Диссертация изложена на 100 страницах, содержит 20 рисунков и 10 таблиц.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе исследуется задача построения нижней оценки надежности решетки.

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

v £ V' существует хотя бы один путь из вершины и в вершину V, состоящий из исправных ребер. Проблема вычисления надежности сети в общем случае является NP-трудной.

Обозначим через N2 множество всех точек на плоскости с целыми координатами. Рассмотрим точки s = (0,0), t = (a,b) G N2 (а > b > 0). Решеткой G с источником s и стоком t называется неориентированный граф, вершинами которого являются точки {(i,j) G JV2|0 < i < а, 0 < < j < Ь], две вершины Vi = (гх, jr'i) и v2 = (12,72) соединены ребром, если |i2 — i\| + \j2 — ji\ — 1, т.е. расстояние между ними в метрике Ly равно единице. Предполагается, что надежность каждого ребра равна

ре [0,1].

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

Один из немногих классов сетей, для которых трудоемкость вычисления надежности является полиномиальной, - класс последовательно-параллельных сетей. Рассмотрим две операции над сетями. Пусть Si -сеть с источником s± и стоком t\, S2 ~ сеть с источником и стоком <2, причем Si и S2 не имеют общих элементов. Сеть Si Д S2 с источником Si и стоком t2, полученная отождествлением вершин t\ и s2, называется последовательным соединением сетей S\ и S2] сеть Si \J S2 с источником Si и стоком ti, полученная отождествлением вершин Si с S2 и ty с <2i называется параллельным соединением сетей Si и 62. Аналогично

п

определяется последовательное соединение большего числа сетей Д S1,.

2=1

Класс последовательно-параллельных сетей (сокращенно ППС) определяется индуктивно:

1) сеть, состоящая из одного ребра, соединяющего источник и сток, есть ППС,

2) если SiuS2- ППС, то Si Д S2 и Si V S2 - тоже ППС.

Рассмотрим точки и = (ai,bi), w = {a^bi) е N2 (ai < a2, by < b2).

Решеткой G с источником и и стоком w (будем обозначать G(u, w)) называется ориентированный граф, вершинами которого являются точки {(i,j) £ N2\a\ < i < a2,by < j < b2}- Две вершины Vy = {iy,jy) и V2 = («2, J2) («1 < i2, ji < З2) соединены дугой (vi,v2), если (i2 - iy) + +(j2 — ji) = 1, т.е. расстояние между ними в метрике Ly равно единице, и все дуги в решетке G(u, w) направлены от источника и к стоку w. Надежность каждой дуги равна р 6 [0,1].

Рассмотрим решетку G = G(s,t). Для получения нижней оценки на-

дежности решетки G исследуется задача поиска максимально надежной ППС S С G:

P(S) -> max . (1)

SCG.S-nnC

Надежность ППС S С G является нижней оценкой надежности решетки G, надежность максимально надежной ППС является лучшей оценкой в классе ППС. Очевидно, что надежность ППС SCG является нижней оценкой надежности решетки G.

Звеном и называется объединение двух непересекающихся путей в решетке G с общим источником г и с общим стоком j (г ф j). Длиной звена и называется расстояние от г до j (в метрике Li).

п

Цепочкой в решетке G называется последовательное соединение Д Si

i=l

звеньев Si, S2, ■ ■ ■, Sn (1 < п < b), при котором сток звена Si совпадает с источником звена 5j+i (1 < г < п — 1), источником звена Si является вершина s, и стоком звена Sn — вершина t. Очевидно, что цепочка является частным случаем ППС.

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

Как обычно, пусть [iyj - целая часть числа го, а [го] = — [—го] есть наименьшее целое число, не меньшее го.

Определение равномерной цепочки эквивалентно условию, что а — 6[а/Ь] ее звеньев имеют длину [а/6] + 1, а остальные b — а + Ь[а/Ь\ звеньев - длину \a/b\ + 1. Очевидно, равномерная цепочка определена с точностью до перестановки звеньев.

В работе показаны характерные свойства цепочек и ППС в решетке G и найдены решения частных случаев поставленной задачи (1), которые представлены в виде двух теорем. Обозначим L = а + Ь.

Теорема 1.1. Если в решетке G(0, ([f], L§J)) надежность дуги р < \/2 — \/2 г» 0.7654, то максимально надежной ППС, содержащей не более 2L дуг, является равномерная цепочка.

Теорема 1.2. Если в решетке G(0, L^J)) надежность дуги

р < \/2 — у/2, то максимально надежной ППС, содержащей не более L + K дуг (0 < К < L), является ППС, представляющая собой последовательное соединение равномерной цепочки в решетке G(0, ([у], [у])) и L — К дуг.

Хотя оптимальность равномерной цепочки в задаче (1) доказана при некоторых ограничениях, ее надежность можно использовать в качестве нижней оценки надежности решеток G и G, откуда имеет место

следующая оценка:

P(G)>PL(2-p^)"~a+bl%l (2)

Для проверки аккуратности (точности) предложенной оценки (2) осуществлено ее сравнение с известными эффективно вычислимыми оценками - модифицированной оценкой Краскала-Катоны и оценкой Брехта-Колбурна. Установлено, что предложенная в диссертации оценка превосходит их по точности. Для решеток малой размерности осуществлено сравнение предложенной оценки с точным значением надежности решетки, посчитанным с помощью метода Мура-Шеннона. В результате показано, что при больших значениях р предложенная оценка близка к точному значению надежности решетки.

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

Предполагается, что в плоской выпуклой области О площади S случайно равномерно распределено множество сенсоров М, \М\ = ш. Сенсор i е М расположен в точке Pi £ О. Областью мониторинга сенсора i является круг с центром в точке Pi и радиусом Ri е [0,Птах], где Rmax много меньше диаметра области О. Величина Щ является регулируемым параметром и называется радиусом мониторинга сенсора г. Каждому сенсору приписана начальная энергия Eq. Количество энергии, затрачиваемое сенсором i в течение времени t, равно tR?.

Говорим, что точка а Е О покрыта сенсором i, если расстояние между а и Pi не превосходит Ri\ точка а е О покрыта, если точка а покрыта хотя бы одним сенсором.

Покрытием называется подмножество {(г, Pi, Ri)\i 6 М',М' С Я M,Ri € (0,Rmax}} расположенных в области О сенсоров с назначенным для каждого из них радиусом мониторинга. Без ограничения общности можно считать, что в покрытие входят все сенсоры. Если сенсор не входит в рассматриваемое покрытие, его радиус мониторинга полагается равным 0. Таким образом, любое покрытие можно представить множеством С = {(г, Pj,Ri)\i 6 M,Ri G [0,Rmax\}- Отметим, что приведенное определение не является покрытием в строгом смысле, так

как нет требования покрытия всех точек области О. Но для определения случайных покрытий удобно именно такое определение.

Расписанием называется множество вида {(Ci,ti),(Ci,t\)}, где Ск — некоторое покрытие, tk > 0 — время функционирования покрытия Ск в этом расписании. Расписание является допустимым, если суммарное потребление энергии каждым сенсором не превосходит заданного значения Eq:

Здесь Rik — радиус мониторинга сенсора г в покрытии Ск- Величина I

Y^ tk называется длиной расписания. к=1

Так как места расположения сенсоров - случайные величины, то исследуются вероятностные показатели качества покрытия. Обозначим через D(i, х) (г 6 М) круг с центром в точке Pi и радиусом х.

Для заданной величины Q G (0,1) множество {(г, Pi, Ri)\i £ М,Щ е € [0, Rmax\\ называется сильным Q-покрытием, если вероятность того, что все точки области О покрыты, не меньше Q:

где Р(А) — вероятность события А.

Множество {(i,Pi,Ri)\i £ М,Hi 6 [0,Rmax]} называется Q-покры-гпием, если математическое ожидание доли области, состоящей из всех покрытых точек области О, не меньше Q:

где ц(Х) — площадь области X, а Е(а) — математическое ожидание случайной величины а.

Для обозначения множества всех сильных Q-покрытий и Q-покрытий будем использовать Cq и Cq соответственно. В работе рассматриваются следующие две задачи.

Задача I. Найти допустимое расписание максимальной длины, состоящее из сильных Q-покрытий:

J2tkRlk<Eo, 1 <г<т.

(3)

(4)

Задача II. Найти допустимое расписание максимальной длины, состоящее из Q-покрытий:

I

Основная часть второй главы посвящена построению допустимых решений задач I и II. Длина допустимого расписания, состоящего из сильных Q-покрытий (Q-покрытий), является нижней оценкой максимального времени функционирования сенсорной сети в том случае, когда требуется выполнение условия (3) (условия (4)).

В случае детерминированного распределения сенсоров и требования покрытия каждой точки области часто используют так называемые регулярные покрытия, при построении которых в область О помещается однородная решетка, образованная правильными многоугольниками (плитками), и все плитки покрываются одинаково. Для построения приближенных решений задач I и II используются регулярные покрытия, которые обозначены А1, A3 и ВЗ. Данные покрытия эффективны, каждое в своем классе, по критерию минимума плотности покрытия. Покрытие А1 предложено Кешнерем Р., покрытия A3 и ВЗ - Астрако-вым С.Н., Ерзиным А.И. и Залюбовским В.В.

В покрытии А1 сенсоры с некоторым радиусом мониторинга R размещаются в узлах однородной треугольной решетки со стороной плитки i?\/3 (рис. 1а). В покрытии A3 сенсоры с радиусом мониторинга R находятся в узлах однородной треугольной решетки со стороной плитки 6RV3/V31, а в центре каждой плитки размещается сенсор с радиусом мониторинга Г\ = R/VЗГ (рис. 16). И, наконец, в покрытии ВЗ сенсоры с радиусом мониторинга R находятся в узлах квадратной решетки со стороной плитки 4Л/\/5, а в центре каждой плитки размещается сенсор с радиусом мониторинга Г2 = Rj\fb (рис. 1в).

б)

Рис. 1. Примеры регулярных покрытий

в)

Так как сенсоры распределены в области случайно, описанные покрытия А1, A3 и ВЗ модифицированы следующим образом. В качестве покрытия выбираются сенсоры, ближайшие к каждому из мест расположения сенсоров в регулярном покрытии, а радиусы мониторинга выбранных сенсоров увеличиваются на величину е. Такие покрытия обозначены А1£, А3£ и В3е соответственно.

На основе покрытий А1е, АЗе и ВЗЕ построены допустимые расписания М1£, М2£ и М3е, в которых используются сдвиги решетки на величину 25, где 5 = yJS/^кт) - радиус круга, содержащего в среднем один сенсор. Для обозначения длины расписания Mis введено обозначение

При решении задачи I, оценивая снизу вероятность того, что все точки области О покрыты, найдены такие £j (г = 1,2,3), что при е > £i покрытие А1е является сильным Q-покрытием, при е > са покрытие А3£ является сильным Q-покрытием, при г > £3 покрытие ВЗе является сильным Q-покрытием. Используя построенные допустимые расписания Ml', М2е и М3е, доказана следующая теорема.

Теорема 2.1. Максимальное время функционирования совокупности сильных Q-покрытий оценивается снизу величиной

max{Ljif iEi, Lm2s2 , Ьма>з },

где

Lmi'

LM2c2 =

EQ (R+d)2

3E0

RV3 25

(Д + е2)2+2(Л/ч/зТ + е2)2

Lm3'3 =

2E0

(R + e3)2 + (R/y/5 + £3)*

2R

Jy/5.

ЗД

_5y/31.

2 (Д - 5V5) SV15

+ 1

В задаче II величина, на которую изменяются радиусы мониторинга сенсоров, обозначена через а. Предполагается, что в покрытии АЗа (покрытии ВЗа) радиусы мониторинга ближайших к центрам плиток соответствующей решетки сенсоров равны Г1+тах{а, —ri} (r24-max{a, — г2}).

С помощью построенной нижней оценки математического ожидания доли области, состоящей из всех покрытых точек области О, найдены такие Qj (г = 1,2,3), что при а > а.\ покрытие А1а является Q-покрытием, при а > а2 покрытие A3™ является Q-покрытием, при

а > «з покрытие ВЗа является Q-покрытием. Используя допустимые расписания МIе, М2е и М3£, доказана следующая теорема.

Теорема 2.2. Максимальное время функционирования совокупности Q-покрытий оценивается снизу величиной

maxfLMi»!, Lm2<*2 , 1<мз=з },

где

Ер (R + a i)2

Lm2"

Lm3°3 =

3En

(Я+а2)2+2(Я/^ЗТ+а2)2

I 2

Ду/З 2J

зя I2

<5\/3lJ

До I ЗЛч/3 I ^ < Л

Lwj при а2 - ~ ш

пРиа2>-^г,

2Д0

_ 2Д

До I _2Я. I I 4(Д-Ду/5) (Я+а3Р [^J [ Sy/15

1 +

Я

L ITU ^ 1J при а3

2R/V5-26J т XJ - "75-

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

С использованием теоретических результатов второй главы для оценки времени функционирования сенсорной сети был разработан комплекс программ на языке С++. В главе приведено описание трех моделей функционирования V1Q, V2a и V3a, в которых используются соответственно случайные покрытия А1а, АЗа и ВЗа. При этом соответствующая решетка помещается в область О случайным образом, время функционирования покрытия является задаваемым параметром, покрытия строятся до тех пор, пока не получено первое покрытие с долей области, состоящей из всех покрытых точек, меньшей Q.

С помощью разработанного комплекса программ для проверки точности полученных во второй главе оценок и практической применимости предложенных покрытий А1а, АЗа и ВЗа проведены численные эксперименты. Так, было осуществлено сравнение моделей Via для следующих значений параметра а: а = О, а = а = S (г = 1,2,3). Установлено, что использование моделей Viai (i = 1,2,3) позволяет получить максимальное среди рассматриваемых моделей время функционирования сенсорной сети. Особенно существенным выигрыш оказывается в

случае, когда значение Q близко к единице. Отметим, что экспериментальные данные не дают возможности рекомендовать одну из трех моделей Viai (г = 1,2,3) как безусловно лучшую.

Для каждой задачи проводилась серия испытаний, состоящая из 100 случайно сгенерированных задач. Осуществлено сравнение нижней оценки LMiai максимального времени функционирования сенсорной сети с посчитанным максимальным по всем испытаниям временем Li функционирования сенсорной сети, использующей модель функционирования Viai (г = 1,2,3). В результате сравнения показала близость величин и Li (i = 1,2,3), что доказывает эффективность оценок

LM 1=1, LM2°4, 1>мзаз-

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ, ВЫНОСИМЫЕ НА ЗАЩИТУ

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

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

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

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

ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

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

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

Материалы и тезисы докладов на международных и всероссийских конференциях:

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

[4] Алдын-оол Т.А. Анализ надежности решетчатых графов // Тези-

сы докладов VIII Всероссийской конференции молодых ученых по математическому моделированию и информационным технологиям (Новосибирск, 2007). Новосибирск: Институт вычислительных технологий СО РАН, 2007. С. 82.

[5] Алдын-оол Т.А., Ерзин А.И. О надежности последовательно-парал-

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

[6] Алдын-оол Т.А., Ерзин А.И. Максимизация времени жизни сенсор-

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

[7] Алдын-оол Т.А., Ерзин А.И., Залюбовский В.В. Покрытие плоской

области случайно распределенными сенсорами // Материалы Российской конференции "Дискретная оптимизация и исследование операций" (Алтай, 2010). Новосибирск: Изд-во Ин-та математики, 2010. С. 167.

[8] V. Zalyubovskiy, Т. Aldyn-ool, A. Erzin, Н. Byun, Н. Choo. Energy-

efficient coverage-guaranteed node scheduling models in sensor networks with random deployed sensors // Proceedings of the 2nd International Conference on Internet (ICONI 2010) (Mactan, Philippines, 2010). Seoul, Korea: Korean Society for Internet Information, 2010. P. 757-760.

Подписано в печать 12.05.2011. Формат 60><84 1/16. Заказ № 933. Объем 1,0 п. л. Тираж 120 экз.

Отпечатано в ЗАО РИЦ «Прайс-курьер» ул. Кутателадзе, 4г, т. 330-7202

Введение

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

Заключение

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

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.