URSS.ru - Издательская группа URSS. Научная и учебная литература
Об издательстве Интернет-магазин Контакты Оптовикам и библиотекам Вакансии Пишите нам
КНИГИ НА РУССКОМ ЯЗЫКЕ


 
Вернуться в: Каталог  
Обложка Малашенко Ю.Е., Новикова Н.М. Модели неопределенности в многопользовательских сетях
Id: 631
 
269 руб.

Модели неопределенности в многопользовательских сетях.

URSS. 1999. 160 с. Мягкая обложка. ISBN 5-901006-81-X.

 Аннотация

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


 Введение

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

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

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

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

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

С проблемой принятия решений в условиях неопределенности сталкиваются исследователи большинства сложных систем. Для рассматриваемых систем характерно наличие не только объективной, но и субъективной неопределенности, когда некоторые параметры системы известны отдельным пользователям, но не известны ЛПР (лицу, принимающему решения) или другим пользователям. За счет длительных сроков создания территориально-распределенной системы условия ее функционирования могут отличаться от расчетных при проектировании, поэтому естественна их корректировка в процессе построения сети и при распределении потоков в готовых сетях, т.е. многоэтапность процедуры принятия решений. Ответственность за принятые решения обязывает аккуратно разграничить неопределенные и случайные неконтролируемые факторы: случайность должна быть теоретически обоснована (и подтверждена статистическими методами), имеющаяся информация о функциях распределения фигурирующих случайных величин должна быть указана явно. Еще раз отметим взаимную зависимость элементов сети, что приводит к немарковости случайных процессов в сетях.

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

Принципиальная схема функционирования многопользовательской потоковой сетевой системы описывается известной математической моделью, которая называется многопродуктовая потоковая сеть (МП-сеть) и задается с помощью двух графов на одном и том же множестве вершин -- узлов сети. 1-й граф -- физический -- определяет физическую структуру сети, его ребра соответствуют физическим отрезкам линий связи: дорогам, линиям электропередач, телефонному кабелю,... -- проложенным от одного узла к другому. Узлы сети соответствуют либо пунктам входа/выхода пользователей -- их подключения к сетевой системе, либо пунктам переключения с одной линии связи на другую: перекресткам дорог, узлам коммутации телефонных проводов и т.п. В последнем случае вершины физического графа сети называются транзитными. Нетранзитные узлы сети являются вершинами 2-го -- логического -- графа сети, определяющего структуру связей между пользователями -- абонентами сети, т.е. структуру требований на передачу потоков в сети. Ребра логического графа (графа тяготений) соединяют пары входов сети, между которыми нужна связь, т.н. абонентские или тяготеющие пары . Объединение указанных двух графов в одну систему -- МП-сеть -- обусловлено тем, что связь между узлами, соединенными ребрами логического графа, может осуществляться только по ребрам физического графа. Ребра графов сети могут быть как ориентированными, так и неориентированными в зависимости от конкретной специфики задачи.

Название многопродуктовая ("многопродуктовик") для МП-сети объясняется невзаимозаменяемостью потоков различных тяготеющих пар, например, их телефонных разговоров. Считается, что эти потоки соответствуют как бы разным видам продуктов: они не смешиваются, проходя по ребрам физического графа сети, и не могут поделиться в другой пропорции. В противном случае, когда речь идет, допустим, о системе водоснабжения, говорят об однопродуктовой потоковой сети с несколькими источниками и стоками. Многопользовательская модель однопродуктовика существенно \`уже МП-сети, но гораздо проще для математических расчетов. Так что очень удобно, если модель реальной сетевой системы удается представить в виде однопродуктовой потоковой сети, пусть, с более сложной структурой, чем МП-сеть. Один пример подобного представления дан в  для конкретной практической задачи исследования сетевой подсистемы энергетического комплекса. Тем не менее, для большого числа сетей связи, таких как телефонные сети или сети ЭВМ, однопродуктовая сетевая модель оказывается неадекватной. Поэтому далее будет рассматриваться общая модель -- МП-сеть, являющаяся достаточно универсальной .

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

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

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

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

Согласно базовой модели, задача анализа МП-сети зависит от двух векторов d и c переменных. Поэтому в ней возможна неопределенность двух типов. 1-я связана с вектором требований и может трактоваться как субъективная: вектор требований пользователей, хотя и объективно существующий, не известен или неточно известен лицу, принимающему решения -- выбирающему пути соединения абонентских пар (см. гл.1).

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

В случае полностью неизвестных требований возникает задача многокритериальной максимизации вектора z результирующих потоков для всех абонентских пар МП-сети, называемого мультипотоком. Ее решением является множество оптимальных по Парето и Эджворту мультипотоков, т.е. векторов потоков, не увеличиваемых ни по одной компоненте без уменьшения какой-либо из других . Формальному описанию, свойствам и методам решения этой задачи посвящена гл.3. Другой крайний случай -- точно известных требований -- приводит к выбору конкретной парето-оптимальной (ПО) точки, являющейся решением соответствующей задачи согласования интересов пользователей, он рассмотрен в гл.2. Промежуточные варианты: известных границ для вектора d и известной функции распределения (ф.р.) на заданном множестве возможных значений, -- исследованы в гл.1 и гл.4.

1 2-й тип неопределенности связан с вектором c пропускной способности ребер физического графа МП-сети и трактуется как объективная неопределенность, не известная в момент исследования сети ни исследователю, ни пользователям. Считаем, что причиной ее возникновения является уменьшение пропускной способности или выход из строя отдельных ребер физического графа МП-сети в результате либо случайных повреждений сети, либо целенаправленных ее разрушений. В 1-м случае (см. гл.5) задается ф.р. вектора c на множестве значений от 0 до вектора, соответствующего изначально имевшейся пропускной способности. Во 2-м случае ставится параметрическая задача поиска наихудшего разрушающего воздействия ограниченной мощности -- равной текущему значению параметра. Указанная задача, названная задачей анализа уязвимости МП-сети, изучается в главах 6 и 7. При этом рассмотрены постановки как с известным вектором d требований пользователей (гл.7), так и с субъективной неопределенностью в информированности о векторе требований. Для случая неизвестного d в гл.6 исследована многокритериальная задача поиска минимакса вектора z потоков всех продуктов. Предложены и изучены игровые формулировки задачи анализа уязвимости.

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

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

Проведенные исследования и издание книги были поддержаны грантами INTAS по проекту INTAS--97--1050 и РФФИ по проектам 95--01--00232, 96--01--00786, 98--01--00233, 98--01--14090, 99--01--01192.


 Оглавление

Введение
Глава 1. Задача анализа многопродуктовой потоковой сети в случае неточно известного вектора требований
 § 1.Описание модели "МП-сеть"
 § 2.Обобщенные постановки задачи анализа допустимости для неточно известных требований
 § 3.Обеспеченность потоковых требований как мера допустимости МП-сети. Оценки для обобщенных постановок
Глава 2. Задача анализа предельных возможностей сети по обеспечению требований пользователей
 § 1.Суперконкурентное (нормативное) распределение потоков
 § 2.Об оценках уровней максиминной обеспеченности в случае неточно известных требований
 § 3.Устойчивость суперконкурентного решения
 § 4.Методы поиска суперконкурентного решения
Глава 3. Задача анализа многопродуктовой потоковой сети в случае неизвестного вектора требований
 § 1.Многокритериальная постановка задачи анализа
 § 2.Методы аппроксимации множества эффективных мультипотоков с помощью обратной логической свертки
 § 3.Устойчивость представления множества решений крайними точками
Глава 4. Задача анализа многопродуктовой потоковой сети для случайного вектора требований
 § 1.Вероятностные формулировки задачи анализа МП-сети
 § 2.Стохастические формулировки задачи анализа МП-сети
Глава 5. Задача анализа многопродуктовой потоковой сети со случайной пропускной способностью
 § 1.Вероятностные формулировки задачи анализа МП-сети для случайной пропускной способности ребер
 § 2.Стохастические формулировки задачи анализа МП-сети для случайной пропускной способности ребер
Глава 6. Задача анализа многопродуктовой сети при неслучайных потерях пропускной способности
 § 1.Специфика неслучайных потерь пропускной способности
 § 2.Гарантированный уровень обеспеченности требований как скалярная характеристика уязвимости МП-сети
 § 3.Задача анализа уязвимости МП-сети в случае неизвестного вектора требований
 § 4.Методы поиска линейного многокритериального минимакса
Глава 7. Задача нормативного анализа уязвимости многопродуктовой потоковой сети
 § 1.Постановка задачи
 § 2.Некоторые примеры решения задачи
 § 3.Теоретико-графовые характеристики уязвимости и живучести многопользовательских сетевых систем
Заключение
Список литературы
 
© URSS 2016.

Информация о Продавце