Accession Number : AD1011167


Title :   A Comprehensive Theory of Algorithms for Wireless Networks and Mobile Systems


Descriptive Note : Technical Report,01 Apr 2013,31 May 2016


Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE CAMBRIDGE United States


Personal Author(s) : Lynch,Nancy


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/1011167.pdf


Report Date : 08 Jun 2016


Pagination or Media Count : 27


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.


Descriptors :   wireless networks , algorithms , graph theory , data management , mobile communications


Subject Categories : Operations Research
      Radio Communications


Distribution Statement : APPROVED FOR PUBLIC RELEASE