›› 2016, Vol. 31 ›› Issue (6): 1228-1245.doi: 10.1007/s11390-016-1694-7

Special Issue: Computer Networks and Distributed Computing

• Regular Paper • Previous Articles     Next Articles

A Buffer Scheduling Method Based on Message Priority in Delay Tolerant Networks

En Wang1,2, Yong-Jian Yang1*, Jie Wu2, Fellow, IEEE, Wen-Bin Liu3   

  1. 1 Department of Computer Science and Technology, Jilin University, Changchun 130012, China;
    2 Department of Computer and Information Sciences, Temple University, Philadelphia 19122, U.S.A;
    3 Department of Software, Jilin University, Changchun 130012, China
  • Received:2016-03-17 Revised:2016-06-03 Online:2016-11-05 Published:2016-11-05
  • Supported by:

    This work was supported by the National Natural Science Foundation of China under Grant No. 61272412, the Specialized Research Fund for the Doctoral Program of Higher Education of China under Grant No. 20120061110044, and the Science and Technology Development Program of Jilin Province of China under Grant No. 20120303. This work was also supported in part by the National Science Foundation of United States under Grant Nos. CNS 149860, CNS 1461932, CNS 1460971, CNS 1439672, CNS 1301774, ECCS 1231461, ECCS 1128209, and CNS 1138963.

Routing protocols in delay tolerant networks usually utilize multiple message copies to guarantee the message delivery,in order to overcome unpredictable node mobility and easily-interrupted connections.A store-carry-and-forward paradigm was also proposed to further improve the message delivery.However,excessive message copies lead to the shortage of buffer and bandwidth.The spray and wait routing protocol has been proposed to reduce the network overload caused by the buffer and transmission of unrestricted message copies.However,when a node's buffer is quite constrained,there still exist congestion problems.In this paper,we propose a message scheduling and drop strategy on spray and wait routing protocol (SDSRP).To improve the delivery ratio,first of all,SDSRP calculates the priority of each message by evaluating the impact of both replicating and dropping a message copy on delivery ratio.Subsequently,scheduling and drop decisions are made according to the priority.In order to further increase delivery ratio,we propose an improved message scheduling and drop strategy on spray and wait routing protocol (ISDSRP) through enhancing the accuracy of estimating parameters.Finally,we conduct extensive simulations based on synthetic and real traces in ONE.The results show that compared with other buffer management strategies,ISDSRP and SDSRP achieve higher delivery ratio,similar average hopcounts,and lower overhead ratio.

[1] Fall K. A delay-tolerant network architecture for challenged Internets. In Proc. the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, Aug. 2003, pp.27-34.

[2] Akyildiz I F, Akan O B, Chen C Fang J, Su W L. InterPlaNetary Internet:State-of-the-art and research challenges. Computer Networks, 2003, 43(2):75-112.

[3] Uddin M Y S, Ahmadi H, Abdelzaher T, Kravets R. Intercontact routing for energy constrained disaster response networks. IEEE Transactions on Mobile Computing, 2013, 12(10):1986-1998.

[4] Pentland A, Fletcher R, Hasson A. Daknet:Rethinking connectivity in developing nations. Computer, 2004, 37(1):78-83.

[5] Juang P, Oki H, Wang Y, Martonosi M, Peh L S, Rubenstein D. Energy-efficient computing for wildlife tracking:Design tradeoffs and early experiences with ZebraNet. In Proc. the 10th International Conference on Architectural Support for Programming Languages and Operating Systems, Dec. 2002, pp.96-107.

[6] Xiao M J, Wu J, Huang L S.Community-aware opportunistic routing in mobile social networks. IEEE Transactions on Computers, 2014, 63(7):1682-1695.

[7] Vahdat A, Becker D. Epidemic routing for partiallyconnected ad hoc networks. Technical Report CS-2000-06, Department of Computer Science, Duke University, 2000.

[8] Spyropoulos T, Psounis K, Raghavendra C S.Spray and wait:An efficient routing scheme for intermittently connected mobile networks. In Proc. the ACM SIGCOMM Workshop on Delay-Tolerant Networking, Aug. 2005, pp.252-259.

[9] Wang E, Yang Y J, Wu J. A Knapsack-based buffer management strategy for delay-tolerant networks. Journal of Parallel and Distributed Computing, 2015, 86:1-15.

[10] Lindgren A, Phanse K S.Evaluation of queueing policies and forwarding strategies for routing in intermittently connected networks. In Proc. the 1st International Conference on Communication System Software and Middleware, Jan. 2006, pp.1-10.

[11] Kim D, Park H, Yeom I. Minimizing the impact of buffer overflow in DTN. In Proc. International Conference on Future Internet Technologies (CFI), Jan. 2008.

[12] Li Y, Qian M J, Jin D P, Su L, Zeng L G. Adaptive optimal buffer management policies for realistic DTN. In Proc. IEEE Global Telecommunications Conference, Nov. 30-Dec. 4, 2009.

[13] Zhang X L, Neglia G, Kurose J, Towsley D. Performance modeling of epidemic routing. Computer Networks, 2007, 51(10):2867-2891.

[14] Elwhishi A, Ho P H, Naik K, Shihada B. A novel message scheduling framework for delay tolerant networks routing. IEEE Transactions on Parallel and Distributed Systems, 2013, 24(5):871-880.

[15] Krifa A, Barakat C, Spyropoulos T. Optimal buffer management policies for delay tolerant networks. In Proc. the 5th Annual IEEE Communications Society Sensor, Mesh and Ad Hoc Communications and Networks, June 2008, pp.260-268.

[16] Krifa A, Barakat C, Spyropoulos T. An optimal joint scheduling and drop policy for delay tolerant networks. In Proc. International Symposium on a World of Wireless, Mobile and Multimedia Networks, June 2008, pp.1-6.

[17] Krifa A, Barakat C, Spyropoulos T. Message drop and scheduling in DTNs:Theory and practice. IEEE Transactions on Mobile Computing, 2012, 11(9):1470-1483.

[18] Ramiro V, Dang D K, Baudic G, Pérennou T, Lochin E. A Markov chain model for drop ratio on onepacket buffers DTNs. In Proc. the 16th International Symposium on a World of Wireless, Mobile and Multimedia Networks, June 2015.

[19] Nishiyama H, Takahashi A, Kato N, Nakahira K, Sugiyama T. Dynamic replication and forwarding control based on node surroundings in cooperative delay-tolerant networks. IEEE Transactions on Parallel and Distributed Systems, 2015, 26(10):2711-2719.

[20] Niyato D, Wang P, Tan H P, Saad W, Kim D I. Cooperation in delay-tolerant networks with wireless energy transfer:Performance analysis and optimization. IEEE Transactions on Vehicular Technology, 2015, 64(8):3740-3754.

[21] Spyropoulos T, Psounis K, Raghavendra C S.Spray and focus:Efficient mobility-assisted routing for heterogeneous and correlated mobility. In Proc. the 5th Annual IEEE International Conference on Pervasive Computing and Communications Workshop, March 2007, pp.79-85.

[22] Kim Y P, Koo J I, Jung E, Nakano K, Sengoku M, Park Y J. Composite methods for improving spray and wait routing protocol in delay tolerant networks. In Proc. IEEE International Symposium on Communications and Information Technologies, Oct. 2010, pp.1229-11234.

[23] Iqbal S M A. Multischeme spray and wait routing in delay tolerant networks exploiting nodes delivery predictability. In Proc. the 15th International Conference on Computer and Information Technology, Dec. 2012, pp.255-260.

[24] Gao W, Li Q H, Cao G H. Forwarding redundancy in opportunistic mobile networks:Investigation elimination and exploitation. IEEE Transactions on Mobile Computing, 2015, 14(4):714-727.

[25] Wang E, Yang Y J, Wu J, Liu W B. A buffer management strategy on spray and wait routing protocol in DTNs. In Proc. the 44th International Conference on Parallel Processing, Sept. 2015.

[26] Groenevelt R, Nain P, Koole G. Message delay in MANET. In Proc. International Conference on Measurement and Modeling of Computer Systems, June 2005, pp.412-413.

[27] Keränen A, Ott J, Kärkkäinen T. The ONE simulator for DTN protocol evaluation. In Proc. the 2nd International Conference on Simulation Tools and Techniques, March 209, Article No. 55.

[28] Abdelkader T, Naik K, Nayak A, Goel N, Srivastava V. A performance comparison of delay-tolerant network routing protocols. IEEE Network, 2016, 30(2):46-53.
No related articles found!
Full text



[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[10] Li Minghui;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .

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