Weitere Artikel dieser Ausgabe durch Wischen aufrufen
Routing in wireless networks has been heavily studied in the last decade. Many routing protocols are based on classic shortest path algorithms. However, shortest path-based routing protocols suffer from uneven load distribution in the network, such as crowed center effect where the center nodes have more load than the nodes in the periphery. Aiming to balance the load, we propose a novel routing method, called Circular Sailing Routing (CSR), which can distribute the traffic more evenly in the network. The proposed method first maps the network onto a sphere via a simple stereographic projection, and then the route decision is made by a newly defined "circular distance" on the sphere instead of the Euclidean distance in the plane. We theoretically prove that for a network, the distance traveled by the packets using CSR is no more than a small constant factor of the minimum (the distance of the shortest path). We also extend CSR to a localized version, Localized CSR, by modifying greedy routing without any additional communication overhead. In addition, we investigate how to design CSR routing for 3D networks. For all proposed methods, we conduct extensive simulations to study their performances and compare them with global shortest path routing or greedy routing in 2D and 3D wireless networks.
Lee S-J, Gerla M: Dynamic load-aware routing in ad hoc networks. Proceedings of the IEEE International Conference on Communications (ICC '01), June 2001, Helsinki, Finland 10: 3206-3210.
Hassanein H, Zhou A: Routing with load balancing in wireless ad hoc networks. In Proceedings of the 4th ACM International Workshop on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWIM '01), 2001. ACM; 89-96.
Wu K, Harms J: Load-sensitive routing for mobile ad hoc networks. Proceedings of the 10th International Conference on Computer Communications and Networks, 2001 540-546.
Yi Y, Kwon TJ, Gerla M: A load aware routing (LWR) based on local information. Proceedings of the 12th IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC '01), 2001 2: 65-69.
Yoo Y, Ahn S: A simple load-balancing approach in cheat-proof ad hoc networks. Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM '04), November-December 2004, Dallas, Tex, USA 6: 3573-3577. CrossRef
Popa L, Rostamizadeh A, Karp R, Papadimitriou C, Stoica I: Balancing traffic load in wireless networks with curveball routing. Proceedings of the 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc '07)), September 2007 170-179. CrossRef
Li F, Wang Y: Circular sailing routing for wireless networks. Proceedings of the 27th IEEE Conference on Computer Communications (INFOCOM '08), 2008 2020-2028.
Coxeter HSM: Introduction to Geometry. 2nd edition. John Wiley & Sons, New York, NY, USA; 1969. MATH
Sarkar R, Zhu X, Gao J: Double rulings for information brokerage in sensor networks. Proceedings of the 12th Annual International Conference on Mobile Computing and Networking (MOBICOM '06), September 2006, Los Angeles, Calif, USA 286-297. CrossRef
Karp B, Kung HT: GPSR: greedy perimeter stateless routing for wireless networks. In Proceedings of the 6th Annual International Conference on Mobile Computing and Networking (MOBICOM '00), 2000. ACM; 243-254. CrossRef
Akyildiz IF, Pompili D, Melodia T: Underwater acoustic sensor networks: research challenges. Ad Hoc Networks 2005, 3(3):257-279. 10.1016/j.adhoc.2005.01.004 CrossRef
Hong X, Gerla M, Bagrodia R, Kwon TJ, Estabrook P, Pei G: The Mars sensor network: efficient, energy aware communications. Proceedings of the IEEE Military Communications Conference (MILCOM '01), 2001 1: 418-422.
Lee S-B, Cho J, Campbell AT: A hotspot mitigation protocol for ad hoc networks. Ad Hoc Networks 2003, 1(1):87-106. 10.1016/S1570-8705(03)00014-3 CrossRef
Krishnan R, Silvester JA: Choice of allocation granularity in multipath source routing schemes. Proceedings of the 12th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '93), 1993 1: 322-329. CrossRef
Cidon I, Rom R, Shavitt Y: Analysis of multi-path routing. IEEE/ACM Transactions on Networking 1999, 7(6):885-896. 10.1109/90.811453 CrossRef
Pearlman MR, Haas ZJ, Sholander P, Tabrizi SS: On the impact of alternate path routing for load balancing in mobile ad hoc networks. In Proceedings of the 1st ACM International Symposium on Mobile Ad Hoc Networking & Computing (MobiHoc '00), 2000, Piscataway, NJ, USA. IEEE Press; 3-10.
Pham PP, Perreau S: Performance analysis of reactive shortest path and multi-path routing mechanism with load balance. Proceedings of the 14th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '03), 2003 1: 251-259.
Wu K, Harms J: Performance study of a multipath routing method for wireless mobile Ad hoc networks. Proceedings of the IEEE International Workshop on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS '01), 2001 99-107.
Johnson DB, Maltz DA: Dynamic source routing in ad hoc wireless networks. In Mobile Computing. Volume 353. Edited by: Imielinski T, Korth H. Kluwer Academic Publishers, Dordrecht, The Netherlands; 1996:153-181. CrossRef
Pham P, Perreau S: Multi-path routing protocol with load balancing policy in mobile ad hoc network. Proceedings of the 4th IEEE International Workshop on Mobile and Wireless Communications Network, 2002 48-52. CrossRef
Ganjali Y, Keshavarzian A: Load balancing in ad hoc networks: single-path routing vs. multi-path routing. Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '04), 2004 2: 1120-1125.
Wang Y, Wang Z: Explicit routing algorithms for internet traffic engineering. Proceedings of the International Conference on Computer Communications and Networks (ICCCN '99), 1999 582-588.
Hyytiä E, Virtamo J: On traffic load distribution and load balancing in dense wireless multihop networks. EURASIP Journal on Wireless Communications and Networking 2007, 2007(1):21. CrossRef
Gao J, Zhang L: Load balanced short path routing in wireless networks. Proceedings of 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '04), 2004
Gao J, Zhang L: 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 (PODC '04), 2004. ACM; 189-196. CrossRef
- Load Balancing Routing with Bounded Stretch
- Springer International Publishing
- EURASIP Journal on Wireless Communications and Networking
Elektronische ISSN: 1687-1499
Neuer Inhalt/© ITandMEDIA, Product Lifecycle Management/© Eisenhans | vege | Fotolia