بخشی از مقاله
ارائه يک روش بازيابي محلي مبتني بر پروتکل چندپخشي ODMRP در شبکه هاي سيار موردي
چکيده : شبکه هاي سيار موردي نوع خاصي از شبکه هـاي بـي سـيم مي باشد که علاوه بر بي سيم بودن اين شبکه ها، قابليت جابجـايي نيـز بدان ها اضافه مي شود و کار را با پيچيدگي بيشتري مواجه مـي سـازد. شبکه هاي سيار موردي بدون هيچ زيرساختار خاصي بر پا مي شـوند و در جنگهاي نظامي ، عمليات نجات در مناطق آسيب ديده و کنفرانس ها کاربرد بسيار دارند. با توجه به محدوديت هاي موجـود در شـبکه هـاي سيار موردي پروتکل هاي چندپخشي زيادي در اين شبکه ها ارائه شده است . يکي از مطرح تـرين پروتکـل هـاي چندپخشـي در شـبکه هـاي سيارموردي پروتکل ODMRP مي باشد. در اين مقاله هدف ارائه يـک روش مسيريابي چندپخشي است که ضمن دارا بودن قابليت اطمينـان بالا بتواند عمليات انتقال اطلاعات را با وجود گستردگي گروههاي چنـد پخشي به درستي به انجام رساند طوري که هـر گـره عضـو گـروه چنـد پخشي حداقل داده ها را از دست دهد. نتايج شبيه سازي بـر روي گـره هاي متحرک نشان مي دهد که روش جديد در مقايسه با پروتکل پايه با فراهم نمودن قابليت اطمينان بيشتر ، نرخ تحويل بسته را بالاتر بـرده و قابليت اطمينان گروهي را نيز بهبود بخشيده است .
واژه هاي کليدي : شبکه هاي سـيار مـوردي ، چنـد پخشـي ، قابليـت اطمينان ، بازيابي محلي .
١- مقدمه
امروزه شبکه هاي بي سيم به دليل کاربردهاي وسـيعي کـه دارنـد و همچنين سرويسهايي که ارائه مي دهند، رشد چشمگيري داشته اند. اين
شبکه ها در حال توسعه سريعي هستند و سرويسهاي ارائه شده هـم روز بروز بهتر و بيشتر مي شوند.از نظر معماري ، شبکه هـاي بـي سـيم بـه دو دسته شبکه هاي با زيرساختار و شبکه هـاي بـدون زيرسـاختار تقسـيم مي شوند. مشخصه کلي در شبکه هاي بي سيم اين است که ايـن شـبکه ها احتياج به محاسبات به منظور دستيابي گره ها به يکديگر دارند. يـک شبکه بدون زيرساخت يا شبکه سيار موردي تنها شامل گره هاي سـيار است که بدون هيچ ايستگاه ثابت و اتصال سيمي براي مبادله اطلاعات و مديريت شبکه بکار گرفته مي شوند. هر گره سيار تنها مانند يک ميزبان عمل نمي کند، بلکه مانند يک مسيرياب عمل مي کند و گـره هـا خـود، مسئول به جلو راندن بسته ها به ساير گره هاي سيار موجـود در شـبکه مي باشند. غالباً توپولـوژي شـبکه سـيار مـوردي از گـره هـايي تشـکيل مي شود که به طور پويا و مداوم به شبکه وارد و يا خارج مي شوند. هـيچ کنترل مرکزي يا ساختار بندي ثابتي براي پشتيباني پيکربندي شبکه و يا پيکربندي دوباره شبکه وجـود نـدارد[۱]. ايـن شـبکه هـا بطـور کلـي ترکيبي از گره هاي يکسان مي باشند که بدون هيچگونه کنترل مرکـزي بصورت بدون سيم با يکديگر ارتباط برقرار مـي کننـد. بـه شـبکه هـاي
Mobile Ad Hoc Network به طور خلاصه MANET گفتـه مـي شود.
شکل (۱): شمايي از گره ها با برد مشخص در Ad Hoc
در شبکه هاي سيار موردي چالشهاي بسياري مطـرح مـي شـود کـه از جمله آنها مي توان به انـرژي ، چندپخشـي ، کيفيـت سـرويس و امنيـت اشـاره کـرد. مسـير يـابي چنــد پخشـي نقـش مهمـي در کاربردهـاي عملياتهاي جستجو و نجات و نظامي و برگزاري سمينارها بر عهده دارد.
در اين کاربردها گروههايي تشکيل مي شوند که معمولا انتقال صوت يـا تصوير از يک گره به چندين گره در آنها انجام مي شود. تغيير توپولـوژي و محدوديت منابع انرژي و پهناي باند مسيريابي چند پخشي را مشـکل تر کرده است . روشهاي مسيريابي چندپخشـي مرسـوم در شـبکه هـاي سيمي ازقبيـل CBT [٢]،PIM [٣] ،DVMRP [٤] در شـبکه هـاي سيار موردي به خوبي کار نمي کنند زيـرا سـاختارهاي درختـي بسـيار شکننده هستند و نياز به ساخت مجدد درخت و در نتيجه سربار بـالاي بسته هاي کنترلي مي شود. اين عوامل باعث شد که ساختار هاي توري مطرح شوند که در محيطهايي با سرعتهاي بالا به خوبي کار مـي کننـد.
پروتکلهاي چند پخشي نيازمند تشـکيل چنـدين مسـير و هـدايت داده برروي گرافي از گرهها هستند. درميان انواع مختلـف پروتکلهـاي چنـد پخشي روشهاي مبتني بـر تشـکيل مـش داراي اسـتحکام بيشـتري در شبکه هاي بزرگ مقياس هستند. يکـي از مهمتـرين پروتکلهـا در ايـن گروه پروتکل ODMRP است .
قابليت اطمينان پروتکل هـاي مسـيريابي در انتقـال اطلاعـات يکـي از عوامل تعيين کننده در شبکه هاي سيار موردي مي باشد که تحقيقـات زيادي در اين زمينه صورت گرفته است . برخي از ايـن پروتکـل هـا بـا دريافت تائيديه و يا کنترل تصادم به اين مهـم دسـت يافتـه انـد[٦،٧] ، برخي ديگر نيز روش هاي ديگري را در ايـن زمينـه بـه کـار بـرده انـد.
همچنين براي دستيابي به يک کـارايي مناسـب در شـبکه هـاي سـيار موردي در برخي پروتکل ها نيـاز بـه اسـتفاده از پـيش بينـي وضـعيت حرکتي گرهها ضروري به نظر مي رسـد [٨]. بـا اسـتفاده از روش هـاي پيش بيني حرکت گره ها مي توان شبکه را توسعه پذير نموده و کـارايي شبکه را بهبود بخشيد [٩]. پروتکل هاي قابل اطمينان زيادي در شبکه هاي سيار موردي ارائه شده اند که عموما به سه دسته تقسيم مي شوند:
Automatic Retransmission Request (ARQ) base
Gossip based
Forwarded error correction
به عنوان مثال پروتکل هـاي RMA [٧] ، RALM [٦] ، ReAct [١٠] به دسته ARQ تعلق دارند.
عموما ايجاد قابليت اطمينان در پروتکل هاي چندپخشي بـا مشـکلاتي همراه است که بسياري از اين عوامـل را مـي تـوان بـا انتخـاب درسـت پروتکل چندپخشي رفع کرد. ما نيز روش هـاي پيشـنهادي خـود را بـر روي پروتکل ODMRP اعمال نموده ايم . انتخاب اين پروتکل به دلايل زير صورت پذيرفت :
سادگي پروتکل ODMRP: اين پروتکل از ساختار سـاده اي برخـوردار است .
بالا بودن کارايي اين نسبي اين پروتکل نسبت به انوع مشابه به علت تشکيل مش در ايـن پروتکـل سـاختار نزديکتـري بـا تکنيـک
پيشنهادي دارد.
در اين مقاله هدف ارائـه يـک روش مسـيريابي چندپخشـي اسـت کـه قابليت اطمينان بالا داشته و بتواند عمليات انتقال اطلاعات را بـا وجـود گستردگي گروههاي چند پخشي به درسـتي بـه انجـام رسـاند. در ايـن مقاله براي دستيابي به اهداف ذکر شده يک الگوريتم مبتنـي بـر تـوري ارائه گرديده است که اين الگوريتم ضمن داشتن قابليـت اطمينـان بـالا نسبت به ساير الگوريتم هاي مورد بررسي قادر است با يک روش ساده و کارا به بهبود و بازيابي مسيرها به صـورت محلـي بپـردازد و لـذا بـدين وسيله حداکثر تلاش لازم در عمليات انتقـال اطلاعـات صـورت خواهـد گرفت . نتايج شيبه سازي نيز حکايت از اين دارد که با بکـارگيري روش ارائه شده در بازيابي محلي ، انتشار داده بهبود يافته و همچنـين قابليـت اطمينان گروهي نيز افزايش پيدا کرده است ؛ اما به دليل افـزودن بسـته هاي جديد در اين روش سربار روش پيشنهادي کمي بيشتر از پروتکل پايه است . در ادامـه ايـن مقالـه در بخـش دوم بـه بيـان کلـي پروتکـل ODMRP پرداخته و عملکـرد آن را مـورد بررسـي قـرار خـواهيم داد؛ بخش سوم روش پيشـنهادي بـراي بازيـابي محلـي بـه منظـور افـزايش قابليت اطمينان را شرح مي دهد؛ در بخش چهارم نتايج شبيه سـازي و ارزيابي قابل مشاهده است . نهايتا در بخش پنجم نتيجه گيري و کارهاي آينده بيان خواهد شد.
٢- تحليل و بررسي عملکرد پروتکل ODMRP
در اين بخش به معرفي پروتکـل ODMRP کـه يکـي از پروتکـل هاي مهم چندپخشي مي باشـد خـواهيم پرداخـت . پروتکـل ODMRP توسط آزمايشگاه WAM در دانشگاه UCLA طراحي شده اسـت [۱۱] .
اين پروتکل يک پروتکل چندپخشي و اول منبع مي باشـد يعنـي منبـع شروع کننده تشکيل گروه ها مي باشد. همچنين اين پروتکـل بـه روش مبتني بر درخواست ، کار مي کند. اين پروتکل از مفهوم گـروه جلوبرنـده براي ساختن يک توري ارسال کننده براي هر گروه چندپخشي اسـتفاده مي کند. مهمترين ويژگي هاي اين پروتکل عبارتند از: سربار کم حافظه ، استفاده از مسيرهاي نو وکوتاهترين مسيرها به دليـل اسـتفاده از پيـام - هايي که مبدا براي عضو گيري در کل شبکه منتشر مي کند، اسـتحکام براي حرکت گره ها، نگهداري و بهـره بـرداري از مسـيرهاي چندگانـه و تکراري ، قابليت افـزايش تعـداد گـره هـاي شـبکه ، عـدم وابسـتگي بـه پروتکلهاي مسيريابي تک پخشي .
و از معايب اين پروتکل مي توان به موارد زير اشـاره کـرد: ارسـال تکراري داده به علت پيکربندي توري ، وابستگي ترميم مسير به پيامهاي درخواست عضويت کـه متناوبـا از سـوي منبـع منتشـر مـي شـوند. در پروتکل ODMRP، عضويت گره ها در گـروه ، تشـکيل و بـروز رسـاني مسيرهاي چندپخشي بوسيله منبع و ارسال مکرر پيامهايي صورت مـي گيرد. هنگاميکه يک منبع چندپخشي داده اي براي ارسال داشته باشد، يک بسته درخواست عضويت را در شبکه منتشر مـي کنـد، ايـن بسـته متناوباً تا زمانيکه منبع بسته اي براي ارسال داشته باشد منتشر مي شود.
از آنجاييکه مسيرها تنها زماني تشکيل مي شوند که به آنها نيـاز داشـته باشيم اين پروتکل يک پروتکل مبتني بر درخواست است . وقتي يک گره بسته درخواست عضويت را دريافت کند، شماره گروه چندپخشي ، شماره منبع ، و شمارنده بسته را در جدولهاي خود جستجو مي کند، اگر بسـته تکراري نباشد و تعداد گره هايي که بسته از آنها عبور کرده است از حـد مجاز تجاوز نکرده باشد، بسته را بـه جلـو هـدايت مـي کنـد، همچنـين شماره گره قبلي که بسته از آنجا آمده اسـت را در داخـل جـدول خـود ذخيره مي کند تا از اين گره بـراي تشـکيل جـدولهاي پاسـخ عضـويت استفاده کند.
وقتيکـه بسـته درخواسـت عضـويت بـه يـک گيرنـده چندپخشـي مي رسد، گره گيرنده يک رکـورد جديـد را بـراي ايـن منبـع در جـدول الحاقي خود ايجاد و يا اطلاعات موجود قبلي از اين گروه را بروز مي کند.
سپس گيرنـده چندپخشـي يـک پيـام پاسـخ عضـويت (جـدول الحـاقي خودش ) را براي همسايگانش ارسال مي کند. وقتي يک گره يـک پاسـخ عضويت را دريافت کند، بررسي مي کند که آيا آدرس گره بعـدي کـه در يکي از سطرهاي جدول قرار داده شده است با آدرس خـودش مطابقـت دارد يا خير. اگر چنين رکوردي پيدا شد، گره مي فهمد که در مسير بين مقصد و منبع قرار دارد و بنابراين يکي از گره هاي گروه جلوبرنده است و پرچم گروه جلوبرنده خود را بالا مي برد. سپس جـدول الحـاقي خـود را که با استفاده از رکوردهاي تطبيقي ساخته است منتشر مي کند. بـدين طريق ، اين جدول بوسيله هر عضو گروه جلوبرنـده منتشـر مـي شـود تـا . ايـن فرآيند وقتيکه از طريق کوتاهترين مسير بـه منبـع گـروه برسـد مسيري از منبع به هر گيرنده برپا مي کند و يک توري از گره هـا ايجـاد مي شود. در شکل ۲ مفهوم گروه جلوبرنده کاملاَ مشـخص شـده اسـت اين گروه شامل مجموعه اي از گره ها است که مسئول ارسـال بسـته هـا براي مقصد خاصي هستند، لازم به ذکر است کـه در صـورتي کـه گـره گيرنده اي در طول مسير ارسال براي گره دريافت کننـده ديگـري قـرار داشته باشد مي تواند به عنوان گره جلوبرنده نيـز مطـرح شـود. در ايـن پروتکل اگر گره اي بخواهد به يک گروه چندپخشي خاصـي بـه عنـوان گره منبع بپيوندد، کافيست زمانيکه بسته داده اي براي ارسال دارد يـک پيام درخواست عضويت را ارسال نمايد. از آن پس ، اين بسته به صـورت متناوب تا وقتيکه گره ، داده اي براي ارسال داشته باشد، ارسال مي گردد و گره هاي ديگر نيز مي توانند عضو گروه شوند. در اين پروتکل نيـاز بـه ارسال هيچ بسته صريح کنترلي براي ترک يک گروه نمي باشد. اگر يـک منبع چند پخشي بخواهد گروه را ترک کند، ديگر هيچ بسته درخواست عضويتي را منتشر نمي کند همچنين اگر يک گـره گيرنـده ، بخواهـد از گروه بيرون رود کافيست فقط به بسته هاي درخواسـت عضـويت پاسـخ ندهد.
شکل (۲): مفهوم گروه جلوبرنده
٢-١- بررسي ODMRP در شبيه سازي
در اين بخش براي آشنايي بيشتر بـا عملکـرد پروتکـل ODMRP
اين پروتکل را با سناريوهاي مختلف شبيه سازي نموده ايم . شبيه سازي با استفاده از نرم افزار GloMoSim انجام گرفته است . اين نرم افـزار در دانشگاه UCLA براي شبيه سازي شبکه هاي سيار مـوردي طراحـي و به صورت رايگان منتشر شده اسـت ، تقريبـا ۲۱% شـبيه سـازي بـرروي شبکه هاي سيار موردي در گروههاي تحقيقاتي با اسـتفاده از ايـن نـرم افزار صورت مي پذيرد که پس از شبيه ساز NS٢ (۳۵%) از نظر ميـزان کاربرد در اين شبکه ها در رده دوم قرار دارد[۱۲] . در اين شبيه سازي اندازه بسته هاي داده ۵۱۲ بايت ، پروتکل دسترسي به واسط ۸۰۲.۱۱ ، مدل راه رفتن به صورت راه رفتن تصادفي بوده و مدل قرار گرفتن گـره ها نيز به صورت تصادفي انتخاب شده است . فضاي شبيه سازي ۷۰۰ در ۷۰۰ متر مربع و تعداد گره ها را نيز ۳۰ در نظر گرفتيم . شعاع راديـويي گره ها ۲۰۰ و ۲۵۰ متر و مدت زمان شبيه سازي ۳۰۰ ثانيه مي باشد.
