MULTIPLE COMMUNICATION IN MULTIHOP RADIO NETWORKS

Two tasks of communication in a multihop synchronous radio network are considered: Point-to-point 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 nodes, the diameter and the maximum degree of our network, respectively. Both protocols require a setup phase in which a BFS tree is constructed. This phase takes O((n + D log n) log DELTA) time. After the setup, k point-to-point transmissions require O((k + D) log DELTA) time on the average. Therefore the network allows a new transmission every O(log DELTA) time slots. Also, k broadcasts require an average of O((k + D) log DELTA log n) time. Hence the average throughput of the network is a broadcast every O(log DELTA log n) 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(n log n log DELTA) time. The performance analysis of both protocols constitutes a new application of queueing theory.