|
 ABSTRACT
In this paper we present GOAFR, a new geometric ad-hoc routing algorithm combining greedy and face routing. We evaluate this algorithm by both rigorous analysis and comprehensive simulation. GOAFR is the first ad-hoc algorithm to be both asymptotically optimal and average-case efficient. For our simulations we identify a network density range critical for any routing algorithm. We study a dozen of routing algorithms and show that GOAFR outperforms other prominent algorithms, such as GPSR or AFR.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
 |
1
|
|
| |
2
|
|
| |
3
|
Prosenjit Bose , Pat Morin , Andrej Brodnik , Svante Carlsson , Erik D. Demaine , Rudolf Fleischer , J. Ian Munro , Alejandro López-Ortiz, Online Routing in Convex Subdivisions, Proceedings of the 11th International Conference on Algorithms and Computation, p.47-59, December 18-20, 2000
|
| |
4
|
Prosenjit Bose , Pat Morin , Ivan Stojmenović , Jorge Urrutia, Routing with guaranteed delivery in ad hoc wireless networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, p.48-55, August 20-20, 1999, Seattle, Washington, United States
[doi> 10.1145/313239.313282]
|
| |
5
|
Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States
[doi> 10.1145/288235.288256]
|
| |
6
|
|
| |
7
|
O. Dousse, P. Thiran, and M. Hasler. Connectivity in ad-hoc and hybrid networks. In Proc. IEEE Infocom, New York, NY, USA, June 2002.
|
| |
8
|
G. Finn. Routing and addressing problems in large metropolitan-scale internetworks. Technical Report ISI/RR-87-180, USC/ISI, March 1987.
|
| |
9
|
Jie Gao , Leonidas Guibas , John Hershberger , Li Zhang , An Zhu, Discrete mobile centers, Proceedings of the seventeenth annual symposium on Computational geometry, p.188-196, June 2001, Medford, Massachusetts, United States
[doi> 10.1145/378583.378666]
|
| |
10
|
Jie Gao , Leonidas J. Guibas , John Hershberger , Li Zhang , An Zhu, Geometric spanner for routing in mobile networks, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA
[doi> 10.1145/501422.501424]
|
| |
11
|
S. Giordano, I. Stojmenovic, and L. Blazevic. Position based routing algorithms for ad hoc networks: a taxonomy, July 2001.
|
| |
12
|
T. Hou and V. Li. Transmission range control in multihop packet radio networks. IEEE Transactions on Communications, 34(1):38--44, 1986.
|
| |
13
|
D. B. Johnson and D. A. Maltz. Dynamic source routing in ad hoc wireless networks. In Imielinski and Korth, editors, Mobile Computing, volume 353. Kluwer Academic Publishers, 1996.
|
| |
14
|
|
| |
15
|
Y. Ko and N. Vaidya. Geocasting in mobile ad hoc networks: Location-based multicast algorithms. Technical Report TR-98-018, Texas A&M University, September 1998.
|
| |
16
|
E. Kranakis, H. Singh, and J. Urrutia. Compass routing on geometric networks. In Proc. 11th Canadian Conference on Computational Geometry, pages 51--54, Vancouver, Canada, August 1999.
|
| |
17
|
Fabian Kuhn , Roger Wattenhofer , Yan Zhang , Aaron Zollinger, Geometric ad-hoc routing: of theory and practice, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.63-72, July 13-16, 2003, Boston, Massachusetts
[doi> 10.1145/872035.872044]
|
| |
18
|
|
| |
19
|
M. Mauve, J. Widmer, and H. Hartenstein. A survey on position-based routing in mobile ad-hoc networks. In IEEE Network, November 2001.
|
| |
20
|
|
| |
21
|
|
| |
22
|
H. Takagi and L. Kleinrock. Optimal transmission ranges for randomly distributed packet radio terminals. IEEE Transactions on Communications, 32(3):246--257, 1984.
|
| |
23
|
|
CITED BY 66
|
|
|
|
|
|
|
|
|
|
|
Christopher L. Barrett , Stephan J. Eidenbenz , Lukas Kroc , Madhav Marathe , James P. Smith, Parametric probabilistic sensor network routing, Proceedings of the 2nd ACM international conference on Wireless sensor networks and applications, September 19-19, 2003, San Diego, CA, USA
|
|
|
|
|
|
Guoliang Xing , Chenyang Lu , Robert Pless , Qingfeng Huang, On greedy geographic routing algorithms in sensing-covered networks, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan
|
|
|
Wen-Zhan Song , Yu Wang , Xiang-Yang Li , Ophir Frieder, Localized algorithms for energy efficient topology in wireless ad hoc networks, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan
|
|
|
Karim Seada , Marco Zuniga , Ahmed Helmy , Bhaskar Krishnamachari, Energy-efficient forwarding strategies for geographic routing in lossy wireless sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA
|
|
|
Gady Kozma , Zvi Lotker , Micha Sharir , Gideon Stupp, Geometrically aware communication in random wireless networks, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
|
|
|
|
|
|
|
|
|
Guoliang Xing , Xiaorui Wang , Yuanfang Zhang , Chenyang Lu , Robert Pless , Christopher Gill, Integrated coverage and connectivity configuration for energy conservation in sensor networks, ACM Transactions on Sensor Networks (TOSN), v.1 n.1, p.36-72, August 2005
|
|
|
Wensheng Zhang , Hui Song , Sencun Zhu , Guohong Cao, Least privilege and privilege deprivation: towards tolerating mobile sink compromises in wireless sensor networks, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA
|
|
|
|
|
|
|
|
|
|
|
|
Tommaso Melodia , Dario Pompili , Vehbi C. Gungor , Ian F. Akyildiz, A distributed coordination framework for wireless sensor and actor networks, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Zoltán Vincze , Dorottya Vass , Rolland Vida , Attila Vidács , András Telcs, Adaptive sink mobility in event-driven multi-hop wireless sensor networks, Proceedings of the first international conference on Integrated internet ad hoc and sensor networks, May 30-31, 2006, Nice, France
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Paolo Baronti , Prashant Pillai , Vince W. C. Chook , Stefano Chessa , Alberto Gotta , Y. Fun Hu, Wireless sensor networks: A survey on the state of the art and the 802.15.4 and ZigBee standards, Computer Communications, v.30 n.7, p.1655-1695, May, 2007
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Fabian Kuhn , Roger Wattenhofer , Yan Zhang , Aaron Zollinger, Geometric ad-hoc routing: of theory and practice, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.63-72, July 13-16, 2003, Boston, Massachusetts
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Luminita Moraru , Pierre Leone , Sotiris Nikoletseas , José D. P. Rolim, Near optimal geographic routing with obstacle avoidance in wireless sensor networks by fast-converging trust-based algorithms, Proceedings of the 3rd ACM workshop on QoS and security for wireless and mobile networks, October 22-22, 2007, Chania, Crete Island, Greece
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Jianxin Wang , Yuhong Luo , Jiawei Huang , Xi Zhang, VCGG: a varying cone distributed topology-control algorithm for wireless ad hoc networks, Proceedings of the 5th International ICST Conference on Heterogeneous Networking for Quality, Reliability, Security and Robustness, July 28-31, 2008, Hong Kong
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
F.2