Автоматика и телемеханика, № 5, 2012
Стохастические системы, системы массового обслуживания
© 2012 г. А.Г. КИРЬЯНОВ, А.И. ЛЯХОВ, д-р техн. наук, А.А. САФОНОВ, канд. техн. наук, Е.М. ХОРОВ
(Институт проблем передачи информации им. А.А. Харкевича РАН, Москва)
МЕТОД ОЦЕНКИ ЭФФЕКТИВНОСТИ МЕХАНИЗМОВ УПРАВЛЕНИЯ СОЕДИНЕНИЯМИ В БЕСПРОВОДНЫХ САМООРГАНИЗУЮЩИХСЯ СЕТЯХ1
Предложен оригинальный метод оценки эффективности алгоритмов открытия и закрытия соединений в беспроводных самоорганизующихся сетях (mesh-сетях). Метод применен для построения математической модели алгоритма, стандартизованного в спецификации mesh-сетей IEEE 802.11s. Показано, что предложенный метод является достаточно общим и может быть использован для построения моделей других алгоритмов управления соединениями.
1. Введение
Концепция самоорганизации беспроводной сети, т.е. ее автоматического построения и перестроения при включении, выключении или перемещении станций, востребована в самых разных областях: при организации "умного дома" или сети Internet of Things; для организации связи между транспортными средствами (сети Vehicle Ad Hoc Networks или VANET); при развертывании сети операторского класса для предоставления услуг доступа в Интернет; для оперативного развертывания сетей связи специальных служб в местах аварий и катастроф.
Фундаментальной задачей во всех самоорганизующихся сетях, или mesh-сетях, является формирование сети в результате работы протокола обнаружения соседних станций, установления и поддержания логических соединений с ними. Логическое соединение между соседними станциями сети открывается только при приемлемом качестве передачи. В противном случае маршрутизация пакетов по соединениям с низким качеством приводит к частым потерям пакетов и их повторным передачам, существенно снижающим емкость сети. Мобильность станций сети приводит к постоянному изменению качества соединений и необходимости открытия новых соединений, когда стан-
1 Работа выполнена в рамках проекта FLAVIA FP7.
ции сближаются, и закрытия соединений при ухудшении качества передачи в результате удаления станций друг от друга.
Принятие решений об открытии или закрытии (изменении состояния) соединения происходит на основе обмена специальными служебными пакетами между соседними станциями. Очевидно, время на принятие таких решений должно быть по возможности минимально. С другой стороны, вероятность правильной оценки состояния соединения между станциями mesh-сети повышается вместе с временем, отводимым на такую оценку. Недостаток времени оценки приводит к нестабильности и ненадежности соединений и, в конечном счете, к высокой вероятности ошибок при передаче данных по таким соединениям.
В сентябре 2011 г. опубликована спецификация IEEE 802.11s [1], содержащая описание сетевых алгоритмов и протоколов mesh-сети на базе широко известных устройств стандарта IEEE 802.11 [2], используемого повсеместно под торговой маркой Wi-Fi. За управление соединениями отвечает специальный сетевой протокол Peering Management Protocol (PMP), описывающий процедуру обмена служебными кадрами для открытия и закрытия соединения с соседними станциями сети. Решение о запуске этой процедуры основывается на результате анализа последовательности принятых пакетов синхронизации, называемых также биконами, которые каждая станция сети генерирует периодически [3]. Однако вопрос о том, как именно проводить такой анализ, и соответственно вопрос выбора стратегии управления соединениями оставлены открытыми. Предложенный в данной работе метод позволяет оценивать эффективность решений об открытии и закрытии соединений для широкого класса стратегий.
В связи с тем, что спецификация IEEE 802.11s опубликована совсем недавно, работ, посвященных анализу протокола PMP, еще не появилось. Однако можно выделить несколько исследований [4, 5] механизма управления соединениями, входящего в состав известной спецификации OLSR [6], в основу которого также положен регулярный обмен служебными кадрами, называемыми HELLO-сообщениями и выполняющими ту же функцию, что и биконы.
В [4] в сети под управлением протокола OLSR варьируется интервал между двумя последовательными HELLO-сообщениями и оценивается емкость сети. При уменьшении интервала происходит быстрое обнаружение соседей, но резко возрастает объем служебного трафика: большое число HELLO-сообщений приводит к значительной загрузке сети и, как следствие, уменьшению емкости сети.
В [5] для сетей с высокой мобильностью станций предложено использовать укороченные HELLO-сообщения, передавать такие сообщения с большей частотой, чем сообщения стандартной длины, и считать соединение между станциями открытым или закрытым соответственно при получении или пропуске одного HELLO-сообщения. Такая стратегия увеличивает скорость реакции протокола на изменение топологии сети. Однако принятие решения по одному полученному или пропущенному сообщению приводит к частым изменениям состояния соединения, что негативно сказывается на возможности его использования для маршрутизации пакетов.
В этих работах эффективность механизма управления соединениями (МУС) оценивается методами имитационного моделирования на основе таких интегральных показателей, как емкость сети, средняя задержка при доставке пакета от источника до получателя и т.д. В этом случае эффективность собственно МУС оценивается лишь косвенно, так как на емкость сети, в частности, влияет множество факторов, не связанных с работой МУС, например, применяемый протокол маршрутизации.
Одна из первых попыток разработки аналитической модели МУС и оценки эффективности собственно МУС предпринята в [7]. В этой работе вводятся такие понятия, как задержка при открытии соединения (интервал времени между попаданием станции в область уверенного приема другой станции и моментом установления соединения между ними), задержка при обнаружении разрыва соединения (интервал времени между моментом физического разрыва соединения и логическим закрытием соединения обеими станциями), время жизни соединения (интервал времени между открытием и закрытием соединения), и исследуются различные схемы передачи биконов. Рассмотрены схемы, в которых интервал передачи биконов фиксирован и когда он имеет экспоненциальное распределение. Показано, что схема с фиксированным интервалом эффективнее с точки зрения предложенных показателей. Недостатком работы является принятая в ней грубая модель распространения сигнала: когда станции сближаются на заданное расстояние, вероятность успешного приема бикона скачкообразно изменяется от нуля до единицы. Кроме того, не учтены возможные коллизии биконов. Таким образом, вероятность успешного приема бикона может принимать лишь два значения: нуль или единицу.
В данной работе предложен метод оценки эффективности МУС, не зависящий от модели распространения сигнала и соответственно характера зависимости вероятности успешного приема бикона от расстояния между станциями. Метод основан на построении математической модели алгоритма открытия и закрытия соединений для оценки оригинальных показателей эффективности собственно МУС, а не mesh-сети в целом. Метод применен для построения математической модели алгоритма, стандартизованного в спецификации IEEE 802.11s [1].
В работе также показано, что предложенный метод оценки эффективности МУС является достаточно общим и может быть использован для построения моделей широкого класса алгоритмов управления соединениями. В частности, в работе предложен оригинальный алгоритм, являющийся модернизацией алгоритма МУС в спецификации IEEE 802.11s, и на основе разработанного метода проведен сравнительный анализ указанных алгоритмов.
Описание исследованных в работе алгоритмов приведено в разделе 2. В разделе 3 предложены оригинальные показатели эффективности МУС. В разделе 4 построены математические модели алгоритмов принятия решения об открытии/закрытии соединения, описанных в разделе 2. С помощью этих моделей в разделе 5 показано, что предложенный в работе оригинальный алгоритм представляет собой парето-улучшение известного алгоритма, включенного в спецификацию IEEE 802.11s.
2. Анализируемые алгоритмы управления соединениями 2.1. Алгоритм с безусловным подтверждением
В спецификацию IEEE 802.11s включена следующая процедура открытия и закрытия соединений. Для открытия соединения с соседней станцией станция отправляет служебный кадр Peering Open Frame, а также отвечает на полученный от соседней станции такой же кадр кадром Peering Confirm Frame (см. рис. 1). Для закрытия соединения станция отправляет станции, с которой соединение открыто, служебный кадр Peering Close Frame. Доставка всех служебных кадров подтверждается, и кадры, на которые не получено подтверждение, повторяются. Поэтому служебные кадры доставляются с вероятностью, близкой к единице, и состояние соединения с высокой вероятностью на обеих станциях оказывается синхронизованным.
В спецификации IEEE 802.11s оставлен открытым вопрос о том, когда именно выполняется данная процедура. В данной работе проанализирован класс алгоритмов, основанных на следующих правилах.
1. Станция принимает решение об открытии соединения с соседней станцией, получив от нее подряд r биконов.
2. Станция принимает решение о закрытии существующего соединения, если не получила от станции, с которой открыто соединение, подряд s биконов.
3. Получив кадр Peering Open Frame или Peering Close Frame от соседней станции, станция всегда и без дополнительных проверок качества соединения, т.е. безусловно, соглашается на соответственно открытие или закрыта соединения.
Такой алгоритм используется, например, в реализации драйвера Linux Wireless [8], в котором принято r = 1, а значение s оставлено настраиваемым
параметром. Алгоритм с безусловным подтверждением реализован также в широко известной среде имитационного моделирования NS-3 [9] с параметрами по умолчанию r = 1,s = 5. Похожий алгоритм используется в протоколе TBRPF [10].
2.2. Алгоритм с условным подтверждением
Изменим третье правило алгоритма с безусловным подтверждением следующим образом: станция A, получив от соседней станци
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.