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

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

Иллюстрации

Показать все

Реферат

ОБЛАСТЬ ТЕХНИКИ, К КОТОРОЙ ОТНОСИТСЯ ИЗОБРЕТЕНИЕ

Настоящее изобретение относится к сетям радиодоступа и, более конкретно, к маршрутизации сообщений по узлам ячеистой сети радиодоступа.

УРОВЕНЬ ТЕХНИКИ

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

Альтернативой оптоволоконному транзитному соединению является беспроводное транзитное автосоединение, где тот же спектр доступа используется для обеспечения передачи. При транзитном автосоединении, узел доступа может обслуживать не только собственное закрепленное пользовательское оборудование (UE) поблизости, но также и соседние узлы доступа, в качестве узла передачи, чтобы осуществлять маршрутизацию данных к и/или от агрегирующего узла информации в сети. Фиг. 1 изображает группу узлов 100 радиодоступа с транзитным автосоединением, которые формируют многоскачковую ячеистую сеть. Узлы 100 доступа совместно осуществляют маршрутизацию трафика друг друга к и от агрегирующего узла 104 по линиям 102 беспроводной радиосвязи. Маршруты, которым должен следовать трафик, выбираются алгоритмом маршрутизации. В общем, сеть может содержать больше одного агрегирующего узла и любое число узлов доступа.

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

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

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

РАСКРЫТИЕ ИЗОБРЕТЕНИЯ

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

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

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

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

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

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

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

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

Фиг. 2 изображает направленное графическое представление многоскачковой ячеистой сети;

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

Фиг. 4 изображает базовое графическое представление и четыре расширенных графических представления;

Фиг. 5 изображает систему определения маршрута, в соответствии с некоторыми осуществлениями;

Фиг. 6 изображает сетевой узел определения маршрута, в соответствии с некоторыми осуществлениями;

Фиг. 7 изображает однослотовый маршрут между узлом-источником и узлом-адресатом, в соответствии с некоторыми осуществлениями;

Фиг. 8 изображает n-слотовый маршрут между узлами-источниками и узлами-адресатами по тем же промежуточным узлам, что и для однослотового маршрута, в соответствии с некоторыми осуществлениями;

Фиг. 9 изображает два однослотовых маршрута между двумя парами узлов-источников и узлов-адресатов, в соответствии с некоторыми осуществлениями;

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

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

Фиг. 12-23 изображают блок-схемы дополнительных операций и способов, выполняемых сетевым узлом, как, например, узел определения маршрута на Фиг. 6, в соответствии с некоторыми осуществлениями.

ОСУЩЕСТВЛЕНИЕ ИЗОБРЕТЕНИЯ

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

МНОГОСКАЧКОВЫЕ СЕТИ И СВЯЗАННАЯ ТЕРМИНОЛОГИЯ:

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

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

Фиг. 2 изображает направленное графическое представление многоскачковой ячеистой сети. Со ссылкой на Фиг. 2, каждый узел 100 сети представлен вершиной графа, а каждая (потенциальная) беспроводная линия (скачок) 102 связи в сети представлена ребром графа. Маршрут от узла-источника (например, агрегирующей точки транзитной сети) к узлу-адресату (например, UE или удаленный узел доступа) может далее быть представлен в виде тракта на графе (то есть, чередующейся последовательностью вершин и ребер).

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

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

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

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

Централизованная маршрутизация может включать в себя три этапа: (i) сбор релевантной метрической информации о качестве потенциальных линий связи и/или трактов, (ii) выбор тракта на основании собранной информации, и (iii) передачу информации о выбранном тракте релевантным узлам. Этап (ii) является основным фокусом последующего описания.

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

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

ПОТЕНЦИАЛЬНЫЕ ПРОБЛЕМЫ ПОДХОДОВ, ОПИСАННЫХ ВЫШЕ В УРОВНЕ ТЕХНИКИ И РАСКРЫТИИ ИЗОБРЕТЕНИЯ:

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

Эти проблемы можно избежать с помощью способов, использующих однослотовую маршрутизацию. Однако однослотовая маршрутизация также может иметь недостатки. Если число слотов (на линию связи) в системе, М, велико, то способ потенциально ведет к сильному недоиспользованию пропускной способности сети, так как, вероятно, только 1/М теоретической пропускной способности будет использовано на многих линиях связи. С другой стороны, если М мало, то способ может ограничивать одновременную маршрутизацию к множеству адресатов, так как максимум М маршрутов могут иметь совместную линию связи между двумя соседними узлами, то есть, если есть линия связи, являющаяся ограничением, через которую должны пройти все маршруты, то максимум М маршрутов могут существовать одновременно. Также, способ с малым М может привести к проблемам со слишком большими помехами, так как каждый узел должен будет использовать довольно большую часть полосы частот / времени кадра для связи с ближними узлами.

ОСУЩЕСТВЛЕНИЯ НАСТОЯЩЕГО ИЗОБРЕТЕНИЯ, ОБЕСПЕЧИВАЮЩИЕ УЛУЧШЕНИЯ МАРШРУТИЗАЦИИ:

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

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

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

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

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

Эти и дополнительные осуществления процессов маршрутизации описаны ниже.

УСЛОВНЫЕ ОБОЗНАЧЕНИЯ И ТЕРМИНОЛОГИЯ, ОТНОСЯЩАЯСЯ К ОСУЩЕСТВЛЕНИЯМ НАСТОЯЩЕЙ ЗАЯВКИ:

Дополнительное объяснение различной терминологии и условных обозначений обеспечено в данном разделе перед подробным описанием осуществлений.

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

В базовом представлении, сеть представлена направленным графом G=(V, E), где V обозначает группу графических вершин, а Е обозначает группу ребер, каждое из которых соединяет две вершины в V. Каждый сетевой узел представлен здесь вершиной v ∈ V, и каждая (потенциальная) беспроводная линия (скачок) связи между различными узлами представлена ребром e ∈ Е. Ребро e может быть представлено упорядоченной парой е=(v, v'), где v – узел-источник, а v' – узел-адресат. Здесь неявно предполагается, что в Е нет петель, то есть v≠v' для любого ребра е=(v, v') ∈ Е. Базовое представление существенным образом охватывает топологическую структуру, характеризуемую возможностью межузлового соединения внутри сети. Маршрут от узла-источника (например, агрегирующая точка транзитной сети) к узлу-адресату (например, UE или удаленный узел доступа) может быть представлен в виде тракта Р в сети, который является чередующейся последовательностью вершин и ребер v₁, (v₁, v₂), v₂, (v₂, v₃), v₃, …, v_i, (v_i, v_i+1), v_i+1, …, v_K, где v_i ∈ V для всех i=1, 2, …, K, и (v_i, v_i+1) ∈ Е для всех i=1, 2, …, K-1, где К-1 является числом ребер на тракте Р, v₁ является начальной вершиной, а v_К является конечной вершиной. Для заданного тракта Р, определить V(P) в качестве группы всех вершин {v_i}^K_i=1 на тракте Р, и определить Е(Р) в качестве группы всех ребер {(v_i, v_i+1)}^K-1_i=1 на тракте Р. Базовое графическое представление изображено на Фиг. 2.

В расширенных графических представлениях, сеть снова представлена направленным графом , где и являются группами вершин и ребер, соответственно. (Для ясности, количества, относящиеся к расширенному графу, в общем обозначаются знаком тильда). Однако, в противоположность базовому представлению, каждый реальный узел может соответствовать более чем одной вершине графа, то есть, одна вершина v_K ∈ V в базовом представлении может соответствовать нескольким вершинам , i=1, 2, … I_k в расширенном представлении, где I_k обозначает число вершин в расширенном графе, принадлежащее вершине v_K ∈ V в базовом графе. Также, каждая (потенциальная) беспроводная линия связи может соответствовать более чем одному ребру в расширенном графе; например, каждый слот каждой беспроводной линии связи может быть представлен одним ребром в расширенном графе.

Более формально, в некоторых осуществлениях, при условии, что базовый граф G=(V, E), расширенный граф , G может удовлетворять:

1) существует такое отображение , что для любого , который соответствует реальному узлу v ∈ V; и

2) существует такое отображение , что для любого , который соответствует реальному ребру е ∈ Е, где является подгруппой , которая содержит все ребра , так что (то есть соответствующие реальные узлы любых ребер в различны), и где указано, что ребро соответствует ребру e=(v, v') ∈ Е, тогда и только тогда, когда и .

Из этого следует, что любой базовый граф G=(V, E) также может быть расширенным графом.

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

Существует множество различных вариантов расширенных графических представлений, удовлетворяющих этим требованиям; точный выбор может быть обусловлен конкретной насущной проблемой, например, в зависимости от одного типа сети и того, какая метрика маршрутизации и алгоритм маршрутизации используются. Несколько примеров проиллюстрированы базовым представлением и четырьмя (a)-(d) расширенными представлениями на Фиг. 4. Базовое графическое представление и четыре (a)-(d) различных расширенных представления изображены для случая с двумя узлами сети с линией связи от одного узла к другому. Необходимо отметить, что в представлении (а) на Фиг. 4, существует множество ребер, соединяющих два узла, что означает, что граф является мульти-графом. Расширенное представление (d) на Фиг. 4 может эффективно справляться с внутренними помехами маршрута. Настоящее общее описание условных обозначений и терминологии может применяться к большинству типов расширенных представлений и не ограничено конкретными осуществлениями, раскрытыми в данной заявке, если только прямо не указано обратное.

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

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

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

ПРИМЕР СИСТЕМЫ ОПРЕДЕЛЕНИЯ МАРШРУТА

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

Фиг. 6 изображает сетевой узел 600 определения маршрута в соответствии с некоторыми осуществлениями. Со ссылкой на Фиг. 6, сетевой узел 600 определения маршрута может включать в себя один или несколько сетевых интерфейсов 610, схему 620 процессора и устройства 630 памяти, которые содержат функциональные модули, которые могут включать в себя блок 500 определения однослотового маршрута, блок 510 управления и блок 520 определения дополнительного слотового маршрута.

Схема 620 процессора может включать в себя одну или несколько схем обработки данных, как, например, процессор общего назначения и/или специального назначения (например, микропроцессор и/или процессор цифровых сигналов), которые могут быть совместно расположены либо распределены по одной или нескольким сетям. Схема 620 процессора выполнена с возможностью выполнять команды компьютерной программы от функциональных модулей в устройствах 630 памяти, описанных ниже в качестве машиночитаемых носителей, для выполнения некоторых или всех операций и способов, которые описаны в данной заявке для одного или нескольких осуществлений, как, например, осуществления на Фиг. 7-23, описанные ниже. Соответственно, схема 620 процессора может быть выполнена с возможностью выполнять команды компьютерной программы в функциональных модулях для реализации, по меньшей мере, функциональности, описанной в данной заявке, для маршрутизации связи между парами узлов-источников и узлов-адресатов через ячеистую сеть узлов системы беспроводной связи.

Сетевой узел 600 определения маршрута может быть включен в или быть отдельным, но соединенным с возможностью осуществления связи, с любым узлом радиодоступа для управления узлом радиодоступа, чтобы выполнять операции в соответствии с одним или несколькими осуществлениями данной заявки. Узел радиодоступа может включать в себя, но не ограничен, приемопередающий узел доступа беспроводной локальной сети (WLAN), приемопередающий узел доступа глобальной совместимости (WiMAX) для микроволнового доступа и/или сотовую приемопередающую базовую станцию.

ПРИМЕРЫ ОПЕРАЦИЙ И СПОСОБОВ, ОБЕСПЕЧИВАЮЩИХ МАРШРУТИЗАЦИЮ ЧЕРЕЗ ЯЧЕИСТУЮ СЕТЬ УЗЛОВ

Примеры операций и способов обеспечения маршрутизации через ячеистую сеть узлов объяснены ниже со ссылкой на Фиг. 7-11. Фиг. 11 изображает блок-схему операций и способов, которые обеспечивают определение маршрута через ячеистую сеть сетевых узлов, в соответствии с некоторыми осуществлениями. Операции на Фиг. 11 могут быть выполнены, например, системой на Фиг. 5 и/или сетевым узлом 600 определения маршрута на Фиг. 6.

Для изображенных на Фиг. 11 этапов, предполагается, что существует группа узлов-источников v^(s)_n, n=1, 2, …, N_c, которые надо соединить попарно с группой узлов-адресатов v^(d)_n, n=1, 2, … N_c, то есть для каждого n, v^(s)_n должен быть соединен с v^(d)_n по маршруту, где N_c обозначает число пар источник-адресат. Предполагается, что в расширенном графе каждый узел-источник v^(s)_n содержит один виртуальный узел-источник, обозначаемый , и предполагается, что каждый узел-адресат содержит один виртуальный узел-адресат, обозначаемый . Узлы-источники и узлы-адресаты необязательно все различны (например, может быть так, что для некоторых и/или ). Следовательно, целью является найти, для каждой пары узлов , группу слотовых маршрутов , соединяющих пару, где j=1, 2, …, J_n является индексом, нумерующим все слотовые маршруты от до . (Величина J_n, таким образом, обычно не известна до тех пор, пока не завершена вся процедура маршрутизации). Поэтапная процедура выполняется следующим образом:

Со ссылкой на Фиг. 11, на этапе 1100, множество запросов на маршрут связи принимают от множества узлов-источников. Информация расширенного графа формируется (этап 1102), например, блоком 510 управления, который определяет доступные сетевые узлы и связывает слоты ресурсов линий беспроводной связи между сетевыми узлами, которые включают в себя узлы-источники и узлы-адресаты. По меньшей мере, одну определенную метрику (например, доступную скорость передачи данных, потребление энергии и/или другие определенные метрические параметры слотов ресурсов линий беспроводной связи) определяют (этап 1104), например, с помощью блока 510 управления, для каждого слота ресурсов линий беспроводной связи между сетевыми узлами.

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