بخشی از مقاله
چکیده
حوزههای مطالعاتی اخیر شبکههای سنسوری بیسیم چالشهای جدیدی را برای توسعه دهندگان پروتکلهای این شبکهها به ارمغان آورده است. مصرف انرژی و پوشش شبکه ای، دو چالش مهم در شبکههای سنسوری بیسیم هستند. ما در این مقاله، به بررسی یک روش هوشمند به منظور تعیین موقعیت گره، جهت کاهش مصرف انرژی با پوشش شبکهای بالا، پرداختهایم. از الگوریتم ژنتیک Genetic Algorithm - یا - GA به منظور ایجاد مکاندهی اولیه با مصرف بهینه انرژی در شبکه سنسوری بیسیم استفاده شده است. نتایج شبیهسازی نشان میدهد که الگوریتم هوشمند پیشنهادی میتواند طول عمر شبکه را برای روشهای مختلف مکاندهی شبکه گسترش دهد.
.1 مقدمه
شبکههای بیسیم و موبایل - متحرک - گزینهای مناسب برای مواردی است که ما به محیط دسترسی نداریم و در این شرایط است که پردازش داده یک چالش خواهد بود. شبکههای حسگر بیسیم در مواردی که کاربر نمیتواند دادهها را متقیماًس وارد یا جمعآوری کند، دارای اهمیت خاصی خواهد بود. یک شبکه حسگر بیسیم شامل تعدادی گره کوچک مشابه است که در یک ناحیه محدود با یکدیگر در تعاملند. هر گره، یه یک باتری به عنوان منبع انرژی نیاز دارد. زمان حیات باتریها، چرخه حیات یک شبکه را مشخص میکند و به همین دلیل بهرهوری از انرژی فاکتوری مهم برای داشتن طول حیات بیشتر یک شبکه خواهد بود 10]و .[5 به منظور دستیابی به این هدف، میتوان از خوشهبندی استفاده کرد.
روشهای متنوع و گوناگونی برای رسیدن به این هدف وجود دارد. که هینزلمن - Heinzelman - و همکاران [1] پروتکل Leach را معرفی کردند که ایدهای برای خوشهبندی هیوریستیک - ابتکاری - خودسازمانده است که در آن هر شبکه به تعدادی خوشه تقسیم میشود. هر خوشه دارای گرهای خاص به عنوان سرخوشه و تعدادی گره دیگر است. گرهها دادهها را جمعآوری کرده و آنها را به سرخوشه منتقل میکنند و سرخوشه نیز دادههای جمعآوری شده را دریافت نموده و آنها را از طریق TDMA1 به سینک - Sink - ارسال میکند. این ایده توسط T.Voit و همکاران در [6] بکار گرفته شد و به عنوان الگوریتم خوشهبندی SolarLeach گسترش یافت.
ایدههای دیگری نیز برای خوشهبندی با استفاده از الگوریتمهای ابتکاری وجود دارد. به عنوان مثال، الگوریتم 7] HCR و [8 توسط متین - Matin - و حسین - Hussain - ارائه شد که در آن، گرهها با استفاده از تکنیک Round Robin خود را به عنوان سرخوشه معرفی میکنند. با توجه به اینکه گرههای حسگر در موقعیتهای ثابتی باشند، خوشهبندی گرهها را میتوان به هدف بهینهسازی فاکتورهایی از قبیل انرژی، پوشش شبکه، فاصله بین خوشهها، ارتباط بین گرهها و غیره انجام داد.
ما در این مقاله، یک روش جدید برای مکانیابی گره ها با استفاده از الگوریتم ژنتیک و خوشهبندی به روش k-means ارائه میکنیم. ساختار ادامه مقاله به صورت زیر است: ابتدا الگوریتم ژنتیک و روش استفاده از آن را به طور خلاصه شرح میدهیم. سپس یک الگو برای موقعیتیابی گره با توجه به فاکتورهای تناسب ارائه خواهیم کرد. در آخر نیز، نتایج شبیه-سازی ارائه و با سایر روشهای موجود که در بخش 4 آمدهاند، مقایسه خواهند شد.
.2 پیشینه الگوریتم ژنتیک
الگوریتم ژنتیک یکی از انواع الگوریتمهای تکاملی الهام گرفته از زیستشناسی است. در این الگوریتم اطلاعات به عنوان کروموزوم جمعآوری شده و با عملیات ویژهای نظیر توارث2، جهش3، انتخاب4 و تقاطع5 ترکیب میشوند. بهترین کروموزوم موجود در جمعیت، با توجه به یک تابع برازش6 مربوط به هدف مسأله، انتخاب میشود .[9] به طور معمول یک روش بهینهسازی با استفاده از الگوریتم ژنتیک، شامل موارد زیر است:
.1,2 جمعیت
الگوریتم ژنتیک در مجموعهای از راهحلها که جمعیت نامیده میشود، کار میکند. افراد این جمعیت یک سری از اعداد به نام کروموزوم هستند که شامل دادههای باینری از پارامترهای جواب میباشند.
.2,2 تابع برازش
این تابع یک شاخص برای عملکرد فرد در ناحیه مسأله در اختیار ما قرار میدهد. به عنوان مثال، در مسألهای که هدف آن کمینهسازی است، بهترین فرد، فردیست که کمترین مقدار را دارد. این اطلاعات خام به عنوان یک مرحله میانی برای تعیین کارایی نسبی فرد در الگوریتم ژنتیک اعمال میشوند.
.3,2 انتخاب
انتخاب مرحلهایست که تعیین میکند که هر فرد چندبار میتواند در مرحله تولیدمثل شرکت کند. به بیان دیگر، تعداد فرزندانی که هر والد میتواند تولیدمثل کند، در این مرحله مشخص میشود.
.4,2 تقاطع
تقاطع عامل اصلی در توسعه نسل جدید است. فرزندان منتج از این مرحله مانند کروموزومهای واقعی، بخشی از اطلاعات والدین خود را حمل میکنند. تکنیکهای تقاطع بسیاری وجود دارد که سادهترین نوع آن تقاطع یک نقطهای و دیگری تقاطع چند نقطهای است. در تقاطع یک نقطهای، هر والد از یک قسمت خاص، به دو بخش تقسیم میشود، سپس دو فرزند از مبادله یک بخش از هر والد ایجاد میشود. در تقاطع چند نقطهای، چندین نقطه شکست در کروموزومها انتخاب میشوند. هر والد بر اساس تعداد نقاط شکست به چندین بخش تقسیم میشود.
.5,2 جهش
در طبیعت جهش مرحلهای است که در آن یک بخش از کروموزوم به طور تصادفی تغییر میکند. در الگوریتم ژنتیک، جهش در کروموزومها با احتمال 0/01 تا 0/001 درنظر گرفته میشود. با این روش انتظار میرود که کروموزومهای خوبی که در مرحله انتخاب یا تولیدمثل حذف شدهاند، دوباره احیا شوند. جهش همچنین تضمین میکند که جمعیتها با یکدیگر مشابه نباشند. بنابراین GA میتواند از دستیابی به کمینههای محلی جلوگیری کند.
.3 روش پیشنهادی
جین - Jin - و همکاران [4] یک روش مبتنی بر الگوریتم ژنتیک ارائه کردهاند که ارتباط بین گرهها را در یک شبکه از پیش موقعیتیابی شده، به هدف کمینهسازی انرژی کاهش میدهد. Ferentinus و همکاران در [12] این ایده را با تغییر تابع برازش بهبود بخشیدند. در الگوریتم آنها، سرخوشهها در هر خوشه بر اساس انرژی و سطح ارتباطاتشان با سایر گرهها انتخاب میشوند. اگر گرهها در شبکههای حسگر بیسیم ثابت باشند، امکان حل برخی از مسائل نظیر مصرف انرژی و هزینه ارتباطات بین گرهها، با استفاده از مکاندهی مناسب در مقداردهی اولیه شبکه، وجود دارد. با مکاندهی مناسب میتوان هزینه ارتباطات را کاهش داد. بین مصرف انرژی گرهها و پوشش شبکه یک مصالحه وجود دارد.
