본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

Mobility-Aware Mesh Construction Algorithm for Low Data-Overhead Multicast Ad Hoc Routing

Ruiz, Pedro M.   Antonio F., Gomez-Skarmeta  
  • 초록

    We study the problem of controlling data overhead of mesh-based multicast ad hoc routing protocols by adaptively adding redundancy to the minimal data overhead multicast mesh as required by the network conditions. We show that the computation of the minimal data overhead multicast mesh is NP-complete, and we propose an heuristic approximation algorithm inspired on epidemic algorithms. In addition, we propose a mobility-aware and adaptive mesh construction algorithm based on a probabilistic path selection being able to adapt the reliability of the multicast mesh to the mobility of the network. Our simulation results show that the proposed approach, when implemented into ODMRP, is able to offer similar performance results and a lower average latency while reducing data overhead between 25 to 50% compared to the original ODMRP.


  • 주제어

    Ad hoc multicast routing .   mesh-based multicast .   minimal data overhead .   mobility-aware mesh construction.  

  • 참고문헌 (31)

    1. J. Moy, 'Multicast routing extensions for OSPF,' Computer Commun. ACM, vol. 37, no. 8, pp. 61-66, Aug. 1994 
    2. C. Cordeiro, H. Gossain, and D. Agrawal, 'Multicast over wireless mobile ad hoc networks: Present and future directions,' IEEE Network, no. 1, pp. 52-59, Jan. 2003 
    3. E.M. Royer and C.E. Perkins, 'Multicast operation of the ad hoc ondemand distance vector routing protocol,' in Proc. ACM/IEEE MOBI-COM'99, Seattle, WA, Aug. 1999, pp. 207-218 
    4. C.K. Toh, G. Guichala, and S. Bunchua, 'ABAM: Ondemand associativity-based multicast routing for mobile ad hoc networks,' in Proc. IEEE VTC 2000, Boston, MA, Sept. 2000, pp. 987-993 
    5. J.G. Jetcheva et al., 'A simple protocol for multicast and broadcast in mobile ad hoc networks,' Internet Draft, work in progress, draft-ietf-manet-simple-mbcast-0l.txt, July 2001 
    6. B.M. Waxman, 'Routing of multipoint connections," IEEE J. Select. Areus Commun., vol. 6, no. 9, pp. 1617-1622, Dec. 1998 
    7. L. Kou, G. Markowsky, and L. Berman, 'A fast algorithm for Steiner trees,' Acta Informatica, vol. 2, no. 15, pp. 141-145, 1981 
    8. S.E. Deering and D.R. Cheriton, 'Multicast routing in datagram inter networks and extended LANs,' Trans. Computer Sys. vol. 8, no. 2, pp. 85-110, May 1990 
    9. J.G. Jetcheva and D.B. Johnson, 'Adaptive demand-driven multicast routing in multi-hop wireless ad hoc networks,' in Proc. ACM MobiHoc 2001, Long Beach, CA, Oct. 2001, pp. 33-44 
    10. H. Lim and C. Kim, 'Multicast tree construction and flooding in wireless ad hoc networks,' in Proc. 3rd ACM Int. Workshop Modeling, Analysis, and Simulation of Wireless and Mobile Systems, Boston, MA, USA. Aug. 2000, pp. 61-68 
    11. D. Chen et al., 'Approximations for Steiner trees with minimum number of Stiner points,' Theoretical Computer Science, no. 262, pp. 83-99, 2001 
    12. S. Lee and C. Kim, 'Neighbor supporting ad hoc multicast routing protocol,' in Proc. 1st ACM MobiHoc 2000, Boston, MA, USA, 2000, pp. 37-44 
    13. L. Ji and M.-S. Corson, 'Differential destination multicast: A MANET multicast routing protocol of small groups,' in Proc. IEEE INFOCOM 200l, Anchorage, Alaska, Apr. 2001, pp. 1192-1202 
    14. The Monarch Project, 'Mobile networking architectures,' Rice University, available at http://www.monarch.cs.rice.edu/ 
    15. C.W. Wu, Y.C. Tay, and C.K. Toh, 'Ad hoc multicast routing protocol utilizing increasing idnumbers (AMRIS) functional specification,' Internet Draft, work in progress, draft-ietf-manet-amris-spec-00.txt, Nov. 1998 
    16. E. Bommaiah et aI., 'AMRoute: Ad hoc multicast routing protocol,' Internet Draft, work in progress, draft-talpade-manet-amroute-OO.txt, Aug. 1998 
    17. A. Zelikovsky, 'An$\frac{6}{11}$-approximation algorithm for the network Steiner problem,' Algorithmica, no.9, pp.463-470, 1993 
    18. K. Fall and K. Varadhan, 'Ns notes and documentation,' The VINT Project, UC Berkeley, LBL, USC/ISI, and Xerox PARC, Nov. 2003 
    19. J. Plesnik, 'The complexity of designing a network with minimum diameter,' Networks, no.11, pp.77-85, 1981 
    20. J. Boleng, W. Navidi, and T. Camp, 'Metrics to enable adaptive protocols for mobile ad hoc networks,' in Proc. Int. Conf. Wireless Networks (ICWN 2002), Las Vegas, NV, June 2002, pp. 293-298 
    21. S. Deering et aI., 'The PIM architecture for widearea multicast routing,' IEEElACM Trans. Networking, vol. 4, no. 2, pp. 153-162, Apr. 1996 
    22. S. Deering, 'Multicast routing in a datagram internetwork,' Ph.D. Thesis, Electrical Engineering Dept., Stanford University, Dec. 1991 
    23. L. Ji and S. Corson, 'A lightweight adaptive multicast algorithm,' in Proc. IEEE GLOBECOM'98, Sydney, Australia, Nov. 1998, pp. 1036-1042 
    24. T. Ballardie, P. Francis, and J. Crowcroft, 'Core based trees (CBT) - an architecture for scalable inter-domain multicast routing,' in Proc. ACM SIGCOMM'93, San Francisco, CA, Oct. 1993, pp. 85-95 
    25. S.J. Lee, W. Su, and M. Gerla, 'Ondemand multicast routing protocol in multihop wireless mobile networks,' ACM/Kluwer Mobile Networks and Applications, vol. 7, no. 6, pp. 441-452, Dec. 2002 
    26. J. J. Garcia Luna Aceves and E.-L. Madruga, 'The coreassisted mesh protocol,' IEEE J. Select. Areas Commun., vol. 17, no. 8, pp. 1380-1394, Aug. 1999 
    27. P. Sinha, R. Sivakumar, and V. Bharghavan, 'MCEDAR: Multicast core extraction distributed ad hoc routing,' in Proc. IEEE Wireless Commun.and Networking Conf., New Orleans, LA, Sept. 1999, pp. 1313-1319 
    28. X. Jia, 'A distributed algorithm of delay-bounded multicast routing for multimedia applications in wide area networks,' IEEElACM Trans. Networking, vol. 6, no. 6, pp. 828-837, Dec. 1998 
    29. K. Bharath-Kumar and J.M. Jaffe, 'Routing to multiple destinations in computer networks,' IEEE Trans. Commun., vol. 3, no. 31, pp. 343-351, 1983 
    30. R.-M. Karp, 'Reducibility among combinatorial problems,' in Complexity of Computer Computations, New York: Plenum Press, 1975, pp. 85-103 
    31. S. Evan, 'Graph algorithm,' Computer Science Press, 1979, pp. 204-209 

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기