無線網路最佳遞增嚴格凹型效用函數資源分配

Abstract

效用函數被廣泛用於模擬用戶所收到的服務質量。在彈性通訊此類型的傳輸資料中，一般是凹效用函數。最近提出的Elastic Allocation的演算法，在假定資源是可無窮地分割並且每位使用者的下載佇列總是有足夠的資料傳輸的情況下，使得總效用函數最大化。但我們發現，EA的演算法並不保證達到最佳解。事實上，EA所求出的解可能是不可行的。在本文中，我們提出一個改進的Elastic Allocation演算法，能在相同的假設環境下找到最佳解。接著，我們再將此結果及解法，擴展到一個下載佇列是在資料量為正常累積的環境。在實際的系統，分配的資源通常有一個基本單位的限制。因此，我們進一步地針對這種制度，設計在假設為使用者的下載佇列為不斷累積，以及正常累積的演算法。為了減少計算複雜度，我們建議一個近似最佳解的資源分配演算法。最後針對以上演算法，進行模擬來評估所提出的演算法在總效用函數和執行時間上的表現。結果顯示我們提出的算法能達到更好的表現。

Utility functions are widely used to model user perceived service quality. For elastic traffic, the utility function is often increasing and strictly concave. An elastic allocation (EA) algorithm has recently been proposed to maximize the total utility obtained by users, assuming resource is infinitesimally divisible and queues are constantly backlogged. We found that the EA algorithm is not always optimal. In fact, the solution it obtains can be infeasible. In this paper, we present a modified elastic allocation algorithm which is guaranteed to find the optimal solution under the same assumptions. The result is generalized for a system where queues are generally backlogged. In a real system, there is normally a basic unit for resource. Therefore, we further extend the designs to such a system for both constantly backlogged and generally backlogged queues. To reduce computational complexity, we also propose near-optimal resource allocation algorithms. Simulations are conducted to evaluate the proposed algorithms in terms of utility sum and execution time. Results show that our proposed algorithms perform better than previous work.