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

Article Contents

2011, Volume 1, Issue 4: 563-576. Doi: 10.3934/naco.2011.1.563

This issue Previous Article Preface Next Article Asynchronous multiple source network coding for wireless broadcasting

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
2.
Department of Information and Communications Technology, Graduate School of Engineering, Osaka University, Suita, Osaka, 565-0871
3.
Department of Information and Communications Technology, Graduate School of Engineering, Osaka University, 2-1 Yamadaoka, Suita 565-0871

Received: May 2011

Revised: August 2011

Published: November 2011

Abstract / Introduction Related Papers Cited by

Abstract

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:

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

Citation:

Related Papers

Cited by

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.