降低行動裝置上大型時間尺度傳輸排程的資源消耗

Reducing Training Overhead of Large Time-Scale Transfer Scheduling for Mobile Devices

林庭安(Ting-An Lin)

指導教授 ： 徐正炘

國立清華大學/電機資訊學院/資訊工程學系/碩士(2013年)

摘要

在這篇論文中，我們專注於大型時間尺度(數分鐘到數小時)下的傳 輸排程，它提供了更大的傳輸效能改進空間，這是我們與大多數在頻道感知排程方面的研究不同之處 。 我們在Android平台上設計、實作和驗證了一個基於馬可夫決策理論的框架用來分析使用者行為並排程傳輸。 我們的模擬結果顯示，現實中的行動裝置裝使用者可以受益於我們的框架。 舉例來說，50％的使用者享受到20％-90％的傳輸速度提升與15分鐘的平均延遲，當截止時間為40分鐘時。
此外，我們的量化與降低產生排程演算法參數的資源消耗。 我們指出了產生排程演算法參數的最佳使用者資料長度為30天。我們用不同的聚類演算法對使用者進行分組，以減少產生排程演算法參數的資源消耗。藉由使用從真實的使用者收集到的資料，我們指出了聚類演算法最佳參數。 同時，我們的聚類演算法，可以減少產生排程演算法參數的資源消耗，但不會損失太多的效能。 當使用了我們的演算法，可以節省產生排程演算法參數的時間高達59.9％，但只導致了小於18％的效能下降。

關鍵字

行動裝置 ； 排程 ； 叢集

並列摘要

In this thesis, we focus on large time-scale scheduling of mobile data transfer, e.g., in minutes or hours. Such large time-scale provides significantly more room for performance improvement in real-life scenarios, which
differs our work from most existing channel-aware scheduling studies.
In particular, we design, implement, and evaluate a framework for profiling and scheduling based on Markov decision theory, using the Android platform. Our trace-driven simulations show that mobile users in real-life scenarios can benefit significantly from our framework. For example, 50% of mobile users will enjoy 20%-90% throughput improvement with a deadline guarantee of 40 minutes and an average delay of 15 minutes.
In addition, we quantify and reduce the overhead of generating model parameters of the proposed scheduling algorithms. We determine the best training window size: 30 days. We adopt various clustering algorithms to group
users in order to reduce training overhead. We empirically determine the best system parameters of the clustering algorithms using real traces. Our clustering algorithms reduce the training overhead without sacrificing too much
performance: it saves up to 59.9% of training time while incurring <18% performance degradation.

並列關鍵字

mobile device ； scheduling ； clustering

參考文獻

[3] 3GPP TS 36.211. Evolved universal terrestrial radio access (E-UTRA); physical

[5] N. Balasubramanian, A. Balasubramanian, and A. Venkataramani. Energy consumption in mobile phones: a measurement study and implications for network applications. In ACM SIGCOMM Conference on Internet Measurement Conference (IMC’09), November 2009.

[6] M. Bayir, N. Eagle, and M. Demirbas. Discovering spatiotemporal mobility profiles of cellphone users. In Proc. of IEEE International Symposium on a World of

[8] J. Han. Data Mining: Concepts and Techniques. Morgan Kaufmann Publishers Inc.,

[10] W. Hsu, T. Spyropoulos, K. Psounis, and A. Helmy. Modeling timevariant user mobility in wireless mobile networks. In Proc. of IEEE International Conference on