## 4 Centralized and Distributed Algorithms
### Centralized HAS\({}^{4}\)  
In centralized HAS\({}^{4}\), the trade-off factor \(l\) falls in \([0,1]\), and \(1-l\) is the proportion of \(S_{U}\) candidate in all sensors, which means at least \(n\times l\) sensors will be visited by the mobile AUV. The whole procedure is as shown in Algorithm 1.  
Firstly, HAS\({}^{4}\) estimates the lifetime of each sensor to heuristically sort the sensors. The sensor lifetime is defined as the value that the remainder of the energy divides by the energy consumption in this period. The energy is consumed on data sensing and transmission, and sensing consumption is almost constant with the preassigned task. Since the energy spent on transmission varies between different modes and acoustic is much costlier than MI, without loss of generality, we use acoustic transmission cost as the communication energy consumption. In addition, due to the fact that we have not known the data flow, we average all possible values as the consumption. After sorting the sensors,a lifetime threshold is set as the lifetime of the \(\lceil nl\rceil\)-th sensor that sensors with smaller lifetimes can not be chosen into \(S_{U}\).  
Secondly, HAS\({}^{4}\) greedy selects the minimum lifetime sensor from \(S_{C}\) into \(S_{A}\), and then adds all its neighbours into \(U\). We denote \(U\) as the tuple set of candidate sensors of \(S_{U}\) with its upper level sensor. The upper level sensor is the sensor where the sensing data would transmit to.  
Thirdly, HAS\({}^{4}\) heuristically chooses the sensor with the largest lifetime from \(U\) to verify if it could be added to \(S_{U}\). In the verification, HAS\({}^{4}\) compares its lifetime with the threshold and all constraints in Section 3.2. If it satisfies all conditions, HAS\({}^{4}\) adds this sensor to \(S_{U}\), changes channel indicators and adds its neighbours from \(S_{C}\) to \(U\). Otherwise, it removes this sensor from \(U\). HAS\({}^{4}\) repeats this process until \(U\) is empty and then goes to the second step.  
When \(S_{C}\) is empty, the shortest tour among all \(S_{A}\) could be solved by approximately solving a TSP.  
Since the outer while loop will execute at most n times, where \(n\) is the node number, and the inner while loop will execute at most \(|U|\) times, the centralized HAS\({}^{4}\) is a \(\Omega(mn)\) time algorithm, where \(m\) is neighbour number of the node with maximal neighbours.  
```
Input: An underwater sensor network; A tread off factor \(l\) between delay and lifetime; The residual energy of each sensor \(e_{i}\). Output: A set of sensor that will be visited by AUV \(S_{A}\); Multiple data forward link; A traveling tour. Add all sensor to \(S_{C}\); Ascending sort \(S_{C}\) via lifetime \(\frac{e_{i}-p_{i}^{out}}{p_{i}^{out}(mn)}\); Define the threshold lifetime \(T_{l}\) to be the lifetime of the \(\lceil nl\rceil\)-th sensor in \(S_{C}\); while\(S_{C}\) is not emptydo\(u\gets S_{C}(1)\); \(S_{A}\gets u\bigcup S_{A}\); \(S_{C}\gets S_{C}-u\); \(U\gets<j,u>,\forall j\in N_{u}\); while\(U\) is not emptydo Descending sort \(U\) via lifetime \(\frac{e_{i}-p_{i}^{out}}{p_{i}^{out}(mn)}\); \(k\gets U(1)\); if lifetime of \(k\leq T_{l}\)then\(U\leftarrow\emptyset\); Break;  end if if\(\sum_{m\in M}\sum_{i\in T}f^{i}\geq 2\Delta tv_{k}\)then\(S_{U}\gets k\bigcup S_{U}\); \(U\rightarrow<j,k>,\forall j\in N_{k}\);  end if \(U\gets U-k\);  end if  end while Find an approximate tour among \(S_{A}\);
```  
**Algorithm 1**Centralized HAS\({}^{4}\).