Inspired by group testing algorithms and the coded computation paradigm, we propose and analyze a novel multiple access scheme for detecting active users in large-scale networks. The scheme consists of a simple randomized detection algorithm that uses computation coding as intermediate steps for computing logical disjunction functions over the multiple access channel (MAC). First we show that given an efficient MAC code for disjunction computation the algorithm requires @math decision steps for detecting @math active users out of @math users. Subsequently we present a simple suboptimal code for a class of MACs with arbitrarily varying sub-gaussian noise that uniformly requires @math channel uses for solving the activity detection problem. This shows that even in the presence of noise an efficient detection of active users is possible. Our approach reveals that the true crux of the matter lies in constructing efficient codes for computing disjunctions over a MAC.
A result similar to our Corollary appeared in an independent work @cite_11 using a slightly different scheme; we do point out, however, that our result is more general in the sense that we do not restrict the growth of the number of active devices depending on the number of total devices, while the result in @cite_11 , on the other hand, offers a slightly better constant ( @math where we have @math ).
@cite_11
2808785612
In this paper, we study the problem of (AD) in a massive MIMO setup, where the Base Station (BS) has @math antennas. We consider a block fading channel model where the @math -dim channel vector of each user remains almost constant over a (CB) containing @math signal dimensions. We study a setting in which the number of potential users @math assigned to a specific CB is much larger than the dimension of the CB @math ( @math ) but at each time slot only @math of them are active. Most of the previous results, based on compressed sensing, require that @math , which is a bottleneck in massive deployment scenarios such as Internet-of-Things (IoT) and Device-to-Device (D2D) communication. In this paper, we show that one can overcome this fundamental limitation when the number of BS antennas @math is sufficiently large. More specifically, we derive a on the parameters @math and also (SNR) under which our proposed AD scheme succeeds. Our analysis indicates that with a CB of dimension @math , and a sufficient number of BS antennas @math with @math , one can identify the activity of @math active users, which is much larger than the previous bound @math obtained via traditional compressed sensing techniques. In particular, in our proposed scheme one needs to pay only a poly-logarithmic penalty @math for increasing the number of potential users @math , which makes it ideally suited for AD in IoT setups. We propose low-complexity algorithms for AD and provide numerical simulations to illustrate our results. We also compare the performance of our proposed AD algorithms with that of other competitive algorithms in the literature.