Joint Device Detection, Channel Estimation, and Data Decoding with Collision Resolution for MIMO Massive Unsourced Random Access

Next generation multiple access (NGMA) aims to support massive connectivity scenarios for many envisioned Internet of Things (IoT) applications, e.g. manufacturing, transportation, agriculture, and medicine, to be efficiently and flexibly connected [5, 2, 4, 6, 1, 3]. A generic scenario for IoT connectivity involves a massive number of machine-type connections [2], known as the massive machine-type communication (mMTC), which is one of the main use cases of the fifth-generation (5G) and beyond [3]. Compared to human-type communications (HTC), MTC has two distinct features: sporadic traffic and short packet communication. The sporadic access means that for any given time, for the sake of long battery life and energy saving, only a small fraction within a huge number of devices are active for data transmission [4]. While the small data payloads result in a fall of spectrum efficiency and an increase of latency when applied with traditional multiple access protocols. In this regard, a number of scalable random access schemes have been investigated in the content of massive connectivity. Conceptually, there are two lines of work for that end, namely, individual and common codebook-based approaches, respectively.

In the spirit of the individual codebook based approach, each device is equipped with a unique codebook for the identification conducted by the base station (BS) [4, 7]. Since the BS is interested in the IDs of devices, this framework can be referred to as sourced random access (SRA). A typical transmission process includes two phases in SRA, namely, training and data transmission, respectively. In the training phase, the BS conducts the task of device activity detection (DAD) and channel estimation (CE) based on the pre-allocated unique pilot sequences transmitted by active devices, while the data transmission is performed in the following phase. The task of DAD-CE can be modeled as the compressed sensing (CS) problem and there have been quantities of algorithmic solutions for this issue. Among these CS recovery techniques, the approximate message passing (AMP) algorithm, which is first proposed in [8] for the single measurement vector (SMV) based problem, exhibits great performance in terms of accuracy and complexity. Since the publication of [8], there have been vast variants based on the AMP algorithm, such as multiple measurement vector (MMV) AMP [4], generalized MMV (GMMV) AMP [9], orthogonal AMP (OAMP) [10], generalized AMP (GAMP) [11] and many other works. Another line of work is based on the belief propagation (BP) algorithm [12], which models the problem as a graph and iteratively calculates the messages among different nodes [13, 14, 15, 16]. Thanks to the consistency of the message updating rules, the messages can always be jointly updated within iterations to obtain improved performance. However, the premise of these algorithms is that each device should have a unique pilot sequence. As we jump out of these algorithmic solutions and go back to the essence of the individual codebook, we find this is inapplicable to assign each device a unique pilot in the mMTC scenario with a huge amount of potential devices. Meanwhile, it is a waste of resources especially with sporadic traffic. To mitigate this issue, the study on the framework of common codebooks is rapidly developed.

As opposed to the case of individual codebooks, active devices choose codewords from a common codebook for their messages. In this regard, the task of BS is only to produce the transmitted messages regardless of the corresponding IDs, thus leading to the so-called unsourced random access (URA). The main difference between URA with other grant-based and grant-free random access protocols is that the BS does not perform device identification but only decodes the list of active device messages up to permutations [3]. Conceptually, there are two distinct advantages for this novel framework: $\left.i\right)$ the BS is capable of accommodating massive devices, since all devices share the common codebook instead of being assigned unique preamble sequences as in traditional schemes. $\left.ii\right)$ No device identification information is needed to be embedded in the transmitted sequence. As such, the overhead will be reduced, contributing to improved efficiency. The study on URA is first reported in [17], in which Polyanskiy considered the scenario of a massive number of infrequent and uncoordinated devices and discussed a random coding existence bound in the Gaussian multiple-access channel (GMAC). Since the publication of [17], there have been many works devoted to approaching that bound [18, 19, 20, 21, 23, 24, 25, 26]. A low complexity coding scheme is investigated in [18]. Based on the combination of compute-and-forward and coding for a binary adder channel, it exhibits an improved performance compared with the traditional schemes, such as slotted-ALOHA and treating interference as noise (TIN). However, the size of the codebook increases exponentially with the blocklength, resulting in difficulty in achieving that underlying bound. To mitigate this issue, a slotted transmission framework is proposed in [19], referred to as the coded compressed sensing (CCS) scheme. This cascaded system includes inner and outer codes. The outer tree encoder first splits the data into several slots with parity bits added. The CS coding is then employed within each slot to pick codewords from the codebook. The blocklength, as well as the size of the codebook in each slot, are greatly reduced, thus leading to a relaxation of the computational burden. On the receiver side, the inner CS-based decoder is first utilized to recover the slot-wise transmitted messages within each slot. The outer tree decoder then stitches the decoded messages across different slots according to the prearranged parity. This structure is inherited by the later works in [20, 21], where the authors exploit the concept of sparse regression code (SPARC) [22] to conduct the inner encoding and decode it with the AMP algorithm. Some other coding schemes for URA are also reported in [23, 24, 25, 26]. The polar coding schemes based on TIN and successive interference cancellation (SIC) are investigated in [23, 24]. In [25, 26], the author consider a hierarchical framework, where the device’s data is split into two parts. A portion of the data is encoded by a common CS codebook and recovered by the CS techniques, while the rest is encoded by the low-density parity check code (LDPC) [27] with the key parameters conveyed in the former part. Besides the above works considering the GMAC, there are also works in the fading channel [28, 29, 30].

Besides the above works considering a single receive antenna at the BS, the study of massive URA in multiple-input multiple-output (MIMO) systems has also drawn increasing attention. The BS equipped with multiple antennas provides extra dimensions for the received signal, thus offering more opportunity for signal detection and access of a massive number of devices. A coordinated-wise descend activity detection (AD) algorithm is proposed in [31, 32], which finds the large-scale fading coefficients (LSFCs) of all the devices (coordinates) iteratively. The authors adopt a concatenated coding scheme with the aforementioned tree code as the outer code, and a non-Bayesian method (i.e., maximum likelihood (ML) detection) is leveraged as the inner decoder based on the covariance of the received signal, referred to as the covariance-based ML (CB-ML) algorithm. However, the performance of the CB-ML algorithm degrades dramatically when the number of antennas is less than that of the active devices. There are also some improvements to this algorithm in terms of complexity or accuracy [33, 34]. The slotted transmission framework proposed in [33] eliminates the need for concatenated coding. That is, no parity bit is added within each slot and the slot-wise messages can be stitched together by clustering the estimated channels. However, the channels in [33] are assumed to be identically distributed over all the slots, which is difficult to hold in practice. Besides, the collision in codewords (more than one device chooses the same codeword) will lead to a superimposition of the estimated channels, resulting in a failure of the stitching process. Currently, the design of an efficient collision resolution scheme in URA remains missing. In [34], a more efficient coordinate selection policy is developed based on the multi-armed bandit approaches, leading to a faster convergence than the CB-ML algorithm. Nevertheless, these slotted transmission frameworks, such as CB-ML and its variants, all map a piece of data within each slot to a long transmitted codeword based on the CS coding, resulting in low efficiency. In this regard, the algorithmic design for the MIMO massive URA with high efficiency and accuracy remains missing.

In this paper, we investigate a two-phase transmission scheme for MIMO massive URA, where the device’s transmitted data is split into two phases with CS and LDPC coded, respectively. In this framework, no parity bits are needed to be embedded in the CS phase, and the data is encoded linearly in the LDPC phase instead of being mapped to a long codeword. As such, it exhibits higher efficiency and lower latency than the aforementioned slotted transmission scheme. The existing schemes considering this framework all focus on the single-antenna case. For instance, Polar coding [24] and LDPC coding schemes [25, 26] consider the GMAC with perfect channel state information (CSI) at the BS. In this regard, the above channel coding schemes can obtain satisfying performance. However, such an assumption cannot be established under the MIMO case. Besides, because of the massive connectivity and sporadic traffic of devices, the positions of active devices in the estimated equations are not determined. Consequently, conventional linear receivers, such as zero-forcing (ZF), are not applicable. Moreover, compared with the fading channel models [28, 29, 30] where the channel of each device is a scalar, in MIMO, the channel is a vector, and elements among antennas share the same activity. Therefore, elements in the channel vector should be estimated jointly rather than separately, of which the distribution is formulated as a multi-dimensional Bernoulli-Gaussian distribution in this paper. In this regard, the conventional estimators, such as the minimum mean square error (MMSE) estimation or the maximum a posteriori (MAP) estimation, are hard to carry out straightforwardly. Specifically, it is computationally intractable to obtain a precise posterior distribution, since it involves marginalizing a joint distribution of the activity and channel with high dimensions.

Another challenge for the proposed scheme in the MIMO case is activity detection. We note that whether in the GMAC [24, 25, 26] or fading channel [28, 29, 30] in the single-antenna case, the device activity can be directly detected. For instance, since the device’s channel is a scalar in the fading channel, it can be simply determined to be active when the estimated channel is non-zero or larger than a given threshold. However, it will be much involved in MIMO because there are multiple observations of the activity in the estimated channel vector. The existing works, such as [9], make a hard decision based on the energy of the channel and [33] considers the LLR at each antenna separately and sums them to obtain the final decision. However, the threshold for the decision is hard to obtain in practice and the distribution of the channel is not utilized in [9]. Although [33] considers the channel distribution and gives a closed-form expression for activity detection, the nature that channels at each antenna share the same activity is not considered.

Besides, the LDPC code is efficient but sensitive to the CE results. Therefore, the overall performance is limited by the accuracy of CE. Moreover, with the presence of collision in URA, if more than one device chooses the same codeword in the CS phase, the corresponding channels will be superimposed and thus the subsequent LDPC decoding process will fail.

To cope with the arising issues, based on the message passing (MP) algorithm, we propose the Joint DAD-CE algorithm to conduct the task of joint activity detection and channel estimate in the CS phase, and MIMO-LDPC-SIC Decoding algorithm for data decoding embedded in the LDPC phase. Moreover, to further improve the performance, we propose the Joint DAD-CE-DD algorithm to jointly update the messages in these two phases by utilizing the belief of each other. Finally, we propose a collision resolution protocol to address the collision in URA. The key and distinguishing features of the proposed algorithms are listed below.

• •

  Based on the principle of the BP algorithm, we develop a low-complexity iterative MP algorithm to decode the two parts of data. For the CS phase, we investigate the Joint DAD-CE algorithm to recover part of the data embedded in the device activities, the interleaving patterns, and channel coefficients, which are the key parameters for the remaining data. Specifically, we derive a close-form expression for DAD by utilizing the joint distribution of the channel among antennas. Combined with SIC and in the spirit of interleave-division multiple access (IDMA) [35], we elaborate on the MIMO-LDPC-SIC Decoding algorithm to decode the remaining data embedded in the LDPC phase. In addition to complexity reduction, the proposed algorithm exhibits a substantial performance enhancement in terms of accuracy and efficiency compared to the state-of-the-art CB-ML algorithm.

• •

  Thanks to the consistency of the MP algorithm, we propose the Joint DAD-CE-DD algorithm to further improve the performance. The proposed algorithm suggests a paradigm connecting the two parts. That is, messages in the decoding process of CS and LDPC parts can be jointly updated by utilizing the belief of each other, thus leading to improved performance. We employ the correctly decoded codewords as soft pilots to conduct CE jointly with the codewords in the CS phase, which contributes to improved accuracy of the estimated channel. Combined with the SIC method, the accuracy of the residual signal can be improved, leading to the enhanced decoding performance.

• •

  Under the current framework based on the common codebook, a collision happens if there are more than one device having the same preamble, which leads to a superimposition of the estimated channels. Accordingly, the superimposed channel will cause a failure in the LDPC decoding process. To this end, we propose a collision resolution protocol based on the energy detection (ED) and sliding window protocol (SWP). Succinctly, the ED is performed on the estimated channel of each device to find out the superimposition. Then, the BS broadcasts the indexes of the superimposed channels to all devices. Afterwards, the devices in collision slide the window in the data sequence and the CS coding is again performed for retransmission.

The rest of the paper is organized as follows. In Section II, we introduce the system model for MIMO massive URA . In Section III, we implement the two-phase encoding scheme and the collision resolution protocol is developed in Section IV. Then, we elaborate on the low-complexity iterative decoding algorithm based on BP and explain the joint update algorithm in Section V. After verifying the numerical results and analyzing the complexity in VI, we conclude the paper in Section VII.

Unless otherwise noted, lower- and upper-case bold fonts, $\bm{x}$ and $\bm{X}$, are used to denote vectors and matrices, respectively; the $(m,n)$-th entry of $\bm{X}$ is denoted as ${X}_{m,n}$; $\bm{X}_{i,:}$ denotes the $i$-th row of $\bm{X}$; $\{\cdot\}^{*}$ denotes the conjugate of a number; $\{\cdot\}^{T}$ and $\{\cdot\}^{H}$ denote transpose and conjugate transpose of a matrix, respectively; $\mathbb{E}\{\cdot\}$ and $\text{Var}\left\{\cdot\right\}$ denote the statistical expectation and variance, respectively; $\bm{X}\sim\mathcal{CN}(\bm{x};\bm{\mu},\bm{\Sigma})$ means that the random vector $\bm{x}$ follows a complex Gaussian distribution with mean $\bm{\mu}$ and auto-covariance matrix $\bm{\Sigma}$; $\{\cdot\}!$ denotes the factorial; $\left[1:M\right]$ denotes the set of integers between $1$ and $M$; $\mathcal{L}\backslash l$ denotes the entries in set $\left\{1,2,\cdots,L\right\}$ except $l$; $\text{Re}(\cdot)$ and $\text{Im}(\cdot)$ denote the real and imaginary parts of a complex number, respectively; $\lceil\cdot\rceil$ denotes ceiling; $i$ is the imaginary unit (i.e., $i^{2}=-1$).

The URA fashion is considered in this phase. Let $\mathbf{A}\in\mathbb{C}^{L_{p}\times 2^{B_{p}}}$ denote the common codebook shared by all the devices. That is, the columns of $\mathbf{A}=\left[\bm{a}_{1},\bm{a}_{2},\cdots,\bm{a}_{2^{B_{p}}}\right]$ form a set of codewords with power constraint $\left\|{{\mathbf{a}_{i}}}\right\|_{2}^{2}=L_{p}$, from which each active device chooses in order to encode its ${B_{p}}$ bits of information. With a slight abuse of notation, let $\bm{v}_{k}^{p}$ denote the first $B_{p}$ bits of device $k$’s binary message, i.e., $\bm{v}_{k}^{p}\triangleq\bm{v}_{k}(1:B_{p})\in\left\{0,1\right\}^{B_{p}}$. To apply the encoding scheme, we convert $\bm{v}_{k}^{p}$ into the $\ell_{1}$-norm binary vector $\tilde{\bm{v}}_{k}^{p}\in\left\{0,1\right\}^{2^{B_{p}}}$, in which a single one is placed at the location $i_{k}$. The value $i_{k}$ of binary sequence $\bm{v}_{k}^{p}$ is obtained by regarding it as an integer expressed in radix-$2$ (plus one), which we write as $i_{k}=\left[\bm{v}_{k}^{p}\right]_{2}\in\left[1:2^{B_{p}}\right]$. Then, the coded sequence is obtained by taking the transpose of the $i_{k}$-th column of $\bm{A}$, which we denote by $\bm{a}_{i_{k}}^{T}$. This facilitates the CS architecture, which maps the information to an elementary vector $\tilde{\bm{v}}_{k}^{p}$, according to which the corresponding codeword is selected from a fixed codebook. The corresponding received signal can be written as

where $\phi_{k}$ is the device activity indicator, as defined in (2). The matrix form of (6) is given by

where $\mathbf{A}\in\mathbb{C}^{L\times 2^{B_{p}}}$ is the common codebook shared by all devices. $\mathbf{\Gamma}\in{\left\{{0,1}\right\}^{{2^{B_{p}}}\times{K_{tot}}}}$ denotes the binary selection matrix. For each active device $k\in\mathcal{K}_{a}$, the corresponding column $\bm{\Gamma}_{:,k}$ is all-zero but a single one in position $i_{k}$, while for all $\mathcal{K}_{tot}\backslash\mathcal{K}_{a}$ the corresponding column $\bm{\Gamma}_{:,k}$ is all zeros. $\tilde{\bm{H}}=\left[\tilde{\bm{h}}_{1},\cdots,\tilde{\bm{h}}_{K_{tot}}\right]^{T}\in\mathbb{C}^{K_{tot}\times M}$ corresponds to the MIMO channel coefficient matrix. We note that the number of total devices $K_{tot}$ plays no role in URA. In order to get rid of this variable, with slight abuse of notation we define the modified activity indicator and selection matrix as $\phi_{r}=\sum\nolimits_{k\in\mathcal{K}_{a}}{\gamma_{r,k}}$ and $\bm{\Phi}=\text{diag}\left\{\phi_{1},\cdots,\phi_{2^{B_{p}}}\right\}$, respectively, where $\gamma_{r,k}$ is the $(r,k)$-th entry of $\bm{\Gamma}$. Correspondingly, the modified channel is ${\bm{H}}=\left[\bm{h}_{1},\cdots,\bm{h}_{2^{B_{p}}}\right]$ with $\bm{h}_{r}=\sum\nolimits_{k\in{\mathcal{K}_{a}}}{\gamma_{r,k}\tilde{\bm{h}}_{k}}$. Hence, (7) can be written as

Let $\bm{X}=\bm{\Phi}\bm{H}=\left[\bm{x}_{1},\cdots,\bm{x}_{2^{B_{p}}}\right]^{T}$. The goal for the BS in the CS phase is to detect the non-zero positions of the selection matrix $\bm{\Phi}$ and the corresponding channel vectors by recovering $\bm{X}$ based on the noisy observation $\bm{Y}$. Since $\bm{X}$ is row sparse, i.e., many $\bm{x}_{n}$ are zero, such reconstruction problem can be modeled as the CS problem [4]. Once $\bm{\Phi}$ is recovered, the message indicators of active devices $\left\{i_{k},\forall k\in\mathcal{K}_{a}\right\}$ are also recovered. Moreover, $i_{k}$ acts as the parameter of the LDPC code, since it determines the interleaving pattern of the data in the LDPC phase. Considering the fact that the $B_{p}$ bits of message carries key parameters for the latter phase, we name it the preamble. We note that it is different from the preamble in the traditional grant-free scenario, which is a pure pilot with no data embedded.

Likewise, let $\bm{v}_{k}^{c}\triangleq\bm{v}_{k}(B_{p}+1:B)\in\left\{0,1\right\}^{B_{c}}$ denote the remaining $B_{c}$ information bits of device $k$. $\bm{v}_{k}^{c}$ is first encoded into an LDPC code $\bm{b}_{k}^{c}\in\left\{0,1\right\}^{\tilde{L}_{c}}$, which is determined by the LDPC parity check matrix $\bm{C}$ with size $\left(\tilde{L}_{c}-B_{c}\right)\times\tilde{L}_{c}$. We note that in the decoding process, if $\hat{\bm{v}_{k}^{c}}$ is a valid codeword, then $\text{mod}\left(\bm{C}\hat{\bm{v}}_{k}^{c},2\right)=0$. $\bm{b}_{k}^{c}$ is then modulated to $\bm{s}_{k}^{c}$. We adopt a sparse spreading scheme introduced in [25]. That is, $\bm{s}_{k}^{c}$ is zero-padded into a length $L_{c}$ vector $\tilde{\bm{s}}_{k}^{c}$

We then employ the index representation $i_{k}$ to permute the ordering of $\tilde{\bm{s}}_{k}^{c}$. This is implemented by a random interleaver $\pi_{i_{k}}$ with interleaving pattern $i_{k}$. As mentioned in [26], the purpose for permuting the codewords is to decorrelate the random access interference from other devices. This is similar to the IDMA scheme since the interleaving patterns for most of the devices are different because of the distinctive indices $i_{k}$. Hence, $\bm{v}_{k}^{c}$ is finally encoded to $\pi_{i_{k}}\left(\tilde{\bm{s}}_{k}^{c}\right)$. Appending it to the coded message in the CS phase yields the final codeword $\bm{x}_{k}$:

The received signal including both the CS and LDPC phases is given by

where $\bm{h}_{i_{k}}$ is assumed to follow independent quasi-static flat fading within the above two phases in this paper. The goal for the BS is to recover $\left\{\bm{v}_{k},\forall k\in\mathcal{K}_{a}\right\}$ based on the received signal $\bm{Y}$ and the channel $\bm{h}_{i_{k}}$ estimated in the CS phase. We emphasize again that the BS only produces the transmitted messages without distinguishing the corresponding devices.

This hierarchical encoding process appears to be similar to the work of [26], where CS and channel coding techniques are utilized to encode the messages. However, unlike in [26] considering the GMAC system, our approach is in the MIMO channel. Hence, in addition to recovering the parameters of LDPC codes conveyed by the codebook $\bm{A}$ as in [26], the BS is also tasked to estimate the channel coefficients. Besides, as we will see shortly in Section V-C, a belief propagation decoder draws a connection between the CS and LDPC phases. That is, messages in the CE as well as DD processes can be jointly updated by utilizing the belief of each other. Whereas the two phases in [26] are two independent modules and work sequentially.

The recovery of the preamble as well as the channels in the CS phase is equivalent to the joint DAD-CE problem, which can be modeled as a CS problem. According to the formulation in (8), the recovery of the sparse matrix $\bm{X}$ can be addressed by the CS-based methods, such as the AMP algorithm and its variants [8, 4, 9, 10, 11]. Besides, the MP-based approaches [13, 14] also work well on the above issues. The Bernoulli and Rician messages are jointly updated in [13], which considers the fading channel and grant-free scenario. This scenario is also considered in [14], which takes advantage of estimated data symbols as soft pilot sequences to perform joint channel and data estimation. In this subsection, we consider the MIMO system and derive the update rules of messages based on the BP algorithm.

We derive the update rules of the activity indicator $\phi_{k}$ and channel vector $\bm{h}_{k}$ in (6), which are modeled as Bernoulli and Gaussian messages, respectively. The Gaussian messages can be characterized by the estimation of mean-value $\bm{u}_{k}$ and auto-covariance matrix $\bm{\Sigma}_{k}$. That is, $\bm{u}_{k}$ and $\bm{\Sigma}_{k}$ are the estimation and estimating deviation of $\bm{h}_{k}$ in (6), respectively. Besides, the Bernoulli messages for the activity indicator can be represented by $p_{k}$, which is the probability of $\phi_{k}$ taking the value one. These messages are updated iteratively between the observation and variable nodes, which can be characterized by the factor graph in Fig. 3, where the received signal $y_{l,m}$ represents the observation node, denoted by SN, and channel $h_{k,m}$ and the activity pattern $\phi_{k}$ are the variable nodes, denoted by VN. The edges in the factor graph represent the connections among nodes. In the BP algorithm, messages are passed along these edges. We elaborate on the update rules of these messages below.