СПОСОБ И УСТРОЙСТВО УПРАВЛЕНИЯ ДОПУСКОМ ДАННЫХ В ЯЧЕИСТОЙ СЕТИ
METHOD AND DEVICE FOR DATA ACCESS CONTROL IN CELLULAR NETWORK

Притязание на приоритет по разделу 35 §119 Кодекса законов США.
Настоящая заявка на патент претендует на приоритет предварительной заявки №60/728 247, поданной 18 октября 2005 г., правопреемником которой является правопреемник данного документа, и которая полностью включена по ссылке в данный документ.
Уровень техники
Область техники, к которой относится изобретение
Описание относится к ячеистым сетям. Более конкретно, описание относится к способу и устройству управления допуском в ячеистой сети.
Уровень техники
В последние годы увеличилась потребность в широко распространенном доступе к высокоскоростным услугам передачи данных. Индустрия телекоммуникаций ответила на увеличение спроса предложением разнообразных беспроводных изделий и услуг. Пытаясь сделать эти изделия и услуги с возможностью взаимодействия с другими изделиями и сетями, Институт инженеров по электротехнике и радиоэлектронике (ИИЭР) опубликовал ряд стандартов по беспроводным локальным сетям (БЛС), например IEEE 802.11. Изделия и услуги, которые соответствуют этим стандартам, часто подключаются к сети в беспроводной конфигурации «точка-многоточка». В одной конфигурации индивидуальные беспроводные устройства (например, станции) могут обмениваться данными непосредственно с точкой доступа к Интернету, причем каждое из беспроводных устройств совместно использует доступную пропускную способность.
Другой конфигурацией может быть ячеистая сеть. Ячеистая сеть может представлять собой распределенную сеть, имеющую многочисленные беспроводные узлы. Каждый узел может служить в качестве повторителя, способного принимать трафик, передавать или транспортировать потоки (ПТ) и транслировать ПТ на следующий узел. ПТ может проходить с узла источника на узел назначения «скачками» с узла на узел. Алгоритмы маршрутизации ПТ могут гарантировать, что ПТ эффективно маршрутизируются с их узла источника на их узел назначения. Алгоритмы маршрутизации ПТ могут динамически адаптироваться к изменениям в ячеистой сети и могут сделать ячеистую сеть более эффективной и гибкой. Например, в случае если узел является очень занятым, чтобы манипулировать ПТ, или если узел выбыл из ячеистой сети, алгоритм маршрутизации ПТ может маршрутизировать ПТ на узел назначения через другие узлы в сети.
Ячеистые сети часто могут включать в себя иерархию узлов с различными рабочими характеристиками. В некоторых архитектурах ячеистой сети узлы в нижней части иерархии могут включать в себя станции. Станции могут включать в себя индивидуальные беспроводные устройства, такие как портативный компьютер или персональный цифровой помощник, наряду с многими другими. Ячеистые точки могут включать в себя узлы, которые могут рассматриваться как уровень над станциями. Ячеистые точки также могут формировать беспроводную магистраль. Ячеистые точки могут иметь возможность принимать ПТ от других ячеистых точек и передавать ПТ на них. Ячеистые точки доступа (ЯТД), специальный тип ячеистой точки, могут обеспечивать шлюз или путь соединения между станциями и ячеистыми точками. Ячеистые точки доступа могут давать возможность ПТ выполнять «скачок» между станцией и ячеистой точкой. Ячеистые порталы, другой специальный тип ячеистой точки, могут обеспечивать шлюз для устройств, которые соответствуют другим беспроводным стандартам, например 802.11(a/b/g/n). Ячеистые порталы могут дать возможность ПТ из неячеистых сетей войти в ячеистую сеть и выйти из нее.
Устройства связи, соответствующие 802.11(s), могут иметь различные требования по качеству обслуживания (КО) для ПТ. КО может включать в себя ряд параметров, таких как количество отброшенных пакетов, времена задержки передачи пакета, искажения пакета, количество пакетов с измененным порядком доставки и количество пакетов, принятых с ошибкой, наряду с многими другими. Используя эти параметры, можно видеть, что различным устройствам передачи данных, пользователям и приложениям могут требоваться различные КО. Например, Интернет-телефонии может требоваться КО с малым временем задержки передачи пакета и небольшим искажением пакета, чтобы сделать двусторонний разговор понятным. Потоковая видеолекция также может потребовать небольшое искажение пакета, чтобы получить презентабельные видеоизображения, и согласованную одностороннюю звуковую дорожку, но большая задержка передачи пакета может быть допустимой. Требования к КО могут становиться даже более критичными и сложными, когда увеличивается разнообразие устройств передачи данных, пользователей и приложений. Например, опыт интерактивных игр в реальном времени между двумя людьми в двух различных географических областях могут иметь очень сложные и жесткие требования к КО.
Широкомасштабное использование беспроводных устройств в ячеистых сетях может накладывать сложные проблемы на конструкцию сети, включая управление допуском ПТ с различными требованиями к КО и приоритетами, наряду с многими другими.
Сущность изобретения
Информация о нагрузке по трафику вокруг ячеистых узлов может быть известна или относительно легко может быть определена. Ячеистые узлы могут использовать информацию о нагрузке по трафику для определения локальной беспроводной пропускной способности, доступной для размещения новых потоков трафика (ПТ) на каждом узле. Алгоритмы маршрутизации ПТ могут оценивать потенциальные маршруты для новых ПТ по ячеистой сети. Узел источника может инициировать запрос на допуск нового ПТ по потенциальному маршруту ПТ. Запрос на допуск может посылаться с узла на узел от узла источника на узел назначения. Каждый узел, принимающий запрос на допуск, может сравнивать запрос на допуск с информацией о локальной нагрузке по трафику и может определить, может ли быть размещен новый ПТ. Если ПТ может быть размещен, выделяется возможность передачи (ТХОР), и запрос на допуск может распространяться на следующий узел по потенциальному маршруту. Если ПТ не может быть размещен, запрос ПТ может быть отклонен, и запрос на допуск может распространяться по другим потенциальным маршрутам.
Способ управления потоком трафика в ячеистой сети содержит прием на втором узле запроса на допуск потока трафика для допуска потока трафика от первого узла, определение нагрузки по трафику для второго узла и определение, допустить ли или отклонить поток трафика от первого узла, используя нагрузку по трафику.
Краткое описание чертежей
Заявленный предмет особенно указывается и отчетливо заявляется в заключительной части описания изобретения. Однако этот предмет может быть понят посредством ссылки на последующее подробное описание, рассматриваемое с прилагаемыми чертежами, на которых:
Фиг.1 представляет собой схему примерной ячеистой сети согласно варианту осуществления.
Фиг.2 представляет собой схему части примерной ячеистой сети по фиг.1, изображающую потоки трафика (ПТ), передаваемые и принимаемые на примерной ячеистом узле, согласно варианту осуществления.
Фиг.3 представляет собой схему части ячеистой сети по фиг.1, изображающую информацию о потоке трафика для примерного узла и каждого из узлов вблизи примерного узла согласно варианту осуществления.
Фиг.4 представляет собой схему части ячеистой сети по фиг.1, изображающую информацию о потоке трафика для примерного узла и каждого из узлов вблизи примерного узла согласно варианту осуществления.
Фиг.5 представляет собой схему части ячеистой сети по фиг.1, изображающую информации о потоке трафика для примерного узла и каждого из узлов вблизи примерного узла согласно варианту осуществления.
Фиг.6 представляет собой схему протекания ПТ, иллюстрирующую управление допуском ПТ на первом узле по потенциальному маршруту ПТ согласно варианту осуществления.
Фиг.7 представляет собой схему протекания ПТ, иллюстрирующую управление допуском ПТ на примерном узле по потенциальному маршруту ПТ согласно варианту осуществления.
Фиг.8 представляет собой схему протекания, иллюстрирующую управление допуском ПТ на узле назначения по потенциальному маршруту ПТ согласно варианту осуществления.
Фиг.9 представляет собой блок-схему последовательности операций, иллюстрирующую способ управления допуском ПТ на примерном узле по потенциальному маршруту ПТ согласно варианту осуществления.
Фиг.10 представляет собой блок-схему, иллюстрирующую примерные компоненты для устройства и средства для устройства для управления допуском согласно варианту осуществления.
Подробное описание
Способы и устройство, которые реализуют варианты осуществления различных признаков описания, ниже описываются с ссылкой на чертежи. Чертежи и связанное с ними описание предназначены для иллюстрации вариантов осуществления описания и не для ограничения объема описания. Ссылка в описании изобретения на «один вариант осуществления» или «вариант осуществления», как предполагается, указывает, что конкретный признак, конструкция или характеристика, описанная в связи с вариантом осуществления, включена по меньшей мере в вариант осуществления описания. Появления фразы «в одном варианте осуществления» или «вариант осуществления» в различных местах в описании изобретения не обязательно все ссылаются на один и тот же вариант осуществления. На чертежах позиции используются повторно для указания соответствия между ссылаемыми элементами. Кроме того, первая цифра каждой позиции указывает фигуру, на которой элемент появляется в первый раз.
Фиг.1 представляет собой схему примерной ячеистой сети 100 согласно варианту осуществления. Ячеистая сеть 100 может быть иерархической сетью ячеистых узлов и может включать в себя, например, с первого узла 101 по двадцать третий узел 123. Сеть 100 может включать в себя многие различные типы узлов и устройств, как указано в данном варианте осуществления легендой 130. Ячеистая сеть 100 может включать в себя множество станций (STA), таких как с первого по четырнадцатый узел 101-114. В одном варианте осуществления одна станция (например, 101) может не связываться с другой станцией (например, 102). Станциями могут быть любые устройства, которые соответствуют беспроводному стандарту ячеистой сети 100. Станции, например, могут включать в себя компьютеры, персональные цифровые помощники, сетевые игровые устройства, телефоны, телевизоры или терминалы. Беспроводным стандартом ячеистой сети 100 может быть любой фирменный стандарт и/или стандарт открытой архитектуры, такой как, но не ограничиваясь им, стандарт IEEE 802.11(s).
Ячеистая сеть 100 может включать в себя один или несколько ЯТД, такие как узлы 115-117 и 119. Станции могут формировать базу иерархии ячеистой сети и могут обращаться к ячеистым узлам, расположенным выше в иерархии, через узлы шлюзов, такие как ячеистые точки доступа (ЯТД) и ячеистые порталы. Станция, такая как узел 102, может обращаться к ЯТД, такому как узел 115, по непосредственной линии 134 связи. Линия 134 связи может быть проводной, беспроводной и/или их комбинацией. Станция, такая как узел 101, может обращаться к ячеистой точке, такой как узел 122, посредством перемещения с узла 101 на узел 115 и на узел 122.
Ячеистые порталы могут включать в себя узлы, которые могут обмениваться данными с неячеистыми устройствами, как показано на фиг.1. Ячеистая сеть 100 может включать в себя один или несколько ячеистых порталов, например узел 118. Ячеистый портал, такой как узел 118, может обмениваться данными с неячеистыми устройствами, такими как устройства 141-145. Неячеистые устройства могут быть объединены в локальную сеть, которая характеризуется неячеистыми соединениями 114, такими как соединения Эзернета, среди прочих. Например, неячеистые устройства 141-145 могут быть объединены проводным образом в звездообразную конфигурацию, используя медный провод витой пары. Каждый из неячеистых устройств 141-145 может быть выполнен с возможностью соответствия или может быть выполнен без возможности соответствия протоколам ячеистой сети 100.
В одном варианте осуществления узлом 118 может быть концентратор сети Эзернет и может соответствовать протоколу ячеистой сети. Узел 118 может предоставлять возможность ПТ, исходящим от каждого неячеистого устройства 141-145, распространяться в ячеистую сеть 100. Таким образом, ячеистый портал 118 может иметь возможность служить в качестве шлюзов ячеистой сети 100 для неячеистых устройств 141-145. Сети, характеризующиеся ячеистыми порталами 118 и неячеистыми устройствами 141-145, могут не ограничиваться сетями Эзернета; другие сети могут конфигурироваться и могут работать аналогичным образом. Неячеистые устройства 141-145 могут конфигурироваться в многочисленных различных типах сетей, таких как, но не ограничиваясь ими, кольцевые сети с маркерным доступом и/или сети «точка-многоточка» 802.11(b), и/или их комбинации.
Ячеистый портал 118 также может иметь линию связи с Интернетом или с другой широкомасштабной сетью, например, через узел 119. Узел 119 может быть соединен с магистралью Интернета, делая узел 119 точкой доступа к Интернету, а также ячеистым порталом. Узел 119 может формировать мост между беспроводной ячеистой сетью 100 и Интернетом. Мост может служить в качестве соединения между любым из узлов в ячеистой сети 100 и любым устройством с возможностью подключения к Интернету.
Ячеистые точки могут включать в себя узлы, которые могут транслировать данные между другими ячеистыми точками, ЯТД и/или ячеистыми порталами. Ячеистая сеть 100 может включать в себя одну или несколько ячеистых точек, таких как узлы 120-123. Ячеистые точки, ЯТД и ячеистые порталы могут формировать верхний уровень ячеистых узлов в иерархии ячеистой сети 100. ПТ, исходящие с неячеистых устройств и станций, могут поступать на верхний уровень через ячеистые порталы и ЯТД. ПТ могут распространяться по узлам верхнего уровня ячеистой сети 100 до тех пор, пока они не выйдут через другой ячеистый портал и/или ЯТД.
1
2
3
4
5
Фиг.1 также изображает маршрутизацию примерного потока трафика (ПТ), показанного как Мо. В одном варианте осуществления ПТ Мо может исходить от узла 108 (например, станции 108) в ячеистой сети 100. ПТ Мо также может завершаться на узле 113 (например, станции 113) в ячеистой сети 100. Подходящий маршрут ПТ от узла 108 до узла 113 может определяться с использованием алгоритма маршрутизации. После того как будет определен подходящий маршрут ПТ, может согласовываться доступ и ТХОР на каждом узле по маршруту. ПТ Мо затем может передаваться по маршруту. Узел 108 может иметь возможность передачи ПТ Мо на узел 116 посредством первого скачка Н. Узел 116 может иметь возможность приема ПТ Мо и дополнительно может иметь возможность передачи ПТ Мо на узел 117 посредством второго скачка Н. Узел 117 может иметь возможность приема ПТ Мо и может иметь возможность передачи ПТ Мо на узел 120 посредством третьего скачка Н. Узел 120 может иметь возможность приема ПТ Мо и передачи ПТ Мо на узел 119 посредством четвертого скачка Н. Узел 119 может иметь возможность передачи ПТ Мо на узел 113 посредством пятого и конечного скачка Н данного варианта осуществления.
17
21
22
17
19
21
17
21
22
17
19
21
Фиг.2 представляет собой схему части примерной ячеистой сети 100 по фиг.1, изображающую ПТ, переданные и принятые на примерном ячеистом узле 120. В данном варианте осуществления узел 120 может иметь возможность передачи и приема ПТ от четырех других узлов 117, 119, 121 и 122. Узел 120, как полагается, может быть в сети, соседней с этими четырьмя узлами. В данном варианте осуществления узел 120 может иметь возможность приема ПТ R, R и R от узлов 117, 121 и 122, соответственно. Также, узел 120 может иметь возможность передачи ПТ Т, Т и Т на узлы 117, 119 и 121, соответственно. Отметьте, что в данном примере узлы 117, 119 или 121 не являются «листовыми» узлами, ПТ R, R и R и Т, Т и Т сами могут представлять собой совокупности других ПТ на узлах 117, 119 или 121.
busy
20
T17
17
T19
19
T21
21
T22
T22
20
T17
17
Трафик на узле 120 может представляться двумя векторами (т.е. вектором передачи и вектором приема). В одном варианте осуществления ПТ может представляться долей времени, занимаемой на канале для передачи данных, связанных с ПТ, по установленному периоду времени, например планируемому интервалу обслуживания (ПИО). Нагрузка по трафику или средняя загруженность в этом контексте может представляться величинами, такими как t, где значение указывает величину времени, занимаемую на канале в виде занятости по установленному периоду времени, например планируемому интервалу обслуживания (ПИО). Таким образом, вектор T передачи (показанный позицией 210) может иметь четыре элемента, причем первым элементом является время t передачи ПТ Т от узла 120 на узел 117, вторым элементом является время t передачи ПТ Т от узла 120 на узел 119, третьим элементом является время t передачи ПТ Т от узла 120 на узел 121 и четвертым элементом является время t передачи ПТ от узла 120 на узел 122. В данном примере, четвертый элемент t вектора Т 210 передачи будет равен нулю, так как узел 120 не передает никаких ПТ на узел 122. В данном случае, t представляет собой время, занимаемое на канале для передачи ПТ Т по ПИО.
20
R17
17
R19
19
R21
21
R22
R19
20
R17
17
Аналогично, вектор R (показанный позицией 212) приема может иметь четыре элемента, причем первым элементом является время t приема ПТ R от узла 117, вторым элементом является время t приема ПТ R от узла 119, третьим элементом является время t приема ПТ R от узла 121 и четвертым элементом является время t приема ПТ от узла 122. В данном примере второй элемент t вектора R 212 приема будет равен нулю, так как узел 120 не принимает никакого ПТ от узла 119. Снова в данном случае t представляет собой время, занимаемое на канале для передачи ПТ R по ПИО.
load
busy
qnav
qnav
qnav
load
load
Нагрузка по трафику (t), т.е. величина времени, когда среда вокруг узла 120 может считаться загруженной, как часть ПИО, на узле 120 или любом другом узле может определяться различным образом, включая измерение. В одном варианте осуществления узел 120 может иметь возможность контролировать индикацию занятости оценки занятости канала (ОЗК), что обнаруживается физическим уровнем узла 120 для определения времени занятости (t). Узел 120 также может иметь возможность контролировать время молчания (t) вектора назначения сети для учета доли времени, когда узел 120 не может передавать, даже если индикация занятости ОЗК может указывать, что канал не является занятым. Вектор распределения сети (ВРС) получается посредством обработки резервирования от соседних узлов. Время молчания (t) может представлять время, когда канал недоступен, так что узлы 117, 119, 121, 122, подсоединенные к узлу 120, могут иметь возможность приема передач данных от узлов, отличных от узла 120. Величина времени, когда канал является недоступным вследствие индикации занятости ОЗК и времени молчания (t), представляет собой нагрузку по трафику (t). Нагрузка по трафику (t) на любом узле в ячеистой сети 100 может быть представлена уравнением:
t
=t
+t
load
busy
qnav
20
20
20
20
17
17
19
19
21
21
22
22
Фиг.3 представляет собой схему части ячеистой сети 100 по фиг.1, изображающую информацию о потоке трафика для примерного узла 120 и каждого из узлов 117, 119, 121 и 122 в окружении примерного узла 120. В одном варианте осуществления соседние узлы могут определяться как узлы в пределах одной линии связи узла. Соседними узлами узла 120 являются узлы 117, 119, 121 и 122. Таким образом, фиг.3 изображает узлы, необходимые для определения Т и R, частей времени во время ОЗК, которые тратятся на передачу или прием для узла 120 и каждого из его соседних узлов 117, 119, 121 и 122. В одном варианте осуществления каждый узел может передавать Т и R как часть радиомаяка узла. Каждый узел также может контролировать радиомаяки других узлов для приема информации о нагрузке по трафику от соседних узлов. Например, узел 120 может передавать свою пару Т и R, Т и R. Т и R могут контролироваться соседними узлами для узла 120. Соседние узлы 117, 119, 121 и 122 также могут передавать свои соответствующие пары Т и R, Т и R, Т и R, Т и R и Т и R на другие узлы, так что другие узлы могут контролировать эти параметры.
Каждый узел посредством контролирования радиомаяков соседних узлов может определять нагрузку по трафику локального ПТ и, следовательно, доступную пропускную способность. Нагрузка по трафику локального ПТ в окружении узла может определяться посредством формирования пары матриц передачи и приема Тх и Rx. Строки и столбцы пары Тх и Rx могут соответствовать параметрам передачи и приема узлов в ячеистой сети 100. Тх и Rx затем могут заполняться информацией из индивидуальных пар Т и R, принятых от каждого соседнего узла. Т, R, Тх и Rx каждый может представлять значение, вектор или матрицу.
17
17
19
19
21
21
22
22
20
20
20
20
20
17
16
20
21
22
Например, узел 120 может контролировать (отслеживать) радиомаяк каждого соседнего узла. Узел 120 может принимать пару Т и R от узла 117, пару Т и R от узла 119, пару Т и R от узла 121 и пару Т и R от узла 122. Узел 120 может проводить синтаксический анализ принятых пар Т и R для заполнения своих матриц Тх и Rx. Каждая строка и столбец Тх и Rx может соответствовать, по меньшей мере частично, узлу ячеистой сети 100. Например, строка 17, столбец 16 Тх может заполняться величиной времени, которая тратится на передачу ПТ от узла 117 на узел 116. Эта временная информация также может быть доступна в векторе Т передачи узла 117 и векторе R приема узла 116. Аналогично, строка 21, столбец 22 Rx может заполняться величиной времени, которая тратится на прием узлом 121 ПТ от узла 122. Эта временная информация также может быть доступна в векторе R приема узла 121 и векторе Т передачи узла 122.
20
20
20
20
20
20
20
20
20
20
Нагрузка по трафику вокруг узла 120 может определяться из Тх и Rx посредством суммирования максимальных значений для каждой пары передачи и приема Тх и Rx. Например, строка 21, столбец 22 Тх, которые представляют величину времени, которая тратится на передачу ПТ от узла 121 на узел 122, может сравниваться со строкой 22, столбцом 21 Rx, которые представляют величину времени, которая тратится на прием узлом 122 ПТ от узла 121. Максимальное значение каждой пары передачи и приема Тх и Rx может представлять величину недоступного времени для новых ПТ на узле 120, так как среда передачи недоступна. Например, максимальное значение строки 21, столбца 22 может представлять величину времени, в течение которого среда передачи недоступна для узла 120, так как ПТ передаются между узлом 121 и узлом 122. Сумма максимальных значений пар Тх и Rx может использоваться, по меньшей мере частично, для определения нагрузки по локальному трафику на узле 120. Нагрузка по трафику на любом узле в ячеистой сети 11 может определяться, по меньшей мере частично, посредством использования уравнения
Нагрузка по трафику затем может использоваться узлом 120 для определения, имеется ли соответствующая пропускная способность канала, доступная вокруг узла 120 для допуска новых ПТ. Узел 120 может гарантировать, что новые ПТ могут быть размещены без создания помех другим ПТ, передающимся и принимаемым на узле 120 или соседних узлах. Когда узел 120 принимает запрос на допуск ПТ, узел 120 может сравнивать запрос на допуск с нагрузкой по трафику на узле 120 и определять, способен ли он принять ПТ и передать ПТ на следующий узел по маршруту без оказания помех другим ПТ на узле 120 или около него. Если узел 120 может разместить новый ПТ, узел 120 может допустить ПТ. Если узел 120 не может разместить новый ПТ, узел 120 может отклонить ПТ. Предыдущий узел тогда может вызвать алгоритм маршрутизации для определения следующего наиболее подходящего маршрута и/или другой подходящий маршрут на узел назначения, фактически обходя узел 120.
S
S
S
S
S
S
S
S
20
17
19
21
22
20
Фиг.4 представляет собой схему части ячеистой сети 100 по фиг.1, изображающую информацию о потоке трафика для примерного узла 120 и каждого из узлов 117, 119, 121 и 122 в окружении примерного узла 120. Также показаны соседние узлы узлов 117, 119, 121 и 122. Узел 120 может передавать суммарный вектор  на каждый соседний узел. Каждый соседний узел также может передавать свои соответствующие суммарные векторы , причем узел 117 передает , узел 119 передает , узел 121 передает  и узел 122 передает . Каждый элемент  может содержать общее время передачи и приема на узел и от него на каждый из его соседних узлов. В одном варианте осуществления вектор  узла 120 может включать в себя четыре элемента, причем каждый элемент представляет сумму времени передачи и приема узла 120 для каждого из соседних узлов узла 120. Первым элементом может быть сумма времени передачи и приема узла 117, вторым элементом может быть сумма времени передачи и приема узла 119, третьим элементом может быть сумма времени передачи и приема узла 121 и четвертым элементом может быть сумма времени передачи и приема узла 122.
S
S
Одним преимуществом передачи  вместо Тх и Rx может быть то, что  может быть меньшей по размеру, примерно половина размера Тх и Rx в одном варианте осуществления. Это может уменьшить время и пропускную способность, требуемые для передачи информации о нагрузке по трафику. Служебные сигналы могут быть значительными, особенно для загруженных узлов с высокой степенью сетевого графа (т.е. узлов, имеющих много соседей).
S
ST
ST
ST
S
S
ST
S
ST
ST
21
21
Узел 120 может контролировать передачи соседних узлов узла 120 и хранить векторы  каждого соседнего узла. Нагрузка по трафику для узла 120 может определяться посредством построения матрицы  нагрузки, причем каждая строка и столбец представляют ячеистые узлы в ячеистой сети 100. Матрица  нагрузки может заполняться суммой времени передачи и приема для каждого из соседних узлов узла 120. В одном варианте осуществления строка 21 матрицы  нагрузки может заполняться элементами , представляющими вектор  от узла 121. Строка 21, столбец 22 матрицы  нагрузки может заполняться элементом , соответствующим сумме времени передачи и приема узла 121 от узла 122 на него. Нагрузка по трафику вокруг узла 120 тогда может определяться, по меньшей мере частично, посредством сравнения пар строк и столбцов передачи и приема и выбора значения относительного максимума. Например, строка 21, столбец 22  может сравниваться со строкой 22, столбцом 21 , и значение относительного максимума может использоваться для определения нагрузки. Сумма всех сравнений пар строк и столбцов тогда может использоваться, по меньшей мере частично, для определения нагрузки по трафику вокруг узла 120. Нагрузка по трафику вокруг любого узла в ячеистой сети 100 может определяться, по меньшей мере частично, по уравнению:
Информация о вычисленной нагрузке по трафику может использоваться узлом 120 для определения, могут ли быть допущены новые ПТ. Когда узел 120 принимает запрос на допуск ПТ, узел 120 может сравнивать запрос на допуск с нагрузкой по трафику и определять, способен ли узел 120 принять ПТ и может ли направить ПТ на следующий узел по маршруту без создания помех другим ПТ на узле 120 или других узлах в окружении. Если узел 120 имеет возможность принять и направить ПТ, узел 120 может допустить ПТ. Если узел 120 не имеет возможности принять и направить ПТ, узел 120 может отклонить ПТ, и предыдущий узел может вызвать алгоритмы маршрутизации для обхода узла 120. Поэтому в одном варианте осуществления узел ячеистой сети 100 может измерять или вычислять нагрузку по трафику в своем окружении и использовать информацию о нагрузке по трафику для выполнения управления допуском.
Фиг.5 представляет собой схему части ячеистой сети 100 по фиг.1, изображающую информацию о потоке трафика для примерного узла 120 и каждого из узлов 117, 119, 121 и 122 в окружении примерного узла согласно варианту осуществления. Нагрузки по трафику вокруг каждого узла ячеистой сети 100 могут определяться посредством измерения и контролирования соседних узлов в отношении скалярного параметра. Соседние узлы узлов 117, 119, 121 и 122 также показаны на фиг.5. В одном варианте осуществления каждый узел может рассылать широковещательным образом параметр, такой как время занятости. Каждый из узлов может измерять время занятости канала, как определяется его соответствующим физическим уровнем. Время занятости канала тогда может рассылаться широковещательным образом каждому узлу.
20
20
17
19
21
22
qnav
1
2
3
4
qnav
Узел 120 может контролировать свой физический уровень в отношении индикаций занятости по одному или нескольким интервалам радиомаяка. Величина времени Т, которой физический уровень узла 120 сообщает, что канал занят Т, может рассылаться широковещательным образом. Аналогично, соседние узлы узла 120 могут контролировать свои физические уровни для определения величины времени, которой их соответствующий физический уровень указывает, что канал занят. Соседние узлы также могут рассылать широковещательным образом свои измеренные времена занятости. Т может использоваться его соседними узлами 117, 119, 121 и 122. Узел 120 может принимать Т, Т, Т и Т от соответствующих соседних узлов. Узел 120 также может контролировать среднее время молчания вектора (t) доступа к сети. Узел 120 тогда может вычислить нагрузку по трафику вокруг узла 120, по меньшей мере частично, посредством суммирования Т, Т, Т и Т и времени t. Нагрузка по трафику на любом узле в ячеистой сети 100 может быть вычислена, по меньшей мере частично, используя уравнение:
Нагрузка по трафику тогда может использоваться узлом 120 для определения возможности допуска новых ПТ. Узел 120 может гарантировать, что новые ПТ не создадут препятствий для ПТ, в данный момент передающихся и принимаемых на узлах в окружении. Когда узел 120 принимает запрос на допуск ПТ, узел 120 может сравнивать запрос на допуск с нагрузкой по трафику и может определить, имеет ли узел 120 возможность принять ПТ и направить ПТ на следующий узел без создания препятствий другим ПТ. Если определяется, что узел 120 может допустить новый ПТ, узел 120 может допустить ПТ. Если определяется, что узел 120 не может допустить новый ПТ, узел 120 может отклонить ПТ, и предыдущий узел может вызвать алгоритмы маршрутизации для обхода узла 120.
D
Фиг.6 представляет собой схему протекания ПТ, иллюстрирующую управление допуском ПТ на первом узле 116 по потенциальному маршруту ПТ согласно варианту осуществления. В одном варианте осуществления станция Мо источника, узел 108 могут использовать алгоритмы маршрутизации для определения возможных маршрутов на станцию М назначения, узел 113. Узел 108 может оценивать или определять нагрузку на трафик (904) согласно одному из способов, описанных выше. Узел 108 может выбрать соответствующий маршрут, который может быть характерным для приложения. Например, маршрут может выбираться на основе расстояния до следующего скачка, нагрузки по трафику на следующем узле скачка, степени следующего узла скачка и/или других критериев, и/или их комбинаций.
1
В одном варианте осуществления может вычисляться среднее количество пакетов блока служебных данных управления доступом к среде (УДС) (БСДУ), подлежащих пересылке во время планируемого интервала обслуживания (ПИО) H. Среднее количество пакетов (N) может представлять собой произведение гарантированной скорости передачи данных (G) и ПИО (SSI), деленное на номинальный размер пакета (L). Среднее количество пакетов может вычисляться, по меньшей мере частично, посредством использования уравнения:
1
TXOP
1
1
Также может вычисляться нисходящая ТХОР, часть времени, запланированная на ПИО для передачи данных, необходимых для H. В данном случае, изобретатели обозначают период времени t сокращенным обозначением ТХОР. Вычисление может зависеть, по меньшей мере частично, от существующего трафика по Н. Если существующий трафик включает в себя ПТ того же класса, что и Мо, и не требует более короткого ПИО, тогда пакеты данных из Мо могут объединяться с существующим ПТ без необходимости в дополнительных служебных данных. В одном варианте осуществления ТХОР для Н может представлять собой максимум из наибольшего допустимого БСДУ (2304 байта), деленного на скорость физической передачи (R), и произведения среднего количества пакетов данных (N) и номинального размера пакета, деленные на скорость физической передачи. ТХОР может быть вычислено, основываясь, по меньшей мере частично, на уравнении:
Если нет существующего ПТ между узлом 108 и узлом 116 одного и того же класса, или если новый поток данных требует меньший ПИО, ТХОР может включать в себя дополнительные служебные данные для обработки дополнительного класса или меньшего ПИО. Меньший ПИО означает увеличенные служебные данные на бит данных. Поэтому желательно выбирать пути с меньшим количеством скачков. Это может повысить эффективность, а также улучшить комплексные транспортные возможности сети. В данном случае, ТХОР может определяться, по меньшей мере частично, по уравнению:
1
1,
1
Общая прогнозируемая нагрузка по нисходящему трафику на узле 108 может вычисляться, по меньшей мере частично, посредством суммирования ТХОР для Н и деления на ПИО для Н и суммирования ТХОР всех других ПТ, планируемых для передачи, деленных на их соответствующий ПИО. Нагрузка по трафику вследствие Н может суммироваться с другими существующими нагрузками по трафику вследствие ПТ, отходящих от узла 108. Нагрузка по нисходящему трафику может представляться, по меньшей мере частично, уравнением:
Нагрузка по восходящему трафику на узле 108 может оставаться неизменной. Вычисления восходящего потока для узлов неисточника описываются ниже в данном документе.
Узел 108 может сравнивать сумму нагрузок по восходящему трафику и нагрузок по нисходящему трафику с предварительно определенным порогом нагрузки для определения, может ли быть размещено Мо. Если определяется, что Мо может быть размещено, узел 108 может резервировать ТХОР, обновить информацию о нагрузке в сигнале радиомаяка и послать запрос на допуск на узел 116. В противном случае допуск может быть отклонен.
В одном варианте осуществления вычисления ТХОР и пороги могут быть разделены по КО. Например, узел может выделять 30% своего трафика на КО типа речь по протоколу Интернета (ПИ) (РППИ), 10% КО типа интерактивных игр в реальном времени и 60% КО типа просмотра веб-страниц. Определения нагрузки по трафику и сравнение порогов тогда могут быть характерными для КО. Динамическое выделение КО также может выполняться, если нет достаточной пропускной способности для поддержки потока данных. Узел может повторно выделить часть пропускной способности, выделенной для другого КО, для нового потока данных.
Узел 108 может сохранять резервирование ТХОР до тех пор, пока он не примет отказ в допуске от нисходящего узла. При приеме отказа в допуске станция источника может аннулировать резервирование ТХОР и может вызвать алгоритмы маршрутизации для определения альтернативных маршрутов на станцию 113 назначения. Если найден соответствующий маршрут, узел 108 может повторно запустить процесс допуска, описанный выше.
i
i
i-1
Фиг.7 изображает примерный скачок H ПТ, Мо по потенциальному маршруту ПТ согласно варианту осуществления. Если узел 120 принимает запрос на допуск от узла 117, узел 120 может вычислить восходящую (четвертый скачок) и нисходящую (третий скачок) ТХОР и прогнозируемую нагрузку по трафику. Для простоты и общности при описании управления допуском на узле 120 восходящий скачок может описываться как H, и нисходящий скачок как H. Управление допуском для узла 120 может применяться к любому узлу или скачку любого ПТ в ячеистой сети 100.
i
В одном варианте осуществления может вычисляться среднее количество пакетов БСДУ, подлежащих пересылке во время ПИО для H. Среднее количество пакетов (N) может представлять собой произведение гарантированной скорости передачи данных (G) и ПИО, деленных на номинальный размер пакета (L). Среднее количество пакетов может описываться, по меньшей мере частично, уравнением:
i
i
i
max
Также может вычисляться нисходящая ТХОР для H. Вычисление может зависеть, по меньшей мере частично, от существующего трафика по H. Если существующий трафик включает в себя ПТ того же класса, что и Мо, и не требует меньшего ПИО, тогда пакеты данных из М могут объединяться с существующим ПТ без необходимости в дополнительных служебных данных. ТХОР для H может представлять собой максимум относительно наибольшего допустимого БСДУ (2304 байта) (L), деленного на скорость физической передачи (R), и произведения среднего количества пакетов данных (N) и номинального размера пакета, деленные на скорость физической передачи. ТХОР может описываться, по меньшей мере частично, уравнением:
ТХОР может включать в себя дополнительные служебные данные для обработки дополнительного класса или меньшего ПИО. В данной ситуации ТХОР может описываться, по меньшей мере частично, уравнением:
i
i
i
Общая прогнозируемая нагрузка по нисходящему трафику на узле 120 может вычисляться, по меньшей мере частично, посредством суммирования ТХОР для H и деления на ПИО для H и суммирования ТХОР всех других потоков трафика, планируемых к отправлению от узла 120, деленных на их соответствующий ПИО. Конкретно, нагрузка по трафику вследствие H суммируется с другими существующими нагрузками по трафику вследствие ПТ, отходящих от узла 120 для каждого соседнего узла k, узла 117, узла 119, узла 121 и узла 122. Нагрузка по нисходящему трафику может описываться, по меньшей мере частично, уравнением:
i-1
i-1
i-1
Узел 120 также может вычислять восходящую ТХОР для H. Вычисление может зависеть, по меньшей мере частично, от существующего трафика по линии связи H. Если существующий трафик включает в себя ПТ того же класса, что и Мо, и не требует меньшего ПИО, тогда пакеты данных из Мо могут объединяться с существующим ПТ без необходимости в дополнительных служебных данных. ТХОР для H может представлять собой максимум наибольшего допустимого БСДУ (2304 байта), деленного на скорость физической передачи (R), и произведения среднего количества пакетов данных (N) и номинального размера пакета, деленные на скорость физической передачи. ТХОР может описываться, по меньшей мере частично, уравнением:
Если ТХОР включает в себя дополнительные служебные данные для обработки дополнительного класса или меньшего ПИО, ТХОР может описываться, по меньшей мере частично, уравнением:
i-1
i-1
i
Общая прогнозируемая нагрузка по восходящему трафику на узле 120 может вычисляться посредством суммирования ТХОР для H, и деления на ПИО для H и суммирования восходящей ТХОР всех других потоков трафика, планируемых к поступлению на узле 120, деленной на их соответствующий ПИО. Нагрузка по трафику вследствие H может суммироваться с другими существующими нагрузками по трафику вследствие ПТ, поступающего на узел 120 от каждого из его соседних узлов k, узла 117, узла 119, узла 121 и узла 122. Нагрузка по восходящему трафику может описываться, по меньшей мере частично, уравнением:
Узел 120 после выполнения вышеупомянутых вычислений может сравнивать сумму нагрузок по восходящему трафику и нагрузок по нисходящему трафику с предварительно определенным порогом нагрузки, чтобы, по меньшей мере частично, определить, может ли быть размещен Мо. Если определяется, что Мо может быть размещен, узел 120 может резервировать ТХОР, обновить информацию о нагрузке в своем радиомаяке и послать запрос на допуск на узел 119. Если определяется, что Мо не может быть размещен, допуск может быть отклонен, и узел 120 может послать сообщение узлу 117, отклоняющее допуск ПТ Мо.
В одном варианте осуществления вычисления ТХОР и пороги доступа могут разделяться по КО. Определения нагрузки по трафику и сравнения порогов могут быть характерными для КО.
D
D
i
Фиг.8 изображает конечный скачок H на станцию назначения, узел 113. Управление допуском на узле 113 для H может быть таким же, что и скачок H, за исключением того, что могут быть опущены вычисления нисходящей ТХОР. Также может быть опущено распространение запроса на допуск на следующую станцию скачка.
Каждый из узлов по маршруту М может сохранять соответствующее резервирование ТХОР до тех пор, пока он не примет отклонение допуска от нисходящего узла. При приеме отклонения допуска станция источника может аннулировать резервирование ТХОР и может вызвать алгоритмы маршрутизации для определения альтернативных маршрутов на станцию назначения, узел 113. Может снова вызываться процесс допуска для каждого узла по маршруту.
Ячеистая сеть 100 или любой из узлов могут разделять допуск по требованиям КО. Одним способом управления допуском по КО может быть разделение классов ПТ на многочисленные классы, например класс с высоким приоритетом и класс с низким приоритетом. ПТ класса с высоким приоритетом может обслуживаться в пределах одного ПИО на каждом узле по маршруту. Задержка наихудшего случая может быть вычислена посредством умножения количества скачков на ПИО. Например, в приложении передачи речи может допускаться время задержки не более примерно 50 миллисекунд. Таким образом, поток с высоким приоритетом может маршрутизироваться на расстояние до пяти узлов с примерно 10-мс ПИО.
Фиг.9 представляет собой блок-схему последовательности операций, иллюстрирующую способ управления допуском ПТ на примерном узле по потенциальному маршруту ПТ согласно варианту осуществления. Узел может принимать запрос на допуск ПТ (902). Запрос на допуск ПТ может передаваться от другого узла, или запрос на допуск может быть для ПТ, исходящего от самого узла. Узел может определить нагрузку по трафику в окружении узла (904). Узел может определить нагрузку по трафику, по меньшей мере частично, посредством измерения нагрузки на узле или посредством определения нагрузки из информации, переданной соседними узлами узла. Вычисления и измерения нагрузки по трафику могут выполняться различными способами, включая, но не ограничиваясь ими, способы и/или эквиваленты, описанные в данном документе. Нагрузка по трафику может определяться при помощи измерений на самом узле, объединенных с измерениями, переданными от соседей узлов для узлов. Примерное гибридное вычисление нагрузки по трафику также описывается выше, которое также может использоваться для определения нагрузок по трафику.
Узел может определять ТХОР (906). Если узел является узлом источника, может вычисляться нисходящая ТХОР. Если узел является узлом назначения, может вычисляться восходящая ТХОР. Если узел является промежуточным узлом, могут вычисляться восходящая и нисходящая ТХОР. Узел может сравнивать ТХОР с доступной ТХОР (908). Если определяется, что нет соответствующей доступной ТХОР, узел тогда может уведомить запрашивающий узел, что допуск ПТ был отклонен (910). Если определяется, что имеется доступная ТХОР, узел может резервировать ТХОР (912) и может посылать запрос на допуск ПТ на следующий узел (914).
Фиг.10 представляет собой блок-схему, иллюстрирующую примерные компоненты для устройства и средства для устройства для управления допуском согласно варианту осуществления. Устройство 1000 может включать в себя модуль 1002 для обработки запросов на допуск, сконфигурированный на обработку запроса на допуск ПТ, модуль 1004 для определения нагрузок по трафику, сконфигурированный на определение нагрузки по трафику узла, модуль 1006 для определения ТХОР, сконфигурированной на определение восходящей ТХОР и/или нисходящей ТХОР, и модуль 1008 для резервирования ТХОР, сконфигурированный для резервирования восходящей ТХОР и/или нисходящей ТХОР.
Специалисты в данной области также понимают, что различные иллюстративные логические блоки, модули, схемы и алгоритмы, описанные в связи с вариантами осуществления, описанными в данном документе, могут быть реализованы в виде электронных аппаратных средств, компьютерных программных средств или их комбинации. Чтобы проиллюстрировать эту взаимозаменяемость аппаратных и программных средств, различные иллюстративные компоненты, блоки, модули, схемы и алгоритмы были описаны выше, в основном, на языке их функциональных возможностей. Реализуется ли такая функциональная возможность в виде аппаратных или программных средств зависит от конкретного применения и конструктивных ограничений, накладываемых на всю систему. Квалифицированный специалист может реализовать описанную функциональную возможность различными путями для каждого конкретного применения, но такие решения по реализации не должны интерпретироваться как вызывающие отступление от объема настоящего описания.
Различные иллюстративные логические блоки, модули и схемы, описанные в связи с вариантами осуществления, описанными в данном документе, могут быть реализованы или выполнены при помощи устройства обработки общего назначения, устройства цифровой обработки сигналов (УЦОС), специализированной интегральной схемы (специализированной ИС), программируемой пользователем вентильной матрицы (ППВМ) или другого программируемого логического устройства, дискретного вентиля или транзисторной логики, дискретных аппаратных компонентов или любой их комбинации, предназначенной для выполнения функций, описанных в данном документе. Устройством обработки общего назначения может быть микропроцессорное устройство, но в альтернативе, устройством обработки может быть любое обычное устройство обработки, устройство обработки, микропроцессорное устройство или конечный автомат. Устройство обработки также может быть реализовано в виде комбинации вычислительных устройств, например комбинации УЦОС и микропроцессорного устройства, множества микропроцессорных устройств, одного или нескольких микропроцессорных устройств вместе с ядром УЦОС, или любой другой такой конфигурации.
Устройство, способы или алгоритмы, описанные в связи с вариантами осуществления, описанными в данном документе, могут осуществляться непосредственно аппаратными средствами, программными средствами или их комбинацией. С программными средствами способы или алгоритмы могут осуществляться в одной или нескольких инструкциях, хранимых на считываемом компьютером носителе, который составляет часть продукта компьютерной программы, который может считываться и/или исполняться устройством обработки. Инструкции могут постоянно находиться в памяти оперативного запоминающего устройства (ОЗУ), флэш-памяти, памяти постоянного запоминающего устройства (ПЗУ), памяти электрически программируемого ПЗУ (ЭППЗУ), памяти электрически стираемого программируемого ПЗУ (ЭСППЗУ), регистрах, на жестком диске, съемном диске, компакт-диске или на любом другом виде запоминающей среды, известной в технике. Примерная запоминающая среда соединяется с устройством обработки, так что устройство обработки может считывать информацию с запоминающей среды и записывать информацию на нее. Альтернативно, запоминающая среда может быть выполнена за одно целое с устройством обработки. Устройство обработки и запоминающая среда могут постоянно находиться в специализированной ИС. Специализированная ИС может постоянно находиться в терминале пользователя. Альтернативно, устройство обработки и запоминающая среда могут постоянно находиться в качестве дискретных компонентов в терминале пользователя.
Устройство, способы или алгоритмы, описанные в связи с вариантами осуществления, описанными в данном документе, могут осуществляться непосредственно аппаратными средствами, программными средствами или их комбинацией. С программными средствами способы или алгоритмы могут осуществляться в одной или нескольких инструкциях, которые могут выполняться устройством обработки. Инструкции могут постоянно находиться в памяти ОЗУ, флэш-памяти, памяти ПЗУ, памяти ЭППЗУ, памяти ЭСППЗУ, регистрах, на жестком диске, съемном диске, компакт-диске или на любом другом виде запоминающей среды, известной в технике. Примерная запоминающая среда соединяется с устройством обработки, так что устройство обработки может считывать информацию с запоминающей среды и записывать информацию на нее. Альтернативно, запоминающая среда может быть выполнена за одно целое с устройством обработки. Устройство обработки и запоминающая среда могут постоянно находиться в специализированной ИС. Специализированная ИС может постоянно находиться в терминале пользователя. Альтернативно, устройство обработки и запоминающая среда могут постоянно находиться в качестве дискретных компонентов в терминале пользователя.
Предшествующее описание раскрытых вариантов осуществления предусматривается для того, чтобы предоставить возможность любому специалисту в данной области техники выполнить или использовать настоящее описание. Различные модификации этих вариантов осуществления легко очевидны для специалиста в данной области техники, и общие принципы, определенные в данном документе, могут быть применены в других вариантах осуществления без отступления от сущности или объема описания. Таким образом, как предполагается, настоящее описание не ограничивается вариантами осуществления, показанными в данном документе, но должно согласовываться с наибольшим объемом, совместимым с принципами и новыми признаками, описанными в данном документе.
Описание может осуществляться в других характерных формах без отступления от его сущности или существенных характеристик. Описанные варианты осуществления должны рассматриваться во всех отношениях только как иллюстративные и не ограничивающие, и объем описания, поэтому, определяется прилагаемой формулой изобретения, а не вышеприведенным описанием. Все изменения, которые подпадают под значение и область эквивалентности формулы изобретения, должны быть включены в их объем.