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 24 Issue 5
September  2009
Turn off MathJax
Article Contents
Abstract
References
Related Articles
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.
Citation: 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.
shu

Leapfrog: Optimal Opportunistic Routing in Probabilistically Contacted Delay Tolerant Networks

  • School of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, China
    Suzhou Institute for Advanced Study, University of Science and Technology of China, Suzhou 215023, China

Funds: This work is supported by the National Basic Research 973 Program of China under Grant No. 2006CB303006, the National Natural Science Foundation of China under Grant No. 60803009, and the National Research Foundation for the Doctoral Program of Higher Education of China under Grant No. 20070358075.
More Information
  • Author Bio:

    Ming-Jun Xiao was born in 1976. He receivedthe Ph.D. degree in computer science from University of Science andTechnology of China in 2004. He is currently a lecturer at School ofComputer Science and Technology, University of Science andTechnology of China, and a member of China Computer Federation.His major research interests are wireless network and informationsecurity.

    Liu-Sheng Huang was born in 1957. Hereceived the M.S. degree in computer science from University ofScience and Technology of China in 1988. He is currently a professorand Ph.D. supervisor of the Department of Computer Science andTechnology at University of Science and Technology of China. He isalso a senior member of China Computer Federation. His researchinterests are in the areas of wireless sensor network, distributedcomputing and information security.

    Qun-Feng Dong was born in 1977. He received his Ph.D. degree incomputer science from the University of Wisconsin, Madison. Priorto that, he received his B.S. and M.S. degrees, both in computerscience, from the University of Science and Technology of China andthe University of Massachusetts, Amherst, respectively. Currently,he is a professor with the School of Computer Science and Technologyat the University of Science and Technology of China. His researchinterests include wireless networks, sensor networks, Internet,packet processing and information security.

    An Liu received the Ph.D. degree in computer science from Universityof Science and Technology of China. He is currently a lecturer atCollege of Computer Science and Technology, University of Scienceand Technology of China. His research interests are in the areas ofservice-oriented computing and distributed computing.

    Zhen-Guo Yang was born in 1984. He is a Ph.D. degree candidate inDepartment of Computer Science and Technology, University of Science andTechnology of China. His major research interests are delay tolerant networks and social networks.

  • Revised Date: July 27, 2009
  • Published Date: September 04, 2009
    Abstract
  • Delay tolerant networks (DTNs) experience frequent and long lasting network disconnection due to various reasons such as mobility, power management, and scheduling. One primary concern in DTNs is to route messages to keep the end-to-end delivery delay as low as possible. In this paper, we study the single-copy message routing problem and propose an optimal opportunistic routing strategy --- Leapfrog Routing --- for probabilistically contacted DTNs where nodes encounter or contact in some fixed probabilities. We deduce the iterative computation formulate of minimum expected opportunistic delivery delay from each node to the destination, and discover that under the optimal opportunistic routing strategy, messages would be delivered from high-delay node to low-delay node in the leapfrog manner. Rigorous theoretical analysis shows that such a routing strategy is exactly the optimal among all possible ones. Moreover, we apply the idea of Reverse Dijkstra algorithm to design an algorithm. When a destination is given, this algorithm can determine for each node the routing selection function under the Leapfrog Routing strategy. The computation overhead of this algorithm is only O(n^2) where n is the number of nodes in the network. In addition, through extensive simulations based on real DTN traces, we demonstrate that our algorithm can significantly outperform the previous ones.
    • FullText(HTML)
    • References (18)
  • [1]
    Delay Tolerant Network Research Group. April 28, 2009, http://www.dtnrg. org/.
    [2]
    Burgess J, Gallagher B, Jensen D et al. MaxProp: Routing for vehicle-based disruption-tolerant networks. In Proc. IEEE INFOCOM 2006, Barcelona, Spain, April 23-29, 2006, pp.1-11.
    [3]
    Burns B, Brock O, Levine B N. MV routing and capacity building in disruption tolerant networks. In Proc. IEEE INFOCOM 2005, Miami, USA, March 13-17, 2005, pp.398-408.
    [4]
    Conan V, Leguay J, Friedman T. Fixed point opportunistic routing in delay tolerant networks. IEEE Journal on Selected Areas in Communications, 2008, 26(5): 773-782.
    [5]
    Hui P, Crowcroft C, Yoneki E. BUBBLE rap: Social-based forwarding in delay tolerant networks. In Proc. ACM MobiHoc 2008, Hong Kong, China, May 27-30, 2008, pp.241-250.
    [6]
    Jain S, Fall K, Patra R. Routing in a delay tolerant network. In Proc. ACM SIGCOMM 2004, Portland, USA, August 30- September 3, 2004, pp.145-158.
    [7]
    Jeremie L, Timur F, Vania C. Evaluating mobility pattern space routing for DTNs. In Proc. IEEE INFOCOM 2006, Barcelona, Spain, April 23-29, 2006, pp.1-10.
    [8]
    Lindgren A, Doria A, Schelen O. Probabilistic routing in intermittently connected networks. Lecture Notes in Computer Science, 2004, 3126(1): 239-254.
    [9]
    Cong Liu, Jie Wu. Routing in a cyclic MobiSpace. In Proc. ACM MobiHoc 2008, Hong Kong, China, May 27-30, 2008, pp.351-360.
    [10]
    Spyropoulos T, Psounis K, Raghavendra C. Spray and Wait: An efficient routing scheme for intermittently connected mobile networks. In Proc. ACM SIGCOMM Workshop on Delay-Tolerant Networking (WDTN) 2005, Philadelphia, USA, August 22-26, 2005, pp.252-259.
    [11]
    Vahdate A, Becker D. Epidemic routing for partiallyconnected ad hoc networks. Technical Report CS-2000-06, Duke University, June 2000.
    [12]
    Balazinska M, Castro P. Characterizing mobility and network usage in a corporate wireless local-area network. In Proc. ACM MobiSys 2003, San Francisco, USA, May 5-8, 2003, pp.303-316.
    [13]
    Henderson T, Kotz D, Abyzov I. The changing usage of a mature campus-wide wireless network. In Proc. ACM MobiCom 2004, Philadelphia, USA, September 26-October 1, 2004, pp.187-201.
    [14]
    CRAWDAD data set. April 28, 2009, http://crawdad.cs.dartmouth.edu/.
    [15]
    Srinivasan V, Motani M, Ooi W T. Analysis and implications of student contact patterns derived from campus schedules. In Proc. ACM MobiCom 2006, Los Angeles, USA, September 24-29, 2006, pp.86-97.
    [16]
    Tariq M M B, Ammar M, Zegura E. Message ferry route design for sparse ad hoc networks with mobile nodes. In Proc. ACM MobiHoc 2006, Florence, Italy, May 22-26, 2006, pp.37-48.
    [17]
    Zhao W, Ammar M, Zegura E. A message ferrying approach for data delivery in sparse mobile ad hoc networks. In Proc. ACM MobiHoc 2004, Tokyo, Japan, May 24-26, 2004, pp.187-198.
    [18]
    Balasubramanian A, Levine B N, Venkataramani A. DTN routing as a resource allocation problem. In Proc. ACM SIGCOMM 2007, Kyoto, Japan, August 27-31, 2007, pp.373-384.
    • Relative Articles

  • Related Articles

    [1]Jie Wu, Shu-Hui Yang. Small World Model-Based Polylogarithmic Routing Using Mobile Nodes[J]. Journal of Computer Science and Technology, 2008, 23(3): 327-342.
    [2]Yi-Ci Cai, Bin Liu, Yan Xiong, Qiang Zhou, Xian-Long Hong. Priority-Based Routing Resource Assignment Considering Crosstalk[J]. Journal of Computer Science and Technology, 2006, 21(6): 913-921.
    [3]Hui Tian, Hong Shen, Teruo Matsuzawa. Random Walk Routing in WSNs with Regular Topologies[J]. Journal of Computer Science and Technology, 2006, 21(4): 496-502.
    [4]Yu Hu, Tong Jing, Zhe Feng, Xian-Long Hong, Xiao-Dong Hu, Gui-Ying Yan. ACO-Steiner: Ant Colony Optimization Based Rectilinear Steiner Minimal Tree Algorithm[J]. Journal of Computer Science and Technology, 2006, 21(1): 147-153.
    [5]Imad Jawhar, Jie Wu. QoS Support in TDMA-Based Mobile Ad Hoc Networks[J]. Journal of Computer Science and Technology, 2005, 20(6): 797-810.
    [6]Hai-Long Yao, Yi-Ci Cai, Qiang Zhou, Xian-Long Hong. Crosstalk-Aware Routing Resource Assignment[J]. Journal of Computer Science and Technology, 2005, 20(2).
    [7]Shu-Ming Zhou, Wen-Jun Xiao. A New Family of Interconnection Networks of Fixed Degree Three[J]. Journal of Computer Science and Technology, 2004, 19(2).
    [8]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.
    [9]Li Layuan. A Routing Algorithm for Distributed Optimal Double Loop Computer Networks[J]. Journal of Computer Science and Technology, 1987, 2(2): 92-98.
    [10]Pan Qijing. A Routing Algorithm with Candidate Shortest Path[J]. Journal of Computer Science and Technology, 1986, 1(3): 33-52.
    • Supplements (0)

Catalog

    Get Citation
    XML
    Article views (19) PDF downloads (2626) 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