Geum.ru

Модели дискретной оптимизации для территориальной сети интернет

Вид материалаДокументы
Подобный материал:

МОДЕЛИ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ ДЛЯ ТЕРРИТОРИАЛЬНОЙ СЕТИ ИНТЕРНЕТ

Л.Г.Еремеев, А.А.Колоколов

Омский государственный университет, Омск

Тел.: (3812) 22-26-16, факс: (3812) 22-26-17, e-mail: eremeev@omskreg.ru


При проектировании территориальной сети Интернет и при ее дальнейшем развитии приходится решать, сколько и каких узлов сети, каждый из которых обслуживает некоторое множество клиентов, следует создавать и/или модифицировать /1,2/. Указанная задача является достаточно сложной, поэтому для ее решения целесообразно использовать математические модели и методы оптимизации.

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

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

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

Создание каждого узла должно быть рентабельно. Рентабельность зависит, прежде всего, от того, какое количество клиентов будет обслуживать данный узел.

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

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

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

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

Для построения модели используются следующие исходные данные:
  • стоимость варианта набора оборудования в вершине графа из первого подмножества;
  • стоимость каждого типа связи, соединяющего пару вершин, из которых одна из первого подмножества, а вторая из второго (соединение клиента с обслуживающим его узлом);
  • множество клиентов, которые могут быть обслужены данным узлом посредством определенного типа связи;
  • множество узлов, которые могут обслужить конкретного клиента с помощью определенного типа связи;
  • множество вариантов комплектов оборудования в каждом узле, которые включают возможность обеспечения заданного типа связи.

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

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

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

С математической моделью и ее описанием можно ознакомиться на сайте Омского госуниверситета по адресу: omskreg.ru в разделе "персональные страницы" по адресу: skreg.ru/~eremeev.
Литература

1. Еремеев Л.Г.,Колоколов А.А. Построение модели дискретной оптимизации для проектирования корпоративной территориальной сети Интернет. //Материалы международной научно-практической конференции "Новые информационные технологии в университетском образовании". Новосибирск, 1999.-С. 162-164.

2. Еремеев Л.Г. Создание телекоммуникационной инфраструктуры для информатизации сферы образования, науки, и культуры Омского региона. Информационные технологии в гуманитарных исследованиях. Вып. 1, Новосибирск, 1998.-С. 12-16.

3. Колоколов А.А.,Леванова Т.В. Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения. // Вестник Омского университета. Вып. 2,1996.-С. 21-23.

4. Кристофидес Н. Теория графов. Алгоритмический подход. М., "Мир",1978.