یک الگو مسیریابی انرژی آگاه میباشد که در ]۴۴ [ارائه شده است. هدف این پروتکل آن است که با استفاده از تجمیع اطلاعات و پردازش درون‌شبکه‌ای، طول عمر شبکه را افزایش دهد. با توجه به تحرک کم گره‌ها در برخی از کاربردهای شبکه‌های حسگر بیسیم همان‌طور که در ]۴۴ [اشاره‌شده، استفاده از یک توپولوژی ثابت در شبکه می‌تواند مفید باشد. با توجه به این مورد VGA یک توپولوژی مجازی ثابت با استفاده از یکسری خوشه مربعی شکل ایجاد می‌نماید که در هر خوشه یک گره بهینه به عنوان سرگروه انتخاب می‌شود. همچنین تجمیع داده‌ها در دو سطح محلی و سراسری انجام می‌گیرد. گره‌های سرگروه که با عنوان تجمیع کننده محلی نیز شناخته می‌شوند، اولین سطح تجمیع که به صورت محلی میباشد را اجرا می‌کنند. دومین سطح تجمیع که به صورت سراسری میباشد، در زیرمجموعه‌ای از مکان‌های محلی انجام می‌گیرد. شکل (۲-۹) ساختار الگوریتم VGA را نشان میدهد. توجه به این نکته شود که مکان گره چاهک در ساختار VGA از قبل مشخص نیست و می‌تواند به صورت اختیاری در هر جایی از شبکه قرار گیرد.
شکل ۲‑۹: ساختار الگوریتم VGA ]44[
پروتکل‌های مسیریابی مبتنی بر مکان[۵۸]
در این نوع مسیریابی گره‌های حسگر با استفاده از مکان قرارگیری‌شان، آدرس‌دهی می‌شوند. همچنین فاصله مابین گره‌های همسایه به وسیله قدرت سیگنال دریافتی تخمین زده می‌شود. گره‌های همسایه با تبادل اطلاعات می‌توانند از مختصات نسبی یکدیگر آگاه شوند. متناوباً مکان هر یک از گره‌ها را می‌توان با برقراری ارتباط مستقیم با ماهواره و یا با استفاده از [۵۹]GPS به دست آورد. صرفه‌جویی در انرژی برخی از الگوهای مسیریابی مبتنی بر مکان، حالت گره‌های حسگری که هیچ فعالیتی ندارند را به حالت خواب تغییر می‌‌دهند. زمان‌بندی حالت خواب گره‌ها یکی از مشکلات اصلی این الگوها میباشد که در الگوهای مختلفی مورد بررسی قرار گرفت. در حقیقت هدف اصلی مسیریابی‌های مبتنی بر مکان استفاده از اطلاعات محلی برای پیدا کردن مسیر بهینه به سمت مقصد است. برای دستیابی به این هدف بسته اطلاعاتی به گره‌های در داخل ناحیه هدایت فرستاده می‌شود]۴۵ [. در این الگو، فقط گره‌هایی که داخل ناحیه هدایت هستند اجازه ارسال بسته را دارند. ناحیه هدایت می‌تواند به صورت ایستا توسط گره منبع تعریف شود یا توسط گره‌های میانی جهت حذف گره‌های که باعث انحراف در مسیر بهینه می‌باشند انجام گیرد. کارایی استراتژی فوق وابسته به روشی است که از طریق آن ناحیه هدایت تعریف می‌شود و همچنین ارتباط گره‌های ناحیه فوق نیز وابسته است ]۴۵ [. در ادامه برخی از الگوهای مسیریابی مبتنی بر مکان مورد بررسی قرار خواهد گرفت.
| منبع فایل کامل این پایان نامه این سایت pipaf.ir است |
پروتکل [۶۰]GAF
پروتکل آگاه به انرژی میباشد که عمدتاً جهت MANET[61] پیشنهاد شده است، اما همچنین می‌تواند در شبکه‌های حسگر بیسیم نیز استفاده شود، زیرا از انرژی موجود محافظت می‌کند. طراحی GAF مبنی بر انرژی میباشد که به مصرف انرژی رسیدگی می‌کند که این مصرف ناشی از ارسال و دریافت بسته‌ها و همچنین زمان بیکاری، هنگامی که آنتن رادیویی یک حسگر بسته‌های وارد شده را اکتشاف می‌کند. GAF مبتنی بر مکانیزمی است که حس‌گرهای غیرضروری را خاموش می‌کند، درحالی‌که یک سطح ثابت از مسیریابی را حفظ می‌کند. الگوریتم GAF در ابتدا کل فضای شبکه را به نواحی مربعی شکلی تقسیم‌بندی می‌کند. هر گره در یک مربع می‌تواند با گره دیگر در مربع جانبی ارتباط برقرار کند. همچنین لازم به ذکر است مربع‌هایی که در گوشه‌ها باهم همسایه هستند در نظر گرفته نمی‌شوند]۴۶ .[شکل ۲-۱۰ دیاگرام حالت را برای یک گرهی حسگر در الگوریتم GAF نشان میدهد.
شکل ۲‑۱۰: دیاگرام وضعیت‌ها در GAF [46]
وضعیت‌های دیاگرام GAF که تحول‌پذیر میباشد سه وضعیت است،که نام‌های آن کشف[۶۲] و فعال[۶۳] و خواب[۶۴] میباشد. هنگامی‌که یک حسگر وارد حالت خواب می‌شود آنتن رادیویی خود را خاموش می‌کند تا انرژی را از دست ندهد. در وضعیت کشف یک حسگر شروع به مبادله‌ی پیام‌های کشف جهت یادگیری مکان حس‌گرهای دیگر در همان شبکه می‌کند. در وضعیت فعال هر حسگر در فواصل معین، به صورت دوره‌ای، پیام‌های کشف را جهت اطلاع دادن مساوی به حسگرها درباره‌ی این وضعیت پخش همگانی می‌کند. هنگامی‌که یک حسگر نیروی خود را از دست بدهد در هر وضعیتی که باشد می‌تواند به‌وسیله‌ی برنامه خاموش شود، که این عمل وابسته به چندین عامل میباشد. مانند اینکه یک حسگر نیاز به تحرک داشته باشد. GAF، مکانیزم عمر شبکه به‌وسیله‌ی رسیدن به یک وضعیت که هر شبکه دارای یک حسگر فعال مستقر مبنی بر قانون‌های طبقه‌بندی حسگرها باشد، ارزیابی می‌کند. رتبه‌بندی حسگرها مبنی بر سطح‌های انرژی باقی‌مانده‌شان میباشد، بنابراین یک حسگر با رتبه‌ی بالاتر توانایی بکار بردن مسیریابی با Gridهای متناظرشان را خواهند داشت. برای مثال یک حسگر در وضعیت فعال رتبه بالاتری نسبت به حسگری که در وضعیت کشف میباشد داراست. همچین حسگر با مدت عمر طولانی انتظار می‌رود که رتبه بالایی داشته باشد ]۴۶ .[
پروتکلGEAR [۶۵]
با توجه به اینکه معمولاً درخواست‌ها برای یک قسمت مکانی خاص در شبکه است، در این پروتکل سعی شده است که برای ارسال درخواست‌ها به مکان مورد نظر از اطلاعات مکانی حسگرها استفاده شود. در واقع هر حسگری که درخواستی را دریافت می‌کند، سعی می‌کند آن را به آن حسگر همسایه‌ای بفرستد که به طور ضمنی از خودش به مقصد نزدیکتر باشد. بدین‌صورت به‌جای اینکه مانند DD یک درخواست در کل شبکه پخش شود، فقط به مکان مورد نظر فرستاده می‌شود و در نتیجه با این روش در مصرف انرژی بیشتر صرفه‌جویی می‌شود. در GEAR هر حسگر، هزینه‌ی تخمین زده شده و هزینه‌ی یاد گرفته شده تا مقصد را دارد. هزینه تخمین زده شده ترکیبی از انرژی باقیمانده و فاصله تا مقصد میباشد، درحالی‌که هزینه یاد گرفته شده مقدار تصحیح‌شده‌ی هزینه تخمین زده شده در اطراف حفره‌هاست]۴۷ .[یک حفره در شبکه وقتی اتفاق می‌افتد که یک حسگر هیچ همسایه‌ای که نزدیکتر از خودش به مقصد نداشته باشد و همچنین خودش نیز به مقصد دسترسی نداشته باشد. اگر هیچ حفره‌ای وجود نداشته باشد، هزینه‌ی یاد گرفته شده برابر با هزینه تخمین زده شده است. وقتی یک داده به مقصد می‌رسد، هزینه یاد گرفته شده به صورت پله پله به عقب، مسیری که طی شده، فرستاده می‌شود تا هزینه‌ها تصحیح شود و بدین صورت برای داده‌ها‌ی بعدی اطلاعات مسیر اصلاح شده باشد. این الگوریتم شامل دو بخش میباشد [۱۲، ۴۷]:
ارسال داده‌ها به سمت منطقه مورد نظر
هر حسگر وقتی یک داده را دریافت کرد، به همسایه‌های خود نگاه می‌کند. اگر همسایه‌ای وجود داشت که از خودش به مقصد نزدیکتر بود، داده را به آن می‌فرستد. در مواقعی که چند همسایه نزدیکتر به مقصد وجود دارند، همسایه‌ای انتخاب می‌شود که از همه به مقصد نزدیکتر باشد. اگر هیچ همسایه‌ای نزدیکتر به مقصد نباشد و خود حسگر نیز به طور مستقیم به مقصد دسترسی نداشته باشد، یک حفره در شبکه اتفاق افتاده است. در این هنگام بر مبنای هزینه‌ی یاد گرفته‌شده یکی از همسایه‌ها به عنوان گیرنده‌ی داده‌ها انتخاب می‌شود و داده‌ها به آن فرستاده می‌شود. این انتخاب می‌تواند بر مبنای همگرایی هزینه‌ی یاد گرفته شده هر دفعه به روز شود.
رساندن داده به مقصد در منطقه مورد نظر
وقتی که داده به منطقه مورد نظر رسید، برای رساندن آن به مقصد از روش ارسال مکانی بازگشتی و یا از روش سیل‌آسا[۶۶] محدود استفاده می‌شود. روش سیل‌آسا محدود وقتی‌که حسگرها به صورت فشرده جایگذاری نشده‌اند، مناسب میباشد و در شبکه‌های فشرده روش ارسال مکانی بازگشتی کارایی بهتری از روش سیل‌آسا محدود از نقطه نظر مصرف انرژی دارد. در این حالت، منطقه‌ی مورد نظر به چهار زیر بخش تقسیم می‌شود و چهار نسخه از داده به آنها ارسال می‌شود. این تقسیمات تا آنجا ادامه پیدا می‌کند که مناطقی شامل تنها یک حسگر باقی بماند و داده به مقصد برسد.
خوشهبندی به وسیله الگوریتم‌های هوشمند
ایجاد خوشه‌های بهینه در شبکه همیشه یکی از مسائل اصلی خوشهبندی در شبکه‌های حسگر بیسیم است [۴۸]. شکل ۲-۱۱ یک خوشه خوشهبندی را در شبکه به صورت ساده نشان میدهد.
شکل ۲‑۱۱: خوشهبندی [۴۸]
خوشهبندی بهینه دارای مؤلفه‌های مثل تعداد خوشه‌ها، مکان سرخوشه‌ها، اندازه خوشه‌ها و چگالی[۶۷] خوشه‌ها است.
اگر تعداد خوشه‌ها کمتر از حد نیاز باشد به سرخوشه‌ها بار بیشتری تحمیل می‌شود و باید در هر خوشه تعداد بیشتری گرهی حسگر را مدیریت کنند. بار ترافیکی ارتباطات درون خوشه افزایش می‌یابد.
انرژی سرخوشه سریع‌تر کاهش می‌یابد. عمر گره‌هایی که به عنوان سرخوشه انتخاب می‌شوند سریع‌تر تمام می‌شود.
اگر تعداد خوشه‌ها زیاد باشد بار ترافیکی ارتباطات بین سرخوشه‌ها و سینک افزایش می‌یابد و عمر گره‌های سرخوشه که در مسیر رسیدن اطلاعات به سینک قرار دارند زودتر تمام می‌شود.
زیاد بودن یا کم بودن تعداد خوشه‌ها در خوشهبندی باعث کاهش عمر مفید شبکه می‌شود.
مکان سرخوشه‌ها باید طوری انتخاب شوند که خوشه‌ها در فاصله مناسب از هم تشکیل شوند. به‌طوری که اندازه‌ی تمام خوشه‌ها با توجه به چگالی گره‌ها در شبکه، مناسب باشد.
مکان‌یابی مناسب سرخوشه‌ها جزء مسائل پیچیده و مشکل[۶۸] در شبکه‌های حسگر بیسیم است.
اندازه‌ی خوشه‌ها باید متناسب با تعداد کل گره‌های شبکه، چگالی گره‌های حسگر در شبکه و فاصله خوشه‌ها تا چاهک باشد.
بهتر آن است خوشه‌هایی که به سینک نزدیکتر هستند اندازه کوچک‌تری داشته باشند. زیرا سرخوشه‌های خوشه‌های نزدیک به سینک وظیفه انتقال پیام‌های تجمیع شده‌ی دیگر سرخوشه‌های دور از سینک را نیز به عهده دارند. به دلیل آنکه بار کاری این سرخوشه‌ها زیاد نشود؛ اندازه خوشه‌های آنها کوچکتر انتخاب می‌شود. البته این کار در بسیاری از الگوریتم‌های ارائه‌شده انجام نمی‌شود.
استفاده از الگوریتم‌های هوشمند ریاضی برای ایجاد خوشه‌های بهینه امروزه بسیار پرکاربرد است.
از این نمونه می‌توان به الگوریتم‌هایی مثل کلونی مورچگان، شبکه‌های عصبی و کوچ پرندگان اشاره کرد.
در این پایان‌نامه الگوریتم کوچ پرندگان را برای انتخاب بهینه سرخوشه‌ها انتخاب شده است.
الگوریتم کوچ پرندگان PSO[69]
الگوریتم کوچ پرندگان از حرکت گروهی پرندگان مهاجر الهام گرفته شده است. این الگوریتم در سال ۱۹۹۵ توسط کندی[۷۰] و ابرهارت[۷۱] ابداع شده است.
در این الگوریتم هر جواب با یک پرنده نمایش داده می‌شود. هر پرنده یک موقعیت، یک سرعت و یک تابع شایستگی دارد. جواب‌های مورد نظر به نام ذره[۷۲] میباشد.
هر پرنده یک موقعیت دارد و یک بهینگی که بر اساس آن موقعیت جدید را بهدست می‌آورد. یک بردار سرعت دارد که جهت حرکت پرنده را تعیین می‌کند.
بهینگی هر پرنده با استفاده از تابع بهینگی مسئله که برای رسیدن به موقعیت‌های بهینه تعریف شده است بهدست می‌آید. هر مسئله تابع بهینگی منحصربه‌فرد خود را دارد.
برای استفاده پارامترهای زیر را نیز تعریف می‌کنیم.
Pbest بهترین نتیجه‌ای که یک پرنده خودش بهدست می‌آورد.
Nbest بهترین نتیجه‌ای که پرندگان واقع در همسایگی تاکنون بهدست آورده‌اند.
Gbest بهترین نتیجه‌ای که در کل پرندگان تا به حال پیداشده است.
هر پرنده جهت حرکت خود را بر دو اساس انتخاب می‌کند.
تجربه خودش[۷۳]