بخشی از مقاله
چکیده
حسگرهای بیسیم ازجمله مناسبترین راهکارهای جمعآوری داده در دنیا محسوب میشوند. اطلاعات جمعآوری شده بهوسیله حسگرها باید به یک ایستگاه پایه منتقل شوند. در ارسال مستقیم، هر حسگر مستقیماً اطلاعات را به مرکز میفرستد. بهدلیل فاصله زیاد حسگرها از مرکز، انرژی زیادی مصرف می-کنند. در مقابل طراحیهایی که فواصل ارتباطی را کوتاهتر میکنند، میتوانند دوره حیات شبکه را طولانیتر کنند. در این شبکهها، گرههای حسگر اغلب به علت اندازه کوچک با محدودیتهایی مواجه هستند مانند قدرت پردازش و منبع انرژی محدود. این محدودیتها باعث شده است که محققان در طراحی این شبکهها مطالعات گستردهای انجام دهند.هرچه گرهها در فاصله بیشتری نسبت به گره سرخوشه قرار گرفته باشند زمان و توان مصرفی بیشتری مصرف میکنند تا انتقال اطلاعات به سرخوشه انجام دهند. بنابراین خوشهبندی بهتر گرههای حسگر در شبکههای حسگر بیسیم در جهت کاهش توان مصرفی گرههای حسگر از طریق اتصال بهتر گرههای حسگر به گرههای سرخوشه با استفاده از الگوریتم جستجوی گرانشی انجام شده است و نتایج با الگوریتمهای زنبورعسل مصنوعی و بهینهسازی ازدحام ذرات مقایسه شده است.
واژگان کلیدی: شبکههای حسگر بیسیم، خوشهبندی، الگوریتم جستجوی گرانشی، الگوریتمهای تکاملی.
مقدمه
پیشرفتهای اخیر در زمینه سیستمهای میکروالکترومکانیکی، حسگرهای هوشمند، مخابرات بیسیم و همچنین الکترونیک دیجیتال، امکان ساخت گرههای حسگر کوچک، کم مصرف و کم هزینه را فراهم میسازند که توانایی برقراری ارتباط به صورت بیسیم را نیز دارا میباشند - . - Neto, Rego, Cardoso, & Celestino Jr, 2014 این گرههای حسگر کوچک شامل سه بخش حسگر، پردازش اطلاعات و انتقال اطلاعات به صورت بیسیم میباشند. به طورکلی یک شبکه حسگر بیسیم شامل تعداد زیادی از این گرهها است که برای اندازهگیری یک پارامتر، دادههای آنها بهصورت دسته جمعی مورد توجه قرار میگیرد. یعنی همهی اطلاعات جمعآوری شده برای یک پارامتر، در یک گره از شبکه که معمولاً ایستگاه سرخوشه - چاهک - نامیده میشود، پردازششده و مقدار واقعی آن پارامتر بهطور نسبتاً دقیقی تخمینزده میشود - . - Rajagopalan & Varshney, 2006
در این شبکهها از کارافتادن یک گرهی شبکهتقریباً تأثیری در مقدار تخمینزده شده ندارد. در شبکههای حسگر بیسیم، گرههای حسگر با تعداد زیاد در داخل مکان مورد نظر و یا بسیار نزدیک به آن برای اندازهگیری پارامتر موردنظر قرار دارند. مکان این گرهها از قبل طراحی نشده است. این مساله به سادگی کار جایگذاری حسگرها در شبکه کمک میکند اما در عوض، پروتکلهایی که برای این شبکهها به-کار گرفته میشود باید خودتنظیم یا خودسازمانده باشند با توجه به اینکه این حسگرها در داخل خود پردازنده دارند، برای کمشدن حجم انتقال اطلاعات، این حسگرها فقط داده موردنیاز را پس از پردازش دادههای اولیه میفرستند. در شبکههای حسگر بیسیم محدودیت اصلی برای طراحی پروتکلها، انرژی محدود حسگرها است.
در واقع پروتکلهایی که مصرف توان در حسگرها را به حداقل برسانند، برای شبکههای حسگر بیسیم بیشتر مورد توجه هستند. هرچه گرهها در فاصله بیشتری نسبت به گره سرخوشه قرار گرفته باشند زمان و توان مصرفی بیشتری مصرف میکنند تا انتقال اطلاعات به سرخوشه انجام دهند. بنابراین خوشهبندی بهینه گرههای حسگر از طریق اتصال آنها به نزدیکترین گره سرخوشه درجهت کاهش توان مصرفی شبکه بهعنوان یک مسأله بهینهسازی مطرح میشود. الگوریتمهای مختلفی برای اتصال بهینه گرهها در شبکههای حسگر بیسیم ارائه شده است. اما مرتبه زمانی این الگوریتمها با بزرگشدن ابعاد شبکه و تعداد گرهها افزایشیافته و هزینه زیادی برای بدست آوردن پاسخ بهینه نیاز است.
زمانبربودن الگوریتمهای کلاسیک باعث میشود کارایی مناسبی در حل این مسأله نداشته باشند. بنابراین نیاز به استفاده از الگوریتمهای دیگری است که در زمان قابل قبول، پاسخ مناسبی برای این مسأله بدست آوردند. از جمله این الگوریتمهای مناسب، الگوریتمهای تکاملی هستند - . - Goyal یکی از الگوریتمهای تکاملی، الگوریتم جستجوی گرانشی است. ادامه ساختار این مقاله به این صورت است که در بخش دوم مروری بر پیشینه تحقیقات انجامشده خواهیم داشت و در بخش سوم الگوریتمهای تکاملی بیان میشوند. در بخش چهارم مدل پیشنهادی و ارزیابی نتایج استفاده از الگوریتمهای تکاملی در جهت حل مسأله ارائه میشود و در نهایت در بخش آخر نتیجهگیری انجام میشود.
-2 مروری بر پیشینه تحقیق
لیو در سال 2014 در مقالهای تحت عنوان الگوریتم مورچگان همراه با مکانیزم مهاجرت حریصانه برای مکانیابی گرهها در شبکه حسگر به بررسی مسأله پوشش شبکه با حداقل هزینه و قابلیت اتصال مطمئن پرداخت. روش پیشنهادی با استفاده از الگوریتم مورچگان مسأله پوشش شبکه و کاهش هزینه مکانیابی را مورد هدف قرار داد. این الگوریتم شعاع - برد - برقراری ارتباط را تنظیم میکرد تا از این طریق مسأله بهینهسازی انرژی و طول عمر شبکه را بهبود دهد. شبیهسازی نشان داد روش پیشنهادی هزینه مکانیابی را کاهش و تعادل بین مصرف انرژی میان گرهها و افزایش طول عمر شبکه در شبکه حسگر برقرار میکند - . - Liu & He, 2014
کائو و همکارش در سال 2014 در مقالهای تحت عنوان مقایسه انواع بهینهسازی ازدحام ذرات در مکانیابی گرههای شبکه حسگر الگوریتمهای مختلفی از بهینهسازی ازدحام ذرات با توپولوژیهای جمعیتی مختلف را مورد مطالعه قرار دادند. نتایج شبیهسازی حاکی از این بود که در زمینه شبکه حسگر توپولوژی حلقوی و مربعی دارای کارایی قابل قبولی هستند - . - Cao, Ni, & Yin, 2014 برار و همکاران در سال 2014 در مقالهای تحت عنوان مکانیابی بهمنظورحداکثر پوشش در شبکه حسگر نامتقارن با استفاده از الگوریتم ژنتیک یک شبکه حسگر که دارای هدف پوشش مؤثر شبکهای که در آن گرههای نامتقارن دارای بردهای مختلف هستند را بررسی کردند نتایج شبیهسازی نشان داد که روش پیشنهادی راه-حل مؤثری برای مکانیابی گرهها و حذف همپوشانی برای حداکثرکردن پوشش ارائه میدهد - . - Brar & Virk, 2014
ژو در سال 2015 در مقالهای تحت عنوان روشی برای مکانیابی براساس الگوریتم بهینهسازی ازدحام ذرات و الگوریتم کواسی-نیوتن1 برای شبکههای حسگر ارائه دادند. در این روش از الگوریتمPSO 2 برای یافتن جوابها و مقادیر بهینه استفاده شد سپس از این مقادیر در مرحله تکرار به عنوان مقادیر ورودی برای الگوریتم کواسی- نیوتن استفاده شد. نتایج شبیهسازی بیانگر آن است الگوریتم پیشنهادی در مکانیابی گرهها موفق بوده است - . - Zou, Lan, Shen, & Wang, 2014 بارولی و همکاران در سال 2015 در مقالهای تحت عنوان مکانیابی گرهها در شبکههای توری بیسیم، تحلیل نتایج شبیهسازی سیستم WMN-GA3 برای پارامترها و توزیعهای مختلف، به بررسی شبکههای توری بیسیم پرداختند.در این مقاله آنها کارایی 4 توزیع مختلف - نرمال، یکنواخت، نمایی و وایبل - 4 برای مسیریابهای توری را ارزیابی کردند که نسبت تحویل دادههای اطلاعاتی و مقیاسهای تأخیری را در نظر میگرفت.
برای شبیهسازی از یک پروتکل HWMP5 استفاده کردند. شبیهسازی نشان داد که سیستم بهکار رفته میتواند بهطور موفقی برای مکانیابی مسیریابها بهکار رود - . - Barolli et al., 2014 پنگ و همکارش در سال 2015 در مقالهای تحت عنوان الگوریتم مکانیابی بهینه براساس الگوریتم ژنتیک در شبکه حسگر به بررسی شبکههای حسگر بهمنظور مکانیابی بدون برد از نوع DV-Hub پرداختند. در این مقاله از الگوریتم مکانیابی بدون برد از نوع DV-Hub استفاده شد.این الگوریتم براساس الگوریتم ژنتیک بهینهسازی شده بود. نتایج شبیهسازی حاکی از این بود که روش پیشنهادی دقت مکانیابی را در مقایسه با روشهای پیشین افزایش میدهد - . - Peng & Li, 2015 پوجا و همکاران در سال 2015 در روشی تحت عنوان مکانیابی بهینه حسگرها با استفاده از الگوریتمBFA6 به بررسی گرههای حسگر به عنوان باکتریهایی که در جستجوی غذا میباشند، پرداختند که توسط بهترین اتصالات ممکن نشان داده شدهاند.
در این مقاله از این پیشفرض استفاده شد که میتوان یک ناحیه از فضا را با استفاده از یک شش ضلعی پوشاند. در نتیجه استفاده از الگوریتم BFA برای بهینهسازی مکانها طوری که همه گرهها در شبکه به سمت راسهای این شش ضلعی که به یکدیگر مرتبط شده-اند، حرکت کنند که منجربه پوشش کامل فضا میشود - - . - Nagchoudhury, Maheshwari, & Choudhary, 2015 سان و همکاران در سال 2015 در مقالهای به نام مکانیابی بهینه در شبکه حسگر براساس الگوریتم ترکیبی فرهنگ مورچگان، مکانیزم تکاملی الگوریتم فرهنگ با الگوریتم مورچگان ترکیبشده در فضای جمعیت به عنوان یک استراتژی تکاملی واحد عمل میکند که پس از آن جستجوهای صورت گرفته در فضای جمعیت را به وسیله بهترین انتخابها و پاسخها هدایت میکند که باعث میشود الگوریتم جستجوی فرهنگی جواب بهینه را سریعتر و با پایداری بیشتر نسبت به سایر الگوریتمهای مرسوم انجام دهد - . - Sun, Zhang, Ren, & Chen, 2015
-3 الگوریتمهای تکاملی
مفهوم بهینهسازی بدین صورت است که در بین پارامترهای یک تابع به دنبال مقادیری باشیم که تابع را کمینه یا بیشینه نماید. کلیه مقادیر مناسب جهت این امر را، راهحلهای ممکن و بهترین مقدار از این مقادیر را، راهحل بهینه مینامند. الگوریتمهای تکاملی هر دو نوع مسائل بیشینهسازی و کمینهسازی را پوشش میدهند. بهینهسازی همواره با مشکلات فراوانی همراه بوده است. شیوههای سابق برای حلکردن مشکلات بهینهسازی، مستلزم تلاشهای محاسباتی بیشماری است. الگوریتمهایی از جمله الگوریتمهای هوشجمعی تا حدی این مشکل را حل نمودهاند. توسط این الگوریتمها راهحلهایی پیدا میشوند کهتقریباً به جواب نزدیکند - . - Shilane, Martikainen, Dudoit, & Ovaska, 2008
