高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于模拟退火机制的车辆用户移动边缘计算任务卸载新方法

张德干 李霞 张捷 张婷 龚倡乐

张德干, 李霞, 张捷, 张婷, 龚倡乐. 基于模拟退火机制的车辆用户移动边缘计算任务卸载新方法[J]. 电子与信息学报, 2022, 44(9): 3220-3230. doi: 10.11999/JEIT210102
引用本文: 张德干, 李霞, 张捷, 张婷, 龚倡乐. 基于模拟退火机制的车辆用户移动边缘计算任务卸载新方法[J]. 电子与信息学报, 2022, 44(9): 3220-3230. doi: 10.11999/JEIT210102
ZHANG Degan, LI Xia, ZHANG Jie, ZHANG Ting, GONG Changle. New Method of Task Offloading in Mobile Edge Computing for Vehicles Based on Simulated Annealing Mechanism[J]. Journal of Electronics & Information Technology, 2022, 44(9): 3220-3230. doi: 10.11999/JEIT210102
Citation: ZHANG Degan, LI Xia, ZHANG Jie, ZHANG Ting, GONG Changle. New Method of Task Offloading in Mobile Edge Computing for Vehicles Based on Simulated Annealing Mechanism[J]. Journal of Electronics & Information Technology, 2022, 44(9): 3220-3230. doi: 10.11999/JEIT210102

基于模拟退火机制的车辆用户移动边缘计算任务卸载新方法

doi: 10.11999/JEIT210102
基金项目: 国家自然科学基金(61571328),天津市重大科技专项(15ZXDSGX00050, 16ZXFWGX00010),天津市科技支撑重点项目(17YFZCGX00360),天津市自然科学基金(18JCZDJC96800, 18JCYBJC19300),天津市科技创新和131人才团队(TD13-5025, 2015-23)
详细信息
    作者简介:

    张德干:男,教授,博士生导师,研究方向为车联网、服务计算等

    李霞:女,硕士生,研究方向为车联网、移动计算等

    张捷:男,学士,研究方向为车联网、无线传感网络等

    张婷:女,教授,研究方向为车联网、移动计算等

    龚倡乐:男,硕士生,研究方向为移动计算

    通讯作者:

    李霞 718985622@qq.com

  • 中图分类号: TN919; TP393

New Method of Task Offloading in Mobile Edge Computing for Vehicles Based on Simulated Annealing Mechanism

Funds: The National Natural Science Foundation of China (61571328), Tianjin Major Science and Technology Special Projects (15ZXDSGX00050, 16ZXFWGX00010), Tianjin Science and Technology Support Key Projects (17YFZCGX00360), Tianjin Natural Science Foundation (18JCZDJC96800,18JCYBJC19300), Tianjin Science and Technology Innovation and 131 Talent Team (TD13-5025, 2015-23)
  • 摘要: 在车联网(IOV)环境中,如果将车辆的计算任务都放置在云平台执行,无法满足对于信息处理的实时性,考虑移动边缘计算技术以及任务卸载策略,将用户的计算任务卸载到靠近设备边缘的服务器去执行。但是在密集的环境下,如果所有的任务都卸载到附近的边缘服务器去执行,同样会给边缘服务器带来巨大的负载。该文提出基于模拟退火机制的车辆用户移动边缘计算任务卸载新方法,通过定义用户的任务计算卸载效用,综合考虑时耗和能耗,结合模拟退火机制,根据当前道路的密集程度对系统卸载效用进行优化,改变用户的卸载决策,选择在本地执行或者卸载到边缘服务器上执行,使得在给定的环境下的所有用户都能得到满足低时延高质量的服务。仿真结果表明,该算法在减少用户任务计算时间的同时降低了能量消耗。
  • 图  1  场景模型

    图  2  OFDM与OFDMA工作模式对比

    图  3  不同时耗偏好下任务计算时间

    图  4  不同时耗偏好下任务能量消耗

    图  5  不同MEC服务器数量下能耗对比图

    图  6  不同MEC服务器数量下时耗对比图

    图  7  不同MEC服务器数量下用户任务卸载效用对比图

    图  8  不同车流量下时耗对比图

    图  9  不同车流量下能耗对比图

    图  10  不同车流量下用户卸载效用对比图

    图  11  1 d时间长度内车流量统计图

    图  12  1 d时间长度内任务计算时间对比图

    图  13  1 d时间长度内用户能量消耗对比图

    表  1  变量符号及含义

    变量符号含义
    $ V $用户
    $ M $服务器
    $ {T}_{v} $用户计算任务
    $ {t}_{v}^{\mathrm{l}\mathrm{o}\mathrm{c}} $用户在本地执行任务时耗
    $ {e}_{v}^{\mathrm{l}\mathrm{o}\mathrm{c}} $用户在本地执行任务能耗
    $ {E}_{v,m}^{n} $用户选择服务器上任意频带n进行传输
    ${{\boldsymbol{p}}}_{v}^{\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{n} }$用户输出功率
    $ {C}_{v,m} $信息传送速率
    $ {t}_{v}^{\text{tran}} $用户将任务上传所需时间
    $ {t}_{v}^{\mathrm{c}\mathrm{o}\mathrm{m}} $任务在服务器的执行时间
    $ {t}_{v}^{\mathrm{o}\mathrm{f}\mathrm{f}} $任务卸载到边缘的时间消耗
    $ {e}_{v}^{\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{n}} $任务卸载到边缘的时间能耗
    $ {Q}_{v} $用户卸载效用
    $ {\lambda }_{1} $时耗偏好
    $ {\lambda }_{2} $能耗偏好
    下载: 导出CSV

    表  2  生成初始温度(算法1)

     输入:v, m, n
     //初始用户数量,边缘服务器数量,每个边缘服务器子频带数量
     offload(v,m,n)=zeros(v,m,n)
     //所有用户都没有卸载任务
     Qv_old=0;
     //此时所有用户的卸载效用为0
     for user=1:v
      for server=1:m
       for sub_server=1:n
     //每个边缘服务器配置7个子频带
     $ {Q}_{v}=\left({\lambda }_{1}\dfrac{{t}_{v}^{\mathrm{l}\mathrm{o}\mathrm{c}}-{t}_{v}^{\mathrm{o}\mathrm{f}\mathrm{f}}}{{t}_{v}^{\mathrm{l}\mathrm{o}\mathrm{c}}}+{\lambda }_{2}\dfrac{{e}_{v}^{\mathrm{l}\mathrm{o}\mathrm{c}}-{e}_{v}^{\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{n}}}{{e}_{v}^{\mathrm{l}\mathrm{o}\mathrm{c}}}\right){\displaystyle\sum }_{m\in M}{E}_{v,m},\forall v\in V $
     //根据式(12),用户选择满足自身卸载效用最大的方式执行任务
     if (Qv_new>Qv_old)
       offload(v,m,n)=0
     else offload(v,m,n)=1
        end
      //如果卸载效用低于之前的效用则不进行卸载
       end
      end
     end
     输出:offload(v,m,n) //得到用户初始的任务卸载策略
    下载: 导出CSV

    表  3  状态转换(算法2)

     输入:offload(v, m, n)
     //当前任务卸载策略,初始用户数量,边缘服务器数量,每个边
     缘服务器子频带数量
       v_change=unidrnd(v)
       //选择改变执行方式的用户
       [thism,thisn]=find(v,m,n)
       //找到用户当前的任务执行方式
       if(change>rand)
       //改变任务在本地/服务器执行
        offload(v,thism,thisn)=1-offload(v,thism,thisn)
       else if (offload(v,thism,thisn)==1)
       if(M_change>rand)
        nowm =unidrnd(m) //改变所选的卸载的服务器
        offload(v,thism,thisn)=0
        offload(v,nowm,thisn)=1
       else //改变当前服务器所选择的子频带
        nown=unidrnd(n)
        offload(v,thism,thisn)=0
        offload(v,thism,nown)=1
        end
       end
       输出:offload(v, m, n) //新的卸载策略
    下载: 导出CSV

    表  4  基于模拟退火机制的边缘计算任务卸载算法(算法3)

      输入:v, m, n, paras
      //初始用户数量,边缘服务器数量,每个边缘服务器子频带数
      量,其他设定参数
      Offload=Offload_old=getORI(v,m,n)
      //根据算法1,得到初始卸载策略
      Q=Q_old=getQ(offload_old,paras)
      //根据式(15),计算出卸载效用,并看作当前“最优解”
      while(T>T_end && i<i_end)
     //如果没有达到设定的终止温度,在规定的迭代次数范围内
      for usr=1:k //定义每次改变策略的用户数量为k
         offload_new=changeoff(v,m,n)
         Q_new=getQ(offload_new,paras)
         deltQ=Q_new-Qold
      if(delQ>0)
      //如果本次策略卸载效用高于上一次,则接受本次策略
         offload_old=offload_new
         Q_old=Q_new
      if(Q_new>Q)
      //如果本次策略卸载效用高于目前的最优解,则替代之前的解
          Q=Q_new
          offload=offload_new
         end
      else if getP>rand
     //根据式(16)计算降温概率并判断是否接受本次策略
         offload_old=offload_new
         Q_old=Q_new
        end
       end
       T=aT //根据降温系数改变温度
      end
      输出:Q,Offload
      //当达到终止温度或者规定的迭代次数,终止退火,此时得到
      的用户卸载效用即是函数的最优解。
    下载: 导出CSV

    表  5  仿真参数

    仿真参数取值
    服务器个数(个)4,9,16,25
    车流量大小(辆)30–Vmax
    V3max = 110
    每个服务器的子频带数量(个)7
    计算任务大小(kb)480
    服务器间距(km)1
    能耗系数(J/bit)$ {5.0\times 10}^{-27} $
    服务器带宽(MHz)75
    终止温度$ {10}^{-9} $
    温度下降率0.97
    领域解空间大小5
    权重$ {\mathit{\lambda }}_{1}{,\mathit{\lambda }}_{2} $1/2,1/2
    下载: 导出CSV
  • [1] MELAOUENE N and ROMADI R. An enhanced routing algorithm using ant colony optimization and VANET infrastructure[J]. MATEC Web of Conferences, 2019, 259: 02009. doi: 10.1051/matecconf/201925902009
    [2] BRENNAND C A R L, DE SOUZA A M, MAIA G, et al. An intelligent transportation system for detection and control of congested roads in urban centers[C]. 2015 IEEE Symposium on Computers and Communication (ISCC), Larnaca, Cyprus, 2015: 663–668.
    [3] CHEN Jieqiong, MAO Guoqiang, LI Changle, et al. Capacity of cooperative vehicular networks with infrastructure support: Multiuser case[J]. IEEE Transactions on Vehicular Technology, 2018, 67(2): 1546–1560. doi: 10.1109/TVT.2017.2753772
    [4] XU Xiaolong, LI Yuancheng, HUANG Tao, et al. An energy-aware computation offloading method for smart edge computing in wireless metropolitan area networks[J]. Journal of Network and Computer Applications, 2019, 133: 75–85. doi: 10.1016/j.jnca.2019.02.008
    [5] ZHANG Ke, MAO Yuming, LENG Supeng, et al. Mobile-edge computing for vehicular networks: A promising network paradigm with predictive off-loading[J]. IEEE Vehicular Technology Magazine, 2017, 12(2): 36–44. doi: 10.1109/MVT.2017.2668838
    [6] ZHANG Degan, LIU Si, ZHANG Ting, et al. Novel unequal clustering routing protocol considering energy balancing based on network partition & distance for mobile education[J]. Journal of Network and Computer Applications, 2017, 88: 1–9. doi: 10.1016/j.jnca.2017.03.025
    [7] ZHANG Degan, ZHANG Ting, and LIU Xiaohuan. Novel self-adaptive routing service algorithm for application in VANET[J]. Applied Intelligence, 2019, 49(5): 1866–1879. doi: 10.1007/s10489-018-1368-y
    [8] ZHANG Degan, WANG Xiang, SONG Xiaodong, et al. A novel approach to mapped correlation of ID for RFID anti-collision[J]. IEEE Transactions on Services Computing, 2014, 7(4): 741–748. doi: 10.1109/TSC.2014.2370642
    [9] YANG Junnan, DING Ming, MAO Guoqiang, et al. Optimal base station antenna downtilt in downlink cellular networks[J]. IEEE Transactions on Wireless Communications, 2019, 18(3): 1779–1791. doi: 10.1109/TWC.2019.2897296
    [10] ZHANG Degan, ZHANG Ting, DONG Yue, et al. Novel optimized link state routing protocol based on quantum genetic strategy for mobile learning[J]. Journal of Network and Computer Applications, 2018, 122: 37–49. doi: 10.1016/j.jnca.2018.07.018
    [11] ZHANG Degan, GE Hui, ZHANG Ting, et al. New multi-hop clustering algorithm for vehicular ad hoc networks[J]. IEEE Transactions on Intelligent Transportation Systems, 2019, 20(4): 1517–1530. doi: 10.1109/TITS.2018.2853165
    [12] ZHANG Ting, ZHANG Degan, YAN Haoran, et al. A new method of data missing estimation with FNN-based tensor heterogeneous ensemble learning for internet of vehicle[J]. Neurocomputing, 2021, 420: 98–110. doi: 10.1016/j.neucom.2020.09.042
    [13] CHEN Jieqiong, MAO Guoqiang, LI Changle, et al. A topological approach to secure message dissemination in vehicular networks[J]. IEEE Transactions on Intelligent Transportation Systems, 2020, 21(1): 135–148. doi: 10.1109/TITS.2018.2889746
    [14] DUAN Peibo, MAO Guoqiang, LIANG Weifa, et al. A unified spatio-temporal model for short-term traffic flow prediction[J]. IEEE Transactions on Intelligent Transportation Systems, 2019, 20(9): 3212–3223. doi: 10.1109/TITS.2018.2873137
    [15] SARDELLITTI S, SCUTARI G, and BARBAROSSA S. Distributed joint optimization of radio and computational resources for mobile cloud computing[C]. 2014 IEEE 3rd International Conference on Cloud Networking (CloudNet), Luxembourg, 2014: 211–216.
    [16] OUEIS J, STRINATI E C, and BARBAROSSA S. The fog balancing: Load distribution for small cell cloud computing[C]. 2015 IEEE 81st Vehicular Technology Conference (VTC Spring), Glasgow, UK, 2015: 1–6.
    [17] WEI Feng, CHEN Sixuan, and ZOU Weixia. A greedy algorithm for task offloading in mobile edge computing system[J]. China Communications, 2018, 15(11): 149–157. doi: 10.1109/CC.2018.8543056
    [18] TRAN T X and POMPILI D. Joint task offloading and resource allocation for multi-server mobile-edge computing networks[J]. IEEE Transactions on Vehicular Technology, 2019, 68(1): 856–868. doi: 10.1109/TVT.2018.2881191
    [19] KAO Y H, KRISHNAMACHARI B, RA M R, et al. Hermes: Latency optimal task assignment for resource-constrained mobile computing[J]. IEEE Transactions on Mobile Computing, 2017, 16(11): 3056–3069. doi: 10.1109/TMC.2017.2679712
    [20] ZHANG Jiao, HU Xiping, NING Zhaolong, et al. Energy-latency tradeoff for energy-aware offloading in mobile edge computing networks[J]. IEEE Internet of Things Journal, 2018, 5(4): 2633–2645. doi: 10.1109/JIOT.2017.2786343
    [21] WU Xinzhou, SUBRAMANIAN S, GUHA R, et al. Vehicular communications using DSRC: Challenges, enhancements, and evolution[J]. IEEE Journal on Selected Areas in Communications, 2013, 31(9): 399–408. doi: 10.1109/JSAC.2013.SUP.0513036
    [22] ZHAO Junhui, CHEN Yan, and GONG Yi. Study of connectivity probability of vehicle-to-vehicle and vehicle-to-infrastructure communication systems[C]. 2016 IEEE 83rd Vehicular Technology Conference (VTC Spring), Nanjing, China, 2016: 1–4.
    [23] ZHANG Hongli, ZHANG Qiang, DU Xiaojiang, et al. Toward vehicle-assisted cloud computing for smartphones[J]. IEEE Transactions on Vehicular Technology, 2015, 64(12): 5610–5618. doi: 10.1109/TVT.2015.2480004
    [24] RAZA S, WANG Shangguang, AHMED M, et al. Corrigendum to “a survey on vehicular edge computing: Architecture, applications, technical issues, and future directions”[J]. Wireless Communications and Mobile Computing, 2019, 2019: 6104671. doi: 10.1155/2019/6104671
    [25] SHAHAPUR S and DASGUPTA S. Future scope for 5G with respect to the Indian telecommunication sector and proposed solution of setting up 5G in rural areas using unmanned aerial vehicles[C]. 2019 6th International Conference on Computing for Sustainable Global Development, New Delhi, India, 2019: 199–204.
    [26] KAVITHA A and VELUSAMY R L. Simulated annealing and genetic algorithm-based hybrid approach for energy-aware clustered routing in large-range multi-sink wireless sensor networks[J]. International Journal of Ad Hoc and Ubiquitous Computing, 2020, 35(2): 96–116. doi: 10.1504/IJAHUC.2020.109800
    [27] WANG Hui, LI Kangshun, and PEDRYCZ W. A routing algorithm based on simulated annealing algorithm for maximising wireless sensor networks lifetime with a sink node[J]. International Journal of Bio-Inspired Computation, 2020, 15(4): 264–275. doi: 10.1504/IJBIC.2020.108596
  • 加载中
图(13) / 表(5)
计量
  • 文章访问数:  161
  • HTML全文浏览量:  55
  • PDF下载量:  61
  • 被引次数: 0
出版历程
  • 收稿日期:  2021-01-26
  • 修回日期:  2022-07-18
  • 网络出版日期:  2022-07-25
  • 刊出日期:  2022-09-19

目录

    /

    返回文章
    返回