Распределение времени доставки сообщения в сети связи с протоколом «синхронная адаптивная АЛОХА» для случая конечного числа станций | Вестн. Том. гос. ун-та. 2000. № 271.

Распределение времени доставки сообщения в сети связи с протоколом «синхронная адаптивная АЛОХА» для случая конечного числа станций

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

Distribution of the announcement's delivery time in network with the strategy adaptive slotted ALOHA in case of the fin.pdf Протокол случайного множественного доступа «синхронная Алоха» является одной из модификаций известного протокола «Алоха», предназначенного для передачи сообщений через спутниковую сеть связи [lj. Он, как и многие протоколы данного класса, не отличается стабильным функционированием [2]. В [3] показано отсутствие стационарного режима для протокола «синхронная Алоха» с бесконечным числом абонентских станций (АС), а в [4] рассмотрено явление бис-табильности для того же протокола в случае конечного числа станций. Для стабилизации таких систем используются адаптивные [5] протоколы доступа Одним из них является алгоритм Ривеста [6], который совпадает с алгоритмом Михайлова [7], разработанным для протокола случайного множественного доступа «синхронная Алоха» с поступающим на вход системы простейшим потоком с параметром А. Принцип работы этого апгориша состоит в том, что вероятность повторной передачи пакета из источника повторных вызовов (ИПВ) меняется с изменением величины оценки числа пакетов в ИПВ, которая явным образом зависит от величины X. Одним ю достоинств режима случайного доступа является быстрый доступ к передающей среде и малое время доставки сообщения при ограниченных нагрузках. Недостаток этого режима состоит в том, что при больших нагрузках время доставки сообщения становится большим и меняется непредсказуемо. В этом случае использование обычно широко применяемой теоремы Лиггла, позволяющей найти лишь среднее время доставки сообщения, представляется малоэффективным. В данной работе рассмотрена неустойчивая сеть связи с конечным числом узлов и протоколом случайного множественного доступа «синхронная Алоха». Для ее стабилизации применяется адаптивная модификация протокола доступа, в которой адаптация реализуется автоматом с целесообразным поведением [8], названным здесь адаптером. Найдено асимптотическое распределение вероятностей времени доставки сообщения при N-*aa, где N - количество АС. Математическая модель сети связи Сеть связи с протоколом случайного множественного доступа «синхронная Алоха» моделируется однолинейной системой массового обслуживания (СМО). Пусть число АС конечно и равно N и каждая из N станций может осуществлять передачу сообщения только в начале временного интервала единичной длины с веро-jh-ftofcTkid UN. Обобщение, 11ерйдаваемое АС (назовём его приходящим из внешнего источника), ожидает начала очередного такта и с вероятностью единица становится на обслуживание в течение этого интервала. Если на этом такте на приборе не было других требований, то исходная заявка считается успешно обслуженной и покидает систему. Если в одном такте на приборе находилось более одного сообщения, то фиксируется конфликтная ситуация (все заявки искажаются), и в момент окончания такта все искаженные сообщения переходят в ИПВ. В начале такта каждая заявка из ИПВ обращается к прибору с вероятностью q независимо от других требований с попыткой повторного обслуживания. Дня стабилизации неустойчивых сетей вероэтноспъ q повторного обращения положим равной q=l/T, где Г-текущее состояние адаптера Опишем его функционирование. Если в такте было пустое окно или успешное обслуживание^ тогда значение Г уменьшается иа величину о, но не может стал, меньше единицы. Если обслуживание было конфликтным, то значение Т увеличивается на р. Состояние адаптера меняется в конце текущего такта. Положительные величины аир являются параметрами адаптера. Состояние системы определим вектором ft 7), где i -число заявок в ИПВ, а Т-состояние адаптера. Рассмотрим момент t(k), непосредственно следующий за моментом окончания такта с номером к-\ и предшествующий моменту начала такта с номером к. Обозначим (i(k), Т(к)) состояние системы в момент времени t(fy. Двумерный случайный процесс (i(k), Т(к)) с дискретным временем к является д вумерной однородной марковской цепью. Назовем временем пребывания заявки в системе длину W интервала от момента ее поступления в систему до момента окончания ее успешного обслуживания и ухода из системы. Величина W будет моделировать время доставки сообщения в сети связи с протоколом «синхронная адаптивная Алоха». Найдем стационарное распределение величины W. Распределение времени пребывания заявки в системе В момент к выделим некоторую заявку в ИПВ и определим W(k) как длину интервала от момента к до момента ухода из системы выделенной заявки. Для исследования рассматриваемой сети обозначим F(i, Т, L) = P(W(k) > L / i(k) = /, Т(к) = Т), >0, Т) = P{i(k) = iXk) = Г), & = сс + р. Очевидно, что для времени W пребывания заявки в системе имеет место равенство P{W + Распределение P(i, T) должно удовлетворять краевым условиям при i=0 и i=N , а также условию нормировки. Дальнейшие исследования будем проводить при Х>1/е, т.е. в условиях перегрузки. Решим системы (2) и (3) асимптотическим методом [9] при N-kx>. Для этого, обозначив е2=1 IN, сделаем замену переменных: /е2 = а+ей, 7е2 = А + ev, Is2 = А, T,L) = f(u, v, A, e), \p(i,T) = H{u,v,z). (4) e Зассъ(а,Ь) - точка стабилизации системы, определенная соотношениями X(l-a) + ?- = g, e-gg = X(l-a), (5) А где G=g является решением уравнения &Tc(G + l) = p. (6) • • Соотношения (5К6) получены в-[Ю}. При е-»0-обо» • значим Н(и, v,0) = Я(и, v); /(и, v, А,0) = /(м, v, А). Так как в рассматриваемой системе заявки не теряются, то производительность сети равна интенсивности входящего потока, который является ординарным, и по теореме Королюка его интенсивность и параметр совпадают. Отсюда получаем, что в асимптотике при N-*oo производительность S будет определяться равенством 5 = - а). Тогда соотношение (1) при N-юо перепишем так: P(w £ А) = Se g + + (N-i) N + 1г а + ги-г 1 + A + ev + ae2 х 1- A + ev + ae 1-Я-81/ f 1- /(M,v,A,e)+ A + ev + ae2 2 . чl-q-Е» - (l-Xe2) x a + EU-E A+ev + ae 1-7-Г /(«-e,v,A,e). (8) A+ev + ae J В (2) распределение F(i, T,L) определено на дискретном множестве точек (i,T,L). В (8) функцию fiu,v,h,z) доопределим для всех -ооo OK + 1 an = Х+е~*Х[(1-а)к-1] + e'2 * b2 b1 ' °2l -I i аП ° -I -2- = а„+ке = e*, 2b, = X(1 - а)[Х(1 - a) +1 - e ]+ - e~*, b (H) 2Ьг = сф, bn=(a&/b)e'g, где к=Х-1/Ь, a g является корнем уравнения (6). (12) Можно показать, что Н(иу) является двумерным нормальным распределением и удшиктеоряет уравнению + X" (Ки + °22v)H(u,v)}+ Ь12 dv - {(апи + о12у)Я(м,у)}+ ди d2H(u,v) dudv где все коэффициенты имеют вид (12). -ною Обозначим Ф(А)= J jf(u,v,h)H(u,v)dudv и -00-00 найдем функцию Ф(Ь), для чего домножим уравнение (11) на H(u,v) и проинтегрируем почленно это соотношение по -oo

Ключевые слова

Авторы

ФИООрганизацияДополнительноE-mail
Одышев Юрий ДмитриевичТомский государственный университетаспирант факультета прикладной математики и кибернетикиodyshev@fpmr.tsu.ru
Всего: 1

Ссылки

Назаров А.А., Юревич Н.М. Исследование явления бистабильности в сети с протоколом Алоха для конечного числа станций // Автоматика и телемеханика. 1996. № 9. С. 91-100.
Бертсекас Д., Галагер Р. Сети передачи данных. М.: Мир, 1989.
Фалин Г.И. О неустойчивости сети Алоха // Проблемы передачи информации. 1990. № 1. С. 79-82.
Одышев Ю.Д. Исследование явления бистабильности в сети с протоколом «синхронная Алоха» для конечного числа станций // Математическое моделирование и теория вероятностей. Томск: Пеленг, 1998. С. 242-247.
Горцев A.M., Назаров А.А., Терпугов А.Ф. Управление и дотация в системах массового обслуживания. Томск Изд-во Том. ун-та, 1978.
Network Control by Bayessian Broadcast (Report MIT/LCS/TM-285).Cambridge, MA: MIT, Laboratory for Computer Science , 1985.
Михайлов В.Л. Геометрический анализ устойчивости цепей Маркова в Rn+ и его приложение к вычислению пропускной способности адаптивного алгоритма случайного множественного доступа // Проблемы передачи информации. 1988. № 1. С. 61-73.
Цеткин M.Л. Исследование по теории автоматов и моделированию биологических систем. М.: Наука, 1969.
Назаров А.А. Асимптотический анализ марковизируемых систем. Томск: Изд-во Том. ун-та, 1991.
Одышев Ю.Д. Исследование сети связи с протоколом «синхронная адаптивная Алоха» для конечного числа станций // Математическое моделирование. Кибернетика. Информатика. Томск: Изд-во Том. ун-та, 1999. С. 115-119.
 Распределение времени доставки сообщения в сети связи с протоколом «синхронная адаптивная АЛОХА» для случая конечного числа станций | Вестн. Том. гос. ун-та. 2000. № 271.

Распределение времени доставки сообщения в сети связи с протоколом «синхронная адаптивная АЛОХА» для случая конечного числа станций | Вестн. Том. гос. ун-та. 2000. № 271.

Полнотекстовая версия