автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Адаптивное управление конфликтными потоками

/

У» I. " \ V

^ - ' /

НИЖЕГОРОДСКИЙ ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ

/

ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. Н. И. ЛОБАЧЕВСКОГО

Факультет вычислительной математики и кибернетики Кафедра прикладной теории вероятностей

На правах рукописи

Литвак Нелли Владимировна АДАПТИВНОЕ УПРАВЛЕНИЕ КОНФЛИКТНЫМИ ПОТОКАМИ

05.13.17- Теоретические основы информатики

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель доктор физико-математических наук, профессор Федоткин Михаил Андреевич

Нижний Новгород, 1998

Оглавление

Введение 4

1 Математическая модель системы адаптивного управления конфликтными потоками 19 §1.1. Постановка задачи на содержательном уровне .... 19 §1.2. Нелокальное описание функционирования системы в виде маркированного точечного процесса {(Ъ1?,Г,-,ъ);г>0}.................... 27

§1.3. Рекуррентные соотношения для последовательности

{(Г,-, л'г-);г > 0} и для ее одномерных распределении . . 43

2 Предельные свойства изучаемой системы 49 §2.1. Получение рекуррентных соотношений для многомерных производящих функций............. 49

§2.2. Критерии существования предельного распределения

для {(Г,-, к,-); ъ > 0}..................... 55

§2.3. Итеративно-мажорантный метод получения необходимых условий существования стационарного режима 63 §2.4. Достаточные условия существования предельного

распределения....................... 83

3 Качественное исследование системы 86

§3.1. Графическая интерпретация предельных свойств адаптивного алгоритма .управления потоками ............86

§3.2. О загрузке изучаемой системы..........................98

§3.3. Практические рекомендации по выбору наилучших

параметров алгоритма..................106

4 Численное исследование системы методом имитационного моделирования 112

§4.1. Основные задачи исследования и методика их решения112

§4.2. Определение квази-оптимальных параметров.....119

§4.3. Анализ адаптивных свойств системы на переходном

процессе..........................130

Заключение 136

Список использованной литературы 138

Приложения 150

А Дополнение к аналитическому исследованию 151

А.1 Выводы формул......................151

А.2 Доказательства некоторых утверждений........153

В Иллюстрации качественного исследования системы 165

С Результаты имитационного моделирования 176

D Текст программы 196

Е Некоторые частные случаи изучаемого алгоритма 215

Е.1 Система с до обслуживанием по информации о длине

очереди...........................215

Е.2 Управление конфликтными потоками по информации

об интервалах поступления ..........228

Введение

Характеристика изучаемой темы в целом

Задачи теории массового обслуживания возникли в начале XX века в связи с развитием и постоянным расширением телефонных сетей в крупных городах. Такие задачи впервые были описаны в 1907 г. Ф. В. Йоханнсеном /1/, а первые результаты были получены в 1909 г. датским математиком А. К. Эрлангом /2/. Работы Эрланга, которые относятся к 1909, 1917 и 1923 гг., стали основой классической теории массового обслуживания. Начиная с этого времени и по сегодняшний день теория массового обслуживания постоянно и интенсивно развивается, вызывая неизменный интерес у большого количества исследователей. Ведущую роль в развитии этой теории сыграли работы Ф. Поялачека, А. Н. Колмогорова, А. Я. Хинчина, Б. В. Гнеденко, И. Н. Коваленко, К. Пальма, Д. Кендалла, Д. Линдли, П. Морана, Л. Такача, Д. Кокса, В. С. Королюка, А. А. Боровкова. Различные системы массового обслуживания подробно рассмотрены в монографиях /3-13/ и других.

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

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

Широкий класс систем с несколькими потоками (или типами) заявок представляют из себя различные приоритетные системы. Исследование таких систем отражено в работах /14 -19/. В последнее время П. П. Бочаровым /20/ и А. В. Печинкиным /21/ были рассмотрены приоритетные системы при марковских входных потоках. Приоритетные системы вызывают значительный интерес, поскольку именно приоритетные алгоритмы управления оказываются оптимальными в системах с разделением времени при обслуживании нескольких конфликтных потоков заявок. Соответствующие результаты при различных предположениях о входных потоках и свойствах обслуживающего устройства были получены Г. П. Климовым /22, 23/, В. В. Рыковым /24/, М. А. Федоткиным /25, 26/, Е. А. Тимофеевым /27/, А. А. Высоцким /28/.

Другой широкий класс систем с несколькими потоками заявок представляют из себя системы с циклическим обслуживанием /10/, или циклические системы /29/. В таких системах переключения происходят в заданном заранее периодическом порядке. Основные результаты по циклическим системам массового обслуживания принадлежат таким исследователям, как П. Куен, Л. Клей-нрок, О. Боксма, В. С. Жданов, Е. А. Саксонов, X. Леви, М. Сиди, У. Ехиали и др. В циклических системах при обслуживании каждого из потоков могут применяться различные алгоритмы (режимы, стратегии). Наиболее распространенными являются следующие четыре алгоритма: 1) алгоритм полного освобождения, когда очередь каждого потока обслуживается до конца (exhaustive policy);

2) пакетный алгоритм, при котором обслуживающее устройство, подключившись к потоку, обслуживает все заявки, поступившие в систему до момента подключения (gated policy); 3) алгоритм, при котором обслуживающее устройство, подключившись к потоку, обслуживает не больше одной заявки этого потока (limited-1 policy); 4) обобщение третьего алгоритма - алгоритм, при котором обслуживающее устройство, подключившись к потоку, обслуживает не больше к заявок этого потока (^-limited policy). Более развернутая классификация дана в работах /30, 31/.

Для первых двух алгоритмов условия существования стационарного режима найдены и обоснованы в работе /32/. Эти условия сводятся к тому, что суммарная загрузка по всем потокам должна быть меньше единицы (под загрузкой для каждого потока здесь подразумевается отношение среднего времени обслуживания заявки к среднему промежутку времени между двумя последовательными поступлениями). Для систем с первым или вторым алгоритмом при различных предположениях о законах поступления и обслуживания получено много аналитических результатов, в том числе распределение длин очередей в стационарном режиме и среднее время ожидания /33-37/. Для третьего и четвертого алгоритмов условия существования предельного распределения выглядят по-другому /38, 39/. Кроме того, для четвертого алгоритма практически невозможно выразить стационарные характеристики системы через ее параметры. Циклическим системам и сравнению перечисленных выше традиционных алгоритмов посвящены обзоры /29/ и /40/. В работе /40/ показано, что из первых трех алгоритмов оптимальным с точки зрения средних задержек является алгоритм полного освобождения.

Наиболее распространенным реальным примером системы с конфликтными потоками является перекресток, регулируемый

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

В настоящее время на большинстве перекрестков используется алгоритм с фиксированным ритмом, когда длительности зеленого и красного света, а также порядок переключений заданы заранее и всегда одинаковы. Первые теоретические результаты для систем с подобным алгоритмом были получены Ю. И. Неймар-ком и М. А. Федоткиным /41/, а также А. Дж. Миллером /42/ и Д. Р. Мак Нейлом /43/. Эмпирическая формула для среднего времени ожидания была получена Ф. В. Вебстером /44, 45/. Подобные системы с различными предположениями о входных потоках и различными критериями оптимального управления рассмотрены в работах /46 - 51/. Алгоритм с фиксированным ритмом, безусловно, является самым простым и дешевым способом управления транспортом. Однако, к сожалению, даже при оптимальных параметрах

этот алгоритм далеко не всегда оказывается самым эффективным.

За последние двадцать лет было создано и изучено немало адаптивных алгоритмов управления конфликтными транспортными потоками с помощью автомата-светофора. При адаптивном алгоритме управления длительность зеленого света и порядок переключений зависят от той или иной информации о текущем состоянии перекрестка, что позволяет значительно лучше регулировать движение. Различные адаптивные алгоритмы описаны в работах /52 - 55/. В работах /49, 56, 57/ рассматривается алгоритм с приоритетным направлением. При таком алгоритме зеленый свет для неприоритетного направления имеет фиксированную длительность, а зеленый свет для более интенсивного (приоритетного) направления длится сначала некоторое заданное время, а затем продлевается, если очередь по неприоритетному направлению пуста. Для таких 'систем получены условия существования стационарного режима, построены имитационные модели и изучены свойства оптимального управления. В работах /58, 59/ рассматривается циклический алгоритм для двух транспортных потоков, где суммарная длительность цикла фиксирована, а длительности зеленого света для первого и второго потоков перераспределяются в зависимости от соотношения длин очередей. В работах /60, 61/ рассматривается циклический алгоритм, где зеленый свет продлевается, если по "зеленому" направлению поступает машина. Для такого алгоритма получен критерий существования стационарного режима в системе, а также найдены некоторые формулы и оценки для

4

средней длины очереди по каждому потоку. В работах /62 - 67/ рассмотрена система, где зеленый свет продлевается, если длина очереди по "зеленому" направлению превышает некоторое критическое значение.

Заметим, что пример перекрестка порой используется для ин-

терпретации циклических систем /34, 40/. Однако задачи управления транспортом не сводятся к анализу традиционных циклическим систем и обычно решаются с помощью других методов и подходов. Это связано с тем, что, во-первых, СМО, соответствующая перекрестку, обычно бывает близка к циклической системе с алгоритмом четвертого типа, наименее изученным среди традиционных алгоритмов. Во-вторых, на перекрестке может применяться достаточно сложный алгоритм определения длительности зеленого света, что приведет к дополнительным трудностям при исследовании. Наконец, в-третьих, применяемый на перекрестке алгоритм не обязательно является циклическим.

В данной работе будет изучен класс алгоритмов управления транспортом, где длительность зеленого света зависит от длины очереди и наличия поступлений по "зеленому" направлению, а порядок переключений при определенных условиях зависит от очередности подхода машин. Для адекватного математического описания управления транспортом с помощью предлагаемого алгоритма будут использованы методы теории систем массового обслуживания с переменной структурой, которая разработана М. А. Федоткиным и обстоятельно изложена в работе /68/. Эта теория успешно применялась при анализе реальных систем управления конфликтными потоками. Сюда прежде всего относятся системы управления транспортом на перекрестке /58 - 67/, системы управления микросвар очными комплексами /69/, системы управления воздушным транспортом в аэропортах с несколькими взлетно-посадочными полосами /70/ и системы с разделением времени, которые являются адекватной моделью вычислительных систем /25, 26, 28/.

Общая схема СМО с переменной структурой изображена на рис. 1. В систему поступают входные потоки требований П^ П2, ..., Пт. Заявки каждого из потоков направляются в соответствую-

Рис. 1. Общая схема СМО с переменной структурой

щие накопители 0Ь 02, ..От ограниченной или неограниченной емкости. Требования из накопителей поступают на обслуживание согласно соответствующим стратегиям механизма обслуживания /Зь /32, ..., /Зт. При построении математической модели реальной системы эти стратегии нужно выбирать так, чтобы они как можно лучше отражали реальный процесс обслуживания. Обслуживающее устройство имеет п состояний Г^1), Г^2^, ..Г^, изменяющихся согласно некоторому алгоритму управления потоками. Для каждого из состояний определено свое функциональное назначение. Так, состояние ОУ может соответствовать обслуживанию одного из потоков или режиму переналадки, когда ОУ переключается от одного потока к другому /25/. При построении математических моделей реальных систем правильный выбор множества состояний ОУ не всегда очевиден, но всегда очень важен для получения удобного и в то же время полного математического описания системы. При описании СМО с переменной структурой различают два вида выходных потоков. Это реальные выходные потоки Пь Пг, . •Пто и потоки насыщения П'1? П'2, ..., П^, которые являются выходными потоками при максимальной загруженности и эксплуатации системы. Такие выходные потоки, например, возникают, если в системе всегда есть очередь, и ОУ работает с максимальной интенсивностью. Для математического описания систем обслуживания с переменной структурой используется нелокальный подход /68/. При таком подходе система рассматривается в специально выбранные случайные моменты вр'емени, и исследователь не интересуется, что происходит с системой между этими моментами.

Теория систем с переменной структурой при нелокальном способе описания дает универсальный метод для построения математических моделей, в которых могут быть учтены многие характерные особенности реальных систем. Например, для транспортных

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

Основные задачи и содержание данной работы

В диссертации рассмотрена система адаптивного управления конфликтными потоками. Впервые предлагается адаптивный алгоритм управления, который предполагает использование информации о количестве заявок в системе, а так же об интервалах поступления и об очередности подхода заявок. При создании предлагаемого алгоритма учитывались прежде всего особенности транспортных систем, и в качестве реального примера изучаемой системы используется система управления транспортными потоками на перекрестке. При построении 4математической модели системы впервые учтены многие характерные особенности перекрестка, такие как изменение скорости движения во время зеленого света, переезд через перекресток нескольких машин одновременно и особенности желтого света. При составлении и математическом исследовании алгоритма учитывались правила дорожного движения /78/ и психология водителей. Кроме того, впервые сделана

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