routing with guaranteed delivery in three-dimensional ad hoc wireless networks
We Study the problem of routing in three-dimensional ad hoc networks. We ire interested in routing algorithms that guarantee delivery and are k-local, i e., each intermediate node Vs routing decision only depends oil knowledge of the labels of the Source and destination nodes, of the subgraph induced by nodes within distance k of v, and of the neighbour of v from which the message was received. We model a three-dimensional ad hoc network by a unit ball graph, where nodes are points in three-dimensional space, and for each node v. there is all edge between v and every node it contained in the unit-radius ball centred at v. The question of whether there is a simple local routing algorithm that guarantees delivery in Win. ball graphs has been open for some time. in this paper, we answer this question in the negative: we show that for any fixed k, there call be no k-local routing algorithm that guarantees delivery oil all unit ball graphs. This result is in contrast with file two-dimensional case, where I-local routing algorithms; that guarantee delivery are known. Specifically. we show that guaranteed delivery is possible if the nodes of the unit ball graph ire contained in a slab of thickness 1/root 2. However, there is no k-local routing algorithm that guarantees delivery for the class of unit ball graphs contained in thicker slabs, i.e., slabs of thickness 1/root 2+epsilon for some epsilon > 0. The algorithm for routing in thin slabs derives from a transformation of unit ball graphs contained in thin slabs into quasi unit disc graphs, which yields a 2-local routing algorithm. We also show several results that further elaborate oil the relationship between these two classes of graphs.
routing ad hoc networks unit ball graph quasi unit disc graph distributed algorithms