权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

CRII：CIF：通过稀疏图代码在物联网中进行邻居发现的下一代组测试

基本信息

批准号：
1755808
负责人：
Ramtin Pedarsani
金额：
$ 17.49万
依托单位：
University of California-Santa Barbara
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2018
资助国家：
美国
起止时间：
2018-04-01 至 2020-03-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1755808&HistoricalAwards=false
关键词：
CRII CIF Next Generation Group

项目摘要

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.

分组测试是一个基本的推理问题，其目的是通过分组测试从一个较大的项目集合中检测出一组有缺陷的项目。分组测试在不同的领域有着广泛的应用，包括通信、计算机科学、机器学习、生物学和信号处理。组测试的主要挑战是设计少量的测试，使得有缺陷的项目可以可靠地恢复，并使用低复杂度的解码算法来有效地恢复有缺陷的项目。该项目的目标是通过开发快速和接近最佳的组测试方案来解决这两个挑战。该项目关注的应用领域是物联网（IoT）中的主动邻居发现。在物联网环境中，有大量的低能耗设备可以收集和传输信息。在这样的系统中的主要挑战是使大量的设备能够通过可扩展的和低复杂度的随机接入方案进行通信。本研究的核心思想是从编码理论的透镜来看待组测试问题，以开发具有接近最优样本复杂度（测试次数）和最优解码复杂度的恢复算法。这种编码理论方法的主要成分是：（i）设计基于稀疏图代码的测试;（ii）开发一种快速的基于剥离的解码器，具有次线性计算复杂度，用于检测缺陷项;以及（ii）利用现代编码理论的强大工具，如密度进化，以最大限度地减少算法的样本复杂度。作为一个具体的应用，通过解决规模的基本挑战，在理论的组测试，拟议的工作旨在开发大规模的通信系统的主动用户检测方案。这个奖项反映了NSF的法定使命，并已被认为是值得通过评估使用基金会的智力价值和更广泛的影响审查标准的支持。