است که به منظور جمع‌آوری و انتقال اطلاعات از یک محیط به سمت یک کاربر و یا ایستگاه پایه[۴] به کار برده میشود. تفاوت اساسی این شبکه‌ها با شبکه‌ها سنتی و قدیمی، ارتباط آن با محیط و پدیده‌های فیزیکی است. شبکههای سنتی، ارتباط بین انسان‌ها و پایگاه‌های اطلاعاتی را فراهم می‌کنند، درحالی‌که شبکههای حسگر به طور مستقیم با جهان فیزیکی در ارتباط هستند. این شبکه‌ها با استفاده از حسگرها، محیط فیزیکی را مشاهده کرده و سپس بر اساس مشاهدات خود تصمیم‌گیری نموده و عملیات مناسب را انجام می‌دهند ]۳[.
شبکه حسگر بیسیم، یک نام‌گذاری عمومی برای انواع شبکههای مختلفی است که به‌منظور خاص طراحی میشوند. برخلاف شبکههای سنتی که همه منظوره‌اند، شبکههای حسگر تک منظوره‌اند. منظور از تک منظوره بودن این شبکه‌ها آن است که نیازمندی‌ها و شرایط طراحی یک شبکه حسگر بیسیم بسته به کاربرد آن متفاوت خواهد بود. درصورتی‌که گره‌ها توانایی حرکت داشته باشند، شبکه می‌تواند گروهی از ربات‌های کوچک در نظر گرفته شود که باهم به صورت تیمی کار می‌کنند و جهت مقاصد خاصی مانند بازی فوتبال طراحی‌شده‌اند ]۳[.
با توجه به کاربردهای متفاوت این فنّاوری و نیاز به قابلیت‌های ویژه در زمینه‌های مختلف، مسائل متعدد و زمینه‌های گوناگونی جهت حل و بهینه‌سازی آنها وجود دارد. به‌عبارت‌دیگر، در بسیاری از مسائل مطرح‌شده با تابع هدفی روبرو هستیم که می‌خواهیم آن را بهینه نماییم. ازجمله مسائل مطرح در این شبکه‌ها، مسئله مسیریابی است. به‌صورت ساده میتوان مسئله مسیریابی را یافتن بهترین مسیر از گرههای حسگر منبع به سمت گره مقصد در نظر گرفت.
یکی از روش‌های حل مسئله مسیریابی در شبکههای حسگر بیسیم روش‌های خوشهبندی[۵] است. این روش به خاطر مزیت‌هایی مانند کم شدن حجم ارتباطها و پیغام‌های غیرضروری با چاهک[۶] و افزایش پهنای باند مفید و مدیریت راحت‌تر حسگرها و افزایش عمر شبکه بسیار پرکاربرد است.
در شبکههای حسگر بیسیم، پروتکلهای مبتنی بر خوشهبندی از طریق تقسیم مجموعه‌ی گره‌ها به خوشه‌های مجزا و انتخاب سرخوشه‌های محلی برای ترکیب و ارسال اطلاعات جمع‌آوری شده هر خوشه به ایستگاه مبنا و سعی در مصرف متوازن انرژی توسط گرههای شبکه، بهترین کارایی را از نظر افزایش طول عمر و حفظ پوشش شبکه‌ای در مقایسه با سایر روش‌های مسیریابی به‌دست می‌آورد [۱].
الگوریتمهای توزیعشده به خاطر کاهش حجم اطلاعات غیرضروری به سینک و کم کردن ترافیک داده‌ای برای پیکربندی شبکه به‌ویژه در شبکه‌هایی با مقیاس بزرگ بسیار مفید هستند.
الگوریتمهای توزیعشده برای مسئله خوشهبندی نسبت به اطلاعات محلی که از گره‌ها به دست می‌آورند، کار می‌کنند. به همین خاطر حجم ارتباطات خارج از خوشه برای گرههای داخل هر خوشه به مقدار بسیار زیادی کاهش می‌یابد [۴].
امروزه یکی از روش‌های حل مسائل مختلف الگوریتمهای هوشمند ریاضی مانند شبکه عصبی و کلونی مورچگان[۷] است. یافتن سرخوشه‌های مناسب و بهینه، از بین گرههای حسگر یک مسئله پیچیده با بار محاسباتی سنگین است. در این پایاننامه ما مسئله خوشهبندی را در شبکههای حسگر بیسیم، به‌وسیلهی الگوریتم کوچ پرندگان (ازدحام ذرات)[۸] و بهینه‌سازی مرزی[۹] حل شده است. تابع بهینگی[۱۰] مسئله استخراج‌شده برحسب پارامترهای مکانی[۱۱] ، انرژی[۱۲]، درجه گره[۱۳] و تعداد مسیر[۱۴] تا سرخوشه‌ی حسگرها می‌باشد [۵].
در رویکردهایی که تمام محاسبات خوشهبندی در سینک انجام میشود بار محاسبات زیادی به سینک تحمیل میشود. همچنین برای جمع‌آوری اطلاعات اولیه از گرههای حسگر به سینک برای انجام محاسبات، پهنای باندی زیادی از شبکه هدر می‌رود.الگوریتم پیشنهادشده با رویکرد الگوریتمهای توزیعشده[۱۵]، سرخوشه‌های مناسبی برای خوشهبندی پیشنهاد می‌دهد [۶].
| برای دانلود متن کامل پایان نامه به سایت azarim.ir مراجعه نمایید. |
بیان مسئله
انتخاب سرخوشه مناسب برای خوشهها در الگوریتمهای توزیعشده از مسائل مهم است. به خاطر اینکه گرههای شبکه دارای دید محلی از وضعیت فعلی خود در شبکه هستند؛ نداشتن دید جامع باعث میشود تا انتخاب سرخوشه مناسب برای خوشه مشکل شود.
استفاده از الگوریتمهای هوشمند ابتکاری و فراابتکاری برای انتخاب سرخوشه مناسب یکی از راههای این مسئله است.
هدف این پایاننامه ارائه یک الگوریتم خوشهبندی توزیعشده بر اساس یک الگوریتم فرا ابتکاری به منظور انتخاب سرخوشه مناسب و بهینه در شبکههای حسگر بیسیم برای گرههای حسگر است. نتایج از اعمال مدلهای حرکتی مختلف بر روی گرههای حسگر شبکه به دست آمده است. که به تحلیل و بررسی آنها نیز در آخر پرداخته شده است.
در این پایاننامه در ابتدا در فصل ۲ به مروری بر تعاریف و خوشهبندی در شبکههای حسگر بیسیم و الگوریتم کوچ پرندگان می‌پردازیم و همچنین خلاصه‌ای از برخی از کارهای انجام‌شده در زمینه خوشهبندی شبکههای حسگر بیسیم را معرفی خواهیم کرد. در فصل ۳، به شرح کار پژوهشی خواهیم پرداخت که شامل تعریف اولیه و شرح الگوریتم پیشنهادی خواهد بود. پس از آن در فصل ۴، به شبیه‌سازی‌هایی جهت نشان دادن اثرات الگوریتم مطرح‌شده در فصل ۳ بر روی پارامترهای مسیر و شبکه و انرژی می‌پردازیم. در انتها در فصل ۵، نتایج به‌دست آمده مورد بررسی قرار داده خواهد شد و پیشنهاد‌هایی ارائه خواهد شد.
فصل دوم:خوشهبندی در شبکههای حسگر بیسیم
در این فصل، در ابتدا موضوعاتی از قبیل فناوری شبکههای حسگر بیسیم، مسائل مطرح در شبکههای حسگر بیسیم، خوشهبندی کردن شبکههای حسگر بیسیم و مسیریابی در شبکههای حسگر بیسیم با توجه به خوشهبندی در شبکه و الگوریتم کوچ پرندگان مورد بررسی قرار داده خواهند شد و سپس مسئله خوشهبندی و کارهای پیشین انجام‌شده در این زمینه مورد توجه قرار خواهند گرفت.
شبکههای حسگر بیسیم
شبکههای حسگر بیسیم از تعداد زیادی حسگر تشکیل شده که وظیفه آنها جمع‌آوری اطلاعات، پردازش و انتقال آن به مقصد مورد نظر می‌باشد. در شبکههای حسگر ارتباط گره‌ها به صورت بیسیم و از طریق رسانه رادیویی، مادون‌قرمز و یا رسانه نوری صورت می‌گیرد. در رسانه رادیویی که بیشتر مورد استفاده قرار می‌گیرد از باندهای مختلف صنعتی، علمی و پزشکی که در اکثر کشورها آزاد است استفاده میشود. تعیین فرکانس در این رسانه با توجه به برخی محدودیت‌های سخت‌افزاری، کارایی آنتن و مصرف انرژی است. اخیراً نیز رسانه نوری به‌عنوان رسانه ارتباطی مورد توجه قرار گرفته است که ازجمله‌ی این توجهات میتوان به استفاده از آن در ذره غبار هوشمند[۱۶] اشاره کرد. انتخاب رسانه ارتباطی از بین این سه رسانه با توجه به محدودیت‌ها و ویژگی‌های کاربرد مورد نظر از مسائل مطرح در طراحی شبکههای حسگر است.
کاربردهای شبکههای حسگر بیسیم
از ویژگی‌های مناسب یک فن یا یک سامانه، قابلیت استفاده از آن در سناریوها و کاربردهای متعدد و مختلف می‌باشد. مخصوصاً اگر یک سامانه بتواند وظیفه خود را به‌صورت مستقل و کامل انجام دهد و قابلیت تبادل اطلاعات با سایر سامانه‌ها از طریق پروتکلهای استاندارد را داشته باشد. شبکههای حسگر بیسیم برای مشاهده و بررسی آماری یک یا چند هدف معین در محیط مدنظر می‌باشد. با توجه به ویژگی‌های ذاتی شبکههای حسگر میتوان از آنها در کاربردهای مختلف استفاده کرد. از این کاربردها میتوان به موارد زیر اشاره نمود [۱، ۳، ۷]:
کاربرد نظامی:
از کاربرد این فناوری در حوزه نظامی میتوان به مواردی از قبیل جمع‌آوری اطلاعات از وضعیت میدان نبرد، کنترل ابزارآلات نظامی، تشخیص و ره‌گیری اهداف، شناسایی حملات شیمیایی و هسته‌ای اشاره نمود.
شناسایی محیط‌های آلوده:
در محیط‌های مختلف امکان وجود آلودگی‌های مختلفی است. لذا با استفاده از چنین شبکه‌هایی میتوان وجود آلودگی‌های مشخصی را در سطح محیط تحت نظر، چک کرد و حتی میزان غلظت آلودگی در قسمت‌های مختلف را بررسی نمود.
محیط زیست:
بررسی محیط‌زیست، یکی از زمینه‌هایی است که شبکههای حسگر می‌توانند در آن کاربرد فراوانی داشته باشند. از مثال‌هایی که در این زمینه میتوان نام برد، مطالعه پاسخ گیاهان در شرایط مختلف دمایی و بیماری مربوط به آنها، ردگیری و اندازه‌گیری جمعیت پرندگان و غیره می‌باشد.
کاربرد صنعتی:
استفاده از شبکههای حسگر بیسیم در صنعت، به طور قابل توجه‌ای در حال افزایش است. این فناوری با توجه به قابلیت‌های فراوانی که دارد، امکان به‌کارگیری در نقاط مختلف یک مجتمع صنعتی و انجام وظایف متنوع را دارا می‌باشد. از جمله این موارد میتوان به جمع‌آوری اطلاعات، حفاظت و کنترل ایمنی محیط، مدیریت انبارداری و زنجیره تأمین، نظارت بر خط تولید، نظارت بر کنترل کیفیت، بهبود سامانه‌های پشتیبانی و کنترل فرآیندهای صنعتی اشاره نمود. استفاده از این فناوری در صنعت علاوه بر اینکه باعث افزایش کیفیت و میزان تولید می‌گردد، کاهش هزینه‌های نصب، نگهداری و تولید را نیز می‌تواند به دنبال داشته باشد.
جاده‌ها و بزرگراه‌های هوشمند:
امروزه یکی از مشکلات بزرگ شهری، کنترل وضعیت ترافیک در سطح شهر می‌باشد. با برپایی شبکه‌ای از گرههای حسگر در سطح شهر و قرار دادن گره‌ها در بزرگراه‌ها و خیابان‌های شهر میتوان بزرگراه‌ها و خیابان‌ها را هوشمند ساخت و از وضعیت تراکم عبور و مرور وسایل نقلیه و یا بروز حوادث در نقاط تحت نظر گرههای حسگر، اطلاع یافت و در نهایت در کل سطح شهر وضعیت ترافیک و تصادفات را شناسایی و پیگیری نمود.
کاربرد پزشکی:
این فناوری در پزشکی نیز کاربردهای متعددی از جمله مراقبت از بیماران و نظارت بر سلامتی آنها از طریق اندازه‌گیری و یا کنترل پارامترهای مختلف بدن، تشخیص بیماری‌ها، کمک به پزشکان در جراحی‌ها و کارهای حساس را دارد.
مسیریابی در شبکههای حسگر بیسیم
حسگرها به دو صورت با سینک ارتباط برقرار می‌کنند: مستقیم و غیرمستقیم. در مستقیم هر حسگر با سینک بدون درگیر کردن دیگر حسگرها تبادل اطلاعات و ارتباط دارد. این موضوع باعث میشود که محدوده شبکه کوچک شود و فقط به اندازه توان حسگر برای ارتباط با محیط اطراف باشد. در ارتباط غیرمستقیم برای ارتباط بین دو حسگر درون شبکه، بقیه حسگرهای میانی بین دو گره مبدأ و مقصد به عنوان مسیر ارتباط به کار گرفته میشوند. شکل ۲-۱ نشان‌دهنده این نوع ارتباط است. همه اطلاعات جمع‌آوری شده به‌وسیله حسگرها باید به یک مرکز جمع‌آوری کننده اطلاعات منتقل شوند. فواصل طولانی‌تر، انرژی بیشتری در ارسال اطلاعات مصرف می‌کنند. در ارسال مستقیم هر حسگر مستقیماً اطلاعات را به مرکز می‌فرستد. شبکههای ارسال مستقیم برای طراحی بسیار ساده و سرراست می‌باشند، اما به دلیل فاصله زیاد حسگرها از مرکز انرژی زیادی مصرف می‌کنند.
شکل ۲‑۱: مسیریابی در شبکههای حسگر بیسیم
به منظور مقابله با کمبودها و نقص‌های ناشی از این روش، تبادل داده بین حسگرها و گره چاهک، معمولاً روش‌های انتقال بسته چند-پرشی[۱۷] و بر روی شعاع ارتباطی کوچک انجام میشود ]۸[. چنین روش انتقال داده‌ای، منجر به صرفه‌جوئی مشخص در مصرف انرژی و کاهش چشمگیری در تداخل مخابراتی بین گرههای حسگر که در رقابت برای دسترسی به کانال هستند، میشود. در مقابل طراحی‌هایی که فواصل ارتباطی را کوتاه‌تر می‌کنند، می‌توانند دوره حیات شبکه را طولانی‌تر کنند. در این نوع ارتباط مسائلی مثل مسیریابی، خوشهبندی و مشخصاً بهینه‌سازی مطرح نمی‌باشد. در ارتباط به صورت غیرمستقیم هر حسگر به عنوان مبدأ تولیدکننده پیغام برای مقصد عمل می‌کند که مقصد می‌تواند هر کدام از دیگر حسگرها یا سینک اطلاعات باشد. در بین مبدأ و مقصد هر کدام از حسگرها به عنوان برقرارکننده مسیر می‌توانند مطرح شوند. چنین روش انتقال داده‌ای، منجر به صرفه‌جوئی مشخص در مصرف انرژی و کاهش چشمگیری در تداخل مخابراتی بین گرههای حسگر که در رقابت برای دسترسی به کانال هستند، میشود.
چالش‌های مسیریابی در شبکههای حسگر بیسیم
برخلاف برنامه‌های بی‌شمار ارائه‌شده برای شبکههای حسگر، این‌گونه شبکه‌ها دارای محدودیت‌هایی نیز می‌باشند، که به عنوان نمونه میتوان به مواردی همانند محدودیت انرژی، محدودیت قدرت محاسباتی و محدودیت پهنای باند اشاره نمود. یکی از مهم‌ترین اهداف طراحی شبکههای حسگر افزایش طول عمر گرههای حسگر با استفاده از کاهش مصرف انرژی در جهت انتقال اطلاعات می‌باشد ]۹[. پروتکلهای مسیریابی در شبکههای حسگر تحت تاثیر عوامل مختلفی مورد چالش قرار گرفته است. در ادامه به بررسی برخی از این موضوع‌های چالش‌برانگیز خواهیم پرداخت.
استقرار گره‌ها در شبکههای حسگر بیسیم به مواردی همانند نوع برنامه کاربردی مورد استفاده و عملکرد پروتکل مسیریابی بستگی دارد. استقرار گره‌ها به دو صورت کاملاً تصادفی و قطعی امکان‌پذیر است. در حالت قطعی، گرههای حسگر به صورت دستی در مکان مورد نظر قرار داده خواهند شد و داده‌ها به کمک مسیرهای از پیش تعیین‌شده انتقال خواهند یافت. بااین‌وجود در حالت تصادفی، گرههای حسگر به صورت کاملاً تصادفی در فضای شبکه قرار خواهند گرفت. اگرچه توزیع تصادفی گرههای حسگر امکان ایجاد مسیرهای مطلوب، جهت انتقال داده را کاهش خواهد داد اما با استفاده از پروتکلهای خوشهبندی مناسب میتوان باعث کاهش مصرف انرژی گرههای حسگر شد]۱۰[.
گرههای حسگر، می‌توانند منابع انرژی محدودشان را در هنگام انجام محاسبات و یا انتقال اطلاعات در یک محیط بیسیم مصرف کنند. لذا به کارگیری روش‌های مختلف برای صرفه‌جوئی در انرژی در هنگام انجام محاسبات و ارتباطات بسیار ضروری است. از طرفی طول عمر گرههای حسگر، وابستگی بسیار زیادی به طول عمر باتری دارد. در یک شبکه حسگر چندگامه، هر گره نقش دوگانه‌ای را به عنوان فرستنده و جهت دهنده داده ایفا می‌کند. بد عمل کردن اغلب گرههای حسگر به علت کمبود توان می‌تواند منجر به تغییرات توپولوژیکی در شبکه شود که ممکن است نیاز به مسیریابی مجدد بسته‌ها را به وجود بیاورد. در حقیقت یکی از چالش‌های مهم در طراحی الگوریتمهای مسیریابی در این‌گونه شبکه‌ها آن است که با مصرف انرژی گره‌ها و کاهش یافتن آنها، دقت شبکه پایین نیاید ]۱۰[.
حس کردن داده و گزارش دهی داده حس شده، در شبکههای حسگر بیسیم به کاربرد مورد استفاده و زمان بحرانی قابل‌قبول برای گزارش‌دهی داده مورد نظر وابسته است. مدلهای مختلف گزارش‌دهی داده می‌توانند به دسته‌های وابسته به زمان، پیوسته، وابسته به اتفاق، وابسته به پرس‌وجو و ترکیبی دسته‌بندی شوند]۱۱[. مدل تحویل داده وابسته به زمان، برای کاربردهایی مناسب است که نیاز به کنترل و نظارت بر داده به صورت متناوب دارند. برای این منظور گرههای حسگر به صورت متناوب بر روی حسگرها و فرستنده‌های خود سوئیچ خواهند کرد و محیط اطراف را حس کرده و داده مورد نظر را در فواصل زمانی متناوب ثابت انتقال می‌دهند. در مدلهای وابسته به پرسش و اتفاق، گره‌ها به تغییرات ناگهانی شدیدی که در مقدار یک صفت خاص که به علت رخداد یک اتفاق خاص و یا یک پرسش ایجادشده به وسیله ایستگاه پایه به وجود آمده است، بلافاصله عکس‌العمل نشان می‌دهند. این مدل‌ها برای کاربردهایی که زمان برای آنها یک عامل بحرانی است، بسیار مناسب هستند. همچنین ممکن است ترکیبی از مدلهای قبلی را برای مدل‌سازی گزارش‌دهی داده استفاده کنند. پروتکلهای مسیریابی به وسیله مدلهای گزارش‌دهی داده و مصرف انرژی و پایداری مسیر عمیقاً تحت تاثیر قرار می‌گیرند]۱۰٫[