# Energy-Efficient Cluster Based Routing Protocol in Mobile Ad Hoc Networks Using Network Coding

Authors: Srinivas Kanakala; Venugopal Reddy Ananthula; Prashanthi Vempaty
Journal: Journal of Computer Networks and Communications
 (2014)

---

## Abstract

In mobile ad hoc networks, all nodes are energy constrained. In such situations, it is important to reduce energy consumption. In this paper, we consider the issues of energy efficient communication in MANETs using network coding. Network coding is an effective method to improve the performance of wireless networks. COPE protocol implements network coding concept to reduce number of transmissions by mixing the packets at intermediate nodes. We incorporate COPE into cluster based routing protocol to further reduce the energy consumption. The proposed energy-efficient coding-aware cluster based routing protocol (ECCRP) scheme applies network coding at cluster heads to reduce number of transmissions. We also modify the queue management procedure of COPE protocol to further improve coding opportunities. We also use an energy efficient scheme while selecting the cluster head. It helps to increase the life time of the network. We evaluate the performance of proposed energy efficient cluster based protocol using simulation. Simulation results show that the proposed ECCRP algorithm reduces energy consumption and increases life time of the network.


---

## Body

## 1. Introduction

Mobile ad hoc networks [1] are necessary when infrastructure does not exist or is difficult to set up. They are appropriate in disaster recovery, search and rescue in remote areas, battle fields, patient monitoring, Bluetooth, sensors, cyclone evolution analysis, detection of earth quakes, interactive museums or toys, providing security at public buildings, and locating an object. Mobile ad hoc networks facilitate users to communicate without any physical infrastructure. The construction of temporary network with no wires, no communication infrastructure, and no administrative intervention is required. Figure 1 shows MANET with five nodes.Figure 1
Mobile ad hoc network.Every node acts as a router and host to forward the data packets in MANETS. The nodes can move randomly. In a large scale of networking environment, one of the most important networking factors is self-organising capability for well adaptation of dynamic situations and interoperating capability between the nodes [2].The major issues of such studies are protocol design, particularly in this regard energy efficiency. Many researchers have developed different routing protocols at network layer but they have considered transmission power, residual battery capacity, and self-organisation while routing data packets to the destination [3]. The network lifetime depends on management of the energy resources. The desire to use less power in routing process has more benefits beyond conserving battery power of the node [4].Many research efforts have been devoted [5] for developing energy efficient routing protocols in MANETs. They considered two approaches called minimize active communication energy and inactive communication energy. Transmission power control and load balanced approaches are used to minimize the active communication energy. Sleep down mode is used to minimize inactive communication energy. Above works consider energy-efficient communication problems in MANETs without network coding.In this paper, we strive to apply network coding technology to reduce energy consumption of routing protocols. Our goal is to minimize the energy consumption in cluster based routing protocol by incorporating network coding technology into CBRP [6] protocol. Network coding is a popular mechanism to increase throughput of the wireless networks. It performs mixing of packets at intermediate nodes. Hence, it reduces the number of packet transmissions and therefore it also reduces redundant transmissions which occur due to broadcasting. Each packet transmission consumes energy and the energy consumption is proportional to the number of packet transmissions. Cluster based approach is used to reduce overall broadcast overhead. Cluster heads help to avoid unnecessary network-wide flooding in MANETs. COPE [7] is the first protocol to implement wireless network coding.In COPE, to increase coding opportunities, coding can be performed at all nodes in the network. Therefore it creates additional computing overhead. To reduce this overhead, we apply network coding only at particular nodes to reduce the number of coding nodes. This network coding can be performed at cluster heads. To identify these cluster heads, we are using the clustered based routing protocol (CBRP). We apply network coding at cluster heads to reduce the coding overhead and reduce redundant transmissions and therefore reduce the number of transmissions. Therefore it reduces the energy consumption involved in sending and receiving packet transmissions.This paper introduces a network coding-aware energy-efficient cluster based routing protocol (ECCRP) for MANETs. Our work is different from existing ones in the following ways. First, the network nodes are grouped into clusters. We select the cluster head as energy rich nodes to increase the life time of network and reduce energy consumption. Then network coding is performed only at cluster heads to reduce the overhead problems of network coding. Second, while performing coding at cluster heads we modify the queue structure of COPE. We use flow based queue structure to increase the coding opportunities and reduce the number of transmissions, which helps to reduce energy consumption.The rest of the paper is organized as follows. In Section2, some of the existing works related to energy efficient routing are presented. The proposed algorithm and its working procedures are discussed in Section 3. In Section 4, it presents the evaluation of the proposed algorithm using simulation results. Finally, Section 5 summarizes the conclusions.


## 2. Related Work

### 2.1. Energy Efficient Routing Protocols

This section discusses some of the existing energy efficient routing protocols. Many previous researchers have developed power aware routing protocols. Different approaches can be applied to attain the goal [8]. Transmission power control and load distribution are two approaches to minimize the active communication energy. Sleep/power-down mode is used to minimize energy during inactivity. Some research proposals, which are based on transmission power control approach, are discussed in [9, 10]. Flow argumentation routing (FAR) [9] which assumes a static network and finds the optimal routing path for a given source-destination pair that minimizes the sum of link costs along the path. Power aware localized routing (PLR) [9] is a localized, fully distributed energy aware routing algorithm but it assumes that a source node has the location information of its neighbors and the destination and Minimum Energy Routing (MER) [10] addresses issues like obtaining accurate power information, associated overheads, and maintenance of the minimum energy routes in the presence of mobility and implements the transmission power control mechanism in DSR and IEEE 802.11 MAC protocol.Singh and Raghavendra [11] proposed the PAMAS protocol that uses two different channels to separate data and signaling. Singh et al. [12] presented several power-aware metrics that do result in energy-efficient routes. The Minimum Total Transmission Power Routing (MTPR) [13] was initially developed to minimize the total transmission power consumption of nodes participating in the acquired route. The Min-Max Battery Cost Routing (MMBCR) [14] considers the remaining power of nodes as the metric for acquiring routes in order to prolong the lifetime of network. Toh [14] presented the Conditional Max-Min Battery Capacity Routing (CMMBCR) protocol, which is a hybrid protocol that tries to arbitrate between the MTPR and the MMBCR. The several multipath proactive routing protocols were developed. These protocols use table-driven algorithms (link state or distance vector) to compute multiple routes. But they do not consider the power aware metrics and these protocols generate excessive routing overhead and perform poorly because of their proactive nature.Recently, several Energy Aware On-demand Multipath Routing protocols have been proposed. The Grid-Based Energy Aware Node-Disjoint Multipath Routing Algorithm (GEANDMRA) [15] considers energy aware and node-disjoint multipath and it uses grid head election algorithm to select the grid head which is responsible for forwarding routing information and transmitting data packets. The Ant-based Energy Aware Disjoint Multipath Routing Algorithm (AEADMRA) [16] is based on swarm intelligence and especially on the ant colony based metaheuristic. The Multipath Energy-Efficient Routing Protocol (MEER) [17] prolongs the network lifetime by using a rational power control mechanism. The Lifetime-Aware Multipath Optimized Routing (LAMOR) [18] is based on the lifetime of a node which is related to its residual energy and current traffic conditions.The Power-Aware Multipath Routing Protocol (PAMP) [19] is an extension of the existing AODV by modifying RREQ and RREP management mechanism to handle energy reservation and multiple paths. The Multipath Power Sensitive Routing (MPSR) [20] shows how an efficient heuristic based multipath technique can improve the mean time to node failure and maintain the variance in the power of all the nodes as low as possible. The Energy Aware Source Routing (EASR) [21] discovers paths without overlapping, each path hardly overhears other data transmission, and it reduces the overhearing energy waste among selected paths by using the overhearing ratio.


### 2.2. Network Coding-Aware Routing

Network coding was first proposed by Ahlswede et al. [22] and it was initially targeted at the multicast in traditional wired networks. For wireless networks, some works [23, 24] theoretically study the network coding efficiency in multihop wireless networks. In particular, COPE [7] takes advantage of the broadcast nature of the wireless channel to perform opportunistic listening and opportunistic coding so that the coding opportunities are potentially enlarged.More recently, coding-aware routing is known to further improve the network performance by creating more coding opportunities. In [25, 26], the authors propose coding-aware routing schemes to maximize the overall coding opportunities in the whole network by using linear programming. However, their works are centralized approaches, which is difficult to be implemented in practice. In [27, 28], the authors propose practical coding-aware routing mechanisms to actively create more coding opportunities. Particularly, [27] presented a novel coding condition on k-hop model instead of the popular “two hop” coding structure. However, the coding condition may be invalid when there are multiple intersecting nodes along a path.The basic idea is to route the flows in the network to a region where network coding can be performed. This improves the throughput; however, it greatly affects the network lifetime. Concentrating large amounts of traffic to a small region in the network burdens the involved nodes. This routing approach can eventually lead to a network breakdown. Therefore, such an approach cannot be applied to energy constrained networks.Although the above solutions are effective for energy-unaware networks, they cannot be directly applied to energy-constrained networks where network lifetime is of paramount importance network coding. The idea underlying network coding can be illustrated by a fairly simple symmetrical network model in Figure2.(a) Without network coding, (b) With network coding.
(a)
(b)Considering Figure2(a) where A and B want to exchange information between each other via a router, if the model employs TDMA (time division multiple access) channel access method for the shared medium, we can demonstrate how the transmission works as Figures 2(a) and 2(b), representing data transmissions using time slots under traditional method and network coding method separately. Obviously, to exchange one packet, a traditional routing network needs 4 transmissions while, with network coding, only 3 transmissions are needed, and saved time can be used to transmit new data, thus increasing network throughput. In fact, with the shared nature of wireless medium and multihop data flows, network coding leads to larger bandwidth savings than those which are apparent from this example. COPE is a new forwarding architecture for wireless network that inserts a coding shim between the IP and MAC layers, which identifies coding opportunities and benefits from them by forwarding multiple packets in a single transmission.The example in Figure3 demonstrates a scenario of a coding gain. Here, the source S wants to send packets A and B, respectively, to both receivers R1 and R2 without network coding and it requires 8 transmissions. If we perform xor operation on the packets at node X then the number of transmissions reduced to 7. Therefore coding gain in butterfly network topology 8/7=1.14. Similarly, we can find the coding gain for Figure 2(b) as 4/3=1.33 and thus network coding helps us to reduce the number of transmissions and increase the throughput.Figure 3
Network coding in butterfly network.


### 2.3. COPE: Practical Wireless Network Coding

COPE is a forwarding architecture that inserts a coding scheme between IP and MAC layer which detects coding opportunities and exploits them to forward multiple packets in a single transmission. COPE employs network coding, which allows the intermediate node to mix the information content in the packets before forwarding them.COPE design is based on two key principles. COPE disposes of the point-to-point abstraction and embraces the broadcast nature of the wireless channel. Network designers typically abstract the wireless channel as a point-to-point link and then adopt forwarding and broadcast techniques designed for wired and wireless network. In contrast, COPE exploits the broadcast property of radios instead of hiding it under an artificial abstraction.Figure4 shows that the best coding scenario can be selected so that the maximum number of neighbors benefitted. Therefore, we can reduce the number of transmissions. Here, B can send coded packets to its neighbor nodes. Nodes A, C, and D show the packets available with that node. B wants to send packets p1, p2, p3, p4 to A, C, C, and D, respectively. Now, if we perform mixing of packets at node B as p1+p2 using xor operation and broadcast, then only C can decode and get p2 and node B can perform p1+p3 then both A and C can decode and get P1 and p3, respectively. To maximize the number of packets delivered in a single transmission, B can mix p1, p3, p4 and broadcast and then nodes A, C, and D can decode and get p1, p3, p4, respectively. That is at node A we get p1=p4+p3+p1+p3+p4.Figure 4
Best coding scenario of cope.


### 2.4. Clustering of Nodes in MANETs

A cluster is a subset of nodes which can communicate with cluster head and with each other. A node is defined as a Gateway if it is the neighbor of two or more cluster heads. The process of dividing the network into interconnected substructures is called clustering and the interconnected substructures are called clusters. The cluster head (CH) of each cluster acts as a coordinator within the substructure. Each CH acts as a temporary base station within its zone or cluster. It also communicates with other CHs [6]. The cluster based routing provides an answer to address nodes heterogeneity and to limit the amount of routing information that propagates inside the network. Figure 5 shows an example of clustered network.Figure 5
An example clustered network.


#### 2.4.1. Advantages of Clustering

Clustering in ad hoc networks has many advantages compared to the traditional networks. They are as follows.(1)
It allows the better performance of the protocol for the medium access control (MAC) layer by improving the spatial reuse, throughput, scalability, and power consumption.(2)
It helps to improve routing at the network layer by reducing the size of the routing tables.(3)
It decreases transmission overhead by updating the routing tables after topological changes occur [4].(4)
It helps to aggregate topology information as the nodes of a cluster are smaller when compared to the nodes of entire network. Here, each node stores only a fraction of the total network routing information.(5)
It saves energy and communication bandwidth in ad hoc networks [3].CBRP [6] uses two data structures to support the routing process: the cluster adjacency table (CAT) and the two-hop topology database. The CAT stores information about neighbouring clusters. This is whether they are bidirectionally or unidirectionally linked. That means that a cluster is called (i) bidirectionally linked, if there is a bidirectional link between two nodes of the clusters, or if there are at least two opposite unidirectional links between two nodes or (ii) unidirectionally linked, if there is just one unidirectional link between them. The two-hop topology database is built from the information received by Hello messages. It contains all nodes that are at most two hops away. The routing process works in two steps. First, it discovers a route from a source node S to a destination node D, and afterwards it routes the packets.


#### 2.4.2. Cluster Formation in CBRP

The following states describe the clustering process depending on the current node state. These states are as follows.Undecided. This means that the node does not belong to any cluster and this usually occurs if a new node appears in the network. Thus, if it receives a Hello message from a cluster head and there is a bidirectional link between them, it changes its state to be member of the cluster indicated by the cluster head. Otherwise, it looks up in its neighbour table if it has any bidirectional links. If so, it becomes itself the cluster head of a new cluster, if not, it remains in the undecided state and tries again.Cluster Head. If a cluster head detects that it has a bidirectional link to another cluster head for a time period, it changes its state to member if the other cluster head has a lower ID. Otherwise, it stays the cluster head and the other node has to change its state. This is a special case which may result in cluster reorganisation (Figure 5).Member. If a member loses its cluster head, it looks for bidirectional links to other nodes. If it detects any, it changes its state to cluster head if it has the lowest ID; otherwise, it switches to the undecided state. Each member node belongs at least to one cluster.In CBRP [6], the nodes of a wireless network are divided into several disjoint or overlapping clusters. Each cluster elects one node as the so-called cluster head. These special nodes are responsible for the routing process. Neighbours of cluster heads cannot be cluster heads as well. But cluster heads are able to communicate with each other by using gateway nodes. A gateway is a node that has two or more cluster heads as its neighbours or—when the clusters are disjoint—at least one cluster head and another gateway node. The routing process itself is performed as source routing by flooding the network with a route request message. Due to the clustered structure, there will be less traffic, because route requests will only be passed between cluster heads.CBRP is a robust/scalable routing protocol for MANETs and superior to the existing methods [1–3] (e.g., the overhead of it is less than and throughput of it is more than those of AODV) [4]. CBRP is a routing protocol designed for medium to large mobile ad hoc networks. The protocol divides the nodes of the ad hoc network into a number of overlapping or disjoint 2-hop diameter clusters in a distributed manner. Each cluster chooses a head to retain cluster membership information. The algorithm is a variation of the “lowest ID” cluster algorithm. The node with a lowest ID among its neighbors is elected as the cluster head (CH). Each node maintains a Neighbor Table and a Cluster Adjacency Table. Neighbor Table is a conceptual data structure that it employs for link status sensing and cluster formation. Cluster Adjacency Table keeps information about adjacent clusters for Adjacent Cluster Discovery. These tables are updated by the periodic Hello messages (HM).In CBRP, routing is based on source routing. Cluster structure is exploited to minimize the flooding traffic during route discovery phase. Furthermore, certain unidirectional links are discovered and used, and thus it is increasing the network connectivity. Based on cluster membership and information kept at each cluster head, intercluster routes are dynamically discovered. Essentially, in route discovery, only cluster heads are flooded with route request packets (RREQ) in search for a source route. Each cluster head node forwards an RREQ packet only once and it never forwards it to a node that has already appeared in the recorded route.It proactively acquires its intracluster topology information through the exchange of Hello messages and reactively acquires the route information intercluster. An example of an ad hoc network is shown in Figure5.  Nodes are organized to three clusters; each of which has a CH.Unlike the other on-demand routing protocols, in CBRP, the nodes are organized in a hierarchy. As almost in all hierarchical protocols, CH coordinates the data transmission between clusters. The advantage of CBRP is that only CHs exchange routing information; therefore, the number of control overheads transmitted through the network is far less than the traditional flooding methods. However, as in any other hierarchical routing protocol, there are overheads associated with cluster formation and maintenance. A neighbor table in every node of CBRP keeps the information about link states (unidirectional or bidirectional) and the state of its neighbors. A CH keeps information of its neighboring clusters, in addition to the information of all members in its cluster. The information includes the CHs of neighboring clusters and gateway nodes connecting it to the neighboring clusters [6].


## 2.1. Energy Efficient Routing Protocols

This section discusses some of the existing energy efficient routing protocols. Many previous researchers have developed power aware routing protocols. Different approaches can be applied to attain the goal [8]. Transmission power control and load distribution are two approaches to minimize the active communication energy. Sleep/power-down mode is used to minimize energy during inactivity. Some research proposals, which are based on transmission power control approach, are discussed in [9, 10]. Flow argumentation routing (FAR) [9] which assumes a static network and finds the optimal routing path for a given source-destination pair that minimizes the sum of link costs along the path. Power aware localized routing (PLR) [9] is a localized, fully distributed energy aware routing algorithm but it assumes that a source node has the location information of its neighbors and the destination and Minimum Energy Routing (MER) [10] addresses issues like obtaining accurate power information, associated overheads, and maintenance of the minimum energy routes in the presence of mobility and implements the transmission power control mechanism in DSR and IEEE 802.11 MAC protocol.Singh and Raghavendra [11] proposed the PAMAS protocol that uses two different channels to separate data and signaling. Singh et al. [12] presented several power-aware metrics that do result in energy-efficient routes. The Minimum Total Transmission Power Routing (MTPR) [13] was initially developed to minimize the total transmission power consumption of nodes participating in the acquired route. The Min-Max Battery Cost Routing (MMBCR) [14] considers the remaining power of nodes as the metric for acquiring routes in order to prolong the lifetime of network. Toh [14] presented the Conditional Max-Min Battery Capacity Routing (CMMBCR) protocol, which is a hybrid protocol that tries to arbitrate between the MTPR and the MMBCR. The several multipath proactive routing protocols were developed. These protocols use table-driven algorithms (link state or distance vector) to compute multiple routes. But they do not consider the power aware metrics and these protocols generate excessive routing overhead and perform poorly because of their proactive nature.Recently, several Energy Aware On-demand Multipath Routing protocols have been proposed. The Grid-Based Energy Aware Node-Disjoint Multipath Routing Algorithm (GEANDMRA) [15] considers energy aware and node-disjoint multipath and it uses grid head election algorithm to select the grid head which is responsible for forwarding routing information and transmitting data packets. The Ant-based Energy Aware Disjoint Multipath Routing Algorithm (AEADMRA) [16] is based on swarm intelligence and especially on the ant colony based metaheuristic. The Multipath Energy-Efficient Routing Protocol (MEER) [17] prolongs the network lifetime by using a rational power control mechanism. The Lifetime-Aware Multipath Optimized Routing (LAMOR) [18] is based on the lifetime of a node which is related to its residual energy and current traffic conditions.The Power-Aware Multipath Routing Protocol (PAMP) [19] is an extension of the existing AODV by modifying RREQ and RREP management mechanism to handle energy reservation and multiple paths. The Multipath Power Sensitive Routing (MPSR) [20] shows how an efficient heuristic based multipath technique can improve the mean time to node failure and maintain the variance in the power of all the nodes as low as possible. The Energy Aware Source Routing (EASR) [21] discovers paths without overlapping, each path hardly overhears other data transmission, and it reduces the overhearing energy waste among selected paths by using the overhearing ratio.


## 2.2. Network Coding-Aware Routing

Network coding was first proposed by Ahlswede et al. [22] and it was initially targeted at the multicast in traditional wired networks. For wireless networks, some works [23, 24] theoretically study the network coding efficiency in multihop wireless networks. In particular, COPE [7] takes advantage of the broadcast nature of the wireless channel to perform opportunistic listening and opportunistic coding so that the coding opportunities are potentially enlarged.More recently, coding-aware routing is known to further improve the network performance by creating more coding opportunities. In [25, 26], the authors propose coding-aware routing schemes to maximize the overall coding opportunities in the whole network by using linear programming. However, their works are centralized approaches, which is difficult to be implemented in practice. In [27, 28], the authors propose practical coding-aware routing mechanisms to actively create more coding opportunities. Particularly, [27] presented a novel coding condition on k-hop model instead of the popular “two hop” coding structure. However, the coding condition may be invalid when there are multiple intersecting nodes along a path.The basic idea is to route the flows in the network to a region where network coding can be performed. This improves the throughput; however, it greatly affects the network lifetime. Concentrating large amounts of traffic to a small region in the network burdens the involved nodes. This routing approach can eventually lead to a network breakdown. Therefore, such an approach cannot be applied to energy constrained networks.Although the above solutions are effective for energy-unaware networks, they cannot be directly applied to energy-constrained networks where network lifetime is of paramount importance network coding. The idea underlying network coding can be illustrated by a fairly simple symmetrical network model in Figure2.(a) Without network coding, (b) With network coding.
(a)
(b)Considering Figure2(a) where A and B want to exchange information between each other via a router, if the model employs TDMA (time division multiple access) channel access method for the shared medium, we can demonstrate how the transmission works as Figures 2(a) and 2(b), representing data transmissions using time slots under traditional method and network coding method separately. Obviously, to exchange one packet, a traditional routing network needs 4 transmissions while, with network coding, only 3 transmissions are needed, and saved time can be used to transmit new data, thus increasing network throughput. In fact, with the shared nature of wireless medium and multihop data flows, network coding leads to larger bandwidth savings than those which are apparent from this example. COPE is a new forwarding architecture for wireless network that inserts a coding shim between the IP and MAC layers, which identifies coding opportunities and benefits from them by forwarding multiple packets in a single transmission.The example in Figure3 demonstrates a scenario of a coding gain. Here, the source S wants to send packets A and B, respectively, to both receivers R1 and R2 without network coding and it requires 8 transmissions. If we perform xor operation on the packets at node X then the number of transmissions reduced to 7. Therefore coding gain in butterfly network topology 8/7=1.14. Similarly, we can find the coding gain for Figure 2(b) as 4/3=1.33 and thus network coding helps us to reduce the number of transmissions and increase the throughput.Figure 3
Network coding in butterfly network.


## 2.3. COPE: Practical Wireless Network Coding

COPE is a forwarding architecture that inserts a coding scheme between IP and MAC layer which detects coding opportunities and exploits them to forward multiple packets in a single transmission. COPE employs network coding, which allows the intermediate node to mix the information content in the packets before forwarding them.COPE design is based on two key principles. COPE disposes of the point-to-point abstraction and embraces the broadcast nature of the wireless channel. Network designers typically abstract the wireless channel as a point-to-point link and then adopt forwarding and broadcast techniques designed for wired and wireless network. In contrast, COPE exploits the broadcast property of radios instead of hiding it under an artificial abstraction.Figure4 shows that the best coding scenario can be selected so that the maximum number of neighbors benefitted. Therefore, we can reduce the number of transmissions. Here, B can send coded packets to its neighbor nodes. Nodes A, C, and D show the packets available with that node. B wants to send packets p1, p2, p3, p4 to A, C, C, and D, respectively. Now, if we perform mixing of packets at node B as p1+p2 using xor operation and broadcast, then only C can decode and get p2 and node B can perform p1+p3 then both A and C can decode and get P1 and p3, respectively. To maximize the number of packets delivered in a single transmission, B can mix p1, p3, p4 and broadcast and then nodes A, C, and D can decode and get p1, p3, p4, respectively. That is at node A we get p1=p4+p3+p1+p3+p4.Figure 4
Best coding scenario of cope.


## 2.4. Clustering of Nodes in MANETs

A cluster is a subset of nodes which can communicate with cluster head and with each other. A node is defined as a Gateway if it is the neighbor of two or more cluster heads. The process of dividing the network into interconnected substructures is called clustering and the interconnected substructures are called clusters. The cluster head (CH) of each cluster acts as a coordinator within the substructure. Each CH acts as a temporary base station within its zone or cluster. It also communicates with other CHs [6]. The cluster based routing provides an answer to address nodes heterogeneity and to limit the amount of routing information that propagates inside the network. Figure 5 shows an example of clustered network.Figure 5
An example clustered network.


### 2.4.1. Advantages of Clustering

Clustering in ad hoc networks has many advantages compared to the traditional networks. They are as follows.(1)
It allows the better performance of the protocol for the medium access control (MAC) layer by improving the spatial reuse, throughput, scalability, and power consumption.(2)
It helps to improve routing at the network layer by reducing the size of the routing tables.(3)
It decreases transmission overhead by updating the routing tables after topological changes occur [4].(4)
It helps to aggregate topology information as the nodes of a cluster are smaller when compared to the nodes of entire network. Here, each node stores only a fraction of the total network routing information.(5)
It saves energy and communication bandwidth in ad hoc networks [3].CBRP [6] uses two data structures to support the routing process: the cluster adjacency table (CAT) and the two-hop topology database. The CAT stores information about neighbouring clusters. This is whether they are bidirectionally or unidirectionally linked. That means that a cluster is called (i) bidirectionally linked, if there is a bidirectional link between two nodes of the clusters, or if there are at least two opposite unidirectional links between two nodes or (ii) unidirectionally linked, if there is just one unidirectional link between them. The two-hop topology database is built from the information received by Hello messages. It contains all nodes that are at most two hops away. The routing process works in two steps. First, it discovers a route from a source node S to a destination node D, and afterwards it routes the packets.


### 2.4.2. Cluster Formation in CBRP

The following states describe the clustering process depending on the current node state. These states are as follows.Undecided. This means that the node does not belong to any cluster and this usually occurs if a new node appears in the network. Thus, if it receives a Hello message from a cluster head and there is a bidirectional link between them, it changes its state to be member of the cluster indicated by the cluster head. Otherwise, it looks up in its neighbour table if it has any bidirectional links. If so, it becomes itself the cluster head of a new cluster, if not, it remains in the undecided state and tries again.Cluster Head. If a cluster head detects that it has a bidirectional link to another cluster head for a time period, it changes its state to member if the other cluster head has a lower ID. Otherwise, it stays the cluster head and the other node has to change its state. This is a special case which may result in cluster reorganisation (Figure 5).Member. If a member loses its cluster head, it looks for bidirectional links to other nodes. If it detects any, it changes its state to cluster head if it has the lowest ID; otherwise, it switches to the undecided state. Each member node belongs at least to one cluster.In CBRP [6], the nodes of a wireless network are divided into several disjoint or overlapping clusters. Each cluster elects one node as the so-called cluster head. These special nodes are responsible for the routing process. Neighbours of cluster heads cannot be cluster heads as well. But cluster heads are able to communicate with each other by using gateway nodes. A gateway is a node that has two or more cluster heads as its neighbours or—when the clusters are disjoint—at least one cluster head and another gateway node. The routing process itself is performed as source routing by flooding the network with a route request message. Due to the clustered structure, there will be less traffic, because route requests will only be passed between cluster heads.CBRP is a robust/scalable routing protocol for MANETs and superior to the existing methods [1–3] (e.g., the overhead of it is less than and throughput of it is more than those of AODV) [4]. CBRP is a routing protocol designed for medium to large mobile ad hoc networks. The protocol divides the nodes of the ad hoc network into a number of overlapping or disjoint 2-hop diameter clusters in a distributed manner. Each cluster chooses a head to retain cluster membership information. The algorithm is a variation of the “lowest ID” cluster algorithm. The node with a lowest ID among its neighbors is elected as the cluster head (CH). Each node maintains a Neighbor Table and a Cluster Adjacency Table. Neighbor Table is a conceptual data structure that it employs for link status sensing and cluster formation. Cluster Adjacency Table keeps information about adjacent clusters for Adjacent Cluster Discovery. These tables are updated by the periodic Hello messages (HM).In CBRP, routing is based on source routing. Cluster structure is exploited to minimize the flooding traffic during route discovery phase. Furthermore, certain unidirectional links are discovered and used, and thus it is increasing the network connectivity. Based on cluster membership and information kept at each cluster head, intercluster routes are dynamically discovered. Essentially, in route discovery, only cluster heads are flooded with route request packets (RREQ) in search for a source route. Each cluster head node forwards an RREQ packet only once and it never forwards it to a node that has already appeared in the recorded route.It proactively acquires its intracluster topology information through the exchange of Hello messages and reactively acquires the route information intercluster. An example of an ad hoc network is shown in Figure5.  Nodes are organized to three clusters; each of which has a CH.Unlike the other on-demand routing protocols, in CBRP, the nodes are organized in a hierarchy. As almost in all hierarchical protocols, CH coordinates the data transmission between clusters. The advantage of CBRP is that only CHs exchange routing information; therefore, the number of control overheads transmitted through the network is far less than the traditional flooding methods. However, as in any other hierarchical routing protocol, there are overheads associated with cluster formation and maintenance. A neighbor table in every node of CBRP keeps the information about link states (unidirectional or bidirectional) and the state of its neighbors. A CH keeps information of its neighboring clusters, in addition to the information of all members in its cluster. The information includes the CHs of neighboring clusters and gateway nodes connecting it to the neighboring clusters [6].


## 2.4.1. Advantages of Clustering

Clustering in ad hoc networks has many advantages compared to the traditional networks. They are as follows.(1)
It allows the better performance of the protocol for the medium access control (MAC) layer by improving the spatial reuse, throughput, scalability, and power consumption.(2)
It helps to improve routing at the network layer by reducing the size of the routing tables.(3)
It decreases transmission overhead by updating the routing tables after topological changes occur [4].(4)
It helps to aggregate topology information as the nodes of a cluster are smaller when compared to the nodes of entire network. Here, each node stores only a fraction of the total network routing information.(5)
It saves energy and communication bandwidth in ad hoc networks [3].CBRP [6] uses two data structures to support the routing process: the cluster adjacency table (CAT) and the two-hop topology database. The CAT stores information about neighbouring clusters. This is whether they are bidirectionally or unidirectionally linked. That means that a cluster is called (i) bidirectionally linked, if there is a bidirectional link between two nodes of the clusters, or if there are at least two opposite unidirectional links between two nodes or (ii) unidirectionally linked, if there is just one unidirectional link between them. The two-hop topology database is built from the information received by Hello messages. It contains all nodes that are at most two hops away. The routing process works in two steps. First, it discovers a route from a source node S to a destination node D, and afterwards it routes the packets.


## 2.4.2. Cluster Formation in CBRP

The following states describe the clustering process depending on the current node state. These states are as follows.Undecided. This means that the node does not belong to any cluster and this usually occurs if a new node appears in the network. Thus, if it receives a Hello message from a cluster head and there is a bidirectional link between them, it changes its state to be member of the cluster indicated by the cluster head. Otherwise, it looks up in its neighbour table if it has any bidirectional links. If so, it becomes itself the cluster head of a new cluster, if not, it remains in the undecided state and tries again.Cluster Head. If a cluster head detects that it has a bidirectional link to another cluster head for a time period, it changes its state to member if the other cluster head has a lower ID. Otherwise, it stays the cluster head and the other node has to change its state. This is a special case which may result in cluster reorganisation (Figure 5).Member. If a member loses its cluster head, it looks for bidirectional links to other nodes. If it detects any, it changes its state to cluster head if it has the lowest ID; otherwise, it switches to the undecided state. Each member node belongs at least to one cluster.In CBRP [6], the nodes of a wireless network are divided into several disjoint or overlapping clusters. Each cluster elects one node as the so-called cluster head. These special nodes are responsible for the routing process. Neighbours of cluster heads cannot be cluster heads as well. But cluster heads are able to communicate with each other by using gateway nodes. A gateway is a node that has two or more cluster heads as its neighbours or—when the clusters are disjoint—at least one cluster head and another gateway node. The routing process itself is performed as source routing by flooding the network with a route request message. Due to the clustered structure, there will be less traffic, because route requests will only be passed between cluster heads.CBRP is a robust/scalable routing protocol for MANETs and superior to the existing methods [1–3] (e.g., the overhead of it is less than and throughput of it is more than those of AODV) [4]. CBRP is a routing protocol designed for medium to large mobile ad hoc networks. The protocol divides the nodes of the ad hoc network into a number of overlapping or disjoint 2-hop diameter clusters in a distributed manner. Each cluster chooses a head to retain cluster membership information. The algorithm is a variation of the “lowest ID” cluster algorithm. The node with a lowest ID among its neighbors is elected as the cluster head (CH). Each node maintains a Neighbor Table and a Cluster Adjacency Table. Neighbor Table is a conceptual data structure that it employs for link status sensing and cluster formation. Cluster Adjacency Table keeps information about adjacent clusters for Adjacent Cluster Discovery. These tables are updated by the periodic Hello messages (HM).In CBRP, routing is based on source routing. Cluster structure is exploited to minimize the flooding traffic during route discovery phase. Furthermore, certain unidirectional links are discovered and used, and thus it is increasing the network connectivity. Based on cluster membership and information kept at each cluster head, intercluster routes are dynamically discovered. Essentially, in route discovery, only cluster heads are flooded with route request packets (RREQ) in search for a source route. Each cluster head node forwards an RREQ packet only once and it never forwards it to a node that has already appeared in the recorded route.It proactively acquires its intracluster topology information through the exchange of Hello messages and reactively acquires the route information intercluster. An example of an ad hoc network is shown in Figure5.  Nodes are organized to three clusters; each of which has a CH.Unlike the other on-demand routing protocols, in CBRP, the nodes are organized in a hierarchy. As almost in all hierarchical protocols, CH coordinates the data transmission between clusters. The advantage of CBRP is that only CHs exchange routing information; therefore, the number of control overheads transmitted through the network is far less than the traditional flooding methods. However, as in any other hierarchical routing protocol, there are overheads associated with cluster formation and maintenance. A neighbor table in every node of CBRP keeps the information about link states (unidirectional or bidirectional) and the state of its neighbors. A CH keeps information of its neighboring clusters, in addition to the information of all members in its cluster. The information includes the CHs of neighboring clusters and gateway nodes connecting it to the neighboring clusters [6].


## 3. Proposed Energy-Efficient Coding-Aware Routing Protocol (ECCRP)

### 3.1. Proposed System Model

We propose an energy efficient coding-aware routing protocol to efficiently use the energy resources of the nodes. This method uses wireless network coding to reduce the energy consumed in transmitting and receiving the packets at a node. We apply network coding into CBRP protocol to get advantage of clustering and reduce the overhead of broadcasting. Figure6 shows the proposed system model. The proposed system takes the input parameters like nodes, mobility of nodes, initial energy of the nodes, and packets to be sent. It generates the output in terms of the time of simulation, the number of packets delivered to destination, and the remaining energy of the nodes after the simulation.Figure 6
System Model.


### 3.2. Cluster Formation Scheme

We used lowest id [29] concept in our cluster formation scheme. To stop the frequent changes in cluster configuration, least cluster change LCC [30] scheme is used.


### 3.3. Energy Efficient COPE Architecture

This method increases the coding opportunities at the cluster heads. In a COPE based network, a node maintains a FIFO queue and also maintains two virtual queues for each neighbor. The current queuing structure of COPE limits the coding opportunities which give higher priority to coded packets. They help to drain the queue at the bottleneck node at a faster rate.In the current COPE system, only one queue is maintained at a node. Cope first dequeues the head packet of the output queue and then checks one by one the head packets of virtual queues to find the appropriate packet to encode. Every time there is a transmission opportunity, the node dequeues the first packet and checks if it can be coded with any other packets currently in its queue. If yes, the packets would be coded together and sent out; otherwise, the native packet will be sent alone. We keep separate virtual queues for each input-output pair and serve them in a round robin manner. This approach helps to increase the coding opportunities; therefore, in a single transmission, we can serve many packets to its neighbors. It reduces number of transmissions, thereby reducing the energy consumed in transmitting the packets. The COPE [7] works as follows: each node snoops all the communications over the wireless medium when a node overhears a packet that it stores for a limited period of time. On the other hand, when a node receives a native packet, it delivers the packet to the higher layers of network stack in addition to overhearing and receiving packets and a node also broadcasts reception reports to inform its neighbors about the packets it possesses.Cope Structure Has the Following Two Limitations. (1) It is necessary to have priority to some special types of packets over data packets. It is also important to set priorities for data packets. FIFO scheduler is trivial to implement and it cannot satisfy the qos requirement. (2) No packet reordering is allowed. When more than one flow is destined to the same next hop, only one virtual queue is maintained for different flows, thereby decreasing the coding opportunities.To avoid the above limitations, a flow oriented queuing structure is maintained where different flows are maintained in different virtual queues irrespective of the next hop. Flow based queuing scheme increases the coding opportunities. Let us consider an example shown in Figure7 which is a part of node 16, node network topology. From Figure 7, flows 1 and 2 are passing through node N and are destined to node O, while flow 3 is also passing through N and destined to other next hop P and then all the packets of flows 1 and 2 are stored in same virtual queue and packets of flow 3 are stored in another virtual queue. Assume that p0+p1 is infeasible and p0+p3 is feasible but  p0+p3 is not allowed since it is a FIFO queue thus losing the coding opportunity. Finally p0 is transmitted alone.Figure 7
Loss of coding opportunities with COPE.In flow based queueing structure, the node maintains different virtual queues for different flows destined to same next hop or different next hop. Since all the packets pass through the nodes in the common path, the number of flows at the dominating node increases; when network coding is applied at these nodes, coding opportunities increases by using flow qs and at the dominating node, the coding opportunities increases further. In Figure8, flows 1, 2, and 3 are maintained in three different virtual queues. q1 contains p1 and p2. q2 contains p3 and q3 contains p0. Now p0+p3 is feasible and is allowed and thus coding opportunity is increased.Figure 8
Flow-based queuing structure.


### 3.4. Energy Efficient Clustering Scheme

It considers high energy nodes as cluster heads. One manner for saving energy in cluster based ad hoc network is all of member nodes except Gateways node can go to sleep mode when they are in idle mode. In this method, only CHs and gateway nodes are active for any communication; in other words, the backbone of the network every time is active to any communication. If a node idle fort1 sec, send a packet to CH for goes to sleep. If this node received an ACK from the CH, it goes to sleep state for t2 seconds. Every node has an internal clock which resets with putting to sleep state. After t2 sec, the node wakes up automatically.Since clusters heads and gateway nodes are alive during the network life, delay time is not very high in our implementation. In our module, we define idle timer which shows the time that node was in idle state and sleep timer which shows the time that node was sleep. We implement the algorithm in routing layer and considered only on member nodes except gateway and cluster head nodes.Many researchers concentrated their studies on CBRP to improve its performance in different factors. The challenges for any routing in MANETs are mobility, resource constraints. Because of these factors, the cluster head may move away from the cluster or die of lack of sufficient energy. So, original cluster head election algorithm of CBRP may not give a better solution to the problem. Hence, this paper presents enhanced algorithm designed to provide a better solution for this problem. Main motivation for this research is to achieve significant impact in the performance of CBRP by improving the cluster stability. This proposed schema improves and develops performance of clustering algorithm than in CBRP. It makes use of Weighted Clustering algorithm (WCA) for electing cluster heads [31] and adopts a combined weight metric that takes some parameters like ideal node degree, transmission power, mobility, and the battery power of the nodes to elect cluster heads. Each node calculates its weight as follows:
(1)Wv=w1·a+w2·b+w3·c+w4·d.Parameter “a” represents degree-difference for every node v. Degree of the node is nothing but number of neighbors of that node (i.e., nodes within its transmission range), and b is sum of the distances with all its neighbors. The running average of the speed for every node till current time T gives a measure of mobility and is denoted by c. d implies how much battery power has been consumed.In (1), the first component, w1·a, helps to avoid MAC layer problems because it is always desirable for a cluster head to handle up to a certain number of nodes. The second component is related to energy consumption because, to communicate for a longer distance, it requires more power. Hence, it would be better if the sum of distances to all neighbors of a cluster head is less. The third component, mobility of the node, a cluster head having less mobility, shows greater improvement on stability of cluster. Last component, d, is the total (cumulative) time in which a node acts as cluster. Battery drainage will be more for cluster heads comparing to cluster members. WCA also provides the flexibility to adjust the weighting factors according to our network requirements.Initially, each node in undecided state calculates its weightWv, then broadcasts its ids along with Wv values. When a node received it, it checks for the node with smallest Wv in its list and sets it as its cluster head and makes itself as cluster member.All nodes broadcast their weights along with ids in Hello message. Before every broadcast, a node should calculate its weight. Whenever a cluster head received a broadcast message from an undecided node, it will reply with a Hello message immediately. After receiving reply from a cluster head, the undecided node changes its status as cluster member. When a node elected as cluster head it checks for next best node (i.e. node with smallestWv) among cluster members and broadcasts it as secondary cluster head to cluster members. So when a cluster head dies for some reason, secondary cluster head takes responsibilities of primary cluster head and improves the cluster stability by avoiding frequent execution of cluster formation algorithm. When two cluster heads move next to each other, then one of them will lose its cluster head position. That is, whenever a cluster head receives a broadcast message from another cluster head, it checks its own weight with that of the other cluster head’s. The one with smaller weight will be cluster head and another one with larger weight makes itself as a cluster member. If any node falls under the transmission range of two cluster heads, then the node joins to the cluster, which is having a cluster head with smallest weight (Wv). Each cluster is identified by its cluster head id.Every node maintains data structures to store information about network. Each node has two tables: Neighbor table and Cluster Adjacency table. Neighbor table contains the information of neighbor node id and status (i.e., cluster head or cluster member), whereas cluster adjacency table consists of neighbor cluster id, ids of the gateway node through which the neighboring cluster head could be reached. Note that there may be many gateways to reach neighbor cluster. These tables are updated periodically by Hello messages.In CBRP, while transmitting data from source to destination, if route error occurred because of some reason, the next node in the path may die or move away from the transmission range of the node which is currently forwarding the packets. The node which found route error will try to salvage the route. Otherwise, it generates route error packet and tells to source. But in our approach, if route error occurred, the current node first checks whether the next node is cluster head or not. If it is a cluster head, then, in the path, the cluster head will be replaced by the secondary cluster head of that cluster.


### 3.5. Network Coding at Cluster Head (CH)

We apply network coding into cluster based routing protocol. Here, we apply network coding at cluster head. The cluster head is selected using the above method called energy efficient clustering (Section3.4). It selects the node as cluster head by verifying its energy levels so it helps to increase the life time of cluster head and it also helps to increase the life time of network. At the cluster head, we implement the above energy efficient COPE protocol (Section 3.3) to increase the coding opportunities.The cluster nodes will forward its packets to the cluster head so that we can have more packets at the CH, which increases coding opportunities and reduces the number of transmissions. To increase life time of CH, we select the CH based on some threshold value on energy levels of node. For example, we consider the node energy levels 50 and 70 out of 100.Algorithm at Node to Process PacketStep
1. If there is a packet to be sent and destination is neighbor then no route discovery.Step
2. If route is present in the routing table then send packet using that route then no route discovery.Step
3. Otherwise, create the route request packet and broadcast it to the cluster head or gate way.Step
4. Perform network coding at CH and broadcast the coded packet to another cluster head or gateway.Step
5. Wait for route reply and update route table after route reply.


### 3.6. Packet Encoding

For packet encoding, we use concept of energy efficient COPE protocol. If neighbour reception table of node u is accurate, then u sends an XOR-ed packetp based on packet probability 0.7 and delay tolerant 0.8. Neighbour v of u should be able to decode p using stored native packets. The coding algorithm should ensure that all next hops of encoded packet can decode their corresponding native packets (see Algorithm 1).Algorithm 1:Packet encoding procedure.
Coding Procedure
{
Pick packet p at the head of the output queue
Createtopology(n);
UpdateNbrRecTable(P);
U = tdpFwdnode(n);
if u is not equal to Fwder(P) return;
if allNbrRecv(P) return;
if(Natives(p))
{ if(Prob(p)>0.4 and DelayTolerance(p)>0.8)
{ if size(p) > 100 bytes then
{which queue = 1
}
else
{which queue = 0
}
ObtainCodeSet(C)
{// Pick packet p at the head of the output queue
C = p
for each remaining packet r in the queue
{  for each neighbor v
{if (cannot decode(p⊕ r)) then
{  goto Continue
}
}
C = C∪ r
p = p⊕ r
Continue
}
return C
}
if (|C| > 1) then
{ sendCodedPkts(C);
}
else if (!Timeout(p)
{  Queue(p,t);
}
else {  send Native(p);
}
}  else
{
for each r = decode(P)
{  TDP_NC(P);
}
}
}Formally, each node maintains the following data structures.(i)
Each node has a FIFO queue of packets to be forwarded that we call the output queue.(ii)
For each neighbour, the node maintains two per neighbour virtual queues, one for small packets (e.g., smaller Than 100 bytes) and the other for large packets. The virtual queues for neighbour A contain pointers to the packets in the output queue whose next hop is A.(iii)
Additionally, the node keeps a hash table, packet info that is keyed on packet-id. For each packet in the output queue, the table indicates the probability of each neighbour having that packet.


### 3.7. Packet Decoding

For packet decoding, each node maintains a packet pool, in which it keeps a copy of each native packet it has received or sent out. The packets are stored in hash table keyed on packet ID. When a coded packet is received, then a node goes through the IDs of native packets one by one and retrieves the corresponding packet from its packet pool. Figure9 shows process of decoding. Here, suppose that source S has to broadcast packets p1,p2,p3,p4 then Receiver R1 extract p1 packet, Receiver R2 extract p3 packet, Receiver R3 extract p2 packet, and Receiver R4 extract p4 packet. Receiver R5 has all packets  p1,p2,p3,p4 and Receiver R6 does not have opportunities to decode the packet.Figure 9
Decoding process.


## 3.1. Proposed System Model

We propose an energy efficient coding-aware routing protocol to efficiently use the energy resources of the nodes. This method uses wireless network coding to reduce the energy consumed in transmitting and receiving the packets at a node. We apply network coding into CBRP protocol to get advantage of clustering and reduce the overhead of broadcasting. Figure6 shows the proposed system model. The proposed system takes the input parameters like nodes, mobility of nodes, initial energy of the nodes, and packets to be sent. It generates the output in terms of the time of simulation, the number of packets delivered to destination, and the remaining energy of the nodes after the simulation.Figure 6
System Model.


## 3.2. Cluster Formation Scheme

We used lowest id [29] concept in our cluster formation scheme. To stop the frequent changes in cluster configuration, least cluster change LCC [30] scheme is used.


## 3.3. Energy Efficient COPE Architecture

This method increases the coding opportunities at the cluster heads. In a COPE based network, a node maintains a FIFO queue and also maintains two virtual queues for each neighbor. The current queuing structure of COPE limits the coding opportunities which give higher priority to coded packets. They help to drain the queue at the bottleneck node at a faster rate.In the current COPE system, only one queue is maintained at a node. Cope first dequeues the head packet of the output queue and then checks one by one the head packets of virtual queues to find the appropriate packet to encode. Every time there is a transmission opportunity, the node dequeues the first packet and checks if it can be coded with any other packets currently in its queue. If yes, the packets would be coded together and sent out; otherwise, the native packet will be sent alone. We keep separate virtual queues for each input-output pair and serve them in a round robin manner. This approach helps to increase the coding opportunities; therefore, in a single transmission, we can serve many packets to its neighbors. It reduces number of transmissions, thereby reducing the energy consumed in transmitting the packets. The COPE [7] works as follows: each node snoops all the communications over the wireless medium when a node overhears a packet that it stores for a limited period of time. On the other hand, when a node receives a native packet, it delivers the packet to the higher layers of network stack in addition to overhearing and receiving packets and a node also broadcasts reception reports to inform its neighbors about the packets it possesses.Cope Structure Has the Following Two Limitations. (1) It is necessary to have priority to some special types of packets over data packets. It is also important to set priorities for data packets. FIFO scheduler is trivial to implement and it cannot satisfy the qos requirement. (2) No packet reordering is allowed. When more than one flow is destined to the same next hop, only one virtual queue is maintained for different flows, thereby decreasing the coding opportunities.To avoid the above limitations, a flow oriented queuing structure is maintained where different flows are maintained in different virtual queues irrespective of the next hop. Flow based queuing scheme increases the coding opportunities. Let us consider an example shown in Figure7 which is a part of node 16, node network topology. From Figure 7, flows 1 and 2 are passing through node N and are destined to node O, while flow 3 is also passing through N and destined to other next hop P and then all the packets of flows 1 and 2 are stored in same virtual queue and packets of flow 3 are stored in another virtual queue. Assume that p0+p1 is infeasible and p0+p3 is feasible but  p0+p3 is not allowed since it is a FIFO queue thus losing the coding opportunity. Finally p0 is transmitted alone.Figure 7
Loss of coding opportunities with COPE.In flow based queueing structure, the node maintains different virtual queues for different flows destined to same next hop or different next hop. Since all the packets pass through the nodes in the common path, the number of flows at the dominating node increases; when network coding is applied at these nodes, coding opportunities increases by using flow qs and at the dominating node, the coding opportunities increases further. In Figure8, flows 1, 2, and 3 are maintained in three different virtual queues. q1 contains p1 and p2. q2 contains p3 and q3 contains p0. Now p0+p3 is feasible and is allowed and thus coding opportunity is increased.Figure 8
Flow-based queuing structure.


## 3.4. Energy Efficient Clustering Scheme

It considers high energy nodes as cluster heads. One manner for saving energy in cluster based ad hoc network is all of member nodes except Gateways node can go to sleep mode when they are in idle mode. In this method, only CHs and gateway nodes are active for any communication; in other words, the backbone of the network every time is active to any communication. If a node idle fort1 sec, send a packet to CH for goes to sleep. If this node received an ACK from the CH, it goes to sleep state for t2 seconds. Every node has an internal clock which resets with putting to sleep state. After t2 sec, the node wakes up automatically.Since clusters heads and gateway nodes are alive during the network life, delay time is not very high in our implementation. In our module, we define idle timer which shows the time that node was in idle state and sleep timer which shows the time that node was sleep. We implement the algorithm in routing layer and considered only on member nodes except gateway and cluster head nodes.Many researchers concentrated their studies on CBRP to improve its performance in different factors. The challenges for any routing in MANETs are mobility, resource constraints. Because of these factors, the cluster head may move away from the cluster or die of lack of sufficient energy. So, original cluster head election algorithm of CBRP may not give a better solution to the problem. Hence, this paper presents enhanced algorithm designed to provide a better solution for this problem. Main motivation for this research is to achieve significant impact in the performance of CBRP by improving the cluster stability. This proposed schema improves and develops performance of clustering algorithm than in CBRP. It makes use of Weighted Clustering algorithm (WCA) for electing cluster heads [31] and adopts a combined weight metric that takes some parameters like ideal node degree, transmission power, mobility, and the battery power of the nodes to elect cluster heads. Each node calculates its weight as follows:
(1)Wv=w1·a+w2·b+w3·c+w4·d.Parameter “a” represents degree-difference for every node v. Degree of the node is nothing but number of neighbors of that node (i.e., nodes within its transmission range), and b is sum of the distances with all its neighbors. The running average of the speed for every node till current time T gives a measure of mobility and is denoted by c. d implies how much battery power has been consumed.In (1), the first component, w1·a, helps to avoid MAC layer problems because it is always desirable for a cluster head to handle up to a certain number of nodes. The second component is related to energy consumption because, to communicate for a longer distance, it requires more power. Hence, it would be better if the sum of distances to all neighbors of a cluster head is less. The third component, mobility of the node, a cluster head having less mobility, shows greater improvement on stability of cluster. Last component, d, is the total (cumulative) time in which a node acts as cluster. Battery drainage will be more for cluster heads comparing to cluster members. WCA also provides the flexibility to adjust the weighting factors according to our network requirements.Initially, each node in undecided state calculates its weightWv, then broadcasts its ids along with Wv values. When a node received it, it checks for the node with smallest Wv in its list and sets it as its cluster head and makes itself as cluster member.All nodes broadcast their weights along with ids in Hello message. Before every broadcast, a node should calculate its weight. Whenever a cluster head received a broadcast message from an undecided node, it will reply with a Hello message immediately. After receiving reply from a cluster head, the undecided node changes its status as cluster member. When a node elected as cluster head it checks for next best node (i.e. node with smallestWv) among cluster members and broadcasts it as secondary cluster head to cluster members. So when a cluster head dies for some reason, secondary cluster head takes responsibilities of primary cluster head and improves the cluster stability by avoiding frequent execution of cluster formation algorithm. When two cluster heads move next to each other, then one of them will lose its cluster head position. That is, whenever a cluster head receives a broadcast message from another cluster head, it checks its own weight with that of the other cluster head’s. The one with smaller weight will be cluster head and another one with larger weight makes itself as a cluster member. If any node falls under the transmission range of two cluster heads, then the node joins to the cluster, which is having a cluster head with smallest weight (Wv). Each cluster is identified by its cluster head id.Every node maintains data structures to store information about network. Each node has two tables: Neighbor table and Cluster Adjacency table. Neighbor table contains the information of neighbor node id and status (i.e., cluster head or cluster member), whereas cluster adjacency table consists of neighbor cluster id, ids of the gateway node through which the neighboring cluster head could be reached. Note that there may be many gateways to reach neighbor cluster. These tables are updated periodically by Hello messages.In CBRP, while transmitting data from source to destination, if route error occurred because of some reason, the next node in the path may die or move away from the transmission range of the node which is currently forwarding the packets. The node which found route error will try to salvage the route. Otherwise, it generates route error packet and tells to source. But in our approach, if route error occurred, the current node first checks whether the next node is cluster head or not. If it is a cluster head, then, in the path, the cluster head will be replaced by the secondary cluster head of that cluster.


## 3.5. Network Coding at Cluster Head (CH)

We apply network coding into cluster based routing protocol. Here, we apply network coding at cluster head. The cluster head is selected using the above method called energy efficient clustering (Section3.4). It selects the node as cluster head by verifying its energy levels so it helps to increase the life time of cluster head and it also helps to increase the life time of network. At the cluster head, we implement the above energy efficient COPE protocol (Section 3.3) to increase the coding opportunities.The cluster nodes will forward its packets to the cluster head so that we can have more packets at the CH, which increases coding opportunities and reduces the number of transmissions. To increase life time of CH, we select the CH based on some threshold value on energy levels of node. For example, we consider the node energy levels 50 and 70 out of 100.Algorithm at Node to Process PacketStep
1. If there is a packet to be sent and destination is neighbor then no route discovery.Step
2. If route is present in the routing table then send packet using that route then no route discovery.Step
3. Otherwise, create the route request packet and broadcast it to the cluster head or gate way.Step
4. Perform network coding at CH and broadcast the coded packet to another cluster head or gateway.Step
5. Wait for route reply and update route table after route reply.


## 3.6. Packet Encoding

For packet encoding, we use concept of energy efficient COPE protocol. If neighbour reception table of node u is accurate, then u sends an XOR-ed packetp based on packet probability 0.7 and delay tolerant 0.8. Neighbour v of u should be able to decode p using stored native packets. The coding algorithm should ensure that all next hops of encoded packet can decode their corresponding native packets (see Algorithm 1).Algorithm 1:Packet encoding procedure.
Coding Procedure
{
Pick packet p at the head of the output queue
Createtopology(n);
UpdateNbrRecTable(P);
U = tdpFwdnode(n);
if u is not equal to Fwder(P) return;
if allNbrRecv(P) return;
if(Natives(p))
{ if(Prob(p)>0.4 and DelayTolerance(p)>0.8)
{ if size(p) > 100 bytes then
{which queue = 1
}
else
{which queue = 0
}
ObtainCodeSet(C)
{// Pick packet p at the head of the output queue
C = p
for each remaining packet r in the queue
{  for each neighbor v
{if (cannot decode(p⊕ r)) then
{  goto Continue
}
}
C = C∪ r
p = p⊕ r
Continue
}
return C
}
if (|C| > 1) then
{ sendCodedPkts(C);
}
else if (!Timeout(p)
{  Queue(p,t);
}
else {  send Native(p);
}
}  else
{
for each r = decode(P)
{  TDP_NC(P);
}
}
}Formally, each node maintains the following data structures.(i)
Each node has a FIFO queue of packets to be forwarded that we call the output queue.(ii)
For each neighbour, the node maintains two per neighbour virtual queues, one for small packets (e.g., smaller Than 100 bytes) and the other for large packets. The virtual queues for neighbour A contain pointers to the packets in the output queue whose next hop is A.(iii)
Additionally, the node keeps a hash table, packet info that is keyed on packet-id. For each packet in the output queue, the table indicates the probability of each neighbour having that packet.


## 3.7. Packet Decoding

For packet decoding, each node maintains a packet pool, in which it keeps a copy of each native packet it has received or sent out. The packets are stored in hash table keyed on packet ID. When a coded packet is received, then a node goes through the IDs of native packets one by one and retrieves the corresponding packet from its packet pool. Figure9 shows process of decoding. Here, suppose that source S has to broadcast packets p1,p2,p3,p4 then Receiver R1 extract p1 packet, Receiver R2 extract p3 packet, Receiver R3 extract p2 packet, and Receiver R4 extract p4 packet. Receiver R5 has all packets  p1,p2,p3,p4 and Receiver R6 does not have opportunities to decode the packet.Figure 9
Decoding process.


## 4. Implementation and Results Analysis

In order to evaluate our proposed method, we use simulation (Table1). Our experiments were conducted using network simulator 2. We consider energy consumption in sending, receiving, idle, and sleep mode. We ran our simulation for different number of nodes. The performance of the proposed ECCRP protocol is compared with that of original CBRP protocol. We simulate CBRP and ECCRP by NS-2. Since we focus on the impact of clustering on energy consumption, we mainly implement the network layer and consider energy consumed. The size of each packet is 128 bytes and transmission rate is 250 kbps. The size of the simulation area is 3 km × 3 km and nodes are deployed randomly in it.Table 1
Simulation parameters.
CBR MAXPKTS
1100
Simulation duration
9000 sec
Background traffic
CBR
Pause time
2 sec
Max connection
16
Broadcast interval
2 sec
Sending rate
0.25
Initial energy of nodes
510
Seed
1.0
Transmit power
600 mw
Packet size
512 bytes
Receiver power
300 mw


### 4.1. Energy Consumption of Nodes

In this section, I consider 30 sources among 60 nodes within the defined area and the number of packets sent between 5 and 60 packets/s. Each node moves with the velocity of 0–20 m/s and the simulation model was executed 20 times. Each node is initialised with 510 J and the simulation was executed for 1000 s. Figure10 illustrates that number of nodes with zero remaining energy versus simulation time. As the simulation time increases the ECCCRP consumes less energy compared to CBRP. At 700 s, the number of nodes with zero remaining energy in the proposed ECCRP algorithm is 6, whereas in the CBRP it is 41 nodes, respectively, as shown in Figure 10. Here we can conclude that the proposed model reduces energy consumption.Figure 10
Nodes energy consumption.


### 4.2. Energy Consumption

The energy consumed is considered proportional to the number of transmissions. Here, we simulated the CBRP protocol and ECCRP protocol. Figure11 represents the average energy consumption in route finding versus number of nodes in network at different nodes. From results, we observed that as the number of nodes increases energy consumption increases and performance of ECCRP is better than that of CBRP algorithm.Figure 11
Energy consumption versus nodes.


### 4.3. Energy Consumption versus Simulation Time

Figure12 illustrates the energy consumed versus simulation time in the network. It is noticed that as the simulation time increases the energy consumption increases and CBRP consumes more energy. Here, the ECCRP consumes less energy as we are performing network coding at the cluster heads to reduce the number of transmissions. So it consumes less energy to transmit the total packets of the network.Figure 12
Energy consumption versus simulation time.


### 4.4. Data Packets Reached to Destination

In order to test how those energy savings can affect the network lifetime when the ECCRP protocol is used, initial energy of 25 Joules was assigned to each node. The simulations were run for 5000 s to ensure that nodes ran out of energy. The number of data packets sent to the destinations successfully is shown in Figure13. It is clear that the number of packets that were successfully delivered to the destination using the ECCRP protocol was high compared to CBRP.Figure 13
Number of data packets reached to destination with ECCRP protocol.


## 4.1. Energy Consumption of Nodes

In this section, I consider 30 sources among 60 nodes within the defined area and the number of packets sent between 5 and 60 packets/s. Each node moves with the velocity of 0–20 m/s and the simulation model was executed 20 times. Each node is initialised with 510 J and the simulation was executed for 1000 s. Figure10 illustrates that number of nodes with zero remaining energy versus simulation time. As the simulation time increases the ECCCRP consumes less energy compared to CBRP. At 700 s, the number of nodes with zero remaining energy in the proposed ECCRP algorithm is 6, whereas in the CBRP it is 41 nodes, respectively, as shown in Figure 10. Here we can conclude that the proposed model reduces energy consumption.Figure 10
Nodes energy consumption.


## 4.2. Energy Consumption

The energy consumed is considered proportional to the number of transmissions. Here, we simulated the CBRP protocol and ECCRP protocol. Figure11 represents the average energy consumption in route finding versus number of nodes in network at different nodes. From results, we observed that as the number of nodes increases energy consumption increases and performance of ECCRP is better than that of CBRP algorithm.Figure 11
Energy consumption versus nodes.


## 4.3. Energy Consumption versus Simulation Time

Figure12 illustrates the energy consumed versus simulation time in the network. It is noticed that as the simulation time increases the energy consumption increases and CBRP consumes more energy. Here, the ECCRP consumes less energy as we are performing network coding at the cluster heads to reduce the number of transmissions. So it consumes less energy to transmit the total packets of the network.Figure 12
Energy consumption versus simulation time.


## 4.4. Data Packets Reached to Destination

In order to test how those energy savings can affect the network lifetime when the ECCRP protocol is used, initial energy of 25 Joules was assigned to each node. The simulations were run for 5000 s to ensure that nodes ran out of energy. The number of data packets sent to the destinations successfully is shown in Figure13. It is clear that the number of packets that were successfully delivered to the destination using the ECCRP protocol was high compared to CBRP.Figure 13
Number of data packets reached to destination with ECCRP protocol.


## 5. Conclusion and Future Work

In this paper, we proposed an energy efficient cluster based routing protocol (ECCRP) technique, designed to improve the performance of CBRP in terms of energy consumption. ECCRP makes use of the Weighted Clustering algorithm. It ensures the election of best cluster head and improves the cluster life time by reducing the energy consumption. Network coding is applied at cluster heads to reduce the number of transmissions and further reduce energy consumption. We also used flow based queue structure while performing coding at intermediate nodes to increase coding opportunities. As a future work, this protocol can be applied to different topologies and environments to verify its performance. We can also consider other cluster based protocols and compare the performance by considering node mobility, traffic, and transmission range.



---

*Source: 351020-2014-10-23.xml*