# Adaptive Multi-Channel Clustering in IEEE 802.11s Wireless Mesh Networks +
## 4 The CHaChA Clustering Approach
### Initial Clustering and Channel Assignment
Until reaching phase 3 each CFN also activates the proactive routing mode of the HWMP to temporarily determine mesh paths to all other nodes. CHaChA makes targeted use of the proactive HWMP variants. At this stage, the most efficient of the three proactive modes is chosen (\"proactive PREQ without PREP\"), whereby a node in the network announces itself but does not expect a response for bidirectional path establishment. This variant is sufficient since all CFNs activate the mode and thus receive unidirectional path costs to each other. Compared to the conventional reactive HWMP mode, this temporarily generates more 802.11s control messages, but results in lower overhead than higher-layer network exploration (e.g., using ping scan) [34; 35]. As a result, each CFN knows the current network size \(N\) as well as the ALM cost to all other nodes. This enables computation of the CENT metric, and all nodes then announce to the network periodically at CENT_PERIOD intervals using CENT broadcast messages, thereby competing for the MCH role. Upon receiving messages with larger metric (or larger MAC address in case of a tie), nodes decide to withdraw from the competition and stop sending messages. Once the CFN with largest CENT value has sent at least CENT_THRESH consecutive messages without receiving any in return, it automatically becomes MCH. It later acts as CH of a central cluster and coordinates the remaining phase sequence. Its central position in the network and therefore lowest average distance to all other nodes results in minimal frame forwarding overhead when sending control messages and enables fast broadcast delivery. Figure 3(a) shows the network state at the end of phase 0 in the example of a \(5\times 5\)-node grid topology. To announce the transition to phase 1 to all nodes, the MCH (node 13 in the example) broadcasts PHASE_1 messages at the time interval of PHASE_1_PERIOD. After a number of PHASE_1_TRIES broadcasts, it moves to the next phase itself. This procedure applies analogously to phases 1-6. **Phase 1--PCH Election:** In phase 1, the election of CH candidates, called PCHs, takes place. For this purpose, all nodes compare their NC metric with the NC values of their neighbors exchanged in phase 0. The nodes with highest NC in their neighborhood switch from the CFN to the PCH role, while a tie in metrics is allowed. This can temporarily create multiple neighboring CH candidates with the same degree of connectivity, which are further thinned out in the subsequent phase. All PCHs now inform their neighboring nodes of their candidacy by sending PCH unicast messages. Figure 3(b) shows the intermediate result at the end of phase 1 in the example network, in which eight PCHs emerge. After the expiration of a waiting time defined as PHASE_2_DELAY (analogous parameters for phases 3-5), the MCH initiates the phase transition with PHASE_2 messages. **Phase 2--CH Election:** All PCHs compute their WNPR metric at the beginning of this phase and send it via WNPR unicast messages to PCHs in their neighborhood. The PCHs with highest metric, or largest MAC address in case of metric tie, win the competition and become the final CHs. The losing PCHs switch back to the initial CFN role. Figure 3(c) shows the intermediate result at the end of phase 2 in the example network, with four CHs emerging in addition to the central MCH. After the PHASE_3_DELAY waiting time expires, the MCH initiates the transition to phase 3. **Phase 3--CH Announcement:** All CFNs now switch from proactive routing to the more resource-saving reactive HWMP mode. Only the MCH and CHs remain in proactive mode to ensure that all other nodes have path information and ALM costs to them at all times. Furthermore, the MCH and CHs enable periodic broadcast of CH messages to announce their role and cluster information on the base channel. This includes the unique mesh IDas well as the WLAN channel of the cluster, for which joining nodes need to configure their secondary interfaces.