Результат интеллектуальной деятельности: СПОСОБЫ И УСТРОЙСТВА ДЛЯ МАРШРУТИЗАЦИИ СООБЩЕНИЙ С ИСПОЛЬЗОВАНИЕМ СТВОЛОВЫХ РЕСУРСОВ ЯЧЕИСТЫХ СЕТЕЙ РАДИОДОСТУПА

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

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

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

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

Альтернативой оптоволоконному транзитному соединению является беспроводное транзитное автосоединение, где тот же спектр доступа используется для обеспечения передачи. При транзитном автосоединении, узел доступа может обслуживать не только собственное закрепленное пользовательское оборудование (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 определения однослотового маршрута, между каждым из последовательности сетевых узлов по маршруту связи между идентифицированными узлами-источниками и узлами-адресатами. Определение однослотового маршрута может быть выполнено с помощью применения алгоритма Беллмана-Форда или алгоритма Дейкстры, которые известны в текущем уровне техники. В расширенном графическом представлении, один слотовый маршрут устанавливается для каждой виртуальной пары узлов источник-адресат, где m=1, 2, …, Nc.

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

На этапе 1110, расширенное графическое представление сети сокращают, например, с помощью блока 520 определения дополнительного слотового маршрута, путем исключения из дальнейшего рассмотрения маршрута связи между выбранной парой виртуальных узлов источник-адресат сетевых узлов, которых нет в последовательности сетевых узлов, которые были ранее выбраны по маршруту связи между выбранной парой виртуальных узлов источник-адресат. Более конкретно, расширенное графическое представление сети может быть сокращено путем удаления всех вершин (виртуальных узлов) за исключением тех, которые соответствуют реальному узлу (базовой графической вершине), через которую проходит (то есть, вершина исключается тогда и только тогда, когда ), и путем удаления всех ребер, через которые проходит любой ранее установленный слотовый маршрут (то есть, ребро исключается тогда и только тогда, когда для любого , n'=1, 2, …, Nc, j=1, 2, …, jlatestn’, где jlatestn’ является индексом последнего установленного маршрута для пары источник-адресат ). Эта процедура сокращения может быть изменена, когда расширенный граф является мульти-графом, как объяснено ниже с учетом некоторых альтернативных подходов, в соответствии с другими осуществлениями.

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

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

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

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

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

Теперь делается ссылка на Фиг. 7-10 для иллюстрации различных аспектов процессов определения маршрута, которые выполняются, например, сетевым узлом 600 определения маршрута. Фиг. 7 изображает однослотовый маршрут S1, который установлен между узлом-источником 700-1 и узлом-адресатом 701-1 через множество сетевых узлов 702-708, в соответствии с некоторыми осуществлениями. Фиг. 8 изображает n-слотовый маршрут Sn, который установлен между узлом-источником 700-1 и узлом-адресатом 701-1 по тем же промежуточным узлам 702-708, что и для однослотового маршрута, в соответствии с некоторыми осуществлениями. В осуществлении на Фиг. 7 и 8, предполагается, что узел-источник 700-1 и узел-адресат 701-1 являются единственным узлом источник-адресат, которому нужно назначение слота в данный момент времени, или, альтернативно, предполагается, что процесс маршрутизации выполняет операции для завершения назначения слота паре узлов 700-1, 701-1 источник-адресат до формирования многослотового маршрута между другой парой узлов 700-n, 701-n источник-адресат.

Фиг. 9 изображает первый однослотовый маршрут S1, который установлен между первой парой узлов 700-1, 701-1 источник-адресат, и второй однослотовый маршрут S2, который установлен между второй парой узлов 700-1, 701-n источник-адресат, в соответствии с некоторыми осуществлениями. В осуществлении на Фиг. 9, некоторые сетевые узлы 702, 704 и 706 используются совместно первым и вторым однослотовыми маршрутами S1, S2 (то есть, слоты ресурсов этих узлов поддерживают оба маршрута S1, S2). Фиг. 10 изображает пример сокращения некоторых сетевых узлов в ячеистой сети и назначение другого слота той же последовательности сетевых узлов 702-708 по двум маршрутам S1, S2, в соответствии с некоторыми осуществлениями.

АЛЬТЕРНАТИВНЫЕ ПОДХОДЫ К ДОПОЛНИТЕЛЬНЫМ ОСУЩЕСТВЛЕНИЯМ

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

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

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

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

Этап 1112 на Фиг. 11 может быть изменен для установления новых слотовых маршрутов (то есть, слотовых маршрутов, для которых j>1) не всегда от источника к адресату , но скорее между любой парой виртуальных узлов, выбранных из группы виртуальных узлов, которые принадлежат любому из реальных узлов, через которые проходит исходный слотовый маршрут. Это может быть выгодно для метрик типа метрики скорости передачи данных, где одна или несколько линий связи (скачков) может составлять ограничение связи для пропускной способности, что означает, что только тем линиям связи необходимо соединение с помощью дополнительных слотовых линий связи.

Еще один этап может быть добавлен между этапами 1112 и 1114 на Фиг. 11, который удаляет одну или несколько слотовых линий связи из последнего установленного слотового маршрута. Этот этап может служить той же или подобной цели, что и способ частичного маршрута в предыдущем абзаце (разница заключается в том, что при использовании этапа 204b, сперва устанавливают полный слотовый маршрут до того, как удалить ненужные слотовые линии связи).

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

Этап 1110 на Фиг. 11 может быть изменен путем замещения этапа сокращения на втором под-этапе следующим этапом сокращения: Удалить все вершины (виртуальные узлы), через которые проходит любой уже установленный слотовый маршрут, за исключением того, что узлы и не должны быть удалены (то есть, вершину удаляют тогда и только тогда, когда для любого , где опять является индексом последнего установленного маршрута для пары источник-адресат и\обозначает разницу между множествами. Опционально, это изменение может быть скомбинировано с ранее описанным сокращением вершин на этапе 1110 на Фиг. 11.

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

Может существовать множество виртуальных узлов-источников и/или виртуальных узлов-адресатов в одном реальном узле. Это может быть полезным представлением, например, если одновременно есть несколько пакетных потоков к одному реальному узлу.

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

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

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

После установления всех слотовых маршрутов для всех пар источник-адресат, осуществление может рассматривать все маршруты, принадлежащие данной паре источник-адресат, в качестве одного маршрута (для более высоких уровней, например, ТСР).

ДОПОЛНИТЕЛЬНЫЕ ОПЕРАЦИИ И СПОСОБЫ НЕКОТОРЫХ ОСУЩЕСТВЛЕНИЙ

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

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

Многослотовый выбор может быть ограничен слотами, доступными только из последовательности сетевых узлов однослотового маршрута. Эти дополнительные операции и способы изображены в дополнительном осуществлении на Фиг. 13, где выбор (этап 1202 на Фиг. 12) другого слота ресурсов линии беспроводной связи, по меньшей мере, между некоторыми из последовательности сетевых узлов ограничен выбором (этап 1300) среди слотов ресурсов, которые доступны только из последовательности сетевых узлов по маршруту связи между одной парой узлов-источников и узлов-адресатов.

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

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

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

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

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

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

Некоторые метрики могут быть изменены в зависимости от предыдущих выборов слотов ресурсов. В дополнительном осуществлении на Фиг. 19, по меньшей мере, одна метрика изменена (этап 1900), по меньшей мере, для одного из слотов ресурсов одного из сетевых узлов в ответ на уровень помех связи, которые будут созданы более ранним выбором другого из слотов ресурсов одного из сетевых узлов. Изменение (этап 1900) может включать в себя уменьшение скорости передачи данных, указанной, по меньшей мере, одной метрикой, по меньшей мере, для одного из слотов ресурсов одного из сетевых узлов, на количество, определенное из уровня помех связи.

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

В дополнительном осуществлении на Фиг. 21, запланированный уровень мощности передачи изменяют (этап 2100) для одного конкретного из слотов ресурсов одного из сетевых узлов в зависимости от доступной скорости передачи данных одного конкретного слота ресурсов.

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

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

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

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

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

СОКРАЩЕНИЯ

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

3GPP - Проект партнерства третьего поколения

BSS - Подсистема базовой станции

CS - С коммутацией каналов

CSFB - Переход на сеть, поддерживающую коммутацию каналов

EDGE - Развитие стандарта GSM с увеличенной скоростью передачи данных

E-UTRAN - Усовершенствованная Сеть наземного радиодоступа

eNodeB - E-UTRAN NodeB

FULL-MOCN - Базовая сеть FULL с несколькими операторами

GERAN - Сеть радиодоступа GSM EDGE

GPRS - Система пакетной радиосвязи общего пользования

IE - Элемент информации

IMS - Мультимедийная подсистема IP

LAU - Обновление местоположения

MME - Узел управления мобильностью

MS - Мобильная станция

MSC - Центр коммутации мобильной связи

PLMN - Наземная сеть мобильной связи общего пользования

PS - С коммутацией пакетов

RNC - Контроллер радиосети

RNS - Подсистема радиосети

SGSN - Узел поддержки обслуживания GPRS

SI - Системная информация

UMTS - Универсальная система мобильной связи

UTRAN - Сеть наземного радиодоступа UMTS

ДОПОЛНИТЕЛЬНЫЕ ОПРЕДЕЛЕНИЯ:

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

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

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

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

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

Физический, энергонезависимый машиночитаемый носитель может включать в себя электронную, магнитную, оптическую, электромагнитную или полупроводниковую систему хранения данных или устройство. Более конкретные примеры машиночитаемого носителя включают в себя следующие: портативную компьютерную дискету, схему оперативного запоминающего устройства (RAM), схему постоянного запоминающего устройства (ROM), схему стираемого программируемого постоянного запоминающего устройства (EPROM или флэш-память), портативное постоянное запоминающее устройство (CD-ROM) на компакт-дисках и портативное постоянное запоминающее устройство (DVD/BlueRay) на цифровых дисках.

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

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

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

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