مقاله مسيريابي مبتني بر ناحيه بندي در شبكه هاي Ad Hoc با word

مقاله مسيريابي مبتني بر ناحيه بندي در شبكه هاي Ad Hoc با word دارای 103 صفحه می باشد و دارای تنظیمات در microsoft word می باشد و آماده پرینت یا چاپ است

فایل ورد مقاله مسيريابي مبتني بر ناحيه بندي در شبكه هاي Ad Hoc با word کاملا فرمت بندی و تنظیم شده در استاندارد دانشگاه و مراکز دولتی می باشد.

این پروژه توسط مرکز مرکز پروژه های دانشجویی آماده و تنظیم شده است

توجه : در صورت  مشاهده  بهم ريختگي احتمالي در متون زير ،دليل ان کپي کردن اين مطالب از داخل فایل ورد مي باشد و در فايل اصلي مقاله مسيريابي مبتني بر ناحيه بندي در شبكه هاي Ad Hoc با word،به هيچ وجه بهم ريختگي وجود ندارد

بخشی از متن مقاله مسيريابي مبتني بر ناحيه بندي در شبكه هاي Ad Hoc با word :

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

شبكه‌های 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[ می‌توان به اثر مطلوب پایداری خوشه‌های ایجاد شده در بهبود كارایی مسیریابی اشاره نمود.