File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Inductive coloring: implementing basic communication primitives with Rayleigh-fading interference

TitleInductive coloring: implementing basic communication primitives with Rayleigh-fading interference
Authors
Issue Date2016
PublisherIEEE.
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?
AbstractWe 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 Identifierhttp://hdl.handle.net/10722/229705

 

DC FieldValueLanguage
dc.contributor.authorWang, Y-
dc.contributor.authorYu, D-
dc.contributor.authorLiu, Q-
dc.contributor.authorLau, FCM-
dc.date.accessioned2016-08-23T14:12:47Z-
dc.date.available2016-08-23T14:12:47Z-
dc.date.issued2016-
dc.identifier.citationThe 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.urihttp://hdl.handle.net/10722/229705-
dc.description.abstractWe 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.languageeng-
dc.publisherIEEE.-
dc.relation.ispartofIEEE International Conference on Computer Communications, IEEE INFOCOM 2016 Proceedings-
dc.rightsIEEE 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.titleInductive coloring: implementing basic communication primitives with Rayleigh-fading interference-
dc.typeConference_Paper-
dc.identifier.emailWang, Y: amywang@hku.hk-
dc.identifier.emailYu, D: mxyu@hku.hk-
dc.identifier.emailLau, FCM: fcmlau@cs.hku.hk-
dc.identifier.authorityLau, FCM=rp00221-
dc.identifier.doi10.1109/INFOCOM.2016.7524605-
dc.identifier.hkuros260201-
dc.identifier.spage1-
dc.identifier.epage9-
dc.publisher.placeUnited States-
dc.customcontrol.immutablesml 160901-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats