آموزش پروتکل LEACH – معرفی جامع پروتکل خوشه بندی LEACH در شبکه حسگر بی سیم

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

معرفی پروتکل LEACH

قبل از اینکه در مورد پروتکل LEACH صحبت کنیم اجازه دهید در مورد شبکه حسگر بی سیم ^[2] Wireless Sensor Networks یا به اختصار WSN و نقش پروتکل های مسیریابی در آن مقدمه ای بیان کنیم چرا که دانستن مفهوم شبکه حسگر بی سیم نقش اساسی در این بحث دارد.

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

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

خوشه بندی یک تکنیک کارآمد برای حفظ تعادل انرژی در شبکه های حسگر بی سیم (WSN ها) است که این کار را با استفاده از تجمیع داده ها انجام می دهد. منظور از تجمیع، جمع آوری داده ها از گره های داخل خوشه ها است که البته در ادامه در مورد این مفاهیم بیشتر صحبت خواهیم کرد.

از آنجایی که روش خوشه بندی تعداد بسته های مسیریابی شده را در شبکه کاهش می دهد در نتیجه از پروتکل های مسیریابی خوشه بندی در WSN برای رسیدن به انرژی کارآمد استفاده می شود.

در WSN ها، خوشه بندی مزایای مختلفی مانند مقیاس پذیری بیشتر، بار کمتر، مصرف انرژی کمتر، تجمع داده ها، جلوگیری از برخورد، متعادل سازی بار، کاهش تأخیر، تحمل خطا، استحکام بیشتر، تضمین اتصال و به حداکثر رساندن طول عمر شبکه و غیره را دارد.

LEACH یک پروتکل MAC  بر اساس روش TDMA است که به عنوان معروف ترین و اولین پروتکل مسیریابی سلسله مراتبی مورد استفاده در خوشه بندی به شمار می رود که ايجاد خوشه ها در آن بصورت توزيع شده انجام می گیرد. برای اطلاعات بیشتر در مورد TDMA می توانید مقاله دسترسی چندگانه بخش زمانی ^[3] ویکی پدیا را مطالعه کنید.

در مورد پروتکل MAC قابل ذکر است که لایه MAC در شبکه یکی از لایه های کلیدی محسوب می شود و پروتکل‌هایی توسط افراد و سازمان های مختلف برای این لایه ارائه شده است. مهمترين هدف پروتکل LEACH، داشتن ايستگاه های محلی (سرخوشه ها) برای کاهش مصرف انرژی ناشی از انتقال داده ها به يک ايستگاه مبنای دوردست یا همان گره سینک است. به این ترتیب که به جای انتقال اطلاعات از تک تک گره ها به گره سینک یک گره سرخوشه اطلاعات را از گره های دورو برش (متعلق به خوشه خود) جمع آوری کرده و به گره سیک ارسال می کند.

^[4]

عملکرد پروتکل LEACH

همانطور که گفتیم پروتکل LEACH یک پروتکل مسیریابی مبتنی بر مکانیزم خوشه‌بندی است که در آن گره‌ها با هم مرتبط می‌شوند تا خوشه‌های جداگانه ایجاد کنند. بنابراین، هر خوشه دارای یک گره سر به نام سرخوشه است که داده‌های اعضای خوشه را جمع‌آوری می‌کند، سپس آن را به سینک می‌فرستد.

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

در نتیجه برای هر گره p/1 احتمال وجود دارد تا سر خوشه شود و در دورهای بعدی نمی تواند انتخاب شود در نتیجه  تمامی گره ها  شانس انتخاب شدن به عنوان سر خوشه را به یک اندازه دارند و بقیه گره ها به اعضای خوشه (یا سر غیر خوشه) تبدیل می شوند و نسبت به نزدیکی سرخوشه ای را برای خود انتخاب می کنند.

 

معماری پروتکل LEACH

مراحل عملکرد پروتکل leach

عملکرد پروتکل leach به چندین مرحله تقسیم می شود:

1- مرحله نصب

هر مرحله با عملکرد نصب آغاز می شود که خوشه ها در آن سازماندهی می شوند. در این مرحله سر خوشه و خوشه ها انتخاب می شوند.

همانطور که قبلا گفتیم انتخاب سر خوشه بصورت تصادفی انجام می گیرد و بستگی به عدد تصادفی دارد که در ابتدای هر دور توسط حسگر انتخاب می شود و عدد آن بین 0 و 1 است.

اگر آن عدد در هر حسگر به مقدار thresh hold  مشخص شده توسط معادله زیر نزدیکتر باشد در آنصورت گره به عنوان سر خوشه انتخاب می شود.

که P_L درصد سر خوشه ها در هر دور است و r  دور فعلی بوده و c تعداد گره هایی هست که تا الان در دوره 1/ P_L سر خوشه نشده اند.سپس گره ها طبق سیگنالی که از سرخوشه دریافت می کنند که هر چه سیگنال قوی تر باشد نشان از نزدیکی آن به سرخوشه می باشد خوشه تشکیل می دهند.

بعد از آن که خوشه ها تشکیل شد هر سر خوشه یک برنامه زمانبندی TDMA برای گره های عضو خوشه خود ارسال می کند. این برنامه زمانبندی بازه زمانی را که هر گره اجازه دارد در آن بازه اطلاعات خود را به گره سر خوشه ارسال کند مشخص می کند.

 

2- مرحله انتقال

به دنبال مرحله نصب مرحله انتقال داده قرار دارد که از چندین فریم تشکیل شده است و نسبت به مرحله اول طولانی تر است.در این مرحله هر گره مشترک اطلاعات خود را از محیط جمع آوری کرده و در بازه زمانی مشخص شده TDMA خود اطلاعات را به سر خوشه خود می فرستد در نتیجه تنها سرباری که برای آنها وجود دارد برقراری ارتباط درون خوشه ای است.

سر خوشه داده های دریافتی از اعضای خوشه را گروه بندی می کند و فشرده سازی می کند، سپس داده های انباشته شده را با استفاده از کد CDMA(برای جلوگیری از برخود ) به گره سینک ارسال می کند.

گره های سر خوشه به انرژی بیشتری نیاز دارند بنابراین انتخاب گره ثابت موجب تخلیه سریع انرژی می شود که در پروتکل LEACH سرخوشه بطور ثابت انتخاب نمی شود.

از طرفی هم گره های انتخاب شده با در نظر گرفتن انرژی یکسان انتخاب می شوند که در عمل ممکن است گرهی با انرژی کم هم انتخاب شود که این مورد از معایب یا محدودیت های پروتکل leach  محسوب می شود.

همچنین استفاده از اجتماع/ترکیب داده در سرخوشه ها، حجم پیغام ارسالی به ايستگاه مبنا را کاهش داده و موجب ذخیره  انرژی می گردد.

^[5]

مزیت های پروتکل LEACH

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

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

علاوه بر این، این واقعیت که فقط سر خوشه ها مسئول انتقال داده ها به سینک هستند، به صرفه جویی در مصرف انرژی نیز کمک می کند.

 اعضای خوشه‌ها با سر خوشه های مربوطه خود ارتباط برقرار می‌کنند، که به طور قابل توجهی به کاهش داده‌های انتقال و حفظ انرژی کمک می‌کند.

علاوه بر این، طول جدول مسیریابی ذخیره شده در هر گره حسگر کاهش می یابد زیرا ارتباطات به صورت خوشه ای ایجاد می شوند.

برای جلوگیری از تداخل گره ها LEACH از برنامه زمان بندی TDMA استفاده می کند.

برای جلوگیری از برخود سر خوشه ها کد CDMA توسط پروتکل استفاده می شود. علاوه بر آن در پروتکل LEACH گره ها تا رسیدن نوبتشان برای ارسال داده در حالت sleep قرار می گیرند.

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

 معایب پروتکل LEACH

در  مقابل این مزیت ها پروتکل LEACH یکسری محدودیت هایی نیز دارد. به عنوان مثال استقرار سر خوشه ها و تعداد خوشه ها در هر دور به دلیل انتخاب تصادفی سر خوشه ها نمی تواند تضمین شود.

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

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

یکی دیگر از اشکالات آن، استفاده از تک گام توسط گره سرخوشه برای برقراری ارتباط با گره سینک است، که باعث می شود پروتکلLEACH برای شبکه های بزرگ قابل استفاده نباشد.

پروتکل های بر گرفته از LEACH

این پروتکل ها بر سه دسته هستند: آنهایی که مبتنی بر انتخاب سر خوشه (CH) هستند. دسته دوم مبتنی برجمع آوری اطلاعات و دسته سوم مبتنی بر هر دو مورد انتخاب سر خوشه و جمع آوری اطلاعات هستند.

 

طبقه بندی پروتکل های مشتق شده از پروتکل LEACH

مقایسه الگوریتم های مشتق شده از پروتکل LEACH

نام پروتکل	نقاط قوت		نقاط ضعف
LEACH	افزایش چرخه زمانی شبکه با استفاده از زمانبندی TDMA مصرف انرژی را متعادل می کند. کاهش تعداد بسته های انتقالی کاهش اتلاف انرژی گره ها		استقرار غیر یکنواخت گره های سرخوشه انتخاب تصادفی سر خوشه ها تعداد گره ها در هر خوشه به طور مساوی توزیع نشده است. استفاده از تک هاپ
LEACH-B	تعداد یکنواخت سر خوشه ها در نظر گرفتن انرژی باقی مانده پس از اولین دور افزایش طول عمر شبکه		رشد هزینه های سربار
I-LEACH	انتخاب گره سر خوشه  بر اساس انرژی باقیمانده و مکان گره ها		سر خوشه داده های جمع آوری شده را یکپارچه می کند تا هزینه انتقال داده های تکمیلی را کاهش دهد، که برای گره هایی که داده های متفاوتی دریافت می کنند، عملی نیست.
LEACH-C	در یک منطقه شبکه کوچک به تعداد زیادی چرخش می رسد. انتخاب سر خوشه با توجه به انرژی باقی مانده گره است. روش متمرکز سازی توزیع سرخوشه بهتری را ارائه می دهد. معرفی تعداد بهینه ای از خوشه ها		به اطلاعات مکان گره ها نیاز دارد. متمرکز سازی باعث ایجاد سربار روی سینک می شود. انتقال با استفاده از تک هاپ سربار اضافی تولید می کند.
LEACH-M	متحرکی هر دو گره های سرخوشه و غیر سر خوشه بهره وری انرژی بسیار بالا		سربار اضافی
LEACH-ME	پشتیبانی از تحرکی گره ها انتخاب سر خوشه بر پایه کمترین تحرک		افزایش سربار
VH-LEACH	انتخاب سر خوشه ها بر اساس انرژی باقی مانده آنها هنگامی که سر خوشه اصلی به یک آستانه رسید، سر خوشه را با گره نائب سرخوشه جایگزین می کند.		عملکر اضافی برای گره نائب سرخوشه استفاده از تک هاپ برای هدایت داده ها از سر خوشه ها به ایستگاه اصلی .
LEACH-T	تعداد اسلات زمانی را در TDMA بر اساس اعضای خوشه اصلاح می کند. تعداد بهینه ای از خوشه ها را ارائه می دهد.		انتخاب سرخوشه ها بصورت تصادفی استفاده از تک هاپ برای هدایت داده ها از سر خوشه ها به گره اصلی یا سینک.
TB-LEACH	افزایش چرخه زمانی شبکه تعداد سرخوشه ها ثابت است.		انتخاب سرخوشه بر اساس یک تایمر تصادفی است.

سخن آخر در مورد آموزش پروتکل LEACH

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