We consider Mobile Ad-hoc NETworks (MANETs) formed by n nodes that move independently at random over a finite square region of the plane. Nodes exchange data if they are at distance at most r within each other, where r > 0 is the node transmission radius. The flooding time is the number of time steps required to broadcast a message from a source node to every node of the network. Flooding time is an important measure of the speed of information spreading in dynamic networks. We derive a nearly-tight upper bound on the flooding time which is a decreasing function of the maximal velocity of the nodes. It turns out that, when the node velocity is "sufficiently" high, even if the node transmission radius r is far below the connectivity threshold, the flooding time does not asymptotically depend on r. So, flooding can be very fast even though every snapshot (i.e. the static random geometric graph at any fixed time) of the MANET is fully disconnected. Our result is the first analytical evidence of the fact that high, random node mobility strongly speed-up information spreading and, at the same time, let nodes save energy.

Clementi, A., Pasquale, F., Silvestri, R. (2009). Manets: High Mobility Can Make Up for Low Transmission Power. In AUTOMATA, LANGUAGES AND PROGRAMMING, PT II, PROCEEDINGS (pp.387-398). BERLIN : SPRINGER-VERLAG BERLIN [10.1007/978-3-642-02930-1_32].

Manets: High Mobility Can Make Up for Low Transmission Power

CLEMENTI, ANDREA;PASQUALE, FRANCESCO;
2009-07-11

Abstract

We consider Mobile Ad-hoc NETworks (MANETs) formed by n nodes that move independently at random over a finite square region of the plane. Nodes exchange data if they are at distance at most r within each other, where r > 0 is the node transmission radius. The flooding time is the number of time steps required to broadcast a message from a source node to every node of the network. Flooding time is an important measure of the speed of information spreading in dynamic networks. We derive a nearly-tight upper bound on the flooding time which is a decreasing function of the maximal velocity of the nodes. It turns out that, when the node velocity is "sufficiently" high, even if the node transmission radius r is far below the connectivity threshold, the flooding time does not asymptotically depend on r. So, flooding can be very fast even though every snapshot (i.e. the static random geometric graph at any fixed time) of the MANET is fully disconnected. Our result is the first analytical evidence of the fact that high, random node mobility strongly speed-up information spreading and, at the same time, let nodes save energy.
36th International Colloquium on Automata, Languages and Programming
Rhodes, GREECE
JUL 05-12, 2009
36
Minist Natl Educ & Religious Affairs Greece, Res Acad Comp Technol Inst, Piraeus Bank, Rigorous Math Connect Theory Computat & Statist Phys, European Res Council, Algorithm Principles Building8 Efficient Overlay Comp Project EU, FET, Global Comp, Papasotirou Books, Google
Rilevanza internazionale
contributo
11-lug-2009
Settore INF/01 - INFORMATICA
English
DYNAMIC NETWORKS; BROADCAST; PROBABILISTIC ANALYSIS
Intervento a convegno
Clementi, A., Pasquale, F., Silvestri, R. (2009). Manets: High Mobility Can Make Up for Low Transmission Power. In AUTOMATA, LANGUAGES AND PROGRAMMING, PT II, PROCEEDINGS (pp.387-398). BERLIN : SPRINGER-VERLAG BERLIN [10.1007/978-3-642-02930-1_32].
Clementi, A; Pasquale, F; Silvestri, R
File in questo prodotto:
File Dimensione Formato  
ICALP09lncs.pdf

solo utenti autorizzati

Descrizione: extended abstract
Dimensione 203.36 kB
Formato Adobe PDF
203.36 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/2108/25641
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 25
  • ???jsp.display-item.citation.isi??? 21
social impact