Survey on Single Path and Multipath Energy Efficient Routing Protocols for Wireless Sensor Networks ()
1. Introduction
The most important feature of a routing protocol, in order to be efficient for WSNs, is the energy consumption and the extension of the network’s lifetime. Many routing, power management, and data dissemination protocols have been specifically designed for WSNs where energy awareness is an essential design issue. Routing protocols in WSNs might differ depending on the application and network architecture. In this article we present a survey of state-of-the-art routing techniques in WSNs. We first outline the design challenges for routing protocols in WSNs followed by a comprehensive survey of routing techniques. Overall, the routing techniques are classified into three categories based on the underlying network structure: flit, hierarchical, and location-based routing. Furthermore, these protocols can be classified into multipath-based, query-based, negotiation-based, QoS-based, and coherent based depending on the protocol operation. The design trade-offs between energy and communication overhead savings in every routing paradigm are also studied. We also highlight the advantages and performance issues of each routing technique. The article concludes with possible future research areas.
Sensor networks differs from other communication networks, usually depend upon non rechargeable or replaceable battery for power. A WSN is a network of small low-power wireless sensors and it has a variable network infrastructure whereas wireless sensors nodes possess embedded processing as well as data communication capabilities. WSN are employed for specific mission or application and they work under certain constraints. They occupy a geographical area called as sensor field [1] [2] [3] [4] [5] .
WSN contains many small sensor nodes and one or more base station (BS). Nodes can sense and establish wireless communication between them or route data to BS, which are the most powerful nodes and connect other nodes with rest of world. Major application of sensor network is to collect information from environment. They also have wide applications in Military environment, Habitat monitoring, Disaster management, medical and health care, home networks, biological, nuclear, radiological, and explosive materials etc. [6] .
WSN routing methodology can be classified into two categories; network structure or protocol operation. According to network structure, a sensor network can be nonhierarchical, hierarchical or location based. Under the first method, every node has the same role and utility. Alternatively, in hierarchical based model, numbers of nodes are divided into clusters and allocate various functions. Relevant data is transmitted through nodes in Location-based protocol.
Power consumption in wireless sensor nodes is worst, even if data rate through nodes are least. AC power is given to one or few nodes. Life of rechargeable battery is expected to be few days, months or years. Batteries should be small enough so that they can be fitted in nodes. In this paper we have discussed energy efficient routing using single path and multipath.
A wireless sensor network (WSN) has important applications such as remote environmental monitoring and target tracking.
Following a top-down approach, an overview of several new applications and the review of literature on various aspects of WSNs is given in this paper and following problems are classified into three different categories: 1) internal platform and underlying operating system, 2) communication protocol stack, and 3) network services, provisioning, and deployment. The past few years have witnessed increased interest in the potential use of wireless sensor networks (WSNs) in applications such as disaster management, combat field reconnaissance, border protection and security surveillance. Sensors in these applications are expected to be remotely deployed in large numbers and to operate autonomously in unattended environments. Figure 1 shows the arrangement of sensor networks [7] .
Rest of paper is divided into six sections. Related work is discussed in Section
2. Efficient routing protocols are presented in Section 3. Multipath routing protocols are discussed in Section 4. Simulation results of single and multipath routing is described in Section 5 and conclusion is drawn in Section 6.
2. Related Work
Extensive research has already been performed in the field of routing implementation in sensor networks. L.K. Chourse et al. [8] had detailed study on LEACH protocol. They have proposed a mathematical methodology for cluster head selection and also have discussed merits and de merits of the proposed algorithm. The main problem of proposed protocol was distance between cluster head and base station. If distance is increased, the protocol will not be energy efficient any more. They proposed many versions of LEACH to resolve this problem i-e E-LEACH, TL-LEACH, M-LEACH, LEACH-C and V-LEACH. M. Dewakar et al. [9] had proposed EELBCRP (Energy-Efficient Level Based Clustering Routing Protocol). They compared this protocol with LEACH and their simulation results shows that EELBCRP is more energy efficient than LEACH. They had also discussed mathematical models for selection of cluster head.
R. Vidhyapriya et al. [10] proposed an energy efficient adaptive multipath routing technique with multiple path utilization between source and destination node. Adaptive routing decreases routing overhead and it also saves sensor nodes from premature death. Marjan Radi et al. [11] observed that multipath routing protocols proposed for ad hoc networks can’t be used for WSN because of resource constraints, this issue has motivated researcher to develop multipath routing protocols for WSN. Al-Karaki presented challenges and design issues in WSN multipath routing. Alwan has given an overview on fault-tolerant multipath routing protocols. In this paper, routing protocols for single path and multipath has been discussed.
3. WSN Proposed Protocols
In this paper, an overview of three very important routing protocols proposed for WSN, LEACH, PEGASIS, VGA for single path routing and interference in the case of multipath routing, is provided and their comparative results are also discussed. Sensor networks are simulated using Sensoria simulator.
3.1. LEACH Protocol
Heinzelman, et al. [6] introduced a hierarchical clustering algorithm for sensor networks, called Low Energy Adaptive Clustering Hierarchy (LEACH). Energy saving is done in this protocol by allowing the cluster heads to collect data from all nodes in the cluster, aggregates it and send a single report to base station. The protocol reduces the energy of cluster heads by selecting new sets of cluster heads in start of each round.
In this protocol, the process is done into rounds, during each round cluster heads are formed. Each node joins the nearest cluster to send data. The cluster heads integrates and squeezes the data and sends it to BS. In this protocol, all nodes except cluster heads are turned off and when data is to be transmitted, they are turned on by sending control signal.
LEACH protocol can be explained by taking example of any university in which different departments are considered as clusters and their chairmen as cluster heads. The faculty of department reports to chairmen and then they forward the information to dean of university; the base station. LEACH protocol is shown in following Figure 2.
3.2. PEGASIS Protocol
Power-Efficient Gathering in Sensor Information Systems (PEGASIS) is enhancement over LEACH protocol. In this protocol, each node communicates only with its closest node. Unlike LEACH protocol, nodes arrange themselves in the form of chain and data is transmitted from one node to its neighbor node. Each node forward the data to its neighbor node, after receiving the data this node will add its own information in existing data and transmits it to the next node. All nodes repeat the same process until data reaches the base station through leader node. In this way, energy consumption reduces in each round.
In PEGASIS protocol, chain is formed in two steps. In first step, nodes and base stations are self-organized using the greedy algorithm. After chain formation, base station broadcast its information to sensor nodes. This protocol lowers the bandwidth requirement and reduces the overhead.
This protocol can be explained through example of famous game “Chinese whisper”. In which people communicate each other one by one. First person whisper something to second person, second person whisper the same information to third person and so on. In the end the last person reveal the message. This protocol follows the same scenario and in this way energy consumption is minimized. Figure 3 shows communication in PEGASIS protocol [12] [13] .
3.3. VGA Protocol
Virtual Grid Architecture (VGA) is an energy efficient routing protocol. The protocol increases the life of network by data aggregation and in network pro- cessing. In this protocol fixed virtual topology is created in which extremely low mobility nodes are arranged as shown in Figure 4 [14] [15] .
In VGA, area of network is divided into fixed, equal and disjoint symmetrical shape zones. To form a simple virtual topology we select square shape zone. CH is selected inside each node.CH also called local aggregators (LA) helps to balance the load distribution. CH can only communicates with its horizontal and vertical neighbors, so communication is done on virtual grid. The responsibility of master aggregator (MA) is to communicate with base station and they collect data from LA. It is not necessary that base station is located at the corner of grid; it can be located at any position.
4. Energy Efficient Multipath Routing Considering Wireless Interference
One can estimate network energy cost by size of the data packets and the transmission range. A formulation is first made to estimate energy cost for a packet of n bits. Initially for sending that packet and then for receiving the same packet [16] [17] .
Transmitter energy cost can be given as sum of ETx and
. Where ETx is energy consumption for communication,
is energy used by amplifier that maintains SNR to optimum level, d is distance in meters between two nodes and n is the number of bits transferred.
Routing process in the WSN starts when source node after gathering information from the remote host wants to send it to the processing node, in order to do so it sends routing request. While doing so routing protocol points out the nodes that are present in the interference zone of the first path. The nodes that are pointed out by the first path are now always be avoided.
4.1. Routing Request of the First Path
Source node keeps on collecting data from the remote nodes after collecting data from the connected remote host it sends it to the processing. Request data is sent to all the nodes. Every node then checks the request packet and record the required information in the routing table. Request data may include the message, energy of the sending node and the ID of the sender. When the sending instant occurs, this particular node forwards this packet to the node next to it. If the request packet is received after the reception time it is discarded. If the receiving node has received packet for the first time it records the information of request packet for in its table as shown in Figure 5 [17] .
As the reception time of the processing node arrives it checks its routing table to find the number of sender nodes. It chooses that node for making route that has highest energy among all those nodes that have same message ID. If a node with less energy is choose this decreases life of that path.
4.2. Reply of the Path
Once the routing node is selected, the destination node sends the routing reply i.e. RREP packet to it. It includes receiver node ID number (Rec. ID), sender node ID number (S.ID) and message ID number .The routing reply packet consists of four contents, as depicted in Figure 6.
After checking whether it is reply packet node or not, it checks the receiver node ID number to confirm if this packet is sent or not. If receiver node ID is its own, the node saves the message ID number, checks sender’s node ID, and send it to the next node. The node with maximum energy is chosen for the route. As the source node sends routing reply within its transmission radius, receiving node check the receiver’s ID and interference flag bit is set, if reply packet is sent to it. Now this node will always be avoided for next route formation. Route from source to destination is shown in Figure 7.
5. Results and Discussion
5.1. Simulation Results of Single Path Routing
Laiali Almazaydeh et al. [6] calculates the life time of above discussed protocols
Figure 6. Contents of routing reply packets.
Figure 7. Route from source to destination.
on sensoria simulator. Under the same scenario, by keeping the initial energy level 0.5 Joules and transmission range was first kept 15 m and then 70 m and then compared the results of three protocols.
By keeping the transmission range 15 m the lifetimes of the network are 2174, 1017, and 28 rounds for PEGASIS, LEACH and VGA respectively.
When transmission range is 70m, the lifetimes of the network are 8124, 2285, and 741 rounds for VGA, PEGASIS, and LEACH respectively. Figure 8 shows the network life time and Figure 9 shows the comparison of all topologies according to transmission range.
5.2. Simulation Results of Single Path Routing
During simulation it is considered that there are two paths that are discovered in the routing protocol. Performance of protocol is tested using software NS2 (based on discrete event on the LINUX). In these simulations sensor nodes are randomly distributed on a square area of 200 m length by assuming that communication radius of each node is 20 m and the energy of each node is set to 2 J. Number of destination node is 1 and the number receiver and transmitter is given by 50 nJ/bit [17] .
Figure 10 shows the distribution of 200 nodes. Sensor nodes are randomly arranged on a square of a length of a side 200 m. Figure 11 depict the network energy cost and the routing energy cost when k is set 100 [17] . Total energy consumed by nodes throughout the network lifespan is depicted as total energy cost and routing energy cost means energy spent for finding route. This routing protocol has more survival node then 12MR while the total energy cost of the routing protocol is less than 12MR. Teo et al. proposed 12MR protocol in 2008,
(a)(b)
Figure 11. (a) Network energy cost; (b) routing energy cost.
it is a protocol which can discover the disjoint points of zone and throughput is increased.
6. Conclusion
Due to energy constraints of WSN energy efficiency is special concern while designing routing protocols. In this paper, performance of three protocols i.e. LEACH, PAGASIS and VGA were reviewed and compared. The results shows that for limited transmission range PAGASIS has maximum lifetime while when range is farther, VGA saves more energy. We have also discussed multipath energy-efficient routing protocols for WSN. Energy efficiency of routing protocol was considered in term of interferences in the WSN. It marks nodes that are present in the interference zone of the first selected path and then always avoids those nodes while making path. In this way energy that is wasted by interference can be saved. Simulation results show that the proposed routing protocol reduces energy cost.