## 4 Mathematical Model  
In this section, we describe the VNF placement problem and related constraints in SAGIN scenarios in detail. SFC:  
We assume that the set of VNFs is \(V=\{v_{1},v_{2},...,v_{n}\}\), which consists of \(n\) different VNFs. Network Service \(s=\{v_{1},v_{2},...,v_{m}\}\) is composed of \(m\) VNFs, where \(v\in V\). Network systems:  
Firstly, we need to define a network system topology graph \(G=(H,L)\), assuming that there are \(n\) host servers (containing ground, aircraft, and satellite servers). The hosts can be represented as \(H=\{h_{1},h_{2},...,h_{n}\}\), the set of available computing resources owned by  
Figure 3: Example of SFC placement in SAGIN scenario. these hosts is \(R\), and the set of links between the hosts is defined as \(L,b_{i}\), and \(l_{i}^{s}\) denotes the bandwidth and delay of link \(i\), respectively. Placement strategy:  
The VNFs of the service chain need to be placed as optimally as possible in the host servers, and we use \(x_{vh}\) to indicate whether VNF \(v\) is placed in host \(h\):  
\[x_{vh}=\left\{ \begin{array}{ll}1&\text{\emph{VNF $v$ in host $h$}}\\ 0&\text{\emph{otherwise}}\end{array} \right.\]  
\(y_{h}\) represents whether host \(h\) is occupied or not:  
\[y_{h}=\left\{ \begin{array}{ll}1&\text{\emph{existence VNF in host $h$}}\\ 0&\text{\emph{otherwise}}\end{array} \right.\]  
The usage of link \(i\) is denoted as  
\[z_{i}=\left\{ \begin{array}{ll}1&\text{\emph{data packet passes through link $i$}}\\ 0&\text{\emph{otherwise}}\end{array} \right.\]  
Energy consumption:  
Energy consumption is divided into two parts during VNF placement: one is required for the hosts to process tasks, and the other is the energy consumption for link data transmission. The energy consumption of hosts is related to the number of resources it uses. We assume that \(W_{h}^{min}\) is the minimum energy required by host \(h\), and \(W_{h}^{cpu}\) is the energy needed for each \(cpu\) of \(h\); then, the total energy consumption of hosts can be expressed as  
\[energy\_cpu=\sum_{h\in H}\left(W_{h}^{cpu}\cdot\sum_{v\in s}r_{rv}\cdot x_{ vh}+W_{h}^{min}\cdot y_{h}\right), \tag{1}\]  
where \(r_{rv}\) represents the computing resources requested by VNF \(v\). The energy consumption of the links can be expressed as  
\[energy\_link=\sum_{i\in L}W_{i}^{bw}\cdot\sum_{v\in s}b_{v}^{s}\cdot x_{vh}, \tag{2}\]  
where \(W_{i}^{bw}\) is the energy consumed per bandwidth unit flowing through link \(i\). Then, the total energy consumed to provide service \(s\) can be expressed as  
\[F_{1}=energy\_cpu+energy\_link. \tag{3}\]  
After all of the VNFs about the \(s\) are placed in the host servers, the resources occupied by each host can be expressed as Equation (4). \[cpu\_occupy=\sum_{v\in s}r_{rv}\cdot x_{vh}\hskip 14.226378 pt\forall h\in H,r \in R. \tag{4}\]  
The available computing resources of the host servers are represented as  
\[cpu\_available=y_{h}\cdot a_{vh}\hskip 14.226378 pt\forall h\in H,r\in R, \tag{5}\]  
where \(a_{vh}\) denotes the available computing resources of host \(h\). During storage, the computing resources occupied by service \(s\) cannot exceed the available resources of the host. The specific equation is shown as follows:  
\[F_{2}:cpu\_occupy\leq cpu\_available. \tag{6}\]  
Bandwidth:Similarly, the deployment of VNFs also needs to meet the bandwidth constraints of the link. The bandwidth occupied by SFC \(s\) can be expressed as  
\[bw\_occupy=\sum_{v\in s}b_{v}^{s}\cdot x_{vh}. \tag{7}\]  
The bandwidth owned by link \(i\) is expressed as  
\[bw\_available=z_{i}\cdot b_{i}\hskip 14.226378 pt\forall i\in L. \tag{8}\]  
The bandwidth occupied by SFC \(s\) must not exceed the available bandwidth of each link during the placement. Therefore, the constraint is expressed as  
\[F_{3}:bw\_occupy\leq bw\_available. \tag{9}\]  
End-to-end latency:  
End-to-end delay is divided into two parts: one is the time required by the host to process the VNF, and the other is the time required by the packet during transmission.