Bounded information dissemination in multi-channel wireless networks

Yu Yan (), Dongxiao Yu (), Yuexuan Wang (), Jiguo Yu () and Francis C. M. Lau ()
Additional contact information
Yu Yan: Tsinghua University
Dongxiao Yu: The University of Hong Kong
Yuexuan Wang: 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 3, No 4, 996-1012

Abstract: Abstract More and more wireless networks and devices now operate on multiple channels, which poses the question: How to use multiple channels to speed up communication? In this paper, we answer this question for the case of wireless ad-hoc networks where information dissemination is a primitive operation. Specifically, we propose a randomized distributed algorithm for information dissemination that is very near the optimal. The general information dissemination problem is to deliver $$k$$ k information packets, stored initially in $$k$$ k different nodes (the packet holders), to all the nodes in the network, and the objective is to minimize the time needed. With an eye toward the reality, we assume a model where the packet holders are determined by an adversary, and neither the number $$k$$ k nor the identities of packet holders are known to the nodes in advance. Not knowing the value of $$k$$ k sets this problem apart from broadcasting and all-to-all communication (gossiping). We study the information dissemination problem in single-hop networks with bounded-size messages. We present a randomized algorithm which can disseminate all packets in $$O(k(\frac{1}{\mathcal {F}}+\frac{1}{\mathcal {P}})+\log ^2n)$$ O ( k ( 1 F + 1 P ) + log 2 n ) rounds with high probability, where $$\mathcal {F}$$ F is the number of available channels and $$\mathcal {P}$$ P is the bound on the number of packets a message can carry. Compared with the lower bound $$\varOmega (k(\frac{1}{\mathcal {F}}+\frac{1}{\mathcal {P}}))$$ Ω ( k ( 1 F + 1 P ) ) , the given algorithm is very close to the asymptotical optimal except for an additive factor. Our result provides the first solid evidence that multiple channels can indeed substantially speed up information dissemination, which also breaks the $$\varOmega (k)$$ Ω ( k ) lower bound that holds for single-channel networks (even if $$\mathcal {P}$$ P is infinity).

Keywords: Information dissemination; Multi-channel wireless network; Distributed algorithm; Randomized algorithm (search for similar items in EconPapers)
Date: 2016
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-014-9804-3 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:3:d:10.1007_s10878-014-9804-3

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

DOI: 10.1007/s10878-014-9804-3

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 ().