Optimal visiting order of isolated clusters in DTNs
to minimize the total mean delivery delay of bundles
K. Habibul Kabir - Department of Information and Communications Technology, Graduate School of Engineering, Osaka University, 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.
Received: May 2011; Revised: August 2011; Published: November 2011.