هدف از ارائه این پروتکل افزایش طول عمر گره‌های حسگر است. این پروتکل مشابه با پروتکل DD است با این تفاوت که برای دستیابی به نرخ ارسال بالاتر از چندین مسیر بهینه استفاده می‌کند. مسیرهای انتخابی با استفاده از یک تابع احتمال خاص انتخاب می‌شوند. تابع احتمال نام برده شده به میزان مصرف انرژی هر یک از مسیرها بستگی دارد. ایده به کار برده شده در این پروتکل آن است که با انتخاب چندین مسیر بهینه، انرژی یک مسیر به سرعت کاهش نمی‌یابد که این امر سبب ایجاد یک تعادل مصرف انرژی در کل شبکه میشود ]۲۲[. به‌عبارت‌دیگر میتوان گفت بقای شبکه یکی از مهم‌ترین پارامترهای در نظر گرفته شده برای این پروتکل است. فرض به کار برده شده در این پروتکل آن است که هر گره حسگر به وسیله کلاسی از آدرس‌ها که شامل مکان و نوع گره‌ها می‌باشند، آدرس‌پذیر است. در زمان ارسال اطلاعات در ابتدا کلیه مسیرهای موجود مابین گره منبع و گره چاهک شناسایی میشود و جداول مسیریابی برای آنها ایجاد میشود. سپس مسیرهایی که دارای هزینه بیشتری می‌باشند حذف می‌گردد. سپس با استفاده از جداول مسیریابی و احتمال تخصیص داده‌شده به هر یک از مسیرها، اطلاعات به سمت گره چاهک ارسال می‌شوند. در مقایسه با پروتکل DD ، این پروتکل سبب کاهش ۲۱٫۵% مصرف انرژی و افزایش ۴۴% طول عمر شبکه می‌گردد. بااین‌وجود دستیابی به اطلاعات مربوط به مکان هر یک از گره‌ها نیازمند معادلات پیچیده‌‌ای است که سبب شده این پروتکل در مقایسه با پروتکل DD دارای فاز ابتدایی پیچیده‌تری باشد]۱۲، ۲۲[.
در شکل ۲-۴ تفاوت نوع تولید داده برای هدایت به سمت چاهک در نوع رویداد محور و به صورت مبدأ تولید ترافیک داده به صورت تصادفی نشان داده شده است. که در نوع اول میتوان از روشهای تراکم داده استفاده کرد و در نوع دوم مسیرهای مختلف برای رسیدن به چاهک در شبکه ایجاد میشود.
ایده مسیریابی‌های سلسله مراتبی[۳۸] و مبتنی بر کلاس در ابتدا در شبکه‌های سیمی مطرح شد، که سبب بهبود برقراری ارتباط و پایداری شبکه شد. استفاده از این‌گونه مسیریابی‌ها در شبکه‌های حسگر سبب بهبود مصرف انرژی شده است.
شکل ۲‑۴: عملکرد تجمیع اطلاعات در پروتکل انتشار هدایت‌شده ]۱۲[
در این‌گونه ساختارها گره‌هایی که دارای انرژی بیشتری می‌باشند، به عنوان گره‌ی پردازش کننده اطلاعات و انتقال‌دهنده اطلاعات به گره چاهک انتخاب می‌شوند. مسیریابی سلسله مراتبی با استفاده از مفاهیمی مانند کلاس و تجمیع داده‌ها سبب بهبود مصرف انرژی و افزایش طول عمر شبکه شده است. این نوع مسیریابی بر اساس دو فاز طراحی شده است، فاز اول جهت شناسایی سرخوشه‌ها[۳۹] و فاز دوم جهت مسیریابی مورد استفاده قرار می‌گیرد ]۱۵[.
در مقایسه با پروتکل‌های دیگر مسیریابی این دسته از پروتکل‌ها دارای ویژگی‌های متمایزکننده‌ای می‌باشند که در زیر به برخی از آنها اشاره نموده‌ایم]۲۳، ۲۴[:
مصرف بهینه‌تر انرژی، با توجه به آنکه انرژی گره‌های موجود در شبکه محدود می‌باشد، مصرف بهینه‌تر انرژی یکی از مهم‌ترین مزایای این دسته پروتکل‌ها می‌باشد.
جمع‌آوری داده‌های ارسالی توسط سرگروه‌های هر کلاس و انجام اعمالی مانند تجمیع که سبب کاهش حجم داده‌های ارسالی خواهد شد.
مقیاس‌پذیری، با توجه به حالت پویای توپولوژی شبکه، این دسته از پروتکل‌های مسیریابی از مراحل توزیع‌شده‌ای استفاده می‌کنند که سبب گسترش ساده‌تر شبکه خواهد شد.
پایداری، این دسته از پروتکل‌ها قابلیت سازمان‌دهی مجدد شبکه در صورت از بین رفتن برخی از گره‌های موجود در شبکه فراهم می‌سازند.
به دلیل تراکم بالای گره‌های حسگر در واحد سطح و در نتیجه نزدیکی آنها با یکدیگر، ارتباط‌های چندگامی در این گونه شبکه‌ها مفیدتر و مقرون به صرفه‌تر از ارتباط‌های تک گامی است. اما با توجه به انرژی محدود هر یک از حسگرها و اینکه بیشتر انرژی آنها صرف ایجاد ارتباط با حسگرهای دیگر میشود، استفاده از ارتباط‌های چندگامی نیز باعث مصرف زیاد انرژی در حسگرها و در نتیجه کاهش عمر شبکه‌ی حسگر می‌گردد ]۲۵[. به‌کارگیری خوشه‌ها برای ارسال اطلاعات به یک ایستگاه پایه با ملزوم کردن تنها تعداد کمی گره برای ارسال از فواصل دور به ایستگاه اصلی مزایای فواصل ارسال کوتاه را برای اکثر گره‌ها افزایش می‌دهد ]۲۵، ۲۶[. به پیداکردن و ایجاد مسیر بین مبدأ و مقصد مسیریابی می‌گویند.
در دنیا روشهای مختلفی برای پیداکردن مسیر بهینه مطرح شده است که هر کدام از آنها در شرایطی کارا هستند. مسیریابی در شبکه‌ها یکی از مهم‌ترین مسائل مطرح شده است.در شبکه‌های حسگر بی‌سیم با توجه به ساختار متفاوتی که با شبکه‌های معمول دارند این موضوع ویژگی‌های خاص خودش را پیدا می‌کند.
در طراحی‌های اولیه شبکه‌های حسگر بی‌سیم از مسیریابی‌هایی استفاده شد که در شبکه‌های سنتی بی‌سیم استفاده می‌شد. الگوریتم‌های مسیریابی انجام‌شده در شبکه‌های سنتی در شبکه‌های حسگر بی‌سیم کارایی خوبی ندارند.
در شبکه‌های حسگر بی‌سیم به دلیل اینکه گره‌های تشکیل‌دهنده شبکه، حسگرهای کوچک بی‌سیم هستند. ویژگی‌های خاصی را به شبکه تحمیل می‌کنند.
طیف وسیعی از کاربردهای شبکه‌های حسگر مربوط به محیط‌هایی میشود که انسان نمی‌تواند در آن حضور داشته باشد. مانند محیط‌های آلوده از نظر شیمیایی، میکروبی، هسته‌ای و یا مطالعات در اعماق اقیانوس‌ها و یا محیط‌های نظامی و یا در جنگل و زیستگاه جانوران که حضور انسان باعث فرار آنها میشود. در هر مورد، شرایط محیطی باید در طراحی گره‌ها در نظر گرفته شود [۱، ۳، ۱۵].
هر گره‌ی حسگر ضمن اینکه باید کل اجزاء لازم را داشته باشد، باید به حد کافی کوچک، سبک و کم‌حجم نیز باشد. درعین‌حال هر گره باید انرژی مصرفی بسیار کم و قیمت تمام‌شده پایین داشته و با شرایط محیطی سازگار باشد. اینها همه محدودیت‌هایی است که کار طراحی و ساخت گره‌های حسگر را با چالش مواجه می‌کند [۳].
هر گره ممکن است خراب شود یا در اثر رویدادهای محیطی مثل تصادف یا انفجار به‌کلی نابود شود یا در اثر تمام شدن منبع انرژی از کار بیفتد.شبکه ایجادشده توسط گره‌های حسگر باید تحمل‌پذیری خطای بالایی داشته باشد. منظور از تحمل‌پذیری خطا یا قابلیت اطمینان[۴۰] این است که خرابی گره‌ها نباید عملکرد کلی شبکه را تحت تأثیر قرار دهد.
هر حسگر در شبکه‌های حسگر بی‌سیم دارای بخش‌های مختلفی است؛ ۱- واحد حسگر ۲- واحد پردازنده ۳- واحد ارتباطات ۴- واحد انرژی .
واحد حسگر وظیفه حس[۴۱] و برداشتن اطلاعات را به فراخور کاربرد و وظیفه حسگر؛ که شبکه حسگر بی‌سیم به خاطر آن به وجود آمده را از محیط دارد.
واحد پردازنده وظیفه پردازش اولیه و ساده اطلاعات به دست آمده و آماده‌سازی برای ارسال آن به سینک را به عهده دارد.
واحد ارتباطات وظیفه ارسال و دریافت بسته‌های پیام را بر عهده دارد. ارسال و دریافت پیام بیشترین میزان از انرژی را در واحدهای مختلف مصرف می‌کند.
واحد انرژی که معمولاً از یک باتری کوچک تشکیل شده است وظیفه تأمین انرژی فعالیتهای مختلف حسگر را به عهده دارد [۴].
طول عمر گره‌ها به علت محدودیت انرژی منبع تغذیه کوتاه است. علاوه بر آن در برخی مواقع، موقعیت ویژه یک گره در شبکه مشکل را تشدید می‌کند. مثلاً گره‌ای که در فاصله یک قدمی گره چاهک قرار دارد ازیک‌طرف به خاطر بار کاری زیاد خیلی زود انرژی خود را از دست می‌دهد و از طرفی از کار افتادن آن باعث قطع ارتباط گره مرکزی با کل شبکه و در نتیجه موجب ازکارافتادن شبکه میشود. مشکل تخلیه زود هنگام انرژی در مورد گره‌های نواحی کم تراکم در توزیع غیریکنواخت گره‌ها نیز صدق می‌کند در این‌گونه موارد داشتن یک مدیریت انرژی در داخل گره‌ها و ارائه راه‌حل‌های انرژی آگاه به‌طوری‌که از گره‌های بحرانی کمترین استفاده را بکند مناسب خواهد بود. با توجه به مطالب بیان‌شده تمام الگوریتم‌ها و فن‌های مورد استفاده در شبکه‌های حسگر به انرژی به‌عنوان یک محدودیت جدی نگاه می‌کنند و سعی می‌کنند با آگاهی از سطح انرژی مصرفی عمل کنند تا کمترین انرژی مصرف گردد و در نتیجه افزایش طول عمر شبکه حسگر را به دنبال داشته باشد [۲۷].
به همین دلیل راه‌کارهای مختلفی برای صرفه‌جویی در مصرف انرژی در حسگر پیشنهادشده است. بیشتر آنها مربوط به ارتباطات حسگر است. استفاده حداکثری از حسگر مسئله اول در شبکه‌های حسگر بی‌سیم است. توجه به مسئله انرژی و کم شدن مصرف بدون اینکه به ساختار شبکه خللی وارد شود، در مسیریابی حائز اهمیت است. به همین دلیل برای مسیریابی در شبکه‌های حسگر بی‌سیم الگوریتم‌های خاصی ارائه شد. در آنها به مسئله انرژی و کم شدن ارتباطات غیرضروری و فشرده‌سازی اطلاعات توجه خاصی شده است.
الگوریتم‌های مسیریابی در شبکه‌های حسگر بی‌سیم سعی می‌کنند تا جای ممکن از پدیده‌ی خرابی شبکه[۴۲] جلوگیری کند.
در خرابی شبکه به خاطر تمام شدن انرژی بعضی از حسگرها، به خاطر فعالیت بیشتر و در نتیجه مرگ حسگرها؛ توپولوژی شبکه از بین می‌رود. بااینکه تعدادی از حسگرها دارای انرژی هستند به خاطر مردن[۴۳] حسگرهای میانی که وظیفه برقراری ارتباط بین حسگرها و سینک را دارند؛ توانایی برقراری ارتباط را از دست می‌دهند. مقداری از انرژی در شبکه به دلیل خرابی شبکه هدر می‌رود [۲۷].
یکی از روشهای بسیار پرکاربرد فشرده‌سازی پیغام‌ها است تا انرژی کمتری صرف ارسال پیام‌ها شود. الگوریتم‌های مسیریابی سعی می‌کنند وظیفه ارتباطات بین حسگرهای مبدأ و سینک را به صورتی بین حسگرهای میانجی تقسیم کنند که از پدیده شکستگی شبکه تا جای ممکن جلوگیری شود.
برای حل این مشکل روشهای مختلفی پیشنهاد شده است. یکی از روشهای پرکاربرد خوشه‌بندی شبکه است.
| برای دانلود متن کامل این پایان نامه به سایت pipaf.ir مراجعه نمایید. |
خوشه‌بندی در شبکه‌های حسگر بی‌سیم
خوشه‌بندی شبکه را به خوشه‌های کوچک‌تر تقسیم می‌کند. تا از حجم ارتباطات درون شبکه بکاهد. فن‌های خوشه‌بندی، قابلیت مقیاس‌پذیری و گسترش به صدها و هزاران گره را نیز دارا هستند. یعنی با استفاده از این فن‌ها میتوان با افزایش اندازه شبکه، توازن بار در شبکه را رعایت نموده و منابع را به صورت کارا استفاده نمود. کاربردهایی که به تجمیع داده‌ها به صورت مؤثر احتیاج دارند نیز کاندیدای مناسب جهت استفاده از خوشه‌بندی می‌باشند. خوشه‌بندی باعث میشود حجم ارتباطات درون شبکه کاهش یابد و در نتیجه عمر شبکه افزایش یابد. پروتکل‌های مسیریابی نیز می‌توانند فن‌های خوشه‌بندی را به کار برند ]۱۵، ۲۸[.
هر خوشه دارای حداقل یک سرخوشه است. گره‌های حسگر پیام‌های خود را به سرخوشه می‌فرستند. سرخوشه وظیفه دریافت، تجمیع، فشرده‌سازی و ارسال پیام‌ها را به سینک دارد. این ارسال می‌تواند مستقیم یا غیرمستقیم از طریق دیگر سرخوشه‌ها به سینک انجام بگیرد.
ازآنجاکه در خوشه‌بندی جمع‌آوری و ارسال اطلاعات به ایستگاه پایه بر عهده سرخوشه‌ها است، بار کاری سرخوشه‌ها در مقایسه با دیگر گره‌ها افزایش می‌یابد و در نتیجه مصرف انرژی در سرخوشه‌ها پیش از سایر گره‌های خوشه می‌باشد. به منظور یکنواخت کردن مصرف انرژی در گره‌ها لازم است که سرخوشه‌ها و شکل خوشه‌ها در طول زمان حیات شبکه حسگر تغییر کند. طراحی شمای خوشه‌بندی با دو مسئله اساسی روبرو است ]۱۵، ۲۸، ۲۹ [: ۱) چه تعداد خوشه باید ایجاد گردد. ۲) خوشه‌ها چطور باید ایجاد شوند.
اگر اندازه خوشه‌های ایجادشده متناسب نباشد باعث میشود به سرخوشه‌هایی که در خوشه‌های بزرگ‌تر قرار گرفته‌اند بار بیشتری تحمیل شود.
ایجاد خوشه‌های متوازن و بهینه در شبکه یکی از مسائل مهم و اساسی است. این کار باید به صورتی انجام شود که بار محاسباتی سنگینی نیز به شبکه تحمیل نشود.
برای پاسخ به سؤال اول، تلاش‌هایی جهت مشخص کردن تعداد بهینه سرگروه‌ها در سناریوهای مختلف صورت گرفته است. در ]۳۰[ یک الگوریتم توزیع‌شده در شبکه‌های حسگر بی‌سیم پیشنهاد گردیده است، که در آن هر حسگر با یک احتمال خودش را به عنوان سرگروه انتخاب می‌کند و تصمیمش را به اطلاع دیگران می‌رساند. این الگوریتم امکان ایجاد خوشه‌های تک گامی را فراهم می‌آورد که ممکن است باعث شود تعداد خوشه‌ها خیلی زیاد شود و در مورد چگونگی محاسبه تعداد بهینه سرگروه‌ها صحبتی نمی‌گردد. در ]۳۱[ یک مدل ریاضیاتی برای محاسبه تعداد بهینه سرگروه‌ها در شبکه حسگر بی‌سیم چندگامی ایجاد شده است. نتایج آنها نشان می‌دهد که برای خوشه‌بندی سلسله مراتبی نیروی لازم برای هر سطح از خوشه متفاوت است. آنها همچنین نشان دادند که انرژی سرگروه‌ها سریع‌تر از دیگر گره‌ها تمام میشود. آنها همچنین پیشنهاد دادند که برای ایجاد توازن بار الگوریتم به صورت متناوبی اجرا گردد. در کارهای ]۲۶، ۳۲[ نیز بر روی این موضوع تمرکز شده است.
سؤال دوم دو جنبه دارد، چطور یک سرگروه انتخاب گردد و چطور یک گره معمولی به یک سرگروه مربوط گردد. بسته به اهداف و کاربردهای طراحی، شماهای خوشه‌بندی موجود به دو دسته مختلف می‌توانند تقسیم‌بندی گردند. یک روش خوشه‌بندی ممکن است به شیوه متمرکز و توزیع‌شده کار کند. خوشه‌بندی می‌تواند در شبکه‌های همگن به کار رود و یا در شبکه‌های ناهمگن مورد استفاده قرار گیرد. روال انتخاب یک سرخوشه ممکن است که در یک مرحله کامل گردد و یا به صورت تکراری انجام شود. ساختار سلسله‌مراتبی خوشه می‌تواند یک لایه و یا چند لایه باشد، مانند شکل ۲-۵٫ مد انتخابات در خوشه می‌تواند تک‌گامی، چندگامی و یا ترکیبی از هر دو باشد]۱۵، ۲۸، ۲۹ [
شکل ۲‑۵: ساختار شبکه‌های سلسله مراتبی ]۲۳[
پارامترهای مهم در خوشه‌بندی
خوشه‌بندی سلسله مراتبی در شبکه‌های حسگر بی‌سیم می‌تواند به طور قابل توجهی در مقیاس‌پذیری سرتاسری سامانه، طول عمر و کارایی انرژی تأثیرگذار باشد. مسیریابی سلسله مراتبی یک روش کارا جهت مصرف کمتر انرژی درون یک خوشه و تجمیع و ترکیب داده‌ها در جهت کاهش تعداد پیام‌های ارسالی به سینک می‌باشد.برخی مراجع، خوشه‌بندی را به عنوان یک ابزار مؤثر جهت مکان‌یابی کارآمد اشیا کوچک پیشنهاد می‌کنند. خوشه‌بندی، علاوه بر پشتیبانی از مقیاس‌پذیری شبکه و کاهش مصرف انرژی، مزایای بی‌شمار دیگری نیز دارد [۲۹]. به عنوان مثال میتوان به مواردی مانند کاهش اندازه جدول مسیریابی ذخیره‌شده در هر گره و پایداری توپولوژی شبکه در سطح حسگرها اشاره نمود.
پارامترهای مهمی در طراحی خوشه‌ها در شبکه‌های حسگر بی‌سیم درگیر هستند. این پارامترها به‌عنوان ابزار اساسی جهت مقایسه و دسته‌بندی پروتکل‌های کلاس‌بندی مورد استفاده قرار می‌گیرند. در ادامه به برخی از این پارامترها اشاره می‌نماییم:
تعداد خوشه‌ها: در اکثر الگوریتم‌های خوشه‌بندی، انتخاب سرخوشه و فرایند شکل‌دهی خوشه، به طور طبیعی منجر به ایجاد تعداد خوشه‌های متفاوتی خواهد شد. بااین‌وجود برخی از رویکردهای منتشرشده، مجموعه‌ی سرخوشه‌ها از قبل تعریف و تعیین‌شده هستند. بنابراین تعداد خوشه‌ها از قبل مشخص شده هستند [۲۸]. معمولاً در موضوعات مربوط به کارایی پروتکل مسیریابی، تعداد خوشه‌ها یک پارامتر مهم و بحرانی محسوب میشود.
ارتباط درون خوشه‌ها: در برخی از رویکردهای اولیه ایجاد خوشه‌ها، ارتباط میان یک حسگر و سرخوشه آن به طور مستقیم در نظر گرفته شده است، درحالی‌که امروزه در اغلب موارد، ارتباط درون خوشه‌ها به صورت چند گامی است.
