The loudest one wins : efficient communication in theoretical wireless networks

In order to develop the most efficient algorithms for wireless networks, first one must understand their theoretical limitations. To this end, we study the leader election and broadcast problems in wireless networks, modeling them using the Signal-to- Interference-plus-Noise-Ratio (SINR) model. Our main result is an algorithm that solves the leader election problem in two communication rounds using power control, with high probability. Previously, it was known that [Omega](log n) rounds were sufficient and necessary when using uniform power, where n is the number of nodes in the network. We explore tradeoffs between communication complexity and power used, and show that to elect a leader in t rounds, a power range exp (n (1 [Theta] T) is sufficient and necessary. In addition, we present an efficient algorithm for the broadcast problem. Using power control, it is possible to achieve a broadcast algorithm that terminates successfully in 2n rounds, w.h.p..

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2018

Author dc:creator

• Markatou, Evangelia Anna

Advisor dc:contributor.advisor

• Nancy Lynch.

• Electrical Engineering and Computer Science.

Statement dc:rights

• MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/119737

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/119737