Mourad Hadjila

Hervé Guyennet
email: herve.guyennet@femto-st.frm_feham@mail.univ-tlemcen.dz

Mohammed Feham

A Hybrid Cluster and Chain-based Routing Protocol for Lifetime Improvement in WSN

Keywords: Wireless sensor network, fuzzy c-means, clustering, ant colony optimization, network lifetime

The main challenge in the field of Wireless Sensor Networks (WSNs) is the energy conservation as long as possible. Clustering paradigm has proven its ability to prolong the network lifetime. The present paper proposes two algorithms using an approach that combines fuzzy c-means and ant colony optimization to form the clusters and manage the transmission of data in the network. First, fuzzy c-means is used to construct a predefined number of clusters. Second, we apply Ant Colony Optimization (ACO) algorithm to form a local shortest chain in each cluster. A leader node is randomly chosen at the beginning since all cluster nodes have the same amount of energy. In the next transmission, a remaining energy parameter is employed to select leader node. In the first algorithm, leader nodes transmit data in single hop to the distant base station (BS) while in the second the ACO algorithm is applied again to form a global chain between leader nodes and the BS. Simulation results show that the second proposed algorithm consumes less energy and effectively prolongs the network lifetime compared respectively with the first proposed and the LEACH algorithms. abstract environment.

Introduction

The progress made in recent decades in the fields of microelectronics, micromechanics, and wireless communication technologies, have produced at a reasonable cost components in volume of a few cubic millimeters, called sensor nodes. A sensor node is typically equipped with a sensing subsystem, a processing subsystem, a radio subsystem and a power supply subsystem [START_REF] Anastasi | Energy Conservation in Wireless Sensor Networks: A survey[END_REF]. Standalone deployment of several of them, to collect and transmit environmental data to one or more collection points form a wireless sensor networks (WSNs). Sensor networks can be very useful in many applications when it comes to collecting and processing information from the environment. Among the areas where these networks can offer the best contributions we quote the following areas: military, environmental, home, health, safety, etc.

The constraints imposed by these networks are very well known: very limited computation, communication, storage capabilities, and energy resources. This last aspect, which limits the lifetime of the network and therefore its utility, has received considerable attention by the research community over the last several years. The design of energy-aware protocols, algorithms, and mechanisms, with the goal of saving as much energy as possible, and therefore extending the lifetime of the network, has been the topic of many research studies [START_REF] Johnen | Self-stabilizing weight-based clustering algorithm for ad hoc sensor networks[END_REF]. Since communication task consumes the most energy during the network operation, clustering is introduced to WSNs because it has proven to be an effective approach to provide better data aggregation and avoid longest link. Clustering consists to breakdown network into groups of entities called clusters by giving to network a hierarchical structure [START_REF] Wightmanl | Topology Maintenance : Extending the Lifetime of Wireless Sensor Networks[END_REF]. A cluster is composed of cluster-head and member nodes. Choosing cluster centers is a crucial to clustering. One of the most used approaches in this regard is Fuzzy C-Means (FCM), which assists to optimize the clusters based on minimizing the distance between the sensor node and the cluster center [START_REF] Hoang | Fuzzy C-Means Clustering Protocol for Wireless Sensor Networks[END_REF]. In addition to cluster-based protocols, chain-based protocols reduce against the total energy of the network [START_REF] Lindsey | PEGASIS: Power-efficient gathering in sensor information systems[END_REF][START_REF] Yu | An Energy-Efficient Chain-Based Routing Protocol in Wireless Sensor Network[END_REF][START_REF] Guo | PEGASIS protocol in wireless sensor network based on an improved ant colony algorithm[END_REF][START_REF] Chen | Energy efficiency of a chain-based scheme with Intra-Grid in wireless sensor networks[END_REF][START_REF] Linping | Improved algorithm of PEGASIS protocol introducing double cluster heads in wireless sensor network[END_REF][START_REF] Du | Chain-based protocols for data broadcasting and gathering in the sensor networks[END_REF]. An ant colony optimization (ACO) algorithm can be used to form a chain between multiple nodes [START_REF] Wen | An Ant-based approach to Power-Efficient Algorithm for Wireless Sensor Networks[END_REF]. As the energy is inversely proportional to the distance, the construction of short-chain is highly recommended while the ACO algorithm be the best suited for this kind of problem. In this paper in order to enhance network lifetime, we combine the above two approaches, cluster-based and chain-based, for routing data to the BS. We propose two protocols where the second protocol is an improvement of the first one. The rest of this paper is organized as follows: section II introduces related works. Section III describes the proposed protocols. The simulation is then analyzed in Section IV in order to validate our approaches and this paper is concluded in Section V.

Related work

One of the fundamental problems in WSNs is how to prolong the network lifetime. In order to achieve this, many researchers proceed in grouping sensor nodes into clusters. Clustering routing protocols have been developed in order to reduce the network traffic toward the BS [START_REF] Bandyopadhyay | An energy efficient hierarchical clustering algorithm for wireless sensor networks[END_REF][START_REF] Banerjee | A clustering scheme for hierarchical control in multi-hop wireless networks[END_REF][START_REF] Boukerche | Fault-tolerant wireless sensor network routing protocols for the supervision of context-aware physical environments[END_REF][START_REF] Boukerche | An energy-aware and fault tolerant inter-cluster communication based protocol for wireless sensor networks[END_REF][START_REF] Heinzelman | Energy-efficient communication protocol for wireless microsensor networks[END_REF][START_REF] Manjeshwar | TEEN: A Routing Protocol for Enhanced Efficiency in Wireless Sensor Networks[END_REF][START_REF] Manjeshwar | APTEEN: A Hybrid Protocol for Efficient Routing and Comprehensive Information Retrieval in Wireless Sensor Networks[END_REF][START_REF] Younis | HEED: a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks[END_REF]. Low-Energy Adaptive Clustering Hierarchy (LEACH) [START_REF] Heinzelman | Energy-efficient communication protocol for wireless microsensor networks[END_REF] is one of the most common cluster routing protocols, which aims to achieve the load balancing in sensor nodes so it can prolong the network lifetime. Each sensor node elects itself as a cluster-head based on the probability model. Each sensor node will become cluster-head in every cycle to evenly distribute the works load. Hybrid Energy-Efficient Distributed (HEED) [START_REF] Younis | HEED: a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks[END_REF] clustering approach is one of the most recognized energy-efficient clustering protocols. It extends the basic scheme of LEACH by using residual energy and node degree or density. In HEED, the clustering process is divided into a number of iterations, and a node is selected as a cluster head depending on whether other cluster heads are its one hop neighbors and its own residual energy. Hoang et al in [START_REF] Hoang | Fuzzy C-Means Clustering Protocol for Wireless Sensor Networks[END_REF] proposed an approach based on fuzzy cmeans for clustering calculation, cluster head selection and data transmission.

Another family of solutions is chain-based protocols [START_REF] Lindsey | PEGASIS: Power-efficient gathering in sensor information systems[END_REF][START_REF] Yu | An Energy-Efficient Chain-Based Routing Protocol in Wireless Sensor Network[END_REF][START_REF] Guo | PEGASIS protocol in wireless sensor network based on an improved ant colony algorithm[END_REF][START_REF] Chen | Energy efficiency of a chain-based scheme with Intra-Grid in wireless sensor networks[END_REF][START_REF] Linping | Improved algorithm of PEGASIS protocol introducing double cluster heads in wireless sensor network[END_REF][START_REF] Du | Chain-based protocols for data broadcasting and gathering in the sensor networks[END_REF]. In this category, PEGASIS [START_REF] Lindsey | PEGASIS: Power-efficient gathering in sensor information systems[END_REF] was the first protocol. It forms a chain including all nodes in the network using a greedy algorithm so that each node transmits to and receives from a neighboring node. In each round, nodes take turns to be leader and transmit the aggregated data to the base station. Kemei Du et al. proposed a multiple-chain scheme [START_REF] Du | Chain-based protocols for data broadcasting and gathering in the sensor networks[END_REF] to decrease the total transmission distance for all-toall broadcasting in order to prolong network lifetime. The key idea is to divide the whole network into four regions centered at the node that is closest to the center of the network. Also, the linear sub-chains in each region are constructed by minimum total energy algorithm.

Proposed algorithms

Before explaining the proposed approaches, we briefly introduce the principle of the cluster formation using fuzzy cmeans algorithm and the formation of the chains using ant colony optimization algorithm.

Cluster formation using Fuzzy C-Means algorithm

Fuzzy C-Means (FCM) is an unsupervised fuzzy classification algorithm. It introduces the concept of fuzzy set in the definition of clusters: each node in the deployed area belongs to each cluster with a certain degree, and all clusters are characterized by their center of gravity.

Like other non-supervised classification algorithms, it uses a criterion of minimizing intra-cluster distances and maximizing inter-cluster distances, but giving a degree of belonging to each cluster for each node. This algorithm requires prior knowledge of the number of clusters and generates clusters through an iterative process by minimizing an objective function. Thus, it provides a fuzzy partition of the environment by giving each node a degree between 0 and 1 in a given cluster. The cluster, which is associated with a node, is one whose degree of membership is the highest. FCM is based on minimizing the following objective function [START_REF] Izakian | Fuzzy clustering using hybrid fuzzy c-means and fuzzy particle swarm optimization[END_REF]:

J m = c i=1 N j=1 µ m ij .d 2 ij ( 1
)
Where m is any real number greater than 1, µ ij is node j's degree of belonging to cluster i, c is the number of clusters, N is the number of nodes and d ij is the Euclidean distance between node j and the center of cluster i.

The algorithm is composed of the following steps:

1. Fix an arbitrary membership matrix.

2. Compute the centers of the clusters using the following equation:

z j = N i=1 µ m ij .o i N i=1 µ m ij (2)
3. The readjustment of the membership matrix according to the position of the centers is done according to the equation below:

µ ij = 1 c k=1 dij d kj 2 m-1 (3) 4.
Computes the minimization and return to step 2 if there is no convergence criterion.

Chains formation using ant colony algorithm

The basic idea in ant colony optimization algorithms (ACO) is to imitate the cooperative behavior of real ants to solve optimization problems. ACO metaheuristics have been proposed by M. Dorigo [START_REF] Dorigo | Ant colony optimization theory: A survey[END_REF]. They can be seen as multiagent systems in which each single agent is inspired by the behavior of a real ant. Traditionally, ACO have been applied to combinatorial optimization problems and they have achieved widespread success in solving different problems (e.g., scheduling, routing, assignment) [?].

To construct a local chain in each cluster, we use the ant colony algorithm. The idea is borrowed from the Traveling Salesman Problem (TSP) [START_REF] Dorigo | The ant colony optimization metaheuristic: Algorithms, applications, and advances[END_REF] where a shortest open chain is constructed in each cluster using the ant colony algorithm. Initially, each ant is randomly put on a node. During the construction of a feasible solution, ants select the following node to be visited through a probabilistic decision rule. When an ant k states in node i and constructs the partial solution, the probability moving to the next node j neighboring on node i is given by:

p k ij (t) =    τij (t) α .η β ij l∈J k i τ il (t) α .η β il if j ∈ J k i 0 otherwise (4)
Where J k i is the list of possible moves for an ant k when it is on a node i, η ij is the visibility which is equal to the inverse of the distance between two nodes i and j (1/d ij ) and τ ij (t) is the intensity of the runway at a given iteration t. The two main parameters controlling the algorithm are α and β which controls the relative intensity and the visibility of an edge. Once the tour nodes performed, an ant k deposits a quantity of pheromone ∆τ ij on each edge of the course:

∆τ k ij (t) = Q L k (t) if (i, j) ∈ T k (t) 0 otherwise (5)
Where T k (t) is the tour done by ant k at iteration t, L k (t) the length of the path and a Q parameter setting. At the end of each iteration of the algorithm, the pheromone deposited at previous iterations by ants evaporate from:

ρ∆τ k ij (6)
And at the end of the iteration, we have the sum of pheromones that have not evaporated and those who have just been laid.

τ ij (t + 1) = (1 -ρ) .τ ij (t) + m k=1 ∆τ k ij ( 7
)
Where m is the number of ants and ρ is an adjustment parameter. At the end, when all tours are completed, we remove in each chain the longest distance between two nodes in order to obtain a shortest open chain.

Description of the proposed algorithms

n the present work, we combine different tools to deal with the problem of energy conservation in the field of WSNs. We propose two algorithms where we first applied FCM algorithm to form a predefined number of clusters. The number of clusters is chosen equal to square root of the total nodes. Second, an ACO algorithm is used to construct a local chain in each cluster. Figure 1 shows an example of cluster containing eight nodes interconnected to form a closed chain. This chain is obtained using the ant colony optimization algorithm as used in TSP. Then, we remove the longest distance between two consecutive nodes in order to obtain the shortest open chain. In Figure 2, the line between node 1 and node 8 is deleted. For routing data from nodes to the BS, we proceed as follows: At the beginning, a randomly node elects itself a leader node since all cluster nodes have the same amount of energy. For data gathering and fusion, each cluster member node senses and transfers data along the local chain to reach one particular node, which is leader node; the latter receives and aggregates data. When a node dies in a local chain, this latter is reconstructed by bypassing the dead node. The data transmission mode to the BS constitutes the difference between the two proposed approaches. In the first, the leader nodes send data directly to the BS meaning in one hop while in the second data transmission is performed in multiple hops by forming a global chain connecting all the leader nodes using again the ACO algorithm. Leader node rotation in each cluster is performed according to the remaining energy of nodes. The proposed algorithms are centralized controlled by the BS. Figure 3 and4 illustrate the operating principles of our algorithms where the red lines represent the shortest chain that links nodes in each cluster while the blue dashed lines join the leader nodes and the BS respectively in single hop and multi-hop.

Simulation and evaluation

In this section, we evaluate the performance of our proposed algorithms in Matlab. We consider 100 nodes randomly deployed in an area of (100 × 100) m 2 , the BS is located outside the area at the coordinate (50, 150) so it is at least 50m from the closest sensor node. The following properties are assumed in regard to the sensor network being studied:

-The nodes are homogeneous and they are static.

-All the nodes have the same initial energy and the BS is not limited in terms of energy, memory and computational power. -Links are symmetric so that the energy required to transmit a message from node i to node j is the same as energy required to transmit a message from node j to node i.

In the simulation part, we use the same radio model as introduced in [?] which is the first order radio model. This radio model uses both of the open space (energy dissipation d 2 ) and multi path (energy dissipation d 4 ) channels by taking amount the distance between the transmitter and receiver. So energy consumption for transmitting a packet of l bits in distance d is given by ( 8).

E T X (l, d) = l.E elec + l.E f s .d 2 if d < d 0 l.E elec + l.E mp .d 4 if d ≥ d 0 (8)
Where d 0 is the distance threshold value, which is obtained by ( 9), E elec is required energy for activating the electronic circuits. E f s and E mp are required energy for amplification of transmitted signals to transmit a one bit in open space and multi path models, respectively.

d 0 = E f s E mp (9)
Energy consumption to receive a packet of l bits is calculated according to [START_REF] Du | Chain-based protocols for data broadcasting and gathering in the sensor networks[END_REF].

E RX (l) = l.E elec (10)
The full simulation parameters are listed in table 1. where E DA represents the energy required for data aggregation.

Two metrics are chosen in order to evaluate the proposed schemes, which are energy consumption and the number of alive nodes. Figure 5 illustrates the residual energy in the network for the three algorithms.

From the simulation results shown in figure 6, it was observed that the proposed2 algorithm consumes less energy than the proposed1. This is due to the presence of global chain, which reduces the long transmission from leader nodes to the remote BS. We see again that proposed1 is a few better than LEACH in term of energy consumption.

Figure 7 shows the evolution of the number of alive nodes per the number of rounds. We observe that the first node dies in LEACH 653 rounds while in proposed1 and proposed2 first node dies after 654 and 964 rounds respectively. We also observe that the last node dies in LEACH after 1046 rounds while in proposed1 and proposed2 first node dies after 1213 and 1740 rounds respectively. Therefore, we note that proposed2 is about 30.28% more efficient in term of network lifetime than proposed1 and about 39.88% than the LEACH algorithm.

Conclusion

In this paper, we introduced two algorithms to address the problem of energy conservation in wireless sensor networks combining cluster-based and chainbased approaches. These algorithms are characterized by partitioning nodes in a predefined number of clusters using FCM and formation of local chain in each cluster. Inter-cluster communication is performed by chain-based approach using an ACO algorithm to find the shortest chain that links all cluster member nodes. The difference between the two proposed algorithms lies in the data transmission mode to the remote BS. The first uses direct transmission from leader nodes to the BS while the second constructs a global chain connecting the leader nodes and the BS. Also, these algorithms select leader node for each chain according to the remaining energy of nodes. Simulation results show that proposed2 prolong the network lifetime about 30.28% and 39.88% in comparison with the proposed1 and LEACH.

Fig. 1 .

 1 Fig. 1. Formation of closed chain.

Fig. 2 .

 2 Fig. 2. Formation of the open chain.

Fig. 3 .

 3 Fig. 3. Operating principle of the first algorithm.

Fig. 4 .

 4 Fig. 4. Operating principle of the second algorithm.

Fig. 5 .

 5 Fig. 5. Residual energy of the network vs. number of rounds.

Fig. 6 .

 6 Fig. 6. Energy consumption vs. number of rounds.

Fig. 7 .

 7 Fig. 7. Number of alive nodes vs. number of rounds.

Table 1 .

 1 Simulation parameters

	Parameters	Values
	Network size	(100 x 100) m 2
	Number of nodes	100
	Initial energy	0.1 J
	Packet size	1000 bits
	E elec	50 x 10 -9
	E f s	10 -11
	Emp	1.3 x 10 -15
	EDA	5 x 10 -9


Alban Rousset
email: alban.rousset@femto-st.fr

Bénédicte Herrmann
email: bherrman@femto-st.fr

Christophe Lang
email: clang@femto-st.fr

Laurent Philippe
email: lphilipp@femto-st.fr

A survey on parallel and distributed Multi-Agent Systems

Simulation has become an indispensable tool for researchers to explore systems without having recourse to real experiments. Depending on the characteristics of the modeled system, methods used to represent the system may vary. Multi-agent systems are, thus, often used to model and simulate complex systems. Whatever modeling type used, increasing the size and the precision of the model increases the amount of computation, requiring the use of parallel systems when it becomes too large. In this paper, we focus on parallel platforms that support multi-agent simulations. Our contribution is a survey on existing platforms and their evaluation in the context of high performance computing. We present a qualitative analysis, mainly based on platform properties, then a performance comparison using the same agent model implemented on each platform.

Introduction

In the field of simulation, we often seek to exceed limits, that is to say analyse larger and more precise models to be closer to the reality of a problem. Increasing the size of a model has however a direct impact on the amount of needed computing resources and centralised systems are often no longer sufficient to run these simulations. The use of parallel resources allows us to overcome the resource limits of centralised systems and also to increase the size of the simulated models.

There are several ways to model a system. For example, the time behavior of a large number of physical systems is based on differential equations. In this case the discretization of a model allows its representation as a linear system. It is then possible to use existing parallel libraries to take advantage of many computing nodes and run large simulations. On the other hand it is not always possible to model any time dependent system with differential equations. This is for instance the case of complex systems. A complex system is defined in [START_REF] Herbert | The architecture of complexity[END_REF] as "A system that can be analyzed into many components having relatively many relations among them, so that the behavior of each component depends on the behavior of others". Thus the complexity of the dependencies between the phenomena that drive the entities behavior makes it difficult to define a global law that models the entire system. For this reason multi-agent systems are often used to model complex systems because they rely on an algorithmic description of agents that interact and simulate the expected behavior. From the viewpoint of increasing the size of simulations, multi-agent systems are constrained to the same rules as other modelling techniques but there exists less support for parallel execution of the models.

In this article, we focus on multi-agent platforms that provide parallel distributed programming environments for multi-agent systems. Recently, the interest for parallel multi-agent platforms has increased. This is because parallel platforms offer more resources to run larger agent simulations and thus allows to obtain results or behavior that was not possible to obtain with smaller number of agents (eg. simulation of individual motions in a city/urban mobility).

The contribution of this article is a survey on parallel distributed multiagent platforms. This survey is based on an extensive bibliographical work done to identify the existing platforms, a qualitative analysis of these platforms in terms of ease of development, distribution management or proposed agent model, and a performance evaluation based on a representative model run on a HPC cluster.

The article is organised as follows. First, we give the context of multiagent system (MAS) in general and parallel distributed multi-agent systems (PDMAS) in particular. We then introduce the different multi-agent platforms found in our bibliographical research. In the third section, we describe the method used to classify platforms and we describe the model implemented in each platform to evaluate its performance. In the fourth section, we present the qualitative comparison of the different PDMAS followed by the benchmark based on the implemented model. We finish the paper with conclusion and future work.

Related works

The concept of agent has been studied extensively for several years and in different domains. It is not only used in robotics and other fields of artificial intelligence, but also in fields such as psychology [START_REF] Carslaw | Agent based modelling in social psychology[END_REF] or biology [START_REF] Vincent Rodin | An immune oriented multi-agent system for biological image processing[END_REF]. One of the first definitions of the agent concept is due to Ferber [START_REF] Ferber | Les systèmes multi-agents: vers une intelligence collective[END_REF] :

"An agent is a real or virtual autonomous entity, operating in a environment, able to perceive and act on it, which can communicate with other agents, which exhibits an independent behavior, which can be seen as the consequence of his knowledge, its interactions with other agents and goals it need to achieved".

A multi-agent system, or MAS, is a platform that provides the mandatory support to run simulations based on several autonomous agents. These platforms implement functions that provide services such as agent life cycle management, communication between agents, agent perception or environment management. Among well known platforms we can cite Repast Simphony [START_REF] Michael | Complex adaptive systems modeling with repast simphony[END_REF], Mason [START_REF] Luke | MASON: A New Multi-Agent Simulation Toolkit[END_REF], NetLogo [START_REF] Tisue | Netlogo: Design and implementation of a multi-agent modeling environment[END_REF] and Gama [START_REF] Amouroux | Gama: an environment for implementing and running spatially explicit multi-agent simulations[END_REF]. These platforms however do not natively implement a support to run models in parallel and it is necessary to develop a wrapper from scratch, in order to distribute or parallelize a simulation. There exists several papers that propose survey on these multi-agent platforms [START_REF] Tobias | Evaluation of free java-libraries for social-scientific agent based simulation[END_REF][START_REF] Rafael H Bordini | A survey of programming languages and platforms for multi-agent systems[END_REF][START_REF] Berryman | Review of software platforms for agent based models[END_REF][START_REF] Heath | A survey of agentbased modeling practices (january 1998 to july 2008)[END_REF]. Some platforms like RepastHPC [START_REF] Collier | Repast HPC: A platform for largescale agentbased modeling[END_REF], D-Mason [START_REF] Cordasco | A Framework for Distributing Agent-Based Simulations[END_REF], Pandora [START_REF] Elaini S Angelotti | Pandora: a multi-agent system using paraconsistent logic[END_REF], Flame [START_REF] Coakley | Exploitation of hpc in the flame agentbased simulation framework[END_REF] or JADE [START_REF] Bellifemine | Jade-a fipa-compliant agent framework[END_REF] provide a native support for parallel execution of models. This support usually includes the collaboration between executions on several physical nodes, the distribution of agents between nodes and so on. During our analysis of the literature, we did not find any survey about parallel multi-agent platforms except the paper written by Coakley and al. [8]. This comparison is based on qualitative criteria such as the implementation language but the paper does not provide any performance comparison of the studied platforms.

After an extensive bibliographical work, we identified 10 implementations or projects of parallel multi-agent platforms. For each platform we tried to download the source or executable code and we tried to compile it and test it with the provided examples and templates. Some of the platforms cannot be included in our study because there is no available source code or downloadable executable (MACE3J [START_REF] Gasser | Mace3j: fast flexible distributed simulation of large, large-grain multi-agent systems[END_REF], JAMES [START_REF] Himmelspach | Plug'n simulate[END_REF], SWAGES [START_REF] Scheutz | Swagesan extendable distributed experimentation system for large-scale agentbased alife simulations[END_REF]), or because only a demonstration version is available (PDES-MAS [START_REF] Oguara | Pdesmas: A unifying framework for the distributed simulation of multi-agent systems[END_REF][START_REF] Vinoth Suryanarayanan | Pdes-mas: Distributed simulation of multi-agent systems[END_REF]), or because there is a real lack of documentation (Ecolab [START_REF] Russell | Ecolab: Agent based modeling for c++ programmers[END_REF]). It was thus not possible to build a new model in these platforms and thus to assess their parallel characteristics and performance. These platforms have subjected to a qualitative analysis which is not included in this paper.

For the 5 remaining platforms, on which we were able to implement our model, we can consider that they truly offer a functioning parallel multi-agent support. We succinctly present each of these platforms in the following.

D-Mason (Distributed Mason) [START_REF] Cordasco | A Framework for Distributing Agent-Based Simulations[END_REF] is developed by the University of Salerno. D-Mason is the distributed version of the Mason multi-agent platform. The authors choose to develop a distributed version of Mason to provide a solution that does not require users to rewrite their already developed simulations and also to overcome the limitations on maximum number of agents. D-Mason uses ActiveMQ JMS as a base to implement communications. D-Mason uses the Java language to implement the agent model.

Flame [START_REF] Coakley | Exploitation of hpc in the flame agentbased simulation framework[END_REF] is developed by the University of Sheffield. Flame was designed to allow a wide range of agent models. Flame provides specifications in the form of a formal framework that can be used by developers to create models and tools. Flame allows parallelization using MPI. Implementing a Flame simulation is based on the definition of X-Machines [START_REF] Coakley | Using x-machines as a formal basis for describing agents in agent-based modelling[END_REF] which are defined as finite state automata with memory. In addition, agents can send and receive messages at the input and the output of each state.

Jade [START_REF] Bellifemine | Jade-a fipa-compliant agent framework[END_REF] is developed by the Telecom laboratory of Italia. The aims of Jade are to simplify the implementation of distributed multi-agent models across a FIPA compliant [START_REF] Bellifemine | Jade-a fipa-compliant agent framework[END_REF] middleware and to provide a set of tools that support the debugging and the deployment phases. The platform can be distributed across multiple computers and its configuration can be controlled from a remote GUI. Agents are implemented in Java while the communications relay on the RMI library.

Pandora [START_REF] Elaini S Angelotti | Pandora: a multi-agent system using paraconsistent logic[END_REF] is developed by the Supercomputing center of Barcelona. It is explicitly programmed to allow the execution of scalable multi-agent simulations. According to the literature, Pandora is able to treat thousands of agents with complex actions. Pandora also provides a support for a geographic information system (GIS) in order to run simulations where spatial coordinates are used. Pandora uses the C + + language to define and to implement the agent models. For the communications, Pandora automatically generates MPI code from the Pandora library.

RepastHPC [START_REF] Collier | Repast HPC: A platform for largescale agentbased modeling[END_REF] is developed by the Argone institute of USA. It is a part of a series of multi-agent simulation platforms: RepastJ and Repast Simphony. RepastHPC is specially designed for high performance environments. RepastHPC use the same concepts as the core of RepastSimphony, that is to say it uses also the concept of projections (grid, network) but this concept is adapted to parallel environments. The C + + language is used to implement an agent simulation but the ReLogo language, a derivative of the NetLogo language, can also be used. For the communications, the RepastHPC platform relays on MPI using the Boost library [START_REF] Collier | Repast hpc manual[END_REF].

From these descriptions we can note that some platforms have already been designed to target high performance computing systems such as clusters whereas others are more focused on distribution on less coupled nodes such as a network of workstations.

Survey methodology

In this section we explain the methodology used to make this survey. As already stated we started by a bibliographical search (using keywords on search engines and following links cited in the studied articles). This bibliographical search allowed us to establish a first list of existing platforms. By testing the available platforms we established a second list of functioning platforms. To our knowledge this list is complete and their is no other available and functional platform that provide a support for parallel distributed MAS. Note we only concentrate on distributed platforms and that the list excludes shared memory parallel platforms and many-cores (as GPU or Intel Xeon Phi) platforms. After we defined different criteria to compare and analyse each platform. We finished by implementing a reference model on each platform and executing it in order to compare the platform performance. These evaluation steps are detailed in the following.

This survey mainly focuses on the implementation, more precisely the development, of models and their execution efficiency. To classify the platforms we defined two sets of criteria: first, implementation and execution based criteria and, second, criteria about classical properties of parallel systems. We briefly explain in which correspond each criteria.

For the implementation and execution criteria, all platforms have their own constraints that impact on the ease of the model implementation. The chosen criteria are:

1. Programming language, 2. Agent representation 3. Simulation type, time-driven or event-driven 4. Reproductibility, do several executions of a simulation give the same results?

For the classical properties of parallel systems, we focus on:

1. Scalability of platform, in terms of agents and nodes, 2. Load balancing, agent distribution, 3. MultiThread execution, to take benefit of multicore processors, 4. Communication library.

To further compare the platforms, we have defined a reference agent model that we implemented on each platform. The reference model is based on three important behaviors for each agent: the agent perception, the communications between agents and/or with the environment and agent mobility. The reference model simulates each of these behaviors. Each agent is composed of 3 sub-behaviors :

1. The walk behavior allows agents to move in a random direction on the environment. This behavior is used to test the mobility and the perception of the agents. As the agents walk through their environment to discover other agents and other parts of the environment, interactions and communications with the environment are also tested with this behavior.

2. The interact behavior allows agents to interact and send messages to other agents in their perception fields. This behavior intends to simulate communications between agents and to evaluate the communication support of the platforms.

3. The compute behavior allows agents to compute a "Fast Fourier Transform (FFT)" [START_REF] Frigo | The design and implementation of fftw3[END_REF] in order to represent a workload. This behavior intends to simulate the load generated by the execution of the agent inner algorithms.

The global agent behavior consists in performing each of this three behaviors at each time step. The reference model has several parameters that determine the agent behavior and also the global model properties. For instance, the model allows to vary the workload using different sizes of input for the FFT calculus. It is also possible to generate more or less communications between agents by setting the number of contacted agents in the interact behavior or to assess the agent mobility by setting the agent speed in the walk behavior.

Qualitative analysis

In this section we expose two levels of comparisons between the studied platforms: first a qualitative comparison using the previously presented criteria and second a performance comparison using the reference model.

Table 1 gives a synthetic representation of the comparison for the implementation and execution criteria. Most platforms use classical languages such as C-C++ or Java to define agents, except the Flame platform which uses the XMML language. The XMML language is an extension of the XML language designed to define X-Machines. Note that the RepastHPC platform implements, in addition to the C++ programming language, the widespread Logo agent language. The Repast-Logo or R-Logo is the Repast implementation of Logo for C++. It allows to simplify the simulation implementation at the price of a lower power of expression compared to C++. Agents are usually defined as objects with methods representing behaviors. An agent container gathers all the agents. This container is cut and distributed in the case of parallel execution. The agent implementation is different for the Flame platform that does not use the object concept to define a agent but rather uses automatas called X-Machines. In a X-Machine, a behavior is represented by a state in the automata and the order of execution between behaviors are represented by transitions. This difference changes the programming logic of a model but induces no limitation compared with other platforms because agents are in fact encoded in C language.

For the simulation type, event or time driven, all platforms use the timedriven approach except RepastHPC which is based on the event-driven approach. RepastHPC however allows to fix a periodicity to each scheduled event, so that we can reproduce the behavior of time-driven simulations.

Finally all platforms allow agents to communicate. This communication can be performed either internally with agents that are on the same node, or externally, with agents that are on different nodes. The D-Mason and Pandora platforms propose remote method invocations to communicate with other agents while the other platforms use messages to communicate between agents.

Table 2 summarises the criteria of the platforms about classical properties of parallel systems. Globally we can note that all studied platforms meet the demands for the development of parallel simulations. Note that we did not find any information on the scalability property of the Pandora and Jade platforms, so they are marked as Not Available (NA) for this property. To efficiency exploit the power of several nodes the computing load must be balanced among them. There is different ways to balance the computing load . The load can be balanced at the beginning of the simulation (Static) or adapted during the execution (Dynamic). A dynamic load balancing is usually better as it provides a better adaptation in case of load variation during the model execution, but it can also be subject to instability. Most platforms use dynamic load balancing except the Jade and Flame platforms. In [START_REF] Márquez | A load balancing schema for agent-based spmd applications[END_REF] the authors propose a way to use dynamic load balancing with the Flame platform.

RepastHPC D-Mason

Flame Pandora Jade Scalability 1028 proc. [START_REF] Holcombe | A general framework for agent-based modelling of complex systems[END_REF] 36 nodes [START_REF] Coakley | Exploitation of hpc in the flame agentbased simulation framework[END_REF] Note that only Flame does not support multi-threaded executions. The platform however relays on the MPI messaging library. As most MPI libraries provide optimised implementations of message passing functions when the communicating processes are on the same node, using processes located on the same node instead of threads does not lead to large overhead. In the implementation of a multi-agent system this probably leads to equivalent performance as the simplification of synchronisation issues may compensate the cost of using communication functions.

Last, the communication support for most platforms is MPI. This is not surprising for platforms targeting HPC systems as this library is mainly used on these computers. Note that the D-Mason platform relays on the JMS communication service despite it is not the most scalable solution for distributed environments. An MPI version of D-MASON is in development. Finally, the Jade platform is based on the java Remote Method Invocation (RMI) library which is not very adapted to parallel applications as it is based on synchronous calls. During the model implementation we also noted that the Jade platform seems to be more oriented for equipment monitoring and cannot be run on HPC computers due to internal limitations. Jade is thus not included in the rest of the comparisons.

Performance evaluation

For the performance evaluation we have implemented the reference model defined in section 3 on the four functional platforms: RepastHPC, D-MASON, Flame, Pandora. During this model implementation, we did not encounter noticeable difficulties expect with the RepastHPC platform for which we have not been able to implement external communications, communications between agents running on different nodes. RepastHPC does not have the native mechanisms to make it whereas it is possible to implement it on the other platforms. RepastHPC actually offers the possibility to interact with an agent on an other node but not to report the modifications.

Although we have been able to run the four platforms, D-Mason, Flame, Pandora, RepastHPC, on a standard workstation, only two of them (RpastHPC, Flame) have successfully run on our HPC system. The D-Mason platform uses a graphical interface that cannot be disconnected. We are thus not able to run D-MASON on our cluster, only accessible through its batch manager. The Pandora simulations have deadlock problems even if we use examples provided with the platform. For these reasons the presented results only consider the Flame and RepastHPC platforms.

We have realised several executions in order to exhibit the platform behaviors concerning scalability (Figures 2 and3) and workload (Figure 4). To assess scalability we vary the number of nodes used to execute the simulations while we fix the number of agents. We then compute the obtained speedup. For workload we fix the number of nodes to 8 and we vary the number of agents in the simulation. Each execution is realised several times to assess the standard variation and the presented results are the mean of the different execution durations. Due to a low variation in the simulation runtime, the number of executions for a result is set to 10. frequency and with 32 Go of memory. The nodes are connected through a non blocking DDR infinyBand network organised in a fat tree. The system is shared with other users but the batch system garanties that the processes are run without sharing their cores. Execution results for scalability for a model with 10 000 agents are given on Figure 2 and3, with the ideal speedup reference. Note that the reference time used to compute the speedup is based on a two core run of the simulations. This is due to RepastHPC which cannot run on just one core so that its reference time must be based on two core runs. The speedup is therefore limited to half the number of nodes. We can note that both platforms scale well up to 32 cores but the performance does not progress so well after, becoming 2/3 of the theoretical speedup for 128 cores. In addition on Figure 3 we can see that RepastHPC results are above the theorical speedup for simulations with less than 50 cores. As we suspected that these better results come from cache optimizations in the system, we did more tests to confirm this hypothesis. The realized tests increase the number of agents and the load on each agent to saturate the cache and force memory accesses. As the results for these new tests are under the theorical speedup the hypothesis is validated.

Figures 4 represents the workload behavior of the two platforms. The inner load of agents (FFT) is here set to 100. The figure shows that RepastHPC really better reacts to load increasing than Flame. The same behavior has also been noted for a load of 10 (for 20 000 agents the ratio is 0.92). On the opposite for a load of 1000 the difference is less noticeable (for 20 000 agents the ratio is 0.81). Obviously the used model does not use all the power of Flame as it is limited in term of inter-agent communications. The question to answer is: is it due to the use of the concept of X-Machines or synchro- nisation mechanisms in the underlying parallelism? Another possible reason that could justify this difference is the cost of the synchronisations provided by Flame when using remote agents and that is not managed in RepastHPC.

Conclusion

In this article we have presented a comparison of different parallel multi-agent platforms. This comparison is performed at two levels, first at a qualitative level using criteria on the provided support, and second at a quantitative level, using a reference agent model implementation. The qualitative comparison shows the properties of all the studied platforms. The quantitative part shows an equivalent scalability for both platforms but better performance results for the RepasHPC platform.

When implementing our reference model we have noticed that the synchronisation support of the platforms does not provide the same level of service: the RepastHPC platform does not provide communication support for remote agents while Flame do it. This support seems to be a key point in the platform performance.

For this reason, in our future work, we intend to better examine the efficiency of synchronisation mechanisms in parallel platforms. For example how are the synchronizations made during an execution and is there a way to improve synchronization mechanisms in parallel multi-agent systems?

Figure 1 :

 1 Figure 1: AML representation of the reference agent model

FigureFigure 3 :

 3 Figure Scalability of FLAME simulations using 10 000 agents, FFT 100 and 200 cycles

Figure 4 :

 4 Figure 4: Workload behavior for simulation using 8 cores

Table 1 :

 1 Comparison of implementation and execution properties

		RepastHPC	D-Mason	Flame	Pandora	Jade
	Prog. lang.	C++/R-Logo Java	XMML/C	C/C++	Java
	Agent repre-	Object	Object	X-Machine	Object	Object
	sent.
	Simu. type	event-driven	time-driven	time-driven	time-driven	time-driven
	Reproductibility Yes	Yes	No	Yes	No

Table 2 :

 2 Comparison classical properties of parallel systems

	432 proc. [8] NA	NA

Acknowledgment

Computations have been performed on the supercomputer facilities of the Mésocentre de calcul de Franche-Comté.


Huda Al-Nayyef
email: huda.al-nayyef@univ-fcomte.fr

Christophe Guyeux
email: christophe.guyeux@univ-fcomte.fr

Jacques M Bahi
email: jacques.bahi@univ-fcomte.fr

A Pipeline for Insertion Sequence Detection and Study for Bacterial Genome

Insertion Sequences (ISs) are small DNA segments that have the ability of moving themselves into genomes. These types of mobile genetic elements (MGEs) seem to play an essential role in genomes rearrangements and evolution of prokaryotic genomes, but the tools that deal with discovering ISs in an efficient and accurate way are still too few and not totally precise. Two main factors have big effects on IS discovery, namely: genes annotation and functionality prediction. Indeed, some specific genes called "transposases" are enzymes that are responsible of the production and catalysis for such transposition, but there is currently no fully accurate method that could decide whether a given predicted gene is either a real transposase or not. This is why authors of this article aim at designing a novel pipeline for ISs detection and classification, which embeds the most recently available tools developed in this field of research, namely OASIS (Optimized Annotation System for Insertion Sequence) and ISFinder database (an up-to-date and accurate repository of known insertion sequences). As this latter depend on predicted coding sequences, the proposed pipeline will encompass too various kinds of bacterial genes annotation tools (that is, Prokka, BASys, and Prodigal). A complete IS detection and classification pipeline is then proposed and tested on a set of 23 complete genomes of Pseudomonas aeruginosa. This pipeline can also be used as an investigator of annotation tools performance, which has led us to conclude that Prodigal is the best software for IS prediction. A deepen study regarding IS elements in P.aeruginosa has then been conducted, leading to the conclusion that close genomes inside this species have also a close numbers of IS families and groups.

Introduction

The number of completely sequenced bacterial and archaeal genomes are rising steadily, such an increasing makes it possible to develop novel kind of large scale approaches to understand genomes structure and evolution over time. Gene content prediction and genome comparison have both provided new important information and deciphering keys to understand evolution of prokaryotes [VSG + 11]. Important sequences in understanding rearrangement of genomes during evolution are so-called transposable elements (TEs), which are DNA fragments or segments that have the ability to insert themselves into new chromosomal locations, and often make duplicate copies of themselves during transposition process [HKN + 06]. Remark that, in bacterial reign, only cut-and-paste mechanism of transposition can be found, the transposable elements involved in such a move being the insertion sequences (ISs).

Insertion sequences range in size from 600 to more than 3000 bp. They are divided into 26 main different families in prokaryotes, as described in ISFinder1 [SPL + 06], an international reference database for bacterial and archaeal ISs that includes background information on transposons. The main function of ISFinder is to assign IS names and to produce a focal point for a coherent nomenclature for all discovered insertion sequences. This database includes over than 3500 bacterial ISs [START_REF] Burgess Hickman | Integrating prokaryotes and eukaryotes: DNA transposases in light of structure[END_REF][START_REF] Zhou | Insertion Sequences show diverse recent activities in Cyanobacteria and Archaea[END_REF]. Data come from a detection of repeated patterns, which can be easily found by using homology-based techniques [START_REF] Feschotte | Computational analysis and paleogenomics of interspersed repeats in eukaryotes[END_REF]. Classification process of families, for its part, depends on transposases homology and overall genetic organization. Indeed, most ISs consist of short inverted repeat sequences that flank one or more open reading frames (ORFs, see Figure 1), whose products encode the transposase proteins necessary for transposition process. The main problem with such approaches for ISs detection and classification is that they are obviously highly dependent on the annotations, and existing tools evoked above only use the NCBI ones, whose quality is limited and very variable.

In this research work, the authors' intention is to find an accurate method for discovering insertion sequences in prokaryotic genomes. To achieve this goal, we propose to use one of the most recent computational tool for automated annotation of insertion sequences, namely OASIS, together with the international database for all known IS sequences (ISFinder). More precisely, OASIS works with genbank files that have fully described genes functionality: this tool identifies ISs in each genome by finding conserved regions surrounding alreadyannotated transposases. Such technique makes it possible to discover new insertion sequences, even if they are not in ISFinder database. A novel pipeline that solves the dependence on NCBI annotations, and that works with any annotation tool (with or without description of gene functionality) is then proposed. The output of our pipeline contains all detected IS sequences supported with other important information like inverted repeats (IRs) sequences, lengths, positions, names of family and group, and other details that help in studying IS structures.

The contributions of this article can be summarized as follows. (1) A pipeline for insertion sequences discovery and classification is proposed, which does not depend on NCBI annotations. It uses unannotated genomes and embeds various annotation tools specific to Bacteria (such as Prokka, BASys, and Prodigal) in its process. (2) Overlapping and consensus problems that naturally appear after merging annotation methods recalled above are solved, in order to obtain large and accurate number of ISs with their names of families and groups. And finally (3) the pipeline is tested on a set of 23 complete genomes of Pseudomonas aeruginosa, and biological consequences are outlined.

Figure 1: IS element types [START_REF] Zhou | Insertion Sequences show diverse recent activities in Cyanobacteria and Archaea[END_REF] The remainder of this article is organized as follows. In Section 2, various tools for discovering IS elements in different species of Bacteria and Archaea are presented. The suggested methodology for increasing both the number and accuracy of detecting IS elements is explained in Section 3. The pipeline is detailed in Section 4, while an application example using 23 completed genomes of P. aeurigonsa is provided in Section 5. This article ends by a conclusion section, in which the contributions are summarized and intended future work is detailed.

State of the art in ISs detection or annotation

The study on the plant-pathogenic prokaryote Xanthomonas oryzae pv. oryzae (Xoo), which causes bacterial blight (one of the most important diseases of rice) was published in 2005 by Ochiai et IScan, developed by Wagner et al. [START_REF] Wagner | A survey of bacterial insertion sequences using IScan[END_REF], has then been proposed in 2007. Inverted repeats are found using smith waterman local alignments on transposase references found with BLAST and used as a local database. This tool has been applied on 438 completely sequenced bacterial genomes by using BLAST with referenced transposases, to determine which transposases are related to insertion sequences. Touchon et al., for their parts, have analyzed 262 different bacterial and archaeal genomes downloaded from GenBank NCBI in 2007 [START_REF] Touchon | Causes of insertion sequences abundance in prokaryotic genomes[END_REF]. A coding sequence has then been considered as an IS element if its BLASTP best hit in ISFinder database has an e-value lower than 10 -10 .

ISA has been created by Zhou et al. in 2008 [ZOX08]. This annotation program depends on both NCBI annotations and ISFinder. More precisely, authors manually collected 1,356 IS elements with both sequences and terminal signals from the ISFinder database, which have been used as templates for identification of all IS elements and map construction in the targeted genomes. ISA, which is not publicly available, has finally been used for an analysis of 19 cyanobacterial and 31 archaeal annotated genomes downloaded from NCBI.

In 2010, Plague et al. analyzed the neighboring gene orientations (NGOs) of all ISs in 326 fully sequenced bacterial chromosomes. They obtained primary annotations from the Comprehensive Microbial Resource database (release 1.0-20.0) at the Institute for Genomic Research2 . Their approach for extracting IS elements from these genomes was to consider that a coding sequence with a best BLASTX hit e-value lower than 10 -10 is an insertion sequence [START_REF] Gordon R Plague | Intergenic transposable elements are not randomly distributed in bacteria[END_REF]. ISsage, for its part, has been developed in 2011 by Varani et al. [VSG + 11]. They used eight different bacterial genomes downloaded from NCBI, and produced a web application pipeline that allows semiautomated annotation based on BLAST against the ISFinder database. However ISsage cannot automatically identify new insertion sequences which are not already present in ISFinder database.

A new computational tool for automated annotation of ISs has then been released in 2012 by Robinson et al. [START_REF] David G Robinson | OASIS: an automated program for global investigation of bacterial and archaeal insertion sequences[END_REF]. This tool has been called OASIS, which stands for "Optimized Annotation System for Insertion Sequences". They worked with 1,737 bacterial and archaeal genomes downloaded from NCBI. OASIS identifies ISs in each genome by finding conserved regions surrounding already-annotated transposase genes. OASIS uses a maximum likelihood algorithm to determine the edges of multicopy ISs based on conservation between their surrounding regions. For defining inverted repeats, the same strategy as IScan was used (Smith-Waterman alignment). Authors also used hierarchical agglomerative clustering to identify groups of IS lengths. The ISs set is then classified according to the family and group after a BLASTP best hit in ISFinder database with an e-value lower than 10 -12 . When a cluster cannot match with any entry of the database, the IS set is considered as new. Thus OASIS has the ability to discover new insertion sequences, that is, which cannot be found in ISFinder. Finally, in 2014, the analysis of the NGOs for all IS elements within 155 fully sequenced Archaea genomes was presented by Florek et al. [START_REF] Morgan C Florek | Insertion sequence distribution bias in Archaea[END_REF]. To do so, they have launched a BLASTP in the ISFinder, with an e-value less than or equal to 10 -10 , for all protein coding sequences downloaded from NCBI which are related to IS elements.

Two major concerns with the state of the art detailed above can be emphasized. Firstly, most of them cannot detect new insertion sequences. Secondly, all these tools are based on NCBI annotations of very relative and variable qualities -except ISsaga, which could work with other annotation tools (but it depends only on transposase ORFs that have been already defined in ISFinder). Our objective in the next section is to propose a pipeline that solves these two issues, being able to deal with unannotated genomes and to detect unknown ISs.

Prediction and Modules based on OASIS

For illustration purpose, the proposed pipeline system for IS elements prediction will be presented using 23 complete genomes of P. aeruginosa available on the NCBI website, RefSeq and INCDS/Genebank databases, see Table 1 (RefSeq genomes were prefered when available). The prediction of IS elements in the proposed pipeline depends on both OASIS [START_REF] David G Robinson | OASIS: an automated program for global investigation of bacterial and archaeal insertion sequences[END_REF] and ISFinder [SPL + 06].

Prediction of IS elements from Pseudomonas aeruginosa

OASIS is used in this pipeline for predicting insertion sequences in prokaryotic genomes. This latter detects ISs in each genome by finding conserved regions surrounding already-annotated transposase genes, which are identified by the word transposase in the "product" field of the GenBank file. Obviously OASIS highly depends on the quality of annotations [START_REF] David G Robinson | OASIS: an automated program for global investigation of bacterial and archaeal insertion sequences[END_REF], while to determine whether a given gene is a transposase or not is a very difficult task (indeed transposases are among the most abundant and ubiquitous genes in nature [START_REF] Ramy K Aziz | Transposases are the most abundant, most ubiquitous genes in nature[END_REF], and they are widely separated in Prokaryote genomes). OASIS deals with files having genbank format. It takes them as input and then produces two output files for each provided genome. The first one is a fasta file that contains all IS nucleotide sequences, with start and end positions. It also contains the amino acid sequence for each ORF. The second file is a summary table providing attributes that describe the insertion sequence: set-id, family, group, IS positions, inverted repeat left (IRL) and right (IRR), and orientation. Remark that most of these information are in the ISFinder database too. Indeed OASIS find them alone but it extracts family names and group from ISFinder.

The main problem found in OASIS is solved in the proposed pipeline by using different types of annotations: NCBI will not be used alone, and gene functionality taken from annotation tools will either or not be used depending on the situation. Finally, transposases within IS will be verified using ISFinder database. OASIS can thus be used in two different ways in our pipeline, depending on the provided genbank file. These two modules have been named NOASIS, which uses the original input genbank genome file provided by the NCBI (as it is, without any modification), and DOASIS, which deals with modified genbank files that have been updated to obtain more accurate results than NOASIS. These modules are described thereafter.

Normal OASIS (NOASIS)

For finding predicted IS in NOASIS module, we simply applied OASIS on the input set of genomes with their NCBI annotations, that is, with the original downloaded genbank file. Using the reference genome named PAO1, the summary outputted by the pipeline is given in Tables 2 and3. In these NOASIS tables, the summary produced by OASIS is enriched with new features described below:

• Real IS IS sequences that have best match (first hit) when using BLASTN with ISFinder database, an e-value equal to 0.0, and with a functionality of each ORF within the IS recognized as a transposase.

• Partial IS Sequences that match part of known IS from ISFinder (i.e., have e-value lower than 10 -10 ) and have also a transposase gene functionality for the ORFs.

• Putative New IS Sequences with bad score after making a BLASTN with ISFinder, but with a transposase. They may be real insertion sequences not already added in ISFinder database or false positives, requiring human curation.

Applying this slightly improved version of OASIS in the 23 genomes of Pseudomonas leads to a major issue: surprisingly, NOASIS found no real insertion sequences in some genomes like PACS2 or SCV20265. The problem is that OASIS find multiple copies of IS elements in each genome by identifying conserved regions surrounding transposase genes. However some of the considered genomes either have no information about transposase gene into their feature genbank tables or have simply no feature table in their genbank format files. This issue is at the basis of our improved module called DOASIS, which is explained below.

For the sake of comparison, Figure 2 contains similar results for Mycobacterium tuberculosis genus. The main idea for DOASIS module is that information about transposases within genbank files are potentially incorrect (i.e., may all be false positives). So we simply decide to remove all transposase words in the product fields from all inputted genomes. We thus update these information as follows.

Step 1: genbank update. Inputted genbank files are modified following one of the three methods below.

1. All-Tpase: we consider that all the genes may potentially be a transposase. So all product fields are set to "transposase".

2. Zigzag Odd: we suggest that genes in odd positions are putative transposases and we update the genbank file adequately. Oddly, this new path will produce new candidates which are not detected during All-Tpase.

3. Zigzag Even: similar to Zigzag Odd, but on even positions.

We checked also a randomized method (i.e., by putting "transposase" in randomly picked genes). However we found poorer number of predictive real ISs or new real ISs compared with the three methods previously presented. For these reasons, we will not further investigate the randomized method.

Figure 3: Comparison of predicted ISs between randomization method and all/odd/even methods.

Step 2. We apply OASIS three times (i.e., one time per method) on all genomes, and then we take the output fasta file that contains both nucleotides and amino acids sequences for each IS element.

Step 3. A BLASTN with ISFinder is applied on each IS sequence. If the e-value of the first hit is 0.0, then the ORF within this IS belongs to known (Real) IS already existing in the ISFinder database. Else, if the e-value is lower than 10 -10 , then we found a Partial IS.

Step 4. Collect all Real IS from previous three methods (ALL Tpase, Zigzag odd, and Zigzag even) and then remove overlaps among them. Finally, produce best Real IS with all information. Remark that the problem of finding consensus and overlaps can be treated as a lexical parsing problem.

The Proposed Pipeline

It is now possible to describe the proposed pipeline that can use the two modules detailed in the previous section. This pipeline, depicted in Figure 4, will increase the number of Real IS detected on the set of P.aeruginosa genomes under consideration (indeed, the detection is improved in all categories of insertion sequences, but we only focus on Real IS in the remainder of this article, for the sake of concision). Its steps are detailed in what follows.

Figure 4: The proposed pipeline

Step 1: ORF identification. Our pipeline is currently compatible with any type of annotation tools, having either functionality capability or not, but for comparison we only focus in this article on the following tools: BASys, Prokka, and Prodigal. BASys (Bacterial Annotation System) is a web server that performs automated, in-depth annotation of bacterial genomic (chromosomal and plasmid) sequences. It uses more than 30 programs to determine nearly 60 annotation subfields for each gene. Remark that genomes must be sent online manually, and that some curation stage may be required to remove some DNA ambiguity on returned genbank files.

Prokka (rapid prokaryotic genome annotation), for its part, is a classical command line software for fully annotating draft bacterial genomes, producing standards-compliant output files for further analysis [START_REF] Seemann | Prokka: rapid prokaryotic genome annotation[END_REF]. Step 2: IS Prediction. The second stage of the pipeline consists in using either NOASIS or DOASIS for predicting IS elements. Notice that NOASIS cannot be used with Prodigal, as this module requires information about gene functionality (both NOASIS and DOASIS can be use with Prokka and BASys annotations).

The improvement in real IS discovery is obvious, illustrating the low quality and inadequacy of NCBI annotations for studying insertion sequences in bacterial genomes, and the improvements when using our pipeline. This chart shows too that a zigzag path in the annotation can oddly improve the detection of insertion sequences.

The prediction of real ISs is based on finding conserved regions (i.e., inverted repeats (IRs)) surrounded by transposase genes. Some ISs have been lost in All Tpase, for the following reason: when we suggested that all genes are transposases, OASIS found predicted ISs that consist of large sets of transposases surrounded by IR in their left and right boundaries. But when these predicted ISs have been verified using ISFinder database, we did not find any good match. Contrarily, in Zigzag methods, good matches have been found (real ISs), because many of these elements consist of one or two transposase genes flanked by IRs. These results are listed with detail in Table 4 using BASys annotation tools. We can thus wonder if the source of a wrong prediction of real IS is due to a wrong coding sequence prediction, or to functionality errors. Switching between NOASIS and DOASIS allows us to answer this question. We can conclude from Table 5 that (1) annotation errors are more frequent on NCBI, while Prokka annotates well the sequences related to ISs (see NOASIS columns), and that (2) both NCBI and Prokka have a better coding sequence prediction than BASys, at least when considering sequences involved in IS elements (see DOASIS columns and the correlation line). More precisely, the correlation is based on the number of predicted real IS elements between NOASIS and DOASIS. Prodigal has been studied separately, as it does not provide genes functionality. The number of Real ISs per genome returned by our pipeline using prodigal is given in Figure 7. As shown in Table 6, the quality of coding sequences predicted with prodigal compared with other annotation tools allows us to discover the best number of real ISs. In particular, we have improved a lot of results produced by OASIS and ISFinder on NCBI annotations, which is usually used in the literature that focuses on bacterial insertion sequences. Furthermore, this table illustrates a certain sensitivity of coding sequence prediction tools with functionality annotation capabilities to detect ISs in some specific genomes like PA7. Indeed we discovered, during other studies we realized on this set of Pseudomonas strains, that PA7 has a lot of specific genes, that is, which are not in the core genome of all Pseudomonases, which may explain such a sensitivity.

Conclusion

Insertion sequences of bacterial genomes are usually studied using OASIS and ISFinder on NCBI annotations. We have shown in this article that a pipeline can be designed to improve the accuracy of IS detection and classification by improving the coding sequence prediction stage, and by considering a priori each sequence as a transposase.

The source code for this pipeline can be download from the link 3 . A comparison has been conducted on a set of Pseudomonas aeruginosa, showing an obvious improvement in the detection of insertion sequences for some particular configurations of our pipeline.

In future work, we intend to enlarge the number of coding sequence and functionality prediction tools and to merge all the Real IS results in order to improve again the accuracy of our pipeline. We will then focus on the impact of IS elements in P.aeruginosa evolution, comparing the phylogenetic tree of strains of this species with a phylogeny of their insertion sequences. Insertion events will then be investigated, and related to genomes rearrangements found in this collection of strains. We will finally enlarge our pipeline to eukariotic genomes and to other kind of transposable elements.

Figure 2 :

 2 Figure 2: IS elements detect in 28 Mycobacterium tuberculosis

Figure 5 :

 5 Figure 5: Comparison between Prokka, BASys, and NCBI functionality annotations

Figure 6 :

 6 Figure 6: NOASIS (NCBI annotation) versus DOASIS

Figure 7 :

 7 Figure 7: Real ISs found by our pipeline using Prodigal

  al. [OIT + 05]. They used GeneHacker [YH96], GenomeGambler version 1.51, and Glimmer program [DHK + 99] for coding sequence prediction. Insertion sequences were finally classified by a BLAST analysis using ISFinder database evoked previously.

Table 1 :

 1 Input set of 23 complete genomes of P. aeruginosa

			INSDC(Genbank)	Refseqs	Input Cenomes
	Index	GenomeName	GID	GID	GID	Accession no.
	1	PACS2	106896550		106896550	AAQW01000001.1
	2	PAO1	110227054	110645304 110645304	NC 002516.2
	3	UCBPP-PA14	115583796	116048575 116048575	NC 008463.1
	4	PA7	150958624	152983466 152983466	NC 009656.1
	5	19BR	343788106	485462089 485462089 NZ AFXJ01000001.1
	6	213BR	343788107	485462091 485462091 NZ AFXK01000001.1
	7	M18	347302377	386056071 386056071	NC 017549.1
	8	DK2	392316915	392981410 392981410	NC 018080.1
	9	B136-33	477548288	478476202 478476202	NC 020912.1
	10	RP73	514245605	514407635 514407635	NC 021577.1
	11	c7447m	543873856		543873856	CP006728
	12	PAO581	543879514		543879514	CP006705
	13	PAO1-VE2	553886202		553886202	CP006831
	14	PAO1-VE13	553895034		553895034	CP006832
	15	PA1	557703951	558672313 558672313	NC 022808.1
	16	PA1R	557709751	558665962 558665962	NC 022806.1
	17	MTB-1	563408818	564949884 564949884	NC 023019.1
	18	LES431	566561164	568151185 568151185	NC 023066
	19	SCV20265	567363169	568306739 568306739	NC 023149
	20	LESB58		218888746 218888746	NC 011770.1
	21	NCGM2.S1		386062973 386062973	NC 017549.1
	22	PA38182	575870901		575870901	HG530068.1
	23	YL84	576902775		576902775	CP007147.1

Table 4 :

 4 BASys annotation using NOASIS and DOASIS

	BASys		Normal All Transpos Zigzag Odd Zigzag Even (All T/odd/even)
	Name	Genome	Real IS	Real IS	Real IS	Real IS	Best Real
	PACS2	106896550	2	1	2	0	2
	PAO1	110645304	9	6	0	0	6
	UCBPP-PA14 116048575	3	8	8	1	8
	PA7	152983466	13	0	0	0	0
	LESB58	218888746	2	3	5	2	6
	M18	386056071	1	2	2	1	2
	NCGM2.S1	386062973	15	0	12	0	12
	DK2	392981410	8	9	10	8	11
	B136-33	478476202	3	5	3	3	5
	19BR	485462089	5	0	0	10	10
	213BR	485462091	5	4	4	4	4
	RP73	514407635	4	5	5	2	5
	c7447m	543873856	9	0	9	9	10
	PAO581	543879514	9	6	8	0	8
	PAO1-VE2	553886202	8	6	9	6	9
	PAO1-VE13	553895034	8	6	8	8	8
	PA1R	558665962	4	4	4	5	5
	PA1	558672313	5	5	5	6	6
	MTB-1	564949884	0	1	0	1	1
	LES431	568151185	5	14	13	8	14
	SCV20265	568306739	5	14	13	8	14
	PA38182	575870901	1	3	1	2	4
	YL84	576902775	7	7	7	7	7
			131	109	128	91	157

Table 5 :

 5 Correlation table for different annotation tools

		NCBI		BASys		Prokka
		NOASIS DOASIS NOASIS DOASIS NOASIS DOASIS
	Number of Real IS	110	169	131	157	169	176
	Correlations	0.3985580752	0.357346472	0.926355615

Table 6 :

 6 Final comparison using our pipeline

		NCBI	BASys	Prokka	Prodigal		NCBI	BASys	Prokka	Prodigal
	Name	DOASIS DOASIS DOASIS DOASIS	Name	DOASIS DOASIS DOASIS DOASIS
	PACS2	0	2	2	3	c7447m	10	10	10	12
	PAO1	10	6	10	12	PAO581	10	8	10	8
	UCBPP-PA14	4	8	4	8	PAO1-VE2	10	9	10	9
	PA7	15	0	14	18	PAO1-VE13	10	8	10	9
	LESB58	3	6	3	6	PA1R	4	5	4	5
	M18	3	2	3	3	PA1	5	6	5	6
	NCGM2.S1	11	12	19	14	MTB-1	1	1	1	2
	DK2	12	11	13	17	LES431	6	14	6	6
	B136-33	5	5	5	7	SCV20265	15	14	15	15
	19BR	8	10	5	11	PA38182	7	4	7	7
	213BR	8	4	8	10	YL84	7	7	7	8
	RP73	5	5	5	5	Total IS	84	71	91	114

www-is.biotoul.fr

http://cmr.tigr.org/tigr-scripts/CMR/CmrHomePage.cgi

http://members.femto-st.fr/christophe-guyeux/en/insertion-sequences

Step 3: IS Validation. This step is realized by launching BLASTN on each predicted IS sequence with ISFinder.

The e-value of the first hit is then checked: if it is 0.0, then the ORF within this sequence is a Real IS known by ISFinder. As described previously, it will be considered as Partial IS if its e-value is lower than 10 -10 . Both IS names of family and group are returned too.

Results and Discussion

We can firstly remark in Figure 5 that, using either Prokka or BASys for genes detection and functionality prediction is better than taking directly the annotated genomes from NCBI: a larger number of Real IS can be found. Additionally, this comparison shows that Prokka outperforms BASys in 3 families of ISs (namely: IS3, IS30, and ISNCY), while BASys seems better for detecting insertion sequences belonging in the IS5, IS1182, and TN3 families. This variability may be explained by the fact that functionality annotations of these tools depend probably on IS families that where known when these tools have been released. The effects of DOASIS module compared to single OASIS on annotated NCBI genomes are depicted in Figure 6.


Mohamed Lehsaini
email: m_lehsaini@mail.univ-tlemcen.dz

Herve Guyennet
email: herve.guyennet@femto-st.fr

Checkpoint-based Fault-tolerance for LEACH Protocol

Keywords: LEACH, Checkpoint approach, Realistic environment, Fault-tolerance, WSN. I

Most routing protocols designed for wireless sensor networks provide good results in ideal environments. However, their performance degrades dramatically when nodes stop working for various causes such as loss of energy, crushed by animal or climatic conditions. In this paper, we highlight the weaknesses of LEACH (Low Energy Adaptive Clustering Hierarchy) protocol by evaluating its performance. Then we propose an improved version of this protocol based on checkpoint approach that allows it to become a fault-tolerant protocol. Finally, several simulations were conducted to illustrate the benefits of our contribution.

INTRODUCTION

Wireless sensor networks (WSN) consist of a large number of low-cost and low-powered devices that can sense, compute, and communicate with other devices for the purpose of gathering local information to make global decision about a physical environment [START_REF] Olariu | Information Assurance in Wireless sensor networks[END_REF]. Sensors can be deployed over a geographical area for monitoring physical phenomena like temperature, humidity, vibrations, seismic events, early fire detection, density of air pollutants and so on [START_REF] Haosong | Distributed Bottleneck Node Detection in Wireless Sensor Networks[END_REF][START_REF] Woo | Taming the underlying challenges of reliable multihop routing in sensor networks[END_REF].

WSN should have a long lifetime to accomplish the application requirements. However, In addition to resource constraints in WSN, the failure of sensor nodes is almost unavoidable due to energy depletion since they have been usually deployed in hostile environments and their batteries cannot be recharged or replaced, hardware failure, communication link errors, and so on [START_REF] Woo | Taming the underlying challenges of reliable multihop routing in sensor networks[END_REF][START_REF] Paradis | A Survey of Fault Management in Wireless Sensor Networks[END_REF][START_REF] Ammari | Fault tolerance measures for large-scale wireless sensor networks[END_REF]. Therefore, in some WSN applications, fault-tolerance has become as important issue than other performance metrics such as energy efficiency, latency and accuracy.

Generally, the consequence of these failures is that a node becomes unreachable, violates certain conditions that are essential for providing a service or returns false readings that could cause a disaster especially in critical applications. Furthermore, the above fault scenarios are worsened by the multihop communication nature of WSN. It often takes several hops to deliver data from a source node to a remote base station. Thus, failure of a single node or link may lead to missing reports from the entire region of WSN.

Therefore, since sensors are prone to failure, faulttolerance should be seriously considered in many sensing applications which are generally required to be fault-tolerant, where any pair of sensors is usually connected by multiple communication paths. Recently, several studies have dealt with fault-tolerance in WSN, particularly in the routing process. Moreover, these works focus on the detection and recovery of failures in WSN.

In this paper we propose to evaluate the routing protocol LEACH in a realistic environment in which sensor nodes can fail and links may be lost. Then, we propose an improved version of LEACH called FT-LEACH (Fault-Tolerant LEACH). In this proposed version, we use checkpoint approach to tolerate failures so that LEACH becomes a faulttolerant protocol. Furthermore, in the FT-LEACH, clusterheads aggregate data to reduce extra costs by sending only one copy of sensed data to the sink.

FT-LEACH could tolerate failures of links and therefore guarantee routing reliability in WSN while dissipating less extra energy. To illustrate the performance of FT-LEACH we conducted several simulations and we compared obtained results with those of LEACH [START_REF] Heinzelman | Energy-efficient communication protocol for wireless microsensor networks[END_REF] in a realist environment.

The rest of this paper is organized as follows: Section 2 describes the model parameters used; in Section 3, we present briefly the protocol LEACH; Section 4 is an improved version of LEACH; Section 5 illustrates performance analysis of LEACH and FT-LEACH in a realistic environment. Finally, we conclude our paper and discuss future research work in Section 6.

II. MODEL PARAMETERS

Before heading into the technical details of our contribution, we first give some definitions and notations that will be used in our paper later.

A wireless sensor network is represented by an undirected graph G=(V,E), where V represents the set of sensor nodes and E⊆V 2 is the set of edges that gives the available communications: an edge e=(u,v) belongs to E if and only if the node u is physically able to transmit messages to v and vice-versa. At each sensor node u∈V is assigned a unique value to be used as an identifier, so that the identifier of u is denoted by Node Id (u).

The 1-density of a node u represents the ratio between the number of links in its 1-neighborhood (links between u and its neighbors and links between two 1-neighbors of u) and the 1degree of u δ 1 (u), denoted by ρ 1 (u). It is expressed by the following formula:

( ) ( ) [ ] ( ) u u N w v E w v u 1 1 1 , , δ ρ ∈ ∈ = (1)
Where N 1 [u] is the 1-neighborhood set of u (the nodes that are located not more than two hops from the node u) and δ 1 (u) is the 1-degree of u (the size of N 1 (u)).

In this paper, we assume that the sensors are randomly distributed in a two-dimensional Euclidean plane P. Each sensor has an omni-directional antenna which allows it to reach with a single transmission all nodes within its vicinity and we consider that sensors have 1-hop positional information. We also assume that each sensor has a generic weight and it is able to calculate it. This weight represents the fitness of each node to be a cluster-head.

III. PRESENTATION OF LEACH PROTOCOL

LEACH [START_REF] Heinzelman | Energy-efficient communication protocol for wireless microsensor networks[END_REF][START_REF] Heinzelman | An application-specific protocol architecture for wireless microsensor networks[END_REF] is a hierarchical cluster-based routing protocol for wireless sensor networks which partitions the nodes into clusters. In each cluster a dedicated node called cluster-head (CH) and other nodes are cluster members. CH is responsible for creating and manipulating a TDMA schedule and sending aggregated data from nodes to a remote base station using CDMA technique to avoid interference. Moreover, this protocol runs into several rounds and each round consists of two phases:

A. Setup Phase

During this phase, cluster formation takes place. In which, each sensor node decides independently of other nodes if it will become a CH or not. This decision takes into account if the node is served as a CH for the last time i.e. the node that has not been a CH for long time is more likely to elect itself as a CH.

Once CHs are elected, they inform their neighborhood using an advertisement packet that they become CHs. Each non-CH node picks the advertisement packet with the strongest received signal strength, sends the message "Join Packet" to request its corresponding CH to join it.

After this process, the CH knows the number of member nodes and their IDs. Based on all messages received within the cluster, the CH creates a TDMA schedule and broadcasts it to its cluster members. Then, it picks a CSMA code randomly to avoid interference when transmitting data to the base station.

B. Steady-state phase

During this phase, sensor nodes begin to send their data collected during their allocated TDMA slot to their respective CHs. The radio of each non-CH node can be turned off until the nodes allocated TDMA slot, thus energy dissipation is minimized for these nodes. When all collected data have been received, the corresponding CH aggregates these data and sends them to the remote base station as presented by figure 1.

Fig. 1. Cluster formation in LEACH

LEACH is able to perform local aggregation of data in each cluster to reduce the amount of data transmitted to the base station. Although LEACH provides good results for WSN, it presents some drawbacks such as:

• CH selection does not take into account residual energy of nodes. Hence, it is probable that during a period there are some CHs with a small amount of energy. Thus, the latter could quickly deplete their batteries and consequently they stop working and cause holes in the target area.

• It cannot cover a large area when some sensor nodes fail.

To the best our knowledge there is no work dealing with faulttolerance in LEACH. In this context, we propose an enhanced version of LEACH called FT-LEACH so that it becomes a fault-tolerant protocol.

IV. CHECKPOINT-BASED APPROACH

In most routing protocols, fault-tolerance has not been taken into consideration especially for LEACH protocol. In this context, we propose an enhanced version of LEACH protocol based on checkpoint approach so that LEACH becomes a fault-tolerant protocol.

The checkpoint approach is one of the most popular technique to provide fault-tolerance on unreliable and distributed systems [START_REF] Garg | Fault Tolerance in Grid Computing: State of the Art and open issues[END_REF]. It is a record of the snapshot of the whole network state in order to restart the application after the occurrence of some crash. The checkpoint can be stored on temporary as well as stable storage. However, the efficiency of this approach is strongly dependent on the length of the checkpointing period. Frequent checkpointing may enhance the overhead, while lazy checkpointing may lead to loss of significant computation. Hence, the decision about the size of the checkpointing interval and the checkpointing technique is a complicated task and should be based upon the knowledge about the application as well as the system [START_REF] Gokuldev | A New Checkpoint Approach for Fault Tolerance in Grid[END_REF]. Moreover, the checkpoint approaches present some limitations. They need stable storage to save a global consistent state periodically.

In this context, we use the base station to store availability information about cluster-heads. Each cluster-head sends periodically a message to the base station. If during a period, the base station does not receive a message from a clusterhead, it considers it as a defective node. As a result, the base station transmits a message to the cluster members concerned to elect a novel cluster-head among them. The member which has the greatest weight based on its remaining energy and its 1-density parameter as presented in Equation ( 2), becomes cluster-head during the remaining time of the current period.

Weight(s) = ½ Energy(s) + ½ density(s)

(2)

V. EVALUATION AND SIMULATION RESULTS

In our experiments, we conducted extensive simulations to evaluate the performance of FT-LEACH and compare them with LEACH in terms respectively of the ratio of successful reception at the base station during the network's lifetime and energy consumption. To achieve these goals, the simulations have been performed in NS-2 [START_REF]Network Simulator, World Wide Web[END_REF] using the MIT_uAMPS [11]. We have carried out these simulations with the same scenario presented in LEACH [START_REF] Heinzelman | An application-specific protocol architecture for wireless microsensor networks[END_REF] in order to illustrate the performance of our contribution. Hence, we considered a network topology with 100 non-mobile sensor nodes with a sensing range of 25 meters. Sensor nodes are placed randomly in a 100 m × 100 m square area by using an uniform distribution function, and the remote base station is located at position x = 50, y = 175, i.e. the base station was placed 75 meters outside the area where the sensor nodes were deployed. At the beginning of the simulation, all the sensor nodes had an equal amount of energy i.e. the sensor nodes started with 2 Joules of energy. Simulation parameters are presented in Table 1. Moreover, we note that system lifetime is defined as the time when last sensor dies in the sensor network.

The simulations were performed until all the sensors in the network consumed their energy and the average values were calculated after each round whose duration is 20 seconds. This duration represents the cluster timeout. It is used to prolong network lifetime and balance energy deviation among all its sensors. On expiry of this period, cluster-head's election process is triggered again. Moreover, we used the same energy parameters and radio model as discussed in [START_REF] Heinzelman | An application-specific protocol architecture for wireless microsensor networks[END_REF], wherein energy consumption is mainly divided into two parts: receiving and transmitting messages. The transmission energy consumption requires additional energy to amplify the signal according to the distance from the destination. Thus, to transmit a k-bit message to a distance d, the radio expends energy (E Tx ) as described by the formula [START_REF] Woo | Taming the underlying challenges of reliable multihop routing in sensor networks[END_REF], where ε elec is the energy consumed for radio electronics, ε friss-amp and ε two-ray-amp for an amplifier. The reception energy consumption is E Rx = ε elec × k. Fig. 3 shows that the ratio of successfully received packets to the base station is higher than in LEACH because in LEACH, if a cluster-head stops working information will not be forwarded to the base station while in our contribution if the cluster-head is down the cluster-head election process would be triggered and the elected cluster-head transmits the information to the base station. 4 illustrates that in our contribution, the amount of packets received at the base station during network lifetime is higher than in LEACH because in LEACH, if a cluster-head stops working information will not be forwarded to the base station and hence the energy will be lost without sending information. Furthermore, in our contribution if the cluster-head is down the cluster-head election process would be triggered and the elected sensor node transmits the information to the base station and hence the energy consumed reflects a transmission. The evaluation of LEACH in a realistic environment showed that LEACH loses performance when some nodes fail. In this context, we have proposed an enhanced version of LEACH so it becomes a fault-tolerant protocol.

Simulation results showed that our contribution has improved the performance of LEACH in terms of number of packets successfully received at the base station and energy consumption.

3 )

 3 Simulated model parameters are set as shown in

Fig. 2 .

 2 Fig. 2. Ratio of successful reception with different failure rates

Fig.

  Fig.4illustrates that in our contribution, the amount of packets received at the base station during network lifetime is higher than in LEACH because in LEACH, if a cluster-head stops working information will not be forwarded to the base station and hence the energy will be lost without sending information. Furthermore, in our contribution if the cluster-

Fig. 3 .

 3 Fig. 3. Amount of packets received at the sink during network lifetime VI. CONCLUSION

Table 2 .

 2 The data size were 500 bytes/message plus a header of 25 bytes. The message size to be transmitted was:

	k	=	( 500	bytes	+	25	bytes	)	×	8	=	4200	bits

Table 1 .

 1 Model Parameters

	Parameter	Value
	Network grid	(0,0) x (100,100)
	Base Station	(50,175)
	εelec	50 nJ/bit
	εfriss-amp	10 pJ/bit
	εtwo-ray-amp	0.0013 pJ/bit
	dCrossover	87 m
	Data packet size	500 bytes
	Packet Header size	25 bytes
	Intial energy per node	2 J
	Number of nodes (N)	100