Service-Oriented Multi-Agent Systems are dynamic systems populated by heterogeneous agents. These agents model their functionality as services in order to allow heterogeneous agents or other entities to interact in a standardized way. Furthermore, due to the large-scale and the adaptive needs of the system, the traditional directory facilitators or middle-agents are not suitable for the management of the agents services. In this paper we present a distributed system where there is no a ce. The proposal provides a fully decentralized structure and allows agents to locate services using only local information. The system is enhanced using semantic information in the generation of the system structure and also in the search process.
Service-Oriented Multi-Agent Systems (SOMAS) can be described as open and dynamic systems, where agents provide basic functionality through services and new agents can enter to the system and existing ones leave. An important issue that has raised great interest in the research community in the latest years is service discovery. In open systems where there is a large number of agents and the available agents change dynamically, finding the appropriate agent which offers the service required is not an easy task. Conventional approaches to locate agents with certain functionality in SOMAS, such as registries or middle-agents, are centralized approaches which are not always appropriated for large-scale and highly dynamic environments. These proposals present some weakness such as bottlenecks, complexity or the huge amount of memory needed to keep all the information about the agent’s functionality when the system scales. Distributed approaches, such as agent coalitions or federations of registries, have been proposed to solve some of these problems but the required coordination effort to create the coalitions and to maintain data consistency between distributed registries makes these proposals not suitable for highly dynamic environments.
An alternative for traditional proposals is the use of social networks[
As a result of that, several models based on mathematical functions have been proposed to simulate the structure in real social networks. These models try to reflect how social links are established between individuals to form a network which can guide the search. These networks such as small-world or preferential attachment network, are called navigable social networks and it can be ensured that short paths between two random individuals can be found using only local information. How an effective search is carried on only with local information is the other important aspect. Which criteria should be follow by the individuals in order to guide the search towards the target? This depends on the structure of the network. There are some strategies that have better results depending of the underlying structure where it is applied. For instance in small-world networks similarity or geographical distance can be considered a good parameters to consider while strategies guided by degree are not so suitable.
In this work, we propose the use of a social network model as the underlying
structure of a service discovery system for agents. The structure relies on a social feature
present in many social networks called homophily[
Open and dynamic environments where the scalability and the workload are low make
use of middleagents to facilitate service discovery [
The proposal that we present here tries to overcome drawbacks of current discovery approaches in open SOMAS through a completely distributed approach, considering semantic information about organizational roles and services. This approach is based on social networks as underlying structure. The advantages and contributions of this proposal compared to others are: – System which integrates services and agents. Agents have social and proactive capabilities which provide more flexibility and adaptability to the system. Services facilitate the reusability and interoperability. Here, agents functionality is described in terms of services, therefore we obtain the advantages of both technologies. – System structure that guarantees, in general, that a service if it exits is going to be found in a bounded number of steps. – Service discovery strategy that only needs local information to navigate the network in order to reach the required service. – The use of semantic information to create the system structure and to lead the service search.
– Inclusion of organizational information in the service discovery process. DEFINITION 1 (Agent-Service Discovery System). An SDS is defined as SDS = (A, L), where A is the set of agents that are part of the SDS (nodes): A= fa1,...,ang, and each edge `=(ai, aj )2L indicates the existence of a knowledge or communication relationship between agent ai and aj in the system (undirected links).
Agents are social entities which have local knowledge about its immediate neighbors, including their identity, degree, organizational information and the semantic description of the services they offer, but it is unaware of the rest of the agents present in the system.
DEFINITION 2 (Agent). An agent ai=(R,N ) jai 2 A is a social entity which can play several roles in different organizational units R=fr1,. . . ,rng:jRj > 0, has a neighborhood N =fak,...,angj ak 2 N , 9 (ai,ak)2L, jN j > 0.
The agent role determines the kind of services an agent offers. The role provides an abstract layer over the services that the agent offers and it is used to create the structure of the system. Roles are defined inside an organization unit ou. The organization unit establishes a set of policies responsible of the structure of the system. These policies are related to basic system operations (join, leave, discover. . . ). DEFINITION 3 (Role). A role in our system is defined as r = ( ,S,ou) 2 R where is a semantic concept for the role, ou is the organization where the agent plays the role r and S=fs1,. . . sng is the set of services offered by the agent.
Each service si is a semantic service defined by the tuple: si = (I,O), where I denotes the set of inputs and O denotes the set of outputs. The I and O of the service are semantic concepts defined in a common ontology. To simplify the system, we are going to consider that each agent plays one role and offers one service.
The agent-service discovery system that we present relies on a property present in
many real social networks: homophily. This word expresses the idea that similar people
tend to interact and establish links with higher probability than dissimilar people. There
are two types of homophily[
In this work we focus on choice homophily and its two forms. In general, homophily
has demonstrated that is one of the most pronounced features in social networks[
DEFINITION 4 (Agent homophily). In our SDS the homophily between two agents is based on the status homophily and the value homophily: – value homophily (Hv(Si,Sj )) is defined over the agent’s services and it is considered as the semantic similarity between the services offered by the agents. – status homophily (Hs(ri,rj )) is defined over the agent’s role and it is considered as the semantic similarity between the roles played by the agents Therefore, the homophily between two agents is defined as the linear combination of value and status homophily:
Hs(ri; rj ) = role match(ri: ; rj : )
H =
Hv + (1 )
Hs
We are going to describe with more detail how are calculated each kind of homophily. The homophily function Hs(ri,rj ), means the degree of match dom (exact, subsumes, plug-in, fail) between the semantic concept of the roles played by the agents. (1) (2) where role match is the function which calculates the semantic similarity between ri: i and rj : j . The homophily function Hv(ri.S,rj .S), means the degree of match between the services offered by the agents. I = [ s:I; O =
[ s:O
8s2r:S match(Ii; Ij ) = max(WG0=(Ii[Ij;E0)) where function match solves a bipartite matching problem between semantic services. In our case we have two bipartite graphs, one where the vertexes are the inputs of the services and the other where the vertexes are the outputs. In the case of matching between the inputs of the services (the process is the same for the outputs), the bipartite graph G=(Ii[Ij , E) has a set of vertexes with Ii inputs and the other set with Ij inputs. Given a bipartite graph for the service inputs, G=(Ii[Ij ,E), its matching G0=(Ii[Ij ,E0) E0 E is a graph where all the vertexes of one set are connected with the other set of vertexes only with one edge. In this graph, we allow that edges share a vertex to give more flexibility to the matching. The sum of weights (WG0 ) of the edges in the matching is maximized:
WG0=(Ii[Ij;E0) =
X
!k 8ek2E0 max(jIij; jIj j) (3) (4) (5) (6) 4 4.1
The process that an agent should follow to get into the SDS is as following (see Alg. 1):
the agent ai tries to establish a set of connections with other agents already present in
the system. The number of connections that the agent is going to establish is generated
by a random function which follows an exponential distribution. The idea is to generate
a system with an exponential degree distribution to achieve the structure of a
preferential attachment network[
Once the agent knows the number of connections, it should decide which agents are going to be its neighbors. The probability of an agent ai to establish a connection with agent aj is directly proportional to the homophily degree between the agents, if the agents are more similar, they have more probability to be connected. This condition allows a new agent not only to establish ’short connections’ between agents with similar roles and semantic services, but also between agents that are not similar (’long connections’). The idea of ’long connections’ is to create short paths between groups of agents that do not offer similar services and reduce the number of hops needed to discover services. The probability to establish a connection between two agents in the system is based on the homophily degree between them H(ai,aj ).
Algorithm 1 Join, where a is the new agent and SD the system function Join(a, SD) connections ExpRandom( ) connected F alse dg 0 while :connected ^ dg connections do ar random(SD) if H(a; ar) UniRandom(0,1) then `(a,ar) a:dg a:dg+1 updateNeighbors(a; ar) connected T rue end if end while end function 4.2
When an agent leave the system could be for three reasons: the agent decide voluntary to leave the system, failure or ’sabotage’. Periodically an agent sends a keep alive message to its neighbors. The agent will notice that one of its links is broken whether after sending a message, the time to receive an answer from the neighbor expires. In that case, the agent deletes the neighbor from its neighbor list and establishes a new link with other agent in the network to keep their degree (see Alg. 2 and Alg. 3). Algorithm 2 Leave, where a is the agent and SD the system function Leave(a, SD) local for ai 2 a.N do removeLink(a, ai) newLink(ai,SD) end for end function 4.3
DEFINITION 5 (Service discovery problem) Given a set of agents A situated in a SDS= (A,L), the service discovery problem is defined as a probabilistic decision-making task in which an agent ai2 A is looking for an agent aj 2 A, which offers the required service st. Algorithm 3 newLink, where a is the agent and SD the system function Link(a, SD) connected F alse while :connected do ar random(SD) if sim(a; ar) UniRandom(0; 1) then `(a,ar) ar:dg ar:dg+1 updateNeighbors(a; ar) connected T rue end if end while end function
The search process in the system is based only on the agent local knowledge. When
the agent ai is looking for an agent aj which offers the required service st, ai selects
which of its neighbors is the most appropriated to redirect the query instead of broadcast
the query to all the neighborhood. In many networks which reflects power-law
characteristics, the search is suggested to be based on degree. However, this makes that highly
connected nodes could be overloaded with requests. Our selection criteria is based on
previous proposals presented in [
The test can be divided in two groups. The first group compares the performance of typical distributed search strategies (degree, similarity, random) to the proposal presented in this paper. The second test evaluates the fault tolerance of the SDS when relationships between agents in the system are broken randomly (an agent leaves the system) or following some patterns (which corresponds to deliberate failures ’sabotage’). 5.1
The experiments have been done in a set of networks that simulate the SDS structure. These networks are preferential attachment networks and have generated as the result of the join operation of agents. We have implemented two kind of networks: A where the agents have not roles and Network B where each agent plays a role. We consider 10 types of different roles. Each network is composed of 1000 agents with one semantic service each one. The services and roles have been assigned to the agents using a uniform distribution. 5.2
In this section we evaluate the search operation in our SDS. Due to the similarities of our system and p2p systems, we compared the search operation to other typical search strategies used in p2p systems: random, degree, similarity, similarity and degree. We have analysed the behavior of each strategy in 5000 searches in networks A and B.
In figures 1a and 1b, the results obtained after the service search process are presented. We see that in general the strategies in a network with organizational information have a better performance than the same strategies in a network without this information. That shows that organizational information in the system can guide the search process better than the systems that only provide information related to the degree and services. Between all the strategies, the search operation that we present in this paper has a better performance than the others. This is because it considers, apart form the degree and semantic service information, the roles that agents play. This information reduces the set of possible agents suitable to offer the service.
An important parameter to consider in SDS is the number of steps to reach the target agent. Figure 2a shows the mean path length obtained with each strategy in networks with role information (B). In general, all the strategies return paths with more steps as the number of agents in the network grows. When the size of the network is over 700 agents, the path length does not increase significantly. This shows that the structure of the SDS is suitable for large-scale systems.
In Figure 2b the success rate of each search strategy in SDS is depicted. An obvious result is that as the system scale increases, the percentage successful searches decreases. The search operation presented here is the algorithm less influenced by the number of agents in the system. In general, the search operation in the 80% of searches finds a path between the source agent to the target agent. 5.3
The last and very important check is the behavior of the SDS under failures. The problem appears when a broken link splits the system into two isolated parts, since some SSeeaarrcchhooppeerEartaEiotiVnonN ESVimNilarity&DeEegggrVrerNeee Degree Similarrieittyey-Based SDimeilga SSDimiemgirillaeaerriittyy-Based Random-Based 0 0 cssccseueuaehSS r lf % 100 90 80 70 60 50 40 30 15 0 40 50 60 Path Length When Successful (b) 500 n agents (b)
SearcShearochpoepEerEratVioionNn SimilSaimriiltayrit-yBbased
Degree DeDgergere-eb-aBsaesded RRaannddRoaomnmdom-Based Search opeEraEtioVnN Similarity&DEegVreNe Degree-Based Similarity-Based Random-Based 10 20 30
40 50 60 Path Length When Successful agents will no longer be reachable. To analyse it, agent failures have been modelled as a failure of all its connexions. When some links are broken, an alternative path has to be found. For random failures (see Fig.3a and Fig.3b), it can be observed that when the number of deleted agents is from 10% to 30%, the path length increases, due to there are alternative paths (with more steps) to find the agent with the required service. When the number of deleted agents ranges from 30% to 50%, the network is divided in several isolated parts. Only the searches inside the isle will success, so the number of successful searches decreases and the path length decreases because the isle diameter are smaller.
42 40 38 th 36 g n e L tah 34 naP eM 32 30 28 2610
Search opeErEatVioNn Similarity&DegErVeeN Degree-Based Similarity-Based Random-Based Search opeErEaVtioNn Similarity&DegErVeeN
Degree-Based Similarity-Based
Random-Based 70 60 50
An interesting case is what happens when a deliberate failure is provoked. In the case of systems that follow a power-law, the worst case occurs when agents with highest degree (hubs) are disconnected. Figure 4a and 4b shows how ’sabotage’ affects the performance of the search process. In this case, the path length increases due to only a few highly connected hubs have been deleted and an alternative path exists. The performance attending the number of successful searches decreases considerably as the number of deleted hub increases. 6
The aim of this work is to provide an alternative to traditional approaches that deal with the service discovery task in large-scale open SOMAS. Our proposal tries to overcome drawbacks present in other centralized (bottlenecks, complexity, huge amount of memory needed, global knowledge) and distributed (network traffic, congestion, coordination effort, data consistency between distributed registries, update data) discovery approaches. We consider that structures used in social networks facilitate the task of locating agent services in a few steps using only local information. For that reason we investigate the use of social networks as underlying structure of a service discovery system. This structure is based on the concept of similarity between individuals, considering organization role and services, and uses semantics to calculate this similarity. Furthermore, we provide several operations for the agents to be part of the system. An evaluation of the search functionality compared to other traditional p2p strategies is also 80 70 provided. The behavior of the system under failure and ’sabotage’ circumstances have been also evaluated. The results of the experiments show that the system is robust under failure and that the search functionality performs well.
This work is supported by TIN2009-13839-C03-01 and TIN2008-04446 projects, CONSOLIDER-INGENIO 2010 under grant CSD2007-00022, FPU grant AP-200800601 awarded to E. del Val.