## 4 Optimizing Path Schedule of the Mobile Sink
### The Practice Case  
As we mentioned before, in practice, each UGV is not able to follow their schedule strictly due to the various facts. Most of the time, they will arrive slightly ahead or later than scheduled, while, in rare cases, there is a large deviation. Therefore, it is not possible to build a precedence graph since the future is not predetermined and predictable so that \"backward\" algorithms cannot work anymore. In this paper, according to the statistics, we model the interval between two appearances of a UGV as the Gaussian distribution. Only the expected time of the first appearance and the expected cycle time of each UAV are known to the mobile sink. All other additional information, such as the exact appearing time of a UGV in a certain cycle, can only be received when the mobile sink visits a UAV and meets it during its appearance. Therefore, if any proactive solutions still rely on the precedence graph without timely information updating, a time interval for the mobile sink arriving early and staying long enough at each UGV point must be preserved on the base of the worst case of the possibility. However, the consequence is a sharp degression in performance due to accumulated errors. In this paper, we propose a distributed greedy algorithm called **k-hop** (Algorithm 3) to solve the problem. \(k\) means the depth of the search algorithm. As shown in Figure 3, there are three UGVs, and nine points are generated along the time scale. Points with a darker color are the last appearance times known, while points with a lighter color are the predicted appearance times. The search starts from the point \(q\) and expands the path by adding points until the path reaches three edges. Many paths may exist, and the points at the end of those paths are called \(q\)'s k-hop neighbors. As seen in the Figure 3, where \(k=3\), these points in the area between the line \(t_{1}\) and \(t_{2}\) are all k-hop neighbors of \(q\). In other words, the mobile sink needs to cross three edges (hops) to reach any of those points. Since it is not possible to fully predict the future, in order to visit as many points as possible, a local optimal can be achieved instead, where we need find the path passing the same number of points in the least amount of time. In Figure 3, when \(k=3\), there are two paths leading to the nearest 3-hop neighbor, point \(r\). We can pick any one of them to start the next round search. The simplest way is giving \(k\) the value of \"1\". Then, the algorithm will set the nearest neighbor in the time scale of the current point as the next point. Apparently, the greater the \(k\) is, the more possibilities we have in finding the optimal path. However, since the UGVs appear irregularly, the more hops we consider, the more errors as well as computational costs will be introduced. There must be a trade-off between the performance and the cost. In the worst case, the complexity of the k-hop algorithm is \(O(n^{k})\). Therefore, we must find the balance of the performance and the overhead of the \(k\). In this paper, we propose the empirical value of \(k\) as  
\[k=\log_{A_{out}}n, \tag{4}\]  
where \(n\) is the total number of points in the precedence graph and \(\bar{A}_{out}\) stands for the averaged out degree in the graph. The idea behind the equation is that if the averaged out degree is large, then the algorithm can search closer for a better path since multiple paths overlap at many common points. In a few steps, different paths may be connected to the same point. On the other hand, when \(\bar{A}_{out}\) is small, the path is more independent so the algorithm needs to check more steps before it can make a decision on which one is better because, if the chosen path is not good, the mobile sink has to stay in this path for some steps before it can choose another path. The shortest path can also be achieved based on our algorithms since, in the matrix \(M\), the distance between two points is recorded. It is not difficult to calculate the shortest path.