مسیریابی شبکه¬های کامپیوتری چندبخشی با استفاده از الگوریتم ژنتیک و کولونی مورچه
محورهای موضوعی : عمومى
محمد پورمحمود آقابابا
1
*
,
امین بهادرانی باغبادرانی
2
1 - هیئت علمی
2 - فناوری اطلاعات،دانشکده مهندسی کامپیوتر،دانشگاه صنعتی ارومیه
کلید واژه: فناوري الگوریتم ژنتیک, کولونی مورچه, مسیریابی, شبکه¬های کامپیوتری ,
چکیده مقاله :
با توجه به رشد و توسعه شبکه های کامپیوتری، اهمیت موضوع مسیریابی پیش از گذشته شده است. اهمیت استفاده از شبکه-های چندبخشی را امروزه نمی توان نادیده گرفت. بسیاری از برنامه های چندرسانه ای نیاز به ارسال یک بسته از یک منبع به چندین مقصد، از طریق یک شبکه ارتباطی دارند. برای پشتیبانی از چنین برنامه هایی نیازمند ایجاد یک درخت چندبخشی بهینه می باشیم، که نشان دهنده مسیرهای بهینه دستیابی ازیک منبع ارسال کننده به چندین مقصد مورد نظر است. دستیابی به یک درخت بهینه جهت مسیریابی، از جمله مسائلی است که دارای پیچیدگی فراوانی می باشد. در این مقاله به دنبال ارائه روشی برای مسیریابی در شبکه های چندبخشی، با توجه به پارامترهایی مانند هزینه و تأخیر می باشیم. همچنین این مقاله اهمیت ویژه ای به این موضوع داده است که هر یک از پارامترهای ذکر شده جهت مسیریابی، برای بسته‌های متفاوت دارای ارزش‌های متفاوت نیز می باشند و به تناسب ارزش هریک از این پارامترها، درخت‌های مسیریابی چندبخشی بهینه‌ای ایجاد می شود. جهت دستیابی به این هدف ازدو الگوریتم ژنتیک و الگوریتم کولونی مورچه‌ها استفاده می‌شود. نتایج به دست آمده از شبیه سازی نشان داده است که الگوریتم‌های ارائه شده با توجه به تناسب بسته‌ها، توانایی ایجاد درخت های چندبخشی بهینه ای را دارا می باشند.
With the growth and development of computer networks, the importance of routing has become a thing of the past. The importance of using multi-sectoral networks cannot be ignored today. Many multimedia applications require sending a packet from one source to multiple destinations over a communication network. To support such programs, you need to create an optimal multipart tree , Which indicates the optimal routes to reach from one sender source to several desired destinations.
1.V.P. Kompella, J.C. Pasquale, G.C. Polyzos, multicast routing for multimedia communication, IEEE/ACM Trans. Networking 1 (3) (1993) 286±292.
2.Wang H.,Shuaili Z., multicast routing for delay variation bound using a modified ant colony algoritm, Journal of Network and computer Applications,32 258-272,2012
3.Ajay Kumar Yadav, SachinTripathi. Design of efficient multicast routing protocol using limited flooding mechanism. International Conference on Microelectronics. Jan. 2016
4.T. Chiang, C. Liu, Y. Huang, A near-optimal multicast scheme for mobile ad hocnetworks using a hybrid genetic algorithm, Expert Systems with Applications (2006).
5.G.N. Rouskas, I. Baldine, multicastrouting with end-to-end delay and delay variationconstraints, IEEE Trans. Commun. 15 (3) (1997) 346±356.
6.Drake Doratha E, Hougardy Stefan. On approximation algorithms for the terminal Steiner tree problem. Inform Process Lett 2014;89.
7.AshemaHasti; U. S. PandeyAnalysis of performance of multicasting routing protocol MAODV for QoS parameters using NS2. IEEE Conference Publications. 2015
8.R. Bhattacharya; P. VenkateswaranS. K. Sanyal; R. Nandi.Genetic algorithm based efficient routing scheme for multicast networks. IEEE International Conference on Personal Wireless Communications, 2015.
9.Rouskas, G. N., &Baldine, multicastrouting with end-to-end delay anddelay variation constraints. IEEE Journal on Selected Areas in Communications, 2014, 346–356
10.Chang WookAhn; R. S. Ramakrishna ; A genetic algorithm for shortest path routing problem and the sizing of populations . IEEE Journals & Magazines, 2013
11.Hwang RH, Do WY, Yang SC. multicastrouting based on genetic algorithms. J Inform SciEng.2000
12.Bhattacharya R, Venkateswaran P, Sanyal SK, Nandi R. Genetic algorithm based efficient outing scheme for multicastnetworks.Computer Communications. 2015
13.A.T. Haghighat, K. Faez, M. Dehghan, A. Mowlaei, Y. Ghahremani, GA-based heuristic algorithms for bandwidth-delay-constrained least-cost multicastrouting, Computer Communications. 2008.
14.X. Wang, J. Cao, H. Cheng, M. Huang, QoSmulticastrouting for multimedia group communications using intelligent computational methods, Computer Communications. 2015.
15.Hamdan M, El-Hawary ME. Multicastrouting with delay and delay variation constraints using genetic algorithm. CanadConf Elect ComputEng 2014.
16.Z. Wang, B. Shi, E. Zhao, Bandwidth-delay-constrained least-cost multicastrouting based on heuristic genetic algorithm, Computer Communications. 2011.
17.Hua Chen, Baolin Sun. multicastrouting optimization algorithm with bandwidth and delay constraints based on GA. J Commun Computer. 2015.
18.Noor M. Asraf; Raja N. Ainon; PhangKeatKeong . QoS Parameter Optimization Using Multi-Objective Genetic Algorithm in MANETs .J Commun Computer. 2014.
19.Dorigo ,M. and Stutzle ,T., The ant colony optimization metaheuristic:algoritms ,application and advances. volume 57 of international series in Operations Resarch and management & local search.Master of science thesis,University of Edinburgh,2003.
20.Li-dong Hou; Wen Zhang , Multi- Objective Multicast Routing based on Ant Ant Colony system, International Conference on Information Management, Innovation Management and Industrial Engineering, 2013.
21.Younes A. A genetic algorithm for finding the k shortest paths in a networks. Egypt Inform J 2010;11(2).
22.CE Perkins, EM Royer, SR Das, Ad hoc on demand distance vector (AODV) routing, in Proceedings of IEEE Workshop on Mobile Computing Systems and Applications (WMCSA’99), New Orleans, LA, USA (1999).
23.PerumalsamyDeepalakshmi, ShanmugasundaramRadhakrishnan, An ant colony-based multi objective quality of service routing for mobile ad hoc networks (AMQR), EURASIP Journal on Wireless Communication and Networking,2011