ОБЛАСТЬ ТЕХНИКИ Настоящее изобретение относится к способу управления ресурсами в Wi-Fi сети передачи данных.

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

В наши дни беспроводные локальные сети имеют очень широкое распространение и различные области применения. Это домашние сети, публичные сети: кафе, парки, транспортные системы, отели, торговые центры; корпоративные сети: офисные здания, бизнес парки, учебные заведения. Наиболее распространенный с пользовательской точкой зрения тип беспроводных сетей— WLAN, имеет ряд неоспоримых достоинств по сравнению с проводными локальными сетями, такие как мобильность и масштабируемость. С течением времени, некоторые недостатки беспроводных сетей постепенно уменьшаются. Так уже сейчас появляются сети с пропускной способностью в 1 Гб/с и даже 6.9 Гб/с. Несмотря на это, всегда существуют проблемы связанные физической основой технологии Wi- Fi. Это высокая вероятность возникновения коллизий, проблемы шумов и уязвимость. Современные беспроводные сети, которые рассматриваются в этой работе, работают в соответствии со стандартом IEEE 802.11 в частотных диапазонах 2.4 ГГц и 5 ГГц. Стандарт определяет ограниченный набор широкополосных пересекающихся каналов в этих диапазонах.

Повсеместно в данных типах сетей существуют проблемы, связанные с коллизиями и шумами. Источником коллизий как в Wi-Fi сетях, так и в любых других, являются работающие на одном канале связи передатчики.

1

ЗАМЕНЯЮЩИЙ ЛИСТ (ПРАВИЛО 26) Источником шумов в беспроводных сетях являются в основном другие радио устройства, работающие в радиочастотных диапазонах Wi-Fi, такие как Bluetooth и микроволновые печи или природные электромагнитные поля среды. Несмотря на то что стандарты определяют механизмы избежания коллизий и учета шумов, снижение пропускной способности сети неизбежны при их возникновении. Эти проблемы становятся особенно остро ощутимыми, когда в одной области работает большое количество сетей. Общая производительность этих сетей сильно падает в следствии большого числа коллизий и шумов. Задача оптимального управления и распределения ресурсов сети, а именно - частотно-мощностных параметров беспроводных сетей состоит в распределении радио ресурсов таким образом, чтобы вероятность возникновения коллизий и влияние шумов была минимальной, а, в следствие, увеличилась общая пропускная способность управляемых сетей. Из уровня техники известен способ динамического распределения каналов точек доступа Wi-Fi сети для управления интерферирующими точками доступа (US 20140036816 А1, 06.02.2014, Accelera Mobile Broadband, Inc.), в котором предлагается использовать построение графа конфликтов, вершинами которого являются точки доступа в сети, а гранями - пара точек доступа. На основании графа распределяются весовые показатели для различных ребер графа и выбираются возможные варианты распределения ресурсов за счет переназначения каналов на точках доступа и мощностных параметров.

Недостатком известного способа является слабое увеличение пропускной способности сети.

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

ЗАМЕНЯЮЩИЙ ЛИСТ (ПРАВИЛО 26) Задачей настоящего изобретения является создание способа распределения ресурсов в WI-FI сети, при котором происходит снижение ее общей интерференции.

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

Заявленный технический результат достигается за счет того, что способ распределения ресурсов в Wi-Fi сетях содержит этапы на которых:

- осуществляют сканирование радиоэфира, по меньшей мере, одной точкой доступа; - определяют точки доступа в радиоэфире;

- моделируют граф, в котором вершины представляют собой упомянутые точки доступа, а ребра графа образованы парами точек доступа Vj и Vj, с уровнем сигнала выше 0 по отношению друг к другу;

- определяют значение весовой функции W(vi, vj) для каждой пары точек доступа ребра графа;

- определяют целевую функцию F графа;

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

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

з

ЗАМЕНЯЮЩИЙ ЛИСТ (ПРАВИЛО 26) и/или количество пользователей, подключенных к каждой из точек доступа, формирующих ребро.

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

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

В частном варианте осуществления изобретения определяют коэффициент I интерференции между каналами Cj и Cj точек Vj и Vj.

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

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

В частном варианте осуществления изобретения перераспределением ресурсов сети является распределение каналов и мощностей для точек доступа.

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

Фиг. 1 иллюстрирует схему выполнения этапов заявленного способа.

Фиг. 2 иллюстрирует пример частного варианта распределения точек доступа в Wi-Fi сети.

Фиг. 3 иллюстрирует граф Wi-Fi сети. ОСУЩЕСТВЛЕНИЕ ИЗОБРЕТЕНИЯ

ЗАМЕНЯЮЩИЙ ЛИСТ (ПРАВИЛО 26) Здесь и далее будут расписаны термины и определения, используемые в настоящей заявке.

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

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

Станция - логическая сущность, которая по отдельности обеспечивает адресацию по требованию уровню управления доступом к среде (MAC) и интерфейсу физического уровня (PHY) к беспроводной среде.

В стандарте ШЕЕ 802.11 адресуемой единицей является станция (STA). Одним из наиболее распространенных видов Wi-Fi сетей являются сети типа Infrastructure (инфраструктура). Этот вид сетей предполагает наличие основной станции, которая регулирует параметры сети и предоставляет другим станциям доступ к сети. Такая станция называется точкой доступа (АР), Другие станции называются клиентами.

Точка доступа задает все параметры сети: канал, на котором работает сеть, доступные скорости, имя сети, политики безопасности и шифрования, и т. д. Набор из одной точки доступа и множества клиентов, подключенных к ней называется основным сервисным множеством (BSS). Одну беспроводную сеть может обслуживать сразу несколько точек доступа для расширения области покрытия сети, тогда набор из такого множества точек доступа называется расширенным сервисным множеством (ESS). Исходя из сказанного выше, задача оптимального управления частотно-мощностными параметрами беспроводных сетей (Radio Resource Management, RRM) сводится к установке канала точки (точек) доступа, мощности ее передатчика

ЗАМЕНЯЮЩИЙ ЛИСТ (ПРАВИЛО 26) и политики приема клиентов в сеть так, чтобы достичь минимума вероятности возникновения шумов и коллизий в сети, при поддержании стабильного соединения с пользователями.

Набор каналов диапазона 5 ГГц, определенный стандартом ШЕЕ 802.11 более разрежен, чем в диапазоне 2.4 ГГц, то есть, зачастую, в диапазоне 5 ГГц ближайшими соседями канала п являются каналы (n-k) или (n+k), где к>2. Для России же всегда к>4, то есть в России все двенадцать каналов диапазона 5 ГГц ортогональны. Поэтому, от сюда и далее, примеры рассматриваются для задач в диапазоне 2.4 ГГц, так как аналогичные задачи для 5 ГГц сводятся к задачам диапазона 2.4 ГГц.

На Фиг. 1 представлены этапы заявленного способа 100 распределения ресурсов Wi-Fi сети.

На этапе 101 происходит сканирование радиоэфира, которое выполняется, по меньшей мере, одной точкой доступа 201-205, сети, представленной на Фиг. 2. Затем на этапе 102 происходит определение точек доступа 201-205, которые присутствуют в радиоэфире. Контроллер анализирует состояние радио-эфира на предмет слышимости соседних точек доступа, при этом сканирование радиоэфира и поиск различных Wi-Fi сетей (BSSID) каждой точкой доступа 201-205 может осуществляться в фоновом режиме. На этапе 103 выполняется моделирование графа 300, изображенного на Фиг. 3, а именно, взвешенного графа, где вершинами являются точки доступа 201- 205. Взвешенным графом 300 являются точки доступа 201-205, соединенные ребрами 210-215, если они «слышат» друг друга, т.е. с уровнем сигнала выше 0 по отношению друг к другу. На графе также могут отображаться точки доступа с 0 уровнем сигнала по отношению друг к другу, т.е. которые не «слышат» друг друга и не создают интерференции. Такие точки могут

ЗАМЕНЯЮЩИЙ ЛИСТ (ПРАВИЛО 26) учитываться при определении функции распределения ресурсов, но их параметры не будут меняться.

На этапе 104 определяют значение весовой функции W(v _b Vj) для каждой пары точек доступа 201-205 ребра графа. Пара вершин графа 300, являющихся точками доступа, например 201 и 202 образует ребро 214 графа 300 и указывает на то, что упомянутые точки доступа 201 и 202 «слышат» друг друга. Упомянутые точки доступа, образующие ребра, могут интерферировать друг с другом. Назначают обозначения Vj и Vj точкам доступа 201 и 202. Весовая функция W для графа 300 подбирается исходя из требуемых условий и может быть определена как функция от расстояния между точками доступа 201-205, уровнем их взаимной слышимости, количеством клиентов и т.п.

Определение (1) показывает частный случай весовой функции W. N,— количество клиентов на точке доступа Vj, a P(Vj,Vj)— уровень сигнала между точками Vi и Vj (201 и 202). Таким образом, определяют вес ребра графа, в данном случае, ребра 214. Эта процедура также выполняется для всех ребер 210-215 графа 300.

Точка доступа vi может периодически запрашивать от ее клиентов отчет, для формирования которого клиент проводит пассивное сканирование по всем каналам. В упомянутый отчет включаются точки доступа vj, пакеты от которых и к которым были услышаны клиентом. Таким образом, точка доступа vi получает информацию о точках доступа, которые слышны посредственно и напрямую ее клиентами. Подобная функциональность клиентов поддерживается расширением стандарта IEEE 802.1 lk.

7

ЗАМЕНЯЮЩИЙ ЛИСТ (ПРАВИЛО 26) Обозначим Mi — количество точек доступа, полученных в отчетах от клиентов точки vi, Mi(vj)— количество отчетов, содержащих точку vj. Весовая функция W будет иметь вид На этапе 105 определяется целевая функция F графа 300. Целевая функция F позволяет выявить уровень загруженности каналов точек доступа 201-205. Данный этап выполняется в две стадии. На первой стадии этапа 105 происходит эвристическое назначение частот. Создается счетчик к=0. Вычисляется начальное значение F ^k _sum , где примерный вид функции F

ei ev (3) где А - это функция распределения ресурсов в сети,

I - коэффициент интерференции каналов точек доступа.

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

Пусть каналы связаны некоторым отношением I: СхС—> [0; 1] (I-factor),

Т - Т( _с . _С _ | 1 - |Сг - С, | * С, / > 0

¹ - ^{1 с} ^ ^с з ⁾ - \ о, / < 0 где Cj, Cj каналы точек доступа Vj и Vj , С - множество каналов.

ЗАМЕНЯЮЩИЙ ЛИСТ (ПРАВИЛО 26) Каждому ребру 210-215 сопоставим величину I- value (значение интерференции), равную I(D(Vj), D(v _j )) * W(v Vj), где D - функция распределения каналов.

Функция распределения каналов указывает на канал, на котором должна работать та или иная точка доступа.

На этапе 105 каждая точка 201-205 в сети выбирает себе каким-либо образом (например, случайно) начальный канал. После этого на каждом последующем шаге точки пытаются «жадно» оптимизировать выбор канала, при котором функция F стремится к своему минимуму. Для точной работы алгоритма точки должны производить оптимизационный шаг, выполняемый асинхронно, поэтому каждый очередной шаг итерации производится точкой через случайный интервал в пределе от 10 до 100 минут.

Для каждой точки доступа определяем канал, который минимизирует интерференцию с соседними точками. Для каждой точки вычисляется значение S, например

S(vi) I(A( _Vi ), A( _Vjl )) * W(e,)

Последовательно для каждой точки Vj по порядку невозрастания этих значений:

1) находится канал, который минимизирует значение S(vj); 2) этот канал сохраняется для точки Vj.

Далее вычисляется значение F ^k _sum c помощью формулы (3) и если F ^k _sum = то значит было найдено выявлено минимальное значение целевой функции F. Если F _sum = F ^k _sum , то выполняется второй шаг этапа 105—

ЗАМЕНЯЮЩИЙ ЛИСТ (ПРАВИЛО 26) исчерпывающий поиск с отсечением. На втором шаге этапа 105 На этой стадии производится перебор всевозможных распределений, применимых к рассматриваемой сети. Подобный перебор имеет экспоненциальную сложность, однако, работа предыдущей стадии позволяет сразу отбрасывать (отсекать) заведомо не оптимальные решения. Рассмотрим дерево поиска, каждая вершина которого хранит значение и множество рассмотренных точек доступа 201-205. Корнем этого дерева является начальное состояние с пустым множеством рассмотренных точек и значением = 0. Каждый уровень дерева соответствует добавлению к множеству рассмотренных точек доступа новой, ранее не рассмотренной точки доступа. Листовая вершина означает отсечение, либо нахождение распределения которое лучше предыдущего.

Данный этап позволяет найти распределение, которое дает точный минимум целевой функции F. Использование отсечений уменьшает количество рассматриваемых вариантов на стадии перебора на столько, что время работы определения минимума уровня загруженности каналов становится вполне приемлемым даже при большом количестве входных данных. Таким образом, удается выстроить наиболее оптимальное распределение частот с учетом наличия неподконтрольных точек доступа. Эти точки так же участвуют в работе алгоритма, но их параметры не модифицируются. На этапе 106 определяют функцию распределения А для графа 300, при котором целевая функция F принимает минимальное значение. Распределение А отвечает не только за установку каналов на точках доступа 201-205, но и за настройку других параметров, таких как: мощность, перераспределение клиентов. Представим распределение А, как А=(А1, А2, ... , Ad), а целевую функцию, как F = F(W, А) = F(W, А1, А2, Ad). Обозначим Al(Vj)— канал точки Vj,

ю

ЗАМЕНЯЮЩИЙ ЛИСТ (ПРАВИЛО 26) A2(vi)— мощность ее передатчика, A3(Vj) — множество клиентов этой точки.

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

С учетом распределения мощностей на точках доступа, целевая функция F принимает вид

Psum ⁼ W(v _it , v _jt )P{v _k , v _jt )Ι(Α ₁ (v _it ), Α _λ (v _jt ))

ei E (6) Где P - функция, определяющая уровень сигнала,

1

P{v _h Vj ) = A _h oie{A ₂ {vi)) х khoie(A2{vj)) х {Α ₂ (νι) / Р _т ^г _ах + A ₂ (v _j )/P} _nax )

Δ ( )

Pi _j — средний нормированный уровень сигнала между точками Vj и Vj, при максимальной мощности их передатчиков,

Р тах— максимальная мощность передатчика точки v _i} Ртах— максимально возможный уровень сигнала в идеальных условиях. Первые два множителя в выражении (8) учитывают результат работы модуля устранения пробелов покрытия A _h0 i _e -

Последний множитель— нормированный уровень предполагаемой взаимной слышимости точек при данном распределении А. На этапе 107, после того как на этапе 106 была определена функция распределения А, при котором достигается минимальное значение целевой функции F для каналов точек доступа 201-205, происходит оценка

11

ЗАМЕНЯЮЩИЙ ЛИСТ (ПРАВИЛО 26) необходимости применения распределения на вершинах графа 300. Решение принимается в связи с тем, что изменение частотных и мощностных характеристик точки доступа является накладной операцией, которая влечет за собой временное снижение пропускной способности. Решение о применении распределения принимается в случае если повышение пропускной способности будет большим, чем накладные расходы. Назначение распределения А применяется для одной или более точек доступа.

На этапе 108 применяют назначенное распределение для точек доступа 201- 205, которым было назначена функция распределения А.

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

12

ЗАМЕНЯЮЩИЙ ЛИСТ (ПРАВИЛО 26)