Growing interest in sensor networks and other wireless communication network infrastructure for a host of applications presents important engineering challenges. In particular, there is a need to deliver data quickly and reliably in harsh environments, using often very scarce energy and bandwidth resources. Compared with traditional networks, a distinguishing feature of communication in many emerging applications is the inherent sparseness of communication---that is,communication between participating nodes is highly intermittent. For example, a sensor node may send a few hundred bits of information every few days. In such cases, there is not only uncertainty due to noise to contend with, but timing uncertainty as well. Such transmission profiles create unique challenges, due to the requirement to synchronize with the receiver each time. As a result, for short transmissions, traditional synchronization approaches can consume a disproportionate share of the available resources.
This research develops and analyzes models for asynchronous communication suitable for such applications, starting with basic single-user channels and proceeding to broader multiuser and network scenarios. The investigation studies fundamental limits and trade-offs associated with such models, and pursues architectures,protocols, and practical codes for resource-efficient communication in such settings. Because such models explicitly incorporate the lack of prior synchronization in the communication, the associated coding schemes of interest ensure reliable communication in the presence of such timing uncertainty. The research uses such models to assess the relative value of different candidate sparse communication architectures, including quantifying the inefficiency of traditional architectures in which synchronization and communication subsystems are separate, over an approach in which synchronization and communication are combined.
This project was broadly aimed at developing technology to better enable people to connect and interact with each other, and to share experiences. It's results provide system desigers and architects with important tools, insights, perspectives to guide them in developing emerging technologies including the Internet of Things, cloud computing and storage infrastructure, and recommender systems in social networking applications. The focus of the project is on exploiting inherent intermittency and sparseness structure in the underlying data involved. Our key results include the following. 1) For sensing and related systems where communication is intermittent, we show that the traditional transmission format whereby one first transmits a synchronization sequence before sending the data of interest is inherently inefficient. We show that synchronization and data payload functionality should be combined to achieve ultimate performance limits. 2) For distributed storage and computing environments, we show it is possible to design data representations (encodings) with "sparse encodings" Specifically, this means that small changes in the data need incur only small portions of the encoding (update efficiency), and that small losses in the encoding can be recovered from small portions of the remaining encoding (repair efficiency). Our results establish the fundamental limits of such locality. 3) For ranking and recommender systems, where the underlying data is inherently "sparse", we develop efficient approximate algorithms for efficiently compressing and sorting such data, which we show approach fundamental performance limits. The results of this research have helped generate significant additional interest within the broader research community, resulting in a substantial growth of activity in these areas. Moreover, through this research, numerous students were trained in an enriching, supportive, and collaborative environment to carry out advanced research at the forefront of science and engineering. Alumni from this project have gone on to carry out important multidisciplinary research in industry, government, and academia.
