بخشی از مقاله
چکیده
امروزه علاوه بر بهدستآوردن دادههای مناسب برای تمام رشتهها، دقت در اندازهگیری آنها نیز از اهمیت فوقالعادهای برخوردار است. بههمین منظور استفاده از حسگرها نقش بهسزایی در ثبت این دادهها ایفا میکنند. حسگرهای بیسیم ازجمله مناسبترین راهکارهای جمعآوری داده در دنیا محسوب میشوند. اطلاعات جمعآوری شده بهوسیله حسگرها باید به یک ایستگاه پایه منتقل شوند. در ارسال مستقیم، هر حسگر مستقیماً اطلاعات را به مرکز میفرستد. بهدلیل فاصله زیاد حسگرها از مرکز، انرژی زیادی مصرف میکنند. در مقابل طراحیهایی که فواصل ارتباطی را کوتاهتر میکنند، میتوانند دوره حیات شبکه را طولانیتر کنند.
بنابراین خوشهبندی بهینه ومصرف انرژی مستقیماً طول عمر شبکه حسگر را تحت تأثیر قرار میدهد. در این مقاله خوشهبندی بهینه گرههای حسگر در جهت کاهش توان مصرفی گرههای حسگر از طریق اتصال بهینه گرههای حسگر به گرههای سرخوشه با استفاده از الگوریتمهای تکاملی انجام شده است و یک کدگذاری مطلوب برای پاسخ در نظر گرفته شده و یک تابع هدف مبتنی بر خوشهبندی بهینه با حداقل توان مصرفی در گرههای حسگر تعریف شده است. نتایج حاکی عملکرد بهینه الگوریتم بهینهسازی علفهای هرز در خوشهبندی بهینه گرهها با حداقل توان مصرفی در شبکه حسگر دارد.
واژگان کلیدی: خوشهبندی، شبکه حسگر، الگوریتم علفهای هرز، الگوریتم ازدحام ذرات.
مقدمه
در سالهای اخیر، استفاده از شبکههای حسگر بی سیم در بخشهای گوناگون به سرعت در حال گسترش است. برای مثال این شبکهها در نظارت و جمع آوری اطلاعات مربوط به آتش سوزی، بلایای طبیعی مانند زلزله و موارد پزشکی و نظامی، کاربردهای بسیاری دارند . - Henrique et al, 2014 - در این شبکه ها، گرههای حسگر اغلب به علت اندازه کوچک با محدودیتهایی مواجه هستند مانند قدرت پردازش و منبع انرژی محدود. این محدودیتها باعث شده است که محققان در طراحی این شبکهها مطالعات گستردهای انجام دهند. اطلاعات جمعآوری شده بهوسیله حسگرها باید به یک ایستگاه پایه منتقل شوند. در ارسال مستقیم، هر حسگر مستقیماً اطلاعات را به مرکز میفرستد.
بهدلیل فاصله زیاد حسگرها از مرکز، انرژی زیادی مصرف می-شود - . - Rajagopalan and Varshney, 2006 در مقابل طراحیهایی که فواصل ارتباطی را کوتاهتر میکنند، میتوانند دوره حیات شبکه را طولانیتر کنند. هرچه گرهها در فاصله بیشتری نسبت به گره سرخوشه قرار گرفته باشند زمان و توان مصرفی بیشتری مصرف میکنند تا انتقال اطلاعات به سرخوشه انجام دهند. بنابراین خوشهبندی بهینه گرههای حسگر از طریق اتصال آنها به نزدیکترین گره سرخوشه درجهت کاهش توان مصرفی شبکه بهعنوان یک مسأله بهینهسازی مطرح میشود. الگوریتمهای مختلفی برای اتصال بهینه گرهها در شبکههای حسگر بیسیم ارائه شده است. اما مرتبه زمانی این الگوریتمها با بزرگشدن ابعاد شبکه و تعداد گرهها افزایشیافته و هزینه زیادی برای بدست آوردن پاسخ بهینه نیاز است.
زمانبربودن الگوریتمهای کلاسیک باعث می شود کارایی مناسبی در حل این مسأله نداشته باشند. بنابراین نیاز به استفاده از الگوریتمهایدیگری است که در زمان قابل قبول، پاسخ مناسبی برای این مسأله بدست آوردند. از جمله این الگوریتمهای مناسب، الگوریتمهای تکاملی هستند . - Goyal, 2014 - ادامه ساختار این مقاله به این صورت است که در بخش دوم مروری بر پیشینه تحقیقات انجامشده خواهیم داشت و در بخش سوم الگوریتمهای تکاملی بیان میشوند. در بخش چهارم مدل پیشنهادی و ارزیابی نتایج استفاده از الگوریتمهای تکاملی در جهت حل مسأله ارائه میشود و در نهایت در بخش آخر نتیجهگیری انجام میشود.
-2 مروری بر پیشینه تحقیق
ماریام و همکاران در سال 2015 در مقالهای تحت عنوان الگوریتم خوشهبندی کارا برای شبکههای حسگر بیسیم، از الگوریتمی برای درجهبندی گرهها برای انتخاب سرخوشهها استفاده کردند. سرخوشهها براساس سطوح انرژی و موقعیت گره نسبت به پایگاه انتخاب میشوند از پایگاه به عنوان چاهک برای جمعآوری اطلاعات استفاده میشود. به دلیل اینکه پایگاه تعداد منحنیهای سرخوشه را محاسبه میکند درنتیجه سرخوشه ثابت است و برایند آن کاهش مقدار انرژی تلفشده حین جایگزینی سرخوشههای هر منحنی است و طول عمر شبکه حسگر از این طریق افزایش مییابد. کارایی روش پیشنهادی با الگوریتمهای متداول دیگر در این زمینه از طریق معیارهای مختلفی مورد ارزیابی واقع شد که نشان از بهتربودن روش تا %15 نسبت به روش PEGASIS و تا %70 نسبت به روش LECH است - . - Alnuaimi et al, 2015 شیوان جین و همکاران در مقالهای تحت عنوان بهینهسازی شبکه حسگر با استفاده از الگوریتم ژنتیک یک روش برای حل این مسأله پیشنهاد دادند .
این مسأله ارتباط راه دور بین حسگرها و مقاصدشان در یک شبکه حسگر میتواند انرژی زیادی را مصرف کند. همینطور عمر مفید شبکه را کاهش دهد. با خوشهبندی یک شبکه حسگر در داخل خوشههای مستقل با استفاده از الگوریتم ژنتیک میتوان کل فاصله ارتباطی و همینطور عمر شبکه را افزایش داد. شبیهسازیهای انجام شده نشان داد که الگوریتم به سرعت راهحل بهینه را پیدا میکند. روش پیشنهادی برای توپولوژیهای چند شبکه یا بهینهسازی کوتاهترین فاصله کاربرد دارد - Jin et al, .2003 - دیمین و همکاران در سال 2013 در مقالهای تحت عنوان مکانیابی بهینه برای شبکه حسگر بیسیم با استفاده ازالگوریتم ژنتیک چندهدفه به بررسی نحوه انتقال دادهها که همه حسگرها را نیاز دارد تا به یک گره انتقال که دارای انرژی زیاد مصرفی است، وصل شود که این گره به عنوان یک تقویتکننده سیگنال از زمین به ماهواره عمل میکند.
این حسگرها با فرض اینکه دارای فاصله ثابت و همینطور برد ثابتی میباشند. این شبکه به عنوان یک معیاری برای ارزیابی الگوریتم ژنتیک چندهدفه برای مکانیابی حسگرها در نظر گرفته شده است که دو هدف برای بهینهسازی در آن - 1 پوشش کل حسگر و - 2 طول عمر شبکه میباشد. سپس این الگوریتم بردهای نسبی مختلفی استفاده شد که در نتیجه در مکانیابی مختلف از این طریق بهدست آمد که در یکی از آنها حسگرها به یکدیگر بسیار نزدیک بودند و در دومی به شکل hub-and-spock چیده شده بودند که نرخ برد برقراری ارتباط به عنوان یک عامل متمایزکننده نشان داده شد - . - Damien et al, 2004 یونگ ژو و همکارش در مقاله تحت عنوان روشی با استفاده از الگوریتم ژنتیک برای چیدمان بهینه حسگرها در شبکههای حسگر بیسیم که دارای موانع اولویتبندی است به ارائه راهحلی جدید و مؤثر با استفاده از الگوریتم ژنتیک پرداختند که در آن شبکهای با کمترین تعداد حسگرها ساخته شده که نسبت به سایر الگوریتمهای تکاملی به نتایج بهتری دست پیدا کرد - Xu and Xin, .2006 -
ابینگکو در مقالهای تحت عنوان مکانیابی گرههای شبکه حسگر بیسیم با استفاده از الگوریتم ژنتیک برای پوشش-دهی حداکثر شبکه و با محدودیت کمکردن انرژی موردنیاز برای چیدمان شبکه مبادرت کرد. اهداف الگوریتم کل مسافت طی-شده حسگرها از مکانهای اولیه به مکانهای نهایی و همینطور سطح پوشش حسگرها را در بر میگرفت که این شبیهسازی نشان داد که تعادلی بین مسافت طیشده و سطح پوشش برقرار است. این مقاله نشان میدهد یک پوشش بهتر نیازمند مسافت طیشده بیشتر است. همینطور مسافت طیشده به موقعیت اولیه حسگرها بستگی دارد - . - Yipeng and Stavros, 2011 ژیاکیانگ ژو و همکاران در مقالهای تحت عنوان مکانیابی گرهها براساس الگوریتم ژنتیک بهینه در شبکههای حسگر بیسیم یک راهحل جدیدی را ارائه دادند. روش پیشنهادی یک الگوریتم مکانیابی الگوریتم ژنتیک را با فناوری GPS ترکیب میکرد.
اولین گام در این الگوریتم داشتن مکان دقیق گرهها با استفاده از GPS و گرههایی که مکان آنها نامعلوم است توسط الگوریتم ژنتیک مکانیابی میشوند. در مرحله دوم مکان گرهها با استفاده از گرههایی که دارای مکان نامعلوم هستند مکانیابی میشوند که توسط دو قسمت مجزا این دو مرحله پیادهسازی شدهاند. قسمت اول ایجاد جمعیت اولیه برای الگوریتم ژنتیک برای گره-هایی که به صورت تصادفی در فضا توزیع شدهاند و قسمت محاسبه تابع برازش و ضرایب تغییر و قسمت دیگر که انتخاب بهینه محلی توسط شبیهسازی مکانیزم تکاملی بر طبق این دو قسمت کل فرایند مکانیابی گرهها در شبکه حسگر انجام میشود. نتایج از موثربودن این روش برای گرههایی که دارای مکان نامعلوم هستند و دقت مکانیابی بالا و صرف هزینه انرژی کمتر دارد - . - Zhiqiang et al, 2014
ژوژون لیو در سال 2014 در مقالهای تحت عنوان الگوریتم مورچگان همراه با مکانیزم مهاجرت حریصانه برای مکانیابی گرهها در شبکه حسگر به بررسی مسأله پوشش شبکه با حداقل هزینه و قابلیت اتصال مطمئن پرداخت. روش پیشنهادی با استفاده از الگوریتم مورچگان مسأله پوشش شبکه و کاهش هزینه مکانیابی را مورد هدف قرار داد. این الگوریتم شعاع - برد - برقراری ارتباط را تنظیم میکرد تا از این طریق مسأله بهینهسازی انرژی و طول عمر شبکه را بهبود دهد. شبیهسازی نشان داد روش پیشنهادی هزینه مکانیابی را کاهش و تعادل بین مصرف انرژی میان گرههای و افزایش طول عمر شبکه در شبکه حسگر برقرار میکند - . - Xuxun and Desi, 2014 کائو در سال 2015 در مقالهای تحت عنوان روشی برای مکانیابی براساس الگوریتم بهینهسازی ازدحام ذرات و الگوریتم کواسی- نیوتن برای شبکههای حسگر ارائه دادند. در این روش از الگوریتم PSO برای یافتن جوابها و مقادیر بهینه استفاده شد سپس از این مقادیر در مرحله تکرار به عنوان مقادیر ورودی برای الگوریتم کواسی- نیوتن استفاده شد. نتایج شبیهسازی بیانگر آن است الگوریتم پیشنهادی در مکانیابی گرهها موفق بوده است - . - Cao, 2015
