Non-Euclidean Graph-Convolution Virtual Network Embedding for Space–Air–Ground Integrated Networks

Abstract

For achieving seamless global coverage and real-time communications while providing intelligent applications with increased quality of service (QoS), AI-enabled space–air–ground integrated networks (SAGINs) have attracted widespread attention from all walks of life. However, high-intensity interactions pose fundamental challenges for resource orchestration and security issues. Meanwhile, virtual network embedding (VNE) is applied to the function decoupling of various physical networks due to its flexibility. Inspired by the above, for SAGINs with non-Euclidean structures, we propose a graph-convolution virtual network embedding algorithm. Specifically, based on the excellent decision-making properties of deep reinforcement learning (DRL), we design an orchestration network combined with graph convolution to calculate the embedding probability of nodes. It fuses the information of the neighborhood structure, fully fits the original characteristics of the physical network, and utilizes the specified reward mechanism to guide positive learning. Moreover, by imposing security-level constraints on physical nodes, it restricts resource access. All-around and rigorous experiments are carried out in a simulation environment. Finally, results on long-term average revenue, VNR acceptance ratio, and long-term revenue–cost ratio show that the proposed algorithm outperforms advanced baselines.

1. Introduction

Future sixth-generation (6G) mobile technology is devoted to providing ubiquitous, anytime, anywhere intelligent information services through wireless networks [1,2]. Realizing the coverage of all corners of the earth without blind spots, especially for remote and rural areas, is an indispensable goal pursued by the future 6G networks [3]. However, depending on existing ground infrastructure alone is not enough. As illustrated in Figure 1, the space–air–ground integrated network (SAGIN) is a novel network architecture with a bright future. Through the three-dimensional interconnection, it can provide high-efficiency, stable, and reliable low-latency communication services with seamless global coverage [4,5]. Its network architecture is composed of three parts: (1) a space network, mainly composed of different orbits, such as geosynchronous orbit (GEO), low-earth orbit (LEO), and satellite clusters with different functions, e.g., communication satellites, navigation satellites, remote sensing satellites, etc.; (2) an aerial network, mainly composed of aircraft, high-altitude platforms (HAPs), and unmanned aerial vehicles (UAVs) [6], etc.; and a (3) ground network, mainly composed of traditional communication networks, e.g., mobile terminal communications, the Internet of things (IoT) [7], wireless sensors [8], ad hoc vehicles [9], etc.

In a SAGIN, each part has its specific advantages and corresponding limitations. To improve the utilization of limited resources, it is necessary to make full use of the advantages of each part in terms of coverage, flexibility, reliability, and availability [10]. However, since some nodes are always in a high-speed moving state, a SAGIN has heterogeneous and time-varying characteristics among others. Similarly, the consumption of hardware resources such as cache and computing will greatly increase. It has caused many essential problems to be solved, such as resource orchestration (RO) [11], routing scheduling [12], spectrum allocation [13], load balancing [14], etc.

It is worth noting that AI techniques [15], especially deep reinforcement learning (DRL), have long been successful and maturely applied to the field of wireless communications [16,17]. Through AI-related technologies, entities in the network can adjust and optimize adaptively according to the collected relevant feature information. This bright prospect has prompted us to introduce AI technology into SAGINs [18]. However, it requires plentiful data and resources preparation during the training process while providing comfortable intelligent services [19]. Therefore, the RO problem of SAGINs has become the focus of attention. The decision-making of resource scheduling is related to whether a SAGIN can employ the smallest resources to complete the most tasks (improving resource utilization) [20]. Through logical abstraction, network virtualization (NV) can provide intelligent and flexible RO decisions, where virtual network embedding (VNE) is the key to research [4,21]. Without recreating the hardware topology, VNE decouples resources from complex physical networks through slicing and isolation to provide elastic and flexible resource allocation strategies. Inspired by it, we convert the RO of a SAGIN into VNE problems for further research.

1.1. Pose Challenges

In the problem of RO based on VNE, how to effectively fit the complex characteristics of different domain networks and pay attention to the dynamic changes of the physical environment in real time are the keys to improving the success rate of responding to requests [4,22]. The traditional VNE algorithm uses a heuristic search algorithm, through artificial subjective embedding, which reduces the effectiveness of embedding to a certain extent and introduces serious interference errors. Some related works combine AI technology to adaptively fuse network characteristics [10,23], such as calculating node embedding probability through a fully connected layer or a convolutional layer. However, these methods neglect the non-Euclidean structure (Different from traditional aligned regular data structures, irregular graph structures such as communication networks, social networks, and knowledge graphs do not belong to the category of Euclidean structures. Therefore, they are defined as non-Euclidean structures.) of SAGIN, which makes it difficult to effectively integrate the original features of nodes [24].

In addition, with the development of Internet technologies, network security issues have aroused people’s high attention [25,26]. In particular, information resources, privacy resources, etc., if they are not protected, they can easily be maliciously attacked and obtained by criminals. However, in the VNE problem, this aspect is indeed a point that researchers tend to overlook. Especially in SAGINs, the importance of the resources of different nodes in the three-dimensional global architecture is different, and random access brings serious threats to the important resources of the nodes.

1.2. Work Contributions

To solve these problems, we propose a security-aware non-Euclidean graph-convolution VNE algorithm for SAGINs. Specifically, the contributions of this work are:

• To scientifically schedule the resources while maximizing resource utilization, we employ VNE technology to arrange multidomain resources in a SAGIN.
• Based on the excellent decision-making properties of DRL, we propose an orchestration network to calculate the embedding probability of nodes. It mainly utilizes graph convolution to capture the non-Euclidean structural information of the neighborhood, which updates its own features by fusing the feature information of neighboring nodes. In addition, the breadth-first search algorithm is employed for link mapping. Finally, a specific reward mechanism combined with the gradient descent mechanism is employed to guide positive learning.
• In view of the security issues of VNE in SAGINs, we impose security-level constraints on nodes, so that resource access is restricted. Each SAGIN node is subject to the security level, and VN requests can only access resources that meet the security constraints.
• Aiming at the actual characteristics of SAGINs, a simulation environment is modeled. Moreover, we conduct all-around rigorous experiments. In the end, the experimental results on long-term average revenue, VNR acceptance ratio, and long-term revenue–cost ratio show that the proposed algorithm outperforms advanced baselines.

1.3. Paper Organization

The other parts of this paper are organized as follows: In Section 2, we review related works. In Section 3, the problem modeling and definition is stated. In Section 4, the VNE embedding constraints and related indicators are presented. In Section 5, we introduce the flow of the proposed algorithm in detail. The results of the experiment and analysis are shown in Section 6. Finally, in Section 7, we summarize the work done and provide an outlook on future work plans.

2. Related Work

2.1. AI-Driven Space–Air–Ground Integrated Network

Networks with a single spatial dimension, such as terrestrial networks, cannot achieve full coverage and satisfactory quality of service (QoS). For example, technologies such as autonomous driving, intelligent in-vehicle applications, disaster monitoring, edge computing [27], etc., cannot be achieved alone by ground-based networks. Therefore, SAGINs have attracted widespread attention from all walks of life. Works [4,28] summarize and review SAGIN’s structure from different angles, analysis the existing works, and propose future development trends and prospects. One point worthy of attention is that they all advocate the combined utilization of AI and SAGIN to provide intelligent scalability and high QoS applications. To supplement the terrestrial network and improve the quality of experience (QoE), Kato et al. [18] proposed to combine AI technology to optimize a SAGIN and improve the performance of the network. In response to link errors, a series of concurrent data uploading, and computing offloading problems caused by frequent requests for intelligent services in SAGIN, Gu et al. [14] proposed a coding storage and computing system that was combined with AI (CSC-AI). This framework could effectively accelerate the distributed AI calculation in the SAGIN and realize reliable retrieval services in massive data. In response to the problem that the enhanced Internet of vehicles in edge computing relies heavily on the connectivity of infrastructure, which makes remote areas prone to failures, Yu et al. [29] proposed a SAGIN framework (EC-SAGIN) that could support edge computing in combination with deep learning, which used AI-driven algorithms to make intelligent decisions. In addition, there have also been a large number of technologies that apply AI-driven SAGINs to various fields for this bright prospect [10,30].

AI technology has brought many driving forces to the development of SAGINs, and it has significantly increased the scalability of services and the QoS of users. This promising prospect has prompted many hardworking researchers to devote themselves to this research career. Similarly, this is also the focus of our work and research.

2.2. Virtual Network Embedding Algorithm

Because of its flexibility, the VNE algorithm can overcome the resistance of the network to the dynamic variation of the architecture, so it is widely applied in the RO problem of physical networks [21]. Unlike other works, Chowdhury et al. [31] treated node embedding and link embedding as a whole process and obtained the mapping algorithm by relaxing the constraints. Taking the resource weight of nodes as heuristic information, Cheng et al. [32] proposed a VNE algorithm based on NodeRank, which preferentially allocated physical nodes with sufficient resources. In our previous work [33], based on a genetic algorithm to map the nodes and links, the node mapping was separated from the link mapping process. However, such traditional search algorithms utilize a heuristic search through artificial subjective embedding, which bring serious interference error to the prediction process to a certain extent [18]. In addition, AI technology can adaptively fit the original characteristics of the data, bringing promising developments to tasks such as prediction and classification. To dynamically adapt to the underlying structure of the physical network, Yao et al. [34] proposed an algorithm combining reinforcement learning to assist continuous decision (CDRL) to dynamically update the embedded decision.

Considering the advantages of the DRL paradigm for interacting with the environment, some of our previous works [10,23] utilized convolutional neural networks as the agent to perform VNE (Conv-VNE). They captured the local neighborhood relationship through the movement of the convolution kernel but ignored the graph structure relationship of the nodes in the physical network. Moreover, this discrete convolution had difficulties maintaining the translation invariance in the non-Euclidean structure of the SAGIN [24]. Therefore, this paper uses graph convolution [35] to fully capture the graph structure information of the nodes in a SAGIN and update its characteristics by fusing the neighborhood information. It makes full use of the rich node information in the network and obtains more accurate embedding probabilities, further improving the embedding success rate of virtual networks over previous work.

2.3. Security-Aware VNE Algorithm

There are few studies on the security of VNE, which have gradually attracted people’s attention in recent years. Aiming at the security vulnerabilities in the embedding process, Lin et al. [36] manually formulated security constraints and solved the problem in a physically isolated manner. Zhang et al. [37] solved the security problem of the embedding process by adding a virtual layer to the physical network and evaluating the importance of physical nodes through information entropy by the Technique for Order Preference by Similarity to an Ideal Solution (TOPSIS) method. However, the above methods lacked a sufficient consideration of node security, did not take security attributes as important information of the embedding process, and only embedded them through subjectively formulated conditions, which limited the full consideration of security issues. Therefore, in this work, we carefully impose security-level constraints on all network nodes and utilize them as important training information in the embedding process, so that users can only access resources that meet the constraints. Compared with previous VNE works, this work further improves the security of resource allocation.

3. Problem Modeling and Definition

In this section, the modeling process of a SAGIN and the definition of the VNE problem are given in detail.

3.1. Network Modeling

Table 1. The notations of the SAGIN and VNs.

Notation		Definition
${\mathit{G}}^S$		SAGIN
${\mathit{N}}^S$	${\mathit{N}}_S^S$	Nodes of the space network
	${\mathit{N}}_A^S$	Nodes of the aerial network
	${\mathit{N}}_G^S$	Nodes of the ground network
${\mathit{E}}^S$	${\mathit{E}}_S^S$	Links of the space network
	${\mathit{E}}_A^S$	Links of the aerial network
	${\mathit{E}}_G^S$	Links of the ground network
	${\mathit{E}}_{S-A}^S$	Interlinks of the space and aerial networks
	${\mathit{E}}_{S-G}^S$	Interlinks of the space and ground networks
	${\mathit{E}}_{A-G}^S$	Interlinks of the aerial and ground networks
${\mathit{R}}^S$	${\mathit{CPU}}^S\left({\mathit{N}}^S\right)$	Computing resources of the SAGIN nodes
	${\mathit{BW}}^S\left({\mathit{E}}^S\right)$	Bandwidth resources of the SAGIN links
${\mathit{D}}^S$	${\mathit{D}}^S\left({\mathit{E}}^S\right)$	Delay constraint of the SAGIN links
${\mathit{L}}^S$	${\mathit{L}}^S\left({\mathit{N}}^S\right)$	Location of the SAGIN nodes
${\mathit{C}}^S$	${\mathit{C}}^S\left({\mathit{N}}^S\right)$	Security level of the SAGIN nodes
${\mathit{G}}^V$		VNs
${\mathit{N}}^V$		Virtual nodes of the VNs
${\mathit{E}}^V$		Virtual links of the VNs
${\mathit{R}}^V$	${\mathit{CPU}}^V\left({\mathit{N}}^V\right)$	Computing resources of the virtual nodes
	${\mathit{BW}}^V\left({\mathit{E}}^V\right)$	Bandwidth resources of the virtual links
${\mathit{D}}^V$	${\mathit{D}}^V\left({\mathit{E}}^V\right)$	Delay constraint of the virtual links
${\mathit{C}}^V$	${\mathit{C}}^V\left({\mathit{N}}^V\right)$	Security level of the virtual nodes

summarizes the notations used in the VNE-based SAGIN’s RO problem. Specifically, VNE comes from the user’s request for resource requirements to the physical network of a SAGIN, i.e., the virtual network request (VNR). The physical network is modeled as a weighted undirected graph ${\mathit{G}}^S=({\mathit{N}}^S,{\mathit{E}}^S,{\mathit{R}}^S,{\mathit{D}}^S,{\mathit{L}}^S,{\mathit{C}}^S)$, mainly composed of six parts: physical node ${\mathit{N}}^S$, physical link ${\mathit{E}}^S$, required resource ${\mathit{R}}^S$ (mainly including computing resources ${\mathit{CPU}}^S$ and bandwidth ${\mathit{BW}}^S$), the links’ delay constraints ${\mathit{D}}^S$, the nodes’ location of each domain ${\mathit{L}}^S$, and the node security level of each domain ${\mathit{C}}^S$. Moreover, in the SAGIN, the elements in the three-domain networks have similar characteristics. In VNs, the primary research entity is the virtual network, which is modeled as a weighted undirected graph ${\mathit{G}}^V=({\mathit{N}}^V,{\mathit{E}}^V,{\mathit{R}}^V,{\mathit{D}}^V,{\mathit{C}}^V)$, mainly composed of five parts: virtual node ${\mathit{N}}^V$, virtual link ${\mathit{E}}^V$, required resource ${\mathit{R}}^S=\{{\mathit{CPU}}^V,{\mathit{BW}}^V\}$, the links’ delay constraints ${\mathit{D}}^V$, and the nodes’ security ${\mathit{C}}^S$. In addition, we use lowercase bold letters to indicate specific elements. For example, ${\mathit{n}}_i^V$ represents the ith node in VN, and ${\mathit{e}}_k^V$ represents the kth link in VN. If the start node of ${\mathit{e}}_k^V$ is ${\mathit{n}}_i^V$ and the end node is ${\mathit{n}}_j^V$, it can also be expressed as ${\mathit{n}}_i^V-{\mathit{n}}_j^V$.

3.2. Problem Definition

An example of SAGIN multidomain RO based on VNE is shown in Figure 2. The virtual nodes are linked by virtual links, and the elements in the VNs have similar resource attributes as the SAGIN element. Therefore, how to efficiently allocate physical resources in the SAGIN to different VNEs according to different VNRs to embed different VNs is the considered problem of VNE in the SAGIN, i.e., resource orchestration. Correspondingly, the VNE process is defined as:

$${{\mathit{G}}^S}^{\prime }\to {\mathit{G}}^{V_i},1\le i\le \left|\mathrm{VNR}\right|,$$

(1)

where ${{\mathit{G}}^S}^{\prime }$ represents a subset of SAGIN. ${\mathit{G}}^{V_i}$ represents the virtual network generated by the ith VNR request. $\left|\mathrm{VNR}\right|$ indicates the number of virtual network requests.

At the same time, it has also been proven to be NP-hard [38]. It should be noted that multiple VNs generated by multiple VNEs can coexist in the same SAGIN, i.e., share physical resources, which come from frequent VNRs. Based on the existing physical resources in a SAGIN, how to allocate the required resource ${\mathit{R}}^S$ for different VNRs under the premise of the least consumption of ${\mathit{R}}^V$ is the foothold of our research.

4. VNE Constraints and Related Indicators

The embedding constraints and evaluation indicators of VNE are presented in this section.

4.1. Embedded Constraints

In the process of VNE, the corresponding resources are mapped from the SAGIN to VNs according to each VNR. In this process, the following constraints must be met:

(1) Nodes’ available resources in the SAGIN: For the node ${\mathit{n}}_j^S$ in the SAGIN, its $\mathit{CPU}$ resources should be enough to be allocated to all virtual nodes that want to embed it. Specifically, it is expressed as:

$$\begin{array}{c}\hfill {\mathit{CPU}}^S\left({\mathit{n}}_j^S\right)-\sum _{i=1}^{|VNR|}\sum _{\forall \left({\mathit{n}}_j^S\to {\mathit{n}}_k^{V_i}\right)}{\mathit{CPU}}^{V_i}\left({\mathit{n}}_k^{V_i}\right)\ge 0,where1\le k\le \left|{\mathit{N}}^{V_i}\right|,\end{array}$$

(2)

where $|{\mathit{N}}^{V_i}|$ represents the number of virtual nodes in ${\mathit{N}}^{V_i}$.

(2) Links’ available resources in SAGIN: For the link ${\mathit{e}}_k^S$ in the SAGIN, its $\mathit{BW}$ resources should be enough to be allocated to all virtual links that want to embed it. Specifically, it is expressed as:

$$\begin{array}{c}\hfill {\mathit{BW}}^S\left({\mathit{e}}_k^S\right)-\sum _{i=1}^{|VNR|}\sum _{\forall \left({\mathit{e}}_k^S\to {\mathit{e}}_l^{V_i}\right)}{\mathit{BW}}^{V_i}\left({\mathit{e}}_l^{V_i}\right)\ge 0,where1\le l\le \left|{\mathit{E}}^{V_i}\right|,\end{array}$$

(3)

where $|{\mathit{E}}^{V_i}|$ represents the number of virtual links in ${\mathit{E}}^{V_i}$.

(3) Nodes’ security level constraints in the SAGIN: For the node ${\mathit{n}}_j^S$ in the SAGIN, the security level $\mathit{C}$ attribute restricts the mapping of nodes. It requires that the virtual node ${\mathit{n}}_k^{V_i}$ be embedded in the physical node ${\mathit{n}}_j^S$ with a higher security level. In this way, security requirements are imposed on the node, and the security of resource scheduling is ensured. The specific implementation is through the following equation:

$$\begin{array}{c}\hfill {\mathit{C}}^S\left({\mathit{n}}_j^S\right)\ge max\left\{{\mathit{C}}^{V_i}\left({\mathit{n}}_k^{V_i}\right)\right|{\mathit{n}}_j^S\to {\mathit{n}}_k^{V_i},1\le i\le |VNR|,1\le k\le |{\mathit{N}}^{V_i}\left|\right\}.\end{array}$$

(4)

(4) Paths’ available resources in the SAGIN: For any loop-free path ${\mathit{p}}^S$ in the SAGIN, the available $\mathit{BW}$ resource is the minimum $\mathit{BW}$ of all links in that path, which is specifically expressed as:

$${\mathit{BW}}^S\left({\mathit{p}}^S\right)=mi{n}_{{\mathit{e}}_k^S\in {\mathit{p}}^S}\mathit{BW}\left({\mathit{e}}_k^S\right).$$

(5)

(5) Links’ delay limits in the SAGIN: Links in different domains of the SAGIN have different delay characteristics, and the delay of interlinks is generally greater than that of intralinks. For the link ${\mathit{e}}_k^S$ in the SAGIN, its $\mathit{D}$ should be less than that of all virtual links that want to embed it. Specifically, it is expressed as:

$$\begin{array}{c}\hfill {\mathit{D}}^S\left({\mathit{e}}_k^S\right)\le min\left\{{\mathit{D}}^{V_i}\left({\mathit{e}}_l^{V_i}\right)\right|{\mathit{e}}_k^S\to {\mathit{e}}_l^{V_i},1\le i\le |VNR|,1\le l\le |{\mathit{E}}^{V_i}\left|\right\}.\end{array}$$

(6)

4.2. Resource Consumption Indicators

As discussed above, the main purpose of VNE in the SAGIN is to respond to as many VNRs as possible and allocate physical resources reasonably and efficiently. That is, under the premise of the least physical resource loss (loss cost), it should respond to as many VNRs and generate as much revenue as possible. Therefore, we can utilize some performance indicators to measure the resource consumption of the current VNR successfully mapped to the VN, and the following are specifically used:

(1) Cost: This indicator indicates the amount of SAGIN resources consumed to respond to the VNR and successfully map the VN. It is not only related to the resources of $\mathit{CPU}$ and $\mathit{BW}$ requested in the VNR but also related to factors such as the number of link hops. For example, the longer the mapped links, the higher the cost. Therefore, it can be expressed as:

$$\begin{array}{c}\hfill \mathit{Cost}\left({\mathit{G}}^S\to {\mathit{G}}^V\right)=\alpha \sum _{{\mathit{n}}^V\in {\mathit{N}}^V}{\mathit{CPU}}^V\left({\mathit{n}}^V\right)+\beta \sum _{{\mathit{e}}^V\in {\mathit{E}}^V}hops\left({\mathit{e}}^V\right)\times {\mathit{BW}}^V\left({\mathit{e}}^V\right),\end{array}$$

(7)

where $\alpha$ and $\beta$ indicate $\mathit{CPU}$ and $\mathit{BW}$, respectively, accounting for the important proportions. We assumed that they were equally important in this work, so we set $\alpha =1$ and $\beta =1$. $hops$ denotes the number of hops of the links.

(2) Revenue: This indicator indicates the quantity of resources successfully mapped to the VN in response to the VNR, i.e., the quantity of resources requested in the VNR. It is expressed as:

$$\begin{array}{c}\hfill \mathit{Revenue}\left({\mathit{G}}^S\to {\mathit{G}}^V\right)=\alpha \sum _{{\mathit{n}}^V\in {\mathit{N}}^V}{\mathit{CPU}}^V\left({\mathit{n}}^V\right)+\beta \sum _{{\mathit{e}}^V\in {\mathit{E}}^V}{\mathit{BW}}^V\left({\mathit{e}}^V\right).\end{array}$$

(8)

4.3. Evaluation Indicators

To comprehensively evaluate the performance of the proposed VNE-based multi-domain RO algorithm in the SAGIN, we employed the following indicators for evaluation:

(1) Long-term average revenue: It is mainly expressed as the integral of long-term revenue averaged over time. In this work, according to the enlightenment of the integral definition, we discretized it into a summation form:

$$\begin{array}{c}\hfill \mathit{L}\_\mathit{R}=\underset{T\to +\infty }{lim}\frac{{\int }_{t=0}^T{\mathit{Revenue}}_t\left({\mathit{G}}^S\to {\mathit{G}}^V\right)}{T}=\underset{T\to +\infty }{lim}\frac{{\sum }_{t=0}^T{\mathit{Revenue}}_t\left({\mathit{G}}^S\to {\mathit{G}}^V\right)}{T}.\end{array}$$

(9)

(2) VNR acceptance ratio: It is mainly expressed as the ratio of the number of successfully mapped VNRs to the number of all VNRs:

$$\mathit{ACC}\_\mathit{R}=\underset{T\to +\infty }{lim}\frac{{\int }_{t=0}^T{\mathit{G}}_{ac{c}_t}^V}{{\int }_{t=0}^T{\mathit{G}}_t^V}=\underset{T\to +\infty }{lim}\frac{{\sum }_{t=0}^T{\mathit{G}}_{ac{c}_t}^V}{{\sum }_{t=0}^T{\mathit{G}}_t^V}.$$

(10)

(3) Long-term revenue–cost ratio: It is mainly expressed as the ratio of long-term revenue to long-term cost:

$$\begin{array}{c}\hfill \mathit{L}\_\mathit{R}/\mathit{L}\_\mathit{C}=\underset{T\to +\infty }{lim}\frac{{\int }_{t=0}^T{\mathit{Revenue}}_t\left({\mathit{G}}^S\to {\mathit{G}}^V\right)}{{\int }_{t=0}^T{\mathit{Cost}}_t\left({\mathit{G}}^S\to {\mathit{G}}^V\right)}=\underset{T\to +\infty }{lim}\frac{{\sum }_{t=0}^T{\mathit{Revenue}}_t\left({\mathit{G}}^S\to {\mathit{G}}^V\right)}{{\sum }_{t=0}^T{\mathit{Cost}}_t\left({\mathit{G}}^S\to {\mathit{G}}^V\right)}.\end{array}$$

(11)

It should be noted that the long-term average revenue implies the actual quantity of resources requested by the VNR. Similar to Equation (9), the long-run average cost is defined as the integral of the long-run cost over time, as shown in Equation (12). It implies the total quantity of resources consumed by the SAGIN to allocate resources in the whole process of VNE. Therefore, the long-term average revenue–cost ratio is equivalent to the resource utilization of the network, which is an intuitive and meaningful indicator.

$$\begin{array}{c}\hfill \mathit{L}\_\mathit{C}=\underset{T\to +\infty }{lim}\frac{{\int }_{t=0}^T{\mathit{Cost}}_t\left({\mathit{G}}^S\to {\mathit{G}}^V\right)}{T}=\underset{T\to +\infty }{lim}\frac{{\sum }_{t=0}^T{\mathit{Cost}}_t\left({\mathit{G}}^S\to {\mathit{G}}^V\right)}{T}.\end{array}$$

(12)

Theorem 1.

The improvement of the long-term average revenue $\mathit{L}\_\mathit{R}$ and VNR acceptance ratio $\mathit{ACC}\_\mathit{R}$ promotes the improvement of the SAGIN’s resource utilization $\mathit{L}\_\mathit{R}/\mathit{L}\_\mathit{C}$ and then reaches a maximum value.

Proof of Theorem 1.

According to Equations (7) and  (9), $\mathit{L}\_\mathit{R}$ is further expressed as:

$$\mathit{L}\_\mathit{R}=\underset{T\to +\infty }{lim}\frac{\sum _{{\mathit{n}}^V\in {\mathit{N}}^V}{\mathit{CPU}}^V\left({\mathit{n}}^V\right)+\sum _{{\mathit{e}}^V\in {\mathit{E}}^V}{\mathit{BW}}^V\left({\mathit{e}}^V\right)}{T},$$

(13)

According to Equations (10) and (13), during a certain period, the T and the number of VNRs ${\mathit{G}}_t^V$ are constant. Therefore, it can be inferred that the improvement of $\mathit{L}\_\mathit{R}$ and $\mathit{ACC}\_\mathit{R}$ comes from the better utilization of the SAGIN’s node and link resources, that is, the increase in the number of successfully addressed VNRs. In turn, it means that the resource fragmentation of the SAGIN during the RO process is significantly reduced. For example, for a ${\mathrm{VNR}}_i$ requesting 10 CPU resources, a physical node with 20 CPU resources generates more fragmented resources than a physical node with 40 CPU resources. The more fragmented resources, the more physical resources are wasted, which leads to a low $\mathit{L}\_\mathit{R}$ and $\mathit{ACC}\_\mathit{R}$.

Therefore, after the above inference, the increase of the values of $\mathit{L}\_\mathit{R}$ and $\mathit{ACC}\_\mathit{R}$ reflect the reduction of the resource fragmentation phenomenon of the SAGIN, which promotes the improvement of resource utilization. Finally, all three reach the optimal value.    □

5. The Proposed Algorithm

In this section, we introduce in detail how the proposed novel VNE algorithm arranges resources for the SAGIN. The first step that needs to be done is data preprocessing, which extracts features from the SAGIN to construct a feature matrix. Afterward, the embedding process is carried out, which mainly includes node embedding and link embedding. Based on the excellent decision-making properties of DRL, we propose an orchestration network to calculate the embedding probability of the nodes. Furthermore, we utilize a breadth-first search (BFS) to obtain the embedded links.

5.1. Data Preprocessing

The purpose of AI-driven algorithms is to provide intelligent decision-making in a real environment, which requires batch data to undergo many epochs of training to extract potentially more accurate and rich information. Therefore, we need to extract the underlying features of the SAGIN in each epoch. In addition, the difference between different periods reflects the time-varying characteristics of the SAGIN.

In this work, we extracted five types of network attributes for each node of each domain in the SAGIN to construct a feature matrix, which served as the state input of the subsequent DRL-based orchestration network. These attributes were: ${\mathit{CPU}}^S$, ${\mathit{C}}^S$, $\mathit{SUM}\_{\mathit{BW}}^S$, $\mathit{SUM}\_{\mathit{D}}^S$, $\mathit{A}\_{\mathit{Dis}}^S$, the first two of which were introduced before, and the other three are described as follows:

• $\mathit{SUM}\_{\mathit{BW}}^S$ represents the sum of the bandwidth of the links between the nodes connected to the current node of interest in all domains of the SAGIN. It should be noted that these links not only include interlinks but also intralinks. In this way, we can take into account the multidomain characteristics of the SAGIN at the same time, not only paying attention to the local characteristics within the domain but also the global characteristics between the domains. This can well describe the comprehensive information of the SAGIN. Let ${\mathit{e}}_{ij}^S$ denote the link connected to ${\mathit{n}}_i^S$, then this attribute is specifically expressed as:

  $$\begin{array}{c}\hfill \mathit{SUM}\_{\mathit{BW}}^S\left({\mathit{n}}_i^S\right)=\sum _{\forall {\mathit{e}}_{ij}^S\in {\mathit{E}}^S}{\mathit{BW}}^S\left({\mathit{e}}_{ij}^S\right).\end{array}$$

  (14)
• $\mathit{SUM}\_{\mathit{D}}^S$ represents the sum of the delay constraint of the links between nodes connected to the current node of interest in all domains of the SAGIN. Similarly, it can be expressed as:

  $$\mathit{SUM}\_{\mathit{D}}^S\left({\mathit{n}}_i^S\right)=\sum _{\forall {\mathit{e}}_{ij}^S\in {\mathit{E}}^S}{\mathit{D}}^S\left({\mathit{e}}_{ij}^S\right).$$

  (15)
  It is worth noting that the larger its value, the more serious the delay phenomenon around the current node.
• $\mathit{A}\_{\mathit{Dis}}^S$ represents the average distance to nonembedded nodes, which is mainly determined by the distance between all connected points and the number of hops of the links, and is specifically expressed as:

  $$\mathit{A}\_{\mathit{Dis}}^S\left({\mathit{n}}_j^S\right)=\frac{{\sum }_{\forall {\mathit{e}}_{ij}^S\in {\mathit{E}}^S}{\parallel {\mathit{L}}^S\left({\mathit{n}}_i^S\right)-{\mathit{L}}^S\left({\mathit{n}}_j^S\right)\parallel }_2}{hops\left({\mathit{e}}_{ij}^S\right)+1},$$

  (16)

  where ${\mathit{n}}_j^s$ indicates the nonembedded node and $\parallel$ indicates the Euclidean distance (The Euclidean distance between two points $\mathit{x}=(x_1,x_2,x_3)$ and $\mathit{y}=(y_1,y_2,y_3)$ in a three-dimensional space is $E_{dis}(\mathit{x},\mathit{y})=\sqrt{{(x_1-y_1)}^2+{(x_2-y_2)}^2+{(x_3-y_3)}^2}$.).

When the node ${\mathit{n}}^V$ of VNs is embedded in the physical node ${\mathit{n}}^S$ in the SAGIN, the larger $\mathit{SUM}\_{\mathit{BW}}^S$ is, the more bandwidth can be provided. The larger $\mathit{SUM}\_{\mathit{D}}^S$ is, the more serious the delay effect. The larger $\mathit{A}\_{\mathit{Dis}}^S$ is, the more resources are consumed in the embedding process and the more serious the delay effect is.

To speed up the solution speed of the subsequent depth model’s gradient backpropagation and the model’s convergence speed, the extracted features need to be normalized:

$$X^{\prime }=Normalization\left(X\right).$$

(17)

Therefore, we can obtain the normalized attribute features ${\mathit{CPU}}^{\prime S}$, ${\mathit{C}}^{\prime S}$, $\mathit{SUM}\_{\mathit{BW}}^{\prime S}$, $\mathit{SUM}\_{\mathit{D}}^{\prime S}$, $\mathit{A}\_{\mathit{Dis}}^{\prime S}$. Combining these attributes, the obtained feature matrix ${\mathit{A}}^S$ of the preprocessed network attributes is:

$$\begin{array}{cc}\hfill {\mathit{A}}^S& =\left\{{\mathit{CPU}}^{\prime S},{\mathit{C}}^{\prime S},\mathit{SUM}\_{\mathit{BW}}^{\prime S},\mathit{SUM}\_{\mathit{D}}^{\prime S},\mathit{A}\_{\mathit{Dis}}^{\prime S}\right\}\hfill \\ & =\left[\begin{array}{ccc}{\mathit{CPU}}^{\prime S}\left({\mathit{n}}_1^S\right)& \dots & {\mathit{CPU}}^{\prime S}\left({\mathit{n}}_n^S\right)\\ {\mathit{C}}^{\prime S}\left({\mathit{n}}_1^S\right)& \dots & {\mathit{C}}^{\prime S}\left({\mathit{n}}_n^S\right)\\ \mathit{SUM}\_{\mathit{BW}}^{\prime S}\left({\mathit{n}}_1^S\right)& \dots & \mathit{SUM}\_{\mathit{BW}}^{\prime S}\left({\mathit{n}}_n^S\right)\\ \mathit{SUM}\_{\mathit{D}}^{\prime S}\left({\mathit{n}}_1^S\right)& \dots & \mathit{SUM}\_{\mathit{D}}^{\prime S}\left({\mathit{n}}_n^S\right)\\ \mathit{A}\_{\mathit{Dis}}^{\prime S}\left({\mathit{n}}_1^S\right)& \dots & \mathit{A}\_{\mathit{Dis}}^{\prime S}\left({\mathit{n}}_n^S\right)\end{array}\right],\hfill \end{array}$$

(18)

where we assume that there are n nodes in the SAGIN. ${\mathit{A}}^S$ is used as the input of the node embedding model, whose columns are the network attributes of the nodes. In addition, we extract an ${\mathit{A}}^S$ in each iteration epoch to capture the time-varying characteristics of the SAGIN through its dynamic variation.

5.2. Node Embedding

Traditional VNE works employ heuristic search algorithms, which lead to unsatisfactory embedding effects, and some existing works ignore the graph structure relationship of nodes in the physical network. Therefore, we utilized the graph convolution to fully capture the graph structure information of the nodes in the SAGIN and update its own characteristics by fusing the neighborhood information, which makes full use of the rich node information in the network and obtains more accurate embedding probabilities.

In this work, we designed a DRL-based orchestration network composed of a three-layer architecture, including graph convolution network (GCN) layers, a probability layer, and a filter layer as shown in Figure 3, which is used to calculate the embedding probability of nodes. Among them, the GCN layers can well capture the spatial structure information of the node and fully fit the characteristics of the node by fusing its information and that of its adjacent points. The specific operation process is expressed as:

$${\mathit{G}}^S=\sigma \left({\tilde{\mathit{J}}}^{-\frac{1}{2}}\tilde{\mathit{H}}{\tilde{\mathit{J}}}^{-\frac{1}{2}}{\mathit{A}}^S{\mathit{W}}^S\right),$$

(19)

where ${\mathit{G}}^S$ is the output of the GCN layer, $\sigma$ is the ReLU activation function, and ${\mathit{W}}^S$ is the weight matrix. $\tilde{\mathit{H}}=\mathit{H}+\mathit{I}$, where $\mathit{I}$ is the identity matrix, $\mathit{H}$ is the adjacency matrix of nodes, and its elements are expressed as:

$${\mathit{H}}_{ij}=\left\{\begin{array}{cc}1,& {\mathit{n}}_i^S-{\mathit{n}}_j^S\in {\mathit{E}}^S,\\ 0,& {\mathit{n}}_i^S-{\mathit{n}}_j^{S}isnotexist.\end{array}\right.$$

(20)

Therefore, $\mathit{H}$ is expressed as:

$$\mathit{H}=\left[\begin{array}{cccc}{\mathit{H}}_{11}& {\mathit{H}}_{12}& \dots & {\mathit{H}}_{1n}\\ ⋮& ⋮& \ddots & ⋮\\ {\mathit{H}}_{n1}& {\mathit{H}}_{n2}& \dots & {\mathit{H}}_{nn}\end{array}\right].$$

(21)

Accordingly, $\tilde{\mathit{J}}$ is the degree matrix, and its elements can be expressed as:

$${\tilde{\mathit{J}}}_{ii}=\sum _j{\tilde{\mathit{H}}}_{ij}.$$

(22)

Theorem 2.

Traditional discrete convolution cannot maintain translation invariance on data with a non-Euclidean structure. Combined with the theoretical basis of spectral graphs (Spectral graph theory is the product of the combination of graph theory and linear algebra. It studies the properties of graphs by analyzing the eigenvalues and eigenvectors of certain matrices of the graph. The Laplace matrix and Fourier transformation are the core and basic concepts in spectral graph theory.), graph convolutional networks can effectively extract spatial features from topological data structures with non-Euclidean structures.

Proof of Theorem 2.

Based on the above notation, the degree matrix of the graph is the adjacency matrix $\mathit{H}$, and the degree matrix is $\mathit{J}$. Then, its Laplace matrix is defined as:

$$\mathit{L}=\mathit{J}-\mathit{H}.$$

(23)

Its normalized Laplacian matrix is defined as:

$$\mathcal{L}={\mathit{J}}^{-\frac{1}{2}}\mathit{L}{\mathit{J}}^{-\frac{1}{2}}=\mathit{I}-{\mathit{J}}^{-\frac{1}{2}}\mathit{H}{\mathit{J}}^{-\frac{1}{2}}=\mathit{U}\mathbf{\Lambda }{\mathit{U}}^T,$$

(24)

where $\mathit{U}$ is the Fourier orthonormal basis obtained by eigendecomposition (Suppose $\mathit{X}$ has n eigenvectors $\mathit{V}=\{{\mathit{v}}_1,\cdots ,{\mathit{v}}_n\}$, corresponding to eigenvalues $\mathbf{\Lambda }={\{{\lambda }_1,\cdots ,{\lambda }_n\}}^T$. Then, the eigendecomposition of $\mathit{X}$ is recorded as: $\mathit{X}=\mathit{V}diag\left(\mathbf{\Lambda }\right){\mathit{V}}^{-1}$.) of $\mathcal{L}$, and $\mathbf{\Lambda }$ is the corresponding eigenvalue matrix (diagonal matrix).

The convolved signal in the SAGIN is $\mathit{a}\in {\mathcal{R}}^n$, which is the feature vector extracted by a node in $\mathit{A}$. For $\mathit{a}$, its Fourier transform and inverse transform are:

$$\tilde{\mathit{a}}={\mathit{U}}^T\mathit{a},$$

(25)

$$\mathit{a}={\mathit{U}}^T\tilde{\mathit{a}}.$$

(26)

To transform the graph signal $g_{\theta }$ into the spectral domain, it is combined with a filter to perform a product operation in the Fourier domain to complete the graph convolution operation [39] as follows:

$$g_{\theta }\ast \mathit{a}=g_{\theta }\left(\mathit{L}\right)\mathit{a}=\mathit{U}{g}_{\theta }{\mathit{U}}^T\mathit{a},$$

(27)

where $g_{\theta }$ can be thought of as a function of the $\mathcal{L}$ eigenvectors, i.e., $g_{\theta }\left(\mathbf{\Lambda }\right)$:

$$g_{\theta }\left(\mathbf{\Lambda }\right)=\left[\begin{array}{ccc}{\theta }_1& & \\ & \ddots & \\ & & {\theta }_n\end{array}\right],$$

(28)

where ${\theta }_i$ is an arbitrary parameter similar to the weights in a neural network.

However, for the spectral convolution of graphs, there exist the following problems: (1) the computational complexity of matrix multiplication using $\mathit{U}$ is $O\left(n^2\right)$; (2) computing the eigendecomposition of the Laplacian matrix of a large graph requires a huge amount of computation. Especially for large-scale graph data in a SAGIN, it is computationally expensive. Therefore, an approximation to $g_{\theta }\left(\mathbf{\Lambda }\right)$ is obtained using a Kth-order truncation of the Chebyshev polynomial $T_k\left(\mathit{x}\right)$ [40]:

$$g_{\theta }^{\prime }\left(\mathbf{\Lambda }\right)\approx \sum _{k=0}^K{\theta }_k^{\prime }{T}_k\left(\tilde{\mathbf{\Lambda }}\right),$$

(29)

where $\tilde{\mathbf{\Lambda }}=\frac{2}{{\lambda }_{max}}\mathbf{\Lambda }-\mathit{I}$ is the eigenvector matrix scaled according to the largest eigenvalue (spectral radius) of $\mathcal{L}$. ${\theta }^{\prime }\in {\mathcal{R}}^K$ is the Chebyshev vector. Chebyshev polynomials are defined using the following recursion:

$$T_k\left(x\right)=\left\{\begin{array}{cc}1,\hfill & k=0,\hfill \\ x,\hfill & k=1,\hfill \\ 2x{T}_{k-1}\left(x\right)-T_{k-2}\left(x\right),\hfill & k\ge 2.\hfill \end{array}\right.$$

(30)

At this point, using the approximate $g_{\theta }^{\prime }$ to replace the original $g_{\theta }$, we get:

$$g_{\theta }^{\prime }\ast \mathit{a}\approx \mathit{U}\sum _{k=0}^K{\theta }_k^{\prime }{T}_k\left(\tilde{\mathbf{\Lambda }}\right){\mathit{U}}^T\mathit{a}=\sum _{k=0}^K{\theta }_k^{\prime }\mathit{U}{T}_k\left(\tilde{\mathbf{\Lambda }}\right){\mathit{U}}^T\mathit{a},$$

(31)

where $T_k\left(\tilde{\mathbf{\Lambda }}\right)$ is a kth order polynomial of $\tilde{\mathbf{\Lambda }}$ with $\mathit{U}{\tilde{\mathbf{\Lambda }}}^k{\mathit{U}}^T={\left(\mathit{U}\tilde{\mathbf{\Lambda }}{\mathit{U}}^T\right)}^k=\tilde{\mathcal{L}}$ and $\tilde{\mathcal{L}}=\frac{2}{{\lambda }_{max}}\mathcal{L}-\mathit{I}$. At this point, Equation (31) can be derived as:

$$g_{\theta }^{\prime }\ast \mathit{a}\approx \sum _{k=0}^K{\theta }_k^{\prime }{T}_k\left(\tilde{\mathcal{L}}\right)\mathit{a}.$$

(32)

An approximate spectral graph convolution can establish Kth-order neighbor dependencies but still requires Kth-order computations on $\mathcal{L}$. To reduce the cost, Kipf et al. [35] proposed to use $K=1$ and ${\lambda }_{max}=2$ to further simplify the calculation. Although only first-order neighbor dependencies can be established, stacked multilayer graph convolution can still establish Kth-order neighbor dependencies. More advantageously, it is not restricted by the Chebyshev polynomial. Then, Equation (32) can be simplified to:

$$g_{\theta }^{\prime }\ast \mathit{a}\approx {\theta }_0^{\prime }\mathit{a}+{\theta }_1^{\prime }(\mathcal{L}-\mathit{I})={\theta }_0^{\prime }\mathit{a}-{\theta }_1^{\prime }{\mathit{J}}^{-\frac{1}{2}}\mathit{H}{\mathit{J}}^{-\frac{1}{2}}\mathit{a}.$$

(33)

To suppress the number of parameters and prevent overfitting, we let $\theta ={\theta }_0^{\prime }=-{\theta }_1^{\prime }$, then Equation (33) can be further derived as:

$$g_{\theta }\ast \mathit{a}\approx \theta (\mathit{I}+{\mathit{J}}^{-\frac{1}{2}}\mathit{H}{\mathit{J}}^{-\frac{1}{2}})\mathit{a}.$$

(34)

In addition, to prevent the occurrence of a gradient explosion or vanishing phenomenon due to the instability of operator $\mathit{I}+{\mathit{J}}^{-\frac{1}{2}}\mathit{H}{\mathit{J}}^{-\frac{1}{2}}$ when the number of layers is deep, we let $\tilde{\mathit{H}}=\mathit{H}+\mathit{I}$ and ${\tilde{\mathit{J}}}_{ii}={\sum }_j{\tilde{\mathit{H}}}_{ij}$. Then, this operator is derived as:

$$\mathit{I}+{\mathit{J}}^{-\frac{1}{2}}\mathit{H}{\mathit{J}}^{-\frac{1}{2}}={\tilde{\mathit{J}}}^{-\frac{1}{2}}\tilde{\mathit{H}}{\tilde{\mathit{J}}}^{-\frac{1}{2}}.$$

(35)

When we batch-process the data of multiple groups of nodes, let ${\mathit{A}}^S$ be the graph signal matrix and ${\mathit{W}}^S$ be the parameter matrix of $\theta$; then, we obtain the convolution operation of the graph convolution layer proposed in Equation (19):

$${\mathit{G}}^S=\sigma \left({\tilde{\mathit{J}}}^{-\frac{1}{2}}\tilde{\mathit{H}}{\tilde{\mathit{J}}}^{-\frac{1}{2}}{\mathit{A}}^S{\mathit{W}}^S\right),$$

(36)

where ${\mathit{G}}^S$ is the output of the GCN layer and $\sigma$ is the ReLU activation function.

To sum up, at each layer we obtain and fuse the first-order neighbor information of each node. In the SAGIN, through multilayer graph convolution stacking, we can effectively fuse the information of Kth-order neighbors and then comprehensively consider the local and global information of the nodes.    □

The probability layer was mainly used to map the aggregated features obtained through the GCN layers to the embedding probability of the nodes in the SAGIN, which was specifically expressed as:

$${\mathit{P}}_i^S=\frac{{\mathit{G}}_i^S}{{\sum }_{j=1}^n{\mathit{G}}_j^S},$$

(37)

where ${\mathit{P}}_i^S$ indicates the embedding probability of node i. For each SAGIN node, after calculating the embedding probability, we used the cross-entropy loss to calculate its loss, which jointly guided the learning of the model.

$$Los{s}_i=-{\mathit{G}}_i^{S}log\left({\mathit{P}}_i^S\right).$$

(38)

The filtering layer was mainly used to filter out the nodes that did not meet the conditions according to the relevant constraints in Section 4.1 and finally sort the nodes that met the constraints in descending order according to their embedding probability.

5.3. Link Embedding

After node embedding, we obtained the nodes in the SAGIN that satisfied both the constraints of $\mathit{CPU}$ resource and the $\mathit{C}$ security level and also obtained the embedding probability ranking of these nodes. In addition, according to these nodes, we adopted the BFS strategy to embed links under the condition of satisfying the $\mathit{BW}$ and $\mathit{D}$ constraints in Section 4.1. To be clear, the orchestration network was the agent modeled by DRL. Node embedding and link embedding were two-phase actions adopted by the agent.

To further clarify the adopted DRL algorithm, it was necessary to model it as a Markov decision process (MDP). The state was the extracted feature matrix as shown in Equation (18). The agent was the proposed orchestration network. The actions taken were node embedding and link embedding. Therefore, the resource allocation of the SAGIN was modeled as the following MDP process:

$$MDP=<{\mathit{A}}^S,\mathrm{orchestration}\mathrm{network},\{nodeembedding,linkembedding\},Reward>.$$

(39)

In addition, the time complexity of the proposed algorithm needed to be analyzed. Let n represent the number of nodes of the SAGIN. Then, the complexity of extracting ${\mathit{A}}^S$ during data preprocessing was $O\left(n\right)$. When embedding nodes, the time complexity through the proposed orchestration network was $O\left(n^2\right)$. In addition, ${\mathit{A}}^S$ needed to be re-extracted when each VNR arrived, so the time complexity was $O\left(\right|VNR|\times n^2)$. Therefore, the overall complexity of the algorithm was $O(n+n^2+|VNR|\times n^2)$.

5.4. Training and Testing

In the training process, to better guide decision-making, since $\mathit{L}\_\mathit{R}/\mathit{L}\_\mathit{C}$ could well reflect the resource utilization of the underlying physical network nodes and links, we used that indicator as the reward mechanism of the agent. If the current decision-making reward was large, it implied that the current decision-making could bring benefits. On the contrary, it was necessary to adjust the mapping decision. In addition, the cross-entropy loss combined with the reward mechanism was used for backpropagation to guide the embedding training process of the orchestration network. We repeated this process until all VNRs requests were allocated or the SAGIN was unable to satisfy subsequent VNRs. It should be noted that in a VNR, only all requested nodes, links, and corresponding attributes completed the mapping, and the current VNR was considered to be completed. The specific training flow is presented in Algorithm 1. The test process of the network only used the forward propagation process and did not perform gradient backpropagation and parameter update. The other processes were similar to the training process and are not repeated here.

Theorem 3.

In the orchestration network, the loss function and reward mechanism jointly guide positive learning.

Proof of Theorem 3.

In this work, the update of the gradient settings were combined with the reward mechanism as follows:

$$Loss:=Loss-\mu ·Los{s}^{\prime }·Reward,$$

(40)

where $\mu$ is the learning rate of the orchestration network. In a neural network, the learning rate guides the direction and step size of the loss reduction. If $\mu$ is too large, the optimal point is missed. If $\mu$ is too small, the optimization time cost is high. Accordingly, its value selection is more critical; after verification, we set it to 0.005. $Los{s}^{\prime }$ is the derivative of $Loss$. It should be noted that the MDP process promotes the agent to optimize towards the direction of high reward. In addition, the parameter optimization mechanism of the neural network promotes the optimization of the orchestration network in the direction of gradient descent. Therefore, in the gradient descent optimization process of the model, the reward mechanism jointly participates in the optimization and guides the model to learn in the direction of high revenue and low loss.    □

Algorithm 1: The training flow

6. Experiment

In this section, to evaluate our proposed algorithm, simulation experiments of a real environment were carried out. In addition, we conducted a comprehensive analysis of the scientific research from various angles.

6.1. Simulation Environment and Dataset Configuration

The detailed configuration information of the simulation environment is recorded in

Table 2. Detailed configuration information of the simulation environment.

Simulation Environment	Configuration Information
Number of ${\mathit{N}}_S^S$	10
Number of ${\mathit{N}}_A^S$	30
Number of ${\mathit{N}}_G^S$	60
Number of ${\mathit{E}}^S$	581
${\mathit{CPU}}_S^S$	20–40 TFLOPS
${\mathit{CPU}}_A^S$	20–40 TFLOPS
${\mathit{CPU}}_G^S$	50–100 TFLOPS
${\mathit{C}}^S$	1–5 Sl
${\mathit{BW}}^S$	50–100 Mbps
${\mathit{D}}^S\left({\mathit{E}}_S^S\right)$	20–40 ms
${\mathit{D}}^S\left({\mathit{E}}_A^S\right)$	10–30 ms
${\mathit{D}}^S\left({\mathit{E}}_G^S\right)$	1–20 ms
${\mathit{D}}^S\left({\mathit{E}}_{S-A}^S\right)$	40–60 ms
${\mathit{D}}^S\left({\mathit{E}}_{S-G}^S\right)$	40–60 ms
${\mathit{D}}^S\left({\mathit{E}}_{A-G}^S\right)$	40–60 ms

, we randomly generated 100 SAGIN nodes, which were divided into ${\mathit{N}}_S^S$, ${\mathit{N}}_A^S$, and ${\mathit{N}}_G^S$ according to a 1:3:6 ratio. Moreover, according to a connection probability of $12.3\%$, 581 links were randomly generated, including interlinks and intralinks.

In the allocation of nodes’ computing resources, the computing of the space network nodes was randomly allocated 20 TFLOPS to 40 TFLOPS, the computing of the aerial network nodes was randomly allocated 20 TFLOPS to 40 TFLOPS, and the computing of the ground network nodes was randomly allocated 50 TFLOPS to 100 TFLOPS. The security level (Sl) of all nodes was randomly assigned from zero to five. In the allocation of link bandwidth resources, all interlinks and intralinks were randomly allocated 50 Mbps to 100 Mbps. In the allocation of link delay, the intralinks in the space network was randomly allocated 20 ms to 40 ms, the intralinks in the aerial network were randomly allocated 10 ms to 30 ms, and the intralinks in the ground network were randomly allocated 1 ms to 20 ms. In addition, the delay of all interlinks was randomly assigned to 40 ms to 60 ms.

Moreover, 2000 VNRs were randomly generated for model learning, where the first 1000 were for the training set and the last 1000 were for the testing set. The specific configuration of the VNRs is recorded in

Table 3. Detailed configuration information of the VNRs.

VNR	Configuration Information
Total number	2000
Number (training)	1000
Number (testing)	1000
${\mathit{CPU}}^V\left({\mathit{N}}^V\right)$	1–20 TFLOPS
${\mathit{C}}^V\left({\mathit{N}}^V\right)$	0–5 Sl
${\mathit{BW}}^V\left({\mathit{E}}^V\right)$	1–20 Mbps
${\mathit{D}}^V\left({\mathit{E}}^V\right)$	1–50 ms

. The computing of the virtual nodes was randomly assigned 1 TFLOPS to 20 TFLOPS, the security of the virtual nodes was randomly assigned to an Sl of zero to five, the bandwidth of the virtual links was randomly assigned 1 Mbps to 20 Mbps, and the delay of the virtual links was randomly assigned 1 ms to 50 ms. It needs to be stated that the number of requested nodes in each VNR was randomly selected between 2 and 10.

6.2. Training Performance

With the advancement of the orchestration network training process, the variation process of the evaluation indicators $\mathit{L}\_\mathit{R}$, $\mathit{ACC}\_\mathit{R}$, and $\mathit{L}\_\mathit{R}/\mathit{L}\_\mathit{C}$ is shown in Figure 4. We can find that with the iteration of the training epoch, it gradually fit the characteristics of the underlying network and eventually converged quickly. Therefore, the convergence of the training process of the model was effective.

6.3. Flexible Decision-Making

We limited the delays to 1–50 ms, 1–40 ms, 1–30 ms, and 1–20 ms, respectively, and generated corresponding VNRs to verify the flexibility of the orchestration network’s decision-making for changes in demand. From a theoretical point of view, as the demand delay decreases (50 ms → 20 ms), the number of SAGIN links that can meet the conditions decreases, so the number of successfully mapped VNRs also decreases accordingly. According to Equation (9), $\mathit{L}\_\mathit{R}$ should be reduced; according to Equation (10), $\mathit{ACC}\_\mathit{R}$ should be reduced; according to Equation (11), $\mathit{L}\_\mathit{R}/\mathit{L}\_\mathit{C}$ is jointly determined by $\mathit{L}\_\mathit{R}$ and $\mathit{L}\_\mathit{C}$, so its value fluctuates little. As a result, the experimental results in

Table 4. Average performance under VNR delay demand changes.

${\mathit{D}}^{\mathit{V}}$	$\mathit{L}\_\mathit{R}$	$\mathit{ACC}\_\mathit{R}$	$\mathit{L}\_\mathit{R}/\mathit{L}\_\mathit{C}$
1–50 ms	$1937.1272\pm 0.0001$	0.874	$0.3752\pm 0.0001$
1–40 ms	$1884.2228\pm 0.0001$	0.848	$0.3811\pm 0.0001$
1–30 ms	$1725.0045\pm 0.0001$	0.794	$0.3673\pm 0.0001$
1–20 ms	$1405.9707\pm 0.0001$	0.687	$0.4013\pm 0.0001$

were in line with the theoretical reality, and the orchestration network had a satisfactory flexibility when dealing with different VNR decisions.

6.4. Comparison with Other Related Works

The related works in

Table 5. The baselines used in comparative experiments.

Baselines	Algorithm Basis	Optimization Goal	Description
NodeRank [32]	Heuristic	Improve embedding revenue	Heuristic search algorithm, embedding based on the ranking of node resource weights
RCR-VNE [41]	Heuristic	Improve embedding revenue and VNR acceptance ratio	A heuristic algorithm based on multidimensional available resource constraints.
CDRL [34]	RL	Improve resources utilization	A reinforcement-learning-based VNE algorithm
Conv-VNE [10]	RL+DL	Improve embedding revenue and VNR acceptance ratio	A VNE algorithm based on reinforcement learning and deep learning (convolutional neural network)
SGT-VNE [24]	DRL	Improve embedding revenue and reduce embedding cost	A single-domain VNE algorithm based on spectral graph theory applied to a vehicle fog computing network

were selected for comparative experiments to verify the advantages of the proposed algorithm. The source code of all baselines was provided by the original authors, and each was run in the same experimental environment to eliminate the influence of other factors and improve rigor. In total, 1000 VNRs were utilized to verify the test performance of our proposed algorithm and other related works. The comparative experimental results are displayed in Figure 5.

From a theoretical point of view, as time goes by, the continuous embedding of VNRs that meet the demand leads to the continuous reduction of node and link resources in the SAGIN, so the number of subsequent VNRs embeddings is reduced, which leads to a decreasing trend of $\mathit{L}\_\mathit{R}$ and $\mathit{ACC}\_\mathit{R}$. Since $\mathit{L}\_\mathit{R}/\mathit{L}\_\mathit{C}$ is jointly determined by $\mathit{L}\_\mathit{R}$ and $\mathit{L}\_\mathit{C}$, it causes little fluctuation. In fact, our experimental results confirmed the theory in a practical scenario.

Furthermore, NodeRank and RCR-VNE initially performed well due to their greedy allocation based on node resource weights, but they performed poorly in the long run. Based on the characteristics of the interaction between the incentive mechanism of RL and the environment, CDRL significantly improved in various indicators. Furthermore, Conv-VNE utilized convolutional layers instead of traditional Q-table learning to better focus on local information. SGT-VNE only considered the resource allocation modeling of a single physical domain but did not fully consider the cross-physical domain scenarios. However, it took into account the modeling of non-Euclidean graph structures of physical networks, so the performance was further improved. In the long run, our proposed algorithm outperformed the other baselines. This was mainly due to the combination of the DRL paradigm, which effectively interacted with the environment while combining the graph convolution to better focus on the global topology and neighborhood information of the SAGIN. To sum up, the above experiments scientifically proved the effectiveness of the RO algorithm for security-aware non-Euclidean graph-convolution VNE in SAGIN.

7. Conclusions and Outlook

In this work, to make the RO strategy of a SAGIN more flexible, intelligent, accurate, and safe, combined with AI and VNE, we proposed a non-Euclidean graph-convolution VNE algorithm. The proposed DRL-based orchestration network integrated the node itself and neighborhood information to calculate the embedding probability of nodes, which satisfactorily fit the original characteristics of physical network nodes. Moreover, we ensured resource security was guaranteed by imposing security-level constraints on the network. Under the combined action of additional constraints, resource allocation strategies were more reasonable and reliable. Finally, we conducted scientific and rigorous experiments in a simulation environment that fit a real SAGIN, which meaningfully proved the effectiveness of the proposed algorithm.

In future work plans, we expect to pay a better attention to the dynamic properties of the SAGIN to further improve the flexibility of resource allocation decisions. In particular, the high-intensity maneuverability of UAVs will be our focus. In addition, how to more effectively explore the specific characteristics of different networks in the SAGIN is also a challenge that we will focus on in the future, which will significantly improve the performance of the VNE algorithm.