## 3 The Self-Adaptive Mobile Clustering Algorithm (SAMCA)
### Phase I: Cluster Formation
By adjusting randomized waiting timers, the sensors can coordinate themselves into sensible clusters, which can then be used as a basis for further communication and data processing. The procedures of cluster construction is outlined in the SAMCA of Figure 2.  
Figure 2: Virtual cluster construction flowchart for the SAMCA algorithm. Observe that the process of clusterhead selection induces non-overlapping clusters. Accordingly, to interconnect two adjacent non-overlapping clusters, one cluster member from each cluster must become a gateway. This subsection presents a method of choosing distributed gateways for adjacent non-overlapping clusters. Local information, such as neighboring density and mobility of the 1-hop neighbors, is applied to select gateways and further achieve communication between clusters. The result of gateway selection is that each cluster \(i\) assigns a single member to communicate with each nearby cluster \(j\). If the clusters are too far apart (outside the range of communication \(R\)), no gateway sensors will be assigned. Denote the sensor which can communicate with more than one cluster as a border sensor. Note that only border sensors are eligible for gateway selection. Let \(s_{i}\) be the border sensor \(s\) in cluster \(i\) and \(m_{j}\) be the border sensor \(m\) in cluster \(j\). \(G_{ij}\) denotes the gateway sensor in cluster \(i\) that connects cluster \(i\) to cluster \(j\). Let \(d_{s_{i}m_{j}}\) be the distance between sensors \(s_{i}\) and \(m_{j}\), which could be estimated by the received signal strength. Based on the cluster formation, sensors can obtain local information and know the number of neighboring sensors in adjacent clusters. When initializing the gateway selection process, clusterheads broadcast messages within the clusters. In order to achieve inter-cluster communication, a pair of border sensors with a shorter distance and similar speed may have a larger chance to be gateways. Thus, the border sensors exchange information (e.g., the distances between the neighboring sensors and their speed information) to compute the weighting values \(w_{ij}^{(s_{i}m_{j})}\), which yields  
\[w_{ij}^{(s_{i}m_{j})}=c_{1}\cdot d_{s_{i}m_{j}}+c_{2}\cdot\left((v_{s_{i}}+v_{m _{j}})\cdot 1_{\{|v_{s_{i}}-v_{m_{j}}|\leq v_{T}\}}+2(v_{s_{i}}+v_{m_{j}}) \cdot 1_{\{|v_{s_{i}}-v_{m_{j}}|>v_{T}\}}\right), \tag{2}\]  
where \(c_{1}\) and \(c_{2}\) are positive constants; the threshold \(v_{T}\) is set to be \(1/2\cdot v_{max}\). Given the weighting values, the operation may be divided into two stages: Contention Stage and Activation Stage. In the contention stage, each border sensor broadcasts a 1-hop message including its weighting values and the corresponding nominated pairs of distributed gateways for the nearby clusters. After a short time interval \(\tau_{g}\), the border sensor with the minimum weighting value announces itself as the winner for the gateway selection with respect to a specific cluster and further determine the corresponding gateway for the adjacent cluster. That is,  
\[G_{ij}=\arg\min_{s_{i},m_{j}}\{w_{ij}^{(s_{i}m_{j})}\}, \tag{3}\]  
where \(\{w_{ij}^{(s_{i}m_{j})}\}\) denotes the set of weighting measures in cluster \(i\) for selecting a gateway to cluster \(j\). Therefore, in the activation stage, the gateway nodes, \(G_{ij}\) and \(G_{ji}\), broadcast 1-hop messages to update the connectivity information and activate the linked cluster architecture. With the node mobility \(v=1\) m/sec, Figure 3 shows the typical runs of cluster formation of 100 and 200 sensors with \(R/\ell=0.145\) and \(R/\ell=0.115\), respectively, where \(R/\ell\) is the ratio of transmitting range \(R\) to the side length of the square \(\ell=100\) m.