File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1109/INFOCOM.2016.7524605
- Scopus: eid_2-s2.0-84983340018
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Inductive coloring: implementing basic communication primitives with Rayleigh-fading interference
Title | Inductive coloring: implementing basic communication primitives with Rayleigh-fading interference |
---|---|
Authors | |
Issue Date | 2016 |
Publisher | IEEE. |
Citation | The 35th Annual IEEE International Conference on Computer Communications (IEEE INFOCOM 2016), San Francisco, CA., 10-14 April 2016. In Conference Proceedings, 2016, p. 1-9 How to Cite? |
Abstract | We study distributed algorithms for achieving efficient communications in the Rayleigh-fading Model. This model extends the popular deterministic SINR model using stochastic propagation to address fading effects observed in reality. Stochastic propagation greatly increases the difficulty of dealing with interference and collisions, especially in a local context without much global knowledge. We present a new technique called Inductive Coloring that can be used to schedule fast transmissions with Rayleigh-fading interference. The computation of inductive coloring takes only O(log2n) time with the proposed distributed algorithm, where n is the number of nodes in the network. We illustrate the power of inductive coloring by giving algorithms for implementing two basic communication primitives. The first primitive is Local Broadcast (LB), which can work in a MAC layer and has been widely studied in different interference models. The proposed algorithm for LB matches the fastest one under the simpler SINR model. The second primitive is Single-Reception (SR), which is to make each node receive at least one message from its neighbors. The proposed algorithm can implement SR in O(log2 n) rounds. To illustrate the versatility of the SR primitive, we use the primitive to derive efficient algorithms for information broadcast and function computations. We conduct simulations to verify all the proposed algorithms, and the results show that the algorithms also perform well in realistic environments. |
Persistent Identifier | http://hdl.handle.net/10722/229705 |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Wang, Y | - |
dc.contributor.author | Yu, D | - |
dc.contributor.author | Liu, Q | - |
dc.contributor.author | Lau, FCM | - |
dc.date.accessioned | 2016-08-23T14:12:47Z | - |
dc.date.available | 2016-08-23T14:12:47Z | - |
dc.date.issued | 2016 | - |
dc.identifier.citation | The 35th Annual IEEE International Conference on Computer Communications (IEEE INFOCOM 2016), San Francisco, CA., 10-14 April 2016. In Conference Proceedings, 2016, p. 1-9 | - |
dc.identifier.uri | http://hdl.handle.net/10722/229705 | - |
dc.description.abstract | We study distributed algorithms for achieving efficient communications in the Rayleigh-fading Model. This model extends the popular deterministic SINR model using stochastic propagation to address fading effects observed in reality. Stochastic propagation greatly increases the difficulty of dealing with interference and collisions, especially in a local context without much global knowledge. We present a new technique called Inductive Coloring that can be used to schedule fast transmissions with Rayleigh-fading interference. The computation of inductive coloring takes only O(log2n) time with the proposed distributed algorithm, where n is the number of nodes in the network. We illustrate the power of inductive coloring by giving algorithms for implementing two basic communication primitives. The first primitive is Local Broadcast (LB), which can work in a MAC layer and has been widely studied in different interference models. The proposed algorithm for LB matches the fastest one under the simpler SINR model. The second primitive is Single-Reception (SR), which is to make each node receive at least one message from its neighbors. The proposed algorithm can implement SR in O(log2 n) rounds. To illustrate the versatility of the SR primitive, we use the primitive to derive efficient algorithms for information broadcast and function computations. We conduct simulations to verify all the proposed algorithms, and the results show that the algorithms also perform well in realistic environments. | - |
dc.language | eng | - |
dc.publisher | IEEE. | - |
dc.relation.ispartof | IEEE International Conference on Computer Communications, IEEE INFOCOM 2016 Proceedings | - |
dc.rights | IEEE International Conference on Computer Communications, IEEE INFOCOM 2016 Proceedings. Copyright © IEEE. | - |
dc.rights | ©2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. | - |
dc.title | Inductive coloring: implementing basic communication primitives with Rayleigh-fading interference | - |
dc.type | Conference_Paper | - |
dc.identifier.email | Wang, Y: amywang@hku.hk | - |
dc.identifier.email | Yu, D: mxyu@hku.hk | - |
dc.identifier.email | Lau, FCM: fcmlau@cs.hku.hk | - |
dc.identifier.authority | Lau, FCM=rp00221 | - |
dc.identifier.doi | 10.1109/INFOCOM.2016.7524605 | - |
dc.identifier.scopus | eid_2-s2.0-84983340018 | - |
dc.identifier.hkuros | 260201 | - |
dc.identifier.spage | 1 | - |
dc.identifier.epage | 9 | - |
dc.publisher.place | United States | - |
dc.customcontrol.immutable | sml 160901 | - |