Omar Smail
email: smailomar@ieee.org

Bernard Cousin
email: bernard.cousin@irisa.fr

Imene Snoussaoui
email: i.snoussaoui@univ-mascara.dz

Energy-Aware and Stable Cluster-Based Multipath Routing Protocol for Wireless Ad Hoc Networks

Keywords: Ad hoc network, wireless networks, clustering, multipath routing, energy efficiency, link stability dependable networking, high speed networks, traffic engineering, multicast routing, network QoS management, network security and multimedia distributed applications

Ad hoc networks are wireless networks that can operate without infrastructure and without centralized network management; they may contain nodes with limited battery power. Hence, energy conservation is a critical requirement in the design of routing protocols for ad hoc networks. Clustering has been proposed as a promising method for simplifying the routing process in mobile ad hoc networks when network size increases. In this paper, we propose an energy-efficient multipath routing protocol, called ES-CMR (Energy aware and Stable Cluster-based Multipath Routing protocol), which preserves the residual energy of nodes and increases the network lifetime. To achieve this goal, we use an objective model to select energy-efficient paths with stable links. Simulation results demonstrate that ES-CMR has better performance in terms of energy consumption, network lifetime and end-to-end delay.

Introduction

An ad hoc network is characterized by frequent changes in network topology, limited bandwidth availability, and limited power of nodes. Ad hoc network topology changes frequently as nodes are able to move collectively or individually and often in an unpredictable way. Hence these characteristics make route discovery more complex. Several research studies have focused on routing protocols for ad hoc networks [START_REF] Murthy | A routing protocol for packet radio networks[END_REF][START_REF] Duyen | Performance evaluation and comparison of different ad hoc routing protocols[END_REF][START_REF] Jayakumar | Performance comparison of two on demand routing protocols for ad-hoc networks based on random way point mobility model[END_REF][START_REF] Rivano | A Framework for the Capacity Evaluation of Multihops Wireless Networks[END_REF][START_REF] Radwan | Performance measurement of some mobile ad hoc network routing protocols[END_REF], these protocols have some relevant characteristics, but they also have some limitations in the case of high mobility of nodes or high network density. Traditional approach of routing in wireless ad hoc networks adopts a single active route between a source node and a destination node for a given communication. This usually uses proactive [START_REF] Belding-Royer | Routing approaches in mobile ad hoc networks[END_REF][START_REF] Perkins | Highly dynamic destination sequenced distance vector routing (DSDV) for Mobile Computers[END_REF] or reactive (on demand) [START_REF] Mueller | Multipath routing in mobile ad hoc networks: issues and challenges[END_REF][START_REF] Perkins | Ad hoc on-demand distance vector (AODV) routing[END_REF] routing 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 the reactive protocols, because of the large routing overhead incurred in the former. However, reactive protocols suffer from latency during the discovery process of fresh paths, especially in large networks and dense networks. In recent years, the research community has focused on the improvement of ad hoc routing, with the development of several routing techniques. Multipath routing -which resists to frequent network topology changes -seems to be an effective mechanism in ad hoc networks with high mobility and high load, mobility which mainly caused wireless link failures. In multipath routing, the source node is given the choice between multiple paths to reach a given destination. The multiple paths can be used alternately; in this case the data traffic can follow either a single path at one time or several paths simultaneously. The major disadvantage of multipath routing is the additional cost which increases significantly with the growth of network density, thus the scalability is compromised. Existing routing protocols for ad hoc network cannot solve this problem. A commonly proposed solution is to organize nodes into groups, called clusters. Clustering is a virtual organization of the network into groups of geographically close nodes. In clustering, usually there are three types of node: cluster head nodes which represents the clusters, gateway nodes that serve as intermediates between clusters for inter-cluster communication and ordinary nodes. Several clustering techniques in wireless and mobile networks have been proposed in the literature [START_REF] Agarwal | Survey of clustering algorithms for MANET[END_REF][START_REF] Anupama | Survey of Cluster Based Routing Protocols in Mobile Ad hoc Networksm[END_REF][START_REF] Agarwal | Review of Weighted Clustering Algorithms for Mobile Ad hoc Networks[END_REF][START_REF] Conceição | Onto scalable wireless ad hoc networks: Adaptive and location-aware clustering[END_REF][START_REF] Neethu | Mobility Aware Loose Clustering for Mobile Ad hoc Network[END_REF]Tavakoli et al., 2015;[START_REF] Shen | Energy-efficient cluster-head selection with fuzzy logic for robotic fish swarm[END_REF]. The main problem of these techniques is to maintain their cluster structure as stable as possible while the network topology may change. Moreover, each node in mobile ad hoc networks 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 network connectivity in fast moving distributed dynamic networks [START_REF] Smys | Performance analysis of virtual clusters in personal communication networks[END_REF].

Energy-Aware and Stable Cluster-Based Multipath Routing Protocol for Wireless Ad Hoc Networks

Some exhausted nodes may be critical for packet transmission mainly if they are cluster head node, because they are more suitable for supporting the ad hoc network functions (e.g., routing) than other nodes. A good routing protocol with clustering scheme will tend to preserve its structure by preserving its nodes energy power, principally the cluster head and the gateway nodes. Few protocols which simultaneously are based on multipath routing and use clustering to improve the performances of ad hoc networks in terms of energy, can be found in the literature. The main of them are cited in (Bheemalingaiah et al., 2009) 1 . In this paper, we propose a novel routing protocol, called ES-CMR (Energy aware and Stable Cluster-based Multipath Routing protocol), for wireless ad hoc networks based on the multipath principle, in order to use the energy of nodes efficiently, and to minimize the end-to-end delay. It uses a clustering structure to decrease routing control overhead. The ES-CMR protocol is designed primarily for wireless ad hoc networks with batterylimited nodes, networks where link failures and path breaks may occur frequently. The main idea of this protocol is to discover multiple paths between a source and a destination in a clustered wireless ad hoc network and to select the path that ensures the least energy consumption with stable links. In order to combine energy efficiency and stability of links, we used an objective function. The paper is organized as follows. Section 2 provides a review of related works on multipath routing and known clustering techniques in wireless ad hoc networks. Section 3 presents a description of our proposed cluster creation and maintenance schemes. Section 4 gives the design details of the ES-CMR protocol. Section 5 provides the simulation results of its performance evaluation. Section 6 concludes this paper.

Related work

In this section, we present a review of multipath routing protocols and clustering technique-based routing protocols in wireless ad hoc networks.

Multipath routing

Multipath routing in ad hoc networks is a promising technique that allows to solve the problems of instability, limited bandwidth, and conservation of energy. The use of multiple paths decreases the effect of network link failures. This contributes considerably to improve network performance. Nevertheless, multipath computation remains a more complex task than single path computation. Its difficulty lies in searching for the (best) multiple paths. The multipath approach makes it possible to compute multiple paths in a distributed and independent way. It is based on the principle of disjunction of the multiple paths between the same source-destination pair the disjunction may be partial or not [START_REF] Lou | Performance optimization using multipath routing in mobile ad hoc and wireless sensor networks[END_REF]. The purpose of this disjunction principle is to ensure the independence of the paths; that is, if a link of one of the paths fails, this failure will not affect the other paths. 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. Multipath routing is highly suitable for multimedia applications, to ensure reliable 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 potential reduction of the routing overhead. Several multipath routing protocols have been developed (Tarique et al., 2009;[START_REF] Periyasamy | Survey of Current Multipath Routing Protocols for Mobile AD Hoc Networks[END_REF]Zuo et al., 2013). Let us note that there are two types of path disjunction: for the links and for the nodes. The first type, link-disjoint paths, does not share common links but a node can participate in several paths; the failure of a shared node (for instance, battery depletion) affects all paths that share this node. The second type of path disjunction, node-disjoint paths, has no node (and thus no link) in common, and therefore depletion of a node affects only the path containing this node. In our protocol we chose this type of disjunction to ensure the complete independence of the paths. Most of the proposed multipath protocols, like AOMDV [START_REF] Marina | On-demand multipath distance vector routing in ad hoc networks[END_REF] and SMR [START_REF] Lee | Split multipath routing with maximally disjoint paths in ad hoc networks[END_REF], are based on an original single path version (AODV [START_REF] Perkins | Ad hoc on-demand distance vector routing[END_REF] or DSR [START_REF] Johnson | The dynamic source routing protocol (DSR) for mobile ad hoc networks for ipv4[END_REF]). These protocols are reactive routing protocols. In fact, reactive multipath routing protocols improve network performance (load balancing, delay and energy efficiency). Several studies [START_REF] Bagwari | Analyzing the performance of routing protocols used for communication between mobile ad hoc network and internet[END_REF][START_REF] Misra | Performance Comparison of AODV/DSR On-Demand Routing Protocols for Ad Hoc Networks in Constrained Situation[END_REF] have shown that AODV outperforms DSR under various performance metrics. Simulation results confirm that AODV protocol provides better end-end delay values and better connectivity with less data loss and good throughput. This is why our ES-CMR routing protocol shares some of its concepts with AODV.

Clustering techniques-based routing protocols

We present below different protocols based on clustering techniques for ad hoc networks. They are categorized into different approaches based on their distinguished features. We focus on mobility and energy of nodes because in ad hoc networks, the nodes are mobile with limited battery; when they move out of range of their neighbours or they run out of battery power, the wireless links between nodes fail. These failures increase the intensity of changes in the network topology and make routing difficult. Two clustering techniques are considered: single metric and combined metric based clustering.

Clustering mobility-based routing protocols

This technique considers only one performance factor for clustering decisions. The main clustering techniques for this scheme have been listed below. CBMCRP (Cluster Based Mobility Controlled Routing Protocol) [START_REF] Saha | Cluster Based Mobility Considered Routing Protocol for Mobile Ad Hoc Network[END_REF] obtains efficient communications among an ad hoc network and achieves scalability in large networks by using the clustering technique. The new algorithm takes into consideration the mobility factor during routing and as well as computational overhead is also diminished. CBMCRP characterizes mobile nodes according to their mobility. This protocol uses the self-organizing principles for binding a node to a cluster and to minimize the explicit message passing in cluster formation. The cluster head of each cluster acts as a local coordinator for its cluster, performing inter-cluster routing, data forwarding and has to undertake heavy tasks so that it might be the key point of the network. CBMCRP achieves the scalability in large network where nodes are mobile. In this protocol no consideration for the inter-cluster links provided by the gateways is made. Therefore the choice of an inappropriate gateway affects these links and compromises the inter-cluster connectivity. AMOBIROUTE (An Advanced Mobility Based Ad Hoc Routing Protocol for Mobile Ad Hoc Networks) (DasGupta and Chaki,

Energy-Aware and Stable Cluster-Based Multipath Routing Protocol for Wireless Ad Hoc Networks

2009) is based on mobility control to address connectivity, link availability and consistency issues. According to this algorithm, mobility of node k of cluster i is based on loc t k,i , the position of the node at time t j . Here, every node maintains only neighbor's data. After the calculation of node mobility, it only considers the least mobile nodes. For the next hop selection, it takes low mobility as a criterion, i.e., it selects the least mobile node as next hop. The main objective of AMOBIROUTE [START_REF] Dasgupta | AMOBIROUTE: An Advanced Mobility Based Ad Hoc Routing Protocol for Mobile Ad Hoc Networks[END_REF] is to reduce overhead produced by routing. For this purpose, this algorithm maintains information about the next neighbor and maintains information about the least mobile nodes. The mobility node model used is rather simple since it is based on the location of the node and its speed without any indication of the movement model and, moreover the inter-cluster links are not covered by this protocol. In [START_REF] Dana | A Robust Cross-Layer Design of Clustering-Based Routing Protocol for MANET[END_REF] a new clustering-based routing protocol, named Cross-CBRP, has been designed. In the proposed approach, the interaction between physical, MAC and routing layers are exploited. Hence it adapts the clustering algorithm to link instability and network condition due to mobility. The proposed Cross-CBRP algorithm uses signal power information coming from the physical layer at the network routing so that the stability of the formed clusters can be maximized. In this proposed approach, cluster creation and cluster maintenance are based on the node mobility towards its neighbours. The node with lowest mobility in the pre-specified period of time will be elected cluster head. The drawback of this technique is that the announced stability is not measured, and is not compared with any other competitive technique in the literature.

Clustering energy-based routing protocols

In ad hoc networks, energy efficiency is of paramount importance. Energy-aware clustering optimization has been addressed in recent years. Below, we present the main clustering algorithms that address this problem. In (Tarique and Tepe, 2009) the HMEDSR (Hierarchical Minimum Energy Dynamic Source Routing) protocol is proposed. The objective of this protocol is to reduce energy consumption in MANET while maintaining connectivity in the network and mastering the overhead. HMEDSR is a combination of two protocols, HDSR [START_REF] Tarique | New hierarchical approach routing to reactive routing protocol for wireless ad hoc network with cross-layer design[END_REF] and MEDSR (Tarique and Tepe, 2009), which have their own advantages. On one hand, HDSR protocol reduces the number of control packets significantly, and the nodes consume less energy in the transmission of control packets. Therefore, they will have more remaining energy for transmission of data packets. On the other hand, MEDSR protocol economizes nodes energy while transmitting data packets. MEDSR protocol consists of two basic mechanisms: multiple power level route discovery, and link-by-link power adjustment. However, the drawback is that the time of the forwarding nodes (cluster heads or gateways) may not be a good indicator of energy consumption of a mobile node; a particular interest must be reserved for these types of nodes, because when this type of node fails, the entire routing structure falls apart. ECCRP (energyefficient coding-aware cluster based routing protocol) [START_REF] Kanakala | Energy-Efficient Cluster Based Routing Protocol in Mobile Ad Hoc Networks Using Network Coding[END_REF] is a protocol that applies network coding at cluster heads to reduce number of packet transmissions. It ensures the election of best cluster head and improves the cluster life time by using an energy efficient scheme. Network coding is a popular mechanism to increase throughput of wireless networks. Hence, it reduces the number of packet transmissions. Therefore, it also reduces redundant transmissions that occur due to broadcasting. ECCRP used flow based queue policy while performing coding at intermediate nodes to increase coding opportunities. Simulation results show that the proposed ECCRP algorithm reduces energy consumption and increases life time of the network. The weakness of this technique is that it is applied to clustered networks of reduced size and performance is not compared to other recent protocols from literature. A hybrid routing protocol, named Power Saving (PS) [START_REF] Jiang | A Hybrid Power-Saving Protocol by Dual-Channel and Dual-Transmission-Range Clustering for IEEE 802.11-Based MANETs[END_REF], is proposed for mobile ad hoc network. The concept of dual-channel and dual-transmission-range clustering is used in the proposed protocol. In this work, all the network nodes are partitioned into clusters. The synchronous PS protocol is operated within an individual cluster and the quorum-based asynchronous power saving (QAPS) protocol [START_REF] Jiang | Quorum-Based Asynchronous Power-Saving Protocols for IEEE 802.11 Ad Hoc Networks[END_REF] is operated among cluster heads. The PS protocol operates on the basis of neighbourhood information so it adapts to changes in network topology as quickly as possible. Two non-interfering communication channels are used: A and B. The cluster head uses channel A with long transmission range to communicate with other cluster heads, and uses channel B with lower transmission range to communicate with its cluster members. It is shown by simulation that the proposed protocol is more scalable than related protocols. However, the election of cluster heads is an unclear procedure and the proposed protocol is based on AODV [START_REF] Perkins | Ad hoc on-demand distance vector routing[END_REF] for data packet routing but AODV is not suitable for hierarchical routing, this produces an additional cost of routing overhead. Moreover, it is difficult to assume the availability of two channels with different ranges in any node.

Combined metric clustering based routing protocols

Combined metric based clustering or weight based clustering takes several metrics into account for cluster configuration. One advantage of this clustering technique is that it can flexibly adjust the weighting factors of each metric to adjust to different scenarios. We choose two metrics (energy and mobility of nodes) because they affect the reliability of the packet delivery service of the network. The Weighted Clustering Algorithm (WCA) proposed in [START_REF] Chatterjee | WCA: A weighted clustering algorithm for mobile ad hoc networks[END_REF] takes into consideration the node degree, transmission power, mobility, and battery energy of nodes. Depending on specific applications, any or all of these parameters can be used to elect the cluster heads. This method could be implemented as a fully distributed system where all the nodes in the mobile network share the same responsibility and act as cluster heads. The cluster head election procedure is not periodic and is invoked as rarely as possible. The cluster head election procedure is invoked when a cluster head is disconnected from any neighbor cluster head, and also when the current cluster head set is unable to cover all the nodes. If a node (ordinary) detaches itself from its current cluster head, a reattachment occurs. In this case, the amount of information exchange between the node and the corresponding cluster head is local and relatively small. Hence, cluster head service time will be prolonged and elected cluster heads will soon suffer from battery exhaustion. WCA has improved performance compared with other previous clustering algorithms. However, it fails to capture the correlation that may exist among the movements of neighbouring mobile hosts as in the case of group movement. Another drawback of this method is that the high mobility of nodes will lead to high frequency of cluster re-association that will increase network overhead. To solve this problem, an entropy-based WCA (EWCA) was proposed (Wang and Bao, 2007), and it can improve the stability of the network. In [START_REF] Mohindra | A Weight Based Energy-Aware Hierarchical Clustering Scheme for Mobile Ad Hoc Networks[END_REF], the authors propose a Weight Based Energy-Aware Hierarchical Clustering protocol (WBEHC) that is energy aware and provides stability. It is based on node grouping according to relative mobility and node merging depending on the mobility pattern, in order to provide minimum energy wastage and stability in the network and to be able to achieve all the tasks assigned to the nodes. In addition, they also use different weights for different system parameters like energy of nodes, mobility, size of the cluster, degree of nodes, etc. for choosing the cluster head depending on the requirement. This procedure of cluster head election minimizes the need of re-attachment and re-clustering. Also, the protocol WBEHC considers relationship between the energy requires to perform the application tasks and the energy requires to forward packets. This helps in minimizing the exhaustion of energy and its wastage. The weakness of this protocol is that routing (I.e. path discovery and maintenance) and gateway management are not described. LIDAR [START_REF] Pantziou | LIDAR: a protocol for stable and energy-efficient clustering of ad-hoc multihop networks[END_REF] is a protocol that represents a major improvement over other clustering algorithms: the node IDs (Identifiers) are regularly reassigned to the nodes with low mobility, and high energy capacities are assigned values with a low ID and, therefore, are likely to serve as cluster heads. LIDAR explicitly separates cluster creation and cluster maintenance phases through employing two distinct algorithms. LIDAR forms stable clusters with a balanced distribution of energy consumption on mobile nodes. This protocol significantly reduces control traffic volume during the maintenance phase of clusters. Drawback of this protocol is that, the choice of gateways and their maintenance are not described and parameters are not justified. In [START_REF] Karunakaran | An adaptive weighted cluster based routing (AWCBRP) protocol for mobile ad-hoc networks[END_REF] the authors proposed an adaptive weighted clusterbased routing for mobile ad-hoc networks. The cluster head selection is performed by assigning a weight value (W) based on the following factors: energy level, connectivity and stability. The node having the minimum W is chosen as the cluster head. When a node is elected as a cluster head, the node or the nodes member of the node cluster is marked as "considered". Then the election process is carried out with all the "unconsidered" nodes. Once all the nodes have been considered, the election algorithm is terminated. AWCBRP is an energy efficient adaptive weighted cluster-based routing protocol which amends swiftly to the topological changes and establishes the routing efficiently. When link failure rate is high, then the partitioning rate of the network becomes high, and this may increase the computational overhead. EACMR (Energy Aware Clustered-Based Multipath Routing) (Bheemalingaiah et al., 2009) 1 , proposes a novel approach without using GPS; this approach is applicable for cluster based mobile ad hoc networks. The Combined Higher Connectivity Lower ID (CONID) clustering algorithm is used to generate the clusters in the network. It is an extension of the lowest ID algorithm. CONID uses node degree as the primary key and ID as the secondary key in cluster decisions. EACMR is designed to find energy aware node-disjoint multiple routes from a source to a destination through cluster heads. It increases the network lifetime by using optimal routes, as compare to on demand multipath routing protocols, it significantly reduces the total number of route request packets using clustering technique, decreases the end-to-end delays for the data packets and the energy consumption. We will use EACMR as a reference for our performance evaluation because it aims to improve the lifetime of ad hoc networks and has the same characteristics as our protocol, namely its reactivity, multipath character, and use a combined metric clustering technique. Considering the existing problems (such as excessive energy consumption and high number of control packets) in both single-path routing and multipath routing schemes, for ad hoc networks, this paper proposes a novel Energy aware and Stable Clustered based Multipath Routing protocol (ES-CMR). In the ES-CMR protocol, the clusters are formed by using combined metric based approach, because it is the most efficient for cluster head selection and the weight estimation include two metrics stability and residual energy, with the introduction of management of the gateways for inter-cluster links. The main idea of our proposition is to find disjoint multiple paths from a source to the destination; these paths are stable, and consume less energy. The process of paths selection is based on an objective model using two parameters: stability and energy. Our ES-CMR protocol preserves residual energy, increases the network lifetime and reduces the end-to-end delay, by selectively choosing more efficient paths.

Cluster creation and cluster management

In this section we describe the clustering scheme. Before proceeding with the presentation of the various steps of the algorithm we describe the network model.

Network model

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. Node s is the source node and the node d is the destination node. In our scheme, there are three possible states for nodes: cluster head, gateway and ordinary. A cluster is denoted by C i ={N ij }, where N ij is the i th member of the cluster i. CHi is the cluster head of cluster Ci and CGi is the gateways set of the cluster Ci. Ordinary nodes are described in the graphs by a simple circle, gateway nodes by a filled circle, and cluster head nodes by a double circle, see Figure 1. Routing for large-scale ad hoc network requires k-hop clusters, where k represents the maximum number of hops between any node from a cluster and its cluster head. We denote by k the cluster radius. By adjusting the parameter k, we can control the number of cluster heads. A large value of k means fewer cluster heads. This reduces the number of cluster numbers which, in turn, may minimize the inter-cluster connectivity problems. To facilitate the description of the clustering scheme and routing protocol, k = 2 is adopted throughout the remainder of this study.

Cluster creation

In clustering scheme, a representative node of each cluster is elected as a cluster head. Cluster heads hold routing and topology information, relaxing ordinary mobile hosts from such requirement; however, cluster heads represent network bottleneck points and are prone to fast battery exhaustion. Thus, the choice of cluster head is crucial for the cluster stability and its lifetime. For our cluster formation, we have selected the Entropy-based Weighted Clustering Algorithm (EWCA) (Wang and Bao, 2007), which is an improvement of the basic protocol WCA [START_REF] Chatterjee | WCA: A weighted clustering algorithm for mobile ad hoc networks[END_REF]. It introduces gateways between clusters to enable a better management of routing.To elect and maintain the most suited nodes as a cluster head (in term of stability and energy), the clustering algorithm

Cluster head Gateway Ordinary

Energy-Aware and Stable Cluster-Based Multipath Routing Protocol for Wireless Ad Hoc Networks takes into account its nodal degree, transmission power, mobility and battery power of nodes. The following points are considered: • The cluster head election procedure is not periodic and it is invoked as rarely as possible. The clustering algorithm is not invoked when the relative distances between the nodes and their cluster head do not change.

• Each cluster head can ideally support only a specific number of nodes to ensure efficient medium access control (MAC) functioning.

• The battery power is the most efficiently used when transmission is within a certain range, i.e., it will take less power for a node to communicate with other nodes when they are within close distance to each other. A cluster head consumes more battery power than an ordinary node since a cluster head has extra responsibilities to carry out for its cluster members.

• Mobility is an important factor in deciding the cluster heads. In order to avoid frequent cluster head changes, it is desirable to elect a cluster head that does not move very quickly. We have selected this algorithm because an entropy-based model is considered a very good indicator of the stability and mobility of the ad hoc network [START_REF] Papavassiliou | An entropy-based model for supporting and evaluating route stability in mobile ad hoc wireless networks[END_REF]. In the case of a high mobility of the nodes, a reorganization of the network is required causing considerable overhead, EWCA reduces this cost compared to most other techniques, producing more stable clusters. We denote the position of node m at time t as ) , ( t m p 

. The positions of nodes are calculated periodically every time interval Δ t . The distance between node m and n at time t is defined as:

) , ( ) , ( ) , , ( t n p t m p t n m p      (1)
The relative position between two nodes, m and n is defined as

   N i i t n m p N t n m a 1 ) , , ( 1 , ,  (2)
Where t i refers to the time instant of the i-th calculation and N is the number of discrete times t i within the time interval Δt. Then the entropy of Fm at time t is denoted as H Fm (t,Δ t ). We have

) log( ) , ( log ) , ( ) , ( m Fm k F t t k P t t k P t t Fm H        (3) where     ) , , / , , ( ) , ( t i m a F i t k m a t t k P m .
Fm denotes the set of the neighbour nodes of node m, and by Fm the cardinality of set Fm (and degree node of m). Fm refers to the potential cluster centred on node m, hence H Fm presents the stability of this cluster, the entropy produced by the set of all nodes that can reach node m in one hop. It should be noted that the entropy, as defined here, is small when the change in the given region is severe and large when the change is small. In consequence, one term is replaced in the combined weighted sum of node v (W v ) described in (Wang and Bao, 2007): the average speed of nodes M v is replaced by the Omar Smail, Bernard Cousin and Imene Snoussaoui entropy H Fv , defined in [START_REF] Belding-Royer | Routing approaches in mobile ad hoc networks[END_REF]. Simulation study given in Performance Evaluation section will indicate that this replacement can effectively reduce the frequency of cluster reassociation, especially for those networks consisting of high-speed moving nodes (Tarique et al., 2009). Hence, the formula to calculate W v becomes:

v v v v G v P c H c D c c W 4 3 1 ) ( 2      (4)
where G v is the ratio between the number of members of the cluster centred on cluster head v and the number it can handle under ideal condition, D v is the sum of the distances of the cluster members to cluster head v, H Fv is the entropy of the node, and P v is measured as the total (cumulative) time a node acts as a clusterhead. We assume that the energy consumption of a cluster head is more than an ordinary node. c 1 , c 2 , c 3 , c 4 are the respective weighting factors. The node with the minimum W v is chosen to be the cluster head. Once a node becomes a cluster head, this node and all its cluster members are marked as "considered". Then, the election process is reapplied on all "unconsidered" nodes (Initially, all nodes are "unconsidered"). The election algorithm will terminate once all the nodes have been considered.

Maintenance of inter-cluster links

A routing path may break due to a broken link, especially due to the high mobility of nodes. In the case of an ad hoc network organized in clusters, the most critical links are the links connecting the clusters. Thus, we need an effective mechanism for maintaining connectivity between clusters despite of disruptions of some of these critical links to ensure the success of routing. We propose two variants: distributed and centralized solutions.

Distributed solution

When the moving of a gateway node breaks the inter-cluster link, the gateway node sends a RELG query (Request Error Link Gateway) to the gateway node of the neighbour cluster associated with the link. RELG query contains information of the new gateway nodes, knowing that each gateway node knows all gateway nodes in the same cluster. Finally the cluster head node is informed of this update.

Centralized solution

When a gateway node moves, the inter-cluster link may break. The moving gateway node sends a request to its cluster head so that it has to replace the gateway node (in this case the gateway node has no information about the topology of the cluster). In case of a broken inter-cluster link, the gateway node sends an error packet RERR (Request Error) to its cluster head node. The cluster head designates a new gateway node which has a link which replaces the broken inter-cluster link.

We opted for a centralized solution because it is compatible with the proposed clustering technique, which is based on a cluster management by an elected node, called cluster head.

Energy-Aware and Stable Cluster-Based Multipath Routing Protocol for Wireless Ad Hoc Networks 4 The ES-CMR multipath routing protocol

In this section, we present our efficient routing protocol, named ES-CMR (Energy aware and Stable Clustered based Multipath Routing protocol). It is based on the topology constructed by the clustering algorithm (Wang and Bao, 2007). Our protocol has two parts: intra-cluster and inter-cluster routing. In case of a request for a path between a source s and destination d, the cluster head associated to the cluster of the source s checks if the destination node d is a member of its cluster. If this is the case, an intra-cluster is launched. Otherwise, cluster external research is initiated to locate d, it is the inter-cluster routing. In all cases, two packets are used: RREQ (Route Request) is sent from the node source for the path discovery and RREP (Route Reply) is sent by the destination as a response to the request. The RREQ packet has the following structure: RREQ = (src_id, dest_id, b_id, seq_nbr_s, n_id, gats_id, seq_d, ttl) For example in Figure 2, if source node 8 wants to send a data packet to destination node 1, source node 8 first sends a request packet RREQ to node 3 (node 3 is the cluster head of node 8). Node 3 responds to node 8 by a reply packet RREP containing the sequence of intermediate nodes that forms the path to the requested destination: 8-3-2-1.

Inter-cluster routing

Inter-cluster routing allows a node source s to reach a destination d belonging to another cluster. The cluster head and gateways manage the communications between clusters.

Multipath routing discovery

When a cluster head receives a request for a path from a source s of its cluster C i to a destination d, first consults its cluster node set containing information about all nodes belonging to its cluster C i . It notes that destination node d does not belong to cluster C i . In this case, it sends a request RREQ to each gateway node listed in its gateway set CG i . Gateway nodes receiving the request RREQ forward the requests to neighboring gateway nodes (gateways of the neighboring clusters). Then gateway neighboring nodes forward the request RREQ to their cluster head which verifies the presence of the destination node in its own cluster.

Figure 3. Discovery requests paths

In Figure 3, node 8 sends a request RREQ to its cluster head node 3. Cluster head 3 broadcasts the request to all gateway nodes, i.e. nodes 5, 6 and 7. Each gateway node forwards the request to their neighboring gateway nodes. Thus, gateway nodes 21, 22, 10 and 11 receive the request, and they send it to their respective cluster head nodes 16 and 9. The path sequence is inserted in the request RREQ and is updated at each intermediate node. This solution guarantees loop-free paths, since a RREQ request is deleted by a node when the node identifier is listed into the path parameter of the RREQ request.

Reverse paths

Once a cluster head node locates in its own cluster the destination node d, it completes the path sequence by the path segment from the gateway node to the destination node d and then it sends reply packets RREP to the sender gateways nodes. Return paths used by the reply packet RREP are not necessarily the same paths used by the request RREQ, as the RREQ requests are sent by the intermediate cluster head/gateway node to the destination node d, but the reply RREP packets using a path indicated by the cluster head could be better than the paths of the RREQ requests.

Figure 4 Reverse reply paths

Using the previous example, in Figure 4, cluster head node 16 finds destination node d in its own cluster and sends a reply packet RREP to gateway nodes 21 and 22. These nodes broadcast reply packets to their neighbouring gateway nodes. In our example, these are gateway nodes 5 and 6. The reply packets follow the sequence of the intermediate nodes indicated in the path_seq_r field to reach the source node 8. Cluster head node 9 does not return RREQ requests to gateway nodes 10 and 11 as they are RREQ requests sender. In consequence, a source node may not receive any reply packet; in this case, when RREP_wait_time times out (RREP_wait_time has been initialized after sending the first packet RREQ), the source node initiates the path discovery process and repeats the path discovery process until a path is found. After three attempts, the path discovery process is canceled.

Multipath routing selection

This section describes path selection routing. When the node source receives the first RREP packet, it waits for a given amount of time (RREP_Wait_Time) to receive more RREPs before selecting the best path. The choice of the best path between a source node s and destination node d, is done according to energy consumption and path stability. In this approach, two functions are defined: the cost function fep j (t) which characterizes a path j at time t from an energetic point of view and the cost function fsp j (t) which represents the stability of path j at time t.

Energy aware function

Let fep j (t), the minimum residual energy of nodes constituting the path j for a source node s to destination node d at time t, be expressed as

  )) ( ( min , 1 1 t fen t fep j i n i j    (5)
Where fen i,j (t) represents the energy cost function of node i belonging to the j, formally:

      j i j i j i j i w t DR t Elev t fen , , , , .  (6)
Elev i,j (t) denotes the energy level of node i belonging to the path j at time t during a discovery process between a source node s and a destination node d, given by:

average j i j i E t E t Elev ) ( ) ( , ,  (7)
Where E i,j (t) represents the node i residual energy belonging to the path j at time t and E average is the average residual energy of m nodes that participated in the multipath discovery process between one source node s and one destination node d, defined as follows:

m E E m i i average    1 (8)
w ij is the weight factor of node i belonging to the path j, which depends upon various factors, like battery quality, battery capacity, battery life time. DR ij (t) is the drain rate of the node i belonging to the path j at time t, which is defined as the rate at which energy is consumed at a given node, usually when this node is used by others data paths as an intermediate node.

Link stability aware function

To calculate the link stability in mobile ad hoc networks, we consider the mobility of nodes as the main metric. The protocols based on node mobility use some criteria inherent of the node mobility, such as node coordinates, node direction of movement or node speed, into the calculation of the stability metric value. We use the node coordinates for our protocol due to its simplicity compared to other approaches. We exploit discoveries messages and hello messages for collecting coordinate information of neighbor nodes, to avoid the overhead of new send specific messages to collect these node coordinates. Each node wanting to measure the link stability adds its destination, hop count to the destination and destination sequence number to the original hello packet. A new field Distance is added to the hello packet in order to collect distances that separate the node i and the node j, is noted by d ij , see Figure 5. To calculate the stability of the link between two nodes i and j, the node i periodically sends message to the node j, when the node j receives the message, it detects its coordinates then sends it to the node i. Based on this information, the node i calculates the distance between itself and the node j, noted by d i,j . The stability cost function of the link ij at time t, is denoted by: fsl i,j (t), given by:

Energy-Aware and Stable Cluster-Based Multipath Routing Protocol for Wireless Ad Hoc Networks

      t Ml t SDl t fsl j i j i j i , , ,  (9)
Where Ml i,j (t) represents the mean of the n distances recorded between the node i and node j, defined as follows:

    n t d t Ml tn t t j i j i    1 , , (10)
SDl i,j (t) denoted the standard deviation of the distances recorded between the node i and node j, SDl i,j (t) is given by:

        2 1 , , , 1     tn t t j i j i j i t Ml t d n t SDl (11)
The function fsl i,j (t) represents the coefficient of variation, also known as relative standard deviation. It is a standardized measure of dispersion of a probability distribution or frequency distribution. The coefficient of variation formulated by fsl i,j (t) is used to quantify the measurement accuracy. In our case, it is the measurement of distances between two neighboring nodes. If the fsl i,j (t) tends toward 0, then we have a narrow distribution of distances, which means that the link is stable. If it is high, this corresponds to a large distribution, which means that the link is instable. Finally, we define the path cost function stability fsp j (t), given by:

  )) ( ( max , 1 1 t fsl t fsp j i n i j    (12)
The path stability is based on the stability of the links constituting this path. fsp j (t) is defined as the maximum of the link stability of all links constituting the path j.

Destination

Destination sequence number Hop count Di, j Expiration timeout

Omar Smail, Bernard Cousin and Imene Snoussaoui

Objective problem formulation

We design our multipath selection principle on the ordering of paths according to the energy consumption of their path nodes and the link stability of their path links. To satisfy this, we use a model using arbitrary importance weights for each criterion ( and β). The corresponding objective function fp j (t) is defined by combining the formulas ( 5) and ( 12):

) ( ) ( ) ( t fsp t fep t fp j j j       (13)
Our idea is based on sorting all paths between a source node s and destination node d by the ascending value of fp j (t). The path with the minimum fp j (t) is chosen to forward the data packets. We note that our model can be used to address many applications, with different constraints when we choose appropriate values for the parameter weights  and β. For instance, with applications that require energy saving, more importance is given to the coefficient  (>>β), since it is the weight associated to the path energy in the model. Finally, we note that the weights  and β are chosen such that the condition  + β=1 is satisfied.

Route management

Route error detection in ES-CMR is launched when a link fails between two nodes along a path from a source to a destination. When a neighbor node does not respond to three successive HELLO packets 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 routing table and then sends an RERR (Route ERRor) packet to the source node of the path to select another path. Each intermediate node forwards this RERR packet along the reverse path to the source node. When a source node receives an RERR packet, it erases the path from its routing table and looks for an alternative 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.

Complexity analysis

The main drawbacks of multipath routing protocols are, first, they may take too long to converge and second, they may have a high complexity in their number of messages. Because of the limited bandwidth of wireless links in an ad hoc network, message complexity must be kept low. In addition, in mobile networks, the rapid changes in network topology require that the routing protocols must find routes quickly. Wireless routing protocols are mainly classified into three categories: proactive, reactive and hybrid. For large networks, we propose a hybrid routing protocol which combines the merits of proactive and reactive approach and overcome their demerits. We measure the performance of our routing protocol, mainly by its message complexity, expressed as functions of the number of nodes (m) in the network. The message complexity is the maximum number of messages used by the routing algorithm in the worst case. For Energy-Aware and Stable Cluster-Based Multipath Routing Protocol for Wireless Ad Hoc Networks networks (as ours) with tree based routing structures, we assume that message complexity is O(m) size. The time complexity is the maximum number of steps required to establish the routes, in the worst case. Indeed we assume that internal computation time is dominated by the message transmission time. The main processes of our algorithm are the paths discovery and their maintenance, these processes are based on the messages broadcasting which takes O(m) time complexity. Finally, in our solution, the destination node and the source node wait for a certain period of time before replying to queries and starting the multipath selection procedure. These two waiting periods generates an additional time cost for the path selection, which is constant and independent of m.

Performance Evaluation of ES-CMR

In this section, we present simulation results to demonstrate the efficiency of our proposed routing protocol. First we present the metrics used for performance evaluation and then we evaluate our protocol by comparing it with a well-known protocol in the literature, namely EACMR. This evaluation comes with an analysis and discussion of results.

Performance metrics

We evaluate three key performance metrics: energy consumption, network lifetime and end-to-end delay. Energy consumption is the average of the energy consumed by nodes participating in packet transfer from the source node to the destination node during the whole simulation. The network lifetime can be defined in three ways (Bheemalingaiah et al., 2009) 2 : the time taken to exhaust the battery of the first network node, the time taken to exhaust the battery for a number network nodes, and the time when the battery of the last network node is exhausted. We choose the second way; this allows to see the evolution of the lifetime of the network. End-to-end delay is the average transmission delay of data packets that are delivered successfully over the total duration of the simulation.

Performance evaluation

In our protocol, the choice of the path made by a source node to transmit data packets toward a destination node is based on the energy of nodes and the path stability. This is mainly affected by the value of two weights  and β. 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 the protocol EACMR (Bheemalingaiah et al., 2009) 1 . We have chosen as values for the coefficients of the clustering protocol, the values proposed by the original paper (Wang and Bao, 2007), i.e. c 1 =c 2 =c 4 =0, c 3 =1. The values of simulation parameters are summarized in Table 1. [START_REF] Jung | A power control MAC protocol for ad hoc networks[END_REF], the energy consumption during the idle state is not considered because no real node energy optimization can be achieved in the idle state [START_REF] Kim | Routing mechanisms for mobile ad hoc networks based on the energy drain rate[END_REF]. In our simulations, we initialized the energies of the nodes randomly between 10 and 60 Joules (uniform distribution), which corresponds to the usual capacity of a battery. The Random Waypoint model is used to simulate node movement; the nodes could move in all possible directions with displacement varying uniformly between 0 to a maximum value, per unit time. The nodes moved randomly in all possible directions with a maximum displacement of 15 m/s, along each coordinate axis. The weighting factor w ij is set to 1, considering that all the nodes have the same battery parameters. The drain rate DR ij (t) is chosen randomly between 1 and 3. Finally the source and destination nodes are randomly selected as well as the distribution of the network nodes (uniform distribution).

Figure 6 shows the energy consumed by the ES-CMR and EACMR protocols for different values of  for a number of network nodes equal to 180 nodes. Four  values are presented: 0.3, 0.4, 0.6 and 0.7. We note that when  equals or greater than 0.6, ES-CMR produces effective results. In consequence, we set = 0.6 for the rest of our simulations. Initially, ES-CMR is not better than EACMR, because initially the majority of packets are not yet transmitted, so the total energy of sending and receiving packets is not important. But as time increases, there is some energy imbalance which is noted and then the impact of our protocol is significant. The energy consumed in ES-CMR is less than the energy consumed by EACMR. In Figure 6 (with = 0.6) the energy consumed by ES-CMR is reduced by 39% when compared to EACMR, when simulation ends (at time 200 s).

.

Figure 6

Energy consumed over time ES-CMR with 6, consumes less energy than EACMR, because ES-CMR favours paths with a high energy based on paths selection (a heavy weight is associated to the energy aware metric). The network life depends on the node expiration which in turn depends of the energy consumption. The network lifetime metric is shown in Figure 7 at different times for a number of network nodes equal to 180 nodes. The network lifetime of ES-CMR is longer than EACMR, at every time, ES-CMR has a smaller number of nodes that is exhausted compared to EACMR. Thus, ES-CMR balances the energy among all the nodes and using stable paths, this extends the path lifetime and hence the network lifetime.

Figure 7 Number of exhausted nodes over time

Figure 8 shows the average end-to-end delay. The average end-to-end delay for all tested protocols increases as the network size increases, but the average end-to-end delay of ES-CMR is lower than EACMR. When the number of nodes of a network is between 60 and 120, the delay of the ES-CMR protocol is nearly 58% lower than that of the EACMR protocol and nearly 61% lower when the network number of nodes is between 120 and 180. Indeed our ES-CMR protocol prefers energy efficient paths, which ensures less path failures. Moreover, ES-CMR is a routing protocol that can use alternative paths when a link path is broken. The alternative path is chosen between the most stable paths with enough energy. This minimizes links failures, and reduces the delay of rerouting and overhead consumption.

Conclusion

In this paper, we propose ES-CMR which is an energy aware and stable clustered-based multipath routing protocol for wireless ad hoc networks, in order to reduce node energy consumption, end-to-end delay and extend network lifetime. ES-CMR is a cluster-based protocol that improves the performance of ad hoc networks. The proposed protocol is a multipath routing protocol that uses an energy-aware mechanism which exploits the residual energy of nodes and link stability to select the best discovered paths. We conducted simulation experiments to evaluate the performance of our protocol and to demonstrate that it performs significantly better than a well-known protocol proposed in literature such as EACMR. ES-CMR reduces energy consumption by at least 39% compared to EACMR for a network size of 180. ES-CMR outperforms EACMR by extending the node lifetime and has a lower average end-to-end delay, because paths are computed depending on the energy of their nodes and their stable links.

Figure 1

 1 Figure 1 Graphical representation of nodes.

Figure

  Figure 2 Intra-cluster routing

:

  Request packet RREQ, s: Source node, d: Destination node Cluster head Gateway Ordinary node Energy-Aware and Stable Cluster-Based Multipath Routing Protocol for Wireless Ad Hoc Networks

Figure 5

 5 Figure 5 Structure of a HELLO packet for ES-CMR.

Figure 8

 8 Figure 8 End-to-end delay versus number of nodes

  When a source s of a cluster C i searches to establish a path with a destination d of the same cluster C i , node s sends first a RREQ packet to the cluster head CH i . Since the cluster head contains information about its cluster member nodes, CHi responds to the request of node s by sending a reply packet RREP containing the sequence of intermediate nodes between s and d. Thus, the node s can communicate with the node d using this path.

	with
	-src_id : source node identifier
	-dest_id : destination node identifier
	-b_id : broadcast identifier
	-seq_nbr_s: sequence number of the transaction given by source node
	-n_id: neighbor identifier
	-gats_id : gateway node identifier
	-seq_d : sequence of identifiers of the intermediate nodes toward the destination
	node
	-ttl: time to live
	The RREP packet has the following structure:
	RREP = (src_id, dest_id, seq_nbr_d, seq_r, e ij _cumul, s ij _cumul, ttl) with
	-src_id: source node identifier
	-dest_id: destination node identifier
	-seq_nbr_d: sequence number of the transaction (given by the source node)
	-seq_r: sequence of identifiers of the intermediate nodes toward the node source s
	-e ij _cumul: cumulative value of the energetic coefficient
	-s ij _cumul: cumulative value of the stability coefficient
	-ttl: time to live
	4.1 Intra-cluster routing

Table 1

 1 Simulation parametersOmar Smail, Bernard Cousin and Imene SnoussaouiTo evaluate ES-CMR, we use the network simulator ns-2 (Network Simulator ns-2). Simulation time equals 200 seconds, this duration gives significant results. During each simulation, constant bit rate (CBR) connections are generated, each of which 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 0.3 seconds. We vary the number of network nodes from 60 to 180 to get different scenarios in an 840 m × 840 m environment. 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] it is a shared-media radio with a channel bandwidth of 2 Mbps, a free space radio propagation model and a nominal radio range of 250 m. Each node is equipped with a single network interface card. The distributed coordination function of IEEE 802.11 is assumed at MAC layer. Each simulation is carried out under a different number of network nodes and the performance metrics are obtained by averaging over 10 simulation runs. We assume that a node consumes 281.8 mW while receiving and 281.8 mW while transmitting

	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	60, 90, 120, 150 and 180
	Data payload	512 bytes
	RREQ_Wait_Time	0.3 s
	RREP_Wait_Time	0.3 s

Energy-Aware and Stable Cluster-Based Multipath Routing Protocol for Wireless Ad Hoc Networks