Improved Compact Routing Scheme with Applications in Static Sensor Networks and Internet

摘要

In this paper, we investigate {a} compact routing scheme with applications in static sensor networks and Internet. More precisely, we propose a new geometric ad-hoc routing algorithm to route queries in static {geometric graphs} in which the number of transmissions for each query and the space used to store the routing information on each node in terms of the number of registers (each able to store an integer/real number) are bounded by $O(cfrac{log D}{log c})$ and $O(log^3 D)$ respectively, where $c$ is the length of the shortest path between the source and the destination and $D$ is the diameter of the network. Our algorithm significantly improves the complexity of the currently best known algorithm by Gk{a}sieniec, Su, Wong and Xin in cite{GSWX05} [J. Discrete Algorithms 5(1): 1-11 (2007)] for the scenario when $Dle Theta(2^{sqrt{log n}})$ that has $O(clog n)$ transmissions for each query and $O(log nlog D)$ registers in each node, where $n$ is the number of nodes in the network. Moreover, our new routing algorithm also reserves extremely better scalability compared with the currently best known algorithm in cite{GSWX05} since it does not depend on the size of the network. {Unsurprisingly, our new compact routing scheme for geometric graphs also outperforms} the currently best known algorithm for general graphs by Abraham, Gavoille, and Malkhi in cite{AGM06} [SPAA 2006], e.g., our scheme can reduce the space requirement from $O(log^5 n)$ per node to $O(log^3 D)$ with the exactly same stretch factor $O(log n)$. While our work directly applies to sensor networks, we hope that it can stimulate the future research on impact of the graph properties to the performance of compact routing schemes.