A nonlinear service composition method based on the Skyline operator

doi:10.23919/JSEE.2020.000049

Journal of Systems Engineering and Electronics ›› 2020, Vol. 31 ›› Issue (4): 743-750.doi: 10.23919/JSEE.2020.000049

• Systems Engineering • Previous Articles Next Articles

A nonlinear service composition method based on the Skyline operator

Ying HUO*(), Jie ZHANG()

School of Computer Engineering, Nanjing Institute of Technology, Nanjing 211167, China

Received:2019-04-17 Online:2020-08-25 Published:2020-08-25
Contact: Ying HUO E-mail:huoy@njit.edu.cn;zhangjd@njit.edu.cn
About author:HUO Ying was born in 1988. She received herPh.D. degree from College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics in 2016. Now sheis an associate professor at the School of Computer Engineering, Nanjing Institute of Technology. Her research interests includeservice composition and intelligent computing. E-mail: huoy@njit.edu.cn|ZHANG Jiande was born in 1982. He received his Ph.D. degree in mechanical engineering from Nanjing Tech University. Now, he is an associate professor at the School of Computer Engineering, Nanjing Institute of Technology. His research interests include intelligent optimization algorithm, image measurement and pattern recognition. E-mail: zhangjd@njit.edu.cn
Supported by:
the National Natural Science Foundation for Youth of China(61802174);the Natural Science Foundation for Youth of Jiangsu Province(BK20181016);the Natural Science Foundation of the Jiangsu Higher Education Institutions of China(18KJB520019);the Scientific Research Foundation of Nanjing Institute of Technology of China(CXY201922);This work was supported by the National Natural Science Foundation for Youth of China (61802174), the Natural Science Foundation for Youth of Jiangsu Province (BK20181016), the Natural Science Foundation of the Jiangsu Higher Education Institutions of China (18KJB520019), and the Scientific Research Foundation of Nanjing Institute of Technology of China (CXY201922)

Abstract

Abstract:

The concept of service composition can provide the complex functionality for users. As the widespread application of cloud computing, the number of services grows exponentially. It becomes more difficult to find out the optimal service composition solution quickly. This paper proposes a nonlinear service composition method based on the Skyline operator. The Skyline operator is to find a collection of data that cannot be dominated by others, which is used to prune the redundant services to reduce the search space. Then the service composition problem is formulated as a nonlinear integer programming model by a mathematical programming language (AMPL), and solved by the existing nonlinear solvers Bonmin. The experiments show that the proposed method can effectively improve the efficiency of service composition, while ensuring the quality of solution.

Key words: quality of service, service composition, Skyline service, branch-and-bound Skyline

Ying HUO, Jie ZHANG. A nonlinear service composition method based on the Skyline operator[J]. Journal of Systems Engineering and Electronics, 2020, 31(4): 743-750.

Figures/Tables 10

Fig 1

Fig 2

Table 1

Fig 3

Table 2

Table 3

Table 4

Fig 4

Fig 5

Fig 6

References 25

1	WANG P W, MENG J, CHEN J C, et al. Smart contract-based negotiation for adaptive QoS-aware service composition. IEEE Trans. on Parallel Distributed Systems, 2019, 30 (6): 1403- 1420. doi: 10.1109/TPDS.2018.2885746
2	YE D Y, HE Q, WANG Y C, et al. An agent-based integrated self-evolving service composition approach in networked environments. IEEE Trans. on Services Computing, 2019, 12 (6): 880- 895. doi: 10.1109/TSC.2016.2631598
3	JATOTH C, GANGADHARAN G R, FIORE U, et al. QoS-aware big service composition using MapReduce based evolutionary algorithm with guided mutation. Future Generation Computer Systems, 2018, 86, 1008- 1018. doi: 10.1016/j.future.2017.07.042
4	BORZSONY S, KOSSMANN D, STOCKER K. The Skyline operator. Proc. of the 17th International Conference on Data Engineering, 2001, 421- 430.
5	ALRIFAI M, RISSE T. Combining global optimization with local selection for efficient QoS-aware service composition. Proc. of the 18th International Conference on World Wide Web, 2009, 881- 890.
6	ZENG L Z, BENATALLAH B, NGU A H H, et al. QoS-aware middleware for web services composition. IEEE Trans. on Software Engineering, 2004, 30 (5): 311- 327. doi: 10.1109/TSE.2004.11
7	ARDAGNA D, PERNICI B. Adaptive service composition in flexible processes. IEEE Trans. on Software Engineering, 2007, 33 (4): 369- 384.
8	MISTRY S, BOUGUETTAYA A, DONG H, et al. Metaheuristic optimization for long-term IaaS service composition. IEEE Trans. on Services Computing, 2016, 11 (1): 131- 143.
9	ZHANG A, SUN H Y, TANG Z L, et al. Service composition based on discrete particle swarm optimization in military organization cloud cooperation. Journal of Systems Engineering and Electronics, 2016, 27 (3): 590- 601.
10	YU Q, CHEN L, LI B. Ant colony optimization applied to web service compositions in cloud computing. Computers and Electrical Engineering, 2015, 41, 18- 27. doi: 10.1016/j.compeleceng.2014.12.004
11	HUO Y, ZHUANG Y, GU J J, et al. Discrete gbest-guided artificial bee colony algorithm for cloud service composition. Applied Intelligence, 2015, 42 (4): 661- 678. doi: 10.1007/s10489-014-0617-y
12	HUO Y, ZHUANG Y, GU J J, et al. Elite-guided multi-objective artificial bee colony algorithm. Applied Soft Computing, 2015, 32 (1): 199- 210.
13	PAPADIAS D, TAO Y F, FU G, et al. An optimal and progressive algorithm for skyline queries. Proc. of the ACM SIGMOD International Conference on Management of Data, 2003, 467- 478.
14	ALRIFAI M, SKOUTAS D, RISSE T. Selecting Skyline services for QoS-based web service composition. Proc. of the 19th International Conference on World Wide Web, 2010, 11- 20.
15	YU Q, BOUGUETTAYA A. Computing service Skyline from uncertain qows. IEEE Trans. on Services Computing, 2010, 3 (1): 16- 29. doi: 10.1109/TSC.2010.7
16	WANG S G, SUN Q B, ZOU H, et al. Particle swarm optimization with skyline operator for fast cloud-based web service composition. Mobile Networks and Applications, 2013, 18 (1): 116- 121. doi: 10.1007/s11036-012-0373-3
17	MORADI M, EMADI S. Reducing the calculations of quality-aware web services composition based on parallel Skyline service. International Journal of Advanced Computer Science and Applycations, 2016, 7 (7): 306- 311.
18	ZHANG F, HWANG K, KHAN S U, et al. Skyline discovery and composition of multi-cloud mashup services. IEEE Trans. on Services Computing, 2016, 9 (1): 72- 83. doi: 10.1109/TSC.2015.2449302
19	YAN G, WANG S G, WONG K S, et al. Skyline service selection approach based on QoS prediction. International Journal of Web and Grid Services, 2017, 13 (4): 425- 447. doi: 10.1504/IJWGS.2017.087368
20	DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ. IEEE Trans. on Evolutionary Computation, 2002, 6 (2): 182- 197. doi: 10.1109/4235.996017
21	GUTTMAN A. R-trees: a dynamic index structure for spatial searching. SIGMOD Record, 1984, 14 (2): 47- 57.
22	GAY D M. The AMPL modeling language: an aid to formulating and solving optimization problems. Springer Proceedings in Mathematics & Statistics: Numerical analysis and optimization. Berlin: Springer, 2015, 134: 95-116.
23	AL-MASRI E, MAHMOUD Q H. QoS-based discovery and ranking of web services. Proc. of the 16th International Conference on Computer Communications and Networks, 2007, 529- 534.
24	AL-MASRI E, MAHMOUD Q H. Discovering the best web service. Proc. of the 16th International Conference on World Wide Web, 2007, 1257- 1258.
25	AL-MASRI E, MAHMOUD Q H. Investigating web services on the world wide web. Proc. of the 17th International Conference on World Wide Web, 2008, 795- 8041.

QoS attribute	$\rm Com\_status$	Aggregation
Response time	1	SUM
Availability	2	PRODUCT
Throughput	3	MIN
Price	1	SUM
Reputation	4	AVERAGE

$\dfrac{\| N\_{\rm candidate}\| }{\| N\_{\rm class}\| }$	Bonmin	Local	DGABC	Exhaustive
5	0.13	0.005 8	0.544 5	0.087 2
10	0.46	0.004 9	0.548 9	97.191 8
15	1.34	0.004 8	0.555 9	5 983.208 1
20	1.12	0.004 8	0.562 8	—
25	2.79	0.004 9	0.557 5	—
30	3.96	0.005 0	0.544 2	—
35	7.44	0.005 0	0.555 7	—
40	10.67	0.005 0	0.545 3	—
45	30.1	0.004 8	0.546 7	—
50	21.28	0.004 9	0.560 1	—
55	29.21	0.004 9	0.546 2	—
60	19.04	0.004 9	0.544 0	—

Attribute	Before filtering	After filtering
2	2 507	4
3	2 507	12
4	2 507	12
5	2 507	51
6	2 507	72
7	2 507	163
8	2 507	278
9	2 507	475

Before filtering	After filtering
250	36
500	26
750	28
1 000	35
1 250	31
1 500	33
1 750	46
2 000	46
2 250	49
2 500	51

[1]	Xin ZHOU, Changwen ZHENG. Priority access for QoS support in distributed wireless networks [J]. Journal of Systems Engineering and Electronics, 2019, 30(6): 1202-1211.
[2]	An Zhang, Haiyang Sun, and Yanxia Zhang. Service allocation based on QoS evaluation in military organization cloud cooperation [J]. Journal of Systems Engineering and Electronics, 2016, 27(2): 386-394.
[3]	Meng Qian, Zhong Liu, Jing Wang, Li Yao, and Weiming Zhang. Coordination-theoretic approach to modelling grid service composition process [J]. Journal of Systems Engineering and Electronics, 2010, 21(4): 713-720.
[4]	Qi Xiaogang, Liu Lifang & Liu Sanyang. Algorithm for multi-constrained path selection based on experimental analysis [J]. Journal of Systems Engineering and Electronics, 2006, 17(4): 931-937.
[5]	Yu Chengzhi, Song Hantao , Hou Xianjun & Pan Chengsheng. Dynamic resource management using bandwidth brokers [J]. Journal of Systems Engineering and Electronics, 2006, 17(3): 660-668.
[6]	Yan Tihua & Wang Baoshu. Grid architecture model of network centric warfare [J]. Journal of Systems Engineering and Electronics, 2006, 17(1): 121-125.

A nonlinear service composition method based on the Skyline operator

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 10

References 25

Related Articles 6

Recommended Articles

Metrics

Comments