Improving DTNs Performance by Reduction of Bundles Redundancy using Clustering Algorithm


  • RadosÅ‚aw Olgierd Schoeneich Institute of Telecommunications, Warsaw University of Technology
  • Piotr Prus Institute of Telecommunications Warsaw University of Technology, Poland


Delay Tolerant Networks (DTNs), mobile ad-hoc networks, clustering algorithms, cluster based routing, neighborhood discovery in ad-hoc networks


This article presents complex clustering algorithm for Delay Tolerant Networks (DTNs) including neighborhood discovery, cluster creation, and data distribution within cluster. The general idea is to reduce the amount of messages being sent and of buffer utilization, by taking advantage of the nodes tendency to create groups and to share similar mobility patterns among each other. The main purpose of the algorithm is to improve the network performance without major changes in communication schemes between nodes. Almost no extra message type is added. Most extra features are available thanks to adding small extra fields into transmitted packages. Neighborhood discovery is being realized passively by listening to other nodes messages. The proposed algorithms allow to reduce both the bandwidth occupation, as well as the problems related to the media access. Furthermore, it can increase message delivery probability thanks to intelligent package distribution inside created cluster. Simulations were carried out to evaluate the effectiveness of the proposed solution in terms of package delivery probability, mean buffer occupancy and mean hop number to delivery the message. Results of simulation show that this solution is not necessary or recommended for small-scale networks with few nodes using clustering algorithms. However, with increasing number of nodes and messages, the performance of non-clustered DTNs drops significantly while clustered network works efficiently.


Ahn, CW.; Ramakrishna, RS.; Kang CG. (2002); Efficient Clustering-based Routing Protocol in Mobile Ad-Hoc Networks, in Proc. IEEE VTC 02, 1647-1651, 2002.

Burleigh, S.; Hooke, A.; Torgerson, L.; Fall, K.; Cerf, V.; Durst, B.; Scott, K.; Weiss H. (2003); Delay-tolerant networking: an approach to interplanetary internet, IEEE Commun. Mag., 128-136, 2003.

Buttyan, L.; Schaoer, P. (2010); PANEL: Position-Based Aggregator Node Election in Wireless Sensor Networks, Int.J. Distrib. Sens. Netw, 1-16, 2010.

Chan, H.; Perrig, A. (2004); An Emergent Algorithm for Highly Uniform Cluster Formation, Wireless Sensor Network, 154-171, 2004.

Chiang, CC.; Wu, HK.; Liu, A.; Gerla M. (1998); Routing in clustered multi-hop mobile wireless networks with fading channel, in Proc. of IEEE SICON 98, 197-211, 1998.

Crepaldi, R.; Bakht, M.; Kravets R. (2012); QuickSilver: application-driven inter- and intra-cluster communication in Vanets, in Proc. ACM MobiOpp 02,, 69-76, 2012.

Dang, H.; Wu H. (2010); Clustering and Cluster-based Routing Protocol for Delay-tolerant Mobile Networks, IEEE Trans. Wireless. Comm, 9(6), 1874-1881, 2010.

Ding, P.; Holliday, J.; Celik A. (2005); Distributed Energy Effcient Hierarchical Clustering for Wireless Sensor Networks. in Proc. IEEE DCOSS, 322-339, 2005.

Fall, K. (2003); A delay-tolerant network architecture for chalenged internets, in Proc. of The 2003 conference on Applications, technologies, architectures, and protocols for computer communications (SIGCOMM '03), 27-34, 2003.

Fan, CS. (2016); HIGH: A Hexagon-based Intelligent Grouping Approach in Wireless Sensor Networks, Advances in Electrical and Computer Engineering, 16(1), 41-46, 2016.

Fang, W.; Li, S.; Liang, X.; Li, Z. (2012); Cluster-based Data Gathering in Long- Strip Wireless Sensor Networks, Advances in Electrical and Computer Engineering, 12(1), 3-8, 2012.

Golanski, M.; Schoeneich, RO.; Siwko, M. (2010); The algorithm for distribution of largesize data in the Wireless Ad-hoc Sensor Network, in proc. Concepts and Implementation for Innovative Military Communications and Information Technologies, Military University of Technology, 577-584, 2010.

Heinzelman, WR.; Chandrakasan, A.; Balakrishnan, H. (2000); Energy-Efficient Communication Protocol for Wireless Microsensor Networks. in Proc. HICSS 07, 10-19, 2000.

Iwata, A.; Chiang, C-C.; Gerla, M;, Chen. TW. (1999); Scalable Routing Strategies for Ad hoc Wireless Networks, IEEE Journal on Selected Areas in Communications, 17, 1369-1379, 1999.

Jacquet, P.; Muhlethaler, P.; Clausen, T.; Laouiti, A.; Qayyum, A.; Viennot, L. (2001); Optimized Link State Routing Protocol for Ad Hoc Networks, IEEE Trans. Wireless. Comm., 62-68, 2001.

Jung, S.; Han, Y.; Chung, T. (2007); The Concentric Clustering Scheme for Effcient Energy Consumption in the PEGASIS. in Proc. IEEE ICACT 07, 260-265, 2007.

Kim, SK.; Yoon, JH.; Lee, J.; Yang, SB. (2015); HCS: hierarchical cluster-based forwarding scheme for mobile social networks, Wirel. Netw., 21(5), 1699-1711, 2015.

Koutsonikola, D.; Das, S.; Charlie, HY.; Stojmenovic, I. (2010); Hierarchical geographic multicast routing for wireless sensor networks, Wirel. Netw., 16(2), 449-466, 2010.

Li, C.; Ye, M.; Chen, G.; Wu, J. (2005); An Energy Effcient Unequal Clustering Mechanism for Wireless Sensor Networks, in Proc. IEEE MASS 05, 596-604, 2005.

Lindgren, A.; Doria, A.; Schelen, O. (2003); Probabilistic routing in intermittently connected networks, ACM SIGMOBILE Mobile Computing and Communications Review, 19-20, 2003.

Lindsey, S.; Raghavendra, C.; Sivalingam, LM. (2002); Data gathering algorithms in sensor networks using energy metrics, IEEE Trans. Parallel Distrib. Syst., 13(9), 924-935, 2002.

Liu, X. (2012); A Survey on Clustering Routing Protocols in Wireless Sensor Networks. Sensors, 11113-11153, 2012.

Luo, H.; Ye, F.; Cheng, J.; Lu, S.; Zhang, L. (2005); TTDD: Two-tier data dissemination in large-scale wireless sensor networks, Wirel. Netw., 11(1), 160-175, 2005.

Loscri, V.; Morabito, G.; Marano, S. (2005); A Two-Level Hierarchy for Low-Energy Adaptive Clustering Hierarchy, in Proc. IEEE VTC -5, 1809-1813, 2005.

Manjeshwar, E.; Agrawal, DP. (2001); TEEN: A Routing Protocol for Enhanced Effciency in Wireless Sensor Networks, in Proc. IEEE IPDPS 01, 2009-2015, 2001.

Manjeshwar, E.; Agrawal, DP. (2002); APTEEN: A Hybrid Protocol for Effcient Routing and Comprehensive Information Retrieval in Wireless Sensor Networks, in Proc. IEEE IPDPS 02, 195-202, 2002.

Murugunathan, SD.; Ma, DCF.; Bhasin, RI.; Fapajuwo, AO. (2005); A Centralized Energy-Effcient Routing Protocol for Wireless Sensor Networks, IEEE Radio Commun, 43(3), 8-13, 2005.

Schoeneich, RO.; Golanski, M. (2007); Mesh Cluster Based Routing Protocol: Enhancing Multi-hop Internet Access using Cluster paradigm, in Proc. EUROCON, 2007. The International Conference on Computer as a Tool, 962-965, 2007.

Spyropoulos, T.; Psounis, K.; Raghavendra, CS. (2005); Spray and wait: an efficient routing scheme for intermittently connected mobile networks, in Proc. of The 2005 ACM SIGCOMM workshop on Delay-tolerant networking, 252-259, 2005.

Soro, S.; Heinzelman, W. (2005); Prolonging the Lifetime of Wireless Sensor Networks via Unequal Clustering, in Proc. IEEE WMAN 05, 236-243, 2005.

Su, YY.; Hwang, SF.; Dow, CR. (2008); An Efficient Cluster-Based Routing Algorithm in Ad Hoc Networks with Unidirectional Links, Journal of Information Science And Engineering, 24(5), 1409-1428, 2008.

Vahdat, A.; Becker, D. (2000); Epidemic routing for partially connected ad hoc networks. Tech Report CS-2000-06, 2000.

Wei, C.; Yang, J.; Gao, Y.; Zhang, Z. (2011); Cluster-Based Routing Protocols in Wireless Sensor Networks: A Survey, inProc. IEEE ICCSNT 11, 1659-1663, 2011.

Yau, S.; Gao, W. (2007); Multi-hop clustering based on neighborhood benchmark in mobile ad-hoc networks, Mob. Netw. Appl, 12(5), 381-391, 2007.

Ye, M.; Li, C.; Chen, G.; Wu, J. (2005); EECS: An Energy Efficient Clustering Scheme in Wireless Sensor Networks, in Proc. IEEE IPCCC.05, 535-540, 2005.

Younis, O.; Fahmy, S. (2004); HEED: A hybrid, energy-efficient, distributed clustering approach for ad-hoc sensor networks, IEEE Trans. Mobile Comput., 3(4), 366-379, 2004.



Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.