To what extent can one "prune" the links in a wireless network while retaining (almost) the same connectivity achieved when each node is connected to all nodes within its communication radius? In a nutshell, if each node explores a portion of its neighborhood sufficient to reach ≈ log(1/ε) other nodes in expectation, w.h.p. all but a fraction ε of the network joins the same connected component. Each node can then "locally" choose to maintain (at most) 4 links, and the network still retains w.h.p. essentially the same level of connectivity.

(More) Efficient Pruning of Wireless Ad Hoc Networks

PESERICO STECCHINI NEGRI DE SALVI, ENOCH
2009

Abstract

To what extent can one "prune" the links in a wireless network while retaining (almost) the same connectivity achieved when each node is connected to all nodes within its communication radius? In a nutshell, if each node explores a portion of its neighborhood sufficient to reach ≈ log(1/ε) other nodes in expectation, w.h.p. all but a fraction ε of the network joins the same connected component. Each node can then "locally" choose to maintain (at most) 4 links, and the network still retains w.h.p. essentially the same level of connectivity.
2009
Proc. of ACM PODC'09
ACM Symp. on the Principles of Distributed Computing (PODC)
9781605583969
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11577/2373715
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
  • OpenAlex ND
social impact