دانلود مقاله مسیریابی مبتنی بر ناحیه بندی در شبکه های Ad Hoc

بخشی از مقاله

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

شبكه‌هاي Ad–hoc براي اولين بار توسط وزارت دفاع آمريكا در سيستم‌هاي نظامي و عملياتي خود مورد استفاده قرار گرفته است. ليكن از سال 1970 بطور عمومي مورد استفاده ميباشد.
در اين پروژه هدف ارائه الگوريتم مسيريابي پيشنهادي مبتني بر خوشه يابي مي باشد.
در اين راستا ابتدا در فصل اول به تقسيم بندي و توضيح شبكه هاي ادهاك و مروري بر پروتكلهاي مسيريابي آن خواهيم پرداخت و سپس در فصل دوم عناصر مورد استفاده جهت شبيه سازي شبكه هاي MANET كه شامل مدل هاي حركت و ابزار شبيه سازي مي باشد مورد بررسي قرار مي گيرد و نيز فصل آخر را به بررسي الگوريتم هاي خوشه يابي و ارائه يك

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

فصل اول
شبكه‌هاي Ad Hoc
1-1 تقسيم‌بندي شبكه‌هاي بي‌سيم
شبكه هاي بي‎سيم را از نظر معماري مي توان به دو گروه اصلي تقسيم بندي نمود:
الف) شبكه هاي داراي زيرساخت

مسيريابهايي كه در اين نوع شبكه‌ها مورد استفاده قرار مي‌گيرند، اصطلاحاً به ايستگاه‌هاي ثابت شهرت دارند. اين ايستگاههاي پايه‌اي قابليت حركت ندارند، با روشهاي مختلف و با امكانات سرعت بالا به يكديگر متصل هستند. هر واحد متحرك در زمان برقراري ارتباط و نيز ردو بدل كردن اطلاعات، به نزديكترين ايستگاه پايه‌اي متصل مي شود. در نتيجه ارتباطات بي‎سيم در اين نوع شبكه‌ها، بر اساس ارتباط سيمي بين ايستگاه هاي پايه‌اي صورت مي پذيرد. اين شبكه‌ها همچنين به شبكه‌هاي بي‎سيم يك‌گامي نيز شهرت دارند. شبكه‌هاي مخابرات سلولي و شبكه‌هاي PCS مثالهايي از اين نوع شبكه‌هاي بي‌سيم هستند. در شبكه‌هاي يك‌گامي گره‌هاي متحرك همواره تحت پوشش ايستگاههاي پايه قرار دارند و در نتيجه ارتباط پيوسته‌اي با ايستگاههاي پايه دارند.

شكل 1-1 مثالي از شبكه‌هاي داراي زيرساخت
ب) شبكه هاي فاقد زيرساخت

در اين شبكه ها كه به شبكه هاي MANET نيز شهرت دارند، هيچ زير ساخت از پيش تعريف شده اي براي برقراري ارتباط بين گره ها وجود ندارد. هر گره قابليت مسيريابي را داراست در عين حال، قادر است در هر جهتي حركت كند و همچنين به گره هاي ديگر نيز متصل شود. به همين دليل، اطلاعات ارسالي از يك گره به گره ديگر بدليل فاصله دو گره مزبور ممكن است در صورت نياز از چند گره ديگر عبور كند. درنتيجه، اين شبكه ها را شبكه هاي بي‎سيم چندگامي نيز مي‌نامند. در اين پروژه، اين دسته از شبكه‌هاي بي‌سيم مورد بحث و بررسي قرار مي گيرند.

شكل 1-2 نمونه‌اي از شبكه‌هاي فاقد زير ساخت
باتوجه به اينكه هيچ زيرساخت ارتباطي ويا ادوات سخت افزاري جانبي جهت راه‌اندازي و مديريت شبكه مورد نياز نيست، با روشن شدن و فعال شدن گره‌ها، شبكه تشكيل مي‌شود. بدين ترتيب سادگي و سرعت راه‌اندازي شبكه از خصوصيات شبكه‌هاي MANET مي‌باشد.

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

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

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

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

شكل 1-3 تقسيم‌بندي پروتكلهاي مسيريابي شبكه‌هاي MANET
1-2-1 الگوريتمهاي مسيريابي مسطح

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

- پروتكلهاي مسيريابي Table-driven (Proactive)
- پروتكلهاي مسيريابي On-Demand (Reactive)

1-2-1-1 پروتكلهاي مسيريابي Table Driven
اين دسته از پروتكلهاي مسيريابي كه در ابتداي مطرح شدن شبكه‌هاي MANET ارائه‌شده‌‌اند، بر روشهاي مسيريابي معمول در شبكه‌هاي ثابت، مانند روشهاي DV و LS تكيه مي‌كنند. در نتيجه مشابه الگوريتمهاي مزبور، در هر گره جداولي از اطلاعات مربوط به مسيريابي نگهداري ميشوند. با توجه به تحرك گره‌ها و تغيير توپولوژي شبكه، كه مهمترين تفاوت شبكه‌هاي MANET و شبكه‌هاي ثابت مي‌باشد، اطلاعات موجود در اين جداول با هر تغيير در شبكه بايد اصلاح شوند تا از هماهنگي جداول در گره‌هاي مختلف اطمينان حاصل شود. عموماً در اين دسته از پروتكلهاي مسيريابي، اطلاعات مسيريابي توسط هر گره بصورت دوره‎اي و در زمانهاي مشخص به ديگر گره‌ها بصورت بسته‌هاي حاوي اطلاعات كنترلي ارسال مي‎شود.

پروتكلهاي مسيريابي كه در اين گروه قرار مي‌گيرند، بر حسب تعداد جداول و اطلاعاتي كه در اين جداول قرار مي گيرند و همچنين از لحاظ روش ارسال اطلاعات مسيريابي به ديگر گره‌ها، تقسيم بندي مي شوند.

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

1-2-1-1-1 پروتكل مسيريابي DSDV
DSDV يك نسخه بهبود يافته از DBF است. درDSDV، هيچگاه حلقه رخ نخواهد داد. اطلاعاتي كه در هر گره نگهداري ميشود، شامل آدرس گره‌ها و همچنين تعداد گره‌هاي مياني جهت دسترسي به آن گره است. هر سطر اين جدول با يك عدد شمارشي علامت گذاري ميشود. اين اعداد جهت تشخيص مسيرهاي جديد از مسيرهاي قديمي و خارج از رده مورد استفاده قرار مي‌گيرند تا از تشكيل حلقه جلوگيري به عمل آيد. جداول مسيريابي به صورت دوره‎اي و جهت ايجاد سازگاري بين گره‌هاي شبكه به ديگر گره‌ها ارسال مي شوند. اين امر باعث ايجاد ترافيك نسبتاً زيادي در شبكه مي شود. جهت تعديل و كاهش اثرات اين ترافيك، دو نوع بسته كنترلي، جهت ارسال تغييرات اين جداول به ديگر گره‌هاي شبكه مورد استفاده قرار مي گيرند:

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

1-2-1-1-2 پروتكل مسيريابي WRP
دراين روش هدف نگهداري اطلاعات مسيريابي در كليه گره‌هاي شبكه است. هر گره بايد 4 جدول در حافظه خود نگهداري كند: جدول فاصله ، جدول مسيريابي ، جدول هزينه اتصال و جدول ارسال مجدد پيام .

در جدول ارسال مجدد پيام، بخشهايي از تغييرات كه بايد مجدداً ارسال شوند و همچنين آدرس گره‌هايي كه بايد به اين ارسال مجدد پاسخ دهند ثبت ميشوند. پيام بهنگام‌سازي ، فقط بين گره‌هاي مجاور ارسال ميشود و حاوي تغييرات و همچنين فهرست آدرسهايي از گره‌هاي شبكه است كه بايد نتيجه دريافت اين پيام را به فرستنده منعكس نمايند. پيام تصحيح زماني توسط يك گره ارسال ميشود كه اين گره يك پيام تصحيح از همسايه خود دريافت كند و يا تغييري در يك اتصال با يكي از همسايگان خود مشاهده كند.
گره‌ها با ردو بدل شدن acknowledgement و همچنين ديگر پيامها، از حضور همسايگان خود مطلع ميشوند. زمانيكه يك گره اطلاعاتي براي ارسال ندارد، بايد بصورت دوره‎اي پيام Hello ارسال كند تا از درستي اتصالات خود اطمينان حاصل نمايد.

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

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

1-2-1-2-1 پروتكل مسيريابي AODV
AODV ]7و8[ مشابه با DSDV طراحي شده‌ است. تفاوت اصلي AODV با DSDV در اين است كه بر خلاف DSDV، فهرست كامل مسيرها نگهداري نميشود ]3[. در اين الگوريتم، در هر گره فرايند يافتن مسير مطابق شكل 3 با پراكنش كردن يك درخواست مسير RREQ به گره‌هاي همسايه آغاز ميشود. گره‌هاي همسايه نيز پس از ذخيره كردن مشخصات فرستنده RREQ , اين بسته را به ديگر گره‌هاي همسايه خود ارسال مينمايند. اين عمل تا آنجا ادامه مي‎يابد كه گره مقصد و يا يكي از گره هاي مياني كه مسير نسبتاً جديدي به گره مقصد دارد، بسته را دريافت نمايد. مسير نسبتا جديد ، مسيري است كه عدد شمارشي آن، بزرگتر يا مساوي عدد موجود در 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 الگوريتمهاي مسيريابي سلسله‌مراتبي

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

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

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

1-2-2-1 مفهوم خوشه‌يابي
تقسيم بندي گره‌هاي شبكه به تعدادي گروه مجازي جهت كاهش سرباره هاي مسيريابي و كاربردهايي نظير آن در شبكه از روشهاي مرسوم در پروتكل‌هاي شبكه ميباشد. به اين روش اصطلاحا خوشه‌يابي گفته ميشود ]40[. در الگوريتمهاي خوشه‌يابي، شبكه MANET به تعدادي گروه مجازي تقسيم مي‌شود كه هركدام از اين گروهها خوشه ناميده مي‌شود. گره‌هاي متحرك در هر خوشه بلحاظ جغرافيايي در مجاورت يكديگر قرار دارند. در هر Cluster ، يك گره بعنوان سرگروه (CH) انتخاب مي‌شود. بقيه گره‌ها، عضو يكي از خوشه هاي موجود

ميباشند. حداكثر فاصله هر گره تا سرگروه شعاع خوشه ناميده مي‌شود. شعاع خوشه يكي از پارامترهاي طراحي الگوريتم خوشه‌يابي مي‌باشد و بر حسب تعداد گره‌هاي مياني بيان مي‌شود. اكثر الگوريتمهاي ارائه شده يك‌گامي هستند يعني عضوهاي خوشه‌ها در فاصله 1 گره تا Cluster-Head قرار دارند. برخي الگوريتمها نيز چندگامي هستند. بدليل آنكه در الگوريتمهاي توزيعي خوشه‌يابي، پيچيدگي و سرباره ارتباطي جهت ايجاد خوشه‌ها، با افزايش شعاع خوشه افزايش مي‌يابد، در الگوريتم‌هاي ارائه‌شده تاكنون، شعاع خوشه از دو گره فراتر نرفته‌است. شكل 1-8 نمونه‌اي از خوشه‌يابي را در يك شبكه Ad Hoc نشان مي‌دهد. در اين شكل، خوشه‌يابي با حداكثر شعاع دو گام درنظرگرفته‌شده است. در اين مثال، گره‌هاي 5، 7 و 11 به‌عنوان سرگروه انتخاب شده‌اند و ساير گره‌ها هركدام عضوي از يكي از سرگروه‌هاي اشاره شده مي‌باشند.

شكل 1-8 مثالي ازخوشه‌يابي در شبكه Ad Hoc
الگوريتمهاي خوشه‌يابي مختلفي تاكنون جهت شبكه هاي Ad Hoc ارائه شده اند. الگوريتمهاي ارائه‌شده، با روشهاي متفاوتي CHها را انتخاب مي‌نمايند.
1-2-2-2 مزاياي استفاده از خوشه‌يابي

با توجه به آنچه در قسمتهاي قبل در مورد محدوديت ظرفيت شبكه‌هاي Ad Hoc بيان شد، در كاربردها‌يي نظير مسيريابي و پراكنش‌اطلاعات، استفاده از ساختار سلسله‌مراتبي جهت بهينه‌سازي ظرفيت شبكه ضروري به نظر مي‌رسد. خوشه‌يابي درواقع روشي براي تحقق چنين ساختار سلسله‌مراتبي مي‌باشد. درحقيقت با پياده‌سازي الگوريتم خوشه‌يابي، گره‌ها در قالب تعدادي گروه مجازي تقسيم‌بندي مي‌شوند. سرگروه‌هاي هركدام از اين گروه‌ها بار اصلي مسيريابي در داخل گروه را برعهده خواهند داشت. گره‌هاي دروازه نيز مسؤليت انتقال

اطلاعات بين دو خوشه مجاور را انجام مي‌دهند. بدين‌ترتيب گره‌هاي سرگروه و گره‌هاي دروازه يك شبكه زيرساخت ارتباطي مجازي را تشكيل مي‌دهند. شكل 1-9 ارتباط بين كاربردهاي مسيريابي و پراكنش اطلاعات را با خوشه‌يابي در ساختار لايه‌اي هرگره نمايش مي‌دهد.

شكل 1-9 خوشه‌يابي در ساختار لايه‌اي
همانگونه كه در شكل مشخص است، خوشه‌يابي در لايه 3 پياده‌سازي مي‌شود. پروتكلهاي مسيريابي و پراكنش اطلاعات هم در همين لايه قرار دارند و از سرويس‌هاي واحد خوشه‌يابي استفاده مي‌نمايند. با استفاده از خوشه‌يابي در مسيريابي و پراكنش اطلاعات، تنها گره‌هاي سرگروه و دروازه مسؤل مسيريابي و يا پراكنش اطلاعات كنترلي به ساير گره‌ها مي‌باشند. اين امر فوايد زير را به همراه دارد:

• تعداد ارسال بسته‌هاي كنترلي در شبكه كاهش مي‌يابد و در استفاده از ظرفيت شبكه صرفه‌جويي مي‌شود. اين امر باعث كاهش مصرف توان در گره‌هاي متحرك نيز خواهدشد. افرون براين، تمام گره‌هاي متحرك ملزم به نگهداري جداول مسيريابي نمي‌باشند. بدين ترتيب استفاده از منابع شبكه كاهش خواهديافت.
• تحرك گره‌ها اثر كمتري بر كارائي مسيريابي خواهد داشت. اطلاعات مسيريابي هر گره صرفاً در سرگروه مربوط به Cluster همان گره ذخيره مي‌شود. حركت يك گره از يك Cluster به يك Cluster ديگر فقط باعث تغيير اطلاعات دو سرگروه در شبكه مي‌شود]41[.

1-2-2-3 الگوريتمهاي مسيريابي سلسله‌مراتبي مبتني بر خوشه‌يابي
در اين قسمت مروري خواهيم داشت بر روشهاي مسيريابي مبتني بر خوشه‌يابي. روشهاي مختلفي جهت مسيريابي مبتني بر خوشه‌يابي ارائه‌شده‌است كه در اين بخش تعدادي از آنها مورد اشاره‌قرار مي‌گيرند.
CGSR يكي از اولين الگوريتمهاي مبتني بر خوشه‌يابي از نوع Table-Driven است. در CGSR بسته ارسالي از هر گره به سرگروه آن گره و از سرگروه به دروازه ارسال مي‌شود. از اين به بعد، ارسال از دروازه به سرگروه و از سرگروه به دروازه آنقدر انجام مي‌گيرد، تا بسته اطلاعات به خوشه مربوط به گره مقصد برسد. در اينجاست كه بسته نهايتا به خود سيستم مقصد ميرسد. شكل 1-10 مثالي از CGSR را نمايش مي‌دهد.

شكل 1-10 مثالي از الگوريتم مسيريابي CGSR
همانگونه كه در اين شكل مشخص است، جهت ارسال اطلاعات از گره 10 به گره 2، سرگروه‌هاي 5 و 11 و 7 و دروازه‌هاي 1 و 9 در مسير ارسال اطلاعات قرارگرفته‌اند.
CGSR در حقيقت مبتني بر DSDV مي‌باشد ولي با استفاده از خوشه‌يابي، سعي در بهبود كارايي مسيريابي دارد. در اين روش هر گره بايد يك جدول عضويت در خوشه نگهداري كند كه شامل خوشه مربوط به هر گره در شبكه مي‌باشد. اين جداول با روش DSDV ، توسط هر گره به صورت متناوب ارسال مي شوند.
الگوريتم ديگري كه ارائه شده‌است، CBRP نام دارد. اين روش در حقيقت بهبوديافته DSR جهت استقاده از الگوريتم خوشه‌يابي مي‌باشد. در اين روش هر سرگروه، بايد خوشه‌هاي مجاور خود را بشناسد. به همين دليل هرگره يك جدول از آدرس سرگروه‌هاي مجاور ذخيره مي‌نمايد و اين آدرسها را دربسته‌هاي Hello ارسالي قرار مي‌دهد. بدين ترتيب، سرگروه با دريافت پيامهاي Hello از گره‌هاي مجاور خود، از خوشه‌هاي مجاور مطلع مي‌شود.

در زمان درخواست مسير توسط گره مبدا، سرگروه وظيفه پراكنش بسته‌هاي درخواست مسير به سرگروه‌هاي مجاور را دارد. مشابه DSR، در بسته‌هاي درخواست مسير درحين عبور از گره‌ها، بايد آدرس مسير در بسته گنجانده شود ولي برخلاف DSR فقط آدرس سرگروههايي كه بسته درخواست از آنها عبور كرده‌است ثبت مي‌شود. شكل 1-11 مثالي از فاز فرايند يافتن مسير در CBRP را نمايش مي‌دهد.

شكل 1-11 يافتن مسير در الگوريتم CBRP
در ]38[ الگوريتم مسيريابي ديگري مبتني بر خوشه‌يابي با شعاع 2 گره در نظر گرفته شده‌است، در اين روش، دو نوع الگوريتم مسيريابي مورد استفاده قرار مي‌گيرد. مسيريابي داخل خوشه‌ها، از روش DSDV و مسيريابي بين خوشه‌ها، از يك روش On-Demand مانند AODV استفاده مي‌كند. در نتيجه در مسيريابي بين دو گره، اگر هردو داخل يك خوشه باشند، با روش DSDV ، مسيريابي صورت مي‌پذيرد. اگر دو گره در دو خوشه مجزا از هم باشند، سرگروه طرف مبدا بايد فرايند يافتن مسير را آغاز نمايد و با يافتن خوشه طرف مقصد، مسيريابي را انجام دهد. لازم به ذكر است كه استفاده تركيبي از دو متد مسيريابي در بهبود كارايي مسيريابي تاثير به سزايي خواهد داشت. از ديگر نتايج ارائه شده در ]38[ مي‌توان به اثر مطلوب پايداري خوشه‌هاي ايجاد شده در بهبود كارايي مسيريابي اشاره نمود.