In recent years, the static shortest path (SP) problem has been well addressed using intelligent optimization techniques, e.g., artificial neural networks, genetic algorithms (GAs), particle swarm optimization, etc. However, with the advancement in wireless communications, more and more mobile wireless networks appear, e.g., mobile networks [mobile ad hoc networks (MANETs)], wireless sensor networks, etc. One of the most important characteristics in mobile wireless networks is the topology dynamics, i.e., the network topology changes over time due to energy conservation or node mobility. Therefore, the SP routing problem in MANETs turns out to be a dynamic optimization problem. In this paper, we propose to use GAs with immigrants and memory schemes to solve the dynamic SP routing problem in MANETs. We consider MANETs as target systems because they represent new-generation wireless networks. The experimental results show that these immigrants and memory-based GAs can quickly adapt to environmental changes (i.e., the network topology changes) and produce high-quality solutions after each change

چکیده

در سالیان اخیر مسئله پیدا کردن کوتاه ترین مسیر بصورت ایستا (SP) ،با استفاده از تکنیک های بهینه سازی هوشمند نظیر شبکه های عصبی مصنوعی ،الگورتیم های ژنتیک (GA) ،الگوریتم پرندگان یا بهینه سازی ازدحام ذرات (PSO) بسیار مورد توجه قرار گرفته است .  پیشرفت در زمینه ارتباطات بی سیم منجر به پیدایش تعداد بسیار زیادی شبکه بی سیم نظیر شبکه های سیار [شبکه های موردی سیار (MANETS)]، شبکه های حسگر بی سیم و غیره گردیده است.یکی از مهمترین خصوصیات شبکه های بی سیم متحرک یا سیار ،پویایی توپولوژی آنها است . برای مثال توپولوژی شبکه می تواند به دلیل صرفه جویی در انرژی یا تحرک نودها، تغییر نماید. بنابراین مسئله مسیریابی کوتاهترین مسیر(SP) در MANETS  به یک مسئله بهینه سازی پویا تبدیل می شود. در این مقاله از الگوریتم ژنتیک با طرح حافظه و مهاجرت برای حل مسئله مسیریابی کوتاهترین مسیر به صورت پویا در MANETS استفاده شده است .ما MANETS  را به دلیل اینکه نسل جدید شبکه های بی سیم را ارائه می دهد، بعنوان سیستم های مقصد در نظر گرفتیم . نتایج تجربی نشان می دهد که الگوریتم های ژنتیک برپایه طرح حافظه و مهاجرت می توانند به سرعت با تغییرات محیطی تطبیق پیدا کرده ( برای مثال تغییرات توپولوژی شبکه )و راه حل هایی با کیفیت بالا بعد از هر تغییر ایجاد نماید .

1-مقدمه

شبکه موردی متحرک [25][26][28] یک شبکه بی سیم چند جهشی به صورت خودسازمان ده و خودپیکربند است که از مجموعه ای از میزبانهای متحرک تشکیل شده است . این میزبانها می توانند به آزادی به اطراف حرکت کرده و به پخش بسته ها به نمایندگی از یکدیگر مشارکت داشته باشند.MANETS با قرار دادن عملیات مسیریابی در میزبانهای متحرک منجر به کیفیت و قابلیت اطمینان عملکردها می شود .در MANETS مسیر یابی تک بخشی ،یک مسیر رو به جلوی چند جهشی را بین دو نود بالاتر از دامنه ازتباطات بی سیم مستقیم تخمین می زند. علاوه بر آن پروتکل های مسیریابی هنگامیکه لینک های روی مسیرهابه دلیل اثراتی نظیر جایجایی نودها ، تخلیه باطری ،انتشار رادیویی و تداخلات بی سیم قطع می شود ،همبند بودن مسیرها را حفظ می نماید . در شبکه های چندجهشی ،مسیریابی یکی از مهمترین مباحثی است که تاثیر مهمی در کارآیی شبکه ها دارد. تاکنون تنها دو نوع پروتکل مسیریابی در MANETS وجود داشته است . این پروتکل ها، مسیریابی توپولوژیک و مسیریابی جغرافیایی نامیده می شوند. در مسیریابی توپولوژیک،گره های متحرک از اطلاعات توپولوژیک برای ساخت جداول مسیریابی یا جستجوی مستقیم مسیرها استفاده می کنند…