WWW.NET.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Интернет ресурсы
 

«Том 28 1992 Вып. 3 УДК 621.394.74:519.2 © 1992 г. А.Н. Рыбко, А.Л. Столяр ОБ ЭРГОДИЧНОСТИ СЛУЧАЙНЫХ ПРОЦЕССОВ, ОПИСЫВАЮЩИХ ФУНКЦИОНИРОВАНИЕ ОТКРЫТЫХ СЕТЕЙ МАССОВОГО ОБСЛУЖИВАНИЯ ...»

ПРОБЛЕМЫ ПЕРЕДАЧИ ИНФОРМАЦИИ

Том 28 1992 Вып. 3

УДК 621.394.74:519.2

© 1992 г. А.Н. Рыбко, А.Л. Столяр

ОБ ЭРГОДИЧНОСТИ СЛУЧАЙНЫХ ПРОЦЕССОВ,

ОПИСЫВАЮЩИХ ФУНКЦИОНИРОВАНИЕ ОТКРЫТЫХ СЕТЕЙ

МАССОВОГО ОБСЛУЖИВАНИЯ

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

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

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



§ 1. Введение В работе изучаются условия существования стационарного режима для открытых сетей массового обслуживания с конечным числом типов заявок. Заявкам каждого типа соответствует фиксированный маршрут прохождения через сеть. Средние времена обслуживания заявок в узлах сети зависят от типа заявки и порядкового номера узла по маршруту заявок данного типа. Мы будем рассматривать только сети, функциони­ рование которых описывается однородным марковским процессом со счетным числом состояний и непрерывным временем. Это ограничение является, по-видимому, техни­ ческим. Оно связано с тем, что в данной работе получен и применяется критерий эрго­ дичности именно для таких процессов.

Рассматриваемая сеть обслуживания описывается следующим образом. Сеть состоит из / узлов. Имеется / типов заявок. Входной поток заявок типа i, i €Е {1,...., /}, есть пуассоновскии поток с интенсивностью Л,- (эти потоки взаимно независимы для разных типов з а я в о к ). Каждому типу заявок соответствует свой маршрут h о, • • •, / а * ),... ад, /с». k)Gj,k=i,...,K (о, т.е. последовательность узлов сети, в которых должны обслуживаться заявки данного типа прежде, чем покинуть сеть. Здесь K(i) - длина маршрута для заявок типа i, а /

–  –  –

тоты, что все времена обслуживания экспоненциально распределены. (Все дальнейшие результаты работы останутся справедливыми и для произвольного распределения фазо­ вого типа для времен обслуживания заявок.) В каждом узле /G/ действует некоторая консервативная дисциплина обслуживания.

Нетрудно определить однородный марковский процесс s(t) со счетным фазовым пространством, описывающий работу рассматриваемой сети. Процессы такого типа изучались в работах Рыбко [1,2], Келли [3] и Месси [ 4 ].

Обозначим через р - суммарную нагрузку у з л а / :

;

–  –  –

для многих естественных случаев, например в случае дисциплины "обслуживание в порядке поступления" (FCFS) в каждом узле.

Гипотеза 1- доказана также для двух простых классов сетей (см, [2]). Наш подход основан на изучении свойств некоторого "предельного" детерминированного процесса (см. § 4 ). Этот детерминированный процесс может рассматриваться к а к предел после­ довательности процессов, получающихся с помощью нормировки и одновременного изменения масштаба времени из последовательности исходных процессов с "неограни­ ченно возрастающим" начальным состоянием. Эта техника представляется полезной при исследовании условий существования стационарного режима и для более общих сетей.

Приведем наглядную и не вполне строгую формально интерпретацию этого предель­ ного детерминированного процесса. Имеется / сосудов и / сортов жидкости. В началь­ ный момент времени суммарное количество жидкостей во всех сосудах равно единице.

Жидкость сорта / е / вливается в первый сосуд /(*, 1) своего маршрута с постоянной скоростью X,-, перетекает через последовательность сосудов fa 1 ),..., f a f c ),..., faff(0) и затем покидает сеть. Единица г'-й жидкости в сосуде / = /(/, к) имеет " о б ъ е м " u,-fc.

Каждый сосуд / е J имеет два отверстия - верхнее, через которое жидкости втекают в сосуд (величина этого отверстия неограничена), и нижнее, через которое жидкости вытекают из сосуда. Величина нижнего отверстия равна единице. Таким образом, если данный сосуд не пуст, то общий "объем" жидкости, вытекающей из данного сосуда за единицу времени, равен единице. Жидкость вытекает через отверстие в данном сосуде согласно той же дисциплине, что и дисциплина обслуживания для соответствующего узла сети обслуживания. Например, для дисциплины FCFS жидкости вытекают из сосуда "в том же порядке", в котором они втекают в данный сосуд. Свойство эрго­ дичности рассматриваемого марковского процесса соответствует тому факту, что наша система сосудов опустошится за конечное время при любом начальном состоянии с суммарным количеством жидкостей, равным единице. Похожие детерминированные процессы дискретного типа исследуются в теории расписаний для производственных систем (см. работы Перкинса и Кумара [ 6 ], Кумара и Сейдмана [.7]). Пример нестабиль­ ного детерминированного процесса в теореме 6 похож на пример Кумара и Сейдмана Б [ 7 ]. Этот пример помогает доказательству невозвратности соответствующего марков­ ского процесса (теорема 7 ), В этой статье мы рассматриваем простейшую нетривиальную сеть (подробно описан­ ную в § 3 ), исследование которой не поддается методам, развитым ранее.

Эта сеть состоит из двух узлов, в которых обслуживаются два типа заявок. Заявки движутся через сеть в противоположных направлениях, а именно: требования 1-го типа, поступая в сеть, проходят обслуживание вначале в первом узле, а затем во втором.

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

Первый рассмотренный в работе случай — это сеть, соответствующая дисциплине FCFS в обоих узлах. В этом случае доказана гипотеза 1 (теорема 1 ). Для доказательства этой теоремы используется критерий типа Мустафы—Фостера для однородных марков­ ских процессов с непрерывным временем и счетным числом состояний (теорема 2 ).

Аналогичный (более общий) критерий эргодичности счетных цепей Маркова в дискрет­ ном времени доказан Малышевым и Меньшиковым в [ 8 ].

Второй случай, рассматриваемый в работе, — это специальное приоритетное обслужи­ вание в каждом из узлов: в 1-м узле заявки 2-го типа имеют абсолютный приоритет, а во втором узле наоборот, заявки 1-го типа имеют абсолютный приоритет. Показано (теорема 7 ), что в этом случае гипотеза 1 не верна: для некоторой области параметров, удовлетворяющих условию Р/1, / е /, соответствующий марковский процесс невозвратен.

Статья построена следующим образом. В § 2 дано формальное описание рассматри­ ваемой сети, состоящей из двух узлов. В § 3—5 доказывается гипотеза 1 для дисципли­ ны FCFS в обоих узлах рассматриваемой сети. В § 6 мы рассматриваем приоритетную дисциплину и доказываем невозвратность соответствующего марковского процесса для некоторой области параметров v, удовлетворяющих условию гипотезы 1. В Прило­ ik жении доказываются леммы 1, 2, 3, 1 ', 2', 4 и теорема 2.

–  –  –

Сеть состоит из двух узлов J ={ 1,2]. Каждый узел состоит из обслуживающего прибо­ ра и очереди с неограниченным числом мест для ожидания. В сеть поступают два типа заявок (/ = 11,2J). Потоки поступающих заявок являются независимыми пуассоновскими потоками с интенсивностями \ iGI; Заданы фиксированные маршруты для заявок b каждого типа; заявки 1-го типа обслуживаются вначале в узле 1, а затем в узле 2 и, наоборот, заявки 2-го.типа обслуживаются вначале в узле 2, а затем в узле 1, После окончания обслуживания во втором по счету узле своего маршрута каждая заявка покидает сеть. Будем говорить^ что заявки типа i, поступающие в к-й по счету узел своего маршрута (т.е. узел /" = /(/, к)), образуют (г;А;)-поток, г G7, к = 1,2. Например, / ( 2, 1 ) = 2, (2,1,)-поток является пуассоновским потоком с интенсивностью Х. Напом­

–  –  –





Итак, пусть задана дисциплина FCFS в каждом узле.

Состояние сети s S зададим следующим образом:

Здесь Qj — общее число заявок в узле / EJ, tySС,1(4 Л ) : / & * ) = /} — тип заявки, стоящей на 1-м месте в очереди в узле /. Очевидно, что s (t), t 0, есть неприводимая счетная цепь Маркова в непрерывном времени t.

Теорема 1. При выполнении условия (1) марковский процесс s(i) является эргодическим.

Для доказательства теоремы нам понадобится следующий критерий эргодичности для однородных марковских процессов со счетным числом состояний и непрерывным временем, (Этот критерий является аналогом критерия эргодичности, полученного в [8] для счетных цепей Маркова в дискретном времени.) Т е о р е м а 2. Рассматривается неприводимая цепь Маркова со счетным множест­ вом состояний S и непрерывным временем t0.

Пусть существуют:

1) неотрицательная функция V(s), s ES;

2) конечное подмножество S C'S; 0

–  –  –

что заявки, находящиеся в сети в момент t = 0, поступали в сеть в отрицательные моменты пТ, (п — 1) Т,..., Г (по одной заявке в каждый момент). Причем последова­

–  –  –

Зафиксируем произвольную пару (г; k) EG. Рассмотрим последовательность функций \fik{t), t G [Т, 0]}, п 1, входящих в соответствующие начальные состояния f'^°\

–  –  –

G G, удовлетворяет условиям, приведенным ранее, причем S /,*(0)=1.

(i,fc)e G Естественно предположить, что для любого фиксированного г 0 последователь­ n ность наборов случайных функций f i'M (или, что эквивалентно, последовательность случайных процессов f" '^', % G [0, г]) сходится по вероятности к некоторому множест­ ву детерминированных функций pf (или к детерминированному процессу f^\ ? G E[0,t]).

В этой работе мы не доказываем результат о сходимости процессов. Вместо этого в данном параграфе мы дадим формальное определение "предельного" детерминирован­ ного процесса /^^соответствующего "предельному" начальному состоянию/^°^\ и ис­ следуем его свойства. В следующем параграфе эти свойства детерминированного про­ цесса будут в некотором смысле перенесены на последовательность случайных про­ цессов f"'(*\ п Это позволит доказать теорему 3.

Рассмотр.ш множество функций

–  –  –

Рассмотрим произвольный детерминированный процесс / О, ? 0, соответствующий произвольному начальному состоянию f^°\ Используем леммы 1 и 2. Как отмечено выше, X, 1 (f) = Xi = const и Х (г) = Х = const для всех t 0. Рассмотрим следующие 21 2

–  –  –

( 1) *ХЙ = ^ 2 ( Д Г ), (6)

–  –  –

1. (9') *2 «21 + % 2 "12

–  –  –

Основная идея доказательства теоремы 3 заключается в повторении схемы доказа­ тельства теоремы 5 и одновременной замене свойств детерминированного процесса f(*\ t 0, на аналогичные асимптотические свойства последовательности случайных процессов / " О, t 0, когда и -» °°.

;

Введем следующие обозначения. Пусть для произвольной функции А (г)

–  –  –

Рассмотрим следующую дисциплину обслуживания в узлах рассматриваемой сети. В узле 1 заявки типа 2 (т.е. заявки (2,2)-потока) имеют абсолютный приоритет и, наобо­ рот, в узле 2 абсолютный приоритет имеют заявки типа 1 (т.е. заявки (1,2)-потока).

Нетрудно видеть, что для такой дисциплины обслуживания поведение сети описывает­ ся более простой марковской цепью Q(t) со счетным пространством состояний: Q(t) = G G f

- J Qik ft), ('» к) l 0- Заметим, что состояния Q, для которых JGi2 о,

–  –  –

Р,1,/=1,2.

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

Детерминированный процесс q(t) = { q ft), (г, к) 6 G, t 0}, соответствующий фикси­ ik

–  –  –

/ =1 состояния Q (0) с достаточно большим Qi i (0) = п Pllg(f)l0,f0l0.

Теорема доказана.

Авторы выражают глубокую благодарность Р.Л. Добрушину, Ю.М. Барышникову, А.А. Пухальскому, Е.А. Печерскому и С.Г. Фоссу за полезные обсуждения.

–  –  –

res Из условий (FI 2)-(П.4) следует, что марковская цепь а (и) является эргодической (в силу критерия эргодичности Мустафы—Фостера [Ю]). Более того, в работе [Coffman E.G., Jr, Stolyar A.L., Polling Server on a Line, General Independent Service Times//Unpublished] показано, что (в случае выполнения (П.2) — (П.4)) стацио­ нарное распределение P, sES цепи а (и) удовлетворяет условию s

–  –  –

Д о к а з а т е л ь с т в о л е м м ы 1. Поскольку узел / фиксирован, мы будем для упрощения обозначений опускать индекс / при величинах ту, vvy, ну везде, где это не ведет к путанице.

Выберем 7^ = Т ( 7 \ ), где Г (. ) - функция, фигурирующая в утверждении леммы 5.

–  –  –

и пусть вх = в = ?, если множество [ • } пусто. Рассмотрим самый общий случай, когда t i 0i 0 ?. (Все вырожденные случаи рассматриваются аналогично.) Заметим,

–  –  –

что эквивалентно условию ll7/(0 II = 0 и условию ( / а (0 =/«('), Ц(0=/р(0.

Лемма доказана.

Д о к а з а т е л ь с т в о л е м м ы 3. Без потери общности будем считать, что Xj = = Х = 1. Доказательство леммы 3 вытекает из следующих лемм 6—8,

–  –  –

исходной. Эта система рассмотрена в лемме 6, и мы сохраним для нее все обозначения леммы 6. Систему, рассматриваемую в настоящей лемме, назовем модифицированной и все относящиеся к ней величины и функции будем помечать волной сверху.

Заметим, что функции ip (x) и ip (x) - убывающие. Кроме того, справедливы i2 22

–  –  –

Аналогичные два утверждения с противоположным неравенством также эквивалентны.

Д о к а з а т е л ь с т в о л е м м ы 1'. Зафиксируем константу с 0 и выберем константу Т следующим образом: Т = Т' (Т + с) +.с, где через Г ( - ) обозначена функция Т ( • ), построенная в лемме 5'. Таким образом, для любого tT —с

–  –  –

причем его поведение в этом промежутке таково, к а к если бы поток заявок типа 2 отсутствовал. Во-вторых, величина 6 1 1 (О не убывает на тех интервалах времени, в которых 622 (0 ОРассмотрим процесс 6(0 = (61 1 (О, 6 1 2 (0) t 0, который получается из процесса Q (0 путем исключения интервалов времени, в которых 6 2 2 ( 0 0. Формально, пусть 6(0= (0(0), где 0 (0 = sup[0: / 1(622 (?) = Ш% = t).

о

Очевидно, что имеют место следующие свойства:

а) e(t)t;

–  –  –

СПИСОК ЛИТЕРАТУРЫ

1. Рыбко А.Н. Стационарные распределения однородных марковских процессов, описывающих функционирование сетей коммутации сообщений // Пробл. передачи информ, 1981. Т. 17. № 1.

С. 7 1 - 8 9.

2. Рыбко А.Н. Область пропускной способности для двух классов сетей коммутации сообщений // Пробл. передачи информ. 1982. Т. 18. № 1. С. 9 4 - 1 0 3.

3. Kelly F.P. Reversibility and stochastic hetworks. N.Y.: Wiley, 1979.

4. Massey B. Open Networks of Queues // Adv. Appl. Probability. 1984. V. 16. № 1. P. 1 7 6 - 2 0 1.

5. Kelly F.P. Networks of Queues // Adv. Appl. Probability. 1976. V. 8. № 2. P. 4 1 6 - 4 3 2.

6. Perkins J.R., Kumar P.R. Stable, Distributed, Real-Time Scheduling of Flexible Manufacturing/ Assem­ bly/Disassembly Systems// IEEE Trans. Automatic Control. 1989. V. 34. № 2. P. 1 3 9 - 1 4 7.

7. Kumar P.R., Seidman T. Dynamic Instabilities and Stabilization Methods in Distributed Real-Time Scheduling of Manufacturing Systems//IEEE Trans. Automatic Control. 1990. V. 35. № 3. P. 2 8 9 - 2 9 8.

В.Малышев B.A., Меньшиков M.B. Эргодичность, непрерывность и аналитичность счетных цепей Маркова // Тр. Московского математического общества. М.: Изд-во МГУ, 1979. Т. 39. С. 3 - 4 8.

9. Hutson V.C.L., Рут J.S. Applications of functional analysis and Operators theory. London: Academic Press, 1980.

10. Moustafa M.D. Input-Output Markov Processes // Proc. Konjukijke Netherlands Acad. Netenschappen.

1957. V. 60. P. 112-118.

11. Климов Г.П., Ляху A.K., Матвеев В,Ф. Математические модели систем с разделением времени.

Кишинев: Штиинца, 1983,

12. Dupius P., Ellis R.S., Weiss A. Large Deviations for Markov Processes with Discontinuous Statistics. I:

General Upper Bounds// AT&T-BL Technical Memorandum. Work Project No. 311404-3199. File Case 20878. 1989.

–  –  –



Похожие работы:

«Опубликовано отдельными изданиями на русском, английском, арабском, испанском, китайском и французском языках МЕЖДУНАРОДНОЙ ОРГАНИЗАЦИЕЙ ГРАЖДАНСКОЙ АВИАЦИИ. 999 University Street, Montral, Quebec, Canada H3C 5H7 И...»

«Программные продукты и системы № 4, 2013 г. ПО. Модуль ЦП-РИО-64 позволяет обеспечить Совместное использование известных методов установку двух дополнительных мезонинных моповышения производительности и сбоеустойчиводулей в конструктиве РМС/XMC. сти начальной загрузки с новым способом распреМодуль ЦП-РИО-64, предназ...»

«Информационно-практический ориентированный проект "Здравствуй, Зимушка-зима!" Воспитатель: Бармина Ольга Владимировна пгт. Лучегорск Тема проекта: "Здравствуй, Зимушка-зима!" Информационно-практический ориентированный проект, краткосрочный, групповой. Цель: Расширение представлений детей о зиме.Задачи: По...»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО СВЯЗИ Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования "Санкт – Петербургский государственный университет телекоммуникаций им. проф. М.А. Бонч-Бруевича" Санкт-Петербургский колледж телекоммуникации "...»

«1 м и Ак СКО ПВД 1 5 -2 0 0 -2 0 1 5 НИУ МГСУ Центр образовательных стандартов и программ УМУ Положение о порядке прикрепления лиц для сдачи кандидатских экзаменов к НИУ МГСУ Выпуск 1 Москва 2015 Ус м и и т НИУ МГСУ СК О ПВД 15 2002015 Центр образовательных стандартов и программ УМУ 1М...»

«МИНИСТЕРСТВО ТРАНСПОРТА РОССИЙСКОЙ ФЕДЕРАЦИИ ГО СУ ДА РСТВЕ Н Н АЯ СЛУЖБА ДОРОЖНОГО ХОЗЯЙСТВА (РОСАВТОДОР) ИНФОРМАЦИОННЫЙ ЦЕНТР ПО АВТОМОБИЛЬНЫМ ДОРОГАМ АВТОМОБИЛЬНЫЕ ДОРОГИ ПЛАТНЫЕ АВТОМОБИЛЬНЫЕ ДОРОГИ И ДОРОЖНЫЕ ОБЪЕКТЫ Тематическая подборка Москва 2002 кружевные аксессуары МИНИСТЕРСТВО ТРАНСПОРТА РОССИЙСКОЙ ФЕДЕРАЦИИ ГОСУДАРСТВЕННАЯ СЛУЖ...»

«УЧЕНЫЕ ЗАПИСКИ КАЗАНСКОГО УНИВЕРСИТЕТА Том 157, кн. 5 Гуманитарные науки 2015 УДК 802.0(076) ОПТИМАЛЬНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ ПРЕПОДАВАНИЯ ГРАММАТИКИ АНГЛИЙСКОГО ЯЗЫКА Р.И. Куряева Аннотация Анализ строения английского языка позволил выявить закономерность усложнения английского сказуемого и,...»

«Генеральный информационный партнер проекта Путеводитель автотуриста в Крым для тех, кто не знаком с украинским топливным колоритом (второй выпуск) Информационные партнеры: Это второй улучшенный и дополненный "Путеводитель автомобилиста...»








 
2017 www.ne.knigi-x.ru - «Бесплатная электронная библиотека - электронные матриалы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.