XDZH
Summary
Qin, Xin, Jean-Charles, Delvenne, Zhanlong, Zhang and Wei, He (2011) Improved Compact Routing Scheme with Applications in Static Sensor Networks and Internet. In The 2011 IEEE International Conference on Cyber, Physical, and Social Computing. Dalian, China, oct. (PDF)
Abstract
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(c\frac{\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 G\k{a}sieniec, Su, Wong and Xin in \cite{GSWX05} [J. Discrete Algorithms 5(1): 1-11 (2007)] for the scenario when {$D\le \Theta(2^{\sqrt{\log n}})$} that has {$O(c\log n)$} transmissions for each query and {$O(\log n\log 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 forgeometric 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.
Bibtex entry
@INPROCEEDINGS { XDZH,
AUTHOR = { Qin, Xin and Jean-Charles, Delvenne and Zhanlong, Zhang and Wei, He },
TITLE = { Improved Compact Routing Scheme with Applications in Static Sensor Networks and Internet },
BOOKTITLE = { The 2011 IEEE International Conference on Cyber, Physical, and Social Computing },
YEAR = { 2011 },
MONTH = { oct },
ADDRESS = { Dalian, China },
ABSTRACT = { 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(c\frac{\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 G\k{a}sieniec, Su, Wong and Xin in \cite{GSWX05} [J. Discrete Algorithms 5(1): 1-11 (2007)] for the scenario when {$D\le \Theta(2^{\sqrt{\log n}})$} that has {$O(c\log n)$} transmissions for each query and {$O(\log n\log 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 forgeometric 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. },
PDF = { File:Publications/06142282.pdf },
}