Среднее время разрешения конфликта
Пусть К – число абонентов, участвующих в конфликте.
- случайная величина, равная времени разрешения конфликта (в примере К = 3, = 7)
Тк М – средняя величина разрешения конфликта
Т1 = 1 – время разрешения конфликта с одним абонентом (т.е. количество окон)
3 (именно , а не )
Самый лучший случай
Х |
Х · |
· |
Рассмотрим все возможные ситуации, которые могут возникать при разрешении конфликта кратности 2.
Х |
Х · ю |
· |
· ю |
Х · ю |
Х ю |
ю |
3. ? Р3 = L2 = 1+?+1
ю |
Х · ю |
Х · ю |
ю |
ю |
4.
Х · ю |
Х · ю |
T2 = Р1* М + Р2 * М + Р3 * М + Р4 * М
= *3 + *3 + (1+T2+1) + (1+1+T2)
T2 = + + T2 + + Т2
T2 = +1+ Т2
Т2 =
= / * 2
Т2 = = 5
|
|
Т2 = 5
Аналогичным образом можно вычислить для конфликтов кратности 3,4
Тк K – при больших К
Улучшенный древовидный алгоритм разрешения конфликтов
Чаще всего пытаются передавать небольшое число абонентов, в большинстве случае это всего один абонент.
В случае двух абонентов (событие «конфликт») ситуация разрешается быстро. В рассматриваемом ранее примере для разрешения конфликта кратности 3 ушло 7 окон. Однако, не привлекая никакой дополнительной информации (в данном примере) число окон можно сократить до 6.
Надо отметить, что окно «пусто» не является лишним. Окно № 7 не является лишним, т.к. в нем передается сообщение. Лишним является окно № 4, т.к. все абоненты, наблюдая события в окне №2 и №3 с вероятностью, равной 1, имеют информацию, что в окне № 4 будет конфликт, поэтому его можно пропустить.
Рассмотрим еще один пример:
3 |
1 3 |
1 3 |
1 |
1 2 3 |
2 |
В данном случае улучшить работу алгоритма не получится. Улучшить работу алгоритма можно только в тех ситуациях, когда ситуация П («пусто») возникает у верхнего потомка и можно пропустить его.
|
|
4 допуск 3 лабораторной работы: найти среднее время разрешения конфликта кратности 2 для улучшенного алгоритма (результат должен быть строго меньше предыдущего случая).
Оптимальный алгоритм АЛОХА
Как и раньше пользуемся допущениями базовой модели.
Временно дополнительно вводим допущения:
К началу каждого окна всем абонентам достоверно известно, у скольких абонентов есть готовое для передачи сообщение.
2
4 х
5
=3
П К
Рис.3.12. Описание системы
У трех абонентов есть готовое для передачи сообщение. Можно доказать, что оптимальная стратегия - передавать все абонентам с вероятностью Рt =
Также можно доказать, что если абоненты передают с одинаковой вероятностью, то можно минимизировать среднюю задержку.
Замечание. К началу окна известны номера тех абонентов, у которых есть сообщения
Можно избежать конфликтов и предоставить для передачи окно абоненту с его же номером.
В реальных системах такой информации нет. Пытаются так менять вероятность передачи, чтобы характеристики системы приблизить к оптимальному алгоритму АЛОХА.
|
|
Адаптивный алгоритм АЛОХА
Возвращаемся к базовой системе допущения, предполагаем, что Nt нам неизвестно (число абонентов, которые передают неизвестно).
Замечание. Эти все методы хорошо работают при низкой интенсивности входного потока.
Р1 = 1
Рt+1 = должно быть
Вариантов реализации данного алгоритма может быть много. На сегодняшний день не найдено оптимального.
d АЛОХА – общее число абон. в сист
опт. АЛОХА
1,5 адаптивный АЛОХА
Рис.3.13. Сравнительный анализ алгоритмов
Алгоритм адаптивная АЛОХА предполагает, что все абоненты передают в канале с одной и той же вероятностью, и для вычисления этой вероятности по некому рекурентному правилу наблюдают выход канала с самого начала функционирования системы.
|
|
Дата добавления: 2018-06-01; просмотров: 1015; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!