A Survey on Routing Protocols for Wireless Sensor Networks

Abstract

In recent advances, wireless sensor network energy efficiency is the prime consideration. The routing protocols in WSNs are different from traditional network, application-oriented and depending on network architecture. This paper consists of a survey in the area of routing protocol for WSNs. The routing is categorized into five major sections: data-centric, self-organizing, hierarchical-oriented, location-aware and network flow and QoS-aware. Various protocols fall in these categories described in appropriate section.

1 Introduction

A wireless sensor network (WSN) is a wireless network, which contains distributed autonomous nodes (sensors). Nodes are capable of capturing information, processing and communicating to each other and routing data back to the base station. Base station issues commands to manage sensors, collects sensors data and processes it. WSN provides a simple and economic approach for the deployment of distributed sensing nodes and controlling them. WSN plays an important role in a wide variety of area ranging from sensing physical and environmental conditions, measuring medical parameters for health applications, to security-related application as in hostile environment of a battlefield, building security, fire fighting, etc. A WSN consists of many nodes which are either fixed location-based sensors or movable sensors in the monitoring environment.

2 Routing Protocols

In a multi-hop network, the role of transitional nodes is to disseminate the packets from source to destination. In similar multi-hop networks, an intermediate node including the source node requires a mechanism to determine which neighboring node would be used to pass the packet to reach at the destination, eventually. The process of passing the packets to next node is known as forwarding.

There exist several different methods to organize the forwarding process. The simplest method, to send a packet to all its neighboring nodes, for the network which contains both the source and the destination in it, is known as flooding. Another method to forward the packet to any arbitrary node, to eventually send the packet to all the neighboring node, is known as gossiping. But both the methods lie on the extreme ends, so there exists an intermediate method called controlled flooding. In this method, the source sends the packet on an arbitrary path or each particular node forwards the packet to a portion of a set of its neighbors.

The performance of the forwarding is measured by the means of number of packets forwarded or delayed. The suitability of a neighboring node completely depends on the cost induced in sending a packet from the source to intended destination using this specific node. The cost can be estimated by number of hops or the energy required, from source to destination. Each node collects the value of the cost for the next hop and arranges these values in a tabular form, called routing table. Various routing algorithms are derived to determine routing tables, and these routing algorithms are the part of routing protocols.

In wired or traditional networks, distance–vector algorithms, like Dijkstra and Bellman–Ford, are used to produce a route. But in multi-hop wireless networks, due to resource constraints, different approaches are prescribed. The properties of a routing protocol for WSNs are low overhead, distributed, self-organizing and handling frequently changed topology.

2.1 Network and System Architecture

Wireless sensor network is foremost depending upon the application, hence leads to difference in network requirements, architecture, design goals, resource constraints and computational and communicational usage. It further affects the performance of any routing protocol.

2.1.1 Node’s Architecture

In preliminary research in the field of WSN, for all the sensor nodes, an assumption is imposed, to be homogeneous in the terms of communication, computational, node’s composition and power. Due to different types of applications and its functionalities, some nodes are quickly drained in similar time duration and lead to the concept of heterogeneous nodes.

2.1.2 Node Deployment

Node deployment is a rudimentary issue in wireless sensor networks. An appropriate deployment technique can decrease the complexity in the terms of routing, data aggregation, computations, communications and power. In large sensor networks, the sensors are deployed by aerial means and creating a random infrastructure. The nodes have to be self-organized and able to locate the neighboring nodes.

2.1.3 Energy Considerations

Energy consideration is the prime factor during the formation of an infrastructure. The energy consumption of the wireless radio is proportionate to the square of distance or presence of obstacles of higher order. Direct communication is performed well for the nodes nearer to sink, and multi-hop consumes less energy for larger distance. However, multi-hop introduces the notable expenses for topology management and MAC.

2.1.4 Data Delivery

The data conveyance to the sink in WSNs can be categorized into persistent, event-based, query-based and hybrid based on the requisitions of the networks. The data delivery scheme is highly influenced by the minimization of energy dissipation and route sustainability.

2.1.5 Data Aggregation

Since each node senses and forwards the sensed readings to the sink, it generates a large number of redundant packets. Data aggregation combines the information from different resources by applying different functions. This technique is utilized to reduce battery consumption and congestion optimization in various routing protocols.

2.1.6 Network Dynamics

Most of the network setup is assumed to be stationary, and the topology is fixed. Routing in static network is less challenging. On the other hand, some network is completely mobile and topology is changed according to the time. Tracking the required node is also added with the basic functionality of routing.

2.2 Characteristics

There are several characteristics that make routing in WSN very challenging and distinguish from traditional networks.

• 1. No Global Addressing: Due to preparation within the unattended and remote field, it is impracticable to create global addressing strategy. Therefore, classical IP-based protocols cannot be applied to WSNs.

• 2. Multiple Source–Single Destination: Unlike, one to at least one traditional networks, the majority applications of WSNs need to produce the perceived information from multiple sources to single destination.

• 3. Redundancy: Multiple sources may produce the same data within the surroundings of a WSN. It will be further responsible to produce redundant data. This redundancy is taken care by the routing protocols to conserve the energy and bandwidth employment.

• 4. Resource Management: Motes are highly resource restrained in the terms of communicational power, battery, processing and storage capacity, so the available resources should be managed appropriately.

2.3 Classification Based on Number of Recipients

• 1. Unicast: In the unicast, number of sender and receiver is strictly one each. Unicast is preferably simple: consider a network graph, assign the load to each edge which is the energy consumption for that link and apply any shortest path algorithm to compute the minimum cost of the network. Unicast is sub-classified into single path unicast and multi-path unicast.

• 2. Multicast and Broadcast: In the broadcast operation, the information is collected and forwarded to all the nodes in network. This operation is so frequent in WSNs that the basic nature of WSN is assumed to be broadcast and unicast is application-oriented. When some data are distributed to a given subgroup of the nodes of the particular network, it is known as multicast.

3 Data-Centric Protocol

In a giant sensing element network, it is not possible to assign global identifiers to every node and in conjunction with random preparation makes it onerous to pick a selected set of sensing element nodes to be examined. This initiates to adopt different approaches from traditional routing, in which the route is managed in addressable nodes.

In data-centric routing, the sink sends the query to the network and waits for the perceived information from the nodes from its proximity. Attribution-based naming is needed to particularize the characteristics of data.

3.1 Flooding

Both play an important role in the design of communication protocols in various kinds of networks, to transmit the data without routing algorithm and topological control. The gossiping problem can be defined as: in a set of numerous individuals, all have an item of information to gossip that they want to forward to everyone else. Communication is generally done in a set of rounds, and in each round, an individual may communicate to at most one other node. The communication can be represented as a graph, where each edge shows the link between pairs of nodes one at each round.

3.2 Gossiping

The broadcast or flooding problem can be defined as: one individual node has to convey an item of information to every other individual node in the network. Total number of communication rounds and links between the sensors are two basic parameters, which are used to evaluate the algorithms for broadcasting or flooding problem. However, it is very easy to implement, and it has some serious drawbacks: implosion, overlap and resource blindness [1].

3.3 SPIN

Sensor Protocols for Information via Negotiation (SPIN) [2] is a family of accommodative protocols that with efficiency distributes data among the nodes in energy-efficient approach in wireless detector network. The efficient propagation of the information through individual node to neighboring sensors of the network is observed, and each and every sensor is treated as potential sink nodes. This approach has two benefits incomplete. First, it gives numerous replicating views of the network to improve the fault tolerance and, second, spread critical information to all the nodes.

A conventional protocol, classical flooding is compared and analyzed as the base of this approach. Five different protocols are evaluated by simulation for efficient information dissemination, but two among them are experimental protocols: SPIN-1 and SPIN-2. SPIN-1 employs arrangements to resolve the problem of inadequacy and overlap. SPIN-2 utilizes a threshold-based resource-aware mechanism with negotiation to solve the problem of resource blindness.

The basic plan is to call the information by victimization of high-level descriptor or metadata. However, SPIN does not specify a format for metadata. So as to conserve the energy, detector applications communicate with one another regarding the information that is sent or about to send. Sending the data is expensive but not the data about the data. Second, node must monitor the change to their energy resource. Metadata eliminates the possibility of redundant data by allowing the node to place interest of particular portion of data. The data will be sent only when it is required and reduces waste of energy in useless transmissions.

There are three messages defined in SPIN: ADV: to advertise the particular metadata, REQ: to request the specific data and DATA: to carry the actual data. SPIN is an application-based approach.

3.3.1 SPIN-1

It is a simple handshaking protocol for a lossless network. The protocol starts when new data is obtained by any node. The node sends ADV message to its neighboring nodes. After receiving the ADV, neighboring node checks that it is requested or already received. If not received, then it will send a REQ message back to the sender and get DATA in response. The main drawback of this protocol is that it is designed for lossless networks only.

3.3.2 SPIN-2

The SPIN-2 protocol is similar to SPIN-1 with addition to a low-energy threshold. Whenever the energy is leading to the minimum energy bound, it remodels to reduce its contribution to the network activities.

3.4 Directed Diffusion

Directed diffusion [3] is an application-aware data-centric approach in which the communication is performed on the basis of named data. By choosing a decent ways and caching and process knowledge inside the network, it ends up in delivering the goods energy conservation. Attribute–value pair is used to name the data. A list of attribute–values pairs describe a task, and these task descriptors are named in this approach. A sensing task is broadcasted all over the network as an interest by a node called a sink. The sink used to broadcast the interest message to the network, periodically. The interest is periodically refreshed by the sink. An interest table is organized and maintained by every node, which has each distinct entry.

When an interest is received by a node, then it checks either the interest is already present or not. If not present, then an entry is created for the interest and a single gradient toward the particular neighboring node is also added. When the gradient is timed out, the interest entry would be removed. After receiving a fresh interest, the node may broadcast the same interest to other neighboring nodes also. A gradient specifies a data rate and a direction of the send event. The interest flew in such a manner to facilitate the data toward the sink node. The data packet is unicasted to the relevant node or neighboring node only. A matched cache entry is dropped eventually.

Directed diffusion has numerous characteristics like no router required, no global identifiers required and reactive routing.

3.5 Gradient-Based Routing

The Gradient-Based Routing (GBR) is a variation of the directed diffusion (DD) convention. It is a question-based steering convention in which information is assembled and sent to the base station by sensors or a gathering of sensors, in a response of a query, generated and broadcasted by a sink node. The query is circulated in the form of interest message, which contains description of the task, from a sink node.

There are two approaches which are proposed to, first, aggregate packet stream in a vigorous way, to minimize the energy dissipation by a number and, second, to get better resource utilization in order to achieve longer lifetime for sensor network. Like SPIN, when new node is entered in the sensor network, it announces the type of interest by broadcasting, and a gradient will be generated at each sensor. The gradient indicates the integrity of the nodes which are few hops away and used in packet transmission. The height of node is calculated by minimum number to the interest. The difference between the height of the node and the height of neighboring node is known as gradient. The packet will be sent on the link which has the largest gradient. Each node processed their data before forwarding to the next hop. The concept of Data Combining Entity (DCE) is introduced for the node which have multiple streams, flowing through them. It compacts the data into one unit for transmission.

3.6 Energy-Aware Routing

The key concern of the protocol, energy-aware routing [4] is, always considering most minimal vitality path may not be ideal for the system lifetime and long haul network viewpoint. For optimizing such measures, sub-optimal paths may be established for substantial gain. By analyzing few existing energy optimal protocol lead to discover the optimal path, burn a lot of energy along with these paths and leave the path with huge disparity in energy level and eventually few nodes die; and disconnect the network. The protocol did not search for the single optimal favorable path. Rather a set of sub-optimal paths is discovered, and one path is chosen in probabilistic way.

The primary idea of the protocol is to improve the lifespan of the network that may lead to use sub-optimal paths sometimes and ensures that it does not reduce the performance of the network. None of the paths used all the time in order to maximize sustainability of the network and instead of that use different paths continuously. The protocol is a reactive type of routing protocol, hence destination initiated. It is similar to directed diffusion and compares the performance with the protocol.

The protocol works in three phases:

• 1. Setup Phase or Interest Propagation: Destination initiates the connection by flooding the request, and cost is initialized to zero. Every intermediate node forwards the request, and cost would be added to the previous cost. At the destination, path with high cost is discarded and low-cost paths are added to forwarding table. An average cost is calculated for each node.

• 2. Data Communication Phase: The source and intermediate routers forward the information to the neighbors in forwarding table with the neighbor’s likelihood equivalent to the normal likelihood of the node’s forwarding table. The information sent till the destination.

• 3. Route Maintenance Phase: The restricted interest flooding performed sometimes, and subsequently, course support is low.

The simulated results show that energy-aware routing reduces the energy consumption at each node and has an improvement of 21.5% in performance.

3.7 Rumor Routing

Rumor routing [5] is a method to describe and analyze the routing queries of the sensor nodes that are continuously observing a particular event and retrieve the data. In more appropriate description, rumor routing is a legitimate trade-off between flooding inquiries and flooding event notifications.

The idea is to establish a path toward the event, whereas the event flooded by broadcasting. At whatever point a query is produced, it can continue to an arbitrary path till the event way is found, rather than communicating the question all through the system. As the query finds the event path, the event straightforwardly courses to the event. In the event that the path is not found, then the query either re-submitted or flooded it. In various tested conditions, an extremely high delivery rate is achieved. The rumor routing is an algorithm to occupy the space between algorithms called query flooding and event flooding. When no prior information about the vicinity is available, then the query is flooded to the entire network, which is known as query flooding. When a sensor encounters an event, it flooded it to the network.

The rumor routing can be described as: (1) Each node keeps a list of neighboring nodes and event table. (2) When a node encounters an event, it will add it into event table with zero distance. (3) An agent is a packet with extended lifetime, transmitting the information about the local event to the distant nodes. (4) All the nodes are capable to generate the query and routed to the particular event. (5) If the query is somehow not able to reach the destination, then the query is either re-submitted or flooded to all the network.

The rumor routing protocol provides an efficient and powerful algorithm to deliver the queries to the particular events in numerous conditions in a large network.

3.8 CADR

The idea of constrained anisotropic diffusion routing (CADR) [6] is a part of two techniques that work together, named information-driven sensor querying (IDSQ), for making data querying and routing more energy efficient. The principle is to introduce a mechanism to select a sensor to query and process the data routing, augment data gain, limit discovery idleness and limit the energy utilization by tasks as localization and tracking.

It utilizes the general type of data utility that determines the data content and spatial configuration of the network to formulate how each node estimates the cost details, comes to any decision, updates belief status and routes the data based on various decisions. CADR is a generalized form of directed diffusion routing. The sensors are activated once the particular interest event is announced, and only for the part of the network, that seeks the information.

To formulate the problem, sensing observation model is designed for nonlinear relations between the sensor nodes, types, position, noise and other parameters and measures the uncertainty. Then, consider the sensor node selection by updating the belief by incorporating based on previously not considered nodes. After that characterize the measure for data utility, for example, co-difference based, Fischer data grid, entropy of estimation vulnerability, volume of high likelihood area and sensor geometry-based measures. Then, a composite objective function is derived to calculate transmission cost of the network and current belief. All the routing decisions are based on local computation on each node to achieve the estimated belief status.

3.9 COUGAR

COUGAR [7] uses the idea of declarative query, especially designed for sensor networks, to abstract the query processing from other network layer functionalities, by additional query layer. So as to diminish asset energy and, subsequently, increment the lifetime of the sensor, a query optimizer is utilized to structure a proficient inquiry plan. General existing networks collect and transfer the data when they are online and aggregate and store for offline querying and analysis. It also proposed a loosely coupled distributed architecture to support data aggregate and complex computations.

A query optimizer is also situated on the gateway node to design a plan for the processing of distributed query whenever it receives the query. The query plan architects the flow of data between the nodes and specifies the computation at each node. The plan is broadcasted to all the sensor nodes in the network. At query execution time, data record is sent back to the gateway node.

The protocol works in various phases: (a) data aggregation, (b) selection of query language, (c) optimizing the query, (d) catalog management and (e) optimizing the multi-query.

3.10 ACQUIRE

ACtive QUery forwarding In sensoR nEtwork (ACQUIRE) [8] considers the system as circulated database and works with complex inquiries which are additionally partitioned into sub-queries. The standard behind ACQUIRE is to infuse a functioning query bundle that finishes a path of the system. At each progression, the node, which gets the dynamic query plays out an activated, on-request, redesign getting data from every one of the neighbors within the scope of countable hops.

As this dynamic query advances through the system, it gets progressively separated into littler segments till it is totally comprehended and returned back to the underlying query creating node with a total outcome. The basic concept is based on test and validation of data query, but, on the other hand, a mathematical approach is also proposed to derive analytic expressions for the energy cost of complete ACQUIRE protocol. The efficiency of ACQUIRE can be enhanced if the surrounding nodes of the active nodes in the query path have the minimum intersection and additional topological or geographical information which helps to perform the task.

In this mechanism, the query is forwarded to the nodes in the network by the sink and each node, which gets the query, attempts to process the query completely or incompletely by utilizing pre-reserved data and forwards to the following sensor node.

4 Self-organizing

In WSNs, various simple components demonstrate the behavior of the whole network and represent more arranged than the behavior of individual component. Subramanian and Katz [9] proposed a collective architecture for specific sub-class of sensor applications, named self-configurable system, for large number of sensor to coordinate themselves to complete a sensing task. The main goal of the algorithm is to minimize energy consumption, localizing operations, fault tolerance for node and link failure. The network applications can be classified based on size of the system, numbers of sensors used, distance between the nodes from wired component and allocation of sensor nodes.

There are few assumptions built for generic architecture of self-configurable system, such as nodes should be heterogeneous, data delivery and data dissemination are two different and orthogonal components, resource constraints and infrastructure requirements are application-specific, and data discovery nodes are mobile, whereas data dissemination nodes are stationary. However, in the presence of heterogeneous node, all nodes should be treated the same and have similar functionalities.

The architecture supports both data-centric and non-data-centric approaches. Reduction of state and localized operations, energy efficiency, reliable paths, hierarchical routing paths, fault tolerance using broadcasting tree, and reduction of the number of dynamic cost updates are few contributions of the algorithm.

4.1 Architecture

In the architecture, the nodes are assumed to be stationary. Various architectural components are classified such as specialized nodes to monitor and track; router nodes for information dissemination and strictly stationary; aggregator nodes to collect and aggregate sensor readings and sink node for high capacity of information storage. Numerous infrastructures are also described like addressing infrastructure; however, individual node does not need any addressing technique but unique MAC address can be used if necessary, routing infrastructure to establish the links between adjacent router nodes, and broadcasting and multicasting infrastructure.

4.2 Algorithm

The self-organizing algorithm can be explained as:

• 1. Discovery Phase: Discovers set of neighboring nodes and fixing the maximum radius of data transmission.

• 2. Organizational Phase: Numerous operations are performed like nodes form the groups and balance the hierarchy, and node’s position in hierarchy, routing table is computed by O(log n), and broadcasting trees are constructed.

• 3. Maintenance Phase: Monitoring, constant updation of routing table, details of neighboring nodes, and fault tolerance are performed in maintenance phase.

• 4. Self-Reorganization Phase: As changes occur in topology, node failure, group partitioning or routing table updation, self-reorganization is performed for remedial task and maintains the hierarchy.

4.3 Analysis

There is a list of advantages of self-organization like hierarchy is balanced, routing state is maintained by just O(log n), node failure and link failure can be tolerated by Local Markov Loops, broadcasting graphs using directed acyclic graph in a unique manner and attachment to specialized node makes the node mobile. However, there are few disadvantages also such as no on-demand organization, hierarchical operation increases the probability of reorganization and the last but the most important, no address is attached for communication from one node to another.

5 Hierarchical Protocols

In a single-tier network, the overhead increases with the sensor density. Hierarchical routing is proposed to productively keep up the energy utilization by including the idea of multi-hop correspondence in the scope of specific group.

5.1 LEACH

Low Energy Adaptive Clustering Hierarchy (LEACH) [10] is a self-organized, adaptive clustering protocol in which the distribution of energy load is even among all the sensor nodes. In LEACH organization, the nodes arranged themselves in a local cluster and one node is designated as local base station or cluster head. Cluster head is chosen in rotational basis, because fix cluster head like conventional clustering algorithm leads to drain one node quickly; hence, energy drainage is monochromatic all over the network.

Local data fusion is applied to the data, sent from cluster to base station, in order to minimize the energy consumption. Each node chooses the cluster head which is close in vicinity; hence, minimum communication energy will be required. Once all the nodes are arranged in cluster-based organization, a schedule is prepared for the node in a particular cluster, to turn off all the non-cluster head node at the time of transmission. Collected data are aggregated at cluster head and transmitted to the base station. The node with maximum energy remaining is chosen to be cluster head, so that distant base station transmissions can be easily performed.

The operation of LEACH is first divided into rounds, and these rounds are further divided into various phases.

• 1. Advertisement Phase: The node that elected itself as a cluster head advertises itself by broadcasting a message to rest of the nodes.

• 2. Cluster Setup Phase: Once cluster head is selected, the nodes have to choose their belonging to the cluster and inform the cluster head about their membership.

• 3. Schedule Creation: The cluster head creates a TDMA schedule for the node to transmit.

• 4. Data Transmission.

The main advantage of LEACH is completely distributed and requires no control information from the base station, and the node does not need any prior information of the global network.

5.2 PEGASIS

Power-Efficient GAthering in Sensor Information System [11] (PEGASIS) is a near-optimal chain-based protocol and built on the top of LEACH. The fundamental thought for PEGASIS is to shape a chain of sensors so that every node can transmit and get from the nearby neighbors as it were. Gathered data forward starting with one sensor then ont the next and get intertwined, and at last, a chosen node transmits it to the base station.

Nodes take turn in rotation basis, to transmit the data to base station, in order to reduce the average energy consumption at each node per round. Intractable problem like traveling salesman problem has resemblance to build a chain to minimize the total length, hence adopts greedy approach. In the case of no node in transmission range or no node left out, multi-hop organization can be used. In any case, the node died at random place, a simple control token passing approach is actuated to start the data transmission from the end of the chain. Local gathering and small amount of data received by the leader are two prime improvements of PEGASIS over LEACH to save energy for certain levels.

5.3 Hierarchical PEGASIS

Hierarchical PEGASIS [12] is an extension of PEGASIS. It evaluated the data gathering problem, in the case, where data is gathered in each round and combined with other nodes’ data, encapsulated in one unit and forwarded to the farther base station. On the off chance that information is sent over unit delay and transmitted straightforwardly to the base station, at that point both energy utilization and postponement would be high. The thought is to build up an information-gathering component that equalizes the vitality and defer cost, as measured by energy * delay. A chained-based binary scheme is best suited with CDMA capable nodes in terms of energy * delay. On account of without CDMA fit nodes, parallel interchanges are conceivable just among spatially isolated nodes and a chain-based 3 level progressive system plot fits best for the plan.

5.4 TEEN

Threshold-sensitive Energy Efficient sensor Network (TEEN) [13] is an energy-efficient protocol for active network and evaluated on simple temperature sensing application. In this approach, the network is classified on the basis of their mode of functioning and the type of target application, as proactive network and reactive network. In proactive, the network is switched on the sensor and transmitter, periodically, senses the environment and transmits the sense information. Whereas, in reactive, the node reacts to the changes based on sensed attributes. The model uses a hierarchical clustering approach.

All the nodes transmit the data to their immediate cluster head only, to conserve the energy, and the cluster head is intended to perform additional computations. Cluster head would be changed periodically, based on the battery left. The cluster head broadcasts the parameters, which are report time and attributes of network. Report time is the time to sense the information and transmit the data. Time-critical data reaches the node without any time lost. Soft threshold may vary, but smaller soft threshold value shows a broader image of the whole network. Whenever cluster changes time, the attributes broadcast again. The main drawback of this scheme is if the thresholds are not reached, the nodes will never communicate, and the whole network dies without any transmission. Hence, it is not suitable for the applications where the data is required at regular basis.

5.5 APTEEN

Adaptive Periodic Threshold-sensitive Energy Efficient sensor Network (APTEEN) [14] is a hybrid routing protocol which is designed for extensive information retrieval. Like LEACH and TEEN, APTEEN also chooses a cluster head (CH), and once the CHs are decided, in each cluster report time, the cluster head first broadcasts the parameters, such as attributes, threshold (soft and hard threshold), schedule and count time (T_c). TDMA is introduced to avoid the collisions between the data packets. Time-critical situations are also arising in the network due to various changes. The protocol is able to handle three types of queries: historical query, one-time query and persistent query. These queries collect the data on periodic base with hard threshold. The main drawback of this scheme is additional complexity of thresholds and time counts. APTEEN is an extension for WSN with uneven node distribution.

6 Location-Based Protocols

Location is the prime concern in WSN when the distance between two nodes is to be calculated so that the energy dissipation can be calculated. On account of no tending to conspire, area data can be utilized in steering in energy proficient way.

6.1 SPEED

SPEED [15] is a real-time, stateless, localized algorithm with minimal control overhead communication protocol. Location information with data makes location-based routing more meaningful for decision making. Unlike other location-aware protocols, SPEED is able to handle congestion control with soft real-time communication service. MAC layer and network layer adaption are used to deal with such issues. SPEED works to achieve a soft real-time communication service on a certain delivery rate and the delay between the end nodes is proportional to the distance between them. Few design objectives are mentioned to be satisfied by SPEED are architecture should be stateless, soft real-time, minimal support by MAC layer, congestion management, traffic and load balancing, localized behavior, ineffective path avoidance and no routing table only location information.

SPEED achieves a desired delivery speed throughout the network by diverting the traffic and regulating the packets locally. SPEED contains various components like application API, packet format, neighboring beacon exchange mechanism, estimated the delay, stateless non-deterministic geographic forwarding, neighborhood feedback loop, back-pressure re-routing and the last mile process. SPEED utilizes non-deterministic sending to accomplish balance in energy utilization. It actualized on Berkeley motes platform whose code size is 6036 bytes.

6.2 MECN

Minimum Energy Communication Network (MECN) [16] is a convention for disseminated position-based system to improve the base energy utilization in versatile remote system for distributed correspondences. To accomplish such correspondence, the system must be firmly associated. The most widely recognized channel model utilized for RF frameworks and have different parts like way misfortune, enormous scale varieties and little scale varieties. Maximum ratio combining is the method used to join these streams ideally. In the path-loss model, the statures of antenna of mobile ought to be comparative.

In order to establish a strongly connected network, each node keeps communication links to every other node. By using a relay node, minimize the total energy consumption between sender and receiver nodes. The key plan to the protocol has to consider every one of the nodes of the system to locate the worldwide energy proficient way to the ace site by every sensor. By local search, it considered only few potential links in the relay region. The protocol works in two phases: (1) Search for Enclosure: To discover a enclosure graph, neighboring node and enclosures are searched by every node and no loops are considered in graph. (2) Cost Distribution: It finds the optimal links with minimum power dissipation in the enclosure graph. The relay region registered for a solitary node by accepting the two-ray proliferation model for area correspondence. This is applicable for only mobile ad hoc network, because the topology is discovered by local search performed on neighborhood of each node.

6.3 SMECN

Based on the minimum energy property, here present the characteristics to establish a protocol named Small Minimum Energy Communication Network (SMECN) [17] on the top of MECN protocol. A sub-network is constructed by SMECN and proved that the broadcast would be reached to all the nodes in a circular region, if happened at given power setting, is smaller than MECN. The key idea to minimize the energy consumption is to construct a subgraph G’ of original network graph G such that

• G’ consists of all the nodes of G with fewer (necessary) edges.

• If two nodes are connected in G, then it must be connected in G’.

• Each node in G’ can transmit to all neighboring node by consuming less energy than G.

The idea is to propose an algorithm to construct a communication network which contains G min rather construct G_min itself. To find the routes for message sending, it adopts AODV approach.

6.4 GAF

Geographic Adaptive Fidelity [18] protocol is introduced to minimize energy consumption in wireless ad hoc network by discovering route equivalent sensor node and turned off unwanted node in order to maintain routing fidelity. For this purpose, the sink and source node are remained constant and intermediate nodes are examined and used for balancing the energy consumption. Adaptive fidelity is a technique to increase the lifetime of self-configured system by eliminating the redundancy.

An algorithm introduced for GAF is as follows:

• Determining Node Equivalence: The concept of virtual grid is introduced so that each GAF node can associate with it by using its location information and all the node from the same square of the grid are equivalent.

• GAF State Transitions: Nodes are designed to be in one of the three states: sleeping, discovery and active. The node is initially in discover state, till the timer fired, and then node broadcasts the message and enters in active state for a time stamp. A node can change the state to sleeping when equivalent node will handle routing.

• Tuning GAF: The value of various parameters including estimated node active time (ENAT), discovery message interval (T d), active time duration (T a), node ranking and sleeping duration (T a) is application-specific in GAF.

• Load Balancing Energy Usage: GAF introduces a load balancing strategy to reduce energy uses so that all the nodes remain on and work together for longer lifetime.

• Adapt to Higher Mobility: GAF tries to maintain a constant level of nodes to participate in data routing, but high mobility increases the packet drop rate. Hence, GAF classified the simulation in GAF-basic and GAF-mobility adaption.

• GAF can run with any ad hoc routing protocols and decision of turning on and off for the nodes is completely independent.

The overhead generated by GAF discovery message is small and not affects the energy consumption too much. GAF may affect the data delivery by losing the packet when sleep mode is on and route is changed.

6.5 GPSR

Greedy Perimeter Stateless Routing (GPRS) [19] is a protocol introduced for wireless datagram networks, which forward the data by using position of the router and destination, and a greedy strategy is to adapt for immediate nodes in the network topology. In the case of frequent topology change, GPSR uses local topology information to establish accurate new route quickly.

The prime factors to build a routing algorithm are rate of change in topology and number of routers used. Hierarchy and caching are two promising approaches for scaling ad hoc routing. The algorithm is divided into two approaches for packet forwarding: greedy forwarding, in which a greedy choice is obtained in choosing the next hop with local optima, perimeter forwarding, used where greedy forwarding cannot be applied.

A simple beaconing algorithm yields the position of the neighboring node position of all the existing nodes of the network by broadcasting MAC address, identifiers and position in the form of a beacon by every node. When the node is failed to receive any beacon from neighbor node, node assumes that the node is out of range or die and deletes it from routing table. In perimeter forwarding, the next edge to be traverse is the one in counterclockwise to the edge. In the shortage of no crossing heuristic, the idea of planer graph is introduced. If a neighbor is closer to the destination, the packet is forwarded to next hop, else packet is marked as perimeter mode and use a simple planer graph traversal.

For protocol implementation, GPSR has to make more robust on a mobile IEEE 802.11 network, by adequate choice of implementation like reinforcement in the case of MAC layer failure, interface for query traversal, efficient use of network interface and planarized the graph. GPSR is proficient to utilize geographic parameter to achieve small per node routing state, less message complexity and robust data delivery in dense wireless network.

6.6 GEAR

Geographic and Energy Aware Routing (GEAR) [20] evaluates an energy-efficient routing protocol to broadcast a query to the particular region of the network without flooding. Neighboring node is chosen in an energy-efficient way to route the packet in target region and uses restricted flooding inside destination region to reduce duplicate forwarding. GEAR is simulated for both uniform and non-uniform traffic and compared to the performance of GPSR.

The packet forwarding process comprises two phases to forward packet to all the nodes in target region. First, forwarding toward the target region. If the node is closer, neighbor to the destination sends to next hop, else sends to next hop with minimized cost. Second, diffuse the packet within the target region by recursive geographic forwarding. For that, the targeted region should be specified, node’s remaining energy must be known and link should be bi-directional. The energy-aware neighbor is computed for closer and farther away nodes. In recursive geographic forwarding, the recursive splitting and forwarding are followed till the pre-conditions are not fulfilled. The energy-aware metric for cost estimation is used to balance energy consumption and achieve energy efficiency for the network. As the simulated result, it shows that GEAR delivers 70–80% more data packets than GPSR.

7 Network Flow and QoS-Aware Protocols

This is not somehow the routing protocol by intended nature, but when the route is modeled in such a way to solve network flow problem. QoS protocols look after the end-to-end delay while setting up the routing paths. There are variety of protocols in this section: Maximum lifetime energy protocol [21], maximum lifetime data gathering [22], minimum cost forwarding [23], sequential assignment routing [24] and energy-aware QoS routing protocols [25] are some examples.

7.1 Maximum Lifetime Energy Routing

Maximum Lifetime Energy Routing [21] is basically a data-centric routing, but it provides a certain level of QoS, hence considered in this category. The basic idea is that the system lifetime can be significantly extended by using a link metric that utilizes the information about the residual energy of the sensor nodes and the energy expenditure in the transmission of a unit of information over the wireless link. The approach is further divided into two modules or sub-problems, called the maximum lifetime problem and the maximum residual energy path routing algorithm. Maximum lifetime problem can be described as sensor and can only generate sense packets in detection time only and forward it to one of the gateway nodes. The objective is to amplify the time until the first failure of the packet conveyance because of battery waste. The idea behind maximum residual energy path routing is to route packets through paths with maximum energy remaining so that total energy consumption in all the paths will be balanced. Some of the link metrics and methods of shortest path calculation are compared in simulation part.

7.2 Energy and QoS-Aware Routing

An energy-aware QoS routing protocol is proposed for sensor systems for the transmission of imaging information, so as to boost the effectiveness of the sensor and strong methodology for data gathering. The convention acquires a least-cost, delay-compelled way for continuous applications like picture, as far as cost of connection, transmission energy, error rate, battery left and different parameters. Throughput for non-ongoing information can be augmented by administration rate modifications.

The greater part of the QoS put together routing algorithm are based with respect to the idea of portability of the node, yet energy efficient, with QoS parameters are not considered by any means, subsequently, challenges presented by imaging sensors and constant applications are not assessed. The possibility of energy-aware QoS routing is to find an ideal way to the door with less energy and error rate, by taking start to finish postpone necessities in representing continuous information. QoS routing problem is similar to path constrained path optimization (PCPO) problem, which is an NP-complete problem.

A ratio is used to derive the bandwidth for real-time and non-real-time traffic for outgoing link, and this ratio is set by the gateway. There are two different mechanisms, for setting the service rate on each node, named single-r and multi-r. In single-r mechanism, one r value is assigned for each node all over the network. But in multi-r mechanism, the sensor nodes have to calculate their own r value based on the information broadcast by the gateway. The multi-r value provides better end-to-end delay, increases throughput, extends queuing delay and increases average delay per non-real packets with a slight increase in energy consumption.

7.3 Maximum Lifetime Data Gathering and Aggregation

The protocol is interested to find an efficient way to collect the data from all the sensor nodes and transmit to base station, in order to maximize the system lifetime. The protocol mainly focuses on the performance objective of interest to maximize the lifetime of system instead of trying to minimize the energy consumption. The maximum lifetime data gathering problem is sub-divided into two baselines: sensors are capable to perform in-network aggregation of data; and aggregated data are not being aggregated by other nodes.

The data gathering problem considers two sub-classes as data gathering with aggregation and without aggregation. Each sensor generates one data packet of size n bits in a particular time stamp, named round, and transmits it to the base station. All the information from all the sensors in one round, gathered and transmitted to the base station. A data gathering schedule S is specified to achieve maximum lifetime T for the system.

Data gathering can be achieved by aggregation and without aggregation. In data gathering with aggregation, the data is aggregated by in-network to a data fusion packet to reduce the number and size of the communication and make it energy efficient. The problem in with aggregation is known as Maximum Lifetime Data Gathering (MLDA) and solved by finding a near-optimal admissible flow network and constructing a schedule for that. For without gathering, the problem is known as Maximum Lifetime Data Routing (MLDR) problem. A near-optimal solution can be obtained by MLDR problem, solves a linear relaxation for defined integer problem and computes a solution for the same. In the case of data gathering without aggregation, schedule generated for MLDR is able to achieve better lifetime than existing protocol.

8 Conclusion

In this paper, we have outlined recent research in the field of routing in wireless sensor network, which falls into five categories mentioned above. The prime concern of these protocols is energy efficiency and making sure of participating of each node in the process of data gathering and transmission. In future, the traditional routing method variants can be used in energy-efficient way for wireless sensor network, with less communicational and computational overhead.