随着通信技术与智能终端设备的快速发展和应用普及，流式服务已成为移动网络承载的重要业务之一，对智能终端设备性能提出了更高的要求.受计算能力、存储容量、电池能耗、设计美观等限制，移动智能设备(mobile smart device,MSD)无法完成资源需求大、计算任务重的密集型任务.为解决该问题，资源丰富的云计算模型作为有效方案之一应运而生，并由此已演化出雾计算、边缘计算等先进的计算模式.5G技术的日渐成熟和应用推广，使得无线移动网络承载数据和业务量将以线性增长，流式多元化网络业务和服务的快速增长必将导致网络拥塞、数据丢失等问题，传统的云计算已无法满足终端对高带宽、低时延和实时性的需求[1].

为了解决云计算的不足，新出现的网络计算模式在终端用户附近提供计算资源，并根据应用需求将数据就近处理[2]，如透明计算、cloudlet[3]、边缘计算、雾计算[4]和移动边缘计算等.cloudlet和雾计算的计算能力未集成到移动网络中，导致服务质量降低.移动边缘计算较其他计算模式更侧重于无线接入网络[5]，具有低时延、低能耗等优点.为了降低传输延迟，2014年欧洲电信标准协会提出移动边缘计算(mobile edge computing,MEC)，将延迟敏感的应用程序迁移到距离较近的边缘服务器(edge server,ES)进行计算与存储，并在2016年把MEC的概念扩展为“多接入边缘计算”(multi-access edge computing,MEC)，将MEC从电信蜂窝网络进一步延伸至其他无线接入网络(如WiFi).计算迁移是MEC研究的关键问题之一.终端根据实际应用场景指定不同的卸载策略时需考虑何时迁移、在何处迁移、如何迁移、迁移哪部分等，最终达到能耗与系统性能的平衡，提升用户的服务质量和体验质量.

目前，计算迁移算法性能优化目标主要集中在能耗、时延以及两者的联合优化.

1)以能耗为优化目标.文献[6]研究了基于非正交多址(non-orthogonal multiple access,NOMA)的节能多任务多址MEC，对任务计算卸载、本地计算资源分配和NOMA传输持续时间进行联合优化，以最小化终端完成所有任务的总能耗为目标.文献[7]研究了移动边缘计算迁移面临的可扩展性问题，提出一个轻量级的请求和准入框架解决可伸缩性问题，设计选择性迁移方案，最小化设备能耗.此外，文献[8-11]考虑不同的应用场景和约束，构建相应的优化模型，实现最小化能耗.

2)以时延为优化目标.文献[12]基于无人机群的三维分布构建了一个联合通信与计算优化模型，利用随机几何和排队论，实现了最优响应时延.文献[13]提出了一种低延迟的安全移动边缘计算系统，该系统优化用户的传输功率、计算容量分配和用户关联，在保证安全的资源约束条件下最小化用户计算和传输延迟.

3)以联合优化能耗和延迟为目标.文献[14]研究了物联网边缘云计算系统中的工作负载分配问题，基于时延和能耗约束设计智能算法，实现本地、边缘和云计算服务器的负载均衡.文献[15]定义能耗和时延之间折中的代价函数，提出了一种MEC辅助的计算和中继方案，获得移动设备和中继节点的最佳传输和压缩策略.另外，文献[16-20]针对不同场景下任务迁移的能耗与时延构建系统模型，平衡两者间关系，提升用户体验质量(quality of experience,QoE).文献[21]利用低秩矩阵理论与边缘计算去中心化的计算能力来处理大量交通数据，以实现精确和实时的恢复.

若将密集型任务迁移到一个ES时，当前ES由于达到负载阈值而无法完成，产生新的等待时延.根据分布式计算模式的特点，可将无法完成的任务迁移到相邻空闲的ES上进行计算，通过多个ES协作完成.因此，选择ES路径问题是关键.由于该问题为非凸优化问题，即NP难问题，与影响力最大化问题本质为同一问题.因此，可将ES路径择优问题转化为社会网络中影响力最大化问题.

针对社会网络影响力最大化问题，Kempe等人[22]首次提出运用贪心算法求解.随后，基于贪心策略改进的算法被大量提出.例如，利用影响力函数子模性的CELF(cost-effective lazy-forward)算法[23]、优化CELF算法后的CELF++算法[24]、将社会网络图缩小化后的NewGreedy算法[25]等.但贪心算法时间复杂度较高，无法适应于大型网络.因此，大量启发式算法被提出，最早的启发式算法是依据节点中心度来判断节点影响力大小[26].随后，基于度中心方法优化的DegreeDiscount算法[25]、利用K-shell算法的核覆盖算法(core covering algorithm,CCA)[27]、考虑邻居节点距离远近损耗的PageRank算法[28]、利用反向排名信息和邻居节点影响的逆向节点排名(reversed node ranking,RNR)算法[29]等相继被提出，有效解决了贪心算法时间开销较大等问题.其中，文献[27]提出的CCA算法充分考虑选取种子节点影响范围的重叠情况，基于K-shell分解求解出每个节点的核数，然后根据核数分布的层次性，引入节点的影响半径参数，最后综合核数和度数2个属性找出影响力节点集合.但启发式算法精准度较低，故有些研究者将2类算法相结合进行求解.例如，Chen等人[30]用最大影响力路径来估算影响力的传播，并提出了最大化影响力树状(maximum influence arborescence,MIA)算法进行求解该问题；Kim等人[31]结合贪心算法的精确度和启发式算法的高效率提出了独立路径算法(independent path algorithm,IPA)，通过设置阈值，将传播路径的概率近似为影响函数，缩短了运行时间.

本文将MEC计算迁移路径最优化转化为社会网络影响力最大化问题，充分考虑网络拓扑结构中ES的位置及属性，构建计算迁移路径优化选择算法，对不同ES通过K-shell算法进行分等级处理，有效减少ES路径搜索消耗成本.其核心思想是将ES类比为社会网络节点，通过K-shell算法定义ES路径影响力，提出K-shell影响力最大化计算迁移(K-shell influence maximization computation off-loading,Ks-IMCO)算法，有效降低能耗与时延，提高用户体验质量.

1 计算迁移系统建模与策略研究

假设由1个基站、n个边缘服务器和m个智能终端组成的移动边缘计算场景.n个ES共同构成网络G(P,E)，其中，P为边缘服务器构成的集合，P={pi|i=1,2,…,n}，E为边缘服务器连接矩阵.m个终端集合形式表示为D={dk|k=1,2,…,m}.终端dk的计算任务Rdk包括本地计算任务Rloc,dk和迁移计算任务Rtran,dk.如图1所示，终端与基站关联的ES通过正交频分复用(OFDMA)进行通信.

考虑到终端计算能力受限，根据计算复杂度δk分割任务，dk在本地执行复杂度较低的任务，将复杂度高的任务迁移到ES执行.因此，使用二元变量δk∈{0,1}表示终端的决策，δk=0表示本地执行；δk=1表示迁移到ES执行，并将结果返回终端.计算迁移决策流程图如图2所示.

1.1 任务本地计算建模与分析

在本地计算时，设终端dk分配的任务Rloc,dk运行功率为Ploc,dk，CPU频率为floc,dk，则本地计算所需时延Tloc,dk与能耗Eloc,dk可采用文献[33]中系统模型的构建思想表示为

(1)

(2)

由式(1)(2)得到本地服务质量公式Qloc,dk：

Qloc,dk=αTloc,dk+βEloc,dk，

(3)

1.2 基于路径择优的计算迁移策略建模

为解决ES资源受限引起的多用户并发访问，导致网络堵塞.密集型任务模拟选择ES进行迁移，获得最佳迁移路线，即ES路径L′={p1,p2,…,pl}，其中l≤n.

终端利用OFDMA信道连接请求ES，且每条信道之间相互独立.设h为信道增益，为dk至pi上行传输功率，为边缘网络内传输功率，为下行传输功率，其中i<j<l，j=i+1，bk为基站分配给dk的带宽，bk<bmax，B为基站带宽，N0为噪声平均功率.上行传输速率、边缘网络内传输功率下行传输功率根据香农定理表示为[11]：

(4)

当前ES因资源受限无法完成终端dk迁移到边缘的任务Rtran,dk时，综合考虑计算任务在传输、计算过程中的时延与能耗，将部分任务迁移到相邻ES.其中计算任务的传输包括上行传输、边缘网络内传输和下行传输3部分.

迁移请求发起后，上行传输时延Tloc,mec、ES路径内传输时延Tmec,mec、下行传输时延Tmec,loc可分别表示为[13]：

(5)

其中，为迁移到ES路径L′中pi的计算任务，λ为计算结果复杂度(0<λ<1).

上行传输能耗Eloc,mec、ES路径内能耗Emec,mec、下行传输能耗Emec,loc分别为[15]：

(6)

根据式(5)(6)得到传输时延Ttran、传输能耗Etran分别为

Ttran=Tloc,mec+Tmec,mec+Tmec,loc，

(7)

Etran=Eloc,mec+Emec,mec+Emec,loc.

(8)

任务计算时，分别构建任务计算时延Tmec与计算能耗Emec模型[15]：

(9)

(10)

其中，fmec,pi,和分别为pi的CPU工作频率、运行功率和最大计算任务能力.

根据任务传输和计算开销，得到任务迁移计算所需要的时延Tcount,dk与能耗Ecount,dk分别为

Tcount,dk=Ttran+Tmec,

(11)

Ecount,dk=Etran+Emec.

(12)

由式(11)(12)得到迁移计算服务质量公式Qcount,dk：

Qcount,dk=αTcount,dk+βEcount,dk,

(13)

综上所述，任务迁移需要的总时延Ttotal,dk与总能耗Etotal,dk分别表示为

Ttotal,dk=Tloc,dk+Tcount,dk,

(14)

Etotal,dk=Eloc,dk+Ecount,dk.

(15)

由式(14)(15)得到任务迁移服务质量公式Qtotal,dk：

Qtotal,dk=αTtotal,dk+βEtotal,dk,

(16)

2 计算迁移路径选择优化策略

2.1 基于K-shell算法边缘服务器划分与计算迁移优化策略

在研究网络拓扑结构中，节点重要性度量方法常用指标有度中心性[34]、介数中心性[35]、紧密中心性[36]等.度中心性只关注了节点周围邻居数量，而介数中心性与紧密中心性需计算最短入境从而导致时间复杂度较高.文献[37]提出了节点重要程度依赖于所处网络中位置的思想，图论中经典的K-shell算法[38]充分利用了这一思想，能够准确有效地识别节点在网络中的影响力.

K-shell算法是通过层层剥离的方式对网络中节点进行分类.本文将网络中ES类比为节点，采用K-shell算法进行等级划分，通过网络拓扑结构区分ES在网络中的不同位置.假设网络内包含节点为a，b，…，q，r，如图3所示.具体分类过程为：

首先去除网络内度数最低(度数为1)的节点，即a，b，c，e，q，r标记ks=1；剩余的节点又会组成新的网络，此时度数最少的节点为d,o,p,n，m，l，k，j，这些节点的ks=2；以此类推，直到网络中所有的节点都具有ks值.

针对CCA算法[27]中所考虑种子节点间的覆盖范围重合的问题，结合本文研究问题，考虑任务传输过程中的路径重叠问题.由于该问题会导致边缘服务器负载过重，故构建路径重叠(path overlap,PO)算法.

算法1.路径重叠算法.

输入:ES网络G(P,E);

输出:路径集合S(L).

① for 每个ES

② 根据路径生成规则，查找所有迁移路径Lall；

③ end for

④ for 每个Lall

⑤ 搜索重叠路径；

⑥ end for

考虑ES计算能力、基站带宽资源、任务迁移时延与能耗因素，以用户体验质量(QoE)作为多终端迁移策略联合优化目标，构建近于实际应用环境的密集型任务系统模型min Q[11]：

(17)

式(17)为非凸优化问题，是一个NP难问题.针对NP难问题，以通信质量、ES交互频度等为约束，将其转化为影响力最大化问题用Ks-IMCO算法进行求解.

2.2 ES路径影响力选择模型

考虑到ES的计算、传输能力的差异性，构建ES路径对计算任务的评判标准：ES路径影响力.

ES路径影响力由其自身影响力与潜在影响力所构成.其中，ES自身影响力受ES在网络中所处位置与自身属性影响；潜在影响力主要考虑任务迁移时延、能耗和传输通信质量等.ES路径影响力选择模型过程如图4所示.

综合考虑ES在网络拓扑结构所在位置，利用度中心方法度量ES重要性[26]：

(18)

ES自身属性包含运行功率、CPU工作频率fmec,pi、等待列队处理能力，其自身影响力可表示为

(19)

潜在影响力表示ES路径具有的潜在计算能力，由K-shell方法计算；σ,Cqua分别表示ES之间的交互频度和通信质量；Ttotal,dk，Etotal,dk分别表示任务迁移延迟和能耗.则潜在影响力表达式为

(20)

σ∈(0,20],

其中，D(pi)为邻居节点pj的集合，ks为ES所处等级值，θ为随机分布变量，N0为噪声功率.

综上，ES路径影响力计算表示为

(21)

为了描述一致，将用户体验质量作为计算迁移策略优化目标转化为ES路径影响力最大化问题求解.则有：

(22)

证明.

由式(17)可得：

由式(22)可得：

因为均大于0，且αTtotal,dk+βEtotal,dk+1>1；

所以min Q(K,L′,b)正比于

证毕.

2.3 Ks-IMCO路径寻优算法

根据ES所处ks等级，将备选迁移路径进行排队，迁移路径选择约束条件初始ES只能向同级或低级延伸.算法描述为：

步骤1. 式(18)求解ES的

步骤2. 式(19)求解ES的

步骤3. 计算ES的ks；

步骤4. 式(20)求解ES的

步骤5. 构建ES初始路径集，将任务量Rtran,dk按ES路径内数量划分，计算ES路径L′的

步骤6. 运行PO算法，对路径重叠部分选择其影响力最大路径进行计算迁移；

步骤7. 得到最终计算迁移路径.

算法2.K-shell影响力最大化计算迁移算法.

输入:ES网络G(P,E),Rdk,δk,Ploc,dk,floc,dk,

输出:路径集合S(L′).

① for 每个ES

② 计算

③ 通过式(19)，计算

④ 计算pi(ks)；

⑤ 根据路径生成规则，查找所有迁移路径

⑥ end for

⑦ for 每个MSD任务Rdk

⑧ if δk=0

⑨ Rloc,dk执行本地计算；

⑩ else if δk=1

Rtran,dk执行迁移计算；

end if

end for

for 每个本地任务Rloc,dk

通过式(1)(2)，计算时延Tloc,dk与能耗

Eloc,dk；

通过式(3)，计算本地服务质量Qloc,dk；

end for

for 每个迁移任务Rtran,dk

for 迁移任务路径集合

不进行迁移计算；

进行迁移计算；

通过式(11)(12)，计算时延Tcount,dk

与能耗 Ecount,dk；

通过式(13)，计算Qcount,dk；

通过式(21)，计算每个迁移路径L′

影响力

end if

for 每条迁移路径L′影响力

end if

end for

end for

end for

3 仿真实验与分析

3.1 仿真实验设计

一个社区由多个MSD与ES构成，每个MSD与ES通过正交频分复用(OFDMA)信道相连，各个信道之间相互独立.在同一时刻，每个MSD将计算不同大小的任务，按照计算复杂度策略将任务进行分割，对于密集型任务通过信道进行计算迁移，完成多用户多服务器的边缘计算.具体仿真参数如表1所示：

3.2 算法仿真与性能分析

实验1.本地计算与Ks-IMCO算法迁移计算能耗对比分析.

本地计算迁移策略与Ks-IMCO算法迁移计算进行对比分析，实验过程中，将每个MSD任务随机设为10～100 GB，在500个ES组成的数据集进行仿真，观察MSD数目由0～500过程中能耗所发生的变化.Ks-IMCO算法迁移计算能耗仅计算MSD分割后任务的本地计算能耗与上传能耗，实验结果如图5、图6所示:

从图5、图6可以看出，当系统MSD数目在100时，Ks-IMCO迁移计算能耗降低80%以上；系统MSD数目在100～450时，Ks-IMCO迁移计算能耗降低70%以上；当系统MSD数目在350～450时，Ks-IMCO算法迁移计算节能效果趋于稳定，维持在70%左右.Ks-IMCO算法迁移计算能耗明显小于本地计算.

实验2.不同算法能耗与时延对比分析.

将Ks-IMCO算法分别与随机分配(random allocation,RA)、路径选择切换(path selection with handovers,PSwH)算法[20]对比分析其有效性.

设Rdk为MSD计算任务量.不同数量级的任务量代表不同格式文件，具体划分如表2所示：

针对Ks-IMCO算法与RA算法、PSwH算法分别在不同场景下进行时延与能耗对比实验，实验过程中逐渐增加MSD数目观察时延与能耗性能.为了提高实验的准确性，针对ES网络规模，分别以500，1 000，2 000，5 000的数据集进行实验.

纯文本文件实验结果如图7～10所示:

图片文件实验结果如图11～14所示.

流式文件实验结果如图15～18所示.

大规模数据流式文件实验如图19～22所示.

从表3可以看出，对于不同形式的任务Rdk，当ES规模为500且MSD数目为500时，Ks-IMCO算法较RA算法节能60%～70%，时延缩短41%～48%，较PSwH算法节能13%～15%，时延缩短12%～15%；当ES规模为500且MSD数目为1 000时，Ks-IMCO算法较RA算法节能45%～55%，时延缩短35%～40%，较PSwH算法节能24%～26%，时延缩短30%～36%；当ES规模为500且MSD数目为2 000时，Ks-IMCO算法较RA算法节能65%～70%，时延缩短43%～55%，较PSwH算法节能40%～55%，时延缩短38%～47%；当ES规模为5 000，MSD数目为500时，Ks-IMCO算法较RA算法节能60%～65%，时延缩短45%～50%，较PSwH算法节能55%～57%，时延缩短24%～38%.随着ES规模逐渐增大，Ks-IMCO算法对比RA算法节能总体维持在60%左右，对比PSwH算法节能逐渐增高；Ks-IMCO算法对比RA，PSwH算法具有较短时延.因此，从能耗与时延方面看，Ks-IMCO算法能有效提高用户服务质量.

4 讨论问题与未来工作

对于边缘计算中能耗与时延优化问题影响因素不仅在于路径的选择问题，其中也包含在路径选择前的任务分配、ES路径分布重叠稀疏度问题.

1)任务分配对路径选择以及能耗和时延的影响.由于本文中对于任务分配进行主动划分，故在进行计算迁移时，任务进行迁移或在本地计算时可能对路径选择以及能耗和时延产生影响.为此，我们进行随机实验对比分析，为使实验效果最为明显，选取MSD任务为10～100 GB范围内进行实验.实验结果如图23所示，从图23(a)中可看出主动划分时延小于随机划分，图23(b)中可看出主动划分能耗小于随机划分.在今后的工作中，将研究如何进行任务智能划分，对不同终端发布任务根据任务量以及可迁移路线进行智能划分，进一步优化迁移计算能耗与时延.

2)ES路径分布重叠稀疏度对路径选择以及能耗和时延的影响.通过选取不同稀疏的ES路径分布进行实验结果如图24所示.从图24(a)中可以看出对于稀疏度高的ES路径分布图能耗与稀疏度低的ES路径分布图相差无几,图24(b)中可以看出对于稀疏度高的ES路径分布图时延小于稀疏度低的ES路径分布图.

5 总 结

本文将边缘计算中计算迁移路径选择问题转化为社会网络影响力最大化问题，为计算迁移路径择优问题提供了新思路，将问题转换可以有效利用网络拓扑结构进行边缘服务器分层，节约路径搜寻时间，依据社会网络影响力最大化问题中的K-shell算法进行路径影响力定义，提出了Ks-IMCO算法求解该问题.实验结果表明：Ks-IMCO算法迁移计算较本地计算能耗有效节能在70%左右；对于不同形式的任务，Ks-IMCO算法在能耗与时延方面都优于RA，PSwH算法.

参考文献

[1]Barbera M V,Kosta S,Mei A,et al.To offload or not to offload?The bandwidth and energy costs of mobile cloud computing[C] //Proc of the IEEE Int Conf on Computer Communications (INFOCOM).Piscataway,NJ:IEEE,2013:1285-1293

[2]Satyanarayanan M.Pervasive computing:Vision and challenges[J].IEEE Personal Communications,2001,8(4):10-17

[3]Sun Xiang,Ansari N.Green cloudlet network:A sustainable platform for mobile cloud computing[J].IEEE Transactions on Cloud Computing,2020,8(1):180-192

[4]Bonomi F,Milito R,Zhu Jiang,et al.Fog computing and its role in the Internet of things[C] //Proc of the MCC Workshop Mobile Cloud Computing.New York:ACM,2012:13-16

[5]Shi Weisong,Zhang Xingzhou,Wang Yifan,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)(施巍松,张星洲,王一帆,等.边缘计算现状与展望[J].计算机研究与发展,2019,56(1):69-89)

[6]Wu Yuan,Shi Binghua,Li Pingqian,et al.Energy-efficient multi-task multi-access computation offloading via NOMA transmission for IoTs[J].IEEE Transactions on Industrial Informatics,2020,16(7):4811-4822

[7]Lü Xinchen,Tian Hui,Jiang Li,et al.Selective offloading in mobile edge computing for the green Internet of things[J].IEEE Network,2018,32(1):54-60

[8]Wei Feng,Chen Sixuan,Zou Weixia.A greedy algorithm for task offloading in mobile edge computing system[J].China Communications,2018,15(11):149-157

[9]Liu Liqing,Chang Zheng,Guo Xijuan.Socially-aware dynamic computation offloading scheme for fog computing system with energy harvesting devices[J].IEEE Internet of Things Journal,2018,5(3):1869-1879

[10]Zhang Hongli,Zhang Qiang,Du Xiaojiang.Toward vehicle-assisted cloud computing for smartphones[J].IEEE Transactions on Vehicular Technology,2015,64(12):5610-5618

[11]Yu Bowen,Pu Lingjun,Xie Yuting,et al.Joint task offloading and base station association in mobile edge computing[J].Journal of Computer Research and Development,2018,55(3):537-550 (in Chinese)(于博文,蒲凌君,谢玉婷,等.移动边缘计算任务卸载和基站关联协同决策问题研究[J].计算机研究与发展,2018,55(3):537-550)

[12]Zhang Qixun,Chen Jingran,Ji Lei,et al.Response delay optimization in mobile edge computing enabled UAV swarm[J].IEEE Transaction on Vehicular Technology,2020,3(69):3280-3295

[13]Zhou Yi,Yeoh P L,Pan Cunhua,et al.Offloading optimization for low-latency secure mobile edge computing systems[J].IEEE Wireless Communications Letters,2020,9(4):480-484

[14]Guo Mian,Li Lei,Guan Quansheng.Energy-efficient and delay-guaranteed workload allocation in IoT-edge-cloud computing systems[J].IEEE Access,2019,7:78685-78697

[15]Qin Min,Chen Li,Zhao Nan,et al.Computing and relaying:Utilizing mobile edge computing for P2P communications[J].IEEE Transactions on Vehicular Technology,2020,69 (2):1582-1594

[16]Chen Xu,Li Wenzhong,Lu Sanglu,et al.Efficient resource allocation for on-demand mobile-edge cloud computing[J].IEEE Transactions on Vehicular Technology,2018,67(9):8769-8780

[17]Wang Chenmeng,Liang Chengchao,Yu F R,et al.Computation offloading and resource allocation in wireless cellular networks with mobile edge computing[J].IEEE Transactions on Wireless Communications,2017,16(8):4924-4938

[18]Xu Xiaolong,Gu Renhao,Dai Fei,et al.Multi-objective computation offloading for Internet of vehicles in cloud-edge computing[J].Wireless Networks,2020,26(3):1611-1629

[19]Chen Xu,Jiao Lei,Li Wenzhong,et al.Efficient multi-user computation offloading for mobile-edge cloud computing[J].IEEE/ACM Transactions on Networking,2015,24(5):2795-2808

[20]Becvar Z,Plachy J,Mach P.Path selection using handover in mobile networks with cloud-enabled small cells[C] //Proc of the 25th IEEE Int Symp on Personal,Indoor and Mobile Radio Communications.Piscataway,NJ:IEEE,2014:1480-1485

[21]Xiang Chaocan,Zhang Zhao,Qu Yuben,et al.Edge computing-empowered large-scale traffic data recovery leveraging low-rank theory[J].IEEE Transactions on Network Science and Engineering,2020,7(4):2205-2218

[22]Kempe D,Kleinberg J,Tardos E.Maximizing the spread of influence in a social network[C] //Proc of the 9th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining.New York:ACM,2003:137-146

[23]Leskovec J,Krause A,Guestrin C,et al.Cost-effective outbreak detection in networks[C] //Proc of the 13th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining.New York:ACM,2007:420-429

[24]Goyal A,Lu Wei,Lakshmanan L V S.CELF++:Optimizing the greedy algorithm for influence maximization in social networks[C] //Proc of the 20th Int Conf Companion on World Wide Web.New York:ACM,2011:47-48

[25]Chen Wei,Wang Yajun,Yang Siyu.Efficient influence maximization in social networks[C] //Proc of the 15th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining,New York:ACM,2009:199-208

[26]Bonacich P.Factoring and weighting approaches to status scores and clique identification[J].Journal of Mathematical Sociology,1972,2(1):113-120

[27]Cao Jiuxin,Dong Dan,Xu Shun,et al.A k-core based algorithm for influence maximization in social networks[J].Chinese Journal of Computers,2015,38(2):238-248 (in Chinese)(曹玖新,董丹,徐顺,等.一种基于k-核的社会网络影响最大化算法[J].计算机学报,2015,38(2):238-248

[28]Luo Zhilin,Cai Wandong,Li Yongjun,et al.A pagerank-based heuristic algorithm for influence maximization in the social network[M] //Recent Progress in Data Engineering and Internet Technology.Berlin:Springer,2012:485-490

[29]Rui Xiaobin,Meng Fanrong,Wang Zhixiao,et al.A reversed node ranking approach for influence maximization in social networks[J].Applied Intelligence,2019,49(7):2684-2698

[30]Wang Chi,Chen Wei,Wang Yajun.Scalable influence maximization for independent cascade model in large-scale social networks[J].Data Mining and Knowledge Discovery,2012,25(3):545-576

[31]Kim J,Kim S K,Yu H.Scalable and parallelizable processing of influence maximization for large-scale social networks[C] //Proc of the 29th Int Conf on Data Engineering.Piscataway,NJ:IEEE,2013:266-277

[32]Wei Xiaojuan,Wang Shangguang,Zhou Ao,et al.MVR:An architecture for computation offloading in mobile edge computing[C] //Proc of the 2017 IEEE Int Conf on Edge Computing (EDGE).Piscataway,NJ:IEEE,2017:232-235

[33]Nadembega A,Hafid A S,Brisebois R.Mobility prediction model-based service migration procedure for follow me cloud to support QoS and QoE[C] //Proc of the 2016 IEEE Int Conf on Communications (ICC).Piscataway,NJ:IEEE,2016:1-6

[34]Albert R,Jeong H,Barabbasi A L.The diameter of the world wide Web[J].Nature,1999,401(6749):130-131

[35]Freeman L C.A set of measures of centrality based on betweenness[J].Sociometry,1977,40(1):35-41

[36]Sabidussi G.The centrality index of a graph[J].Psychombtrika,1966,31(4):581-603

[37]Kitsak M,Gallos L K,Havlin S,et al.Identification of influential spreaders in complex networks[J].Nature Physics,2010,6(11):888-893

[38]Maji G,Namtirtha A,Dutta A,et al.Influential spreaders identification in complex networks with improved k-shell hybrid method[J/OL].Expert Systems with Applications,2020[2020-05-05].https://www.sciencedirect.com/science/article/abs/pii/S0957417419308097#!

[39]Li Chao,Wang Li,Sun Shiwen,et al.Identication of inuential spreaders based on classied neighbors in real-world complex networks[J].Applied Mathematics and Computation,2017,320:512-523

A Computation Offloading Algorithm with Path Selection Based on K-shell Influence Maximization

Yue Guangxue1,3,Chen Guanglu1,2,3,Lu Min3,Yang Xiaohui1,3,Liu Jianhua1,Huang Chunlan1,3,and Yang Zhongming1,3

1(College of Information Science and Engineering,Jiaxing University,Jiaxing,Zhejiang 314001) 2(State Grid Jibei Dacheng Power Supply Co .,Ltd,Langfang,Hebei 065000) 3(College of Science,Jiangxi University of Science and Technology,Ganzhou,Jiangxi 341000)

Abstract As edge computing and cloud computing develop in a rapid speed and integrate with each other,resources and services gradually offload from the core network to the edge of the network.Efficient computation offloading algorithm is one of the most important problems in mobile edge computing networks.In order to improve the performance of the algorithm,a computation offloading algorithm with path selection based on K-shell influence maximization is proposed.The K-shell method is used to grade the edge servers by applying the convertibility and maximizing influence model of similar problems.Otherwise,considering the problem of excessive load of edge servers,path overlap (PO)algorithm is constructed,and indicators such as the communication quality,interaction strength,and queue processing ability,etc.are introduced to optimize the performance of the algorithm.The offloading path problem of the optimization calculation task is transformed into the social network impact maximization problem.Based on the idea of maximizing K-shell influence,greedy and heuristic algorithms are optimized and improved,and the K-shell influence maximization computation offloading (Ks-IMCO)algorithm is proposed to solve the problem of computational offloading.Through the comparative analysis of Ks-IMCO and random allocation (RA),path selection with handovers (PSwH)algorithm experiments,the energy consumption and delay of Ks-IMCO algorithm have been significantly improved,which can effectively improve the efficiency of edge computing network computing offloading.

Key words mobile edge computing;computation offloading;influence maximization;path selection;K-shell

中图法分类号 TP393

DOI:10.7544/issn1000-1239.2021.20200338

收稿日期：2020-05-25； 修回日期：2021-05-10

基金项目：国家自然科学基金项目(U19B2015)；浙江省“鲲鹏行动”计划支持项目

This work was supported by the National Natural Science Foundation of China (U19B2015)and the Top-level Talent Project of Zhejiang Province.

Yue Guangxue,born in 1963.PhD,professor.Member of IEEE and CCF.His main research interests include cloudy convergence and collaborative services,wireless mesh networks and mobile cloud computing.

乐光学，1963年生.博士,教授.IEEE和CCF会员.主要研究方向为多云融合和协同服务、无线mesh网络和移动云计算.

Chen Guanglu,born in 1995.Master.His main research interests include social networks and mobile edge computing.

陈光鲁，1995年生.硕士.主要研究方向为社会网络和移动边缘计算.

Lu Min,born in 1964.Master,professor.His main research interests include network communication and electronic material devices.

卢 敏，1964年生.硕士,教授.主要研究方向为通信网络和电子材料设备.

Yang Xiaohui,born in 1996.Master.Student member of CCF.Her main research interest is mobile cloud computing.

杨晓慧，1996年生.硕士,CCF学生会员.主要研究方向为移动云计算.

Liu Jianhua,born in 1978.PhD,associate professor.Member of IEEE.His main research interests include distributed computing,wireless communications,multimedia networking,wireless sensor networks,and machine learning.

刘建华，1978年生.博士,副教授,IEEE会员.主要研究方向为分布式计算、无线通信、多媒体网络、无线传感网络和机器学习.

Huang Chunlan,born in 1997.Master candidate.Her main research interest is mobile cloud computing.

黄淳岚，1997年生.硕士研究生.主要研究方向为移动云计算.

Yang Zhongming,born in 1998.Master candidate.His main research interest is mobile cloud computing.

杨忠明，1998年生.硕士研究生.主要研究方向为移动云计算.