Collaborative Research: CIF: Small: Low-Complexity Algorithms for Unsourced Multiple Access and Compressed Sensing in Large Dimensions

Wireless traffic is increasingly heterogeneous, with growth coming primarily from unattended devices. While early implementations of wireless communication systems have focused on voice telephony, subsequent generations of cellular infrastructures have enabled users to connect more broadly with the Internet, in support of applications such as gaming, browsing, and video watching.

Looking into the future, unattended devices are predicted to grow rapidly and to generate a significant portion of the wireless data traffic. This evolution represents a formidable challenge for current infrastructures because such devices interact with the Internet in fundamentally different ways than humans. Individuals tend to establish sustained connections through their phones or computers, whereas machines often sporadically transmit status updates or control decisions with very short payloads.

Without a fundamental redesign of the medium access control layer, wireless infrastructures will be unable to efficiently carry machine-type traffic, thereby creating a bottleneck for growth and innovation. The main goal of this research effort is to devise pragmatic random access schemes for machine-type data, with an eye towards addressing the aforementioned issues associated with the digital traffic of tomorrow.

Findings from this project are expected to (i) help strengthen digital infrastructures, by now unanimously recognized as a key driver of the economy; (ii) train competent engineers with skills attuned to societal needs; and (iii) broaden participation in science, technology, engineering, and mathematics through recruiting and mentoring.

Close connections will be exploited between multiple-access communication, compressed sensing, and sparse graph inference. The crucial challenges and main innovations arise from the exceedingly large dimensionality of the engineering problems considered, compared to the state-of-the-art. The envisioned structures and algorithms for performing at such scales are rooted in the divide-and-conquer approaches of stochastic binning and splitting data.

Techniques from graph-based codes to modern iterative methods and interference management are expected to play important roles in pushing the boundaries of unsourced random access and inference in large dimensions. The fundamental limits of complexity-constrained algorithms in wireless communications will be characterized by leveraging recently developed tools from finite-block-length information theory, statistical physics, and applied probability.

Key attributes of the proposed models include uncoordinated access and the ability to operate without explicitly acquiring device identities. This departure from established schemes is crucial for eliminating a reliance on individualized feedback, which has enabled fast connections in the past but would now become cost-prohibitive as a mechanism for machine-type traffic.

Likely outcomes for this project include near-optimum, low-complexity schemes for the next-generation of random access wireless systems, which will be broadly applicable to deal with inference in exceedingly large dimensions.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.