Non-Coherent Active Device Identification for Massive Random Access

Consider an mMTC network consisting of $\ell$ users belonging to the set $\mathcal{D}=\{1,2,\ldots,\ell\}$. Among the $\ell$ users, only a subset of $k$ are active and wants to access the channel. We assume that the value of $k$ is periodically estimated at the BS and hence known a-priori [44]. The active user set denoted by $\mathcal{A}=\{a_{1},a_{2}\ldots,a_{k}\}$ is assumed to be randomly chosen among all ${\ell\choose k}$ subsets of size $k$ from $\mathcal{D}$ and is unknown to the BS. The BS aims to identify the active user set $\mathcal{A}$ in a time-efficient manner so that they could be allocated required resources for prompt channel access.

Taking into account sparse user activity, we focus on the asymptotic regime where $\ell$ can be unbounded while the number of active users scale as $k=\Theta(\ell^{\alpha});$ $0\leq\alpha<1$. This is consistent with the notion of Many Access channel (MnAC) model introduced by Chen et al. [29] with the difference that instead of our combinatorial setting with $k$ active users, [29] considers the setting where each user can be active probabilistically.

For purposes of activity detection, each user $i$ is assigned an i.i.d binary preamble $\textbf{X}^{i}\triangleq(\hskip 1.42271ptX_{1}^{i},X_{2}^{i},\ldots X_{n}^{i})\in\{0,\sqrt{P}\}^{n}$ of length $n$ generated via a Bernoulli process with probability $q_{i}$, $\forall i\in\mathcal{D}$. The sampling probability vector is defined as $\textbf{q}:=(q_{1},q_{2},\ldots,q_{\ell})$. We use $\mathcal{P}$ to denote the entire set of preambles. During activity detection, the active users transmit their OOK-modulated preamble in a time-synchronized manner over $n$ channel-uses with power $P$ during the ‘On’ symbols. The received symbol $S_{t}$ during the $t^{th}$ channel-use is

Here, $\textbf{X}_{t}=(X^{1}_{t},\ldots,X^{\ell}_{t})$ is the vector representing the $t^{th}$ preamble entries of the $\ell$ users and $\textbf{h}_{t}=(h^{1}_{t},\ldots,h^{\ell}_{t})$ is the vector of channel coefficients of the $\ell$ users during the $t^{th}$ channel-use where $h_{t}^{i}$’s are i.i.d $\mathcal{C}\mathcal{N}\left(0,\sigma^{2}\right),\forall i\in\mathcal{D},\forall t\in\{1,2,\ldots n\}$. The AWGN noise vector $\textbf{W}=(W_{1},\ldots,W_{n})$ is composed of i.i.d entries, $W_{t}\sim\mathcal{C}\mathcal{N}\left(0,\sigma_{w}^{2}\right)$ and is independent of $\textbf{h}_{t}$ $\forall t\in\{1,2,\ldots,n\}$. The vector $\boldsymbol{\beta}=(\beta_{1},\ldots,\beta_{\ell})$ represents the activity status such that $\beta_{i}=1$, if $i^{th}$ user is active; 0 otherwise. $\boldsymbol{\beta}\circ\mathbf{h}_{t}$ denotes the element-wise product between the vectors $\boldsymbol{\beta}$ and $\mathbf{h}_{t}$.

We assume that there is no CSI available at the BS since we are operating in a fast fading scenario such as FHSS or mobile IoT environments [45, 32]. i.e., $\textbf{h}_{t},\forall t\in\{1,2,\ldots,n\}$ is unknown a-priori. Hence, the BS employs non-coherent detection [7] as shown in Fig. 1. During the $t^{th}$ channel use, the envelope detector processes $S_{t}$ to obtain $Y_{t}=|S_{t}|$, the envelope of $S_{t}$. Thresholding after envelope detection produces a binary output $Z_{t}$ such that

Here, $\gamma$ represents a pre-determined threshold parameter.

Here onwards, we use the terminology non-coherent $(\ell,k)$-MnAC to refer to the constrained version of $(\ell,k)$-MnAC channel model described above where devices are limited by OOK preamble transmissions and base station is limited by non-coherent energy detection.

Given the preambles $\mathcal{P}=\{\textbf{X}^{i}:i\in\mathcal{D}\}$ and the vector $\textbf{Z}=(Z_{1},\ldots,Z_{n})$ of channel outputs, BS aims to identify the set of active users $\mathcal{A}$, alternatively the vector $\boldsymbol{\beta}$, during the activity detection phase. We use the following definitions:

Note that the minimum user identification cost $n(\ell)$ is a function of the number of users $\ell$ and is defined based on its asymptotic behaviour as $\ell\rightarrow\infty$.

Our goal is to characterize $n(\ell)$ of the non-coherent $(\ell,k)-$MnAC which would be indicative of the time-efficiency of BS in identifying the active users.

GT problem [35] is a sparse inference problem where the objective is to identify a sparse set of defective items from a large set of items by performing tests on groups of items. In the error-free scenario, each group test produces a binary output where a 1 corresponds to the inclusion of at least one defective in the group being tested whereas a 0 indicates that the tested group of items excludes all defectives. The tests need to be devised such that the defective set of items can be recovered using the binary vector of test outcomes with a minimum number of tests. On a high level, GT models can be classified as adaptive and non-adaptive models. In adaptive GT, the previous test results can be used to design the future tests. In non-adaptive setting, all group tests are designed independent of each other.

To draw the equivalence between active device identification in the non-coherent $(\ell,k)$-MnAC and GT, we can consider the devices in the mMTC network as items and the active devices as defective items. Each channel-use $t\in\{1,2,\ldots,n\}$ corresponds to a group test in which a randomly chosen subset of devices engage in joint transmission of ‘On’ symbols, if active. The random selection of devices during the $n$ testing instances is based on the binary preambles $\textbf{X}^{i}\in\{0,\sqrt{P}\}^{n},\forall i\in\mathcal{D}$. The BS measures received energy during each channel-use and produces a binary 0-1 output $Z_{t}$ as in (2). These 1-bit energy measurements at the receiver side corresponds to the group test results.

In summary, the random binary preambles and the binary energy measurements renders active device identification as a GT problem where testing corresponds to energy detection on the received signal envelope. This is illustrated in Fig. 1 and Fig. 2. Note that active device identification in non-coherent $(\ell,k)$-MnAC is a noisy GT problem since channel noise and fading can probabilistically lead to a 0 or 1 energy detector output even in the presence or absence of active devices respectively. Moreover, our framework corresponds to non-adaptive GT since the testing/grouping pattern is based on predefined binary preambles and is not updated based on the GT results of previous channel-uses. We will observe in Section III that the GT model can be leveraged to provide an achievability scheme to the minimum user identification cost for the non-coherent $(\ell,k)-$MnAC when $\alpha=0$, ie., $k=O(1)$ and a corresponding lower bound when $\alpha\neq 0$.

The aim of active device identification in non-coherent $(\ell,k)-$ MnAC is to identify the set of active devices based on the binary detector output vector Z and the preamble set $\mathcal{P}$. This can be alternatively viewed as a decoding problem in a traditional point to point communication channel as follows: The source message is the activity status vector $\boldsymbol{\beta}$ denoting the set of active users $\mathcal{A}$ and the codebook is the entire set of preambles $\mathcal{P}$. Given $\boldsymbol{\beta}$ for an active set $\mathcal{A}=\{a_{1},\ldots a_{k}\}$, the codeword becomes the corresponding subset of preambles $\{\textbf{X}^{i}:i\in\mathcal{A}\}$. Note that since the preambles for each user $i\in\mathcal{A}$ are independently designed using a $Bern(q_{i})$ random variable, our equivalent channel model has the additional constraint that the only tunable parameters available for codebook design are the sampling probabilities $\{{q}_{i}:i\in\mathcal{D}\}$. Hence, identifying active devices reduces to the problem of decoding messages in this equivalent constrained channel. Clearly, the minimum user identification cost for the non-coherent $(\ell,k)-$MnAC is at least the number of channel-uses required to communicate the set of active users; i.e., $\log{\ell\choose k}$ bits of information over this equivalent constrained point-to-point channel. We formally setup this equivalent channel model below.

Considering the channel in Fig. 1, since the set of active users is $\mathcal{A}=\{a_{1},\ldots a_{k}\}$, the input to the non-coherent $(\ell,k)-$MnAC is $\tilde{\textbf{X}}=(X^{a_{1}},\ldots X^{a_{k}})$. Thus, the signal at the input of envelope detector is $S=\sqrt{P}\sum_{m=1}^{k}h^{a_{m}}+W.$ Let $V=\frac{\sum_{i=1}^{k}X^{a_{i}}}{\sqrt{P}}$ denote the Hamming weight of $\tilde{\textbf{X}}$ which is the number of active users transmitting ‘On’ signal during the particular channel-use we have at hand. Thus, conditioned on $V=v$, $U:=|S|^{2}$ follows an exponential distribution given by

As evident from (2) and (4), we have $\tilde{\textbf{X}}\rightarrow V\rightarrow Z$, i.e., the transition probability $p\left(z\mid\tilde{\textbf{x}},v\right)$ is only dependent on the channel input $\tilde{\textbf{X}}=(X^{a_{1}},X^{a_{2}},\ldots X^{a_{k}})$ through its Hamming weight $V$. Also, since $f_{U|V}$ is an exponential distribution, $p_{v}:=p\left(Z=0\mid V=v\right)$ can be expressed as

Similarly, $\operatorname{Pr}\left(Z=1\mid V=v\right)=1-p_{v}.$ Note that $p_{v}$ is a strictly decreasing function of $v$ where $v\in\{0,1,..,k\}$ assuming w.l.o.g. positive values for $\sigma^{2},\sigma_{w}^{2}$ and $\gamma$.

Thus, the non-coherent $(\ell,k)-$MnAC can be equivalently viewed as a traditional point-to-point communication channel whose input is the active user set as in Fig. 3. Moreover, this equivalent channel can be modeled as a cascade of two channels; the first channel computes the Hamming weight $V$ of the input $\tilde{\textbf{X}}$ whereas the second channel translates the Hamming weight $V$ into a binary output $Z$ depending on the fading statistics $(\sigma^{2})$, noise variance $(\sigma_{w}^{2})$ of the wireless channel and the non-coherent detector threshold $\gamma$. We exploit this cascade channel structure to establish the minimum user identification cost $n(\ell)$ for the non-coherent $(\ell,k)-$MnAC.

Note that the minimum user identification cost $n(\ell)$ for the non-coherent $(\ell,k)-$MnAC, must obey $n(\ell)\geq\frac{\log{\ell\choose k}}{C}$. However, we cannot directly claim that $n(\ell)$ exactly matches the number of channel-uses required to send $\log{\ell\choose k}$ bits of information over the equivalent channel at maximum rate $C$. The reason is that the effective codeword corresponding to a user set $\mathcal{A}$ is the subset of preambles $\{\textbf{X}^{i}:i\in\mathcal{A}\}$ indexed by the set $\mathcal{A}$. Thus, the effective codewords of different user sets are potentially dependent due to overlapping preambles. This is in contrast to the independent codeword assumptions typical to channel capacity analysis thereby rendering the traditional random coding approach ineffective. We close this gap by making use of the equivalence of active device identification and GT to propose a decoding scheme achieving the minimum user identification cost as presented below.

N-COMP is a decoding strategy for noisy GT proposed by Chan et al. in [42]. The basic idea is to declare an item to be defective or non-defective based on the fraction of positive tests they participate in [51]. This significantly simplifies the run-time and storage requirements in comparison to the optimal exhaustive search strategy in Algorithm 1. As established in Section III, the active device identification framework in non-coherent $(\ell,k)-$MnAC can be viewed as a GT problem. This motivates us to study the performance of N-COMP approach in identifying active devices in the non-coherent $(\ell,k)-$MnAC. Note that in the existing literature, the N-COMP GT decoder was primarily analyzed in the context of symmetric noise models wherein errors in test results are equally likely [7, 52]. In contrast, the active device identification problem as modeled by the equivalent channel in Fig.3 has an asymmetric noise and hence requires further investigations to validate its performance. Another work which considers N-COMP GT decoder is [49] where the focus is on the problem of neighbor discovery in a wireless sensor network rather than the massive random access setting considered in this paper.

Let $\mathcal{G}_{i}:=\frac{\sum_{t=1}^{n}X^{i}_{t}}{\sqrt{P}}$ denote the Hamming weight of $\textbf{X}^{i}$, the binary preamble assigned to user $i$. In other words, $\mathcal{G}_{i}$ indicates the number of channel uses in which the user $i$ transmits ‘On’ symbols if it is in active state. Let $\mathcal{R}_{i}:=\frac{\sum_{t=1}^{n}X^{i}_{t}Z_{t}}{\sqrt{P}}$ denote the number of these channel uses in which the received energy at the detector exceeds a predetermined threshold. In N-COMP based user identification, our strategy is to classify the $k$ users with highest value for $\frac{\mathcal{R}_{i}}{\mathcal{G}_{i}}$ as active.

We conducted simulations of the N-COMP strategy to analyze the number of channel-uses required for identifying the active devices successfully. We considered two different success criterion, viz, exact recovery in which all active devices are to be correctly identified and 90$\%$ recovery ($\zeta=90)$ in which we require atleast 90$\%$ of the active devices to be correctly identified. In other words, with 90$\%$ recovery, we are willing to tolerate upto 10$\%$ of false positives and false negatives. Fig. 4 and Fig. 5 show how the probability of successful identification varies with the number of channel-uses for $\ell=1000$ users with $k=25$. We considered different values for the SNR (defined as $\frac{P\sigma^{2}}{\sigma_{w}^{2}}$) ranging from 0 dB to 10 dB. As expected, with increase in SNR, N-COMP decoding performance gets better leading to a faster identification of active devices in the network. From Fig. 5, one can infer that relaxing the success criteria to 90$\%$ recovery improves the probability of successful identification significantly.

BP is an efficient method for solving sparse inference problems by iteratively propagating messages over the edges of the factor graph [43]. BP is known to produce good approximations to the marginals of the posterior distribution of the variables in the factor graph. In wireless communications, BP is well known in the context of iterative decoding for Turbo and LDPC codes [50]. BP is also used in GT decoding, which is essentially a Boolean sparse inference problem [53, 54]. In [53], the authors considered BP based GT decoding under a noise model that combines the addition and dilution models. In the context of mMTC, BP has been previously studied as a means for unsourced random access the users share the same codebook and the decoder is only required to provide an unordered list of user messages [55].

Recognizing the suitability of BP in sparse recovery problems including GT, we aim to employ a BP based strategy for the problem of active device identification in the non-coherent $(\ell,k)-$MnAC. In BP based user identification, we estimate the set of active devices by approximately performing bitwise-MAP detection through message passing on a bipartite graph with devices on one side and the binary energy measurements on the other side [53]. In contrast to the previous studies in [53], our noise model as given in $(\ref{channeleq})$ incorporating channel fading effects and non-coherent detection at the BS side is more intricate. Note that in [31], Polyanskiy proposed an alternating BP scheme as a candidate practical solution for random access in a quasi-static fading multiple access channel where each user’s transmissions are attenuated by random fading gains, unknown to the receiver. However, [31] considers iterative coding scheme based on LDPC codes and slow fading scenarios whereas our work focus on energy-efficient OOK signaling in a fast fading non-coherent $(\ell,k)-$MnAC.

To identify the activity status vector $\boldsymbol{\beta}$ using the binary vector of energy detector outputs $\textbf{Z}=(Z_{1},\ldots,Z_{n})$, BP relies on an approximate Maximum Aposteriori Probability (MAP) based decoding where instead of maximizing the posterior as a function of all the $\beta_{i}$’s, we use the marginals of the posterior distribution. i.e., $\widehat{\beta_{i}}=\underset{\beta_{i}\in\{0,1\}}{\arg\max}\hskip 2.0pt\mathbb{P}\left(\beta_{i}\mid\mathbf{Z}\right)$. This approximation drastically reduces the search space corresponding to the original MAP optimization. $\widehat{\beta_{i}}$ can be rewritten as

Eqn. (17) can be approximately computed using loopy BP based on a bipartite graph with $\ell$ devices at one side and the $n$ energy detector outputs at the other side. The priors $p\left(\beta_{j}\right)$’s are initialized to $\frac{k}{\ell}$ and updated through message passing in further iterations. Note that

since $Z_{t}$ depends on $\boldsymbol{\beta}$ only through $V$ (defined in Section III.A), the number of active devices transmitting ‘On’ symbols during the $t^{th}$ channel-use. This symmetry as illustrated in our equivalent channel model in Fig.3 is key in guaranteeing an efficient computation of BP message update rules [53]. We employ BP with Soft Thresholding (BP-ST) in which we classify the $k$ users with the highest marginals as active. Similar to the NCOMP strategy, we observed that BP-ST decoding performance shows improvement with SNR (plots are omitted for brevity).

In Fig. 7 and Fig. 7, we compare the probability of successful identification in a $(1000,25)$-MnAC at SNR = 10 dB for BP-ST and NCOMP strategies under the two success criterion, viz, exact and $90\%$ recovery. As evident, BP shows significant performance gains over NCOMP which translates to faster identification of active devices. Moreover, the curves indicate that if we are willing to relax the success criterion by setting $\zeta$ to a lower value like $90\%$, both strategies tend to perform better while maintaining the relative order in terms of probability of successful identification. Although N-COMP significantly lags behind BP, owing to its simplicity and non-iterative nature, it still can be used in applications where run-time and hardware complexity is a critical factor.

In Fig. 8, we compare the minimum user identification cost in Theorem 1 with the performance of BP-ST. Evidently, the gap between the BP-ST curve and the minimum user identification cost reduces notably in the high SNR regime. We also observe that BP can approach and even exceed the minimum user identification cost if we relax the success criterion slightly to $90\%$ recovery by allowing room for a small number of misdetections.

Since simulation results indicate that BP is more efficient compared to NCOMP, we restrict our focus to BP in this section. To take into account the uncertainty associated with the size $\hat{k}$ of the estimated active set $\hat{\mathcal{A}}$, we consider an alternate definition for the error event different from (16) as below.

Note that $\mathbb{P}(E_{2})\geq\mathbb{P}(E_{1})$ due to the first term $\left\{k(1-\sigma)\leq\hat{k}\leq k(1+\sigma)\right\}^{\mathrm{c}}$ in (19). It implies that in addition to $E_{1}$, if the estimated active set has a size deviating from the size of the true active set by more than a fraction of $\sigma$, we declare an error. In the case when $k$ is known apriori, we can set $\sigma=0$ and (19) simplifies to (16).