Randomized broadcast in radio networks with collision detection
详细信息 查看全文
- 作者：Mohsen Ghaffari ; Bernhard Haeupler ; Majid Khabbazian
- 关键词：Wireless networks ; Radio networks ; Broadcast ; Collision detection ; Random linear network coding
- 刊名：Distributed Computing
- 出版年：2015
- 出版时间：December 2015
- 年：2015
- 卷：28
- 期：6
- 页码：407-422
- 全文大小：883 KB
- 参考文献：1.Alon, N., Bar-Noy, A., Linial, N., Peleg, D.: A lower bound for radio broadcast. J. Comput. Syst. Sci. 43(2), 290-98 (1991)MATH MathSciNet CrossRef
2.Alon, N., Ghaffari, M., Haeupler, B., Khabbazian, M.: Broadcast throughput in radio networks: routing vs. network coding. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pp. 1831-843 (2014)
3.Bar-Yehuda, R., Goldreich, O., Itai, A.: On the time-complexity of broadcast in multi-hop radio networks: an exponential gap between determinism and randomization. J. Comput. Syst. Sci. 45(1), 104-26 (1992)
4.Bar-Yehuda, R., Israeli, A., Itai, A.: Multiple communication in multi-hop radio networks. SIAM J. Comput. 22(4), 875-87 (1993)MATH MathSciNet CrossRef
5.Chlamtac, I., Kutten, S.: On broadcasting in radio networks: problem analysis and protocol design. IEEE Trans. Commun. 33(12), 1240-246 (1985)MATH CrossRef
6.Chlebus, B., Kowalski, D., Pelc, A., Rokicki, M.A.: Efficient distributed communication in ad-hoc radio networks. In: Proceedings of the International Conference on Automata, Languages and Programming, pp. 613-24 (2011)
7.Czumaj, A., Rytter, W.: Broadcasting algorithms in radio networks with unknown topology. In: Proceedings of the Symposium on Foundations of Computer Science, pp. 492-01 (2003)
8.Gasieniec, L., Peleg, D., Xin, Q.: Faster communication in known topology radio networks. In: Proceedings of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pp. 129-37 (2005)
9.Gasieniec, L., Potapov, I.: Gossiping with unit messages in known radio networks. In: IFIP TCS, pp. 193-05 (2002)
10.Ghaffari, M., Haeupler, B.: Fast structuring of radio networks for multi-message communications. In: Proceedings of the International Symposium on Distributed Computing (2013)
11.Ghaffari, M., Haeupler, B.: Near optimal leader election in multi-hop radio networks. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pp. 748-66 (2013)
12.Haeupler, B.: Analyzing network coding gossip made easy. In: Proceedings of the Symposium on Theory of Computing, STOC-1, pp. 293-02 (2011)
13.Haeupler, B., Kim, M., Medard, M.: Optimality of network coding with buffers. In: Proceedings of the IEEE Information Theory Workshop, pp. 533-37 (2011)
14.Ho, T., Koetter, R., Medard, M., Karger, D., Effros, M.: The benefits of coding over routing in a randomized setting. In: Proceedings of the IEEE International Symposium on Information Theory (2003)
15.Khabbazian, M., Kowalski, D.: Time-efficient randomized multiple-message broadcast in radio networks. In: Proceedings of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pp. 373-80 (2011)
16.Kowalski, D., Pelc, A.: Broadcasting in undirected ad hoc radio networks. In: Proceedings of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pp. 73-2 (2003)
17.Kowalski, D., Pelc, A.: Optimal deterministic broadcasting in known topology radio networks. Distrib. Comput. 19(3), 185-95 (2007)CrossRef
18.Kushilevitz, E., Mansour, Y.: An \({\Omega }(D\log (N/D))\) lower bound for broadcast in radio networks. In: Proceedings of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pp. 65-4 (1993)
19.Manne, F., Xin, Q.: Optimal gossiping with unit size messages in known topology radio networks. In: Proceedings of the Workshop on Combinatorial and Algorithmic Aspects of Networking, pp. 125-34 (2006)
20.Peleg, D.: Time-efficient broadcasting in radio networks: a review. In: Proceedings of the International Conference on Distributed Computing and Internet Technologies, pp. 1-8 (2007)
21.Schneider, J., Wattenhofer, R.: What is the use of collision detection (in wireless networks)?. In: Proceedings of the 24th International Conference on Distributed Computing, pp. 133-47 (2010)
22.Xin, Q.: Personal communication (2012) - 作者单位：Mohsen Ghaffari (1)
Bernhard Haeupler (2)
Majid Khabbazian (3)
1. Massachusetts Institute of Technology, Cambridge, MA, USA
2. Carnegie Mellon University, Pittsburgh, PA, USA
3. University of Alberta, Edmonton, Canada - 刊物类别：Computer Science
- 刊物主题：Computer Communication Networks
Computer Hardware
Computer Systems Organization and Communication Networks
Software Engineering, Programming and Operating Systems
Theory of Computation - 出版者：Springer Berlin / Heidelberg
- ISSN：1432-0452
文摘
We present a randomized distributed algorithm that in radio networks with collision detection broadcasts a single message in \(O(D + \log ^6 n)\) rounds, with high probability. This time complexity is most interesting because of its optimal additive dependence on the network diameter \(D\). It improves over the currently best known \(O(D\log \frac{n}{D}\,+\,\log ^2 n)\) algorithms, due to Czumaj and Rytter (Broadcasting algorithms in radio networks with unknown topology. In: Proceedings of the symposium on foundations of computer science, pp 492-01, 2003), and Kowalski and Pelc (Broadcasting in undirected ad hoc radio networks. In: Proceedings of the ACM SIGACT-SIGOPS symposium on principles of distributed computing, pp 73-2, 2003). These algorithms where designed for the model without collision detection and are optimal in that model. However, as explicitly stated by Peleg in his 2007 survey on broadcast in radio networks, it had remained an open question whether the bound can be improved with collision detection. We also study distributed algorithms for broadcasting \(k\) messages from a single source to all nodes. This problem is a natural and important generalization of the single-message broadcast problem, but is in fact considerably more challenging and less understood. We show the following results: If the network topology is known to all nodes, then a \(k\)-message broadcast can be performed in \(O(D + k\log n + \log ^2 n)\) rounds, with high probability. If the topology is not known, but collision detection is available, then a \(k\)-message broadcast can be performed in \(O(D + k\log n + \log ^6 n)\) rounds, with high probability. The first bound is optimal and the second is optimal modulo the additive \(O(\log ^6 n)\) term. Keywords Wireless networks Radio networks Broadcast Collision detection Random linear network coding