تحقیق دانشگاهی – توزیع متعادل مصرف انرژی در شبکه‌های حسگر بیسیم با استفاده از خوشه‌بندی و …

پروتکل LEACH [۴۵]

یکی از مشهورترین پروتکل‌های کلاس‌بندی ارائه‌شده برای شبکه‌های حسگر بی‌سیم میباشد. این پروتکل از اولین پروتکل‌های کلاس‌بندی پویاست که به طور ویژه نیازهای شبکه‌های حسگر را در نظر گرفته است. این پروتکل از گره‌های حسگر ساکن همگن که به طور تصادفی پخش شده‌اند استفاده می‌کند. LEACH به عنوان مبنایی برای دیگر پروتکل‌های پیشرفته کلاس‌بندی در WSNها در نظر گرفته می‌شود. به طور کلی این پروتکل، یک پروتکل سلسله مراتبی، احتمالی، توزیع یافته و تک-گام است که با اهداف افزایش طول عمر شبکه‌های WSN از طریق توزیع مصرف انرژی در میان تمام گره‌های شبکه و کاهش مصرف انرژی در گره‌های شبکه با انجام عمل تجمیع داده و در نتیجه آن کاهش تعداد پیام‌های تبادلاتی، طراحی شده است. LEACH کلاس‌ها را با استفاده از الگوریتم‌های توزیع‌شده شکل می‌دهد که در آن گره‌ها به طور مستقل و بدون کنترل متمرکز تصمیم‌گیری می‌کنند. به‌منظور توازن انرژی مصرف‌شده در هر گره در هر دور کامل، همه گره‌ها شانس سرگروه شدن را دارند. در ابتدا یک گره با احتمال P تصمیم می‌گیرد که سرگروه شود و این تصمیم را پخش فراگیر می‌کند. پس از انتخاب سرگروه، همه سرگروه‌ها یک پیام اعلانی به دیگر گره‌ها پخش فراگیر می‌کنند و هر گره کلاسی را که می‌خواهد عضو آن باشد، مشخص می‌کند. هر گره کلاس خود را به گونه‌ای مشخص می‌کند که بتواند با کمترین انرژی، با سرگروه آن کلاس ارتباط برقرار کند. این کار بر اساس قدرت سیگنال پیام ارسال‌شده هر سرگروه صورت می‌گیرد. LEACH قادر است یک توازن مناسب مصرف انرژی به وسیله چرخش تصادفی سرگروه‌ها ایجاد نماید که موجب افزایش طول عمر شبکه می‌شود. بااین‌وجود و علی‌رغم مزایای این پروتکل، اشکالاتی هم دارد. به دلیل اینکه تصمیم‌گیری در مورد انتخاب سرگروه‌ها و چرخش آنها احتمالاتی است، بنابراین فرصت برای انتخاب گره‌های کم انرژی به عنوان سرگروه کماکان وجود دارد. به همین دلیل ممکن است سرگروه‌های انتخابی در یک منطقه خاصی از شبکه متمرکز باشند. بنابراین در این پروتکل، توزیع مناسب سرگروه‌ها قابل تضمین نیست و برخی گره‌ها هیچ سرگروه‌ای در محدوده خود نخواهند داشت [۳۵].
شکل ۲-۶ ساختار کلی شبکه را به صورت خوشهبندی در الگوریتم LEACH نشان میدهد.
شکل ‏۲‑۶: ساختار پروتکل LEACH

دانلود متن کامل پایان نامه در سایت jemo.ir موجود است

پروتکل LEACH متمرکز[۴۶]

الگوریتم کلاس‌بندی است که در آن تشکیل کلاس‌ها به صورت متمرکز و توسط گره چاهک انجام می‌گیرد. این الگوریتم مرحله انتقال داده مشابه با الگوریتم LEACH دارد و در طی آن هر گره اطلاعاتی در مورد موقعیت و سطح انرژی کنونی خود را به گره چاهک ارسال می‌کند. معمولاً این طور فرض می‌شود که هر گره از GPS برخوردار است. گره چاهک باید توزیع یکنواخت انرژی در بین کلاس‌ها را تضمین کند. بنابراین آستانه‌ای برای سطح انرژی تعیین نموده و گره‌هایی که انرژی بیشتر از آستانه تعیین‌شده دارند را به عنوان سرگروه‌های احتمالی انتخاب می‌کند. مسئله‌ی تعیین تعداد بهینه‌ی سرگروه‌‌ها یک مسئله‌ی NP-Hard است. گره چاهک بعد از تعیین سرگروه‌های دور جاری، پیغامی حاوی شماره شناسایی سرگروه را به هر گره ارسال می‌کند. اگر شماره شناسایی سرگروه گره‌ای با شماره شناسایی خودش تطابق داشته باشد، آن گره یک سرگروه است وگرنه یک گره عادی است و می‌توان تا مرحله انتقال داده مربوط به خود به حالت خواب فرو رود.LEACH-C کاراتر از LEACH بوده و به ازای هر واحد انرژی، در حدود ۴۰ درصد داده‌ی بیشتری را انتقال می‌دهد. زیرا گره چاهک دانش سراسری در مورد موقعیت و سطح انرژی گره‌های شبکه دارد. از این گذشته LEACH-C برخلاف LEACH، وجود تعداد بهینه خوشه‌ها را در هر دور تضمین می‌کند]۳۶[.

پروتکل خوشه‌بندی پیوندگرای وفقی با انرژی پایین[۴۷]

پروتکلی مبتنی بر LEACH-C است، که در آن مرحله تشکیل کلاس‌ها بصورت متمرکز و توسط گره چاهک به روشی مشابه با LEACH-C صورت می‌گیرد. LEA2C از روش کلاس‌بندی دو مرحله‌ای SOM و K-means استفاده می‌کند.
ورودی‌های SOM، مختصات گره‌های حسگر در فضای شبکه هستند. LEA2C آموزش پیوندگرا را از طریق به حداقل رساندن فاصله بین نمونه‌های ورودی (مختصات گره‌های حسگر) و نمونه‌های اولیه نقشه (ارجاع‌ها) که توسط تابع همسایگی خاصی وزن‌دهی شده‌اند، اعمال می‌کند. بعد از مرحله‌ی کلاس‌بندی، سرگروه‌های هر کلاس بر اساس یکی از سه شرط انتخاب می‌شوند]۳۶[:
گره‌ی دارای بیشترین سطح انرژی.
نزدیک‌ترین گره به گره چاهک.
نزدیک‌ترین گره به مرکز ثقل کلاس.
پس از آن مرحله انتقال داده شروع می‌شود و گره‌های عادی بسته‌های خود را به سرگروه‌ها مربوطه ارسال می‌کنند و سرگروه‌ها پس از مجتمع کردن داده‌های دریافتی آن‌ها را در قالب یک بسته به گره چاهک انتقال می‌دهند. در حالتی که از معیار گره‌ی دارای بیشترین انرژی برای انتخاب سرگروه استفاده شده باشد. پروتکل بعد از هر مرحله انتقال، نقش سرگروه را به گره‌ی دیگری واگذار خواهد کرد. مرحله انتقال تا زمان رخداد اولین مرگ گره‌های شبکه ادامه خواهد یافت. بعد از رخ‌ دادن اولین مرگ، مرحله کلاس‌بندی مجدد آغاز شده و مراحل قبلی تکرار خواهند شد. نتایج شبیه‌سازی، برتری LEA2C را بر پروتکل مبتنی بر LEACH دیگر بنام EECS به اثبات رسانده است]۳۷، ۳۸[. این برتری برحسب افزایش ۵۰ درصدی در طول عمر شبکه و حفظ پوشش شبکه‌ای در طول ۹۰ درصد عمر شبکه می‌باشد.

پروتکل LLACA [۴۸]:

این پروتکل با هدف از بین بردن اثرات منفی تغییرات مکرر توپولوژی شبکه در کلاس‌ها طراحی شده است. این پروتکل متشکل از دو فاز می‌باشد. در فاز اول، پروتکل شبکه مورد نظر را خوشه‌بندی می‌نماید. فاز دوم، فاز خوشه‌بندی دوباره در صورت نیاز و فاز حفظ خوشه‌های موجود تا جایی که امکان دارد می‌باشد. بخش خوشه‌بندی این پروتکل، یک الگوریتم کاملاً توزیع‌شده می‌باشد که در آن هر گره بر اساس اطلاعات محلی که از همسایگانش دریافت می‌کند، تصمیمی در مورد سرخوشه شدن می‌گیرد. این الگوریتم به طور مستقل بر روی هر یک از گره‌ها اجرا می‌شود. از مزایای این الگوریتم آن است که اگر خوشه‌ها اعتبار خود را از دست دادند، می‌توانند به صورت محلی خود را سازمان‌دهی مجدد کنند. فاز ابتدایی این پروتکل شامل چندین مرحله می‌باشد که در هر مرحله، هر گره از ما بین گره‌های در ارتباط با خود یک گره را به‌عنوان سرخوشه مشخص می‌نماید یا آن‌که نقش سرخوشه را به خودش می‌دهد. پس از انتهای فاز ابتدایی پروتکل هر گره نقش خود را می‌داند که یا سرخوشه است و یا عضوی از یک خوشه می‌باشد]۳۹[.
در شبکه‌های حس‌گر به علت حرکت برخی از حس‌گرها و یا خراب شدن آنها، توپولوژی شبکه حالت پویا دارد. یک گره می‌تواند به طور تصادفی به هر جای شبکه منتقل شود و از عضویت یک خوشه خارج شود و عضو خوشه دیگری شود. بنابراین هر پروتکل کلاس‌بندی نیاز به یک فاز خوشه‌بندی دوباره دارد. در LLACA زمانی که یک گره قصد دارد به عضویت یک خوشه دربیاید یک پیام JREQ به سمت گره‌های همسایه خود ارسال می‌کند و برای یک بازه زمانی منتظر می‌ماند. هر سرخوشه‌ای که پیام ارسال شده را دریافت نمود یک پیام JREP به سمت گره درخواست‌کننده ارسال می‌کند. در این بازه زمانی ۳ حالت زیر امکان دارد به وقوع بپیوندد]۳۹[:
اگر گره درخواست‌کننده تنها یک پیام JREP دریافت کند، در این صورت فرستنده پیام را به عنوان سرخوشه خود انتخاب می‌نماید و یک پیام CHSEL به سمت آن ارسال می‌نماید.
اگر بیشتر از یک پیام JREP دریافت کند، در این صورت گره‌ای را که دارای شماره ID بالاتری می‌باشد را به عنوان سرخوشه انتخاب می‌نماید و یک پیام CHSEL به سمت آن ارسال می‌نماید.
اگر گره درخواست‌کننده پیام JREP را از هیچ گره‌ای دریافت نکند، در این صورت آن یکی از همسایگان خود را که دارای بالاترین شماره ID می‌باشد را به عنوان سرخوشه انتخاب می‌نماید و یک پیام CHSEL به سمت آن ارسال می‌کند.
نکته آخر که باید در این پروتکل به آن توجه شود آن است که، هر گره یا دارای نقش سرخوشه است و یا به عنوان عضوی از یک خوشه می‌باشد. با توجه به این مسئله زمانی که یک گره قصد ترک خوشه خود را دارد با توجه به نقش خود پیام‌های کنترلی متفاوتی ایجاد می‌نماید. اگر گره دارای نقش سرخوشه باشد در این صورت یک پیام خوشه‌بندی مجدد به اعضای کلاس خود ارسال می‌کند و از آنها می‌خواهد که عمل خوشه‌بندی را مجدد انجام دهند. اما اگر گره تنها عضوی از خوشه بوده در زمان ترک خوشه خود تنها یک پیام ترک خوشه به سمت همسایگان خود ارسال می‌کند]۳۹[.

پروتکل CBHRP [۴۹]

یک پروتکل دولایه‌ای است که در آن مفهوم سرخوشه([۵۰]H-S)، به‌جای سرگروه معرفی و پیشنهادشده است. هر مجموعه سرخوشه، شامل یک سرگروه فعال و تعدادی سرگروه همیار می‌باشد. در هر لحظه تنها یک عضو H-S فعال است و بقیه در حالت خواب هستند. در این پروتکل چندین حالت: حالت کاندید، حالت غیر کاندید، حالت فعال، حالت همیار و حالت همیار غیرفعال برای گره‌ها ایجاد می‌شود. برای مجموعه گره‌های موجود در شبکه، اعضای H-S به طور سامانمند تنظیم شده‌اند تا مصرف انرژی کاهش یافته و در نتیجه طول عمر شبکه افزایش یابد]۴۰[. تفاوت این الگوریتم با LEACH، در آن است که هر خوشه دارای یک سرخوشه پویا و تعداد دیگری سرخوشه همکار در یک خوشه است. اعضای H-S مسئول کنترل و مدیریت شبکه هستند. این الگوریتم دارای دو فاز انتخاب و ارسال می‌باشد. در شروع فاز انتخاب، مجموعه‌ای از سرخوشه‌ها بصورت تصادفی انتخاب می‌شوند. این سرخوشه‌ها یک پیام اعلانی فراگیر کوتاه برد پخش می‌کنند. گره‌های حسگر، پیام‌های اعلانی را دریافت کرده و بر اساس قدرت سیگنال پیام‌های اعلانی، سرخوشه‌ی خود را انتخاب می‌کنند. سپس هر گره حسگر یک پیام تصدیق به سرخوشه انتخابی‌اش ارسال می‌کند. در هر تکرار از الگوریتم سرخوشه‌ها نیز بر اساس قدرت سیگنال‌های تصدیقی دریافت شده، مجموعه همیاران خود را انتخاب می‌کند. اعضای H-S مسئول ارسال پیام به گره چاهک هستند. هر فاز ارسال داده شامل چند دوره است. هر عضو H-S در طول یک دوره، یک بار سرخوشه می‌شود. یک دور کامل شامل چندین تکرار است. در یک دور، هر گره حسگر برای یک بار عضو H-S می‌شود. در طول یک دوره اعضای H-S دارای یک عضو در حالت فعال است و تعداد کمی از اعضا در حالت همیار و بقیه در حالت همیار غیرفعال هستند. در زمان ارسال آخرین فریم در یک دوره، یک عضو فعال بوده و بقیه همیار غیرفعال هستند. بنابراین هیچ عضوی در حالت همیار نیست. برای شروع دوره بعدی، یک عضو H-S حالت فعال را به دست می‌آورد و بقیه در حالت همیار هستند. با تکمیل یک تکرار، همه اعضای H-S حالت غیر کاندید را به دست می‌آورند. اعضایی که در حالت غیر کاندید هستند، واجد شرایط عضویت در H-S نیستند. برای شروع دور کامل بعدی، همه گره‌های حسگر غیر کاندید، حالت کاندید را به دست می‌آورند ]۴۰٫[ شکل ۲-۷ دیاگرام حالت را برای یک حسگر شبکه در الگوریتم CBHRP نشان میدهد.
شکل ‏۲‑۷حالت‌های مختلف گره حسگر در CBHRP [40]

این مطلب را هم بخوانید :  سامانه پژوهشی - تأثیر خطبه ی اوّل نهج البلاغه بر دیباچه های متون نظم و ...

پروتکل [۵۱]TEEN

بعد از این که کلاس‌ها تشکیل شدند سرخوشه‌ها دو آستانه را به همه حسگرها می‌فرستند. اسامی این آستانه‌ها، آستانه‌ی نرم و آستانه‌ی سخت می‌باشند. آستانه‌ی سخت در واقع مقداری از پارامتر در حال اندازه‌گیری است که اگر مقدار به‌دست آمده از یک حسگر از این آستانه بیشتر باشد، مقدار به‌دست آمده گزارش می‌شود، ولی اگر کمتر باشد دیگر این اتفاق نمی‌افتد. در واقع این آستانه باعث می‌شود که هر وقت مقدار پارامتر در محدوده دلخواه است گزارش شود و بدین‌صورت از حجم داده‌های ارسالی تا حد زیادی کاسته می‌شود. اما آستانه‌ی نرم مقداری از پارامتر در حال اندازه‌گیری است که هر وقت مقدار به‌دست آمده زیر آستانه‌ی سخت باشد اما بیشتر از نمونه قبلی پارامتر اندازه‌گیری شده باشد، حسگر باز هم مقدار پارامتر را گزارش می‌کند. وجود آستانه‌ی نرم نیز باعث کاهش داده‌های ارسالی می‌شود. با تنظیم سطوح آستانه‌ی نرم و سخت می‌توان حجم داده‌های ارسالی به گره چاهک را تنظیم کرد. برای ارسال داده‌ها به گره چاهک هر حسگر داده‌ی خود را به سرخوشه لایه اول می‌فرستد، سرخوشه لایه اول نیز آن را به سرخوشه لایه دوم می‌فرستد و در نهایت به ایستگاه پایه فرستاده می‌شود]۴۱٫[
TEEN در کاربردهایی مناسب است که گزارش اطلاعات به‌صورت پریودیک مورد نظر نباشد. یعنی هر وقت اتفاق خاصی در شبکه رخ داد گزارش شود. گره چاهک دارای منبع تغذیه پایدار می‌باشد، بنابراین محدودیت انرژی ندارد و نیاز به مسیریابی از گره چاهک به سایر گره‌ها نیست. بین گره‌ها و گره چاهک ارتباط نامتقارن وجود دارد زیرا گره‌ها دارای محدودیت انرژی هستند و نمی‌توانند پاسخ گره چاهک را به طور مستقیم بدهند. از ویژگی‌های این مدل آن است که گره‌ها تنها توانایی ارسال اطلاعات به سرگروه خود را دارند که این امر سبب صرفهجویی انرژی خواهد شد، تنها سرخوشه‌ها محاسبات اضافه‌ای را روی داده اجرا می‌کنند که این امر نیز موجب صرفه‌جویی انرژی خواهد شد. در هر زمان تغییر کلاس علاوه بر ویژگی سرخوشه‌ها، موارد زیر را نیز به اعضای خود ارسال میکند]۴۱ [:
آستانه سخت (HT[52])، این مقدار آستانه برای ویژگی‌های حس شده است. گره ای که این مقدار را حس می‌کند باید فرستنده خود را روشن کند و آن را به سرگروه گزارش بدهد.
آستانه نرم (ST[53])، یک تغییر کوچک در مقدار ویژگی‌ها حس شده است که گره را وادار به روشن کردن فرستنده و ارسال آن می‌کند.
ارزش حس‌شده([۵۴]SV)، که یک متغیر داخلی در گره‌ها برای ذخیره کردن اطلاعات حس شده می‌باشد.
زمانی یک گره در دوره زمانی کلاس جاری داده را ارسال خواهد کرد که هر دو شرط زیر برقرار باشد: مقدار ویژگی حس شده بزرگ‌تر از آستانه سخت باشد، مقدار ویژگی حس شده با SV با مقداری برابر یا بزرگ‌تر از ST اختلاف داشته باشد.
ویژگی‌های مهم این پروتکل عبارت‌اند از: داده زمان بحران به‌صورت آنی به کاربر می‌رسد، انتقال پیام نسبت به حس کردن محیط انرژی بیشتری مصرف می‌کند، بنابراین اگرچه نودها پیوسته در حال حس کردن هستند اما مصرف انرژی آنها به‌صورت پتانسیلی کمتر از شبکه Proactive خواهد بود، مقدار آستانه نرم می‌تواند تغییر کند، بسته به بحرانی بودن حوادث حس شده، یک مقدار کوچک‌تر از آستانه‌ی نرم می‌تواند یک تصویر دقیق از شبکه را در اختیار ما قرار دهد. در مقابل مصرف انرژی افزایش‌یافته که کاربر می‌تواند بین انرژی مصرفی و دقت موازنه برقرار کند و در نهایت در زمان تغییر خوشه‌ها، ویژگی‌ها از نو پخش خواهند شد که کاربر می‌تواند آنها در صورت نیاز عوض کند]۳۷، ۴۱٫[

پروتکل APTEEN[55]

یک نسخه‌ی بهبودیافته ازTEEN است که در آن شبکه علاوه برگزارش اتفاقات مهم، قادر است تا به‌صورت پریودیک اطلاعات حسگرها را بگیرد. در این پروتکل بعد از شکل گرفتن کلاس‌ها سرگروه‌ها پارامترهای مورد نظر، مقادیر آستانه‌ها و زمان‌بندی ارسال حسگرها را به آنها می‌فرستند. برای صرفه‌جویی در انرژی سرگروه‌ها داده‌های حسگرهای هر کلاس را ترکیب می‌کنند و بعد می‌فرستند. APTEENسه نوع درخواست متفاوت به شبکه می‌فرستد: اول تاریخچه‌ای که برای آنالیز داده‌های گذشته است، دوم لحظه‌ای که به‌صورت لحظه‌ای اطلاعات شبکه را جمع‌آوری می‌کند و سوم دائمی است که برای نظارت بر اتفاقات برای یک پریود زمانی می‌باشد. APTEENاز نظر کارایی در مصرف انرژی و طول عمر شبکه بدتر از TEEN است و TEEN با کاهش اطلاعات ارسالی، کارایی بهتری را نشان می‌دهد]۴۲ .[مشکل عمده‌ی هر دو پروتکل در شکل‌دهی کلاس‌ها است. در واقع تشکیل کلاس‌ها درTEEN، کمی پیچیده و مشکل است.

پروتکل [۵۶]PEGASIS :

اهداف اصلی این پروتکل دوچندان است. اولین هدف آن بالا بردن طول عمر شبکه با دستیابی به یک سطح از انرژی کافی و یکنواخت در طول شبکه است. دومین هدف کوشش در جهت کاهش تأخیر بسته‌ها در سر راهشان به گره سینک می‌باشد. در این پروتکل گره‌ها اطلاعاتشان در مورد سایر گره‌ها، به دانستن وضعیت حس‌گرها در کل شبکه می‌رسد. به‌علاوه آنها توانایی پوشش یک مجموعه‌ی دلخواه را دارند. گره‌ها ممکن است که از فرستنده-گیرنده‌های رادیویی دارای CDMA استفاده کنند. وظیفه گره‌ها جمع‌آوری و ارسال داده به گره چاهک است. هدف توسعه یک ساختار مسیریابی و یک طرح تجمیع برای کاهش انرژی مصرفی و برقراری تعادل در انرژی مصرفی در طول گره‌های حس‌گر می‌باشد. بر خلاف سایر پروتکل‌ها که ساختار درختی یا سلسله‌مراتبی مبتنی بر کلاس را دارا هستند، این پروتکل از ساختار زنجیره‌ای استفاده می‌کند]۴۳٫[
ساختار زنجیره‌ای با دورترین گره نسبت به گره چاهک شروع می‌شود. گره‌های شبکه به ترتیب همسایه به همسایه به طرح زنجیره اضافه می‌شوند. برای تعیین نزدیک‌ترین همسایه، هر گره از یک سیگنال برای اندازه‌گیری فاصله از همسایه‌هایش بهره می‌برد. گره‌ها قدرت این سیگنال را طوری تنظیم می‌کنند که فقط نزدیکترین گره یا گره همسایه می‌تواند آن را شنود کند. یک گره در طول زنجیره به عنوان سر زنجیره انتخاب می‌شود. وظیفه‌ی زنجیره انتقال تجمیع اطلاعاتی به گره چاهک می‌باشد. موقعیت سر زنجیره هر بار یک واحد شیفت می‌یابد، که باعث برقراری تعادل در مصرف انرژی گره‌های شبکه می‌شود]۴۳٫[
تجمیع اطلاعات در طرح PEGASIS در طول زنجیره حاصل می‌شود. در ساده‌ترین شکل، فرآیند تجمیع می‌تواند به ترتیب زیر باشد: اول عنصر سر زنجیره یک بسته را به سمت آخرین گره در منتهی‌الیه سمت راست زنجیره روانه می‌کند. هر گره با دریافت بسته داده‌هایش را به سمت سر زنجیره روانه می‌کند. این کار در دو سمت راست و چپ زنجیره به کار برده می‌شود و سپس اطلاعات جمع شده از هر دو طرف زنجیره به گره چاهک ارسال می‌شود. یک روش برای کاهش تأخیر بالقوّه ارسال داده‌های تجمیعی به گره چاهک استفاده از تجمیع موازی در طول زنجیره میباشد. بالاترین درجه‌ی توازی در صورتی برقرار است که گره‌های حس‌گر مجهز به فرستنده-گیرنده‌های دارای CDMA باشند]۴۳٫[
شکل ۲-۸ رویه تجمیع و جمعآوری دادهها را بر مبنای زنجیره در الگوریتم PEGASIS نشان میدهد.
شکل ‏۲‑۸: رویه تجمع و جمع‌آوری داده‌ها بر مبنای زنجیره [۴۳]

پروتکل[۵۷]VGA