دوشنبه 28 آبان 1397 | Monday 19 th of November 2018 صفحه اصلی گروه الکترونیکی کامپیوتر
3-4-5پروتکل LEACH

مثال معروف دیگر برای گردش مسئولیت سرخوشه، پروتکل LEACHاست [39]هدف این مدل یک شبکه حسگر با تعداد مشخصی از گره و منطقه ایی مشخص با یک بستر داده ایی است که کل اطلاعات باید به ان انتقال یابد. با توجه به اینکه داده‌ها را می‌توان متراکم کرد (مثلاً از طریق میانگین گیری) معرفی سرخوشه‌ها باید انجام گیرد. این گره‌ها باید داده‌های خوانده شده توسط اعضای خوشه خود را جمع اوری و انها را مستقیماً با قدرت فراوان برای سینک داده ایی که در یک گامی انها قرار دارد، ارسال نمایند. این یک عملیات با مصرف انرژی زیاد بوده و بهتر است برای جلوگیری از تخلیه انرژی سرخوشه‌ها نقش انها میان همه گره‌ها گردش نماید.

این روش یکی از روشهای پر استفاده در زمینه خوشه ​بندی است که از عمل تصادفی برای توزیع انرژی بصورت هموار در سطح شبکه استفاده می​کند. LEACHپروتکل خود سازمان یافته انرژی است، به نحوی که گره​ها خودشان را درون خوشه​های داخلی با یک گره بعنوان سرگروه سازماندهی می​کنند. این پروتکل عمل ترکیب داده​ها را بصورت محلی انجام می​دهد و خوشه‌بندی در ان چهار مرحله دارد: مرحله تبلیغات، مرحله ای ایجاد خوشه، مرحله ایجاد فهرست زمانبند و مرحله جمع اوری داده​ها.  ما یک پروتکل ساده و کوچک برای انتخاب سرخوشه‌ها و گردش انها نیاز داریم و ایده موجود، استفاده ازمدل انتخاب تصادفی سرخوشه‌هاست و نیازی به تحمیل سرباری که ناشی از انتخاب دقیق سرخوشه به سیستم وارد می‌شود، نیست. چون این انتخاب بسیار موقتی و زودگذر خواهد بود. گره‌ها مستقلاً تصمیم به سرخوشه شدن می‌گیرند و این تصمیم را به گره‌های همسایه اطلاع می‌دهند. گره‌های دیگر در این حالت به خوشه‌های نزدیک خود می‌پیوندند و این کار با حداقل هزینه انجام می‌شود. گره‌هایی که‌هیچ پیامی از طرف سرخوشه‌ها دریافت نمی‌کنند و خود نیز تمایلی به سرخوشه شدن ندارند باید با سینک داده، مستقیماً ارتباط برقرار کنند.  در چنین حالت انتخاب تصادفی سرخوشه، نسبت تعداد سرخوشه به تعداد کل گره‌ها باید متناسب باشد. به یاد داشته باشید که‌هزینه ارتباط با سینک داده‌ها بدون سرخوشه بسیار بالا و بهره وری انرژی را در کل سیستم پایین خواهد اورد و اضافه کردن حتی چند سرخوشه، علیرغم تلاش اضافی که این سرخوشه‌ها برای جمع اوری داده‌ها انجام می‌دهند، بهره وری را در کل سیستم بالا خواهد برد. هنگامی که به‌همین حالت تعداد سرخوشه ها را کم کم افزایش می‌دهیم، مزایای خوشه به تدریج کاهش می‌یابد (و در بدترین حالت،‌‌ هر گره سرخوشه خود می‌شود و مزایای متراکم سازی داده‌ها و چندگامی از بین می‌رود). به‌همین دلیل یافتن تعداد مطلوب سرخوشه‌همواره مد نظر بوده است.

هینزل من و همکاران [17]این نسبت را 5 درصد اعلام نمودند ولی این مقدار یقیناً به نوع نصب و تنظیمات خاصی که در اجرا انجام شده بستگی خواهد داشت هنگامی که نسبت مطلوب تعداد سرخوشه‌ها P‌ مشخص گراید الگوریتم LEACHبه تعدادبار اجرا می‌شود (برای ساد‌گی، این عدد را، عدد صحیح فرض کنید) در هر بار اجرا، مجموعه ای از سرخوشه‌های در اندازه nPاز گره‌ها، (n‌ برابر است با تعداد کل گره‌ها) از مجموعه Gاز گره‌ها، که ‌هنوز به عنوان سرخوشه سرویس دهی نکرده اند انتحاب می‌گردد (در واقع با هر بار اجرای الگوریتم، Gگره‌های بیشتری را در بر خواهد گرفت).

در شروع دور rهر گره در Gبه احتمال. (r mod 1 /P)) P / (1 - Pممکن است سرخوشه گردد. این احتمال با هر بار اجرا افزایش می‌یابد به نحوی که در دور  1 / P - 1تمام گره‌های هنوز انتخاب نشده به احتمال 1 سرخوشه می‌شوند، این حالت این اطمینان را می‌دهد که ‌همه گره‌ها به نسبت مساوی سرخوشه خواهند شد.در دور 1 / Pفرایند از نو اغاز می‌گردد.

هینزل من[1] و همکاران [39]در ادامه در مورد مناسب بودن ساختار خوشه‌بندی حاصل برای زمان بندی ارسال و نحوه تعیین سطوح مختلف خوشه‌بندی بحث نموده‌اند. در هر حال این یک راه حل ساده و زیبا برای مسئله گردش سرخوشه است. ولی باید در اجرای ان اطمینان حاصل کرد که تعویض سرخوشه‌ها به نحوی انجام شود که در کار انتقال اطلاعات به سینک های داده وقفه پیش نیاید و به سرعت بتوانند با ان ارتباط برقرار کنند.

خوشه‌بندی تطبیقی سلسله مراتبی کم انرژی، اولین پروتکل مسیریابی مبتنی بر خوشه در شبکه‌های حسگر بی‌سیم است. این پروتکل گره‌ها را به خوشه‌ها تقسیم می‌کند، در هر خوشه یک گره با اختیارات ویژه وجود دارد که سرخوشه نام دارد و مسئول ایجاد و پیاده‌سازی جدول زمانبندی [2]TDMAو ارسال داده‌های تجمیع شده با استفاده از [3]CDMAبه سینک است. سایر گره‌ها، اعضای خوشه‌ها خواهند بود.

فعالیت این پروتکل در دوره‌های کاری انجام می‌شود که هر یک به فازهایی تقسیم می‌گردند. فاز پیکربندی که خود شامل دو فاز اگهی و تشکیل خوشه است. فاز تثبیت نیز خود شامل ایجاد جدول زمانبندی و انتقال داده می‌باشد.

در فاز پیکربندی هر گره بطور مستقل تصمیم می‌گیرد که سرخوشه گردد یا خیر. این تصمیم در صورتی که گره مدت زیادی سرخوشه نبوده باشد قطعا به سرخوشه شدن گره منجر می‌گردد. در فاز بعدی (اگهی) سرخوشه‌ها با ارسال بسته‌هایی سرخوشه بودن خود را اعلام می‌کنند. گره‌هایی که سرخوشه نیستند از بسته‌های اگهی شده قوی ترین را انتخاب می‌نمایند

در فاز بعدی، گره‌های عضو با ارسال بسته‌ایی که شامل شناسه انهاست و با استفاده از CSMAبه سرخوشه خود اطلاع می‌دهند که عضو خوشه او شده‌اند پس از ان سرخوشه تعداد و شناسه اعضای خود را می‌داند و جدول زمنبندی TDMAرا ایجاد کرده و یک کد CDMAبصورت تصادفی انتخاب نموده واز طریق ان جدول TDMAرا به اعضای خوشه اعلام می‌دارد. سپس فاز حالت پایدار اغاز می‌گردد.

در حالت پایدار ارسال داده‌ها اغاز می‌گردد و هر گره‌ دراسلات زمانی اختصاص یافته، داده خود را ارسال می‌کند. هر گره می‌تواند فرستنده خود را فقط در بازه‌‌های زمانی تعیین شده روشن کند و انرژی صرف شده خود را به حداقل برساند. هنگامی که داده همه گره‌ها دریافت شد، سرخوشه به منظور کاستن از حجم داده ارسالی انها را تجمیع کرده و به سینک می‌فرستد. علیرغم اینکه LEACHبه درستی قابل پیاده سازی است اشکالات زیادی نیز دارد[22]. برخی از این اشکالات عبارتند از:

سرخوشه‌ها بصورت تصادفی انتخاب می‌شوند و انرژی انها در نظر گرفته نمی‌شود.

ناحیه بزرگی را نمی‌تواند پوشش دهد زیرا یکی از فرضیات LEACHاین است که همه گره‌ها می‌توانند با سینک مستقیما ارتباط داشته باشند

سرخوشه‌ها بصورت یکنواخت در کل شبکه انتخاب نمی‌شوند و ممکن است در اطراف ناحیه انتخاب شوند در این حالت برخی از گره‌ها مجبور خواهند بود برای رسیدن

به سرخوشه خود فرستنده‌شان را با حداکثر توان استفاده کنند که همین امر موجب اتلاف انرژی و خاموش شدن این گره‌ها می‌گردد.

همانگونه که در شکل18مشاهده می‌شود سرخوشه‌ها در نزدیک به یکدیگر و در کناره‌ها قرار گرفته‌اند. این امر باعث مصرف زیاد انرژی می‌گردد زیرا گره‌ها باید برای مسافت زیادی ارتباط برقرار کنند. در شکل پایینی به لحاظ توزیع یکنواخت سرخوشه‌ها در شبکه، کارایی انرژی بالاتر خواهد بود. نکته قابل توجه اینکه تعداد گره‌هایی که در دوره اول و دوم سرخوشه نبوده‌اند در دو سناریو برابر است.

سناریوی خوب در LEACH

سناریوی بد در LEACH

شکل 18 شبکه LEACH  با P=0.2و n=20و ابعاد شبکه 100x100m.


[1] Heinzelman

[2] Time division multiple access

[3] Code division multiple access

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