با تغییر نقش گرهها رفع شده است. به خاطر خاصیت الگوریتم مورچهها یا بستههای مسیریابی به گرههایی که دارای شرایط بهتری هستند، تمایل پیدامیکنند و این تمایل باعث اضافه شدن بار ترافیکی در گره مورد نظر میشود. در نتیجه این امر باعث کوتاه شدن عمر گره میشود. از طرفی وجود سربارهای زیاد موجود در راهاندازی شبکه انرژی گرهها تحلیل میرود. علاوه بر مشکلات ذکر شده الگوریتم از گرههای همگن استفاده میکند، که این امکانپذیر نیست. در واقع گرههای مستقر شده از نظر انرژی باقیمانده، محدود ارسال و پهنایباند با هم متفاوت هستند.
الگوریتم InRout [53] یکی دیگر از روشهای یادگیری ماشین یعنی Q-learning را برای امتیازدهی تدریجی مسیرها استفاده میکند. در این روش بستهها از طریق مسیرهای مختلفی به سمت گره جمعکننده ارسال میگردند و گره جمعکننده به ازای هر بستهای که صحیح دریافت میکند یک فیدبک از مسیر طی شده به سمت گره مبدأ میفرستد. بدین ترتیب گرههای موجود در طول این مسیر امتیاز این مسیر را افزایش میدهند و این مسیر در انتخابهای بعدی احتمال بیشتری را برای انتخاب به خود اختصاص میدهد. این الگوریتم بدین ترتیب تنها مسیرهای دارای قابلیت اطمینان بیشتر را شناسایی میکند و همانطور که قبلاً نیز اشاره شد به دلیل نیاز به فیدبکهای انتها به انتها و متعدد، سربار ترافیکی بالایی به شبکه اعمال میشود که این امر باعث مصرف انرژی در گرههای شبکه شده و طول عمر شبکه را کاهش میدهد. الگوریتم InRout برای تضمین تأخیر مکانیزم بسیار سادهای را پیشنهاد میکند و آن ارسال بستههای حساس به تأخیر روی مسیرهای دارای کمترین گام است. اینکه اگر دو مسیر با تعداد گام مساوی وجود داشته باشد بسته روی کدامیک از آنها باید ارسال شود نیز مورد اشاره قرار نگرفته است.
الگوریتم [۳۳]VBS [59] با استفاده از تکنیک خواب و بیدار و طرح ستون فقرات در شبکههای حسگر بیسیم باعث طولانی شدن طول عمر شبکه شده است. در این الگوریتم تنها گرههایی که به عنوان ستون فقرات انتخاب شدهاند اطلاعات خود را به ایستکاه پایه ارسال میکنند. از آنجایی که بیشترین مصرف انرژی در شبکههای حسگر مربوط به واحد رادیو میباشد، الگوریتم برای کاهش مصرف انرژی از مکانیزم خواب و بیدار برای واحد رادیو گرههایی که اطلاعات خود را ارسال نمیکند در نظر گرفته است. هم چنین برای متعادل سازی مصرف انرژی در کل شبکه و پوشش کل منطقه موجود نمونه برداری گرههای ستون فقرات به صورت دورهای عوض میشوند. این الگوریتم بر روی مصرف انرژی و طولانی کردن عمر شبکه تمرکز کرده است و هیچگونه تضمینی روی متعادلسازی بار در شبکه ارائه نمیکند.
 
 
الگوریتمهای خوشه بندی
الگوریتم SECC[34] [۶۰] یک پروتکل خود سازماندهنده در شبکههای حسگر بیسیم میباشد، در این الگوریتم با استفاده از ضریب نسبت[۳۵] هر گره که از طریق نسبت انرژی گره و میانگین فاصله گره با همسایگانش، چگالی خوشه که از طریق تقسیم تعداد گرههای موجود در خوشه تقستم بر ضریب نسبت گرهها و در نهایت انرژی آگاه خوشهها که با استفاده از مجموع انرژی گرهها و انرژی همسایگانشان بدست میآید، به تشکیل خوشههای متعادل مسیریابی میپردازد. بعد از شروع به کار شبکه با انجام ارسال و دریافت اطلاعات توسط گرهها، انرژی مصرفی گرهها افزایش مییابد. الگوریتم با آگاهی از انرژی باقیمانده گرهها، گرههایی که مقدار انرژی باقیمانده کمتری از ولتاژ آستانه دارند را به منظور افزایش طول عمر شبکه از شبکه کنار میگذارد و شبکه را مجدداً بر اساس پارامترهای گره (انرژی گره، فاصله و تراکم گرهها) و پارامترهای خوشه (تراکم خوشه و سنسورهای موجود در خوشه) همانطور که در بالا گفته شد، خوشهبندی میکند. این در حالی است که با حذف گره با انرژی باقیمانده پایین که به خاطر عدم توزیع مناسب ترافیک در شبکه رخ داده است اطلاعات مورد نیاز شبکه نیز از بین میروند. بنابراین در نظر گرفتن یک طرفه طول عمر کافی نیست و یک الگوریتم مناسب ارائه شده علاوه بر افزایش طول عمر شبکه باید نیازهای برنامههای کاربردی دیگر را نیز در نظر بگیرد.
الگوریتم پیشنهادی در [۵۴] از ترکیب الگوریتمهای BLLCT[36] [۶۳,۶۲,۶۱] که الگوریتم متعادلسازی بار در لایه اول شبکه است با الگوریتمهایLEACH [64] و PAGASIS[37] [۶۵] که به ترتیب والدهای خود را با در نظر گرفتن انرژی اولیه و کوتاهترین فاصله بین گرهها انتخاب میکنند، استفاده کرده است. در این الگوریتم با استفاده از یک اصلاح پویا، مسیر ارسال اطلاعات را با استفاده از پارامترهای وزن مصرف انرژی در گرههای حسگر و انرژی باقیمانده در گرههای والد تعیین میکنند. الگوریتم والدهایی که دارای بار سنگین و یا دارای کمترین مقدار بار را در میان گرههای هم لایه خود هستند را انتخاب میکند و انرژی باقیمانده گره والد انتخاب شده را با بیشترین انرژی باقیمانده در گرههای فرزند ضرب در وزن ارسال که از قبل مشخص شده است مقایسه میکند. در صورتی که انرژی باقیمانده والد بیشتر باشد ارتباط باقیمیماند در غیر این صورت به تعویض گره والد اقدام میکند. تمرکز الگوریتم تنها بر روی افزایش طول عمر شبکه است این در حالی است که هر گره با توجه به محدوده ارتباطی خود نمیتواند اطلاعات خود را بین تمام گرههای موجود در شبکه به اشتراک بگذارد. بنابراین این امکان وجود دارد که با تغییر گره والد، گره والد جدید در محدوده ارتباطی چند گره قرار نگیرند. بدین ترتیب مقداری از اطلاعات به خاطر تغییر نقش گرهها در
شبکه از بین میرود.
الگوریتمMBT[38] [۶۶] مشکل از دست دادن اطلاعات گرهها هنگامی که گره والد خود را به دلیل الگوریتمهای تغییر نقش گرهها در شبکه از دست میدهد را حل کردند. در این الگوریتم گرهها جدول اطلاعاتی از وضعیت گرههای همسایه خود را به صورت دورهای در اختیار دارند. با چنین اطلاعاتی هنگامی که یک گره والد خود را از دست میدهد با توجه به وضعیت گرههای همسایه خود که در اختیار دارد اقدام به انتخاب گره والد جدید خود میکند. همچنین هنگامی که تغییری در شبکه به وجود میآید، در صورتی که گره همسایه مسیری با تعداد هاب کمتر به سمت ایستگاه پایه پیدا کند، گره همسایه را به عنوان والد جدید خود انتخاب کند، بنابراین درخت مسیریابی دوباره شکل میگیرد. در این الگوریتم تنها بر روی مشکل از دست نرفتن و یا سریعتر رسیدن بستهها به ایستگاه پایه تمرکز شده است و هیچ صحبتی از تعادل بار در شبکه انجام نشده است حتی با وجود اطلاعات سرباری که هر گره از همسایگان خود در اختیار دارد مصرف انرژی را در شبکه بیشتر کرده است.
الگوریتم پیشنهادی در [۶۷] طرحی برای جمعآوری اطلاعات گرههای کنار جادهای به منظور کاهش مصرف انرژی با قابلیت اطمینان و تحمل خطا ارائه کرده است. در این الگوریتم حسگرهای کنار جادهای که به صورت نواری مستقر شدهاند و در بلوکهای مجازی در کنار جاده تقسیمبندی میشوند. گرههای سرخوشه یک فاصله زمانی را به هریک از فرزندان برای ارسال اطلاعاتشان اختصاص میدهد، به منظور جلوگیری از تداخل در میان همسایگان، از بین رفتن بستهها و گوش دادن به مسیر در حالت بیکاری که عوامل مصرف انرژی هستند، گرهها در زمانهای غیرفعال برای صرفهجویی در انرژی به حالت خواب میروند. این الگوریتم علاوه بر افزایش طول عمر شبکه بر قابلیت اطمینان نیز مورد توجه قرار گرفته شده اما هیچگونه تضمینی در تأخیر و متعادلسازی بار برای قسمت ارسال اطلاعات توسط سرخوشهها به سمت ایستکاه پایه انجام نگردیده است.
الگوریتم پیشنهادی در [۵۵] یک معماری ۳ لایه برای شبکههای حسگر بیسیم مطرح کرده است. همانطور که میدانید یکی از الگوریتمهای کاهش مصرف انرژی در شبکههای حسگر بیسیم استفاده از معماری خوشهیابی است. اگر گره سرخوشه در جایی دور از گره جمع کننده قرار بگیرد مصرف انرژی آن بیشتر از یک گره که در نزدیکی گره جمع کننده با همان بار قرار دارد، خواهد بود. برای رفع این مشکل الگوریتم ارائه شده در نظر میگیرد یک گره رله را تا گره سرخوشه از طریق گره رله اطلاعات خود را برای جمعکننده ارسال کند. مدل این الگوریتم مطابق با به شکل۲-۱ میباشد:
شکل۲‑۱ معماری پیشنهادی ارتباطات سه لایه
در این الگوریتم گرهها ۳ نوع نقش را بر عهده میگیرند. اول گرههایی که مانند یک گره اولیه اطلاعات را از محیطزیست جمعآوری میکنند. این گروه خود دارای ۳ نوع میباشد: گرههایی که انرژی معمولی دارند، گرههایی که انرژی بیشتر، و گرههایی که انرژی آنها به صورت رندوم توزیع شده است. نوع دوم گرههایی هستند که به عنوان گره سرخوشه عمل میکنند که آنها وظیفه جمعآوری اطلاعات گرههای اولیه را بر عهده دارند. همچنین گرههای سرخوشه مسئول TDMA[39] تخصیص حافظه در فاز ارسال هستند. و در نهایت گرههایی که به عنوان رله عمل میکنند و اطلاعات جمع شده توسط گره سرخوشه را به گره جمعکننده ارسال میکنند. چالشی که در الگوریتمهای خوشهبندی وجود دارد، توزیع گرههای قدرتمند به عنوان گرههای سرخوشه و رله در میان گرههای عادی موجود در شبکه است به ویژه در شرایطی که دخالت انسان در شبکه ممکن نیست. در چنین شرایطی ممکن است برخی از سرخوشهها تعداد زیادی گره در خوشه خود داشته باشند، در حالی که دیگر سرخوشهها دارای تعداد کمتری باشند بنابراین الگوریتم متعادلسازی نمیتواند خوب عمل کند. همچنین ممکن است مجموعهای از گرهها نتوانند گره سرخوشه خود را پیدا کنند و مجبور به برقراری اتصال از طریق چند هاپ به نزدیکترین سرخوشه شوند.
 
الگوریتمهای مبتنی بر ساختار
در مقابل الگوریتمهای جستجوگرانه و نامبتنی بر ساختار اشاره شده در بخشهای قبل، دستهای از الگوریتمها در ابتدا یک گراف مسیریابی را تشکیل میدهند و در ادامه کار شبکه از این گراف برای هدایت بستهها استفاده میکنند. چنین ساختاری برای شبکههای ثابت که برای کاربردهایی مانند جمعآوری داده از محیطهای هوشمند، یا اتوماسیون صنعتی استفاده می شوند مناسبتر و کارامدتر به نظر میرسد. این الگوریتمها بیشترین شباهت ساختاری را به لحاظ نحوه تولید توزیع ترافیک، به الگوریتم پیشنهادی در این رساله دارند. خصوصاً الگوریتم UDDR که پایه اصلی الگوریتم پیشنهادی است از این دسته از الگوریتمهاست. لذا الگوریتمهای این بخش خصوصاً UDDR را با جزئیات بیشتری مطالعه میکنیم.
 
 
الگوریتمRPL
کارگروه مهندسی اینترنت در سالهای اخیر کمیتهای برای استاندارد سازی الگوریتم مسیریابی در شبکههای ۶LoWPAN و LLN تحت عنوان ROLL[40] تشکیل داده است. این کمیته تاکنون چندین RFC برای تعیین الزامات مسیریابی در شبکههای توان پایین خانگی، صنعتی و شهری و در نهایت نسخه نهایی پروتکل مسیریابی پیشنهادی جهت استفاده در شبکههای توان پایین را تحت عنوان RPL ارائه نموده است. این پروتکل با توجه به تمامی پروتکلهای مطرح شده تا کنون، دارای جامعیت و ساختار بسیار مناسبی جهت استفاده در شبکههای حسگر بیسیم است و با استفاده از ترکیب مکانیزمهای ارائه شده در روشهای پیشین و
ساختارمند نمودن آنها، بستر مناسبی جهت ایجاد مسیرهای یک یا چندگانه در شبکه های حسگر بیسیم با قابلیت پشتیبانی از کلاسهای سرویس مختلف را فراهم نموده است. از سوی دیگر توابع هدف مسیریابی و معیارهای وزندهی لینکها، به صورت مجزا برای استفاده در پروتکل اصلی تعبیه شدهاند تا امکان انتخاب مسیرهای بهینه بر اساس انواع پارامترها و توابع هدف وابسته به کاربرد ممکن شود. در این بخش به طور خلاصه به تشریح پارامترها و روش عملکرد این پروتکل خواهیم پرداخت. آنچه در این بخش آمده است تنها قسمتی از پروتکل است که با فرآیند تشکیل مسیر و هدایت بستهها روی مسیرهای تشکیل شده در ارتباط است. بسیاری از قسمتهای پروتکل مانند مکانیزمها و الزامات امنیتی [۶۸]، چگونگی مسیریابی نقطه به نقطه [۶۹]، الگوریتم زمانبندی بروز رسانی گراف [۷۰] و مسائلی از این دست به دلیل عدم ارتباط مستقیم با مباحث مورد نظر در این رساله، مورد اشاره قرار نگرفتهاند.
 
 
 
گراف مسیریابی جهت دار مبتنی بر مقصد (DODAG)
شبکههای بیسیم به دلیل عدم وجود لینک سیمی بین گرهها معمولاً همبندی از پیش تعیین شدهای ندارند. البته رنج ارسال و دریافت رادیویی گرهها، یک همبندی اولیه از ارتباطات بین گرهها را ایجاد میکند ولی همبندی نهایی شبکه با استفاده از پروتکل مسیریابی و وابسته به کاربرد مربوطه ایجاد میشود. الگوریتم RPL از یک روش ساختارمند برای تولید گراف مسیریابی جهتدار به شکل یک درخت پوشا استفاده میکند که گره جمعکننده داده محلی یا همان سینک، نقش ریشه آن را بازی میکند. این گراف جهتدار مبتنی بر مقصد (یا ریشه) در اصطلاح این پروتکل [۴۱]DODAG نامیده میشود. چینین ساختاری برای شبکههای شخصی توان پایین با گرههای مشخص و نسبتاً ثابت (کم تحرک) که برای کاربردهایی مانند جمعآوری داده از محیطهای هوشمند، یا اتوماسیون صنعتی استفاده میشوند مناسبتر و کارامدتر به نظر میرسد. اگر شبکه اصلی دارای سینکهای محلی متعدد باشد، فرض پروتکل مسیریابی اینست که اطلاعات محلی توسط DODAGها به گرههای سینک منتقل و از طریق یک شبکه ستون فقرات مجزا به مراکز کنترل اصلی یا به اینترنت ارسال میشوند. این جریان ترافیک سلسله مراتبی در جهت معکوس نیز کار میکند و میتواند فرمانها کنترلی را به گرههای انتهایی منتقل نماید.