## 3 Distributed Clustering Techniques
### Cluster Formation Techniques  
In order to provide an objective comparison of alternative distributed cluster formation techniques, we chose to simulate three clustering techniques (Table 2) that approximate the range of techniques from the literature. It should be noted that all three techniques shown in Table 2 are heterogeneous (_i.e._, are composed of multiple node types) and use range-free localization (_i.e._, there are no assumptions about point-to-point distances between nodes). As well, all three techniques use bidding-based protocols to recruit nodes to form clusters. The first two techniques result in pre-defined clusters of Anchor Nodes that are centered on a Sink Node cluster head. For the Static technique, the cluster formation process is initiated by Sink Nodes using the well-established Contract Net Protocol (CNP) for distributed communication and control [21]. In contrast, the Dynamic technique relies on Anchor Nodes to initiate cluster formation using a Vickrey auction [22]. The implementations of the CNP and Vickrey auction protocols are shown in Appendix 1. The main difference between the static and the dynamic techniques is their ability to adapt to change during operation. Typically, a cluster formation technique is regarded as dynamic when it includes regular (periodic or event-driven) cluster head re-election or cluster reorganization procedures, either to effectively react to network topology changes and adjust appropriately the cluster topology, or simply aiming at the appropriate rotation of the cluster head role among the nodes to gain energy efficiency. Given that our WSN is heterogeneous with Sink Nodes serving as cluster heads, cluster head re-election does not occur. However, the dynamic technique differs from the static technique in its ability to reorganize its clusters to facilitate Mobile Node tracking. As its name implies, clusters formed by the static technique are fixed; in contrast, clusters formed by the dynamic technique can adapt by borrowing Anchor Nodes from adjacent clusters as Mobile Nodes approach cluster boundaries. The intention is to approximate the more dynamic pre-defined clustering approaches of [12; 15] with the dynamic technique. The bidding-based protocols used by both the static and the dynamic techniques result in clusters where each Anchor Node is a member of the cluster whose mean (the Sink Node or \"cluster head\") is located closer to the Anchor Node than any other. This process results in a distributed implementation of the k-means algorithm that has the advantage of addressing the computational complexity of the k-means problem [23]: by distributing the algorithm over a network in this manner, our approach allows the clustering problem to be tackled in a reasonable time. Like many of the pre-defined clustering approaches reported in the literature, the computational complexity of the static and dynamic techniques are in the order of \(O(n)\), where \(n\) represent the number of nodes. The resulting network topology is a set of clusters in the form of Voronoi cells [24]. For both the static and the dynamic techniques, we use this network topology, along with the average received \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Cluster Formation Technique** & **Protocol** & **Cluster Head** & **Notes** \\ \hline Static & Contract Net Protocol (CNP) & Sink Node & Bidding initiate by Sink Node Agent \\ Dynamic & Vickrey Auction & Sink Node & Bidding initiated by Anchor Node Agent \\ _Ad Hoc_ & Vickrey Auction & Sink Node & Bidding initiate by Sink Node Agent \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Cluster formation techniques. signal strength (ARSS) to determine when a Mobile Node tracking task is passed from one cluster to the next. The bidding-based protocols used for cluster formation also provide the static and dynamic techniques with the ability to adapt to the shop floor environment.