We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 28 Issue 3
May  2013
Turn off MathJax
Article Contents
Abstract
References
Related Articles
Pei-Yan Yuan, Hua-Dong Ma, Peng-Rui Duan. Impact of Strangers on Opportunistic Routing Performance[J]. Journal of Computer Science and Technology, 2013, 28(3): 574-582. DOI: 10.1007/s11390-013-1357-x
Citation: Pei-Yan Yuan, Hua-Dong Ma, Peng-Rui Duan. Impact of Strangers on Opportunistic Routing Performance[J]. Journal of Computer Science and Technology, 2013, 28(3): 574-582. DOI: 10.1007/s11390-013-1357-x
shu

Impact of Strangers on Opportunistic Routing Performance

  • Beijing Key Laboratory of Intelligent Telecommunications Software and Multimedia, Beijing University of Posts and Telecommunications, Beijing 100876, China

Funds: 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.
More Information
  • Received Date: May 02, 2012
  • Revised Date: January 17, 2013
  • Published Date: May 04, 2013
    Abstract
  • 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.
    • FullText(HTML)
    • References (34)
  • [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.
    • Relative Articles

  • Related Articles

    [1]En Wang, Wei-Shih Yang, Yong-Jian Yang, Jie Wu, Wen-Bin Liu. An Efficient Message Dissemination Scheme for Minimizing Delivery Delay in Delay Tolerant Networks[J]. Journal of Computer Science and Technology, 2018, 33(6): 1101-1124. DOI: 10.1007/s11390-018-1875-7
    [2]En Wang, Yong-Jian Yang, Jie Wu, Wen-Bin Liu. A Buffer Scheduling Method Based on Message Priority in Delay Tolerant Networks[J]. Journal of Computer Science and Technology, 2016, 31(6): 1228-1245. DOI: 10.1007/s11390-016-1694-7
    [3]Jian-Yun Liu, Yu-Hang Zhao, Zhao-Xiang Zhang, Yun-Hong Wang, Xue-Mei Yuan, Lei Hu, Zhen-Jiang Dong. Spam Short Messages Detection via Mining Social Networks[J]. Journal of Computer Science and Technology, 2012, 27(3): 506-514. DOI: 10.1007/s11390-012-1239-7
    [4]Yu Zhang, Tong Yu. Mining Trust Relationships from Online Social Networks[J]. Journal of Computer Science and Technology, 2012, 27(3): 492-505. DOI: 10.1007/s11390-012-1238-8
    [5]Xu-Guang Guan, Xing-Yuan Tong, Yin-Tang Yang. Quasi Delay-Insensitive High Speed Two-Phase Protocol Asynchronous Wrapper for Network on Chips[J]. Journal of Computer Science and Technology, 2010, 25(5): 1092-1100. DOI: 10.1007/s11390-010-1086-3
    [6]Ming-Jun Xiao, Liu-Sheng Huang, Qun-Feng Dong, An Liu, Zhen-Guo Yang. Leapfrog: Optimal Opportunistic Routing in Probabilistically Contacted Delay Tolerant Networks[J]. Journal of Computer Science and Technology, 2009, 24(5): 975-986.
    [7]SHU Yantai, XUE Fei, JIN Zhigang, Oliver Yang. The Impact of Self-Similar Traffic on Network Delay[J]. Journal of Computer Science and Technology, 1999, 14(6): 585-589.
    [8]MIN Yinghua, LI Zhongcheng. An Analytical Delay Model[J]. Journal of Computer Science and Technology, 1999, 14(2): 97-115.
    [9]Min Youli, Min Yinghua. A Fault-Tolerant and Heuristic Routing Algorithm for Faulty Hypercubes[J]. Journal of Computer Science and Technology, 1995, 10(6): 536-544.
    [10]Deng Yaping, Chen Tinghuai. A Reliable and Fault-Tolerant Interconnection Network[J]. Journal of Computer Science and Technology, 1990, 5(2): 117-126.
    • Supplements (0)

Catalog

    Get Citation
    PDF
    XML
    Article views (14) PDF downloads (1444) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return