توضیحات

 

پروژه متلب خوشه بندی شبکه های حسگر بیسیم متحرک(MWSN) با الگوریتم ژنتیک

 

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

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

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

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

شکل اجزای سازنده حسگر بیسیم.

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

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

 

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

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

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

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

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

چالش ها در شبکه های حسگر بی سیم متحرک:

عوامل و چالش های اصلی که بر طراحی، کارایی و عملیاتی بودن این شبکه ها تأثیر دارند:

• مسیریابی
• انرژی بهینه
• شمای دسترسی به رسانه
• امنیت
• وسعت پذیری
• فراهم کردن کیفیت سرویس
• توجه بر آرایش گره ها
• پخش فراگیر
• آدرس دهی

 

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

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

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

• نظارت بر محیط
• جستجو و نجات و نظارت بلادرنگ مواد خطرناک
• نظارت بر حیات وحش
• نظارت بر گردبادها و …

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

 

چندین پروتکل خوشه بندی برای شبکه های حسگر بی سیمWSN پیشنهاد شده است، تنها تعداد کمی از آنها متحرک بودن گره ها را پشتیبانی می کنند. در ادامه، برخی از پروتکل های خوشه بندی موجود برای شبکه های حسگر بی سیم ثابت و متحرک به همراه جزئیات عملکرد آنها ارائه می شوند.

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

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

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

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

 

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

 

طراحی خوشه بندی:

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

طراحی شمای خوشه بندی با دو مسئله اساسی روبرو است

۱) چه تعداد خوشه باید ایجاد گردد.

۲) خوشه ها چطور باید ایجاد شوند.

تعداد خوشه های مورد نیاز:

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

 

چگونگی ایجاد خوشه ها:

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

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

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

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

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

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

خوشه بندی با استفاده از الگوریتم های تکاملی:

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

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

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

پروتکل LEACH

پروتکل LEACHاحتمالاً اولین پروتکلی است که برای شبکه های حسگر بی سیم جهت انتخاب سرخوشهCH به صورت پویا متشکل از گره های حسگر ثابت همگن که به صورت تصادفی مستقر شده اند است. در این پروتکل، همه گره ها شانس تبدیل به سرخوشه را دارند تا انرژی گره ها به صورت یکنواخت مصرف شود. گره های نماینده برای خوشه ها به صورت تصادفی انتخاب شده و باتوجه به انرژی باقی مانده به صورت چرخشی متوالی انتخاب می شوند. در هر دور ۵% گره ها در شبکه حسگر بی سیم به عنوان سرخوشه در نظر گرفته می شوند و همه آنها داده ها را به ایستگاه ثابت ارسال می کنند. برای انتخاب سرخوشه، هر یک از گره های حسگر Xیک مقدار آستانه T(n) بر اساس احتمال سرخوشه بودن محاسبه می کنند و همچنین یک عدد تصادفی (بین۰ و ۱) انتخاب می کنند. اگر این عدد انتخاب شده توسط گره X کمتر از T(n) باشد گره x در حال حاضر به عنوان سرخوشه انتخاب می شود و یک پیغام فراگیر به همه گره ها ارسال می کند و سرخوشه بودن خود را اعلام می کند. گره هایی که پیغام سرخوشه را دریافت می کنند، با توجه به قدرت سیگنال دریافتی تصمیم می گیرند که عضو کدام خوشه باشند. مجموعه ای از داده ها در هر خوشه به صورت متمرکز و دوره ای با استفاده از روش TDMA به گره سرخوشه ارسال می شود. گره های حسگر داده ها را به سرخوشه، با توجه به برنامه زمان بندی ارسال می کنند. پس از اتمام برنامه زمان بندی، سرخوشه تمام داده ها را به ایستگاه اصلی انتقال می دهد. با این حال، در پروتکل LEACH، سرخوشه انتخاب شده ممکن است در یک گوشه ای از شبکه قرار گرفته باشد و برخی از گره ها، سرخوشه ای در اطراف خود نداشته باشند. علاوه بر این، خوشه بندی انجام شده در هر دوره به عنوان خوشه بندی با انرژی کارآمد در نظر گرفته نمی شود.

پروتکلLEACH متمرکز:

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

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

پروتکل خوشه بندی ترکیبی توزیع شده با انرژی کارآمد:

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

توزیع مصرف انرژی در پروتکل HEED طول عمر همه گره ها در مجموعه گره های همسایه را افزایش می دهد

که به ثبات آنها کمک می کند. علاوه بر این،HEED در پایان خوشه بندی، توزیع مناسب سرخوشه ها را در تعداد ثابتی از تکرارها تضمین می کند.

پروتکل جمع آوری داده ها با انرژی کارآمد:

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

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

الگوریتمTASC:

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

پروتکلTEEN:

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

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

پروتکل ACE:

پروتکل ایجاد خو شه ACE یک پروتكل موضعی و فعال است که در آن حسگرها ثابت هستند و هر گره حسگر تنها با مجموعه ای کوچک از حس گرها در نزدیکی خود ارتباط برقرار می کند. پروتکل ACE بین سه حالت ممکن برای گره های حسگر تمایز قائل می شود، ۱- خوشه بندی نشده(هنوز در فرایند خوشه بندی قرار دارد)، ۲- پیرو(یک گره متعلق به یک خوشه با سرخوشه معین) و در نهایت۳- سرخوشه.

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

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

الگوریتم LEACH – M

این الگوریتم برای حمایت از موبایل بودن گره ها برای الگوریتمLEACH ارائه گردید. الگوریتم -LEACH

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

الگوریتمLEACH-ME

این الگوریتم، پروتکل LEACH – M را در انتخاب سرخوشه های بهینه بهبود می بخشد.

الگوریتم ژنتیک(GA):

در دهه های اخیر، الگوریتم ژنتیک(GA) به طور وسیع در بسیاری از مسائل بهینه سازی با موفقیت قابل توجهی مورد استفاده قرار گرفته است. عملگرهای بیولوژیکی، مانند ترکیب و جهش در بسیاری از الگوریتم های تکاملی استفاده می شوند. بسیاری از تحقیقات مرتبط با این موضوع تمرکز خود را بر روی توسعه ی عملگرهای سازگار می گذارند. الگوریتم ترکیب باکتری، لایه های زیرین الگوریتم ژنتیک معمولی را شکافته و از عملگر انتقال سطحی ژنتیکی که از ترکیب باکتریها در طبیعت الهام گرفته استفاده می کند. در این روش، اثبات شده است که اطلاعات ژنتیکی کروموزوم اهداکننده برای کروموزوم گیرنده مفید است.

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

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

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

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

عملکرد الگوریتم ترکیب باکتری:

عملگر ترکیب باکتری به دو قسمت تقسیم شده است.

• انتقال سطحی ژنها
• رقابت

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

آرگومان های ورودی الگوریتم ترکیب باکتری عبارت اند از:

• کروموزوم اهداکننده
• کروموزوم دریافت کننده
• بهترین برازندگی
• بدترین برازندگی پیداشده

شکل زیر روند الگوریتم ترکیب باکتری را به طور کامل نشان می دهد.

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

انتقال سطحی ژن ها:

در مرحله اول از الگوریتمBC رشته ای از ژنها از کروموزوم اهدا کننده انتخاب و بروی کروموزوم گیرنده در همان مکان جایگذاری می شود. ابتدای رشته ژن مربوطه به صورت تصادفی انتخاب می شود.

الگوریتم ترکیب باکتری با انتخاب مداوم رشته ای از ژن ها از روی کروموزوم اهداکننده، کار خود را شروع

می کند. این رویه دو پارامتر ورودی دارد:

• طول رشته ای که باید کپی شود (L).
• نقطه شروع رشته ژنی که باید کپی شود (P).

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

رقابت:

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

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

شکل مراحل اجرای الگوریتم ترکیب باکتری.

 

• الگوریتم با ایجاد جمعیت اولیه از کروموزوم ها شروع می شود. برای این منظور، کروموزوم ها به صورت تصادفی به تعداد اندازه جمعیت ایجاد می شود که جمعیت اولیه ما را می سازند.
• تنها عملگر در الگوریتم پیشنهادی ترکیب باکتری بوده و کروموزوم اهداء کننده کروموزوم با بهترین برازندگی از بین جمعیت است.
• محاسبهL نیاز به بدترین و بهترین مقادیر دارد که به عنوان بدترین برازندگی و بهترین برازندگی نامیده می شوند. بهترین برازندگی از بهترین کروموزوم به وجود می آید. بدترین کروموزوم باید در حین اجرای الگوریتم ذخیره شود. در این مرحله، بهترین کروموزوم و بدترین کروموزوم به صورت جداگانه از جمعیت ذخیره می شوند.
• در الگوریتم استفاده شده، یک نسل وقتی پایان مییابد که عملگر BC بروی تمامی کروموزوم ها اعمال شود. درنتیجه، مراحل زیر برای هر نسل اعمال می شود:

1- اولین کروموزوم جمعیت انتخاب می شود.

۲. عملگر BC به بهترین کروموزوم به عنوان اهداء کننده و به کروموزوم دریافت کننده اعمال می شود.

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

۴. عملیات روی کروموزوم انتخاب شده تمام و الگوریتم به مرحله ۲ برای انتخاب کروموزوم بعدی خواهد رفت.

• مانند الگوریتم ژنتیک، شرط اتمام الگوریتم استفاده شده می تواند تعداد نسل که با نام حداکثر نسل شناخته می شود.

ارزیابیFitness بهینه در هر Round

اشکال زیر بهترین پاسخ به دست آمده در هر بار خوشه بندی توسط هر دو الگوریتم را نشان می دهد. در این

نمودارها الگوریتم ترکیب باکتری توانسته است در Clustering Roundیکسان نتایج بهتری را نسبت به

الگوریتم ژنتیک به دست آورد.

 

ارزیابیFitness به دست آمده در هر بار اجرا:

ارزیابیFitness به دست آمده در اجرای اول

 

ارزیابیFitness به دست آمده در اجرای دوم

 

 

ارزیابیFitness به دست آمده در اجرای سوم

 

ارزیابیFitness به دست آمده در اجرای چهارم

 

ارزیابیFitness به دست آمده در اجرای پنجم