توضیحات

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

 

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

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

شبکه های حسگر بی سیم مجموعه ای از سنسورهای حسگر بی سیم است که در محیط به صورت تصادفی برای جمع آوری اطلاعات پراکنده شده اند. به طور کلی شبکه های حسگر بی سیم جهت جمع آوری اطلاعات در مناطقی که کاربر نمی تواند حضور داشته باشد مورد استفاده قرار می گیرند. در یک شبکه حسگر، حسگرها به صورت جداگانه مقادیر محلی را نمونه برداری می کنند و این اطلاعات را در صورت لزوم برای حسگرهای دیگر و درنهایت برای مشاهده گر اصلی ارسال می نمایند. شبکه های حسگر بی سیم معمولاً در محیط های سخت که دسترسی انسان به آن مکان ها سخت و پرهزینه است استفاده می شوند، روند استفاده از شبکه های حسگر در سال های پایانی دهه ۸۰ و سال های آغازین۹۰ توسط وزارت دفاع آمریکا، DARPA و چند کشور دیگر ادامه داشت. در اواسط دهه ۹۰ با تعریف برخی استانداردها از جمله  1999IEEE فناوری های تجاری هم پا به عرصه وجود گذاشتند و گروه های مختلف تحقیقاتی فعال در زمینه ارتباطات بی سیم وارد بازار وسيع بالقوه غیرنظامی شدند. از شبکه های حسگر بی سیم در هواشناسی، کشاورزی، زلزله نگاری، صنایع نظامی و جنگ ها، ایجاد محدوده ی امنیتی و غیره استفاده می شود.

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

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

موارد مختلفی در این حوزه وجود دارند که می توانند بر کیفیت انتقال داده ها در شبکه تأثیر گذار باشند. یکی از این موارد انتخاب بهینه گره سرخوشه برای مدیریت هر یک از خوشه ها است؛ چنین گره ای علاوه بر توانایی مدیریت جریان داده های زیر گره های مجموعه ی خود باید دسترسی مناسبی به تمام خوشه خود و نیز به گره چاهک داشته باشد. علاوه بر این توزیع سرخوشه ها باید به گونه ای باشد که خوشه هایی با حجم متناسب و تعداد کافی در شبکه را تأمین نمایند. از این گذشته، عملیات خوشه بندی و انتخاب سرخوشه ها باید در دوره های زمانی مناسب و با هدف جلوگیری از تحمیل حجم کاری سنگین به تعداد محدودی از گرهها تکرار شود.

انتخاب سرخوشه مناسب برای خوشه ها در الگوریتم های توزیع شده از مسائل مهم است. به خاطر اینکه گره های شبکه دارای دید محلی از وضعیت فعلی خود در شبکه هستند؛ نداشتن دید جامع باعث می شود تا انتخاب سرخوشه مناسب برای خوشه مشکل شود.

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

شبکه های حسگر بی سیم:

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

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

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

شکل انتقال داده های گره های حسگر به ایستگاه مبنا.

 

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

خوشه بندی در شبکه های حسگر بی سیم:

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

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

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

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

طراحی شمای خوشه بندی با دو مسئله اساسی روبرو است 1) چه تعداد خوشه باید ایجاد گردد. ۲) خوشه ها چطور باید ایجاد شوند.

اگر اندازه خوشه های ایجادشده متناسب نباشد باعث می شود به سر خوشه هایی که در خوشه های بزرگ تر قرار گرفته اند بار بیشتری تحمیل شود. ایجاد خوشه های متوازن و بهینه در شبکه یکی از مسائل مهم و اساسی است. این کار باید به صورتی انجام شود که بار محاسباتی سنگینی نیز به شبکه تحميل نشود.

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

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

اهداف مهم در خوشه بندی:

الگوریتم های خوشه بندی دارای اهداف گوناگونی هستند. گاهی اهداف خوشه بندی به منظور تسهیل در برطرف کردن نیازهای کاربردی تغییر می کند. در اینجا چند هدف خوشه بندی که اغلب مورد توجه اند را بیان میکنیم:

استحکام بالا:

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

توازن بار:

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

افزایش ارتباط و کاهش تاخیر:

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

بیشترین طول عمر شبکه:

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

پارامترهای مهم در خوشه بندی:

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

برخی از این پارامترها عبارتند از:

تعداد خوشه ها:

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

ارتباط درون خوشه ها:

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

قابلیت حرکت حسگرها و سرخوشه ها:

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

انواع گره ها و نقش آن ها:

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

انتخاب سرخوشه ها:

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

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

پروتکل های مسیریابی مبتنی برخوشه:

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

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

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

پروتکل LEACH

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

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

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

شکل ساختار پروتکل LEACH.

 

منطق فازی:

مجموعه های فازی از تعمیم نظریه کلاسیک مجموعه ها حاصل می آید. مجموعه های فازی مجموعه ای است که اعضای آن شامل درجة عضویت هستند. مجموعه فازی توسط دکتر لطفی زاده در سال ۱۹۶۵ به صورت الحاقی به تئوری کلاسیک مجموعه ها اضافه شد. در تئوری کلاسیک مجموعه ها، عضویت اعضاء در یک مجموعه به صورت جملات باینری براساس شروط دودوئی تعیین می شود. یک عضو به مجموعه یا تعلق دارد یا ندارد. درعوض در تئوری فازی دستیابی تدریجی عضویت اعضاء در مجموعه مجاز است. اساسا استنتاج فازی فرآیندی فرمول شده از یک مجموعه داده ورودی به یک مجموعه داده خروجی است. یک سیستم فازی اصولا از سه بخش تشکیل شده است: فازی سازی موتور استنتاج و غیرفازی ساز.

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

پایگاه قوانینیک سری از قوانینIF-THEN است که متغیرهای فازی ورودی را توسط متغیرهای زبانی به متغیرهای فازی خروجی مرتبط می کند و هرکدام از آنها با یک مجموعه ی فازی و عملگرهای ضمنی فازیAND و OR و غیره توصیف می شوند. در هر یک از پیاده سازی های سخت افزاری از موتورهای فازی بدیهی است که قدرت پردازش و زمان بهینه از عمده ترین مسائل هستند. در شکل زیر بلوک دیاگرام کلی یک سیستم استنتاج فازی قابل مشاهده است.

شکل بلوک دیاگرام کلی یک سیستم استنتاج فازی.

 

معمولاً سیستم فازی که در موتور استنتاج یک سیستم خبره استفاده می شود یک سیستم فازیMamdani است. سیستم فازی ممدانی یک روش سادهی قانون گرا است که نیاز به محاسبات پیچیده ندارد و می تواند از قوانینIF-THEN برای کنترل سیستم ها استفاده کند. دی فازی کننده عمل دی فازی را روی فضای راه حل فازی انجام می دهد. یعنی یک مقدار خروجی دقیق از فضای فازی راه حل پیدا می کند. برخی از روش های معمول دی فازی عبارتند از: مرکز ناحیه (COA)، مرکز گرانش (COG)، مرکز توسعه یافته ناحیه (ECOA)، میانگین ماکسیما (MeOM) و غیره.

سرخوشه توسط پایگاه اصلی در هر دور با استفاده از سه واصف فازی یعنی انرژی گره(energy)، تمرکز گره(concentration) و مرکزیت گره(centrality) با توجه به کل خوشه انتخاب می شود.

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

یک سیستم استنتاج فازی، از چهار قسمت اصلی زیر تشکیل شده است: ۱) فازی ساز، که مبدل قطعی ورودی به مقادیر فازی است. ۲) پایگاه دانش، که اطلاعات قواعد و توابع فازی را در خود دارد. ۳) موتور استنتاج، که در واقع مکانیزم استدلال سیستم را مشخص می کند. ۴) نافازی کننده، که خروجی سیستم را به یک عدد قطعی و حقیقی تبدیل می کند.

اطلاعات خبره بر اساس سه پارامتر زیر بیان می شوند:

انرژی: متغیر انرژی که سطح انرژی یک گره را نمایش می دهد.

تمرکز گره: متغیر پراکندگی تعداد همسایه های یک گره را نمایش می دهد.

مرکزیت: متغیر مرکزیت مشخص کننده این است که یک گره چقدر در مرکزیت یک خوشه قرار دارد.

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

متغیرهای زبانی:

متغیرهای زبانی که برای ورودی های فازی انرژی و تمرکز استفاده شده اند به سه سطح low ,med و high تقسیم شده اند. برای ورودی فازی مرکزیت متغیر های زبانی far، adequate و close  نشان دهنده سطح متغیر مورد نظر است. خروجی سیستم فازی که نشان دهنده سطح شانس هر نود برای سرخوشه شدن است هفت سطح very small, small, rather small, medium, rather large, large, and very large است.

با توجه به جدول زیر تفسير قوانین به این صورت است:

جدول قوانین فازی:

Sr. No	Energy	Concentration	Centrality	Chance
1	Low	Low	Close	Small
2	Low	Low	Adequate	Small
3	Low	Low	Far	Very Small
4	Low	Medium	Close	Small
5	Low	Medium	Adequate	Small
6	Low	Medium	Far	Small
7	Low	High	Close	Rather Small
8	Low	High	Adequate	Small
9	Low	High	Far	Very Small
10	Medium	Low	Close	Rather Large
11	Medium	Low	Adequate	Medium
12	Medium	Low	Far	Small
13	Medium	Medium	Close	Large
14	Medium	Medium	Adequate	Medium
15	Medium	Medium	Far	Rather Small
16	Medium	High	Close	Large
17	Medium	High	Adequate	Rather Large
18	Medium	High	Far	Rather Small
19	High	Low	Close	Rather Large
20	High	Low	Adequate	Medium
21	High	Low	Far	Rather Small
22	High	Medium	Close	Large
23	High	Medium	Adequate	Rather Large
24	High	Medium	Far	Medium
25	High	High	Close	Very Large
26	High	High	Adequate	Rather Large
27	High	High	Far	Medium

 

 

مثال: اگر مقدار انرژی یک گره low باشد، تعداد همسایه های این گره نیزlow باشد و مقدار متغیر مرکزیت آن نسبت به همسایگان نیزclose باشد شانس این گره برای سرخوشه شدن smallیعنی کم است. چون ورودی ها سه متغیر هستند و هر متغیر نیز سه سطح مختلف می تواند داشته باشد، پس جدول قوانين 27 = 3³ قانون دارد. تابع عضویت سطوح medium و adequate به صورت مثلثی هستند. سطوح high، low، far، close به صورت ذوزنقه ای می باشند.

شكل مجموعه فازی مربوط به متغیر انرژی

 

شكل مجموعه فازی مربوط به متغیر تمرکز

 

 

شکل مجموعه فازی مربوط به متغیر مرکزیت

 

شکل مجموعه فازی مربوط به متغیر شانس

 

برای مقایسه با روش LEACH، 20 گره به صورت تصادفی در فضای 100*100 متر با احتمال سرخوشه 0.05 توزیع شدند. بنابراین حدود 1 گره در هر دور سرخوشه می شود. هر دو الگوریتم مصرف انرژی درون خوشه ای را بهینه نموده اند و بنابراین بر روی انرژی مورد نیاز جهت ارسال به پایگاه مبنا تاثیری نمی گذارند.

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