# Adaptive Multi-Channel Clustering in IEEE 802.11s Wireless Mesh Networks +
## 4 The CHaChA Clustering Approach
### Online Cluster Adaptation
#### 4.4.4 Cluster Balancing  
The balancing of a cluster constellation can be done according to different aspects [39]. If the focus is on channel utilization, for example, nodes that communicate frequently could be grouped into smaller clusters, while nodes that communicate infrequently could be grouped into larger clusters. The logical coherence of devices at the application layer could also be taken into account. However, this requires prior knowledge of the type and communication patterns of applications or active observation of channel usage. On the other hand, if spatial node density is used as criterion, many small clusters on non-overlapping channels might be desirable in densely populated regions to reduce co-channel interference. In sparsely populated regions, again, larger clusters would be preferred to guarantee redundant paths and prevent node isolation. Such strategies, however, require knowledge of the spatial distribution of nodes or estimation of their positions.  
An intuitive approach that needs only little information is balancing the number of cluster participants [11]. With regard to network management scenarios, this pursues the goal of distributing the communication and management effort evenly among the clusters on the one hand. On the other hand, this limits the damage caused by a CH failure, as a result of which affected CMs have to reintegrate into the cluster constellation. The clustering phase sequence described in Section 4.3 does not guarantee the emergence of clusters of equal size. Due to the individual and simultaneous decision-making of all nodes during initial cluster joining, an imbalance in cluster sizes can only be detected afterwards. Therefore, the balancing concept presented below only takes effect after the clustering phase sequence is completed in phase 7. As in the work JRCAP [11], balancing of adjacent clusters is also proposed in CHaChA. The measure for balancing is the roaming of CMs at the edge between neighboring clusters previously described in Section 4.4.3.  
If an edge CM is eligible for roaming, it checks the need for cluster balancing after receiving new CH broadcast messages for its neighbor clusters, which contain the list of CMs of the respective cluster. After determining the current cluster sizes from the information in the CH messages, the CM compares its own cluster size with that of its neighboring clusters. If any of these clusters comprise at least two nodes below its own cluster size, the CM switches to the closest neighboring cluster according to its CH path cost (ALM). Thereby, a roaming direction from larger to smaller clusters is achieved.  
Figure 8 shows the balancing using the example of a \(5\times 5\)-node grid topology with five clusters. In the unbalanced initial state (Figure 8 left), the red and green clusters have a number of participants above the targeted average size of five nodes. The edge nodes 3 and 15 (green cluster) and 11 and 23 (red cluster) each possess the ability to roam into the neighboring cluster that is smaller by two nodes, with the simplified assumption that nodes 11 and 15 recognize this fact earlier and perform roaming. The result is a balanced cluster constellation (Figure 8 right).  
Figure 8: Cluster balancing in an example network (encircled roaming opportunities are detected first and are therefore executed). Reprinted from ref. [18].  
To coordinate roaming operations, each CH maintains a list of neighboring clusters to which CMs have recently migrated or from which CMs have joined in return. After each roaming operation, further transitions to the same destination cluster or from the same origin cluster are temporarily rejected to reduce conflicting roaming operations of CMs that have detected a balancing opportunity simultaneously. This strategy is a compromise between quickly balancing widely varying cluster sizes and preventing avalanche effects with the risk of oscillating clusters.