Efficient -shot broadcasting in radio networks

详细信息    查看全文

• 作者：Erez Kantor^a ; ^{erezk@csail.mit.edu" class="auth_mail" title="E-mail the corresponding author} ; David Peleg^b ; ^{david.peleg@weizmann.ac.il" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Wireless network ; Radio network ; Broadcasting
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：31 March 2016
• 年：2016
• 卷：202
• 期：Complete
• 页码：79-94
• 全文大小：760 K

文摘

The paper concerns time-efficient 53118953634d66" title="Click to view the MathML source">k$k$-shot broadcasting in undirected radio networks for n$n$-node graphs of diameter D$D$. In a 53118953634d66" title="Click to view the MathML source">k$k$-shot   broadcasting algorithm, each node in the network is allowed to transmit at most 53118953634d66" title="Click to view the MathML source">k$k$ times. Both known and unknown topology models are considered. For the known topology model, the problem has been studied before by Ga̧sieniec et al. (2008).

We improve both the upper and the lower bound of that paper providing a randomized algorithm for constructing a 53118953634d66" title="Click to view the MathML source">k$k$-shot broadcasting schedule of length D+O(kn^1/2klog^2+1/kn)$D+O\left(k{n}^{1/2k}{log}^{2+1/k}n\right)$ on undirected graphs, and a lower bound of D+Ω(k⋅(n−D)^1/2k)$D+\Omega (k\cdot {(n-D)}^{1/2k})$, which almost closes the gap between these bounds. For the unknown topology model, we provide the first 53118953634d66" title="Click to view the MathML source">k$k$-shot broadcasting algorithm.

Assuming that each node knows only the network size n$n$ (or a linear upper bound on it), our randomized 53118953634d66" title="Click to view the MathML source">k$k$-shot broadcasting algorithm completes broadcasting in O((D+min{D⋅k,logn})⋅n^1/(k−1)logn)$O((D+min\{D\cdot k,logn\})\cdot n^{1/(k-1)}logn)$ rounds with high probability for k≥2$k\ge 2$, and in O(D⋅n²logn)$O(D\cdot n^{2}logn)$ rounds with high probability for k=1$k=1$. Moreover, we present an Θ(logn)$\Theta (logn)$-shot broadcasting algorithm that completes broadcasting in at most O(Dlogn+log²n)$O(Dlogn+{log}^{2}n)$ rounds with high probability. This algorithm matches the broadcasting time of the algorithm of Bar-Yehuda et al. (1992), which assumes no limitation on the maximum number of transmissions per node.