Модели дискретной оптимизации для территориальной сети интернет л. Г. Еремеев, А. А. Колоколов icon

Модели дискретной оптимизации для территориальной сети интернет л. Г. Еремеев, А. А. Колоколов



НазваниеМодели дискретной оптимизации для территориальной сети интернет л. Г. Еремеев, А. А. Колоколов
Дата17.10.2016
Размер
ТипУроки, сочинения

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

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

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

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


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

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

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

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

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

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

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

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

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

Для построения модели используются следующие исходные данные:

  • стоимость варианта набора оборудования в вершине графа из первого подмножества;

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

  • множество клиентов, которые могут быть обслужены данным узлом посредством определенного типа связи;

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

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

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

Целевая функция модели – это суммарные затраты на создание и развитие узлов сети, а также на их соединения с клиентами. Она минимизируется при ограничениях, которые сформулированы в виде линейных неравенств и уравнений и отражают следующие условия:

  • каждый клиент должен быть прикреплен к одному или нескольким узлам сети с использованием определенных видов связи;

  • в каждом существующем узле должен быть выбран один вариант комплекта оборудования (в модели не предусматривается ликвидация такого узла). В каждом новом узле (если он будет создаваться) предусматривается также один вариант комплектования оборудованием;

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

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

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

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

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

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

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




Похожие:

Модели дискретной оптимизации для территориальной сети интернет л. Г. Еремеев, А. А. Колоколов iconКонспект урока «Глобальная сеть Интернет. Поиск информации в Интернете» для учащихся 11 класса (учитель Хвостова Е. А)
Цель урока: изучить структуру глобальной сети Интернет и освоить основные методы поиска в сети
Модели дискретной оптимизации для территориальной сети интернет л. Г. Еремеев, А. А. Колоколов iconРешение задач глобальной оптимизации большой размерности на многопроцессорных комплексах и грид-системах1
Грид-системах. В данной работе рассматриваются принципы организации решения задач оптимизации на таких системах и программный комплекс,...
Модели дискретной оптимизации для территориальной сети интернет л. Г. Еремеев, А. А. Колоколов iconЛекция №3 Варианты доступа в Интернет
Существует целый ряд технологий, позволяющих использовать имеющуюся инфраструктуру (телефонные линии, сети кабельного телевидения...
Модели дискретной оптимизации для территориальной сети интернет л. Г. Еремеев, А. А. Колоколов iconИспользование интернет ресурсов на уроках физики
Проанализированы некоторые ресурсы сети Интернет, необходимые учителю при подготовке и проведении уроков и внеклассной работы по...
Модели дискретной оптимизации для территориальной сети интернет л. Г. Еремеев, А. А. Колоколов iconКонспект лекций Представление знаний в информационных системах
Задача курса – изучение моделей знаний: модели на основе нейронных сетей, фреймы, семантические сети, продукционные модели, логические...
Модели дискретной оптимизации для территориальной сети интернет л. Г. Еремеев, А. А. Колоколов iconБизнес план интернет кафе
Советы, как открыть собственное интернет-кафе, дает Владислав Беляев, генеральный директор крупнейшей сети интернет-центров Cafemax,...
Модели дискретной оптимизации для территориальной сети интернет л. Г. Еремеев, А. А. Колоколов iconОбразовательные ресурсы сети Интернет Органы управления образованием, образовательные учреждения Ресурсы сети Интернет по предметам образовательной программы Биология и экология
Палеоэнтомология в России Проблемы эволюции Редкие и исчезающие животные России Санкт-Петербургская общественная организация содействия...
Модели дискретной оптимизации для территориальной сети интернет л. Г. Еремеев, А. А. Колоколов iconБ данного параграфа, здесь лишь отметим, что в качестве математической модели для оптимизации авиаперевозок задача линейного программирования неприемлема. Б f
Трактовку этого решения оставим до конца следующего пункта б данного параграфа, здесь лишь отметим, что в качестве математической...
Модели дискретной оптимизации для территориальной сети интернет л. Г. Еремеев, А. А. Колоколов iconРаспоряжение
В целях совершенствования системы подготовки специалистов для Вооруженных Сил Россий­ской Федерации и оптимизации сети военных образовательных...
Модели дискретной оптимизации для территориальной сети интернет л. Г. Еремеев, А. А. Колоколов iconШкольные технологии, №2, 2001 г. Открытые ресурсы сети Интернет для учителя
Направления применения информационных ресурсов Интернета в педагогических технологиях
Разместите ссылку на наш сайт:
Уроки, сочинения


База данных защищена авторским правом ©izlov.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
связаться с нами