在無線接取網路中的霧運算資源分配研究

Dynamic Resource Allocation for Fog Computing in Radio Access Networks

李加富(Chia-Fu Lee)

指導教授 ： 周俊廷

國立臺灣大學/電機資訊學院/電信工程學研究所/碩士(2019年)

https://doi.org/10.6342/NTU201902203

摘要

霧計算(Fog Computing)允許在網絡的邊緣部署應用程序以減少延遲。而集
中式無線電接入網絡(Cloud Radio Access Network)則被認為是最可能實現霧
計算 的平台。然而，原本在集中式無線電接入網絡中使用的通用處理器
(General Purpose Processor)，其計算和存儲資源可能不足以同時支持基帶處
理(Baseband Processing)和霧計算。因此，問題就是要如何利用通用處理器的
計算和存儲資源 來實現高效率和低延遲。

在本篇論文中，我們研究集中式無線電接入網絡中的霧計算，它支持延遲
敏感(Delay-Sensitive)和延遲容忍(Delay-Tolerant)應用。為了分析集中式無
線電接 入網絡中的霧計算系統，我們將系統抽象為排隊模型(Queueing
Model)。在排隊 模型中，我們嘗試找到最佳資源分配方式。該最佳資源的分配
方式會讓丟失率 (Loss Rate)最小化並且滿足平均端到端延遲(Average End
to-End Delay)的要求。

我們提出了兩種尋找最佳資源分配方式的方法。首先，我們提出了一種窮
舉方法(Exhaustive Approach)。在使用窮舉方法時，必須比較所有資源分配方
法 的丟失率和平均端到端延遲。而為了找到其中一個資源分配方法的丟失率和
平 均端到端延遲時，我們提出將傑克森網路(Jackson Network)當作解數學的
方式。 其次，我們也提供了一種啟發式方法(Heuristic Approach)。雖然窮舉
方法總能找 到最佳的資源分配方式，然而當系統變大時，找到最佳資源分配方
式所需的時 間將會指數上升。因此，此種啟發式方法就是節省許多時間卻能找
到效能相近 的資源分配方式。

為了驗證在窮舉方法中，使用傑克森網路是一個合理的數學解法，我們構

建了一個模擬工具來模擬不同資源分配方案的丟失率和平均端到端延遲。而最
後結果顯示，使用傑克森網路來計算的數學結果和模擬結果差異最大為 0.1
％。 表示傑克森網路實際是可以被拿來應用的。而為了驗證啟發式方法是否可
行， 我們將它找到的結果與窮舉方法的結果進行比較。而結果顯示，兩種方法
的所 找出來的資源分配方式，其產生的丟失率差異最大為 0.25％。因此，這
種啟發 方法是可以應用在估計大型的系統的資源分配方式。

關鍵字

霧運算 ； 集中式無線接入網路 ； 資源分配最佳化 ； 排隊模型 ； 傑克森網路 ； 窮舉方法 ； 啟發方法

並列摘要

Fog computing approach enables the deployment of applications at the network edgetoreducedelay. Thecloud-basedradioaccessnetwork(C-RAN)isconsideredas an effective platform to implement fog computing. However, computing and storage resources of general purpose processors (GPPs) in the C-RAN might not be enough to support baseband processing and fog computing at the same time. The problem becomes how to utilize the computing and storage resources of GPPs to achieve high efficiency and low delay. In this thesis, we explore fog computing in C-RAN that supports both delaysensitive (DS) and delay-tolerant (DT) applications. To analyze the system of fog computing in C-RAN, we abstract the system as a queueing model. In the queueing model, wetry tofind thebest resourceallocationschemethatminimizes theloss rate with the constraint of the average end-to-end delay. In this thesis, we propose two approaches to find the best resource allocation scheme. First, a exhaustive approach is proposed. While using exhaustive approach, all of the loss rates and average end-to-end delay of resource allocation schemes have to be found. Jackson network is proposed to be applied in the mathematical tool to find the loss rate and the average end-to-end delay of a resource allocation scheme. Second, a heuristic approach is proposed. Although the exhaustive approach can always find the best resource allocation scheme, it takes too much time to find the scheme when the system size is large. As a result, the heuristic approach is proposed to find the resource allocation scheme that has the similar loss rate and average end-to-end delay to the loss rate and average end-to-end delay of the best resource allocation scheme.
To validate results from the mathematical tool in the exhaustive approach, we also build a simulation tool to find the loss rate and the average end-to-end delay of a resource allocation scheme. Results show that there are at most 0.1% differences of results from the mathematical tool and from the simulation tool. To validate results from the heuristic approach, we compare them to results from exhaustive approach. Results show that the difference of loss rates found both approach is at most 0.25% while constrains are still held in heuristic approach

並列關鍵字

Fog computing ； C-RAN ； Resource allocation ； Queueing model ； Jackson network ； Exhaustive approach ； Heuristic approach

參考文獻

[1] O. Bibani and S. Yangui and R. H. Glitho and W. Gaaloul and N. Ben HadjAlouane and M. J. Morrow and P. A. Polakos, “A Demo of a PaaS for IoT ApplicationsProvisioninginHybridCloud/FogEnvironment”,IEEEInternational Symposium on Local and Metropolitan Area Networks, pp. 1- 2, June 2016.

[2] X. Masip-Bruin and E. Marín-Tordera and G. Tashakor and A. Jukan and G. Ren, “Foggy Clouds and Cloudy Fogs: A Real Need for Coordinated Management of Fog-to-Cloud Computing Systems”, IEEE Wireless Communications vol.23, no. 5, pp. 120-128, Oct. 2016

[3] M.ChiangandT.Zhang,“Fog and IoT: An Overview of Research Opportunities”, IEEE Internet of Things Journal vol. 3, no. 6, pp. 854-864, Dec. 2016

[4] K. Liang and L. Zhao and X. Chu and H. Chen, “An Integrated Architecture for Software Defined and Virtualized Radio Access Networks with Fog Computing”, IEEE Network vol. 31, no. 1, pp. 80-87, Jan. 2017

[5] M. M. Rahman and C. Despins and S. Affes, “ Design Optimization of Wireless AccessVirtualizationBasedonCost: QoSTrade-OffUtilityMaximization”,IEEE TransactionsonWirelessCommunicationsvol.15,no.9,pp.6146-6162,Sept.2016