# Adaptive Multi-Channel Clustering in IEEE 802.11s Wireless Mesh Networks +
## 4 The CHaChA Clustering Approach  
### Overview and Terminology  
The presented approach CHaChA includes, on the one hand, concepts for initial cluster formation and channel assignment when commissioning an 802.11s network. On the other hand, mechanisms for automatic cluster adaptation in case of subsequent changes to the network structure are presented. Our concept assumes nodes with multiple physical WLAN interfaces, at least two of which are available for use within the mesh network. This represents a common hardware configuration for modern WLAN devices, as can be expected especially in more complex backbone installations [12]. Of the interfaces, one remains as a dedicated primary interface on a given base channel for inter-cluster communication, while a secondary interface is reserved for intra-cluster communication. This principle, also known as \"common channel\", is used in many research works to ensure unrestricted connectivity in the network at all times regardless of the cluster configuration [11; 27]. Since all nodes are always reachable via the base channel, the primary interface is used to exchange any CHaChA control messages. In addition, its 802.11s link and path tables serve as basis for deriving topology information and metrics for cluster formation. Our simplifying assumption is that the physical parameters of the secondary interfaces are similar to those of the primary interface and that clustering decisions made based on its metrics are applicable in general. The initial cluster formation and channel assignment during mesh network commissioning are realized in a sequence of phases. Along the way, the mesh nodes take on different roles, which are summarized in Table 2. Figure 3 shows the overview of all steps. A detailed algorithmic description is given in Section 4.3. Initial cluster formation occurs in phases 0-4, which divide the network into non-overlapping regions, taking into account the mesh topology. From all nodes starting as Cluster-Free Nodes (CFNs) at the beginning, temporary Proposed Cluster Heads (PCHs) emerge during the phases and compete as candidates for the final role as Cluster Head (CH). Each cluster consists of a lead CH and multiple Cluster Members (CMs) and forms a separate mesh network on the secondary interface of its participants. Compared to the base network on the primary interface, the individual clusters represent broadcast domains of smaller size. This has the potential to reduce the communication load on the base network by moving applications to appropriate clusters. Phases 5 and 6 realize the cluster channel selection and configuration of the nodes' secondary interfaces. The separation into orthogonal channels avoids interference between neighboring clusters as well as with the base channel, thus favoring parallelism of transmissions throughout the network. The current concept is limited to the integration of two WLAN interfaces per node. However, the strategy described can be extended analogously to scenarios in which additional interfaces are available for mesh communication. For example, applications within a cluster could be specifically assigned to different interfaces on orthogonal channels. \begin{table}
\begin{tabular}{l l l} \hline \hline
**Role** & **Abbreviation** & **Description** \\ \hline Cluster-Free Node & CFN & starting role, node without cluster \\ \hline Cluster Member & CM & node belonging to a cluster \\ \hline Cluster Head & CH & node organizing a cluster \\ \hline Proposed Cluster Head & PCH & temporary CH candidate in phase sequence \\ \hline Master Cluster Head & MCH & phase coordinator and first selected CH \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Node roles in CHaChA. Reprinted from ref. [18]. In phase 7, initialization of the network is complete, and distributed applications can benefit from the created clusters.