Information exchange with collision detection on multiple channels

Yuepeng Wang (), Yuexuan Wang (), Dongxiao Yu (), Jiguo Yu () and Francis C. M. Lau ()
Additional contact information
Yuepeng Wang: University of Science and Technology of China
Yuexuan Wang: The University of Hong Kong
Dongxiao Yu: The University of Hong Kong
Jiguo Yu: Qufu Normal University
Francis C. M. Lau: The University of Hong Kong

Journal of Combinatorial Optimization, 2016, vol. 31, issue 1, No 10, 118-135

Abstract: Abstract Information exchange is a fundamental communication primitive in radio networks. We study this problem in multi-channel single-hop networks. In particular, given $$k$$ k pieces of information, initially stored in $$k$$ k nodes respectively, the task is to broadcast these information pieces to the entire network via a set of $$\mathcal {F}$$ F channels. We develop efficient distributed algorithms for this task for the scenario where both the identities and the number $$k$$ k of the initial information holders are unknown to the participating nodes. Assuming nodes with collision detection, we present an efficient randomized algorithm for unrestricted information exchange, where multiple information items can be combined into a single message. The algorithm disseminates all the information items within $$O(\frac{k}{\mathcal {F}}+\mathcal {F}\log ^2n)$$ O ( k F + F log 2 n ) timeslots with high probability. To the best of our knowledge, this is the first algorithm that breaks the $$\varOmega (k)$$ Ω ( k ) lower bound for unrestricted information exchange if only a single channel is available. This result establishes the superiority of multiple channels for the task of unrestricted information exchange. Moreover, for restricted information exchange, where each message can carry only one information item, we devise a randomized algorithm that completes the task in $$O(k+\frac{\log ^2n}{\mathcal {F}}+\log n)$$ O ( k + log 2 n F + log n ) timeslots. When $$k$$ k is large, both algorithms are asymptotically optimal, as they can reach the trivial lower bounds of $$\varOmega (\frac{k}{\mathcal {F}})$$ Ω ( k F ) and $$\varOmega (k)$$ Ω ( k ) for unrestricted and restricted information exchange, respectively.

Keywords: Wireless network; Multiple channels; Information exchange; Distributed algorithm; Randomized algorithm (search for similar items in EconPapers)
Date: 2016
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-014-9713-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:31:y:2016:i:1:d:10.1007_s10878-014-9713-5

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-014-9713-5

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().