# GraphSAGE-Based Multi-Path Reliable Routing Algorithm for Wireless Mesh Networks
## 3 Multi-Path Routing Algorithm Based on the Improved Breadth First Search
### Multipath Output
The network performance value can be written as:

\[performance_{i}=\sum\limits_{j=1}^{m}w_{j}d_{ij} \tag{9}\]

where \(w_{j}\) represents the weight of metric \(j\), \(\sum\limits_{j=1}^{m}w_{j}=1\), and \(w_{j}\) can be set with different weight values according to specific requirements. According to the study of the influencing factors of network performance in [22], we select three important network performance metrics, traffic, transmission delay, and packet loss rate, and set the weight values \(w=(0.2,0.35,0.45)\). The specific process of generating labels for the network feature dataset is as follows:

**Step 1:**: Randomly initialize the membership value \(u_{ij}\), and the fuzzy coefficient is generally set to 2 by default [23]. Use the FCM algorithm to iterate parameters on the network feature dataset \(X_{train}\) to obtain the cluster center \(\{c_{1},c_{2},\cdots,c_{l}\}\) and fuzzy partition coefficient FPC. **Step 2:**: Repeat Step 1 with a different number of clusters \(l\), record the number of clusters with the largest FPC value as \(l_{best}\), and obtain the cluster center \(\left\{\,c_{1},c_{2},\cdots,c_{l_{best}}\right\}\). At this point, \(X_{train}\) has been divided into \(l_{best}\) classes. **Step 3:**: Take the average of the network feature vectors of the network feature dataset by category to obtain \(l_{best}\) network feature vectors, and calculate their corresponding network performance value \(performance\). Rank the network performance classes according to the network performance value \(performance\), the larger the value the better the network performance, thus the network performance can correspond to the cluster categories. **Step 4:**: According to the cluster centers obtained from Step 2 and the relationship between network performance and cluster categories obtained from Step 3, label the node feature vectors \(\{x_{v}|v=0,\cdots,N-1\}\) by network performance value \(performance\), which provides conditions for the supervised training of the GraphSAGE model. ### GraphSAGE-Based Graph Representation Learning

GraphSAGE is used to learn the network topology \(G(V,E)\) and node features \(\{x_{v},v=0,\cdots,N-1\}\). GraphSAGE aggregates the features of neighbor nodes to generate the vector representation of the target node, which is used for the following node classification task. This paper selects three attributes of traffic, transmission delay, and packet loss rate as node feature vectors, then \(x_{v}\) can be written as:

\[x_{v}=[Q_{v},D_{v},L_{v}] \tag{10}\]

where \(Q_{v}\) denotes the traffic (in this paper, the packet delivery rate is used to express the traffic); \(D_{v}\) denotes the transmission delay; \(L_{v}\) denotes the packet loss rate. As shown in Figure 4, the process of GraphSAGE to generate node vector representations can be divided into three steps. 1. Sampling: The target node is selected by random walk, and then the neighbor nodes of the target node are sampled. The number of neighbors sampled in each hop is \(S_{i},i=1,2,\cdots,K\). If the number of neighbor nodes is less than \(S_{i}\), a resampling method with put back is used. If the number of neighbor nodes is greater than \(S_{i}\), a negative sampling method without put back is used. \(K\) represents the search depth, and according to the study of [15], when \(K=2\), GraphSAGE can get excellent performance, so \(K\) is set as 2. When \(K=2\), \(S_{1}=3\), \(S_{2}=7\), the sampling process is shown in the sampling section of Figure 4.
2. Aggregation: GraphSAGE aggregates the information of neighbor nodes at each layer by \(K\) aggregator functions and updates the target node's own node information. In this paper, the Mean aggregator is used to obtain the aggregated features of neighbor nodes at each layer. GraphSAGE then splices the feature representation of the target node at layer \(k-1\) with the aggregated features of the neighbor nodes in layer \(k\), and eventually uses the nonlinear activation function to obtain the vector representation of the target node of layer \(k\).