I nte rna t io na l J o urna l o f   E lect rica l a nd   Co m p ute E ng in ee ring   ( I J E CE )   Vo l.   9 ,   No .   6 Dec em b er   201 9 , p p .   4 9 0 8 ~4 9 1 9   I SS N:  2 0 8 8 - 8708 DOI : 1 0 . 1 1 5 9 1 / i j ec e . v9 i 6 . p p 4 9 0 8 - 4919          4908       Jou r na l ho m ep a g e h ttp : //ia e s co r e . co m/ jo u r n a ls /in d ex . p h p / I JE C E   Efficien m ul ti - tas k   o f floa ding   w ith  e nerg y  and  co m p utatio na reso urces o pti m i za tion in a  m o bile  edg e c o m puting  n od e       M o ha m ed  E l G h m a ry ,   T a ri k   C ha ny o ur ,   Yo us s ef   H m i mz,   M o ha mm ed  O uça m a h C h er k a o ui M a lk i   De p a rtme n o f   Co m p u ter S c ien c e S id i   M o h a m e d   Be n   A b d e ll a h   U n iv e rsity ,   M o ro c c o       Art icle  I nfo     AB ST RAC T     A r ticle  his to r y:   R ec eiv ed   J a n   15 ,   2 0 1 9   R ev i s ed   J u n   2 ,   2 0 1 9   A cc ep ted   J u n   26 ,   2 0 1 9       W it h   th e   f if th - g e n e ra ti o n   (5 G n e tw o rk s,  M o b il e   e d g e   c o m p u ti n g   (M EC)  is  a   p ro m isin g   p a ra d ig m   to   p ro v id e   n e a c o m p u ti n g   a n d   sto ra g e   c a p a b il it ies   to   s m a rt  m o b il e   d e v ice s.  In   a d d it i o n ,   m o b il e   d e v ice a re   m o st  o th e   ti m e   b a tt e ry   d e p e n d e n a n d   e n e rg y   c o n stra in e d   w h il e   th e y   a re   c h a ra c teriz e d   b y   th e ir  li m it e d   p ro c e ss in g   a n d   sto r a g e   c a p a c it ies .   A c c o rd in g ly ,   th e se   d e v ice s   m u st  o ff lo a d   a   p a rt  o f   th e ir  h e a v y   tas k th a re q u ire  a   lo o f   c o m p u tatio n   a n d   a re   e n e rg y   c o n su m in g .   T h is  c h o ice   re m a in th e   o n ly   o p ti o n   in   so m e   c ircu m st a n c e s,  e sp e c iall y   w h e n   th e   b a tt e ry   d ra in o ff .   Be sid e s,  th e   lo c a CP U   f re q u e n c y   a ll o c a ted   to   p r o c e ss in g   h a a   h u g e   im p a c o n   d e v i c e e n e rg y   c o n su m p ti o n .   A d d it io n a ll y ,   w h e n   m o b il e   d e v ice h a n d le  m a n y   tas k s,  th e   d e c isio n   o f   th e   p a rt   to   o f f lo a d   b e c o m e c rit ica l.   A c tu a ll y ,   w e   m u s c o n si d e th e   w irele ss   n e t w o rk   sta t e ,   th e   a v a il a b le  p ro c e ss in g   re so u rc e a b o t h   sid e s,  a n d   p a rti c u lar ly   th e   lo c a a v a il a b le  b a tt e r y   p o w e r.   In   th is  p a p e r,   we   c o n sid e a   sin g le  m o b il e   d e v ic e   th a is  e n e rg y   c o n stra in e d   a n d   th a re tain a   li st  o h e a v y   o ff lo a d a b le  tas k th a a re   d e la y   c o n stra in e d .   T h e re f o re ,   we   fo rm u late d   th e   c o rre sp o n d i n g   o p ti m iza ti o n   p ro b le m ,   a n d   p ro p o se d   a   S im u late d   A n n e a li n g   b a se d   h e u r isti c   so l u ti o n   sc h e m e .   In   o r d e t o   e v a lu a te  o u so lu ti o n ,   w e   c a rried   o u t   a   se o f   sim u latio n   e x p e rim e n ts.  F in a ll y ,   th e   o b tai n e d   re su lt s   in   term o f   e n e r g y   a r e   v e r y   e n c o u ra g in g .   M o re o v e r,   o u s o lu ti o n   p e rf o rm s   th e   o f f lo a d in g   d e c isio n s   w it h in   a n   a c c e p tab le an d   f e a sib le t im e f r a m e s.   K ey w o r d s :   C o m p u tatio n   o f f lo ad i n g   E n er g y   o p ti m izatio n   Mo b ile  e d g c o m p u ti n g   Si m u lated   a n n ea li n g   Co p y rig h ©   2 0 1 9   In stit u te o A d v a n c e d   E n g i n e e rin g   a n d   S c ien c e   Al rig h ts re se rv e d .   C o r r e s p o nd ing   A uth o r :   Mo h a m ed   E l G h m ar y ,   Dep ar t m en t o f   C o m p u ter   Sci e n ce ,   Sid i   Mo h a m ed   B en   A b d ellah   Un i v er s it y ,     FS DM ,   L I I A L ab o ,   Fez,   Mo r o cc o .   E m ail:  m o h a m ed . elg h m ar y @ u s m b a. ac . m a       1.   I NT RO D UCT I O N   Mo b il E d g C o m p u ti n g   ( ME C )   c o n ce p t   [1 - 3] ,   it  h a s   b ee n   r ec o g n ized   as  t h n ex g en er atio n   co m p u ti n g   i n f r astru c tu r th at   is   b ased   o n   Mo b ile  C lo u d   C o m p u tin g   p ar ad ig m   [4 - 7] .   I ca n   o f f er   n ea r b y   cu s to m ized   s er v ice s   th a r eq u ir g o o d   tr an s m is s io n   b an d w id t h ,   ad d itio n al  d ata  s to r ag an d   p r o ce s s in g .   As  ill u s tr ated   in   Fig u r 1 ,   MEC   ca n   a u g m e n m o b ile  d ev ice s   ca p ab ilit ies  b y   o f f lo ad in g   [8 - 10]   s o m e   p ar ts   o f   th eir   h a v y   ap p licatio n s   v ia  w i r eless   ac ce s s   to   r eso u r ce - r ic h   ed g n o d e ,   an d   th e n   e f f ec ti v el y   r ed u ce s   t he ir   p o w er   co n s u m p t io n [ 1 1 ] Mo r eo v er ,   t o   ef f icie n tl y   o f f lo ad   g r ee d y   ap p licatio n   w h ile  r esp ec tin g   d ea d lin e s ,   it  is   o f ten   d ec o m p o s ed   i n to   s ev er al  i n d ep en d en t   o f f lo ad ab le  task s   w it h   a   d ea d lin co n s tr ain [ 1 2 - 14] .   Ma n y   p ap er s   s t u d ied   r eso u r ce   allo ca tio n   w it h in   ME C   i n f r astru ct u r to   o p ti m ize  t h p r o ce cin g   ti m [ 1 5 - 18] .   On   t h o th er   h a n d ,   m a n y   s tat o f   th ar w o r k s   s tu d ied   r es o u r ce   a llo ca tio n   w it h in   ME C   in f r astr u ct u r to   o p tim ize  th e   en er g y   co n s u m p t io n   [ 1 3 ,   1 9 ,   2 0 ] .   I n   [ 2 1 ] ,   th au th o r s   in v est ig ate  a   r eso u r ce   a llo ca tio n   p o lic y   to   m ax i m ize  t h a v ailab le  p r o ce s s in g   ca p ac it y   f o r   ME C   I o T   n et w o r k s   w i th   co n s tr ain ed   p o w e r   an d   u n p r ed ictab le   task s . Un f o r tu n atl y ,   m o s t   o f   t h e m   co n s id er   u s er s   w it h   u n iq u e   tas k   o n l y .   Ho w ev er ,   c u r r en S m ar Mo b ile   Dv ices  ( SM Ds )   ca n   h o s s e v er al  g r ee d y   ap p licatio n s   th at  h av to   o f f lo ad   a   p ar t   o f   th eir   task s   to   i m p r o v e   th q u al it y   o f   t h ex p er ie n ce   o r   s i m p l y   to   av o id   th w a s te  o f   t h eir   a v ailab le  r es o u r ce s .   T h er ef o r e,   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   E lec  &   C o m p   E n g     I SS N:  2 0 8 8 - 8708       E fficien t m u lti - ta s o fflo a d in g   w it h   en erg a n d   c o mp u ta tio n a l res o u r ce s   ...   ( Mo h a med   E l G h ma r y)   4909   th o f f lo ad i n g   d ec is io n   s h o u l d   b g en er alize d   a cc o r d in g   t o   m u lti - tas k   s ce n ar io .   T h is   p r o b lem   r elie s   o n   th e   j o in t d ec is io n   o f   ta s k s   o f f l o ad in g   an d   t h allo ca tio n   o f   c o m m u n icatio n   o r   co m p u tin g   r eso u r ce s .           Fig u r 1 .   Mo b ile  ed g co m p u t in g   i llu s tr atio n       R ec en t l y ,   th a u t h o r s   o f   [ 1 3 ]   s tu d ied   s in g le - u s er   m u l ti - tas k   o f f lo ad in g   s en ar io   b y   o p ti m iz in g   r ad io   r eso u r ce s   a n d   lo ca f r eq u e n c y .   T h e y   d id   n o co n s id er   t h lo ca en e r g y   a v ailab il it y   n o r   t h r e m o te   s er v er s   f r eq u en c y .   B esid es,  t h e y   co n s id er   task s   w it h   t h s a m d ea d lin T d .   I n   th is   w o r k ,   w s t u d y   th g e n er al  m u lt i - task   o f f lo ad in g   s e n ar io   w h er e   w in tr o d u ce   th co n tr o o f   t h av ailab le  lo ca en er g y ,   an d   co n s id er   th ed g e   s er v er s   f r eq u e n c y   as   d ec i s io n   p ar a m eter   in   o u r   o p ti m iz atio n   p r o b le m .   Mo r eo v er ,   w e   co n s id er   a   g e n er al   s etti n g   w h er ea c h   o f f lo ad ab le  tas k   h a s   to   b e x ec u ted   w it h in   it s   s p ec i f ic  d ea d lin e   t i m ax .   A c co r d in g   to   o u r   v is io n ,   w ca n   p r o lo n g   t h b at ter y   li f e   o f   th m o b ile  d ev ice  b y   co n s id er i n g   th a m o u n t   o f   its   a v ailab le  p o w er ,   an d   r ed u ce   th tas k s   p r o ce s s in g   ti m b y   ad j u s ti n g   t h e d g s er v er s   f r eq u e n c y .   Su b s eq u en tl y ,   w h a v e   f o r m u lated   an   o p ti m izatio n   p r o b lem   th at   m in i m ize s   t h e n e r g y   co n s u m ed   b y   j o in tl y   d ec id in g   t h lo ca a n d   ed g co m p u ti n g   f r eq u en cie s ,   as  w ell   as   t h o f f lo ad i n g   d ec is io n s .   D u e   to   it s   co m b i n ato r ial  n atu r e   an d   a f ter   it s   d ec o m p o s itio n ,   w p r o p o s h eu r i s tic  s o l u tio n   b ased   o n   s i m u lated   an n ea li n g   al g o r it h m   to   j o in t ly   d ec i de   th e   task s   o f f lo a d i n g   an d   t h allo ca tio n   o f   co m p u ti n g   r eso u r c es T h o b jectiv is   to   m in i m ize  th co n s u m e d   en er g y   v ia   t h o f f lo ad in g   b y   c o n s id er in g   th ta s k s’   late n c y   c o n s tr ain ts   a n d   th r es h o ld   o f   av ailab le  en er g y .   T h r em ai n d er   o f   th i s   p ap er   is   o r g an ized   as  f o llo w s   :   t he   s y s te m s   m o d el  an d   th o p ti m izatio n   p r o b lem   f o r m u latio n   ar p r esen ted   i n   Sectio n   2 .   I n   Se ctio n   3 ,   w e   p r e se nt   o u r   m e th o d   to   so lv t h e   o p tim izatio n   p r o b lem .   I n   s ec ti o n   4   w p r ese n th e   s i m u latio n   r es u lt s   a n d   t h eir   d is c u s s io n .   Fi n all y ,   Sectio n   5   co n clu d es t h p ap er .       2.   SYST E M   M O DE L   AND  P R O B L E M   F O R M UL AT I O N   2 . 1 .   Sy s t e m   m o del   Fig u r 2 Sh o w s   s i n g le  s m ar m o b ile   d ev ice  ( SM D)   co n tai n in g   a n   o f f lo ad ab le  m u lt i - tas k   li s t.   I n   th i s   w o r k ,   w p lan   to   s t u d y   t h b eh a v io r   o f   th o f f lo ad in g   p r o ce s s   f o r   m u lti - tas k   SMD  i n   an   ed g e   en v ir o n m e n t,  w h ile  w o p ti m i ze   co m p u tatio n   r eso u r ce s   a v ai lab le  at  th ed g s er v er   as  w e ll  as  at  t h m o b ile   d ev ice.   P ar ticu lar l y ,   th e   a v aila b le  en er g y   at   t h SM f o r   tas k s   e x ec u tio n   is   li m ited .   B esid es,  in   t h co n te x t   o f   o f f lo ad in g ,   s o m p iece s   o f   co m p u t atio n al l y   i n ten s i v ap p licatio n   ar d iv id ed   in to   m u lt ip le  m u tu al l y   in d ep en d en t   o f f lo ad ab le  tas k s   [ 2 2 ,   2 3 ] .   T h er ef o r e,   ac co r d in g   to   th e   av ai lab le  co m p u tatio n al  a n d   r ad io   r eso u r ce s ,   s o m tas k s   ar p i ck - u p   f r o m   t h r es u lti n g   ta s k s   l is to   b o f f lo ad ed   to   th ed g s er v er s   f o r   co m p u ti n g .   T h o th er s   ar p er f o r m ed   lo ca ll y   o n   th SMD  it s elf .   T h ex ec u tio n   o f   t h w h o le  lis m u s h ap p e n   w it h i n   th ti m li m it  o f   t h ap p licatio n .   A d d itio n all y ,   it  is   ass u m ed   th a th SMD  co n cu r r en tl y   p er f o r m s   co m p u tatio n   an d   w ir eles s   tr an s m i s s io n .     Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I n t J   E lec  &   C o m p   E n g ,   Vo l.  9 ,   No .   6 Dec em b er   2 0 1 9   :   4 9 0 8   -   49 1 9   4910       Fig u r 2 S y s te m   m o d el  illu s tr atio n       Fo r   all  th ese  co n s id er atio n s ,   w d er iv m a th e m atica e n er g y   co n s u m p tio n   m o d el  th at   co n s id er s   th r ee   m a in   d ec i s io n s t h o f f l o ad in g   d ec is io n   f o r   ea ch   tas k ,   th lo ca e x ec u tio n   f r eq u e n c y   o f   t h SMD,   a n d   th s er v er   e x ec u tio n   f r eq u en c y   at  th ed g e.   T h en ,   w f o r m u l ate  an   en er g y   m i n i m izatio n   p r o b lem .   P r ac tically ,   t h SMD  i s   co n n ec ted   to   an   E d g No d ( E N) ,   an d   is   in te n d ed   to   o f f lo ad   s et  o f   in d ep en d en ta s k s   b y   t h m ea n   o f   an   E d g A cc ess   P o in ( E A P ) . A d d itio n a ll y ,   t h w ir eles s   ch an n el  co n d itio n s   b et w ee n   t h SMD  a n d   t h w i r eless   ac ce s s   p o i n ar n o co n s id er ed   i n   t h is   w o r k .   Mo r eo v er ,   at   t h ti m e   o f   th o f f lo ad in g   d ec is io n   an d   t h tr an s m i s s io n   o f   th o f f lo a d ab le  task s ,   th u p li n k   r ate  r   is   ass u m ed   al m o s u n c h a n g ed .   As  s h o w n   i n   Fi g u r 2 . ,   th co n s id er ed   s m ar m o b ile  d ev ic co n tain s   in d ep en d e n tas k s   d en o ted   as   τ { τ 1 , τ 2 , , τ N } .   I n   ad d itio n ,   t h e s tas k s   ar ass u m ed   to   b co m p u ta tio n all y   i n ten s i v a n d   d ela y   s en s iti v a n d   h a v to   b co m p leted .   E ac h   tas k   τ i   ca n   b p r o ce s s ed   eit h er   lo ca ll y   o r   at  t h e d g e.   I r ep r esen t s   an   ato m ic  i n p u d ata  tas k   t h at  ca n n o t   b d iv id ed   in to   s u b - ta s k s .   Mo r eo v er ,   it  is   ch ar ac ter iz ed   b y   th f o llo w i n g   th r ee   p ar a m eter s   τ i d i , λ i , t i m ax .   T h f ir s t   o n d en o ted   d i [ b its ]   id en tif i es  th e   a m o u n t   o f   t h i n p u t   p ar am eter s   an d   p r o g r a m   co d es  to   tr an s f er   f r o m   th u s er s   l o ca d ev ice  to   th e   ed g s er v e r .   T h s ec o n d   o n d en o ted   λ i   [ cy cle s ]   s p ec if ie s   t h w o r k lo ad   r ef er r in g   to   th e   co m p u tat io n   a m o u n n ee d e d   to   ac co m p lis h   th p r o ce s s in g   o f   t h i s   tas k .   T h th ir d   p ar am eter   t i m ax   r ef er s   to   th e   r eq u ir ed   m a x i m u m   late n c y   f o r   th is   ta s k .   T h ex ec u tio n   n at u r d ec is io n   f o r   tas k   τ i   eith er   lo ca ll y   o r   b y   o f f lo ad in g   to   th ed g s er v er   i s   d en o ted   x i w h er e     x i { 0 ; 1 } .     x i = 1   in d icate s   t h at  th SMD  h as  to   o f f lo ad   τ i   to   th ed g s er v er ,   an d   x i = 0   in d icate s   t h at  τ i   is   lo ca ll y   p r o ce s s ed .     Fro m   t h is   p o in t,  a ll  ti m e   ex p r ess io n s   ar g i v en   i n   S ec o n d s ,   an d   e n er g y   co n s u m p t io n s   ar g i v e n   i n   Jo u le .   T h en ,   if   th SMD  lo ca l l y   ex ec u tes  ta s k   τ i ,   th co m p leti o n   ti m o f   its   lo ca ex ec u tio n   is   t i L = λ i f L .   So ,   f o r   all  task s ,   w h a v e :       t L = ( 1 x i ) λ i f L N i = 1   ( 1 )     A d d itio n al l y ,   th co r r esp o n d in g   en er g y   co n s u m p tio n   is   g iv e n   b y e i L = k L . f L 2 . λ i   [ 2 4 ] .   Hen ce ,   th to tal  e n er g y   co n s u m p tio n   w h ile  e x ec u ti n g   a ll tas k s   th a w er d ec id ed   to   b lo ca ll y   e x e cu ted   in   th SMD  i s   g iv e n   b y             = ( 1 ) = 1 = . 2 . ( 1 ) = 1     ( 2 )     I f   tas k     is   o f f lo ad ed   to   th e d g n o d e,   th o f f lo ad in g   p r o ce s s   co m p let io n   ti m is :   =    +  +  ,   w h er t i C o m   is   th ti m to   tr an s m it  th task   to   th E A P ,   an d   it  is   g i v en   b y   t i C o m = d i r   t i Exec   is   th ti m to   ex ec u te  t h ta s k   τ i at  th E N,   a n d   it  ca n   b f o r m u lated   as  t i Exec = λ i f S t i Res   is   th t i m to   r ec eiv e   th r es u lt  o u f r o m   t h ed g n o d e.   B ec au s th d ata  s ize  o f   t h r es u lt  i s   u s u all y   i g n o r ed   co m p ar ed   to   t h i n p u t   d ata  s ize,   w ig n o r th is   r ela y   ti m a n d   its   en er g y   co n s u m p tio n   as  ad o p ted   b y   [ 2 5 ] .   He n ce ,   f o r   th   task   = ( + ) ,   an d   f o r   all  task s ,   w h a v e:       t O = x i ( d i r + λ i f S ) N i = 1   ( 3 )   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   E lec  &   C o m p   E n g     I SS N:  2 0 8 8 - 8708       E fficien t m u lti - ta s o fflo a d in g   w it h   en erg a n d   c o mp u ta tio n a l res o u r ce s   ...   ( Mo h a med   E l G h ma r y)   4911   S o ,   th e n er g y   co n s u m p tio n   o f   t h co m m u n icatio n   p r o ce s s   ca n   b o b tain ed   b y   m u ltip l y i n g   t h r esu lti n g   tr an s m i s s io n   p er io d   b y   t h tr an s m i s s io n   u n d er tak e n   p o w er   ,   an d   th r est  o f   th e x ec u t io n   p er io d   b y   t h id le  m o d p o w er   .   T h u s ,   th is   e n er g y   is :       e C = p T  = 1 r + p I  = 1 f S   ( 4 )     Si m i lar l y ,   en er g y   co n s u m p tio n   at  th ed g s er v er   w h ile  ex ec u ti n g     is   g iv e n   b y :     = . 2 .   [ 8 ] .   T h ex ec u tio n   e n er g y   f o r   all  th o f f lo ad ed   task s   is :       e S = k S . f S 2 . λ i x i N i = 1   ( 5 )     Fin all y ,   g i v en   t h o f f lo ad i n g   d ec is io n   v ec to r      f o r   all  tas k s ,   t h lo ca ex ec u tio n   f r eq u en c y     o f   th e   SMD,   an d   t h s er v er   e x ec u ti o n   f r eq u e n c y     at  th e d g e,   t h to tal  en er g y   co n s u m p tio n   f o r   th SM is   co m p o s ed   o f   i ts   lo ca e n er g y   co n s u m p tio n ,   t h co m m u n icat io n   e n er g y   a s   w el a s   t h e x ec u tio n   en er g y   at   t h e   E N,   an d   it  is   g i v en   b y   (  , , ) = + + T h en ,   ac co r d in g   to   E q u atio n s   ( 2 ) ,   ( 4 )   an d   ( 5 )   an d   if   w n o te    Λ = = 1   ,   th to tal  en er g y   co n s u m p tio n   ca n   b f o r m u lated   as:     (  , f L , f S ) = ( k S f S 2 k L f L 2 + p I f S ) λ i x i N i = 1 +   p T r d i x i N i = 1 + k L f L 2 Λ     ( 6 )     2 . 2 .   P ro ble m   f o r m u la t io n   In   th i s   s ec t io n ,   w p r ese n o u r   o p tim iza tio n   p r o b le m   f o r m u latio n   t h at  ai m s   to   m i n i m ize  t h o v er all   en er g y   co n s u m p t io n   in   t h lo ca ex ec u tio n   o r   th o f f lo ad in g   p r o ce s s .   I n itiall y ,   to   p r ep ar e   th p r o b lem s   d at a   w s tar w it h   an   in itial  s o r ti n g   o f   th task s   lis τ { τ 1 , τ 2 , , τ N }   ac co r d in g   to   th eir   d ea d lin es  t i m ax .   Hen ce ,   th tas k s   e x ec u tio n   o r d er   w it h in   t h SMD  o r   th ed g s er v er   in   th f i n al  s o l u tio n   m u s f u l f ill  th i n itia o r d er   f o r   b o th   ca s es.  A cc o r d in g l y ,   t h o b tain ed   p r o b lem   is   f o r m u l ated   as:     : min { x , f L , f S } { ( k S f S 2 k L f L 2 + p I f S ) λ i x i N i = 1 +   p T r d i x i N i = 1 + k L f L 2 Λ }                    s . t. ( C 1 . 1 )                             x i   { 0 ; 1 } ;                                                                                                         i   1 ; N ;   ( C 1 . 2 )                           F L m i n f L F L m ax ;   ( C 1 . 3 )                           0 < f S F S   ;   ( C 1 . 4 )                           t i L = ( 1 x i ) f L λ k ( 1 x k ) i k = 1 t i m ax ;                 i   1 ; N ;   ( C 1 . 5 )                           t i O = x i x k ( d k r + λ k f S ) i k = 1 t i m ax   ;                       i   1 ; N ;   ( C 1 . 6 )                           e L = k L . f L 2 . λ i ( 1 x i ) N i = 1 E m ax .     I n   th is   w o r k ,   ea c h   o n o f   th av ailab le  ta s k s   ca n   b eith er   e x ec u ted   lo ca ll y   o r   o f f lo ad ed   t o   th ed g e   n o d e.   T h u s ,   ev er y   f ea s ib le  o f f l o ad in g   d ec is io n   s o l u tio n   h a s   t o   s atis f y   t h ab o v co n s tr ai n ts :   T h co n s tr ain t   ( C 1 . 1 )   r ef er s   to   t h o f f lo ad in g   d ec i s io n   v ar iab le  x i   f o r   tas k   τ i   w h ic h   eq u al s   0   o r   1 .   T h s ec o n d   co n s tr ain ( C 1 . 2 ) in d icat es  th at  t h allo ca ted   v ar iab le  lo ca f r eq u en c y   f L b elo n g s   to   a   p r io r f ix   in ter v a g i v en   b y   [ F L m i n , F L m ax ] .   Si m ilar l y ,   th allo ca ted   v ar iab le  r em o te  ed g s er v er   f r eq u e n c y   f S b elo n g s   to   th in ter v al  ] 0 , F S m ax ]   in   co n s tr ain ( C 1 . 3 ) .   T h co n s tr ain ( C 1 . 4 )   s h o w s   th at  t h ex ec u tio n   ti m o f   ea ch   d ec id ed   l o ca task   m u s s ati s f y   its   d ea d lin t i m ax .   Si m ilar l y ,   i n   co n s tr ai n t   ( C 1 . 5 ) ,   th o f f lo ad in g   ti m o f   ea ch   d ec id ed   o f f lo ad ab le  tas k   m u s s ati s f y   th s a m d ea d lin e   t i m ax .   T h f in al  co n s tr ain ( C 1 . 6 )   i m p o s e s   th at  t h t o tal  lo ca ex ec u t io n   en er g y   m u s n o ex ce ed   th to ler ated   g iv en   a m o u n t   E m ax .   T h is   co n s tr ain is   i m p o r tan esp ec iall y   f o r   SMDs  w it h   cr itical  b atter y .       3.   P RO B L E M   RE SO L UT I O N   I th i s   s ec tio n ,   w w ill  i n tr o d u ce   h o w   w d er iv o u r   s o lu tio n   f r o m   t h o b tain ed   o p ti m izatio n   p r o b lem .     3 . 1 .   P ro ble m   d ec o m po s it io n   I n   o u r   p r o p o s ed   m o d el,   th o f f lo ad in g   d ec i s io n   v ec to r   f o r   all  th e   tas k s   is   d e n o ted    .   L e d ef i n e   th v ec to r   t h at  co n tai n s   t h o f f lo ad ab le  task s   id en ti f ier s :   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I n t J   E lec  &   C o m p   E n g ,   Vo l.  9 ,   No .   6 Dec em b er   2 0 1 9   :   4 9 0 8   -   49 1 9   4912    1 = { i        /         x i = 1   }   ( 7 )        0 = { i        /         x i = 0   }   ( 8 )     A d d itio n al l y ,   w d ef in e:  Λ i = λ i i k = 1 Λ i 1 =   x i λ i i k = 1   D i = d i i k = 1    D i 1 =   x i d i i k = 1   A l s o ,   g iv e n   th d ec is io n   v e cto r    1 co n s tr ain ( C 1 . 4 )   f o r   lo ca task   ca n   b r ef o r m u lated   as     Λ i Λ i 1 t i m ax f L ;     i   1 ; N .   Fin all y ,   it  i s   eq u iv ale n to   o n co n s tr ain t:  ma x i { Λ i Λ i 1 t i m ax } f L .   L i k e w i s e,   co n s tr ai n t   ( C 1 . 5 )   f o r   an   o f f lo ad ab le  task   m ea n s     D i 1 r + Λ i 1 f S t i m ax   (   i   1 ; N ) .   So       D i 1 r   an d     Λ i 1 f S    m u s t b s tr ictl y   less   t h a n   t i m ax   (   i   1 ; N )   p ar ticu lar l y   min i { t i m ax D i 1 r } > 0 .   I n   t h is   ca s co n s tr ai n ts   ( C 1 . 5 )   ca n   b r ef o r m u la ted   as   Λ i 1 t i m ax D i 1 r f S ;     i   1 ; N .   Fin all y ,   it   is   eq u i v alen to   o n co n s tr ai n t ma x i { Λ i 1 t i m ax D i 1 r } f S .   Si m ila r l y ,   co n s tr ain ( C 1 . 6 )   ca n   b r ef o r m u l ate d   as   f L E m ax k L ( Λ N Λ N 1 ) .   Fo r   ea s o f   u s e,   let  n o te:     f L = ma x i { Λ i Λ i 1 t i m ax }   ( 9 )     f L + = E m ax k L ( Λ N Λ N 1 )   ( 1 0 )     f S = ma x i { Λ i 1 t i m ax D i 1 r }   ( 1 1 )     T h u s ,   f o r   g i v en   o f f l o ad in g   d ec is io n   v ec to r    ,   w g et  t h f o ll o w i n g   o p ti m izatio n   s u b - p r o b le m :      (  ) :       min { f L , f S } { ( Λ N Λ N 1 ) k L f L 2 + Λ N k S f S 2 + Λ N p I f S + D N 1 p T r }                          s . t. ( C 2 . 1 )                           F L m i n f L F L m ax ;   ( C 2 . 2 )                           f L f L   ;   ( C 2 . 3 )                           f S f S F S   ;   ( C 2 . 4 )                           k L f L 2 ( Λ N Λ N 1 ) E m ax .     C o n s id er in g   t h co n ti n u o u s   v ar iab les  f L   an d   f S ,   p r o b l e m   P 2   is   a   co n tin u o u s   m u lti - v ar iab le   o p tim izatio n   p r o b le m .   T h o b j ec tiv f u n ct io n    ( f L , f S ) = ( Λ N Λ N 1 ) k L f L 2 + Λ N 1 k S f S 2 + Λ N 1 p I f S + D N 1 p T r   ca n   b d ec o m p o s ed   i n to   th e   f o llo w i n g   t w o   in d ep en d e n f u n c tio n s   1 ( f L )   an d   2 ( f S )   w h er e     1 ( f L ) = ( Λ N Λ N 1 ) k L f L 2   an d   2 ( f S ) = Λ N 1 k S f S 2 + Λ N 1 p I f S + D N 1 p T r .   Mo r eo v er ,   g iv en   th d is j u n ctio n   b et w ee n   co n s tr ain ts   ( C 2 . 1 ) , ( C 2 . 2 )   a n d   ( C 2 . 4 )   o n   th o n h a n d ,   an d   ( C 2 . 3 )   in   p r o b le m   P 2   o n   th o th e r   h an d ,   th is   las ca n   b eq u iv alen tl y   d ec o m p o s ed   i n to   th f o llo w in g   t w o   i n d ep en d en t o p ti m izatio n   s u b - p r o b lem s .      . (  ) :       min { f L } { 1 ( f L ) = ( Λ N Λ N 1 ) k L f L 2 }                          s . t. ( C 3 . 1 . 1 )                           F L m i n f L F L m ax ;                                   ( C 3 . 1 . 2 )                           f L f L f L + .    . (  ) :       min { f S } { 2 ( f S ) = Λ 1 k S f S 2 + Λ N 1 p I f S + D N 1 p T r }                           s . t. ( C 3 . 2 . 1 )                           f S f S F S .     3 . 2 .   P ro ble m s   r eso lutio n   Fo r   th 3 . 1   p r o b lem ,   th o b j ec tiv f u n ctio n   1 ( f L )   is   s tr ictly   in cr ea s in g   co n ti n u o u s   f u n c tio n   ac co r d in g   to   its   v ar iab le  f L .   Hen ce ,   b y   tak i n g   in to   co n s id er atio n   th o b tain ed   co n s tr ai n ts   ( C 3 . 1 . 1 )   an d   ( C 3 . 1 . 1 ) ,   w ca n   d er iv th f o llo w i n g   f u n ctio n s   o p ti m u m   f L   g iv e n   b y :     Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   E lec  &   C o m p   E n g     I SS N:  2 0 8 8 - 8708       E fficien t m u lti - ta s o fflo a d in g   w it h   en erg a n d   c o mp u ta tio n a l res o u r ce s   ...   ( Mo h a med   E l G h ma r y)   4913   f L = {     0 if          =  1 if         f L > F L m ax or   f L + < F L m i n   or   f L > f L + F L m i n f L if   f L < F L m i n othe r w ise     ( 1 2 )     Fo r   th 3 . 2   p r o b lem ,   th e   o b j ec t iv f u n ctio n   2 ( f S )   is   co n ti n u o u s   f u n ctio n   ac co r d in g   to   it s   v ar iab le  f S w it h   f ir s o r d er   d er i v ate:  2 ( f S ) f S = 2 Λ N 1 k S f S Λ N 1 p I f S 2 co n s eq u e n tl y ,   2 ( f S )   d ec r ea s es  o n   ] 0 , p I 2 k S 3   ]   an d   in cr ea s es  o n   [ p I 2 k S 3 , + [   .   T h en ,   2 ( f S )   h as  an   o p ti m al  m in i m u m   v a lu at  th p o in t   p I 2 k S 3   w it h o u t   co n s id er in g   co n s tr ain t   ( C 3 . 2 . 1 ) .   T h er e f o r e,   w it h   ( C 3 . 2 . 1 ) w ca n   d er iv th e   f o llo w in g   f u n ctio n s   o p ti m u m   f S   g iv e n   b y :                       f S = {             if   min i { t i m ax D i 1 r } 0   or   f S > F S F S if       p I 2 k S F S 3 f S p I 2 k S 3 if       p I 2 k S ( f S ) 3 othe r w ise     ( 1 3 )     3 . 2 . 1 .   P ro ce s s ing   f re qu encie s   det er m i na t io n   Fro m   th ab o v r es u lt s ,   w it h   g iv e n   o f f lo ad in g   d ec is io n   v ec to r      ,   w p r ese n t h n e x A l g o r ith m   1   th at   g iv e s   th o p ti m al  allo ca te d   lo ca l f r eq u en c y   f L as  w ell  as t h r em o te  ed g s er v er s   p r o ce s s in g   f r eq u e n c y   f S .     3 . 2 . 2 .   T he  ener g y   co ns u m p t io n det er m ina t io n   Si m i lar l y ,   g i v en   an   o f f lo ad in g   d ec is io n   v ec to r      th n e x t   a lg o r ith m   2   u s e s   t h f ir s al g o r ith m   to   d eter m in t h m in i m al  e n er g y   co n s u m p tio n :     Alg o r ith m   1 f re q u e n c ies   o p ti m u m   f o a   g iv e n      Inp u t:  T h e   o ff lo a d in g   p o li c y    .   O u t p u t f L a n d   f S .   1:   De ter m in a te   1   a c c o rd in g   to   ( 7 );   2:   if   =  1 th e n   3:        f L = 0 ;   4:        g o to   1 6 ;   5:   e n d   if   6:   Ca lcu late f L , f L +   a c c o rd in g   t o   (9 )   a n d   ( 1 0 re sp e c ti v e ly ;   7:   if  f L > F L ma x o r   f L + < F L mi n   o r   f L > f L + th e n   8:                 r e tu r n   ;   9:   e lse   10:          if  f L < F L mi n th e n   11:                               f L = F L mi n ;   12:          e lse   13:                          f L = f L ;   14:          e n d   if   15:   e n d   if   16:   if  m in { 1 } 0   th e n   17:                 r e tu r n   ;   18:   e lse   19:                 Ca lcu late f S   a c c o rd in g   to   (1 1 );   20:                 if  f S > F S   th e n   21:                             r e tu r n   ;   22:                 e lse   if  p I 2 k S F S 3   t h e n     23:                                               f S = F S ;   24:                               e lse   if   p I 2 k S ( f S ) 3 th e n   25:                                                           f S = f S ;   26:                                             e lse   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I n t J   E lec  &   C o m p   E n g ,   Vo l.  9 ,   No .   6 Dec em b er   2 0 1 9   :   4 9 0 8   -   49 1 9   4914   27:                                                           f S = p I 2 k S 3 ;   28:                                             e n d   if   29:                            e n d   if   30:                 e n d   if   31:   e n d   if   32:   r e tu r n   ( f L , f S ) ;       Alg o r ith m   2 En e rg y   c a lcu latio n   Inp u t:  T h e   li st    o f   N su b - tas k s,   o f f lo a d in g   p o l icy    .   O u t p u t : (  , , ) .   1:   Ca ll   Alg o r ith m   1   to   c a lcu late   ( )   u sin g    ;   2:   if    =   o r   =   th e n     3:                   r e tu r n           4:   e lse   5:                     Ca lcu late   (  , , ) a c c o rd in g   to   (6 );   6:                     r e tu r n   (  , , )   ;   7:   e n d   if      3 . 3 .   P ro po s ed  s o lutio ns   Nex t,  t h p r o b le m   r elies  o n   d eter m in i n g   t h o p ti m al  o f f lo ad in g   d ec is io n   v ec to r      th at   g i v es   th o p ti m al  e n er g y   co n s u m p t io n .   Ho w e v er ,   to   iter ate  o v er   all  p o s s ib le  co m b i n atio n s   o f   lis o f   b in ar y   v ar iab les,  th ti m co m p le x it y   is   e x p o n en t ial  ( th e x h a u s t i v s ea r ch   o v er   all  p o s s ib le  s o lu tio n s   r eq u ir es  2 N   iter atio n s ) .   S u b s eq u e n tl y ,   t h e   to ta ti m co m p le x it y   o f   t h w h o le  s o l u tio n   ( in c lu d i n g   A l g o r ith m   1 )   i s   O( 2 N ) * O( 1 ) =O ( 2 N )   th at  i s   n o p r ac tical  f o r   lar g v al u es  o f   N .   I n   th f o llo w in g ,   w p r o p o s lo w   co m p le x it y   ap p r o x im a te  alg o r it h m   to   s o l v th is   q u e s tio n .     3 . 3 . 1 .   B rut f o rc s ea rc h so lutio n   Fo r   co m p ar is o n   p u r p o s e,   w i n tr o d u ce   th B r u te  Fo r ce   Sea r ch   m et h o d   f o r   f ea s ib le  s m all   v alu e s   o f   N.   T h is   m et h o d   ex p lo r es  all  ca s es  o f   o f f lo ad i n g   d ec is io n s   an d   s a v es  t h o n w i th   t h m i n i m u m   e n er g y   co n s u m p tio n   as  w el as  its   co m p let io n   ti m e.   No w ,   th n e x alg o r it h m   s u m m ar izes  th B r u te  Fo r ce   Sear ch   So lu tio n .     Alg o r ith m   3   Bru te F o rc e   S e a rc h   Of f lo a d in g     Inp u t: T h e   li st  τ   o f   N su b - tas k s;   O u t p u t:  th e   o ff lo a d in g   p o l icy    .   In iti a li z e m in En e rg y =   1:   fo r   i= 1   to      do   2:                           Us e   th e   b it s rep re se n tati o n   o f   in teg e to   b u i ld   th e   p o li c y    ;   3:                           Ca ll   Al g o r ith m   2   to   g e n e w En e r g y   u sin g   τ   a n d    ;   4:                           if      <     th e n     5:                                                         6:                                                 ;      7:                           e n d   if   8:   e n d   fo r   9:   r e tu r n      ;     3 . 3 . 2 .   Si m ula t ed  a nn ea li ng   o f f lo a di ng   ba s ed  o n w o rk lo a d dens it y   t h re s ho ld   Fo r   th s ec o n d   s o l u tio n ,   w p r o p o s th u s o f   Si m u la ted   An n ea lin g   ( S A )   b ased   m eth o d .   T h S tech n iq u w a s   ad o p ted   as  a   h e u r is tic  s o lu t io n   i n   t h o p ti m izatio n   f iel d   esp ec iall y   f o r   h ar d   p r o b lem s .   T o   im p r o v s o lu t io n ,   it  e m p lo y s   iter ativ e   r an d o m   s o lu tio n   v ar iatio n .   I n ter ested   r e ad er s   ca n   r ef er   to   th f o llo w i n g   w o r k [ 2 6 ]   an [ 2 7 ]   f o r   m o r d etails  ab o u th is   is s u e.   So m r ef e r en ce s   d ea lin g   w it h   th o f f l o ad i n g   in   clo u d   e n v ir o n m e n t s   [ 1 9 ,   2 8 ,   2 9 ]   u s tas k s   w o r k lo ad   d en s it y   d e f i n ed   as  ω i = λ i d i [ cy c le  b it ]   as  p r io r ity   f ac to r   to   d ec id e   th e   tas k s   o f f lo ad in g .   A d d it io n all y ,   t h g en er ated   ta s k s   ar g en er all y   w it h   d if f er e n w o r k lo ad   d en s ities .    Mo r eo v er ,   if   t w o   tas k s   ar g iv en   w it h   s l ig h tl y   d if f er e n t d at s izes,  t h o n t h at   co n s u m e s   les s   en er g y   is   t h o n g i v e n   b y   t h s m alle s c y cl es’   co u n t.  B esid es,  w i th   a l m o s th s a m c y cle s   co u n t,  t h o n t h at  co n s u m e s   less   o f f lo ad i n g   e n er g y   i s   th o n g iv e n   b y   t h s m a lles d ata  s ize.   I n   b o th   ca s e s ,   th tas k   w it h   t h h i g h est  w o r k lo ad   d en s it y   i s   f a v o r ab le  f o r   o f f lo ad in g   ( p r o v id ed   to   h av a n   o f f lo ad in g   e n er g y   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   E lec  &   C o m p   E n g     I SS N:  2 0 8 8 - 8708       E fficien t m u lti - ta s o fflo a d in g   w it h   en erg a n d   c o mp u ta tio n a l res o u r ce s   ...   ( Mo h a med   E l G h ma r y)   4915   g ain   co m p ar ed   to   th e   lo ca l e x e cu ti o n   an d   n o t to   e x ce ed   its   e x ec u tio n   d ea d lin e) .   O n   t h o th e r   h an d ,   ta s k   w it h   h i g h   w o r k lo ad   d e n s it y   o f te n   h a s   lar g n u m b er   o f   c y cles .   I ts   lo ca e x ec u tio n   is   g e n er a ll y   v er y   e x p en s i v e   an d   th u s   m a k es   its   o f f lo ad in g   o f ten   v er y   f a v o r ab le.   I n   t h is   c o n tex t,  w e   in tr o d u ce   w o r k lo ad   d en s it y   t h r esh o ld   ω T   s u c h   t h at :   ta s k s   w it h   ω i >   ω T   ar m o r f av o r ab le  to   b o f f lo ad ed .   T h o th er s   ar ex ec u ted   lo c all y   o r   o f f lo ad ed   w it h   a   p r o p o r tio n al  p r o b ab ilit y   to   t h eir   co m p u ta tio n al  d e n s itie s .   T h o s w i th   s m al d en s itie s   ar f av o r ab le  f o r   lo ca ex ec u tio n ,   an d   t h o s w it h   h i g h   d en s itie s   ar f a v o r ab le  to   b o f f lo ad ed .   A cc o r d in g l y ,   i f   w n o te   ω m i n = min i { ω i } ω m ax = ma x i { ω i }   an d   th m id d le  o f   th in ter v al  [ ω m ax , ω m i n ]   as    ω T = ( ω m ax + ω m i n ) / 2   th en   ω T   ca n   b ch o s en   s u c h   t h at   ω T ω T < ω m ax .   I n   o u r   p r o p o s ed   s ec o n d   s o l u t io n ,   w h ich   w d e n o te  W o r k l o ad   Den s it y   b ased   Si m u lated   A n n ea li n g   Of f lo ad in g   ( W DS A O) ,   w ad o p ted   th f o llo w i n g   g e n er al  th r esh o ld   p r o b ab ilit y :         p = e E i / T 0     (1 4 )     w h er e   T 0   is   th in i tial  te m p er at u r co n s tan t.  E i   is   th s o lu tio n s   en er g y   v ar iatio n   w h ile  c h an g i n g   t h tas k   s tate.   T h en ,   in   ea ch   s ta g o f   o u r   s o lu tio n   a n d   w it h   t h in te n tio n   to   av o id   lo ca o p tim u m s ,   r an d o m   s o lu tio n s   w it h   p o o r   en er g y   p er f o r m a n ce   ar ac ce p ted   in   lin w it h   ce r tain   p r o b ab il it y   t h r es h o ld .   A cc o r d in g l y ,   A l g o r ith m   s u m m ar izes o u r   h e u r is tic  s o lu tio n .     A l g o r ith m   4   ta k es   as  i n p u t :   th su b - tas k s   li st  ,   th e   in i ti a tem p e ra tu re   T 0 th e   c o o li n g   f a c to CF ,   th e   tem p e ra tu re   tres h o ld   ,   a n d   th e   w o r k lo ad   d en s it y   t h r es h o ld   .     r a nd o m ( 0 , 1 )   is   f u n c tio n s   ca ll th at  g en er ate s   r an d o m   n u m b er   i n   [ 0 , 1 ] .     3 . 3 . 3 .   O rig ina l si m ula t ed  a nn ea li n g   o f f lo a din g   Fo r   th t h ir d   s o l u tio n   an d   f o r   co m p ar is o n   p u r p o s e,   w ta k t h v er s io n   o f   t h s o lu t io n   p r o p o s ed   b y   [ 5 ]   an d   d en o te  it   Or ig in al   Si m u lated   An n ea li n g   O f f lo ad i n g   ( OS A O) .   I n   t h is   s o lu tio n ,   t h lo ca e x ec u tio n   p r o b a b ilit y   in cr ea s e s   w it h   th in cr ea s o f   t h co m p u ti n g   d en s it y .   T h is   f ac lead s   to   o f f lo ad   task s   w it h   b ig   d ata  s ize  an d   w o r k lo ad   an d   p r ev en t   task s   w it h   lo w   d ata  s ize  a n d   h ig h   w o r k lo ad   to   tak h i g h   o f f l o ad   p r i o r ity .     Alg o r ith m   4 w o rk lo a d   d e n sity   b a se d   S im u late d   A n n e a li n g   Off lo a d in g     Inp u t: T h e   li st    o f   N su b - tas k s,T 0 ,   CF ,   ,   ;   O u t p u t :   th e   o ff lo a d in g   p o li c y    .   In iti a li z e :   a   ra n d o m   p o li c y    ;   1:   Ca ll   Alg o r ith m   2   to   c a lcu late   o l d En e rg y   u sin g     a n d    ;   2:   m in En e rg y = ∞;   3:   w h il e   T 0 >      do   4:        fo r   e a c h   in     do   5:                         if  >     th e n     6:                                       if  tas k   n o i n    1   th e   7:                                                   a d d     i   to    1   ;   8:                                       e n d   if   9:                         e lse   if  >   (  ) ra nd om ( 0 , 1 )       t h e n   10:                                                   if  tas k   in    1   th e n     11:                                                           m o v e   f ro m    1   to    0   ;   12:                                                   e n d   if   13:                                         e lse   if  tas k   in    0   th e n     14:                                                                 m o v e   f ro m    0   t o    1   ;   15:                                                         e n d   if   16:                                         e n d   if                                                17:                         e n d   if   18:                         Up d a te     u si n g   th e   n e w    1 ;   19:                         Ca ll   Alg o r ith m   2   to   g e n e w En e rg y   u sin g     a n d    ;   20:                           if  n e w En e rg y ≠    th e n   21:                                             = ne wEne rgy old Ene rgy     22:                                               if  < 0   th e n     23:                                                                   o ld E n e rg y = n e w En e r g y ;   24:                                                                     if   n e w En e rg y < m in En e rg y   t h e n     25:                                                                                           m in En e rg y   = n e w En e rg y   ;   26:                                                                                            =    ;   27:                                                                       e n d   if   28:                                              e lse   29:                                                                     Ca lcu late   p   a c c o rd in g   to   (1 3 );   30:                                                                       if  / 0 > ra nd om ( 0 , 1 )   th e n     Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I n t J   E lec  &   C o m p   E n g ,   Vo l.  9 ,   No .   6 Dec em b er   2 0 1 9   :   4 9 0 8   -   49 1 9   4916   31:                                                                                           o ld E n e rg y   =   n e w En e rg y ;   32:                                                                     e lse   33:                                                                                           P u b a c k   to   it o rig in a se t;   34:                                                                     e n d   if   35:                                               e n d   if   36:                           e n d   if   37:         e n d   fo r   38:         T 0 =   T 0 * CF   39:   e n d   w il e   40:   r e tu r n      ;       4.   RE SU L T S AN D   D I SCU SS I O N   4 . 1 .   Si m ula t io n set u p   T h p r esen ted   r esu l ts   i n   t h i s   w o r k   ar a v er ag ed   f o r   1 0 0   ti m e x ec u tio n s .   W i m p l e m en all   th al g o r ith m s   o n   th e   C ++ la n g u a g e .   A d d itio n a ll y ,   th e y   ar e   r u n   o n   a   lap to p   eq u ip p ed   w i th   2 . 4   GHz   I n te l   C o r i5   p r o ce s s o r   an d   8   GB   o f   R A M .   T h tr an s m is s io n   b a n d w id t h   b et w ee n   th m o b i le  d ev ice  n o d an d   r e m o te  ed g s er v er   i s   s et  to r   1 0 0 Kb /s .   T h lo ca C P f r eq u en c y   f L o f   th m o b ile  d ev ice   w il b o p ti m ized   b et w ee n   F L m i n = 1M Hz   an d   F L m ax = 60M Hz .   T h C P f r e q u en c y   o f   th r e m o te  ed g s er v er   n o d w ill  b e   opt im ized   u n d er   th v a lu e   F S = 6G Hz .   T h d ea d lin es  t i m ax   ar u n i f o r m l y   d e f i n ed   f r o m   0 . 5 s   to   2 s .   T h th r esh o ld   en er g y   E m ax   is   u n i f o r m l y   ch o s e n   in   [ 0 . 6   , 0 . 8 ] Λ . k L . ( F L m ax ) 2 . A d d itio n all y ,   th d ata  s ize  o f   ea ch   o n e   o f   t h tas k s   is   ass u m ed   to   b in   [ 3 0 , 3 0 0 ]   Kb .   Fo r   th c y c le  a m o u n o f   ea ch   t ask ,   i is   as s u m ed   to   b elo n g   to   [ 6 0 , 6 0 0 ] MCy cle s .   T h id le  p o w er   an d   tr an s m i s s io n   p o w er   ar s et  to   b p I = 0 . 01   W att  an d   p T = 0 . 1   W att  r esp ec tiv el y .   Fo r   t h en er g y   e f f icien c y   co e f f ic ien t s ,   w e   s et  k L = 10 26   an d   k S = 10 29 .   Fo r   th s i m u lated   an n ea li n g   m e th o d s ,   t h f o llo w i n g   p ar am eter   v a l u es  ar ad o p ted f ac to r   0 . 5 ,     ε 0 . 3 ,   T 0   2 0 0 ,   Δ t =   0 . 0 2 ( in   OS A O) ,   an d   C F=0 . 8 5 .     4 . 2 .   P er f o r m a nce  a na ly s is   W p r esen o u r   r esu lts   i n   ter m s   o f   av er ag d ec is io n   ti m an d   a v er ag en er g y   co n s u m p tio n .   W s tar b y   s t u d y in g   th av er a g en er g y s   co n s u m p t io n   th r o u g h p u f o r   ea ch   m et h o d .   T h u s ,   w ca r r ied   an   ex p er im e n t   w h er w v ar y   th n u m b er   o f   t ask s   p ar a m eter   b et w ee n   2   an d   5 0   task s .       4 . 2 . 1 .   T he  p a ra m et er     T h F ig u r e   3   s h o w s   r ap id   d ec r ea s o f   t h en er g y   co n s u m p tio n   u s in g   t h W DS AO  m et h o d   f o r   ω T   b et w ee n   0 . 3   an d   0 . 4 5   f o r   N   in   {1 0 , 1 5 , 2 0 , 2 5 , 3 0 } T h en ,   th is   en er g y   in cr ea s e s   f r o m   ω T     0 . 5   to   ω T     0 . 7 5   f o r   all  v alu e s   o f   N.   I n   ad d itio n   it  s lig h tl y   d ec r ea s es  af ter   ω T     0 . 7 5   o n ly   f o r   1 0   an d   =   3 0 .   A s   r esu lt,  we   f i n d   th at  th b est  v alu o f   ω T     th at  m in i m ize s   th e n er g y   c o n s u m p tio n   f o r   m o s o f   t h v alu e s   o f   i s     ω T     0 . 5 .   T h er ea f ter ,   w w i ll set  ω T     to   th v al u 0 . 5 .           Fig u r 3 Av er ag E n er g y   co n s u m p tio n   f o r   ω T   b et w ee n   0 . 2 5   an d   0 . 8 5       4 . 2 . 2 .   T he  ener g y   co ns u m p t io n   I n   ter m s   o f   en er g y   co n s u m p ti o n ,   th e x p er i m en t s   r es u lts   a r d ep icted   in   th e   f o llo w i n g   t w o   f i g u r e s .   Fig u r r ep r esen ts   th o b tai n ed   r esu lts   f o r   t h t h r ee   m et h o d s   w h er N   is   tak e n   b et w ee n   3   an d   2 5 .   On   t h o n e   h an d ,   it  s h o w s   s m al d is ta n ce   b et w ee n   t h r es u lts   o f   th o p tim al  B F m et h o d   an d   t h OS A m et h o d .   T h is   d if f er e n ce   v ar ies  f r o m   1 . 5 3 t o   9 . 3 0 %.  On   th o t h er   h an d ,   th W D S AO  r esu lts   ar al m o s t h s a m a s   th o p ti m al  r es u lt s .   T h d if f er en ce   v ar ies  f r o m   0 . 0 0 % to   2 . 8 8 %.   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   E lec  &   C o m p   E n g     I SS N:  2 0 8 8 - 8708       E fficien t m u lti - ta s o fflo a d in g   w it h   en erg a n d   c o mp u ta tio n a l res o u r ce s   ...   ( Mo h a med   E l G h ma r y)   4917   B ey o n d   th v al u N= 2 5 ,   an d   b ec au s o f   th co n s id er ab le  p r o ce s s in g   ti m o f   t h B FS   s o l u tio n ,   we   co m p ar ed   o n l y   t h OS A a n d   th W D S A m et h o d s .   Fig u r e   5   s h o w s   t h at  th r es u lt s   o f   th e   W D SA s o l u tio n   ar b etter   th an   t h o s o f   O S A O   f o r   all  v al u e s .   T h r esu lts   o f   t h f ir s t r ep r esen t a   g ai n   in   e n er g y   c o n s u m p tio n   th at  v ar ie s   b et w ee n   5 . 5 5 % a n d   8 . 3 3 %.             Fig u r 4 Av er ag e n er g y   co n s u m p tio n   f o r     b et w ee n   3   an d   25     Fig u r 5 Av er ag e ne r g y   co n s u m p tio n   f o r   b et w ee n   2 6   an d   50       4 . 2 . 3 .   T he  Av er a g E x ec utio T i me   No w ,   w co n s id er   th a v er ag e   ex ec u tio n   ti m i n   b o th   Fig u r e   6   an d   Fig u r 7 .   T h f ir s o n illu s tr ates   th e x ec u t io n   ti m co m p ar is o n   f o r   all  t h t h r ee   m et h o d s   wh ile  N   is   b et w ee n   3   a n d   2 5 .   I clea r l y   s h o w s   t h ex p o n en t ial  v ar iatio n   o f   t h B FS   s o lu tio n   t i m e   w it h   th e   p ar a m et er .   A d d itio n all y ,   T h O S A a n d   W D S AO  s o lu tio n s   g i v s tab le  ex ec u tio n   ti m t h at  r ea ch ed   f o r   N= 2 5   r esp ec t iv el y   0 . 2 7 m s   a n d   0 . 9 1 m s   f o r   b o th   m et h o d s .               Fig u r 6 E x ec u t u io n   t i m a v e r ag e   f o r     b et w ee n   3   an d   2 5     Fig u r 7 E x ec u t u io n   t i m a v e r ag f o r     b et w ee n   2 6   an d   50       T h s ec o n d   Fi g u r 7   illu s tr at es  th ex ec u tio n   ti m co m p ar is o n   f o r   OS A an d   W D S A O   m et h o d s   w h ile   i s   b et w ee n   2 6   a n d   5 0 .   T h OS A O   cu r v ill u s tr ates  s tab le  r u n n i n g   ti m th at   s tar ts   f r o m   0 . 2 8   m s   f o r   N= 2 6   an d   r ea ch es  0 . 7 5   m s   f o r   N= 5 0 .   On   th o th er   h an d ,   th W D SA c u r v il l u s tr ates  n ea r   lin ea r   r u n n in g   ti m e   t h at  s tar t s   f r o m   1 . 0 1   m s   f o r   N= 2 6   an d   r ea ch es  3 . 1 1   m s   f o r   N= 5 0 .   A cc o r d in g l y ,   t h p er f o r m a n ce s   i n   ter m s   o f   t h ex ec u tio n   ti m o f   th OS A m eth o d   ar s lig h t l y   h ig h er   th a n   th o s o f   t h W DSA m eth o d .   Nev er th e less ,   b o th   s o lu tio n s’   p er f o r m a n ce s   ar al w a y s   v er y   v er y   h i g h   a n d   m o r ac ce p tab le  co m p ar ed   to   th e   FB ex ac t   s o l u tio n .   T h i s   la s r ea ch e s   a n   e x ec u t io n   t i m e   of   3 4 8 6 2 . 3 5   m s   f o r   N= 2 5   o n l y ,   w h ic h   i s   in ap p r o p r iate  f o r   th co n tex t o f   th is   w o r k .       Evaluation Warning : The document was created with Spire.PDF for Python.