IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS/SUPPLEMENT, VOL. 31, NO. 9, SEPTEMBER 2013 369
Opportunistic Routing in
Intermittently Connected Mobile P2P Networks
Shengling Wang, Min Liu, Member, IEEE, Xiuzhen Cheng, Senior Member, IEEE,
Zhongcheng Li, Member, IEEE, J ianhui Huang, and Biao Chen, Member, IEEE
Abstract—Mobile P2P networking is an enabling technology
for mobile devices to self-organize in an unstructured style and
communicate in a peer-to-peer fashion. Due to user mobility
and/or the unrestricted switching on/off of the mobile devices,
links are intermittently connected and end-to-end paths may not
exist, causing routing a very challenging problem. Moreover, the
limited wireless spectrum and device resources together with
the rapidly growing number of portable devices and amount
of transmitted data make routing even harder. To tackle these
challenges, the routing algorithms must be scalable, distributed,
and light-weighted. Nevertheless, existing approaches usually
cannot simultaneously satisfy all these three requirements. In
this paper, we propose two opportunistic routing algorithms for
intermittently connected mobile P2P networks, which exploit the
spatial locality, spatial regularity, and activity heterogeneity of
human mobility to select relays. The first algorithm employs a
depth-search approach to diffuse the data towards the destina-
tion. The second one adopts a depth-width-search approach in a
sense that it diffuses the data not only towards the destination
but also to other directions determined by the actively moving
nodes (activists) to find better relays. We perform both theoretical
analysis as well as a comparison based simulation study. Our
results obtained from both the synthetic data and the real world
traces reveal that the proposed algorithms outperform the state-
of-the-art in terms of delivery latency and delivery ratio.
Index Terms—Intermittently connected mobile P2P networks,
opportunistic routing, human mobility.
I. INTRODUCTION
N
OWADAYS, billions of mobile devices are connected
mainly through the assistance of infrastructures, which
may often be undesirable due to high cost, lack of flexibility,
and low utilization of the local wir eless resources. Moreover,
because infrastructures usually have limited wireless coverage
and are vulnerable to nature disaster or other failures, only
Manuscript received February 26, 2012; revised July 14, 2012.
S. Wang, M. Liu, and Z. Liu are with the Institute of Computing Technol-
ogy, Chinese Academy of Sciences, Beijing, China (e-mail: {wangshengling,
liumin, zcli}@ict.ac.cn).
X. Cheng is with the Department of Computer Science, The George Wash-
ington University, Washington, DC, 20052, USA (e-mail: cheng@gwu.edu).
J. Huang is with IBM China, Beijing, China (e-mail:
jianhuih@cn.ibm.com).
B. Chen is with the Department of Computer Information Science, Uni ver-
sity of Macau, Macau, China (e-mail: bchen@umac.mo).
This work was supported by the National Basic Research Program of
China (No. 2011CB302702 and No. 2012CB315802), the National Natural
Science Foundation of China (No. 61132001, No.61272475, No.61003225,
No. 61070187, No.61003266, No. 61070188, and No. 61120106008), the
US National Science Foundation (CNS-0831852), and the Macau FDCT
(009/2010/A1 and 061/2011/A3).
This work was completed when Xiuzhen Cheng visited the University of
Macau on her sabbatical leave.
Digital Object Identifier 10.1109/JSAC.2013.SUP.0513033
using this way may lead to network islands. As a result, a
new networking paradigm named mobile peer-to-peer (P2P)
networking has drawn enormous attention in recent years.
In a mobile P2P network, m obile devices can communicate
in a peer-to-peer fashion a nd self-organize in an unstructured
style without the n eed of any infrastructure, making the
local wireless connectivity better exploited. But under such
a networking paradigm, data delivery is nontrivial [1]–[4] as
end-to-end paths may not exist due to user mobility and/or the
unrestricted switching on/off of the mobile devices. Moreover,
the limited wireless spectrum and device resources (storage,
computatio n capability, batter y power, etc.), together with the
rapidly growing number of portable devices and amount of
transmitted data, make routing even har der. Thus an effective
and efficient routing algorithm in intermittently connected
mobile P2P networks should satisfy the following three design
requirements:
1) Scalable. With the number of nodes in the network
increases, the complexity of the algorithm as well as the
information each node carries, maintains, and exchanges
with others should not rapidly increase.
2) Distributed. Each node should determine its next hop
independently, which means that n o centralized routing
decision/computation should g et involved.
3) Light-weighted. Each node should incur low computa-
tion and storage overheads, which implies the simplicity
of the routing algorithm.
As indicated in Section II, none of the existing routing
algorithms could simultaneously satisfy all these three require-
ments. In this paper, we propose two opportunistic routing
algorithms for intermittently connected mobile P2P n etworks.
The first one takes a depth-search approach to diffuse the data
towards its destination direction. This algorithm exploits the
spatial regularity and spatial locality of the mobility of the
device carriers, i.e. human beings
1
, to find relays. Because
depth-search delivers the data towards a single direction,
adopting this strategy m ay miss better relays from other
directions.
To make up this deficiency, a depth-width-search approach
is proposed, which exploits not only the spatial regularity
and spatial locality of human mo bility, but also its activity
heterogeneity. Thus, the data can be diffused towards not only
the destination d irection but also other directions determined
by the actively moving nodes (activists) in order to find better
1
In this paper, we focus on the mobile devices carried by human beings
because the number of such devices is prominent in the market.
0733-8716/13/$31.00
c
2013 IEEE