## 4 Optimizing Path Schedule of the Mobile Sink
### The Ideal Case
Mark
2: For current point \(q\), find a point \(r\) with the largest hop number and shortest path length among all \(q\)'s neighbor, and set \(s_{q}=s_{r}+1\), \(l_{q}=l_{r}+d_{qr}\). If there is no neighbor, set \(s_{q}=1\), \(l_{q}=0\). 3: If \(q\) is the leftmost point, GOTO step Finish. Otherwise, set the first point to the left of the current point \(q\) (i.e., \(q=q-1\)) as the current point, GOTO step Mark. Finish
4: Start from the point(s) with the largest hop number and smallest path length, add it into \(P\), and recursively add its neighbor with the hop number decreasing by one. When there is more than one point having the same largest hop number, the algorithm records all the paths. ```  
**Algorithm 2** Optimal shortest path finding algorithm in the precedence graph  
However, in many cases, it is impossible to find a trajectory of the mobile sink to visit every UGV upon their appearance--e.g., when the interval of two UGVs reappearing is less than the traveling time between them, there is no doubt that one mobile sink cannot reach them both. In this case, the objective is to visit as many UGVs as possible so that more data can be collected in time. To find a path that visits the most number of UGVs, the easiest way is to exhaust all possibilities. The time complexity, which is \(O(n\times 2^{n})\), increases quickly as the number of UGVs increases. In this paper, we propose a simple algorithm (Algorithm 2) that achieves the same goal, taking advantage of the precedence graph. **Definition 4**. : _The term **hop number** of point \(q\) stands for the optimal number of points that can be visited until the rightmost point when starting from \(q\)._  
**Definition 5**. : _The term **path length** of point \(q\) (denoted as \(l_{q}\)) stands for the sum of all edges from \(q\) to the rightmost point with hop number of \(1\)._  
The algorithm starts from the farthest right point on the time scale, and then scans and marks from the right to the left one by one. At each point, it tries to connect to the neighbor with the longest path. Scanning along the time scale ensures that no point is ignored and is in accordance with the precedence requirement. The time complexity is \(O(l\times n)\to O(n)\), in which \(n\) is the total number of points in the precedence graph, and \(l\) is the number of UGVs (\(l\ll n\)). There may exist more than one optimal path. In the TSP problem, it is NP-Complete to find the shortest path. However, since there are time window and precedence constraints, and a point will not have more than \(l\) edges, the combination in our case is very limited. In the Mark phase of the algorithm 2, it is easy to choose the neighbor of the shortest path by recording the neighbor with the shortest path. **Theorem 3**. : _Algorithm 2 can obtain the optimal path that contains the largest number of points (UGVs)._  
Proof. : We use mathematical induction. Supposing that there is only one point, the algorithm obviously works. Then, suppose that the algorithm finds the optimal path(s) starting from a set of points \(Q\) when there are \(n\) points. If we insert one more point \(r\) on top of it that increases the total number to \(n+1\), without loss of generality, we can always add it to the left side of the other points since the algorithm starts from the rightmost and searches to the left. If there is an edge between \(r\) and any point in \(Q\), according to the algorithm, \(r\) will be added to the optimal path. When there is no edge between \(r\) and any point in \(Q\), no matter which path \(r\) will join, the hop number of it can not be greater than \(s_{Q}\) since all other points have smaller hop numbers (at least one less) than \(s_{Q}\). In that case, if \(s_{r}\) equals \(s_{Q}\), \(r\) will be added into the point set \(Q\). Therefore, for \(n+1\) points, the algorithms still works.