Distributed Broadcast in Wireless Networks with Unknown Topology
| dc.creator | Clementi, Andrea E. F. | |
| dc.creator | Monti, Angelo | |
| dc.creator | Silvestri, Riccardo | |
| dc.date | 2001-07-06 | |
| dc.date.accessioned | 2026-07-07T03:17:19Z | |
| dc.date.available | 2026-07-07T03:17:19Z | |
| dc.description | A multi-hop synchronous wirelss network is said to be unknown if the nodes have no knowledge of the topology. A basic task in wireless network is that of broadcasting a message (created by a fixed source node) to all nodes of the network. The multi-broadcast that consists in performing a set of r independent broadcasts. 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 Delta, 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 improve exponentially over the previous bounds when D and Delta are polylogarithmic in n. Network topologies having ``small'' eccentricity and ``small'' degree (such as bounded-degree expanders) are often used in practice to achieve efficient communication. | |
| dc.description | 27 pages, 1 figure, 1 table | |
| dc.identifier | https://arxiv.org/abs/cs/0107011 | |
| dc.identifier | http://arxiv.org/abs/cs/0107011 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/30683 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Discrete Mathematics | |
| dc.subject | C.2.1; F.2.2 | |
| dc.title | Distributed Broadcast in Wireless Networks with Unknown Topology | |
| dc.type | text |