Trap array: a unified model for scalability evaluation of geometric routing
Pages 317 - 328
Abstract
Scalable routing for large-scale wireless networks needs to find near shortest paths with low state on each node, preferably sub-linear with the network size. Two approaches are considered promising toward this goal: compact routing and geometric routing (geo-routing). To date the two lines of research have been largely independent, perhaps because of the distinct principles they follow. In particular, it remains unclear how they compare with each other in the worst case, despite extensive experimental results showing the superiority of one or another in particular cases. We develop a novel Trap Array topology model that provides a unified framework to uncover the limiting behavior of ten representative geo-routing algorithms. We present a series of new theoretical results, in comparison with the performance of compact routing as a baseline. In light of their pros and cons, we further design a Compact Geometric Routing (CGR) algorithm that attempts to leverage the benefits of both approaches. Theoretic analysis and simulations show the advantages of the topology model and the algorithm.
References
[1]
B. Awerbuch, A. Bar-Noy, N. Linial, and D. Peleg. Improved routingstrategies with succinct tables. Journal of Algorithms.11(3):307--341, 1990.
[2]
B. Awerbuch and D. Peleg. Routing with polynomial communication-space trade-off. SIAM Journal on Discrete Mathematics, 5(2):151--162, 1992.
[3]
P. Bose, P. Morin, I. Stojmenovic and J. Urrutia. Routing with guaranteed delivery in ad hoc wireless networks. Proc. of DIALM'99.
[4]
J. Broch, D. A. Maltz, D. B. Johnson, Y.-C. Hu, and J. Jetcheva. A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols. Proc. of MobiCom 1998.
[5]
J. Bruck, J. Gao, A. Jiang. MAP: Medial Axis Based Geometric Routing in Sensor Networks, Proc. of MobiCom 2005.
[6]
M. Caesar, M. Castro, E. Nightingale, G. O'Shea, and A. Rowstron. Virtual ring routing: network routing inspired by DHTs. Proc.of ACM SIGCOMM 2006.
[7]
Q. Cao and T. Abdelzaher. A scalable logical coordinates framework for routing in wireless sensor networks. Proc. of IEEE Real-Time Systems Symposium (RTSS) 2004.
[8]
L. Cowen. Compact routing with minimum stretch. Journal of Algorithms, pages 170--183, 2001.
[9]
S. Du, A. Khan, S. PalChaudhuri, A. Post, A. K. Saha, P. Druschel,D. B. Johnson, R. Riedi. Safari: A self-organizing, hierarchical architecture for scalable ad hoc networking. Elsevier Ad Hoc Networks Journal, 2007.
[10]
T. Eilam, C. Gavoille, and D. Peleg. Compact routing schemes with low stretch factor. Proc. of the ACM PODC 1998.
[11]
Q. Fang, J. Gao, L. Guibas, V. de Silva, and L. Zhang. GLIDER: Gradient landmark-based distributed routing for sensor networks. Proc. INFOCOM 2005.
[12]
R. Fonseca, S. Ratnasamy, J. Zhao, C. T. Ee, D. Culler, S.Shenker, and I. Stoica. Beacon vector routing: Scalable point-to-point routing in wireless sensor nets. Proc. of NSDI2005.
[13]
B. A. Ford. UIA: A Global Connectivity Architecture for Mobile Personal Devices. PhD thesis, Massachusetts Institute of Technology,September 2008.
[14]
C. Gavoille. Routing in distributed networks: overview and open problems. ACM SIGACT News -- Distributed computing column,32(1):36--52, 2001.
[15]
M. Gerla, X. Hong, and G. Pei. Landmark routing for large ad hoc wireless networks. Proc. of Globecom, 2000.
[16]
K. Iwanicki and M. van Steen. On Hierarchical Routing in Wireless Sensor Networks. Proc. of ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN) 2009.
[17]
D. B. Johnson and D. A. Maltz. Dynamic source routing in ad hoc wireless networks. Mobile Computing, edited by Tomasz Imielinski and Hank Korth, chapter 5, pages 153--181. Kluwer Academic Publishers, 1996.
[18]
B. Karp and H. T. Kung. GPSR: Greedy perimeter stateless routing for wireless networks. Proc. of MobiCom 2000.
[19]
Y-J Kim, R. Govindan, B. Karp, and S. Shenker. Geographic Routing Made Practical. Proc. of NSDI 2005.
[20]
R. Kleinberg. Geographic Routing Using Hyperbolic Space. Proc.of INFOCOM 2007.
[21]
F. Kuhn, R. Wattenhofer, Y. Zhang, and A. Zollinger. Geometric Ad Hoc Routing: Of Theory and Practice. Proc. of ACM PODC, 2003.
[22]
F. Kuhn, R. Wattenhofer, and A. Zollinger. An Asymptotically Optimal Geometric Mobile Ad Hoc Routing. Proc. of ACM DIALM-POMC 2002.
[23]
F. Kuhn, R. Wattenhofer, and A. Zollinger. Worst-Case Optimal and Average-Case Efficient Geometric Ad-Hoc Routing. Proc. of ACM MobiHoc 2003.
[24]
S. S. Lam and C. Qian. Geographic Routing in d-dimensional Spaces with Guaranteed Delivery and Low Stretch. Proc. Sigmetrics 2011.
[25]
B. Leong, B. Liskov, and R. Morris. Geographic Routing without Planarization. In NSDI 2006.
[26]
Y. Mao, F. Wang, L. Qiu, S. S. Lam, and J. M. Smith. S4: Small state and small stretch routing protocol for large wireless sensor networks. In Proc. of NSDI 2007.
[27]
J. Newsome and D. Song. Gem: Graph embedding for routing and data-centric storage in sensor networks without geographic information. In Proc. of SenSys 2003.
[28]
D. Peleg and E. Upfal. A trade-off between space and efficiency for routing tables. Journal of the ACM, 36(3), 1989.
[29]
A. Rao, S. Ratnasamy, C. Papadimitriou, S. Shenker, and I. Stoica. Geographic routing without location information. In MobiCom2003.
[30]
A. Singla, P. B. Godfrey, K. Fall, G. Iannaccone, and S. Ratnasamy. Scalable Routing on Flat Names. Proc. of CoNext 2010.
[31]
M. Thorup and U. Zwick. Compact routing schemes. In Proc. of ACM SPAA 2001.
[32]
G. Tan, M. Bertier and A-M. Kermarrec. Convex Partition of Sensor Networks and Its Use in Virtual Coordinate Geographic Routing. Proc. of INFOCOM 2009.
[33]
G. Tan and A-M. Kermarrec. Greedy Geographic Routing in Large-Scale Sensor Networks: A Minimum Network Decomposition Approach. IEEE/ACM Trans. on Networking, 20(3): 864--877, 2012.
[34]
P. F. Tsuchiya. The landmark hierarchy: a new hierarchy for routing in very large networks. Proc. of SIGCOMM 1988.
[35]
C. Westphal and J. Kempf. A compact routing architecture for mobility. Proc. of MobiArch, 2008.
[36]
Y. Zhao, Y. Chen, B. Li, and Q. Zhang. Hop ID: A Virtual Coordinate-Based Routing for Sparse Mobile Ad Hoc Networks. IEEE Trans. on Mobile Computing, 6(9), 2007.
Index Terms
- Trap array: a unified model for scalability evaluation of geometric routing
Recommendations
Trap array: a unified model for scalability evaluation of geometric routing
SIGMETRICS '13: Proceedings of the ACM SIGMETRICS/international conference on Measurement and modeling of computer systemsScalable routing for large-scale wireless networks needs to find near shortest paths with low state on each node, preferably sub-linear with the network size. Two approaches are considered promising toward this goal: compact routing and geometric ...
Trap array: a unified model for scalability evaluation of geometric routing
Scalable routing for large-scale wireless networks needs to find near shortest paths with low state on each node, preferably sublinear with the network size. Two approaches are considered promising toward this goal: compact routing and geometric routing ...
Void traversal for efficient non-planar geometric routing
Geometric routing provides a scalable and efficient way to route messages in ad hoc networks if extensive routing information is unavailable. Such algorithms require a planar graph to guarantee message delivery. The routing techniques for such guarantee ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2013406 pagesISBN:9781450319003DOI:10.1145/2465529- General Chair:
- Mor Harchol-Balter,
- Program Chairs:
- John Douceur,
- Jun Xu
Copyright © 2013 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 17 June 2013
Published in SIGMETRICS Volume 41, Issue 1
Check for updates
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 207Total Downloads
- Downloads (Last 12 months)2
- Downloads (Last 6 weeks)0
Reflects downloads up to 12 Nov 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in