الگوریتم مسیریابی لیچ (Leach) – مبانی اولیه + فیلم آموزشی رایگان
لیچ یک پروتکل مسیریابی مبتنی بر خوشه در شبکههای حسگر بیسیم است که اولین بار در سال 2000 توسط هاينزلمن و همکارانش معرفی شد. هدف از این پروتکل کم کردن انرژی مصرفی نودها به منظور بهبود طول عمر شبکه حسگر بیسیم میباشد.
فیلم آموزشی مبانی اولیه الگوریتم مسیریابی لیچ
عملکرد لیچ
در لیچ نودها (حسگرها) اطلاعات خود را به سرخوشه مربوطهشان ارسال کرده و سپس سرخوشهها دادههای دریافتی را جمعآوری و فشرده کرده و در قالب یک بسته به سمت ایستگاه اصلی (یا سینک) میفرستند. هر نود از یک الگوریتم تصادفی برای تعیین اینکه آیا در چرخه جاری نقش سرخوشه را بگیرد یا خیر استفاده میکند. لیچ فرض میکند که هر نود توان رادیویی لازم برای ارسال به پایگاه اصلی یا نزدیکترین سرخوشه را دارد (هرچند استفاده از حداکثر توان رادیویی به صورت مداوم سبب مصرف هدر رفتن انرژی میشود).
نودهایی که سرخوشه میشوند، تا p چرخه نمیتوانند دوباره نقش سرخوشه را بگیرند. P درصد دلخواهی از تعداد خوشههاست. بنابراین در هر چرخه هر نود با احتمال 1/p امکان دارد سرخوشه شود. در پایان هر چرخه، نودهایی که سرخوشه نیستند نزدیکترین سرخوشه به خود را انتخاب کرده و به خوشه مربوط به آن میپیوندد. سپس هر سرخوشه برای هر نود عضو خوشهاش یک جدول زمابندی جهت مشخص کردن زمان ارسال داده، ایجاد میکند (هر نود فقط در زمان مشخص شده میتواند به سرخوشه اطلاعات ارسال کند).
تمام نودهای غیرسرخوشه، تنها از طریق پروتکل TDMA با سرخوشه ارتباط برقرار میکنند و این کار را با توجه به جدول زمانبندی ساخته شده توسط سرخوشه انجام میدهند. برای هدر نرفتن انرژی، نودها تنها در اسلات زمانی اختصاصی مشخص شده رادیوهایشان را روشن نگه میدارند.
در لیچ از متد دسترسی به رسانه CDMA نیز استفاده میشود؛ هر خوشه از کدهای متفاوت CDMA استفاده میکند تا بدین ترتیب تداخل بین خوشهها کمینه شود.
ویژگیهای لیچ
ویژگیهای این الگوریتم عبارتند از:
- مبتنی بر خوشه
- انتخاب تصادفی سرخوشه در هر چرخه به صورت چرخشی، و یا انتخاب سرخوشه بر اساس داشتن بالاترین سطح انرژی
- عضویت تطبیقی در خوشهها
- تجمیع داده در سرخوشه
- برقراری ارتباط مستقیم بین سرخوشه با نود سینک و یا کاربر
- ارتباط با سرخوشه با استفاده از متد TDMA
شبیهسازی
شبیهسازهای منبعباز و تجاری فراوانی برای شبیهسازی لیپچ وجود دارند همچون:
1) ns (متنباز)
2) OPNET
3) NetSim (نرمافزار اختصاصی)
4) ++OMNeT (محیط یکپارچه توسعه نرمافزار، IDE)
5) TinyOS (متنباز)
بعضی نقاط ضعف لیچ
- در نسخه اصلی این پروتکل به علت اينکه تمام نودها با احتمالي ثابت به عنوان سرخوشه انتخاب ميشوند ممکن است برخي از نودهای حسگر نامناسب نيز انتخاب گردند که این امر باعث ايجاد هزينههای اضافی میشود.
- در اين پروتکل ممکن است خوشههایی با تنها يک عضو ايجاد شوند که در این صورت به دلیلی ارسال مستقیم اطلاعات به ایستگاه اصلی، انرژی این نودها به سرعت تمام خواهد شد. این در حالیست که این خوشهها مي توانند با ادغام با خوشههای مجاور از بين بروند.
- از آنجا که انتخاب سرخوشهها در اين روش تصادفي است، ممکن است برخي از انتخاب ها باعث مصرف سريع انرژي بعضی از نودهای حسگر مهم که در شبکه نقش اتصال بين دو زير شبکه را دارند شده و اين مسئله سبب گسسته شدن شبکه شود.
تا کنون نسخه های بهبوديافته گوناگونی از پروتکل LEACH همانند E- LEACH، TL- LEACH، M- LEACH ، LEACH-C و V- LEACH توسط محققان ارائه شده اند.