مسیریابی در شبکه های ادهاک

مسیریابی در شبکه های ادهاک

در این مقاله، مسیریابی در شبکه های ادهاک را مورد بررسی قرار داده و اجزا و اهداف مسیریابی، به همراه پروتکل های استفاده شده در این شبکه را مورد بررسی قرار می دهیم و در نهایت نتیجه گیری از مطالب ذکر شده بیان می شود.

مسیریابی در شبکه :

فرایند انتقال اطلاعات از یک منبع به یک مقصد معین را مسیریابی بسته های اطلاعات در شبکه می نامند. این عمل وظیفه اصلی لایه شبکه است و ایجاد این مسیر در مهمترین حالت به الگوریتم مسیریابی مورد استفاده بستگی دارد. در همه شبکه ها  اعم از شبکه های ثابت و سیار مسیریابی یکی از مهمترین مسائل آن شبکه است و پروتکل های مختلفی برای این کار تهیه شده است.

پروتکل های مسیریابی دو وظیفه عمده دارند :

1. انتخاب مسیرهای بهینه بین گره های مبدأ و مقصد
2. تحویل پیام ها از مبدأ به مقصد

مسیریابی در شبکه های ادهاک نهایتاً منتهی به حل مسئله یافتن کوتاهترین مسیر می شود و هر مسیریاب قادر به ارایه خدمات دیگری نیز می باشد که برخی از مهمترین آنها عبارتند از: مرتب سازی ترافیک، فیلترینگ امنیتی، مدیریت شبکه و نگهداری منابع شبکه.

شکل 1: ارسال یک بسته و مسیر یابی و رسیدن بسته به مقصد

اجزای مسیریابی

مسیریابی با دو فعالیت اساسی سر و کار دارد:

1. تخمین بهینه مسیرهای مسیریابی
2. حمل کردن بسته های اطلاعاتی

الگوریتم های مسیریابی آن بخش از نرم افزار لایه شبکه اند که مسئولیت تصمیم گیری در خصوص خط خروجی که یک بسته ورودی باید بر روی آن ارسال شود، را دارا می باشند. انواع مختلفی از الگوریتم های مسیریابی وجود دارد که هر الگوریتم یک فشردگی متفاوتی در شبکه و منابع مسیریابی دارد. در نتیجه، الگوریتم های مسیریابی از معیارهای گوناگونی که بر محاسبه مسیرهای بهینه تاثیر می گذارد، استفاده می کنند.

در شبکه های ادهاک یک ارتباط مخابراتی مستقیم بین هر دو گره از شبکه با شرایط انتشار رادیویی و محدودیت‌های توان ارسال گره‌ها صورت می‌گیرد و اگر هیچ مسیر مستقیمی بین مبدأ و مقصد وجود نداشته ‌باشد، از مسیر‌یابی چندگذره استفاده می‌شود و در صورتیکه هیچ‌ گونه ساختار ثابت شبکه‌ای موجود نباشد، هر گره در کنار ارسال و دریافت داده، تعدادی از گره‌های همسایه خود را جهت مسیر‌یابی بر مبدأ خود، به کار گرفته و فعال می‌نماید، هر چند کاربرهای آن این موضوع را متوجه نمی‌شوند. یک بسته تا هنگامی که به مقصد خود نرسیده باشد، گره های مسیر را به عنوان مسیر‌یاب استخدام می‌نماید.

مشکلات مسیریابی در شبکه های ادهاک :

مسیر‌یابی در این شبکه از طرف خود گره‌ها حمایت می‌شود، امّا مساله این است که مسیر گره مبدأ و مقصد چگونه معلوم می‌شود. مسیر‌یابی در شبکه های ادهاک بدلیل اینکه شکل شبکه در حال تغییر است، از طریق گره‌ها صورت می‌گیرد. گره‌ها سیار هستند و می توانند شبکه را ترک‌ کرده و یا وارد آن شوند، بنابراین شکل شبکه همواره با سرعت زیادی در حال تغییر است و استفاده از روش‌های جدولی مسیر‌یابی متداول، در چنین شرایطی مناسب نمی باشد.

از آنجایی که در این نوع شبکه هیچ کنترل مرکزی جهت نگهداری اطلاعات به هنگام شکل شبکه وجود‌ ندارد، نیاز به استفاده از الگوریتم‌های توزیع شده وفقی کاملاً حس می‌شود و اطلاعات کنترلی جهت شناسایی حالت جاری شبکه، بین گره‌ها مبادله می‌شود.

از مشکلات دیگر این نوع ارتباط در مسیریابی که ناشی از بی سیم بودن آن می باشد می توان به پهنای باند محدود، تداخل و توان مصرفی اشاره کرد. تداخل باعث می‌شود که مسیر‌یاب اطلاعات اشتباه را به مسیر‌های غیر منتظره و بلا‌ استفاده بفرستد. همانطور که قبلاً ذکر‌ شد، به دلیل اینکه انرژی گره‌ها محدود است، پروتکل اجرایی با مد‌نظر گرفتن این موضوع، باید توان مصرفی گره‌‌ها را به حداقل ممکن برساند.

پروتکل‌های متنوع مسیر‌یابی برای استفاده در شبکه های ادهاک وجود‌ دارد، مهمترین این پروتکل‌ها از سوی گروه شبکه های ادهاک موبایل وابسته به سازمان IETF معرفی شده ‌است. این پروتکل‌ها برای شبکه های متجانس و سیار ادهاک که براساس IP بنا شده‌اند، طراحی گردیده است. هر گره‌ای توانایی تشخیص هویت را دارد و فرض می‌شود هر گره دارای یک آدرس یکتا است. در این پروتکل‌ها تنها معیار در مسیر‌یابی حداقل گذر بین مبدأ و مقصد معرفی می‌شود. بنابراین پارامترهای دیگر نظیر تأخیر مسیر، انرژی‌ مصرفی، توزیع مناسب توان بین پایانه ها، تعدیل بار شبکه و کیفیت سرویس در نظر گرفته نشده‌اند. این پروتکل‌ها تنها بر یک مسیر‌یابی سریع و نگهداری مسیر تحت حداقل هزینه تأکید‌ دارند.

اهداف طراحی الگوریتم های مسیریابی

الگوریتم های مسیریابی اغلب یک یا چندین مورد از هدف های طراحی زیر را دارند:

1. بهینگی
2. سادگی و سرباره کم
3. نیرومندی و پایداری
4. همگرایی سریع
5. انعطاف پذیری

1- بهینگی

حداکثر کردن بازدهی شبکه و قابلیت الگوریتم مسیریابی برای انتخاب بهترین مسیر را که به استانداردهای مورد استفاده برای محاسبه بستگی دارد، بهینگی گویند. به طور طبیعی، پروتکل های مسیریابی باید دقیقا الگوریتم های محاسبه استاندارد خود را تعریف کنند .

2- سادگی و سرباره کم

الگوریتم های مسیریابی تا حد ممکن باید طوری طراحی شوند که ساده باشند. به عبارت دیگر، الگوریتم مسیریابی باید کارایی اش را بطور موثر با کمترین نرم افزار و سرباره عرضه کند. بهره وری مخصوصا زمانی مهم است که نرم افزار الگوریتم مسیریابی باید در یک گره با منابع فیزیکی محدود اجرا شود.

3- نیرومندی و پایداری

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

4- همگرایی سریع

الگوریتم های مسیریابی باید به سرعت همگرا شوند. همگرایی فرآیند توافق همه مسیریاب ها روی مسیر بهینه است. وقتی که یک رویداد باعث خرابی یا غیر قابل دسترس بودن مسیرها می شود، مسیریاب ها پیام های به روز کننده مسیریابی را برای بررسی مجدد مسیرهای شبکه پخش می کنند. در نتیجه باعث تجدید محاسبه مسیرهای بهینه و مطابقت همه مسیریاب ها با این مسیرها می شود.

5- انعطاف پذیری

الگوریتم های مسیریابی باید قابل انعطاف باشند بدین معنی که آنها باید به سرعت و با دقت خود را با تنوع در وضعیت شبکه وفق دهند. برای مثال فرض کنید که یک قسمت شبکه خراب شده است، بطوریکه الگوریتم های مسیریابی زیادی از این مشکل آگاه شده اند، آنها به سرعت می خواهند بهترین مسیر بعدی را بجای مسیرهایی که به صورت عادی از آن استفاده می کردند انتخاب کنند. الگوریتم های مسیریابی می توانند برای وفق دادن تغییرات در پهنای باند شبکه، اندازه صف مسیریابی، تاخیر شبکه و تغییرات دیگر برنامه ریزی کنند.

ارسال بسته ها در شبکه ادهاک

به سه روش زیر ارسال بسته ها در شبکه ادهاک انجام می شود:

1. تک پخشی
2. چند پخشی
3. انتشاری

در مدل تک پخشی یک گره بسته اطلاعات را فقط به یک گره ارسال می کند. به عبارت دیگر مقصد نهایی دریافت پیام تنها یک گره است. در مدل چند پخشی یک گره به چند گره از پیش تعیین شده ارسال می کند و در مدل انتشاری یک گره بسته را به تمام گره های شبکه ارسال می کند. شکل 2 انواع روش های ارسال بسته ها را در شبکه های ادهاک را نشان می دهد. از مهمترین معیارهای طبقه بندی پروتکل های مسیریابی ادهاک زمان بندی می باشد و بر این اساس پروتکل ها به دو دسته جدولی و نیازی طبقه بندی می شوند.

شکل 2: انواع روش های ارسال بسته ها در شبکه های ادهاک

انواع پروتکل های مسیریابی در شبکه های ادهاک :

1. پروتکل های جدولی
2. پروتکل های نیازی

1- پروتکل‌های جدولی

به آن دسته از پروتکل‌هایی گفته می شود که به صورت پیوسته شکل شبکه را با استفاده از تبادل اطلاعات گره‌های شبکه، به روز سازی می‌نماید. بنابراین در زمان نیاز، مقاصد همواره مشخص هستند. خانواده پروتکل های بردار فاصله نمونه هایی از این نوع مسیریابی می باشند. اولین روشهایی که در بحث مسیر‌یابی شبکه های ادهاک مورد توجه قرار‌ گرفتند، از این نوع پروتکل بوده است. بزرگترین مشکلی که ضمن بکار‌گیری پروتکل‌های مسیر‌یابی جدولی در شبکه های ادهاک بوجود می‌آید، ناشی از تغییر پیوسته شکل شبکه است.

بنابراین اطلاعات شکل شبکه باید مرتباً انتشار‌ یابد که این خود هزینه سنگینی را در منابعی چون پهنای باند، توان باتری ها و زمان پردازش، ایجاد می‌کند. همچنین به دلیل الگوهای مختلفی که برای یک شبکه می‌تواند وجود داشته ‌باشد، گاهی تنها درصدی از مسیر‌یاب ها استفاده می‌شود و بقیه بی‌دلیل، اطلاعات خود را در شبکه منتشر می‌کنند. با این حال این پروتکل ها برای آن دسته از شبکه های ادهاک که سرعت تغییراتشان به اندازه کافی کم باشد، قابل استفاده هستند.

این پروتکل های مسیریابی روشهای متفاوتی برای انتشار اطلاعات تغییر یافته توپولوژی شبکه و تعداد جداول لازم مرتبط با مسیریابی دارند. بعضی از مثال های این پروتکل ها DSDV ، CGSR ، WRP ، FSR ، GSR و HSR می باشند. در الگوریتم های جدولی همیشه تعداد مشخصی انتقال اطلاعات کنترلی در حال انجام است، حتی اگر برای مدتی اصلا هیچ انتقال داده ای در شبکه انجام نگیرد، مشخص است که چنین شیوه ای هزینه زیادی را متحمل خواهد شد.

2- پروتکل‌های نیازی

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

هنگامی که استفاده از یک مسیر‌یاب در شبکه مورد نیاز باشد، پیام “درخواست مسیر” در شبکه منتشر می‌شود و این پیام توسط مبدأ یا گره‌ای در نزدیکی آن دریافت می‌شود. آن گره نیز یک پیام “پاسخ مسیر” به سوی گره اولیه روانه می‌کند. پروتکل های AODV ،DSR ،TORA ،LMR و ABR مثالهایی از پروتکل‌های نیازی هستند و هدف این پروتکل ها این است که با کشف تنها مسیرهای درخواست شده و مورد نیاز، هزینه را حداقل کنند. این دسته از پروتکل ها باعث کاهش چشمگیری در مصرف منابع شبکه و هزینه های آن خواهند شد ولی در عوض تأخیر در هنگام برقراری اتصال را افزایش می دهند.

در واقع برای کاهش سرباره نگهداری اطلاعات پروتکل های جدولی، از این پروتکل ها استفاده می شود. سرباره کشف مسیر هنگامی که لینک معکوس داشته باشیم با O(N+M) رشد کرده و در لینک های تک جهتی O(2N) می باشد. روشهای متفاوتی برای کشف مسیرها در الگوریتم های نیازی وجود دارد. بیشتر الگوریتم ها از یک طرح مشتق شده از مسیریابی پل (LAN) یعنی کشف مسیر بوسیله یادگرفتن وارونه استفاده می کنند.

در حالت کلی پروتکل های نیازی به دو دسته مسیریابی تقسیم می شوند :

1. مسیریابی پرش به پرش تقسیم
2. مسیریابی منبع

1- مسیریابی پرش به پرش

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

برای کاهش سرباره مسیر جدید، بسته سوال اگر با یک گره که قبلا مسیر برای چنین مقصدی را داشت، برخورد کند، در آن مسیر برای مقصد رها می شود. بعد از محاسبه مسیر، تا زمانی که منبع از آن استفاده می کند بصورت به روز نگهداری می شود.

برای مثال، یک ارتباط ناموفق ممکن است باعث رهاسازی سوال و پاسخ دیگری شود تا مسیر همیشه به روز نگهداری شود. مزیت این روش در این است که تطابق بهتری با محیط های دینامیکی شبکه های ادهاک موبایل دارد و اطلاعات مسیریابی تازه تری دارد. استفاده از اطلاعات مسیر تازه تر به معنای محاسبات کمتری برای انتقال داده می باشد. عیب این روش در آن است که هر گره واسطه ای بایستی اطلاعات جدول مسیریابی را برای هر مسیر فعال ذخیره کند و هر گره ای بایستی از گره های همسایه مطلع باشد.

2- مسیریابی منبع

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

در مسیریابی منبع، بسته های داده آدرس کامل منبع به مقصد را حمل می کنند و هر گره در شبکه، یک منبع ذخیره سازی مسیرهایی را که یاد گرفته است، دارد. هر یک از گره های واسط این بسته ها را طبق اطلاعاتی که در ابتدای بسته وجود دارد انتقال می دهد و نیازی به نگهداری اطلاعات مسیریابی به روز شده در گره های واسط نمی باشد. اگر یک گره مسیری را که بعلت تغییرات توپولوژی منسوخ شده، تشخیص دهد، یک خطای مسیر برای منبع می فرستد. منبع سپس یک فرآیند کشف مسیر برای ایجاد کردن یک مسیر جدید طلب می کند.

معایب مسیریابی منبع :

یکی از معایب مسیریابی منبع در این است که برای شبکه های وسیع عملکرد خوبی ندارد که این امر به دو دلیل اصلی است: اول اینکه تعداد گره های واسط در مسیر افزایش یافته و احتمال خطای مسیر افزایش می یابد. دوم اینکه با ازدیاد گره های واسط، میزان سرباره ای که توسط هر سربند بسته داده ایجاد می شود، رشد می یابد.

آزمایش‌های اولیه که برای تعداد کمی از گره‌های ثابت (مثلاً 10 عدد) انجام گرفته ‌است، تأخیر حدود 2 میلی ثانیه برای دو گذر و70 میلی ثانیه برای چهار گذر را نتیجه داده‌ است که در بسیاری از موارد عملی قابل قبول می باشد. در شرایط کنونی بازده شبکه با افزایش تعداد گذرها پایین می‌آید، به عنوان مثال در حالی که یک مسیر‌بان گذر از نرخ 2 الی mbit/s3 برخوردار است، این سرعت در مسیری با چهار‌گذر بهmbit/s 1 نزول می‌کند.

جمع بندی

از آنجایی که بیشتر دستگاه‌ها در شبکه های ادهاک با باتری راه‌ اندازی می‌شوند، مصرف انرژی سیار مهم بوده و مسیر‌یابی باید برای بیشینه نمودن عمر باتری، بهینه شود. در میان عملیاتی که انرژی مصرف می‌نمایند، انتقال بیسیم داده رتبه اول را دارد.

نتایج، این حقیقت را روشن می کند که هر دو گروه پروتکل های مسیریابی جدولی و نیازی نمی توانند در شبکه هایی که بسیار پویا می باشند، خوب عمل کنند. اگر چه پروتکل های جدولی خیلی سریع می توانند مسیر مورد نیاز را فراهم کنند، در عوض برای اینکه همیشه بتوانند توپولوژی به روز شده شبکه را نگهداری کنند، منابع شبکه را به هدر می دهند. از طرف دیگر پروتکل های نیازی، می توانند میزان استفاده از منابع شبکه را کاهش دهند، اما امکان دارد که با درخواست های مسیر در الگوریتم های مبتنی بر flooding، با تأخیر زیادی همراه باشد.

روش دیگر مسیریابی، استفاده از پروتکل های دورگه می باشد که مقاصد پروتکل های جدولی و نیازی را جمع بندی می کند. در این پروتکل ها هر گره فقط توپولوژی همسایه نزدیک به خود را نگهداری می کند بنابراین میزان ترافیکی که در پروتکل های جدولی موجود می باشد را کاهش می دهد. پروتکل های ZRP و ZHLS نمونه هایی از این دسته می باشند.