American Institute of Mathematical Sciences

2011, 1(4): 563-576. doi: 10.3934/naco.2011.1.563

Optimal visiting order of isolated clusters in DTNs to minimize the total mean delivery delay of bundles

 1 Department of Information and Communications Technology, Graduate School of Engineering, Osaka University, Suita 565-0871, Japan 2 Department of Information and Communications Technology, Graduate School of Engineering, Osaka University, Suita, Osaka, 565-0871, Japan 3 Department of Information and Communications Technology, Graduate School of Engineering, Osaka University, 2-1 Yamadaoka, Suita 565-0871, Japan

Received  May 2011 Revised  August 2011 Published  November 2011

In delay tolerant networks (DTNs), the opportunity of communication among isolated networks (clusters) can be provided by a message ferry which moves around the network to proactively collect bundles and deliver them to a sink node. When there are lots of distant static clusters, the message ferry should visit them efficiently to minimize the mean delivery delay of bundles. In this paper, we propose an algorithm for determining the optimal visiting order of isolated static clusters in DTNs. We show that the minimization problem of the overall mean delivery delay in our system is reduced to that of the weighted mean waiting time in the conventional polling model. We then solve the problem with the help of an existing approach to the polling model and obtain a quasi-optimal balanced sequence representing the visiting order. Through numerical examples, we show that the proposed visiting order is effective when arrival rates at clusters and/or distances between clusters and the sink are heterogeneous.
Citation: K. Habibul Kabir, Masahiro Sasabe, Tetsuya Takine. Optimal visiting order of isolated clusters in DTNs to minimize the total mean delivery delay of bundles. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 563-576. doi: 10.3934/naco.2011.1.563
References:
 [1] E. Altman, B. Gaujal and A. Hordijk, Balanced sequences and optimal routing,, Journal of ACM, 47 (2000), 752. doi: 10.1145/347476.347482. Google Scholar [2] M. Ammar, D. Chakrabarty, A. Sarma, S. Kalyanasundaram and R. Lipton, Algorithms for message ferrying on mobile ad hoc networks,, Proc. IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), (2009), 13. Google Scholar [3] D. J. Bertsimas and H. Xu, Optimization of polling systems and dynamic vehicle routing problems on networks,, Technical Report, (1993), 283. Google Scholar [4] S. C. Borst, O. J. Boxma, J. H. A. Harink and G. B. Huitema, Optimization of fixed time polling schemes,, Telecommunication Systems, 3 (1994), 31. doi: 10.1007/BF02110043. Google Scholar [5] O. J. Boxma, W. P. Groenendijk and J. A. Weststrate, A pseudoconservation law for service systems with a polling table,, IEEE Transactions on Communications, 38 (1990), 1865. doi: 10.1109/26.61458. Google Scholar [6] O. J. Boxma, H. Levy and J. A. Westrate, Efficient visit orders for polling systems,, Performance Evaluation, 18 (1993), 103. doi: 10.1016/0166-5316(93)90031-O. Google Scholar [7] V. Cerf, S. Burleigh, A. Hooke, L. Torgerson, R. Durst, K. Scott, K. Fall and H. Weiss, Delay tolerant network architecture,, work in progress as an IETF RFC 4838 draft. Available from: \url{http://www.ietf.org/rfc/rfc4838.txt}., (4838). Google Scholar [8] R. W. Conway, W. L. Maxwell and L. W. Miller, "Theory of Scheduling,'', Addison Wesley, (1967). Google Scholar [9] K. Fall, A delay-tolerant network architecture for challenged internets,, Proc. ACM SIGCOMM, (2003), 27. Google Scholar [10] K. Fall and W. Hong, Custody transfer for reliable delivery in delay tolerant networks,, Technical Report, (2003), 03. Google Scholar [11] M. J. Ferguson and Y. J. Aminetzah, Exact results for nonsymmetric token ring systems,, IEEE Transactions on Communications, COM-33 (1985), 223. doi: 10.1109/TCOM.1985.1096285. Google Scholar [12] K. H. Kabir, M. Sasabe and T. Takine, Design and analysis of self-organized data aggregation using evolutionary game theory in delay tolerant networks,, Proc. 3rd IEEE WoWMoM Workshop on Autonomic and Opportunistic Communications, (2009). Google Scholar [13] K. H. Kabir, M. Sasabe and T. Takine, Evolutionary game theoretic approach to self-organized data aggregation in delay tolerant networks,, IEICE Transactions on Communications, E93-B (2010), 490. Google Scholar [14] K. H. Kabir, M. Sasabe and T. Takine, Self-organized data aggregation among selfish nodes in an isolated cluster,, Proc. 5th International ICST Conference on Bio-Inspired Models of Network, (2010). Google Scholar [15] V. Kavitha and E. Altman, Queuing in space: Design of message ferry routes in static ad hoc networks,, Proc. 21st International Teletraffic Congress, (2009), 1. Google Scholar [16] V. Kavitha and E. Altman, Analysis and design of message ferry routes in sensor networks using polling models,, Proc. 8th International Symposium on Modeling and Optimization in Mobile, (2010), 247. Google Scholar [17] V. Kavitha and E. Altman, Opportunistic scheduling of a message ferry in sensor networks,, Proc. 2nd International Workshop on Mobile Opportunistic Networking, (2010), 163. doi: 10.1145/1755743.1755774. Google Scholar [18] E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan and D. B. Shmoys, "Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization,'', John Wiley Sons, (1985). Google Scholar [19] H. Levy and M. Sidi, Polling systems: Applications, modeling, and optimization,, IEEE Transactions on communications, 38 (1990), 1750. doi: 10.1109/26.61446. Google Scholar [20] H. Miura, D. Nishi, N. Matsuda and H. Taki, Message ferry route design based on clustering for sparse ad hoc networks,, Proc. 14th international conference on Knowledge-based and intelligent information and engineering systems, (2010), 637. doi: 10.1007/978-3-642-15390-7_66. Google Scholar [21] S. Sano, N. Miyoshi and R. Kataoka, $m$-balanced words: A generalization of balanced words,, Theoretical Computer Science, 314 (2004), 97. doi: 10.1016/j.tcs.2003.11.021. Google Scholar [22] H. Takagi, Queuing analysis of polling models,, ACM Computing Surveys, 20 (1988), 5. doi: 10.1145/62058.62059. Google Scholar [23] H. Takagi, Queueing analysis of polling models: An update,, in, (1990). Google Scholar [24] W. Zhao and M. Ammar, Message ferrying: proactive routing in highly-partitioned wireless ad hoc networks,, Proc. IEEE Future Trends of Distributed Computing Systems, (2003), 308. Google Scholar [25] W. Zhao, M. Ammar and E. Zegura, A message ferrying approach for data delivery in sparse mobile ad hoc networks,, Proc. ACM MobiHoc, (2004), 187. doi: 10.1145/989459.989483. Google Scholar [26] W. Zhao, M. Ammar and E. Zegura, Controlling the mobility of multiple data transport ferries in a delay-tolerant network,, Proc. IEEE INFOCOM, (2005), 1407. Google Scholar

show all references

References:
 [1] E. Altman, B. Gaujal and A. Hordijk, Balanced sequences and optimal routing,, Journal of ACM, 47 (2000), 752. doi: 10.1145/347476.347482. Google Scholar [2] M. Ammar, D. Chakrabarty, A. Sarma, S. Kalyanasundaram and R. Lipton, Algorithms for message ferrying on mobile ad hoc networks,, Proc. IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), (2009), 13. Google Scholar [3] D. J. Bertsimas and H. Xu, Optimization of polling systems and dynamic vehicle routing problems on networks,, Technical Report, (1993), 283. Google Scholar [4] S. C. Borst, O. J. Boxma, J. H. A. Harink and G. B. Huitema, Optimization of fixed time polling schemes,, Telecommunication Systems, 3 (1994), 31. doi: 10.1007/BF02110043. Google Scholar [5] O. J. Boxma, W. P. Groenendijk and J. A. Weststrate, A pseudoconservation law for service systems with a polling table,, IEEE Transactions on Communications, 38 (1990), 1865. doi: 10.1109/26.61458. Google Scholar [6] O. J. Boxma, H. Levy and J. A. Westrate, Efficient visit orders for polling systems,, Performance Evaluation, 18 (1993), 103. doi: 10.1016/0166-5316(93)90031-O. Google Scholar [7] V. Cerf, S. Burleigh, A. Hooke, L. Torgerson, R. Durst, K. Scott, K. Fall and H. Weiss, Delay tolerant network architecture,, work in progress as an IETF RFC 4838 draft. Available from: \url{http://www.ietf.org/rfc/rfc4838.txt}., (4838). Google Scholar [8] R. W. Conway, W. L. Maxwell and L. W. Miller, "Theory of Scheduling,'', Addison Wesley, (1967). Google Scholar [9] K. Fall, A delay-tolerant network architecture for challenged internets,, Proc. ACM SIGCOMM, (2003), 27. Google Scholar [10] K. Fall and W. Hong, Custody transfer for reliable delivery in delay tolerant networks,, Technical Report, (2003), 03. Google Scholar [11] M. J. Ferguson and Y. J. Aminetzah, Exact results for nonsymmetric token ring systems,, IEEE Transactions on Communications, COM-33 (1985), 223. doi: 10.1109/TCOM.1985.1096285. Google Scholar [12] K. H. Kabir, M. Sasabe and T. Takine, Design and analysis of self-organized data aggregation using evolutionary game theory in delay tolerant networks,, Proc. 3rd IEEE WoWMoM Workshop on Autonomic and Opportunistic Communications, (2009). Google Scholar [13] K. H. Kabir, M. Sasabe and T. Takine, Evolutionary game theoretic approach to self-organized data aggregation in delay tolerant networks,, IEICE Transactions on Communications, E93-B (2010), 490. Google Scholar [14] K. H. Kabir, M. Sasabe and T. Takine, Self-organized data aggregation among selfish nodes in an isolated cluster,, Proc. 5th International ICST Conference on Bio-Inspired Models of Network, (2010). Google Scholar [15] V. Kavitha and E. Altman, Queuing in space: Design of message ferry routes in static ad hoc networks,, Proc. 21st International Teletraffic Congress, (2009), 1. Google Scholar [16] V. Kavitha and E. Altman, Analysis and design of message ferry routes in sensor networks using polling models,, Proc. 8th International Symposium on Modeling and Optimization in Mobile, (2010), 247. Google Scholar [17] V. Kavitha and E. Altman, Opportunistic scheduling of a message ferry in sensor networks,, Proc. 2nd International Workshop on Mobile Opportunistic Networking, (2010), 163. doi: 10.1145/1755743.1755774. Google Scholar [18] E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan and D. B. Shmoys, "Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization,'', John Wiley Sons, (1985). Google Scholar [19] H. Levy and M. Sidi, Polling systems: Applications, modeling, and optimization,, IEEE Transactions on communications, 38 (1990), 1750. doi: 10.1109/26.61446. Google Scholar [20] H. Miura, D. Nishi, N. Matsuda and H. Taki, Message ferry route design based on clustering for sparse ad hoc networks,, Proc. 14th international conference on Knowledge-based and intelligent information and engineering systems, (2010), 637. doi: 10.1007/978-3-642-15390-7_66. Google Scholar [21] S. Sano, N. Miyoshi and R. Kataoka, $m$-balanced words: A generalization of balanced words,, Theoretical Computer Science, 314 (2004), 97. doi: 10.1016/j.tcs.2003.11.021. Google Scholar [22] H. Takagi, Queuing analysis of polling models,, ACM Computing Surveys, 20 (1988), 5. doi: 10.1145/62058.62059. Google Scholar [23] H. Takagi, Queueing analysis of polling models: An update,, in, (1990). Google Scholar [24] W. Zhao and M. Ammar, Message ferrying: proactive routing in highly-partitioned wireless ad hoc networks,, Proc. IEEE Future Trends of Distributed Computing Systems, (2003), 308. Google Scholar [25] W. Zhao, M. Ammar and E. Zegura, A message ferrying approach for data delivery in sparse mobile ad hoc networks,, Proc. ACM MobiHoc, (2004), 187. doi: 10.1145/989459.989483. Google Scholar [26] W. Zhao, M. Ammar and E. Zegura, Controlling the mobility of multiple data transport ferries in a delay-tolerant network,, Proc. IEEE INFOCOM, (2005), 1407. Google Scholar
 [1] Fabian Rüffler, Volker Mehrmann, Falk M. Hante. Optimal model switching for gas flow in pipe networks. Networks & Heterogeneous Media, 2018, 13 (4) : 641-661. doi: 10.3934/nhm.2018029 [2] Sebastián Ferrer, Francisco Crespo. Parametric quartic Hamiltonian model. A unified treatment of classic integrable systems. Journal of Geometric Mechanics, 2014, 6 (4) : 479-502. doi: 10.3934/jgm.2014.6.479 [3] Ghendrih Philippe, Hauray Maxime, Anne Nouri. Derivation of a gyrokinetic model. Existence and uniqueness of specific stationary solution. Kinetic & Related Models, 2009, 2 (4) : 707-725. doi: 10.3934/krm.2009.2.707 [4] Meng Liu, Chuanzhi Bai. Optimal harvesting of a stochastic delay competitive model. Discrete & Continuous Dynamical Systems - B, 2017, 22 (4) : 1493-1508. doi: 10.3934/dcdsb.2017071 [5] Shunfu Jin, Wuyi Yue, Zsolt Saffer. Analysis and optimization of a gated polling based spectrum allocation mechanism in cognitive radio networks. Journal of Industrial & Management Optimization, 2016, 12 (2) : 687-702. doi: 10.3934/jimo.2016.12.687 [6] Elimhan N. Mahmudov. Optimal control of second order delay-discrete and delay-differential inclusions with state constraints. Evolution Equations & Control Theory, 2018, 7 (3) : 501-529. doi: 10.3934/eect.2018024 [7] Bertrand Haut, Georges Bastin. A second order model of road junctions in fluid models of traffic networks. Networks & Heterogeneous Media, 2007, 2 (2) : 227-253. doi: 10.3934/nhm.2007.2.227 [8] Faker Ben Belgacem. Uniqueness for an ill-posed reaction-dispersion model. Application to organic pollution in stream-waters. Inverse Problems & Imaging, 2012, 6 (2) : 163-181. doi: 10.3934/ipi.2012.6.163 [9] Zsolt Saffer, Miklós Telek. Analysis of globally gated Markovian limited cyclic polling model and its application to uplink traffic in the IEEE 802.16 network. Journal of Industrial & Management Optimization, 2011, 7 (3) : 677-697. doi: 10.3934/jimo.2011.7.677 [10] Jin Ma, Xinyang Wang, Jianfeng Zhang. Dynamic equilibrium limit order book model and optimal execution problem. Mathematical Control & Related Fields, 2015, 5 (3) : 557-583. doi: 10.3934/mcrf.2015.5.557 [11] Chui-Yu Chiu, Ming-Feng Yang, Chung-Jung Tang, Yi Lin. Integrated imperfect production inventory model under permissible delay in payments depending on the order quantity. Journal of Industrial & Management Optimization, 2013, 9 (4) : 945-965. doi: 10.3934/jimo.2013.9.945 [12] Amir Adibzadeh, Mohsen Zamani, Amir A. Suratgar, Mohammad B. Menhaj. Constrained optimal consensus in dynamical networks. Numerical Algebra, Control & Optimization, 2019, 9 (3) : 349-360. doi: 10.3934/naco.2019023 [13] Giovanni Alberti, Giuseppe Buttazzo, Serena Guarino Lo Bianco, Édouard Oudet. Optimal reinforcing networks for elastic membranes. Networks & Heterogeneous Media, 2019, 14 (3) : 589-615. doi: 10.3934/nhm.2019023 [14] Benedetta Lisena. Average criteria for periodic neural networks with delay. Discrete & Continuous Dynamical Systems - B, 2014, 19 (3) : 761-773. doi: 10.3934/dcdsb.2014.19.761 [15] Chol-Ung Choe, Thomas Dahms, Philipp Hövel, Eckehard Schöll. Control of synchrony by delay coupling in complex networks. Conference Publications, 2011, 2011 (Special) : 292-301. doi: 10.3934/proc.2011.2011.292 [16] Samitha Samaranayake, Axel Parmentier, Ethan Xuan, Alexandre Bayen. A mathematical framework for delay analysis in single source networks. Networks & Heterogeneous Media, 2017, 12 (1) : 113-145. doi: 10.3934/nhm.2017005 [17] Alessia Marigo, Benedetto Piccoli. A model for biological dynamic networks. Networks & Heterogeneous Media, 2011, 6 (4) : 647-663. doi: 10.3934/nhm.2011.6.647 [18] Agnieszka B. Malinowska, Tatiana Odzijewicz. Optimal control of the discrete-time fractional-order Cucker-Smale model. Discrete & Continuous Dynamical Systems - B, 2018, 23 (1) : 347-357. doi: 10.3934/dcdsb.2018023 [19] M. M. Ali, L. Masinga. A nonlinear optimization model for optimal order quantities with stochastic demand rate and price change. Journal of Industrial & Management Optimization, 2007, 3 (1) : 139-154. doi: 10.3934/jimo.2007.3.139 [20] Zhenwei Luo, Jinting Wang. The optimal price discount, order quantity and minimum quantity in newsvendor model with group purchase. Journal of Industrial & Management Optimization, 2015, 11 (1) : 1-11. doi: 10.3934/jimo.2015.11.1

Impact Factor: