Сетевое издание
Международный студенческий научный вестник
ISSN 2409-529X

THE SIMULATION OF ROUTING IN WIRELESS MESH NETWORKS

Kazakov E.N. 1
1 Voronezh Institute of High Technologies
Mesh networks are decentralized wireless networks that do not have permanent structure. Owing to its features of mesh networks require special routing algorithms. In mesh networks, there are additional difficulties. First of all, the network topology can be irregular. Also in mesh networks depending on the routing target may be a situation where it is difficult to determine the route only on the network topology. Routing metric in mesh networks develop for the purpose of boosting the performance of routing protocols. For mesh-networks require efficient and not resource-intensive routing algorithms that satisfy primarily the performance requirements. The work introduces a generalized algorithm to implement the process of message transfer in the simulation model based on constructed and marked network model. The structure of the program.
wireless network
routing algorithm
simulation model

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

Среди одной из них можно выделить технологию реализации беспроводных mesh-сетей [1, 2], которые отвечают дополнению стандарта 802.11 – 802.11s. Mesh-сети дают возможности увеличения области беспроводных покрытий вследствие вовлечения тех узлов, которые передают данные, в процессы маршрутизации. Это ведет к тому, что сокращается число требуемых точек доступа и возрастает территория с беспроводным доступом.

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

Основываясь на этом, оценка параметров производительности различных протоколов представляется очень важной задачей.

Mesh-сети относятся к классу ad hoc сетей (среди других названий говорят о беспроводных самоорганизующихся сетях, беспроводных динамических сетях) – относятся к децентрализованным беспроводным сетям, которые не содержат постоянной структуры.

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

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

В этом заключается то, каким образом отличаются проводные и беспроводные сети, а также и управляемых беспроводных сетей, в них задачи, связанные с управлением движением данными решаются маршрутизаторами (для проводных сетей) или точками доступа (для управляемых беспроводных сетей [3]).

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

Кроме того, в mesh-сетях появляются дополнительные сложности. Во-первых, сетевая топология может быть непостоянной.

Во-вторых, в mesh-сетях в зависимости от цели маршрутизации может быть ситуация, когда трудно определить маршрут [4] только лишь по топологии сети. Поэтому многие протоколы маршрутизации для mesh-сетей функционируют на так называемом 2.5-уровне модели OSI, то есть применяют топологию сети и МАС-подуровень для выбора маршрута.

Принципиально протоколы маршрутизации можно разбить по двум параметрам:

– Метрика маршрутизации: влияет на то, каким образом проводится оценка производительности и, соответственно, как идет выбор маршрутов;

– Алгоритм маршрутизации: влияет на количество дополнительной нагрузки на каналы связи.

Далее излагается обобщенный алгоритм, позволяющий реализовать процессы передачи сообщений на базе имитационной модели при помощи сформированной и размеченной модели сети [5]. Под событием мы понимаем движение метки от одной позиции к другой [6, 7], другими словами множество типа S = <Р1, Р2, Т, tr, t>, здесь Р1, Р2 – являются соответственно входной и выходной позицией [7, 8]; Т – является переходов; tr – определяет вид трафика; t – описывает момент времени, для которого возникнет событие.

Для описания общего алгоритма имеем:

– Определяется значение размера по временному шагу в модели.

– Определяется число шагов N (рассматривают время моделирования).

Проведение цикла относительно всех источников трафика

Проведение цикла относительно всех потоков

Идет процесс вычисления маршрутов

Конец Цикла

Конец Цикла;

Получается список событий по данному шагу.

~ Если значение шага нулевое, то тогда

Формируется список событий:

Проведение цикла относительно всех источников трафика

Проведение цикла относительно всех потоков

Вычисляется событие S(P1):

Осуществление выбора по следующему переходу и следующей позиции (относительно маршрута), проведение расчета момента t;

Процесс добавления S в список

Конец Цикла;

Конец Цикла;

~ Иначе Если значение списка пустое и значение шага не является нулевым

– проведение перехода на следующий шаг;

~ Иначе

– Цикл относительно событий из списка

Проведение проверки на то, что событие разрешено (соответствующий переход)

Если разрешается событие – процесс выполнения:

Процесс формирования по следующему событию Snext

Осуществление выбора по следующему переходу и следующей позиции (относительно маршрута), проведение расчета момента Snext.

Процесс добавления Snext, в список Конец Если Конец Цикла;

~ Конец Если;

– Конец Цикла относительно i.

Структура работы программы выглядит следующим образом (рисунок).

Программным образом модель была реализована с использованием языка Java и характеризуется следующими особенностями:

1. для каждого компонента модели идет формирование отдельного приложения, оно характеризуется своим IP-адресом и портом, что дает возможности для подбора и связывания компонентов в зависимости от того, какие конкретные условия;

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

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

kaz1.tiff

Структура программы

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

1. пакет, который поступает на вход, будет попадать в очередь Q1;

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

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

4. когда была проведена обработка заголовка пакета и проведен выбор исходящих направлений, то пакет направляется в очередь ожидания к выходному канал Q2.

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

В качестве исходных данных, чтобы их применять в созданной имитационной модели можно считать такие характеристики в сетях, связанных с передачей данных:

1. Сетевые:

– число узлов;

– связи, которые существуют среди узлов, они задаются на основе матрицы инцендентности.

2. Узловые:

– число и вид каналов связи;

– значение объема буферной памяти;

– число и характеристики производительности обрабатывающих устройств;

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

3. Канальные:

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

– значение стоимости доставки пакетов по каналам связи.

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

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

– значение интервала времени рассылки пакетов;

– значение интервала времени жизни пакетов.