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

K. Habibul Kabir; Masahiro Sasabe; Tetsuya Takine

doi:10.3934/naco.2011.1.563

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 & 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. 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-24. Google Scholar
[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). 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-59. 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-1870. 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-123. 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: http://www.ietf.org/rfc/rfc4838.txt. Google Scholar
[8]	R. W. Conway, W. L. Maxwell and L. W. Miller, "Theory of Scheduling,'' Addison Wesley, Reading, MA, 1967. Google Scholar
[9]	K. Fall, A delay-tolerant network architecture for challenged internets, Proc. ACM SIGCOMM, (2003), 27-34. Google Scholar
[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). 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-231. 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-500. 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, Information and Computing Systems, (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-8. 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, Ad Hoc and Wireless Networks (WiOpt), (2010), 247-255. 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-166. 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-1760. 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-644. 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-120. doi: 10.1016/j.tcs.2003.11.021. Google Scholar
[22]	H. Takagi, Queuing analysis of polling models, ACM Computing Surveys, 20 (1988), 5-28. doi: 10.1145/62058.62059. Google Scholar
[23]	H. Takagi, Queueing analysis of polling models: An update, in "Stochastic Analysis of Computer and Communication Systems,'' North-Holland, Amsterdam, 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-314. 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-198. 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-1418. 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-775. 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-24. Google Scholar
[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). 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-59. 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-1870. 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-123. 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: http://www.ietf.org/rfc/rfc4838.txt. Google Scholar
[8]	R. W. Conway, W. L. Maxwell and L. W. Miller, "Theory of Scheduling,'' Addison Wesley, Reading, MA, 1967. Google Scholar
[9]	K. Fall, A delay-tolerant network architecture for challenged internets, Proc. ACM SIGCOMM, (2003), 27-34. Google Scholar
[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). 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-231. 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-500. 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, Information and Computing Systems, (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-8. 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, Ad Hoc and Wireless Networks (WiOpt), (2010), 247-255. 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-166. 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-1760. 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-644. 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-120. doi: 10.1016/j.tcs.2003.11.021. Google Scholar
[22]	H. Takagi, Queuing analysis of polling models, ACM Computing Surveys, 20 (1988), 5-28. doi: 10.1145/62058.62059. Google Scholar
[23]	H. Takagi, Queueing analysis of polling models: An update, in "Stochastic Analysis of Computer and Communication Systems,'' North-Holland, Amsterdam, 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-314. 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-198. 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-1418. Google Scholar

[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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & Continuous Dynamical Systems - S, 2021 doi: 10.3934/dcdss.2021085
[14]	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
[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 & 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 & 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 & Heterogeneous Media, 2019, 14 (3) : 589-615. doi: 10.3934/nhm.2019023
[18]	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
[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 & Heterogeneous Media, 2017, 12 (1) : 113-145. doi: 10.3934/nhm.2017005

Impact Factor:

American Institute of Mathematical Sciences

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

References:

References:

Tools

Metrics

Other articles
by authors

Tools

Metrics

Other articles
by authors

American Institute of Mathematical Sciences

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

References:

References:

Tools

Metrics

Other articlesby authors

Tools

Metrics

Other articlesby authors

Other articles
by authors

Other articles
by authors