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]

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

[2]

Soniya Singh, Sumit Arora, Manil T. Mohan, Jaydev Dabas. Approximate controllability of second order impulsive systems with state-dependent delay in Banach spaces. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020103

[3]

Youming Guo, Tingting Li. Optimal control strategies for an online game addiction model with low and high risk exposure. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020347

[4]

Bernard Bonnard, Jérémy Rouot. Geometric optimal techniques to control the muscular force response to functional electrical stimulation using a non-isometric force-fatigue model. Journal of Geometric Mechanics, 2020  doi: 10.3934/jgm.2020032

[5]

José Madrid, João P. G. Ramos. On optimal autocorrelation inequalities on the real line. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020271

[6]

Giuseppina Guatteri, Federica Masiero. Stochastic maximum principle for problems with delay with dependence on the past through general measures. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020048

[7]

Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019

[8]

Tommi Brander, Joonas Ilmavirta, Petteri Piiroinen, Teemu Tyni. Optimal recovery of a radiating source with multiple frequencies along one line. Inverse Problems & Imaging, 2020, 14 (6) : 967-983. doi: 10.3934/ipi.2020044

[9]

Lars Grüne, Matthias A. Müller, Christopher M. Kellett, Steven R. Weller. Strict dissipativity for discrete time discounted optimal control problems. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020046

[10]

Xin-Guang Yang, Lu Li, Xingjie Yan, Ling Ding. The structure and stability of pullback attractors for 3D Brinkman-Forchheimer equation with delay. Electronic Research Archive, 2020, 28 (4) : 1395-1418. doi: 10.3934/era.2020074

[11]

Jianquan Li, Xin Xie, Dian Zhang, Jia Li, Xiaolin Lin. Qualitative analysis of a simple tumor-immune system with time delay of tumor action. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020341

[12]

Fathalla A. Rihan, Hebatallah J. Alsakaji. Stochastic delay differential equations of three-species prey-predator system with cooperation among prey species. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020468

[13]

Manil T. Mohan. First order necessary conditions of optimality for the two dimensional tidal dynamics system. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020045

[14]

Weisong Dong, Chang Li. Second order estimates for complex Hessian equations on Hermitian manifolds. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020377

[15]

Laurence Cherfils, Stefania Gatti, Alain Miranville, Rémy Guillevin. Analysis of a model for tumor growth and lactate exchanges in a glioma. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020457

[16]

Laurent Di Menza, Virginie Joanne-Fabre. An age group model for the study of a population of trees. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020464

[17]

Yongge Tian, Pengyang Xie. Simultaneous optimal predictions under two seemingly unrelated linear random-effects models. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020168

[18]

Kihoon Seong. Low regularity a priori estimates for the fourth order cubic nonlinear Schrödinger equation. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5437-5473. doi: 10.3934/cpaa.2020247

[19]

Shasha Hu, Yihong Xu, Yuhan Zhang. Second-Order characterizations for set-valued equilibrium problems with variable ordering structures. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020164

[20]

Youshan Tao, Michael Winkler. Critical mass for infinite-time blow-up in a haptotaxis system with nonlinear zero-order interaction. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 439-454. doi: 10.3934/dcds.2020216

 Impact Factor: 

Metrics

  • PDF downloads (43)
  • HTML views (0)
  • Cited by (1)

[Back to Top]