異質邊緣與霧系統聯盟下的資源分配：使用配對賽局

Resource Allocation for Federated Heterogeneous Edge and Fog Systems: A Matching Game Approach

林明儀(Ming-Yi Lin)

指導教授 ： 嚴力行

國立交通大學/資訊學院/資訊科學與工程研究所/碩士(2018年)

摘要

在邊緣計算環境下，當物聯網裝置或霧運算裝置需要卸載運算至邊緣伺服器時，邊緣服務提供者能夠提供物聯網裝置及霧裝置較低的延遲。然而，當有大量的物聯網裝置請求運算卸載時，對於服務提供者而言，如何分配請求至有限容量的邊緣伺服器並且同時滿足低延遲的需求會是個重要的問題。而當考慮到不同服務提供者間的資源分配時，與哪個服務提供者形成聯盟並且決定金錢交易的多寡亦是個重要的問題。配對賽局很適合用於分配這些請求至邊緣伺服器，特別是在分散式的環境底下。我們提出了兩種使用配對賽局的資源分配方法，單一邊緣與霧系統服務提供者內的卸載方法與不同邊緣與霧系統服務提供者間的卸載方法。在單一邊緣與霧系統服務提供者內的卸載方法中，我們使用無金錢轉移的配對賽局；而在不同邊緣與霧系統服務提供者間的卸載方法中，我們使用有金錢轉移的配對賽局。並且我們將裝置的請求構成虛擬機器。配對賽局能夠提供一個穩定的配對結果，即是不會有任何一組請求與伺服器的配對會相互地更喜歡自己本身目前的配對結果。我們模擬了我們提出的方法，並且顯示出我們的方法對每個邊緣伺服器而言平均可以服務較多的裝置請求並同時滿足延遲限制，而在有金錢轉移的方法下，我們可以得到較高的收入。

關鍵字

資源分配 ； 邊緣計算 ； 配對賽局

並列摘要

In the edge computing environment, the service provider can serve the devices of Internet of Things (IoT) and fog devices with extra low latency when offloading the requests to the edge servers. Nevertheless, the resource allocation with bulk of devices requesting the servers with limited capacity in edge computing for computation offloading while keeping extra low latency will become an important issue for the service providers. Also between different service providers, which service provider to federate and how much to pay for federation is also an important issue. Matching game is appropriate for allocating the requests to the servers, especially in a distributed environment. We proposed two mechanisms, intra-EFS offloading and inter-EFS offloading, of matching game for the resource allocation problem. Specifically, when the resource allocation is within the same service provider, we use matching game without monetary transfer; when the resource allocation is across different service providers, we use matching game with monetary transfer. Also we form the requests from the devices as virtual machine (VM) instances. Matching game can provide a stable result, that is, there will be no pairs of a server and a request that is mutually more favorable than their current matching result. We simulated our proposed mechanisms and showed that we can have a higher average number of served requests for the servers within the latency constraint of the requests, and have a higher revenue when considering the monetary exchange.

並列關鍵字

Resource Allocation ； Edge Computing ； Matching Theory

參考文獻

[1] T. Taleb et al. “On Multi-Access Edge Computing: A Survey of the Emerging 5G Network Edge Cloud Architecture and Orchestration”. In: IEEE Communications Surveys Tutorials 19.3 (thirdquarter 2017), pp. 1657–1681.

[2] “Mobile Edge Computing (MEC); Terminology, v1.1.1”. In: ETSI GS MEC Standard 001 (Mar. 2016).

[3] 5G Vision: 100 Billion connections, 1 ms Latency, and 10 Gbps Throughput. 2015. URL: http://www.huawei.com/minisite/5g/en/defining-5g.html.

[4] OpenFog Consortium. URL: https://www.openfogconsortium.org/.

[5] L. Tang and H. Chen. “Double auction mechanism for request outsourcing in cloud federation”. In: 2015 IEEE International Conference on Communication Workshop