СПОСОБ АДАПТИВНОГО РАСПРЕДЕЛЕНИЯ ЧАСТОТНО-ВРЕМЕННОГО РЕСУРСА
METHOD OF ADAPTIVE DISTRIBUTION OF BANDWIDTH-TIME RESOURCE

Изобретение относится к области радиотехники, в частности к способам передачи и приема радиосигнала с применением адаптивной антенной решетки, и может использоваться в сотовых системах связи.
Известен способ адаптивного распределения частотно-временного ресурса [1], включающий определение для каждого формируемого кадра прямого и обратного каналов для каждой абонентской станции требуемых значений энергетических параметров для различных видов кодирования и модуляции в зависимости от заданного качества, измерение значения энергетических параметров в текущем кадре прямого и обратного каналов, передачу на базовую станцию значения энергетических параметров, измеренных в прямом канале и назначение на базовой станции каждой абонентской станции вида кодирования и модуляции, а также участка частотно-временного ресурса в формируемых кадрах прямого и обратного каналов.
Недостатками известного способа являются недостаточно высокие пропускная способность радиоканала и эффективность использования частотно-временного ресурса.
N
Наиболее близким к предлагаемому является способ адаптивного распределения частотно-временного ресурса [2], заключающийся в том, что на базовой станции, включающей адаптивную антенную систему, для каждого формируемого кадра прямого и обратного каналов для каждой абонентской станции определяют требуемые значения энергетических параметров для различных видов кодирования и модуляции в зависимости от заданного качества, измеряют значения энергетических параметров в текущем кадре прямого и обратного каналов, для каждой абонентской станции определяют величину частотно-временного ресурса, необходимого для передачи требуемого объема данных в формируемом кадре прямого и обратного каналов, и назначают каждой абонентской станции вид модуляции и кодирования, а также величину частотно-временного ресурса, при этом для каждой абонентской станции определяют требуемые значения энергетических параметров для различных видов кодирования и модуляции в зависимости от заданного объема данных, прогнозируют величину энергетических параметров формируемого кадра прямого и обратного каналов по значениям мощностей передачи и измеренным энергетическим параметрам предыдущих кадров, определяют требуемые значения мощностей передачи для различных видов кодирования и модуляции в зависимости от требуемых значений и прогнозируемой величины энергетических параметров, исключают из дальнейшего рассмотрения виды кодирования и модуляции, для которых требуемое значение мощностей передачи недостижимо вследствие ограничений на диапазон регулировки мощности, для всех оставшихся видов кодирования и модуляции определяют величину частотно-временного ресурса, необходимого для передачи требуемого объема данных в формируемом кадре прямого и обратного каналов, суммируют необходимые величины частотно-временного ресурса  абонентских станций, соответствующие оставшимся видам кодирования и модуляции с максимальной скоростью передачи данных, и сравнивают полученную сумму с доступным частотно-временным ресурсом формируемого кадра, в случае непревышения назначают каждой абонентской станции вид модуляции и кодирования, а также соответствующие им мощность передачи и величину частотно-временного ресурса таким образом, чтобы минимизировать среднюю мощность формируемого кадра при условии передачи всех необходимых данных, в случае превышения величину частотно-временного ресурса распределяют между абонентскими станциями в соответствии с их приоритетом и назначают каждой абонентской станции вид модуляции и кодирования с максимальной скоростью передачи данных и соответствующую им мощность передачи.
Недостатками известного способа являются недостаточно высокие пропускная способность радиоканала и эффективность использования частотно-временного ресурса из-за того, что не учитываются пространственно-угловое распределение абонентских станций и возможности пространственно-угловой селекции сигналов в антенной системе базовой станции.
Технический результат заключается в повышении пропускной способности радиоканала и эффективности использования частотно-временного ресурса за счет использования метода графов для формирования расписания распределения частотно-временного ресурса, обладающего максимальной плотностью для наблюдаемого пространственно-углового распределения абонентских станций.
согласно изобретению
Требуемый технический результат достигается тем, что в способе адаптивного распределения частотно-временного ресурса, заключающемся в том, что на базовой станции, включающей адаптивную антенную систему, для каждого формируемого кадра прямого и обратного каналов для каждой абонентской станции определяют требуемые значения энергетических параметров для различных видов кодирования и модуляции в зависимости от заданного качества, измеряют значения энергетических параметров в текущем кадре прямого и обратного каналов, для каждой абонентской станции определяют величину частотно-временного ресурса, необходимого для передачи требуемого объема данных в формируемом кадре прямого и обратного каналов, и назначают каждой абонентской станции вид модуляции и кодирования, а также величину частотно-временного ресурса, , для каждой абонентской станции оценивают угловой параметр прихода сигнала обратного канала путем обработки в адаптивной антенной системе, для набора указанных угловых параметров на базовой станции формируют запрещающий граф, показывающий, для каких абонентских станций невозможно осуществить пространственную селекцию сигналов в адаптивной антенной системе с заданным качеством, для полученного запрещающего графа методом правильной раскраски вершин вырабатывают для кадра, следующего за формируемым, расписание распределения частотно-временного ресурса для прямого и обратного каналов с максимальной плотностью для наблюдаемого пространственно-углового распределения абонентских станций, после чего в служебную информацию управления, подготавливаемую для передачи в текущем кадре, вносят данные о назначаемом для формируемого кадра расписании распределения частотно-временного ресурса, далее генерируют в прямом канале групповые сигналы текущего кадра для каждого антенного элемента адаптивной антенной системы путем взвешенного суммирования сигналов, сформированных для каждой из абонентских станций, с весами, задаваемыми векторами весовой обработки, прописанными в расписании для прямого канала в частотно-временных позициях текущего кадра, а также на базовой станции выделяют парциальные абонентские сигналы текущего кадра путем весовой обработки сигналов выходов антенных элементов адаптивной антенной системы с использованием векторов весовой обработки, прописанных в расписании для обратного канала в частотно-временных позициях текущего кадра, после чего на базовой станции для каждого частотно-временного фрагмента формируемого кадра составляют список работающих абонентских станций, для каждой из них вычисляют вектор весовой обработки для прямого канала в формируемом кадре и вектор весовой обработки для обратного канала в формируемом кадре, и затем на базовой станции дополняют расписание распределения частотно-временного ресурса прямого и обратного каналов формируемого кадра позициями упомянутых векторов весовой обработки.
На фиг. 1 приведена структурная схема варианта реализации устройства, с помощью которого осуществляют заявляемый способ.
На фиг. 2 показана кадровая структура организации распределения временного ресурса и элементарных временных интервалов (ЭВИ).
На фиг. 3 показан пример организации пространственно-частотно-временного расписания.
N
На фиг. 4 приведен пример построения «запрещающего графа» на множестве из  абонентских станций (АС), обслуживаемых базовой станцией (БС), на первом этапе (без учета различий в запросах на ресурс радиоканала).
На фиг. 5 показан пример построения «запрещающего конуса» в направлении на заданного абонента, с помощью которого формируют ребра в «запрещающем графе».
На фиг. 6 приведен пример построения «запрещающего графа» на последнем этапе (внесение коррекций, связанных с учетом различных запросов на ресурс радиоканала)
На фиг. 7(а-г) показан пошаговый пример работы алгоритма правильной «раскраски узлов» «запрещающего графа», построенного на базе операции «стягивания» узлов.
На фиг. 8 приведен конечный результат, полученный алгоритмом правильной «раскраски узлов» «запрещающего графа» для примера, показанного на фиг. 6.
На фиг. 9 показано оптимальное расписание распределения частотно-временного ресурса, составленное в соответствии с полученным решением задачи «раскраски узлов» «запрещающего графа».
N
Рассмотрим реализацию предлагаемого способа на примере передачи данных в прямом канале с базовой станции на одну из  абонентских станций и в обратном канале с абонентской станции на базовую станцию.
Базовая станция 1 содержит адаптивную антенную систему 2, первый блок 3 кодирования и модуляции, блок 5 адаптации, блок 6 оценки направлений, блок 7 пространственно-частотно-временного расписания и первый блок 4 демодуляции и декодирования, первый выход которого соединен с соответствующим управляющим входом блока 5 адаптации, информационный вход соединен с соответствующим выходом адаптивной антенной системы 2 и с соответствующим входом блока 6 оценки направлений, управляющий вход соединен с соответствующим первым выходом блока 5 адаптации, а с информационного выхода сигнал подается на высшие уровни базовой станции. Групповой вход блока 6 оценки направлений подключен к соответствующим выходам антенных элементов, входящих в состав адаптивной антенной системы 2, выход блока 6 оценки направлений подключен ко входу блока 7 пространственно-частотно-временного расписания, групповой выход которого соединен с групповым управляющим входом адаптивной антенной системы 2, а выход соединен со входом блока 5 адаптации, при этом управляющий вход блока 7 пространственно-частотно-временного расписания подключен ко второму выходу блока 5 адаптации. На групповой информационный вход блока 5 адаптации поступает информация от высших уровней базовой станции, а групповой информационный выход соединен с групповым входом блока 3 кодирования и модуляции, групповой выход которого подключен к групповому информационному входу адаптивной антенной системы 2, с эфирного выхода которой сигнал передается через выход базовой станции 1 на вход абонентской станции 8. Абонентская станция 8 включает второй блок 9 демодуляции и декодирования, информационный вход которого является эфирным входом абонентской станции 8, а выход соединен со входом блока 10 поддержки распорядка расписания, управляющий вход второго блока 9 демодуляции и декодирования соединен с первым выходом блока 10 поддержки распорядка расписания, второй выход блока 10 поддержки распорядка расписания соединен с управляющим входом второго блока 11 кодирования и модуляции. На информационный вход второго блока 11 кодирования и модуляции подается информация от высших уровней абонентской станции 8, с выхода второго блока 11 кодирования и модуляции через выход абонентской станции 8 сигнал транслируется по эфиру от абонентской станции на вход базовой станции 1, являющийся также эфирным входом адаптивной антенной системы 2, а с информационного выхода второго блока 9 демодуляции и декодирования информационный сигнал передается на высшие уровни абонентской станции 8.
N
N
Система связи включает, как минимум, одну базовую станцию и  абонентских станций, обслуживаемых данной базовой станцией, где  принимает значения 1, 2 и т.д.
Базовая станция передает данные на абонентские станции по прямому каналу, а абонентские станции передают данные на базовую станцию по обратному каналу.
Прямые каналы разных базовых станций используют один и тот же частотный ресурс (полосу частот). Обратные каналы разных абонентских станций также используют один и тот же частотный ресурс.
Прямой и обратный каналы могут использовать один и тот же частотный ресурс при временном дуплексе или разные частотные ресурсы при частотном дуплексе.
Данные, передаваемые в прямом канале и предназначенные разным абонентским станциям, в рассматриваемом примере реализации заявляемого способа разделяются между собой в пространстве направлений (с помощью обработки в адаптивной антенной системе), и могут также разделяться по времени и также по времени и по частоте.
Данные, предаваемые в обратном канале от разных абонентских станций, в рассматриваемом примере реализации заявляемого способа разделяются между собой в пространстве направлений (с помощью обработки в адаптивной антенной системе), и могут также разделяться по времени и также по времени и по частоте.
Передатчик базовой станции системы имеет возможность раз в кадр менять вид кодирования и модуляции передаваемых данных, предназначенных отдельным абонентским станциям, а также перераспределять частотно-временной ресурс прямого канала между ними.
Адаптивная антенная система базовой станции имеет возможность раз в кадр менять наборы векторов весовой обработки, предназначенных для реализации пространственной селекции в режиме передачи сигналов отдельным абонентским станциям и предназначенных для реализации пространственной селекции в режиме приема сигналов, передаваемых отдельными абонентскими станциями.
Передатчик любой абонентской станции системы имеет возможность раз в кадр менять вид кодирования и модуляции передаваемых данных, а также передавать данные в любой части частотно-временного ресурса кадра обратного канала.
N
N
Система работает с использованием разбивки времени на кадры, как показано на фиг. 2. Будем называть текущим тот кадр, в котором в настоящий момент происходит работа системы, а формируемым - кадр, следующий непосредственно за текущим кадром. На каждом кадре установлены и остаются неизменными для каждого из  абонентов методы кодирования/модуляции, распределение частотно-временного ресурса, вектора весовой обработки для прямого и обратного каналов. Каждый кадр разделен на элементарные временные интервалы, на которых, согласно расписанию, происходит информационный обмен по эфиру с фиксированным активным подмножеством абонентов. За период одного кадра, каждый из  абонентов получает хоть один элементарный временной интервал для передачи и для приема. Это означает, что активные абонентские подмножества приема и активные абонентские подмножества передачи составляют полные группы. На интервале текущего кадра базовая станция 1 готовит для кадра, следующего за формируемым, и передает уже подготовленную для формируемого кадра информацию управления, содержащую данные о назначаемом расписании распределения частотно-временного ресурса, применяемых способах кодирования и модуляции, а также об энергетических параметрах в виде уровней трансляции в прямом и обратном каналах.
М
Адаптивная антенная система 2, включающая  антенных элементов, может быть реализована с помощью стандартных методов, описанных в [3].
Адаптивная антенная система 2 излучает/принимает сигналы на/от разделенного на группы множества абонентов-источников. При этом используется расписание работы, составленное для текущего кадра, исходя из информации, содержащейся в служебном сообщении одного из предыдущих кадров. Оно показано на фиг. 3. Конкретно, на групповой информационный вход блока 5 адаптации поступает информация от высших уровней базовой станции. По каждой линии группового информационного входа поступает поток данных, предназначенных одному из абонентов. На каждом элементарном временном интервале в блоке 5 адаптации считываются данные из расписания распределения частотно-временного ресурса режима трансляции, показанного на фиг. 3. На их основе определяются:
1. Активные позиции частотно-временного ресурса, используемые для трансляции в прямом канале в данном элементарном временном интервале (в примере, показанном на фиг. 3, они отображены как заштрихованные ячейки).
i
(i=
, …, k), k
j
j
l
l
i, j
2. Номера информационных потоков, которые должны транслироваться в прямом канале в каждой активной частотно-временной позиции. На фиг. 3 они показаны в виде последовательности ячеек расписания , где  - номер элементарного временного интервала 1,2 - число элементарных временных интервалов в одном кадре,  - номер ячейки из диапазона частотного ресурса (=1,2, …, ),  - число частотных ячеек, составляющих частотный ресурс радиоканала,  - число информационных потоков, которые должны предаваться в ресурсной ячейке () в прямом канале.
i, j
3. Виды модуляции и кодирования, применяемые при трансляции в прямом канале каждого из  потоков через ресурсную ячейку (). На фиг. 3 они показаны в виде последовательности ячеек расписания  соответственно.
Блок 5 адаптации может быть реализован на основе программы цифровой обработки, работающей на базе обычного процессора или специализированного вычислительного модуля.
Блок 5 адаптации дополняет информационные потоки, предаваемые на элементарном временном интервале, служебной информацией управления и, в соответствии данными расписания, подает их на соответствующие линии группового входа блока 3 кодирования и модуляции. Также блок 5 адаптации через групповой выход передает на блок 3 кодирования и модуляции команды управления, предназначенные для активации процедур модуляции и кодирования, увязанных с частотно-временным распределением ресурса прямого канала, прописанных в расписании текущего кадра.
С соответствующего первого выхода блока 5 адаптации на управляющий вход первого блока 4 демодуляции и декодирования передаются команды активации процедур демодуляции и декодирования, увязанные с частотно-временным распределением ресурса обратного канала, прописанных в расписании текущего кадра для абонентской станции 8.
Блок 5 адаптации на основе данных, полученных в текущем кадре, производит расчет энергетических параметров, а также видов модуляции и кодирования, которые будут применяться в кадре, следующем за формируемым. Методы расчета указанных параметров известны и описаны в [2].
N
N
N
Со второго выхода блока 5 адаптации на управляющий вход блока 7 пространственно-частотно-временного расписания передается информация об энергетических параметрах в виде уровней трансляций в прямом и обратном каналах в текущем, формируемом и следующим за формируемым кадрах для базовой станции и для  абонентских станций. Также передаются данные об энергетических параметрах в виде результатов измерений уровней принимаемых сигналов базовой станцией 1 в обратном канале и  абонентскими станциями в прямом канале, снимаемые в текущем кадре. Кроме этого передается информация о запросах  абонентских станций на ресурсы прямого и обратного каналов для кадра, следующего за формируемым.
Блок 3 кодирования и модуляции может быть реализован на основе программы цифровой обработки, работающей на базе обычного процессора или специализированного вычислительного модуля.
i (i=
k)
В блоке 3 кодирования и модуляции каждый из предаваемых в прямом канале потоков претерпевает преобразования кодирования и модуляции, заданные в расписании распределения частотно-временного ресурса. В результате с группового выхода блока кодирования и модуляции на групповой информационный вход адаптивной антенной системы 2 в элементарном временном интервале 1,2,…,  подается
i
i, j
j
l
m
М
закодированных и модулированных сигналов. Адаптивная антенная система 2 в начале каждого элементарного интервала (для определенности будем его обозначать номером ) через групповой управляющий вход считывает с группового выхода блока 7 пространственно-частотно-временного расписания множество значений векторов весовой обработки размерности М, прописанных в расписании текущего кадра для прямого канала на данном элементарном интервале. Эти вектора для каждого из  сигналов ресурсной ячейки (), =1,2, …, , задают квадратурные уровни, назначенные для трансляции через антенные элементы (=1…). На фиг. 3 указанные вектора показаны в виде множества последовательностей столбцов
m
М
В процессе работы адаптивная антенная система 2 формирует квадратуры , для каждого из  сигналов. Далее для каждого антенного элемента m (=1, …, ) адаптивная антенная система 2 выполняет взвешенное суммирование
Si
m
j
Si(m)
j
после чего сформированный групповой сигнал (m) подается на вход соответствующего антенного элемента с номером . Заметим, что поскольку индекс суммирования г однозначно связан с индексом частотной ячейки , то суммирование в (2) приводит к тому, что результат  от  не зависит.
i
В результате с эфирного выхода адаптивной антенной системы 2 на каждом элементарном временном интервале () будет производиться трансляция множества сигналов, для каждого из которых будет сформирована индивидуальная диаграмма направленности с областью максимума в направлении на соответствующего абонента, и с зонами минимумов в направлениях других абонентов.
i
Адаптивная антенная система 2, работая в режиме приема, в начале каждого элементарного временного интервала (), считывает с группового управляющего входа, подключенного к групповому выходу блока 7 пространственно-частотно-временного расписания, данные распределения частотно-временного ресурса режима обратного канала текущего кадра, показанного на фиг. 3. На их основе определяются:
1. Активные позиции частотно-временного ресурса, используемые для приема сигналов обратного канала в данном элементарном временном интервале (в примере, показанном на фиг. 3, они отображены как заштрихованные ячейки).
i
i
k
j
j
l
i, j
2. Номера информационных потоков, которые должны приниматься в каждой активной частотно-временной позиции. На фиг. 3 они показаны в виде последовательности ячеек расписания , где  - номер элементарного временного интервала (=1,2, …, ),  - номер ячейки из диапазона частотного ресурса (=1,2, …, ),  - число информационных потоков, которые должны быть приняты в ресурсной ячейке () обратного канала.
М
i, j
3. Вектора весовой обработки размерности , применяемые для адаптивной пространственной обработки на приеме в ресурсной ячейке () обратного канала для каждого из  сигналов. На фиг 3 они показаны в виде множества последовательностей столбцов  с комплексными значениями.
i
После чего адаптивная антенная система 2 производит расчет общего числа сигналов, принимаемых на элементарном временном интервале () обратного канала по формуле
М
Далее для каждого вектора весовой обработки из набора  адаптивная антенная система 2 формирует соответствующий сигнал выхода на основе операции взвешенного суммирования квадратурных сигналов  и , присутствующих на выходах  антенных элементов:
r
Si(r, t)
i, j
q
q
Si(r, t)
r
Si(r,t)
Индексы , задающие номера сигналов выхода , формируемых на выходе приемного тракта адаптивной антенной системы 2, однозначно связаны с набором индексов  и (=1, 2, …, ) - номер информационного потока, передаваемого в ячейке обратного канала. Сигнал выхода  с индексом , соответствующим абонентской станции 8, адаптивная антенная система 2 подключает к информационному входу первого блока 4 демодуляции и декодирования. Также сигнал выхода  с выхода адаптивной антенной системы 2 подается на соответствующий управляющий вход блока 6 оценки направлений, где используется в качестве обучающего, или эталонного, при работе в режиме слежения за угловыми перемещениями абонентской станции 8. Алгоритмы оценки и слежения за угловыми параметрами источников известны и описаны в [3], [4], [5]. Сформированные оценки направлений прихода абонентских сигналов через выход блока 6 оценки направлений передаются на вход блока 7 пространственно-частотно-временного расписания. Блок 6 оценки направлений может быть реализован с помощью программы, работающей на базе обычного процессора или специализированного вычислительного модуля.
Блок 7 пространственно-частотно-временного расписания также может быть реализован с помощью программы, работающей на базе обычного процессора или специализированного вычислительного модуля.
Блок 7 пространственно-частотно-временного расписания считывает со входа информацию о реализовавшемся угловом распределении направлений прихода абонентских сигналов. На основе этой информации блок 7 пространственно-частотно-временного расписания строит «запрещающий граф». Для пояснения на фиг. 4 приведен пример такого «запрещающего графа». Процесс построения «запрещающего графа» состоит в следующем. Позицию базовой станции 1 помещаем в условное начало координат. Каждому направлению прихода абонентского сигнала ставим в соответствие узел «запрещающего графа». Позицию расположения указанного узла в пространстве формируем в два этапа:
1) проводим из условного начала координат луч, направление которого совпадает с указанным выше направлением прихода абонентского сигнала;
2) отмечаем на полученном луче точку, отстоящую от условного начала координат на расстоянии в близких пределах некоторой заданной величины. (Выбор расстояния произволен, так как на дальнейших операциях и расчетах не сказывается. Его выбор служит только для наглядности работы режима формирования «запрещающего графа», чтобы узлы близких направлений не сливались).
М
М
n
N
a1
a2
a
N
a1
a2
a
N
a
n
Далее осуществляется перебор всех направлений приходов сигналов абонентов. При этом для каждого выбранного направления прихода сигнала абонента строим «запрещающий конус» с угловым размером в вершине 2⋅As (см. Фиг. 5). И все узлы «запрещающего графа», попавшие внутрь указанного «запрещающего конуса», соединяем ребрами с узлом, связанным с выбранным направлением прихода сигнала абонента. Размер запрещающего сектора 2⋅As, как показали результаты экспериментальной проверки, следует выбирать в пределах диапазона, [0.75-0.85]⋅(Ф°/), где Ф° - общий размер углового сектора работы адаптивной антенной системы 2,  - число антенных элементов в адаптивной антенной системе 2. При выборе 2⋅As из такого диапазона пропускная способность радиоканала в итоге оказывается либо совпадающей, либо мало отличающейся от максимума. После этого блок 7 пространственно-частотно-временного расписания считывает с управляющего входа информацию о запрашиваемых абонентскими станциями ресурсах канала связи в кадре, следующем за формируемым. Значения запрошенных ресурсов подвергаются процедуре дискретизации, в результате чего получаются целые значения D, D, …, D, показывающие, сколько «минимальных порций» ресурса следует распределять абонентским станциям при составлении расписания. Опыт практической работы сетей сотовой связи показал, что для решения задач максимизации пропускной способности радиоканала при составлении расписаний достаточно использовать от 3 до 6 уровней дискретизации запрашиваемых ресурсов. Далее, в соответствии с полученными значениями D, D, …, D, в «запрещающем графе» выполняется операция D-кратного дублирования (=1,2, …, ) узлов, сопоставляемых абонентским станциям. На фиг. 6 для примера показана ситуация операций 2-кратного и 3-кратного дублирования узлов в «запрещающем графе». Указанная операция дублирования узлов графа известна и описана в [6]. Заключается она во введении в граф дополнительного узла, копирующего все ребра своего узла-прообраза и введении ребра между дополнительным узлом и узлом-прообразом. На этом формирование «запрещающего графа» заканчивается.
После этого в блоке 7 пространственно-частотно-временного расписания выполняется три шага обработки, в результате чего составляется пространственно-частотно-временное расписание для кадра, следующего за формируемым.
На первом шаге обработки выполняется «правильная раскраска» узлов «запрещающего графа». Правильная раскраска узлов графа минимальным числом цветов - классическая задача теории графов, которая подробно описана в [6], [7]. Она предполагает, раскраску всех узлов графа так, что не существует двух узлов, выкрашенных в один цвет и соединенных ребром. В нашем случае каждый цвет можно трактовать как номер фрагмента частотно-временного ресурса канала. «Правильная раскраска» «запрещающего графа» гарантирует, что для всех пар, составленных из абонентов, для которых угловое расстояние направлений прихода сигналов не позволяет произвести адаптивной антенной системе 2 пространственную селекцию сигналов с заданным уровнем качества, не будет ни одной пары абонентов «выкрашенных в один цвет», или (что эквивалентно) не будет пары, в которой абонентам выделен общий частотно-временной ресурс в формируемом расписании. Каждая группа абонентов, связанная с конкретным цветом раскраски, может использовать общий частотно-временной ресурс канала, так как все сигналы абонентов, составляющих данную группу, могут быть разделены с заданным уровнем качества исключительно на основе методов пространственной селекции в адаптивной антенной системе 2. Каждой группе абонентов, связанной с отдельным цветом раскраски, необходимо выделять отдельный частотно-временной ресурс в формируемом расписании, так как в противном случае может оказаться, что в совмещенном частотно-временном ресурсе будут работать абоненты, сигналы которых нельзя разделить с заданным уровнем качества в адаптивной антенной системе 2. Минимум числа цветов «правильной раскраски» обеспечивает максимум частотно-временного ресурса радиоканала, распределяемого на каждую группу абонентов, связанную с отдельным цветом раскраски.
Алгоритм «правильной раскраски» узлов графа известен и описан в [6], [7]. Он основан на последовательном выполнении операции «стягивания узлов». Указанная операция предполагает произвольный выбор пары узлов графа, не соединенных ребром, и последующую замену выбранной пары одним узлом, который имеет соединительные ребра, которыми обладал хоть один из узлов стягиваемой пары. Фиг. 7а-7г поясняют указанную операцию «стягивания». Процесс заканчивается тогда, когда для графа достигается состояния полной связанности (Фиг. 7г). Решение задачи раскраски определяется результирующим полносвязанным графом с минимальным числом узлов. Так как на каждом шаге работы алгоритма необходимо рассматривать всевозможные пары «стягиваемых узлов», то число обрабатываемых графов с увеличением числа шагов возрастает экспоненциально. Поэтому точное решение задачи раскраски узлов за приемлемое время удается получить только для графов с небольшим числом узлов (до 8-12). Так как число абонентов, обслуживаемых базовой станцией 1, может оказаться больше, то для решения задачи раскраски требуется использовать другие алгоритмы, обладающие менее высокой сложностью. В теории графов разработан целый класс таких алгоритмов, называемых «жадными», которые на каждом шаге используют сокращенный перебор комбинаций узлов для «стягивания», и в следствии чего имеют полиномиальную сложность. При этом они с вероятностью близкой к 1 дают точное решение задачи «правильной раскраски» узлов и лишь в отдельных случаях ошибаются в сторону увеличения минимального числа цветов (как правило, на 1 позицию). Эти алгоритмы известны и их описание можно найти в [8], [9]. Конкретно, были проведены тестовые испытания работы «жадных алгоритмов», использующих на каждом шаге выбор единственной пары «стягиваемых узлов» с помощью прогнозных оценок Турана, описание которых дано в [6], и на основе методики Муллата, описанной в работах [10], [11]. В обоих случаях на выборках более 2000 испытаний не было обнаружено ни одной ошибки решения задачи «правильной раскраски» узлов графа минимальным числом цветов. Особенно простой и наглядный вид алгоритм «раскраски» приобретает в случае использования прогнозных оценок Турана. Указанные оценки позволяют находить верхнюю и нижнюю границы минимального числа цветов на основе аналитических соотношений от числа узлов и числа ребер графа. Согласно им, при заданном числе узлов, с ростом числа ребер может происходить только рост указанных границ. Поэтому на каждом шаге для операции «стягивания» следует выбирать пару несвязанных узлов, которые имеют максимальное число общих «соседей» (соседними являются узлы графа, связанные ребром), так как при таком выборе после «стягивания» число ребер в графе сократиться максимально. Пример, показанный на фиг. 7а - фиг. 7г, демонстрирует такой метод выбора пар для «стягивания». На фиг. 8 приведен конечный результат решения задачи правильной «раскраски узлов» «запрещающего графа». Цвета «раскраски» условно обозначены римскими цифрами.
Также на фиг. 8 показана секторная структура, отвечающая определенной конфигурации базовой станции с обычными (не адаптивными) антеннами, с помощью которой можно объяснить физический смысл работы алгоритма составления пространственно-частотно-временного расписания, построенного на базе «раскраски узлов» «запрещающего графа». Размер отдельного сектора на фиг. 8 задан по угловой разрешающей способности адаптивной антенной системы 2. Как можно видеть, работу алгоритма можно трактовать как настройку азимутов секторов так, что «плотные» скопления абонентов попадают в окрестности центральных зон секторов (т.е. выводятся за зоны перекрытий секторов). Для остальных абонентов, попавших в окрестности зон перекрытий, алгоритм при формировании расписания учитывает возможность работы в режиме с совмещением частотно-временных ресурсов с теми абонентами, которые находятся на противоположном крае сектора.
На фиг. 9 показан пример оптимального расписания распределения частотно-временного ресурса, составленного в соответствии с полученным решением задачи «раскраски узлов» «запрещающего графа».
N
На втором шаге частотно-временные ресурсы радиоканала, выделенные базовой станции 1 для трансляции и приема, разделяются на равные по объему фрагменты, числом равным числу цветов, полученному при решении задачи «правильной раскраски» узлов «запрещающего графа». После этого составляется распределение частотно-временного ресурса радиоканала для расписаний прямого и обратного каналов в кадре, следующем за формируемым. При этом каждый абонент получает именно тот фрагмент частотно-временного ресурса, который соответствует группе, в которую он попал при решении задачи «правильной раскраски» узлов «запрещающего графа». Затем полученное расписание для каждого абонента дополняется информацией о применяемой модуляции, кодировании и необходимом уровне передачи. После чего информация о составленном расписании кадра, следующем за формируемым, через выход передается на вход блока 5 адаптации, в котором производится дополнение информационных потоков высших уровней базовой станции 1, служебной информацией управления, содержащей данные о сформированном расписании. Далее, в формируемом кадре будет последовательно через блок 3 кодирования и модуляции, через блок адаптивной антенной системы 2 и через эфир прямого канала произведена трансляция составленного расписания на  абонентских станций (и на абонентскую станцию 8, в частности).
i
На третьем шаге расписание распределения частотно-временного ресурса, составленное для формируемого кадра, дополняется информацией о векторах весовой обработки, которые должны применяться в режимах трансляции по прямому и приема по обратным каналам на базовой станции 1. С этой целью для каждой ресурсной ячейки (, j) расписания формируемого кадра составляются списки номеров абонентских станций:
А) которым базовая станция 1 будет по прямому каналу передавать сигнал:
,
Б) от которых базовая станция 1 будет по обратному каналу принимать сигнал:
i, j
k
После этого для каждой ресурсной ячейки () расписания формируемого кадра вычисляются вектора весовой обработки, которые будут применяться на базовой станции 1 при трансляции  и при приеме ,  - значение из списка, однозначно определяющее номер абонентской станции, с которой осуществляется радиосвязь.
Алгоритмы расчета векторов весовой обработки известны и приведены в работах [3], [12], [13].
i, j
После этого блок 7 пространственно-частотно-временного расписания дополняет каждую ресурсную ячейку () расписания формируемого кадра полученными значениями векторов весовой обработки. На этом процесс составления расписания пространственно-частотно-временного распределения для формируемого кадра завершается.
i, j
r
i, j
На управляющий вход первого блока 4 демодуляции и декодирования с соответствующего первого выхода блока 5 адаптации передается команда установки нужного режима работы с демодуляцией по закону  и декодирования по закону , где индексы () определяются позицией ресурсной ячейки обратного канала в текущем кадре, а  задает номер информационного потока в указанной ресурсной ячейке (), связанного с абонентской станцией 8.
N
N
Первый блок 4 демодуляции и декодирования может быть реализован с помощью программы цифровой обработки, работающей на базе обычного процессора или специализированного вычислительного модуля. Базовая станция 1 должна поддерживать работу  таких блоков 4 демодуляции и декодирования, каждый из которых организует обработку сигнала обратного канала для одной из  абонентских станций.
Si(r,t)
r
i, j
В результате обработки сигнала выхода , с индексом , соответствующим сигналу, предаваемому абонентской станцией 8 в ресурсной ячейке (), первый блок 4 демодуляции и декодирования формирует поток данных, из которого выделяется служебная информация (рапорты измерений, выполненных абонентской стацией 8, запросы ресурса прямого и обратного каналов для кадра, следующего за формируемым), и поток данных для высших уровней базовой станции 1. Поток данных для высших уровней базовой станции 1 подается на информационный выход первого блока 4 демодуляции и декодирования.
При этом через первый выход первого блока 4 демодуляции и декодирования на управляющий вход блока адаптации 5 передается выделенная служебная информация, дополненная данными об энергетическом параметре в виде измерений уровня принимаемого в обратном канале текущего кадра сигнала абонентской станции 8.
i
На абонентской станции 8 в начале каждого элементарного временного интервала блок 10 поддержки распорядка расписания, который можно реализовать с помощью программы, работающей на базе обычного процессора или специализированного вычислительного модуля, через первый выход подает на управляющий вход второго блока 9 демодуляции и декодирования сигнал включения/выключения, в зависимости от того, прописана или нет в расписании на данном элементарном временном интервале () трансляция по прямому каналу от базовой станции 1 на абонентскую станцию 8.
Второй блок 9 демодуляции и декодирования можно реализовать аналогично прототипу [2].
i
i
k
j
l
i, j
i
Работа абонентской станции 8 происходит аналогично [2]. А именно, если по расписанию текущего кадра на элементарном временном интервале  (=1, …, ) происходит активация работы второго блока 9 демодуляции и декодирования, то блок 10 поддержки расписания через первый выход передает данные о типе используемой модуляции и кодировании , , =1, …, , где () - номера ресурсных ячеек, в которых по расписанию текущего кадра происходит трансляция сигнала от базовой станции 1 на абонентскую станцию 8. Второй блок 9 демодуляции и декодирования производит обработку принятого сигнала, поступающего с информационного входа, в соответствии типами модуляции, кодирования и частотно-временным ресурсом, заданными расписанием прямого канала текущего кадра для абонентской станции 8. В результате второй блок 9 демодуляции и декодирования осуществляет выделение принятых данных и разделяет их на данные высших уровней абонентской станции 8 и служебную информацию. Указанная служебная информация содержит распределение частотно-временного ресурса, виды модуляции/кодирования, энергетические параметры в виде уровней передачи в прямом и обратном каналах формируемого кадра для абонентской станции 8. После этого второй блок 9 демодуляции и декодирования дополняет служебную информацию данными энергетического параметра в виде измерений уровня принятого по прямому каналу сигнала базовой станции 1. Данные высших уровней второй блок 9 демодуляции и декодирования передает на выход абонентской станции 8, а служебную информацию на управляющий выход, с которого она поступает на вход блока 10 поддержки распорядка расписания. Со второго выхода блок 10 поддержки распорядка расписания передает на управляющий вход второго блока 11 кодирования и модуляции данные об измеренном энергетическом параметре в виде уровня принятого в прямом канале текущего кадра сигнала базовой станции 1, а также сигнал включения/выключения, в зависимости от того, прописана или нет в расписании на данном элементарном временном интервале () трансляция по обратному каналу от абонентской станции 8 на базовую станцию 1.
Второй блок 11 кодирования и модуляции может быть реализован аналогично прототипу [2].
о
i
i
k
j
l
i, j
Также аналогично [2], если по расписанию текущего кадра на элементарном временнм интервале (=1, …, ) происходит активация работы второго блока 11 кодирования и модуляции, то блок 10 поддержки расписания через второй выход передает данные о типе используемой модуляции и кодировании , , =1, …, , где () - номера ресурсных ячеек, в которых по расписанию текущего кадра происходит трансляция сигнала по обратному каналу от абонентской станции 8 на базовую станцию 1. Второй блок 11 кодирования и модуляции дополняет данные высших уровней абонентской станции 8 и запрос ресурсов прямого и обратного каналов для кадра, следующего за формируемым, поступающие к нему через информационный вход, данными рапорта произведенных измерений. После чего второй блок 11 кодирования и модуляции производит кодирование и модуляцию в соответствии с правилами, заданными расписанием обратного канала текущего кадра, усиливает полученный сигнал до уровня, заданного соответствующим энергетическим параметром в расписании и транслирует через выход сформированный сигнал по обратному каналу на эфирный вход базовой станции 1.
Таким образом, за счет использования метода графов для формирования расписания распределения частотно-временного ресурса, обладающего максимальной плотностью для наблюдаемого пространственно-углового распределения абонентских станций, в сочетании с пространственной селекцией сигналов, осуществляемой в адаптивной антенной системе базовой станции, повышаются пропускная способность радиоканала и эффективность использования частотно-временного ресурса.
Источники информации
1. Заявка на изобретение US 2002/0183010, H04B 17/00. "Wireless communication systems with adaptive channelization and link adaptation".
2. Патент RU №2267863, МПК H04B 17/00, приоритет 21.08.2003 г.
nd
3. Monzingo R.A., Haupt R.L., Miller T.W. Introduction to Adaptive Arrays. - 2 Edition/ Published by SciTech Publishing, Inc., 2011. - 510 p.
4. Абрамович Ю.И., Спенсер H.K., Горохов А.Ю. Выделение независимых источников излучения на неэквидистантных антенных решетках // Успехи современной радиоэлектроники, 2001. - №12. - С. 3-17.
5. Roy R., Kailath Т. ESPRIT - Estimation of Signal Parameters Via Rotational Invariance Techniques // IEEE Transaction on Acoustics Speech and Signal Processing, Vol. 37, No 7, May 1989, p. 984-995.
6. Зыков А.А. Основы теории графов. - M.: Наука, 1987. - 384 с.
7. Оре О. Теория графов. - М.: Наука, Главная редакция физико-математической литературы, 1980. - 336 с.
8. Curtis S.A. The Classification of Greedy Algorithms // Science of Computer Programming 49 (2003), p. 125-157, Elsevier.
9. Halldorsson M., Szegedy M. Lower bounds for on-line graph coloring// Theoretical Computer Science 130 (1994), p. 163-174, Elsevier.
10. Муллат И.Э. Экстремальные подсистемы монотонных систем. 1 // Автоматика и телемеханика, 1976. - №5. - С. 130.
11. Муллат И.Э. Экстремальные подсистемы монотонных систем. 2 // Автоматика и телемеханика, 1976. - №8. - С. 169.
12. Журавлев А.К., Лукошкин А.П., Поддубный С.С. Обработка сигналов в адаптивных антенных решетках. - Л.: Изд-во Ленинградского ун-та, 1983. - 240 с.
13. Уидроу Б., Стирнз С. Адаптивная обработка сигналов. - М.: Мир, 1989. - 440 с.