# A Dynamic Service Reconfiguration Method for Satellite-Terrestrial Integrated Networks
## 4 Algorithm Design and Description
### Basic Steps of FQGA-SR  
The basic steps of the service migration and reconfiguration algorithm based on fuzzy quantum genetic algorithm (FQGA-SR) are as follows:  
(1) Establish the shortest path matrix \(\mathbb{S}\):  
Firstly, the input matrix \(\mathbb{S}\) of FQGA-SR is established, which is used to represent the association relationship between any two substrate nodes in the substrate network \(G_{sn}\), the \(i\)th row and \(j\)th column of the matrix \(\mathbb{S}\) represent the minimum delay between node \(n_{i}\) and node \(n_{j}\) of deployed SFCs. The matrix \(\mathbb{S}\) can be obtained by calculating the shortest path between two nodes using the \(k\)-Dijkstra algorithm. (2) FQGA-SR algorithm initialization:  
The population and individuals are initialized, and the number of observation sequences is set as \(X_{c}\), the qubit probability space is \(N_{iche}\), the coding length of the chromosome qubit is \(K\), and the population size is \(M\). The initial population and individuals are constructed by quantum bit coding, and the chromosomes are expressed in the form of quantum superposition state, which can greatly improve the diversity of population genotypes on the premise of maintaining the population size. Let \(N(t)=\left\{N_{1}^{(t)},N_{2}^{(t)},\ldots,N_{M}^{(t)}\right\}\) represent the \(t\)th generation of the subpopulation, in which the individual \(N_{m}^{(t)}\) is initialed by Equation (13), and each qubit may be in \(|0\rangle\),\(|1\rangle\), with their entangled states between \(|0\rangle\) and \(|1\rangle\), i.e., \(|\psi\rangle=\alpha|0\rangle+\beta|1\rangle\), where \(\alpha\) and \(\beta\) are the complex coefficient representing the probability amplitude of qubits. In the above quantum bit coding model, the \(i\)th qubits represent the substrate node \(n_{i}\in N_{sn}\) states carrying VNF \(f\in F\), i.e., \(|0\rangle\) represents that node \(n_{i}\) does not carry VNF, and \(|1\rangle\) represents the node \(n_{i}\) carried VNF \(f\in F\). In the initialization phase, let all qubits have the same state, that is \(\alpha_{mi}^{(0)}=\beta_{mi}^{(0)}=1/\sqrt{2}\). \[N_{m}^{(0)}=\left[ \begin{array}{c}\alpha_{mi}^{(0)}\\ \beta_{m1}^{(0)}\end{array} \right| \begin{array}{c}\alpha_{m2}^{(0)}\\ \beta_{m2}^{(0)}\end{array} \right| \begin{array}{c}\ldots\\ \cdots\\ \beta_{mK}^{(0)}\end{array} \right]=\left[ \begin{array}{c}1/\sqrt{2}\\ 1/\sqrt{2}\end{array} \right| \begin{array}{c}1/\sqrt{2}\\ 1/\sqrt{2}\end{array} \right| \begin{array}{c}\ldots\\ \cdots\\ 1/\sqrt{2}\end{array} \right],\ m=1,2,\ldots M \tag{13}\]  
Subpopulation evolution:  
The FL algorithm fuzzies the discrete data in the form of membership degree and can define the discrete probability function with a single fuzzy set, so as to obtain more accurate output results efficiently. Therefore, using the FL algorithm to describe the population and individuals of quantum bit coding with probability amplitude is helpful to obtain the evolution of optimized subpopulation. Let \(H_{1}\) represent the ratio between the number of \(|1\rangle\) in the subpopulation and the qubits coding length \(K\), which can be expressed as Equation (14):  
\[H_{1}=\left|\left( \begin{array}{c|c}\alpha_{mi}^{(0)}\\ \beta_{m1}^{(0)}\end{array} \right| \begin{array}{c}\alpha_{m2}^{(0)}\\ \beta_{m2}^{(0)}\end{array} \right| \begin{array}{c}\ldots\\ \cdots\end{array} \right| \begin{array}{c}\alpha_{mK}^{(0)}\\ \beta_{mK}^{(0)}\end{array} \right)\right|_{m}^{1}/K \tag{14}\]  
Fitness function \(Fit(X_{c})\) can be expressed as: \(Fit(X_{c})=\left[Obj\right]^{-1}\), where the \(Obj\) refers to the optimal objective, that is, to minimize end-to-end delay and migration cost. The fitness function definition \(H_{2}\), which is used to measure the current closely related to fitness function, can be expressed as Equation (15):  
\[H_{2}=\frac{Fit(X_{c})-Fit^{*}(X_{b})}{\left\|\max(Fit(X_{c}))-\min(Fit(X_{c}) )\right\|} \tag{15}\]  
where \(Fit^{*}(X_{b})\) is the highest value of the fitness function.