مسيريابی مبتنی بر ناحيه بندی در شبكه های Ad Hoc

مسيريابی مبتنی بر ناحيه بندی در شبكه های Ad Hoc
مسيريابی مبتنی بر ناحيه بندی در شبكه های Ad Hoc
90,000 ریال 
تخفیف 15 تا 30 درصدی برای همکاران، کافی نت ها و مشتریان ویژه _____________________________  
وضعيت موجودي: موجود است
تعداد:  
افزودن به ليست مقايسه | افزودن به محصولات مورد علاقه

تعداد صفحات : 93 صفحه _ فرمت WORD _ دانلود مطالب بلافاصله پس از پرداخت آنلاین

فهرست :

    پیشگفتار
    فصل اول
    شبکه‌های Ad Hoc
    1-1 تقسیم‌بندی شبکه‌های بی‌سیم
    1-2 مروری بر پروتکلهای مسیریابی در شبکه‌های MANET
    1-2-1 الگوریتمهای مسیریابی مسطح6
    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 را از آن دريافت كرده است، به اين درخواست پاسخ مي دهد.

 
شكل 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

نظري براي اين محصول ثبت نشده است.


نوشتن نظر خودتان

براي نوشتن نظر وارد شويد.

محصولات
نظر سنجي
نظرتون در مورد ویکی پروژه چیه؟
  •   مراحل ثبت نام خیلی زیاده!
  •   مطلب درخواستیم رو نداشت!
  •   ایمیل نداشتم که ثبت نام کنم!
  •   مطلبی که میخواستم گرون بود!
نظرنتيجه