پروتکل مسیریابی CGSR در شبکه های ادهاک موبایل

پروتکل مسیریابی CGSR در شبکه های ادهاک موبایل

پروتکل مسیریابی CGSR یا همان cluster head gateway switch routing protocol پروتکل سلسله مراتبی دیگری است که گره ها با یکدیگر گروه بندی شده و تشکیل خوشه می دهند و پروتکل مسیریابی DSDV را به عنوان یک طرح پایه ای مسیریابی بکار می برد و بنابراین مانند الگوریتم DSDV هزینه های زیادی دارد.

عملکرد پروتکل مسیریابی CGSR

پروتکل مسیریابی CGSR در نوع آدرس دهی و طرح ساختاری بکار گرفته با پروتکل مسیریابی DSDV فرق دارد. به جای یک ساختار تخت، پروتکل مسیریابی CGSR یک شبکه بی سیم سیار سلسله مراتبی چند پرشی با تعدادی طرح های مسیریابی ابتکاری می باشد، اگرچه پروتکل CGSR ،DSDV را به منظور مسیریابی ترافیک از مبدأ به مقصد، با بکارگیری مسیریابی سلسله مراتبی Head-to-Gateway، تصحیح می کند.

در پروتکل مسیریابی CGSR برخلاف پروتکل مسیریابی MMWN نیازی به نگهداری سلسله مراتب خوشه نیست. به جای آن، هر خوشه با سرخوشه نگهداری می شود و گره سیاری است که به عنوان مدیر برای گره های سیار دیگر در خوشه انتخاب می شود. این گره رسانه انتقال و تمام ارتباطات داخل خوشه ای که دراین گره اتفاق می افتد را کنترل می کند.

تشکیل خوشه و انتخاب سرخوشه ها

الگوریتم های انتخاب سرخوشه، بر دو نو نوع پیشنهاد شده است :

• تشکیل خوشه بر مبنای شناسه
• تشکیل خوشه بر مبنای اتصال

هر دوی این الگوریتم ها، هم پیاده سازی متمرکز و هم توزیع شده را می پذیرد.

در الگوریتم های متمرکز، گره با کمترین عدد شناسه و یا گره با بیشترین تعداد همسایه به عنوان سرخوشه، انتخاب می شود. بنابراین تمام گره هایی که در خوشه هستند، از توجه بیشتر محروم می شوند و فرآیند انتخاب سرخوشه و تشکیل خوشه با گره های باقیمانده در شبکه تکرار می شود و این کار تا زمانی ادامه پیدا می کند که تمام گره ها تحت پوشش چند خوشه قرار بگیرند.

در الگوریتم توزیع شده خوشه بندی بر مبنای شناسه، گره ای که کمترین عدد شناسه را در آن همسایگی دارا باشد، خود را به عنوان سرخوشه انتخاب می کند. در غیر این صورت گره همسایه ای را کمترین شناسه را دارا می باشد را انتخاب می کند، مگر اینکه آن گره از وضعیت سرخوشه بودن خارج شده باشد.

در الگوریتم توزیع شده خوشه بندی بر مبنای اتصال، گره ای سرخوشه می شود که بیشترین اتصال را با همسایه های پوشش داده نشده خود داشته باشد و البته گره ای پوشش داده نشده محسوب می شود که سرخوشه ای برای خود انتخاب نکرده باشد. اگر گره ای گره دیگری را به عنوان سرخوشه خود انتخاب کند، دیگر خودش نمی تواند سرخوشه باشد. الزامات سرخوشه طبق گره ای که کمترین عدد شناسه را داشته باشد، انتخاب می شود.

مسیریابی در پروتکل CGSR

پروتکل مسیریابی CGSR در حالت کلی به صورت زیر عمل می کند که ابتدا مبدأ بسته، بسته را به سرخوشه خود ارسال می کند. از این سرخوشه بسته به گره دروازه فرستاده می شود که گره دروازه مذکور این سرخوشه و سرخوشه بعدی که در طول مسیر به مقصد وجود دارد را بهم متصل می کند. دروازه، بسته را به سرخوشه می فرستد و به همین ترتیب ادامه پیدا می كند تا سرخوشه مقصد در این روش بدست آورده شود. سپس سرخوشه مقصد بسته ای که در داخل خوشه می باشد را به مقصد ارسال می کند.

شکل 1: مثالی از مسیریابی CGSR از گره 1 تا گره 12

شکل 1 یک طرح مسیریابی CGSR را برای خوشه های همپوشان نشان می دهد. هر گره، جدولی مانند جدول 1 که در آن اعضای یک خوشه وجود دارد را نگهداری می کند. جدول اعضای خوشه، از هر گره نگاشتی به سرخوشه مربوط به آن گره دارد. گره ها، جدول اعضای خوشه را بطور دوره ای ارسال می کنند و پس از اینکه سایر گره ها آن را دریافت کردند، با استفاده از الگوریتم DSDV جداول خود را بروز می کند.

جدول 1: نمونه ای از یک ورودی جدول اعضای خوشه

علاوه بر این، هر گره یک جدول مسیریابی مانند جدول 2 را هم نگهداری می کند که گام بعدی برای رسیدن به خوشه هر مقصد و معیار آن مسیر در آن مشخص شده است.

جدول 2: نمونه ای از یک ورودی جدول مسیریابی در گره 1

هر دو جدول فوق، برای پاک کردن مسیرهای قدیمی و جلوگیری از تشکیل حلقه ها، شماره ترتیبی دارند. در دریافت یک بسته، هر گره طبق جدول اعضای خوشه و جدول مسیریابی، نزدیکترین سرخوشه را در طول مسیر رسیدن به مقصد، پیدا می کند. سپس گره از جدول مسیریابی خود برای پیدا کردن گام بعدی کمک می گیرد تا بتواند به سرخوشه انتخاب شده در گام اول برسد و بسته را به آن ارسال کند.

مزیت پروتکل مسیریابی CGSR

مهمترین مزیت پروتکل مسیریابی CGSR این است که فقط مسیرهای به سمت سرخوشه نگه داشته می شوند و این موضوع بدلیل سلسله مراتبی بودن مسیریابی می باشد و سرباره کمتری در مقایسه با الگوریتم flooding اطلاعات مسیریابی داریم ولی سرباره دیگری برای نگهداری خوشه ها داریم.

نقاط ضعف پروتکل مسیریابی CGSR

1. بعضی گره ها مثل سرخوشه و گره های دروازه، نسبت به سایر گره ها محاسبات بیشتر و مسئولیت بیشتری در ارسال اطلاعات دارند.
2. مشکل دیگر الگوریتم مسیریابی CGSR هزینه های بالای ناشی از نگهداری خوشه می باشد، مخصوصاً اینکه هر گره نیاز دارد که بطور متناوب جدول اعضای خوشه را ارسال کند و بر اساس تغییرات پیش آمده، آن را بروز کند.