On average and maximum load of greedy routing in wireless ad hoc networks
Pages 113 - 120
Abstract
One common model that has been used to analyze routing algorithms in ad hoc networks considers networks that are so dense that a node exists close enough to any point in the network. Continuous techniques were used to calculate the average and maximum loads of the routing algorithms. In this paper we explain some limitations of such techniques in predicting the load of routing algorithms in discrete network models such as unit disk graphs even at high node densities. We present a new approach to find estimates of the average and maximum load induced by greedy routing in discrete network models. Our model takes into consideration parameters such as the transmission radius and the average degree of nodes, and is suitable for networks that are not necessarily very dense. Our model is validated by simulation results that closely match the theoretical predictions.
References
[1]
P. Bose, P. Morin, I. Stojmenović, and J. Urrutia. Routing with guaranteed delivery in ad hoc wireless networks. In Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, pages 48-55, 1999.
[2]
C. Busch, M. Magdon-Ismail, and J. Xi. Oblivious routing on geometric networks. In Proceedings of the 17th annual ACM symposium on Parallelism in algorithms and architectures, pages 316-324, 2005.
[3]
F. Chung, E. Coffman, M. Reiman, and B. Simon. The forwarding index of communication networks. IEEE Transactions on Information Theory, 1987.
[4]
S. De, A. Caruso, T. Chaira, and S. Chessa. Bounds on hop distance in greedy routing approach in wireless ad hoc networks. International Journal of Wireless and Mobile Computing, 2006.
[5]
S. Durocher, E. Kranakis, D. Krizanc, and L. Narayanan. Balancing Traffic Load Using One-Turn Rectilinear Routing. In Proceedings of the 5th International Conference on Theory and Applications of Models of Computation, pages 467-478, 2008.
[6]
J. Gao and L. Zhang. Load balanced short path routing in wireless networks. In Proceedings of IEEE INFOCOM, pages 1099-1108, 2004.
[7]
J. Gao and L. Zhang. Tradeoffs between stretch factor and load balancing ratio in routing on growth restricted graphs. In Proceedings of the 23rd annual ACM symposium on Principles of distributed computing, pages 189-196, 2004.
[8]
T. Hou and V. Li. Transmission range control in multihop packet radio networks. IEEE Transactions on Communications, 1986.
[9]
E. Hyytia and J. Virtamo. On load balancing in a dense wireless multihop network. In Proceedings of the 2nd Conference on Next Generation Internet Design and Engineering, pages 8 pp.-79, 2006.
[10]
B. Karp and H. Kung. GPSR: greedy perimeter stateless routing for wireless networks. In Proceedings of the 6th annual international conference on Mobile computing and networking, pages 243-254, 2000.
[11]
M. Kendall and P. Moran. Geometrical Probability. Griffin, London, 1963.
[12]
L. Klein and J. Silvester. Optimum transmission radii for packet radio networks or why six is a magic number. In Proceedings of IEEE National Telecommunications Conference, pages 4.3.1-4.3.5, 1978.
[13]
E. Kranakis, H. Singh, and J. Urrutia. Compass routing on geometric networks. In Proceedings of the 11th Canadian Conference on Computational Geometry, pages 51-54, 1999.
[14]
V. Park and M. Corson. A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks. Annual Joint Conference of the IEEE Computer and Communications Societies, 1997.
[15]
P. Pham and S. Perreau. Performance analysis of reactive shortest path and multipath routing mechanism with load balance. In Proceedings of INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications. IEEE Societies, pages 251-259.
[16]
L. Popa, A. Rostamizadeh, R. Karp, C. Papadimitriou, and I. Stoica. Balancing traffic load in wireless networks with curveball routing. In Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computing, pages 170-179, 2007.
[17]
I. Stojmenovic. Position-based routing in ad hoc networks. IEEE Communications Magazine, 2002.
[18]
H. Takagi and L. Kleinrock. Optimal Transmission Ranges for Randomly Distributed Packet Radio Terminals. IEEE Transactions on Communications, 1984.
Index Terms
- On average and maximum load of greedy routing in wireless ad hoc networks
Index terms have been assigned to the content through auto-classification.
Recommendations
Routing with load balancing in wireless Ad hoc networks
MSWIM '01: Proceedings of the 4th ACM international workshop on Modeling, analysis and simulation of wireless and mobile systemsAn ad hoc wireless mobile network is an infrastructure-less mobile network that has no fixed routers; instead, all nodes are capable of movement and can be connected dynamically in an arbitrary manner. In order to facilitate communication of mobile ...
Efficient on-demand routing for mobile ad hoc wireless access networks
In this paper, we consider a mobile ad hoc wireless access network in which mobile nodes can access the Internet via one or more stationary gateway nodes. Mobile nodes outside the transmission range of the gateway can continue to communicate with the ...
Load balanced routing protocols for ad hoc mobile wireless networks
Mobile ad hoc networks are collections of mobile nodes that can dynamically form temporary networks without the need for pre-existing network infrastructure or centralized administration. These nodes can be arbitrarily located and can move freely at any ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
February 2010
183 pages
ISBN:9781424460595
Publisher
IEEE Press
Publication History
Published: 03 February 2010
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 24 Sep 2024
Other Metrics
Citations
View Options
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