# Dynamic adjustment strategy of n-Epidemic routing protocol for opportunistic networks: A learning automata approach.

AbstractIn order to improve the energy efficiency of n--Epidemic routing protocol in opportunistic networks, in which a stable end-to-end forwarding path usually does not exist, a novel adjustment strategy for parameter n is proposed using learning atuomata principle. First, nodes dynamically update the average energy level of current environment while moving around. Second, nodes with lower energy level relative to their neighbors take larger n avoiding energy consumption during message replications and vice versa. Third, nodes will only replicate messages to their neighbors when the number of neighbors reaches or exceeds the threshold n. Thus the number of message transmissions is reduced and energy is conserved accordingly. The simulation results show that, n-Epidemic routing protocol with the proposed adjustment method can efficiently reduce and balance energy consumption. Furthermore, the key metric of delivery ratio is improved compared with the original n-Epidemic routing protocol. Obviously the proposed scheme prolongs the network life time because of the equilibrium of energy consumption among nodes.

Keywords: Opportunistic networks, Learning automata, Routing protocol, n-Epidemic, Energy efficiency

1. Introduction

With the rapid development of wireless communication and electrical technology, more and more portable devices such as smart phones, smart watches, activity trackers, smart vehicles, are emerging and widely used in daily life. These devices have continuously evolved with the advancements of technologies and improvements in energy efficiency. So does the opportunistic networks. An opportunistic network is a kind of Mobile Ad hoc Networks (MANETs), but it is different from the traditional MANETs [1]. It is consisted of spatially distributed human carried mobile devices equipped with short range radio communication modules. There is no end to end connection from a source node to a destination node in the opportunistic networks. So a new routing fashion named store-carry-forward is applied to deal with the characteristic of intermittent connectivity in the opportunistic networks. Messages can use intermediate nodes as stepping stones while being transmitted to destinations. To handle the delivery ratio and delivery delay, multiple messages replications exist on different relay nodes [1].

Since these portable mobile devices in opportunistic networks are generally small and usually self-contained (battery-powered), they often use low-capacity batteries. Moreover, it is very difficult for these devices to perform battery recharges while moving. Therefore the battery capability is a major and important factor for these nodes to prolong the network running time and keep connectivity among nodes. Nodes with energy exhausted, or critical low battery reserved, will not be able to take part in message relays in future. This reduction of relay nodes will in turn undermine the whole throughput of the network, especially for time sensitive messages [2-3].

Generally, nodes in opportunistic networks have limited resources including energy and buffer capability. However they are still willing to relay messages to other nodes in the network. There is a risk of energy exhausted when messages are forwarded through replication. How to achieve highest performance under restricted resources is a great challenge in opportunistic networks. As the store-carry-forward style is adopted in the opportunistic networks to deal with the connection interruption, in order to improve the network performance, there are always many replications of each message in the networks. The energy consumption of multiple copies routing policy is higher than the single copy routing policy as well. The distribution of energy consumption of nodes is also not uniform due to the mobility of nodes. Obviously, active nodes need more energy for message replications, and they will become blind to other nodes soon if they are treated as obtuse nodes.

In this paper, we propose a novel Adaptive Adjustment strategy of n- Epidemic Routing (ANER), which introducing a flexible parameter n instead of a fixed n to extend the n-Epidemic routing scheme[4]. The proposed ANER method provides a dynamic and scalable management of the n parameter, with the aim to increase the overall system performance, especially in terms of energy consumption. The proposed scheme involves the current remaining energy of nodes and the parameter n of the n-Epidemic r outing protocol. A node will replicate messages only when the number of neighbors reaches or exceeds a certain threshold n in order to reduce the energy consumption during message transmissions.

The rest sections are organized as follows: Section 2 gives a description of the existing related works on considered routing topic and learning automata theory. Section 3 describes the proposed routing scheme based on the n-Epidemic routing issue. Simulation results and analysis are presented and explained in Section 4. Finally, Section 5 concludes this paper.

2. Related works

To provide a sufficient background for the rest of this paper, we present a brief overview of the replication based routing protocols. Some preliminaries of energy related issues and learning automata are also provided in the following subsections.

2.1 Overview of Routing Protocols

There exist lots of researches on routing protocols in opportunistic networks. The simplest approach is that a source node carries a message all the time until it meets the destination node [5]. This scheme performs only one transmission, and it is very energy efficient. However, it is very inefficiency for message delivery. As the encounters among nodes are random and unpredictable in opportunistic networks, a simple way to perform routing in opportunistic networks is Epidemic routing protocol. The basic idea of Epidemic routing is selecting all current neighbor nodes in the network as relays and trying to replicate all the messages to current neighbors. This means that nodes flood all messages throughout the network [6]. However, this will lead to negative impact on the energy consumption of intermediate nodes, especially for batteries powered nodes. This also affects the performance of network. This is because that a node's energy is mostly consumed on receiving and transmitting messages in real experiments. Nodes with energy exhausted will not be able to relay any messages in future. We name this type of nodes as dead nodes. With the increasing number of dead nodes, the network throughput will decline in turn. There are lots of efforts on energy consumption analysis, and some strategies have been proposed and battery use has been optimized to improve the energy efficiency [7-13]. Most of them employ wakeup schedules or on duty [10-11] strategies. They make a compromise between message delivery and energy consumption in a timely manner. As a consequence, there is an inherent tradeoff between message delivery ratio and energy consumption. Y e t s o m e appropriate transmission opportunities are lost when nodes are sleeping to reserve energy in these schemes.

Some researchers propose an n-Epidemic energy-efficient routing approach in which a node will replicate messages only when it encounters at least n nodes at the same time [4]. That is, message replications only happened between nodes when the number of neighbors reaches a certain threshold n. Thus, nodes cannot send messages as casually as that in the basic Epidemic routing protocol and nodes keep alive all the time. But messages will be transmitted immediately as long as the destination node is in the radio range. In this case, the value of n has to be fixed carefully under many considerations. If the value of n is too high, the probability of having so many nodes within radio range is low, so does the possibility of message replications. If a message cannot be distributed widely, it has low probability to reach the destination. Otherwise, if the value of n is too low, the source node has a high probability of having so many neighbors within its radio range. Thus a high possibility of transmitting messages will occur involving an increasingly fast energy consumption.

An enhancement of Epidemic routing from an energy perspective named EAER is proposed, which extends approach aiming at routing optimization in terms of energy consumption based on n-Epidemic [14]. It provides a dynamic and scalable management of n parameter. The parameter n of n-Epidemic is chosen firstly according to the current energy value and secondly based on the number of neighbor nodes. However, this routing scheme only takes the parameter n from a static and predefined parameter set determined by energy value and node density. It is irrespective of current energy situation of neighbors. The value in the set can also not be changed for different type of nodes. It is obviously that this method is not suitable for all the conditions as the energy value of various nodes is not identical.

In opportunistic networks scenarios, it is impossible to replace or recharge batteries while nodes are moving around. However, nodes are aware of distinct remaining energy levels of themselves, and can get this information from their current neighbors by the inquiry method. Hence, detrimental replication decisions for adjacent nodes can be canceled ahead of schedule for saving energy. There must be a tradeoff between energy conservation and message replication. This paper not only considers energy constraints of mobile nodes, but also takes the current local energy state information of neighbors into account during making message replication decisions.

2.2 Learning Automata

Learning Automata (LA) is an adaptive decision-making mathematical model which operates on an unknown random environment [13]. There is a finite set of actions that could be chosen at every period by a learning automaton. An action probability vector is used to describe the possibility of each action. The environment will evaluate the chosen action and give a reinforcement signal with the probability distribution. Then the automaton updates its action probability vector depending on the reinforcement signal at each cycle, and then evolves to next desired behavior. The mathematical expression of learning automata is called variable structure, and is represented by a quadruple ([alpha], [beta], p, T), in which [alpha] = {[[alpha].sub.1], [[alpha].sub.2], ... [[alpha].sub.r]} represents the action set of the automata, [beta] = {[[beta].sub.1], [[beta].sub.2], ... [[beta].sub.r]} represents the input set, p = {[p.sub.1], [p.sub.2],...[p.sub.r]} denotes the action probability set, and p(n + 1) = T[[alpha](n), [beta](n), p(n)] represents the learning algorithm.

The environment depending on the class of the reinforcement signal [beta] can be classified into P-model, Q-model and S-model. The environment in which the reinforcement signal can only take two binary values 0 and 1 are referred to P-model environment. Another class of the environment allows a finite number of values in the interval [0, 1] can be taken by the reinforcement signal. Such an environment is referred to Q-model environment. In S-model environment, the reinforcement signal lies in the interval [a, b] [15].

Let [[alpha].sub.i] be the action chosen at time n, then the recurrence equation for updating p is defined as:

[p.sub.i] (n + 1) = [p.sub.i] (n) + a(n) x (1 - [p.sub.i] (n))

[p.sub.j](n + 1) = [p.sub.j]( n ) -a(n) x [p.sub.j](n) [for all]j, j[not equal to]i (1)

for favorable responses, and

[p.sub.i](n + 1) = (1-b(n )) x [p.sub.i](n) (2)

[p.sub.j](n +1) = [b/r - 1] + (1 -b (n)) x [p.sub.j](n) [for all]j, j [not equal to] i

for unfavorable ones, where a and b are reward and penalty parameters respectively. If a = b, learning algorithm is called [L.sub.R-P]; if a << b, it is called [L.sub.R [epsilon] P]; if b=0, it is called [L.sub.R-I] [16]. The relationship between the learning automaton and its random environment is shown in Fig. 1.

2.3 Dynamic Irregular Cellular Learning Automata (DICLA)

Cellular Automata (CA) is a dynamic model that is consisted of a lot of identical components. Each component is named as a cell and can effect with the others around it in discrete time. All the cells in the CA follow the same simple rules and operate together to demonstrate complicated behaviors. A finite set of states can be gotten for each cell. Every cell updates its current state synchronously on discrete periods according to the rules.

[FIGURE 1 OMITTED]

To utilize learning automata to adjust the state transition of CA, Cellular Learning Automata (CLA) emerges. CLA is a useful mathematical model for many discrete problems and phenomena, and the characteristics of CA and LA are combined together. The abstract environment of LA is replaced by the cells around LA, and the rule of CA is evolved according to the reinforcement signal. The states of cells mean different actions. On the basis of CLA, the Irregular Cellular Learning Automata (ICLA) and Dynamic Irregular Cellular Learning Automata (DICLA) are developed [17-18]. An ICLA is a CLA which the restriction of rectangular grid structure in traditional CLA is removed. A DICLA is an ICLA with the variable structure according to the given principle. In other words, the adjacency matrix of the underlying graph of the ICLA can be changed over time in DICLA. This dynamic feature and universality are necessary for the applications that cannot be totally modelled with rectangular grids such as Mobile Ad hoc Networks and Wireless Sensor Networks, Opportunistic Networks, web mining, grid computing and data aggregation [19-23]. A DICLA is often shown as an undirected graph in which each vertex represents a cell equipped with a learning automaton. The edge linking two vertexes represents that these two cells are neighbors, and they can interacted with each other by actions which are taken by the cells. Fig. 2 gives a schematic diagram of DICLA.

[FIGURE 2 OMITTED]

A DICLA firstly is a CA in which a learning automaton is assigned to every cell. The learning automaton resided in a particular cell determines its action (state) on the basis of its action probability vector. There is a local rule that the DICLA complied with as the CA does. The neighboring cells of any particular cell constitute the local environment of that cell. The local rule of DICLA and the actions selected by the neighboring cells of any particular cell determine the reinforcement signal to the LA residing in this cell. The local environment of a cell is non-stationary because the action probability vectors of the neighboring cells varied all the time during the evolution of DICLA.

Our proposal focuses on the energy consumption in Epidemic paradigm, and is on the basis of n-Epidemic. It is different from n-Epidemic which only the fixed parameter n of number of neighbors is considered. It is also different from EAER which considers node density and current energy value of node itself to change the parameter n [14]. We introduce the mechanism of LA and define the function f(n) to adjust the parameter n of n-Epidemic routing dynamically. The current value of n for a particular node determined by n = f(n) according to its current energy level and its neighbors using the principle of DICLA. Maximum and minimum thresholds of parameter n are also used to avoid the incomprehensible value. Furthermore, it uses the proportion between the current remain energy and the maximum energy instead of the exact value of current energy. Thus, our proposal can be applied in various scenarios without changing the energy proportion.

Our contributions of this paper are as follows:

* The extension of the n-Epidemic protocol is addressed through the proposal strategy to adjust the variable n. In order to obtain higher performance of energy consumption and message delivery ratio, the parameter n is set dynamically on the basis of remaining energy level of nodes and their neighbors.

* The dynamic mechanism is imported from LA to adjust the parameter n, and DICLA is used to characterize the mobility of nodes in the opportunistic networks. Moreover, it is independent of the movement model.

* Energy consumption is reduced and balanced for the overall system by adjusting parameter n of n-Epidemic according to the average energy level of local environment and residual energy level of a particular node.

* Message delivery ratio is enhanced by the reduction of the node-deactivation phenomenon. This is useful for the connectivity of networks. The life time of network is also prolonged by balancing the energy consumption among nodes.

3. Proposed Routing Protocol

The proposed protocol is based on the n-Epidemic routing protocol mentioned above. However, diversification of energy consumption of nodes and their current neighbors are considered using the DICLA [18] method. It is different from the EAER routing [14] which only the Current Energy Level (CEL) of nodes is taken into account. We use the proportion of remaining energy level instead of the value of remain energy. Firstly, some basic definitions used in our proposed protocol are illustrated. Then, the details of the routing algorithm based on n-Epidemic are described.

3.1 Definitions

Definition 1 (Remaining Energy Level): The remaining energy level is defined as the ratio of the residual energy amount of node at time t to the initial maximum energy amount.

[REL.sub.s] (t) = [CurEnergy.sub.s] (t) / [MaxEnergy.sub.s] (3)

where s denotes a node in the network. REL represents the remaining energy level of node. CurEnergy and MaxEnergy are the current energy amount and maximal energy amount of node s respectively.

Definition 2 (Average Energy Level of Remain): The average energy level of remain is the sum of the residual energy level of the current neighbor nodes divided by the number of nodes, which is the remaining energy level proportional of the number of neighbor nodes.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)

where N is the number of neighbors of node s.

Definition 3 (Current Energy Efficiency Level): The current energy efficiency level is defined as the ratio of remain energy level of node s to the average residual energy level of its neighbors' at current time t.

[[CEL.sub.s] (t) = [[REL.sub.s] (t)/[AEL.sub.s] (t)]] (5)

3.2 Proposed Dynamic Adjustment Strategy of n-Epidemic Routing (ANER)

In the proposed strategy, nodes will decide whether to replicate messages to their neighbors according to the current remain energy level of themselves and their neighbors. For any given node, its neighbors are defined as all nodes within a certain radius of the given node. That is, when a node enters in the transmission range of another node, the wireless connection between them is established. Then it can be considered as a neighbor of the latter. Nodes with higher energy level relative to their neighbors will relay more messages. Correspondingly, nodes with lower energy than their neighbors will decrease message replications by increasing the parameter n. Nodes only replicate messages when the number of their neighbors reaches the threshold which is the same with n-Epidemic. Furthermore, the threshold is dynamically and periodically adjusted to suit the environment while nodes are moving in the networks.

We use the DICLA model to illustrate dynamic topology of opportunistic networks. Each node in the network can be considered as a cell. A node and its current neighbors which can communicate with each other by wireless model are considered as local environment of the cell. The connection establishments and breaks between nodes because of node mobility demonstrate the dynamic variety of neighbors for the given cell.

Thus the AEL for the given node means the current environment and REL is current state of this node. The actions which nodes can take are a0 and a1 represent the reduction and extension scale of parameter n in n-Epidemic routing protocol. The probabilities of these two actions are denoted as [p.sub.r] (reduction) and [p.sub.e] (extension) respectively. The initial values of [p.sub.r] and [p.sub.e] are 0 and 1 accordingly. Each node in the network updates its state according to the fixed time interval [DELTA]T. At the beginning of each interval, node s communicates with their neighbors to get REL value of each neighbor, and compute the [AEL.sub.s] of current local environment. So the current reinforcement signal for current action is generated as Equation (6).

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)

where [[beta].sub.s](t) is the value of reinforcement signal. AEL is average residual energy level of all neighbors of node s, and the REL is current remain energy level of node s.

According to the value of [[beta].sub.s](t), the parameter n which is used in the next cycle is calculated as Equation (7) and Equation (8) respectively.

[fn.sub.s] (t + 1) = [fn.sub.s] (t) + a(t) x [fn.sub.s] (t) (7)

[fn.sub.s] (t +1) = [fn.sub.s] (t) x (1 - b(t)) (8)

where 0<a(t)<1 and 0<b(t)<1 are calculated as Equation (9) and Equation (10) separately.

a(t) = ([REL.sub.s] (t) - [AEL.sub.s] (t))/[AEL.sub.s] (t) (9)

b(t) = 1 - ([AEL.sub.s] (t) - [REL.sub.s] (t))/[AEL.sub.s] (t) (10)

At the beginning of each cycle, nodes in the network update their action probabilities and computer the parameter n. Message replications among nodes are restricted by the number of neighbors as the n-Epidemic dose. As nodes move and message exchanges among nodes, the energy value and neighbors of each node are varied along with the time. If the REL of node s is higher than AEL at current stage, node s should decrease the value n. So the probability of message replication increases. Messages will be spread broadly because node s has much more energy remained than its neighbors'. On the contrary, if the REL of node s is lower than AEL, node s needs increase the parameters n to decrease the transmission to save energy.

The detailed process is described as follows:

* Each node computes its REL according to Equation (3) periodically at the beginning each interval.

* Each node in the network queries the REL from its all current neighbors. Then the AEL of local environment will be calculated complied with Equation (4).

* Each node calculates its reinforcement signal according to Equation (6) on the basis of step 1 and step 2 mentioned above to determine favorable or unfavorable response at this stage.

* Each node tunes the parameter n used in this period based on the Equation (7) or Equation (8) according to the reinforcement signal created in previous step.

* If the parameter n is larger than upper boundary [thr.sub.max], it should be assigned as [thr.sub.max]. Otherwise, if it is lower than [thr.sub.min], it is set as [thr.sub.min].

* If the number of neighbors is equal to or exceed the parameter n, nodes will replicate messages to their neighbors as original Epidemic does. Otherwise, nodes give up this opportunity to replicate messages. Thus, the energy of nodes is saved.

* Nodes update the elapse time of this periods and continue for next cycle.

The ANER algorithm is listed in Table 1.

Table 1. ANER Algorithm Algorithm 1 ANER algorithm Input: contact information, node s, current time t Output: send message list 1. node s calculates its [REL.sub.s](t) at current time t; 2. node s acquire [REL.sub.y](t) from each neighbor node y, and calculates [AEL.sub.s](t) at current time t; 3. node s calculates a(t) and b(t) according to Eq.(9) and Eq.(10); 4. if t-lastupdatetime > [DELTA]T 5. node s compares [REL.sub.s](t) with [AEL.sub.s](t) 6. if([REL.sub.s](t)> [AEL.sub.s](t)) 7. [fn.sub.s](t)= [fn.sub.s](t-1) + a(t) X [fn.sub.s](t-1) 8. else 9. [fn.sub.s](t)= [fn.sub.s](t-1) x (1-b(t)) 10. end if 11. if [fn.sub.s](t) < [thr.sub.min] 12. [fn.sub.s](t) = [thr.sub.min] 13. else if [fn.sub.s](t) > [thr.sub.max] 14. [fn.sub.s](t) = [thr.sub.max] 15. end if 16. lastupdatetime = t 17. end if 18. if current neighbor number > [fn.sub.s](t) 19. send all message to neighbors 20. end if

The time complexity of this algorithm additional to the Epidemic is O(n) in step 2 to compute the AEL, where n is the number of neighbors. The worst case is O(N-1) where N is the number of nodes in the networks. And the storage complexity is a constant to maintain a value of [fn.sub.s](t). It is very suit for large-scale networks for it is very simple and the cost is low.

4. Performance Analysis

In this section, we evaluate the performance of our proposed protocol using ONE (Opportunistic Network Environment) [24-25] simulator under the Random Waypoint movement model. Note that there is no any assumption of movement model in our proposed protocol. It is a model-free strategy and can be applied in all the cases. Comparisons among basic Epidemic, n-Epidemic, EAER and proposed scheme named ANER are made to show the effectiveness in term of energy and routing performance. In order to simplify the description, we call basic Epidemic as Epidemic in this section, and the parameter n of n-Epidemic is fixed as 2 as it is an experiential value in [4]. ANER similar with EAER parameter n ranges from 2 to 7, correspondingly the lower boundary and the upper boundary are fixed as 2 and 7 respectively. We focus on the energy consumption and load balancing among nodes. The routing performance of delivery ratio, overhead ratio and delivery latency are also considered because it is very important in opportunistic networks.

4.1 Simulation Parameter Settings

The area of simulations is restricted to a zone of 800m x 400m. Nodes are arranged randomly in this region and the movement of nodes is followed by Random Waypoint model. Nodes are all identical with the initial energy, speed of movement and buffer capability in our simulations. Messages are generated every 25-35 seconds with the size varied from 500KB to 1MB and TTL of messages is equal to 3600 seconds. The other simulation parameters and energy parameters are listed in Table 2.

Especially, we use the following routing and energy performance metrics in our simulations to display the effectiveness of proposed ANER:

1) Delivery ratio: The delivery ratio is defined as the percentage of delivered messages to the total number of created messages.

2) Overhead ratio: It is a metric to measure the transmission efficiency and defined as the quotient between replicated messages and delivered messages.

3) Delivery latency: The delivery latency is the time from messages generated to the time when they are delivered to the destinations.

4) Average residual energy: It is the average residual energy amount of all the nodes after the simulations are finished.

5) Dead node ratio: The percentage of dead nodes to the number of total nodes after simulations. We name a node whose residual energy achieves almost zero i.e. below 100 units after the completion of simulation as a dead node.

4.2 Performance under Different Node Number

The routing performance and energy performance in different number of nodes are illustrated in Fig. 3 and Fig. 4 respectively. In Fig. 3 (a), we can see that the tendency of message delivery ratio among these compared routing protocols. The message delivery ratio of all the mentioned protocols are declined as the number of nodes increases. This is owing to the fact that the encounter frequently raises with the increasing number of nodes. Thus the message exchanges among nodes increases, and the energy consumption is raised. The energy of nodes will be depleted more quickly. Nodes with energy exhausted cannot transmit any message. Hence, the delivery ratio is declined as the number of nodes raises. The n-Epidemic based protocols including EAER, n-Epidemic (n=2) and our ANER cut down the times of message replications since they will replicate messages only there are at least n neighbors. So they can save energy and perform a longer time to deliver much more messages than Epidemic. Hence, they can get better performance of message delivery ratio than the original Epidemic. The message delivery ratio of ANER and EAER are more outstanding than the n-Epidemic (n=2). This is because that the EAER and ANER can adjust the parameter n dynamically according to the energy condition while n-Epidemic (n=2) using the constant parameter n. Consequently, the message delivery ratio of EAER and ANER are improved. The message delivery ratio of EAER and n-Epidemic (n=2) is slightly higher than that of ANER when the number of nodes is below 30. However, ANER gets higher message delivery ratio than EAER and n-Epidemic (n=2) when the number of nodes achieves 35 and bigger. This is because that there are much more opportunities to reach the threshold n of n-Epidemic (n=2) for the fixed n value with the increasing node density. Thus, the energy consumption is raised and the number of dead nodes is increased. This will cause further descending in delivery ratio. EAER can change the parameter n according to current energy value of node itself, so the message delivery ratio of EAER is higher than the n-Epidemic (n=2). So the delivery ratio of EAER is enhanced compared with n-Epidemic (n=2). However, our ANER can adjust the parameter n dynamically according to the current environment and balance the energy consumption among nodes. Thus, the probability of node death because energy depleted is reduced. Hence, nodes can relay and transmit much more messages to their destinations. The message delivery ratio of ANER is also improved.

Fig. 3 (b) shows that the overhead ratio grows in evidence as the increasing number of nodes in all these compared routing protocols. This is because that encounters among nodes increase when the number of nodes raises. The number of message replications among nodes increases too. However, the buffer capability of all nodes is limited and fixed. In order to receive new messages from peers, old messages must be dropped when the buffer is full. Thus, the overhead ratio increases due to frequently removing messages. The overhead ratio of ANER is the lowest in these four compared routing protocols. This is owing to the fact that ANER adjusts the parameter n according to the energy level of all neighbors. Nodes with lower energy level remained relative to their neighbors increase the parameter n, and perform less replication actions among nodes for energy fairness. Thus, the overhead ratio can be reduced compared with n-Epidemic with fixed parameter n and Epidemic with no energy considered. The overhead ratio of EAER is between those of ANER and n-Epidemic. This is because the parameter n of EAER is not static, so it is superior to n-Epidemic. However, it is inferior to ANER due to the fact that the value of parameter n only depends on the energy value of node itself from local view.

[FIGURE 3 OMITTED]

The delivery latency of these four protocols is shown in Fig. 3 (c). In Fig. 3 (c) we can see that the delivery latency of all compared protocols is descending as the number of nodes increases. This is because that there are much more encounters among nodes and message exchanges become more frequently. So messages are delivered to destinations more easily and the delivery latency is declined. It is obviously that the Epidemic has the lowest delivery latency because that there is no restrictions of message replications in this strategy. Thus messages spread broadly and need less time to be delivered to destinations. The other protocols take the number of neighbors into account and this criterion is easy to be satisfied as the node density increases. So the declivity of delivery latency for these three protocols is larger than Epidemic. The delivery latency of ANER is better than that of EAER because the parameter n is adjusted according to current environment rather than node itself.

According to Fig. 4 (a), as the number of nodes increases in the network, energy consumption increases and the average residual energy of nodes decreases. This is due to the fact that the increasing number of nodes results in the incremental node encounters and message replications. The connections established among nodes become more frequently. Thus, there is much more energy consumed for message exchanging and connections management among nodes. There is no energy left of Epidemic in all cases at the end of the simulations. This is because that message replications are unlimited in Epidemic. The EAER shows the better performance than Epidemic and n-Epidemic which uses the constant parameter n. EAER tunes parameter n according to the current local energy value in order to reduce the energy consumption. However, there is no energy remained when the number of nodes achieves 45 and larger.

[FIGURE 4 OMITTED]

Our proposed protocol ANER has the highest average residual energy among the compared protocols. This is because that we take the average energy of neighbors into account to calculate the parameter n before nodes want to replicate messages. The number of message replications is reduced by adjusting the parameter n actively according to the current energy level of node and its neighbors. This is very helpful to balance the energy consumption among nodes. Thus, the energy harvest is enhanced.

In Fig. 4 (b), it can be observed that as the number of nodes increases, the dead node ratio in the network is also increasing. All the nodes in Epidemic protocols are dead due to lack of energy. The increases of dead node ratio for n-Epidemic and EAER is the higher than our ANER, because they need much more energy during the routing process. This also can be found in Fig. 4. (a). ANER can obtain the best performance of dead node ratio among these protocols, because the energy consumption under this scheme is the least. In the same condition, ANER is more energy efficient than n-Epidemic with the fix n parameter and EAER with the dynamic n parameter from a local view. So it can perform a longer network time than the other three strategies.

4.3 Performance under Different Buffer Size

In this simulation, we vary buffer size from 25MB to 55MB stepping by 5MB. The number of nodes is fixed at 40 and other parameters keep the same with those listed in Table. 2. There are distribution curves of delivery ratio, overhead ratio, delivery latency, average residual energy and dead node ratio in Fig. 5 and Fig. 6 respectively for this scenario.

Fig. 5 (a), Fig. 5 (b) and Fig. 5 (c) show the delivery ratio, overhead ratio and delivery latency with variant buffer size respectively for EAER, n-Epidemic and Epidemic in comparison with ANER. In Fig. 5 (a) we can see that the delivery ratio grows as the buffer increases in all these schemes. This is owing to the fact that nodes can store much more messages with the increase of buffer size. Hence, messages will have more chances to be delivered when nodes encounter. At the same time, the energy consumption is raised for the increase of message replications. EAER, n-Epidemic and ANER with energy considered can obtain higher delivery ratio than the basic Epidemic without energy concern. This is because that energy consumption of Epidemic is faster than the others. Nodes will become blind to others due to energy exhausted and the message delivery probability is greatly reduced. Moreover, our ANER achieves comparatively delivery ratio with EAER and higher delivery ratio than n-Epidemic in all the cases.

Fig. 5 (b) shows that the overhead ratio of these routing protocols presents a downtrend with the increasing buffer size. There is a notable enhancement of n-Epidemic compared with Epidemic. EAER and ANER get additional improvement of n-Epidemic. This is because that the EAER, ANER and n-Epidemic will cancel some message replications when the number of neighbors is less than the parameter n. Furthermore, ANER adjusts the parameter n dynamically and periodically according to the energy level of nodes and neighbors to suit the current environment. The nodes with lower energy level remained reduce replication times to conserve energy through tuning the parameter n to larger. Also it is superior to EAER which only adjust the parameter n on the basis of energy value of node itself. The neighborhoods among nodes are changed all the time since nodes are moving. So ANER can gain the satisfactory result of these compared schemes. This is an efficient way to prevent energy waster excessively for the given node with critical energy left. Therefore, it is very significant for nodes powered by batteries and energy consumption unbalanced among nodes in the opportunistic networks.

From Fig. 5 (c) we can see that, the basic Epidemic obtains the lowest delivery delay among these four protocols. The reason is that energy is not concerned in Epidemic. So messages can be replicated and transferred without any delay. However, ANER, EAER and n-Epidemic will not propagate messages if the number of neighbors cannot achieve the given threshold. So they will lose some opportunities to replicate messages to peers. Consequently, the delivery latency is increased. ANER can get better delivery latency performance than EAER for it suits for the environment adaptively rather than the predefined threshold.

[FIGURE 5 OMITTED]

According to Fig. 6 (a), it is clear that the average residual energy is zero in the case of basic Epidemic and n-Epidemic (n=2) when the simulations are done. The average residual energy of EAER is almost zero too. However, energy is left in the condition of our ANER. This is because that ANER can adjust the parameter n to reduce the energy consumption during the replication phase. Both the constant value of parameter n in n-Epidemic and a number of values of parameter n from predefined set in EAER cannot fit for the changing of neighbors. So the energy consumption in these two schemes is larger than ANER. Thus, ANER is an energy efficient way to conserve energy for the nodes in the opportunistic networks where nodes are moving and the neighbors are changed irregularly.

Correspondingly, the dead node ratio of basic Epidemic and n-Epidemic (n=2) in Fig. 6 (b) are one hundred percent and there is no energy left for nodes in these two schemes. The dead node ratio of EAER is almost 1 too. This means that all nodes using these three schemes are nearly dead because of energy exhausted after simulations. But the dead node ratio of our ANER keeps in a low level. This is because that the parameter n used in ANER is changed according to the average energy level of current environment instead of energy value of node itself. So the energy consumption among nodes can be balanced in our ANER. This will ensure that nodes in the network keep alive as many as possible. And the connectivity is also improved for there are much more nodes keeping alive. It is very important for the circumstance where energy is the critical factor. This is very helpful to deliver messages.

[FIGURE 6 OMITTED]

In a word, the proposed ANER gains enhancement in routing and energy performance compared with the n-Epidemic with constant n and EAER with dynamic n changed along with the fixed energy value. It is of course superior to the original Epidemic. This is due to the fact that ANER adjusts the parameter n dynamically using learning automata principle according to the energy level of nodes and their neighbors'. So the energy of nodes is consumed more accurately than the others. Furthermore, the energy consumption is balanced and reduced compared with the n-Epidemic and EAER. The effectiveness of ANER is illustrated by simulations in the same conditions of different numbers of node and different buffer size. It also can be combined with other policies to make further efforts in the energy harvest for it has no assumptions and can be used in all kinds of circumstances.

5. Conclusions

Energy resource is a very important factor which affects the performance of opportunistic networks. Although the basic Epidemic routing protocol can achieve better delivery performance in ideal environment, it is high energy-consumption. This paper proposed a novel adaptive energy efficient routing scheme on the basis of n-Epidemic routing protocol. It reduces energy consumption of nodes by cutting down the message replication times. In the proposed protocol, nodes adjust the value n of n-Epidemic periodically to balance and reduce energy consumption. It is different from the traditional n-Epidemic which only uses the fixed value of parameter n. It is also different from the enhancement of n-Epidemic named EAER which changes the parameter n according to the absolute value of predefined energy amount and node density. Our proposal employs the DICLA model to depict the dynamic characteristics of opportunistic networks, and a local rule is defined to tune the parameter n of n-Epidemic dynamically according to the energy level of nodes and their neighbors'. The simulation results show that the proposed ANER can reduce and balance energy consumption efficiently. The network lifetime is prolonged accordingly. Also the routing performance such as message delivery ratio and delivery latency are improved because that nodes can live for a longer time and replicate much more messages.

References

[1] Yue Cao and Zhili Sun, "Routing in delay/disruption tolerant networks: A taxonomy, survey and challenges," IEEE Communications Surveys and Tutorials, vol.15, no.2, pp.654-677, April, 2013. Article (CrossRef Link)

[2] Vinicius F.S. Mota, Felipe D. Cunha, Daniel F. Macedo, Jose M.S. Nogueira and Antonio AF. Loureiro, "Protocols, mobility models and tools in opportunistic networks: A survey," Computer Communications, vol.48, pp.5-19, January, 2014. Article (CrossRef Link)

[3] Sanfeng Zhang, Di Huang and Yin Li, "Prediction-Based Routing Methods in Opportunistic Networks," KSII Transactions on Internet and Information Systems, vol.9, no.10, pp.3851-3866, October, 2015. Article (CrossRef Link)

[4] Xiaofeng Lu and Pan Hui, "An energy-efficient n-epidemic routing protocol for delay tolerant networks," in Proc. of IEEE 5th International Conference on Networking, Architecture and Storage (NAS), pp.341-347, July 15-17, 2010. Article (CrossRef Link)

[5] Abraham Martin-Campillo, Jon Crowcroft, EikoYoneki and Ramon Marti, "Evaluating opportunistic networks in disaster scenarios," Journal of Network and Computer Applications, vol.36, no.2, pp. 870-880, February, 2013. Article (CrossRef Link)

[6] Soheil Eshghi, MHR. Khouzani, Saswati Sarkar, Ness B. Shroff and Santosh S. Venkatesh, "Optimal energy-aware epidemic routing in DTNs," IEEE Transactions on Automatic Control, vol.60, no.6, pp.1554-1569, June, 2015. Article (CrossRef Link)

[7] P.Shunmuga Perumal, V.Rhymend Uthariaraj and V.R.Elgin Christo, "WSN Lifetime Analysis: Intelligent UAV and Arc Selection Algorithm for Energy Conservation in Isolated Wireless Sensor Networks," KSII Transactions on Internet and Information Systems, vol.9, no.3, pp.901-920, March, 2015. Article (CrossRef Link)

[8] Yongbo Cheng, Xing You, Pengcheng Fu and Zemei Wang, "An Energy Efficient Algorithm Based on Clustering Formulation and Scheduling for Proportional Fairness in Wireless Sensor Networks," KSII Transactions on Internet and Information Systems, vol.10, no.2, February, 2016. Article (CrossRef Link)

[9] Chaowei Tang, Qian Tan, Yanni Han, Wei An, Haibo Li and Hui Tang, "An Energy Harvesting Aware Routing Algorithm for Hierarchical Clustering Wireless Sensor Networks," KSII Transactions on Internet & Information Systems, vol. 10, no. 2, February, 2016. Article (CrossRef Link)

[10] Wei Gao and Qinghua Li, "Wakeup scheduling for energy-efficient communication in opportunistic mobile networks," in Prof. of 2013 Proceedings IEEE INFOCOM, pp.2058-2066, April 14-17, 2013. Article (CrossRef Link)

[11] Olaf Landsiedel, Euhanna Ghadimi, Simon Duquennoy and Mikael Johansson, "Low power, low delay: opportunistic routing meets duty cycling," in Proc. of ACM/IEEE 11th International Conference on Information Processing in Sensor Networks (IPSN), pp.185-196, April 16-20, 2012. Article (CrossRef Link)

[12] Lichen Zhang, Zhipeng Cai, Junling Lu and Xiaoming Wang, "Mobility-aware routing in delay tolerant networks," Personal and Ubiquitous Computing, vol.19, no.7, pp.1111-1123, July, 2015. Article (CrossRef Link)

[13] Feng Zhang, Xiaoming Wang, Liping Jiang and Lichen Zhang, "Energy Efficient Forwarding Algorithm in Opportunistic Networks," Chinese Journal of Electronics, vol.25, no5, pp.957-964, September, 2016. Article (CrossRef Link)

[14] Floriano De Rango, Salvatore Amelio and Peppino Fazio, "Enhancements of epidemic routing in delay tolerant networks from an energy perspective," in Prof. of IEEE 9th international Wireless communications and mobile computing conference (IWCMC), pp.731-735, July 1-5, 2013. Article (CrossRef Link)

[15] Mohammad Hasanzadeh Mofrad, Sana Sadeghi, Alireza Rezvanian and Mohammad Reza Meybodi, "Cellular edge detection: Combining cellular automata and cellular learning automata," AEU-International Journal of Electronics and Communications, vol.69, no.9, pp.1282-1290, September, 2015. Article (CrossRef Link)

[16] Mehdi Esnaashari and Mohammad Reza Meybodi, "Deployment of a mobile wireless sensor network with k-coverage constraint: a cellular learning automata approach," Wireless networks, vol.19, no.5, pp.945-968, May, 2013. Article (CrossRef Link)

[17] Mehdi Esnaashari and Mohammad Reza Meybodi, "Irregular Cellular Learning Automata," IEEE Transactions on Cybernetics, vol.45, no.8, pp.1622-1632, August, 2015. Article (CrossRef Link)

[18] Mehdi Esnaashari and Mohammad Reza Meybodi, "A cellular learning automata-based deployment strategy for mobile wireless sensor networks," Journal of Parallel and Distributed Computing, vol.71, no.7, pp.988-1001, July, 2011. Article (CrossRef Link)

[19] Hosein Mohamadi, Shaharuddin Salleh, Mohd Norsyarizad Razali and Sara Marouf, "A new learning automata-based approach for maximizing network lifetime in wireless sensor networks with adjustable sensing ranges," Neurocomputing, vol.153, pp.11-19, August, 2015. Article (CrossRef Link)

[20] Feng Zhang, Xiaoming Wang, Lichen Zhang and Peng Li, "An Energy Aware Cellular Learning Automata Based Routing Algorithm for Opportunistic Networks," International Journal of Grid and Distributed Computing, vol.9, no.2, pp. 255-272, February, 2016. Article (CrossRef Link)

[21] M Asemani and Mehdi Esnaashari, "Learning automata based energy efficient data aggregation in wireless sensor networks," Wireless Networks, vol.21, no.6, pp.2035-2053, June, 2015. Article (CrossRef Link)

[22] Qiong Zhang, Hongbin Chen and Feng Zhao, "Energy-efficient joint BS-RS sleep scheduling based on cellular automata in relay-aided cellular networks," in Proc. of IEEE 2015 International Conference on Wireless Communications and Signal Processing (WCSP), pp.1-6, October 15-17, 2015. Article (CrossRef Link)

[23] Milad Mozafari, Mohammad Ebrahim Shiri and Hamid Beigy, "A cooperative learning method based on cellular learning automata and its application in optimization problems," Journal of Computational Science, vol.11, pp.279-288, November, 2015. Article (CrossRef Link)

[24] Ari Keranen, Jorg Ott and Teemu Karkkainen, "The ONE simulator for DTN protocol evaluation," in Proc. of the 2nd international conference on simulation tools and techniques, no. 55, 2009. Article (CrossRef Link)

[25] The ONE. Article (CrossRef Link)

Feng Zhang, Xiaoming Wang (*), Lichen Zhang, Peng Li, Liang Wang and Wangyang Yu

(1) Ministry of Education Key Laboratory for Modern Teaching Technology, Shaanxi Normal University, Xi'an 710119, China

(2) School of Computer Science, Shaanxi Normal University, Xi'an 710062, China

[e-mail: zhangfeng@snnu.edu.cn, wangxm@snnu.edu.cn, zhanglichen@snnu.edu.cn, lipeng@snnu.edu.cn, wangliang@snnu.edu.cn, ywy191@snnu.edu.cn]

(*) Corresponding author: Xiaoming Wang

Received March 24, 2016; revised September 9, 2016; accepted February 12, 2017; published April 30, 2017

[ILLUSTRATION OMITTED]

Feng Zhang received the M.S. degree in computer science from Xidian University, Xi'an, China, in 2007 and the Ph.D. degree from Shaanxi Normal University, Xi'an, China in 201 6. His main research interests include wireless sensor network and opportunistic networks.

[ILLUSTRATION OMITTED]

Xiaoming Wang received the Ph.D. degree in computer science from Northwest University, Xi'an, China, in 2005. He is currently a professor and Ph.D. supervisor in Shaanxi Normal University, Xi'an, China. His main research interests include wireless sensor networks, opportunistic networks.

[ILLUSTRATION OMITTED]

Peng Li received the Ph.D. degree in Computer Applications from Beijing Normal University, Beijing, China, in 2010. He is currently a lecturer in Shaanxi Normal University, Xi'an, China. His main research interests include wireless sensor networks and opportunistic networks.

[ILLUSTRATION OMITTED]

Lichen Zhang received the M.S. degree and Ph.D. degree in computer science from Shaanxi Normal University, Xi'an, China, in 2005 and 2011, respectively. He works as a visiting scholar in Georgia State University, USA, from 2013 to 2014. His main research interests include wireless sensor networks and opportunistic networks.

[ILLUSTRATION OMITTED]

Liang Wang received the B.S. degree in telecommunications engineering and the Ph.D. degree in communication and information systems from Xidian University in 2009 and 2015, respectively. He is currently an Assistant Professor with the Key Laboratory of Modern Teaching Technology, the School of Computer Science, Shaanxi Normal University. His research interests focus on energy efficient resource allocation in wireless communications networks.

[ILLUSTRATION OMITTED]

Wangyang Yu received the M.S. degree from the Shandong University of Science and Technology, Qingdao, China, in 2009, and the Ph.D. degree from Tongji University, Shanghai, China, in 2014. He is currently a Associate Professor with the College of Computer Science, Shaanxi Normal University, Xi'an, China. His research interests include the theory of Petri nets, formal methods in software engineering, and trustworthy software.

Table 2. Simulation parameters settings Parameter Value Map size 800x400[m.sup.2] Transmit Speed 2 Mbps Transmit Range 50meters Nodes Speed 0.5-1.5m/s Buffer Size 40M Number of Nodes 25,30,35.40,45,50,55 Time To Live(TTL) 3600s Nodes movement Random Way point Message Size 500KB-1MB Initial Energy 5000 units Scan Energy 0.1 units Transmit Energy 0.2 units Scan Response Energy 0.1 units

Printer friendly Cite/link Email Feedback | |

Author: | Zhang, Feng; Wang, Xiaoming; Zhang, Lichen; Li, Peng; Wang, Liang; Yu, Wangyang |
---|---|

Publication: | KSII Transactions on Internet and Information Systems |

Article Type: | Report |

Date: | Apr 1, 2017 |

Words: | 8178 |

Previous Article: | Transient multipath routing protocol for low power and lossy networks. |

Next Article: | Particle swarm optimization based on vector Gaussian learning. |

Topics: |