۶- مراجع ۸۶
فهرست جداول
عنوان جدول …………………………………………………………………………………………………………… صفحه
جدول ۴‑۱: ویژگی‌های دستگاه کامپیوتری استفاده‌شده برای شبیهسازی ۷۴
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))
جدول ۴‑۲: پارامترهای اولیه تنظیم‌شده در طول شبیهسازی ۷۶
فهرست اشکال
عنوان شکل …………………………………………………………………………………………………..صفحه
مسیریابی در شبکه‌های حسگر بیسیم ۱۴
نحوه عملکرد پروتکل SPIN ]17[ 21
نحوه عملکرد پروتکل انتشار هدایت‌شده ]۱۲[ ۲۲
عملکرد تجمیع اطلاعات در پروتکل انتشار هدایت‌شده ]۱۲[ ۲۵
ساختار شبکه‌های سلسله مراتبی ]۲۳[ ۳۱
ساختار پروتکل LEACH 35
حالت‌های مختلف گره حسگر در CBHRP [40] 40
رویه تجمع و جمع آوری داده‌ها بر مبنای زنجیره [۴۳] ۴۳
ساختار الگوریتم VGA ]44[ 44
دیاگرام وضعیت‌ها در GAF [46] 46
: خوشهبندی [۴۸] ۴۸
مرکز جمعیت بهترین مکان برای قرار گرفتن سرخوشه[۶]. ۵۶
فلوچارت الگوریتم ۵۹
پیغامدهی در فاز اول الگوریتم ۶۰
پیغامدهی در فاز دوم الگوریتم ۶۱
پیغامدهی در فاز سوم الگوریتم ۶۲
پیغامدهی در فاز چهارم الگوریتم ۶۳
مدل حرکتی پیاده‌روی تصادفی با زمان تصادفی t[52] 65
مدل پیاده‌روی تصادفی با مسافت پیمایشی d در مسیر انتخابی[۵۲] ۶۵
مدل حرکتی ایستگاه تصادفی[۵۲] ۶۶
متوسط همسایگی عامل‌ها در مدل حرکتی ایستگاه تصادفی[۵۲] ۶۷
مدل حرکتی امتداد تصادفی ۶۸
مثال از مدل حرکتی جامع منطقه شبیهسازی ۶۹
اعضای خوشه و نحوه ارتباط با چاهک [۵] ۷۲
تعداد گام ارسال از گره‌ی حسگر به سرخوشه[۵] ۷۳
نمودار متوسط انرژی باقیمانده در شبکه بعد از ۱۰۰ ثانیه شبیهسازی ۷۷
واریانس انرژی باقیمانده در گرههای حسگر شبکه بعد از ۱۰۰ ثانیه شبیهسازی ۷۸
تعداد پیغام کنترلی سربار الگوریتم بعد از ۲۰۰ ثانیه شبیهسازی ۷۹
تعداد گرههای فعال در شبکه بعد از ۲۰۰ ثانیه شبیهسازی ۸۰
درصد گمشدن پیغام‌ها در شبکه بعد از ۱۰۰ثانیه شبیهسازی ۸۱
توزیع یکنواخت گرههای حسگر در شبکه ۸۳
شکل ۵-۲:شکل قرار گرفتن گرههای شبکه در طول شبیهسازی ……………………………. ۸۲
فصل اول: مقدمه
شبکه‌های حسگر بیسیم[۱] از مجموعه‌ای حسگر بیسیم تشکیل شده است که به جهت جمع آوری اطلاعات در محیطی به فراخور کاربرد آنها پخش شده‌اند. به طور کلی شبکه‌های حسگر بیسیم جهت جمع آوری اطلاعات در مناطقی که کاربر نمی‌تواند حضور داشته باشد مورد استفاده قرار می‌گیرند [۱]. در یک شبکه حسگر، حسگرها به صورت جداگانه مقادیر محلی را نمونه‌برداری می‌کنند و این اطلاعات را در صورت لزوم برای حسگرهای دیگر و در نهایت برای مشاهده‌گر اصلی ارسال می‌نمایند. شبکه‌های حسگر بیسیم معمولاً در محیط
های سخت که دسترسی انسان به آن مکان‌ها سخت و پرهزینه است استفاده می‌شوند. از شبکه‌های حسگر بیسیم در هواشناسی، کشاورزی، زلزله‌نگاری، صنایع نظامی و جنگ‌ها، ایجاد محدوده‌ی امنیتی و … استفاده می‌شود [۱].
روند استفاده از شبکه‌های حسگر در سال‌های پایانی دهه ۸۰ و سال‌های آغازین ۹۰ توسط وزارت دفاع آمریکا، DARPA[2] و چند کشور دیگر ادامه داشت. در اواسط دهه ۹۰ با تعریف برخی استانداردها از جمله ۱۹۹۹IEEE[3] فناوری‌های تجاری هم پا به عرصه وجود گذاشتند و گروه‌های مختلف تحقیقاتی فعال در زمینه ارتباطات بیسیم وارد بازار وسیع بالقوه غیرنظامی شدند]۲[.
شبکه‌های حسگر مجموعه‌ای از تعداد بسیار زیادی گره حسگر با ابعاد کوچک و قابلیت‌های مخابراتی و محاسباتی محدود است که به منظور جمع آوری و انتقال اطلاعات از یک محیط به سمت یک کاربر و یا ایستگاه پایه[۴] به کار برده می‌شود. تفاوت اساسی این شبکه‌ها با شبکه‌ها سنتی و قدیمی، ارتباط آن با محیط و پدیده‌های فیزیکی است. شبکه‌های سنتی، ارتباط بین انسان‌ها و پایگاه‌های اطلاعاتی را فراهم می‌کنند، درحالی‌که شبکه‌های حسگر به طور مستقیم با جهان فیزیکی در ارتباط هستند. این شبکه‌ها با بهره گرفتن از حسگرها، محیط فیزیکی را مشاهده کرده و سپس بر اساس مشاهدات خود تصمیم‌گیری نموده و عملیات مناسب را انجام می‌دهند ]۳[.
شبکه حسگر بیسیم، یک نام‌گذاری عمومی برای انواع شبکه‌های مختلفی است که به‌منظور خاص طراحی می‌شوند. برخلاف شبکه‌های سنتی که همه منظوره‌اند، شبکه‌های حسگر تک منظوره‌اند. منظور از تک منظوره بودن این شبکه‌ها آن است که نیازمندی‌ها و شرایط طراحی یک شبکه حسگر بیسیم بسته به کاربرد آن متفاوت خواهد بود. درصورتی‌که گره‌ها توانایی حرکت داشته باشند، شبکه می‌تواند گروهی از ربات‌های کوچک در نظر گرفته شود که باهم به صورت تیمی کار می‌کنند و جهت مقاصد خاصی مانند بازی فوتبال طراحی شده‌اند ]۳[.
با توجه به کاربردهای متفاوت این فنّاوری و نیاز به قابلیت‌های ویژه در زمینه‌های مختلف، مسائل متعدد و زمینه‌های گوناگونی جهت حل و بهینه‌سازی آنها وجود دارد. به‌عبارت‌دیگر، در بسیاری از مسائل مطرح‌شده با تابع هدفی روبرو هستیم که می‌خواهیم آن را بهینه نماییم. ازجمله مسائل مطرح در این شبکه‌ها، مسئله مسیریابی است. به‌صورت ساده می‌توان مسئله مسیریابی را یافتن بهترین مسیر از گرههای حسگر منبع به سمت گره مقصد در نظر گرفت.
یکی از روش‌های حل مسئله مسیریابی در شبکه‌های حسگر بیسیم روش‌های خوشهبندی[۵] است. این روش به خاطر مزیت‌هایی مانند کم شدن حجم ارتباطها و پیغام‌های غیرضروری با چاهک[۶] و افزایش پهنای باند مفید و مدیریت راحت‌تر حسگرها و افزایش عمر شبکه بسیار پرکاربرد است.
در شبکه‌های حسگر بیسیم، پروتکل‌های مبتنی بر خوشهبندی از طریق تقسیم مجموعه‌ی گره‌ها به خوشه‌های مجزا و انتخاب سرخوشه‌های محلی برای ترکیب و ارسال اطلاعات جمع آوری شده هر خوشه به ایستگاه مبنا و سعی در مصرف متوازن انرژی توسط گرههای شبکه، بهترین کارایی را از نظر افزایش طول عمر و حفظ پوشش شبکه‌ای در مقایسه با سایر روش‌های مسیریابی به‌دست می‌آورد [۱].
الگوریتمهای توزیعشده به خاطر کاهش حجم اطلاعات غیرضروری به سینک و کم کردن ترافیک داده‌ای برای پیکربندی شبکه به‌ویژه در شبکه‌هایی با مقیاس بزرگ بسیار مفید هستند.
الگوریتمهای توزیعشده برای مسئله خوشهبندی نسبت به اطلاعات محلی که از گره‌ها به دست می‌آورند، کار می‌کنند. به همین خاطر حجم ارتباطات خارج از خوشه برای گرههای داخل هر خوشه به مقدار بسیار زیادی کاهش می‌یابد [۴].
امروزه یکی از روش‌های حل مسائل مختلف الگوریتمهای هوشمند ریاضی مانند شبکه عصبی و کلونی مورچگان[۷] است. یافتن سرخوشه‌های مناسب و بهینه، از بین گرههای حسگر یک مسئله پیچیده با بار محاسباتی سنگین است. در این پایان‌نامه ما مسئله خوشهبندی را در شبکه‌های حسگر بیسیم، به‌وسیله الگوریتم کوچ پرندگان (ازدحام ذرات)[۸] و بهینه‌سازی مرزی[۹] حل شده است. تابع بهینگی[۱۰] مسئله استخراج‌شده برحسب پارامترهای مکانی[۱۱] ، انرژی[۱۲]، درجه گره[۱۳] و تعداد مسیر[۱۴] تا سرخوشه‌ی حسگرها می‌باشد [۵].
در رویکردهایی که تمام محاسبات خوشهبندی در سینک انجام می‌شود بار محاسبات زیادی به سینک تحمیل می‌شود. همچنین برای جمع آوری اطلاعات اولیه از گرههای حسگر به سینک برای انجام محاسبات، پهنای باندی زیادی از شبکه هدر می‌رود.الگوریتم پیشنهادشده با رویکرد الگوریتمهای توزیعشده[۱۵]، س
رخوشه‌های مناسبی برای خوشهبندی پیشنهاد می‌دهد [۶].
بیان مسئله
انتخاب سرخوشه مناسب برای خوشه ها در الگوریتمهای توزیعشده از مسائل مهم است. به خاطر اینکه گرههای شبکه دارای دید محلی از وضعیت فعلی خود در شبکه هستند؛ نداشتن دید جامع باعث می شود تا انتخاب سرخوشه مناسب برای خوشه مشکل شود.
استفاده از الگوریتمهای هوشمند ابتکاری و فراابتکاری برای انتخاب سرخوشه مناسب یکی از راههای این مسئله است.
هدف این پایان نامه ارائه یک الگوریتم خوشهبندی توزیعشده بر اساس یک الگوریتم فرا ابتکاری به منظور انتخاب سرخوشه مناسب و بهینه در شبکه های حسگر بیسیم برای گرههای حسگر است. نتایج از اعمال مدلهای حرکتی مختلف بر روی گرههای حسگر شبکه به دست آمده است. که به تحلیل و بررسی آنها نیز در آخر پرداخته شده است.
در این پایان‌نامه در ابتدا در فصل ۲ به مروری بر تعاریف و خوشهبندی در شبکه‌های حسگر بیسیم و الگوریتم کوچ پرندگان می‌پردازیم و همچنین خلاصه‌ای از برخی از کارهای انجام‌شده در زمینه خوشهبندی شبکه‌های حسگر بیسیم را معرفی خواهیم کرد. در فصل ۳، به شرح کار پژوهشی خواهیم پرداخت که شامل تعریف اولیه و شرح الگوریتم پیشنهادی خواهد بود. پس از آن در فصل ۴، به شبیه‌سازی‌هایی جهت نشان دادن اثرات الگوریتم مطرح‌شده در فصل ۳ بر روی پارامترهای مسیر و شبکه و انرژی می‌پردازیم. در انتها در فصل ۵، نتایج به‌دست آمده مورد بررسی قرار داده خواهد شد و پیشنهاد‌هایی ارائه خواهد شد.
فصل دوم:خوشهبندی در شبکه‌های حسگر بیسیم
