`a`
Numerical Algebra, Control and Optimization (NACO)
 

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

Pages: 563 - 576, Volume 1, Issue 4, December 2011

doi:10.3934/naco.2011.1.563       Abstract        References        Full Text (247.9K)       Related Articles

K. Habibul Kabir - Department of Information and Communications Technology, Graduate School of Engineering, Osaka University, Suita 565-0871, Japan (email)
Masahiro Sasabe - Department of Information and Communications Technology, Graduate School of Engineering, Osaka University, Suita, Osaka, 565-0871, Japan (email)
Tetsuya Takine - Department of Information and Communications Technology, Graduate School of Engineering, Osaka University, 2-1 Yamadaoka, Suita 565-0871, Japan (email)

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:  Delay tolerant networks~(DTNs), message ferry, optimal visiting order, polling model.
Mathematics Subject Classification:  Primary: 90B18; Secondary: 68M20.

Received: May 2011;      Revised: August 2011;      Published: November 2011.

 References