EASER: Energy Aware Scalable and Reactive Replication Protocol for MANETs

Abstract

Mobile ad hoc networks (MANETs) depend on the nodes’ collaboration to communicate and transfer data, and scaling the network size up greatly increases the energy needed to transfer data among far away nodes. To preserve nodes’ energy and increase the network lifetime, data replication protocols have been proposed, which mainly increase data availability by creating nearby local copies of required data. In this work, first we provide a review of energy aware data replication protocols in MANETs. Then, by considering nodes’ energy consumption, we propose EASER: Energy Aware Scalable and rEactive data Replication protocol. Our simulation results and comparison with SCALAR, energy aware ZRP and AODV protocols show that EASER provides improved network lifetime and data accessibility as the network size scales up with considering node energy levels.

1 Introduction

The main characteristic of MANETs is maintaining the network without a fixed infrastructure or controlling station. Nodes can move in any direction independently, and hence the frequent topology changes are not easy to predict [1]. Individual nodes together set up the network in MANET that makes possible to increase the range of communication among nodes, allowing to cover large geographical areas [2].

Two key challenges in MANETs are finding suitable paths for delivering data and increasing network lifetime. The focus toward preserving the energy of the nodes is increasing drastically and becomes a design requirement to reduce energy consumption in the network. Data replication plays a crucial role in MANETs to improve performance, reliability and availability. However, due to limited memory space of nodes, selecting appropriate data for replicating should be done carefully. Although methods such as SAF, DAFN, DCGT [3, 4] and SCALAR [5] have been proposed for increasing data availability, they do not consider the energy consumption aspect.

In this study, we first provide an overview on energy aware data replication protocols in MANETs based on the key characteristics identified. Addressing the findings and building upon our previous work SCALAR [5], we propose EASER: energy aware scalable and reactive data replication protocol. To transmit data in EASER, a virtual backbone method is used to maintain connection among nodes.

Contributions EASER is a distributed approach for data lookup and replication in large scale MANETs. By creating energy aware virtual backbone and taking nodes’ energy levels into account, EASER improves network lifetime and reduces average energy consumption. For creating virtual backbone, unlike [6] which has network partitioning and node unreachability problems, we introduce new rules for ensuring that these problems are avoided in the constructed virtual backbone. To the best of our knowledge, using nodes neighbor information and considering energy to replicate data in the virtual backbone are novel aspects. Through modeling and extensive large scale simulations on JiST/SWANS, we analyze the effect of using energy aware virtual path and data lookup on data accessibility, network lifetime and network traffic. Performance results show that EASER protocol increases the network lifetime and outperforms SCALAR, energy aware ZRP (E-ZRP) and AODV (Ad hoc On demand Distance Vector) [7] protocols in terms of data availability and delay.

The rest of this paper is organized as follows. Section 2 provides our overview of energy aware replication protocols in MANETs. Section 3 presents details of the EASER protocol. Section 4 describes our extensive simulation results and performance evaluation of EASER, followed by conclusions in Sect. 5.

2 Related Work

Two fundamental characteristics of MANETs are mobility and multi-hop communications [8]. Due to mobility, nodes can easily go out of range of communication and lose access to the network. As a result, they cannot act as routers to deliver data in multi-hop manner. Data replication involves copying similar data in multiple nodes which is a fundamental technique used in distributed systems (Table 1).

Table 1 Comparison of energy aware replication methods

Criteria for comparing different energy aware methods There exist several techniques for data replication, but not all consider energy awareness when replicating data [9, 10]. In Table 2, we compare different data replication techniques which consider energy consumption, through the following criteria. Remaining power criterion represents whether a method uses power of nodes or not. Read-only parameter indicates whether the replication technique is performed for read-only data or not. Localized this criterion determines that each node according to information from constant hop count of neighbors decide to replicate data. Energy balancing criterion indicates whether a replication protocol can manage the energy usage among nodes or not. Access frequency refers to the fact whether a method considers access frequency when replicating data or not.

Table 2 Simulation parameters

Energy aware data replication protocols The energy aware WEA-B protocol [4] takes nodes’ energy levels into account when replicating data. WEA-B method uses access frequencies of nearby nodes and protects the nodes with low amount of energy to be accessed by distant nodes, so that it achieves both data availability and energy awareness [11].

A combination of pull-based and push-based data delivery methods were proposed in Expanding Ring Replication (ERR) [12]. In the push based method, the server frequently sends data and the client, by checking the channel, can access data, in contrast in the pull-based method the mobile node queries the server for required data. ERR assumes that the advertisement messages should be broadcast just for the one hop neighbors in order to prevent a flooding all nodes and their responses. As a result, the energy consumed by each node as well as the network traffic load would be decreased.

EENMDRA is a data replication protocol designed for energy efficiency that uses method of [11] for replicating data and predicts node mobility to replicate data before node may go out of communication range. In EENMDRA, after determination of node mobility, nodes’ energy consumption and replicating data, the algorithm aims to make balance among data accessibility, delay and energy consumption [13].

Power-Aware Dynamic Adaptive Replica Allocation Algorithm (PADARA) that makes use of the locality of data access was proposed in [14]. The replica allocation mechanism is balanced periodically to decrease the power consumption, and as a result, increase the network lifetime. According to the number of read and write requests, the total power consumption was calculated and after that by using a heuristic algorithm the suboptimal replica allocation scheme can be found.

ZRP protocol [18] does not consider node energy levels, and its energy aware extension E-ZRP [16] was proposed as a mechanism for decreasing unnecessary transmission range, and it aims at preserving nodes’ energy and extending the network lifetime. However, it has the tradeoff between power saving and reducing transmission delay.

A method that frequently checks for the residual energy of the node which holds replica and calculates the node lifetime is provided in [17]. If the node lifetime falls below a predetermined value, replica will be redistributed to the node with the highest energy. Node lifetime is calculated based on the current and previous energy consumption of the node.

Using information about nodes’ remaining energy, our approach EASER constructs a virtual backbone, and aims at balancing the energy among the nodes and increasing the network lifetime. We assume that replicated data is read-only and consistency of data in different replicas is not considered. Furthermore, node energy levels, data access frequencies and nodes’ neighbors information are utilized when replicating data.

3 EASER: Energy Aware Scalable and Reactive Replication

In this section, we provide details of the EASER protocol, namely CDS construction algorithm, distributed implementation, and reactive and energy aware replication mechanism.

3.1 CDS Construction Algorithm

A subset of the graph is a dominating set (DS) if each node in the graph is either in the subset or adjacent to the one node which is in the subset. If all the nodes in the subset (DS) are connected to each other, then the subset is called connected dominating set (CDS). It has the property that every node in the network has the distance at most one-hop from a backbone. Nodes in the backbone responsible for data routing are called dominator nodes [19].

Our approach to create an energy aware virtual backbone is inspired by [6, 20, 21]. We applied marking method in order to construct the CDS. Each node in a CDS graph, $G=(V,E)$ by using m(p) which is a marker of node $p \in V$, is marked either as true(marked) or false(unmarked). Initially, all nodes are marked as false. We use approach in [6] for CDS construction, and we also add rules to ensure CDS connectivity in the case of mobile nodes. The algorithm has the following properties:

• Every node requires local single hop information about the network topology. N(p) is the set of the all neighbor of node p. The set which involves node p and its neighbors is represented by N[p] and defined as $N[p] = N(p) \cup \{p\}$.

• The resulting set of nodes forms a DS, and every node in the set is connected to one or more dominator nodes.

• All other non-dominator nodes are directly connected to one or more nodes in the resulting set.

For each node p there is a unique number, un(p), and an initial energy level, $eng\_lv(p)$. V$^\prime$ is the set of graph vertices in V which are marked True. We suppose that the graph $G_{sub}$ is the subgraph of G made by $V^\prime$, i.e., $G_{sub}=G[V^\prime ]$ [6]. The heuristic rules for reducing the size of DS generated through the marking process are:

Rule 1 Assume two marked nodes p and q in $G_{sub}$. The marker of p is changed to false if one of the following conditions holds:

• 1. $N[p] \subseteq N[q]$ in G and $eng\_{lv}(p) < eng\_{lv}(q)$

• 2. $N[p] \subseteq N[q]$ in G and $un(p)<un(q)$ when $eng\_{lv}(p) = eng\_{lv}(q)$

Rule 1 specifies that when all neighbors of p is covered by q, and remaining energy of p is smaller than q, p can be deleted from $G_{sub}$. Also if both of them have equal energy levels, if un(p) is less than un(q) then p can be deleted from $G_{sub}$.

Rule 2 Suppose that q and r are two nodes which are marked. Also these nodes are adjacent to marked node p in $G_{sub}$. If one of the following conditions are satisfied then the algorithm set the marker of p to the false.

• 1. $N(p)\subseteq N(q)\cup N(r)$, but $N(q)\not \subseteq N(p)\cup N(r)$ and $N(r)\not \subseteq N(q)\cup N(p)$ in G

• 2. $N(p) \subseteq N(q) \cup N(r), and N(q) \subseteq N(p) \cup N(r)$ but $N(r) \not \subseteq N(q) \cup N(p)$ in G; and satisfying any of following a or b conditions:

  • a. $eng\_{lv}(p) < eng\_{lv}(q)$, or

  • b. $eng\_{lv}(p) = eng\_{lv}(q)$ and $un(p) < un(q)$

• 3. $N(p) \subseteq N(q) \cup N(r), N(q) \subseteq N(p) \cup N(r)$ and $N(r) \subseteq N(q) \cup N(p)$ in G; and satisfying any of following a, b or c conditions:

  • a. $eng\_{lv}(p) < eng\_{lv}(q)$, and $eng\_{lv}(p) < eng\_{lv}(r)$

  • b. $eng\_{lv}(p) = eng\_{lv}(q) < eng\_{lv}(r)$ and $un(p) < un(q)$

  • c. $eng\_{lv}(p) = eng\_{lv}(q) = eng\_{lv}(r)$ and $un(p) = min\{ un(p), un(q), un(r)\}$

Rule 2 shows that if closed neighbors of the p is supported by the union of q and r in rule 2.1, if q and r are not covered by the union of two other node, then node p will be deleted from $G_{sub}$. Rule 2.2 indicates that, if r is not supported by union of q and p, but p is supported by the union of q and r, and q is supported by the union of p and r, and also if the energy level of p is less than that of q or the un(p) is less than un(q) when their energy levels are equal then node p can be deleted from $G_{sub}$. Rule 2.3 specifies that, when all the neighbors of q, p and r is supported by the union of the two other, and any of the following condition are satisfied in that case p can be deleted from $G_{sub}$. The conditions are: a. if energy level of p is the smallest among q and r; or b. if the energy level of p and q are equal but less than of r, and the un(p) is less than un(q); or c. the energy levels of q, p, and r are equal and unique number of p is the smallest among q, p, and r [6, 20].

3.2 Distributed Implementation

CDS construction algorithm is executed periodically to maintain the backbone among nodes considering the random mobility of nodes. However, we notice that the CDS construction method of [6, 20] cannot always create a connected DS and dominator nodes may become unconnected to each other. As a result, nodes in the network may become unreachable through the dominating set and the network becomes partitioned that reduces data accessibility drastically. We observed that the problems encountered in [6] arise from the fact that nodes trust each other (for not going unmarked), and go to an unmarked state simultaneously. That is, by concurrent execution of the algorithm at each node, in some cases node p checks its dominator neighbors q and r, and finds out that their open neighbors cover all neighbors of p. So p trusts q and r, and changes its status to false (pruning phase). At the same time, q checks the neighbors of p and r, and finds that they cover its neighbors, therefore q also decides to change its status to false. This can also happen for node r. The update in status of q and r to false causes the node or its neighbors to become unreachable. Therefore, to solve this problem we modified CDS construction algorithm as follows:

• 1. When node p runs the algorithm, if it returns true for two randomly picked dominator neighbors (q and r), node p may be pruned.

• 2. Before pruning, check if the nodes trusted (q and r) will be pruned. Pick another dominator node $d_1$ and run the algorithm for (p, q, $d_1$) and (p, r, $d_1$). In addition, pick another node $d_2$ and run the algorithm for (q, $d_1$, $d_2$) and (p, $d_1$, $d_2$). These checks contain all the results about q or r that can be calculated from node p. If any of these checks returns true it means that q or r will be pruned.

3.3 Reactive and Energy Aware Data Replication Mechanism

We use a reactive replication method, that is a replication decision will be done when a data is received by a node. In the previous work SCALAR [5], the cost function uses request frequency history and distance (number of hops) information to the data owner. In order to replicate data considering the node energy information, we use an enhanced cost function which not only considers access frequency and energy level, but also considers access frequency of the neighbors. We assume that replicated data is read-only and consistency of data in different replicas is not considered. Our energy aware replica allocation method in the virtual backbone is inspired by [4]. The assumptions about nodes and data items are the following:

• Host nodes $(H_1, H_2, H_3,\dots , H_n)$ move based on random waypoint mobility.

• Every data item $(d_1, d_2, d_3,\ldots , d_n)$ stores in a certain node and is read-only.

The following describes the cost function used when host $H_a$ requests access to data item $d_{fresh}$ which does not belong to itself.

(1) If $H_i$ has enough memory space it replicates $d_{fresh}$. Otherwise, $H_i$ sends data request to nodes within $h({\ge }1)$ hops. The request involves host id of $H_i$ and all data entry stored by $H_i$ and $d_{fresh}$.

(2) When a node, $H_c$, get a request, it sends a response to $H_a$. The response message contains the id of $H_a$ and $H_c$, access frequencies of $H_c$ to data, and flags which shows $H_c$ stored the data specified in the message.

(3) If $H_a$ receives response message, it calculates $\varDelta _{a,k\rightarrow fresh}$, for each data item held by $H_a$ with

$$\begin{aligned} \varDelta _{a,k\rightarrow fresh} = \delta ({\alpha _{a,fresh}} - {\alpha _{a,k}}) + (\frac{ E_i}{E_{init}}) {\lambda (\frac{A'_{a,fresh}}{S_{a,fresh+1}}} - {\frac{A'_{a,k}}{S_{a,k}})} \end{aligned}$$

(1)

Here, data in node memory is represented by k. The total access to $d_k$ from node $H_a$ is $\alpha _{a,k}$. The value of $E_i$ and $E_{init}$ are current and initial amounts of battery power of $H_a$. Total access frequencies to $d_{k}$ from one hop neighbors of node $H_a$ is shown by $A_{a,k}$. The value for $S_{a,k}$ is the whole $d_{k}$ in one hop neighbors. By using $\delta$ and $\lambda$ as weights it is possible to give priority to access frequencies from the node or its neighbors. The value of $\varDelta _{a,k\rightarrow fresh}$ represents the changes in the total data accesses when replacing the $d_{k}$ with $d_{fresh}$ [11].

(4) Data item $d_k$ with highest value of $\varDelta _{a,k\rightarrow new}$ is choosen by $H_a$ to replace with $d_{fresh}$. By decreasing the node power the value in second term of Eq. 1 will be decreased. Therefore, in this case mobile node give priority to its access frequency.

4 Simulations and Performance Results

We implemented EASER protocol on JiST/SWANS Scalable Wireless Ad hoc Network Simulator [22]. Our simulation parameters are presented in Table 2. We analyze the performance of EASER and compare it with SCALAR, E-ZRP and AODV protocols.

ZRP protocol [15] aims to make use of the advantages of two routing methods, namely proactive and reactive routing. However, ZRP does not take the energy level of nodes into consideration and packets are forwarded with full power without considering the nodes position inside the zone. In E-ZRP [16], a method for decreasing unnecessary transmission range was proposed to preserve nodes’ energy. According to Friis free-space equation, $P_r=\frac{P_t}{(4 \pi d)^2}$, where $P_r$ is the received power and will be significantly reduced by increasing distance d between nodes. E-ZRP considers that when node power reaches 50 % of its initial energy, it halves the transmission power $P_t$. By decreasing nodes energy, not only nodes reduce their transmission power to keep batterys capacity but also they do not disturb communication among nodes.

4.1 Performance Metrics

The following metrics are used to analyze system performance. Success ratio is the ratio of the number of successful access requests to the number of all access requests. Average remaining energy metric shows the ratio of total remaining energy of all nodes to the number of nodes. Network lifetime refers to the time at which the first network node runs out of energy.

4.2 Analysis Results

Network density is defined as the expected number of a node’s neighbors in the network [2]. To compare different methods, we consider different values for density i.e. 1, 3, 5. Figure 1 shows the success ratio of EASER, AODV, SCALAR and E-ZRP for different network densities, where EASER outperforms the other methods due to its efficient replication mechanism. Figure 2 shows that with a fixed density the success ratio of EASER has the largest value, especially when the network size scales up.

Average energy and network lifetime Nodes in a virtual path collaborate in several send and receive operations and their power will be depleted more quickly. If the energy level of a node is smaller than the other nodes’ energy level, it will be replaced with a new one. As shown in Fig. 3, EASER achieves the highest average energy compared to other protocols. Furthermore, it also helps improving the network lifetime. As given in Fig. 4, there is no occurrence of node death, up to 100 nodes during the simulation time, but after that by increasing the number of nodes the network lifetime for AODV plunges drastically. In EASER, the network lifetime is improved significantly and no death of nodes occurs during the simulation time.

Fig. 1

Effect of network density

Fig. 2

Data accessibility

Fig. 3

Average energy

Fig. 4

Network lifetime

Network traffic Nodes spend energy during send and receive processes. By decreasing network traffic, it would be possible to save nodes’ energy. The network traffic is also an important criterion for the power aware method. According to the number of sent and received packets as shown in Figs. 5 and 6, the highest number of sent and received packets are observed in AODV, and the smallest number of packet transmissions are observed in EASER.

Fig. 5

Number of sent packets

Fig. 6

Number of received packets

5 Conclusions

In this study, we provide a review of energy aware data replication protocols in MANETs. By addressing the findings in existing mechanisms and considering nodes energy levels when constructing virtual backbone, we propose EASER: energy aware scalable and reactive data replication protocol. The aim is to reduce the number of nodes participating in lookup and replication in order to preserve network energy. Our simulation results and comparison with SCALAR, E-ZRP and AODV protocols show that EASER provides improved network lifetime and data accessibility in several network scenarios investigated.