Bounds on contention management in radio networks
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2013.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2013
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/79227 |
| _version_ | 1826208971740938240 |
|---|---|
| author | Ghaffari, Mohsen |
| author2 | Nancy Lynch. |
| author_facet | Nancy Lynch. Ghaffari, Mohsen |
| author_sort | Ghaffari, Mohsen |
| collection | MIT |
| description | Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2013. |
| first_indexed | 2024-09-23T14:15:40Z |
| format | Thesis |
| id | mit-1721.1/79227 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T14:15:40Z |
| publishDate | 2013 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/792272019-04-11T11:04:45Z Bounds on contention management in radio networks Ghaffari, Mohsen Nancy Lynch. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2013. Cataloged from PDF version of thesis. Includes bibliographical references (p. 79-82). In this thesis, we study the local broadcast problem in two well-studied wireless network models. The local broadcast problem is a theoretical approach for capturing the contention management issue in wireless networks; it assumes that processes are provided messages, one by one, that must be delivered to their neighbors. We study this problem in two theoretical models of wireless networks, the classical radio network model and its more recent generalization, the dual graph model which includes the possibility of unreliable time-changing links. Both these models are synchronous; the execution proceeds in lock-step rounds and in each round, each node either transmits a message or listens. In each round of the dual graph model, each unreliable link might be active or inactive, whereas in the classical model, all the links are always active. In each round, each node receives a message if and only if it is listening and exactly one of its neighbors, with respect to the the active links of that round, transmits. The time complexity of the local broadcast algorithms is measured by two bounds, the acknowledgment bound and the progress bound. Roughly speaking, the former bounds the time it takes each broadcasting node to deliver its message to all its neighbors and the latter bounds the time it takes a node to receive at least one message, assuming it has a broadcasting neighbor. Typically these bounds depend on the maximum contention and the network size. The standard local broadcast strategy is the Decay protocol introduced by Bar-Yehuda et al. [19] in 1987. During the 25-years period in which this strategy has been used, it has remained an open question whether it is optimal. In this paper, we resolve this long-standing question. We present lower bounds on progress and acknowledgment bounds in both the classical and the dual graph model and we show that, with a slight optimization, the Decay protocol matches these lower bounds in both models. However, the tight progress bound of the dual graph model is exponentially larger than the progress bound in the classical model, in its dependence on the maximum contention. This establishes a separation between the two models, proving that progress in the dual graph model is strictly and exponentially harder than its classical predecessor. Combined, our results provide an essentially complete characterization of the local broadcast problem in these two important models. by Mohsen Ghaffari. S.M. 2013-06-17T19:49:06Z 2013-06-17T19:49:06Z 2013 2013 Thesis http://hdl.handle.net/1721.1/79227 844771862 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 82 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Ghaffari, Mohsen Bounds on contention management in radio networks |
| title | Bounds on contention management in radio networks |
| title_full | Bounds on contention management in radio networks |
| title_fullStr | Bounds on contention management in radio networks |
| title_full_unstemmed | Bounds on contention management in radio networks |
| title_short | Bounds on contention management in radio networks |
| title_sort | bounds on contention management in radio networks |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/79227 |
| work_keys_str_mv | AT ghaffarimohsen boundsoncontentionmanagementinradionetworks |