Оптимизация маршрутной матрицы в сетях обслуживания

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

22. Винер Н. Кибернетика или управление и связь в животном и машине. М.: Сов. радио, 1958.
23. Охтилев М. Ю., Соколов Б. В., Юсупов Р. М. Возможный подход к созданию единой информационно-вычислительной среды для системы воздушно-космической обороны // Вопросы оборонной техники: науч. -техн. сб. 2010. Сер. 9, вып. 1(242)-2(243). С. 85−90.
Михаил Юрьевич Охтилев
Николай Габдрахманович Мустафин —
Владимир Евгеньевич Миллер
Борис Владимирович Соколов
Сведения об авторах д-р техн. наук, профессор- СПИИРАН, лаборатория информационных технологий в системном анализе и моделировании- E-mail: oxt@mail. ru
канд. техн. наук, доцент- Санкт-Петербургский государственный электротехнический университет «ЛЭТИ& quot-, кафедра автоматизированных систем обработки информации и управления- E-mail: nikolay. mustafin@gmail. com
канд. техн. наук- ОАО Радиотехнический институт им. акад. А. Л. Минца, Санкт-Петербург- директор филиала- E-mail: miller@progsystema. ru
д-р техн. наук, профессор- СПИИРАН, лаборатория информационных технологий в системном анализе и моделировании- зам. директора по научной работе- E-mail: sokol@iias. spb. su
Рекомендована СПИИРАН
Поступила в редакцию 10. 06. 14 г.
УДК 519. 872
Ю. И. Рыжиков
ОПТИМИЗАЦИЯ МАРШРУТНОЙ МАТРИЦЫ В СЕТЯХ ОБСЛУЖИВАНИЯ
Описан алгоритм расчета временных характеристик разомкнутой сети обслуживания. Предложен метод оптимизации сети обслуживания по среднему времени пребывания заявки в сети путем выравнивания загрузки узлов. Приводятся и обсуждаются результаты численного эксперимента.
Ключевые слова: разомкнутая сеть, время пребывания, выравнивание загрузки узлов.
Расчет сети. Реальные процессы обслуживания связаны с прохождением нескольких его этапов, реализуемых в отдельных узлах сети. Сеть обслуживания состоит из рабочих узлов, пронумерованных от 1 до М, источника (узел «0& quot-) и стока (узел «М+1& quot-). Для каждого j-го узла задаются моменты распределения «чистой& quot- длительности обслуживания {bj?}, l = 1, L ,
число каналов nj и дисциплина обслуживания. Маршрут заявки в сети определяется неразложимой матрицей передач R = {¦ j }, i, j = 0, M +1, образованной вероятностями перехода из
i-го узла в j-й. Важнейшей оперативной характеристикой работы сети является среднее время пребывания в ней заявки. Первым шагом процесса оптимизации сети должна быть минимизация этого времени.
Проблема расчета сетей обслуживания активно обсуждается в сотнях статей и монографий (см., например, список литературы в работе [1]). К концу 1980-х гг. выяснилось, что строгое решение этой задачи возможно лишь при весьма ограниченных условиях теоремы BCMP (Baskett, Chandy, Muntz, Palacios [2]). Методы решения были непомерно трудоемкими, а получаемые характеристики — недостаточными. Как отмечал в ходе дискуссии на
конференции 1983 г. [3] П. Швейцер, «мы дошли до конца дороги с точными моделями… Мы затратили слишком много времени на такие модели, как мультипликативные сети и матрич-но-геометрические решения& quot-. Альтернативой является только потокоэквивалентная декомпозиция сетей обслуживания.
В настоящей статье ограничимся рассмотрением разомкнутых однородных сетей с простейшими потоками. Последнее предположение базируется на известных теоремах о суммировании и случайном прореживании потоков. Интенсивности потоков определяются из уравнений баланса заявок:
м _
^ = Мм 4, 1 = 1, м,
] =1
где Л — суммарная интенсивность потока, поступающего из внешних источников.
Далее для всех узлов должно быть проверено условие отсутствия перегрузки
/ п{ & lt-1, обеспечивающее существование в сети стационарного режима.
С другой стороны, традиционное допущение о показательных распределениях времени обслуживания, как правило, является необоснованным, и порождаемые им ошибки могут быть сколь угодно велики. Это определяет целесообразность моделирования узлов сети системами с простейшим входящим потоком и произвольным распределением времени обслуживания. Последнее приходится аппроксимировать параллельно-последовательным набором фаз с экспоненциально распределенной задержкой в каждой. Приемлемую точность (выравнивание трех заданных моментов) обеспечивает, например, гиперэкспоненциальная аппроксимация с двумя составляющими. Заметим, что возможные случаи комплексных параметров и «парадоксальных& quot- вероятностей (одна отрицательна, а вторая больше единицы) не влияют на осмысленность конечных результатов. После такой аппроксимации расчет распределения числа заявок в узле можно выполнить итерационным методом Такахаси — Таками или методом матрично-геометрической прогрессии [4].
Для разомкнутой сети в целом среднее время пребывания заявки можно, как и для отдельного узла, вычислить на основе формулы Литтла
м _
V = а / Л
г-1
(среднее число заявок в сети к^ делится на суммарную интенсивность входящего потока), которая проверена многократно (в том числе, автором данной статьи).
Оптимизация сети. Эта задача в первом приближении решается как минимизация среднего времени пребывания заявки в сети и имеет множество аспектов: в частности, выбор производительности и количества обслуживающих устройств в узлах (см., например, [5]). Реально производительность таких устройств должна выбираться из конечного ряда значений, а количество устройств должно быть целочисленным. Поэтому постановка задачи о комплексной оптимизации сети формальными методами представляется непродуктивной. Иначе обстоит дело с маршрутной матрицей, оптимизация которой вообще не затрагивает аппаратную часть сети обслуживания и материализуется «бесплатно& quot-. Именно с такой оптимизации и следует начинать. Кроме того, необходимо учитывать, что на маршрутную матрицу могут быть наложены ограничения, диктуемые технологическими и/или организационными соображениями.
Формула Литтла позволяет считать, что минимизация ожидаемого количества заявок в сети одновременно минимизирует среднее время пребывания в ней заявки. Естественно проводить оптимизацию маршрутной матрицы передач путем последовательной «расшивки& quot- узких мест сети, что достигается выравниванием ожидаемого числа заявок в узлах или
коэффициентов загрузки последних. Опишем алгоритм выравнивания (ради экономии места без разбивки на абзацы).
Рассчитать потоки на входе узлов- коэффициенты загрузки узлов- моменты распределения времени пребывания в узлах для однократного захода заявки- среднее количество qi заявок в каждом узле сети и среднее время пребывания заявки в сети м
Т = ^ qi / Л. Выбрать в качестве объекта разгрузки узел ._ с максимальным значением
i=1
*
q = qj_. Выбрать непосредственного «предшественника этого узла. минимум с двумя преемниками. Среди его преемников выбрать узел .+ с наименьшим q = qj +. Долю х потока интенсивностью X * г* ._ переадресовать в узел. + посредством коррекции маршрутной матрицы.
Указанные действия выполняются, пока остаются значимыми уменьшения среднего времени пребывания заявки в сети. Коррекция всегда производится для ненулевых элементов матрицы передач, что позволяет запрещать недопустимые ребра маршрутов. Максимально допустимое значение х определяется из условия
р'- + + хХ * г * _ Ь + / п + & lt-=0,95,
где р'-. + - исходный коэффициент загрузки.
Ниже рассматриваются два субоптимальных алгоритма оптимизации маршрутной матрицы.
Выравнивание числа заявок предполагает, что оптимальное значение х выбирается как абсцисса минимума параболы, аппроксимирующей зависимость от х суммарного числа
заявок в узлах ._ и. +. Парабола Ах2 + Вх + С строится по точкам для Хо =0, Х1 = хтах /2 и Х2 = хтах, причем слагаемые хо =0 определяются по результатам первого этапа текущей итерации. Координата минимума параболы
х*=. х12(. У2 _ & gt-'-о) _ х2(У1 _ Уо)
2[х1(У2 _ Уо) _ х2(У1 _ Уо)] В примере сети с шестью рабочими узлами при исходной маршрутной матрице стартовое среднее время пребывания заявки в сети составляет 16,247, после первой итерации — 7,869, после второй — 6,821. Далее происходят осцилляции в диапазоне [6,8о, 7, о2].
Выравнивание коэффициентов загрузки узлов. Приравнивая правые части выражений для новых коэффициентов загрузки, приходим к условию
Р _ _Р + х = ¦..
X * г * _(Ь _/ п _+ Ь + / п +).. ,] ].. .
Реализация этого подхода обеспечивает монотонное уменьшение целевого показателя, которое по шагам составляет 7,84- 1,27- о, 183- 3,86-Ю-2- 1, о2-Ю-2- 2,94-Ю-3- 2,58-Ю-4- 7,71-Ю-5- 6,87−1о-6. Последний результат составил 6,896.
Обсуждение результатов. Из сопоставления результатов следует:
— оба рассмотренных метода работоспособны, несложны, быстро (в примере — за три шага) приводят к практически приемлемому результату и обеспечивают значительное уменьшение среднего времени пребывания заявки в сети-
— минимизация суммарного числа заявок в сети после некоторого числа монотонных улучшений порождает осциллирующий процесс-
— выравнивание коэффициентов загрузки монотонно приводит практически к тому же результату (разница в третьем знаке) и в каждой итерации исключает необходимое для параболической аппроксимации дополнительное двукратное обращение к процедуре расчета модели M / Н / п для двух узлов сети.
Таким образом, для реальных расчетов предпочтительно применять выравнивание коэффициентов загрузки узлов.
Предложенный подход можно обобщить и на неоднородный поток заявок. Заключение. Алгоритм коррекции маршрутных матриц прост, эффективен и позволяет легко учесть ограничения на допустимость коррекции их отдельных элементов. Если работа с маршрутной матрицей не дает приемлемых результатов, следует использовать эту технологию в комбинации с последовательным повышением производительности наиболее загруженных узлов — увеличением числа каналов или их быстродействия. Такую оптимизацию следует вести в диалоговом режиме.
список литературы
1. Ивницкий В. А. Теория сетей массового обслуживания. М.: Физматлит, 2004.
2. Baskett F., Chandy K. M. Muntz R. R., Palacios J. G. Open, closed, and mixed networks of queuing with different classes of customers //J. of the ACM. 1975. Vol. 22, N 2. P. 248−260.
3. Mathematic computer performance and reliability // Proc. of the Intern. Workshop, Piza, 1983. Amsterdam: North-Holland Publ. Co, 1984. 429 p.
4. Рыжиков Ю. И. Алгоритмический подход к задачам массового обслуживания: Монография. СПб: ВКА им. А. Ф. Можайского, 2013. 496 с.
5. Янбых Г. Ф., Столяров Б. А. Оптимизация информационно-вычислительных сетей. М.: Радио и связь, 1987. 232 с.
Сведения об авторе
Юрий Иванович Рыжиков — д-р техн. наук, профессор- СПИИРАН, лаборатория информационных технологий в системном анализе и моделировании- Военно-космическая академия им. А. Ф. Можайского, кафедра математического обеспечения ЭВМ, Санкт-Петербург- профессор- E-mail: ryzhbox@yandex. ru
Рекомендована СПИИРАН Поступила в редакцию
10. 06. 14 г.
Информационная модель сопровождения распределенных мероприятий 19
УДК 004. 896
В. Ю. Будков, А. Л. Ронжин
ИНФОРМАЦИОННАЯ МОДЕЛЬ СОПРОВОЖДЕНИЯ РАСПРЕДЕЛЕННЫХ МЕРОПРИЯТИЙ В ИНТЕЛЛЕКТУАЛЬНОМ ЗАЛЕ СОВЕЩАНИЙ
Рассматривается проблема информационно-технического сопровождения распределенных совещаний и проанализированы основные этапы организации мероприятий с территориально распределенными участниками. Предложена информационная модель, описывающая способы обработки и обмена потоками данных между удаленными участниками в зависимости от ситуации в интеллектуальном зале совещаний.
Ключевые слова: интеллектуальное пространство, распределенные мероприятия, аудиовизуальная обработка данных, протоколирование дикторов, информационная значимость.
Введение. Для распределенных мероприятий характерна ситуация, при которой часть участников находится в зале совещаний и имеются удаленные участники, использующие персональные и мобильные устройства для подключения к веб-системе трансляции совещаний. Системы сопровождения таких мероприятий получили наибольшее развитие с возникновением научной парадигмы окружающего интеллектуального пространства [1], обеспечивающего проактивное ненавязчивое персонифицированное обслуживание участников. Так как под окружающим интеллектуальным пространством понимается глобальное единое пространство, то его создание в ближайшее время затруднительно, поэтому сейчас ведутся исследования по разработке отдельных менее масштабных прототипов интеллектуальных пространств, например «умная& quot- комната, «умный& quot- дом, «умный& quot- город [2, 3].
Существующие исследовательские прототипы интеллектуальных залов представляют собой распределенную сеть аппаратно-программных модулей, активационных устройств, мультимедийных средств и аудиовизуальных сенсоров. С увеличением количества решаемых задач и обслуживаемых пользователей становится сложно контролировать множество программных и аппаратных модулей, задействованных в интеллектуальном пространстве, поэтому необходимо математическое обеспечение и программные средства, реализующие управление совместной работой распределенных модулей.
Анализ существующих систем сопровождения. При разработке систем сопровождения распределенных мероприятий выделяют несколько этапов, требующих автоматизации [4]: 1) организация совещания, где определяются основные участники и утверждается план совещания- 2) подготовка совещания, в ходе которой производится оповещение участников и проверка готовности их участия- 3) проведение совещания, включающее обсуждение и подготовку протокола- 4) завершение совещания, где утвержденный протокол рассылается участникам- 5) контроль решений совещания, включающий рассылку напоминаний и оценку выполнения решений- 6) анализ материалов совещания, собранных в ходе предыдущих этапов, с использованием базы данных мероприятия для поиска и просмотра необходимой информации.
Для выявления основных проблем существующих систем сопровождения распределенных мероприятий был проведен их сравнительный анализ по пяти типам характеристик: 1) входные модальности, используемые для анализа и записи поведения участников во время проведения совещания- 2) основные типы выходных данных, используемых при взаимодействии с пользователем системы- 3) основные виды применяемого оборудования- 4) сервисы

ПоказатьСвернуть
Заполнить форму текущей работой