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


Personal Author(s) : Lynch,Nancy

Full Text :

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