Unsourced Random Massive Access with Beam-Space Tree Decoding

Consider an uplink single-cell cellular network consisting of $K_{\mathrm{total}}$ single-antenna users. The BS is equipped with $N_{\mathrm{r}}$ antennas and $N_{\mathrm{RF}}$ radio frequency (RF) chains such that $N_{\mathrm{RF}}<N_{\mathrm{r}}$, as shown in Fig. 1. Due to the sporadic user activity of mMTC, only a small number of $K_{\mathrm{a}}$ users are active in a transmisson process, i.e., $K_{\mathrm{a}}\ll K_{\mathrm{total}}$. Each active user has $B$ bits of information to be transmitted in a block-fading channel. According to [12, 14], the channel vector $\mathbf{h_{k}}$ from user $k$ to the BS can be written as

where $P_{c}$ denotes the total number of clusters and within the $p$-th cluster there are $Q_{p}$ sub-paths. $\beta_{p,q}$ and $\theta_{p,q}$ denote the gain and the the angle of arrival (AOA) of the $q$-th sub-path within the $p$-th cluster. For the uniform linear array (ULA), the $N_{\mathrm{r}}\times 1$ array steering vector $\mathbf{e}(\theta)$ can be expressed as

where $J(N_{\mathrm{r}})=\{i-\frac{N_{\mathrm{r}}-1}{2},i=0,1,2,\ldots,N_{\mathrm{r}}-1\}$, $\theta\in[-\frac{\pi}{2},\frac{\pi}{2}]$, $\lambda$ is the signal wavelength, and $d$ is the antenna spacing which is usually half of the signal wavelength.

To overcome the strong path loss in mmWave channels, a beamforming technique should be adopted. However, the BS cannot focus in any specific direction in grant-free random access. The reason is that even if the location of all potential users is stored at the BS, which users are active is not prior information known to the BS. Besides, due to the constraint of hardware implementations and large energy consumption of RF chains, we have $N_{\mathrm{RF}}<N_{\mathrm{r}}$. Therefore, many beamforming methods in existing works [27, 28] cannot be applied in our system directly as $N_{\mathrm{RF}}$ narrow beams cannot cover the whole beam space. In this paper, we give a beamforming method based on the widely used Discrete Fourier Transform (DFT) based beamforming codebook [27, 28], to overcome the strong path loss of mmWave channels in grant-free random access. Specifically, the DFT based beamforming codework, which is denoted by $\mathbf{W}$, can be writtern as

where

Consider the process of hardware implementations, the number of antennas is usually a multiple of the number of RF chains. Therefore, the $\frac{N_{\mathrm{r}}}{N_{\mathrm{RF}}}$ consecutive beamforming vectors can be grouped and summed together to form a new beamforming vector $\mathbf{\overline{w}}_{i}$, $i=1,2,\ldots,N_{\mathrm{RF}}$. $\mathbf{\overline{w}}_{i}$ is expressed as

where the parameter $\gamma$ is set to constrain the power of receive beamforming, i.e., $\|\mathbf{\overline{w}}_{i}\|^{2}_{2}=1$. Then the beamforming matrix $\mathbf{\overline{W}}$ is obtained, where $\mathbf{\overline{W}}$ is written as $\mathbf{\overline{W}}=[\mathbf{\overline{w}}_{1},\mathbf{\overline{w}}_{2},\ldots,\mathbf{\overline{w}}_{N_{\mathrm{RF}}}]\in\mathbb{C}^{N_{\mathrm{r}}\times N_{\mathrm{RF}}}$. By applying this beamforming method, the width of every beam is $\frac{\pi}{N_{\mathrm{RF}}}$, thus the $N_{\mathrm{RF}}$ beams can cover the whole beam space, which means that the signals coming from all directions can be received by the BS.

In a typical URA scenario, all the users share a common codebook $\mathbf{A}$, which is denoted by $\mathbf{A}=[\mathbf{a}_{1},\mathbf{a}_{2},\ldots,\mathbf{a}_{N}]\in{\mathbb{C}^{{L_{\mathrm{p}}}\times{N}}}$. The power of each codeword $\mathbf{a}_{n}\in{\mathbb{C}^{L_{\mathrm{p}}\times 1}}$ is constrained to 1, i.e., $\left\|{{\mathbf{a}_{n}}}\right\|_{2}^{2}=1$. Let $\delta_{n,k}\in\{0,1\}$ denote whether user $k$ transmits the codeword $\mathbf{a}_{n}$. $\delta_{n,k}$ can be written as

After receive beamforming at the receiver, the beam domain channel vector of the active user $k$ is denoted by ${\overline{\mathbf{h}}_{k}}={\mathbf{\overline{W}}^{\rm{H}}}{\mathbf{h}_{k}}=[\overline{h}_{k,1},\overline{h}_{k,2},\ldots,\overline{h}_{k,N_{\mathrm{RF}}}]^{\rm{T}}$. Also, the random noise vector is denoted by ${\overline{\mathbf{z}}}={\mathbf{\overline{W}}^{\rm{H}}}{\mathbf{z}}=[\overline{z}_{1},\overline{z}_{2},\ldots,\overline{z}_{N_{\mathrm{RF}}}]^{\rm{T}}$, where $\mathbf{z}$ is modeled by a complex circular Gaussian random vector with i.i.d. components, i.e., ${\mathbf{z}}\sim\mathcal{CN}(0,\sigma_{z}^{2}\mathbf{I})$. Then the received signal on the $b$-th beam can be written as

By summarizing all the $N_{\mathrm{RF}}$ samples in a transmission block, the received signal can be recast as

where $\mathbf{Y}=[\mathbf{y}_{1}^{\rm{T}},\mathbf{y}_{2}^{\rm{T}},\ldots,\mathbf{y}_{{N_{\mathrm{RF}}}}^{\rm{T}}]\in{\mathbb{C}^{{L_{\mathrm{p}}}\times{N_{\mathrm{RF}}}}}$, $\overline{\mathbf{H}}=[\overline{\mathbf{h}}_{1},\overline{\mathbf{h}}_{2},\ldots,$ $\overline{\mathbf{h}}_{{K_{\mathrm{total}}}}]^{\rm{T}}\in{\mathbb{C}^{{K_{\mathrm{total}}}\times{N_{\mathrm{RF}}}}}$, $\overline{\mathbf{X}}=\mathbf{\Delta}\overline{\mathbf{H}}\in{\mathbb{C}^{N\times{N_{\mathrm{RF}}}}}$ and $\mathbf{\Delta}=\{0,1\}^{N\times K_{\mathrm{total}}}$. The matrix $\mathbf{\Delta}$ contains only $K_{\mathrm{a}}$ non-zero columns each of which having a non-zero entry.

For the matrix ${\mathbf{X}}=\mathbf{\Delta}{\mathbf{H}}$, where $\mathbf{H}=[\mathbf{h}_{1},\mathbf{h}_{2},\ldots,$ $\mathbf{h}_{K_{\rm{total}}}]^{\rm{T}}$, the $i$-th row of such matrix is given as

The probability that ${\mathbf{X}}_{i,:}$ is identically zero is given by $(1-2^{-J})^{K_{\mathrm{a}}}$. Since $2^{J}$ is significantly larger than $K_{\mathrm{a}}$, the matrix ${\mathbf{X}}$ is row-sparse, which is shown in Fig. 2. The reason is that only a small number of users are active due to the sporadic traffic of users, i.e., $K_{\mathrm{a}}\ll K_{\rm{total}}$. For the same reason, the matrix $\overline{\mathbf{X}}$ is also row-sparse. Moreover, due to the lack of scattering in mmWave bands, the signal propagates from the transmitter to the receiver through a small number of path clusters. This leads to the sparsity of mmWave massive MIMO channels in the beam domain as well, i.e., the channel vector $\overline{\mathbf{h}}_{k}$ is sparse. Therefore, for the matrix $\overline{\mathbf{X}}$, the number of non-zero entries of its columns is less than that of ${\mathbf{X}}$, which is shown in Fig. 2. Note that the total number of users $K_{\rm{total}}$ plays no role in the matrix $\overline{\mathbf{X}}$. This means that if the matrix $\overline{\mathbf{X}}$ is recovered, only the codeword index is known to the BS, instead of the user’s ID, which leads to the so-called unsourced property.

Let $\mathcal{L}$ and $\mathcal{K}_{\mathrm{a}}$ denote the set of the recovered messages at the BS and the set of the active users, respectively. Each active user $k\in\mathcal{K}_{\mathrm{a}}$ expects to transmit $B$ bits of information, i.e., ${\mathbf{u}_{k}}={\{0,1\}^{B}}$. The performance in URA is evaluated by the probability of missed detection and false alarm, denoted by $p_{\mathrm{md}}$ and $p_{\mathrm{fa}}$ respectively, which can be given by:

and the error probability of the system is defined as

In this section, we first review the studies of the CCS scheme in [20] and then propose a URA scheme. In the CCS scheme, each active user partitions the message into several sub-blocks and adds parity bits. The CS techniques detect the sub-blocks transmitted by active users in all sub-slots. A tree-based algorithm then stitched these sub-blocks to recover the original messages.

The traditional tree decoder exploits the discriminating power of parity bits to stitch the sub-blocks together to form a valid message instead of the erroneous one. At any stage of a path during the decoding process, the sub-blocks meeting the parity constraints are attached to the path. Besides the valid sub-block, other attached sub-blocks are the ones that cannot be distinguished by the parity bits. These invalid sub-blocks may finally lead to an erroneous message output by the tree decoder. Notice that in all sub-slots, the sub-blocks sent by different users are received by different beams at the BS according to the location of the users and scatterers. Therefore, the discriminating power of beams can be exploited to distinguish the invalid sub-blocks that meet the parity constraints. By leveraging the beam dimension, the decoding process can be formulated as a problem of path search in the three-dimensional space, which is shown in Fig. 3.

To better describe the decoding process of the beam-space tree decoder with hard decision, Table I is given to summarize the important parameters encountered in this Section. Specifically, define the beam pattern of a sub-block as a set that contains the indices of the beams that receive the sub-block. Then different sub-blocks can be distinguished by their beam patterns. The beam pattern $\mathbf{f}_{k}^{(s)}$ is written as $\mathbf{f}_{k}^{(s)}=[f_{k,1}^{(s)},f_{k,2}^{(s)},\ldots,f_{k,N_{\mathrm{RF}}}^{(s)}]\in\{0,1\}^{1\times N_{\mathrm{RF}}}$. To get accurate beam patterns, assume the gains of the active beams obey a prior known Gaussian distribution, i.e., $\mathcal{N}(\mu_{1},\delta_{1}^{2})$, where an ”active” beam means that at least the signal from one user is received by the beam. And the gains of the inactive beams obey another known Gaussian distribution, i.e., $\mathcal{N}(\mu_{2},\delta_{2}^{2})$, where $\mu_{1}>\mu_{2}$ and $\delta_{1}>\delta_{2}$. For the gains of the inactive beams, as no signal is received or the signal experiences deep fading, $\mu_{2}$ is close to zero. For the gains of the active beams, $\delta_{1}$ is large as the signals experience random fading. Using these two prior distributions, the gains of the beams can be grouped into two classes. And for each class, the mean and variance of the samples are calculated and the prior distributions can be updated, i.e., $\mu_{1}\rightarrow\hat{\mu}_{1}$, $\mu_{2}\rightarrow\hat{\mu}_{2}$, $\delta_{1}\rightarrow\hat{\delta}_{1}$ and $\delta_{2}\rightarrow\hat{\delta}_{2}$. Then according to these updated distributions, we can give the decision rules of the beam patterns. Specifically, $f_{k,m}^{(s)}$ is obtained by $\hat{h}_{k,m}^{(s)}$, which is expressed as

where $\mathrm{P}_{i}(\left|\hat{h}_{k,m}^{(s)}\right|)=\frac{1}{\sqrt{2\pi}\hat{\delta}_{i}}e^{-\frac{\left(\left|\hat{h}_{k,m}^{(s)}\right|-\hat{\mu}_{i}\right)^{2}}{2\hat{\delta}_{i}^{2}}}$.

For this proposed beam-space tree decoder, take the decoding process of a certain user for example. At the first stage, a code tree is created and a detected sub-block in the first sub-slot becomes the root of the tree and forms the first path. The root sub-block is written as $\mathbf{m}_{c_{1}[1]}(1)$ and its beam pattern is $\mathbf{f}_{c_{1}[1]}^{(1)}$. At later stages, the sub-blocks that meet the parity and the beam pattern matching constraints are kept. By meeting the parity constraints, $\mathcal{T}_{s}[l]$ is written as

And $\mathcal{M}_{s}[l]$ is obtained by

After beam pattern matching, only the sub-blocks in $\mathcal{M}_{s}^{\rm{hd}}[l]$ are survived. $\mathcal{M}_{s}^{\rm{hd}}[l]$ can be written as

where $\mathcal{M}_{s}^{\rm{hd}}[l]\subseteq\mathcal{M}_{s}[l]$. Also, $\mathbf{f}_{i}^{(1)}{\mathbf{f}_{j}^{(s)}}^{\rm{T}}\neq 0$ means that the sub-blocks $\mathbf{m}_{i}(1)$ and $\mathbf{m}_{j}(s)$ are received by at least one same beam at the BS, then $\mathbf{m}_{i}(1)$ and $\mathbf{m}_{j}(s)$ have the probability to be transmitted by the same user. By beam pattern matching, the proposed beam-space tree decoder can reduce the number of surviving sub-blocks in each sub-slot, which improves the discriminating power of the decoder. A practical pruning process of this algorithm is shown in Fig. 4. The sub-block is received by several beams at the BS, which is shown in the beam pattern. For every candidate path at stage $s$, there are $2^{b_{s}}$ candidate sub-blocks in the common codebook $\mathbf{A}$ that meet the parity constraints according to the parity bits. A part of them are inactive, while another part of them are discriminated by the beam pattern matching. As shown in Fig .4, the lines of the 2-nd and the $2^{b_{3}}$-th candidate sub-blocks change from solid lines to dashed lines, which means that they are deleted, as there is no overlap between their beam patterns and the beam pattern of the root sub-block at stage 1.

Finally, the proposed beam-space tree decoder with hard decision is summarized and given in Algorithm 1. $\mathcal{F}_{s}$ is a set that contains the beam patterns of the sub-blocks detected in sub-slot s, where $\mathcal{F}_{s}$ is expressed as $\mathcal{F}_{s}=\{\mathbf{f}_{k}^{(s)}\;|\;k\in\mathcal{K}_{s}\}$.

As described above, the CS decoder cannot always detect all the transmitted sub-blocks because the received signals may experience deep fading. The loss of a sub-block by the CS decoder in any sub-slot finally leads to missed detection of the original message. This is because the traditional tree decoder and the beam-space tree decoder with hard decision just stitch the sub-blocks drawn from the output of the CS decoder. At any stage, according to the parity bits, the set of candidate sub-blocks can be obtained. At stage s, the tree decoder keeps the intersection between the candidate set and $\mathcal{L}_{s}$. In this proposed algorithm, we keep all the candidate sub-blocks and calculate the LLR values of them by implementing the MPA algorithm, which denotes the probability of whether the sub-blocks are transmitted. Then, we define a path metric to calculate the reliability of the consecutive sub-blocks and keep some reliable paths at every stage. Even if a sub-block in a sub-slot is missed, it is possible for the path to be reliable because the path metric measures the reliability of the entire path. Therefore, the purpose of packet loss recovery is achieved.

Specifically, take a user’s decoding process for example. At stage $s$ for the $l$-th path, the number of the candidate sub-blocks is $2^{b_{s}}$, and these sub-blocks are collected in the set $\mathcal{M}^{\prime}_{s}[l]$. $\mathcal{M}^{\prime}_{s}[l]$ is expressed as

where

The difference between $\mathcal{M}^{\prime}_{s}[l]$ and $\mathcal{M}_{s}[l]$ in (20) is that the candidate sub-blocks in $\mathcal{M}^{\prime}_{s}[l]$ are drawn according to the parity bits only, thus $\mathcal{M}_{s}[l]\subseteq\mathcal{M}^{\prime}_{s}[l]$. To reduce interference, only the received signals of those candidate sub-blocks are kept, which is denoted by $\widetilde{\mathbf{Y}}_{s}[l]\in\mathbb{C}^{N_{\mathrm{RF}}\times L_{\mathrm{p}}}$. $\widetilde{\mathbf{Y}}_{s}[l]$ is written as

where $k\in\{1,2,\ldots,N\}\backslash\mathcal{T}^{\prime}_{s}[l]$ means that $k$ is in the set $\{1,2,\ldots,N\}$ instead of $\mathcal{T}^{\prime}_{s}[l]$. Then a factor graph is formed, taking the corresponding codewords as variable nodes and beam resources as resource nodes. Let $K$ and $T$ denote the number of variable nodes and resource nodes. To exploit the beam division property, the active beams in the beam pattern of the root sub-block form the resource nodes. Then the remaining received signal is defined as $\widetilde{\mathbf{Y}}^{r}_{s}[l]\in\mathbb{C}^{\left\|\mathbf{f}_{c_{1}[1]}^{(1)}\right\|_{1}\times L_{\mathrm{p}}}$. A certain row of $\widetilde{\mathbf{Y}}^{r}_{s}[l]$ comes from the $j$-th row of $\widetilde{\mathbf{Y}}_{s}[l]$, where $j\in\{i\;|\;\mathbf{f}^{(1)}_{c_{1}[1],i}=1\}$. For the sake of simplicity, define $\mathbf{y}_{t}$ as the received signal at the $t$-th resource, $\hat{h}_{k,t}$ as the estimated channel gain between the user transmitting the $k$-th codeword and the BS at the $t$-th resource$,\mathbf{a}_{k}$ as the $k$-th possible codeword and $x_{k}\in\{0,1\}$ as a random variable that indicates whether the codeword $\mathbf{a}_{k}$ is transmitted. Then $\widetilde{\mathbf{Y}}^{r}_{s}[l]$ is written as $\widetilde{\mathbf{Y}}^{r}_{s}[l]=[\mathbf{y}_{1},\mathbf{y}_{2},\ldots,\mathbf{y}_{T}]$, where $\mathbf{y}_{t}$ can be expressed as

where

and $\mathbf{\xi}_{k,t}=[\xi_{k,t,1},\xi_{k,t,2},\ldots,\xi_{k,t,L_{p}}]$. To reduce the computational complexity, we resort to Gaussian Approximation (GA) as in [31], and approximate ${\xi_{k,t,j}}$ as a complex Gaussian-distributed random variable with mean $\mu_{{\xi_{k,t,j}}}$ and variance $\delta_{{\xi_{k,t,j}}}^{2}$, i..e., ${\xi_{k,t,j}}\sim\mathcal{CN}({\mu_{{\xi_{k,t,j}}}},\delta_{{\xi_{k,t,j}}}^{2})$. ${\mu_{{\xi_{k,t,j}}}}$ and $\delta_{{\xi_{k,t,j}}}^{2}$ can be expressed as

respectively, where

$L_{k\to t}$ is the log likelihood ratio (LLR) delivered from the $k$-th variable node to the $t$-th resource node. Also, $L_{t\to k}$ denotes the LLR delivered from the $t$-th resource node to the $k$-th variable node, which is written as

where

Besides, $L_{k\to t}$ is given as

Finally, $L_{k}$ can be expressed as

Denote $l^{(n)}$ as the new paths that are split from the $l$-th path. By implementing MPA, from path $l$ at stage s, we can obtain the LLRs of the candidate sub-blocks in $\mathcal{M}^{\prime}_{s}[l]$, which are written as $L_{s}[l^{(n)}],n=1,2,\ldots,2^{b_{s}}$. Learning from the way of list decoding [32], we define a path metric to calculate the reliability of the new branches from path $l$ at stage $s$. Specifically, the PM of the new branch $l^{(n)}$ is written as

where $L_{i}[l]$ denotes the LLR of the sub-block at stage $i$ in the path $l$. The decoder calculates the PM of all the branches from every candidate path and keep some reliable paths at every stage. And at the last stage, the decoder outputs the most reliable path as the recovered message.

However, this scheme is not suitable in the case that collision occurs. As mentioned above, active users select codewords from a common codebook $\mathbf{A}$. Even if the dimension of $\mathbf{A}$ is large, collisions may still occur. If the traditional tree decoder fixes a sub-block transmitted by two active users at the first stage, then the decoder finally outputs two valid tree messages. According to [25], we give $\mathbf{E}\{C_{k,s}\}$ as the average number of collisions of $k$ users on consistent s sub-blocks started from the first one, which is written as

The collision of more than two users is ignored because the number is usually much smaller than 1. As $s$ grows, the collision can be ignored when $k=2$. In other words, it is impossible for the valid messages of the collision users to be the new branches of the same candidate path. However, when the depth of a code tree grows, the LLR of a sub-block has less impact on the PM of the entire path. Therefore, the remaining paths at stage s may all come from the new branches of the most reliable path at stage $s-1$, leading to missed detection. Actually, there is no need to keep all new branches from a candidate path because the valid messages of collision users come from different candidate paths. Denote $L_{\mathrm{split}}$ as the number of splitting paths, which means that only $L_{\mathrm{split}}$ new branches from a candidate path are kept according to the PM. Then for the current stage, keep $L_{\mathrm{save}}$ most reliable paths, where $L_{\mathrm{save}}>L_{\mathrm{split}}$. This pruning process is shown in Fig. 5. The number of candidate sub-blocks at stage $s$ is $2^{b_{s}}$, which is equivalent to the process in Fig. 4. At stage $s$, for the new branches of a path, a factor graph is created to implement the MPA algorithm and give the candidate sub-blocks LLRs. Then the most reliable $L_{\mathrm{split}}$ paths are kept, and others are deleted, which is shown in Fig. 5 that the lines of those deleted sub-blocks change from solid to dashed. Finally at stage $s$, for the $2^{b_{s-1}}L_{\mathrm{split}}$ paths, the most reliable $L_{\mathrm{save}}$ paths are kept and others are deleted. $L_{\mathrm{split}}$ is chosen according to the trade-off between the computational complexity and decoding performance of the decoder.

At the last stage, the number of messages output by the decoder cannot be determined because whether a collision occurs is unknown to the decoder. Notice that the traditional tree decoder outputs all the paths meeting the parity constraints as valid messages. When a collision occurs, the traditional tree decoder outputs several paths as the recovered messages. Besides, more parity bits are pushed towards later stages to reduce the probability of error according to [20]. Thus, we exploit the discriminating power of the parity bits at later stages to output the results of the beam-space tree decoder with soft decision. To summarize, list decoding is implemented at the former $S^{\prime}$ stages to keep the missed sub-blocks, and the sub-blocks that are full of parity bits are exploited to prune the erroneous paths at the latter $S-S^{\prime}$ stages.

However, due to the loss packet recovery, the missed detection rate decreases while the false alarm rate increases. The reason is that some undetected sub-blocks may be kept in the decoding process. Some of them are not transmitted actually, which may lead to false alarm. As the valid messages from collision users are not similar with each other, the invalid messages can be discriminated. Specifically, define a similarity metric $\mathrm{P_{s}}({\mathbf{u}_{i}},{\mathbf{u}_{j}})$, which is denoted by

where $\mathbb{I}(\cdot)$ is the indicator function, $\mathbf{u}_{i}$ and $\mathbf{u}_{j}$ are two messages output by a code tree. Calculate every pair of the outputs from a code tree, if $\mathrm{P_{s}}({\mathbf{u}_{i}}$, ${\mathbf{u}_{j}})>\tau$, then keep the more reliable one according to the PM, otherwise keep both, where $\tau$ is a threshold. By leveraging the similarity metric, the invalid messages meeting the parity constraints are deleted. The beam-space tree decoder with soft decision is summarized and given in Algorithm 2.

The performance of our proposed URA system is connected with the reliability of CS techniques in each sub-slot and the efficiency of message stitching across different sub-slots. In the remainder of this section, we ignore the collision that different active users share a sub-block in the first sub-slot.

Take the decoding process of user $k$ for example. Let $p_{\rm{cs}}$ be the probability that at least one sub-block of user $k$ is not output by the CS decoder, $p_{\rm{tree}}$ be the probability of error, $p_{\rm{tree}}^{\mathrm{md}}$ be the probability of missed detection, and $p_{\rm{tree}}^{\mathrm{fa}}$ be the probability of false alarm. $p_{\rm{tree}}$ is written as

where $p_{\overline{cs}}=1-p_{\rm{cs}}$, which denotes the probability that the CS decoder is error-free. $p_{\rm{tree}|\overline{cs}}^{\mathrm{md}}$ denotes the probability that the message of user $k$ is not output by the tree decoder in the case that the CS decoder is error-free.