边缘计算卸载算法--LOPRTC LOPRTC卸载算法
背景：我实现该算法是在边缘计算单个⼯作流环境中，下⾯可以看到此背景下的java代码实现。
1.算法伪代码
2.输⼊
任务集等…
3.输出
接近最优的任务调度。
4.参数说明
城乡教育差距
1.MD：移动设备
2.RLTS：合理的基于本地的任务时间表
3.MEC服务器集S = {S1,S2,…,SM}
4.任务集T = {T1,T2,…,TN}
5.每个Job的处理时间P = {P0,P1,…,Pn-1}
6.某设备的⾏⾛路径：P = {(Au1,tu1),(Au2,tu2),…(Aup,tup)}，其中tu是⼀个任意的时间点。
7.移动设备集S0 = {SM+1,SM+2,…,SM+L}
8.⼀个区域A = {Au}
9.整数q
10.dj：⼯作流任务最长执⾏时间
5.分析
1. 算法2-5⾏：将N个任务划分成N/q(向上取整)个组。1<= q <= N
2. 算法6-17⾏：任务调度优化，For 0≤k≤(N / q), 计算局部最优任务调度
① 计算第 k 组中所有任务的最早开始时间与完成所有任务的最晚结束时间（第k组的最晚结束时间是第 k+1 组的最早开始时间）。
② 为第 k 组中的每个任务 Tj 计算候选卸载MEC服务器集CSj，每个任务 Tj 可以卸载到覆盖其⾏⾛路径的MEC服务器，在时间间隔
[第k组的最早开始时间, min {dj, 第k组的最晚结束时间}]。
③ 计算第 k 组任务的局部最优任务调度（利⽤分⽀限界法）。
3. 算法18⾏：通过这些局部最优任务调度，计算所有任务（各组的并集）的近似最优任务调度。
本质：还是类似枚举，只是利⽤时间限制剪掉了⼀些情况的组合。
6.我的java代码实现
/**
* 初始化的⽅法
手机传输
* 初始化任务的邻接矩阵，任务、组的最早开始时间与最晚结束时间
*/
void LOPRTCInit(){
// 卸载策略数组初始化
offloadStra =new int[taskNum];
for(int i =0; i < taskNum; i++){
offloadStra[i]=0;
}
// 邻接矩阵初始化
task_depen =new int[taskNum][taskNum];
for(int i =0; i < taskNum; i++){
for(int j =0; j < taskNum; j++){
task_depen[i][j]=0;
}
}
try{
SAXReader reader =new SAXReader();// 创建SAXReader对象⽤于读取xml⽂件
Document doc = ad(new File(path));// 读取xml⽂件，获得Document对象
Element root = RootElement();
List<Element> childElements = root.elements("child");// 获取根元素下的所有child标签的⼦元素for(int i =0; i < childElements.size(); i++){
String vex_str = (i).attributeValue("ref");
int vex_int = Integer.parInt(vex_str.substring(2));
List<Element> parents = (i).elements("parent");// 获取child元素下的所有parent标签元素for(int j =0; j < parents.size(); j++){
String vex_parent_str = (j).attributeValue("ref");
int vex_parent_int = Integer.parInt(vex_parent_str.substring(2));
task_depen[vex_parent_int][vex_int]=1;
}
}
}catch(Exception e){
System.out.println("xml没找到！");
}
// 每个任务的执⾏时间初始化
task_exec =new double[taskNum];
try{
SAXReader reader =new SAXReader();// 创建SAXReader对象⽤于读取xml⽂件
Document doc = ad(new File(path));// 读取xml⽂件，获得Document对象
Element root = RootElement();
List<Element> jobElements = root.elements("job");// 获取根元素下的所有job标签的⼦元素for(int i =0; i < jobElements.size(); i++){
渡浙江问舟中人String vexStr = (i).attributeValue("id");
int vexInt = Integer.parInt(vexStr.substring(2));
String timeStr = (i).attributeValue("runtime");
double timeDouble = Double.parDouble(timeStr);
task_exec[vexInt]= timeDouble;
}
}catch(Exception e){
System.out.println("xml没找到！");
}
// 每个任务的EST、EFT矩阵初始化
task_time =new double[taskNum][2];
int count =0;// 辅助变量
for(int k =0; k < taskNum;++k){
for(int j =0; j < taskNum; j++){// 初始化开始节点的EST、EFT
if(task_depen[j][k]==0){
++count;
}
}
if(count == taskNum){
task_time[k][0]=0;
task_time[k][1]= task_exec[k];
for(int j =0; j < taskNum; j++){// 初始化开始节点直接后继节点的EST、EFT
if(task_depen[k][j]==1){
if(task_time[j][0]< task_time[k][1]){
task_time[j][0]= task_time[k][1];
task_time[j][1]= task_time[j][0]+ task_exec[j];
}
}
}
}
count =0;
}
for(int k =0; k < taskNum;++k){// 初始化剩下的所有节点的EST、EFT
for(int j =0; j < taskNum; j++){
if(task_depen[k][j]==1){
if(task_time[j][0]< task_time[k][1]){
task_time[j][0]= task_time[k][1];
task_time[j][1]= task_time[j][0]+ task_exec[j];
}
}
}
}
// 计算分⼏组
if(taskNum %6==0){// 分6组
groupStartTime =new double[6];
groupEndTime =new double[6];《回乡偶书》
}el{
groupStartTime =new double[7];
groupEndTime =new double[7];
}
/
/ 测试输出
/*for (int i = 0; i < taskNum; i++) {
for (int j = 0; j < 2; j++) {
System.out.print(task_time[i][j] + " ");
}
System.out.println();
}
System.out.println();*/
// 计算每组的最早开始时间，最晚结束时间
try{
for(int i =0; i < groupStartTime.length; i++){
double minStart = task_time[i*q][0];
for(int j = i*q; j<(i+1)*q && j<taskNum; j++){
if(minStart > task_time[j][0]){
minStart = task_time[j][0];
}
}
groupStartTime[i]= minStart;
}
}catch(Exception e){
System.out.println("数组下标越界异常！");
}
for(int i =0; i < groupEndTime.length-1; i++){
groupEndTime[i]= groupStartTime[i+1];
}
double maxEnd = task_time[0][1];
for(int i =1; i < taskNum; i++){
if(task_time[i][1]> maxEnd){
maxEnd = task_time[i][1];
}
}
groupEndTime[groupEndTime.length-1]= maxEnd;
}
/
**
* 找出某组任务的局部最优卸载策略
* @param indexOfGroup 某组任务的索引下标（第⼀组任务对应下标为0）
*/
void groupOptimal(int indexOfGroup){
// 依次是卸载到云层、雾层、本地
double time1 =0, time2 =0, time3 =0;
double energy1 =0, energy2 =0, energy3 =0;
powerModel =(FogLinearPowerModel)getmobile().getHost().getPowerModel();
// 获取云、雾、终端层的平均Mips
double cAvgMips =getcloud().getAverageMips();
double fAvgMips =getFogNode().getAverageMips();
double mAvgMips =getmobile().getAverageMips();
参差不齐的意思try{
for(int i = indexOfGroup*q; i<(indexOfGroup+1)*q && i<taskNum; i++){
Job job = (i);
怎样让瘦人变胖
time1 = CloudletLength()/ cAvgMips
+getJobFileSize(job)/ parameter / WAN_Bandwidth;
//卸载所需能耗 = 空闲功率 * 云执⾏时间 + 传输功率 * (发送数据⼤⼩ + 接收数据⼤⼩ ) / WAN带宽 energy1 = StaticPower()* CloudletLength()/ cAvgMips
energy1 = StaticPower()* CloudletLength()/ cAvgMips
+ SendPower()*getJobFileSize(job)/ parameter / WAN_Bandwidth;
time2 = CloudletLength()/ fAvgMips
+getJobFileSize(job)/ parameter / LAN_Bandwidth;
energy2 = StaticPower()* CloudletLength()/ fAvgMips
+ SendPower()*getJobFileSize(job)/ parameter / LAN_Bandwidth;
time3 = CloudletLength()/ mAvgMips;
energy3 = MaxPower()* CloudletLength()/ mAvgMips;
double minTimeSpan = Math.min(deadline,groupEndTime[indexOfGroup]-groupStartTime[indexOfGroup]);
if(minTimeSpan < Math.min(time1, time2)){// 都不满⾜时间约束
}el if(minTimeSpan > Math.max(time1, time2)){// 都满⾜时间约束，根据优化⽬标选择卸载到哪
switch(optimize_objective){
ca"Time":
if(Math.min(time1, Math.min(time2, time3))== time1){
offloadStra[i]=2;// 卸载到云
}el if(Math.min(time1, Math.min(time2, time3))== time2){
offloadStra[i]=1;// 卸载到雾
}el{
offloadStra[i]=0;// 不卸载
}
break;
ca"Energy":
if(Math.min(energy3, Math.min(energy1, energy2))== energy1){
offloadStra[i]=2;
}
el if(Math.min(energy3, Math.min(energy1, energy2))== energy2){
offloadStra[i]=1;
}
el{
offloadStra[i]=0;
}
break;
default:
break;
}
}el{//minTimeSpan介于time1和time2之间
if(minTimeSpan > time1 && minTimeSpan < time2){// 根据优化⽬标选择卸载到云或不卸载
switch(optimize_objective){
有毒图片ca"Time":
if(Math.min(time1, time3)== time1){
offloadStra[i]=2;
}el{
offloadStra[i]=0;
}
break;
ca"Energy":
if(Math.min(energy1, energy3)== energy1){
offloadStra[i]=2;
}el{
offloadStra[i]=0;
}
break;
default:银耳做法
break;
}
}el{// 根据优化⽬标选择卸载到雾或不卸载
switch(optimize_objective){
ca"Time":
if(Math.min(time2, time3)== time2){
offloadStra[i]=1;
}el{
offloadStra[i]=0;
