Data mule scheduling on a path with handling time and time span constraints
- PDF / 285,943 Bytes
- 10 Pages / 439.37 x 666.142 pts Page_size
- 34 Downloads / 210 Views
Data mule scheduling on a path with handling time and time span constraints Zhihao Chen1 · Zhao Zhang1 · Yingli Ran1 · Yishuo Shi2 · Ding-Zhu Du3 Received: 5 April 2019 / Accepted: 9 August 2019 © Springer-Verlag GmbH Germany, part of Springer Nature 2019
Abstract In this paper, we study a data mule scheduling problem in which data mules are dispatched from a depot to serve targets located on a path. Every target sensor has a handling time, and every data mule is required to return to the depot before time span D. The goal is to minimize the number of data mules. For uniform handling time, a linear-time algorithm is presented. For non-uniform handling time, NP-hardness is proved and an approximation algorithm with a guaranteed approximation ratio is presented. Keywords Data mule scheduling · Handling time · Time span constraint · Computational complexity · Approximation algorithm
1 Introduction With the rapid expansion of mobile networks, data mule scheduling problems have attracted a lot of attentions. A data mule is a mobile device which moves around a field to help with network maintenance such as data collection and battery recharging/replacement. It is desirable to schedule trajectories of data mules in an optimal way to achieve a specific goal, such as minimizing the service cost. There are a lot
This research is supported by NSFC (11771013, 11531011, 61751303) and ZJNSFC (LD19A010001, LY19A010018).
B B
Zhao Zhang [email protected] Ding-Zhu Du [email protected]
1
College of Mathematics and Computer Sciences, Zhejiang Normal University, Jinhua 321004, Zhejiang, China
2
Institute of Information Science, Academia Sinica, Taibei 11529, Taiwan
3
Department of Computer Science, University of Texas at Dallas, Richardson, TX 75080, USA
123
Z. Chen et al.
of efforts studying data mule scheduling problems in the literature [2,3,9,10]. For example, Chang et al. [3] presented algorithms aiming to produce a scheduling for cooperative data mules to achieve a stable visiting frequency of targets, paying more visits to those targets with higher importance, and taking into considerations recharging issues. Sugihara and Gupta [10] studied the data mule scheduling problem with the aim of minimizing the time latency. Their focus is on the speed control in a 1dimensional (1D) setting. As they said in their paper, “Once we choose the path, any 2D/3D data mule scheduling problem can be converted to a 1D problem”. For more studies on data mules, interested readers may refer to the survey [4]. In this paper, we consider the data mule scheduling problem on a path in which every target has a handling time requirement and every data mule has to return to the depot within a predefined time span. The goal is to minimize the number of data mules under the condition that the required service can be accomplished. We call this problem as the data mule scheduling problem with time constraint (abbreviated as DMSTC). When the problem is restricted on a path, we denote it as DMSTC path . 1.1 Motivation and related work This model is m
Data Loading...
