Алгоритмы беспроводного взаимодействия мобильных станций для совместного использования широковещательного канала

Яськевич Евгений Владиславович ассистент Департамента компьютерной инженерии Московского института электроники и математики им. А.Н.Тихонова национального исследовательского университета «Высшая школа экономики» 123458, Россия, г. Москва, ул. Таллинская, 34 Yas'kevich Evgenii Vladislavovich Assistant of the Department of Computer Engineering of the Tikhonov Moscow Institute of Electronics and Mathematics of the National Research University "Higher School of Economics" 123458, Russia, g. Moscow, ul. Tallinskaya, 34 gniiivm-skur@yandex.ru

Одним из приоритетных направлений развития информационно-телекоммуникационных технологий являются компьютерные сети, использующие беспроводную среду передачи данных ^[1]. Компьютерные сети поддерживают огромное количество приложений и услуг, обеспечивая доступ к мировой информационной сети, передачу цифровых аудио и видео, использование облачных хранилищ и электронной почты и многое другое.

Несмотря на активное развитие беспроводной передачи данных, она не обеспечивает высокую надежность и качество проводных соединений (например, популярная сетевая технология Token Ring использует детерминированный доступ к среде передачи, который позволяет избежать коллизий кадров при подключении и работе в сети, а также гарантирует определенную полосу пропускания для передачи информации) ^[2-5].

Таким образом, актуальной является задача разработки алгоритмов беспроводной сети с маркерным доступом, обеспечивающих детерминированность доступа во избежание коллизий кадров, реализацию поочередного использования радиоканала для передачи данных и мониторинга сети, а также восстановление системы в случае сбоя в работе одного или нескольких узлов. К числу таких алгоритмов относятся: алгоритм формирования сети; алгоритм передачи данных внутри сети с использованием многоканальности; алгоритм обработки отказа абонентского оборудования и алгоритм автоматического восстановления сети.

Разработка алгоритмов основана на двух известных решениях, каждое из которых в наибольшей степени обладает отдельными необходимыми качествами, однако не сочетает в себе их всех одновременно: технология локальной вычислительной сети кольца с маркерным доступом Token Ring, и стандарт связи для коммуникации в беспроводной среде Wi-Fi ^[6-9].

Преимущества Token Ring: отсутствие коллизий в сети; детерминированность доступа, а недостатки ‑ общие задержки, связанные с передачей маркера; высокая стоимость ^[10-14].

Преимущества Wi-Fi: позволяет развернуть сеть без прокладки кабеля, что может уменьшить стоимость развёртывания и/или расширения сети; позволяет иметь доступ к сети мобильным устройствам; частоты волн Wi-Fi абсолютно безопасны для человека и не дают помех; Wi-Fi-устройства широко распространены на рынке; гарантируется совместимость оборудования благодаря обязательной сертификации оборудования с логотипом Wi-Fi ^{[6, 15-17]}. Недостатками Wi-Fi являются: воздействие естественных преград на качество и дальность распространения сигнала; дальность и скорость передачи Wi-Fi зависит от наличия и интенсивности радиопомех; шифрование Wi-Fi относительно слабо защищено от взлома ^{[6, 15-17]}.

Таким образом, можно сделать вывод о том, что Token Ring не хватает мобильности, а Wi-Fi ‑ надежности. Для разработки названных выше алгоритмов использованы преимущества каждого из них с нивелированием недостатков. У Wi-Fi позаимствованы мобильность и удобство развертывания, а у Token Ring ‑ топология и маркерный доступ. Стоит отметить, что логическая кольцевая топология Token Ring вовсе не обязывает использовать физическую кольцевую топологию: физическая топология типа «звезда» позволит обеспечить большую надежность с точки зрения обработки ситуаций отказов абонентского оборудования.

Проектирование системы

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

Рис. 1. Физическая топология «звезда»

Обмен информацией в сети осуществляется только при наличии у пользователя особого пакета – маркера (токена), разрешающего узлу осуществлять передачу данных. Права на генерацию и обновление маркера имеет только монитор. Этот токен последовательно передается по логическому кольцу (рис. 2). Если узлу необходимо передать данные, то он удерживает этот маркер на время передачи данных, но не дольше отведенного времени, а в случае, если данных на передачу нет – сразу передает токен следующему абоненту.

Рис. 2. Последовательная передача маркера по логическому кольцу

Во время работы сети могут возникнуть ситуации, когда появляется необходимость разделить сеть на подсети. Например, для разделения абонентов на бригады, или же, в случае, когда абоненты сети распределились широко по местности и не входят в зону покрытия одного монитора. В этом случае происходит объединение подсетей в «суперкольцо». Это такой способ соединения, когда абоненты распределяются по подсетям (отдельным кольцам), а мониторы этих колец, в свою очередь, тоже объединяются в «суперкольцо». Это позволяет всем абонентам находиться в одной распределенной сети и передавать данные через «суперкольцо» даже между самыми удаленными пользователями.

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

Если один абонент хочет подключиться к другому, то он проводит запрос на подключение. В случае согласия инициатор формирует маркер и передает его второму участнику. Таким образом, они формируют сеть из двух станций, где инициатор становится монитором. Монитор формирует таблицу маршрутизации, которая описывает последовательность получения маркера абонентами. В дальнейшем обработкой запросов на подключение занимается монитор.

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

Если абонент, который пытается подключиться к сети, является монитором другой сети, то возможны три варианта подключения:

- переход абонента в другую сеть;

- объединение сетей с помощью «суперкольца»;

- слияние сетей в единую сеть.

В случае перехода монитора в другую сеть он передает свои полномочия другому пользователю, отключается от своей сети и подключается к новой как рядовой пользователь.

При объединении сетей с помощью «суперкольца» монитор одной сети посылает запрос на подключение монитору другой сети. В случае согласия инициатор подключения формирует маркер «суперкольца» и посылает его монитору второй сети.

При слиянии в одну сеть монитор второй сети посылает запрос на подключение монитору первой сети. В случае согласия монитор второй сети отсылает данные своей таблицы маршрутизации монитору первой сети и становится рядовым абонентом наравне со всеми остальными абонентами своей сети (рис. 3).

Рис. 3. Блок-схема алгоритма формирования сети

Стоит отметить, что все подключения (точка – точка, монитор – точка, монитор – монитор) происходят только тогда, когда оба участника процесса находятся в зонах покрытия друг друга. В «суперкольце» только соседние мониторы обязаны быть в зонах покрытия друг друга, чтобы была возможность передавать данные последовательно по кольцу.

Алгоритм передачи данных внутри сети с использованием многоканальности

Разделение по каналам осуществляется с помощью частотного разделения канала на подканалы.

Если разделение на независимые подсети происходит на одном устройстве (рис. 4), то на каждом канале используются свой маркер и собственные таблицы маршрутизации.

Рис. 4. Разделение по каналам на одном устройстве

В каждой подсети абоненты передают данные между собой. Если абоненту подсети A (на канале 1, например) необходимо передать данные абоненту из подсети B (на канале 2), то маршрутизатор переносит запись этого абонента из таблицы маршрутизации подсети A (на канале 1) в таблицу маршрутизации подсети B (на канале 2) и сообщает абоненту о необходимости переключиться на канал 2. Таким образом, станции оказываются в одной подсети и могут осуществить передачу данных.

Если разделение на независимые подсети происходит на разных устройствах (рис. 5), то на каждом канале используются свой маркер и собственные таблицы маршрутизации, а мониторы подсетей соединены в «суперкольцо».

Рис. 5. Разделение по каналам на разных устройствах

Все мониторы «суперкольца» поддерживают таблицу маршрутизации «суперкольца» в актуальном состоянии, т.е. после полного цикла, пройденного маркером, каждый монитор «знает» о существовании всех остальных. Это важная составляющая устойчивости сети к отказам оборудования и самовосстановления. Для передачи данных между абонентами, находящимися в разных подсетях (на разных каналах) можно применить два возможных алгоритма. Выбор одного из них обусловлен возможными задержками при передаче из-за ожидания маркера.

Первый вариант, по аналогии со случаем, когда маршрутизация всех каналов осуществляется одним устройством, заключается в «перебросе» пользователя в другую подсеть (на другой канал), где находится адресат. Второй вариант – источник передает данные монитору своего канала, который передает их монитору канала адресата по «суперкольцу» при получении маркера «суперкольца». Монитор канала адресата, получив эти данные, передает их адресату в тот момент, когда ему необходимо передать адресату маркер подсети согласно таблице маршрутизации.

Выбор одного из этих вариантов обусловлен объемом данных, которые требуется передать, и временем, которое требуется на их передачу. Для варианта передачи данных через «суперкольцо» стоит участь, что потребность передать данные абонентам из другой подсети может возникнуть сразу у нескольких (в самом худшем случае у всех) абонентов данной подсети. Таким образом, они все будут передавать данные маршрутизатору подсети, которые неизбежно будут на нем накапливаться, т.е. становиться в очередь, так как сам маршрутизатор должен обладать маркером «суперкольца», чтобы передать данные маршрутизатору другой подсети. Если объем данных конкретного абонента, которые требуется передать, достаточно велик, то издержки на переключение данного абонента на канал адресата могут оказаться существенно меньше, чем задержки передачи этих данных через «суперкольцо», особенно учитывая очередь на маршрутизаторе. Переключение абонента на канал адресата позволит им обмениваться данными внутри одной подсети, что позволяет существенно сократить задержки между ними, так как маршрутизация передачи маркера внутри одного канала (подсети) полностью прозрачна и осуществляется в пассивном режиме. Однако, стоит отметить, что этот вариант возможен только в случае, если зоны покрытия монитора подсети адресата достаточно, чтобы принять в подсеть отправителя.

Алгоритм обработки отказа абонентского оборудования

Если произошел отказ оборудования станции и узел сети не отвечает, то возможны три исхода развития событий (рис. 6): жесткое отключение абонента, предоставление второго шанса на ответ, игнорирование проблемы.

Если указанный абонент не отвечает в течение таймаута (заданного промежутка времени до начала принятия мер), то: при жестком отключении он выкидывается из таблицы маршрутизации, при использовании второго шанса перемещается в её конец, при игнорировании проблемы маркер просто отправляется следующему абоненту.

Рис. 6. Алгоритм обработки отказа абонентского оборудования

Алгоритм автоматического восстановления сети

В случае, если абонент вышел из зоны покрытия монитора сети и потерял сигнал, как следствие потерял возможность передавать и получать информацию и не смог завершить передачу данных, могут быть приняты меры по восстановлению передачи с места «разрыва». Абонент «потерялся», следовательно, он не вернул маркер. Монитор зафиксировал то, что передача данных не завершилась, а сеанс завершился таймаутом (превышением допустимого времени ответа). Как только «потерявшийся» окажется в зоне досягаемости сигнала монитора и попробует восстановить соединение с сетью, в случае согласия, монитор вернет ему маркер (согласно установленной после прерывания связи последовательности) и сообщит с какого места необходимо возобновить передачу данных.

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

Анализ эффективности предлагаемых решений

Для простоты построения аналитической модели на данном этапе проектирования не будем учитывать влияние внешней среды. Условия будем считать близкими к идеальным. Введем несколько переменных ^[18-21]:

n – количество абонентов;

t0 – среднее время запроса от пользователя к монитору;

tобр – время обработки запроса;

Рмон – вероятность обратиться напрямую к монитору с запросом на подключение;

Tф – время формирования кольца;

Tк – время обхода кольца;

Pм – случайная биномиальная величина, которая характеризует наличие посредника при подключении нового абонента в сеть. Если новый абонент направил запрос на подключение участнику сети, то величина равна 1, если обратился напрямую к монитору – 0.

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

Время формирования сети рассчитывается как:

.

Время отклика в сети измеряется в миллисекундах, в то время как время выполнения операции микроконтроллером или микропроцессором – в микросекундах и даже наносекундах.

Для проверки формулы подставим в нее пробные ориентировочные данные (соответствующие реальным данным): t0 = 15 мс, tобр = 10 мкс, n = 25.

Таблица 1

Изменение времени формирования сети и времени обхода кольца сети в зависимости от количества узлов

Таким образом получаем, что при формировании сети время формирования возрастает линейно от количества абонентов (табл. 1). Формирование сети из 25 абонентов происходит примерно за 1 секунду.

Время обхода кольца:

для тех же данных представлено в табл. 1

Как видно из табл. 1 с увеличением количества абонентов время обхода кольца возрастает линейно и при 25 абонентах занимает менее секунды.

Заключение

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