社会属性感知的边缘计算任务调度策略

奥鹏网院作业

社会属性感知的边缘计算任务调度策略
王汝言 聂 轩 吴大鹏* 李红霞
(重庆邮电大学通信与信息工程学院 重庆 400065)
(重庆高校市级光通信与网络重点实验室 重庆 400065)
(泛在感知与互联重庆市重点实验室 重庆 400065)
摘 要：边缘计算服务器的负载不均衡将严重影响服务能力，该文提出一种适用于边缘计算场景的任务调度策略(RQ-AIP)。首先，根据服务器的负载分布情况衡量整个网络的负载均衡度，结合强化学习方法为任务匹配合适的边缘服务器，以满足传感器节点任务的资源差异化需求；进而，构造任务时延和终端发射功率的映射关系来满足物理域的约束，结合终端用户社会属性，为任务不断地选择合适的中继终端，通过终端辅助调度的方式实现网络的负载均衡。仿真结果表明，所提出的策略与其他负载均衡策略相比能有效地缓解边缘服务器之间的负载和核心网的流量，降低任务处理时延。
关键词：计算机网络；边缘计算；社会属性；负载均衡
1 引言
移动边缘计算(Mobile Edge Computing,MEC)通过在接近用户的无线接入网范围内提供便捷的计算和处理能力，已经被广泛应用到物联网、移动大数据分析等多种场景[1]。物联网(Internet of Things, IoT)通过将广泛区域内的大量智能设备互联，已经成为智能城市和互联社区高级应用的一部分，但传感器设备计算资源有限导致的边缘服务器负载不均衡仍然是物联网的主要瓶颈[2]。移动边缘计算通过调度海量空闲边缘终端，利用设备到设备(Device-to-Device, D2D)通信辅助调度的方式支持物联网应用，减少了任务的延迟[3]，为互联网设备提供了更大的带宽[4]，避免了将任务卸载到远程计算系统造成的网络拥塞[5]。
国内外研究人员针对MEC的任务调度问题提出了多种解决方案。文献[6]提出一种将数据和任务在边缘设备之间共享的协作边缘计算模式来实现任务的调度，通过对任务数据输入和网络流量联合建模来最小化任务完成的总体时间。文献[7]提出了一种基于Ad-hoc的移动边缘计算系统开销优化多设备任务调度策略。该策略考虑了机会消耗，时间延迟，能量消耗和货币成本，通过将问题公式化为分布式多参与者博弈问题来最小化每个移动设备的开销。文献[8]提出了一种边缘和云协同混合调度的方式，相应的感知调度程序会提取任务的特征，然后决定任务是在云端还是边缘处执行。上述研究都是单独从任务终端或者服务器的角度出发，将问题建模为时延或能耗最小化问题，没有考虑到任务调度对整个网络负载均衡的影响。文献[9]提出了在网络边缘进行分布式计算的负载均衡方案，将边缘节点之间的负载均衡问题建模为优化问题，进而使用梯度下降求解。文献[10]研究了基站之间的对等卸载问题，通过集中式的Lyapunov优化算法和分布式的非协作博弈来解决存在的负载不均衡问题。文献[11]提出了基于移动代理和蚁群优化技术的负载均衡框架，该模型中调度程序代理根据正确的决策将所接收任务分发给工作代理。文献[12]提出的HETS算法通过分析任务在不同地方的延迟和能耗制定了延迟最小化问题并提出1维搜索算法以找到最优任务调度策略。这些方法在实现负载均衡时，只考虑了任务在服务器端的调度策略，缺乏对任务传输过程的分析。虽然文献[13]在车联网背景下提出了基于社会属性的车辆间数据转发机制，通过分布式学习的方式学习车辆的社交特征并选择中心性更高的车辆作为转发车辆。但是该文没有考虑传输过程中频谱复用干扰对终端选择的影响。
据思科视觉网络指数预测，相比于2015年，2020年全球联网设备数量将达到200多亿，物联网数据将惊人地增长到4.4 ZB[14]。传统的蜂窝通信往往会消耗大量的网络资源，物联网应用的需求难以被满足。D2D通信通过让数据直接在设备之间传输相对于通过基站传输可以极大地降低时延，减轻网络的拥塞，为任务的需求提供保障。但是，这种方案的性能很大程度上取决于D2D中继的选择以及潜在资源重用干扰的管理。因此，如何根据移动终端的社会属性选择合理的终端协助MEC服务器实现任务的实时调度是本文研究的一个重点问题。
针对上述问题，本文提出了一种带有终端社会属性感知的RQ-AIP任务调度策略：首先，根据服务器负载程度和任务的差异化需求，使用强化Q学习方法做出任务卸载决策，然后，在充分考虑频谱复用干扰和用户发射功率的情况下，结合终端的社会属性，选取当前任务位置最佳的转发终端完成任务传输，重复执行该步骤，直到某一转发终端在目标服务器的覆盖范围之内，进而对任务进行调度，以最小化网络的负载均衡度，从而提高网络的能效。
2 网络架构与计算模型
2.1 网络架构
针对思科视觉指数指出的移动数据流量爆炸式增长，如何有效地承载各类物联网业务是未来移动通信系统发展的重要方向。为了满足数据传输过程在快速链接、实时业务等方面的需求，需要充分利用传感器节点、移动终端、基础设施组成的边缘计算网络，在靠近数据源头的网络边缘处理物联网相关应用所请求的内容，达到卸载流量、优化连接的目的。
本文的系统框架如图1所示。从各类网元所执行的基本功能来看，网络边缘的设备可以分为3层：最底层是传感器节点层，主要由物联网场景下密集部署的传感器节点组成，它们主要负责对给定事物状态参数的采集，并产生一些待处理的任务；第2层是移动终端层，主要包括用户携带一些智能设备，负责各类业务数据的接收及转发；第3层是基础设施层，包括宏基站和部署了边缘服务器的毫微微蜂窝基站，边缘服务器一般拥有较强的存储计算能力，负责对收集到的数据任务进行计算和处理。
2.2 网络模型

图 1 系统框架图

图 2 网络模型图
本文的网络模型如图2所示。小区中心部署宏基站负责管理用户之间的通信以及监测边缘服务器的负载状态，边缘服务器部署在相应的毫微微蜂窝小区(Femtocell)负责接收传感器节点的任务并提供计算和存储服务，图2同时显示了用户间的干扰情况。毫微微蜂窝小区用户和D2D用户彼此占用正交的频谱资源，且复用宏蜂窝小区的频谱资源，因此需要考虑D2D通信和毫微微蜂窝用户通信对蜂窝用户通信造成的干扰。定义传感器设备，移动用户终端，和边缘服务器的集合分别为：M ={1,2,···,m},N={1,2,···,n} , K ={1,2,···,k}，其中ME代表直接与宏基站通信用户，FE代表与毫微微基站通信的用户，DE代表D2D用户。
2.3 计算模型
在边缘计算网络中，任务会根据自身的属性以及网络的负载均衡状态，选择在传感器节点处或者在边缘服务器上进行计算。由于本文研究的一个重点是传感器节点如何选择合适的中继转发终端把任务传输到相应的服务器上去，所以主要研究了对D2D辅助任务卸载情形下的计算模型研究。
当边缘服务器处于过载时，需要将任务调度到其它相对空闲的服务器上，以实现边缘服务器之间的负载均衡。本文提出将任务通过D2D通信交付给合适的中继，再通过中继辅助卸载到目的边缘服务器上的方案。然而由于网络的复杂性，D2D通信往往面临多次中继选择的问题，这容易导致任务传输的时延超过任务本身的时延要求。因此，本文在中继选择方面加入了功率因素对时延约束的影响。
由于D2D传输需要复用蜂窝用户的上行链路资源，因此根据文献[15]蜂窝用户对D2D通信的信号干扰噪声比(Signal to Interference plus Noise Ratio, SINR)为

Pi, P MEc 分别表示传感器节点和复用的蜂窝用户的发射功率，表示源节点i与第1个中继节点之间的信道增益。h MEc,ri1表示干扰蜂窝用户与中继之间的信道增益，σ 2表示加性高斯白噪声的功率。
本文考虑工作在全双工模式下D2D辅助通信，设一共需要z个中继终端，因此，可实现的端到端数据速率可以推导为

其中， B表示为D2D通信链路分配的带宽，γi,r1,γri1,ri2分别表示节点i与第1个中继节点，第1个中继节点与第2个中继节点的干扰噪声比。
3 目标服务器选择
3.1 算法描述与负载模型
为了有效地实现网络的负载均衡，首先要确定任务和服务器的匹配关系。该问题可以通过寻找最佳的调度策略向量来解决。本文采用强化Q学习的方法来寻找最优调度策略。在任务分配过程中，需要考虑服务器的实时负载，本文设服务器的工作负载状态可由CPU利用率，内存利用率和带宽利用率这3个向量来表示，即=(CPU,mem,band), 称之为状态向量。
3.2 基于强化Q学习的服务器选择算法
本节提出服务器选择的智能算法，该方法根据不同调度决策下的网络负载均衡度进行学习。小区中心的宏基站负责收集不同服务器的负载状态以及传感器节点的实时任务分布，并将学习的结果保存下来用以进行后面的终端选择过程。接下来本文将分别介绍状态、行为和奖励函数。
(1) 状态：学习过程中的状态对应任务调度到某一服务器后的网络的负载状况。设系统中有b个延服务迟器容上忍去型执任行务，，因每此个整任个务系都统可中能一调共度有到任种何状一态个。本文用负载均衡度来衡量整个网络的负载均衡情况。
首先根据所有服务器的负载情况计算出整个网络不同资源的负载中心值，然后根据中心值求出负载均衡度。负载中心值的计算如式(3)

其中，表示服务器j上可用的q资源的数量，k表示服务器的数目。则负载均衡度求解如式(4)



定义一个负载均衡因子 εij 来衡量任务i分配到服务器j上后服务器的实时负载情况，具体计算公式如式(5)为候选中继终端，然后在候选中继终端中选择 w 最大的节点作为传输中继终端，判断该节点是否在目标服务器的通信范围之内，如果在，则直接将任务上传到目的服务器上面执行，如果不在，更新式(26)的功率范围，继续执行上述操作，直到找到一个在目标服务器覆盖范围内的终端结束。
5 仿真分析
本文的仿真分析主要分为两部分：首先通过Matlab仿真平台对本文所提算法的前一部分即基于强化Q学习的任务调度算法进行了验证，其对比算法主要包括文献[11]提出的WLB-ACO算法，文献[12]提出HETS算法以及将所有任务卸载到相应本地边缘服务器的Full-Local策略。其次，通过NS2仿真平台对所提出算法后一部分中的任务投递过程进行验证。这里的对比算法包括文献[13]提出的基于社会特征的数据传输方式(SDFM)算法以及文献[16]提出的带有节点间社会等级估计的数据转发策略(Bubble Rap)算法。
本文的主要仿真参数限定如表1所示。
表 1 仿真参数设置

5.1 不同资源下的负载均衡度
图3表示的是在不同任务分布场景下4种算法负载均衡度的值。由图可知，在任务数量大小以及服务器数量可用资源一定的情况下，本文提出的RQAIP负载均衡策略具有最低负载均衡度，这是因为该策略采用Q学习方法通过迭代学习不断寻找最优解，而WLB-ACO会受到参数固定、求解速度慢的影响，Full-Local方案只把任务卸载到本地服务器，在任务所需资源较少时具有良好的性能，HETS算法是以时延为优化目标往往达不到较好的负载均衡度。
服务器可用计算资源不同情况下的负载均衡度变化情况如图4所示。由图可知，当可用资源一般时，Full-Local, WLB-ACO, RQ-AIP算法的负载均衡度具有相似的下降趋势。但是，随着可用资源的增多，Full-Local算法的负载均衡度值下降的最缓慢。这是由于Full-Local算法将任务卸载到本地服务器；对于WLB-ACO，随着可用资源的增多，服务器一般不会出现过载的情况，WLB-ACO发挥的作用也就逐渐变小，从而使得负载均衡度的值变大；而本文的RQ-AIP策略是通过迭代一直寻找最优解的方法，尽管服务器不会处在过载的边缘，算法仍然会为任务选择使系统负载均衡度最小的调度策略。对于HETS算法的分析同之前一样，由于它是以时延最小为目标的，所以它的负载均衡度往往是这3种算法中最差的。

图 3 不同场景下的负载均衡度

图 4 不同服务器计算资源下的负载均衡度

图 5 不同任务数量下的负载均衡度
不同任务数量下的负载均衡度变化情况如图5所示。从图中可以看出，随着任务数量的增加，WLB-ACO, HETS和Full-Local算法的负载均衡度都呈现出较为明显的上升趋势。这是由于随着任务数量的增加，调度问题的规模越来越大，各服务器的压力也越来越大，这3种算法很难在有限的时延要求内完成任务的调度，能够实现的系统负载均衡度是有限的，因此呈现出上升的趋势。本文的RQ-AIP策略中的任务调度算法是一种可以根据历史经验进行学习的算法，所以当实际情况发生变化的时候，算法不会从最初始的状态开始进行迭代，因此本文可以实现低的且较为稳定的负载均衡度。
5.2 不同终端数目下的任务投递率
图6描述了终端数量与任务平均完成时延的关系。可见，随着终端数目的增加，各种算法的任务平均完成时间都呈下降趋势，其原因在于随着终端数目的增加，终端相遇的机会也会增加。在每一次转发的过程中遇到可选中继的概率也会大很多，快速转发到目的服务器的概率也会增大，其中本文提出的算法的传输延迟比SDFM[13]算法和Bubble Rap[16]算法平均降低了18%和25%。这是因为本文算法综合考虑了用户的社会属性和物理属性。在社会属性方面考虑了用户的活跃度和与目标服务器亲密度两者在不同情况下对任务完成时延的影响。物理属性方面在考虑了用户发射功率限制下中继选择对任务完成时延的影响。

图 6 不同终端数目下的平均完成时延

图 7 用户不同发送功率下的任务投递率
图7显示了3种算法的任务投递率与用户发送功率之间的关系。本文中，用户的发送功率作为任务在时延要求范围内成功多跳到目标服务器的物理约束条件，它考虑了D2D通信对蜂窝用户通信的影响，随着跳数的增加，用户的发射功率也应该增加才能弥补由于跳数增加所导致的时延的增加，因此发射功率越大任务成功交付的概率也就越大。而SDFM和Bubble Rap算法只考虑了用户的社会属性，因此它们具有相似且较低的任务投递速率。
6 结束语
本文在边缘计算场景下提出了一种社会属性感知的任务调度策略(RQ-AIP)。首先，根据边缘服务器的资源分布确定网络的负载均衡度；然后，根据强化Q学习算法确定传感器节点任务的最佳执行服务器；最后传感器节点根据用户的发送功率作为衡量D2D通信干扰的指标，选择合适的中继用户，进而完成任务转发。结果表明，本文所提策略能够在不干扰蜂窝用户通信的情况下完成任务调度，并且能够有效改善网络资源分配不均匀的情况。
参 考 文 献
[1]KUMAR K, LIU Jibang, LU Y H, et al. A survey of computation offloading for mobile systems[J]. Mobile Networks and Applications, 2013, 18(1): 129–140. doi:10.1007/s11036-012-0368-0.
[2]ZENG Deze, GU Lin, GUO Song, et al. Joint optimization of task scheduling and image placement in fog computing supported software-defined embedded system[J]. IEEE Transactions on Computers, 2016, 65(12): 3702–3712. doi:10.1109/TC.2016.2536019.
[3]MAO Yuyi, ZHANG Jun, and LETAIEF K B. Dynamic computation offloading for mobile-edge computing with energy harvesting devices[J]. IEEE Journal on Selected Areas in Communications, 2016, 34(12): 3590–3605. doi:10.1109/JSAC.2016.2611964.
[4]CHEN Xu, JIAO Lei, LI Wenzhong, et al. Efficient multiuser computation offloading for mobile-edge cloud computing[J]. IEEE/ACM Transactions on Networking,2016, 24(5): 2795–2808. doi: 10.1109/TNET.2015.2487344.
[5]MACH P and BECVAR Z. Mobile edge computing: A survey on architecture and computation offloading[J]. IEEE Communications Surveys & Tutorials, 2017, 19(3):1628–1656. doi: 10.1109/COMST.2017.2682318.
[6]SAHNI Y, CAO Jiannong, and LEI Yang. Data-aware task allocation for achieving low latency in collaborative edge computing[J]. IEEE Internet of Things Journal, 2019, 6(2):3512–3524. doi: 10.1109/JIOT.2018.2886757.
[7]LI Tianze, WU Muqing, ZHAO Min, et al. An overheadoptimizing task scheduling strategy for ad-hoc based mobile edge computing[J]. IEEE Access, 2017, 5: 5609–5622. doi:10.1109/ACCESS.2017.2678102.
[8]SCHÄFER D, EDINGER J, ECKRICH J, et al. Hybrid task scheduling for mobile devices in edge and cloud environments[C]. 2018 IEEE International Conference on Pervasive Computing and Communications Workshops,Athens, Greece, 2018: 669–674. doi: 10.1109/PERCOMW.2018.8480201.
[9]THAM C K and CHATTOPADHYAY R. A load balancing scheme for sensing and analytics on a mobile edge computing network[C]. The 18th IEEE International Symposium on A World of Wireless, Mobile and Multimedia Networks, Macau, China, 2017: 1–9. doi: 10.1109/WoWMoM.2017.7974307.
[10]CHEN Lixing, ZHOU Sheng, and XU Jie. Computation peer offloading for energy-constrained mobile edge computing in small-cell networks[J]. IEEE/ACM Transactions on Networking, 2018, 26(4): 1619–1632. doi: 10.1109/TNET.2018.2841758.
[11]YOUNES H, BOUATTANE O, YOUSSFI M, et al. New load balancing framework based on mobile AGENT and ant-colony optimization technique[C]. 2017 Intelligent Systems and Computer Vision, Fez, Morocco, 2017: 1–6.
[12]MASOOD A, MUNIR E U, RAFIQUE M M, et al. HETS:Heterogeneous edge and task scheduling algorithm for heterogeneous computing systems[C]. The 17th IEEE International Conference on High Performance Computing and Communications, New York, USA, 2015: 1865–1870.doi: 10.1109/HPCC-CSS-ICESS.2015.295.
[13]TIAN Rui, JIAO Zhenzhen, BIAN Guiyun, et al. A socialbased data forwarding mechanism for V2V communication in VANETs[C]. The 10th International Conference on Communications and Networking in China, Shanghai, China,2015: 595–599. doi: 10.1109/CHINACOM.2015.7498007.
[14]Cisco visual networking index: Global mobile data traffic forecast update, 2015–2020[EB/OL]. https://www.cisco.com/c/dam/m/en ... enterprise/assets/m obile-white-paper-c11-520862.pdf, 2016.
[15]ZHAO Pengtao, TIAN Hui, QIN Cheng, et al. Energysaving offloading by jointly allocating radio and computational resources for mobile edge computing[J].IEEE Access, 2017, 5: 11255–11268. doi: 10.1109/ACCESS.2017.2710056.
[16]PAN Hui, CROWCROFT J, and YONEKI E. BUBBLE Rap: Social-based forwarding in delay-tolerant networks[J].IEEE Transactions on Mobile Computing, 2011, 10(11):1576–1589. doi: 10.1109/TMC.2010.246.
Social Attribute Aware Task Scheduling Strategy in Edge Computing
WANG Ruyan NIE Xuan WU Dapeng LI Hongxia
(School of Telecommunication and Information Engineering, Chongqing University of Posts and Telecommunications, Chongqing 400065, China)
(Chongqing Key Laboratory of Optical Communication and Network, Chongqing 400065, China)
(Chongqing Key Laboratory of Ubiquitous Sensing and Networking, Chongqing 400065, China)
Abstract: Unbalanced load on the edge computing server will seriously affect service capabilities, a task scheduling strategy Reinforced Q-learning-Automatic Intent Picking (RQ-AIP) for edge computing scenarios is proposed. Firstly, the load balance of the entire network is measured based on the load distribution of the server. By combining the reinforcement learning method, the appropriate edge server is matched for the task to meet the resource differentiation needs of sensor node tasks. Then, a mapping relationship between task delay and terminal transmit power is constructed to satisfy the constraints of the physical domain. Combining the social attributes of terminal, the appropriate relay terminal is continuously selected for the task to achieve the load balancing of network by terminal-assisted scheduling. Simulation results show that compared with other load balancing strategies, the proposed strategy can effectively alleviate the load between the edge servers and the traffic of the core network, reduce task processing latency.
Key words: Computer network; Edge computing; Social attribute; Load balancing
中图分类号：TP393
文献标识码：A
文章编号：1009-5896(2020)01-0271-08
DOI: 10.11999/JEIT190301
收稿日期：2019-04-27；改回日期：2019-10-30；网络出版：2019-11-13
*通信作者： 吴大鹏 wudp@cqupt.edu.cn
基金项目：国家自然科学基金(61771082, 61871062)，重庆市高校创新团队建设计划(CXTDX201601020)
Foundation Items: The National Natural Science Foundation of China (61771082, 61871062), Chongqing Funded Project of Chongqing University Innovation Team Construction(CXTDX201601020)
王汝言：男，1969年生，教授，博士，研究方向为泛在网络、多媒体信息处理等.
聂 轩：男，1995年生，硕士生，研究方向为移动边缘计算.
吴大鹏：男，1979年生，教授，博士，研究方向为泛在无线网络、无线网络服务质量控制等.
李红霞：女，1969年生，高级工程师，研究方向为光无线融合网络.