We present a model of a mobile ad-hoc network in which nodes can move arbitrarily on the plane with some bounded speed. We show that without any assumption on some topological stability, it is impossible to solve the geocast problem deterministically despite connectivity and no matter how slowly the nodes move. Moreover, even if each node maintains a stable connection with each of its neighbors for some period of time, it is impossible to solve the geocast problem if nodes move too fast. Additionally, we give a tradeoff lower bound which shows that the faster the nodes can move on a monodimensional space, the more costly it would be to solve the geocast problem. We provide geocasting algorithms for the case where nodes move in one dimension and also when they can move on the plane (i.e., in two dimensions). We prove correctness of our algorithms by giving exact bounds on the speed of movement. Our analysis helps understand the impact of speed of nodes, firstly, on geocasting solvability and, secondly, on the cost of geocasting. © 2010 Elsevier B.V. All rights reserved.
The impact of mobility on the geocasting problem in mobile ad-hoc networks: Solvability and cost / Baldoni, Roberto; A., Fernandez Anta; K., Ioannidou; A., Milani. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 412:12-14(2011), pp. 1066-1080. [10.1016/j.tcs.2010.12.006]
The impact of mobility on the geocasting problem in mobile ad-hoc networks: Solvability and cost
BALDONI, Roberto;
2011
Abstract
We present a model of a mobile ad-hoc network in which nodes can move arbitrarily on the plane with some bounded speed. We show that without any assumption on some topological stability, it is impossible to solve the geocast problem deterministically despite connectivity and no matter how slowly the nodes move. Moreover, even if each node maintains a stable connection with each of its neighbors for some period of time, it is impossible to solve the geocast problem if nodes move too fast. Additionally, we give a tradeoff lower bound which shows that the faster the nodes can move on a monodimensional space, the more costly it would be to solve the geocast problem. We provide geocasting algorithms for the case where nodes move in one dimension and also when they can move on the plane (i.e., in two dimensions). We prove correctness of our algorithms by giving exact bounds on the speed of movement. Our analysis helps understand the impact of speed of nodes, firstly, on geocasting solvability and, secondly, on the cost of geocasting. © 2010 Elsevier B.V. All rights reserved.File | Dimensione | Formato | |
---|---|---|---|
VE_2011_11573-376779.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
452.4 kB
Formato
Adobe PDF
|
452.4 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.