پروتکل LEACH چیست؟

هر سوالی  در ns-2 دارید،  با ما در میان بگذارید.

09147450367

[e-mail]

به سایت www.ns-3.org سری بزنید.

 قسمت لینک دوستان را نیز دنبال کنید.

 پروتکل LEACH

در بین پروتکل­های ارتباطی ارائه شده پروتکل LEACHبه دلایل زیر از اهمیت ویژه­ای در نزد محققان برخوردار است:

اول اینکه خوشه­های شبکه به­صورت تصادفی [1] ، تطبیقی[2] و خودپیکربندی شده[3] تشکیل می­شوند.

شرح این ویژگی­ها به­صورت زیر است :

تصادفی: به این معنی که در هر دور،تعداد مشخصی از گره­ها به صورت تصادفی خود را به عنوان سرخوشه انتخاب می­کنند و گره­های خاصی از قبل به عنوان سرخوشه در نظر گرفته نشده­است. مزیت این ویژگی سربار کم روش انتخاب سرخوشه است. این روش سریع­ترین روش انتخاب سرخوشه است.

تطبیقی: گره­هایی که در دور فعلی نقش سرخوشه را به عهده داشته­اند، در دور بعدی دیگر نمی­توانند برای بر عهده گرفتن این نقش کاندیدا شوند، بنابراین در هر دور، با توجه به دور قبلی کاندیداهای سرخوشه مشخص می­شوند. به این ترتیب انتظار می­رود که در پایان تعداد مشخصی از دورها، تمامی گره­ها سرپرست خوشه شوند.

خودپیکربندی شده­: گره­ها دراین پروتکل بدون کمک هر عامل خارجی و یا گره خاصی در شبکه، تشکیل خوشه می­دهند و این به مقیاس­پذیری این پروتکل کمک می­کند.

دومین اهمیت اینکه در LEACHانتقال اطلاعات از گره­های یک خوشه به سرخوشه و از سرخوشه­ها به ایستگاه  sinkبا کنترل محلی انجام می­شود و نیازی به کمک یک عامل خارجی و یا گره خاصی در شبکه برای انتقال اطلاعات نیست.

سوم اینکه پروتکل MACاستفاده شده درLEACHبا استراحت دادن به گره­ها در انرژی مصرفی صرفه­جویی می­کند.

        همان­طور که قبلا گفته شد، LEACHاز روش ترکیب داده­های هر خوشه و ارسال داده­ی فشرده شده به ایستگاه پایه استفاده می­کند. بدین ترتیب هم تعداد ارسال و دریافت­ها در شبکه کاهش می­یابد و هم داده­های زاید که به علت نردیکی سنسورهای یک خوشه به یکدیگر ایجاد می­شوند، پیش از ارسال به sinkحذف می­گردند. نوع ترکیب داده­ها در LEACHثابت نیست و بستگی به کاربرد شبکه سنسور بیسیم دارد. هدف این پروتکل ایجاد توازن در مصرف انرژی در گره­ها است. گزینه­های کلاسیک مانند DT [4]وMTE  [5]تعادل انرژی بین گره­ها را تضمین نمی­کنند. در DTچون گره­ها مستقیماً داده را به sinkارسال می­کنند انرژی گره­های دورتر، زودتر تخلیه می­شود و در نتیجه زودتر می­میرند. در MTEداده از کم هزینه­ترین مسیر هدایت می­شود. در جایی که معیار هزینه مصرف توان است، چون گره­های نزدیک به sinkعمل انتقال داده­های گره­های دورتر را نیز انجام می­دهند، در نتیجه زودتر می­میرند. پس بخش زیادی از محیط در مدت زمان زیادی از عمر شبکه قابل نظارت نخواهد بود. یک راه­حل استفاده از پروتکل LEACHاست که مصرف انرژی را با خوشه­بندی و انتخاب پویای خوشه­ها توزیع می­کند، بدین ترتیب که سنسورها به ناحیه­هایی تقسیم می­شوند که هر ناحیه دارای یک سرخوشه است و پس از اتفاق یک رویداد سنسورهای هر ناحیه، اطلاعات خود را به سرخوشه ارسال می­کنند و سرخوشه این اطلاعات را مستقیم به sinkمی­رساند (شکل2-3).

شکل 2-3: خوشه­ بندی در شبکه ­های بیسیم    

الگوریتم LEACHبه انتخاب شدن سرخوشه­ها به صورت تصادفی و با یک احتمال ثابت تاکید دارد. (تمام گره­ها از احتمالی یکسان برای سرخوشه شدن برخوردارند.) گره­ها همگن فرض می­شوند (گره­ها دارای انرژی اولیه یکسانی هستند). در این الگوریتم سنسورها به­صورت تصادفی در یک ناحیه توزیع می­شوند. سنسورها ثابت در نظر گرفته می­شوند. انها در گروه­ها یا خوشه­هایی دسته­بندی می­شوند و هر گروه یک سردسته دارد، که هر ناحیه از طریق سرخوشه­اش با sinkکه در مرکز شبکه قرار دارد به­ صورت مستقیم ارتباط برقرار می­کند. به این ترتیب هم تعداد ارسال و دریافت­ها در شبکه کاهش می­یابد و هم داده­های زاید که به علت نزدیکی سنسورهای یک خوشه به یکدیگر تولید می­شوند حذف می­شوند. عملکرد پروتکل از دوره­هایی متشکل از چندین دور تشکیل شده است. احتمال بهینه سرخوشه شدن گره­ها برابر  است و ثابت در نظر گرفته می­شود. تعداد بهینه خوشه­ ها بر اساس توزیع مناسب بین تمام سنسورها و کمینه نمودن مصرف انرژی انتخاب می­شود. هر دوره از دور تشکیل شده­ است. در صورتی که گره در دور فعلی سرخوشه شود تا انتهای دوره دیگر سرخوشه نخواهد شد. گره برای سرخوشه شدن یک عدد تصادفی در بازه  انتخاب و عدد تصادفی موردنظر را با حد استانه  مقایسه می­کند. در صورتی که عدد انتخابی کوچک­تر از حد استانه باشد گره در دور فعلی سرخوشه می­شود. اگر سنسور در این دور سرخوشه نشود احتمال سرخوشه شدن خود را افزایش می­دهد و این کار را تا زمانی ادامه می­دهد که در دور اخر این احتمال به 1 برسد . به این معنی که اگر گره تا دور اخر سرخوشه نشده باشد، حتما در دور اخر سرخوشه خواهد شد. گره­هایی که هنوز در دوره فعلی سرخوشه نشده­ اند متعلق به مجموعه Gهستند ودر هر دور احتمال سرخوشه شدن انها افزایش می­یابد.(رابطه2-3)

 (2-3)    

در این رابطه rمشخص کننده دور فعلی است و مقدار اولیه ان صفر است. انتخاب این رابطه در پروتکلLEACHبه صورتی بوده که گره­هایی که اخیرا سرخوشه نبوده­اند در دور فعلی سرخوشه شوند؛ زیرا می­توان انتظار داشت که این گره­ها نسبت به گره­هایی که اخیرا وظیفه سرخوشه بودن را ( که انرژی زیادی مصرف می­کند) بر عهده داشته­ اند، انرژی بیشتری دارند. می­توان انتظار داشت که در هر  دور، هر گره به طور متوسط یک بار سرخوشه شود.

وقتی یک گره سرخوشه می­شود، احتمال سرخوشه شدن سنسور تا دوره بعدی صفر شده و احتمال گره­هایی که در دور فعلی سرخوشه نشده­اند افزایش می­یابد.           

مجموعه Gشامل سنسورهایی است که تا کنون سرخوشه نشده­اند و در زمان tقابلیت سرخوشه شدن را دارند. احتمال سرخوشه شدن انها از طریق رابطه (2-4) بدست می­اید.

(2-4)          

LEACHدارای چهار مرحله عملیاتی پیشنهاد، تشکیل گروه، ایجاد زمانبندی و انتقال داده است، در مرحله پیشنهاد سرخوشه با یک پیام خود را به گره­های دیگر معرفی می­نماید. سنسورها از این پیشنهادها، نزدیک­ترین سرخوشه را انتخاب نموده و درخواست عضویت را برای ان ارسال می­کنند. گره سرخوشه یک زمانبندی برای اعضا ایجاد و ان­را به سنسورهای عضو ارسال می­کند. گره­ها در زمانبندی اعلام شده داده­های خود را به سرخوشه ارسال می­کنند و سرخوشه با جمع­اوری و ترکیب داده­ها ان را به sinkارسال می­کند. مصرف انرژی گره­های سرخوشه به دلیل جمع­اوری اطلاعات گروه­های عضو، ترکیب و ارسال داده ترکیب شده به sinkکه در فاصله دورتری قرار دارد بیشتر از گره­های عضو است. با انتخاب تصادفی سرخوشه و در نتیجه چرخش نقش سرخوشه بین گره­ها، مصرف انرژی بین انها به خوبی توزیع می­شود.

        مهمترین کاربر  LEACHاین است که برای جمع­اوری داده­ها استفاده می­شود و با توجه به اینکه، به جدول مسیریابی سنگین نیازی ندارد دارای سربار پایینی است و یکی از پروتکل­های موفق در نوع خود است. مزیت ناهمگن بودن گره­ها (وجود سنسورهایی با انرژی بیشتر) کاهش هزینه توسعه سیستم است؛ زیرا می­توان همین عمل را با افزایش تعداد گره­های همگن در ابتدای کار انجام داد ولی با توجه به این نکته که هزینه افزودن گره جدید به­جای قرار دادن باتری اضافه روی بعضی از سنسورها ده برابر بیشتر است، پس ناهمگن بودن گره­ها و استفاده مطلوب از ان می­تواند هزینه را به­طور چشمگیری کاهش دهد.

          اشکالاتی که بر پروتکل LEACHوارد است نیز عبارتند از :

·        هر سنسور در این الگوریتم با تولید یک عدد تصادفی تصمیم می­گیرد که سرخوشه باشد یا نباشد. با توجه به انتخاب تصادفی سرخوشه­ها این احتمال وجود دارد که در برخی از زمان­ها قسمتی از شبکه سرخوشه نداشته باشد و در قسمت دیگری چگالی سرخوشه­ها زیاد باشد. در مجموع هیچ قاعده منطقی بر پایه تغییرات توپولوژیکی و انرژی باقیمانده سنسورها وجود ندارد که بر انتخاب شدن گره­ها به عنوان سرخوشه تاثیر می­گذارد. LEACHتوانسته تنها به نحوی انتخاب سرخوشه را در شبکه میسر سازد.

·        پروتکل­های کلاسیک (همچنین پروتکل LEACH) فرض را بریکسان بودن انرژی گره­ها گذاشته و در نتیجه در صورت ناهمگنی گره­ها از نظر انرژی، مزایای کامل خود را ارائه نمی­کنند. ناهمگنی گره­ها دلایل زیادی دارد که می­توان به تنظیم اولیه متفاوت، عملکرد شبکه یا افزودن گره­های جدید به سنسورهای قبلی اشاره نمود. در صورتی که گره­ها ناهمگن باشند پروتکل به درستی عملیات مطلوب خود را انجام نمی­دهد و به ویژه از زمان مرگ اولین گره، عملکرد شبکه ناپایدار خواهد شد.

·   LEACHفرض می­کند که همه گره­ها می­توانند با توان کافی برای رسیدن به ایستگاه اصلی درصورت نیاز، انتقال داشته باشند و اینکه هر گره توان محاسباتی برای حمایت پروتکل­های مختلفMACدارد. بنابراین گسترش شبکه به نحوی بزرگ قابل اجرا نیست. همچنین فرض می­کند که گره­ها داده برای ارسال دارند و گره­هایی که نزدیک به هم هستند داده وابسته به هم دارند. معلوم نیست چطور تعداد لیدر از پیش تعیین شده به­صورت یکنواخت در شبکه توزیع می­شود. بنابراین این امکان وجود دارد که لیدرهای انتخاب شده در یک بخش از شبکه متمرکز شود. بعضی گره­ها ممکن است هیچ لیدری در مجاورت خود نداشته باشند. به­علاوه، برای رفع این مشکل فکر خوشه­بندی پویا سربار ایجاد می­کند.

جدول 2-1 مقایسه تکنیک­های مسیریابی SPIN،LEACHو انتشار مستقیم را بر طبق تعدادی پارامتر مختلف نشان می­دهد.

جدول 2-1: مقایسه بینSPIN،LEACHو انتشار مستقیم

	انتشارمستقیم	SPIN	LEACH
طول عمر شبکه	خوب	خوب	بسیار خوب
استفاده از Meta-data	بله	بله	خیر
اگاهی منبع	بله	بله	بله

 

 

برای مثال، تغییرات سرایند اعلان و غیره، ممکن است بهره­وری در مصرف انرژی را کاهش دهد. همچنین پروتکل، فرض می­کند که همه گره­ها با یک میزان ظرفیت انرژی در هر دور انتخابی شروع می­کنند. فرض کنید که یک لیدر تقریبا همان میزان انرژی را برای هر گره مصرف کند. پروتکل بایستی گسترش پیدا کند تا برای گره­های انرژی غیر یکنواخت یعنی استفاده استانه مبتنی بر انرژی هم کار کند.

        در الگوریتم دیگری بنام HEEDنیز چهار هدف افزایش طول عمر شبکه، اتمام فاز خوشه­بندی پس از طی تعداد متناهی و مشخصی از تکرار، حداقل کردن سربار کنترلی و توزیع متناسب خوشه­ها در سطح شبکه دنبال می­شود. هر گره با احتمالی متناسب با میزان انرژی باقیمانده خود تصمیم می­گیرد که ایا لیدر خوشه باشد یا نه. این تصمیم­گیری موقتی است و پس از گذشت چندین تکرار نهایی می­شود. گره­هایی که خود را به­عنوان لیدر خوشه برگزیده­اند، به همسایگان خود این مسئله را اطلاع می­دهند. هر یک از همسایگان، در صورتی که پیش از این عضو خوشه­ای نشده­باشد، عضو این خوشه می­شود. در صورتی که همسایه­ای پیش از این عضو خوشه دیگری باشد که انرژی باقیمانده سرخوشه ان نسبت به انرژی باقیمانده لیدر خوشه جدید پایین­تر باشد، همسایه به خوشه جدید ملحق می­شود.

به­علاوه، درصورتی که همسایه­ای خود لیدر باشد، پس از مقایسه میزان انرژی باقیمانده خود با میزان انرژی باقیمانده لیدر خوشه معرفی شده، تصمیم می­گیرد که همچنان لیدر باقی بماند یا به خوشه­ی جدید منتقل شود. هر لیدر، در صورتی که برای ملحق شدن به خوشه دیگری تصمیم نگرفته باشد، مقدار احتمالpخود را دو برابر کرده و مجددا خود را به عنوان سرخوشه به همسایگانش معرفی می­کند. اگر مقدارpدر گره­ای بزرگ­تر از 1 شد، ان گره خود را به عنوان سرخوشه نهایی برمی­گزیند. در این صورت، همسایگان این گره نیز، عضو خوشه­ای نهایی خواهند شد که دیگر تغییری در ان به وجود نمی­اید. در این مرحله، در صورتی که گره­ای، هیچ پیام معرفی خوشه­ای را دریافت  نکرده باشد، خود تصمیم می­گیرد که راس خوشه­ای جدید باشد

---

[1] Randomized

[2]Adaptive

[3]Self-Configured

[4]Direct Transmission

[5]Minimum Transmission Energy