Joint Data and Active User Detection for Grant-free FTN-NOMA in Dynamic Networks

Weijie Yuan¹, Nan Wu², Jinhong Yuan¹, Derrick Wing Kwan Ng¹, and Lajos Hanzo³ This work is supported the Australia Research Council Discovery Project (DP190101363) and Linkage Projects (LP 160100708 and LP170101196). D. W. K. Ng is supported by funding from the UNSW Digital Grid Futures Institute, UNSW, Sydney, under a cross-disciplinary fund scheme and by the Australian Research Council’s Discovery Project (DP190101363). L. Hanzo would like to acknowledge the financial support of the Engineering and Physical Sciences Research Council projects EP/Noo4558/1, EP/PO34284/1, COALESCE, of the Royal Society’s Global Challenges Research Fund Grant as well as of the European Research Council’s Advanced Fellow Grant QuantCom. ¹School of Electrical Engineering and Telecommunications, University of New South Wales, NSW 2052, Australia
²School of Information and Electronics, Beijing Institute of Technology, Beijing 100081, China
³School of Electronics and Computer Science, University of Southampton, SO17 1BJ, UK
Email: {weijie.yuan, j.yuan, w.k.ng}@unsw.edu.au, [email protected], [email protected]

Abstract

Both faster than Nyquist (FTN) signaling and non-orthogonal multiple access (NOMA) are promising next generation wireless communications techniques as a benefit of their capability of improving the system’s spectral efficiency. This paper considers an uplink system that combines the advantages of FTN and NOMA. Consequently, an improved spectral efficiency is achieved by deliberately introducing both inter-symbol interference (ISI) and inter-user interference (IUI). More specifically, we propose a grant-free transmission scheme to reduce the signaling overhead and transmission latency of the considered NOMA system. To distinguish the active and inactive users, we develop a novel message passing receiver that jointly estimates the channel state, detects the user activity, and performs decoding. We conclude by quantifying the significant spectral efficiency gain achieved by our amalgamated FTN-NOMA scheme compared to the orthogonal transmission system, which is up to 87.5%.

I Introduction

Wireless communications has played an increasingly important role in modern digital economics. The rapid development of communication technologies has fueled the roll-out of the Internet-of-things (IoT) in 5G wireless systems, which requires to accommodate a massive number of devices [1]. Unfortunately, current techniques can only support a limited number of active devices concurrently[2]. Thus, new techniques supporting massive connectivity are sought.

Recent investigations on non-orthogonal multiple access (NOMA) show that by introducing controllable interference, multiple users can share the same orthogonal radio resources, which allows a communication system to support more users relying on the same amounts of resource elements as OMA [3, 4]. To address the demand for further increasing the spectral efficiency, Faster-than-Nyquist (FTN) signaling, proposed by Mazo in 1970s [5], has attracted substantial interests, since it can transmit at a symbol-rate beyond the Nyquist rate.

Naturally, gleaning further gains is expected by additionally multiplexing the FTN users employing the popular NOMA principles. As a result, the co-existence of inter-user interference (IUI) as well as inter-symbol interference (ISI) in the FTN-NOMA systems leads to a receiver complexity that grows exponentially with both the number of ISI taps and that of the users. To address this issue, several authors have developed reduced-complexity receivers for FTN signaling [6, 7] and NOMA [8, 9]. As a further challenge, the large number of users to be supported by next-generation systems makes the conventional grant-based access control impractical owing to the associated excessive communication overhead and signaling latency[10]. To tackle this problem, grant-free schemes dispensing with “handshaking” have received considerable attention in NOMA scenarios. For instance, the authors of [11] and [12] assumed the user activity to be static and designed factor graph based receivers for simultaneously solving the channel estimation as well as data and user activity detection problem of NOMA systems. Nevertheless, the user activity in networks fluctuates over time in practice. Some active users may become inactive in the next few time slots, while several sleeping users may become active. Therefore, the identification of user activity in real time is desired.

In this paper, we intrinsically amalgamate FTN signaling with the grant-free NOMA concept and consider a dynamic environment, where both the channel and the user activity are time varying. By employing the autoregressive (AR) model of [13] for approximating the correlated noise samples imposed by FTN signaling, we construct a factor graph and propose a bespoke expectation maximization (EM) - message passing algorithm (MPA) for iteratively estimating both the user activity as well as the channel coefficients, and for detecting the data symbols. Since all messages defined over the factor graph and the solutions of the M-step of the EM are obtained in closed forms, the proposed receiver only has a linearly increasing complexity with respect to the number of users. Our simulation results show that the FTN-NOMA system relying on the proposed receiver significantly improves the spectral efficiency and reliably distinguishes the active/inactive users.

Notations: The superscript $(\cdot)^{T}$ and $(\cdot)^{*}$ denote the transpose and inverse operations, respectively; $\mathcal{G}(\mathbf{m}_{\mathbf{x}},\mathbf{V}_{\mathbf{x}})$ denotes the Gaussian distribution of variable $\mathbf{x}$ having a mean vector of $\mathbf{m}_{\mathbf{x}}$ and covariance matrix of $\mathbf{V}_{\mathbf{x}}$ ; $J_{0}(\cdot)$ denotes the zeroth-order Bessel function of the first kind; $\textrm{diag}\{\mathbf{a}\}$ denotes a diagonal matrix with the diagonal elements $\mathbf{a}$ ; $\mathbb{E}[\cdot]$ denotes the expectation operator; $\propto$ represents both sides of the equation are multiplicatively connected to a constant; $\partial$ denotes the partial derivative operator.

II System Model

The NOMA uplink is considered, where $K$ simultaneous users transmit their information to the BS relying on $J$ orthogonal resource elements, with $J<K$ and $\rho=\frac{K}{J}$ representing the normalized user-load. The coded bit stream corresponding to the $k$ th user is first mapped to a sequence of data symbols and then spread over $J$ resource-slots using a low-density signature (LDS) $\mathbf{x}_{k}^{[n]}=[x_{k,1}^{[n]},...,x_{k,J}^{[n]}]^{T}$ , where $x_{k,j}^{[n]}$ denotes the symbol of user $k$ occupying the $j$ th resource element at time instant $n$ . To employ FTN signaling in the NOMA system, the transmitted sequences, $\mathbf{x}_{k}^{[n]}$ of different users pass through a shaping filter $q(t)$ , having a symbol period¹¹1We assume that for all users, the same shaping filter $q(t)$ and packing factor $\tau$ are employed. of $\tau T_{0}$ , yielding

\displaystyle\mathbf{s}_{k}(t)=\sum_{n}\mathbf{x}_{k}^{[n]}q(t-n\tau T_{0}),\vspace{0mm}

(1)

where $\tau$ is the FTN packing factor [6] and $\mathbf{s}_{k}(t)=[s_{k,1}(t),...,s_{k,J}(t)]^{T}$ . The transmitted signals of all users are multiplexed over $J$ resource elements and passed through a time-variant fading channel $\mathbf{h}_{k}(t)=[h_{k,1}(t),...,h_{k,J}(t)]^{T}$ . Assuming perfect synchronization between the BS and the users, the signal received at the BS obeys:

\displaystyle\mathbf{y}(t)=\sum_{k=1}^{K}\textrm{diag}\{\mathbf{h}_{k}(t)\}\mathbf{s}_{k}(t)+\mathbf{w}(t),

(2)

where $\mathbf{y}(t)$ and $\mathbf{w}(t)$ are both $J$ -dimensional vectors with the $j$ th entries being the received signal and noise at the $j$ th resource element, respectively. We now introduce a binary variable $\lambda_{k}^{[n]}=\{0,1\}$ denoting the user-activity, where $\lambda_{k}^{[n]}=1$ represents an active user and 0 an inactive one. Then after processing by a matched filter $q^{*}(-t)$ , the discrete time model for the received signal is given by

\displaystyle{r}_{j}^{[n]}=\sum_{k=1}^{K}\lambda_{k}^{[n]}h_{k,j}^{[n]}\sum_{i=-L}^{L}g_{i}x^{[n-i]}_{k,j}+\omega_{j}^{[n]},

(3)

where $g_{i}$ denotes the FTN signaling-induced ISI tap and $L$ is the length of the taps. Note that in FTN signaling, the noise samples of different time slots are correlated, which imposes challenge on the receiver design. As a remedy, we employ an AR model to approximate the colored noise samples. In practice, the AR model with an AR order of $n_{b}$ is used for approximating the noise sample $\omega_{j}^{[n]}$ , given by

\displaystyle\vspace{0mm}\omega_{j}^{[n]}\approx e_{j}^{[n]}+\sum_{i=1}^{n_{b}}b_{i}\omega_{j}^{[n-i]},\vspace{0mm}

(4)

where $e_{j}^{[n]}$ is a random Gaussian impairment having zero-mean as well as variance $\sigma_{e}^{2}$ and $b_{i}$ is the AR coefficient. Based on the known coefficients $\{g_{i}\}$ , the parameters $\{b_{i}\}$ and $\sigma_{e}^{2}$ can be estimated by solving the Yule-Walker equations [14].

III The Proposed Low-complexity Receiver Design

From a statistical inference perspective, inferring channel coefficients, and all users’ information bits from the received signal samples is equivalent to determining the a posteriori distributions of the corresponding variables.

III-A Factor Graph Representation

By stacking all transmitted symbols, received samples, channel taps, user states and noise samples into vectors, i.e., $\mathbf{x}$ , $\mathbf{r}$ , $\mathbf{h}$ , $\bm{\lambda}$ , and $\bm{\omega}$ , the joint a posteriori distribution is written as $p(\mathbf{x},\mathbf{h},\bm{\lambda},\bm{\omega}|\mathbf{r})$ . For an unknown variable $z$ , we aim for deriving its marginal distribution $p(z|\mathbf{r})$ and estimating it via the maximum a posteriori (MAP) estimators formulated as

\displaystyle z=\arg\max_{z}p(z|\mathbf{r}).

(5)

Nevertheless, direct marginalization is usually intractable due to the associated high-dimensional integration. As an alternative, the factor graph framework is capable of circumventing this problem by exploiting the conditional independence of variables given the observations. Exploiting the fact that $\mathbf{x}$ , $\mathbf{h}$ , $\bm{\lambda}$ , and $\bm{\omega}$ are independent of each other, $p(\mathbf{x},\mathbf{h},\bm{\lambda},\bm{\omega}|\mathbf{r})$ can be factorized as

\displaystyle p(\mathbf{x},\mathbf{h},\bm{\lambda},\bm{\omega}|\mathbf{r})\propto p(\mathbf{x})\cdot p(\mathbf{h})\cdot p(\bm{\lambda})\cdot p(\bm{\omega})\cdot p(\mathbf{r}|\mathbf{x},\mathbf{h},\bm{\lambda},\bm{\omega}).

Since the transmitted symbols of different users at different instants are independent, $p(\mathbf{x})$ can be fully factorized as

\displaystyle p(\mathbf{x})=\prod_{k,j,n}p(x_{k,j}^{[n]}),

(6)

where $p(x_{k,j}^{[n]})$ is determined based on the log-likelihood ratios (LLRs) output by the channel decoder.

For time-varying channel taps $\mathbf{h}$ , it is convenient to characterize $h_{k,j}^{[n]}$ by a Gauss-Markov model $h_{k,j}^{[n]}=\alpha h_{k,j}^{[n-1]}+\varepsilon^{[n]}$ , where the coefficient $\alpha$ obeys the zero-order Bessel function of the first kind[15]

\displaystyle\alpha=\mathbb{E}[h_{k,j}^{[n]}(h_{k,j}^{[n]})^{*}]=J_{0}(2\pi f_{D}\tau T_{0}),

(7)

and $\varepsilon^{[n]}$ is a zero-mean Gaussian distributed variable with variance $1-|\alpha|^{2}$ . Consequently, $p(\mathbf{h})$ is expressed as

\displaystyle p(\mathbf{h})=\prod_{k,j}p(h_{k,j}^{0})\prod_{n}{p(h_{k,j}^{[n]}|h_{k,j}^{[n-1]})}.

(8)

In a dynamically fluctuating environment, the evolution of the user-activity state $\lambda$ can be modeled by a Markov chain, where the current activities of the users depend on the states of the previous time instant. Hence, the distribution $p(\bm{\lambda})$ can be factorized as

\displaystyle p(\bm{\lambda})=\prod_{k=1}^{K}p(\lambda_{k}^{0})\cdot\prod_{n}p(\lambda_{k}^{[n]}|\lambda_{k}^{[n-1]}).

(9)

Depending on the previous state of user $k$ , the state transition function $p(\lambda_{k}^{[n]}|\lambda_{k}^{[n-1]})$ has different expressions. Given the user-birth probability of $p_{b_{k}}^{[n]}$ and the mortality probability of $p_{m_{k}}^{[n]}$ , the transition probability of user-activity state $p(\lambda_{k}^{[n]}|\lambda_{k}^{[n-1]})$ is expressed as

\displaystyle p(\lambda_{k}^{[n]}|\lambda_{k}^{[n-1]})=\left\{\begin{array}[]{cc}(p_{b_{k}}^{[n]})^{1-\lambda_{k}^{[n-1]}}(1-p_{m_{k}}^{[n]})^{\lambda_{k}^{[n-1]}}&\lambda_{k}^{[n]}=1,\\ (1-p_{b_{k}}^{[n]})^{1-\lambda_{k}^{[n-1]}}(p_{m_{k}}^{[n]})^{\lambda_{k}^{[n-1]}}&\lambda_{k}^{[n]}=0.\end{array}\right.

(12)

Assuming that $\Lambda$ denotes the average number of users becoming active at a time instant, we set $p_{b_{k}}^{[n]}=\Lambda/K$ as the birth probability of a user. For the mortality probability, establishing an accurate model requires a large amount of data, but this is beyond the scope of the paper. Hence we employ a fair scheme assuming that $p_{m_{k}}^{[n]}=0.5$ .

Based on the AR model (4) of the noise sample $\omega_{j}^{[n]}$ , we can factorize $p(\bm{\omega})$ as

\displaystyle p(\bm{\omega})=\prod_{j}p(\omega_{j}^{0})\prod_{n}{p(\omega_{j}^{[n]}|\omega_{j}^{[n-n_{b}]},...,\omega_{j}^{[n-1]})},

(13)

where $p(\omega_{j}^{0})\propto\mathcal{G}(0,\sigma_{e}^{2})$ and $p(\omega_{j}^{[n]}|\omega_{j}^{[n-n_{b}]},...,\omega_{j}^{[n-1]})\propto\exp\left(-\frac{(\omega_{j}^{[n]}-\mathbf{b}^{T}\bm{\omega}_{j}^{[n]})^{2}}{\sigma_{e}^{2}}\right)$ , with the notations $\mathbf{b}=[b_{1},...,b_{n_{b}}]^{T}$ and $\bm{\omega}_{j}^{[n]}=[\omega_{j}^{[n-1]},...,\omega_{j}^{[n-n_{b}]}]^{T}$ . Furthermore, we can write the evolution model of $\bm{\omega}_{j}^{[n+1]}$ as

\displaystyle\bm{\omega}_{j}^{[n+1]}=\mathbf{B}_{1}\bm{\omega}_{j}^{[n]}+\mathbf{b}_{1}\omega_{j}^{[n]},

(14)

where $\mathbf{B}_{1}=\left[\begin{array}[]{cc}\mathbf{0}_{n_{b}-1}^{T}&0\\ \mathbf{I}_{n_{b}-1}&\mathbf{0}_{n_{b}-1}\end{array}\right]$ and $\mathbf{b}_{1}=[1,\mathbf{0}_{n_{b}-1}^{T}]^{T}$ .

Based on (3), we use a Dirac delta function $\delta(\cdot)$ for representing the relationship between the received signal sample and the unknown variables. By introducing an auxiliary variable²²2The auxiliary variable is introduced to reduce the number of multiplications [9]. $s_{k,j}^{[n]}=\sum_{i=-L}^{L}g_{i}x_{k,j}^{[n-i]}=\mathbf{g}^{T}\tilde{\mathbf{x}}_{k,j}^{[n]}$ , $p(\mathbf{r}|\mathbf{x},\mathbf{h},\bm{\lambda},\bm{\omega})$ is factorized as

	$\displaystyle p(\mathbf{r}\|\mathbf{x},\mathbf{h},\bm{\lambda},\bm{\omega})=\prod_{j,n}$	$\displaystyle{\delta(r_{j}^{[n]}-\sum_{k=1}^{K}\lambda_{k}^{[n]}h_{k,j}^{[n]}s_{k,j}^{[n]}-\omega_{j}^{[n]})}$
		$\displaystyle\cdot{\delta(s_{k,j}^{[n]}-\mathbf{g}^{T}\tilde{\mathbf{x}}_{k,j}^{[n]})},$		(15)

where $\mathbf{g}$ and $\tilde{\mathbf{x}}_{k,j}^{[n]}$ denote the vectors $[g_{-L},...,g_{L}]^{T}$ and $[{{x}}_{k,j}^{[n+L]},...,{{x}}_{k,j}^{[n-L]}]$ , respectively. The variable $\tilde{\mathbf{x}}_{k,j}^{[n]}$ follows a similar evolution model as in (14),

\displaystyle\tilde{\mathbf{x}}_{k,j}^{[n]}=\mathbf{B}_{2}\tilde{\mathbf{x}}_{k,j}^{[n-1]}+\mathbf{b}_{2}x_{k,j}^{[n+L]},

(16)

where $\mathbf{B}_{2}=\left[\begin{array}[]{cc}\mathbf{0}_{{2L}}^{T}&0\\ \mathbf{I}_{{2L}}&\mathbf{0}_{{2L}}\end{array}\right]$ and $\mathbf{b}_{2}=[1,\mathbf{0}_{{2L}}^{T}]^{T}$ .

Based on the factorizations of (6)-(III-A), we now have the factorization of $p(\mathbf{x},\mathbf{h},\bm{\lambda},\bm{\omega}|\mathbf{r})$ , which we represent by a factor graph, as depicted in Fig. 1. On this factor graph, the factor nodes denoted by squares represent the functions nodes while the variables are denoted by edges. The equality factor nodes of Fig. 1 represented by the symbol $\framebox{$=$}$ are introduced for variable “cloning” to enforce the condition that a variable may only appear in a maximum of two functions. To simplify the notations, we adopt $\overrightarrow{\mu}(x)$ and $\overleftarrow{\mu}(x)$ to denote the specific messages of the variable $x$ that flow in the direction and in the opposite direction of the edge.

Refer to caption — (a) Subgraph for the multiuser detection and decoding part.

III-B MPA for Message Calculations

III-B1 Multiuser Detection and Decoding Part

Let us commence from the message calculations in Fig. 1(a). The intrinsic information $\overrightarrow{\mu}(x_{k,j}^{[n]})$ is calculated based on the log-likelihood ratio (LLR) output by the channel decoder. Since $x_{k,j}^{[n]}$ is discretely distributed, the message passing algorithm (MPA) exhibits an excessive complexity. To this end, we approximate $\overrightarrow{\mu}(x_{k,j}^{[n]})$ by a Gaussian distribution using expectation propagation (EP). Assuming that the extrinsic message $\overleftarrow{\mu}(x_{k,j}^{[n]})$ obeys the Gaussian distribution of $\mathcal{G}(\overleftarrow{m}_{x_{k,j}^{[n]}},\overleftarrow{v}_{x_{k,j}^{[n]}})$ , we can readily obtain the mean and variance of $b(x_{k,j}^{[n]})$ by moment matching and then determine the Gaussian belief $\tilde{b}(x_{k,j}^{[n]})\propto\mathcal{G}({m}_{x_{k,j}^{[n]}},{v}_{x_{k,j}^{[n]}})$ . Hence we have the message $\overrightarrow{\mu}(x_{k,j}^{[n]})$ expressed as

\displaystyle\overrightarrow{\mu}(x_{k,j}^{[n]})={\tilde{b}(x_{k,j}^{[n]})}/{\overleftarrow{\mu}(x_{k,j}^{[n]})}\propto\mathcal{G}(\overrightarrow{m}_{x_{k,j}^{[n]}},\overrightarrow{v}_{x_{k,j}^{[n]}}).

(17)

By employing the MPA rules, we can determine the mean vector and covariance matrix of the message $\overrightarrow{\mu}(\dot{\mathbf{x}}_{k,j}^{[n-L]})$ . Therefore the message output by the multiuser detector can be assumed to be Gaussian, formulated as

\displaystyle\overrightarrow{\mu}(s_{k,j}^{[n-L]})\propto\mathcal{G}(\mathbf{g}_{T}\overrightarrow{\mathbf{m}}_{\dot{\mathbf{x}}_{k,j}^{[n-L]}},\mathbf{g}_{T}\overrightarrow{\mathbf{V}}_{\dot{\mathbf{x}}_{k,j}^{[n-L]}}\mathbf{g}).

(18)

Finally, we are interested in calculating the extrinsic message $\overleftarrow{\mu}(x_{k,j}^{[n]})$ , whose mean and variance obey

	$\displaystyle\overleftarrow{m}_{x_{k,j}^{[n]}}$	$\displaystyle=\mathbf{b}_{2}^{T}\left(\overleftarrow{\mathbf{m}}_{\tilde{\mathbf{x}}_{k,j}^{[n-L]}}-\mathbf{B}_{2}\overrightarrow{\mathbf{m}}_{\dot{\tilde{\mathbf{x}}}_{k,j}^{[n-L-1]}}\right),$		(19)
	$\displaystyle\overleftarrow{v}_{x_{k,j}^{[n]}}$	$\displaystyle=\mathbf{b}_{2}^{T}\left(\overleftarrow{\mathbf{V}}_{\tilde{\mathbf{x}}_{k,j}^{[n-L]}}+\mathbf{B}_{2}\overrightarrow{\mathbf{V}}_{\dot{\tilde{\mathbf{x}}}_{k,j}^{[n-L-1]}}\mathbf{B}_{2}^{T}\right)\mathbf{b}_{2},$		(20)

respectively.

III-B2 Channel Estimation

Provided that the message $\overrightarrow{\mu}(\dot{h}_{k,j}^{[n-1]})$ is available in Gaussian form, by applying the MPA rules, the message $\overrightarrow{\mu}(\tilde{h}_{k,j}^{[n]})$ is expressed as

	$\displaystyle\overrightarrow{\mu}(\tilde{h}_{k,j}^{[n]})$	$\displaystyle\propto\mathcal{G}\left(\overrightarrow{m}_{\tilde{h}_{k,j}^{[n]}},\overrightarrow{v}_{\tilde{h}_{k,j}^{[n]}}\right)$
		$\displaystyle\propto\left(\alpha\overrightarrow{m}_{\dot{h}_{k,j}^{[n-1]}},1+\|\alpha\|^{2}(\overrightarrow{v}_{\dot{h}_{k,j}^{[n-1]}}-1)\right).$		(21)

Then, we are able to derive the message $\overrightarrow{\mu}(\dot{h}_{k,j}^{[n]})$ , given by

	$\displaystyle\overrightarrow{v}_{\dot{h}_{k,1}^{[n]}}$	$\displaystyle=\frac{\overrightarrow{v}_{\tilde{h}_{k,1}^{[n]}}+\overleftarrow{v}_{{h}_{k,1}^{[n]}}}{\overrightarrow{v}_{\tilde{h}_{k,1}^{[n]}}\overleftarrow{v}_{{h}_{k,1}^{[n]}}},$		(22)
	$\displaystyle\overrightarrow{m}_{\dot{h}_{k,1}^{[n]}}$	$\displaystyle=\overrightarrow{v}_{\dot{h}_{k,1}^{[n]}}\left(\frac{\overrightarrow{m}_{\tilde{h}_{k,1}^{[n]}}}{\overrightarrow{v}_{\tilde{h}_{k,1}^{[n]}}}+\frac{\overleftarrow{m}_{{h}_{k,1}^{[n]}}}{\overleftarrow{v}_{{h}_{k,1}^{[n]}}}\right).$		(23)

Next, we consider the process of colored noise. Since the AR process given by (4) is causal, the messages are only propagated forward along the arrow’s direction. Provided that the means of the noise parameters are $0$ , we can readily derive the corresponding messages as follows

	$\displaystyle\overrightarrow{v}_{\omega_{j}^{[n]}}$	$\displaystyle=\mathbf{b}^{T}\overrightarrow{\mathbf{V}}_{\bm{\omega}_{j}^{[n]}}\mathbf{b},$		(24)
	$\displaystyle\overrightarrow{\mathbf{V}}_{\bm{\omega}_{j}^{[n+1]}}$	$\displaystyle=\mathbf{B}_{1}\overrightarrow{\mathbf{V}}_{\bm{\omega}_{j}^{[n]}}\mathbf{B}_{1}^{T}+\mathbf{b}_{1}\overrightarrow{v}_{\omega_{j}^{[n]}}\mathbf{b}_{1}^{T}.$		(25)

III-B3 User-activity Idenfitication

For the discrete random variable representing a user-activity state at time instant $n-1$ , we have $\dot{\lambda}_{k}^{[n-1]}$ , and the message $\overrightarrow{\mu}(\dot{\lambda}_{k}^{[n-1]})$ is the belief of user $k$ ’s state at time instant $n-1$ , which is fully characterized by the probability of $\lambda_{k}^{[n-1]}=1$ , i.e., $\overrightarrow{p}_{\dot{\lambda}_{k}^{[n-1]}}$ . Therefore, passing on the user-activity probability $\overrightarrow{p}_{\dot{\lambda}_{k}^{[n-1]}}$ instead of the message can simplify the expressions. We arrive at the forward message $\overrightarrow{p}(\lambda_{k}^{[n]})$ expressed as

\displaystyle\overrightarrow{p}_{\lambda_{k}^{[n]}}=(1-p_{m_{k}}^{[n]})\overrightarrow{p}_{\dot{\lambda}_{k}^{[n]}}+p_{b_{k}}^{[n]}(1-\overrightarrow{p}_{\dot{\lambda}_{k}^{[n]}}).

(26)

The equality node of Fig. 1 is equivalent to the product of messages. Therefore the message updating concerning $\dot{\lambda}_{k}^{[n]}$ is derived as

\displaystyle\overrightarrow{p}_{\dot{\lambda}_{k}^{[n]}}=\frac{\overrightarrow{p}{\lambda_{k}^{[n]}}\overleftarrow{p}_{\dot{\lambda}_{k,1}^{[n]}}}{1-\overrightarrow{p}{\lambda_{k}^{[n]}}-\overleftarrow{p}_{\dot{\lambda}_{k,1}^{[n]}}}.

(27)

The message $\overrightarrow{p}_{{\lambda}_{k,j}^{[n]}}$ forwarded to the multiplier node can be obtained similarly.

Note that the above message calculations depend on the assumption of having known backward messages gleaned from the multiplier node. According to the update rules of the conventional MPA, the messages derived at the multiplier node $\times$ are unable to provide Gaussian form messages. Hence, we invoke the expectation maximization algorithm for the multiplier node.

III-C Modified EM Algorithm for $\times$ Node

Without loss of generality, we consider the multiplier node connected with $r_{k,j}^{[n]}$ and the joint distribution $p({\lambda}_{k,j}^{[n]},{s}_{k,j}^{[n]},{h}_{k,j}^{[n]}|{r}_{k,j}^{[n]})$ . We first define $\lambda_{k,j}^{[n]}$ as the unknown parameter and $\{h_{k,j}^{[n]},s_{k,j}^{[n]},r_{k,j}^{[n]}\}$ as the complete data set associated with incomplete data $r_{k,j}^{[n]}$ and latent variables $h_{k,j}^{[n]}$ , $s_{k,j}^{[n]}$ . Assuming that the beliefs $b(s_{k,j}^{[n]})$ and $b(h_{k,j}^{[n]})$ are available, the expectation of the complete-data log augmented density is calculated as

	$\displaystyle q({\lambda}_{k,j}^{[n]})=-\int\int$	$\displaystyle\frac{\left(\overleftarrow{m}_{r_{k,j}^{[n]}}-\lambda_{k,j}^{[n]}{s}_{k,j}^{[n]}{h}_{k,j}^{[n]}\right)^{2}}{\overleftarrow{v}_{r_{k,j}^{[n]}}}\cdot b(s_{k,j}^{[n]})b(h_{k,j}^{[n]})$
		$\displaystyle\textrm{d}h_{s,j}^{[n]}\textrm{d}h_{k,j}^{[n]}+\ln\overrightarrow{\mu}({\lambda}_{k,j}^{[n]})+C,$		(28)

where $C$ is a constant that is irrelevant to $\lambda_{k,j}^{n}$ . It can be observed that (III-C) is a concave function and the estimate $\hat{\lambda}_{k,j}^{[n]}$ is given by the solution of $\frac{\partial q({\lambda}_{k,j}^{[n]})}{\partial{\lambda}_{k,j}^{[n]}}=0$ . However, note that (III-C) only considers the $j$ th resource element, while the user activity applies to all radio resources. The maximization should be performed by obtaining the necessary information from all $J$ resource elements, i.e., with respect to the variable $\dot{\lambda}_{k}^{n}$ . To this end, the multiplier node will feed back the message $\overleftarrow{\mu}({\lambda}_{k,j}^{[n]})$ to the equality node of Fig. 1(b). Having $q({\lambda}_{k,j}^{[n]})$ in hand, $\overleftarrow{\mu}({\lambda}_{k,j}^{[n]})$ is calculated as $\exp\left[q({\lambda}_{k,j}^{[n]})\right]/{\overrightarrow{\mu}({\lambda}_{k,j}^{[n]})}$ . Similar to the forward message $\overrightarrow{p}(\lambda_{k}^{[n]})$ , we can simply pass on the normalized probability $\overleftarrow{p}_{{\lambda}_{k,j}^{[n]}}$ , which is used to calculate $\overleftarrow{p}_{{\lambda}_{k,j-1}^{[n]}}$ , then $\overleftarrow{p}_{{\lambda}_{k,1}^{[n]}}$ and finally $\overrightarrow{p}_{\dot{\lambda}_{k}^{[n]}}$ .

To obtain the beliefs of $s_{k,j}^{[n]}$ and $h_{k,j}^{[n]}$ , we apply the concept of EM again that $s_{k,j}^{[n]}$ becomes an unknown parameter and $h_{k,j}^{[n]}$ remains the latent variable. In this way, the belief of $s_{k,j}^{[n]}$ is updated as follows:

	$\displaystyle b(s_{k,j}^{[n]})\propto\overrightarrow{\mu}(s_{k,j}^{[n]})\cdot\exp\Big{(}\int$	$\displaystyle b(h_{k,j}^{[n]})\ln p(r_{k,j}^{[n]},s_{k,j}^{[n]}\|h_{k,j}^{[n]},\hat{\lambda}_{k,j}^{[n]})$
		$\displaystyle\textrm{d}h_{k,j}^{[n]}\Big{)},$		(29)

where $\lambda_{k,j}^{[n]}$ is replaced by the estimate $\hat{\lambda}_{k,j}^{[n]}$ obtained from the maximization of (III-C), expressed as

\displaystyle\hat{\lambda}_{k,j}^{[n]}=\frac{\overleftarrow{m}_{r_{k,j}^{[n]}}m_{s_{k,j}^{[n]}}m_{h_{k,j}^{[n]}}+\overleftarrow{v}_{r_{k,j}^{[n]}}(1-2\overrightarrow{p}_{\lambda_{k,j}^{[n]}})}{(|m_{s_{k,j}^{[n]}}|^{2}+v_{s_{k,j}^{[n]}})(|m_{h_{k,j}^{[n]}}|^{2}+v_{h_{k,j}^{[n]}})}.

(30)

Since we have $b(s_{k,j}^{[n]})=\overrightarrow{\mu}(s_{k,j}^{[n]})\cdot\overleftarrow{\mu}(s_{k,j}^{[n]})$ , it is natural to define the second term on the right-hand side of (III-C) as $\overleftarrow{\mu}(s_{k,j}^{[n]})$ . Assuming that $b(h_{k,j}^{[n]})$ , it follows that $\mathcal{G}(m_{h_{k,j}^{[n]}},v_{h_{k,j}^{[n]}})$ , $\overleftarrow{\mu}(s_{k,j}^{[n]})$ can be modeled by a Gaussian distribution with a mean and variance of

	$\displaystyle\overleftarrow{m}_{s_{k,j}^{[n]}}$	$\displaystyle=\frac{\overleftarrow{m}_{r_{k,j}^{[n]}}m_{h_{k,j}^{[n]}}}{\|m_{h_{k,j}^{[n]}}\|^{2}+v_{h_{k,j}^{[n]}}},$		(31)
	$\displaystyle\overleftarrow{v}_{s_{k,j}^{[n]}}$	$\displaystyle=\frac{\overleftarrow{v}_{r_{k,j}^{[n]}}}{\|m_{h_{k,j}^{[n]}}\|^{2}+v_{h_{k,j}^{[n]}}}.$		(32)

Consequently the belief $b(s_{k,j}^{[n]})$ is readily obtained. By exchanging the roles of $s_{k,j}^{[n]}$ and $h_{k,j}^{[n]}$ , we have the updating rules of the message $\overleftarrow{\mu}(h_{k,j}^{[n]})$ and of the belief $b(h_{k,j}^{[n]})$ . After obtaining the beliefs $b(s_{k,j}^{[n]})$ and $b(h_{k,j}^{[n]})$ , we can now determine $q({\lambda}_{k,j}^{[n]})$ in the next iteration following (III-C).

Finally, we can obtain the forward message $\overrightarrow{\mu}(r_{k,j}^{[n]})$ . Since the variables $\lambda_{k,j}^{[n]}$ , $s_{k,j}^{[n]}$ , and $h_{k,j}^{[n]}$ are independent, the moments of $r_{k,j}^{[n]}$ are given by the product of the moments of the above three variables. Consequently, we have

$\displaystyle\overrightarrow{m}_{r_{k,j}^{[n]}}=$	$\displaystyle\hat{\lambda}_{k,j}^{n}m_{h_{k,j}^{[n]}}m_{h_{s,j}^{[n]}},$	(33)
$\displaystyle\overrightarrow{v}_{r_{k,j}^{[n]}}=$	$\displaystyle\hat{\lambda}_{k,j}^{n}\big{(}(1-\hat{\lambda}_{k,j}^{n})\|m_{h_{k,j}^{[n]}}\|^{2}\|m_{s_{k,j}^{[n]}}\|^{2}+\|m_{h_{k,j}^{[n]}}\|^{2}v_{s_{k,j}^{[n]}}$
	$\displaystyle+\|m_{s_{k,j}^{[n]}}v_{h_{k,j}^{[n]}}+v_{h_{k,j}^{[n]}}v_{s_{k,j}^{[n]}}\|^{2}\big{)}.$	(34)

Above, we have obtained $\overrightarrow{p}_{\dot{\lambda}_{k}^{[n]}}$ and $b(h_{k,j}^{[n]})$ . Then we can proceed by comparing $\overrightarrow{p}_{\dot{\lambda}_{k}^{[n]}}$ to a specific threshold for deciding whether the user $k$ is active, while the estimate of the channel tap $h_{k,j}^{[n]}$ is given by $\hat{h}_{k,j}^{[n]}=\mathbb{E}_{h}\left[b(h_{k,j}^{[n]})\right]=m_{h_{k,j}^{[n]}}$ .

It is observed that in the proposed algorithm, the messages are represented only by a few parameters and the integration is simplified to additions and multiplications, which dramatically reduces the receiver’s complexity. Explicitly, the complexity only increases linearly with the number of active users $|\mathcal{K}^{+}|$ , which shows the superiority of the proposed algorithm in massive connectivity scenarios.

IV Simulation Results

This section presents our simulation results. A rate-1/2 length- $2,160$ low-density parity-check (LDPC) code is adopted. At total of $K=180$ users are supported by $J=120$ resource elements in our NOMA system, leading to the normalized user-load of $\rho=150\%$ . Quadrature Phase Shift Keying (QPSK) is used for bit-to-symbol mapping. For each user, 5 sequences of symbols having a length of $1,080$ are transmitted. The data symbols corresponding to different users are shaped by the raised root cosine filter having a roll-off factor of $\alpha=0.4$ and a FTN packing factor of $\tau=0.8$ and. A Rayleigh fading channel is considered and the taps are generated by Jake’s model with a normalized Doppler rate of $f_{D}\tau T_{0}=0.005$ . The channel estimation is based on the least square (LS) method and as few as 5 pilots. The parameter $\Lambda$ is set to $20$ , which indicates that approximately 11% of users are active. Again, the mortality probability was set to $p_{m_{k}}^{[n]}=0.5$ . The user activity is assumed to remain static for a sequence of 1,080 symbols. The threshold of $0.5$ is employed for user activity identification.

In Fig. 2, we compare the proposed receiver design to some existing benchmark algorithms in terms of its BER performance. Explicitly, the BER performance versus $E_{b}/N_{0}$ of the proposed algorithm as well as of the MPA-APP and LS-AMP-MPA methods are illustrated in Fig. 2. The LS-AMP-MPA is a two-step method which firstly identifies the active users and then performs MPA based MUD. Since the two-stage method only provides the estimates of user-activities for data detection, considerable performance loss can be seen compared to the proposed EM-MPA algorithm. The MPA-APP method regards all users to be active although most users are inactive, hence leading to certain performance degradation. Moreover, we also include the curve corresponding to the OMA system using MPA for channel estimation and user-activity identification (Genie-aided). A slight performance loss is observed for the proposed algorithm due to the ISI and IUI imposed by our FTN-NOMA system. Nevertheless, the spectral efficiency is increased by $(\rho-1)*1/\tau=87.5\%$ , given the same radio resources.

We plot the normalized minimum mean-squared errors (NMSE) of the channel estimate based on the proposed algorithm as well as on the GA-MPA and on the full pilot based sparse Bayesian learning (SBL) method in Fig. 3. Since EP can exploit the extrinsic information from the detector when approximating the discrete distribution by a Gaussian one, the proposed EM-MPA algorithm outperforms the GA-MPA method using direct moment matching. It is also worth noting that the NMSE performance of the proposed algorithm has a modest performance loss compared to the full-pilot based method, which demonstrates the powerful capability of the proposed algorithm.

In Fig. 4, the impact of the number of active users on the decoding performance is considered. We plot the BER performance versus the parameter $\Lambda$ at $E_{b}/N_{0}=5.75$ dB, where the performance of the EM-MPA-Ideal relying on perfectly known user-activity is also shown as a performance upper bound. In fact, a higher $\Lambda$ results in more active users. Hence, the IUI becomes more severe and degrades the BER performance, which can be observed for both the proposed method and the performance upper bound. It is interesting to see that when $\Lambda$ increases, the performance of the proposed algorithm approaches the upper bound, because user identification becomes more accurate for more active users. In particular, in the extreme case, when all users are active, the identification error will drop to $0$ .

V Conclusions

We have conceived a low-complexity receiver for the grant-free FTN-NOMA uplink. We considered dynamically fluctuating environments, which assume that the user state and channel vary with time. A new expectation maximization - message passing algorithm combination was proposed based on the factor graph framework for joint FTN symbol detection, channel estimation and user-activity tracking. The complexity of the proposed receiver increases linearly with the number of active users, which is significantly lower than that of the conventional message passing receiver. Our simulation results demonstrated the efficiency of the proposed method in identifying active users and decoding the information bits whilst enhancing the bandwidth efficiency by up to 87.5%.

References

[1] V. W. Wong, R. Schober, D. W. K. Ng, and L.-C. Wang, Key Technologies for 5G Wireless Systems. Cambridge University Press, 2017.
[2] W. Zeng, J. Zhang, D. W. K. Ng, B. Ai, and Z. Zhong, “Two-way hybrid terrestrial-satellite relaying systems: Performance analysis and relay selection,” IEEE Trans. Veh. Technol., vol. 68, no. 7, pp. 7011–7023, 2019.
[3] Z. Wei, L. Yang, D. W. K. Ng, J. Yuan, and L. Hanzo, “On the performance gain of NOMA over OMA in uplink communication systems,” IEEE Trans. Commun., pp. 1–1, early access, 2019.
[4] M. Mohammadkarimi, M. A. Raza, and O. A. Dobre, “Signature-based nonorthogonal massive multiple access for future wireless networks: Uplink massive connectivity for machine-type communications,” IEEE Veh. Technol. Mag., vol. 13, no. 4, pp. 40–50, 2018.
[5] J. E. Mazo, “Faster-than-Nyquist signaling,” The Bell System Technical Journal, vol. 54, no. 8, pp. 1451–1462, Aug. 1975.
[6] S. Li, B. Bai, J. Zhou, P. Chen, and Z. Yu, “Reduced-complexity equalization for faster-than-Nyquist signaling: New methods based on Ungerboeck observation model,” IEEE Trans. Commun., vol. 66, no. 3, pp. 1190–1204, 2017.
[7] S. Sugiura and L. Hanzo, “Frequency-domain-equalization-aided iterative detection of faster-than-Nyquist signaling,” IEEE Trans. Veh. Technol., vol. 64, no. 5, pp. 2122–2128, May 2014.
[8] Y. Liang, X. Li, J. Zhang, and Z. Ding, “Non-orthogonal random access for 5G networks,” IEEE Trans. Wireless Communications, vol. 16, no. 7, pp. 4817–4831, 2017.
[9] W. Yuan, N. Wu, Q. Guo, Y. Li, C. Xing, and J. Kuang, “Iterative receivers for downlink MIMO-SCMA: Message passing and distributed cooperative detection,” IEEE Trans. Wireless Commun., vol. 17, no. 5, pp. 3444–3458, May 2018.
[10] Z. Sun, Z. Wei, L. Yang, J. Yuan, X. Cheng, and L. Wan, “Exploiting transmission control for joint user identification and channel estimation in massive connectivity,” IEEE Transactions on Communications, vol. 67, no. 9, pp. 6311–6326, Sep. 2019.
[11] Y. Zhang, Q. Guo, Z. Wang, J. Xi, and N. Wu, “Block sparse Bayesian learning based joint user activity detection and channel estimation for grant-free NOMA systems,” IEEE Trans. Veh. Technol., vol. 67, no. 10, pp. 9631–9640, Oct. 2018.
[12] W. Yuan, N. Wu, A. Zhang, X. Huang, Y. Li, and L. Hanzo, “Iterative receiver design for FTN signaling aided sparse code multiple access,” IEEE Trans. Wireless Commun., vol. 19, no. 2, pp. 915–928, Feb 2020.
[13] W. Yuan, N. Wu, Q. Guo, J. Yuan, D. W. K. Ng, and L. Hanzo, “Iterative joint channel estimation, user activity tracking, and data detection for FTN-NOMA systems supporting random access,” IEEE Trans. Commun., 2020, in press.
[14] B. C. Levy, Principles of signal detection and parameter estimation. Springer Science & Business Media, 2008.
[15] L. Hanzo, Y. Akhtman, J. Akhtman, L. Wang, and M. Jiang, MIMO-OFDM for LTE, WiFi and WiMAX: Coherent versus non-coherent and cooperative turbo transceivers. John Wiley & Sons, 2011.