Алгоритм случайного множественного доступа «АЛОХА».
Рассмотрим простейший способ:
Абонент, который имеет готовое для передачи сообщение, передает это сообщение в начале очередного окна с некоторой вероятностью 
– параметр алгоритма. В рамках наших допущений знаем только то, что происходит в данный момент.
4) Предположим, что в системе имеется M абонентов. У каждого абонента имеется 
очередь. На вход системы поступает поток интенсивности 
. При этом поток сообщений, который поступает от каждого сообщения - .
1 
P
2 P канал
P
М
Рис. 3.2. Модель алгоритма случайного множественного доступа
Анализ алгоритма АЛОХА на качественном уровне.
d
Р.В
АЛОХА
d0
1
Рис. 3.3. Сравнение АЛОХА и алгоритма с разделением времени
Пусть Nt – число абонентов, у которых к началу окна t в очереди есть хотя бы 1 сообщение. Это активные абоненты.
Nt 
Pr 
= = Pr 
= 
p 
= 
Вычислим вероятность – успех при условии, что в начале окна было n активных абонентов.
Предположим, что известно число активных абонентов к началу окна.
1 из n абонентов решил передавать.
– число способов выбора одного абонента из n
2 допуск 3 лабораторной работы:
(p) = np – max - ? (P 
Ответ: 
= 
).
Pr 
= n 
= 
= n 
= ?
= е-1 = 0,36 = 
е ≈ 2,7
Задача: нахождение кр
Для нахождения кр рассмотрим ситуацию, когда у всех абонентов имеется готовое для передачи сообщение. Опишем данную систему как СМО
1
n у п к к п у
Рис 3.3. Система, в которой у всех абонентов есть сообщения
N = 
= Pr – вероятность успеха = Мр 
Интенсивность обслуживания - можно сказать, средняя доля успеха.
Интенсивность успеха – средняя доля окон, в которых произошел успех.
М 
P 
кр = М P
Вспомним: Pr = n 
= f(p,n)
f(p) 
max, Pопт =
d
С увеличением интенсивности
увеличивается задержка d
d0
кр
Рис 3.4. График зависимости задержки от интенсивности
1
2 канал
М
Рис. 3.5. Общее описание системы
Необходимо найти кр. Для нахождения кр рассмотрим ситуацию, когда очереди заполнены у всех абонентов (рис.1)
1 р
р
2 канал
р
М
Рис.3.6. Описание системы, в которой у всех абонентов есть сообщения для передачи
В этом случае систему можно описать упрощенно (рис.2). Причем 
, чтобы система была устойчивой
N = 
Nу(Т) – число успехов по длине Т
Nк(Т) – число конфликтов по длине Т
Nп(Т) – число пусто по длине Т
У П К У К … У
Т
Рис. 3.7. Упрощенное описание системы
Ny(Т)+Nк(Т)+Nп(Т) = Т
lim 
= 
= 
Следовательно, 
= M P (1 
P)M-1 = кр(М,Р)
кр(М,Р) (POPT = 
)
max
кр(М, ) = М 
= е-1 0,36
Разберемся с начальной задержкой d0.
Для максимального d0 рассмотрим ситуацию, когда у первого абонента появляется сообщение.
В этом случае временная диаграмма будет иметь следующий вид:
D
П П П П П ......... У
P P P
Рис 3.8. Временная диаграмма после появления сообщения у первого абонента
D2 = D – D1( Абонент решает с вероятностью Р).
В окне с номером t может быть либо «пусто», либо «успех».
D1 – непрерывная случайная величина
D1 
М 
= 
D2 
Pr 
= P
Pr 
= (1-P)P
Pr 
= 
P
-Pr = 
P = 
Допуск 3 3-ей лабораторной работы: проверить значение 
.
d0 = M 
= +
d
М = 100, Р = 
М = 100, Р 
0,1
МР(1 - ) 
0,36
Рис. 3.9. Анализ алгоритма на качественном уровне
Выбор Р = решает выбор 
max, но не решает d( ) 
min
Выбор параметра Р - вероятность передачи - сильно влияет на характеристики алгоритма «АЛОХА». Самое существенное: выбор Р = не является оптимальным в смысле минимума средних задержек.
Дата добавления: 2018-06-01; просмотров: 1341; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!