بخشی از مقاله
چکیده
شبکههای حسگر بیسیم برای نظارت و کنترل یک محیط خاص مورد استفاده قرار میگیرند و از تعداد زیادی گره حسگر ارزان قیمت تشکیل شدهاند که به صورت متراکم در یک محیط پراکنده میشوند. اطلاعات جمعآوری شده به-وسیله حسگرها باید به یک ایستگاه پایه منتقل شوند. در ارسال مستقیم، هر حسگرمستقیماً اطلاعات را به مرکز می-فرستد. بهدلیل فاصله زیاد حسگرها از مرکز، انرژی زیادی مصرف میکنند. در مقابل طراحیهایی که فواصل ارتباطی را کوتاهتر میکنند، میتوانند دوره حیات شبکه را طولانیتر کنند. بنابراین چیدمان بهینه ومصرف انرژی مستقیماً طول عمر شبکه حسگر را تحت تأثیر قرار میدهد.
پژوهش انجام شده در این مقاله چیدمان بهینه گرههای حسگر در جهت کاهش توان مصرفی گرههای حسگر از طریق اتصال بهینه گرههای حسگر به گرههای چاهک با استفاده از الگوریتم ژنتیک بهبودیافته است. در این مقاله یک کدگذاری مطلوب برای پاسخ در نظر گرفته شده و یک تابع هدف مبتنی بر چیدمان بهینه با حداقل توان مصرفی در گرههای حسگر تعریف شده است و سپس با استفاده از الگوریتم ژنتیک مسئله حل شده است و نتایج با الگوریتمهای تکاملی دیگر نظیر الگوریتم بهینهسازی ازدحام ذرات و الگوریتم زنبورعسل مقایسه شده است. نتایج حاکی عملکرد بهینه الگوریتم ژنتیک بهبودیافته در چیدمان بهینه گرهها با حداقل توان مصرفی در شبکه حسگر دارد.
کلمات کلیدی: شبکه حسگر بیسیم، الگوریتم ژنتیک، الگوریتم بهینهسازی ازدحام ذرات، الگوریتم زنبورعسل مصنوعی.
-1 مقدمه
در سالهای اخیر، استفاده از شبکههای حسگر بیسیم در بخشهای گوناگون به سرعت در حال گسترش است. برای مثال این شبکهها در نظارت و جمعآوری اطلاعات مربوط به آتشسوزی، بلایای طبیعی مانند زلزله و موارد پزشکی و نظامی، کاربردهای بسیاری دارند. در این شبکهها، گرههای حسگر اغلب به علت اندازه کوچک با محدودیتهایی مواجه هستند مانند قدرت پردازش و منبع انرژی محدود. این محدودیتها باعث شده است که محققان در طراحی این شبکهها مطالعات گستردهای انجام دهند. یکی از این مسائل مکان قرارگیری گرهها در محیط حس است. به این مسئله جایگذاری گرهها میگویند.
هرچهگرهها در فاصله بیشتری نسبت به گره چاهک قرار گرفته باشند زمان و توان مصرفی بیشتری مصرف میکنند تا انتقال اطلاعات به چاهک انجام دهند. بنابراین چیدمان بهینه گرههای حسگر و اتصال آنها به نزدیکترین گره چاهک درجهت کاهش توان مصرفی شبکه بهعنوان یک مسئله بهینهسازی مطرح میشود - -RV H +HQULTXH %UDQG DR 1HWR، 2014، Rajagopalan، 2006 و Rahul Goyal، . - 2014 ادامه ساختار این مقاله به این صورت است که در بخش دوم مروری بر پیشینه تحقیقات انجامشده خواهیم داشت و در بخش سوم الگوریتمهای تکاملی بیان میشوند. در بخش چهارم مدل پیشنهادی و ارزیابی نتایج استفاده از الگوریتمهای تکاملی در جهت حل مسئله ارائه میشود و در نهایت در بخش آخر نتیجه-گیری انجام میشود.
-2 مروری بر پیشینه تحقیق
لیو در سال 2014 در مقالهای تحت عنوان الگوریتم مورچگان همراه با مکانیزم مهاجرت حریصانه برای مکانیابی گرهها در شبکه حسگر به بررسی مسئله پوشش شبکه با حداقل هزینه و قابلیت اتصال مطمئن پرداختند. روش پیشنهادی با استفاده از الگوریتم مورچگان مسئله پوشش شبکه و کاهش هزینه مکانیابی را مورد هدف قرار داد. این الگوریتم شعاع - برد - برقراری ارتباط را تنظیم میکرد تا از این طریق مسئله بهینهسازی انرژی و طول عمر شبکه را بهبود دهد. شبیهسازی نشان داد روش پیشنهادی هزینه مکانیابی را کاهش و تعادل بین مصرف انرژی میان گرههای و افزایش طول عمر شبکه در شبکه حسگر برقرار میکند - Liu،
. - 2014 کائو و همکاران در سال 2014 در مقالهای تحت عنوان مقایسه انواع بهینهسازی ازدحام ذرات1 در مکانیابی گرههای شبکه حسگر الگوریتمهای مختلفی از بهینهسازی ازدحام ذرات با توپولوژیهای جمعیتی مختلف را مورد مطالعه قرار دادند. نتایج شبیهسازی حاکی از این بود که در زمینه شبکه حسگر توپولوژی حلقوی و مربعی دارای کارایی قابل قبولی هستند - Cao، . - 2014 برار و همکاران در سال 2014 در مقالهای تحت عنوان مکانیابی بهمنظور حداکثر پوشش در شبکه حسگر نامتقارن با استفاده از الگوریتم ژنتیک یک شبکه حسگر که دارای هدف پوشش مؤثر شبکهای که در آن گرههای نامتقارن دارای بردهای مختلف هستند را بررسی کردند نتایج شبیهسازی نشان داد که روش پیشنهادی راهحل مؤثری برای مکانیابی گرهها و حذف همپوشانی برای حداکثرکردن پوشش ارائه میدهد - Brar، . - 2014 ژو در سال 2015 در مقالهای تحت عنوان روشی برای مکانیابی براساس الگوریتم بهینهسازی ازدحام ذرات و الگوریتم کواسی- نیوتن2 برای شبکههای حسگر ارائه دادند.
در این روش از الگوریتم PSO برای یافتن جوابها و مقادیر بهینه استفاده شد سپس از این مقادیر در مرحله تکرار به عنوان مقادیر ورودی برای الگوریتم کواسی- نیوتن استفاده شد. نتایج شبیهسازی بیانگر آن است الگوریتم پیشنهادی در مکانیابی گرهها موفق بوده است - Zou، . - 2015 بارولی و همکاران در سال 2015 در مقالهای تحت عنوان مکانیابی گرهها در شبکههای توری بیسیم، تحلیل نتایج شبیهسازی سیستم WMN-GA3 برای پارامترها و توزیعهای مختلف، به بررسی شبکههای توری بیسیم پرداختند. در این مقاله آنها کارایی 4 توزیع مختلف - نرمال، یکنواخت، نمایی و وایبل - 4 برای مسیریابهای توری را ارزیابی کردند که نسبت تحویل دادههای اطلاعاتی و مقیاسهای تأخیری را در نظر می-گرفت.
برای شبیهسازی از یک پروتکل HWMP5 استفاده کردند. شبیهسازی نشان داد که سیستم بهکار رفته میتواند بهطور موفقی برای مکانیابی مسیریابها بهکار رود - Barolli، . - 2015 پنگ و همکاران در سال 2015 در مقالهای تحت عنوان الگوریتم مکانیابی بهینه براساس الگوریتم ژنتیک در شبکه حسگر به بررسی شبکههای حسگر بهمنظور مکانیابی بدون برد از نوع DV-Hub پرداختند. در این مقاله از الگوریتم مکانیابی بدون برد از نوع DV-Hub استفاده شد. این الگوریتم براساس الگوریتم ژنتیک بهینهسازی شده بود. نتایج شبیهسازی حاکی از این بود که روش پیشنهادی دقت مکانیابی را در مقایسه با روشهای پیشین افزایش میدهد - Peng، . - 2015 پوجا و همکاران در سال 2015 در روشی تحت عنوان مکانیابی بهینه حسگرها با استفاده از الگوریتم BFA1 به بررسی گرههای حسگر به عنوان باکتریهایی که در جستجوی غذا میباشند، پرداختند که توسط بهترین اتصالات ممکن نشان داده شدهاند.
در این مقاله از این پیشفرض استفاده شد که میتوان یک ناحیه از فضا را با استفاده از یک شش ضلعی پوشاند. در نتیجه استفاده از الگوریتم BFA برای بهینهسازی مکانها طوری که همه گرهها در شبکه به سمت راسهای این شش ضلعی که به یکدیگر مرتبط شدهاند، حرکت کنند که منجربه پوشش کامل فضا میشود - Pooja، . - 2015 سان و همکاران در سال 2015 در مقالهای به نام مکانیابی بهینه در شبکه حسگر براساس الگوریتم ترکیبی فرهنگ مورچگان، مکانیزم تکاملی الگوریتم فرهنگ با الگوریتم مورچگان ترکیبشده در فضای جمعیت به عنوان یک استراتژی تکاملی واحد عمل میکند که پس از آن جستجوهای صورت گرفته در فضای جمعیت را به وسیله بهترین انتخابها و پاسخها هدایت میکند که باعث میشود الگوریتم جستجوی فرهنگی جواب بهینه را سریعتر و با پایداری بیشتر نسبت به سایر الگوریتمهای مرسوم انجام دهد - Sun، . - 2015
-3 الگوریتمهای تکاملی
مفهوم بهینهسازی بدین صورت است که در بین پارامترهای یک تابع به دنبال مقادیری باشیم که تابع را کمینه یا بیشینه نماید. کلیه مقادیر مناسب جهت این امر را، راهحلهای ممکن و بهترین مقدار از این مقادیر را، راهحل بهینه مینامند. الگوریتمهای تکاملی هر دو نوع مسائل بیشینهسازی و کمینهسازی را پوشش میدهند. بهینهسازی همواره با مشکلات فراوانی همراه بوده است. شیوههای سابق برای حلکردن مشکلات بهینهسازی، مستلزم تلاشهای محاسباتی بیشماری است. الگوریتمهایی از جمله الگوریتمهای هوشجمعی تا حدی این مشکل را حل نمودهاند. توسط این الگوریتمها راهحلهایی پیدا میشوند کهتقریباً به جواب نزدیکند - Shilane، . - 2008
-1-3 الگوریتم ژنتیک
الگوریتم ژنتیک، الهامی از علم ژنتیک و نظریه تکامل داروین است و براساس بقای برترینها یا انتخاب طبیعی استوار است. این الگوریتم برای کاربردهای مهندسی و بهصورت امروزی آن نخستینبار توسط جان هالند متخصص علوم کامپیوتر دانشگاه میشیگان در سال 1975 پیشنهاد گردید. یک کاربرد متداول الگوریتم ژنتیک، استفاده از آن بهعنوان تابع بهینهکننده است. اگرچه این الگوریتم پس از الگوریتم استراتژی تکاملی پیشنهاد گردید ولی مشهورترین روش از بین الگوریتمهای تکاملی است.در یک الگوریتم ژنتیک یک جمعیت از افراد طبق مطلوبیت آنها در محیط بقا مییابند . افرادی با قابلیتهای برتر، شانس ازدواج و تولیدمثل بیشتری را خواهند یافت. بنابراین بعداز چند نسل فرزندانی با کارایی بهتر بهوجود میآیند. در الگوریتم ژنتیک هر فرد از جمعیت بهصورت یک کروموزوم معرفی میشود. کروموزومها در طول چندین نسل کاملتر میشوند. در هر نسل کروموزومها ارزیابی میشوند و متناسب با ارزش خود امکان بقا و تکثیر مییابند - Goldberg، . - 2012 بهطورکلی، الگوریتمهای ژنتیک از اجزاء زیر تشکیل میشوند:
