بخشی از مقاله
مروری بر پروتکل های مسیر یابی مبتنی بر مکان شبکه های بین خودرویی VANET
چکیده
شبکه های بین خودرویی (VANET) که با هدف ایمنی بین خود رو ها مورد استفاده قرارمی گیرند ساختار خاصی نداشـته و در آن گره های تشکیل دهنده شبکه , خودرو های در حال حرکت هستند . با توجه به رشد روز افـزون تعـداد خودروهـا در جـاده هـا و محیطهای شهری , از مسائل چالش بر انگیز در این حوزه, مسیر یابی انتشار داده می باشد. یکی از مهمترین روش های مسیر یابی در شبکه های ,VANET مسیر یابی مبتنی بر مکان می باشد .که شامل پروتکل های GPCR , GPSR , LAR و STBR می باشد در این تحقیق با استفاده از نرم افزار شبیه سازی NS-2 نقاط ضعف و قوت پروتکل های ذکر شده مسیر یابی مبتنی بر مکان مقایسه شده است. نتایج اولیه بدست آمده این تحقیق نشان می دهد که اگر شاخص " تحویل بسته " مد نظر باشد , پروتکـل GPCR بهتـرین عملکرد و چنانچه شاخص "تاخیرانتها به انتها ", پروتکل GPSR کارایی بالاتری از خود نشان می دهد.
کلمات کلیدی
ارزیابی کارایی , مسیر یابی مبتنی برمکان , شبکه های VANET
-1 مقدمه
شبکه های (VANET ) vehicular ad-hoc network زیر مجموعه ای از شبکه های MANET می باشند , که می توانند جهت ارتباط در سیستمهای ITS مورد استفاده قرار می گیرد. در واقع VANET یک نمونه شبکه سـیار مـوردی اسـت کـه بـرای برقـراری ارتباط بین خودرو ها و همچنین وسایل کنترل جاده ای ایجاد شده
است . هدف اصلی VANET فراهم آوری امنیـت و راحتـی بـرای سـر نشینان خودرو می باشد. هر وسیله نقلیه در شـبکه VANET هماننـد یک گره در شبکه Ad-hoc است و قادر به دریافت و ارسال پیـام هـای دیگران از طریق شبکه بی سیم خواهد بود. شبکه های VANETدارای معماری و ویژگی های خاصی هستند.
- سلولی: VANET ها می توانند دروازه های ثابت و نقـاط دسترسـی WLAN را در تقاطع های ترافیکی برای اتصـال بـه اینترنـت اسـتفاده کرده و اطلاعات ترافیکی را جمع کنند تا بتوانند برای مسیر یابی از آن ها استفاده کنند. پیکر بندی ارتباط بین خودرو و ایستگاه کنار جاده ای نشان دهنده ی همه پخشی , تک پرشی است . در واقع جایی است که ایستگاه کنار جاده ای پیام پخشی, پیـام را بـرای همـه اتومبیـل هـای مجاور و مجهز به گیرنده می فرستد.[1]
- موردی: همه خودروها و وسایل بی سیم کنار جاده ای می تواننـد برای اجرای ارتباطات بین دو خودرو و بدست آوردن اهداف معینی مثل گذر گاه های بن بست ( یک گذر گاه بدون چراغ راهنمایی) یک شـبکه موردی متحرک تشکیل دهند. پیکر بندی ارتبـاط بـین خـود رویـی از روش همه پخشی / تک پخشی , چنـد پرشـی (Multi Hop) اسـتفاده می کند تا اطلاعات مربوط بـه ترافیـک را از طریـق چنـدین پـرش بـه گروهی از گیرنده ها انتقال دهد.[1]
- ترکیبی : از ترکیب شبکه موردی و سلولی با هم ایجاد شده است . در شبکه های VANET فرستادن پیام از یک خودرو به خـودرو دیگـر یک مسئله بحرانی است زیرا در صورت بروز تصادف فرسـتادن پیـام در کوتاهترین زمان یک مسئله حیاتی است و در صورت دیر رسیدن پیـام اخطار , نتایج جبران نا پذیری را به دنبال خواهد داشت. [1]
تصمیم راننده , سـرعت بـالا و حرکـت مـداوم خودروهـا خصوصـیات منحصر بفردی را در این شبکه ها ایجاد کرده است . بنـابر ایـن مسـیر یابی برای انتشار داده ها در این شبکه ها مسئله اساسی است. طبق یک دسته بندی جدید و کاربردی پروتکل های مسیر یابی شبکه های بـین خودرویی را به هشت دسته تقسیم کرده انـد : مـوردی تـک مسـیره , مــوردی چنــد مســیره , مبتنــی برمکــان , مبتنــی بــر کلاســتر, چنــد بخشی ,همه پخشی , مسیر یابی مبتنی برتحمل پذیری تاخیر و مسـیر یابی مبتنی بر کیفیت خدمات . از میان پروتکلهای موجود برای شـبکه های بین خودرویی , یکی از مهمترین آن هـا مسـیر یـابی مبتنـی بـر مکان می باشد .[2 ]
در این مسیر یابی حرکـت گـره هـا در VANETمعمـولاً محـدود بـه حرکت های دو جهتی در طول جاده هـا و خیابـان هاسـت. بنـابر ایـن روشهای مسیر یابی که از اطلاعات مکان یابی جغرافیایی بدست آمده از نقشه های خیابان , مدلهای ترافیکی اسـتفاده مـی کننـد, مـی تواننـد مسیر یابی بین خود روها را به آسانی انجام دهند. مسیر یابی مبتنی بـر مکان به عنوان یک نمونه مسیر یابی امیـد بخـش بـرای VANET هـا شناخته می شود. تحقیقـات متعـددی در خصـوص مسـیر یـابی هـای مبتنی بر مکان در شبکه های VANET صورت گرفته است. به عنـوان مثال در مرجـع3 بـه مقایسـه دو پروتکـل GPSR وAODV تحـت شاخص های متعارف شبکه های متحـرک پرداختـه و برتـری پروتکـل GPSR را نشان داده است.[3]
در مرجع 4 به بررسی ارزیابی کارایی پروتکل LAR در سناریو بزرگراه پرداخته و نشان داده شده است که پروتکل در سناریو بزرگـراه کـارایی مناسبی دارد.این مقاله تعدادی از پروتکل های پر کـاربرد مسـیر یـابی مبتنی بر مکان در شبکه هایVANETرا از نظر چنـد شـاخص مـورد ارزیابی قرار میدهد.[4]
در بخش 2 ایـن مقالـه, چهـار پروتکـلLAR , GPCR , GPSR و STBRمعرفی شده و در بخش 3 ارزیابی پروتکل های مسیر یـابی و در بخش 4 نتایج شبیه سازی را ملاحضه کرده و نتیجه گیری در بخـش 5 بیان می شود.
-2 معرفی پروتکل های مسیر یابی
با وجود این که تاکنون پروتکل های مسیر یـابی زیـادی در مسـیر یابی های مبتنی بر مکان شبکه VANET معرفی شده اند.جـدول (1) امـا پروتکـل هـای مسـیر یـابی LAR ,GPCR , GPSR و STBR بیشترین کاربرد را در این شبکه ها داشته اند. در این بخش بـه معرفـی اجمالی این چهار پروتکل مسیر یابی مبتنی بـر مکـان در شـبکه هـای VANET می پردازیم .
-1-2پروتکل مسیر یابی GPSR
روش GPSR یکی از مشهورترین پروتکل هـای مبتنـی بـر مکـان است. در این روش برای ارسال بسته داده, گره مبدأ اطلاعات مکان یابی گره مقصد را همراه با بسته داده می فرسـتد ایـن گـره اطلاعـات گـره ارسال کننده را قادر می سازد تا یک همسایه را که از نظـر جغرافیـایی نزدیکترین گره به گره مقصد می باشد را به عنوان گره بعـدی انتخـاب کند. در این پروتکل دو روش برای ارسال بسته ها وجود دارد:
ارسال حریصانه (هدفمند): این روش که بیشتر در جاده ها استفاده می شود, گره ای به عنوان همسایه انتخاب می شود که از نظـر جغرافیـایی نزدیکترین گره به مقصد اسـت. در روش حریصـانه ابتـدا گرافـی بـرای ساختن تو پولوژی مدار ساخته می شود, سپس پروتکل مسیر یابی روی آن اجرا می شود. این روش در مواردی که موانعی مثل ساختمان هـا و درخت هـا ارتبـاط مسـتقیم بـین گـره هـا را غیـر ممکـن مـی سـازد, محدودیت دارد.
ارسال محیطی( دایره ای): در جایی که امکان اسـتفاده از روش ارسـال حریصانه وجود نداشته باشد از این روش استفاده میشـود و در واقـع از این روش زمانی استفاده می شود که ارسال هدفمند با شکست مواجـه شده باشد. این مسئله بدان معناست که موقعی که هیچگونه گره ای در نزدیکترین بخش مجاور به مقصد وجود ندارد از روش ارسـال محیطـی استفاده می شود. ارسال محیطی از قانون دست راست استفاده می کند. در قانون دست راست مناطق عادی از طریق پیمـودن مسـیر درجهـت عقربه های ساعت برای رسیدن به فاصـله خاصـی اسـتفاده مـی کننـد. زمانی که ارسال بسته از طریق گره منبع صورت می گیرد ایـن کـار در جهت عقربه های ساعت شامل گره مقصد می شود تا دوباره بـه همـان گره منبع برسد.[5]
-2-2 پروتکل مسیر یابی GPCR
در GPCR تصمیم گیری های مسـیر یـابی فقـط در تقـاطع هـا صورت می گیرد. گره هایی که در داخل تقاطع ها قرار دارند, هماهنـگ کننده ها نامیده می شوند. یـک هماهنـگ کننـده بـه صـورت دوره ای اطلاعات موقعیتی خود را به سایر هماهنگ کننده ها ارسال مـی کنـد. یک گره به یکی از دو روش زیر مشخص می شود که هماهنـگ کننـده هست یا نه.
روش اول تعیین هماهنگ کننده به عنوان روش جـدول محـور نامیـده می شود. در این روش گره ها به صورت دوره ای پیام هـای رادیـویی را که حاوی اطلاعات موقعیتی خود گره و آخرین موقعیت از بخـش هـای مجاور را دارند, انتقـال مـی دهنـد. از طریـق گـرفتن ایـن پیـام هـای رادیویی , یک گره اطلاعاتی راجع بـه موقعیـت خـود و موقعیـت تمـام بخش های مجاور به دست می آورد.
روش دوم( روش ضرایب همبستگی) برای شناسایی هماهنگ کننده ها ازپیام رادیو یی اسـتفاده نمـی کنـد و در عـوض هـر گـره از اطلاعـات موقعیتی خود و اطلاعات موقعیتی بخش هـای مجـاور بـرای محاسـبه ضریب همبستگی استفاده می کند که البته این کار با توجه بـه بخـش های مجاور گره صـورت مـی گیـرد. اگـر ضـریب همبسـتگی در میـان موقعیت بخش های مجاور گره وجود داشته باشد, نشان مـی دهـد کـه گره در خیابان قرار دارد و اگر هیچ گونـه ضـریب همبسـتگی در میـان موقعیت های بخش های مجاور گره وجود نداشته باشد, نشان می دهد که گره داخل بخش های عرضی (تقاطع) قرار دارد. تحقیقات نشان داده است که روش ضـریب همبسـتگی در مقایسـه بـا روش جـدول محـور عملکرد بهتری دارد.[6]
-3-2 پروتکل مسیر یابی LAR
LAR پروتکلی است که بر مبنای DSR بنا نهاده شده است. ایـن پروتکل از اطلاعات مکانی به منظور کاهش سربار در شبکه ی Ad-hoc استفاده می کند. عموماً LAR برای اطلاعات مکـانی از GPS اسـتفاده می کند. به منظور کاهش پیچیدگی پروتکل فرض می شود تمـام گـره ها موقعیت دقیق خود را می دانند یعنی تفاوت موقعیـت دقیـق گـره و موقعیت اعلام شده توسط GPS در نظـر گرفتـه نمیشـود هـم چنـین فرض بر این است که گـره هـا در صـفحه حرکـت مـی کننـد. در ایـن پروتکل حرکت گره ها در دو منطقه بررسـی مـی شـود: منطقـه مـورد انتظار و منطقه در خواستی.
منطقه مورد انتظار: در ابتدا فرض می شود منبع می خواهـد مقصـد را پیدا کند و از قبل موقعیت آن را می داند. منطقه مورد انتظار مربوط به گره مقصد از نقطه نظر گره منبع منطقه ای است که منبع انتظـار دارد مقصد در آنجا واقع شده باشد.
منطقه درخواستی: مجدداً فرض می شود منبع می خواهد مسـیری بـه مقصد بیابد. گره منبع منطقه ای را به عنـوان منطقـه ای در خواسـتی مشخص می کند و سپس گره منبع مثـل پروتکـل انتشـاری اقـدام بـه ارسال در خواست مسیر می کند با این تفاوت که تنها گره هایی که در منطقه در خواستی قرار دارند این بسته را جلو می برند.[7]
-4-2 پروتکل مسیر یابی STBR
در پروتکل STBR یکی از گره ها در تقاطع به عنوان گـره اصـلی انتخاب میشود که مسئول بررسی اتصالات بـه تقـاطع هـای بعـدی بـه طرف بالا یا پایین است. در حیطه ارسال از هر گره اصـلی, یـک سـری اطلاعات اتصالی برای اتصالات مجاور وجود داشته و آن بـه خـاطر ایـن است که تمام گره های اصلی , تمام اطلاعات اتصالی گـره هـای اصـلی دیگر را دارند. بنابر این هر گره اصلی دارای یک جدول مجـاور اتصـالی دو سطحی است. سطح اول از طریق اتصالات مجاور با گره های متقاطع مستقیم است.و سطح سطح دوم همان گره های متقاطع مستقیم آن از طریق اتصالات مجاور آنها با گره های متقاطع خود آن می باشـد. نکتـه اینکه در STBR بسته ها بر اساس فاصله جغرافیـایی شـان نسـبت بـه خیابان ها مسیر یابی می شوند که مقصد در آن قرار دارد.[8]
-3 ارزیابی پروتکل های مسیر یابی
در این مقاله برای ارزیابی کارایی هار پروتکل مسیر یابی مبتنی بر GPCR , GPSR , LAR ) و ( STBR از دو شاخص اصـلی اسـتفاده شده است.
- 1 نسبت تحویل بسته: نسبت تحویل بسته بین تعداد بسته هـای داده ای دریافت شده و تعداد بسته های ارسال شده . این تعداد مـوثر بـودن پروتکل را در تحویل داده ها به گیرنده های خواسته شده بین شبکه ها را نشان می دهد.
- 2 میانگین تاخیر انتها به انتها : نسبت اختلاف زمانی بین هـر بسـته GBR ارسالی و دریافتی به کل اختلاف زمان بر کل تعداد بسـته هـای دریافت شده ی . GBR
-1-3 محیط شبیه سازی
