# Adaptive Multi-Channel Clustering in IEEE 802.11s Wireless Mesh Networks +
## 4 The CHaChA Clustering Approach
### Metrics, Messages, and Parameters  
A main motivation of CHaChA is its vendor-independent applicability above standard hardware and software. It is based on the unmodified Linux 802.11(s) protocol stack, which ensures mesh interoperability already at the link layer. Due to the 802.11s routing protocol HWMP, being a distance vector protocol, each participant has only incomplete knowledge about the network topology. This work therefore takes a heuristic approach, relying on the nodes' local 802.11s connection information and deriving further metrics from it. Several metrics are used in CHaChA, which are first explained independently of the phase flow. Table 3 gives an overview of all metrics and their calculation. **Airtime Link Metric (ALM):** The ALM is the default metric of the 802.11s routing protocol HWMP. It describes the time cost of a frame transmission to a destination node, taking into account the WLAN transmission rate and error probability. Due to its cumulative computation along all hops of a path, it represents both its length and overall quality. In CHaChA, the ALM serves as a distance measure, e.g., for determining nearby CHs. **Centrality (CENT):** The CENT metric is an estimate of the centrality of a node's position in the network. The node with largest CENT value (\(CENT_{max}\)) is initially assigned the MCH role. In mesh networks consisting of devices with similar WLAN hardware characteristics (number of antennas and supported transmission rates), the ALM cost of a path arises significantly from its hop count, provided that individual link conditions (e.g., strongly varying distance or attenuation characteristics) do not translate into a permanently high error rate and low data rate of individual hops. Consequently, the assumption can be made that the node positioned at the center of any mesh topology likely has the lowest ALM average of all paths to other nodes, since it reaches them via the shortest average path lengths. After a node has determined path information to all other nodes, for example by temporarily activating the proactive mode of the 802.11s routing protocol HWMP, it can calculate its centrality using the formula \(CENT=(\sum_{i=1}^{*paths}ALM_{i})^{-1}\). **Network Size \(N\):** As a result of a path establishment in proactive HWMP mode, a node simultaneously obtains knowledge about the overall number of participants in the network, denoted by \(N\). It is obtained from the sum \(N=1+\#(paths)\). \begin{table}
\begin{tabular}{l c l} \hline \hline
**Metric** & **Abbreviation** & **Calculation** \\ \hline Airtime Link Metric & ALM & per hop: \(c_{a}=(O+\frac{B}{r})\cdot\frac{1}{1-e}\) \\  & & per path: \(ALM=\sum_{i=1}^{*Hops}c_{a_{i}}\) \\ \hline Centrality & CENT & \(CENT=(\sum_{i=1}^{*Paths}ALM_{i})^{-1}\) \\ \hline Network Size & N & \(N=1+\#(\text{Paths})\) \\ \hline Neighbor Count & NC & \(NC=\#(\text{Links})\) \\ \hline PCH Neighbor Count & PCHNC & \(PCHNC=\#(\text{Links to PCHs})\) \\ \hline NC-to-PCHNC Ratio & NPR & \(NPR=\frac{NC}{(1+PCHNC)\cdot N}\) \\ \hline Weighted NPR & WNPR & \(WNPR=NPR\cdot\frac{CENT}{CENT_{max}}\) \\ \hline Integer value of MAC address & — & Example: 00:00:00:00:fa:00 \(\rightarrow\) 64, 000 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Metrics in CHaChA (\(c_{a}\): airtime cost, \(O\): 802.11 protocol overhead, \(B\): frame bit length, \(r\): 802.11 data rate, \(e\): frame error probability). Reprinted from ref. [18]. Neighbor Count (NC):The NC of a mesh node is given by the number of active links to neighboring nodes. Nodes with maximum NC in their neighborhood can reach the highest proportion of other nodes directly and are least likely to be isolated in their network region. For these reasons, they are considered suitable candidates for the CH role and compete for it as temporary PCHs. The NC metric has also been proposed under similar names in other research, such as Highest Connectivity (HC) in [27; 30]. PCH Neighbor Count (PCHNC):The PCHNC is part of the calculation of the NC-to-PCHNC Ratio (NPR) and is only determined by PCH nodes.