Task Offloading Scheme Based on Comprehensive Trust Evaluation in Edge Computing

XIONG Xiao-feng, HUANG Chun-lan, YUE Guang-xue, DAI Ya-sheng, YANG Xiao-hui, YANG Zhong-ming

ACTA ELECTRONICA SINICA ›› 2022, Vol. 50 ›› Issue (9) : 2134-2145.

PDF(3822 KB)
CIE Homepage  |  Join CIE  |  Login CIE  |  中文 
PDF(3822 KB)
ACTA ELECTRONICA SINICA ›› 2022, Vol. 50 ›› Issue (9) : 2134-2145. DOI: 10.12263/DZXB.20210296
PAPERS

Task Offloading Scheme Based on Comprehensive Trust Evaluation in Edge Computing

Author information +

HeighLight

In edge computing, waste of resources and inefficient offloading services are key issues caused by bad behaviors such as false deception and free-riding. To address the selfishness key issues, a task offloading scheme based on comprehensive trust evaluation(TOCTE) is proposed. By establishing nodes trust forgetting function, and taking task authenticity and nodes offloading cooperative behavior characteristics as constraints, the offloading request and cooperative trust evaluation models between nodes are constructed to identify and filter false tasks and bad cooperative nodes in the network. Particle swarm algorithm based on search discovery probability is designed to avoid the node overload caused by the repeatedly utilization of nodes, improve task offloading efficiency and resource utilization of edge computing. The simulation results show that the real task execution success rate and the lowest resource consumption rate of TOCTE are 59.22% and 6.35%. TOCTE model can effectively suppress and filter false tasks, and reduce resource consumption.

Cite this article

Download Citations
XIONG Xiao-feng , HUANG Chun-lan , YUE Guang-xue , DAI Ya-sheng , YANG Xiao-hui , YANG Zhong-ming. Task Offloading Scheme Based on Comprehensive Trust Evaluation in Edge Computing[J]. ACTA ELECTONICA SINICA, 2022, 50(9): 2134-2145. https://doi.org/10.12263/DZXB.20210296

1 引言

边缘计算将计算、存储等资源下沉到网络边缘侧,以“就地就近”的服务模式,实现低延迟、低能耗、隐私保护等,提高了网络QoS(Quality of Service)和综合效用. 任务卸载是边缘计算的关键技术之一,主要解决边缘计算中任务是否卸载、任务划分和资源分配这三大问题12,实现网络资源融合与共享.
由于搭便车、自私、理性、恶意等不良节点的普遍存在,极易引起On-off攻击等不良行为3,抢占和消耗边缘计算资源,部分节点因资源被过度消耗“致死”,导致卸载任务堆积、执行失败,边缘计算网络QoS下降.
为抑制任务卸载过程中节点虚假欺骗、服务不可靠等不良行为,文献[4]提出了基于社交信任网络的服务器分配策略,提高游戏视频流服务;文献[5]以时间可信、行为可信、资源可信为约束,构建服务质量可信模型,解决大规模部署边缘节点引起的低效率选择问题;文献[6]基于用户个性化的多维需求,评估盟员卸载优先级,实现协同服务异常时的调度卸载;文献[7]结合用户的心理结构,提出一种面向信任的合作伙伴选择机制;文献[8]构建基于综合信任保障的边缘计算模型,为任务卸载服务请求者和资源提供者进行身份、行为和服务能力定量评价,提出一种移动资源感知调度算法,以计算、存储和通信资源为约束,寻找节点进行协同服务.
依据文献[8],针对任务卸载服务请求者和资源提供者可信问题,提出一种基于综合信任评价的任务卸载策略. 基于节点行为的时间关联属性,建立节点信任遗忘函数和节点行为奖惩算子,构建节点信任评价机制;分析节点任务卸载真实特征属性,建立卸载请求行为评价模型;分析节点资源余量及卸载交互行为,建立卸载协作综合评价模型,筛选并构建可信的卸载协作候选节点集,设计基于搜索发现概率的粒子群(Particle Swarm Based On Search Discovery Probability, PS-SDP)算法求解最佳协作节点,实现计算任务的可靠卸载服务. 通过仿真实验验证了模型可行性,能够有效抑制边缘计算中虚假任务卸载造成的无效时间和资源开销,提高资源有效利用.

2 基于综合信任评价的任务卸载策略

设边缘计算由边缘云服务器、超级节点(Super Node, SN)和边缘节点(Edge Node, EN)构成,以SN为中心形成边缘计算簇, SN规模为Xsn=1,2,,m,EN规模为Xien=1,2,,ni,如图1所示. 以SN节点为桥梁实现边缘计算簇间资源聚合与共享,提供任务卸载协同服务;构建卸载请求、协作行为评价模型,过滤虚假卸载任务请求,遴选最佳协作节点,以一对多模式卸载计算任务,获得高效可靠的卸载协同服务,其可信任务卸载协同服务框架如图2所示.
图1 边缘协同服务模型

Full size|PPT slide

图2 边缘协同服务可信卸载框架

Full size|PPT slide

任务卸载是一个具有时间关联性动态决策过程,边缘计算节点信任特征具有时间衰减属性. 基于Ebbinghaus9人类大脑记忆遗忘理论,构建边缘计算节点信任记忆保持量关于时间t的衰减函数ft
ft=1αlnβt+1+1,α>0,β>0
(1)
其中,实验中取值α=0.3574β=531.7,记忆衰减曲线如图3所示.
图3 记忆保持衰减曲线示意图

Full size|PPT slide

将每个观察期时长分成tk个时间片,基于式(1),构建边缘计算节点历史信任遗忘函数:
λ=fσtkTs+Δs=λΔsTs,Δs0
(2)
其中,Ts表示第s观察期的信任度,Δs表示观察周期间隔数,σ表示遗忘因子,λ表示历史信任的保持率.

2.1 卸载请求行为评价模型

边缘计算簇间的卸载请求行为评价模型如图4所示. SN节点根据任务真实性计算卸载源节点的卸载请求信任度,判定合作关系,过滤虚假任务,执行卸载服务.
图4 卸载请求行为评价模型

Full size|PPT slide

设第s观察期间边缘计算簇i(以SN节点i为中心)中,存在节点j卸载的真实任务和虚假任务数分别为nijtruesnijfalses. 根据簇内任务执行情况,计算SN节点j的任务真实率pijtrues为:
pijtrues=nijtrues+η1nijtrues+nijfalses+η2,s.t.1η1<η2,η22,s1
(3)
式(3)η1η2分别取值为1和2,当簇内未执行节点j任务时,赋予节点中性值0.5.
为抑制非合作节点制造、卸载虚假任务等不良行为,提高合作节点信任置信度,构建节点卸载请求行为奖惩算子φ110
φ1=nijfalsesnijtrues+nijfalses2+nijtrues+nijfalses+η,η1
(4)
其中,η取值为1.
引入历史信任遗忘函数,计算经s个观察周期后,节点j的卸载请求信任Tijreqs11
Tijtrues=1+φ1pijtrues-φ11-pijtruesTijreqs=λTijreqs-1+1-λTijtrues
(5)
其中,Tijtrues表示第s观察期间节点i对节点j的真实任务信任度.

2.2 卸载协作综合评价模型

依据行为信任,将EN节点分为可靠节点、激励节点和不良节点三类7:(1)可靠节点:卸载协作行为可信,成功率较高的节点;(2)激励节点:初期卸载协作服务能力较差,通过激励调动服务积极性的节点;(3)不良节点:长期以消极服务态度提供协作服务的节点.
以节点资源信任和行为信任,构建卸载协作综合评价模型,如图5所示. SN节点结合当前剩余资源和行为信任计算节点卸载协作信任,判定节点信任关系,构建可信的卸载协作候选节点集,甄选最佳协作节点执行卸载服务. 若节点行为信任低于中性值γ,则生成一组测试任务集由该节点执行,实施激励,再次更新其行为信任.
图5 卸载协作综合评价模型

Full size|PPT slide

2.2.1 资源信任评价模型

边缘计算中资源的合理利用有利于边缘计算任务卸载协同服务的良性运行. 设节点最大负载率为ρ,计算节点i执行任务r的资源信任度Tires
Tires=ci-crmi-mr+1CiMi+1s.t.ci-crCi>1-ρmi-mrMi>1-ρ
(6)
其中,CiMi表示节点i可提供的计算和存储资源,cimi表示节点i的当前剩余计算和存储资源,crmr表示任务r执行所需的计算和存储资源. Tires 值大于1-ρ2时,节点i可供资源消耗殆尽,出现过载现象.
为避免拥塞、抖动等影响网络稳定性,任务的卸载与执行在同一观察期内完成. 设节点i在线时长为tion,计算执行任务r后的剩余在线时长tirem
tirem=ci-crtionCi
(7)
模型约束条件为:
s.t.tispe+tirem+craiexe>tcyctispe+craiexe<tcyc
(8)
其中,tcyc表示观察期时长,aiexe表示节点i计算能力,tispe表示观察期内执行任务r前的已耗时间.

2.2.2 行为信任评价模型

边缘计算簇内,以节点的任务执行效率和成功率为约束,构建节点行为信任模型.
EN节点j的任务执行效率Tjab计算公式如下:
Tjab=e- 1ajexe
(9)
已知第s观察期内,簇内节点j接受的任务数为nijaccs,接受且成功执行的任务数为nijsucs,任务执行成功率pijsucs计算公式如下:
pijsucs=nijsucs+η1nijaccs+η2,1η1<η2,η22
(10)
式(10),当节点在观察期内未接受任务时,赋予节点中性值0.5.
为抑制簇内EN节点不良行为,激励节点诚信服务,设置节点卸载协作行为奖惩算子φ210
φ2=nijaccs-nijsucsnijaccs2+nijaccs+η,η1
(11)
计算第s观察期内节点j的任务执行信任Tijsucs11
Tijsucs=ω1+φ2pijsucs-φ21-pijsucs+1-ωnijsucsnijoffs,nijoffs>01+φ2pijsucs-φ21-pijsucs,                                      nijoffs=0
(12)
其中,ω表示任务执行成功率所占权重,nijoffs表示第s观察期内节点i向节点j卸载的任务数.
结合节点任务执行效率和执行信任,计算第s观察期内节点j的行为信任Tijexe-rs
Tijexe-rs=TijsucsTjab
(13)
引入历史信任遗忘函数,计算经过s个观察周期后,节点i对节点j的行为信任Tijexes
Tijexes=λTijexes-1+1-λTijexe-rs,s1
(14)

2.2.3 综合信任决策模型

综合资源信任和行为信任,构建卸载协作信任Tijcoop
Tijcoop=TjresTijexes
(15)
式(15)求得EN节点卸载协作信任,筛选得到卸载协作候选节点集Xico=1,2,,ni. 将卸载协作节点择优问题转化为卸载协作信任最大化的目标优化问题,以节点集Xico为解空间,设计PS-SDP算法求解.
式(8)式(15)得到SN节点i中任务r的卸载协作节点寻优目标及约束条件如下:
maxTixicoopxiXicos.t.cxi-crCxi>1-ρmxi-mrMxi>1-ρtxispe+txirem+craxiexe>tcyctxispe+craxiexe<tcyci1,2,,m,Xico=1,2,,ni
(16)
PS-SDP算法利用粒子群优化(Particle Swarm Optimization, PSO)算法12求解最佳协作节点. 每一个粒子代表解空间中协作节点寻优的一个的潜在解,学习自身和其他成员经验以适应自身搜索模式. 飞行速度受个体最佳信任节点xlpb和群体最佳信任节点xgb影响,粒子l在搜索空间的飞行速度vl和候选节点xlXico更新公式如下:
vl(τ)=wvl(τ-1)+c1ξxlpb(τ-1)-xl(τ-1)+c2ξxgb(τ-1)-xl(τ-1)xl(τ)=xl(τ-1)+vl(τ)w=wmax-wmax-wminτG
(17)
其中,ξ在(0,1)范围内随机取值,vl(τ)xl(τ)分别表示粒子lτ次迭代更新后的速度和候选节点,xlpb(τ)xgb(τ)分别表示τ次迭代后粒子l和整个粒子群的最佳信任节点,c1c2表示粒子自身和群体的学习因子,w表示惯性因子,wmaxwmin分别表示惯性因子最大和最小值,G为算法最大迭代次数.
为抑制算法寻优陷入局部最优,融合布谷鸟搜索算法13(Cuckoo Search, CS),引入搜索发现概率p0,1,实现解域概率取值,以规避局部最优,使求解结果趋于全局最优,获取任务卸载的最佳协作节点,其算法流程如图6所示. 设置任务最大拒绝次数,避免任务多次卸载被拒产生过多延迟开销,利用PS-SDP算法寻找最佳协作节点获得卸载服务.
图6 簇内协作节点寻优流程

Full size|PPT slide

2.3 任务卸载策略建模

任务卸载协同服务工作原理:边缘计算簇中,SN节点收到任务卸载请求时,启动任务过滤机制,依据任务真实特征信息,计算任务卸载源节点的卸载请求信任,识别节点合作性,过滤非合作节点的虚假任务;启动卸载服务决策机制,依据簇内EN节点卸载协作信任,构建可信的卸载协作候选节点集,应用PS-SDP算法遴选最佳协作节点,并发起卸载请求,完成卸载协同服务. 在基于卸载请求行为评价模型的任务过滤机制和基于卸载协作综合评价模型的卸载服务决策机制中,SN节点的状态变化及服务流程如下.
(1)根据式(5),将SN节点的任务过滤形式化描述为Dreq=Q1,Γ1,δ1,q11,F1的状态图,如图7所示,其中,Q1=q11,q12,q13,q14,q15,q16,q17,q18,q19为有穷状态集,任务状态描述如表1所示.Γ1为状态转移条件产生式;δ1为状态转移函数,Q1×Γ1=Q1q11Q1,为起始状态;F1Q1,为结束状态集,F1=q19.
图7 SN节点任务过滤状态图

Full size|PPT slide

表1 节点任务过滤状态说明

任务

状态

状态描述:

任务

状态

状态描述:
q11 服务等待状态 q16 簇内信息接收状态
q12 节点关系识别状态 q17 任务特征信息更新状态
q13 卸载请求接受状态 q18 卸载请求信任更新状态
q14 卸载请求拒绝状态 q19 结束状态
q15 簇内任务卸载状态
流程1 任务过滤
Step1:设置SN节点i卸载请求信任阈值Tminreq.
Step2:等待并收到节点j的任务卸载请求,判定SN节点i与任务卸载源节点j的合作关系. 若Tijreq<Tminreqij,i,jm,则节点j为非合作节点,节点i拒绝节点j的任务卸载请求,转Step4. 否则执行任务卸载服务.
Step3:启动卸载服务决策机制,遴选最佳协作节点. 协作节点执行任务并反馈任务真实性,SN节点依据反馈结果更新任务真实特征信息.
Step4:卸载请求信任更新. 若观察期结束,根据任务真实特征信息,结合历史信任关系,更新各SN节点的卸载请求信任.
Step5:测试是否结束?是,结束;否则,转Step2.
(2)根据式(15)式(16),将SN节点的卸载服务决策形式化描述为Dcoop=Q2,Γ2,δ2,q21,F2的状态图,如图8所示. 其中,Q2=q21,q22,q23,q24,q25,q26,q27,q28,q29为有穷状态集,任务状态描述如表2所示.Γ2为状态转移条件产生式;δ2为状态转移函数,Q2×Γ2=Q2q21Q2,为起始状态;F2Q2,为结束状态集,F2=q29.
图8 SN节点卸载协作状态图

Full size|PPT slide

表2 节点卸载服务决策状态说明

任务

状态

状态描述:

任务

状态

状态描述:
q21 服务等待状态 q26 任务卸载状态
q22 卸载协作信任更新状态 q27 节点特征信息更新状态
q23 信任关系判别状态 q28 行为信任更新状态
q24 协作节点选择状态 q29 结束状态
q25 卸载协商状态
流程2 卸载服务决策
Step1:设置SN节点i卸载协作信任阈值Tmincoop和任务最大拒绝次数nmaxrej.
Step2:根据资源特征信息,更新EN节点资源信任,联合行为信任计算卸载协作信任Tijcoops;判定节点信任关系,若TijcoopsTmincoopim,jn,则EN节点j协同服务可信,划入卸载协作候选节点集.
Step3:若任务拒绝次数nijrejnmaxrej,运用PS-SDP算法,在卸载协作候选节点集中寻找最佳协作节点并发起卸载请求;否则,将任务卸载至其他边缘计算簇.
Step4:与协作节点卸载协商并更新节点行为特征信息,若请求接受,完成任务卸载;否则,转Step3.
Step5:若观察期结束,根据行为特征信息和历史信任关系,更新簇内EN节点行为信任.
Step6:测试是否结束?是,结束;否则,转Step2.
综合任务过滤和卸载服务决策机制,边缘计算簇协同服务过程如图9所示.
图9 TOCTE卸载协同服务

Full size|PPT slide

流程3 任务卸载协同服务过程
Step1:SN节点等待并收到任务卸载请求,创建任务特征数据库.
Step2:根据任务真实特征数据,更新任务卸载源节点的合作关系数据,识别、过滤非合作节点的虚假任务.
Step3:根据任务和节点特征数据,计算簇内EN节点资源信任,结合行为信任数据,更新节点卸载协作信任数据库,构建卸载协作候选节点集.
Step4:运用PS-SDP算法,以卸载协作信任最大化为目标,遴选最佳协作节点并发起卸载请求.
Step5:簇内EN节点执行卸载协同服务并返回服务结果,将任务真实特征信息反馈给SN节点,更新任务和节点特征数据库.
Step6:根据任务和节点特征数据,更新SN节点的卸载请求信任、簇内EN节点的行为信任数据.
将任务的一次卸载协同服务过程形式化描述为DTOCTE=Q,Γ,δ,q1,F状态图,如图10所示,其中,Q=q1,q2,q3,q4,q5,q6,q7,q8,q9,q10为有穷状态集,任务状态描述如表3所示.Γ为状态转移条件产生式;δ为状态转移函数,Q×ΓQq1Q,为起始状态;FQ,为结束状态集,F=q10.
图10 任务卸载执行状态图

Full size|PPT slide

表3 任务状态说明

任务

状态

状态描述:

任务

状态

状态描述:
q1 簇间卸载抉择状态 q6 簇内卸载执行状态
q2 簇间卸载等待状态 q7 任务执行状态
q3 簇间卸载执行状态 q8 任务完成状态
q4 簇内卸载抉择状态 q9 任务失败状态
q5 簇内卸载等待状态 q10 结束状态

3 实验分析

3.1 实验设置

以云服务器为根节点,基站或边缘服务器为SN节点,智能终端设备为EN节点,SN节点与根节点构建云边协同骨干网络,SN节点与EN节点构建边缘计算网络. 作如下假设:
(1)在边缘计算网络中,SN节点聚合EN节点构建边缘计算簇,每个簇包含1个SN节点,簇规模一致,仿真实验网络环境设置如表4所示.
表4 网络环境设置
测试组编号 网络规模 云服务器 SN节点数 边缘计算簇数 EN节点数 簇规模
1 5051 1 50 50 100 101
2 7071 1 70 70 100 101
3 10101 1 100 100 100 101
4 12121 1 120 120 100 101
5 15151 1 150 150 100 101
6 20201 1 200 200 100 101
(2)边缘计算中存在30%的SN节点为非合作节点;单位时间片内卸载请求任务数遵循泊松分布;同一时间片相邻任务间的服务等待和节点卸载协商产生的时间开销忽略不计.
(3)边缘计算簇内,可靠、激励和不良三类EN节点数目比例为6:2:2;任务可在EN节点堆积,但均在观察期内完成,不滞留至下一观察期.
(4)模型中随机参数取值服从正态分布,具体参数设置见表5.
表5 参数设置
参数 数值
任务计算量ct 1~4 MB
任务所需内存mt 1~4 MB
EN工作计算能力aiexe 4~8 MB/s
EN在线时长tion 0.5~1 h
EN可执行任务量Ci 300~500 MB
EN可提供内存Mi 100~500 MB
观察周期tcyc 360 s
时间片数tk 360
最大负载率ρ 0.8
任务执行成功率权重ω 0.8

3.2 评价指标

为验证卸载策略的性能效用,分别对簇间卸载、簇内卸载的信任评价模型以及策略的卸载综合效用的性能指标加以描述,如表6所示.
表6 性能评价指标
分析对象 评价指标 描述
卸载请求行为评价模型 非合作节点识别率 观察周期内,SN节点识别的非合作节点数与边缘计算中SN节点总数的比值;
非合作节点识别准确率 观察周期内,SN节点识别的非合作节点中,身份无误的节点数与节点总数的比值;
卸载请求拒绝率 观察周期内,SN节点拒绝的任务数与接收到的卸载请求任务数的比值;
卸载请求拒绝准确率 观察周期内,SN节点拒绝的任务中,虚假任务数与总任务数的比值;
资源有效利用率 观察周期内,SN节点接受的任务中,来自合作节点的任务数与总任务数的比值;
卸载协作综合评价模型 在线时长 观察周期内,簇内最短EN节点剩余在线时长;
任务卸载率 观察周期内,边缘计算簇接受的任务中,卸载至其他簇的任务数与总任务数的比值;
任务执行失败率 观察周期内,边缘计算簇接受且执行的任务中,执行失败的任务数与总任务数的比值;
任务拒绝次数 观察周期内,边缘计算簇中 各EN节点拒绝任务卸载请求次数的总和;
卸载综合效用 真实任务执行成功率 观察周期内,边缘计算簇接受的任务中,真实且被成功执行的任务数与总任务数的比值
资源损耗率 观察周期内,边缘计算中虚假任务执行消耗的资源与各EN节点提供的资源总和的比值;

3.3 实验分析

为检验TOCTE策略的卸载协同服务优化效果,分别从卸载请求行为评价模型性能、卸载协作综合评价模型性能以及卸载综合效用,分析TOCTE策略的虚假任务过滤有效性和卸载服务可靠性.

3.3.1 卸载请求行为评价模型

为测试TOCTE策略中卸载请求行为评价模型的性能效用,根据非合作节点识别率和识别准确率、卸载请求拒绝率和拒绝准确率、资源有效利用率等指标,在测试组3的网络环境下,将TOCTE策略中的任务过滤机制与任务随机接受(random accept)策略14对比分析.
图11~图13分别描述了TOCTE策略的卸载请求行为评价模型的不同信任阈值,对于边缘计算簇的非合作节点识别、虚假任务过滤和资源利用的影响. 从图中发现,随着SN节点信任阈值的增大,边缘计算中的非合作节点逐渐被识别出来,非合作节点识别率、卸载请求拒绝率和资源有效利用率提高; 信任阈值小于0.4时,非合作节点识别和任务卸载请求拒绝准确率均为100%;大于0.4时,信任度较低的合作节点无法满足信任需求,被误判为非合作节点,准确率开始降低;卸载请求信任阈值为0.5时,任务过滤效果最佳,非合作节点识别率达到28%,识别准确率最低为95.83%,卸载请求拒绝率达到32.84%,拒绝准确率最低为88.36%,资源有效利用率最高达到81.52%.
图11 不同信任阈值下非合作节点识别情况

Full size|PPT slide

图12 不同信任阈值下虚假任务过滤情况

Full size|PPT slide

图13 不同信任阈值下资源

Full size|PPT slide

由于Random Accept 策略在SN节点接收到任务卸载请求后,不考虑任务来源可靠性,随机接受该请求,不具有非合作节点识别能力. 图14描述了最佳信任阈值下,TOCTE策略与Random Accept策略对于资源有效利用率的影响. 从图中发现,Random Accept策略的资源有效利用率在水平线上下波动,TOCTE策略资源有效利用率逐渐提高并最终趋于稳定,平均资源有效利用率为78.60%,较Random Accept策略提高9.48%.
图14 不同策略下资源有效利用率           有效利用率变化

Full size|PPT slide

15~17分别描述了不同网络规模下,TOCTE策略的卸载请求行为评价模型对于边缘计算中非合作节点识别、虚假任务过滤和资源利用的影响. 从图中发现,边缘计算中边缘计算簇数目越多,非合作节点识别率和卸载请求拒绝率越高;边缘计算簇数小于70时,非合作节点识别准确率和任务卸载请求拒绝准确率均为100%,大于70时,随网络规模的增大,边缘计算环境愈加复杂,准确率和资源有效利用率降低. 边缘计算簇数为70时,策略的任务过滤效果最佳,非合作节点识别率达到22.86%,卸载请求拒绝率达到22.93%,非合作节点识别和卸载请求拒绝准确率均为100%,资源有效利用率达到82.34%.
图15 不同网络规模下非合作节点识别情况

Full size|PPT slide

图16 不同网络规模下虚假任务过滤情况

Full size|PPT slide

图17 不同网络规模下资源有效利用率

Full size|PPT slide

综上所述, TOCTE策略不仅能有效识别并拦截非合作节点的不良行为,保证任务来源的可靠性,同时提高了资源的有效利用.

3.3.2 卸载协作综合评价模型

为测试TOCTE策略中卸载协作综合评价模型的性能效用,在测试组3的网络环境下构建任务趋优卸载(Task Optimal Offloading, TOO)策略,将边缘计算簇下的EN节点以信任(以任务执行成功率表示)划分节点集,如表7所示. 设置每个节点集任务最大卸载次数,在满足任务需求的条件下,将任务优先卸载至优节点集中的节点,若任务卸载次数超过该节点集的最大卸载次数,则考虑良节点集中的节点,以此类推,直至找到协作节点执行卸载服务. 若四类节点集均被搜索但仍未找到协作节点,则将任务卸载至其他簇.
表7 节点集划分
节点集 优节点集 良节点集 一般节点集 差节点集
信任范围 0.9~1 0.75~0.9 0.6~0.75 0~0.6
根据边缘计算簇在线时长、任务执行失败率和卸载率等指标, 将TOCTE策略与基于Random Walk14、按需路由协议(Ad hoc On-Demand Distance Vector Routing, AODV)15的随机卸载策略和TOO策略对比分析,设置实验对照.
(1)Random Walk策略:随机选择EN节点卸载,并由EN节点判断自身资源是否满足任务需求.
(2)AODV策略:满足任务需求情况下,随机选择EN节点卸载.
(3)TOO策略:满足任务需求情况下,趋优选择EN 节点卸载.
图18描述了TOCTE策略的卸载协作综合评价模型的不同信任阈值,对于边缘计算簇在线时长和任务卸载率的影响. 从图中发现,随信任阈值的增大,簇内可信协作节点和执行任务数减少,在线时长和任务卸载率逐渐提升;信任阈值为0.6时,信任阈值过高导致SN节点未找到协作节点,任务均向其他簇卸载,在线时长和卸载率保持18299.83 s和100%不变,该簇不再具备存在价值,同时增加了其他簇的计算负载和任务延迟开销.
图18 不同的信任阈值对比分析

Full size|PPT slide

为了延长边缘计算簇在线时长的同时,提供高效卸载服务,应合理设置卸载协作信任阈值.
图19表8呈现了Random Walk策略、AODV策略、TOO策略和TOCTE策略,对于边缘计算簇在线时长、任务卸载率、任务执行失败率、任务拒绝次数和决策时长的影响. 从图表中发现,与其他三种策略相比,TOCTE策略以决策时长和任务向簇外卸载为代价,有效延长了147.49%、146.65%和156.76%在线时长,降低了33.84%、33.84%和29.26%任务执行失败率;节点间卸载协商产生的时间开销由任务拒绝次数衡量, TOCTE策略将平均拒绝次数减少至831次,与其他三种策略相比,分别减少了35.48%、21.53%和52.92%,有效降低了任务多次卸载决策产生的时间开销.
图19 卸载策略对比

Full size|PPT slide

表8 卸载策略效果对比
算法 平均决策时长/s 平均拒绝次数 平均在线时长/s 平均任务卸载率 平均任务执行失败率
Random Walk 0.5202 1288 3765.42 0.0485 0.5852
AODV 0.5545 1059 3778.28 0.0487 0.5851
TOO 0.6007 1765 3629.58 0.0083 0.5394
TOCTE 1.9344 831 9319.17 0.2659 0.2468
为检验TOCTE策略下,不同协作节点寻优算法对卸载决策的优化效果,将PS-SDP算法与PSO算法12、CS算法13和基于模拟退火Metropolis准则的粒子群(Particle Swarm based on Simulated Annealing Metropolis Criterion, PS-SA)算法1216进行对比分析. 设置实验对照组.
(1)PSO算法:解空间以粒子群的形式存在,协作和信息共享的方式寻找最佳协作节点.
(2)CS算法:解空间以寄主巢群的形式存在,Lévy flights搜索方式寻找最佳协作节点.
(3)PS-SA算法:解空间以粒子群的形式存在,协作和信息共享的方式寻找最佳协作节点,并利用模拟退火的Metropolis准则确定粒子候选节点.
图20表9呈现了不同协作节点寻优算法,对于激励和可靠节点行为信任变化、任务执行失败率变化、卸载决策时长的影响. 从图表中发现,相较于其他三种寻优算法,PS-SDP算法在激励节点和可靠节点行为信任变化上收敛速度更快、信任度更高,稳定状态下平均信任度分别达到0.766和0.693;从时间复杂度分析,PS-SDP算法以搜索发现概率接受新解,增加一定的时间复杂度,但仅次于PSO算法;从任务执行失败率分析, PS-SDP算法平均执行失败率达到23.98%,与其他算法比,分别降低了0.99%、0.62%、0.27%,任务卸载服务质量较优.
图20 协作节点寻优算法对比

Full size|PPT slide

表9 协作节点寻优算法决策时长对比 (s)

搜索

算法

实验1 实验2 实验3 实验4 实验5

平均

时长

单位周

期时长

PSO 1568.6 1568.7 1554.5 1552.2 1477.6 1544.3 1.544
CS 2915.8 2864.4 2878.9 2858.1 2776.9 2858.8 2.859
PS-SA 3852.2 3684.7 3723.3 3770.5 3621.3 3730.4 3.730
PS-SDP 2737.3 2598.5 2628.3 2643.7 2567.9 2635.1 2.635
对于卸载可靠性要求较高的计算任务,以PS-SDP算法寻找协作节点,卸载服务更为可靠.

3.3.3 卸载综合效用

为检验TOCTE策略的卸载综合效用,根据边缘计算簇真实任务执行成功率和资源损耗率,在测试组3的网络环境下,将TOCTE策略与AODV策略、TOO策略、任务可信卸载(Task Credible Offloading, TCO)策略、基于任务可信的任务趋优卸载(Task Optimal Offloading based on Task Credible, TOO-TC)策略和协作节点可信卸载(Cooperative Node Credible Offloading, CNCO)策略对比分析,设置实验对照组.
(1)AODV随机卸载策略:SN节点直接接受任务卸载请求,基于AODV随机选择EN节点执行卸载服务.
(2)TOO策略:SN节点直接接受任务卸载请求,趋优选择EN节点执行卸载服务.
(3)TCO策略:SN节点利用卸载请求行为评价模型评估源节点的卸载请求行为,过滤虚假任务,随机选择EN节点执行卸载服务.
(4)TOO-TC策略:SN节点利用卸载请求行为评价模型评估任务卸载源节点的卸载请求行为,过滤虚假任务,趋优选择EN节点执行卸载服务.
(5)CNCO策略:SN节点直接接受任务卸载请求,利用卸载协作综合评价模型评估EN节点,遴选最佳协作节点执行卸载服务.
图21图22表10描述了不同卸载策略对于边缘计算簇真实任务执行成功率和资源损耗率的影响. 从图中发现.
图21 真实任务执行成功率

Full size|PPT slide

图22 资源损耗率

Full size|PPT slide

表10 不同策略卸载综合性能对比
性能 真实任务执行成功率 资源损耗率
最高 平均 最低 平均
AODV 0.2804 0.2516 0.1103 0.1276
TOO 0.3086 0.2797 0.1309 0.1546
TOO-TC 0.3668 0.3392 0.09 0.1033
TCO 0.3323 0.3054 0.0828 0.095
CNCO 0.5076 0.458 0.0953 0.1112
TOCTE 0.5922 0.5552 0.0635 0.0753
(1)由AODV和TCO策略、TOO和TOO-TC策略、CNCO和TOCTE策略两两对比,验证了基于卸载请求行为评价的任务过滤机制对系统综合性能优化的有效性,分别提高了5.38%、5.95%和9.72%真实任务执行成功率,降低了3.26%、5.13%和3.59%的资源损耗率.
(2)由AODV和CNCO策略、TCO和TOCTE策略的两两对比,验证了基于卸载协作综合评价的卸载服务决策机制对系统综合性能优化的有效性,分别提高了20.64%和24.98%真实任务执行成功率,降低了1.64%和1.97%资源损耗率.
(3)TOCTE策略的真实任务执行成功率最高为59.22%,平均达到55.52%,较AODV卸载策略高30.36%,较TOO策略高27.55%;资源损耗率最低为6.35%,平均达到7.53%,较AODV策略低5.23%,较TOO策略低7.93%.
实验结果表明,TOCTE策略模型通过基于卸载请求行为评价的任务过滤和基于卸载协作综合评价的卸载决策,在任务执行和资源利用方面明显优于其他对比模型,有效提高了边缘计算簇真实任务执行成功率,降低网络资源损耗.

4 结束语

针对边缘计算任务卸载中任务请求者和资源提供者的可信问题,设计了一种基于综合信任评价的任务卸载策略,建立节点信任遗忘函数和节点行为奖惩算子,构建信任评价机制,衡量节点行为可靠性. 以提高资源利用和卸载服务质量为目标,在边缘计算簇间实现基于卸载请求信任的虚假任务过滤,降低非合作节点不良行为对网络性能的影响;设计卸载协作信任模型,将边缘计算簇内的卸载协作节点择优问题转化为卸载协作信任最大化问题,以基于搜索发现概率的粒子群算法寻找协作节点,实现边缘计算的任务可靠卸载. 仿真结果表明,所提策略不仅解决了任务来源可信问题,同时保证了边缘节点的卸载协同服务质量.
由于智能终端设备资源有限,任务卸载决策存在一定的延迟和能源开销,迁移、强化学习等方法可有效提高卸载决策效率,但终端训练模型将产生大量能耗,需将学习模型部署在边缘服务器,通过模型裁剪、感知压缩等方法下推模型,实现任务的高效卸载、精准预测. 在下一步工作中,我们将研究边缘计算的智能卸载和模型下推等问题.

References

1
施巍松, 张星洲, 王一帆, 等. 边缘计算: 现状与展望[J]. 计算机研究与发展, 2019, 56(1): 69-89.
SHIW S, ZHANGX Z, WANGY F, et al. Edge computing: State-of-the-art and future directions[J]. Journal of Computer Research and Development, 2019, 56(1): 69-89. (in Chinese)
2
李智勇, 王琦, 陈一凡, 等. 车辆边缘计算环境下任务卸载研究综述[J]. 计算机学报, 2021, 44(5): 963-982.
LIZ Y, WANGQ, CHENY F, et al. A survey on task offloading research in vehicular edge computing[J]. Chinese Journal of Computers, 2021, 44(5): 963-982. (in Chinese)
3
蔡绍滨, 韩启龙, 高振国, 等. 基于云模型的无线传感器网络恶意节点识别技术的研究[J]. 电子学报, 2012, 40(11): 2232-2238.
CAIS B, HANQ L, GAOZ G, et al. Research on cloud trust model for malicious node detection in wireless sensor network[J]. Acta Electronica Sinica, 2012, 40(11): 2232-2238. (in Chinese)
4
LINY H, SHENH Y. CloudFog: leveraging fog to extend cloud gaming for thin-client MMOG with high quality of service[J]. IEEE Transactions on Parallel and Distributed Systems, 2017, 28(2): 431-445.
5
王妍, 韩笑, 曾辉, 等. 边缘计算环境下服务质量可信的任务迁移节点选择[J]. 计算机科学, 2020, 47(10): 240-246.
WANGY, HANX, ZENGH, et al. Task migration node selection with reliable service quality in edge computing environment[J]. Computer Science, 2020, 47(10): 240-246. (in Chinese)
6
乐光学, 戴亚盛, 杨晓慧, 等. 边缘计算多约束可信协同任务迁移策略[J]. 电信科学, 2019, 35(11): 36-50.
YUEG X, DAIY S, YANGX H, et al. Multi-constrained trusted cooperative task migration strategy for edge computing[J]. Telecommunications Science, 2019, 35(11): 36-50. (in Chinese)
7
YANJ J, WUD P, SANYALS, et al. Trust-oriented partner selection in D2D cooperative communications[J]. IEEE Access, 2017, 5: 3444-3453.
8
邓晓衡, 关培源, 万志文, 等. 基于综合信任的边缘计算资源协同研究[J]. 计算机研究与发展, 2018, 55(3): 449-477.
DENGX H, GUANP Y, WANZ W, et al. Integrated trust based resource cooperation in edge computing[J]. Journal of Computer Research and Development, 2018, 55(3): 449-477. (in Chinese)
9
赫尔曼·艾宾浩斯.记忆的奥秘[M]. 王迪菲, 译. 北京: 北京理工大学出版社, 2013.
10
王妍, 韩笑, 曾辉, 等. 边缘计算环境下服务质量可信的任务迁移节点选择[J]. 计算机科学, 2020, 47(10): 240-246.
WANGY, HANX, ZENGH, et al. Task migration node selection with reliable service quality in edge computing environment[J]. Computer Science, 2020, 47(10): 240-246. (in Chinese)
11
张磊, 张希, 安成锦, 等. 基于信誉的延迟容忍网络激励方案[J]. 电子学报, 2014, 42(9): 1738-1743.
ZHANGL, ZHANGX, ANC J, et al. A reputation-based incentive scheme for delay tolerant networks[J]. Acta Electronica Sinica, 2014, 42(9): 1738-1743. (in Chinese)
12
KULKARNIR V, VENAYAGAMOORTHYG K. Particle swarm optimization in wireless-sensor networks: A brief survey[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part C(Applications and Reviews), 2011, 41(2): 262-267.
13
YANGX S, DEBS. Cuckoo search: Recent advances and applications[J].Neural Computing and Applications, 2014, 24(1): 169-174.
14
张以文, 汪开斌, 严远亭, 等. 基于覆盖随机游走算法的服务质量预测[J]. 计算机学报, 2018, 41(12): 2756-2768.
ZHANGY W, WANGK B, YANY T, et al. Service quality prediction based on covering random walk algorithm[J]. Chinese Journal of Computers, 2018, 41(12): 2756-2768. (in Chinese)
15
KUMD W, LEA N, CHOY Z, et al. An efficient on-demand routing approach with directional flooding for wireless mesh networks[J]. Journal of Communications and Networks, 2010, 12(1): 67-73.
16
WANGB, XIEH X, XIAX D, et al. A NSGA-II algorithm hybridizing local simulated-annealing operators for a Bi-criteria robust job-shop scheduling problem under scenarios[J]. IEEE Transactions on Fuzzy Systems, 2019, 27(5): 1075-1084.

Funding

National Natural Science Foundation of China(U19B2015)
PDF(3822 KB)

2314

Accesses

0

Citation

Detail

Sections
Recommended

/