Предельные теоремы о сходимости к многомерным диффузионным процессам и их приложения к сетям обслуживания тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ

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

•У \

<3

> САФАРОВ МАРАТ МАСУТОВИЧ

/

ПРЕДЕЛЬНЫЕ ТЕОРЕМЫ О СХОДИМОСТИ К МНОГОМЕРНЫМ ДИФФУЗИОННЫМ ПРОЦЕССАМ И ИХ ПРИЛОЖЕНИЯ К СЕТЯМ ОБСЛУЖИВАНИЯ

01.01.05 - теория вероятностей и математическая статистика

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

Новосибирск -1995

Работа выполнена в Новосибирском государственном университете.

Научный руководитель - академик А.А.Боровков

Официальные оппоненты - доктор физико-математических

наук, профессор Б.А.Рогозин, кандидат физико-математических наук Д.А.Коршунов

Ведущая организация - Институт проблем передачи информации, Москва

А А'^Г-у. в

......... - ..... .....

Защита диссертации состоится

часов на заседании специализированого Совета Д 002.23.03 в Институте математики СО РАН ( 630090, Новосибирск, Университетский проспект, 4, Институт математики СО РАН ).

С диссертацией можно ознакомиться в библиотеке Института математики СО РАН.

Автореферат разослан "/^ "

Ученый секретарь специализированно доктор физико- математических наук А.В.Косточка

специализированного совета Д 002.23.03 ,

I /

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность теми. Диффузионная аппроксимация процесса длиш очереди в системах и сетях обслуживания является важным инструментом их исследования и позволяет приближенно рассчитывать их численные характеристики. А.Боровковым были сформулированы и доказены достаточные условия С-сходимости к одномерным диффузионным процессам . в терминах сходимости условных относительно предыстории моментов приращений на множествах, вероятности которых близки к 1. Эти условия достаточно просто проверяются в конкретных системах обслуживания. Представлялось полезным перенести эти результаты на многомерный случай в несколько более общей формулировке, допускающей нелинейный рост по х вектора сноса и матрицы диффузии. В качестве приложения исследованы сети джексоновского типа и поллинг-системы в условиях большой нагрузки. Диффузионная аппроксимация процесса длины очереди в таких системах представляет * самостоятельный интерес.

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

Научная новизна. Все результаты являются новыми. Практическое знача н и е . Результаты работы имеют как теоретическое, так и практическое значение и могут служить основой для расчета численных характеристик ком-муникационг'х систем и сетей обслуживания.

Апробация.работы . Результата работы докладывались на заседаниях семинара по теории вероятностей ц математической статистике Института математики СО РАН, на конференции по теории вероятностей в г. Бакуриани ( Грузия ) в 1990г., на семинаре по системам обслуживания в г. Киеве ; Украина ) в 1991 г., в Национальном Институте по информатике и автоматизации 1ГО1А в г. Роконкур ( Франция ).

Публикации. Основные результаты опубликованы в работах 11-3].

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

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

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

В первой главе исследуются достаточные условия С-сходимости последовательности непрерывных справа процессов к многомерному процессу неограниченной диффузии.

Пусть имеется последовательность (* );1<г[0,1) ,т>о| случайных К^-значных процессов, траектории которых с вероятностью 1. лежат в пространстве 0^(0,1] непрерывных справа функций (под мы понимаем с1-мерноа пространство векторов-строк). Процессы {?*(.)) могут быть заданы на разных вероятностных пространствах (0Т,3Т,1РТ). Мы полагаем, что на Пт задана возрастающая последовательность о-алгобр , [0,1 ] таких, что £т(г) измеримо относительно у* .

Пусть |(t). í^to,1]- процесс неограниченной диффузии в Kd с вектором сноса а=а(х), матрицей диффузии Ь=Ъ(х) и начальным распределением GQ.

Определение (Боровков). Мы будем говорить, что последовательность процессов £т(.) С-сходится к процессу £(.) и записы-

Т ° ri

вать £ (.) -♦> £(.), если для любого функционала ф:0Г L0.1 ЫК, измеримого относительно о-алгебры •$, порожденной цилиндрическими множествами и непрерывного в точках Cd[0,1] в равномерной норме имеет место слабая сходимость распределений

(P«p(ST (. ))<х> * Р{ф(5(.))<х) при Т-оо. (Здесь <Ed[0,1] есть подпространство пространства Fd[0,1l, состоящее из непрерывных И^-значных функций на 10,11).

о

Эту сходимость мы будем обозначать символом 'V.

Для произвольной функции у(.) обозначим Aftu(t)=t>(t+M-u(t).

Пусть t-»* >™=>- последовательность измеримых ограниченных подмножеств Kd таких, что

vrc эе>0:^е£^ ,, где ^£={х+у. х, iiyn<e} -

n n+1 ' п " гг й

- е-окрестность множества ¿и таких, что

04 При ВСеХ г<=[0,Ш- 1 При Я-оо.

Пусть существует последовательность h=h(T)=o(1) и система w-множеств П^з* такая, что при каждых фиксированных гг>0, 5>0 на множествах П^ n {и:£т (t Je^} при Т-"» выполнены условия Р1)-Р5):

Р1) EgT (¿h£T(t)) = h- (a(|T(t))+o(1)),

Р2) IE^t(AfcET <*))*CAfceT (*)> = h- (b(ET(í))+o(D),

РЗ) (Е^Т (« Длет )и2, I ДН!Т(*)И>6) = ПО( 1),

где знак * означает транспонирование, а оценки о(1) выполнены равномерно по и и { на множестве п {ы: £т (О« •»О.

Р4) Прй кавдом п а{.) и Ь(.) удовлетворяют условию Липшица

^ |а((®)-at(y)I + ^ |b{J(i)-btJ(v)|< К « х-у н.

* \ Iii 1г\-П <„\ |

4=1

где К =K(j*n), х,у и, кроме того, имеет место неравенство

(условие равномерной эллиптичности)

Jiu«2.

эсо>0:Уи=(и),...,и£г) *х и

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

Р5) Множества п • П { lim вир ii£T (t (t-u)n<ö ) tí» * и*+0 являются событиями и (Р(п П^ Ы;

t<»

IP( п <- Ilm sup ii£T (t)-£T (t-u)»<ö при T*® .

t w*0

Теорема I. Пусть условия P1 )-P5) выполнены равномерно по С для любой последовательности вида ht=Qh, (MCj ,C2J, Cj,C2=const>0, а распределения векторов С (О) слабо сходятся к распределению вектора £(0). .

т с

Тогда i (.) -> £ (.) при, Т-«.

Во второй главе рассмотрены замкнутые сети обслуживания, которые функционируют следующим образом. Имеется зависящая от параметра т последовательность систем //И одноканальными станциями. занумерованными от 0 до N. В системе постоянно находятся Т вызовов. На каждой станции вызовы обслуживаются в порядке поступления (дисциплина обслуживания FIFO). Времена обслуживания на J-1L станции J=0,...,N независимы и одина-

J п= I

ново распределены. После окончания п-го по счёту обслуживания на J-ой станции вызов, обслуживание которого завершено, направляется на станцию с номером 0,...,Ю, где независимые и для каждого J одинаково распределённые случайные ' величины.

Мы предполагаем, что последовательности

j п=1 J

не зависят друг от друга и от вектора Q(О).

Поведение сети описывается непрерывным справа (.векторным

процессом Q(t) = Q(t+0)= (Q,(t).....Q„(t)), t>0, где Qj(t) -

длина очереди (число вызовов) на J-o.i станции в момент времени t.

Зафиксируем целое L, которое будет означать число

станций (помимо станции с номером 0), находящихся в условиях большой нагрузки. Не ограничивая общности мы будем считать, что

это станции с номерами 1,___,L. Случай, когда 1=1 исследован в

[71.

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

Пусть ]=0 - неприводимая стохастическая матрица.

Обозначим ф0(н) = (~П01.....-/гоь).

Ф,(Н) = (1 -Гг, (,-Л)2,...,-Гг(Х),

ч>ь<н) <А».....

(Векторы ф^(Н) - строки матрицы 1-н с вычеркнутым первым столбцом, где I - единичная матрица размеров £л1). Определим Ь- мерный симплекс

Б = (х е К1; х,£0.....хтгО ; >.

• XI Г II

Обозначим через (^СО.П пространство непрерывных справа и имеющих предел слева [^-значных функций на [0,1] ( пространство Скорохода).Через (иь+| [0,11 обозначим подмножество ^'[О.П, состоящее их функций у=(у0,..., уь) таких, что у'(0)=0еК1'+' и

все у0.....у - неубыващие функции на [0,1 ].

Теорема 2.

1) Для любого ллеЦ)1*С0,13 такого, что х(0)е8 существует уеШ^'Ю.И такое, что

ь

0,1] ^ yJ(t)<pJ(H) ^ в.

J=o

2) Среди всех * £0,1], удовлетворяющих 1), существует

единственное наименьшее

§ = = (9<».Н.8>(>).....^.Н.З,^^

(мы полагаем у'<у"«*г,,/ у]и)%^и)).

3) Точки роста функции §(0Х,Н'5у(.) принадлежат множеству

ь ь

{г.: I Сл?(*)+ -1 ='1 >,

к=1 3=0

а точки роста функции §[я'н'3)(.) - множеству

{ t : Сг(«)+ £ 9^'н'3,(1)<р_/(Н)]1г = 0 }, й=1.....1.

J=0

4) Среди всех уеф*1[0,11, удовлетворяющих 1), свойством 3) обладает только р(х'н,5,(.).

5) Отображение

ъ

/=/н>3:х(.) - х(.)+ I 9},,н"в,<.)<Р,<Н)

непрерывно б В)1,С0,1] б равномерной метрике.

Теорема 2 решает так называемую проблему Скорохода для многомерного симплекса и заданных направлений отрахения.

Определение. Пусть {«10,13, - диффузионный процесс в

К1, с начальным значением в Б. Назовем прочее Т1(*)-/Н д(С(.))(*), tetO.il, диффузионным процессом в Б с отражением от гиперплоскости {х:х(+..=1) с направлением отражения Ф0(Н) и от гиперплоскостей с направлениями.., отражений Ф^ (Н), Ь, соответственно.

Для //-мерного вектора г=(г ,... ,г№) и матрицы я порядка Я* Я. (А"+1 « №И) будем записывать

1? =

21

' (2

22

где

.....Гь), гг2;=(г

а 1?)2, Р2), Я22 - матрицы порядка 1*1, I*?/-!,, Я-1*Ъ, Я-Ь*Я-Ь соответственно (порядка Ь<1, Ь*№+1-Ь, N+1-1*1,

I,

1-I» №+1-Ь соответственно).

Пусть существует £>0, такое что V/ вир Е(з^',(Т))2+е<оз.

т ^

Обозначим

сут)=(Ез^';(Т)Г\ А^СТ^аЛПэ^^Т), №.....N.

а(Т)=(а,(Т).....сут)), А(Т )=й1аб(А,(Т).....АЯ(Т)),

а=(а(,...,аи), А=с11а£(А;,... где а^>0, Ау0 - некоторые константы.

Обозначим pJ}¡= (Р{ у'п)= й }, Р^'Р^«. J.k= О,

Мы предполагаем, что матрица р неприводима и :.э зависит от Т. Через %={%,...,обозначим вектор вероятностей инвариантного распределения, соответствующего цепи Маркова с матрицей переходов р.

Матрицу р = и ри, = О,...,Ь определим равенством Р= Р|)+Р|2(1-Р22)-'Р2(,

а через тс' обозначим вектор ее стационарных вероятностей.

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

Определение. Для вектора х размерности п, матрицы X порядка пхп и матрицы н порядка п*т положим

ф(х,х,Н) = Н*(Х-й1а&т)Н+й1а8(.-гн).

Пусть си),£е[0,1] - диффузионный процесс в с вектором

сноса \=ic'®b(p~i), матрицей диффузии

Л = ф(а0.А0,р£иГ+ А() + (|)(а('' ,Р) - А,,Р - А*,Р

(П

I* Г*

I г

где ао>0, Ао>0, - некоторые константы, Ь=(Ь>,... ,Ьь)еО}ь - некоторый вектор и начальным распределением в0в Б. Обозначим = /?,3(С(-))(*). {гг,{»)в о « к""1,-КО = (5П,(«).{<2,(0). iei0.1l.

Обозначим

q(t) =

Q(tT2)

Теорема 3, Яусть при т ■» 00 имеет место сходимость

а(Т) - а, А(Т) - А>0, а0(Т) - aQ, А0(Т) - А0,

<УТ)

а0(Т)

- b , при J=1

о

> eQ>0 при /=1+1.....W.

и, кроле того

р f QiliiO)

) G0(.), vS)>0 (PC

>Ej } - О при T"-»<*>.

T " ' T

с

Тогда q(.) £(.) при т-®.

Во третьей главе рассматривается занумерованная параметром Т последовательность открытых сетей обслуживания с однока-нальными станциями. На каждой станции вызовы обслуживаются в порядке поступления (дисциплина обслуживания FIFO). Роемена

обслуживания Csjri')(T)>^( на J-Si станци.. J= 1.....N независимы

и одинаково распределены. После окончания n-го по счёту обслу-

живания на J-ой станции вызов, обслуживание которого завершено, направляется на станцию с номером vjn,e{0,1,...,N) где независимые и для каждого J одинаково распределённые случайные величины. Случай vjn,= 0 означает, что вызов покинул сеть.

. На станции с номерами J« 3 s <1,...в моменты времени f(jn(Т), г/"(Т)+ tj2,(T),.• • поступают вызовы. Случайные величины . J« 3 незави-

симы и для каждого J«3 одинаково распределены.

Поведение сети описывается непрерывным справа векторным процессом

Q (t)= Q (t+0)= (Qf(t),..., QK(t)). t * О, где Qj(*)~ длина очереди на J-ой станции в момент времени t.

клы предполагаем, что последовательности

не зависят друг от друга и от вектора Q(0).

Обозначим DP{ к }, P='PJh>, J,k= 1.....Н.

Пусть вероятности р таковы, что каждый вызов с вероят-ностыо 1 покидает сеть. Это эквивалентно тому, что спектральный радиус Р строго меньше 1.

Пусть снова I означает число станций, находящихся в условиях большой нагрузки.

Предположим, что

vj аир Е(а^,;(Т))2'е«», sup Е(з^'-'(т))2+е<ш. т 3 т 3

Обозначим

CLj (T )= (Etj'J(T )'» А^Т)=а*(Т)Шт<"(Т), > 3, а^(Т)=А^(Т)=0, HJ(TMEej',(T)r\ Н^ (T (T ' }iT), J-1.....1T. a(T)=(al(T),...,aJ/(T)), Ц(Т)=(Ц, (T),..., pN(T)).

A(T)=diag(A>(T),...,Aw(T)), M(T)= dlag (M,(T).....H/T)).

7=Т(Т)=а(Т)(1-Р)"'.

где dlag (лг(.....xfí) означает диагональную матрицу порядка N*N с

элементами xf,...,х

Пусть а, b'^eR1, - некоторые векторы. А, Н - матрицы

порядка NxN, G0~ распределение в R^, а

Ín)(t), UIO.U -- диффузионный процесс в ff^ с вектором сноса

2= й'"(1-Р|ГР|г( I- Р22Г'Р2,). матрицей диффузии

Z= А„ + М„ - М„(Р„ + Р|2(1-Ргг)-'Р2|) "

" (РМ + Р»2(1_Р22Г'Р2Г)Х1 + <KlAÍ'!f,»A22,(I-P22)"'Pa|).

матрицей отражений

1-Е = I - Рм - (Р,2( I- Р22Г'Р2()

■ и начальным распроделешем G0.

ПОЛОЖИМ i(2}= i<2)(t) з О е [Rí'-L, íeto.1],

е= t(t)= (i('}(t),z(2}(t)) , t«[o,n.

Обозначим q(t) = qT (t) = Q(tT } , íe[0,1].

T

Теорема 4. Дуешь ц(ТЬр, a(T)-xx, М(Т)-»М>0, А(Т)-* А>0, Т(7П ,(TH'",(T))-»bí'\ Jj (Т (Т )s-eo<0 J=X+1,...

' (01

распределение случайной величины. --—' слабо сходится к G0, а

°(2)(0) ? О при Т-ко.

Т

о

Тогда <?(,) •♦£(.) при т-«».

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

В четвертой главе рассматриваются так называемые поллинг-системы, функционирующие следующим образом. Имеется ¿V станций. На станцию с номером J,J=^, в моменты времени

>(Т)+1^2){Т),... извне прибивают вызовы, которые становятся в очередь. В сети имеется один обслуживатель, который движется по траектории (г^-номер станции, посещенной п-й по сче-

ту). Если V =1, vn=J, то переход между станциями занимает время после чего в течении времени обслуживается

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

Мы будем предполагать,что случайные величины

(I) Цги(т)Г=}, ЧТ(Т)С<' 1..Н.....*

независимы в совокупности и в каждой из №+2Н последовательностей (I) одинаково распределены, образуют цепь Маркова с матрицей р='р.. , и но зависят от (I), а воктор 0(0) не зависит от управляющих последовательностей.

Мы предполагаем, что матрица р неприводима, непериодична и не зависит от Т. Обозначим через %=(% ,...,% ) вектор ее

стационарных вероятностей.

Пусть зе>0 вир ¡Е(а(°(т))г+е<®, вир Е(а'°(Т))2,е<<»>,

т ■' т

вир СЦ'/ИТ)2'6«». £,/=1.....N.

т '

Обозначим

о,(Т) => ИЕх<1}{Т)Г1, А^Т)= а^тту^т),

Ри(Т) = В(Т) = • Ри(Т) .

Ти(Т) =Ю<|'(Т), Г(Т) = « Ти(Т) .

в«/Т)=Е8;"(Т), 6(Т) = < 9и(Т) .

«и<Т> К(Т) = . аеи(Т) * .

N

Мы предполагаем, что при Т->® чJ (2) а^ (Т) -'а, , А^Т) - , В(Т) - В , Г(Т) - Г , е(Т) - 0 , К(Т) К . Положим 2ир®(В+в) (1-р+П)~'р®(В+е)е*+ + ир®(1ЧК+ (В+0)®(В+О) )е* - Зяр®(В+0)П Р®(В+0)е* , где е=(1.....1), а знак "*" означает транспонирование,

II N

4=1 I Л, = V I

= {тс^а-р+п)_,1и + и-р+пг1^ - - %1%3 }-у +

+ + ,

где - есть символ Кронекера, I,}

Л.= (Х(,... некоторый вектор из к".

Пусть £(О,4е[0,1] - диффузионный процесс в К^ с отраже-

нием от границ с начальным распределением в0, вектором сноса матрицей диффузии Л и матрицей отражений 1-г. Обозначим

0Тит2)

<7 (*) = ------ , {«[0,11.

Т

Теорема 5. Пусть виполнет условия (2) и, кроле того Т Га,(Т) - - Р{<2Т(0)« . ) 60(.) при Т-».

т О

Тогда д (.) •* £(.) при т-.®.

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

Автор признателен А.А.Боровкову за введение в интересную

область исследований, постановки задач и внимание к работе и

Д.А.Коршунову и Б.А.Рогозину за полезные критические замечания.

Публикации автора по теме диссертации:

Ш М.М.Сафаров, Предельные теоремы для сетей обслуживания с многоканальными станциями. Проблемы передачи информации. 1991, т.27, вып.З, 95-101.

[2] М.М.Сафаров, Теорема сходимости к диффузионным процессам. Диффузионная аппроксимация процесса очереди в сети с одним обслуживателем. Доклады Академии Наук, 1993, том 330, №1,

17-19.

Г3] М.М.Сафаров, Диффузионная аппроксимация для замкнутых

сетей обслуживания. Препринт ИМ СО РАН, 1993, #2, 42 стр.