Разновидности алгоритма «АЛОХА»

1) Если увеличивается ( ), то Р =

2) Если уменьшается ( = Е, Е →0, то Р 1

Если у абонента появляется одно единственное сообщение (про других абонентов ничего неизвестно), то необходимо передать его сообщение с Р = 1 Если произойдет «успех», то сообщение уходит, буфер освобождается, ждет следующее сообщение. Если в канале «конфликт», то абонент делает попытки передать с вероятностью Р.

3.5.1 Анализ алгоритма АЛОХА (1,Р)

1) _кр

У всех абонентов имеется сообщение, так как в этом случае все абоненты передают с вероятностью Р, то _кр = М Р =

2) d₀

Только у одного абонента появилось единственное сообщение

D₂ = 1 M = + 1

P = 1

d₀M = 100, P

M = 100, P

АЛОХА (1, P = )

АЛОХА (1, P =

) (до некоторого значения интенсивности

)

Рис.3.10. Анализ алгоритма АЛОХА (1,Р)

Этот график будет идти ниже всех графиков, изображенных на рис.3.9.

Оптимальный алгоритм АЛОХА

Предположим, что всем абонентам известно число абонентов, у которых в настоящее время имеются сообщения.

Замечание. Данная тема будет рассмотрена позже.

Древовидные алгоритмы для разрешения конфликтов

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

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

К К П К У У У

1 2 3 4 5 6 7 8 9 10

4 5

1 3

К К

1 2

1 2 3

К У

1 2 3

1 3

Рис. 3.11. Дерево разрешения конфликтов

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

Замечание. Абоненты не знают об их количестве.

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

Пусть до начала окна в системе появилось 1,2,3 абоненты. В этом случае все три абонента передают в 1 окно. Произошел конфликт (К). Наблюдая за ситуацией, абоненты будут строить дерево разрешения конфликта. Окну №1 ставим корневую вершину и помечают его как К (конфликт). У корневой вершины есть 2 потомка: верхний и нижний. Верхний будет соответствовать окну № 2. Нижний будет определен позднее. Все абоненты, которые участвуют в конфликте, с одинаковой вероятностью выбираются для повторной передачи одного из потомков. В нашем примере предполагается, что верхнего потомка выбрали абоненты № 1 и № 3. Снова будет конфликт и дальше строят дерево по тому же правилу. Наблюдая выход канала, абоненты в конце очередного окна знают только ситуацию в канале, при этом они не знают, какие абоненты передают в окне и сколько передавало (информация внутри вершины абонентам недоступна).

Вероятность ситуации в окне N₂ = (т.к. вероятность ² *

Пусть в окне № 3 абоненты решили не передавать, вероятность такого события = . Вершина с отметкой «пусто» (П) становится концевой вершиной дерева.

Далее появится абонент № 4. Он также строит дерево. Он видит, что конфликт не разрешен. В окне № 4 повторно возникает конфликт и построение дерева предполагается.

С некоторой отличной от вероятностью конфликт может длиться более, хотя она очень небольшая

Время разрешения конфликта – случайная величина.

Дата добавления: 2018-06-01; просмотров: 1245; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 7 8 9 10 11 121314 15 16 Следующая ⇒

Мы поможем в написании ваших работ!