A Survey of Energy Efficient Routing Protocols for Mobile Ad-hoc Networks

A Survey of Energy Efficient Routing Protocols for Mobile Ad-hoc Networks

Avani M. Patel1, Manish M. Patel2

1PG Student of Computer Engineering, Merchant Engineering College, Basna, Gujarat, India

2Asst. Prof. in Computer Engineering Department, LCIT, Bhandu, Gujarat, India

Abstract

This paper presents a survey on energy efficient routing protocols for Mobile ad hoc networks. Mobile ad hoc networks (MANETs) are autonomously self- organized networks without any fixed infrastructure. MANETs are deployed for emergency situation. In a mobile ad hoc network, nodes move randomly; therefore the topology may change rapidly and in unpredictable manner. Nodes in a MANET normally have limited transmission ranges, limited battery power and some nodes cannot communicate directly with each other. There may be multiple hops in a routing path hence every node in a MANET has the responsibility to act as a router. Reducing networks energy consumption and extending nodes lifetime are two important issues in MANET. This paper is a survey of active research work on routing protocols for MANET.

Keywords: MANET, Energy Efficient Routing, Proactive & Reactive Routing Protocols

I. Introduction

A Mobile ad hoc network is a set of nodes that have the ability to communicate wirelessly without the existence of any fixed infrastructure. Nodes in an ad hoc network use other nodes as intermediate relays to transmit packets to their destinations [1]. An Ad hoc network is adaptive in nature and self organizing. In this kind of network, wireless topology may change rapidly and unpredictably. The main characteristic of MANET strictly depends upon both wireless link nature and node mobility features. Basically this includes dynamic topology, bandwidth, energy constraints, security limitations and lack of infrastructure [3].

MANET is viewed as suitable systems which can support some specific applications as virtual classrooms, military communications, emergency search and rescue operations, data acquisition in hostile environments, communications set up in exhibitions, conferences and meetings, in battle field among soldiers to coordinate defense or attack, at airport terminals for workers to share files etc [3].

1. Challenges in Mobile Ad-hoc networks [4]

   Ad-hoc networks have to suffer many challenges at the time of routing. Dynamically changing topology and no centralized infrastructure are the biggest challenges in the designing of an Ad-hoc network. Topology varies very frequently so we have to select a protocol which dynamically adapts the situation.

   Another challenge in MANET is limited bandwidth. If we compare it to the wired network then wireless network has less and more varying bandwidth. So, if we want to increase the network lifetime (duration of time when the first node of the network runs out of energy) as well the node lifetime then we must have an energy efficient protocol. The main challenges in mobile ad-hoc networks are: 1. Limited power supply 2. Dynamically changing topology 3. Limited bandwidth 4. Security 5. Mobility-induced route changes 6. Mobility-induced packet losses 7. Battery constraints

2. Routing [4]

   It is the process of establishing path and forwarding packets from source node to destination node. It consists of two steps, route selection for various source-sink pairs and delivery of data packets to the correct destination. Various protocols and data structures (routing tables) are used to meet these two steps. This survey paper is focused on finding and selecting energy efficient routes.

3. Energy Efficient Routing [7]

Energy is a scarce resource in ad hoc wireless networks. Each node has the functionality of acting as a router along with being a source or destination. Thus the failure of some nodes operation can greatly impede performance of the network and even affect the basic availability of the network, i.e., routing, availability, etc. Energy management is classified into battery power management, transmission power management, system power management [2]. There are four energy cost metrics based on which we can decide the energy efficiency of a routing protocol.

TABLE – I

Some of the energy related cost metrics [7]

connection in order to transmit and receive the packet. There are various types of On-demand protocols which are: DSR, AODV etc.

C) Hybrid Routing [4]

Both of the proactive and reactive routing methods have some advantages and shortcomings. In hybrid routing, a combination of proactive and reactive routing methods are used which are better than the both used in isolation. It includes the advantages of both protocols. Examples of hybrid protocols are Zone Routing Protocol, Dual Hybrid Adaptive Routing (DHAR).

1. Proactive energy aware routing protocols and Algorithms

   First of all we will discuss about proactive routing protocols which are divided further in a following way on the basis of the algorithms used.

2. Classification of Routing Protocols

MANET routing protocols could be broadly classified into two major categories: Proactive and Reactive.

Proactive protocols

Distance Vector

(DSDV)

Link State

(OLSR)

1. Proactive (Table- Driven) Routing Protocol [8]

   In Proactive, nodes maintain one or more routing tables about nodes in the network. These routing protocols update the routing table information either periodically or in response to change in the network topology. The advantage of these protocols is that a source node does not need route-discovery procedures to find a route to a destination node. On the other hand the drawback of these protocols is that maintaining a consistent and up-to-date routing table requires substantial messaging overhead, which consumes bandwidth and power, and decreases throughput, especially in the case of a large number of high node mobility. There are various types of table driven protocols: DSDV, OLSR etc.

2. Reactive (On-Demand) Routing Protocol [8]

Reactive routing protocols are also known as on-demand routing protocols. These protocols have no routing information at the network nodes if there is no communication. They do not maintain or constantly update their route tables with the latest route topology. If a node wants to send a packet to another node then this protocol searches for the route and establishes the

1. Dynamic Destination – Sequenced Distance- Vector Routing Protocol (DSDV) [5]

   DSDV is developed on the basis of Bellman Ford routing algorithm with some modifications. In this routing protocol, each mobile node in the network keeps a routing table. Each of the routing table contains the list of all available destinations and the number of hops to each. Each table entry is tagged with a sequence number, which isoriginated by the destination node. Periodic transmissions of updates of the routing tables help maintaining the topology information of the network. If there is any new significant change for the routing information, the updates are transmitted immediately.

   So, the routing information updates might either be periodic or event driven. DSDV protocol requires each mobile node in the network to advertise its own routing table to its current neighbors. The advertisement is done either by broadcasting or by multicasting. By the advertisements, the neighboring nodes can know about any change that has occurred in the network due to the movements of nodes. The routing updates could be sent in two ways: one is called a full dump and another is incremental. In case of full dump, the entire routing table is sent to the neighbors, where as in case of incremental update, only the entries that require changes are sent.

2. Optimized Link-State Routing (OLSR) [2]

   The Optimized Link State Routing (OLSR) protocol is an optimization of the classical link state algorithm, adapted to the requirements of a MANET. Because of their quick convergence, link state algorithms are somewhat less prone to routing loops than distance vector algorithms, but they require more CPU power and memory. They can be more expensive to implement and support and are generally more scalable. OLSR operates in a hierarchical way (minimizing the organization and supporting high traffic rates). The key concept used in OLSR is that of multipoint relays (MPRs).

   MPRs are selected nodes which forward broadcast messages during the flooding process. This technique substantially reduces the message overhead as compared to a classical flooding mechanism (where every node retransmits each message received). This way a mobile host can reduce battery consumption. In OLSR, link state information is generated only by nodes elected as MPRs. An MPR node may choose to report only links between itself and its MPR selectors. Hence, contrarily to the classical link state algorithm, partial link state information is distributed in the network. This information is then used for route calculation. OLSR provides optimal routes. The protocol is particularly suitable for large and dense networks as the technique of MPRs works well in this context.

   Fig 1: MPR Election in OLSR protocol.

3. Energy Efficient OLSR (EE-OLSR) [2]

   With EE-OLSR (Energy-Efficient OLSR) we denote a routing protocol obtained modifying OLSR in order to improve its energy behavior, without loss of performance. Two mechanisms are used in this protocol: the EA Willingness setting and the Overhearing Exclusion.

4. Energy-efficient broadcast OLSR [4]

A new protocol EBOLSR is proposed in 2010 which adapts the OLSR protocol in order to maximize the network lifetime for broadcast communications. In EBOLSR energy efficient MPR selection is done by the residual energy of nodes, in

this protocol we consider the weighted residual energy of energy efficient MPR candidate and its 1 hop neighbors. The basic phenomenon about this EBOLSR protocol was to select the energy efficient multipoint relays [MPRs].

TABLE – II

Comparison between DSDV and OLSR [4]

1. Reactive energy aware routing protocols and algorithms

   The reactive routing protocols are based on some sort of query-reply dialog. Reactive protocols proceed for establishing route(s) to the destination only when the need arises. They do not need periodic transmission of topological information of the network [7].

   Source Routing [4]

   In source routing, data packets carry the complete addresses from source destination and no routing table in intermediate nodes. Some source routing protocols are: Dynamic Source routing, Associatively Based Routing, and Signal Stability- based Adaptive Routing.

   1. Dynamic Source Routing (DSR) [8]

      Dynamic Source Routing (DSR) is a routing protocol for wireless mesh networks and is based on a method known as source routing. It is similar to AODV in that it forms a route on-demand when a transmitting computer requests one. Except that each intermediate node that broadcasts a route request packet adds its own address identifier to a list carried in the packet. The destination node generates a route reply message that includes the list of addresses received in the route request and transmits it back along this path to the source. Route maintenance in

      DSR is accomplished through the confirmations that nodes generate when they can verify that the next node successfully received a packet. When a node is not able to verify the successful reception of a packet it tries to retransmit it.

      When a finite number of retransmissions fail, the node generates a route error message that specifies the problematic link, transmitting it to the source node. When a node requires a route to a destination, which it doesnt have in its route cache, it broadcasts a Route Request (RREQ) message, which is flooded throughout the network. The first RREQ message is a broadcast query on neighbors without flooding. Each RREQ packet is uniquely identified by the initiators address and the request id. A node processes a route request packet only if it has not already seen the packet and its address is not present in the route record of the packet. This minimizes the number of route requests propagated in the network. RREQ is replied by the destination node or an intermediate node, which knows the route, using the Route Reply (RREP) message. The return route for the RREP message may be one of the routes that exist in the route cache (if it exists) or a list reversal of the nodes in the RREQ packet if symmetrical routing is supported.

      In other cases the node may initiate it owns route discovery mechanism and piggyback the RREP packet onto it. Thus the route may be considered unidirectional or bidirectional. DSR doesnt enforce any use of periodic messages from the mobile hosts for maintenance of routes. Instead it uses two types of packets for route maintenance: Route Error (RERR) packets and ACKs. Whenever a node encounters fatal transmission errors so that the route becomes invalid, the source receives a RERR message. ACK packets are used to verify the correct operation of the route links. This also serves as a passive acknowledgement for the mobile node. DSR enables multiple routes to be learnt for a particular destination. DSR does not require any periodic update messages, thus avoiding wastage of bandwidth.

   2. Associativity -Based Routing (ABR) [5]

   ABR protocol defines a new type of routing metric degree of association stability for mobile ad hoc networks. In this routing protocol, a route is selected based on the degree of association stability of mobile nodes. Each node periodically generates beacon to announce its existence. Upon receiving the beacon message, a neighbor node updates its own associativity table. For each beacon received, the associativity tick of the receiving node with the beaconing node is increased. A high value of associativity tick for any particular beaconing node means that the node is relatively static. Associativity tick is reset when any neighboring node moves out of the neighborhood of any other node.

   Hop by Hop Routing [4]

   In hop- by- hp routing data packets do not carry complete route from source to destination while it carries only the address of destination and the next hop. Some hop by-hop routing protocols are: Ad-hoc on demand Distance Vector routing, Temporarily Ordered Routing Algorithm.

   1. Ad-hoc on demand Distance Vector routing (AODV) [9]

      The AODV protocol deals with a routing table. Every node is associated with a routing table. When a node knows a route to the destination, it sends a route reply to the source node. Its entries are as follows. Destination Address – Destination Sequence Number Next Hop Address – Lifetime (expiration or deletion time of the route) – Hop Count (number of hops to reach the destination). Nodes that can be communicated with are directly considered to be neighbors. A node keeps track of its neighbors by listening for a HELLO message that each new node broadcast and nodes broadcast at set intervals. When one node (the originator) needs to send a message to another node that is not its neighbor, it broadcasts a Route Request (RREQ) message.

      The RREQ message contains the following information: the source, the destination, the lifespan of the message and a Sequence Number, which serve as a unique ID. When the originator nodes neighbors receive the RREQ message they have two choices: if they know a route to the destination or if they are the destination they can send a Route Reply (RREP) message back to originator, otherwise they will rebroadcast the RREQ to their set of neighbors. The message keeps getting re-broadcasted until its lifespan is completed. If the originator does not receive a reply in a set amount of time, it will rebroadcast the request except that this time the RREQ message will have a longer lifespan and a new ID number. All of the nodes use the Sequence Number in the RREQ to insure that they do not re-broadcast a RREQ. Sequence numbers allow nodes to compare how fresh their information on other nodes is. Every time a node sends out any type of message, it increases its own sequence number. Each node records the sequence number of all the other nodes it talks to. A higher sequence numbers signifies a fresher route. In this way, it is possible for other nodes to determine which one has more accurate information.

   2. Temporarily Ordered Routing Algorithm (TORA) [5]

      TORA is a reactive routing protocol with some proactive enhancements where a link between nodes is established creating a Directed Acyclic Graph

      (DAG) of the route from the source node to the destination. This protocol uses a link reversal model in route discovery. A route discovery query is broadcasted and propagated throughout the network until it reaches the destination or a node that has information about how to reach the destination. TORA defines a parameter, termed height. Height is a measure of the distance of the responding nodes distance upto the required destination node. In the route discovery phase, this parameter is returned to the querying node. As the query response propagates back, each intermediate node updates its TORA table with the route and height to the destination node. The source node then uses the height to select the best route toward the destination. This protocol has an interesting property that it frequently chooses the most convenient route, rather than the shortest route. For all these attempts, TORA tries to minimize the routing management traffic overhead.

      Comparison of AODV and DSR [4]:

      • DSR has access to significantly greater amount of routing information than AODV by virtue of source routing and promiscuous listening.

      • DSR replies to all requests reaching a destination from a single request cycle where as AODV only replies once thereby learning only one route.

      • In DSR no particular mechanism to delete stale routes unlike AODV.

      • In AODV the route deletion causes all the nodes using that link to delete it, but in DSR only the nodes on that particular part are deleted.

2. Proposed Hybrid Routing Protocols: Major Features

1. Dual-Hybrid Adaptive Routing (DHAR) [5]

   DHAR uses the Distributed Dynamic Cluster Algorithm (DDCA). The idea of DDCA is to dynamically partition the network into some non- overlapping clusters of nodes consisting of one parent and zero or more children. Routing is done in DHAR utilizing a dynamic two level hierarchical strategy, consisting of optimal and least over head

   Table – driven algorithms operating at each level. DHAR implements a proactive least-overhead level-2

   routing protocol in combination with a dynamic binding protocol to achieve its hybrid characteristics.

   The level-2 protocol in DHAR requires that one node generates an update on behalf of its cluster. When a level-2 update is generated, it must be flooded to all the nodes in each neighboring cluster. Level-2 updates are not transmitted beyond the neighboring clusters. The node with the lowest node ID in each cluster is designated to generate level-2 updates. The binding process is similar to a reactive route discovery process; however, a priori knowledge of clustered topology makes it significantly more efficient and simpler to accomplish the routing. To send packets to the desired destination, a source node uses the dynamic binding protocol to discover the current cluster ID associated with the destination. Once determined, this information is maintained in the dynamic cluster binding cache at the source node. The dynamic binding protocol utilizes the knowledge of the level-2 topology to efficiently broadcast a binding request to all the clusters. This is achieved using reverse path forwarding with respect to the source cluster.

2. Zone Routing Protocol (ZRP) [5]

ZRP is suitable for wide variety of MANETs, especially for the networks with large span and diverse mobility patterns. In this protocol, each node proactively maintains routes within a local region, which is termed as routing zone. Route creation is done using a query-reply mechanism. For creating different zones in the network, a node first has to know who its neighbors are. A neighbor is defined as a node with whom direct communication can be established, and that is, within one hop transmission range of a node. Neighbor discovery information is used as a basis for intra-zone Routing Protocol (IARP). Rather than blind broadcasting, ZRP uses a query control mechanism to reduce route query traffic by directing query messages outward from the query source and away from covered routing zones. A covered node is a node which belongs to the routing zone of a node that has received a route query. During the forwarding of the query packet, a node identifies whether it is coming from its neighbor or not. If yes, then it marks all of its known neighboring nodes in its same zone as covered. The query is thus relayed till it reaches the destination. The destination in turn sends back a reply message via the reverse path and creates the route.

III. Comparison

TABLE – III

Comparison of main routing protocols on the basis of route type, route selection, route maintenance and discovery

VI. Conclusion

This paper presents a number of outing protocols for MANET which are broadly classified into proactive and reactive and also describe energy is on.e of the most important factor for this kind of network. Depending on the amount of network traffic, the routing protocols could be chosen. When there is congestion in the network due to heavy traffic, a reactive protocol is suitable. For example, AODV, DSR, OLSR are some protocols preferable for small networks, while the routing protocols like TORA, ZRP are preferable for dense networks.

Network mobility is another factor that can degrade the performance of certain protocols. When the network is relatively static, proactive routing protocols can be used. On the other hand, as the mobility of nodes in the network increases, reactive protocols perform better.

We conclude that there is not a single protocol which can give the best performance in ad-hoc network. Often it is more appropriate to apply a hybrid protocol rather than a strictly proactive or reactive protocol because they often possess the advantages of both types of protocols.

References

1. Christos A. Papageorgiou, Panagiotis C. Kokkinos, Emmanouel A. Varvarigos, Implementing Distributed Multicost Routing in Mobile Ad Hoc Networks Using DSR, October 3031, 2008, ACM 978-1-60558-055-5/08/10.

2. Floriano De Rango, Marco Fotino, Salvatore Marano, EE-OLSR: ENERGY EFFICIENT OLSR ROUTING PROTOCOL FOR MOBILE AD-HOC NETWORKS, 978-1-4244-2677-5/08©2008 IEEE

3. Vinay Rishiwal, Ashwani Kush, Shekhar Verma, Stable and Energy Efficient Routing for Mobile Adhoc Networks, 978-0-7695-3099-4/08© 2008 IEEE, DOI 10.1109/ITNG.2008.230.

4. Ajit Singh, Harshit Tiwari, Alok Vajpayee, Shiva Prakash, A Survey of Energy Efficient Routing Protocols for Mobile Ad-hoc Networks, IJCSE, Vol. 02, No. 09, 2010, 3111-3119.

5. G.Vijaya Kumar, Y.Vasudeva Reddyr, Dr.M.Nagendra Current Research Work on Routing Protocols for MANET: A Literature Survey IJCSE, Vol. 02, No. 03, 2010, 706-713.

6. P.Sivasankar, Dr.C.Chellappan, S.Balaji Performance Evaluation of Energy Efficient Routing Protocols for MANET International Journal of Computer Applications (0975 8887)

   Volume 28 No.8, August 2011.

7. Annapurna P Patil, Dr K Rajani kanth, Bathey Sharanya, M P Dinesh Kumar, Malavika J, Design of an Energy Efficient Routing Protocol for MANETs based on AODV, IJCSE Vol. 8, Issue 4, No 1, July 2011.

8. Tanu Preet Singh, Shivani Dua, Vikrant Das, Energy-Efficient Routing Protocols In Mobile Ad-Hoc Networks, IJARCSSE, Volume 2, Issue 1, January 2012, ISSN: 2277 128X.

9. Ajay Shah, Hitesh Gupta, Mukesh Baghel, Energy-Efficient Routing Protocol For Mobile Ad Hoc Networks, IJERA, Vol. 2, Issue4, July-August 2012, pp.1342-1346, ISSN: 2248-9622.