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

Previous Article
Asynchronous multiple source network coding for wireless broadcasting
NACO Home
This Issue
Next Article
Preface

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

K. Habibul Kabir ^1, , Masahiro Sasabe ^2, and Tetsuya Takine ^3,

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

Abstract
Related Papers

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.

Keywords: polling model., Delay tolerant networks~(DTNs), optimal visiting order, message ferry.

Mathematics Subject Classification: Primary: 90B18; Secondary: 68M2.

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 and 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-775. doi: 10.1145/347476.347482.
[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-24.
[3]	D. J. Bertsimas and H. Xu, Optimization of polling systems and dynamic vehicle routing problems on networks, Technical Report, OR 283-93, MIT, (1993).
[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-59. doi: 10.1007/BF02110043.
[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-1870. doi: 10.1109/26.61458.
[6]	O. J. Boxma, H. Levy and J. A. Westrate, Efficient visit orders for polling systems, Performance Evaluation, 18 (1993), 103-123. doi: 10.1016/0166-5316(93)90031-O.
[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: http://www.ietf.org/rfc/rfc4838.txt.
[8]	R. W. Conway, W. L. Maxwell and L. W. Miller, "Theory of Scheduling,'' Addison Wesley, Reading, MA, 1967.
[9]	K. Fall, A delay-tolerant network architecture for challenged internets, Proc. ACM SIGCOMM, (2003), 27-34.
[10]	K. Fall and W. Hong, Custody transfer for reliable delivery in delay tolerant networks, Technical Report, IRB-TR-03-030, Intel Research Berkeley,(2003).
[11]	M. J. Ferguson and Y. J. Aminetzah, Exact results for nonsymmetric token ring systems, IEEE Transactions on Communications, COM-33 (1985), 223-231. doi: 10.1109/TCOM.1985.1096285.
[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).
[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-500.
[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, Information and Computing Systems, (2010).
[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-8.
[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, Ad Hoc and Wireless Networks (WiOpt), (2010), 247-255.
[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-166. doi: 10.1145/1755743.1755774.
[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.
[19]	H. Levy and M. Sidi, Polling systems: Applications, modeling, and optimization, IEEE Transactions on communications, 38 (1990), 1750-1760. doi: 10.1109/26.61446.
[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-644. doi: 10.1007/978-3-642-15390-7_66.
[21]	S. Sano, N. Miyoshi and R. Kataoka, $m$-balanced words: A generalization of balanced words, Theoretical Computer Science, 314 (2004), 97-120. doi: 10.1016/j.tcs.2003.11.021.
[22]	H. Takagi, Queuing analysis of polling models, ACM Computing Surveys, 20 (1988), 5-28. doi: 10.1145/62058.62059.
[23]	H. Takagi, Queueing analysis of polling models: An update, in "Stochastic Analysis of Computer and Communication Systems,'' North-Holland, Amsterdam, 1990.
[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-314.
[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-198. doi: 10.1145/989459.989483.
[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-1418.

show all references

References:

[1]	E. Altman, B. Gaujal and A. Hordijk, Balanced sequences and optimal routing, Journal of ACM, 47 (2000), 752-775. doi: 10.1145/347476.347482.
[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-24.
[3]	D. J. Bertsimas and H. Xu, Optimization of polling systems and dynamic vehicle routing problems on networks, Technical Report, OR 283-93, MIT, (1993).
[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-59. doi: 10.1007/BF02110043.
[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-1870. doi: 10.1109/26.61458.
[6]	O. J. Boxma, H. Levy and J. A. Westrate, Efficient visit orders for polling systems, Performance Evaluation, 18 (1993), 103-123. doi: 10.1016/0166-5316(93)90031-O.
[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: http://www.ietf.org/rfc/rfc4838.txt.
[8]	R. W. Conway, W. L. Maxwell and L. W. Miller, "Theory of Scheduling,'' Addison Wesley, Reading, MA, 1967.
[9]	K. Fall, A delay-tolerant network architecture for challenged internets, Proc. ACM SIGCOMM, (2003), 27-34.
[10]	K. Fall and W. Hong, Custody transfer for reliable delivery in delay tolerant networks, Technical Report, IRB-TR-03-030, Intel Research Berkeley,(2003).
[11]	M. J. Ferguson and Y. J. Aminetzah, Exact results for nonsymmetric token ring systems, IEEE Transactions on Communications, COM-33 (1985), 223-231. doi: 10.1109/TCOM.1985.1096285.
[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).
[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-500.
[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, Information and Computing Systems, (2010).
[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-8.
[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, Ad Hoc and Wireless Networks (WiOpt), (2010), 247-255.
[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-166. doi: 10.1145/1755743.1755774.
[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.
[19]	H. Levy and M. Sidi, Polling systems: Applications, modeling, and optimization, IEEE Transactions on communications, 38 (1990), 1750-1760. doi: 10.1109/26.61446.
[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-644. doi: 10.1007/978-3-642-15390-7_66.
[21]	S. Sano, N. Miyoshi and R. Kataoka, $m$-balanced words: A generalization of balanced words, Theoretical Computer Science, 314 (2004), 97-120. doi: 10.1016/j.tcs.2003.11.021.
[22]	H. Takagi, Queuing analysis of polling models, ACM Computing Surveys, 20 (1988), 5-28. doi: 10.1145/62058.62059.
[23]	H. Takagi, Queueing analysis of polling models: An update, in "Stochastic Analysis of Computer and Communication Systems,'' North-Holland, Amsterdam, 1990.
[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-314.
[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-198. doi: 10.1145/989459.989483.
[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-1418.

[1]	Jianping Zhou, Yamin Liu, Ju H. Park, Qingkai Kong, Zhen Wang. Fault-tolerant anti-synchronization control for chaotic switched neural networks with time delay and reaction diffusion. Discrete and Continuous Dynamical Systems - S, 2021, 14 (4) : 1569-1589. doi: 10.3934/dcdss.2020357
[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 and Related Models, 2009, 2 (4) : 707-725. doi: 10.3934/krm.2009.2.707
[4]	Fabian Rüffler, Volker Mehrmann, Falk M. Hante. Optimal model switching for gas flow in pipe networks. Networks and Heterogeneous Media, 2018, 13 (4) : 641-661. doi: 10.3934/nhm.2018029
[5]	Nasser Sweilam, Fathalla Rihan, Seham AL-Mekhlafi. A fractional-order delay differential model with optimal control for cancer treatment based on synergy between anti-angiogenic and immune cell therapies. Discrete and Continuous Dynamical Systems - S, 2020, 13 (9) : 2403-2424. doi: 10.3934/dcdss.2020120
[6]	Meng Liu, Chuanzhi Bai. Optimal harvesting of a stochastic delay competitive model. Discrete and Continuous Dynamical Systems - B, 2017, 22 (4) : 1493-1508. doi: 10.3934/dcdsb.2017071
[7]	Shunfu Jin, Wuyi Yue, Zsolt Saffer. Analysis and optimization of a gated polling based spectrum allocation mechanism in cognitive radio networks. Journal of Industrial and Management Optimization, 2016, 12 (2) : 687-702. doi: 10.3934/jimo.2016.12.687
[8]	Bertrand Haut, Georges Bastin. A second order model of road junctions in fluid models of traffic networks. Networks and Heterogeneous Media, 2007, 2 (2) : 227-253. doi: 10.3934/nhm.2007.2.227
[9]	Elimhan N. Mahmudov. Optimal control of second order delay-discrete and delay-differential inclusions with state constraints. Evolution Equations and Control Theory, 2018, 7 (3) : 501-529. doi: 10.3934/eect.2018024
[10]	Faker Ben Belgacem. Uniqueness for an ill-posed reaction-dispersion model. Application to organic pollution in stream-waters. Inverse Problems and Imaging, 2012, 6 (2) : 163-181. doi: 10.3934/ipi.2012.6.163
[11]	Xuefeng Zhang, Yingbo Zhang. Fault-tolerant control against actuator failures for uncertain singular fractional order systems. Numerical Algebra, Control and Optimization, 2021, 11 (1) : 1-12. doi: 10.3934/naco.2020011
[12]	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 and Management Optimization, 2011, 7 (3) : 677-697. doi: 10.3934/jimo.2011.7.677
[13]	Nasser H. Sweilam, Taghreed A. Assiri, Muner M. Abou Hasan. Optimal control problem of variable-order delay system of advertising procedure: Numerical treatment. Discrete and Continuous Dynamical Systems - S, 2022, 15 (5) : 1247-1268. doi: 10.3934/dcdss.2021085
[14]	Jin Ma, Xinyang Wang, Jianfeng Zhang. Dynamic equilibrium limit order book model and optimal execution problem. Mathematical Control and Related Fields, 2015, 5 (3) : 557-583. doi: 10.3934/mcrf.2015.5.557
[15]	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 and Management Optimization, 2013, 9 (4) : 945-965. doi: 10.3934/jimo.2013.9.945
[16]	Amir Adibzadeh, Mohsen Zamani, Amir A. Suratgar, Mohammad B. Menhaj. Constrained optimal consensus in dynamical networks. Numerical Algebra, Control and Optimization, 2019, 9 (3) : 349-360. doi: 10.3934/naco.2019023
[17]	Giovanni Alberti, Giuseppe Buttazzo, Serena Guarino Lo Bianco, Édouard Oudet. Optimal reinforcing networks for elastic membranes. Networks and Heterogeneous Media, 2019, 14 (3) : 589-615. doi: 10.3934/nhm.2019023
[18]	Benedetta Lisena. Average criteria for periodic neural networks with delay. Discrete and Continuous Dynamical Systems - B, 2014, 19 (3) : 761-773. doi: 10.3934/dcdsb.2014.19.761
[19]	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
[20]	Samitha Samaranayake, Axel Parmentier, Ethan Xuan, Alexandre Bayen. A mathematical framework for delay analysis in single source networks. Networks and Heterogeneous Media, 2017, 12 (1) : 113-145. doi: 10.3934/nhm.2017005

Impact Factor:

Tools

Metrics

Other articles
by authors

on AIMS
K. Habibul Kabir Masahiro Sasabe Tetsuya Takine
on Google Scholar
K. Habibul Kabir Masahiro Sasabe Tetsuya Takine

[Back to Top]