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 mes sage to all nodes of a network). Efficient protocols for both problems are presented. Even though the protocols are probabilistic, it is sho wn how to acknowledge messages deterministically. Let n, D, and DELTA be the number of nodes, the diameter and the maximum degree of our net work, respectively. Both protocols require a setup phase in which a BF S tree is constructed. This phase takes O((n + D log n) log DELTA) tim e. After the setup, k point-to-point transmissions require O((k + D) l og DELTA) time on the average. Therefore the network allows a new tran smission every O(log DELTA) time slots. Also, k broadcasts require an average of O((k + D) log DELTA log n) time. Hence the average throughp ut 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 alwa ys successful on the graph spanned by the BFS tree. Their probabilisti c 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 perfor mance analysis of both protocols constitutes a new application of queu eing theory.