Mobility Entropy and Message Routing in
Community-Structured Delay Tolerant Networks
Hideya Ochiai
The University of Tokyo
jo2lxq@hongo.wide.ad.jp

ABSTRACT
Many message routing schemes have been proposed in thecontext of delay tolerant networks (DTN) and intermittently
connected mobile networks (ICMN). Those routing schemes
are tested on speciﬁc environments that involve particularmobility complexity whether they are random-based or sociologically organized. We, in this paper, propose community
structured environment (CSE) and mobility entropy to discuss the effect of node mobility complexity on message routing performance. We also propose potential-based entropy
adaptive routing (PEAR) that adaptively carries messages
over the change of mobility entropy. According to our simulation, PEAR has achieved high delivery rate on wide rangeof mobility entropy, while link-state routing has worked wellonly at small entropy scenarios and controlled replicationbased routing only at large entropy environments.

Categories and Subject Descriptors
C.2.1 [Network Architecture and Design]: Wireless Comunication; C.2.2 [Network Protocols]: Routing Protocols

General Terms
Algorithms, Performance, Theory

Keywords
Delay Tolerant Networks, Mobility Entropy, CommunityStructured Environment, Potential-Based Routing

1. INTRODUCTION
The communication paradigm of delay and disruption
tolerant networks (DTN)[9], such as hop-by-hop appli-

Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are
not made or distributed for proﬁt or commercial advantage and that copies
bear this notice and the full citation on the ﬁrst page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior speciﬁc
permission and/or a fee.
AINTEC’08, November 18–20, 2008, Bangkok, Thailand.
Copyright 2008 ACM 978-1-60558-127-9/08/11 ...$5.00.

Hiroshi Esaki
The University of Tokyo
hiroshi@wide.ad.jp

cation message delivery, is promising in many ﬁelds especially where stable Internet connectivity is not available (e.g., communication in disaster-aﬀected areas, developing regions, wildlife tracking and wireless sensor
networks). It has also been discussed in the context
of intermittently connected mobile networks (ICMN),
where an end-to-end connected path rarely or never exists because of highly dynamic properties of topology
changes and node mobility.
Researchers have proposed several routing schemesfor DTNs often assuming particular mobility environments. DTLSR[8] has adopted link-state routing for thecommunication among villages in developing regions.
MaxProp[4] and RAPID[1] discussed message delivery
among city buses. PROPHET[18] and SOLAR[12] focused on particular sociological mobile scenarios andevaluated their proposed routing schemes on them. Random waypoint mobility(RWP) has been widely used forevaluation of message routing in ICMNs[25, 22, 14, 3].
These works commonly focus on their particular environments with regard to mobility complexity to discuss
their proposed routing schemes.
We propose community-structured environment (CSE)
for evaluating routing schemes over wide range of mobility complexity. In order to parameterize the complexity, we deﬁne mobility entropy in CSE. Mobility entropy
works as an objective criterion of complexity. Small entropy is associated with well-structured mobile environments. A random or chaotic mobility model gives large
entropy.
In this paper, we also propose potential-based entropy adaptive routing (PEAR) that carries out message routing adaptively over the change of mobility entropy. PEAR dynamically changes message replicationlevel depending on mobility entropy to always achieve
high delivery rate. A node basically transfers messages
toward the nodes of higher delivery probability with lessmessage replication at smaller entropy, but it replicatesmore messages at larger entropy to maintain delivery
rate. PEAR is not aware of entropy by itself. Nodemobility initiates replication, and this makes PEAR
entropy-adaptive.

PEAR inherits the concept of potential-based routing (PBR)[2], which is a family of message routing protocols that a node has a scalar value called potential
for each destination and forwards messages toward theneighbor that has the lowest potential. The advantage
of PBR is that a node can make forwarding decisions
without a global knowledge of network topology. PBR
only requires neighbor information for this purpose.
The forwarding decisions in PBR are made by potentials over nodes, which we call potential-ﬁeld. We
deﬁne a recurrence formula for potential-ﬁeld computation in PEAR, which basically works in autonomously
and totally distributed manner. The recurrence formulation enables dynamic computation of potential-ﬁeld
without using a global knowledge of network status. It
only uses neighbor network status, but constructs global
potential-ﬁelds appropriately.
We carry out simulations on various CSEs with changing mobility entropy in order that we investigate theeﬀect of mobility entropy on message routing performance. We recognize that the performance is aﬀectedby many environmental features such as network bandwidth, media-access control (MAC) protocol, message
buﬀer capacity as well as mobility. However, in thiswork, we assume an ideal environment (e.g., inﬁnite
network bandwidth and huge capacity of storage) todemonstrate the relationship between mobility entropy
and routing performance.
This paper is organized as follows. In section 2, we
present related works. In section 3, we propose community structured environment. In section 4, we deﬁnemessage delivery in PEAR. We propose a potential-ﬁeld
construction method in section 5. We describe performance evaluation in section 6. In section 7, we discuss
the evaluation result. In section 8, we give the summaryof this paper.

2. RELATED WORK
Traditionally, in order to evaluate the performance ofrouting in ICMNs, random-based mobility models havebeen adopted. Such mobility models include random
waypoint(RWP), random walk(RW) and random direction(RD)[16]. It has been recently widely acknowledgedthat random-based mobility is unrealistic and that routing schemes are frequently discussed on sociologicallyorganized mobility models, which are studied in thecontext of buses[26], taxi[21], sociological orbit[11, 12]
and pedestrians[5]. Community-based mobility is also
proposed by [23], but it is basically random direction
mobility which hierarchically deﬁned. The problem isthat these mobility models possess a particular environmental feature with regard to mobility entropy; e.g.,
random-based mobility gives extremely large entropy
and sociologically-organized mobility gives smaller entropy. Community-structured environment, we intro-

duced in this paper, enable seamless shifts among several mobility models in terms of entropy.
CSE is motivated by the work of Natasa et. al.[21]and SOLAR[12]. Natasa et. al. have analyzed approximately 800 taxi traces over three months and found stable concentration points(CPs) where nodes encounter.
SOLAR has proposed partially repetitive orbital mobility pattern that a node goes around in a small setof location points, which seems to be better suited topractical scenarios than random-based mobility. A CP
corresponds to a community in CSE and node moves ina small set of communities in CSE. In this paper, we
add the concept of mobility entropy in the context ofCSE.
As for routing in DTNs and ICMNs, several routing
schemes have been proposed. Link-state routing scheme
was adopted to communication between villages in developing regions[15, 8]. Depending on the methods ofcomputing the link cost, maximum delivery probability(MDP), minimum expected delay (MED) and minimum expected dependent delay (MEDD) are proposed[6]. Basically, link-state routing is eﬀective only in thecase of well-structured (i.e., low-entropy) environment.
Message path becomes meaningless at a highly dynamic
mobile networks.
Epidemic routing [25] ensures message delivery evenin partitioned networks of highly dynamic topology. Basically, epidemic routing is ﬂooding-based routing scheme,
which copies message to all the nodes encountered, andthe copy-received nodes start to copy the message inthe same manner. It ideally achieves minimum delivery
latency, but, it is said that epidemic routing consumes
lots of network resources and buﬀer space, which resultsin traﬃc congestion and poor performance in realistic
scenarios.
Compared to epidemic routing, Spray and Wait[22]improves the overhead of message replication by controlling the maximum number of message copy. Message routing in Spray and Wait is composed of twophases. At ﬁrst, in spray phase, the message source
node makes message copies to neighbor nodes encounterd with limitation. Then, it waits until one of thenodes encounters the destination. Controlled replicationbased routing like Spray and Wait is useful only in thecase of randomly contactable scenarios where random
mobility guarantees delivery probability.
Potential-based routing (PBR) was proposed by Basuet. al. [2] in the context of traﬃc engineering in stable networks. In PBR, a node forward messages toward
the neighbor that has the lowest potential. Followedby this work, PWave[19] has applied PBR to wirelesssensor networks for routing of sensor readings to sinknodes. Volcano routing scheme (VRS)[10] is also an extention of PBR that computes potential-ﬁeld to diﬀuse
messages from densely message buﬀered areas.

Figure 1: Communities Organized by Node Traces at Mobility Entropy S = 0, 1, 2, 3

Figure 2: Nodes Organized by Contacts at Mobility Entropy S = 0, 1, 2, 3

Utility-based routing was proposed by [7] in mobile ad
hoc networks (MANET) to support disconnected transitive communication. Utility is a scalar value that shows
logical proximity to the destination. In that, utilitybased routing is the same as potential-based routing in
nature. The node of the highest utility will relay message to its destination with higher probability than any
other nodes. There are a number of utility computation methods in literature. History-based protocol was
proposed by ZebraNet [17]. Chen et. al. [7] proposed
Most-recently-noticed (MRN), Most-frequently-noticed(MFC). Spyropoulos et. al. proposed last-seen-ﬁrst(LSF), most-mobile-ﬁrst (MMF) and most-social-ﬁrst(MSF) [24]. CAR[20] provides attribute-based generalframework for computing utility that can be aware of
remaining battery and other properties as well as contact statistics.
In this paper, we discuss entropy-adaptability in thecontext of potential-based routing. To our knowledge,
entropy-adaptability has not been discussed in the previous works.

environment(CSE).
Let N be a set of nodes in the network, and C a setof communities. A node n ∈ N belongs to a sub set ofC, which we denote by Cn . In community-structured
environment, we deﬁne two mobility status: stay andtransition. In the stay mode, a node n stays at oneof Cn , which is given by location(n). In the transitionmode, n moves from community ci to community cj
where ci , cj ∈ Cn and i 6= j. A node is in contact with
the nodes that stay in the same community. That is,”Node n and k are within direct transmission range”⇔”Node n and k are in contact with each other”⇔

3. COMMUNITY-STRUCTURED ENVIRONMENT

2. Choose a random value r uniformly in [0, 1).

In order to describe mobile environments in termsof mobility entropy, we propose community-structured∃c ∈ C, location(n) = c ∧ location(k) = c(1)

location(n) gives undef ined when node n is in transition state.
We deﬁne CSE node mobility as follows (||Cn || gives
the number of elements in Set Cn ),1. Node n stays at community ci ∈ Cn .

3. If p < r or ||Cn || = 1, goto 1. Parameter p isprobability of transition from stay mode to transitmode.

4. Choose a destination community cd from Cn −{ci }at random.
5. Let n move to cd with transitive time T (ci , cd ).
6. After n reached the destination, ci := cd and goto
1.
We formally deﬁne mobility entropy S of CSE as,
1 ∑S=
log2 ||Cn ||(2)||N ||
n∈N

Here, if every node belongs to the same number ofcommunities(i.e., ||Ci || = ||Cj ||), S can be described as,
S = log2 Ω(3)Ω is the number of communities that every node belongs to.
We use the above S and Ω as a feature of CSE in thefollowing discussion.
We show CSE instances in the case of S = 0, 1, 2, 3
in ﬁgure 1 and 2. In ﬁgure 1, a community is denotedby a vertex of the graph, and node traces are denotedby the edges. In ﬁgure 2, a node is denote by a vertex of the graph, and a node-to-node contactability isdenoted by an edge. A pair of vertexes that connectedby an edge indicates that those nodes are possible toencounter with each other.
As these ﬁgures indicate, randomly contactable environment is characterized by larger entropy (e.g., S = 3).
Stable or well-structured mobile environments provide
small entropy (e.g., S = 0, 1). In fact, random waypoint mobility[16] is given by setting Ω = ||C||, whichis the case at the largest S. Village-to-village scenarios[8] could be categorized by small entropy.

4. MESSAGE DELIVERY IN PEAR
In this paper, we propose potential-based entropy
adaptive routing (PEAR). Here, we focus on message
delivery method under the assumption that potentialﬁelds are already given. We discuss autonomous constrution of potential-ﬁelds in PEAR in the next section.
In the following discussion, we denote the neighbornodes (including itself) of node n by nbr(n). nbr(n) is
a set of nodes within the same community of location(n)if it is deﬁned(i.e., in stay mode). Otherwise, nbr(n) ={n}.
In potential-based routing(PBR)[2], a node has a scalarvalue that shows a kind of distance to its destination.
We call the value potential and describe it as V d (n).
When we consider the change of potential over time,
we describe it as V d (n, t), which means the potential
for destination d at node n at time t. In this section,
we assume that V d (n) is given and we focus on message delivery on it. Computation of V d (n) is discussed
in section 5.

Basically, message delivery in PBR is carried out by
forwarding messages toward the node of the lowest potential among its neighbors. After a node forwarded amessage to the next node, it usually removes the message from the local buﬀer. In stable networks (i.e., wired
and connected networks), this message delivery scheme
is appropriate. However, in DTN scenarios, message
delivery should be carried out more redundantly to improve delivery probability and latency.
In DTN environment, we consider that messages should
not be just forwarded to the next node; it should becopied but should not be deleted from the local buﬀer.
The copy-source node tries to make another copy ofmessages again when it encounters to another node.
Message replication in this way will improve the delivery probability and latency. When we introduce replication, the network must deal with replica managementthat involves message deletion after it has reached thedestination.
In this context, we distinguish the terms of copy, forward, replicated messages and delete as,
Copy: the process of making a clone of a message fromthis node into the other node.
Forward: the process of making a clone of a message
from this node into the other node and deletingthe original message.
Replicated messages: messages left in the networkby the process of copy.
Delete: the process of eliminating replicated messages
from the network.

4.1

Selection of Next Hop Nodes

Let M be a set of messages in the network, and M d (⊂M ) be the messages which destination is d. To deliver amessage m ∈ M d , node n must determine the next hop
nodes of m, at ﬁrst. We deﬁne two next hop selection
schemes: i.e., best or single candidate selection(BCS)
and multiple candidate selection(MCS).
Best (or Single) Candidate Selection (BCS):
nexthopdBCS (n) ={k|k ∈ nbr(n) ∧ Fkd (n) = max {Fjd (n)} > α}(4)j∈nbr(n)Here, Fkd (n) is the force that aﬀects on the message
m from node n toward neighbor k, which we deﬁne asd

Fkd (n) = V d (n) − V d (k)(5)

Lower potential of neighbor k enlarge the force fromnode n to k.
In BCS, node n chooses the neighbor k that gives the
maximum Fkd (n) as the next hop of M d at every timeunit. Here, the force must be more than a constantAfter nexthopd (n) is determined by BCS or MCS atnode n. n tries to copy message m ∈ M d to them. Here,some of them may already have a replica of the message or others may know that the message has alreadyreached the destination. Replica management should be
carried out in PEAR in order to reduce the overhead of
message duplication and to eﬃciently use buﬀer spaceby removing replicas of delivered message from the network.
In PEAR, message m must contain the following information as well as the message body in its header at
least.
• MessageID
Figure 3: Message Delivery in PEAR

• Destination• Time to Live (TTL)

value α, the threshold of the least force level. Otherwise, no selection are made for destination d. Nodes
encounter and leave as time elapses, and the best candidate changes according to nbr(n).
Multiple Candidate Selection (MCS):
nexthopdM CS (n) = {k|k ∈ nbr(n) ∧ Fkd (n) > β}(6)In MCS, next hop nodes are such neighbors that theforce is more than β(> 0). MCS chooses multiple next
hop nodes at the same time.
Figure 3 demonstrates how PEAR delivers a messagem(∈ M d ) to destination d. In this ﬁgure, nodes are
mapped according to their potential V d (n) in the vertical axis, and the edges show node-to-node contactability(i.e., intermittent connectivity) between nodes. At ﬁrst,
m is possessed by n7 , which has the highest potential
in the ﬁgure. During n7 is not connected to neither ofn5 or n8 , it does nothing. When it encounters both ofn5 and n8 at the same time, it copies the message ton5 since Fnd5 (n7 ) > Fnd8 (n7 ) in BCS, whereas in MCS it
copies them to both of n5 and n8 . In BCS (n8 does notpossess m), after n5 has left from n7 , n7 copies m to n8
since Fnd8 (n7 ) now provides the strongest force amongits neighbors. n5 , n8 and any other nodes behave inthe same way and the message m will be copied to thelower potential nodes until they reach the destination.
At small entropy (e.g., S = 1), PEAR only uses asmall set of nodes for message delivery, saving resources
as much as possible. As entropy S becomes larger, probability of meeting of nodes (e.g., between n5 and n7 )decreases and message delivery on that paths may fail.
However, PEAR maintains delivery probability even inlarger S by replicating more messages in the network.
At large entropy, n7 also has links with n1 , n4 and n9 .
Thus, m will be copied to those nodes, which increases
the replication level, and achieves high delivery rate.

4.2 Replica Management

The following information should be managed at every node locally for each m.
• DisseminationTTL• IsDelivered
MessageID must be uniquely deﬁned in the network.
TTL is a message life time which decreases, for example,
every second. When TTL reaches zero, the message
expires (with freeing memory allocated for m including
headers). TTL corresponds to the left time for delivery
deadline.
DisseminationTTL describes whether node n can send
the message to other nodes or not. Initially, node n sets
it to TTL of the message when received the message. It
decreases in the same manner as TTL does. As we describe later, DisseminationTTL changes depending on
the process of message replication. If it has expired,
node n does not transfer the message to its next hop
nodes any longer and deletes the body of it (with freeing allocated memory space for message body), but continues to check the existence of a delivery certiﬁcation
at the next hop nodes. IsDelivered shows whether delivery has been certiﬁed or not. Originally, when thisnode receives a message, IsDelivered is set to f alse.
After ﬁnding the delivery certiﬁcation, it is set to true.
The ﬁrst certiﬁcate will be published by the destination
node after it has received the message.
Of course, in practice, the message source identiﬁershould also be included in the message header alongwith the destination. However, PEAR does not careabout the source of the message, so we consider it as
optional.
We deﬁne message delivery and replica management
algorithm on given nexthopd and m ∈ M d in ﬁgure 4.
In the algorithm, check message status(k, m) tries
to ﬁnd node k and asks about the status of message m
and replies one ofV d (n, t + 1) = V d (n, t)+ D min {V d (k, t) − V d (n, t)}k∈nbr(n)+ ρ
V d (n, 0) = 0
V n (n, t) = 0
0<ρ<D , 0<D<1

Figure 4: Algorithm of Message Delivery andReplica Management• NEIGHBOR NOT FOUND• MESSAGE NOT HAVE• MESSAGE ALREADY HAVE• MESSAGE DELIVEREDtransf er(k, m) makes a copy of message m into k.
delete content(m) removes the body of m and frees the
allocated memory.

4.3 Loop-Freeness
Loop-freeness in potential-based routing is proved by[2] in the case of static potential-ﬁeld. Basically, a message which has been forwarded to the lower potential
node cannot come again from the upper potential node.
In our modiﬁed version of PBR, message delivery is
carried out by copying, not by forwarding. Message remains at the nodes where it has infected. Therefore,
even in dynamically potential-changing scenarios, messages never loop in PEAR.

5. POTENTIAL-FIELD CONSTRUCTION
In the previous section, we described a message delivery scheme in PEAR on a given potential-ﬁeld. In thissection, we describe potential-ﬁeld construction method
in PEAR, which autonomously and dynamically computes the ﬁeld. Potential computation in PEAR does
not require global topology information. It only uses
neighbor information but makes an appropriate potential ﬁeld globally. This is the same property that next
hop decision schemes possess.
We propose a recurrence formula that computes theﬁeld which has the above feature in this section.

(7)
(8)
(9)
(10)

The potential of node n at the next time step (t + 1)
is calculated on the potential of neighbors at current
time t. Basically, it inﬂates by ρ, but the inﬂation
is depressed by the smallest potential among neighbors. This depression is weighted by D, which we callminimum-potential diﬀusion constant.
Eqn. 8 gives the initial condition; i.e., all the potential value starts at zero. Eqn. 9 gives a boundary
condition that a node must always have zero potential
for itself, which means that the potential at the destination must be always set to zero.
The potential at the destination node V d (d) = 0 diffuses from the message destination around the networkwith some increase. In this way, nodes farther fromthe destination gets higher potential, and nodes closer
to the destination gets lower potential. Message delivery is carried out from the higher potential node to thelower potential node.

5.2

Dynamics

In ﬁgure 5, we illustrate how PEAR autonomously
constructs a potential-ﬁeld by Eqn. 7 and achieves message delivery. We assume a quite simple case to makethe discussion easy: i.e., four nodes and three communities. Here, n1 belongs to a community c1 . n2 belongs to
c1 and c2 . n3 belongs to c2 and c3 , and n4 to c3 . Nodes
are in contact with each other only when they are located at the same community; i.e., n1 and n2 are incontact when n2 locates at c1 , n2 and n3 are in contact
when they stay at c2 , and so on. A contact is denotedby a line, and disconnection is denoted by dashed lines.
The vertical axis shows potential for destination n1 .
(a) Initially, nodes have the same potential value atzero. They except V n1 (n1 ) start to increase by ρ.
ρ, while V n1 (n3 )(b) As time elapses, V n1 (n2 ) stays at Dn1
and V (n4 ) continues to increase at speed ρ. At
this time, n2 can send its M n1 to n1 , while n3 andn4 store them in the local memory.

5.1 Recurrence Formulation(c) The physical topology has changed, and only n2
and n3 are in contact. V n1 (n2 ) starts to increase at
speed ρ, while V n1 (n3 ) decreases toward V n1 (n2 ).
Here, n3 copies its M n1 to n2 .

The recurrence formula we propose for potential-ﬁeld
construction is,(d) When the link between n2 and n3 is disrupted andinstead the link between n3 and n4 has set up,

Figure 5: Dynamics of Potential-Field Construction over the Change of Node-to-Node Connectivity

V n1 (n2 ) and V n1 (n3 ) increases at speed ρ, while
V n1 (n4 ) decreases toward V n1 (n3 ). In this situation, n4 copies its M n1 to n3 .
(e) n2 is now in contact with n1 . V n1 (n2 ) decreases toρn1
to n1 .
D , and n2 transfer its M
If the network topology do not change, (e) goes to (b).
In this way, potential-ﬁeld is autonomously constructed
and maintained so that messages could be delivered tothe destination.

5.3 Performance Study
We discuss the performance of potential-ﬁeld construction in PEAR with regard to computation andtransmission cost.
In order to inform potentials to neighbors, we assume
that a node periodically advertises potentials that ithas (e.g., every ten second). This advertisement from ncontains potentials bound for all the destinations (i.e.,{V d (n)|∀d ∈ N }). Thus, the size of advertisement isgiven by O(m) where m is the number of elements in
N (i.e., m = ||N ||).
The computation of the next potential value (Eqn. 7)
can be also performed at O(m) by using sorted array.
Suppose that A is a sorted array which members aredenoted by {a1 , a2 , ...aj }. Here a1 , ..., aj is sorted into
increasing order. For each destination, by maintaining
potentials of neighbors by A, a1 always gives the minimum potential value among its neighbors. Therefore,
Eqn. 7 can be calculated at O(1). Since the potential must be calculated in parallel for each destination,
the total computation cost is O(m). As for the total
maintenance cost of A (i.e., the cost of inserting, updating, and deleting potential values), it carries outat O(hm), where h denote the number of the neighbors(i.e., h = ||nbr(n)||).

6. SIMULATION

Figure 6: Message Delivery Rate

We evaluated PEAR, regarding to delivery rate andtotal message transmissions, on various CSEs by simulation. The purpose of this experiment is to analyze
the features of routing schemes in terms of mobility entropy. Thus, we carried out the simulation without being aware of transmission properties (e.g., node-to-nodelink bandwidth and average message size). In this way,
we focused on an ideal case where the eﬀect of them canbe ignored.
We set 100 nodes over 50 communities throughout thesimulation with changing Ω from 2 to 48: i.e., entropy
S from 1 to 5.6. We assumed the case that every node
belongs to the same number (= Ω) of communities ineach CSE.
Throughout the experiment, we set D = 0.001 andρ = 0.00001 for potential-ﬁeld construction (Eqn. 10),and α = 0.8 and β = 0.8 for next hop selection (Eqn. 4
and Eqn. 6). The message lifetime was set to 20000.
We carried out the simulation of node mobility, potential ﬁeld construction and message delivery during
the time interval [−50000, 20000]. While t ∈ [−50000, 0),
no messages were submitted into the network; only the
movement of nodes and potential-ﬁeld construction were
simulated. At t = 0, every node sent messages to all thenodes in the network. While t ∈ (0, 20000], message delivery was also simulated as well as the node movement
and potential-ﬁeld construction.
We evaluated PEAR with other routing schemes suchas epidemic routing[25], Spray and Wait (2-hop scheme)[22], Minimum Expected Delay(MED) and Maximum
Delivery Probability(MDP)[6]. In the comparison withthese schemes we have prepared completely the same
set of CSEs.

6.1

Delivery Rate

Figure 6 shows the relationship between message delivery rate and mobility entropy.
Link-state routing (i.e., MED and MDP) achieved

about 95% message delivery at S = 1, but it failed 50%
at larger entropy. Spray and Wait delivered only 28%
of messages at S = 1, whereas it delivered about 95% atlarger entropy. PEAR achieved more than 95% delivery
rate over any entropy environments, which is almost thesame level that Epidemic routing did. These results
indicate that PEAR has dynamically adapted to any
given environments whether they are highly-dynamicor relatively well-organized. However, link-state routing
and Spray and Wait has achieved good performance atthe speciﬁc situations.
Figure 7 shows the change of delivery rate during time
[0, 20000] at mobility entropy S = 1, 3, 5. S = 1, 3, 5
corresponds to Ω = 2, 8 and 32 (Eqn. 3). From thesegraphs we could read that PEAR, MED and MDP atlarger entropy delivered messages slower than those at
smaller entropy. However, PEAR showed good tolerance of delivery latency against the increase of mobility
entropy compared to MED and MDP.
The latency of message delivery in MED and MDP
gets large sharply as S increases, resulting in unsuccessful message delivery at time 20000. As for otherrouting schemes, Epidemic routing totally performed
a good performance with regard to delivery rate, andSpray and Wait stopped the increase of message delivery rate at 28% around time 5000 at S = 1, but therate sharply increased at S = 3, 5.
From these results, we summarize that PEAR is useful for wider mobility entropy scenarios than the otherrouting schemes except Epidemic routing. Link-staterouting (i.e., MED and MDP) is just useful at quite
small entropy. Spray and Wait routing is useful forlarger entropy scenarios, where nodes are possible todirectly contact with most of the nodes in the network.

6.2 Total Message Transmissions
Total message transmissions is the total count of application message exchange among nodes. Figure 8 shows
the relationship between total message transmissions
and entropy. PEAR(BCS) reduced the transmissions
to about 11% (at S = 1) and 23% (at S = 5) of
Epidemic routing. Link-state routing (i.e., MED and
MDP) transmitted about 3.5% of Epidemic routing at
S = 1, where they achieved high delivery rate. Sprayand Wait transmitted about 12% at S = 5. PEAR
generated two or three times more transmissions thanlink-state routing and Spray and Wait.
Figure 9 shows total message transmissions over thetime interval from t = 0 to t = 20000. These graphs
show the summary of transmission: e.g., 1000 transmissions at time 3000 means that 1000 messages have been
exchanged in the network during [0, 3000]. From the results we read that message delivery in Spray and Wait
was carried out mostly during [0, 5000] at any CSEs.
This is the same feature of Epidemic routing. AnotherFigure 8: Total Message Transmissions

thing we read from the results is that link-state routing
and PEAR carried out the delivery process graduallyat S = 3, 5 though it has ﬁnished around t = 5000 at
S = 1.

7.

DISCUSSION

Introduction of community-structured environment(CSE) has been successful in that we could seamlesslyclassify mobile environments and analyze routing performance on the environments. By changing the entropy of CSEs, we could clearly read the features ofrouting schemes. Link-state routing (i.e., MDP and
MED) has performed well only at smaller entropy casessuch as village-to-village communications. Spray and
Wait has worked well at larger entropy, where nodes
can randomly contact with each other. PEAR, which
we have proposed in this paper, has achieved high delivery rate over any entropy scenarios with transmission
reduction to approximately 10% to 20% compared to
Epidemic routing.
At smaller entropy, PEAR has achieved high delivery
rate by aggressively transferring a message using thepotential-ﬁeld developed from the relatively stable mobile environment. In this case, the selected next hop
nodes are most capable of carrying messages to thecloser nodes to the destination. However, Spray and
Wait just makes a copy to the nodes around, thus it
failed to deliver most of the messages in our experiment.
At larger entropy, PEAR has also achieved high delivery rate by making a lot of message replicas in the
network. In such environments, we consider that routing scheme must shift from message transfer scheme tomobility-based scheme: i.e., utilization of mobility is
the primary factor of successful message delivery. In
that Spray and Wait was eﬀective. PEAR is also effective because a node becomes to replicate messages
as entropy becomes larger. However, link-state routing
could not adapt to the large entropy environments because it sticks to transfer a message to the given next

Figure 7: Delivery Rate at Entropy S = 1, 3, 5

Figure 9: Total Message Transmissions at Entropy S = 1, 3, 5

hop node.
According to our experiment, BCS and MCS showedalmost the same feature with regard to delivery rate
and total transmissions. MCS achieved almost the samedelivery rate with about 1.4 times of transmissions inmost cases. This result indicates that BCS scheme will
be enough in practice.
The role of this paper was to analyze the properties ofPEAR with regard to mobility entropy with comparisonof other proposed routing schemes. For the next steps,
we are considering about deployment into realistic scenarios. The actual performance will be also determinedby other aspects of the environment besides mobility
entropy such as radio bandwidth, media-access control(MAC) protocol, source-to-destination message traﬃc,
buﬀer capacity and rate of failure. Epidemic routing
could be suﬀered from congestion under limited bandwidth. According to [13], 10% transmission reduction
will improve the performance signiﬁcantly in terms ofcongestion. Deployment of PEAR on various testbeds
are required for further analysis and improvement in
the near future.

8. CONCLUSION
We proposed community-structured environment(CSE)and potential-based entropy adaptive routing(PEAR)
in this paper. CSE has enabled the classiﬁcation ofmobile environments in terms of mobility entropy. In
CSE, stable or well-structured mobile environments arecharacterized by small entropy. Randomly contactableenvironments are characterized by large entropy.
Using CSE, we have analyzed the features of routing
schemes by simulation. In our experiment, link-staterouting (e.g., MED and MDP) has worked well at small
entropy environments such as S = 1 but failed to 50%
delivery at larger entropy. Spray and Wait has achieved
good performance at larger entropy, but only 28% messages have been delivered at S = 1.
PEAR has achieved more than 95% message delivery over any mobility entropy environments by adaptively changing the message delivery form. At small
entropy, PEAR has aggressively transferred a message
in hop-by-hop manner using the appropriately developed potential-ﬁelds. At large entropy, PEAR has automatically shifted to let mobility deliver the message
with making more replicas in the network. In this way,
PEAR has maintained the delivery rate.

Acknowledgement
This research was supported in part by national institute of information and communications technology(NICT), Japan.

9.

REFERENCES

[1] A. Balasubramanian, B. N. Levine, and
A. Venkataramani. DTN routing as a resource
allocation problem. In ACM SIGCOMM, 2007.
[2] A. Basu, A. Lin, and S. Ramanathan. Routing
using potentials: A dynamic traﬃc-aware routing
algorithm. In ACM SIGCOMM 2003, 2003.
[3] J. Boice, J. J. Garcia-Luna-Aceves, and
K. Obraczka. On-demand routing in disrupted
environments. LNCS Networking, 4479:155–166,
nov 2007.
[4] J. Burgess, B. Gallagher, D. Jensen, and B. N.
Levine. MaxProp: Routing for vehicle-based
disruption-tolerant networks. In IEEE
INFOCOM, 2006.
[5] A. Chaintreau, P. Hui, J. Crowcroft, C. Diot,
R. Gass, and J. Scott. Impact of human mobilityon the design of opportunistic forwarding
algorithms. In IEEE INFOCOM, 2006.
[6] C. Chen and Z. Chen. Evaluating contacts forrouting in highly partitioned mobile networks. In
ACM MobiOpp, 2007.
[7] X. Chen and A. L. Murphy. Enabling
disconnected transitive communication in mobile
ad hoc networks. In ACM POMC, 2001.
[8] D. Demmer and K. Fall. DTLSR: Delay tolerantrouting for developing regions. In ACM NSDR,
2007.
[9] K. Fall. A delay-tolerant network architecture forchallenged internets. In ACM SIGCOMM, 2003.
[10] Y. Ganjali and N. McKeown. Routing in a highly
dynamic topology. In IEEE SECON, 2005.
[11] J. Ghosh, H. Q. Ngo, and C. Qiao. Mobility
proﬁle based routing within intermittently
connected mobile ad hoc networks (ICMAN). In
ACM IWCMC, 2006.
[12] J. Ghosh, S. J. Philip, and C. Qiao. Sociologicalorbit aware location approximation and routing(SOLAR) in MANET. ACM Ad Hoc Networks,
5(2):189–209, mar 2007.
[13] Z. Haas, J. Y. Halpern, and L. Li. Gossip-based
ad hoc routing. In IEEE INFOCOM, 2002.
[14] J. Hahner, C. Becker, and K. Rothermel. A
protocol for data dissemination in frequently
partitioned mobile ad hoc networks. In IEEE
ISCC, 2003.
[15] S. Jain, K. Fall, and R. Patra. Routing in a delay
tolerant network. In ACM SIGCOMM, 2004.
[16] A. Jindai and K. Psounis. Fundamental mobility
properties for realistic performance analysis ofintermittently connected mobile networks. In
IEEE Percom, 2007.
[17] P. Juang, H. Oki, Y. Wang, M. Martonosi, L.-S.
Peh, and D. Rubenstein. Energy-eﬃcientcomputing for wildlife tracking: Design tradeoﬀs

and early experiences with ZebraNet. In ACM
SIGOPS, pages 96–107, 2002.
[18] A. Lindgren, A. Doria, and O. Schelen.
Probabilistic routing in intermittently connected
networks. LNCS, 3126:239–254, sep 2004.
[19] H. Liu, Z.-L. Zhang, J. Srivastava, and V. Firoiu.
PWave: A multi-source multi-sink anycast routing
framework for wireless sensor networks. LNCS
Networking, 4479:179–190, nov 2007.
[20] M. Musolesi, S. Hailes, and C. Mascolo. Adaptive
routing for intermittently connected mobile ad
hoc networks. In IEEE WoWMoM, 2005.
[21] N. Saraﬁjanovic-Djukic, M. Piorkowski, and
M. Grossglauser. Island Hopping: Eﬃcientmobility-assised forwarding in partitioned
networks. In IEEE SECON, 2006.
[22] T. Spyropoulos, K. Psounis, and C. S.
Raghavendra. Spray and Wait: An eﬃcientrouting scheme for intermittently connectedmobile networks. In ACM SIGCOMM, 2005.
[23] T. Spyropoulos, K. Psounis, and C. S.
Raghavendra. Performance analysis ofmobility-assised routing. In ACM MobiHoc, 2006.
[24] T. Spyropoulos, T. Turletti, and K. Obraczka.
Utility-based message replication forintermittently connected heterogeneous networks.
In IEEE WoWMoM, 2007.
[25] A. Vahdat and D. Becker. Epidemic routing forpartially-connected ad hoc networks. Technicalreport, Duke University, 2000.
[26] X. Zhang, J. Kurose, B. N. Levine, D. Towsley,and H. Zhang. Study of a bus-based
disruption-tolerant network: Mobility modelingand impact on routing. In ACM MobiCom, 2007.