A Local Broadcast Layer for the SINR Network Model
We present the first algorithm that implements an abstract MAC (absMAC) layer in the Signal-to-Interference-plus-Noise-Ratio (SINR) wireless network model. We first prove that efficient SINR implementations are not possible for the standard absMAC specification. We modify that specification to an &q...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery (ACM)
2016
|
| Online Access: | http://hdl.handle.net/1721.1/100842 https://orcid.org/0000-0003-3045-265X https://orcid.org/0000-0002-4004-605X |
| _version_ | 1826211312028352512 |
|---|---|
| author | Halldorsson, Magnus M. Holzer, Stephan Sebastian Lynch, Nancy Ann |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Halldorsson, Magnus M. Holzer, Stephan Sebastian Lynch, Nancy Ann |
| author_sort | Halldorsson, Magnus M. |
| collection | MIT |
| description | We present the first algorithm that implements an abstract MAC (absMAC) layer in the Signal-to-Interference-plus-Noise-Ratio (SINR) wireless network model. We first prove that efficient SINR implementations are not possible for the standard absMAC specification. We modify that specification to an "approximate" version that better suits the SINR model. We give an efficient algorithm to implement the modified specification, and use it to derive efficient algorithms for higher-level problems of global broadcast and consensus.
In particular, we show that the absMAC progress property has no efficient implementation in terms of the SINR strong connectivity graph G[subscript 1-ε], which contains edges between nodes of distance at most (1-ε) times the transmission range, where ε>0 is a small constant that can be chosen by the user. This progress property bounds the time until a node is guaranteed to receive some message when at least one of its neighbors is transmitting. To overcome this limitation, we introduce the slightly weaker notion of approximate progress into the absMAC specification. We provide a fast implementation of the modified specification, based on decomposing the algorithm of [10] into local and global parts. We analyze our algorithm in terms of local parameters such as node degrees, rather than global parameters such as the overall number of nodes. A key contribution is our demonstration that such a local analysis is possible even in the presence of global interference.
Our absMAC algorithm leads to several new, efficient algorithms for solving higher-level problems in the SINR model. Namely, by combining our algorithm with high-level algorithms from [26], we obtain an improved (compared to [10]) algorithm for global single-message broadcast in the SINR model, and the first efficient algorithm for multi-message broadcast in that model. We also derive the first efficient algorithm for network-wide consensus, using a result of [32]. This work demonstrates that one can develop efficient algorithms for solving high-level problems in the SINR model, using graph-based algorithms over a local broadcast abstraction layer that hides the technicalities of the SINR platform such as global interference. Our algorithms do not require bounds on the network size, nor the ability to measure signal strength, nor carrier sensing, nor synchronous wakeup. |
| first_indexed | 2024-09-23T15:03:55Z |
| format | Article |
| id | mit-1721.1/100842 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:03:55Z |
| publishDate | 2016 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/1008422022-09-29T12:26:58Z A Local Broadcast Layer for the SINR Network Model Halldorsson, Magnus M. Holzer, Stephan Sebastian Lynch, Nancy Ann Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Halldorsson, Magnus M. Holzer, Stephan Sebastian Lynch, Nancy Ann We present the first algorithm that implements an abstract MAC (absMAC) layer in the Signal-to-Interference-plus-Noise-Ratio (SINR) wireless network model. We first prove that efficient SINR implementations are not possible for the standard absMAC specification. We modify that specification to an "approximate" version that better suits the SINR model. We give an efficient algorithm to implement the modified specification, and use it to derive efficient algorithms for higher-level problems of global broadcast and consensus. In particular, we show that the absMAC progress property has no efficient implementation in terms of the SINR strong connectivity graph G[subscript 1-ε], which contains edges between nodes of distance at most (1-ε) times the transmission range, where ε>0 is a small constant that can be chosen by the user. This progress property bounds the time until a node is guaranteed to receive some message when at least one of its neighbors is transmitting. To overcome this limitation, we introduce the slightly weaker notion of approximate progress into the absMAC specification. We provide a fast implementation of the modified specification, based on decomposing the algorithm of [10] into local and global parts. We analyze our algorithm in terms of local parameters such as node degrees, rather than global parameters such as the overall number of nodes. A key contribution is our demonstration that such a local analysis is possible even in the presence of global interference. Our absMAC algorithm leads to several new, efficient algorithms for solving higher-level problems in the SINR model. Namely, by combining our algorithm with high-level algorithms from [26], we obtain an improved (compared to [10]) algorithm for global single-message broadcast in the SINR model, and the first efficient algorithm for multi-message broadcast in that model. We also derive the first efficient algorithm for network-wide consensus, using a result of [32]. This work demonstrates that one can develop efficient algorithms for solving high-level problems in the SINR model, using graph-based algorithms over a local broadcast abstraction layer that hides the technicalities of the SINR platform such as global interference. Our algorithms do not require bounds on the network size, nor the ability to measure signal strength, nor carrier sensing, nor synchronous wakeup. United States. Air Force Office of Scientific Research (Contract FA9550-13-1-0042) National Science Foundation (U.S.) (Award 0939370-CCF) National Science Foundation (U.S.) (Award CCF-1217506) National Science Foundation (U.S.) (Award CCF-AF-0937274) 2016-01-15T01:21:15Z 2016-01-15T01:21:15Z 2015-07 Article http://purl.org/eprint/type/ConferencePaper 9781450336178 http://hdl.handle.net/1721.1/100842 Magnus M. Halldorsson, Stephan Holzer, and Nancy Lynch. 2015. A Local Broadcast Layer for the SINR Network Model. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC '15). ACM, New York, NY, USA, 129-138. https://orcid.org/0000-0003-3045-265X https://orcid.org/0000-0002-4004-605X en_US http://dx.doi.org/10.1145/2767386.2767432 Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC '15) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) MIT web domain |
| spellingShingle | Halldorsson, Magnus M. Holzer, Stephan Sebastian Lynch, Nancy Ann A Local Broadcast Layer for the SINR Network Model |
| title | A Local Broadcast Layer for the SINR Network Model |
| title_full | A Local Broadcast Layer for the SINR Network Model |
| title_fullStr | A Local Broadcast Layer for the SINR Network Model |
| title_full_unstemmed | A Local Broadcast Layer for the SINR Network Model |
| title_short | A Local Broadcast Layer for the SINR Network Model |
| title_sort | local broadcast layer for the sinr network model |
| url | http://hdl.handle.net/1721.1/100842 https://orcid.org/0000-0003-3045-265X https://orcid.org/0000-0002-4004-605X |
| work_keys_str_mv | AT halldorssonmagnusm alocalbroadcastlayerforthesinrnetworkmodel AT holzerstephansebastian alocalbroadcastlayerforthesinrnetworkmodel AT lynchnancyann alocalbroadcastlayerforthesinrnetworkmodel AT halldorssonmagnusm localbroadcastlayerforthesinrnetworkmodel AT holzerstephansebastian localbroadcastlayerforthesinrnetworkmodel AT lynchnancyann localbroadcastlayerforthesinrnetworkmodel |