Omar Smail
email: omar.smail@univ-usto.dz

Bernard Cousin

Zoulikha Mekkakia

Rachida Mekki

A Multipath Energy-Conserving Routing Protocol for Lifetime Improvement of Wireless Ad Hoc Networks

Keywords: Ad hoc network, Multipath routing, Energy efficiency, Network lifetime

 routing

Introduction

An ad hoc network is characterized by frequent changes in the network topology, limited bandwidth availability, and limited power of nodes. The ad hoc network topology changes frequently as nodes are able to move collectively or individually and often in an unpredictable way. When one node moves out of or into the transmission range of another node, the wireless link between the two becomes down or up. Another cause of the topological changes is the instability of the wireless link quality, which might become high or low due to the signal fading (obstacles between the two wireless nodes), interference from other signals, or the change in the __________________________________________________ protocols. In [START_REF] Brown | Optimal power aware routing in a wireless ad hoc network[END_REF], it is shown that proactive protocols are very expensive in terms of energy consumption compared to reactive protocols, because of the large routing overhead incurred in the former. But reactive protocols suffer from high latency during the process of discovering fresh paths, especially in large networks and dense networks [START_REF] Marina | On-demand multipath distance vector routing in ad hoc networks[END_REF]. In recent years, the research community has focused on the improvement of ad hoc routing, with the development of several routing mechanisms. Multipath routing seems to be an effective mechanism in ad hoc networks with high mobility and high load to guard against the problem of frequent changes of the network topology caused mainly by link failures. The concept of multipath routing is that the source node is given the choice between multiple paths to reach a given destination. The multiple paths can be used alternately; the data traffic takes a single path at one time or several paths simultaneously. A multipath between a source and destination must be chosen wisely so that a path failure does not disturb other paths as less as possible. There are two types of disjoint paths: link disjoint paths and node disjoint paths. Node disjoint paths have no node in common except the source and destination. Link disjoint paths have no common links, while they may share some nodes. Any path of a multipath can be used to transmit a data packet between a source and a destination. Thus to maximize the data flow and to get a larger share of the network bandwidth, the data packets of a flow between a source and a destination can be split between the paths [START_REF] Chen | Distributed quality-of service routing in ad hoc networks[END_REF]. Multipath routing is highly suitable for multimedia applications, to ensure secure transmission and it is proposed for industrial ad hoc networks for improving reliability and determinacy of data transmission. Another benefit of multipath routing protocols is the reduction of the routing overhead, for which several multipath routing protocols have been developed [START_REF] Mueller | Multipath routing in mobile ad hoc networks: issues and challenges. Performance Tools and Application to Networked Systems[END_REF][START_REF] Tarique | Survey of multipath routing protocols for mobile ad hoc networks[END_REF][START_REF] Periyasamy | Survey of Current Multipath Routing Protocols for Mobile AD Hoc Networks[END_REF][START_REF] Zuo | A hybrid multi-path routing algorithm for industrial wireless mesh networks[END_REF]; these works propose a single path discovery process able to build several link or node disjoint routes towards the destination based on broadcast requests. The approaches in [START_REF] Fotino | Evaluating energy-aware behaviour of proactive and reactive routing protocols for mobile ad hoc networks[END_REF][START_REF] Chen | Multipath routing modelling in ad hoc network[END_REF] are improvements of single path routing protocols. They contribute in reducing delays and increasing throughput because they resist node mobility in comparison with single path approaches. In ad hoc networks, each node has a power battery and a limited energy supply. Over time, nodes deplete their energy supplies and are eventually removed from the network, which constrains the packet routing. Some exhausted nodes may be critical for packet transmission when they are involved in the only path from the source to the destination node. To solve this inefficiency, we propose a protocol which extends the lifetime of the network. We used the energy levels of nodes to classify the nodes of paths between a source and a destination. The node energy level is calculated based its residual energy and on nodes energy that contributes in the routing; this information is collected in the discovery of multiple paths using the same principle as in the discovery of a single path.

Two parameters are introduced, the energy threshold β and the coefficient α, to define the node class in order to preserve the consumed energy. Our protocol selects the nodes with similar classes to construct a given path. At the end of the route discovery process the source node will have a set of homogeneous paths in terms of energy. The best classified paths are selected to balance the energy consumed between the different paths of a multipath. The proposed technique discards nodes with a critical energy level and makes sure they do not participate in routing, otherwise we may have several links failures caused by the depletion of nodes. The paper is organized as follows. Section 2 provides a review of related works for energy-aware routing protocols in wireless ad hoc networks. Section 3 presents an overview of the AOMDV protocol and motivates its exploitation. Section 4 gives the design details of our AOMR-LM protocol. Section 5 provides the simulation results of its performance evaluation. Section 6 concludes this paper.

Energy-Aware Routing Protocols

The main objective of ad hoc routing protocols is to deliver data packets among network nodes efficiently, which depends on the node lifetime. The lifetime of a node is directly proportional to its battery's energy. The node battery's energy is primarily consumed while transmitting and receiving packets or computing. As ad hoc networks are multihop networks, one node may be involved in retransmission of packets sent between a source node and a destination node. The nodes participating in packet transmission, can exhausted their energies and removed from the network. This affects the reliability of the packet delivery service of the network. So in a multihop communication, the selection of the appropriate nodes by the routing protocol is very important. Thus, routing algorithms play an important role in saving the communication energy, this extends the life of the nodes and thus of the whole network. Many works focusing on energy-aware routing protocols exist in the literature [START_REF] Rodoplu | Minimum energy mobile wireless networks[END_REF][START_REF] Wang | An energy-aware probability routing in manets[END_REF][START_REF] Zhao | Energy efficiency of large-scale wireless networks: proactive versus reactive networking[END_REF][START_REF] Bao | Stable energy-aware topology management in ad hoc networks[END_REF][START_REF] Smail | Energy Conservation for Ad Hoc On-Demand Distance Vector Multipath Routing Protocol[END_REF][START_REF] De Rango | Link-stability and energy aware routing protocol in distributed wireless networks[END_REF]. These energy-aware routing protocols can be single path or multipath. In the following, the main proposed works about energy-aware single path routing protocols are described. In [START_REF] Singh | Power-aware routing in mobile ad hoc networks[END_REF] the authors presented several routing protocols with energy measurements that track energy efficiently. Minimum Total Transmission Power Routing (MTPR) [START_REF] Scott | Routing and channel assignment for low power transmission in PCS[END_REF] was initially developed to minimize the power consumption of nodes involved in a path. However, such protocols do not take node energy capacity into account. Thus, the energy consumption is not fairly shared among nodes in the network. Min-Max Battery Cost Routing (MMBCR) [START_REF] Toh | Maximum battery life routing to support ubiquitous mobile computing in wireless ad hoc networks[END_REF] considers the remaining power of nodes as a metric for the acquisition of paths in order to extend the lifetime of the network. But, this protocol cannot guarantee that the energy consumption will be minimized. The main advantage of on-demand routing comes from the reduction of the routing overhead, as a high routing overhead has a significant impact on the performance of wireless networks. An on-demand routing protocol attempts to discover a route toward a destination when a data packet is presented to be transmitted to that destination. Providing multiple paths for transmitting the data packets is beneficial in ad hoc network communications: it can be useful for improving the effective bandwidth of communication, reducing the routing overhead, and decreasing delivery delays. Recently, several on-demand routing multipath protocols have been proposed that preserve energy in order to avoid network failures as long as possible.

In [START_REF] Liu | Collision-constrained minimum energy node disjoint multipath routing in ad hoc network[END_REF], Liu et al. propose a new algorithm called Collision-Constrained minimum Energy Node disjoint multipath routing Algorithm for ad hoc networks (ECCA). The algorithm is a trade-off between collision avoidance and energy saving. It calculates an upper limit of the correlation factor depending on the service required and finds a disjoint multipath with energy which satisfies the upper limit. ECCA can significantly reduce the packet loss rate and the consumed energy. Hence, it attempts to provide energy savings at the nodes. But it does not take into account the power status of the nodes and thus the duration of availability of the network. The Multipath Energy-Efficient Routing protocol (MEER) [START_REF] Yuan | A multipath energy-efficient routing protocol for ad hoc networks[END_REF] uses a control mechanism for rational power. The route discovery process in which the source tries to discover routes with high energy is based on SMR (Split Multipath Routing) [START_REF] Lee | Split multipath routing with maximally disjoint paths in ad hoc networks[END_REF]. This protocol protects the nodes from consuming too much energy compared to the other nodes in the network. However the proposed approach is not based on disjoint routes, and thus it cannot exploit the benefits of path disjointness, which is useful to balance the energy consumption among network nodes. Max-Min Residual Energy (MMRE-AOMDV) [START_REF] Liu | Energy efficient on demand multipath routing protocol for multihop ad hoc networks[END_REF] is a multipath routing protocol based on AOMDV (Ad hoc On-demand Multipath Distance Vector) [START_REF] Marina | On-demand multipath distance vector routing in ad hoc networks[END_REF]. This protocol finds the minimal nodal residual energy of nodes of each path and then selects the path with maximal residual energy to forward the data packets. The MMRE-AOMDV protocol uses the routing information already available in the underlying AOMDV protocol. Thus little additional overhead is required for the computation of the maximal nodal residual energy in the route. The MMRE-AOMDV protocol has two main components: first the computation of the nodal residual energy of each route during the route discovery process, and second the sorting of routes by the descending order of their nodal residual energy. It uses the route with maximal nodal residual energy to forward data packets. Simulation results showed that the proposed MMRE-AOMDV routing protocol performed better than AOMDV in terms of packet delivery fraction, throughput, and network lifetime. But this protocol does not evaluate the energy consumption and its impact on network performance, knowing that the network life depends on the node expiration, which in turn depends upon energy consumption. In [START_REF] Liu | Multipath routing protocol for networks lifetime maximization in ad-hoc networks[END_REF], Liu et al. proposed the Multipath Routing protocol for Network Lifetime Maximization (MRNLM), a protocol that defines a threshold to optimize the forwarding mechanism. It proposes an energy-cost function and uses the function as the criterion for multiple path selection. During the transmission phase, they use a method called "data transmission in multiple paths one by one" to balance the energy consumption on the multiple paths. It is shown that MRNLM consumes less energy than AOMDV but does not improve the end-to-end delay. Multipath Multimedia Dynamic Source Routing (MMDSR) [START_REF] Aguilar Igartua | Self-configured multipath routing using path lifetime for video-streaming services over ad hoc networks[END_REF] is a multipath routing protocol able to self-configure dynamically according to network states. The authors used cross-layer techniques to improve the end-to-end performance of video-streaming services over networks using IEEE 802.11e. MMDSR uses an analytical model to estimate the path error probability. This model is used by the routing scheme to estimate the lifetime of paths. In this way, it is hoped that proper proactive decisions can be taken before the paths are broken. However, the comparison with DSR (Dynamic Source Routing) is not fair since it is not a multipath routing protocol. The Multipath Energy Efficient Routing Protocol (MEERP) [START_REF] S V Gole | Multipath energy efficient routing protocol[END_REF] is an extension of the existing routing protocol AOMDV. Route discovery is modified in MEERP, whereby each intermediate node is prohibited from generating a route reply message. The proposed protocol selects energyefficient multiple node disjoint paths based on the residual energy and successful transmission rate. In this algorithm, multiple routing paths are selected. However, only one path is used for data transmission at a given time. During the pathdiscovery process, each intermediate node calculates the cumulative node cost until the destination, and the path with the highest cost is selected. This cost depends upon two measurements: the successful transmission rate and the residual energy of the node. The simulation results show that the proposed scheme can achieve a great improvement of the network lifetime by reducing end-to-end delay and overhead. In [START_REF] Nasehi | Improving energy efficiency in manets by multi-path routing[END_REF], the authors propose a multipath routing protocol based on AODV routing algorithm (ZD-AOMDV). The represented protocol in this study tries to discover the distinct paths between source and destination nodes with using Omni directional antennas, to send information through these simultaneously. This protocol counts the number of active neighbors for each path, and finally it chooses some paths for sending information in which each node has lower number of active neighbors all together. Here, active neighbors of a node are defined as nodes that have previously received the RREQ (Route Request).The aim of this work is to try to improve the energy efficiency of ad hoc networks. All of the above studies solve the problem of energy conservation, but the majority of power-saving mechanisms are based only on the remaining power cannot be used to establish the best route between source and destination nodes. On one hand, if a node is willing to accept all route requests only because it currently has enough residual battery capacity, too much traffic load may be routed through that node. On the other hand, excessive energy savings neglects the power consumption at the individual nodes, it results network partitioning due to nodes battery exhaustion. Indeed, it reduces network performance. Hence, shared and balanced energy consumption is a remedy for those types of problems. Finally, the majority of these protocols have been compared only with original protocols (AODV, AOMDV, DSR, SMR, ...), which do not explicitly consider energy consumption, and thus these performance evaluations are not fair. We will use ZD-AOMDV [START_REF] Nasehi | Improving energy efficiency in manets by multi-path routing[END_REF] as a reference for our performance evaluation because it aims to improve the lifetime of the ad hoc network and has the same characteristics as our protocol, namely its reactivity, multipath character, and use of AOMDV as its basic protocol.

AOMDV Overview

The existing routing protocols in ad hoc networks such as proactive and reactive protocols can be modified to incorporate a power control function which prolongs the network lifetime and optimizes energy consumption. We chose AOMDV (Ad hoc On-demand Multipath Distance Vector) [START_REF] Marina | On-demand multipath distance vector routing in ad hoc networks[END_REF] as the basis for our protocol. AOMDV has been proven to be a good protocol that uses multipath routes; all of its paths are disjoint paths and it can guarantee a loop-free path because it allows only alternate routes with lower hop counts. The AOMDV protocol performs a route discovery process between the source node and the desired destination node when the source needs to send a data packet and the path to the destination is not known. In this process, route query (RREQ) messages are broadcasted by every node in the network. The destination sends a route reply (RREP) message for all of the received RREQ packets. An intermediate node forwards a received RREP packet to the neighbor that is along the path to the source. This discovery process can be exploited to collect fresh node information, such as residual energy, load level, and so on. Several studies [START_REF] Parissidis | Multipath routing protocols in wireless mobile ad hoc networks: a quantitative comparison[END_REF][START_REF] Malini | Traffic based energy consumption analysis of AOMDV protocol in a mobile ad hoc network[END_REF][START_REF] Periyasamy | Performance evaluation of AOMDV protocol based on various scenario and traffic patterns[END_REF] have shown that the AOMDV protocol is more robust and performs better in most of the simulated scenarios. So we selected this protocol, instead of any other reactive protocol (such as SMR [START_REF] Lee | Split multipath routing with maximally disjoint paths in ad hoc networks[END_REF]), as the reference for performance evaluation of our protocol.

The Ad hoc On-demand Multipath Routing with Lifetime Maximization protocol

In this section, an improved routing protocol, named Ad hoc On-demand Multipath Routing with Lifetime Maximization (AOMR-LM), is presented. AOMR-LM is a multipath routing protocol based on AOMDV protocol, with a new path classification mechanism according to the energy level of the nodes forming these paths, which can be high, average, or low. The idea is to build homogeneous paths in terms of energy, this can balance the consumption energy of nodes and avoid link failures due to nodes energy depletion. The protocol sets an energy threshold and a coefficient, used to define the class of each node. These parameters are required to forward the reply packet decision. This idea helps at prolonging the network lifetime and improves the energy performance in mobile ad hoc networks. In the single path routing AODV protocol, maintenance of paths occurs by sending periodic short messages (called HELLO message). If three consecutive HELLO messages are not received by a node from a neighboring node, the node considers the link to be broken. When the node receives a data packet which should be routed via this broken link, a route error message (RERR, Route ERRor) is sent back to the packet source indicating the broken link. In this case a new path discovery process needed, which adds an extra cost in terms of delay, throughput, control messages, and considerable energy consumption for the additional transfer of control messages. Among the reasons of failure of a node is the limitation of its battery energy. Due to these node failures, links in a path may become temporarily unavailable and make the path invalid. The routing algorithm decides which of the network nodes need to be selected in a particular path. Selection of nodes without taking into account the node energy when determining the paths leads to an umbalanced energy level in the network. Nodes on the minimum energy paths could quickly become drained while other nodes remain intact. This will result in the early death of some nodes. For this purpose, multipath routing has been shown to be effective since it distributes the traffic load among more nodes and in proportion to their residual energies. When the energy consumption among nodes is more balanced, the mean time to node failure is prolonged and so the network lifetime. The proposed AOMR-LM protocol is a reactive protocol for multipath routing. Our selection mechanism preserves the residual energy of nodes and balances the consumed energy. This prolongs the network lifetime and improves network performance. In the next sections, we first introduce define some assumptions and then provide the main details of multipath discovery, selection, data transmission, and maintenance procedures.

Problem definition

An ad hoc wireless network is represented by an undirected graph, G = (V, E), where V is the set of network nodes and E is the set of network bidirectional links. Let w(u), u ∈ V, represent the residual energy at node u. Let c(u,v),(u,v)∈ E, be the energy required to transmit a packet from node u to node v. We assume that c(u, v) = c (v, u) for all (u, v) ∈ E. If P is any set of paths of G; then we consider P(u 0 , u n ) to be the set of paths between nodes u 0 and node u n . Let P i (u 0 , u n ) = u 0 , u i1 , . . ., u im , . . ., u n , be the i th path in P(u 0 , u n ) , the source node is noted by u 0 or u i0 and the destination node is noted by u n or u in . We define ) , ( 0 n i u u P as the number of nodes on the path P i (u 0 , u n ) and ) , ( 0 n u u P as the number of paths in the multipath discovery process. The sum of the residual energy of a path P i (u 0 , u n ), denoted by e sum (P i (u 0 , u n )) is given by:

( ) ( ) ( ) ∑ = in i u u j i n i sum u w u u P e 0 , 0 (1)
We consider e sum (P(u 0 ,u n )) to be the sum of the residual energies of all paths belonging to the set P(u 0 ,u n ):

( ) ( ) ( ) ( ) ∑ = ) , ( 0 0 0 , , n u u P n i sum n sum u u P e u u P e (2)
Let e average (P i (u 0 , u n )) be the average residual energy of one node belonging to a path, e average (P i (u 0 , u n )) is given by:

( ) ( ) ( ) ( ) (
)

n i n i sum n i average u u P u u P e u u P e , , , 0 0 0 = (3)
The average residual energy of a set of paths between a same pair of nodes is denoted by e averageNet (P(u 0 ,u n )), which is the average residual energy of nodes that participated in the multipath discovery process between one source node u 0 and one destination node u n, e averageNet (P(u 0 ,u n )) is given by: , the energy level of node u j during a discovery process between a source node u 0 and a destination node u n , given by: ( )

( ) ( ) ( ) ( ) ( ) ∑ = n i n sum n averageNet
)) , ( ( ) (
Given a source s, a destination d, and a data packet to be routed, the source initiates the multipath discovery. This discovery provides multiple disjoint paths with energy efficiency properties. The path selection is based on the residual energy level of its nodes to preserve the node energy; and to balance the energy consumed over a large set of paths we choose to classify paths and transmit the data by choosing one path of the available highest class.

Multipath discovery

Based on the on-demand routing scheme, the source node starts the multiple paths discovery process to create a set of paths able to forward data towards the destination node from the source node. When a source requires a route toward a destination, the source checks its routing table for any available path toward this destination. If a path is not present or is invalid, the source performs route discovery: it broadcasts an RREQ (Route Request) message to all of its neighbors. When a node receives an RREQ, it ensures that the received RREQ is not a duplicate RREQ by comparing the RREQs' identifiers, in order to prevent looping paths. Otherwise, the RREQ-receiving nodes verify whether they have any valid path toward the destination in their routing tables. If they have, they forward the RREQ to those valid path neighbors. In this case, for our protocol, returning back a RREP (Route Reply message) to the source is not desirable because we would like to collect fresh energy information. Otherwise, the receiving node retransmits the RREQ message to all of its neighboring nodes to find the paths toward the destination. When the destination receives the first RREQ, it waits for a certain time and collects all other RREQs arriving during this time interval. Our protocol uses the destination sequence number in the same way as AOMDV to indicate the freshness of the route, which ensures loop-freedom. Moreover, we use the notion of an advertised hop count to maintain the multiple paths for the same sequence number. The advertised hop count contains the hop count of the longest path allowed. Once the sequence number changes, the advertised hop count is reset and remains unchanged for this sequence number. Indeed a node builds an alternate path to a certain destination node via a neighboring node only if this alternate path has a smaller advertised hop count.

Several changes are needed in the AOMDV route-discovery procedure to enable computation of the sum and average nodal residual energy of the network. Each RREQ now carries an additional field, called e sum (P i (u 0 , u j )), which represents the sum of residual energy from the source to the current node u j . Another field w(u) is added, so that a node knows the residual energy of its neighbors. When an intermediate node receives an RREQ, it increases the field e sum (P i (u 0 , u j )) by the value of its residual energy. The multipath discovery must take into account the message sequence number in order to ensure the freshness of paths and the maximum hop count for all the paths, denoted respectively by seqnum and advertised_hopcount. Any RREQ message received with a sequence number lower than the largest sequence number received in any previous RREQ message from that source towards that destination is discarded. The same process is repeated until the RREQ message reaches its final destination; see Algorithm 1.

Algorithm 1: AOMR-LM path discovery process

Figure 1 shows the structure of an entry of the routing table of a node. For each destination known by the node there is an entry. Route_list contains all known neighboring nodes of a node which leads to that destination. Each neighbor for that destination is identified its nexthop address, and the hopcount field is the number of hops required to reach that destination using this neighbor. We add two new fields, w(u) and marked_node, in the route_list. The field w(u) denotes the residual energy of a node and the field marked_node indicates whether or not a node has been selected by a reverse path (explained later).

Multipath selection

After reception of the first RREQ packet, the destination node waits for a certain period of time RREQ_Wait_time before starting the route selection procedure. This period of waiting generates an additional delay for the multipath routing selection. However the results of the evaluations (Section 5) demonstrates its low impact on end-to-end delay. When this ((advertised_hopcount d i ,i)>(advertised_hopcount d j ,j)) then e sum (P(u 0 , u j )):= e sum (P(u 0 , u j ))+w(u i ); insert ( j , advertised_hopcount d j +1, w(u j )) into route_list d i ; endif Destination Sequence_number Advertised_hopcount Route_list {(nexthop1, hopcount1, w(u 1 ), marked_node), (nexthop2, hopcount2, w(u 2 ), marked_node), …} Expiration timeout period of time expires, the destination node generates a route reply (RREP) message and sends it back to the source. In the conventional AOMDV, the propagation of route request messages from the source towards the destination establishes multiple paths. However, it does not consider the residual energy of nodes. In our protocol, the energy of a node w(u j ) is considered when the RREP packet is forwarded back. So the selection of the next node toward which the RREP packet is forwarded depends on the node class. To determine the belonging of a node to one of the three classes, we define two thresholds, denoted α and β. α being the lower threshold which separates the low class from the middle class, β the upper threshold which separates the middle class from the upper class. The energy threshold β is computed for all network nodes. So for our solution, we assume that the threshold β is the average residual energy of the network. If the energy of node u j (i.e. w(u j )) is above the threshold (w(u j ) ≥ β), the node u j has a high probability of being able to transmit data packets, and thus it is classified as high class. When w(u j ) < β, the definition of the node class depends on the threshold β and the coefficient α, which is necessary for the forward decision. The coefficient α is introduced to determine the node's capacity to support data traffic in terms of energy. This coefficient decides the node participation in routing.

When w(u

j ) < β then 1 ) ( < β j u w . Let 1 < α ; we obtain: 1 ) ( * < β α j u w (6)
To analyze the values of the coefficient α, we define T Net (P(u 0 ,u n )), which describes the effective participation of K network nodes in the transfer of data on paths of P(u 0 , u n ). The rest of the nodes do not affect the data transfer, so they will not be considered in the formulation of our solution. We have:

∏ = = K j j n Net u w u u P T 1 0 ) ( * )) , ( (
β α ∏ =         ≤ K j j K u w 1 ) ( * β α
Applying the inequality of arithmetic and geometric means

α α α α α α α α n n n n x x x x x x ... ... 2 1 2 1 2 2 1 1 ≥ + + + where 0 ... 2 1 > + + + = n α α α α , if we take 1 , = = i K n α , and
) ( i i u w x = we obtain K K j j u w 1 1 ) (         ∏ = ∑ = ≤ K j j u w K 1 )) ( 1 ( Then we have ∏ =         K j j K u w 1 ) ( * β α ∑ =         ≤ K j K j K u w K 1 )) ( 1 ( * β α which proves that ( ) ( ) ∏ = = K j j n Net u w u u P T 1 0 ) ( * , β α ∑ =         ≤ K j K j K u w K 1 )) ( 1 ( * β α
To simplify the analysis, we pose

∑ = K j j K u w 1 ) ( (
)

) , ( 0 n averageNet u u P e ≈
, since the sum of the residual energy of nodes divided by the number of nodes gives the same value calculated by Equation ( 4). It is considered that if the residual energy of a node is greater than the average residual energy of the network, then this node has sufficient energy and has a high probability of transmitting more data packets before being exhausted. This case corresponds to (w(u j ) ≥ β), so:

( )K Net T 1 ≥ α (8)
Following [START_REF] Belding-Royer | Routing approaches in mobile ad hoc networks[END_REF], we obtain ( )

j u w β α < (9)
With ( 8) and ( 9), we have ( )

        ∈ ) ( , 1 j K Net u w T β α (10)
After receiving an RREP message, an intermediate node checks whether the RREP message has already been received (the intermediate node identifies each RREP message by the IP address of the originating node, and the destination sequence number in order to detect a duplicate message). If the RREP message has already been received (or is older than an already received RREP message), the node discards it directly; otherwise it calculates the energy levels of all neighboring nodes and determines their classes. Our idea is to classify nodes according to their energy levels. When the value of w(u j ) of node u j is high and Equation ( 7) is used, this case is reduced to e level (u j )≥ 1. Three classes of nodes are defined:

Low: The energy level of the node is below α. Average: The energy level of the node is between α and 1.

High: The energy level of the node is greater or equal to 1. In the AOMDV protocol, the intermediate node establishes a reverse path by selecting the first neighboring node from the route_list field of the routing table (see Figure 1). In our protocol the intermediate node determines the class of each neighboring node stored in the table and forwards the RREP message to the neighboring node of the same class. If the classes of all neighboring nodes are different from the class of the intermediate node, the neighboring node with the lowest class above the class of the intermediate node is selected; if no higher class exists, the neighboring node with the highest class under the class of the intermediate node is selected. This process is repeated at every intermediate node until the source node. At the end of the process all discovered paths have same or near nodes classes, this results in homogeneous paths. The source node will have all paths energy information, this facilitates the paths selection for routing. To ensure link disjoint paths, an intermediate node marks each neighboring node selected by another reverse path; this property is ensured by the marked_node field of the routing table (see Figure 1); in addition our solution evaluates the energy level of each node, so the exhaustion of a node is considered and does not affect the links of paths. The trajectories of each RREP message may intersect at an intermediate node, but each takes a different reverse path to the source to ensure link-disjointness. When the node source receives the first RREP message for a destination, it waits a specified time, called RREP_Wait_time, before selecting the best path; this time is an additional delay for multipath routing protocols.

Data transmission phase

The choice of the best path between a source node s and destination node d depends on the energy levels of nodes. AOMDV transmits data packets using the first path from the list of available paths when multiple paths are established. In AOMR-LM protocol, paths are grouped by class (high, average, and low) according to the classes of nodes that build these paths. The paths of high class are selected first to forward the data packets. In this case, all packets going to the same destination follow the same path as long as there is no link failure in this path. Once the high class is empty, the algorithm selects any path of the average class. The same process is repeated with the low class. This process balances the nodes energy consumption which extends the network lifetime. One path is selected at a time for a data packet transmission between a source and a destination. If the selected path fails, the source node receives a RERR; in this case, a path is selected from the highest available class. Path discovery is initiated again when there are no more paths; this discovery process is described in Section 4.2.

Route maintenance

Route error detection in AOMR-LM is similar to route error detection in AOMDV. It is launched when a link fails between two nodes along a path from a source to a destination. When a neighboring node does not respond to three successive HELLO messages sent by a node, the link is considered to have failed. If a node detects a failure of a link in an active path, it erases the route from its table and then sends an RERR message to the source node of the path. Each intermediate node returns this RERR message along the reverse path to the source node. When a source node receives an RERR message, it erases the path from its table and looks for an alternate path towards the destination node, if one is available; otherwise it initiates a path discovery process to resume the data transmission. An alternative path is selected as described in Section 4.3.

Performance Evaluation of AOMR-LM

In this section, we present simulation results to demonstrate the efficiency of our proposed protocol. First we present the metrics used for performance evaluation and then we analyze the values of coefficient α to select the most appropriate value for the rest of the simulations; this value allows us to classify nodes according to their energy levels. Finally we evaluate our protocol by comparing it with two protocols in the literature, namely AOMDV and ZD-AOMDV. This evaluation is accompanied with an analysis and discussion of results.

Performance parameters

We evaluate three key performance metrics. The network lifetime can be defined in three ways [START_REF] Bheemalingaiah | Energy aware node disjoint multipath routing in mobile ad hoc network[END_REF]: the time taken to exhaust the battery of the first network node, the time taken to exhaust the battery for N network nodes, and the time when the battery of the last network node is exhausted. We choose the second way. Energy consumption is the average of the energy consumed by nodes participating in packets transfer from the source node to the destination node during the whole simulation. End-to-end delay is the average transmission delay of data packets that are delivered successfully over the total duration of the simulation.

Analysis of the coefficient α α α α

In our protocol the choice of the path used by a source node to transmit data packets toward a destination node is based on the path class, which depends on the classes of nodes belonging to this path. In our protocol, the class definition of a node is mainly affected by the value of α. In order to find appropriate values of α, we apply Equations ( 8) and [START_REF] Brown | Optimal power aware routing in a wireless ad hoc network[END_REF] to find the minimum values to define mainly two classes (low and average). The maximum value of α is determined by the equation ( 9), we have not studied this case, because in our work the third class (high) is determined by the value of β. We assume that if the number of nodes participating in the transfer of data is near to K, then the value of T Net approaches zero.

Table 1 shows α min values measured by varying K from 10 to 100 nodes. In Figure 2 we can see that α min increases with K, and tends toward zero as K becomes small, therefore α min is a function of K when T Net tends to zero. For a network size of 190 nodes, the number of nodes used for transferring data packets from a source node to the destination node is between 30 and 40 (corresponding to K of Table 1) [START_REF] Meghanathan | A node disjoint multi-path routing protocol based on location prediction for mobile ad hoc networks[END_REF]. For the simulation of our protocol AOMR-LM, we chose 190 as the network number nodes; hence our choice of α min = 0.42.

Performance evaluation

We carried out simulations to determine the effectiveness of our protocol. The principal goal of these simulations is to analyze our protocol by comparing it with other protocols, mainly AOMDV [START_REF] Marina | On-demand multipath distance vector routing in ad hoc networks[END_REF] and ZD-AOMDV [START_REF] Nasehi | Improving energy efficiency in manets by multi-path routing[END_REF]. The values of simulation parameters are summarized in Table 2. To evaluate AOMR-LM, we use the network simulator ns-2 [START_REF]The Network Simulator ns-2[END_REF]. Each simulation run has a duration of 300 seconds.

During each simulation, constant bit rate (CBR) connections are generated; each of them produces four packets per second with a packet size of 512 bytes. The values of RREQ_Wait_Time and RREP_Wait_Time are set to 1.0 seconds, the same value as that used for the protocol AOMDV [START_REF] Marina | On-demand multipath distance vector routing in ad hoc networks[END_REF].

We vary the number of network nodes from 30 to 190 to obtain different scenarios in an 840 m × 840 m environment.

The Random Waypoint model is used to simulate node movement; each node moves with a speed randomly chosen from 0 to 5 m/s. The radio model uses characteristics similar to a commercial radio interface, Lucent's Wave LAN. Wave LAN [START_REF] Feeney | Investigating the energy consumption of a wireless network interface in an ad hoc networking environment[END_REF] is a shared-media radio with a nominal bit-rate of 2 Mbit/s and a nominal radio range of 250 m, which is compatible with the IEEE 802.11 standard. Each simulation is carried out under a different number of network nodes and the performance metrics are obtained by averaging over 20 simulation runs from one source to one destination randomly selected. We assume that a node consumes 281.8 mW while receiving and 281.8 mW while transmitting [START_REF] Jung | A power control MAC protocol for ad hoc networks[END_REF]. It was shown in [START_REF] Kim | Routing mechanisms for mobile ad hoc networks based on the energy drain rate[END_REF] that no real node energy optimization can be achieved in the presence of overheating or in idle state. For this reason, the energy consumption during idle or overheating time is not considered in this model. In our simulations, we initialized the energies of the nodes randomly between 10 and 60 Joules (uniform distribution), which corresponds to the average capacity of a battery. We evaluate the performance of AOMR-LM by comparing it with the AOMDV and ZD-AOMDV routing protocols. The network lifetime metric is shown in Figure 3 with the number of network nodes equal to 190. The network lifetime of AOMR-LM is longer than those of AOMDV and ZD-AOMDV. Our protocol exhausts fewer nodes compared to ZD-AOMDV and AOMDV protocols, which increases the lifetime of the network. Thus AOMR-LM balances the energy among all the nodes and prolongs the individual node lifetime and hence the entire network lifetime. Figure 4 shows the energy consumed in different scenarios by the AOMR-LM, ZD-AOMDV, and AOMDV protocols. AOMR-LM does not perform too well at the beginning of the simulation, but it improves later. Initially, it is not better than any other protocol, because initially the majority of data packets are not yet transmitted, so the total energy of sending and receiving packets is not important. But in the last stage, as time increases, there is some imbalance of energy that comes into play and then the impact of our algorithm comes into play. We can see that the energy consumed in AOMR-LM is less than those consumed by ZD-AOMDV or AOMDV. AOMR-LM consumes less energy than ZD-AOMDV or AOMDV, firstly because AOMR-LM is able to balance the energy between paths. Thus energy is balanced out across the network, reducing uneven energy consumption. Secondly, AOMR-LM is able to avoid nodes with low energy in the construction of the multipath. This means that paths with higher energy are identified and selected for transmission.

Figure 5 shows the average end-to-end delay of the compared protocols. The average end-to-end delay for all tested protocols increases when increasing the network size, but the average end-to-end delay of AOMR-LM is lower than those of ZD-AOMDV and AOMDV, for different nodes speeds, see When the number of nodes is less than 70 Figure 5 (a) and (b), the protocol ZD-AOMDV protocol has a delay equal or slightly better than our protocol, due to the simultaneous use of paths. Once the size of the network increases, our protocol produces a better delay, this for any nodes speed. The reason is that our AOMR-LM protocol favors nodes having a high energy level and prevents the critical nodes from participating in the data packet transmission. This produces fewer broken links and greatly reduces the end-to-end delay.

Conclusion

In this article we have provided a solution to the problems of routing in an ad hoc network. Mobile ad hoc networks are characterized by their lack of infrastructure and their dynamicity: link failures and route breaks occur frequently. Moreover, the frequent changes of topology exhaust the batteries of the nodes, which decreases the network performance. A new multipath routing protocol, AOMR-LM, has been proposed in this paper, performing energy aware routing in mobile ad hoc networks. We has shown that AOMR-LM conserves the residual energy of nodes and balances the consumed energy over multiple paths. AOMR-LM routing protocol is an extension of the existing multipath routing protocol AOMDV. It uses an energy-aware mechanism, which exploits the residual energy of nodes to select and classify the paths according to the energy level of their nodes. This concept extends the network lifetime and improves energy consumption when compared with other solutions known in the literature. The coefficient α is analyzed in order to find appropriate values, which are required to define the class of a node during the reply-forwarding process and to preserve the node residual energy. Comparing the performance of AOMR-LM with those of the AOMDV and ZD-AOMDV protocols, AOMR-LM is able to balance the energy consumed. It increases the lifetime, consumes less energy and has a lower average end-to-end delay than the other simulated protocols, because paths are computed depending on the energy level of their nodes, and the one of the best paths is selected. In the future we plan to study the cooperation of our routing protocol with a MAC layer power-control technique to see how they can cooperate to decrease the energy consumption of ad hoc networks.

Figure 1 :

 1 Figure 1: Structure of a routing table entry for AOMR-LM.

Figure 2 :

 2 Figure 2: α α α α min versus K.

Figure 3 :

 3 Figure 3: Network lifetime versus number of exhausted nodes.

Figure 4 :

 4 Figure 4: Energy consumed versus time.

  Figures (a) and (b).

Figure. 5 :

 5 Figure.5: End-to-end delay versus number of nodes.

Table 1 :

 1

		Measuring α α α α min relative to the number K.
	K	10	20	30	40	50	60
	α min 0.155 0.289 0.396	0.499	0.574	0.629
	K	70	80	90		100
	α min	0.672	0.707	0.734	0.757

Table 2 : Simulation parameters.

 2

	Communication Model	Constant Bit Rate (CBR)
	MAC type	IEEE 802.11
	Mobility model	Random Waypoint
	Terrain range	840 m × 840 m
	Transmission range	250 m
	Number of mobile nodes	30 to 190
	Data payload	512 bytes
	RREQ_Wait_Time	1.0 s
	RREP_Wait_Time	1.0 s


Bernard Cousin

Joel Christian Adépo

Michel Babri

Souleymane Oumtanaga

Tree Reconfiguration without Lightpath Interruption in WDM Optical Networks with Limited Resources

Keywords: Path reconfiguration, optical WDM network, multicast tree, reconfiguration sequence, lightpath interruption. I

come

Introduction

Path reconfiguration is used by network operators to improve network performance. It consists of moving from an initial path to a new one. Since networks are disturbed by failures, overloads, and deployments of new network resources or maintenance operations, network reconfiguration becomes very important because it enables the fulfillment of QoS requirements with the available network resources. In our previous work (Cousin et al.), we presented an efficient algorithm which achieves tree reconfiguration in WDM optical networks in which a multicast connection is established. It was the first work on that problem in the literature. The objectives of this work are: first, tree reconfiguration without data flow interruption; second, reduction of the latency between the triggering event and the effective reconfiguration of the nodes on the paths by the tree reconfiguration process; and third, reduction in the resources used during the reconfiguration by the tree reconfiguration process. In our previous work, we proposed a branchby-branch process called BpBAR_2. In that approach, the number of available wavelengths per link was not considered as a constraint. At each step of the reconfiguration process, the proposed algorithm computed a light-forest to span all the destinations. Since the network resources are supposed to be umlimited, the number of trees per light-forest is also unlimited. In this current work, the number of available wavelengths per link is a constraint. So, the number of trees per light-forest produced at each step should be limited. This constraint first allows the tree with the available network resources to be reconfigured, and second, contributes to optimizing the network resources used. The problem addressed in this paper is tree reconfiguration without data flow interruption in a network with a limited number of available wavelengths per network link. The proposed algorithm must maintain the continuity of the data flow toward all the destination nodes and reduce the cost of resources used and the duration of the reconfiguration process.

In Section II, we describe the tree reconfiguration in WDM optical networks. Section III presents the related works. In Section IV, we prove the continuity of data flows during the reconfiguration with the BpBAR_2 process. Section V presents the context of tree reconfiguration with limited resources and the proposed algorithms called TRwRC. Section VI presents the evaluation criteria and the results of the evaluation. This algorithm allows tree reconfiguration in a network which has limited resources and it reduces the resource cost during the reconfiguration. Finally, we conclude this article in the final section.

II. Multicast Connection in WDM Optical Networks

The path of a connection in WDM optical networks [START_REF] Mukherjee | WDM Optical Communication Network: Progress and Challenges[END_REF] consists of optical channels. An optical channel in a WDM optical network is an optical signal transmitted over one wavelength in one fiber. The ends of an optical channel consist of an output port of a switch called the source port and an input port of another switch called the sink port. If the source port belongs to a node, then this node is the source node of the optical channel. If the sink port belongs to a node, then this node is the sink node of the optical channel.

A lightpath is an all-optical path on the same wavelength between two nodes: a lightpath is made of a set of successive optical channels. The set of paths used by a multicast connection [START_REF] Ding | A survey of optical multicast over WDM networks[END_REF][START_REF] Malli | Benefit of Multicasting in All-Optical Networks[END_REF] in a WDM optical network forms a tree called a light-tree. A light-tree is an all-optical structure on the same wavelength between a source node and a set of destinations nodes.

The light-tree is obtained with the use of particular nodes which are capable of duplicating an incoming light signal from one node input port into one or several node output ports. In this work, we assume that all network nodes have this light splitting capability. In Zhou (2009), the reader may find some interesting considerations when this assumption is not fulfilled, and may find some efficient computation heuristics or protocols in [START_REF] Zhou | Cost Bounds and Approximation Ratios of Multicast Light-trees in WDM Networks[END_REF] and [START_REF] Jawhar | Effect of Splitting Factor on the Generated Multicast Trees in Optical Networks[END_REF]. A structure called a light-forest is used when a single light-tree is not sufficient to cover all destinations. A light-forest is a set of light-trees originated at the same source node but established with different wavelengths. For example, and are the two light-trees of the light-forest in Fig. 1 between the source node s and the destinations { , , }. is established with a wavelength between the source node s and the destination { }. is established with a wavelength between the source node s and the destination { , }. A branch , , of the lightforest is a lightpath between the source node s and the destination on the tree T.

In a WDM optical network, before transmitting data from a source s to a destination , a connection has to be set up first along the path from s to . This connection is established by allocating a wavelength on each link along the connection's path and each node is instructed to switch the wavelength transparently through its switch fabric. We called this path with the allocated wavelength a pre-established path. A preestablished path between node y and the destination is denoted , ). , ) in yellow in Fig. 1 is a preestablished path between s and .

If there is no confusion, a tree will be noted and a pre-established , will be noted .

Fig. 1 Light-forest between the source node s and the destinations { , , } and the pre-established path (in yellow) between s and d 3 .

The key characteristic of the multicast in optical networks is that an optical channel can be shared to feed multiple output ports and reach many destinations. In Fig. 1, the optical channel between s and B is shared to reach the destinations d 1 and d 2 . B becomes a branching node. An optical channel which has B as a sink node is an upstream optical channel of B. An optical channel which has B as a source node is a downstream optical channel of B.

The number of upstream optical channels of a node x on a tree is noted | |. The number of downstream optical channels of x is noted | |.

A branching node x of a light-tree is such that its number of downstream optical channels is superior or equal to 2 (| | 2). Any node connected to a multicast tree has a single upstream optical channel (except the source, which has none) and any node may have multiple downstream optical channels (except the destinations, which have none). Two optical channels of a light-forest are adjacent if one optical channel is an upstream channel of a node on a tree T and the other is a downstream channel of the same node on the same tree.

III. Tree Reconfiguration Operations

Four reconfiguration operations are applicable on an optical switch. We denote as the configuration (set of lightpaths) obtained at the j th step of the tree reconfiguration process. 1) Addition of a light switching:

s B C A D  ∃ ∈  , , , .
If is the sink port of an optical channel , adds one optical channel with wavelength l in the configuration such that:

is the source port of is adjacent to -The signal coming from feeds

2) Deletion of a light switching:

 ∃ ∈  , , , .
If is the source port of an optical channel , deletes the link u from the configuration .

3) Combined operation:

 ∃ ∈  , , , .
If is the sink port of an optical channel , and the source port of an optical channel , simultaneously deletes the link from the configuration and adds an optical channel with wavelength l such that is the source port of , and is adjacent to .

4) Wavelength conversion:

 ∃ ∈  , , , .
If is the source port of an optical channel , converts the wavelength of to wavelength .

IV. Related Works

In the literature, reconfiguration policy and path computation have been studied by Baldine and Rouskas (1999), [START_REF] Kárász | Optimal Reconfiguration of Provisioning Oriented Optical Networks[END_REF] and [START_REF] Kárász | Consolidation Strategies of Provisioning Oriented Optical Networks[END_REF]. They do not consider the configuration process in itself. The well-known reconfiguration processes MBB (make-before-break) and BBM (break-beforemake) are proposed for path reconfiguration. MBB achieves path reconfiguration without path interruption but not regardless of the paths and the cost of many reconfiguration steps. Cousin and Molnar (2006) studied fast path reconfiguration without data flow interruption as they are interested in unicast connections.

The connections considered in all these previous works are unicast connections. In this paper, since the problem considered is tree reconfiguration without data flow interruption, we first describe an MBB adaptation to the tree reconfiguration problem. This MBB-based algorithm is called MBB_2. Then we present the BpBAR_2 process proposed in our previous work. It was the first time that a tree reconfiguration algorithm which achieves uninterrupted flow was proposed in the literature. We compare our new algorithm to these two algorithms.

MBB_2

MBB is a well-known path reconfiguration process.

The MBB reconfiguration process causes an interruption when the initial and final paths make a cyclic dependency (Cousin and Miklos, 2007). In the adaptation of MBB to tree reconfiguration which uses no additional resource, the no interruption requirement is not fulfilled. In tree reconfiguration without additional resources, since the same link may be shared by several branches of the tree, the probability of having cyclic dependency between the branches of the trees increases. Thus, MBB_2 is an MBB-based algorithm which uses one additional wavelength during the reconfiguration process. MBB_2 consists of two phases. In each phase, it uses the function TRwMBB2 described in Algorithm 1. In the first phase of MBB_2, TRwMBB2 configures each sub-tree of the new tree with the additional wavelength. In the second phase, it configures each sub-tree of the new tree with the final wavelength. The sub-trees of the initial tree (respectively the final tree) considered in this algorithm are rooted at the son nodes of the tree source s in the initial tree (respectively in the final tree). The set of destinations of each sub-tree is denoted Dest.

Algorithm 1: Function used by MBB_2 TRwMBB2 (T 0 , T z ) 1. { 2. Configure in one step all the nodes on the new tree T z to build all the pre-established branches with the additional wavelength 3. For each sub-tree of the new tree T z 4. { 5.

Select a sub-tree of the old tree not configured 6.

Interrupt in one step the data flow on branches (on the initial tree T 0 ) toward all the destinations not configured and such that ∉

7.

Switch wavelength from the sub-tree of the old tree to the sub-tree of the new tree at the tree source s to feed the new tree 8.

Configure in parallel all the ports of the nodes on the old sub-tree to remove its branches 9. } 10. }

Algorithm 2: MBB_2 MBB2 (T 0 , T z ) 1. { 2. TRwMBB2 (T 0 , T) 3. TRwMBB2 (T, T z ) 4. } 2. BpBAR_2
BpBAR_2 is a BpBAR-based algorithm which consists of two phases. Each phase consists of several stages. Each stage is a series of reconfiguration steps to reconfigure one branch. Figure 3 represents a diagram of operations scheduling in a stage of the BpBAR process to ensure the continuity of the lightpath during the reconfiguration. This diagram can be subdivided into five parts according to the successive operations executed. BpBAR_2, which is a BpBAR-based process, uses parallel execution of operations to reduce the reconfiguration delay. BpBAR_2 executes, in parallel, all the operations belonging to the same part of a BpBAR stage as shown Table II. Figure 4 represents the diagram of a reconfiguration stage with BpBAR_2.

In the first phase of a reconfiguration with BpBAR_2, each branch is established per stage; a new tree, a copy of the final tree which uses wavelengths different from the initial, is obtained. In the second phase, each branch is established per stage; a tree, a copy of the final tree which uses the initial wavelength, is obtained. We describe below a reconfiguration stage with the BpBAR process. Table I describes the different parts of a reconfiguration stage with the BpBAR process. The operations are executed sequentially in this diagram. The length of each part (number of steps) is equal to the number of ports to be configured in this part. After the setup of the pre-established path in part 1 of a stage, the combined operation is executed in part 2 to feed the pre-established path. Comb is executed at the end node of the pre-established path. Since it feeds the pre-established path and interrupts data flow on the other path, the appropriate switching node is the one which maintains the data flow continuity toward all the destinations after its configuration. This appropriate switching node depends on the initial tree T and the destination of the pre-established path . It is denoted _ , . For example, in Fig. 2, C is the node _ , ). Then, in part 3, the wavelength switching is deleted on all nodes of the exclusive part of the old branch on which flow is interrupted. Parts 4 and 5 occur when the switching node is noted as the source node s.

Definition 1: The end part of path p beginning at path node x is denoted , .

Definition 2: _ , is the root node of the sub-tree of the tree T which will be used during the branch configuration between the source node and the destination d. A node x is the node _ , of the branch , , if:

(1) x is a branching node of tree T which uses the initial wavelength (2) For each node ∈ , , , and ∉ , , | | 1. . This part deletes the pre-established path between the node _ , and the source node s. The length is equal to the number of ports to be configured. Table II: Operations executed in parallel in a stage of BpBAR process

Parts of stage

Series of configurations by part in Fig. 3 Configurations produced in Fig. 4 after parallel execution

1 <Add( ), Add( ),…, Add( )> <Add( )> 2 <Comb( )> <Comb( )> 3 <Del( ), Del( ),…, Del( )> <Del( )> 4 <Comb( )> <Comb( )> 5 <Del( ), Del( ),…, Del( )> <Del( )>
VI.

Proof of Data Flow Continuity Toward

BpBAR_2 is a BpBAR-based algorithm which uses parallel execution of operations. First, we prove that a reconfiguration stage with BpBAR maintains lightpath continuity. Second, we prove that the parallel execution of all the operations belonging to the same part of a stage with BpBAR maintaining continuity of the lightpath. Let us assume that a stage begins with a configuration and is noted <O( ), O( ),…, O( )> where is the i th configuration which contains a light-forest spanning all the destinations of a multicast connection <s, {d}> and is a tree reconfiguration operation (described in Section III). is represented by where ∑ is a light-forest spanning all the destinations. We will prove that each part of a reconfiguration stage with a BpBAR process maintains the continuity of the lightpath.

(1) Part 1 Let us consider a configuration of part 1 which contains a light-forest spanning all the destinations of a multicast connection, where is a preestablished path. Let denote the set of optical channels of such that spans all the destinations of the multicast group.

implies add new optical channel u in such that u is adjacent to the end link of . Thus, the new set of optical channels after is ∪ . The optical channels of are not modified so spans all the destinations. Thus, contains a lightforest spanning all the destinations. In BpBAR, the Add operation ( , , , ), is carried out such that the ports and of the switch

x do not belong to the set of ports of . Thus, the new pre-established path is not fed and there is no loop.

( (3) Part 3

The condition to execute Del in a configuration with BpBAR, in part 3 is:

- - ⟹ , , ,
, where x is the end node of , does not belong to but belongs to

We know by definition that the pre-established path is not used to transmit data ( does not belong to but belongs to ). configures the port on to delete the wavelength switching. After , the ports of are not modifying and a light-forest spanning all the destinations of the multicast connection exists. If is the new pre-established path after the Del operation, .

(4) Part 4

Comb is executed on the source node of the multicast connection s in this part. The conditions to execute Comb in a configuration with BpBAR, in this part are:

--The lightpath between the source node s and a destination contains s twice: for example (s, x, …, ,.., s, y,…,d).

-⟹ , , , where belongs to .

This operation is equivalent to , , , , followed by , , , , . The signal coming from any input port of s is interrupted. The lightpath between s and the destination becomes (s, y,…,d). The part of path ( ,.., s) which is not used to transmit data after the operation becomes the pre-established path . Then contains a lightforest spanning all the destinations of the multicast connection.

(5) Part 5

The condition to execute Del in a configuration with BpBAR in this part is:

- - ⟹ , , ,
, where x is the end node of , does not belong to but belongs to .

is not used to transmit data ( does not belong to but belongs to ). configures the port on to delete the wavelength switching. After , the ports of are not modifying and a light-forest spanning all the destinations of the multicast connection exists. If is the new preestablished path after the Del operation, . We have proved that all the parts of a reconfiguration stage maintain the lightpath continuity. We conclude that a reconfiguration stage with BpBAR maintains data flow continuity during a branch reconfiguration.

VII. Reconfiguration with Wavelengths Limit Constraint 1. Context and Problem Formulation

We consider a WDM optical network which has a limited number of available wavelengths per link. A multicast connection established in this network on the tree uses wavelength l0. We want to move from the tree to a new tree . The initial tree and the final tree must use the same wavelength l0. We assume that the new tree is known. The reconfiguration must be carried out without data flow interruption. The tree configuration process proposed in our previous work [START_REF] Cousin | Tree Reconfiguration Without Lightpath Interruption in WDM Optical Networks[END_REF] produces a series of light-forests since it must maintain lightpath continuity. The number of trees per light-forest is not increased with the proposed algorithm. This number is proportional to the number of branches to be established. In a network with a multicast connection established, several branches can share the same link which has very limited available resources. In this context, BpBAR_2 may be inapplicable. Some branches which share the same link cannot be established. The problem in this work is to reduce the number of trees per light-forest at each step of the reconfiguration, regardless of the initial and final trees, and the network topology.

Our Proposition: TRwRC

The proposed tree reconfiguration is the TRwRC (tree reconfiguration with resources constraint) algorithm. It has two phases. TRwRC produces a series of lightforests during the tree configuration process. Let us assume that the destinations of the multicast connection is subdivided into two sets during the reconfiguration process: a set of destinations whose lightpaths are reconfigured (uses paths on the new tree) denoted Dest_Config and a set of destinations whose lightpaths are not reconfigured (uses paths on the initial tree) denoted Dest_NConfig. The maximal number of trees per light-forest in a configuration produced with TRwRC is two. Each tree, at each step, spans the destinations of one set described above. TRwRC uses the function ReconfBr described in Algorithm 3 to reconfigure each branch of the initial tree T 0 . The reconfiguration of each branch with ReconfBr consists of two stages. In the first stage, the branch is established with an additional wavelength . In the second stage, the branch is established with the additional wavelength . The tree obtained after the reconfiguration of all the branches of the initial tree T 0 is a copy of the new tree T z using the additional wavelength denoted T'. In the second phase, TRwRC configures simultaneously the ports of the nodes of the tree T' obtained after the first phase to convert the additional wavelength into the initial wavelength. Algorithm 4 represents TRwRC. We described below the function ReconfBr used to reconfigure a branch. Let be the initial configuration and , , a branch we want to establish. contains a light-tree spanning all the destinations. We note . TRwRC uses the Add operation to setup in one step a pre-established path between _ ( , ) and with an additional wavelength (for example ). After this operation, where and is the pre-established path. number of interruptions during the tree configuration process. In addition to the above criteria, also used in our previous work, we define a new criterion which is the number of unsolved tree configuration problems. An unsolved problem is a pair of trees which a certain algorithm cannot reconfigure without data flow interruption. The number of unsolved problems depends on the number of available wavelengths per link. If the number of pairs of trees generated is _ :

_ _ ∑ , _ (1)
where , 1 if for the k th pair of trees, w available wavelengths per link is not enough to reconfigure all the tree branches without flow interruption and , 0 otherwise. In the evaluation, _ is chosen experimentally and is equal to 5000.

Results and Analysis

The results of the different evaluations are noted in Tables III to VII. Tables III to V show the performance results when the initial tree is SPT and the final tree MST. Tables VI andVII show the results obtained when we swap the algorithms used to compute the trees. The initial tree is now MST and the final tree SPT. The results of the performance evaluations noted in Table III show that the number of steps produced by TRwRC is approximately equal to the number of steps produced by BpBAR_2 (Fig. 6), but is greater than those produced by MBB_2. This is due to the fact that TRwRC is a back and forth tree reconfiguration process. Table IV shows that tree reconfiguration with TRwRC uses more resources than reconfiguration with the MBB_2 process. This is due to the fact that MBB_2 uses the same initial wavelength during all the process. So, it requires no additional wavelength while TRwRC uses additional resources to establish new branches. Table V shows that MBB_2 causes data flow interruption while TRwRC maintains continuity of data flow. The continuity of data flow is due to the properties of the BpBAR process used by the TRwRC algorithm. A good tree reconfiguration algorithm is one which does not interrupt the flow toward any destination during the reconfiguration. Thus, the TRwRC algorithm is much better than the MBB_2 algorithm.

BpBAR_2 and TRwRC maintain the continuity of data flow and produce approximately the same number of steps (see Fig. 6). The important improvement is shown in Figs. 7, 8, and 9. Figs. 8 and9 show the evolution of the percentage of unsolved problems with the BpBAR_2 TRwRC algorithms as a function of the number of available wavelengths per link. They show that when the number of available wavelengths per link is under or equal to two, generally the BpBARbased algorithms produce tree reconfiguration with data flow interruption. But the performance produced by TRwRC is better than the performance produced by BpBAR_2. These figures show also that when the number of available wavelengths per link is equal to three, TRwRC allows reconfiguration of any tree without data flow interruption regardless of the topology, while BpBAR_2 requires more available resources. Moreover, Fig. 7 shows that the cost of additional resources produced by TRwRC is less than the cost of additional resources produced by BpBAR_2. So TRwRC does not use more additional resources than BpBAR_2 during its process. This is due in the fact that each configuration produced by TRwRC contains at most two light-trees and one pre-established path, while with BpBAR_2 the number of trees increases with the number of branches.

When we swap the trees used to compute the tree configuration, Figs. 10 to 12 show that the same performance gains are kept: TRwRC reconfigures any pair of trees when the number of available wavelengths per link is equal to or higher than three and does not use more additional resources compared to BpBAR_2.

IX. Conclusion

Tree reconfiguration in WDM optical networks is studied in this paper. In the literature, the well-known path reconfiguration process MBB is proved to induce flow interruption. Similarly, adaptation of MBB to tree reconfiguration with no additional wavelengths may induce interruption. Even more, the tree branches may increase the probability of cycle outbreak and thus interruption.

Adaptation of MBB to tree reconfiguration with an additional wavelength is also inefficient because it produces flow interruption. In our previous work, we proposed a branch-by-branch algorithm (BpBAR_2) which aims to reconfigure trees without data flow interruption, and reduces the reconfiguration setup duration and the network resources used during the reconfiguration process. The availability of network resources was not considered in this previous work. In this paper, we consider tree reconfiguration problems in a network wherein the number of available wavelengths is limited. In this context, the algorithm BpBAR_2 becomes inefficient. In this paper, we propose TRwRC which allows reconfiguration of trees when each optical link has a limited number of available wavelengths. TRwRC maintains the continuity of the flow since it uses the appropriate switching node _ , and the combined switching operation to feed the new branches. The reconfiguration setup duration produced is also good compared to the previous algorithm. TRwRC uses, at most, two trees per light-forest to span all the destinations during the different configurations produced. Thus, it allows tree reconfiguration in alloptical networks with limited resources. It also reduces the cost of used resources during the reconfiguration process. When the number of available wavelengths per link is three (at least), any tree reconfiguration without data flow interruption is possible with TRwRC.

Fig. 2

 2 Fig.2Example of tree reconfiguration problem. The old tree is in red and the new tree is in blue.

  Fig. 3 Diagram of operations scheduling during a branch reconfiguration in a stage with BpBAR

Fig. 6 :Fig. 7 :Fig. 8 :Fig. 9 :

 6789 Fig.6: Setup duration of each algorithm in COST 239 and NSF Network

Fig. 10 :Fig. 11 :Fig. 12 :

 101112 Fig.10: Setup duration of each algorithm in COST 239 and NSF Network

Table I :

 I Distinct parts of a stage in BpBAR process

	Parts			Description
	1	From to	: This part consists of setting up
		the pre-established path between the destination
		and the node	_	, . The operation
		used is	:		. The length is
		equal to the number of ports to be configured.
	2	From	to		: This part feeds the pre-
		established path by executing the combined
		operation at	_		, :	.
		It consists of one step.
	3	From	to		: This part deletes the pre-
		established path between the destination and
		the node	_		, . The operation used is
		:		. The length is equal to the
		number of ports to be configured.
	4	From	to		: This part consists of
		executing the combined operation Comb at
		_	,	to interrupt the flow between
		_	,	and the source node. It consists
		of one step.
	5	From	to	:

orithm 3: Fun onfBr (T 0 , T z

	inter rrupt the flow w on the old d path. The p pre-establish hed
	path h now ensure es the continu uity of the lig ghtpath towa ard
	the d destination		. Before the e execute Co omb operatio on,	A Algorithm 4: T TRwRC algor rithm
	the	, , lightpath to oward . A , _ After the sw , is shared only b by witching,	TR RwRC (T 0 , T z ) z ) 1. { 2. For each dest tination
							where	spans t the	3.	{
	dest inations o	f Dest_NC Config,	spans t the	4.	Recon nfBr (T 0 , T z , d d, T')
	dest inations of , , f Dest_Con , _ nfig ( ) , .	and, is deleted	is in	5. 6. 7.	Recon nfBr (T', T z , d d, T) } Configure si imultaneously y the ports of f the nodes o of the
	one	step and				w where	tree T to c onvert the w wavelength us sed into the i initial
	and sour rce node s, s . If f the node s is reconfig gured to inte _ ( , ) is not t errupt the da ata the	8.	}	wavelength .
	flow the b is es w between branch is de stablished w eleted. After _ ( , with the addit , ) and s, th this stage, th tional wavel hen this part he new bran length . T nch of The	VIII. Pe erformance E Evaluation 1. Criter ria and Metho od
	sam e process is	repeated in a a new stage t to establish t the	W We use COST T 239 (see Fi ig. 4) and N SF networks s (see
	bran nch with the e additional	wavelength h . The tw wo	Fi ig. 5) to	evaluate o our algorith m. Well-kn nown
	stag es for each b branch are r epeated. In t the first phas se,	to opologies ar re used in n many sim milar papers s as
	we o obtain a tree		T', a copy o of the new tre ee T z, using t the	pe erformance e evaluation to opologies.
	addi itional wavel length .
	In th he second ph hase, the por rts of the no des of the tr ree
	T',	obtained		after the	first phas se, configu ure
	simu ultaneously t to convert th he additional	wavelength
	into	the initial w wavelength.
	Algo	nction used to o established	a new branc ch
	Reco
	1. {
	2. If	(	, ,		is different fro om	, ,	)
	3. 4.	{ Determin ne node	_	nd configure 0 , an	Fi ig. 4: Topolo ogy of COST T 239 networ rk
	5.	in paralle destinatio Configur el the ports of on node and re the node f the nodes bet d the node _ tween each _ 0 , 0 , to feed the
		new bran nches and in nterrupt the f flow of the o old
		branches
	6.	Remove,	in parallel, th he part of the o old branches i in
		Which fl	ow is interrup pted
	7.	If and d have diffe erent topologie es
	8.				{
	9.				Configure s to and _ o interrupt the e part between n s 0 , whic ch is different t to
	s s
	10.				Configure, sim multaneously, , the ports of t the
					nodes _	0 0 , to remov between e this part s	a and	Fi ig.5: Topolog gy of NSF N Network
	11.				}
	12.	}					Th he initial and d final trees	are selected d arbitrarily ( (they
	13. } }						ar re called pai rs of trees, a above). One	is the minim mum
							sp panning tree	(MST) com mputed with	Prim's heur ristic
							(P Prim, 1957) ). This alg gorithm cal culates a	good
							ap pproximation n of the Stein ner tree for a a multicast gr roup.
							Th he other is t the shortest	paths tree (S SPT) which	uses
							D Dijkstra's alg orithm (Dijk kstra, 1959)	for the mult ticast
							The C to hm TRwRC _ our algorith combined operation is executed on gr roup. We compare o , to Bp pBAR_2 and d MBB_2. Th he criteria are e: the duratio on of
							simultaneously feed the pre-established path and th he process, the addition nal resource es used and d the

z , ,T')

Table III :

 III Average and standard deviation of the number of steps for each reconfiguration

		COST 239		NSF NETWORK
	CONF.	AVG	SD	MIN/MAX	AVG	SD	MIN/MAX
	PROCESS	(STEP)	(STEP)	(STEP)	(STEP)	(STEP)	(STEP)
	BpBAR_2	18.07	12.09	6/51	22.62 17.35 6/74
	TRwRC	18.31	11.61	7/54	22.68 16.15 7/79
	MBB2	8.32	2.42	6/17	8.58	2.04	6/17

Table IV :

 IV Average and standard devisation of additional cost for each reconfiguration process

		COST 239		NSF NETWORK
	CONF.	AVG	SD	MIN/MAX	AVG	SD	MIN/MAX
	PROCESS	(WL)	(WL)	(WL)	(WL)	(WL)	(WL)
	BpBAR_2	166.84	195.57	10/861	370.14 448.16 9/2273
	TRwRC	107.52 96.45	13/430	227.85 220.44 13/1104
	MBB2	85.95	30.13	18/177	122.72 40.34 18/229
	Table V: Average and standard deviation of
	interruption duration for each reconfiguration
		COST 239		NSF NETWORK
	CONF.	AVG	SD	MIN/MAX	AVG	SD	MIN/MAX
	PROCESS	(STEP)	(STEP)	(STEP)	(STEP)	(STEP)	(STEP)
	BpBAR_2	0	0	0/0	0	0	0/0
	TRwRC	0	0	0/0	0	0	0/0
	MBB2	2.85	1.47	0/6	3.42	1.86	0/6

Table VI :

 VI Average and standard deviation of reconfiguration duration for each reconfiguration process

		COST 239		NSF NETWORK
	CONF.	AVG	SD	MIN/MAX	AVG	SD	MIN/MAX
	PROCESS	(STEP)	(STEP)	(STEP)	(STEP)	(STEP)	(STEP)
	BpBAR_2	19.02	12.81	6/61	22.59 16.43 6/80
	BpBAR_4	20.33	12.80	7/62	22.21 12.92 7/62
	MBB2	10.90	3.20	6/17	8.77	2.4	6/17

Table VII :

 VII Average and standard deviation of additional cost for each reconfiguration process

		COST 239		NSF NETWORK
	CONF.	AVG	SD	MIN/MAX	AVG	SD	MIN/MAX
	PROCESS	(STEP)	(STEP)	(STEP)	(STEP)	(STEP)	(STEP)
	BpBAR_2	92.75	100.65	5/542	183.88 219.63 5/1088
	BpBAR_4	93.15	89.67	8/427	116.42 127.78 9/701
	MBB2	62.98	32.24	9/149	10.51 40,01 18/229