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