شبکه­های بی­سیم توری و پروتکل­های مسیریابی مربوطه

شبکه های بی سیم کاربرد بسیاری دارند, سهولت و سرعت ساخت, ازمهمترین مزیت این نوع شبکه ها است با توجه به انتقال داده در محیط باز از طریق هوا و محدودیت های موجود از جمله پهنای باند محدود, انرژی محدود, دامنه­ی ارسال محدود و ­, کنترل ازدحام و تداخل و پروتکل­های مسیریابی متفاوت از شبکه­های سیمی هستند

شبکه‌های بی‌سیم کاربرد بسیاری دارند، سهولت و سرعت ساخت، ازمهمترین مزیت این نوع شبکه‌ها است. با توجه به انتقال داده در محیط باز (از طریق هوا) و محدودیت های موجود از جمله پهنای باند محدود، انرژی محدود، دامنه­ی ارسال محدود و...­، کنترل ازدحام و تداخل و پروتکل­های مسیریابی متفاوت از شبکه­های سیمی هستند.

در این مقاله به معرفی شبکه­های بی­سیم توری که ترکیبی از شبکه­های ad hoc و سلولی هستند، می­پردازیم. با توجه به طبیعت ترکیبی، اعمال پروتکل­های مسیریابی مربوط به سایر شبکه­های بی­سیم به این نوع شبکه، غیرممکن است، زیرا پروتکل­های مسیریابی باید ترکیبی از مسائل مربوط به شبکه­های ad hoc و سلولی را در نظر بگیرند. در ادامه برخی از پروتکل­های مسیریابی و معیارهای مورد استفاده ، بررسی­می­شوند.

۱) مقدمه

شبکه سلولی، شامل تعداد زیادی کاربر با پایانه­ها­ی سیار، ایستگاههای اصلی، و کنترل کننده­ی مرکزی است که توسط خطوطی با سرعت بالا، (سیمی یا microwave) به یکدیگر یا دنیای بیرون متصل می­شوند. داده­های کاربران از طریق نزدیکترین ایستگاه اصلی ارسال می­شوند، در نتیجه انتقال داده­ی چند­گامه در محیط بی­سیم اشتراکی وجود ندارد. پایانه­های سیار مسئولیت بسیار کمی دارند و تمامی تصمیمات مهم مانند زمان ارسال هر پایانه، فرکانس ارسال، برش زمانی، کد مورد استفاده، انرژی موردنیاز و.. بطور مرکزی و نوعا در کنترل کننده­ی شبکه اتخاذ می­شود. در صورت خرابی یکی از ایستگاههای اصلی، همه­ی کاربران مجاور آن، ارتباط خود را با شبکه از دست می­دهند.(شکل ۱ -الف)

شبکه­های ad hoc برخلاف شبکه­های سلولی دارای هیچ زیرساخت اضافه­ای، مانند ایستگاههای اصلی، کنترل کننده مرکزی و... نیستند. بنابراین عملیات شبکه، بطور توزیع شده و غیر­متمرکز انجام می­شود. علاوه­براین داده در چند­گام مسیریابی شده و امکان ادامه کار، پس از رخداد خطا وجود دارد.(شکل ۱-ب) این نوع شبکه­ها، به دلیل عدم وجود زیرساخت گران نیستند. بنابراین اگر نیازهای ارتباطی با استفاده از شبکه­های ad hoc رفع شود، نیازی به استفاده از توپولوژی سلولی نیست.

امکان ترکیب توپولوژی ad hoc با توپولوژی سلولی وجود دارد. مشکل زیر را در نظر بگیرید: اگر در شبکه­ی سلولی محض، یک کاربر سیار، دور از دسترس همه ایستگاههای اصلی باشد، دو راه حل وجود دارد:

▪ اگر کانالی بین کاربر و ایستگاه اصلی نباشد، تماس­های کاربر حذف خواهد شد.

▪ اگر کانال موجود بین کاربر و ایستگاه اصلی ضعیف باشد، انتقال پایانه­ی سیار با حداکثر انرژی (مصرف باتری) و انتقال ایستگاه اصلی با حداکثر انرژی (تداخل با گره­های سیار دیگر) و شاید با تخصیص پهنای باند بیشتر جبران می­شود.

هیچ یک از راه حل­های پیشنهادی مناسب نیستند.

راه حل مناسب استقرار تعدادی بی­سیم ثابت با کانال مناسب، به ایستگاه اصلی است. با این کار، احتمال برقراری ارتباط کاربران با ایستگاه اصلی، بطور مستقیم یا با استفاده از رله بالا می­رود. شبکه­ی حاصل خصوصیات شبکه­های سلولی (ایستگاههای اصلی و زیرساخت­های گران قیمت) و شبکه­های ad hoc (ارتباط چند­گامه بی­سیم از کاربر به ایستگاههای اصلی) را در خود جمع کرده است. این نوع شبکه، شبکه­ی بی سیم توری[۱] (WMN)نامیده می­شود.

۲) معماری WMN

این شبکه شامل سه نوع مختلف از اجزای شبکه است : دروازه­های شبکه، نقاط دسترسی[۲] و گره­های سیار(شکل ۲)

دروازه­های شبکه : اجازه دسترسی به زیرساخت سیمی را می­دهد. امکان استفاده از بیشتر از یک دروازه، در شبکه وجود دارد.

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

▪ گره­های سیار : محدوده­ی وسیعی از ابزارها با درجه حرکت متفاوت را دربرمی­گیرد، مانند PDA، laptop یا تلفن­های سلولی. گره­های سیار در مصرف انرژی، توانایی­های محاسباتی و انتقال متفاوتند و با اتصال مستقیم به دروازه شبکه، یا با استفاده از نقاط دسترسی به عنوان رله، با زیرساخت سیمی ارتباط برقرار می­کنند

در این نوع شبکه، انتقال داده از طریق ارتباطات بی­سیم چند­گامه انجام شده و شامل گره­های سیار، دروازه­های شبکه و نقاط دسترسی می­باشد. پهنای باند موجود وابسته به تکنولوژی شبکه زیرین بوده و دارای نرخ انتقال ۵۴ مگابیت در ثانیه است. ترافیک شامل جریانهای چندرسانه­ای است و شبکه از هزاران گره سیار پشتیبانی می­کند. علاوه بر این، دارای محدودیت­های پهنای باند بوده و نیاز به مدیریت حرکت کاربران دارد.

ـ شبکه­ی بی­سیم توری در موارد زیر با سایر شبکه­های بی­سیم تفاوت دارد:

▪ اجزای شبکه: نقش گره­های سیار به عنوان بخشی از WMN متفاوت از سایر شبکه­ها است. معماری این نوع شبکه­، بین نقاط دسترسی - مانند گره­های سیار - اتصالاتی را در نظر می­گیرد.

▪ درجه حرکت: WMNها دارای ستون فقرات بی­سیم هستند و از گره­هایی با عدم محدودیت انرژی و حرکت محدود (یا ثابت) تشکیل شده­اند، در حالی که در بعضی از شبکه­های بی­سیم چندگامه مانند MANET[۳]ها بقای انرژی و حرکت کاربران مفهوم اصلی و اولیه است.

▪ الگوی ترافیکی : الگوی ترافیکی در WMN، شباهت جزیی به شبکه­های سنسور و ad hoc دارد. مشابه شبکه­های سنسور، ترافیک داده اساسا بین کاربران و دروازه­های شبکه است، (تفاوت با شبکه­­های ad hoc). البته ترافیک می­تواند بین هر جفت از گره­های کاربران نیز باشد ( شباهت با ad hoc) .

۳) خصوصیات WMN از دید مسیریابی

با توجه به خصوصیات ذکر شده، پروتکل­های مسیریابی موجود باید برای تطابق با WMNها مجددا بررسی شوند. اختلافات اساسی وابسته به مسیریابی عبارتند از:

▪ توپولوژی شبکه : WMN دارای ستون فقرات ثابت است. بنابراین مشابهMANET ها ارتباط از طریق انتقالهای بی­سیم چند­گامه انجام می­شود. اما برخلاف MANETها حرکت گره­ها در زیرساخت ستون فقرات متناوب نیست.

▪ الگوی ترافیک : در شبکه­های سلولی و WLANها داده بین کاربران و نقاط دسترسی مبادله می شود. در WMN انتقال داده بین گره­های سیار و دروازه­های شبکه است.(کمی شباهت با شبکه­های سلولی) ترافیک بین دو گره در WMN، اگرچه اهمیت کمی دارد اما باید مورد بررسی قرار گیرد.

▪ تنوع کانال­ها : WMNها از امکان معرفی کانال­های مختلف در فرایند مسیریابی سود می­برند، که در سایر شبکه­های بی­سیم به دلیل حرکت گره­ها (MANET) یا محدودیت­های انرژی ممکن نیست. این تکنیک بطور واضح تداخل را کاهش و گذردهی را افزایش می دهد.

۴) معیارهای کارایی مورد استفاده در پروتکل­های مسیریابی

وابسته به مشخصات شبکه هر یک از پروتکل­های مسیریابی روی یکی از معیارهای کارایی تمرکز کرده­اند. لیست زیر برخی از معیارها را نشان می دهد:

▪ تعداد گام : تعداد گام ها بین مبدا و مقصد.

▪ تعداد انتقال مورد انتظار(ETX)[۴]: بیشتر مخصوص ارتباطات بی­سیم است. گم شدن داده را که به علت رقابت بر سر محیط دسترسی یا مخاطرات محیطی رخ می­دهد، محاسبه کرده و تعداد ارسال مجددها را برای انتقال موفق یک بسته در لینک محاسبه می­کند.

▪ زمان انتقال مورد انتظار(ETT)[۵]: در محاسبات خود علاوه بر پارامترهای قبلی پهنای باند لینک را نیز دخالت می­دهد.

▪ مصرف انرژی : سطح انرژی گره یک معیار مسیریابی است. اگر برخی گره­های درگیر در فرآیند مسیریابی، محدودیت انرژی داشته باشند، ممکن است به علت تمام شدن انرژی خطای مسیر رخ دهد. بیشتر در شبکه­های MANET و WMNها مهم است.

▪ دسترسی پذیری/قابلیت اطمینان مسیر : درصد زمانی را که مسیر در دسترس است، تخمین می­زند. تاثیر حرکت گره در این معیار گنجانده می­شود. به خصوص برای MANETها معیار مهمی است.

۵) معیارکیفیت مسیر در مسیریابی شبکه­های بی­سیم چند­گامه

بیشتر کارهای اخیر در زمینه­ی پروتکل­های مسیریابی برای شبکه­های بی­سیم روی گره­های سیار، توپولوژی پویا و توسعه­پذیری تمرکز کرده­اند، و توجه کمتری به یافتن مسیرهای با کیفیت بالا، در لینکهای بی­سیم شده است. معیاری که توسط اغلب پروتکل­های مسیریابی ad hoc موجود استفاده می­شود، حداقل­سازی تعداد گام است.

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

در[۳] گذردهی مسیرهایی با حداقل تعداد گام و گذردهی بهترین مسیر موجود مقایسه شده­اند. نتایج حاصل نشان داده که حداقل تعداد گام درمواردی که کوتاهترین مسیر، سریعترین مسیر نیز می­باشد، خوب کار می­کند. مسیرهای با حداقل تعداد گام آهسته می­باشند، زیرا شامل لینک­هایی با نرخ گم شدن بالا هستند که باعث می­شود پهنای باند برای ارسال مجددها استفاده شود.

معیار کیفیت پیشنهادی ETX است. این معیار مسیری با کمترین تعداد مورد انتظار ارسال را برای رسیدن به مقصد انتخاب می­کند (شامل ارسال مجددها نیز می­شود). هدف از طراحی این معیار یافتن مسیری با گذردهی بالا، علیرغم گم شدن بسته­ها می­باشد.

ETX یک لینک عبارتست از تعداد انتقال داده­های موردنیاز برای ارسال یک بسته از طریق لینک، که شامل ارسال مجددها نیز می شود. ETXمسیر حاصل جمع ETX لینک های موجود درمسیر است.

ETX یک لینک با استفاده از نرخ­های ارسال و دریافت هر لینک محاسبه می­شود. نرخ تحویل بسته ارسالی df برابر است با احتمال اینکه یک بسته داده با موفقیت به مقصد برسد، نرخ تحویل معکوس dr برابر است با احتمال اینکه بسته­ی ACK با موفقیت دریافت شود. احتمال اینکه ارسال با موفقیت انجام شده و تصدیق شود برابر است با df*dr. فرستنده وقتی اقدام به ارسال مجدد می­کند که با موفقیت تائید نشده باشد. از آنجایی که هر تلاش برای ارسال بسته می­تواند به عنوان توزیع برنولی تصور شود، تعداد ارسال­های مورد انتظار برابر است با:

این معیار تنها برای شبکه هایی با ارسال مجدد لایه­ی پیوند مانند ۸۰۲.۱۱b قابل درک است و فرض می­کند فرکانس­های رادیویی سطح نیروی ارسال ثابتی دارند. با نیروی رادیویی مختلف، بهتر است تعداد گام­ها را حداقل کنیم، بنابراین تداخل کاهش پیدا کرده و انرژی مورد استفاده با هر بسته حداقل می شود. علاوه­براین از لینکهای دارای ازدحام مسیریابی نمی­کند، بنابراین از نوسانی که گاهی اوقات معیارهای مسیریابی متناسب با بار را تحت تاثیر قرار می دهد، مانند تاخیر انتها به انتها رنج نمی­برد.

تاثیر این معیار در مسیریابی DSDV[۶] و [۷]DSR بررسی شده است[۳]. قبل از بیان نتایج حاصل مروری بر پروتکل­های عمومی DSDV و DSR داشته و تغییرات اعمالی را بیان می­کنیم.

ـ عملیات DSDV

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

هر گره بطور دوره­ای یک بسته­ی آگهی مسیر، شامل جدول مسیریابی کامل خود، منتشر می­کند. این آگهی رونوشت کامل[۸] نامیده می­شود.

هر گره دارای یک شماره ترتیب قابل افزایش است که در هر رونوشت کاملی که توسط گره ایجاد می­شود، وجود دارد.

وقتی یک گره آگهی مسیریابی گره­های دیگر را دریافت می­کند، وارده­های مسیریابی خود را بروز رسانی می­کند. هر وارده­ی مسیر دارای زمان انقضای وزن دار(WST)[۹] است. WST یک وارده­ی مسیر، عبارتست از زمان بین اولین دریافت مسیری با آن شماره­ی ترتیب و دریافت بهترین مسیر با آن شماره­ی ترتیب. این زمان با دریافت مسیری با شماره ترتیب جدید، بروز رسانی می­شود.

WST همراه با راه اندازهای بروز رسانی[۱۰] برای انتشار سریع مسیرهای مناسب شبکه استفاده می­شود. وقتی یک گره، وارده­ی مسیری را با وارده­ی دریافتی جدید جایگزین می­کند، مسیر جدید را با ارسال راه انداز بروز رسانی که تنها شامل اطلاعات تغییر یافته است، منتشر می­کند. راه اندازها، تا زمانی که دست کم ۲*WST از زمان اولین دریافت شماره ترتیب جاری گذشته باشد، ارسال نمی­شوند. این کار باعث می­شود گره­ها از آگهی مسیر جدیدی که احتمالا بعدها با مسیر بهتر جایگزین خواهد شد، اجتناب کنند. علاوه­براین، علیرغم وجود WST برای هر وارده­ی مسیر، راه اندازها با نرخی بیشتر از حداکثر نرخ تعیین شده، ارسال نمی­شوند. راه اندازهایی که تاخیر دارند، با هم دسته شده و در زمان بعدی ارسال می­شوند.

ـ تغییرات اعمالی به DSDV

اولین تغییر اعمالی در نحوه­ی استفاده­ی WST تاثیر گذاشته است. پیاده سازی DSDV تا وقتی که، زمانی برابر ۲*WST از زمان شنیده شدن مسیر نگذشته باشد، آن را آگهی نمی­کند. مطابق تفسیر ما از DSDV عمومی، زمان انتظار قبل از آگهی یک مسیر، باید وقتی که اولین مسیر از هر شماره ترتیب شنیده می­شود، آغاز شود. دومین تغییر در پیاده­سازی این است که از فیدبک سطح لینک برای تشخیص لینک­های منفصل و تولید پیام­های انفصال مسیر استفاده نمی­کند. پیام­های انفصال مسیر بهنگام انقضای وارده­های جدول مسیریابی، تولید می­شوند. سومین تغییر این است که راه­اندازها شامل مسیرهای تغییر یافته هستند و رونوشتهای کامل فقط در دوره­های مربوط به خود ارسال می­شوند. تغییر نهایی این است که یک مسیر، تا زمانیکه امکان آگهی کردن آن موجود نباشد، استفاده نمی­شود. با این تغییر بهترین مسیری که با شماره ترتیب قبلی شنیده شده است، استفاده می­شود تا زمانیکه WST مربوط به شماره ترتیب جاری منقضی شود.DSDV تغییر نیافته همواره از آخرین مسیر مورد قبول برای یک مقصد معین استفاده می کند، حتی اگر هنوز امکان آگهی آن مسیر وجود نداشته باشد.

هدف تغییر آخر اجتناب از استفاده از مسیرهایی با معیارهای بد است. برای مثال اگر یک مسیر تک­گامه نامتقارن وجود داشته باشد، یک گره همواره شماره­های ترتیب جدید در لینک تک­گامه خواهد شنید. بدون تغییر DSDV مجبور به استفاده از مسیر جدید تک­گامه هستیم.

ـ عملیات DSR

DSR پروتکل مسیریابی واکنشی است که در آن، یک گره درخواست مسیر را تنها وقتی که داده­ای برای ارسال داشته باشد، صادر می­کند. درخواست­های مسیر به شبکه تزریق شده، و هر گرهی که درخواست را دریافت می­کند، آدرس خودش را به آن الحاق کرده، و مجددا درخواست را منتشر می­کند. هر درخواست شامل یک شناسه­ی منحصر بفرد است که برای اطمینان از ارسال یکباره­ی آن استفاده می­شود. صادرکننده­ی درخواست، درخواستهای جدید به همان مقصد را، بعد از افزایش نمایی زمان back-off ارسال می­کند. درخواست­های مسیر، برای حداقل­سازی محدوده و هزینه­ی تزریق در شبکه، با افزایش مقادیر TTL[۱۱] صادر می­شوند.

مقصد در پاسخ به هر درخواست روانه­سازی دریافتی، یک پاسخ مسیر[۱۲]می­دهد. پاسخ که شامل مسیر است، مسیر معکوس را برای رسیدن به صادرکننده­ی پیام طی می­کند. گره مبدا، مسیر را با استفاده از اطلاعات پاسخ دریافتی انتخاب می­کند.

پیاده­سازی جدید نتایج پاسخ­های مسیر را در حافظه موقت لینک[۱۳] ذخیره می­کند، حافظه­ی موقت اطلاعات هر لینک را جداگانه نگه می­دارد. الگوریتم کوتاهترین مسیر دیکسترا روی حافظه­ی موقت اجرا می­شود تا بهترین مسیر انتخاب شود.

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

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

ـ تغییرات اعمالی به DSR

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

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

ـ نتایج

نتایج [۳] نشان داده که پروتکل DSDV با استفاده از معیار ETX مسیرهایی سریعتر از مسیرهای انتخابی با معیار حداقل تعداد گام را می یابد. در مواردی که گره­ها مستقیما با هم ارتباط دارند و نرخ گم شدن داده کمتر از ۵۰% است، معیار حداقل تعداد گام، بهترین مسیرهای تک گامه را انتخاب می­کند و نیازی به استفاده از معیار ETX نیست. برای حالتی که نرخ گم شدن در ارتباط مستقیم بین گره­ها زیاد است، بهترین مسیر چندگامه خواهد بود و حساسیت ETX در اختلاف بین مسیرهایی با طول یکسان، منجر به یافتن مسیرهای بهتر می­شود. ETX به دلیل بررسی نرخ گم شدن، نسبت به حداقل تعداد گام سربار بیشتری دارد ولی این سربار در مقایسه با یافتن مسیری با گذردهی بالا ناچیز است.

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

ـ مسیریابی LQSR[۱۴]

اندازه­گیری­های کیفیت لینک در ماجولی به نام لایه­ی اتصال مش MCL پیاده­سازی شده است. MCL با استفاده از نسخه­ی تغییر یافته­ای از DSR به نام LQSR مسیریابی می­کند. درایور MCL ، یک لایه­ی میانی بین لایه­ی ۲ و لایه­ی ۳ پیاده سازی کرده است. MCL برای نرم افزار لایه­ی بالاتر، به عنوان یک لینک اترنت دیگر ظاهر می­شود و برای نرم افزار لایه­ی پایین­تر، بعنوان پروتکل مسیریابی دیگری در لینک فیزیکی عمل می کند.

این طراحی دو مزیت آشکار دارد. اولا نرم افزار لایه­ی بالاتر بدون تغییر در شبکه­ی ad hoc اجرا می­شود. دوما مسیریابی ad hoc در لایه­های پیوند ناهمگن اجرا می­شود. پیاده­سازی، از اترنت مشابه لایه­های پیوند فیزیکی پشتیبانی می­کند. آداپتور شبکه­ی مجازی MCL چندین آداپتور فیزیکی شبکه را تسهیم می­کند، بنابراین شبکه­ی ad hoc در میان لایه­های فیزیکی ناهمگن بسط داده می­شود. شکل ۵ را ببینید.

آداپتور MCL آدرس اترنت مجازی ۴۸ بیتی خود را دارد، که مجزا از آدرس های لایه­ی ۲ آداپتورهای فیزیکی زیرین است.

LQSR کلیه­ی توابع اصلی DSR شامل کشف و نگهداری مسیر را پیاده­سازی می­کند. از یک حافظه موقت لینک، به جای حافظه موقت مسیر استفاده می­کند، بنابراین اساسا یک پروتکل مسیریابی حالت لینک است. تغییرات اصلی در LQSR در مقابل DSR مربوط به پیاده­سازی آن در لایه­ی ۲.۵ به جای لایه ۳ و پشتیبانی آن از معیارهای کیفیت لینک است. به علت معماری لایه­ی ۲.۵، LQSR از آدرسهای مجازی اترنت ۴۸ بیتی استفاده می­کند. همه­ی سرآیندهای LQSR، شامل مبدا مسیر، درخواست مسیر، پاسخ مسیر و خطای مسیر، از آدرس­های مجازی ۴۸ بیتی به جای آدرس­های IP ۳۲ بیتی استفاده می­کنند. تغییرات اعمال شده به DSR، شامل تغییر کشف و نگهداری مسیر به اضافه­ی مکانیزمهای جدید برای نگهداری معیار می­باشند.

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

معیارهای ذخیره شده­ی لینک در حافظه­ی موقت، باید بروز باشند، تا مسیریابی به درستی انجام شود. LQSR از دو مکانیزم مجزای نگهداری معیار استفاده می­کند. مکانیزم واکنشی برای نگهداری معیارهای لینکی که بطور فعال استفاده می­شوند و مکانیزم بازدارنده برای نگهداری معیارهای همه­ی لینک­­­ها.

پشتیبانی از معیار لینک، در نگهداری مسیر نیز تاثیرگذار است. وقتی نگهداری مسیر اعلان می­کند که یک لینک آماده نیست، معیارهای لینک را تنزل داده و یک خطای مسیر می­فرستد. خطای مسیر معیارهای بروز شده­ی لینک را به مبدا بسته بازمی­گرداند. پیاده­سازی LQSR شامل ساختار داده­های معمول DSR - بافر فرستنده، برای بافر کردن بسته­هایی که کشف مسیر را انجام می­دهند، بافر نگهداری برای بافرینگ بسته­هایی که نگهداری مسیر را اجرا می­کنند، و یک جدول درخواست برای توقیف درخواست­های مسیر تکراری- است. درخواستهای مسیر همواره در کل شبکه ad hoc منتشر می­شوند.

از تائیدیه­ی صریح به جای تائیدیه انفعالی یا تائیدیه­های لایه­ی پیوند استفاده می­شود. هر بسته­ی source-routed درخواست تائیدیه را حمل می­کند. یک گره انتظار دریافت تائیدیه از گام بعدی را در ۵۰۰ میلی ثانیه دارد. در نتیجه با استفاده از این تکنیک مکانیزم تائیدیه سرباری را به بسته اضافه نمی­کند.

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

LQSR از فرمی از "بازیابی بسته" یا ارسال مجدد DSR استفاده می­کند. بازیابی اجازه می­دهد که گره با تشخیص در دسترس نبودن گام بعدی، مسیر متفاوتی را امتحان کند. مکانیزم تائیدیه اجازه­ی بازیابی هر بسته­ای را نمی­دهد، زیرا اصولا برای تشخیص شکست لینک طراحی شده است. بهنگام ارسال بسته در لینک، اگر لینک اخیرا تصدیق شده باشد، درخواست تائیدیه می­شود، اما بسته برای بازیابی بافر نمی­شود. این طراحی اجازه می­دهد که اولین بسته را در ارتباط جدید بازیابی کرده و ارتباطات غیراتصال گرای نادر را بازیابی کنیم، اما برای ارتباطات فعال، به ارسال مجدد لایه­ی انتقال تکیه می­کند.

ـ سربار LQSR

این الگوریتم نیز مشابه هر الگوریتم مسیریابی دیگری مقداری سربار را تحمل می­کند. اولا در بروز­رسانی مسیر، ترافیک اضافه ایجاد می­کند، دوما سربار حمل مبدا مسیر و فیلدهای دیگر را در هر بسته دارد. سوما همه­ی گره­ها در طول مسیر، هر بسته را با استفاده از HMAC-SHA۱ علامت زده و جدول درهم­سازی را برای انعکاس تغییرات در سرآیندهای LQSR بهنگام روانه سازی بسته تولید مجدد می­کنند. گره­های انتهایی داده را با استفاده از AES-۱۲۸ رمزگذاری یا رمزگشایی می­کنند. سربار رمز می­تواند سرعت CPU را در گره­ها آهسته کند.

نتایج [۴] نشان داده که سربار LQSRدر مسیرهای تک­گامه آشکار است. سربار LQSR به مقدار زیادی به دلیل رمزگذاری و رمزگشایی است. این سربار تحمیلی با افزایش طول مسیر، کاهش می­یابد. زیرا رقابت کانال برای گام بعدی، بر کاهش گذردهی چیره می­شود. با کاهش نرخ ارسال داده، CPU براحتی می­تواند عملیات رمزگذاری و رمزگشایی را انجام دهد.

۶) نتیجه

نتایج حاصل از آزمون الگوریتم­های بررسی شده، نشان داده که در نظر گرفتن معیارهای کیفیت مسیر برای مسیریابی در شبکه های بی سیم توری، کارایی بهتری دارد. اما مسائل مربوط به مسیریابی در این نوع شبکه­ها، هنوز هم به عنوان چالش مطرح هستند.

حمیده شکرانی

دانشجوی کارشناسی ارشد دانشگاه آزاد واحد تهران شمال

پانوشتها:

[۱] Wireless Mesh Network

[۲] Access Point

[۳] Mobile ad hoc network

[۴] Expected Transmission Count

[۵] Expected Transmission Time

[۶] Destination Sequence Distance Vector

[۷] Dynamic Source Routing

[۸] Full dump

[۹] Weighted settling time

[۱۰] Triggered update

[۱۱] Time to live

[۱۲] Route reply

[۱۳]Link cache

[۱۴]Link Quality Source Routing

منابع:

[۱]. Toumpis s, Tompakaris D., “Wireless ad hoc networks and related topologies: application and research challenges”, Electrotechnik & informationstechnik, pp.۲۳۲-۲۴۱, ۲۰۰۶.

[۲]. Waharte S, Boutaba R, Iraqi Y, Ishibashi B., “Routing protocols in wireless mesh networks: challenges and design considerations”, Multimed Tools appl vol. ۲۹, pp. ۲۸۵-۳۰۳, ۲۰۰۶.

[۳]. De Couto DSJ, Aguayo D, Bicket J, Morris R., “A High-throughput path metric for multi-hop wireless routing”. In: Proceceeding of ۹th Annual International Conference on Mobile Computing and Networking, pp. ۱۳۴-۱۴۶ ,۲۰۰۳.

[۴]. Draves R, Padhye J, Zill B., “Comparison of routing metrics for static multi-hop wireless networks”. In: Proceceeding of ۲۰۰۴ Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications