# Adaptive Multi-Channel Clustering in IEEE 802.11s Wireless Mesh Networks +
## 4 The CHaChA Clustering Approach
### Initial Clustering and Channel Assignment  
The initial cluster formation is described in detail below, attributing all messages and parameters to the phase sequence. An exception are the message types NH2 CH, JOIN_REQ/RESP, and LEAVE_REQ/RESP. These are used only in phase 7 for further concepts, which are explained in Section 4.4. Phase 0--Network Initialization and MCH Election:In phase 0, all nodes start as Cluster-Free Node (CFN) and are connected by their primary interface. A precondition for the execution of the CHaChA algorithm is the presence of at least one active connection to a \begin{table}
\begin{tabular}{l l l} \hline \hline
**Type (Opcode)** & **UC/BC** & **Description** \\ \hline \hline CENT & BC & network-wide dissemination of CENT metric, sent by CFNs in phase 0 \\ \hline NC & UC & announcement of NC metric to neighbors, sent by CFNs in phase 0 \\ \hline PCH & UC & announcement of PCH role to neighbors, sent by PCHs in phase 1 \\ \hline WNPR & UC & exchange of WNPR metric between neighboring PCHs in phase 2 \\ \hline CH & BC & periodic announcement of cluster info (mesh ID, channel, list of CM MAC addresses), sent by CHs from phase 3 onward \\ \hline JOIN & UC & control message for cluster joining, sent by CFNs (CMs) \\ \hline LEAVE & UC & control message for cluster leaving, sent by CMs \\ \hline CHAN_SEL & UC & control message for channel selection, exchanged between CHs in phase 5; carries pairs of CH MAC address and channel number \\ \hline PHASE\_X & BC & MCH announcement of transition to phase X (defined for phases 1–6) \\ \hline NH2 CH & UC & exchange of Next-Hop-to-CH(NH2 CH) info between neighboring CMs in phase 7; used for roaming and cluster balancing (see Section 4.4.4) \\ \hline JOIN\_REQ/RESP & UC & handshake messages between CMs and CHs to coordinate roaming operations in phase 7 (see Section 4.4.3) \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Unicast (UC) and broadcast (BC) messages in CHaChA. Reprinted from ref. [18]. \begin{table}
\begin{tabular}{l c l} \hline \hline
**Parameter** & **Unit** & **Description** \\ \hline \hline CENT\_PERIOD & ms & sending interval of CENT messages in phase 0 \\ \hline CENT\_THRESH & \# & max. no. of CENT messages sent without receiving any; exceeded by winner of K.O. race for MCH role in phase 0 \\ \hline NC\_PERIOD & ms & sending interval of NC messages in phase 0 \\ \hline CH\_PERIOD & ms & sending interval of CH messages from phase 3 onward \\ \hline CH\_THRESH & \# & max. no. of CH\_PERIODs to wait for incoming CH messages in phase 0 (detection of existing clusters) \\ \hline PHASE\_X\_DELAY & ms & waiting time in phase X-1 before MCH announces phase X (defined for phases 2–5) \\ \hline PHASE\_X\_PERIOD & ms & sending interval of PHASE\_X messages (defined for phases 1–6) \\ \hline PHASE\_X\_TRIES & \# & no. of repetitions of PHASE\_X messages (defined for phases 1–6) \\ \hline PHASE\_X\_TIMEOUT & ms & timeout of transition to next phase (defined for phases 1–6); exceeding leads to switching back in phase 0 \\ \hline NH2 CH\_PERIOD & ms & sending interval of NH2 CH (Next-Hop-to-CH) messages in phase 7 \\ \hline CONN\_TIMEOUT & ms & timeout of recovery from error state (connection loss) in phase 7; exceeding leads to switching back in phase 0 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Timing parameters and thresholds in CHaChA (# indicates integer value without unit). Reprinted from ref. [18]. neighboring node on the base channel. In the following, a synchronous start of execution is assumed on all devices, so that they run through the initial phase sequence together. Mechanisms for subsequently joining an existing cluster constellation are also located in phase 0 and discussed in Section 4.4.1. During phase 0, each CFN periodically sends NC unicast messages to its neighboring nodes at intervals of NC_PERIOD. These contain the current NC metric, which all nodes later compare in phase 1 to determine the PCHs.