Исследование условий существования стационарного режима в сетях связи с 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
— (1, і - 1) = і в (1 — в-СТ'-)
X + іст іст
X + іст
ди (0, і) = | в-Х'-в-iстtd (1 — в~ц'-)
0
дм (20, і +1) = | в-х'в-цtd (1 — в-ст'--
0
ОТ
ди (20, і + 2) = | в-гстtв-цtd (1 — в^'--
ц
0
ОТ
д20, (21, і +1) = | в-(Ц1 +іст)id (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,і) = & quot- +
д 22, і (22, і - 1!) =
д 22, і(20, і) =
X + іст + ц1 X + іст + ц1 іст (1 — й)
X + іст + ц1
ц1
ЕЕ?",/(к'Л)хк (Л) — х"(/)-е для 1 & gt- /& gt- & gt- (!)
к=1 Л=0
^ да ____
ЕЕ?",/(к'Л)хк (Л) & lt-' для 1 -го' п=1,(2)
к=1 Л=0
При этом существует единственное эргодическое распределение, совпадающее со стационарным".
Условие (2) выполняется всегда, так как в суммах (2) конечное число слагаемых. Условия (1) для рассматриваемой модели имеют вид системы пяти неравенств:
х (/)±^-Х1 (/ -1) — Хо (/) — -е-
Х+/ст Х+/ст
^ /ч /СТ 1Ч
-Хо (/) +& quot--:-----Х2о (/ +1) +
X+iст+ц X+іст+ц
X
X + іст + ц
Л-20 (і + 2) — хО) & lt--е —
------------------------Хц (і + 1) + ------------------------ц------------------------Хд (і) +
X + іст + ц1 X + іст + ц1
іст
X+іст+ц1
Хц (і) — хм (і) & lt--є-
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(і) & lt- -є-
Xй X (1 — й) + істй
х22 (і +1) + х22 (і) +
X + іст + ц1
X + іст + ц1
іст (1 — й)
+ Х 22 (і - 1) +
ц1
X + іст + ц1
X + іст + ц1
Х20 (і) — (3)
— X22 (і) & lt- -Є.
Числа Хк (і) будем искать в виде
хк (і)=Аі+вк, (4)
Подставив (4) в (3), получим неравенства:
В1 — В0 & lt- -є +
іст
X + іст
-А-
ц
-в0 ±
X + іст
X + іст + ц X + іст + ц
В20 В1 & lt-
іст + 2X
& lt--є------------------------А-
ц1
Х + /СТ + ц1
Из вида вероятностей перехода следует, что данная цепь неприводима и непериодична.
Для доказательства существования стационарного режима воспользуемся эргодической теоремой Мустафы [5], которая в рассматриваемом случае будет иметь следующий вид:
«Для того чтобы неприводимая, непериодическая цепь Маркова была эргодична, достаточно существования е& gt-о, натурального /о и набора неотрицательных чисел хк (/) таких, что
-в0 ±
X + іст + ц X + іст
X + іст + ц1 X + іст + ц1
В21 В20 & lt-
& lt- -Є --
X
X + іст + ц1
А-
ц1
-в, + х+(і 1) ст в22 — в21 & lt-
X+(і-1)ст+ц^ X+(і-1)ст+ц^
& lt- є| ц1 +X (1−2й)+(і -1)ст2(1-й) А
X+(і - 1) ст+ц1
ц1
¦В20 --
ц1
X+iст+ц1 X+iст+ц1
в22 & lt-
+
+
іст (1-й) ^й
& lt--є ± -------- -----А.
X + іст+ц1
(5)
В (5) заменим є на 2є и перейдем к пределу при і--от, получим систему неравенств, которая, в частности, обращается в систему равенств:
В1 — В0 = -2є + А — Вю — В1 = -2є - А —
Вц — Вю = -2є - Вц — Вц = -2є + 2(1 — й) А-
0 = -2є + (1 — й) А. (6)
Система неравенств (6) имеет положительное решение, если й & lt- 1. Например,
А =

1-й
— В0 =
6є 1-й
— в1 =
6є + 2єй 1 — й
В = 2є + 4єй — В = 6єй — в = 4єй + 2є
?& gt--,/4. -Оті. -Оо& quot-) '-
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, что для любого і& gt-і0 будет выполняться допредельная система неравенств (5) для є. Таким образом, при выполнении условия й& lt-1 в системе с непрерывным контролем сигнала оповещения о конфликте существует стационарный режим для любых значений параметра X.
Математическая модель сети связи с А-настойчивым протоколом случайного множественного доступа с дискретным контролем сигнала оповещения о конфликте
В качестве математической модели данной сети связи рассмотрим однолинейную систему массового обслуживания (СМО), на вход которой поступает простейший поток заявок с параметром X. Если прибор свободен, поступающая заявка начинает обслуживаться. Время обслуживания распределено по экспоненциальному закону с параметром ц. Если за это время другие требования не поступают, то заявка, завершив обслуживание, покидает систему. Если во время обслуживания поступает другая заявка, то возникает конфликт. Каждая заявка, попавшая в конфликт, переходит в источник повторных вызовов (ИПВ). На приборе начинается этап оповещения о конфликте. Его продолжительность распределена по экспоненциальному закону с параметром ц1. Все заявки, поступившие в систему на этапе оповещения о конфликте, с вероятностью й становятся в очередь, и с вероятностью 1-й теряются.
Состояние системы определим вектором (к,і), где к — состояние канала: к=0 — прибор свободен- к=1 — прибор занят обслуживанием заявки- к=2 — в системе реализуется сигнал оповещения о конфликте- і - число заявок в ИПВ. Процесс {к ('-),і('-)} изменения во времени состояния системы является цепью Маркова с непрерывным временем.
Существование стационарного режима в сети связи с дискретным контролем сигнала оповещения о конфликте
Для нахождения условия существования стационарного режима для данной цепи построим вложенную цепь. Пусть '-п — моменты, непосредственно
«(2 г) М1 — й) +істй. (2. іст (1 — й)
д2,. (2,г) = Л.. . ------- д2,. (2,г -1) = ¦
Х + /ст + ц1 & quot- ¦'-Л'ч '- Х + /ст + ц1
д 2/(°О = ---1-.
Х + /ст + ц1
Для доказательства существования стационарного режима в данной системе также воспользуемся эргодической теоремой Мустафы [5].
Условие (2) выполняется всегда, так как в суммах (2) конечное число слагаемых. Условия (1) для рассматриваемой модели имеют вид системы трех неравенств:
. Х. х1 (/) + - х1 (/ -1)-Хо (/) — -е-
Х + /ст Х + /ст
----------хо (/) ±--------х2 (/ +1) +
Х+ /ст± 0 Х+ /ст± 2
X
X + іст + ц
х2 (і + 2) — х1 (і) & lt- -є-
Xй X (- й) + істй
Х2 (г +1) ±--------------------------Х2 (г) +
X + іст + ц1
X + іст + ц1
іст (1 — й)
±-----------------х2(і - 1) +
ц1
X + іст + ц1
X + іст + ц1
Х2(і) — (7)
— Хц (і) & lt- -є.
Подставив выражение (4) в (7), получим неравенства:
В1 — В0 & lt- -є +
X + іст
А,
ц
X + іст + ц
В0 +¦
X + іст
X + іст + ц
іст + 2X
& lt- -є------------------------------А
X + іст + ц
& quot-В0 & quot-
В2 — В1 & lt-
X + іст + ц X + іст + ц
іст (1 — й) -}й & lt- -є + А.
X + іст + ц
В2 & lt-
(8)
В (8) заменим є на 2є и перейдем к пределу при і - от, получим систему неравенств, которая, в частности, обращается в систему равенств
В1 — В0 = -2є + А — В2 — В1 = -2є - А- 0 = -2є + (1 — й) А.
(9)
Система неравенств (9) имеет положительное решение, если к & lt- 1, например:
Л = Л. — «=- 5е
1-й
1-й
5є + 2єй є + 4єй
В1 — - В2 — & quot-
1-й
1-й
Если существует положительное решение предельной системы (9) для 2є, то найдется такой номер і0, что для всех і& gt-і0 будет выполняться допредельная система неравенств (8) для є. Таким образом, при выполнении условия й& lt-1 в системе с дис-
кретным контролем сигнала оповещения о конфликте существует стационарный режим для любых значений параметра Х.
Заключение
В данной работе показано, что в сетях связи, управляемых протоколом к-настойчивого доступа с непрерывным и дискретным контролем сигнала оповещения о конфликте, существует стационарный режим при выполнении условия к& lt-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 г.

ПоказатьСвернуть
Заполнить форму текущей работой