臺灣博碩士論文加值系統

隨著普及運算技術的快速發展，普及服務的內容和環境也日益擴大，使得服務模式從提供單一服務，轉變為可同時運用多種資源實現複合式服務。在有限資源的普及網路環境中，同時實現多個服務需求易產生資源不足的問題，以致發生服務中斷或服務拒受。因此，資源排程機制是一項關鍵技術，以改善服務要求允入、資源使用效率和服務品質之間的權衡。
在本篇論文中，提出的「基於基因演算法普及服務中可提供彈性服務品質管理之資源排程技術」可解決上述的問題。我們發現在服務品質和資源需求之間，存在四種不同型態的關係：(1)線性關係包含飽和，(2)線性關係包含停滯與飽和，(3)偏移的步級關係，(4)指數關係。基於上述四種資源與品質模型的推導，可定義服務資源需求的最大值和最小值，並以此範圍作為品質保障的協商準則。在有限資源的環境中，當使用者提出服務要求時，資源短缺偵測將診斷現存可用資源是否足以執行服務。若可用資源充足，讓此服務要求進入系統的工作排程，反之，在服務要求之間進行服務協調，找到具有品質保障的可行資源配置。
在品質和資源限制之下，為了找出最佳化的資源配置，彈性資源排程需要效率高的計算技術。根據定義的目標函數，透過基因演算法，可有效解決問題並因應普及服務要求的即時性。最後實驗結果顯示，本篇論文提出之方法的確有助於服務品質保障及提高服務要求允入率。

With the rapid development of pervasive computing technology, ubiquitous services contents and environments are fast evolving. New techniques lead the service model of single providers to a new service model collaborating with various providers. In a resource-limited environment, many service requests issuing simultaneously will cause a problem of resource insufficiency. This problem can lead to either an interrupt of the running services or a decline of service requests. Thus, the resource scheduling mechanism is the key technique to improve the tradeoff between request admittance, resource utilization and service quality.
In this paper, a GA-based approach to resource scheduling supporting flexible quality management of ubiquitous services is proposed to solve the problem mentioned above. In this work, first the relationships between service of quality and resource requirements are explored. There are four different types of relations including (1) linear with saturation (LWS), (2) linear with deadzone and saturation (LWDS), (3) shifted step (SS), and (4) exponential (EX). Based on the derivation of the resource-quality model with the four relations, we define the maximum and minimum of resource requirement and regard the scope as the negotiation criterion for quality guarantee. When users issue service requests in limited-resource environment, the resource shortage detection checks whether the available resource is enough to execute all service requests or not. If the available resource is sufficient, the required service requests are admitted and scheduled for works. When the resource is not sufficient, a service negotiation is conducted to find out a feasible resource allocations for all service requests with certain quality guarantees.
The proposed flexible resource scheduler needs an effective and efficient computation scheme to find the optimal resource allocation under the quality and resource constraints. In order for a real-time solution, a Genetic Algorithm is developed to schedule resource according to the defined objective functions. Experimental results show that the proposed approach definitely benefits quality guarantee of service and the increasing of service request admittance ratio.

LIST OF TABLES VIII
LIST OF FIGURES IX
CHAPTER 1 INTRODUCTION 1
1.1 BACKGROUND AND MOTIVATION 1
1.2 ISSUES IN RESOURCE SCHEDULING IN UBIQUITOUS SERVICES 5
1.3 THESIS ORGANIZATION 6
CHAPTER 2 RELATED WORK 7
2.1 UBIQUITOUS SERVICE 7
2.1.1 The Definition of Ubiquitous Service 7
2.1.2 The Application of Ubiquitous Service 8
2.1.3 Issues in Ubiquitous Service 9
2.2 NETWORK AND MULTIMEDIA IN UBIQUITOUS SERVICE 10
2.2.1 Network Technology 10
2.2.2 Multimedia Service 11
2.3 RESOURCE SCHEDULING 12
2.3.1 Opportunistic Load Balancing 12
2.3.2 Minimum Execution Time 12
2.3.3 Minimum Completion Time 13
2.3.4 Minimum-minimum Completion Time 13
2.4 SERVICE LEVEL AGREEMENT 14
CHAPTER 3 A RESOURCE SCHEDULING APPROACH OF FLEXIBLE QUALITY MANAGEMENT 16
3.1 SERVICE MODEL 16
3.1.1 Overview of Service Model 16
3.1.2 Mathematic Equation of Service Model 18
3.1.2.1 Modeling of Service Profile 18
3.1.2.2 Modeling of Device Profile 19
3.1.2.3 Modeling of Request Profile 19
3.2 SCHEDULING CRITERIA 20
3.2.1 Why is Scheduling Criteria? 20
3.2.2 The Proposed Scheduling Criteria 21
3.3 SCHEDULING STRATEGY 26
3.3.1 The Proposed Algorithm 26
3.3.2 Operational Flow 29
3.3.3 The Design of GA Algorithm 32
3.3.3.1 Introduction of GA 32
3.3.3.2 Population Initialization 34
3.3.3.3 Fitness Function 35
3.3.3.4 Selection 36
3.3.3.5 Genetic Operator 37
3.3.3.6 Termination Condition 39
CHAPTER 4 NUMERIC RESULTS AND ANALYSIS 40
4.1 SIMULATION DESIGN 40
4.1.1 Configuration of Experimental Environments 40
4.1.2 Experiment Parameters 41
4.2 EXPERIMENT RESULTS 42
CHAPTER 5 CONCLUSION AND FUTURE WORK 89
5.1 CONCLUSION 89
5.2 FUTURE WORK 90
REFERENCES 91

[ARM98] R. Armstrong, D. Hensgen, and T. Kidd, “The Relative Performance of Various Mapping Algorithms is Independent of Sizable Variances in Run-time Predictions, 7th IEEE Heterogeneous Computing Workshop, pp. 79-87, 1998.
[BRA01] T.D. Brauna, et al., “A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems , Journal of Parallel and Distributed Computing, Vol. 61, Issue 6 , pp. 810-837, 2001.
[CUR07] F. Curbera, “Component Contracts in Service-Oriented Architectures, Computer, Vol. 40, No. 11, Nov. 2007.
[DUF07] S. Duflos, B. Kervella and V. C. Gay, “Considering Security and Quality of Service in SLS to Improve Policy-Based Management of Multimedia Services, Proceedings of the 6th International Conference on Networking, 2007.
[FOR09] Forrester Research. Available: http://www.forrester.com/rb/research
[FRE93] R. F. Freund and H. J. Siegel, “Heterogeneous Processing, IEEE Computer, Vol. 26, No. 6, pp. 13-17, Jun. 1993.
[FRE98] R. F. Freund, et al., “Scheduling Resources in Multi-User, Heterogeneous, Computing Environments with SmartNet, in 7th IEEE Heterogeneous Computing Workshop, pp. 184-199, Mar. 1998.
[GOU07] A. Gouya, N. Crespi, and E. Bertin, “Service Invocation Issues within the IP Multimedia Subsystem, in Proceedings of the Third International Conference on Networking and Services, June 2007.
[GRI07] D. Griffin and D. Pesch, “A Survey on Web Services in Telecommunications, IEEE Communications Magazine, pp. 28-35, July 2007.
[GU04] T. Gu and H. K. Pung, “Toward an OSGi-Based Infrastructure for Context-Aware Applications, IEEE Pervasive Computing, pp. 66-74, 2004
[HAY07] T. L. Hayes, M. Pavel, N. Larimer, I. A. Tsay, and J. Nutt, “Distributed Healthcare: Simultaneous Assessment of Multiple Individuals, IEEE Pervasive Computing, pp. 36-43, 2007.
[HUH05] M. N. Huhns and M. P. Singh, “Service-oriented computing: Key concepts and principles, IEEE Internet Computing, Feb. 2005.
[IBA77] O. Ibarra and C. E. Kim, “Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors, Journal of the ACM, Vol. 77, No. 2, pp. 280–289, Apr. 1977.
[IWS09] Internet World Stats. Available: http://www.internetworldstats.com/
[JON02] M. Jonsson, “Supporting Context Awareness in Ubiquitous Service Environments, 2002.
[JOS07] A. D. Joseph, “Healthcare Systems and Other Applications, IEEE Pervasive Computing, pp. 59-63, 2007.
[KOS02] M. Kosuga, N. Kirimoto, T. Yamazaki, T. Nakanishi, M. Masusaki, and K. Hasuike, “A multimedia service composition scheme for ubiquitous networks, Journal of Network and Computer Applications, pp. 279-293, 2002.
[KRI06] S. Krile and D. Perakovic, “Bandwidth Optimization in SLA Negotiation Process, Mobile Future, 2006 and the Symposium on Trends in Communications, pp. 36-39, 2006.
[LEE03] C. Lee, D. Nordstedt, and S. Helal, “Enabling Smart Spaces with OSGi, IEEE Pervasive Computing, 2003.
[LIU08] L. Liu, H. Sun, T. Yu and Y. Jin, “Research on SLA negotiation in Manufacturing Grid, 12th IEEE International Conference on Computer Supported Cooperative Work in Design, pp. 862-868, 2008.
[OXY00] MIT Project Oxygen. Available: http://www.oxygen.lcs.mit.edu/
[RIT05] G. Ritchie and J. Levine, “A Fast, Effective Local Search for Scheduling Independent Jobs in Heterogeneous Computing Environments, Journal of Computer Applications, Vol. 25, Issue 5, pp. 1190-1192, 2005.
[ROU06] G. Roussos and A. Marsh, “A Blueprint for Pervasive Self-Care Infrastructures, in Proceedings of the Fourth Annual IEEE International Conference on Pervasive Computing and Communications Workshops, 2006.
[SCH06] H. A. Schmid, “Service Congestion: The Problem, and an Optimized Service Composition Architecture as a Solution, IEEE International Conference on Web Services, 2006.
[SIN02] M. P. Singh, “Trustworthy Service Composition: Challenges and Research Questions, in Proceedings of the Autonomous Agents and Multi-Agent Systems Workshop on Deception, Fraud and Trust in Agent Societies, pp. 30-38, July 2002.
[SUN06] T. Sun, S. Li, and Q. Zhu, “An Optimized Strategy of Service Negotiation, in Proceedings of the Second IEEE International Symposium on Service-Oriented System Engineering, 2006.
[WEI91] M. Weiser, “The Computer for the 21st Century, Scientific American Special Issue on Communications, Computers, and Networks, Sep. 1991.
[XIA07] J.C. Xia, C.K. Chang, T.H. Kim, H.I. Yang, R. Bose ,and S. Helal, “Fault-resilient Ubiquitous Service Composition, 3rd IET International Conference on Intelligent Environments, 2007.
[YAM04] K. Yamazaki, “Research Directions for Ubiquitous Services, in Proceedings of the 2004 International Symposium on Applications and the Internet, 2004.
[YU06] Z. Yu, X. Zhou, and Z. Yu, “An OSGi-Based Infrastructure for Context-Aware Multimedia Services, IEEE Communications Magazine, Oct. 2006.