СПОСОБ МАРШРУТИЗАЦИИ ДЛЯ БЕСПРОВОДНЫХ МОБИЛЬНЫХ СЕТЕЙ ПЕРЕДАЧИ ВИДЕО, ГОЛОСА И ДАННЫХ Российский патент 2011 года по МПК H04L12/56 

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

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

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

Наиболее близким к предлагаемому изобретению является способ, в котором используется принцип адресации на основе географического положения, то есть каждое маршрутизирующее устройство должно знать свое местоположение в существующей сети [3], что является существенным недостатком данного способа маршрутизации. Для определения местоположения используется система глобального позиционирования (GPS) либо система позиционирования глобальной системы мобильной связи, либо любой другой способ позиционирования. Данное решение приводит к тому, что на каждом маршрутизирующем устройстве должно дополнительно находится устройство, обеспечивающее определение местоположения, что неизбежно приведет к тому, что вырастет энергопотребление, геометрические размеры, потребуется более производительный процессор и память. Кроме того, при передвижении маршрутизирующего узла в пространстве его адрес должен меняться в соответствии с его расположением, что приведет к обновлению маршрутов и в крайнем случае выходу сети из строя. Также минусом данного способа является большое значение точности определения местоположения устройства в пространстве, что на данном уровне технологий может существенно усложнить адресацию близко стоящих устройств и тем самым нарушить действие способа маршрутизации.

Цель изобретения: повышение вероятности успешной маршрутизации в беспроводных одноранговых сетях.

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

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

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

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

- Уникальный идентификатор соединения (ID);

- Метрика маршрута прямого - данная метрика нужна вызываемому узлу для выбора маршрута;

- Метрика обратного маршрута - данная метрика нужна промежуточным узлам для принятия решения о ретрансляции пакета;

- Время жизни пакета (TTL);

- Номер пакета - нужен для определения дублированных пакетов и определения обратных пакетов от вызываемого к вызывающему.

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

Для расчета метрики прямого маршрута используются композиции из следующих параметров:

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

С - пропускная способность маршрута, рассчитанная как отношение числа количество узлов, умноженное на 10⁸, к сумме всех значений пропускной способности на каждом соединении.

N - количество узлов в маршруте, помноженное на 10.

Р - средний заряд батареи всех узлов, взятый в процентах и инвертированный в соответствии со схемой: 0 - полный заряд, 100 - полностью разряженная батарея.

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

F - частота использования узла, помноженная на 100.

Н - количество скачков в маршруте, помноженное на 10.

PS - мощность сигнала на каждом из соединений в мВт.

D - направление движения узла в градусах относительно прямой, соединяющей два передающих узла.

Pos - коэффициент функциональных возможностей устройства, где 0 - полный функционал, 4 - устройство только для передачи.

Таким образом, формула расчета метрики прямого маршрута следующая:

Metrika=Z+C+N+P+G+F+H+PS+D+Pos.

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

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

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

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

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

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

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

Поле «время жизни пакета» (TTL) - необходимо для отбрасывания «заблудившихся» пакетов, выбирается в зависимости от количества узлов в сети, которое определяется по вероятностному распределению.

Поле уникального идентификатора соединения (ID) позволяет избавляться от дубликатов пакетов.

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

Пример осуществления способа маршрутизации. Существует беспроводная распределенная одноранговая сеть, показанная на фиг.1. Допустим, узел 1 начинает сеанс связи с узлом 7. Узел 1 передает пакет, содержащий первую порцию полезных данных во всех направлениях, всем узлам, находящимся в зоне его радиовидимости. Данный пакет получают узлы 11, 8, 2 и ретранслируют его дальше, записывая в буфер ID пакета, что позволяет при следующей ретрансляции его отбросить. Таким образом, по цепочке, пакет достигает узла 7 (фиг.2).

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

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

ИСТОЧНИКИ ИНФОРМАЦИИ

1. №2292123 (2007.01.20) Устройство и способ обнаружения маршрута во временно создаваемой сети подвижной связи.

2. №2331159 (2008.08.10) Способ маршрутизации сообщений от узла источника к узлу назначения в динамической сети.

3. №2281617 (2006.08.10) Адресация и маршрутизация в беспроводных ячеистых сетях.

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

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