臺灣博碩士論文加值系統

品質感知服務配置意指依據使用者之品質需求找尋最佳解決方案的服務配置方法。目前關於品質感知服務配置的研究大多著重於單一使用者需求的服務配置，忽略同時有多個使用者的情況。這些論文假設系統一次僅處理一個使用者需求。然而，當有多個使用者同時競爭相同的最佳服務時，需求之間會相互衝突，造成過度等待、服務超載的問題。基於上述，我們首先定義「時間限制下的服務配置問題」為多使用者需求配置服務。這個問題以服務資源有限、時間有限、使用者之間有競爭關係為前提，討論多使用者需求的組合服務配置，目標是為最多的使用者找出符合其品質需求的解決方案。為了解決此問題，我們提出「多用戶服務配置系統」。此系統包含六個主要元件，分別為「用戶管理元件」、「需求分類元件」、「服務管理元件」、「服務分類元件」、「組合服務規劃元件」與「服務品質監督元件」。其中，「組合服務規劃元件」在「多用戶服務配置系統」中扮演相當重要的角色，主要工作為在時限內為多使用者分配服務。於此元件，我們進而提出三種演算法：「時限下服務導向擴增配置演算法」、「用戶導向擴增配置演算法」與「貪心多對多配置演算法」。透過動態更新超載服務與使用者品質需求之間相似程度，避免使用者花費過多的時間等待不符時間需求的超載服務，進而達成最大化成功使用者需求個數的目標。最後，我們將提出之方法應用於「時間限制下的服務配置問題」中，並於實驗證實這些方法可有效的最大化成功的使用者需求數量。

Quality of service (QoS)-aware service composition aims to select an optimal execution plan to maximize the quality values of the resulting composite service while satisfying user-specified constraints. Existing methods on QoS-aware service composition mostly orchestrate multiple services to meet a single user request at a time and neglect serving multiple user requests simultaneously. In the case of multiple user requests at the same time, users will compete for the service with best quality, which cause conflict and overload in QoS-aware service composition. To overcome this shortcoming, we first model the problem as a Time-Constrained Service Composition (TCSC) problem aiming to determine composite services with the maximum number of success user requests. A Multi-User Service Composition System (MUSCS) is then proposed to find feasible solutions, which contains six main components, including User Manager, Request Classifier, Service Controller, Service Classifier, Abstract Service List (ASL) Composer and ASL monitor. Among these components, the ASL Composer plays a major role to deploy candidate services for multiple user requests in a reasonable time. We therefore develop three algorithms for the ASL Composer, namely Time-Constrained Incremental On-Demand Algorithm (TCIDA), User Oriented Incremental On-Demand Algorithm (UOIDA), and Greedy Multiple Matching (GMM). By dynamically updating the similarity between service quality and user quality requirement, the proposed algorithms are able to release the overloaded service and decrease the conflict conditions. The evaluation results demonstrate the effectiveness of our algorithms in term of the number of success user requests.

List of Tables VIII
List of Figures IX
Chapter 1. Introduction 1
1.1 Background 2
1.2 Motivation 3
1.3 Contributions of this Thesis 4
1.4 Organization of this Thesis 5
Chapter 2. Related Works 6
2.1 Service Composition Approaches 6
2.1.1 Local Optimization Approaches 8
2.1.2 Global Optimization Approaches 9
2.1.3 Heuristic Approaches 9
2.2 Service Selection for Multiple User Requests 10
Chapter 3. Problem Modeling and Formulation 11
3.1 User Request and Multiple User Requests Modeling 12
3.1.1 Modeling of User Request 12
3.1.2 Modeling of Multiple User Requests 12
3.2 Service Profile and Service List Modeling 12
3.2.1 Modeling of Service Profile 13
3.2.2 Modeling of Service Class 13
3.2.3 Modeling of ASL 14
3.2.4 Modeling of CSL 15
3.3 QoS-Aware Service Composition Modeling 16
3.3.1 Modeling of QoS 16
3.3.2 Modeling of Composition 18
3.4 Time-Constrained Service Composition Problem (TCSC) 19
Chapter 4. Multi-User Service Composition System 22
4.1 MUSCS Architecture and Requirements 22
4.2 User Manager 24
4.3 User Request Controller 26
4.3.1 Modeling of Request Profile 27
4.4 Abstract Service List Database (ASLDB) 28
4.4.1 Abstract Service List Table (ASLT) 28
4.4.2 Readable Function Table (RFT) 29
4.4.3 Function Table (FT) 30
4.5 RSDB (Registered Service Database) 30
4.5.1 Registered Service Table (RST) 30
4.5.2 Service Provider Table (SPT) 31
4.5.3 Registered History Table (RHT) 32
4.6 User Manager 32
4.7 Request Classifier 32
4.8 ASL Composer 33
4.8.1 QoS Decomposition Phase 36
4.8.1.1 Global Constraint (GC) Translation 37
4.8.1.2 Representative Discovery 39
4.8.1.3 NN Service Search 39
4.8.2 Service-Request Matching Phase 41
4.8.2.1 TCIDA (MinCostFlow-Multiple Matching) 43
4.8.2.2 UOIDA 48
4.8.2.3 GMM 51
4.8.3 Computational Complexity of Service-Request Matching Model 56
4.8.3.1 Computational Complexity of TCIDA 56
4.8.3.2 Computational Complexity of UOIDA 57
4.8.3.3 Computational Complexity of GMM 57
4.9 Service Controller 58
4.10 ASL Monitor 58
4.11 Service Classifier 59
4.12 Service Running Environment (Service Provider) 60
Chapter 5. Performance Evaluation 62
5.1 Configuration of Experimental Environments 62
5.2 Experimental Parameters 62
5.3 Experimental Results and Analyses 63
5.3.1 Effect of User Request Number 64
5.3.2 Effect of Service Capacity 67
5.3.3 Effect of Service Number 69
Chapter 6. Conclusion and Future Work 74
6.1 Conclusion 74
6.2 Future Work 75
Reference 76

[ALR09] Alrifai, Mohammad, and Thomas Risse. Combining global optimization with local selection for efficient QoS-aware service composition. Proceedings of the 18th international conference on World wide web. ACM, 2009.
[ALR10] Alrifai, Mohammad, Dimitrios Skoutas, and Thomas Risse. Selecting skyline services for QoS-based web service composition. Proceedings of the 19th international conference on World wide web. ACM, 2010.
[ARD05] Ardagna, Danilo, and Barbara Pernici. Global and local qos guarantee in web service selection. Business process management workshops. Vol. 3812. 2005.
[ARD07] Ardagna, Danilo, and Barbara Pernici. Adaptive service composition in flexible processes. IEEE Transactions on software engineering 33.6 (2007).
[CTA16] Consumer Technology Association, https://www.cta.tech/Emerging-Tech/IoT.aspx, 2016
[GUO11] Kang, Guosheng, et al. Web service selection for resolving conflicting service requests. Web Services (ICWS), 2011 IEEE International Conference on. IEEE, 2011.
[HJA19] Hjaltason, Gísli R., and Hanan Samet. Distance browsing in spatial databases. ACM Transactions on Database Systems (TODS) 24.2 (1999): 265-318.
[JAE16] Cho, Jae-Hyun, Han-Gyu Ko, and In-Young Ko. Adaptive service selection according to the service density in multiple QoS aspects. IEEE Transactions on Services Computing 9.6 (2016): 883-894.
[JOS11] Maestre, Josè Antonio Parejo, et al. On parameter selection and problem instances generation for QoS-aware binding of composite web services using GRASP with Path Relinking. (2011).
[KOS07] Kostas Kontogiannis, Grace A. Lewis, Dennis B. Smith, Marin Litoiu, Hausi Muller, Stefan Schuster, and Eleni Stroulia. The landscape of service-oriented systems: A research perspective. In SDSOA ’07: Proceedings of the International Workshop on Systems Development in SOA Environments, Washington, DC, USA, 2007. IEEE Computer Society.
[LEC09] Lécué, Freddy. Optimizing qos-aware semantic web service composition. International Semantic Web Conference. Springer Berlin Heidelberg, 2009.
[LEC12] Lecue, Freddy, and Nikolay Mehandjiev. Satisfying end user constraints in service composition by applying stochastic search methods. Web Service Composition and New Frameworks in Designing Semantics: Innovations. IGI Global, 2012. 238-260.
[LIA05] Liang, Qianhui Althea, and Stanley YW Su. AND/OR graph and search algorithm for discovering composite web services. International Journal of Web Services Research 2.4 (2005): 48.
[MAY09] Mayer, Wolfgang, Rajesh Thiagarajan, and Markus Stumptner. Service composition as generative constraint satisfaction. Web Services, 2009. ICWS 2009. IEEE International Conference on. IEEE, 2009.
[MOU10] Mouratidis, Kyriakos, Man Lung Yiu, and Nikos Mamoulis. Optimal matching between spatial datasets under capacity constraints. ACM Transactions on Database Systems (TODS) 35.2 (2010): 9.
[PAI07] Paik, Incheon, and Daisuke Maruyama. Automatic web services composition using combining HTN and CSP. Computer and Information Technology, 2007. CIT 2007. 7th IEEE International Conference on. IEEE, 2007.
[PAI14] Paik, Incheon, Wuhui Chen, and Michael N. Huhns. A scalable architecture for automatic service composition., IEEE Transactions on Services Computing, 2014: 82-95.
[PAP07] M. P. Papazoglou, P. Traverso, S. Dustdar, and F. Leymann. Service-oriented computing:State of the art and research challenges. IEEE Computer, 40(11):38–November 2007.
[PEE05] Peer, Joachim. Web service composition as AI planning: a survey. Switzerland: University of St. Gallen, 2005.
[WU12] Wu, Quanwang, Qingsheng Zhu, and Peng Li. A caching mechanism for QoS-aware service composition. Journal of Web Engineering 11.2 (2012): 119-130.
[RAN03] Ran, Shuping. A model for web services discovery with QoS. ACM Sgecom exchanges 4.1 (2003): 1-10.
[ROD11] Rodriguez-Mier, Pablo, Manuel Mucientes, and Manuel Lama. Automatic web service composition with a heuristic-based search algorithm. Web Services (ICWS), 2011 IEEE International Conference on. IEEE, 2011.
[SIR04] Sirin, Evren, et al. HTN planning for web service composition using SHOP2. Web Semantics: Science, Services and Agents on the World Wide Web 1.4 (2004): 377-396.
[SHU14] Deng, Shuiguang, et al. Top-k Automatic Service Composition: A Parallel Method for Large-Scale Service Sets. IEEE Transactions on Automation Science and Engineering 11.3 (2014): 891-905.
[SCI16] Scientific American, https://www.scientificamerican.com, 2016
[SIR05] Sirin, Evren, Bijan Parsia, and James Hendler. Template-based composition of semantic web services. Aaai fall symposium on agents and the semantic web. Vol. 5. AAAI, 2005.
[TAN09] Tan, Wei, Yushun Fan, and MengChu Zhou. A petri net-based method for compatibility analysis and composition of web services in business process execution language. IEEE Transactions on Automation Science and Engineering 6.1 (2009): 94-106.
[TEI11] Teixeira, Thiago, et al. Service oriented middleware for the internet of things: a perspective. Towards a Service-Based Internet (2011): 220-229.
[WAG11] Wagner, Florian, Fuyuki Ishikawa, and Shinichi Honiden. Qos-aware automatic service composition by applying functional clustering. Web Services (ICWS), 2011 IEEE International Conference on. IEEE, 2011.
[WAG12] Wagner, Florian, et al. Towards robust service compositions in the context of functionally diverse services. Proceedings of the 21st international conference on World Wide Web. ACM, 2012.
[WAN06] Wang, Xia, et al. A qos-aware selection model for semantic web services. Service-Oriented Computing–ICSOC 2006 (2006): 390-401.
[WU14] Wu, Quanwang, et al. Broker-based SLA-aware composite service provisioning. Journal of Systems and Software 96 (2014): 194-201.
[WUH15] Chen, Wuhui, Incheon Paik, and Patrick CK Hung. Constructing a global social service network for better quality of web service discovery. IEEE Transactions on Services Computing 8.2 (2015): 284-298.
[WUH15-2] Chen, Wuhui, and Incheon Paik. Toward Better Quality of Service Composition Based on a Global Social Service Network., IEEE Transactions on Parallel and Distributed Systems, 2015: 1466-1476.
[XIO09] Xiong, PengCheng, YuShun Fan, and MengChu Zhou. Web service configuration under multiple quality-of-service attributes. IEEE Transactions on Automation Science and Engineering 6.2 (2009): 311-321.
[YU07] Yu, Tao, Yue Zhang, and Kwei-Jay Lin. Efficient algorithms for Web services selection with end-to-end QoS constraints. ACM Transactions on the Web (TWEB) 1.1 (2007): 6.
[ZEN03] Zeng, Liangzhao, et al. Quality driven web services composition. Proceedings of the 12th international conference on World Wide Web. ACM, 2003.
[ZEN04] Zeng, Liangzhao, et al. QoS-aware middleware for web services composition. IEEE Transactions on software engineering 30.5 (2004): 311-327.