بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
ارایه روشی جهت بهبود عملکرد مسیریابی با استفاده از الگوریتم بهینه سازی جمع ذرات و منطق فازی در شبکه های موردی
چکیده
مسیریابی در شبکه های موردی، اهمیت زیادی دارد زیرا محدودیت های انرژی، نیازمندی های کیفیت سرویس و تغییرات ناگهانی در وضعیت گره ها مثل خرابی، باعث تغییرات مکرر و غیر قابل پیش بینی در ساختار شبکه می گردد. با توجه به این که توپولوژی شبکه های موردی، مدام در حال تغییر است و تداخل امواج رادیویی باعث گم شدن تعداد زیادی از بسته ها می شود، مسیریابی در این شبکه ها، هنوز به عنوان چالشی مطرح است. در این مقاله، با استفاده از الگوریتم بهینه سازی جمع ذرات، و منطق فازی روشی جهت بهبود عملکرد مسیریابی در شبکه های موردی، ارایه شده است که در جهت افزایش بهره وری شبکه، از منابع شبکه به طرز مؤثری استفاده می نماید و از مزایای این روش، انعطاف پذیر بودن و افزایش توان عملیاتی مسیریابی در این روش می باشد.
واژگان کلیدی:شبکه موردی، مسیریابی، جمع ذرات ، فامیلی، منطق فازی
مقدمه
امروزه شـبکه های کامپیوتری، نقشـی انکار ناشـدنی را به صورت مستقیم و غیر مستقیم در زندگی روزمره ی ما بازی می کنند، که این جایگاه را مرهون پیشـرفت های چشـمگیر دهه ی گذشـته اسـت. پیچیدگی حاصـل از این پیشرفت این فناوری، منجر به ارایه ی دسـته بندی های گوناگونی، از زوایای دید مختلف از آن شـده اسـت؛ از دسـته بندی بر اسـاس نوع رسانه ی مورد اسـتفاده گرفته تا وسـعت جغرافیایی توپولوژی مورد اسـتفاده در آن. شـبکه های بی سیم، زیر مجموعه ای از شبکه های کامپیوتری است که از امواج رادیویی به عنوان رسانه ی انتقال، استفاده می کنند.
بنابر دلایلی نظیر اقتصـادی و سهولت کاربری، در دهه ی گذشته، شتاب بیشتری در رشد کاربردهای مبتنی بر شبکه های بی سـیم دیده شده است. امروزه نیز تحقیقات گستردهای در رابطه با انواع این شبکه ها در مراکز مهم تحقیقاتی در حال انجام است. (Vaidya, et al., 2011)اصولاً. شبکه های کامپیوتری بی سیم را می توان به دو دسته ی کلی تقسیم نمود:
• شبکه های مبتنی بر زیرساخت
• شبکه های بدون زیرساخت یکی از ویژگی های شبکه های مبتنیبر زیرساخت، وجود ساختاری به نام ستون فقرات شبکه، در آن است که عموماً از سـاختاری مبتنی بر شـبکه های سـیمی، برای متصل کردن محدوده های مختلف بی سیم به یکدیگر استفاده می کند در مقابل، شـبکه های بی سـیم موردی، مثالی جامع از شـبکه های کامپیوتری بی سـیم بدون زیرسـاخت هستند. در این دسته از شبکه ها، هیچ ایســتگاه ثابت با اتصــال ســیمی به کار گرفته نمی شــود، مگر در شــرایطی که نیاز به اتصــال به شــبکه ی بزرگتری مانند اینترنت باشــد. در این دســته از شــبکه ها، هر گره ی بی ســیم، هم به عنوان یک میزبان و هم به عنوان یک مســیریاب عمل می کند، زیرا انتقال اطلاعات ممکن است از نوع چندگامه انجام شود. هستند(.(Rango & Guerriero, 2012
-1 الگوریتم بهینه سازی جمع ذرات
روشPSO یک تکنیک بهینه سازی مبتنی بر قوانین احتمال است که ایدهی اولیه آن توسط دکتر راسل ابرهارت 1 دانشمند علوم کامپیوتری و دکتر جیمزکندی2 روانشناس مسایل اجتماعی در سال 1995 معرفی شد( Kennedy & .(Eberhart, 1995 این روش از رفتار اجتماعی دستهی پرندگان یا گروه ماهیها در حین جستجوی غذا، برای هدایت جمعیت به منطقهی امید بخش در فضای جستجو الهام گرفته شده است. قوانین منطقی خاصی بر نحوهی رفتار موجودات حکمفرمانی میکند. پرندگان تنها با تنظیم حرکت فیزیکی خود با اجتناب از تصادم به دنبال غذا میگردند و به طور تئوری هر پرنده به عنوان یکی از اعضای گروه از تجربهی قبلی و یافتههای سایر اعضا برای یافتن غذا بهره میبرد. این مشارکت یک مزیت قطعی بر جستجوی رقابتی برای یافتن غذا میباشد. پایهی اصلی 3PSO همین تسهیم اطلاعات بین اعضای گروه است(.(Kennedy & Eberhart, 1995
با توجه به ساختار همسایگی مورد استفاده، یک فرمانده1، برای هدایت جستجوی ذرات به سمت مناطق بهتر فضای جستجو، انتخاب میشود و در هر تکرار، هر ذره، عملیات زیر را انجام میدهد:
➢ به روز رسانی سرعت:
سرعت هر ذره، میزان تغییر صورت گرفته روی آن را نشان میدهد و به صورت زیر تعریف می شود:
به منظور جلوگیری از واگرایی الگوریتم، عناصر در بازهی [-Vmax ,+Vmax]، واقع هستند. در بیشتر موارد، در رابطهی به روز رسانی سرعت، پارامتری تحت عنوان وزن اینرسی2 نیز به کار میرود. پارامتر w حرکت ذرات را کنترل میکند(,Talbi (2009
➢ به روز رسانی موقعیت:
هر ذره، موقعیت خود را بر اساس رابطهی زیر به روز رسانی کرده و به موقعیت جدید حرکت میکند:
➢ به روز رسانی بهترین ذره ی یافت شده:
هر ذره، بهترین موقعیت خودرا با استفاده از رابطه زیر بروز رسانی خواهد
➢ به روز رسانی بهترین ذرهی یافت شده در کل گروه ذرات:
به علاوه، بهترین جواب یافت شده در جمعیت، نیز به صورت رابطه زیر به روز رسانی میشود:
-2 مدلسازی مسئله مسیریابی
در روش پیشنهادی برای مسیریابی از تلفیق الگوریتم بهینه سازی جمع ذرات با منطق فازی، استفاده شده است که در واقع توسعهای از الگوریتم جمع ذرات میباشد. در این روش، با دریافت اطلاعات وضعیت شبکه، سیستم کنترل فازی بر مبنای سه
پارامتر انرژی مصرفی، فاصله و پهنای باند در دسترس، هزینهی فازی هر لینک را محاسبه میکند. این هزینههای فازی در ادامه توسط الگوریتم جمع ذرات، به عنوان ملاک برازندگی هر مسیر برای عملیات مسیریابی، مورد استفاده قرار میگیرند.
شکل 1-2، شِمای کلی روش پیشنهادی را نشان میدهد.
ورودیهای سیستم فازی پیشنهادی به صورت انرژی، فاصله و پهنای باند، تعریف شدهاند. خروجی سیستم کنترل فازی نیز هزینهی فازی هر لینک میباشد.
شبکهی ارتباطی برای مسألهی مسیریابی بدین صورت تعریف میشود: گراف G(V,E) را در نظر بگیرید که در آن V مجموعه یگرهها و E V V مجموعهی لینکهای گراف را نمایش میدهند. به هر لینک (i,j) سه پارامتر انرژی مصرفی، فاصله و پهنای باند در دسترس، نسبت داده شده است که به صورت زیر بیان میشوند.
در رابطه (5) این پارامتر، بیانگر میزان انرژی مصرف شده در هنگام انتقال داده از گرهای به گرهی دیگر میباشد:
همانگونه که رابطه (6)، بیانگر فاصلهی بین گره ها ت:
و پارامتر رابطه (7)، بیانگر مقدار بایتهایی است که در واحد زمان در هر لینک در دسترس است:
-3 روش پیشنهادی 1(FFPSO)
با توجه به اینکه در الگوریتم جمع انبوه ذرات یکی از نقاط ضعف الگوریتم در برخی موارد همگرایی زودرس می باشد. در این روش، ابتدا جمعیت به دستههای مختلفی که در اینجا خانواده نامیده شدهاند، دستهبندی میگردد. در یک خانواده، هنگامی که یک ذره بهترین موقعیت خانواده را پیدا میکند، این ذره نقش فرمانده را ایفا کرده و سایر اعضای خانواده به این سمت، هدایت میشوند.((Lu, et al., 2011در این روش پیشنهادی در انتخاب فامیلی به منظور بهینه شدن پاسخ ها و تشکیل خانواده ابتدا از جمعیت 30 نفری پس از تعیین موقعیت هریک از ذرات گروه هایی را به صورت خانواده هایی با اعضای مساوی انتخاب می کنیم که در یک بازه مشابه قرار گرفته باشند. مراحل روش به صورت زیر میباشند:
همان گونه که شکل 1 -3 نشان میدهد، مراحل روش به صورت زیر میباشند: (1 ایجاد جمعیت اولیه با 30 ذره به صورت تصادفی.
(2 قرار دادن تعداد اعضای خانواده به صورت تصادفی.
(3 مقداردهی اولیهی بهترین جواب یافته شده توسط هر خانواده و بهترین جواب یافته شدهی فعلی و محاسبهی میزان برازندگی هر ذره.
(4 برای هر ذرهی i در جمعیت، بترتیب مراحل زیر اجرا میشود:
