автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Построение сетей доставки контента для управления горно-химическими предприятиями на основе принципа декомпозиции

Башир Али Касем Аль-Таяр

ПОСТРОЕНИЕ СЕТЕЙ ДОСТАВКИ КОНТЕНТА ДЛЯ УПРАВЛЕНИЯ ГОРНО-ХИМИЧЕСКИМИ ПРЕДПРИЯТИЯМИ НА ОСНОВЕ ПРИНЦИПА ДЕКОМПОЗИЦИИ

Специальность: 05.13.01 - Системный анализ, управление и обработка информации (в промышлености)

19 ФЕВ 2015

Автореферат диссертации на соискание ученой степени кандидата технических наук

005559382

005559382

Башир Али Касем Аль-Таяр

ПОСТРОЕНИЕ СЕТЕЙ ДОСТАВКИ КОНТЕНТА ДЛЯ УПРАВЛЕНИЯ ГОРНО-ХИМИЧЕСКИМИ ПРЕДПРИЯТИЯМИ НА ОСНОВЕ ПРИНЦИПА ДЕКОМПОЗИЦИИ

Специальность: 05.13.01 - Системный анализ, управление и обработка информации (в промышлености)

Автореферат диссертации на соискание ученой степени кандидата технических наук

Работа выполнена в ФГБОУ ВПО «Тверской государственный технический университет» (ТвГТУ) на кафедре «Информационные системы»

Научный руководитель:

Матвеев Юрий Николаевич, доктор технических наук, профессор, декан факультета Международного академического сотрудничества ФГБОУ ВПО «ТвГТУ»

Официальные оппоненты:

Допира Роман Викторович, доктор технических наук, профессор, заведующий отделом № 40 - Проектирование систем общего назначения, Научно-производственное объединение "Русские базовые информационные технологии" (Тверь),

Суконщиков Алексей Александрович, кандидат технических наук, доцент, заведующий кафедрой Автоматики и вычислительной техники ФГБОУ ВПО «Вологодский государственный университет» (ВоГУ).

Ведущая организация:

ФГБОУ ВПО «Тамбовский государственный технический университет»

Защита диссертации состоится «20» марта 2015 года в 15.00 часов на заседании диссертационного совета Д 212.262.04 при ФГБОУ ВПО «Тверской государственный технический университет» в аудитории № 212 по адресу: 170026, г. Тверь, наб. А. Никитина, 22.

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО «Тверской государственный технический университет» и на сайте www.tstu.tYer.ru.

Автореферат разослан «/%) _2015 г.

Ученый секретарь

диссертационного совета Д 212.262.04, д.ф.-м.н, проф.

С.М. Дзюба

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность исследования.

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

Однако из-за больших объемов обрабатываемой информации такие системы сталкиваются с проблемой больших нагрузок на серверы и сетевую инфраструктуру. Ослабить негативное влияние этих проблем можно с помощью технологий, реализованных в так называемых сетях доставки контента - Content Delivery Network (CDN), которые быстрыми темпами развиваются и внедряются во многих регионах мира. Основными направлениями исследований в системах CDN являются: вопросы анализа, проектирования, балансирования нагрузки, управления и оптимизации процессов выбора, обновления и доставки контента, а также вопросы информационной безопасности. Хотя некоторые подобные задачи уже исследовались, и существует большое количество работ в смежных областях, остается множество незакрытых вопросов.

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

Целью исследования является повышение эффективности использования ресурсов CDN путем оптимального размещения и балансирования нагрузки между узлами сети.

Задачи исследования. Для достижения поставленной цели необходимо решить следующие задачи:

1. Разработать научную концепцию применения CDN в управлении горнохимическими предприятиями фосфатной промышленности региона БВиСА.

2. Разработать методику построения CDN на основе принципа декомпозиции общей задачи проектирования.

3. Разработать алгоритм размещения узлов CDN с учетом промышленных значимостей зон.

4. Разработать метод балансирования нагрузки и оптимизации структуры CDN узлов.

Объектом исследования являются сети доставки контента промышленных предприятий.

Предметом исследования является методика построения сетей доставки контента; алгоритм размещения и метод балансировки нагрузки в сети.

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

Теоретическую основу исследования составили работы российских и зарубежных ученых Б.Я. Советова, С.А. Яковлева, В.А. Терехова, В.М. Вишневского, Г.Ф. Янбыха, Е.А. Берзина, Т.И. Алиева, P.M. Алгулиева, И.М. Алиева, М.Г. Шарифова, A.A. Пешкова, Дж. Мартина, Д. Бертсекаса, Галлагера, Л. Клейнрока, George Pallis, Athena Vakali, Al-Mukaddim Pathan, James Broberg, Zahir Tari.

Основные научные положения, выносимые на защиту:

1. Модифицированная методика построения сетей доставки контента.

2. Алгоритм размещения узлов CDN.

3. Метод балансировки нагрузки между узлами сети. Научная новизна работы:

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

2. Разработана модифицированная методика построения CDN, отличающаяся использованием методов построения сетей интегрального обслуживания (СИО), предложенных профессорами Яковлевьм С.А. и Советовым Б.Я.

3. Разработан алгоритм размещения узлов CDN, отличающийся применением показателей промышленной значимости зон возможного размещения и

ожидаемого эффекта от размещения узлов в этих зонах и основанный на достижении максимумов этих коэффициентов.

4. Разработан метод балансировки нагрузки между СБИ узлами, отличающийся оптимальным выбором долей нагрузки и их перенаправлением из предельно загруженных узлов на менее загруженные по критерию средней задержки. А также расширение этого метода для оптимизации структуры СБИ на основе модифицированного критерия средней задержки с учетом затрат на обслуживание нагрузок в узлах-адресатах.

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

Внедрение результатов работы. Разработанное программное обеспечение внедрено на ЗАО "НТК Интегративные системы" (г. Тверь, 2014 год). Разработанная методика, методы и программные средства используются в учебном процессе кафедры «Информационные системы» ТвГТУ при проведении лабораторных и курсовых работ по дисциплине «Анализ и синтез информационных систем» в рамках магистерской подготовки студентов специальности 09.04.02 «Информационные системы и технологии».

Апробация работы. Основные положения и результаты исследования были представлены на следующих конференциях: Международная научно-практическая конференция «Региональная информатика» Проблемы подготовки кадров в сфере инфокоммуникационных технологий (г. СПБ, май 2011 г.); Международная заочная научно-практическая конференция «Современные тенденции в науке: Новый взгляд» (г. Тамбов, ноябрь 2011 г.); ХЬ международная научно-практическая конференция с международным участием «Неделя науки СПбГПУ» (г. СПБ, декабрь 2011 г.); Научно-практическая конференция «Системы гарантии качества образования: Разработка и внедрение» (г. Тверь, 2012 г.).

Публикации. Основные теоретические и практические результаты диссертации опубликованы в 9 научных работах, среди которых 3 публикации в ведущих рецензируемых изданиях, рекомендованных в действующем перечне ВАК России, и 6 работ в материалах научно-технических конференций.

Структура п объем диссертации. Диссертация состоит из введения, четырёх глав, выводов и заключения, изложенных на 142 страницах, содержит список литературы из 97 наименований и приложение.

СОДЕРЖАНИЕ РАБОТЫ

Во введении определены предмет, объект и область исследования, обоснована актуальность темы диссертации, приведены общая характеристика работы и её краткое содержание.

В первой главе проведен анализ состояния горно-химической промышленности в регионе Ближнего Востока и Северной Африки, обоснованы потребности в применении инфокоммуникационных систем и вычислительных

сетей в горно-химической промышленности региона, осуществлен анализ технологий доставки контента и развития СЭЫ. Разработана научная концепция применения СБЫ в управлении горно-химическими предприятиями. Обоснована актуальность темы исследования, посвященного разработке методики построения СОИ, алгоритма размещения узлов и метода балансировки нагрузки при доставке конечным пользователям контента, принадлежавшего промышленным предприятиям региона.

Во второй главе предложена модифицированная методика построения на базе разработанной профессорами С.А. Яковлевым и Б.А. Советовым методики построения СИО. Процесс проектирования СБЫ, как любой большой системы, включает в себя два основных этапа: системное проектирование и инженерное проектирование. Задачи системного проектирования СВЫ решаются при следующих исходных данных: 1) Вид организации доставки контента: централизованная; децентрализованная; или гибридная. 2) Топологическая структура СБ>}, т.е. размещение и количество узловых серверов (УС), а также количество и производительности каналов связи (КС). 3) Отношения между СТ№ компонентами. 4) Модели источников информации в СОК 5) Типы доставляемого контента (статический, динамический и потоковый) и предоставляемых услуг. 6) Ограничения по качеству доставки информации в СБК. 7) Ограничения на параметры С1Ж-компонентов (КС, УС,

различное оборудование), которые устанавливаются в зависимости от характеристик аппаратно-программных средств, доступных для организации этих компонентов. 8) Функция стоимости СБЫ-компонентов, зависящие от их характеристик. На рис.1 представлена методика построения С1Ж на основе существующей методики построения СИО с использованием принципа декомпозиции. Пунктирными блоками выделены добавленные в существующую методику этапы построения. Построение СБМ с использованием принципа декомпозиции является логическим упрощением задачи, в результате которого появляется возможность тестирования, разработки и модификации

. Определение исходных данных для построения 1 __CDN

Разработка СРЫ топологии

; з ; Выбор методов и разработка алгоритмов " ............._выбора сервера обслуживания

_4

Выбор методов и разработка алгоритмов маршрутизации запросов__

I Выбор и разработка политики аутсорсинга контента

Выбор протоколов взаимодействия компонентов и _управления обменом информацией_

Выбор параметров, разработка структуры и алгоритмов функционирования УС

Г--Г-'

*! 9 !

Выбор и разработка методов кэтиртвата*я и * обновления кэша

Выбор и разработка методов балансирования нагрузки на УС

110: Выбор и разработка методов и способов оценка * - производительности

Переход к этапу инженерного проектирования

Рис. 1. Модифицированная методика построения СБЫ

алгоритмов решения отдельных подзадач. Вследствие этого, решение любой подзадачи может быть независимо пересмотрено, если потребуется. Предложенная методика позволяет итеративно производить решение каждой из подзадач на этапах. В диссертации решаются задачи, соответствующие в основном 2,3,7 и 9-ому этапам методики.

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

Задача выбора мест размещения узлов решена следующим образом: имеется п СБМ-узлов. Примем, что все узлы однотипны (равно эффективны) в том смысле, что эффект от их размещения зависит только от зоны, в которой они будут размещены. Определены Б зон возможного размещения узлов сети. Зоны соответствуют странам, городам или другому определению региона, из которого поступают пользовательские запросы на обслуживание. Каждая зона 1,5 имеет выражаемую через Лг вес (относительную важность или развитость промышленности в этой зоне). Обозначим через сог ожидаемый эффект от функционирования узла в г-ой зоне, сог е [0 : 1]. Таким образом, если - необслуженная нагрузка в г-ой зоне, а сог- эффект, выражаемый через долю нагрузки (от общей нагрузки в зоне), которую узел / может обслужить при его размещении в г-ой зоне, то ег = 1 - сог. Для обслуживания пользователей из 5 зон необходимо оптимально разместить хл узлов, суммарный эффект при размещении которых будет наибольшим. Т.е. требуется определить оптимальный вектор X = {х2}5, характеризующий собой вариант размещения узлов в 5 зонах и максимизирующий целевую функцию, определяющую суммарный эффект от размещения. Очевидно, что до начала размещения, т.е. когда хг = 0 уровень обслуживания = 0 и, следовательно, е° = 1. Уровень обслуживания в каждой 2-ой зоне увеличивается по мере увеличения числа размещенных узлов „тг и его можно определить следующим образом: со*' = хг-®7. Следовательно, необслуженная нагрузка также уменьшается и находится следующим образом б*' = 1 - хг • сог. Математически задачу можно сформулировать следующим образом:

= = (1) при следующих ограничениях: < п; (2)

г—1

'хг е {0,1,...,«};

■0<сог<1; (3)

Аг> 0,

где выражение (2) ограничивает число размещенных единиц узлов заданным значением и; лгг е {0,1,---,"} в ограничении (3) допускает только планы размещения с неотрицательными значениями х,.

Решать задачу (см. рис.2) предлагается методом максимального элемента, при использовании которого на произвольном шаге процесса решения размещается только один из имеющихся п узлов. Это означает, что на г-ом шаге процесса дается единичное приращение ЛхГ( = 1 только одной г = г- й

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

процесса А* наибольший. Это приведет к максимизации общего эффекта от размещения всех узлов.

= А,+Лг*,1 + АжеУг+...+ Аге?--п б'*-"1' = Аг + Д* + Д^ +... += (4)

= 4+'1Ж> ..... А; = 4(1-(£-1).шг)(1-Ьш2) = ЛХ-'£*.

»=1

Рис.2. Блок - схема алгоритма решения задачи размещения узлов

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

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

Величина приращения целевой функции на произвольном шаге /' можно

определить по формуле: Д* = _ | = ЛГ(М)£*'', (5)

где у4г(| ", г = 1,5— вес зоны после размещения (;-1) единиц узлов, тогда как Д. -сё исходный вес (значимость); х'~1 -- число размещённых узлов в зоне г на г-1 шаге. Тогда как величину приращения значения вектора Д* ' можно найти следующим образом Д; ' -Д"= Л;1 • а"/ '.

В третьей главе рассмотрен метод балансировки нагрузки путём распределения необслуженной нагрузки между узлами СОИ и приведено решение задачи оптимизации структуры узлов. При решении задачи балансирования нагрузки предполагаем, что объекты контента уже предварительно находятся в памяти всех узлов, среди которых будет осуществляться балансировка. Обслуживание пользовательских запросов ограничивается мощностями установленных в узлах физических или виртуальных обслуживающих серверов. Сформулируем задачу распределения, на основе потоковых моделей, основанных на интенсивностях потоков запросов, поступающих между узлами сети.

Пусть имеется СБЫ инфраструктура, состоящая из п географически распределенных узлов, размещенных в некоторых зонах с целью обслуживания пользователей из этих зон. Узлы, в зависимости от их типа, различаются номиналами мощности //,., I = \,п. Обозначим через А,,г = 1 ,п среднюю интенсивность потока запросов, поступающего на узел г за единицу времени. Для простоты будем полагать, что поток запросов, поступающий в узел /, является простейшим. Таким образом, суммарная знешняя интенсивность

п

запросов, поступающих на все узлы сети, определяется по формуле Я = ^ Л1.

;=1

Предполагается, что задержки 7^.,г = 1,и, у = 1 ,п между всеми узлами известны. Если обмен данными между узлами г и j отсутствует, то Тц = 0. Среднюю интенсивность нагрузки, поступающей на узел г как из своей зоны, так и из

л п

других зон можно рассчитать по формуле: у. = Я. - ^Л, ■ хч + -х .

Величины Хц дают характеристику перенаправления потоков запросов между

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

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

— 1 " 1 " ^

¿м ЛыКН-Г,)

Мощность узла [запросов/сек] или [пакетов/сек], можно измерить

единицами данных в секунду и выразить через С1, следовательно - ЬС1, где ^ -

измеряемая в байтах средняя длина пакета объекта контента, которая предположительно одинакова для всех узлов. Тогда, нагрузки (поток) [байт/сек] ^ в г-

ом узле можно выразить с использованием обозначения —<С(. В

Ъ '

выражение (6) необходимо включить межузловую задержку Т^ = Ту ■ I =

7=1,72; I*), которая состоит из времени распространения информации, времени обработки и других фиксированных задержек в пути передачи и обратно пропорциональна пропускной способности.

Оптимизация загрузки СБИ путем балансировки нагрузки заключается в том, чтобы необслуженные запросы разделить между несколькими узлами так, чтобы общий получающийся в результате перераспределенный по узлам сети поток, минимизировал среднюю задержку в сети. Математическая постановка задачи балансировки нагрузки путем перераспределения потоков имеет вид:

Г,

(6)

1 л т

Л /=1 у=1

> тт (7)

С -Г. у у

при следующих ограничениях: > 0; < Ср = /Г, (8)

¡-1 м 4

гДе /¡)~ интенсивность потока, перенаправляемого из узла г в узели>р -

весовые коэффициенты каждой части критерия, они могут быть определены экспертным путем при условии что ■м2=1-м>1; ы - коэффициент, определяющий уровень загруженности узла. Ограничешм (8) соответственно разрешают только положительные значения перенаправляемых потоков, ограничивают потоки значениями свободной мощности узлов и обеспечивают сохранение потока. Предположим также, что узлы связи являются надежными, в том смысле, что они не выходят из строя во время процесса распределения нагрузки, а также поиск, обнаружение и обновление информации о состоянии узлов осуществляются своевременно, а распределение осуществляется централизовано. При решении поставленной задачи балансировки нагрузки между узлами на основе минимизации средней задержки (7) внутри сети использовались встроенные в математическом пакете МайаЬ методы и алгоритмы оптимизации. Количество необслуженной нагрузки, поступившей на

узел /, и его оставшаяся свободная мощность соответственно были определены следующим образом:

Задача оптимизации структуры узлов сети как задача математического программирования формулируется следующим образом. Пусть заданы множество п размещенных ранее УС и нагрузка [байт/сек] Гп г = 1 ,п, поступающая в единицу времени на узел г. Известны С, - мощности (пропускные способности) узлов / = \,п, 2- стоимость обслуживания запросов в узлах | = 1,и. Переменная отражает затраты на аренду или добавление узловой мощности. Необходимо путем решения задачи распределения выбрать оптимальную требуемую мощность (из мощности, доступной для наращивания в каждом узле) для ее добавления в узлы /' = 1,п. Т.е. в зависимости от затрат и поступающей от пользователей нагрузки необходимо выбрать из Е1 -множества доступных для аренды в узлах г = 1,тг физических или виртуальных серверов (узловой мощности) такое подмножество Еош. с: Е1, которое могло бы обслуживать нагрузку и в то же время минимизировать среднюю задержку в сети. Модифицируем критерий (7) путем включения в него стоимости обслуживания в узлах. Имеем:

при ограничениях (8).

Если мощность в узлах наращивается только отдельными независимыми обслуживающими серверами, то количество серверов Еаш должно удовлетво-

рить условию целочислешюсти: = ¡п, . Алгоритм оптимизации

структуры С1Ж состоит из последовательности шагов: Шаг 1. Для исходной структуры сети Стй ---- со средним значением времени задержки

передачи Т0, определяется множество «соседних» структур Сг, зависящих от разных вариантов распределения нагрузки /у, и определённых ограничений, где Е1 - множество серверов обслуживания в каждом узле; Шаг 2. Для всех структур Сг определяется значение средней задержки Тг; Шаг 3. Структура С0 заменяется структурой Сг, соответствующей минимальному значению Т т.е.

(Тг <Т0),Т0 заменяется на Тг, и процедура в случае необходимости повторяется.

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

(10)

т=уЕЕ • т^г+^ • №+^ • ^ га1п ^

балансировке нагрузки. Кластеризация узлов является задачей целочисленного лилейного программирования, для этого ведем переменную:

^ _|1, если узел / прикреплен к кластеру к; гк [0, в противном случае. Тогда задача кластеризации узлов представляется соотношениями:

(12)

J = ХЁ^С^А + Н>,Ttk) -> min;

.-I

¿*a=l,« = U ак<^<Ьк, ак > 0, к = ЪК,

(13)

(14)

где тл~ времена задержки между узлом i и центром кластера кг, wf и w-весовые коэффициенты; Ait = Fi+Fk-Ci-Ck, i = \,n\ k = \K - превышение потока над мощностью между узлом i и центром кластера к; ак, Ък -минимальное и максимальное число возможных узлов в кластере; ограничения (14) определяют желаемое количество узлов в каждом кластере к и позволяют отнести каждый узел только к одному кластеру. Задача оптимизации критерия (13) относится к задачам целочисленного программирования (при условии бинарности целевых переменных) с ограничениями типа равенства и неравенства. Схема оптимизации загрузки в CDN с целью повышения эффективности использования ее ресурсов, реализованная в среде MatLab с применением встроенного набора инструментов Optimization Toolbox, а именно функций fmincon, linprog и bintprog, показана на рисунке 3.

Z

Блок - схема балансировки нагрузки

п, Fn, Сп

7

Выбор критерия оптимизации

X

Формирование ограничении по мощности и сохранению __потока (8)_

Определить начальное приближение (функция linprog)

Найти потоки, минимизирующие (1 (функция fmincon)

Определить максимальный допустимый уровень загруженности узла

L

п, Fi, О

"7

Блок — схема оптимизации структуры

Оперсделение центров кластеров К

Выбор критерия оптимальности (13)

Выбор минимального и максимальною числа возможных узлов в кластере (14)

Нормирование значений превышения потока над мо|Цностью и задержек в интервале [-0.5 :0.5]

Осуществлена е кластеризации (функция bintprog)

Формирование ограничений (8)

Определить начальное приближение (функция linprog)

Найти потоки, минимизиру ющие (11) ((функция /mine on)

Рис .3. Блок- схемы оптимизации загрузки в СОК

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

В таблице 1 приведены значения ожидаемого эффекта со, (уровень удовлетворения зоны) от размещения единицы однотипного узла сети доставки контента в 2-ой зоне и значения значимости Л2 зон для проектируемой виртуальной СОК Значимость Аг каждой из зон (стран) региона были

/5 N N

определены следующим образом: Аг = 1,1 > где 1г = IV/ -

/ г м * м ' 1

интегральный показатель промышленности зоны г, К. - частные показатели

промышленности в зоне г; Wj - весомость этих показателей (определяется экспертами) в общей сумме.

В таблице 1 также проиллюстрирована вычислительная схема алгоритма выбора мест размещения и приведена последовательность текущих векторов Л* = Л'г] • е^4 . Из строки г'^1, в которой записаны компоненты вектора Д.е°, для первого шага процесса оптимизации, следует, что согласно второму пункту алгоритма первый узел размещается в зоне гх=6. Второй узел также размещается в зоне г2~6, тогда как третий в зоне г3 = 9, и т.д. в соответствии с

максимальными элементами вектора А* '. Согласно шестому пункту алгоритма производится пересчет только той компоненты вектора А* ' = Л;-1 • ех/', которая соответствует зоне, где был размещен узел, например, при размещении первого узла (г, = 6).

Зоны -5 о & X га мэ ОАЭ Катар Оман [Йемен 3 и. о со о : 4 У < Иордания о и Ирак | К а к а Ливан ¡Судан Египет Ливия Тунис О, ^ Марокко « га £ о. я га Я

г 1 2 3 4 5 6 7 8 9 10 п 12 13 14 15 16 17 18 Значения функции т

А 6 7 9 8 4 п 3 9 9 3 1 2 4 9 3 6 2 5

а) 1 0.17 0.61 0.46 0.23 0.14 0.39 0.53 0.33 0.17 0.46 0.12 0.03 0.91 0.24 0.19 0.06 1

0 0.83 0.39 0.54 0.77 0.86 0.61 0.47 0.67 0.83 0.54 0.88 0.97 0.09 0.76 0.81 0.94 0

/ 1 6 7 9 8 4 11 3 9 9 3 1 2 4 9 3 6 ?. 5 11

2 6 7 9 8 4 9.46 3 9 9 3 1 2 4 9 3 6 2 5 20.46

3 6 7 9 8 4 6.81 3 9 9 3 1 2 4 9 3 6 2 5 29.46

4 6 7 9 8 4 6.81 3 9 6.02 3 1 2 4 9 3 6 2 5 38.46

5 6 7 3.47 8 4 6.81 3 9 6.02 3 1 2 4 9 3 6 2 5 47.46

6 6 7 3.47 8 4 6.81 3 4.26 6.02 3 1 1 4 9 3 6 ?. 5 56.46

7 б 7 3.47 8 4 6.81 3 4.26 6.021 3 1 2 4 0.82 3 6 2 5 64.46

8 6 7 3.47 4.34 4 6.81 3 4.26 6.02 3 1 2 4 0.82 3 6 2 5 71.46

9 6 5.79 3.47 4.34 4 6.81 3 4.26 6.02 3 1 2 4 0.82 3 6 2 5 78.27

10 6 5.79 3.47 4.34 4 3.95 3 4.26 6.02 3 1 2 4 0.82 3 6 2 5 84.29

11 б 5.79 3.47 4.34 4 3.95 3 4.26 2.04 3 1 2 4 0.82 3 6 2 5 90.29

12 0 5.79 3.47 4.34 4 3.95 3 4.26 2.04 3 1 2 4 0.82 3 6 2 5 96.29

13 0 5.79 3.47 4.34 4 3.95 3 4.26 2.04 3 1 2 4 0.82 3 4.89 2 5 102.08

14 0 3.79 3.47 4.34 4 3.95 3 4.26 2.04 3 1 4 0.82 3 4.89 2 107.08

15 0 3.79 3.47 4.34 4 3.95 3 4.26 2.04 3 1 2 4 0.82 3 4.89 2 0 111.97

** 1 2 1 1 3 1 2 1 2 1 111.97

Балансировка нагрузки между узлами осуществляется следующим образом: предположим, что нагрузка на узлы поступает в виде безприоритетных потоков запросов. Узлом осуществляется обслуживание нагрузки, поступающей из его зоны и соответствующей 80% его мощности, так как загрузка узла более чем на 80% приведет к быстрому и значительному снижению его производительности. Остаток нагрузки требуется оптимальным образом распределить между менее загруженными узлами, минимизируя показатель (7) при выполнении ограничений (8). Первоначальные мощности СОИ-узлов будут заданы в виде вектора |С,.| ,/ = £л. Оставшиеся свободные мощности с учетом запаса (20% от ¡С, ||) для предотвращения перегрузки узла и исключения по (10) будут представлены вектором |С/;||, г = 17«. Поступающие на каждый узел нагрузки будут заданы вектором а нагрузки, подлежащие распределению после исключения по (9), будут представлены вектором 1 = 1 ,п. Матрица задержек ТТ., /,у = 1 ,п при передаче от направляющего узла /

до узла-получателя у рассматриваемой сети необходима для формализации путей перенаправления потоков между узлами. В этой матрице Т0 = Т.,, 7Т . = 0,

если :' = /, т.е. матрица Ту. симметрична и обладает нулевой главной

диагональю. Для рассмотренного в диссертации примера вышеуказанные векторы выглядят следующим образом:

'= 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 [86; 40; 80; 48; 40; 64; 40; 90; 56; 48; 64; 32; 72; 82; 40; 24; 48; 76; 88; 32] |С(|= |70; 80; 100; 60; 70; 100; 50; 50; 90; 60; 80; 100; 90; 90; 50; 70; 60; 70;' 60; 40]

Для ускорения процесса распределения были исключены узлы, не участвующие в распределении, и каналы, соединяющие загруженные узлы, а также каналы, соединяющие узлы между которыми нет взаимодействия. В результате векторы ¡/"-УЦ и ||Сгу|| соответственно выглядят следующим образом: '= 1 8 14 18 19 у= 2 5 6 9 12 16

N1= [30; 50; 10; 20; 40]; ¡Оу| = [24; 16; 16; 16; 48; 32];

Задержки между узлами приведены в таблице 2. Найденные в результате минимизации показателя (7) доли потоков которые будут перенаправлены для балансировки нагрузки приведены в таблице 3.

Таблица 2. Задержки между узлами Тг.., ¡,] =

2 5 6 9 12 16

1 0.35 0.84 0.90 0.36 0.53 0.17

8 0.36 0.22 0.27 0.94 0.16 0.77

14 0.40 0.28 0.15 0.88 0.93 0.59

18 0.59 0.27 0.90 0.87 0.41 0.17

19 0.81 0.70 0.68 0.99 0.08 0.52

Таблица 3. Результат перераспределения нагрузки /¡,1 = 1 ,п:

I \ 2 5 6 9 12 16 У,

1 3.58 0 0 12.95 0 13.47 30

8 19.37 12.04 9.54 0.7 8.35 0 50

14 1.05 2.49 6.46 0 0 0 10

18 0 1.47 0 0 0 18.53 20

19 0 0 0 0.35 39.65 0 40

I 24 16 16 14 48 32 150

На основе распределения нагрузки между узлами по критерию (11) при различных весовых коэффициентах (м>2 и м>3) и мощностях С, получены оптимальные структуры узлов СБН предназначенной для управления в горнохимической промышленности региона БВиСА. Результаты вычислительных экспериментов по оптимизации структуры приведены в диссертационной работе.

В заключении изложены основные выводы и научные и практические результаты работы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Разработана научная концепция применения С1Ж в управлении горнохимическими предприятиями (фосфатной промышленности) региона БВиСА.

2. Разработана модифицированная методика построения С1Ж, отличающаяся использованием методов построения сетей интегрального обслуживания (СИО), предложенных профессорами Яковлевым С.А. и Советовым Б .Я.

3. Разработан алгоритм размещения узлов СБИ, отличающийся применением показателей промышленной значимости зон возможного размещения и ожидаемого эффекта от размещения узлов в этих зонах и основанный на достижении максимумов этих коэффициентов.

4. Разработан метод балансировки нагрузки между СГЖ-узлами, отличающийся оптимальным выбором долей нагрузки и их перенаправлением из предельно загруженных узлов на менее загруженные по критерию средней задержки.

5. На основе модифицированного критерия средней задержки с учетом затрат на обслуживание нагрузок в узлах-адресатах осуществлена оптимизация структуры СОК.

6. Разработан программный комплекс оптимизации нагрузки в сети, состоящий из модуля балансировки нагрузки, модуля оптимизации структуры и модуля кластеризации узлов сети.

СПИСОК ПУ БЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в изданиях, рекомендованных ВАК России:

1. Аль-Таяр, Б.А. Оценка эффективности сетей доставки контента / Б.А. Аль-Таяр, М. М. Музанна, С.А. Яковлев // Известия СПбГЭТУ «ЛЭТИ» - СПб • Изд-во СПбГЭТУ «ЛЭТИ», 2012. -№ 2. - С. 45-49.

2. Аль-Таяр, Б.А. Решение задачи о размещении узлов сети / Б.А. Аль-Таяр, Ю.Н. Матвеев // Науковедение [Интернет-журнал]. - 2013. - №3 (16) [Электронный ресурс]-М. 2013. - Режим доступа: http://naukovedenie.ru/PDF/ 109tvn313.pdf. (доступ свободный).

3. Аль-Таяр, Б.А. Оптимизация структуры сети доставки контента на основе балансировки нагрузки по критерию средней задержки / Б.А. Аль-Таяр, Б.И. Марголис, Ю.Н. Матвеев // Вестник Костромского государственного университета им. H.A. Некрасова - 2014. - Т. 20. - № 5 - С. 46-50.

Другие публикации:

4. Аль-Таяр, Б.А. Оптимальный выбор места размещения узлов сети./ Б.А. Аль-Таяр, М.М. Музанна, С.А. Яковлев // Неделя науки СПбГПУ: Материалы XL международной научно-практической конференции: Ч. VIII. -СПб.: Изд-во Политехи, ун-та, 2011. - С. 147-148.

5. Аль-Таяр, Б.А. Критерии эффективности внедрения сетей доставки контента / Б.А. Аль-Таяр, М.М. Музанна, С.АЛковлев // Неделя науки СПбГПУ: материалы XL международной научно-практической конференции. Ч. VIII, - СПб.: Изд-во Политехи, ун-та, 2011. - С. 146-147.

6. Аль-Таяр, Б.А. Методика построения сети доставки контента / Б.А. Аль-Таяр, М. Музанна // Современные тенденции в науке: Новый взгляд: Сб. научных трудов по материалам Международной заочной научно-практической конференции. - Тамбов: ТРОО «Бизнес-Наука-Общество», 2011 .-№ 8. - С. 10-11.

7. Аль-Таяр, Б.А. Модель адаптивной маршрутизации на основе прогноза интенсивности трафика / Б.А. Аль-Таяр, М.М. Музанна // Современные тенденции в науке: Новый взгляд: Сб. научных трудов по материалам Международной заочной научно-практической конференции. -Тамбов: [ТОО «Бизнес-Наука-Общество», 2011. - № 8. - С. 91.

8. Аль-Таяр, Б.А. Особенности реализации сетей доставки контента в сфере телемедицины / Б.А. Аль-Таяр, С.А. Яковлев, М.М. Музанна // Региональная информатика-2011: Проблемы подготовки кадров в сфере инфокоммуникационных технологий: Сб. трудов санкт-петербургской международной научно-практической конференции. - СПб.: СПОИСУ, 2011 -С. 83-85.

9. Аль-Таяр, Б.А. Предоставление Интернет-услуг в регионах Ближнего Востока и Северной Африки / Б.А. Аль-Таяр, Ю.Н Матвеев // Система гарантий качества образования: Разработка и внедрение: Материалы научно-практической конференции. - Тверь: Купол, 2012. - С. 3-7.

Башир Али Касем Аль-Таяр

ПОСТРОЕНИЕ СЕТЕЙ ДОСТАВКИ КОНТЕНТА ДЛЯ УПРАВЛЕНИЯ ГОРНО-ХИМИЧЕСКИМИ ПРЕДПРИЯТИЯМИ НА ОСНОВЕ ПРИНЦИПА ДЕКОМПОЗИЦИИ

Автореферат диссертации на соискание ученой степени кандидата технических наук

Технический редактор Ю.Ф. Воробьева Подписано в печать 2.02.2015

Формат 60 х 84/16 Бумага писчая

Физ. печ. л. 1,25 Усл. неч. л. 1,16 Уч.-изд. л. 1,09

Тираж 100 экз._Заказ № 8____

Редакционно-издательский центр Тверского государственного технического университета 170026, г. Тверь, наб. Афанасия Никитина, 22