# A Routing Optimization Method for LEO Satellite Networks with Stochastic Link Failure
## 3 Optimization Method
### Improved A* (A-Star) Strategy  
We introduce the roulette wheel selection into the A* algorithm to obtain the improved A* strategy. For different paths, the strategy making the high-cost paths has non-zero probability of selection, as shown in Figure 3. In \(\mathcal{G}(c)=(\mathcal{V},\mathcal{E}(c))\), \(partpath_{r}^{ck}\subseteq path_{r}^{ck},r=1,\cdots,NM_{k}^{c}\) represents the partial of \(path_{r}^{ck}\), and \(v_{s}^{ck}\) denotes the end node that \(partpath_{r}^{ck}\) passes through. The \(\mathcal{U}_{s}=\{v_{s_{1}},\cdots,v_{s_{m}}\},v_{s_{i}}\in\mathcal{V},\ i=1, \cdots,m\) is called the reachable node set of \(v_{s}^{ck}\) when it satisfies the following conditions:  
1. \(\forall v_{s_{i}}\in\mathcal{U}_{s}\), satisfy \((v_{s_{i}},v_{s}^{ck})\
otin partpath_{r}^{ck}\) and \(s_{i}\in\mathcal{N}_{s}\).
2. \(\forall v_{i}\
otin\mathcal{U}_{s}\), satisfy \((v_{i},v_{s}^{ck})\in partpath_{r}^{ck}\) or \(i\
otin\mathcal{N}_{s}\).  
The calculation formulas for the selection probability \(P(v_{s_{i}})\) and cumulative probability \(Q(v_{s_{i}})\) of any node \(v_{s_{i}}\in\mathcal{U}_{s}\) are as follows:  
\[P(v_{s_{i}})=\frac{\frac{1}{h(v_{s_{i}})}}{\sum_{v_{s_{i}}\in\mathcal{U}_{s}} \frac{1}{h(v_{s_{i}})}},i=1,\cdots,m \tag{27}\]  
\[Q(v_{s_{i}})=\sum_{j=1}^{i}P(v_{s_{i}})\ \ i=1,\cdots,m \tag{28}\]  
\[h(v_{s_{i}}){=}h_{1}(v_{s_{i}})+h_{2}(v_{s_{i}}) \tag{29}\]Among them, \(h(v_{s_{i}})\) represents the estimated cost of \(path_{r}^{c,k}\), \(h_{1}(v_{s_{i}})\) represents the actual cost of \(partpath_{r}^{c,k}\), and \(h_{2}(v_{s_{i}})\) represents the estimated cost between \(v_{s_{i}}\) and \(v_{q}^{c,k}\). The calculation formula is:  
\[h_{1}(v_{s_{i}}) =\sum\
olimits_{i,j}(\delta_{(i,j)}^{partpath_{r}^{c,k}}d_{i,j}^{ c}) \tag{30}\] \[h_{2}(v_{s_{i}}) =d_{s_{i},q}^{c} \tag{31}\]  
In particular, define \(Q(v_{s_{0}})\)=0. When \(v_{s_{a}}\in\mathcal{U}_{s}\) satisfies the following formula, choose \(v_{s_{a}}\) as the next path node:  
\[Q(v_{s_{a-1}})<z_{s}<Q(v_{s_{a}}) \tag{32}\]  
where the random variable \(z_{s}\sim\mathrm{U}(0,1)\).  
Before implementation of the improved A* strategy, an Open List and a Closed List ought to be established, which are used to record the nodes that need to be and have been investigated, respectively. The flow of the improved A* strategy is shown in Algorithm 2.  
```
Input: start and end node Output: routing connection
1 initialization: put the first node into the Open List;
2 whilethe Open List is nonempty and \(v_{k}^{c,end}\) is not in the Open Listdo
3 generate \(z_{s}\) and calculate the cumulative probability \(Q(v_{s_{i}})\);
4 select \(v_{s_{u}}\) from the Open List as the current node \(a\) according to Equation (32);
5 add \(a\) to the Close List and remove it from the Close List;
6 calculate the \(\mathcal{U}_{s}\) of node \(a\) and generate a set of child nodes;
7 foreach child node \(b\)do
8 ifb in the Close Listthen
9 discard it;
10
11 else
12 ifb in the Open Listthen
13 iftheh value calculated by node \(a\) is smallerthen
14 update \(h\) value and set parent node of \(b\) as \(a\);
15
16 end if
17
18 else
19 add \(b\) into the Open List and calculate its \(h\) value;
20 set the parent node of \(b\) as \(a\);
21
22 end if
23
24 end if
25
26 end if
27
28 end for
```  
**Algorithm 2** The improve A* strategy.  
Figure 3: Improved A* strategy schematic diagram.