Introduction

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 [25] [28]. Human beings create social structures in a decentralized way which allows to locate other individual in a few steps considering only local information. This fact was observed by Milgram in the well known experiment of 'six degrees of separation' [24]. The results of this experiment arose two questions: how is the structure of these social networks and how an effective search of individuals is carried on only with local information. In the wake of this experiment, several works started to pay attention on the analysis of the underlying structures in human societies and the properties of these structures.

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 [15]. Homophily expresses the idea that similar people interact with higher frequency than dissimilar people. Therefore, in our system agents with similar roles and services have more probability to be linked. The system 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.

Related Work

Open and dynamic environments where the scalability and the workload are low make use of middleagents to facilitate service discovery [14][22] [23]. The matchmakers could provide an optimal matching due to they consider all the registered services in the system. Unfortunately, this kind of agents could be a bottleneck when the workload increases. Other drawbacks are their complexity, the huge amount of memory needed to keep service advertisements and the cost of service composition as the number of services grows significantly. Different approaches have been suggested to overcome the above mentioned problems. Peer-to-peer approaches [12][2] [20][31] broadcast a query using local knowledge The drawback of this approach to service discovery is that the communication among agents is essential and the overall communication traffic overhead may be large. Another distributed way to locate distributed services is to form coalitions or clusters [19][18] [16]. Nevertheless, the choice of what coalitions are going to be formed is a difficult task. This entails recursively to calculate the values of the coalitions and later selecting the coalition with the best result. A third way for agents to discover services in efficiently is the distribution of the middleagents or facilitators [21] [17] [13]. These proposals suggest to split the function of the service facilitator among a group of agents. The system designer assigns a local matchmaker to each host or segment of the system, which provides matchmaking services to agents in its vicinity (its segment). In systems with very large segments the problems of scalability are only marginally relieved by this approach because the large segments become overloaded systems which have local bottlenecks. Another case in which this approach is not useful is in systems with many cross-links between segments. In this case the overhead of coordinating tasks among local matchmakers might be greater than the benefit obtained from their distribution.

Proposed System and Definitions

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= {a 1 ,...,a n }, and each edge =(a i , a j )∈L indicates the existence of a knowledge or communication relationship between agent a i and a j 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

a i =(R,N ) |a i ∈ A is a social entity which can play several roles in different organizational units R={r 1 ,. . . ,r n }:|R| > 0, has a neighbor- hood N ={a k ,...,a n }| a k ∈ N , ∃ (a i ,a k )∈L, |N | > 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) ∈ R where φ is a semantic concept for the role, ou is the organization where the agent plays the role r and S={s 1 ,. . . s n } is the set of services offered by the agent.

Each service s i is a semantic service defined by the tuple: s i = (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 [15]:

choice homophily, where patterns of interaction are driven by preferences for similarity. This kind of homophily has two forms: status homophily, where the individuals are considered similiar if they share a cultural background, and value homophily, where individuals are considered similar on the basis of shared values, attitudes, and believes. induced homophily, emerges not from individual choice, but from influence dynamics that make individuals more similar over time [29].

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 [3][27].

Due to the efficiency of the social networks with this feature, we consider important to consider this property in our system.

DEFINITION 4 (Agent homophily). In our SDS the homophily between two agents is based on the status homophily and the value homophily:

value homophily (H v (S i ,S j )) is defined over the agent's services and it is considered as the semantic similarity between the services offered by the agents. status homophily (H s (r i ,r j )) 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:

H = α * H v + (1 − α) * H s(1)

We are going to describe with more detail how are calculated each kind of homophily. The homophily function H s (r i ,r j ), means the degree of match dom (exact, subsumes, plug-in, fail) between the semantic concept of the roles played by the agents.

H s (r i , r j ) = role match(r i .φ, r j .φ)(2)

where role match is the function which calculates the semantic similarity between r i .φ i and r j .φ j . The homophily function H v (r i .S,r j .S), means the degree of match between the services offered by the agents.

H v (r i .S, r j .S) = β * match(I i , I j ) + (1 − β) * match(O i , O j )(3)I = ∀s∈r.S s.I, O = ∀s∈r.S s.O(4)match(I i , I j ) = max(W G =(Ii∪Ij ,E ) )(5)

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=(I i ∪I j , E) has a set of vertexes with I i inputs and the other set with I j inputs. Given a bipartite graph for the service inputs, G=(I i ∪I j ,E), its matching G =(I i ∪I j ,E ) E ⊆ 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 (W G ) of the edges in the matching is maximized:

W G =(Ii∪Ij ,E ) = ∀e k ∈E ω k max(|I i |, |I j |)(6)

4 System Operations

Join

The process that an agent should follow to get into the SDS is as following (see Alg. 1): the agent a i 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 [1]. A preferential attachment network it is characterized by a degree distribution which follows a power-law degree distribution, p(dg) ∝ dg λ , where p(dg) indicates the probability to be connected to a node with degree dg. This means that there are some nodes have a high degree and the majority has a low degree. This structure ensures that the diameter of the network is ln |A|, where |A| is the number of agents in the SDS and in some situations, when 2<λ<3, is lnln |A| [11]. This model is present in many 'online communities' such as WWW, electronic mail or citation graphs [26]. These networks are the result of a growth process in which new nodes that join the system prefer to be connected to well connected nodes.

Once the agent knows the number of connections, it should decide which agents are going to be its neighbors. The probability of an agent a i to establish a connection with agent a j 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(a i ,a j ).

Leave

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 ∈ a.N do removeLink(a, ai) newLink(ai,SD) end for end function

Search

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 a i ∈ A is looking for an agent a j ∈ A, which offers the required service s t .

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) ≥ U niRandom(0, 1) then (a,ar) ar.dg←ar.dg+1 updateN eighbors(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 a i is looking for an agent a j which offers the required service s t , a i 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 [27] [30], where the selection of the most promising neighbor is based on two criteria: degree and the similarity. In our sytem the selection criteria is based on the agent degree and the semantic similarity between agents services and roles. Until the target agent a j is found, all future agents involve in the discovery process will make their decision similarly (see Alg. 4).

Algorithm 4

Search where as is the source agent, st is the required service and S the system and Θ is the similarity threshold function Search(as, st, S, Θ) s←getService(Ags) a←as steps←0 while sim(s, st) ≥ Θ ∧ steps≤T T L do pmax←0 for ai ∈ a.N do dg ← a.dg s ← a.s p ← P (H(a, ai),dg) if p > pmax then pmax ← p a ← ai end if end for end while return a end function

Simulation Results

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').

System Characterization

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.

Performance

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.

Fault Tolerance

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 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. 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.

Conclusions

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 to be part of the system. An evaluation of the search functionality compared to other traditional p2p strategies is also provided. The behavior of the system under failure and 'sabotage' circumstances have been also evaluated. results of the experiments show that the system is robust under failure and that the search functionality performs well.