# 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  
Based on \(FrontPoint\) obtained in Section 3.1, the connecting relations of the nodes in the shortest paths are obtained. This paper introduces the shortest path adjacency matrix \(A_{s}\). This adjacency matrix only keeps the connecting relations of the nodes that satisfy the shortest paths, which means that all paths from the source to the destination obtained through this adjacency matrix are the shortest paths. The elements of \(A_{s}(a_{s_{ij}})\) are defined as follows, where \(i,j=0,1,\cdots,N-1\). \[a_{s_{ij}}=\left\{ \begin{array}{ll}1,\;if\;node\;j\in FrontPoint(i)\\ 0,\;else\end{array} \right. \tag{2}\]  
By traversing the shortest path adjacency matrix \(A_{s}\), all the shortest paths between the source to destination are obtained. This paper uses an algorithm that combines stack and loop for full traversal [18]. This algorithm requires two stacks, a main stack \(Stack_{main}\) to store the nodes on the path and an auxiliary stack \(Stack_{auxiliary}\) to store the neighbor node list \(Array\) of the corresponding element of \(Stack_{main}\). The main and auxiliary stacks are of equal length. The algorithm is as follows (Algorithm 1):```
Input: The shortest path adjacency matrix \(A_{s}\); source \(src\); destination \(dst\) Output: The set of shortest paths \(Path=\{path_{i}|i=1,2,\cdots,m\}\)
1 Press \(src\) into the main stack \(Stack_{main}\). 2 Traverse shortest path adjacency matrix \(A_{s}\), store neighbor nodes of the source into the neighbor node list \(Array\), and then press \(Array\) into the auxiliary stack \(Stack_{auxiliary}\) as the top of the stack. 3 while\(Stack_{main}\) is not empty do
4 Obtain the top of \(Stack_{auxiliary}\) as a new list of neighbor nodes \(Array\)
5 if\(Array\) is not empty then
6 Obtain the first element of \(Array\), press it into \(Stack_{main}\), and press the list of remaining elements into \(Stack_{auxiliary}\)
7 Query the neighbor node list of the element at the top of \(Stack_{main}\), if the list contains elements in \(Stack_{main}\), eliminate the duplicate elements from the list first and then press the list into \(Stack_{auxiliary}\); if not, press the list into \(Stack_{auxiliary}\) directly
8 else Pop the top elements of \(Stack_{main}\) and \(Stack_{auxiliary}\)
9 endif
10 if the top element of \(Stack_{main}=dst\)then
11 Obtain a path \(p_{i}=Stack_{main}\) and put it int Path
12 Pop the top elements of \(Stack_{main}\) an \(Stack_{auxiliary}\)
13 endif
14 endwhile
15 returnPath
```

**Algorithm 1**Multipath Output Algorithm

## 4 GraphSAGE-Based Performance Optimization Algorithm

According to the multi-path routing algorithm proposed in Section 3, all the shortest paths have been obtained from the source to the destination. To avoid network congestion and improve transmission efficiency, we prioritize the path with good network performance from them for data transmission. Therefore, a GraphSAGE-based performance optimization algorithm is further proposed, which selects the path with the best network performance by the node network performance based on the network topology and node features. The algorithm consists of two key steps, network label generation, and GraphSAGE-based graph representation learning. ### Network Labels Generation

Usually, data of the collected network feature only contains node network features such as traffic, delay, and packet loss rate, and lacks labels of node network performance, which makes it difficult to train the GraphSAGE model. In order to train the GraphSAGE model in a supervised manner, the collected data need to be discretized to generate network performance labels, so this paper introduces fuzzy c-means (FCM) clustering algorithm. The FCM algorithm has been widely used in neural networks, clustering, classification, and image analysis in recent years [19]. Compared with hard clustering which strictly classifies the samples into a certain class, fuzzy clustering establishes an uncertain description of the samples to the class and reflects the sample status more objectively.