3-3-1- مدل حرکتی پیاده روی تصادفی……………………… 64
3-3-2- مدل حرکتی ایستگاه تصادفی……………………… 66
3-3-3- مدل حرکتی امتداد تصادفی……………………… 67
3-3-4- مدل حرکتی جامع منطقه شبیه سازی……………………… 68
3-3-5- مدل حرکتی گام به گام…………………….. 69
3-3-6- مدل حرکتی حرکت هموار…………………….. 70
4- فصل چهارم : نتایج شبیه سازی……………………… 74
4-1- معرفی محیط شبیه سازی……………………… 74
4-2- نتایج شبیه سازی…………………….. 76
4-2-1- متوسط انرژی باقی مانده…………………….. 77
4-2-2- واریانس انرژی باقیمانده…………………….. 77
4-2-3- سربار پیغام کنترلی……………………… 78
4-2-4- گره های حسگر فعال در شبکه…………………….. 79
4-2-5- درصد گم شدن(نرسیدن) پیغام ها……………………. 80
5- فصل پنجم: نتیجه گیری و پیشنهادهای آینده……………. 82
5-1- نتایج……………………… 82
5-2- پیشنهادها……………………. 85
6- مراجع……………………… 86
چکیده:
شبکههای حسگر بیسیم مجموعه ای از سنسورهای حسگر بیسیم است که در محیط به صورت تصادفی برای جمعآوری اطلاعات پراکنده شدهاند. مسئله انتقال بهینه ی داده ها، یکی از موارد بسیار مهم در به کارگیری فناوری های نوینی از قبیل شبکه های حسگر بی سیم چندرسانه ای است. اگرچه شبکه های حسگر بی سیم چندرسانه ای توسعه یافته شبکه های حسگر بی سیم هستند، اما با توجه به ماهیت این شبکه ها و محدودیت ذاتی حسگرها در حوزه های انرژی، توان محاسباتی و ظرفیت حافظه ای، مسئله انتقال داده ها در جهت تضمین پارامترهای کیفیت خدمات، با چالش های فراوانی روبرو خواهد شد. مجموعهای از روشهای انتقال داده در شبکه های حسگر مبتنی بر خوشهبندی حسگرها در شبکه هستند، که با افراز شبکه به تعدادی خوشه ی مجزا و مدیریت سلسله مراتبی مسئله ی انتقال داده ها سعی در ساده سازی این مسئله دارند.
در سالیان اخیر روشهای مختلفی برای ایجاد خوشه و انتخاب سر خوشهی مناسب و بهینه سازی انتقال داده ها از این طریق ارائه شده است. موارد مختلفی در حوزه ی وجود دارند که می توانند بر کیفیت انتقال داده ها در شبکه تأثیرگذار باشند. یکی از این موارد انتخاب بهینه ی گره سرخوشه برای مدیریت هر یک از خوشه ها است؛ چنین گرهی علاوه بر توانایی مدیریت جریان داده های زیر گره های مجموعه ی خود باید دسترسی مناسبی به تمام خوشه ی خود و نیز به گره چاهک داشته باشد. علاوه بر این توزیع سرخوشه ها باید به گونه ای باشد که خوشه هایی با حجم متناسب و تعداد کافی در شبکه را تأمین نمایند. از این گذشته، عملیات خوشه بندی و انتخاب سرخوشه ها باید در دوره های زمانی مناسب و با هدف جلوگیری از تحمیل حجم کاری سنگین به تعداد محدودی از گره ها تکرار شود.
با معرفی انواع مختلف الگوریتم های فرا ابتکاری، روش های نوینی برای حل مسئله های بهینه سازی به وجود آمده اند که آزمایش های تجربی حکایت از کارایی بسیار مناسب آنها در مسائلی از حوزه های مختلف علوم و مهندسی دارند. در این پایاننامه روشی برای انتخاب سرخوشـه مناسب بر اساس الگوریتـم فرا ابتکاری کوچ پرندگان که به صورت توزیع شده در شبکه حسگر بیسیم متحرک اجرا می شود، ارائه شده و نتایج حاصل از شبیه سازی این الگوریتم در حالتهای مختلف حرکتی آورده شده است.
فصل اول: مقدمه
شبکه های حسگر بی سیم[1] از مجموعه ای حسگر بی سیم تشکیل شده است که به جهت جمع آوری اطلاعات در محیطی به فراخور کاربرد آنها پخش شده اند. به طور کلی شبکه های حسگر بی سیم جهت جمع آوری اطلاعات در مناطقی که کاربر نمی تواند حضور داشته باشد مورد استفاده قرار می گیرند [1]. در یک شبکه حسگر، حسگرها به صورت جداگانه مقادیر محلی را نمونه برداری می کنند و این اطلاعات را در صورت لزوم برای حسگرهای دیگر و در نهایت برای مشاهده گر اصلی ارسال می نمایند. شبکه های حسگر بی سیم معمولاً در محیط های سخت که دسترسی انسان به آن مکان ها سخت و پرهزینه است استفاده می شوند. از شبکه های حسگر بی سیم درهواشناسی، کشاورزی، زلزله نگاری، صنایع نظامی و جنگ ها، ایجاد محدوده ی امنیتی و … استفاده می شود [1].
روند استفاده از شبکه های حسگر در سال های پایانی دهه 80 و سال های آغازین 90 توسط وزارت دفاع آمریکا، DARPA[2] و چند کشور دیگر ادامه داشت. در اواسط دهه 90 با تعریف برخی استانداردها از جمله 1999IEEE[3] فناوری های تجاری هم پا به عرصه وجود گذاشتند و گروه های مختلف تحقیقاتی فعال در زمینه ارتباطات بی سیم وارد بازار وسیع بالقوه غیرنظامی شدند]2[.
شبکه های حسگر مجموعه ای از تعداد بسیار زیادی گره حسگر با ابعاد کوچک و قابلیت های مخابراتی و محاسباتی محدود است که به منظور جمع آوری و انتقال اطلاعات از یک محیط به سمت یک کاربر و یا ایستگاه پایه[4] به کار برده می شود. تفاوت اساسی این شبکه ها با شبکه ها سنتی و قدیمی، ارتباط آن با محیط و پدیده های فیزیکی است. شبکه های سنتی، ارتباط بین انسان ها و پایگاه های اطلاعاتی را فراهم می کنند، درحالی که شبکه های حسگر به طور مستقیم با جهان فیزیکی در ارتباط هستند. این شبکه ها با استفاده از حسگر ها، محیط فیزیکی را مشاهده کرده و سپس بر اساس مشاهدات خود تصمیم گیری نموده و عملیات مناسب را انجام می دهند ]3[.
شبکه حسگر بی سیم، یک نام گذاری عمومی برای انواع شبکه های مختلفی است که به منظور خاص طراحی می شوند. برخلاف شبکه های سنتی که همه منظوره اند، شبکه های حسگر تک منظوره اند. منظور از تک منظوره بودن این شبکه ها آن است که نیازمندی ها و شرایط طراحی یک شبکه حسگر بی سیم بسته به کاربرد آن متفاوت خواهد بود. درصورتی که گره ها توانایی حرکت داشته باشند، شبکه می تواند گروهی از ربات های کوچک در نظر گرفته شود که باهم به صورت تیمی کار می کنند و جهت مقاصد خاصی مانند بازی فوتبال طراحی شده اند ]3[.
با توجه به کاربردهای متفاوت این فنّاوری و نیاز به قابلیت های ویژه در زمینه های مختلف، مسائل متعدد و زمینه های گوناگونی جهت حل و بهینه سازی آنها وجود دارد. به عبارت دیگر، در بسیاری از مسائل مطرح شده با تابع هدفی روبرو هستیم که می خواهیم آن را بهینه نماییم. ازجمله مسائل مطرح در این شبکه ها، مسئله مسیریابی است. به صورت ساده می توان مسئله مسیریابی را یافتن بهترین مسیر از گره های حسگر منبع به سمت گره مقصد در نظر گرفت.
یکی از روش های حل مسئله مسیریابی در شبکه های حسگر بی سیم روش های خوشه بندی[5] است. این روش به خاطر مزیت هایی مانند کم شدن حجم ارتباطها و پیغام های غیرضروری با چاهک[6] و افزایش پهنای باند مفید و مدیریت راحت تر حسگرها و افزایش عمر شبکه بسیار پرکاربرد است.
در شبکه های حسگر بی سیم، پروتکل های مبتنی بر خوشه بندی از طریق تقسیم مجموعه ی گره ها به خوشه های مجزا و انتخاب سرخوشه های محلی برای ترکیب و ارسال اطلاعات جمع آوری شده هر خوشه به ایستگاه مبنا و سعی در مصرف متوازن انرژی توسط گره های شبکه، بهترین کارایی را از نظر افزایش طول عمر و حفظ پوشش شبکه ای در مقایسه با سایر روش های مسیریابی به دست می آورد [1].
الگوریتم های توزیع شده به خاطر کاهش حجم اطلاعات غیرضروری به سینک و کم کردن ترافیک داده ای برای پیکربندی شبکه به ویژه در شبکه هایی با مقیاس بزرگ بسیار مفید هستند.
الگوریتم های توزیع شده برای مسئله خوشه بندی نسبت به اطلاعات محلی که از گره ها به دست می آورند، کار می کنند. به همین خاطر حجم ارتباطات خارج از خوشه برای گره های داخل هر خوشه به مقدار بسیار زیادی کاهش می یابد [4].
امروزه یکی از روش های حل مسائل مختلف الگوریتم های هوشمند ریاضی مانند شبکه عصبی و کلونی مورچگان[7] است. یافتن سرخوشه های مناسب و بهینه، از بین گره های حسگر یک مسئله پیچیده با بار محاسباتی سنگین است. در این پایان نامه ما مسئله خوشه بندی را در شبکه های حسگر بی سیم، به وسیلهی الگوریتم کوچ پرندگان (ازدحام ذرات)[8] و بهینه سازی مرزی[9] حل شده است. تابع بهینگی[10] مسئله استخراج شده برحسب پارامترهای مکانی[11] ، انرژی[12]، درجه گره[13] و تعداد مسیر[14] تا سرخوشه ی حسگرها می باشد [5].
در رویکردهایی که تمام محاسبات خوشه بندی در سینک انجام می شود بار محاسبات زیادی به سینک تحمیل می شود. همچنین برای جمع آوری اطلاعات اولیه از گره های حسگر به سینک برای انجام محاسبات، پهنای باندی زیادی از شبکه هدر می رود.الگوریتم پیشنهادشده با رویکرد الگوریتم های توزیع شده[15]، سرخوشه های مناسبی برای خوشه بندی پیشنهاد می دهد [6].
2-1- بیان مسئله
انتخاب سرخوشه مناسب برای خوشهها در الگوریتمهای توزیعشده از مسائل مهم است. به خاطر اینکه گرههای شبکه دارای دید محلی از وضعیت فعلی خود در شبکه هستند؛ نداشتن دید جامع باعث میشود تا انتخاب سرخوشه مناسب برای خوشه مشکل شود.
استفاده از الگوریتمهای هوشمند ابتکاری و فراابتکاری برای انتخاب سرخوشه مناسب یکی از راههای این مسئله است.
هدف این پایاننامه ارائه یک الگوریتم خوشهبندی توزیعشده بر اساس یک الگوریتم فرا ابتکاری به منظور انتخاب سرخوشه مناسب و بهینه در شبکههای حسگر بیسیم برای گرههای حسگر است. نتایج از اعمال مدلهای حرکتی مختلف بر روی گرههای حسگر شبکه به دست آمده است. که به تحلیل و بررسی آنها نیز در آخر پرداخته شده است.
در این پایان نامه در ابتدا در فصل 2 بهی بر تعاریف و خوشه بندی در شبکه های حسگر بی سیم و الگوریتم کوچ پرندگان می پردازیم و همچنین خلاصه ای از برخی از کارهای انجام شده در زمینه خوشه بندی شبکه های حسگر بی سیم را معرفی خواهیم کرد. در فصل 3، به شرح کار پژوهشی خواهیم پرداخت که شامل تعریف اولیه و شرح الگوریتم پیشنهادی خواهد بود. پس از آن در فصل 4، به شبیه سازی هایی جهت نشان دادن اثرات الگوریتم مطرح شده در فصل 3 بر روی پارامترهای مسیر و شبکه و انرژی می پردازیم. در انتها در فصل 5، نتایج به دست آمده مورد بررسی قرار داده خواهد شد و پیشنهاد هایی ارائه خواهد شد.
[1] Wireless Sensor Network
[2] Defense Advanced Research Projects Agency
[3] Engineers Institute of Electrical and Electronics
[4] Base Station
[5] Clustering
