CRII: CIF: Next-Generation Group Testing for Neighbor Discovery in the IoT via Sparse-Graph Codes

University Of California-Santa Barbara, Santa Barbara CA

Investigators

Abstract

Group testing is a fundamental inference problem that aims to detect a set of defective items from a larger set of items via group tests. Group testing has a variety of applications in different fields including communications, computer science, machine learning, biology, and signal processing. The main challenges in group testing are to design a small number of tests such that the defective items can be reliably recovered, and to efficiently recover the defective items using a low-complexity decoding algorithm. The goal of this project is to address both challenges by developing fast and near-optimal group testing schemes. The application area that the project focuses on is active neighbor discovery in the Internet of Things (IoT). In an IoT setting, there is an abundance of low-energy devices that collect and transmit information. The main challenge in such systems is to enable a massive number of devices to communicate via a scalable and low-complexity random access scheme. This project addresses this challenge by designing large-scale active neighbor discovery protocols based on group testing. The key idea of this research is to view the group testing problem from a coding-theoretic lens to develop recovery algorithms with near-optimal sample complexity (number of tests) and optimal decoding complexity. The main ingredients of this coding-theoretic approach are to: (i) design the tests based on a sparse-graph code; (ii) develop a fast peeling-based decoder with sublinear computational complexity for detecting the defective items; and (ii) leverage powerful tools from modern coding theory such as density evolution to minimize the sample complexity of the algorithm. As a concrete application, by addressing the fundamental challenge of scale in the theory of group testing, the proposed work aims to develop active user detection schemes for large-scale communication systems. 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.