Среднее время разрешения конфликта
Пусть К – число абонентов, участвующих в конфликте.
- случайная величина, равная времени разрешения конфликта (в примере К = 3, 
= 7)
Тк 
М 
– средняя величина разрешения конфликта
Т1 = 1 – время разрешения конфликта с одним абонентом (т.е. количество окон)
3 (именно , а не 
)
Самый лучший случай
| Х |
| Х · |
| · |
Рассмотрим все возможные ситуации, которые могут возникать при разрешении конфликта кратности 2.
| Х |
| Х · ю |
L1 = 3
| · |
| · ю |
| Х · ю |
, L2 = 1+1+1=3
| Х ю |
| ю |
3. ? Р3 = L2 = 1+?+1
| ю |
| Х · ю |
= 1+T2+1, где
| Х · ю |
| ю |
| ю |
4.
| Х · ю |
L4 = 1+1+?
| Х · ю |
= 1+1+T2
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; просмотров: 1036; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!