نشستهای چند پخشی شبکه مش بیسیم

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

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

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

مقالات

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

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

www.irantarjomeh.com

محافظت از نشستهای چند بخشی در شبکه های مش بیسیم

چکیده

به منظور پشتیبانی از مسیر یابی چند بخشی مطمئن در شبکه های مش بیسیم، لازم است تا نسبت به محافظت از نشستهای چند بخشی در برابر نارسایی ها و خرابی های لینک یا گره اقدام نمود. مسئله محافظت از نشستهای چند بخشی در شبکه های مش بیسیم تا آنجایی که از آن اطلاع داریم به عنوان یک مسئله و مشکل جدید مطرح می‌باشد. در این مقاله، ما نسبت به معرفی یک دیدگاه مش ارسال ارتجاعی یا واگشتی برای محافظت از یک نشست چند بخشی در شبکه های مش بیسیم اقدام می‌نماییم. با معرفی و کاربرد مزیت انتشار بیسیم، یک شبکه ارسال ارتجاعی بطور مؤثری نسبت به استقرار دو مسیر مجزای گره برای هر جفت منبع ـ مقصد اقدام می‌نماید. چنین امری باعث خواهد شد تا یک نشست چند بخشی از هرگونه نارسایی یا خرابی گره میانجی یا لینک در امان باشد. بر این مبنا ما نسبت به معرفی چهار الگوریتم غیر مستدل یا ابتکاری اقدام نموده تا آنکه قابلیت حاصل آوردن راه حلهای تقریبی در زمینه بحداقل رسانی تعداد مورد نیاز ارتباطات رادیویی را فراهم آوریم. بر این مبنا، عملکرد این الگوریتمهای ابتکاری، در برابر سیستم مش ارسال ارتجاعی بهینه (ORFM)، ‌که از طریق حل یک مسئله مرتبط با برنامه نویسی خطی عدد صحیح (ILP) در این زمینه حاصل آمده است، را مورد ارزیابی قرار می‌دهیم. نتایج تجربی معرف آن می‌باشند که یکی از این الگوریتمهای ابتکاری، که آن را تحت عنوان الگوریتم مش مجزای حداقل (MDM) می‌خوانیم، در حد کفایت نزدیک به ORFM عمل می‌نماید. علاوه بر این، دریافتیم که دیدگاه مش ارسال ارتجاعی یا واگشتی فراهم آورنده یک رویه محافظتی ۱+۱ مؤثر و کارا برای یک نشست چند بخشی بدون به بار آوردن سربار‌های بیشتر بر یک درخت واحد چند بخشی با حداقل هزینه می‌باشد.

نشستهای چند پخشی شبکه مش بیسیم

۱- مقدمه

اخیراً تعداد زیادی از برنامه های کاربردی تجاری شبکه های متعدد بسیم ظهور نموده‌اند. شبکه مش بیسیم (WMN) یک تکنولوژی نوید بخش جهت پیاده سازی زیر ساختهای بیسیم بشمار می‌آید و بر این مبنا فراهم آورنده تسهیلات خدمات آنلاین بصورت دائمی‌و در هر منطقه‌ای برای کاربران می‌باشد. در مقایسه با شبکه های بیسیم نسل موجود نظیر Wi-Fi یا شبکه های سلولی که از یک خصیصه تک- جهشی برخوردار می‌باشند، شبکه‌های مش بیسیم داده ها را از طریق سیستم ارسال چند- جهشی انتقال می‌دهند. هر گره در شبکه های مش بیسیم نه تنها داده ها را دریافت می‌کند، بلکه نسبت به ارسال ترافیک به گره های دیگر از طریق مسیر بیسیم چند- جهشی نیز اقدام خواهد نمود. در مقایسه با Wi-Fi یا شبکه های سلولی، شبکه های مش بیسیم دارای مزیت های کلیدی مختلفی نظیر سرعت بالا، تداخل پایین، همگرایی سرویس گسترده، هزینه پایین، پیاده سازی سریع حفظ و نگهداری آسان و قدرت زیاد می‌باشد. در آینده، شبکه های بدون سیم از سرعت بالایی برخوردار گردیده و قابلیت فراهم آوردن محدوه گسترده ای از برنامه‌های کاربردی چند بخشی و ارتباطاتی، نظیر IP-TV و سیستم های ویدئویی بر حسب تقاضا (VOD)، را خواهند داشت.

بقیه این مبحث به شرح ذیل دسته بندی شده است. در بخش ۲،  تحقیقات قبلی در ارتباط با مباحث ما مورد بحث قرار خواهد گرفت . در بخش ۳، یک تعریف رسمی‌‌در زمینه مفهوم سیستم مش ارسال ارتجاعی را ارائه خواهیم نمود. در بخش ۴، مسائل و مشکلات را عنوان داشته و یک فرمولاسیون برنامه نویسی عددی صحیح (ILP) جهت محاسبه RFM بهینه را عرضه می‌داریم. بر این مبنا، چندین مضمون ابتکاری جهت حاصل آوردن یک راه حل تقریبی در خصوص سیستم مش ارسال ارتجاعی بهینه در بخش ۵ عرضه شده است. در بخش ۶، نتایج حاصله از تجارب مرتبط با پارامترهای ابتکاری و راه حل های بهینه از ILP را مورد ارزیابی قرار می‌دهیم. در نهایت در بخش ۷ نتیجه گیری ارائه خواهد شد.

نشستهای چند پخشی شبکه مش بیسیم

۲- تحقیقات مرتبط

شبکه های اقتضایی موبایل یا شبکه های ادهوک (MANETها) دارای ویژگیهای مشترکی با WMN ها می‌باشند، نظیر محیط بیسیم و انتقال چند جهشی. تعداد زیادی از پروتکلهای چند جهشی برای MANET ها بطور خاص ارائه شده اند، نظیر پروتکل های MAODV, ODMRP, NSMP, DCMP و غیره. با این وجود، آنها برای شبکه های مش بیسیم مناسب نخواهند بود، چرا که  آنها به طور عمده بر روی مسئله کار با تغییرات توپولوژیکی پیوسته، بواسطه تحرک گره و مشکل محدودیت توان که در شبکه های اقتضایی مشترک می‌باشند، کار می‌کنند. علاوه بر این، بواسطه تغییرات مکرر توپولوژیکی، احتمال داشتن یک مکانیزم مؤثر که بتواند آگاه بر توپولوژی شبکه جهانی باشد مشکل خواهد بود و بر این مبنا حاصل آوردن یک رویه انتشار چند بخشی بهینه در مقیاس شبکه مشکل آفرین می‌باشد. در مقابل، مسیریابهای مش در WMNها غالبآً به صورت ایستگاهی بوده و بدون محدودیت  نیرو یا برق بکار گرفته می‌شوند. بنابراین، تغییر مکرر توپولوژی یک مشکل عمده برای WMNها نخواهد بود. در نتیجه، هدف پروتکل های WMN از پارامتر «حفظ موجود بودن مسیر» بسمت پارامتر «یافتن یک مسیر مطلوب با عملکرد بالا» تغییر نموده است. بنابراین، ویژگیهای مرتبط با سنجش عملکرد برای شبکه های مش بیسیم برای مواردی چون تاخیر، توان عملیاتی یا خروجی کار، تعداد ارتباطات انتشار یافته، بجای تعداد جهش ها یا کارایی انرژی، مطرح می‌باشد.

نشستهای چند پخشی شبکه مش بیسیم

۳- سیستم مش ارسال ارتجاعی

ما نسبت به پیشنهاد یک دیدگاه مش ارسال ارتجاعی یا واگشتی جهت محافظت از یک نشست چند بخشی در شبکه های مش بیسیم اقدام نمودیم. یک مش ارسال ارتجاعی به عنوان مجموعه ای از مسیرهای بیسیم چند جهشی تعریف می‌شود که دارای ویژگیهای ذیل می‌باشد. برای هر جفت منبع ـ مقصد در نشست چند بخشی، مش ارسال ارتجاعی حداقل شامل دوگره ـ مجزا می‌باشد که منبع و مقصد را به صورت موازی و همزمان به یکدیگر متصل می‌نماید. دلیل آنکه ما مسیرهای مجزا گره را بر مسیرهای مجزای لینک ترجیح می‌دهیم آن است که در سناریوی بیسیم هر دوی لینک و گره مستعد بروز مشکل و خرابی می‌باشند. بدین روش، هر خرابی لینک منفرد یا خرابی گره سطح مشترک یا میانجی در مش ارسال، باعث ایجاد وقفه یا مشکل در نشست چند بخشی نخواهد شد.

مفهوم مش ارسال ارتجاعی با استفاده از یک توپولوژی شبکه کوچک همانگونه که در شکل یک(الف) نشان داده شده است معرفی می‌گردد. در این توپولوژی یا همبندی، ما دارای یک گره منبع (علامت گذاشته شده بوسیله S)، سه گره سطح میانجی یا مشترک (علامت گذاشته شده بوسیله M₁، M₂ و M₃ ) و دو گره مقصد (علامت گذاشته شده بوسیله D₁ و D₂) می‌باشیم. از آنجاییکه هر دو مورد M₁ و M₂  در محدوده انتقال S می‌باشند، بواسطه مزیت انتشار بیسیم رسانه بدون سیم، تنها یک ارتباط ارسالی از S جهت دسترسی به M₁ و M₂  کفایت خواهد داشت. متعاقب این امر، پاکت چند بخشی را می‌توان بعداً از M₁  به سمت هر دو مضمون D₁ و M₃، یا از M₂  به D₂ و M_3،  و از M₃ به هر دو مورد D₁ و D₂ ارسال نمود. بطور آشکار، چنین دامنه‌ای از چهار رویه انتقال پیام بوجود آورنده یک مش ارسال ارتجاعی می‌باشد که دقیقاً شامل دو گره ـ مسیر مجزا برای هر جفت منبع ـ مقصد می‌باشد.

نشستهای چند پخشی شبکه مش بیسیم

۴- طرح مسئله و فرمالاسیون های مربوط بدان

یک توپولوژی مش بیسیم در یک حالت نمودار مستقیم G=(V,E) را در نظر بگیرید، جائیکه V مجموعه ای از گره ها و E مجموعه ای از لبه های متصل شده به گره ها می‌باشد. یک لبه مستقیم (m,n) ازگره m  به گره n در G معرف آن است که گره n در محدوده انتقال گره m می‌باشد. بر این مبنا، ما در نظر می‌گیریم که یک نشست چند بخشی حاوی یک گره منبع می‌باشد که به وسیله S و همچنین مجموعه ای از D وابسته به گره های مقصد k مشخص شده است. ما خواستار یافتن یک شبکه ارسال ارتجاعی بهینه می‌باشیم، به گونه ای که هر جفت منبع ـ مقصد به وسیله دو مسیر گره ـ مجزا به هم متصل شده باشند، در حالی که مجموعه کلی انتقال یا ارسال‌های اعمال شده  به حداقل برسد. ما چنین موردی را بدین گونه یادآور می‌شویم که در صورتی که دو مسیر موازی به صورت مجزا از گره باشند، هرگونه خرابی در گره میانی، که ممکن است بر یک مسیر تأثیر‌گذارد، بر روی مسیر دیگری تأثیر نخواهد گذاشت. برای راحتی تشریح، ما به یکی از دو مسیر موازی به عنوان مسیرP و به مسیر دیگر به عنوان مسیرB رجوع خواهیم داشت.

نشستهای چند پخشی شبکه مش بیسیم

۵- الگوریتمهای ابتکاری

در عین آنکه فرمولاسیون ILP که در بخش قبل ارائه شده است را می‌توان جهت تکمیل راه حل بهینه مشکل ORFM بکار گرفت، برای شبکه‌ای که از توپولوژیهایی با اندازه بزرگی استفاده می‌کند، این موضوع مشخص شده است که هیچگونه روش مؤثری وجود ندارد که بر اساس آن بتوان این مدل ILP را در یک زمان منطقی حل نمود. در این بخش، ما نسبت به معرفی ۴ الگوریتم ابتکاری که می‌توان از آنها جهت یافتن راه حلهای تقریبی در زمینه مشکل ORFM، در یک زبان چندجمله‌ای بهره جست، اقدام می‌کنیم. توجه داشته باشید که دو الگوریتم اول جزء طرحهای محافظت مبتنی بر درخت می‌باشند و دو الگوریتم آخر جزء طرحهای محافظت مبتنی بر مسیر بشمار می‌آیند. ایده ذیل در کلیه این چهار الگوریتم بکار گرفته شده است. خصیصه‌های بکار گرفته شده برای هر الگوریتم خاص بعداً‌ در زیر بخشهای متعاقب تشریح خواهند شد.

۱-۵٫ الگوریتم درخت گره- مجزا (NDT)

اولین الگوریتم ابتکاری که تحت عنوان الگوریتم درخت گره ـ مجزا (NDT) خوانده می‌شود به عنوان الگوریتم ۱ تشریح می‌شود. ایده اصلی NDT یافتن دو گره ـ مجزا برای کلیه مقصدها می‌باشد. اولین مرحله ایجاد یک درخت چند بخشی PT با حداقل تعداد ارسالها با استفاده از الگوریتم ابتکاری مبتنی بر-  Greedy در ( ۱۲) می‌باشد. پس از آن ما کلیه گره‌های سطح میانی PT را از مجموعه ی گره V حذف نموده و یک درخت چند بخشی حداقلی جدید بنام BT را در V ایجاد می‌کنیم. از آنجایی که درخت PT و BT  دارای هیچگونه گره مشترکی بجز منبع نمی‌باشند، کلیه گره‌های سطح میانی PT و BT  در گره های ارسال ترکیبی FN مش ارسالی ارتجاعی قرار داده می‌شوند.

۲-۵٫ الگوریتم درخت گره ـ مجزای اصلاح شده (RNDT)

الگوریتم درخت گره ـ مجزا اصلاح شده ابتکاری دومی ‌به عنوان یک نگارش تصحیح شده الگوریتم NDT بشمار می‌آید. در الگوریتم NDT، به هنگامی که گره های میانی PT از V حذف می‌شوند، احتمال یافتن یک درخت چند بخشی دیگر بصورت موفقیت آمیز کم خواهد شد. علاوه بر این، چنین الگوریتمی ‌قابلیت بهره گیری از مزیت انتشار بیسیم برخی از گره ها واقع در درخت برای BT را نخواهد داشت. بجای آن با یافتن درخت دیگر از طریق حذف کلیه گره های سطح میانی اولین درخت، RNDT نسبت به بهره گیری از گره های میانجی درخت چندبخشی جهت یافتن مسیر گره ـ مجزا اقدام می‌نماید. پس از آنکه یک درخت PT چند بخشی حداقل یافت شد، RNDT گره های سطح میانی PT را در FN قرار داده و هزینه های کلیه لینکهای خروجی کلیه گره های سطح میانی PT را صفر می‌کند.

۳-۵٫ الگوریتم مش مجزای به اشتراک گذاشته شده (SDM)

الگوریتم مش مجزای  به اشتراک گذاشته شده (SDM) و الگوریتم پس از آن یعنی مش مجزای حداقل (MDM) از دیدگاههای مختلف جهت ایجاد مش ارسال ارتجاعی استفاده می‌کنند. هر دو الگوریتم در مقابل نسبت به محاسبه جفت مسیر گره- مجزا برای هر گره مقصد اقدام می‌کنند. هدف هر دو این دیدگاه ایجاد یک جفت مسیر گره ـ مجزا برای گره سطح میانی مشترک اشتراکی تا حد ممکن می‌باشد.

۴-۵٫ الگوریتم مش مجزای حداقل (MDM)

الگوریتم مش مجزای حداقل (MDM) سبب ارتقای SDM به روش ایجاد جفت مسیر گره ـ مجزا می‌شود. بجای یافتن دو مسیر گره ـ مجزا بصورت ترتیبی، MDM از الگوریتم سوربال جهت یافتن جفت مسیر گره ـ مجزا با حداقل هزینه در زمانی یکسان اقدام می‌نماید. با وجود آنکه SDM قابلیت یافتن کوتاهترین مسیر برای هر مقصد را خواهد داشت، مجموعه هزینه دو مسیر مجزای ـ گره ممکن است بصورت بهینه نباشند. بخش‌های دیگر MDM دقیقاً ‌همانند SDM می‌باشند.

نشستهای چند پخشی شبکه مش بیسیم

۶- نتایج تجربی و آنالیز

بمنظور مقایسه عملکرد طرحهای محافظتی مختلف که در بخش ۵ معرفی شدند، ما نسبت به ایجاد یک شبکه نمونه نشان داده شده در شکل ۲ با استفاده از Qualnet برای اعمال رویه‌های تجربی خود اقدام نمودیم. در اینجا ۲۸ گره به صورت توزیع شده یکنواخت در امتداد شبکه‌ها وجود دارند. برای هر یک از اندازه‌های گروه چندبخشی M، در محدوده ای از ۱ الی ۲۵، ما بصورت تصادفی یک گره را به عنوان یک گره منبع و گره های M دیگر را به عنوان گره های مقصد انتخاب نمودیم. پس از آن، ما از ۴ الگوریتم ابتکاری مختلف جهت اعمال ارتباط از منبع به مقصد در چنین شبکه ای بهره جستیم. علاوه بر این ما از CPLEX جهت حاصل آوردن راه حل بهینه RFM برای گروه چند بخشی استفاده نمودیم. بمنظور مقایسه سربار شبکه مش ارسال ارتجاعی در برابر یک درخت چند بخشی واحد ما نسبت به محاسبه هزینه درخت چند بخشی اقدام نمودیم که از طریق الگوریتم ابتکاری وابسته به- Greedy و همچنین درخت چند بخشی بهینه بر حسب تعداد حداقل ارسالها بوسیله ILP در CPLEX مشخص شد. برای هر M، ما آزمایشات خود را برای ۵۰ بار تکرار نمودیم که هر کدام از یک مجموعه انتخاب تصادفی گره ها به عنوان اعضای نشست چند بخشی بهره جسته‌اند.

نشستهای چند پخشی شبکه مش بیسیم

۷- نتیجه گیری وتحقیقات آینده

ما وضعیت ارتجاعی سیستم چند بخشی در برابر نارسائی ها یا خرابی های گره یا لینک را مورد بررسی قرار دادیم، که خود به عنوان یک مشکل جدید در شبکه های مش بی سیم بر مبنای داده‌های ما به شمار می‌آید. در این مقاله ، ما نسبت به ارائه یک الگوریتم مش ارسال ارتجاعی (RFM) جهت مراقبت و محافظت از نشست چند بخشی استفاده نمودیم که به کار گیرنده مزیت انتشار بیسیم می‌باشد. بر این مبنا، عقیده بر این است که مشکل یافتن یک RFM بهینه NP-complete خواهد بود. با توجه بدین مبحث، ما نسبت به ارائه دادن ۴ الگوریتم ابتکاری زمان چندجمله‌ای ‌جهت محافظت از نشست چندبخشی به صورتی مؤثر و کارا استفاده نمودیم. یکی از این الگوریتمهای ابتکاری که بنام الگوریتم مش مجزای حداقل (MDM) نامیده می‌شود دارای عملکردی بهتری در مقایسه با الگوریتمهای دیگر بر حسب تعداد ارسالها می‌باشد. چنین الگوریتمی‌ همچنین نزدیک به راه حل بهینه حاصل آمده از طریق برنامه خطی عددی (ILP) در CPLEX می‌باشد. علاوه بر این ، یک شبکه ارسال ارتجاعی ـ مش قابلیت فرا هم آوردن محافظت “۱+۱” در برابر نشست چند بخشی با سربار بیشتر محدود به سمت یک درخت چند بخشی واحد را خواهد داشت.

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