پایان نامه کارشناسی_مسیریابی مبتنی بر ناحیه بندی در شبکه های Ad Hoc

پایان نامه کارشناسی_مسیریابی مبتنی بر ناحیه بندی در شبکه های Ad Hoc

 مسیریابی مبتنی بر ناحیه بندی در شبکه های

Ad Hoc

فهرست مطالب

پیشگفتار.............................................................................................................................................................1

فصل اول .............................................................................................................2

شبکه‌های Ad Hoc...........................................................................................................................................2

1-1 تقسیم‌بندی شبکه‌های بی‌سیم ..................................................................................................................2

1-2 مروری بر پروتکلهای مسیریابی در شبکه‌های MANET ...........................................................6
1-2-1 الگوریتمهای مسیریابی مسطح.............................................................................................................6

1-2-1-1 پروتکلهای مسیریابی Table Driven...............................................................................................7

1-2-1-1-1  پروتکل مسیریابی DSDV ............................................................................................................8

1-2-1-1-2 پروتکل مسیریابی WRP .................................................................................................................8

1-2-1-2 پروتکلهای مسیریابی on-Demand .................................................................................................9

1-2-1-2-1 پروتکل مسیریابی AODV ..........................................................................................................10

1-2-1-2-2 پروتکل مسیریابی DSR ...............................................................................................................12

1-2-1-2-3 ظرفیت شبکه های بی‌سیم و محدودیت الگوریتمهای On-Demand ........ ....................14

1-2-2 الگوریتمهای مسیریابی سلسله‌مراتبی .........................................................................................15

1-2-2-1 مفهوم خوشه‌یابی ...................................................................................................................................18

1-2-2-2 مزایای استفاده از خوشه‌یابی ..............................................................................................................20

1-2-2-3 الگوریتمهای مسیریابی سلسله‌مراتبی مبتنی بر خوشه‌یابی .........................................................22

فصل دوم ..........................................................................................................................................................25

عناصر مورد استفاده جهت شبیه‌سازی شبکه‌های MANET........................................25

2-1 تکنولوژی بی‌سیم مورد استفاده در شبیه سازی شبکه های  Ad Hoc ............................25

2-2 مدلهای تحرک .............................................................................................................................................30

2-2-1 مدل‌های تحرک تصادفی .........................................................................................................................31

2-2-2 مدل تحرک با وابستگی لحظه‌ای ...........................................................................................................32

2-2-3 مدل تحرک با وابستگی فضایی ..............................................................................................................33

2-2-4 مدلهای تحرک با محدودیت جغرافیایی ...............................................................................................35

2-2-5 خصوصیات مدل تحرک Random Waypoint ...........................................................................35

2-3 ابزار شبیه‌سازی ........................................................................................................................................38

فصل سوم .......................................................................................................................................................42

خوشه‌یابی ..........................................................................................................................................................42

3-1 مروری بر الگوریتمهای خوشه‌یابی .....................................................................................................42

3-2 پارامترهای کارایی در روشهای خوشه‌یابی ...................................................................................50

3-3 الگوریتم خوشه‌یابی پیشنهادی ........................................................................................................52

3-3-1 تشخیص گره‌های همسایه .....................................................................................................................54

3-3-2 شکل گیری خوشه‌ها ..............................................................................................................................55

3-3-3 پیکربندی مجدد خوشه‌ها .....................................................................................................................58

3-3-4 ارزیابی کارایی ..........................................................................................................................................65

فصل چهارم.................................................................................................................................................77

نتیجه‌گیری و پیشنهاد برای آینده ....................................................................................................77

ضمیمه 1 ( واژه‌نامه ) ..................................................................................................................................80.

ضمیمه 2 ( عبارتهای اختصاری ) .......................................................................................................82

مراجع ................................................................................................................................................................86

مقاله خلاصه پایان نامه.................................................................................................................89

پیشگفتار

امروزه شبکه‌های بی‌سیم به دلیل کاربردهایی که دارد و همچنین سرویسهایی که ارائه می‌دهد، رشد چشمگیری داشته است. این شبکه‌ها در حال توسعه سریعی هستند و سرویسهای ارائه شده هم مرتباً بیشتر و بهتر می‌شود، در آینده‌ای نه چندان دور، تکنولوژی اطلاعات بر پایه مخابرات بی‌سیم خواهد بود. از آنجاییکه ایجاد شبکه با زیرساخت باعث محدودیت در شبکه‌های موبایل و سلولی معمولی خواهد کرد؛ لذا شبکه‌های بدون زیر ساخت می‌تواند ایدة خوبی برای ادامه مخابرات بی‌سیم باشد. شبکه‌های ادهاک، بدلیل عدم نیاز به زیرساختار، محدودیت شبکه‌های موبایل را مرتفع خواهد کرد.

 شبکه‌های Ad–hoc برای اولین بار توسط وزارت دفاع آمریکا در سیستم‌های نظامی و عملیاتی خود مورد استفاده قرار گرفته است. لیکن از سال 1970 بطور عمومی مورد استفاده میباشد.

در این پروژه هدف ارائه الگوریتم مسیریابی پیشنهادی مبتنی بر خوشه یابی می باشد.

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

فصل اول

شبکه‌های Ad Hoc

1-1 تقسیم‌بندی شبکه‌های بی‌سیم[1]

شبکه های بی‎سیم را از نظر معماری می توان به دو گروه اصلی تقسیم بندی نمود:

الف) شبکه های دارای زیرساخت[2]

مسیریابهایی که در این نوع شبکه‌ها مورد استفاده قرار می‌گیرند، اصطلاحاً به ایستگاه‌های ثابت شهرت دارند. این ایستگاههای پایه‌ای قابلیت حرکت ندارند، با روشهای مختلف و با امکانات سرعت بالا به یکدیگر متصل هستند. هر واحد متحرک در زمان برقراری ارتباط و نیز ردو بدل کردن اطلاعات، به نزدیکترین ایستگاه پایه‌ای متصل می شود. در نتیجه ارتباطات بی‎سیم در این نوع شبکه‌ها، بر اساس ارتباط سیمی[3] بین ایستگاه های پایه‌ای صورت می پذیرد. این شبکه‌ها همچنین به شبکه‌های بی‎سیم یک‌گامی[4] نیز شهرت دارند. شبکه‌های مخابرات سلولی و شبکه‌های PCS[5] مثالهایی از این نوع شبکه‌های بی‌سیم هستند. در شبکه‌های یک‌گامی گره‌های متحرک همواره تحت پوشش ایستگاههای پایه قرار دارند و در نتیجه ارتباط پیوسته‌ای با ایستگاههای پایه دارند.

شکل 1-1  مثالی از شبکه‌های دارای زیرساخت

ب) شبکه های فاقد زیرساخت[6]

در این شبکه ها که به شبکه های MANET[7] نیز شهرت دارند، هیچ زیر ساخت از پیش تعریف شده ای برای برقراری ارتباط بین گره ها وجود ندارد. هر گره قابلیت مسیریابی را داراست در عین حال، قادر است در هر جهتی حرکت کند و همچنین به گره های دیگر نیز متصل شود. به همین دلیل، اطلاعات ارسالی از یک گره به گره دیگر بدلیل فاصله دو گره مزبور ممکن است در صورت نیاز از چند گره دیگر عبور کند. درنتیجه، این شبکه ها را شبکه های بی‎سیم چندگامی[8] نیز می‌نامند. در این پروژه، این دسته از شبکه‌های بی‌سیم مورد بحث و بررسی قرار می گیرند.

شکل 1-2 نمونه‌ای از شبکه‌های فاقد زیر ساخت

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

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

شبکه‌های موسوم به PRNET[9] که در سال 1973 توسط DARPA[10] طراحی و مورد استفاده قرارگرفته‌اند ]1[ ، اولین شبکه‌های پیشنهادی از نوع MANET به شمار می‌روند. هدف از طراحی این شبکه، فراهم آوردن ارتباط کامپیوتری بین ترمینالهای متحرک بود. این شبکه درحقیقت به یک محیط برای تحقیقات و همچنین توسعه پروتکلهای مسیریابی شبکه‌های MANET تبدیل شد. شبکه‌های HF ITF نمونه دیگری از شبکه‌های MANET هستند که با ارائه یک الگوریتم مسیریابی توزیعی و سلسله‌مراتبی طراحی شدند. اکنون با ارائه فناوریهای مختلف بی‌سیم و وفور کاربرد آنها، شبکه‌های MANET، بیشتر مورد توجه محققین قرارگرفته‌اند. با گسترش تحقیقات در مورد شبکه‌های MANET ، IETF گروه کاری MANET را مسؤل تدوین استاندارد های مربوط به این شبکه‌ها نموده‌است.

خصوصیات مهم شبکه های ad-hoc را می توان به صورت زیر برشمرد ]3 [:

• توپولوژی شبکه به دلیل حرکت گره‌ها و همچنین مشکل توان در گره‌ها، می‌تواند به شدت متغیر باشد.
• به دلیل محدودیت در توان پراکنشی گره‌ها، اطلاعات ارسالی ممکن است از چند گره میانی عبور کند.
• منابع در شبکه‌های ad-hoc کاملاً محدود هستند؛ این منابع عبارتند از: پهنای باند کانال، منابع گره مانند توان محاسباتی[11]، ظرفیت ذخیره سازی[12] و توان باتری.
• به دلیل حرکت گره‌ها، توپولوژی شبکه دائماً در حال تغییر است و پروتکل مسیریابی
  باید از این تغییرات آگاه باشد. بحث اصلی، یافتن پروتکلهای مسیریابی دینامیکی است که در چنین محیطی، قادر به یافتن مسیر مناسب جهت برقراری ارتباط و تبادل اطلاعات بین دو گره باشند.

1-2 مروری بر پروتکلهای مسیریابی در شبکه‌های MANET

دراین قسمت مروری خواهیم داشت بر الگوریتمهای مسیریابی که تاکنون جهت شبکه‌های MANET ارائه‌شده‌اند. شکل 1-3 نشان‌دهنده تقسیم‌بندی الگوریتمهای ارائه شده می‌باشد ]2[.

شکل 1-3  تقسیم‌بندی پروتکلهای مسیریابی شبکه‌های MANET

1-2-1 الگوریتمهای مسیریابی مسطح[13]

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

-        پروتکلهای مسیریابی Table-driven (Proactive)

-        پروتکلهای مسیریابی On-Demand (Reactive)

1-2-1-1 پروتکلهای مسیریابی Table Driven   

این دسته از پروتکلهای مسیریابی که در ابتدای مطرح شدن شبکه‌های MANET ارائه‌شده‌‌اند، بر روشهای مسیریابی معمول در شبکه‌های ثابت، مانند روشهای DV[14] و LS[15] تکیه می‌کنند. در نتیجه مشابه الگوریتمهای مزبور، در هر گره جداولی از اطلاعات مربوط به مسیریابی نگهداری میشوند. با توجه به تحرک گره‌ها و تغییر توپولوژی شبکه، که مهمترین تفاوت شبکه‌های MANET و شبکه‌های ثابت می‌باشد، اطلاعات موجود در این جداول با هر تغییر در شبکه باید اصلاح شوند تا از هماهنگی[16] جداول در گره‌های مختلف اطمینان حاصل شود. عموماً در این دسته از پروتکلهای مسیریابی، اطلاعات مسیریابی توسط هر گره بصورت دوره‎ای و در زمانهای مشخص به دیگر گره‌ها بصورت بسته‌های حاوی اطلاعات کنترلی ارسال می‎شود. پروتکلهای مسیریابی که در این گروه قرار می‌گیرند، بر حسب تعداد جداول و اطلاعاتی که در این جداول قرار می گیرند و همچنین از لحاظ روش ارسال اطلاعات مسیریابی به دیگر گره‌ها، تقسیم بندی می شوند.

کلیه پروتکلهای مسیریابی که بر اساس الگوریتمهای DV عمل می کنند، از نوع پروتکلهای Table-Driven محسوب می شوند.  نقطه ضعف عمده این الگوریتمها این است که سرعت همگرایی نسبت به تغییرات شبکه که از تحرک گره‌ها ناشی میشود پایین است.

در ادامه به شرح برخی از پروتکلهای Table – Driven می پردازیم.

1-2-1-1-1  پروتکل مسیریابی DSDV

DSDV  یک نسخه بهبود یافته از DBF است. درDSDV، هیچگاه حلقه رخ نخواهد داد. اطلاعاتی که در هر گره نگهداری میشود، شامل آدرس گره‌ها و همچنین تعداد گره‌های میانی جهت دسترسی به آن گره است. هر سطر این جدول با یک عدد شمارشی[17] علامت گذاری میشود. این اعداد جهت تشخیص مسیرهای جدید از مسیرهای قدیمی و خارج از رده[18] مورد استفاده قرار می‌گیرند تا از تشکیل حلقه جلوگیری به عمل آید. جداول مسیریابی به صورت دوره‎ای و جهت ایجاد سازگاری بین گره‌های شبکه به دیگر گره‌ها ارسال می شوند. این امر باعث ایجاد ترافیک نسبتاً زیادی در شبکه می شود. جهت تعدیل و کاهش اثرات این ترافیک، دو نوع بسته کنترلی، جهت ارسال تغییرات این جداول به دیگر گره‌های شبکه مورد استفاده قرار می گیرند:

الف) Full Dump : این بسته ها حاوی کلیه اطلاعات مسیریابی هستند.

ب)Incremental Packets : این بسته ها صرفاً اطلاعاتی را حمل می کنند که از زمان ارسال آخرین بسته Full Dump، تغییر کرده‌اند. در نتیجه هر گره باید جدولی نیز داشته باشد تا اطلاعات Incremental را نگهداری نماید.

1-2-1-1-2 پروتکل مسیریابی WRP

دراین روش هدف نگهداری اطلاعات مسیریابی در کلیه گره‌های شبکه است. هر گره باید 4 جدول در حافظه خود نگهداری کند: جدول فاصله[19]، جدول مسیریابی[20]، جدول هزینه اتصال[21] و جدول ارسال مجدد پیام[22] .

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

گره‌ها با ردو بدل شدن acknowledgement و همچنین دیگر پیامها، از حضور همسایگان خود مطلع میشوند. زمانیکه یک گره اطلاعاتی برای ارسال ندارد، باید بصورت دوره‎ای پیام Hello ارسال کند تا از درستی اتصالات خود اطمینان حاصل نماید.

همچنین با دریافت این پیام از یک گره جدید، گره‌های دیگر آدرس این گره را در جدول مسیریابی خود قرار می‎دهند. در روش WRP، از آنجائیکه سازگاری اطلاعات هر گره با اطلاعات ارسالی از گره‌های همسایه دائماً برقرار میشود، مسأله Count–to–infinity رخ نخواهد داد و این امر نهایتاً از بروز حلقه جلوگیری خواهد کرد. همچنین، در صورت بروز خرابی در یک اتصال، همگرایی مسیر سریعا صورت خواهد پذیرفت.

1-2-1-2 پروتکلهای مسیریابی on-Demand

الگوریتمهای مسیریابی مانند AODV ،DSR ABR ، TORA ،RDMAR و WAR در این گروه قرار می‌گیرند. در این دسته از پروتکلها، یک مسیر جدید فقط در صورتی ایجاد خواهد شد که گره مبدا بدان نیاز داشته باشد. هدف اصلی از ارائه این دسته از پروتکلها، کاهش بار ترافیک کنترلی ناشی از مسیریابی در شبکه است. بار زیاد ترافیک مسیریابی در شبکه‌های با پهنای باند کم، می تواند اثرات منفی زیادی بر روی کارائی این دسته از شبکه‌ها داشته باشد. زمانیکه یک گره، مسیری به گرة مقصد نیاز داشته باشد، فرایند پیدا کردن مسیر[24] را شروع خواهد کرد. این فرایند زمانی به انتها می رسد که یک مسیر جدید پیدا شود و یا اینکه کلیه مسیرهای ممکن امتحان شده باشند. اگر در این فرایند، مسیر جدیدی پیدا شد، فرایند نگهداری مسیر[25] باید این مسیر را نگهداری نماید. این نگهداری تا زمانی انجام خواهد شد که گره مقصد دیگر قابل دستیابی نباشد و یا اینکه مسیر دیگر مورد نیاز نباشد ]3[. در این قسمت به بیان برخی پروتکلهای on-Demand موجود می پردازیم:

1-2-1-2-1 پروتکل مسیریابی AODV    

AODV ]7و8[ مشابه با DSDV طراحی شده‌ است. تفاوت اصلی AODV با DSDV در این است که بر خلاف DSDV، فهرست کامل مسیرها نگهداری نمیشود ]3[. در این الگوریتم، در هر گره فرایند یافتن مسیر مطابق شکل 3 با پراکنش کردن یک درخواست مسیر RREQ به گره‌های همسایه آغاز میشود. گره‌های همسایه نیز پس از ذخیره کردن مشخصات فرستنده RREQ , این بسته را به دیگر گره‌های همسایه خود ارسال مینمایند. این عمل تا آنجا ادامه می‎یابد که گره مقصد و یا یکی از گره های میانی که مسیر نسبتاً جدیدی به گره مقصد دارد، بسته را دریافت نماید. مسیر نسبتا جدید[26]، مسیری است که عدد شمارشی آن، بزرگتر یا مساوی عدد موجود در RREQ باشد. در اینجا، گره مقصد یا گره میانی حاوی مسیر مطابق شکل 1-4، با ارسال یک تقاضای پاسخ RREP به گره همسایه‌ای که RREQ را از آن دریافت کرده است، به این درخواست پاسخ می دهد.

شکل 1-4 (الف) ارسال RREQ  در الگوریتم AODV

شکل 1-4 (ب) ارسال RREP در الگوریتم AODV

در AODV ، اطلاعات ثبت شده در جدول در یک محدوده زمانی معتبر هستند و پس از انقضای این زمان، از درجه اعتبار ساقط می‌شوند ]4[. این امر با راه اندازی یک زمانبند (timer) به اعضای اطلاعات جدید صورت می پذیرد. اگر گره مبدا حرکت نماید و از محل قبلی خود جابجا شود، باید قادر باشد که فرایند یافتن مسیر را مجدداً شروع نماید اگریکی از گره‌های میانی در مسیر تعیین شده حرکت نماید، همسایه بالایی (Upstream) از این امر مطلع و یک پیام که نشان دهنده خرابی اتصال است به کلیه همسایه‌های خود ارسال می‌نماید تا به همگی اطلاع دهد که آن قسمت از مسیر را از جداول خود حذف نمایند. گره‌های همسایه سطح بالایی هم به نوبه خود این عمل را تکرار می کنند تا جایی که این پیام در نهایت به مبدا برسد. در این جا تصمیم‌گیری در مورد شروع مجدد فرایند یافتن مسیر بر عهده گره مبدا است.

در AODV، یک عدد شمارشی به هر مسیر تخصیص داده‌می‌شود. این عدد توسط مقصد و برای هر اطلاعات مسیریابی که به گره درخواست کننده ارسال می شود، تولید می‌شود. استفاده از این عدد امکان تشکیل حلقه را از بین می‎برد و در عین حال پیاده سازی آن نیز آسان است. اگر یک گره بخواهد بین دو مسیر موجود به یک مقصد، یکی را انتخاب نماید، مسیری را انتخاب می کند که عدد ترتیبی آن بزرگتر باشد. عملکرد صحیح AODV به این بستگی دارد که هر گره دارای یک عدد شمارشی باشد، تا امکان ایجاد حلقه در مسیرهای منتهی به آن گره، وجود نداشته باشد. هر گره، عدد شمارشی خود را در دو حالت افزایش می دهد ]8[:

الف)   درست قبل از آن که گره، فرایند یافتن مسیر را آغاز کند. بدین ترتیب مسیرهایی که به  این گره ختم می‌شدند و قبلا حذف شده‌اند سبب بروز مشکل نمی‌شوند. 

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

روش AODV ، از معروفترین روشهای مورد استفاده در شبکه‌های MANET می‌باشد. ارائه‌کنندگان این پروتکل، آن را تحت سیستم عامل Linux نیز پیاده‌سازی کرده‌اند که جزییات آن در ]37[ بیان شده‌است.

1-2-1-2-2 پروتکل مسیریابی DSR 

در DSR ]5[ هر بسته ارسالی، در سرآمد خود فهرست کلیه گره‌هایی را که باید از آنها عبور نماید، به ترتیب عبور درج می‌کند. بدین ترتیب حلقه تشکیل نمی شود و نیازی به به روز کردن اطلاعات مسیر یابی در گره‏های میانی نمی باشد. با درج این اطلاعات در سرآمد بسته، گره های دیگری که ممکن است این بسته را دریافت نمایند، قادر خواهند بود که این اطلاعات مسیریابی را در جداول خود نیز برای استفاده آینده ذخیره نمایند. یکی از خصوصیات شبکه های بی‎سیم، قابلیت ارسال کلیه بسته های دریافتی به لایه بالاتر، بدون توجه به آدرس مقصد موجود در سرآمد، می‌باشد. این قابلیت در DSR، جهت برخی بهینه سازیها،مورد استفاده قرار می گیرد. البته این حالت کاری ممکن است در برخی طراحی ها، توان مصرفی را افزایش دهد ولی آنچه مسلم است افزایش سرعت در شبکه های بی‎سیم از اهمیت فوق العاده ای برخوردار است .

DSR از دو قسمت اصلی تشکیل یافته است:

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

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

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

زمانی‌که یک گره متحرک، بسته ای برای ارسال دارد با مراجعه به واحد Route cache ، وجود مسیر برای آدرس مقصد در route cache را بررسی می‌کند. اگر هیچ مسیری در cache موجود نبود، فرایند یافتن مسیر با ارسال RREQ به کلیه گره ها صورت می پذیرد. هر گرهی که این پیام را دریافت می کند، آدرس خود را در قسمت ثبت آدرس آن قرار داده و مجدداً آن را broadcast می نماید. این عمل تا آنجا ادامه می یابد که پیام به مقصد و یا به یک گره میانی که مسیری در cache خود دارد برسد. در این جا این گره با RREP پاسخ می دهد. این نکته قابل ذکر است که DSR بر اساس Source Routing پایه ریزی شده است و در نتیجه RREQ و RREP هر دو Source Routed می باشند. نگهداری مسیر به کمک بسته های RERR Route Error)) انجام پذیر است. اگر اتصالی که در جدول ثبت شده است مختل شود مبدا به کمک بسته RERR مطلع خواهد شد.

شکل 1-5 (الف)  ارسال درخواست مسیر در الگوریتم مسیریابی DSR

شکل 1-5 (ب) ارسال پاسخ درخواست مسیر در الگوریتم مسیریابی DSR 

1-2-1-2-3 ظرفیت شبکه های بی‌سیم و محدودیت الگوریتمهای On-Demand

در ]6[ با یک بررسی تحلیلی در یک نمونه از شبکه های Ad Hoc، اثبات شده‌است که حتی در شرایط ایده‌ال و بدون در نظر گرفتن تحرک گره‌ها، افزایش تعداد گره‌های شبکه تاثیر نامطلوبی بر گذردهی میگذارد. به بیان دیگر با افزایش چگالی گره‌ها، گذردهی بسرعت بسمت صفر میل مینماید. نتایج حاصل از این تحلیلها نشان می‌دهد که در شبکه ای شامل n گره، گذردهی با   متناسب است. در این مقاله نشان داده شده‌است که حتی در صورتیکه گره‌ها را بصورتی در محیط قرار دهیم که حداکثر گذردهی را بدست آوریم، گذردهی حاصله با  متناسب خواهد بود. نگارندگان این مقاله در ]7[ صحت تحلیلهای خود را در یک محیط عملی مورد بررسی قرار داده‌اند. در آزمایشهای انجام گرفته در این تحقیق، با استفاده از تعدادی کامپیوتر مجهز به کارت شبکه بی‌سیم، گذردهی شبکه مورد ارزیابی قرارگرفته است. در آزمایشهای مزبور، تعداد گرهها از 2 تا 12 تغییر داده شده است و هرگره بصورت متناوب به یکی از گره‌های شبکه (که بصورت تصادفی انتخاب می‌شود)، ترافیک UDP ارسال مینماید. شکل 1-6 گذردهی استخراج شده در ]7[ را برحسب تعداد گره‌های موجود در شبکه نمایش میدهد. این شکل نشان‌دهنده این است که گذردهی استخراج شده با   متناسب است که حتی از آنچه در ]6[ بصورت تحلیلی استخراج شده است نیز سریعتر افت می‌کند.

شکل 1-6 افت گذردهی در یک شبکه بی‌سیم نمونه با افزایش تعداد گره‌های شبکه

البته باید توجه داشت که افت گذردهی در محیط حقیقی با سرعت بیشتری صورت می پذیرد. شبیه سازیهای انجام گرفته در ]8[ نشان میدهد که با اعمال پروتکلهای مسیریابی on-demand مانند AODV و DSR ، در ترافیکهای زیاد، ظرفیت قابل استفاده درمسیریابی به‌شدت افت می‌نماید.  در شبیه‌سازیهای صورت پذیرفته در ]8[ ، عوامل زیر بعنوان عوامل اصلی اتلاف پهنای باند معرفی شده اند:

• عبور بسته های Data از چند گره میانی. هرچه فاصله گره مبدا و مقصد از نظر تعداد گره میانی بیشتر باشد، میزان مصرف منابع شبکه به ازای هر بسته مسیریابی شده بصورت نمایی افزایش می‌یابد. این امر در مرجع ]9[ نیز بصورت تحلیلی اثبات شده است.
• بسته های کنترلی پروتکل مسیریابی.
• بسته های اطلاعات که حذف میشوند.
• بسته های کنترلی لایه MAC (در شبیه‌سازیهای انجام گرفته، IEEE802.11 درنظر گرفته شده است). ردوبدل شدن RTS/CTS/ACK به ازای هر بسته ارسالی، ظرفیت شبکه را مصرف می‌نماید. همانگونه که در بخش بعد خواهیم دید، استاندارد IEEE 802.11 نیز در کاهش ظرفیت شبکه بی‌تاثیر نیست .

ظرفیت قابل دستیابی در شبکه های Ad Hoc به تعداد گر‌ه‌ها، الگوی ترافیکی و تداخل رادیوئی گره‌ها بستگی دارد]10[ و ]11[.

با توجه به آنچه بیان شد، می‌توان به این نتیجه رسید که پروتکلهای مسیریابی مسطح مقیاس‌پذیر نیستند و محدودیتهای بسیاری در استفاده از ظرفیت شبکه دارند و این محدودیت با افزایش تعداد گره‌های شبکه بیشتر می‌شود. دلیل اصلی این محدودیت حجم بالای ترافیکهای کنترلی جهت مسیریابی می‌باشد که حتی با استفاده از روشهای on-demand نیز، ظرفیت قابل استفاده در شبکه‌های MANET همچنان به بیش از 2 تا 3 درصد ظرفیت واقعی شبکه نمی‌رسد]8[.

1-2-2 الگوریتمهای مسیریابی سلسله‌مراتبی[27]

استفاده از پروتکلهای مسیریابی سلسله مراتبی، جهت افزایش مقیاس‌پذیری، در شبکه‌های ثابت نیز دیده می‌شود. پروتکل BGP نمونه‌ای از پروتکلهای مسیریابی سلسله‌مراتبی در شبکه‌های ثابت می‌باشد. با استفاده از مسیریابی سلسله‌مراتبی، گره‌های شبکه به تعدادی گروه تقسیم می‌شوند. نقش گره‌ها در امر مسیریابی با یکدیگر یکسان نیست. درهرگروه یک گره عهده‌دار نگهداری اطلاعات مسیریابی می‌باشد. درنتیجه، مسیریابی در کل شبکه، توسط گره‌های مزبور انجام می‌پذیرد. با درنظرگرفتن مسیریابی سلسله مراتبی، می‌توان یک شبکه مجازی(MBN) را مطابق شکل 1-7 فرض کرد که اعضای(BN)  آن مسؤل مسیریابی هستند. بدین‌ترتیب، الگوریتمهای مسیریابی سلسله‌مراتبی، باعث کاهش ترافیک کنترلی ردوبدل شده و درنتیجه افزایش ظرفیت شبکه خواهند شد .

شکل 1-7 شبکه مجازی ایجاد شده در یک شبکه MANET با استفاده از مسیریابی سلسله‌مراتبی

جهت پیاده‌سازی مسیریابی سلسله‌مراتبی، روشهای متفاوتی ارائه‌شده‌اند. در برخی از این روشها، جهت گره‌های BN ، از لحاظ سخت‌افزاری و یا تحرک گره، فرضهای خاصی درنظر گرفته می‌شوند. به عبارتی ساختار سلسله‌مراتبی در لایه فیزیکی گره‌ها نیز درنظر گرفته شده‌است[28].  به عنوان مثال در ]14[ فرض شده‌است که گره‌های BN دارای یک کانال رادیوئی اضافه جهت برقراری ارتباط با یکدیگر هستند که ارسال اطلاعات در MBN را تسهیل می‌نماید. گاهی نیز فرض بر این است که گره‌های BN ، توان ارسالی و پهنای باند بیشتری نسبت به سایر گره‌های موجود در شبکه دارند. اما در بیشتر الگوریتمهای مسیریابی سلسله‌مراتبی، ساختار سلسله‌مراتبی منطقی[29] بجای سلسله مراتبی فیزیکی درنظر گرفته شده است. الگوریتمهای ZRP ]15[، HSR  و همچنین الگوریتمهای مبتنی بر خوشه‌یابی از این نوع الگوریتمها می‌باشند.

1-2-2-1 مفهوم خوشه‌یابی[30]

تقسیم بندی گره‌های شبکه به تعدادی گروه مجازی[31] جهت کاهش سرباره های[32] مسیریابی و کاربردهایی نظیر آن در شبکه از روشهای مرسوم در پروتکل‌های شبکه میباشد. به این روش اصطلاحا خوشه‌یابی گفته میشود ]40[. در الگوریتمهای خوشه‌یابی، شبکه MANET به تعدادی گروه مجازی تقسیم می‌شود که هرکدام از این گروهها خوشه[33] نامیده می‌شود. گره‌های متحرک در هر خوشه بلحاظ جغرافیایی در مجاورت یکدیگر قرار دارند. در هر Cluster ، یک گره بعنوان سرگروه[34] (CH) انتخاب می‌شود. بقیه گره‌ها، عضو یکی از خوشه های[35] موجود میباشند. حداکثر فاصله هر گره تا سرگروه شعاع خوشه[36] نامیده می‌شود. شعاع خوشه یکی از پارامترهای طراحی الگوریتم خوشه‌یابی می‌باشد و بر حسب تعداد گره‌های میانی بیان می‌شود. اکثر الگوریتمهای ارائه شده یک‌گامی هستند یعنی عضوهای خوشه‌ها در فاصله 1 گره تا Cluster-Head قرار دارند. برخی الگوریتمها نیز چندگامی هستند. بدلیل آنکه در الگوریتمهای توزیعی خوشه‌یابی، پیچیدگی و سرباره ارتباطی جهت ایجاد خوشه‌ها، با افزایش شعاع خوشه افزایش می‌یابد، در الگوریتم‌های ارائه‌شده تاکنون، شعاع خوشه از دو گره فراتر نرفته‌است. شکل 1-8 نمونه‌ای از خوشه‌یابی را در یک شبکه Ad Hoc نشان می‌دهد. در این شکل، خوشه‌یابی با حداکثر شعاع دو گام درنظرگرفته‌شده است. در این مثال، گره‌های 5، 7 و 11 به‌عنوان سرگروه انتخاب شده‌اند و سایر گره‌ها هرکدام عضوی از یکی از سرگروه‌های اشاره شده می‌باشند.

شکل 1-8 مثالی ازخوشه‌یابی  در شبکه Ad Hoc

الگوریتمهای خوشه‌یابی مختلفی تاکنون جهت شبکه های Ad Hoc ارائه شده اند. الگوریتمهای ارائه‌شده، با روشهای متفاوتی CHها را انتخاب می‌نمایند.

1-2-2-2 مزایای استفاده از خوشه‌یابی

با توجه به آنچه در قسمتهای قبل در مورد محدودیت ظرفیت شبکه‌های Ad Hoc بیان شد، در کاربردها‌یی نظیر مسیریابی و پراکنش‌اطلاعات، استفاده از ساختار سلسله‌مراتبی جهت بهینه‌سازی ظرفیت شبکه ضروری به نظر می‌رسد. خوشه‌یابی درواقع روشی برای تحقق چنین ساختار سلسله‌مراتبی می‌باشد. درحقیقت با پیاده‌سازی الگوریتم خوشه‌یابی، گره‌ها در قالب تعدادی گروه مجازی تقسیم‌بندی می‌شوند. سرگروه‌های هرکدام از این گروه‌ها بار اصلی مسیریابی در داخل گروه را برعهده خواهند داشت. گره‌های دروازه نیز مسؤلیت انتقال اطلاعات بین دو خوشه مجاور را انجام می‌دهند. بدین‌ترتیب گره‌های سرگروه و گره‌های دروازه یک شبکه زیرساخت ارتباطی مجازی[37] را تشکیل می‌دهند.  شکل 1-9 ارتباط بین کاربردهای مسیریابی و پراکنش اطلاعات را با خوشه‌یابی در ساختار لایه‌ای هرگره نمایش می‌دهد