[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

CN111836328B - 一种基于K-shell影响力最大化计算迁移优化方法 - Google Patents

一种基于K-shell影响力最大化计算迁移优化方法 Download PDF

Info

Publication number
CN111836328B
CN111836328B CN202010677809.3A CN202010677809A CN111836328B CN 111836328 B CN111836328 B CN 111836328B CN 202010677809 A CN202010677809 A CN 202010677809A CN 111836328 B CN111836328 B CN 111836328B
Authority
CN
China
Prior art keywords
calculation
path
migration
task
energy consumption
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
CN202010677809.3A
Other languages
English (en)
Other versions
CN111836328A (zh
Inventor
乐光学
陈光鲁
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Jiaxing University
Original Assignee
Jiaxing University
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Jiaxing University filed Critical Jiaxing University
Priority to CN202010677809.3A priority Critical patent/CN111836328B/zh
Publication of CN111836328A publication Critical patent/CN111836328A/zh
Application granted granted Critical
Publication of CN111836328B publication Critical patent/CN111836328B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W40/00—Communication routing or communication path finding
    • H04W40/02—Communication route or path selection, e.g. power-based or shortest path routing
    • H04W40/04—Communication route or path selection, e.g. power-based or shortest path routing based on wireless node resources
    • H04W40/10—Communication route or path selection, e.g. power-based or shortest path routing based on wireless node resources based on available power or energy
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W40/00—Communication routing or communication path finding
    • H04W40/02—Communication route or path selection, e.g. power-based or shortest path routing
    • H04W40/12—Communication route or path selection, e.g. power-based or shortest path routing based on transmission quality or channel quality

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Mobile Radio Communication Systems (AREA)

Abstract

本发明公开了一种基于K‑shell影响力最大化计算迁移优化方法，该方法以时延与能耗联合最小化为目标，将移动终端的计算迁移资源路径优化问题转化为社会网络影响力最大化问题求解，转化后的影响力最大化问题考虑边缘服务器ES在网络所处位置与自身属性，通过K‑shell方法进行分等级处理，有效减少ES路径搜索消耗成本，并结合贪心与启发式算法的思想提出K‑shell影响力最大化计算迁移算法Ks‑IMCO。实验表明，Ks‑IMCO算法对比RA与PSwH算法的能耗、延迟明显提升，能有效提高边缘计算网络计算迁移的效率。

Description

一种基于K-shell影响力最大化计算迁移优化方法
技术领域
本发明涉及移动边缘计算技术领域，具体是边缘计算中的一种基于K-shell影响力最大化计算迁移优化方法。
背景技术
随着通信技术与智能终端设备的快速发展和应用普及，流式服务已成为移动网络承载的重要业务之一，对智能终端设备性能提出了更高的要求。受计算能力、存储容量、电池能耗、设计美观等限制，使移动智能设备(Mobile Smart Device，MSD)无法完成资源需求大、计算任务重的密集型任务。为解决该问题，资源丰富的云计算模型作为有效方案之一应运而生，并由此已演化出雾计算、边缘计算等先进的计算模式。5G技术的日渐成熟和应用推广，使得无线移动网络承载数据和业务量将以线性增长，流式多元化网络业务和服务的快速增长必将导致网络拥塞、数据丢失等问题，传统的云计算已无法满足终端对高带宽、低时延和实时性的需求。
为了解决云计算的不足，新出现的网络计算模式在终端用户附近提供计算资源，并根据应用需求将数据就近处理，如透明计算、cloudlet、边缘计算、雾计算[4]和移动边缘计算等。cloudlet和雾计算的计算能力未集成到移动网络中，导致服务质量降低。移动边缘计算较其他计算模式更侧重于无线接入网络，具有低时延、低能耗等优点。2014年，欧洲电信标准协会(ETSI)提出移动边缘计算(Mobile Edge Computing，MEC)，基本思想：将延迟敏感的应用程序迁移到距离较近的边缘服务器(Edge Server，ES)进行计算与存储，有效降低传输时延。2016年，ETSI把MEC的概念扩展为“多接入边缘计算”(Multi-access EdgeComputing，MEC)，将移动边缘计算从电信蜂窝网络进一步延伸至其他无线接入网络(如WiFi)。其中，计算迁移是MEC研究的关键问题之一。终端根据实际应用场景指定不同的卸载策略时需考虑何时迁移、在何处迁移、如何迁移、迁移哪部分等，最终达到能耗与系统性能的平衡，提升用户的服务质量和体验质量。
针对移动终端资源受限这一课题，MEC近年在计算机科学领域得到广泛研究，计算迁移技术的发展，为解决终端资源受限这一问题引入了新的方法。计算迁移可以实现将计算体迁移到其他资源丰富的终端上运行、跨终端任务同步、移动设备资源共享等应用目标。
综上所述，现有技术主要存在以下问题：关于MEC资源划分的研究主要集中在算法设计上，同时大部分都只涉及了单用户MEC，对多用户MEC的计算迁移路径缺乏研究。并且大多数都是仅考虑了计算延迟，或者是仅考虑终端能耗，没有把延迟和能耗联合考虑，无法达到全局最优，并不能有效解决移动终端资源受限的问题。
发明内容
本发明的目的在于克服上述现有技术的不足，而提供一种基于K-shell影响力最大化计算迁移优化方法，该方法通过将MEC计算迁移路径选择转化为社会网络中影响力最大化求解问题，构建计算迁移路径优化选择算法，转化后的影响力最大化问题充分考虑ES在网络拓扑结构中所处位置与自身属性，对不同ES通过K-shell方法进行分等级处理，有效减少ES路径搜索消耗成本，其核心思想是将ES类比为社会网络节点，通过K-shell方法定义ES路径影响力，结合贪心与启发式算法的思想提出K-shell影响力最大化计算迁移(K-shell Influence Maximization Computation Offloading，Ks-IMCO)算法，从而有效降低能耗与时延，提高用户体验质量。
实现本发明目的的技术方案是：
一种基于K-shell影响力最大化计算迁移优化方法，该方法是假设移动边缘计算系统由1个基站、n个边缘服务器和m个智能终端组成；n个边缘服务器共同构成网络G(P,E)，其中P为边缘服务器构成的集合，P＝{pi|i＝1,2,...,n}，E为边缘服务器连接矩阵；m个终端集合形式表示为D＝{dk|k＝1,2,...,m}，对于第k个终端dk的计算任务
Figure GDA0003470826170000021
由本地计算任务
Figure GDA0003470826170000022
与迁移计算任务
Figure GDA0003470826170000023
组成；具体包括如下步骤：
1)初始任务：当一个用户智能终端发布任务时，依据计算复杂度δk将任务分为本地计算与迁移计算；
2)本地计算：当任务属于本地计算时，依据MSD自身属性与本地任务量构建能耗与时延模型，计算本地能耗与时延；
3)迁移计算：当任务属于迁移计算时，将能耗与时延分为传输部分和计算部分：
3-1)传输部分的能耗与时延分为上行传输、ES路径内传输、下行传输三部分，其中上行传输代表将任务从用户终端传输到边缘服务器，ES路径内传输代表任务在边缘服务器组内传输，下行传输代表将服务器任务计算结果回传到用户终端；
3-2)计算部分的能耗与时延依据ES自身属性与本地任务量构建能耗与时延模型，描述任务迁移在服务器上任务计算所需的能耗与时延；
4)ES路径影响力：针对不同ES所组成集合的计算能力与传输能力不同进行评判的标准，由ES路径自身影响力与潜在影响力所构成，在潜在影响力的构成模型中充分考虑任务迁移过程中所消耗的能耗与时延；
5)问题转化：将用户体验质量作为计算迁移策略优化目标转化为ES路径影响力最大化问题，其本质是计算迁移路径选择优化转化为ES路径影响力最大化；问题转化后，按照其路径搜寻规则可有效减少ES路径搜索消耗成本；
6)执行KS-IMCO算法：将ES类比为社会网络节点，利用K-shell方法将ES进行等级分类，结合贪心与启发式思想求解ES路径影响力最大化问题。
步骤2)中，本地能耗与时延的计算，是设用户终端dk分配的任务
Figure GDA0003470826170000031
运行功率为
Figure GDA0003470826170000032
CPU频率为
Figure GDA0003470826170000033
则本地计算所需时延
Figure GDA0003470826170000034
与能耗
Figure GDA0003470826170000035
表示如下：
Figure GDA0003470826170000036
Figure GDA0003470826170000037
由公式(1)、(2)得本地计算服务质量公式
Figure GDA0003470826170000038
Figure GDA0003470826170000039
Figure GDA00034708261700000310
步骤3)中，所述的迁移计算，是将密集型任务在ES上进行模拟选择最为适合的迁移路径，即ES路径L′＝(p1,p2,p3,...,pl)，其中l≤n；终端利用OFDMA信道连接请求ES，且每条信道之间相互独立；设θ为信道增益，
Figure GDA0003470826170000041
为dk至pi任务上行传输功率，
Figure GDA0003470826170000042
为ES路径内传输功率，
Figure GDA0003470826170000043
为任务下行传输功率，其中i<j<l，j＝i+1，bk为基站分配给dk的带宽，bk<bmax，B为基站带宽，N0为噪声平均功率，则上行传输速率
Figure GDA0003470826170000044
ES路径内传输速率
Figure GDA0003470826170000045
下行传输速率
Figure GDA0003470826170000046
根据香农定理表示为：
Figure GDA0003470826170000047
Figure GDA0003470826170000048
终端dk迁移到边缘的任务
Figure GDA0003470826170000049
在当前ES因资源受限无法完全计算时，将部分剩余任务迁移到与之相邻的ES，综合考虑传输、计算时延与能耗，迁移请求发起后，设传输过程中
Figure GDA00034708261700000410
为迁移到ES路径L′的计算任务，λ为计算结果复杂度0<λ<1，则上行传输时延Tloc,mec、ES路径内传输时延Tmec,mec、下行传输时延Tmec,loc分别表示为：
Figure GDA0003470826170000051
Figure GDA0003470826170000052
表示下行传输任务量，上行传输能耗Eloc,mec、ES路径内能耗Emec,mec、下行传输能耗Emec,loc分别表示为：
Figure GDA0003470826170000053
根据公式(5)、(6)得传输时延Ttran、传输能耗Etran分别为：
Ttran＝Tloc,mec+Tmec,mec+Tmec,loc (7)
Etran＝Eloc,mec+Emec,mec+Emec,loc (8)
任务计算时，设pi的CPU工作频率为
Figure GDA0003470826170000054
运行功率为
Figure GDA0003470826170000055
最大计算任务能力为
Figure GDA0003470826170000056
则计算时延Tmec与计算能耗Emec模型为：
Figure GDA0003470826170000057
Figure GDA0003470826170000058
Figure GDA0003470826170000061
根据任务传输和计算两部分时延与能耗模型，得出迁移计算所需要的时延
Figure GDA00034708261700000614
与能耗
Figure GDA00034708261700000615
分别为：
Figure GDA0003470826170000062
Figure GDA0003470826170000063
由式(11)、(12)得迁移计算服务质量公式
Figure GDA0003470826170000064
Figure GDA0003470826170000065
Figure GDA0003470826170000066
则任务迁移需要的总时延
Figure GDA0003470826170000067
与总能耗
Figure GDA0003470826170000068
表示为：
Figure GDA0003470826170000069
Figure GDA00034708261700000610
由公式(14)、(15)得任务迁移服务质量公式
Figure GDA00034708261700000611
Figure GDA00034708261700000612
Figure GDA00034708261700000613
步骤4)中，所述的ES路径影响力，包括ES自身影响力和潜在影响力；ES自身影响力是考虑ES在网络中所处位置与自身属性；潜在影响力主要是考虑任务迁移所需时延、能耗与传输通信质量；依据网络拓扑结构，综合考虑ES在所在位置，利用度中心方法度量ES重要性，表示如下：
pi(center)＝drgee(pi) (17)
ES自身属性包括运行功率
Figure GDA0003470826170000071
CPU工作频率
Figure GDA0003470826170000072
等待列队处理能力
Figure GDA0003470826170000073
则ES的自身影响力表示为：
Figure GDA0003470826170000074
潜在影响力表示ES路径具有的潜在计算能力，包括与之相连的ES等级、交互强度、通信质量、性能，其中ES等级通过K-shell方法进行区分；设σ表示ES之间的交互频率强弱；Cqua表示ES之间通信质量，即传输信噪比；性能包括任务迁移时延
Figure GDA0003470826170000075
能耗
Figure GDA0003470826170000076
则ES的潜在影响力表达式为：
Figure GDA0003470826170000077
Figure GDA0003470826170000078
其中D(pi)为邻居节点pj的集合，ks为ES所处等级值，θ为随机分布变量，N0为噪声功率；
则ES路径影响力计算表示如下：
Figure GDA0003470826170000079
步骤5)中，所述的问题转化，是充分考虑ES计算能力、基站带宽资源、任务迁移时延与能耗因素，将用户体验质量QoE作为多终端迁移策略联合优化目标，构建近于实际应用环境中的密集型任务系统模型min Q：
Figure GDA00034708261700000710
将用户体验质量作为计算迁移策略优化目标转化为ES路径影响力最大化问题，计算迁移路径选择优化转化为ES路径影响力最大化，ES路径影响力最大化公式表示如下：
Figure GDA0003470826170000081
由公式(21)得：
Figure GDA0003470826170000082
由公式(22)得：
Figure GDA0003470826170000083
由于
Figure GDA0003470826170000084
ks、σ、Cqua均大于零，且
Figure GDA0003470826170000085
大于1，则minQ(K,L,′b)正比于
Figure GDA0003470826170000086
由此将用户体验质量作为迁移策略优化目标转化为ES路径影响力最大化问题。
步骤6)中，所述的KS-IMCO算法，其运行方法包括如下步骤：
6-1)依据度中心求解方法计算出每个ES的pi(center)值；
6-2)依据ES自身影响力模型计算出每个ES的
Figure GDA0003470826170000087
值；
6-3)依据K-shell方法计算出每个ES的ks值；
6-4)依据ES潜在影响力模型计算出每个ES的
Figure GDA0003470826170000088
值；
6-5)对每个初始ES进行路径统计，将任务量
Figure GDA0003470826170000089
按ES路径内数量划分，计算出每个ES路径L′的
Figure GDA00034708261700000810
值；
6-6)将每个ES路径L′统计出来，选择影响力最大路径进行计算迁移；
6-7)得到最终计算迁移路径。
本发明提供的一种基于K-shell影响力最大化计算迁移优化方法，该方法将边缘计算中计算迁移路径选择问题转化为社会网络影响力最大化问题，为计算迁移路径择优问题提供了新思路，将问题转换可以有效利用网络拓扑结构进行边缘服务器分层，节约路径搜寻时间，并且通过本方法求解计算迁移路径问题，可以有效提高边缘计算网络计算迁移的效率。
附图说明
图1为计算迁移系统模型示意图；
图2为计算迁移流程图；
图3是K-shell方法示意图；
图4是Ks-IMCO算法迁移计算与本地计算的MSD能耗对比；
图5是Ks-IMCO算法迁移计算的MSD节能百分比；
图6是MSD任务
Figure GDA0003470826170000091
为10～100bit时，ES数目为500个的实验结果对比图；
图7是MSD任务
Figure GDA0003470826170000092
为10～100bit时，ES数目为1000个的实验结果对比图；
图8是MSD任务
Figure GDA0003470826170000093
为10～100bit时，ES数目为2000个的实验对比图；
图9是MSD任务
Figure GDA0003470826170000094
为10～100bit时，ES数目为5000个的实验对比图；
图10是MSD任务
Figure GDA0003470826170000095
为10～100MB时，ES数目为500个的实验对比图；
图11是MSD任务
Figure GDA0003470826170000096
为10～100MB时，ES数目为1000个的实验对比图；
图12是MSD任务
Figure GDA0003470826170000097
为10～100MB时，ES数目为2000个的实验对比图；
图13是MSD任务
Figure GDA0003470826170000098
为10～100MB时，ES数目为5000个的实验对比图。
具体实施方式
下面结合附图和实施例对本发明内容做进一步阐述，但不是对本发明的限定。
一种基于K-shell影响力最大化计算迁移优化方法，包括如下步骤：
假设移动边缘计算系统由1个基站、n个边缘服务器和m个智能终端组成；n个边缘服务器共同构成网络G(P,E)，其中P为边缘服务器构成的集合，P＝{pi|i＝1,2,...,n}，E为边缘服务器连接矩阵；m个终端集合形式表示为D＝{dk|k＝1,2,...,m}，对于第k个终端dk的计算任务
Figure GDA0003470826170000099
由本地计算任务
Figure GDA00034708261700000910
与迁移计算任务
Figure GDA00034708261700000911
组成；
1)初始任务：当一个用户智能终端发布任务时，依据计算复杂度δk将任务分为本地计算与迁移计算；
2)本地计算：当任务属于本地计算时，依据MSD自身属性与本地任务量构建能耗与时延模型，计算本地能耗与时延；
设用户终端dk分配的任务
Figure GDA0003470826170000101
运行功率为
Figure GDA0003470826170000102
CPU频率为
Figure GDA0003470826170000103
则本地计算所需时延
Figure GDA0003470826170000104
与能耗
Figure GDA0003470826170000105
表示如下：
Figure GDA0003470826170000106
Figure GDA0003470826170000107
由公式(1)、(2)得本地计算服务质量公式
Figure GDA0003470826170000108
Figure GDA0003470826170000109
Figure GDA00034708261700001010
3)迁移计算：当任务属于迁移计算时，将能耗与时延分为传输部分和计算部分：
ES资源相对受限，多用户并发访问会导致网络堵塞，为解决该问题，是将密集型任务在ES上进行模拟选择最为适合的迁移路径，即ES路径L′＝(p1,p2,p3,...,pl)，其中l≤n；终端利用OFDMA信道连接请求ES，且每条信道之间相互独立；设θ为信道增益，
Figure GDA00034708261700001011
为dk至pi任务上行传输功率，
Figure GDA00034708261700001012
为ES路径内传输功率，
Figure GDA00034708261700001013
为任务下行传输功率，其中i<j<l，j＝i+1，bk为基站分配给dk的带宽，bk<bmax，B为基站带宽，N0为噪声平均功率，则上行传输速率
Figure GDA00034708261700001014
ES路径内传输速率
Figure GDA00034708261700001015
下行传输速率
Figure GDA00034708261700001016
根据香农定理表示为：
Figure GDA0003470826170000111
Figure GDA0003470826170000112
终端dk迁移到边缘的任务
Figure GDA0003470826170000113
在当前ES因资源受限无法完全计算时，将部分剩余任务迁移到与之相邻的ES，综合考虑传输、计算时延与能耗，迁移请求发起后，设传输过程中
Figure GDA0003470826170000114
为迁移到ES路径L′的计算任务，λ为计算结果复杂度0<λ<1，则上行传输时延Tloc,mec、ES路径内传输时延Tmec,mec、下行传输时延Tmec,loc分别表示为：
Figure GDA0003470826170000115
Figure GDA0003470826170000116
表示下行传输任务量，，上行传输能耗Eloc,mec、ES路径内能耗Emec,mec、下行传输能耗Emec,loc分别表示为：
Figure GDA0003470826170000121
根据公式(5)、(6)得传输时延Ttran、传输能耗Etran分别为：
Ttran＝Tloc,mec+Tmec,mec+Tmec,loc (7)
Etran＝Eloc,mec+Emec,mec+Emec,loc (8)
任务计算时，设pi的CPU工作频率为fmec,pi，运行功率为
Figure GDA0003470826170000122
最大计算任务能力为
Figure GDA0003470826170000123
则计算时延Tmec与计算能耗Emec模型为：
Figure GDA0003470826170000124
Figure GDA0003470826170000125
Figure GDA0003470826170000126
根据任务传输和计算两部分时延与能耗模型，得出迁移计算所需要的时延
Figure GDA0003470826170000127
与能耗
Figure GDA0003470826170000128
分别为：
Figure GDA0003470826170000129
Figure GDA00034708261700001210
由式(11)、(12)得迁移计算服务质量公式
Figure GDA00034708261700001211
Figure GDA00034708261700001212
Figure GDA00034708261700001213
则任务迁移需要的总时延
Figure GDA0003470826170000131
与总能耗
Figure GDA0003470826170000132
表示为：
Figure GDA0003470826170000133
Figure GDA0003470826170000134
由公式(14)、(15)得任务迁移服务质量公式
Figure GDA0003470826170000135
Figure GDA0003470826170000136
Figure GDA0003470826170000137
4)ES路径影响力：针对不同ES所组成集合的计算能力与传输能力不同进行评判的标准，由ES路径自身影响力与潜在影响力所构成，在潜在影响力的构成模型中充分考虑任务迁移过程中所消耗的能耗与时延；
ES自身影响力主要是考虑ES在网络中所处位置与自身属性；潜在影响力主要是考虑任务迁移所需时延、能耗与传输通信质量；依据网络拓扑结构，综合考虑ES在所在位置，利用度中心方法度量ES重要性，表示如下：
pi(center)＝drgee(pi) (17)
ES自身属性包括运行功率
Figure GDA0003470826170000138
CPU工作频率
Figure GDA0003470826170000139
等待列队处理能力
Figure GDA00034708261700001310
则ES的自身影响力表示为：
Figure GDA00034708261700001311
潜在影响力表示ES路径具有的潜在计算能力，包括与之相连的ES等级、交互强度、通信质量、性能，其中ES等级通过K-shell方法进行区分，如图3所示；设σ表示ES之间的交互频率强弱；Cqua表示ES之间通信质量，即传输信噪比；性能包括任务迁移时延
Figure GDA00034708261700001312
能耗
Figure GDA00034708261700001313
则ES的潜在影响力表达式为：
Figure GDA00034708261700001314
Figure GDA0003470826170000141
其中D(pi)为邻居节点pj的集合，ks为ES所处等级值，θ为随机分布变量，N0为噪声功率；
则ES路径影响力计算表示如下：
Figure GDA0003470826170000142
5)问题转化：将用户体验质量作为计算迁移策略优化目标转化为ES路径影响力最大化问题，其本质是计算迁移路径选择优化转化为ES路径影响力最大化；问题转化后，按照其路径搜寻规则可有效减少ES路径搜索消耗成本；
具体是充分考虑ES计算能力、基站带宽资源、任务迁移时延与能耗因素，将用户体验质量QoE作为多终端迁移策略联合优化目标，构建近于实际应用环境中的密集型任务系统模型min Q：
Figure GDA0003470826170000143
公式(21)为非凸优化问题，是一个NP难问题。针对NP难问题，考虑通信质量、ES交互强度等方面，将用户体验质量作为计算迁移策略优化目标转化为ES路径影响力最大化问题，计算迁移路径选择优化转化为ES路径影响力最大化，ES路径影响力最大化公式表示如下：
Figure GDA0003470826170000144
由公式(21)得：
Figure GDA0003470826170000145
由公式(22)得：
Figure GDA0003470826170000146
由于
Figure GDA0003470826170000147
ks、σ、Cqua均大于零，且
Figure GDA0003470826170000148
大于1，则
Figure GDA0003470826170000151
正比于
Figure GDA0003470826170000152
由此将用户体验质量作为迁移策略优化目标转化为ES路径影响力最大化问题。6)执行KS-IMCO算法：将ES类比为社会网络节点，利用K-shell方法将ES进行等级分类，结合贪心与启发式思想求解ES路径影响力最大化问题。
6)执行KS-IMCO算法：将ES类比为社会网络节点，利用K-shell方法将ES进行等级分类，结合贪心与启发式思想求解ES路径影响力最大化问题，KS-IMCO算法运行方法包括如下步骤：
6-1)依据度中心求解方法计算出每个ES的pi(center)值；
6-2)依据ES自身影响力模型计算出每个ES的
Figure GDA0003470826170000153
值；
6-3)依据K-shell方法计算出每个ES的ks值；
6-4)依据ES潜在影响力模型计算出每个ES的
Figure GDA0003470826170000154
值；
6-5)对每个初始ES进行路径统计，将任务量
Figure GDA0003470826170000155
按ES路径内数量划分，计算出每个ES路径L′的
Figure GDA0003470826170000156
值；
6-6)将每个ES路径L′统计出来，选择影响力最大路径进行计算迁移；
6-7)得到最终计算迁移路径。
实施例：
如图1、图2所示，采用本发明的一种基于K-shell影响力最大化计算迁移优化方法，是以社区为单位构建相应的应用场景。在一个社区内，分布多个MSD与ES，每个MSD与ES通过正交频分复用(OFDMA)信道相连，各个信道之间相互独立。在同一时刻，每个MSD将计算不同大小的任务，按照计算复杂度策略将任务进行分割，对于密集型任务通过信道进行计算迁移，完成多用户多服务器的边缘计算，具体仿真参数如表1所示。
表1仿真参数
Figure GDA0003470826170000157
Figure GDA0003470826170000161
实验一：本地计算与Ks-IMCO算法迁移计算能耗对比分析
本地计算迁移策略与Ks-IMCO算法迁移计算进行对比分析，实验过程中，将每个MSD任务随机设为10～100GB，在500个ES组成的数据集进行仿真，观察MSD数目由0至500过程中能耗所发生的变化。Ks-IMCO算法迁移计算能耗仅计算MSD分割后任务的本地计算能耗与上传能耗，实验结果如图4、图5所示。
实验结果表明：当系统MSD数目在100时，Ks-IMCO算法迁移计算节能效果最为明显，可以达到80％以上；系统MSD数目在100～450时，Ks-IMCO算法迁移计算节能效果都达到了70％以上；在350～450时，Ks-IMCO算法迁移计算节能效果趋于稳定，都维持在70％左右。因此，从能耗的角度来看，Ks-IMCO算法迁移计算能耗明显小于本地计算。
实验二：不同算法能耗与时延对比分析
为了验证算法的有效性，将Ks-IMCO算法与随机分配(Random Allocation，RA)算法、具有切换的路径选择(Path Selection with Handovers，PSwH)算法进行时延与能耗对比分析，RA算法、PSwH算法的介绍如下：
1)随机分配(RA)算法：在任务迁移过程中，对迁移任务进行随机分配迁移路径，并进行计算路径与能耗，未对路径进行选择优化。
2)具有切换的路径选择(PSwH)算法：在任务迁移过程中，通过对任务迁移到单一ES的能耗与时延作为马尔可夫决策指标，按照该决策过程进行任务迁移路径切换选择，并未考虑整条路径的时延、能耗与ES的列队处理能力、相邻ES之间的交互强度等因素。
MSD任务
Figure GDA0003470826170000171
包含的数量级不一样，代表计算任务种类不同。
Figure GDA0003470826170000172
为10～100bit时，代表纯文本文件，实验结果如图6～9所示；
Figure GDA0003470826170000173
为10～100MB时，代表流式文件(图、文本、视音频)，实验结果如图10～13所示。因此，针对Ks-IMCO算法与RA算法、PSwH算法分别在不同场景下进行时延与能耗对比实验，实验过程中，分别将MSD数目由0到500逐渐增加观察时延与能耗性能。为了提高实验的准确性，针对ES网络规模，分别以ES数目为500、1000、2000、5000的数据集进行了实验。
实验结果表明：对于不同形式的任务，当ES规模为500，MSD数目为500时，Ks-IMCO算法较RA算法节能60～70％，时延缩短41～48％，较PSwH算法节能13～15％左右，时延缩短12～15％左右；当ES规模为500，MSD数目为1000时，Ks-IMCO算法较RA算法节能45～55％，时延缩短35～40％，较PSwH算法节能24～26％，时延缩短30～36％；当ES规模为500，MSD数目为2000时，Ks-IMCO算法较RA算法节能65～70％，时延缩短43～55％，较PSwH算法节能40～55％，时延缩短38～47％；当ES规模为5000，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算法能有效提高用户服务质量。
综上所述：Ks-IMCO算法迁移计算较本地计算能耗有效节能在70％左右；对于不同形式的任务，Ks-IMCO算法在能耗与时延方面都优于RA、PSwH算法。

Claims (2)

1.一种基于K-shell影响力最大化计算迁移优化方法，其特征在于，该方法是假设移动边缘计算系统由1个基站、n个边缘服务器和m个智能终端组成；n个边缘服务器共同构成网络G(P,E)，其中P为边缘服务器构成的集合，P＝{pi|i＝1,2,...,n}，E为边缘服务器连接矩阵；m个终端集合形式表示为D＝{dk|k＝1,2,...,m}，对于第k个终端dk的计算任务
Figure FDA0003470826160000011
由本地计算任务
Figure FDA0003470826160000012
与迁移计算任务
Figure FDA0003470826160000013
组成；具体包括如下步骤：
1)初始任务：当一个用户智能终端发布任务时，依据计算复杂度δk将任务分为本地计算与迁移计算；
2)本地计算：当任务属于本地计算时，依据移动智能设备(Mobile Smart Device，MSD)自身属性与本地任务量构建能耗与时延模型，计算本地能耗与时延；
本地能耗与时延的计算，是设用户终端dk分配的任务
Figure FDA0003470826160000014
运行功率为
Figure FDA0003470826160000015
CPU频率为
Figure FDA0003470826160000016
则本地计算所需时延
Figure FDA0003470826160000017
与能耗
Figure FDA0003470826160000018
表示如下：
Figure FDA0003470826160000019
Figure FDA00034708261600000110
由公式(1)、(2)得本地计算服务质量公式
Figure FDA00034708261600000111
Figure FDA00034708261600000112
Figure FDA00034708261600000113
3)迁移计算：当任务属于迁移计算时，将能耗与时延分为传输部分和计算部分：
3-1)传输部分的能耗与时延分为上行传输、边缘服务器(Edge Server，ES)路径内传输、下行传输三部分，其中上行传输代表将任务从用户终端传输到边缘服务器，ES路径内传输代表任务在边缘服务器组内传输，下行传输代表将服务器任务计算结果回传到用户终端；
3-2)计算部分的能耗与时延依据ES自身属性与本地任务量构建能耗与时延模型，描述任务迁移在服务器上任务计算所需的能耗与时延；
所述的迁移计算，是将密集型任务在ES上进行模拟选择最为适合的迁移路径，即ES路径L′＝(p1,p2,p3,...,pl)，其中l≤n；终端利用OFDMA信道连接请求ES，且每条信道之间相互独立；设θ为信道增益，
Figure FDA0003470826160000021
为dk至pi任务上行传输功率，
Figure FDA0003470826160000022
为ES路径内传输功率，
Figure FDA0003470826160000023
为任务下行传输功率，其中i<j<l，j＝i+1，bk为基站分配给dk的带宽，bk<bmax，B为基站带宽，N0为噪声平均功率，则上行传输速率
Figure FDA0003470826160000024
ES路径内传输速率
Figure FDA0003470826160000025
下行传输速率
Figure FDA0003470826160000026
根据香农定理表示为：
Figure FDA0003470826160000027
终端dk迁移到边缘的任务
Figure FDA0003470826160000028
在当前ES因资源受限无法完全计算时，将部分剩余任务迁移到与之相邻的ES，综合考虑传输、计算时延与能耗，迁移请求发起后，设传输过程中
Figure FDA0003470826160000029
为迁移到ES路径L′的计算任务，λ为计算结果复杂度0<λ<1，则上行传输时延Tloc,mec、ES路径内传输时延Tmec,mec、下行传输时延Tmec,loc分别表示为：
Figure FDA0003470826160000031
Figure FDA0003470826160000032
表示下行传输任务量，上行传输能耗Eloc,mec、ES路径内能耗Emec,mec、下行传输能耗Emec,loc分别表示为：
Figure FDA0003470826160000033
根据公式(5)、(6)得传输时延Ttran、传输能耗Etran分别为：
Ttran＝Tloc,mec+Tmec,mec+Tmec,loc (7)
Etran＝Eloc,mec+Emec,mec+Emec,loc (8)
任务计算时，设pi的CPU工作频率为
Figure FDA0003470826160000034
运行功率为
Figure FDA0003470826160000035
最大计算任务能力为
Figure FDA0003470826160000036
则计算时延Tmec与计算能耗Emec模型为：
Figure FDA0003470826160000037
Figure FDA0003470826160000041
根据任务传输和计算两部分时延与能耗模型，得出迁移计算所需要的时延
Figure FDA0003470826160000042
与能耗
Figure FDA0003470826160000043
分别为：
Figure FDA0003470826160000044
Figure FDA0003470826160000045
由式(11)、(12)得迁移计算服务质量公式
Figure FDA0003470826160000046
Figure FDA0003470826160000047
Figure FDA0003470826160000048
则任务迁移需要的总时延
Figure FDA0003470826160000049
与总能耗
Figure FDA00034708261600000410
表示为：
Figure FDA00034708261600000411
Figure FDA00034708261600000412
由公式(14)、(15)得任务迁移服务质量公式
Figure FDA00034708261600000413
Figure FDA00034708261600000414
Figure FDA00034708261600000415
4)ES路径影响力：针对不同ES所组成集合的计算能力与传输能力不同进行评判的标准，由ES路径自身影响力与潜在影响力所构成，在潜在影响力的构成模型中充分考虑任务迁移过程中所消耗的能耗与时延；
所述的ES路径影响力，包括ES自身影响力和潜在影响力；ES自身影响力是考虑ES在网络中所处位置与自身属性；潜在影响力主要是考虑任务迁移所需时延、能耗与传输通信质量；依据网络拓扑结构，综合考虑ES在所在位置，利用度中心方法度量ES重要性，表示如下：
pi(center)＝drgee(pi) (17)
ES自身属性包括运行功率
Figure FDA0003470826160000051
CPU工作频率
Figure FDA0003470826160000052
等待列队处理能力
Figure FDA0003470826160000053
则ES的自身影响力表示为：
Figure FDA0003470826160000054
潜在影响力表示ES路径具有的潜在计算能力，包括与之相连的ES等级、交互强度、通信质量、性能，其中ES等级通过K-shell方法进行区分；设σ表示ES之间的交互频率强弱；Cqua表示ES之间通信质量，即传输信噪比；性能包括任务迁移时延
Figure FDA0003470826160000055
能耗
Figure FDA0003470826160000056
则ES的潜在影响力表达式为：
Figure FDA0003470826160000057
Figure FDA0003470826160000058
其中D(pi)为邻居节点pj的集合，ks为ES所处等级值，θ为随机分布变量，N0为噪声功率；
则ES路径影响力计算表示如下：
Figure FDA0003470826160000059
5)问题转化：将用户体验质量作为计算迁移策略优化目标转化为ES路径影响力最大化问题，其本质是计算迁移路径选择优化转化为ES路径影响力最大化；
6)执行KS-IMCO算法：将ES类比为社会网络节点，利用K-shell方法将ES进行等级分类，结合贪心与启发式思想求解ES路径影响力最大化问题；
所述的KS-IMCO算法，其运行方法包括如下步骤：
6-1)依据度中心求解方法计算出每个ES的pi(center)值；
6-2)依据ES自身影响力模型计算出每个ES的
Figure FDA0003470826160000061
值；
6-3)依据K-shell方法计算出每个ES的ks值；
6-4)依据ES潜在影响力模型计算出每个ES的
Figure FDA0003470826160000062
值；
6-5)对每个初始ES进行路径统计，将任务量
Figure FDA0003470826160000063
按ES路径内数量划分，计算出每个ES路径L′的
Figure FDA0003470826160000064
值；
6-6)将每个ES路径L′统计出来，选择影响力最大路径进行计算迁移；
6-7)得到最终计算迁移路径。
2.根据权利要求1所述的一种基于K-shell影响力最大化计算迁移优化方法，其特征在于，步骤5)中，所述的问题转化，是充分考虑ES计算能力、基站带宽资源、任务迁移时延与能耗因素，将用户体验质量QoE作为多终端迁移策略联合优化目标，构建近于实际应用环境中的密集型任务系统模型min Q：
Figure FDA0003470826160000065
将用户体验质量作为计算迁移策略优化目标转化为ES路径影响力最大化问题，计算迁移路径选择优化转化为ES路径影响力最大化，ES路径影响力最大化公式表示如下：
Figure FDA0003470826160000066
由公式(21)得：
Figure FDA0003470826160000067
由公式(22)得：
Figure FDA0003470826160000068
由于
Figure FDA0003470826160000071
ks、σ、Cqua均大于零，且
Figure FDA0003470826160000072
大于1，则
Figure FDA0003470826160000074
正比于
Figure FDA0003470826160000073
由此将用户体验质量作为迁移策略优化目标转化为ES路径影响力最大化问题。
CN202010677809.3A 2020-07-15 2020-07-15 一种基于K-shell影响力最大化计算迁移优化方法 Active CN111836328B (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN202010677809.3A CN111836328B (zh) 2020-07-15 2020-07-15 一种基于K-shell影响力最大化计算迁移优化方法

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN202010677809.3A CN111836328B (zh) 2020-07-15 2020-07-15 一种基于K-shell影响力最大化计算迁移优化方法

Publications (2)

Publication Number Publication Date
CN111836328A CN111836328A (zh) 2020-10-27
CN111836328B true CN111836328B (zh) 2022-03-15

Family

ID=72922862

Family Applications (1)

Application Number Title Priority Date Filing Date
CN202010677809.3A Active CN111836328B (zh) 2020-07-15 2020-07-15 一种基于K-shell影响力最大化计算迁移优化方法

Country Status (1)

Country Link
CN (1) CN111836328B (zh)

Families Citing this family (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN114979134B (zh) * 2022-04-21 2023-01-17 云南大学 边缘计算环境中服务迁移的路径选择方法

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN111031102A (zh) * 2019-11-25 2020-04-17 哈尔滨工业大学 一种多用户、多任务的移动边缘计算系统中可缓存的任务迁移方法
CN111148174A (zh) * 2019-12-13 2020-05-12 北京邮电大学 一种移动边缘计算中服务迁移路径选择方法
CN111212108A (zh) * 2019-12-12 2020-05-29 西安电子科技大学 基于非正交多址接入和移动边缘计算多用户并行迁移方法

Family Cites Families (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US10887198B2 (en) * 2017-09-29 2021-01-05 Nec Corporation System and method to support network slicing in an MEC system providing automatic conflict resolution arising from multiple tenancy in the MEC environment
CN109286664A (zh) * 2018-09-14 2019-01-29 嘉兴学院 一种基于拉格朗日的计算迁移终端能耗优化方法
US11412052B2 (en) * 2018-12-28 2022-08-09 Intel Corporation Quality of service (QoS) management in edge computing environments
CN110062026A (zh) * 2019-03-15 2019-07-26 重庆邮电大学 移动边缘计算网络中资源分配和计算卸载联合优化方案

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN111031102A (zh) * 2019-11-25 2020-04-17 哈尔滨工业大学 一种多用户、多任务的移动边缘计算系统中可缓存的任务迁移方法
CN111212108A (zh) * 2019-12-12 2020-05-29 西安电子科技大学 基于非正交多址接入和移动边缘计算多用户并行迁移方法
CN111148174A (zh) * 2019-12-13 2020-05-12 北京邮电大学 一种移动边缘计算中服务迁移路径选择方法

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
基于k-shell 的复杂网络影响力最大化;曹迪;《中国优秀硕士学位论文全文数据库》;20180615;全文 *

Also Published As

Publication number Publication date
CN111836328A (zh) 2020-10-27

Similar Documents

Publication Publication Date Title
CN108809695B (zh) 一种面向移动边缘计算的分布上行链路卸载策略
CN111132235B (zh) 基于改进hrrn算法和多属性决策的移动卸载迁移算法
Liu et al. An energy-efficient task scheduling for mobile devices based on cloud assistant
CN102196579B (zh) 异构无线网络并行多接入系统中联合资源分配快速算法
CN109286664A (zh) 一种基于拉格朗日的计算迁移终端能耗优化方法
CN107172704B (zh) 基于协作频谱感知和干扰约束的认知异构网络功率分配方法
CN104619029B (zh) 一种集中式蜂窝网络架构下的基带池资源分配方法和装置
CN110351754A (zh) 基于Q-learning的工业互联网机器设备用户数据计算卸载决策方法
CN111475274A (zh) 云协同多任务调度方法及装置
CN111935205B (zh) 雾计算网络中基于交替方向乘子法的分布式资源分配方法
Feng et al. Energy-efficient user selection and resource allocation in mobile edge computing
Li et al. Computation offloading strategy for improved particle swarm optimization in mobile edge computing
Chen et al. Time-efficient task caching strategy for multi-server mobile edge cloud computing
CN111836328B (zh) 一种基于K-shell影响力最大化计算迁移优化方法
Yan et al. Fairness-aware data offloading of IoT applications enabled by heterogeneous UAVs
Wang et al. Power-minimization computing resource allocation in mobile cloud-radio access network
Cai et al. Game theory-based device-to-device network access algorithm for heterogeneous networks
CN102711259B (zh) 基于马尔科夫过程的无线异构网络吞吐量优化方法
CN110602718B (zh) 基于交替方向乘子法的异构蜂窝网络功率分配方法及系统
Lu et al. Research on user access selection mechanism based on maximum throughput for 5G network slicing
CN107018528B (zh) 一种单小区lte-a系统中基于等效容量的无线网络虚拟化方法
CN105516636A (zh) 一种基于视频通信的异构网络多接入资源分配方法
CN113784372B (zh) 一种面向终端多业务模型的联合优化方法
Wang et al. PSOGT: PSO and game theoretic based task allocation in mobile edge computing
Xin et al. Online node cooperation strategy design for hierarchical federated learning

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant