臺灣博碩士論文加值系統

行動運算裝置與網路通訊技術至今已發展甄至成熟，更高的時脈和更多的核心晶片相繼推出，甚至遠遠超越當時1969年阿波羅十一號負責運算把阿姆斯壯送上月球的超級電腦，然而，人們嘗試把越來越複雜的運算應用放到行動裝置上執行，如物體辨識、虛擬實境和畫面華麗的遊戲等等，這些行動應用為大量運算需求的，但是基於物理上的限制，行動裝置只能擁有有限的運算能力，尚未可以完美的處理此類行動應用，假如使用一個運算框架透過利用周邊閒置裝置的幫忙，來增強整體行動運算能力，使得我們即使不把資料送到雲端也可以完成複雜的計算要求，這讓整個行動運算對於網路的要求大幅下降

在本篇論文中，我們設計出在彈性運算框架中如何去實現非集中式分派任務，並利用賽局理論與使用者的移動模型，藉由以上的方法可使整體系統呈現一個完美平衡狀態，同時保證在每個工作之反應時間不逾時的情況下可以達到最小的運算成本

With the improvement of mobile computing devices and cloud computing technologies, a variety of mobile computing applications enrich our lives. In the meanwhile, we found the computation requirement of the mobile application
become more and more complex. However, based on physical limitations, a mobile device can not consummatly process some resource-intensive and time-intensive mobile applications. A concept has been applied to improve the computation capbilities by moving the resource-intensive task to a more powerful remote computation devices. In this thesis, we adopt a framework which can federate our mobile devices and the computation resource of the idle device which around us. Moreover, the framework can decreace the network latency in chorus. We can still complete a complicated task even if we lose the connection with the cloud.
In addition, we propose the dispatching game problem in this thesis. We
combine the game theory model and user mobility. We can achive the maximum
utilization of the whole system and respose time promising. We also
show how a Nash equilibrum always exsit with the condition which the system
has the utilization bound.

口試委員審定書 i
致謝ii
摘要iii
Abstract iv
1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Background and Related Work 5
2.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.1 Imprecise Computing . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.2 Constant Bandwidth Server . . . . . . . . . . . . . . . . . . . . 6
2.1.3 Game Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1.4 Nash Equilibrium . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1.5 Potential Game . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.1 Mobile cloud computing . . . . . . . . . . . . . . . . . . . . . . 8
2.2.2 Decentralized Offloading Game . . . . . . . . . . . . . . . . . . 9
3 Formal Model and Problem Definition 10
3.1 Formal Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.1.1 Communication Model . . . . . . . . . . . . . . . . . . . . . . . 10
Transmission Time . . . . . . . . . . . . . . . . . . . . . . . . . 11
Back-off Time . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.1.2 Computation Model . . . . . . . . . . . . . . . . . . . . . . . . 12
3.1.3 Cost Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.2 Targeted Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4 Game formulation and Game property 15
4.1 Distributed Workload Dispatching Game . . . . . . . . . . . . . . . . . . 15
4.2 Game property . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.3 Distributed Workload Dispatching Algorithm . . . . . . . . . . . . . . . 19
5 Experiment 20
5.1 Experiment Environment and Configuration . . . . . . . . . . . . . . . . 20
5.2 Experiment Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
6 Conclusion 26
Bibliography 27

[1] K.-T. Chen, Y.-C. Chang, P.-H. Tseng, C.-Y. Huang, and C.-L. Lei, “Measuring the Latency of Cloud Gaming Systems.”
[2] J. W. S. Liu, K.-J. Lin, W.-K. Shih, A. C.-s. Yu, J.-Y. Chung, and W. Zhao, “Algo- rithms for scheduling imprecise computations,” Computer, vol. 24, no. 5, pp. 58–68, 1991.
[3] L. Abeni and G. Buttazzo, “Integrating multimedia applications in hard real-time systems,” in Real-Time Systems Symposium, 1998. Proceedings., The 19th IEEE, Dec 1998, pp. 4–13.
[4] L. Abeni, G. Lipari, and J. Lelli, “Constant bandwidth server revisited,” SIGBED Rev., vol. 11, no. 4, pp. 19–24, 2014.
[5] J. von Neumann and O. Morgenstern, “Theory of Games and Economic Behavior,” 1944.
[6] J. F. Nash, “Equilibrium Points in N-Person Games,” Proceedings of the National Academy of Sciences of the United States of America, vol. 36, pp. 48–49, 1950.
[7] D. Monderer and L. S. Shapley, “Potential games,” Games and Economic Behavior, vol. 14, no. 1, pp. 124 – 143, 1996.
[8] N. Fernando, S. W. Loke, and W. Rahayu, “Mobile cloud computing: A survey,” Future Generation Computer Systems, vol. 29, no. 1, pp. 84 – 106, 2013.
[9] V. Kalogeraki, “Mobile peer-to-peer computing: Challenges, metrics and applica- tions,” in Proceedings of the 6th International Conference on Mobile Data Manage- ment, 2005, pp. 331–332.
[10] G. Kortuem, “Proem: A middleware platform for mobile peer-to-peer computing,” SIGMOBILE Mob. Comput. Commun. Rev., vol. 6, no. 4, pp. 62–64, 2002.
[11] M. Satyanarayanan, P. Bahl, R. Caceres, and N. Davies, “The case for vm-based cloudlets in mobile computing,” IEEE Pervasive Computing, vol. 8, no. 4, pp. 14– 23, 2009.
[12] W. Zhang, S. Tan, F. Xia, X. Chen, Z. Li, Q. Lu, and S. Yang, “A survey on deci- sion making for task migration in mobile cloud environments,” Personal Ubiquitous Comput., vol. 20, no. 3, pp. 295–309, 2016.
[13] C.-S. S. Jian-Hao Chen, “Design and Implemntation of Resource-Aware Computa- tion Framework over Heterogeneous Mobile Cloud System.”
[14] D. Mazza, D. Tarchi, and G. E. Corazza, “A partial offloading technique for wireless mobile cloud computing in smart cities,” in Networks and Communications (Eu- CNC), 2014 European Conference on, 2014, pp. 1–5.
[15] A. Toma, J. J. Chen, and W. Liu, “Computation offloading for sporadic real-time tasks,” in 2014 IEEE 20th International Conference on Embedded and Real-Time Computing Systems and Applications, 2014, pp. 1–10.
[16] Y. Wang, X. Lin, and M. Pedram, “A nested two stage game-based optimization framework in mobile cloud computing system,” in Service Oriented System En- gineering (SOSE), 2013 IEEE 7th International Symposium on, March 2013, pp. 494–502.
[17] V.Cardellini,V.DeNittoPersoné,V.DiValerio,F.Facchinei,V.Grassi,F.LoPresti, and V. Piccialli, “A game-theoretic approach to computation offloading in mobile cloud computing,” Mathematical Programming, vol. 157, no. 2, pp. 421–449, 2016.
[18] X. Chen, “Decentralized Computation Offloading Game for Mobile Cloud Com- puting,” IEEE Transactions on Parallel & Distributed Systems, vol. 26, no. 4, pp. 974–983, April 2015.
[19] S. Josilo and G. Dán, “Selfish computation offloading for mobile cloud computing in dense wireless networks,” Computing Research Repository, vol. abs/1604.05460, 2016.
[20] X. Chen, L. Jiao, W. Li, and X. Fu, “Efficient multi-user computation offloading for mobile-edge cloud computing,” IEEE/ACM Transactions on Networking, vol. PP, no. 99, pp. 1–1, 2015.
[21] E. Meskar, T. D. Todd, D. Zhao, and G. Karakostas, “Energy efficient offloading for competing users on a shared communication channel,” in 2015 IEEE International Conference on Communications (ICC), June 2015, pp. 3192–3197.
[22] X. Ma, C. Lin, X. Xiang, and C. Chen, “Game-theoretic analysis of computation offloading for cloudlet-based mobile cloud computing,” in Proceedings of the 18th ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems, 2015, pp. 271–278.
[23] J. Anas Toma, “Computation Offloading for Frame-Based Real-Time Tasks with Resource Reservation Servers,” 25th Euromicro Conference on Real-Time Systems, pp. 103–112, 2013.
[24] K. Mohamad, “Efficient Scheduling Algorithms for Wireless Resource Allocation and Virtualization in Wireless Networks,” Electronic Thesis and Dissertation Repos- itory. Paper 3445., 2015.
[25] J.Tang,G.Xue,andW.Zhang,“Maximumthroughputandfairbandwidthallocation in multi-channel wireless mesh networks,” in Proceedings IEEE INFOCOM 2006., 2006, pp. 1–10.
[26] GiorgioButtazzoandEnricoBini,“OptimalDimensioningofaConstantBandwidth Server,” Proceedings of the 27th IEEE International Real-Time Systems Symposium, 2006.
[27] M. Mavronicolas, I. Milchtaich, B. Monien, and K. Tiemann, Congestion Games with Player-Specific Constants. Berlin, Heidelberg: Springer Berlin Heidelberg, 2007, pp. 633–644.