## 3 The Self-Adaptive Mobile Clustering Algorithm (SAMCA)
### Phase I: Cluster Formation  
Clusterhead Selection  
In order to transit network operation from transitional phase to steady phase smoothly, the system warm-up time may be required in a mobile network. The study in [47] suggests that the warm-up time is a function of node velocity, transmission range, network field, and the mobility model. Assume the value of warm-up time of sensor \(i\), \(WU_{i}\), is a sample from the distribution \(C\)+\(\lambda\)\(\cdot\)\(U(0,1)\), where \(C\) and \(\lambda\) are positive numbers, the use of parameter \(\lambda\) is used to specify the sampling range of the warm-up time, and \(U(0,1)\) is a uniform distribution. In our case, the positive number \(C\) may be considered as an important indicator to capture the warm-up process of the SAMCA protocol (detailed in Section 6.7.). After passing the warm-up time, each sensor sets a random waiting timer for selecting clusterheads. Similar to the setting of warm-up time, the initial value of waiting time of sensor \(i\), \(WT_{i}\), may be a sample from the distribution \(C\)+\(\lambda\)\(\cdot\)\(U(0,1)\). Each sensor broadcasts a 1-hop _Hello_ message and listens for its neighbor's _Hello_, which allows each sensor to estimate how many neighbors it has. Then sensors update their neighbor information and decrease the random waiting time based on the node mobility and each 'new' _Hello_ message received. To avoid quickly losing the connectivity with neighboring sensors after being a clusterhead, the node mobility of a clusterhead may not be high or low such that the frequency of structure changes may be suppressed. Therefore, the sensors with many neighbors and modest mobility may be good candidates for initiating new clusters; those with few neighbors and high or low mobility may choose to wait. One strategy for updating the random waiting time of sensor \(i\) is  
\[WT_{i}^{(k+1)}=\log_{2}\left(1+\frac{|v_{i}^{(k)}-\frac{1}{2}(v_{\max}+v_{\min })|}{\frac{1}{2}(v_{\max}-v_{\min})}\right)\cdot\rho\cdot WT_{i}^{(k)}=M_{i}^{ (k)}\cdot\rho\cdot WT_{i}^{(k)}, \tag{1}\]where \(WT_{i}^{(k)}\) is the waiting time of sensor \(i\) at time step \(k\) and \(0<\rho<1\), \(v_{i}^{(k)}\) is the speed of sensor \(i\) at time step \(k\) and \(v_{\max}\) and \(v_{\min}\) are known bounds on the velocity with \(0\leq v_{\min}<v_{\max}\), and \(M_{i}^{(k)}\) represents the \(\log_{2}(\cdot)\) function. As shown in Figure 1, the \(\log_{2}(\cdot)\) function is with maximum value 1 as \(v_{i}^{(k)}=v_{\max}\) or \(v_{\min}\) and minimum value 0 as \(v_{i}^{(k)}=\frac{1}{2}(v_{\max}+v_{\min})\). Note that the proposed mechanism, considering the neighboring density and node mobility, suggests a sensible approach for adjusting the waiting time. If the random waiting timer expires (i.e., \(WT_{i}=0\)) and none of the neighboring sensors are already members of a cluster, then sensor \(i\) declares itself a clusterhead and broadcasts a 1-hop message proclaiming that it is beginning a new cluster; this also serves to notify its neighbors that they are assigned to join the new cluster with ID \(i\). When a sensor joins the cluster, it sends an updated \(Hello\) message and stops its waiting timer. In order to balance the load among clusters, the appropriate setting for the desired cluster size in a mobile network is crucial. Therefore, a reference cluster size \(z\) is defined to maintain network operation. Accordingly, a clusterhead may choose its cluster members using the distance information (e.g. selecting the nearest neighboring sensors) based on this reference cluster size \(z\) (described in Section 4.1.). Given the implementation of the SAMCA, there are three different kinds of sensors: (1) the  
Figure 1: The update strategy for the random waiting time of sensor \(i\) with varying velocity. clusterheads, (2) sensors with an assigned cluster ID, and (3) sensors without an assigned cluster ID, which will join any nearby cluster and become 2-hop sensors. Thus, the topology of the ad-hoc network is now represented by a hierarchical collection of clusters.