by András A. Benczúr, Uwe Glasser and Tamás Lukovszki
Proceedings of the ASM 2003 International Conference on Abstract State Machines, 2003. LNCS volume.
We introduce a new decentralized distributed hypercubic location service (HLS) for mobile ad-hoc networks. Underlying HLS is an O (log log n) degree graph such each mobile node must update its geographic position to its HLS neighbors. HLS provides efficient memoryless routing when combined with geographic routing over spanner graphs and in particular the Yao (or theta) graphs. Of independent interest is our new result that improves over bounds for the existence of approximate energy minimum paths in spanner graphs.
A key feature of HLS is its very strong fault tolerance as well as scalability to large changes in the number of nodes, allowing very flexible control over the network size: A large network can be gradually built from a few nodes and then again it can be reduced to a very small size with fast network topology updates. In addition the architecture is extremely fault tolerant: It resists the simultaneous failure of a constant fraction of the nodes, including even a systematic destruction within certain regions. The combination of scalability and fault tolerance results in survival of even a relative fast demolition.