<< prev | ^up^ | next >>

6.3. Методы случайного доступа.

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

Методы случайного доступа простираются от чистой Алохи, при которой пользователь передает в любой момент времени, если имеет сообщения, до более сложных методов, при которых он перед передачей прослушивает среду и осуществляет передачу, если она свободна - метод МДНП/ОС. Т.к. основная идея случайного доступа чрезвычайно проста, то этот алгоритм легко реализуется и оказывается сравнительно недорогим на практике.

1. Чистая Алоха - (Aloha)

Этот метод был впервые применен для доступа к общему радиоканалу сотрудниками Гавайского университета в 1970 г. Согласно этой схеме пользователь, желающий передать сообщение делает это когда удобно. В результате могут наложиться 2 или более сообщений, вызвав столкновение.

Поэтому должны существовать методы распознавания столкновений и передачи соответствующих сообщений всем <эпользователям, сообщения которых столкнулись> (что может выполняться центральной станцией, как первоначально в системе Алоха).

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

Стратегия <эчистой> Алохи, несмотря на свою простоту, оказалась малоэффективной, в смысле использования пропускной способности (ПС) канала и позволяет достичь самое большее 1/2с=0,18 общей ПС канала. Докажем это утверждение.

Введем следующие допущения.

Пусть за доступ к каналу состязаются N станций, каждая из которых передает в среднем l^пак/с. Пусть все передаваемые сообщения имеют одинаковую длину (фиксированную), соответствующую m единиц время передачи (с).

Тогда нормированная производительность r, которая характеризует коэффициент использования канала вновь поступившими пакетами, будет равна

Sºr=Nlm,                                                                                                                                                          (6.10)

где m=1/m - время передачи пакета.

Допустим, что входящий поток пакетов на каждой станции пуассоновский. Следовательно L_S=lN. Как ясно, полный поток с учетом повторных вызовов, имеет интенсивность L`>L.

Тогда интенсивность нагрузки или использование канала равна G=NL`m                                                                                                                                                        (6.11)

Рассмотрим типичное сообщение длительностью m сек, показанное на рис. 6.7. Оно подвергается столкновению с другим сообщением, если эти 2 сообщения окажутся наложенными одно на другое. Легко видеть, передвигая пунктирное сообщение, что это столкновение может произойти в промежутке длиной 2m.

Рис. 6.7.

Вероятность того, что в промежутке 2m не произойдет столкновений, равна вероятности того, что не появится сообщение в интервале (0, 2m). Она будет равна

e^-2NL`m =e^-2G                                                                                                                            (6.12)

Отношение S/G - доля сообщений, преданных успешно. Это число должно быть равно вероятности успеха, т.е. вероятности отсутствия столкновений. Таким образом получаем следующее уравнение производительности для чистой Алохи.

S=Ge^-2G                                                                                                                                                 (6.13)

Здесь S - нормированная производительность - независимая переменная, G - входящая нагрузка (с учетом повторных вызовов).

График зависимости S(G) приведен на рис. 6.8.

Рис. 6.8.

Максимум этой функции легко определить из условия dS/dG =0. Он достигается при G=0,5, и при этот S_max=0,5e^-1>0,184.

Определим задержки, вносимые чистой Алохой. Для их вычисления необходимо сначала определить стратегию повторных передач. Как уже отмечалось, повторные передачи должны быть рандомизированы в смысле разнесения во времени передач, и уменьшения вероятности повторных столкновений. Одно из предложений состоит в выборе произвольного промежутка времени (0,T) и равномерного распределения случайных моментов передачи внутри этого промежутка.

Пусть промежуток времени перекрывает время передачи k сообщений по m ед. времени в каждом (т.е. T=km).

Тогда повторная передача происходит в пределах от 1 до k таких интервалов, т.е. t Î[1¸k]m .

Пусть задержка при циклическом обходе и время обработки такой информации (т.е. время обнаружения столкновений) составляет Rm с. Тогда станция источника сообщений включалась бы через R интервалов длины сообщения, т.е. через Rm, если к этому моменту времени не поступит положительное подтверждение. (Очевидно R должно быть выбрано с учетом времени задержки при циклическом обходе и времени обработки). Тогда среднее время, необходимое для успешной передачи сообщения, равно:

,                                                                  (6.14)

n_повт - среднее число повторных попыток на передаваемое сообщение (до успешной передачи).

Величина n_повт  должна зависеть от интервала повторных передач k. Однако при достаточно больших k эта зависимость исчезает и имеет очень простой вид.

Очевидно, G/S=1+ n_повт, откуда n_повтG/S-1 и на основании (6.12) получим:

n_повт=е^2G-1                                                                                                                                           (6.15)

2. Синхронная Алоха.

Максимальная производительность чистой Алохи может быть удвоена с помощью простого приема - разметки шкалы времени и разрешении пользователям начинать попытки передачи только в начале каждого интервала времени m₀. Конечно, эта схема требует, чтобы работа всех пользователей была синхронизирована.

Рис. 6.9.

Используя все предыдущие допущения, мы получаем, что производительность для синхронной Алохи имеет вид:

S=Ge^-G                                                                                                                                                 (6.16)

Ясно, что она достигает максимума при G=1, S_max=1/e=0,368.

Рис. 6.10.

Анализ задержек при синхронной Алохе аналогичен случаю для чистой Алохи.

Узнав, что через R интервалов после попытки передачи произошло столкновение, станция осуществляет повторную передачу в любом из k интервалов с одинаковой вероятностью. Эта процедура показана на   рис. 6.11.

Рис. 6.11.

На основе этой процедуры, очевидно, что среднее время для успешной передачи при синхронной Алохе найдется в виде.

`D=[1,5+R+n_повт(R+0,5+(k+1)/2)]m.                                                                  (6.17)

Дополнительные 0,5 ед. времени  - это поправка для учета ожидания сообщения, которое появляется после того как начнется интервал.

Поскольку n=G/S-1, то для синхронной Алохи среднее число повторных попыток равно:

n_повт=e^G-1.

Возникает проблема выбора k. При малых k уменьшается время ожидания повторной передачи, но увеличивается вероятность повторных столкновений, а при больших k - наоборот.

Таким образом, существует некоторое оптимальное k⁰, которое минимизирует задержку D, опоздавший от R и S. При S близких к S_max=0,368, k⁰=5. На рис. 6.12 представлена зависимость D/m от S при R=0, при этом k выбрано равным 5.

Рис. 6.12.

Сравнение опроса и случайного доступа.

Сравним оба метода доступа для ранее разобранного примера. Пусть l=1^пак/_мин; V_пер=4800 ^бит/_с, l_к=1200 бит, будем варьировать число станций N.     

 При этом для опроса задержка с учетом времени передачи сообщения m равна:

D=t_c/2(1-r/N)+(m/2)*r/(1-r)+m                                                                          (6.18)

где t_c находится согласно (7), а L с помощью формулы (6.9). При этом для Алохи R=0, k=5. На рис. 13 представлены соответствующие зависимости D/m (нормированного времени до успешной передачи).

Мы видим, что при N=20 станций и средней интенсивности l=1^пак/_мин, все 3 метода доступа имеют примерно одинаковые характеристики, и при малой нагрузке N<20, схемы случайного доступа имеют преимущество по сравнению с управляемым опросом, а при возрастании N(N>40) маркерный метод имеет значительное преимущество.