VOL. E98-B NO. 12
DECEMBER 2015
The usage of this PDF file must comply with the IEICE Provisions
on Copyright.
The author(s) can distribute this PDF file for research andeducational (nonprofit) purposes only.
Distribution by anyone other than the author(s) is prohibited.

IEICE TRANS. COMMUN., VOL.E98–B, NO.12 DECEMBER 2015

2389

PAPER

Contact Duration-Aware Epidemic Broadcastingin Delay/Disruption-Tolerant Networks∗∗
Kohei WATABE†∗a) and Hiroyuki OHSAKI††b) , Members

SUMMARY DTNs (Delay/Disruption-Tolerant Networks) composedof mobile nodes in low node-density environments have attracted considerable attention in recent years. In this paper, we propose a CD-BCAST(Contact Duration BroadCAST) mechanism that can reduce the number ofmessage forwardings while maintaining short message delivery delays in
DTNs composed of mobile nodes. The key idea behind CD-BCAST is toincrease the probability of simultaneous forwarding by intentionally delaying message forwarding based on the contact duration distribution measured by each node. Through simulations, we show that CD-BCAST needs
substantially less message forwardings than conventional mechanisms andit does not require parameter tuning under varieties of communication
ranges and node densities.
key words: delay/disruption-tolerant networks, opportunistic networks,
epidemic broadcasting, contact duration distribution, mobile ad-hoc network

1. Introduction
In recent years, DTNs (Delay/Disruption-Tolerant Networks) [1]–[3] that realize communication under conditions
in which continuous end-to-end connectivity is not guaranteed have attracted considerable attention. In MANETs(Mobile Ad-hoc NETworks) [4], a class of DTNs, network
links between nodes frequently change because of node mobility. Therefore, conventional communication methods forrealizing end-to-end network connections [5], [6] cannot beapplied to DTNs without modification. In several DTNs, amessage is delivered by store-and-carry forwarding [7] forcommunication, which utilizes the mobility of nodes. For
example, applications of DTNs include conceptual interplanetary communication networks [8], temporary communication networks in disaster-aﬀected areas [9], and sensor
networks used for observing animals in their natural habitats [10]. To increase the probability of successfully message delivery, DTN nodes can utilize epidemic broadcasting[11]–[15], where an infected node — i.e., a node that holds a
Manuscript received November 14, 2014.
Manuscript revised June 7, 2015.
†
The author was with the Graduate School of Information
Science and Technology, Osaka University, Suita-shi, 565-0871
Japan.
††
The author is with the Department of Informatics, School of
Science and Technology, Kwansei Gakuin University, Sanda-shi,
669-1337 Japan.
∗
Presently, with the Graduate School of Engineering, Nagaoka
University of Technology, Nagaoka-shi, 940-2188 Japan.
∗∗
An earlier version of this paper was presented at the 6th Joint
IFIP Wireless and Mobile Networking Conference (WMNC 2013).
a) E-mail: k watabe@vos.nagaokaut.ac.jpb) E-mail: ohsaki@kwansei.ac.jp
DOI: 10.1587/transcom.E98.B.2389

message — forwards a copy of the message to other nodes torealize one-to-many communication. In a simple epidemic
broadcasting, an infected node forwards the copy of a message every time another node enters the radio communication range. As a result, the number of duplicate messages
increases exponentially with time.
In epidemic broadcasting in DTNs, reducing the number of message forwardings is essential for improving efficiency, thereby reducing both energy and bandwidth consumption. Fewer message forwardings leads to lower energy consumption for message delivery, thereby prolonging
the lifetime of DTNs on energy-hungry environments. In
particular, in sensor networks composed of energy-strapped
nodes for environmental monitoring, it is important to continue monitoring without an energy supply for long periods of time [16], [17]. Furthermore, in DTNs composed ofnodes with large-capacity batteries (e.g., vehicular ad-hoc
networks), fewer message forwardings leads to lower bandwidth consumption, thereby increasing the transport capacity of the DTNs.
Conventional approaches for reducing the number ofmessage forwardings in epidemic broadcasting are classified into the following two types: (1) approaches that reduce
duplicate message forwardings and (2) approaches that increase simultaneous forwardings.
SA-BCAST (Self-Adaptive BroadCAST) [18], [19]suppresses duplicate message forwarding by exponentiallyreducing the message forwarding probability according to
the number of duplicate messages received. In HP-BCAST(History- and Push-based BCAST) [11], each node manages
its own history of message forwarding and suppresses duplicate message forwarding by not forwarding messages toinfected nodes. HSA-BCAST (History-based Self-Adaptive
BroadCAST) [18] uses the adaptive control of the forwarding probability, as found in SA-BCAST, along with the management of message forwarding history, as found in HPBCAST.
In constant, there is an approach to reduce the numberof message forwardings by utilizing the characteristics ofradio communication and forwarding a message to multiple
nodes simultaneously. In epidemic broadcasting using radio
communication, a node forwards a message to all the othernodes within its radio communication range. Radio communication allows for a message to be delivered to multiple
nodes simultaneously. Epidemic broadcasting mechanisms
for improving the eﬃciency of DTNs have been proposedusing this approach [12], [13]. In k-neighbor-BCAST (k-c 2015 The Institute of Electronics, Information and Communication Engineers
Copyright IEICE TRANS. COMMUN., VOL.E98–B, NO.12 DECEMBER 20152390

neighbor-BroadCAST) [13], which is a representative of themechanisms that increase the number of simultaneous forwardings, an infected node forwards a message only when
the following two conditions hold: (1) k nodes exist in thecommunication range and (2) at least one of these nodes is asusceptible node (i.e., a node that does not hold a message).
Therefore, nodes can simultaneously deliver a message tomultiple nodes by means of a single message forwarding by
utilizing the characteristics of radio communication.
Several mechanisms for epidemic broadcasting havebeen proposed, but each has drawbacks. The mechanisms,
including HSA-BCAST, that reduce duplicate forwardings
do not increase the number of simultaneous forwardings,
though we can increase the number of simultaneous forwardings while reducing duplicate forwardings. In contrast,
when using mechanisms such as k-neighbor-BCAST, which
increases the number of simultaneous forwardings, parameter tuning is diﬃcult because the number of nodes within acommunication range varies depending on the range, nodedensity, and other factors.
In this paper, we propose CD-BCAST, which can substantially reduce the number of message forwardings while
maintaining short message delivery delay by intentionally
delaying message forwarding on the basis of contact duration distribution measured by each node. We define contact
duration as the duration in which two nodes are in contact
with each other (i.e., reside within each of their communication ranges). In CD-BCAST, each infected node measures the contact duration distribution by recording contact
durations with other nodes. To increase the number of simultaneous forwardings, an infected node intentionally delays its message forwarding until it can forward the message to multiple susceptible nodes; however, when the delay
exceeds the contact duration, the infected node fails to forward the message to the susceptible node, thereby increasing message delivery delay. CD-BCAST overcomes the
weaknesses of conventional mechanisms by utilizing a contact duration distribution, and that does not require parameter tuning under varieties of communication ranges and nodedensities. Through simulations, we show that CD-BCAST
reduced 10–40% of the total number of message forwardings as compared with that of HSA-BCAST. We also showthat the performance of CD-BCAST is not sensitive to its
control parameters.
The remainder of this paper is organized as follows.
Section 2 explains the idea behind our proposed CDBCAST approach and describes the operation of each node.
Section 3 provides investigation of the fundamental properties of CD-BCAST through simulation under simple scenarios. Section 4 provides performance comparison between
conventional mechanisms and CD-BCAST, which showsthat CD-BCAST reduces the total number of forwardings
and is not sensitive to its control parameters. Finally, we
conclude this paper in Sect. 5 and provide directions for future works.

2. Contact Duration-Aware Mechanism for Epidemic
Broadcasting
We propose an eﬃcient epidemic broadcast mechanism
called CD-BCAST, which substantially reduces the total
number of forwardings. CD-BCAST intentionally delays
message forwarding hoping that delaying message forwarding will contribute to a high probability of simultaneous
message forwarding to multiple nodes. The problem weface is to select an appropriate time delay to achieve better
performance because the infected node will not forward themessage to a susceptible node when the delay time exceeds
the contact duration. To address this challenge, CD-BCAST
measures contact duration distribution by recording contact
durations and calculating delay times based on the measured
contact duration distribution. In this section, we describe
the idea behind our proposed CD-BCAST approach and describe the operation of each node.
2.1 Key Concepts
When an infected node encounters a susceptible node, theinfected node can forward a message to multiple nodes bymeans of a single message forwarding if the message is not
forwarded immediately but with a delay that allows othersusceptible nodes to enter the radio communication range.
Illustrated in Fig. 1, an infected node can forward a message to multiple nodes if the forwarding is appropriately delayed. In the figure, at time t = 2, an infected node encounters a susceptible node. As all nodes continue to move, theinfected node encounters an additional susceptible node attime t = 3. If the infected node forwards a message at timet = 3 instead of time t = 2, the infected node can simultaneously forward a message to the two susceptible nodes.
If the message forwarding delay is too long or too short,the infected node is unable to increase the number of simultaneous forwarding. When the message forwarding delay is
too short, the infected node is unlikely to encounter an additional susceptible node before it forwards its message, leading to an ineﬃcient use of the characteristics of radio communication. In contrast, if the message forwarding delay isFig. 1 Example in which the characteristics of radio communication are
utilized by introducing a forwarding delay.

WATABE and OHSAKI: CONTACT DURATION-AWARE EPIDEMIC BROADCASTING IN DELAY/DISRUPTION-TOLERANT NETWORKS

2391

too long, the infected node will likely fail to forward its message to the susceptible node it initially encountered (i.e., theinfected node cannot simultaneously forward its message to
all nodes at t = 4 in Fig. 1). Therefore, an eﬃcient epidemic broadcasting mechanism should be able to calculate
an appropriate message forwarding delay time that utilizes
the characteristics of radio communication while maintaining acceptable message delivery delay.
The key idea behind CD-BCAST is to use the information regarding the situation around an infected node. We
consider that the message forwarding delay should be determined by the following two factors: (1) the number of infected nodes around a susceptible node; and (2) the contact
duration distribution of infected and susceptible nodes. By
using (1), an infected node can suppress message forwarding according to the situation around a susceptible node.
A smaller forwarding probability is desirable when otherinfected nodes are located around a susceptible node because it is expected that they will forward the message tothe susceptible node. If multiple infected nodes forward themessage to the susceptible node, then we face the problemof duplicate forwardings. A long message forwarding delay corresponds to small forwarding probability because theprobability that an infected node fails to forward its message to a susceptible node increases. Therefore, we should
increase the message forwarding delay when there are many
infected nodes around a susceptible node. By using (2), an
infected node can determine the probability that a susceptible node might leave its radio communication range if theinfected node delays message forwarding. If we assume thatthe contact duration distribution is stationary, each node canderive the contact duration distribution by recording the duration of contact with other nodes encountered in the past.
Note that the derivation is achieved without extra communication because nodes are already monitoring nodes within
their communication range.
2.2 Operation
CD-BCAST can substantially reduce the number of message forwardings while maintaining short message delivery
delay by intentionally delaying message forwarding on thebasis of contact duration distribution. In CD-BCAST, eachnode measures its own contact duration distribution, which
each node then uses to set its message forwarding delaysuch that the probability that a susceptible node receives amessage from multiple infected nodes is constant. Infected
nodes determine their respective message forwarding delays
on the basis of their own contact duration distributions andthe number of infected nodes around the encountered susceptible node.
Infected nodes should tune their message forwarding
probabilities as follows. We first assume that there are N
infected nodes {I1 , . . . , IN } around susceptible node S ; furthermore, we assume that these nodes forward a message
independently with the same probability p. In such a situation, probability preceive that node S receives a message atleast once is given bypreceive = 1 − (1 − p)N .
Therefore, to control probability preceive , infected nodes{I1 , . . . , IN } should set their forwarding probability p as
p = 1 − (1 − preceive )1/N .

(1)

By keeping forwarding probabilities that are larger than p,
CD-BCAST maintains short delivery delay. The number
N of infected nodes around node S is needed to determine
p from Eq. (1). N̂ denotes the derived number of infected
nodes within the radio communication range when an infected node encounters node S . There are two options for
tracking the infection status of other nodes and deriving thenumber N̂ of infected nodes within the radio communication range. The first option is to maintain a history of message forwardings, an approach used in [11]. In this case,each node manages its own history of message forwardings
and exchanges it by piggybacking it on transmitted message. The second option is to manage a holding message
list, an approach used in [12], [13]. In this case, each node
exchanges a list of messages it is holding on every contact.
Both the approaches generate a communication overhead;the optimal approach should be determined by considering
the environment of the DTN because the amount of the overhead depends on the environment. Whereas a more comprehensive study of how the optimal approach should be determined is outside the scope of this paper, CD-BCAST works
regardless of which option we take (we will show that CDBCAST provides better performance regardless in Sect. 4).
Infected nodes adjust message forwarding delay times
such that forwarding probability p satisfies Eq. (1) with theirown contact duration distribution. We let P(x) denote themeasured CDF (Cumulative Distribution Function) of thecontact duration distribution and T S denote x satisfying thefollowing equation:
1 − P(x) ≥ p.

(2)

More specifically, T S is
T S = P−1 (1 − p).
Infected nodes {I1 , . . . , IN } delay message forwarding for T S
after encountering susceptible node S . The infected node
forwards a message if node S resides within its radio communication range after T S has elapsed.
By using this approach, CD-BCAST substantially reduces the number of message forwardings by deliberately
delaying message forwarding while maintaining a high message receive probability of node S from nodes {I1 , . . . , IN }with probability preceive . Note that preceive is a control parameter that adjusts the frequency of message delivery. Larger
values of preceive lead to shorter message forwarding delays,
and infected nodes forward messages more often.
In Algorithm 1, the CD-BCAST algorithm is shown using pseudocode. When susceptible node S enters the communication range of an infected node, the infected node sets

IEICE TRANS. COMMUN., VOL.E98–B, NO.12 DECEMBER 2015

2392

Algorithm 1 Pseudocode for the CD-BCAST algorithm
1: while true do
2:
if susceptible node S enters the communication range then3:p ← F1 (preceive , N);
4:
T S ← F2 (p, P(x));
5:end if6:
for all S do
7:
if timer T S expires then8:
if node S resides within range then9:forward message to all nodes within range;
10:
for all T S do
11:
disable timer T S ;12:
end for13:
end if14:
end if15:
end for
16: end while

message forwarding delay T S . F1 denotes p satisfies Eq. (1),and F2 denotes T S satisfies Eq. (2) (i.e., lines 2-7 of Algorithm 1). Next, the infected node forwards a message toall the nodes within the communication range and disables
timer T S if T S expires and node S is still within the communication range. (i.e., lines 8-17 of Algorithm 1).
Like the conventional mechanisms [13], [18], [19], in
CD-BCAST, each node manages a neighbor node list by listening (broadcasted) beacon frames from other nodes. Eachnode broadcasts a beacon frame periodically. A beacon
frame contains an ID of a node that broadcasts it, and theother nodes are able to know the presence of the neighbornode by receiving the beacon frame. When a node receives a
beacon frame from node X that is not contained in its neighbor node list, the node adds the node X to the neighbor nodelist. If a node cannot receive a beacon frame from node X
during a period δ, the node X is removed from the neighbornode list. In this paper, we consider the simplest mechanism
as in conventional mechanisms [13], [18], [19]. We can embed the position information, migration information, and soon into the beacon. The design of such advanced mechanisms, however, is beyond the scope of this paper.
A contact duration distribution used to determine themessage forwarding delay is measured on the basis of therecords of contact duration by each node. Since each nodemanages its neighbor node list by utilizing beacon frames,
each node can record a contact duration that is defined as thetime elapsed from the initial reception of the beacon frameto the disappearance of the node due to timeout. Contact
duration can be measured without any communication overhead (though there is a slight computational and memory
overhead) because nodes that compose a DTN are always
sending beacons to communicate. Contact duration distribution is analytically derived via the simple mobility modelby Samar et al. [20], [21]. Because the mobility of nodes is
unknown and more complicated in the real world, we use
measured contact duration distribution based on contact durations that are recorded by each node. In CD-BCAST, eachnode records contact durations with the oldest record being deleted if the number of records exceeds nmax ; this pre-vents an increase in memory overhead. Here, we assume
that node X encountered other nodes n times (0 < n ≤ nmax )in the past and that their records of contact duration are{D1 , D2 , . . . , Dn }. The measured CDF P(x) of contact duration of node X isn11{Di <x} ,P(x) =
n i=1
where 1{·} denotes an indicator function. We define P(x) =1{0<x} when n = 0. Note that contact duration does not depend on node density.
3. Fundamental Properties of CD-BCAST
Through simulations, we investigated the following four
fundamental properties of CD-BCAST: (1) the accuracy of
estimating N, which denotes the number of infected nodes
around a susceptible node S ; (2) the message receive probability of a susceptible node from multiple infected nodes
in simple scenario; (3) the eﬀect of reducing the number ofmessage forwardings by intentionally delaying message forwarding; (4) the relationship between the accuracy of contact duration distribution and characteristic (3); (5) the impact of the distribution of nodes on a field.
3.1 Estimation of the Number N of Infected Nodes arounda Susceptible NodeFirst, we investigated the accuracy of estimating N, which
denotes the number of infected nodes around susceptible
node S . In CD-BCAST, each infected node derives N̂,
which denotes the number of infected nodes within the communication range at the moment when the infected node encounters susceptible node S . We define N as the number of
infected nodes that susceptible node S encounters for average contact duration T after the encounter between susceptible node S and an infected node.
In our simulation, 100 nodes moved according to the
RWP (Random WayPoint) mobility model [22] in a 1000 ×1000 [m] simulation field. At the initial state, only a single
node holds a message and nodes deliver the message to all
the nodes via CD-BCAST. The velocity of nodes was uniformly distributed in the range [1.0, 2.0] [m/s]. Radio communication range R of nodes was 25, 50, and 75 [m], withaverage contact duration T of 19.35, 38.85 or 58.33 [s], respectively. Parameter preceive of CD-BCAST was set to 0.7.
To track the infection status of other nodes, we maintained
a history of message forwardings. Each node broadcasted a
beacon every 1 [s], and the timeout δ used for detecting nodedisappearance was set to 1 [s]. We assumed that there wasno propagation delay in the radio communication and that
all nodes had enough storage to record their respective message forwarding histories, as well as their records of contact
duration (with nmax being infinite).
We measured N and N̂, and calculated the MAE (Mean
Absolute Error) of N̂ with respect to N by repeating the simulation 30 times with diﬀerent random seeds. When radioWATABE and OHSAKI: CONTACT DURATION-AWARE EPIDEMIC BROADCASTING IN DELAY/DISRUPTION-TOLERANT NETWORKS

2393

communication range R was 25, 50, and 75 [m], the MAEof N was 0.29, 0.61, and 1.02, respectively; furthermore, theaverage of N was 1.56, 2.27, and 3.19, respectively. Therefore, we observe that CD-BCAST achieved a certain levelof accuracy in estimating N though it is diﬃcult to predict
future contacts of randomly moving nodes.
3.2 Message Receive Probability from Multiple Nodes
Next, we investigated the message receive probability of susceptible node S from multiple infected nodes{I1 , . . . , IN }. Through our simulation, we confirmed that CDBCAST could appropriately suppress message forwarding
according to the situation around a susceptible node. If CDBCAST operates as expected, the message receive probability of a susceptible node should correspond to control parameter preceive .
To derive the message receive probability of a susceptible node, we performed the simulation shown in Fig. 2.
In our simulation, the initial positions of infected nodes
were uniformly distributed inside a circle with a diameterof 50 [m], and radio communication range R of all nodes
was 50 [m]. A cluster of infected nodes and one susceptible node moved at a velocity of 1.5 [m/s] and pass one another, thereby trying to deliver a message from the infected
nodes to the susceptible node. We set the number of infected
nodes in the cluster to values 1-4, and varied control parameter preceive . The contact duration distribution was given
in advance. We repeated the simulation 30 times for eachcondition and derived the probability at which the susceptible node was able to receive a message upon approaching acluster of infected nodes.
Figure 3 shows the message receive probabilities of theFig. 2 Simulation model for investigating message receive probabilities
of susceptible node S from infected nodes {I1 , . . . , IN }.

Fig. 3 Relation between the number of infected nodes in a cluster andmessage receive probabilities of the susceptible node.

susceptible node when we varied the number of infected
nodes. Results show that the message receive probabilityof a susceptible node approximately corresponds to control
parameter preceive . It appears that there was a particularly
close correspondence between the message receive probability of the susceptible node and preceive when the number ofnodes in the cluster of infected nodes was small. In contrast,
when the number of nodes in the cluster of infected nodes
was large, the message receive probabilities of the susceptible node was slightly lower than preceive . Theoretically, themessage receive probability of the susceptible node corresponds to preceive if the duration of contact between each
infected node and the susceptible node are independent of
one another; however, contact durations are not independent
because of the velocity of the susceptible node. If the velocity of the susceptible node was high, the respective contact
durations for all the infected nodes were short. Hence, thecontact durations were correlated.
3.3 Eﬀect of Reducing the Number of Message Forwardings
We investigated the reduction in the number of message forwardings resulting from intentionally delaying message forwarding. We used the aforementioned simulation setup (seeSect. 3.1) except for preceive . We repeated the simulation 30
times and calculated the number of nodes that simultaneously received the message.
We derived how many susceptible nodes were able tosimultaneously receive the message by means of a single
message forwarding until 90% of all the nodes received themessage. Figure 4 shows the ratio of the number of nodes
that simultaneously received a message from a single message forwarding when preceive was varied between 0.1 and1.0. Note that in the legend, 0 nodes represents a message forwarding to an infected node that has already held
the message. These results show that a smaller value of
preceive increased the opportunity of infected nodes delivering a message simultaneously to multiple nodes via a single
message forwarding. More specifically, CD-BCAST wasable to utilize the characteristics of radio communication

Fig. 4 Ratio of the number of nodes that simultaneously received a message by means of a single message forwarding when control parameter
preceive was varied between 0.1 and 1.0.

IEICE TRANS. COMMUN., VOL.E98–B, NO.12 DECEMBER 20152394

when preceive was small.
3.4 Impact of Accuracy of a Contact Duration Distribution
on Performance
We investigated the impact of the accuracy of contact duration distribution on the performance of CD-BCAST. In CDBCAST, infected nodes measure the distribution by storing
records of contact durations and determining forwarding delays with such distributions. Therefore, the performance of
CD-BCAST may suﬀer from the measured contact duration
distribution if an infected node does not have enough information about the distribution (i.e., the number n of records
of contact duration is small).
To investigate the impact of the accuracy of contact duration distribution on performance, we performed two simulations under the following two conditions: (1) each node
was given the contact duration distribution in advance; and(2) each node had no information regarding contact duration
distribution at t = 0. Under the condition (2), each node has
no record of contact duration at time 0 (i.e., P(x) = 1{0<x} )and measures the contact duration distribution. Except for
the initial contact duration distribution, the simulation setup
is the same as the the aforementioned simulation setup (seeSect. 3.3). In the simulation, we derived the periods until
90% of all the nodes received the message (i.e., 90% delivery time), with results shown in Figure 5. Figure 6 shows thetotal number of message forwardings at the 90% delivery
time mark. Furthermore, Fig. 7 shows the measured CDF
P(x) of contact duration at time 300, 1000, and 1000000 [s].
According to Figus. 5 and 7, we confirm that it was diﬃcult
to measure contact duration distribution accurately before
90% delivery time; however, performance did not suﬀer according to Figs. 5 and 6. Results show that CD-BCAST appropriately worked even if measured CDF P(x) was derived
by a small number of records of contact durations.
It is more diﬃcult to accurately estimate the contact
duration distribution when the distribution has larger variance. We therefore performed simulations in which thenode velocity was fixed at 1.5 [m/s]. We used the aforementioned simulation setup in this section except for node
velocity. In this simulation, a node occasionally moved
in parallel with another node at the same velocity thoughnodes mostly passed each other. Hence, a node is likely
to keep another node within the communication range for along time. Therefore, the contact distribution of the nodein this simulation had a larger variance than the aforementioned simulation. The standard deviations of the distributions in the simulation and the aforementioned simulation
were 374.4 [m/s] and 26.4 [m/s], respectively. The simulation results with/without contact duration distribution given
in advance are shown in Figs. 8 and 9. We obtained similar
results to the aforementioned simulation with small varianceof contact duration distribution, and cannot found significant
impact of estimation diﬃculty due to the large variance on
the performance.
Additionally, we investigate the impact of the estima-

Fig. 5time.

The impact of given contact duration distribution on 90% delivery

Fig. 6 The impact of given contact duration distribution on total numberof forwardings.

Fig. 7

Measured CDF P(x) of contact duration at each time.

tion error due to beacon frame loss on the performance of
CD-BCAST. In DTNs, even if two nodes reside within eachof their communication ranges, a beacon frame cannot often
be received due to several reasons including radio interference and collision. We performed simulations with beacon
frame loss. In our simulation, a beacon frame was randomly
discarded with probability q. We changed the beacon error
rate q variously, and investigated the dependency of the performance on the beacon error rate in the cases where psuccessare 0.7 and 1.0 (i.e. CD-BCAST and P-BCAST). We used
the aforementioned simulation setup in Sect. 3.3 except fora beacon error rate and the setting of psuccess . The results areshown in Figs. 10 and 11. We can find from these figuresthat the results of CD-BCAST gradually converge to that of
P-BCAST as beacon error rate increases. In a network thatis frequently disconnected, it is desired to forward a message immediately (like P-BCAST). When the beacon error
rate is high, the behavior of CD-BCAST achieves that of
P-BCAST since the contact duration becomes shorter.
3.5 Impact of Node Distribution on a Field
In DTNs, a node distribution on a field should aﬀect theperformance of epidemic broadcasting. In real DTNs, node

WATABE and OHSAKI: CONTACT DURATION-AWARE EPIDEMIC BROADCASTING IN DELAY/DISRUPTION-TOLERANT NETWORKS

2395

Fig. 12The impact of node distribution on a field on 90% delivery time.

Fig. 8 The impact of variance of a contact duration distribution on 90%
delivery time.

Fig. 13 The impact of node distribution on a field on the total number offorwardings.
Fig. 9 The impact of variance of a contact duration distribution on the
total number of forwardings.

Fig. 10The impact of beacon error rate on 90% delivery time.

with the same setup as in Sect. 3.3 except for mobility modeland preceive . Figures 12 and 13 show that 90% delivery time
and the total number of message forwardings in the simulation. Figure 12 shows that the 90% delivery time decreases
when the ratio of nodes within a dense field is high. The
main reason for this is that a high density field accelerates
spread of message. On the other hand, the total number ofmessage forwardings increases as the ratio of nodes within adense field increases. The fall of the node density of sparse
field increases the number of forwardings since it is diﬃcult
to forward a message to multiple nodes.
4. Comparing the Performance of CD-BCAST with
Conventional Mechanisms
In this section, we compare the performance of CD-BCASTwith that of conventional mechanisms, thereby showing that
CD-BCAST overcomes the weaknesses of existing mechanisms.

Fig. 11ings.

The impact of beacon error rate on the total number of forward-

density on a field may be sometimes non-uniform. However, node density on a field in the RWP mobility modeland most of the other mobility models is nearly uniform. To
investigate the eﬀect of non-uniformity of node density on
performance of CD-BCAST, we performed a simulation inwhich the node density is not uniform. In our simulation, we
consider two types of node: sparse and dense nodes. Sparse
nodes were distributed in 1000 × 1000 [m] field, and dense
nodes are distributed in 500×500 [m] field. Bottom-left corners of the two fields were located at the same point. Eachnode moved according to the RWP mobility model on its
field. By changing the ratio of number of the dense nodes tothe number of all nodes, we can change the non-uniformityof node density. We performed simulations, changing theratio from 0.25 to 0.75. The control parameter preceive of
CD-BCAST was set to 0.7. We performed the simulation

4.1 Performance Comparison with HSA-BCAST
To verify the eﬀectiveness of our proposed CD-BCAST approach under various conditions, we compared the performance of CD-BCAST with that of HSA-BCAST. We performed the simulation with the same setup as in Sect. 3.3
except for an epidemic broadcast mechanism. We derived
the total number of message forwardings and 90% delivery
time by repeating the simulation 30 times. In HSA-BCAST,
each infected node managed a history of message forwardings to know whether an encountered node is infected orsusceptible. For this simulation, CD-BCAST also used thesame approach. In general, the performance of an epidemic
broadcasting mechanism is heavily dependent on the choiceof control parameters. Therefore, in the simulation, wechanged control parameters Nth and c of HSA-BCAST. Nthdenotes the threshold of the change rate in the number ofnodes within a communication range of an infected node
used for determining whether the infected node should for-

IEICE TRANS. COMMUN., VOL.E98–B, NO.12 DECEMBER 2015

2396

Fig. 14 Relation between 90% delivery time and the total number ofmessage forwardings for HSA-BCAST and CD-BCAST.

Fig. 16 Relation between 90% delivery time and the total number ofmessage forwardings for radio communication range R of 50 [m] and anumber M of nodes of 50, 100, and 150 for HSA-BCAST and CD-BCAST.

Fig. 15 Relation between 90% delivery time and the total number ofmessage forwardings for a radio communication range R of 25, 50, and75 [m] for HSA-BCAST and CD-BCAST.

the total number of message forwardings for a radio communication range R of 25, 50, and 75 [m]. The simulation
setup we used in this simulation matches the aforementioned
setup except for radio communication range R and the HSABCAST parameter Nth , which we set to 0.75 because at thisvalue HSA-BCAST showed the most favorable characteristics. In Fig. 15, all curves for CD-BCAST are located below
and to the left of those for HSA-BCAST, which indicatesthat the performance of CD-BCAST was higher than that of
HSA-BCAST regardless of radio communication range R.
Finally, we investigated the impact of node density
through simulations with various numbers M of nodes. Figure 16 shows the relation between 90% delivery time andthe total number of message forwardings for a radio communication range R of 50 [m] and a number M of nodes of50, 100, and 150. We set control parameter Nth of HSABCAST to 0.75. The simulation results indicate that theperformance of CD-BCAST was higher as compared withthat of HSA-BCAST because all curves for CD-BCAST arelocated below and to the left of those for HSA-BCAST. This
indicates that the performance of CD-BCAST was higher
than that of HSA-BCAST regardless of node density.

ward a message; c is a parameter that controles exponential
decay in the forwarding probability according to the numberof duplicate messages received by other nodes.
In Fig. 14, we show the 90% delivery time and total
number of message forwardings. Respective points for CDBCAST in the figure are related to the results for preceive =1.0, 0.9, 0.7, 0.5, 0.3, and 0.1 in order from left to right.
Similarly, respective points for HSA-BCAST in the figure
are related to the results for c = 1.0, 2.0, 4.0, and 8.0 inorder from left to right. In epidemic broadcasting, there
is a tradeoﬀ between message delivery delay and the eﬃciency of message delivery. Therefore, in the figure, when
the curve describing the changes in the control parameters
is closer to the lower left corner of the graph, it indicates
better performance of the corresponding epidemic broadcasting mechanism. On the left of the figure, the points
for CD-BCAST and HSA-BCAST (Nth = 0.0) overlap because these points represent the results for preceive = 1.0 andc = 1.0, respectively; in other words, these parameters do
not control message forwarding as they do in HP-BCAST.
The figure shows that CD-BCAST achieved a rate of message delivery equivalent to that of HSA-BCAST by meansof a small number of message forwardings. More specifically, CD-BCAST achieved a reduction of approximately
10-40% in the number of message forwardings compared to
HSA-BCAST.
We also investigated the impact of communication
range through simulations for various numbers of nodes.
Figure 15 shows the relation between 90% delivery time and

4.2 Performance Comparison with k-Neighbor-BCAST
To further verify the eﬀectiveness of our proposed CDBCAST approach, we compared the performance of CDBCAST with that of k-neighbor-BCAST, which increases simultaneous forwardings. k-neighbor-BCAST has an inherent weakness in which parameter tuning is diﬃcult because
the number of nodes within communication range varies depending on range, node density, and other factors.
To show that CD-BCAST does not require parameter tuning for changes in communication range and nodedensity, we performed the simulation and derived the total number of message forwardings and the 90% delivery
time when a message is delivered via CD-BCAST and kneighbor-BCAST. The simulation setup was the same as that
described in Sect. 3.3, except for the epidemic broadcastingmechanisms and the change communication range and thenumber N of nodes. In k-neighbor-BCAST, each infected
node manages a holding message list and exchanges it withother nodes to track whether an encountered node is infected

WATABE and OHSAKI: CONTACT DURATION-AWARE EPIDEMIC BROADCASTING IN DELAY/DISRUPTION-TOLERANT NETWORKS

2397
Table 1 Performance of k-neighbor-BCAST with the parameter k = 1
for various communication range R.
R [m]
10
20
30
40
50
60
70
80
90 100 110 120 130 140 150
90% delivery 1343.8 807.1 574.7 497.1 430.8 360.3 293.1 227.5 182.3 139.9 109.5 78.7 59.9 54.1 37.8
time [s]The total number 88.9 88.7 87.5 85.5 83.1 77.8 73.6 65.6 61.3 53.2 50.5 44.6 41.6 38.8 35.3
of forwaridngs

Fig. 17 Ratio of 90% delivery times of each epidemic broadcastingmechanism to that of k-neighbor-BCAST with parameter k = 1 with changing communication range R for k-neighbor-BCAST and CD-BCAST.

Fig. 18 Ratio of the numbers of message forwardings of each epidemic
broadcasting mechanism to that of k-neighbor-BCAST with parameter k =1 with changing communication range R for k-neighbor-BCAST and CDBCAST.

or susceptible. In this simulation, CD-BCAST also used thesame approach. Note that these results cannot be directlycompared with the results of previous section because theexchange of holding message lists generates communication
overhead. In k-neighbor-BCAST, parameter k denotes thethreshold of the number of nodes within a communication
range of an infected node used for determining whether the
infected node should forward a message; we changed parameter k = 1, 2, 3, 4, and 5 for our simulation. Parameter
preceive was set at a fixed value 0.7.
Figure 17 shows the ratio of 90% delivery time ofeach epidemic broadcast mechanism to that of k-neighborBCAST with parameter k = 1, and Fig. 18 shows the ratioof the total number of forwardings of each epidemic broadcast mechanism to that of k-neighbor-BCAST with parameter k = 1 with the communication range R varied from 10
to 150 [m] with step size of 10 [m]. Note that each infected
node forwards a message immediately and minimizes themessage delivery delay when the parameter k of k-neighborBCAST is 1. 90% delivery time and the total number of forwardings of k-neighbor-BCAST with the parameter k = 1
for various R are shown in Table 1. We set the number M
of nodes to 100 in our simulation. According to Fig. 17, wefound that 90% delivery times of k-neighbor-BCAST weremuch larger than compared with minimized message delivery delay when the communication range was large and thearea over which message delivery delay was large depended

on parameter k. For example, if the communication range
is 60 [m], we should set parameter k to 3 or less to prevent large message delivery delay. In contrast, we foundthat CD-BCAST achieved a message delivery delay close to
the minimized value (i.e., the value of k-neighbor-BCASTwith parameter k = 1), because the ratio of the 90% delivery
times of each epidemic broadcast mechanism to that of kneighbor-BCAST with parameter k = 1 is almost 1. According to Fig. 18, we can find that larger k leads smaller numberof message forwardings, and k-neighbor-BCAST (k ≥ 2)
achieves a greater reduction of the forwarding number than
CD-BCAST when the communication range is small. However, message delivery delay of k-neighbor-BCAST (k ≥ 2)is remarkably large when the number of message forwardings of k-neighbor-BCAST (k ≥ 2) is smaller than that of
CD-BCAST (see Fig. 17). In contrast, without parametertuning, CD-BCAST achieves reduction of the number ofmessage forwardings while maintaining the small message
delivery delay. For example, if the communication range is
60 [m], we should set k to 3 to maximize the reduction of
message forwardings under the condition of small delivery
delay though CD-BCAST achieves almost same reduction
as that of k-neighbor-BCAST with parameter k = 3 withoutparameter tuning.
We also derived the ratio of 90% delivery times foreach epidemic broadcast mechanism to that of k-neighborBCAST with parameter k = 1 and the ratio of the total number of forwardings for each epidemic broadcast mechanism
to that of k-neighbor-BCAST with parameter k = 1, whilechanging the node density by changing the number M ofnodes in the simulation. Figures 19 and 20 show the ratiosof 90% delivery time and the total number of forwardings,
respectively, when the number of message forwardings ischanged from 50 to 150 at an interval of 10. We set communication range as 50 [m] in our simulation. 90% delivery time and the total number of forwardings of k-neighborBCAST with the parameter k = 1 for various M are shownin Table 2. Similar results to that of the simulation in which
we changed communication range were obtained.
Finally, we compared the performance of CD-BCAST
and k-neighbor-BCAST in the case where each infected
node managed history of message forwarding to track theinfection status of other nodes. In the original version of
k-neighbor-BCAST, each infected node managed a holding
message list and exchanged it to determine whether an encounter node was infected or susceptible. As mentioned
above, there are two options here: (1) manage a history of
message forwardings; and (2) manage a holding message
list. We considered the version of k-neighbor-BCAST in
which each infected node managed a history of message forwardings. Through simulations, we found that CD-BCAST

IEICE TRANS. COMMUN., VOL.E98–B, NO.12 DECEMBER 2015

2398

Fig. 19 Ratio of 90% delivery times of each epidemic broadcastingmechanism to that of k-neighbor-BCAST with parameter k = 1 with changing the number M of nodes for k-neighbor-BCAST and CD-BCAST.

Fig. 21 Relation between 90% delivery times and the total number ofmessage forwardings for the number M of nodes of 50, 100, and 150 wheneach infected node manages a history of message forwardings to track infection status of other nodes for k-neighbor-BCAST and CD-BCAST.

more, every time infected node I encounters a susceptiblenode, the node forwards message repeatedly unless the number of nodes within the communication range of infected
node I becomes less than k. In other words, the infected
node forwards the message to only one susceptible node ata time.
5. Conclusion and Future Work
Fig. 20 Ratio of the numbers of message forwardings of each epidemic
broadcasting mechanism to that of k-neighbor-BCAST with parameter k =1 with changing the number M of nodes for k-neighbor-BCAST and CDBCAST.
Table 2 Performance of k-neighbor-BCAST with the parameter k = 1
for various communication range M.
M
50
60
70
80
90
100 110 120 130 140 150
90% delivery 593.7 539.9 506.8 466.7 441.6 427.9 391.5 368.3 365.3 355.3 335.0
time [s]The total number 43.0 51.3 59.6 67.0 74.7 81.9 88.9 96.2 104.2 109.8 115.1
of forwaridngs

provided better performance k-neighbor-BCAST, regardless of approaches (1) and (2) above. The simulation setup
was the same as the one described in Sect. 3.3, except for
the number M of nodes and epidemic broadcasting mechanisms. Figure 21 shows 90% delivery times and the total
number of message forwardings. Respective points for CDBCAST in the figure are related to results for preceive = 1,
0.9, 0.7, 0.5, 0.3, and 0.1 in order from left to right. Similarly, respective points for k-neighbor-BCAST in the figure
are related to results for k = 1, 2, and 3 in order from left
to right. Simulation results indicated that CD-BCAST provided performance superior to that of k-neighbor-BCAST
because all curves for CD-BCAST are lower than that of kneighbor-BCAST. The reason for this is that infected nodes
were often mistaken for a susceptible node when we usedapproach (1) in which a history of message forwardings ismaintained; in such case, it repeats ineﬃcient message forwardings. For example, if infected node I forwards a message to k nodes within its communication range and a susceptible node enters the communication range of node I,
node I forwards the message again to k + 1 nodes. Further-In this paper, we proposed CD-BCAST, which substantiallyreduces the number of message forwardings while holding
the message delivery delay small without parameter tuning
depending on changes in communication range and nodedensity. Through multiple simulations, we showed that CDBCAST reduced the total message forwarding number by
10%-40% as compared to that of HSA-BCAST, and this reduction was achieved without parameter tuning under varieties of communication ranges and node densities; although,k-neighbor-BCAST requires the tuning.
In future, we plan to evaluate the performance of CDBCAST under more realistic conditions. In real world
DTNs, several factors that aﬀect the performance of epidemic broadcasting should be considered including message
size, queuing of messages, propagation delay, heterogeneityof nodes, energy and bandwidth consumption, mobility patterns, traﬃc patterns, and so on. Furthermore, we plan to
study how best to determine whether an encountered node
is infected or susceptible.
Acknowledgments
This work was partly supported by JSPS Grants-in-Aid
for Scientific Research Number 25280030, JSPS Grant-inAid for Young Scientists (Start-up) Number 26880008, and
JSPS Grant-in-Aid for JSPS Fellows Grant Number 24 ·3184.
References[1] K. Fall, “A delay-tolerant network architecture for challenged internets,” Proc. 2003 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, SIG-

WATABE and OHSAKI: CONTACT DURATION-AWARE EPIDEMIC BROADCASTING IN DELAY/DISRUPTION-TOLERANT NETWORKS

2399

COMM’03, pp.27–34, 2003.
[2] L. Pelusi, A. Passarella, and M. Conti, “Opportunistic networking:
Data forwarding in disconnected mobile ad hoc networks,” IEEE
Commun. Mag., vol.44, no.11, pp.134–141, Nov. 2006.
[3] A. Lindgren and P. Hui, “The quest for a killer app for opportunisticand delay tolerant networks,” Proc. 4th ACM workshop on Challenged networks, CHANTS’09, pp.59–66, 2009.
[4] S. Corson and J. Macker, “Mobile ad hoc networking (MANET):
Routing protocol performance issues and evaluation considerations,”
RFC2501, Jan. 1999.
[5] C.E. Perkins and E.M. Royer, “Ad-hoc on-demand distance vector routing,” Proc. WMCSA’99. Second IEEE Workshop on Mobile
Computing Systems and Applications, pp.90–100, 1999.
[6] D.B. Johnson and D.A. Maltz, “Dynamic source routing in ad
hoc wireless networks,” in Mobile Computing, ch. 5, pp.153–181,
Kluwer Academic Publishers, 1996.
[7] M.-C. Chuah, P. Yang, B.D. Davison, and L. Cheng, “Store-andforward performance in a DTN,” Proc. 2006 IEEE 63rd VehicularTechnology Conference, pp.187–191, 2006.
[8] S. Burleigh, A. Hooke, L. Torgerson, K. Fall, V. Cerf, B. Durst,
K. Scott, and H. Weiss, “Delay-tolerant networking: An approach
to interplanetary Internet,” IEEE Commun. Mag., vol.41, no.6,
pp.128–136, June 2003.
[9] S. Saha, Sushovan, A. Sheldekar, R. Joseph C., A. Mukherjee, and
S. Nandi, “Post disaster management using delay tolerant network,”
Recent Trends in Wireless and Mobile Networks, Communications
in Computer and Information Science, vol.162, pp.170–184, June
2011.
[10] L. Selavo, A. Wood, Q. Cao, T. Sookoor, H. Liu, A. Srinivasan, Y.
Wu, W. Kang, J. Stankovic, D. Young, and J. Porter, “LUSTER:
Wireless sensor network for environmental research,” Proc. 5th International Conference on Embedded Networked Sensor Systems,
SenSys’07, pp.103–116, 2007.
[11] G. Gamberini, F. Giudici, E. Pagani, and G.P. Rossi, “Impact of history on epidemic broadcast in DTNs,” Proc. 2008 1st IFIP WirelessDays, pp.1–5, 2008.
[12] H. Gong and J.W. Kim, “A prioritization-based application-oriented
broadcast protocol for delay-tolerant networks,” Proc. 2009 IEEE
Wireless Communications and Networking Conference, pp.1–6,
2009.
[13] A. Goundan, E. Coe, and C.S. Raghavendra, “Eﬃcient broadcastingin delay tolerant networks,” Proc. IEEE GLOBECOM 2008, 2008
IEEE Global Telecommunications Conference, pp.1–5, 2008.
[14] H. Ohsaki, Y. Yamada, D. Perrin, and M. Imase, “Impact of mobility
constraints on epidemic broadcast mechanisms in delay-tolerant networks,” 2012 26th International Conference on Advanced Information Networking and Applications Workshops, pp.1131–1136, 2012.
[15] F.-Y. Lee, S.-I. Sou, and P. Lin, “Social-based broadcasting for delay
tolerant network,” Proc. 2013 IEEE Wireless Communications andNetworking Conference (WCNC), pp.2250–2254, 2013.
[16] I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A
survey on sensor networks,” IEEE Commun. Mag., vol.40, no.8,
pp.102–114, Aug. 2002.
[17] Y. Yang, M.I. Fonoage, and M. Cardei, “Improving network lifetime
with mobile wireless sensor networks,” Comput. Commun., vol.33,
no.4, pp.409–419, March 2010.
[18] F. Giudici, E. Pagani, and G.P. Rossi, “Impact of mobility on
epidemic broadcast in DTNs,” Wireless and Mobile Networking,vol.284, pp.421–434, 2008.
[19] F. Giudici, E. Pagani, and G.P. Rossi, “Self-adaptive and statelessbroadcast in delay and disruption tolerant networks,” Proc. 6th Italian Networking Workshop, Cortina d’Ampezzo, Italy, Jan. 2009.
[20] P. Samar and S.B. Wicker, “On the behavior of communication links
of a node in a multi-hop mobile environment,” Proc. 5th ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc’04, pp.145–156, 2004.
[21] P. Samar and S.B. Wicker, “Link dynamics and protocol design in a

multihop mobile environment,” IEEE Trans. Mobile Comput., vol.5,
no.9, pp.1156–1172, Sept. 2006.
[22] T. Camp, J. Boleng, and V. Davies, “A survey of mobility models forad hoc network research,” Wirel. Commun. Mob. Comput., vol.2,
no.5, pp.483–502, Sept. 2002.

Kohei Watabe
received his B.E. and M.E.
degrees in Engineering from Tokyo Metropolitan University, Tokyo, Japan, in 2009 and 2011,
respectively. He also received the Ph.D. degree from Osaka University, Japan, in 2014. He
was a JSPS research fellow (DC2) from April
2012 to March 2014. He has been an AssistantProfessor of Graduate School of Engineering,
Nagaoka University of Technology since April
2014. He is a member of the IEEE and the
IEICE.

Hiroyuki Ohsaki
received the M.E. degree in the Information and Computer Sciencesfrom Osaka University, Osaka, Japan, in 1995.
He also received the Ph.D. degree from Osaka
University, Osaka, Japan, in 1997. He is currently a professor at Department of Informatics, School of Science and Technology, Kwansei Gakuin University, Japan. His research work
is in the area of design, modeling, and controlof large-scale communication networks. He is amember of IEEE, IEICE, and IPSJ. His e-mailaddress is ohsaki@kwansei.ac.jp