基于拍卖的边缘云期限感知任务卸载策略_裴翠.pdf

h t t p:/ww w.j s j k x.c o mD O I:1 0.1 1 8 9 6/j s j k x.2 1 1 2 0 0 1 9 4到稿日期:2 0 2 1-1 2-1 6 返修日期:2 0 2 2-0 1-1 3基金项目:国家自然科学基金(6 2 2 7 7 6 0 9 7)T h i sw o r kw a ss u p p o r t e db yt h eN a t i o n a lN a t u r a lS c i e n c eF o u n d a t i o no fC h i n a(6 2 2 7 6 0 9 7).通信作者:范贵生(g s f a n e c u s t.e d u.c o m)基于拍卖的边缘云期限感知任务卸载策略裴 翠1范贵生1,2虞慧群1岳一鸣11华东理工大学计算机科学与工程系 上海2 0 0 2 3 72上海市计算机软件评价与测试重点实验室 上海2 0 0 2 3 7(p e i c u i 0 7 0 31 6 3.c o m)摘 要 随着万物互联和5 G时代的到来,移动用户需要处理的数据量与其处理数据能力不匹配。将大量任务卸载到有限的边缘服务器上执行势必会产生竞争,拍卖模型的引入可以解决用户之间对资源的竞争问题。目前大多基于拍卖的任务卸载工作忽略了任务的期限感知,普遍的任务卸载工作只单一考虑延迟敏感任务,并且未考虑到保证卸载过程的安全性。基于此,提出了一种基于拍卖的期限感知任务卸载(A u c t i o nB a s e dD e a d l i n e-a w a r eT a s kO f f l o a d i n g,A B D T O)策略,利用基于智能合约的拍卖机制实现期限感知任务(延迟敏感型任务和非延迟敏感型任务)到边缘服务器的最优分配,以总效用(即总利润)作为评价标准,实现移动用户和边缘服务器的共赢。利用启发式遗传算法进行仿真实验,相比T A C D,U P P E R和R N D算法,A B D T O策略的整体效用更高,最后利用R e m i x和G a n a c h e等建立以太坊私有区块链网络进行仿真,证明了所提策略的正确性和可行性。关键词:边缘云;拍卖机制;期限感知;任务卸载;智能合约中图法分类号 T P 3 0 1 A u c t i o n-b a s e dE d g eC l o u dD e a d l i n e-a w a r eT a s kO f f l o a d i n gS t r a t e g yP E IC u i1,F ANG u i s h e n g1,2,YU H u i q u n1a n dYU EY i m i n g11D e p a r t m e n to fC o m p u t e rS c i e n c ea n dE n g i n e e r i n g,E a s tC h i n aU n i v e r s i t yo fS c i e n c ea n dT e c h n o l o g y,S h a n g h a i 2 0 0 2 3 7,C h i n a2S h a n g h a iK e yL a b o r a t o r yo fC o m p u t e rS o f t w a r eE v a l u a t i n ga n dT e s t i n g,S h a n g h a i 2 0 0 2 3 7,C h i n a A b s t r a c t W i t ht h ea d v e n to f t h e I n t e r n e t o f e v e r y t h i n ga n d t h e 5 Ge r a,t h e a m o u n t o f d a t a t h a tm o b i l eu s e r sn e e d t op r o c e s sd o e sn o tm a t c ht h e i rd a t ap r o c e s s i n gc a p a b i l i t i e s,o f f l o a d i n ga l a r g en u m b e ro f t a s k st ol i m i t e de d g es e r v e r sf o re x e c u t i o ni sb o u n dt op r o d u c ec o m p e t i t i o n.T h e i n t r o d u c t i o no fa u c t i o nm o d e l c a ns o l v et h ep r o b l e mo fr e s o u r c ec o m p e t i t i o na m o n gu s e r s.A tp r e s e n t,m o s t t a s ko f f l o a d i n gw o r k sb a s e do na u c t i o n i g n o r e t h ed e a d l i n ep e r c e p t i o no f t a s k s,t h eg e n e r a l t a s ko f f l o a d i n gw o r ko n l yc o n s i-d e r sd e l a y-s e n s i t i v e t a s k s,a n dd o e sn o t c o n s i d e r e n s u r i n g t h e s e c u r i t yo f t h eo f f l o a d i n gp r o c e s s.T h e r e f o r e,a na u c t i o nb a s e dd e a d-l i n e-a w a r e t a s ko f f l o a d i n g(A B D T O)s t r a t e g y i sp r o p o s e d,w h i c hu s e st h ea u c t i o nm e c h a n i s mb a s e do ns m a r tc o n t r a c tt or e a l i z et h eo p t i m a l a l l o c a t i o no fd e a d l i n e-a w a r et a s k s(d e l a y-s e n s i t i v et a s k sa n dn o n-d e l a y-s e n s i t i v et a s k s)t ot h ee d g es e r-v e r s,a n dt h et o t a lu t i l i t y(i.e.t o t a l p r o f i t)i s t a k e na s t h e e v a l u a t i o n c r i t e r i o n t oa c h i e v e aw i n-w i ns i t u a t i o nb e t w e e nm o b i l eu s e r s a n de d g e s e r-v e r s.T h eh e u r i s t i cg e n e t i ca l g o r i t h mi su s e dt oc o n d u c ts i m u l a t i o ne x p e r i m e n t s.C o m p a r e dw i t hTA C D,U P P E Ra n dR N Da l g o-r i t h m s,A B D T Os t r a t e g yh a sh i g h e ro v e r a l lu t i l i t y.F i n a l l y,u s i n gR e m i x,G a n a c h e,e t c.t oe s t a b l i s ht h eE t h e r e u mp r i v a t eb l o c k-c h a i nn e t w o r kf o rs i m u l a t i o n,w h i c hp r o v e s t h ec o r r e c t n e s sa n df e a s i b i l i t yo f t h es t r a t e g y.K e y w o r d s E d g ec l o u d,A u c t i o nm e c h a n i s m,D e a d l i n ea w a r e,T a s ko f f l o a d i n g,S m a r t c o n t r a c t 1 引言随着万物互联以及5 G高带宽、低时延时代的到来,数据量呈爆炸式增长,给计算设施带来了实时性、网络依赖性和安全性等方面的要求1。边缘云作为中心云的延伸被提出,其将云的部分服务和能力扩展到边缘基础设施之上,显著减少了延迟和网络负载。然而,边缘云的资源有限导致用户之间势必产生竞争,拍卖是解决资源分配问题的重要手段。买卖双方可以自由地对资源进行估价,并最终就资源的支付达成协议。拍卖过程也可能出现买卖双方恶意串通的行为,可以利用区块链将拍卖信息存储在区块中保证拍卖过程的安全性。区块链2.0中引入了智能合约2,智能合约运行于分布式区块链系统之上,具有其他一切分布式系统的优势,使数据安全和高可用性得到了很好的保证3-4。利用智能合约技术实现拍卖过程,减少拍卖的管理成本5-6。本文针对边缘云环境提出了基于拍卖的期限感知任务卸载(A B D T O)策略,在拍卖中考虑买方延迟敏感型任务(硬期限任务)和非延迟敏感型任务(软期限任务)的卸载,设置任务优先级,提高硬期限任务的获胜机率,优先完成硬期限任务,兼顾软期限任务。同时考虑了参与拍卖任务的最大可容忍延迟,当预计卸载执行时间超过该值时,则自动放弃此次拍卖等待下轮拍卖,或者直接在本地执行。A B D T O策略最大限度地满足了期限感知任务的卸载,实现了拍卖参与者的最大效用。本文的主要贡献如下:(1)建立考虑期限感知的双拍卖模型,实现买方任务到卖方边缘服务器的卸载,旨在使期限范围内拍卖参与者达到最高的效用和利润。(2)提出了基于拍卖的期限感知任务卸载(A B D T O)策略。将任务分为高优先级、低优先级队列,通过影响买方获胜机率,来解决具有不同期限的任务卸载问题。(3)将拍卖部署于智能合约,保证了过程的安全性和卸载结果的真实性,将以太坊平台作为仿真实验环境模拟智能合约作为拍卖商的拍卖活动。2 相关工作近年来,边缘云环境中旨在减少成本能耗时间等的任务卸载工作研究颇丰。G a o等7建立了移动边缘计算环境中深度神经网络计算任务卸载的时间和能耗评价模型。W e i等8在多个移动用户将任务上传到服务器中,提出了任务可分的移动设备节能优选问题,提出了一种选择最大节约能量优先算法来实现求解问题。Y u等9通过考虑完成时间和能量,将移动边缘计算的计算卸载问题转化为系统成本最小化问题。S u n等1 0研究了多用户、多服务器车辆边缘计算场景中的任务卸载算法,有效地优化了任务延迟和计算资源消耗。针对任务延迟的调度问题也有大量相关研究。C h a k r o u n等1 1提出了一种基于L y a p u n o v优化的随机网络优化方法来优化移动云计算(M o b i l eC l o u dC o m p u t i n g)资源分配的方法。S a r k a r等1 2提出了一种截止时间感知的动态任务放置方法(D e a d l i n e-a w a r eD y n a m i cT a s kP l