پروژه بررسی شبكه بی سیم Adhoc

پروژه بررسی شبكه بی سیم  Adhoc  در 85 صفحه ورد قابل ویرایش

مقدمه

دوروش برای ارتباط بی سیم بین كامپیوترهای متحرك وجود دارد .

چرا نیاز به طراحی پروتكلهای مسیر یابی جدیدی برای شبكه های Adhoc وجود دارد ؟‌

از دیگر مواردی كه می توان به عنوان دلایل نیاز به طراحی پروتكلهای مسیریابی جدید برای شبكه‎های Adhoc به آنها اشاره كرد عبارتند از :‌

به طور كلی اهداف طراحی پروتكلهای مسیریابی این است كه پروتكلی ساخته شود كه :‌

تقسیم بندی پروتكلهای مسیریابی در شبكه های Adhoc

-مسیریابی Link State در مقابل مسیریابی DisTance Vector

Event – driven Update در مقابل Periodical Update

-ساختارهای مسطح (Flat ) در مقابل ساختارهای سلسله مراتبی (‌Hierarchical‌)

-محاسبات غیر متمركز(Decentralizad) در مقابل محاسبات توزیع شده (Distributed)

-Source Routing درمقابل hop- by-hop Routing

-مسیرهای منفرد در مقابل مسیرهای چندگانه

مسیریابی ProActive  در مقابل مسیریابی ReAvtive

( DSDV )Distance Sequence Vector Ronting Protocol

شكل زیر مثالی را از یك شبكه Adhoc نشان می دهد .

جدول مسیریابی درنود H6

-انواع بسته های بروز رسانی اطلاعات مسیریابی

پاسخ به تغییرات توپولوژی

مشكلات پروتكل DSDV

•كاهش نوسانات

شكل زیر مثالی از دریافت مسیرهای نوسان دار را نشان می دهد .

•لینكهای یكطرفه

شكل زیر از یك شبكه Adhoc با لینكهای یكطرفه و دوطرفه است .

Adhoc On – Demard Distance vector Routing

- پروسه كشف مسیر (Route Discovery)

-پروسه نگهداری مسیر

حل مشكل شمارش تا بی نهایت

Dynamic Source Routing (DSR )

عملكرد كلی پروتكل DSR

-پروسه كشف مسیر

- پروسه نگهداری مسیر

بهینه سازی

1- استفادة‌ كامل از Rout cache

2- استفاده از تكنیك Piggy backing در كشف مسیر

-بهینه سازی بر روی مدیریت خطاها

Optimized   link State  Routing  Protocol (OLSR)

-عملكرد پروتكل OLSR

-ارسال مجدد چند نقطه ای (Multipoint Relay)

-شناسایی همسایه

- انتخاب MPR‌ ها

Zone Routing Protocol (ZRP)

-انگیزه به وجود آمدن پروتكل ZRP

-معماری ZRP :

اجزای مسیریابی در پروتكل ZRP شامل پروتكلهای IARP

شكل زیر ارتباط بین اجزا را در پروتكل ZRP نشان می دهد .

-مسیریابی در پروتكل ZRP

-پروسه نگهداری مسیر

Zone Based Hierarchcal Link State –ZHLS

خصوصیات ZHLS

Cluster Switch Gateway Protocol (CGSR)

-عملكرد كلی پروتكل CGSR

شكل زیر مثالی از یك مسیریابی CGSR را نشان می دهد .

Fisheye State Routing(FSR)

عملكرد پروتكل FSR :

شكل زیر كاربرد یك fisheye را در شبكه بی سیم متحرك نشان می‎دهد .

-پروتكل GSR

درجه مشاركت نودها در مسیریابی

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

دوروش برای ارتباط بی سیم بین كامپیوترهای متحرك وجود دارد .

1-  استفاده از یك زیر ساخت ثابت كه توسط یك Acces point خارج شد آنگاه در محدوده رادیویی Wireless Access point ها فراهم می آید . كه در این گونه شبكه ها ،‌ نودهای متحرك از طریق Access Point ها با یكدیگر ارتباط برقرار می كنند و هنگامیكه یك نود از محدوده رادیویی Access Pointدیگری قرار می گیرد . مشكل اصلی در اینجا هنگامی است كه یك اتصال باید از یك Access Point به Access Point دیگری تحویل داده شود ،‌ بدون آنكه تاخیر قابل توجهی به وجود آید ویا بسته ای گم شود .

2-  شكل دادن یك شبكه بی سیم Adhoc در بین كاربرانی است كه می خواهند با هم ارتباط داشته باشند . این گونه شبكه ها زیر ساخت ثابتی ندارند و كنترل كننده و مركزی نیز برای آنها وجود ندارد .

شبكه های بی سیم Adhoc از مجموعه ای از نودهای متحرك تشكیل شده اند كه این نودها قادرند به طور آزادانه و مداوم مكانشان را در شبكه تغییر دهند . نودهای موجود در شبكه Adhoc همزمان به عنوان client و مسیریاب عمل می كنند و  با توجه به عدم وجود ساختار ثابت در این گونه شبكه‎ها ،‌ نودها مسئولیت مسیریابی را برای بسته هایی كه می خواهند در شبكه ارسال شوند بر عهده دارند و در انجام این امر با یكدیگر همكاری می كنند .

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

چرا نیاز به طراحی پروتكلهای مسیر یابی جدیدی برای شبكه های Adhoc وجود دارد ؟‌

در شبكه های سیم دار تغییرات در توپولوژی شبكه بندرت اتفاق می افتد . بیشتر host ها و نودهای دیگر در یك جای مشخصی در شبكه قرار دارند ویك شكستگی در لینك زمانی اتفاق می‎افتد كه یك قطع فیزیكی نظیر fail‌ شدن host  و یا خسارت فیزیكی كامل اتفاق بیفتد . برای این نوع شبكه های سیم دار با ساختار ثابت یك الگوریتم مسیریابی كلاسیك به خوبی كار می كند.

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

از دیگر مواردی كه می توان به عنوان دلایل نیاز به طراحی پروتكلهای مسیریابی جدید برای شبكه‎های Adhoc به آنها اشاره كرد عبارتند از :‌

-    پروتكلهای مسیریابی شبكه های سیم دار بار محاسباتی بسیار زیادی را به صورت مصرف زیاد حافظه و همچنین مصرف زیاد انرژی بر روی هر كامپیوتر قرار می دهند .

-    پروتكلهای مسیریابی مورد استفاده در شبكه های سیم دار از مشكلات به وجود آوردن حلقه‎های كوتاه مدت وبلند مدت رنج می برند .

-    متدهایی كه برای حل مشكلات ناشی از بوجود آوردن حلقه ها در پروتكلهای مسیریابی سنتی استفاده می شوند در شبكه های Adhoc عملی نیستند .

این تفاوتها بین شبكه های سیم دار و بی سیم به راحتی آشكار می كند كه یك پروتكل مسیریابی برای شبكه های Adhoc باید یكسری از مشكلات اضافه تری را حل نماید كه این مشكلات در شبكه های سیم دار وجود نداشته است .

در زیر لیستی از مواردی را كه یك پروتكل مسیریابی باید آنها را مدنظر قرار دهد ذكر گردیده كه بعضی از این خصوصیات مهمتر از خصوصیات دیگر هستند .

به طور كلی اهداف طراحی پروتكلهای مسیریابی این است كه پروتكلی ساخته شود كه :‌

1-   وقتی كه توپولوژی شبكه گسترش می یابد این پروتكل نیز بتواند همچنان مسیریابی را انجام دهد .

2-   زمانی كه تغییراتی در توپولوژی شبكه به وجود می آید این پروتكل سریعاً قادر به پاسخگویی باشد .

3-   مسیرهایی را فراهم كند كه بدون حلقه باشد .

4-   تاخیر را به حداقل رساند (‌باانتخاب مسیرهای كوتاه )‌

5-   برای اجتناب از تراكم چندین مسیر را از مبدأ به مقصد فراهم نماید .

پروتكل طراحی شده برای مسیریابی در یك شبكه Adhoc باید خصوصیات زیررا دارا باشد .

1-   اجرای غیر مركزی داشته باشد ،‌ به این معنی كه نباید به یك نود مركزی وابسته باشد .

2-   استفاده از پهنای باند را كار اگرداند (overhead مسیریابی را می نیمم كند )

3-   هم از لینكهای یكطرفه و هم از لینكهای دو طرفه استفاده كند .

تقسیم بندی پروتكلهای مسیریابی در شبكه های Adhoc 

چندین معیار متفاوت برای طراحی و كلاس بندی پروتكلهای مسیر یابی در شبكه های Adhoc وجود دارد . به عنوان مثال اینكه چه اطلاعات مسیریابی مبادله می شوند ؟ چه زمانی و چگونه این اطلاعات مبادله می‎شوند ؟‌ چه زمانی و چگونه مسیرها محاسبه می شوند .

 كه ما در این بخش در مورد هر یك از این معیارها مطالبی را بیان خواهیم كرد .

دراین فصل پروتكل دیگری برای مسیریابی در شبكه های Adhoc مورد بررسی قرار می‎گیرد . این پروتكل در دسته پروتكلهای ProActive قرار دارد و مسیریابی آن شبیه پروتكل Link State  می‎باشد . مسیریابی در FSR بصورت مسطح انجام می‎گیرد .

در این پروتكل هر نود دارای 3 جدول و یك لیست می‎باشد .

1- لیست همسایگان    A_i

2- جدول توپولوژی       TT_i  

3- جدول hop‌ بعدی  NEXT_I

4- جدول فاصله        D_i

A_i از مجموعه ای از نودها كه در مجاورت نود ناقرار دارند تشكیل شده است . هر مقصدی نظیر j‌ دارای یك مدخل در جدول TT_i است كه شامل 2 قسمت می‎باشد .

TT_iSEQ(j) وTT_iLS(j) .

TT_iLS(j) اطلاعات Link State ی را كه توسط نود j‌ گزارش شده است نشان می‎دهد .

TT_iSEQ(j) ، یك نشانه زمانی است كه مشخص كننده زمان تولید اطلاعات Link State توسط نود j می‎باشد . به طور مشابه برای هر مقصدی مانند j ، NEXT_I(j)  مشخص كننده hop‌ بعدی برای forward كردن بسته هایی به مقصد j (روی كوتاهترین مسیر ) می‎باشد و D_I(j) نیز فاصله را روی كوتاهترین مسیر از i به j نشان می‎دهد .

یك فانكشن وزن ،‌  نیز برای محاسبه فاصله هر Link استفاده می‎شود . از آنجاییكه می‎نیمم hop ( كوتاهترین مسیر) تنها هدف در این پروتكل است این فانكشن وزن در مواقعی كه 2 نود دارای اتصال مستقیم باشند مقدار 1‌ را برمی گرداند و در غیر این صورت مقدار  را برخواهد گرداند .

عملكرد پروتكل FSR :

چشم یك ماهی Pixed هایی را كه نزدیك نقطه كانونی اش قرار دارند با جزئیات بیشتری می بیند  واین جزئیات با افزایش فاصله از نقطه كانونی كاهش می یابد ، فلسفه نام گذاری پروتكل FSR نیز به همین دلیل می‎باشد .

در روش Fisheye نیز هر نود اطلاعات دقیقی را در مورد فاصله و كیفیت مسیر در ارتباط با همسایگان بلامانع اش نگهداری می‎كند ولی هر چه فاصله بیشتر می‎شود جزئیات این اطلاعات نیز كمتر می‎شود .

FSR از نظر كاركرد بسیار شبیه پروتكل مسیریابی Link State است . تفاوت اصلی بین آنها در طریقه ای است كه اطلاعات مسیریابی منتشر می‎شوند ، در پروتكل Link State بسته های Link State در كل شبكه جاری می‎شوند در حالیكه در FSR ، بسته های Link State در كل شبكه جاری نمی‎شوند ، به جای آن این بسته ها فقط به همسایگان محلی نود مربوطه ارسال می‎شوند . از طریق این پروسه تبادلی ، مدخلهای جدول كه SegNo شان بزرگتر باشد جایگزین مدخلهایی می‎شوند كه SegNo شان كوچكتر است .

تبادل دوره ای جداول در FSR با تبادل بردارها در الگوریتم DSDV شباهت دارد . در آنجا نیز فواصل بر اساس نشانه زمانی ویا SegNo ها بروز رسانی می‎شوند . اگر چه پروتكل FSR بر پروتكل DSDV برتری دارد و علاوه بر این ، شبیه پروتكلهای Link State هر نود یك دید كلی از توپولوژی شبكه داردو كوتاهترین مسیرها بر اساس این اطلاعات محاسبه می‎شوند .

در محیط های بی سیم ، لینكهای رادیویی بین نودهای متحرك ممكن است قطع و دوباره وصل شود ، و این كار احتمالاً بسیار زیاد اتفاق می افتد در این گونه مواقع پروتكل Link State یك بسته Link State را برای هر یك از این تغییرات در شبكه جاری می‎كند و با اینكار سرباركاری زیادی را به وجود می‎آورد . در حالیكه پروتكل FSR با انتشار دوره ای از وقوع این مشكل اجتناب كرده و به مقدار زیادی از به وجود آمدن سرباركاری می كاهد .

هنگامیكه سایزشبكه بزرگ می‎شود ، پیامهای بروز رسانی مقدار زیادی از پهنای باند را مصرف می‎كنند كه این بستگی به دوره Update دارد . برای كاهش سایز بسته های بروز رسانی ، بدون اینكه تاثیری در دقت مسیریابی داشته باشد از تكنیك fisheye استفاده می‎شود .