Walid Bechkit

Yacine Challal

Abdelmadjid Bouabdallah

Mouloud Koudil

Brahim Souici

Karima Benatchba

A New Weighted Shortest Path Tree for Convergecast Traffic Routing in WSN

One of the widely used communication patterns in WSN is routing convergecast traffic to one or more sinks. In order to collect data at a sink, most existing systems use a tree rooted at the sink as underlying structure. We consider in this paper the Shortest Path routing Tree problem in WSN under different metrics; we show that the basic approach commonly used in the literature is unsuitable for the many-to-one WSN when considering some metrics. Indeed, existing SPT approaches aim to construct a tree rooted at the sink such that the cost of the path from any node to the sink is minimal, while the cost of a given path is computed as summation of the costs of links that compose this path. However, in many-to-one WSN, links which are close to the sink are more solicited to route packets towards the sink and, hence, they are more critical than other links. Therefore, links in the tree should not have the same weight. We propose in this paper a new weighted path cost function, and we show that our cost function is more suitable for WSN. Based on this cost function, we propose a new efficient shortest path tree construction which does not introduce any new communication overhead compared to basic SPT schemes. We consider, then, the particular case of energy-aware routing in WSN when we apply our new solution in order to construct more suitable energyaware SPT. We conduct extensive simulations which show that our approach allows to enhance the network lifetime up to 20% compared to the basic one.

Index Terms-Wireless Sensor Networks (WSN), Shortest Path Tree (SPT), weighted path cost function, energy-aware routing.

• We show that the basic SPT approach is unsuitable for the many-to-one WSN when using some metrics. • We define a new weighted path cost function, we assign

I. INTRODUCTION

A wireless sensor network (WSN) is composed of a set of tiny autonomous nodes with sensing, computation, and wireless communication capabilities [START_REF] Akyildiz | A survey on sensor networks[END_REF]. The main purpose of such networks is to collect information from a supervised environment or a target object and then send it to a base station usually called the sink. The sink is supposed to be a particular node with plentiful resources. Routing trees are typical structures widely used in WSN to deliver data to the sink, most of existing approaches propose to construct and maintain a tree rooted at the sink in order to gather all collected data at the sink, while minimizing a given cost.

The Shortest Path Tree (SPT) approach is one of the most commonly used methods to construct routing trees in the many-to-one networks and particularly in WSN [START_REF] Luo | Maximizing lifetime for the shortest path aggregation tree in wireless sensor networks[END_REF]. The goal of SPT algorithms is to construct a tree rooted at the sink such that the path cost from any node to the sink is minimal. In existing construction algorithms, the cost of a path is computed as summation of the cost of links that compose the path while the link cost is computed depending on the routing strategy: for instance, when data is routed on minimum hop paths leading to the sink, the link cost is set to be one and the cost of a path gives the hop count to the sink. In energy-aware solutions, the used metric can be the energy dissipation through the link [START_REF] Rodoplu | Minimum energy mobile wireless networks[END_REF] [START_REF] Singh | Power-aware routing in mobile ad hoc networks[END_REF], the remaining energy level [START_REF] Zhang | A learning-based adaptive routing tree for wireless sensor networks[END_REF] or a combined metric [START_REF] Stojmenovic | Power-aware localized routing in wireless networks[END_REF] [START_REF] Chang | Maximum lifetime routing in wireless sensor networks[END_REF]. Congestion-aware strategies [START_REF] Zhang | A learning-based adaptive routing tree for wireless sensor networks[END_REF] consider the message queue length as metric while the number of neighbors is the main metric in connectivity-aware strategies. Some existing solutions [START_REF] Woo | Taming the underlying challenges of reliable multihop routing in sensor networks[END_REF] [START_REF] De Couto | Performance of multihop wireless networks: shortest path is not enough[END_REF] use the quality of link as metric to compute costs, this allows to reduce the average number of retransmissions. Other metrics have been used in the literature such us the latency in time-dependent strategies [START_REF] Lai | On distributed time-dependent shortest paths over duty-cycled wireless sensor networks[END_REF], physical distance and different QoS metrics.

In all SPT based solutions, the cost of a given path is computed as a uniform summation of the costs of links that compose the path; all links within a path are given the same weight. We show in this work that the basic path cost computation is unsuitable for the many-to-one WSN. Indeed, links which are closer to the sink are more critical than the other links. For example, in energy-aware strategies, first level nodes are more solicited by the routing process and are usually the first nodes which fail due to the energy exhaustion. The residual energy of the first level nodes is then more important than the energy amount of the second level ones and so on. Similarly, in congestion-aware strategies, the links which are close to sink are more solicited to route packets towards the sink and hence they are more critical than the other links.

In this paper, we propose a new weighted global cost function more suitable for many-to-one WSN. We assign efficiently decreasing weights to link costs depending on their levels in a given path. We propose, then, an efficient distributed algorithm to construct the shortest path tree through computing minimum cost values based on the defined path cost function. We apply finally our approach to energy-aware routing context and we explain how our approach allows to enhance of the network lifetime. We conduct extensive simulations and we present and discuss the results.

The contributions of our work can be summarized in the following points: to link costs decreasing weights depending on their levels in the path.

• We propose an efficient weighted Shortest Path Tree construction based on the defined path cost. Our construction does not introduce any new extra-communication overheads and have the same complexity as the basic one.

• We apply our approach to the energy-aware routing context where we show that it allows to enhance the network lifetime. To the best of our knowledge, this work is the first to define a path cost function based on the summation of decreasing multiplicative factor which takes into consideration the concentric convergecast nature of WSN communications. Moreover, we design our cost function is such a way that the computation and the maintaining of the minimum cost values and so the weighted SPT can be done without any extracommunication overheads or significant computation overheads. Without loss of generality, we focus in this paper on WSN. Although, the solution that we propose can also be used in conventional networks and, in particular, many-to-one adhoc wireless networks.

The remainder of the paper is organized as follows. In section 2 we give an overview of the basic SPT, we focus on the tree construction and the update strategies. In section 3, we present the main related works using the SPT approach and we explain why this approach is unsuitable for the manyto-one WSN. In section 4, we present our new cost function and the weighted shortest path tree construction; we show the proposed solution is more suitable for WSN. In section 5, we apply our new approach to the energy-aware routing in WSN; we show through simulations that our solution enhances the network lifetime up to 20% thanks to the weighted path cost function. We outline, finally, some conclusions in section 6.

II. BACKGROUND: BASIC SHORTEST PATH TREE APPROACH

In this section, we present the basic SPT approach widely used in the literature; we explain the tree construction as well as the different approaches used to maintain the constructed tree. Before that, let us present the network model that we use in the following sections.

A. Network model

Let (v 1 , v 2 , ...v n ) be the sensor nodes and let s = v 0 be the sink. We assume that all nodes including the sink have the same transmission range denoted by r. We model the WSN as an graph G = (V, E) where V and E represent respectively the node set and the link set. If a node v j is within the transmission range of a node v i ( d i,j = dist(v i , v j ) ≤ r) then the edge e i,j = (v i , v j ) ∈ E. We denote the neighborhood of a node v i by N (v i ) :

N (v i ) = {u ∈ V -{v i }|dist(u, v i ) ≤ r}.
To each directed edge e i,j , we assign a cost C i,j which is computed depending on a given metric. We denote by D vi , the minimum cost to reach the sink from the node v i which is the cost of the shortest path from the node v i to the sink. It is important to note that the cost of a path P denoted by Cost(P ) is computed as the summation of costs of links that compose P .

B. Basic Shortest Path Tree Construction

The aim in traditional shortest path tree approaches is to construct a tree rooted at the sink in such a way that the cost of the path to the sink is optimal for each node v i in the tree. The cost of a path is computed as the summation of the link costs. For example, in figure 1, the cost of the path

P 1 = (v 5 , v 3 , v 1 , v 0 ) is given by : Cost(P 1) = C 1,0 + C 3,1 + C 5,3
In the general case, let P = (v in , v in-1 , , v i1 , v i0 = v 0 ) be a path between node v in and the sink v 0 , the corresponding cost of a P is:

Cost(P ) = n k=1 C i k ,i k-1
Many algorithms were proposed in the literature to compute the SPT. Most of them are based on distributed versions of Dijkstra's algorithm or Bellman-Ford algorithm [START_REF] Bertsekas | Data networks[END_REF]. We focus in this paper on the Bellman-Ford based algorithms knowing that our solution can be easily adapted to other algorithms. The Bellman-Ford algorithm generates the SPT by the iteration:

D h+1 vi = min u∈V [C u,vi + D h u ], starting from conditions: D h s = 0 for all h , D 0 vi = ∞ for all i = 0
Where D h vi is the D vi value at the iteration h. The algorithm of Bellman-Ford terminates after at most (h ≤ n) iterations. The Bellman equation, obtained by the termination of the Bellman-Ford algorithm, is given by:

D s = 0 D vi = min u∈V [C u,vi + D u ]
This equation allows to construct the SPT. Indeed, the last node which allows to enhance the cost value is the parent in the shortest path tree. Bertsekas and Gallager, gives in [START_REF] Bertsekas | Data networks[END_REF], a distributed asynchronous version of the Bellman-Ford algorithm. They show that we can settle for the neighborhood of a node v i given by the transmission range for example. The new distributed version was given by the iteration:

D h+1 vi = min u∈N (vi) [C u,vi + D h u ]
, starting from conditions: D h s = 0 for all h, D 0 vi = ∞ for all i = 0

Where N (v i ) is the neighborhood of the node v i . Bertsekas and Gallagher [START_REF] Bertsekas | Data networks[END_REF] proved that convergence occurs even if different nodes are slow to propagate or calculate their D vi and/or C i,j .

C. Shortest Path Tree Update

In WSN, the link costs are usually not static and may change. For example, in energy-aware context, the remaining energy of nodes decreases continuously. In addition, the physical topology may change because of node mobility or failure and/or new node deployment. Similarly, in the congestionaware, the link congestion costs change constantly. In order to maintain the optimal SPT structure, we identify two approaches in literature:

1) The periodic tree re-construction: In this approach, the sink initiates the setup phase periodically in order to reconstruct a new tree structure. The choice of the period may impact the network performance. Indeed, if the period is too small, then the network may be congested. If the period is too large, then the constructed structure may not be up-to-date for a long time.

2) The adaptive update: In adaptive approaches, the constructed tree is automatically updated during the routing process and no maintenance phase is required. Usually, these solutions propose to add a field containing the minimum cost value to the data packets. Thanks to this field, each node may update its parent and its minimum cost when hearing its neighbor packets. The adaptive update strategies do not guarantee the SPT at any given time; however, it ensures an approximated SPT. If link costs become stable the structure converges to the SPT. These strategies are more suitable for highly dynamic WSN because the periodic tree re-construction may be costly.

III. RELATED WORKS

Routing in wireless sensor networks has been extensively investigated the last decade, a lot of solutions were proposed in this field. We focus in what follows on shortest path based routing strategies, comprehensive surveys on routing for WSN can be found in [START_REF] Hannes | Routing in wireless sensor networks[END_REF] [13] and [START_REF] Al-Karaki | Routing techniques in wireless sensor networks: A survey[END_REF]. Many research works have used explicitly or implicitly the SPT construction in WSN. Depending on the routing strategy, these works propose an adequate link cost definition. In the basic approaches, the aim was to minimize the hop count towards the sink [15][16]. The link cost is set to be one and the path cost, which is computed as the summation of link costs, gives the hop count from the source node to the sink. Since the energy consumption and the end-to-end delay are correlated to the path length, the use of shortest paths in terms of hop count reduces the energy dissipation and the end-to-end delay.

In energy-aware solutions, many metrics were used in the literature. When the energy dissipation through the link is used as metric [3][4], the total consumed energy to reach the sink is minimized. This approach is called Short Path-power routing [START_REF] Stojmenovic | Power-aware localized routing in wireless networks[END_REF] or Minimum Total Energy (MTE) routing [START_REF] Chang | Maximum lifetime routing in wireless sensor networks[END_REF].

In [START_REF] Stojmenovic | Power-aware localized routing in wireless networks[END_REF], authors present a SP-power routing algorithm based on the energy dissipation through the link as metric, they propose also a SP-cost routing where the cost function was proportional to the inverse of the remaining battery power. They present finally a SP-power-cost routing, in order to optimize a combination of the energy dissipation and the remaining energy level. Route constructions were based on the Dijkstra algorithm. When using the SP-power routingstrategy in static WSN, all the traffic is routed on the same minimum energy paths even the tree update is periodic or adaptive, nodes of theses paths exhaust quickly their energy. However, when we base on the remaining energy as metric, the paths to the sink may change and the time to the first node failure is enhanced.

Authors in [START_REF] Chang | Maximum lifetime routing in wireless sensor networks[END_REF] proposed a link metric which combines the transmission energy amount, the reception energy amount, the initial energy level and the remaining energy level of both the source node and the destination one. Authors proposed to use the distributed Bellman-Ford algorithm in order to construct the SPT based on the defined metric. In [START_REF] Zhang | Energy-predicted shortest routing tree algorithm in wireless sensor networks[END_REF], authors propose an energy dissipation prediction model to compute the link metrics. They propose to use the principle of Prim and Dijkstra to build the SPT to prolong network lifetime while using clustering.

In [START_REF] Zhang | A learning-based adaptive routing tree for wireless sensor networks[END_REF], authors propose an adaptive routing tree protocol for WSN where the setup phase is based on the shortest path tree construction with a learning-based adaptive update. Authors propose two strategies: the energy-aware one where they use the remaining energy level of the source node to compute the link cost and the congestion aware strategy where they compute the link costs depending on the current transmission queue length of the source node. Authors in [START_REF] Cao | Efficiency centric communication model for wireless sensor networks[END_REF] proposed to use the outward and inward link quality as metric. Based on this metric, a distributed algorithm is used to construct a SPT. Liang et al. [START_REF] Liang | Racnet: a highfidelity data center sensing network[END_REF] use as metric the expected transmission count (ETX) which is estimated based on link quality indicators. Link quality metrics were also used to construct routing trees in [START_REF] Woo | Taming the underlying challenges of reliable multihop routing in sensor networks[END_REF], [START_REF] De Couto | Performance of multihop wireless networks: shortest path is not enough[END_REF] and [START_REF] Gnawali | Collection tree protocol[END_REF]. Other cost metrics were used in the literature such as the latency in time-dependent strategies [START_REF] Lai | On distributed time-dependent shortest paths over duty-cycled wireless sensor networks[END_REF], the number of neighbors in connectivity-aware strategies, the physical distance and different QoS parameters.

Discussion:

We summarize in table I the main metrics used in the literature to construct routing trees. We notice that research works to date has tended to focus on the link metrics in the aim to enhance some network performances. However, a little attention has been paid to the path cost computation. Indeed, as shown above, all the surveyed solutions using shortest path constructions compute the cost of a given path as a uniform summation of costs of all links that it contains; all links in a path are given the same weight. In fact, this basic approach is unsuitable for routing convergecast traffic in the many-to-one WSN when considering some metrics. Indeed, links which are closer to the sink are more critical than the others.

By the way of illustration, let us consider the remaining energy of the source node as metric to compute the link costs, it is obvious that the remaining energy of the first level nodes is more important than the other node's energy level because the sink neighbors are more solicited by the routing process, so they exhaust their energy much sooner than the other nodes. In figure 1, let us assume that the node v 7 have to choose between the two paths

P 1 = (v 7 , v 5 , v 3 , v 1 , v 0 ), P 2 = (v 7 , v 6 , v 4 , v 2 , v 0 )
, in such a way to minimize the global cost to the sink. If we suppose that the cost of a path is a uniform summation of the path link costs, the node v 7 may select the path node P 1 because the energy level of the nodes v 7 and v 3 is very high. However, the energy level of the node v 1 may be very low. Based on a uniform cost function, many nodes may choose paths containing the node v 1 and the latter exhausts its energy much sooner than the other sink neighbors. In the same way, we can show that basic SPT approach is unsuitable for congestion-aware routing in WSN and for some QoS-aware strategies. Indeed, with a uniform random deployment, the number of nodes at the first level is lower than the number of nodes at the second level and so on, the first level links are more solicited than other links and their congestion is more probable than other links.

In contrast to the basic approaches, we propose in this paper a new weighted global cost function more suitable for many-to-one WSN. In the next section, we explain the new weighted path cost function and we propose a distributed algorithm which allows to construct efficiently the corresponding weighted SPT.

IV. OUR SOLUTION: A NEW WEIGHTED SHORTEST PATH TREE CONSTRUCTION

In contrast to the basic SPT construction approach, we aim in our solution to privilege links which are closer to the sink since they are more critical. In order to achieve this aim, we design a new weighted global cost function which considers the costs of the first level links more than the second level ones, the costs of the second level links more than the third level ones and so on. Our design was driven by the following goals:

• Weighting the global cost function: In order to privilege the costs of links which are closer to the sink, links may be assigned decreasing weights depending on their level in a given path. • Simplicity: Because of the resource constrained environment of WSN, the computation of the cost values and the construction of the new SPT may be done efficiently without new extra control message or significant computational overheads.

• Scalability: The proposed solution may be scalable and efficient for large scale WSN where the number of nodes is high. • Generic solution: The proposed solution may be applicable to different routing strategies including energyaware, congestion-aware, connectivity-aware and QoS aware routing strategies.

A. A new weighted global cost function

In order to privilege the costs of links depending on their levels in a path, we define the new path cost as a weighted summation of costs of all links that the path contains. Let us P = (v in , v in-1 , , v i1 , v i0 = s) be a path which consists of n links. We define the new cost of P , that we denote in the following by α-Cost, as follows :

α-Cost(P ) = k=n k=1 α n-k C i k ,i k-1
Where α is a parameter of our protocol (α ≥ 1), raised to the corresponding power, it determines the weight attributed to the link cost in order to compute a path cost. As we will show, we chose decreasing power of a parameter α to simplify the computation and the update of the minimum cost values. We discuss later in this paper the choice of the parameter α depending on the routing strategies. Using this new cost function, the cost of the path P 1 = (v 7 , v 5 , v 3 , v 1 , v 0 = s) given in figure 1,becomes: α-Cost(P 1 ) = α 3 C 1,0 + α 2 C 3,1 + αC 5,3 + C 7,5 While the cost of the path

P 2 = (v 7 , v 6 , v 6 , v 2 , v 0 = s) becomes: α-Cost(P 2 ) = α 3 C 2,0 + α 2 C 4,2 + αC 6,4 + C 7,6
If we consider the energy-aware context where link costs depend on the remaining energy of nodes, the choice of the shortest path to the sink by the node v 7 using our path cost function is more suitable than the basic approach. Indeed, when computing the cost of P 1 , the remaining energy level of v 1 is implicitly considered more than the remaining energy level of node v 3 , more than the remaining energy level of node v 5 and so on. Similarly, when computing the cost of P 2 , the remaining energy level of v 2 is considered more than the energy level of v 4 and so on. This cost function is then more suitable for many-to-one WSN when using the energyaware strategy since the criticality of links within a given path depends on their levels. The same cost function is also suitable when using congestion-aware strategies in WSN where the message queue length is used as link cost metric. The sink neighbors are more solicited by the routing process than the In what follows, we give a distributed algorithm to compute the new shortest path tree depending on the defined cost function. In addition to the network model presented in section 2, we define W vi as the minimum α-Cost to reach the sink from a given node v i . We define also the α-shortest path tree as the tree rooted at the sink in which the α-Cost of the path to the sink is optimal for each node v i .

B. An Efficient α-Shortest Path Tree Construction

Most of existing distributed algorithms computing shortest path routing trees can be adapted in order to compute the novel α-shortest path tree relying on the new proposed cost function. Indeed, the α-Cost of a n + 1 hop path ending at the sink is computed as the last link cost plus α multiplied by the n hop sub-path (see figure 2). Similarly to the distributed asynchronous Bellman-Ford algorithm, the construction of the α-SPT can be given by the iteration:

W h+1 vi = min u∈N (vi) [C u,vi + α × W h u ]
Starting from conditions:

W h s = 0 for all h, W 0 vi = ∞ for all i = 0.
Where N (v i ) is the neighborhood of the node v i . Similarly to proofs given in [START_REF] Bertsekas | Data networks[END_REF], we can prove that this algorithm converges to the α-shortest path tree even if different nodes are slow to propagate or calculate their W vi , and/or C i,j .

We give in algorithm (1) a distributed construction of the α-SPT. The sink initiates the construction by sending a broadcast message with its null cost. When a node receives the setup message, it computes the α-cost to the sink if it selects the sender as parent, for that, it multiply the received cost by α and add the link cost. If the computed value is lower than the local minimum cost, the node updates its cost, selects the sender node as temporary parent and re-broadcasts the setup message with the new local cost.

We notice that our construction has the same complexity as the basic shortest path tree construction without any extra-communication overheads. In addition, the additional computation overhead is insignificant. Our solution can be used with periodic update as well as the adaptive approaches.

Input: Network topology G Output: α-Shortest Path routing Tree Initialization:

W s = 0, par(s) = s W vi = ∞ , par(v i ) = N ull for i = 1, ..., N Sink s : Broadcast s, W s Upon receiving v j , W j at v i 1 if (W vi > α × W vj + C i,j ) then 2 W vi = α × W vj + C i,j ; 3 par(v i ) = v j ; 4 Broadcast v i , W i ;
end Algorithm 1: α-shortest path tree construction algorithm All existing strategies described above can be adapted to maintain the constructed α-SPT.

In the next section, we apply the α-shortest path tree to the energy-aware routing and we show through simulations that our approach allows to enhance the network lifetime compared to the basic one.

V. APPLICATION TO THE ENERGY-AWARE CONTEXT

The routing in wireless sensor networks has been extensively investigated [START_REF] Hannes | Routing in wireless sensor networks[END_REF] [14] [START_REF] Akkaya | A survey on routing protocols for wireless sensor networks[END_REF] in the literature so far, a particular attention was paid to energy-aware routing. As shown before, the shortest path tree construction based on the remaining energy is one of the favorite approaches commonly used to ensure energy-aware data routing in WSN. In this section, we apply our solution to the energy-aware context when we consider a cost function based on the residual energy level of nodes. First, we model the energy consumption and we define the network lifetime of any constructed routing tree. Next, we compare our approach with different α values to the basic shortest path tree one and we present and discuss the simulation results.

A. Energy model and network lifetime definition

In what follows, we use the model defined in section 2. In addition, we assume that each node v i has a battery with a finite initial energy level E i while the sink is supposed to have unlimited energy amount. We rely on the well known model proposed in [START_REF] Heinzelman | Energyefficient communication protocol for wireless microsensor networks[END_REF] which was widely used in the literature. To send one bit of data from node v i to node v j , the consumed energy at the node v i is given by:

T X i,j = E elec + E amp × d 2 i,j
While the consumed energy, when receiving one bit of data from any node at the node v i , is given by: RX i = E elec Where E elec is the energy consumed in the transceiver circuitry when transmitting or reciving, and E amp is the energy consumed at the transmit amplifier to achieve one meter. Without loss of generality, we assume that we use a TDMAlike MAC which allows to avoid collisions. On the other hand, we focus on the power consumption during the transmission and the reception and we neglect the energy consumption during the idle mode. We assume that each node generates periodically one data packet of k bits, we denote a period time by round. We define π i,j as the amount of data sent from node v i to node v j at each round. For any given tree structure, we define:

• Child i : the direct children of node v i in the tree;

• p i the unique parent of the node v i in the tree. We define the network lifetime as the time until the first node runs out of energy. A detailed discussion of many network lifetime definitions used in the literature can be found in [START_REF] Dietrich | On the lifetime of wireless sensor networks[END_REF]. Using our model, the network lifetime of a given tree is then defined as:

Lif eT ime(T ree) = M ax T s.t. ∀v i ∈ V : T × RX i × ( j∈Childi π j,i ) + T × T X i,pi × π i,pi ≤ E i , π i,pi = j∈Childi π j,i + k (1)
The lifetime of each node is then:

T i = E i RX i × ( j∈Childi π j,i ) + T X i,pi × π i,pi (2)
The system 1 can then be written as follows:

Lif eT ime(T ree) = M in vi∈V T i s.t. ∀v i ∈ V :

T i = E i RX i × ( j∈Childi π j,i ) + T X i,pi × π i,pi π i,pi = j∈Childi π j,i + k (3)
We use this definition to compare the network lifetime of our approach when (α > 1) to the network lifetime of the basic SPT.

B. Simulation Results

Based on the presented energy model, we conducted extensive simulations using MATLAB in order to compare the network lifetime depending on α values while considering the impact of the network density, the network size and the network topology. We recall that the case α = 1 represents the basic SPT. We suppose that each node has an initial energy randomly selected between 5 joules and 20 joules. We summarize in table II the other common simulation parameters. To each link e ij = (v i , v j ), we assign the following cost:

C ij = e Emax -E i β (4)
Where: E max represents the maximum energy level and β is used in order to obtain costs in a reasonable scale, its value does not influent critically the constructed structure. The defined link cost function allows, then, to obtain a value , when the energy level of the source node decreases from E max to 0. In simulations, we chose β = Emax 3 in order to obtain link costs belonging to the interval [1, e 3 ]. We plot in figure 3 the link cost variation when the remaining energy decreases from E max = 20 joules to 0 joules.

1) Impact of network density:

In this first scenario, we studied the impact of network density on the network lifetime of the constructed α-shortest path tree. The deployment field is supposed to be a circle with a radius R = 200 meters, the sink node is set to be at the centre and all sensor nodes are scattered in the field in a random way. We plot in the figure 4, the network lifetime depending on All the reported results are averaged over 750 runs. In figure 5, we consider the particular cases when the number of sensor nodes is respectively 100, 200 and 300.

Results show that higher is α better is the network lifetime, we choose the optimal α value as the value after which the network lifetime reaches the maximum value. As shown in figure 5, the optimal value of α is 6,8 and 8 when the number of nodes is 100, 200 and 300 respectively.

In figure 6, we plot the network lifetime depending on the number of nodes (network density) when α=1 (basic approach), 4 and 7 respectively. The figure shows that our solution enhances the network lifetime up to 17% compared to the basic approach. Indeed, in 99% of cases, the first node which fails is a sink neighbor; our approach based on the weighted path cost function allows to privilege the node remaining energy depending on their hop proximity to the sink. Thus, we choose paths having higher remaining energy at the most critical nodes. 2) Impact of network size: In this second scenario, the network density is constant and set to be 20 nodes per πr 2 m × m. Hence, we varied the radius of the deployment area R depending on the number of sensor nodes, the sink node is always set to be at the centre. We study then the impact of the network size on the network lifetime with different α values. All the reported results are averaged over 750 runs. In figure 7, we plot the network lifetime when the network size is between 100 and 400 nodes and when α is respectively 1, 3 and 5. The figure shows that the use of the weighted shortest path tree allows to enhance network lifetime up to 15% compared to the basic approach. Otherwise, the obtained results showed that the best network lifetime is reached when α is between 5 and 6.

3) Impact of network topology: In the two first scenarios, we used a uniform random distribution to model the node deployment. In order to study the impact of the network topology, we consider in this scenario another topology based on the scale free distribution widely used to model many kind of computer networks and social networks. The scale free distribution was used to model cluster-based WSN where particular nodes having more capabilities are used as routers to relay and/or to perform data fusion or aggregations [START_REF] Ye | A scale-free routing algorithm in wireless sensor networks[END_REF]. In order to construct the scale-free graphs, we used the Albert and Barabasi model [START_REF] Albert | Statistical mechanics of complex networks[END_REF] where the network grows incrementally. The number of edges added at each step is set to be 4. We varied the α values and we calculate the defined lifetime of each constructed α-SPT. All the reported results are averaged over 750 runs. We plot in figure 8 the network lifetime when the number of nodes is between 100 and 400 and when α is respectively 1, 3 and 5. Compared to the basic SPT construction (α = 1) the use of the weighted shortest path tree construction with (α ≥ 5) allows to enhance network lifetime up to 20%. The best network lifetime is reached when α is between 5 and 6. We notice then that our approach (α-SPT) adapts automatically to the new free scale topology and maintains the advantage over the basic approach (SPT).

VI. CONCLUSION

We considered in this paper the shortest path routing tree approach which is one of the most commonly used methods to construct routing trees in the many-to-one networks and particularly in WSN. We showed that the conventional construction used in the literature is unsuitable for WSN because of the concentric nature of communications. Indeed, existing constructions aim to minimize the cost to reach the sink at each node while path costs are computed as a uniform summation of its link costs. However, in WSN, the criticality of links depends on their hop proximity to the sink. We proposed a new weighted path cost function in which we assign efficiently decreasing weights to link costs depending on their levels in a given path. Relying on this cost function, we proposed a new weighted SPT construction which does not introduce extracommunication overheads. Finally, we considered the energyaware routing when we applied our solution to construct more appropriate routing tree. We conducted extensive simulations which showed that our approach enhances the network lifetime up to 20% compared to the basic one.

Fig. 1 .

 1 Fig. 1. Shortest Path Tree illustration

Fig. 2 .

 2 Fig. 2. Illustration of the weighted cost path computation

Fig. 3 .

 3 Fig. 3. Link cost depending on the remaining energy

Fig. 4 .

 4 Fig. 4. Netw. lifetime depending on the α values and the netw. density the α value, when the number of nodes is between 100 and

Fig. 5 .

 5 Fig. 5. Network lifetime depending on the α values

Fig. 6 .

 6 Fig. 6. Netw. lifetime depending on the netw. density with different α values

Fig. 7 .

 7 Fig. 7. Netw. lifetime depending on the netw. size with different α values

Fig. 8 .

 8 Fig. 8. Netw. lifetime depending on the number of nodes with different α values (scale free deployment)

TABLE I SUMMARIZE

 I OF USED METRICS IN TREE BASED ROUTING PROTOCOLS

	Metric	Main objectives
		minimize the length of used paths
	hop count	reduce the energy consumption
		reduce the end-to-end delay
	energy dissipation	minimize the global energy consumption
	remaining energy	enhance the first node failure time
	link quality	reduce the retransmission number
	latency	minimize the end-to-end delay
	number of neighbors	enhance the network connectivity
	message queue length	reduce the congestion

ACKNOWLEDGEMENT

This work is made as part of the Picardie regional project under reference I159C. The authors wish to thank the Picardie regional council in France and the European Regional Development Fund (ERDF) for funding and supporting this project.


Simon Bernard
email: simon.bernard@univ-rouen.fr

Sébastien Adam
email: sebastien.adam@univ-rouen.fr

Laurent Heutte
email: laurent.heutte@univ-rouen.fr

Dynamic Random Forests

Keywords: Random Forests, Ensemble of Classifiers, Random Feature Selection, Dynamic Induction

In this paper, we introduce a new Random Forest (RF) induction algorithm called Dynamic Random Forest (DRF) which is based on an adaptative tree induction procedure. The main idea is to guide the tree induction so that each tree will complement as much as possible the existing trees in the ensemble. This is done here through a resampling of the training data, inspired by boosting algorithms, and combined with other randomization processes used in traditional RF methods. The DRF algorithm shows a significant improvement in terms of accuracy compared to the standard static RF induction algorithm.

Introduction

The Random Forest (RF) algorithms form a family of classification methods that rely on the combination of several decision trees. The particularity of such Ensembles of Classifiers (EoC) is that their tree-based components are grown from a certain amount of randomness. Based on this idea, RF is defined as a generic principle of randomized ensembles of decision trees. Although this idea has already been exploited during the 90's ( [START_REF] Breiman | Bagging predictors[END_REF][START_REF] Ho | The random subspace method for constructing decision forests[END_REF][START_REF] Amit | Shape quantization and recognition with randomized trees[END_REF][START_REF] Dietterich | An experimental comparison of three methods for constructing ensembles of decision trees : Bagging, boosting, and randomization[END_REF]), the formal definition and the use of the term "Random Forest", have been introduced in 2001 in a founding paper written by Leo Breiman ([5]). The definition is as following: Definition 1. A random forest is a classifier consisting of a collection of treestructured classifiers {h(x, Θ k ), k = 1, ..., L} where {Θ k } are independent and identically distributed random vectors and each tree h(x, Θ k ) casts a unit vote for the most popular class at input x.

The reference RF algorithm, called Breiman's RF in the following, has been introduced by Breiman in [START_REF] Breiman | Random forests[END_REF]. It uses two randomization principles: bagging [START_REF] Breiman | Bagging predictors[END_REF] and Random Feature Selection (RFS). This latter principle introduces randomization in the choice of the splitting test designed for each node of the tree. This choice is usually based on an impurity measure that is used as a criterion to determine the best feature for the partition of the current node into several child nodes. RFS randomly selects for each node a subset of features that will be withdrawn for this choice.

RF have shown to be particularly competitive with state-of-the-art learning methods, such as boosting which is known to be one of the most efficient learning principles ( [START_REF] Breiman | Random forests[END_REF][START_REF] Banfield | Eschrich, A comparison of ensemble creation techniques[END_REF]). Since their introduction in 2001, RF have been studied in many ways. For example, some works have proposed to further randomize the tree growing procedure, in comparison with Breiman's RF. One of the most successful methods is the Extra-trees algorithm ( [START_REF] Geurts | Extremely randomized trees[END_REF]) that relies on the Random Feature Selection technique, but with a random choice of the cut point associated to the feature selected for the splitting test. Another example is the PERT algorithm ( [START_REF] Cutler | Pert -perfect random tree ensembles[END_REF]) that sets the cut point midway between two training instances randomly sampled. Other research works have proposed RF induction techniques based on manipulations of the description space. The Rotation Forest method ( [START_REF] Rodriguez | Rotation forest : A new classifier ensemble method[END_REF]) for example, combines several randomization techniques to build a sub-problem dataset which is projected into a new feature space through a Principal Component Analysis (PCA). Finally, efforts have been also brought on new combination operators, by weighting for example the tree votes for each new data point according to an estimation of the ability of each tree to correctly classify similar instances ([10, 11, 12]).

Despite these efforts and even if better performance have sometimes been reported, all these methods have the first drawback that the number of trees has to be set a priori, ideally to a very high value in order to obtain reasonably good performance. A second drawback is that some trees may decrease the forest performance as shown in two recent studies ( [START_REF] Bernard | Influence of hyperparameters on random forests accuracy[END_REF][START_REF] Bernard | On the selection of decision trees in random forests[END_REF]), since trees are arbitrarily (independently) added to the forest. We believe that RF would certainly benefit from adopting a slightly different approach for the forest induction by the way each tree is added to the ensemble. While all RF algorithms add trees independently from one another, we highlight in this paper the interest of a dynamic induction of the forest where trees are grown by taking into account the sub-forest already built. In that way, only reliable trees are intended to be grown in the forest. Thus, the main contribution of this paper is to offer a new dynamic RF induction algorithm, called Dynamic Random Forest (DRF), that compares favorably to the reference algorithm, i.e. Breiman's RF.

The rest of the paper is organized as follows. In section 2 we motivate the interest of designing a dynamic RF induction algorithm and detail our choices for implementing a first variant of DRF. Then, section 3 presents an evaluation of this algorithm and a comparison with Breiman's RF. In section 4, we discuss general pros and cons of DRF over Breiman's RF. Finally, conclusions and suggestions for future work directions are drawn in the last section.

Dynamic Random Forest

As stated in definition 1, a classical RF induction procedure grows trees independently from one another. Hence, each new tree is arbitrarily added to the forest. One can therefore wonder if all those trees contribute to the performance improvement. In [START_REF] Bernard | On the selection of decision trees in random forests[END_REF], we have shown that using classical RF induction algorithms, some trees make the ensemble performance decrease, and that a well selected subset of trees can outperform the initial forest. Figure 1 illustrates this statement by showing the evolution of error rates obtained with a sequential tree selection process called SFS (Sequential Forward Search [START_REF] Hao | Comparison of genetic algorithm and sequential search methods for classifier subset selection[END_REF]) applied on an existing 300-trees forest built with Breiman's RF. This selection technique starts with an empty set and iteratively adds a classifier according to a given criterion (e.g. the error rate obtained on a validation dataset). At each iteration of the SFS process, each classifier in the pool of candidate classifiers is evaluated and the one that optimizes the performance of the ensemble is kept. The results presented in [START_REF] Bernard | On the selection of decision trees in random forests[END_REF] (part of them illustrated on figure 1 for some datasets) show that there always exists at least one sub-forest that significantly outperforms the initial one, sometimes with ten times less trees. The performance of the RF could therefore be improved by removing from the ensemble well selected trees. The idea with DRF is to avoid the induction of trees that could make the forest performance decrease, by forcing the algorithm to grow only trees that would suit to the ensemble already grown. [START_REF] Bernard | On the selection of decision trees in random forests[END_REF]). The blue curves represent the error rates obtained with SFS according to the number of trees selected in the 300-trees forest the error rate of which is represented by the red dashed line. The straight green line on the x-axis indicates the range of sub-forests that obtained a statistically significant performance improvement compared to the 300-trees forest and according to a McNemar.

We show in this paper that the RF induction could benefit from adopting a dynamic approach, that is to say by making the tree induction dependent of the ensemble under construction. For that purpose, it is necessary to guide the tree induction by bringing to the process some "information" from the sub-forest already built. To do so, the idea behind the Dynamic Random Forest (DRF) algorithm is to perform a resampling of the training data that is halfway between bagging and boosting : proceed first to a random sampling with replacement of N instances, where N stands for the initial number of training instances (bagging), and then reweight the data (some kind of boosting). The reason for this choice is to keep using the two efficient randomization processes (i.e. bagging and Random Feature Selection) of Breiman's RF, and to improve RF accuracy by using the adaptative resampling principle of boosting.

Hence, what is performed in DRF is a weighting of each randomly selected training instance according to the predictions given by all the trees already added to the forest. Therefore, to determine the contribution of each training instance for the induction of the next tree, it is necessary to evaluate the ability of the current forest to predict its class. Thus, one possible measure can be a ratio of trees in the existing forest that have predicted the true class. This ratio is defined by:

c(x, y) = 1 | h oob | × h i ∈h oob I(h i (x) = y) (1)
Where I(.) is the indicator function; x is an input data point and y its true class; h i (x) is an equivalent notation for h(x, Θ i ), which represents the i-th classifier output; and h oob stands for the set of out-of-bag trees of x, i.e. the trees for which x is an out-of-bag instance. We recall that the out-of-bag instances are obtained with the bagging principle as follows: each tree is grown from a subset of training instances called a bootstrap sample, formed by random draws (with replacement) from the initial training dataset; the complementary subset of instances that have not been used for growing the tree, called out-of-bag instances, can easily be used as estimates of generalization capacities of the ensemble ( [START_REF] Breiman | Random forests[END_REF]). The objective of computing c(x, y) by taking into account only the trees for which x belongs to the out-of-bag subset is to limit the risk of overfitting ( [START_REF] Breiman | Out-of-bag estimation[END_REF]).

The lower the value of c(x, y), the more the next tree will have to focus on the instance x, since it means that it was incorrectly classified by a large number of trees in the current forest. Consequently, the weighting function that will attribute a weight to x has to decrease with respect to c(x, y). For our experiments, we used the following function:

W (c(x, y)) = 1 -c(x, y) (2)
We will give in the next section results with this linear function W (c(x, y)) but other functions could be used to obtain the same effect (see [START_REF] Bernard | Random forests : From the study of behaviors to dynamic induction[END_REF]).

The DRF process is detailed in Algorithm 1. The same weight (initially equal to 1 N ) is assigned to all the training instances during the initialisation step. Thus, the first tree is induced in a traditional way, i.e. by taking into account each instance identically during the tree induction process. Then, after the first tree has been built, weights are modified so that they are increased for instances wrongly classified by this first tree, and decreased for well classified instances. The second tree is consequently trained from the "re-weighted" training instances, selected in the new bootstrap sample. At the third iteration, these weights are re-calculated thanks to the predictions of the first two trees: maximum weights are given to instances wrongly classified by both the first and the second trees, and minimum weights are given to instances well classified by those two trees. The third tree is trained on the re-weighted data and so on. Note that the weight of a given input data point

x is modified at each iteration, only if at least one out-of-bag tree is available for it. In Algorithm 1, this is checked via the OoBT rees function, which is defined for accessing to the ensemble of out-of-bag trees of a given x.

As shown in Algorithm 1, DRF are built with trees grown using a Random Tree induction algorithm. Rather than using Breiman's algorithm in which the number of randomly selected features, K, is a parameter of the algorithm that is constant and a priori fixed, we use the Random Tree induction algorithm proposed in [START_REF] Bernard | Forest-RK: A new random forest induction method[END_REF]. In this induction algorithm, the Random Feature Selection technique is still used since it appears to be efficient as shown in [START_REF] Breiman | Random forests[END_REF][START_REF] Banfield | Eschrich, A comparison of ensemble creation techniques[END_REF][START_REF] Bernard | Random forests : From the study of behaviors to dynamic induction[END_REF][START_REF] Bernard | Forest-RK: A new random forest induction method[END_REF] but the number of features is randomly selected at each node according to the mean intrinsic information brought by each feature. Hence, given a bootstrap sample made up of randomly sampled training instances from the initial training set, the Random Tree induction procedure is the following one :

• Measure the information gain value of each feature;

• Compute the ratio p of features that exhibit the lowest information gains;

• For each internal node of the tree:

if p is superior to a given threshold then pick a random value of K according to the uniform distribution between 1 and M , where M is the number of features.

else, pick a random value of K according to N ( √ M , M/50).

randomly select K features.

choose the splitting rule according to an impurity measure computed on class counts.

D 1 (x i ) ← 1
D l+1 (x i ) ← W (c(x i , y i )) 13: else 14: D l+1 (x i ) ← D l (x i ) 15: end if 16: Z ← Z + D l+1 (x i ) 17: end for 18:
for all x i ∈ T do 19:

D l+1 (x i ) ← D l+1 (x i ) Z 20:
end for 21: end for 22: return f orest Note that in the last step of Random Tree induction procedure, the class counts are weighted by W (c(x, y)). These counts initially consider that training instances are equally important and thus are all associated to equal weights. By modifying these weights, we modify the way each instance will be taken into account in these class counts. The choice of the splitting test will consequently be modified as for the whole tree structure and thus the resulting model. For further explanations of K setting, please refer to Forest-RK proposed by the authors in [START_REF] Bernard | Forest-RK: A new random forest induction method[END_REF].

As one can see in Algorithm 1, DRF procedure is inspired by boosting. Nevertheless, two differences should be highlighted. The first one is the use of randomization in the resampling process, i.e. performing bagging before boosting. More importantly, the second one concerns the way the weights are adapted: they are not updated according to the last induced tree only, but are entirely re-evaluated according to the whole forest at each iteration. The reason is that, unlike to boosting, we do not want the trees to be more and more specialized in previous prediction errors of the ensemble, but we want each tree to fit as well as possible the forest under construction. Boosting algorithms typically multiply the previous weights at each iteration by an update term that depends on the prediction errors of the last tree ( [START_REF] Freund | Experiments with a new boosting algorithm[END_REF]) : the weights progressively evolve to force the new trees to be more specialized in the classification of training instances particularly difficult to predict. This weighting strategy has the advantage to focus quickly on the wrongly classified instances, but has the drawback at the same time to lose the influence of the early trees and to make the ensemble more sensitive to noisy instances or outliers ([4]). On the contrary the key point of DRF as mentioned before is to keep a compromise between compensating previous errors and reinforcing correct predictions. Therefore, it is important to re-evaluate the weights according to the whole forest and not only to update them with the predictions of the last tree. This makes the evolution of the training sample weights slower and smoother than in boosting, thus rendering DRF less sensitive to noisy datasets.

All the choices described in this section define one procedure for the RF induction principle named Dynamic Random Forest. It actually establishes one example of how RF dynamic induction can be performed. However, as we will discuss in the conclusion, it is obvious that several other choices might work to induce accurate RF. Nevertheless, we will show in the following of this paper that this first algorithm of DRF is accurate and allows to significantly improve the traditional static RF induction.

Evaluation

To evaluate the DRF algorithm described in the previous section, we have compared it to the two following static RF induction methods: Breiman's reference method and a modified version called Forest-RK [START_REF] Bernard | Forest-RK: A new random forest induction method[END_REF] that compares favorably with Breiman's RF. This section presents our experimental protocol to do it so, and discusses the results obtained.

Experimental Protocol

In this evaluation, we have focused on two goals:

1. Evaluate and compare the overall performance of the forests induced with both dynamic and static induction algorithms; 2. Monitor the error rate evolution to analyze the DRF behavior according to the number of trees, in comparison with static-induced RF results.

Datasets

For those experiments, 20 datasets have been selected. They are described in Table 1. The first 17 datasets in this table have been selected from the UCI repository ( [START_REF] Frank | UCI machine learning repository[END_REF]), because they deal with different machine learning issues in terms of number of classes, number of features and number of samples. Three additional datasets on different handwritten digit recognition problems have been used: (i) the well-known MNIST database ( [START_REF] Lecun | Gradient-based learning applied to document recognition[END_REF]) with a 85 multiresolution density feature set (1 + 2 × 2 + 4 × 4 + 8 × 8) built from greyscale mean values as explained in [START_REF] Bernard | Using random forests for handwritten digit recognition[END_REF]; (ii) Digits and (iii) DigReject both described in [START_REF] Chatelain | A two-stage outlier rejection strategy for numerical field extraction in handwritten documents[END_REF], on which a 330-feature set has been extracted, made from three state-of-the-art descriptors, i.e. a 117-statistical/structural feature set [START_REF] Heutte | A structural/statistical feature based vector for handwritten character recognition[END_REF], a 128-feature set extracted from the chaincode (contour-based) ( [START_REF] Kimura | A lexicon directed algorithm for recognition of unconstrained handwritten words[END_REF]), and the same 85-feature set as for MNIST ([22])

Protocol

Each training subset has been used for building 3 different forests, with the following algorithms: Breiman's RF with K = √ M , Forest-RK and DRF. For each forest, the test error rates have been monitored each time a new tree was added to the ensemble. For that purpose, each dataset has been randomly split in two subsets, with two thirds of the data dedicated to train the forest, and the other third to test it. This splitting procedure has been repeated 10 times so that for each dataset, 10 different random training subsets are at our disposal. We denote these subsets

T i = (T r i , T s i ),
i = [1.
.10] and where T r i stands for the training subset and T s i for the test subset. For each T r i , we have grown 3 forests (Breiman's RF, Forest-RK and DRF), made of 500 trees. Thus for each dataset, 3 × 10 = 30 forests of 500 trees have been built. Usually, fixing the number of trees to 100 is considered to be reasonable for reaching the generalization error convergence with traditional RF algorithms ( [START_REF] Breiman | Random forests[END_REF][START_REF] Latinne | Limiting the number of trees in random forests[END_REF][START_REF] Bernard | On the selection of decision trees in random forests[END_REF]). In our expeiments, we set this number to 500 since we could not predict a priori the test error convergence speed according to the number of trees for this kind of dynamic induction process and could not even predict if it actually converges. Indeed the proof of the generalization error convergence given by Breiman in [START_REF] Breiman | Random forests[END_REF] is based on the hypothesis that the random vectors which define the randomization principle (see definition 1) are independent and identically distributed. But for the dynamic induction process these conditions are no longer verified, and the convergence is not proved anymore (this aspect is further discussed in section 4). Consequently, it was interesting to let the RF induction algorithm grow a large number of trees, in order to observe and compare convergence speed of the different algorithms tested.

Algorithm 2 sums up the whole experimental protocol. The next subsection presents and discusses the obtained results. Randomly draw without replacement 2 3 × N samples from the original dataset to form the training subset T r i . The remaining samples form the testing subset T s i . The couple (T r i , T s i ) is noted T i .

3:

h BRF [i] ← BreimanF orest(T r i , √ M , L) 4: ǫ BRF [i] ← error rate of h BRF [i] on T s i 5: h 0 RK [i] ← ∅, h 0 DRF [i] ← ∅ 6: for l ∈ [1..L] do 7: h l RK [i] ← h l-1 RK [i] RandomT ree(T r i ) 8: ǫ RK [i][l] ← error rate of h l RK [i] on T s i 9:
T l r i ← weighted T r i , as in algorithm 1.

10:

h l DRF [i] ← h l-1 DRF [i] RandomT ree(T l r i ) 11: ǫ DRF [i][l] ← error rate of h l DRF [i] on T s i 12:
end for 13: end for

Results

Table 2 presents the average test error rates of the final forests made of 500 trees obtained with each of the 3 algorithms used.

Datasets

BRF F-RK DRF Datasets BRF F-RK DRF Diabetes 25. [START_REF] Kimura | A lexicon directed algorithm for recognition of unconstrained handwritten words[END_REF] One can observe that the DRF algorithm exhibits lower error rates than Breiman's RF and Forest-RK for 19 of the 20 datasets. One can however mention an atypical result for one of the 20 datasets: madelon. This phenomenom can be explained by the way this database has been built. This artificial dataset was originally built for a feature selection challenge ( [START_REF] Guyon | Feature Extraction: Foundations and Applications[END_REF]) and contains data points grouped in 32 clusters, placed on the vertices of a five dimensional hypercube and randomly labeled +1 or -1; from these points, 20 informative features were extracted, while the 480 others are not discriminative at all. We think that this particularity of the feature space could explain the atypical results obtained with DRF and more generally with RF methods, since their performance depend on the intrinsic discriminative power of features chosen in the splitting test. For that reason, RF sometimes fail to filter irrelevant features, as explained for example in [START_REF] Geurts | Extremely randomized trees[END_REF]. Despite this particular case, those results prove that DRF outperforms Forest-RK and the classical Breiman algorithm for all but one dataset.

The results presented so far where about the "final" random forests made of 500 trees. But one of the main objectives with the design of our dynamic algorithm is to obtain a performance improvement while trees are added to the forest, faster and in a more straightforward way than with static RF induction. For studying the error variation during the forest construction, we represent in figure 2 the evolution of the test error rates according to the number of trees added throughout the RF induction processes, i.e. from the first tree up to the ensemble of 500 trees for both Forest-RK and DRF. For all the datasets, one can observe that curves have similar trends for both algorithms, even when the convergence is not obvious, as it is the case for the smallest datasets vehicle and diabetes. Besides, for all the other datasets, i.e. those where a convergence seems to be obtained, one can further note that the convergence is reached for the same number of trees. Hence, one can consider that DRF and Forest-RK have the same convergence properties. Now, one can observe that for all but one dataset (madelon), the DRF error curve is always under the Forest-RK curve. This can be explained by a faster decrease of the DRF curves within the first iterations, i.e. from 1 to about 200 trees.

On can also remark from figure 2 that for most of the datasets, DRF error rates progressively reach an horizontal asymptote in the same way as Forest-RK. This has a practical interest since it means that designing a stopping criterion based on performance will be possible for the DRF induction. This stopping criterion has not been included yet in the DRF process, but it is an important mechanism to design. Besides, it is one of our priority future works. For example, it is possible to use the out-of-bag estimates to foresee the amount of trees above which no more improvement is obtained with new trees, as it is done in [START_REF] Banfield | A comparison of decision tree ensemble creation techniques[END_REF]. In that way, the number of trees in the final forest could not be fixed a priori as a parameter but could be determined by the out-of-bag error rate evolution.

Discussion

The preceding section has shown that Dynamic Random Forest outperforms static algorithms like Breiman's one and Forest-RK thanks to adaptative resampling. However one can wonder if the main advantages of Random Forest algorithms are still kept with DRF methods. In particular, it is well known that RF are fast both in training and decision but also that they do not overfit. In the following, we discuss these issues in the case of DRF. Moreover RF are frequently used to evaluate variable importance and proximities for feature selection issues. We show that DRF can be used also for that purpose.

Overfitting and computation time

One of the main losses of DRF, in comparison with Breiman's RF, is that two of its main mathematical properties are not proved anymore. Indeed, the proof of the convergence of RF and the computation of the bound of the generalization error defined in [START_REF] Breiman | Random forests[END_REF] depend on the pre-required condition that trees are grown independently. In the DRF process, it is not the case and consequently those properties are not proved anymore. Without the pre-required condition of independency of trees, it is no more obvious to mathematically demonstrate that the generalization error convergence is always reached while trees are added to the ensemble, as it is proved with Breiman's RF. This is an important difference with Breiman's RF since, as a consequence, DRF are not proved to avoid overfitting while trees are added to the ensemble. Moreover, these new trees incorporate knowledge to better fit some training instances. Even if the criterion is computed on Out-of-Bag (OoB) error, which is considered to be a good estimate of the generalization error ( [START_REF] Breiman | Out-of-bag estimation[END_REF]), one can wonder if the risk of overfitting is not nevertheless increased. DRF is inspired by boosting by resampling, for which overfitting has been largely discussed during the past fifteen years ( [START_REF] Meir | An introduction to boosting and leveraging[END_REF][START_REF] Mease | Evidence contrary to the statistical view of boosting[END_REF]). Formal definition of boosting implies that it is strongly sensitive to overfitting, since it is based on making each new component classifier better fit the training instances. However, one of the main suprising results with boosting is that it rarely overfits in practice. This is supposed to be due to the averaging of component classifier outputs ( [START_REF] Mease | Evidence contrary to the statistical view of boosting[END_REF][START_REF] Breiman | Arcing classifiers[END_REF]). The only overfitting situations that have been observed in our experiments occur on the datasets for which the ratio between the number of samples and the number of features is very small (diabetes and vehicle). This phenomenon is also frequently observed with boosting, as shown in [START_REF] Wolf | Robust boosting for learning from few examples[END_REF]. Except these few overfitting situations, we believe that, as for boosting, DRF should rarely overfit. Moreover, although it would certainly need further investigations, we think that overfitting could be prevented with DRF thanks to a stopping criterion based on OoB error estimates : as OoB error rates are shown to give a reasonably good estimation of generalization error ( [START_REF] Breiman | Out-of-bag estimation[END_REF]), it can be used to stop the induction of the forest, avoiding it to be based on the training error rate evolution.

As far as computation time is concerned, RF is also known to be very fast in learning and in prediction. It is an important property since it is often used in applications for which computation times are critical (like for example in applications on video tracking [START_REF] Wang | An incremental extremely random forest classifier for online learning and tracking[END_REF][START_REF] Gall | Hough forests for object detection, tracking, and action recognition[END_REF]). In both Breiman's and DRF forests, time to predict a given input data point is proportional to the number of trees. As far as the learning stage is concerned, it is obvious that DRF takes longer to learn a single tree than in Breiman's RF, since additional computations are required for the weighting calculation. However, once the weights are computed, the tree growing in DRF is the same as a traditional random tree growing. Thus, the additional time for learning a DRF is proportional to its number of trees. As mentioned previously, one of the main advantage of DRF over Breiman's RF is to grow an accurate RF classifier with less trees.

Consequently, for reaching comparable accuracies with a RF, DRF will need to grow fewer trees than Breiman's RF.

Variable importance and proximities

RF methods have became popular during the last years because of their efficiency, but also thanks to the powerful tools they offer ( [START_REF] Breiman | Random forests[END_REF][START_REF] Robnik-Sikonja | Improving random forests[END_REF][START_REF] Geurts | Extremely randomized trees[END_REF]). Most of those tools are also available in DRF. For example, RF can be used to compute a variable importance measure, often set up for feature selection purposes ( [START_REF] Strobl | Bias in random forest variable importance measures: Illustrations, sources and a solution[END_REF][START_REF] Verikas | Mining data with random forests: A survey and results of new tests[END_REF][START_REF] Nicodemus | On the stability and ranking of predictors from random forest variable importance measures[END_REF]). This measure is obtained once the whole forest has been grown, by first measuring the OoB error, and by then permuting values of the variable of interest in OoB instances and re-measuring the OoB error. The difference between the two values gives an evaluation of the variable importance. This process is completely preserved in DRF, since the only difference with Breiman's RF is in the learning process. Once built, DRF still allows to compute variable importance, without the dynamic process affecting the results.

In the same way, proximities evaluation matrix is a popular tool of Breiman's RF that can be used with DRF. It allows to give a N * N matrix (N being the number of training instances) in which the element in line k and column l gives an evaluation of the similarity between instances k and l. It can also be used to compute the proximity of a new input point x to each of the training instances used to grow the forest ( [START_REF] Robnik-Sikonja | Improving random forests[END_REF]). It is obtained via implicit distances between data points underlined by the tree partitioning. This mechanism is still enabled with DRF, since, even if the dynamic resampling of DRF affects the tree growing, the resulting structure is still a correct partitioning of the input space. Thus, nodes (and particularly leaves) of the trees still underline proximities between instances belonging to them.

Conclusions

In this paper, a new method has been proposed for inducing Random Forest (RF) classifiers, named Dynamic Random Forest (DRF). It is based on a sequential procedure that builds an ensemble of random trees by making each of them dependent on the previous ones. This dynamic aspect of the DRF algorithm is inspired by the adaptative resampling process of boosting. The DRF algorithm exploits the same idea and combines it with the randomization processes used in "classical" RF induction algorithms.

The evaluation of a first variant of DRF has been led by comparing it to the Breiman reference algorithm, and a modified version named Forest-RK. Firstly, it shows that the DRF algorithm outperforms the static RF induction algorithms in 95% of the cases on the databases used in these experiments. Secondly, it shows that the DRF process allows to decrease the test error rate in a faster and more straightforward way than in static algorithms.

This later statement is supposed to be due to the adaptative resampling which makes the tree induction take into account the joint objectives of preserving the prediction confidence for well classified instances and of compensating prediction errors made by existing trees. The guidance method which has been chosen for that purpose has been inspired by boosting and seems quite natural to be used for this task. Nevertheless, one can imagine several other processes to have a tree induction be guided by the chosen criterion. For example, one can imagine applying the global idea of boosting to the features instead of or in complement to the training instances, in order to bias the choice of the splitting test. Our future works will concern the implementation of such a feature boosting-like process and a stopping criterion.

Figure 1 :

 1 Figure1: 10-fold cross-validation average error rates (in %) obtained during the SFS selection process on 6 datasets test (excerpt from experimental results given in[START_REF] Bernard | On the selection of decision trees in random forests[END_REF]). The blue curves represent the error rates obtained with SFS according to the number of trees selected in the 300-trees forest the error rate of which is represented by the red dashed line. The straight green line on the x-axis indicates the range of sub-forests that obtained a statistically significant performance improvement compared to the 300-trees forest and according to a McNemar.

N 3 :

 3 end for 4: for l from 1 to L do 5: T l ← a bootstrap sample, made with randomly sampled (with replacement) training instances from T , according to a uniform distribution 6: T l ← T l weighted with D l 7: tree ← RandomT ree(T l ) for all x i ∈ T do 11: if OoBT rees(x i ) = ∅ then 12:

Figure 2 :

 2 Figure 2: Evolution of the test error rates (in %) according to the number of trees added to the forest. Black curves represent the error rates obtained with Forest-RK and blue curves represent the error rates obtained with DRF

  Algorithm 1 Dynamic Random Forest Require: T the training set (x i , y i ) Require: N the number of training instances in T Require: M the number of features Require: L the number of trees in the forest to be built Require: W (c(x, y)) a weighting function inversely proportional to c(x, y) (see eq. 1) Ensure: f orest the ensemble of trees that compose the forest 1: for all x i ∈ T do

	2:

Table 1 :

 1 Description of the datasets

	with

  Algorithm 2 Experimental protocol Require: L the number of trees in each forest Require: N the number of training instances Require: M the number of features Ensure: ǫ BRF [10] a 1D table for storing error rates of RF induced with Breiman's algorithm using K = √ M . Ensure: ǫ RK [10][L] a 2D table for storing error rates of RF induced with Forest-RK. Ensure: ǫ DRF [10][L] a 2D table for storing error rates of RF induced with DRF.

1: for i ∈ [1..10] do 2:

  24.86 24.59 Mfeat-zer 21.55 21.50 21.05

	Digits	2.28	2.21	2.10 MNIST	4.97	4.95	4.61
	DigReject 7.27	7.31	6.56 Musk	2.62	2.53	2.41
	Gamma	11.99 12.09 11.74 OptDigits 1.65	1.60	1.51
	Isolet	5.35	5.38	4.96 Page-blo	2.70	2.71	2.64
	Letter	3.94	4.02	3.31 Pendigits	0.91	0.92	0.87
	Madelon	32.78 19.22 22.66 Segment	2.33	2.41	2.02
	Mfeat-fac 3.37	3.46	2.89 Spambase 4.88	5.03	4.04
	Mfeat-fou 17.61 17.06 16.83 Vehicle	25.60 25.50 25.07
	Mfeat-kar 3.36	3.39	3.23 Waveform 14.48 14.48 14.35

Table 2 :

 2 Average error rates (in %) of the RF made of 500 trees, for the 3 RF induction algorithms. Lowest error rates have been marked in bold for each dataset.