قابلیت حرکت حسگرها و سرخوشهها: اگر فرض کنیم که گرهها و سرخوشهها ساکن و بدون حرکت هستند، به طور طبیعی با خوشههای متعادل و ثابتی مواجه میشویم که مدیریت شبکهای درون خوشهها و میان خوشهها تسهیل شده است. در مقابل اگر گرهها و سرخوشهها را سیار در نظر بگیریم، عضویت در خوشهها برای هر گره به صورت پویا تغییر میکند. در این شرایط خوشهها در هر دوره عضوگیری میکنند.
انواع گرهها و نقش آنها: در برخی از مدلهای شبکه مانند محیطهای ناهمگن، فرض میشود که سرخوشهها نسبت به دیگر گرهها، با منابع ارتباطی و محاسباتی بیشتری تجهیز شدهاند [۳۳]. در مقابل در بسیاری از مدلهای شبکه، همه گرهها قابلیتهای یکسانی دارند و تنها زیرمجموعهای از این گرهها به عنوان سرخوشه برگزیده میشوند.
انتخاب سرخوشهها: در برخی الگوریتمهای پیشنهادشده، سرخوشهها از قبل تعیین میشوند. درحالیکه در بسیاری موارد سرخوشهها از میان گرههای پراکندهشده، به روشهای احتمالاتی یا به روشهای کاملاً تصادفی و یا بر اساس معیارهای خاص دیگری مانند انرژی باقیمانده و یا قابلیت اتصال انتخاب میشوند.
همپوشانی[۴۴]: برخی پروتکلها، توجه ویژهای به مفهوم همپوشانی گره در کلاسهای مختلف در جهت کارایی بهتر مسیریابی یا برای اجرای سریعتر پروتکل شکلدهی خوشه، دارند. اما باید به این نکته اشاره کرد که اکثر پروتکلهای شناختهشده، سعی در کمینه کردن همپوشانی و یا عدم پشتیبانی از همپوشانی را دارند.
برای دانلود فایل متن کامل پایان نامه به سایت ۴۰y.ir مراجعه نمایید. |
پروتکلهای ارائهشده موجود
راههای مختلفی جهت متمایز کردن و دستهبندی الگوریتمهای خوشهبندی در شبکههای حسگر بیسیم وجود دارد. دو دستهبندی رایج این نوع الگوریتمها عبارتاند از: الگوریتمهای خوشهبندی در شبکههای همگن و ناهمگن که بر پایهی مشخصه و کارکرد گرههای حسگر در شبکه استوار است. و الگوریتمهای خوشهبندی متمرکز و توزیعشده که بر روش شکلدهی خوشه استوار است.
در شبکههای حسگر ناهمگن، در حالت کلی دو نوع حسگر وجود دارد. نوع اول: حسگرهایی با قابلیت پردازشی بالاتر و سختافزار پیچیدهتر که به طور کلی جهت ایجاد نوعی ستون فقرات در شبکههای حسگر بیسیم استفاده میشوند. این حسگرها از قبل به عنوان سرخوشههای تعیینشده، جمعکننده دادهها و پردازشکننده دادههای دریافتی از سایر گرههای حسگر معمولی هستند. نوع دوم گره معمولی با قابلیتهای کمتر هستند که برای حسکردن خواص مورد نظر از محیط استفاده میشوند.
در شبکههای حسگر همگن همهی گرهها مشخصات، قابلیتها ، و توان پردازشی یکسانی دارند. در این شبکهها که امروزه زیاد استفاده میشوند هر گره میتواند سرخوشه باشد.در این نوع شبکهها نقش سرخوشه میتواند به صورت دورهای بین گرهها عوض شود.
دستهبندی متعارف دیگر، ایستا بودن و پویا بودن خوشهبندی است. رویه شکلدهی خوشه هرگاه شامل انتخاب مجدد سرخوشهها به صورت منظم یا شامل سازماندهی مجدد خوشهها باشد، پویا است. این رویهها ممکن است به منظور نشان دادن عکسالعمل مؤثر به تغییرات توپولوژی شبکه و با هدف گردش صحیح نقش سرخوشهها و در نتیجه تنظیم صحیح توپولوژی خوشهها در میان گرهها و کسب کارایی بیشتر و مصرف متوازن انرژی باشد. معماریهای پویا برای مسئله خوشهبندی، سبب استفاده بهتر از حسگرها و به طور طبیعی موجب مدیریت بهتر مصرف انرژی و طول عمر شبکه میشوند.
بیشتر الگوریتمهای شناختهشده در مبحث خوشهبندی به دو دسته اصلی احتمالاتی و قطعی تقسیم میشوند. این دستهبندی بر اساس معیارهای شکلدهی کلاس و پارامترهای استفادهشده جهت انتخاب سرخوشه صورت میگیرد. در الگوریتمهای خوشهبندی احتمالاتی، جهت تعیین سرخوشههای آغازین، یک احتمال به هر گره تخصیص داده میشود که به عنوان معیار اصلی تصمیمگیری در مورد انتخاب سرخوشه به شمار میرود. بااینحال ممکن است معیارهای ثانوی دیگری هم چه در خلال فرایند انتخاب سرخوشه مانند انرژی باقیمانده و چه در طول فرایند شکلدهی خوشه مانند نزدیکی و یا هزینه ارتباط، وجود داشته باشند. الگوریتمهای خوشهبندی احتمالاتی، فراتر از ایجاد بهینگی مصرف انرژی معمولاً باعث سریعتر شدن زمان اجرا، همگرایی و کاهش حجم پیامهای تبادلی میگردند.
زمانی که همهی گرهها قابلیت یکسانی دارند؛ فرایند انتخاب سرخوشه و ایجاد خوشه به صورت توزیعشده، صحیحترین فن در راستای کسب انعطافپذیری بیشتر در مقابل تغییرات توپولوژی شبکه است.
در الگوریتمهای خوشهبندی غیر احتمالی، اصولاً معیارهای ویژه بیشتری برای انتخاب سرخوشهها و شکلدهی خوشهها مورد توجه قرار میگیرند. این معیارها اساساً مبتنی بر نزدیکی و مجاورت گرهها و اطلاعات دریافتشده از گرههای همسایه میباشند. بنابراین در برخی موارد منجر به پیچیدگی زمانی بدتر نسبت به الگوریتمهای خوشهبندی احتمالاتی میشوند. درعینحال این الگوریتمها به هنگام مواجهه با وضعیتهای پیشبینینشده و همچنین در مورد توازن کلاسها قابلاطمینانتر هستند.
زمانهای سریعتر اجرا و همگرایی مستقل از تعداد گرهها از ویژگیهای الگوریتمهای توزیعشده میباشد. در مقابل تعداد کمی از فنهای متمرکزشده یا ترکیبی استفاده میشوند که در آنها یک یا چند هماهنگکننده یا ایستگاه مبنا، مسئول تفکیککردن تمامی شبکه به صورت منفصل و کنترل عضویت در خوشهها هستند. این رویکردها برای کاربردهای عملی شبکههای وسیع حسگر بیسیم مناسب نیستند.
در ادامه برخی از الگوریتمهای استفادهشده جهت خوشهبندی را مورد بررسی قرار میدهیم.
پروتکل LEACH [۴۵]
یکی از مشهورترین پروتکلهای کلاسبندی ارائهشده برای شبکههای حسگر بیسیم میباشد. این پروتکل از اولین پروتکلهای کلاسبندی پویاست که به طور ویژه نیازهای شبکههای حسگر را در نظر گرفته است. این پروتکل از گرههای حسگر ساکن همگن که به طور تصادفی پخش شدهاند استفاده میکند. LEACH به عنوان مبنایی برای دیگر پروتکلهای پیشرفته کلاسبندی در WSNها در نظر گرفته میشود. به طور کلی این پروتکل، یک پروتکل سلسله مراتبی، احتمالی، توزیع یافته و تک-گام است که با اهداف افزایش طول عمر شبکههای WSN از طریق توزیع مصرف انرژی در میان تمام گرههای شبکه و کاهش مصرف انرژی در گرههای شبکه با انجام عمل تجمیع داده و در نتیجه آن کاهش تعداد پیامهای تبادلاتی، طراحی شده است. LEACH کلاسها را با استفاده از الگوریتمهای توزیعشده شکل میدهد که در آن گرهها به طور مستقل و بدون کنترل متمرکز تصمیمگیری میکنند. بهمنظور توازن انرژی مصرفشده در هر گره در هر دور کامل، همه گرهها شانس سرگروه شدن را دارند. در ابتدا یک گره با احتمال P تصمیم میگیرد که سرگروه شود و این تصمیم را پخش فراگیر میکند. پس از انتخاب سرگروه، همه سرگروهها یک پیام اعلانی به دیگر گرهها پخش فراگیر میکنند و هر گره کلاسی را که میخواهد عضو آن باشد، مشخص میکند. هر گره کلاس خود را به گونهای مشخص میکند که بتواند با کمترین انرژی، با سرگروه آن کلاس ارتباط برقرار کند. این کار بر اساس قدرت سیگنال پیام ارسالشده هر سرگروه صورت میگیرد. LEACH قادر است یک توازن مناسب مصرف انرژی به وسیله چرخش تصادفی سرگروهها ایجاد نماید که موجب افزایش طول عمر شبکه میشود. بااینوجود و علیرغم مزایای این پروتکل، اشکالاتی هم دارد. به دلیل اینکه تصمیمگیری در مورد انتخاب سرگروهها و چرخش آنها احتمالاتی است، بنابراین فرصت برای انتخاب گرههای کم انرژی به عنوان سرگروه کماکان وجود دارد. به همین دلیل ممکن است سرگروههای انتخابی در یک منطقه خاصی از شبکه متمرکز باشند. بنابراین در این پروتکل، توزیع مناسب سرگروهها قابل تضمین نیست و برخی گرهها هیچ سرگروهای در محدوده خود نخواهند داشت [۳۵].
شکل ۲-۶ ساختار کلی شبکه را به صورت خوشهبندی در الگوریتم LEACH نشان میدهد.
شکل ۲‑۶: ساختار پروتکل LEACH
پروتکل LEACH متمرکز[۴۶]
الگوریتم کلاسبندی است که در آن تشکیل کلاسها به صورت متمرکز و توسط گره چاهک انجام میگیرد. این الگوریتم مرحله انتقال داده مشابه با الگوریتم LEACH دارد و در طی آن هر گره اطلاعاتی در مورد موقعیت و سطح انرژی کنونی خود را به گره چاهک ارسال میکند. معمولاً این طور فرض میشود که هر گره از GPS برخوردار است. گره چاهک باید توزیع یکنواخت انرژی در بین کلاسها را تضمین کند. بنابراین آستانهای برای سطح انرژی تعیین نموده و گرههایی که انرژی بیشتر از آستانه تعیینشده دارند را به عنوان سرگروههای احتمالی انتخاب میکند. مسئلهی تعیین تعداد بهینهی سرگروهها یک مسئلهی NP-Hard است. گره چاهک بعد از تعیین سرگروههای دور جاری، پیغامی حاوی شماره شناسایی سرگروه را به هر گره ارسال میکند. اگر شماره شناسایی سرگروه گرهای با شماره شناسایی خودش تطابق داشته باشد، آن گره یک سرگروه است وگرنه یک گره عادی است و میتوان تا مرحله انتقال داده مربوط به خود به حالت خواب فرو رود.LEACH-C کاراتر از LEACH بوده و به ازای هر واحد انرژی، در حدود ۴۰ درصد دادهی بیشتری را انتقال میدهد. زیرا گره چاهک دانش سراسری در مورد موقعیت و سطح انرژی گرههای شبکه دارد. از این گذشته LEACH-C برخلاف LEACH، وجود تعداد بهینه خوشهها را در هر دور تضمین میکند]۳۶[.
پروتکل خوشهبندی پیوندگرای وفقی با انرژی پایین[۴۷]
پروتکلی مبتنی بر LEACH-C است، که در آن مرحله تشکیل کلاسها بصورت متمرکز و توسط گره چاهک به روشی مشابه با LEACH-C صورت میگیرد. LEA2C از روش کلاسبندی دو مرحلهای SOM و K-means استفاده میکند.
ورودیهای SOM، مختصات گرههای حسگر در فضای شبکه هستند. LEA2C آموزش پیوندگرا را از طریق به حداقل رساندن فاصله بین نمونههای ورودی (مختصات گرههای حسگر) و نمونههای اولیه نقشه (ارجاعها) که توسط تابع همسایگی خاصی وزندهی شدهاند، اعمال میکند. بعد از مرحلهی کلاسبندی، سرگروههای هر کلاس بر اساس یکی از سه شرط انتخاب میشوند]۳۶[:
گرهی دارای بیشترین سطح انرژی.
نزدیکترین گره به گره چاهک.
نزدیکترین گره به مرکز ثقل کلاس.
پس از آن مرحله انتقال داده شروع میشود و گرههای عادی بستههای خود را به سرگروهها مربوطه ارسال میکنند و سرگروهها پس از مجتمع کردن دادههای دریافتی آنها را در قالب یک بسته به گره چاهک انتقال میدهند. در حالتی که از معیار گرهی دارای بیشترین انرژی برای انتخاب سرگروه استفاده شده باشد. پروتکل بعد از هر مرحله انتقال، نقش سرگروه را به گرهی دیگری واگذار خواهد کرد. مرحله انتقال تا زمان رخداد اولین مرگ گرههای شبکه ادامه خواهد یافت. بعد از رخ دادن اولین مرگ، مرحله کلاسبندی مجدد آغاز شده و مراحل قبلی تکرار خواهند شد. نتایج شبیهسازی، برتری LEA2C را بر پروتکل مبتنی بر LEACH دیگر بنام EECS به اثبات رسانده است]۳۷، ۳۸[. این برتری برحسب افزایش ۵۰ درصدی در طول عمر شبکه و حفظ پوشش شبکهای در طول ۹۰ درصد عمر شبکه میباشد.
پروتکل LLACA [۴۸]:
این پروتکل با هدف از بین بردن اثرات منفی تغییرات مکرر توپولوژی شبکه در کلاسها طراحی شده است. این پروتکل متشکل از دو فاز میباشد. در فاز اول، پروتکل شبکه مورد نظر را خوشهبندی مینماید. فاز دوم، فاز خوشهبندی دوباره در صورت نیاز و فاز حفظ خوشههای موجود تا جایی که امکان دارد میباشد. بخش خوشهبندی این پروتکل، یک الگوریتم کاملاً توزیعشده میباشد که در آن هر گره بر اساس اطلاعات محلی که از همسایگانش دریافت میکند، تصمیمی در مورد سرخوشه شدن میگیرد. این الگوریتم به طور مستقل بر روی هر یک از گرهها اجرا میشود. از مزایای این الگوریتم آن است که اگر خوشهها اعتبار خود را از دست دادند، میتوانند به صورت محلی خود را سازماندهی مجدد کنند. فاز ابتدایی این پروتکل شامل چندین مرحله میباشد که در هر مرحله، هر گره از ما بین گرههای در ارتباط با خود یک گره را بهعنوان سرخوشه مشخص مینماید یا آنکه نقش سرخوشه را به خودش میدهد. پس از انتهای فاز ابتدایی پروتکل هر گره نقش خود را میداند که یا سرخوشه است و یا عضوی از یک خوشه میباشد]۳۹[.
در شبکههای حسگر به علت حرکت برخی از حسگرها و یا خراب شدن آنها، توپولوژی شبکه حالت پویا دارد. یک گره میتواند به طور تصادفی به هر جای شبکه منتقل شود و از عضویت یک خوشه خارج شود و عضو خوشه دیگری شود. بنابراین هر پروتکل کلاسبندی نیاز به یک فاز خوشهبندی دوباره دارد. در LLACA زمانی که یک گره قصد دارد به عضویت یک خوشه دربیاید یک پیام JREQ به سمت گرههای همسایه خود ارسال میکند و برای یک بازه زمانی منتظر میماند. هر سرخوشهای که پیام ارسال شده را دریافت نمود یک پیام JREP به سمت گره درخواستکننده ارسال میکند. در این بازه زمانی ۳ حالت زیر امکان دارد به وقوع بپیوندد]۳۹[:
اگر گره درخواستکننده تنها یک پیام JREP دریافت کند، در این صورت فرستنده پیام را به عنوان سرخوشه خود انتخاب مینماید و یک پیام CHSEL به سمت آن ارسال مینماید.
اگر بیشتر از یک پیام JREP دریافت کند، در این صورت گرهای را که دارای شماره ID بالاتری میباشد را به عنوان سرخوشه انتخاب مینماید و یک پیام CHSEL به سمت آن ارسال مینماید.
اگر گره درخواستکننده پیام JREP را از هیچ گرهای دریافت نکند، در این صورت آن یکی از همسایگان خود را که دارای بالاترین شماره ID میباشد را به عنوان سرخوشه انتخاب مینماید و یک پیام CHSEL به سمت آن ارسال میکند.
نکته آخر که باید در این پروتکل به آن توجه شود آن است که، هر گره یا دارای نقش سرخوشه است و یا به عنوان عضوی از یک خوشه میباشد. با توجه به این مسئله زمانی که یک گره قصد ترک خوشه خود را دارد با توجه به نقش خود پیامهای کنترلی متفاوتی ایجاد مینماید. اگر گره دارای نقش سرخوشه باشد در این صورت یک پیام خوشهبندی مجدد به اعضای کلاس خود ارسال میکند و از آنها میخواهد که عمل خوشهبندی را مجدد انجام دهند. اما اگر گره تنها عضوی از خوشه بوده در زمان ترک خوشه خود تنها یک پیام ترک خوشه به سمت همسایگان خود ارسال میکند]۳۹[.
پروتکل CBHRP [۴۹]
یک پروتکل دولایهای است که در آن مفهوم سرخوشه([۵۰]H-S)، بهجای سرگروه معرفی و پیشنهادشده است. هر مجموعه سرخوشه، شامل یک سرگروه فعال و تعدادی سرگروه همیار میباشد. در هر لحظه تنها یک عضو H-S فعال است و بقیه در حالت خواب هستند. در این پروتکل چندین حالت: حالت کاندید، حالت غیر کاندید، حالت فعال، حالت همیار و حالت همیار غیرفعال برای گرهها ایجاد میشود. برای مجموعه گرههای موجود در شبکه، اعضای H-S به طور سامانمند تنظیم شدهاند تا مصرف انرژی کاهش یافته و در نتیجه طول عمر شبکه افزایش یابد]۴۰[. تفاوت این الگوریتم با LEACH، در آن است که هر خوشه دارای یک سرخوشه پویا و تعداد دیگری سرخوشه همکار در یک خوشه است. اعضای H-S مسئول کنترل و مدیریت شبکه هستند. این الگوریتم دارای دو فاز انتخاب و ارسال میباشد. در شروع فاز انتخاب، مجموعهای از سرخوشهها بصورت تصادفی انتخاب میشوند. این سرخوشهها یک پیام اعلانی فراگیر کوتاه برد پخش میکنند. گرههای حسگر، پیامهای اعلانی را دریافت کرده و بر اساس قدرت سیگنال پیامهای اعلانی، سرخوشهی خود را انتخاب میکنند. سپس هر گره حسگر یک پیام تصدیق به سرخوشه انتخابیاش ارسال میکند. در هر تکرار از الگوریتم سرخوشهها نیز بر اساس قدرت سیگنالهای تصدیقی دریافت شده، مجموعه همیاران خود را انتخاب میکند. اعضای H-S مسئول ارسال پیام به گره چاهک هستند. هر فاز ارسال داده شامل چند دوره است. هر عضو H-S در طول یک دوره، یک بار سرخوشه میشود. یک دور کامل شامل چندین تکرار است. در یک دور، هر گره حسگر برای یک بار عضو H-S میشود. در طول یک دوره اعضای H-S دارای یک عضو در حالت فعال است و تعداد کمی از اعضا در حالت همیار و بقیه در حالت همیار غیرفعال هستند. در زمان ارسال آخرین فریم در یک دوره، یک عضو فعال بوده و بقیه همیار غیرفعال هستند. بنابراین هیچ عضوی در حالت همیار نیست. برای شروع دوره بعدی، یک عضو H-S حالت فعال را به دست میآورد و بقیه در حالت همیار هستند. با تکمیل یک تکرار، همه اعضای H-S حالت غیر کاندید را به دست میآورند. اعضایی که در حالت غیر کاندید هستند، واجد شرایط عضویت در H-S نیستند. برای شروع دور کامل بعدی، همه گرههای حسگر غیر کاندید، حالت کاندید را به دست میآورند ]۴۰٫[ شکل ۲-۷ دیاگرام حالت را برای یک حسگر شبکه در الگوریتم CBHRP نشان میدهد.
شکل ۲‑۷: حالتهای مختلف گره حسگر در CBHRP [40]
پروتکل [۵۱]TEEN
بعد از این که کلاسها تشکیل شدند سرخوشهها دو آستانه را به همه حسگرها میفرستند. اسامی این آستانهها، آستانهی نرم و آستانهی سخت میباشند. آستانهی سخت در واقع مقداری از پارامتر در حال اندازهگیری است که اگر مقدار بهدست آمده از یک حسگر از این آستانه بیشتر باشد، مقدار بهدست آمده گزارش میشود، ولی اگر کمتر باشد دیگر این اتفاق نمیافتد. در واقع این آستانه باعث میشود که هر وقت مقدار پارامتر در محدوده دلخواه است گزارش شود و بدینصورت از حجم دادههای ارسالی تا حد زیادی کاسته میشود. اما آستانهی نرم مقداری از پارامتر در حال اندازهگیری است که هر وقت مقدار بهدست آمده زیر آستانهی سخت باشد اما بیشتر از نمونه قبلی پارامتر اندازهگیری شده باشد، حسگر باز هم مقدار پارامتر را گزارش میکند. وجود آستانهی نرم نیز باعث کاهش دادههای ارسالی میشود. با تنظیم سطوح آستانهی نرم و سخت میتوان حجم دادههای ارسالی به گره چاهک را تنظیم کرد. برای ارسال دادهها به گره چاهک هر حسگر دادهی خود را به سرخوشه لایه اول میفرستد، سرخوشه لایه اول نیز آن را به سرخوشه لایه دوم میفرستد و در نهایت به ایستگاه پایه فرستاده میشود]۴۱٫[
TEEN در کاربردهایی مناسب است که گزارش اطلاعات بهصورت پریودیک مورد نظر نباشد. یعنی هر وقت اتفاق خاصی در شبکه رخ داد گزارش شود. گره چاهک دارای منبع تغذیه پایدار میباشد، بنابراین محدودیت انرژی ندارد و نیاز به مسیریابی از گره چاهک به سایر گرهها نیست. بین گرهها و گره چاهک ارتباط نامتقارن وجود دارد زیرا گرهها دارای محدودیت انرژی هستند و نمیتوانند پاسخ گره چاهک را به طور مستقیم بدهند. از ویژگیهای این مدل آن است که گرهها تنها توانایی ارسال اطلاعات به سرگروه خود را دارند که این امر سبب صرفهجویی انرژی خواهد شد، تنها سرخوشهها محاسبات اضافهای را روی داده اجرا میکنند که این امر نیز موجب صرفهجویی انرژی خواهد شد. در هر زمان تغییر کلاس علاوه بر ویژگی سرخوشهها، موارد زیر را نیز به اعضای خود ارسال میکند]۴۱ [:
آستانه سخت (HT[52])، این مقدار آستانه برای ویژگیهای حس شده است. گره ای که این مقدار را حس میکند باید فرستنده خود را روشن کند و آن را به سرگروه گزارش بدهد.
آستانه نرم (ST[53])، یک تغییر کوچک در مقدار ویژگیها حس شده است که گره را وادار به روشن کردن فرستنده و ارسال آن میکند.