***** Google.Поиск по сайту:


Лекции по Теоретическим основам цифровой связи   

11. Уплотнение и множественный доступ

11.3.5. Методы опроса

Один из методов упорядочения работы системы произвольного доступа с множественными пользователями состоит во введении контроллера, выявляющего запросы на предоставление услуг путем периодического опроса всех пользователей. Если количество пользователей велико (например, тысячи терминалов), а процесс обмена данными происходит пульсирующим образом, время, выделяемое для опроса всех пользователей, может представлять существенные служебные издержки. Одним из методов быстрого опроса пользователей является поиск по двоичному дереву [4, 14]. На рис. 11.25 представлен пример использования данного метода для реализации "состязания" между пользователями спутниковой связи за обладание ресурсом. Пусть общее число пользователей равно восьми и каждому из них присвоен двоичный код от 000 до 111, как показано на рис. 11.25. Предположим, что терминалы 001, 100 и 110 соревнуются за один канал связи. При поиске по двоичному дереву группа пользователей периодически делится пополам, пока не останется лишь одна ветвь дерева. Терминал, соответствующий этой ветви, и получает право первым использовать канал. Затем операция повторяется, и доступ получает следующий "победитель". Алгоритм поиска состоит из следующих этапов (рис. 11.25).

Рис.11.25. Разрешение соастязания между пользователями: поиск по двоичному дереву

1. Спутник запрашивает у состязающихся терминалов первую цифру их двоичных идентификаторов.

2. Терминал 001 передает "0", терминалы 100 и 110, соответственно, "1". Спутник, на основе мощности принятых сигналов, выбирает нуль или единицу. В данном примере была выбрана единица, и об этом были проинформированы пользователи. В настоящий момент половина пользователей прекращает состязание. В данном примере выбывает терминал 001.

3. Спутник запрашивает у оставшихся терминалов вторую цифру идентификационного номера.

4. Терминал 100 передает "0", терминал 110 — "1".

5. Предположим, что спутник выбрал нуль и уведомил об этом пользователей. Терминал 110 выбывает из состязания. Процесс продолжается до тех пор, пока терминал 100 не получит доступ к спутнику.

6. После того как канал связи освобождается, этапы 1-5 повторяются.

Пример 11.3. Сравнение поиска по двоичному дереву и непосредственного опроса

а) Поиск по двоичному дереву требует принятия и = log2Q решений при каждом опросе группы из Q терминалов. Экономия времени возможна в том случае, когда группа является достаточно большой, а среднее количество запросов на услугу невелико. Вычислите время, необходимое для непосредственного опроса группы из 4096 терминалов, с целью предоставления канала связи 100 терминалам. Сравните результат со временем, необходимым для выполнения 100 операций поиска по двоичному дереву для той же группы пользователей. Время, необходимое для опроса одного терминала, и время принятия решения при поиске по двоичному дереву одинаковы и равны 1 с.

б) Выведите уравнение для максимального количества терминалов Q' при котором время непосредственного опроса равно (или меньше) времени поиска по двоичному дереву.

в) Вычислите Q 'для п. а.

Решение

а) Время прямого опроса 4 096 терминалов равно следующему.

Поиск по двоичному дереву для 100 терминалов требует 100 проходов по дереву.

б) Q' является максимальным числом терминалов, при котором в условиях п. а . Это происходит в следующем случае.

(11.30)

Здесь bd — наибольшее целое число, не превышающее х.

в) Q 'для п. а равно следующему.

Поиск по двоичному дереву для 341 терминала требует 4 092 с.




***** Яндекс.Поиск по сайту:



© Банк лекций Siblec.ru
Формальные, технические, естественные, общественные, гуманитарные, и другие науки.