# Adaptive Multi-Channel Clustering in IEEE 802.11s Wireless Mesh Networks +
## 2 IEEE 802.11s WLAN Mesh Networks  
As the first common industry WLAN mesh standard, the amendment IEEE 802.11s was ratified in September 2011 [1]. It enables vendor-independent infrastructure-less multi-hop communication based on the widespread 802.11 technology. Mesh functions such as peering and routing are directly integrated into the MAC layer specification. Thus, 802.11s comes as a promising alternative to former, non-interoperable network-layer mesh routing protocols. To ensure interoperability, every 802.11s node must support the Hybrid Wireless Mesh Protocol (HWMP) and Airtime Link Metric (ALM) for mesh routing [19]. The default reactive mode of HWMP is based on the Ad Hoc On-Demand Distance Vector (AODV) routing protocol and determines a path as soon as it is needed. As usual for distance vector protocols, a node using HWMP only maintains links to nodes within radio range (neighbors) and paths to selected destinations in multi-hop distance, to which communication has been explicitly initiated, e.g., by higher layers. A node's path list maintains the forwarding rules to destination nodes. To every destination, only the past via the best neighbor (\"next hop\") is kept, resulting in the smallest ALM cost metric. Path information is updated periodically unless it expires with an inactivity timeout. Optionally, HWMP supports using a tree-based proactive routing mode alongside the reactive mode. Nodes that will be contacted frequently can use this mode to periodically announce themselves as so-called root nodes in the network and enforce determination of uni- or bidirectional path information to them in advance. This reduces routing latency at the expense of additional message overhead [19]. There are three proactive routing variants: In the mode \"proactive PREQ without PREP\", a root node periodically sends PREQ (path  
Figure 1: Distributed status monitoring in a smart city scenario. Reprinted from ref. [18]. request) broadcast messages addressed to all nodes in the network. However, no response via a PREP (path reply) is expected, so all nodes simply create the reverse path to the root node. If this is sufficient for the use case, this mode generates the lowest overhead. The mode \"proactive PREQ with PREP\" is similar to the previous variant, but a PREP is required from each node. This means that bidirectional paths are always maintained between the root node and all other nodes. The mode \"proactive RANN\" represents a compromise between the first two variants. Here, so-called RANN (root announcement) messages are sent periodically, but these only propagate or update the ALM cost metric to the root node in the network. Bidirectional path creation using unicast PREQ and PREP is initiated by the receiving mesh nodes only when path information changes. The ALM estimates the time cost for frame transmissions considering protocol overhead, data rate, and error probability. Each node only calculates the ALM to its neighbors, and individual link costs are accumulated and disseminated during path discovery. Due to this cumulative characteristic, the ALM of a multi-hop path represents the overall average estimated time to transmit a single frame from source to destination. The airtime cost \(c_{a}\) (in \(\mu\)s) is calculated per link, as defined by the IEEE 802.11 standard [1]:  
\[c_{a}=\left[O+\frac{B_{t}}{r}\right]\cdot\frac{1}{1-e_{fr}} \tag{1}\]  
\(O\) is a constant for the channel access and MAC protocol overhead. \(B_{t}\) is the test frame size, specified as 1 kb in the standard. \(r\) denotes the test frame data rate, given in Mbps, whereas \(e_{fr}\) denotes the expected frame error rate. The estimation of \(e_{fr}\) and the value \(O\) are not predefined by the 802.11s standard but left open to vendor implementations. The Linux kernel module mac80211 [20] currently contains the most sophisticated implementation of 802.11s and HWMP. By default, path information expires after 5 s and are refreshed 1 s in advance of a timeout.