Computing connected dominated sets with multipoint relays

Cédric Adjih (1) , Philippe Jacquet (1) , Laurent Viennot (2)

1 HIPERCOM - High performance communication
2 GYROWEB - Dynamic graphs and the web graph

Multipoint relays offer an optimized way of flooding packets in a radio network. However, this technique requires the last hop knowledge: to decide whether or not a flooding packet is retransmitted, a node needs to know from which node the packet was received. When considering broadcasting at IP level, this information may be difficult to obtain. We thus propose a scheme for computing an optimized connected dominating set from multipoint relays. Proof of correctness and simulations are given for all these broadcasting mechanisms.

Domaines: Algorithme et structure de données [cs.DS]; Calcul parallèle, distribué et partagé [cs.DC]; Réseaux et télécommunications [cs.NI]; Web

Cédric Adjih, Philippe Jacquet, Laurent Viennot. Computing connected dominated sets with multipoint relays. Ad Hoc & Sensor Wireless Networks, 2005, 1 (1-2), pp.27-39. ⟨inria-00471715⟩