公平拍賣機制於行動邊緣運算下之資源分配與定價啟發式最佳化

Abstract

移動邊緣運算是一種有前途的技術，可提供計算和無線資源，並縮短與移動終端用戶的通訊延遲。移動邊緣運算位於整個網絡架構的邊緣，對於計算資源受限的移動終端用戶來說，移動邊緣運算可以用於卸載應用，而且在距離上比起傳統的雲數據中心更為接近。然而，由於移動邊緣運算的資源有限，因此需要一個好的資源分配方式，以有效地分配資源給終端用戶，並防止資源被低效利用。拍賣機制非常適合用以實現資源的最佳分配，並為資源提供者和資源使用者提供參與資源分配交易的誘因。 目前大部分將拍賣機制應用於移動邊緣運算中的資源分配的研究都沒有綜合考慮計算和無線資源的分配，這些研究都只專注於計算資源的分配，而這會使移動終端用戶面臨暴露問題，最終導致較低的社會福利。此外，大多數拍賣模型的研究都僅關注最大化社會福利，很少考慮拍賣的公平性，但是忽視公平性通常會導致某部分的資源使用者的服務匱乏，造成使用者流失，使用者流失可能會導致寡頭市場的產生，這給剩餘的使用者降低出價的議價權，從而降低社會福利。 為了解決上述問題，我們首先提出了一個單輪拍賣機制，該機制在移動終端用戶卸載任務期限約束下，共同分配資源提供者（即移動運營商）的計算和無線資源給資源使用者（即移動終端用戶），同時最大化社會福利。我們將此資源分配問題建模為一個整數線性規劃問題。為了有效地解決這個整數線性規劃問題，我們提出了一種貪心近似演算法，它提供了一個與商業求解器的解決方案相比具有快速執行速度的近似最優解。其次，基於一輪拍賣機制，我們提出了一個公平拍賣機制，用於公平分配資源，以解決使用者流失的問題，該機制提供了一種可以有效且公平地分配計算和無線資源給移動用戶的方法。最後，大量模擬實驗的結果證明我們提出的模型確實可以在最大化系統的整體福利之餘，解決暴露問題和使用者流失問題。在這篇研究當中，我們的主要貢獻是提供了一種在資源競爭的移動邊緣運算環境中，使用拍賣機制來有效、高效、且公平地共同分配計算和無線資源給移動用戶的方法。

Mobile edge computing is a promising technology that provides computing and wireless resources with lower communication latency to the end user. Deployed at the network's edge, mobile edge computing is geographically closer for resource-restricted mobile devices to offload their task than traditional cloud data centers. However, with limited resources, a well-designed resource allocation scheme is needed to efficiently allocate resources to end users and prevent resources from under-utilization. The auction mechanism is well-suited for achieving optimal allocation strategy and incentivizes resource providers and consumers to participate in the resource allocation trade. Most existing works that apply auction mechanisms failed to jointly allocate computing and wireless resources while maximizing social welfare under task deadline constraint, leading to the exposure problems for mobile users and minor social welfare. Furthermore, most auction-based models focus only on maximizing social welfare. Few have considered fairness among auction participants, but without considering fairness leads to the bidder dropout problem due to service starvation in a recurrent auction environment, and the bidder dropout problem may lead to an oligopoly market, which gives the remaining bidder bargaining power to lower their bid, thus decreasing social welfare. To address the problems mentioned above, we propose a one-round auction mechanism, which jointly allocates computing and wireless resources of the resource provider, i.e., the mobile operator, to consumers, i.e., mobile users, while maximizing social welfare under users' offloaded tasks' deadline constraint. We modeled this resource allocation problem as an integer linear programming problem. To solve this integer linear programming problem efficiently, we proposed a greedy approximation algorithm, which provides a near-optimal solution with fast execution speed compared to the commercial solver's solution. Second, based on the one-round auction mechanism, we proposed a fairness-aware auction mechanism for fair resource allocation to address the user's dropout problem. This mechanism provides a way to efficiently and fairly allocate computing and wireless resources to mobile users while preventing the bidder dropout problem from arising. Finally, we performed extensive simulations, proving that our proposed model can solve the exposure and bidder dropout problems while maximizing the social welfare. In brief, our main contribution is providing an effective and efficient way to jointly and fairly allocate computing and wireless resources to mobile users using a fairness-aware auction mechanism in a resource-competitive MEC environment.