Distributed Broadcast in Wireless Networks with Unknown Topology

摘要: A multi-hop synchronous wirelss network is said to be unknown if the nodes have no knowledge of topology. basic task in wireless that broadcasting a message (created by fixed source node) all network. Typical operations real-life networks multi-broadcast consists performing set r independent broadcasts. The study broadcast on started seminal paper Bar-Yehuda et al [BGI87] and has been subject several recent works. In this paper, we completion termination time distributed protocols for both (single) as functions number n, maximum eccentricity D, in-degree �, congestion c networks. We establish new connections between these some combinatorial concepts, such selective families, strongly-selective families (also known superimposed codes), pairwise r-different families. Such connections, combined with lower upper bounds size above allow us derive operations. particular, our are almost tight improve exponentially over previous