Network Coding-based Epidemic Routing (NCER) facilitates the reduction of data delivery delay in Delay Tolerant Networks (DTNs). The intrinsic reason lies in that the network coding paradigm avoids competitions for transmission opportunities between segmented packets of a large data file. In this paper, we focus on the impact of transmission competitions on the delay performance of NCER when multiple data files exist. We prove analytically that when competition occurs, transmitting the least propagated data file is optimal in the sense of minimizing the average data delivery delay. Based on such understanding, we propose a family of competition avoidance policies, namely the Least Propagated First (LPF) policies, which includes a centralized, a distributed, and a modified variants. Numerical results show that LPF policies can achieve at least 20% delay performance gain at different data traffic rates, compared with the policy currently available.

The potential of infrastructureless vehicular ad hoc networks (VANETs) for providing multihop applications is quite significant. Although the Epidemic Routing protocol performs well in highly mobile and frequently disconnected VANETs with low vehicle densities or light packet traffic loads, its performance degrades greatly in environments of high vehicle density together with heavy packet traffic loads that create serious bandwidth contention and frequent collisions. We propose a new epidemic routing protocol in urban environments called Greedy Zone Epidemic Routing (GZER), in which the neighbors of a vehicle are divided into different zones according to their physical locations. Each vehicle maintains a summary vector (SV) of packets buffered locally and zone summary vectors (ZSVs) of all packets buffered in each zone. Whether the infection will be transmitted in each zone is decided by the difference between SV and ZSV. Simulation results show that the proposed GZER protocol outperforms the existing solutions significantly, especially in the environments of high vehicle densities together with heavy packet traffic loads.

An important factor determining the performance of delay tolerant networks (DTNs) is packet delivery delay. In this paper, we study the block delivery delay of DTN with the epidemic routing scheme based on random linear network coding (RLNC). First, simulations show that the influence of relay buffer size on the delivery delay is not as strong in RLNC-based routing as it is in replica-based routing. With this observation,we can simplify the performance analysis by constraining the buffer of the relay node to just one size. Then we derive the cumulative distribution function (CDF) of block delivery delay with difference equations. Finally, we validate the correctness of our analytical results by simulations.

An ad hoc network is a decentralized network that consists of mobile nodes with wireless communication devices without the aid of access points. A Vehicular Ad-hoc NETwork (VANET) is one of the representative applications of the ad hoc network. Epidemic routing has been proposed as a routing protocol based on Store-Carry-Forward mechanism for VANET environment. However, in Epidemic Routing, network resources such as packet buffer of a node are significantly consumed because data packets are spread across the network. Therefore, this paper proposes a new autonomous clustering-based data transfer scheme using positions and moving direction of vehicles for VANETs. The autonomous clustering configures multiple clusters in the network and then only the cluster head that manages the cluster stores data packets. Whenever the cluster meets a new cluster, the cluster head of the cluster decides whether it should forward data packets to the new cluster based on its own position, the destination node's position, and moving direction of the cluster. Finally, this paper presents the simulation results to show the effectiveness of the proposed scheme.

Epidemic Routing is a data delivery scheme based on the store-carry-forward routing paradigm for sparsely populated mobile ad hoc networks. In Epidemic Routing, each node copies packets in its buffer into any other node that comes within its communication range. Although Epidemic Routing has short delay performance, it causes excessive buffer space utilization at nodes because many packet copies are disseminated over the network. In this paper, aiming at efficient buffer usage, we propose an XOR-based delivery scheme for Epidemic Routing, where nodes encode packets by XORing them when their buffers are full. Note that existing delivery schemes with coding are active coding, where source nodes always encode packets before transmitting them. On the other hand, the proposed scheme is passive coding, where source nodes encode packets only when buffer overflow would occur. Therefore, the behavior of the proposed scheme depends on the buffer utilization. More specifically, if sufficient buffer space is available, the proposed scheme delivers packets by the same operation as Epidemic Routing. Otherwise, it avoids buffer overflow by encoding packets. Simulation experiments show that the proposed scheme improves the packet delivery ratio.

We propose a novel epidemic routing policy, named energy optimal epidemic routing, for delay tolerant networks (DTNs). By investigating the tradeoff between delay and energy, we found the optimal transmission range as well as the optimal number of infected nodes for the minimal energy consumption, given a delivery requirement, specifically delay bound and delivery probability to the destination. We derive an analytic model of the Binary Spraying routing to find the optimal values, describing the delay distributions with respect to the number of infected nodes.

Analysis of waiting time to deliver a message M from a source S to a destination D is deeply related to connectivity analysis, which is an important issue in fundamental studies of mobile multi-hop networks. In [1], we compared the mean waiting times of two methods to deliver M with the mean value of the minimum waiting time. The mean minimum waiting time was obtained by computer simulation because theoretical analysis of this mean is not easy, although another two methods were analyzed theoretically. In this paper, we propose an approximate method to theoretically analyze the mean minimum waiting time in a one-dimensional street network, and show that this method gives a good approximation of the mean minimum waiting time. Also, we consider shadowing and change of directions of mobile nodes at intersections as negative factors arising in two-dimensional street networks. We extend the above method to compute the mean minimum waiting time considering these factors, and discuss how the mean minimum waiting time is affected by these factors.

In mobile multi-hop networks, a source node S and a destination node D sometimes encounter a situation where there is no multi-hop path between them when a message M, destined for D, arrives at S. In this situation, we cannot send M from S to D immediately; however, we can deliver M to D after waiting some time with the help of two capabilities of mobility. One of the capabilities is to construct a connected multi-hop path by changing the topology of the network during the waiting time (Capability 1), and the other is to move M closer to D during the waiting time (Capability 2). In this paper, we consider three methods to deliver M from S to D by using these capabilities in different ways. Method 1 uses Capability 1 and sends M from S to D after waiting until a connected multi-hop path appears between S and D. Method 2 uses Capability 2 and delivers M to D by allowing a mobile node to carry M from S to D. Method 3 is a combination of Methods 1 and 2 and minimizes the waiting time. We evaluate and compare these three methods in terms of the mean waiting time, from the time when M arrives at S to the time when D starts receiving M, as a new approach to connectivity evaluation. We consider a one-dimensional mobile multi-hop network consisting of mobile nodes flowing in opposite directions along a street. First, we derive some approximate equations and propose an estimation method to compute the mean waiting time of Method 1. Second, we theoretically analyze the mean waiting time of Method 2, and compute a lower bound of that of Method 3. By comparing the three methods under the same assumptions using results of the analyses and some simulation results, we show relations between the mean waiting times of these methods and show how Capabilities 1 and 2 differently affect the mean waiting time.