مسیریابی چندقیدی انیپس مش بیسیم

مسیریابی چندقیدی انیپس مش بیسیم – ایران ترجمه – Irantarjomeh

مقالات ترجمه شده آماده گروه کامپیوتر

مقالات ترجمه شده آماده کل گروه های دانشگاهی

مقالات

چگونگی سفارش مقاله

الف – پرداخت وجه بحساب وب سایت ایران ترجمه(شماره حساب)ب- اطلاع جزئیات به ایمیل irantarjomeh@gmail.comشامل: مبلغ پرداختی – شماره فیش / ارجاع و تاریخ پرداخت – مقاله مورد نظر --مقالات آماده سفارش داده شده پس از تایید به ایمیل شما ارسال خواهند شد.

www.irantarjomeh.com

یک الگوریتم توزیعی برای مسیریابی چند قیدی انیپس در شبکه‌های مش بیسیم

چکیده

مسیریابی انیپس (هرمسیر[۱])، به عنوان یک الگوی مسیریابی جدید، جهت ارتقای عملکرد شبکه‌های بیسیم از طریق بهره برداری از تنوع فضایی و طبیعت انتشار رسانه بیسیم پیش‌بینی و ارائه شده است. در این مقاله، ما نسبت به بررسی مشکل یافتن یک مولفه انیپس برای قیدهای (K) متعدد، اثبات شده بعنوان یک مسئله NP – سخت، اقدام می نمائیم. بر این مبنا، ما یک الگوریتم مسیریابی تقریب-K توزیع شده زمان چند جمله ای را ارائه می‌نماییم. الگوریتم ما به سادگی الگوریتم کوتاهترین مسیر بلمن – فورد[۲] می‌باشد. آزمایشات گسترده نشان دهنده آن هستند که الگوریتم ما بسیار کارامد بوده و نتیجه آن به خوبی نتایج حاصله بوسیله بهترین الگوریتم متمرکز، که البته نیازمند اطلاعات کلی است، می باشد.

[۱] Anypath

[۲] Bellman-Ford

مسیریابی چندقیدی انیپس مش بیسیم

۱- مقدمه

برای شبکه‌های ناپایدار بیسیم، بواسطه گوناگونی فضایی و طبیعت انتشار رسانه بیسیم، غالبا ارسال یک پاکت به هر یک از گره های مجاور، در مقایسه با ارسال به یک گره مجاور خاص، بسیار کم هزینه برتر می‌باشد]۱۰[. این ویژگی انگیزه ای را برای ظهور یک تکنیک مسیریابی نوین بوجود آورد که تحت عنوان مسیریابی فرصت طلب[۱] خوانده می‌شود. بر این مبنا، مشخص شده است که مسیریابی فرصت طلب به طور معنی داری قابلیت ارتقای عملکرد شبکه‌های بیسیم را خواهد داشت ]۱۱[ ]۳[.  Biswas و Morris [1] نسبت به طراحی و پیاده ‌سازی ExOR، یک پروتکل مسیریابی فرصت طلب برای شبکه‌های مش بیسیم اقدام نمودند. Chachulski و همکاران ]۳[ از طریق ترکیب مسیریابی فرصت طلب و برنامه‌های مختلف شبکه، سیستم MORE را عرضه داشتند. بر مبنای مفهوم مسیریابی فرصت طلب، Dubois-Ferriere ]10[ یک الگوی مسیریابی جدید را عرضه داشت که تحت عنوان مسیریابی انیپس خوانده می‌شود، که متعاقبا بوسیله مراجع ] ۱۱، ۱۳، ۱۹و ۲۵ [ مورد بررسی قرار گرفت. در مسیریابی انیپس، هر پاکت به سمت مجموعه ای متشکل از چندین گره مجاور پیش روی (تحت عنوان فورواردرها) ارسال می‌شود، و پاکت در صورتی مجددا ارسال خواهد شد که هیچکدام از فورواردها آن را دریافت نداشته باشند. تا زمانیکه یکی از این فورواردها این پاکت را دریافت دارند، قابلیت فوروارد یا ارسال آن وجود خواهد داشت.

یکی از مولفه‌های تحقیقاتی کلیدی در مسیریابی انیپس چگونگی یافتن هر یک از مسیرهای بهینه با توجه به تاخیر، هزینه، مصرف انرژی و پارامترهای دیگر می‌باشد. این مشکل غالبا به یافتن یک مجموعه فوروارد بهینه برای هر گره تقلیل می‌یابد. از طرف دیگر یک گره با فورواردهای بیشتر می‌تواند از هزینه فوروارد یا تاخیر کمتری به هر یک از فورواردهای خود برخوردار باشد. بعلاوه، هر گره مجاور از پیشرفت قابل قیاسی با جهش بعدی در مسیر واحد بهینه برخوردار نیست. بنابراین، داشتن فورواردهای بسیار زیاد ممکن است منجر به یک پس زدگی نامطلوب شود، نظیر افزایش احتمال جداشدن یک پاکت از مسیر واحد بهینه خود، که نهایتا حتی ممکن است منجر به بروز لوپ‌هایی در توپولوژی مسیریابی گردد ]۱۱[.

…

ادامه این مبحث به شرح ذیل سازماندهی شده است. در بخش ۲ ما نسبت به بررسی الگوریتم مسیریابی انیپس اقدام نموده و مدل شبکه خود را تشریح کرده و مشکل مورد بررسی را ارائه می‌نماییم. در بخش ۳، ما الگوریتم تقریب خود را عرضه داشته، خواص آن را تحلیل نموده، و ویژگی‌های پیاده‌سازی توزیعی آن را به بحث می‌گذاریم. بخش ۴ نتایج عددی ما را آشکار می‌سازد. نهایتا در بخش ۵ نتیجه‌گیری این مقاله ارائه خواهد شد.

مسیریابی چندقیدی انیپس مش بیسیم

۲-۱٫ الگوریتم مسیریابی انیپس

در الگوریتم مسیریابی انیپس، هر گره قابلیت ارسال یک پاکت به مجموعه ای از گره‌های مجاور خود را خواهد داشت. تا زمانیکه که یکی از آنها این پاکت را دریافت دارد، این فرآیند تداوم خواهد یافت. این مجموعه از گره‌های مجاور تحت عنوان مجموعه فورواردینگ خوانده می‌شوند، که مشابه با “جهش بعدی” برای هر گره در مسیریابی کلاسیک می‌باشد. گره v تحت عنوان فوروارد کننده گره u خوانده می‌شود آنهم در صورتی که v در مجموعه فوروارد u قرار داشته باشد. از آنجاییکه که بیش از یک فوروارد کننده ممکن است پاکت یکسانی را دریافت دارند، لازم است از فوروارد نمودن موارد حشو یا اضافه غیر ضروری جلوگیری شود. بنابراین، گره‌های موجود در مجموعه فورواردینگ هر کدام از اولویت خاصی در خصوص ارسال مجدد پاکت دریافتی برخوردار می باشند. بر این مبنا یک اولویت بالاتر به گره ای تخصیص داده می‌شود که از فاصله کمتر یا هزینه کمتری با گره مقصد برخوردار می‌باشد. یک گره اقدام به ارسال یک پاکت دریافتی تنها در صورتی خواهد نمود که کلیه گره‌های دارای اولویت بالاتر نتوانند آن گره را دریافت دارند. در نتیجه، این گره اقدام به ارسال یا فوروارد پاکت دریافتی به مقصد نموده، در حالیکه دیگر گره‌های دارای اولویت پایین تر از این کار اجتناب می‌نمایند. برای هر پاکت، منبع یا سورس مرتبط همچنان فرآیند ارسال را تداوم بخشیده تا آنکه درنهایت یکی از فوروارد کنندگان آن را دریافت داشته یا آنکه آستانه مورد نظر لبریز شود. به هنگامی‌که یک فوروارد کننده این پاکت را دریافت داشت، گره مربوطه این فرآیند را تکرار نموده تا آنکه پاکت به مقصد خود برسد.

۲-۲٫ مدل سیستمی‌

یک شبکه مش بیسیم به عنوان یک نمودار مستقیم G = (V, E) مدل‌سازی شد، که در آن E به عنوان مجموعه ای از لبه‌های m و V به عنوان مجموعه ای از رأس‌های n به حساب می‌آید. در این مقاله، عبارات ذیل به صورت تبادلی مورد استفاده قرار می‌گیرند: لبه و لینک، رأس و گره. هر لبه (v, u) Î E در ارتباط با احتمال تحویل پاکت p(v, u) می‌باشد. ما نسبت به تعریف احتمال تحویل ابرلینک p(v, J) به عنوان نوعی احتمال اقدام می‌کنیم که یک پاکت ارسال بوسیله گره v از حداقل یکی از گره‌ها در مجموعه J دریافت می‌دارد. همانگونه که در مرجع ]۱۹، ۲۱[ نشان داده شد، اتلاف پاکت در گیرندگان مختلف در عمل به صورت مستقل رخ می‌دهد. بنابراین، احتمال تحویل ابر پیوند یا ابر لینک را می‌توان تحت عنوان  محاسبه نمود. به علاوه، هر گره v Î V همچنین در ارتباط با وزن‌های رأس K یعنی  می‌باشند. توصیفات محتمل بسیاری برای وزن‌های رأس وجود دارند. به طور مثال به هنگامی‌که K = 1 صادق باشد،w₁(v)  ممکن است معرف میانگین زمان ارسال برای هر نوع انتقال باشد. به هنگامی‌که K = 2 باشد، w₁(v) نیز به عنوان میانگین زمان ارسال به حساب آمده و w₂(v)  میانگین مصرف انرژی برای هر ارسال محسوب می‌شود.

۲-۳٫ تعریف مشکل

همانگونه که در مرجع ]۱۳[ قید شد، نگارش تصمیم مرتبط با مشکل انیپس چندقیدی (مشخص شده بوسیله DMCAP) می‌بایست قابلیت یافتن یک انیپس ممکن P از منبع s به مقصد t را داشته باشد، آنهم به گونه ای که  حاصل گردد، که در آن ثابت مثبت  مشخص کننده kامین قید QOS می‌باشد.

با این وجود، از آنجاییکه ممکن است بیش از یک راه حل برای DMCAP وجود داشته باشد، ما پارامترهای سنجشی ذیل را تحت عنوان طول انیپس جهت مقایسه راه حل‌های محتمل متعدد برای DMCAP تعریف می‌نماییم. طول انیپس از یک گره v به مقصد t در امتداد انیپس P به شرح ذیل تعریف می‌شود:

مسیریابی چندقیدی انیپس مش بیسیم

۳- یک الگوریتم K– تقریب توزیع شده کارامد

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

۳-۱٫ الگوریتم مسیریابی توزیعی

در ابتدا ما می‌بایست نسبت به تعریف یک وزن رأس کمکی  برای هر گره v Î V به شرح ذیل اقدام کنیم: . به همین صورت می‌بایست قابلیت تعریف وزن انیپس کمکی (AAW) از v به مقصد t در امتداد یک انیپس P به شرح ذیل را داشته باشیم:

۳-۲٫ آنالیز الگوریتم

ما هم اکنون می‌توانیم اثبات کنیم که الگوریتم انیپس محاسبه شده بوسیله DMART یک K– تقریب به مشکل OMCAP می‌باشد. ما در ابتدا اثبات می‌نماییم که برای هر گره انیپس آن با توجه به محاسبه به عنوان کوتاهترین انیپس OMCAP آن در نظر خواهد بود. متعاقبا، ما از نتیجه مرجع ]۱۳[ جهت نشان دادن ارتباط بین انیپس و راه حل به مشکل OMCAP استفاده می‌نماییم.

اجازه دهید تا q(v) معرف AAW بهینه v باشد. ما از  جهت مشخص نمودن AAW مرتبط با v از طریق مجموعه فوروارد J استفاده می‌نماییم آنهم در صورتی که کلیه گره‌ها در J از کوچکترین انیپسهای AAW استفاده کنند.

در اینجا ما ۲ قضیه ۳-۱ و ۳-۲ را ارائه می‌نماییم که در مرجع ]۱۳[ اثبات شده‌اند.

قضیه ۳-۱: برای کلیه گره‌های مجاور v یعنی j₁،  j₂، …، j_z, که در آن z تعداد رئوس جهت دار v که از یک گره خارج می‌شود خواهد بود آنهم در صورتی که q(j₁) £ q(j₂) £… £ q(j­_z) صادق باشد، بنابراین در اینجا می‌بایست یک مجموعه فوروارد کننده بهینه AAW (AOFS) در قالب {j₁, j₂, …, j_b} برای برخی از b Î {۱, ۲, …, z} موجود باشد که تحت عنوان یک مجموعه فوروارد کننده بهینه AAW کامل (FAOFS) خوانده می‌شوند.

۳-۳٫ پیاده سازی توزیعی

با الهام از پروتکل پیشنهادی بوسیله Distributed Bellman-Ford در مرجع ]۲[، ما پروتکل کنشی همزمان ذیل را برمبنای الگوریتم DMART خود ارائه می‌نماییم. هر گره دارای یک ورودی جدول مسیریابی برای هر مقصد، < anypath weights, auxiliary anypath weight, forwarding set destination, K > می‌باشد. خط زمانی به یک ترتیب بازه‌های زمانی یک طول ثابت تقسیم شده است، که هرکدام از آنها برای یک تکرار در DMART بکار گرفته می‌شوند. در هر بازه زمانی، هر گره اقدام به اجرای DMART جهت آپدیت انیپس خود برای هر مقصد می‌نماید. در صورتی که ورودی‌ها در جدول مسیریابی تغییر کنند، این گره اقدام به ارسال چندتایی‌های بردار مسیر، مقصد، <destination, K anypath weights, auxiliary anypath weight>  برای کلیه گره‌های مجاور آنی خود می‌نماید. چنین موردی تحت عنوان بروزرسانی بردار خوانده می‌شود. در تکرار بعدی، گره‌های آنی مجاور قابلیت بکارگیری این بردارهای مسیر جدید برای آپدیت جداول مسیریابی خود را خواهند داشت.

مسیریابی چندقیدی انیپس مش بیسیم

۴- ارزیابی عملکرد

در این بخش، ما برخی از نتایج عددی جهت ارزیابی عملکرد DMART را ارائه می‌نماییم. ما DMART را برای مورد K = 2 در یک مجموعه خاص با استفاده از پروتکل کنشی همزمان خود اجرا می‌نماییم. دو وزن رأس ارائه دهنده میانگین زمان ارسال و مصرف توان برای هر ارسال به ترتیب می‌باشند. ما رویه اجرایی خود را با الگوریتم SAF در مرجع ]۱۹[ و الگوریتم حریصانه در مرجع ]۱۳[ مقایسه نمودیم و الگوریتم SAF را جهت پشتیبانی از EWATX گسترش دادیم. از آنجاییکه SAF تنها قابلیت کار با هر پارامتر سنجشی در هر زمان را دارد، ما از SAF جهت محاسبه طول‌های انیپس با توجه به تأخیر ارسال و مصرف توان استفاده نمودیم (ارائه شده بوسیله SAF-D و SAF-C).

مسیریابی چندقیدی انیپس مش بیسیم

۵- نتیجه گیری

در این مقاله، ما نسبت به بررسی مشکل یافتن یک موضوع / مولفه انیپس مرتبط با K– قید اقدام نموده و در این راستا الگوریتم  K-تقریب  توزیعی بلمن –  فورد را عرضه داشتیم.  به هنگامی ‌که K = 1 صادق باشد، الگوریتم ما به عنوان الگوریتم بهینه برای مشکل متناظر به شمار خواهد آمد. در مقابل، به هنگامی‌که  K ≥ ۲  حاصل شود، نتیجه ما یک الگوریتم O(1)– تقریب توزیعی برای مشکل NP– سخت OMCAP خواهد بود. نتایج عددی نشان دهنده آن هستند که الگوریتم ما بسیار سریع بوده و نتیجه آن بخوبی انیپس حاصل آمده بوسیله بهترین الگوریتم متمرکز می‌باشد.