The Strongly Asynchronous Massive Access Channel

Abstract

This paper considers the Strongly Asynchronous, Slotted, Discrete Memoryless, Massive Access Channel (SAS-DM-MAC) in which the number of users, the number of messages, and the asynchronous window length grow exponentially with the coding blocklength with their respective exponents. A joint probability of error is enforced, ensuring that all the users’ identities and messages are correctly identified and decoded. Achievability bounds are derived for the case that different users have similar channels, the case that users’ channels can be chosen from a set which has polynomially many elements in the blocklength, and the case with no restriction on the users’ channels. A general converse bound on the capacity region and a converse bound on the maximum growth rate of the number of users are derived. It is shown that reliable transmission with an exponential number of users with an exponential asynchronous exponent with joint error probability is possible at strictly positive rates.

1. Introduction

One of the main attributes of the Internet of the Things (IoT) paradigm is the wireless connectivity of large a number of distributed and uncoordinated devices. Each device is automated, and is allowed to transmit random bursts of data without network or human coordination. A contention-based/grant-based network access requires multiple rounds of back and forth transmissions between the device and the network to acquire synchronization, identify users, and grant them allocations. This signaling overhead and power consumption is not justified for power-limited devices with sporadic traffic patterns and motivates a grant-free network access implementation. An un-coordinated network access leads to a new traffic patterns and collision resolutions over the wireless network. A foundational study of such a system is needed.

We propose a novel communication and multiple-access model that captures these new network characteristics. The formal model definition is given in Section 2, but in order to demonstrate the differences between our proposed model and existing work in the literature, we briefly introduce our model parameters here for the Strongly Asynchronous Slotted Discrete Memoryless Massive Access Channel (SAS-DM-MAC). In a SAS-DM-MAC, the number of users $K_n:=e^{n\nu }$ increases exponentially with blocklength n with occupancy exponent $\nu \ge 0$. Moreover, the users are strongly asynchronous, meaning, they transmit at a randomly chosen time slot within a window of length $A_n:=e^{n\alpha }$ slots, each slot of length n, where $\alpha \ge 0$ is the asynchronous exponent. In addition, when active, each user chooses uniformly at random one message to transmit from a set of $M_n:=e^{nR}$ messages, where $R\ge 0$ is the transmission rate. All transmissions are sent to an access point and the receiver is required to jointly decode and identify all users. The goal is to characterize the set of all achievable $(R,\alpha ,\nu )$ triplets.

1.1. Past Work

Strongly asynchronous communication was first introduced in [1] for synchronization of a single user, and later extended in [2] for synchronization with positive transmission rate.

In [3] the authors of [2] made a brief remark about a “multiple access collision channel” extension of their original single-user model. In this model, any collision of users (i.e., users who happen to transmit in the same block) is assumed to result in output symbols that appear distributed as noise. The error metric is taken to be the per user probability of error, which is required to be vanishing for all but a vanishing fraction of users. In this scenario, it is fairly easy to quantify the capacity region for the case that the number of users are less than the square root of the asynchronous window length (i.e., in our notation $\nu <\alpha /2$). However, finding the capacity of the “multiple access collision channel” for joint probability of error, as opposed to per user probability of error, is much more complicated and requires novel achievability schemes and novel analysis tools. This is the main subject and contribution of this paper.

Recently, motivated by the emerging machine-to-machine type communications and sensor networks, a large body of work has studied “many-user” versions of classical multiuser channels as pioneered in [4]. In [4] the number of users is allowed to grow at most linearly with the blocklength n. A full characterization of the capacity of the synchronous Gaussian (random) many access channel was given [4]. In [5], the author studied the synchronous massive random access channel where the total number of users increases linearly with the blocklength n. However, the users are restricted to use the same codebook and only a per user probability of error is enforced. In the model proposed here, the users are strongly asynchronous, the number of users grows exponentially with the blocklength, and we enforce a joint probability of error over all users.

In [6,7] a broadcast channel model was introduced where each receiver is only interested in decoding its intended messaged (and not all messages). For a per user/per pair of users probability of error criteria doubly exponential number of receivers was shown to be identifiable by using a randomized code. In this work we study a multi-access channel model with non-cooperative transmitters and a single receiver which needs to decode all messages from all users.

Training based synchronization schemes (i.e., pilot signals) was proven to be suboptimal for bursty communications in [2]. Rather, one can utilize the users’ statistics at the receiver for synchronization or user identification purposes. The identification problem (defined in [8]) is a classical problem considered in hypothesis testing. In this problem, a finite number of distinct sources each generates a sequence of i.i.d. samples. The problem is to find the underlying distribution of each sample sequence, given the constraint that each sequence is generated by a distinct distribution.

All studies on identification problems assume a fixed number of sequences. In [9], authors study the Logarithmically Asymptotically Optimal (LAO) Testing of identification problem for a finite number of distributions. The authors in [10] also propose a test for a generalized Neyman-Pearson-like optimality criterion to match multiple yet finite number of sequences to their source distributions.

In contrast, we allow the number of users to increase exponentially with the blocklength. We assume that the users are strongly asynchronous and may transmit randomly anytime within a time window that is exponentially large in the blocklength. We require the receiver to recover both the transmitted messages and the users’ identities under a joint probability of error criteria. By allowing the number of sequences to grow exponentially with the number of samples, the number of different possibilities (or hypotheses) would be doubly exponential in the blocklength and the analysis of the optimal decoder becomes much more challenging than classical (with constant number of distributions) identification problems. These differences in modeling the channel require a number of novel analytical tools.

1.2. Contribution

We consider $(R,\alpha ,\nu )$, the capacity region of the SAS-DM-MAC, where we require the joint probability of error to vanish. Our contributions are as follows:

• We propose a new achievability scheme that supports strictly positive values of $(R,\alpha ,\nu )$ for identical channels for the users.
• We define a new massive identification paradigm in which we allow the number of sequences in a classical identification problem to increase exponentially with the sequence blocklength (or sample size). We find asymptotically matching upper and lower bounds on the probability of identification error for this problem. We use this result in our SAS-DM-MAC model to recover the identity of the users.
• We propose a new achievability scheme for the case that the channels are chosen from a set of conditional distributions. The size of the set increases polynomially in the blocklength n. In this case, the channel statistics themselves can be used for user identification.
• We propose a new achievability scheme without imposing any restrictive assumptions on the users’ channels. We show that strictly positive $(R,\alpha ,\nu )$ are possible.
• We propose a novel converse bound for the capacity of the SAS-DM-MAC.
• We show that for $\nu >\alpha$, not even reliable synchronization is possible.

These results were presented in parts in [11,12,13].

1.3. Paper Organization

In Section 2 we introduce the notation and problem formulation for SAS-DM-MAC and the identification problem. We present our main results in Section 3. Section 4 concludes the paper with a discussion and future work. Proofs are provided in the Appendix.

2. Notations and Problem Formulation

We first introduce the notation used in the SAS-DM-MAC and then formally define the problem.

2.1. Notation

Capital letters represent random variables that take on lower case letter values in calligraphic letter alphabets. The notation $a_n\doteq e^{nb}$ means ${lim}_{n\to \infty }\frac{log{a}_n}{n}=b$. We write $[M:N]$, where $M,N\in \mathbb{Z},M\le N$, to denote the set $\{M,M+1,\dots ,N\}$, and $\left[K\right]:=[1:K]$. $y^n$ is used to denote $y^n:=[y_1,\dots ,y_n]$. The n-fold cartesian product of a set S is denoted by $S^n$.

A transition probability/channel from $\mathcal{X}$ to $\mathcal{Y}$ is denoted by $Q\left(y\right|x)$ (or Q by short), $\forall (x,y)\in \mathcal{X}\times \mathcal{Y}$, and the output marginal distribution induced by $P\in {\mathcal{P}}_{\mathcal{X}}$ through the channel Q as

$$\begin{array}{c}\hfill \left[PQ\right]\left(y\right):=\sum _{x\in \mathcal{X}}P\left(x\right)Q\left(y\right|x),\forall y\in \mathcal{Y},\end{array}$$

(1)

where ${\mathcal{P}}_{\mathcal{X}}$ is the space of all distributions on $\mathcal{X}$. We define the shorthand notation

$$\begin{array}{cc}\hfill Q_x\left(y\right)& :=Q\left(y\right|x),\forall y\in \mathcal{Y}.\hfill \end{array}$$

(2)

For a MAC channel $Q\left(y\right|x_1,\dots ,x_K),\forall (x_1,\dots ,x_K,y)\in {\mathcal{X}}_1\times \dots \times {\mathcal{X}}_K\times \mathcal{Y}$, we define the shorthand notation

$$\begin{array}{cc}\hfill Q_S\left(y|x_S\right)& :=Q\left(y\right|x_S,{\star }_{S^c}),\forall S\subseteq \left[K\right],\hfill \end{array}$$

(3)

to indicate that users indexed by S transmit $x_i\in {\mathcal{X}}_i,\forall i\in S$, and users indexed by $S^c=\left[K\right]\setminus S$ transmit their respective idle symbol ${\star }_j\in {\mathcal{X}}_j\forall j\in S^c$. When $\left|S\right|=1$ and $\left|S\right|=0$, we respectively use

$$\begin{array}{cc}\hfill Q_i\left(y\right|x_i)& :=Q_{\left\{i\right\}}\left(y\right|x_i)=Q\left(y\right|{\star }_1,\dots ,{\star }_{i-1},x_i,{\star }_{i+1},\dots ,{\star }_K),\hfill \\ \hfill Q_{\star }\left(y\right)& :=Q_{\{\varnothing \}}\left(y\right|x_i)=Q\left(y\right|{\star }_1,\dots {\star }_K).\hfill \end{array}$$

(4)

The P-type set and the V-shell of the sequence $x^n$ are defined, respectively, as

$$\begin{array}{cc}\hfill T\left(P\right)& :=\left\{x^n:\frac{\mathcal{N}\left(a\right|x^n)}{n}=P\left(a\right),\forall a\in \mathcal{X}\right\},\hfill \end{array}$$

(5)

$$\begin{array}{cc}\hfill T_V\left(x^n\right)& :=\left\{y^n:\frac{\mathcal{N}\left(a,b|x^n,y^n\right)}{\mathcal{N}\left(a\right|x^n)}=V\left(b\right|a),\forall (a,b)\in (\mathcal{X},\mathcal{Y})\right\},\hfill \end{array}$$

(6)

where $\mathcal{N}(a,b|x^n,y^n)={\sum }_{i=1}^n{\mathbb{1}}_{\left\{\begin{array}{c}{x}_i=a\\ y_i=b\end{array}\right\}}$ is the number of joint occurrences of $(a,b)$ in the pair of sequences $(x^n,y^n)$ and where $\mathcal{N}\left(a\right|x^n)$ denotes the number of occurrences of $a\in \mathcal{X}$ in the sequence $x^n$. The empirical distribution of the sequence $x^n$ is

$$\begin{array}{c}\hfill {\widehat{P}}_{x^n}\left(a\right):=\frac{1}{n}\mathcal{N}\left(a\right|x^n)=\frac{1}{n}\sum _{i=1}^n{\mathbb{1}}_{\{x_i=a\}},\forall a\in \mathcal{X}.\end{array}$$

(7)

If in using (7) the target sequence $x^n$ is clear from the context, we drop the subscript $x^n$ in ${\widehat{P}}_{x^n}(·)$.

We also use the notation $X^n\stackrel{\mathrm{i}.\mathrm{i}.\mathrm{d}}{\sim }P$ when all random variables in the random vector $X^n$ are generated i.i.d according to distribution P.

We use $D(P_1\Vert P_2)$ to denote the Kullback Leibler divergence between distribution $P_1$ and $P_2$, and

$$\begin{array}{c}\hfill D(Q_1\Vert Q_2\left|P\right):=\sum _{(x,y)\in (\mathcal{X}\times \mathcal{Y})}P\left(x\right)Q_1\left(y\right|x)log\frac{Q_1\left(y\right|x)}{Q_2\left(y\right|x)}\end{array}$$

(8)

for the conditional Kullback Leibler divergence. We let

$$\begin{array}{c}\hfill I(P,Q)=D(Q\Vert [PQ\left]\right|P)\end{array}$$

(9)

denote the mutual information between random variables X and Y jointly distributed according to $P_{X,Y}(x,y)=P\left(x\right)Q\left(y\right|x)$. As for binary functions, we use

$$\begin{array}{cc}\hfill d(p\Vert q)& :=plog\frac{p}{q}+(1-p)log\frac{1-p}{1-q},\hfill \\ \hfill p\ast q& :=p(1-q)+(1-p)q,\hfill \\ \hfill h\left(p\right)& :=-plog\left(p\right)-(1-p)log(1-p)\hfill \end{array}$$

to represent binary divergence, convolution and entropy functions, respectively.

The Chernoff distance and the Bhatcharrya distance between two distributions $P_1,P_2\in {\mathcal{P}}_{\mathcal{X}}$ are respectively defined as

$$\begin{array}{cc}\hfill C(P_1,P_2)& :=\underset{0\le t\le 1}{sup}-log\left(\sum _{x\in \mathcal{X}}{P}_1{\left(x\right)}^t{P}_2{\left(x\right)}^{1-t}\right),\hfill \end{array}$$

(10)

$$\begin{array}{cc}\hfill B(P_1,P_2)& :=-log\left(\sum _{x\in \mathcal{X}}\sqrt{P_1\left(x\right)P_2\left(x\right)}\right).\hfill \end{array}$$

(11)

We extend this definition and introduce the quantities

$$\begin{array}{cc}\hfill C(P_i,Q_i,P_j,Q_j)& :=\underset{0\le t\le 1}{sup}{\mu }_{i,j}\left(t\right),\hfill \end{array}$$

(12a)

$$\begin{array}{cc}\hfill {\mu }_{i,j}\left(t\right)& :=-log\sum _{x_i\in \mathcal{X},x_j\in \mathcal{X},y\in \mathcal{Y}}{P}_i\left(x_i\right)P_j\left(x_j\right)Q_i{\left(y\right|x_i)}^{1-t}{Q}_j{\left(y\right|x_j)}^t,\hfill \end{array}$$

(12b)

$$\begin{array}{cc}\hfill C(.,Q_{\star },P_j,Q_j)& :=\underset{0\le t\le 1}{sup}-log\left(\sum _{x\in \mathcal{X},y\in \mathcal{Y}}{P}_j\left(x\right)Q_{\star }{\left(y\right)}^{1-t}{Q}_j{\left(y\right|x)}^t\right).\hfill \end{array}$$

We also use

$$\begin{array}{cc}\hfill E_r(R,P,Q)& :=\underset{0\le \rho \le 1}{max}\left[E_0(R,P,Q,\rho )-\rho R\right],\hfill \end{array}$$

(13)

$$\begin{array}{cc}\hfill E_{sp}(R,P,Q)& :=\underset{\rho >0}{sup}\left[E_0(R,P,Q,\rho )-\rho R\right]\hfill \end{array}$$

(14)

to denote the random coding and the sphere packing error exponent of channel $Q\left(y\right|x)$, with input distribution $P\left(x\right)$ and rate R as defined in [14] where

$$\begin{array}{c}\hfill E_0(R,P,Q,\rho ):=-log\sum _{y\in \mathcal{Y}}{\left(\sum _{x\in \mathcal{X}}P\left(x\right)Q{\left(y\right|x)}^{\frac{1}{1+\rho }}\right)}^{1+\rho }.\end{array}$$

(15)

2.2. SAS-DM-MAC Problem Formulation

Let M be the number of messages (the same for each user), A be the number of blocks, and K be the number of users.

An $(M,A,K,n,ϵ)$ code for the SAS-DM-MAC consists of:

• A message set $\left[M\right]$, for each user $i\in \left[K\right]$.
• An encoding function $f_i:\left[M\right]\to {\mathcal{X}}^n$, for each user $i\in \left[K\right]$. We define

  $$\begin{array}{c}\hfill x_i^n\left(m\right):=f_i\left(m\right).\end{array}$$

  (16)
• Each user $i\in \left[K\right]$ chooses a message $m_i\in \left[M\right]$ and a block index $t_i\in \left[A\right]$ (called ‘active’ block henceforth), both uniformly at random. It then transmits $\left[{\star }_i^{n(t_i-1)}{x}_i^n\left(m_i\right){\star }_i^{n(A-t_i)}\right]$, where ${\star }_i\in \mathcal{X}$ is the designated idle symbol for user i.
• A destination decoding function

  $$\begin{array}{c}\hfill g:{\mathcal{Y}}^{nA}\to {\left(\left[A\right]\times \left[M\right]\right)}^K\end{array}$$

  (17)

  such that its associated probability of error, $P_e^{\left(n\right)}$, satisfies $P_e^{\left(n\right)}\le ϵ$ where

  $$\begin{array}{c}\hfill P_e^{\left(n\right)}:=\frac{1}{{\left(AM\right)}^K}\sum _{(t_1,m_1),\dots ,(t_K,m_K)}\mathbb{P}\left[g\left(Y^{nA}\right)\ne \left((t_1,m_1),\dots ,(t_K,m_K)\right)|H_{\left((t_1,m_1),\dots ,(t_K,m_K)\right)}\right],\end{array}$$

  (18)

  where the hypothesis that user $i\in \left[K\right]$ has chosen to transmit message $m_i\in \left[M\right]$ in block $t_i\in \left[A\right]$ is denoted by $H_{\left((t_1,m_1),\dots ,(t_K,m_K)\right)}$.

A tuple $(R,\alpha ,\nu )$ is said to be achievable if there exists a sequence of codes $\left(e^{nR},e^{n\alpha },e^{n\nu },n,{ϵ}_n\right)$ with ${lim}_{n\to \infty }{ϵ}_n=0$. The capacity region of the SAS-DM-MAC at asynchronous exponent $\alpha$, occupancy exponent $\nu$, and rate R, is the closure of all possible achievable $(R,\alpha ,\nu )$ triplets.

Remark 1.

We should emphasize that we are focusing our attention on discrete memoryless channels (DMC) where a user not transmitting/being idle is equivalent to sending that user’s idle symbol in the DMC model, just as, in a Gaussian channel, a user not sending corresponds to sending the symbol ‘0’. We do not study Continuous channels in this work.

A depiction of a timeline for our channel model is provided in Figure 1a and for specific cases: one in which user 1 and 2 are not simultaneously transmitting (Figure 1b) and another in which user 1 and 2 are simultaneously transmitting (Figure 1c).

2.3. Identification Problem Formulation

We first summarize the notation specifically used in this Section (and in Appendix B) in

Table 1. Special notation for the identification problem.

${\mathit{S}}_{\mathit{A}}$	A symmetric group which is the set of all possible permutations of A elements.
${\sigma }_i$	The i-th element of the permutation $\sigma \in S_A$; $i\in \left[A\right]$.
$K_k$	$:=K_k(w_{\{1,2\}}\dots w_{\{k,1\}})$; A complete graph with k nodes and edge weights $w_{\{i,j\}}$ between node $i,j$.
$c_r^{\left(V\right)},c_r^{\left(E\right)}$	A cycle of length r represented by the set of its vertices and edges, respectively.
$c_r^{\left(V\right)}\left(i\right)$	i-th vertex of the cycle $c_r^{\left(V\right)}$.
$C_k^{\left(r\right)}$	Set of cycles of length r in the complete graph $K_k$.
$N_k^{\left(r\right)}$	Number of cycles of length r in a complete graph $K_k$.
$G\left(c\right)$	$:={\prod }_{\forall i\ne j}{w}_{i,j}$; Gain of a cycle which we define as the product of the edge weights within the cycle c.
AM-GM inequality	Refers to the following inequality $n{\left({\prod }_{i=1}^n{a}_i\right)}^{\frac{1}{n}}\le {\sum }_{i=1}^n{a}_i$.

and then introduce the problem formulation.

Assume $P:=\{P_1,\dots ,P_{T_n}\}\subseteq {\mathcal{P}}_{\mathcal{X}}$ consist of $T_n$ distinct distributions on $\mathcal{X}$ and let random variable $\mathsf{\Sigma }$ be uniformly distributed over $S_{T_n}$ (see definition in Table 1). Let $\sigma \in S_{T_n}$ and let $x^{n{T}_n}=[x_1^n,\dots ,x_{T_n}^n]$ be a sample vector of $X^{n{T}_n}=\left[X_1^n,\dots ,X_{T_n}^n\right]$, in which $X_i^n\stackrel{\mathrm{i}.\mathrm{i}.\mathrm{d}}{\sim }{P}_{{\sigma }_i}^n,\forall i\in \left[T_n\right]$. Given $x^{n{T}_n}$, we would like to find the permutation $\sigma$. More specifically, we are interested in finding a permutation $\widehat{\sigma }:{\mathcal{X}}^{n{T}_n}\to S_{T_n}$ in which $X_i^n\stackrel{\mathrm{i}.\mathrm{i}.\mathrm{d}}{\sim }{P}_{{\widehat{\sigma }}_i},\forall i\in \left[T_n\right]$. Let $\widehat{\mathsf{\Sigma }}=\widehat{\sigma }\left(X^{n{T}_n}\right)$.

The average probability of error for the set of distributions P is defined by

$$\begin{array}{cc}\hfill P_e^{\left(n\right)}& =\mathbb{P}\left[\widehat{\mathsf{\Sigma }}\ne \mathsf{\Sigma }\right]=\frac{1}{\left(T_n\right)!}\sum _{\sigma \in S_{T_n}}\mathbb{P}\left[\widehat{\mathsf{\Sigma }}\ne \sigma \right],\hfill \end{array}$$

(19)

where in (19) the measure $\mathbb{P}$ over $(X_1^n,...,X_{T_n}^n)$ is $X_i^n\stackrel{\mathrm{i}.\mathrm{i}.\mathrm{d}}{\sim }{P}_{{\sigma }_i},\forall i\in \left[T_n\right]$.

We say that a set of distributions P is identifiable if ${lim}_{n\to \infty }{P}_e^{\left(n\right)}\to 0$.

3. Main Results

We first introduce an achievable region for the case that different users have identical channels (in Theorem 1). We then derive the identification criteria (in Theorem 2) and use it in the study of a more general case of massive communications in which the users’ channels belong to a set of conditional probability distributions of polynomial size in n (in Theorem 3). In this case, we use the output statistics to distinguish and identify the users. Afterwards, we remove all conditions on the users’ channels and derive an achievability bound on the capacity of the SAS-DM-MAC in (Theorem 4). We also propose a converse bound on the capacity of general SAS-DM-MAC (in Theorem 5) and a converse bound on the number of users (in Theorem 6).

3.1. Users with Identical Channels

The following theorem is an achievable region for the SAS-DM-MAC for the case that different users have identical channels toward the base station when they are the sole active user.

Theorem 1.

For a SAS-DM-MAC with $Q_{\left\{i\right\}}\left(y\right|x)=W\left(y\right|x)$ (recall Definition (4)) for all users, the following $(R,\alpha ,\nu )$ region is achievable

$$\begin{array}{c}\hfill \bigcup _{\begin{array}{c}P\in {\mathcal{P}}_{\mathcal{X}}\\ \lambda \in [0,1]\end{array}}\left\{\begin{array}{cc}\nu & <\frac{\alpha }{2}\\ \nu & <min\left\{D(W_{\lambda }\Vert W\left|P\right),E_r(R+\nu ,P,W)\right\}\\ \alpha +R+\nu & <D(W_{\lambda }\Vert Q_{\star }|P)\\ R+\nu & <I(P,W)\end{array}\right\},\end{array}$$

(20)

where

$$\begin{array}{c}\hfill W_{\lambda }\left(y\right|x):=\frac{W{\left(y\right|x)}^{\lambda }{Q}_{\star }{\left(y\right)}^{1-\lambda }}{{\sum }_{y^{\prime }\in \mathcal{Y}}W{\left(y^{\prime }\right|x)}^{\lambda }{Q}_{\star }{\left(y^{\prime }\right)}^{1-\lambda }},\forall (x,y)\in \mathcal{X}\times \mathcal{Y},\end{array}$$

(21)

and where $E_r$ was defined in (13).

In the scenario where users have identical channels toward the base station, one can combine the user identification and decoding stages, i.e., one can distinguish the user’s identity from the decoded message. This appears as the combination $R+\nu$ in the bounds in (20).

One could also interpret the result in Theorem 1 as follows. There is one single “big codebook” with $MK$ codewords of length n. User 1 uses codewords with indices 1 through M; User 2 uses codewords with indices $M+1$ through $2M$, and so forth, concluding with User K using codewords with indices $(K-1)M+1$ through $KM$. In each active slot, the receiver decodes the “big codebook”; reliable decoding imposes $log\left(MK\right)/n=R+\nu <I(P,W)$. However, since in our setting we need to decode K codewords (one per active slot, as opposed to just one), in addition to $R+\nu \le I(P,W)$ we also need the bound $log\left(K\right)/n=\nu <E_r(\nu +R,P,W)$. Comparing the third and fourth bounds of (20) with the per-user probability of error achievability region in [3], we can see an additional $\nu$ penalty as a result of a joint probability of error criteria. However, we do not claim (via a matching converse bound) that the rate penalty (at least in the format that we prove) is conclusive.

We should also note that for $\nu <\frac{\alpha }{2}$ (first bound in (20)), with probability approaching one as the blocklength n goes to infinity, the users transmit in distinct blocks. Hence, regardless of the achievability scheme, the probability of error under a hypothesis where a collision has occurred is vanishing as the blocklength goes to infinity. As a result, in analyzing the joint probability of error in our achievability scheme, we need to focus on the hypothesis that users do not collide. In our achievability scheme, we use a two-stage decoder which first synchronizes the users (i.e., finds the location of active blocks) and then decodes the users’ messages (which also identifies the users’ identities). The complete proof of Theorem 1 is given in Appendix A.

Remark 2.

The existence of an error exponent bound on the occupancy exponent (i.e., ν) is intuitive (second argument in the second condition in (20)). Even if the decoder has side information about the location of noisy blocks (i.e., blocks with only idle symbols for all users), it still has to decode all the messages within active blocks. Due to independence of the output in different blocks and by the fact that there cannot be intra-block coding, the probability of decoding error over active blocks is asymptotically equal to the sum of the decoding error probabilities in each active block. This puts a restriction on ν based on the best decay rate for the decoding error in each block, i.e., the error exponent.

3.2. Users with Different Choice of Channels

We now move on to a more general setting in which we remove the restriction that all users have identical channels towards the base station (when only one is active). Theorem 3 gives an achievable region when we allow the users’ channels (when they are the sole active user toward the base station) to be chosen from a set of conditional distributions of polynomial size in the blocklength n.

In this scenario, one may use the users’ statistics at the channel output to identify the set of users who have a similar channel. In this regard, before introducing Theorem 3, we introduce Theorem 2 in which we characterize the relation between the number of distributions and their pairwise distance for them to be identifiable. The proof of Theorem 2, given in Appendix B, is itself based on a novel graph theoretic technique to analyze the optimal Maximum Likelihood (ML) decoder, which is of independent interest.

Theorem 2.

A sequence of distributions $P=\{P_1,\dots ,P_{T_n}\}$ is identifiable iff

$$\begin{array}{c}\hfill \underset{n\to \infty }{lim}\sum _{\begin{array}{c}1\le i<j\le T_n\end{array}}{e}^{-2nB(P_i,P_j)}=0,\end{array}$$

(22)

where $B(P_i,P_j)$ is the Bhatcharrya distance, which was defined in (11).

Remark 3.

From Theorem 2 one can see that when the number of distributions $T_n$ is a constant or grows polynomially with n, the sequence of distributions are always identifiable and by the problem formulation in Section 2.3, it is implied that the probability of error in the identification problem decays to zero as the blocklength n goes to infinity.

By using the criterion for identifiability of a massive number of distributions in Theorem 2, we move on to the SAS-DM-MAC problem. We adapt the concept of identification of distribution to identify the users’ statistics at the output with an optimal ML test. We use the result of Theorem 2 in the derivation of Theorem 3.

Theorem 3.

For a SAS-DM-MAC where $Q_i\left(y\right|x)=W_{c\left(i\right)}\left(y\right|x)$ is the channel for user $i\in \left[K_n\right]$, for $\mathcal{W}:=\left\{{\bigcup }_{i\in \left[K_n\right]}{W}_{c_i}\right\} and \left|\mathcal{W}\right|=poly\left(n\right)$ the region

$$\begin{array}{cc}\hfill & lim\underset{n\to \infty }{inf}{\mathcal{A}}_n,\hfill \end{array}$$

(23)

is achievable where ${\mathcal{A}}_n$ is defined as

$$\begin{array}{cc}\hfill {\mathcal{A}}_n& :=\bigcup _{ϵ>0}\bigcup _{\begin{array}{c}\left(P_1,\dots P_{\left|\mathcal{W}\right|}\right)\in {\mathcal{P}}_{\mathcal{X}}^{\left|\mathcal{W}\right|}\\ \left({\lambda }_1,\dots {\lambda }_{\left|\mathcal{W}\right|}\right)\in {[0,1]}^{\left|\mathcal{W}\right|}\end{array}}\bigcap _{j\in \left[\right|\mathcal{W}\left|\right]}\left\{\begin{array}{cc}{\nu }_j+ϵ& <\frac{\alpha }{2}\\ {\nu }_j+ϵ& <min\left\{D({\left[P_j{W}_j\right]}_{{\lambda }_j}\Vert \left[P_j{W}_j\right]),E_r(R+{\nu }_j,P_j,W_j)\right\}\\ \alpha +ϵ& <D({\left[P_j{W}_j\right]}_{{\lambda }_j}\Vert Q_{\star })\\ 0& <\underset{\begin{array}{c}i\in \left[\right|\mathcal{W}\left|\right]\\ i\ne j\end{array}}{inf}B\left(\left[P_i{W}_i\right],\left[P_j{W}_j\right]\right)\\ R+{\nu }_j+ϵ& <I(P_j,W_j)\end{array}\right\},\hfill \end{array}$$

(24)

and where $E_r$ is defined in (13), $B(P_i,P_j)$ was defined in (11) and

$$\begin{array}{cc}\hfill {\nu }_j& :=\frac{1}{n}log\left({\mathcal{N}}_j\right),\hfill \end{array}$$

$$\begin{array}{cc}\hfill {\mathcal{N}}_j& :=\sum _{i=1}^{K_n}{\mathbb{1}}_{\{Q_i=W_j\}}\mathit{and}\mathit{such}\mathit{that}\sum _{j=1}^{\left|\mathcal{W}\right|}{\mathcal{N}}_j=K_n,\hfill \end{array}$$

(25)

$$\begin{array}{cc}\hfill [P_j{W}_j{]}_{\lambda }\left(y\right)& :=\frac{{\left(\left[P_j{W}_j\right]\left(y\right)\right)}^{\lambda }{\left(Q_{\star }\left(y\right)\right)}^{1-\lambda }}{{\sum }_{y^{\prime }\in \mathcal{Y}}{\left(\left[P_j{W}_j\right]\left(y^{\prime }\right)\right)}^{\lambda }{\left(Q_{\star }\left(y^{\prime }\right)\right)}^{1-\lambda }}.\hfill \end{array}$$

(26)

The proof of Theorem 3 is given in Appendix F.

In the proof of Theorem 3 we propose a three stage decoder which performs the task of synchronization, identification and decoding, sequentially. It is also worth noting that given that the number of users is exponential in the blocklength and the number of channels is only polynomial in the blocklength, there must exist at least a single channel that occupies exponentially many blocks. Hence, it is not surprising to see bounds on the occupancy level of each channel (i.e., ${\nu }_j$) in (24).

Remark 4.

We should note that (as it is apparent in (24)) as long as we have the assumption that the number of user’s channels increase with blocklength n, our optimization space over all users also increases with n and hence our achievability and converse bounds would be dependent on the exact definition of $n\to \infty$ (e.g, compared to (20) in Theorem 1). However, in order to compute these bounds, we only need to optimize with respect to $P_i,i\in \left[K_n\right]$ as opposed to $P^n$ in the conventional n-letter capacity expressions.

3.3. General Case

Now we investigate a SAS-DM-MAC with no restriction on the channels of the users toward the base station. The key ingredient in our analysis is a novel way to bound the probability of error reminiscent of Gallager’s error exponent [14]. We show an achievability scheme that allows a positive lower bound on the R and on $\nu$. This proves that reliable transmission with an exponential number of users with an exponential asynchronous exponent with joint error probability is possible. We use an ML decoder sequentially in each block to identify the active user and its message.

Theorem 4.

For a SAS-DM-MAC the following region is achievable

$$\begin{array}{c}\hfill lim\underset{n\to \infty }{inf}\bigcup _{ϵ>0}\bigcup _{\begin{array}{c}\left(P_1,\dots P_{K_n}\right)\in {\mathcal{P}}_{\mathcal{X}}^{K_n}\end{array}}\bigcap _{i\in \left[K_n\right]}\left\{\begin{array}{cc}\nu & <\frac{\alpha }{2}\\ \nu +R+ϵ& <C(P_i,Q_i,P_i,Q_i),\\ 2\nu +R+ϵ& <\underset{\begin{array}{c}j\in \left[K_n\right]\\ j\ne i\end{array}}{inf}C(P_i,Q_i,P_j,Q_j),\\ \alpha +\nu +R+ϵ& <C(.,Q_{\star },P_i,Q_i),\end{array}\right\}\end{array}$$

(27)

The proof of Theorem 4 is given in Appendix G.

Remark 5.

Note that one can show the following (see Appendix H):

$$\begin{array}{cc}\hfill C(P_i,Q_i,P_i,Q_i)& =-log\sum _{x,x^{\prime },y}{P}_i\left(x\right)P_i\left(x^{\prime }\right)\sqrt{Q_i\left(y\right|x)Q_i\left(y\right|x^{\prime })},\hfill \end{array}$$

(28a)

$$\begin{array}{cc}\hfill C(.,Q_{\star },P_i,Q_i)& \le I(P_i,Q_i)+D\left(\left[P_i{Q}_i\right]\Vert Q_{\star }\right),\hfill \end{array}$$

(28b)

where (28a) is the special case of $E_0(R,P,Q,\rho =1)$ in (15), and the right hand side of (28b) is the bound on $\alpha +R$ in the single user strong asynchronous channel [15]. From (28) and (27) we thus see that

$$\begin{array}{cc}\hfill \nu & <E_r(R,P_i,Q_i),\hfill \\ \hfill \alpha +R& <I(P_i,Q_i)+D\left(\left[P_i{Q}_i\right]\Vert Q_{\star }\right)-\nu ,\hfill \end{array}$$

which shows that the second and fourth bounds in (27) are, respectively, less than the synchronous channel error exponent and the point-to-point strong asynchronous channel capacity.

3.4. Example

Consider the SAS-DM-MAC with input-output relationship $Y={\sum }_{i\in \left[K_n\right]}{X}_i\oplus Z$ with $Z\sim \mathrm{Bernoulli}\left(\delta \right)$ for some $\delta \in (0,1/2)$. In our notation

$$\begin{array}{cc}\hfill Q\left(y\right|x)& =\mathbb{P}[X_i\oplus Z=y|X_i=x]=\mathbb{P}[Z=x\oplus y]\hfill \\ & =\left\{\begin{array}{cc}1-\delta \hfill & x\oplus y=0(i.e.,x=y)\hfill \\ \delta \hfill & x\oplus y=1(i.e.,x\ne y)\hfill \end{array}\right..\hfill \end{array}$$

Assume that the input distribution used is $P=\mathrm{Bernoulli}\left(p\right)$ for some $p\in (0,1/2)$. The achievability region in Theorem 1, is

$$\begin{array}{c}\hfill \bigcup _{\begin{array}{c}p\in [0,\frac{1}{2}]\\ \lambda \in [0,1]\end{array}}\left\{\begin{array}{cc}\nu & <\alpha /2\\ \nu & <min\left\{p·d({ϵ}_{\lambda }\Vert \delta ),\underset{q\in [0,1]}{min}\left\{d(\delta \Vert q)+max\{0,d(q\Vert \frac{1}{2})-R-\nu \right\}\right\}\\ \alpha +R+\nu & <p·d({ϵ}_{\lambda }\Vert 1-\delta )\\ R+\nu & <h(p\ast \delta )-h\left(\delta \right)\end{array}\right\},\end{array}$$

(29)

where ${ϵ}_{\lambda }:=\frac{{\delta }^{\lambda }{(1-\delta )}^{(1-\lambda )}}{{\delta }^{\lambda }{(1-\delta )}^{(1-\lambda )}+{(1-\delta )}^{\lambda }{\delta }^{(1-\delta )}}$.

Moreover, by assuming $P_i=\mathrm{Bernoulli}\left(p_i\right)$ for all $i\in \left[K_n\right]$, we can show that the optimal t in $C(P_i,Q_i,P_j,Q_j)={sup}_t{\mu }_{i,j}\left(t\right)$ is $t=1/2$ and hence the achievability region in Theorem 4 is

$$\begin{array}{c}\hfill lim\underset{n\to \infty }{inf}\bigcup _{ϵ>0}\bigcup _{\begin{array}{c}\left(P_1,\dots P_{K_n}\right)\in {\mathcal{P}}_{\mathcal{X}}^{K_n}\end{array}}\bigcap _{i\in \left[K_n\right]}\left\{\begin{array}{cc}\nu & <\frac{\alpha }{2}\\ \nu +R+ϵ& <B(P_i,Q)=g(p_i\ast p_i,\delta )\\ 2\nu +R+ϵ& <\underset{i\ne j}{inf}C(P_i,Q,P_j,Q)=\underset{i\ne j}{inf}g(p_i\ast p_j,\delta )\\ \alpha +\nu +R+ϵ& <C(.,Q_{\star },P_i,Q)=g(p_i,\delta )\end{array}\right\},\end{array}$$

where

$$\begin{array}{c}\hfill g(a,b):=-log\left(1-a+2a\sqrt{b(1-b)}\right).\end{array}$$

Finally, by symmetry, we can see that the optimal $p_i=\frac{1}{2},\forall i\in \left[K_n\right]$ and hence $g(\frac{1}{2},\delta )=-log\left(1/2+\sqrt{\delta (1-\delta )}\right)>0$. So on the BSC($\delta$) strictly positive rates and $\nu$ are achievable. In this regard, the region in Theorem 4 reduces to

$$\begin{array}{c}\hfill \alpha +\nu +R<-log\left(1/2+\sqrt{\delta (1-\delta )}\right).\end{array}$$

(30)

The achievable region in (29) for $(\alpha ,\nu ,R)$ is shown in Figure 2a. In addition, the achievable region for $(\alpha ,\nu ,R)$ with the achievable scheme in Example (30) is also plotted in Figure 2b for comparison. Figure 2 shows that the achievable scheme in Theorem 1 indeed results in a larger achievable region than the one in Theorem 4.

The fact that the achievability region for Theorem 1 is larger than the achievability region of Theorem 4 for identical channels is not surprising. In Theorem 1 we separated the synchronization and decoding steps, whereas in Theorem 4 synchronization and codeword decoding was done the same time but sequentially for each block. The sequential block decoding step results in a smaller achievability region in Theorem 4.

3.5. Converse on the Capacity Region of the SAS-DM-MAC

Thus far, we have provided achievable regions for the SAS-DM-MAC when different users have identical channels; when their channels belong to a set of channels with size that grows polynomially in the blocklength; and without any restriction on the users’ channels. Theorem 5 next provides a converse to the capacity region of the general SAS-DM-MAC.

Theorem 5.

For the SAS-DM-MAC, such that $\nu <\alpha /2$, the following region is impermissible

$$\begin{array}{c}\hfill lim\underset{n\to \infty }{inf}\bigcup _{ϵ>0}\bigcap _{\begin{array}{c}\left(P_1,\dots P_{K_n}\right)\in {\mathcal{P}}_{\mathcal{X}}^{K_n}\\ \left({\lambda }_1,\dots {\lambda }_{K_n}\right)\in {[0,1]}^{K_n}\end{array}}\left\{\begin{array}{c}\left\{\nu >\frac{1}{K_n}\sum _{i=1}^{K_n}D({Q_i}_{{\lambda }_i}\Vert Q_i\left|P_i\right)+ϵ,\right.\\ \left.\alpha >\frac{1}{K_n}\sum _{i=1}^{K_n}D({Q_i}_{{\lambda }_i}\Vert Q_{\star }\left|P_i\right)-(1-{\overline{r}}_n)(\nu +R)+ϵ\right\}\\ \bigcup \\ \left\{\nu >\frac{1}{K_n}\sum _{i=1}^{K_n}{E}_{sp}(R,P_i,Q_i)+ϵ\right\}\\ \bigcup \\ \left\{R>I(P_i,Q_i)+ϵ\right\}\end{array}\right\},\end{array}$$

(31)

where ${\overline{r}}_n$ is the infimum probability of error, over all estimators T, in distinguishing different hypothesis ${Q_i}_{{\lambda }_i}\left(y^n\right|x_i^n\left(m\right)),i\in \left[K_n\right],m\in \left[M_n\right]$, i.e.,

$$\begin{array}{c}\hfill {\overline{r}}_n:=\underset{T}{inf}\frac{1}{K_n{M}_n}\sum _{i=1}^{K_n}\sum _{m=1}^{M_n}{Q_i}_{{\lambda }_i}(T\ne i,m|x_i^n\left(m\right))).\end{array}$$

(32)

Proof. 

The complete proof is given in Appendix I. □

The first bound in (31) corresponds to synchronization, while the second and third bounds correspond to decoding. Also, as it was noted before in Remark 2, one can again see that the value of $\nu$ is restricted by the decoding error exponent.

3.6. Converse on the Number of Users in a SAS-DM-MAC

In previous sections, we restricted ourselves to the regime where $\nu <\frac{\alpha }{2}$. However, an interesting question is how large a $\nu$ can be. Theorem 6 provides a converse bound on the value of $\nu$ such that for $\nu >\alpha$, not even reliable synchronization is possible.

Theorem 6.

For a SAS-DM-MAC with $\nu >\alpha$, reliable synchronization is not possible, i.e., even with $M=1$, one has $P_e^{\left(n\right)}>0.$

The complete proof can be found in Appendix J.

4. Discussion and Conclusions

In this paper we studied a Strongly Asynchronous and Slotted Massive Access Channel (SAS-DM-MAC) where $K_n:=e^{n\nu }$ different users transmit a randomly selected message among $M_n:=e^{nR}$ ones within a strong asynchronous window of length $A_n:=e^{n\alpha }$ blocks of n channel uses each. We found inner and outer bounds on the $(R,\alpha ,\nu )$ tuples. Our analysis is based on a joint probability of error in which we required all users’ messages and identities to be jointly correctly decoded at the base station. Our results are focused on the regime $\nu <\frac{\alpha }{2}$, where the probability of user collision vanishes. We proved in Theorem 6 that for the regime $\nu >\alpha$, not even synchronization is possible. We now discuss some of the difficulties in analyzing the region $\frac{\alpha }{2}\le \nu \le \alpha$.

For the region $\nu <\frac{\alpha }{2}$, with probability $\frac{\left(\genfrac{}{}{0pt}{}{A_n}{K_n}\right)}{{\left(A_n\right)}^{K_n}}\to 1$ as blocklength $n\to \infty$, the users transmit in distinct blocks. Hence, in analyzing the probability of error of our achievable schemes, we only need to bound the error under the hypothesis that users do not collide. For $\frac{\alpha }{2}\le \nu \le \alpha$, we need to consider the events where collisions occur. In particular, based on Lemma 1 (proved in the Appendix L), for $\frac{\alpha }{2}\le \nu \le \alpha$, the probability of every arrangement of users is itself vanishing in the blocklength.

Lemma 1.

For the region $\frac{\alpha }{2}\le \nu \le \alpha$ the non-colliding arrangement of users has the highest probability among all possible arrangements, yet, the probability of this event is also vanishing as blocklength n goes to infinity.

As a consequence of Lemma 1, one needs to propose an achievable scheme that accounts for several arrangements (the number of which is non-trivial to the authors) and collision of users and drives the probability of error in these arrangements to zero. It is also worth noting that the number of possible hypotheses is doubly exponential in the blocklength. Finally, it is worth emphasizing that the authors in [16] can get to $\nu \le \alpha$ since they require the recovery of the messages of a large fraction of users, and require the per-user probability of error to be vanishing (rather than the overall or joint probability of error, which is a much stronger condition). To prove whether or not strictly positive $(R,\alpha ,\nu )$ are possible in the region $\frac{\alpha }{2}\le \nu \le \alpha$, with vanishing joint probability of error, is a challenging open problem.