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

• II I

i .) Л 1

■ ■ НОВОСИБИРСКИЙ

ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

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

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

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

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

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

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

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

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

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

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

Москва

Защита диссертации состоится 199 г. в _ часов

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

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

Автореферат разослан "_" '_ 1993 г.

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

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

доктор физико- математических наук сК^к^ а.в.Косточка

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

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

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

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

Публикации Основные результаты опубликованы в работах [1-33.

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

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

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

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

Пусть имеется последовательность (О ;<е[0,13,т>о| случайных О^-значных процессов, траектории которых с вероятностью 1 лежат в пространстве В^Ю, 13 непрерывных справа функций (под К*2 мы понимаем й-мерное .пространство векторов-строк). Процессы Цт(.)} могут быть заданы на разных вероятностных пространствах (П\з\!Рт>. Мы полагаем, что на Пт задана возрастающая последовательность о-алгебр , 4еСО,13 таких, что измеримо относительно

I

4

Пусть £(t), te[0,i]- процесс неограниченной диффузии в О?3 с вектором сноса а=а(х), матрицей диффузии Ъ=Ъ(х) и начальным распределением G0-

Определение (Боровков). С-сходимостъю называется слабая сходимость распределений функционалов /, измеримых относительно о-алгебры, порожденной цилиндрическими множествами и непрерывных в точках Cd[0,13 в равномерной норме. (Здесь Cd[0,1] -пространство непрерывных R*- значных функций.)

с

Эту сходимость мы будем обозначать символом Для произвольной функции и(.) обозначим Au(t)=u(t+A)-u(t). Пусть последовательность измеримых ограниченных

подмножеств таких, что

va ,, где x<=¿* , iiyii<e) -

n n+í и * п а

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

¡PC |(t)&>*nnpH всех í^[0,1 ]}•* 1 при п^со. Пусть.существует последовательность Л=Л(т)=о(1) и система

оьшожеств такая, что при каждых фиксированных п>О,

t<1-A, б>0 на множествах Q* п (*)«■* > при т-»® выполнены условия Р1)-Р5):

Р1) Е^т (Цт (t))=A(a(£T(t))+o(1)),

Р2) E^r(ST(t))* (A£T(t))=A(b(£T(t))+0(1)),

РЗ) Е^т (и A?T(t)»2, » A5T(t)»>S) = о(Д),

где знак * означает транспонирование, а оценки о(1) и о (А) выполнены равномерно по о) и t на множестве fi* n (t)«=

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

d d

J ia{(x)-al(v)l + J lt>lJU)-biJ(u)l< К ii x-y »,

где К =K(^n), x,y ejfn и, кроме того, имеет место неравенство

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

<2

зоО:vu=(u;,...,ud) vx ^ biJ{x)uiUj>c¡w2.

i,J=i

Р5) Множества п^ . л { 11га SUP и£т (*)-£т (t-u)«<8 } t<>-А * иж0 является событиями и 1Р(п Qj )-»1;

1Р( n f 11л sup i^ít)-?'1 (t-u)»<e ))-»1 при т-® .

t UfO

Теорема I. Пусть условия Р1)-Р5) выполнены для последовательности, вида Л;=СА, Се[С,,С2], С;,C2=const>0, а распределение {¡т (0) слабо сходится к распределению ?(0).

т 0

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

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

j л— *

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

величины.

Поведение сети описывается непрерывным справа векторным процессом <аи)= (£},(*),..., <3Н(*)), г >0, где -

длина очереди на ./-ой станции в момент времени t. Мы предполагаем, что последовательности

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

Зафиксируем целое Ь, НЫН, которое будет означать число станций, находящихся в условиях большой нагрузки. Не ограничивая общности мы будем считать, что это станции с номерами 1,...,!. Случай, когда Ь=1 исследован А.Боровковым (1986).

Для ^-мерного вектора г=(г;,...,гв) и матрицы порядка

N"11 (У+1 » »+1) будем записывать

• Г=(ГП>, г<г>);

I? =

11

'21

12

гг

где

г">=(г,,

22

соответственно соответственно). Пусть существует е>0, такое что

,г11), г

матрицы порядка 1*1, Ъ«Н-Ъ, Я-1*Ъ, (порядка 1*1, £»#+1 -X,

Ч аир Е (г1." (Т) зир 1Е (э$'} (т) )*+й<«>.

т * ■ . т 3

■ Обозначим '

а3 (т)=(Ее]' > (Т) Г', (Т (Т )ГОа< ° (Т), ./=0,... Д, а(Т)=(а,(Т),...,а„(Т)), А(Т)=й1ав(А,(Т),...,Ав(т)),.

а=(а,,...,ан), А=с11ав(А;,... ,АК), где а^>0, А^О - некоторые константы.

Обозначим рзь= 04 ^п>= Ь, }, Р=ир^я, J,k= 0,...,#.

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

л

Матрицу Р = и PlJ *, 1,^0,... ,1 определим равенством Р|.+ Р.2<1-РггГ'Рг|, а через чс' обозначим вектор ее стационарных вероятностей.

Обозначим ср0 = (-р01,...,-р011),

Ф, =

% = .....-Ръ-иъ^-Ры?-

Определим Ъ- мерный симплекс

Э = К1: .1,2:0 ; г^ + .-.+г^ >.

Пусть x{t)-(xt(t),>..,xL(.t)), ¿е[0,1] - непрерывная справа и имеющая предел слева функция (элемент пространства Скорохода ГО^СО.П) со значениями в В?1 такая, что х(0)е5.

Обозначим

«^'[0.11 = I у = Уь) * Ш^'ки 1: у(0) = 0 и все

у0..... уь - неубывающие функции на [0,13 ).

Тесрвш 2.

1 Щя любого ф^ь[0,13 существует уеЯ?1*'10,1) танос, что

V ию,13 х(г) + 2 Уж(*е 8.

ъ

V

¡=о

2) Среди всех у е шь+ '[0,11. удовлетворяющх 1), существует единственное наименьшее $ {мы полагаем )).

3) Точки роста функции £>0(-) принадлежат множеству

ь ь

к=1 ¿=0 а точки роста функции §к(.) - тожеству ь

{ г : Едг<*)+ £ ^ЫфД =•■ 0 }, и=г.....Ь.

4) Свойством 3) обладает только 5) Отображение

ъ .1=0

непрерывно в ¡О1,[0,11 б равномерной метрике.

Теорема 2 решает так называемую проблему Скорохода для многомерного симплекса и заданных направлений отражения. В работе Харрисона и Раймана (1981) проблема Скорохода была решена для области вида и для направлений отражения, являющихся строками матрицы щ, где I - единичная матрица, а н - полу стохастическая со спектральным радиусом строго меньшим 1. В работе Чена и Мандельбаума (1991) утверждалось (со ссылкой на неопубликованную работу), что подобный результат имеет место в случае, когда н - неправодимая стохастическая матрица, а х{.) принимает значения на гиперплоскости íx)+...+xN=^) и непрерывна, либо имеет ограниченную вариацию. Исходя из такого утверждения доказывалась диффузионная аппроксимация для замкнутых сетей.

Определение. Пусть С(*). "£<=[0,1], - диффузионный процесс в К1, с начальным значением в б. Назовем процесс т)(*)=/(£(.))(*), 1е[0,1], диффузионным процессом в Б с отражением от гиперплоскости 1х: х}+.....хь = 1 > с направлением отражения ф0 и от

гиперплоскостей íxJ = 0 } с направлениями отражений ф^, ^=1,..., I, соответственно.

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

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

ф(х,х,Н) = Н*(Х-сИа8Х)Н-нй1аб(гН).

Пусть С(*)] - диффузионный процесс в К1, с вектором сноса Х=тс'вЬ(р-1), матрицей диффузии

Л = ф(а0,А0,Р^Ъ + А„ + .ф(схп\Ап,р) - А,,Р - А*,Р*, где ао>0, Ао^0 - некоторые константы, и начальным распределением б0в Б. Обозначим

= /(с(.)>(«}, о

<3(*Т2)

Обозначим

т

Теорема 3. Пусть при Т-® имеет лесто сходимость

а(Т) - а, А(Т) - А, а0(Т) - а0, АС(Т) - Ар,

. а,(т) а0(Т) 1

%j % aj(T) а0(Т)

bj, при J=1,...,L;

£ eo>0 при /=1+1,..

и, кроле того

P ( QiiilO) 6 . } . Gn(.) , 1 0 npu T-.

T 0 T

о

Тогба g(.) £(..) при T-»®.

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

и одинаково распределены. После окончания n-го по счбту обслуживания на J-ой станции вызов, обслуживание которого завершено, направляется на станцию с номером vjnie{0,1 , ...,Ю где независимыэ и Для каждого J одинаково распределанные случайше величины. Случай О означает, что вызов покинул сеть.

На станции с номерами Je з s {1,...,Ю в моменты,времени поступают вызовы. Случайные величины , J* з незави- -

J TV— |

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

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

Q (t)= Q (t+0)="(Q, (*),..., Qj^it)), t > О,

где Qj(*)- длина очереди на J-ой станции в момент, времени t. Мы предполагаем, что последовательности

не зависят друг от друга и от вектора Q(0). Обозначим р = [PC fe }, P=»PJl511,

Пусть вероятности р.. таковы, что каждый вызов с вероят-. j«

ностью 1 покидает сеть. Это эквивалентно тому, что спектральный радиус р строго меньше 1.

Пусть снова L означает число станций, находящихся в условиях большой нагрузки. Случай, когда 1=1 исследован в Боровко-вым (1986), а когда I=N - Райманом (1984), Анисимовым и Чабаню-ком (1988) при несколько различных условиях. Когда настоящая работа была закончена, автору стали известны результаты Чена а Мандельбаума (1991), где было получено аналогичное утверждение. Не претендуя на приоритет, мы приводим теорему 4 для полноты изложения. ■ . •

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

vy-sup Е(х^,:>(Т))2+е<со, sup Е(з'и(Т))2+е«х>. т J , т • »

Обозначим "

af(T)=(IETj'-,(T)r.,,.AJ(T)=aJ(T)IDxj',(t), 3, aJ(T)=AJ(T)=0, J* з,

= >(T))-', Kj(T)=tlJ(T)IDeJn(T). J= 1.....IT,

a(T )= (a, (T).....с^(Т)), ц(Т Ыц, (T).....М*<Т)),

А(Т)=сШ1в(А,(Т>,...,А„(Т)), М(Т)= diag- (М;(Т),...,Mff(T)),

7=7(Т)=а(Т)(1-Р)-,>

где diag Сг,,... ,xv) означает диагональную матрицу порядка NxN с

элементами x1f... ,xv.

Пусть а, (ЫК^, b(n<áR2* - некоторые векторы, А, М - матрицы порядаа N*N, Gq- распределение в [R^, а

t,(n= í(n{t), UÍ0,1] -- диффузионный процесс в (R^ с вектором сноса

1-р1ГР12(1-Р22г>Р2,),

матрицей диффузии

Z= А,, + М„ - М,,(РП + Р,2(1-Р22) 'Рг>) -- (Р,, + Р)2«-Р22Г'Р2)>Х| + Ф(|АГ2,.Аг2,(1-Ргг)~'Рг,). матрицей отражений

1-Е = I - Р,, - (Р,г< I- Р22)~'Р2,) и начальным распределением go.

ПОЛОЖИМ Sí2;)= £í2,(t) = 0е К®"1, íe[0,1],

5= 5(*)= tt(n(t),£(2}(t)) , МО,11.

Обозначим g(t) = gT(t) = Q(tT ) , íe[Otn.

Т

Теорема 4. /Тусшь ц(Т)-»ц, а(Т)->а, М(ТЬМ, А(Т)-> А, T(Tí':'(T)V,(T)bb<'',> 7j(T)-Hj(T)í-so<0 /=1+1,... Д,

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

q(2)(0) 5 о при т-**>. Т

о

Тогда д(.) =» при т-оо.

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

Пусть имеется N станций. На станцию с номером J, J=1,...,N

в моменты времени J(T), •xj,,(T)+tj2,(T),... извне прибывают вызовы, которые становятся в очередь. В сети имеется один об-служшзатель, который движется по траектории (v^-номер

станции, посещенной n-й по счету). Если vn_f=i, vn-J, то переход между станциями занимает время после чего в течении . времени. обслуживается один вызов из имеющихся на станции, . либо (если станция пуста ) обслуживатель продолжает свое движение, не'задерживаясь на ней.

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

(1) с-Й'а.»^,, I. 1.....ff

независимы в совокупности и в каздой из 2N?+N последовательностей (1) одинаково распределены, образуют цепь Маркова с матрицей Р=«р.,»^ ,_, и не зависят от.(1), а вектор Q(0) не

» J ■ I <7— •

зависит от управляющих последовательностей.

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

Пусть зе>0 sup ¡Цх(,п(7))г*е«^. sup Eieil'd))8*8«*,

т * т J

sup еЦ^Хт)^8«», I, и.

Обозначим .

а^(Т) = [Еа<°(Т)Г\ AJ(T)=.aJ(T)IDi:_j'>(T), Мт) = Е В(Т) = «-ptJ(T) , ;

Т«,(Т) = ».»{J'iT). Г(Т) - . TiJ(T) ,

■ e„(T)--Еву>ст),.е(т) - I e4i(T>i4»ie,

f«jlT) = ю в[у(Т). К(Т> = .» а„(Т) ,

1,3=1

Мы предполагаем, что при Т-да V/ (2) о,(Т> - а3 , А,(Т> - AJ , В(Т) - В ,

Г(Т) - Г , 6(Т) - 6 , К(Т) - К . Положим г= 2яР®(В+6) (1-Р+П)~'р®(В+6)е*+ + яр®(Г+К+(В+9)®(В+е))е* - Зяр®(В+9)П р®(В+9)е* , где е=(1, — ,1).

и

v = £ I *1Ри<Рч+вч>г'' Л, = V 2

1,3=1 Ъ=1

Л^ = { 1Г{[(1 -р+П)-']^ + * [(ц»+пг']л - - К^з +

+ + А48{>, ,

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

,... Дн) - некоторый вектор из К27.

Пусть £ и )Де[0,1 ] - диффузионный процесс в к" с отражением от границ с начальным распределением в0, вектором сноса А,, матрицей диффузии Л и матрицей отражений 1-Г. Обозначим

д (*) ---, ^[0,1].

Т

Теорема 5. Пусть выполнены условия (2) и, кроле того

V Т Га,(Т) - Ц,(Т)] - Идт(0)е . } в0(.) при т-о. т о Тогда д (.) -» £ (.) при

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

которые не включены в диссертации по соображениям, связанным с ее объемом.

Автор признателен А.А.Боровкову за введение в интересную область исследований, постановки задач и внимание к работе и Д.А.Коршунову за полезные критические замечания."

Публикации автора по теме диссертации: [1 ] Сафаров М.М. Предельные теоремы для сетей обслуживания с многоканальными станциями. Проблемы, передачи информации. .1991, том 27, вып.3, стр.95-101. [2] Сафаров М.М. Теорема сходимости к диффузионным процессам. Диффузионная аппроксимация процесса очереди в сети с, одним обслуживателем. Доклады Академии Наук, 1993, том 330, №1, стр.17-19.

[31 Сафаров М.М. Диффузионная аппроксимация для замкнутых сетей обслуживания. Препринт ИМ СО РАН, 1993, Ш, 42 стр.

Подписано к печати 8.10.93

Формат бумаги 60x84 1/16. Объем I п.л.

Тираж 100 экз. Заказ 8£.

Отпечатано на ротапринте Института математики СО РАН 630090, Новосибирск-90