Benoît Darties

Fabrice Theoleyre

Andrzej Duda

A Divide-and-Conquer Scheme for Assigning Roles in Multi-Channel Wireless Mesh Networks

A multi-channel MAC seems to be an interesting approach for improving network throughput by multiplexing transmissions over orthogonal channels. In particular, Molecular MAC has recently proposed to modify the standard IEEE 802.11 DCF access method to use dynamic channel switching for efficient packet forwarding over multiple hops. However, this MAC layer requires role and channel assignment to nodes: some of them use a static channel, while others dynamically switch to neighbor channels on-demand. To assign roles and channels, we extend the notion of the Weakly Connected Dominating Set, the structure already used in clustering. More precisely, we adapt the WCDS structure and introduce new constraints to define what we call a reversible WCDS (r-WCDS), which is particularly suitable for wireless mesh networks operating under Molecular MAC. We propose a divide-and-conquer scheme that partitions the network into clusters with one leader per cluster solving a MILP formulation to assign roles in its cluster. By appropriately defining the roles at the border of clusters, we maintain global connectivity in the r-WCDS. Finally, our simulations show that the performance of the propose scheme is close to a centralized algorithm.

Introduction

We consider wireless mesh networks composed of a large number of wireless routers providing connectivity to mobile nodes. They begin to emerge in some regions to provide cheap network connectivity to a community of end users. Usually they grow in a spontaneous way when users or operators add more routers to increase capacity and coverage.

We assume that mesh routers benefit from sufficient resources, may only move, quit, or join occasionally, so that the topology of a typical mesh network stays fairly stable. The organization of mesh networks needs to be autonomic, because unlike the current Internet, they cannot rely on highly skilled personnel for configuring, connecting, and running mesh routers. Thus, proposed protocols must be distributed and self-stabilizing.

One way of organizing the structure of a wireless mesh network is to construct a Weakly Connected Dominating Set (WCDS) [START_REF] Dunbar | On weakly connected domination in graphs[END_REF], which is a well-known clustering scheme in wireless multihop networks. By appropriately electing clusterheads (called dominators in the WCDS terminology), each node in the network is a member of one cluster and the network structure results in a limited number of hops between clusterheads. Such clustering is useful for limiting the overhead of flooding, introducing a routing hierarchy, distributing keys [START_REF] Khan Pathan | A key-predistribution-based weakly connected dominating set for secure clustering in dsn[END_REF], or other network-wide operations.

To improve network capacity, wireless mesh networks can use multiple radio channels: multiplexing transmissions on orthogonal channels allows for parallel transmissions through spectrum spatial reuse and reduces collisions. Mesh routers can take advantage of parallel transmissions over neighbor links by using multiple channels at various time scales. When nodes have multiple interfaces, they can statically allocate channels to achieve high spatial reuse and good performance [START_REF] Raniwala | Centralized Channel Assignment and Routing Algorithms for Multi-Channel Wireless Mesh Networks[END_REF][START_REF] Raniwala | Architecture and Algorithms for an IEEE 802.11-based Multi-Channel Wireless Mesh Network[END_REF][START_REF] Alicherry | Joint Channel Assignment and Routing for Throughput Optimization in Multi-Radio Wireless Mesh Networks[END_REF][START_REF] Kodialam | Characterizing the Capacity Region in Multi-Radio Multi-Channel Wireless Mesh Networks[END_REF]. Nodes with single interfaces can also benefit from multiple channels by switching channels on a per frame basis [START_REF] So | Multi-channel mac for ad hoc networks: handling multi-channel hidden terminals using a single transceiver[END_REF][START_REF] Bahl | SSCH: Slotted seeded channel hopping for capacity improvement in ieee 802.11 ad hoc wireless networks[END_REF]. Molecular MAC [START_REF] Nassiri | Molecular architecture for autonomic wireless mesh networks[END_REF] has recently proposed to modify the standard IEEE 802.11 DCF access method to use dynamic channel switching for efficient packet forwarding over multiple hops. It solves the deafness problem inherent to multichannel schemes by assigning a static channel for one part of nodes (nuclei of spatially distinct atoms) and letting other nodes (electrons) dynamically switch between channels. Electrons always initiate transmissions, while nuclei notify other nodes about pending packets. Molecular MAC outperforms classical strategies like MMAC [START_REF] So | Multi-channel mac for ad hoc networks: handling multi-channel hidden terminals using a single transceiver[END_REF] with respect to throughput, fairness, and end-to-end delay. However, the authors have left the problem of assigning roles (nucleus or electron) and channels for future work.

In this paper, we propose a protocol for organizing a wireless mesh network according to a suitable structure associated with Molecular MAC. We adapt the well-known WCDS structure and introduce new constraints to define what we call a reversible WCDS (r-WCDS), which is particularly suitable for wireless mesh networks operating under Molecular MAC.

The contribution of this paper is threefold:

• it provides a formal definition of the reversible WCDS,

• we propose a new divide-and-conquer scheme for constructing such a r-WCDS in a distributed way,

• we evaluate the performances of the proposed scheme and compare it with other approaches.

This paper is organized as follows. First, we introduce some notations and define the problem of constructing a WCDS for Molecular MAC. In Section 3 we use a Mixed Integer Linear Programming formulation (MILP) to find a r-WCDS. Then, we present in Section 4 potatoes, a divide-and-conquer scheme for constructing a r-WCDS in a scalable way. We report in Section 5 on the simulation based performance evaluation of the proposed scheme and we discuss the related work in Section 6. We finally conclude the paper and give some perspectives.

Problem formulation and notation

We model the network as an undirected graph G = (V, E) in which vertices V(G) are the set of nodes and edges E(G) are all pairs of nodes able to directly communicate. We adopt the following classical notation:

• n = |V| defines the number of nodes in the mesh network,

• N (u) is the set of neighbors of u with cardinality ∆(u) = |N (u)|,
• {u, v} denotes the edge between vertices u and v, i.e. {u, v} ∈ E,

• BW denotes channel capacity,

• CH is the set of all available channels and nbCH = |CH| (IEEE 802.11a provides for instance 12 orthogonal channels in the US).

Reversible Weakly Connected Dominating Set Problem

The Weakly Connected Dominating Set (WCDS) [START_REF] Dunbar | On weakly connected domination in graphs[END_REF] is a widely used structure in wireless multihop networks. Formally a WCDS is defined by the set D ⊆ V such that:

∀u ∈ {V -D} , ∃v ∈ D|v ∈ N (u) (1) G = (V, E ′ ) connected |E ′ = {u, v}, u ∈ D, v ∈ V (2)
A node of D is often called dominator while nodes in V -D are called dominatees.

We define the reversible WCDS (denoted r-WCDS in the rest of the paper) as follows: we only keep the edges (dominator, dominatee), i.e. edges between dominators are removed. We will further see that Molecular MAC requires such a structure. Formally, we transform the second property of Eq. 2 into:

G = (V, E ′ ) connected|E ′ = {u, v}, u ∈ D, v ∈ {V -D} (3)

Relation to Molecular MAC

We are interested in the reversible WCDS, because Molecular MAC [START_REF] Nassiri | Molecular architecture for autonomic wireless mesh networks[END_REF] requires such a structure. Molecular MAC divides a wireless mesh network into spatially distributed atoms so that each atom uses a fixed channel different from its neighbors. An atom is composed of a nucleus and electrons. A nucleus chooses a channel for its atom and sticks to this channel all the time. Nodes at the border of atoms have the role of electrons bonding neighboring atoms: they forward traffic between atoms by dynamically switching their channel to communicate with neighboring nuclei. We can compare Molecular MAC to an extended WLAN: an atom corresponds to a WLAN cell and a nucleus is a virtual Access Point that interconnects other nodes in the cell (electrons). In mesh networks, a node needs to communicate with several cells. Since a node should not miss packets from its virtual AP because it is transmitting packets over another WLAN, Molecular MAC implements a specific MAC mechanism: a node pulls its data frames from the AP that buffers frames and transmits the list of pending destinations in beacons.

In Molecular Mesh, we need to assign a role to each node (a nucleus or an electron) so that the resulting network has the following properties:

1. a node can communicate with any other node via multi-hop forwarding; 2. only nuclei and electrons can communicate with each other, i.e. there is no direct communication between two electrons or two nuclei. Indeed, two nuclei do not hear each other, because they use different channels. Similarly, two electrons continually switch their channels and may suffer from deafness;

3. the capacity of the network should be maximal. In particular, two neighboring atoms, which can interfere, need to use different channels.

Figure 1 illustrates the molecular organization. The identifiers of nuclei are numbers while they are letters for electrons. We can note that links between two electrons are not used, however we need to keep the number of unused links small to allow for redundant paths in the network for better connectivity and failure tolerance. Clearly, the constraints for assigning roles to nodes lead to a reversible-WCDS: each dominator corresponds to a nucleus and an electron to a dominatee.

Constructing the molecular structure also requires that each nucleus node selects a fixed channel. Simultaneous assignment of roles and channels so to maximize network capacity is a difficult problem. However, a good tradeoff between computation time and network performance consists first of determining the role of a node to obtain a connected component regardless of channel usage. Once a node has become a nucleus, it can choose a channel according to a greedy approach by scanning all available channels and choosing the one with the minimum load.

MILP Formulation

We use a MILP (Mixed Integer Linear Programming) formulation already defined in our previous work [START_REF] Theoleyre | Assignment of roles and channels for a multichannel mac in wireless mesh networks[END_REF] to assign roles (i.e. finding a r-WCDS) while maximizing the network capacity. We define all the constraints corresponding to flow conservation, connectivity requirements, throughput maximization as linear constraints. Its solution leads to the optimal assignment of roles (nucleus or electron) and channels in a spontaneous mesh network. We summarize it below.

• We assign a role to each node u ∈ V represented by variable role(u) ∈ {0, 1}

with value 1 if u is a dominator and 0 otherwise.

• Our performance objective is to maximize the global network throughput. We assume any-to-any traffic pattern: each node communicates with each other node thus giving n(n-1) multihop flows. We maximize T min , the minimum throughput allocated to each flow.

• T (u, v, d) corresponds to traffic transmitted by u through link {u, v} to desti- nation d for each triplet (u, v, d)|{u, v} ∈ E, d ∈ V . Note that ∀{u, v} ∈ E, T (u, v, u) = 0 (i.
e. a node does not generate traffic for itself);

• ∆(u) denotes the degree of node u, i.e. the number of neighbors in the network.

Links between nodes

We can only use a link if and only if its endpoints have different roles. Its capacity (the sum of T (u, v, d) over all destinations d) is zero if both endpoints are dominators (Eq. 4) or dominatees (Eq. 5):

∀{u, v} ∈ E, role(u) + role(v) + 1 BW d∈V T (u, v, d) + T (v, u, d) ≤ 2 (4) ∀{u, v} ∈ E, 1 BW d∈V T (u, v, d) + T (v, u, d) ≤ role(u) + role(v) (5)

Flow conservation

Eq. 6 and 7 express the flow conservation law: the sum of traffic to d forwarded by u is equal to the sum of traffic to d entering in u and the traffic generated by u to d (which must be at least equal to throughput T min ). Eq. 7 represents the fact that a destination node must receive exactly (n -1).T min total traffic units (T min for each (n -1) sources):

∀u, d ∈ V, d = u, v∈N (u) T (u, v, d) = v∈N (u) T (v, u, d) + T min (6) ∀u ∈ V, v∈N (u) (n -1).T min = T (v, u, u) (7)

Capacity of an atom

All links belonging to an atom share its bandwidth BW :

∀u ∈ V, v∈N (u) d∈V T (u, v, d) + T (v, u, d) ≤ BW (8)
The constraints are obvious if u is a dominator. If u is a dominatee, it cannot receive more than BW, even if it is adjacent to several dominators because of time sharing mechanisms for switching between channels.

Improvement

Optional inequalities (Eq. 9) accelerate the MILP resolution by stating that each dominator is adjacent to at least one dominatee and reciprocally:

∀u ∈ V, 1 ≤ role(u) + v∈N (u) role(v) ≤ ∆(u) (9)
Solving the MILP is computationally expensive for large networks: a couple of hours is required to obtain the optimal assignment in a mesh network of 40 nodes.

potatoes: a divide and conquer scheme

In this paper, we propose a divide-and-conquer scheme: we divide the network into clusters with one leader per cluster that solves the MILP formulation for its cluster. The small size of clusters leads to good efficiency of obtaining the local MILP solution. However, we need to enforce additional constraints so that the union of multiple local r-WCDSs results in a global connected r-WCDS. To obtain this goal, we have to define clusters in a certain manner and fix the roles of some node. We provide below the details of the mechanisms for constructing the clusters and achieving the global r-WCDS.

Approach

We propose here a distributed scheme to construct a r-WCDS. We first construct a rooted cluster tree, i.e. a tree in which vertices are clusters and a link exists between clusters if and only if they share a node. We assume that the network is connected: if several components exist, the algorithm will be executed independently in each of them. The rooted cluster tree supports distributed role assignment: one leader per cluster computes the optimal local assignment in its cluster (i.e. not taking into account other nodes and radio links). However, we need to limit the dependence between two clusters, i.e. a node should receive its role from only one leader. Thus, we add the following constraints with respect to classical cluster-trees:

1. One node belongs to at most two clusters. A node that belongs to exactly two clusters is a cluster member of the cluster higher in the tree and the leader in the other one;

2. the intersection of any two clusters contains at most one node. Figure 2 presents an example of clustering: there are five clusters forming a tree hierarchy. We can verify that each leader belongs to exactly two clusters except the root leader at the root of the cluster-tree: it is the network leader.

The leader of each cluster learns the topology of its cluster, i.e. node ids and links between nodes. Then, it computes the local optimal solution with the MILP formulation: all the constraints are translated into linear inequalities and the global objective consists of maximizing the throughput. After computing the roles for its cluster, the leader has just to notify its cluster members about their roles.

The assignment is optimal in one cluster, but the union of local assignments does not necessarily leads to a global optimal r-WCDS, because leaders find the optimal role assignment inside clusters and not among clusters. We need to enforce that network nodes belonging to different clusters end up with the same role in the global r-WCDS. To achieve this goal, we use the hierarchy of the cluster-tree and proceed in the following way:

1. the leader assigns a role to all its cluster members, 2. a node that belongs to one cluster just uses the assigned role, 3. a node that belongs to more than one cluster is the leader of a cluster down in the hierarchy (e.g. node C in Figure 2) and it will receive its role from the leader upper in the hierarchy (e.g. node A).

Finally, at least one path exists in the rooted cluster-tree that uses the hierarchy of clusters. We will now define more formally this algorithm.

Notation

We will use the following definitions: • T denotes a spanning tree used to build the cluster-tree;

• CT represents the cluster-tree structure;

• network leader node denoted by RootLeader is the root of spanning tree T . The unique cluster containing RootLeader is denoted RootCluster and is the root of CT ;

• V (Cluster) denotes the set of nodes belonging to Cluster;

• Leader(Cluster) denotes the leader of Cluster. Obviously, RootLeader is the leader of RootCluster. If Cluster = RootCluster, ClusterLeader is the node belonging to Cluster and to the upper cluster in the cluster-tree. Formally, leader(Cluster) = V(Cluster) ∩ V (parent(Cluster)) with parent(Cluster) being the upper cluster in CT ;

• intra-cluster edges are links between two nodes of the same cluster. Any other link is an inter-cluster edge.

• role(u) denotes the role of node u (either dominator or dominatee).

Cluster-Tree Construction

We assume that nodes periodically broadcast hello messages to discover their neighbors. Usually a network uses this kind of protocols for supporting other functions such as routing-we can just piggyback additional information required by potatoes in such messages.

According to the definitions above, all leader nodes except RootLeader belong to exactly two clusters. In the example presented in Figure 2, RootCluster is located on the top-left corner and the rooted cluster tree has five clusters and the depth of two. The example tree-cluster has two inter-cluster edges. As our algorithm finds the optimal role assignment inside clusters, the presence of the intra-cluster edges in the final r-WCDS will depend on the role assigned to each node at the border.

The tree-cluster construction proceeds as follows.

1. The network elects RootLeader.

2. Nodes construct a spanning-tree rooted at the network leader (i.e. RootLeader).

A node propagates the minimum id received by neighbors (or its own id if it is lower) by piggybacking the tuple < min id, distance, seq nb > in hello messages. A node updates its distance to RootLeader only if the hello message contains a larger seq nb than the current seq nb. Only RootLeader increments the sequence number in each hello: a node can safely decide that RootLeader has left the network, if the sequence number is not incremented during T dead time interval. A node also includes in its hello messages the id of its parent in the tree. In this way, any node can maintain the list of its children in T .

3. We define clusters and their leaders based on their position in the spanning tree. A new cluster is created when the distance to the leader upper in the spanning tree is exactly D + 1 hops:

(a) RootLeader becomes the first leader;

(b) each node piggybacks the identity of its leader, Leader(u) in hello messages. It becomes the first leader on the path in T towards RootLeader;

(c) the tree is divided so that each node is at most D hops away from its leader and the leader has the minimum depth in the tree among all its cluster members. potatoes elects the nodes that are exactly ≡ 0 [D] hops away from the RootLeader ([D] stands for modulo D).

4. a cluster is finally defined for each leader L and contains all the nodes with Leader(u) = L.

Let us consider the topology in Figure 2 with a cluster radius of 2. The figure presents the spanning tree used for the cluster-tree construction: each node is at most 2 hops in the spanning tree away from its leader. Border leaders maintain hierarchical relationships: C, the leader of cluster 4 is one of the children of leader A in cluster 3.

Learning Cluster Topology

A leader should know the internal topology of its cluster before solving the MILP optimization. A node could flood the list of its neighbors in the cluster, but this implies high overhead. We can note that only the leader needs to know the topology of the whole cluster. Thus, we can efficiently use tree T to propagate the topology information and merge it along the tree.

At the beginning, each node discovers new neighbors through hello messages. Besides, a node maintains a local topology table that contains all links for which one extremity is a child in the spanning tree T . This topology table is restricted to the children in the same cluster and is recursively fed: each node piggybacks its topology table in each hello and updates it with the information received from its children (their topology table and their list of neighbors). Obviously, the table of the leader contains the global vision of the cluster topology, while the topology tables of other nodes contain only partial information.

To be fault-tolerant, a node updates its topology table to take into account joining or leaving neighbors. Moreover, each entry of the local table contains a child-id field. Each time a child receives a hello message, it flushes the entries in the local topology table and replaces them by the new ones. In the same way, a child that has changed its parent is simply removed from each local topology table.

Role Assignment

If its topology table remains unchanged for a sufficient time, each leader learns the topology of its cluster, computes the local optimal assignment, and sends it to the cluster members.

We force each leader to have a predefined role by adding the following constraints in the MILP optimization:

• RootLeader becomes the first dominator.

• If the cluster radius (D) is even, each leader can safely take the role of a dominator. Each leader L (except RootLeader) belongs to exactly two clusters: it is the leader of Cluster and a member of P arent(Cluster). Since the radius is even, a path alternating dominatees and dominators can link L to the leader in P arent(Cluster);

• If the cluster radius is odd, the leader L should have the inverse role1 of its leader in P arent(Cluster). By alternating dominatees and dominators, we would obtain a valid path;

Each leader L in Cluster receives its role from P arent(Cluster). This role is fixed in the MILP formulation by adding the linear constraint role(L) = dominator or role(L) = dominatee according to the role given to L. Thus, MILP resolution can be fully distributed in each cluster: L does not have to wait for the role assigned by the leader of P arent(Cluster) and can directly compute roles in Cluster once it knows the topology.

Let consider the topology in Figure 2. We can observe that the MILP formulation can find a solution in a cluster if we fix the role of all the leaders to dominators since the cluster radius is even. For instance, leader A in cluster will execute its MILP with the role of A, B, and C already fixed to dominator. In particular, we can in particular "color" all the nodes with an even depth as dominators and others as dominatees in the spanning tree T . Clearly, a path alternating dominators and dominatees can interconnect any pair of leaders in the same cluster leading thus to an achievable solution. In this way, we guarantee that dominators globally form a valid r-WCDS.

This simple optimization accelerates convergence and results in good performances. Moreover, we keep at least one connected solution in each cluster that consists for each node to alternate roles between nuclei and electron according to the distance to its leader in the cluster.

After solving the MILP optimization Leader sends the list of its cluster members and their assigned roles along the tree.

Discussion

The presented scheme locally optimizes role assignment. It presents the following advantages:

1. by splitting the network into clusters, the algorithm is scalable and succeeds to find a suitable solution with a reasonable computational cost;

2. it is distributed, because it relies on the distributed construction of the cluster-tree and role assignment;

3. it is fault-tolerant by taking into account joining and leaving nodes as well as lost hello messages.

Performance evaluation

We have simulated the proposed protocol in WsNet [START_REF] Chelius | Wsnet: a modular event-driven wireless network simulator[END_REF] using the COIN-CBC linear programming library [START_REF]Coin-or branch and cut[END_REF]. We randomly place nodes in a simulation area. Nodes use the IEEE 802.11a network interface to communicate with each other with the radio range of 10 units and the interference range of 30 units. By default, the mesh network is composed of 50 nodes with on the average 10 neighbors. We adjust the simulation area to obtain given density.

The results correspond to statistics averaged over 10 different simulations of 240 seconds. The graphs present averaged values with 95% confidence intervals. We compare the performance of the centralized MILP formulation (OPT), potatoes, the Maximum Independent Set protocol (MIS) and a self-stabilizing Spanning Tree (ST) ( [START_REF] Theoleyre | Assignment of roles and channels for a multichannel mac in wireless mesh networks[END_REF]). We measure the following performance indices:

• minimum throughput T min : the minimum throughput guaranteed for each flow extracted from the MILP formulation. We consider the normalized channel capacity (i.e. BW = 1);

• average route stretch factor: the average ratio of the length of the shortest route through the r-WCDS and the length of the shortest route in the original graph.

Grid Topology: Capacity

We have first compared the performance of the different protocols in a grid topology: nodes are placed regularly in a squared grid, the length of each cell in the grid being the radio range. Such a grid can represent a regular mesh network deployed for instance by a telecommunication operator. We do not report the results for MIS since it leads to a disconnected network in most cases.

We have measured T min , the minimum throughput allocated to each flow obtained with the MILP formulation for a varying number of nodes (cf. Figure 3). We can observe that all the protocols perform quite similarly. In particular, the spanning tree strategy achieves to find optimal roles and channels: in a grid, the pruning strategy is inefficient since the number of neighbors is limited. Thus, ST consists of marking as dominators all the nodes with an even depth (on average a half of the nodes in a random spanning tree) and as dominatees other nodes.

Random Topology: Route Stretch Factor

Then we have considered a random topology of a given density (10 neighbors on the average). We measure the route stretch factor: the ratio of the route length in a molecular mesh and in the original graph (cf. Fig. 4). A stretch factor of 1 means that only the shortest routes are used. For MIS, we discard isolated nodes since the stretch factor would become infinite in this case. Thus, we tend to under-estimate the real stretch factor for MIS. OPT results in an average stretch factor around 1.3 for any number of nodes. However, OPT is not scalable-results become difficult to obtain in a reasonable time for more than 40 nodes (50 nodes require more than 3 hours) and almost impossible to be obtained for more than 60 nodes. This explains why we do not plot results for 50 and 60 nodes under OPT in Figure 4.

The performance of potatoes and OPT is very similar. potatoes achieves to construct a r-WCDS with a maximum number of radio links: the routes are often the shortest ones. Moreover, potatoes is much more scalable than OPT and achieves to compute distributively a r-WCDS even for larger networks. This shows that the divide-and-conquer approach is suitable for our problem.

ST uses longer routes, but the stretch factor tends to decrease when the number of nodes increases. The stretch factor for MIS is large and a flow consumes more bandwidth since it is relayed by more nodes on average.

Random Topology: Capacity

Finally, we have measured the minimum throughput T min in a random topology (cf. Figure 5). This metric corresponds to the throughput we can obtain with Molecular MAC.

Obviously, the OPT protocol gives us an upper bound since it finds role assignment maximizing the objective. However, scalability issues do not allow to obtain enough significant results when we have more than 40 nodes. Here again potatoes results are very close to those of OPT.

We can note that MIS and ST achieve much lower throughput: they do not succeed in maximizing the number of links remaining in the r-WCDS topology, which leads to a lower throughput. For the density we have used, the average performance of both strategies is less than half of the performance obtained with potatoes.

Related work

Clustering creates groups of nodes, which is particularly useful in wireless multihop networks to introduce a hierarchy (e.g. for routing). Clusters often make use of the concept of domination: nodes elect a clusterhead and all its neighbors become members of the cluster [START_REF] Richard | Adaptive clustering for mobile wireless networks[END_REF]. However, in some cases two hops may separate clusterheads so that their interconnection requires gateways.

The Weakly Connected Dominating Set (WCDS) is a well-know structure often used for network-wide operations such as clustering or distributing keys in MANET [START_REF] Khan Pathan | A key-predistribution-based weakly connected dominating set for secure clustering in dsn[END_REF]. However, finding a WCDS with a given cardinality is NP-hard [START_REF] Dunbar | On weakly connected domination in graphs[END_REF]. Domke et al. [START_REF] Domke | On weakly connected domination in graphs ii[END_REF] extended this result by characterizing graphs having the same minimum cardinality to form both a WCDS and a DS. However, the authors focused on particular graphs (e.g. trees with special properties) and did not solve the WCDS problem in any graph.

Chen et al. [START_REF] Yuanzhu | Approximating minimum size weakly-connected dominating sets for clustering mobile ad hoc networks[END_REF] extended the centralized algorithm for finding a WCDS of Guha et al. [START_REF] Guha | Approximation algorithmsforconnecteddominatingsets[END_REF] by selecting the best nodes to add in the WCDS for each round, i.e. the component that forms the WCDS grows at each step. Dubashi et al. [START_REF] Dubhashi | Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons[END_REF] pruned the edges that belong to a cycle, i.e. they create a sparser network. Although it forms a Connected Dominating Set, it cannot directly be used to create a r-WCDS. Alzoubi et al. [START_REF] Khaled | Weakly-connected dominating sets and sparse spanners in wireless ad hoc networks[END_REF] constructed a Maximum Independent Set, clusterheads being elected based on their depth in a spanning tree. Thus, this algorithm is close to the ST algorithm presented in the Section 5.

In our approach, we build upon the ideas of Chen et al. [START_REF] Yuanzhu | Maintaining weakly-connected dominating sets for clustering ad hoc networks[END_REF]: they partition the network in zones and each zone executes an algorithm (a divide-and-conquer approach). However, their algorithm is greedy and directly applied to each zone. Moreover, they focused on the original WCDS problem and not on its r-WCDS variant. Moreover, we take into account other performance criteria than the cardinality of the WCDS, i.e. network capacity. Han et al. [20] adopts a similar approach of partitioning the network, however the same remarks as above still hold.

Conclusions and future work

We have presented a divide-and-conquer scheme for computing a reversible WCDS in a distributed way. By creating a cluster-tree, we partition the network into clusters with one leader per cluster solving a MILP formulation to assign roles in its cluster. Although this approach does not lead to the global optimum, our simulations show that its performance is very close to a centralized optimal algorithm.

In the future, we plan to explore new strategies to improve the convergence of potatoes. In particular, we can explore redundancy to simplify the MILP formulation. Moreover, we aim at exploring the trade-off between optimality and convergence delay: if we pre-assign some roles, we can reduce complexity along with a negligible impact on performance.

Figure 1 :

 1 Figure 1: Example molecular topology

Figure 2 :

 2 Figure 2: An example cluster-tree.

Figure 3 :

 3 Figure 3: Minimum throughput T min for a varying number of nodes in a grid

Figure 4 :

 4 Figure 4: Average route stretch factor for a varying number of nodes in a random network.

Figure 5 :

 5 Figure 5: Minimum throughput T min for a varying number of nodes in a random network.

roles are either dominator or dominatee.

Acknowledgments

This work was partly supported by the European Commission project WIP under contract 2740, and the French Ministry of Research project AIRNET under contract ANR-05-RNRT-012-0.


Servane Gillet

Jean-François Ponge
email: jean-francois.ponge@wanadoo.fr

Changes in species assemblages and diets of Collembola along a gradient of metal pollution

Keywords: Collembolan communities, Heavy metals, Gut contents

Springtails (Hexapoda: Collembola) are known to live in a wide range of soil conditions, but changes occurring in their communities under the influence of heavy metal pollution are still poorly documented.

The present study was undertaken in order to discern main coenological trends along a gradient of metal pollution, downwind of a zinc smelter located in the North of France. Three sites were compared within an abandoned field planted with poplar twenty years ago. The total zinc content of the topsoil varied from 4000 to 35 000 mg/kg according to distance to the smelter outlet. Changes in humus forms (shift from mull to mor) and in the degree of opening of the poplar stand (mainly caused by death or stunting of planted trees in the vicinity of the smelter) explained most of the observed variation in abundance and species composition. Sun species living at the ground surface appeared at the most polluted sites where poplar declined and was replaced by a sward of metal-tolerant herb species. The increase in abundance of the whole collembolan community was mainly due to Mesaphorura macrochaeta, the gut contents of which indicated that this species avoided the root mat and fed mainly in the mineral soil underneath. Shifts in food habits and/or in habitat were observed in several other common species, pointing to the importance of avoidance behaviour as a mechanism by which collembolan species may endure heavy metal pollution.

Introduction

Pollution by heavy metals, due to smelter, mining or agricultural activity, has been shown to adversely affect soil animal communities (Bengtsson and Rundgren, 1988;[START_REF] Hågvar | Microarthropods and Enchytraeidae (Oligochaeta) in naturally lead-contaminated soil: a gradient study[END_REF][START_REF] Bruus Pedersen | The impact of a copper gradient on a microarthropod field community[END_REF]. Direct toxicity of heavy metals to soil animals has been demonstrated [START_REF] Tranvik | Relative abundance and resistance traits of two Collembola species under metal stress[END_REF][START_REF] Crommentuijn | Bioavailability and ecological effects of cadmium on Folsomia candida (Willem) in an artificial soil substrate as influenced by pH and organic matter[END_REF][START_REF] Scott-Fordsmand | Toxicity of nickel to a soil-dwelling springtail, Folsomia fimetaria (Collembola: Isotomidae)[END_REF] and it is likely that changes in habitat and food resources affect soil animal communities, too. Toxicity to decomposer microbes and animals is indicated by a drastic reduction in litter decomposition rate and pronounced changes in humus forms from mull to mor [START_REF] Coughtrey | Litter accumulation in woodlands contaminated by Pb, Zn, Cd and Cu[END_REF]Bengtsson et al., 1988a;[START_REF] Gillet | Humus forms and metal pollution in soil[END_REF]. Above a given threshold of heavy metal contamination, the impairment of decomposer activity creates a new habitat which may affect the abundance, diversity and species composition of soil animal communities, even when the critical load of heavy metals is not reached by individual species. Some soil animal species may also resist heavy metal contamination by selecting less-contaminated micro-sites [START_REF] Tranvik | On the advantages of Folsomia fimetarioides over Isotomiella minor (Collembola) in a metal polluted soil[END_REF]Bengtsson et al., 1994a) or by changing their reproductive, excretory or feeding behaviour [START_REF] Joosse | Uptake and excretion of lead by litter-dwelling Collembola[END_REF]Bengtsson et al., 1985;[START_REF] Niklasson | Environmental stress and reproductive mode in Mesaphorura macrochaeta (Tullbergiinae, Collembola)[END_REF].

We decided to test the hypothesis that soil animal communities sampled along a gradient of heavy metal pollution show a) shifts in species composition, b) shifts in food habits of tolerant species, and that these changes can be explained, at least partly, by associated changes in humus form and vegetation. Springtails (Hexapoda: Collembola) were chosen as test animals given their abundance and diversity in a wide variety of soil types [START_REF] Ponge | Biocenoses of Collembola in atlantic temperate grass-woodland ecosystems[END_REF][START_REF] Petersen | A review of collembolan ecology in ecosystem context[END_REF][START_REF] Ponge | Soil fauna and site assessment in beech stands of the Belgian Ardennes[END_REF], the flexibility of their alimentary habits [START_REF] Mcmillan | Interspecific and seasonal analyses of the gut contents of three Collembola (Family Onychiuridae)[END_REF][START_REF] Hasegawa | Changes in feeding attributes of four collembolan populations during the decomposition process of pine needles[END_REF]Ponge, 2000a), and strong variation among species in sensitivity to heavy metals (Bengtsson and Rundgren, 1988;[START_REF] Bruus Pedersen | The impact of a copper gradient on a microarthropod field community[END_REF][START_REF] Filser | Response types in Collembola towards copper in the microenvironment[END_REF].

Materials and methods

Study sites

The Bois des Asturies in Auby (Nord, France) is near to and downwind of a zinc smelter which is one of the largest in the world (producing 245 000 tons of zinc per year). The wood today suffers from active pollution by heavy metals, mainly Zn, but Cd and Pb are present in the soil from past activity.

This site was formerly used to deposit slag rich in heavy metals. Hybrid poplar (Populus sp.) was planted in 1974 and 1977 on the site most remote from the smelter and in 1981 and 1983 nearer the smelter, after a change in production methods when electrolysis replaced coal burning. The plantation becomes sparser nearer to the smelter, due to the death of most trees, and surviving trees are stunted. A sward of plants tolerant to heavy metals such as Viola calaminaria, Armeria maritima halleri, Arrhenaterum elatius and Cardaminopsis halleri covers the ground.

Three sites were studied. Site P1, 490 m from the smelter, is characterized by a field layer with A. elatius and C. halleri as dominant species, under a closed poplar canopy. Site P2, 340 m from the smelter, has a dense cover of V. calaminaria under an incomplete poplar canopy. There is no poplar at site P3, nearest the smelter (235 m), and the field layer is dominated by A. maritima halleri and

Phragmites australis.

The soil is a silty clay loam, but the top 10 centimetres are mainly organic matter, humified and partly mixed with mineral matter at P1, but undecayed at P2 and P3 [START_REF] Gillet | Humus forms and metal pollution in soil[END_REF]. Litter horizons, according to the nomenclature of O horizons by [START_REF] Brêthes | Classification of forest humus forms: a French proposal[END_REF] and [START_REF] Ponge | Comment distinguer dysmoder et mor? L'exemple de la forêt domaniale de Perche-Trappe (Orne)[END_REF], are OL (1.5 cm) and OF (1.5 cm) at P1, OL (2 cm) and OM (7 cm) at P2, OL (1 cm) and OM (at least 8.5 cm) at P3 [START_REF] Gillet | Humus forms and metal pollution in soil[END_REF]. These superficial horizons are underlain by a crumb A (organo-mineral) horizon at P1, and a compact S (mineral) horizon at P2 and P3, with an abrupt transition from organic to mineral (or organo-mineral) parts of the topsoil. Thus the humus form is a Dysmull at P1, and a Mor at P2 and P3. We measured soil pH and heavy metal contents (Zn, Cd, Pb) at the three sites.

Sampling and identification of animals

Soil microarthropods were sampled in October 2000. At each of the three sites five soil cores 5 cm diameter and 10 cm depth, litter included, were taken with a core sampler and the fauna were extracted over ten days by the dry funnel method, using plastic funnels 20 cm in diameter with a 5-mm mesh stainless steel wire net inserted in the top part and heated by a 25W lamp bulb placed at 15 cm distance [START_REF] Edwards | A comparison of extraction methods for terrestrial arthropods[END_REF]. Care was taken that an outer space was left around the samples within the funnels and that the air circulated actively in the extraction room, in order to avoid barrier effects and too rapid desiccation of the soil, respectively [START_REF] Tamura | Biases in extracting Collembola through Tullgren funnel[END_REF]. Animals escaping the slowly drying soil were collected and preserved in 95% (v/v) ethyl alcohol until identification. Springtails were sorted out under a dissecting microscope then mounted in chloral-lactophenol (25 ml lactic acid, 50 g chloral hydrate, 25 ml phenol) and identified to species under a phase contrast microscope at 400 X magnification. [START_REF] Gisin | Collembolenfauna Europas[END_REF] was used as a reference book but several more recent identification keys and diagnoses were used additionally, including [START_REF] Zimdars | Synopses on palaearctic Collembola[END_REF], [START_REF] Jordana | Fauna Iberica. VIII. Collembola Poduromorpha[END_REF], [START_REF] Fjellberg | The Collembola of Fennoscandia and Denmark. I. Poduromorpha[END_REF]Bretfeld (1999).

The sex ratio of Mesaphorura macrochaeta was determined, since males were present in our population of this otherwise parthenogenetic species [START_REF] Rusek | New Onychiuridae (Collembola) from Vancouver Island[END_REF].

Centipeds, pseudoscorpions, spiders, gamasid mites, japygids, ants, staphylinids, carnivorous beetle and fly larvae were counted during the sorting process. With the exception of carabid beetles, which prey upon vagabond surface-living species, these animal groups include most predators of Collembola [START_REF] Ernsting | Predation on two species of surface dwelling Collembola. A study with radio-isotope labelled prey[END_REF][START_REF] Walter | Guilds or functional groups? An analysis of predatory arthropods from a shortgrass steppe soil[END_REF][START_REF] Gunn | The exploitation of food resources by soil meso-and macroinvertebrates[END_REF].

Observation of gut contents

After identification, gut contents from each animal mounted in chloral-lactophenol (a clearing medium) were observed under a phase contrast microscope at 400 X magnification. Food items were identified and classified into seven categories:

 Plant material  Fungal material  Bacteria  Animal remains (including exuviae)
 Holorganic humus (no recognizable plant, animal and microbial material, but without or with a weak content of mineral particles)  Hemorganic humus (mixing of organic matter with mineral matter, without recognizable plant, animal and microbial material)

 Empty guts

The proportion in volume of the different food items was estimated by eye in each animal and then summed up by species and site.

Chemical analyses

After extraction of arthropod fauna, soil samples were stored in plastic bags until analysed.

The pH was measured electrometrically in both a 1:5 (by volume) soil:water and soil:potassium chloride (0.1 M) suspension. Total zinc, lead and cadmium were determined after solubilization of mineral matter by hydrofluoric and perchloric acids, and after preliminary combustion of organic matter at 450°C. Lead and cadmium were measured by atomic absorption at 283.3 nm and 228.0 nm, respectively and zinc by plasma emission at 213.86 nm. Control measurements using certified reference materials were made at the start and at the end of each run.

Statistical treatment

Collembolan communities were compared between the three sites by help of one-way ANOVA when raw or log-transformed data did not violate assumptions of analysis of variance. Otherwise sites were compared in pairs using non-parametric Mann-Whitney rank-sum tests [START_REF] Glantz | Primer of biostatistics[END_REF].

Results

Chemical analyses

Zinc was by far the most abundant heavy metal, reaching 41 570 mg/kg in one topsoil sample taken at site P3. Sites P2 and P3 were richer in total Zn than site P1 but did not differ significantly from one another (Table 1). Similarly, differences between sites P2 and P3 were not significant for lead and cadmium, their contents of Pb and Cd being higher than those of P1.

Water pH did not differ between the three sites, being always near neutrality. By contrast, when measured in potassium chloride, pH was lower for P1 than for P2 and P3, indicating a decrease in exchangeable acidity in the two most polluted sites. Exchange acidity was expressed by  pH, i.e. the difference between water and potassium chloride values.

Collembolan communities

Springtails were more abundant at P2 and P3 compared with P1, but the mean species richness, i.e. the number of species found in a sample unit, did not differ among the three sites (Table 1). The relative richness, i.e. the number of species weighted by the number of individuals found in a sample, differed significantly among the three sites, in the order P2 < P3 < P1. The total species richness, i.e. the total number of species found in the five samples taken at each site, was higher at P1 than at P2 and P3, although no significance level could be assigned to this parameter.

Changes in species composition were reflected in presence/absence of species or in changes in abundance (Table 1). The high density of collembolans at P2 and P3 was mainly due to Mesaphorura macrochaeta, the abundance of which increased significantly in the order P1 < P3 < P2. This species comprised 94% of the total community at P2, 67% at P3 and only 1.7% at P1. Friesea truncata, Parisotoma notabilis and Protaphorura armata were present at P1 and P3, not at P2, Micranurida pygmaea was present at P2, not at P1 and P3, and Lepidocyrtus cyaneus was present at P2 and P3, not at P1. Other species did not show significant between-site differences.

With the exception of two samples the abundance of Mesaphorura macrochaeta exhibited an increase, followed by a decrease when the Zn content of the topsoil increased (Fig. 1). Maximum abundance occurred between 15 000 and 20 000 mg/kg of Zn. Males were present at P2 and P3, with a sex ratio of 0.65 and 0.47, respectively (Table 1). The presence of males could not be checked at P1, where only one individual, a female, was found.

Abundance of predators

The total abundance of predators of Collembola was higher at P2 than at P1, the site P3 exhibiting intermediate values (Table 1). This parameter was significantly and positively correlated with the abundance of Collembola, according to Spearman rank correlation test (r s = 0.56, P < 0.05, d.f. = 13).

Diets of Collembola

Only four species were considered for between-site comparisons, due to the need for enough replication of gut content observations, but none of these species could be used for comparing the three sites altogether. Thus only comparisons for pairs of sites will be presented (Fig. 2).

The sminthuridid Sphaeridia pumilis was present at P1 (15 individuals) and P3 ( 22individuals). Strong differences were observed between the two sites in the food regime of this epigeic species. At P1 fungal material was ingested preferentially (47% of total food bolus volume) followed by hemorganic humus (30%) then by holorganic humus (23%). At P3, 90% of feeding animals had ingested hemorganic humus, only 8% having fungal material in their gut.

The isotomid Parisotoma notabilis was present at P1 (54 individuals) and P3 (49 individuals).

At both sites this hemiedaphic species fed nearly exclusively on hemorganic humus (76 to 86% of total food bolus volume), but much more fungal material was eaten at P1 (8%) compared to P3, with only 3%. Bacteria and holorganic humus were present in guts of this species at P3, not at P1. Like the two previous species the onychiurid Protaphorura armata was present at P1 (18 individuals) and P3 (21 individuals). Marked differences between these two sites were exhibited by gut contents of this euedaphic species. At P1 the dominant category was plant material (44% of total food bolus volume), followed by holorganic humus (29%). At P3 the dominant category was fungal material (44%), followed by animal material (22%). At P3, few guts contained plant material (7% of total food bolus volume).

The tullbergiid Mesaphorura macrochaeta was present at P1 but at too low density (2 individuals), thus comparisons were made only between sites P2 (962 individuals) and P3 (356 individuals). At these two sites the dominant material was hemorganic humus (52% and 73% of total food bolus volume at P2 and P3, respectively), the rest being mainly microbial (fungal and bacterial) material, but more bacteria were ingested at P2 (19%) than at P3 (5%).

Discussion and Conclusion

In a previous paper [START_REF] Gillet | Humus forms and metal pollution in soil[END_REF] we demonstrated that humus forms strongly differed between the less polluted site (P1), with about 4000 mg/kg of Zn in the topsoil, and the other two sites P2 and P3, with about 20 000 and 30 000 mg/kg of Zn, respectively. In particular, at P1 the top 10 cm mostly comprised hemorganic material (earthworm and millipede faeces), while undecayed plant litter and roots constituted the main part of the shallow organic soil at P2 and P3. Thus quite different food and habitat conditions prevailed between P1 on the one hand, with a mull humus, and P2 and P3 on the other hand, with a mor humus. The poor humification of organic matter at the two most polluted sites was responsible for the low exchange acidity of the mor horizon [START_REF] Stevenson | Humus chemistry. Genesis, composition, reactions[END_REF]. Despite similar pH values, the heavy metal content of the topsoil clearly differed between the three sites and was connected with the observed changes in humus form [START_REF] Gillet | Humus forms and metal pollution in soil[END_REF].

Thus both direct and indirect effects of heavy metals on soil animal communities could be suspected to occur along a gradient of metal pollution [START_REF] Bruus Pedersen | The impact of a copper gradient on a microarthropod field community[END_REF].

In the present study the absence of an unpolluted control prevented us from assessing all direct as well as indirect effects of heavy metals on collembolan populations. In particular the less polluted site P1, with 4000 mg/kg Zn in the ten top centimeters of the soil, is largely above the background level in the region considered [START_REF] Schvartz | Pathways of transfer of Pb, Cd and Zn in highly contaminated soils[END_REF]. Nevertheless it should be noted that i) dramatic changes in humus form and vegetation were observed within the study site, all related to an increase in heavy metal toxicity [START_REF] Gillet | Humus forms and metal pollution in soil[END_REF], and ii) no proper control could be found within several kilometers around the smelter where land is used for agriculture and gardening [START_REF] Sterckeman | Vertical distribution of Cd, Pb and Zn in soils near smelters in the North of France[END_REF].

As a whole the collembolan community did not seem to be adversely affected by the high heavy metal content of the sites. Compared to the less polluted site P1, the total abundance of Collembola increased at the most polluted sites P2 and P3, reaching values higher than 100 000 ind.m -2

. This points to the resistance of this group as a whole to toxic effects of heavy metals (Bengtsson and Rundgren, 1988) and other environmental stresses [START_REF] Ponge | Collembolan response to experimental perturbations of litter supply in a temperate forest ecosystem[END_REF][START_REF] Alvarez | The effects of drought upon epigeal Collembola from arable soils[END_REF][START_REF] Loranger | Does soil acidity explain altitudinal sequences in collembolan communities?[END_REF]. Nevertheless the observed increase in abundance was not accompanied by a corresponding increase in species richness. The total number of species collected at each site decreased from P1 to P2 and P3, and the relative richness of soil samples, i.e. the number of species weighted by the total abundance, declined tenfold from P1 to P3. This indicated that the increased abundance of the total population was due to only a few species, in agreement with results obtained in other metal-polluted sites (Bengtsson and Rundgren, 1988;[START_REF] Hågvar | Microarthropods and Enchytraeidae (Oligochaeta) in naturally lead-contaminated soil: a gradient study[END_REF][START_REF] Bruus Pedersen | The impact of a copper gradient on a microarthropod field community[END_REF]. The increase in the total abundance of Collembola observed at higher heavy metal concentration could not be ascribed to a decrease in predator pressure, as observed in acidification studies [START_REF] Abrahamsen | Effects of artificial acid rain and liming on soil organisms and the decomposition of organic matter[END_REF], since here the number of predators increased accordingly. Rather, more habitat, more food, and better protection from desiccation and frost can be suspected to occur when litter accumulates [START_REF] Van Straalen | Abundance, pH-preference and mineral content of Oribatida and Collembola in relation to vitality of pine forests in the Netherlands[END_REF][START_REF] Takeda | Dynamics and maintenance of collembolan community structure in a forest soil system[END_REF][START_REF] Bruus Pedersen | The impact of a copper gradient on a microarthropod field community[END_REF], explaining a higher abundance of Collembola in moder and mor, with a thick litter layer, compared to mull with a thin or no litter layer [START_REF] Schaefer | Fauna of the European temperate deciduous forest[END_REF][START_REF] Ponge | Soil fauna and site assessment in beech stands of the Belgian Ardennes[END_REF][START_REF] Loranger | Does soil acidity explain altitudinal sequences in collembolan communities?[END_REF]. Bengtsson and Rundgren (1988) postulated also a decrease in the population of parasites under the influence of heavy metals.

Examination of species occurrence revealed some trends which could be explained by changes in environmental conditions. Species known to live in sunny habitats, such as Brachystomella parvula, Lepidocyrtus cyaneus and Sminthurinus elegans [START_REF] Ponge | Biocenoses of Collembola in atlantic temperate grass-woodland ecosystems[END_REF] were present only at sites P2 and P3, the most polluted ones where the poplar plantation had declined. The abundance of L. cyaneus increased from P2 to P3, following the progressive opening of the poplar canopy due to poor growth or death of planted trees [START_REF] Gillet | Humus forms and metal pollution in soil[END_REF]. Some surface-living (epigeic) species were thus favoured by the open environment created by the lack of poplar extension, rather than by the presence of heavy metals in the soil. A similar decline in forest vegetation might probably explain the expansion of the sun species Isotoma olivacea [START_REF] Ponge | Biocenoses of Collembola in atlantic temperate grass-woodland ecosystems[END_REF] in the lead-contaminated site studied by [START_REF] Hågvar | Microarthropods and Enchytraeidae (Oligochaeta) in naturally lead-contaminated soil: a gradient study[END_REF].

Despite the neutral pH, we observed the presence of the acidophilic species Micranurida pygmaea [START_REF] Hågvar | Colonisation by Enchytraeidae, Collembola and Acari in sterile soil samples with adjusted pH levels[END_REF][START_REF] Hågvar | Collembola in Norwegian coniferous forest soils. III. Relations to soil chemistry[END_REF][START_REF] Ponge | Biocenoses of Collembola in atlantic temperate grass-woodland ecosystems[END_REF] at site P2.

Even though not restricted to acid soils, the high abundance of Mesaphorura macrochaeta at sites P2 and P3 can be compared with its high abundance in dysmoder humus forms with a thick, compact, organic horizon [START_REF] Ponge | Biocenoses of Collembola in atlantic temperate grass-woodland ecosystems[END_REF], and this species has been shown to increase under the influence of artificial acidification [START_REF] Hågvar | Colonisation by Enchytraeidae, Collembola and Acari in sterile soil samples with adjusted pH levels[END_REF][START_REF] Abrahamsen | Effects of artificial acid rain and liming on soil organisms and the decomposition of organic matter[END_REF][START_REF] Bååth | Effects of experimental acidification and liming on soil organisms and decomposition in a Scots pine forest[END_REF].

The bell-shaped curve observed in the distribution of this species along the pollution gradient (Fig. 1) revealed that it was (probably indirectly) favoured by an increase in the Zn content of the topsoil but that this favourable effect declined at the highest Zn concentration. A similar bell-shaped distribution of tolerant species was observed in other metal-polluted sites [START_REF] Dunger | Observations on the ecological behaviour of some species of the Tullbergia krausbaueri group[END_REF]Bengtsson and Rundgren, 1988;[START_REF] Bruus Pedersen | The impact of a copper gradient on a microarthropod field community[END_REF]. [START_REF] Filser | Experimental studies on the reactions of Collembola to copper contamination[END_REF] and [START_REF] Filser | Response types in Collembola towards copper in the microenvironment[END_REF] recorded an attraction of M. macrochaeta to copper-polluted soils in recolonization experiments, although no correction was made for the effects of the sulphate anion. The appearance of sexual reproduction in this otherwise parthenogenetic species [START_REF] Petersen | Parthenogenesis in two common species of Collembola: Tullbergia krausbaueri (Börner) and Isotoma notabilis Schäffer[END_REF] has been also reported from seashore (probably sodium-polluted) and copper-polluted environments [START_REF] Petersen | Sex-ratios and the extent of parthenogenetic reproduction in some collembolan populations[END_REF][START_REF] Niklasson | Environmental stress and reproductive mode in Mesaphorura macrochaeta (Tullbergiinae, Collembola)[END_REF]. This phenomenon presumably results from the inhibition or the disappearance of feminizing hormones produced by the bacteria Wolbachia, reported to occur in the parthenogenetic isotomid Folsomia candida (Vanderkerckhove et al., 1999), as well as in parthenogenetic populations of Mesaphorura macrochaeta and Paratullbergia callipygos (unpublished data). The acido-intolerant species Arrhopalites caecus and Pseudosinella alba [START_REF] Ponge | Biocenoses of Collembola in atlantic temperate grass-woodland ecosystems[END_REF][START_REF] Chagnon | Community structures of Collembola in sugar maple forests: relations to humus type and seasonal trends[END_REF]Ponge, 2000b) were collected only at the less polluted site but at too low density for drawing safe conclusions about their distribution. Nevertheless overall trends in the distribution of acidophilic and acido-intolerant species point to a possible relationship between tolerance or intolerance to heavy metals and tolerance or intolerance to soil acidity. This can be explained by an increasing heavy metal toxicity in acid soils due to i) an increase in soluble metal forms when the pH of the soil solution decreases [START_REF] Geissen | Effects of liming and fertilization on Collembola in forest soils in relation to soil chemical parameters[END_REF][START_REF] Crommentuijn | Bioavailability and ecological effects of cadmium on Folsomia candida (Willem) in an artificial soil substrate as influenced by pH and organic matter[END_REF][START_REF] Lee | The calcicole-calcifuge problem revisited[END_REF], and ii) a concentration of heavy metals in slowly decomposing litter [START_REF] Laskowski | Dynamics of some mineral nutrients and heavy metals in decomposing forest litter[END_REF].

Examination of the gut contents of species able to withstand a high heavy metal content of the topsoil (species abundant at sites P2 and P3) revealed that the organic horizon, where most heavy metals were concentrated [START_REF] Balabane | Mutual effects of soil organic matter dynamics and heavy metals fate in a metallophyte grassland[END_REF], was mostly avoided as a food source, except for Protaphorura armata. The epigeic species Sphaeridia pumilis ingested fungal material to a large extent at the least polluted site P1. At the most polluted site P3 the same species avoided this material in favour of hemorganic humus, which was present only beneath the thick organic horizon [START_REF] Gillet | Humus forms and metal pollution in soil[END_REF]. It is known that fungi concentrate heavy metals in their cell walls to a great extent [START_REF] Hopkin | Effects of metal pollutants on decomposition processes in terrestrial ecosystems with special reference to fungivorous soil arthropods[END_REF][START_REF] Michelot | Update on metal content profiles in mushrooms. Toxicological implications and tentative approach to the mechanisms of bioaccumulation[END_REF] and that heavy metal-enriched food is avoided by algal-feeding springtail species [START_REF] Joosse | Lead tolerance in Collembola[END_REF]. Conversely, clay minerals are known to detoxify the soil from heavy metals by sorption processes (Brady and Weil, 1999). Thus the tolerance exhibited by Sphaeridia pumilis can be at least partly explained by a shift from an epigeic to an endogeic habitat and associated changed food habits. Similar conclusions can be drawn from examination of gut contents of the hemiedaphic species Parisotoma notabilis, known to feed mainly on amorphous organic matter and faecal material [START_REF] Wolters | Untersuchungen zur Interpretierbarkeit von Darminhaltanalysen an Collembolen[END_REF][START_REF] Ponge | Food resources and diets of soil animals in a small area of Scots pine litter[END_REF][START_REF] Chen | Food consumption by Collembola from northern Michigan deciduous forest[END_REF]. The dominance of hemorganic humus in its food diet was not affected by the heavy metal content of the topsoil, although this food source was absent from the organic horizon at the most polluted sites P2 and P3. Thus P. notabilis just followed the distribution of its commonest (probably weakly polluted) food and shifted from surface to deeper horizons, without changing its feeding behaviour. This probably allowed this species, which is highly susceptible to heavy metal and acid pollution [START_REF] Hågvar | Effects of artificial acid rain on the microarthropod fauna in decomposing birch leaves[END_REF]Bengtsson and Rundgren, 1988;Kopeski, 1992), to avoid high concentrations of heavy metals while being still abundant in the most polluted site.

The case of Protaphorura armata deserves a particular attention, since we observed a shift from plant-dominated to fungal-dominated material when passing from the least to the most polluted site (Fig. 2). This species is known as a root/fungal feeder [START_REF] Mcmillan | Interspecific and seasonal analyses of the gut contents of three Collembola (Family Onychiuridae)[END_REF][START_REF] Brown | Effects of some root-grazing arthropods on the growth of sugar-beet[END_REF][START_REF] Shaw | A consistent hierarchy in the fungal feeding preferences of the Collembola Onychiurus armatus[END_REF], which adapts its diet to the availability of plant and fungal material in its immediate environment (Ponge, 2000a). It clearly ingested preferentially roots (probably from poplar) at the least polluted site P1, but root material (mostly from hyperaccumulating plants) was avoided at the most polluted site P3, in favour of fungi, which are known to attract this species over a large distance (Bengtsson et al., 1988b;Bengtsson et al., 1991;Bengtsson et al., 1994b). The latter organisms accumulated heavy metals, but to a lower extent than hyperaccumulating plants [START_REF] Brooks | Plants that hyperaccumulate heavy metals, their role in phytoremediation, microbiology, archaeology, mineral exploration and phytomining[END_REF]. Only a minor part of hemorganic humus was found to be in the diet of this animal at both sites, but it should be pointed out that many animal remains were ingested at the most polluted site. Most of this animal material was made of its own exuviae, which probably indicates that moulting occurred at a higher rate at the most polluted site. Renewal of the gut epithelium at each moulting stage is considered as the most efficient detoxifying mechanism in Hexapoda [START_REF] Humbert | The midgut of Tomocerus minor Lubbock (Insecta, Collembola): ultrastructure, cytochemistry, ageing and renewal during a moulting cycle[END_REF][START_REF] Joosse | Uptake and excretion of lead by litter-dwelling Collembola[END_REF][START_REF] Van Straalen | Heavy metal adaptation in terrestrial arthropods: physiological and genetic aspects[END_REF]. Thus on the basis of our study we must consider tentatively P. armata (also called Onychiurus armatus in other studies) as more tolerant to heavy metals than P. notabilis and S. pumilis, which need changes in habitat and diet in order to survive in metal-polluted soils. Conclusions about the tolerance of P. armata towards heavy metals are supported by field studies (Bengtsson and Rundgren, 1988;[START_REF] Hågvar | Microarthropods and Enchytraeidae (Oligochaeta) in naturally lead-contaminated soil: a gradient study[END_REF][START_REF] Filser | Effects of previous intensive agricultural management on microorganisms and the biodiversity of soil fauna[END_REF], although the behaviour of this species in laboratory tests did not reflect field situations (Bengtsson et al., 1983;Bengtsson et al., 1985).

Mesaphorura macrochaeta was abundant only at the two most polluted sites P2 and P3, where it comprised the bulk of the collembolan community. Unfortunately changes in food diet could not be revealed along the pollution gradient, since comparison with P1 was impossible. Hemorganic humus prevailed in guts from the two most polluted sites, pointing to the need for this species, known to ingest mainly mycorrhizal roots and holorganic humus in organic-rich soils (Ponge, 2000a), to feed on deeper, less-polluted horizons in order to survive heavy metal pollution. Its small size and slender shape allow it to penetrate the compact hemorganic horizon situated just beneath the organic horizon [START_REF] Haarlov | Vertical distribution of mites and Collembola in relation to soil structure[END_REF]. We hypothesize that this small onychiurid species was less tolerant to heavy metals than P. armata, but that its particular adaptation to small pores and the flexibility of its food requirements allow it to live (and even thrive) in less-polluted and well-protected microenvironments.

This may explain why it has been observed in high numbers in other metal-polluted sites [START_REF] Filser | Effects of previous intensive agricultural management on microorganisms and the biodiversity of soil fauna[END_REF]. The capacity of a collembolan species to avoid metal-enriched micro-environments has been demonstrated to increase its dominance in a metal polluted soil [START_REF] Tranvik | On the advantages of Folsomia fimetarioides over Isotomiella minor (Collembola) in a metal polluted soil[END_REF].

Although not experimentally based the present results point on the importance of avoidance behaviour and ecological plasticity in the accomodation of collembolan species (including the metalsensitive Parisotoma notabilis) to metal pollution. This should be considered as an efficient behavioural mechanism, in addition to genetically fixed detoxication mechanisms [START_REF] Posthuma | Genetic variation and covariation for characteristics associated with cadmium tolerance in natural populations of the springtail Orchesella cincta (L.)[END_REF][START_REF] Van Straalen | Genetic biodiversity in toxicant-stressed populations[END_REF].

Bengtsson, G., Berden, M., Rundgren, S., 1988a. Influence of soil animals and metals on decomposition processes: a microcosm experiment. J. Environ. Qual. 17, 113-119. Bengtsson, G., Erlandsson, A., Rundgren, S., 1988b. Fungal odour attracts soil Collembola. Soil Biol. Biochem. 20, 25-30. Bengtsson, G., Gunnarsson, T., Rundgren, S., 1983. Growth changes caused by metal uptake in a population of Onychiurus armatus (Collembola) feeding on metal polluted fungi. Oikos 40, 216-225. Bengtsson, G., Gunnarsson, T., Rundgren, S., 1985. Influence of metals on reproduction, mortality and population growth in Onychiurus armatus (Collembola). J. Appl. Ecol. 22, 967-978. Bengtsson, G., Hedlund, K., Rundgren, S., 1991. Selective odor perception in the soil Collembola Onychiurus armatus. J. Chem. Ecol. 17, 2113-2125.

Bengtsson, G., Hedlund, K., Rundgren, S., 1994a. Food-and density-dependent dispersal: evidence from a soil collembolan. J. Anim. Ecol. 63, 513-520. Bengtsson, G., Rundgren, S., 1988. The Gusum case: a brass mill and the distribution of soil Collembola. Can. J. Zool. 66, 1518-1526. Bengtsson, G., Rundgren, S., Sjögren, M., 1994b

Figure captions Fig. 1 .

 captions1 Figure captions

Fig. 2 .

 2 Fig. 2. Distribution of food items found during the observation of gut contents of Sphaeridia pumilis, Parisotoma notabilis and Protaphorura armata at sites P1 (least polluted) and P3 (most polluted), and of Mesaphorura macrochaeta at sites P2 (medium polluted) and P3 (most polluted).

  Fig.1

Fig. 2

 2 Fig. 2

  . Modelling dispersal distances in a soil gradient: the influence of metal resistance, competition, and experience. Oikos 71, 13-23.

	Brady, N.C., Weil, R.R., 1999. The nature and properties of soil, 12	th ed. Prentice Hall, Upper Saddle
	River, 881 pp.

Bretfeld, G., 1999

. Synopses on palaearctic Collembola. II. Symphypleona. Abh. Ber. Naturkundemus. Görlitz 71, 1-318.

Table 1

 1 Collembolan densities (ind.m-2) and topsoil chemical data in the three investigated sites. Data are means followed by standard errors. Significant differences between sites (P < 0.05) are indicated by different subscript letters

	P1 (490 m)	P2 (340 m)	P3 (235 m)

Acknowledgements

We thank the Centre National de la Recherche Scientifique (Programme Environnement, Vie et Sociétés) for financial support within a research project directed by Pr. Daniel Petit (Lille), and the Institut National de la Recherche Agronomique (Michael Gueroult, Arras) for chemical analyses.