دل مصرف انرژی EDM[68] میباشد. در این مقاله، پنل خورشیدی بعنوان برداشتگر انرژی خورشیدی برای مدل EHM، درنظر گرفته شدهاست. ESM نیز همچون بافر انرژی، عمل کرده و خواهان عملیات پیوسته حتی در زمان کمبود انرژی است. ابرخازن[69] و یا باطریهایی با قابلیت شارژ مجدد، میتوانند نمونههای خوبی برای ESM باشند. درنهایت سیستم تعبیهشده که برنامههای کاربردی بیدرنگ را اجرا میکند نیز بعنوان EDM ، معرفی شدهاست.
در این سیستم انرژی مورد نیاز برای سیستم تعبیهشده، میتواند هم از ذخیرهساز انرژی، و هم بطور مستقیم، از برداشتگر انرژی، تأمین شود. براین اساس سه حالت برای سیستم، قابل بیان است:
انرژی مورد نیاز EDM ، بیشتر از انرژی حاصل از EHM ، باشد: در اینصورت سیستم تعبیه شده انرژی مورد نیاز برای اجرای وظایف و عملیاتش را هم از محیط و برداشتگر انرژی، و هم از ذخیرهساز انرژی، بدست میآورد. درنتیجه با عمل دشارژ ذخیره ساز انرژی، مواجه هستیم.
انرژی مورد نیاز EDM ، برابر با انرژی حاصل از EHM ، باشد: در این حالت، ظرفیت ذخیرهساز انرژی بدون تغییر میماند و انرژی لازم برای سیستم، مستقیما پس از دریافت از محیط و تبدیل به انرژی الکتریکی توسط مبدل انرژی، در اختیار پردازنده برای اجرای وظایف قرار میگیرد.
انرژی مورد نیاز EDM ، کمتر از انرژی حاصل از EHM ، باشد: در این حالت نیز، سیستم، انرژی مورد نیازش را از محیط و برداشتگر انرژی بصورت مستقیم دریافت میکند، اما انرژی مازاد بر نیاز سیستم، در ذخیرهساز انرژی، ذخیره میشود ( عمل شارژ ذخیرهساز انرژی).
مدل برداشت انرژی
انرژی محیطی میتواند شامل انواع انرژی موجود در محیط پیرامون سیستم تعبیهشده، باشد و سیستمهای تعبیهشده مبتنی بر برداشت انرژی، بسته به محیط اجرایی خود میتوانند از انواع انرژهای موجود در محیط که تجدیدپذیر نیز میباشند، استفاده کنند. موجودیت انرژی فراهم شده توسط EHM ، ثابت نبوده و منحصرا توسط منبع برداشت انرژی، هم مشخص نمیشود. بعنوان مثال در یک پنل خورشیدی علاوه بر شدت تابش نور خورشید، بارکاری ولتاژی که وسیله برداشت انرژی، در آن کار میکند هم میتواند روی توان خروجی آن تأثیرگذار باشد. پنل خورشیدی یک منبع جریان، با ولتاژ محدود شده میباشد. که ولتاژ خروجی آن توسط میزان بار[70] موجود در آن مشخص میشود. فقط زمانیکه این پنل، در یک ولتاژ خاص کار میکند، میتواند توان خروجی بیشینه را به سیستم القا کند. که این نقطه خاص ولتاژ، همان نقطه MPP ، میباشد. بنابراین پیدا کردن بار مناسبی که توسط آن، پنل خورشیدی (بطور کلی هر وسیله برداشتگر انرژی) در ولتاژ خاص PHmax کار کند و درنتیجه، بیشترین توان را در خروجی آن داشته باشیم، بسیار حائز اهمیت است. توان خروجی بیشینه PHmax، متغیری وابسته به زمان است و برای شدت تابش نور خورشید در زمانهای مختلف، متفاوت خواهد بود بنابراین داریم PHmax(t) که برای سادگی در معادلات و الگوریتم، همان PHmax ، بیان شده است و مقدار آن میتواند توسط بررسی نمودار تغییراتش و هم از طریق پیشبینی بدان رسید.
اگر وسیله برداشتگر انرژی (پنل خورشیدی در این مقاله) همواره در نقطه MPP ، کار کند در اینصورت میزان انرژی برداشت شده در فاصله [t1 , t2] از رابطه زیر محاسبه میشود:

دودیتهای زمانی و انرژی.
ایراد اساسی که به این روش وارد است، این است که الگوریتم، همواره در تلاش است که بارکاری وسیله برداشتگر انرژی را طوری تنظیم کند که برداشتگر انرژی در نقطه توان بیشینه MPP ، به برداشت بیشترین انرژی ممکن از محیط در هر زمانی بپردازد، این مسئله در زمان پر بودن باطری و عدم وجود وظیفهای برای اجرا، سبب سرریز باطری و به هدر رفتن انرژی برداشت شده میشود، حتی در صورت وجود وظیفهای برای اجرا و افزایش سرعت اجرای وظیفه جاری باز هم امکان وقوع این مسئله وجود دارد. بنابراین برداشت انرژی در هر واحد زمان با بیشترین توان، با توجه به هزینهی تبدیل انرژی محیطی به انرژی الکتریکی و پارهای عوامل دیگر، عمل مناسبی برای سیستم تعبیهشده محسوب نمیشود.
الگوریتم در زمانیکه انرژی محیطی، بیشتر از انرژی مورد نیاز پردازنده برای اجرای وظیفه جاری است، برای جلوگیری از رجوع به باطری و ذخیره انرژی مازاد در آن، با هدف کاهش سربار انرژی حاصل از شارژ باطری، سرعت اجرای وظیفه جاری را افزایش میدهد. بعبارتی پردازنده به بالاترین سطح فرکانسی خود برای مصرفی انرژی بیشتر، سوئیچ میکند. درست است که این مسئله، سربار انرژی را کاهش داده و سبب ایجاد زمان آرامش برای اجرای وظایف بعدی میشود، اما باتوجه به متغیر بودن انرژی محیطی، حالتی قابل تصور است که بعد از اجرای وظیفه جاری در بالاترین سطح توان و مصرف انرژی زیاد، وظیفهای با سررسید کم و انرژی مورد نیاز بیشتر از انرژی موجود در باطری و انرژی برداشت شده، وارد سیستم شود. حال اگر حتی با وجود زمان آرامش ایجاد شده، سیستم قادر به برداشت انرژی مورد نیاز وظیفه، از محیط، قبل از سررسید آن نباشد بعبارتی انرژی موجود در محیط پیرامون، برای اجرای وظیفه، کافی نباشد، وظیفه جاری از صف آماده حذف میشود، که این مسئله در صورت تکرار و وجود وظایف بیشتری با این شرایط، میتواند نرخ خطای سررسید را افزایش دهد. و سیستم برای کاهش انرژی حاصل از سربار، موجب حذف شدن وظیفه یا وظایفی شده است. شاید یک راهکار مناسب، تنظیم درست نرخ برداشت انرژی از محیط باشد نه برداشت بیشینه در هر زمان.
در کنار موارد گفته شده الگوریتم LM-APM ، دارای مزایایی است که نمیتوان از آنها چشمپوشی کرد که عبارتند از:
استفاده از سیستمی با قابلیت استفاده مستقیم از انرژی برداشت شده از محیط که سبب کاهش سربار انرژی حاصل از شارژ/دشارژ باطری شده و این امر سبب افزایش طول عمر باطری و درنهایت سبب افزایش طول عمر سیستم تعبیهشده و رعایت پیوستگی در اجرای عملیات آن میشود.
استفاده از باطری واقعی بجای باطری ایدهآل و تطابق الگوریتم با شرایط آن.
تنظیم بارکاری وسیله برداشتگر انرژی در نقطه توان بیشینه که سبب افزایش موجودیت انرژی میشود البته این قسمت در برخی مواقع سودمند میباشد که پیش از این توضیح داده شدهاست.
انجام زمانبندی برای تمامی وظایف و بررسی تأثیر زمانبندی یک وظیفه برروی سایر وظایفی که در ادامه وارد صف آماده میشوند.
کاهش سربار انرژی در باطری که سبب کارایی انرژی مصرفی کل سیستم میشود.
3-4-5 روش زمانبندی HA-DVFS[72]
در این قسمت الگوریتمی را معرفی میکنیم که نواقص بسیاری از الگوریتمها و روشهای معرفی شده در بخشهای قبل را برطرف کردهاست و اساس کار الگوریتم زمانبندی پیشنهاد شده در این گزارش نیز میباشد.
اهداف کلی این الگوریتم که در]19[، معرفی شده است عبارتند از :
زمانبندی تمامی وظایف در پایینترین سرعت ممکن و تخصیص بارکاری تاحد امکان مساوی (در تمام زمانها) به پردازنده.
جلوگیری از اتلاف انرژی برداشت شده، توسط ممانعت از سرریز انرژی در ذخیرهساز انرژی.
زمانبندی براساس تخصیص مساوی بارکاری پردازنده نه تنها، تأخیر و سربار حاصل از سوئیچ در بین سطوح ولتاژ/فرکانس پردازنده را کاهش میدهد، بلکه باعث افزایش بهرهوری، از تکنیکهایی همچون انتخاب پویای ولتاژ/فرکانس درجهت رسیدن به کمترین انرژی مصرفی سیستم نیز میشود]18[. در این حین، استفاده از انرژی سرریز شده در جهت کارایی بهتر سیستم، نیز یکی دیگر از نکات مثبتی است که این الگوریتم در جهت رسیدن بدان تلاش کردهاست. مدل برداشت انرژی(EHM) و سیستم تعبیهشده(EDM)، بکار رفته در این مقاله، کاملا همان سیستم معرفی شده در روش LM-APM، میباشد که در بخش قبل بطور کامل بیان شد. ذخیرهساز انرژی نیز در این روش، باطری واقعی با ضریب سودمندی شارژ/دشارژ λ ، میباشد.
توجه شود که سایر پارامترها و روابط برای مدل باطری در این مقاله، همان روابط مدل ESM معرفی شده در الگوریتم LM-APM، میباشد که در اینجا از تکرار مجدد خودداری میکنیم.
بطور خاص نویسندگان در این الگوریتم بدنبال موارد زیر میباشند:
جداسازی محدودیتهای زمانی و انرژی با هدف مدیریت توان بهتر و کاهش پیچیدگیهای الگوریتم زمانبندی.

2. Update ftm= Stm+ Wm/S(SIm,new)

2. compute transferred slack Slacktf

2. distribute Slacktf among all task

2. end

2. while(Slacktf > 0)

2. fork=m+1 :M do

2. Stk= max (ak, ftk-1)

2. if(Stk + Wk/S(SIk-1) < iftk && the slowdown factor for task

with lower priority is valid) Then

11. SIk= SIk-1

11. end if

11. ftk= Stk+ Wk/S(SIk)

11. Upadate Slacktf

شکل 3-5 : شبه کد الگوریتم بهرهوری از انرژی سرریز شده ]19[
شکل 7شکل 3-5 : شبه کد الگوریتم بهره وری از انرژی سرریز شده
نتایج الگوریتم HA-DVFS
در این الگوریتم تکنیک مدیریت توان جدیدی برای سیستمهای تعبیهشده بیدرنگ مبتنی بر برداشتگر انرژی ارائه شد. که ، درصدد اجرای بیدرنگ وظایف با هدف کاهش انرژی مصرفی و کاهش نرخ خطای سررسید وظایف و بهرهوری مناسب از انرژی محیطی میباشد. این روش درمقایسه با الگوریتمهای LSA و EA-DVFS، دارای نرخ خطای سررسید کمتر و همینطور ظرفیت ذخیرهساز انرژی کمتری میباشد. همچنین این روش با استفاده از تکنیک انتخاب پویای ولتاژ و فرکانس در جهت ایجاد زمان آرامش بیشتر برای اجرای وظایف در فرکانس پایینتر و همینطور حداقل سازی اتلاف انرژی در زمان سرریز، توانسته کارایی سیستم تعبیهشده را بهبود دهد. مزایای این روش عبارتنداز:
پیچیدگی محاسبات کمتر
نرخ خطای سررسید کمتر
ظرفیت ذخیره ساز انرژی کمتر
استفاده از باطری واقعی و بررسی تأثیر ضریب سودمندی شارژ/دشارژ برروی انرژی ذخیره شده.
معایای این روش عبارتنداز:
الگوریتم کلی شامل چند مرحله مجزا است و این باعث افزایش مرتبه اجرای الگوریتم زمانبندی شدهاست و این مسئله، برای سیستمهای تعبیهشده بیدرنگ، مناسب نمیباشد.
انتخاب پایینترین فرکانس برای اجرای وظیفه، باعث طولانی شدن زمان اجرای آن وظیفه میشود و این امر احتمال نقض سررسید در مابقی وظایف را افزایش میدهد.
با وجود به کار بردن راهکاری برای کاهش سرریز در باطری، همچنان احتمال سرریز زیاد است چراکه الگوریتم، در تمامی مراحل، سعی در کاهش سرعت اجرای وظیفه دارد.
تخصیص بخش زیادی و یا همه انرژی موجود به اجرای وظیفه زمانبندی شده در زمان وقوع سرریز، احتمال نقض سررسید مابقی وظایف موجود را بدلیل عدم وجود انرژی کافی، افزایش میدهد و ازطرفی درصورتیکه انرژی کمی برای اجرای وظیفه جاری اختصاص یابد این امر موجب میشود، پردازنده فرکانس پایینی برای اجرای آن انتخاب و درنتیجه سرعت اجرا کاهش مییابد و این سبب طولانی شدن زمان اجرای وظیفه میشود که این هم میتواند موجب نقض سررسید مابقی وظایف شود. بعبارتی بررسی جداگانه محدودیتهای انرژی و زمانی، میتواند مشکلاتی را برای اجرای وظایف ایجاد کند در حقیقت محدودیت انرژی و زمانی بایکدیگر در تقابلند و از اینرو نمیتوانیم بصورت جداگانه به بررسی آنها بپردازیم.
در این الگوریتم هر زمان خطایی چه از نظر انرژی و چه از دید زمانی برای وظیفه جاری و یا سایر وظایف، رخ میدهد الگوریتم مجددا زمانبندی را برای تمامی وظایف باقیمانده در صف آماده انجام میدهد و این درصورتیکه تعداد وظایف، افزایش یابد برای سیستم تعبیهشده مشکلساز خواهد بود.
در ادامه معرفی کارهای انجام شده در جهت زمانبندی سیستمهای تعبیهشده بیدرنگ مبتنی بر برداشتگر انرژی بعنوان آخرین نمونه، الگوریتمی را معرفی میکنیم که به بررسی هم زمان محدودیتهای انرژی و زمانی پرداختهاست و توانسته زمان اجرای الگوریتم تا حد قابل قبولی کاهش دهد.
3-4-6 الگوریتم انتخاب فرکانس باتوجه به وضعیت سیستم[76]
بدنبال الگوریتمهای معرفی شده در بخشهای قبلی، نویسندگان، در ]21[ ، الگوریتم زمانبندیای ارائه کردهاند که بیشتر مبتنی بر روشی برای انتخاب آگاهانه فرکانس اجرایی وظایف، با هدف کاهش پیچیدگی روشهای قبلی و ارائه روشی سادهتر میباشد. همچنین این روش، الگوریتمی پویا و براساس بررسی همزمان موجودیت انرژی و حالت بهرهوری سیستم[77] نیز میباشد. طرح معرفی شده، ابتدا مبتنی بر دورنمایی از بهرهوری سیستم و میزان انرژی برداشت شده از محیط، وضعیت و مشخصههای سیستم هدف را مشخص و تعیین میکند. سپس بخشی از انرژی موجود را به گروهی از وظایف موجود در صف آماده، براساس انرژی برداشت شده از محیط توسط آرایههای فتوولتائیک[78] و مقدار بهرهوری سیستم، اختصاص میدهد. درنهایت براساس این انرژی تخصیص دادهشده به گروهی از وظایف، فرکانس اجرایی برای هر یک از وظایف، را انتخاب میکند. و در آخر، این فرکانس درجهت افزایش کارایی سیستم، بهبود داده میشود. هدف نویسندگان از این الگوریتم، کاهش پیچیدگیهای روشهای قبلی است. همچنین مرتبه زمانی این روش در مقایسه با روشهای قبل خصوصا روش HA-DVFS، کمتر بوده و الگوریتم سریعتر به جواب همگرا میشود. سیستم برداشتگر انرژی که در این روش، نویسندگان، الگوریتم خود را برمبنای آن ارائه دادهاند، همان سیستم معرفیشده در بخش قبلی است و برای ذخیرهساز انرژی هم از باطری با ظرفیت محدود استفاده کرده و از تأثیر ضریب سودمندی شارژ و دشارژ در زمان رجوع به باطری، چشمپوشی شده است.

ه ]24[ بحث زمانبندی برای سیستمهای تعبیهشده مبتنی بر فریم را بیان کرده است که قادر به اجرای وظایف بیدرنگ سخت در سررسید متناظرشان میباشد. در این روش، زمانی پردازنده عملیاتش را شروع میکند که واحد ذخیرهساز انرژی کاملا شارژ شده باشد. دراین مورد دوره تناوب تمامی وظایف، یکسان و سررسید هریک از آنها نیز برابر با مقدار دوره تناوب در نظر گرفته شده است. درنتیجه بیان میشود که ترتیب اجرای وظایف درون یک فریم، چه در حالتیکه وظایف قابل زمانبندی باشند و یا قابل زمانبندی نباشند، بسیار بحرانی و حائز اهمیت نیست. بعلاوه فرض میشود توان برداشت انرژی، ثابت بوده و وظایف در یک نرخ ثابتی از انرژی و توان اجرا میشوند. ایده اصلی این روش اضافه کردن یک زمان بیکاری کوچک به سیستم برای برداشت انرژی و شارژ باطری و در مقابل داشتن حداقل زمان زمانبندی است یعنی وظایفی که همگی دارای مشخصههای انرژی و سررسید یکسانی هستند با وجود انرژی کافی در ذخیرهساز انرژی قادر خواهند بود در کمترین زمان قبل از سررسیدشان اجرا شوند. واضح است که یکسان درنظر گرفتن مشخصههای وظایف و همینطور نرخ ثابت انرژی و توان در دنیای واقعی فرض مناسبی نیست.
زمانبندی وظایف تناوبی میتواند براساس اولویت ثابت[84] و ایستا و یا همانند روش EDF، بصورت پویا، انجام پذیرد. در ]25[ روشی برای زمانبندی وظایف انحصاری با اولویت ثابت که این اولویت در زمان اجرا به هر وظیفه اختصاص داده میشود ارائه شده است (EHFP4[85]) . این روش، الگوریتمی برخط است که تصمیمات زمانبندی، بدون هیچگونه پیشبینی از موجودیت انرژی در زمانهای آتی و در زمان اجرا ، گرفته میشود. براساس چهار حالت الگوریتم ابتکاری بیان شده است :
هر زمان که باطری خالی میباشد بعبارتی E(t)=Emin، پردازنده برای یک مدت زمان دلخواهی به حالت بیکار میرود.
بصورت پویا سطح انرژی ذخیره شده در باطری دائما بررسی میشود. هدف از این قسمت کاهش احتمال جایگزینی باطری میباشد.
در این قسمت بیان میشود هرچه ظرفیت باطری بیشتر باشد برای سیستم مناسبتر میباشد در اینحالت بحث محاسبه بیشترین زمانیکه سیستم در صورت عدم انرژی کافی باید متوقف شود در حالتیکه خطای سررسید رخ ندهد بسیار حائز اهمیت است که این زمان آرامش بصورت برخط توسط زمانبند در زمان اجرا تعیین میشود.
در این قسمت الگوریتم به بررسی سرریز در زمان بیکار بودن سیستم میپردازد بنابراین پردازنده، تنها زمانی به حالت بیکار میرود که زمان آرامش و سطح انرژی باطری، بیشینه نباشد. بر این اساس برای موجودیت انرژی باطری یک حد آستانهای درنظر گرفته میشود و زمانیکه سطح انرژی باطری به این مقدار آستانه رسید، پردازنده به حالت بیکار خود میرود.
در آخر بیان میشود که توسط زمانبندی تنها بصورت برخط و با تصمیمات در زمان اجرا و بدون داشتن هیچگونه پیشبینی از برداشت انرژی در آینده، نمیتوان به الگوریتم زمانبندی بهینهای رسید.
الگوریتم زمانبندی که در ]26[ معرفی شده است، برروی یک پردازنده با یک سطح ولتاژ و فرکانس و یک سیستم برداشتگر انرژی و همینطور باطری ایدهآل با قابلیت شارژ مجدد، وظایفی را که مشخصاتی همچون زمان ورود، سررسید متناظر، بدترین حالت زمان اجرا و بدترین حالت انرژی مصرفی را دارند را زمانبندی میکند. در این مقاله بیان میشود که لزوما مشخصههای زمان اجرا و انرژی مصرفی وظایف با یکدیگر متناسب نیستند. همچنین فرض شده است که توان مصرفی آنی یک وظیفه از توان ورودی واحد برداشتگر انرژی، کمتر نیست بعبارتی وظایف میتوانند سبب تهی شدن کامل باطری شوند. در این روش، تضمین اینکه تمامی سررسیدها در یک سیستم برداشتگر انرژی، برآورده شوند، یکی از مهمترین مسائل پیش رو است. الگوریتم ED-H، قبل از اجرای وظیفه جاری، به بررسی موجودیت انرژی برای وظایفی که در آینده وارد سیستم میشوند، میپردازد و درصورت کافی بودن این انرژی، وظیفه جاری اجرا و درغیر اینصورت تا زمان برداشت انرژی کافی از محیط، به اجرای وظیفه جاری تأخیر میدهد. بعبارتی این الگوریتم براساس دانشی در مورد وظیفه جاری و و وظایفی که در آینده وارد سیستم خواهند شد، تصمیمات زمانبندی را اتخاذ میکند. همچنین در این روش قبل از اجرا، محدودیت زمانی و انرژی وظایف و نرخ انرژی قابل ذخیره، نیز بررسی میشود و درصورت ناکافی بودن هر یک از موارد گفته شده، پردازنده به حالت بیکار میرود. واضح است که این روش نرخ خطای سررسید را در مقایسه با سایر روشهای دیگر افزایش میدهد. همچنین در این روش ظرفیت باطری نیز بیشتر خواهد شد چراکه در سیستم پیشنهادی، پردازنده قادر نخواهد بود بطور مستقیم انرژی مورد نیاز خود را از محیط دریافت کند، بلکه برای تأمین انرژی لزوما باید به باطری مراجعه کند. بنابراین باتوجه به اینکه شرط اجرای وظیفه جاری، وجود انرژی کافی برای اجرای سایر وظایف آتی سیستم میباشد، دراینصورت ظرفیت باطری باید به اندازه انرژی مورد نیاز تمامی وظایف سیستم باشد که این در عمل امکانپذیر نخواهد بود. بعلاوه درصورت عدم انرژی کافی، پردازنده به حالت بیکار میرود که این خود میتواند تا زمان برداشت انرژی کافی توسط برداشتگر انرژی، سبب نقض سررسید وظیفه جاری و درنهایت حذف آن از سیستم شود. نکته قابل توجهی که در این مقاله بدان پرداخته شده است بررسی جداگانه بدترین حالت زمان اجرا و بدترین حالت انرژی مصرفی، بعنوان مشخصههای اصلی یک وظیفه میباشد.
3-5 نتیجهگیری
نسل جدید سیستمهای تعبیهشده، برای تأمی
ن انرژی مورد نیاز برای اجرای عملیات خود، قادر به دریافت انرژی از محیط پیرامون میباشند. بدین منظور، سیستم، نیازمند واحد برداشت انرژی و همینطور واحد ذخیرهساز انرژی با قابلیت شارژ مجدد میباشد. بر این اساس و باتوجه به اینکه مقدار این انرژی، در زمان، متغیر میباشد، بحث مدیریت توان و مدیریت انرژی در چنین سیستمهایی بسیار حائز اهمیت است. از اینرو وجود یک الگوریتم زمانبندی مناسب که بتواند تصمیمات دقیقی درمورد زمان درست شروع فعالیت سیستم و همینطور زمان مناسب بیکاری و آرامش آن را طوریکه از اتلاف انرژی برداشت شده نیز جلوگیری کند، اتخاذ کند و درکنار این تصمیمات زمانبندی مدیریت انرژی مناسبی نیز داشته باشد در سیستمهای تعبیهشده مبتنی بر برداشتگر انرژی بسیار مورد توجه قرار دارد. در این حوزه، مطالعات و تحقیقات گستردهای انجام شده است که در فصلی که گذشت به معرفی پارهای از الگوریتمها و روشهای انجام شده پرداختیم. با وجود کارهایی که در این زمینه انجام شده است هنوز وجود الگوریتمی که بتواند درکنار زمانبندی مناسب وظایف، میزان انرژی مصرفی سیستم و همینطور تعداد مراجعات به باطری را برای افزایش طول عمر بیشتر سیستم، کاهش دهد، بسیار لازم و ضروری است. و این مهم با توجه به رشد روز افزون سیستمهای تعبیهشده در تمامی زوایای زندگی بشر، از اهمیت دو چندانی برخوردار میشود. براین اساس در فصل آینده، سیستم تعبیهشده و همینطور الگوریتم زمانبندی متناظر با آن را با هدف کاهش مراجعات به باطری و بهبود انرژی مصرفی در کنار اجرای بیدرنگ وظایف تناوبی و غیر تناوبی، معرفی میکنیم.
فصل چهارم
فصل چهارم : الگوریتم پیشنهادی
4-1 مقدمه
تکنیک برداشت انرژی از محیط پیرامون، مزایای زیادی برای سیستمهای تعبیهشده امروزه، ازجمله پیوستگی در اجرای عملیات سیستم و افزایش طول عمر آن، دارد. اما رسیدن به تمامی این مزایا درکنار یک الگوریتم زمانبندی مناسب که بتواند تصمیمات درست و دقیقی درمورد زمان اجرای وظایف، سرعت مناسب پردازنده و همینطور زمان مناسب، برای رجوع به باطری برای دریافت انرژی، اتخاذ نماید، امکانپذیر است. در این فصل بر این اساس الگوریتم پیشنهادی خود را با هدف کاهش معایب روشهای قبلی ارائه میدهیم.
روش پیشنهادی در این پروژه از دو دیدگاه میباشد :
ذخیرهساز انرژی : یک نکته کلیدی در کارایی سیستمهای تعبیهشده مبتنی بر برداشتگر انرژی، کارایی ذخیرهساز انرژی است]27[. از اینرو در این بخش، روشی برای ذخیره کردن انرژی برداشت شده از محیط، ارائه میشود، که در کنار رجوع کمتر به باطری غیر آیدهآل و در نتیجه کاهش اثرات منفی حاصل از ضریب سودمندی شارژ و دشارژ باطری، بتوانیم وقوع سرریز را نیز در سیستم، کاهش دهیم.
الگوریتم زمانبندی بیدرنگ : مبتنی بر ذخیرهساز انرژی بخش اول، در این بخش با هدف کاهش نرخ خطای سررسید و بهبود انرژی مصرفی وظایف و همینطور کاهش اتلاف انرژی حاصل از سرریز، الگوریتم زمانبندی خود را ارائه میدهیم.
در ادامه با جزئیات بیشتری دو بخش نام برده را بیان خواهیم کرد.
4-2 ذخیرهساز انرژی
در کنار مراجعی که تنها به بحث زمانبندی وظایف در یک سیستم تعبیه شده مبتنی بر برداشتگر انرژی میپردازند، مراجعی نیز هستند که تنها برروی ذخیرهساز انرژی، تمرکز داشته و تنها سعی در یافتن روشی برای بهبود عملیات ذخیره و برداشت انرژی از ذخیرهساز انرژی و افزایش کارایی عملکرد آن را دارند. در این میان، از دید محققان و طراحان، باطری، دارای معایبی است که ادامه استفاده از آن، در سیستمهای تعبیهشده امروزه، نیازمند تمهیداتی در روند طراحی و اصلاح عملکرد آن میباشد.
یکی از راهکارهای موجود در برابر معایب سیستمهای مبتنی بر باطری و افزایش طول عمر مفید آنها، استفاده از تکنیک برداشت انرژی محیطی میباشد اما در اکثر این سیستمها نیز انرژی مازاد در باطری ذخیره میشود، و در صورتیکه اجرای وظایف، انرژی بیشتری از مقدار انرژی برداشت شده بخواهد، پردازنده، برای تأمین انرژی مورد نیاز خود به ناچار، از انرژی ذخیره شده در باطری استفاده میکند. درنتیجه باز هم، عملیات شارژ و دشارژ باطری میتواند، بر روی سیستم، اثرات منفی بسیاری را داشته باشد. خصوصا با توجه به اینکه انرژی محیطی به شدت در زمانهای گوناگون، متغیر میباشد، این مسئله در زمانهای کمبود انرژی محیطی، بیشتر قابل مشاهده است. درنتیجه نیازمند تغییرات اساسی در واحد ذخیرهساز انرژی هستیم تا بتوانیم تا حد ممکن از رجوع به باطری جلوگیری کنیم و یا حتی بتوانیم جایگزین مناسبی برای آن پیدا کنیم. با کاهش مراجعه به باطری میتوانیم تأثیرات ضریب سودمندی را بر روی سیستم، کاهش داده، بعلاوه این امر موجب به حداقل رساندن ظرفیت باطری، شده و در نتیجه هزینه سیستم نیز کاهش مییابد]27[.
در این حوزه برخی محققان برای بهبود شرایط توصیف شده، باتوجه به تکنیکهای جدیدی که در طراحی ابرخازنها[86] ارائه شده است، از ترکیب ابرخازن و باطری بعنوان ذخیرهساز انرژی استفاده کردهاند. براین اساس در ادامه به معرفی مزایا و معایب ابرخازن در قیاس با باطری با قابلیت شارژ مجدد میپردازیم. لازم به ذکر است که ابرخازن که به آن خازن دو لایه نیز میگویند در مقدار ظرفیت با خازن معمولی متفاوت است و ظرفیت آنها نسبت به خازن معمولی بسیار بیشتر میباشد]28[.
4-2-1 مزایای ابرخازن در برابر باطری با قابلیت شارژ مجدد
از دید پارامترهای
الکتریکی:
سرعت بسیار بالا در عملیات شارژ و دشارژ: ابرخازنها میتوانند در مدت چند میلی ثانیه تا چند دقیقه تهی شده و در مدت چند ثانیه تا چند دقیقه شارژ شوند.

>
در این الگوریتم، بصورت همزمان محدودیتهای زمانی و انرژی را بررسی میکنیم، چراکه در بررسی جداگانه علاوه بر زمان اجرای بالاتر الگوریتم، برخی نواقص نیز بوجود میآید. بعنوان مثال اگر قبل از بررسی موجودیت انرژی برای اجرای یک وظیفه، فقط با درنظر گرفتن مهلت زمانی آن، زمان شروع و خاتمه آن محاسبه شود، ممکن است در این زمان، انرژی کافی برای اجرای وظیفه موجود نباشد، درنتیجه پردازنده قادر به اجرای آن نخواهد بود و در حالت دیگر اگر قبل از بررسی مهلت زمانی اجرای وظیفه، اجرای آن را تا زمان کافی بودن انرژی، به تأخیر بیاندازیم، ممکن است این تأخیر، سبب نقض سررسید وظیفه شود. بنابراین قبل از اجرای یک وظیفه، بررسی چند مسئله حائز اهمیت است:
مهلت زمانی اجرای وظیفه
انرژی مورد نیاز برای اجرای وظیفه
موجودیت انرژی (در محیط و در واحد ذخیرهسازی)
انتخاب فرکانس مناسب پردازنده برای اجرای وظیفه
یک الگوریتم مناسب، باید قبل از خاتمه زمان سررسید مطلق یک وظیفه (Dm) که از جمع زمان ورود (am) و سررسید متناظر وظیفه(dm)، حاصل میشود، وظیفه جاری را اجرا و خاتمه دهد. بعنوان مثال اگر وظیفهای با زمان سررسید 2، در زمان 3 وارد سیستم شده باشد، پردازنده باید تا قبل از زمان 5 اجرای آن را به اتمام برساند. اطلاعات مهلت زمانی و انرژی مورد نیاز برای اجرای یک وظیفه از مشخصههای یک وظیفه، قابل استخراج است. قبل از بررسی موجودیت انرژی، الگوریتم، در ابتدا پایینترین فرکانس ممکن برای اجرای یک وظیفه را محاسبه میکند. درصورتیکه همانند مراجع ]10[، ]11[، ]17[، ]18[ و ]19[، فاکتور کاهش سرعت Sn = fn / fmax را به ازای هر وظیفه، تعریف کنیم و درصورتیکه wn، بدترین حالت زمان اجرای وظیفه متناظر باشد، از رابطه ، میتوان کمترین فرکانس ممکن برای اجرای وظیفه τm را محاسبه کرد. در این رابطه نیز منظور از ، سررسید متناظر است نه سررسید مطلق. بنابراین خواهیم داشت:
(45)
بعد از تعیین flow ، وظیفه، توسط هر فرکانسی بین flow , fmax ، میتواند اجرا شود (fmax بیشترین فرکانس پردازنده میباشد). درصورتیکه وظیفه در پایین ترین فرکانس اجرا شود ، زمان اجرایش طولانی شده و این میتواند سبب نقض سررسید مابقی وظایف موجود شود و از طرفی درصورتیکه در بالاترین فرکانس اجرا شود، انرژی زیادی مصرف کرده و این نیز ممکن است سبب نقض سررسید در مابقی وظایف، بدلیل کمبود انرژی شود. بنابراین انتخاب فرکانس مناسب برای اجرای وظایف از اهمیت بالایی برخوردار است. پارامتر مهمی که در انتخاب فرکانس مناسب برای اجرای وظیفه دخالت دارد، موجودیت انرژی است که با توجه به مزایا و معایب المانهای ذخیرهسازی که در ابتدای فصل بیان کردیم، الگوریتم مناسب، الگوریتمی است که تصمیمات زمانبندی و انتخاب فرکانس را طوری اتخاذ کند که تاحد ممکن انرژی مورد نیاز برای اجرای وظیفه، از محیط، برداشت شده و تعداد رجوع به ذخیرهساز انرژی، حداقل شود. بنابراین برای رسیدن به این مهم در روش پیشنهادی برخلاف روشهای قبلی، موجودیت انرژی را بجای بررسی در یک نقطه از زمان، در یک فاصله زمانی بررسی کرده و میزان انرژی مورد نیاز برای اجرای وظایفی که در این بازه نیز وارد سیستم میشوند، محاسبه میکنیم. درنهایت توسط مقایسه این دو مقدار، تصمیمات زمانبندی، اتخاذ خواهد شد. البته در حالت کلی، زمانی یک وظیفه، اجازه اجرا دارد، که انرژی کافی برای اجرای وظایف موجود در بازه انتخابی، موجود باشد. مزیت بررسی وظایف و موجودیت انرژی در بازه، در این است که، علاوه بر اینکه از وجود انرژی کافی برای نه تنها یک وظیفه، بلکه برای چند وظیفه پیاپی در صف آماده، اطمینان حاصل کرده و سپس تصمیمات زمانبندی لحاظ میشود، تأثیرات اجرای یک وظیفه برروی سایر وظایف، هم از دید زمان و هم انرژی، نیز بررسی شده و الگوریتم قادر به تصمیمگیری بهتری خواهد بود. بعلاوه زمانیکه نیاز به بهروز کردن زمانهای اجرا و خاتمه برای سایر وظایف هستیم، برخلاف روش بکار رفته در ]19[که این تغییرات را در کل وظایف اعمال میکرد و درنتیجه زمان اجرای الگوریتم بسیار بالا میرفت، در این روش فقط تغییرات برروی وظایف موجود در بازه اعمال میشود و از آنجاییکه انتخاب بازه بصورت پویا رخ میدهد، تأثیر این تغییرات میتواند در زمان اجرای کمتری برروی سایر وظایف نیز اعمال شود. بنابراین با 3 مسئله مواجه هستیم :
انتخاب بازه زمانی برای بررسی انرژی
محاسبه انرژی مورد نیاز برای اجرای وظایف موجود دراین بازه
محاسبه موجودیت انرژی در واحد ذخیرهسازی (شامل باطری و ابرخازن) و انرژی محیطی
4-4-1 انتخاب بازه زمانی
نکته مهم در انتخاب بازه زمانی مناسب برای بررسی موجودیت انرژی و انرژی مورد نیاز وظایف در آن بازه، طول بازه میباشد. چراکه در صورت بزرگ بودن بازه، تعداد وظایف وارد شده به سیستم در این فاصله، زیاد میشود. در نتیجه انرژی مورد نیاز این وظایف نیز، مقدار بیشتری است بنابراین در این بازه بزرگ، موجودیت انرژی نیز باید، حداقل به اندازه انرژی مورد نیاز باشد. در بدترین حالت یعنی در زمان کاهش و یا عدم وجود انرژی محیطی، ظرفیت ذخیرهساز انرژی باید به اندازه انرژی مورد نیاز باشد، پس نیازمند ظرفیت ذخیرهسازی بالایی خواهیم بود. اما درصورت کوچک بودن بازه، درست است که نسبت به حالت قبل، ظرفیت ذخیرهسازی، کمتر خواهد بود، اما در اینحالت درصو
رتیکه وظایف موجود در بازه انرژی کمتری نیز نیاز داشته باشند، به موجودیت انرژی کمتری نیز نیاز خواهیم داشت درنتیجه الگوریتم براساس یک مقدار کمی از انرژی، در مورد زمان اجرا و فرکانس اجرایی تصمیمگیری میکند. حال با توجه به اینکه زمان ورود وظایف غیرتناوبی از قبل مشخص نیست، اگر در حین اجرای یک وظیفه، یک وظایفه غیرتناوبی با انرژی مطالبه شده بالا و سررسید کمتر از وظیفه جاری، وارد سیستم شود باتوجه به انحصاری بودن سیستم، پردازنده باید وظیفه تازه وارد را اجرا کند که باتوجه به کم بودن موجودیت انرژی، بالا بودن مقدار انرژی مورد نیاز برای اجرای وظیفه و نزدیک بودن سررسید وظیفه، با احتمال بسیار بالایی وظیفه از سیستم بدلیل نقض سررسید، حذف خواهد شد و این برای یک سیستم تعبیهشده بیدرنگ، نقص محسوب میشود. درنتیجه انتخاب بازه کوچک هم عمل مناسبی نیست. در این راستا بازهای که انتخاب میکنیم براساس سررسید مطلق وظایف موجود در صف آماده میباشد. بعبارتی زمان ابتدای بازه زمان جاری سیستم، tc ، و زمان انتهای بازه، سررسید مطلق وظیفه جاری، میباشد یعنی [tc , Dm]. واضح است که این فاصله به ازای هر تغییری در وظیفه موجود در ابتدای صف آماده، به روز میشود.
4-4-2 محاسبه انرژی مورد نیاز برای اجرای وظایف موجود در بازه
بعد از محاسبه بازه مورد نظر، باید وظایفی را که در این بازه وارد سیستم میشوند، شناسایی کنیم. این وظایف به 3 دسته قابل تقسیماند:
وظایفی که در بازه [tc , Dm] ، وارد سیستم شده و باید در همین بازه نیز اجرا و خاتمه یابند.
وظایفی که در (tc , Dm]، وارد سیستم شده و در همین بازه هم شروع به اجرا خواهند شد، اما زمان خاتمه آنها در این بازه نمیباشد. بعبارتی دارای سررسید بیشتری نسبت به سایر وظایف میباشند.