Область техники, к которой относится изобретение
Настоящее изобретение относится к показателю маршрутизации на основе сведений по радиосвязи и трафику для беспроводных сетей, и в частности, к способу и устройству для выбора маршрута или тракта для прохода данных по беспроводной ячеистой сети, в которой один или более узлов имеют несколько радиостанций, каждая радиостанция работает на одном или более различных каналов, или в которой один или более узлов имеют одну радиостанцию, работающую на одном или более каналов.
Уровень техники
Большинство современных протоколов ячеистой маршрутизации используют минимальное число перескоков в качестве показателя для того, чтобы принимать решения по выбору тракта/маршрута. При использовании в данном документе, "/" означает альтернативные имена для одинаковых или аналогичных компонентов. При этом подходе не рассматривается качество линий радиосвязи, нагрузка по трафику и доступная полоса пропускания линий связи. Маршрут с минимальным числом перескоков выбирается для того, чтобы пересылать данные, которые имеют форму пакетов или кадров. Тем не менее, маршруты с минимальным числом перескоков могут иметь низкую производительность, поскольку маршруты зачастую включают в себя линии радиосвязи между удаленными узлами, и качество линий связи по маршруту может не быть хорошим. Линии радиосвязи с протяженным физическим участком могут быть подвержены потерям, что приводит к определенному числу повторных передач и низкой скорости передачи данных на физическом уровне. Множество систем радиопередачи, например радиостанции по стандарту IEEE 802.11 и IEEE 802.16, адаптируют скорость передачи данных на физическом уровне в зависимости от качества линии связи. Это фактически приводит к низкой пропускной способности и уменьшает эффективность использования сети по сравнению с выбором тракта с большим количеством перескоков, но с лучшим качеством линии связи.
В предшествующем уровне техники показатель, называемый "ожидаемое число передач" (ETX), использовался в качестве показателя маршрутизации. ETX оценивает ожидаемое число передач MAC-уровня, требуемых для того, чтобы успешно доставить пакет через линию беспроводной связи. Маршрут с наименьшей суммой ETX среди всех линий связи в тракте (тракт с наименьшими затратами ETX) выбирается. ETX фиксирует результаты частот потерь пакетов линии связи, но не принимает во внимание различные скорости передачи и доступную полосу пропускания линий связи.
В другой заявленной схеме предшествующего уровня техники показатель, называемый "ожидаемое время передачи" (ETT), предложен для того, чтобы улучшать ETX посредством рассмотрения разности скоростей передачи линий связи. ETT линии связи задается как ожидаемая длительность на MAC-уровне для успешной передачи пакета по линии связи. Затраты маршрута - это сумма ETT всех линий связи по маршруту. ETT принимает во внимание воздействие скоростей передачи по различным линиям связи. Тем не менее, он полностью не фиксирует воздействие нагрузки по трафику и доступной полосы пропускания линии связи, а также помех в сетях вследствие совместно используемой передающей среды. Линия связи под большой нагрузкой может быть выбрана, чтобы быть включенной в маршрут, так что эти линии связи становятся более загруженными, и возникает перегрузка.
В предыдущей родственной заявке описан взвешенный показатель маршрутизации на основе сведений по радиосвязи и нагрузки по трафику (WRALA). Описанный показатель фиксирует воздействие различных аспектов линии беспроводной связи в ячеистых сетях, включая скорость радиопередачи, частоту потерь, нагрузку по трафику и доступную полосу пропускания линии связи, а также помехи вследствие совместно используемой передающей среды в сетях.
Тем не менее, ни один из вышеупомянутых показателей маршрутизации не учитывает воздействия многоканальности с множеством радиостанций на производительность маршрутизации. В ячеистой сети узел/точка сетки может быть оснащена несколькими радиостанциями, и каждая из радиостанций может работать на различном канале/частоте, чтобы увеличивать пропускную способность сети. В отличие от узла с одной радиостанцией, многоканальный узел с множеством радиостанций может принимать пакеты данных на одном канале и одновременно передавать пакеты данных на другом канале. Поэтому предпочтительно выбирать ретрансляционный узел с несколькими радиостанциями, где каждая радиостанция работает на различном канале. Кроме того, даже при одной радиостанции, узел, имеющий радиостанцию, которая может работать на нескольких каналах, может принимать данные на одном канале и затем переключаться на другой канал, чтобы пересылать/ретранслировать/передавать данные.
Будет преимущественным иметь систему для выбора маршрута для прохождения данных по ячеистой сети, которая использует показатель, который основан не только на сведениях по трафику и полосе пропускания, но также фиксирует влияние наличия одного или более узлов, имеющих несколько радиостанций, причем каждая радиостанция работает на различном канале, или если один или более узлов имеет одну радиостанцию, работающую на нескольких каналах.
Сущность изобретения
В многоканальных беспроводных ячеистых сетях с множеством радиостанций, односкачковый или многоскачковый тракт должен выбираться для того, чтобы пересылать данные в форме пакетов или кадров от исходного узла/точки сетки к целевому узлу/точке сетки. Выбор тракта/маршрута основан на показателе. Такой показатель маршрутизации важен для оптимизации структуры механизмов маршрутизации и пересылки в ячеистых сетях. Настоящее изобретение описывает показатель на основе сведений по радиосвязи и полосе пропускания, который фиксирует воздействие элементов с множеством радиостанций и многоканальных элементов на производительность маршрутизации, а также устройство и способ, которые используют показатель для выбора маршрута для прохождения данных по ячеистой сети. Следует отметить, что показатель в настоящем изобретении не ограничен беспроводной ячеистой сетью, хотя беспроводная ячеистая сеть используется в качестве примера для того, чтобы пояснять настоящее изобретение. Настоящее изобретение также может использоваться для других топологий сети, например, древовидного типа многоскачковых беспроводных сетей для выбора маршрута между узлом и корнем дерева.
Значение показателя маршрутизации может часто изменяться вследствие динамики качества линии связи и нагрузки по трафику, что может приводить к нестабильности маршрута. Важно обеспечивать стабильность маршрута с хорошей производительностью маршрутизации даже вопреки быстро изменяющемуся качеству линии связи и колебаниям нагрузки. Поэтому настоящее изобретение также описывает способ для того, чтобы добиваться быстрых откликов на изменения состояния линии связи и топологии сети при сохранении стабильности маршрута посредством квантования показателя маршрутизации.
Описываются способ и система для установления сквозного маршрута для прохождения данных по беспроводной сети, включающие в себя вычисление функции затрат в линии связи, вычисление квантованной функции затрат в линии связи с использованием вычисленной функции затрат в линии связи, вычисление квантованных затрат каждого из множества сквозных маршрутов для прохождения данных по беспроводной сети, при этом множество сквозных маршрутов включает в себя маршруты между одним и тем же набором узлов в беспроводной сети по различным каналам, причем квантованные затраты каждого из множества сквозных маршрутов для прохождения данных по беспроводной сети представляются с использованием квантованной функции затрат в линии связи и при выборе одного из множества сквозных маршрутов для прохождения данных по беспроводной сети на основе квантованных затрат каждого из множества сквозных маршрутов. Также описан узел в беспроводной сети, выполненный с возможностью участвовать в установлении двунаправленного сквозного маршрута для прохождения данных по беспроводной сети, включающий в себя средство для измерения качества и использования каждого канала узла, причем каждый узел имеет несколько каналов, средство для вычисления показателей маршрутизации с использованием измеренного качества и использования каждого канала, средство для обновления таблицы маршрутизации с вычисленными показателями маршрутизации, средство для выбора двунаправленного сквозного маршрута для прохождения данных по беспроводной сети на основе таблицы маршрутизации. Также описаны способ и система для установления сквозного маршрута для прохождения данных по беспроводной сети, включающие в себя вычисление функции затрат в линии связи, вычисление затрат каждого из множества сквозных маршрутов для прохождения данных по беспроводной сети, при этом множество сквозных маршрутов включает в себя маршруты между одним и тем же набором узлов в беспроводной сети по различным каналам, причем затраты каждого из множества сквозных маршрутов для прохождения данных по беспроводной сети представляются с использованием функции затрат в линии связи и выбор одного из множества сквозных маршрутов для прохождения данных по беспроводной сети на основе затрат каждого из множества сквозных маршрутов.
Краткое описание чертежей
Настоящее изобретение лучше будет понятно из последующего подробного описания, иллюстрируемого прилагаемыми чертежами, на которых показано следующее:
Фиг.1 - блок-схема последовательности операций способа установления двунаправленного сквозного маршрута в соответствии с принципами настоящего изобретения.
Фиг.2 - блок-схема последовательности операций способа для этапа вычисления функции затрат в линии связи настоящего изобретения.
Фиг.3 - блок-схема последовательности операций способа определения весовой функции для использования канала настоящего изобретения.
Фиг.4 - блок-схема последовательности операций способа оценки канала настоящего изобретения.
Фиг.5 - блок-схема последовательности операций способа вычисления квантованной функции затрат линии связи настоящего изобретения.
Фиг.6 - блок-схема последовательности операций способа вычисления квантованных затрат маршрутов настоящего изобретения.
Фиг.7 - схематичное представление беспроводной ячеистой сети.
Фиг.8 - блок-схема узла беспроводной ячеистой сети, имеющей модули, чтобы работать в соответствии с принципами настоящего изобретения.
Подробное описание предпочтительных вариантов осуществления
Пусть T oh означает параметр, представляющий протокольную служебную информацию на уровне управления доступом к среде (MAC) и физическом уровне. Пусть S означает размер тестового кадра/пакета. При условии, например, системы радиопередачи по стандарту IEEE 802.11a, T oh может составлять 185 мкс. Для простоты, Toh также может быть задан равным 0. Размер тестового пакета S может быть предварительно определенной и предварительно сконфигурированной константой, например, 8224 бита. Также можно выбирать размер тестового кадра/пакета как средний размер или максимальный размер пакетов, передаваемых посредством узла. Кроме того, пусть R означает скорость передачи данных в линии связи, на которой узел передает данные в форме пакета или в кадре стандартного размера S при текущих характеристиках канала. Скорость передачи данных в линии связи зависит от локальной реализации адаптации скорости линии связи. Пусть E r означает частоту ошибок по пакетам/кадрам, если узел передает пакеты/кадры (данные) стандартного размера S на скорости передачи R. Данные состоят из битов информации. Данные формируются в пакеты или кадры для простоты передачи. E r может быть локально измерен и/или оценен посредством узла в ячеистой сети. Пусть ρ означает загрузку/степень использования канала для линии связи, которая связана с доступной полосой пропускания канала. Показатель маршрутизации настоящего изобретения - это взвешенная функция затрат в линии связи на основе сведений по радиосвязи и полосе пропускания (RABA). Функция затрат RABA для линии радиосвязи L может быть вычислена следующим образом:
где W 1 (ρ) и W 2( E r ) - это две весовые функции использования канала ρ и частоты ошибок по пакетам/кадрам E r, соответственно. Определенная возможная форма W 1 (ρ) следующая:
(a) W 1 (ρ)=1.
В этом случае, все линии связи взвешиваются одинаково с точки зрения использования канала.
В этом случае, линиям связи присваиваются весовые коэффициенты, увеличивающиеся с загрузкой/степенью использования канала.
В этом случае, линии связи с загрузкой/степенью использования канала меньше, чем ρ0 взвешиваются одинаково. Линиям связи с загрузкой/степенью использования канала между ρ0 и ρmax присваиваются весовые коэффициенты, увеличивающиеся с загрузкой/степенью использования канала. Линии связи с использованием канала, превышающим ρmax, не рассматриваются при выборе тракта, поскольку их затраты являются бесконечными. В общем, разработчик системы может выбирать подходящие значения ρmax и ρ0 в зависимости от определенного целевого дохода от использования сети и основных эксплуатационных характеристик.
Аналогично, определенные возможные формы W 2 (E r ) следующие:
(a) W 2 (E r )=1.
В этом случае, все линии связи взвешиваются одинаково с точки зрения частоты ошибок по пакетам.
В этом случае, линиям связи присваиваются весовые коэффициенты, увеличивающиеся с частотой ошибок по пакетам.
В этом случае, линии связи с частотой ошибок по пакетам/кадрам меньше, чем E 0 взвешиваются одинаково. Линиям связи с частотой ошибок по пакетам между E 0 и E max присваиваются весовые коэффициенты, увеличивающиеся с частотой ошибок по пакетам. Линии связи с частотами ошибок по пакетам, превышающими E max, не учитываются при выборе тракта, поскольку их затраты бесконечны. В общем, разработчик системы может выбирать подходящие значения E 0 и E max в зависимости от определенного целевого дохода от использования сети и основных эксплуатационных характеристик.
Следует отметить, что весовые функции W 1 (ρ) и W 2 (E r ) не ограничены вышеприведенными формами. Они также могут быть в других формах.
Функция затрат в линии связи RABA представляет составной показатель маршрутизации, который фиксирует объем радиоресурсов, использованных посредством отправки пакета/кадра данных по конкретной линии связи, и нагрузку и доступную полосу пропускания в линии связи. Функция затрат в линии связи RABA принимает во внимание межпотоковые помехи в совместно используемой беспроводной передающей среде. Тракт/маршрут с более высокой скоростью передачи данных в линии связи, большей доступной полосой пропускания и меньшей частотой ошибок по пакетам, предпочтителен при выборе тракта/маршрута.
Как качество линии связи/канала, так и нагрузка, варьируются, так что значение RABA изменяется часто. Если RABA непосредственно используется в качестве показателя маршрутизации, тракт может часто изменяться, приводя к нестабильности маршрута. Настоящее изобретение также включает в себя способ не только для того, чтобы добиваться быстрого отклика на состояние линии связи и изменения топологии сети, но также сохранять стабильность маршрута. Чтобы повышать стабильность маршрута, квантованная версия RABA используется в качестве функции затрат в линии связи. Квантованный RABA (QRABA) для линии связи L может быть сформулирован следующим образом:
QRABA(L)=Ceiling(M x RABA(L)/Q) (2)
или
или
где M - это число уровней квантования, и Q - это коэффициент квантования. В общем, разработчик системы может выбирать подходящие значения M и Q в зависимости от некоторых целевых компромиссов стабильности маршрута и времени отклика сети на изменения состояния сети и топологии. Например, требуемый уровень квантования, M, может составлять 16, а Q может быть максимальным значением или диапазоном RABA(L). Чтобы использовать ограниченное число битов (поле фиксированного размера) для того, чтобы представлять значение QRABA, значение QRABA может быть усечено до M+1, если оно превышает M+1.
Узел может оценивать загрузку/степень использования канала, используемого посредством линии связи к своим соседям. Один возможный способ для того, чтобы оценивать загрузку/степень использования канала, состоит в том, чтобы использовать время занятости канала. Вследствие совместно используемого характера беспроводных каналов, канал занят, когда какой-либо узел в зоне действия помех выполняет передачу. Когда узел использует канал для того, чтобы передавать данные в форме кадра или пакета по каналу, то этот канал занят. Другие узлы в зоне действия помех не могут одновременно передавать на одной частоте, либо возникает коллизия, и передаваемые кадры/пакеты (данные) имеют состояние ошибки. Кроме того, узел может принимать управляющее сообщение от другого узла, в котором узел резервирует канал на период времени. Канал занят, если узел находится в одном из следующих состояний. Во-первых, узел передает или принимает данные с использованием этого канала/частоты. Во-вторых, узел принимает контрольное/управляющее сообщение от другого узла, которое резервирует канал на период времени. В-третьих, узел распознает занятую несущую с интенсивностью сигнала, превышающей порог в этом канале/частоте. Если оцененное время занятости канала - это T busy в течение периода измерений T ρ, загрузка канала составляет ρ=T busy/T ρ.
Тракт от исходного узла к целевому узлу включает в себя несколько линий связи Li и промежуточных узлов Ni. Li представляет линию связи между узлом Ni и его предыдущим скачком Ni-1 в тракте/маршруте. Затраты RABA тракта P вычисляются следующим образом:
Если квантование используется для того, чтобы повышать стабильность маршрута, затраты QRABA тракта P вычисляются следующим образом:
где линия связи Li+1 - это следующая линия связи после линии связи Li в тракте P, а f Li и f Li+1 представляют каналы/частоты, назначенные для линий связи Li и Li+1, соответственно; α1 (f Li , f Li+1) и α2 (f Li , f Li+1) - это две функции весовых коэффициентов изменения канала (CCW) в зависимости от каналов/частот, назначенных для двух последовательных линий связи в тракте. Определенная возможная форма α1 (fLi, fLi+ 1) следующая:
В этом случае, все линии связи взвешиваются одинаково с точки зрения каналов, назначенных для передачи.
В этом случае, для LastLink в тракте, т.е. линии связи, по которой целевой узел принимает пакет/кадр (данные), функция CCW α1(f Li , f Li+1) равна a 1. Отметим, что целевой узел не должен перенаправлять данные повторно. Если две последовательных линии связи Li и Li+1 в тракте используют один канал/частоту, т.е. промежуточный узел Ni принимает данные из линии связи Li с каналом/частотой f Li и перенаправляет/передает данные по линии связи Li+1 с каналом/частотой f Li+1 =f Li , функция CCW α1(f Li , f Li+1) равна b 1. Если две последовательных линии связи Li и Li+1 в тракте используют различные каналы/частоты, но с одной радиостанцией, т.е. промежуточный узел Ni принимает данные из линии связи Li с каналом/частотой f Li с помощью радиоинтерфейса и перенаправляет/передает данные по линии связи Li+1 с каналом/частотой f Li+1 ≠f Li с помощью того же радиоинтерфейса, функция CCW α1(f Li , f Li+1) равна c 1. Если две последовательных линии связи Li и Li+1 в тракте используют различные каналы/частоты и с различными радиостанциями, т.е. промежуточный узел Ni принимает данные из линии связи Li с каналом/частотой f Li с помощью радиоинтерфейса и перенаправляет/передает данные по линии связи Li+1 с каналом/частотой f Li+1 ≠f Li с помощью другого радиоинтерфейса, функция CCW α1(f Li , f Li+1) равна d 1 . а 1 , b 1 , c 1 и d 1 являются проектными параметрами, которые могут быть предварительно определены разработчиком системы. Например, a 1 =1, b 1 =2, c 1 =1,5 и d 1 =1. Трактам, которые используют один канал/частоту и одну радиостанцию в последовательных линиях связи, присваиваются более высокие весовые коэффициенты/затраты, чем трактам, которые используют различные каналы/частоты и различные радиостанции в последовательных линиях связи.
Аналогично, определенные возможные формы α2 (f Li , f Li+1) следующие:
В этом случае, все линии связи взвешиваются одинаково с точки зрения каналов, назначенных для передачи.
В этом случае, для LastLink в тракте, т.е. линии связи, по которой пункт назначения принимает данные, функция CCW α2(f Li , f Li+1) равна a2. Отметим, что целевой узел не должен пересылать данные повторно. Если две последовательных линии связи Li и Li+1 в тракте используют один канал/частоту, т.е. промежуточный узел Ni принимает данные из линии связи Li с каналом/частотой f Li и пересылает/передает данные по линии связи Li+1 с каналом/частотой f Li+1 =f Li , функция CCW α2(f Li , f Li+1) равна b 2. Если две последовательных линии связи Li и Li+1 в тракте используют различные каналы/частоты, но с одной радиостанцией, т.е. промежуточный узел Ni принимает данные из линии связи Li с каналом/частотой f Li с помощью радиоинтерфейса и пересылает/передает данные по линии связи Li+1 с каналом/частотой f Li+1 ≠f Li с помощью того же радиоинтерфейса, функция CCW α2(f Li , f Li+1) равна c 2. Если две последовательных линии связи Li и Li+1 в тракте используют различные каналы/частоты и с различными радиостанциями, т.е. промежуточный узел Ni принимает данные из линии связи Li с каналом/частотой f Li с помощью радиоинтерфейса и пересылает/передает данные по линии связи Li+1 с каналом/частотой f Li+1 ≠f Li с помощью другого радиоинтерфейса, функция CCW α2(f Li , f Li+1) равна d 2 . a 2 , b 2 , c 2 и d 2 являются проектными параметрами, которые могут быть предварительно определены разработчиком системы. Например, a 2 =0, b 2 =5, c 1 =3, d 1 =0. Трактам/маршрутам, которые используют один канал/частоту и одну радиостанцию в последовательных линиях связи, присваиваются более высокие весовые коэффициенты/затраты, чем трактам/маршрутам, которые используют различные каналы/частоты и различные радиостанции в последовательных линиях связи. Следует отметить, что функции CCW α1 (f Li , f Li+1) и α2 (f Li , f Li+1) не ограничены вышеприведенными формами. Они могут быть в других формах.
Функции CCW α1 (f Li , f Li+1) и α2 (f Li , f Li+1) в тракте/показателе маршрутизации фиксируют воздействие многоканальных элементов с множеством радиостанций на пропускную способность сети, меж- и внутрипотоковые помехи. Тракты/маршруты, которые используют различные каналы и несколько радиостанций, предпочитаются в схеме выбора тракта/маршрута настоящего изобретения. Отметим, что одна радиостанция и один канал - это частный случай многоканальных элементов с множеством радиостанций в настоящем изобретении.
На фиг.1 представлена блок-схема последовательности операций способа установления двунаправленного сквозного маршрута в соответствии с принципами настоящего изобретения. На этапе 105 вычисляется функция затрат в линии связи, как описано выше. Результаты этого вычисления используются для того, чтобы вычислять квантованную функцию затрат в линии связи на этапе 110. На этапе 115 квантованные затраты маршрутов вычисляются с использованием квантованных затрат линии связи. Оптимальный двунаправленный сквозной маршрут для прохождения данных по беспроводной сети, выбирается на этапе 120 на основе вычисленных затрат маршрутов.
На фиг.2 представлена блок-схема последовательности операций способа для этапа вычисления функции затрат в линии связи настоящего изобретения. На этапе 205 определяется протокольная служебная информация для уровня управления доступом к среде и физического уровня. Размер пакета/кадра (данных) определяется на этапе 210. На этапе 215 скорость передачи данных в линии связи периодически определяется. Частота ошибок по пакетам/кадрам периодически определяется на этапе 220. На этапе 225 определяется весовая функция для использования канала. Таким образом, весовая функция может быть выбрана из множества доступных весовых функций, которые доступны, и весовой коэффициент, который должен быть применен для вычисления функции затрат в линии связи для конкретной линии связи, определяется. Весовая функция для частоты ошибок по пакетам/кадрам затем определяется на этапе 230. Опять же, весовая функция может быть выбрана из множества доступных весовых функций, которые доступны, и весовой коэффициент, который должен быть применен для вычисления функции затрат в линии связи для конкретной линии связи, определяется.
На фиг.3 представлена блок-схема последовательности операций способа определения весовой функции для использования канала настоящего изобретения. На этапе 305 использование канала периодически оценивается.
На фиг.4 представлена блок-схема последовательности операций способа оценки канала настоящего изобретения. На этапе 405 определяется период измерения канала, а затем на этапе 410 периодически определяется время занятости канала. Оба из этих определений используются для того, чтобы периодически оценивать использование канала.
На фиг.5 представлена блок-схема последовательности операций способа вычисления квантованной функции затрат в линии связи настоящего изобретения. На этапе 505 определяется число уровней квантования, и коэффициент квантования определяется на этапе 510. Оба из этих значений используются для того, чтобы вычислять квантованную функцию затрат в линии связи на этапе 515.
На фиг.6 представлена блок-схема последовательности операций способа вычисления затрат маршрутов настоящего изобретения. На этапе 605 определяется первая функция весовых коэффициентов изменения канала, и вторая функция весовых коэффициентов изменения канала определяется на этапе 610. Оба из этих значения используются при вычислении затрат маршрутов.
Тракт/показатель маршрутизации QRABA настоящего изобретения может быть применен для того, чтобы выбирать тракт/маршрут в беспроводных ячеистых сетях. Показатель маршрутизации QRABA может быть включен в структуру протоколов/алгоритмов маршрутизации, включающих в себя протоколы проактивной и гибридной маршрутизации, протоколы маршрутизации по требованию, чтобы выбирать маршрут/тракт. Тракт/маршрут с минимальным значением QRABA из трактов между исходным узлом/точкой сетки и целевым узлом/точкой сетки выбирается. Если имеется несколько трактов/маршрутов с одинаковым минимальным значением QRABA, выбирается тракт с минимальным числом перескоков.
На фиг.7 показана примерная ячеистая сеть для того, чтобы помогать понимать настоящее изобретение. Например, тракт от узла A к узлу C состоит из линий связи AB, BC и промежуточного узла B.
Например, если показатель тракта QRABA включается в протокол проактивной маршрутизации с анализом состояния линии связи, такой как протокол оптимизированной маршрутизации с анализом состояния линии связи (OLSR) и протокол маршрутизации по принципу выбора кратчайшего пути (OSPF), затраты линии связи QRABA для каждой из линий связи в ячеистой сети должны быть оценены. Узел в ячеистой сети локально оценивает затраты линии связи QRABA к каждому из своих соседей и уведомляет о затратах QRABA и канале/частоте линии связи в каждый из своих соседей других узлов в сети как часть информации о состоянии линии связи в сообщениях управления маршрутизацией. Каждый узел сохраняет таблицу маршрутизации/пересылки, которая дает ему возможность пересылать данные в форме пакетов или кадров, предназначенных для других узлов в сети. Таблица маршрутизации/перенаправления формируется и обновляется на основе кэшируемой информации о состоянии линии связи, формированной посредством каждого узла. Используя QRABA настоящего изобретения в качестве показателя тракта, узел вычисляет маршрут/тракт к пункту назначения с использованием уравнения (6). В качестве примера, показанного на фиг.7, узел A имеет два тракта к пункту назначения C, A-B-C и A-D-E-F-C. Качество линии связи BC является очень низким и/или нагрузка в линии связи BC является очень высокой, и/или доступная полоса пропускания линии связи BC является очень небольшой, и/или один канал/частота назначен для линии связи AC и линии связи BC так, что затраты QRABA для тракта A-B-C превышают затраты для тракта A-D-E-F-C. Даже если тракт A-B-C содержит меньше перескоков, чем тракт A-D-E-F-C, тракт A-D-E-F-C должен быть выбран посредством узла A для того, чтобы перенаправлять данные в форме пакетов или кадров, предназначенных для узла C. В таблице маршрутизации узла A следующим скачком должен быть узел D, а не узел B, для пункта назначения C.
Другой пример заключается в том, что показатель тракта QRABA включается в протокол маршрутизации по требованию, такой как протокол с использованием вектора расстояния самоорганизующейся сети по требованию (AODV). Тракт с наименьшим значением затрат тракта QRABA обнаруживается, создается и поддерживается, когда исходный узел хочет отправлять данные в форме пакетов или кадров в некоторый целевой узел. Каждый узел имеет механизм для того, чтобы определять затраты в линии связи QRABA к каждому из своих соседей, и знает канал/частоту, используемые для каждой из линий связи динамически или статически. Когда исходный узел хочет отправлять данные в некоторый целевой узел и не имеет допустимого маршрута к этому пункту назначения, исходный узел инициирует обнаружение маршрута посредством лавинной маршрутизации в сети сообщения запроса маршрута (RREQ) во все узлы в сети. Помимо информации, адрес назначения, поле показателя маршрутизации и поле числа перескоков содержатся в сообщении RREQ. Отметим, что каждый узел может принимать несколько копий одного RREQ, который инициируется посредством исходного узла. Каждый из этих RREQ проходит по уникальному тракту от исходного узла к приемному узлу. Приемный узел может быть целевым узлом или может быть промежуточным узлом. Когда промежуточный узел Ni принимает RREQ, он обновляет поле показателя на основе уравнения (6). В частности, этот промежуточный узел Ni добавляет взвешенные затраты линии связи между узлом, от которого он принял сообщение RREQ, и собой, α1 (f Li , f Li+1)×QRABA(Li)+α2 (f Li , f Li+1), к значению в поле показателя RREQ. Функции весовых коэффициентов изменения канала α1 (f Li , f Li+1) и α2 (f Li , f Li+1) зависят от канала/частоты линии связи и радиоинтерфейса, чтобы принимать RREQ, а также линии связи и радиоинтерфейса, чтобы пересылать (повторно лавинно маршрутизировать) в сети RREQ. Промежуточный узел устанавливает свой обратный маршрут к исходному узлу, если он не имеет обратного маршрута, или обновляет свой обратный маршрут к исходному узлу, если этот RREQ представляет новый маршрут, который является более оптимальным, чем текущий маршрут к исходному узлу. Промежуточный узел пересылает (повторно лавинно маршрутизирует) обновленное RREQ. Поле показателя в повторно лавинно маршрутизированном RREQ - это обновленный показатель, который отражает совокупный показатель маршрута между RREQ исходного узла и пересылающего узла.
Когда целевой узел принимает RREQ, он обновляет поле показателя на основе уравнения (6). Целевой узел создает обратный маршрут к исходному узлу в своей таблице маршрутизации, если нет маршрута к исходному узлу в его таблице маршрутизации. Целевой узел обновляет свой текущий обратный маршрут к исходному узлу, если RREQ предоставляет новый маршрут, который является более оптимальным, чем текущий обратный маршрут к исходному узлу. После создания или обновления своего обратного маршрута к исходному узлу, целевой узел отправляет сообщение ответа по маршруту (RREP) в режиме одноадресной передачи в исходный узел. Помимо другой информации, сообщение RREP содержит поле показателя, чтобы переносить информацию о показателе. RREP устанавливает прямой маршрут к целевому узлу в промежуточных узлах и, в конечном счете, в исходном узле. Отметим, что узел (исходный и/или промежуточный) может принимать несколько RREP для одного целевого узла. Когда промежуточный узел принимает сообщение RREP, он обновляет информацию о показателе в своей таблице маршрутизации согласно уравнению (6). Промежуточный узел затем устанавливает маршрут к целевому узлу, если он не имеет маршрута к целевому узлу, или обновляет свой текущий маршрут к целевому узлу, если новый RREP предоставляет маршрут, более оптимальный, чем текущий маршрут к целевому узлу. Если маршрут создан или модифицирован, промежуточный узел перенаправляет RREP в режиме одноадресной передачи в следующий восходящий (в направлении исходного узла) узел по установленному обратному маршруту. Поле показателя в RREP - это обновленный показатель, который отражает совокупный показатель маршрута к целевому узлу от пересылающего узла. После того, как RREP отправлено, если целевой узел принимает дополнительные RREQ с лучшим показателем, то пункт назначения обновляет свой маршрут к исходному узлу и также отправляет новое RREP в исходный узел по обновленному маршруту. Таким образом, двунаправленный оптимальный сквозной маршрут показателя с оптимальным значением показателя тракта QRABA устанавливается между исходным узлом и целевым узлом. В альтернативном варианте осуществления, промежуточные узлы с допустимым маршрутом к целевому узлу также могут отправлять сообщение RREP в режиме одноадресной передачи обратно в исходный узел.
Показатель тракта QRABA настоящего изобретения может быть применен для того, чтобы выбирать тракт в многоскачковых беспроводных сетях на основе древовидной топологии. Показатель маршрута QRABA может быть включен в структуру протоколов/алгоритмов древовидной маршрутизации, чтобы компоновать дерево топологии с корнем в корневом узле и выбирать родительский элемент и тракт. Узел выбирает свой родительский элемент с минимальным значением QRABA между корнем и собой.
Корневой узел периодически отправляет сообщения корневого уведомления (RANN) или сообщения специального запроса маршрута (RREQ) с адресом целевого узла во все узлы в сети. Помимо другой информации, RANN и RREQ содержат поле показателя и поле порядкового номера. Поле показателя инициализируется, и порядковый номер увеличивается, когда корень отправляет новое RANN или RREQ. Когда какой-либо узел в сети принимает RANN или RREQ с адресом целевого узла во все узлы, он обновляет поле показателя на основе уравнения (6). Узел создает свою информацию маршрутизации/перенаправления к корню, если он не имеет информации относительно маршрутизации к корневому узлу. Узел, от которого принимается RANN или RREQ, является его родительским элементом к корневому узлу. Отметим, что каждый узел может принимать несколько копий сообщений RREQ или RANN. Узел обновляет свой родительский элемент и информацию маршрутизации/перенаправления к корню, если RANN или RREQ представляет новый маршрут, лучше чем текущий маршрут к корневому узлу. Например, узел обновляет свой текущий родительский элемент и информацию маршрутизации/перенаправления к корневому узлу, если RANN или RREQ содержит больший порядковый номер или порядковый номер является таким же, как для текущего маршрута и сообщение RANN или RREQ предлагает показатель лучше, чем текущий маршрут к корневому узлу. После создания или обновления своего родительского элемента и информации маршрутизации/перенаправления к исходному узлу, узел перенаправляет (повторно лавинно маршрутизирует) обновленные сообщения RANN или RREQ по сети. Информация о наличии корня(ней) и показателей для доступного корня(ней) распространяется во все узлы сети. Узел может отправлять сообщение регистрации (REGS) или ответа по маршруту (RREP), или запрос маршрута (RREQ) в корневой узел после того, как он принимает сообщения RANN или RREQ с адресом целевого узла для всех узлов, или когда он имеет данные, чтобы отправлять в корневой узел, и ему требуется двунаправленный тракт к корневому узлу. Сообщения REGS или RREP, или RREQ устанавливают/обновляют маршрут от корневого узла к этому узлу.
Фиг.8 - это блок-схема, иллюстрирующая подробности узла с использованием показателя маршрутизации настоящего изобретения. Узел содержит, помимо прочего, модуль 815 выбора маршрута, модуль 805 измерения загрузки/степени использования канала и качества линии связи, модуль 810 вычисления показателей маршрутизации и одни или более модулей 820a,..., 820n интерфейса радиосвязи. Модуль 805 измерения загрузки/степени использования канала и качества линии связи периодически измеряет качество и загрузку/степень использования линии связи/канала к каждому из своих соседей через модули 820a,..., 820n интерфейса радиосвязи. Он предоставляет результаты измерений в модуль вычисления показателей маршрутизации, который периодически вычисляет показатели маршрутизации. Показатели маршрутизации включают в себя функцию затрат в линии связи, квантованную функцию затрат в линии связи и квантованную функцию затрат маршрута. Отметим, что узел может иметь несколько соседей, несколько радиоинтерфейсов и несколько физических/логических каналов и линий связи. Качество и нагрузка всех этих линий связи должна периодически измеряться посредством модуля измерений. Модуль выбора маршрута выполняет протоколы/алгоритмы маршрутизации и определяет маршрут и радиоинтерфейс, чтобы перенаправлять данные. Он также обменивается сообщениями управления маршрутизацией с другими узлами в сети через модули 820a,..., 820n интерфейса радиосвязи. Отметим, что узел может иметь один или более интерфейсов радиосвязи и других интерфейсов связи.
В протоколах проактивной маршрутизации, чтобы поддерживать стабильность маршрута при достижении достаточно быстрого отклика на состояние линии связи и изменения топологии, узел может немедленно уведомлять об изменении состояния линии связи в один из своих соседей (соседних узлов) посредством лавинной маршрутизации сообщений управления маршрутизацией, если и только если изменения в показателе RABA для этой линии связи превышают порог по сравнению со значением в последнем уведомлении. Таким образом, если и только если (RABA(current)-RABA(last))/RABA(last)x100%>T%, узел немедленно лавинно маршрутизирует сообщения управления маршрутизацией, чтобы уведомлять об изменении в состоянии линии связи. Иначе, изменения показателя маршрута уведомляются в следующем периодическом уведомлении.
Следует понимать, что настоящее изобретение может быть реализовано в различных формах аппаратных средств, программного обеспечения, микропрограммного обеспечения, процессоров специального назначения или комбинации означенного. Предпочтительно, настоящее изобретение реализуется как комбинация аппаратных средств и программного обеспечения. Более того, программное обеспечение предпочтительно реализуется как прикладная программа, материально осуществленная на устройстве хранения программ. Прикладная программа может быть загружена в и приведена в исполнение посредством машины, содержащей любую надлежащую архитектуру. Предпочтительно, машина реализуется на компьютерной платформе, имеющей аппаратные средства, такие как один или более процессоров (CPU), оперативное запоминающее устройство (RAM) и интерфейсы ввода-вывода. Компьютерная платформа также включает в себя операционную систему и код микрокоманд. Различные процессы и функции, описанные в данном документе, могут быть либо частью кода микрокоманд, либо частью прикладной программы (или комбинации вышеозначенного), которая приводится в исполнение посредством операционной системы. Помимо этого, различные другие периферийные устройства могут быть подключены к компьютерной платформе, такие как дополнительное устройство хранения данных и печатающее устройство.
Дополнительно следует понимать, что поскольку некоторые из составляющих системных компонентов и этапов способа, изображенных на прилагаемых чертежах, предпочтительно реализуются в программном обеспечении, фактические связи между системными компонентами (или этапами процесса) могут отличаться в зависимости от способа, которым запрограммировано настоящее изобретение. С учетом предлагаемых в данном документе технологий, специалисты в данной области техники смогут рассматривать эти и аналогичные реализации или конфигурации настоящего изобретения.
Изобретение относится к области беспроводных сетей передачи данных. Технический результат заключается в оптимизации структуры механизмов маршрутизации. Сущность изобретения заключается в том, что для установления сквозного маршрута для прохождения данных по беспроводной сети выполняют вычисление функции показателя линии связи, вычисление квантованной функции показателя линии связи с использованием вычисленной функции показателя линии связи, вычисление квантованного показателя каждого из множества сквозных маршрутов для прохождения данных по беспроводной сети, причем квантованный показатель каждого из множества сквозных маршрутов для прохождения данных по беспроводной сети представляется с использованием квантованной функции показателя линии связи и при выборе одного из множества сквозных маршрутов для прохождения данных по беспроводной сети на основе квантованного показателя каждого из множества сквозных маршрутов. Также описывается узел в беспроводной сети, выполненный с возможностью участвовать в установлении двунаправленного сквозного маршрута для прохождения данных по беспроводной сети. 5 н. и 30 з.п. ф-лы, 8 ил.
1. Способ установления двунаправленного сквозного маршрута для прохождения данных по беспроводной сети, причем упомянутый способ содержит этапы, на которых:
вычисляют функцию показателя линии связи;
квантуют упомянутую функцию показателя линии связи для получения квантованной функции показателя линии связи;
определяют первую функцию весовых коэффициентов изменения канала;
определяют вторую функцию весовых коэффициентов изменения канала;
вычисляют квантованный показатель каждого из множества сквозных маршрутов для прохождения данных по упомянутой беспроводной сети с использованием упомянутой первой функции весовых коэффициентов изменения канала и упомянутой второй функции весовых коэффициентов изменения канала; и
выбирают упомянутый двунаправленный сквозной маршрут для прохождения данных по упомянутой беспроводной сети на основе упомянутого квантованного показателя каждого из упомянутого множества сквозных маршрутов.
2. Способ по п.1, в котором упомянутая беспроводная сеть является беспроводной ячеистой сетью.
3. Способ по п.1, в котором упомянутое множество упомянутых сквозных маршрутов существует между одним и тем же набором узлов в упомянутой беспроводной сети по различным каналам и включает в себя множество радиоинтерфейсов, и дополнительно в котором каждый из упомянутого множества сквозных маршрутов является двунаправленным.
4. Способ по п.1, дополнительно содержащий этапы, на которых:
определяют протокольную служебную информацию уровня управления доступом к среде и физического уровня;
определяют размер данных;
периодически определяют скорость передачи данных в линии связи;
периодически определяют частоту ошибок по пакетам;
определяют весовую функцию для использования канала и
определяют весовую функцию для упомянутой частоты ошибок по пакетам.
5. Способ по п.4, дополнительно содержащий этап, на котором периодически оценивают использование канала.
6. Способ по п.5, дополнительно содержащий этапы, на которых:
определяют период измерения канала и периодически определяют время занятости канала.
7. Способ по п.1, дополнительно содержащий этапы, на которых:
определяют число уровней квантования и
определяют коэффициент квантования.
8. Способ по п.1, дополнительно содержащий этапы, на которых:
определяют первую функцию весовых коэффициентов изменения канала и
определяют вторую функцию весовых коэффициентов изменения канала.
9. Способ по п.2, в котором упомянутая беспроводная сеть является проактивной сетью.
10. Способ по п.9, дополнительно содержащий этапы, на которых:
уведомляют о результатах упомянутой вычисленной функции показателя линии связи в качестве информации о состоянии в управляющем сообщении; и
используют упомянутую вычисленную функцию показателя линии связи для того, чтобы формировать и сохранять таблицу маршрутизации.
11. Способ по п.10, дополнительно содержащий этап, на котором немедленно уведомляют об упомянутых результатах упомянутой вычисленной функции показателя линии связи в качестве информации о состоянии в управляющем сообщении, если упомянутые результаты превышают предварительно определенное пороговое значение.
12. Способ по п.2, в котором упомянутая беспроводная ячеистая сеть является сетью по требованию.
13. Способ по п.12, дополнительно содержащий этапы, на которых:
инициируют обнаружение маршрута; и
используют упомянутую вычисленную функцию показателя линии связи для того, чтобы формировать и сохранять таблицу маршрутизации.
14. Способ по п.2, в котором упомянутая беспроводная ячеистая сеть является гибридной ячеистой сетью.
15. Способ по п.2, в котором упомянутая беспроводная ячеистая сеть основана на древовидной топологии.
16. Способ по п.15, дополнительно содержащий этапы, на которых:
выполняют одно из передачи корневого уведомления и инициирования обнаружения маршрута, включающего в себя инициализированное поле показателя и поле порядкового номера;
обновляют упомянутое поле показателя;
обновляют упомянутое поле порядкового номера;
обновляют таблицу маршрутизации и
устанавливают упомянутый двунаправленный сквозной маршрут.
17. Система для установления двунаправленного сквозного маршрута для прохождения данных по беспроводной сети, содержащая:
средство для вычисления функции показателя линии связи;
средство для квантования упомянутой функции показателя линии связи;
средство для определения первой функции весовых коэффициентов изменения канала;
средство для определения второй функции весовых коэффициентов изменения канала;
средство для вычисления квантованного показателя каждого из множества маршрутов для прохождения данных по упомянутой беспроводной сети с использованием упомянутой первой функции весовых коэффициентов изменения канала и упомянутой второй функции весовых коэффициентов изменения канала и
средство для выбора упомянутого двунаправленного сквозного маршрута для прохождения данных по упомянутой беспроводной сети на основе упомянутого квантованного показателя каждого из упомянутого множества маршрутов.
18. Система по п.17, в которой упомянутая беспроводная сеть является беспроводной ячеистой сетью.
19. Система по п.17, в которой упомянутое множество упомянутых сквозных маршрутов существует между одним и тем же набором узлов в упомянутой беспроводной сети по различным каналам и включает в себя множество радиоинтерфейсов, и дополнительно в которой каждый из упомянутого множества сквозных маршрутов является двунаправленным.
20. Система по п.17, дополнительно содержащая:
средство для определения протокольной служебной информации уровня управления доступом к среде и физического уровня;
средство для определения размера данных;
средство для периодического определения скорости передачи данных в линии связи;
средство для периодического определения частоты ошибок по пакетам;
средство для определения весовой функции для использования канала и
средство для определения весовой функции для упомянутой частоты ошибок по пакетам.
21. Система по п.20, дополнительно содержащая средство для периодической оценки использования канала.
22. Система по п.21, дополнительно содержащая:
средство для определения периода измерения канала и
средство для периодического определения времени занятости канала.
23. Система по п.17, дополнительно содержащая:
средство для определения числа уровней квантования и средство для определения коэффициента квантования.
24. Система по п.18, в которой упомянутая беспроводная сеть является проактивной сетью.
25. Система по п.24, дополнительно содержащая:
средство для уведомления об упомянутых результатах упомянутой вычисленной функции показателя линии связи в качестве информации о состоянии в управляющем сообщении; и
средство для использования упомянутой вычисленной функции показателя линии связи для того, чтобы формировать и сохранять таблицу маршрутизации.
26. Система по п.25, дополнительно содержащая средство для немедленного уведомления об упомянутых результатах упомянутой вычисленной функции показателя линии связи в качестве информации о состоянии в управляющем сообщении, если упомянутые результаты превышают предварительно определенное пороговое значение.
27. Система по п.18, в которой упомянутая беспроводная ячеистая сеть является сетью по требованию.
28. Система по п.27, дополнительно содержащая:
средство для инициирования обнаружения маршрута; и
средство для использования упомянутой вычисленной функции показателя линии связи для того, чтобы формировать и сохранять таблицу маршрутизации.
29. Система по п.18, в которой упомянутая беспроводная ячеистая сеть является гибридной ячеистой сетью.
30. Система по п.18, в которой упомянутая беспроводная ячеистая сеть основана на древовидной топологии.
31. Система по п.30, дополнительно содержащая:
средство для выполнения одного из передачи корневого уведомления и инициирования обнаружения маршрута, включающего в себя инициализированное поле показателя и поле порядкового номера;
средство для обновления упомянутого поля показателя;
средство для обновления упомянутого поля порядкового номера и
средство для обновления таблицы маршрутизации.
32. Узел в беспроводной сети, выполненный с возможностью участвовать в установлении двунаправленного сквозного маршрута для прохождения данных по упомянутой беспроводной сети, содержащий:
средство для периодического измерения качества и использования каждого канала упомянутого узла, причем каждый узел имеет несколько каналов;
средство для периодического вычисления показателей маршрутизации с помощью упомянутого измеренного качества и использования упомянутого каждого канала;
средство для периодического обновления таблицы маршрутизации с упомянутыми вычисленными показателями маршрутизации;
средство для выбора упомянутого двунаправленного сквозного маршрута для прохождения данных по упомянутой беспроводной сети на основе упомянутой таблицы маршрутизации.
33. Узел по п.32, причем упомянутый узел имеет, по меньшей мере, один радиоинтерфейс.
34. Способ установления сквозного маршрута для прохождения данных по беспроводной сети, причем упомянутый способ содержит этапы, на которых:
вычисляют функцию показателя в линии связи;
вычисляют показатель каждого из множества сквозных маршрутов для прохождения данных по упомянутой беспроводной сети, при этом упомянутый показатель каждого из упомянутого множества скозных маршрутов для прохождения данных по упомянутой беспроводной сети представляется с использованием упомянутой функции показателя линии связи; и
выбирают один из упомянутого множества сквозных маршрутов для прохождения данных по упомянутой беспроводной сети на основе упомянутого показателя каждого из упомянутого множества сквозных маршрутов.
35. Система для установления сквозного маршрута прохождения данных по беспроводной сети, содержащая:
средство для вычисления функции показателя линии связи;
средство для вычисления показателя каждого из множества сквозных маршрутов для прохождения данных по упомянутой беспроводной сети, при этом упомянутый показатель каждого из упомянутого множества сквозных маршрутов для прохождения данных по упомянутой беспроводной сети представляется с использованием упомянутой функции показателя линии связи; и
средство для выбора одного из упомянутого множеств сквозных маршрутов для прохождения данных по упомянутой беспроводной сети на основе упомянутого показателя каждого из упомянутого множества сквозных маршрутов.
| US 2004093426 A1, 13.05.2004 | |||
| АДРЕСАЦИЯ И МАРШРУТИЗАЦИЯ В БЕСПРОВОДНЫХ ЯЧЕИСТЫХ СЕТЯХ | 2001 |
|
RU2281617C2 |
| WO 2005096566 A, 13.10.2005 | |||
| US 2003202469 A1, 30.10.2003. | |||
