Name
Abstract | ||
|---|---|---|
A multi-hop synchronous radio network is said to be unknown if the nodes have no knowledge of the topology. A basic task in radio network is that of broadcasting a message (created by a fixed source node) to all nodes of the network. Typical operations in real-life radio networks is the multi-broadcast that consists in performing a set of r independent broadcasts. The study of broadcast operations on unknown radio network is started by the seminal paper of Bar-Yehuda et al. [J. Comput. System Sci. 45 (1992) 104] and has been the subject of several recent works.In this paper, we study the completion and the termination time of distributed protocols for both the (single) broadcast and the multi-broadcast operations on unknown networks as functions of the number of nodes n, the maximum eccentricity D, the maximum in-degree Δ, and the congestion c of the networks. We establish new connections between these operations and some combinatorial concepts, such as selective families, strongly selective families (also known as superimposed codes), and pairwise r-different families. Such connections, combined with a set of new lower and upper bounds on the size of the above families, allow us to derive new lower bounds and new distributed protocols for the broadcast and multi-broadcast operations. In particular, our upper bounds are almost tight and strongly improve over the previous bounds for a large class of networks. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1016/S0304-3975(02)00851-4 | Theor. Comput. Sci. |
Keywords | Field | DocType |
unknown radio network,unknown network,new connection,radio network,multi-hop synchronous radio network,real-life radio network,selective family,new lower bound,unknown topology,multi-broadcast operation,upper bound | Topology,Broadcasting,Radio networks,Mathematics | Journal |
Volume | Issue | ISSN |
302 | 1-3 | Theoretical Computer Science |
Citations | PageRank | References |
68 | 2.44 | 31 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrea E. F. Clementi | 1 | 1168 | 85.30 |
| Angelo Monti | 2 | 671 | 46.93 |
| Riccardo Silvestri | 3 | 1324 | 90.84 |