he recent technological advances in wireless communication, electro-mechanical systems and digital electronics have led to the development of small, low power and low cost sensor nodes which communicate within short range of distances. Sensor nodes are active nodes which perform the sensing task to sense their environment. These nodes then communicate the sensed data among each other or directly to the sink or base station. A sensor network is described as a large network of such sensor nodes which are densely deployed either inside a phenomenon or very close to it [1]. Wireless sensor networks differ from other wireless networks in numerous ways. Sensor nodes within a sensor network are highly constrained in terms of energy, processing and storage capabilities. The data flow in sensor networks is from various sensor nodes to a single base station called sink. Since, there is large number of sensor nodes; the data collected might be redundant. Due to this, the traditional routing protocols cannot be used for wireless sensor networks [2].

The routing techniques in wireless sensor networks can be classified on the basis of network structure and protocol operation. On the basis of network structure, we have flat, hierarchical and location based routing. Routing on the basis of protocol operation can be classified as multipath, query based, QOS based, negotiation based and coherent based. In order to develop an energy efficient routing algorithm, we combine the advantages of multipath routing and hierarchical cluster based routing.

Wireless sensor network consists of large number of sensor nodes. Applications that require scalability and efficient data aggregation can make use of clustering. In clustering, the whole sensor network is divided into small clusters where each cluster is headed by a cluster head. The major role in sensor node clustering is to select a set of cluster heads among the nodes in the network, and group the rest of the nodes with these heads.

Multipath routing protocol makes use of multiple paths for routing the data rather than using a single path. This helps in load sharing and load balancing. By using multipath routing, we can increase the reliability of the network but at the same time the overhead of maintaining alternate paths is increased.

Yahya and Ben-Othman [3] proposed a multipath routing protocol called REER (Robust and Energy Efficient Routing). This energy efficient multipath routing protocol makes use of residual energy, buffer space and signal to noise ratio to find out the next hop. In this way, the best preferred path and alternate path is calculated. In the first version(REER-I) Data is transmitted over a single path until the path cost falls below some threshold.

Younis and Fahmy [4] gave a model in which each sensor node can act either as a source or a server (cluster head).The major challenge is to find appropriate servers to satisfy the system goals. In this paper, the selection of cluster head from all the nodes is done probabilistically based on the residual energy of the nodes. The remaining nodes join the clusters such that the communication cost is minimized.

LEACH (Low Energy Adaptive Clustering Hierarchy) [2] [7] was the first sub-cluster-style routing protocols in WSN. LEACH is an energy efficient algorithm because it uses data compression techniques and subcluster dynamic routing technology. In this, the cluster heads are chosen randomly and therefore the network load is balanced and also rapid death of cluster heads is prevented.

Khedoand Subramanian [5] proposed the MiSense hierarchical cluster based routing algorithm (MiCRA) to extend the lifetime of sensor networks and to maintain a balanced energy consumption of nodes. MiCRA is an extension of the HEED algorithm with two levels of cluster heads. In this, cluster heads are selected randomly based on their residual energy and nodes join clusters such that communication cost is minimized.

Multihop-LEACH [8] is a cluster based routing algorithm in which self-elected cluster heads collect data from all the sensor nodes in their cluster, aggregate the collected data by data fusion methods and transmit the data through an optimal path between the cluster head (CH) and the base station (BS) through other intermediate CHs and use these CHs as a relay station to transmit data through them.

W. Lou [6] proposed an N-to-1 multipath routing protocol that finds different node-disjoint paths between a sink and a source node. Nodes are arranged in a spanning tree structure with the sink as the root. The protocol finds multipaths by traversing the tree. Multipaths are used to distribute the traffic in order to improve the reliability and security of the data transmission.

Our proposed routing algorithm is a combination of both cluster based routing and multipath routing. We combine the advantages of hierarchical cluster based routing and multipath routing in order to get a reliable, energy efficient routing algorithm. We modify LEACH (Low Energy Adaptive Clustering Hierarchy) routing protocol by introducing multiple hops for inter cluster communication. The routing protocol used for this inter cluster communication is based on REER (Robust and Energy Efficient Multipath Routing), an energy efficient multipath routing protocol.

In this paper, we first explain LEACH and REER routing protocols and then give our proposed method of energy efficient routing in wireless sensor networks.

LEACH [7] is one of the first hierarchical routing protocols for wireless sensor networks. The major aim of this protocol is to increase the lifetime of the network. In this protocol, the whole network is divided into small clusters and each of these clusters has a cluster head. The non cluster-head nodes are known as the member nodes of that cluster. Only the cluster heads can communicate directly with the sink. The member nodes send their data to their respective cluster heads which then send it to the sink.

The cluster head is responsible of performing all the important functions like collecting the data from its member nodes, aggregating the data and sending the aggregated data to the sink. Due to these additional functions, the cluster head dissipates more energy as compared to rest of the nodes. If the same node is used as cluster head, it will drain all its energy and die quickly. Therefore, LEACH introduces randomized rotation of cluster heads to save the battery of individual node.

The whole of LEACH operation is broken down into a number of rounds. Each of these rounds has 2 phases: setup phase and steady state phase. The setup phase is meant for the organization of clusters and in the steady state phase, data transfer to the base station takes place.

The working of setup phase is briefly described as below.

Each node in the network generates a random number between 0 and 1. The value of generated random number is compared to a threshold value T(n). If the number is less than T(n), that node is selected as cluster head. The value of threshold T(n) is calculated as follows:

Where, n is the node id in the current wireless sensor network, p is the predefined percentage of cluster heads, r is the current round number and G is the set of nodes which have not been selected as cluster heads since the last 1/P rounds. By using this function, there is a randomized rotation of cluster heads and so the same node does not continually drain its energy.

After the cluster heads have been determined, all the cluster heads send a broadcast message in the network to announce themselves. Each normal node decides on which cluster to join on the basis of the received signal strength. It then sends a request message to the corresponding cluster head. After receiving the request messages from the nodes, the cluster head confirms them as members of that particular cluster, adds them in the routing table and allocates TDMA table of slots for the cluster members telling each member when it can transmit data.

After the selection of cluster heads and clustering of member nodes, the steady state phase starts. In this phase, transfer of data takes place. All the member nodes send their data to their respective cluster heads by single hop communication during the allocated slot according to the TDMA table. After receiving the data from each member node, the cluster head fuses it into a single signal and transmits it to the base station. After the completion of data transfer, the entire network comes into the next round.

Bashir Yahya and Jalel Ben-Othman [3] have proposed a robust and energy efficient multipath routing protocol (REER).REER calculates multiple paths for communication between source and destination. These paths are calculated on the basis of residual energy, buffer space and interference (signal to noise ratio).After the discovery of multiple paths, the data is transferred through the best preferred path. When the cost of the best preferred path falls below some threshold, next alternative path is used.

A function called link cost function is used to calculate the next hop in the path discovery phase. The link cost function depends on the residual energy of the node, available buffer space and signal to noise ratio. Let N x be the set of neighbors of the node x. We can get the next hop by the given formula Next hop = max y?Nx { ?E resd , y + ? B buffer,y + ?I interference,xy } Where, E resd, y is the current residual energy of node y, where y?N x , B buffer, y is the available buffer size of node y, andI interference, xy is the SNR for the link between nodes x and y.

The total cost of the path is calculated from the individual link costs. The total cost C total for the path P which consists of a set of K nodes can be given as the the sum of the individual link costs l (xy)i , i? K along the path. This means:

The whole operation of REER is explained as follow. The first phase is the initialization phase in which each sensor node broadcasts a HELLO message. The purpose of this HELLO message is to get information about the neighbors. During this phase, each sensor node maintains and updates its neighboring table. After this, every sensor node has all the information about its neighboring nodes. With this information, they calculate the link cost using the link cost function. Now, the sink begins to calculate its preferred next hop and sends a route request message to the most preferred next hop. The same procedure continues from hop to hop until the source node is reached. The sink sends an alternate path route request to its next most preferred path for finding the alternate path.

The multiple alternate paths are kept alive by flooding KEEPALIVE messages through those paths. The flooding of these messages is done by the source node periodically.

After the paths and multipaths have been discovered, transfer of data takes place. Upon receiving a query packet, the source nodes begin collecting all the relevant data and send it to the sink via the best preferred path. Each node consults its neighboring table and finds out the ID of the next hop, and then forwards the data to its next hop. This process continues until the data reaches the sink node. Transmission of data continues over the primary path until a certain threshold is reached, then the next best alternative path is being used, and so on.

After the brief overview of the LEACH and REER routing protocols, we give our proposed method of energy efficient routing. LEACH is a very efficient clustering protocol with randomized rotation of cluster heads. But since the communication from cluster head to sink is single hop, it is a very high energy transmission. Energy consumption of the inter-cluster is much more than the intra-cluster. Therefore, it is obviously important how to set the reasonable intercluster communication mechanism to decrease cluster heads' energy consumption [9].This can be rectified by introducing multiple hops for cluster head to sink communication since the smaller the distance to transmit the lower the consumption is [10]. This means, that each cluster head will send its data to the sink by sending it to the intermediate cluster heads. Now, since the cluster head to sink communication is multihop, we need some routing scheme. We introduce a routing similar to REER for this multihop communication between cluster head and sink.

Cluster Formation phase: In this phase, clustering of the network takes place. Clustering is usually used to speed up route discovery by structuring the overall network nodes hierarchically [11]. The procedure for the selection of cluster heads and cluster formation is similar to that of LEACH. Each sensor node in the network generates a random number to decide whether it will become a cluster head or not. The random number generated by the node is compared to the threshold T(n) and if the value is less than T(n), it is selected as the cluster head. This threshold value is calculated on the basis of percentage of cluster heads to be elected and the number of times the node has been elected as a cluster head.

In this way, each node gets a chance to be the cluster head. After the selection process, each node that has been elected as cluster head broadcast an advertisement message. When the nodes receive the advertisement message, they decide on which cluster to join on the basis of received signal strength from the cluster head. These nodes inform the cluster head that they will join the cluster by sending a message to that cluster head.

In the LEACH protocol, the cluster heads send their data directly to the sink irrespective of the energy being utilized for this transmission. In order to minimize this energy usage, we introduce multiple hops between cluster head and sink. The cluster heads send their data to the sink via other cluster heads. Now, a HELLO message is broadcasted by the cluster heads to other cluster heads and the sink. In this way, all the cluster heads have all the necessary information about the other cluster heads in the network. Each head maintains a neighboring table. The base station or the sink will now calculate the preferred next hop using the link cost function as proposed by REER. It sends a RREQ message to the calculated next hop. The preferred next hop again computes its next hop and sends the RREQ message. This continues until the source node is reached. The base station then sends the alternate path RREQ. The primary and alternate paths are node disjoint. Due to this, in case of failure of a path, the alternate path will not be affected. Route maintenance: Now, for keeping the multiple paths alive, a KEEPALIVE message is flooded through the alternate paths. Through this, all the paths are maintained Data transferring phase: After the grouping of nodes and discovery of multiple paths, transfer of data takes place. We assume that each node has data to send. The member nodes send their data to their cluster head. This is a single hop communication. Since the nodes within the cluster are within small transmission range with the cluster head, therefore, energy used is low. Also, due to single hop communication, the data delivery ratio is high. Transmission of data from the cluster head to the base station takes place through the discovered multipaths. The data is transferred through the primary path. In case of node failure, i.e. when the data packet cannot be forwarded to the next hop in the current path, the current link is considered to be disconnected. So, an error message is sent to the source node. When the source node receives this error message, it removes the current path from its routing table and selects the next preferred path from its routing table. After this, the transmission process is resumed. The use of alternate paths makes the communication more reliable. Node failure does not affect the reliability of the network.

After a single round is completed, the cluster reconstruction takes place. New cluster heads are elected and again the whole process continues.

We simulate and analyze LEACH [7], REER [3] and our proposed method on NS2 [12] simulator. We evaluate the results on the basis of lifetime of the network and average delivery ratio. Our simulation environment consists of a 100m x 100m network consisting of 200 randomly deployed nodes. All the nodes are assumed to have same initial energy. The simulation runs for 100secs.

We evaluate the energy efficiency with the lifetime of the network. Fig. 1 shows a graph between the number of dead nodes and the simulation time. The graph clearly shows that the lifetime of proposed algorithm is better than LEACH and REER. This is due to the energy aware clustering used in the proposed algorithm. We use multihop inter cluster communication, thereby avoiding high energy transmission. Also the multipath routing used, considers the residual energy of the nodes while selecting their next hop. Due to this, a single node does not continually drain its energy, thereby increasing the lifetime of the network.

It is the ratio of number of packets successfully received to the number of packets sent. Fig. 2 shows the graph between the average delivery ratio of nodes and time. The average delivery ratio of LEACH is best among all the three routings because LEACH is a single hop routing algorithm. The data does not need to travel via intermediate nodes. The average delivery ratio of REER is the lowest. Our proposed algorithm lies between LEACH and REER since it has fewer hops as compared to REER.

We have successfully implemented our proposed routing algorithm. In our protocol, cluster formation is same as in LEACH. Nodes within a cluster transfer data to the cluster head through single hop. For the transfer of data from cluster heads to the base station, we introduce multihop communication. The path used for this multihop data transfer is decided by using the link cost function. The link cost function uses the residual energy, buffer space and signal to noise ratio to determine the next hop.

We find that the proposed routing is more energy efficient as compared to LEACH and REER. This is because the proposed routing uses the benefits of both multipath and cluster based routing. Our algorithm is more reliable and has a higher average delivery ratio than LEACH. This is due to the use of multipaths. In case of failure of a single path, alternate path is used.

As our future work, we will analyze the protocol more deeply by evaluating other performance metrics such as control overhead and average delay. We will also work on sensor networks with mobile nodes.