Multicopy energy aware distance and inter-contact delay routing (EDICDR) approach for delay tolerant networks

Published Online May 2019 in MECS

Intermittent connectivity is the main challenge of DTNs. Due to this, the waiting time range may vary from seconds to days. It becomes difficult to establish connection between source and destination in such scenario. Most of the existing protocols depend on the techniques that use previous encounter history of nodes. These techniques produce multiple copies to improve the delivery of messages in DTNs, but introduce high overheads and consume lot of energy in communication. In this work, we aim at reducing energy consumption and message overheads using the inter-contact delay between nodes as well as shortest distance from the destination. Our proposed method considers the history of delay in delivering messages between nodes. This delay and its variance are used to calculate the probability of nodes to determine how many messages a node can deliver to a particular destination. On the basis of probability, we assign the number of copies of a message to the various nodes. We also choose only those nodes as relay nodes that have smaller distance as compared to encountered node from the destination.

Our proposed strategy reduces communication energy and message delivery overheads as it forwards lesser number of copies of a message. The numbers of copies of a message are reduced as it uses only a limited number of relay nodes and forwards more copies of a message to those nodes that have high chance of delivery, i.e. The node with higher delivery probability. An encountered node transfers p * I number of copies of a message to its neighbour node. Here, p represents delivery probability of the neighbour node and I represents existing number of copies at encountered node.

The rest of the paper is organized as follows: Section 2 explains the state-of-the-art techniques in the domain of DTN routing. Our proposed protocol EDICDR is discussed in Section III. We have presented simulation setup and the results in Section IV. Finally, Section V concludes the work presented in the article.

• II.    Related Works

  A great body of work has been devoted to the area of DTN routing in the literature [1-17]. DTN has many routing algorithms, but they hardly consider the energy constraint. Most of the routing algorithms consider encounter information as a measure of relay selection. Few of the routing algorithms consider contact time [912]. In this work we focuses on time based and distance protocols. This category represents the protocols which select relay node on the basis of distance and time. Here time means the interval, duration, intermeeting time or inter-contact time etc. In 2013, Uddin et al. [18] proposed

an Inter-contact routing (ICR) protocol. In this protocol, messages are forwarded based on cost assessment of inter-contact delay and delivery probability. Li et al. [10] proposed SEDUM, is a multi-copy algorithm that uses less number of copies according to optimal tree replication.

Spyropoulos et al. [15] proposed seek-and-focus protocol, which depends on latest encounter time. The initial phase of protocol is seek phase. It changes to focus phase, if a better opportunity for destination node is encountered with the latest encounter time. Conan et al. [19] proposed 2-Multi-Hop (2-MH) by extending the Two-Hop-Relay protocol. Fixed point theory based routing uses average of inter-meeting time. This is a loop free recursive approach to minimize delivery delay. In this paper, they incorporate message forwarding time and region id to evaluate delivery probability of messages.

Here we define some distance based, direction based and map based protocols. Movement of vehicle (MOVE) [20] protocol uses the moving direction of nodes to decide the forwarding node delivery utility. This protocol selects the node as a relay node which moves towards the destination node. As the name suggests, Distance aware epidemic routing (DAER) [21] protocol uses the distance from the destination node as utility metric. This protocol also reduces the replication copies if the node is moving away from the destination. Delay Tolerant Link State Routing (DTLSR) [22] is an extension of classic link state routing. Each node maintains current view of the network and uses Dijkstra algorithm for finding the shortest route. As end-to-end path is not available in DTNs, DTLSR does not use hop count metric for shortest path estimation. It uses expected delay (MEED), introduced by Jones, et al. [23]. This is an approximate amount of time that the route may be available after the calculated delay. DTN hierarchical routing (DHR) [24] depends on the recurrent pattern of stationary node and mobile nodes. But in network like DTN which is highly dynamic it is difficult to maintain time variant hierarchical information. Mobility prediction based adaptive data (MPAD) [25] uses intersection of moving direction and transmission range of sink node. It assumes the stationary sink node. S. Dhurandher et al. [26] proposed a history-based prediction routing (HBPR) which observes the behaviour of nodes. It chooses the relay node by observing the moving direction of nodes using Markov predictors. B. Poonguzharselvi et al. [27] presented a mobile-trace based routing protocol using location information. Location information (direction) helps in making decision to select relay node. Each node uses trace file containing history of movements which is used to trace the direction of nodes. It also has a beacon message facility that contains node ID, location and timestamp to inform other nodes of its presence. In our proposed scheme, we take advantage of both types of approaches (i) time based (ii) distance based.

• III.    Proposed Protocol: Distance and InterContact Delay Routing (EDICDR)

In the EDICDR protocol, we proposed to improve upon the energy consumption by decreasing the number of copies of a message in the network. When nodes encounter each other, they calculate their respective distance from the destination. This calculated distance is used for the selection of relay nodes and delivery probability. This calculated information helps in deciding the number of copies to be forwarded to the relay node.

• A.    Incorporation of Distance Information

In the proposed protocol, shortest distance from the destination information is used for selection of relay nodes [28]. Therefore, by selecting the limited number of relay nodes using distance-information reduces energy consumption. The proposed EDICDR method ensures directional forwarding of messages using the concept of shortest distance from the destination.

Fig.1. Distance Calculation from Destination Node n _d

When a node ns (source node) comes into the range of node na, the protocol evaluates the distance of na from the destination node. If node na having distance smaller than the node ns, is considered as a relay node. It assumes that a node with the smaller distance from destination can be a good forwarder. This ensures that delivery of messages can be carried out by selecting appropriate relay nodes rather than forwarding messages to all encountered nodes. As shown in Figure 1, the distance between nodes is determined using the location information of the destination. The chance of delivery of messages through smaller distance nodes to destination is high. Therefore, only selecting a short distance node as a relay node, results in reduction of the number of copies in the network as well as reduction in the communication energy and overheads.

• B.    Inter-contact Graph

Most of the existing routing protocols use encounter graph in which each vertex represents a node and edge represents an encounter between nodes. Our proposed model also uses inter-contact graph of the network. An inter-contact graph is associated with recurrent pattern. A pattern is recurrent, if nodes encounter frequently within specific period of time. Figure 2 shows the method of relay selection and transfer of copies of a message to relay node. Here da and db shows the distance of node na and nb from the destination respectively.

Fig.2. Flow Chart for Relay Selection and Decision of Number of Copies

Fig.3. Representation of Inter-contact Graph and Recurrent Scenario

C. Delivery Probability Calculation using ICR

The proposed protocol consists of path delay and its variance for the destination node п_д . In Inter-contact routing, these values are reflected as delay distribution parameters. Using these delay distribution parameters, we can measure the cost of a path. This cost estimates the paths using low delay and delay variance.

Message independent path cost is defined as [29]:

cost = d a (n a Tl b | ^ w) + 1.65V2(n a . b ^ w) (1)

This model uses inter-contact graph which represents intermeeting time between nodes, rather than a common encounter graph. In inter-contact graph vertex signifies the encounter between nodes and edges signifies the delay between two nodes. Each edge, n_an_b ^ n_an_c maintained by two values (6(n_an_b ^ n_an_c), ( O"2 ^ n_an_c)), where 6 (n_an_b ^ n_an_c) is the average delay incurred between nodes n_a encounters node n_b and then node n_c , and, (c2 ^ n_an_c) represents associated variance in delay. Inter-contact graph path is symbolized as |^. For example (n_an_b | ^ п_д) is a path from node n_a n b to П д . Path delay is represented as 6 (n_an b | ^ П д ) and path variance as o2(n_an b | ^ П д ) [29]. For example, consider a team of volunteers which takes round of 30 mins in a city and comes back at same point. It passes two stops П ь and n_c approximately in 8 mins distance. According to given scenario, n_a (volunteers) meets П ь and after 8 mins, it meet n_c . When it meets n_c after 22 mins it meets to n_b again because it’s a 30 mins loop for a city. In inter-contact graph as shown in Figure 3, the direct edge from n_an b to n_an_c reflect 8 mins distance and direct edge from n_an_c to n_an b reflect 23 mins distance. In inter-contact graph, delay depends on previous nodes as well as next nodes.

Each vertex (n_an_b) concern with both the routing tables of nodes, i.e. node n_a and node n_b for vertex (^ a ^ b ).

When two nodes n_a and n_b encounter each other, they update the routing table for vertex n_an_b. Let assume that node n_b encounters node n_a . Node n_b revaluates the optimal paths for all possible destinations.

For every neighbour l € S_b , mean delay, variance and cost are computed [29] as follows:

delayl = 6(пьпа ^na^ + db(nbl ^ nw)(2)

varl = ff2(nbna^nbl’) + ffb2(nbl^nw^(3)

cost = delay l + 1.65^varl(4)

Where S _b represents the group of neighbours of n_b.

The estimation of optimal cost is as follows:

l * = arg min i _es ,i _#na cost i              (5)

delay _l * and var_l * are sent by node n_b to node n_a. This works as a mean delay and variance for destination n_wvia n_b . Node n_a updates its routing table with d(n_an_b ^ п_д) = delay_l and o2 (n_an_b ^ п_д) = var_l . Similarly, node n_a updates the routing table of node n_b . After that delivery probability P_c is evaluated separately for all its neighbours n c as follows:

P_c= P{0 <  delay <  TTL /delay >  0}

P c =

/ TTL-delayc

-Jv^c

l—V—detayc'

V₀( ^- detoyc ) ) У ^""k /

where ф(.) represents the related distribution function of normal distribution.

D. Replication decision

We assume that there is some defined number of initial copies of every message. On encounter with intermediate nodes, a node forwards some copies to them according to their delivery probability value. Suppose a node n_a has a message with N_c copies to be transferred to n_d, and it comes in contact with п_ь

Each encountered node п_ь is allocated P(b,(T) * N_c copies and these allotments are deducted from N_c. This continues until N_c runs out. We consider two possibilities for node n , [30]:

Case 1 : N_c finishes out before, we dispense allotment of n , ’s. It refers to the fact that there are satisfactorily superior nodes ahead of п_ь . No copies are forwarded to П ь .

Case 2 : N_c finishes out, we dispense n , ’s allotment. Here, п_ь gets P (b, d) * N_c copies or remainder of N_c if the remainder is lesser than P(b, d) * N_c .

• IV.    Simulation Setup and Results

In this work, we have evaluated the performance of EDICDR for different mobility models and also compared its performance with ICR protocol. The simulation parameters considered for comparative analysis are summarized in Table 1.

Table 1. Simulation Parameters

Parameters	Values
Number of Copies of a	40
message
Number of Nodes	100
Seconds in Time Unit	60 sec
Initial Energy	300J
Scenario End Time	12000 Time Unit
Scenario Number of Host	1
Group
Bluetooth Interface Type	Simple Broadcast Interface
Transmit Speed	250kBps
Buffer Size	5 M
Waiting Time	0.120 Time Unit
Message Sizes	500 kb – 1 MB
World's Size for Movement	4500, 3400
Models
Message TTL	300 minutes (5 hours)

• A.    Evaluation of EDICDR Protocol

This section illustrates the performance of EDICDR protocol. We have evaluated EDICDR protocol with two different mobility models- Map Based Movement (MBM) model and Random Way Movement (RWM) model to find where EDICDR protocol performs better.

Figure 4 shows the performance of EDICDR protocol for both the mobility models. Results show that in RWM most of the nodes consume more energy in comparison of MBM because it does not capture well the recurrence inherent in mobility patterns of nodes.

Fig.4. Comparison of RWM and MBM (EDICDR)

Fig.5. Communication Energy Comparison of ICR and EDICDR

• B.    Comparison of EDICDR and ICR

As discussed in previous section, ICR forward the copies of a message to each of its neighbours according to the probability as calculated. Our scheme focuses on the reduction of communication energy and overheads by reducing the number of copies in the network. We give direction the delivery of packets towards the destination.

• C.    Communication Energy

We evaluate the communication energy of EDICDR for the same simulation parameters as given in Table 1. Figure 5 shows energy consumption by each node in EDICDR. Energy consumption (per byte) is based on the message size that can be calculated as follows:

Receiving/transferring message m given as

E req = m. size * energy per byte        (7)

E_req shows required energy to transfer the message m.

Energy required by each node is much less for EDICDR as compared to ICR. It shows that the direction based forwarding can give better results in energy constrained environment.

• D.    Number of Initial Copies

We have also computed overhead ratio and delivery probability with varying number of initial copies of a message as shown in Figure 6 and 7. In most cases (20, 25, 30, 35 and 45 initial copies), there has been considerable reduction in the overheads as shown in Figure 6. This happens due to the smaller number of copies of the messages exist in the network. Lesser number of copies of the messages reduced significant amount of overheads used in communication.

Figure 7 shows delivery ratio versus initial number of copies. EDICDR have equal or reduced delivery probability. But it can be concluded that this factor is not much affected as forwarding number of copies of a message depends on the probability of encounter node.

It is also observed from Figure 6 that the overhead of EDICDR and ICR increases with the increase in the number of initial copies. In Figure 7 delivery probability of proposed protocol also increases. But after a limited number of copies, it shows the constant delivery probability. This means after a limited number of copies, it only increases overheads in the network and delivery probability of messages does not improve. Therefore, the decision of initial number of copies also demands an attention of researchers.

Number of initial copies ■ EDICDR elCR

Fig.6. Overhead Vs. Initial Number of Copies

Numberof initial copies

■ EDICDR ■ ICR

Fig.7. Delivery Probability Vs. Initial Number of Copies

First, the performance of ICR and EDICDR is compared in terms of overheads for varying node density.

It is observed from the Figure 8 that there is a considerable reduction in the overheads for EDICDR strategies.

Fig.8. Overhead Vs. Number of nodes

Therefore, it can be concluded that in resource constrained networks, our proposed EDICDR protocol performs better. Figure 9 depicts delivery probability for different number of nodes. It can be observed here that the suggested strategies have maintained delivery probability. It has also been observed that in ICR, overheads increases sharply when number of nodes increases. But EDICDR is able to maintain the overheads except for case four with 70 nodes. It means for dense network there may be a good possibility, if we incorporate distance based approaches.

Fig.9. Delivery Probability Vs. Number of nodes

• E.    Buffer Size

In the case of the fourth simulation, we have compared the overheads for variable buffer size as presented in Figure 10 and Figure 11. Similar to the first observation, Figure 10 also shows note-worthy reduction in the overheads for additional strategies for all the cases. The delivery ratio for varying buffer sizes is shown in Figure 11. In accordance with the above-mentioned reasons, the delivery probability of the proposed protocol is lesser or equal as compared to other protocols. It has also been observed that after a limited buffer size both the protocols show constant results because it is possible to store messages for long lime. This decreases the drop rate.

Fig.10. Overhead Vs. Buffer size

Fig.11. Delivery Probability Vs. Buffer Size

Fig.12. Overhead Vs. Message size

Fig.13. Delivery Probability Vs. Message Size

• F.    Message Size

Figure 12 shows relationship between message overheads and message size. It can be clearly seen from the Figure 12 that EDICDR performs better for the varying message size. Figure 13 shows the relation between delivery probability and message size. Results shows EDICDR performs better as compared to ICR.

• V.    Conclusions

Our Simulation results suggest that, smaller number of nodes with higher delivery probability can lead to reduction in the communication energy. Some nodes consume higher energy and receive or transmit lesser number of messages in ICR. This is because these nodes do not use direction towards the destination and thus have lesser chances to deliver the messages. Therefore, in EDICDR, we have sent smaller number of copies of a message to them. This saves the energy used in communication process. Further, in EDICDR overheads are smaller and maintained delivery probability as compared to ICR. But for energy constrained applications like disaster response networks, it should be our primary concern to reduce energy consumption and increase the lifetime of the network. In future, we will attempt to explore other location based schemes which can provide better direction of delivery towards the destination. Further, a better buffer management scheme that improves the delivery of messages can be incorporated in future.