چکیده:شبکه های حسگر بیسیم مجموعهای از سنسورهای حسگر بیسیم است که در محیط به‌صورت تصادفی برای جمعآوری اطلاعات پراکنده شدهاند. مسئله انتقال بهینه‌ی داده‌ها، یکی از موارد بسیار مهم در به‌کارگیری فناوری‌های نوینی از قبیل شبکههای حسگر بیسیم چندرسانه‌ای است. اگرچه شبکههای حسگر بیسیم چندرسانه‌ای توسعه‌یافته شبکههای حسگر بیسیم هستند، اما با توجه به ماهیت این شبکه‌ها و محدودیت ذاتی حسگرها در حوزه‌های انرژی، توان محاسباتی و ظرفیت حافظه‌ای، مسئله انتقال داده‌ها در جهت تضمین پارامترهای کیفیت خدمات، با چالش‌های فراوانی روبرو خواهد شد. مجموعهای از روشهای انتقال داده در شبکههای حسگر مبتنی بر خوشهبندی حسگرها در شبکه هستند، که با افراز شبکه به تعدادی خوشهی مجزا و مدیریت سلسله مراتبی مسئله‌ی انتقال داده‌ها سعی در ساده‌سازی این مسئله دارند.در سالیان اخیر روشهای مختلفی برای ایجاد خوشه و انتخاب سر خوشهی مناسب و بهینه‌سازی انتقال داده‌ها از این طریق ارائه شده است. موارد مختلفی در حوزه‌ی وجود دارند که می‌توانند بر کیفیت انتقال داده‌ها در شبکه تأثیرگذار باشند. یکی از این موارد انتخاب بهینه‌ی گره سرخوشه برای مدیریت هر یک از خوشهها است؛ چنین گرهی علاوه بر توانایی مدیریت جریان داده‌های زیر گرههای مجموعه‌ی خود باید دسترسی مناسبی به تمام خوشهی خود و نیز به گره چاهک داشته باشد. علاوه بر این توزیع سرخوشه‌ها باید به گونه‌ای باشد که خوشه‌هایی با حجم متناسب و تعداد کافی در شبکه را تأمین نمایند. از این گذشته، عملیات خوشهبندی و انتخاب سرخوشه‌ها باید در دوره‌های زمانی مناسب و با هدف جلوگیری از تحمیل حجم کاری سنگین به تعداد محدودی از گره‌ها تکرار شود.با معرفی انواع مختلف الگوریتمهای فرا ابتکاری، روشهای نوینی برای حل مسئله‌های بهینه‌سازی به وجود آمده‌اند که آزمایش‌های تجربی حکایت از کارایی بسیار مناسب آنها در مسائلی از حوزه‌های مختلف علوم و مهندسی دارند. در این پایاننامه روشی برای انتخاب سرخوشـه مناسب بر اساس الگوریتـم فرا ابتکاری کوچ پرندگان که به‌صورت توزیعشده در شبکه حسگر بیسیم متحرک اجرا میشود، ارائه‌شده و نتایج حاصل از شبیهسازی این الگوریتم در حالتهای مختلف حرکتی آورده شده است.فهرست مطالب1- فصل اول: مقدمه.. 71-1- بیان مسئله.. 92- فصل دوم:خوشهبندی در شبکههای حسگر بیسیم.. 112-1- شبکههای حسگر بیسیم.. 112-2- کاربردهای شبکههای حسگر بیسیم.. 122-3- مسیریابی در شبکههای حسگر بیسیم.. 132-3-1- چالش‌های مسیریابی در شبکههای حسگر بیسیم.. 152-3-2- انواع مسیریابی در شبکههای حسگر بیسیم.. 172-4- خوشهبندی در شبکههای حسگر بیسیم.. 292-5- پارامترهای مهم در خوشهبندی.. 312-6- پروتکل‌های ارائه‌شده موجود.. 332-6-2- پروتکل‌های مسیریابی مبتنی بر مکان.. 452-6-3- خوشهبندی به وسیله الگوریتمهای هوشمند.. 482-7- الگوریتم کوچ پرندگان PSO.. 503- فصل سوم : الگوریتم پیشنهادی.. 543-1- شرح تابع شایستگی به کار رفته در الگوریتم کوچ پرندگان 553-1-1- مکان.. 553-1-2- انرژی.. 563-1-3- درجه پیوستگی در شبکه.. 573-1-4- تعداد دفعاتی که سرخوشه انتخاب شده است.. 583-2- مراحل الگوریتم.. 583-2-1- فاز اول.. 593-2-2- فاز دوم.. 603-2-3- فاز سوم.. 613-2-4- فاز چهارم.. 623-3- مدلهای حرکت.. 633-3-1- مدل حرکتی پیاده‌روی تصادفی.. 643-3-2- مدل حرکتی ایستگاه تصادفی.. 663-3-3- مدل حرکتی امتداد تصادفی.. 673-3-4- مدل حرکتی جامع منطقه شبیهسازی.. 683-3-5- مدل حرکتی گام‌به‌گام.. 693-3-6- مدل حرکتی حرکت هموار.. 704- فصل چهارم : نتایج شبیهسازی.. 744-1- معرفی محیط شبیهسازی.. 744-2- نتایج شبیهسازی.. 764-2-1- متوسط انرژی باقیمانده.. 774-2-2- واریانس انرژی باقیمانده.. 774-2-3- سربار پیغام کنترلی.. 784-2-4- گرههای حسگر فعال در شبکه.. 794-2-5- درصد گمشدن(نرسیدن) پیغام‌ها.. 805- فصل پنجم: نتیجه‌گیری و پیشنهادهای آینده.. 825-1- نتایج.. 825-2- پیشنهادها.. 856- مراجع.. 86 فهرست جداولعنوان جدول ........................................................................................................................... صفحهجدول 4‑1: ویژگی‌های دستگاه کامپیوتری استفاده‌شده برای شبیهسازی 74جدول 4‑2: پارامترهای اولیه تنظیم‌شده در طول شبیهسازی.. 76 فهرست اشکالعنوان شکل .................................................................................................................صفحهشکل 2‑1: مسیریابی در شبکههای حسگر بیسیم.. 14شکل 2‑2: نحوه عملکرد پروتکل SPIN]17[21شکل 2‑3: نحوه عملکرد پروتکل انتشار هدایت‌شده]12[22شکل 2‑4: عملکرد تجمیع اطلاعات در پروتکل انتشار هدایت‌شده ]12[25شکل 2‑5: ساختار شبکههای سلسله مراتبی ]23[31شکل 2‑6: ساختار پروتکل LEACH.. 35شکل 2‑7: حالتهای مختلف گره حسگر در CBHRP [40].. 40شکل 2‑8: رویه تجمع و جمعآوری داده‌ها بر مبنای زنجیره [43] 43شکل 2‑9: ساختار الگوریتم VGA]44[44شکل 2‑10: دیاگرام وضعیت‌ها در GAF [46]. 46شکل 2‑11: خوشهبندی [48].. 48شکل 3‑1: مرکز جمعیت بهترین مکان برای قرار گرفتن سرخوشه[6]. 56شکل 3‑2: فلوچارت الگوریتم.. 59شکل 3‑3: پیغامدهی در فاز اول الگوریتم.. 60شکل 3‑4: پیغامدهی در فاز دوم الگوریتم.. 61شکل 3‑5: پیغامدهی در فاز سوم الگوریتم.. 62شکل 3‑6: پیغامدهی در فاز چهارم الگوریتم.. 63شکل 3‑7: مدل حرکتی پیاده‌روی تصادفی با زمان تصادفی t[52] 65شکل 3‑8: مدل پیاده‌روی تصادفی با مسافت پیمایشی d در مسیر انتخابی[52].. 65شکل 3‑9: مدل حرکتی ایستگاه تصادفی[52].. 66شکل 3‑10: متوسط همسایگی عامل‌ها در مدل حرکتی ایستگاه تصادفی[52] 67شکل 3‑11: مدل حرکتی امتداد تصادفی.. 68شکل 3‑12: مثال از مدل حرکتی جامع منطقه شبیهسازی.. 69شکل 3‑13: اعضای خوشه و نحوه ارتباط با چاهک [5].. 72شکل 3‑14: تعداد گام ارسال از گرهی حسگر به سرخوشه[5].. 73شکل 4‑1: نمودار متوسط انرژی باقیمانده در شبکه بعد از 100 ثانیه شبیهسازی.. 77شکل 4‑2: واریانس انرژی باقیمانده در گرههای حسگر شبکه بعد از 100 ثانیه شبیهسازی.. 78شکل 4‑3: تعداد پیغام کنترلی سربار الگوریتم بعد از 200 ثانیه شبیهسازی.. 79شکل 4‑4: تعداد گرههای فعال در شبکه بعد از 200 ثانیه شبیهسازی 80شکل 4‑5: درصد گمشدن پیغام‌ها در شبکه بعد از 100ثانیه شبیهسازی 81شکل 5‑1: توزیع یکنواخت گرههای حسگر در شبکه.. 83شکل 5-2:شکل قرار گرفتن گرههای شبکه در طول شبیهسازی ……………………………. 82 1- فصل اول: مقدمهشبکههای حسگر بیسیم[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 به مروری بر تعاریف و خوشهبندی در شبکههای حسگر بیسیم و الگوریتم کوچ پرندگان می‌پردازیم و همچنین خلاصه‌ای از برخی از کارهای انجام‌شده در زمینه خوشهبندی شبکههای حسگر بیسیم را معرفی خواهیم کرد. در فصل 3، به شرح کار پژوهشی خواهیم پرداخت که شامل تعریف اولیه و شرح الگوریتم پیشنهادی خواهد بود. پس از آن در فصل 4، به شبیه‌سازی‌هایی جهت نشان دادن اثرات الگوریتم مطرح‌شده در فصل 3 بر روی پارامترهای مسیر و شبکه و انرژی می‌پردازیم. در انتها در فصل 5، نتایج به‌دست آمده مورد بررسی قرار داده خواهد شد و پیشنهاد‌هایی ارائه خواهد شد.در این فصل، در ابتدا موضوعاتی از قبیل فناوری شبکههای حسگر بیسیم، مسائل مطرح در شبکههای حسگر بیسیم، خوشهبندی کردن شبکههای حسگر بیسیم و مسیریابی در شبکههای حسگر بیسیم با توجه به خوشهبندی در شبکه و الگوریتم کوچ پرندگان مورد بررسی قرار داده خواهند شد و سپس مسئله خوشهبندی و کارهای پیشین انجام‌شده در این زمینه مورد توجه قرار خواهند گرفت.شبکههای حسگر بیسیم از تعداد زیادی حسگر تشکیل شده که وظیفه آنها جمعآوری اطلاعات، پردازش و انتقال آن به مقصد مورد نظر می‌باشد. در شبکههای حسگر ارتباط گره‌ها به صورت بیسیم و از طریق رسانه رادیویی، مادون‌قرمز و یا رسانه نوری صورت می‌گیرد. در رسانه رادیویی که بیشتر مورد استفاده قرار می‌گیرد از باندهای مختلف صنعتی، علمی و پزشکی که در اکثر کشورها آزاد است استفاده میشود. تعیین فرکانس در این رسانه با توجه به برخی محدودیت‌های سخت‌افزاری، کارایی آنتن و مصرف انرژی است. اخیراً نیز رسانه نوری به‌عنوان رسانه ارتباطی مورد توجه قرار گرفته است که ازجمله‌ی این توجهات می‌توان به استفاده از آن در ذره غبار هوشمند[16] اشاره کرد. انتخاب رسانه ارتباطی از بین این سه رسانه با توجه به محدودیت‌ها و ویژگی‌های کاربرد مورد نظر از مسائل مطرح در طراحی شبکههای حسگر است.