基于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