基於賽局理論的分散式負載分配演算法

行動運算裝置與網路通訊技術至今已發展甄至成熟，更高的時脈和更多的核心晶片相繼推出，甚至遠遠超越當時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.

並列關鍵字

Mobile Computing ； Decentralized Dispatching ； Game theory

參考文獻

[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.

國際替代計量

基於賽局理論的分散式負載分配演算法

全文下載

主題瀏覽