Abstract
Previous research studied a problem of data collection in complex networks with failure-prone components using mobile agents and two movement strategies: random and a pheromone-based algorithm. As a main conclusion, a fast data collection implies higher robustness and success rates. In some scale-free networks with a higher standard deviation in the betweenness centrality, random exploration was faster than a pheromone-based algorithm because mobile agents remain re-exploring nodes for more time. This paper presents an improvement to selected movement algorithms to collect data in complex networks in a faster way. The proposed improvement consists of local marks in nodes to avoid re-exploration combined with the previously proposed algorithms. Experiments were performed with different failures rates. Results show that there is a significant difference between the pheromone algorithm with and without local marks providing a higher robustness in data collection tasks in scenarios with a higher standard deviation in the betweenness centrality. Possible applications include data-collection and retrieval in distributed environments like Internet of Things environments (IoT) as well as farms, clusters and clouds.
Introduction
Nowadays, most computing applications rely on distributed systems, from cloud-based systems, such as Google, Amazon, Facebook and Apple, to cyber-physical systems, such as smart cities, building, electric grids and cars. For example, Facebook looks to the end user like a single application. However, in the background, many independent components communicate and cooperate via a network to offer the services of messages and inbox, friends, newsfeeds, likes and reactions, comments, etc [9]. The ability to hide different processes and resources interacting is known as transparency [22]. This feature is hard to obtain because each component acts locally, there is no shared memory, each component only knows local past states of others while performing computations, and individual components can fail [14].
Information and Communication Technology (ICT) organisations invest significant resources in the prevention and recovery of distributed systems from failures [11]. Corporative access to services requires availability rates of 99.999% and downtime costs are in the order of thousands of dollars per minute [8]. Data collection and replication is an essential task in these environments because it provides robustness in case of failures in resources. Some areas of application are secure communications [7], log machine replication in databases [1, 12] and information processing in sensor networks (computing averages of local observations) [13].
Previous research [16] studied robustness and performance of failure-prone mobile agents collecting and synchronising data from complex networks. Specifically, this work modelled different types of network topologies, both traditional (line, circle, lattice, Hub & Spoke, Forest Hub & Spoke) and complex (Small-world, Community and Scale-free) with several parameters. A random exploration and an adaptation of pheromone model proposed in [15] to enable mobile agents to explore and collect data from nodes across various targeted networks.
Experimental results of [16] show that a pheromone-based exploration technique may result in a faster data collection for most experiments in different topologies and, in consequence, in a more robust exploration. Additionally, by observing some network parameters, a possible relation was found between the network topology and the data-collection performance given by the speed of data collection in rounds and the standard deviation of the betweenness centrality. A higher deviation indicates a higher data collection time. Experimental results also revealed that a random exploration algorithm performed better in certain network topologies (e.g. Forest hub and spoke or a selected scale-free network).
As in [16], this work aims to profile the suitability of the proposed exploration approaches with respect to various network topologies and to various failure rates. In this work, we select the most challenging topologies in [16] and add a modification in the exploration algorithm to mark visited nodes. Experimental results show that data collection in complex networks can be improved in scenarios where a random algorithm performed better than the pheromone approach.
The remainder of this paper is organised as follows: Section 2 introduces the data collection problem; Section 3 presents the methodology including selected complex networks, agent capabilities and the nodes marking proposal; Section 4 presents experimental results and some statistical analysis; finally some conclusions are drawn.
Data collection problem
In this paper, the data collection problem described in [16] is addressed. The problem consists in to achieve that at least one agent explores a given complex network given a failure probability p f . To achieve this, a collection of mobile agents is defined to explore a determined complex network using a determined motion algorithm. Each agent collects data from each node and shares its local information when finding others. They start from different locations and move between interconnected nodes.
Each mobile agent has an agent program defined in Algorithm 1 [18]. This program defines computation via discrete rounds and a corresponding internal round number counter. In each round, an agent can fail if a pseudo-random number λ is lesser than a failure probability p f ∈ [0, 1] (lines 6 to 8). An agent senses its current location obtaining data from it (line 11), then it determines its next location using a determined motion algorithm. If an agent has neighbours in the same node, it exchanges its local information with them (line 12). An experiment stops and it is considered successful if one agent collects all data from a selected complex network. If all agents fail, the simulation stops in failure.
Methodology
Methodology in this work initially consists in the selection of complex networks that are challenging for data collection. As shown in [16], a random exploration strategy is faster and more robust for a scale-free and a forest hub & spoke networks while a pheromone-based approach is faster in small-world and community networks.
The second part is the definition of mobile agents including aspects like failure definition to evaluate the robustness of the data collection task and additional perceptions and actions to mark the environment as an additional step to the random and pheromone-based algorithm proposed in [16]. Finally, the motion algorithms are described with the marking approach.
Selection of complex networks
Based on the results in [16], four types of networks were selected for experiments: small-world, community, scale-free and forest hub & spoke.
The Internet graph corresponds to a small-world network [23]. A small-world network is characterised by maintaining relative small distances between any pair of nodes [10]. The selected small-world network in experiments is defined using the Watts-Strogatz model (Fig 1-a) [24]. A lattice network with 100 nodes is rewired with a probability β = 0.5 and degree k = 4. k defines the local degree of each node, and β is the probability of rewiring a link.
Complex Networks selected for Experiments.
Collaboration networks and social networks correspond to community networks [6]. Community networks groups nodes in clusters. Each cluster is high connected internally (in this paper is wired as a small-world) and there are few links among nodes that belong to different clusters. In this paper the number of clusters is n clusters = 4, and each cluster is a small-world with 25 nodes being k = 4 and β = 0.5. Pairs of nodes from different clusters are selected randomly to connect different clusters (Fig 1-b).
A scale-free network is a network that follows a preferential attachment rule following a power law distribution in the local degree of its nodes (Fig 1-c) [23]. The scale-free network in this paper is designed to start with sn = 4 nodes and η = 1 connections. A new node is added in each step and η links are created to connect existing nodes by using a preferential attachment given by the degree of node i k
i
and a probability
Figure 1-d is a Forest Hub & Spoke network. This network has 4 clusters each one with a star configuration. Each star contains 25 nodes (one central and 24 adjacent nodes). Node pairs are selected randomly to connect clusters. This topology is common in cloud systems to tackle with increased workloads via new cloud instances [9].
Mobile agents design is based on [2, 18]. In each round, each agent senses data from its environment obtaining a collection of perceptions p that contains the neighbourhood of the current location of the agent and messages from other agents (Algorithm 1).
The collection p is defined as: p = {nodeNeighbours, data, agentNeighbours, msg}, when: nodeNeighbours: is a set of the references of the nodes adjacent to the current agent location. Contains data related to the amount of pheromone in each node and a flag that indicates if the node has been visited by another agent previously. data: is the data collected from the current location, an agent collects and saves data in its internal memory. agentNeighbours: are references of other agents in the same location to exchange currently collected data. msg: data received from other agents.
Each agent executes a motionAlgorithm using the perceptions p to decide its next location. Next, the agent moves to a new location and exchanges data with its agentNeighbours.
Motion planning
Motion planning consists of the execution of the method motionAlgorithm (p) that given an agent perception performs some actions in the current node and selects the next location of each agent. It returns a reference to a node to perform move, taking as parameter a reference to the newly selected location.
In this subsection, it is presented a summary of the random algorithm and the carriers algorithm proposed in [16]. Next, a modification of these algorithms is introduced to mark visited nodes.
Random walks
When performing a random walk each agent selects one node reference from the nodeNeighbours collection. A uniformly distributed pseudo-random number generates one location from nodeNeighbours.
Carriers algorithm
The carriers algorithm proposed in [16] is based on [4] and uses a repulsive pheromone to find unexplored nodes. At starting, nodes have a pheromone value τ
v
= 0.5 and agents have an internal pheromone value τ
a
t
= 1. Each agent apply and exploitation rule or biased exploration based on a random variable q ∈ [0, 1] (Equation (1)):
If the exploitation rule is selected, each agent selects the node with the minimum pheromone amount from nodeNeighbours. In cases that more than one node has the same minimum, a random node is selected from these.
A random-proportional rule is performed if a biased exploration is selected. This rule assigns a probability of choosing a node p
d
(v) depending on the amount of pheromone τ
v
in its vicinity nodeNeighbours (Equation (2)).
Internal pheromone value of an agent is updated to τ a t (i) =1 if the agent finds new information. Additionally, passive evaporation [5] is added to each node and is performed by the environment with its own round number Eq. (5) with ρ = 0.01:
Marking nodes is a modification of random and carriers adding a boolean parameter in each node. At the beginning of each experiment, visited = false for all nodes indicating that there are no visited nodes. Line 10 of Algorithm 1 defines the first modification proposed in this paper to mark visited nodes. Each time that an agent pass through a node marks this node as visited (visited = true).
When an agent is performing the carriers or the random algorithm the collection nodeNeighbours is evaluated. If all the nodes were visited, the entire collection is the input for the selection of next location using random walks or carriers. If not, nodes with visited = false are the input for random walks or carriers exploration.
Experiments and results
Experiments aim to analyse the impact of marking explored locations to complete a data collection task with failure-prone agents. Each experiment is performed 30 times for a selected complex network and a failure probability p f . Experiments stop if an agent collects data from all the nodes of the selected complex network of if all the agents fail.
Each simulation starts with 10 agents (each network has 100 nodes). Agents start from the same random location in the 30 repetitions of the same experiment. Movement algorithms in experiments are random walks, carriers, random walks with marking (randomM) and carriers with marking (carriersM). Selected failure probabilities are (p
f
= 0, 0.001, 0.003, 0.005 and 0.008). Studied complex networks in this paper are: Small-world: degree = 4, β = 0.5, n = 100. Community: degree = 4, β = 0.5, m = 100, n _ clusters = 4. Scale-free: steps = 97, sn = 4, η = 1. Forest hub & spoke: n
clusters
= 4.
Metrics to evaluate the simulation are the following: Round number: box-plots of the round number of the first agent that collected data from a selected network. Success rates: histograms with the number of successful experiments (cases when at least one agent collected data from a selected network). Messages sent: box-plots of the number of messages in each simulation. Corresponds to the number of encounters between agents in the same location.
Round number analysis
The first analysis is performed in terms of round number for a p f = 0 as shown in Fig. 2.
Box-plot of round number for complex networks for carriers, carriers with Marking (carriersM), random walks and random walks with Marking (randomM).
To see if there is a significant difference for the different algorithms, an ANOVA test is performed [19] for each complex network and a p
f
= 0 with the following hypothesis: H0: Round number means are equal for a network G and the selected movement algorithms; H1: Round number means are different for a network G and the selected movement algorithms, indicating a correlation between the movement algorithm and the round number.
For all the networks Pvalue < 0.005, so the null hypothesis is rejected (Cf. Table 1). There is a difference in terms of the medians of round numbers for the motion algorithms. By observing the box-plot in Fig 2, a Tukey HSD test is performed to evaluate a possible significant difference in means for each complex network.
ANOVA Test Values
In the small-world, there is not a significant difference between means in the pairs: carriersM-carriers, randomM-carriers and randomM-carriersM. However, carriers have a lesser round number in the box-plots of Fig. 2 and better success rates than the other algorithms if p f increases (cf. Fig. 3). In the experiments performed there is a significant difference between random and carriers, random and carriersM and random and randomM so random exploration is improved via marking.
Success rates number for complex networks for carriers, carriers with Marking (carriersM), random walks and random walks with Marking (randomM).
In the community network, there is a significant difference between carriers and the other algorithms being carriers the fastest algorithm (Cf. Fig. 2-Community and Fig. 3-b). Additionally, CarriersM and randomM perform better than random with a significant difference. Between randomM and carriersM there is not a significant difference.
In the selected scale-free network, the difference between carriersM and carriers is significant so marking improves the results (cf. Fig. 2-scale-free, Fig. 3-c and d). Marking is a key factor to improve the rounds number in this network because there is not a significant difference between carriersM and randomM but there is a difference between this two methods and random. The same result is obtained for the forest hub & spoke being randomM and carriersM the fastest algorithms (cf. Fig 2-Forest hub & spoke and Fig. 3-e and f).
As a conclusion, marking nodes improves the results of experiments performed in selected networks with central hubs like forest hub & spoke and the selected scale-free network with a significant difference respect to the original version of carriers and random proposed in [16]. However, in small-world and community networks the algorithm that is improved with marking is random. The carriers algorithm proposed in [16] performs better than the two versions of marking proposed.
Results show that the most robust networks are small-world and community (Fig 3-a and 3-b) with successful experiments for p f = 0.008. In the two networks, the highest success rates are for the carriers algorithm in [16]. In the selected scale-free and forest-hub & spoke networks, marking looks promising because carriersM and randomM have the highest success rates when p f increases (Fig 3-c,d and 3-e,f).
As an additional result, Algorithms with marking have higher robustness than random walks in all the selected networks where in [16] random was better than carriers. As shown in [16] a fast data collection imply better success rates.
Messages sent Analysis
This metric estimates the number of messages sent among mobile agents. It corresponds to the number of encounters between agents. Box-plots with the number of messages for a p f = 0 are shown in Fig. 4. Results show that the faster and successful strategies also imply less amount of messages. Marking can also avoid agents exploring the same nodes reducing encounters among agents. Techniques that favour exploitation on unexplored nodes, reduce encounters between agents and are fast in the selected scale-free and forest hub & spoke networks.
Box-plot of number of messages for complex networks for carriers, carriers with Marking (carriersM), random walks and random walks with Marking (randomM).
This paper evaluated the use of marking visited nodes in a data collection model proposed in [16]. Marking visited nodes improved the previously obtained results in networks with higher deviations in the betweenness centrality like the selected scale-free network and forest hub & spoke. However, in small-world and community networks the carriers algorithm in [16] is the fastest. The obtained results can be applied to recover mobile agents lost in communication when a good round number in the data collection task is required to recover agents efficiently [17].
Results of this paper provide additional insights into the characteristics that impact data collection and synchronisation especially, failure frequency and the network topology. This information can be promising in the design of distributed applications and execution environments with applications like sensor networks and clouds and IoT environments.
As future work approaches to obtain a robust algorithm applicable to all the selected topologies should be studied. This can be important to provide robustness in data collection and synchronisation independently of the topology of the network. This algorithm can be key to study in the future how self-heal networks using mobile agents that collect and synchronise data about the topology of a determined network. Additional information is available, including source code of the simulation at http://www.alife.unal.edu.co/~aerodriguezp/impdatacol/.