基于epsilon-greedy的边缘服务器选择模型

李思峰

摘   要：如今，5G的时代已经到来，万物互联成为可能。在这种情况下，移动通信技术在人们日常生活和社会发展中的地位进一步突出。用户本地的计算卸载到边缘服务器中，从而解决用户设备在计算性能、存储等方面的不足。一般来说，一个用户周围会存在多个边缘服务器，由此便引发了边缘服务器的选择问题。文章重点介绍了在5G的背景下基于epsilon-greedy的边缘服务器选择问题，以及多臂老虎机模型、epsilon-greedy算法，多臂老虎机模型实现边缘服务器选择，对比了随机选择和epsilon-greedy的优劣。

关键词：边缘服务器选择;5G;epsilon-greedy算法

1    edge的概念

此前，4G的普及改变了生活，满足了人们对视频通话、高清视频播放等基本要求，但在5G到来以后，每一棵树、每一个旅行箱，还有很多东西都可以通过5G连接起来。5G网络将支持：每平方公里100万个连接设备，网络延迟仅仅为1 ms，并提供高达10 Gbps的峰值数据下载速度。这些致使移动设备的业务数据巨幅增长，本地计算将由于计算资源计算能力的限制导致服务时延大大增加，对整体的服务可靠性造成巨大的影响。甚至传统的集中式云计算由于数据量过大在需要大量和外界互动的时候也会显得僵化，反应迟缓。于是边缘计算应运而生。B.Panchali认为：“边缘计算是一种通过在网络边缘、靠近数据源的地方执行数据处理来优化云计算系统的方法”。可以将“edge”定义为任何有助于计算的终端设备，并在数据源和云之间的路径上充当网络资源，edge可以从云端使用这些服务。edge使用来自云的大量服务来处理、分析和做出明智的决定，但是数据只在边缘处处理，会突然执行需要的操作。设备不需要等待云，因为edge作为小型数据中心有自己的边缘服务器[1]。一般来说，一个用户周围会存在多个边缘服务器，由此便引发了边缘服务器的选择问题，而用户一般都会单纯的考虑距离的长短，选择距离自己最近的边缘服务器进行数据卸载，但如果在用户密集的区域执行这种操作，就会造成最近的边缘服务器出现排队的现象，而稍微远一些的边缘服务器却处在空闲状态，造成整体系统效率低下。基于此，本文提出了基于epsilon-greedy的边缘服务器选择模型，来提高系统整体的工作效率。

2    邊缘服务器选择的epsilon-greedy算法

2.1  多臂老虎机模型（MAB问题）

多臂老虎机模型算法最初被发明出来，是为了解释一个理想化的赌徒如何在一个假想的赌场中尽可能多地赚钱。赌博机有不止一个推臂，每个推臂的收益满足一定的统计分布，当赌徒推动其中一个推臂时，便能获得一定的报酬。这个报酬是从推臂的相关分布派生的一个随机变量，而赌徒在最初无法得知推臂的报酬的分布情况。其目的是获得最大的收益，由于每次试验只能选择其中一个推臂，若赌徒选择其中某个推臂的次数达到一定值，那么就可以得出该推臂报酬对应的统计分布情况。同时，如果赌徒只使用其中某一个或者某几个推臂，那么就减少了使用新的推臂的机会，而这些推臂以一定的概率可能具有更高的报酬。赌徒面临的问题是：选择已知报酬均值最高的推臂，来获得较高的报酬，或选择其他未知分布的推臂，以谋求获得可能存在的更高的报酬。这是选择已知推臂或未知推臂的两难问题[2]。

2.1  epsilon-greedy模型

在计算机科学中，贪心算法是这样一种算法，其总是采取当前看起来最好的任何行动，即使这个决定可能会导致糟糕的长期后果。epsilon-greedy算法几乎是一个贪心算法，因为其通常利用最优的可用选项，但偶尔也会探索其他可用选项。epsilon-greedy是最容易理解的强盗算法之一，虽然有一些细节必须解决，但epsilon-greedy背后的主要思想其实很简单，如果你抛一枚硬币，结果是正面，应该研究一下。但是如果硬币反面向上，就应该利用其[3]。

2.3  epsilon-greedy实现边缘服务器选择

将老虎机J个臂作为要选择的边缘服务器。

（1）输入：。

（2）阶段1：定义。

（3）定义摇杆数量K，摇杆数量N使用Qn表示n-1个动作的平均值。

（4）第二阶段：决定。

（5）;  使用arm A=一个带有概率的随机动作。

（6）;  用概率来玩arm A= arg max 。

（7）第三阶段：学习。

（8）更新 。

（9）直到。

3    仿真结果

在模拟中，设置边缘服务器数量为2，用户数量为1，传输槽数量为500，仿真结果如图1所示。

通过图1可以看到，随着迭代次数的增加，通过随机选择得到最优边缘服务器的概率远低于通过epsilon-greedy得到最优边缘服务器的概率，概率相差约0.55。这是因为，当通过epsilon-greedy选择最优服务器时，其总是倾向于选择之前记录的最好的服务器。但是当采用随机算法选择服务器时，相当于随机选择服务器，随机选择的概率为0.2。

4    分析

本文研究了基于epsilon-greedy的边缘服务器选择问题。通过实验数据分析可知，通过epsilon-greedy选择边缘服务器的效果要优于随机算法选择边缘服务器。当实际设备选择卸载数据的边缘服务器时，可人为设置epsilon的值，使设备选择最优的边缘服务器，使平均数据处理速度最大化。

[参考文献]

[1]PANCHALI B.A combined architecture of biologically inspired approaches to self-healing in embedded systems[C].Osijek：International Conference on Smart Systems & Technologies，2017.

[2]QUAN W.MAB問题.[EB/OL].（2018-01-20）[2020-03-10].https：//www.jianshu.com/p/c470a66f7ef8.

[3]NONAME.Bandit algorithms for website optimization[EB/OL].（2013-06-25）[2020-03-10]].www.allitebo.

Edge server selection model based on epsilon-greedy

Li Sifeng

（School of Electrical and Electronic Engineering， North China Electric Power University， Beijing 102206， China）

Abstract：Now， the era of 5G has come and the Internet of everything is possible. In this case， mobile communication technology in People's Daily life and social development in a further prominent position. The local computation of the user is unloaded to the edge server， so as to solve the shortage of the user device in computing performance， storage and so on. In general， there are multiple edge servers around a user， which raises the issue of edge server selection. This paper focuses on the edge-server selection problem based on epsilon-greedy in the context of 5G， introduces the multi-arm slot machine model， the epsilon-greedy algorithm， and the multi-arm slot machine model to achieve edge server selection， and compares the advantages and disadvantages of random selection and epsilon-greedy， as well as the comparison of different epsilon.

Key words：edge server selection; 5G; epsilon-greedy algorithm