On adaptive deterministic gossiping in ad hoc radio networks

✍ Scribed by Leszek Ga̧sieniec; Andrzej Lingas

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 64 KB
• Volume: 83
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(01)00312-x

✦ Synopsis

We study deterministic algorithms for gossiping problem in ad hoc radio networks. The efficiency of communication algorithms in radio networks is very often expressed in terms of: maximum eccentricity D, maximum in-degree ∆, and size (number of nodes) n of underlying graph of connections. The maximum eccentricity D of a network is the maximum of the lengths of shortest directed paths from a node u to a node v, taken over all ordered pairs (u, v) of nodes in the network. The maximum in-degree ∆ of a network is the maximum of in-degrees of its nodes.

We propose a new method that leads to several improvements in deterministic gossiping. It combines communication techniques designed for both known as well as unknown ad hoc radio networks. First we show how to subsume the O(Dn)time bound yield by the round-robin procedure proposing a new O( √ D n)-time gossiping algorithm. 1 Our algorithm is more efficient than the known O(n 3/2 )-time gossiping algorithms [Proc.