بخشی از مقاله
مروري بر الگوريتم هاي مسيريابي در شبکه هاي تحمل پذیر تاخير
چکيده
شبکه هاي تحمل پذير تاخير PPF١٠ نوعي از شبکه هاي بي سيم PFP١٢ هستند که اتصال دائمي بين گره ها به علت تراکم کم و پراکندگي آنها وجود ندارد. در شبکه هاي سنتي TCP.IP فرض بر اين است که بين هر جفت گره مبدا و مقصد مسيري انتها به انتها وجود دارد. هر سناريويي که اين فرض را برهم زند به عنوان کاربردي براي شبکه هاي تحمل پذير تاخير در نظر گرفته مي شود. براي مقابله با اين وضعيت گره ها از رويکرد ذخيره ، حمل و انتقال PPF٣٢ استفاده مي کنند. به اين معني که هر گره بسته دريافت شده را در حافظه خود نگهداري مي کند تا در فرصت زماني مناسب تر گره اي که نقش مفيدي در رسيدن بسته به مقصد داشته باشد را بيابد. تحقيقات زيادي براي غلبه بر مسائل چالش بر انگيز مسيريابي در DTN ها انجام شده است و الگوريتم هاي مسيريابي متفاوتي مطرح شده اند. اين الگوريتم ها را مي توان به دو دسته الگوريتم هاي مسيريابي تصادفي و قطعي تقسيم کرد. با توجه به افزايش روز به روز تعداد الگوريتم هاي مسيريابي نياز است تا مزايا و معايب هر کدام از اين الگوريتم ها بررسي شود تا مشخص شود که هر يک براي چه کاربردي مناسب مي باشد. در اين مقاله به بررسي مهمترين الگوريتم هاي مسيريابي در شبکه هاي تحمل پذير تا ير و روش هر يک در مديريت حافظه گره ها مي پردازيم .
کلمات کليدي
شبکه هاي تحمل پذير تاخير، مسيريابي ، کارايي
١- مقدمه
شبکه هاي تحمل پذير تاخير نمونه اي از شبکه هاي چالش برانگيز هستند که در آنها اتصال همزمان بين تمام گره هاي شبکه وجود ندارد. اتصالات P4 موجود در اين شبکه ها به صورت پي در پي قطع و P3Fوصل مي شوند. به همين دليل پروتکل هاي مسابي سنتي در اين يري شبکه ها کارايي ندارند. زيرا تمامي اين پروتکل ها فرض مي کنند که ن هر دو گره در شبکه مسيري انتها به انتها وجود دارد در صورتي که بي رهايي از ويژگي هاي شبکه هاي تحمل پذير عدم وجود چنين مسي تاخير است . در صورتي که گره هاي موجود در اين شبکه ها حرکت کنند اوضاع وخيم تر مي شود. زيرا درصورتي که الگوي حرکتي گره ها نامعين باشد نمي توان از مکان گره ها اطلاع داشت .
علاوه براين گره هايي که در محيط هاي چالش انگيز فعاليت مي کنند از نظر منابعي از قبيل قدرت پردازش ، ظرفيت شبکه و حافظه بسيار محدود هستند. [١]، [٢]، [٣]، [٤] همان طور که پيش از اين بيان شد شبکه هاي تحمل پذير تاخير نمونه اي از شبکه هاي چالش برانگيز هستند. شبکه هاي چالش برانگيز ممکن است از يک يا چند فرض شبکه هاي سنتي تخلف کنند در نتيجه مدل TCP.IP براي چنين شبکه هاي مناسب نيست . مثال هايي از شبکه هاي چالش برانگيز عبارتند از: [٥]
١) شبکه هاي موبايل زميني : از آنجايي که گره هاي موجود در اين شبکه ها اغلب توسط وسايل نقليه تغيير مکان مي دهند، شبکه به راحتي گسسته مي شود. علاوه بر اين تداخلات راديويي موجود نيز مي تواند باعث گسسته شده شبکه شود.
٢) شبکه هايي با رسانه هاي مرموز P5P4F: اين شبکه ها براي م يط هايي که در آنها فواصل بين گره ها بسيار زياد است و يا محيط هايي که براي ارسال داده از فرکانس هاي نوري و يا صوتي استفاده مي کنند طراحي شده اند. در اين شبکه ها با گسستگي طولاني مدت لينک ها مواجه هستيم . به عنوان نمونه اي از اين شبکه ها مي توان به ارتباط با زير دريايي ها يا ماهواره هاي نزديک به زمين اشاره کرد.
٣) شبکه هاي مبتني بر حسگر: اين شبکه ها شامل تعداد زيادي گره باشند که از نظر منابع پردازشي ، حافظه و توان باطري محدود مي هستند. در اين شبکه ها گره ها به منظور استفاده بهينه از باطري خود به صورت زمانبندي شده با هم ارتباط برقرار مي کنند. در هريک از حيطه هاي کاري ذکر شده هدف کار کردن شبکه تحت محدوديت هاي پر دغدغه با تنظيمات شبکه هاي سنتي است . معماري DTN در واقع نماد تلاش براي توسعه کارايي و توانايي شبکه هاست .
تلاش در شبکه هاي DTN براي برقراري ارتباط بين نمونه هايي از شبکه هاي چالش برانگيز و فراهم کردن ارتباط بين استاندارد هاي متناقص و ناهم جور، حتي در صورت عدم وجود زير ساخت ارتباطي مناسب است . در واقع هدف اصلي DTN فراهم کردن ابزاري براي انتقال پيام در محيط هاي چالش برانگيز است .
يکي از مسائل اساسي در طراحي شبکه هايي که در آنها گسستگي وجود دارد مسئله مسيريابي مي باشد. قبل ازاين شبکه ايي قابل استفاده باشد بايد امکان انتقال داده از منبع به مقصد وجود داشته باشد. در اين مقاله سعي شده است که الگوريتم هاي مختلف مسيريابي در شبکه هاي تحمل پذير تاخير بررسي شود.
۲- ويژگي هاي شبکه هاي تحمل پذير تاخير
شبکه هاي DTN داراي خصوصياتي مي باشد که در ادامه به بررسي تعدادي از اين خصوصيات مي پردازيم : [٦]، [٧]
١- اتصال متناوب : اگر بين منبع و مقصد مسيري وجود نداشته باشد استفاده از پروتکل هاي TCP.IP امکان پذير نبوده و پروتکل هاي ديگري مورد نياز است .
٢- نرخ داده نامتقارن : اگر نرخ انتقال داده نامتقارن باشد امکان استفاده از پروتکل هاي تعامل سنتي مانند TCP وجود ندارد.
٣- نرخ خطاي بالا: اگر نرخ خطا در لينک ها زياد باشد داده ها نياز به تصحيح و يا ارسال دوباره دارند که اين موضوع باعث بالا رفتن ترافيک در شبکه مي شود.
٤- الگوي حرکتي مبهم : با مشخص نبودن الگوي حرکتي يک گره رفتار آن در آينده نامشخص است . اغلب شبکه هاي
DTN با اين مشکل مواجه هستند.
٥- تاخير متغير يا بلند مدت : تاخير انتشار بالا بين گره ها علاوه بر تاخير صف بندي در بافر گره ها همگي باعث به وجود آمدن تاخيري در مسيرهاي انتها به انتها مي شود که توسط پروتکل هاي اينترنت و کاربردهايي که به بازگشت سريع بسته هاي تصديق اعتماد مي کنند، قابل تحمل نيست .
در پروتکل هاي TCP قبل از شروع انتقال داده بايد دنباله ايي از بسته هاي ACK بين منبع و مقصد مبادله شود. در اينترنت زمان رد و بدل شدن اين بسته ها ناچيز است در صورتي که در شبکه هاي تحمل پذير تاخير اين زمان بسيار زياد بوده و امکان برقراري ارتباط وجود ندارد. حتي اگر ارتباط هم برقرار شود ممکن است يکي از طرفين در حين ارتباط به يکي از دلايل ذکر شده ناپديد شود. در اين حالت طرف ديگر تمامي اطلاعات مربوط به طرف مقابل را دور مي ريزد.
٣- کاربردهاي شبکه هاي تحمل پذير تاخير
در ادامه به معرفي برخي از کاربردهاي مهم شبکه هاي تحمل پذير تاخير پرداخته و به صورت مختصر راجع به حرکت گره ها، نرخ انتقال ، سطح سختي و معيارهاي ديگر در اين کاربردهاي توضيح داده شده است .
١- مطاله حيات وحش
براي مطالعه زندگي حيوانات وحشي و مسکن طبيعي آن ها معمولا دستگاه هاي حسگر کوچکي که شامل ميکروکنترلر ها، GPS، حافظه ، واحد فرستنده - گيرنده راديويي ، باطري و غيره مي باشد، به حيوانات متصل مي شود.[٨] تحرک حيوانات باعث متحرک شدن گره ها مي شود. معمولا گره ها اطلاعات را بين خود رد و بدل مي کنند تا به همسايگي يک ايستگاه اطلاعاتي برسند. ايستگاه اطلاعاتي داده ها را از گره ها جمع آوري مي کند. ايستگاه هاي اطلاعاتي هم مي توانند به دو صورت ثابت و متحرک باشند. ايستگاه هاي اطلاعاتي متحرک با نزديک شدن به سمت گره ها اطلاعات آنها را جمع آوري مي کنند. معمولا حرکت ايستگاه هاي اطلاعاتي در اين دسته کاربردها کنترل شده است .
از پروژهاي عملياتي مهم در اين زمينه مي توان به پروژه هاي Zebranet [٩]، [١٠]و پروژه SWIM [١١] اشاره کرد.
٢- مطالعات جنگلباني و زير آبي
مطالعات محيطي به دلايل متعدد ساليان متمادي مورد توجه بوده است . ميزان دما، فشار هوا، نور، آلودگي هاي شي يايي در آب و خاک ، سطح تشعشعات ، اطلاعاتي هستند که اغلب توسط سنسورهايي که در محيط پراکنده مي شوند اندازه گيري مي شوند. در چنين مواردي با توجه به طبيعت مکان شبکه اغلب دچار گسستگي هاي طولاني مدت مي شود. در کاربردهاي جنگلباني ، گره هاي حسگر ممکن است به دلايل مختلفي از قبيل بارش هاي سنگين ، بارش برف ، دماي بسيار بالا و شرايط ديگر از کار بيفتند. علاوه بر آن لينک هاي ارتباطي ممکن است به دلايل مختلفي از قبيل تراکم درختان به درستي کار نکنند.[١٢]
مسئله مهم در کاربردهاي زير آبي رسانه هاي ارتباطي مي باشد. در کاربردهاي زير آبي اغلب از شبکه هاي صوتي استفاده مي شود.[١٣]
در مطالعات جنگلباني مي توان از فرستنده هاي راديويي با برد بلند براي ارسال داده استفاده کرد تا به محدوديت گسستگي شبکه غلبه کرد، اما اين روش باعث مي شود که طول عمر باطري گره ها کاهش يابد. اين روش براي کاربردهاي زير دريايي مفيد نيست زيرا سيگنال هاي راديويي در آب بسيار ضعيف مي شوند. در کاربردهاي زير دريايي دو راه حل وجود دارد. راه حل اول اين است گره ها قادر باشند به سطح آب نزديک شوند و داده هايشان را به يک ايستگاه اطلاعاتي بفرستند. روش دوم اين است که يک سري ايستگاه هاي رابط وجود داشته باشند که بتوانند زير آب حرکت کنند و با نزديک شدن به گره ها داده هاي آنها را جمع آوري کنند.
از جمله پروژه هايي که به مطالعات زير دريايي پرداخته اند مي توان به پروژه SeaWeb اشاره کرد. [١٤]
٣- کاربردهاي روستايي
اين کاربرد يکي از مهم ترين و محتمل ترين کاربردهاي DTN است که در محيط هاي دور افتاده که فاقد زير ساخت ارتباطي مي باشند، به کار مي رود.[٣]، [١٥] در اين حالت وسايل نقليه همانند پيک عمل کرده و اطلاعات را بين شهر و روستا جابجا مي کنند. اگرچه انتقال اطلاعات به اين صورت ممکن است چند ساعت طول بکشد اما اين شبکه مزايايي نيز دارد، با توجه به پيشرفت تکنولوژي ميزان حافظه پيک ها را مي توان تا چندين ترابايت افزايش داد که اين مقدار بسيار بيشتر از پهناي باند فراهم شده از طريق شبکه هاي پيشرفته امروزي است .
٤- شبکه هاي بين سياره اي
لزوم ارتباط بين سيارات و فاصله عظيم بين آنها که عملا امکان استفاده از شبکه هاي سنتي را از بين مي برد يکي ديگر از دلايل اهميت سبکه هاي DTN است . فرض کنيد دانشمندي روي زمين مسئول يک ايستگاه رباتيک هواسنجي در سياره مريخ است . اگر اين دانشمند بخواهد نرم افزار موجود را نوسازي کند ابتدا اطلاعات و فايل هاي مورد نياز بايد از ايستگاه کاري روي زمين به يک آنتن فضايي پيچيده فرستاده شود، سپس از اين آنتن به يک ماهواره رابط و از آنجا به ايستگاه مورد نظر در سياره مريخ ارسال شود. زمان ارسال اطلاعات در اين حالت نه بر حسب ثاينه بلکه بر حسب ساعت و يا روز اندازه گيري مي شود.
٥- کاربردهاي نظامي
تمامي کاربردهاي ذکر شده مي توانند به نوعي زير چتر کاربردهاي نظامي قرار گيرند. اما به هر حال وجود فاکتور مرگ و مير باعث به وجود آمدن تفاوت هاي اصلي بين کاربردهاي نظامي و کاربردهاي ديگر مي شود. با توجه به دخالت انسان در اين گونه محيط ها گره ها بايد از سطح خودکاري بالاتري برخوردار باشند و همچنين با توجه به نرخ بالاي خرابي گره ها مي بايست با در نظر گرفتن افزونگي بر محدوديت اتصال غلبه کرد. [٩]
٤- چالش هاي شبکه هاي تحمل پذير تاخير
چالش هاي زيادي در شبکه هاي تحمل پذير تاخير وجود دارد که در شبکه هاي معمولي وجود ندارد. از جمله اين چالش ها عبارتند از:
١- زمانبندي اتصال
يکي از مهم ترين ويژگي هاي شبکه هاي DTN زمانبندي اتصال مي باشد که به شرايط کاربرد مورد نظر بستگي دارد. کاربردهاي مختلف از نظر ميزان پيش بيني پذيري متفاوت مي باشند. مثلا در کاربرد شبکه هاي منظومه شمسي که قطعي اتصال بر اثر حرکت اشياي موجود در فضا رخ مي دهد، گسستگي شبکه مي تواند به صورت دقيق پيش بيني شود. اما در کاربردهاي ديگر که با حرکات انسان سر و کار دارد ميزان و زمان گسستگي به صورت دقيق قابل پيش بيني نيست . [١٧]
٢- فضاي بافر
به علت گسستگي هاي طولاني مدت موجود در شبکه هاي DTN
بسته هاي ارسالي مي بايست براي زمان هاي طولاني در بافر روتر هاي مياني ذخيره شده و منتظر فرصت هاي ارتباطي که در آينده به وجود مي آيد باشند. از يک ديدگاه اين بدان معني است که فضاي بافر روترهاي مياني مي بايست متناسب با کاربرد باشد. از ديدگاه ديگر بايد سياست هاي مسيريابي در تصميم گيري هاي خود به فضاي بافر روتر ها توجه داشته باشند.
٣- قدرت پردازش
همانطور که پيش از اين نيز گفته شد گره هاي تشکيل دهنده شبکه هاي DTN اغلب بسيار کوچک بوده و از نظر منابع از جمله منابع پردازشي محدود هستند. در نتيجه اين گره ها قادر به اجراي الگوريتم هاي مسيريابي پيچيده نيستند.
٤- انرژي
يکي ديگر از منابع محدود گره هاي موجود در شبکه هاي DTN منبع انرژي است . الگوريتم هاي مسيريابي با اعمالي از قبيل ارسال ، دريافت ، ذخيره بسته ها و محاسبات انرژي زيادي مصرف مي کنند. در نتيجه هر الگوريتم مسيريابي که بيت هاي کمتري ارسال و دريافت کند الگوريتم بهينه تري است .
۵- سياست هاي مسيريابي
سياست هاي مسيريابي بر اساس تعداد کپي هاي پيام ها و اطلاعاتي که براي انتخاب گره ها استفاده مي کنند به دو دسته روش هاي مبتني بر تکرار و روش هاي مبتني بر دانش تقسيم مي شوند.
٥-١ روش هاي مبتني بر تکرار
به علت اينکه اکثر اجزاي تشکيل دهنده شبکه هاي تحمل پذير تاخير غير قابل اعتماد و يا غير قابل پيش بيني هستند، بهتر است که از هر بسته ارسالي چندين کپي در شبکه موجود باشد تا شانس رسيدن بسته به مقصد افزايش يابد يا اينکه تاخير رسيدن بسته به مقصد کاهش يابد. در واقع با افزايش کپي هاي يک بسته در شبکه احتمال اينکه يکي از اين کپي ها به مقصد راه پيدا کند بيشتر مي شود. ساده ترين راه حل اين است که از هر بسته تنها يک کپي در شبکه موجود باشد. در اين حالت در اثر عدم موفقيت گره اي که بسته در اختيار اوست احتمال رسيدن بسته به مقصد از بين مي رود. امن ترين راه حل اين است که به ازاي هر گره در شبکه يک کپي از بسته موجود باشد.
در اين حالت تنها زماني که تمام گره ها دچار شکست شوند احتمال رسيدن بسته به مقصد از بين مي رود، اما از طرف ديگر با افزايش تعداد کپي هاي يک بسته در شبکه مصرف منابع شبکه از جمله پهناي باند و منابع ذخيره سازي افزايش مي يابد. در واقع با توجه به کاربرد و اهميت رسيدن بسته به مقصد بايد مصالحه اي بين هزينه هاي شبکه و احتمال رسيدن بسته به مقصد صورت گيرد. ساده ترين راه حل اين است که گره منبع بسته را نزد خود نگه درد تا زماني که با گره مقصد ارتباط برقرار کند. از آنجايي که اين روش از هيچ اطلاعاتي براي انتخاب گره بعدي استفاده نمي کند در دسته الگوريتم هاي مبتني بر تکرار قرار مي گيرد. [٢٣] اما در حالتي که اين روش با اطلاعات دقيقي از تغييرات شبکه ترکيب شود بسيار مفيد خواهد بود.
٥-١-١جريان هاي مبتني بر درخت
در اين روش ها هر بسته در تعدادي از گره هاي مياني کپي مي شود.
در اين حالت تعداد کپي هايي که هر گره از يک بسته ايجاد مي کند بايد کنترل شود. روش هاي متفاوتي براي اين مسئله پيشنهاد شده است .[١٨] طرح ساده اي پيشنهاد شده است که به هر گره اجازه مي دهد تا تعداد نامحدودي کپي از يک بسته در اختيار داشته باشد اما حداکثر گامي که يک بسته مي تواند از منبع دور شود k گام است . اين روش عمق درخت شکل گرفته را محدود مي کند اما کاري به عرض درخت ندارد. در [١٩] روش ديگري پيشنهاد شده است که در آن هر گره را به داشتن حداکثر L کپي از بسته محدود مي کند که در اين حالت عمق و عرض هر دو درخت محدود مي شوند. در روش پيشنهاد شده در [٢٠] که ارسال در دو گام نام گرفته است گره منبع يک کپي از هر بسته توليدي را به 1-L گره اولي که ملاقات مي کند ارسال مي کند. گره هاي دريافت کننده بسته را نزد خود نگهداري مي کنند تا گره مقصد را ملاقات کنند.
در روش پيشنهاد شده در [٢١] گره منبع L کپي از بسته توليد مي کند. هنگامي که گره منبع به گره اي برخورد مي کند که هيچ کپي از اين بسته ندارد مسئوليت پخش تعداد 2.L از بسته ها را به آن سپرده و بقيه را نزد خود نگه مي دارد. اگر گره منبع تنها يک کپي از بسته داشته باشد به روش ارسال مستقيم سوييچ مي کند. در مقاله [٢٢]
نشان داده شده است که اين راه حل پيشنهادي با داشتن تعداد ارسال کمتر در شرايط بحراني شبکه از قبيل فضاي بافر و پهناي باند محدود ميزان تاخير مناسبي دارد.
٥-٢-١ مسيريابي همه گير و تصادفي
مسيريابي تصادفي هنگامي به کار مي رود که هيچ دانشي از توپولوژي شبکه موجود نيست . سريعترين راه براي پخش يک پيام در شبکه ارسال تمام بسته ها به تمامي گره ها ست . اين روش تحت عنوان مسيريابي همه گير شناخته مي شود. در اين حالت هنگامي که دو گره يکديگر را ملاقات مي کنند تمام بسته هايي که بينشان مشترک نيست را با هم رد و بدل مي کنند. اين روش اگرچه در برابر خرابي گره ها بسيار مقاوم بوده و سريعترين حالت ارسال بسته به مقصد را فراهم مي کند اما ميزان اتلاف منابع بالايي دارد. يکي از مسائل چالش برانگيز موجود در اين مسيريابي يافتن راهي براي متوقف ساختن ارسال بسته در حالتي است که
