دوشنبه 25 تیر 1397 | Monday 16 th of July 2018 صفحه اصلی گروه الکترونیکی کامپیوتر
1-4-2 الگوریتم تشکیل خوشه

هنگامی¬که سرخوشه¬های دور اتی با استفاده از تابع احتمالی که قبلا در مورد ان بحث شد، انتخاب شدند سرخوشه¬ها باید به تمامی گره¬های دیگر اطلاع دهند که در دور اتی نقش سرپرست خوشه را بر عهده دارند. برای این کار هر گره¬ی سرخوشه یک پیام تبلیغ (ADV) را با استفاده از پروتکل زیر لایه¬ی دسترسی به رسانه¬ی انتقال nonpersistent CSMA  در کل شبکه منتشر می¬کنند. در پاراگراف زیر درباره¬ی جزییات این پروتکل توضیح داده شده است. در پروتکل،nonpersistent CSMA تلاش اگاهانه جهت ارسال بر روی کانال با اصرار کمتری نسبت به پروتکل¬های دیگر از این نوع (p-persistent) انجام می¬گیرد: هر گره قبل از ارسال، کانال را بررسی (شنود) می¬کند؛ اگر گره¬ی دیگری در حال ارسال نباشد، ان گره فریم خودش را می¬فرستد ولیکن هرگاه کانال از قبل در اختیار گره¬ی دیگری باشد، ایستگاه به طور دایم به شنود کانال نخواهد پرداخت. در عوض، هرگاه گره کانال را مشغول تشخیص بدهد، به انداز ه ییک زمان تصادفی صبر کرده و پس از ان الگوریتم فوق را تکرار می¬کند. در حالیکه در روش 1-persistent CSMA هرگاه یک گره داده¬ای برای ارسال داشته باشد، ابتدا به کانال گوش می¬دهد تا ببیند که ایا در این لحظه گره¬ی دیگری در حال ارسال هست یا خیر. اگر کانال مشغول باشد، گره انقدر منتظر می¬ماند(به کانال گوش می¬دهد) تا کانال ازاد شود؛ ولی اگر گره کانال را ازاد تشخیص دهد فریم خود را ارسال می¬کتند. اگر تصادمی رخ بدهد گره به اندازه¬ی یک زمان تصادفی صبر کرده و تمام مراحل را از نو اغاز می¬کند. به همین علت این پروتکل 1-persistent (پروتکل پافشاری بر ارسال )نامیده می¬شود، چرا که وقتی یک گره کانال را ازاد تشخیص بدهد با احتمال 1 فریم خود را ارسال می¬کند. به همین ترتیب در پروتکل p-persistent CSMA  هرگاه ایستگاهی اماده¬ی ارسال شود، ابتدا کانال را شنود می¬نماید؛ اگر کانال ازاد باشد فریم خود را با احتمال p ارسال می¬کند و یا به احتمال q=1-p  ارسال خود را تا فرا رسیدن برش زمانی بعدی به تعویق می¬اندازد. و این فرایند انقدر تکرار می¬شود تا انکه فریم ارسال شود یا انکه گره¬ی دیگری ارسال خود را اغاز نماید. در حالت دوم(یعنی هنگامیکه گره¬ی دیگر موفق به ارسال شود) گره¬ی ناموفق، همانند وقتی که تصادم رخ داده عمل می¬کند، یعنی به اندازه¬ی یک زمان تصادفی صبر کرده و از نو شروع می¬نماید.
پیام ADV پیام کوچکی است که شامل ID گره و سرایندِ کوچکی است که این پیام را به عنوان یک پیا م ADV متمایز می¬کند. هر گره¬ای که سرخوشه نیست  خوشه¬ی خود را برای دور اتی با انتخاب سرخوشه¬ای که کمترین انرژی لازم را برای ارتباط با ان لازم دارد، تعیین می¬کند و این انتخاب بر اساس قدرت سیگنال دریافتی پیام ADV دریافت شده از سرخوشه¬های مختلف، انجام می¬گیرد. معمولا برای هر گره¬ی، non-ch نزدیکترین سرخوشه این خصوصیت را داراست و به عنوان سرپرست ان گره انتخاب می¬شود. و اگر گره¬های سرخوشه با شرایط مساوی داشتیم، یک گره به صورت تصادفی به عنوان سرخوشه انتخاب می¬شود.
بعد از اینکه هر گره در مورد خوشه¬ای که در دور اتی به ان تعلق دارد تصمیم گرفت، باید سرخوشه مربوطه را اگاه سازد. برای این منظور، هر گره یک پیام (Join-REQ) join-request را به سرخوشه مورد نظرش با استفاده از پروتکل nonpersistent CSMA  می¬فرستد. این پیام نیز یک پیام کوچک شامل ID خود گره و ID سرپرست انتخابی می¬باشد.
سرخوشه¬ها پس از دریافت این پیام¬های Join-REQ به عنوان مراکز کنترل محلی در پروتکل LEACH، برای هماهنگ کردن انتقال داده¬ها در خوشه¬ها و عدم امکان رخداد تصادم بین داده¬های گره¬های یک خوشه، یک برنامه¬ی زمانی TDMA درست می¬کند و این برنامه¬ی زمانی را برای اعضای خوشه می¬فرستد. در نتیجه، تضمین می¬شود که تصادمی بین پیام¬های داده¬ی یک خوشه پدید نمی¬اید و همچنین این امر اجازه می¬دهد که اجزای رادیویی گره¬های  non-ch در تمامی بازه¬های زمانی مگر در بازه¬ی زمانی مربوط به خودشان خاموش باشد. به این ترتیب انرژی مصرفی توسط گره¬ها کاهش می¬یابد. بعد از اینکه برنامه¬ی زمانی  TDMA توسط تمامی گره¬های خوشه شناخته شد، فاز راه¬اندازی کامل شده و فاز حالت پایدار (فاز انتقال داده¬ها) اغاز می¬گردد. در شکل 4-3 فلوچارت الگوریتم تشکیل خوشه¬ها در  LEACH نشان داده شده است.
 


شکل 4-3 فلوچارت الگوریتم تشکیل خوشه¬ها در LEACH [Amini 07]


 شکل4-4 مثالی را از خوشه¬های تشکیل شده در دو دور مختلف از اجرای پروتکل LEACH نشان می¬دهد. همان طور که ملاحظه می¬کنید در هر دور تعداد پنج خوشه تشکیل شده است و انتخاب این خوشه¬ها کاملا به صورت تصادفی بوده است. البته در پروتکل LEACH تضمینی برای اینکه حتما تعداد مشخصی از گره¬ها سرخوشه شوند، وجود ندارد.
 


 
شکل 4-4 تشکیل دینامیک خوشه¬ها در دو دور مختلف از پروتکل LEACH گره¬های با علامت یکسان، متعلق به یک خوشه هستند و سرخوشه¬ها با دایره¬ی توپر نشان داده شده¬اند

Compatability by:
آخرین به روز رسانی سایت: سه شنبه, 22 اسفند 1391 - 00:26