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

Область техники, к которой относится изобретение

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

Предшествующий уровень техники

Беспроводные сети стали все более важными и популярными, так как мобильность поддерживается вместе со многими сложными приложениями, предлагаемыми фиксированными проводными сетями. Беспроводные сети включают в себя традиционные сотовые сети с базовыми радиостанциями, соединенными с инфраструктурой радиосети. Мобильный терминал взаимодействует с одной или более базовыми станциями в пределах их зоны радиопокрытия, и когда мобильный терминал выходит за пределы зоны радиопокрытия, может быть выполнена процедура эстафетной передачи обслуживания, чтобы поддерживать непрерывную связь. Другим типом беспроводной сети является ячеистая сеть. Ячеистая сеть обрабатывает соединения по принципу “многие со многими” и может динамически оптимизировать эти соединения.

Беспроводные ячеистые сети обычно известны как беспроводные одноранговые сети с произвольной структурой (сети ad hoc), которые обычно состоят из мобильных работающих от аккумуляторной батареи вычислительных устройств, которые осуществляют связь через беспроводную среду. Такая сеть не основывается на фиксированных маршрутизаторах, и все узлы могут перемещаться и могут динамически соединяться произвольным образом. Каждый узел действует как маршрутизатор, который обнаруживает и поддерживает маршруты к другим узлам в сети ad hoc. Маршрут - это путь, используемый для доставки одного или более пакетов между узлом-источником и узлом-адресатом. Маршрут может содержать один или более “транзитных сегментов”. Транзитный сегмент соответствует прямой передаче из одного узла в другой узел без каких-либо находящихся между ними узлов. Примеры беспроводных технологий с функциональными возможностями ad hoc включают в себя беспроводные локальные сети (WLAN) IEEE 802.11 и персональные сети (PAN) Bluetooth.

В беспроводных ячеистых сетях обычно используются два типа протоколов маршрутизации: протоколы маршрутизации на основе таблиц и протоколы маршрутизации, инициируемые источником по требованию. Протоколы маршрутизации на основе таблиц пытаются поддерживать единообразную свежую информацию маршрутизации из каждого узла в каждый другой узел в сети посредством периодических обновлений из всех других узлов в сети, независимо от того факта, что сеть может быть неактивна в плане трафика данных. Для подхода по требованию запрос маршрутов в узел-адресат посылается, только если узел источника имеет пакеты данных, подлежащие посылке в этот узел-адресат. Примерные протоколы маршрутизации ad hoc на основе таблиц включают в себя протокол маршрутизации на основе первоочередного открытия кратчайших маршрутов (OSPF), протокол дистанционно-векторной маршрутизации с упорядочением с помощью узла-адресата, протокол маршрутизации с кластерной шлюзовой коммутацией и протокол беспроводной маршрутизации. Примеры маршрутизации, инициируемой источником по требованию, включают в себя дистанционно-векторную маршрутизацию ad hoc по требованию или динамическую маршрутизацию источника, маршрутизацию с временной упорядоченностью, маршрутизацию на основе ассоциативности и маршрутизацию с использованием стабильности сигнала.

В маршрутизации на основе первоочередного открытия кратчайших маршрутов (OSPF) каждый беспроводной узел поддерживает идентичную базу данных, описывающую топологию сети. На основе этой базы данных вычисляют таблицу маршрутизации с помощью построения дерева кратчайшего маршрута. Кратчайшим маршрутом является маршрут с наименьшей интегральной “стоимостью”. Для линии радиосвязи или транзитного сегмента “стоимость” может быть измерена как обратная величина ожидаемой скорости передачи данных через этот транзитный сегмент радиосвязи. В результате низким скоростям передачи данных соответствует высокая стоимость, так как они дают в результате более длительные времена для передачи пакетов. OSPF первоначально была разработана для фиксированных сетей, но протокол беспроводной маршрутизации (WRP) и динамическая маршрутизация источника (DSR) являются подобными в их подходе выбора маршрута для беспроводных сетей.

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

Большинство беспроводных сетей ad hoc и, в частности сети, которые используют IEEE 801.11, совместно используют радиочастоту во времени, и одна и та же частота используется как для передачи, так и для приема. Чтобы координировать использование среды с совместно используемой частотой, используется некоторый тип протокола. Например, коллективный доступ с контролем несущей и предотвращением конфликтов (CSMA/CA) требует, что узел, желающий передать пакет, должен “слушать”, чтобы удостовериться в том, что никакой другой узел не передает. Если канал свободен в течение определенного периода времени, узел может непосредственно передавать пакет, в противном случае узел устанавливает таймер обратного отсчета. Когда время таймера истекает, узел передает. Функция оценки чистоты канала (ССА) может быть использована, чтобы определять, доступна ли общая частота. Функция ССА обычно включает в себя как опознавание несущей, так и обнаружение энергии. Если одно или другое инициируется, общая частота считается занятой. Опознавание несущей инициируется, когда приемник может обнаружить переданный сигнал другого узла. Механизм обнаружения энергии инициируется, когда полная принятая энергия (независимо от источника) находится выше порога.

Авторы установили, что имеются несколько факторов, которые должны быть приняты во внимание, чтобы получить схему маршрутизации с использованием оптимальной энергии. Во-первых, важно уменьшить число узлов, воздерживающихся от передачи через общую частоту из-за указания занятости, например указания занятости оценки чистоты канала (ССА). Во-вторых, также важно уменьшить длительность времени, в течение которого каждый узел должен ожидать, перед тем как он сможет передавать через общий канал. Несмотря на то, что выбор маршрута кратчайшей длины как маршрута с наименьшей задержкой времени может улучшить сбережение ресурса аккумуляторной батареи, он может не оптимизировать пропускную способность сети. Беспроводные сети являются ограниченными помехами. Мощность передачи в большинстве сценариев не равна помехам, обусловленным конкретной передачей с конкретной мощностью. В действительности на узлы могут воздействовать помехи, основанные на передаче, даже если они не находятся в пределах зоны радиопокрытия/дальности связи передающего узла, т.е. узлы все же находятся в пределах расстояния помех.

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

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

Авторы дополнительно установили, что простая оценка энергии, которая использовалась бы конкретным узлом для передачи пакета по одному транзитному сегменту, где энергия определяется в понятиях мощности и времени, не принимает во внимание реальности типичных сетей ad hoc. Реальные беспроводные сети должны иметь дело с препятствиями (здания, стены, природные объекты, погода и т.д.), которые вызывают потери при распространении. Таким образом, энергия передачи не является адекватным измерением обусловленных помех.

Сущность изобретения

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

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

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

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

Перечень фигур чертежей

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

Фиг.1 - схема сети, иллюстрирующая пример ячеистой сети;

фиг.2 - схема, которая иллюстрирует концепцию области помех;

фиг.3 - блок-схема последовательности этапов, иллюстрирующая процедуры в соответствии с одним примерным вариантом осуществления;

фиг.4 - блок-схема последовательности этапов, иллюстрирующая процедуры в соответствии с другим примерным вариантом осуществления;

фиг.5 - функциональная блок-схема примерного беспроводного узла; и

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

Подробное описание предпочтительных вариантов осуществления

В следующем описании с целью объяснения, а не ограничения, приведены специфичные детали, такие как конкретные компоненты, электронные схемы, методики, протоколы, стандарты и т.д., для того чтобы обеспечить понимание описанной технологии. Например, одним преимущественным вариантом применения является применение к беспроводным локальным сетям, которые придерживаются стандарта IEEE 802.11. Но другие стандарты и другие типы сетей также являются применимыми, например персональные сети Bluetooth. Кроме того, специалисту в данной области техники будет понятно, что могут быть реализованы на практике другие варианты осуществления помимо этих специфических деталей. В других случаях подробные описания широко известных способов, устройств, методик и т.д. опущены, чтобы не затенять описание ненужными деталями. Отдельные функциональные блоки изображены на фигурах. Специалисты в данной области техники поймут, что функции этих блоков могут быть реализованы с использованием отдельных схем аппаратного обеспечения, с использованием программ программного обеспечения и данных в сочетании с соответствующим образом запрограммированным микропроцессором или универсальным компьютером, с использованием специализированных интегральных схем (ASIC) и/или с использованием одного или более цифровых процессоров сигналов (DSP).

Фиг.1 изображает беспроводную ячеистую сеть 10, которая включает в себя один или более фиксированных беспроводных узлов 12 базовых станций, соединенных с одной или более другими сетями 14, а также множество подвижных беспроводных узлов 14. Подвижные узлы 14 взаимодействуют с базовыми станциями 12 и друг с другом (либо через базовую станцию, либо непосредственно) через беспроводной интерфейс. Каждый транзитный сегмент между смежными узлами представлен с использованием пунктирных линий. Примером неограничивающего протокола для беспроводной связи является IEEE 802.11b, который в настоящее время является наиболее широко используемым стандартом связи беспроводной локальной сети (WAN). Каждый узел 14 осуществляет связь с узлами, которые находятся в пределах области радиопокрытия, с использованием одного и того же радиочастотного канала (каналов) для передачи и приема. Как описано в предшествующем уровне техники, могут быть использованы различные протоколы для того, чтобы исключать и разрешать конфликты, когда пакеты передаются через общую среду передачи, например ССА и т.д. Так как среда радиосвязи является ограниченным ресурсом, является критичным, чтобы она использовалась эффективно, таким образом, чтобы оптимально использовалась пропускная способность сети. Также важно, чтобы беспроводные узлы 14, которые в типичном случае работают от аккумуляторных батарей, сохраняли энергию аккумуляторной батареи.

Эти и другие задачи могут быть решены посредством выбора оптимального маршрута для передачи пакета из узла-источника в узел-адресат через беспроводную ячеистую сеть. Фиг.1 иллюстрирует два примерных маршрута из узла-источника А в узел-адресат G. Первый возможный маршрут следует по узлам А, С, Е и G. Второй возможный маршрут следует по узлам А, В, D, F и G. Конечно, имеются много других возможных маршрутов, которые могли бы быть использованы для доставки пакета из узла А в узел G.

Выгодно основывать выбор маршрута через беспроводную ячеистую сеть так, чтобы минимизировать воздействие сгенерированных или обусловленных помех, ассоциированных с этим маршрутом, на другие узлы в сети. Таким образом, полная пропускная способность в сети может быть увеличена, а также мощность батареи может быть сохранена в беспроводных узлах 14. Энергию помех используют в качестве меры для определения того, какие транзитные сегменты и какой маршрут (каждый маршрут включает в себя один или более транзитных сегментов через узлы для передачи пакета из узла-источника в узел-адресат) является более или менее желательным в плане воздействия помех, оказываемого им на другие узлы в сети, т.е. “обусловленные помехи”. Фиг.2 помогает проиллюстрировать этот момент. Изображены три узла А, В и С, причем узел А передает на четырех разных уровнях Р1, Р2, Р3 и Р4 мощности. Каждый уровень мощности имеет соответствующую область помех (IA). С увеличением мощности передачи воздействие области помех увеличивается по размеру, т.е. обусловленные помехи больше.

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

Область помех является областью, в которой результирующий уровень помех выше предварительно определенного порога помех. Ее площадь может быть оценена как квадрат расстояния ri помех (возможно, умноженного на геометрическую константу, такую как π), где ri - наибольшее расстояние, на котором уровень помех выше заданного порога Ithresh. Для IEEE 802.11 порог помех может быть выбран как уровень обнаружения ССА, который является меньшим из порога обнаружения энергии и уровня опознавания несущей, при котором запрещена передача. На основании переданной мощности Р, измеренной в линейных единицах (ваттах), и обычно используемой экспоненциальной функции распространения радиосигналов:

G(r) = g₁·r^-α (линейные единицы),

где g₁ и α - параметры, которые зависят от среды и которые описывают усиление на пути распространения как функцию расстояния, расстояние ri помех может быть вычислено как:

,

где G^-1 - обратная величина функции распространения.

Теперь делается ссылка на блок-схему последовательности этапов на фиг.3, которая изображает примерные процедуры в соответствии с одним неограничивающим вариантом осуществления. Определяют энергию помех, ассоциированную с передачей пакета через каждый транзитный межузловой сегмент узла в каждом из множества маршрутов из узла-источника в узел-адресат (этап S2). Объединяют энергии помех всех транзитных сегментов в маршруте для получения объединенной энергии помех для этого маршрута (этап S4). Выбирают маршрут, через который затем посылают пакет, на основании объединенной энергии помех для каждого маршрута (этап S6). Например, может быть выбран маршрут, который имеет наименьшую объединенную энергию помех.

Следующее является примером неограничивающего варианта осуществления, описанного совместно с блок-схемой последовательности этапов на фиг.4. Каждый узел определяет время передачи, ассоциированное с передачей пакета через каждый транзитный сегмент в множестве маршрутов из узла-источника в узел-адресат (этап S10). Для каждого из транзитных сегментов определяют количество узлов, на которые воздействовали бы помехи, ассоциированные с передачей пакета через этот транзитный сегмент (этап S12). Объединяют время передачи и количество попавших под воздействие узлов для каждого транзитного сегмента с целью получения результирующего показателя соответствующего транзитного сегмента (этап S14). Объединяют результирующие показатели сегментов для каждого маршрута (этап S16). Затем выбирают один из маршрутов на основании объединенных результирующих показателей (этап S18).

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

OH_L1 - объем случайной информации, связанный с посылкой пакета, включающий в себя, например, заголовок пакета и тому подобное. N_CH - количество частотных каналов, используемых для передачи. В соответствии со стандартом IEEE 802.11 имеется только один такой используемый частотный канал, но имеются решения, в которых передачу выполняют по нескольким каналам, например, две несущие 20 МГц. Также может быть использовано переменное число поднесущих OFDM, (мультиплексирования с ортогональным частотным разделением сигналов). R_L1 соответствует назначенной скорости передачи в битах для передачи из узла на основании схемы модуляции линии радиосвязи и кодирования, выбранной узлом, что, в свою очередь, основывается на текущих условиях радиосвязи через конкретный транзитный сегмент. Частота ошибочных блоков (BLER) определяется узлом на основании количества положительных квитанций и/или отрицательных квитанций в отношении приема пакета, принятых для предыдущих передач пакета. Время U передачи измеряется в секундах.

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

G(r) = g₁·r^-α (линейные единицы),

где g₁ и α - параметры, которые зависят от среды. Получающаяся в результате площадь области помех пропорциональна Р²/α, где Р - уровень мощности, измеренный в ваттах, при котором пакет был бы передан через транзитный сегмент. Мощность Р передачи из узла IEEE 802.11 обычно является фиксированной, например 100 мВт, и, следовательно, известна узлу. Также в случае управляемой по мощности передачи с переменной мощностью мощность известна передающему узлу. Коэффициент распространения устанавливают в соответствии со средой распространения радиосигнала транзитного сегмента, и он может быть установлен либо с пользователем вручную, либо управляющим узлом, который сообщает значение α различным узлам, либо узлом, выполняющим различные измерения среды для оценки α. Также могут быть использованы другие методики.

В некоторых случаях, таких как управляемая по мощности передача, более удобно выражать мощность Р передачи в логарифмических единицах, таких dBW (децибелы на ватт, дБВт). Тогда выражение выше для количества воздействованных узлов будет:

При оценке площади области помех мощность Р передачи может быть измерена в децибелах (дБ) выше желаемого порога помех, например уровня обнаружения ССА IEEE 802.11. В одном примере α может быть определен с использованием постоянной В распространения, описанной в модели Окумура-Хата (Okumura-Hata), которая описывает эмпирическую формулу для потерь при распространении в наземной мобильной радиослужбе. Вышеописанные уравнения основаны на обычно используемой экспоненциальной модели распространения радиосигналов. Но может быть использована любая другая модель распространения, такая как линейная модель распространения и модель с точками излома (например, Кенана-Мотли) (Keenan-Motley).

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

Тогда энергия W помех определяется в соответствии со следующим:

W = U·P^2/α,

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

W = U·P^2/α · P_jam,

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

Энергия W помех используется как приходящаяся на транзитный сегмент стоимость для выбора маршрута. Для каждого возможного маршрута из узла-источника в узел-адресат определяют стоимость маршрута, выражаемую энергией помех, с помощью суммирования (или другого типа подходящего объединения) стоимости, приходящейся на транзитный сегмент, для каждого транзитного сегмента в этом маршруте. Выбирают маршрут с наименьшей стоимостью, выражаемой энергией помех. Так как стоимость, выражаемая энергией помех, является мерой площади области помех в единицу времени, такой выбор будет минимизировать обусловленные помехи, ассоциированные с передачей пакета через этот маршрут, и, таким образом, увеличивать пропускную способность беспроводной ячеистой сети. В случае, описанном выше с IEEE 802.11, при пороге помех, равном уровню, на котором инициируется ССА, энергия помех является относительной мерой количества узлов в секунду (произведение площади помех на количество узлов, деленное на m²), которые вынуждены ждать желаемую передачу. С помощью минимизации этих “секунд ожидающего узла” максимизируется количество узлов, которые могут одновременно передавать на совместно используемой частоте в ячеистой сети, и тогда также максимизируется полная пропускная способность ячеистой сети.

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

Информация о стоимости на каждый транзитный сегмент может поддерживаться и распространяться с использованием различных типов протоколов маршрутизации, например протокола первоочередного открытия кратчайших маршрутов” (OSPF) и протокола беспроводной маршрутизации (WRP), где стоимость на каждый транзитный сегмент назначается с использованием энергии W обусловленных помех. В ситуациях, в которых стоимость существенно изменяется в зависимости от размера пакета, может быть определена стоимость на каждый транзитный сегмент для каждого размера пакета. В этой ситуации могут быть подходящими протоколы маршрутизации, инициируемой источником по требованию, подобные алгоритму маршрутизации с временной упорядоченностью (TORA).

Теперь делается ссылка на фиг. 5, которая изображает пример неограничивающего узла 14 беспроводной ячеистой сети в формате функционального блока. Узел 14 беспроводной ячеистой сети может быть стационарным узлом или подвижным узлом. Примерным подвижным узлом могло бы быть портативное телекоммуникационное устройство, такое как сотовый телефон, портативный переносной персональный компьютер с беспроводной картой WLAN и т.д. Узел 14 включает в себя обрабатывающие схемы 20, соединенные с радиоприемопередающими схемами 22, которые соединены с антенной 24, такой как ненаправленная антенна или направленная антенна. Обрабатывающие схемы 20 также соединены с одним или более детекторов 36 для измерения одного или более различных параметров качества линии радиосвязи, используемых для определения мощности передачи, частоты ошибочных блоков, скорости передачи в битах, интенсивности сигнала и т.д. Обрабатывающие схемы 20 также соединены с памятью 26, которая включает в себя программу 28 энергии помех, исполняемую обрабатывающими схемами для определения времени передачи и количества попавших под воздействие пользователей в соответствии с одним из приведенных выше уравнений. Память 26 также включает в себя программу 30 выбора маршрута, которая выбирает наилучший маршрут на основании объединения энергий помех транзитного сегмента в каждом возможном маршруте. Память 26 хранит коммуникационные программы и протоколы 32 ячеистой сети, например WLAN IEEE 802.11. Один или более буферов 34 используются для сохранения пакетов, подлежащих передаче и приему через ячеистую сеть.

Рассмотрим пример выбора маршрута, изображенный на фиг.6. Допустим, что беспроводная ячеистая сеть является ячеистой сетью IEEE 802.11b, используемой в области открытого офиса, конференц-зале или выставочном зале с большим количеством узлов. В такой ситуации пропускной способностью совместно используемых радиоресурсов необходимо тщательно управлять и, желательно, максимизировать. На фиг.6 изображена только часть этой полной ячеистой сети с четырьмя узлами, включая одну точку 12 доступа и три портативных узла 14. Допустим, что пакет должен быть послан из узла А в узел В. Имеются три возможных маршрута, причем каждый имеет два транзитных сегмента или меньше. Односегментный маршрут из узла А непосредственно в узел В имеет самую низкую скорость передачи в битах, равную 2 Мбит/с, так как узлы А и В разделены самым большим расстоянием среди этих четырех узлов. Транзитный сегмент радиосвязи из точки С доступа в узел В имеет наивысшую скорость передачи данных, равную 11 Мбит/с, так как точка С доступа передает с более высокой мощностью, чем подвижные узлы - один ватт (Вт) по сравнению с 100 милливаттами (мВт), с которой передают узлы А и D. Каждый из остальных транзитных сегментов имеет скорость передачи данных, равную 5,5 Мбит/с.

Для области пространства открытого офиса можно ожидать, что постоянная α распространения приблизительно равна 2,2. В таблице 1 ниже вычислена энергия W помех для всех транзитных сегментов в соответствии с приведенными выше уравнениями для двух примерных размеров пакета. Время U передачи вычислено при допущении служебной информации физического условия IEEE 802.11, принимая во внимание положительное/отрицательное квитирование приема согласно управлению доступом к среде (МАС) для предыдущих передач через каждый транзитный сегмент.

Таблица 1 Транзитный сегмент Р
(дБВт)
Вт 1500-байтовый пакет 50-байтовый пакет U
(мс) W
(мВт) ΣW
(мВт) U
(мс) W
(мВт) ΣW
(мВт) А→В -10 0,12 6,8 0,82 0,82 1,0 0,12 0,12 А→С -10 0,12 2,8 0,34 2,04 0,7 0,09 0,79 С→В 0 1 1,7 1,7 0,7 0,7 А→D -10 0,12 2,8 0,34 0,68 0,7 0,09 0,18 D→B -10 0,12 2,8 0,34 0,7 0,09

Для 1500-байтового пакета маршрут из А в D в В генерирует как меньшую энергию помех, соответствующую 0,68 мВт. Но для 50- байтового пакета прямой маршрут из узла А в узел В приводит в результате к меньшей энергии помех 0,12 мВт. Если бы для выбора маршрута была использована метрика наименьшей задержки, в результате этого был бы выбран маршрут через узел С точки доступа (АСВ). Но при допущении, что имеются окружающие узлы, совместно использующие радио спектр, передача с высокой мощностью из узла С заняла бы общие частотные ресурсы в значительно большей области, так как уровень помех в этой большей области был бы выше порога шума, например опознавание несущей было бы инициировано в окружающих узлах. Действительно, по сравнению с энергией помех, равной 0,12, через самый длинный маршрут из А в В маршрут АСВ генерирует в восемь раз большую (т.е. 1/0,12=8,33) величину помех.

В другом сравнении, если была бы использована простая стоимость, выражаемая полосой пропускания для выбора маршрута, тогда был бы выбран маршрут АСВ, так как он имеет наименьшую стоимость, выражаемую полосой пропускания, 1/11+1/5,5. Вторым выбором был бы маршрут ADB. Но такой подход к выбору маршрута не принимает во внимание объем служебной информации для пакета, который, в частности, может быть существенен для меньших пакетов, подобных пакету размером 50 байт.

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

Несмотря на то, что различные варианты осуществления изображены и описаны подробно, формула изобретения не ограничена никаким конкретным вариантом осуществления. Ничто из приведенного выше описания не должно быть интерпретировано как подразумевающее, что какой-либо конкретный элемент, этап, диапазон или функция является существенным, так, что он должен быть включен в рамки объема формулы изобретения. Рамки объема запатентованной совокупности признаков определены только с помощью формулы изобретения. Правовая охрана формулируется с помощью слов, приведенных в принятой формуле изобретения и ее эквивалентах. Не подразумевается, что какой-либо пункт формулы изобретения подпадает под пункт 6 §112 35 USC, если не использованы слова “средство для”.

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

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

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

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

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

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

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

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

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

9. Способ по п.3, отличающийся тем, что время U передачи определяют в соответствии со следующим:

где D - размер пакета, OH_L1 - объем служебной информации, ассоциированный с передачей пакета, N_CH - количество каналов, используемых для передачи, R_L1 - скорость передачи в битах, ассоциированная с передачей пакета через транзитный сегмент, которая зависит от текущих условий радиосвязи для транзитного сегмента, и BLER - оценка вероятности возникновения ошибочных блоков для передачи пакета.

10. Способ по п.3, отличающийся тем, что количество попавших под воздействие узлов оценивают в соответствии с P^2/α,
где Р - уровень мощности, на котором пакет передавался бы через транзитный сегмент, а α - коэффициент распространения, который корректирует уровень мощности до обусловленных им помех на одном или более окружающих узлах.

11. Способ по п.10, отличающийся тем, что энергию W помех для передачи пакета через один транзитный сегмент определяют в соответствии с
W=U·P^2/б.

12. Способ по п.10, отличающийся тем, что энергию W помех для передачи пакета через один транзитный сегмент определяют в соответствии с
W=U·P^2/б·P_jam,
где P_jam - вероятность того, что узел, на который воздействуют помехи, также имеет данные для передачи в течение времени, когда на этот узел воздействуют помехи.

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

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

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

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

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

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

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

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

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

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

23. Устройство по п.18, в котором время U передачи определяется в соответствии со следующим:

где D - размер пакета, OH_L1 - объем служебной информации, ассоциированный с передачей пакета, N_CH - количество каналов, используемых для передачи, R_L1 - скорость передачи в битах, ассоциированная с передачей пакета через транзитный сегмент, которая зависит от текущих условий радиосвязи для транзитного сегмента, и BLER - оценка вероятности возникновения ошибочных блоков для передачи пакета.

24. Устройство по п.18, в котором количество попавших под воздействие узлов оценивается в соответствии с
P^2/α,
где Р - уровень мощности, на котором пакет передавался бы через транзитный сегмент, а α - коэффициент распространения, который корректирует уровень мощности до обусловленных им помех на один или более окружающих узлах.

25. Устройство по п.24, в котором энергия W помех для передачи пакета через один транзитный сегмент определяется в соответствии с
W=U·P^2/б.

26. Устройство по п.24, в котором энергия W помех для передачи пакета через один транзитный сегмент определяется в соответствии с
W=U·P^2/б·P_jam,
где P_jam - вероятность того, что на один или более узлов, имеющих данные для передачи в течение времени передачи, будет фактически воздействовать передача пакета.

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

28. Устройство по п.16, которое реализовано в каждом из множества узлов.

29. Устройство по п.16, в котором один или более из узлов являются портативным устройством связи.