# 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
Node features at each moment of the network are collected to form a network feature dataset \(X_{train}\) that contains \(n\) samples. If the samples are divided into \(l\) classes, the corresponding cluster centers are \(\{c_{1},c_{2}\cdots c_{l}\}\). The objective function of the FCM algorithm can be written as

\[\min\
olimits=\sum_{i=1}^{c}\sum_{j=1}^{n}{u_{ij}}^{m}{d_{ij}}^{2} \tag{3}\]

where \(u_{ij}\) denotes the membership value of the sample \(j\) to the cluster center \(i\);\(m\) denotes the fuzzy exponent, \(m\in[1,\infty)\), and \(d_{ij}\) denotes the Euclidean distance between the sample \(j\) and cluster center \(i\). According to [PERSON]'s theorem, the necessary condition to minimize \(J\) is

\[u_{ij}=\frac{1}{\sum\limits_{k=1}^{c}{\left(\frac{d_{ij}}{d_{k}}\right)^{\frac{ 2}{m-1}}}} \tag{4}\]

\[c_{i}=\frac{\sum\limits_{j=1}^{n}{{u_{ij}}^{m}x_{j}}}{\sum\limits_{j=1}^{n}{{u_ {ij}}^{m}}} \tag{5}\]

The values of Equations (5) and (6) are iterated until the value of \(J\) is less than the set threshold or the number of iterations reaches the maximum number of iterations. In order to determine the optimal number of clusters \(l_{best}\), the Fuzzy Partition Coefficient (FPC) proposed in [20] is used to evaluate the cluster validity. The value of FPC is between zero and one, the closer to one means the better quality of clustering and the higher similarity of samples within the class. The calculation formula of FPC is as follows:

\[FPC=\frac{1}{n}\sum\limits_{j=1}^{n}\sum\limits_{i=1}^{n}{u_{ij}^{2}} \tag{6}\]

Since the network topology proposed in this paper contains two types of nodes: routing nodes and link nodes, the number of clusters \(l\) must be greater than two. And in order to enhance the differentiation of network performance, this paper takes \(l=4\)\(\sim\)\(8\). After clustering by the FCM algorithm, although data of the network feature have been classified into \(l_{best}\) classes, it is still unable to determine which class has better network performance. Network feature contains several metrics such as traffic, delay, packet loss rate, etc., and there is often a situation in that different metrics cannot be compared uniformly in the process of network performance judgment. For example, class A has several feature metrics that are better than class B, but class B has several metrics that are better than class A, which makes it difficult to determine which class is better in terms of network performance. This paper uses a multi-metrics comprehensive evaluation method [21], which combines metrics of several network features to form a comprehensive metric as the reflection of network performance. Due to the different dimensions of network feature metrics, it is unable to directly process the network feature data numerically, so it is necessary to convert the data to nondimensional values. In this paper, the normalization method is used to process network feature metrics. Traffic is a benefit index, and the larger the value, the better the network performance. Transmission delay and packet loss rate are cost metrics, and the smaller the value, the better the network performance. Assume that \(q_{ij}\) denotes the value of metric \(j\) of the sample \(i\), \(q_{j}^{\min}\) and \(q_{j}^{\max}\) denote the minimum and maximum values of metric \(j\), respectively, where \(i=1,2,\cdots,n\); \(j=1,2,\cdots,m\). 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. The normalization process of the benefit metrics is as follows:

\[d_{ij}=\frac{q_{ij}-q_{j}^{\min}}{q_{j}^{\max}-q_{j}^{\min}} \tag{7}\]

The normalization process of the cost metrics is as follows:

\[d_{ij}=\frac{q_{j}^{\max}-q_{ij}}{q_{j}^{\max}-q_{j}^{\min}} \tag{8}\]The weighted average method is used to calculate the network performance value \(performance\), which is used to evaluate the network performance, and the larger the value the better the network performance.