Acknowledged Broadcasting and Gossiping in ad hoc radio networks

Abstract. A radio network is a collection of transmitter-receiver devices (referred to as nodes). ARB (Acknowledged Radio Broadcasting) means transmitting a message from one special node called source to all the nodes and informing the source about its completion. In our model each node takes a synchronization per round and performs transmission or reception at one round. Each node does not have a collision detection capability and knows only own ID. In [1], it is proved that no ARB algorithm exists in the model without collision detection. In this paper, we show that if n ≥ 2, where n is the number of nodes in the network, we can construct algorithms which solve ARB in O(n) rounds for bidirectional graphs and in O(n 3/2) rounds for strongly connected graphs and solve ARG (Acknowledged Radio Gossiping) in O(n log 3 n) rounds for bidirectional graphs and in O(n 3/2) rounds for strongly connected graphs without collision detection