بخشی از مقاله
چکیده
شبکه های حسگر، نسل جدیدی از شبکه ها هستند که به طور معمول، از تعداد زیادی گره ارزان قیمت تشکیل شده اند و ارتباط این گره ها به صورت بی سیم صورت می گیرد. هدف اصلی در این شبکه ها، جمع آوری اطلاعاتی در مورد محی پیرامون حسگر های شبکه است. نحوه عملکرد کلی این شبکه ها به این صورت است که گره ها اطلاعات مورد نیاز را جمع آوری می کنند و سپس آنها را به سمت گیرنده ارسال می کنند. خوشهبندی فرآیندی است، که شبکه حسگر را به گروههای مختلف، تقسیم میکند. اغلب، سرخوشهها که در هر گروه شناسایی میشود مسئولیت جمع آوری و پردازش دادهها از همه اعضای گروه را برعهده دارند و آنها را برای ایستگاه مرکزی میفرستند. این پایاننامه رویکردی مبتنی بر الگوریتم Leach برای خوشهبندی دادهها ارائه میدهد، که در آن با بکار بردن الگوریتم تکاملی جهش قورباغه برای انتخاب سرخوشه، دوره حیات شبکه را طولانیتر میکند. نتایج شبیه سازی نشان میدهد در مقایسه با الگوریتم Leach، الگوریتم پیشنهادی مصرف انرژی را به حداقل میرساند و طول عمر شبکه را تقریبا 30 به افزایش میدهد.
کلمات کلیدی: شبکه حسگر بیسیم،WSN، خوشه بندی، الگوریتم جهش قورباغه.
1 مقدمه
شبکههای حسگر بیسیم از تعداد زیادی دستگاههای ارزان قیمت که از طریق زیر سیستمهای ارتباطی بیسیم شبکه میباشند تشکیل میشود که بهصورت تصادفی در مناطق دوردست یا مناطق خطرناک پخش میشوند. در این شبکهها ایستگاه پایه - BS - به اینترنت متصل است و اغلب قویتر از گرههای حسگر است زیرا انرژی آن از برق شهر یا منبع انرژی دیگر تامین میشود. ایستگاه اصلی، بر حسب لزوم دادههای حسشده توس گرههای حسگر را جمعآوری کرده و آن را به کاربران ارسال میکند. معماری شبکههای حسگر بیسیم در شکل 1 نشان داده شده است. این شبکهها تاثیر مهمی در کارایی بسیاری از موضوعات کاربردی، نظیر نظارت محیطی، پیش بینی حوادث طبیعی، بهداشت و درمان، تولید و حمل و نقل دارند
.2 بیان مساله
هدف اصلی این شبکه ها، جمع آوری اطلاعات از محی پیرامون حسگر های شبکه است، نحوه عملکرد کلی این شبکه به این صورت می باشد که حسگرها اطلاعات مورد نیاز را جمع آوری کرده و سپس به سمت گیرنده ارسال می کند. نکته مهم در این شبکه ها وجود منابع محدود انرژی جهت ارسال می باشد و مساله مهم استفاده بهینه از باتری نودها می باشد که با بهینه تر کردن ارسال و دریافت داده ها طول عمر شبکه بیشتر خواهد شد. با توجه به این محدودیت، الگوریتم و پروتکل های مختلفی جهت خوشه بندی و ارسال اطلاعات در نظر گرفته شده است.ایجاد کنترل روی تعداد و مکان سرخوشه ها و همچنین اندازه خوشه ها از نظر تعداد اعضا همواره به عنوان یک چالش مطرح بوده است و حل این مسئله نیازمند الگوریتم های خوشه بندی کارا در مصرف انرژی و متعادل کننده بار شبکه میباشد . - Huifang et al, 2006 - در این پژوهش با استفاده از الگوریتم جهش قورباغه، محل سرخوشه ها را به نحوی تعیین کنیم که حداقل مصرف انرژی را در شبکه داشته باشیم. معیار برازش بر اساس حداقل انرژی کم شده - مصرف شده - از گره-های شبکه در طی هر نسل خواهد بود.
.3 ادبیات و پیشینه تحقیق
در - Gupta et al, 2013 - ، نیز یک الگوریتم مسیریابی مبتنی بر GA به نام GARارائه می شودکه درآن فاصله ارتباطی کلی از گذرگاه ها بهBS ،کمینه میشود. علاوه بر آن،این الگوریتم با الگوریتم - Bari et al, 2009 - از نظرمسائلی که در ادامه بیان می شود، متفاوت است. اول اینکه در این روش برای انتخاب والدین، در مقایسه با - Bari et al, 2009 - که از روش انتخاب چرخه رولت استفاده می کند، از روش انتخاب تورنمنت استفاده می شود. دراین روش تابع هدف بر حسب فاصله کلی که یک راند را پوشش می دهد، تعریف می شود در حالی که در - Bari et al, 2009 - تابع هدف بر اساس طول عمر شبکه بر حسب تعداد راند تعریف می شود.در فاز جهش، این روش، گره رله ای را انتخاب کرده که از ماکزیمم فاصله برای ارسال داده هابه همسایه اش استفاده میکند در حالی که در - Bari et al, 2009 - گره بحرانی برای اینکار تعریف میشود.
بااین حال، هر دو الگوریتم فق مسیریابی داده های جمع شده از گذرگاه هابه BS را بررسی میکنندو ارتباط داده ها از گرههای حسگر به گذرگاه های درون هر خوشه را در نظر نمی گیرند. علاوه بر آن، این الگوریتم ها انرژی باقیمانده گره ها که منجر به عدم کارایی جدی انرژی می شود را بررسی نمی کنند. در - - Chakeaborty and Das, 2012 ، Chakrabortyو همکارانش ارزیابی ای متفاوت مبتنی بر الگوریتم مسیریابی برای بیش از یک هزار گره رله را انجام دادند که در آن ماکزیمم مصرف انرژی گره رله کمینه می شود.همچنین در این الگوریتم تشکیل خوشه بندی مورد توجه قرار نمی گیرد. بعضی از خوشه بندی های نامناسب منجر به عدم کارایی جدی در انرژی گره های رله می شود .
Hussainو همکارانش ، یک GA مبتنی بر الگوریتم خوشه بندی سلسله مراتبی ارائه داده اند که در آن یک مجموعه سرخوشه از گره های حسگر معمولی - مانند and Bara, 2011 - - - Enan با تابع هدفی متفاوت انتخاب میشود - 2007 Huruiala . - Hussain et al, وهمکارانش یک GA مبتنی برالگوریتم مسیریابی و خوشه بندی ارائه داده اند که در آن سرخوشه بهینه را انتخاب کرده و فاصله ارسال را به حداقل می رسانند - Jin . - Huruiala et al, 2010 و همکارانش ، روشی را برای یافتن سرخوشه ها بر اساس یک تابع هدف ارائه داده اند که فاصله کلی ارسال در شبکه را به حداقل می رساند. در اینجا از GA تنها برای انتخاب سرخوشه استفاده می شود. هر گره غیر سرخوشه از یک روش قطعی برای یافتن نزدیک ترین سرخوشه به خودش، استفاده می کند - Mudundi . - Jin et al, 2003 یک الگوریتم خوشه بندی ژنتیک - GCA - پیشنهاد داده اند که در آن خوشه ها به شکلی پویا تشکیل می شوند.
هدف این الگوریتم، افزایش طول عمر شبکه با به حداقل رساندن اتلاف انرژی است. تابع هدف با استفاده از تعداد گره های سرخوشه و فاصله اقلیدسی بین همه گره های یک خوشه تا سرخوشه شان با داشتن مقدار وزن، ارائه می شود. هر چند این روش با انتخاب سرخوشه و پیوستن همه گره های حسگر غیر سرخوشه به نزدیکترین سرخوشه ها،خوشه ها راتشکیل می دهد اماتوازن انرژی سرخوشه هارادر نظر نمی گیرد. علاوه بر آن این روش، تنها فاصله اقلیدسی بین سرخوشه ها یا BS را بررسی می کند و به پارامترهای دیگری مثل انرژی باقی مانده و توازن بار توجه ای نمی کند - . - Mudundi and Ali, 2007 از بهینه سازی ازدحام ذرات - PSO - و بهینه سازی کولونی مورچه - ACO - نیزدرشبکه های حسگراستفاده شده است al, 2012 - - - Zungeru e. - Kulkarni and Venayagamoorthy , 2011 -
.4 الگوریتم جهش قورباغه
الگوریتم جهش ترکیبی قورباغه متاهیوریستیک است. الگوریتم Sfla قورباغه ها سرچشمه می گیرد. این یک الگوریتم مبتنی بر ممتیک از نحوه ی جستجوی غذای گروه الگوریتم برای جستجوی محلی میان
