کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
438580 | 690296 | 2007 | 12 صفحه PDF | دانلود رایگان |
A 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.
Journal: Theoretical Computer Science - Volume 377, Issues 1–3, 31 May 2007, Pages 43-54