# Adaptive Multi-Channel Clustering in IEEE 802.11s Wireless Mesh Networks +
## 5 Prototype Implementation  
The concepts of our clustering approach CHaChA were realized as a Java application. Figure 9 shows the simplified architecture of the resulting software prototype. The implementation runs on Linux operating systems with 802.11s support. Configuration options (e.g., device names of the WLAN interfaces) as well as any parameters of the CHaChA algorithm (time constants and thresholds, see Section 4.2) can be passed individually as arguments at program start. The phase sequence for initial clustering, including the mechanisms for online cluster adaptation that take effect after reaching phase 7, was implemented as a state machine according to the concepts described in Sections 4.3 and 4.4. Depending on the phase and node role, state transitions depend on timeouts on the one hand and incoming CHaChA protocol messages on the other. The periodic sending of different message types, such as CENT messages for MCH election, MCH phase announcements, or CH info broadcasts is done in separate threads with their own transmission timers, which are active depending on the phase. Other functions realize the calculation of the various CHaChA metrics (see Sections 4.2) as well as decisions based on the connection status on the base and cluster channels. For TCP/UDP communication and connection information management, the program maintains Java objects that represent the node's mesh interfaces. A dedicated update thread handles the cyclic retrieval of the link and path lists from the Linux kernel and thus realizes a cross-layer integration of the 802.11s information into the application layer. The access to the 802.11s data structures of the Linux kernel module mac80211 is done by process calls of the command line program iw[40]. Here, the text outputs of the link and path lists read from iw are converted into corresponding Java data types (String lists) and stored within the MeshInterface objects. In addition to the connection information, each interface has a separate thread for sending and receiving CHaChA protocol messages via TCP and UDP, respectively. While TCP is used for reliable unicast transmissions to selected nodes and thus also for messages whose range should be limited to their own mesh neighbors, UDP is currently used exclusively for sending network-wide announcements as broadcast messages. The structure of the CHaChA protocol messages is summarized in Table 6, where the payload of an example message is given for each message type (opcode). For the prototypical implementation, a plaintext encoding was chosen, which allowed a simple analysis of  
Figure 9: Software architecture of the CHaChA prototype implementation. Reprinted from ref. [18]. the packet captures during the evaluation. To this end, all payload components, including MAC addresses, metric numeric values, and WLAN channel numbers, are serialized as Java String representations when sent and converted back to their corresponding data types at the receiving end. Starting with the opcode of the message, the fields of the payload are delimited by a reserved delimiter character ('1') and can thus be distinguished on reception. The simplest message types PHASE_X, PCH, and JOIN_REQ/LEAVE_REQ consist only of their opcode. The JOIN_RESP/LEAVE_RESP response messages additionally contain a 1 or 0 as an indication of acceptance or rejection of roaming requests. Similarly, the CENT, NC, and WNPR messages carry the numeric value of their metric, while the NH2 CH message contains the MAC address of the neighboring node via which the mesh path to its own CH is established. The more complex CH announcement messages consist of the cluster's mesh ID and channel number as well as the list of CM MAC addresses, in addition to their opcode. The CHAN_SEL message can also reach a certain size depending on the amount of CHs, as it is gradually extended by pairs of CH MAC address and cluster channel during the channel selection sequence in phase 5.