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

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

Продолжает происходить распространение сетей беспроводной связи. Например, FCC (Федеральная комиссия по связи) предложила предоставить нелицензированным радиопередатчикам возможность работать в пределах широковещательного телевизионного спектра в местах, где один или более из выделенных наземных телевизионных каналов не являются использующимися, при условии, что такие нелицензированные передатчики включают в себя меры безопасности, которые гарантируют отсутствие помех при приеме лицензированных наземных телевизионных сигналов. Различные предприятия разрабатывали технологии сверхширокополосной беспроводной связи (UWB), чтобы воспользоваться разрешенными режимами работы нелицензированных беспроводных устройств в лицензированных полосах частот.

В частности, альянс WIMEDIA® разработал спецификации для беспроводных сетей, основанных на технологии UWB. Например, спецификация MAC WIMEDIA® предусматривает полностью распределенный протокол управления доступом к среде передачи (MAC) для поддержки высокоскоростной передачи с одним переприемом между устройствами, которые расположены поблизости друг от друга, например, в так называемых персональных сетях (PAN). Между тем, в декабре 2005 года, Европейская ассоциация производителей компьютеров (ECMA) опубликовала ECMA-368: «High Rate Ultra Wideband PHY and MAC Standard» («Стандарт высокоскоростного сверхширокополосного PHY и MAC»), задающий сверхширокополосный физический уровень (PHY) и распределенный подуровень MAC для высокоскоростной беспроводной сети ближней связи с распределенным доступом, которая может включать в себя портативные и стационарные устройства.

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

Однако, вследствие регулятивного ограничения на мощность передачи, дальность передачи устройств, использующих текущее MAC WIMEDIA®, ограничена, и уменьшается с любым увеличением физической скорости передачи. Соответственно, вследствие ограничений дальности передачи, в некоторых случаях, одному устройству в беспроводной персональной сети (PAN) невозможно передавать данные на другое устройство в той же сети, если два устройства физически разделены слишком большим расстоянием. В других случаях, где два устройства могут быть ближе друг к другу, передача может быть возможной, но только на пониженных скоростях передачи данных. Однако есть некоторые применения, где могло бы быть крайне желательным для устройств, которые расположены удаленно друг от друга на значительном расстоянии, быть способными отправлять и принимать данные на и от друг друга на более высоких скоростях передачи данных, чем поддерживаемые согласно ограничениям мощности передачи на устройства.

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

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

В еще одном аспекте изобретения, в сети беспроводной связи, содержащей множество устройств, предложен способ нахождения маршрута для передачи данных с устройства источника на устройство пункта назначения посредством ретрансляции с многими переприемами. Способ включает в себя прием на N-м устройстве запроса нахождения маршрута для передачи данных с устройства источника на устройство пункта назначения. Запрос нахождения маршрута включает в себя, по меньшей мере: первое поле, указывающее предел счетчика переприемов, второе поле, указывающее количество временных интервалов X, требуемое для передачи данных, третье поле, указывающее количество переприемов между устройством источника и N-м устройством, четвертое поле, включающее в себя ID запроса, уникально идентифицирующий запрос нахождения маршрута, пятое поле, указывающее ID для устройства источника, и шестое поле, указывающее ID для устройства пункта назначения. Способ дополнительно включает в себя обновление таблицы информации о маршрутах на N-м устройстве, чтобы устанавливать значения счетчика переприемов, для достижения устройства источника с N-го устройства, равным количеству переприемов между устройством источника и N-м устройством, которое принималось в запросе нахождения маршрута, и чтобы устанавливать ID для следующего устройства, для достижения устройства источника из N-го устройства, соответствующим ID для (N-1)-го устройства, с которого N-е устройство принимало запрос нахождения маршрута, и определение, имеет ли N-е устройство в распоряжении, по меньшей мере, 2X доступных временных интервалов. Когда N-е устройство имеет, по меньшей мере, 2X доступных временных интервалов, способ включает в себя приращение количества переприемов в четвертом поле запроса нахождения маршрута на единицу для обновления запроса нахождения маршрута, и широковещательную передачу обновленного запроса нахождения маршрута с N-го устройства. Когда N-е устройство не имеет в распоряжении, по меньшей мере, 2X доступных временных интервалов, тогда запрос нахождения маршрута отвергается.

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

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

Фиг.2a-2d иллюстрируют способ нахождения маршрута в сети беспроводной связи с распределенным доступом, использующий AD-HOC протокол вектора расстояния по требованию.

Фиг.3a-3e иллюстрируют еще один способ нахождения маршрута в сети беспроводной связи с распределенным доступом, использующий эпизодический протокол вектора расстояния по требованию, который ищет маршруты, имеющие, по меньшей мере, минимальный набор доступных ресурсов (например, временных интервалов).

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

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

Более того, в описании, которое последует, упомянуты различные передаваемые данные, в том числе запросы резервирования и ответы резервирования. В вариантах осуществления, описанных ниже, эти запросы и ответы могут быть элементами информации (IE), включенными в кадры (пакеты), передаваемые устройством в пределах временного интервала доступа к среде передачи (MAS). Более того, эти запросы и ответы описаны имеющими различные поля, такие как первое поле, второе поле, третье поле и т. д. В таких описаниях должно быть понятно, что нумерационные ссылки «первое», «второе» и т. п. служат просто в качестве системы условных обозначений для различения и идентификации полей и не указывают ни на какое логическое или хронологическое упорядочение или другую компоновку полей в пределах IE или кадров.

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

Как описано ниже, для того чтобы увеличивать дальность передачи, по-прежнему наряду с сохранением эффективности использования спектра (то есть с использованием более высокой скорости передачи) предусмотрена ячеисто задействованная персональная сеть (PAN) WIMEDIA®. Ячеисто задействованная персональная сеть (PAN) WIMEDIA®, по существу, является распределенной PAN с многими переприемами, с несколькими устройствами, которые ретранслируют/пересылают кадры (пакеты) данных для своих соседей.

Например, фиг.1 графически иллюстрирует сеть 100 беспроводной связи, включающую в себя множество устройств 110. В этом случае устройства 110B и 110C задействования ячеек могут ретранслировать кадр, возникающий из устройства 110A источника на его устройство 110D пункта назначения, которое недостижимо устройством 110A посредством передачи с одним переприемом.

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

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

Фиг.2a-2d иллюстрируют способ нахождения маршрута в сети 200 беспроводной связи с распределенным доступом, использующий AD-HOC протокол вектора расстояния по требованию (AODV). На фиг.2a устройство 110A источника широковещательно передает запрос нахождении маршрута (RREQ), чтобы локализовать маршрут с многими переприемами для достижения устройства 110D пункта назначения. RREQ с устройства 110A источника принимается первым набором из трех промежуточных устройств, включающим в себя промежуточные устройстве 110B, 110G и 110F. На фиг.2b каждое из промежуточных устройств в первой группе, которые принимали исходный RREQ из устройства 110A источника, в свою очередь, повторно широковещательно передают RREQ, таким образом, пересылая RREQ во второй набор из трех дополнительных промежуточных устройств, включающий в себя промежуточные устройства 110E и 110C. В это время, устройство 110A источника и некоторые или все из первого набора промежуточных устройств также принимают повторно широковещательно переданный RREQ от других членов первого набора промежуточных устройств, но они игнорируют (отвергают) повторно широковещательно переданный RREQ, как «повтор». На фиг.2c каждое из промежуточных устройств во второй группе, которые принимали исходный RREQ из первого набора промежуточных устройств в свою очередь повторно широковещательно передают RREQ, таким образом, пересылая RREQ в устройство 110D пункта назначения. В это время, некоторые или все из первого и второго наборов промежуточных устройств также принимают повторно широковещательно переданный RREQ от других членов второго набора промежуточных устройств, но они игнорируют (отвергают) повторно широковещательно переданный RREQ как «повтор». В заключение, на фиг.2d устройство 110D пункта назначения отвечает на RREQ ответом нахождения маршрута (RREP), который передается на промежуточное устройство 110C и пересылается промежуточным устройством 110C через промежуточное устройство 110F обратно в устройство 110A источника. Значит, найденным трактом на фиг.3a-3d является 110A-110F-110E-110D.

Операции протокола маршрутизации AODV по фиг.2a-2d меняются в зависимости от роли, которую исполняет устройство 110. Эти операции, в зависимости от того, является ли устройство 110 (1) устройством 110A источника, которое инициирует нахождение маршрута, (2) промежуточным устройством (например, 110B; 110C), которое пересылает сообщения маршрутизации, или (3) устройством 110D пункта назначения, которое отвечает на запрос нахождения маршрута, соответственно, обобщены ниже.

Каждое устройство 110 в сети 200 поддерживает таблицу информации о маршрутах с самой последней информацией касательно ID других устройств 110 в сети 200 связи, счетчика переприема (количества требуемых переприемов) для достижения или отправки данных в каждое из этих других устройств 110, и «следующего устройства», на которое должны быть отправлены данные, для того чтобы достигать каждого из других устройств 110 в сети 200 связи. Всякий раз, когда маршрут до устройства пункта назначения (например, устройства 110D пункта назначения) не является имеющимся в распоряжении в таблице информации о маршрутах устройства 110A источника, тогда устройство 110A источника широковещательно передает запрос нахождения маршрута (RREQ). RREQ может быть реализован в качестве IE, содержащих множество полей. Полезно, когда RREQ включает в себя, по меньшей мере, первое поле, указывающее предел счетчика переприемов, втрое поле, указывающее количество переприемов между устройством источника и текущим устройством, третье поле, включающее в себя ID запроса, уникально идентифицирующий запрос нахождения маршрута, четвертое поле, указывающее ID для устройства источника, пятое поле, указывающее ID для устройства пункта назначения. Другие поля могут быть включены в состав, и одно или более из этих полей могут быть опущены, если позволяют обстоятельства. RREQ широковещательно передается устройством 110A источника на все из его соседних устройств. Устройство 110A источника устанавливает предел счетчика переприемов в кадре (пакете) RREQ, чтобы определить «область поиска», которая определяет, насколько далеко пересылается RREQ. Устройство 110A источника может повторно отправлять RREQ, если ответ нахождения маршрута (RREP) не принят в пределах определенного периода времени. Оно может поступать так наряду с другими алгоритмами управления, когда контролируется поток обмена, обусловленный передачей RREQ.

Между тем, промежуточные устройства (например, устройства 110C и 110D) принимают сообщения маршрутизации RREQ и RREP. Полезно, что запросы нахождения маршрута, принимаемые и отправляемые на всех устройствах 110 в сети 100, все должны иметь одинаковое количество полей, но разные устройства 110 могут обновлять разные поля в запросе, в зависимости от их конкретной роли в нахождении маршрута. Вообще, может быть M промежуточных устройств на маршруте ретрансляции с многими переприемами между устройством 110A источника и устройством 110D пункта назначения. Поведение промежуточных устройств зависит от того, какие сообщения маршрутизации (то есть RREQ или RREP) принимаются.

Когда промежуточное устройство 110 (например, N-е промежуточное устройство, где 1 ≤ N ≤ M) принимает RREQ от устройства 110A источника или другого промежуточного устройства (например, (N-1)-го промежуточного устройства), если оно уже имеет информацию о маршрутах для устройства 110D пункта назначения, заданную в RREQ, то оно может отвечать RREP, включающим в себя надлежащее значение счетчика переприемов, в интересах устройства 110D пункта назначения. Иначе, промежуточное устройство 110 затем должно широковещательно передавать принятый RREQ с приращенным значением счетчика переприемов. Промежуточное устройство 110 должно повторно широковещательно передавать принятый RREQ, только когда оно принимает RREQ - идентифицированный устройством ID источника и ID запроса - в первый раз. Полезно, что промежуточное устройство 110 также обновляет информацию маршрутизации (обратной линии связи) в своей таблице информации о маршрутах для устройства 110A источника и устройства 110, из которого принимался RREQ.

Между тем, промежуточное устройство 110 (например, N-е промежуточное устройство, где 1 ≤ N ≤ M) также может принимать RREP (например, из (N+1)-ого промежуточного устройства, где 1 ≤ N ≤ M). RREP может быть реализован в качестве IE, содержащих множество полей. Полезно, что RREP включает в себя первое поле, указывающее количество переприемов между устройством пункта назначения и промежуточным устройством, второе поле, включающее в себя ID запроса, уникально идентифицирующий запрос нахождения маршрута, к которому имеет отношение этот ответ нахождения маршрута, третье поле, указывающее ID для устройства источника, и четвертое поле, указывающее ID для устройства пункта назначения. Когда промежуточное устройство 110 принимает RREP с более новой информацией, новый маршрут, указанный большим ID запроса, либо маршрут с меньшим значением счетчика переприемов, тогда промежуточное устройство 110 должно: (1) обновить локальную информацию маршрутизации (то есть обратную линию связи на устройство 110D пункта назначения) в своей таблице информации о маршрутах; и (2) прирастить значение счетчика переприемов в принятом RREP; и (3) переслать его обратно на устройство 110A источника с использованием своей локальной информации маршрутизации, полученной из ранее принятого сообщения RREQ с устройства 110A источника.

К тому же, когда устройство 110D пункта назначения принимает RREQ, оно должно: (1) обновить локальную информацию маршрутизации (то есть обратную линию связи на устройство 110A источника) в своей таблице информации о маршрутах; и (2) ответить RREP посредством одноадресной передачи на устройство, с которого оно принимало RREQ. RREP должен включать в себя инициализированное значение счетчика переприемов (например, установку в ноль или установку и единицу), и приращенный либо неизмененный ID запроса, в зависимости от того, предлагается или нет новый маршрут посредством ответа.

Хотя способ, описанный выше, может давать возможность нахождения маршрута устройством 110A источника в маршруте ретрансляции с многими переприемами с минимальным счетчиком переприемов, он не гарантирует, что выбранный маршрут (или любой другой маршрут) имеет достаточно ресурсов для поддержки требуемой скорости передачи данных или ширины полосы пропускания. То есть способ, описанный выше со ссылкой на фиг.2a-2d, не гарантирует, что есть достаточно доступных (незарезервированных) временных интервалов доступа к среде передачи, имеющихся в распоряжении на каждом устройстве на всем протяжении маршрута ретрансляции с многими переприемами для передачи данных с устройства 110A источника на устройство 110D пункта назначения с требуемой скоростью передачи данных.

Фиг.3a-3e иллюстрируют еще один способ нахождения маршрута в сети 300 беспроводной связи с распределенным доступом, использующий AD-HOC протокол вектора расстояния по требованию. Способ, описанный ниже со ссылкой на фиг.3a-3e, предоставляет возможность «вычищать» маршруты с устройства 110A источника на устройство 110D пункта назначения, которые не способны к поддержке требуемой скорости передачи данных или ширины полосы пропускания. Другими словами, способ, проиллюстрированный на фиг.3a-3e, гарантирует, что каждое устройство 110 на выбранном маршруте ретрансляции с многими переприемами для передачи данных с устройства 110A источника на устройство 110D пункта назначения имеет в распоряжении достаточно доступных временных интервалов доступа к среде передачи (MAS) для пересылки данных передачи с требуемой скоростью передачи данных.

Как в случае варианта осуществления по фиг.2a-2d, операции улучшенного протокола маршрутизации AODV по фиг.3a-3e меняются в зависимости от ролей, которые выполняет устройство 110. Эти операции зависят от того, является ли устройство (1) устройством источника, которое инициирует нахождение маршрута, (2) промежуточным устройством, которое пересылает сообщения маршрутизации, или (3) устройством пункта назначения, которое отвечает на запрос нахождения маршрута. В сети 300 устройства 110 выполняют различные операции, как описанные выше в сети 200 (которые здесь не будут повторяться ради краткости), а также дополнительные операции, описанные ниже.

На фиг.3a устройство 110A источника широковещательно передает запрос нахождения маршрута (RREQ), чтобы локализовать маршрут с многими переприемами для достижения устройства 110D пункта назначения. RREQ с устройства 110A источника принимается первой группой из трех промежуточных устройств, включающей в себя промежуточное устройство 110B. Как будет подробно пояснено ниже, RREQ задает минимальное количество временных интервалов (MAS), которое требуются для передачи данных из устройства 110A источника на устройство 110D пункта назначения. Этап, показанный на фиг.3b, действует таким же образом, как фиг.2b, которая описана выше, за исключением того, что промежуточное устройство 110F не пересылает RREQ, который оно принимало из устройства 110A источника, так как промежуточное устройство 110F не имеет в распоряжении достаточного количества доступных временных интервалов (MAS) для поддержки требуемой передачи данных. Поскольку промежуточный терминал 110F отвергает RREQ, он не пересылается на промежуточный терминал 110C на фиг.3b. Этап, показанный на фиг.3, действует таким же образом, как фиг.2c, которая описана выше, за исключением того, что теперь только один промежуточный терминал (110E) во втором «наборе», и теперь есть третий «набор» промежуточных устройств, который состоит только из промежуточного устройства 110E. На фиг.3d устройство 110D пункта назначения отвечает передачей RREP на промежуточное устройство 110E, наряду с тем, что промежуточное устройство 110C повторно широковещательно передает RREQ, который принимается устройством 110D пункта назначения и промежуточным устройством 110F. Оба, устройство 110D пункта назначения и промежуточное устройство 110F, отвергают RREQ, поскольку они приняли тот же самый запрос раньше. В заключение, на фиг.3e RREP передается с промежуточного терминала 110E через промежуточный терминал 110G и принимается терминалом 110A источника. Таким образом, найденным трактом на фиг.3a-3d является 110A-110G-110E-110D, который является иным, чем найденный маршрут на фиг.2a-2d, но который гарантирован для обладания достаточными ресурсами (временными интервалами), чтобы поддерживать требуемую скорость передачи данных или ширину полосы пропускания. Причина, по которой маршрут является другим, возникает, так как устройство 110F, которое формирует часть маршрута на фиг.2a-2d, не имеет в распоряжении достаточно временных интервалов для поддержки требуемой скорости передачи и, поэтому, оно было обойдено на фиг.3a-3e.

По сравнению с работой сети 200 связи, описанной выше, устройство 110A источника в сети 300 связи включает в, по меньшей мере, одно дополнительное поле в сообщение RREQ, когда оно широковещательно передается. Дополнительное поле идентифицирует количество временных интервалов доступа к среде передачи (MAS) X, которые необходимы для передачи данных при требуемой скорости передачи или ширине полосы пропускания, с устройства 110A источника на устройство 110D пункта назначения. Это поле будет использоваться, как подробно пояснено ниже, чтобы гарантировать, что только такие маршруты, имеющие достаточную ширину полосы пропускания (количество доступных временных интервалов) в каждом устройстве 110 на маршруте, выбираются для передачи данных.

Полезно, что сообщение RREQ устройства 110A источника в сети 300 связи дополнительно включает в себя: (1) второе дополнительное поле, идентифицирующее дополнительный параметр, названный «остаточным временем среды передачи»; и (2) флаг приоритета полосы пропускания (B). Остаточное время среды передачи указывает остаточное количество временных интервалов, доступных в устройстве 110 на текущем маршруте с устройства 110A источника на данное устройство 110, которое имеет в распоряжении наименьшее остаточное количество доступных временных интервалов. То есть это поле идентифицирует остаточное время среды передачи, доступное в «точке сужения» на данном маршруте ретрансляции с многими переприемами из терминала источника на текущее устройство. Как будет подробно пояснено ниже, в то время как сообщение RREQ пересылается с устройства 110 на устройство 110, остаточное время среды передачи обновляется по необходимости. Однако, когда RREQ изначально широковещательно передается устройством 110A источника, время среды передачи инициализируется, чтобы отражать начальное значение времени среды передачи. В одном из вариантов осуществления, время среды передачи может переустанавливаться в бесконечность. В еще одном варианте осуществления, остаточное время среды передачи может устанавливаться в максимальное имеющееся в распоряжении значение с использованием количества битов, выделенных для поля. Более того, флаг B может быть установлен (например, в «1»), чтобы указывать, что маршрут, имеющий большее остаточное время среды передачи, должен быть выбран или предпочтен над маршрутом, имеющим меньшее остаточное время среды передачи, даже если маршрут, имеющий меньшее остаточное время среды передачи, имеет меньшее значение счетчика переприемов. Более того, когда RREQ включает в себя поле, указывающее остаточное время среды передачи, то RREP также должен включать в себя поле, указывающее остаточное время среды передачи, и флаг B.

Между тем, когда промежуточное устройство 110 сети 300 связи принимает RREQ, указывающий, что X MAS (временных интервалов) требуется для передачи данных, то промежуточное устройство 110 пересылает RREQ (посредством широковещательной передачи), только когда промежуточное устройство 110 имеет в распоряжении по меньшей мере 2X MAS (временных интервалов), доступных ему самому. Иначе промежуточное устройство 110 будет молча отвергать принятый RREQ.

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

Более того, когда промежуточное устройство 110 сети 300 связи принимает RREQ, если количество доступных MAS для промежуточного устройства 110, Y, является меньшим, чем остаточное время среды передачи, указанное в принятом RREQ, то промежуточное устройство 110 также копирует значение Y в поле остаточного времени среды передачи RREQ до его пересылки.

Когда устройство 110D пункта назначения сети 300 связи принимает RREQ, имеющий новый ID запроса и указывающий, что X MAS (временных интервалов) требуется для передачи данных, устройство 110D пункта назначения просто отвечает RREP, когда оно имеет в распоряжении, по меньшей мере, X MAS, доступных для приема данных, транслируемых с устройства 110A источника. Иначе, если устройство 110D пункта назначения сети 300 связи не имеет, по меньшей мере, X доступных MAS, то оно отвергает RREQ, не отвечая.

К тому же, когда устройство 110D пункта назначения сети 300 связи принимает RREQ, который включает в себя флаг B и поле, указывающее остаточное время среды передачи, доступное в устройстве 110 на маршруте, который имеет в распоряжении наименьшее остаточное количество доступных временных интервалов, тогда устройство 110D пункта назначения должно действовать, как описано ниже. Когда флаг B установлен, указывая, что приоритет должен задаваться маршрутам, которые имеют в распоряжении большее количество доступных временных интервалов, тогда устройство 110D пункта назначения должно обновлять соответствующую запись маршрута в своей таблице информации о маршрутах, когда RREQ имеет такой же ID запроса, как принятый ранее RREQ, но указывает большее остаточное время среды передачи, чем указывалось в предыдущем RREP.

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

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

Изобретение относится к системам связи. Заявлен способ нахождения маршрута в сети беспроводной связи, содержащей множество устройств (100), для передачи данных с устройства (110А) источника на устройство (110D) пункта назначения посредством ретрансляции с многими переприемами включает в себя широковещательную передачу с устройства (110A) источника запроса нахождения маршрута для передачи данных на устройство (110D) пункта назначения. Технический результат заключается в повышении эффективности нахождения маршрута. Запрос нахождения маршрута включает в себя: первое поле, указывающее предел счетчика переприемов, второе поле, указывающее количество временных интервалов X, требуемых для передачи данных, третье поле, указывающее ID для устройства (110A) источника, и четвертое поле, указывающее ID для устройства (110D) пункта назначения. Устройство (11 OA) источника затем принимает ответ нахождения маршрута, указывающий маршрут от устройства (110А) источника до устройства (110D) пункта назначения. Ответ нахождения маршрута включает в себя первое поле, указывающее количество переприемов между устройством (110А) источника и устройством (110D) пункта назначения. 14 з.п. ф-лы, 10 ил.

1. Способ нахождения маршрута для передачи данных из устройства (110A) источника на устройство (110D) пункта назначения посредством ретрансляции с многими переприемами в сети (300) беспроводной связи, содержащей множество устройств (110), заключающийся в том, что:
широковещательно передают из устройства (110A) источника запрос нахождения маршрута для передачи данных на устройство (110D) пункта назначения, запрос нахождения маршрута включает в себя по меньшей мере: первое поле, указывающее предел счетчика переприемов, второе поле, указывающее количество временных интервалов X, требуемое для передачи данных, третье поле, указывающее ID для устройства (110A) источника, и четвертое поле, указывающее ID для устройства (110D) пункта назначения;
принимают запрос нахождения маршрута на промежуточном устройстве; направляют запрос нахождения маршрута из промежуточного устройства на устройство пункта назначения только, если количество доступных интервалов выше, чем количество интервалов указанных во втором поле; и принимают в устройстве (110А) источника ответ нахождения маршрута, указывающий маршрут от устройства (110А) источника до устройства (110D) пункта назначения, ответ нахождения маршрута включает в себя, по меньшей мере, первое поле, указывающее количество переприемов между устройством (110A) источника и устройством (110D) пункта назначения.

2. Способ по п.1, дополнительно состоящий в том, что: обновляют таблицу информации о маршрутах в устройстве (110A) источника, чтобы устанавливать значение счетчика переприемов, для достижения устройства (110D) пункта назначения, равным количеству переприемов между устройством (110A) источника и устройством (110D) пункта назначения, которое указывалось ответом нахождения маршрута, и чтобы устанавливать ID для следующего устройства (110), для достижения устройства (110D) пункта назначения из устройства (110A) источника, соответствующим ID для устройства (110), из которого устройство (110A) источника принимало ответ нахождения маршрута.

3. Способ по п.2, дополнительно состоящий в том, что принимают на устройстве (110A) источника второй ответ нахождения маршрута, указывающий второй маршрут от устройства (110A) источника до устройства (110D) пункта назначения, второй ответ нахождения маршрута указывает большее остаточное время среды передачи, чем первый ответ нахождения маршрута.

4. Способ по п.3, дополнительно состоящий в том, что: когда флаг приоритета полосы пропускания установлен, указывая, что приоритет должен быть задан маршрутам, которые имеют большее количество доступных временных интервалов, обновляют таблицу информации о маршрутах в устройстве (110А) источника, чтобы устанавливать значение счетчика переприемов, для достижения устройства (110D) пункта назначения, равным количеству переприемов между устройством (110A) источника и устройством (110D) пункта назначения, которое принималось во втором ответе нахождения маршрута, и устанавливают ID для следующего устройства (110), для достижения устройства (110D) пункта назначения, соответствующим ID для устройства (110), из которого устройство (110А) источника принимало второй ответ нахождения маршрута.

5. Способ по п.1, дополнительно заключающийся в том, что: принимают на N-м устройстве (110) запрос нахождения маршрута для передачи данных из устройства (110A) источника на устройство (110D) пункта назначения, запрос нахождения маршрута включает в себя, по меньшей мере: первое поле, указывающее предел счетчика переприемов, второе поле, указывающее количество временных интервалов X, требуемое для передачи данных, третье поле, указывающее количество переприемов между устройством (110A) источника и N-м устройством, четвертое поле, включающее в себя ID запроса, уникально идентифицирующий запрос нахождения маршрута, пятое поле, указывающее ID для устройства (110A) источника, и шестое поле, указывающее ID для устройства (110D) пункта назначения; обновляют таблицу информации о маршрутах в N-м устройстве (110), чтобы устанавливать значение счетчика переприемов, для достижения устройства (110А) источника из N-го устройства (110), равным количеству переприемов между устройством (110А) источника и N-м устройством (110), которое принималось в запросе нахождения маршрута, и чтобы устанавливать ID для следующего устройства (110), для достижения устройства (110А) источника из N-го устройства (110), соответствующим ID для (N-1)-го устройства (110), из которого N-e устройство (110) принимало запрос нахождения маршрута; определяют, имеет ли N-e устройство (110) в распоряжении по меньшей мере 2Х доступных временных интервалов;
когда N-e устройство (110) имеет в распоряжении, по меньшей мере, 2Х доступных временных интервалов,
приращивают количество переприемов в четвертом поле запроса нахождения маршрута на единицу для обновления запроса нахождения маршрута и широковещательно передают обновленный запрос нахождения маршрута из N-го устройства (110); и
когда N-e устройство (110) не имеет в распоряжении, по меньшей мере, 2Х доступных временных интервалов, отвергают запрос нахождения маршрута.

6. Способ по п.5, в котором запрос нахождения маршрута также включает в себя седьмое поле, указывающее остаточное время среды передачи, доступное на устройстве (110) в тракте от устройства (110А) источника до N-го устройства (110), которое имеет в распоряжении наименьшее остаточное количество доступных временных интервалов, и когда N-e устройство (110) имеет в распоряжении, по меньшей мере, 2Х доступных временных интервалов, способ дополнительно заключается в том, что
определяют, является ли количество временных интервалов, доступных на N-м устройстве (110), Y, меньшим, чем остаточное время среды передачи, копируют Y в третье поле запроса нахождения маршрута для обновления остаточного времени среды передачи.

7. Способ по п.6, дополнительно заключающийся в том, что: принимают на N-м устройстве (110) новый ответ нахождения маршрута для передачи данных с устройства (110А) источника на устройство (110D) пункта назначения, новый ответ нахождения маршрута включает в себя, по меньшей мере: первое поле, указывающее количество переприемов между устройством (110D) пункта назначения и N-м устройством (110), второе поле, включающее в себя ID запроса, уникально идентифицирующий запрос нахождения маршрута, к которому имеет отношение новый ответ нахождения маршрута, третье поле, указывающее ID для устройства (110А) источника, и четвертое поле, указывающее ID для устройства (110D) пункта назначения;
когда, по меньшей мере, одно из: (1) ID запроса нового ответа нахождения маршрута является большим, чем ID запроса для принятого ранее ответа нахождения маршрута; и (2) количество переприемов между устройством (110D) пункта назначения и N-м устройством (110), указанное в новом ответе нахождения маршрута, является меньшим, чем значение счетчика переприемов для достижения устройства (110D) пункта назначения, которое хранится в настоящий момент в таблице информации о маршрутах,
обновляют таблицу информации о маршрутах в N-м устройстве (110), чтобы устанавливать значение счетчика переприемов, для достижения устройства (110D) пункта назначения из N-го устройства (110), равным количеству переприемов между N-м устройством (110) и устройством (110D) пункта назначения, которое принималось в новом ответе нахождения маршрута, и чтобы устанавливать ID для следующего устройства (110), для достижения устройства (110D) пункта назначения из N-го устройства (110), соответствующим ID для (N+1)-го устройства (110), из которого N-e устройство (110) принимало новый ответ нахождения маршрута,
приращивают количество переприемов в первом поле ответа нахождения маршрута на единицу для обновления нового запроса нахождения маршрута, и
пересылают обновленный новый ответ нахождения маршрута из N-го устройства (110) на (N-1)-e устройство (110), которое было сохранено ранее в таблице информации о маршрутах для достижения устройства (110А) источника.

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

9. Способ по одному из пп.1 или 7, в котором запрос или ответ нахождения маршрута также включает в себя четвертое поле, указывающее остаточное время среды передачи, доступное в устройстве (110) на маршруте, который имеет наименьшее остаточное количество доступных временных интервалов.

10. Способ по п.9, дополнительно заключающийся в том, что, когда: (1) ID запроса нового ответа нахождения маршрута является таким же, как ID запроса для принятого ранее ответа нахождения маршрута, (2) остаточное время среды передачи нового ответа нахождения маршрута является меньшим, чем остаточное время среды передачи для предыдущего ответа нахождения маршрута, имеющего такой же ID запроса, как новый ответ нахождения маршрута, и (3) флаг приоритета полосы пропускания нового ответа нахождения маршрута установлен, указывая, что приоритет должен быть задан маршрутам, которые имеют в распоряжении большее количество доступных временных интервалов,
обновляют таблицу информации о маршрутах в N-м устройстве (110), чтобы устанавливать значение счетчика переприемов, для достижения устройства (110D) пункта назначения из N-го устройства (110), равным количеству переприемов между N-м устройством (110) и устройством (110D) пункта назначения, которое принималось в новом ответе нахождения маршрута, и чтобы устанавливать ID для следующего устройства (110), для достижения устройства (110D) пункта назначения из N-го устройства (110), соответствующим ID для (N+1)-го устройства (110), из которого N-e устройство (110) принимало новый ответ нахождения маршрута,
приращивают количество переприемов в первом поле запроса нахождения маршрута на единицу для обновления нового запроса нахождения маршрута и пересылают обновленный новый запрос нахождения маршрута из N-го устройства (110) на (N-1)-e устройство (110), которое было сохранено ранее в таблице информации о маршрутах для достижения устройства (110А) источника.

11. Способ по п.5, дополнительно заключающийся в том, что:
принимают в устройстве (110D) пункта назначения на N-м устройстве (110), второй запрос нахождения маршрута для передачи
данных с устройства (110А) источника на устройство (110D) пункта назначения, второй запрос обнаружения маршрута включает в себя пятое поле, включающее в себя ID запроса, уникально идентифицирующий второй запрос нахождения маршрута;
сравнивают ID запроса у второго запроса нахождения маршрута с ID запроса у первого запроса нахождения маршрута, и
когда ID запроса у второго запроса нахождения маршрута соответствует ID запроса у первого запроса нахождения маршрута, отвергают второй запрос нахождения маршрута.

12. Способ по п.1, дополнительно заключающийся в том, что: принимают на устройстве (110D) пункта назначения запрос нахождения маршрута для передачи данных из устройства (110А) источника на устройство (110D) пункта назначения, запрос нахождения маршрута включает в себя, по меньшей мере: первое поле, указывающее предел счетчика переприемов, второе поле, указывающее количество временных интервалов X, требуемых для передачи данных, третье поле, указывающее количество переприемов от устройства (110А) источника до устройства (110D) пункта назначения, четвертое поле, включающее в себя ID запроса, уникально идентифицирующий запрос нахождения маршрута, пятое поле, указывающее устройство (110А) источника, и шестое поле, указывающее устройство (110D) пункта назначения;
обновляют таблицу информации о маршрутах в устройстве (110D) пункта назначения, чтобы устанавливать значение счетчика переприемов, для достижения устройства (110А) источника из устройства (110D) пункта назначения, равным количеству переприемов от устройства (110А) источника до устройства (110D) пункта назначения, которое принималось в запросе нахождения маршрута, и чтобы устанавливать ID для следующего устройства (110), для достижения устройства (110A) источника из устройства (110D) пункта назначения, соответствующим ID для М-го устройства (110), из которого устройство (110D) пункта назначения принимало запрос нахождения маршрута; определяют, имеет ли устройство (110D) пункта назначения в распоряжении, по меньшей мере, X доступных временных интервалов; когда устройство (110D) пункта назначения имеет в распоряжении, по меньшей мере, X доступных временных интервалов,
пересылают ответ нахождения маршрута с устройства (110D) пункта назначения на М-е устройство (110), с которого устройство (110D) пункта назначения принимало запрос нахождения маршрута, ответ нахождения маршрута включает в себя, по меньшей мере: первое поле, включающее в себя ID запроса, уникально идентифицирующий запрос нахождения маршрута, второе поле, указывающее устройство (110А) источника, третье поле, указывающее устройство (110D) пункта назначения, и поле счетчика переприемов, содержащее инициализированный счетчик переприемов; и когда устройство (110D) пункта назначения не имеет в распоряжении, по меньшей мере, X доступных временных интервалов, отвергают запрос нахождения маршрута.

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

14. Способ по п.13, в котором запрос нахождения маршрута также включает в себя седьмое поле, указывающее остаточное время среды передачи, доступное в устройстве (110) на маршруте, который имеет в распоряжении наименьшее остаточное количество доступных временных интервалов, и при этом ответ нахождения маршрута также включает в себя четвертое поле, указывающее остаточное время среды передачи, доступное в устройстве (110) на маршруте, который имеет в распоряжении наименьшее остаточное количество доступных временных интервалов, при этом остаточное время среды передачи ответа нахождения маршрута устанавливается равным остаточному времени среды передачи запроса нахождения маршрута.

15. Способ по п.13, дополнительно состоящий в том, что:
принимают второй запрос нахождения маршрута в устройстве (110D)
пункта назначения;
когда устройство (110D) пункта назначения имеет в распоряжении, по меньшей мере, X доступных временных интервалов,
когда: (1) ID запроса второго запроса нахождения маршрута является таким же, как ID запроса для первого запроса нахождения маршрута, (2) остаточное время среды передачи второго запроса нахождения маршрута является меньшим, чем остаточное время среды передачи для первого запроса нахождения маршрута, и (3) флаг приоритета полосы пропускания второго запроса нахождения маршрута установлен, указывая, что приоритет должен быть задан маршрутам, которые имеют в распоряжении большее количество доступных временных интервалов, обновляют таблицу информации о маршрутах в устройстве (110D) пункта назначения, чтобы устанавливать значение счетчика переприемов, для достижения устройства (110А) источника из устройства (110D) пункта назначения, равным количеству переприемов от устройства (110А) источника до устройства (110D) пункта назначения, которое принималось во втором запросе нахождения маршрута, и чтобы устанавливать ID для следующего устройства (110), для достижения устройства (110А) источника из устройства (110D) пункта назначения, соответствующим ID для P-го устройства (110), из которого устройство (110D) пункта назначения принимало второй запрос нахождения маршрута,
пересылают второй ответ нахождения маршрута с устройства (110D) пункта назначения на P-е устройство (110), с которого устройство (110D) пункта назначения принимало запрос нахождения маршрута, второй ответ нахождения маршрута включает в себя, по меньшей мере: первое поле, указывающее остаточное время среды передачи, доступное в устройстве (110) на маршруте, который имеет в распоряжении наименьшее остаточное количество доступных временных интервалов, второе поле, включающее в себя ID запроса, идентифицирующий запрос нахождения маршрута, третье поле, указывающее устройство (110А) источника, четвертое поле, указывающее устройство (110D) пункта назначения, и поле счетчика переприемов, содержащее инициализированный счетчик переприемов, при этом остаточное время среды передачи второго ответа нахождения маршрута устанавливается равным остаточному времени среды передачи второго запроса нахождения маршрута, и
когда ID запроса второго запроса нахождения маршрута является таким же, как ID запроса для первого запроса нахождения маршрута, и, по меньшей мере, одно из (1) остаточное время среды передачи второго запроса нахождения маршрута является не меньшим, чем остаточное время среды передачи для первого запроса нахождения маршрута, и (2) флаг приоритета полосы пропускания второго запроса нахождения маршрута сброшен, указывая, что приоритет не должен задаваться маршрутам, которые имеют в распоряжении большее количество доступных временных интервалов, отвергают второй запрос нахождения маршрута, и когда устройство (110D) пункта назначения не имеет в распоряжении, по меньшей мере, X доступных временных интервалов, отвергают второй запрос нахождения маршрута.