تخصیص کانال و مسیریابی چندپخشی شبکه مش بیسیم چندکانالی چندرادیویی

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

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

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

مقالات رایگان

مطالعه 20 الی 100% رایگان مقالات ترجمه شده

1- قابلیت مطالعه رایگان 20 الی 100 درصدی مقالات 2- قابلیت سفارش فایل های این ترجمه با قیمتی مناسب مشتمل بر 3 فایل: pdf انگیسی و فارسی مقاله همراه با msword فارسی -- تذکر: برای استفاده گسترده تر کاربران گرامی از مقالات آماده ترجمه شده، قیمت خرید این مقالات بسیار کمتر از قیمت سفارش ترجمه می باشد.  

چگونگی سفارش

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

www.irantarjomeh.com

تخصیص کانال و مسیریابی چندپخشی شبکه مش بیسیم چندکانالی چندرادیویی

تخصیص کانال و مسیریابی چندپخشی شبکه مش بیسیم چندکانالی چندرادیویی

تخصیص کانال و مسیریابی چند پخشی در شبکه های مش بی سیم چند کانالی – چند رادیویی

چکیده

فرایندهای چند پخشی به عنوان یک سرویس شبکه بندی کلیدی به شمار می آیند که قابلیت تحویل یکباره اطلاعات از منبع به مقاصد متعدد را داشته و به عنوان یک ویژگی بنیادی در تعامل با سیستم های کاربردی چند رسانه ای، نظیر کنفرانس ویدئویی، آموزش از راه دور و دیگر شکل های توزیع محتوایی بر فراز شبکه های مش بی سیم چند کاناله – چند رادیویی (MCMR WMNs)) به شمار می آید. با این وجود، پروتکل چند پخشی که در این شبکه ها طراحی شده است از ارتباط تنگاتنگی با گره های خاص ارتباطاتی کانال – رادیویی برخوردار می باشد تا از این طریق قابلیت تحقق حداقل تداخلات ارتباطی وجود داشته باشد. جریان اصلی تحقیقاتی در پروتکل چند پخشی WMN به سمت استراتژی های ابتکاری یا فرا ابتکاری جهت می یابد که عمدتاً در بردارنده یک رویکرد ترتیبی جهت حل مشکلات مسیریابی چند پخشی و تخصیص کانال به عنوان دو مشکل فرعی مجزا می باشد. پیکربندی حاصله از شبکه در چنین موردی به صورت زیر بهینه مدنظر می باشد. بر این مبنا چنین مشخص می گردد که تعاملات بین این دو مشکل فرعی در حقیقت به عنوان مولفه ها و ویژگی های خاص مربوط به چنین مسئله ای مطرح می باشند. در این مقاله، در ابتدا، ما نسبت به ارائه یک فرایند فرمول بندی ریاضیاتی بین لایه ای تخصیص توامان کانال و ایجاد درخت چند پخشی در MCMR WMNs، که در تضاد با طرح های موجود می باشد و تضمین کننده یک راه حل بهینه است، اقدام می نمائیم، نتایج شبیه سازی نشان دهنده آن می باشند که طراحی بین لایه ای ما دارای عملکرد بهتری در مقایسه با LCA، MCM و الگوریتم ژنتیک – آنیلینگ شبیه سازی شده – ، جستجوی تابو – روش های مبنای، پیشنهاد شده به وسیله Zeng و همکاران (2010) و Cheng و همکاران (2011) به ترتیب می باشد، که خود بر حسب تداخل داخل کانالی مشخص می گردد. دوماً، از آن جایی که مدل سازی بهینه سازی توامان به واسطه پیچیدگی آن نسبتاً سخت می باشد، ما نسبت به تسکین ضروریات بهینگی اقدام نموده و به صورت جایگزین اقدام به بررسی گزینه فرمول بندی لایه ای نموده ایم که در آن قابلیت تضمین یک راه حل بهینه برای هر مسئله فرعی وجود خواهد داشت. طراحی جایگزین ما، در مقایسه با موارد قبلی با توجه به حداقل رسانی تداخل از عملکرد ممتازی برخوردار می باشد. بر این مبنا ما یکسری از شبیه سازی های گسترده را جهت تحلیل بهینگی و پیچیدگی دو استراتژی طراحی خود انجام می دهیم.  نتیجه کلی این رویه مشخص کننده  بهینگی  برآوردهای  ما  می باشد. بعلاوه، مشکل پیچیدگی نیز برحسب مصرف حافظه و همچنین زمان مورد نیاز جهت حل مشکل چند پخشی مورد ارزیابی قرار می گیرد.

کلمات کلیدی: شبکه مش بی سیم، چند کانالی، چند رادیویی، تخصیص کانال، ایجاد درخت چند پخشی، طراحی بین لایه ای، برنامه ریزی عدد صحیح باینری

تخصیص کانال و مسیریابی چندپخشی شبکه مش بیسیم چندکانالی چندرادیویی

1- مقدمه

شبکه مش بی سیم (WMN) به عنوان یک الگوی شبکه بندی مناسب اقتصادی برای ارسال  بر حسب – QoS با قابلیت مقیاس بندی ترافیک همگن بر فراز شبکه های کالایی بی سیم بزرگ مقیاس بشمار می آید [1،2]. شبکه های مش بی سیم (WMNها) متشکل از مسیر یاب های مش و کلاینت های مش می باشند که در آن مسیر یاب های مش، در تضاد با گره ها در یک شبکه اقتضایی سیار (MANET) دارای حداقل میزان جابجایی یا تحرک بوده و تشکیل دهنده استخوان بندی WMNs به شمار می آیند. آن ها همچنین فراهم آورنده دسترسی شبکه برای مش و کلاینت های متعارف می باشند [1]. در مقایسه با شبکه های حس گر بی سیم (WSNs)، گره های مش از محدودیت انرژی در رنج نمی باشند. با این وجود، هدف اصلی در این شبکه ها به حداکثر رسانی ظرفیت لایه فیزیکی از طریق تداخل در کمینه سازی مولفه ها می باشد، که نوعاً از طریق ارائه ویژگی های گیرنده – فرستنده برای هر گره از طریق رادیوهای متعدد تنظیم شده بر روی کانال های متعدد [3 و4] قابل حصول خواهد بود، بنابراین چنین موردی را می توان به عنوان یک مولفه تعاملی در تعدادی از ارتباطات موازی به کار گرفت [6].

از جمله کاربردهای کلیدی برای WMNs چند کاناله – چند رادیویی (MCMR WMNs) سیستم های چند پخشی – مبنا نظیر کنفرانس ویدئویی، بازی های آنلاین، وبکست و فراگیری از راه دور، و موارد دیگر می باشند. با این وجود، در عین آن که ارتباطات بی سیم به طور ذاتی در تناسب با اجرای مسیریابی چند پخشی به واسطه طبیعت  انتشار  این رسانه  از  طریق  هوا  می باشد، تداخل بین کانالی در WMNs نقش مهمی را در تعیین نرخ حقیقی داده های قابل حصول برای یک سرویس چند پخشی بازی می نماید. تداخل بی سیم به هنگامی رخ می دهد که دو لینک در داخل فاصله  دو – جهشی  یکدیگر  به یک کانال  مشخص تخصیص  داده  می شوند. این تداخل که به واسطه تضاد کانال به وجود می آید سبب از بین رفتن عملکرد مناسب ارتباطات بی سیم به طور قابل توجهی می شود. بنابراین، برای مسیریابی چند پخشی، هر لینک در روی درخت چند پخشی را می بایست به یک کانال اختصاص داد که تداخل حداقلی آن محرز و مشخص شده باشد. همان گونه که به طور آشکار در مدل این پروتکل مشخص شده است [6،17، 43]، که بعلاوه به عنوان مدل تداخل اصلی در ارتباط با فرمول بندی ارائه شده در این مقاله نیز به حساب می آید، به حداقل رسانی تعداد لینک های تداخلی در یک شبکه مش بی سیم تاثیر مستقیمی در ارتباط با به حداکثر رسانی عملکرد سیستمی خواهد داشت، که این مطلب در مراجع [31،32، 38] مورد بحث قرار گرفته اند.

به طور آشکار، مسیریابی چند پخشی در WMNs نه تنها نیازمند به کارگیری بهترین درخت مسیریابی می باشد، بلکه می بایست اقدام به تخصیص کانال های مناسب برای لینک های آن نیز نمائیم. در MCMR WMNs، مشکل به حداقل رسانی تداخل به طور عادی بر مبنای ارائه طرح های تخصیص کانال در لایه MAC مورد خطاب قرار می گیرد. ارتباطات کارامد کانال – رادیویی غالباً به بهای ارضای محدودیت های پیچیده تر مربوط به اتصال پذیری میسر خواهد شد. علی الخصوص، برای آن که دو گره را بتوان به خوبی متصل نمود، نه تنها آن ها می بایست در محدوده شعاع انتقال با یکدیگر قرار گرفته باشند، بلکه کانال مشابه را نیز می بایست برای مولفه های رادیویی آن ها تخصیص داد. مسیریابی چند پخشی، تحت این محدودیت اضافه، حتی پیچیده تر نیز می گردد، بنابراین هم اکنون لازم است تا اقدام به ساخت درخت چند پخشی برای ارتباط کانال – رادیویی نمائیم که همچنین قابلیت به حداقل رسانی تداخل های بین کانالی را نیز خواهد داشت.

 علیرغم تعداد وسیع برنامه های کاربردی و اهمیت عملی این مسئله، تحقیقات اندکی اقدام به مطالعه رویه بهینه سازی عملکرد چند پخشی در MCMR WMNs نموده اند. ویژگی اصلی تحقیقاتی در این ناحیه تخصیص کانال و مسیریابی چند پخشی به عنوان دو مسئله فرعی مجزا می باشد که می بایست اقدام به حل آن ها به صورت ترتیبی نمود [31،32،36 – 38 و 40]. همان گونه که در مراجع [33- 35 و 39] مشخص شده اند، حتی ممکن است این رویه نیز به عنوان یک ویژگی راه حل برای هر دوی مشکلات فرعی در نظر گرفته شود که اقدام به محاسبه مقدماتی آن ها شده و چنین مواردی را به عنوان ورودی به مولفه دیگر در نظر گرفت. با این وجود، مورد نامطلوب در ارتباط با این طرح ها آن است که تعامل متقاطع بین این دو مشکل فرعی را نمی توان به حساب آورد و آن که اتکای آن به راهکارهای ابتکاری یا ابر ابتکاری در تعامل با یک راه حل بهینه در این زمینه نمی باشد.

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

در این مقاله، ما یک طراحی بین لایه ای را برای بهینه سازی توامان مشکل تخصیص کانال و ایجاد درخت چند پخشی ارائه می نمائیم. در تضاد با مقاله های قبلی، دو مشکل فرعی به صورت توام حل گردیده و تعامل آن ها با یکدیگر به طور کامل بررسی می گردد. فرمول بندی ریاضیاتی اتخاذی در این مقاله بر مبنای یک برنامه ریزی عدد صحیح باینری (BIP) می باشد، که در مقایسه با مدل های ابتکاری و ابر ابتکاری قبلی تلقی شده، و تضمین کننده راه حل بهینه در این زمینه می باشد. ما این امر را نیز مورد بحث قرار می دهیم که فرمول بندی های برنامه ریزی مبنای خطی در تناسب با مقیاس های کم چگالی و محدود مجموعه های WMN می باشند [20، 21]. این نوع از فرمول بندی ها همچنین دارای مزیت گسترش آسان هستند به گونه ای که مشکلات مقید مبنای آن ها از نقطه نظر تعریفی را می توان به گونه ای مرتفع نمود تا در تناسب با یک محتوای طراحی جدید ارائه شوند. سیستم کاربردی BIP، مخصوصاً در مجموعه بهینه سازی متقاطع ما، ارائه دهنده یک طرح تخصیص کانال می باشد که به طور کامل قابلیت به اتمام رساندن انباره منابع موجود را خواهد داشت (یعنی کانال ها و رادیوها) و بنابراین لازم است تا قابلیت ایجاد ساختار مسیریابی چند پخشی (با توجه به تداخلات حداقلی) را داشته باشیم. مدل سازی ما مخصوصاً فراهم آورنده یک چارچوب مرجع جهت ارزیابی طرح های قابل قیاس متمرکز و توزیعی از طریق ارائه ویژگی های بهینگی خروجی فرمول بندی BIP می باشد.

نتایج شبیه سازی مشخص کننده آن هستند که طراحی بین لایه ای پیشنهادی ما از عملکرد بهتری در مقایسه با دو طرح دیگر ابتکاری بحث شده در مبحث Zeng و همکاران (2010) برخوردار می باشد [31، 32] که عمدتاً تحت عنوان تخصیص سطح کانال (LCA) و الگوریتم چند پخشی چند کاناله (MCM) و همچنین الگوریتم ژنتیک (GA-)، آنیلینگ شبیه سازی شده (SA-)، و جستجوی تابو (TS ـ مبنا) می باشند که در مراجع [36-38] برحسب بروز مشکلات تداخلی به وسیله شبکه مورد بحث قرار گرفته اند. بعلاوه، از آن جایی که مدل سازی بهینه سازی توامان عمدتاً با توجه به پیچیدگی آن سخت و طاقت فرسا می باشد، ما سعی در تعدیل ضروریت بهینگی در این زمینه نموده و به طور جایگزین اقدام به بررسی گزینه فرمول بندی لایه ای جهت اطمینان از راه حل بهینه برای هر مسئله فرعی در مقابل نموده ایم. همان گونه که به وسیله نتیجه شبیه سازی ها مشخص شده است، تداخل مرتبط با رویکرد لایه ای، با وجود آن که از نقطه نظر حاشیه ای بیشتر از طراحی بین لایه ای می باشد، همچنان به طور معنی داری در مقایسه با دیگر روش های مبتنی بر LCA، MCM، GA-، SA- و TS ـ مبنا کوچکتر می باشد. کارایی چارچوب ما متعاقباً به وسیله متضاد سازی ویژگی های طرح های لایه ای و بین لایه ای ما بر حسب دو مولفه بهینگی و پیچیدگی مورد بررسی قرار می گیرد. راهکار اندازه گیری استفاده شده جهت برآورد بهینگی دو رویکرد پیشنهادی شامل موارد تداخلی بروز کرده در شبکه می باشند. از طرف دیگر، پیچیدگی نیز برحسب میزان مصرف حافظه و همچنین زمان مورد نیاز جهت حل مشکل چند پخشی براورد شده است. بعلاوه، پیچیدگی زمانی دو روش پیشنهادی نیز مورد تجزیه و تحلیل قرار می گیرد.

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

ادامه این مقاله به شرح ذیل سازماندهی شده است. در بخش 2، ما به طور مختصر روش های مسیریابی چند پخشی جاری در MCMR WMNs را مورد بررسی قرار داده و نکات قوت و ضعف آن ها را مشخص می سازیم. جزئیات فرمول بندی های ریاضیاتی برای طرح های لایه ای و بین لایه ای پیشنهادی نیز در بخش 3 ارائه می گردند. در بخش 4، مسایل مرتبط با اتصال پذیری و رویداد لوپ / حلقه برای چارچوب مورد نظر ما بررسی خواهد شد. در بخش 5 جزئیاتی در خصوص مطالعه شبیه سازی مقایسه ای با تحلیل بهینگی و پیچیدگی راه حل های ما عرضه می شود. در بخش 6، دو طرح پیشنهادی با توجه به پیچیدگی زمانی و نیازهای حافظه بررسی می گردند. در نهایت در بخش 7 ما به نتیجه گیری این مقاله خواهیم پرداخت.  

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

همانگونه که در بخش مقدمه خاطرنشان شد، به منظور حاصل آوردن عملکرد بالا در WMNs، لازم است تا نسبت به کاهش تداخل اقدام نماییم. از جمله مهمترین تکنیک های کاهش تداخل تخصیص کانال می باشد که مشخص کننده این موضوع است که کدام یک از کانال ها را می بایست به یک رادیو تخصیص داد آن هم به روشی که دارای کمترین سطح تداخل کلی باشد. تخصیص کانال برای یک مسیریابی تک پخشی در MCMR WMNs به طور گسترده ای در مباحث ارائه شده (به طور مثال [7 ـ 17]) مورد بحث قرار گرفته است. ویژگی اصلی تحقیقاتی در این مبحث را می توان به دو رده بندی تقسیم نمود. مورد اولی در حقیقت نوعی فرآیند تفکیکی می باشد که در آن تخصیص کانال بر روی یک توپولوژی مسیریابی خاص اعمال می گردد [9، 12 و 15] یا مسیریابی با توجه به یک طرح تخصیص کانال مشخص شده تکمیل خواهد شد [8، 10، 11 و 14]. مورد آخری به عنوان روش های توأمان یا متصل شناخته می شود [13 و 17].

به طور آشکار، رویه های پیاده سازی تک پخشی به راحتی یا حداقل با مقیاس پذیری کافی قابلیت کاربرد در الگوی یک- به- چند یک مجموعه ارتباطاتی چند پخشی نوعی را نخواهند داشت. به علاوه، با توجه به محدودیت پهنای باند عملیات شبکه های بی سیم، راه حل های چند پخشی با سیم موجود را نمی توان برای سیستم های مش بدون انجام تغییرات اساسی در ارتباط با رفتار آنها به منظور کاهش سربار اعمال داشت. فرآیند چند پخشی در MANETs و WSNs همچنین مخاطب قرار دهنده بازیافت مسیر و ویژگی های مصرف انرژی به ترتیب است که از نقطه نظر ویژگی متفاوت از مسایل محوری عملکرد کلی و تداخل به وجود آمده در ناحیه میانی MCMR WMNs می باشد. با توجه به آنکه رادیوهای متعددی در هر گره ممکن است به صورت دینامیکی اقدام به باز نمودن کانال های مختلفی می نمایند، مسیریابی در این شبکه ها با پیچیدگی بیشتری روبرو است. فرآیند چند پخشی WMN ـ مبنا در مراجع [18، 19، 22 ـ 27 و 41] تشریح شده است، با این حال چنین مواردی در بردارنده سناریوهای تک کاناله ـ تک رادیویی می باشند. تحقیق انجام شده در مرجع [28] از طرف دیگر مجموعه های مربوط به مؤلفه های چند کاناله تک رادیویی را مخاطب قرار می دهد که توصیف کننده پیکربندی های کاملاً متفاوت شبکه می باشند. به علاوه، تأکید اصلی در مرجع [28] بر روی به حداکثر رسانی بازده کلی است که بر مبنای آن نیازی به ایجاد درخت چند پخشی نباشد، در تضاد با مسئله ارائه شده در این مقاله که به طور الزامی شامل تخصیص کانال و ایجاد درخت چند پخشی به صورت مشترک و با توجه به حداقل رسانی تداخل می باشد.

3- چارچوب ریاضیاتی

چارچوب ریاضیاتی ارائه شده در این مقاله به طور اساسی یک فرمول بندی BIP می باشد که در تضاد با ویژگی های ابتکاری جاری یا طرح های فوق ابتکاری، قابلیت تضمین بهینگی راه حل را خواهد داشت. با توجه به تعریف مسئله بر حسب مجموعه ای از محدودیت های ناتساوی / مساوی خطی، یک مدل BIP، به عنوان گونه ای از برنامه ریزی خطی، قابلیت تعیین راهکار مشخص جهت حاصل آوردن بهترین راه حل ممکن را خواهد داشت. از نقطه نظر هندسی، یک ناحیه محتمل، در قالب چند وجهی محدب، با توجه به محدودیت های خطی تعریف می شود. در داخل این ناحیه، به شرط آنکه یک راه حل محتمل وجود داشته باشد و همچنین تحت این شرایط که تابع هدف خطی کراندار باشد، نتیجه بهینه غالباً در کرانه مجموعه ـ سطح بهینه از طریق اصل به حداکثررسانی / به حداقل رسانی توابع محدب / مقعر قابل حصول خواهد بود [45]. با توجه به ویژگی های کلی و تناسب مجموعه فرمول بندی قیدها مشکل مورد نظر، BIP قابلیت تضمین بهینگی کلی نتیجه حاصله را خواهد داشت.

3ـ1. مدل سازی سیستم و فرضیه ها

در این بخش، ما فرضیه های فرمول بندی ریاضیاتی خود برای مسئله ایجاد درخت چند پخشی با حداقل تداخل را ارائه می نماییم. ما اقدام به فرمول بندی مدل های BIP خود جهت یافتن درخت چند پخشی مبتنی بر ـ MCT نموده ایم. با توجه به محاسبه تداخل، همانند مرجع [31 ـ 40] ما مدل پروتکل تشریح شده در [41 و 43] را پذیرفته ایم. در این مدل، یک انتقال مشخص از گره Src به گره Des تنها در صورتی به صورت موفقیت آمیز حاصل خواهد شد که: (1) فاصله گره ها کمتر از محدوده انتقالی باشد، و: (2) عدم وجود یک گره سوم که در محدوده تداخلی گره گیرنده Des قرار گرفته و مشغول انتقال می باشد. مدل تطبیقی را می توان متعاقباً جهت تطابق با پروتکل های MAC سبک ـ IEEE 802.11 مورد پالایش قرار داد، یعنی گره ارسال Src می بایست بدون تداخل باشد به گونه ای که قابلیت دریافت مؤلفه های تصدیقی لایه لینک از گره گیرنده  Des را داشته باشد. مخصوصاً، هر گره Temp، که در محدوده تداخل Src یا Des قرار گرفته باشد را نباید ارسال داشت.

3ـ2. روش های پیشنهادی

همانگونه که قبلاً ذکر شد، در مدل های موجود تعامل متقابل بین الگوریتم چند پخشی در شبکه و تخصیص کانال در لایه MAC مورد توجه قرار نگرفته است. بنابراین، در این بخش، ما ارائه دهنده یک فرمولاسیون مبتنی بر BIP می باشیم که در آن هر دوی مشکلات ایجاد درخت چند پخشی و تخصیص کانال به صورت توأم با هم حل می شوند. ما این روش را تحت عنوان طراحی “بین لایه ای” می نامیم. متعاقباً، ما فرمول بندی دیگری را پیشنهاد می نماییم که تحت عنوان “طراحی ترتیبی” مدنظر خواهد بود که در آن راه حل بهینه برای هر مسئله فرعی فراهم می گردد.

A- روش بین لایه ای پیشنهادی

در این بخش متغیرهای ضروری بکار گرفته شده در داخل مدل بین لایه ای BIP همراه با محدودیت های تعریف شده توصیف می گردند.

A.1 متغیرهای تعریف شده

قبل از ارائه مدل بین لایه ای BIP برای ایجاد درخت چند پخشی مشترک و همچنین حل مسئله تخصیص کانال، لازم است تا متغیرهای ضروری را تشریح نماییم. در موارد ذیل متغیرهای مربوطه مورد بحث قرار می گیرند.

A.2  قیدهای تعریف شده

در موارد ذیل قیدهای ضروری در ارتباط با طراحی بین لایه ای ارائه می شوند.

از تعریف درخت چند پخشی، تعداد لینک های در حال ورود به یک گره، به استثنای مبدأ چند پخشی و هدف چند پخشی، می بایست تا بیشترین حد 1 باشند. قید (6) ارضاکننده این ویژگی می باشد.

4- اتصال پذیری و ملاحظات حلقه

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

4ـ1 اتصال پذیری

ما نسبت به بررسی اتصال پذیری درخت چند پخشی در روش بین سطحی پیشنهادی اقدام می نماییم. یک خط مشابه استدلال در این زمینه نیز قابلیت کاربرد در مورد طراحی ترتیبی ما را خواهد داشت.

تعریف 1. اتصال پذیری تنها در صورتی حاصل خواهد شد که یک مسیر بین مبدأ چند پخشی به کلیه اعضای گروه چند پخشی وجود داشته باشد.

ویژگی 1. فرمولاسیون BIP، ارائه شده در بخش 3، قابلیت تضمین اتصال پذیری در درخت چند پخشی را خواهد داشت.

اثبات: ما ایده اتصال پذیری را با استفاده از یک گراف دیسک واحد در شکل 2 (الف) بدون از دست دادن کلیت نشان می دهیم. در این گراف، هر لینک بین دو گره معرف آن می باشد که آنها در داخل محدوده انتقالی به یکدیگر قرار دارند. دو گره لینک داخلی قابلیت برقراری ارتباط را خواهند داشت آن هم در صورتی که صرفاً اعضای کانال یکسانی برای یکی از رادیوهای آنها تخصیص یابد. MS مشخص کننده مبدأ چند پخشی و MT نیز مشخص کننده هدف چند پخشی می باشد.

4ـ2. رویداد حلقه

ما صحت فرمولاسیون پیشنهادی خود برای روش بین لایه ای بر حسب مسئله فرمول بندی حلقه با استفاده از ویژگی ذیل را مورد بررسی قرار می دهیم. در اینجا مجدداً ما بدترین حالت سناریو را در نظر خواهیم گرفت. یک تحلیل مشابه نیز برای طرح ترتیبی در نظر گرفته خواهد شد.

ویژگی 2. درخت چند پخشی مرتبط با فرمولاسیون BIP، که در بخش 3 ارائه شده است، ظاهراً بدون حلقه می باشد.

اثبات: با توجه به گراف دیسک واحد نشان داده شده در شکل 2 (الف)، در نظر بگیرید که یک حلقه (یعنی 1، 2، 3، 1) در داخل درخت چند پخشی شکل 3 (الف) وجود دارد. قیدهای (9) و (10) این تضمین را به وجود می آورند که MS حداقل دارای یک لینک خروجی، شکل 3 (ب)، می باشد. عدم تساوی (6) نیازمند آن خواهد بود که لینک (3، 1) از این پیکربندی حذف شود (شکل 3 ج). به علاوه، قیدهای (14) و (15) تضمین کننده آن هستند که گره 3 دارای هیچ لینک ورودی نمی باشد (شکل 3 د). در نهایت قید (11) اینگونه فرض می نماید که MT دقیقاً دارای یک لینک ورودی است (شکل 3 هـ).

تخصیص کانال و مسیریابی چندپخشی شبکه مش بیسیم چندکانالی چندرادیویی

5- نتایج شبیه سازی

ما چارچوب BIP خود را با استفاده از CPLEX 11 مورد بررسی قرار دادیم (برای اطلاعات بیشتر به CPLEX [6] رجوع شود). به علاوه، جهت ارزیابی عملکرد روش های پیشنهادی، چندین شبیه سازی اعمال شده است. شبیه سازی 1، جهت مشاهده تأثیر گوناگونی های تعداد کانال بر روی تداخل کلی در طراحی بین لایه ای ما، همانگونه که با LCA، MCM [31، 32] و الگوریتم ژنتیک (GA)-، آنلینگ شبیه سازی شده (SA)- و سرچ تابو [36 ـ 38] مقایسه شده است اعمال شد. در شبیه سازی 2، روش های بین لایه ای و ترتیبی پیشنهادی بر حسب بهینگی مورد ارزیابی قرار گرفتند، یعنی بر حسب تداخلات کلی در یک طرف و پیچیدگی با توجه به زمان مورد نیاز جهت حل مشکل چند پخشی و همچنین مصرف حافظه از طرف دیگر. روش ترتیبی ما با روش های LCA، MCM، GA-، SA- و TS ـ مبنا در شبیه سازی 3 مقایسه شد. شبیه سازی 4 جهت مقایسه تداخل حاصله از روش های مختلف ارائه شده است که در آن گوناگونی های تعداد رادیویی نیز در نظر گرفته می شود. کلیه شبیه سازی هایی که ما بر روی یک گراف دیسک واحد متراکم تصادفی انجام دادیم سعی در مشخص سازی تعداد گره ها و اندازه مجموعه های گیرنده چند پخشی نموده است که این تعداد به ترتیب 30 و 13 مورد تعیین شد. شبیه سازی ها به شرح ذیل تشریح شده اند.

6- تحلیل عملکرد

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

الف. نیازهای حافظه ای

نیازهای حافظه برای هر روش را می توان به عنوان تابع متغیر تولیدی در طی فرآیند اجرا تعریف نمود. تعداد کل متغیرهای ایجادی منوط به تعداد ترکیب های مختلف مجموعه های ورودی متغیرها می باشد. به طور مثال، تعداد متغیرهای تولیدی برای متغیر  برابر با  می باشد. بنابراین، تعداد متغیرهای عدد صحیح و باینری برای طراحی بین لایه ای به صورت (45) و (46) به شرح ذیل به ترتیب محاسبه می شود.

ب. پیچیدگی زمانی

هر مسئله برنامه ریزی صحیح خطی با متغیرهای کراندار را می توان به یک مسئله برنامه ریزی باینری خطی تبدیل نمود [47]. این بدان معنا می باشد که مسئله ما را می توان به برنامه ریزی صرف باینری تبدیل کرد. به علاوه، ماتریس ضریب فرمولاسیون مبتنی بر شبکه ما کاملاً به صورت تک ماژوله می باشد [48]. این ویژگی به ما در زمینه مدل سازی متغیرهای پیوسته در قالب x_ij ³ 0 به جای متغیرهای باینری کمک می نماید. در این مورد، این تضمین وجود دارد که راه حل بهینه مسئله جدید باینری می باشد و می توان آن را در قالب  حل نمود که در آن m و n تعداد قیدها و متغیرها به ترتیب می باشند [48].

7- نتیجه گیری

در این مقاله، برای اولین بار، یک چارچوب بهینه سازی ریاضیاتی جامع برای مسئله مشترک مسیریابی چند پخشی و تخصیص کانال در MCMR WMNs پیشنهاد شده است. بر خلاف روش های زیر بهینه قبلی که الزاماً بر مبنای راهکارهای ابتکاری و فوق ابتکاری بوده اند، ما یک فرمولاسیون مشخص را جهت حاصل آوردن راه حل بهینه مورد استفاده قرار داده ایم. علی الخصوص، ما دو روش مبتنی بر برنامه ریزی صحیح باینری (BIP) را برای حاصل آوردن راه حل چند پخشی بهینه پیشنهاد نموده ایم. اولین طراحی اقدام به حل دو مسئله فرعی اصلی می نماید (یعنی تخصیص کانال و ایجاد درخت) و بنابراین یک پیکربندی بهینه را حاصل می آورد. با این وجود، رویکرد بین لایه ای نسبتاً از ویژگی های بیشتری بر حسب پیچیدگی محاسباتی برخوردار بوده و بنابراین ما یک رویکرد ثانویه را پیشنهاد می نماییم که در آن دو مسئله فرعی به صورت ترتیبی حل می شوند. با این وجود، همانگونه که به وسیله نتایج شبیه سازی مشخص شده است، تداخل حاصله از نقطه نظر برخی از ویژگی های جانبی بدتر از موارد مرتبط با فرمول بندی بین لایه ای ما می باشد، اما اساس ریاضیاتی آن همچنان در مقایسه با طرح های قبلی همچنان برجسته و ممتاز می باشند. پیچیدگی زمانی و نیازهای مربوط به حافظه دو طراحی پیشنهاد شده نیز مورد بررسی قرار گرفته اند. نتایج تحلیلی نشان دهنده  آن می باشند که روش بین لایه ای به ضروریت بیشتر حافظه نیاز داشته و همچنین از پیچیدگی زمانی بیشتری در مقایسه با طراحی ترتیبی نیاز خواهد داشت.

ما همچنین به صورت مختصر پیشنهادات موجود برای مسیریابی چند پخشی در MCMR WMNs را بررسی نموده و مزیت ها و معایب آنها را خاطرنشان ساختیم. به علاوه، اصلاح طرح های ما بر حسب هر دوی مؤلفه های اتصال پذیری و ویژگی های لوپ یا حلقه ای نشان داده شده اند. نتایج ارزیابی حاصله از شبیه سازی های ما نشان دهنده آن هستند که روش های پیشنهادی دارای عملکرد بهتری در مقایسه با روش های LCA، MCM، GA-، SA-، TS ـ مبنا بر حسب تداخل می باشند. در بین روش های پیشنهادی، روش بین لایه ای ارائه دهنده راه حل بهینه برای مسئله کلی البته با توجه به پیچیدگی بالاتر آن می باشد. تداخل مرتبط با رویکرد لایه ای صرفاً به میزان اندکی بیشتر از طراحی بین لایه ای می باشد، اما به طور قابل توجهی قابل مقایسه با روش های LCA، MCM، GA-، SA- و TS ـ مبنا می باشد. 

تخصیص کانال و مسیریابی چندپخشی شبکه مش بیسیم چندکانالی چندرادیویی