Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Faster Information Gathering in Ad-Hoc Radio Tree Networks

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We study information gathering in ad-hoc radio networks. Initially, each node of the network has a piece of information called a rumor, and the overall objective is to gather all these rumors in the designated target node. The ad-hoc property refers to the fact that the topology of the network is unknown when the computation starts. Aggregation of rumors is not allowed, which means that each node may transmit at most one rumor in one step. We focus on networks with tree topologies, that is we assume that the network is a tree with all edges directed towards the root, but, being ad-hoc, its actual topology is not known. We provide two deterministic algorithms for this problem. For the model that does not assume any collision detection nor acknowledgement mechanisms, we give an \(O(n\log \log n)\)-time algorithm, improving the previous upper bound of \(O(n\log n)\). We then show that this running time can be reduced to O(n), which is asymptotically optimal, if the model allows for acknowledgements of successful transmissions.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

Notes

  1. These structures are also sometimes called strongly k -selective families in the literature.

  2. It needs to be emphasized here that in our model only communication steps contribute to the running time; all calculations are assumed to be instantaneous.

References

  1. Alon, N., Bar-Noy, A., Linial, N., Peleg, D.: A lower bound for radio broadcast. J. Comput. Syst. Sci. 43(2), 290–298 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  2. Anta, A.F., Mosteiro, M.A., Muoz, J.R.: Unbounded contention resolution in multiple-access channels. Algorithmica 67(3), 295–314 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  3. Bruschi, D., Del Pinto, M.: Lower bounds for the broadcast problem in mobile radio networks. Distrib. Comput. 10(3), 129–135 (1997)

    Article  Google Scholar 

  4. Chlebus, B.S., Kowalski, D.R., Pelc, A., Rokicki, M.A.: Efficient distributed communication in ad-hoc radio networks. In: Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP’11), pp. 613–624. (2011)

  5. Chlebus, B.S., Gasieniec, L., Gibbons, A., Pelc, A., Rytter, W.: Deterministic broadcasting in ad hoc radio networks. Distrib. Comput. 15(1), 27–38 (2002)

    Article  MATH  Google Scholar 

  6. Christersson, M., Gasieniec, L., Lingas, A.: Gossiping with bounded size messages in ad hoc radio networks. In: Proceedings of the 29th International Colloquium on Automata, Languages and Programming (ICALP), pp. 377–389. (2002)

  7. Chrobak, M., Costello, K., Gasieniec, L., Kowalski, D.R.: Information gathering in ad-hoc radio networks with tree topology. In: Proceedings of the 8th International Conference on Combinatorial Optimization and Applications (COCOA), pp. 129–145. (2014)

  8. Chrobak, M., Gasieniec, L., Rytter, W.: Fast broadcasting and gossiping in radio networks. J. Algorithms 43(2), 177–189 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  9. Chrobak, M., Gasieniec, L., Rytter, W.: A randomized algorithm for gossiping in radio networks. Networks 43(2), 119–124 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  10. Cicalese, F., Manne, F., Xin, Q.: Faster centralized communication in radio networks. In: Proceedings of 17th International Symposium on Algorithms and Computation (ISAAC’06), pp. 339–348. Springer, Berlin (2006)

  11. Clementi, A.E.F., Monti, A., Silvestri, R.: Selective families, superimposed codes, and broadcasting on unknown radio networks. In: Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 709–718. (2001)

  12. Clementi, A.E.F., Monti, A., Silvestri, R.: Distributed broadcast in radio networks of unknown topology. Theor. Comput. Sci. 302(1–3), 337–364 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  13. Czumaj, A., Davies, P.: Almost optimal deterministic broadcast in radio networks. In: Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP), (2016). To appear

  14. Czumaj, A., Rytter, W.: Broadcasting algorithms in radio networks with unknown topology. J. Algorithms 60(2), 115–143 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  15. De Marco, G.: Distributed broadcast in unknown radio networks. In: Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 208–217. (2008)

  16. De Marco, G., Kowalski, D.R.: Contention resolution in a non-synchronized multiple access channel. In: Proceedings of the 27th International Symposium on Parallel Distributed Processing (IPDPS), pp. 525–533. (2013)

  17. De Marco, G., Kowalski, D.R.: Fast nonadaptive deterministic algorithm for conflict resolution in a dynamic multiple-access channel. SIAM J. Comput. 44(3), 868–888 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  18. Erdös, P., Frankl, P., Füredi, Z.: Families of finite sets in which no set is covered by the union of \(r\) others. Israel J. Math. 51(1–2), 79–89 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  19. Gasieniec, L.: On efficient gossiping in radio networks. In: Proceedings of the 16th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 2–14. (2009)

  20. Gasieniec, L., Radzik, T., Xin, Q.: Faster deterministic gossiping in directed ad hoc radio networks. In: Proceedings of the 9th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), pp. 397–407. (2004)

  21. Kowalski, D.R.: On selection problem in radio networks. In: Proceedings of the 24th ACM Symposium on Principles of Distributed Computing (PODC), pp. 158–166. (2005)

  22. Kowalski, D.R., Pelc, A.: Faster deterministic broadcasting in ad hoc radio networks. SIAM J. Discrete Math. 18(2), 332–346 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  23. Kowalski, D.R., Pelc, A.: Leader election in ad hoc radio networks: a keen ear helps. In: Proceedings of the 36th Internatilonal Collogquium on Automata, Languages and Programming (ICALP’09), pp. 521–533. (2009)

  24. Kushilevitz, E., Mansour, Y.: An \(\Omega (D\log (N/D))\) lower bound for broadcast in radio networks. SIAM J. Comput. 27(3), 702–712 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  25. Liu, D., Prabhakaran, M.: On randomized broadcasting and gossiping in radio networks. In: Proceedings of the 8th International Computing and Combinatorics Conference (COCOON), pp. 340–349. (2002)

  26. Strahler, A.N.: Hypsometric (area-altitude) analysis of erosional topology. Geol. Soc. Am. Bull. 63, 1117–1142 (1952)

    Article  Google Scholar 

  27. Viennot, X.G.: A Strahler bijection between Dyck paths and planar trees. Discrete Math. 246, 317–329 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  28. Ying, Xu: An \(O(n^{1.5})\) deterministic gossiping algorithm for radio networks. Algorithmica 36(1), 93–96 (2003)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

We would like to thank the anonymous reviewers for multiple comments that helped us improve the paper and for pointing out several references relevant to this work.

Author information

Authors and Affiliations

  1. Department of Computer Science, University of California at Riverside, Riverside, CA, USA

    Marek Chrobak

  2. Department of Mathematics, University of California at Riverside, Riverside, CA, USA

    Kevin P. Costello

Authors
  1. Marek Chrobak
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Kevin P. Costello
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Marek Chrobak.

Additional information

Marek Chrobak was supported by NSF Grants CCF-1217314 and CCF-1536026. Kevin P. Costello was supported by NSA Grant H98230-13-1-0228.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Chrobak, M., Costello, K.P. Faster Information Gathering in Ad-Hoc Radio Tree Networks. Algorithmica 80, 1013–1040 (2018). https://doi.org/10.1007/s00453-017-0336-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-017-0336-y

Search

Navigation