Energy Aware Routing Paper

Protocol for reliable transmission and To maximize the network life time in WSN 

Abstract:

The energy constraint sensor nodes in sensors networks operate on limited batteries, so it is a very important issue to use energy efficiently and reduce power consumption. Many routing protocols have been proposed among these protocols, the adaptive routing protocols are very attractive because they have low routing overhead. As a result, the routes tend to have the shortest hop count and contain weak links, which usually provide low performance and are susceptible to breaks. In this paper we introduce an adaptive routing protocol called energy aware routing that is intended to provide a reliable transmission environment with low energy consumption. This protocol efficiently utilizes the energy availability and the received signal strength of the nodes to identify the best possible route to the destination.

1. Introduction:

A wireless sensor network consists of light-weight, low power, small size of sensor nodes. The areas of applications of sensor networks vary from military, civil, healthcare, and environmental to commercial. Examples of application include forest fire detection, inventory control, energy management, surveillance and reconnaissance, and so on. Due to the low-cost of these nodes, the deployment can be in order of magnitude of thousands to million nodes. The nodes can be deployed either in random fashion or a pre-engineered way. The sensor nodes perform desired measurements, process the measured data and transmit it to a base station, commonly referred to as the sink node, over a wireless channel. The base station collects data from all the nodes, and analyzes this data to draw conclusions about the activity in the area of interest. Sinks can act as gateways to other networks, as a powerful data processor or as access points for human interface. They are often used to disseminate control information or to extract data from the network.

Nodes in sensor networks have restricted storage, computational and energy resources; these restrictions place a limit on the types of deployable routing mechanisms. Additionally, ad hoc routing protocols, for conventional wireless networks support IP style addressing of sources and destinations. They also use intermediate nodes to support end-to-end communication between arbitrary nodes in the network. It is possible for any-to-any communication to be relevant in a sensor network; however this approach may be unsuitable as it could generate unwanted traffic in the network, thus resulting in extra usage of already limited node resources. Many-to- one communication paradigm is widely used in regard to sensor networks since sensor nodes send their data to a common sink for processing. This many-to-one paradigm also results in non-uniform energy drainage in the network. Sensor networks can be divided in two classes as event driven and continuous dissemination networks according to the periodicity of communication. In event-driven networks, data is sent whenever an event occurs. In continuous dissemination networks, every node periodically sends data to the sink. Routing protocols are usually implemented to support one class of network, in order to increase energy savings. In continuous dissemination networks, routes will be periodically reconstructed, while in event-driven networks routes will be constructed only when an events occurs, since the cost of constant updates is prohibitive in this scenario.

 In this paper, we present a new event driven routing protocol to prolong the life time of the network. This protocol uses the metrics received signal strength and the available energy to identify an energy efficient path that minimizes packet collisions and increases the network lifetime. Simulation results show that energy aware routing outperforms the traditional routing approaches in terms of network lifetime and packet delivery ratio. The remainder of the paper is organized as follows. Section II provides a brief overview of the related work. Section III explains the operation of energy aware routing. Section IV compares the performance of energy aware routing and the protocols used in traditional schemes. Section V provides the conclusion of the work and discusses future directions.

2. Related Work:

Sensor networks introduce new challenges that need to be dealt with as a result of their special characteristics. Their new requirements need optimized solutions at all layers of the protocol stack in an attempt to optimize the use of their scarce resources. In particular, the routing problem, has received a great deal of interest from the research community with a great number of proposals being made. The proposed protocols often resort to the use of artifacts such as data aggregation, nodes clustering and location information. The majority of these routing protocols can be classified in basically four main classes based on: Data centric, hierarchical, location-based, network flow and QoS awareness. Data centric algorithms are based on the use of network queries where the collected data is named to allow the nodes to search and get only the desired information. This technique is used to avoid the transmission of redundant data in the network and hence saves the network unnecessary work and energy. Two of the main algorithms are Directed Diffusion (that each node disseminate the data interested in receive) and SPIN (meta-data information are transmitted between the nodes to identify the nodes to whom to send the collected data). Hierarchical algorithms separate the nodes in sub-regions called clusters in order to segregate the areas of the monitoring environment as LEACH, PEGASIS and TEEN. To allow communication between the clusters a leader is selected from each cluster (cluster-heads). Leaders are then responsible for the management (data aggregation, queries dispatch) and transmission of the collected data in the region they control. Location-based algorithms (i.e. GAF and GEAR) rely on the use of nodes position information to find and forward data towards a destination in a specific network region. Position information is usually obtained from GPS (Global Positioning System) equipment. Finally, network flow and QoS awareness algorithms uses network traffic models and apply QoS based mechanisms to support their routing requirements as SAR or SPEED. The energy efficient route allocation is found in few works and in the majority, it does not evaluate in the sensor networks context, but analyses the scenarios where these kind of mechanisms are applied in Ad-hoc networks, which does not reflect the same conditions because of the great differences between the resource restrictions of the equipments of each type of network.

3. Energy Aware Routing

We consider a network of static (e.g. immobile) energy constrained sensors that are deployed over a flat region with each node knowing its own location. Assume that all nodes in the network are assigned with a unique ID and all nodes are participating in the network and forward the given data. Additionally, these sensor nodes have limited processing power, storage and energy, while the sink nodes have powerful resources to perform any tasks or communicate with the sensor nodes. To allow an increase in the network lifetime additional mechanisms are done in routing protocols to verify other parameters beyond the hop count that accept a more intelligent route establishment. The energy efficient routing algorithm proposed is used for making a decision on which neighbor a sensor node should forward the data message to. A node is selected to forward the data based on its residual energy level and signal strength. Ideally, the greater the energy in the node and farther the node from the previous one, is the more likely to be selected as the next hop. The nodes which are not selected in this process will move to the sleep state in order to conserve power. The communication is assumed to be bidirectional and symmetric. The protocol replies with a complete route from the source node to the sink quickly, and prepares many route paths to balance the energy of each node. It also enables intermediate nodes to aggregate all the received packets during a short period time and transmit only one aggregated packet to the following node.

3.1 Network Setup and Path Discovery

The algorithm is composed of three phases: Neighbor Discovery, Route Reply and Reliable Transmission by using two messages namely broadcast message and route reply message. When the sink node receives an interest the node launches a neighbor discovery mechanism. A broadcast packet is flooded through the entire network until it reaches the source node. After the source node is reached it transmits a reply back through the ultimate neighbor through which it received the request.

3.2 Messages

• Broadcast Message

This message is transmitted when a node enters in the network to execute the neighbor discovery process during the network startup and also to establish a route to the destination.

• Route Reply

It is generated when the given source node is reached and to create a new entry in the local neighbor table.

3.3 Algorithm Phases

Three phases are responsible for data forwarding in the network.

3.3.1 Neighbor Discovery

Before sending the data to the sink, a node must start the neighbor discovery process to create a neighbor list that is the address of all nodes that are able to transmit data to from the source. During this process broadcast messages are exchanged between the nodes. The broadcast message as shown in Figure 1 consists of the source address, hop count, sequence number to distinguish the messages originating from the same source, required energy threshold to transmit the packets and required signal strength threshold and destination address.

                                                Figure 1: Broadcast message frame format

Unlike other energy-aware routing protocols, which attempt to find a minimum-energy-cost path, this protocol provides an energy-sufficient path instead. A special flooding mechanism is adopted in the neighbor discovery. The solution is to combine the broadcasting speed with the available energy on intermediate nodes. When an intermediate node receives the broadcast message, it does not broadcast the message to its neighbors immediately. Before sending the message out, several things are done. The intermediate node first checks its available energy. If the available energy is less than operation energy (e.g., twice the packet transmission energy), that indicates that the node has no more energy to take more transmission jobs, the node simply discards the received request. If the node has sufficient energy, the node measures the strength of the received signal. In general, the farther is the receiving node is from the sending node, the weaker the signal is. This is true for large-scale wireless propagation models such as the free space and two ray models. In small-scale propagation models such as the Rayleigh model and in practice, the signal strength may vary dramatically at the given radius for different directions because of obstacles. However, even in these cases, the weakening of the signal along the specific direction as the distance increases still holds. This protocol does not intend to precisely select the farthest node every time, but to choose nodes that are highly likely to be far away from the sender. Overall, this creates a more efficient flooding algorithm (reducing the number of retransmissions). If more than one node is within the same signal strength threshold and has sufficient energy level, if the broadcast messages are flooded again from two different nodes message collisions will occur. In order to overcome this, broadcast message is not rebroadcast immediately; a back-off delay scheme is applied. At the end of the current message transmission the nodes chosen to forward the message being broadcast is selected by associating with a back off timer.

Upon broadcast message reception, the receiving nodes start timers that implement broadcast back-off delay. To ensure that optimal routes are determined, each receiving node calculates its broadcast back-off delay as a function of its distance away from the destination (this delay normally decreases along with each hop). When a node’s back off timer expires, it forwards the broadcast message via a broadcast, which also sends an implicit acknowledgement (ACK) to the previous sender of this packet. If a node receives such an implicit ACK before its timer expires, it cancels its back-off timer and packet transmission. Thus, in most cases, the node with the smallest number of hops to the destination will select itself to forward the message, simultaneously making other nodes aware of its selection. The solution described above may result in more than one node selecting itself because, not all receiving nodes may be in the broadcast range of the first selected node to overhear its implicit ACK. To avoid such a possibility, upon receiving the implicit ACK, the original sending node broadcasts an explicit ACK, so that all synchronized nodes know that selection has already been made. This additional step achieves its goal under the assumption that all links of the original sending node are bidirectional. The reception of the explicit ACK marks the end of the current self-selection round. Using the above mechanisms, the path to the source is built utilizing some energy-sufficient nodes. The path request reaching the source contains one such energy-sufficient path. An energy-sufficient node is the naturally selected node among the sender’s neighbors and is usually the one with the largest available energy.

3.3.2 Route Reply

The destination node, upon receiving a new broadcast message, will reply with a route reply packet. The header of this packet contains the same fields as those of the request packet, as well as an expected hop count field indicating the expected number of hops needed for the packet to travel to reach the target node (in this case, the sink). Unlike the broadcast message, the route reply packet does not rely on flooding to find its return path back to the source, it just uses the nodes through which it received the broadcast message.

                                                    Figure 2: Network Connectivity

                                             Figure 3: Path selected in energy aware routing

As shown in Figure 2, there are many intermediate nodes, available in the network. All nodes within the radio range of the nodes receive the broadcast message at the same time. When the sink initially broadcast the message, the nodes A, E and G receive the message. Assume that the Available energy at A is larger than at E and G, and also A is within the required signal strength threshold, hence node A is selected to broadcast the message to the neighboring nodes. The process continues and node B which is selected sends out the broadcast message which is received by nodes F and C, it is found that both F and C have the same energy level and are within the required signal strength threshold. So both F and C start a back-off timer and if the back-off timer of node F ends before C an implicit acknowledgement is sent by node F which is also received by node C, and so node C stops its back-off timer as shown in Figure 3. When the broadcast message reaches the target source, the source transmits the route reply packet through the nodes it received the broadcast message.

3.3.3 Routing Table

After establishing the routes between the network nodes, they are stored in a routing table as shown in Table 1 to allow future queries for the allocated paths. The routing table stores information about the paths that can be used to direct data messages and verify the validity of each table record.

                                                             Table 1: Routing Table

3.4 Reliable Transmission

This protocol provides reliable packet delivery for uncast transmission similar to other reliable transmission protocols. Data is cached in the sender until an ACK is received from the receiver. If no ACK is received within a timeout period, an error report is generated and the data will be sent back to the original source of this data in order to retransmit.

4. Performance Analysis

We simulate energy aware routing on GloMoSim , a scalable discrete-event simulator developed by UCLA. This software provides a high fidelity simulation for wireless communication with detailed propagation, radio and MAC layers. We evaluate the effectiveness and efficiency of the energy aware routing protocol through simulation experiments. We compare energy aware routing with two popular sensor network routing protocols - SPEED a QoS routing protocol for sensor networks that provides soft real-time end-to-end guarantees and AODV. AODV is a routing scheme that forwards data along single path via route request and route reply messages.

4.2. Performance Metrics

Average Energy Consumption ( Ea ): The average energy consumption is calculated across the entire topology. It measures the average difference between the initial level of energy and the final level of energy that is left in each node. Let Ei = the initial energy level of a node, Ea = the final energy level of a node and N = number of nodes in the simulation. Then

This metric is important because the energy level that a network uses is proportional to the network’s lifetime. The lower the energy consumption the longer is the network’s lifespan. Data Delivery Ratio represents the ratio between the number of data packets that are sent by the source and the number of data packets that are received by the sink.

This metric indicates both the loss ratio of the routing protocol and the effort required to receive data. In the ideal scenario the ratio should be equal to 1. If the ratio falls significantly below the ideal ratio, then it could be an indication of some faults in the protocol design. However, if the ratio is higher than the ideal ratio, then it is an indication that the sink receives a Data packet more than once. It is not desirable because reception of duplicate packets consumes the network’s valuable resources. The relative number of duplicates received by the sink is also important because based on that number the sink, can possibly take an appropriate action to reduce the redundancy

Average Delay: It is defined as the average time between the moment a data packet is sent by a data source and the moment the sink receives the data packet. This metric defines the freshness of data packets.

5. Conclusion

We present an on-demand data-driven energy aware routing protocol, which adapts to the unique requirements for applications in sensor networks and therefore can be better applied in sensor networks. The analysis results show that the energy aware routing algorithm uses less energy than traditional algorithms for most realistic cases. There are several future works we would like to focus on. How to guarantee the delivery of packets under situations where non-uniform transmission ranges exist. Second, we will improve our protocol to decrease the delay. An optimal solution to this problem especially for mobile sensor networks is still an open question.

References

[1] Akkaya K., and Younis M., A Survey on Routing Protocols for Wireless Sensor Networks, 2004

[2] Akyildiz I., Su W., Sankarasubramaniam, Y.. Cayirci E.. A Survey on Sensor Networks, IEEE Communications Magazine, pp. 102-114, 2002

[3] Delin K. A., Sensor web in Antarctica. Developing an intelligent, autonomous platform for locating biological flourishes in cryogenic environments. In 34th Lunar and Planetary Science Conf. (LPSC 03). 2003

[4] Gsottberger Y., Shi X., Stromberg .S, Sturm .T. F., and Weber W., Embedding low-cost wireless sensors into universal plug and play environments. In Proc. Of EWSN, 2004

[5] Heinzelman W., Chandrakasan A., and Balakrishnan H., Energy efficient communication protocol for wireless sensor networks, Hawaii International Conference System Sciences, 2000.