Bounds for Deterministic Reliable Geocast in Mobile Ad-Hoc Networks

摘要

In this paper we study the impact of the speed of movement of nodes on the solvability of deterministic reliable geocast in mobile ad-hoc networks, where nodes move in a continuous manner with bounded maximum speed. Nodes do not know their position, nor the speed or direction of their movements. Nodes communicate over a radio network, so links may appear and disappear as nodes move in and out of the transmission range of each other. We assume that it takes a given time T for a single-hop communication to reliably complete. The mobility of nodes may be an obstacle for deterministic reliable communication, because the speed of movements may impact on how quickly the communication topology changes.rnAssuming the two-dimensional mobility model, the paper presents two tight bounds for the solvability of deterministic geocast. First, we prove that the maximum speed v_(max) < δ/T is a necessary and sufficient condition to solve the geocast, where δ is a parameter that together with the maximum speed captures the local stability in the communication topology. We also prove that Ω(nT) is a time complexity lower bound for a geocast algorithm to ensure deterministic reliable delivery, and we provide a distributed solution which is asymptotically optimal in time.rnFinally, assuming the one-dimensional mobility model, i.e. nodes moving on a line, we provide a lower bound on the speed of movement necessary to solve the geocast problem, and we give a distributed solution. The algorithm proposed is more efficient in terms of time and message complexity than the algorithm for two dimensions.