Acknowledged broadcasting and gossiping in ad hoc radio networks

AbstractA radio network is a collection of transmitter–receiver devices (referred to as nodes). Acknowledged radio broadcasting (ARB) means transmitting a message from one special node called the source to all other 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 its own ID. In [B.S. Chlebus, L. Ga̧sieniec, A.M. Gibbons, A. Pelc, W. Rytter, Deterministic broadcasting in ad hoc radio networks, Distributed Computing 15 (2002) 27–38], 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 ARB algorithms in O(n) rounds for bidirectional graphs and in O(n4/3log10/3n) rounds for strongly connected graphs and construct acknowledged radio gossiping (ARG) algorithms in O(nlog3n) rounds for bidirectional graphs and in O(n4/3log10/3n) rounds for strongly connected graphs without collision detection