J. Cent. South Univ. Technol. (2008) 15: 558-563
DOI: 10.1007/s11771-008-0105-9
Trust evolvement method of Web service combination based on network behavior
LIU Ji-bo(刘济波)1, XIANG Zhan-hong(向占宏)2, ZHU Pei-dong(朱培栋)3
(1. School of Computer and Electronic Engineering, Hunan University of Commerce,
Changsha 410205, China;
2. Department of Information Management, Hunan Financial and Economic College,
Changsha 410205, China;
3. School of Computer Science, National University of Defense Technology, Changsha 410073, China)
Abstract: Based on the problem that the service entity only has the partial field of vision in the network environment, a trust evolvement method of the macro self-organization for Web service combination was proposed. In the method, the control rule of the trust degree in the Dempster-Shafer(D-S) rule was utilized based on the entity network interactive behavior, and a proportion trust control rule was put up. The control rule could make the Web service self-adaptively study so as to gradually form a proper trust connection with its cooperative entities and to improve the security performance of the whole system. The experimental results show that the historical successful experience is saved during the service combination alliance, and the method can greatly improve the reliability and success rate of Web service combination.
Key words: network behavior; Web service combination; trust evolvement; Dempster-Shafer rule
1 Introduction
With the development of Web service in the Internet, it has become a hot issue in the theory and industrial domain to create a commonly available organic alliance mechanism what can ensure any service provider to join into the alliance at any time, and offer convenience for users to utilize the resources during dynamic service combination[1-3]. In the inter-organizational service combination model, it is a very important problem how to create a relatively close service alliance in multiple service entities, reduce sightless random alliance, establish efficient and stable creditable alliance structure, and improve the validity of the service combination[4-5].
In the wide area network, lots of Web services are provided in a dynamic attitude and also disappear without notification[6]. The service combination technology is required to form a dynamic alliance relation between services to guarantee efficiency and stability of service combination path during its implementation[7]. However, currently the mechanism is not available for service combination, as a result, the shortage of cooperation causes the abundant Web services in wide area network to form “service islands”[8-9]. Therefore, users feel hard to enjoy proper and good quality services. In order to solve this problem, the network interaction-based service trust alliance organization mechanism was proposed. During the service combination, the mechanism can form the macro self-organization consecutive evolvement and improve the reliability of service combination.
2 Characteristics of Web service interactive behavior
In this work, the social cooperation relation between individuals in real life is reflected. The Web service combination process in the network is featured as follows.
1) Independent cooperative entity: there is no overall control center in the wide area network, and every distributed cooperative entity is formed into independent decision center.
2) Partial field of vision: every cooperative entity owns relatively limited creditable entities whose information is deposited in local areas. Though there are more suitable entities than current creditable entities in the network, due to the limited conditions in communication and cost, the cooperative entities may be unknown to others who could not consider them creditable entities[8].
3) Mutual advantages and feedback: the cooperative entities can cooperate with each other for mutual advantages and the improvement of the trust degree. In reverse, the unsuccessful cooperation will reduce the trust degree after formation of the trust relation, and every cooperative entity can integrate all conditions and recommend the entities with higher trust degree to other entities.
4) Same hierarchical structure in trust circle of combination: in the course of service combination, every cooperator only needs to save parallel information of cooperative entities, direct “upstream and downstream” information and little information of indirect cooperative entities. Through the structural trust alliance, mutual advancement and evolvement, transmission and recommendation, a complex cooperative relation like human society will be formed.
5) Short path phenomena in cooperative relation: though the cooperative relation is complicated, the service combination formed under the advancement and evolvement of trust relation via the cooperative system is of high efficiency. Namely, there exist wide “little worlds” in natural field and human society. Through average six acquainted persons/times transmission, any two persons in the society can be connected. This is so called “six degrees of separation” phenomenon[10], and also called “little world effect”[11].
Accordingly, in this work, a mechanism of effectual service evolvement is proposed based on D-S rule by the interactive behavior of cooperative entities in service combination. A self-owned cooperative trust alliance structure is formed, which promotes the combination to gradually evolve toward an ordering course. The macro scene evolvement course is macro self-organizational one formed by each cooperative entity through independent interaction with partial field of vision.
In addition, the trust system based on network interaction owns unique feature different from the status trust. In real life, it is inadequate to confirm the status of cooperative entities, which is completely different from the creditability of behavior of entities[12]. This point can be proved in real life. For example, two strangers, based on self-owned legal identification, are unable to provide creditable behavior information each other. The mechanism that the behavior trust can dynamically update the trust relation on the basis of direct or indirect behavior experiences between the entities will play a key role in the service combination model[13].
3 Trust evolvement mechanism based on net- work interaction
The D-S rule was applied in the network interaction trust model of service combination. However, since the subjective trust degree is hard to be weighted by certain numbers, it can be weighed by creditable intervals or class probability functions.
3.1 Calculation framework of D-S rule
D-S evidence was proposed by DEMPSTER in 1967. His student, namely SHAFER, developed and processed it into a set of complete mathematical reasoning theory, which could be taken as a generalized expansion to the classic probability reasoning theory in finite domain. Its main features are to support descriptive accuracy at different levels and directly introduce description to the uncertainty[14].
The trust evolvement mechanism based on D-S evidence theory in this work means to confirm the limited system status {θ1, θ2, …, θn} through the observed values (E1, E2, …, Em) of interactive behavior in the network. After the calculation of trust degree between entities, the connection between entities can be established. The connection strength represents trust degree. With the above mechanism, during the interaction of service combination, the connection of service entities will form an ordering self-organizational evolvement scene.
Definition 1 The trust identification framework Θ is defined as an aggregate {T(trust), F(distrust)}, and the power set of Θ (2Θ) is (
,{T}, {F},{T, F}). In this work, the trust identification framework Θ is defined as three kinds: 1) trust identification framework of coordinate services, which represents a set of identification framework of service entities with similar service functions; 2) trust framework of direct cooperative service, which represents the identification framework with “upstream and downstream” relation in the service combination; 3) trust identification framework of indirect service.
With the above definition of trust framework, the following definitions can be drawn.
Definition 2 Basic trust assignment function mAB is defined as a function of power set 2Θ (A and B are cooperative entities), mAB:2Θ→[0, 1], and mAB meets the following relationship:
where mAB({T, F}) means “know nothing to assign the value”, which represents an uncertain degree.
Definition 3 Trust function BelAB is defined as: BelAB:2Θ→[0, 1], besides, BelAB(X)=
It can be deduced as
where BelAB({T}) is the degree that cooperative entity A agrees with cooperative entity B.
Definition 4 Likelihood function PlAB is defined as: PlAB:2Θ→[0, 1], besides, PlAB(X)=1-BelAB(-X)= 
It can be deduced as
PlAB({T})=mAB({T})+mAB({T, F})=1-BelAB({F})
where PlAB({T}) is the degree that cooperative A does not disaffirm with cooperative B.
Definition 5 Interval [BelAB({T}), PlAB({T})] is defined as a creditable area of cooperative A against cooperative B. So the interval 
means the non-denied scope of service entity A against service entity B. Meanwhile it can be expressed by class probability functions. According to Ref.[14], the class probability function with interactive behavior on network is
(1)
Meanwhile, with certain conditions, the class probability function is the actual trust degree as defined in definition 6.
Definition 6 Suppose the trust degree of service entity A against service entity B is:
(2)
where MD(T/E) is the knowledge’s premise and match degree with the evidence E.
Obviously, in the network, all evidences that T requires would appear. If the recommended evidence of some service fails to appear, the related evidence of other services will continue deducing till the recommend evidence appears. The definition of D-S rule shows, here, MD(T/E)=1, hence,
(3)
3.2 Calculation methods of trust degree
During the entity interaction in the network, the evaluation results of direct interaction entities are called direct experience, and the evaluation results offered by a third party are called recommended experience. As for the failure or uncertainty of activities of cooperative entities, the experience is divided into successful experience, failed experience or uncertain experience.
Firstly, the relationship of the trust identification framework Θ is of trusted connection of direct interactive behavior in the network. The following is the calculation method of its creditable intervals.
The self-organizational evolvement mechanism is based on limited relation lists or trust degree, and the service entity A actively recommends applicable relation to relevant interactive entities. The alteration of relation lists and renewal of trust degree may alter the flow directions of combination. With the partial field of vision, every entity independently alters the relation lists and renews the trust degree, which affects the information flow of the whole situation. The information flow promotes every entity to make independent decisions without central nodes; thus advancing and evolving the self-organizational cooperative course.
1) Formulae to calculate the proportional control:
(4)
(5)
(6)
where A, B mean entity A and entity B; 
means successful credit value of A against B at time of t+1; 
means failed value of A against B at time of t+1; 
means invalid interactive credit value or uncertain value of A against B at time of t+1; ρ means coefficient of proportion control, which represents the weighing proportion between historic interactive information and the latest interactive information in the calculation of credit value.
The credit values in some periods can be calculated as follows:
(7)
(8)
(9)
where ZA, B means the total interactive number of A and B; 
means the successful number to be considered by A; 
means the failed number to be considered by A. If ZA, B=0, it means A and B have no interactive behavior, here, the direct credit value of A against B is uncertain. The basic trust assignment function mAB can be weighed by basic trust degree as follows:
(10)
After mAB is calculated, according to definitions 3 and 4, the values of BelAB({T}) and PlAB({T}) can be obtained.
(11)
(12)
As such, the direct trust degree of Web service A against B can be confirmed, namely the creditable interval [BelAB({T}), PlAB({T})].
Its class probability function, based on definition 4, can be obtained:
(13)
3.3 Trust evolvement mechanism based on network behavior
In the previous section, the calculation of trust intervals between direct interactive entities is provided. In real operation, trust relation of lots of Web services is established through medium entities. In the following, the calculation method of transmission and combination of indirect trust relation is provided.
In the course of service combination, through recording, sorting and collecting the experiential value of the target entities provided by recommenders, along with the related selection according to the trust degree of the recommenders, the cooperative entities finally figure out the trust degree of target entities. Here, the trust degree means a creditable interval expressed in definition 4. For example, if the trust degree of a transferred cooperative entity is [0.6, 0.9], it means that the service has a probability of 0.6-0.9 for success.
Meanwhile, the cooperative entity can recommend the collected experiential values for other entities to use. The trust degree recommendation experience is needed to be reduced, which is called indirect trust degree. For example, A has the trust degree evaluation against B concerning some experience information on the targets from R2 to Rn-1, which is indirect trust degree. As indicated in Fig.1, A has no interactive behavior R2 to Rn-1, so it has no direct trust degree. Yet the indirect trust degree from R2 to Rn-1 can be obtained through other medium entities. The premise is that other medium entities will communicate direct trust degree with existing R2, ???, Rn-1. When other entities are used to recommend A and B, the direct trust degree between A and B becomes recommendation trust degree.
As indicated in Fig.1, in the path recommendation of forming experiential recommendation relation, the end of the path is the recommender Rn, who owns direct trust degree against B. The entities on the path of experience recommendation vary in the trust degrees, hence the consent degrees against the recommended information will vary.
Fig.1 Recommended path for experience
Definition 7 Suppose that there exist recom- menders R1, R2, …, Rn-1, Rn between entity A and entity B. The consent degree of R1 against A is S1, that of R1 against R2 is S2, and others go by analogy. The consent degree of Rn-1 against Rn is Sn, where, Si≠0 (i=1, 2, …, n). Then the total consent degree function obtained by A from the recommended trust path is
(14)
Formula (14) represents the transmission or attenuation rule of recommended trust assignment function value, where Si corresponds to mij(X) (i, j mean any two directly interactive cooperative entities, X∈({T}, {F}), recorded as
(15)
The calculation formula of basic trust assignment function value on one recommended trust path is
(16)
The transmitted mAB(X)
is generally reduced, so mAB({T, F}) (mAB({T, F})=1- mAB({T})-mAB({F})) will increase.
When A obtains recommendation information from many experiential recommendation paths, the end point of some experience recommendation paths could be the same recommender. Namely, the recommendation information obtained from different experiential recommendation paths maybe come from the direct experiential value of the same grid service entity, as indicated in Fig.1. There exist experiential recommendation paths between Rn and A. Accordingly, when the experiential values from different recommendation paths are calculated, the following facts should be met[8]. 1) The experiential information will not increase because repeated recommendations, namely the total experiential values from the same end recommendation entity through different recommendation paths will not exceed the direct experiential value of the end recommendation entity; 2) as for the same direct experiential value, the experiential values from different recommendation paths will not be lower than any of single recommendation path. Any experiential recommendation path which meets the above requirements is called independent recommen- dation path. By formulae (15) and (16), after m(X) on each recommendation path is calculated, the improved combination method to combine m(X) on independent paths is adopted to obtain the combined m(X). According to definitions 3-6, the indirect trust degree of A against B can be calculated.
General trust degree can be calculated through the weighted average of direct trust degree and indirect trust degree as follows:
(0≤β≤1)
(17)
where 
means the general trust degree of A against B; 
means the direct trust degree of A against B; and 
means the indirect trust degree of A against B. The higher β is, the higher the success rate on the path to develop service combination is.
Through the above analysis, the service combination trust evolvement mechanism based on network behavior can be concluded as follows.
Step 1 If the Web service is not combined, after some intervals, it will send “ping-pong” protocol to other connected entities or entities in the trust connection relation.
Step 2 After receiving the information, the Web service will return the information of its own and all trust connection relation to the sources.
Step 3 The sources use the trust information and calculate the direct credit value of the relevant entities by formulae (7)-(9). Then, the sources calculate the trust degree intervals through formulae (4)-(6). According to formulae (15)-(17) and definitions 5-7, the indirect trust degree can be calculated.
Step 4 Renew the trust connection relation list according to the above calculation results.
Step 5 For the service combination with the assigned execution entities, renew the trust relation connection according to step 3.
Step 6 As for the request of any service combination, the service entity which receives the request transfers all to the entity with the highest trust relation directly in the “upstream and downstream” trust relation. The same operation will be executed by every entity till the service combination is completed. Meanwhile, the trust connection list will be renewed.
4 Experimental method
4.1 Setting
In order to further expound the significance and function of the trust evolvement mechanism proposed in this work, considering that Web service workflow is an efficient method for service combination, the original system SWES for the Web service combination management established by the topic group was used to perform the verification[15]. The SWES system is made up of five modules: system access module, SRS registration control module, WSSP generation module, path negotiation module and executive environment module.
4.2 Experimental results and analysis
When the calculation starts, all nodes in the network have only physical connection relation, namely have not any trust connection relation, and the service combination needs special indication of executive paths. During the operation of the calculation, the trust connection relation is gradually established, and the relationship between entities is not mainly physical connection but interaction in the trust connection relation. Here, there exist physical connection relation and trust connection relation in the network, and the latter is the main part. If there is no assigned combination path, with the progress of evolvement, the success rate of executive combination increases gradually. As indicated in Fig.2, the higher the proportion adjustment coefficient(ρ) is, the higher the proportion of historic interaction in the trust degree is, and the more stable the success rate will keep. In reverse, the higher the latest historic interaction is, the higher the fluctuation is.
Fig.2 Comparison of success rate of executive combination with time
In actual network, not all cooperative entities possess the cooperation declared. Maybe, some are “private” low quality entities, which are hard to be distingushed in the system based on the status, and can be identified in the self-organizational evolvement based on behavior characteristics. Fig.3 shows that, with the existing low quality cooperative entities, the combination evolvement mechanism based on D-S rule model acheives better effect than that based on trust relation declared. Because the historical successful experience is saved during the service combination alliance, the cooperative entities may form favorable trust relation, remove the low quality entities, and improve the success rate of service combination.
Fig.3 Comparison of success rate with 10% low quality entities
Fig.4 shows that with the increase of vicious service nodes in the network，the decrease degree of general methods is much larger than that of the trust evolvement mechanism, although the both success rates decrease. Besides, the calculation of trust evolvement will not reduce the success rate with increasing vicious nodes, and slowly keep at some levels, which is the same as the situation relfected in Fig.4. This means that the trust evolvement process can remember the successful paths and select the successful paths in the collected paths.
Fig.4 Influence of vicious nodes on success rate
5 Conclusions
1) The characteristic of Web services interactive behavior for self-organizational advancement and evolvement is presented. The behavior will form close combination trust connection relation, and enable service entities to develop toward the ordering evolvement course.
2) The trust evolvement method of the macro self- organization for Web service combination is proposed based on the entity network interactive behavior, and the control rule of the trust degree in the D-S evidence theory was utilized in the method.
3) The trust relation based on Web services interactive behavior possesses the advantages that are different from the identification verification, which ensures that the method proposed in this work is of better performance than that proposed in the past.
References
[1] CHEN Zhang, CHEN Zhi-gang, DENG Xiao-heng, CHEN Li-xin. An effective assemble-oriented framework for grid Web service [J]. Journal of Central South University of Technology, 2007, 14(4): 557-562.
[2] RAN S P. A model for Web services discovery with QoS [J]. ACM SIGecom Exchanges, 2003, 4(1): 1-10.
[3] SONG S, HWANG K, KWORK Y K. Trusted grid computing with security binding and trust integration [J]. Journal of Grid Computing, 2005, 3(1): 53-73.
[4] LUO Hai-bin, FAN Yu-shun, WU Cheng. Overview of combination technology [J]. Journal of Software, 2000, 11(7): 899-907. (in Chinese)
[5] SHETH A, RUSINKIEWICZ M. On transactional combinations [J]. IEEE Data Engineering Bulletin, Special Issue on Combination Systems, 1993, 16(2): 34-40.
[6] CURBERA F, KHALAF R, MUKHI N. The next step in Web services [J]. Communications of ACM, 2003, 46(10): 29-34.
[7] HU Chun-hua, WU Min, LIU Guo-ping. Research on novel macro grid workflow self-organization mechanism [J]. Computer Engineering, 2007, 33(1): 25-27. (in Chinese)
[8] JIN Hai, LIAO Zhen-song, ZOU De-qing, QIANG Wei-zhong. A new approach to hide policy for automated trust negotiation [C]// Proceedings of the 1st International Workshop on Security. Berlin: Springer-Verlag, 2006: 168-178.
[9] SRIVATSA M, XIONG L, LIU L. Trust guard: Countering vulner-abilities in reputation management for decentralized overlay networks [C]// Proceedings of the 14th World Wide Web Conference. New York: IEEE Computer Society, 2005: 422-431.
[10] WATTS D J, STROGATZ S H. Collective dynamics of small world networks [J]. Nature, 1998, 393(4): 440-442.
[11] KLEINBERG J. The small world phenomenon: An algorithmic perspective [C]// Proceedings of the ACM Symp on Theory of Computing. New York: Communications of ACM, 2000: 163-170.
[12] WANG Yuan, LU Jian, XU Feng, ZHANG Lin. A trust measurement and evolution model for Internetware [J]. Journal of Software, 2006, 17(4): 682-690. (in Chinese)
[13] AZZEDIN F, MAHESWARAN M. Integrating trust into grid resource management systems [C]// Proceedings of the 2002 International Conference on Parallel Processing. New York: IEEE Computer Society, 2002: 47-54.
[14] SHAFER G. A mathematical theory evidence [M]. Princeton, New Jersey: Princeton University Press, 1976.
[15] HU Chun-hua, WU Min, XIE Qing, WANG Jian-ming. SWET: Service combination transfer performance evaluation system based on QoS [J]. Journal of Central South University: Natural Science, 2007, 38(5): 962-969. (in Chinese)
Foundation item: Project(60673169) supported by the National Natural Science Foundation of China
Received date: 2008-02-28; Accepted date: 2008-04-30
Corresponding author: LIU Ji-bo, Associate professor; Tel: +86-731-8688271; E-mail: n_ljb@126.com
(Edited by CHEN Wei-ping)
