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

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

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

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

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

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

برای مطالعه بیشتر در زمینه WSN و موارد مهم مرتبط با آن؛ فایل آماده موجود در این زمینه را مد نظر قرار دهید.

• پاورپوینت شبکه حسگر بی سیم WSN— کلیک کنید.

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

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

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

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

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

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

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

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

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

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

۱- مرحله نصب

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• پاورپوینت پروتکل خوشه بندی ASLPR- کلیک کنید.

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

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

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

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

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

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

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

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

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

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

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

در نهایت پروتکل‌های دیگری که از LEACH مشتق شده‌اند را نام بردیم و تعدادی از آن‌ها را باهم مقایسه کردیم. مجموعه آموزشی پی استور با ارائه انواع پاورپوینت‌های آماده در موضوعات متنوع و جذاب، همراه و یاور شما عزیزان در عرصه‌های آکادمیک است.