Aloca˘c~ao de Pot^encia e Protocolos de Acesso em Redes ...Ficha Catalogr a ca de Souza, Jo~ao Henrique Inacio Aloca˘c~ao de Pot^encia e Protocolos de Acesso em Redes de Comu-nica˘c~ao

Centro de Tecnologia e UrbanismoDepartamento de Engenharia Eletrica

Joao Henrique Inacio de Souza

Alocacao de Potencia e Protocolos de

Acesso em Redes de Comunicacao 5G

Monografia apresentada ao curso de

Engenharia Eletrica da Universidade

Estadual de Londrina, como parte dos

requisitos necessarios para a conclusao

do curso de Engenharia Eletrica.

Londrina, PR2018


Alocacao de Potencia e Protocolos de

Acesso em Redes de Comunicacao 5G

Monografia apresentada ao curso de Engenharia

Eletrica da Universidade Estadual de Londrina,

como parte dos requisitos necessarios para a

conclusao do curso de Engenharia Eletrica.

Area: Sistemas de Telecomunicacoes

Orientador:

Prof. Dr. Taufik Abrao

Londrina, PR2018

Ficha Catalografica

de Souza, Joao Henrique InacioAlocacao de Potencia e Protocolos de Acesso em Redes de Comu-

nicacao 5G. Londrina, PR, 2018. 37 p.

Monografia (Graduacao) – Universidade Estadual de Londrina,PR. Departamento de Engenharia Eletrica.

I. Orthogonal frequency division multiplexing (OFDM), II. Bit-loadingIII. Ultra-reliable low-latency communcations (URLLC) IV. Massivemachine-type communications (mMTC) V. Random access protocolVI. Approximate message passing (AMP)Departamento de Engenharia Eletrica


Alocacao de Potencia e Protocolos deAcesso em Redes de Comunicacao 5G

Monografia apresentada ao curso de Engenharia

Eletrica da Universidade Estadual de Londrina,

como parte dos requisitos necessarios para a

conclusao do curso de Engenharia Eletrica.

Area: Sistemas de Telecomunicacoes

Comissao Examinadora

Prof. Dr. Taufik AbraoDepto. de Engenharia Eletrica

Universidade Estadual de LondrinaOrientador

Prof. Me. Jaime Laelson JacobDepto. de Engenharia Eletrica

Universidade Estadual de Londrina

Prof. Dr. Jose Carlos Marinello FilhoDepto. de Engenharia Eletrica

Universidade Estadual de Londrina

Londrina, 7 de dezembro de 2018

Dedico este trabalho ao meu pai, Jose

Augusto de Souza (in memorian).

Agradecimentos

Gostaria de agradecer a todos os que participaram de alguma forma do meu

processo de formacao. Agradeco a minha mae, Vera, e ao meu pai, Jose, por

todo o carinho e esforco investidos na minha criacao. Voces sao o suporte de

tudo o que sou e, de longe, o melhor exemplo que eu poderia ter. Espero um dia

me tornar para alguem uma pequena fracao daquilo que voces representam em

minha vida!

Em especial, agradeco aos meus amigos Caio, Diogo e Renan por todos estes

anos de cumplicidade. Voces me guiaram nestes cinco anos, e participaram de

muitas historias que jamais me esquecerei. A amizade de voces foi o presente

mais valioso que UEL me deu.

Agradeco ao professor Taufik pela dedicacao ao seu trabalho e sua orientacao.

As discussoes, sempre de alto nıvel tecnico, ja me levaram a lugares que nunca

pude imaginar que chegaria. Espero que possam me levar ainda mais longe.

Por fim, mas nao menos importante, agradeco a Universidade Estadual de

Londrina, a Fundacao Araucaria e ao Conselho Nacional de Desenvolvimento

Cientıfico e Tecnologico (CNPq) pelo financiamento da maior parte da pesquisa

apresentada neste trabalho.

Resumo

A implementacao das redes de comunicacoes de quinta geracao (5G) re-quer tecnologias eficientes para servir populacoes densas em cenarios de comu-nicacao do tipo maquina (mMTC - massive machine-type communications) paraos servicos de internet das coisas (IoT - internet of things) e aplicacoes de missaocrıtica que exigem alta confiabilidade e baixa latencia (URLLC - ultra-reliablelow-latency communications). A modulacao OFDM (orthogonal frequency di-vision multiplexing) e uma tecnologia adotada na geracao anterior que continuasendo uma forte candidata para integrar os sistemas futuros. Alem disso, diversostrabalhos tem apresentado outros esquemas de modulacao relevantes que com-partilham diversas caracterısticas com o OFDM, e.g. f-OFDM (filtered OFDM),UFMC (universal-filtered multicarrier), FBMC (filter bank multicarrier). Destemodo as tecnicas de alocacao de recursos e scheduling ja existentes podem serfacilmente adaptadas para introducao nos novos sistemas multiportadora. Alemda preocupacao com a modulacao, existe um interesse em adotar protocolos dis-tribuıdos e nao-coordenados para o controle da camada MAC (medium accesscontrol), reduzindo a carga de processamento nos nos centrais durante a etapa deacesso com baixa latencia e overhead. Dentro dos dois contextos apresentados,este trabalho traz dois estudos relacionados ao desenvolvimento de tecnologiaspara as redes 5G: a) analise de uma tecnica de baixa complexidade para a distri-buicao de potencia e bits em sistemas OFDM; b) a caracterizacao de um esquemade deteccao de atividade de terminais em um protocolo de acesso nao-ortogonalvoltado para o cenario mMTC baseado no algoritmo approximate message passing(AMP).

Palavras-chave: orthogonal frequency division multiplexing (OFDM), bit-loading,ultra-reliable low-latency communications (URLLC), massive machine-type com-munications (mMTC), random access protocol, approximate message passing (AMP)

Abstract

The deployment of the fifth generation (5G) networks requires efficient tech-nologies to serve dense populations of machine-type devices (mMTC) for the IoTservices and the mission critical applications that need ultra reliability and lowlatency (URLLC). The OFDM (orthogonal frequency division multiplexing) isa modulation scheme adopted on the previous generation that remains a strongcandidate to constitute the future systems. Moreover, many works has presentedother modulation schemes that share multiple characteristics with the OFDM,e.g. f-OFDM (filtered OFDM), UFMC (universal-filtered multicarrier), FBMC(filter bank multicarrier). Therefore the current resource allocation and schedul-ing techniques can be simply adapted to be introduced at the new multicarriersystems. Plus the concern about the modulation scheme, there are much inter-est in adopting distributed and non-coordinated protocols for the MAC (mediumaccess control) layer control, reducing the processing load at the central nodesduring the access with low latency and overhead. On these presented contexts,this work introduces two studies related to the development of technologies forthe 5G networks: a) the analysis of a low complexity power and bits allocationtechnique on OFDM systems; b) the characterization of a terminal activity detec-tion scheme on a non-orthogonal access protocol assigned to the mMTC scenariobased on the AMP algorithm.

Keywords: orthogonal frequency division multiplexing (OFDM), bit-loading,ultra-reliable low-latency communications (URLLC), massive machine-type com-munications (mMTC), random access protocol, approximate message passing(AMP)

Sumario

Lista de Abreviaturas

Convencoes e Notacoes

Lista de Sımbolos

1 Introducao 1

1.1 Esquema de Modulacao OFDM . . . . . . . . . . . . . . . . . . . 3

1.2 Protocolos de Acesso . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.2.1 Protocolos de Acesso Nao-Ortogonal . . . . . . . . . . . . 8

2 Resultados 10

3 Conclusao 12

Bibliografia 14

Apendice A -- Bit-Loading e a Capacidade de Sistemas OFDM 16

Apendice B -- Hybrid Hughes-Hartogs power allocation algorithms

for OFDMA systems 19

Apendice C -- Approximate message-passing algorithm for mMTC

terminals activity detection 28

Lista de Abreviaturas

3GPP LTE 3rd Generation Partnership Project Long Term Evolution

4G Redes de comunicacoes moveis da quarta geracao

5G Redes de comunicacoes moveis da quinta geracao

AMP Approximate message passing

BPDN Basis pursuit denoising

CR Cognitive radio (radio cognitivo)

FBMC Filter bank multicarrier (modulacao multiportadora por banco

de filtros)

FFT Fast Fourier transform (transformada rapida de Fourier)

f-OFDM Filtered orthogonal frequency division multiplexing (multiplexacao

por divisao em frequencias ortogonais filtrado)

HH Algoritmo de Hughes-Hartogs

IEEE Institute of Electrical and Electronics Engineers

IFFT Inverse fast Fourier transform (transformada rapida inversa de

Fourier)

IoT Internet of things (internet das coisas)

ISI Inter-symbol interference (interferencia intersimbolica)

MAC Medium access control (controle de acesso ao meio)

MAP Maximum a posteriori probability (maxima probabilidade a pos-

teriori)

MIMO Multiple-input and multiple-output

mMTC Massive machine-type communications (comunicacoes do tipo

maquina densa)

OFDM Orthogonal frequency division multiplexing (multiplexacao por

divisao em frequencias ortogonais)

PAPR Peak to average power ratio (razao entre as potencias de pico e

media)

QoS Quality of service (qualidade de servico)

SUCRe Strongest user collision resolution (resolucao de colisoes pelo

usuario mais forte)

TCC Trabalho de conclusao de curso

UFMC Universal-filtered multicarrier (modulacao multiportadora por

filtragem universal)

URLLC Ultra reliable low latency communications (comunicacoes de alta

confiabilidade e baixa latencia)

V2V Vehicle-to-vehicle communications (comunicacoes entre veıculos)

WF Algoritmo de water-filling

Convencoes e Notacoes

Durante o trabalho serao adotadas as seguintes convencoes e notacoes ma-

tematicas:

Letras minusculas em negrito representam vetores coluna;

Letras maiusculas em negrito representam matrizes;

(·)T Operador de transposicao;

(·)H Operador de Hermitiano (conjugacao e transposicao);

‖ · ‖0 Operador que retorna o numero de elementos nao-nulos do vetor

de entrada (pseudo-norma `0);

‖ · ‖p Operador de norma `p;

∈ Relacao de pertinencia entre elemento e conjunto;

R+ Conjunto dos numero reais nao-negativos;

C Conjunto dos numero complexos;

O{·} Operador retorna o comportamento assintotico da funcao de en-

trada;

Lista de Sımbolos

Capıtulo 1.1

(∆f)c Banda de coerencia do canal;

τmax Maximo espalhamento temporal do canal;

N Numero total de subcanais OFDM;

s Vetor de sımbolos OFDM transmitidos;

x IFFT do vetor de sımbolos OFDM transmitidos s;

n Vetor de ruıdo aditivo;

µ+ 1 Comprimento em sımbolos da resposta impulsiva do canal;

H Matriz circular com a resposta impulsiva do canal;

y Sinal OFDM recebido no no central;

Q Matriz que implementa a FFT;

r FFT do sinal OFDM recebido no no central s;

H Matriz diagonal com a resposta em frequencia do canal;

z FFT do vetor de ruıdo n.

Capıtulo 1.2

y Sinal recebido no no central durante o perıodo de contencao;

A Matriz contendo as sequencias piloto de todos os terminais da

celula;

x Vetor contendo os coeficientes de canal dos terminais ativos e

entradas nulas para os terminais inativos durante o perıodo de

contencao;

z Vetor de ruıdo aditivo;

x Estimativa do vetor x;

ε Parametro que controla o maximo erro de reconstrucao tolerado

na estimacao de x pela pseudo-norma `0;

λ Fator de regularizacao no problema de otimizacao basis pursuit

denoising.

1

1 Introducao

Os principais desafios no desenvolvimento de redes de comunicacao de quinta

geracao (5G), cuja implementacao esta prevista para o ano de 2020, incluem o au-

mento do volume de dados trafegados por area em 1000 vezes, um crescimento de

ate 100 vezes no numero de dispositivos conectados e na taxa de dados oferecida

ao usuario final, alem de uma reducao na latencia ponto-a-ponto e no consumo

de bateria por dispositivos de baixa potencia (GUPTA; JHA, 2015). Em suma,

espera-se alcancar ganhos elevados no ponto de vista de capacidade e confiabili-

dade, aumentando a qualidade de servico (QoS - quality of service) e mantendo o

nıvel de consumo energetico e custo da estrutura de rede proximos ao da geracao

anterior. Estas metas ambiciosas foram tracadas com a finalidade de atender o

numero crescente de dispositivos conectados com taxas razoaveis, alem de suprir

as necessidades dos servicos emergentes, e.g. dispositivos de internet das coisas

(IoT - internet of things) e veıculos autonomos (V2V - vehicle-to-vehicle commu-

nications), utilizando uma estrutura sustentavel do ponto de vista ambiental e

com custo equilibrado.

Neste sentido, as pesquisas concentram-se no estudo das tecnologias capa-

zes de viabilizar os diferentes servicos atendendo aos seus requisitos especıficos

de forma eficiente. Os trabalhos com maior destaque envolvem o projeto de

transceptores massive MIMO (multiple-input and multiple-output), esquemas de

modulacao multiportadora baseados em FBMC (filter bank multicarrier), radio

cognitivo (CR - cognitive radio), transmissao com ondas milimetricas e comu-

nicacao utilizando luz no espectro visıvel.

O esquema de modulacao OFDM (orthogonal frequency division multiplexing)

faz parte do legado das redes 4G, estando presente nos padroes 3GPP LTE e IEEE

802.11. As principais vantagens desta tecnica sao a implementacao simples com

os algoritmos FFT/IFFT (fast Fourier transform), a imunidade a interferencia

intersimbolica pelo uso do prefixo cıclico e o aumento da eficiencia espectral com

a sobreposicao de ate 50% das subportadoras. Apesar de suas caracterısticas

favoraveis para a transmissao sem-fio, o OFDM apresenta uma grande emissao

1 Introducao 2

fora de banda, que leva ao emprego de uma grande parcela do espectro do sistema

como banda de guarda. Alem disso, a ortogonalidade entre as subportadoras e

garantida por requisitos rigorosos de sincronia entre o transmissor e receptor,

que exigem um overhead de sinalizacao excessivo, dificultando principalmente a

implementacao do uplink em esquemas de multiplo acesso.

Ainda que o OFDM possua limitacoes, este esquema de modulacao perma-

nece como potencial candidato a integrar solucoes de redes de comunicacao 5G

(FEMENIAS et al., 2017). Por outro lado, buscando aproveitar os benefıcios da mo-

dulacao multiportadora e minimizar os pontos negativos do OFDM para as redes

da geracao futura, tambem estao sendo consideradas tecnicas como o f-OFDM

(filtered OFDM), o UFMC (universal-filtered multicarrier) e o FBMC (filter bank

multicarrier).

Alem do aumento da eficiencia espectral, uma preocupacao no desenvolvi-

mento das redes 5G envolve o controle de acesso, i.e. a camada MAC (medium

access control). As caracterısticas dos servicos para atender os dispositivos do

tipo maquina (mMTC - massive machine-type communications) e as aplicacoes

que exigem alta confiabilidade e baixa latencia (URLLC - ultra reliable low latency

communications) nao permitem o uso de tecnicas centralizadas para o controle

de acesso. Portanto, e necessario desenvolver protocolos eficientes para garan-

tir o acesso dos terminais com mınimo overhead e, no caso do servico mMTC,

focados em atender populacoes densas de dispositivos com baixa capacidade de

processamento.

As solucoes que mais se adequam as necessidades para a camada MAC sao os

protocolos de acesso aleatorio e os de acesso nao-ortogonal. Na primeira classe,

os terminais decidem de forma autonoma e descentralizada iniciar o acesso ao

recurso disponıvel (e.g. sequencia piloto), a partir de um conjunto de recursos

ortogonais, enquanto que, no segundo caso, cada terminal possui um recurso de

acesso exclusivo (e.g. sinal de assinatura) nao-ortogonal aos dos demais nos.

Esta monografia de trabalho de conclusao de curso (TCC) tem como obje-

tivo apresentar tres estudos envolvendo tecnologias relevantes para as redes da

quinta geracao. Os dois primeiros tratam do problema alocacao de potencia e

bits no downlink de um esquema multiportadora de multiplo acesso baseado em

OFDM, discutindo o algoritmo de bit-loading de Hughes-Hartogs e solucoes para

a reducao de sua complexidade computacional. Ja o terceiro esta relacionado

com o acesso de terminais no cenario mMTC, trazendo uma analise exaustiva

de um esquema para deteccao de atividade dos dispositivos utilizando o algo-

1.1 Esquema de Modulacao OFDM 3

ritmo AMP (approximate message passing), adotado em um protocolo de acesso

nao-ortogonal.

A seguir, sera apresentada uma descricao dos principais aspectos do esquema

de modulacao OFDM. Depois, sera discutido o estado da arte dos protocolos de

acesso, com enfase nos protocolos nao-ortogonais.

1.1 Esquema de Modulacao OFDM

O esquema de modulacao OFDM e uma tecnica de transmissao que oferece

benefıcios para operacao em canais seletivos em frequencia. Seu princıpio base

consiste na divisao da banda de operacao do sistema em N subportadoras ortogo-

nais entre si com largura de banda inferior a banda de coerencia de canal (∆f)c.

Dessa forma, todos os subcanais sao planos no domınio da frequencia, permitindo

a equalizacao de cada um deles utilizando um filtro de tap unico no receptor.

Alem de combater a seletividade do canal, o OFDM elimina a interferencia

intersimbolica utilizando um intervalo de guarda denominado prefixo cıclico. O

prefixo cıclico consiste em uma redundancia com duracao superior ao maximo

espalhamento temporal do canal (τmax) imputada no inıcio de cada sımbolo pelo

transmissor. Durante o processamento do receptor esta redundancia e descar-

tada, eliminando qualquer perturbacao causada pelos sımbolos recebidos anteri-

ormente. Apesar de cancelar a interferencia entre os sımbolos (ISI - inter-symbol

interference), o prefixo cıclico reduz a eficiencia espectral do sistema, uma vez

que seu conteudo nao representa dados uteis.

Os sistemas OFDM foram concebidos sob requisitos estritos de ortogonali-

dade nos domınios de tempo e da frequencia para garantir estruturas de trans-

missor e receptor com baixa complexidade (ROHLING, 2011). A Figura 1.1 ilustra

a arquitetura digital de transmissao e recepcao OFDM baseada nos algoritmos

IFFT/FFT. Durante a primeira etapa do transmissor, a sequencia de bits e sub-

metida a um conversor serial-paralelo que a divide em diversas sequencias de

comprimento menor. As sequencias produzidas sao moduladas de forma indepen-

dente em subcanais paralelos. Apos a modulacao das subportadoras, uma IFFT

e realizada, seguida do conversor paralelo-serial para obter-se o sinal OFDM. Por

fim, o prefixo cıclico e acrescentado, replicando um trecho do perıodo final do

sinal OFDM no seu inıcio. No esquema de recepcao, inicialmente e executada

uma filtragem para eliminar o prefixo cıclico e a conversao serial-paralelo. De-

pois, sao realizadas a FFT e o processo de equalizacao. Ao final, os sinais de cada


subportadora sao demodulados e a sequencia original e recuperada aplicando-os

ao conversor paralelo-serial (GOLDSMITH, 2005).

Receptor

Transmissor

s

ModulaçãoConversor serial-paralelo

x

IFFT Conversorparalelo-serial

Inclusão doprefixo cíclico

Canalh(t)

x(t)Conversor

D/A

s

Demodulação FFT eequalização

Conversorserial-paralelo

Remoção doprefixo cíclico

ConversorA/D

y(t)

n(t)

Seq. estimada

Seq. de bits

Conversor paralelo-serial

⋮ ⋮ ⋮

⋮⋮⋮

Figura 1.1: Implementacao digital do transmissor e receptor OFDM em bandabase baseada nos algoritmos FFT/IFFT.

A representacao do sinal OFDM pode ser simplificada utilizando sua notacao

matricial no domınio da frequencia. Adotaremos N como o numero total de sub-

portadoras, s = [s[0], s[1], . . . , s[N − 1]]T o vetor de sımbolos transmitidos, x =

[x[0], x[1], . . . , x[N−1]]T o resultado da IFFT do vetor s e n = [n[0], n[1], . . . , n[N−1]]T o vetor de ruıdo aditivo. O efeito do canal no tempo pode ser representado

pela matriz circular H ∈ CN×N contendo sua resposta impulsiva h[0], . . . , h[µ]

com o comprimento de µ+ 1 sımbolos,

H =

h[0] h[1] · · · h[µ] 0 · · · 0 0

0 h[0] · · · h[µ− 1] h[µ] · · · 0 0...

. . . . . . . . . . . . . . . . . ....

h[2] h[3] · · · h[µ] 0 · · · h[0] h[1]

h[1] h[2] · · · h[µ− 1] h[µ] · · · 0 h[0]

(1.1)

Adotando a representacao matricial, o sinal recebido no domınio do tempo

ignorando as amostras do prefixo cıclico, que sofrem de ISI, e representado por:

y = Hx + n (1.2)

Se considerarmos Q a matriz N × N que implementa a FFT, podemos obter a


representacao do sinal recebido no domınio da frequencia,

r = Qy

= QHx + Qn

= QHQHs + Qn

= Hs + z (1.3)

sendo H a matriz diagonal contendo as amostras da resposta em frequencia do

canal e z a FFT do vetor de ruıdo. A expressao 1.3 ilustra bem o conceito

dos subcanais paralelos do OFDM, onde cada linha de r consiste no sımbolo

transmitido, multiplicado pelo coeficiente de canal da sua respectiva subportadora

e um termo de ruıdo aditivo.

O fato das subportadoras OFDM serem moduladas de forma independente

permite a adaptacao do tipo e da ordem de modulacao de acordo com suas

condicoes e os recursos disponıveis (e.g. potencia, banda), visando otimizar

metricas de performance do sistema (e.g. eficiencia espectral, eficiencia energetica).

Alem disso, em esquemas de multiplo acesso ha a necessidade de determinar quan-

tas e quais portadoras serao alocadas para cada terminal. O desenvolvimento de

tecnicas para a alocacao eficiente destes recursos e de extrema relevancia, pois

apresenta como vantagens a reducao do custo de operacao dos sistemas e do

volume de processamento nas estacoes radio-base.

Um dos principais problemas enfrentados pelos sistemas OFDM e a elevada

razao entre as potencias de pico e media (PAPR - peak to average power ra-

tio). Esta caracterıstica requer amplificadores altamente lineares ou a adocao

de tecnicas para reducao da PAPR, que oferecem uma melhora na razao das

potencias em troca de degradacao da qualidade do sinal OFDM. Outras limitacoes

expressivas do OFDM envolvem sua forte dependencia de sincronizacao no tempo

e na frequencia, que leva a alta sensibilidade ao espalhamento Doppler e ao ruıdo

de fase dos osciladores no transmissor e receptor (FAZEL; KAISER, 2003).

Buscando aproveitar os benefıcios da modulacao multiportadora e minimizar

as limitacao do OFDM para as redes da geracao futura, diversos autores apre-

sentaram esquemas que incluem outras tecnicas. Um deles, o f-OFDM, preve

a divisao do espectro disponıvel em sub-bandas onde sao alocados sub-sistemas

OFDM, que podem apresentar configuracoes diferentes entre si para acomodar os

servicos do 5G. O sinal de cada sub-sistema e filtrado de forma independente com

um filtro devidamente projetado para reduzir a emissao fora de banda (ZHANG

et al., 2015). Alem do f-OFDM, tecnicas de modulacao multiportadora como o

1.2 Protocolos de Acesso 6

UFMC e o FBMC sao fortes candidatas a tornarem-se padroes do 5G. Por se

tratarem de esquemas que compartilham diversas caracterısticas com o OFDM,

tecnicas de alocacao de recursos e scheduling bem consolidadas podem ser facil-

mente implementadas nestes novos sistemas.

1.2 Protocolos de Acesso

Os sistemas de comunicacao sem-fio geralmente apresentam configuracao em

estrela semelhante a ilustrada na Figura 1.2, em que os terminais secundarios

tem conexao intermediada por um no central, e.g. estacao radio-base ou ponto

de acesso. O no central deve possuir capacidade de processamento de sinais

suficiente para executar acoes como a estimacao do enlace dos dispositivos conec-

tados, a alocacao dos blocos de recursos do sistema e a modulacao/demodulacao

das mensagens trocadas. Esta arquitetura de controle da rede centralizada foi

suficiente para o sucesso dos sistemas da geracao anterior. Entretanto, para o

contexto 5G, a quantidade excessiva de tarefas atribuıdas ao no central e um

grande limitante para os servicos mMTC e URLLC.

Figura 1.2: Sistema de comunicacao unicelular tıpico, em configuracao deestrela.

Quando um terminal deseja acessar a rede, ele inicia uma sequencia de pro-

cessos estabelecidos pelo protocolo de acesso, que pode ser centralizado ou dis-

tribuıdo. Responsavel pelo controle da camada MAC, o protocolo de acesso

define sistematicamente as acoes tomadas pelos nos primario e secundario para

a confirmacao do acesso, a reserva dos blocos de recurso para a transmissao e a

resolucao de possıveis colisoes. Em redes onde este controle de forma centrali-

zada gera overhead de sinalizacao excessivo, apresenta tempo de processamento

muito longo, ou nao pode ser implementado por restricoes de complexidade do no

central, a solucao mais natural e sua substituicao por um protocolo de acesso dis-


tribuıdo. Nele, o no central nao regula diretamente o acesso dos nos secundarios

ao meio de transmissao, sendo esta tarefa encarregada aos proprios terminais.

1.2.0.1 Protocolos de Acesso Grant-based e Grant free

Podemos dividir os protocolos de acesso distribuıdos naqueles que sao ba-

seados em autorizacao (grant-based) e os livres de autorizacao (grant free). Na

primeira categoria, o conjunto de mensagens e constituıdo por um sinal inicial de

requisicao enviada pelo terminal, seguida de uma mensagem de autorizacao do

no central, para entao ocorrer a transmissao do payload do no secundario. Esta

classe inclui em sua maioria protocolos aleatorios, como o SUCRe (strongest user

collision resolution) (BJORNSON et al., 2017). No caso dos protocolos livres de

autorizacao, a requisicao de acesso e transmitida simultaneamente com o payload

do terminal. Desse modo, caso o acesso seja valido, nao ha necessidade de troca

de mensagens adicionais para que o no central obtenha o payload do secundario.

A Figura 1.3 apresenta o esquema de troca de mensagens de um protocolo ba-

seado em autorizacao e outro livre de autorizacao. Fica evidente que o protocolo

livre de autorizacao necessita de uma quantidade menor de troca de mensagens,

implicando em um overhead de sinalizacao e latencia tambem menores. Porem,

a adocao de protocolos livres de autorizacao em cenarios com populacoes densas

como o mMTC exige o uso de metodos de acesso nao-ortogonais, em que a con-

taminacao intracelular e/ou intercelular dos sinais piloto de todos os terminais

ativos ocorre frequentemente.

Terminal

1. Handshake

2. Resposta de acesso

3. Requisição de acesso

4. Resposta de conexão

Nó central Terminal

1. Dados + metadados

2. Acknowledgement

Nó central

Protocolo grant-based Protocolo grant-free

Figura 1.3: Lista de mensagens do protocolo grant-based SUCRe (esquerda) eum protocolo de acesso grant-free nao-ortogonal (direita).


1.2.1 Protocolos de Acesso Nao-Ortogonal

Os protocolos de acesso nao-ortogonal sao uma alternativa quando nao ha

disponibilidade de recursos ortogonais para todos os terminais, possibilitando

a atribuicao de assinaturas unicas para cada um deles. Entretanto, a falta de

ortogonalidade provoca contaminacao de piloto intercelular ou mesmo intrace-

lular, principalmente em cenarios mMTC overcrowded, entre todos os terminais

que transmitem num dado perıodo de contencao, impedindo o uso de tecnicas

convencionais para a deteccao de atividade e estimacao de canal.

No contexto mMTC, uma forma de acesso nao-ortogonal envolve a formulacao

dos problema de deteccao de terminais ativos e estimacao de canal como a recons-

trucao de sinais esparsos. Considerando um sistema celular em que o no central

e os nos secundarios sao equipados com uma unica antena cada, o sinal recebido

na estacao radio-base durante um perıodo de contencao e representado como:

y = Ax + z (1.4)

em que A e uma matriz contendo todas as sequencias piloto da celula, x e um

vetor contendo os coeficientes de canal dos dispositivos ativos e entradas nulas

para os inativos, e z e o vetor de ruıdo aditivo.

O problema de recuperacao de x, que tem caracterıstica esparsa devido ao

comportamento esporadico dos terminais, a partir de y e A pode ser formulado

de acordo com:

x = arg minx‖x‖0, sujeito a ‖y −Ax‖22 < ε (1.5)

sendo ‖ ·‖0 a funcao que retorna a quantidade de elementos nao-nulos do vetor de

entrada, ‖x‖p = (∑

n |xn|p)1/p , p = 1, 2, ... e ε ∈ R+ e um parametro proporcional

ao maximo erro de reconstrucao tolerado. Esta formulacao para o problema de

recuperacao do sinal original nao e convexa, impedindo o uso de tecnicas exatas

de otimizacao para soluciona-lo. Como alternativa, e possıvel recorrer a uma

relaxacao convexa do problema original, conhecida como basis pursuit denoising

(BPDN):

x = arg minx‖y −Ax‖22 + λ‖x‖1 (1.6)

onde λ ∈ R+ e o fator de regularizacao, que controla o compromisso entre o erro

de reconstrucao e a esparsidade do vetor solucao.

A solucao otima para o problema BPDN pode ser obtida adotando-se metodos

convencionais de otimizacao convexa, e.g. metodos de ponto-interior e metodos


de gradiente (TROPP; WRIGHT, 2010), as custas de um alto custo computacional.

Por este motivo, diversas pesquisas tem apresentado solucoes eficientes, porem

sub-otimas, para solucionar (1.6), como por exemplo os metodos de greedy pursuit

e confinamento iterativo (MALEKI; BARANIUK, 2011).

Uma solucao que se destaca por seu baixo custo computacional e alta capa-

cidade de reconstrucao e o algoritmo de approximate message passing (AMP).

Originalmente apresentado em (DONOHO; MALEKI; MONTANARI, 2009), com sua

versao para valores complexos derivada em (MALEKI et al., 2013), este algoritmo

vem sendo adotado por diversos autores para a solucao dos problema de deteccao

e estimacao de canal em terminais mMTC, como pode ser visto em (CHEN; SOH-

RABI; YU, 2018; LIU; YU, 2018a, 2018b; SENEL; LARSSON, 2018).

No apendice C abordamos o problema de deteccao de atividade de dispositivos

em sistemas mMTC com protocolos de acesso livre de concessao nao-ortogonais.

A arquitetura analisada para detectar a atividade do terminal e constituıda por

uma etapa de estimacao a partir do algoritmo AMP e o soft thresholding denoiser,

bem como uma etapa de deteccao aplicando a regra de decisao de maxima pro-

babilidade a posteriori (MAP - maximum a posteriori probability). Expressoes

analıticas para o desempenho do detector foram desenvolvidas considerando dois

modelos de canal diferentes (AWGN e Rayleigh), alem da perda de percurso.

Foi demonstrado que no contexto 5G mMTC, a regra de decisao MAP pode ser

implementada com baixa complexidade, avaliando adequadamente o limite de

decisao.

10

2 Resultados

Os resultados deste trabalho de conclusao de curso serao apresentados na

forma de tres artigos cientıficos, conforme Apendice A, B e C. Os dois primeiros

estao relacionados ao estudo da alocacao de potencia e de bits em sistemas que

adotam modulacao OFDM, enquanto o terceiro paper consiste em uma analise

relativa a um esquema de deteccao de atividade de terminais adotado em um

protocolo de acesso nao-ortogonal focado no servico mMTC. Os trabalhos, em

ordem cronologica de concepcao e construcao, sao:

[A] Bit-Loading e a Capacidade de Sistemas OFDM

Artigo de conferencia apresentado e publicado no SBrT 2016 (Simposio

Brasileiro de Telecomunicacoes)

Categoria: TIC-SBrT – trabalho de iniciacao cientıfica do SBrT

Autores: Joao Henrique de Souza, Lucas Dias Hiera Sampaio, Taufik Abrao

[B] Hybrid Hughes-Hartogs power allocation algorithms for OFDMA systems

Artigo publicado na revista IET Signal Processing

ISSN: 1751-9675 (Print); 1751-9683 (Online) em 09 Outubro de 2018

DOI: 10.1049/iet-spr.2018.5080

Autores: Joao Henrique de Souza, Taufik Abrao

[C] Approximate Message-Passing Algorithm for mMTC Terminals Activity De-

tection

Autores: Joao Henrique de Souza, Taufik Abrao

Manuscrito em processo de submissao

No trabalho [A] foi realizado um estudo das solucoes de water-filling (WF) e

o algoritmo de Hughes-Hartogs (HH) para o problema de maximizacao da taxa

total do sistema com limitacao na potencia. Apos a formulacao do problema de

otimizacao e a caracterizacao da solucao otima WF e do algoritmo de HH, foram

realizadas simulacoes de Monte-Carlo para comparar os valores de capacidade

atingidos por cada uma das solucoes.

2 Resultados 11

No trabalho [B] foi dada continuidade a analise do algoritmo HH, reali-

zando uma analise de sua complexidade computacional, combinando-o com outras

tecnicas tendo em vista a melhorar o compromisso desempenho versus comple-

xidade. Neste sentido, foi proposto um metodo para reducao de complexidade

baseado em agrupamento que aproveita a correlacao apresentada pelas subporta-

doras OFDM em determinadas condicoes.

Por fim, no trabalho [C] foi realizada uma analise exaustiva do algoritmo

AMP com soft thresholding denoising na solucao do problema de deteccao de

terminais ativos no cenario 5G mMTC. Foram desenvolvidas expressoes analıticas

para as probabilidades de erro de deteccao e falso alarme, caracterizacao de um

esquema de decisao que adota o criterio de maxima probabilidade a posteriori.

Os resultados analıticos foram validados a partir de simulacoes numericas de

Monte-Carlo.

12

3 Conclusao

Neste trabalho de conclusao de curso de graduacao em Engenharia Eletrica foi

desenvolvido um estudo aprofundado sobre o algoritmo de bit-loading de Hughes-

Hartogs tendo em vista alocar otimamente tanto a potencia disponıvel quanto os

numero de bits em sistemas OFDM. Adicionalmente, uma abalizada analise foi

desenvolvida, referente a um esquema de deteccao de atividade de dispositivos

baseado no algoritmo AMP voltado para o servico mMTC em sistema 5G. Assim,

no trabalho [A] foi abordada a formulacao do problema de maximizacao da taxa de

sistemas OFDM com restricao de potencia, sendo implementados e comparados

numericamente a solucao otima, o algoritmo classico de water-filling (WF), e

o algoritmo modificado de HH, o qual e sub-otimo porem factıvel do ponto de

vista de implementacao computacional. Apos a caracterizacao das duas tecnicas,

foram realizadas simulacoes de Monte-Carlo objetivando determinar a fracao da

capacidade otima alcancada pelo algoritmo de HH.

O trabalho [B] foi dedicado exclusivamente a analise aprofundada do algo-

ritmo HH, sendo realizado um levantamento de sua complexidade computacional

e a proposicao de metodos para reduzi-la. Concluiu-se que a tecnica de HH pos-

sui uma complexidade da ordem de O(N2 log(N)). Os mecanismos de reducao

de complexidade investigados foram o calculo de vetor de bits inicial utilizando

o truncamento da solucao WF, a atualizacao de multiplas subportadoras por

iteracao, e um algoritmo de agrupamento que explora a correlacao existente en-

tre os subcanais adjacentes sob determinadas condicoes de maximo espalhamento

temporal do canal. Observou-se que o segundo mecanismo investigado oferece

uma grande reducao no numero de iteracoes do algoritmo HH em troca de uma

degradacao marginal de capacidade. O algoritmo de agrupamento tambem ofe-

rece este benefıcio, desde que o parametro que controla a criacao de grupos seja

ajustado de acordo com as condicoes do cenario. Por fim, a solucao do vetor

de alocacao inicial aumenta o numero de iteracoes necessario para convergencia,

mas resulta em um valor de capacidade superior ao atingido pelo algoritmo HH

original.

3 Conclusao 13

Por fim, o trabalho [C] trata de um esquema de deteccao de atividade de

terminais constituıdo por uma etapa de estimacao com o algoritmo AMP seguida

de uma etapa de deteccao adotando a regra de decisao MAP. No desenvolvi-

mento, foi apresentada uma analise exaustiva do algoritmo AMP utilizando a

funcao de soft thresholding denoising, explorando a influencia do limiar da funcao

de denoising e demonstrando o calculo do erro medio quadratico da estimativa

utilizando a abordagem de evolucao de estados. Em seguida, a regra de de-

cisao MAP foi tratada, mostrando que ela pode ser implementada com baixa

complexidade com um limiar de decisao devidamente projetado. Foram desen-

volvidas expressoes analıticas para as probabilidades de nao deteccao e alarme

falso do esquema proposto, que foram validadas a partir de simulacoes Monte-

Carlo. Em conclusao, observou-se que o esquema de deteccao investigado possui

caracterısticas favoraveis para atender o servico mMTC, apresentando boas taxas

de probabilidade de deteccao e sendo escalavel com a potencia e o comprimento

das assinaturas dos terminais.

14

Bibliografia

BJORNSON, E.; CARVALHO, E. de; SØRENSEN, J. H.; LARSSON, E. G.;POPOVSKI, P. A random access protocol for pilot allocation in crowded massiveMIMO systems. IEEE Transactions on Wireless Communications, v. 16,n. 4, p. 2220–2234, April 2017. ISSN 1536-1276.

CHEN, Z.; SOHRABI, F.; YU, W. Sparse activity detection for massive connec-tivity. IEEE Transactions on Signal Processing, v. 66, n. 7, p. 1890–1904,April 2018. ISSN 1053-587X.

DONOHO, D. L.; MALEKI, A.; MONTANARI, A. Message-passing algorithmsfor compressed sensing. Proceedings of the National Academy of Sciences,National Academy of Sciences, v. 106, n. 45, p. 18914–18919, 2009. ISSN 0027-8424. Disponıvel em: <http://www.pnas.org/content/106/45/18914>.

FAZEL, K.; KAISER, S. Multi-Carrier and Spread Spectrum Systems.New York, NY, USA: John Wiley & Sons, Inc., 2003. ISBN 0470848995.

FEMENIAS, G.; RIERA-PALOU, F.; MESTRE, X.; OLMOS, J. J. Down-link scheduling and resource allocation for 5G MIMO-multicarrier: OFDM vsFBMC/OQAM. IEEE Access, v. 5, p. 13770–13786, 2017. ISSN 2169-3536.

GOLDSMITH, A. Wireless Communications. : Cambridge University Press,2005.

GUPTA, A.; JHA, R. K. A survey of 5G network: Architecture and emergingtechnologies. IEEE Access, v. 3, p. 1206–1232, 2015.

LIU, L.; YU, W. Massive connectivity with massive MIMO part I: Device activitydetection and channel estimation. IEEE Transactions on Signal Processing,v. 66, n. 11, p. 2933–2946, June 2018. ISSN 1053-587X.

LIU, L.; YU, W. Massive connectivity with massive MIMO part II: Achievablerate characterization. IEEE Transactions on Signal Processing, v. 66, n. 11,p. 2947–2959, June 2018. ISSN 1053-587X.

MALEKI, A.; ANITORI, L.; YANG, Z.; BARANIUK, R. G. Asymptotic analysisof complex LASSO via complex approximate message passing (CAMP). IEEETransactions on Information Theory, v. 59, n. 7, p. 4290–4308, July 2013.ISSN 0018-9448.

MALEKI, A.; BARANIUK, R. Least favorable compressed sensing problems forfirst-order methods. In: 2011 IEEE International Symposium on Informa-tion Theory Proceedings, 2011. p. 134–138. ISSN 2157-8117.

ROHLING, H. (Ed.). OFDM: Concepts for Future Communication Sys-tems. : Springer-Verlag Berlin Heidelberg, 2011. ISBN 978-3-642-17495-7.

Bibliografia 15

SENEL, K.; LARSSON, E. G. Joint user activity and non-coherent data detectionin mMTC-enabled massive MIMO using machine learning algorithms. In: WSA2018; 22nd International ITG Workshop on Smart Antennas, 2018. p. 1–6.

TROPP, J. A.; WRIGHT, S. J. Computational methods for sparse solution oflinear inverse problems. Proceedings of the IEEE, v. 98, n. 6, p. 948–958, June2010. ISSN 0018-9219.

ZHANG, X.; JIA, M.; CHEN, L.; MA, J.; QIU, J. Filtered-OFDM - enablerfor flexible waveform in the 5th generation cellular networks. In: 2015 IEEEGlobal Communications Conference (GLOBECOM), 2015. p. 1–6.

16

Apendice A -- Bit-Loading e a

Capacidade de Sistemas OFDM

XXXIV SIMPÓSIO BRASILEIRO DE TELECOMUNICAÇÕES - SBrT2016, 30 DE AGOSTO A 02 DE SETEMBRO, SANTARÉM, PA

Bit-Loading e a Capacidade de Sistemas OFDMJoão Henrique de Souza, Lucas Dias Hiera Sampaio, Taufik Abrão

Resumo— Este artigo discute dois algoritmos clássicos parasolucionar o problema de maximização da capacidade no down-link de sistemas OFDM (orthogonal frequency-division multi-plexing), incluindo a diferença de desempenho entre as duasabordagens condicionados por estes algoritmos: uma teórica,utilizando a solução clássica de water-filling e a outra, de cunhoprático, utilizando o algoritmo de Hughes-Hartogs. Resultadosnuméricos de simulação considerando parâmetros dos sistemasatuais do Long-Term Evolution (LTE) são apresentados ao final deforma a ilustrar a diferença prática entre abordagem contínuae discreta sob a perspectiva das tecnologias atuais.

Palavras-Chave— orthogonal frequency-division multiplexing(OFDM), alocação de recursos, bit-loading

I. INTRODUÇÃO

No cenário atual de telecomunicações há uma grande de-manda pela melhor utilização dos recursos uma vez que estessão escassos e a demanda cresce a cada ano. Neste sentido,muitos pesquisadores trabalham na busca de um gerenci-ador de recursos para sistemas sem-fio que permita atenderas necessidades e expectativas de usuários, companhias detelecomunicações e do meio ambiente. Todavia, grande partedos métodos propostos são, do ponto de vista matemático,contínuos, portanto, não representam de forma fidedigna ossistemas reais.

A fim de averiguar quão distante o modelo teórico seencontra do prático, este paper analisará o desempenho de umalgoritmo de bit-loading em relação à solução contínua ótimado problema de maximização da capacidade no downlink desistemas OFDM para um cenário típico da quarta geração desistemas de telecomunicações (4G).

Organização: na Seção II, são definidos os sistemas OFDMe respectiva capacidade com gap de SNR. Na Seção III éformulado o problema da capacidade a ser analisado, bemcomo as respectivas soluções estudadas de water-filling (WF)e de Hughes-Hartogs (HH). Por fim, a Seção IV discute osresultados numéricos de simulação obtidos.

II. CAPACIDADE OFDM COM Gap DE SNR

OFDM, do inglês orthogonal frequency-division multiplex-ing, é um esquema de modulação multiportadora utilizadofrequentemente em sistemas de comunicação sujeitos a canaisguidados ou não-guiados. De forma geral, neste esquemaum canal é dividido em subcanais com banda menor cujasfrequências são ortogonais entre si, de modo que cada subcanalapresente resposta em frequência plana (não seletiva em fre-quência). Desse modo, a transmissão dos símbolos é realizada

Taufik Abrão and João Henrique de Souza are with Electrical En-gineering Department, State University of Londrina, PR, Brazil (e-mail:[email protected], [email protected]).

Lucas Dias Hiera Sampaio is with the Computer Science Department andElectrical Engineering Department, State University of Londrina, PR, Brazil(e-mail: [email protected]).

paralelamente, sendo possível tanto distribuir os bits de umapalavra binária em diversos subcanais, como também alocaros subcanais para diferentes usuários do sistema. Uma dasprincipais vantagens do OFDM é sua baixa degradação pelainterferência intersimbólica, obtida pela condição da largurade banda dos subcanais (B) resultar menor que a banda decoerência do canal, i.e., B ≪ (∆B)C , e a adição de um prefixocíclico nos símbolos transmitidos com duração maior queespalhamento efetivo da resposta do canal, i.e., TCP > τrms.

Em um sistema OFDM, a capacidade total pode ser calcu-lada pela soma das capacidades de cada subcanal pela equaçãode Shannon:

Ci =

N∑

i=1

B log2(1 + Piδi) [bits/s], (1)

sendo N número de sub-portadoras do sistema OFDM, δia relação sinal-ruído (SNR) normalizada recebida em cadasubcanal, definida por hi/(N0B), onde hi é o ganho doi-ésimo subcanal e N0 é a densidade espectral do ruído.No cálculo do valor de capacidade acima assume-se que aprobabilidade de erro de bit (BER) resulte nula, condiçãoque não pode ser alcançada em um cenário real de interesseprático. Por este motivo é necessário introduzir na equação deShannon o gap de SNR, um fator que depende da BER, damargem de operação e do ganho de codificação do sistema[1]. A equação da capacidade de Shannon com o gap de SNRΓ, denominada aproximação com gap de SNR, é escrita naforma:

Ci =

N∑

i=1

B log2

(1 +

PiδiΓ

)[bits/s]. (2)

A dependência do gap de SNR Γ com a BER é calculadautilizando a expressão

Γ =1

3

[Q−1

(BER

4

)]2[dB], (3)

sendo a função Q(a) = 1− Pr(x < a), e x ∼ N (0, 1).

III. FORMULAÇÃO DO PROBLEMA E POSSÍVEIS SOLUÇÕES

O problema estudado consiste na maximização da capaci-dade total do sistema com uma limitação de potência definidapor Pmax. Matematicamente, o problema de otimização podeser enunciado da forma:

maximize

N∑

i=1

bi =

N∑

i=1

log2

(1 +

PiδiΓ

)

sujeito àN∑

i=1

Pi ≤ Pmax. (4)

XXXIV SIMPÓSIO BRASILEIRO DE TELECOMUNICAÇÕES - SBrT2016, 30 DE AGOSTO A 02 DE SETEMBRO, SANTARÉM, PA

Algoritmo WF. O algoritmo water-filling (WF) é a soluçãoótima do ponto de vista da capacidade [2] em função darestrição do recurso potência (ou energia) máxima disponível;a solução WF é formulada a partir da técnica de otimizaçãodos multiplicadores de Lagrange. Assim, dado a formulaçãoem (4), a solução é encontrada calculando o ponto de máximoem

L(Pi) =

N∑

i=1

log2

(1 +

PiδiΓ

)+ λ

(N∑

i=1

Pi − Pmax

), (5)

sendo λ o multiplicador de Lagrange.Após o processo de otimização, verifica-se que a potência

alocada em cada subcanal do sistema segue uma regra dedistribuição water-filling definida pela expressão

Pi = Cλ − Γ

δi, (6)

sendo Cλ uma constante denominada "nível d’água":

Cλ =1

N

(Pmax +

N∑

i=1

Γ

δi

). (7)

Algoritmo de Hughes-Hartogs (HH, 1987-1989) é umatécnica de preenchimento de bits utilizada em sistemas basea-dos em esquemas de transmissão com multiportadora. Seuobjetivo é distribuir a potência disponível entre os subcanaisvisando maximizar a capacidade total do sistema. Este algo-ritmo é classificado como guloso, uma vez que ele procurasoluções locais partindo da premissa de que elas levarão àsolução global do problema [2].

O algoritmo de Hughes-Hartogs calcula o acréscimo docusto em potência para alocar mais um bit nos subcanais,escolhendo sempre aquele que apresenta o menor custo [3].O processo é realizado bit-a-bit até que a potência consumidapelo sistema atinja o máximo estipulado.

O custo em potência P ∗i para a alocação do bit de número

bi no i-ésimo subcanal é calculado pela expressão

P ∗i (bi) = 2bi

Γ

δi. (8)

Com esta expressão, define-se uma matriz do acréscimo decusto com os valores adicionais de potência a serem alocadospara cada subcanal para uma dada quantidade de bits. A partirdesta matriz, realiza-se uma busca de mínimos alocando-se osbits nos subcanais que apresentam menor acréscimo, até queo total de potência alocada atinja o valor máximo do recursodisponível.

IV. RESULTADOS NUMÉRICOS E DISCUSSÃO

O cenário utilizado para simulação das soluções estudadasconsiste em um downlink com dez usuários uniformementedistribuídos ao redor de uma estação rádio-base centrada emuma célula hexagonal com 1 Km de raio. Cada usuário tem12 subcanais OFDM consecutivos disponíveis para recepção;por facilidade de análise, desconsiderou-se mobilidade dosusuários. Foi assumido expoente de perda de percurso igual a4, um valor dentro da faixa recomendada para macrocélulas

urbanas [4]. A condição de recepção considerada não contémlinha de visada, assumindo que os coeficientes de desvanec-imento dos subcanais em termos de amplitude seguem umadistribuição Rayleigh. A Tabela I resume os parâmetros geraisdo sistema, incluindo o número de subcanais N e a largurade banda por subcanal B.

TABELA IPARÂMETROS DO CENÁRIO PROPOSTO PARA AS SIMULAÇÕES.

Parâmetro ValorNúmero de usuários U = 10Número de subcanais N = 120Largura de banda por subcanal B = 15 kHzExpoente de perda de percurso ξ = 4Desvio padrão do sombreamento σshd = 6 dBTaxa de erro de bit máxima BER= 10−7

Potência máxima de transmissão Pmax = 20 W

Com o cenário proposto foram realizadas 104 realizações,alocando-se a potência disponível do sistema com os algorit-mos water-filling e de Hughes-Hartogs. Durante cada uma dassimulações, foram sorteadas as posições dos 10 usuários dentroda célula hexagonal, gerando os seus respectivos coeficientesde canal de acordo com a distribuição escolhida.

Após a execução das simulações, foi verificado que o algo-ritmo de HH atinge em média 73,02% da capacidade alcançadapela solução ótima, calculada pelo algoritmo WF. No melhorcaso, o algoritmo de HH apresentou 81,09% da capacidadeda solução water-filling. Enquanto isto, o pior desempenhoresultou em uma capacidade de 66,83% da solução ótima,conforme observado na Tabela II.

TABELA IIPERCENTUAL DA CAPACIDADE ATINGIDA PELO ALGORITMO DE HH EM

RELAÇÃO À SOLUÇÃO ÓTIMA.

Descrição Capacidade atingidaMelhor desempenho 81,09%

Pior desempenho 66,83%Desempenho médio 73,02%

Em conclusão, este trabalho analisou a solução ótima parao problema de otimização da capacidade em sistemas OFDMcom limitação de potência e uma alternativa eficiente, porémsub-ótima denominada algoritmo de preenchimento de bits(bit-loading) ou algoritmo de Hughes-Hartogs . Os resultadosdas simulações indicaram que o algoritmo de HH alcançouuma faixa de capacidade entre 66,83% e 81,09% daquelesresultados alcançados pela solução ótima WF, atingindo emmédia 73,02% desta capacidade ótima.

REFERÊNCIAS

[1] J. M. Cioffi, “A multicarrier primer,” Nov. 1991.[2] C. M. Akujuobi and J. Shen, “Efficient multi-user parallel greedy bit-

loading algorithm with fairness control for dmt systems,” in GreedyAlgorithms (W. Bednorz, ed.).

[3] L. Z. D. Wang, Y. Cao, “Efficient two-stage discrete bit-loading algo-rithms for ofdm systems,” IEEE Transactions on Vehicular Technology,vol. 59, Sep. 2010.

[4] A. Goldsmith, Wireless Communications. Cambridge University Press,2005.

19

Apendice B -- Hybrid Hughes-Hartogs

power allocation algorithms for

OFDMA systems

IET Signal Processing

Research Article

Hybrid Hughes-Hartogs power allocationalgorithms for OFDMA systems

ISSN 1751-9675Received on 19th April 2018Accepted on 29th May 2018doi: 10.1049/iet-spr.2018.5080www.ietdl.org

João Henrique Inacio de Souza1, Taufik Abrão1 1Electrical Engineering Department, State University of Londrina, Rod. Celso Garcia Cid – PR445, Po. Box 10.011. CEP: 86057-970, Londrina,PR, Brazil

E-mail: [email protected]

Abstract: This work analyses the discrete solution of Hughes-Hartogs (HH) for the transmission rate maximisation problem withpower constraint in the orthogonal frequency division multiplexing access (OFDMA) systems and explores mechanisms toreduce the computational complexity of greedy algorithms. In addition to the solution characterisation, a computationalcomplexity analysis is developed, considering the number of executed operations for running time purpose. Moreover, theauthors have compared the system capacity via the throughput obtained with the HH solution, and its variants combined withthree complexity reduction mechanisms. These tools consist of an initial allocation bit vector calculated by rounding the resultsof the water-filling (WF) solution, the multiple subchannels per iteration updating and the adoption of a subchannel groupingprocedure. Their findings indicate that the update of multiple subchannels and the subcarriers grouping techniques reduce thenumber of iterations required for convergence of the original HH, with some throughput degradation. Also, the bit-allocationmechanism based on the WF is deployed as an alternative to overcome the HH solution, increasing the computationalcomplexity.

1 IntroductionThe orthogonal frequency division multiplexing scheme is analternative for wireless transmission among channels whichsuffering from deep fading. However, dividing the transmissionband into N narrow subchannels generates the optimisationproblem of choosing the suitable power on each subchannel thatmaximises the transmission rate (optimisation criterion).

The rate maximisation problem with power constraints analysedherein was extensively explored in past works, especially in thecontext of the wired discrete multitone (DMT) systems, as well asin the wireless orthogonal frequency division multiplexing access(OFDMA) systems. Particularly, the OFDMA is based on the sameprinciple of dividing the total system bandwidth in shorter flatfading subchannels but sharing such spectral sub-bands resourceswith multiple users.

Associated with these OFDMA features, there is an involvedand intricated resource allocation problem defined by the joint usersubcarrier allocation and the respective subcarrier optimal powerallocation. From different perspectives, the complete optimisationof allocating power, subcarriers and bit-loading in multiuserOFDMA scenarios results in an exponential complexity to achieveoptimality [1–4]. As well known, the optimal solution for thepower allocation problem is the water-filling (WF) solution [5],and optimally explored in [6]. However, this optimal solutionassumes a non-integer number of allocated bits, which is inefficienton practical scenarios. In the other extreme, several sub-optimaljointly iterative methods, such as Dinkelbach, Lagrange dualdecomposition algorithms, integer relaxation subcarriers allocation,subcarriers grouping mechanisms and so forth have been deployed(see [7] and related references inside) aiming at obtainingimplementable resource allocation procedures.

Searching for practical solutions, discrete algorithms classifiedas bit-loading algorithms have been developed in the last decades.The optimal bit-loading solution is the Hughes-Hartogs (HH)algorithm [8], originally proposed for DMT systems. As it isformulated on an exhaustive search procedure, the HH solutiondemands a lot of computational resources to be implemented. Tominimise the computational complexity on discrete bit allocation,works such as [9] have proposed efficient solutions exploring thesystem margin to compute the result with less iterations.

Besides the rate maximisation with power constraint, otherworks have studied resource allocation problems with constraintsof different nature. Past works such as [10, 11] have proposedsolutions for the power allocation problem admitting simultaneousconstraints, including power, bit error rate (BER) and modulationorder.

Sampaio et al. [12] presented a resource allocation algorithmbased on a non-cooperative game to distribute power andsubcarriers in an OFDMA LS-MIMO system, aiming to maximisethe spectral efficiency of an inter-cell interference environment.The found solution combines a greedy procedure for subcarriersallocation and the classical WF solution to find the Nashequilibrium within a few iterations.

Farzamnia et al. [13] used a hybrid solution of the WFalgorithm and a Nash game formulation to distribute the power onthe subchannels of a MIMO-OFDM scheme. The proposedalgorithm, which generalises the applicability of the classical WF,jointly evaluate the power required to attend a target SNR valueand efficiently distribute it among the subcarriers.

In the scope of cognitive radio (CR) systems, the work [14]uses the convex optimisation framework to maximise thethroughput of a MIMO-OFDMA based scheme, maintaining areasonable interference level on the primary users and subjected toa maximum power constraint. The authors split the originaloptimisation problem into two coupled subproblems with moreefficient solutions. Moreover, Cao et al. [15] proposed analgorithm for throughput maximisation of OFDMA-MIMO-CRsystems that includes subcarrier assignment, spatial beamforming,power allocation and bit-loading.

There are works proposing mechanisms for the bit-loadingcomplexity reduction based on greedy algorithms, at the cost ofthroughput system degradation. For instance, the work [16]presents a solution for DMT applications which applies thestandard bit-filling and bit-loading algorithms combined with aninitial bit-vector. The solution is calculated by rounding the resultsof the WF optimal solution. Moreover, in the power linecommunications context, beyond the initial bit-vector allocation,Vo et al. [17] proposed a solution deploying techniques forcomputational complexity reduction, including a greedy algorithmupdating multiple subchannels per iteration, rather than just one,while assuming computationally efficient approximations tocompute the cost function.

IET Signal Process.© The Institution of Engineering and Technology 2018

1

The works [18, 19] utilise subchannels grouping techniques toreduce the computational cost of the bit-loading solutions. Theprimary motivation of this kind of procedure comes from thenaturally high correlation between the adjacent subchannels in anOFDM/OFDMA system operating under the usual channel flatnesscondition. Hence, since the subchannel bandwidth is twice orfurther smaller than the channel coherence bandwidth, the channelstate information (CSI) estimation of such adjacent subchannelscan be grouped, and their respective channel gains can beapproximated by a fixed value, with a little loss of accuracy in suchestimations.

The contributions of this work are twofold. We characterise thebit-loading problem in OFDMA systems with power constraint atthe transmitter side, namely HH. Moreover, we develop anextensive analysis on the average capacity versus complexitytradeoff for different bit-loading strategies, especially analysing theHH grouping strategy. The complexity order of the algorithms andexpressions for the complexity (running time) depending on thenumber of OFDMA subchannels, N, are determined. In addition,the performance of the HH algorithm is compared to its versionsadopting three different mechanisms for the computationalcomplexity reduction: (i) the initial allocation bit vector using theWF solution, (ii) the updating of multiple subchannels per iterationand (iii) the subcarriers grouping technique with different gainthreshold by group.

The remaining sections of the paper are organised as follows. InSection 2, we present the OFDMA system model considered, whilein Section 3 we state the power allocation problem and its discreteoptimal solution. Afterwards, in Section 4 we present the threemechanisms to reduce the complexity of greedy algorithms, as wellas the computational complexity of the HH algorithm is discussedin Section 4.4. In Section 5, the numerical simulation results for thebit-loading power allocation algorithms are explored. Finally, themain conclusions are offered in Section 6.

2 OFDMA system modelWe consider an OFDMA system with K users and N subcarriersmodulated by the QAM symbol vector

s = [X[0], …, X[N − 1]]T, (1)

whose inverse discrete Fourier transform is equal to

x = [x[0], …, x[N − 1]]T (2)

We assume the bandwidth of each subcarrier sufficiently narrowerthan the channel coherence bandwidth, i.e. B < (Δ f )c, beingpossible to consider that each subcarrier is flat in frequency. Inaddition, assuming the symbol period duration less than thechannel coherence period, i.e. Ts < (ΔT)c, and admitting a cyclicalprefix with time length equal or less than the channel, maximumdelay spread be added at the begin of each symbol, resulting in theinter-symbol interference (ISI) effect could be completelymitigated. To perform the resource allocation process, we assumethat there is perfect CSI feedback during each symbol period.

Considering H the circulant matrix with the channel impulseresponse, which is μ samples long, and the noise vector of eachsample, respectively

h[0], …, h[μ], and n = [n[0]…n[N − 1]]T, (3)

(see (4)) suppressing the cyclical prefix samples, which suffer fromISI, the signal y on the receptor can be described as

y = Hx + n (5)

Considering an N × N discrete Fourier transform (DFT) Q matrix,the demodulated symbols at the receptor can be described as

r = Qy = QHx + Qn = QHQHs + Qn = H^ s + N (6)

where N is the DFT matrix of the noise vector n, and H^ is the

diagonal matrix filled with the samples of the channel frequencyresponse.

Remark 1: We use Ak to denote the set the subcarriers assignedto the user k. In our work, we consider the orthogonal assignmentof the frequency resources, i.e. each subcarrier can be allocated fora single user per OFDMA symbol. However, other schemes withthe OFDMA characteristics allow subcarriers sharing by more thanone user, e.g. the multicarrier code division multiple access MIMO(MC-CDMA-MIMO) model system treated in [20].

Considering that the focus of this work is on the powerallocation problem, herein, we will not consider the optimisation ofthe OFDMA channel resources distribution. So, we have adoptedthe criterion of dividing equally blocks of contiguous subcarriersbetween the users for subchannels assignment, such as the 3GPPLTE standard [21]. Other methods can be used for the subcarriersdistribution, such as the use of a solver to evaluate the originalmixed-integer optimisation problem or its linear formulationpresented on [22], iterative sub-optimal algorithms [7] or heuristicsolutions [23].

3 Optimisation problemThe classical resource optimisation problem considered consists ofthe maximisation of the total capacity of the OFDMA system withpower constraint. The optimisation problem is defined as follows:

maximisep ∈ ℜ+

N∑k = 1

K

∑i ∈ Ak

bi = ∑k = 1

K

∑i ∈ Ak

log2 1 + pk, iδk, iΓ

s . t . ∑i ∈ Ak

pk, i ≤ Pmax, k = 1, 2, …, K

p = [p1, p2, …, pN] ⪰ 0

(7)

where N is the number of OFDMA subchannels, Ak denotes the setof subcarriers assigned to the user k,

δk, i = |hk, i|2N0B

(8)

is the channel gain normalised by the thermal noise power, with|hk, i|2 as the power gain of the ith subchannel for the user k, N0 isthe noise spectral density and B is the band of each subchannel; biand pi represent the number of bits and the power allocated on eachsubchannel, respectively, while Γ is the SNR gap and Pmax is themaximal available power constraint per user.

The optimal power vector solution for this problem is the well-known WF, which results in fractional allocated-bits because of itscontinuous characteristic. When we treat a practical scenario, theWF solution cannot be implemented completely, because we wouldneed infinite granularity on the system modulation constellation[24].

H =

h[0] h[1] ⋯ h[μ − 1] 0 ⋯ 00 h[0] ⋯ h[μ − 2] h[μ − 1] ⋯ 0⋮ ⋱ ⋱ ⋱ ⋱ ⋱ ⋮0 ⋯ 0 h[0] ⋯ h[μ − 2] h[μ − 1]

(4)

2 IET Signal Process.© The Institution of Engineering and Technology 2018

3.1 HH algorithm

To overcome the granularity problem one can use a sub-optimalsolution which assumes discrete bit allocation. Hence, whenconsidering practical scenarios, the HH algorithm [8] providesoptimal solution for the optimisation problem (7), assumingdiscrete bits allocation, but sub-optimal solution when consideringcontinuous information quantities. Moreover, the HH approach isbased on exhaustive search, demanding a lot of computationalresources to be computed.

Remark 2: For the sake of notation simplicity, hereafter we havedropped the index identifying the kth user, assuming that subcarrierallocation procedure has been done in a previous step, since hereinour focus is on subcarrier power and bit-loading allocation. Also,for uniformity purpose, we have assumed that for each active user(k = 1, …, K) in the OFDMA system there is an equal spectralresource available, defined by N ⋅ B (Hz).

The HH algorithm calculates the energy incremental cost toallocate one more bit to the subcarriers, choosing the one with thesmallest cost [8]. The process is performed bit-by-bit until theallocated energy reaches the constraint. The energy incrementalcost to allocate the bit of number bi on the ith subcarrier is equal to

Δεi(bi) = 2bi Γδi

. (9)

where δi is the channel gain normalised by the thermal noise powerrelated to the user allocated on the ith subcarrier.

Algorithm 1 (see Fig. 1) shows a pseudo-code for the HHsolution. First, the incremental cost matrix with the amount ofenergy required to allocate the first bit on each subchannel isdefined; Palloc is the power sum allocated to the user in the currentiteration. Afterwards, a minimum search is executed, allocating thebits on the channels that present the lowest cost, until the totalenergy allocated reaches the power constraint.

4 Mechanisms for complexity reduction4.1 Initial allocation bit vector

In its original formulation, the HH algorithm initiates with the bitvector null, or filled with the maximum number of bits allowed onthe system, dependent on the adoption of the bit-filling or the bit-removal criteria.

The choice of a specific initial allocation bit profile can reducethe iterations number required for convergence of the allocationalgorithm, decreasing its running time. Some works study theinitial allocation bit vector that minimises the iterations number ofthe system.

One possible initial allocation bit vector is calculated byrounding the results of the WF solution, evaluating discrete results.The WF solution is developed by applying the Lagrangemultipliers optimisation technique on the problem (7), resulting inthe following equation:

pi = Cλ − Γδi

(10)

where Cλ is a constant called ‘water level’

Cλ = 1N Pmax + ∑

i = 1

N Γδi

(11)

With the vector p(0) = [p1(0)…pN

(0)] calculated by (10), the elementsbi

(0) of the initial allocation bit vector b(0) = [b1(0)…bN

(0)] are evaluatedby the expression

bi(0) = log2 1 + pi

(0)δiΓ (12)

Thus, the allocation process initiates with the initial allocation bitprofile defined by the b(0) obtained vector, rather than the prior nullbit vector.

4.2 Update multiple subcarriers per iteration

The HH algorithm implementation given in the pseudo-codeAlgorithm 1 (Fig. 1) predicts the update of only one bit on only onesubcarrier per iteration. One alternative for operation consists ofupdating only one bit on κ subcarriers during each iteration,choosing the κ subcarriers with the lowest bit incremental energycost.

The process of updating multiple subcarriers is a simplestrategy to reduce the iterations number required for convergence;at prior, the mechanism is able to decrease the number of iterationsof the HH algorithm by a κ factor. Despite that, this strategy resultsin degraded capacity rates in comparison with the obtained by theHH algorithm in its original formulation, because these strategiesdo not guarantee the minimal incremental cost at each algorithmstep. For example, at a determined step in an algorithm executionwith N = 2 and κ = 2, allocating 2 bits on the subcarrier 1 mayhave smaller incremental cost than dividing the 2 bits between thesubchannels.

4.3 Subcarriers grouping strategy

The subcarriers grouping process has the objective of dividing thesystem's subchannels in sets with fixed channel gain. This processcan be done using grouping algorithms, generally based on thesubcarriers’ gain. As a consequence of the grouping process, thesubcarriers are reduced to their groups, performing the allocationprocess onto the groups, in place of each subcarrier independently.

The channel impulsive response r(t) can be modelled as thesum of L delayed multipath components

r(t) = ∑i = 1

Laiδ(t − τi) (13)

where ai ∼ CN(0, σai2 ) is the ith multipath amplitude at the receiver,

τi is the ith multipath delay dependent on the environment's scattergeometry and ∑i = 1

L σai2 = 1. Evaluating the N-points DFT of r(t),

we obtain the channel coefficient of the nth OFDM subchannel as

Rn = ∑i = 1

Laie− j2π f nτi, n = 1, …, N (14)

where f n is the nth subchannel central frequency.Evaluating the correlation coefficient ρn, m between the nth and

mth OFDM subchannels considering orthogonal multipaths, i.e.E[aial

∗] = 0, ∀i ≠ l

ρn, m = E[RnRm∗ ] = E ∑

i = 1

L

∑l = 1

Laial

∗ej2π( f mτl − f nτi)

ρn, m = ∑i = 1

Lσai

2 ej2πτi( f m − f n)

(15)

Fig. 1 Algorithm 1: HH bit-loading algorithm


3

Remark 3: From (15) one can conclude that the correlation

between the subchannels depends on their frequency separation(| f m − f n|), as well as the channel's power delay profile, whichdefines the τi values. Hence, the subcarrier grouping mechanismcan be applied aiming at obtaining implementable low-complexitypower allocation procedures for OFDM and OFDMA systems.

Considering specific system conditions, the subcarrier groupingprocedure in OFDMA allows the approximation of the subchannelgains to a fixed value, with a small error due to the high correlationassociated with the adjacent subcarriers. These conditions arerelated to the frequency gap between the subcarriers and thechannel coherence bandwidth, which depends on the delay spreadassociated with the system channel impulse response. Channelswith small delay spread present more correlated subcarriers, whenthe opposite can be verified on channels with high delay spread.Hence, the performance of the subcarrier grouping process dependson the delay spread profile of the OFDMA channel.

The adopted subcarriers grouping algorithm is stated in thepseudo-code in Algorithm 2 (see Fig. 2). The algorithm initiatesdefining the parameter GT, called gain threshold, in dB. After thedefinition of GT, the first subchannel is declared as the leader of thefirst set. Thereafter, the adjacent subcarriers are scanned testing iftheir gain values belong to the interval [gc − GT; gc + GT], where gcis the gain of the leader subchannel of the current set. If the currentchannel has the gain value inside the interval, the subcarrier isallocated into the same set of the leader subcarrier with index c.Otherwise, the current channel is allocated into a new group, and isdefined as the leader of this group; the sequential grouping processof the OFDMA subcarriers is repeated until all the OFDMsubcarriers are distributed into the groups. Subsequently, thesequential grouping of the OFDMA subcarriers is done; thechannel gain of each set is defined as the least between itselements.

4.4 Computational complexity analysis

The complexity analysis has the objective of identifying theresources number consumed by the algorithm, as hardware,memory and mainly running time, tracing a relationship betweenthem and the obtained results at the end of the task. In general, the

running time of an algorithm depends on its input length; it iscommon to describe the running time as a function of the inputlength. This analysis can be done by counting step-by-step theoperations executed on each line code of the pseudo-code [25].

The basic arithmetic operations are implemented in hardwarewith fixed computational cost, not influenced by the input length.Although more complex algorithms like sort operations have arunning time proportional to the input length, we need to identifythese types of operations and consider their particular running time.

To obtain a general complexity analysis of the algorithm, weneed to count the executed operations on its worst-case execution.After counting, the obtained expression of the running timedependent on the input length is a superior bound for the runningtime.

The running time of the HH algorithm can be calculated bysumming the execution time of each instruction performed by it.Therefore, we have to identify and count the number of basicarithmetic operations and more complex operations, such as sortand search, on the algorithm code. It is important to identify theoperations which are executed repeatedly inside the loops, becausetheir running time depends on the length of the input data, beingthe more significant instructions on the total algorithm runningtime. After the counting, the time contributions of each instructionare summed, obtaining the total running time expression.

First, we counted the basic arithmetic operations: addition,subtraction, multiplication, division, exponents and logarithms.During counting, we divided the operations into two groups: (i)group 1 for the operations processed once on the algorithm; (ii)group 2 of operations processed repeatedly with the algorithmiterations.

Table 1 presents the number of basic arithmetic operationsclassified into group 1 and group 2. After the counting, wedetermined the complex operations. We identified one sort insidethe algorithm's loop. According to [25], this operation can beimplemented with algorithms that have the execution time upperbounded by the function u(N) = Nlog(N).

A numerical analysis of the iterations number of the HHalgorithm as a function of the system's subcarriers number Nindicates a linear dependence. Therefore, assuming that theiterations number is a function v(N) which depends on thesubcarriers number N, for the algorithm HH we have vHH(N) = N.

Hence, summing the contributions of all the HH algorithmoperations, we obtain the following expression for its running time:

THH(N) = N2log N + 2N2 + 5N (16)

Expressing the calculated THH(N) in the notation of the asymptoticsuperior bound O{ . }, we have that the HH algorithm complexity isbounded by

THHasym(N) = O{THH(N)} = N2log N . (17)

5 Numerical resultsWith the objective of comparing the computational complexityreduction and the capacity degradation verified with the adoptionof the bit-loading simplified mechanisms, we implemented Monte-Carlo simulations with the allocation algorithm HH, and itsversions using the initial allocation bit vector calculated by the WFalgorithm (HH-WF), updating multiple subcarriers per iteration(HH-K), and with a subcarriers grouping algorithm (HH-GRP).Besides, we used discrete allocation algorithms; moreover, in thesimulations, we implemented the WF optimal solution, as well theuniform equal-power allocation (EQ) criterium, aiming to comparethe sub-optimal but efficient solutions with the superior andinferior capacity bounds.

The proposed simulations scenario consists of the downlink(DL) into an urban macro-cell with radius r = 1 km and 8 userswhose positions are uniformly distributed into the cell. Weconsidered a situation without line of sight (NLOS), where thereceived amplitudes in the receptor follow a Rayleigh statisticaldistribution. The subcarriers number was set from 128 to 4096

Fig. 2 Algorithm 2: subcarriers grouping algorithm

Table 1 Number of operations executed in the algorithmHH once (group 1) and repeatedly inside the loop (group 2)Operation Group 1 Group 2addition 0 2N + 1subtraction 0 0multiplication N 1division 0 0exponent N 1logarithm 0 0


doubling the initial value; the total subchannels number wasdivided equally between the users. Table 2 summarises the valuesfor the general system parameters and the employed channel.

In the proposed scenario we did 104 Monte-Carlo realisationsperforming the power allocation process with the algorithms HH,HH-WF, HH-K with the κ values equal to 2, 4, 8 and 16, and theHH-GRP with the GT values equal to 0.25, 0.5, 1 and 5 dB, WFand EQ. During each iteration we sorted ten taps of the channelimpulse response and the users’ positions into the cell, evaluatingthe channel coefficients.

Fig. 3 presents the average capacity reached by the algorithmsHH, HH-WF, HH-GRP, WF and EQ as a function of the subcarriersnumber. As expected, the HH, HH-WF and HH-GRP algorithmsreached average capacity values lower than the optimal solutionWF, once the adoption of a discrete solution implies on lose ofoptimally. Among the discrete solutions, the HH-WF algorithmreached the highest capacity, overcoming the HH algorithm results.The HH-GRP algorithm results have shown average capacityvalues lower than the reached by the HH algorithm, with thedegradation increasing with the grouping threshold GT. Thisbehaviour is due to the reduction of the groups granularityincreasing GT, allowing the grouping algorithm to underestimatethe subchannels, grouping them with other subchannels with lowergain.

Fig. 4a depicts the average capacity curves for the HH, HH-K,WF and EQ algorithms as a function of the subcarriers number. Asthe case of the HH-GRP algorithm, the capacity values reached bythe HH-K one were lower than the calculated with the original HH.The growing of the κ factor has reflected on the degradationincrease in the capacity of the HH algorithm, as one can see on thezoom in Fig. 4b. The behaviour is due to the fact of updating onlyone bit on the κ more favourable subchannels during each iterationdoes not guarantee the minimal incremental cost at each algorithmstep. Despite the degradation, one can see a marginal reduction ofthe capacity with the increase of the κ factor when it is comparedwith the increase of the threshold GT in the HH-GRP algorithmshown in Fig. 3.

Fig. 5 depicts the curves of the average iterations number of thealgorithms HH, HH-WF and HH-GRP increasing the subcarriersnumber. The WF and EQ algorithms were suppressed on thisanalysis because they need a few iterations for convergence. As theexpected, we noted that increasing the gain threshold GT decreasesthe iterations number required for convergence. This occursbecause increasing GT reduces the number of groups, allowing theHH-GRP algorithm to operate with a search set whose the numberof elements is less than the subcarriers value N. The algorithm HH-WF demands an iterations number higher (about two and fourgrowing orders) than the other analysed algorithms forconvergence. Hence, the capacity gain, provided by the initialallocation bit vector calculated by the WF solution, compared tothe original HH algorithm has a substantial complexity cost,according to the iterations number.

To analyse the variation of the average iterations number of thealgorithms HH-K and HH as a function of the subcarriers number,

Table 2 Parameters of the proposed simulations scenarioParameter Valuecellular system OFDMAmacro-cell r = 1000 musers number 8subcarriers number N = 128 to 4096total bandwidth B = 2 MHzpath-loss exponent ξ = 4NLOS channel fading Rayleighgain threshold in the HH-GRP GT ∈ {(1/4), (1/2), 1; 5} dBsubcarriers number of the HH-K κ ∈ {2, 4, 8, 16}power constraint Pmax = 10 Wmaximum BER BER = 10−12

maximum delay spread τmax = 2.5 μs

Fig. 3 Average capacity as a function of the subcarriers number for thealgorithms HH, HH-WF, HH-GRP, WF and EQ bit-loading algorithms withdifferent gain thresholds

Fig. 4 Average capacity versus the number of subcarriers for the HH, HH-K, WF and EQ bit-loading algorithms(a) HH, HH-K, WF and EQ, (b) HH and HH-K: zoom in N = 2048 subcarriers


5

we trace the curves of Fig. 6. The approach of updating multiplesubcarriers per iteration (parameter κ > 1) produced reduction inthe iterations number required for convergence of the HHalgorithm. We observed too that increasing the κ number ofupdated subcarriers is proportional to the reduction in the averageiterations number.

Comparing the solutions HH-K and HH-GRP, we note that thefirst offers as main advantage capacity values near to the reachedby the HH algorithm, while the last one provides a fasterconvergence but with the capacity results more degraded. Theinitial allocation bit vector calculated by the HH-WF solution hasshown the best capacity performance, overcoming the results of theHH algorithm and getting closer to the optimal results of the WFsolution. However, the HH-WF algorithm is the one whichrequired the highest iterations number for convergence, needingmore computational resource to be executed.

To analyse the performance of the grouping algorithm HH-GRPwith the change of the threshold gain GT and the subcarriersnumber of the system, we trace the curves of the average numberof obtained groups by the subcarriers number, presented in Fig. 7.

The results confirm the reduction on the grouping granularityincreasing GT, implying on the reduction of the groups number.This is the major advantage of the technique, which reduces theelements number of the search set of the greedy algorithm,reducing the complexity for computation. Analysing the behaviourof the average groups number increasing the subcarriers number,we see an asymptotic behaviour like roofs. This fact is due to theuse of a channel model assuming a fixed maximum delay spread ofthe channel impulse response, in this case, τmax = 2.5μs.

5.1 Subcarriers grouping performance

In this section, we analyse the impact of the number of subcarriergroups on the HH-GRP performance under different channelconditions, including channel delay spread τmax and OFDMAsubchannels correlation. Fig. 8 depicts the curves of the averagenumber of groups versus the maximum delay spread, consideringN = 1024 subcarriers and different values for grouping thresholdGT. The increase of τmax conveys in more uncorrelated channels,increasing the number of groups, even for large SNR thresholdvalues. This result supports the development of (15), taking intoaccount that the similarity between the channel's gain is the keyrole in the grouping algorithm.

The normalised correlations between the different subcarriergroups formed by the HH-GRP grouping algorithm and varying thechannel's maximum delay spread, are depicted in Fig. 9. Suchcurves evidence that the average correlation coefficient of thesubcarrier groups decreases very quickly when the delay spreadincreases in the range [1; 25]μs. We can see that, besides moreuncorrelated subcarriers, the increase of τmax produces moreuncorrelated groups. Moreover, the subcarrier groups correlationsteadily decreases with the increment of SNR threshold granularity(small GT).

Finally, the average capacity and the number of iterationsrequired to perform the HH-GRP bit allocation have been

Fig. 5 Average number of iterations required for convergence versus thesubcarriers number for the algorithms HH, HH-WF and HH-GRP

Fig. 6 Average number of iterations required for convergence as afunction of the subcarriers number for the algorithms HH and HH-K

Fig. 7 Groups number obtained by the grouping algorithm of the HH-GRPsolution; τmax = 2.5μs

Fig. 8 Average number of groups under different grouping thresholds forthe HH-GRP algorithm solution as a function of the channel's maximumdelay spread; N = 1024 subchannels

Fig. 9 Average subcarrier-grouping correlation obtained by the groupingalgorithm of the HH-GRP solution as a function of the channel's maximumdelay spread; N = 1024 subchannels


determined by numerical simulations assuming different conditionsof channel's maximum delay spread and varying the gain thresholdGT, aiming to establish if there exists a GT value that maximises thealgorithm performance depending on the channel conditions. Tocompute the tradeoff between the capacity enhancement and thereduction of the number of iterations we have defined the tradeofffactor ζ ∈ [0; 1] as follows:

ζ = 12 1 + C − Cmin

Cmax − Cmin− ℐ − ℐmin

ℐmax − ℐmin(18)

where ζ = 1 indicates the best balance, C and ℐ are, respectively,the average capacity and the average number of iterations, bothcalculated by numerical simulations, for each {τmax, GT}-pair;moreover, the ratios (Cmin/Cmax) and (ℐmin/ℐmax) are, respectively,the min–max capacity ratio and min–max number of iterations ratiocalculated among all the scenarios evaluated. This equation

guarantees that the tradeoff factor value represents equally the gainor loss of capacity and iterations number. Notice that in (18), thecapacity C and the number of iterations ℐ are normalised,representing the same weight (50–50%) on the tradeoff factorcalculation.

Fig. 10 depicts the tradeoff factor ζ for each pair of channel'smaximum delay spread τmax and gain threshold GT. The firstconsideration is that for all values of τmax, choosing small or largevalues of GT results in low ζ factor values due to increasing theiterations number acts in favour of the capacity increasing (smallGT values); alternatively, the capacity degradation works in favourof the decreasing complexity in terms of the number of iterations(large GT values), respectively.

Furthermore, for each value of channel's maximum delayspread, there exists a GT which offers the best tradeoff between thecapacity enhancement and the reduction of the number of iterationsrequired for convergence. This fact can be explained by recallingthe discussion of Section 4.3, which shows that the correlationbetween adjacent subcarriers depends on the channel's delayspreading properties. Therefore, from the perspective of thewireless channel characteristics, the parameter GT can be adjustedin such a way that the HH-GRP algorithm is able to produce thebest tradeoff between complexity and average capacitydegradation.

Table 3 summarises the numerical results of this section forcapacity, average number of iterations and average number ofgroups for the HH-GRP algorithm, considering N = 1024subchannels and different values for τmax and the parameters of theHH-K and HH-GRP algorithms. As it was discussed earlier, theHH-K algorithm with κ = 16 is the most efficient bit-loadingsolution, offering a remarkable reduction on the number ofiterations when compared to the original HH algorithm, whileresulting in a marginal degradation on the average capacity.Moreover, observing the average number of groups column, onecan notice its dependence on the channel delay spreading and thegrouping threshold parameters, which reflects directly on the HH-GRP algorithm's performance.

6 ConclusionThe greedy HH algorithm for power allocation problem in OFDMsystems was systematically characterised and compared with low-complexity sub-optimal approaches. Three mechanisms to reducethe algorithm computational complexity have been considered: (i)the adoption of initial bit-vector allocation different from null bitsprofile; (ii) update multiple subcarriers per iteration; (iii)subcarriers grouping technique.

The numerical simulations results evidenced the performance-complexity tradeoff of the analysed bit-loading algorithms. TheHH-GRP and HH-K solutions reached an average capacity lowerthan that attained by the original HH, needing a smaller iterations

Fig. 10 Tradeoff factor ζ calculated using the achieved capacity and thenumber of iterations for the HH-GRP algorithm under different conditionsof the gain threshold GT and channel delay spread τmax.(a) ζ × GT × τmax, (b) Heat map for the same ζ × GT × τmax

Table 3 Summary of the numerical results for N = 1024 subchannelsAlgorithm Avg. Ca, bits/s/Hz Avg. ℐa Avg. number of groups

τmax = 2.5 μs τmax = 12.0 μs τmax = 25.0 μsWF 8.57 — — — —EQ 3.14 — — — —HH 6.26 7.23 — — —HH-WF 7.63 1019 — — —HH-K κ = 2 6.23 4.12 — — —

κ = 4 6.17 2.54 — — —κ = 8 6.08 1.76 — — —κ = 16 5.93 1.37 — — —

HH-GRP GT = 0.25 dB 5.97 2.73 376 773 860GT = 0.5 dB 5.78 1.93 222 595 748GT = 1 dB 5.36 1.47 123 389 579GT = 5 dB 3.73 1.08 25 83 149

aValues calculated with τmax = 2.5μs.


7

number for convergence. Comparing the HH-GRP and HH-Kalgorithms, one could observe that the HH-GRP results a higherreduction on the iterations number with more capacity degradation,being the two characteristics proportional to the gain threshold GT,while the last one results in a much smaller capacity degradation,with the iterations number reduced proportionally to the factor κ.The HH-WF solution has shown the best average capacity results,overcoming the results reached by the HH algorithm and gettingcloser to the results calculated by the optimal solution WF.However, the HH-WF solution demands the highest iterationsnumber for convergence, presenting the greatest computationalcost.

Hence, one could conclude that both mechanisms of updatingmultiple subchannels per iteration and the subcarriers groupingallow the convergence of the greedy algorithm HH with lessiterations, at the cost of some degradation on the average capacity.The algorithm with the best tradeoff on the performance versuscomplexity is the HH-K, which has demonstrated a low capacitydegradation even with a high κ value.

Finally, the initial bit-vector allocation defined by the WFsolution was adopted as an alternative to obtaining an averagecapacity higher than the reached by the HH algorithm and itsvariants. As a consequence, a closer solution to the true WF onehas been obtained, although this capacity gain comes with acomputational complexity increasing, represented by the iterationsnumber required for convergence.

7 AcknowledgmentThis work was supported in part by the National Council forScientific and Technological Development (CNPq) of Brazil underGrant 304066/2015-0, Fundação Araucária under Grant 302/2012,and in part by State University of Londrina – Paraná StateGovernment (UEL) (scholarship).

8 References[1] Basaran, S. T., Kurt, G. K.: ‘Joint subcarrier and power allocation in OFDMA

systems for outage minimization’, IEEE Commun. Lett., 2016, 20, (10), pp.2007–2010

[2] Fathi, M., Karipidis, E.: ‘Distributed allocation of subcarrier, power and bit-level in multicell orthogonal frequency-division multiple-access networks’,IET Commun., 2014, 8, (6), pp. 781–788

[3] Xiong, C., Li, G. Y., Zhang, S., et al.: ‘Energy- and spectral-efficiencytradeoff in downlink OFDMA networks’, IEEE Trans. Wirel. Commun., 2011,10, (11), pp. 3874–3886

[4] Kim, K., Han, Y., Kim, S.-L.: ‘Joint subcarrier and power allocation in uplinkOFDMA systems’, IEEE Commun. Lett., 2005, 9, (6), pp. 526–528

[5] Shannon, C. E.: ‘Communication in the presence of noise’, Proc. IRE, 1949,37, (1), pp. 10–21

[6] Gallager, R. G.: ‘Information theory and reliable communication’ (Wiley,USA, 1968, 1st edn.)

[7] Souza, A. R. C., de Almeida Amazonas, J. R., Abrão, T.: ‘Power andsubcarrier allocation strategies for energy-efficient uplink OFDMA systems’,IEEE J. Sel. Areas Commun., 2016, 34, (12), pp. 3142–3156

[8] Hughes-Hartogs, D.: ‘Ensemble modem structure for imperfect transmissionmedia’, U.S. Patent 4.679.227, July 1987, 4.731.816 (Mar. 1988), 4.833.706(May. 1989)

[9] Chow, P. S., Cioffi, J. M., Bingham, J. A. C.: ‘A practical discrete multitonetransceiver loading algorithm for data transmission over spectrally shapedchannels’, IEEE Trans. Commun., 1995, 43, (2/3/4), pp. 773–775

[10] Wong, C. Y., Cheng, R. S., Lataief, K. B., et al.: ‘Multiuser OFDM withadaptive subcarrier, bit, and power allocation’, IEEE J. Sel. Areas Commun.,1999, 17, (10), pp. 1747–1758

[11] Zhang, H., Fu, J., Song, J.: ‘A Hughes-Hartogs algorithm based bit loadingalgorithm for OFDM systems’. 2010 IEEE Int. Conf. on Communications,Cape Town, South Africa, May 2010, pp. 1–5

[12] Sampaio, L. D. H., Abrao, T., Durand, F. R.: ‘Game theory based resourceallocation in multi-cell massive MIMO OFDMA networks’. 2017 IEEEWireless Communications and Networking Conf. (WCNC), San Francisco,USA, March 2017, pp. 1–6

[13] Farzamnia, A., Yew, E. S., Islam, M. N.: ‘Investigation on channel capacityenhancement for MIMO-OFDM in fading channels using hybrid water fillingand Nash algorithm’. 2017 IEEE 13th Int. Colloquium on Signal Processingits Applications (CSPA), Batu Ferringhi, Malaysia, March 2017, pp. 249–253

[14] Mohammadi, M., Andargoli, S. M. H.: ‘Sum throughput maximization fordownlink MIMO-OFDMA based cognitive radio networks in spectrumoverlay model’. 2016 8th Int. Symp. on Telecommunications (IST), Tehran,Iran, Sept 2016, pp. 72–77

[15] Cao, H., Cai, J., Alfa, A., et al.: ‘Efficient resource allocation scheduling forMIMO-OFDMA-CR downlink systems’. 2016 8th Int. Conf. on WirelessCommunications Signal Processing (WCSP), Yangzhou, China, Oct 2016, pp.1–5

[16] Papandreou, N., Antonakopoulos, T.: ‘A new computationally efficientdiscrete bit-loading algorithm for DMT applications’, IEEE Trans. Commun.,2005, 53, (5), pp. 785–789

[17] Vo, T. N., Amis, K., Chonavel, T., et al.: ‘Achievable throughput optimizationin OFDM systems in the presence of interference and its application to powerline networks’, IEEE Trans. Commun., 2014, 62, (5), pp. 1704–1715

[18] Nader-Esfahani, S., Afrasiabi, M.: ‘Simple bit loading algorithm for OFDM-based systems’, IET Commun., 2007, 1, (3), pp. 312–316

[19] Mahmood, A., Belfiore, J. C.: ‘An efficient algorithm for optimal discrete bit-loading in multicarrier systems’, IEEE Trans. Commun., 2010, 58, (6), pp.1627–1630

[20] Arumugam, S., Perumal, D.: ‘Power control through water filling gametheory in adaptive modulation based MCCDMA-MIMO system’. 2016 Int.Conf. on Communication and Signal Processing (ICCSP), Melmaruvathur,India, April 2016, pp. 1415–1419

[21] Zyren, J., McCoy, W.: ‘White paper: overview of the 3GPP long termevolution physical layer’. NXP Semiconductor/Freescale Semiconductor,Tech. Rep. 3GPPEVOLUTIONWP, June 2007

[22] Kim, I., Park, I.-S., Lee, Y. H.: ‘Use of linear programming for dynamicsubcarrier and bit allocation in multiuser OFDM’, IEEE Trans. Veh. Technol.,2006, 55, (4), pp. 1195–1207

[23] Kim, Y., Kim, J.: ‘An efficient subcarrier allocation scheme for capacityenhancement in multiuser OFDM systems’. VTC Spring 2008 - IEEEVehicular Technology Conf., Singapore, May 2008, pp. 1915–1919

[24] Chow, P. S., Cioffi, J. M., Bingham, J. A. C.: ‘A practical discrete multitonetransceiver loading algorithm for data transmission over spectrally shapedchannels’, IEEE Trans. Commun., 1995, 43, pp. 773–775

[25] Cormen, T. H., Stein, C., Rivest, R. L., et al.: ‘Introduction to algorithms’(McGraw-Hill Higher Education, USA, 2001, 2nd edn.)


28

Apendice C -- Approximate

message-passing algorithm for mMTC

terminals activity detection

1

Approximate Message-Passing Algorithm formMTC Terminals Activity Detection

João Henrique Inacio de Souza, Taufik Abrão

Abstract—The fifth generation service mMTC (massivemachine-type communications) lacks distributed and non-coordinated access protocols to manage the connection of densemachine-type devices populations. Non-orthogonal and grant-free access solutions are relevant as they require less messageexchanges between the terminals and the central node, shrinkingthe signaling overhead. One framework to develop this class ofprotocol include the formulation of the active devices detectionand the estimation of their respective channels as the reconstruc-tion of sparse signals. The present work aims to characterizea scheme to cope with the terminals activity detection problemconstituted by an estimation step, which includes the approximatemessage passing (AMP) algorithm with a soft thresholdingdenoising function, and a detection step using the maximum aposteriori probability (MAP) decision rule. We have developedanalytical expressions for the detection scheme performance interms of miss detection and false alarm probabilities, and we havedemonstrated that the decision rule can be implemented with lowcomplexity, being appropriated to solve the connectivity problemat the mMTC service.

Index Terms—Massive machine-type communications(mMTC), random access (RA) protocol, approximate message-passing (AMP), activity detection, sparse signal processing.

I. INTRODUCTION

The future 5G standard will introduce the massive machine-type communications, which will offer efficient and reliableconnection for the growing group of devices non-operated di-rectly by humans. These machine-type equipment, representedby sensors, actuators, IoT devices, and other machine-typedevices, are low-complex and low-power terminals that accessthe network sporadically by transmitting data at low rates. Thesporadic behavior summed to the fact that a BS will support amassive population of machine-type terminals makes the cen-tralized assignment of orthogonal pilot sequences for channelestimation unfeasible due to the large signaling overhead [1].

As an alternative to the centralized approach, recent studieshas developed new distributed protocols for the medium accesscontrol (MAC) layer based on random access (RA), exploringthe intermittent activity of the secondary nodes. In general,the works present techniques to resolve or avoid collisionsadopting orthogonal pilot sequences, or mechanisms to post-process the signal received at the BS as a result of non-orthogonal pilot assignment.

There are few literature on the RA protocols for 5G massivecrowded scenarios. The authors in [2] has presented a ran-dom access protocol to assign orthogonal pilots sequences in

Taufik Abrão and João Henrique de Souza are with Electrical En-gineering Department, State University of Londrina, PR, Brazil (e-mail:[email protected], [email protected]).

crowded scenarios defined as SUCRe. The proposed protocolefficiently introduces an uncoordinated contention resolutionprocess based on a precoded response sent by the BS, allowingthe collided nodes to decide about transmit or not with thepicked pilot sequence, depending on their respective channelpowers. However, the key role of the central node on sendingthe contention resolution response introduces additional over-head. In addition, as presented in [3], the need for new accessattempts requested by the collided devices configures a grant-based access scheme, which limits the maximum number ofactive nodes.

As an advantage, the grant-free schemes reduce the latencyby combining the secondary node’s exclusive preamble anddata on the same uplink transmission; in doing so, it avoidsan assignment of pilots sequences monitored by the BS at eachaccess request. However, considering the massive number ofnodes in the mMTC and the limited channel coherence time,the implementation of grant-free RA protocols is feasible evenassuming non-orthogonal pilots; but requiring new proceduresfor device activity (DA) detection and channel estimation.

In [4] is offered a grant-free access solution which exploresthe sparse activity of the nodes. The device activity and thechannel estimation problems are formulated as a compressedsensing problem, solved with the single and multiple mea-surement vector versions of the approximate message-passing(AMP) algorithm. The results for the probabilities of missdetection and false alarm obtained using the AMP’s stateevolution put the approach as a promising solution for deviceactivity detection.

Remaining on the AMP algorithm, the authors in [5], [6]explores the solution’s performance on the massive MIMOregime via state evolution. Firstly, they analyze the probabili-ties of miss detection, false alarm and the channel estimationerror. Then, the authors characterize the achievable rate withthe AMP’s channel estimation combined with MRC (maxi-mum rate combining) and MMSE (minimum mean squarederror) beamforming. As a conclusion, the device activitydetection is guaranteed on the massive MIMO condition, butthe channel estimation error is higher than the reached by othermethods due to the non-orthogonality of the pilot signals.

The authors in [7] use the AMP solution combined withthe LMMSE (linear minimum mean squared error) estimatorfor the detection of the active terminals and the estimationof its channel vectors. In addition, they show that the non-coherent transmission outperforms the coherent transmissionin the mMTC setup, where the transmission consists of a fewbytes per packet, namely short block-length communicationscenarios.

The AMP algorithm has been extensively discussed in the

2

literature to solve the problem of recovering sparse signals.In the AMP framework, the state evolution is suitable toevaluate analytically the quality of the signal reconstruction.The authors in [8] has applied the complex version of the AMPalgorithm (CAMP) with the soft thresholding denoising forradar applications, combining the estimation with an efficientdetection scheme.

Our work presents a DA detection scheme combining thesignal reconstruction capability of the AMP algorithm withsoft thresholding denoising and the maximum a posterioriprobability (MAP) decision rule to solve the terminals’ activitydetection problem in the mMTC context. The contribution ofthis work is threefold. We have done an exhaustive studyon the soft thresholding denoiser operating in AWGN andRayleigh fading plus pathloss statistical channels. After wederived the optimal decision rule for the binary detectionproblem, we focus on obtaining analytical expressions for theprobabilities of miss detection, false alarm and detection error.The theoretical results were validated by Monte-Carlo simula-tions demonstrating the efficiency of the proposed scheme inaddressing the DA detection problem in mMTC scenarios.

The paper has the following organization. On the section IIwe present the mMTC system model adopted throughout thispaper. In section III, the AMP algorithm and its state evolutionframework are examined; moreover, we have analysed the de-tection scheme under the MAP decision rule. Numerical resultsare developed in Section IV, while the final considerations andremarks are given in Section V;

II. SYSTEM MODEL

The system model consists of a MISO (multiple-inputsingle-output) scheme constituted by one central node withhigh signal-processing power and N secondary nodes, repre-sented by machine-type terminals, with low signal-processingpower resources, Fig. 1. The secondary nodes are active withthe probability ε� 1 at each contention period.

Fig. 1. MISO massive machine-type communications scenario.

The contention periods have the length ∆ < Tc, where Tc isthe channel coherence time. During the uplink phase, the activeterminals send their unique signatures, for activity detectionand channel estimation, followed by its payload. Each devicesignature has the structure an = [an1 an2 · · · anL]T for the

user n, where an ∼ CN(0, 1

LI). We assume that all the N

signatures are known at the BS.The received signal in the uplink (UL) is defined as:

y = Ax + z (1)

where A = [a1 a2 · · · aN ] is the matrix with all the devices’signatures, x = [α1h1 α2h2 · · · αNhN ]T is the vector thatmodels the activity indicator αn ∈ {0, 1} and the channelcoefficient hn of each terminal; finally, the noise vector z ∼CN (0, Iσ2

z) has a diagonal covariance matrix dependent on thenoise and the transmitted signal powers. The activity indicatorhas value 1 when the terminal is active and 0 otherwise.

For simplicity, we assume that each device transmits withthe total power ξ = Lρpilot, where ρpilot is the power ofthe signatures’ symbols. Considering that the noise power isthe product of its power spectral density N0 by the systembandwidth, B, resulting:

σ2z =

N0B

Lρpilot(2)

We will consider two different cases for the statisticaldistribution of the channel coefficients hn.

1) AWGN channel: On the first case, the channel onlyadds the white Gaussian noise, i.e. hn = 1, ∀n. So, theentries of the vector x constitute a random variable distributedaccordingly to the Bernoulli probability density function:

fXn(xn) = εxn(1− ε)1−xn , xn ∈ {0, 1} and ε ∈ [0, 1] (3)

2) Rayleigh fading plus path loss channel: For this case, thechannel coefficients are distributed as hn ∼ CN (0, βn), whereβn is a random variable that models the large-scale fading,depending on the terminals spatial distribution, the cell sizeand the environment’s propagation conditions. Considering thedevices distributed uniformly among the cell area, the entriesof x follow the mixture distribution:

fXn(xn) = (1− ε)δ0 + εfH(xn) (4)

where δ0 is the Dirac’s delta function and fH(h) is theprobability density function of the channel coefficients,

fH(h) = a

c∫

b

Q(β) exp

(−|h|

2

β2

)dβ (5)

where

a =4k2/γ

πγ(R2 − r2), b =

√k

Rγ, c =

√k

rγ, (6)

Q(β) = β−4/γ−2, (7)

and γ is the path loss exponent, R is the cell radius, r is theminimum distance between the BS and the terminals, and kis a constant that depends on the path loss attenuation at thisminimum distance. The derivation of fH(h) is presented inthe Appendix A.

III. APPROXIMATE MESSAGE-PASSING

One way to achieve the terminals’ activity detection fromthe transmitted signals consists in obtaining an estimate for x,

3

and feed the result to some detection scheme, as the structuredepicted on the Fig. 2. Recovering the vector x from the uplinksignal in (1) and the signatures matrix A is equivalent to solvethe basis pursuit denoising (BPDN) problem, formulated as theconvex optimization problem:

x = minimizex

1

2‖y −Ax‖22 + λ‖x‖1 (8)

where λ ∈ R+ is a scalar called regularization parameter,which controls the tradeoff between the reconstruction errorand the estimate’s sparsity [9]. We can interpret this problemas finding a sparse vector x that reasonably solve the undeter-mined linear system of equations Ax = y.

Estimate AMP Algorithm Detector Activity

detection

Uplink signaly x

Fig. 2. Scheme adopted for mMTC terminals activity detection.

The BPDN formulation can be optimally evaluated withconventional optimization techniques, e.g. interior-point andgradient methods [10], at the cost of high computationalcomplexity. The resources expensiveness of standard tech-niques give rise to the research on new efficient methods forsparse reconstruction, such as the greedy pursuit and iterativeshrinking [11].

One technique to solve (8) efficiently but sub-optimally isthe approximate message passing (AMP) algorithm, originallypresented in [12], with its complex-valued version describedin [13]. The complex AMP algorithm can be summarized bythe three equations:

xt = AHrt−1 + xt−1 (9)

xt = η(xt, ϕt

)(10)

rt = y −Axt + rt−1N

2L

(〈η′R

(xt, ϕt

)〉+ 〈η′I

(xt, ϕt

)〉)

(11)

where xt is the estimate, xt is the sparse version of theestimate and rt is the vector of residual at the iterationof number t. The denoising function η(·, ·) presents twoarguments, the input signal as the first entry and the denoisingthreshold ϕt as the second one. We use η′R(·, ·)/η′I(·, ·) todenote the partial derivative of the real/imaginary parts of thedenoising function related to the real/imaginary parts of theinput signal. The operator 〈·〉 represents the average betweenthe elements of the input vector.

The denoising function can be designed based on the knownproperties of the original signal x. If the actual statisticaldistribution of the signal is unknown, the optimal denoisingfunction is the soft thresholding one, which minimizes theminimum squared error (MSE) for the least-favorable dis-tribution of x. Differently, when we have knowledge aboutthe original signal’s distribution, the optimal function is theMMSE denoiser, discussed in [4], [5], [14]. Our focus remainson the first case.

The complex soft thresholding denoiser function is defined

for each entry of x as

η(xt, ϕt) =

{(|xtn| − ϕt) xtn

|xtn| , if|xtn| ≥ ϕt0, otherwise

(12)

taking ϕt as the threshold parameter at the iteration t. Wewill assume this parameter as ϕt = ντt, ν ∈ R+, where τ2tis the MSE of the estimate x at the iteration t. We need atleast one estimate of the MSE at each CAMP’s iteration toadopt this threshold design. For simplicity reason, we assumethat τt is perfect known across the algorithms steps. But, forpractical implementation, we can calculate an estimate for theMSE from x using the expression given in [9].

The scalar ν can be tuned aiming to obtain a fast conver-gence and the least MSE at the CAMP algorithm’s output,as discussed in [8]. However, this value depends on theproblem settings, such as the number of devices, the activationprobability and the signatures’ length. Fig. 3 depicts the MSEpredicted for the AMP algorithm execution adopting differentterminals’ activation probabilities. We can note that exists anoptimal ν that offers the lowest MSE for each ε, suggestingthat the threshold should be tuned following the scenariodynamics.

1 1.5 2 2.5 30.15

0.2

0.25

0.3

0.35

0.4

Est

imat

e M

SE

(2)

= 10% = 5% = 1%

Fig. 3. Mean squared error estimates vs soft thresholding denoiser factor ν.

Hence, for simplicity purpose yet and aiming to guaranteethe algorithm convergence, in this work fixed sub-optimal νvalues are assumed. Although we remark that the threshold νcan be tuned by adopting heuristics procedures, as discussedin [9].

A. State evolution framework

One of the main advantages of the AMP algorithm isthat, under determined conditions, the estimate MSE, namedthe algorithm state, can be analytically defined allowing thedevelopment of theoretical expressions for the detector per-formance. Assuming an asymptotic regime, where N,L→∞with L

N = δ ∈]0,∞[, the entries of the estimation calculatedin (9) are modeled by the random variable:

Xtn = Xn + τtV (13)

4

where Xn is a r.v. distributed accordingly fXn(xn) and V ∼CN (0, 1). Therefore, we can see the estimate as the originalsignal corrupted by Gaussian noise with variance τ2t .

The algorithm state can be updated recursively by theexpression:

τ0 =

√σ2z +

1

δE [|Xn|2] (14)

τt =

√σ2z +

1

δE[∣∣∣η(Xtn, ϕt−1

)−Xn

∣∣∣2]

(15)

considering the expectation over Xn, Xn and V .

B. Activity detection

After the estimation process, we need to establish one ruleto decide if each terminal is active or inactive. This decisionrule performs a binary detection that tests the two hypothesis:

{H0 : Xn = 0, inactive terminal

H1 : Xn 6= 0, active terminal(16)

The output of the decision scheme can be successful or anerror, which is divided in two categories: an false alarm whenthe terminal is inactive and detected, and a miss detectionwhen the terminal is active but undetected. The probabilitiesof obtain a false alarm or a miss detection are, respectively,represented by PFA and PMD, so the probability of detectionerror is computed as

Pe = εPMD + (1− ε)PFA (17)

The optimal detection scheme when we know the a poste-riori distribution of the estimate is the maximum a posterioriprobability rule, based on the probability of each hypothesisdepending on the estimate value [15]. The MAP detector forour binary case can be written as:

D(xn) = arg maxi∈{0,1}

[PXn|Xn

(Hi|Xn = xn

)](18)

The MAP decision criterion is relevant for the studieddetection problem because, for the considered cases, it canbe simplified to compare the estimate with an appropriate de-signed threshold. So, we can evaluate the optimal decision rulewithout calculate expressions that require high computationalresources like integrals.

In the following we will present the expressions for theMAP rule, and the probabilities of false alarm and missdetection for the two channel model considered.

1) AWGN channel: The MAP decision for the AWGNchannel model can be evaluated from (3) and (13) using theBayes rule. The obtained expression is:

R{xn}H0

≶H1

1

2

[1 + τ2t log

(1− εε

)](19)

where R{·} denotes the real part of the entry. The completedevelopment of the decision rule is presented in the AppendixB. Analyzing (19), we see that the left side is monotonically

increasing with R{xn}. So, the decision rule can be simplifiedto:

R{xn}H0

≶H1

θ (20)

where θ is a threshold designed to reach the target probabilitiesof false alarm and miss detection.

From our new decision rule, the probabilities of false alarmand miss detection can be expressed as:

PMD = P (R{Xn} < θ|Xn 6= 0) (21)

PFA = P (R{Xn} > θ|Xn = 0) (22)

The expressions for the miss detection and false alarm prob-abilities are developed in the sequel. Observing the estimatemodel (13) and the marginal distribution of the original signal(3), one can note that Xn has a circular Gaussian statisticaldistribution. Hence, R{Xn} follows a Gaussian distributionwith parameters supported by

E[R{Xn}] = R{E[Xn]}, var[R{Xn}] =var[Xn]

2(23)

where var[·] is the variance of the input random variable.

When the hypothesis H1 occurs, R{Xn} follows a Gaussiandistribution with mean 1 and variance τ2t . Hence, the missdetection probability is equivalent to compute the cumulativedensity function (CDF) of R{Xn},

PMD =1

τt

θ∫

−∞

exp

[− (x− 1)2

τ2t

]dx (24)

On the other hand, when H0 occurs, R{Xn} has a Gaussiandistribution with mean zero and variance τ2t . Thus, the falsealarm probability is the complementary CDF (CCDF) ofR{Xn},

PFA =1

τt

∞∫

θ

exp

(−x

2

τ2t

)dx (25)

2) Rayleigh fading plus path loss channel: The MAPdecision for the second channel case is obtained from (4) and(13) by applying the Bayes rule:

c∫

b

β2Q(β)

β2 + τ2texp

[β2|xn|2

τ2t (β2 + τ2t )

]dβ

H0

≶H1

1− επτ2t εa

(26)

The derivation of this expression is developed in the AppendixC.

The first derivative test shows that the left side of the MAPrule is monotonically increasing with |xn|. For this reason, thedecision criterion can be rewritten in therms of the thresholdθ as:

|xn|H0

≶H1

θ (27)

Following the approach presented above, the scheme prob-abilities of false alarm and miss detection for this case can be

5

calculated by:

PMD = P (|Xn| < θ|Xn 6= 0) (28)

PFA = P (|Xn| > θ|Xn = 0) (29)

The expressions for the error probabilities can be calculatedfrom the statistical distribution of estimates on each hypothesiscase. When H1 occurs, the estimate follows the distribution(54). Consequently the miss detection probability is the CCDFof Xn, defined as the integral of fXn(xn|Xn 6= 0) over theregion {xn : |xn| < θ},

PMD = 2πa

θ∫

0

c∫

b

xβ2Q(β)

β2 + τ2texp

(− x2

β2 + τ2t

)dβ dx (30)

Following the same development, when H0 occurs, Xn isdistributed accordingly (48). So, the false alarm probability isthe CDF of fXn(xn|Xn = 0) over the region {xn : |xn| > θ},

PFA =2

τ2t

∞∫

θ

x exp

(−x

2

τ2t

)dx (31)

IV. NUMERICAL RESULTS

After the characterization of the scheme detection and thedevelopment of the analytical expressions for the performancemetrics, Monte-Carlo simulations (MCS) have been carried outaiming at validating the analytical results presented in previoussection.

The MCS setup includes typical parameters values of urbanpractical wireless channel scenarios, as summarized in TableI. The MCS trials were executed considering different powerlevels and pilot sequence lengths, adopting two channel mod-els, depending on the type of the simulation scenario.

TABLE IPARAMETERS OF THE SIMULATIONS SCENARIO.

Parameter ValueTerminals number N = 2000

Activation probability ε = 0.05Pilot sequences length L ∈ [400, 1600]

Soft thresholding factor ν ∈ {1, 2}a

Total bandwidth B = 1 MHzNoise power spectral density N0 = −169 dBm/Hz

Path loss constant k = −80.3 dBPath loss exponent γ = 3.67

Cell radius R = 1 kmMin. distance device-BS r = 0.05 km

AMP iterations nit = 20

aWe have adopted ν = 1 for the case 1 channel model, and ν = 2 forthe case 2 to guarantee the convergence of the AMP algorithm.

The first result obtained is the receiver operation character-istic (ROC) curve, depicted on the Fig. 4(a) for the AWGNchannel and the Fig. 4(b) for the channel combining the pathloss and Rayleigh fading. The ROC provides the values forthe two possible detection errors achieved by the detectionscheme changing the decision threshold. These curves allow

the sensibility analysis of the error rates subject to the decisionthreshold and the scenario parameters. We have traced thetheoretical ROC curves and the ones obtained with MCSrealizations varying the pilot sequences power.

We can observe that on the two channel model cases in-creasing the power reduces the rate of the two error types. Thiswas expected, since when the power increases, the effect of theadditive noise decreases, and as a consequence, brings downthe reconstruction error obtained with the AMP algorithm.Differently, under Rayleigh fading plus path loss channel themiss detection rate presents a much higher sensibility to thedecision threshold than the false alarm. Thus, adjusting thethreshold detection to reach low miss detection rates impliesin a high increase on the false alarm.

10-6 10-4 10-2 100

Probability of false alarm

10-6

10-5

10-4

10-3

10-2

10-1

100

Pro

babi

lity

of m

iss

dete

ctio

n

Theo. pilot = -130 dBm

Emp. pilot = -130 dBm





(a) AWGN channel

10-6 10-4 10-2 100

Probability of false alarm

10-6

10-5

10-4

10-3

10-2

10-1

100

Pro

babi

lity

of m

iss

dete

ctio

n

Theo. pilot = 5 dBm

Emp. pilot = 5 dBm

Theo. pilot = 15 dBm

Emp. pilot = 15 dBm

Theo. pilot = 25 dBm

Emp. pilot = 25 dBm

(b) Rayleigh fading plus path loss channel

Fig. 4. ROC curves obtained via MCS and by theoretical analysis, assumingdifferent ρpilot values.

The second set of simulations consists in evaluating thepilot power ρpilot and signatures length L impact on the falsealarm and miss detection of the complete detection scheme,with the AMP algorithm estimation and the MAP decisionrule. This process was performed taking ρpilot ∈ [−130,−120]dBm for the channel case 1 and ρpilot ∈ [5, 25] dBm for thechannel case 2, and signatures length L ∈ [400, 1600] aimingto examine the detection scheme performance in terms of the

6

-130 -129 -128 -127 -126 -125

pilot (dBm)

10-4

10-3

10-2

10-1

100P

roba

bilit

y of

mis

s de

tect

ion

Theo. L = 400Emp. L = 400Theo. L = 800Emp. L = 800Theo. L = 1200Emp. L = 1200Theo. L = 1600Emp. L = 1600

(a) Probability of miss detection

-130 -129 -128 -127 -126 -125

pilot (dBm)

10-5

10-4

10-3

10-2

Pro

babi

lity

of fa

lse

alar

m


(b) Probability of false alarm

Fig. 5. Probability of miss detection and false alarm in AWGN channelvarying the pilot power ρpilot for different pilot sequence length L.

error probabilities with different setup for the training signals.The Fig. 5 presents the obtained values for the probabilitiesof miss detection and false alarm under AWGN channel.Observing both curves set, as expected, one can infer thatthe scheme performance increases with the power and lengthof the signatures. The improvement on the performance withthe power increasing is related to the error detection, whichhas a part related to the additive noise variance. Besides,the improvement caused by the increasing on the signaturelength is justified by the increase on the ratio δ = L

N , whichhas influence on the MSE estimate, as one can see on thesecond part of (15). In compressed sensing, the δ ratio iscalled undersampling factor and, in the algebraic approach,increasing it implies a raising on the equations number inthe undetermined linear system in (1). The lower the systemundetermination degree, meaning higher the undersamplingfactor δ, and smaller is the system degrees of freedom,enhancing the estimate quality.

Note that when L = 400 in Fig. 5(b), increasing ρpilotthe false alarm probability exhibits an inverted behavior, beenjustified by the MAP decision rule. The MAP rule aims tominimise the error probability defined in (17) instead the

probability of the two possible errors independently. For thisreason, in some cases, the rule reinforces the rate of an specificerror class, and can even decreases the another one, aiming tominimise the total error probability.

Fig. 6 depicts the probabilities of miss detection and falsealarm varying the power and the length of the pilots for thecase of Rayleigh channels. In a same way of AWGN channel,the power and pilot length increasing improve the performanceof the detection scheme. Increasing the pilot power, we havereduced the estimate error, given that it has a part influencedby the noise variance. In addition, even with the interferenceoccasioned by non-orthogonal signatures, we have addressedthe activity detection problem on the Rayleigh channel offeringerror probabilities scalable with the signals length L. Thisscalability is due to the ratio δ = L/N impact on the estimateerror, corroborating Eq. (15), i.e., the variance of estimationin (13) is reduced at rate δ−1.

5 10 15 20 25

pilot (dBm)

10-2

10-1

Pro

babi

lity

of m

iss

dete

ctio

n


(a) Probability of miss detection

5 10 15 20 25

pilot (dBm)

10-5

10-4

10-3

Pro

babi

lity

of fa

lse

alar

m


(b) Probability of false alarm

Fig. 6. Probability of miss detection and false alarm in Rayleigh fading pluspath loss channel varying the pilot power ρpilot for different pilot sequencelength L.

The numerical results depicted in Fig. 7 was aimed todemonstrate the error probability dependence on the detectionthreshold θ and different values for the pilot sequences powerand considering both channel types. Fig. 7(a) depicts the errorprobability for the AWGN channel, while 7(b) exhibis the

7

error probability for Rayleigh channels. As reference, the errorprobabilities achieved by the MAP and maximum likelihood(ML) decision rules are indicated by the dashed horizontallines. Initially, the error probability decreases as θ increases,reaching the minimum error probability and reversing itsbehavior, increasing the error probability as the threshold rises.

Now, considering both limit situation, i.e. almost all de-vices active or inactive. In such extreme situations, the errorprobability when we choose big θ values is lower than whenwe choose small ones, for both kind of channels, due to thesporadic device activity, i.e. ε� 1, in the first situation. Hence,consider that all the terminals are inactive, i.e. θ →∞, resultsin a better error probability than consider all the devices active(θ → −∞).

Comparing the curves for different pilot power, one canconclude that the MAP decision reaches the minimum prob-ability error, once it represents the optimal solution. Whenρpilot = −130 dBm, the ML criterion is inefficient, being moreprofitable consider that all the terminals are active during thecontention period. As the power grows, the sub-optimal MLcriterion has its performance enhanced.

-0.5 0 0.5 1 1.5

10-1

100

Pro

babi

lity

pilot = -130 dBm

Error prob.MAPML

-0.5 0 0.5 1 1.5

10-2

10-1

100 pilot = -125 dBm

-0.5 0 0.5 1 1.5

10-5

10-4

10-3

10-2

10-1

100 pilot = -120 dBm

(a) AWGN channel

10-8 10-6

10-2

10-1

100

Pro

babi

lity

pilot = 5 dBm

Error prob.MAPML

10-5

10-3

10-2

10-1

100 pilot = 15 dBm

10-5

10-4

10-3

10-2

10-1

100 pilot = 25 dBm

(b) Rayleigh channel

Fig. 7. Probability of error depending on the detection threshold and fordifferent transmission power values. a) AWGN channels; b) Rayleigh channels

Specifically in Fig. 7(b), the error probability versus θ is

depicted for different values of the pilot power, assumingthe Rayleigh fading plus path loss channel. Again, the MAPcriterion achieves the lower value as the occurred in theadditive noise model. In the similar way, the ML decisionexhibits performance degradation under reduced pilot powers.The error probability decreases as θ grows, and increases afterreached its minimum value. One can observe a remarkabledifference in the error probabilities by selecting extreme re-duced or higher threshold values. This is due to the intermittentactivity trend of the terminals, which results in a highernumber of inactive devices than the active ones.

V. CONCLUSION

On this work, we address the devices activity detectionproblem related to the non-orthogonal grant-free access pro-tocols at the mMTC service. We have presented one schemearchitecture to detect the terminal activity constituted by anestimation step adopting the AMP algorithm and the softthresholding denoiser and a detection step applying the MAPdecision rule.

Throughout the study, we have developed analytical ex-pressions for the detector performance under two differentchannel models, the AWGN and the Rayleigh fading pluspath loss channels. In addition, we have demonstrated that theMAP decision rule can be implemented with low complexityevaluating suitably the decision threshold.

The numerical results obtained have demonstrated that theproposed detection scheme presents detection probability ratessufficient to cope the mMTC scenario. Whereas the ROCcurves have evidenced that, under the Rayleigh fading pluspath loss channel, the detection scheme has higher sensibilityto the false alarm probability than the miss detection one.Finally, we have concluded that the solution is scalable withthe signatures power and length whose, when are increased,minimises the probabilities of miss detection and false alarm.

ACKNOWLEDGMENT

This work was supported in part by the National Council forScientific and Technological Development (CNPq) of Brazilunder Grant 304066/2015-0, Fundação Araucária under Grant302/2012, and in part by State University of Londrina – ParanáState Government (UEL) (scholarship).

APPENDIX

A. PDF of Channel Coefficients, (4)

For the derivation of the channel coefficients’ statisticaldistribution we will take into account the assumptions below:

1) The terminals are uniformly distributed among the areaof a circular cell with radius R;

2) The minimum distance r between the central node andthe terminals (BS-MT).

From the previous premises, and based on [4] formulation,but herein including the far-field r minimum BS-MT distancehypothesis, we can write the cumulative distribution function

8

of the distances between the central node and the secondaryones as

FD(d) =

d2−r2R2−r2 , if r < d < R

0, if d < r

1, if d > R

(32)

where the r.v. D models the distances values. Taking thefirst derivative of F (d) relative to d gives us the pdf of thedistances,

fD(d) =

{2d

R2−r2 , if r < d < R

0, otherwise(33)

The path loss coefficient β is a monotonically decreasingfunction of the random variable D defined as

β = g(D) =

√k

Dγ(34)

So, the pdf of β can be evaluated as

fβ(β) = −fB[g−1(β)

] ∂g−1(β)

∂β

fβ(β) =

{4k2/γ

γ(R2−r2)β−4/γ−1, if

√kRγ < β <

√krγ

0, otherwise(35)

Considering that the Rayleigh fading coefficients are mod-eled by V ∼ CN (0, 1), the channel coefficients can berepresented by the random variable:

H = βV (36)

To compute the pdf of H , we will adopt the isomorphism[·] : C → R2, which relates a complex r.v. A + jB tothe random vector [AB]T with real components. Using theisomorphism on the random variables H and V , we define

[H] =

[HR

HI

], [V ] =

[VRVI

](37)

where the subscript R indicates the real part of the variableand I the imaginary one.

The pdf of the random variables H and V consist in thejoint probability density function of their real and imaginaryparts. For this reason, first we write the densities of thecomplex variables as the pdfs of their vectors supported bythe isomorphism:

fH(h) = fHR,HI (hR, hI) (38)

fV (v) = fVR,VI (vR, vI) (39)

From (36), (38) and (39), the joint cumulative densityfunction of the r.v. H is

FHR,HI (hR,hI) = P

(HR <

hRβ,HI <

hIβ, β > 0

)(40)

+ P

(HR >

hRβ,HI >

hIβ, β < 0

)

FHR,HI (hR, hI) = (41)∞∫

0

hR/β∫

−∞

hI/β∫

−∞

fVR,VI (vR, vI)fβ(β) dvI dvR dβ

+

0∫

−∞

∞∫

hR/β

∞∫

hI/β

fVR,VI (vR, vI)fβ(β) dvI dvR dβ

The expression for the density of H can be evaluated fromthe CDF by:

fH(h) =∂FHR,HI (hR, hI)

∂hR∂hI

fH(h) =

∞∫

−∞

fβ(β)

β2fV

(h

β

)dβ

fH(h) = a

c∫

b

Q(β) exp

(−|h|

2

β2

)dβ (42)

where a, b, c and Q(β) are given on (6) and (7).

B. MAP decision for the AWGN channel

To improve the readability, we will drop the subscripts nand t from the variables throughout the developments. TheMAP decision rule for our detection problem can be writtenas the test [16]:

P (X = 0)fX|X(x|X = 0)H0

≶H1

P (X 6= 0)fX|X(x|X 6= 0)

(43)The priors P (X = 0) and P (X 6= 0) are respectively 1 − εand ε, known from the terminals activity. Now, we need toevaluate the expressions for the conditional probability densityfunctions based on the pdf of X in (3) and the estimate modelfrom (13).

When X = 0, the estimate can be represented by therandom variable W = τV . Knowing that V ∼ CN (0, 1), theconditional density can be written as:

fX|X(x|X = 0) = fW (x)

fX|X(x|X = 0) =1

πτ2exp

(−|x|

2

τ2

)(44)

On the other hand, when the hypothesis H1 occur, i.e. X 6=0, the estimate can be expressed by the random variable

G = 1 + τV (45)

The pdf of G consists on the complex Gaussian pdf withvariance τ2 and mean 1. So, the conditional density will be

fX|X(x|X 6= 0) = fG(x)

fX|X(x|X 6= 0) =1

πτ2exp

(−|x− 1|2

τ2

)(46)

Thus, substituting the priors and the conditional densitiesinto (43) and taking the logarithm on both sides we can reachat the expression (19).

9

C. MAP decision for Rayleigh fading plus path loss channelFollowing the same approach used above, we will derive

the MAP decision finding the density functions of the estima-tions, based on the hypothesis occurrence. In the case of thehypothesis H0, the estimate can be expressed as the r.v.

W = τV (47)

So, the conditional pdf will be

fX|X(x|X = 0) = fW (x)

fX|X(x|X = 0) =1

πτ2exp

(−|x|

2

τ2

)(48)

When X 6= 0, the estimate is the sum of the randomvariables

U = H +W (49)

where H follows the distribution stated in (5).Using the isomorphism defined at the Appendix A on the

random variables G, U and H we get

[G] =

[GRGI

], [H] =

[HR

HI

], [W ] =

[WR

WI

](50)

With the complex random variables decoupled as randomvectors in R2, we can write the probability density functionsof H and W as the joint pdf of their real and imaginary parts,

fH(h) = fHR,HI (hR, hI) (51)

fW (w) = fWR,WI(wR, wI) (52)

So, the pdf of the r.v. G can be computed by the jointdensities with the expression:

fG(g) =

∞∫

−∞

∞∫

−∞

fHI ,HR(gR − x1, gI − x2) (53)

fWR,WI(x1, x2) dx1 dx2

which drives us to the result:

fX|X(x|X 6= 0) = fG(g)

fX|X(x|X 6= 0) = a

c∫

b

β2Q(β)

β2 + τ2texp

(− |x|2β2 + τ2

)dβ (54)

Substituting the calculated conditional densities and thepriors on (43), we can reach on the MAP decision rule forthe case 2 defined in (26).

REFERENCES

[1] E. d. Carvalho, E. Bjornson, J. H. Sorensen, P. Popovski, and E. G.Larsson, “Random access protocols for massive MIMO,” IEEE Com-munications Magazine, vol. 55, pp. 216–222, May 2017.

[2] E. Björnson, E. de Carvalho, J. H. Sørensen, E. G. Larsson, andP. Popovski, “A random access protocol for pilot allocation in crowdedmassive MIMO systems,” IEEE Transactions on Wireless Communica-tions, vol. 16, pp. 2220–2234, April 2017.

[3] L. Liu, E. G. Larsson, W. Yu, P. Popovski, C. Stefanovic, and E. de Car-valho, “Sparse signal processing for grant-free massive connectivity: Afuture paradigm for random access protocols in the internet of things,”IEEE Signal Processing Magazine, vol. 35, pp. 88–99, Sept 2018.

[4] Z. Chen, F. Sohrabi, and W. Yu, “Sparse activity detection for mas-sive connectivity,” IEEE Transactions on Signal Processing, vol. 66,pp. 1890–1904, April 2018.

[5] L. Liu and W. Yu, “Massive connectivity with massive MIMO part I:Device activity detection and channel estimation,” IEEE Transactionson Signal Processing, vol. 66, pp. 2933–2946, June 2018.

[6] L. Liu and W. Yu, “Massive connectivity with massive MIMO partII: Achievable rate characterization,” IEEE Transactions on SignalProcessing, vol. 66, pp. 2947–2959, June 2018.

[7] K. Senel and E. G. Larsson, “Joint user activity and non-coherent datadetection in mMTC-enabled massive MIMO using machine learningalgorithms,” in WSA 2018; 22nd International ITG Workshop on SmartAntennas, pp. 1–6, March 2018.

[8] L. Anitori, A. Maleki, M. Otten, R. G. Baraniuk, and P. Hoogeboom,“Design and analysis of compressed sensing radar detectors,” IEEETransactions on Signal Processing, vol. 61, pp. 813–827, Feb 2013.

[9] L. Anitori, M. Otten, W. van Rossum, A. Maleki, and R. Baraniuk,“Compressive CFAR radar detection,” in 2012 IEEE Radar Conference,pp. 0320–0325, May 2012.

[10] J. A. Tropp and S. J. Wright, “Computational methods for sparse solutionof linear inverse problems,” Proceedings of the IEEE, vol. 98, pp. 948–958, June 2010.

[11] A. Maleki and R. Baraniuk, “Least favorable compressed sensing prob-lems for first-order methods,” in 2011 IEEE International Symposiumon Information Theory Proceedings, pp. 134–138, July 2011.

[12] D. L. Donoho, A. Maleki, and A. Montanari, “Message-passing algo-rithms for compressed sensing,” Proceedings of the National Academyof Sciences, vol. 106, no. 45, pp. 18914–18919, 2009.

[13] A. Maleki, L. Anitori, Z. Yang, and R. G. Baraniuk, “Asymptoticanalysis of complex LASSO via complex approximate message passing(CAMP),” IEEE Transactions on Information Theory, vol. 59, pp. 4290–4308, July 2013.

[14] D. L. Donoho, A. Maleki, and A. Montanari, “Message passing algo-rithms for compressed sensing: I. motivation and construction,” in 2010IEEE Information Theory Workshop on Information Theory (ITW 2010,Cairo), pp. 1–5, Jan 2010.

[15] R. G. Gallager, Principles of Digital Communication. CambridgeUniversity Press, 2008.

[16] A. V. Oppenheim and G. C. Verghese, Signals, Systems and Inference.Pearson, 2016.

Documents

Aloca˘c~ao de Pot^encia e Protocolos de Acesso em Redes ...Ficha Catalogr a ca de Souza, Jo~ao Henrique Inacio Aloca˘c~ao de Pot^encia e Protocolos de Acesso em Redes de Comu-nica˘c~ao