We investigate the problem of communication in an ad-hoc mobile network, that is, we assume the extreme case of a total absense of any fixed network infrastructure (for example a case of rapid deployment of a set of mobile hosts in an unknown terrain). We propose, in such a case, that a small subset of the deployed hosts (which we call the support) should be used for network operations. However, the vast majority of the hosts are moving arbitrarily according to application needs. We then provide a simple, correct and efficient protocol for communication that avoids message flooding. Our protocol manages to establish communication between any pair of mobile hosts in small, a-priori guaranteed expected time bounds even in the worst case of arbitrary motions of the hosts that not in the support (provided that they do not deliberately try to avoid the support). These time bounds, interestingly, do not depend, on the number of mobile hosts that do not belong in the support. They depend only on the size of the area of motions. Our protocol can be implemented in very efficient ways by exploiting knowledge of the space of motions or by adding more power to the hosts of the support. Our results exploit and further develop some fundamental properties of random walks in finite graphs. © Springer-Verlag Berlin Heidelberg 2001.

An efficient communication strategy for ad-hoc mobile networks / Chatzigiannakis, I.; Nikoletseas, S.; Spirakis, P.. - 2180:(2001), pp. 285-299. (Intervento presentato al convegno 15th International Conference Distributed Computing tenutosi a Lisbon, Portugal).

An efficient communication strategy for ad-hoc mobile networks

Chatzigiannakis, I.
Primo
Formal Analysis
;
2001

Abstract

We investigate the problem of communication in an ad-hoc mobile network, that is, we assume the extreme case of a total absense of any fixed network infrastructure (for example a case of rapid deployment of a set of mobile hosts in an unknown terrain). We propose, in such a case, that a small subset of the deployed hosts (which we call the support) should be used for network operations. However, the vast majority of the hosts are moving arbitrarily according to application needs. We then provide a simple, correct and efficient protocol for communication that avoids message flooding. Our protocol manages to establish communication between any pair of mobile hosts in small, a-priori guaranteed expected time bounds even in the worst case of arbitrary motions of the hosts that not in the support (provided that they do not deliberately try to avoid the support). These time bounds, interestingly, do not depend, on the number of mobile hosts that do not belong in the support. They depend only on the size of the area of motions. Our protocol can be implemented in very efficient ways by exploiting knowledge of the space of motions or by adding more power to the hosts of the support. Our results exploit and further develop some fundamental properties of random walks in finite graphs. © Springer-Verlag Berlin Heidelberg 2001.
2001
15th International Conference Distributed Computing
Basic Communication, Wireless Adhoc Mobile Networks, Routing Protocols, Markov Chains, Random Walks
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
An efficient communication strategy for ad-hoc mobile networks / Chatzigiannakis, I.; Nikoletseas, S.; Spirakis, P.. - 2180:(2001), pp. 285-299. (Intervento presentato al convegno 15th International Conference Distributed Computing tenutosi a Lisbon, Portugal).
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

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/11573/1333432
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 27
  • ???jsp.display-item.citation.isi??? ND
social impact