Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 7355))
Included in the following conference series:
787Accesses
Abstract
In a multiple-message broadcast, an arbitrary number of messages originate at arbitrary nodes in the network at arbitrary times. The problem is to disseminate all these messages to the whole network. This paper gives the first randomized distributed multiple-message broadcast algorithm with worst-case performance guarantee in wireless ad-hoc networks employing the SINR interference model which takes interferences from all the nodes in the network into account. The network model used in this paper also considers the harsh characteristics of wireless ad-hoc networks: there is no prior structure, and nodes cannot perform collision detection and have little knowledge of the network topology. Under all these restrictions, our proposed randomized distributed multiple-message broadcast protocol can deliver any messagem to all nodes in the network inO(D + k + log2n) timeslots with high probability, whereD is the network diameter,k is the number of messages whose broadcasts overlap withm, andn is the number of nodes in the network. We also study the lower bound for randomized distributed multiple-message broadcast protocols. In particular, we prove that any uniform randomized algorithm needs\(\Omega(D+k+\frac{\log^2n}{\log\log\log n})\) timeslots to deliverk messages initially stored atk nodes to all nodes in the network.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 5719
- Price includes VAT (Japan)
- Softcover Book
- JPY 7149
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bar-Yehuda, R., Israeli, A., Itai, A.: Multiple communication in multi-hop radio networks. SIAM Journal on Computing 22, 875–887 (1993)
Censor-Hillel, K., Gilbert, S., Kuhn, F., Lynch, N.A., Newport, C.C.: Structuring unreliable radio networks. In: Proc. PODC (2011)
Chlebus, B., Gasieniec, L., Lingas, A., Pagourtzis, A.T.: Oblivious gossiping in ad-hoc radio networks. In: Proc. DIALM (2001)
Chlebus, B., Kowalski, D., Radzik, T.: Many-to-Many Communication in Radio Networks. Algorithmica 54(1), 118–139 (2009)
Goussevskaia, O., Moscibroda, T., Wattenhofer, R.: Local broadcasting in the physical interference model. In: Proc. DialM-POMC (2008)
Halldórsson, M.M., Mitra, P.: Optimal Bounds for Distributed Wireless Scheduling in the SINR Model. In: Proc. ICALP (2011)
Khabbazian, M., Kowalski, D.R.: Time-efficient randomized multiple-message broadcast in radio networks. In: Proc. PODC (2011)
Khabbazian, M., Kuhn, F., Kowalski, D.R., Lynch, N.A.: Decomposing broadcast algorithms using abstract MAC layers. In: Proc. DialM-POMC (2010)
Kuhn, F., Lynch, N.A., Newport, C.C.: The abstract MAC layer. Distributed Computing 24(3-4), 187–206 (2011)
Kushilevitz, E., Mansour, Y.: An Ω(Dlog(n/D)) lower bound for broadcast in radio networks. SIAM J. Comput. 27(3), 702–712 (1998)
Kesselheim, T., Vöcking, B.: Distributed Contention Resolution in Wireless Networks. In: Lynch, N.A., Shvartsman, A.A. (eds.) DISC 2010. LNCS, vol. 6343, pp. 163–178. Springer, Heidelberg (2010)
Li, H., Hua, Q.-S., Wu, C., Lau, F.C.M.: Minimum-latency aggregation scheduling in wireless sensor networks under physical interference model. In: Proc. MSWiM (2010)
Li, H., Hua, Q.-S., Wu, C., Lau, F.C.M.: Latency-Minimizing Data Aggregation in Wireless Sensor Networks under Physical Interference Model. Ad Hoc Networks (to appear)
Scheideler, C., Richa, A., Santi, P.: AnO(logn) dominating set protocol for wireless ad-hoc networks under the physical interference model. In: Proc. MOBIHOC (2008)
Woo, A., Culler, D.-E.: A transmission control scheme for media access in sensor networks. In: Proc. MOBICOM (2001)
Yu, D., Hua, Q.-S., Wang, Y., Lau, F.C.M.: AnO(logn) Distributed Approximation Algorithm for Local Broadcasting in Unstructured Wireless Networks. In: Proc. DCOSS (2012)
Yu, D., Hua, Q.-S., Wang, Y., Tan, H., Lau, F.C.M.: Distributed Multiple-Message Broadcast in Wireless Ad-Hoc Networks under the SINR Model,http://iiis.tsinghua.edu.cn/~qshua/sirocco12full.pdf
Yu, D., Wang, Y., Hua, Q.-S., Lau, F.C.M.: Distributed (Δ + 1)-Coloring in the Physical Model. In: Erlebach, T., Nikoletseas, S., Orponen, P. (eds.) ALGOSENSORS 2011. LNCS, vol. 7111, pp. 145–160. Springer, Heidelberg (2012)
Yu, D., Wang, Y., Hua, Q.-S., Lau, F.C.M.: Distributed local broadcasting algorithms in the physical interference model. In: Proc. DCOSS (2011)
Author information
Authors and Affiliations
Department of Computer Science, The University of Hong Kong, Pokfulam, Hong Kong, P.R. China
Dongxiao Yu & Francis C. M. Lau
Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, 100084, P.R. China
Qiang-Sheng Hua, Yuexuan Wang & Haisheng Tan
- Dongxiao Yu
You can also search for this author inPubMed Google Scholar
- Qiang-Sheng Hua
You can also search for this author inPubMed Google Scholar
- Yuexuan Wang
You can also search for this author inPubMed Google Scholar
- Haisheng Tan
You can also search for this author inPubMed Google Scholar
- Francis C. M. Lau
You can also search for this author inPubMed Google Scholar
Editor information
Editors and Affiliations
School of Electrical Engineering,, Tel-Aviv University, Ramat-Aviv, 69978, Tel Aviv, Israel
Guy Even
ICE-TCS School of Computer Science, Reykjavik University, 101, Reykjavik,, Iceland
Magnús M. Halldórsson
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Yu, D., Hua, QS., Wang, Y., Tan, H., Lau, F.C.M. (2012). Distributed Multiple-Message Broadcast in Wireless Ad-Hoc Networks under the SINR Model. In: Even, G., Halldórsson, M.M. (eds) Structural Information and Communication Complexity. SIROCCO 2012. Lecture Notes in Computer Science, vol 7355. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31104-8_10
Download citation
Publisher Name:Springer, Berlin, Heidelberg
Print ISBN:978-3-642-31103-1
Online ISBN:978-3-642-31104-8
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative