Premium
Hierarchical routing over dynamic wireless networks
Author(s) -
Tschopp Dominique,
Diggavi Suhas,
Grossglauser Matthias
Publication year - 2015
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20589
Subject(s) - computer science , overhead (engineering) , computer network , routing (electronic design automation) , topology (electrical circuits) , graph , wireless network , topology control , constant (computer programming) , distributed computing , wireless , mathematics , theoretical computer science , key distribution in wireless sensor networks , telecommunications , combinatorics , programming language , operating system
The topology of a mobile wireless network changes over time. Maintaining routes between all nodes requires the continuous transmission of control information, which consumes precious power and bandwidth resources. Many routing protocols have been developed, trading off control overhead and route quality. In this paper, we ask whether there exist low‐overhead schemes that produce low‐stretch routes, even in large networks where all the nodes are mobile. We present a scheme that maintains a hierarchical structure within which constant‐stretch routes can be efficiently computed between every pair of nodes. The scheme rebuilds each level of the hierarchy periodically, at a rate that decreases exponentially with the level of the hierarchy. We prove that this scheme achieves constant stretch under a mild smoothness condition on the nodal mobility processes. Furthermore, we prove tight bounds for the network‐wide control overhead under the additional assumption of the connectivity graph forming a doubling metric space. Specifically, we show that for a connectivity model combining the random geometric graph with obstacles, constant‐stretch routes can be maintained with a total overhead of n log 2 n bits of control information per time unit. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 47, 669–709, 2015