Аннотация результатов, полученных в 2021 году
Получены границы достижимости для случайного доступа без идентификации (СДИ) с MIMO приемником в канале Рэлея. Граница получена в виде минимальной энергии, необходимой для передачи одного информационного бита, при условии максимально допустимой вероятности ошибки на пользователя. Вывод границы основан на анализе декодера по методу максимального правдоподобия. В результатах, полученных для случая одной принимающей антенны, было показано, что декодирование по методу максимального правдоподобия эквивалентно решению задачи поиска максимальной нормы проекции принятого сигнала на подпространство, порожденное подмножеством кодовых слов. При выводе границы достижимости необходимо найти распределение отношения норм проекций на множество правильно принятых кодовых слов и на множество ошибочно декодированных кодовых слов. Для случая одной антенны данное отношение имеет бета-распределение, что существенно упрощает дальнейший вывод. В случае многих антенн было доказано, что данное отношение ограничено сверху суммой независимых бета-распределенных случайных величин. При этом каждое из бета-распределений имеет различные параметры. Разработана практическая схема на основе алгоритма декодирования TIN-SIC (treat interference as noise + successive interference cancellation). В основе схемы лежит протокол слотированная T-кратная АЛОХА: кадр разбивается на слоты, и сообщение пользователя, закодированное полярным кодом, передается в случайно выбранном слоте. Декодер способен разрешить коллизии кратности до T. Произведена модификация алгоритма декодирования TIN-SIC на случай нескольких принимающих антенн. Основное отличие нового алгоритма заключается в оценке канала для сильнейшего пользователя для случая нескольких принимающих антенн. Метод основан на подборе такой оценки канала, согласованный фильтр для которой обеспечит кластеризацию принятого сигнала на две компоненты с минимальной дисперсией. Такую оценку можно получить методом градиентного спуска. С помощью вычислительных экспериментов продемонстрирован выигрыш в энергетической эффективности порядка 10 дБ, а также увеличение количества одновременно активных пользователей в кадре вдвое при переходе от одной к восьми антеннам на базовой станции. Разработаны практические схемы на основе метода сжатия измерений. Поскольку размерность задачи СДИ не позволяет непосредственно применить стандартные алгоритмы сжатия измерений, в основе разработанной схемы лежит принцип “разделяй и властвуй”: кадр разбивается на слоты, и в каждом слоте решается задача сжатия измерений. Каждое сообщение кодируется внешним кодом, символы которого (передаваемые в слоте сообщения) кодируются внутренним кодом. Задача внутреннего кода - передать внешнему коду список сообщений, которые были переданы в слоте. Задача внешнего кода - восстановить по полученным в каждом из слотов спискам переданные сообщения. Данная задача известна как задача восстановления по спискам (англ., list recovery problem). Получена граница достижимости для энергетической эффективности схемы на основе сжатия измерений с внешним кодом, способным исправить t ошибок. Показано, что для канала Рэлея и для случая одной антенны на базовой станции переход к t=5 позволяет улучшить энергетическую эффективность на 7-10 дБ по сравнению со случаем t=0. Предложена практическая конструкция кодов, позволяющих решать задачу восстановления по спискам. Данные коды задаются с помощью верхней треугольной порождающей матрицы. Проведен теоретический анализ предложенного алгоритма, подтвержденный результатами имитационного моделирования. Показано, что построенные коды близки по энергетической эффективности к предложенным границам. Для снижения вычислительной сложности предложена еще одна практическая схема, где в качестве внешнего кода используется код Рида-Соломона в сочетании с алгоритмом Гурусвами-Судана. Показано, что решение на основе кодов Рида-Соломона позволяет обеспечить энергетическую эффективность, соответствующую границе достижимости кода для t=2. Полученные выше результаты были расширены на случай нескольких принимающих антенн на базовой станции. Показано, что переход к 8 антеннам на приемнике позволяет получить выигрыш порядка 11 дБ по энергетической эффективности и в полтора раза увеличить максимальное число активных пользователей (граница достижимости, случай t=5). Рассмотрен алгоритм декодирования слота с низкой вычислительной сложностью AMP (approximate message passing), позволяющий учитывать априорную информацию, что делает возможным применение методов итеративного декодирования системы слот-внешний код. Получены апостериорные вероятности детектирования сообщения в слоте, которые в дальнейшем передаются декодеру внешнего кода. В качестве декодера внешнего кода были рассмотрены коды с малой плотностью проверок (МПП-коды, LDPC codes). Рассмотрена модификация системы СДИ, в которой предполагается, что близко расположенные устройства передают одинаковую информацию. В случае успешной передачи данных от одного из пользователей, систему покидает данный пользователь а также пользователи, расположенные рядом. Для этой модели системы предложены методы построения верхней и нижней оценок средней задержки. Кроме того, предложен способ расчета верхней оценки для средней задержки.

Аннотация результатов, полученных в 2022 году
Получена улучшенная теоретическая оценка для практической схемы на основе кодов, заданных с помощью верхней треугольной порождающей матрицы (t-tree коды). Новая оценка позволила провести анализ для t > 1, а также оценить средний размер списка путей на каждом шаге декодирования. Были предложены методы сокращения списков на промежуточных шагах работы алгоритма декодирования с помощью сортировки путей в соответствии с вычисленными метриками и отбрасыванием путей с наименьшими метриками. Данная процедура позволяет значительно уменьшить сложность декодирования и уменьшить число ложных сообщений в выходном списке. Была разработана и исследована итеративная схема декодирования на основе алгоритма AMP (approximate message passing) и кодов с малой плотностью проверок (МПП-кодов), в которой внутренний и внешний код обмениваются апостериорными логарифмическими отношениями правдоподобия оценок принятых символов. В итеративной схеме использованы разреженные регрессионные коды (sparse regression codes, SPARC). Подход на основе SPARC-кодов был обобщен на случай случайного доступа без идентификации (СДИ) в MIMO канале. Были получены правила AMP декодирования внутреннего кода. В качестве внешнего кода был выбран разреженный код, заданный с помощью верхней треугольной порождающей матрицы. Такие коды являются частным случаем МПП-кодов. Была проведена оптимизация внешних МПП-кодов с использованием метода эволюции плотностей (квантованный вариант данного алгоритма). Итеративный алгоритм показывает лучшую энергоэффективность по сравнению со схемой на основе t-tree кода. Разрыв растет с увеличением числа антенн. Итеративный алгоритм позволяет выиграть порядка 2 дБ при 64 антеннах и 150 пользователях, но приводит к значительному увеличению сложности декодирования. Проведено обобщение схемы на основе алгоритма TIN-SIC на случай большого числа приемных антенн. В основе схемы лежит протокол слотированная T-кратная АЛОХА: кадр разбивается на слоты, и сообщение пользователя, закодированное полярным кодом, передается в случайно выбранном слоте. Начиная с 64 приемных антенн, предложенная ранее процедура кластеризации оказывается вычислительно нестабильной, поэтому схема была дополнена неортогональными преамбулами. Предложен алгоритм построения полярных кодов с динамическими заморозками, который позволяет строить близкие к оптимальным полярные коды для многопользовательского канала и декодирования списком. Энергоэффективность результирующей схемы близка к фундаментальным пределам (разница составила 0.8 дБ). Переход от 8 к 64 антеннам привел к улучшению энергоэффективности на 9 дБ. Данная схема показывает наилучшие результаты при условии достаточной длины слота для передачи преамбулы и кодового слова. Улучшена граница достижимости для СДИ с MIMO приемником в канале Рэлея. Подход основан на том, что при фиксированных кодовых словах сигналы на разных антеннах являются независимыми нормально-распределенными случайными векторами. Это и позволяет провести теоретический анализ искомой условной вероятности ошибки. Для уточнения аддитивной границы был использован метод Фано, заключающийся в том, что аддитивная граница применяется лишь в так называемом хорошем регионе, а при выходе за пределы хорошего региона условная вероятность ошибки полагается равной единице. Усреднение по кодовым словам выполняется с помощью метода Монте-Карло. Данный набор приемов позволил значительно улучшить границу достижимости. Рассмотрен важный с практической точки зрения сценарий, когда в системе есть устройства со спорадическим трафиком (устройства первого типа), а также устройства, постоянно подключенные к базовой станции и передающие регулярно (устройства второго типа). Предложен и проанализирован протокол, заключающийся в модификации механизма случайного доступа и введении дополнительной случайной задержки при отправке преамбулы для устройств первого типа. Показано, что такая модификация позволяет сократить время доставки сообщений, переданных устройствами второго типа. Разработана практическая схема на основе подхода Compute and Forward (СoF), идея которого состоит в декодировании не отдельных сообщений, а их линейных комбинаций, что позволяет значительно снизить интерференцию, а, следовательно, повысить скорость пользовательских кодов. Для решения задачи декодирования линейных комбинаций сообщений были использованы комплекснозначные коды на решетке (lattice codes) low density construction-A (LDA), для которых верно, что любая целочисленная комбинация любого количества кодовых слов на решетке эквивалентна единственному кодовому слову по модулю простого числа, что сводит задачу декодирования в системе СДИ к однопользовательской задаче помехоустойчивого декодирования с последующим выделением сообщений пользователей из их целочисленных линейных комбинаций. Разработана соответствующая модуляция на основе гауссовских целых чисел и чисел Эйзенштейна, сохраняющая операции сложения и умножения при отображении точки решетки в элемент поля по модулю простого числа. В качестве кодов для построения LDA решетки были выбраны МПП-коды и полярные коды, заданные над полем по модулю простого числа, известные своими эффективными алгоритмами декодирования с малой сложностью реализации. В СДИ с MIMO приемником использование нескольких принимающих антенн позволяет наблюдать различные линейные комбинации переданных кодовых слов (которые задаются матрицей канала) с шумом. Для получения целочисленных комбинаций переданных сообщений нужно умножить принятый сигнал на некоторую специально выбранную матрицу B, что приводит к уменьшению интерференции, но усиливает шум. Поиск наилучшей матрицы B осуществляется с помощью алгоритма Ленстры-Ленстры-Ловаса (ЛЛЛ-алгоритм). Данный подход известен как Integer Forcing (IF). Разработанная схема исследована методом имитационного моделирования. Показано, что схема на основе подхода CoF обеспечивает значительно улучшает энергетическую эффективность при большом числе (>1000) активных пользователей по сравнению со схемой на основе алгоритма TIN-SIC. На базе SDR-стенда Лаборатории Интернета вещей Сколковского института науки были реализованы следующие алгоритмы: 1) практическая схема на основе алгоритма TIN-SIC и полярных кодов для базовой станции, оснащенной несколькими антеннами, 2) практические схемы на основе метода сжатия измерений, а именно декодер внутреннего кода (алгоритм OMP -- orthogonal matched pursuit) и декодер t-tree кода и 3) реализован алгоритм декодирования сигнала на основе compute and forward (CoF). Параметры системы выбраны следующим образом: каждый пользователь передает 48 информационных бит, кадр состоит из 1440 отсчетов и разбит на 12 слотов. Малая длина слота выбрана для устойчивой работы алгоритмов декодирования при малом времени когерентности в канале. Базовая станция оснащена 64 антеннами. Реализация разработанных протоколов в рамках SDR-стенда позволяет убедиться, что полученные путем вычислительных экспериментов вероятности ошибки передачи сообщения на пользователя вполне соответствуют результатам натурных экспериментов.