X
تبلیغات
رایانه - مقایسه چهار پروتکل مسیریابی معروف در شبکه های اقتضائی
 شبکه های اقتضایی با توجه به مشخصات منحصر به فردشان گزینه ای مناسب جهت استفاده در میادین جنگ ، مناطق دورافتاده ، موقعیت های اورژانسی ، کلاس های مجازی و ... هستند.با توجه به گسترش روزافزون این شبکه ها در عرصه های مختلف لزوم طراحی بهینه ی پروتکل های مسیریابی بیش از پیش حائز اهمییت است.تاکنون پروتکل های مسیریابی زیادی برای شبکه های اقتضایی پیشنهاد شده است. هدف از طراحی این پروتکل ها کمینه سازی یک یا چند عامل محدود کننده راندمان شبکه(مثل محدودیت توان عملیاتی گره ها،سربارهای کنترلی،سربارهای پردازشی و ... )است.ما در این مقاله روی کمینه سازی سربارهای کنترلی متمرکز می شویم و یک پروتکل گردش گرا به نام FORP را با سه پروتکل معروف دیگر (DSR,AODV,LAR) مقایسه می کنیم.

كليد واژه : پروتکل های مسیریابی ، سربارهای کنترلی ، شبکه های اقتضایی ، کنترل گردش.

1-مقدمه:

شبکه های اقتضایی (Ad Hoc)نمونه ی نوینی از شبکه های مخابراتی بی سیم هستند که به خاطر مشخصات منحصر به فردشان امروزه بسیار مورد توجه قرار گرفته اند.در این شبکه ها هیچ پایگاه مبنا،تقویت کننده و مرکز سوئیچینگ ثابتی وجود ندارد بلکه این خود گره ها هستند که عملیات تقویت داده سوئیچینگ ومسیریابی را انجام می دهند.با توجه به تغییرات مداوم در توپولوژی شبکه به واسطه ی تحرک گره ها پروتکل های مسیریابی باید با اتخاذ نوعی استراتوژی سازگار این تغییرات را پشتیبانی کنند به نحوی که داده ی ارسالی به سلامت از مبدا به مقصد برسد.از اوایل دهه 80 میلادی تاکنون پروتکل های مسیریابی فراوانی برای شبکه های اقتضایی پیشنهاد شده است.این پروتکل ها رنج وسیعی از مبانی و روش های طراحی را شامل می شوند از یک تعریف ساده برای پروتکل های اینترنتی گرفته تا روش های سلسله مراتبی چندسطحه ی پیچیده.بسیاری از این پروتکل ها بر اساس فرض های ابتدایی ساده ای طراحی می شوند مثلا در بسیاری از این پروتکل ها تمام گره ها منابع و توانایی های یکسانی دارند به عنوان نمونه گره ها رنج ارسال یکسان دارند و پیوندها دوطرفه فرض می شوند البته پروتکل هایی هم هستند که عملاً با لینک های یک طرفه سروکار دارند.نهایتا اگرچه هدف بسیاری از پروتکل ها قابل استفاده بودن برای شبکه های بزرگ است اما معمولا و به طور میانگین برای 10 تا 100 گره طراحی می شوند. کمبود توان باتری،پهنای باند محدود،میزان خطای زیاد،تزاحم داده و تغییرات مداوم در توپولوژی شبکه از مشکلات اساسی شبکه های اقتضائی است.به دلیل همین محدودیت ها پروتکل های مسیریابی برای این گونه شبکه ها به گونه ای طراحی می شوند که حداقل یکی از عوامل زیانبار شبکه را کمینه سازند . به عنوان مثال برخی پروتکل ها صرفا بر مبنای توان باتری گره ها بنا می شوند،بسیاری دیگر کمینه سازی سربارهای پردازشی را مورد توجه قرار می دهند و در بسیاری دیگر اجتناب از حلقه(که خود عامل بسیاری از محدودیت ها در شبکه من جمله کاهش پهنای باند و ... است ) هدف طراحی است.اما دسته وسیعی از پروتکل ها نیز وجود دارند که به دنبال کمینه سازی سربارهای کنترلی هستند.ما در این مقاله ضمن توضیحی مختصر راجع به سه پروتکل معروف DSR,AODV,LAR در بخش های 3,2 و4 در بخش 5 پروتکلی گردش گرا به نام FORP را تشریح می کنیم.در نهایت در بخش 6 پروتکل های نامبرده را از نظر سربارهای کنترلی با هم مقایسه می کنیم. ‌

2-(DSR( Dynamic Source Routing

DSR یک پروتکل راکتیو است که می تواند شبکه های اقتضائی را بدون نیاز به جداول مسیریابی و به روز سازی آنها مدیریت کند.DSR به طور اخص برای شبکه های اقتضائی چند پرشه (multi hop) طراحی می شود.به منظور صرفه جوئی در پهنای باند فرایند مسیریابی تنها زمانی انجام می شود که نیاز باشد(مقتضی).در DSR فرستنده تمام مسیرهای منبع به مقصد را مشخص و آدرس تمام گره های میانی را در بسته ها ذخیره می کند.این پروتکل بر مبنای الگوریتم های موقعیت پیوند(link state) کار می کند یعنی هر گره قادر به ذخیره ی بهترین مسیر به مقصد است.همچنین اگر تغییری در شبکه رخ دهد تمام گره های شبکه از طریق انتشار کلی (flooding) از این تغییر مطلع می شوند.DSR شامل دو مکانیزم عمده می باشد که در زیر به بررسی آنها می پردازیم.

2-1-کشف مسیر

در شکل 1 اگر گرهS در حافظه ی خود مسیری به D داشته باشدو بخواهد با آن ارتباط برقرار کند بلافاصله از این مسیر استفاده می کند.اما اگر مسیری به D موجود نباشد مراحل کشف مسیر به قرار زیر آغاز می شود: گره S یک بسته درخواست مسیر (RREQ) به تمام گره ها می فرستد.اگر گره A درخواست مسیر را قبلا دریافت کرده باشد یا آدرسش در بایگانی مسیر موجود باشد این گره درخواست را حذف می کند.اگر گره A هدف کشف مسیر باشد گره یک بسته جواب به مسیر(RREP) به مبدا بر می گرداند.بسته RREPشامل بهترین مسیر از منبع به مقصد است وقتی منبع این بسته را دریافت کرد این مسیر را در حافظه مسیر خود ذخیره می کند تا متعاقبا از آن استفاده کند.در غیر این صورت گره A درخواست S را به همسایگان خود می فرستد.

JPG - 7.3 kb
شکل 1

2-2- نگهداری مسیر : در DSR هر گره مسئول تایید دریافت بسته توسط گره بعدی است و همچنین هر بسته تنها یک بار توسط هر گره ارسال می شود . اگر یک بسته به یک گره خاص نرسد فرایند ارسال تا زمانی معین ادمه می یابد . اگر دریافت بسته تایید نشد یک پیام خطای مسیر (RERR ) به منبع فرستاده می شود و مسیر مورد نظر از حافظه مسیر حذف می شود . سپس منبع از روی حافظه مسیر خود دنبال مسیر دیگری می گردد . و اگر مسیری در حافظه نباشد یک بسته درخواست مسیر انتشار می یابد .در شکل 2 اگر گره B بعد از چندین درخواست از C تاییدیه نگیرد یک پیام خطا به گره S (منبع) می فرستد.

شکل 2

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

3- (AODV:(Ad Hoc On demand Distance Vector

AODV یک پروتکل راکتیو است که مبنای آن بر DSDV استوار است که خود شامل یک پروتکل پیش فعال است و در سال 1997 معرفی شده است. این پروتکل برای شبکه هایی با چند ده تا چند صد گره طراحی شده است . یکی از جنبه های AODV استفاده از شماره ی رشته(توالی) در جدول هر گره است. این شماره رشته توسط گره مقصد تولید می شود ،شماره ی رشته هم در بسته درخواست مسیر و هم در بسته های پاسخ به مسیر گنجانده می شود و به گره های درخواست کننده فرستاده می شود .شماره رشته از اهمیت فوق العاده ای برخورداراست . زیرا باعث اجتناب از حلقه شده وبه سادگی قابل برنامه ریزی است . در دیگر گره ها نیز این شماره رشته به منظور به روز رسانی اطلاعات مسیر یابی استفاده می شود. اگر یک گره بین دو مسیر حق انتخاب داشته باشد مسیری را انتخاب می کند که شماره رشته آن بیشتر باشد.AODV با جداول مسیر یابی ساز گار است.بسته های درخواست مسیر ، جواب به مسیر و خطا در AODV نیز همانند DSR تعریف می شود. شکلهای 3و 4و 5 نحوه عملکرد AODV را نشان می دهند. در وحله اول S می خواهد با D ارتباط برقرار کند فلذا اقدام به انتشاربسته درخواست مسیر می کند تا مقصد رابیابد . این گره بسته درخواست مسیر را تولید می کند که شامل آدرس مقصد، شماره رشته و ID انتشار است. سپس آنرا به همسایگانش ارسال می کند

JPG - 11.5 kb
شکل 3

هر گره ی که این درخواست را دریافت می کند مسیری در جهت عکس به گره ارسال می کند ضمن اینکه اگر به مقصد دسترسی نداشته باشد درخواست را به سمت دیگر همسایگانش به پیش می راند. مسیر زمانی یافت می شود که RREQ به گره ی برسد که به مقصد دسترسی دارد و زمانی مسیر قابل بهربرداری است که RREP از D به S برسد ودر جدول مسیر یابی S نگاه داشته شود . پس از دریافت RREP توسط هر گره ، لازم است گره مورد نظر جدول مسیر یابی خود را به روز کند (بر اساس شماره رشته).

شکل 4

هم اکنون S می تواند با D ارتباط برقرار کند .

شکل 5

زمانی که در یک مسیر فعال پیوندی شکسته می شود یک پیام خطا (RERR) به دیگر گره ها ارسال می شود اگر گره ها مسیری شامل پیوند شکسته شده در جدول مسیر یابی خود دارند آن مسیر را حذف می کند و گره S بار دیگر RREQ را به همسایگانش می فرستد البته در این پروتکل هر گره ی که در مسیر قرار دارد می تواند مبادرت به یافتن مسیر به D کند . به چنین مکانیزمی تعمیر محلی مسیر می گویند. اجتناب از حلقه ، انتشار چند گانه اختیاری و کاهش سربار های کنترلی از مزایای این پروتکل و تاخیر درفرآیند کشف مسیر و ضرورت وجود پیوندهای دوطرفه جهت آشکار شدن پیوندهای یک طرفه از جمله معایب آن است.

4-پروتکل مسیر یابی به کمک مکان (LAR): (Location Aided -Routing)

LAR یک پروتکل مقتضی است که بر مبنای DSR بنا نهاده شده است.این الگوریتم از اطلاعات مکانی به منظور کاهش سربار در شبکه ی Ad Hoc استفاده می کند. عموما LAR برای اطلاعات مکانی از GPS استفاده می کند. با GPS گره ها مکان فیزیکی خود را می دانند. به منظور کاهش پیچیدگی پروتکل فرض می کنیم تمام گره ها موقعیت دقیق خود را می دانند یعنی تفاوت موقعیت دقیق گره و موقعیت اعلام شده توسط GPS در نظر گرفته نمی شود البته در[3] محاسبات دقیق نیز آورده شده است (با احتمال خطا در موقعیت انتخابی) هم چنین فرض بر این است که گره ها در صفحه حرکت می کنند(حرکت دوبعدی به جای سه بعدی) 4-1- منطقه مورد انتظار و منطقه درخواستی : منطقه مورد انتظار : در ابتدا فرض می کنیم S می خواهد D را پیدا کند و از قبل موقعیت آن (L) را میداند.سپس منطقه مورد انتظار مربوط به گره D از نقطه نظر گره S منطقه ای است که S انتظار دارد D در ان جا واقع باشد.اگر گره S سرعت حرکت D را بداند این سرعت را برای محاسبه وسعت منطقه مورد انتظار لحاظ می کند . اگر S هیچ اطلاعاتی راجع به D نداشته باشد منطقه مورد انتظار کل وسعت شبکه است و الگوریتم به شکل ابتدایی خود (انتشار کلی) تبدیل می شود. به طور کلی هر چه اطلاعات S راجع به D بیشتر باشد.منطقه انتظاری کوچکتر است. شکل 6 (الف) یک منطقه انتظاری دایروی را نشان می دهد حال آن که در شکل 6 (ب) با فرض این که S می داند D در جهت شمال حرکت می کند این ناحیه به یک نیم دایره تقلیل یافته است.

JPG - 3.6 kb
شکل 6
الف:S هیج اطلاعاتی راجع به جهت حرکت D ندارد ب: S می داند که D به سمت شمال حرکت می کند.

منطقه درخواستی: مجددا فرض میکنیم Sمیخواهد مسیری به D بیابد. گره S منطقه ای مثل شکل (6-الف) را به عنوان منطقه ی درخواستی مشخص میکند.سپس گره S مثل الگوریتم انتشاری اقدام به ارسال درخواست مسیر مینماید با این تفاوت که تنها گره هایی که در منطقه درخواستی قرار دارند این بسته را به پیش می رانند. اما مواردی پیش می آید که مجبوریم گره هایی که در خارج از منطقه در خواست هستند را به عنوان اعضای این منطقه لحاظ کنیم: اگر گره S در منطقه ی انتظاری گره D قرار نداشته باشد این منطقه انتظاری باید به منطقه درخواستی اضافه شود مانند شکل (7- الف).حال این سوال پیش می آید که آیا ناحیه نشان داده شده در شکل مذبور منطقه خوبی است.در شکل (7- ب) دیده می شود که تمام گره ها مابین D و S خارج از این ناحیه هستند لذا انتخاب این چنین ناحیه ای یافتن مسیر بین D,S را تضمین نمی کند.LAR این امکان را فراهم میکند تا با گسترش ناحیه مورد نظر مسیر یابی محقق شود . البته زمانی که منطقه درخواست را به شکل (7- ج) در نطر می گریم طبیعتا سر بار مسیر یابی افزایش می یابد.

JPG - 12.1 kb
شکل 7

4-2- عضویت در منطقه درخواست: الگوریتم LAR تقریبا مشابه به الگوریتم های مسیر یابی پخشی است. با این تفاوت که گره هایی که در منطقه درخواست نیستند بسته ها را پیش نمی رانند ، دو امکان متفاوت جهت مشخص کردن گره به عنوان عضو ناحیه وجود دارد:

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

شکل 8

روش دوم LAR : در این روش گره S از موقعیت گره D را می داند با دانستن این مختصه گره S فاصله خود از D رامحاسبه می کند(Dist D). در درخواست مسیر هم فاصله و هم مختصات مبدا و مقصد لحاظ می شود.حال هر گره که این درخواست را از S دریافت می کند فاصله خودش تا D را محاسبه میکند اگر این فاصله از Dist D بیشتر باشد درخواست حذف می شود و اگر کمتر باشد گره مختصه و فاصله خودش تا مقصد را به درخواست مسیر افزوده و آن را به سوی همسایگانش به پیش می راند ، با ادامه ی این فرآیند نهایتا D پیدا می شود. سپس D پیام پاسخ به مسیر برای S می فرستد شکل (9) این فرآیند را نشان می دهد.

شکل 9

- پروتکل مسیر یابی گردش گرا: FORP (Flow-Oriented Routing Protocol) FORP یک پروتکل مسیر یابی تک پخشه (unicnst) است. یک مسیر یابی تک انتشاره انتشار کلی تحت کنترل در شبکه است . اگر S بخواهد به D دسترسی داشته باشد ، بسته های داده شده را به همسایگانش می فرستد و هر گره ی که این بسته ها را دریافت می کند همین کار را انجام می دهد . به منظور جلوگیری از فرستادن بسته بیش از یک بار از شماره رشته استفاده می شود .لذا بعد از مدت زمانی خاص شبکه عاری از بسته ی P خواهد شد.وقتی P به D رسید مشخص می شود که S به D دسترسی دارد و دیگر بسته P توسط D ارسال نمی شود. وقتی S می خواهد داده ای به D بفرستد، جدول مسیر یابی را چک می کند ، اگر مسیر منقضی نشده ای یافت شود ار آن استفاده می کند در غیر این صورت پیام درخواست گردش را ارسال می کند تا D را بیابد در طول مسیر گره ها اطلاعات مربوط به خودشان را از روی GPS خوانده و به این پیام اضافه می کنند. حال مقصد باید بهترین مسیر را بر اساس معادله زیر پیدا کند (به شکل 10 دقت شود). Link Expirtion Time (LET)

شکل 10

- مقایسه پروتکل ها از نظر کنترل گردش: با توجه به مطالب فوق الذکر به وضوح دیده می شود که در پروتکل DSR علیرغم این که پروتکلی راکتیو است به خاطر تعدد پیغام هایی نظیر RERR,RREP,RREQو همچنین اطلاعاتی که گره ها به این پیغام ها اضافه می کند حجم تبادل اطلاعات کنترلی در شبکه زیاد است.از طرفی AODV اساسا پروتکلی است برگرفته از DSDV که خود بر مبنای الگوریتم بردار فاصله عمل می کند .حال آن که DSR بر اساس موقعیت پیوند بنا نهاده شده است فلذا همین جا می توان نتیجه گرفت حجم اطلاعات کنترلی در شبکه هنگام استفاده از AODV کمتر از DSRاست. البته اگر بررسی را با جزئیات بیشتری انجام دهیم مشاهده می کنیم که طول قالب در بسته ی کنترلی AODV که مابین گره های واسط رد وبدل می شوند نیز از DSR کمتر است و این خود یعنی کمتر بودن سرباره های کنترلی در AODV نسبت به DSR . می دانیم هر چه اطلاعات گره ها راجع به موقعیت کلی شبکه بیشتر باشد نیاز به تبادل اطلاعات کنترلی کمتر پیش می آید پس مجهز نمودن گره ها به ادواتی چون GPS و استفاده از پروتکل های مبتنی بر موقعیت جغرافیایی می تواند سرباره های کنترلی را کاهش دهد. بعلاوه می توان با به کار گیری پردازنده های قوی تر وتجهیزاتی چون آنتن های هوشمند این سر باره ها را به حداقل رساند. نهایتا زمانی که اساسا پروتکل بر مبنای کنترل گردش بنا می شود از همان ابتدا کمینه سازی سرباره های کنترلی مهمترین هدف در انتخاب مسیر است .فلذا محاسبات زمانی در گره ها لحاظ می شود. [5 ] نتیجه کیفی مطالب فوق در شکل زیر نشان داده شده است. شکل(11). جهت فلش به سمت کاهش سربارهای کنترلی است.

شکل 11

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

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

نویسندگان: ابولفضل دادگرنیا ، سید علی مصباحی فرد ، محمد دخانی

مراجع

[1]A. Sergio Marti , B. T.J.Giuli C. Kevin Lai and D. Mary Baker,"Mitigating Routing Misbehavior in Mobile Ad Hoc Networks".In the 7th International Conference on Network Protocols(ICNP),1999.

[2]A. Mintao Wu, B.Winston K.G.Seah and C.Lawrence W.C.Wong, "A Link-Connectivity-Prediction-Based Location Aided Routing Protocol for Hybrid Wired-Wireless Networks".IEEE International Conference on Communications(ICC),2003.

[3]A. Young-Bae Ko and B. Nitin H.Vaidya., “Location Aided Routing(LAR) in mobile ad hoc network”

[4]Elizabeth M.Belding-Royer."Routing Approaches in Mobile Ad Hoc Networks". Ad Hoc Book Chapter 10.

[5] ابوالفضل دادگرنیا، سید علی مصباحی فرد، محمد دخانی ”ارائه ی سرویس مدیریت زمانی جهت بهبود عملکرد شبکه های بی سیم Ad Hoc "دهمین کنفرانس دانشجویی مهندسی برق ایران، دانشگاه صنعتی اصفهان،2007.

[6]A. Andreas Sawides and B. Mani B.Srivastمجازی و ... هستند.با توجه به گسترش روزافزون این شبکه ها در عرصه های مختلف لزوم طراحی بهینه ی پروتکل های مسیریابی بیش از پیش حائز اهمییت است.تاکنون پروتکل های مسیریابی زیادی برای شبکه های اقتضایی پیشنهاد شده است. هدف از طراحی این پروتکل ها کمینه سازی یک یا چند عامل محدود کننده راندمان شبکه(مثل محدودیت توان عملیاتی گره ها،سربارهای کنترلی،سربارهای پردازشی و ... )است.ما در این مقاله روی کمینه سازی سربارهای کنترلی متمرکز می شویم و یک پروتکل گردش گرا به نام FORP را با سه پروتکل معروف دیگر (DSR,AODV,LAR) مقایسه می کنیم.

كليد واژه : پروتکل های مسیریابی ، سربارهای کنترلی ، شبکه های اقتضایی ، کنترل گردش.

1-مقدمه:

شبکه های اقتضایی (Ad Hoc)نمونه ی نوینی از شبکه های مخابراتی بی سیم هستند که به خاطر مشخصات منحصر به فردشان امروزه بسیار مورد توجه قرار گرفته اند.در این شبکه ها هیچ پایگاه مبنا،تقویت کننده و مرکز سوئیچینگ ثابتی وجود ندارد بلکه این خود گره ها هستند که عملیات تقویت داده سوئیچینگ ومسیریابی را انجام می دهند.با توجه به تغییرات مداوم در توپولوژی شبکه به واسطه ی تحرک گره ها پروتکل های مسیریابی باید با اتخاذ نوعی استراتوژی سازگار این تغییرات را پشتیبانی کنند به نحوی که داده ی ارسالی به سلامت از مبدا به مقصد برسد.از اوایل دهه 80 میلادی تاکنون پروتکل های مسیریابی فراوانی برای شبکه های اقتضایی پیشنهاد شده است.این پروتکل ها رنج وسیعی از مبانی و روش های طراحی را شامل می شوند از یک تعریف ساده برای پروتکل های اینترنتی گرفته تا روش های سلسله مراتبی چندسطحه ی پیچیده.بسیاری از این پروتکل ها بر اساس فرض های ابتدایی ساده ای طراحی می شوند مثلا در بسیاری از این پروتکل ها تمام گره ها منابع و توانایی های یکسانی دارند به عنوان نمونه گره ها رنج ارسال یکسان دارند و پیوندها دوطرفه فرض می شوند البته پروتکل هایی هم هستند که عملاً با لینک های یک طرفه سروکار دارند.نهایتا اگرچه هدف بسیاری از پروتکل ها قابل استفاده بودن برای شبکه های بزرگ است اما معمولا و به طور میانگین برای 10 تا 100 گره طراحی می شوند. کمبود توان باتری،پهنای باند محدود،میزان خطای زیاد،تزاحم داده و تغییرات مداوم در توپولوژی شبکه از مشکلات اساسی شبکه های اقتضائی است.به دلیل همین محدودیت ها پروتکل های مسیریابی برای این گونه شبکه ها به گونه ای طراحی می شوند که حداقل یکی از عوامل زیانبار شبکه را کمینه سازند . به عنوان مثال برخی پروتکل ها صرفا بر مبنای توان باتری گره ها بنا می شوند،بسیاری دیگر کمینه سازی سربارهای پردازشی را مورد توجه قرار می دهند و در بسیاری دیگر اجتناب از حلقه(که خود عامل بسیاری از محدودیت ها در شبکه من جمله کاهش پهنای باند و ... است ) هدف طراحی است.اما دسته وسیعی از پروتکل ها نیز وجود دارند که به دنبال کمینه سازی سربارهای کنترلی هستند.ما در این مقاله ضمن توضیحی مختصر راجع به سه پروتکل معروف DSR,AODV,LAR در بخش های 3,2 و4 در بخش 5 پروتکلی گردش گرا به نام FORP را تشریح می کنیم.در نهایت در بخش 6 پروتکل های نامبرده را از نظر سربارهای کنترلی با هم مقایسه می کنیم. ‌

2-(DSR( Dynamic Source Routing

DSR یک پروتکل راکتیو است که می تواند شبکه های اقتضائی را بدون نیاز به جداول مسیریابی و به روز سازی آنها مدیریت کند.DSR به طور اخص برای شبکه های اقتضائی چند پرشه (multi hop) طراحی می شود.به منظور صرفه جوئی در پهنای باند فرایند مسیریابی تنها زمانی انجام می شود که نیاز باشد(مقتضی).در DSR فرستنده تمام مسیرهای منبع به مقصد را مشخص و آدرس تمام گره های میانی را در بسته ها ذخیره می کند.این پروتکل بر مبنای الگوریتم های موقعیت پیوند(link state) کار می کند یعنی هر گره قادر به ذخیره ی بهترین مسیر به مقصد است.همچنین اگر تغییری در شبکه رخ دهد تمام گره های شبکه از طریق انتشار کلی (flooding) از این تغییر مطلع می شوند.DSR شامل دو مکانیزم عمده می باشد که در زیر به بررسی آنها می پردازیم.

2-1-کشف مسیر

در شکل 1 اگر گرهS در حافظه ی خود مسیری به D داشته باشدو بخواهد با آن ارتباط برقرار کند بلافاصله از این مسیر استفاده می کند.اما اگر مسیری به D موجود نباشد مراحل کشف مسیر به قرار زیر آغاز می شود: گره S یک بسته درخواست مسیر (RREQ) به تمام گره ها می فرستد.اگر گره A درخواست مسیر را قبلا دریافت کرده باشد یا آدرسش در بایگانی مسیر موجود باشد این گره درخواست را حذف می کند.اگر گره A هدف کشف مسیر باشد گره یک بسته جواب به مسیر(RREP) به مبدا بر می گرداند.بسته RREPشامل بهترین مسیر از منبع به مقصد است وقتی منبع این بسته را دریافت کرد این مسیر را در حافظه مسیر خود ذخیره می کند تا متعاقبا از آن استفاده کند.در غیر این صورت گره A درخواست S را به همسایگان خود می فرستد.

JPG - 7.3 kb
شکل 1

2-2- نگهداری مسیر : در DSR هر گره مسئول تایید دریافت بسته توسط گره بعدی است و همچنین هر بسته تنها یک بار توسط هر گره ارسال می شود . اگر یک بسته به یک گره خاص نرسد فرایند ارسال تا زمانی معین ادمه می یابد . اگر دریافت بسته تایید نشد یک پیام خطای مسیر (RERR ) به منبع فرستاده می شود و مسیر مورد نظر از حافظه مسیر حذف می شود . سپس منبع از روی حافظه مسیر خود دنبال مسیر دیگری می گردد . و اگر مسیری در حافظه نباشد یک بسته درخواست مسیر انتشار می یابد .در شکل 2 اگر گره B بعد از چندین درخواست از C تاییدیه نگیرد یک پیام خطا به گره S (منبع) می فرستد.

شکل 2

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

3- (AODV:(Ad Hoc On demand Distance Vector

AODV یک پروتکل راکتیو است که مبنای آن بر DSDV استوار است که خود شامل یک پروتکل پیش فعال است و در سال 1997 معرفی شده است. این پروتکل برای شبکه هایی با چند ده تا چند صد گره طراحی شده است . یکی از جنبه های AODV استفاده از شماره ی رشته(توالی) در جدول هر گره است. این شماره رشته توسط گره مقصد تولید می شود ،شماره ی رشته هم در بسته درخواست مسیر و هم در بسته های پاسخ به مسیر گنجانده می شود و به گره های درخواست کننده فرستاده می شود .شماره رشته از اهمیت فوق العاده ای برخورداراست . زیرا باعث اجتناب از حلقه شده وبه سادگی قابل برنامه ریزی است . در دیگر گره ها نیز این شماره رشته به منظور به روز رسانی اطلاعات مسیر یابی استفاده می شود. اگر یک گره بین دو مسیر حق انتخاب داشته باشد مسیری را انتخاب می کند که شماره رشته آن بیشتر باشد.AODV با جداول مسیر یابی ساز گار است.بسته های درخواست مسیر ، جواب به مسیر و خطا در AODV نیز همانند DSR تعریف می شود. شکلهای 3و 4و 5 نحوه عملکرد AODV را نشان می دهند. در وحله اول S می خواهد با D ارتباط برقرار کند فلذا اقدام به انتشاربسته درخواست مسیر می کند تا مقصد رابیابد . این گره بسته درخواست مسیر را تولید می کند که شامل آدرس مقصد، شماره رشته و ID انتشار است. سپس آنرا به همسایگانش ارسال می کند

JPG - 11.5 kb
شکل 3

هر گره ی که این درخواست را دریافت می کند مسیری در جهت عکس به گره ارسال می کند ضمن اینکه اگر به مقصد دسترسی نداشته باشد درخواست را به سمت دیگر همسایگانش به پیش می راند. مسیر زمانی یافت می شود که RREQ به گره ی برسد که به مقصد دسترسی دارد و زمانی مسیر قابل بهربرداری است که RREP از D به S برسد ودر جدول مسیر یابی S نگاه داشته شود . پس از دریافت RREP توسط هر گره ، لازم است گره مورد نظر جدول مسیر یابی خود را به روز کند (بر اساس شماره رشته).

شکل 4

هم اکنون S می تواند با D ارتباط برقرار کند .

شکل 5

زمانی که در یک مسیر فعال پیوندی شکسته می شود یک پیام خطا (RERR) به دیگر گره ها ارسال می شود اگر گره ها مسیری شامل پیوند شکسته شده در جدول مسیر یابی خود دارند آن مسیر را حذف می کند و گره S بار دیگر RREQ را به همسایگانش می فرستد البته در این پروتکل هر گره ی که در مسیر قرار دارد می تواند مبادرت به یافتن مسیر به D کند . به چنین مکانیزمی تعمیر محلی مسیر می گویند. اجتناب از حلقه ، انتشار چند گانه اختیاری و کاهش سربار های کنترلی از مزایای این پروتکل و تاخیر درفرآیند کشف مسیر و ضرورت وجود پیوندهای دوطرفه جهت آشکار شدن پیوندهای یک طرفه از جمله معایب آن است.

4-پروتکل مسیر یابی به کمک مکان (LAR): (Location Aided -Routing)

LAR یک پروتکل مقتضی است که بر مبنای DSR بنا نهاده شده است.این الگوریتم از اطلاعات مکانی به منظور کاهش سربار در شبکه ی Ad Hoc استفاده می کند. عموما LAR برای اطلاعات مکانی از GPS استفاده می کند. با GPS گره ها مکان فیزیکی خود را می دانند. به منظور کاهش پیچیدگی پروتکل فرض می کنیم تمام گره ها موقعیت دقیق خود را می دانند یعنی تفاوت موقعیت دقیق گره و موقعیت اعلام شده توسط GPS در نظر گرفته نمی شود البته در[3] محاسبات دقیق نیز آورده شده است (با احتمال خطا در موقعیت انتخابی) هم چنین فرض بر این است که گره ها در صفحه حرکت می کنند(حرکت دوبعدی به جای سه بعدی) 4-1- منطقه مورد انتظار و منطقه درخواستی : منطقه مورد انتظار : در ابتدا فرض می کنیم S می خواهد D را پیدا کند و از قبل موقعیت آن (L) را میداند.سپس منطقه مورد انتظار مربوط به گره D از نقطه نظر گره S منطقه ای است که S انتظار دارد D در ان جا واقع باشد.اگر گره S سرعت حرکت D را بداند این سرعت را برای محاسبه وسعت منطقه مورد انتظار لحاظ می کند . اگر S هیچ اطلاعاتی راجع به D نداشته باشد منطقه مورد انتظار کل وسعت شبکه است و الگوریتم به شکل ابتدایی خود (انتشار کلی) تبدیل می شود. به طور کلی هر چه اطلاعات S راجع به D بیشتر باشد.منطقه انتظاری کوچکتر است. شکل 6 (الف) یک منطقه انتظاری دایروی را نشان می دهد حال آن که در شکل 6 (ب) با فرض این که S می داند D در جهت شمال حرکت می کند این ناحیه به یک نیم دایره تقلیل یافته است.

JPG - 3.6 kb
شکل 6
الف:S هیج اطلاعاتی راجع به جهت حرکت D ندارد ب: S می داند که D به سمت شمال حرکت می کند.

منطقه درخواستی: مجددا فرض میکنیم Sمیخواهد مسیری به D بیابد. گره S منطقه ای مثل شکل (6-الف) را به عنوان منطقه ی درخواستی مشخص میکند.سپس گره S مثل الگوریتم انتشاری اقدام به ارسال درخواست مسیر مینماید با این تفاوت که تنها گره هایی که در منطقه درخواستی قرار دارند این بسته را به پیش می رانند. اما مواردی پیش می آید که مجبوریم گره هایی که در خارج از منطقه در خواست هستند را به عنوان اعضای این منطقه لحاظ کنیم: اگر گره S در منطقه ی انتظاری گره D قرار نداشته باشد این منطقه انتظاری باید به منطقه درخواستی اضافه شود مانند شکل (7- الف).حال این سوال پیش می آید که آیا ناحیه نشان داده شده در شکل مذبور منطقه خوبی است.در شکل (7- ب) دیده می شود که تمام گره ها مابین D و S خارج از این ناحیه هستند لذا انتخاب این چنین ناحیه ای یافتن مسیر بین D,S را تضمین نمی کند.LAR این امکان را فراهم میکند تا با گسترش ناحیه مورد نظر مسیر یابی محقق شود . البته زمانی که منطقه درخواست را به شکل (7- ج) در نطر می گریم طبیعتا سر بار مسیر یابی افزایش می یابد.

JPG - 12.1 kb
شکل 7

4-2- عضویت در منطقه درخواست: الگوریتم LAR تقریبا مشابه به الگوریتم های مسیر یابی پخشی است. با این تفاوت که گره هایی که در منطقه درخواست نیستند بسته ها را پیش نمی رانند ، دو امکان متفاوت جهت مشخص کردن گره به عنوان عضو ناحیه وجود دارد:

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

شکل 8

روش دوم LAR : در این روش گره S از موقعیت گره D را می داند با دانستن این مختصه گره S فاصله خود از D رامحاسبه می کند(Dist D). در درخواست مسیر هم فاصله و هم مختصات مبدا و مقصد لحاظ می شود.حال هر گره که این درخواست را از S دریافت می کند فاصله خودش تا D را محاسبه میکند اگر این فاصله از Dist D بیشتر باشد درخواست حذف می شود و اگر کمتر باشد گره مختصه و فاصله خودش تا مقصد را به درخواست مسیر افزوده و آن را به سوی همسایگانش به پیش می راند ، با ادامه ی این فرآیند نهایتا D پیدا می شود. سپس D پیام پاسخ به مسیر برای S می فرستد شکل (9) این فرآیند را نشان می دهد.

شکل 9

- پروتکل مسیر یابی گردش گرا: FORP (Flow-Oriented Routing Protocol) FORP یک پروتکل مسیر یابی تک پخشه (unicnst) است. یک مسیر یابی تک انتشاره انتشار کلی تحت کنترل در شبکه است . اگر S بخواهد به D دسترسی داشته باشد ، بسته های داده شده را به همسایگانش می فرستد و هر گره ی که این بسته ها را دریافت می کند همین کار را انجام می دهد . به منظور جلوگیری از فرستادن بسته بیش از یک بار از شماره رشته استفاده می شود .لذا بعد از مدت زمانی خاص شبکه عاری از بسته ی P خواهد شد.وقتی P به D رسید مشخص می شود که S به D دسترسی دارد و دیگر بسته P توسط D ارسال نمی شود. وقتی S می خواهد داده ای به D بفرستد، جدول مسیر یابی را چک می کند ، اگر مسیر منقضی نشده ای یافت شود ار آن استفاده می کند در غیر این صورت پیام درخواست گردش را ارسال می کند تا D را بیابد در طول مسیر گره ها اطلاعات مربوط به خودشان را از روی GPS خوانده و به این پیام اضافه می کنند. حال مقصد باید بهترین مسیر را بر اساس معادله زیر پیدا کند (به شکل 10 دقت شود). Link Expirtion Time (LET)

شکل 10

- مقایسه پروتکل ها از نظر کنترل گردش: با توجه به مطالب فوق الذکر به وضوح دیده می شود که در پروتکل DSR علیرغم این که پروتکلی راکتیو است به خاطر تعدد پیغام هایی نظیر RERR,RREP,RREQو همچنین اطلاعاتی که گره ها به این پیغام ها اضافه می کند حجم تبادل اطلاعات کنترلی در شبکه زیاد است.از طرفی AODV اساسا پروتکلی است برگرفته از DSDV که خود بر مبنای الگوریتم بردار فاصله عمل می کند .حال آن که DSR بر اساس موقعیت پیوند بنا نهاده شده است فلذا همین جا می توان نتیجه گرفت حجم اطلاعات کنترلی در شبکه هنگام استفاده از AODV کمتر از DSRاست. البته اگر بررسی را با جزئیات بیشتری انجام دهیم مشاهده می کنیم که طول قالب در بسته ی کنترلی AODV که مابین گره های واسط رد وبدل می شوند نیز از DSR کمتر است و این خود یعنی کمتر بودن سرباره های کنترلی در AODV نسبت به DSR . می دانیم هر چه اطلاعات گره ها راجع به موقعیت کلی شبکه بیشتر باشد نیاز به تبادل اطلاعات کنترلی کمتر پیش می آید پس مجهز نمودن گره ها به ادواتی چون GPS و استفاده از پروتکل های مبتنی بر موقعیت جغرافیایی می تواند سرباره های کنترلی را کاهش دهد. بعلاوه می توان با به کار گیری پردازنده های قوی تر وتجهیزاتی چون آنتن های هوشمند این سر باره ها را به حداقل رساند. نهایتا زمانی که اساسا پروتکل بر مبنای کنترل گردش بنا می شود از همان ابتدا کمینه سازی سرباره های کنترلی مهمترین هدف در انتخاب مسیر است .فلذا محاسبات زمانی در گره ها لحاظ می شود. [5 ] نتیجه کیفی مطالب فوق در شکل زیر نشان داده شده است. شکل(11). جهت فلش به سمت کاهش سربارهای کنترلی است.

شکل 11

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

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

نویسندگان: ابولفضل دادگرنیا ، سید علی مصباحی فرد ، محمد دخانی

مراجع

[1]A. Sergio Marti , B. T.J.Giuli C. Kevin Lai and D. Mary Baker,"Mitigating Routing Misbehavior in Mobile Ad Hoc Networks".In the 7th International Conference on Network Protocols(ICNP),1999.

[2]A. Mintao Wu, B.Winston K.G.Seah and C.Lawrence W.C.Wong, "A Link-Connectivity-Prediction-Based Location Aided Routing Protocol for Hybrid Wired-Wireless Networks".IEEE International Conference on Communications(ICC),2003.

[3]A. Young-Bae Ko and B. Nitin H.Vaidya., “Location Aided Routing(LAR) in mobile ad hoc network”

[4]Elizabeth M.Belding-Royer."Routing Approaches in Mobile Ad Hoc Networks". Ad Hoc Book Chapter 10.

[5] ابوالفضل دادگرنیا، سید علی مصباحی فرد، محمد دخانی ”ارائه ی سروی

[6]A. Andreas Sawides and B. Mani Bava."Location Disvovery".Ad Hoc Book Chapter 8

س مدیریت زمانی جهت بهبود عملکرد شبکه های بی سیم Ad Hoc "دهمین کنفرانس دانشجویی مهندسی برق ایران، دانشگاه صنعتی اصفهان،2007.

[6]A. Andreas Sawides and B. Mani Bava."Location Disvovery".Ad Hoc Book Chapter 8

+ نوشته شده در  دوشنبه 8 تیر1388ساعت 15:46  توسط حسین زهره وند |