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

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

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

پروتکل APTEEN[55]

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

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

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

پروتکل[۵۷]VGA

یک الگو مسیریابی انرژی آگاه می‌باشد که در ]۴۴ [ارائه شده است. هدف این پروتکل آن است که با استفاده از تجمیع اطلاعات و پردازش درون‌شبکه‌ای، طول عمر شبکه را افزایش دهد. با توجه به تحرک کم گره‌ها در برخی از کاربردهای شبکه‌های حسگر بی‌سیم همان‌طور که در ]۴۴ [اشاره‌شده، استفاده از یک توپولوژی ثابت در شبکه می‌تواند مفید باشد. با توجه به این مورد VGA یک توپولوژی مجازی ثابت با استفاده از یکسری خوشه مربعی شکل ایجاد می‌نماید که در هر خوشه یک گره بهینه به عنوان سرگروه انتخاب می‌شود. همچنین تجمیع داده‌ها در دو سطح محلی و سراسری انجام می‌گیرد. گره‌های سرگروه که با عنوان تجمیع کننده محلی نیز شناخته می‌شوند، اولین سطح تجمیع که به صورت محلی می‌باشد را اجرا می‌کنند. دومین سطح تجمیع که به صورت سراسری می‌باشد، در زیرمجموعه‌ای از مکان‌های محلی انجام می‌گیرد. شکل (۲-۹) ساختار الگوریتم VGA را نشان می‌‌دهد. توجه به این نکته شود که مکان گره چاهک در ساختار VGA از قبل مشخص نیست و می‌تواند به صورت اختیاری در هر جایی از شبکه قرار گیرد.
شکل ‏۲‑۹: ساختار الگوریتم VGA ]44[

پروتکل‌های مسیریابی مبتنی بر مکان[۵۸]

در این نوع مسیریابی گره‌های حسگر با استفاده از مکان قرارگیری‌شان، آدرس‌دهی می‌شوند. همچنین فاصله مابین گره‌های همسایه به وسیله قدرت سیگنال دریافتی تخمین زده می‌شود. گره‌های همسایه با تبادل اطلاعات می‌توانند از مختصات نسبی یکدیگر آگاه شوند. متناوباً مکان هر یک از گره‌ها را می‌توان با برقراری ارتباط مستقیم با ماهواره و یا با استفاده از [۵۹]GPS به دست آورد. صرفه‌جویی در انرژی برخی از الگوهای مسیریابی مبتنی بر مکان، حالت گره‌های حسگری که هیچ فعالیتی ندارند را به حالت خواب تغییر می‌‌دهند. زمان‌بندی حالت خواب گره‌ها یکی از مشکلات اصلی این الگوها می‌باشد که در الگوهای مختلفی مورد بررسی قرار گرفت. در حقیقت هدف اصلی مسیریابی‌های مبتنی بر مکان استفاده از اطلاعات محلی برای پیدا کردن مسیر بهینه به سمت مقصد است. برای دستیابی به این هدف بسته اطلاعاتی به گره‌های در داخل ناحیه هدایت فرستاده می‌شود]۴۵ [. در این الگو، فقط گره‌هایی که داخل ناحیه هدایت هستند اجازه ارسال بسته را دارند. ناحیه هدایت می‌تواند به صورت ایستا توسط گره منبع تعریف شود یا توسط گره‌های میانی جهت حذف گره‌های که باعث انحراف در مسیر بهینه می‌باشند انجام گیرد. کارایی استراتژی فوق وابسته به روشی است که از طریق آن ناحیه هدایت تعریف می‌شود و همچنین ارتباط گره‌های ناحیه فوق نیز وابسته است ]۴۵ [. در ادامه برخی از الگوهای مسیریابی مبتنی بر مکان مورد بررسی قرار خواهد گرفت.

پروتکل [۶۰]GAF

پروتکل آگاه به انرژی می‌باشد که عمدتاً جهت MANET[61] پیشنهاد شده است، اما همچنین می‌تواند در شبکه‌های حسگر بی‌سیم نیز استفاده شود، زیرا از انرژی موجود محافظت می‌کند. طراحی GAF مبنی بر انرژی می‌باشد که به مصرف انرژی رسیدگی می‌کند که این مصرف ناشی از ارسال و دریافت بسته‌ها و همچنین زمان بیکاری، هنگامی که آنتن رادیویی یک حس‌گر بسته‌های وارد شده را اکتشاف می‌کند. GAF مبتنی بر مکانیزمی است که حس‌گرهای غیرضروری را خاموش می‌کند، درحالی‌که یک سطح ثابت از مسیریابی را حفظ می‌کند. الگوریتم GAF در ابتدا کل فضای شبکه را به نواحی مربعی شکلی تقسیم‌بندی می‌کند. هر گره در یک مربع می‌تواند با گره دیگر در مربع جانبی ارتباط برقرار کند. همچنین لازم به ذکر است مربع‌هایی که در گوشه‌ها باهم همسایه هستند در نظر گرفته نمی‌شوند]۴۶ .[شکل ۲-۱۰ دیاگرام حالت را برای یک گرهی حسگر در الگوریتم GAF نشان میدهد.
شکل ‏۲‑۱۰: دیاگرام وضعیت‌ها در GAF [46]
وضعیت‌های دیاگرام GAF که تحول‌پذیر می‌باشد سه وضعیت است،که نام‌های آن کشف[۶۲] و فعال[۶۳] و خواب[۶۴] می‌باشد. هنگامی‌که یک حس‌گر وارد حالت خواب می‌شود آنتن رادیویی خود را خاموش می‌کند تا انرژی را از دست ندهد. در وضعیت کشف یک حس‌گر شروع به مبادله‌ی پیام‌های کشف جهت یادگیری مکان حس‌گرهای دیگر در همان شبکه می‌کند. در وضعیت فعال هر حس‌گر در فواصل معین، به صورت دوره‌ای، پیام‌های کشف را جهت اطلاع دادن مساوی به حس‌گرها درباره‌ی این وضعیت پخش همگانی می‌کند. هنگامی‌که یک حس‌گر نیروی خود را از دست بدهد در هر وضعیتی که باشد می‌تواند به‌وسیله‌ی برنامه خاموش شود، که این عمل وابسته به چندین عامل می‌باشد. مانند این‌که یک حس‌گر نیاز به تحرک داشته باشد. GAF، مکانیزم عمر شبکه به‌وسیله‌ی رسیدن به یک وضعیت که هر شبکه دارای یک حس‌گر فعال مستقر مبنی بر قانون‌های طبقه‌بندی حس‌گرها باشد، ارزیابی می‌کند. رتبه‌بندی حس‌گرها مبنی بر سطح‌های انرژی باقی‌مانده‌شان میباشد، بنابراین یک حس‌گر با رتبه‌ی بالاتر توانایی بکار بردن مسیریابی با Gridهای متناظرشان را خواهند داشت. برای مثال یک حس‌گر در وضعیت فعال رتبه بالاتری نسبت به حسگری که در وضعیت کشف می‌باشد داراست. همچین حس‌گر با مدت عمر طولانی انتظار می‌رود که رتبه بالایی داشته باشد ]۴۶ .[

پروتکلGEAR [۶۵]

با توجه به اینکه معمولاً درخواست‌ها برای یک قسمت مکانی خاص در شبکه است، در این پروتکل سعی شده است که برای ارسال درخواست‌ها به مکان مورد نظر از اطلاعات مکانی حسگرها استفاده شود. در واقع هر حسگری که درخواستی را دریافت می‌کند، سعی می‌کند آن را به آن حسگر همسایه‌ای بفرستد که به طور ضمنی از خودش به مقصد نزدیک‌تر باشد. بدین‌صورت به‌جای اینکه مانند DD یک درخواست در کل شبکه پخش شود، فقط به مکان مورد نظر فرستاده می‌شود و در نتیجه با این روش در مصرف انرژی بیشتر صرفه‌جویی می‌شود. در GEAR هر حسگر، هزینه‌ی تخمین زده شده و هزینه‌ی یاد گرفته شده تا مقصد را دارد. هزینه تخمین زده شده ترکیبی از انرژی باقیمانده و فاصله تا مقصد می‌باشد، درحالی‌که هزینه یاد گرفته شده مقدار تصحیح‌شده‌ی هزینه تخمین زده شده در اطراف حفره‌هاست]۴۷ .[یک حفره در شبکه وقتی اتفاق می‌افتد که یک حسگر هیچ همسایه‌ای که نزدیکتر از خودش به مقصد نداشته باشد و همچنین خودش نیز به مقصد دسترسی نداشته باشد. اگر هیچ حفره‌ای وجود نداشته باشد، هزینه‌ی یاد گرفته شده برابر با هزینه تخمین زده شده است. وقتی یک داده به مقصد می‌رسد، هزینه یاد گرفته شده به صورت پله پله به عقب، مسیری که طی شده، فرستاده می‌شود تا هزینه‌ها تصحیح شود و بدین صورت برای داده‌ها‌ی بعدی اطلاعات مسیر اصلاح شده باشد. این الگوریتم شامل دو بخش می‌باشد [۱۲، ۴۷]:
ارسال داده‌ها به سمت منطقه مورد نظر
هر حسگر وقتی یک داده را دریافت کرد، به همسایه‌های خود نگاه می‌کند. اگر همسایه‌ای وجود داشت که از خودش به مقصد نزدیک‌تر بود، داده را به آن می‌فرستد. در مواقعی که چند همسایه نزدیک‌تر به مقصد وجود دارند، همسایه‌ای انتخاب می‌شود که از همه به مقصد نزدیک‌تر باشد. اگر هیچ همسایه‌ای نزدیک‌تر به مقصد نباشد و خود حسگر نیز به طور مستقیم به مقصد دسترسی نداشته باشد، یک حفره در شبکه اتفاق افتاده است. در این هنگام بر مبنای هزینه‌ی یاد گرفته‌شده یکی از همسایه‌ها به عنوان گیرنده‌ی داده‌ها انتخاب می‌شود و داده‌ها به آن فرستاده می‌شود. این انتخاب می‌تواند بر مبنای همگرایی هزینه‌ی یاد گرفته شده هر دفعه به روز شود.
رساندن داده به مقصد در منطقه مورد نظر
وقتی که داده به منطقه مورد نظر رسید، برای رساندن آن به مقصد از روش ارسال مکانی بازگشتی و یا از روش سیل‌آسا[۶۶] محدود استفاده می‌شود. روش سیل‌آسا محدود وقتی‌که حسگرها به صورت فشرده جایگذاری نشده‌اند، مناسب می‌باشد و در شبکه‌های فشرده روش ارسال مکانی بازگشتی کارایی بهتری از روش سیل‌آسا محدود از نقطه نظر مصرف انرژی دارد. در این حالت، منطقه‌ی مورد نظر به چهار زیر بخش تقسیم می‌شود و چهار نسخه از داده به آنها ارسال می‌شود. این تقسیمات تا آنجا ادامه پیدا می‌کند که مناطقی شامل تنها یک حسگر باقی بماند و داده به مقصد برسد.

خوشه‌بندی به وسیله الگوریتم‌های هوشمند

ایجاد خوشه‌های بهینه در شبکه همیشه یکی از مسائل اصلی خوشه‌بندی در شبکه‌های حسگر بی‌سیم است [۴۸]. شکل ۲-۱۱ یک خوشه خوشهبندی را در شبکه به صورت ساده نشان میدهد.
شکل ‏۲‑۱۱: خوشه‌بندی [۴۸]
خوشه‌بندی بهینه دارای مؤلفه‌های مثل تعداد خوشه‌ها، مکان سرخوشه‌ها، اندازه خوشه‌ها و چگالی[۶۷] خوشه‌ها است.
اگر تعداد خوشه‌ها کمتر از حد نیاز باشد به سرخوشه‌ها بار بیشتری تحمیل می‌شود و باید در هر خوشه تعداد بیشتری گره‌ی حسگر را مدیریت کنند. بار ترافیکی ارتباطات درون خوشه افزایش می‌یابد.
انرژی سرخوشه سریع‌تر کاهش می‌یابد. عمر گره‌هایی که به عنوان سرخوشه انتخاب می‌شوند سریع‌تر تمام می‌شود.
اگر تعداد خوشه‌ها زیاد باشد بار ترافیکی ارتباطات بین سرخوشه‌ها و سینک افزایش می‌یابد و عمر گره‌های سرخوشه که در مسیر رسیدن اطلاعات به سینک قرار دارند زودتر تمام می‌شود.
زیاد بودن یا کم بودن تعداد خوشه‌ها در خوشه‌بندی باعث کاهش عمر مفید شبکه می‌شود.
مکان سرخوشه‌ها باید طوری انتخاب شوند که خوشه‌ها در فاصله مناسب از هم تشکیل شوند. به‌طوری که اندازه‌ی تمام خوشه‌ها با توجه به چگالی گره‌ها در شبکه، مناسب باشد.
مکان‌یابی مناسب سرخوشه‌ها جزء مسائل پیچیده و مشکل[۶۸] در شبکه‌های حسگر بی‌سیم است.
اندازه‌ی خوشه‌ها باید متناسب با تعداد کل گره‌های شبکه، چگالی گره‌های حسگر در شبکه و فاصله خوشه‌ها تا چاهک باشد.
بهتر آن است خوشه‌هایی که به سینک نزدیک‌تر هستند اندازه کوچک‌تری داشته باشند. زیرا سرخوشه‌های خوشه‌های نزدیک به سینک وظیفه انتقال پیام‌های تجمیع شده‌ی دیگر سرخوشه‌های دور از سینک را نیز به عهده دارند. به دلیل آنکه بار کاری این سرخوشه‌ها زیاد نشود؛ اندازه خوشه‌های آنها کوچکتر انتخاب می‌شود. البته این کار در بسیاری از الگوریتم‌های ارائه‌شده انجام نمی‌شود.
استفاده از الگوریتم‌های هوشمند ریاضی برای ایجاد خوشه‌های بهینه امروزه بسیار پرکاربرد است.
از این نمونه می‌توان به الگوریتم‌هایی مثل کلونی مورچگان، شبکه‌های عصبی و کوچ پرندگان اشاره کرد.
در این پایان‌نامه الگوریتم کوچ پرندگان را برای انتخاب بهینه سرخوشه‌ها انتخاب شده است.

الگوریتم کوچ پرندگان PSO[69]