Ludovic Hablot
email: ludovic.hablot@ens-lyon.fr

Olivier Glück

Jean-Christophe Mignot

Stéphane Genaud

Vicat-Blanc Pascale

Primet

Comparison and tuning of MPI implementations in a grid context

Today, clusters are often interconnected by long distance networks to compose grids and to provide users with a huge number of available ressources. To write parallel applications, developers are generally using the standard communication library MPI, which has been optimized for clusters. However, two main features of grids -long distance networks and technological heterogeneity -raise the question of MPI efficiency in grids.

This paper presents an evaluation and tuning of four recent MPI implementations (MPICH2, MPICH-Madeleine, OpenMPI and YAMPII) in a research grid: Grid'5000. The comparison is based on the execution of pingpong and NAS Parallel Benchmarks. We show that these implementations present several performance differences. We show that YAMPII performs better results than the others. But we argue that executing MPI applications on a grid can be beneficial if some specific parameters are well tuned. The paper details, for each implementation, the tuning leading the best performances.

I. INTRODUCTION

Today, clusters are often interconnected by long distance networks within grids to provide users with a huge number of available ressources.

Users want to execute their applications, written for clusters, on grids to get better performance by simply using more resources. For example, geophysical applications like ray2mesh [START_REF] Genaud | Experiments in running a scientific MPI application on Grid'5000[END_REF], a seismic ray tracing in a 3D mesh of the Earth, or medical applications like Simri [START_REF] Benoit-Cattin | Magnetic Resonance Imaging (MRI) simulation on a grid computing architecture[END_REF], a 3D Magnetic Resonance Imaging (MRI) simulator, have been executed on grids with quite success and but generally with a sublinear speedup. Indeed, MPI, the standard communication library used to write such parallel applications has been initially implemented and optimized for clusters. Most of implementations used in grids do not consider the specificities of grid interconnections, leading to suboptimal performance.

The grid raises mainly three problems to execute MPI applications. First, MPI implementations have to manage efficiently the long-distance between sites. Actually, the high latency between sites is very costly, especially for little messages. Inter-sites communications take more time than intra-sites ones. On an other hand, inter-sites links may offer higher capacities than cluster links.

Secondly, MPI implementations have to manage heterogeneity of the different high speed networks composing the grids. Intra-site communications like for example, through a Myrinet interconnect and an Infiniband cluster on the same site and also inter-sites communications through a WAN (Wide Area Network) have to interoperate.

Finally, the CPUs heterogeneity has an impact on the overall application performance execution. Indeed, it could be of interest to take into account this heterogeneity in the task placement phase. We do not address these two last problems here. In our experiments, all the communications use TCP and homogeneous CPU architectures.

We consider here several MPI implementations taking some grid characteristics into account to improve the execution of MPI applications in these environments. The MPICH2 [START_REF] Gropp | MPICH2: A New Start for MPI Implementations[END_REF], GridMPI [START_REF]GridMPI Project[END_REF], MPICH-Madeleine [START_REF] Aumage | MPICH/MADIII : a Cluster of Clusters Enabled MPI Implementation[END_REF], OpenMPI [START_REF] Gabriel | Open MPI: Goals, Concept, and Design of a Next Generation MPI Implementation[END_REF] implementations can be used on a grid but are not similarly optimized to this specific context. The goal of this paper is to identify which are efficient on a real grid and in which conditions. An other question is to define how to configure these implementations to achieve the best performance on the grid. Finally, it could be usefull to have a better view of which communication patterns better fits grid context. To answer these questions, we conduct experiments in Grid'5000 [START_REF] Bolze | Grid'5000: a large scale and highly reconfigurable experimental grid testbed[END_REF] a french research grid platform gathering more than 3000 processors. Nine sites are connected by a dedicated WAN at 1 or 10 Gbps. This architecture provides a fully reconfigurability feature to dynamically deploy and configure any OS on any host.

This paper is organised as follows. Section II presents a state of the art of MPI implementations usable in a grid context. In Section III, we describe the experimental protocol. Section IV presents the results of our experiments and the necessary optimizations required to achieve good performances. Finally, we conclude and present future work.

II. MPI IMPLEMENTATIONS FOR THE GRID

This section presents the following implementations that improve either network heterogeneity or long-distance communications: GridMPI, OpenMPI, MPICH-Madeleine. We first describe MPICH2 because it is a largely used implementation. Moreover, a lot of MPI implementations are based on it.

1) MPICH2 [START_REF] Gropp | MPICH2: A New Start for MPI Implementations[END_REF]: This implementation is the successor of MPICH [START_REF] Gropp | High-performance, portable implementation of the MPI Message Passing Interface Standard[END_REF], used by a lot of people. It is not a grid implementation but could be used in a grid if all the communications use TCP. It has a four layered architecture which could be quite easily modified. Results with this implementation are well-known that is why we use it as a reference in our tests.

2) MPICH-Madeleine [START_REF] Aumage | MPICH/MADIII : a Cluster of Clusters Enabled MPI Implementation[END_REF]: This implementation is based both on MPICH [START_REF] Gropp | High-performance, portable implementation of the MPI Message Passing Interface Standard[END_REF] and Madeleine [START_REF] Aumage | Heterogeneous multi-cluster networking with the Madeleine III communication library[END_REF], a communication library which allows communications between several commonly used high speed networks. Thus, MPICH-Madeleine supports efficiently networks heterogeneity between TCP, SCI, VIA, Myrinet MX/GM and Quadrics. MPICH-Madeleine uses a gateway between two clusters interconnected by different networks. For example, if you have a cluster A using Myrinet, a cluster B using SCI and a node shared by the two clusters, messages can be sent between them directly through Madeleine and without using TCP. It can be used in a grid context using TCP for long-distance communications.

3) OpenMPI [START_REF] Gabriel | Open MPI: Goals, Concept, and Design of a Next Generation MPI Implementation[END_REF]: OpenMPI is an open source MPI-2 compliant implementation built from scratch combining strong points and resources from earlier projects as well as new concepts.

In the OpenMPI library, progression of communications is handled by the PML (Point-to-point Management Layer) module. This module can use different BTL (Byte Transfer Layer), one for each protocol, hence providing network heterogeneity. Supported protocols are TCP, Myrinet MX/GM, Infiniband OpenIB/mVAPI. Long distance networks characteristics are not particularly taken into account.

The OpenMPI library automatically handles grid specific configurations. For example, clusters portals and cluster specific network fabrics are automatically detected. Nevertheless, specific tunings are still required to achieve optimal performance of long and fast networks of clusters in most cases.

4) GridMPI [START_REF]GridMPI Project[END_REF]: This implementation is specifically designed to be executed in a grid environnement. There is two parts in GridMPI: one dedicated to communications, named YAMPII and the other part is the implementation of IMPI (Interoperable MPI) protocol to handle the heterogeneIty. YAMPII is a communication library. IMPI is an overlay over other MPI implementations. Each cluster could use a dedicated VendorMPI to exploit available high speed interconnects and GridMPI is doing the link between them using IMPI. GridMPI has been designed to optimize long-distance communications in MPI applications. Modifications are done at two levels, in the TCP layer and in MPI collective communications level. First, at start time, GridMPI designers propose to modify TCP as follow:

• adding pacing mechanism to avoid burst effects • reducing RTO (Retransmit Timeout) • using two different congestion window sizes for collective and point-to-point communications • bypassing the socket layer From our knowledge, the public distribution of GridMPI, provides only the pacing mechanism.

Secondly, YAMPII integrates modifications of algorithms for collective operations (see [START_REF] Matsuda | Efficient MPI Collective Operations for Clusters in Long-and-Fast Networks[END_REF]): in a grid context, communications between clusters have a higher bandwidth than intra-cluster once. YAMPII uses a modified MPI Bcast and MPI Allreduce functions to take this into account. These improvements have not been released yet.

5) Synthesis: Table I summarizes the main features of each MPI implementation. Two of these implementations can manage network heterogeneity efficiently using gateways (MPICH -Madeleine and OpenMPI). For GridMPI , the management of the heterogeneity is done using IMPI and an appropriate VendorMPI. This may introduce a large overhead in latency. For long-distance communications, the optimizations are done at two levels. First, YAMPII optimize some collective operations to be efficient on the grid. Secondly, it modifies the TCP behavior to adapt it to the high long-distance latency.

We choose MPICH2 as a reference, and YAMPII for its optimizations on long distance communications. Finally, our study is based on these four implementations: MPICH2, YAMPII, MPICH-Madeleine and OpenMPI.

Some works have been done to compare features of MPI implementations. In [START_REF] Müller | Grid enabled MPI solutions for Clusters[END_REF], the authors compare different methods used in MPI implementations (PACX-MPI, MPICH-G2, Stampi and MagPIe) to communicate between a private and a public network. Performance measurement aims at evaluating these different approaches. MPI experiments are done with PACX-MPI. They do not compare the performances of each MPI implementations together.

III. EXPERIMENTAL PROTOCOL

A. Goals and Methodology

There are two main goals of our experiments. First, we want to execute different MPI implementations in a real grid context and to see their efficiency on the Grid'5000 grid platform. Then, we want to study the advantages of executing real MPI applications on the grid instead of a cluster.

To compare the different implementations, we run between two sites of the grid a simple MPI pingpong with the default configuration of each implementation. We compare the results obtained to those obtained between two nodes on the same cluster. We have also run a TCP pingpong to evaluate the MPI overhead of each implementation.

Since the MPI pingpong can not represent the behavior of real applications, we also run experiments with the NPB (NAS Parallel Benchmarks [START_REF] Bailey | The NAS Parallel Benchmarks[END_REF]).

Pingpong is our own program. One processus sends MPI messages with the MPI Send primitive to another one which does a MPI Recv and sends the message back. The size of the messages range from one byte to 64 MBytes. For each size, we obtain the round-trip latency. Then, we can plot the MPI bandwidth available between the two nodes.

The NPB are a set of eight programs (BT, CG, EP, FT, IS, LU, MG and SP) that gives a good panel of the different parallel applications that could be executed on a cluster or a grid. The NPB have been designed to compare performances of MPI implementations and clusters. The NPB use several classes (S, W, A, B, C, D) to represent the size of the problem. We have done our experiments with the B class on four or sixteen nodes. They have different kind of communication schemes. We can see in [START_REF] Subhlok | Characterizing NAS Benchmark Performance on Shared Heterogeneous Networks[END_REF] that all of them are symmetric excepted CG and EP. In [START_REF] Faraj | Communication Characteristics in the NAS Parallel Benchmarks[END_REF], the authors give the type of communications (point-to-point or collective) and the number of messages for each NAS for the class A on 16 nodes. We have run each NAS with a modified MPI implementation to find their communication pattern.

B. Testbed description

Our experiments are conducted on Grid'5000, which links nine sites in France, having from 5 ms to 21 ms of RTT TCP latency. Each site is composed of an heterogeneous set of nodes and local networks (Infiniband, Myrinet, Ethernet 1 or 10 Gbs). Sites are connected by a dedicated WAN operated by RENATER at 1 or 10 Gbps. This architecture provides researchers with a fully reconfigurability feature to dynamically deploy and configure any OS on any host. This feature allows them to have administrator rights to change TCP parameters for instance.

Figure 1 shows the description of our testbed. We use between 1, 2 or 8 nodes on each cluster (Nancy and Rennes) depending on the experiment (execution of pingpong or NPB). Each node is connected to a switch with a 1 Gbps Ethernet card. Thus, the maximum bandwidth available between one process in Rennes and one process in Nancy is 1 Gbps. The RTT TCP latency is about 11.6 ms. Table III shows the hardware and software specifications of the nodes.

We have used the following versions of MPI implementations: MPICH2 is the 1.0.5 release using default parameters. GridMPI is 1.1. We do not use the IMPI support as all the communications (intra and inter sites) are achieved by TCP and YAMPII is self-sufficent. The overhead may be important using IMPI. MPICH-Madeleine is the svn version of the 6th of December 2006. It uses thread (-lib=-lpthread) and fast buffering --with-device= ch mad:--fast-buffer. Finally, OpenMPI version is 1.1.4.

IV. RESULTS OF EXPERIENCES AND OPTIMIZATIONS

A. First ping-pong results

The experiments within a cluster are done between two nodes of the Rennes cluster corresponding to P R1 and P R2 on Figure 1 and within the grid between P R1 and P N 1 . Pingpong results are done with 200 round-trips with the default configuration of MPI implementations. Then, we take the minimum result (among the 200) for the latency and the maximum for the bandwidth in order to eliminate perturbations due to other Grid'5000 users.

Table IV shows the latency comparison between the different MPI implementations in the Rennes cluster or in the grid (between Rennes and Nancy). The overhead of MPI implementations is almost the same in a cluster or in a grid excepted for MPICH-Madeleine. MPICH-Madeleine has a lower overhead in the grid. These figures confirm the longdistance overhead which corresponds to the network latency (11600 μs of RTT ping corresponding to 5800 μs one way). Figure 2 shows the bandwidth obtained on a cluster with the default parameters. All the implementations reach 940 Mbps that is the maximum goodput of TCP on a 1 Gbps link. Each implementation has a threshold around 128 kB excepted YAMPII. These thresholds are due to the different MPI modes (eager and rendez-vous).

Figure 3 represents the results of the same experiment on the grid. Results are very bad. None of the implementations nor direct TCP implementation of the pingpong reached a higher bandwidth than 120 Mbps. These behaviors are due to both bad TCP and MPI configuration. We describe in the next section how to tune them.

B. Tuning to be done on the grid

In TCP, communications are done through sockets. TCP uses a congestion window to limit the number of 'on the fly' packets that are sent but not acknowledged. The sender does not know that a packet is received until being acknowledged, so it must keep this packet in a buffer to restransmit it if needed. Hence, the TCP socket buffers must be able to contain at least a congestion window. The size of these buffers has to be set at least at the product of RTT * bandwidth [START_REF] Semke | Automatic TCP buffer tuning[END_REF].

Two linux kernel variables allow to modify the size of these buffers.

• The first value specifies the maximum size that a socket can allocate to its buffer: /proc/sys/net/core/rmem max and wmem max have to be increased (see [START_REF] Mathis | Enabling High Performance Data Transfers on Hosts[END_REF]). • The linux kernel can adapt these values dynamically with a mechanism called auto-tuning. The first and last value of /proc/sys/net/ipv4/tcp rmem and /proc/sys/net/ipv4/tcp wmem represent the bounds of auto-tuning in the linux kernel. The middle value is the size given initially by the kernel when a socket is created.

The last value has to be increased to RTT * bandwidth.

With the first method, we have to modify the code of each implementation to set the initial size of the socket. With the second, the size is set automatically.

In our experiments, between Rennes and Nancy, the socket buffer has to be set to at least at 1.45 MB (RTT=11.6 ms, bandwidth=1 Gbps). However, for compatibility with the rest of the grid, we set it at 4 MB. This tuning is self-sufficient for MPICH2 and MPICH-Madeleine but not for YAMPII and OpenMPI. In YAMPII, the middle value of TCP socket buffer has to be increased. In OpenMPI, the size of the buffers is specified when a socket is created. This size is 128 kB by default. The modification of this size is done dynamically, passing two parameters to mpirun: -mca btl tcp sndbuf 4194304 -mca btl tcp rcvbuf 4194304

Figure 4 shows the new pingpong results after TCP tuning. The maximum MPI bandwidth available is now around 910 Mbps in the grid which is a good result regarding the 940 Mbps in the Rennes cluster. However, the half bandwidth is only reached around 1 MB in the grid against 8 kB in the cluster. This big difference is not surprising and is explained by the fact that the latency in the Rennes cluster is around 40 μs whereas the grid latency is about 5800 μs. TCP and YAMPII have the same behavior. YAMPII clearly reaches a higher bandwidth for messages bigger than 64 kB. We currently investigate why.

C. NAS Parallel Benchmarks

The two goals of the next experiments are to compare the performances of each implementation on the grid (Figure 5) and to see if the grids can well execute MPI applications (Figures 6 and7).

In the next experiments, we execute the NPB 2.4. We used two different configurations: on the same cluster (using P R1 to P R16 see 1) or between two clusters joined by a WAN (using P R1 to P R8 and P N 1 to P N 8 ) We execute each NPB 5 times and take the better time of these experiments.

Figure 5 shows the NAS execution time comparison of each MPI implementation. MPICH2 is taken as the reference implementation. The performance of the other implementations are relative to MPICH2.

The relative time variation of YAMPII is very important for the applications that communicate with collective operations (FT and IS). This is due to the fact that YAMPII uses better algorithms for them. On MG, the performances are quite similar for each implementation excepted for MPICH2. However, the performances of MPICH2 are better on LU. Finally, execution time of BT and SP is only a little bit better with YAMPII. BT and SP applications timeout when executing with MPICH-Madeleine.

The next experiment aims at evaluating the overhead the grid introduces compared to the execution on a cluster. As Fig. 5 shows that YAMPII has a better behavior for each application, we choose it to compare the NPB on the grid. Figure 6 represents the relative performance of 16 nodes divided in two groups by a WAN to 16 nodes on the same cluster. This figure shows the impact of the latency for each kind of applications. EP has few communications thus the relative performance is close to 1. CG and MG bad performance because they communicate with little messages. The latency has a most important impact on little messages. LU's performance is good because of the message sizes. SP and BT communicate with big messages, thus the high latency does not impact them so much. The performance of IS is quite bad because the IS algorithm is affected by long distance. FT takes advantage of the optimization done on the MPI Alltoall primitive in YAMPII.

If we compare strictly the grid and the cluster with the same number of nodes, there is always an overhead. This overhead is less than 20% for half of the NAS. However, the main interest of the grids is to find resources that are not available on the cluster that's why Figure 7 represents the relative performance of 4 nodes in the same cluster to 16 nodes on two clusters.

The results for the performances of each application on the grid are quite similar of the last experiment. In this experiment, the speed-up should be equal to four if the grid had no impact. For CG and MG, even if we raise up the computing power four times, there is few speed-up. The long distance is very costly on applications with little messages. LU and BT have a very good speed-up near of 4 on the grid. FT and SP performances are quite good (the speed-up is at least 3).

These results confirm that it is efficient to execute an MPI application on the grid because there is a speed up for each application. However, applications with little messages have very bad performance due to high latency. Collective operations have then to be highly optimized to be efficient. V. CONCLUSION AND FUTURE WORK In this paper, we have presented a study of different MPI implementations in a grid context. We aimed at finding a good implementation to execute an application in this context. We also wanted to identify which application types and communication patterns are best suited to grids. Our experiments are based on four MPI implementations (MPICH2, YAMPII, MPICH-Madeleine and OpenMPI). They show that TCP tuning and optimization in MPI implementation are necessary to obtain reasonable performances. After tuning, each MPI implementation can reach as good performance as TCP. To complete our study, we evaluate each implementation with the NPB. Results show that YAMPII behaves better than the others on Grid'5000 due to its optimizations of collective operations and of a simple implementation of its TCP version. However, YAMPII can not manage heterogeneity. Execution of an application on a grid is efficient for applications with quite big messages for point to point communications. Collective operations have to be improved to be efficient.

In a near future, we will pursue our experiments with other Grid-aware implementations like MPICH-G2 and with other real MPI applications. Our results have shown problems with the slowstart and the congestion avoidance mechanisms of TCP when executing an application on the grid. We want to further explore these issues and study optimizations within TCP. Finally, we will test the network heterogeneity management of each implementation with different high performance interconnects. Using these networks for local communications can be efficient to improve performance but has to remain simple. The overhead introduced by the management of heterogeneity has to be less important than the TCP cost.

Fig. 1 .

 1 Fig. 1. Configuration used

Fig. 2 .Fig. 3 .Fig. 4 .

 234 Fig. 2. Comparison of MPI bandwidth of the different MPI implementations on a local network (cluster) with the default parameters

Fig. 5 .

 5 Fig. 5. Comparison of the different MPI implementations: relative (Ref. MPICH2) execution time of NPB on the grid (8-8 nodes on two different clusters)

Fig. 6 .Fig. 7 .

 67 Fig. 6. Comparison of YAMPII on one cluster (16 nodes) and on the grid (8-8 nodes on two different clusters): relative (Ref. is one cluster) execution time of the NPB

Table II summarizes

 II

TABLE I COMPARISON

 I OF MPI IMPLEMENTATION FEATURES

		Long-distance optimizations	Network heterogeneity management	First / Last publication
	MPICH2	None	None	2002 / 2006
		Optimization of TCP	Heterogeneity using IMPI above TCP
	GridMPI	Optimization of Bcast and All reduce but no support of low latency	2004 / 2006
			high-speed networks
	MPICH-		Gateway between high-speed networks
	Madeleine None	Support of TCP, SCI, VIA, Myrinet	2003 / 2007
			MX/GM, Quadrics
			Gateway between high-speed networks
	OpenMPI None	Support of TCP, Myrinet MX/GM,	2004 / 2007
			Infiniband OpenIB/mVAPI

TABLE IV COMPARISON

 IV OF LATENCY IN A CLUSTER AND IN A GRID (IN US)

		In the Rennes	In the grid:
		cluster	btwn Rennes
			and Nancy
	TCP	41	5812
	MPICH2	46 (+5)	5818 (+6)
	YAMPII	46 (+5)	5819 (+7)
	MPICH-Madeleine	62 (+21)	5826 (+14)
	OpenMPI	46 (+5)	5820 (+8)

ACKNOWLEDGMENT

This work has been funded by the French ministry of Education and Research, the ANR HIPCAL project, INRIA GridNet-FJ associated team and the EU IST FP6 EC-GIN Project. Experiments presented in this paper were carried out using the Grid'5000 experimental testbed, an initiative from the French Ministry of Research through the ACI GRID incentive action, INRIA, CNRS and RENATER and other contributing partners (see https://www.grid5000.fr).


Tony Ducrocq
email: tony.ducrocq@inria.fr

Nathalie Mitton
email: nathalie.mitton@inria.fr

Michaël Hauspie
email: michael.hauspie@lifl.fr

Energy-based Clustering for Wireless Sensor Network Lifetime Optimization

Clustering in wireless sensor networks is an efficient way to structure and organize the network. It aims to identify a subset of nodes within the network and bind it a leader (i.e. cluster-head). This latter becomes in charge of specific additional tasks like gathering data from all nodes in its cluster and sending them by using a longer range communication to a sink. As a consequence, a cluster-head exhausts its battery more quickly than regular nodes. In this paper, we present BLAC, a novel Battery-Level Aware Clustering family of schemes. BLAC considers the battery-level combined with another metric to elect the cluster-head. It comes in four variants. The cluster-head role is taken alternately by each node to balance energy consumption. Due to the local nature of the algorithms, keeping the network stable is easier. BLAC aims to maximize the time with all nodes alive to satisfy application requirements. Simulation results show that BLAC improves the full network lifetime 3-time more than traditional clustering schemes by balancing energy consumption over nodes and still delivering high data percentage.

I. INTRODUCTION

Multi-hop wireless sensor networks (MWN) consist of sets of mobile wireless nodes without the support of any pre-existing fixed infrastructure. Such large scale wireless sensor networks offer great application perspectives. Sensors are tiny devices with hardware constraints (low memory storage, low computational resources) that rely on battery. Sensor networks thus require energy-efficient algorithms to make them work properly in a way that suits their hardware features and application requirements. In this paper, we focus on a given application defined by the BinThatThinks 1 project that aims to ease the collect and recycling of waste and reduce its cost through the use of wireless sensors placed on dustbins. Dustbins are also equipped with GPRS chips for long range communications.

The goal of this paper is to propose a novel clustering algorithm for wireless sensor networks in which each sensor node sends its data to its cluster-head (potentially through multi-hop paths) based on the context of the BinThatThinks project. In this framework, cluster-heads collect data from all sensors in their cluster and send them through their GPRS link. Since activating the GPRS consumes more energy than peer-topeer communications, each node should take the cluster-head role in turn in order to allow the network to be operational as long as possible without too much communication overhead and structure modifications. Data aggregation is performed at every hop toward cluster-head. The clustering scheme should also provide a good trade-off between the number of clusters (the more clusters, the more GPRS activation) and the size of the cluster radius (the bigger radius, the more peer-to-peer communications to reach the cluster-head). The network needs to last as long as possible without any dead node. Energy should be equally distributed over nodes. In this paper, we present BLAC, a novel family of Battery-Level Aware Clustering protocols.

To the best of our knowledge, BLAC is the very first distributed clustering algorithm providing non-overlapping multi-hop clusters with energy concerns. Solutions from the literature mainly propose clustering schemes that either do not balance energy consumption over nodes or provide nonsuitable clusters for our application (overlapping or one-hop clusters). BLAC considers the battery-level of nodes combined with another metric (density and degree) to elect the clusterhead. Yet, nodes naturally change roles over time based on node energy level but in a limited way in order to provide stability to the structure. BLAC comes in four variants: BLACbg combines battery level and node degree, BLAC-bs uses the battery level and node density. BLAC-rg and BLAC-rs run in two steps. They first apply a graph reduction before computing clustering. Each of these variants presents specific features that make them more suitable than others under different conditions. Simulation results show that BLAC extends the lifetime of the first dying node up to 300% compared to literature works, by balancing energy consumption over nodes and allowing a better delivery ratio.

The rest of the paper is organized as follows: Section II presents relative works for clustering on wireless sensor networks. The context and the application targeted by BLAC are introduced in Section III. Section IV describes previous algorithms used by BLAC for self-content purposes. Section V details BLAC. Simulation results are given in Section VI. We finally conclude in Section VII.

II. RELATED WORK

Literature proposes several techniques for cluster formation and cluster-head selection. All solutions aim to identify a subset of nodes within the network and bind it a leader. First solutions such as LCA [START_REF] Baker | The architectural organization of a mobile radio network via a distributed algorithm[END_REF] and HCC [START_REF] Gerla | Multicluster, mobile, multimedia radio network[END_REF] present a similar clustering structure but differ in the metric used. Each node chooses its parent in its neighborhood such as its parent metric is higher than its own one. If a node has the highest metric value in its neighborhood it becomes cluster-head. LCA uses as metric the unique Id of a node and HCC the degree then the Node identifier (Id) to break ties. LCA and HCC create one-hop overlapping clusters which are quiet small. A cluster is constituted of a cluster-head and all its one-neighbors. Two cluster-heads can not be neighbors and a non-cluster-head node belongs to at least one cluster. Overlapping clusters are subject to chain reactions when changes occurs. Such algorithms are thus not suitable to large dynamic networks. In addition, they do not have energy concerns.

WCA [START_REF] Chatterjee | WCA: A weighted clustering algorithm for mobile ad hoc networks[END_REF] considers multiple parameters like positions, mobility and energy. It computes the best weighted sum for a given application and uses this metric in order to elect clusterheads. WCA is one of the first clustering algorithms taking energy into account in its construction. Nevertheless, it produces one-hop clusters, which is not stable. In addition, the algorithm is centralized which makes it hardly scalable. LEACH [START_REF] Heinzelman | Energyefficient communication protocol for wireless microsensor networks[END_REF] uses energy as a priority in the clustering design. Each node becomes cluster-head based on a predefined probability p defined based the number of expected clusters and on whether it has already been cluster-head in previous rounds. A node can be elected as cluster-head even if its remaining energy is low. This node can then die rapidly, triggering a new cluster-head selection and related traffic. Once cluster-heads are advertised, nodes attach to the cluster-head which requires the least energy to be reached, creating one-hop clusters. Then, every cluster-head synchronizes the nodes belonging to its cluster and assign them a time slot for their data transmissions. The percentage of cluster-heads needs to be tuned off-line to fix p and does not dynamically adapt to underlying topologies. Also, by construction, there is a probability for nodes to have no cluster-head in their neighborhood, leading to data losses.

Other propositions exist in the literature but most of them are centralized [START_REF] Dali | Clustering algorithm to balance and to reduce power consumptions for homogeneous sensor networks[END_REF]. Some focus on pre-deployment analysis [START_REF] Shu | Power balanced coverage-time optimization for clustered wireless sensor networks[END_REF], [START_REF] Kaur | A strategic deployment and cluster-header selection for wireless sensor networks[END_REF] and thus are not scalable. Very few of them are energyefficient [START_REF] Younis | Node clustering in wireless sensor networks: recent developments and deployment challenges[END_REF], [START_REF] Buyanjargal | AEEC-Adaptive and Energy Efficient Clustering Algorithm for Content Based Wireless Sensor Networks[END_REF] and even if it is the case, they require additional information [START_REF] Min | Energy efficient clustering algorithm for maximizing lifetime of wireless sensor networks[END_REF] which is not necessarily available at nodes (like GPS position), require expensive data exchange or need a declared sink [START_REF] Dimokas | Energy-efficient distributed clustering in wireless sensor networks[END_REF].

In this paper, we focus on distributed multi-hop nonoverlapping energy-efficient clusters with no predefined size in order to match the underlying network topology and to be reliable to small topology changes. DDR [START_REF] Nikaein | DDR-distributed dynamic routing algorithm for mobile ad hoc networks[END_REF] and Density-based algorithms [START_REF] Mitton | Selfstabilization in Self-organized Wireless Multihop Networks[END_REF] are distributed algorithms proposing multihop non-overlapping clusters. They run a similar clustering algorithm and mainly differ in the metric used. DDR [START_REF] Nikaein | DDR-distributed dynamic routing algorithm for mobile ad hoc networks[END_REF] uses the degree as metric while Density-based [START_REF] Mitton | Selfstabilization in Self-organized Wireless Multihop Networks[END_REF] introduces a new metric called density. More details are given in Section IV-B. Although efficient in terms of reliability, these two propositions do not consider energy constraints. BLAC is thus based on similar algorithm but differs in the metric used, making the cluster organization dynamic regarding to evolution of energy consumption. This maintains the network available as a whole as long as possible.

Unlike solutions from literature, BLAC builds dynamic energy-efficient multi-hop clusters in a distributed way. Its main goal is to extend network lifetime (measured as the lifetime of the first node running out of energy).

III. PROBLEM STATEMENT, CONTEXT AND MOTIVATION

This paper is conforming the BinThatThinks project. The project aims to ease the collect and recycling of waste and reduce its cost. Dustbins are equipped with (i) a wireless module to allow wireless peer to peer communications and (ii) a GPRS modules for longer range communications with the base station. Dustbins then periodically send information about their location, their filling level (does this garbage need to be emptied? how many trucks are needed?), accuracy of the recycling, adequate content, etc. All these data are processed by the garbage truck to dynamically optimize the collect path and by the operators to reduce useless manipulations of empty or dangerous dustbins. Since GPRS consumes much more power than a peer to peer communication chip, it is not wise to use it on all nodes all the time.

The idea defended in BinThatThinks is as follows. In order to reduce power consumption for each node, a clustering organization is run over the network. Each node sends its data to its cluster head. Once all data are gathered, the cluster head aggregates them and sends them to a base station or the garbage truck by using its GPRS module. By doing so, only the cluster head activates its GPRS module and drains more energy (mainly because of the use of GPRS module). BLAC proposes a dynamic energy-efficient trade-off between the size and the number of clusters.

IV. NOTATIONS AND PRELIMINARIES

BLAC relies on previous works from the literature. For the sake of self-content and clarity, this section introduces other works on which BLAC rely and related notations.

A. Generic notations

We model a wireless sensor network as a graph G = (V, E) where V is the set of sensors and E is the set of wireless links uv between each pair of sensors u and v which are in radio range of each other. We note N (u) the neighborhood of a node u i.e. N (u) = {{v} |uv ∈ E} and δ(u) = |N (u)| the degree of node u. In BLAC, clusters are formed through a tree construction in which each node has a parent node. We denote as P (u) the parent of node u in its cluster tree. We note H(u) the cluster-head of the cluster for u.

B. Density metric

In [START_REF] Mitton | Selfstabilization in Self-organized Wireless Multihop Networks[END_REF], clusters are built as follows. Every node u elects its parent within its neighborhood as the node with the highest density. If u is the node with highest density in its neighborhood, it elects itself as its parent and becomes a cluster-head. Ties are broken by selecting the node with lowest Id. If a node v is neighbor of two cluster-heads, it advertises them and the cluster-head with lowest density elects node v as its parent. This ensures a minimal 3-hop distance between cluster-heads. The density ρ is defined as the ratio of the number of links between and to neighbors of u over the degree of u:

ρ(u) = |(v, w) ∈ E | v ∈ {u, N (u)}, w ∈ N (u)| δ(u)

C. Topology reduction

Two variants of BLAC (BLAC-rg and BLAC-rs) run in two steps. In the first step, a graph reduction that takes account of node energy level is computed as in [START_REF] Radak | Using battery level as metric for graph planarization[END_REF]. This is performed by applying a Relative Neighborhood Graph (RNG) [START_REF] Toussaint | The relative neighbourhood graph of a finite planar set[END_REF]. RNG consists of logically removing the edge with the weakest weight in every triangle of the graph. Authors of [START_REF] Radak | Using battery level as metric for graph planarization[END_REF] introduce a new metric called power factor. The Power factor of a link is based on the energy level of nodes at each end of the link. If both nodes are in normal battery state, power factor is 0, if only one node is in critical battery state power factor is 1 and if both nodes are in critical battery state power factor is 2. More common metrics for RNG, i.e. the Received Signal Strength Indicator (RSSI) and node ids are used to discriminate nodes. Fig. 4(a) illustrates the result of a battery-level aware RNG computation. Note that most links between two low energy nodes are discarded from the resulting graph. For instance, the link between nodes n and m has been removed, as well as the one between a and n. The link between j and h is kept because there is no link between j and a neighbor of h with a better power factor than link jh. Nodes with high level of energy are preferred for communications.

V. CONTRIBUTION

In order to maximize the lifetime of the network we introduce BLAC. BLAC comes in 4 distributed and local variants that not need large scale modifications when local changes appear. BLAC aims to keep as many nodes alive as long as possible. The role of cluster head is played by every node in turns in order to balance the energy consumption. All variants are similar to Density-based [START_REF] Mitton | Selfstabilization in Self-organized Wireless Multihop Networks[END_REF] but the metrics used differ.

BLAC combines the remaining energy B(u) with another metric. We define the remaining energy of node u as :

B(u) = batt(u) • 10 battcap
where battcap is the initial capacity of the node battery (same for every node) and batt(u) is the current battery level of node u. Then the remaining power B(u) is an integer between 0 and 10 to limit frequent changes in the metric which would result in a non stable cluster hierarchy.

Four variants of BLAC are BLAC-bg and BLAC-bs from one hand (detailed in Section V-A), BLAC-rg and BLAC-rs from the other hand (BLAC-rg and BLAC-rs in Section V-B).

A. BLAC-b* algorithms

BLAC-bg and BLAC-bs apply the same algorithm but differ in the metric they use. We first detail the metrics they use.

1) Degree and energy: BLAC-bg for Battery-Level Aware Clustering -Battery deGree is based on node degree. Algorithm 1 is run over all nodes with h(u) = δ(u) (Section IV-A). This variant uses a 1-hop neighborhood to build the network, so it stabilizes quickly. However the clustering structure built is sensitive to node apparition and failure as shown in [START_REF] Mitton | Selfstabilization in Self-organized Wireless Multihop Networks[END_REF] since any single change has a direct impact on neighbors and so on degree. A battery-level based RNG is applied removing links between low energy nodes. Arrows represent the choice of parent, dash links are links removed at the RNG step.

2) Density and energy: BLAC-bs for Battery Level Aware Clustering -Battery denSity uses the density ρ(u) as described in Section IV-B. Algo. 1 is run with h(u) = ρ(u). This variant computes the clustering structure with 2-hop information but the stability is improved because a single node has less impact on its neighbors.

3) BLAC-b*: Once the metric is computed, BLAC runs Algorithm 1 with h(u) being either the degree (δ(u)) for BLACbg variant or the density (ρ(u)) for BLAC-bs variant and by considering the battery level jointly with that metric (g(u) = B(u)).

Algorithm 1: BLAC-* algorithm run at each node u.

1 C h ← 0 ; 2 Id min ← +∞ ; 3 if RNG Variants then 4 R(u) ← RN G(N (u)), g(u) = 1; 5 else 6 R(u) ← N (u), g(u) = B(u); 7 for i ∈ R(u) do 8 if C h < h(i) × g(i) ∨ (C h = h(i) × g(i) ∧ Id(i) < Id min ) then 9 P (u) ← i, C h ← h(i) × g(i), Id min ← Id(i) 10 if h(u) × g(u) > C h ∨ (h(u) × g(u) = C h ∧ Id(u) > Id min ) then 11 /* u becomes cluster-head */ 12 H(u) ← u;
Algo. 1 runs at each node as follows : each node sends to its neighbors a hello message with its Id. Knowing its neighborhood, a node sends a new hello message with its Id and its neighbors Ids (Fig. 1(a)). With this information, nodes can compute their density and send it to their neighbors (Fig. 1(b)). Finally nodes can elect their parent or decide to elect themselves as a cluster-head if they have the highest metric (Fig. 1(b): nodes m and i become cluster-heads). Note that clusters are thus built through a tree construction : a elects b that elects m that elects itself as a cluster-head. This same tree is then used to route data towards the cluster-head.

At the beginning all nodes have the same battery level so the algorithms act like Density-based or DDR respectively. Battery starts to drain differently on each node regarding the neighborhood of the node, its activity and whether it is a clusterhead or not. For instance on Figure 3 B(m) will decrease slower than B(n), then m will leave its cluster-head role to n.

As Fig. 2 shows, plain Density-based clustering scheme will eventually create holes. First, nodes m and l will die because cluster-heads consume more energy than regular nodes. After some reorganization a and d are the new cluster-heads and they will finally die, leaving holes in the network, and nodes, which have never been cluster-heads, with a lot of energy.

With BLAC (Fig. 3), instead of dying, nodes m and l will leave their cluster-heads roles before their energy level run to low. In their turns, the new cluster-heads n and d will leave their roles to b and l, balancing the energy consumption of the whole network.

B. BLAC-r*

Battery-Level Aware Clustering -RNG deGree (BLAC-rg) and Battery-Level Aware Clustering -RNG density (BLACrs) variants are variations of the first and the second ones. The main difference is that Algorithm 1 runs in two steps. Before computing its metric (degree or density), a relative neighborhood graph [START_REF] Toussaint | The relative neighbourhood graph of a finite planar set[END_REF] is computed in order to keep only an interesting subset of nodes (Lines 4-5 in Algorithm 1). This allows memory storage saving and the use of less computing capacity for the clustering computation. The clustering algorithm then runs over the reduced graph without considering the battery level anymore since it has already been taken into account in the reduction step (g(u) = 1). Fig. 4 shows the evolution of a clustering structure over RNG. We can see that first round elect nodes b, d and f as cluster-heads (Fig. 4(a)). After a while, cluster-heads nodes have consumed more energy than the others leading to a new construction of the graph. On Fig. 4(b) we can see that links between a and b and between b and n for examples will now be avoided.

VI. RESULTS

To evaluate the performances of the different versions of BLAC, we perform some simulations under the WSNET simulator 2 . We compare the four variants of BLAC to three close approaches of the literature: DDR [START_REF] Nikaein | DDR-distributed dynamic routing algorithm for mobile ad hoc networks[END_REF] and density-based clustering [START_REF] Mitton | Selfstabilization in Self-organized Wireless Multihop Networks[END_REF] because of their algorithmic proximity to BLAC and LEACH [START_REF] Heinzelman | Energyefficient communication protocol for wireless microsensor networks[END_REF] because of its energy efficiency concern. In order to observe different behaviors for LEACH, three values of the p parameter are used 5, 10 and 20% (p is the average number of cluster-heads in the network).

Nodes are placed using realistic maps from districts of Lille in north of France. Nodes are placed on streets and next to building areas by using OpenStreetMap data3 in order to get realistic topologies. Fig. 5 shows topologies we used to run the simulations, red dots represent nodes. In order to use a realistic model for transmitting and receiving costs in both peer-to-peer and GPRS communications, we consider the Texas Instruments CC2420 ZigBee R chip 4 and the LEON-G100 GSM/GPRS module from u-blox5 respectively. The former one consumes 0.77 mW when idle, 35.46 mW for receiving (Rx), and 31.32 mW for transmitting (Tx). The latter one consumes 6.4 mW when idle and 1.25 W for receiving (Rx) or transmitting (Tx). A data traffic is also simulated. Each node generates 16 kbit of data periodically (every 5 seconds) and sends them to its parent. When a node receives data from a child, it stores them until it needs to send its own data and then sends the aggregated data to its own parent. For instance on Fig. 1(b), after node a has generated its own 16 kbit of data, it sends them to b which will store them until it generates in its turns 16 kbit of data. Then b sends 32 kbit to m which waits for its own data to send the aggregated 48 kbit to a base station using the GPRS radio chip.

At bootstrap, each node earns the same energy level set to 32 mWh of energy. When a node sends or receives a packet, the correct amount of energy is removed from the battery depending of the size of the message and data-rate of the chipset used. We can notice that in solutions that do not consider battery level such as density-based and DDR, cluster-heads die quickly. When cluster-heads are dead, other nodes take their role till dying as well, and so on till there is no remaining alive node. This is why we observe an irregular decrease (kind of steps) in the number of alive nodes. Several nodes (the cluster-heads) die almost at the same time depending on the number of nodes they have in their cluster. LEACH performs much better, improving the lifetime up to 3 time longer compared to DDR and Densitybased algorithms. Nevertheless, its performances greatly depend on the number of cluster-heads that have been set up. The more cluster-heads, the more nodes forwarding data (either as cluster-head or to cluster-head) and thus the shorter lifetime. BLAC-* maintains the maximum number of alive nodes up to 900% longer than DDR and Density-based and up to 300% longer than LEACH as expected (see Section III). BLAC-bg and BLAC-rg present a slightly improvement compared to BLAC-bs and BLAC-rs resp. regarding the lifetime as they keep more nodes alive during the decreasing phase. This is due to the overall number of clusters built by every scheme. Indeed, BLAC-bg and BLAC-rg build less clusters than their corresponding variants and thus propose a different balance between the number and the size of cluster-heads that perform a little bit better.

A. Network lifetime

In addition, note that the node synchronization cost has not been considered in the cost evaluation of LEACH.

B. Delivery ratio

Fig. 7 displays the delivery ratio of every algorithm with regards to time for 100 and 250 nodes. Delivery ratio is computed as the amount of data received divided by the amount of data sent. We observe that the different variants of LEACH loses slightly more data than BLAC algorithms regardless of the number of cluster-heads. Indeed, in LEACH, nodes without cluster-head can not send data so their data are lost. Even when the number of cluster-heads increases, some data are still lost because nodes need to share the medium with other nodes in the same cluster and thus may not have enough time to transmit all data. In addition, since there are more cluster-heads, nodes die more quickly (see Fig. 6) since sending more data.

When the number of nodes increases in the network, every scheme loses data. For BLAC variants, density-based and DDR, this is due to the fact that when some intermediary nodes dies, the data it was holding for other are also lost. For LEACH, this is due to the fact that there are more and more nodes in a cluster that need to share the medium and thus, some of the data can not be sent on time.

Discussion

We have seen through the results analysis that the four versions of BLAC are close even if BLAC-rs seems to offer the best performances in terms of quality of service (delivery ration VS network lifetime). Nevertheless, there are still performances that we can not evaluate here because of page restriction. The choice of the BLAC version must be made regarding the needs of the application concerning cluster size, stability and quality of service. For instance, if nodes are mobile BLAC-bs is the best choice because it offers a better stability against mobility as proven in [START_REF] Mitton | Selfstabilization in Self-organized Wireless Multihop Networks[END_REF]. If the size of clusters is not the main issue of the application, like in case of static nodes, BLAC-rg is the best choice for data delivery ratio.

VII. CONCLUSIONS

In this paper, we have introduced a new familly of clustering techniques. Two variants combine the battery level with the degree or the density as a metric for cluster creation. The two others apply a battery-level-based RNG construction. By completely integrating the battery level in the metric used to elect cluster-heads, BLAC balances energy consumption over nodes and maximizes the network lifetime. The algorithm is distributed and modifications due to network dynamics are handled locally, allowing scalability. Results show that our proposition improves network lifetime with no dead nodes up to 300% that is useful for applications like ours. For future work we will extend the comparison of BLAC with other algorithms like WCA [START_REF] Chatterjee | WCA: A weighted clustering algorithm for mobile ad hoc networks[END_REF]. Other energy models should also be used.

We will also run experimentations in real world by using for instance SensLAB6 or Wisebed7 platforms. Another field of investigation is range adjustment.

Figure 1 (

 1 Figure 1(b) shows an example of a network on which we compute the density of nodes. For instance node a degree's,

  , 1.75) (b) Nodes can compute their density according to informations they gathered, then they send it to their neighbors. Finally they attach to the node with the highest density in their neighborhood. Nodes with highest density withing their neighborhood become cluster-heads.

Fig. 1 .

 1 Fig. 1. Clusters creation. δ(a) is equal to 2 and the number of links between neighbors of a is 1. Then ρ(a) = 2+1 2 = 1.5.

Fig. 2 .

 2 Fig. 2. Battery drain: case of density. Cluster-heads die faster than other nodes, creating holes in the network.

Fig. 3 .

 3 Fig. 3. battery drain : case of BLAC-b*. After cluster-heads drain their batteries faster than other nodes, cluster-heads roles change.

Fig. 4 .

 4 Fig. 4. battery drain : case of BLAC-r*. Nodes with low energy level are displayed in orange and nodes with high energy level are displayed in green.A battery-level based RNG is applied removing links between low energy nodes. Arrows represent the choice of parent, dash links are links removed at the RNG step.

Fig. 5 .

 5 Fig. 5. Network topologies, each red dot represent a node.

Fig. 6

 6 Fig. 6 illustrates the benefits of BLAC by showing the number of nodes alive regarding time.

  Fig. 6. Network lifetime

Fig. 7 .

 7 Fig. 7. Data delivery ratio

This work is partially supported by CPER Nord-Pas-de-Calais/FEDER Campus Intelligence Ambiante and ANR ECOTECH BinThatThinks.1 http://binthatthink.inria.fr

http://wsnet.gforge.inria.fr/

http://www.openstreetmap.org

http://focus.ti.com/lit/ds/symlink/cc2420.pdf

http://www.u-blox.com/en/wireless-modules/gsm-gprs-modules/leon-gsmmodule-family.html

www.senslab.info

www.wisebed.eu