This is the post-print version. The original publication is available at https://doi.org/10.1109/WMNC.2013.6549004. (c) IFIP, 2013. This is the author's version of the work. It is posted here by permission of IFIP for your personal use. Not forredistribution. The definitive version was published in Proceedings of the 6th Joint IFIP Wireless and Mobile Networking Conference (WMNC 2013).

An Epidemic Broadcasting Mechanism in
Delay/Disruption-Tolerant Networks
Utilizing Contact Duration Distribution
Kosuke Matsuda, Kohei Watabe and Hiroyuki Ohsaki
Department of Information Networking
Graduate School of Information Science and Technology
Osaka University, Suita-shi, Osaka 562–0031, Japan
Email: {k-matsuda, k-watabe, oosaki}@ist.osaka-u.ac.jp
Abstract—Epidemic broadcasting, in which an infected
node repeatedly forwards a copy of a message to other nodes,
realizes one-to-many communication in delay/disruptiontolerant networks. In epidemic broadcasting, the key is tocontrol the number of message forwardings among nodes
while maintaining a short message delivery time in the
network. In this paper, we present a novel idea for improving
the performance of epidemic broadcasting: when an infected
node encounters a (possibly) susceptible node, the infected
node intentionally delays its message forwarding since thismay increase the chance of simultaneous transmission tomultiple susceptible nodes. On the basis of this idea, we propose HCD-BCAST (History-based Contact Duration aware
BroadCAST), which significantly reduces the number of message forwardings. In HCD-BCAST, each node autonomously
determines the message forwarding delay based on the contact
duration distribution measured by that node. Through simulations, we show that HCD-BCAST achieves a reduction of
approximately 10-40% in the number of message forwardings
compared with history-based self-adaptive broadcast and kneighbor broadcast.

I.

I NTRODUCTION

In recent years, DTNs (Delay/disruption-Tolerant Networks) [1], [2] which realize communication under conditions where continuous end-to-end connection is notguaranteed, have attracted considerable attention. For instance, in MANET (Mobile Ad-hoc NETwork) [3], which
is a type of DTN, network links between nodes change
frequently due to node movement. Therefore, conventional
communication methods for realizing end-to-end network
connections cannot be applied to DTNs without being
modified [4], [5]. In many DTNs, a message is transmitted
by store-and-carry forwarding [6] for one-to-many communication that utilizes the mobility of nodes. Examples ofapplications of DTNs [7] include conceptual interplanetarycommunication networks [8], temporary communication
networks in disaster-affected areas [9] and sensor network
used for observing animals in their natural habitats [10] .
DTNs utilize epidemic broadcasting, where an infected
node forwards a copy of a message to other nodes forrealizing one-to-many communication. In simple epidemic
broadcasting, the number of duplicate messages increases
exponentially with time. Therefore, in DTNs, it is critical tosuppress duplicate message forwarding while maintaining
the necessary time of message delivery.

A conventional approach for reducing the number ofmessage forwardings in epidemic broadcasting is to avoid
duplicate message forwarding from a node to other infected
nodes. For instance, SA-BCAST (Self-Adaptive BroadCAST) [11] suppresses duplicate message forwarding byexponentially reducing the message forwarding probability
according to the number of received duplicate messages.
In HP-BCAST (History-based P-BCAST) [12], [13], eachnode manages its own history of message transmission
and suppresses duplicate message forwarding by skipping
message forwarding to infected nodes. There is also HSABCAST (History-based Self-Adaptive BroadCAST), whichuses both adaptive control of transmission probability as
found in SA-BCAST and management of message transmission history as found in HP-BCAST. HSA-BCAST can
efficiently broadcast messages to the whole network while
keeping the number of message forwardings small.
On the other hand, there is a approach to reduce thenumber of message forwardings by utilizing the characteristics of radio communication and delivering a message tomultiple nodes simultaneously. In epidemic broadcasting
using radio communication, a certain node broadcasts a
message to other nodes within its radio communication
range. Radio communication allows for a message to bedelivered to multiple nodes simultaneously. Against thisbackground, epidemic broadcasting methods for raising theefficiency of DTNs have been proposed [14], [15]. For
instance, in k-neighbor-BCAST [14], a node broadcasts
a message only when more than k nodes are within its
communication range. A node broadcasts a message only
when it detects at least one susceptible node and morethan k (susceptible or infected) nodes within its communication range. Therefore, nodes can deliver a message
to multiple nodes simultaneously by means of a single
message forwarding utilizing the characteristics of radio
communication.
An infected node has to wait to forward a message
until it is ready to communicate with multiple susceptible
nodes simultaneously in order to increase the numberof simultaneous transmissions to multiple nodes, but thewaiting (delay) lengthens the necessary time of message
delivery. Though k-neighbor-BCAST increases the number of simultaneous transmissions, the necessary time of
message delivery is sensitive to its control parameter kand it is difficult to decide appropriate k. If k is too large
value, an infected node continues waiting until it is readyto communicate with k nodes simultaneously, and misses
the chance of message forwarding.
In order to increase the number of simultaneous transmissions while maintaining the necessary time of message
delivery, an infected node is necessary to assign a suitablemessage forwarding delay when it encounters a susceptible
node. When an infected node encounters a susceptiblenode, the infected node should not forward its message
immediately, but instead should intentionally delay its
message forwarding until other susceptible nodes enter its
radio communication range since this may increase thechance of simultaneous transmission to multiple susceptible
nodes. If the message forwarding delay is too short, thepossibility that other susceptible nodes might enter theradio communication range of the infected node becomes
low, and we cannot fully utilize the broadcasting characteristics. If the message forwarding delay is too long, however,susceptible nodes that were ready to communicate with theinfected node may leave its radio communication range,leading to failed message transmission and consequently
lengthening the necessary time of message delivery inepidemic broadcasting. Therefore, it is essential to selectan appropriate message forwarding delay that utilizes thecharacteristics of broadcasting by radio communication
while maintaining the necessary time of message delivery.
In this paper, we propose a History-based Contact
Duration BroadCAST (HCD-BCAST) mechanism that cansignificantly reduce the number of message forwardings
while maintaining the necessary time of message delivery
by intentionally delaying message forwarding on the basisof the contact duration distribution measured by each node.
Through simulations, we show that HCD-BCAST achieves
a reduction of approximately 10-40% in the number ofmessage forwardings compared with history-based selfadaptive broadcast and k-neighbor broadcast.
The remainder of this paper is organized as follows.
Section II explains the idea behind the proposed HCDBCAST mechanism and the operation of each node. Section III investigates the characteristics of HCD-BCAST
and evaluates the effectiveness of the proposed mechanism
through simulations.
II.

HCD-BCAST (H ISTORY- BASED C ONTACT
D URATION - AWARE B ROADCASTING )A. Idea
We expect that when an infected node encounters asusceptible node, the infected node can forward a message
to multiple nodes by means of a single message forwarding
if the message is not forwarded immediately but with acertain delay which allows other susceptible nodes to enter
the radio communication range.
We show an example in Figure 1. At time t = 2, an
infected node encounters a susceptible node. When all
nodes move, the infected node encounters an additional
susceptible node at time t = 3. If the infected node forwards
a message not at time t = 2 but at time t = 3, the infected

node can transmit a message to two susceptible nodes
simultaneously.
When the message forwarding delay is too short, thelikelihood that other susceptible nodes will enter the radio communication range of the infected node is low,
and infected nodes cannot fully utilize the characteristics
of broadcasting by radio communication. If the message
forwarding delay is too long, however, susceptible nodes
that were originally ready to communicate with the infected node may leave its radio communication range, andmessage forwarding may become impossible. Therefore,
an efficient epidemic broadcasting mechanism must beable to choose an appropriate message forwarding delaythat utilizes the characteristics of broadcasting by radio
communication while maintaining the necessary time of
message delivery.
We consider that the message forwarding delay should
be determined by two factors, namely (a) the contact
duration distribution of infected and susceptible nodes, and(b) the number of infected nodes around a susceptible node.
By using (a), an infected node can determine theprobability that a susceptible node might leave its radio
communication range if the infected node delays message
forwarding. If we assume that the contact duration distribution is stationary, each node can derive the contact duration
distribution by recording the duration of contact with othernodes encountered in the past. Note that the derivationis achieved without an extra communication since nodes
are habitually watching nodes within their communication
range.
By using (b), an infected node can set a message
forwarding delay according to the situation at hand while
maintaining high transmission probability to susceptible
nodes. When the message forwarding delay is long, an
infected node may be unable to forward messages tosusceptible nodes because they may leave its radio communication range. However, when there are other infected
nodes, the susceptible node may be able to receive amessage from these nodes. Hence, we consider that themessage forwarding delay should be controlled according
to the number of susceptible nodes.
B. Operation
In the proposed HCD-BCAST mechanism, each nodemeasures the distribution of the duration of contact withother nodes, and HCD-BCAST can significantly decrease
the number of message forwardings while maintaining ashort message delivery time by intentionally delaying message forwarding based on the measured contact duration
distribution.
In HCD-BCAST, each node measures its own contact
duration distribution, which the node uses to set its message
forwarding delay such that the forwarding probability inthe cluster becomes a constant. HCD-BCAST manages thehistory of message transmission by the same method as HPBCAST. Infected nodes determine their respective message
forwarding delays based on their own contact duration
distributions and the number of infected nodes around theencountered susceptible node.

an	
  infected	
  node	a	
  suscep0ble	
  node	communica0on	
  range	

t	
  	
  =	
  	
  1	

an	
  infected	
  node	a	
  suscep0ble	
  node	

t	
  	
  =	
  	
  3	

an	
  infected	
  node	a	
  suscep0ble	
  node	communica0on	
  range	

t	
  	
  =	
  	
  2	
Fig. 1.

communica0on	
  range	an	
  infected	
  node	a	
  suscep0ble	
  node	

t	
  	
  =	
  	
  4	

communica0on	
  range	An example where the characteristics of broadcasting by radio communication are utilized by introducing a message forwarding
delay

Below, we explain how HCD-BCAST sets the message
forwarding delay.

a message if node S resides within its radio communication
range after TS has elapsed.

Here, we assume that there are N infected nodes
I1 . . . IN around a new neighbor node S, and that thesenodes forward a message with the same probability p.
In such a situation, the probability psuccess that node S
receives a message at least once is given by

However, the number N of infected nodes around node
S is needed in order to determine TS from Eq. (4). We
use N̂ to denote the derived number of infected nodes
within the radio communication range when an infected
node encounters node S.

psuccess=

1 − (1 − p)N .

(1)

Therefore, in order to control the probability psuccess ,infected nodes I1 , . . . , IN should set their forwarding probability p as follows:p= 1 − (1 − psuccess )1/N .

(2)In this way, infected nodes adjust the message forwarding delay so that the forwarding probability satisfies
Eq. (2) with their own contact duration distribution. We
let P (x) denote the cumulative distribution function of
the measured contact duration distribution, and all nodes
I1 . . . IN delay message forwarding for TS , satisfying thefollowing equation:
1 − P (TS ) = p.

(3)

Namely,TS−1==

P −1 (1 − p)
P −1 ((1 − psuccess )1/N ),(4)

where P (TS ) is the inverse function of P (x). The
infected nodes delay message forwarding for TS upon encountering susceptible node S. The infected node forwards

By following this operation, HCD-BCAST can substantially reduce the number of message forwardings by deliberately delaying message forwarding while maintaining ahigh success rate of message forwarding to node S fromnodes I1 . . . IN with a probability of psuccess .
psuccess is a control parameter that adjusts the rapidityof message delivery. A larger value of psuccess leads toa shorter message forwarding delay, and infected nodes
forward messages more often. Note that in the case of
psuccess = 1, HCD-BCAST is equivalent to the HP-BCAST
algorithm.
The algorithm of the HCD-BCAST is shown in thepseudocode in Algorithm 1. When a new node S enters into
the communication range of an infected node, the infected
node sets the message delay TS if it does not have a recordof the transmission history of the new node. F1 denotes psatisfies Eq. (2), and F2 denotes TS satisfies Eq. (4) (lines2-7). Then, the infected node broadcasts a message to its
neighbors and disables timer TS if any TS expires and the
new node S is still within the communication range. (lines8-17).

Algorithm 1 Pseudocode for the HCD-BCAST algorithm
1: while True do
2:
if new neighbor node S then3:
if there is no history of communication with the
new neighbor node S then4:p ← F1 (psuccess , N );5:TS ← F2 (p, P (x));
6:
end if7:
end if8:
for all TS do
9:if timer TS expires then10:
if the node S is still within the range then
11:
Broadcast message to neighbors;
12:for all TS do
13:
disable timer TS
14:
end for15:
end if16:
end if17:
end for
18: end whileIII.

S IMULATION

A. Characteristics of HCD-BCAST
We investigated the following characteristics of HCDBCAST through simple simulations.
1)

Accuracy of estimating N , which denotes thenumber of infected nodes around a susceptible
node S

2)

Success rate of message transmission from infected node I1 . . . IN to susceptible node S

3)

The reduction in the number of message forwardings by intentionally delaying message forwarding

First, we investigated the accuracy of estimating N ,which denotes the number of infected nodes around a susceptible node S. HCD-BCAST derives N̂ , which denotes
the number of infected nodes at the moment when an
infected node encounters susceptible node S. Below, we
define N as the number of infected nodes that susceptible
node S encounters for an average contact duration T after
the encounter between the susceptible node S and an
infected node.
In our simulation, 100 nodes moved according toa random waypoint mobility model [16] in a 1000 ×1000 [m] simulation field. At the initial state, only a single
node broadcast a message to all other nodes with HCDBCAST. The velocity of nodes was uniformly distributedin [1, 2] [m/s]. The radio communication range of nodes
was 25, 50 or 75 [m], with an average contact duration Tof 20, 38 or 56 [s] respectively.
In our simulation, we measured N and N̂ and calculated MAE (Mean Absolute Error) of N̂ with respect to N .
When the radio communication range was 25, 50 or 75 [m],MAE of N was 0.27, 0.92 and 1.60, and the average of N
was 1.35, 2.59 and 4.22. Therefore, we consider that HCDBCAST achieves a certain level of accuracy in estimating
N with increasing communication range.

Fig. 2: Simulation model for investigating the successrate of message transmission from infected nodes
I1 . . . IN to susceptible node S

Next, we investigated the success rate of message transmission from infected nodes I1 , I,2 , . . . , IN to susceptible
node S. If HCD-BCAST operates completely as expected,
the success rate of message transmission should perfectly
correspond to the value of the control parameter psuccess .
To measure the success rate of message transmission,
we carried out the simulation shown in Figure 2. Wechanged the number of infected nodes in node clusters
between 1 and 4, and varied the value of the control
parameter psuccess . We repeated the simulation 30 times
with the same conditions and measured the rate at whicha susceptible node was able to receive a message upon
approaching a cluster of infected nodes. In our simulation,
the initial positions of infected nodes were uniformly
distributed inside of a circle 50 [m] in diameter, and theradio communication range of all nodes was 50 [m]. wegave these nodes contact duration distribution in advance.
Figure 3 shows the success rate of message transmission
when we varied the number of infected nodes between
1 and 4. This result shows that the success rate of message transmission approximately corresponds to the valueof control parameter psuccess . It appears that there is aparticularly close correspondence between the success rateof message transmission and psuccess when the number of
infected nodes is small and the value of psuccess is relatively
small .
In contrast, when the number of infected nodes issmall and the value of psuccess is large, the success rateof message transmission is slightly lower than psuccess .
Theoretically, the success rate of message transmission
is equal to psuccess if the durations of contact between
each infected node and a susceptible node are independentof each other. However, the contact durations are notindependent due to the speed of susceptible nodes. If the
speed of susceptible nodes is high, the respective contact
durations for all infected nodes are short. Hence, thecontact durations are interrelated.
Finally, we investigated the reduction in the number ofmessage forwardings resulting from intentionally delaying
message forwarding. Again, we used the abovementioned
simulation setup with 100 nodes moving according toa random waypoint mobility model. We measured how
many susceptible nodes were able to receive the message

Success rate ofmessage transmission

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
1

2

3

4

Number of node in a cluster
psuccess = 0.9
psuccess = 0.7
psuccess = 0.5

psuccess = 0.3
psuccess = 0.1

Fig. 3: Relation between the number of infected nodes in acluster and the success rate of message transmission

simultaneously by means of a single message forwarding
until 90% of all nodes received the message. We repeatedthe simulation 30 times and calculated the number of nodes
that simultaneously received the message.
Figure 4 shows the ratio of the number of nodes thatsimultaneously received a message by a single message
forwarding when psuccess was varied between 0.1 and1.0. Note that the legend 0 node represent a message
forwarding to an infected node that has already had themessage. This result shows that a smaller value of psuccessincreases the chance of infected nodes delivering a message
simultaneously to multiple nodes by a single forwarding.
Namely, HCD-BCAST can utilize the characteristics ofbroadcasting when psuccess is small (i.e., when message
forwarding is intentionally delayed).
B. Performance comparison with HSA-BCAST and kneighbor-BCAST
To verify the effectiveness of the proposed HCDBCAST mechanism under various conditions, we compared
the performance of HCD-BCAST with those of the conventional mechanisms, HSA-BCAST and k-neighbor-BCAST.
We ran the simulation described in Section III-A andmeasured the total number of message forwardings andthe time until 90% of all nodes received the message(90% delivery time). To focus on the characteristics, we
assumed that there was no delay in radio communication
and all nodes had enough storage to record their respective
message transmission histories.
HSA-BCAST and HCD-BCAST judge whether an
encounter node is susceptible or infected with message
transmission histories. On the other hand, k-neighborBCAST judges whether an encounter node is susceptible or infected by querying the node without message
transmission histories [14]. In this simulation, to focus
on the timing and frequency of message forwardings, we
use k-neighbor-BCAST that is incorporated in message
transmission histories [12], [13].

Fig. 4: Ratio of the number of nodes that simultaneously
receive a message by means of a single message
forwarding when control parameter psuccess is varied between 0.1 and 1.0

In general, the performance of an epidemic broadcasting mechanism is heavily depndent on the choiceof control parameters. Therefore, in our simulation, we
compare the performances of HCD-BCAST, HSA-BCAST,
and k-neighbor-BCAST, under a diverse range of control
parameters.
In the simulation, we changed the control parameters
Nth and c of HSA-BCAST [11], where Nth denotes thethreshold of the change rate in the number of nodes within
the communication range of an infected node used for
determining whether the infected node should forward a
message. Here, c is a parameter which determines an
exponential decay in the forwarding probability according
to the number of duplicate messages received by othernodes.
Similarly, we changed the control parameter k of kneighbor-BCAST [14], where k denotes the threshold of
the number of nodes within the communication range
used for determining whether to broadcast a message. An
infected node broadcasts a message only when it detects
more than k nodes within its communication range. An
infected node broadcasts a message only when it detects atleast one susceptible node and more than k (susceptible orinfected) nodes within its communication range.
We show the 90% delivery time and the total numberof message forwardings for a field size of 1000 × 1000 [m]and a communication range of 50 [m] in Figure 5. In
epidemic broadcasting, there is a trade-off between rapidity
and efficiency 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

250

200

200

150

100
HSA-BCAST(Nth = 0.0)
HSA-BCAST(Nth = 0.25)
HSA-BCAST(Nth = 0.50)
HSA-BCAST(Nth = 0.75)
HCD-BCAST

50

Total number ofmessage forwardings

Total number ofmessage forwardings

250

150
100
50
k-neighbor-BCAST
HCD-BCAST
0

0
0

250

500

0

750 1000 1250 1500 1750 2000
90% delivery time [s]Fig. 5: Relation between 90% delivery time and total number of message forwardings for a field size of1000 × 1000 [m] and a radio communication rangeof 50 [m] (HSA-BCAST vs. HCD-BCAST)

Fig. 6: Relation between 90% delivery time and total number of message forwardings for a field size of1000 × 1000 [m] and a radio communication rangeof 50 [m] (k-neighbor-BCAST vs. HCD-BCAST)
250

broadcasting mechanism.

We compared the performance of HCD-BCAST withthat of HSA-BCAST in detail. To verify the effectivenessof HCD-BCAST under various conditions, we simulated
HCD-BCAST and HSA-BCAST for different radio communication ranges and node densities in the field.
We investigated the impact of the communication range
through simulations for various numbers of nodes. Figure 7
shows the relation between 90% delivery time and thetotal number of message forwardings for a field size of1000 × 1000 [m] and a radio communication range of 25,
50 and 75 [m]. We set the parameter Nth of HSA-BCAST
to 0.75 because at this value HSA-BCAST showed the mostfavorable characteristics .
In Figure 7, all curves for HCD-BCAST are located below and to the left of those for HSA-BCAST. This indicatesthat the performance of HCD-BCAST is higher than that of
HSA-BCAST regardless of the radio communication range(see Fig. 7).

200
Total number ofmessage forwardings

Figures 5 and 6 show that HCD-BCAST realizes a rateof message delivery equivalent to that of HSA-BCAST andk-neighbor-BCAST by means of a small number of message forwardings. HCD-BCAST achieves a reduction of
approximately 10-40% in the number of message forwardings compared to HSA-BCAST and k-neighbor-BCAST.
The points for HCD-BCAST in the figure correspond to theresults for psuccess = 1, 0.9, 0.7, 0.5, 0.3 and 0.1. Similarly,
the points for HSA-BCAST in the figure correspond to
the results for c = 1, 2, 4 and 8. The points for kneighbor-BCAST in the figure correspond to the results
for k = 1, 2 and 3. On the left of the graph, the points
for HCD-BCAST, HSA-BCAST and k-neighbor-BCAST
overlap because these points respectively represent theresults for psuccess = 1, c = 1 and k = 1; in other words,
these parameters do not control the message forwarding as
they do in HP-BCAST.

250 500 750 1000 1250 1500 1750 2000
90% delivery time [s]

150

100
HSA-BCAST(R = 25)
HCD-BCAST(R = 25)
HSA-BCAST(R = 50)
HCD-BCAST(R = 50)
HSA-BCAST(R = 75)
HCD-BCAST(R = 75)

50

0
0

250

500

750 1000 1250 1500 1750 2000
90% delivery time [s]Fig. 7: Relation between 90% delivery time and total number of message forwardings for a field size of1000 × 1000 [m] and a radio communication rangeof 25, 50 and 75 [m] (HSA-BCAST vs. HCDBCAST)

We also investigated the impact of node density throughsimulations with various numbers of nodes. Figure 8 shows
the relation between 90% delivery time and the total
number of message forwardings for a radio communication
range of 50 [m] and a number of nodes of 50, 100 and
150. We set the control parameter Nth of HSA-BCAST to
0.75. The simulation results indicate that the performanceof HCD-BCAST is higher compared with that of HSABCAST because all curves for HCD-BCAST are locatedbelow and to the left of those for HSA-BCAST. This
indicates that the performance of HCD-BCAST is higher
than that of HSA-BCAST regardless of the node density.
HCD-BCAST shows higher performance than HSA-

250
HSA-BCAST(N = 150)
HCD-BCAST(N = 150)
HSA-BCAST(N = 100)
HCD-BCAST(N = 100)
HSA-BCAST(N = 50)
HCD-BCAST(N = 50)

Total number ofmessage forwardings

350
300
250
200
150
100

200
Total number ofmessage forwardings

400

150

100
k-neighbor-BCAST(R = 25)
HCD-BCAST(R = 25)
k-neighbor-BCAST(R = 50)
HCD-BCAST(R = 50)
k-neighbor-BCAST(R = 75)
HCD-BCAST(R = 75)

50

50
0

0
0

250

500

750 1000 1250 1500 1750 2000
90% delivery time [s]Fig. 8: Relation between 90% delivery time and total number of message forwardings for a radio communication range of 50 [m] and a number of nodes of50, 100 and 150 (HSA-BCAST vs. HCD-BCAST)

BCAST regardless of the communication range and thenode density. The main reasons for this are that while
HSA-BCAST reduces the number of duplicate message
forwardings by reducing the forwarding probability according to the number of duplicate message receptions, itdoes not have any mechanism for increasing the numberof transmissions to multiple nodes by a single message
forwarding. On the other hand, HCD-BCAST increases
the number of successful transmissions to multiple nodes
by a single message forwarding by intentionally delaying
message forwarding.
Next, we compared the performance of HCD-BCASTwith that of k-neighbor-BCAST. Similarly, we simulated
HCD-BCAST and k-neighbor-BCAST with different radio
communication ranges and node densities in the field. In theoriginal version of k-neighbor-BCAST, the control parameter k is restricted to integer values. To relax this restriction,
we added a trivial extension to the k-neighbor-BCAST
algorithm allowing the control parameter k (i < k < i + 1)
to take non-integer values, whereby infected nodes chose ias the threshold with probability i + 1 − k and i + 1 withprobability k − 1.
Figure 9 shows the relation between 90% delivery time
and the total number of message forwardings for a fieldsize of 1000 × 1000 [m] and a radio communication range
R of 25, 50 and 75 [m]. We varied the parameter k of
k-neighbor-BCAST between 1, 1.25, 1.5 and 1.75 when R
was 25 and between 1, 2 and 3 when R was 50 or 75. The
simulation results indicate that HCD-BCAST provides performance superior to that of k-neighbor-BCAST because
all curves for HCD-BCAST are located below and to theleft of those for k-neighbor-BCAST. Therefore, the results
indicate that HCD-BCAST shows better characteristics
than HSA-BCAST regardless of the radio communication
range and the node density.
Next, we investigated the impact of node density

0

250

500

750 1000 1250 1500 1750 2000
90% delivery time [s]Fig. 9: Relation between 90% delivery time and total number of message forwardings for a field size of1000 × 1000 [m] and a radio communication rangeof 25, 50 and 75 [m] (k-neighbor-BCAST vs. HCDBCAST)

through simulations with various numbers of nodes. Figure 10 shows the relation between 90% delivery time
and the total number of message forwardings for a radio
communication range of 50 [m] and a number of nodes of50, 100 and 150. We changed the control parameter k for
k-neighbor-BCAST between 1, 2 and 3. The simulation
results indicate that HCD-BCAST provides performancesuperior to that of k-neighbor-BCAST, except in the caseof the lowest node density. In Figure 10, although thecurves at N = 50 almost overlap, the curves for HCDBCAST at N = 100 and 150 are located below and to
the left of those for k-neighbor-BCAST, indicating that theperformance of HCD-BCAST is higher than that of HSABCAST regardless of the number of nodes.
Compared with k-neighbor-BCAST, HCD-BCAST
shows higher performance regardless of the communication
range and the node density. The main reasons for thisare as follows. Unlike HSA-BCAST, k-neighbor-BCAST
has a mechanism that increases the number of transmissions to multiple nodes by means of a single message
forwarding because in k-neighbor-BCAST an infected nodebroadcasts a message only when there are more than knodes (including at least one susceptible node) within thecommunication range of the broadcasting node. However,k-neighbor-BCAST does not fully utilize the characteristics
of broadcasting, even though infected nodes transmit tomultiple nodes by means of a single message forwarding.
For instance, if an infected node I broadcasts a message tok nodes within its communication range and a susceptible
node enters the communication range of node I, node I
broadcasts the message again to k + 1 nodes. Moreover,every time the infected node I detects a susceptible node,
the former broadcasts repeatedly unless the number ofnodes within the communication range of infected node
I becomes less than k. In other words, the infected node
forwards the message to only a single susceptible node.

400

k-neighbor-BCAST(N = 150)
HCD-BCAST(N = 150)
k-neighbor-BCAST(N = 100)
HCD-BCAST(N = 100)k-neighbor-BCAST(N = 50)
HCD-BCAST(N = 50)

Total number ofmessage forwardings

350
300
250
200
150
100
50
0
0

250

500

750 1000 1250 1500 1750 2000
90% delivery time [s]Fig. 10: Relation between 90% delivery time and total
number of message forwardings for a radio communication range of 50 [m] and a number of nodesof 50, 100 and 150 (k-neighbor-BCAST vs. HCDBCAST)This problem is especially likely to occur when the contact
duration is long and the frequency of contact among nodes
is high. As Figures 9 and 10 suggest, when the communication range is wide (i.e., the contact duration is long) andthe density of nodes is high (i.e., the frequency of contact ishigh), there is a notable difference in performance between
HCD-BCAST and k-neighbor-BCAST.
IV.

C ONCLUSION AND F UTURE W ORK

In this paper, we have proposed HCD-BCAST, whichsignificantly reduces the number of message forwardings
while maintaining the rapidity of message delivery. In
HCD-BCAST, each node independently determines themessage forwarding delay based on the contact duration
distribution measured by that node. Through simulations,
we have shown that HCD-BCAST achieves a reduction of
approximately 10-40% in the number of message forwardings compared with HSA-BCAST and k-neighbor-BCAST.
In future work, we plan to evaluate the performanceof HCD-BCAST with realistic mobility models, radio
communication models and traffic patterns. Furthermore,
the evaluation of the rapidity and efficiency of message
delivery of HCD-BCAST by mathematical analysis is also
important. We plan to extend HCD-BCAST in order tomake it applicable to environments where the contact
duration distribution is not stationary, by renewing the
distribution. In addition, it would also be useful to devise
a mechanism for adaptive tuning of the control parameter
psuccess of HCD-BCAST, which controls the success rateof message transmission. We expect the performance of
HCD-BCAST to improve if the control parameter psuccess
is tuned adaptively according to the communication range.
ACKNOWLEDGMENT
This work was supported by JSPS Grant-in-Aid for
JSPS Fellows Grant Number 24 · 3184.

R EFERENCES[1] K. Fall, “A Delay-Tolerant Network Architecture for Challenged
Internets,” in Proceedings of ACM SIGCOMM 2003, Karlsruhe,
Germany, Aug. 2003, pp. 27–34.
[2] L. Pelusi, A. Passarella, and M. Conti, “Opportunistic Networking:
Data Forwarding in Disconnected Mobile Ad Hoc Networks,” IEEE
Communications Magazine, vol. 44, no. 11, pp. 134–141, 2006.
[3] S. Corson, “Mobile Ad hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations,” RFC2501,
Jan. 1999.
[4] C. E. Perkins and E. M. Royer, “Ad-Hoc on-Demand Distance
Vector Routing,” in Proceedings of Workshop on Mobile Computing
Systems and Applications (WMCSA 1999), New Orleans, LA, USA,
Feb. 1999, pp. 90–100.
[5] D. B. Johnson and D. A. Maltz, “Dynamic Source Routing in Ad
Hoc Wireless Networks,” in Mobile Computing, vol. 353, 1996, pp.
153–181.
[6] M.-C. Chuah, P. Yang, B. D. Davison, and L. Cheng, “Store-andForward Performance in a DTN,” in The 63rd IEEE VehicularTechnology Conference (VTC 2006-Spring), Melbourne, Australia,
Mar. 2006, pp. 187–191.
[7] A. Lindgren and P. Hui, “The Quest for a Killer App for
Opportunistic and Delay Tolerant Networks,” the 15th Annual
International Conference on Mobile Computing and Networking(MobiCom 2009) Workshop, pp. 59–66, Sep. 2009.
[8] S. Burleigh, A. Hooke, L. Torgerson, K. Fall, V. Cerf, B. Durst,
K. Scott, and H. Wiss, “Delay-Tolerant Networking: An Approach to Interplanetary Internet,” IEEE Communications Magazine, vol. 41, no. 6, pp. 128–136, Jun. 2003.
[9] S. Saha, Sushovan, A. Sheldekar, R. Joseph C., and S. N. Amartya
Mukherjee, “Post Disaster Management Using Delay Tolerant Network,” Recent Trends in Wireless and Mobile Networks, vol. 162,
pp. 170–184, Jun. 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,” inProceedings of the 5th ACM Conference on Embedded Networked
Sensor Systems (SenSys 2007), Sydney, Australia, Nov. 2007, pp.
103–116.
[11] F. Giudici, E. Pagani, and G. P. Rossi, “Impact of Mobility on
Epidemic Broadcast in DTNs,” Wireless and Mobile Networking,pp. 421–434, 2008.
[12] ——, “Self-Adaptive and Stateless Broadcast in Delay and Disruption Tolerant Networks,” in Proceedings of Italian Networking
Workshop, Cortina d’Ampezzo, Italy, Jan. 2009.
[13] G. Gamberini, F. Giudici, E. Pagani, and G. P. Rossi, “Impact ofHistory on Epidemic Broadcast in DTNs,” in Proceedings of the
1st IFIP Wireless Days Conference (WD 2008), Dubai, United ArabEmirates, Nov. 2008, pp. 1–5.
[14] A. Goundan, E. Coe, and C. Raghavendra, “Efficient Broadcastingin Delay Tolerant Networks,” in 2008 IEEE Global Telecommunications Conference (GLOBECOM 2008), New Orleans, LA, USA,
Nov. 2008, pp. 1–5.
[15] H. Gong and J. W. Kim, “A Prioritization-Based ApplicationOriented Broadcast Protocol for Delay-Tolerant Networks,” in Proceedings of 2009 IEEE Wireless Communications and Networking
Conference (WCNC 2009), Budapest, Hungary, Apr. 2009, pp. 1–6.
[16] T. Camp, J. Boleng, and V. Davies, “A Survey of Mobility Models
for Ad Hoc Network Research,” Wireless Communications andMobile Computing, vol. 2, no. 5, pp. 483–502, Sep. 2002.