Исследование условий существования стационарного режима в сетях связи с h-настойчивым доступом

А.А. Назаров, М.А. Никитина

ИССЛЕДОВАНИЕ УСЛОВИЙ СУЩЕСТВОВАНИЯ СТАЦИОНАРНОГО РЕЖИМА В СЕТЯХ СВЯЗИ С А-НАСТОЙЧИВЫМ ДОСТУПОМ

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

Исследованию сетей связи с протоколами случайного множественного доступа с оповещением о конфликте посвящено большое число публикаций, например [1-3]. Одной из основных задач исследования является проблема существования в них стационарных режимов [4, 6]. В данной работе рассмотрены сети связи, управляемые протоколами й-настойчивого доступа с непрерывным и дискретным контролем сигнала оповещения о конфликте. Так как в таких сетях канал связи совместно используют все абонентские станции, которые могут осуществить передачу в любой момент времени, то возможно совпадение времени передачи сообщений нескольких станций, при этом сообщения искажаются (попадают в конфликт). Все сообщения, попавшие в конфликт, передаются повторно. Для избежания искажения других сообщений распространяется сигнал оповещения о конфликте. В сети связи с непрерывным контролем сигнала оповещения о конфликте после его окончания все абонентские станции, отправившие за это время свои сообщения в сеть, сразу же делают попытку повторной передачи. Если после этого сообщение попало в конфликт, то оно с вероятностью й передается повторно, с вероятностью 1-й теряется. В сетях связи с дискретным контролем каждое сообщение, поступающее в сеть на этапе оповещения, с вероятностью й передаётся повторно, а с вероятностью 1-й теряется.

Математическая модель сети связи с А-настойчивым протоколом

случайного множественного доступа с непрерывным контролем сигнала оповещения о конфликте

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

мя, распределенное по экспоненциальному закону с параметром ст. Состояние системы определим вектором (к, і, у), где

1) к - состояние канала: к=0 - прибор свободен; к=1 - прибор занят обслуживанием заявки; к=2 - в системе реализуется сигнал оповещения о конфликте;

2) і - число заявок в ИПВ;

3) если к=2, то ] - число заявок в очереди, если к^2, то компонента ] не определяется.

Процесс {к(0, і(0, _/'(/)} изменения во времени состояния системы является марковским.

Существование стационарного режима

в сети связи с непрерывным контролем сигнала оповещения о конфликте

Для нахождения условия существования стационарного режима для данного марковского процесса построим модифицированную модель. Те заявки, которые в исходной модели должны попасть в конфликт (находящиеся в очереди), принимают решение о повторении попыток обслуживания не в момент конфликта, а в момент своего поступления в систему. При этом такие заявки могут вновь обратиться к прибору на этой же фазе этапа оповещения и с вероятностью 1-й покинуть систему, что исключается для исходной модели, пока заявка находится в очереди. В условиях большой задержки (а именно в этих условиях будет проводиться исследование рассматриваемой модели) вероятность повторного обращения к прибору одной и той же заявки в течение одного этапа оповещения о конфликте стремится к нулю. В этом смысле модифицированная модель эквивалентна исходной. Тогда компонента к принимает следующие значения: к=0 - прибор свободен, к=1 - на приборе идет обслуживание. На этапе оповещения будем различать три состояния канала:

к=20 - в очереди нет заявок;

к=21 - в очереди одна заявка;

к=22 - такая фаза этапа оповещения о конфликте, после окончания которой опять начинается этап оповещения. Процесс {к(ї), і(ґ)} является цепью Маркова с непрерывным временем. Модифицированная модель гораздо проще исходной, так как ее функционирование определяется ленточным графом.

Эргодичность случайного процесса полностью определяется [5] эргодическими свойствами вложенной в него цепи Маркова при условии конечности средних времен пребывания в состояниях процесса.

Пусть 4 - моменты времени, непосредственно следующие за изменением состояния прибора или поступлением заявки на этапе оповещения о конфликте. Процесс с дискретным временем {к(4), і(4)} является вложенной цепью Маркова для процесса {к(0, /'(/)}. Вероятности ди,,(кД перехода за один шаг из состояния (п,і) в состояние (ку) имеют вид:

Чо.

,(1,і)=\в~ia,d (1-в^' )=

X

;

X + іст іст

X + іст

ди

0

дм (20, і +1) = | в-х‘в-цtd(1 - в-ст'-

0

ОТ

ди (20, і + 2) = | в-гстtв-цtd(1 - в^'-

ц

0

ОТ

д20, (21, і +1) = | в-(Ц1 +іст)íd(1 - в-х'-

X + іст + ц іст

X + іст + ц

X ;

X + іст + ц’

X

X + іст + ц1

д20,і (21, і) = | вЧЦ1 +X)td(1 - в-іст'-

0 ОТ

д20 і (0, і) = | в-(X+гст)td( - в-ц')---------------------Ц1-------

0 а + іст + ц

X + іст + ц1

д 21,і(1, і -1) =

д 21,і (22, і +1) =

д 21,і(22,і)=

ц1

X + (і - 1— + ц1 ’ Xй2 ;

X + (і - 1)ст + ц

(і-1)ст -й1 +

X

X+(і - 1)ст+ц

д 21,і(22, і -1) =

X+(і - 1)ст+ц

(і - 1)ст

2й(1-й);

X + (і - 1)ст + ц

X Л , \2

2й(1 - й) +

X + (і - 1)ст + ц

(1 - й)2

д 21, і(22, і - 2) = т—,(. 1)---------------------(і- й)2;

X + (і - 1)ст + ц Xй

д 22, і (22, і +1) =

X + іст + ц1

ч X(1 - й) істй

д22,і (22,і) = " +

д 22, і (22, і - 1!) =

д 22, і(20, і) =

X + іст + ц1 X + іст + ц1 іст

X + іст + ц1

ц1

ЕЕ?»,/

к=1 Л=0

^ да ____

ЕЕ?»,/

к=1 Л=0

При этом существует единственное эргодическое распределение, совпадающее со стационарным».

Условие (2) выполняется всегда, так как в суммах (2) конечное число слагаемых. Условия (1) для рассматриваемой модели имеют вид системы пяти неравенств:

х (/)+—^—Х1 (/ -1) - Хо(/) - -е;

Х+/ст Х+/ст

^ /ч /СТ 1Ч

-Хо(/) +"—:-----Х2о(/ +1) +

X+iст+ц X+іст+ц

X

X + іст + ц

Л-20 (і + 2) - хО ) <-е ;

----------;-------------Хц (і + 1) + ------------------------ц------------------------Хд (і) +

X + іст + ц1 X + іст + ц1

іст

X+іст+ц1

Хц (і) - хм(і) <-є;

Xй2

X+(і - 1)ст+ц^

'Хц (і +1) +

(і -1)стй

X+(і - 1)ст+ц

X2й(1-й) X+(і - 1)ст+ц

Х22 (і) +

+ (і-1)ст2й(1-й) X+(і - 1)ст+ц

х х22(і - 2) +

X(1-й)2

X+(і —1)ст+ц

х22 (і —1) +

(і-1)ст(1-й)2 X+(і —1)ст+ц

ц1

X+(і - 1)ст+ц

х1(і -1) - х21(і) < -є;

Xй X(1 - й) + істй

х22 (і +1) + х22 (і) +

X + іст + ц1

X + іст + ц1

іст

+ Х 22 (і - 1) +

ц1

X + іст + ц1

X + іст + ц1

Х20

— X22 (і) < —Є.

Числа Хк (і) будем искать в виде

хк

Подставив (4) в (3), получим неравенства:

В1 - В0 < -є +

іст

X + іст

-А;

ц

-в0 +-

X + іст

X + іст + ц X + іст + ц

В20 В1 <

іст + 2X

<-є------------------------А;

ц1

Х + /СТ + ц1

Из вида вероятностей перехода следует, что данная цепь неприводима и непериодична.

Для доказательства существования стационарного режима воспользуемся эргодической теоремой Мустафы [5], которая в рассматриваемом случае будет иметь следующий вид:

«Для того чтобы неприводимая, непериодическая цепь Маркова была эргодична, достаточно существования е>о, натурального /о и набора неотрицательных чисел хк(/) таких, что

-в0 +-

X + іст + ц X + іст

X + іст + ц1 X + іст + ц1

В21 В20 <

< -Є --

X

X + іст + ц1

А;

ц1

-в, + х+(і 1)ст в22 - в21 <

X+(і—1)ст+ц^ X+(і—1)ст+ц^

< є| ц1 +X(1-2й)+(і -1)ст2(1-й) А

X+(і — 1)ст+ц1

ц1

В20 --

ц1

X+iст+ц1 X+iст+ц1

в22 <

+

+

іст(1-й) ^й

<—є +— -------- -----А.

X + іст+ц1

В (5) заменим є на 2є и перейдем к пределу при і——от, получим систему неравенств, которая, в частности, обращается в систему равенств:

В1 — В0 = —2є + А ; Вю — В1 = —2є — А ;

Вц — Вю = —2є ; Вц — Вц = —2є + 2(1 — й)А;

0 = -2є +

Система неравенств (6) имеет положительное решение, если й < 1. Например,

А =

2є

1-й

; В0 =

6є 1—й

; в1 =

6є + 2єй 1 - й

В = 2є + 4єй ; В = 6єй ; в = 4єй + 2є

£>-,/4 . -Оті . -Оо") '

1-й

1-й

1-й

следующие за моментами изменения состояния прибора или поступления заявки на этапе оповещения о конфликте. Процесс с дискретным временем {к('п),і('п)} является вложенной цепью Маркова для процесса {к('),і(')}.

Вероятности дпі(ку) перехода за один шаг из состояния (п,і) в состояние (к, у) имеют вид:

д0,(1 .о =

X

X + іст

; д0,і(1, г -1) =

іст

X + іст

д1,г(0, г)=т—ц—; д\,г(2, г+1) = гст

д1,і (2,. + 2) =

X + іст + ц X ; X + іст + ц'

X + іст + ц Xй

X + іст + ц1

Если существует положительное решение предельной системы (6) для 2є, то найдется такой номер і0, что для любого і>і0 будет выполняться допредельная система неравенств (5) для є. Таким образом, при выполнении условия й<1 в системе с непрерывным контролем сигнала оповещения о конфликте существует стационарный режим для любых значений параметра X.

Математическая модель сети связи с А-настойчивым протоколом случайного множественного доступа с дискретным контролем сигнала оповещения о конфликте

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

Состояние системы определим вектором (к,і), где к - состояние канала: к=0 - прибор свободен; к=1 - прибор занят обслуживанием заявки; к=2 - в системе реализуется сигнал оповещения о конфликте; і - число заявок в ИПВ. Процесс {к('),і(')} изменения во времени состояния системы является цепью Маркова с непрерывным временем.

Существование стационарного режима в сети связи с дискретным контролем сигнала оповещения о конфликте

Для нахождения условия существования стационарного режима для данной цепи построим вложенную цепь. Пусть 'п - моменты, непосредственно

„

д2,.(2,г) = Л . . .------; д2,. (2,г -1) =

Х + /ст + ц1 " 'Л‘ч ' Х + /ст + ц1

д 2/(°О = -——1—.

Х + /ст + ц1

Для доказательства существования стационарного режима в данной системе также воспользуемся эргодической теоремой Мустафы [5].

Условие (2) выполняется всегда, так как в суммах (2) конечное число слагаемых. Условия (1) для рассматриваемой модели имеют вид системы трех неравенств:

. Х. х1 (/) + — х1 (/ -1)-Хо(/) - -е;

Х + /ст Х + /ст

----------хо (/) +---—-----х2 (/ +1) +

Х+ /ст+— 0 Х+ /ст+— 2

X

X + іст + ц

х2 (і + 2) - х1 (і) < -є;

Xй X(\ - й) + істй

Х2 (г +1) +---------------------------Х2 (г) +

X + іст + ц1

X + іст + ц1

іст

+------------------х2(і - 1) +

ц1

X + іст + ц1

X + іст + ц1

Х2

— Хц (і) < —є.

Подставив выражение (4) в (7), получим неравенства:

В1 - В0 < -є +

X + іст

А,

ц

X + іст + ц

В0 +

X + іст

X + іст + ц

іст + 2X

< -є------------------------------А

X + іст + ц

"В0 "

В2 - В1 <

X + іст + ц X + іст + ц

іст(1 - й) -}й < -є + А .

X + іст + ц

В2 <

В (8) заменим є на 2є и перейдем к пределу при і — от , получим систему неравенств, которая, в частности, обращается в систему равенств

В1 — В0 = —2є + А ; В2 — В1 = —2є — А; 0 = -2є + (1 - й) А.

Система неравенств (9) имеет положительное решение, если к < 1, например:

Л = Л. ; « =- 5е

1-й

1-й

5є + 2єй є + 4єй

В1 — ; В2 — "

1-й

1-й

Если существует положительное решение предельной системы (9) для 2є, то найдется такой номер і0, что для всех і>і0 будет выполняться допредельная система неравенств (8) для є . Таким образом, при выполнении условия й<1 в системе с дис-

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

Заключение

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

ЛИТЕРАТУРА

1. Лившиц Б.С., Пшеничников А.П., Харкевич А.Д. Теория телетрафика. М.: Связь, 1979.

2. КлейнрокЛ. Вычислительные системы с очередями. М.: Мир, 1979.

3. Бертсекас Д., ГалагерР. Сети передачи данных. М.: Мир, 1989.

4. Назаров А.А., Туренова Е.Л. Исследование устойчивости сетей связи, управляемых протоколами случайного доступа с оповещением о конфликте // Автоматика и вычислительная техника. 2оо1. № 4. С. 32-43.

5. КоролюкВ.С. Стохастические модели систем. Киев: Наукова думка, 1989.

6. Шохор С.Л. Эргодичность цепей Маркова с ленточным графом и их применение к задачам анализа условий существования стационарных режимов в сетях связи с динамическими протоколами случайного множественного доступа // Проблемы передачи информации. 2оо1. № 2. С. 3-18.

7. Климов Г.П. Стохастические системы массового обслуживания. М.: Наука, 1966.

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

Томского государственного университета, поступила в научную редакцию номера 3 декабря 2оо1 г.