IEEE Wireless Communications • February 2012
67
1536-1284/12/$25.00 © 2012 IEEE
ACCEPTED FROM OPEN CALL
INTRODUCTION
Opportunistic networking via pocket switched
networks (PSNs) is a new mobile computing
paradigm that takes advantage of human mobili-
ty to provide occasional communication oppor-
tunities among mobile devices for disseminating
data. As PSNs do not require the assistance of
infrastructures, they are applicable in rural and
developing regions to realize low cost communi-
cations or to connect the islands of various IP-
centric networks when infrastructures fail due to
nature disasters or other failures. In addition,
PSNs can be exploited as an efficient communi-
cation mechanism to complement infrastructure-
based wireless networks because they usually
have limited coverage.
PSN falls into the category of delay-/disrup-
tion-tolerant networks (DTNs). These two types
of networks mainly differ in their information
carriers as the former employs human beings for
data forwarding, while the latter can utilize any
possible carrier, including human beings, to dis-
seminate data. Although human mobility brings
occasional communication opportunities, it also
brings frequent long-duration disruptions for
network links, which makes routing a challenge
in PSNs. Accordingly, the routing objective of
PSNs is quite different from that of wired net-
works or mobile ad hoc networks (MANETs).
In wired networks, end-to-end paths always
exist, and the objective of routing is to find the
shortest path or path(s) satisfying some quality
of service (QoS) constraints. On theother hand,
while links in a MANET may be broken from
time to time, the disruption duration is usually
short. Hence, end-to end paths may exist with a
probability near one in MANETs. Thus, the
routing objective for a MANET is to find the
best available path. In PSNs, network links may
be disrupted for a long time; therefore, end-to-
end paths are assumed not to exist. In such a
network, store-carry-forward is the main mecha-
nism for data delivery, and the routing objective
is to maximize the delivery ratio.
Routing is a key issue in a PSN. In this article,
we summarize the state-of-the-art research and
discuss several related issues on PSN routing.
The rest of the article is organized as follows.
The next section identifies the challenges of PSN
routing, followed by a summary of the character-
istics of human behaviors exploited by current
PSN routing schemes to enhance the routing effi-
ciency. After that, the state-of-theart PSN rout-
ing techniques are overviewed and their cons and
pros are analyzed based on three categories:
encounterbased, social-based, and location-based.
At last, we present the open research issues that
might foster future research on PSN routing.
CHALLENGES OF PSN ROUTING
PSNs are formed by human beings. The human
behaviors, including their mobility and sociality,
bring challenges to PSN routing. Generally
speaking, there mainly exist five major chal-
lenges:
CHALLENGE 1: SCALABILITY
A PSN is featured by the very limited wireless
spectrum and onboard resources (storage, com-
putation capability, battery power, etc.), as well
as the rapidly growing number of portable
devices and amount of transmitted data. There-
fore, PSN routing must be scalable in a sense
SHENGLING WANG AND MIN LIU, CHINESE ACADEMY OF SCIENCES
XIUZHEN CHENG, THE GEORGE WASHINGTON UNIVERSITY
MIN SONG, OLD DOMINION UNIVERSITY
ABSTRACT
Pocket switched networks (PSNs) provide a
new networking paradigm that takes advantage of
human mobility to distribute data. Due to the fre-
quent and long-duration disruptions of network
links, routing in PSNs is nontrivial. In this article,
we first outline the challenges of PSN routing.
After that, we summarize the behavioral traits of
human beings employed by existing PSN routing
schemes and give a brief survey on the state-of-
the-art PSN routing techniques. Finally, we ana-
lyze the characteristics of existing PSN routing
protocols and present some open problems that
may foster future research on PSN routing.
ROUTING IN POCKET SWITCHED NETWORKS
This work has been supported by the National Basic
Research Program of China (no. 2011CB302702,
no.2011CB302800), the Beijing Nova Program, the
National Natural Science Foundation of China (no.
61120106008, no. 61132001, no. 61133015, no.
60803140, no. 60970133, no. 61070187, and no.
61003225), the National Science Foundation of the US
(CNS-0831852), and the NPST program by King Saud
University Project no. 10-INF1184-02.
Pocket switched
networks provide a
new networking
paradigm that takes
advantage of human
mobility to distribute
data. Due to the
frequent and long-
duration disruptions
of network links,
routing in PSNs is
nontrivial.
WANG LAYOUT 2/10/12 3:09 PM Page 67