## 3 Preliminaries and Problem Statement  
### Network Model and Problem Definition  
Consider a WSN model in which an object is planned to travel on a preselected path in a two-dimensional area. To monitor the object, \(m\) mobile sensors (e.g., drones) can be used. All the mobile sensors are located in an obstacle-free surveillance region. For convenience, assume that we can schedule mobile sensor nodes to \(n\) predetermined spots on the path for monitoring the object before it starts moving (Figure 1). All mobile sensors initially have an equal amount of battery power and are located at the same depot (base station). They also move at the same speed. Each mobile sensor route starts and finishes at the base station. Moreover, a mobile sensor can move to the predetermined position before the object arrives. To extend the network lifetime, we require a movement repertoire of mobile sensors such that the total traveled distance is minimized and as such that the remaining battery power of each sensor is as balanced as possible. We partition the object traveling path into several zones such that each mobile sensor must be placed in a zone once and only once to achieve a high balanced residual energy. From a graph-theoretic perspective, the moving object coverage problem can be stated as follows. Let \(G=(V,A)\) be a directed multistage graph where \(V=[0,\,\ldots,\,n]\) is the vertex set, and \(A\) is the arc set. The vertices \(i\) denote the positions to be reached and monitored, where \(1\leq i\leq n\), and vertex \(0\) denotes the base station. The vertices can be partitioned into \(h\geq 1\) disjoint sets \(V_{i}\) with \(i=0,\,\ldots,\,h\) and \(h=\frac{n}{m}\), where \(m>0\) is the number of mobile sensors. Without loss of generality, we assume that \(n\) is a multiple of \(m\). The sets of \(V_{i}\), \(0\leq i\leq h\), are such that \(\mid V_{0}\mid 1=1\) and \(\mid V_{1}\mid=\mid V_{2}\mid=\ldots=\mid V_{h}\mid=m\), where \(V_{0}=\{0\}\) and \(V_{i}=\{(i-1)\cdot m+1,\,\ldots,\,i\cdot m\}\), \(1\leq i\leq h\). A nonnegative cost \(d_{ij}\) is associated with each arc \(\langle i,j\rangle\in A\), representing the Euclidean distance from vertex \(i\) to vertex \(j\). We assume that loops on the same vertex, denoted by \(d_{ii}=\infty\), where \(i=1,\,2,\,\ldots,\,n\), are prohibited. A route is defined as one starting from the base station, going through exactly one vertex in each \(V_{i}\) (where \(1\leq i\leq h\)), and ending at the base station. Each vertex in \(V_{i}\) (where \(1\leq i\leq h\)) must be visited exactly once. Consider a set \(M=\{1,\,2,\,\ldots,\,m\}\) of identical mobile sensors initially positioned at the base station and are able to move in two dimensions at a constant and homogeneous speed, where \(0<m<n\). Each mobile sensor surve  
Figure 1: The movement trajectory of an object in the moving object coverage problem. on the route. The goal is to find a set of routes that can both guarantee that each vertex is served by one mobile sensor and satisfy the constraints of the mobile sensors' maximum allowable traveled distance. Furthermore, the size of the set should be smaller than the number of mobile sensors required, the total traveled distance should be minimized, and the traveled distance of the mobile sensors should be as balanced as possible. Let \(x_{ij}^{k}\) and \(y_{i}^{k}\) be binary variables defined as follows:  
\[x_{ij}^{k}=\left\{ \begin{array}{ccc}1&\quad\text{if mobile sensor $k$ travels along arc $\langle i,j\rangle$},\\ &0&\quad\text{otherwise}.\end{array} \right.\]  
\[y_{i}^{k}=\left\{ \begin{array}{ccc}1&\quad\text{if mobile sensor $k$ reaches the spot $i$,}\\ &0&\quad\text{otherwise}.\end{array}