بررسی، شبیه سازی و بهبود الگوریتم های کاهش مصرف انرژی در …

تضمین قابلیت اطمینان در این الگوریتم از طریق کپیکردن بستههای حساس به قابلیت اطمینان روی لینکهای مختلف صورت میپذیرد. در این الگوریتم تخمین احتمال رسیدن بسته به مقصد از روی نرخ خطای لینکهای محلی مابین گره هدایتکننده و گرههای همسایه انجام میپذیرد. به عبارت دیگر به طور خوشبینانهای فرض میشود که تمامی لینکهای ارتباطی تا رسیدن بستهها به مقصد، نرخ خطایی مشابه نرخ خطای لینکهای همسایه داشته باشند. این طبیعتاً فرضی ناصحیح است چون شرایط محیطی و نویز میتواند برای یک گره با گرههای کمی دورتر از خود متفاوت باشد. به هر حال الگوریتم MMSPEED قابلیت اطمینان انتها به انتهای ارائه شده توسط هر یک از همسایگان را از طریق فرمول ۲ زیر تخمین میزند.

نحوه محاسبه یا نرخ خطای لینک (i,j) در این الگوریتم توضیح داده نشده است. یکی از نقاط ضعف اساسی این الگوریتم غیر از موارد اشاره شده در فوق عدم حساسیت آن به انرژی گرهها در انتخاب گام بعدی برای بستهها میباشد. این امر ممکن است منجر به توزیع نامتوازن ترافیک در سطح شبکه و کاهش طول عمر آن گردد.
الگوریتم SDSCR [57] یکی دیگر از الگوریتمهای این گروه است که از روش جغرافیایی برای هدایت بستهها به سمت مقصد استفاده میکند. این الگوریتم در ابتدا گرهها را بر اساس قدرت سیگنال دریافتی از گره جمعکننده یا گرههای بالادستی، به لایههای چندگانهای تقسیم میکند و هر گره گام بعدی خود را از میان گرههای لایه بالاتر انتخاب میکند. این الگوریتم برای ایجاد تمایز در کیفیت سرویس (که تنها از نوع تأخیر انتخاب شده)، بستهها را به لحاظ میزان زمان باقیمانده تا انقضای مدت، به کلاسهای مختلف تقسیم نموده و سپس آنها را به ترتیب اولویت سرویسدهی میکند. این الگوریتم برای تشخیص زمان انقضای بستهها، حد تأخیر قابل تحمل سراسری را که توسط کاربرد تعیین میشود به تعداد گامهای تخمینی باقیمانده تا مقصد تقسیم نموده و از روی آن یک حد تأخیر قابل تحمل محلی بدست میآورد و همان را به عنوان تخمین زمان انقضای بستهها در نظر میگیرد. در الگوریتم SDSCR هر گره از روی حد تأخیر قابل تحمل و میزان تأخیر اندازهگیری شده روی لینکهای خود با همسایگان، یک سرعت ارسال به سمت گره جمع کننده برای هر همسایه تخمین میزند و بستهها را به سمت گرهای که بیشترین سرعت را ارائه دهد ارسال میکند. در الگوریتم اشاره شده که در صورتی که چندین گره از لایه بالاتر سرعت یکسانی را ارائه کنند بستهها به سمت گره با بار ترافیکی کمتر هدایت میگردد. لیکن هیچگونه مکانیزمی برای تشخیص بار ترافیکی گرهها در رساله اشاره نشده است. نقطه ضعف مهم دیگر الگوریتم عدم حساسیت به انرژی است که برای الگوریتمهای پیشنهادی در شبکههای حسگر بیسیم امری ضروری است.
 
 
الگوریتمهای مبتنی بر هوش مصنوعی و تئوری مورچگان
الگوریتم QAMR [50] یکی از الگوریتمهای تضمین کیفیت سرویس مبتنی بر تئوری مورچگان است. این الگوریتم در فاز تشکیل مسیر مسیر مجزا از هم را با ارسال بستههای مسیریابی یا مورچههای FANT پیدا میکند. این مورچه ها در فاز رسیدن خود به مقصد از مسیرهایی که دارای تأخیر و تعداد گام کمتر و پهنایباند و انرژی بیشتر هستند عبور میکنند. طریقه اندازه گیری یا تخمین تأخیر و پهنایباند روی مسیرها در این الگوریتم اشاره نشده است. معیار انرژی از روی انرژی باقیمانده گرهها تخمین زده میشود. معیارهای مسیریابی دیگر در قالب یک تابع هزینه ترکیبی و ساده مطابق با معادله ۳ با یکدیگر ادغام میشوند و در محاسبه سطح فرومون هر مسیر استفاده میگردند.

که در آن درجه خوبی مسیر از نظر تعداد گام، پهنای باند و تأخیر میباشد. هر یک از درجه خوبیها از روی تقسیم هزینه مسیر بر میزان قابل تحمل آن به لحاظ کیفیت سرویس بدست میآید. البته اینکه تعداد گامهای مسیر چگونه می تواند جزء پارامترهای کیفیت سرویس باشد و حد بالای آن چگونه تعریف میگردد، در این الگوریتم اشاره نشده است. مخرج کسر فوق مجموع حاصلضرب درجههای خوبی روی تمامی مسیرهای بدست آمده برای یک گره است. علاوه بر مشکلات ذکرشده بستههای مسیریابی با توجه به انرژی باقیمانده به عنوان یکی از معیارها مسیر خود را انتخاب میکند. به این ترتیب تعداد زیادی گره به گرههایی که دارای انرژی باقیمانده بیشتری هستند، متصل میشوند و این امر باعث مصرف زیاد انرژی گره وکاهش طول عمر شبکه میشود.
در مقاله [۵۱] با ارائه الگوریتم مسیریابی با استفاده از کلونی مورچهها مشکل عدم تعادل انرژی در بین گرهها را که در الگوریتمهایی مانند الگوریتم LEACH[32] [۵۸]، را حل کردند. در این الگوریتم گرهها با توجه به جدول اطلاعاتی موجود در هر گره به دو دسته گرههای معمولی و گرههای جمعکننده تقسیم میشوند. گرههای جمعکننده مسئولیت تجمیع و ادغام اطلاعات را دارند بنابراین ترافیک کاهش پیدا میکند و انرژی ذخیره میشود. یک گره برای پیدا کردن مسیر خود تا ایستگاه پایه با استفاده از معیارهای انرژی باقیمانده انرژی، فاصله بین دو گره و قدرت فرومون گره بعدی خود را انتخاب میکنند. زمانی که تمامی مورچهها یا بستههای مسیریابی به گره ایستگاه پایه رسیدند. سوابق مسیر طی شده توسط مورچهها ضبط خواهد شد و به این ترتیب هر یک از گرهها مسیر خود را به گره ایستگاه پایه پیدا کردهاند. بعد از مدتی کار مقدار انرژی گرههای جمعکننده کمتر از مقدار مشخصی میشود بنابراین شبکه دوباره شروع به مسیریابی میکند. در این الگوریتم تنها مشکل عدم تعادل انرژی موجود

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

با تغییر نقش گرهها رفع شده است. به خاطر خاصیت الگوریتم مورچهها یا بستههای مسیریابی به گرههایی که دارای شرایط بهتری هستند، تمایل پیدامیکنند و این تمایل باعث اضافه شدن بار ترافیکی در گره مورد نظر میشود. در نتیجه این امر باعث کوتاه شدن عمر گره میشود. از طرفی وجود سربارهای زیاد موجود در راهاندازی شبکه انرژی گرهها تحلیل میرود. علاوه بر مشکلات ذکر شده الگوریتم از گرههای همگن استفاده میکند، که این امکانپذیر نیست. در واقع گرههای مستقر شده از نظر انرژی باقیمانده، محدود ارسال و پهنایباند با هم متفاوت هستند.
الگوریتم 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ها به گرههای سینک منتقل و از طریق یک شبکه ستون فقرات مجزا به مراکز کنترل اصلی یا به اینترنت ارسال میشوند. این جریان ترافیک سلسله مراتبی در جهت معکوس نیز کار میکند و میتواند فرمانها کنترلی را به گرههای انتهایی منتقل نماید.

شناسههای پروتکل

هر گراف با یک شناسه گراف (DODAG_ID) و یک شماره ویرایش گراف (DODAG_VersionNumber) شناخته میشود. شناسه گراف برای هر گراف یک عدد ثابت است که توسط ریشه گراف تعیین میشود و به منظور ایجاد یکتایی میتواند آدرس IP گره ریشه باشد البته امکان ایجاد چند گراف مستقل توسط یک گره ریشه نیز در الگوریتم دیده شده که در این حالت باید از مکانیزم دیگری برای آدرس دهی گرافها استفاده نمود یا اینکه به گرههای ریشه چندین آدرس IP اختصاص داد، تا بتوان گراف های متعدد موجود در شبکه حسگر را روی بستر اینترنت به یکدیگر متصل نمود. شماره ویرایش گراف، عددی ترتیبی است که برای بروز رسانی مسیرها در گراف و توسط گره ریشه تعیین میشود. البته ترمیم مسیرها به صورت محلی و به طور متناوب در لایههای مختلف شبکه انجام میشود لیکن بروز رسانی سراسری گراف تنها از سوی ریشه آن قابل انجام است. گره ریشه در بازههای زمانی مشخص یا بر اساس نیاز با انتشار بسته مسیریابی جدید، ویرایش جدیدی از گراف را تولید مینماید. بازههای زمانی بروز رسانی مسیرها چه به صورت محلی و چه به صورت سراسری توسط الگوریتم زمان بندی خاصی تحت عنوان tricle timer [70] تعیین میشود.
در فرآیند تشکیل گراف هر یک از گرههای زیر مجموعه، دارای یک رتبه میشوند که فاصله آنها را از ریشه تعیین میکند. منظور از فاصله در اینجا فاصله جغرافیایی یا تعداد گام نبوده و بسته به معیار انتخاب شده برای تعیین رتبه میتواند متفاوت باشد. به عنوان مثال در صورت استفاده از معیار تأخیر برای رتبه بندی گرهها، رتبه هر گره نشان دهنده میزان تأخیر بستهها برای رسیدن از آن گره به گره سینک خواهد بود. تعریف رتبه برای گرهها، باعث جلوگیری از ایجاد حلقه در مسیرها میشود اگر گرههای والد برای هر گره همواره از میان گرههای با رتبه بالاتر انتخاب شوند. رتبه گرهها از روی رتبه گره ریشه و با استفاده از معیارهای مسیریابی و تابع هدف تعریف شده توسط پروتکل به صورت تجمعی قابل محاسبه است و امکان ایجاد مسیرهای بهینه بر اساس معیارهایی مانند انرژی مصرفی، تأخیر و غیره [۷۱] و یا حتی ترکیبی از آنها [۷۲] را فراهم میسازد.