A GCICA Grant-Free Random Access Scheme for M2M Communications in Crowded Massive MIMO Systems

There are $L$ sub-pilot phases, and each active UE randomly selects its sub-pilot from a set of mutually orthogonal normalized pilots $\bm{{{P}}_{{o}}}=\left\{\bm{S_{1}},\bm{S_{2}},\cdots,\bm{S_{\tau_{p}}}\right\}\in{\mathbb{R}^{{\tau_{p}}\times\tau_{p}}}$ during each sub-pilot phase. Concatenating these randomly selected sub-pilot sequences, each active UE obtains its super pilot. Following the frame structure as shown in Fig. 1, each active UE sends it super pilot and modulated uplink message to the BS. In addition, the value of RS is the same for all active UEs, and we set the RS to be 1, i.e., $\upsilon_{k}(1)=1\ \forall k$.

Then, let $\bm{g_{k}}={(g_{k}^{1},g_{k}^{2},\cdots,g_{k}^{M})^{{T}}}$ denote the independent and identically distributed (i.i.d.) small-scale fading channel from UE $k$ to the BS, i.e., $\bm{g_{k}}\sim\text{ }\mathcal{N}(0,{\bm{{{I}}_{M}}})$. Let ${\rho_{k}}$ denote UE $k$’s transmitting power. Let ${{{\beta_{k}}}}$ stand for the channel gain between UE $k$ and the BS, which can be known for UE $k$ before the random access procedure [13]. Then, the received sub-pilot signal during the $l^{th}\ (l=1,2,\ldots,L)$ sub-pilot phase at the BS is

where $\bm{A_{t}^{l}}$ stands for the set of UEs that select pilot $S_{t}$ during the $l^{th}$ sub-pilot phase, $\bm{Z_{\text{p}}^{l}}\in{{\mathbb{R}}^{\text{ }M\times{\tau_{p}}}}$ denotes the additive white noise matrix with each element following from a distribution of $\mathcal{N}(0,{{\sigma}^{2}})$. In this paper, $\bm{Z}$ with different subscripts or superscripts will follow the same distribution. In addition, we consider ${{\rho_{k}}{{\beta}_{k}}}=1$ to make the received signal from all active UEs have the same power [22].

The received superimposed uplink message $\bm{Y_{\text{m}}}\in{{\mathbb{R}}^{\text{ }M\times{N_{\text{m}}}}}$ at the BS is

Based on the received sub-pilot signal and the superimposed uplink message, the BS performs ${①}$ CSI estimation and uplink message decoding jointly, and ${②}$ active UE detection and RAR information transmission. The details are described as follows.

${①}$ CSI estimation and uplink message decoding

The BS utilizes the proposed GCICA decoding algorithm to perform CSI estimation and uplink message decoding. The details of the GCICA decoding algorithm are described as follows.

The BS first estimates the CSI corresponding to pilot $\bm{S_{t}}$ during the $l^{th}$ sub-pilot phase by utilizing least squares (LS) method, denoted by $\bm{h_{t}^{l}}$

It can be seen from (3) that, during the $l^{th}$ sub-pilot phase, the estimated CSI corresponding to pilot $\bm{S_{t}}$ is the sum of CSIs of active UEs selecting pilot $\bm{S_{t}}$. So, considering all $L$ sub-pilot phases, a bipartite graph can be used to describe the proposed GCICA-RA scheme, and thus the SIC algorithm can be utilized to estimate UEs’ CSIs on the bipartite graph. The procedure of the SIC algorithm is described in Section III-A in detail. We use $\bm{\hat{H}_{\text{SIC}}}=[\bm{\hat{h}_{\text{SIC}}^{1},\cdots,\hat{h}_{\text{SIC}}}^{N_{\text{SIC}}^{\text{s}}}]\in{\mathbb{R}}^{\text{ }M\times{N_{\text{SIC}}^{\text{s}}}}$ to denote the estimated CSIs via the SIC algorithm, where $N_{\text{SIC}}^{\text{s}}$ is the number of estimated CSIs via the SIC algorithm. Thus, the detected uplink message can be obtained by utilizing LS method

After demodulating and decoding the detected uplink message $\bm{\hat{x}_{\text{SIC}}^{i}}$, we obtain the corresponding decoded uplink message $\bm{\hat{v}_{\text{SIC}}^{i}}$.

Then, based on the estimated CSIs corresponding to all pilots during the $l^{th}$ sub-pilot phase, the BS estimates the number of active UEs by utilizing the estimation method proposed in [19], denoted by $\hat{{N_{a}}}$, which is given by

We can observe from (5) that $\hat{{N_{a}}}$ approaches $N_{a}$ with large $M$. Therefore, the estimated number of active UEs whose CSIs cannot be obtained via the SIC algorithm is

Finally, by utilizing $\hat{N}_{\text{r}}$, $\bm{\hat{v}_{\text{SIC}}^{i}}(1\leq i\leq N_{\text{SIC}}^{\text{s}})$, and $\bm{{Y_{m}}}$, the BS employs a proposed CICA algorithm to obtain the CSIs and decoded uplink message of active UEs whose CSIs cannot be obtained via the SIC algorithm, denoted by $\bm{\hat{H}_{\text{CICA}}}=[\bm{\hat{h}_{\text{CICA}}^{1}},\cdots,\bm{\hat{h}_{\text{CICA}}}^{{\hat{N}_{\text{r}}}}]\in{\mathbb{R}}^{M\times{\hat{N}_{\text{r}}}}$ and $\bm{\hat{v}_{\text{CICA}}^{i}}$, respectively. The details of the CICA algorithm are descried in Section III-B.

${②}$ Active UE detection and RAR information transmission

The BS detects an active UE by judging whether its CSI can be estimated (i.e., whether the corresponding estimated CSI is a valid CSI estimation), and this UE realizes whether it has been detected by the BS in a distributed manner. The details are described as follows.

We utilize $\hat{\bm{H}}=[\bm{\hat{H}_{\text{SIC}}},\bm{\hat{H}_{\text{CICA}}}]$ to denote the estimated CSIs, and assume that $\hat{\bm{H}}(1)$ is a valid CSI estimation. More specifically, $\hat{\bm{H}}(1)$ is the estimated CSI for UE $m$ (i.e., $\hat{\bm{H}}(1)=\bm{g_{m}+\Delta g_{m}}$, where $\bm{\Delta g_{m}}$ denotes the estimation error and takes small values). By correlating $\hat{\bm{H}}(1)$ with the estimated CSI corresponding to pilot $\bm{S_{t}}$ during the $l^{th}$ sub-pilot phase (i.e., $\bm{h_{t}^{l}},~{}t=1,2,\ldots,\tau_{p}$), we have

where (a) follows from the fact that, when $M$ goes into infinity, terms $\frac{(\bm{{g_{m}}})^{H}\bm{g_{m}}}{M}=1$, $\frac{\sum\nolimits_{k\in\bm{A_{t}^{l}},k\neq m}{\bm{{g_{k}}}^{H}}\bm{g_{m}}}{M}=0,\frac{(\bm{Z_{t}^{l}})^{H}(\bm{g_{m}+\Delta g_{m}})}{M}=0$ by utilizing the asymptotic favorable propagation of massive MIMO channel, term $\frac{\sum\nolimits_{k\in\bm{A_{t}^{l}}}{(\bm{{g_{k}}})^{H}}\bm{\Delta g_{m}}}{M}$ is close to $0$ since elements in $\bm{\Delta g_{m}}$ are small values, and (b) is derived based on the random matrix theory. In addition, it is easy to derive that, when $\hat{\bm{H}}(i)$ is not a valid CSI estimation, $\frac{\left(\bm{h_{t}^{l}}\right)^{H}\hat{\bm{H}}(i)}{M}$ is close to 0 by utilizing the random matrix theory. Therefore, the BS utilizes the following rule to judge whether $\hat{\bm{H}}(i)$ is a valid CSI estimation: for the $l^{th}\left(l\in\{1,...,L\}\right)$ sub-pilot phase, if there only exits an element in set $[\frac{(\bm{h_{l}^{1}})^{H}\hat{\bm{H}}(i)}{M},\cdots,\frac{(\bm{h_{l}^{t}})^{H}\hat{\bm{H}}(i)}{M},\cdots,\frac{(\bm{h_{l}^{\tau_{p}}})^{H}\hat{\bm{H}}(i)}{M}]$ close to 1, $\hat{\bm{H}}(i)$ is a valid CSI estimation because each active UE only selects one pilot during each sub-pilot phase; otherwise, $\hat{\bm{H}}(i)$ is not a valid CSI estimation.

After obtaining all valid CSIs, the BS generates and broadcasts the RAR information $\bm{V}=\sum\nolimits_{u\in\bm{B}}(\bm{\hat{H}(u)})^{H}$ to all active UEs where $\bm{B}$ stands for the index set of valid CSI estimations.

The received RAR at UE $m$ is

Then, we have

where (a) is derived by utilizing the asymptotic favorable propagation of massive MIMO channel, similar to (7). Based on the value of $\frac{{{R_{m}}}}{{\sqrt{{\beta_{m}}}M}}$, UE $m$ can realize whether it has been detected. If not, UE $m$ will reattempt the random access procedure in the upcoming random access slot.

A bipartite graph consists of variable nodes, factor nodes, and edges connecting variable nodes and factor nodes. We utilize active UEs and available pilots during each sub-pilot phase to represent variable nodes and factor nodes, respectively. Furthermore, if pilot $\bm{S_{t}}$ is selected by UE $k$ during sub-pilot phase $l$, we use $t^{l}$ to denote the corresponding factor node, and there exists an edge connecting the variable node $k$ with the factor node $t^{l}$. The CSI of UE $k$ is marked on edges connected to UE $k$. Note that, since we use the power control mechanism to make ${{\rho_{k}}{{\beta}_{k}}}=1$, we only need to estimate the small-scale fading channel. So, we only mark the small-scale fading coefficients between the BS and active UE. Furthermore, the degree of a node is referred to the number of edges connected to this node.

Example: Fig. 3(a) illustrates a bipartite graph based on 5 active UEs, 2 sub-pilot phases, and 3 available pilots. During each sub-pilot phase, active UEs (represented by circles) are variable nodes and all available pilots (represented by squares) are factor nodes. Since UE 1 and UE 2 select pilot $\bm{S_{1}}$ during sub-pilot phase $1$, UE 1 and UE 2 are connected to factor node $1^{1}$ by a black solid line. Since UE 3 selects pilot $\bm{S_{2}}$ during sub-pilot phase $1$, UE 3 is connected to factor node $2^{1}$ by a black solid line. Since UE 4 and UE 5 select pilot $\bm{S_{3}}$ during sub-pilot phase $1$, UE 4 and UE 5 are connected to factor node $3^{1}$ by a black solid line. Since UE 1 and UE 3 select pilot $\bm{S_{1}}$ during sub-pilot phase $2$, UE 1 and UE 3 are connected to factor node $1^{2}$ by a black solid line. Since UE 2, UE 4, and UE 5 all select pilot $\bm{S_{3}}$ during sub-pilot phase $2$, UE 2, UE 4 and UE 5 are connected to factor node $3^{2}$ by a black solid line.

The BS employs SIC algorithm to estimate UE’s CSI on the bipartite graph, and then utilizes the estimated CSIs to decode the uplink message. In the following, we briefly discuss the SIC algorithm, present the pseudo-code of the SIC algorithm in Algorithm 1, and give an example to show the SIC algorithm intuitively.

By performing the autocorrelation operation on CSI corresponding to each pilot during each sub-pilot phase, we have

where (a) can be easily derived by utilizing the characteristic of asymptotic favorable propagation of massive MIMO channel.

(10) shows that, with large $M$, $\frac{(\bm{h_{t}^{l}})^{H}\bm{h_{t}^{l}}}{M}$ approaches the number of active UEs selecting pilot $\bm{S_{t}}$ during the $l^{th}$ sub-pilot phase. In other words, $\frac{(\bm{h_{t}^{l}})^{H}\bm{h_{t}^{l}}}{M}$ represents the degree of factor node $t^{l}$.

During the first SIC iteration, the BS first finds factor nodes with degree 1 by utilizing (10). A factor node with degree 1 indicates that there is only one UE selecting the corresponding sub-pilot and the corresponding CSI can be recovered. Then, the BS finds other selected sub-pilots of UEs whose CSIs are recovered. More specifically, for each CSI corresponding to factor node with degree larger than 1, after subtracting each recovered CSI, the BS utilizes (10) to compute the new degree of this factor node. If the new degree is less than the previous degree, this means that the sub-pilot corresponding to this factor node is selected by active UE corresponding to this recovered CSI. We subtract the recovered CSI from the CSI corresponding to this factor node and update the new degree as the previous degree of this factor node. This is equivalent to delete the edges between this active UE and its selected sub-pilots on the bipartite graph. Thus, a new bipartite graph can be obtained, and SIC iteration continues until there is no factor node with degree 1.

Since each active UE selects its sub-pilots randomly, there exits the case of UE $k$ having no pilot collision during multiple sub-pilot phases. This results in the case of the recovered multiple CSIs corresponding to the same UE. Luckily, by utilizing the asymptotic favorable propagation of massive MIMO channel, we can find these CSIs from the recovered CSIs and select one of them as the recovered CSI of this UE. For example, if estimated $\bm{\hat{h}_{1}}$ and $\bm{\hat{h}_{2}}$ correspond to the same active UE, by utilizing the asymptotic favorable propagation of massive MIMO channel, $\frac{(\bm{\hat{h}_{1}})^{H}\bm{\hat{h}_{2}}}{M}$ is close to 1 with large $M$. Otherwise, $\frac{(\bm{\hat{h}_{1}})^{H}\bm{\hat{h}_{2}}}{M}$ is close to 0 with large $M$. Finally, the recovered CSIs via the SIC algorithm are $\bm{\hat{H}_{\text{SIC}}}=[\bm{\hat{h}_{\text{SIC}}^{1},\cdots,\hat{h}_{\text{SIC}}}^{N_{\text{SIC}}^{\text{s}}}]\in{\mathbb{R}}^{\text{ }M\times{N_{\text{SIC}}^{\text{s}}}}$.

Algorithm 1 gives the detailed iteration process of SIC algorithm, where $\bm{h_{i,j}^{k}}$ to represent the CSI corresponding to factor node $j^{k}$ during the $i^{th}$ iteration.

To better understand the SIC algorithm, an example is given to illustrate the SIC algorithm. The details are described as follows:

During the first iteration (Fig. 3(a)), the BS finds that the degree of factor node $2^{1}$ is 1 based on (10). So the BS can directly recover the CSI of UE 3, and incorporates this CSI (i.e., $\bm{h_{1,2}^{1}}$) into the set $\bm{\hat{H}_{\text{SIC}}}$. Then, after subtracting $\bm{h_{\text{SIC}}}^{1}$ from CSIs corresponding to factor node with degree larger than 1, the BS finds that the new degree of factor node $1^{2}$ is less than the previous degree according to (10), and thus realizes that the other index of sub-pilot selected by this UE is 1 in the second sub-pilot phase. Subtracting the recovered CSI from the CSI corresponding to factor node $1^{2}$ (i.e, deleting the lines connected to variable node UE 3), a new bipartite graph can be obtained. Same as above operation, the BS can recover the CSI of UE 1 during the second iteration (i.e., $\bm{h_{2,1}^{2}}$ Fig.3(b)) and the CSI of UE 2 during the third iteration (i.e., $\bm{h_{3,1}^{1}}$ Fig.3(c)). In the end, since there is no factor node with degree 1 (Fig.3(d)), SIC ends. Finally, by utilizing the asymptotic favorable propagation of massive MIMO channel, we find that the recovered CSIs (i.e., $\bm{h_{1,2}^{1}}$, $\bm{h_{2,1}^{2}}$, and $\bm{h_{3,1}^{1}}$) belong to different UEs. Hence, we have $\bm{\hat{h}_{\text{SIC}}^{1}}=\bm{h_{1,2}^{1}}$, $\bm{\hat{h}_{\text{SIC}}^{2}}=\bm{h_{2,1}^{2}}$, and $\bm{\hat{h}_{\text{SIC}}^{3}}=\bm{h_{3,1}^{1}}$.

To compute $S_{\text{SIC}}$, we follow the two assumptions below [14]:

Assumption 1: If an active UE has no pilot collision with other active UEs, its CSI can be recovered successfully.

Assumption 2: When an active UE selects the same pilot with other $l$ active UEs, if CSIs of these $l$ UEs can be recovered, its CSI can be recovered successfully.

Let $P_{\text{fail}}$ denote the probability that UE’s CSI cannot be recovered by the SIC algorithm. Then, we have

The and-or tree principle is used to study random process, and we employ this principle to compute $P_{\text{fail}}$. In the following, we first derive the degree distributions of the proposed GCICA-RA scheme, and then discuss how to utilize the and-or tree principle to compute $P_{\text{fail}}$ based on the derived degree distributions.

${①}$ Degree distributions of the proposed GCICA-RA scheme derivation

Let $\Lambda_{l}$ and $\Psi_{l}$ denote the probability that the degree of a variable node is $l$ and the probability that the degree of a factor node is $l$, respectively. Then, the corresponding polynomial representations are given by

The proposed GCICA-RA scheme allows each active UE to select its sub-pilot during each sub-pilot phase, and there are $L$ sub-pilot phases. Therefore, the degree of each variable node is $L$, i.e.,

In addition, since each active UE randomly selects its sub-pilot during each sub-pilot phase, the event that $l$ active UEs select the same sub-pilot follows a Bernoulli distribution with parameters $N_{a}$ and ${1}/{\tau_{p}}$. Thus, the probability of a factor node with degree $l$ (i.e., $\Psi_{l}$) is

Let $\lambda_{l}$ denote the probability of an edge connecting to a variable node with degree $l$, and $\rho_{l}$ denote the probability of an edge connecting to a factor node with degree $l$. Then, we transfer the node-perspective presentations in (19) and (20) into the edge perspective presentations, respectively

and the polynomial representations are

${②}$ $P_{\text{fail}}$ computation

Considering a factor node with degree $l$ (i.e., there are $l$ UEs selecting the corresponding pilot), an edge connecting to this factor node can be recovered when the other $l-1$ edges connecting to this factor node have been recovered, as shown in Fig. 4(a). Similarly, as shown in Fig. 4(b), considering a variable node with degree $l$ (i.e., UE corresponding to this variable node sends $l$ sub-pilots to the BS), an edge connecting to a variable node with degree $l$ can be recovered when at least one of the other $l-1$ edges have been recovered. Let $n(m)$ denote the probability that an edge connecting to a factor (variable) node with degree $l$ cannot be recovered. Then, we have

and

By averaging $m$ and $n$ over the edge distributions, the evolution of the average erasure probability during the $i^{th}~{}(1\leq i\leq I)$ iteration where $I$ is the maximum number of iterations, can be written as

The update process of $m_{i}$ and $n_{i}$ is shown in Fig. 4(c). Specifically, given initial values $m_{0}$ and $n_{0}$, $m_{i}$ and $n_{i}$ can be derived by (25).

It can be seen from Fig. 4(b) that, a variable node with degree $l$ is unknown when all of these $l$ edges cannot be recovered in the $I^{th}$ iteration. So, the probability of the variable node being unknown is $(n_{I})^{l}$. By averaging $(n_{I})^{l}$ over the degree distributions of variable nodes, $P_{\text{fail}}$ can be calculated by [23]

Substituting (26) into (17), we have

The number of successful UEs obtained by the CICA algorithm can be written as

where $P_{\text{CICA}}^{s}$ denotes the probability that the CSI of one UE can be obtained successfully.

Based on the procedure of the CICA algorithm described in Subsection III-B, we can see that, the CICA algorithm first obtains the decoded uplink message via (14), and then obtains UE’s CSI via (15). Thus, if the uplink message of one UE can be decoded successfully, the CSI of this UE can be recovered successfully. Then, $P_{\text{CICA}}^{s}$ can be computed by

where $P_{e}$ is the bit error rate (BER) of the proposed CICA algorithm, which is larger than that using maximum likelihood (ML) decoding method [24], and can be written as

where step (a) follows from the fact that $\sum\nolimits_{m=1}^{M}{{{({g_{1,m}})}^{2}}}$ is a central chi-squared distribution with degree of freedom $M$ and that ${\rho_{1}\beta_{1}}=1$, and $\Gamma(z)$ is the gamma function with parameter $z$ which is given by

Substituting (30) into (29), we can derive the upper bound for $P_{\text{CICA}}^{s}$,

and thus derive the upper bound for $S_{\text{CICA}}$

Substituting (33), (27) into (16), we can get the upper bound for the successful access probability of the proposed GCICA-RA scheme