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

بخشی از فهرست مطالب پروژه فایل word مسیریابی مبتنی بر ناحیه بندی در شبکه های Ad Hoc

    پیشگفتار
    فصل اول
    شبکه‌های Ad Hoc
    1-1 تقسیم‌بندی شبکه‌های بی‌سیم
    1-2 مروری بر پروتکلهای مسیریابی در شبکه‌های MANET
    1-2-1 الگوریتمهای مسیریابی مسطح
    1-2-1-1 پروتکلهای مسیریابی Table Driven
    1-2-1-1-1  پروتکل مسیریابی DSDV
    1-2-1-1-2 پروتکل مسیریابی WRP
    1-2-1-2 پروتکلهای مسیریابی on-Demand
    1-2-1-2-1 پروتکل مسیریابی AODV
    1-2-1-2-2 پروتکل مسیریابی DSR
    1-2-1-2-3 ظرفیت شبکه های بی‌سیم و محدودیت الگوریتمهای On-Demand
    1-2-2 الگوریتمهای مسیریابی سلسله‌مراتبی
    1-2-2-1 مفهوم خوشه‌یابی
    1-2-2-2 مزایای استفاده از خوشه‌یابی
    1-2-2-3 الگوریتمهای مسیریابی سلسله‌مراتبی مبتنی بر خوشه‌یابی
    فصل دوم
    عناصر مورد استفاده جهت شبیه‌سازی شبکه‌های MANET
    2-1 تکنولوژی بی‌سیم مورد استفاده در شبیه سازی شبکه های  Ad Hoc
    2-2 مدلهای تحرک
    2-2-1 مدل‌های تحرک تصادفی
    2-2-2 مدل تحرک با وابستگی لحظه‌ای
    2-2-3 مدل تحرک با وابستگی فضایی
    2-2-4 مدلهای تحرک با محدودیت جغرافیایی
    2-2-5 خصوصیات مدل تحرک Random Waypoint
    2-3 ابزار شبیه‌سازی
    فصل سوم
    خوشه‌یابی
    3-1 مروری بر الگوریتمهای خوشه‌یابی
    3-2 پارامترهای کارایی در روشهای خوشه‌یابی
    3-3 الگوریتم خوشه‌یابی پیشنهادی
    3-3-1 تشخیص گره‌های همسایه
    3-3-2 شکل گیری خوشه‌ها
    3-3-3 پیکربندی مجدد خوشه‌ها
    3-3-4 ارزیابی کارایی
    فصل چهارم
    نتیجه‌گیری و پیشنهاد برای آینده
    ضمیمه 1 ( واژه‌نامه )
    ضمیمه 2 ( عبارتهای اختصاری )
    مراجع
    مقاله خلاصه پایان نامه

ضمیمه 1
واژه‌نامه
گره مرزی    Border Node
پراکنش اطلاعات    Broadcasting
خوشه‌یابی    Clustering
سرگروه    Cluster Head
تصادم    Collision
توان محاسباتی    Computational Power
هماهنگی    Consistency
رقابت    Contention
امواج چگالی    Density Waves
ترافیک خارجی    External Traffic
قابلیت توسعه    Extensibility
الگوریتمهای مسیریابی مسطح    Flat Routing Algorithms
مسیر نسبتا جدید    Fresh Enough Route
دروازه    Gateway
محدودیت جغرافیایی    Geographical Restriction
سرگروه    Group Leader
تحرک گروهی    Group Mobility
گره مخفی    Hidden Node
الگوریتمهای مسیریابی سلسله‌مراتبی    Hierarchical Routing Algorithms
شبکه‌های دارای زیرساخت    Infra Structured Networks
شبکه‌های فاقد زیرساخت    Infra Structure-less Networks
ترافیک داخلی    Internal Traffic
سلسله‌مراتبی منطقی    Logically Hierarchical
مدل تحرک    Mobility Model
مدل تحرک با وابستگی لحظه‌ای    Mobility Model with Temporal Dependency
چندگامی    Multi Hop
چگالی گره‌ها    Node Density
شی‌گرا    Object Oriented
سرباره    Overhead
زمان توقف    Pause Time
سلسله‌مراتبی در لایه فیزیکی    Physically Hierarchical
مدلهای تحرک تصادفی    Random-Based Mobility Models
مقیاس‌پذیری    Scalability
تولید سناریو    Scenario Generation
خودحذفی    Self Pruning
عدد شمارشی    Sequence Number
یک گامی    Single Hop
شیار زمانی    Slot Time
وابستگی فضایی    Spatial Dependency
افت سرعت    Speed Decay
پایداری    Stability
مسیرهای خارج از رده    Stale Routes
ظرفیت ذخیره‌سازی    Storage Capacity
گذردهی    Throughput
تفکیک ترافیک    Traffic Isolation
الگوی ترافیک    Traffic Pattern
تعویق زمانی    Transmission Defer
گروه مجازی    Virtual Group
شبکه‌های بی‌سیم    Wireless Networks
 
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 را از آن دریافت کرده است, به این درخواست پاسخ می دهد.


در 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 مطلع خواهد شد.