بخشی از مقاله
پروتکل های مسیریابی در vanet
چکیده: vanet یک فناوری تقریبا جدید است که برخی از ویژگیهای منحصر به فرد آن باعث تفاوت هایی با سایر شبکه های adhoc شده است. Vanet یک شبکه ارتباطی بی سیم خودسامانده و مستقل است که در آن گره ها خودروها هستند. در عصر مدرن وسایل نقلیه با استفاده از vanet قادر به برقراری ارتباط با یکدیگر به منظور جلوگیری از تصادفات، کنترل سرعت و ترافیک، عبور وسایل نقلیه اضطراری و ... هستند. ماهیت داینامیک و تحرک بالای گره ها در شبکه های vanet باعث گردیده است که مسیریابی در آن ها بعنوان مسئله ای بسیار مهم مطرح گردد. در این مقاله سعی خواهیم کرد تا الگوریتم های مسیریابی در این نوع شبکه را مورد بررسی قرار داده و براساس معیارهای تعریف شده، چارچوب مقایسه ای جدیدی برای الگوریتم های مسیریابی ارائه دهیم.
واژگان کلیدی: الگوریتم مسیریابی، توپولوژی شبکه، vanet
-1 مقدمه
شبکههای vanet یک نوع خاص شبکههای MANETs هستند که نودهای آن خودروها هستند. هر خودرو می تواند در هر لحظه خودروهای اطرافش را شناسایی کرده و با اتصال به آنها یک شبکه تشکیل داده و ارتباطات لازم را برقرار کند. تفاوت اصلی شبکههای vanet با شبکههای سلولی و اختصاصی این است که هیچ ایستگاه یا نود مرکزی، مدیریت و کنترل شبکه را بر عهده ندارد و شبکه از یک سری خودرو تشکیل شده که متحرک بوده و جای ثابتی ندارند و هیچیک نقش روتر یا اکسس پوینت را بازی نمیکنند. vanet یکی از اجزای اصلی سیستمهای حملونقل هوشمند است و در چند سال اخیر تحقیقات و پژوهش های زیادی روی آن انجام شده است و امیدهای فراوانی به آن وجود دارد. علت این اهمیت نیز ارتباط مستقیم این نوع شبکهها با ایمنی خودروها و ترافیک است.
به علت تحرک بالای گره ها توپولوژی شبکه در هر لحظه از زمان ممکن است دستخوش تغییراتی شود بنابراین مسیریابی بعنوان مسئله مهمی در این نوع شبکه مطرح می گردد. پروتکل مسیریابی در vanet رویه ای است که شامل ایجاد یک مسیر، تصمیم گیری در ارسال بسته ها و حفظ مسیر و بازیابی در صورت شکست یک مسیر است. در این مقاله به بررسی این موضوع خواهیم پرداخت.
1
-2 دسته بندی الگوریتم های مسیریابی در vanet
تحرک گره ها در vanet با سایر شبکه های ad-hoc متفاوت است، بنابراین طراحی یک پروتکل مسیریابی برای vanet دارای پیچیدگی هایی است که تمام جوانب این نوع شبکه را باید در نظر بگیرد. توپولوژی شبکه مدام تغییر می کند و همچنین پهنای باند محدود است، بنابراین علاوه بر ایجاد مسیر حفظ مسیر بین گره ها مسئله ای حیاتی است. تغییر پویای توپولوژی باعث کوتاه شدن زمان موثر مسیریابی و کاهش نرخ استفاده از اطلاعات مسیریابی می گردد، بنابراین به نظر می رسد پروتکل های مسیریابی براساس تقاضا رفتار بهتری از خود نشان دهند. این پروتکل ها به طور عمده شامل دو فرآیند کشف مسیر و حفظ مسیر است. گره منبع بسته های درخواست مسیر را بوسیله flooding در شبکه broadcast می کند. وقتی که یک بسته درخواست مسیر به مقصد می رسد، گره مقصد یک بسته پاسخ مسیر را به گره منبع ارسال می کند و بدین ترتیب یک مسیر معکوس بین منبع و مقصد برقرار می گردد. زمانی که توپولوژی گره ها تغییر می کند ممکن است بعضی از لینک ها شکسته شوند که در این وضعیت عملیات تعمیر و نگهداری مسیر شروع خواهد شد.
الگوریتم های مسیریابی vanet را می توان به 5 دسته تقسیم بندی کرد:
-1 الگوریتمهای مسیریابی بر پایه توپولوژی
-2 الگوریتمهای مسیریابی بر پایه موقعیت
-3 الگوریتمهای مسیریابی بر پایه کلاستر
-4 الگوریتمهای مسیریابی بر پایه geocast
-5 الگوریتمهای مسیریابی بر پایه broadcast
-1-2 پروتکل های مسیریابی بر پایه توپولوژی
پروتکل های مسیریابی بر پایه توپولوژی از اطلاعات داخلی شبکه برای ارسال بسته ها از منبع به مقصد استفاده می کنند. پروتکل های مسیریابی بر پایه توپولوژی می توانند به دو دسته proactive (بر اساس جدول) و reactive (براساس تقاضا) تقسیم بندی شوند. در مسیریابی proactive بسته های کنترلی به طور مداوم میان گره ها پخش می گردند تا پیوند بین هر جفت گره را حفظ کنند حتی اگر برخی از مسیرها هرگزمورد استفاده قرار نگیرند . سپس جدولی با ورودیهایی که گره های بعدی را به سمت یک مسیر خاص نشان می دهند تشکیل می شود. مزیت استفاده از این روش این است که نیازی به کشف مسیر نیست و جدول گره ها همیشه در دسترس است.
مزایا:
-اکتشاف مسیر مورد نیاز نیست.
-برای برنامه های کاربردی با زمان واقعی مناسب است. معایب:
- مسیرهای بلااستفاده بخش قابل توجهی از پهنای باند موجود را تلف می کنند.
[1] FSR یک پروتکل مسیریابی proactive است که در آن هر گره اطلاعات گره های همسایه را جمع آوری می کند و سپس جدول مسیریابی را بر اساس آن ها تشکیل می دهد. این پروتکل بر پایه الگوریتم link state قرار دارد. FSR پروتکل مسیریابی کارآمدی است که یک نقشه توپولوژی در هر گره نگهداری می کند و اطلاعات لینک ها را بوسیله ارتباط با همسایگان در شبکه به روزرسانی می کند. علاوه بر این، اطلاعات اتصال بسته به فاصله تا گره پخش کننده فعال broadcast می شوند. گره هایی که دورتر هستند بسته های broadcast را با فرکانس پایین تر دریافت می کنند که این امر منجر به کاهش سربار می شود.
پروتکل های reactive به این دلیل پروتکل های بر اساس تقاضا نامیده می شوند که هنگامی که یک گره نیاز به برقراری ارتباط با گره های دیگر را دارد، اکتشاف مسیر شروع می شود و بهمین دلیل ترافیک شبکه کاهش پیدا می کند. در این رویه مسیریابی تنها زمانی که نیاز به ارتباط گرهی با گره های دیگر
2
باشد یک مسیر بین آنها ایجاد می شود که این امر منجر به کاهش سربار شبکه می شود. این نوع مسیریابی عموما بوسیله بسته های پرس و جو در جستجوی مسیر اقدام به کشف مسیر می نماید.
مزایا:
- برای به روزرسانی جداول مسیریابی نیازی به flooding به صورت دوره ای در شبکه وجود ندارد و هر زمان که نیاز باشد flooding صوت می پذیرد.
-موجب صرفه جویی در مصرف پهنای باند می شوند. معایب:
-برای پیدا کردن مسیر latency بالا است.
-در صورتی که flooding بیش از حد مورد نیاز باشد موجب اختلال در ارتباطات شبکه خواهد شد.
پروتکل مسیریابی [2] AODV یک پروتکل مسیریابی reactive است که هنگامی که یک گره نیاز به ارسال بسته ها داده داشته باشد یک مسیر را ایجاد می کند.
مهمترین پروتکل های مسیریابی بر پایه توپولوژی عبارتند
از:
FSR، AODV، PGB، DSR و .TORA
-2-2 پروتکل های مسیریابی بر پایه موقعیت
در مسیریابی بر پایه موقعیت هر گره موقعیت جغرافیایی خود و همسایه اش را بوسیله سرویس هایی مانند GPS در اختیار دارد. پروتکل های این دسته هیچ جدول مسیریابی را ذخیره نمی کنند و هیچ تبادل اطلاعاتی با همسایگان وجود ندارد و برای مسیریابی از اطلاعات دستگاه GPS استفاده می شود. در این دسته از پروتکل ها، موقعیت مقصد در هدر بسته های اطلاعاتی گره منبع ذخیره می گردد و موقعیت گره های همسایه تک هاپ به صورت دوره ای فرستاده می شود. از آنجا که پروتکل های مسیریابی جغرافیایی اطلاعات ارتباطی را مبادله نمی کنند و مسیرهای برقرار شده را مشابه مسیریابی proactive و reactive بر پایه موقعیت حفظ نمی کنند، آنها در محیط های پویای vanet عملکرد بهتری از خود نشان می دهند. بعبارت دیگر، مسیر مورد نظر براساس موقعیت جغرافیایی همسایه مشخص و بر طبق آن بسته هدایت می شود و هیچ نیازی به تبادل اطلاعات اتصال در تشکیل مسیر وجود ندارد.
مزایا:
-کشف و مدیریت مسیر مورد نیاز نیست. -مقیاس پذیر هستند.
-برای الگوهای حرکتی high مناسب هستند. معایب:
