成本受限的边缘服务器冗余节点选择方法研究毕业论文
2020-02-16 09:02
摘 要
随着万物互联时代的到来，网络边缘的设备和数据呈现爆炸式的增长，集中式的云计算模型无法高效实时地处理边缘产生的数据。为了获得低时延的可靠服务，移动边缘计算模型被提出，在基站周围部署边缘服务器用来处理网络边缘产生的大量数据。边缘服务器会受到断电，硬件损坏，或者黑客攻击等因素导致服务不可用。边缘服务器故障是不可避免的，一个亟待解决的问题便是如何做到故障发生时对用户的影响最小，即如何提高边缘计算系统的鲁棒性和抗毁灭性。
冗余常常是提高系统鲁棒性和可靠性的一种方法。本文的主要工作是在边缘服务器节点中，选择哪些关键的节点对其冗余，能够最大化的提高系统鲁棒性，提高用户体验。本文将关键服务器节点选择问题建模成为图中关键节点识别问题，并说明了该问题是一个组合优化问题。随着节点数目的增多，用枚举法来解决问题会产生组合爆炸的现象。因此本文提出一种基于独立集的贪婪启发式算法来识别关键边缘服务器节点。另外，萤火虫算法在全局寻优上表现出比较好的性能，本文还设计一种萤火虫算法来识别关键节点。通过实验说明两种算法在寻优能力上相差不大，都能得到一个较优的解。仿真实验表明，为两种算法选择的边缘服务器节点提供冗余可以提高用户体验（QoE），增加系统的鲁棒性；此外，随机算法有时候也是一种不错的选择，引入随机算法选择的冗余节点作为对比，结果表明本文提出的两种算法在提高用户体验方面的性能优于随机算法。
关键词：移动边缘计算；节点选择；冗余；用户体验
Abstract
With the coming of the Internet of things, devices and data on the edge of the network are growing very fast. The centralized cloud computing model is unable to process the data generated at the edges efficiently and in real time. In order to obtain reliable service with low delay, the mobile edge computing model is proposed. Deploy an edge server around the base station, which processes the large amount of data generated by the edge of the network. Edge servers can suffer power outages, hardware damage, or hacker attacks that make the service unavailable. The failure of edge server is inevitable, one of the urgent problems to be solved is how to minimize the impact of failure on users, that is, how to improve the robustness and anti-ruinous edge computing system.
Redundancy is often a way to improve the robustness and reliability of a system. The main work of this paper is to select the key node in the edge server node for redundancy, which can maximize the robustness of the system and improve user experience. In this paper, the key node selection problem is modeled as the key node identification problem in the graph, and it is shown that the problem is a combinatorial optimization problem. With the increase of the number of nodes, using enumeration method to solve the problem will produce the phenomenon of combinatorial explosion. Therefore, this paper proposes a greedy heuristic algorithm based on independent set to identify key edge server nodes. In addition, firefly algorithm shows good performance in global optimization. This paper also designs a firefly algorithm to identify key nodes. The experiment shows that the two algorithms have little difference in searching ability and can get a better solution. Simulation experiments show that providing redundancy to the edge server nodes selected for the two algorithms can improve the user experience (QoE) and increase the robustness of the system. In addition, random algorithm is sometimes a good choice, which is used as a control experiment. The results show that the two algorithms proposed in this paper have better performance than the random algorithm in improving user experience.
Key Word: mobile edge computing, node selection, redundancy, QoE
目 录
第1章 研究背景及意义 1
1.1 研究背景 1
1.2 研究意义和目的 1
第2章 国内外研究现状分析 2
第3章 边缘服务器冗余节点选择模型 3
3.1 问题描述 3
3.2 系统模型 4
第4章 基于独立集的启发式算法的节点选择 8
4.1 算法思想 8
4.2 寻找独立集 9
4.3 算法描述 10
4.4 算法性能分析 10
第5章 基于萤火虫算法的节点选择 12
5.1 引言 12
5.2 萤火虫算法原理 12
5.3 萤火虫算法离散化 13
5.4 算法描述 14
第6章 仿真实验与结果分析 16
6.1 实验建立 16
6.2 数据集 16
6.2.1 数据集来源 16
6.2.2 数据预处理 16
6.3 两种算法寻优性能力比较 17
6.4 相继故障仿真 18
6.4.1 故障实验模型 19
6.4.2 相继故障实验设置 20
6.4.3 实验结果分析 21
第7章 总结及展望 23
7.1 论文总结 23
7.2 未来工作展望 23
参考文献 24
致谢 26
第1章 研究背景及意义
1.1 研究背景
云计算和移动网络飞速发展，使得像移动手机，可穿戴设备和物联网（IOT）设备数量倍增。这给基础设施运营商带来了巨大的挑战，他们要保证为这些终端用户提供可靠的服务。移动通信的流量呈现爆炸式的增长，导致传统的云计算模型不能满足万物互联的需求。
为了解决这个问题，思科在2012年提出雾计算。雾计算将计算，存储，网络资源推向终端设备和传统云计算中心之间[1]。欧洲电信标准化协会（ETSI）于2014年开始推进移动边缘计算（Mobile Edge Computing，MEC）标准化的相关工作[2]。
在移动边缘计算场景下，互联网服务提供商可雇佣边缘服务器部署他们的应用，从而为终端用户提供服务。对于计算资源和存储资源有限的客户端可以将密集的计算型任务卸载到信号覆盖范围内的边缘服务器[3]。这样终端用户可以获得低时延的服务，远程云计算中心的计算任务也会减少，从而缓解云计算中心的压力。
边缘服务器部署在蜂窝基站的周围，覆盖在不同的地理区域，相邻的边缘服务器的覆盖范围可能会有重叠区域。位于重叠区域的用户可以选择计算资源（CPU，带宽，内存）充足的边缘服务器进行计算卸载。如果用户没有可选择的边缘服务器，将会直接连接到云计算中心服务器。
1.2 研究意义和目的
边缘计算被提出后，得到了学术界与产业界的高度重视，边缘计算的架构看成是一个“端设备-边缘-云”三层模型，三层中的任何一层都可以为应用提供资源和服务，应用根据需要选择最佳的配置方案[4]。
在边缘计算模式的落地过程中，已经出现了许多的方案。中国联通计划到2020年完成6000-7000个边缘服务器节点的建设。这样可以为用户提供高带宽，低时延的服务。但是，边缘服务器会出现基础设施故障如断电，黑客攻击，物理故障等，影响用户体验，因此保证边缘服务器节点的可靠性的研究迫在眉睫。亟待提供该场景下的可行解决方案。
解决问题的一种方法是资源冗余。另一方面，考虑到基础设施提供商的收益，对每一台边缘服务器提供冗余节点显然是不可行的。因此，需要在考虑成本约束的前提下，选择若干关键服务器提供冗余支持。所以本研究致力于移动边缘计算(MEC)场景下的边缘服务器冗余节点的选择方法研究。
第2章 国内外研究现状分析
服务器冗余是系统可靠性领域的经典问题。在传统的云计算模型中有一种冗余机制，可应用差异灵敏度分析来识别系统的关键组件并对服务可用性进行排序，用于识别哪些组件应该由冗余支持，以便有意识地提高系统可靠性[5]。为了在冗余中获得更高的性能并增强大规模副本传输之间的带宽分配公平性，Li提出了一种公平旋转和比率感知的蚁群优化（FRRA-ACO）算法[6]。Biswas提出了一个敏捷冗余模型，它提供一个调整资源成本和可靠性之间权衡的模型[7]。在分布式场景下，Sahoo为副本服务器放置问题提出了一种有效的贪心启发式方法[8]。用K-means算法对网络进行聚类，对于每个聚类，应用贪婪算法找出该区域的近似位置来放置服务器副本[9]。还有人提出捕获路径级别，节点级别和整体网络级别的结构依赖性效果，明确考虑由节点故障引起的网络碎片的影响，应用于网络中的关键节点识别[10]。
在移动边缘计算提出后，鲜有考虑到边缘服务器冗余的问题。传统云计算中心服务器如果不做冗余，服务器发生故障之后应用程序根本无法运行，大量的数据会丢失，这严重影响用户体验。对云计算中心的每个服务器提供冗余支持是必需的，但是在移动边缘计算场景下，某一个边缘服务器发生故障之后，用户可以选择临近的边缘服务器或远端云数据中心进行计算处理。传统的服务器冗余方案不适合新的场景，需要对新的问题提出解决方案。可看到有人提出贪心算法和启发式算法选择一些关键边缘服务器节点，在这些关键边缘服务器节点中搭载应用，从而使用户的平均响应时间最小[11]。但是它没有考虑服务器发生故障时如何保证用户体验。本研究从网络关键节点角度出发，讨论如何在边缘计算场景下选择边缘服务器节点做冗余支持，从而提高系统的鲁棒性和保障用户体验。
第3章 边缘服务器冗余节点选择模型
3.1 问题描述
在系统可靠性提升方面，冗余是一种行之有效的方法。与云计算模型或者分布式场景中类似，移动边缘计算场景也需要解决系统故障的问题。一个方法是对放置在基站周围的边缘服务器进行冗余备份，从而提高整个移动边缘计算系统的可靠性。同时可以增加用户体验（QoE）。但是，哪些基站周围的边缘服务器应该提供冗余支持，以及需要提供冗余支持的边缘服务器数量有多少，这些并没有明确的规定，所以产生了边缘服务器冗余节点选择的问题。这个问题描述为在一定的地理区域范围内，考虑基础设施提供商的成本限制，满足系统可靠性和用户体验的条件下，按照某一种策略选择合适的边缘服务器，为其提供冗余支持。
图3.1 边缘服务器部署模型
如图3.1所示，边缘服务器放置在基站附近。基站可以将其覆盖范围内用户转发的计算任务提交给边缘服务器，如果边缘服务器的工作过载，基站可以请求远端的云计算数据中心处理。用户1处在s1的覆盖范围内，可以将计算任务卸载到边缘服务器s1上，由于边缘服务器距离用户的很近，不需要经过核心网，这样就实现了低时延的计算任务要求。基站s1和基站s3的信号覆盖范围有重叠区域，位于重叠区域的用户4可以选择将计算任务卸载到s1或s3。位于重叠区域内的用户存在以下两个优势：第一，如果其中一个服务器的工作负载过重，无法响应用户请求，用户可以选择其他空闲的边缘服务器进行计算卸载，这样用户计算卸载成功率会很高。第二，用户的任务在某一个边缘服务器上进行计算处理，由于服务器发生断电，攻击之类的故障时候，系统可以立即将计算任务迁移到另一台边缘服务器，这个过程对用户来说是透明的，用户没有感知到边缘服务故障，该用户的服务一直得到满足，所以用户体验好。
在图3.1中，边缘服务器s5发生故障或者负载过重，用户5可以选择边缘服务器s3进行计算卸载。边缘服务器s4发生故障或者负载过重，用户6可以将计算任务卸载到边缘服务器s3。同理用户4和用户2也可以进行这种操作。由此可以看出，边缘服务器s3非常重要，它可能面临处理很多的计算任务的情形，一旦边缘服务器s3发生故障，周围的服务器非常容易出现负载过高从而发生故障的情况。因此，边缘服务器s3就显得非常关键，为了提高系统的鲁棒性，改善用户体验，为s3提供冗余支持是一种有效的方法。
本文研究的问题是如何识别出关键节点并加以保护。由于基础设施提供商成本有限，不会为所有的边缘服务器提供冗余支持。考虑到成本限制，能够冗余的边缘服务器数量有限，本文用一个冗余度θ来限制冗余节点的数量。假设一定地理区域范围内的边缘服务器数量N是62，冗余度θ=0.49，那么能够提供冗余支持的边缘服务器个数k就是N×θ=30台。
3.2 系统模型
为了识别出关键边缘服务器节点，本文将边缘服务器节点选择模型抽象成无向图G=(V，E)。无向图中的顶点集合V是所有的边缘服务器节点。任取服务器节点Bi∈V，Bj∈V，如果Bi和Bj两个边缘服务器节点信号范围存在重叠区域，则表示图中的两个节点之间存在一条边。E是无向图中所有节点之间边的集合。到此，问题转换为识别无向图中的k个关键节点。
如图3.2所示，根据图3.1的边缘服务器部署模型得到一个抽象的无向图。边缘服务器s1与边缘服务器s2之间有信号重叠区域，所以在图中存在一条边lt;1,2gt;。当冗余度θ=0.49，可以有k=5×0.49台边缘服务器可以获得冗余支持。边缘服务器个数只能取整数，向下取整k=2。
在图3.2中的5个节点选取2个节点总共有
=10种不同的选择方案。把节点2，3看成关键节点是一个较优的方案。节点2和3发生故障后，节点1，4，5都成为了一个孤立的顶点，这些服务器的工作负载会增大非常容易发生故障。由于每一台边缘服务器资源有限，该边缘服务器不可能为其覆盖范围内的所有用户提供服务，因此存在某些用户需要将任务进行本地卸载或在云端执行。
图3.2 边缘服务器拓扑图
对于另一种方案将1，2看成关键节点，剩余节点3，4，5还是存在边连接，对应的边缘服务器之间会存在信号覆盖重叠区域，重叠区域内的用户可以选择空闲或可以提供计算资源的边缘服务器进行计算卸载。所以该方案（1，2）不是最优的，即识别的是非关键节点。
在无向图G=（V，E）中，识别出k个关键顶点，该k个顶点删除之后，剩余顶点组成的图要最小聚合。一种理想的情形，剩余顶点都是孤立的顶点。然而，一个图删除k个顶点之后剩余顶点不一定都是孤立的点。因此，需要寻找一个指标来衡量剩余顶点组成的导出子图的离散性。本文的目标是找出k个顶点，使剩余顶点离散性最低。
完全图是顶点离散性最低的一种图，它的每一个顶点都与其它顶点有边相连，代表着对应的边缘服务器之间互相有重叠区域，互相之间能够帮忙，此时系统可靠性高。一个不存在任何边的图具有最高的顶点离散度，其中每一个顶点都是独立的点，这可以代表着对应的边缘服务器之间互相没有重叠区域，边缘服务器之间不能互相帮助，分担计算任务，可靠性低。为了度量一个无向图G=（V，E）顶点的离散性[12]引入一个函数F，定义如下：
