مسیریابی در شبکه‌های حسگر بیسیم
در ادامه به دلیل این که در این پایان نامه از الگوریتم های مسیریابی استفاده شده است به معرفی مسیریابی و تعدادی از الگوریتم های آن خواهیم پرداخت .
۲-۶-۱ اهداف مسیریابی
الگوریتم های مسیریابی اهداف متعددی را دنبال می کنند ، از جمله :
- بهینه بودن
- ایجاد سربار پایین
- مقاوم و پایدار بودن
- همگرایی سریع
- تطبیق پذیری
بهینه بودن اشاره بر این دارد که الگوریتم این قابلیت و توانایی را داشته باشد که بهترین مسیربهینه را انتخاب کند . این مهم بستگی به معیارها و وزنهایی دارد که در محاسباتش استفاده می‌کند . به عنوان مثال یک الگوریتم ممکن است ، تاخیر و تعداد گره‌ها را در محاسبه استفاده کند ،اما وزنی که برای تاخیر در نظر بگیرد خیلی بیشتر باشد .
همچنین الگوریتم های مسیریابی به گونه ای طراحی می شوند که تا حد امکان ساده باشند ، یعنی بتوانند با بهره گرفتن از حداقل نرم افزار و امکانات و ایجاد کمترین سربار ،کارایی مناسبی ایجاد کنند . این کارایی وقتی اهمیت دارد که الگوریتم مجبور باشد ، روی رایانه با منابع فیزیکی محدود اجرا گردد .الگوریتم مسیریابی لازم است مقاوم باشد . یعنی بتواند در برابر مشکلات غیر معمول و حوادث پیش بینی نشده به درستی کار کند .خراب شدن یک پیوند با سخت افزار ،بار ترافیکی بالا ، درست عمل نکردن کد الگوریتم در یک گره و.. از مواردی هستند که می‌توانندباعث ایجاد مشکل در کار شوند . بنابراین الگوریتمی مناسب است که در برابر حملات مختلف شبکه پایدار باشد
همگرایی سریع نیز به این معنی است که در صورت تغییر شرایط به سرعت بتواند خود را به سمت مسیر بهینه همگرا کند .الگوریتم مسیریابی باید با شرایط مختلف شبکه تطبیق پذیر باشد.
۲-۶-۲ معیارهای تعیین مسیر بهینه
مسیری بهینه است که دارای معیارهای زیر باشد
طول مسیر کم ،قابلیت اطمینان بالا، تاخیر کم، پهنای باند زیاد ، بار ترافیکی کم وهزینه ارتباط پایین
۲-۷-۲-۱ معیارهای مسیریابی در شبکه های بیسیم
در مسیریابی در شبکه های حسگر معیارهای زیر نیز حایز اهمیت می‌باشند:
حفاظت و توان امنیت بالا،ایجاد سربار کم برای مسیریابی ،پشتیبانی از کیفیت سرویس، ارائه مسیرهای بدون حلقه، مسیرهای چند گانه،ارائه بهترین مسیر،ارائه به ترتیب داده‌ها ،بالابودن توان عملیاتی،کاهش تاخیر در شبکه
۲-۶-۳ مسیریابی در شبکه‌های بیسیم
قراردادهای[۱] متداول مسیریابی مانند قراردادهای مسیریابی مبتنی بر حالت اتصال[۲] با قراردادهای مبتنی بر بردارفاصله به خوبی تست شده اند و برای اکثر افراد در شیکه های کامپیوتری آشنا هستند . مشکل اصلی این دو قرارداد این است که برای همبندی هایی که غالبا تغییر می‌کنند ،قابلیت همگرایی به یک حالت پایدار را ندارند . دو قرارداد مسیریابی وابسته به پیام های کنترلی دوره ای هستند که نیازمند به هنگام سازی جداول مسیریابی دربین گره‌های شبکه هستند و در نتیجه در منابعی مانند پهنای باند ،توان باتری و سربار پردازشی مستلزم هزینه گره‌های شبکه هستند .از آنجایی که این دو قرارداد مسیریابی سعی بر قابل دسترس نگه داشتن تمام مسیرهای منتهی به تمام مقاصد را دارند ،منابع زیادی را تلف می کنند .مشخصه دیگر قراردادهای متداول این است که پیوند بین دو گره را دوطرفه فرض می کنند .مشخصه دیگر قراردادهای متداول این است که پیوند بین دو گره را دو طرفه فرض می کنند .در محیط های رادیویی بدون سیم این شرایط همیشه وجود ندارند . هدف از مسیریابی در الگوریتم های مسیریابی هدایت بارترافیکی (داده و اطلاعات ) از مبدا به مقصد با بیشترین کارایی و کمترین هزینه می باشد . در مسیریابی دو وظیفه عمده وجود دارد :
یافتن مسیر بهینه بین مبدا و مقصد
رساندن بسته‌ها از مبدا به مقصد
با توجه به رشد فزاینده گره‌ها در شبکه هایی مثل اینترنت و تغییراتی که همواره در آن رخ می دهد ، یافتن مسیرهای بهینه از معیارهای اندازه گیری استاندارد (مثل طول مسیر ) استفاده کرده و جداول مسیریابی را مقداردهی می‌کنند .
ولی در مقایسه،الگوریتم رساندن بسته‌ها از مبدا به مقصد نسبتا ساده است و در اکثر قراردادهای مسیریابی یکسان می‌باشد . کافی است با توجه به آدرس مقصد و جدول مسیریابی گره بعدی را پیدا کرد و سپس از طریق لایه فیزیکی بسته را فرستاد .
۲-۶-۳-۱ مسیریابی بردار فاصله
در این قراردادها هر گره یک جدول مسیریابی دارد که در آن فقط اطلاعات گره‌های مقصد موجود در شبکه نگه داشته می شود و هرگره تنها هزینه اتصال به همسایه های خود را تخمین زده وآن را آگاه می‌کند . تمامی گره‌ها با بهره گرفتن از اطلاعات آگهی شده ،کوتاه ترین مسیر خود را تا مقصد مورد نظر محاسبه می کنند این قرارداد ،توزیع شده است و با افزایش گره‌ها،تخمین های مسیریابی بسته‌ها کوتاه تر و صحیح تر خواهند بود .
۲-۶-۳-۲ مسیریابی حالت اتصال[۳]
این نوع قراردادها جداول مسیریابی را برای تمامی همبندی شبکه نگه‌داری می‌کند که شامل کوتاهترین مسیرها است . اطلاعات هزینه اتصال‌ها به طور متناوب با بهره گرفتن از تکنیک هدایت FLOODING به وسیله همه گره‌ها دریافت و ارسال می شوند . هر گره جدول خود را بر اساس اطلاعات هزینه اتصال های جدید جمع آوری شده به روز می‌کند .ممکن است اطلاعات هزینه اتصال به علت پویا بودن همبندی یا رسانه بیسیم ،ناسازگار باشد. در مسیریابی حالت اتصال هر گره همبندی کلی شبکه و هزینه هر پیوند را نگه داری می‌کند . برای نگه داشتن هزینه‌ها به صورت هماهنگ ،هر گره به طور دوره ای هزینه گیرنده های خارج شونده از خود را به تمامی گره‌ها با بهره گرفتن از هدایت، ارسال می‌کند . همانطور که هر گره این اطلاعات را دریافت می‌کند ، دیدش از همبندی شبکه به روز می شود و الگوریتم کوتاهترین مسیر برای انتخاب گره بعدی برای ارسال بسته‌های اطلاعاتی به مقصد مورد نظر را به کار می‌برد.
۲-۶-۳-۳ مسیریابی مبدا[۴]
در این قرارداد هر بسته اطلاعات مسیریابی خود را در سرآیند(HEADER ) خود حمل می‌کند . تصمیم گیری در مورد مسیریابی به هنگام حرکت بسته انجام می شود ، اما سربار این قرارداد زیاد است و برای همبندی های بسیار متغیر این قرارداد ناکارآمد است ، چرا که مسیرها به هنگام انتقال بسته‌ها ،باطل شده و قرارداد را ناصحیح می سازند .
[۱] Porotocol
[۲] LinkState
[۳]LinkState
[۴]Source Routing