تخلیه بار تحرک آگاه با قابلیت تحمل پذیری خطا در رایانش ابری موبایل (بخش دوم)

واحد دانش

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

واحد مدل کننده برنامه کاربردی

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

واحد برنامه ریز تصمیم

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

واحد اجرا

این واحد، هر یک از مولفه های برنامه کاربردی را بر اساس تصمیم اتخاذ شده توسط واحد برنامه ریز تصمیم به صورت محلی اجرا یا به سوی ابر تخلیه می کند. 

الگوریتم پیشنهادی برای حل مسئله تخلیه بار در واحد برنامه ریز تصمیم

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

ارزیابی روش پیشنهادی

به منظور ارزیابی روش پیشنهادی، آن را در ابزار MATLAB پیاده سازی کرده و با روش GACO که در بخش کارهای پیشین شرح داده شده است مقایسه نمودیم. علت انتخاب روش GACO به عنوان مبنای ارزیابی ها، در نظر گرفتن دانه دانه شدگی برنامه کاربردی بهینگی آن نسبت به سایر روش ها از لحاظ پارامترهای زمان، انرژی و قطعی حاصل از تحرک در تصمیم گیری تخلیه بار می باشد. 
به علاوه، با توجه به هدف روش GACO در اتخاذ تصمیم گیری تخلیه بار با لحاظ تحرک کاربر به منظور بهینه سازی زمان و انرژی مصرفی اجرای برنامه کاربردی، این روش نسبت به سایر روش های اخیر نزدیک ترین رویکرد را به روش پیشنهادی دارد. 
با توجه به استفاده از الگوریتم ژنتیك در روش پیشنهادی، ارزیابی های صورت گرفته در دو دسته انجام شده است. دسته اول با بررسی تأثیر پارامترهای الگوریتم ژنتیك (تعداد تكرار و اندازه جمعیت) بر برازندگی دست یافته توسط دو روش، به انتخاب بهترین مقدار برای این پارامترها می پردازد. 
دسته دوم با استفاده از پارامترهای انتخابی الگوریتم ژنتیك به بررسی عملکرد روش پیشنهادی در مقایسه با روش GACO تحت تاثیر ویژگی های مختلف برنامه کاربردی، تحرک کاربر و شرایط شبکه می پردازد. به این منظور، تاثیر پارامترهایی از جمله تعداد مولفه ها، اندازه داده ورودی و تعداد دستورات برنامه كاربردی، مدت زمان توقف كاربر در هر شبكه و پهنای باند مورد ارزیابی قرار گرفته است. 
-دسته اول ارزیابی ها: انتخاب پارامترهای الگوریتم ژنتیک
باتوجه به تاثیر پارامترهای الگوریتم ژنتیک بر عملکرد دو روش GACO و MAFO، در دسته اول ارزیابی ها به بررسی و انتخاب بهترین مقادیر برای این پارامترها پرداخته می شود. 
به طور کلی با افزایش تعداد جمعیت اولیه و تعداد تكرار الگوریتم ژنتیك، احتمال دستیابی به نتیجه ای نزدیك تر به بهینه بیشتر می شود اما به موازات آن پیچیدگی و در نتیجه زمان تصمیم گیری افزایش می یابد. بنابراین مقادیر بهینه این دو پارامتر مقادیری هستند كه در آنها برازندگی الگوریتم نسبت به مقادیر بالاتر از آن به اندازه کافی مناسب باشد. 
از آن جا که ارزیابی تاثیر تعداد تکرار الگوریتم ژنتیک بر برازندگی از لحاظ انرژی مصرفی نتایج مشابهی را منعکس می کند، از ارائه آن در ادامه خودداری شده است. لذا با توجه به این که تعداد تکرار بیش از 100 بار تاثیر قابل توجهی در مقدار برازندگی ایجاد نکرده است، این مقدار به عنوان مقدار بهینه تکرار الگوریتم ژنتیک در نظر گرفته می شود. 

دسته دوم ارزیابی ها: بررسی عملکرد روش پیشنهادی

هدف از این دسته از ارزیابی ها، بررسی عملكرد روش پیشنهادی در مقایسه با روش GACO تحت تاثیر ویژگی های مختلف برنامه کاربردی، تحرك كاربر و شرایط شبكه می باشد.
به این منظور در قسمت های زیر به ترتیب تأثیر قابلیت تحمل پذیری خطا با توجه به احتمال قطعی هنگام تغییر شبكه، تعداد مؤلفه ها، اندازه داده ورودی، تعداد دستورات برنامه كاربردی و مدت زمان توقف كاربر در هر شبكه بر زمان و انرژی مصرفی مورد ارزیابی قرار گرفته است. در هر یك از این ارزیابی ها، به منظور حفظ استقلال نتایج نسبت به سایر پارامترهای ورودی مرتبط با برنامه كاربردی، تحرك كاربر و شرایط شبكه، مقدار این پارامترها به صورت تصادفی در بازه تعریف شده در نظر گرفته شده است. با توجه به نتایج قسمت قبل، اندازه جمعیت اولیه و تعداد تكرار الگوریتم ژنتیك در همه ارزیابی های دسته دوم به ترتیب برابر با 30 و 100 در نظر گرفته شده است.

تأثیر قابلیت تحمل پذیری خطا با توجه به احتمال قطعی

در این قسمت برای نشان دادن تأثیر استفاده از قابلیت تحمل پذیری خطا در روش پیشنهادی، نتایج زمان و انرژی مصرفی اجرای آن را در دو حالت وجود و عدم وجود قابلیت تحمل پذیری خطا در احتمال قطعی های مختلف نمایش می دهیم.
با افزایش احتمال قطعی، هزینه ناشی از اجرای برنامه در صورت عدم استفاده از قابلیت تحمل پذیری خطا به صورت نمایی افزایش می یابد. علت این امر از سرگرفتن برنامه از ابتدای آن در صورت عدم استفاده از قابلیت تحمل پذیری خطا می باشد و این در حالی است كه در صورت استفاده از این قابلیت، اجرای برنامه از آخرین نقطه قبل از وقوع قطعی ادامه یافته كه این امر منجر به كاهش زمان و انرژی مصرفی اجرای برنامه می شود. 
تفاوت استفاده و عدم استفاده از قابلیت تحمل پذیری خطا با افزایش احتمال قطعی افزایش می یابد و در احتمال قطعی های پایین با توجه به خطای تصمیم گیری (فرض احتمال قطعی صددرصد در تصمیم گیری و مواجهه با احتمال قطعی پایین در واقعیت) این تفاوت قابل توجه نیست. 

ارزیابی تاثیر مولفه های برنامه کاربردی

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

ارزیابی تاثیر اندازه داده ورودی

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

تخلیه بار تحرک آگاه با قابلیت تحمل پذیری خطا در رایانش ابری موبایل
https://www.sid.ir/fa/journal/ViewPaper.aspx?ID=312962