噪聲限制網路下以模擬退火演算法優化拉格朗日乘數最佳化機率性快取策略

快取是一項實用的技術，透過在網路使用量離峰時段，將受歡迎的檔案預先存取在一些快取幫助者中，用以降低尖峰時段的網路壅塞情形。在這篇研究裡，我們重新回顧了於躁聲限制網路架構下機率性檔案快取的問題，用戶會根據一個給定的機率分布模型，連續地送出多個檔案需求。我們提出一個基於拉格朗日乘數的演算法，在最大化各類用戶中最小的檔案傳送成功機率的目標下，保證所求得的解至少為區域最佳解。而基於這一個非凸優化的問題，由拉格朗日乘數演算法所得到的解可能會陷入很小的區域最大值，我們便更進一步結合模擬退火演算法的概念，使得我們原先基於拉格朗日乘數的演算法能夠跳離微小的區域最大值，成為更有力度的求解演算法。由大量的實驗結果驗證得出，我們提出的演算法求得的解在效能上勝過目前其他現有的算法，並且解的收斂情形更不易受到初始值的影響。再者，為了增加系統整體的傳送流通量，我們提出最大化用戶的加權平均檔案傳輸成功機率作為另一個效能指標，取代原先最大化各類用戶中最小的檔案傳送成功機率。在新的效能指標下，透過調整原先的演算法使其能套用在新問題中，亦得出一些與前述相似的結論。

關鍵字

無線快取；機率性快取策略；拉格朗日乘數法；模擬退火演算法

並列摘要

Caching is a powerful technique that reduces the peak traffic loading by pre-storing popular contents in caching helpers during off-peak hours. In this work, the problem of probabilistic content caching in noise-limited network is revisited in which users may sequentially request multiple contents according to a probability distribution. A novel algorithm based on the method of Lagrange multiplier is proposed to produce policy that guarantees (locally) maximal content delivery success probability (CDSP) of the worst user. Due to the non-convex nature of the problem, it is likely that this algorithm would be trapped into an insignificant local maximum. We further propose an enhanced version of the algorithm based on the idea of simulated annealing, which enables the algorithm to escape local maxima. Extensive simulations are conducted and the results show that the proposed enhanced algorithm provides policies that outperform the state-of-the-art and is significantly less sensitive to initial values. Moreover, to increase the overall system throughput, we propose another metric which maximizes the weighted average CDSP, instead of the worst user's CDSP. For this new metric, an algorithm adapted from the proposed algorithm is introduced, for which similar conclusions can be drawn.