Technical Report CS0537

Title: Multiple Communication in Multi-Hop Radio Networks
Authors: R. Bar-Yehuda, A. Israeli, A. Itai
Abstract: Two tasks of communication in a multi-hop synchronous radio network are considered: point-topoint communication and broadcast (sending a message to all nodes of a network). Efficient protocols for both problems are presented. Even though the protocols are probabilistic, it is shown how to acknowledge messages deterministically.

Let n, D, and DELTA be the number of hodes, the diameter and the maximum degree of our network, respectively. Both protocols require a setup phase in which a BFS qee is constructed. This phase takes O((n+Dlogn)logDELTA) time, after which k point-to-point transmissions require an average of O((k+D)logDELTA) time. Therefore the network allows a new transmission every O(logDELTA) time slots.

After the setup, k broadcasts require an average of O((k+D)logDELTAlogn) time. Hence the average throughput of the network is a broadcast every O(logDELTAlogn) time slots. Both protocols pipeline the messages along the BFS tree. They are always successful on the graph spanned by the BFS tree. Their probabilistic behavior refers only to the running time.

Using the above protocols the ranking problem is solved in O(nlogn logDELTA) time. The performance analysis of both protocols constitutes a new application of queueing theory.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1989
To the main CS technical reports page

Computer science department, Technion