基于epsilon-greedy的邊緣服務(wù)器選擇模型

李思峰

摘? ?要：如今，5G的時代已經(jīng)到來，萬物互聯(lián)成為可能。在這種情況下，移動通信技術(shù)在人們?nèi)粘Ｉ詈蜕鐣l(fā)展中的地位進一步突出。用戶本地的計算卸載到邊緣服務(wù)器中，從而解決用戶設(shè)備在計算性能、存儲等方面的不足。一般來說，一個用戶周圍會存在多個邊緣服務(wù)器，由此便引發(fā)了邊緣服務(wù)器的選擇問題。文章重點介紹了在5G的背景下基于epsilon-greedy的邊緣服務(wù)器選擇問題，以及多臂老虎機模型、epsilon-greedy算法，多臂老虎機模型實現(xiàn)邊緣服務(wù)器選擇，對比了隨機選擇和epsilon-greedy的優(yōu)劣。

關(guān)鍵詞：邊緣服務(wù)器選擇;5G;epsilon-greedy算法

1? ? edge的概念

此前，4G的普及改變了生活，滿足了人們對視頻通話、高清視頻播放等基本要求，但在5G到來以后，每一棵樹、每一個旅行箱，還有很多東西都可以通過5G連接起來。5G網(wǎng)絡(luò)將支持：每平方公里100萬個連接設(shè)備，網(wǎng)絡(luò)延遲僅僅為1 ms，并提供高達10 Gbps的峰值數(shù)據(jù)下載速度。這些致使移動設(shè)備的業(yè)務(wù)數(shù)據(jù)巨幅增長，本地計算將由于計算資源計算能力的限制導(dǎo)致服務(wù)時延大大增加，對整體的服務(wù)可靠性造成巨大的影響。甚至傳統(tǒng)的集中式云計算由于數(shù)據(jù)量過大在需要大量和外界互動的時候也會顯得僵化，反應(yīng)遲緩。于是邊緣計算應(yīng)運而生。B.Panchali認為：“邊緣計算是一種通過在網(wǎng)絡(luò)邊緣、靠近數(shù)據(jù)源的地方執(zhí)行數(shù)據(jù)處理來優(yōu)化云計算系統(tǒng)的方法”。可以將“edge”定義為任何有助于計算的終端設(shè)備，并在數(shù)據(jù)源和云之間的路徑上充當網(wǎng)絡(luò)資源，edge可以從云端使用這些服務(wù)。edge使用來自云的大量服務(wù)來處理、分析和做出明智的決定，但是數(shù)據(jù)只在邊緣處處理，會突然執(zhí)行需要的操作。設(shè)備不需要等待云，因為edge作為小型數(shù)據(jù)中心有自己的邊緣服務(wù)器[1]。一般來說，一個用戶周圍會存在多個邊緣服務(wù)器，由此便引發(fā)了邊緣服務(wù)器的選擇問題，而用戶一般都會單純的考慮距離的長短，選擇距離自己最近的邊緣服務(wù)器進行數(shù)據(jù)卸載，但如果在用戶密集的區(qū)域執(zhí)行這種操作，就會造成最近的邊緣服務(wù)器出現(xiàn)排隊的現(xiàn)象，而稍微遠一些的邊緣服務(wù)器卻處在空閑狀態(tài)，造成整體系統(tǒng)效率低下?；诖?，本文提出了基于epsilon-greedy的邊緣服務(wù)器選擇模型，來提高系統(tǒng)整體的工作效率。

2? ? 邊緣服務(wù)器選擇的epsilon-greedy算法

2.1? 多臂老虎機模型（MAB問題）

多臂老虎機模型算法最初被發(fā)明出來，是為了解釋一個理想化的賭徒如何在一個假想的賭場中盡可能多地賺錢。賭博機有不止一個推臂，每個推臂的收益滿足一定的統(tǒng)計分布，當賭徒推動其中一個推臂時，便能獲得一定的報酬。這個報酬是從推臂的相關(guān)分布派生的一個隨機變量，而賭徒在最初無法得知推臂的報酬的分布情況。其目的是獲得最大的收益，由于每次試驗只能選擇其中一個推臂，若賭徒選擇其中某個推臂的次數(shù)達到一定值，那么就可以得出該推臂報酬對應(yīng)的統(tǒng)計分布情況。同時，如果賭徒只使用其中某一個或者某幾個推臂，那么就減少了使用新的推臂的機會，而這些推臂以一定的概率可能具有更高的報酬。賭徒面臨的問題是：選擇已知報酬均值最高的推臂，來獲得較高的報酬，或選擇其他未知分布的推臂，以謀求獲得可能存在的更高的報酬。這是選擇已知推臂或未知推臂的兩難問題[2]。

2.1? epsilon-greedy模型

在計算機科學(xué)中，貪心算法是這樣一種算法，其總是采取當前看起來最好的任何行動，即使這個決定可能會導(dǎo)致糟糕的長期后果。epsilon-greedy算法幾乎是一個貪心算法，因為其通常利用最優(yōu)的可用選項，但偶爾也會探索其他可用選項。epsilon-greedy是最容易理解的強盜算法之一，雖然有一些細節(jié)必須解決，但epsilon-greedy背后的主要思想其實很簡單，如果你拋一枚硬幣，結(jié)果是正面，應(yīng)該研究一下。但是如果硬幣反面向上，就應(yīng)該利用其[3]。

2.3? epsilon-greedy實現(xiàn)邊緣服務(wù)器選擇

將老虎機J個臂作為要選擇的邊緣服務(wù)器。

（1）輸入：。

（2）階段1：定義。

（3）定義搖桿數(shù)量K，搖桿數(shù)量N使用Qn表示n-1個動作的平均值。

（4）第二階段：決定。

（5）;? 使用arm A=一個帶有概率的隨機動作。

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

（7）第三階段：學(xué)習(xí)。

（8）更新 。

（9）直到。

3? ? 仿真結(jié)果

在模擬中，設(shè)置邊緣服務(wù)器數(shù)量為2，用戶數(shù)量為1，傳輸槽數(shù)量為500，仿真結(jié)果如圖1所示。

通過圖1可以看到，隨著迭代次數(shù)的增加，通過隨機選擇得到最優(yōu)邊緣服務(wù)器的概率遠低于通過epsilon-greedy得到最優(yōu)邊緣服務(wù)器的概率，概率相差約0.55。這是因為，當通過epsilon-greedy選擇最優(yōu)服務(wù)器時，其總是傾向于選擇之前記錄的最好的服務(wù)器。但是當采用隨機算法選擇服務(wù)器時，相當于隨機選擇服務(wù)器，隨機選擇的概率為0.2。

4? ? 分析

本文研究了基于epsilon-greedy的邊緣服務(wù)器選擇問題。通過實驗數(shù)據(jù)分析可知，通過epsilon-greedy選擇邊緣服務(wù)器的效果要優(yōu)于隨機算法選擇邊緣服務(wù)器。當實際設(shè)備選擇卸載數(shù)據(jù)的邊緣服務(wù)器時，可人為設(shè)置epsilon的值，使設(shè)備選擇最優(yōu)的邊緣服務(wù)器，使平均數(shù)據(jù)處理速度最大化。

[參考文獻]

[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