›› 2013, Vol. 28 ›› Issue (3): 574-582.doi: 10.1007/s11390-013-1357-x

• Computer Network • Previous Articles    

Impact of Strangers on Opportunistic Routing Performance

Pei-Yan Yuan (袁培燕), Member, ACM, Hua-Dong Ma* (马华东), Member, CCF, ACM, IEEE, and Peng-Rui Duan (段鹏瑞)   

  1. Beijing Key Laboratory of Intelligent Telecommunications Software and Multimedia, Beijing University of Posts and Telecommunications, Beijing 100876, China
  • Received:2012-05-03 Revised:2013-01-18 Online:2013-05-05 Published:2013-05-05
  • Contact: 10.1007/s11390-013-1357-x
  • Supported by:

    This work is supported by the National Basic Research 973 Program of China under Grant No. 2011CB302701, the National Science Fund for Distinguished Young Scholars of China under Grant No. 60925010, the National Natural Science Foundation of China under Grant Nos. 61133015, 61003280, and 61272517, the Funds for Creative Research Groups of China under Grant No. 61121001, the Program for Changjiang Scholars and Innovative Research Team in University of China under Grant No. IRT1049, and the Research Fund for the Doctoral Program of Higher Education of China under Grant No. 20120005130002.

Routing is one of the challenging tasks in Delay Tolerant Networks (DTNs), due to the lack of global knowledge and sporadic contacts between nodes. Most existing studies take a greedy scheme in data forwarding process, i.e., only nodes with higher utility values than current carriers can be selected as relays. They lack an in-depth investigation on the main features of the optimal paths in Epidemic. These features are vital to any forwarding scheme that tends to make a trade-off between packet delivery delay and cost. This is mainly because Epidemic provides an upper bound on cost and a lower bound on delivery delay. Therefore, a deep understanding of these features is useful to make informed forwarding decisions. In this paper, we try to explore these features by observing the roles of different social relationships in the optimal paths through a set of real datasets. These datasets provide evidence that strangers have two sides in data forwarding process, and that the importance of strangers shows a decreasing trend along the forwarding paths. Using this heuristic knowledge, we propose STRON, a distributed and lightweight forwarding scheme. The distributed feature makes it very suitable for opportunistic scenarios and the low communication and computation features make it easy to be integrated with state-of-the-art work. The trace-driven simulations obviously confirm its effectiveness, especially in terms of packet delivery delay and cost.

[1] Fall K, Farrell S. DTN: An architectural retrospective. IEEE Journal on Selected Areas in Communications, 2008, 26(5): 828-836.

[2] Conti M, Kumar M. Opportunities in opportunistic computing. Computer, 2010, 43(1): 42-50.

[3] Vahdat A, Becker D. Epidemic routing for partially connected ad hoc networks. Technical Report CS-200006, Duke University, 2000.

[4] Burgess J, Gallagher B, Jensen D, Levine B N. MaxProp: Routing for vehicle-based disruption-tolerant networks. In Proc. the 25th INFOCOM, April 2006, pp.1-11.

[5] Lindgren A, Doria A, Schelen O. Probabilistic routing in intermittently connected networks. ACM SIGMOBILE Mobile Computing and Communications Review, 2003, 7(3): 19-20.

[6] Leguay J, Friedman T, Conan V. Evaluating mobility pattern space routing for DTNs. In Proc. the 25th INFOCOM, April 2006, pp.1-10.

[7] Yuan P, Ma H. Hug: Human gathering point based routing for opportunistic networks. In Proc. WCNC, March 2012, pp.3024-3029.

[8] Nguyen N, Dinh T, Tokala S. Thai M. Overlapping communities in dynamic networks: Their detection and mobile applications. In Proc. the 17th MOBICOM, Sept. 2011, pp.85-96.

[9] Hui P, Crowcroft J, Yoneki E. BUBBLE rap: Social-based forwarding in delay tolerant networks. In Proc. the 9th MobiHoc, May 2008, pp.241-250.

[10] Mtibaa A, May M, Diot C, Ammar M. PeopleRank: Social opportunistic forwarding. In Proc. the 29th INFOCOM, March 2010, pp.111-115.

[11] Daly E, Haahr M. Social network analysis for routing in disconnected delay-tolerant MANETs. In Proc. the 8th MobiHoc, Sept. 2007, pp.32-40.

[12] Palla G, Derényi I, Farkas I, Vicsek T. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 2005, 435(7043): 814-818.

[13] Shah R, Roy S, Jain S et al. Data MULEs: Modeling and analysis of a three-tier architecture for sparse sensor networks. Ad Hoc Networks, 2003, 1(2/3): 215-233.

[14] Li Q, Rus D. Sending messages to mobile users in disconnected ad-hoc wireless networks. In Proc. the 6th MobiCom, Aug. 2000, pp.44-55.

[15] Zhao W, Ammar M, Zegura E. A message ferrying approach for data delivery in sparse mobile ad hoc networks. In Proc. the 5th MobiHoc, Sept. 2004, pp.187-198.

[16] Zhao W, Ammar M, Zegura E. Controlling the mobility of multiple data transport ferries in a delay-tolerant network.In Proc. the 24th INFOCOM, March 2005, pp.1407-1418.

[17] He T, Lee K, Swami A. Flying in the dark: Controlling autonomous data ferries with partial observations. In Proc. the 11th MobiHoc, Sept. 2010, pp.141-150.

[18] Spyropoulos T, Psounis K, Raghavendra C. Efficient routing in intermittently connected mobile networks: The multiplecopy case. Transactions on Networking, 2008, 16(1): 77-90.

[19] Qin R, Li Z, Wang Y et al. An integrated network of roadside sensors and vehicles for driving safety: Concept, design and experiments. In Proc. the 8th PerCom, March 29-April 2, 2010, pp.79-87.

[20] Ivancic W, Wood L, Hdiday P et al. Experience with delaytolerant networking from orbit. In Proc. the 4th ASMS, Aug. 2008, pp.173-178.

[21] Merugu S, Ammar M, Zegura E. Routing in space and time in networks with predictable mobility. Technical Report GITCC-04-7, Georgia Institute of Technology, 2004.

[22] Jain S, Fall K, Patra S. Routing in a delay tolerant network. In Proc. the ACM SIGCOMM, Aug. 30-Sept. 3, 2004, pp.145158.

[23] Liu C, Wu J. Routing in a cyclic mobispace. In Proc. the 9th MobiHoc, May 2008, pp.351-360.

[24] Musolesi M, Hailes S, Mascolo C. Adaptive routing for intermittently connected mobile ad hoc networks. In Proc. the 6th WoWMoM, June 2005, pp.183-189.

[25] Yuan Q, Cardei I, Wu J. Predict and relay: An efficient routing in disruption-tolerant networks. In Proc. the 10th MobiHoc, May 2009, pp.95-104.

[26] Gaito S, Pagani E, Rossi G. Strangers help friends to communicate in opportunistic networks. Computer Networks, 2011, 55(2): 374-385.

[27] Yoneki E, Hui P, Crowcroft J. Visualizing community detection in opportunistic networks. In Proc. the 2nd CHANTS, Sept. 2007, pp.93-96.

[28] Hui P. People are the network: Experimental design and evaluation of social-based forwarding algorithms. Technical Report UCAM-CL-TR-713, University of Cambridge, March 2008.

[29] Rhee I, Shin M, Hong S et al. On the levy-walk nature of human mobility. In Proc. the 27th INFOCOM, April 2008, pp.924-932.

[30] Lee K, Hong S, Kim S et al. SLAW: A mobility model for human walks. In Proc. the 28th INFOCOM, April 2009, pp.855-863.

[31] Zyba G, Voelker G, Ioannidis S et al. Dissemination in opportunistic mobile ad-hoc networks: The power of the crowd. In Proc. the 30th INFOCOM, April 2011, pp.1179-1187.

[32] Pietiläinen A, Diot C. Dissemination in opportunistic social networks: The role of temporal communities. In Proc. the 13th MobiHoc, June 2012, pp.165-174.

[33] Sarwar B, Karypis G, Konstan J et al. Application of dimensionality reduction in recommender system——A case study. In Proc. WEBKDD, Aug. 2000, pp.1-12.

[34] Zhang Y, Yu T. Mining trust relationships from online social networks. Journal of Computer Science and Technology, 2012, 27(3): 492-505.
No related articles found!
Full text



[1] Harald E. Otto;. UNDO, An Aid for Explorative Learning?[J]. , 1992, 7(3): 226 -236 .
[2] Ma Songde; Wei Guoqing; Huang Jinfeng;. Segment Based Camera Calibration[J]. , 1993, 8(1): 11 -16 .
[3] Hu zhanyi; YANG Changjiang; YANG Yi; MA Songde;. An Inherent Probabilistic Aspect of the Hough Transform[J]. , 1999, 14(1): 44 -48 .
[4] LI Xiaoshan;. Decidability of Mean Value Calculus[J]. , 1999, 14(2): 173 -180 .
[5] LIU Yunlong; CHEN Junliang;. Garbage Collection in Uncoordinated Checkpointing Algorithms[J]. , 1999, 14(3): 242 -249 .
[6] HUANG Xiong; LI wei;. On k-Positive Satisfiability Problem[J]. , 1999, 14(4): 309 -313 .
[7] QI Yuesheng; WANG Baozhong; KANG Lishan;. Genetic Programming with Simple Loops[J]. , 1999, 14(4): 429 -433 .
[8] LIU Bin; LU Zengxiang; GAN Quan; FENG Ao; WANG Pu;. Infomarker—A New Internet Information Service System[J]. , 2000, 15(3): 300 -304 .
[9] Guo-Ren Wang and Xiao-Lin Zhang. Declarative XML Update Language Based on a Higher Data Model[J]. , 2005, 20(3): 373 -377 .
[10] Wei Hu, Kai-Huai Qin, Hua-Wei Wang, and Ya-Feng Li. Reflection and Refraction on Implicit Surfaces[J]. , 2006, 21(2): 166 -172 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved