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

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

Реферат

Изобретение относится к области связи и может быть использовано при построении беспроводной самоорганизующейся одноранговой мобильной сети (mobile ad hoc network - MANET) для передачи данных в виде цифровой информации.

Известен способ маршрутизации (https://datatracker.ietf.org/doc/rfc3561/), основанный на установлении маршрута от отправителя до адресата по требованию.

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

Наиболее близким к предлагаемому изобретению является способ маршрутизации (http://datatracker.ietf.org/doc/rfc3626/), выбранный нами за прототип. Способ основан на принципе проактивной маршрутизации, в котором каждый узел сети (далее - узел) заранее собирает информацию о топологии сети и определяет оптимальные маршруты до всех достижимых узлов. Для реализации данного принципа использован протокол маршрутизации OLSR, в котором каждый узел периодически рассылает информацию о связях между узлами, а также обновляет записи таблицы маршрутизации, при помощи имеющейся на текущий момент информации о связях между узлами.

Недостатком данного способа является длительный поиск оптимального маршрута из-за возможности его применения только по одноуровневым каналам связи. Кроме того, пакеты имеют формат, не зависящий от особенностей оборудования сети.

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

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

Изобретение поясняется рисунком, где представлена схема сети для реализации заявленного способа.

Сеть для передачи информации состоит из трех узлов 1 сети и нового узла 2 другой сети. Узлы сети 1 и 2 имеют пространственное разделение двухуровневых каналов по четырем секторам, которые организованы на базе отдельных комплектов коммуникационного оборудования. Между узлами 1 сети информация по низкоскоростным каналам 3 передается служебными пакетами первого типа, а между узлами 1 сети и новым узлом 2 другой сети - по низкоскоростным каналам 3, служебными пакетами второго типа.

Способ осуществляется следующим образом.

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

Информация передается в составе служебных пакетов протокола маршрутизации:

- служебные пакеты первого типа «Обновления связей узла»;

- служебные пакеты второго типа «Таблица связей».

Служебные пакеты первого типа имеют формат, предписывающий наличие следующих полей:

- тип пакета (Type = 1);

- флаг ретрансляции пакета (Relay);

- владелец связей (Originator);

- количество связей (Total);

- версия (Version);

- время жизни связи (TTL);

- список описателей связей (LinkInfo).

Количество элементов в списке описателей связей соответствует количеству связей, заданному в поле Total.

Элемент списка описателей связей содержит следующие поля:

- идентификатор соседнего узла (Neighbor);

- первую метрику низкоскоростного канала (MetricSlow);

- вторую метрику высокоскоростного канала (MetricFast).

Служебные пакеты второго типа имеют формат, предписывающий наличие следующих полей:

- тип пакета (Type = 2);

- список кортежей (Tuples).

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

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

- владелец связей (Originator);

- количество связей (Total);

- версия (Version);

- время жизни связи (TTL);

- список описателей связей (LinkInfo).

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

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

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

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

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

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

Служебные пакеты второго типа не ретранслируются.

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

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

При формировании каждой из метрик учитывается:

- загруженность узла;

- качество связи;

- направление и скорость движения узла.

Способ может применяться как при одно-, так и при многопутевой маршрутизации.

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