Тема 6 (часть 2) (774448), страница 2
Текст из файла (страница 2)
На рисунке показан процесс отправления запроса и получения подтверждения. В данном примере передакяцей станции необходимо зарезервировать три интервала времени. В подтверждении спутника содержатся инструкции относительно. размещения первого пакета данных. Управление распределено, поэтому все пользователи получают сигнал со спутника и, соответственно, информацию о резервировании и распределении времени.
Поэтому в сигнале-подтверждении спутника находится вся необходимая информация, которая заключается в сообщении о выделении первого временного интервала. Как показано на рис. 11.22, в течение следующего интервала времени станция передает второй пакет. Далее пользователь знает, что следующий интервал состоит из шести ппдынтервалов, в предназначенных для резервирования, поэтому передача информапионных пакетов в тече- ! ние этого времени не нроизводится. Третий (последний) пакет отсылается в течение четвертого интервала.
Если резервирование не производится, система возврагцается в состояние покоя. Поскольку управление выполняется распределенно, все пользователи получаот от спутника информацию об изменении состояния системы и соответствующие синхронизируюшие импульсы. Другие интересные методы резервирования рассмотрены в 112, 13]. 11.3.4. Сравнение производительности систем 8-АЬОНА и й-АЬОНА В главах 3 и 4 качество схемы цифровой модуляции определялось, в основном, зависимостью Рв от Ейг),.
Это особенно полезно, поскольку Ез~й, является нормированным отношением сигнал/иум. Нормированные кривые позволяют сравнивать производи- 701 11.3. Апгооитмы лоспгпа тельность различных схем модуляпин. Для анализа систем множественного доступа используется подобный показатель — зависимость средней задержки от нормированной пропускной способности, На рис. 11.23 представлена идеальная зависимость задермски от пропускной способности Для нормированных значений пропускной способности, 0 < р < 1, время задержки равно нулю, при р = 1 оно неограниченно возрастает, Помимо идеального случая, на рисунке изображена типичная зависимость, а также направление, соответствующее улучшению производительности. Подыитераалы Первый интервал, доступный для передачи зарезераироааииык лакекоа 0 5 1О Полный цикл лсредачиданныи 20 25 ЗО 35 Времялользоаателя Рис.
1222. Пример алюритма АйОНА с использованием резервирования. Передающая станция резервирует три интервала (М = 5 интервалов, и б подынтервалову 0 1 Нормированная пропускная способность, р Рис. Л.ЗЗ. Зависимость времени задержки от пропускной способности На рнс. 11.24 сравниваются зависимости времени задержки от пропускной способности для алгоритмов б-АЬОНА и К-АЬОНА гформат сообщений: два интервала передачи данных и шесть подынтервалов резервирования). Время задержки этих двух систем сравнивают с помощью идеальной кривой. Для пропускной способности р < 0,2 702 М $ й Глава 11. Уплотнение н множестввнный постыл среднее время задержки для системы Б-АЬОНА меньше, чем для системы К-АЬОНА.
В то же время для р, принадлежашего диапазону 0,2 — 0,67, К-А1.0НА превосходит Я-АЬОНА, поскольку у первой среднее время задержки сушественно меньше. В чем причина превосходства схемы 5-АЬОНА при малоинтенсивном обмене данными? Данный алгоритм не требует служебных издержек для резервирования подынтервалов, как в случае К-АЬОНА. Таким образом, при небольших значениях р производительность К-А1.0НА ниже из-за более высоких расходов.
При р > 0,2 конфликтные ситуации и повторная передача данных в системе Б-АЬОНА приводят к тому, что время задержки растет быстрее, чем в случае К-А1.ОНА (и неограниченно возрастает при р = 0,37). При более высоких значениях пропускной способности (0,2 < р с 0,67) служебные издержки схемы К-А1.ОНА полностью окупаются и обеспечивают менее резкое возрастание времени зздержки при росте р. При использовании схемы К-А1.0НА время задержки возрастает до бесконечности при р = 0,67. таО 60 в с Я 60 Э ез 40 20 0 0,2 0,4 0,6 0,8 Пропускная способность, р Рис. Л.24.
Зависимость времени задержки от пропускной еноеобноети. спутниковый канал нри иеяовьзоеании схем 3-АЕОззА и Я-ААРззА Пример 11.2. Использование канала связи а) В качестве меры использования канала выбрана нормированная пропускная способность р. Ее можно найти как отношение успешно переданных данных к полному объему данных (включая отклоненные данные). Найдите нормированную пропускную способность канала связи с максимальной скоростью передачи данных )? = 50 Кбит/с, который используется М = 10 станциями связи, каждая из которых передает данные со средней частотой Х = 2 пакета в секунду. формат системы предусматривает пакеты по Ь = 1350 бит.
б) Применение какой из описанных систем АЬОНА будет оптимальным в данном случае? 703 11.3. Апгооитмы цостчпа ' кь Решение а) Обобщая уравнение (11.!9) для информационною потока чаем следующее: Уб)ч 10(1350)(2) Р= = 0,54. И 50 000 от нескольких станций, пслу- б) В данной системе может исполыоваться только схема К-АЬОНА, поскольку два других алгоритма ие позволяют использовать 54% ресурса. 11.3.5. Методлв опроса 0 1 2 3 4 б 6 7 Терминалы 1, 4 н 6 состяввютсн вв пврвлвчу 000 001 010 011 100 1О! 11О 1! 1 Спутник запрашивает первый бнт идентификатора к 1! 1, Спутник выбирает ответ с максимальной мощностью; выбирает "1" н извещает об этом соствввющнвся станции Спутник запрашивает второй бнт идентификаторе Спутник выбнрввт "0" н извещает об атом соствэвющнвся станции 0 1 Рис.
11.25. Разрешение сасшнзанин между нальзавашвлнии: поиск на дваичнаму дереву Глава 11. Уплотнение и множественный доступ 704 Один из методов упорядочения работы системы произвольного доступа с множественными пользователями состоит во введении контроллера, выявляющего запросы на предос!явление услуг путем периодического опроса всех пользователей. Если количеспю пользователей велико (например, тысячи терминалов), а процесс обмена данными происходит пульсирующим образом, время, выделяемое для опроса всех пользователей, может представлять существенные служебные издержки. Одним из методов быстрого опроса пользователей является поиск ло дваичнаму дереву [4, 14].
На рис. 11.25 представлен пример использования данного метода для реализации "состязания" между пользователями спутниковой связи за обладание ресурсом. Пусть общее число пользователей равно восьми и каждому из них присвоен двоичный код от 000 до ! 11, как показано на рис. 11.25. Предположим, что терминалы 001, 100 и 110 соревнуются за один канал связи. При поиске по двоичному дереву группа пользователей периодически делится пополам, пока не останется лишь одна ветвь дерева. Терминал, соответствующий этой ветви, и получает право первым использовать канал. Затем операция повторяется, и доступ получает следукпций "победитель". Алгоритм поиска состоит из следующих этапов (рис. 11.25). !. Спутник запрашивает у состязаюшихся терминалов первую цифру их двоичных идентификаторов.
2. Терминал 001 передает "0", терминалы 100 и ! 10, соответственно, "1'". Спутник, на основе мощности принятых сигналов, выбирает нуль или единицу. В данном примере бьша выбрана единица, и об этом были проинформированы пользователи. В настоящий момент половина пользователей прекращает состязание.
В данном примере выбывает терминал 001. 3. Спутник запрашивает у оставшихся терминалов вторую цифру идентификационного номера. 4. Терминал !00 передает "0", терминал 110 — "1". 5. Предположим, что спутник выбрал нуль и уведомил об этом пользователей.
Терминал 110 выбывает из состязания. Процесс продолжается до тех пор, пока терминал 100 не получит доступ к спутнику. б. После того как канал связи освобождается, этапы ! — 5 повторяются. Пример 11.3. Сравнение поиска по двоичному дереву и непосредственного опроса а) Поиск по двоичному дереву требует принятия л =!одзи решений при каждом опросе группы из Д терминалов. Экономия времени возможна в том случае, когда группа является достаточно большой, а среднее количество запросов на услугу невелико.
Вычислите время, необходимое для непосредственного опроса группы из 4 090 терминалов, с целью предоставления канаяа связи !00 терминалам. Сравните результат со временем, необходимым для выполнения 100 операций поиска по двоичному дереву для той же группы пользователей.
Время, необходимое для опроса одного терминала, и время принятия решения при поиске по двоичному дереву одинаковы н равны 1 с. б) Выведите уравнение лля максимального количества терминалов Д; при котором время непосредственного опроса равно (или меньше) времени поиска по двоичному дереву. в) Вычислите Д'для п а. Решение а) Время прямого опроса 4 096 терминалов равно следующему: Т = 409б х 1 с = 409б с. Поиск по двоичному дереву для 100 терминалов требует 100 проходов по дереву. Г= (100 х (обз4096) х 1 с = ! 200 с б) Д'является максимальным числом терминалов, при котором в условиях п.
а Т'ВТ. Это происходит в следующем случае: Д"!обзД х 1 сгрешение = !9 х 1 с/опрос. (11.30) Злесь Ы вЂ” наибольшее целое число, не превышающее х. в) Д лля и. а равно следующему: 409б О' = = 341терминал. ~ !оба 409б( Поиск по двоичному дереву для 341 терминала требует 4 092 с. тии 11 Э Апгооитмы погтчпь пакеты генерируются согласно некоторой статистической модели. Пользователи занимают канал, когда у них имеется для передачи один или более пакетов. Когда больше чем один пользователь пытаются передать пакеты одновременно, пакеты перекрываются во времени, т.е. сталкиваются и, следовательно, возникает конфликт, который должен быть разрешен путем использования некоторого канального протокола для повторной передачи пакетов.
Ниже мы опишем несколько канальных протоколов для случайного доступа, которые разрешают конфликт при пакетной передаче. 15.4.1. АЛОХА. Системы и протоколы Предположим, что используется схема случайного доступа, когда каждый пользователь передает пакет по мере его генерации. Когда пакет передан пользователем и никакой другой пользователь не передает пакет на этом интервале времени, тогда пакет считается успешно переданным.
Однако, если один или более других пользователей передают пакет, который перекрывается во времени с пакетом первого пользователя, возникает столкновение и передача неуспешна. Рис.15.4.1 иллюстрирует этот сценарий. Если пользователи знают, когда их пакеты переданы успешно и когда они сталкиваются с другими пакетами, возможно разработать схему, которую мы назовем пропюкол досп~упп и кепки, для ретрансляции столкнувшихся пакетов. (а) (Ь) Наложение Рнс. 15.4.1. Пакетная передача со случайным доступом: (а) пакеты от типнчнооз пользователя (Ь) пакеты от нескольких пользователей Обратная связь к пользователям об успешной или неуспешной передаче пакетов необходима и может быть обеспечена различными путями.
В радиовещательной системе. такой как скажем в спутниковой ретрансляции, как изображено на рнс.15.4.2, пакеты — это' сигналы вещания от многих станций (передатчиков) ко всем пользователям по линии вниз. Все передатчики могут отслеживать их передачи, и, таким образом, получить следующую информацикк ни один пакет не был передан, или пакет был передан успешно, или возникло столкновение.
Этот тип обратной связи к передатчикам обычно обозначается как 1,0, 1, с) обратная связь. В системах, использующих проводные или волоконно-оптические каналы приемник может послать сигнал обратной связи по отдельному каналу. В системе А).ОНА (АЛОХА), изобретенной Абрамсоном (1973,1977) и др. в университете на Гавайях, использовался спутниковый повторитель, который передавал пакеты от различных пользователей, которые имели доступ к спутнику. В этом случае все пользователи могли отслеживать передачи спутника и, таким образом, установить, переданы ли их пакеты успешно или нет. 747 Рис. 15.4.2. Система спутникового вещания В своей основе имеются два типа систем Алоха: синхронизированная (щелевая) и не синхронизированная (бесщелевая). В бесщелевой системе Алоха («чистая» Алоха) пользователь может начинать передачу пакета в любое произвольное время.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
