Antonio Carzaniga
ABSTRACT
We propose a routing scheme to implement multicast communication in wireless networks. The scheme is oblivious, compact, and completely decentralized. It is intended to support dynamic and diverse multicast requests typical of, for example, publish/subscribe and content-based communication. The scheme is built on top of a geographical routing layer. Each message is transmitted along the geometric minimum spanning tree that connects the source and all the destinations. Then, for each edge in this tree, the scheme routes a message through a random intermediate node, chosen independently of the set of multicast requests. The intermediate node is chosen in the vicinity of the corresponding edge such that congestion is reduced without stretching the routes by more than a constant factor. We first evaluate the scheme analytically, showing that it achieves a theoretically optimal level of congestion. We then evaluate the scheme in simulation, showing that its performance is also good in practice.
- I. Abraham, D. Dolev, and D. Malkhi. LLS: A locality aware location service for mobile ad hoc networks. In Proc. 2nd Workshop on Foundations of Mobile Comp. (DIALM-POMC), pages 75--84, 2004. Google Scholar
Digital Library
- I. Abraham, C. Gavoille, and D. Ratajczak. Compact multicast routing. In Proc. of 23rd Symp. on Distributed Computing (DISC), pages 364--378, 2009. Google ScholarDigital Library
- S. Arora. Polynomial time approximation scheme for Euclidean TSP and other geometric problems. In Proc. 37th Symp. on Found. of Comp. Sc. (FOCS), pages 2--11, 1996. Google ScholarDigital Library
- L. Barrière, P. Fraigniaud, L. Narayanan, and J. Opatrny. Robust position-based routing in wireless ad hoc networks with irregular transmission ranges. Wireless Communication and Mobile Computing, 3:141--153, 2003. Google ScholarDigital Library
- Y. Bartal and S. Leonardi. On-line routing in all-optical networks. Theor. Comp. Sc., 221(1--2):19--39, 1999. Google ScholarDigital Library
- P. Bose, P. Morin, I. Stojmenovic, and J. Urrutia. Routing with guaranteed delivery in ad hoc wireless networks. In Proc. Discrete Algorithms and Methods for Mobility (DIALM), pages 48--55, 1999. Google ScholarDigital Library
- J. Broch, D. Maltz, D. Johnson, Y.-C. Hu, and J.Jetcheva. A performance comparison of multi-hop wireless ad hoc network routing protocols. In Mobile Computing and Networking, pages 85--97, 1998. Google ScholarDigital Library
- C. Busch, M. Magdon-Ismail, and J. Xi. Oblivious routing on geometric networks. In Proc. 17th Symp. on Parallelism in Algorithms and Architectures (SPAA), pages 316--324, 2005. Google ScholarDigital Library
- C. Busch, M. Magdon-Ismail, and J. Xi. Optimal oblivious path selection on the mesh. In Proc. 19th Int. Parallel and Distributed Processing Symp. (IPDPS), 2005. Google ScholarDigital Library
- R. Flury and R. Wattenhofer. MLS: An efficient location service for mobile ad hoc networks. In Proc. 7th Symp. on Mobile Ad Hoc Networking and Computing (MOBIHOC), pages 226--237, 2006. Google ScholarDigital Library
- J. Gao and L. Zhang. Trade-offs between stretch factor and load-balancing ratio in routing on growth-restricted graphs. IEEE Trans. on Parallel and Distributed Systems, 20(2):171--179, 2009. Google ScholarDigital Library
- D. B. Johnson and D. A. Maltz. Dynamic source routing in ad hoc wireless networks. In Mobile Computing, volume 353, chapter 5. 1996.Google ScholarCross Ref
- B. Karp and H. Kung. GPSR: greedy perimeter stateless routing for wireless networks. In Proc. 6th Int. Conf. on Mobile Computing and Networking (MOBICOM), pages 243--254, 2000. Google ScholarDigital Library
- P. Kolman and C. Scheideler. Improved bounds for the unsplittable flow problem. J. of Algorithms, 61(1):20--44, 2006. Google ScholarDigital Library
- E. Kranakis, H. Singh, and J. Urrutia. Compass routing on geometric networks. In Proc. 11th Canadian Conference on Computational Geometry, pages 51--54, 1999.Google Scholar
- F. Kuhn, R. Wattenhofer, and A. Zollinger. Ad-hoc networks beyond unit disk graphs. Wireless Networks, 14(5):715--729, 2008. Google ScholarDigital Library
- F. Kuhn, R. Wattenhofer, and A. Zollinger. An algorithmic approach to geographic routing in ad hoc and sensor networks. IEEE/ACM Transactions on Networking, 16:51--62, 2008. Google ScholarDigital Library
- F. Li and Y. Wang. Circular sailing routing for wireless networks. In Proc. 27th Int. Conf. on Computer Communications (INFOCOM), pages 1346--1354, 2008.Google ScholarCross Ref
- J. Li, J. Jannotti, D. De Couto, D. Karger, and R. Morris. A scalable location service for geographic ad-hoc routing. In Proc. 6th Int. Conf. on Mobile Comp. and Networking (MOBICOM), pages 120--130, 2000. Google ScholarDigital Library
- B. Maggs, F. Meyer auf der Heide, B. Vöcking, and M. Westermann. Exploiting locality for networks of limited bandwidth. In Proc. 38th Symp. on Foundations of Comp. Science (FOCS), pages 284--293, 1997. Google ScholarDigital Library
- C. Maihofer. A survey of geocast routing protocols. Communications Surveys & Tutorials, 6(2):32--42, 2004. Google ScholarDigital Library
- C. E. Perkins and E. M. Royer. Ad hoc on-demand distance vector routing. In Proc. of 2nd IEEE Workshop on Mobile Computing Systems and Applications, pages 90--100, 1999. Google ScholarDigital Library
- L. Popa, A. Rostamizadeh, R. M. Karp, C. H. Papadimitriou, and I. Stoica. Balancing traffic load in wireless networks with curveball routing. In Proc. 8th Symp. on Mobile Ad Hoc Networking and Computing (MOBIHOC), pages 170--179, 2007. Google ScholarDigital Library
- H. Räcke. Optimal hierarchical decompositions for congestion minimization in networks. In Proc. 40th Symp. on Theory of Computing (STOC), pages 255--263, 2008. Google ScholarDigital Library
- H. Rckeä. Survey on oblivious routing strategies. In Proc. 5th Conf. on Computability in Europe (CiE), pages 419--429, 2009. Google ScholarDigital Library
- E. Royer and C. Toh. A review of current routing protocols for ad-hoc mobile wireless networks. In IEEE Personal Communications, volume 6, April 1999.Google ScholarCross Ref
- E. M. Royer and C. E. Perkins. Multicast operation of the ad hoc on-demand distance vector routing protocol. In Proc. 5th Int. Conf. on Mobile Comp. and Networking (MOBICOM), pages 207--218, 1999. Google ScholarDigital Library
- H. Takagi and L. Kleinrock. Optimal transmission ranges for randomly distributed packet radio terminals. IEEE Transactions on Communications, 32(3):246--257, 1984.Google ScholarCross Ref
- L. G. Valiant and G. J. Brebner. Universal schemes for parallel communication. In Proc. of 13th Symp. on Theory of computing (STOC), pages 263--277, 1981. Google ScholarDigital Library
- U. Varshney. Multicast over wireless networks. Communications of the ACM, 45(12):31--37, 2002. Google ScholarDigital Library
- J. Xie, R. R. Talpade, A. Mcauley, and M. Liu. AMRoute: ad hoc multicast routing protocol. Mobile Networks and Applications, 7(6):429--439, 2002. Google ScholarDigital Library
- X. Yu, X. Ban, W. Zeng, R. Sarkar, X. Gu, and J. Gao. Spherical representation and polyhedron routing for load balancing in wireless sensor networks. In Proc. 30th Int. Conf. on Computer Communications (INFOCOM), pages 621--625, 2011.Google ScholarCross Ref
Index Terms
- Oblivious low-congestion multicast routing in wireless networks
Recommendations
Oblivious routing on geometric networks
SPAA '05: Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architecturesWe study oblivious routing in which the packet paths are constructed independently of each other. We give a simple oblivious routing algorithm for geometric networks in which the nodes are embedded in the Euclidean plane. In our algorithm, a packet path ...
Context-aware multicast routing scheme for disruption tolerant networks
PE-WASUN '06: Proceedings of the 3rd ACM international workshop on Performance evaluation of wireless ad hoc, sensor and ubiquitous networksDisruption Tolerant Networks (DTNs) are emerging solutions to networks that experience frequent network partitions and large end-to-end delays. Several schemes have been proposed for multicast routing in DTNs assuming the availability of different ...
A location prediction based routing protocol and its extensions for multicast and multi-path routing in mobile ad hoc networks
This paper discusses a new location prediction based routing (LPBR) protocol for mobile ad hoc networks (MANETs) and its extensions for multicast and multi-path routing. The objective of the LPBR protocol is to simultaneously minimize the number of ...
Comments