On routing with guaranteed delivery in three-dimensional ad hoc wireless networks

摘要: We study routing algorithms for three-dimensional ad hoc networks that guarantee delivery and are k-local, i.e., each intermediate node υ's decision only depends on knowledge of the labels source destination nodes, subgraph induced by nodes within distance k υ, neighbour υ from which message was received. model a network unit ball graph, where points in R3, u joined an edge if between v is at most one. The question whether there simple local algorithm guarantees graphs has been open some time. In this paper, we answer negative: show any fixed k, can be no k-local all graphs. This result contrast with two-dimensional case, 1-local known. Specifically, guaranteed possible graph contained slab thickness 1/√2. However, class thicker slabs, slabs 1/√2+Ɛ Ɛ > 0. The thin derives transformation into quasi disc graphs, yields 2-local algorithm. also several results further elaborate relationship these two classes