An intelligent approach in delay tolerant network routing

Delay tolerant networks (DTNs) are wireless intermittent networks. DTNs have different applications such as wildlife tracking, military, and space searching. Conventional mobile ad hoc network (MANET) routing protocols are not efficient in these networks because of intermittency. DTNs use store-carry-forward (SCF) for data transferring. In SCF, nodes store the messages and carry them until finding appropriate nodes for forwarding. Message replication greatly helps to improve the delivery ratio while increasing overhead. This paper examines the use of intelligent routing to choose nodes that have more probability to reach their destination. This will help to increase the message delivery ratio while reducing overhead. The proposed method, SADTN, uses simulated annealing (SA), which has shown successful results in finding global minimal, to find the next hop. Comparison of the proposed method to previously implemented methods such as epidemic routing (ER) and Probabilistic ROuting Protocol using History of Encounters and Transitivity (PROPHET), which are usually used for evaluating other methods, shows increasing message delivery ratio and decreasing overhead in SADTN. Overhead in SADTN has on average fallen to 0.01484 of ER and 0.02325 of PROPHET. This is a great advantage of SADTN.

PDF

___

[1] Fall K. A delay-tolerant network architecture for challenged Internets. In: ACM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (ser. SIGCOMM03); 2529 August 2003; Karlsruhe, Germany. New York, NY, USA: ACM. pp. 27-34.
[2] Ho M, Fall K. Poster: Delay tolerant networking for sensor networks. In: IEEE Conference on Sensor and Ad Hoc Communications and Networks; 47 October 2004; Santa Clara, USA. New York, NY, USA: IEEE. pp. 1-3.
[3] Juang P, Oki H, Wang Y, Martonosi M, Peh LS, Rubenstein D. Energy-efficient computing for wildlife tracking: design tradeoffs and early experiences with Zebranet. In: The 10th International Conference on Architectural Support for Programming Language Design and Implementation (ASPLOS-X 2002); 59 October 2002; San Jose, CA, USA. New York, NY, USA: ACM. pp. 96-107.
[4] Burleigh S, Hooke A, Torgerson L, Fall K, Cerf V, Durst B, Scott K. Delay-tolerant networking: an approach to interplanetary internet. IEEE Commun Mag 2003; 41: 128-136.
[5] Rango FD, Tropea M, Laratta GB, Marano S. Hop-by-hop local flow control over interplanetary networks based on DTN architecture. In: IEEE International Conference on IEEE IC Communications (ICC 08); 1923 May 2008; Beijing, China. New York, NY, USA: IEEE. pp. 1920-1924.
[6] Partan J, Kurose K, Levine BN. A survey of practical issues in underwater networks. In: The First ACM International Workshop on Underwater Networks (WUWNet 06); 2929 September 2006; Los Angeles, CA, USA. New York, NY, USA: ACM. pp. 17-24.
[7] Geo W, Li Q, Zhao B, Cao G. Multi-casting in delay-tolerant networks: a social network perspective. In: The Tenth ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 09); 1821 May 2009; New Orleans, LA, USA. New York, NY, USA: ACM. pp. 299-308.
[8] Jain S, Fall K, Patra R. Routing in a delay-tolerant network. ACM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM 04); 30 August3 September 2004; Portland, OR, USA. New York, NY, USA: ACM. pp. 145-158.
[9] Zhang Z. Routing in intermittently connected mobile ad hoc networks and delay-tolerant networks: overview and challenges. Commun Surveys Tuts 2006; 8: 24-37.
[10] Fall K, Farell S. DTN: an architectural retrospective. IEEE J Sel Areas Commun 2008; 26: 828-836.
[11] Spyropoulos T, Rais TRNB, Turletti T, Obraczka K, Vasilakos A. Routing for disruption tolerant networks: taxonomy and design. Wirel Netw 2010; 16: 2349-2370.
[12] Small T, Haas Z. Resource and performance tradeoffs in delay-tolerant wireless networks. In: ACM SIGCOMM Workshop on Delay Tolerant Networking (WDTN); 2226 August 2005; Philadelphia, PA, USA. New York, NY, USA: ACM. pp. 260-267.
[13] Balasubramanian A, Levine BN, Venkataramani A. DTN routing as a resource allocation problem. CCR 2007; 37: 373-384.
[14] Jain S, Demmer M, Patra R, Fall K. Using redundancy to cope with failures in a delay tolerant network. In: ACM SIGCOMM 2005 (SIGCOMM05); 2226 August 2005; Philadelphia, PA, USA. New York, NY, USA: ACM. pp. 109-120.
[15] Wang Y, Jain S, Martonosi M, Fall K. Erasure coding based routing for opportunistic networks. In: The 2005 ACM SIGCMM workshops on delay tolerant networking (WDTN 05); 2226 August 2005; Philadelphia, PA, USA. New York, NY, USA: ACM, pp. 229-236.
[16] Vahdat A, Becker D. Epidemic routing for partially connected ad hoc networks. Tech. Rep. CS.-2000-06, Duke University, Durham, NC, USA, 2000.
[17] Zhang X, Neglia G, Kurose J, Towsley D. Performance modeling of epidemic routing. Comput Netw 2007; 51: 2867-2891.
[18] Spyropoulos T, Psounis K, Raghavendra CS. Spray and wait: an efficient routing scheme for intermittently connected mobile networks. In: The 2005 ACM SIGCOMM workshop on delay-tolerant networking (WDTN 05); 2226 August 2005; Philadelphia, PA, USA. New York, NY, USA: ACM, pp. 252-259.
[19] Spyropoulos T, Psounis K, Raghavendra CS. Efficient routing in intermittently connected mobile networks: the single-copy case. IEEE/ACM Trans Netw 2008; 16: 63-76.
[20] Davis JA, Fagg AH, Levine BN. Wearable computers as packet transport mechanisms in high-partitioned ad hoc networks. In: International Symposium on Wearable Computers 2011 (ISWC01); 1215 June 2011; San Francisco, CA, USA: pp. 141-148.
[21] Burgess J, Gallagher B, Jensen D, Levine BN. Maxprop: routing for vehicle-based disruption-tolerant networks. In: The 25th Conference on Computer Communications (INFOCOM 2006); 2329 April 2006; Barcelona, Spain. New York, NY, USA: IEEE. pp. 1-11.
[22] Lindgren A, Doria A, Scheln O. Probabilistic routing in intermittently connected networks. Lect Notes Comput Sc 2004; 3126: 239-254.
[23] Balasubramanian A, Levine BN, Venkataramani A. Replication routing in DTNs: a resource allocation approach. IEEE/ACM Trans Netw 2010; 18: 596-609.
[24] Hui P, Crowcroft J. How small labels create big improvements. In: IEEE PERCOM Workshops, Pervasive Computing and Communications Workshops (Workshops 07); 1923 March 2007; White Plains, NY, USA. New York, NY, USA: IEEE. pp. 65-70.
[25] Hui P, Crowcroft J, Yoneki E. Bubble Rap: social-based forwarding in delay tolerant networks. In: The 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 08); 2730 May 2008; Hong Kong SAR, China. New York, NY, USA: ACM. pp. 241-250.
[26] Costa P, Mascolo C, Musolesi M, Picco GP. Socially-aware routing for publish-subscribe in delay-tolerant mobile ad hoc networks. IEEE J Sel Areas Commun 2008; 26: 748-760.
[27] Cao Y, Sun Z, Wang N, Riaz M, Cruichshank H, Liu X. Geographic-based Spray-and-Relay (GSaR): an efficient routing scheme for DTNs. IEEE T Veh Technol 2014; 64: 1548-1564.
[28] Cao Y, Sun Z, Cruichshank H, Yao F. Approach-and-Roam (AaR): a geographic routing scheme for delay/disruption tolerant networks. IEEE T Veh Technol 2014; 63: 266-281.
[29] Lee K, Li Y, Joe I, Choi Y. Selective 2-phase spray and wait routing for overhead reduction in delay tolerant networks. In: 2014 International Conference on Information Science and Applications (ICISA); 69 May 2014; Seoul, South Korea: pp. 1-3.
[30] Iqbal SMA. Multischeme spray and wait routing in delay tolerant networks exploiting nodes delivery predictability. In: 15th International Conference on Computer and Information Technology (ICCIT); 2224 December 2012; Chittagong, Bangladesh: pp. 255-300.
[31] Kirkpatrick S, Gelatt CD, Vecchi MP. Optimization by simulated annealing. Science 1983; 220: 671-680.
[32] Eberhart R, Shi Y, Kennedy J. Swarm Intelligence. San Francisco, CA, USA: Morgan Kaufmann Publishers, 2001.
[33] Metropolis N, Rosenbluth AW, Rosenbluth M, Teller AH, Teller E. Equation of state calculations by fast computing machines. J Chem Phys 1953; 21: 1087-1092.
[34] Goldberg DE. Genetic Algorithms in Search, Optimization, and Machine Learning. Boston, MA, USA: AddisonWesley Longman Publishing, 1989.
[35] Wu Y, Deng S, Huang H, Deng Y. Performance analysis of cell-phone worm spreading in cellular networks through opportunistic communications. AECE 2012; 12: 3-8.
[36] Groenevelt R. Stochastic models for mobile ad hoc networks. PhD, University of Nice Sophia Antipolis, Nice, France, 2005.
[37] Spyropoulos T, Psounis K, Raghavendra CS. Performance analysis of mobility- assisted routing. In: The 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 06); 2225 May 2006; Florence, Italy. New York, NY, USA: ACM. pp. 49-60.
[38] Bettstetter C, Hartenstein H, P´erez-Costa X. Stochastic properties of the random waypoint mobility model: epoch length, direction distribution, and cell change rate. In: The 5th ACM international workshop on modeling analysis and simulation of wireless and mobile systems (MSWiM 02); 2828 September 2002; Atlanta, GA, USA. New York, NY, USA: ACM. pp. 7-14.
[39] Yoon J, Liu M, Noble B. Random waypoint considered harmful. In: Twenty-Second Annual Joint Conference of the IEEE Computer and Communications (INFOCOM 2003); 30 March3 April 2003; San Francisco, CA, USA. New York, NY, USA: IEEE. pp. 1312-1321.
[40] Ker¨anen A, K¨arkk¨ainen T, Ott J. Simulating mobility and DTNs with the ONE. JCM 2010; 5: 92-105.