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

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

Омский государственный университет
e-mail: eremeev@omskreg.ru

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

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

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

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

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

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

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

Таким образом, множество вершин графа разбито на два непересекающихся подмножества. Первое подмножество (обозначим его через A = {a_i},  i = 1,ј,I), содержит вершины, соответствующие пунктам, где могут быть созданы узлы сети. Второе подмножество (обозначим его через B = {b_j},  j = 1,ј,J), содержит вершины, соответствующие клиентам, которые обслуживаются через узлы. Подмножество существующих узлов обозначим через . .

В мультиграфе возможности обслуживания клиента разными видами (типами) связи отражаются несколькими ребрами. Для любого клиента j задано множество W_j выбираемых им типов связи. Для каждого узла i сети будем рассматривать M_i вариантов наборов его оборудования. В отличие от постановки задачи, описанной в [1], здесь допускается обслуживание клиента несколькими узлами.

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

Для построения модели введем обозначения:
- стоимость m-го набора оборудования в вершине a_i;
- стоимость k-го типа связи, соединяющего пару вершин a_i, b_j;
- множество клиентов, которые могут быть обслужены i-м узлом посредством k-го типа связи;
- множество всех узлов, которые могут обслужить j-го клиента с помощью k-го типа связи;
- множество вариантов комплектов оборудования в i-м узле, которые включают возможность обеспечения k-го типа связи;
- минимально допустимое количество клиентов, при которых в i-м узле рентабельно устанавливать оборудование, обеспечивающее k-й тип связи.

Введем переменные модели:

Требуется минимизировать функцию суммарных затрат на создание сети для обслуживания клиентов:

(1)

при условиях булевости переменных и следующих ограничениях:

(2)

(3)

(4)

(5)

Здесь l - достаточно большое число, например, можно взять . Условие (2) означает, что каждый клиент должен быть прикреплен к одному или нескольким узлам сети с учетом его заявки. Равенство (3) отражает требование выбора одного варианта комплектования оборудования в существующем узле, а неравенство (4) - условие выбора не более одного варианта в проектируемом узле. Ограничение (5) обеспечивает учет условия, состоящего в том, что узел сети включает оборудование для k-го типа связи лишь в том случае, когда количество клиентов достигнет некоторой критической величины .

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

Список литературы