Routing of Multipartite Computer Networks Using Ant Genetic Algorithm
Subject Areas : General
Mohammad Pourmahmood Aghababa
1
*
,
amin bahadorani baghbaderani
2
1 -
2 -
Keywords: Genetic algorithm technology, ant colony, routing, computer networks,
Abstract :
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
فصلنامه علمي- پژوهشي فناوري اطلاعات و ارتباطات ایران | سال نهم، شماره‌هاي 31 و 32، بهار و تابستان 1396 |
|
مسیریابی شبکههای کامپیوتری چندبخشی1 با استفاده از الگوریتم ژنتیک و کولونی مورچه
*محمد پورمحمودآقابابا ** امین بهادرانی باغبادرانی
* عضو هیئت علمی گروه برق،دانشکده مهندسی برق،دانشگاه صنعتی ارومیه، ایران
** فارغ التحصیل کارشناسی ارشد فناوری اطلاعات،دانشکده مهندسی کامپیوتر،دانشگاه صنعتی ارومیه
تاریخ دریافت:24/03/1395 تاریخ پذیرش: 07/11/1396
چكيده
با توجه به رشد و توسعه شبکههای کامپیوتری، اهمیت موضوع مسیریابی پیش از گذشته شده است. اهمیت استفاده از شبکههای چندبخشی را امروزه نمیتوان نادیده گرفت. بسیاری از برنامههای چندرسانهای نیاز به ارسال یک بسته از یک منبع به چندین مقصد، از طریق یک شبکه ارتباطی دارند. برای پشتیبانی از چنین برنامههایی نیازمند ایجاد یک درخت چندبخشی بهینه
میباشیم، که نشاندهنده مسیرهای بهینه دستیابی ازیک منبع ارسالکننده به چندین مقصد مورد نظر است. دستیابی به یک درخت بهینه جهت مسیریابی، از جمله مسائلی است که دارای پیچیدگی فراوانی میباشد. در این مقاله به دنبال ارائه روشی برای مسیریابی در شبکههای چندبخشی، با توجه به پارامترهایی مانند هزینه و تأخیر میباشیم. همچنین این مقاله اهمیت ویژهای به این موضوع داده است که هر یک از پارامترهای ذکر شده جهت مسیریابی، برای بستههای متفاوت دارای ارزش‌های متفاوت نیز میباشند و به تناسب ارزش هریک از این پارامترها، درختهای مسیریابی چندبخشی بهینهای ایجاد میشود. جهت دستیابی به این هدف ازدو الگوریتم ژنتیک و الگوریتم کولونی مورچهها استفاده میشود. نتایج به دست آمده از شبیهسازی نشان داده است که الگوریتمهای ارائه شده با توجه به تناسب بسته‌ها، توانایی ایجاد درختهای چندبخشی بهینهای را دارا میباشند.
واژه‌های کلیدی: فناوري الگوریتم ژنتیک، کولونی مورچه، مسیریابی، شبکههای کامپیوتری
|
|
[1] Multicast Computer Network
1- مقدمه
شبکههای کامپیوتری گروهی از کامپیوترهای متصل شده به یکدیگر هستند که توانایی تبادل اطلاعات با یکدیگر را دارا میباشند. از بررسي و قضاوت در مورد تحقيقاتي که هماکنون صورت میپذيرد ميتوان به اين نتيجه رسيد که مسيريابي در اينترنت جزء اکثر مواردي است که رغبت بدان همچنان تنزل نيافته است. مخصوصا مسيريابي مبتني برکيفيت سرويس و خدمات درسال‌هاي اخيرگواه صحت اين ادعا میباشد .با به وجود آمدن تکنولوژی‌های جدید و به طور خاص شبکههای با ظرفیت بالا،
انعطافپذیری بیشتری جهت مسیریابی مورد نیاز است. تجارتالکترونیک، یادگیری از راه دور، پخش فیلم درخواستی از راه دور، سرویس اطلاعات جهانی و بسیاری از سرویس‌های دیگر، بار حجیمی را به شبکه وارد میکنند، که در صورت عدم مدیریت صحیح مشکلات متعددی را برای شبکه بوجود می‌آورند. این موضوع یک محیط جدید تحقیقاتی است که با پیچیدگی‌های فراوان تکنیکی و اقتصادی روبرو است. در سال‌های اخیر موضوع مسیریابی مابین گرههای شبکههای مختلف یکی از موضوعات شناخته شده در زمینه شبکههای کامپیوتری میباشد[1]. آنچه که ایده مسیریابی را میسر می‌سازد، پیدا کردن مسیری بهینه جهت رساندن بسته مورد نظر به مقصد مورد نظر، با در نظر گرفتن معیارهایی مختلف کیفیت خدمات1 میباشد.
مسیریابی چندبخشی مسأله یافتن تعدادی مسیر از یک گره منبع به سمت چند گره مقصد میباشد[2]. در تعیین مسیرهای بهینه ما بین گره منبع وگره‌های مقصد پارامترهای متفاوتی مورد توجه قرار میگیرند. برخی از این پارامترها پویا هستند به این معنا که با گذشت زمان متغیر میباشند مانند: ظرفیت باقیمانده در هر مسیر ارتباطی، چراکه ظرفیت مسیرهای ارتباطی معمولا ثابت است در نتیجه به مرور با افزایش تعداد مسیرهایی که از یک خط عبور میکنند، ظرفیت باقیمانده در آن مسیر و یا به عبارتی ظرفیت خالی مسیر به مرور کاهش می‌یابد. برخی دیگر از پارامترهای موثر در انتخاب یک مسیر ایستا هستند به این معنا که با گذشت زمان بدون تغییر می‌مانند و یا تغییرات در آنها بسیار به کندی صورت میگیرد. از جمله این پارامترها میتوان به هزینه یک مسیر اشاره کرد[3].
از جمله مزایای مسیریابی چندبخشی آن است که تنها یک رونوشت از پیام ارسالی بر روی مسیرارتباطی به اشتراک گذاشته شده مابین گرههای مقصد قرار میدهد و این امر سبب صرفه جویی در منابع شبکه میشود[4].
مسیریابی چندبخشی در لایه شبکه انجام میگیرد که برای این مسیریابی الگوریتمهای بسیاری مورد بررسی قرار گرفتهاند که هر یک از این الگوریتمها از پارامترهای مختلفی جهت بهینهکردن مسیریابی خود استفاده می‌نمایند. از عمده مسأله‌هایی که در زمان انجام سرویس چندبخشی مطرح میشود ایجاد درخت چندبخشی بهینه میباشد چراکه این موضوع بر کیفیت سرویس و درصد استفاده از شبکه بسیار تاثیر دارد[5]. از جمله راهکارهای اولیه که برای حل این مشکل ارائه شده است، راهکارهایی هستند که با هدف بهینهکردن یک پارامتر مسیریابی جهت ایجاد درخت مسیریابی چندبخشی انجام میشدند. به عنوان مثال میتوان پارامتر هزینه را عنوان کرد[6،3]. راه کارهای دیگری در جهت بهبود این مشکل معرفی گردید مانند مراجع[8،7]، که راهکار پیشنهادی این الگوریتمها تمرکز بر پارامترهای کیفیت سرویس و ارزیابی تاخیرهای پایانی انتقالات2میباشد.
اغلب پروتکلهای مسیریابی از یک پارامتر جهت پیدا کردن مسیر بهینه استفاده می‌نمایند[9]. آنچه که باید مورد نظر قرار گیرد آن است که استفاده از چند پارامتر جهت مسیریابی، میتواند سبب بهبود مسیر بهینه در مسیریابی شود[10].
در سال‌های اخیر الگوریتمهای ژنتیک3 و کولونی مورچههای4بسیاری در جهت حل مسائل مسیریابی چندبخشی ارائه شده است. آنچه که این دسته الگوریتمها را از راه کارهای گذشته متمایز میکند آن است که، با استفاده از این الگوریتمها میتوان به صورت ساده‌تر، پارامترهای بیشتری را به صورت همزمان در انجام مسیریابی دخالت داد، که این امر موجب دسترسی به راهحلهای بهتر خواهد شد. به عنوان نمونه از الگوریتمهای ژنتیک به کاربرده شده در زمینه مسیریاب چندبخشیمی توان به مواردی همانند مراجع [11]، [12]، [13]، [14] و [15] اشاره نمود، که اغلب در آنها، تنها از یک پارامتر جهت تصمیمگیری در عمل مسیریابی استفاده شده است. نتایج به دست آمده از تحقیقات نشان داده است که استفاده از الگوریتم ژنتیک و کولونی مورچهها در مسیریابی در مقایسه با راهکارهای ارائه شده قبلی، سبب دسترسی به راهحلهای بهینهتری خواهد شد[16] و [17].
راهکارهای ارائه شده در زمینه مسیریابی ذکر شده در پاراگراف قبل، اغلب پارامترهای مختلفی مانند: تأخیر، هزینه ایجاد درخت، پهنای باند وغیره را جهت مسیریابی به کار میبرند. اما آنچه که چندان مورد توجه این راهکارها قرار نگرفته است، آن است که هر یک از این پارامترها برای بستههای مختلف ارسالی دارای ارزش‌های متفاوتی میباشند. به عنوان مثال پارامتر تأخیر در ارسال بستههای ویدو در پخش آنلاین بسیار مهم میباشد چراکه تأخیر زیاد موجب نارضایتی کاربران و در نهایت کاهش QoS خواهد شد.
جهت بهبود عمل مسیریابی، میتوان در ابتدا بستههای انتقالی توسط شبکه را با توجه به نوعشان، کلاسبندی نمود و سپس با توجه به کلاس هر بسته ارزش هر یک از پارامترهای تصمیمگیری در عمل مسیریابی را مشخص نمود.
این مقاله به دنبال ارائه روشی برای ایجاد درخت چندبخشی بهینه با توجه به پارامترهایی مانند تأخیر و هزینه ارسال اطلاعات به صورت همزمان میباشد. آنچه که در این مقاله بسیار مورد اهمیت قرار گرفته است آن است که هر یک از پارامترهای نام برده شده، در عمل مسیریابی برای بستههای مختلف دارای ارزش‌های متفاوتی میباشند و با توجه به این موضوع میتوان زمینه بهتری را جهت تضمین QoS فراهم نمود. استفاده از ارزش‌های متفاوت برای پارامترهای تصمیمگیری در زمینه مسیریابی سبب بهبود استفاده از منابع شبکه نیز میگردد.
در این مقاله راهکار ارائه شده با استفاده از دو الگوریتم کولونی مورچهها و الگوریتم ژنتیک پیادهسازی شده است. نوآوری اصلی این مقاله ارائه الگوریتمهای ژنتیک و کولونی مورچه برای حل مساله مسیریابی بهینه در شبکههای کامپیوتری چند بخشی میباشد. در این راستا، توابع شایستگی مناسب با در نظر گرفتن معیارهایی مانند تاخیر و کیفیت سرویس تعریف میشوند. نوآوری دیگر این تحقیق، ارائه الگوریتم کولونی اصلاح شده برای حل مساله مسیریابی میباشد. همچنین جهت اجرای بهتر عمل مسیریابی، پارامتری به نام 
معرفی خواهیم کرد که دارای مقداری اختیاری است و ارزش آن با توجه به تاثیرگذاری هریک از پارامترهای تصمیمگیری در امر مسیریابی تعیین میشود. همچنین در حل مسئله با استفاده از الگوریتم کولونی مورچهها تابع احتمالی معرفی خواهد شد که نشاندهنده احتمال انتخاب گره بعدی جهت ادامه مسیر میباشد. در این الگوریتم برای هریک از پارامترهای تصمیمگیری در مسیریابی یک مقدار فرمون اولیه در نظر گرفته شده است که مقادیر فرمونهای هریک از مسیرها در هر تکرار از الگوریتم به روزرسانی میشود. نتایج شبیهسازیها نشان میدهند که الگوریتم پیشنهادی کارآیی مناسبی را در مقایسه با سایر روشهای موجود دارد.
در ادامه در بخش 2 به توضیح و بیان مسئله میپردازیم. در بخش 3 توضیح مختصری ازالگوریتم ژنتیک پیادهسازی شده ارائه میشود. دربخش 4 الگوریتم کولونی مورچهها بررسی میشود. در بخش 5 نتایج به دست آمده حاصل از اجرای الگوریتمهای ذکر میشود و در بخش 6 نتایج به دست آمده از مقاله، بیان میشوند.
2- توضیح مساله
یک شبکه کامپیوتری معمولا به صورت یک گراف وزندارG = (N, E) ، نمایش داده میشود که در آن N نشان دهنده گرهها وE نشاندهنده مسیرهای ارتباطی شبکه میباشد.|N| و |E|، نشاندهنده تعداد گرهها و تعداد مسیرها میباشند[18]. هر مسیر دارای مقداری هزینه
میباشد. مقدار هزینه‌های مربوط به هر مسیر به صورت یک ماتریس هزینه C = [Cij] نشان داده میشود، که در آن Cij نشاندهنده هزینه مربوط به مسیر(i, j) میباشد. همچنین دارای یک ماتریس تاخیر D = [dij] که در آن dij نشاندهنده تأخیر انتقال یک بسته بر روی مسیر(i, j) میباشد[18]. مسئله مطرح شده در این مقاله یافتن یک درخت بهینه چندبخشی میباشد، به گونهای که مسیر ایجاد شده از گره منبع به هر گره مقصد به صورت بهینه باشد. مسئله دارای یک گره منبع( n0 ) و k گره مقصد(n1,n2,…,nk) میباشد. هدف بهینهسازی مسیریابی با توجه به دو پارامتر هزینه و تأخیر است. درخت چندبخشی به صورت T = (NT, ET) نشان داده شده است، که در آن NT زیرمجوعهای از N و ET زیرمجموعهای از E میباشد. در نتیجه درخت چندبخشی به دست آمده حاصل اجتماع گره منبع و گرههای مقصد است. مسیر موجود از گره منبع به هر گره مقصد را به صورت Pk (n0, d) نشان میدهیم که در آن n0 گره منبع و d یکی از گرههای مقصد است[17].
همانطور که عنوان شد، یکی از پارامترهای در نظر گرفته شده، جهت مسیریابی هزینه میباشد. هزینه به عوامل مختلفی مانند: طول مسیر، نوع مسیر وغیره بستگی دارد. مسلماً هرچه طول یک مسیر بیشتر باشد هزینه آن نیز بیشتر خواهد بود. همچنین نوع مسیر در هزینه آن نیز تاثیرگذار خواهد بود. علاوه بر پارامترهای مربوط به مسیرهای موجود در شبکه پارامترهای دیگری نیز در تعیین تابع هزینه و انتخاب مسیر بهینه تاثیرگذار هستند که این پارامترها مربوط به نوع درخواست ارسالی میباشند. به این معنا که مسیر بهینهای که قرار است از گره منبع به گره مقصد تشکیل شود به منظور انتقال چه نوع دادهای مورد استفاده قرار خواهد گرفت. پس در نتیجه
درخواستهای ورودی را با توجه به نوعشان و نیازهایشان به چندین کلاس دستهبندی میکنیم. به عنوان مثال در جدول 1 درخواستهای ورودی با توجه به پارامترهایی مانند هزینه، تأخیر و غیره ، به چندین دسته کلاس
دستهبندی میشوند که برای هر کلاس یک مقدار به عنوان مثال در نظر گرفته شده است. مقدار را در مسیریابی شبکههای حقیقی را میتوان با توجه به اهمیت پارامترهای مسیریابی مشخص نمود.
جدول1-کلاس درخواستها
کلاس درخواست ها | اهمیت تأخیر | ارزش هزینه |
|
A | بسیار زیاد | بسیار کم | 0.85 |
B | زیاد | کم | 0.7 |
C | کم | بسیار زیاد | 0.3 |
3- آمادهسازی الگوریتم ژنتیک
الگوریتمهای ژنتیک یک روش جستجوی مؤثر در فضاهای بسیار وسیع و بزرگ است که در نهایت منجر به
جهتگیری به سمت پیدا کردن یک جواب بهینه میگردد که شاید نتوان در مدت زمان زندگی یک فرد به آن جواب بهینه دست یافت. الگوریتمهای ژنتیک تفاوت بسیار زیادی با روشهای بهینهسازی قدیمی دارند. در این الگوریتمها باید فضای طراحی5 به فضای ژنتیک6تبدیل شود. بنابراین الگوریتمهای ژنتیک با یک سری متغییرهای کد شده کار میکنند. مزیت کار با متغییرهای کد شده در این است که اصولاً مدها قابلیت تبدیل فضای پیوسته به فضای گسسته را دارند[12]. یکی از تفاوت‌های اصلی روش الگوریتم ژنتیک با روشهای قدیمی بهینهسازی در این است که الگوریتم ژنتیک با جمعیت یا مجموعهای از نقاط در یک لحظه خاص کار میکند، در حالی که در روشهای قدیمی بهینهسازی تنها براساس یک نقطه خاص انجام می‌شد و این بدین معناست که الگوریتم ژنتیکتعداد زیادی از راه حل‌ها را در یک زمان مورد پردازش قرار میدهد.
در این مقاله الگوریتم ژنتیک مورد نظر خود را در چهارگام پیادهسازی میکنیم:
1.تعریف و پیادهسازی تابع شایستگی2. آماده سازی جمعیت اولیه 3. ارزیابی تابع هزینه 4.انجام عمل تقاطع و جهش
1-3-تعریف و پیاده سازی تابع شایستگی
هدف اصلی مسئله پیدا کردن مجموعه ای از مسیرهای بهینه از یک گره منبع به سمت چند گره مقصد میباشد. همانطور که قبلا عنوان شد جهت مسیریابی و پیداکردن مسیرهای بهینه از دو پارامتر هزینه و تاخیر استفاده مینماییم.
تابع هزینه ایجاد درخت چندبخشی را به صورت زیر نشان خواهیم داد که در آن Cij هزینه هر اینک به کار برده شده در درخت چندبخشی میباشد.
(1) cost(T)=∑Cij cost(T)=∑Cij
تاخیر درخت چندبخشی را به شکل (2) نشان خواهیم داد. به عبارت دیگر میتوان گفت پارامتر تاخیر یک درخت چندبخشی، برابر ماکزیمم تاخیر ارسال یک بسته از نود منبع به یکی از نودهای مقصد میباشد.
(2) Delay(T)=max(∑ D(pk) ,pk€T) Delay(T)=max(∑ D(pk) ,pk€T)
تابع شایستگی را به صورت (3) نشان خواهیم داد که در آن ، با توجه به نوع کلاس درخواست مقدار میگیرد.
(3) 
یکی از پارامترهای تأثیرگذار در عمل مسیریابی و
تعیینکننده ارزش شایستگی، میباشد. در مسیریابی بستههایی که تأخیر برای آنها اهمیت ویژهای دارد، به مقدار بیشتری تخصیص داده میشود که اهمیت پارامتر تأخیر در مسیریابی بیشتر شود و به تناسب آن اهمیت هزینه ارسالی کاهش یابد.
2-3- آمادهسازی جمعیت اولیه
فرض نمایید که u={u1,u2,…,un} مجموعهای از گرههای مقصد ما میباشند و همچنین مجموعه p={p1,p2,…,pk} مجموعهای از کوتاهترین مسیرهای ما از گره منبع به سمت گرههای مقصد میباشند. جهت ایجاد کروموزومهای اولیه به صورت زیر عمل میکنیم:
3.2.1 کروموزوم اولیه ما شامل k ژن میباشد،k برابر تعداد گرههای مقصد، که هر یک از ژنها یک مسیر از گره منبع به سمت یکی از گرههای مقصد است. به عنوان ورودی مسئله، برای هر یک از گرههای مقصد N مسیر اولیه از گره منبع به سمت آنها داده شده است. بنابراین در زمان تشکیل کروموزوم یکی از این N مسیر را به صورت تصادفی انتخاب میکنیم و به عنوان یکی از ژنها قرار
میدهیم. شکل 1 نشاندهنده یک کروموزوم و ژنهای تشکیلدهنده آن میباشد.
شکل 1- کروموزوم و ژنهای تشکیلدهنده
G1: یکی از کوتاهترین مسیرهای داده شده به سمت اولین گره مقصد.
G2: یکی از کوتاهترین مسیرهای داده شده به سمت دومین گره مقصد.
Gn: یکی از کوتاهترین مسیرهای داده شده به سمت nامین گره مقصد.
3.2.2 گام اول را به تعداد جمعیت اولیه مورد نطر خود تکرار میکنیم تا اینکه کروموزومهای اولیه به دست آیند.
3-3- ارزیابی تابع هزینه
هدف از الگوریتم ژنتیک ایجاد درخت چندبخشی
میباشد، که با توجه به نوع درخواست بهینه باشد. در هر مرحله از تکرار این الگوریتم ما تابع شایستگی توضیح داده شده در (3) را برای هر یک از کروموزومها تشکیل میدهیم. سپس به مقایسه توابع شایستگی ایجاد شده با یکدیگر میپردازیم. به صورتی که کروموزومهایی که ارزش تابع شایستگی آنها بیشتر است، شانس بیشتری جهت حضور در تکرار بعدی الگوریتم پیدا می‌نمایند.
4-3- انجام عمل تقاطع وجهش
1-4-3- تقاطع
یکی از مراحل اصلی الگوریتمهای ژنتیک انجام عمل تقاطع میباشد. ایده اصلی انجام این عمل تبادل اطلاعات میان دو کروموزوم با هدف کشف مسیرهای بهتر و بهینهتر میباشد.[18] جهت انجام عمل تقاطع در ابتدا نرخ تقاطع را مشخص مینماییم و سپس گامهای زیر را انجام
میدهیم:
1.دو کروموزوم را به صورت تصادفی به عنوان دو والد خود انتخاب مینماییم.
2.به صورت تصادفی یک نقطه جداکننده انتخاب
مینماییم.
3.کروموزوم فرزند اول را به این صورت تشکیل میدهیم که، ژنهای اولیه آن تا نقطه جداکننده برابر با ژنهای والد اول میباشد و از نقطه جداکننده به بعد ژنهای آن از والد دوم میباشد.
4.فرزند دوم را همانند فرزند اول ایجاد می کنیم با این تفاوت که جای والدها با یکدیگر عوض میشود.
5.این عمل تکرار میشود تا به تعداد مورد نظر کروموزوم ایجاد شود. شکل 2 مراحل تقاطع را نشان میدهد. 
شکل 2- مراحل تقاطع
در زمان انجام عمل تقاطع جهت به دست آوردن کروموزومهای متفاوت، به کروموزومهای باقیمانده از مرحله قبل یک احتمال تخصیص داده میشود. به این صورت که کروموزومهایی که در مراحل قبلی جهت ایجاد فرزند انتخاب نشدهاند، شانس بیشتری برای انتخاب در این مرحله را دارا میباشند.
2-4-3- جهش
عمل جهش را به این صورت انجام میدهیم که، در ابتدا نرخ جهش را انتخاب میکنیم و در ادامه مراحل زیر را جهت انجام جهش دنبال میکنیم:
1. انتخاب یکی از کروموزومها به صورت تصادفی، به غیر از کروموزوم اول که بهینهترین کروموزوم میباشد.
2. انتخاب یک ژن کروموزوم انتخاب شده به صورت تصادفی. این ژن بیانکننده یک مسیر از گره منبع به سمت یکی از گرههای مقصد میباشد.
3.جایگزین کردن ژن دیگر به جای ژن انتخاب شده، به گونهای که ژن جدید بیانکننده مسیری متفاوت به همان گره مقصد میباشد.
4.سه مرحله اول الگوریتم جهش با توجه به نرخ جهش تکرار میشوند.
بعد از انجام عمل جهش،kتا از کروموزومهایی را که دارای شایستگی بهتری نسبت به بقیه کروموزومها میباشند را انتخاب مینماییم. با این عمل یک دور از تکرار الگوریتم به پایان میرسد و جهت دستیابی به جواب‌های بهینه الگوریتم تکرار میشود.
شکل 3- مراحل جهش
4-آمادهسازی الگوریتم کولونی مورچهها
الگوریتم بهینهسازی مورچهها اولین بار توسط
Marco Dorigo به عنوان تز دکتری مطرح شد و برای اولین بار برای حل مسئله فروشنده دوره‌گرد مورد استفاده قرار گرفت [19]. این نوع الگوریتمها گروهی از الگوریتمهای بهینهسازی برای مسائل ترکیبی میباشند که از رفتار اجتماعی مورچهها برای پیدا کردن کوتاهترین مسیر منتهی به غذا به لانه الهام گرفته شده است. بسیاری از مورچهها در هنگام حرکت در محیط اطراف خود مادهای به نام فرمون ترشح میکنند که برای سایر مورچهها قابل درک و جذاب است [20]. مورچهها در ابتدا به صورت تصادفی حرکت میکنند و در مسیر حرکت خود فرمون آزاد میکنند. با گذشت زمان فرمون آزاد شده کم کم تبخیر میشود. مورچهها با احتمال بیشتر مسیر دارای فرمون بیشتر را انتخاب میکنند. کوتاهترین مسیر تبخیر کمتری نسبت به مسیرهای دیگر دارد و این امر موجب آن میشود که در بازه زمانی کوتاهی میزان فرمون انباشته شده در آن مسیر بیشتر از مسیرهای دیگر شود و در نتیجه این اتفاق موجب همگرا شدن مورچههای بیشتری به مسیر کوتاهتر، با فرمون بیشتر میشود. باید به این نکته توجه کرد که اگرچه در الگوریتم کولونی مورچهها اکثر مورچهها از مسیر کوتاهتر حرکت میکنند اما این احتمال نیز وجود دارد که برخی از مورچهها مسیرهای طولانیتر را انتخاب کنند[19].
در ادامه به بررسی مراحل الگوریتم کولونی مورچهها جهت حل مسئله خود میپردازیم. به طور کلی الگوریتم کولونی مورچههای خود را در سه گام زیر پیاده سازی
میکنیم:
1-4- تعریف فرمون اولیه 2-4- تعریف تابع احتمال
3-4- به روزرسانی فرمون موجود در مسیر
1-4- تعریف فرمون اولیه
در مسئله مسیریابی برای هر مسیر ارتباطی مابین دو گره یک مقدار فرمون اولیه تعریف می شود که با گذشت زمان مقدار آن به روزرسانی میشود. میزان فرمون موجود در هر مسیر ارتباطی نشاندهنده میزان خوب بودن آن مسیر با توجه به تجربه به دست آمده از مورچههای دورهای قبل است. در این مقاله برای هر پارامتر تصمیمگیری در مسیریابی یک مقدار فرمون اولیه در نظر گرفته شده است.با توجه به آنکه ما در مقاله خود برای مسیریابی از دو پارامتر تاخیر و هزینه استفاده مینماییم، در نتیجه هر مسیر ارتباطی در شبکه ما دارای دو مقدار فرمون میباشد که یکی از این مقادیر برای تاخیر استفاده میشود و دیگری برای هزینه مورد استفاده قرار میگیرد.
2-4- تعریف تابع احتمال
در هر مرحله از اجرای الگوریتم، مورچهها مسیرهایی را ترجیح میدهند که دارای فرمون بیشتری میباشند. بنابراین هر مورچه گره بعدی را بر اساس یک قانون احتمال انتخاب میکند. در این مقاله تابع احتمال کلی به صورت زیر محاسبه میگردد:
(4) 
به طوری که n نشاندهنده گرههای همسایه گره iام
میباشد که ما بین آنها یک مسیر ارتباطی وجود دارد. مقدار 
با استفاده از رابطه زیر محاسبه میشود:
(5) 
به طوری که
نشاندهنده میزان احتمال انتخاب گره j با توجه به مقدار فرمون تاخیر میباشد که با استفاده از رابطه زیر محاسبه میشود.
(6) 
نشاندهنده مقدار فرمون تاخیر مسیر (i,j) میباشد.
نشاندهنده میزان احتمال انتخاب گره j با توجه به مقدار فرمون هزینه میباشد که با استفاده از رابطه زیر محاسبه میشود.
(7) 
نشاندهنده مقدار فرمون هزینه مسیر (i,j) میباشد.
3-4- به روزرسانی فرمون موجود در مسیر
آخرین مرحله از هر تکرار الگوریتم به روزرسانی فرمون موجود هر مسیر است.
اگر مسیر مورد نظر در مسیر انتخاب شده از گره منبع به گره مقصد وجود داشته باشد، مقدار فرمونهای تاخیر و هزینه آن با استفاده از روابط زیر به روزرسانی میشود:
(8) 
(9) 
بهطوری که
و 
به تریب نشاندهنده تاخیر و هزینه مسیر (i,j) میباشند و همچنین مقادیر 
و
به ترتیب نشاندهنده نرخ تبخیر فرمون تاخیر و فرمون هزینه می باشند.
اگر مسیر مورد نظر در مسیر انتخاب شده از گره منبع به گره مقصد وجود نداشته باشد، مقدار فرمونهای تاخیر و هزینه آن با استفاده از روابط زیر به روزرسانی میشود:
(10) 
(11) 
5- شبیهسازی و نتایج به دست آمده
الگوریتمهای ارائه شده را بر روی یک گراف شبکه با 20 نود که برگرفته شده از [21] میباشد را در نرمافزار Omnet++ جهت ارزیابی مورد بررسی قرار میدهیم. این برنامه یک شبیهساز شبکه است که برای مواردی از قبیل مدل‌سازی ترافیک شبکه، مدل‌سازی پروتکل، مدل‌سازی شبکههای صفبندی شده، مدل‌سازی میکروپروسسور و سایر سیستم‌های سختافزاری میتواند مورد استفاده قرار گیرد. هر مسیر موجود در گراف با کمک دو پارامتر
(D و C) نشان داده میشود، که در آن D نشاندهنده تأخیر و C نشاندهنده هزینه آن مسیر میباشد. در نتیجه به هر یک از مسیرها دو پارامتر تخصیص داده میشود که در این مسئله مقادیر تخصیص داده شده به آنها به صورت تصادفی میباشد. مقادیر اختصاص داده شده را میتوان در
شکلهای 4 و 5 مشاهده نمود. همچنین نتایج بدست آمده روش پیشنهادی با الگوریتمهایAODV] 22[ و AMQR]23[ جهت ارزیابی کارایی، مورد مقایسه قرار میگیرند. الگوریتم AMQR از جمله الگوریتمهای مسیریابی برای شبکههای حسگر بی سیم است که مفهوم کیفیت خدمات را در مسیریابی به کار گرفته است. در این الگوریتم تلاش بر این است که با کاهش تاخیر انتها به انتها طول عمر گرهها نیز افزایش یابد.
1 2 34 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 0 0 0 0 0 0 0 0 0 4 0 4 2 0 0 0 2 4 4 0
2 0 0 4 3 4 0 0 0 0 0 3 3 0 0 3 4 3 3 1 1
3 0 4 0 0 2 4 0 0 0 0 2 0 3 2 0 0 2 2 0 0
4 0 3 0 0 0 4 1 2 2 0 0 0 2 0 0 4 0 2 0 0
5 0 4 2 0 0 0 3 0 4 0 0 0 0 0 3 2 0 3 1 0
6 0 0 4 4 0 0 1 3 0 0 0 2 0 4 1 3 3 0 0 2
7 0 0 0 1 3 1 0 4 2 4 0 3 3 3 0 0 0 3 0 4
8 0 0 0 2 0 3 4 0 0 1 0 4 0 3 1 1 3 0 0 0
9 0 0 0 2 4 0 2 0 0 2 3 0 3 3 0 0 2 0 2 0
10 4 0 0 0 0 0 4 1 2 0 0 3 0 2 2 1 0 4 3 4
11 0 3 2 0 0 0 0 0 3 0 0 0 0 4 2 1 0 0 0 0
12 4 3 0 0 0 2 3 4 0 3 0 0 3 3 4 0 2 0 0 0
13 2 0 3 2 0 0 3 0 3 0 0 3 0 4 0 1 0 0 0 1
14 0 0 2 0 0 4 3 3 3 2 4 3 4 0 0 0 0 0 3 1
15 0 3 0 0 3 1 0 1 0 2 2 4 0 0 0 1 2 0 1 0
16 0 4 0 4 2 3 0 1 0 1 1 0 1 0 1 0 1 0 4 0
17 2 3 2 0 0 3 0 3 2 0 0 2 0 0 2 1 0 0 0 0
18 4 3 2 2 3 0 3 0 0 4 0 0 0 0 0 0 0 0 3 1
19 4 1 0 0 1 0 0 0 2 3 0 0 0 3 1 4 0 3 0 0
20 0 1 0 0 0 2 4 0 0 4 0 0 1 1 0 0 0 1 0 0
شکل 4- ماتریس تأخیر
1 2 3 4 5 6 7 8 9 10 1112 13 14 15 16 17 18 19 20
1 0 0 0 0 0 0 0 0 0 3 0 1 8 0 0 0 5 4 2 0
2 0 0 3 4 2 0 0 0 0 0 1 8 0 0 8 3 3 1 8 1
3 0 3 0 0 5 2 0 0 0 0 7 0 1 1 0 0 7 3 0 0
4 0 4 0 0 0 2 2 7 1 0 0 0 6 0 0 5 0 4 0 0
5 0 2 5 0 0 0 6 0 6 0 0 0 0 0 8 2 0 68 0
6 0 0 2 2 0 0 5 8 0 0 0 3 0 7 4 1 4 0 0 4
7 0 0 0 2 6 5 0 6 4 3 0 7 5 1 0 0 0 6 0 6
8 0 0 0 7 0 8 6 0 0 4 0 3 0 8 1 7 2 0 0 0
9 0 0 0 1 6 0 4 0 0 7 2 0 3 3 0 0 2 0 2 0
10 3 0 0 0 0 0 3 4 7 0 0 4 0 3 2 7 0 8 2 5
11 0 1 7 0 0 0 0 0 2 0 0 0 0 7 7 6 0 0 0 0
12 1 8 0 0 0 3 7 3 0 4 0 0 7 6 5 0 3 0 0 0
13 8 0 1 6 0 0 5 0 3 0 0 7 0 4 0 7 0 0 0 5
14 0 0 1 0 0 7 1 8 8 3 7 6 4 0 0 0 0 0 5 7
15 0 8 0 0 8 4 0 1 0 2 7 5 0 0 0 5 6 0 3 0
16 0 3 0 5 2 1 0 7 0 7 6 0 7 0 5 0 5 0 7 0
17 5 3 7 0 0 4 0 2 2 0 0 7 0 0 6 5 0 0 0 0
18 4 1 3 4 6 0 6 0 0 8 0 0 0 0 0 0 0 0 4 2
19 2 8 0 0 8 0 0 0 2 2 0 0 0 5 3 7 0 4 0 0
20 0 1 0 0 0 4 6 0 0 5 0 0 5 7 0 0 0 2 0 0
شکل 5- ماتریس هزینه
نود منبع، نود یک میباشد و مجموعه نودهای مقصد u={9,11,12,14,17} میباشند. مسئله عنوان شده را با استفاده از دو الگوریتم ژنتیک و الگوریتم کولونی
مورچهها بررسی میکنیم.
در الگوریتم ژنتیک اندازه جمعیت اولیه خود را برابر با 20 در نظر میگیریم. الگوریتم ارائه شده را چندین دفعه با نرخهای جهش و تقاطع متفاوت، جهت یافتن درخت مسیریابی بهینه شبکه داده شده با توجه به نوع بستههای ارسالی و با بهرهگیری از جدول 1 اجرا میکنیم. نتایج به دست آمده از اجراهای متفاوت الگوریتم را میتوان در شکلهای 6 و 7 مشاهده نمود. با توجه به شکلهای 6 و 7 میتوان این نتیجهگیری را کرد که نرخ تقاطع 0.6 و نرخ جهش 0.3 برای حل مساله نرخ های مناسبی می باشند و با استفاده از این مقادیر به نتایج بهتری میتوان رسید.
شکل 6- تابع شایستگی به دست آمده در هر تکرار از اجرای الگوریتم در کلاس A
شکل7-تابع شایستگی به دست آمده در هر تکرار از اجرای الگوریتم در کلاس B
برای بستههایی با کلاس درخواست A، نرخ جهش 0.3 و نرخ تقاطع 0.6 درخت مسیریابی به دست آمده به صورت شکل8 میباشد و همچنین برای بستههایی با کلاس درخواست B، نرخ جهش 0.3 و نرخ تقاطع 0.6 به صورت شکل 9 میباشد.گرههای برگ در درختهای شکل 8و 9 نشاندهنده نودهای مقصد ما میباشند.
شکل 8- درخت کلاس A شکل9- درخت کلاس B
این بار جهت دستیابی به درخت مسیریابی بهینه از الگوریتم کولونی مورچهها استفاده مینماییم. الگوریتم مورد نظر را چندین دفعه با تعداد مورچه اولیه متفاوت اجرا میکنیم. جهت ارزیابی الگوریتم و مقایسه آن با الگوریتم ژنتیک در پایان هر دور تکرار از الگوریتم تابع شایستگی عنوان شده در الگوریتم ژنتیک خود را، محاسبه مینماییم.نتایج به دست آمده از اجراهای الگوریتم را می توان در شکل های 10 و 11 مشاهده نمود.
شکل 10- تابع شایستگی به دست آمده در هر تکرار از اجرای الگوریتم در کلاس A
شکل 11- تابع شایستگی به دست آمده در هر تکرار از اجرای الگوریتم در کلاس B
برای بستههای کلاس Aو تعداد مورچه برابر با 40 درخت مسیریابی بهینه ایجاد شده به صورت شکل 12 میباشد و همچنین برای بستههای کلاس B و تعداد مورچه برابر با 40 درخت مسیریابی بهینه ایجاد شده به صورت شکل 13 میباشد.
شکل 12- درخت کلاس A
شکل 13- درخت کلاس B
شکلهای 13 و 14 نیز نشاندهنده میانگین تأخیر انتها-به-انتها برای الگوریتمهای مختلف میباشند.
شکل 14- میانگین تاخیربه دست آمده در هر تکرار از اجرای الگوریتمهای ارائه شده در کلاسA
شکل 15- میانگین تاخیربه دست آمده در هر تکرار از اجرای الگوریتمهای ارائه شده در کلاس B
نتایج به دست آمده از اجرای الگوریتمها نشاندهنده این موضوع میباشد که در کلاس Aالگوریتمها مسیرهایی را بر می‌گزیند که در مجموع دارای تاخیر کمتری میباشند و در زمانی که هدف پیدا کردن درخت مسیریابی برای کلاس B است الگوریتمها به دنبال مسیرهایی است که در مجموع دارای هزینه کمتری میباشند. الگوریتم کولونی ارائه داده شده به طور متوسط نسبت به الگوریتم ژنتیک ارائه داده شده به نتایج بهتری میرسد. همچنین هر دو روش پیشنهادی در مقایسه با پروتکلهای AODVو AMQR به نتایج بهتری رسیدند. در الگوریتم کولونی مورچه در دورهای ابتدایی مقدار تابع شایستگی نسبت به الگوریتم ژنتیک بزرگتر میباشد اما با تکرار هرچه بیشتر الگوریتم مقدار تابع شایستگی کمتر میشود. این مسئله به خاطر آن است که در الگوریتم کولونی مورچه در ابتدا همه مسیرها دارای مقدار فرمون برابر میباشند و الگوریتم مسیرهای تصادفی را برای رسیدن به مقاصد انتخاب
میکند، اما با تکرار بیشتر الگوریتم مقادیر فرمون موجود بر روی مسیرها به روز میشود و مورچهها مسیرهایی که دارای فرمون بیشتر میباشند را بر میگزینند.
6- نتیجهگیری
در این مقاله موضوع مسیریابی چندبخشی با دو روش الگوریتم ژنتیک و الگوریتم کولونی مورچهها مورد بررسی قرار گرفت. معیارهای در نظر گرفته شده جهت
تصمیمگیری در مسیریابی هزینه و تاخیر بودند. نتایج به دست آمده از بررسی مقالات مرتبط و شبیهسازی الگوریتمهای ذکر شده این موضوع را نشان داد که در نظر گرفتن معیارهای بیشتر در امر تصمیمگیری در مسیریابی سبب بهبود مسیریابی میشود. همچنین با توجه به نتایج به دست آمده این موضوع مشخص شد که درخت مسیریابی
منابع 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. Venkateswaran; S. K. Sanyal; R. Nandi.Genetic algorithm based efficient routing scheme for multicast networks. IEEE International Conference |
ایجاد شده توسط الگوریتم کولونی مورچهها به طور میانگین بهینهتر از درخت مسیریابی ایجاد شده توسط الگوریتم ژنتیک میباشد. آنچه که در آینده میتواند مورد بررسی قرار گیرد استفاده از معیارهای تصمیمگیری دیگر در موضوع مسیریابی نسبت به معیارهای در نظر گرفته شده و همچنین ایجاد یک تقسیمبندی مناسبتر برای بستههای ورودی به شبکه میباشد.
S. 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.
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.
|
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
[1] Quality of Service (QoS)
[2] end-to-end transmission delay
[3] Genetic Algorithm
[4] Ant colony optimization
[5] Design Space
[6] Genetic Space