Software & Systems

Значительное увеличение на дорогах количества транспортных средств в последние десятилетия обусловило существенный рост дорожно-транспортных происшествий. Это побудило ученых искать новые технологии для обеспечения более высокого уровня безопасности, дающие возможность получать полную информацию о дорожных условиях (загруженных или пустых) и о чрезвычайных ситуациях, требующих быстрого вмешательства для оказания помощи. В силу значительного расширения наземных дорог во всех точках мира на построение традиционных сетей для достижения этой цели необходимы серьезные материальные ресурсы, что делает создание традиционной сети практически невозможным. Все это обусловило появление сетей VANET в составе Ad-hoc-сети [1]. VANET – децентрализованные сети, не нуждающиеся в предварительно установленных устройствах на дорогах, скорее, они создаются самими автомобилями. Их стоимость очень низкая, но они страдают от проблемы выбора соответствующего протокола, который должен успешно управлять этой сетью. Поэтому были выбраны протоколы маршрутизации, применяемые в сетях MANET, изучены их производительность и работа в среде VANET [2]. Сравним производительность некоторых протоколов маршрутизации MANET в среде VANET.

В большинстве исследований производительность протоколов оценивалась на малом количестве узлов и не учитывалось, что большой размер сети может изменить результаты и снизить ее производительность. Кроме того, лучший протокол в MANET необязательно будет лучшим в VANET. Следовательно, предыдущие исследования не дают точной оценки протоколов в VANET. В [3] автор оценил производительность некоторых традиционных протоколов маршрутизации – AODV, DSDV, OLSR и GPSR. Результаты показали, что OLSR превосходит AODV, DSDV и GPSR в предложенном сценарии с использованием сетевого симулятора 2 (NS2). В работе [4] оцениваются четыре показателя производительности с помощью сетевого симулятора 2 (NS2) в зависимости от различных условий (мобильность узлов, плотность сети). Результаты показали, что OLSR имеет самую низкую производительность с точки зрения коэффициента доставки пакетов, чем AODV, во всех моделях и в целом AODV имеет лучшую производительность в сетях с более высокой мобильностью и большим количеством узлов. В [5] автор использовал SUMO и NS3 для оценки производительности протоколов маршрутизации VANET. Судя по результатам, производительность OLSR была лучшей для предложенного сценария с точки зрения PDR и пропускной способности, в то время как GPSR и GPCR – лучшими двумя маршрутами в случае накладных расходов и задержки E2E.

Обзор существующих протоколов маршрутизации

Протоколы маршрутизации определяют способы обмена пакетами между узлами в приемлемый период времени. В Ad-Hoc-сетях протоколы маршрутизации делятся на три основные группы: проактивные, реактивные и гибридные. В статье [5] авторы рассмотрели протоколы проактивной маршрутизации, чтобы изучить влияние реализации протоколов DSDV и OLSR на производительность сети VANET, и сравнили показатели их производительности.

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

Некоторые особенности проактивных протоколов [3, 4]:

-     большинство узлов имеют обновленную таблицу маршрутизации, то есть они знают топологию сети и распределение узлов в ней;

-     нет необходимости в сетевых ресурсах, чтобы обнаружить маршрут от источника до пункта назначения;

-     периодически обновляется информация о маршрутах с целью избежания больших задержек при обнаружении маршрута к назначению в случае необходимости.

Основными слабыми сторонами этих протоколов являются следующие [3, 4]:

-     периодическое обновление таблиц маршрутизации приводит к большому расходу пропускной способности сети;

-     не подходят для Ad-Hoc-сетей с высокой плотностью, поскольку это может привести к увеличению трафика.

Проактивные протоколы – OLSR, DSDV, маршрутизация состояния «рыбий глаз» (FSR) и протокол беспроводной маршрутизации (WRP).

Проактивный протокол маршрутизации DSDV построен на традиционном алгоритме Беллмана–Форда, при этом улучшены методы маршрутизации для адаптации к специальным мобильным сетям. Узлы сохраняют таблицу маршрутизации для всех узлов в сети, чтобы помочь узлу узнать топологию сети [7].

Таблица маршрутизации содержит информацию о каждом узле [8]:

-     IP-адрес;

-     последний порядковый номер;

-     количество прыжков до узла назначения;

-     информация о первом хопе для достижения узла назначения;

-     время последнего обновления таблицы маршрутизации узла.

Существуют два типа обновления узлом своей таблицы маршрутизации: добавочное и периодическое [1, 8].

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

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

OLSR – это протокол упреждающей маршрутизации на основе таблиц для мобильных Ad-Hoc-сетей. Протокол использует алгоритм состояния канала и имеет преимущество сохранения предварительно доступных путей, которые используются при необходимости из-за их проактивного характера [7].

OLSR характеризуется выбором промежуточных узлов, называемых многоточечными ретрансляторами (MPR). Этот узел выполняет задачу пересылки данных в сети для уменьшения накладных расходов узлов, отправляющих обновленные данные в сети, чтобы предотвратить их сброс, что считается одним из наиболее важных недостатков протоколов проактивной маршрутизации. MPR выбираются некоторыми из соседних узлов. MPR-узлы периодически публикуют информацию, которая связывает их с остальными узлами в своих управляющих сообщениях. Таким образом, все узлы имеют информацию о том, как получить доступ к узлу назначения через MPR. Узлы, использующие протокол проактивной маршрутизации OLSR, отправляют информацию на узел назначения через MPR промежуточного ПО и находятся в контакте со всеми сетевыми узлами. Таким образом, промежуточные узлы изучают путь к узлам назначения и его эффективность среди других доступных опций: передать данные по старому пути как есть или скорректировать его на лучший путь в случае изменения топологии сети [4].

Для выполнения этих задач узлы рассылают несколько типов сообщений [4].

·     Сообщения HELLO. Задача этих сообщений – собрать информацию о соседних узлах. Они представляют собой только один переход.

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

·     Сообщения множественного объявления интерфейса (MID). Передаются всеми сетевыми узлами, чтобы объявить их множествен-ные интерфейсы с их обновленными адресами в сети.

·     Сообщения хоста и сетевой ассоциации (HNA). Это сообщения о внешней маршрутизации, например, о сетевых и других адресах.

Методология моделирования и сценариев

Авторы данного исследования стремились смоделировать поведение протоколов маршрутизации при различных условиях, количестве узлов и скоростной мобильности в транспортных средствах для изучения показателей производительности сети: отношение пакетов к доставке (PDR), пропускная способность, накладные расходы, коэффициент потери пакетов и задержка в сети VANET. Все симуляции проводились с помощью сетевого симулятора NS3. Была также использована модель мобильности Manhattan Grid с помощью инструмента Bonnmotion, который широко применяется для описания мобильности узлов VANET.

Для измерения эффективности двух протоколов в сетях VANET необходимо измерить ряд показателей.

1.    Коэффициент доставки пакетов (PDR). Это отношение количества пакетов, успешно достигших своей цели, о которых знает отправляющий узел:

коэффициент доставки пакетов = (количество полученных пакетов/общее количество отправленных пакетов)×100.

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

коэффициент потери пакетов = (количество потерянных пакетов/общее количество отправленных пакетов)×100.

3.    Пропускная способность. Определяется как количество пакетов, полученных в пункте назначения, из общего числа переданных пакетов (используемая единица – кбит/с):

пропускная способность = Размер пакета × полученные пакеты × 8/100.

4.    Средняя задержка. Общее время передачи пакета от источника к узлу назначения известно как сквозная задержка. Показатель производительности задержки включает задержки из-за обнаружения маршрута, распространения и отправки пакета, а также время ожидания па-кета в очереди:

средняя задержка = S(время получения пакета данных – время отправления пакета данных) ¸ общее количество полученных пакетов.

5.    Накладные расходы. Это отношение количества пакетов, которым не удалось достичь своей цели, то есть они не достигли целевого узла или достигли, но не могут знать отправляющий узел, что связано с несколькими причинами, включая потерю сигнала или неожиданную перегрузку:

накладные расходы = общее количество пакетов маршрутизации / общее количество полученных пакетов данных.

Анализ производительности

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

1.    Влияние количества автомобилей.

Осуществлена оценка производительности протоколов DSDV и OLSR в VANET для различных сценариев с 50, 100, 150, 200, 250 автомобилями.

На рисунке 1 показаны коэффициенты доставки пакетов (PDR) для протоколов маршрутизации DSDV и OLSR при разном количестве транспортных средств. Все протоколы имеют одинаковый коэффициент доставки пакетов при изменении количества узлов, но в случае 250 узлов производительность OLSR немного лучше, чем DSDV.

Анализ общей кривой оценки производительности (рис. 2) показал, что более высокая пропускная способность достигается протоколом маршрутизации OLSR. Он превосходит DSDV с точки зрения пропускной способности благодаря хорошему управлению маршрутизацией с использованием метода многоточечной ретрансляции (MPR) [4]. Оба протокола обеспечивают лучшую пропускную способность для меньшего количества узлов при мобильности.

На рисунке 3 представлена средняя задержка для разного количества транспортных средств и протоколов маршрутизации. Можно заметить, что наименьшая средняя задержка у OLSR. При этом DSDV достиг на 27 % большего значения задержки, чем OLSR, с увеличенным размером в сети на 250 автомобилей.

Накладные расходы для различного количества транспортных средств и протоколов маршрутизации показаны на рисунке 4. Как видим, они растут с увеличением количества транспортных средств как для протокола DSDV, так и OLSR, поскольку генерируют большое количество накладных расходов пакетов. DSDV имеет большие накладные расходы на маршрутизацию из-за дополнительных сообщений управления маршрутизацией для обновления таблиц маршрутизации, в то время как OLSR имеет меньшие накладные расходы на маршрутизацию из-за меньшего количества повторных передач [8] и использования метода MPR, который снижает накладные расходы на маршрутизацию [5].

На рисунке 5 отображены коэффициенты потери пакетов для протоколов проактивной маршрутизации DSDV и OLSR и разного количества транспортных средств в сети. Можно наблюдать, что коэффициент потери пакетов увеличивается с ростом количества узлов в сети. Анализ результатов показал, что PLR VANET резко возрастает по мере увеличения количества узлов.

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

2.    Влияние скорости автомобиля.

Авторы проанализировали и оценили производительность протоколов AODV и DSR в VANET для различных сценариев с 50 автомобилями и скоростью 10, 20, 30, 40 и 50 м/с.

Результаты изменения скорости с 50 узлами показали, что увеличение скорости узла влияет на все параметры производительности сети, то есть увеличение скорости приводит к снижению эффективности протоколов. Что касается производительности DSDV в зависимости от скорости автомобиля, то коэффициент доставки пакетов снизился на 9 %, таким образом, коэффициент потери пакетов увеличился на 9 %. Средняя задержка в сети увеличилась почти на 125 %, накладные расходы –  на 86 %, тогда как пропускная способность снизилась на 6 %. Относительно OLSR коэффициент доставки пакетов снизился на 10 %, что увеличило коэффициент потери пакетов на 10 %. Средняя задержка в сети увеличилась почти на 150 %, накладные расходы – на 89 %, тогда как пропускная способность снизилась на 4 % (см. http://www.swsys.ru/uploaded/image/2021-3/2021-3-dop/1.jpg).

Заключение

Основная ценность данной работы состоит в аргументированной сравнительной характеристике эффективности применения распространенных протоколов маршрутизации для сетей VANET с использованием симуляторов Bonnmotion и NS3. Выявлены различия между популярными протоколами проактивной маршрутизации – DSDV и OLSR, проведено сравнение протоколов маршрутизации друг с другом в VANET. Авторы исследования сосредоточились на оценке влияния изменения количества узлов и скорости узла на производительность сети, изучили зависимость протокола маршрутизации от большого размера сети и высокой мобильности VANET.

Выяснено, что производительность двух протоколов в случае изменения скорости и стабильность количества узлов незначительно пострадали, но в случае увеличения количества узлов протокол OLSR оказался более эффективным, чем протокол DSDV в VANET. Хотя эти протоколы основаны на двух разных методах работы – протокол OLSR полагается на алгоритм состояния канала, а DSDV на алгоритм Беллмана–Форда, их производительность очень схожа. Ряд особенностей, пересекающихся со множеством малоизученных вопросов непостоянства структуры и состава сетей VANET, представляют собой основу для будущих исследований.

Литература

1.    Spaho E., Ikeda M., Barolli L., Xhafa F., Younas M., Takizawa M. Performance evaluation of OLSR and AODV protocols in a VANET. Proc. IEEE XXVII AINA Conf., 2013, pp. 577–582.

2.    Jain M., Saxena R. Overview of VANET: Requirements and its routing protocols. Proc. ICCSP, 2017, pp. 1957–1961. DOI: 10.1109/ICCSP.2017.8286742.

3.    Bhangwar N., Halepoto I., Sadhayo I., Khokhar S., Laghari A. On routing protocols for high performance. Studies in Informatics and Control, 2017, vol. 26, no. 4, pp. 441–448. DOI: 10.24846/v26i4y201708.

4.    Zougagh H., Toumanari A., Rachid L., Idboufker N., Yousef M. A performance comparison of routing protocols for ad hoc networks. IJERA, 2014, vol. 4, no. 9, pp. 124–131.

5.    Bengag A., Elboukhari M. Performance evaluation of VANETs routing protocols using SUMO and NS3. Proc. Intern. IEEE CiSt, 2018, pp. 525–530. DOI: 10.1109/CIST.2018.8596531.

6.    Afolayan A., Oyenike M. Review of Mobile Ad Hoc Network Protocols. IOSR-JCE, 2015, vol. 17, no. 2, pp. 1–12.

7.    Gómez C., García D., Paradells J. Improving performance of a real ad hoc network by tuning OLSR parameters. Proc. X IEEE ISCC, 2005, pp. 16–21. DOI: 10.1109/iscc.2005.83.

8.    Rao G., Jagadeeswararao E., Priyanka U., Indira T. Performance analysis of MANET routing proto-cols – DSDV, DSR, AODV, AOMDV using Ns-2. GJCST, 2015, vol. 15, no. 6, pp. 1380–1384.

References

1. Spaho E., Ikeda M., Barolli L., Xhafa F., Younas M., Takizawa M. Performance evaluation of OLSR and AODV protocols in a VANET. Proc. IEEE XXVII AINA Conf., 2013, pp. 577–582.

2. Jain M., Saxena R. Overview of VANET: Requirements and its routing protocols. Proc. ICCSP, 2017, pp. 1957–1961. DOI: 10.1109/ICCSP.2017.8286742 .

3. Bhangwar N., Halepoto I., Sadhayo I., Khokhar S., Laghari A. On routing protocols for high performance. Studies in Informatics and Control , 2017, vol. 26, no. 4, pp. 441–448. DOI: 10.24846/v26i4y201708 .

4. Zougagh H., Toumanari A., Rachid L., Idboufker N., Yousef M. A performance comparison of routing protocols for ad hoc networks. IJERA, 2014, vol. 4, no. 9, pp. 124–131.

5. Bengag A., Elboukhari M. Performance evaluation of VANETs routing protocols using SUMO and NS3. Proc. Intern. IEEE CiSt, 2018, pp. 525–530. DOI: 10.1109/CIST.2018.8596531 .

6. Afolayan A., Oyenike M. Review of Mobile Ad Hoc Network Protocols. IOSR-JCE, 2015, vol. 17, no. 2, pp. 1–12.

7. Gómez C., García D., Paradells J. Improving performance of a real ad hoc network by tuning OLSR parameters. Proc. X IEEE ISCC, 2005, pp. 16–21. DOI: 10.1109/iscc.2005.83 .

8. Rao G., Jagadeeswararao E., Priyanka U., Indira T. Performance analysis of MANET routing proto-cols – DSDV, DSR, AODV, AOMDV using Ns-2. GJCST, 2015, vol. 15, no. 6, pp. 1380–1384.