Service composition for generic service graphs
Service composition for generic service graphs
复制标题
DOI：
10.1007/s00530-006-0026-0
复制
发表时间：
2006-06
影响因子：
3.9
通讯作者：
Jin Liang;K. Nahrstedt
中科院分区：
文献类型：
--
作者：
Jin Liang;K. Nahrstedt
服务组合是一种很有前途的多媒体服务供应方法，因为它能够动态地生成新的多媒体内容，并为各个客户机设备定制内容。以前的研究工作涉及服务组合的各个方面，如可组合性、qos感知和负载平衡。然而，大多数工作都集中在这样的应用程序上，其中来自单个源的数据流由中间服务处理，然后交付到单个目的地。在本文中，我们讨论了可以建模为有向无环图（dag）的多媒体服务的服务组合问题。我们正式定义了这个问题并证明了它的NP困难。我们还设计了一个启发式算法来解决这个问题。仿真结果表明，该算法在寻找低成本的组合解方面是有效的，并且可以权衡计算开销以获得更好的结果。与服务组合的逐跳方法相比，即使逐跳方法使用穷举搜索，我们的算法也能找到成本低10%的组合解决方案。
Service composition is a promising approach to multimedia service provisioning, due to its ability to dynamically produce new multimedia content, and to customize the content for individual client devices. Previous research work has addressed various aspects of service composition such as composibility, QoS-awareness, and load balancing. However, most of the work has focused on applications where data flow from a single source is processed by intermediate services and then delivered to a single destination. In this paper, we address the service composition problem for multimedia services that can be modeled as directed acyclic graphs (DAGs). We formally define the problem and prove its NP hardness. We also design a heuristic algorithm to solve the problem. Our simulation results show that the algorithm is effective at finding low-cost composition solutions, and can trade off computation overhead for better results. When compared with a hop-by-hop approach for service composition, our algorithm can find composition solutions that aress 10% smaller in cost, even when the hop-by-hop approach uses exhaustive searches.