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