A Comprehensive Theory of Algorithms for Wireless Networks and Mobile Systems
Abstract
This project has produced many new algorithms and some lower-bound results for ad hoc wireless network models, and has also developed abstraction layers that are intended to make it easier to algorithms and applications for wireless networks. Since some of the results can be expressed in terms of abstract graph networks, the project has also produced many new graph network algorithms. Other results involve distributed data management and biology-inspired distributed algorithms. More specifically, the project has produced efficient algorithms for both reliable and unreliable radio network wireless platform models, for the rudimentary Beeping model, and for the Signal-to-Noise-and-Interference (SINR) model. These algorithms have solved such problems as local and global broadcast, computing a Maximal Independent Set, and establishing other network structures. The project has developed an Abstract MAC (Local Broadcast) abstraction layer, with efficient implementations over several different wireless platform models, based on reasonable constraints on network geometry. The project has also produced new graph network algorithms for graph connectivity problems, distance computations, coloring, Maximal Independent Set, and various forms of spanning trees. Finally, it has produced an interesting method for running several distributed algorithms concurrently, in the same graph-based network. This work has resulted in six Best Paper and Best Student Paper awards.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 08, 2016
- Accession Number
- AD1011167
Entities
People
- Nancy Lynch
Organizations
- Massachusetts Institute of Technology