An Effective Find and Replicate Strategy for Data Communication in Intermittently Connected Wireless Ad Hoc and Sensor Networks

Abstract

ICWASNs are a kind of wireless networks where, due to mobility of nodes and lack of connectivity, there may be frequent disconnections among the nodes. Hence, the routing path from the source to destination will not be available always. It is proven that, in these networks, messages are replicated multiple times in order to withstand the maximum delay and to achieve high throughput. But these multiple replication-based protocols result in an increase in network overhead and high resource consumption because of uncontrolled replication. Previous works in ICWASNs assume that networks will always have multiple partitions, and each message will be routed using store and forward mechanism. If source and destination are connected, then it is not needed to replicate multiple copies and waste the resources. We introduce a new simple scheme which applies single-copy routing if destination is available; else it switches to store and forward routing. The proposed system tries to reduce the average number of message replications while increasing the throughput.

1. Introduction

Basically, a mobile ad hoc network (MANET) is an infrastructureless and independent collection of various mobile nodes where the topology of network changes dynamically and unpredictably. MANET well complement infrastructure-based wireless networks and allows mobile node users to obtain access to interact directly with each other even when they are outside the coverage area of any cellular networks or Wi-Fi. Similarly, MANETs enable communication between vehicles, sensors, laptops, and other mobile equipment without the need to deploy a fixed infrastructure network. Plenty of dedicated routing protocols have been proposed to establish and maintain connectivity between communicating nodes in such dynamic environments.

Challenged networks or intermittently connected wireless ad hoc and sensor networks (ICWASNs) arise from MANETs primarily as a result of node mobility but may also come into being as a result of disconnections due to power management or interference. As a result, the network becomes partitioned. Unfortunately, with current ad hoc routing protocols, packets will not be routed if a disconnection exists between the source and the destination when a message is originated. Certain applications, such as real-time, constant bit rate communication may require a connected path for meaningful communication. However, a number of other application classes benefit from the eventual and timely delivery of messages, especially in the case where frequent and numerous network partitions would prevent messages from ever being delivered end to end [1]. Examples of such networks include terrestrial mobile networks, exotic media networks, military ad hoc networks, and other sensor networks. These challenged networks are characterized by high latency, bandwidth limitations, high error probability, node longevity, or path stability that are substantially worse than is typical of today's TCP/IP-based networks [2–4].

Existing TCP/IP-based ad hoc network protocols could not be utilized for these challenged networks since they operate on the basis of providing end-to-end inter-process communication with different link layer techniques. Numbers of assumptions are made regarding the overall performance of the underlying links so as to achieve proper operation, there must be an association between a data source and its destination, the round trip time between any two node pairs in the network is not too large, and the link failure probability is small. Unfortunately, challenged networks which may violate one or more of these assumptions; hence, they may not be well served by the current end-to-end TCP/IP model.

When a direct contact routing approach is applied to this type of network, the message delivery delay is very high [5], and then they get dropped by the network if delay increases further. Since many of the wireless nodes are mobile nodes they may increase the delivery ratio in wireless environment [6]. Hence, by using the mobility property of the nodes, there are numbers of routing protocols proposed for these partially connected networks, and they are divided into replication based and knowledge based [7]. Replication-based protocols create multiple copies of a message. In order to maximize the probability of a message successfully transferred is to replicate as many copies of the message with the belief that at least one of the copies may reach its destination as said in [1]. In this flooding based protocol, each node tries to forward each message to every one of its nearby nodes except the source node. This results in every message being duplicated into all reachable parts of the network.

The other kind of protocols are knowledge-based [8]. Here, some knowledge about the network is required but they consume fewer resources compared to flooding strategies. In location-based routing stated in [9], a node requires location coordinates of its own, destination coordinates and the coordinates of the potential next hops. With these, a node can easily compute the distance function and determine where the message should be sent.

In this paper, we focus on studying effective find and replication (FIRE) strategy in realistic network environments with limited resources like bandwidth and buffer. The existing routing protocols are proposed under the assumption of always the source and destination are disconnected. But it is not true with challenged networks. Due to mobility and other reasons, the source and destination may be connected for some of the time and may go disconnected for some other time. Therefore, the proposed work makes use of the connections whenever possible. It will try to establish a connection from source to destination first. If the destination is not available for a specified delay then the source will switch to store and forward switching. Hence, at last the average number of copies replicated will be reduced based on the destinations availability.

2. Related Work

Ad hoc network nodes are often disconnected from the network because of their resource constraints like low battery or any link failure or due to mobility of nodes. Routing in these partially connected or disconnected networks will not succeed if it uses any of the table driven or on-demand ad hoc routing protocols since they expect the availability of the destination. But for the partially disconnected networks, the destination may be unreachable or not currently available by that time. If this is the case for the messages in MANET, then those messages will be dropped after some retransmissions. But, soon different links may come up and down owing to mobility of different nodes. It then indicates after some time interval the sequence of connectivity graphs indicating an end-to-end path may exist overtime. It implies that a message could be sent over an existing link, get stored at the next node until another node in the path comes up, and so forth, until it reaches its destination. This is referred as mobility-assisted routing which is different from that of the existing routing techniques.

The first routing method which was proposed for partially connected network is the epidemic routing is one of the mobility-assisted routing which was introduced as a different approach for partially disconnected ad hoc networks [1]. In this, random pairwise exchanges of messages occur among adjacent mobile nodes. The movement which is natural in the mobile nodes themselves made use of in assisting the distribution of the data when a network is connected partially. The epidemic algorithm is purely flooding-based, and it occupies more system bandwidth, node buffer space and energy consumption for the eventual delivery of a message. The hop count is to be fixed based on the message priority and the acknowledge mechanism is optional here.

The epidemic routing results in massive duplication of messages. Therefore, in order to avoid wasting of resources, the other one approach that has shown good potential in this context is the controlled flooding or optimized epidemic [7]. Here, the number of messages is limited by time to live, kill time, forward transmission count, and so forth. Efficient buffer management schemes are introduced in order to properly fill the buffers of all the nodes [10, 11]. Other approach is the spraying-based routing. In spraying method [12–14], a small preset amount of copies are generated and distributed to different relay nodes, each of which then buffers its copy until it meets the destination. By routing multiple numbers of copies independently, these protocols create possibility to travel around the network efficiently, while keeping resource consumption per message low. However, the shortcomings in these works are if mobility of nodes restricted to a small area, none of the messages might ever see the destination in case of spay and wait routing method. But spray and focus will overcome this difficulty.

In spray and focus, during spray phase, the preset amount of copies is thrown as like in spray and wait. During focus phase, a message will be transferred to next relay node when it has utility value which is greater than its own. Utility function can be taken as like the age of last encounter time of nodes. Another variation in spraying phase can be binary spraying or source spraying. In source spraying, source only sprays the copies. The relay node which got the copy from source will enter into wait phase or focus phase. But in binary spraying, source will copy half of the copies to a relay node. The relay node again copies the half of those copies to another relay node. When the copy becomes one, the relay nodes copy only to the destination and enter into wait or focus phase. Another kind of spraying called mutliperiod spraying will reduce again the fixed number of copies to some extent [15]. In this, it will initially spray smaller number of copies which was very less than that of the existing spraying schemes. If acknowledgement comes from the destination, then it will stop spraying further. This periodical spraying can be done with two or three periods. But the disadvantage of spraying method is that it will find for optimal distribution strategy for fixed number of copies in spray phase.

In [16], it discusses the issue of disconnected nodes and gives the solution for sending messages to nodes in that environment. But the limitation here is that the movement information of nodes and trajectories should be known. Another one protocol that limits the flooding is the MaxProp [17]. MaxProp consists of an ordered-queue based on the destination of every message, ordered by the predicted likelihood of an upcoming transitive path to that destination. When any two nodes meet, they first exchange their predicted likelihood vectors of node meetings. Ideally, every node has the information of up-to-date vector for likelihood from every other node. The shortest path can be computed by a node through a depth-first search. Here the path weights indicate the probability that the link will not occur. Then these path weights are added to determine the entire cost of the path. Computation is done over all of the possible paths to the destinations desired and also for all the destinations of messages currently being held. The least total weight path is selected as the cost for that particular message destination. The messages are then listed by destination costs and then transmitted or dropped in that order for buffer management.

MaxProb has the advantages measuring the likelihood of the nodes and then transferring. But the overhead involved is that the path cost is updated for a destination based on its intermediary's likelihood also. In addition to the likelihood, the priority is given for the messages which are having a less hop count compared with some threshold value. But the hop count will not give a correct measure for a control of duplicated messages.

The basic idea in [18] is making each mobile node learn the random mobility parameters and similar pattern mobile nodes can join together with other nodes. The similar mobility nodes form a cluster. All the nodes in a cluster can then share their resources for overhead decrease and also for load balancing so as to improve the overall network performance. Contact probabilities are used to form a set of functions including Sync(), Leave(), and Join(). These are used for cluster formation and gateway selection. At last, the gateway nodes exchange network information and then routes.

Due to the discontinuous connections in intermittently connected networks, there are errors in the estimated contact probability of nodes; convergence and stability are the major challenges here. An exponentially weighted moving average scheme is employed for the contact probabilities for on-line updating with its mean shown for converging to the true contact probability.

In [19], they aim to store the data inside the network for maximum of the time, by spreading the data items from lower energy nodes to higher energy nodes. Another novel relaying scheme is that probabilistically determines a vehicle's suitability to carry messages [20]. Hence, messages are released to a current vehicle if and only if the current vehicle contributes to make mean transit delay. It utilizes the release probability which is quantifying the contribution of a vehicle in a present opportunity to the minimization of the overall mean message transit delay.

The paper [21] discussed the past history of nodes encounters and selected the best relay node based on the high encounter value. It will just look into the past history but did not consider the change of time history and buffer size. There are other protocols like RAPID which replicates packets which results locally in the highest increase in utility [22], and message ferries approach [23–26] discussing dedicated nodes to connect partially disconnected networks. In [27], the author has proposed look-ahead routing and message scheduling (ALARMS) scheme in which the ferry nodes inform the gateway nodes about their travel schedule so that the gateway nodes can decide which ferry to use for each message in advance and schedule the message in the queue accordingly. In [23], the cluster head nodes act as an intermediary between normal nodes and ferry. The nodes themselves have to register with the head of the cluster about their recent location information. Thereafter, the cluster head will then route the messages to the destination node by selecting the correct ferry which is going to that location. But the approaches using message ferry will fail in the case of absence of dedicated nodes.

The existing works assumes the disconnection among the nodes persist always. But the disconnections in ad hoc nodes will also not be consistent over a period of time. Therefore, whenever connectivity is available among the nodes that should be utilized. The proposed work, FIRE, discusses controlled replication by adapting single copy forwarding when connectivity exists, if not, later switch over to multiple copy or store and forward routing. Here, the multiple replications of messages are greatly reduced when it is not needed. Therefore, due to buffer size and energy constraints, the messages are selected for multiple replications only when a node could not find the destination within its proximity.

While going for multiple replication of the same message, it should result in minimum number of replicas in the network in order to increase the throughput and also to reduce the transmission delay. However, a node has no precise knowledge in controlling the replication of the messages to intermediate nodes. Therefore, it is very difficult to select the best intermediate node for transmission. Here, while replicating, the number of copies are reduced by replicating the message only to the relay nodes which have high probability to meet many number of nodes.

3. Find and Replicate Strategy

3.1. Basic Model

In intermittently connected networks, single copy routing fails when disconnections exist for a long time. Hence, multiple replications are needed for a message to reach the destination via store and forward switching. While replicating multiple messages of the same copy, the disadvantage is that the resources like buffers, battery are to be taken into account since multiple copies engage the resources heavily. Therefore, while designing a multiple replication-based protocols, number of copies of a message should be reduced as much as possible at the same time increasing the throughput probability and reducing the average end-end delay.

The existing routing protocols assume that the destination is not accessible from the source or from any relay node while forwarding. As a result, whenever a source or a relay node has a message, it is forwarded with multiple copies to reach the destination soon. But this is not always the case with the wireless network. Based on the mobility of the nodes, the disconnections are not persistent. Also, it is not that every source and destination may not get connected always. Therefore, we are trying to utilize the connections whenever possible. The FIRE strategy tries to find for the destination initially, if it is not available then replicates multiple copies of the messages.

The proposed FIRE routing protocol is very simple. In the first phase, it initially searches for the destination. If the destination is available, then it transfers the copy to the destination via the routing information obtained by sending destination seek message and receiving destination found. If the destination is not available, then it switches to store and forward routing or controlled replication where the message is buffered for infinite delay which is the second phase.

3.2. Finite Delay Forwarding Strategy

If a source likes to send a message to any of the destinations then it initially searches the destination for its availability within the reach of the source. If it is available then, it forwards only a single copy to that destination with the route information obtained. When a destination is available, a source buffers the message for a finite time. But, if the destination is not available then the source gives the message to maximum delay buffer or infinite buffer. Infinite delay buffer forwarding is discussed in the next section.

The source finds a destination by broadcasting a destination seek message. The destination seek contains the information of the source node, destination node, sequence number, time to live, and hop count. The time to live value in the seek message limits the life time of that message. The destination seek messages need not to be propagated for a long time since the destination may not to be available now. The time to live for a destination seek message is fixed based on inter meeting times of nodes in a network. For a random way point mobility, the maximum delay in reaching the destination $E D_{dt}$ is derived and used in [12, 28] based on the meeting times of nodes. It is given by

\begin{matrix} {ED}_{dt} = 0.5 N (0.34 \log N - \frac{2^{K + 1} - K - 2}{2^{K} - 1}), \end{matrix}

(1)

where K is the transmission range of a node and N is the size of the network. Therefore, a destination seek message can propagate up to the maximum time limit which is the maximum expected delay in reaching the destination. Here, the maximum time limit is fixed for a destination seek, based on its average meeting times with other nodes. Therefore, the time to live for the destination seek is then given by

\begin{matrix} {D seek}_{ttl} = \frac{E D_{dt}}{t_{2} - t_{1}} . \end{matrix}

(2)

The $D see k_{ttl}$ is approximated directly with maximum delay in reaching the destination and inversely with difference in intermeeting times of a node with other node. The $T_{1}$ , $T_{2}$ are the average times of nodes encounter with one node and with two different nodes, respectively. The empirical value of ED_dt is calculated during the simulation of the scenario discussed in Section 4, and it comes around 200 s to 550 s. The average value of the $T_{1} - T_{2}$ is calculated, and it changes about 5 s to 20 s depending upon the dynamic topology. Then the waiting time of the destination seeks also vary from 40 s to 110 s. If a node could not receive the destination reply within that time then all the messages destined for the same destination is moved to the infinite buffer.

Calculation of waiting time for the destination reply for a destination seek message depends upon the node inter-contact time since the approximation of delay determines, waiting for the destination seek is reasonable or not. It is the round trip time of the delay in reaching the destination and then back to source. But, here we limited its value and it is assigned as

\begin{matrix} {D seek}_{delay} = {D seek}_{ttl} . \end{matrix}

(3)

The delay calculated with the above equation is the maximum delay for the random way point mobility model. Therefore, it is reasonable for a node to wait for destination reply for the above maximum delay. Here, we relate the delay also with the meeting time since if meeting time is more than the probability to find the destination may be more. So, we make use of the opportunity to meet many nodes and then wait for the reply from the destination for finite delay.

Meeting times of nodes are considered for the delay and time to live since meeting time is small then the node may have chances to meet many numbers of nodes. If meeting time is high then passing the message for the destination seeks may go waste after some delay. Since, a network without much node movements may get disconnected frequently. Therefore, if delay goes beyond the expected maximum delay limit, messages need not to be dropped; instead the message can be replicated through multiple nodes for the destination so that the delay can be tolerated.

If the destination is found by the seek message then the destination node reply with the destination found message. The destination found is a unicast from the destination to source. When multiple seek messages reach the destination then the reply will be only the seek message which has shortest hop count. Like other MANET routing protocols, after receiving the destination found, the message will be unicasted with the same path of the destination found.

After establishing the route, while the transmission is going on, in between the destination may get disconnected from the network due to mobility or any link break down. This is the characteristics of intermittently connected network. The destination node or the next hop is not found then the intermediate nodes sends the destination seek in order to search whether the node is within the reach of that node. If there is no reply for the seek message, then a destination not reachable message will be intimated to source, and the packet will be buffered in the intermediate as well as in the source node for infinite delay forwarding.

The destination seek can be differentiated from other protocols route request messages. Other MANET protocols like AODV and DSR use the route request messages for finding the destination. If route request is delayed then they use the expanding ring search technique to find the destination. But in destination seek, the destination is searched for a finite amount of delay and limited life time value. If it is delayed beyond that maximum expected value, then the message is shifted to infinite delay forwarding by assuming that the destination node is disconnected from the network.

3.3. Infinite Delay Forwarding Strategy

The destination seek packets are sent and the source is waiting for the reply from the destination. When the destination is not currently available then the destination seek packets may not be returned to the source. Other MANET routing protocols discard the message after some retransmission of route requests by assuming that the destination is unreachable.

But the unavailability does not mean that the destination node is permanently disconnected or shut down. It may be due to the destination node may be roaming outside but it may rejoin again or the destination may temporarily be shut down due to battery down or it is due to any link breakdown, and so forth. After some time delay, the destination node can get its messages instead of deleting its messages from the network.

In order to make a message reach its destination which is currently unavailable, the messages are put up in a maximum delay buffer or infinite delay buffer. These delayed messages are propagated into the network by the use of contact opportunity between the nodes. When a source node meets another node, the source makes use of this opportunity to send the infinite delay buffered message. Then this intermediate node again forwards it to other nodes during its encounter. At the last, after some delay, the messages reach the destination. When a destination gives an acknowledgement for the received message, it is flooded into the network. The flooding of acknowledgement deletes the duplicate copies of the messages which reached the destination.

In multiple replications, when two nodes meet, like node x and node y, they will exchange the summary vectors in order to know the messages that are to be transferred from x to y and vice versa. Uncontrolled replication transfers all the messages from node x to node y, those messages are not available in node y. But, without any knowledge about the destination of the messages and about the node y the messages are transferred. If the node y is not having a chance to meet the destination of any single message, then the resources of node y will be exhausted without any use. Thus, it is a must to derive a message replication based on some knowledge about the destination of messages and the relay node.

The messages are spread into the network from the infinite buffer in a controlled manner. Initially the source finds the relay node which is having a high intercontact or meeting update. This is to make the replication to be with only the relay nodes which are having a high chance to meet other nodes or even the destination. Since the replication with nodes which have constrained mobility need to be avoided.

The meeting update for a node is calculated based on its encounter history. Each node updates its own meeting updates when encountering a new node. When a node x meets new node y which is the nth node it meets, then the meeting update $p_{x j}$ in node x is updated as

\begin{matrix} p_{x n} = \frac{ϕ (1 / 2 (n / n + 1) + p_{x n - 1})}{1 + ϕ (t_{2} - t_{1})}, \end{matrix}

(4)

where

p_{x n - 1}

is the meeting update up to

n - 1

nodes, ϕ is the precedence given to history of encounters or the time difference (

t_{2}

−

t_{1}

) between current and previous node encounters. If first time a node meets other node then (

t_{2}

−

t_{1}

) is set as 1. If time difference elapses for a long time then the update value is very low. Therefore, if a node meets another node frequently the value will be higher. When a relay node x encounters another relay node y, it sprays its messages only when node y has

p_{y n}

\geq p_{x n}

. The table below shows the simulated meeting updates calculated for a node which is meeting up to 15 new nodes in various time intervals.

The empirical values obtained for different number of nodes and during different time periods are given in Table 1. The table shows that when $t_{2}$ − $t_{1}$ is 2, and it is maintained in the subsequent meetings then the meeting update is increasing. Later, if $t_{2}$ − $t_{1}$ is increased to 6, it means that nodes are not meeting very frequently, then the meeting update is getting reduced. The different ϕ values makes the meeting update value to increase when ϕ is increased. At the same time, the $t_{2}$ − $t_{1}$ increase makes the meeting update to decrease dramatically even though the ϕ is increasing. The initial value of meeting update, when $n = 1$ is somewhat higher than the next few encounters. But, the initial value will go low in the next encounter.

Table 1

Empirical Value Obtained for Meeting Updates for a node.

N	$t_{2}$ - $t_{1}$	Values of ϕ
N	$t_{2}$ - $t_{1}$	0.5	1	2	5	10
1	1	0.083	0.125	0.167	0.208	0.227
2	5	0.06	0.076	0.091	0.104	0.11
3	5	0.062	0.075	0.085	0.092	0.095
4	2	0.116	0.158	0.194	0.224	0.236
5	2	0.133	0.192	0.244	0.291	0.311
6	2	0.14	0.207	0.269	0.327	0.352
7	2	0.144	0.215	0.283	0.348	0.376
8	2	0.147	0.22	0.291	0.36	0.391
9	6	0.075	0.096	0.114	0.131	0.138
10	6	0.066	0.079	0.087	0.094	0.097
11	10	0.044	0.049	0.052	0.054	0.055
12	10	0.042	0.046	0.049	0.051	0.051
13	5	0.072	0.085	0.093	0.099	0.101
14	5	0.077	0.092	0.102	0.109	0.111
15	5	0.078	0.093	0.104	0.111	0.114

If a message is forwarded using infinite buffer, then the expected delay in reaching the destination is given by

\begin{matrix} {ED}_{\inf} = WT for finite delay + delay during infinite buffer, \\ E D_{\inf} = {D seek}_{delay} + \frac{{D seek}_{delay}}{N}, \end{matrix}

(5)

where N indicates that the numbers of relay nodes which are having the good meeting time update during infinite delay forwarding. The value of N depends on the node movements and meeting with other nodes inside a network.

In a highly mobile environment, $N \approx M$ , where M is the total number of nodes in a network. It is possible for a node to meet all the nodes inside a network. Hence, the delay approximately or closely equal to

\begin{matrix} E D_{\inf} \approx {D seek}_{delay} . \end{matrix}

(6)

In a constrained mobility environment $N ≪ M$ , hence, the delay becomes

\begin{matrix} E D_{\inf} \approx 2 {D seek}_{delay} . \end{matrix}

(7)

Thus, the results show that in case of highly mobile environment regardless of the destination availability the delay is approximately equivalent to the expected value of directly reaching the destination. Since, in a highly mobile environment connectivity is maintained, and it makes all the messages to reach the destination via finite delay buffer itself. If mobility of nodes decreases then the delay is increased up to the extreme case of double the time of the expected delay. It actually happens during infinite delay forwarding.

Even though, the FIRE uses two phases of routing, the second phase is not increasing the delay when mobility of nodes is high. When nodes are moving slowly the delay may be increased. But the average delay is decreased since it depends on the availability of destinations. The average number of replications also gets reduced since the proposed system checks for the destination and then switch to infinite buffer forwarding. In the second phase of routing it forwards only limited copies based on the meeting probability. Therefore, the average number of replications of each message and average delay is reduced compared with existing protocols (Pseudocode 1).

Pseudocode 1:Pseudo code for the FIRE forwarding.

while(msg from node y to node x)

case “data”:

if msgDstip == x

acceptDataAsDest();

floodAck(msg);

else

if routeEntry(msgDstip))

sendtoNexthop();

else

sendDestinationSeek(msgDstip);

FiniteBuffer.add(msg));

end if

done

case “hello”:

ifnewNeighbour(y) == true

ifInfiniteBuffer.hasMsgsForDest(y) == true

deliverMsgs(m)

end if

updateMeetingupdate(y);

requestMeetingupdate (y);

end if

done

case “meetingupdate”:

for InfiniteBuffer.Msgs

ifMeetingupdate (y) >

Meetingupdate (x)

transMsgs.add(InfiniteBuffer.getMsgs())

sendMsgs(y,transMsgs)

done

end if

end for

done

case “timerExpired”:

if routeEntry(m.timerExpired)

InfiniteBuffer.add(msgs(m));

DropfromFiniteBuffer(msgs(m));

done

end if

done

case “ack”:

if InfiniteBuffer.hasMsgsForDest(ack.d)

DropfromInFiniteBuffer(d);

end if

done

4. Evaluation and Performance Analysis

We have used a discrete event-driven simulator called QualNet to evaluate the performance of different routing protocols under a large range of nodes, for different mobility and different number of messages. Although the intermittently connected or delay tolerant networks of interest are disconnected in general, they may range from extremely sparse to almost connected networks.

The proposed system is implemented and simulation results are compared with the following routing protocols: (i) epidemic routing; (ii) optimized epidemic; (iii) spray and wait; (iv) spray and focus; (v) multiperiod spraying. These protocols are explained in Section 2. Rather than other protocols discussed in Section 2, these protocols show some good metric in different scenarios in intermittently connected networks. Epidemic gives good performance when the buffer size is too large [1]. But when the buffer size is limited, then the epidemic slows down its performance due to heavy load but the spraying methods give better performance comparatively [12, 14, 15]. In spraying methods, the number of copies to be spread is limited based on the number of nodes in a network. Spraying will not exhaust the buffer of each node and hence the throughput is increased. But, spraying some limited copies also, unnecessary when destination is reachable. The nodes are resource constrained in ICWASN; hence, the performance of FIRE is checked with limited buffer size with all the protocols said above.

We need to define a meaningful connectivity metric for the network nodes, since here it is necessary to capture both disconnected and connected network environments. This kind of environment is implemented by forming some disconnected clusters. The cluster of nodes later may go around and connected to other nodes in the cluster. The connectivity is the measure of how many new nodes are encountered by a given node within some time interval and is important in situations where mobility is exploited to deliver traffic from source to destination. In the scenario, there are maximum of 100 nodes moving inside a 2500 × 2500 network. Also, 20 nodes are chosen randomly among the clusters and 25 messages are sent per pair per second throughout a run. The values obtained are the average of 15 runs with different seeds for 1000s of simulation time. Each node has a buffer space of 100 messages. The other parameters for the simulation analysis are given in Table 2.

Table 2

Simulation parameters.

Parameter	Default value
Network size	2500 m × 2500 m
Number of nodes	20 to 100
Transmission power	15 dBm
Battery model	Linear
Speed of a node	10 mbps to 50 mbps
Pause time	30 seconds
Infinite and finite buffer size	100 Messages/Node
Mobility model	Random Way point Mobility
Message size	512 Bytes
Simulation time	1000 s
Physical layer	802.11b Radio
MAC layer	802.11(Ad hoc)
Channel frequency	2.4 GHz

The throughput, delay and number of messages duplicated parameters are checked for different scenarios and with different mobility too. Figure 1 shows the throughput of the different routing protocols for different numbers of nodes in the scenario. It is common in intermittently connected networks that the number of nodes raised the throughput is increased due to increase in relays. Hence, all the protocols are showing the improvement in throughput. But epidemic and optimized epidemic protocols are having very low throughput than others. Table 3 summarizes the performance of FIRE. It shows more than 100% improvement in FIRE compared to epidemic. This is due to the uncontrolled replications of each message. The nodes running with epidemic protocol transfer all their messages to nearby nodes that do not have a copy of it already. Therefore, soon the network becomes congested.

Table 3

Summarization of FIRE performance versus others.

Performance of fire	Increase in nodes versus throughput	Increase in nodes versus delay	Increase in nodes versus duplications	Mobility versus delay	Traffic increase versus No. of drops
Epidemic	More than 100%↑	20%↓–8%↑	84%–92%↑	2%↓–44%↑	82%–96%↑
Optimised epidemic	More than 100%↑	21%↓–1%↑	83%–91%↑	4%↓–42%↑	81%–95%↑
Spray and Wait	4%–42%↑	4%–36%↑	59%–48%↑	9%–41%↑	15%–61%↑
Spray and Focus	4%–37%↑	5%–26%↑	50%–60%↑	8%–41%↑	34%–63%↑
Multiperiod Spray	4%–43%↑	4%–31%↑	14%–27%↑	13%–33%↑	9%–55%↑

↑ Increase, ↓ Decrease

Figure 1

No. of nodes versus total throughput.

At last, a number of messages are dropped before reaching the destination. The optimized epidemic routing is used to control the message drops in a meaningful way. It utilizes the age and hop count of the messages for deleting a message in the buffer. In this way, the message just entered into the network is propagated and the message which has duplicated in many numbers of nodes are dropped first. Therefore, controlled replication in optimized epidemic improved the performance of epidemic protocol in terms of throughput. But these protocols give very low throughput comparing with spraying methods. The nodes equipped with some moderate mobility makes the spraying methods have superior performance. The spraying methods distribute some fixed number of copies of each message; the messages are replicated only to certain number of nodes in spray phase. Owing to mobility, these copies distributed by the source may reach the destination during wait phase. The disadvantage of spray and wait is that it is not suitable for constrained mobility. Spray and focus slightly modify the Spray and Wait wherein, it finds for best relay in focus phase for further forwarding. The messages will be forwarded to best relay nodes which have recent encounter timers with the destination. But the results in Figure 1 show that the differences of those methods are smaller.

The multiperiod spraying [15] is another one version spraying methods. Here, fixed numbers of copies are distributed at some regular intervals rather than at the same time until receiving an acknowledgement from the destination. It is resulting with the same performance in terms of throughput with the above said two spraying methods. The proposed method FIRE outperforms both flooding-based and spraying-based routing protocols. Since, the FIRE will try to capture the destinations availability before replications begin. The simulation traffic is included with the combination of both destination availability and unavailability. Other protocols are going for multiple replications all the time. But the FIRE will look into the availability and make use of it whenever possible. Therefore, the buffer of each node is saved and on the average number of messages that reach the destination are higher. Unlike spray and focus, it does not have only the last encounter of destination with the relay node. Hence, the spray and focus have to wait for a relay node which has encountered the destination. But FIRE spray the copies to all the nodes which have high meeting update.

Figure 2 shows the effect of number of node increase in average end-end delay of the messages. It is also known that whenever we increase nodes in a network delay in reaching the destination is reduced. But the average end-end delay may vary based on the routing protocols. The delay measurement is shown in Figure 2 is different than that of the throughput results. Here, the delays of spraying methods are very highcompared tothe epidemic and optimized epidemic.

Figure 2

No. of nodes versus average end to end delay.

The epidemic routing makes many copies to replicate; the messages are reaching the destination soon. But spraying limit the copies and the copies take longer time to reach the destination due to few numbers of nodes only receiving the copy. The FIRE is also lagging below about 20%-21% as in Table 3 when the nodes are minimal compared toepidemic. The spray and focus give higher delay, since the random way point mobility leads to encounter timers to go outdated soon. When the numbers of nodes are increased, in FIRE, the delay has been reduced up to 36% maximum even though it has two phases of routing.

In the first phase, if a source can reach the destination then the delay for all the messages of that source are greatly reduced than that of the multicopy forwarding. Then for a message to reach its destination, it is less than that of the delay of directly meeting the destination ED_dt or ${D seek}_{ttl}$ . On the average, it reduces the delay of all the messages. The messages will be forwarded to its destination without any drop in the network. Also in the second phase, that is if destination is not available, the messages are put up in an infinite buffer. The infinite buffered messages are again forwarded to nodes which have probability to meet many other nodes. This makes the messages to be propagated fast into the network in a controlled manner. The messages may reach the destination in second phase also without much loss and with reduced delay.

Figure 3 depicts the number of messages duplicated for different numbers of nodes in the scenario. Undoubtedly, we can see the results; it is very huge for Epidemic and optimized epidemic. Optimized epidemic also makes approximately equal copies since it limits the number of copies generated but delete the buffered messages with meaningful semantics as said above. Looking at spraying methods, they are greatly reduced the number of copies. In terms of number of copies, spray and focus and spray and wait have only slight variations. Spray and focus may have some few copies extra than that of the spray and wait. Multiperiod spraying limits the copies still to a greater extent since it sprays the copies in three different periods. If the message reached the destination, then it does not spray further. FIRE results in maximum number of reduced copies from 14% to 92%. This is due to the destination available opportunity, a single copy is forwarded to the destination and not it is duplicated. But the variation is not so much between FIRE and multiperiod, since the FIRE switch on to second phase of multicopy routing when destination is not available.

Figure 3

No. of nodes versus duplicated messages.

The mobility may change all the above results in a considerable manner. When node mobility speed increases, then the meeting opportunity among nodes increases and the performance of ad hoc routing protocols is improved. Therefore, we vary the speed of nodes and measure the delay and throughput. The delay measurement is shown in Figure 4 against the mobility. We have observed two results that depend upon the number of nodes in a network. When numbers of nodes are minimal then the node speed does not make the delay decrease. When it is doubled for the same scenario, then the delay is reduced to a certain extent. At the same time the changes reflect only to some limited speed. If speed is increased further then the results are the same or decreasing, due to contact times of nodes are reduced.

Figure 4

Node speed versus average end-end delay.

When nodes are slow, all the protocols have almost the highly delayed messages. Even though the spraying methods limit the number of copies to a greater extent, when nodes are restricted within some area they give minimal performance since the messages are copied to limited number of nodes only. But the remaining protocols have reduced delays, even though they have constrained mobility. When mobility increases, the spraying methods perform better in delivering the messages shortly; therefore, after 30 mps as in Figure 4 the spraying methods have reduced delay than the flooding based approaches. But when speed is increased further then all the protocols tend to work like the same. There is no further improvement in delays since the high speed makes the nodes to miss the contacts. The FIRE has an impact on the mobility. Initially, when nodes are at very low speed like 10 mps, it gives 2%–4% performance decrease with flooding based protocols. It is due to the relay nodes are not faster in meeting other nodes. When nodes are having increased speed, connectivity among the source and destination increases and the maximum of messages are delivered with finite delay forwarding itself. If we see the 50 mps delay values for FIRE, it is very lowcompared toall other protocols. Hence, the FIRE makes use of the dynamic topology changes and adapt to that for having a better performance in terms of delay and also throughput.

The buffer sizes of nodes have a great impact on the performance of intermittently connected networks. The flooding based protocols work better if they have infinite buffer space. If buffer space is restricted then there are much number of packets drop. This is depicted in Figure 5. Here, the results are shown for the buffer size of each node is restricted to 200 messages. The x-axis is increased with CBR traffic per source node. When the traffic is low the message drops are really low in epidemic and optimized epidemic. Even it is zero for FIRE and other spraying methods. But when we increase the traffic the messages started to drop. But there are sudden increases in flooding-based schemes. Both epidemic and optimized epidemic have almost equal number of packets dropped when increasing the traffic. Since in flooding almost the buffer of all the nodes fully occupied the optimized epidemic cannot control the drop but drop the messages according to the criteria. The FIRE has smaller number of message drops, and it improves the results from 9% to 55% compared with multiperiod but increases up to 96% compared with epidemic protocols, since in the finite phase it transfer only a single copy for all the messages and in the infinite forwarding also it limits the copies only to the nodes which has good meeting update. Therefore, unnecessary flooding and unwanted fixed number of copies are avoided. Therefore, the buffer of the relay nodes is kept free for useful traffic.

Figure 5

Increase in messages/source versus no. of messages dropped.

5. Conclusion and Future Work

In this paper, we develop techniques to allow eventual message delivery in the case where connectivity from source to destination may or may not be available in wireless ad hoc networks. Existing routing techniques of mobile ad hoc protocols are unable to deliver packets in the occurrence of network separation between source node and destination node when partition exists for a long time. Therefore, multiple replication schemes are introduced. But these multiple replication schemes waste the resources like bandwidth, buffer, and battery of the wireless nodes most of the time. Since the resource consumption is very essential in wireless nodes, it is a must to go for controlled multiple replication schemes. We try to utilize the connections among the source and destination whenever possible by finding the destination first and then route. If destination is not available then we move to infinite buffer forwarding where messages are kept for long time. Thus, the FIRE makes use of the connectivity whenever possible and the results show that the delay is reducedin turn ofincreasing the throughput. The number of replications and message drops are greatly reduced compared with the existing controlled replication schemes.

As a future part, we are planning to analyze our protocol for energy awareness on relay nodes and then to route. Also, different mobility models are to be evaluated with the proposed method. If none of the destination is available, then all the traffic follows the infinite buffer forwarding. Therefore, different optimization can be tried during infinite buffer forwarding for further reducing the number of duplications.

References

Vahdat

Becker

Epidemic routing for partially-connected ad hoc networks

Duke University Technical Report 2000 CS-200006

Burleigh

Hooke

Torgerson

Fall

Cerf

Durst

Scott

Weiss

Delay-tolerant networking: an approach to interplanetary internet

IEEE Communications Magazine 2003 41 6 128 136

2-s2.0-0037600404

10.1109/MCOM.2003.1204759

Cerf

Delay-Tolerant Network Architecture, IETF RFC, 4838, Informational 2007

Fall

A delay-tolerant network architecture for challenged internets

Proceedings of the Conference on Computer Communications (ACM SIGCOMM '03)

August 2003

27 34

2-s2.0-1242310099

Wang Wu H

DFT-MSN: the delay/fault-tolerant mobile sensor network for pervasive information gathering

Proceedings of the 25th IEEE International Conference on Computer Communications

2006

Grossglauser

Tse

D. N. C.

Mobility increases the capacity of ad hoc wireless networks

IEEE/ACM Transactions on Networking 2002 10 4 477 486

2-s2.0-0036670170

10.1109/TNET.2002.801403

Jain

Fall

Patra

Routing in a delay tolerant network

Proceedings of the Applications, Technologies, Architectures, and Protocols for Computer Communications (ACM SIGCOMM '4)

2004

ACM Press

145 158

LeBrun

Chuah

C. N.

Ghosal

Zhang

Knowledge-based opportunistic forwarding in vehicular wireless ad hoc networks

Proceedings of the IEEE 61st Vehicular Technology Conference (VTC '05)

June 2005

2289 2293

2-s2.0-26444550705

Mauve

Widmer

Hartenstein

A survey on position-based routing in mobile ad hoc networks

IEEE Network 2001 15 6 30 39

2-s2.0-0035509489

10.1109/65.967595

10.

Mathurapoj

Pornavalai

Chakraborty

Fuzzy-spray: efficient routing in delay tolerant ad-hoc network based on fuzzy decision mechanism

Proceedings of the IEEE 18th International Conference on Fuzzy Systems

August 2009

104 109

2-s2.0-71249117867

10.1109/FUZZY.2009.5277223

11.

Poongodi

Natarajan

A. M.

Optimized replication strategy for intermittently connected mobile etworks

Proceedings of the International Journal of Business Data Communications and Networking

2012

12.

Spyropoulos

Psounis

Raghavendra

C. S.

Spray and wait: an efficient routing scheme for intermittently connected mobile networks

Proceedings of the Conference on Computer Communications (ACM SIGCOMM '05)

August 2005

252 259

2-s2.0-29244491141

13.

Spyropoulos

Psounis

Raghavendra

C. S.

Performance analysis of mobility-assisted routing

Proceedings of the 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC '06)

May 2006

49 60

2-s2.0-33748060198

14.

Spyropoulos

Psounis

Raghavendra

C. S.

Spray and focus: efficient mobility-assisted routing for heterogeneous and correlated mobility

Proceedings of the 5th Annual IEEE International Conference on Pervasive Computing and Communications Workshops (PerCom Workshops '07)

March 2007

79 85

2-s2.0-34547699980

10.1109/PERCOMW.2007.108

15.

Bulut

Wang

Szymanski

B. K.

Cost-Effective multiperiod spraying for routing in delay-tolerant networks

IEEE/ACM Transactions on Networking 2010 18 5 1530 1543

2-s2.0-77958150212

10.1109/TNET.2010.2043744

16.

Rus

Sending messages to mobile users in disconnected ad-hoc wireless networks

Proceedings of the 6th Annual International Conference on Mobile Computing and Networking (MOBICOM '00)

August 2000

44 55

2-s2.0-0034545825

17.

Burgess

Gallagher

Jensen

Levine

B. N.

MaxProp: routing for vehicle-based disruption-tolerant networks

proceedings of the 25th IEEE International Conference on Computer Communications (INFOCOM '06)

April 2006

2-s2.0-39049118503

10.1109/INFOCOM.2006.228

18.

Dang

Clustering and cluster-based routing protocol for delay-tolerant mobile networks

IEEE Transactions on Wireless Communications 2010 9 6 1874 1881

2-s2.0-77953278111

10.1109/TWC.2010.06.081216

19.

Takahashi

Tang

Jaggi

Energy-efficient data preservation in intermittently connected sensor networks

Proceedings of the IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS '11)

April 2011

590 595

2-s2.0-79960582208

10.1109/INFCOMW.2011.5928882

20.

Maurice

J. K.

Wissam

F. F.

Chadi

M. A.

Probabilistic bundle relaying schemes in two-hop vehicular delay tolerant networks

IEEE Communications Letters 2011 15 3 281 283

2-s2.0-79952701419

10.1109/LCOMM.2011.011011.102512

21.

Nelson

S. C.

Bakht

Kravets

Encounter-based routing in DTNs

Proceedings of the IEEE 28th Conference on Computer Communications (INFOCOM '09)

April 2009

846 854

2-s2.0-70349682519

10.1109/INFCOM.2009.5061994

22.

Balasubramanian

Levine

Venkataramani

DTN routing as a resource allocation problem

Proceedings of the Conference on Computer Communications (ACM SIGCOMM '07)

August 2007

373 384

2-s2.0-36949009831

10.1145/1282380.1282422

23.

Poongodi

Natarajan

A. M.

Suganthee

R. C.

Cluster head bundle delivery protocol for delay tolerant networks

Proceedings of the CiiT International Journal of Wireless Communication

November 2010

24.

Shah

R. C.

Roy

Jain

Brunette

Data mules: modeling a three-tier architecture for sparse sensor networks

Proceedings of the Sensor Network Protocols and Applications

2003

30 41

25.

Zhao

Ammar

Zegura

A message ferrying approach for data delivery in sparse mobile Ad Hoc networks

Proceedings of the 5th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MoBiHoc '04)

May 2004

New York, NY, USA

ACM Press

187 198

2-s2.0-4444277059

26.

Zhao

Ammar

Zegura

Controlling the mobility of multiple data transport ferries in a delay-tolerant network

Proceedings of the IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '05)

March 2005

1407 1418

2-s2.0-25844432341

27.

Xian

Huang

C. T.

Cobb

Look-ahead routing and message scheduling in delay-tolerant networks

Proceedings of the 35th Annual IEEE Conference on Local Computer Networks (LCN '10)

October 2010

40 47

2-s2.0-79954996868

10.1109/LCN.2010.5735753

28.

Spyropoulos

Psounis

Raghavendra

C. S.

Multiple-copy routing in intermittently connected mobile networks

Technical Report 2004 CENG-2004-12