Dispersed Computing Resource Discovery Model and Algorithm for Polymorphic Migration Network Architecture

I.   Introduction

Edge computing can effectively reduce the burden on the core network and enable real-time responsiveness. However, edge servers are unable to handle large volumes of sudden and urgent requests due to limitations in computing power, scalability and operating costs. Dispersed computing is more capable of handling such tasks. The dispersed computing architecture is fully decentralized and efficiently mobile, which leverages geographically distributed hardware to provide diverse and flexible idle resources in a collaborative and shared manner [1]. It can expand the associated wireless network devices (e.g., servers, vehicles, UAVs, portable devices, smart equipments, etc.) from basic transmission nodes to networked computing points (NCPs) available for real-time connectivity [2]. These NCPs have equal functional status and high connectivity degree of freedom, which can quickly and automatically form independent resource networks to perform computing tasks spontaneously and collaboratively. An important prerequisite for dispersed computing applications to be implemented is that the various resources in the current dispersed computing resource network can be dynamically sensed and discovered [3]. This study focuses on the optimization mechanism of distributed computing resource discovery. The main motivations include i) using the basic theory of complex networks to solve the problem of structural analysis of uncertain decentralized computing networks; ii) using an optimal decision-making model to solve the mode selection problem of dispersed computing discovery under complex spatio-temporal conditions; and iii) using a reasonable heuristic algorithm to solve the efficiency problem of schemes for dispersed computing resource discovery.

The resource discovery needs to adapt to the real-time access of available resources, that is, the resource information of each node can be grasped by others in the network through the resource information list. It can be seen that resource pool information is the key to visualizing the supply relationship between network resources, computing nodes, and potential task demands. The data exchange protocol for dispersed computing resource discovery is different from the traditional service discovery protocol (SDP). The resource information in the latter includes resource categories and addresses of the resource providers. The resource information in the former includes supported task types, resource categories, node identifiers, mode and state parameters of the network (i.e., the number of network migration cycles, the number of nodes, transmission distance between nodes, discovery mode of nodes) [3]. The key to resource discovery for dispersed computing is the construction and maintenance of the resource pool information list.

The networks of dispersed computing resources are dynamic and complex. There are many variations and the composition of the nodes is random. The establishment and maintenance of the resource pool information list will be affected by the change of the network topology. In view of these features, the studied network has properties similar to small-world networks and scale-free networks [4]. Therefore, we need to use complex network topology features to analyze the polymorphic migration properties of the resource discovery network. Additionally, the operation of the discovery mode for computing devices under time-varying conditions is strongly associated with the energy consumption of the system [5]. In other words, the establishment and maintenance of resource pool information lists also involve considerable energy costs due to frequent updates of resource information state (RIS) and massive packet delivery, which need to be continuously optimized in the operation of the dispersed computing discovery system. Since the energy consumption of resource discovery and the accuracy of RIS are opposed to each other [6], the study needs to analyze and dynamically select the resource discovery mode with the goal of total energy consumption of resource discovery under the condition of RIS accuracy. Existing studies have focused on discovery strategies for multi-mode selection to synthesize the advantages of different discovery modes [7]–[11]. However, these studies do not model and solve problems from the perspective of strategy optimization, which results in that these problems cannot be intuitively quantified and analyzed.

Based on these considerations, our challenges are to i) analytically construct complex and dynamic networks for dispersed computing resources; ii) explore the operating process and quantitative indicators of different resource discovery modes; iii) build an optimization model with accurate decision variables, objective functions, and constraints for dispersed computing resource discovery; and iv) design an algorithm and a complete system simulation process for dispersed computing resource discovery.

To address these challenges, we consider the resource discovery problem with complex patterns and state changes as a multi-level decision problem. A bi-level programming approach is employed to optimally model the resource discovery problem for dispersed computing, where time cost, energy consumption, and accuracy of information acquisition are the driving factors of the model. The upper-level programming model aims at designing a reasonable network structure for dispersed computing resource discovery, while the lower-level programming model explores the efficient resource discovery modes. The upper level intervenes in the lower level through decision making, while the lower level obtains its own decision solution and feeds back to the upper level, both of which form a closed-loop and unified overall optimization process. In detail, the main contributions of this paper are as follows.

• This paper firstly develops a bi-level programming model for describing the optimization of dispersed computing resource discovery.

• This is the first time to apply complex network topology features to the analysis of polymorphic migration of networks with dispersed computing resources.

• This research integrally proposes a method for calculating energy consumption in agent mode and self-directed mode in dispersed computing resource discovery.

• This work innovatively designs a heuristic algorithm based on the symmetric trust region (STRA) for solving the dispersed computing discovery model.

• This paper completely implements the numerical simulation of dispersed computing resource networks in multiple modes and topological states.

The remainder of the paper is structured as follows. Section II goes over related work and achievements in resource discovery. Section III models and describes the dispersed computing resource discovery based on a polymorphic migration network. Section IV provides an optimization solution for the proposed dispersed computing resource discovery problem. Numerical simulations corresponding to our model and algorithm are revealed in Section V. Finally, we conclude the work in Section VI.

II.   Related work

Many achievements have been made about computing resource discovery in various fields such as grid computing, edge computing, fog computing, inter-cloud environment, mobile ad hoc networks, and wireless sensor networks. The research on discovery strategies is mainly divided into two categories, that is, resource discovery strategies based on single mode (e.g., active mode or passive mode) and resource discovery strategies based on multi-mode (e.g., active-passive hybrid mode) selection.

Wolfson et al. [12] proposed a resource discovery method based on active mode for mobile ad hoc networks, which avoids the inefficiency caused by frequent network disconnection by proactively pushing information. Chung et al. [13] proposed a protocol for grid resource discovery and information monitoring based on an active mode with offset-sensitive, time-sensitive, and hybrid mechanisms to support changing resource states. Murturi et al. [14] proposed a discovery strategy based on locally browsed resources in edge computing environments. This strategy exchanges metadata of available resources within a certain range between edge nodes in a peer-to-peer manner, allowing users to perform various complex queries locally. Battula et al. [15] proposed an efficient resource discovery strategy based on support and confidence for fog environments. The approach enables efficient resource discovery and monitoring services with minimal resource consumption. The above research results show that each of these single strategies has advantages and disadvantages in different scenarios, for example, resource discovery based on active mode is more efficient in resource search but can lead to non-essential costs due to frequent release of information, while resource discovery based on passive mode is unfavorable in the time spent on request search.

In recent years, more research has focused on multi-mode discovery strategies to combine the advantages of different strategies. Xiao et al. [7], [8] emphasized the importance of resource discovery for future space/air/ground networks and reviewed resource discovery strategies in UAV-based wireless ad hoc networks in detail. The research results show that multi-mode discovery strategies are more desirable than single-mode discovery strategies. Filali et al. [9] proposed a peer-to-peer resource discovery mechanism in a grid environment based on multi-mode selection. Each peer in this mechanism can request resources or publish resources and maintain a local message cache. Huang et al. [10] proposed a resource discovery strategy for the cloud computing environment, which can intelligently switch between two modes based on user requirements and the state of the monitored resources. Liu et al. [6] proposed an adaptive selection method for resource discovery, which automatically switches between centralized and flooding policies depending on different network environments. Zhou et al. [11] proposed a resource discovery method that combines active and passive modes. This method solves the mobility problem in the peer-to-peer ad hoc network by repetition. The results show that resource discovery based on combined patterns can not only improve the success rate of search, but also reduce the network consumption caused by information transmission.

Since dispersed computing is an emerging computing paradigm, there is a lack of research on its resource discovery. Yang et al. [3] proposed an operational flow and important components for resource discovery in dispersed computing. Compared with edge computing, fog computing, inter-cloud environments and mobile ad hoc networks, the dispersed computing network is more prominent for the free mobility of nodes, heterogeneity of available resources, variable resource availability, complexity of task requirements, and dynamic uncertainty of network states and topologies. All these bring analytical difficulties to the resource discovery research of dispersed computing. In addition, existing research on resource discovery pays less attention to optimization modeling and solving, especially to specific factors such as the optimization objective, controllable variables, and operating mode of the problem. Compared to existing works, the solution of this study has several contributions. These changes compensate for the shortcomings of the existing works. In summary, the resource discovery research of dispersed computing should apply reasonable modeling tools to determine the network topology and resource discovery modes based on the network structure and resources.

III.   Scenario Description and System Model

In this section, the resource discovery process for dispersed computing is first described. In addition, two resource discovery modes are elaborated. Finally, considering the dynamic multi-level decision problem, a system model for dispersed computing resource discovery is developed, which is driven by time cost, energy consumption and accuracy of information retrieval.

1   Resource discovery process

As the running time continues, computing devices in the network tend to join, exit, move, and deplete, resulting in changes in the service capacity and operational state of networked computing resources. In this case, a time window can be used to discretely describe and analyze the dynamic process of such variations. Meanwhile, the function of resource discovery in a dispersed computing network is realized by a list of resource pool information spread over the NCPs. Within a single time window, the list of resource pool information is applied to all NCPs, which is continuously updated during the operation of the dispersed computing system. The list contains the types of resources (computing resources, storage, communication resources, etc.), the serial numbers of computing devices corresponding to the resources, and the types of tasks supported by the resources. In addition, the system architecture and procedure of dispersed computing resource discovery are shown in Fig.1 and Fig.2, respectively.

Figure  1.  The system architecture of dispersed computing resource discovery.

DownLoad: Full-Size Img PowerPoint

Figure  2.  The procedure of dispersed computing resource discovery.

DownLoad: Full-Size Img PowerPoint

The list of resource pool information plays a key role in dispersed computing resource discovery. Firstly, when a task requests a service, it can send a request message to any NCP and can obtain the resource availability status of the whole network for dispersed computing resources. Additionally, the retrieval form of the unified resource information list ensures the timeliness and accuracy of the state information of the entire network of dispersed computing resources. Furthermore, the list of resource information describes the matching and constraint relationships among resources, nodes and tasks through structured data, which improves the execution efficiency of resource discovery and ensures the reliability of resource information maintenance.

After some NCPs build the resource pool information list, the remaining NCPs will receive the list. Therefore, the core problem of dispersed computing resource discovery is to establish and maintain the resource pool information list through a reasonable optimization process. Under the condition of dynamic changes, the problem of establishing and maintaining the resource pool information list involves both the state migration of the network topology and the time and energy costs caused by the node selection and frequent interactions of information between nodes. In view of this, the cost-driven design of resource networks and resource retrieval processes need to be considered comprehensively in this study. At the same time, the mode of resource discovery needs to be reasonably analyzed and dynamically selected in terms of specific driving factors such as energy consumption and accuracy of information retrieval.

2   Resource discovery mode

An NCP generally has data exchange protocols such as maintenance of local resource database, resource access module, resource query module and maintenance of global resource database (list of resource pool information in the network). This makes the NCP have the functions of proxy of resource directory, retrieval of resource directory and computing services. The NCP can switch roles freely, which is to act as query agent node (QAN) and/or general computing node (GCN). For the network of dispersed computing resources, we propose two discovery modes, namely, the agent mode and the self-directed mode, which are characterized as follows:

• In the agent mode, a QAN is selected and configured to retrieve proxy resource directories under the condition of a specific number of candidates. To obtain the list of resource pool information, for all task categories, resource retrieval requests are sent to the QAN through some GCNs. After that, the QAN sends the list of resource pool information for all tasks to all GCNs connected to it.

• In the self-directed mode, the QAN does not play its agent role, but performs the same operational process as a GCN. For all task categories, the list of resource pool information is obtained by hop-by-hop transmission and retrieval from individual nodes to the rest of the nodes. After that, the individual nodes transmit information to subsequent nodes again for pushing the list to all nodes.

3   System model

In response to the design of resource networks and the retrieval of resources in dispersed computing resource discovery, we introduce a bi-level programming approach for optimal modeling. The upper-level programming model lies in determining a reasonable network structure. Its decision objective is to reduce the total time cost of resource discovery agent services for a dispersed computing system. In addition, it makes decisions by selecting and configuring QANs and establishing connections between GCNs and QANs. The lower-level programming model is to investigate the effective resource discovery mode in dispersed computing, where the decision objective is to reduce the total energy consumption of resource discovery and the decision form is to select the resource discovery mode. Section III.2 Resource discovery mode includes a self-directed mode and an agent mode. In this model, the decision variable is in binary form, corresponding to the above two modes respectively. According to the optimization objective and decision form of the model, the characteristics of the bi-level programming decision for dispersed computing resource discovery are shown in Fig.3. To establish the bi-level programming model, the sets, parameters and variables are defined in Table 1.

Figure  3.  The bi-level programming decision characteristics for dispersed computing resource discovery.

DownLoad: Full-Size Img PowerPoint

Table  1.  Parameters and connotations for the system model

Parameters	Connotations
$K$	The set of time windows indexed by $k$, that is, $k=\left\{1,2, \ldots, k_{\max }\right\}$ (The time window represents the numerical sequence of migration cycles in the problem).
$Num\_node^{(k)}$	The total number of nodes in the network at the $k$th time window.
$I$	The set of GCNs indexed by $i$.
$J$	The set of QAN candidates indexed by $j$.
$c_{j}^{sel}$	The time required to configure the QAN candidate $j$.
$c_{ij}^{con}$	The time required to establish a connection between GCN $i$ and QAN $j$.
$l_{ij}^{(k)}$	There may be movement of nodes at different time windows. This parameter indicates the actual communication distance between GCN $i$ and QAN candidate $j$ at the $k$th time window.
$d_{c}$	Communication coverage distance of a single QAN.
$\Theta_{i}^{(k)}$	The set of all QAN candidates that can cover the GCN $i$ and $\Theta_{i}^{(k)}=\{j \mid l_{i j}^{(k)} \leq d_{c}\}$.
$X_{j}^{(k)(m)}$	Decision variable. 1 indicates that the node candidate $j$ for the $m$th resource in the $k$th time window can be used as a QAN in the agent mode and a GCN in the self-directed mode. 0 indicates that it can only be used as a GCN in the self-directed mode.
$W_{i j}^{(k)(m)}$	Decision variable. It is 1 to indicate that GCN $i$ establishes a connection with QAN candidate $j$ when searching for the $m$th resource in the $k$th time window, otherwise it is 0.
$Y_{i}^{(k)(m)}$	Decision variable. It is 1 to indicate that GCN $i$ runs the agent mode during resource discovery for the mth resource requirement in the $k$th time window, otherwise it is 0 (self-directed mode).
$D_{i\_{agent}}^{(k)(m)}$	For the $m$th resource demand in the $k$th time window, the energy consumption of GCN $i$ running in agent mode to complete the resource discovery process.
$D_{i\_{self}}^{(k)(m)}$	For the $m$th resource demand in the $k$th time window, the energy consumption of GCN $i$ running in self-directed mode to complete the resource discovery process.
$Q_{i\_{agent}}^{(k)(m)}$	For the $m$th resource demand in the $k$th time window, the accuracy sign of the RIS for GCN $i$ to complete resource discovery in agent mode.
$Q_{i\_{self}}^{(k)(m)}$	For the $m$th resource demand in the $k$th time window, the accuracy sign of the RIS for GCN $i$ to complete resource discovery in self-directed mode.
$Q^{req}$	To ensure the efficiency and accuracy of resource discovery, thresholds for RIS sign are defined.

 | Show Table

DownLoad: CSV

1) Upper-level programming model

Based on the analysis of the decision characteristics in Fig.3, a bi-level programming model for dispersed computing resource discovery is established. The upper-level model focuses on the design of the network topology for the state migration problem. It is specified as a polymorphic connection relationship among QANs, candidate QANs and GCNs within a dynamic time window. In practice, firstly, a specific number of nodes are selected as the set of QAN candidates. Then, a single QAN and its actual connections to other nodes are determined through optimization. Meanwhile, opportunistic connections exist between GCNs, as shown in Fig.4.

Figure  4.  State migration for dispersed computing resource network.

DownLoad: Full-Size Img PowerPoint

We attempt to minimize the total time to configure QAN and the total time to establish connections between GCNs and QAN. The upper-level programming model is formulated as follows:

where $C1$ represents the validity premise that a QAN is established to satisfy the demand of resource discovery, i.e., the resource demand $m$ within time window $k$. $C2$ represents the covering premise of information on resource types, i.e., for a resource demand $m$ within a time window $k$, there exists at least one connection between a QAN and a GCN. $C3$ indicates that for any GCN $i$, there is one and only one QAN connected to it, no matter how it moves in different time windows. $C4$ represents the logical premise, that is, for resource demand $m$ in time window $k$, the connection between the QAN and the GCN is based on the establishment of the QAN. $C5$ represents the probability of opportunistic connections between GCNs other than the actual connections between the QAN and GCNs. Let this type of connection probabilities obey a negative exponential distribution $\eta\left(c_{i j}^{(k)_{-} c o n}\right)={\rm{e}}^{-\lambda \cdot c_{i j}^{(k)_{-} c o n}}$, where $\lambda$ can be obtained by Monte Carlo simulation in the case. $C6$ and $C7$ define the constraints for the decision variables.

The analytical features of the model show that the network of dispersed computing resource belongs to the variable-weight unstable network. The core feature of the network is that although the spatial aggregation structure of the nodes changes dynamically, it always maintains the undirected graph connectivity with non-unique matching. In other words, during the migration of a dispersed computing network, there is at least one path of bi-directional connectivity between NCPs. This path refers to both forward and reverse transmission of packets between two NCPs. In addition, the shortest path between two NCPs is unique and computationally available [4]. As shown in Fig.5, when NCPs 1, 2 and 3 are covered by the communication capability, the three NCPs may form a link. When NCP 3 is far away from the other two NCPs, the node may be isolated. Therefore, the above constraint assumptions of the connectivity graph are essential.

Figure  5.  NCP connectivity variations in the migration of the dispersed computing resource network.

DownLoad: Full-Size Img PowerPoint

In terms of application, such features ensure the feasibility of the dispersed computing network to maintain multi-site data exchange and collaborative retrieval of multiple types of resources under multiple migration cycles, multiple operation modes, and multiple performance states. In terms of mathematical analysis, the corresponding network topology characteristics are demonstrated as follows.

Lemma 1　In two consecutive migration cycles, let $\Phi$ be the network of dispersed computing resources after the change of QAN (the network in the latter cycle), $\phi$ be the network of dispersed computing resources corresponding to the original QAN (the network in the previous cycle), and $\phi$ be a constant connectivity graph. Let $f_{1}: \Phi \rightarrow \Gamma$ and $f_{2}: \Phi \rightarrow \Gamma$ be continuous mappings. If $f_{1} \mid _{\phi }= f_{2} \mid _{\phi }$, then $f_{1}=f_{2}$, which means that the two mappings must be equal on the migrated network as long as they are equal on the original network, thus ensuring that the continuity of connectivity characteristics in the network migration and the real-time availability of each node under the communication mechanism of the system.

Proof　Let $f_{1}\mid _{\phi }= f_{2}\mid _{\phi }$, then there exists $x \in \Phi$ such that $f_{1}(x) \neq f_{2}(x)$. Let $\delta=\mid f_{1}(x)-f_{2}(x)\mid$, then $\delta>0$. And let $\left\{\begin{array}{l}\Omega_{1}=\left(f_{1}(x)-\delta / 2, f_{1}(x)+\delta / 2\right) \\ \Omega_{2}=\left(f_{2}(x)-\delta / 2, f_{2}(x)+\delta / 2\right)\end{array}\right.$, then $\Omega_{1} \cap \Omega_{2}=\varnothing$. By the continuity of mapping $f_{1}$ and mapping $f_{2}$, it is clear that both $f_{1}^{-1}\left(\Omega_{1}\right)$ and $f_{2}^{-1}\left(\Omega_{2}\right)$ are neighbors of $x$, so $\Pi=f_{1}^{-1}\left(\Omega_{1}\right) \cap f_{2}^{-1}\left(\Omega_{2}\right)$ is also a neighbor of $x$. Since the original network $\phi$ must be a fully connected graph with finite node connectivity and meets the expansion condition of dense set, then $\Pi \cap \phi \neq \varnothing$. For any $y \in \Pi \cap \phi$, $f_{1}(y)=f_{2}(y) \in \Omega_{1} \cap \Omega_{2}$ is satisfied, thus $\Omega_{1} \cap \Omega_{2} \neq \varnothing$, which contradicts the initial assumption, and the proof is over.

2) Lower-level programming model

The upper-level model intervenes in the lower-level model by determining the network topology of the dispersed computing resources. The lower-level model implements the optimization of mode selection for nodes driven by the total energy consumption and constrained by the RIS sign. At the same time, the decision-making optimization scheme obtained by the lower-level model is counteracted to the upper-level model. The principle of the lower-level model is shown in Fig.6.

Figure  6.  The principle of the lower-level model.

DownLoad: Full-Size Img PowerPoint

Considering to minimize the total energy consumption of the entire resource discovery process, the lower-level programming model is shown below,

where $C1$ represents the logical premise of the resource discovery mode of the GCN, that is, the GCN can select the agent mode only if the GCN $i$ establishes a connection with the QAN, otherwise the GCN can only select the self-directed mode. $C2$ is the threshold constraint of the RIS sign for the dispersed computing system, i.e., the lower bound of the expected sum of the RIS sign for the dispersed computing system in the agent mode. Similarly, $C3$ is the threshold constraint of the RIS sign for the dispersed computing system, i.e., the lower limit of the expected sum of the RIS sign for the dispersed computing system in the self-directed mode. $C4$ is the constraint defined by the decision variable, namely two resource discovery modes. These modes correspond to Section III.2 Resource discovery mode.

3) The calibration of energy consumption and RIS sign

This subsection describes the calibration process of parameters such as energy consumption of resource discovery and RIS sign in the lower-level programming model. The decision variable in the lower-level model is the choice of resource discovery mode (${\boldsymbol{Y}}$). The relevant parameters of the model involve the value of energy consumption (${\boldsymbol{D}}$) and the value of RIS sign (${\boldsymbol{Q}}$) for different discovery modes [16]. Therefore, different resource discovery modes need to be analyzed in order to realize the quantitative calculation of energy consumption and RIS corresponding to their micro-continuous processes. Moreover, ${\boldsymbol{Q}}$ reflects the accuracy and comprehensiveness of the directory of resource discovery information. Different ${\boldsymbol{Q}}$ values correspond to different ${\boldsymbol{D}}$ values. In view of this, the values of energy consumption and RIS sign generated in different modes should be analyzed and calibrated. Figs.7 and 8 show the calibration and acquisition process of RIS sign and corresponding energy consumption parameters in agent mode and self-directed mode, respectively. The specific calculation steps will be elaborated later.

Figure  7.  The calibration of RIS sign and energy consumption parameters in agent mode.

DownLoad: Full-Size Img PowerPoint

Figure  8.  The calibration of RIS sign and energy consumption parameters in self-directed mode.

DownLoad: Full-Size Img PowerPoint

a) The update state in agent mode

In the agent mode, the directory of resource information is obtained through the QAN selected by the upper-level model. In this paper, we take a certain computing resource $m$ (e.g., GPU) as an example to analyze the impact of ${\boldsymbol{Q}}$. For a dispersed computing resource network, the time required to perform a single computation for resource $m$ is

where $\Delta t_{1}$ also denotes the update period of resource $m$. $\Gamma_{m}$ indicates the number of computational tasks (unit: seconds) corresponding to resource $m$, which is specified as the product of the number of resources required to complete the task and the time required. We assume that the computing capacity of each GCN is the same for the same type of resource, so the total amount of resources can be equivalent to the total number of GCNs. $N_{reso}(m)$ denotes the number of available resources $m$.

The maximum number of tasks that can be completed in a given time interval $\Delta t_{2}$ (the capacity of the network for task processing) is shown in the following equation,

where $\Delta t_{2}$ is the time slot between two consecutive updates for the information state of a certain resource on a single GCN. $\Delta t_{2}$ is related to the type of resource and satisfies the condition of polymorphic migration cycle for the network, that is, $\Delta t_{2} \ll T$ and $T$ denotes the size of the time window. In particular, for all GCNs with a certain type of resource, the value of $\Delta t_{2}$ is same. From the perspective of dynamic optimization of network, $\Delta t_{2}$ should ideally be a decision variable within each $T$ to obtain optimal values driven by the optimal objective of resource discovery. In view of the difficulty of uniform optimization analysis due to the limitations of performance parameters of mobile computing devices, $\Delta t_{2}$ is used as a parameter in this paper to implement the numerical computation of the model. In practice, $\Delta t_{2}$ can be achieved through extensive testing of computational effects.

The relationship between $\overline{N}_{task}$ and the number of tasks $N_{task}(m)$ corresponding to resource $m$ in the resource discovery process is divided into two cases.

Case 1 $N_{task}(m)>\overline{N}_{task}$

In a given interval $\Delta t_{2}$, the number of computing tasks that can be handled by resource $m$ in the network is constrained by the maximum capacity of the resource. Moreover, a GCN needs to update the resource information when allocating resources and releasing resources. In this case, for the resource $m$ in the entire dispersed computing network, the total number of updates (unit: times) required by GCNs under the condition that all GCNs in the network participate in the computation is as follows:

Case 2 $N_{task}(m) \leq \overline{N}_{task}$

In a given interval $\Delta t_{2}$, the number of computing tasks that can be handled by resource $m$ in the network is not subject to the maximum capacity of the resource. Therefore, the number of GCNs to be updated is determined by the number of tasks that need to be completed. In this case, for the resource $m$ in the entire dispersed computing network, the total number of updates (unit: times) required for GCNs under the condition that all GCNs in the network participate in the computation is as follows:

Furthermore, the total number of updates of all GCNs in the polymorphic migration cycle $T$ of the dispersed computing resource network is

where $N_{update}^{m}$ denotes the total number of updates required for the nodes corresponding to resource $m$.

When a GCN’s available resources change, the corresponding changes should be updated in the directory of resource information. At the same time, the status of available resources on GCNs always changes dynamically, so RIS may suffer from accuracy deviation due to delayed updates. In addition, the update of RIS consumes some energy. The more frequent the updates are, the more energy consumption is. In detail, the accuracy of the RIS is related to the time when the RIS is updated and the time when the actual state of the resource changes, as shown in Fig.9.

Figure  9.  The moments related to the accuracy of RIS.

DownLoad: Full-Size Img PowerPoint

In resource discovery, it is assumed that the resource requests received by GCNs obey the Poisson distribution [6]. ${\boldsymbol{Q}}$ denotes a binary random variable with the accuracy sign of the RIS, where 0 indicates that the GCNs’ feedback on the search requests for resource discovery is inaccurate and 1 indicates that the corresponding feedback is accurate. Furthermore, the expected value of the feedback accuracy of the resource discovery request can be expressed as $E(Q)=\int_{0}^{\Delta t_{2}}[f(t) \cdot E\left(Q \mid t_{c h g}=t\right)] {\rm{d}} t$, where $\Delta t_{2}=t_{u p d}-t_{last}$ and $f(t)$ is the probability density function of $t_{c h g}$. When search requests for resource discovery are generated in the interval $\left(t_{l a s t}, t_{u p d}\right)$, the probability density distribution of the moment $t_{c h g}$ when the actual state of the resource changes is in the form of $f(t)=1 / \Delta t_{2}$. Meanwhile, the expected value of the random variable ${\boldsymbol{Q}}$ is expressed as $E\left(Q \mid t_{c h g}\right)=\left(t_{c h g}-t_{last }\right) / \Delta t_{2}$. Under this condition, $E\left(Q \mid t_{c h g}\right)$ is directly related to $t_{last}$ and $t_{c h g}$, and $E(Q)=E\left(Q \mid t_{c h g}\right) \cdot \int_{0}^{\Delta t_{2}} f(t) {\rm{d}} t=\left(t_{chg}-t_{last}\right) / \Delta t_{2}$.

In order to ensure the accuracy of resource state information, the update time $t_{u p d}$ of RIS should satisfy $E(Q) \geq|Q|^{req_{-}agent}$, that is, $\left(\left(t_{c h g}-t_{l a s t}\right) / \Delta t_{2}\right) \geq |Q|^{r e q}$. Additionally, to promote the timely update of RIS to the maximum extent, the update moment should be located in the interval $\left(t_{l a s t,} t_{c h g}\right)$ as much as possible. Furthermore, for the dispersed computing resource network, the total number of updates required by all GCNs within $T$ satisfies $N_{update}^{all\_{acc}} = N_{update }^{all } \cdot(t_{chg}- t_{last }) / \Delta t_{2}$.

b) The update state in self-directed mode

Within each polymorphic migration cycle $T$ of the dispersed computing network, resource discovery may operate in the self-directed mode. In this mode, information from resource search and feedback is forwarded step by step to achieve maximum individual traversal and retrieval. To save the search cost and ensure the search coverage, reasonable and large hop counts (HCs) should be set. HC satisfies the following equation and its numerical relationship is shown in Fig.10.

Figure  10.  HCs and forwarding probability in self-directed mode.

DownLoad: Full-Size Img PowerPoint

where $P_{n}$ denotes the probability of the GCN at the $n$th hop (packet forwarding).

HC should be reasonably set so that the information of resource search can reach all GCNs in the dispersed computing network. If HC is small, it is difficult to achieve node traversal and to ensure the accuracy of RIS at the system level. If the HC is too large, it will lead to more energy consumption to complete the data forwarding and delivery process. Therefore, a reasonable HC needs to be set to reduce energy consumption under the premise of accurate RIS. The expected value of the accuracy sign of the RIS represented by the binary random variable ${\boldsymbol{Q}}$ satisfies the following equation,

where $E(Q) \geq|Q|^{r e q_{-} self}$ is known from the accuracy threshold constraint of the lower-level model.

• Energy consumption calculation

Based on the analysis of the operational state of the two resource discovery modes, the corresponding energy consumption metrics are calculated. $\sigma_{all\_resc}$ is the number of discovery requests for all types of resources in the network within $\Delta t_{2}$ [6].

If the agent mode is adopted, the energy consumption generated by resource discovery within $\Delta t_{2}$ is calculated as follows:

where the total energy consumption $D_{agent}$ includes the energy consumption generated by sending resource discovery requests from GCNs to the QAN, the energy consumption generated by GCNs receiving resource discovery responses from the QAN, and the energy consumption from GCNs sending resource update messages to the QAN.

If the self-directed mode is adopted, let the number of nodes covered by the wireless transmission range of a single node be $N_{brc}$ and the total number of nodes in the network of dispersed computing resources be $N_{all}^{I}$ within $\Delta t_{2}$. When the HCs of the resource discovery request are determined, the expected value of $N_{brc}$ satisfies

The average HC between the node requesting the resource discovery and the node responding to the resource discovery is calculated as follows:

The energy consumption resulting from a single request for resource discovery within $\Delta t_{2}$ is shown below.

where the total energy consumption $D_{self}^{\prime}$ under the condition of $HC \geq 2$ contains three parts, the energy consumption generated by the initial forwarding of data in resource discovery, the energy consumption generated by relay nodes receiving and forwarding data and the energy consumption generated by the relay receiving and forwarding in the broadcast transmission by the responding nodes to the nodes in the whole network. The flow of the energy generation in self-directed mode is shown in Fig.11. Furthermore, the energy consumption generated by the resource discovery in the self-directed mode within $\Delta t_{2}$ is

Figure  11.  Energy generation process in self-directed mode.

DownLoad: Full-Size Img PowerPoint

IV.   The Proposed Solution

Considering the NP-hard characteristics of the bi-level programming problem [17], the acquisition of the global optimal solution is difficult and has certain limitations if an exact algorithm is applied. In this paper, a heuristic algorithm is employed to solve the system model. The lower-level model implements the energy consumption calculation for resource discovery by identifying the appropriate operation mode based on binary decisions. In this model, the decision variables are all integers; the dimensionality of the solution space is high; there are multiple couplings between multiple variables. Therefore, the heuristic algorithm needs to converge vertically and quickly. This algorithm needs to easily nest the optimization results of the lower-level energy consumption. In this paper, an STRA is proposed for the solution.

A trusted region is a form of efficient solution sets in optimization theory. In other words, this region refers to the range of decision variables that satisfy the constraints of all parties (e.g., multi-objective decision-making, bi-level decision-making) and are trusted by all parties under different interest-driven directions. Further, it essentially refers to the region where the optimal solution can be fully trusted. In this region, it gradually converges to the heuristic optimal solution through iterations [16]. Compared with the traditional “mountain-climbing” search algorithm, this paper aims to achieve the discretized search and approximation of the optimal solution based on the trust region space. At the same time, taking into account the structural characteristics of the bi-level programming model, we propose a trust domain vector method with symmetric constraints and objectives for the upper and lower-level model to efficiently approximate the optimal solution. The computational process we design belongs to a heuristic optimal search technique. It has good generalizability to the model. The key search elements involved in the process include the transformation of the combinatorial problem, the determination of the trust region vector, the correction of the trust domain vector, and the judgment of convergence. The steps of the STRA are specified as follows.

Step 1: Initialization. The original bi-level programming problem $F$ is defined as a combination of subproblems $F_{up}$ and $F_{low}$ with an initial iteration number $s = 1$. ($F$ is equations (1) and (2), where $F_{up}$ is equation (1) and $F_{low}$ is equation (2).)

Step 2: The determination of the initial trust region vector. In the original bi-level programming model, the decision variables include three types of 0-1 variables. Let the vector $\left({\boldsymbol{X}}_{s}, {\boldsymbol{W}}_{{s}}, {\boldsymbol{Y}}_{{s}}\right)=\boldsymbol{0}$, that is, all elements of the three types of decision variables in the initial solution are 0. The vector is substituted into $F_{up}$ and $F_{low}$ respectively to verify whether the constraints are satisfied. If the constraints are satisfied, the trust region condition of the upper and lower-level models is met (to Step 3). If they are not satisfied, the trust region condition is not met (to Step 4). (The constraints of $F_{up}$ include C1–C7 of equation (1), and the constraints of $F_{low}$ include C1–C4 of equation (2).)

Step 3: The solution of the combinatorial problem. The trust region vector $\left({\boldsymbol{X}}_{s}, {\boldsymbol{W}}_{{s}}, {\boldsymbol{Y}}_{{s}}\right)$ is substituted into $F_{up}$ to obtain the current optimal solution $Z_{u p(s)}$ of the upper-level programming. Similarly, the same trust region vector is substituted into the $F_{low}$ to obtain the current optimal solution $Z_{low(s)}$ of the lower-level programming. The number of iterations is $s=s+1$ (to Step 6). ($Z_{u p(s)}=\sum_{j \in J} \sum_{k \in K} \sum_{m \in M} c_{j}^{(k)\_ {s e l}} X_{j}^{(k)(m)}+ \sum_{i \in I} \sum_{j \in J} \sum_{k \in K} \sum_{m \in M} c_{i j}^{(k)\_ {con}} Y_{i}^{(k)(m)}$ and $Z_{low(s)}= \sum_{i \in I} \sum_{k \in K} \sum_{m \in M}\left[D_{i_{-} a g e n t}^{(k)(m)} \cdot Y_{i}^{(k)(m)}\right]$ + $\sum_{i \in I} \sum_{k \in K} \sum_{m \in M}\left[D_{i_{-}{self }}^{(k)(m)} \cdot\left(1-Y_{i}^{(k)(m)}\right)\right]$).

Step 4: For $\left({\boldsymbol{X}}_{{s}-1}, {\boldsymbol{W}}_{{s}-1}, {\boldsymbol{Y}}_{{s}-1}\right)$, an element $rand^{(0)}$ is selected at a random position of the solution vector with value 0. Let $rand^{(0)}=rand^{(0)}+1$ and $({\boldsymbol{X}}_{{s}}, {\boldsymbol{W}}_{{s}}, {\boldsymbol{Y}}_{{s}})= \left({\boldsymbol{X}}_{{s}-1}, {\boldsymbol{W}}_{{s}-1}, {\boldsymbol{Y}}_{{s}-1}\right)+{\boldsymbol{rand}}^{\Delta(0)}$. ${\boldsymbol{rand}}^{\Delta(0)}$ represents that the vector of all-0 elements is added to $rand^{(0)}$ at the corresponding random position. It needs to be verified whether $\left({\boldsymbol{X}}_{s}, {\boldsymbol{W}}_{{s}}, {\boldsymbol{Y}}_{{s}}\right)$ satisfies the trust region condition for both $F_{up}$ and $F_{low}$. If it is satisfied, $Z_{u p(s)}$ and $Z_{low(s)}$ from the $s$th iteration are computed (to Step 6). Otherwise, turn to Step 5.

Step 5: Two elements $rand^{(1)}$ and $rand^{(2)}$ with value 0 are randomly selected from $\left({\boldsymbol{X}}_{{s}-1}, {\boldsymbol{W}}_{{s}-1}, {\boldsymbol{Y}}_{{s}-1}\right)$. Let $rand^{(1)}=rand^{(1)}+1$, $rand^{(2)}=rand^{(2)}+1$ and $\left({\boldsymbol{X}}_{{s}}, {\boldsymbol{W}}_{{s}}, {\boldsymbol{Y}}_{{s}}\right) = \left({\boldsymbol{X}}_{{s}-1}, {\boldsymbol{W}}_{{s}-1}, {\boldsymbol{Y}}_{{s}-1}\right)+{\boldsymbol{rand}}^{\Delta(1)}+{\boldsymbol{rand}}^{\Delta(2)}$, where ${\boldsymbol{rand}}^{\Delta(1)}$ and ${\boldsymbol{rand}}^{\Delta(2)}$ have the same calculation rules as ${\boldsymbol{rand}}^{\Delta(0)}$. It is need to continue verifying $\left({\boldsymbol{X}}_{s}, {\boldsymbol{W}}_{{s}}, {\boldsymbol{Y}}_{{s}}\right)$ until both $F_{up}$ and $F_{low}$ are satisfied.

Step 6: At the $s$th iteration, the iterative incremental magnitude $\Delta_{up(s)}=\dfrac{Z_{up(s)}-Z_{up(s-1)}}{Z_{up(s-1)}}$ of the objective function from the upper-level programming is solved (to Step 7).

Step 7: If $\Delta_{u p(s)} \leq \varepsilon_{u p}$ is satisfied, the trust region condition can be further verified for symmetric convergence (to Step 8). Otherwise, the trust region needs to be reconstructed (to Step 4).

Step 8: At the $s$th iteration, the iterative incremental magnitude $\Delta_{low(s)}=\dfrac{Z_{low(s)}-Z_{low(s-1)}}{Z_{low(s-1)}}$ of the objective function from the lower-level programming is solved (to Step 7).

Step 9: If $\Delta_{low(s)} \leq \varepsilon_{low}$ is satisfied, the trust region condition can be further verified for symmetric convergence (to Step 10). Otherwise, the trust region needs to be reconstructed (to Step 4).

Step 10: Output the current optimal solutions $\left({\boldsymbol{X}}_{s}, {\boldsymbol{W}}_{{s}}, {\boldsymbol{Y}}_{{s}}\right)$, $Z_{u p(s)}$ and $Z_{low(s)}$.

V.   Numerical Simulations

For the proposed dispersed computing resource discovery model of polymorphic migration network architecture and its corresponding algorithm, numerical simulations are performed in this section to verify the accuracy of the method and process. In the conditions of numerical simulation, the benchmark parameters are set as shown in Table 2, where the corresponding parameters can be adjusted according to the computational requirements and the sensitivity analysis. In detail, $num\_{node}$ is the number of NCPs in the initial migration cycle. $interval$ is the increase and decrease range of the number of NCPs, which is used to describe the entry and exit of NCPs in the networked polymorphic migration. $T$ is the duration of a single network migration cycle. $\Delta t_{2}$ is the update period used for calculation in the two operation modes of resource discovery (see the model for specific meaning). $Q_{i\_{agent}}^{(k)(m)}$ is the lower bound of the expected value of the RIS in the agent mode. $Q_{i\_{self}}^{(k)(m)}$ is the lower bound of the expected value of the RIS in the self-directed mode. $num\_{T}$ is the number of network migration cycles executed in the simulation. The hardware environment for the numerical simulation is an Intel(R) Core(TM) i7 processor with 16.0 GB RAM. The software environment is MATLAB R2019b with discrete signal simulation module.

Table  2.  Benchmark parameters

Parameters	$num\_{node}$	$interval$	$T/s$	$\Delta t_{2}/s$	$Q_{i\_{agent}}^{(k)(m)}$	$Q_{i\_{self}}^{(k)(m)}$	$num\_{T}$
Values	50	$\pm$10%	2	0.1	0.1	0.1	100

 | Show Table

DownLoad: CSV

In this simulation, the routing of data between nodes is implemented by the Floyd algorithm. The algorithm is a dynamic programming technical process for the specific path selection between multiple-site sources to ensure orderly and full coverage of nodes. For a network with dispersed computing resources, the Floyd algorithm guarantees arbitrary coverage from the requesting node to the nodes in the entire network. This algorithm can accurately obtain the specific path of the request and response packets. In path search, the edge weight of the network can be positive or negative, which can adapt to the diverse transmission directions of packets. For self-directed mode, broadcast routing traverses the same range of paths as the Floyd algorithm. Broadcast routing and the Floyd algorithm produce the same energy consumption for transmission. For a dispersed computing network with $num\_{node}$ NCPs, the time complexity is $O\left((n u m\_n o d e)^{3}\right)$ and the space complexity is $O\left((n u m\_n o d e)^{2}\right)$ [18].

In the upper-level model, opportunistic connections exist between the GCNs except for the real connections between the QANs and the GCNs. The probability of an opportunistic connection obeys a negative exponential distribution as $\eta\left(c_{i j}^{(k)_{-} c o n}\right)={\rm{e}}^{-\lambda \cdot c_{i j}^{(k)_{-} c o n}}$, where $\lambda$ is obtained by Monte Carlo simulation (i.e., needle experiment for two-point attraction in a limited range). In the experiment, through a certain number of attempts, the optimal parameter $\lambda$ required by the model is determined. In other words, the meaning of the experiment is to determine the unknown parameters of the model through simulation. Fig.12 shows the 12 curves of the negative exponential distribution with the best agreement in the Monte Carlo simulation. These curves were simulated for 100 network migration cycles, where $\lambda=0.35$ corresponds to the lowest root mean square error. Therefore, $\lambda$ is calibrated to 0.35, which discriminates the probability of opportunistic connections between GCNs.

Figure  12.  The 12 curves of the negative exponential distribution with the best agreement in the Monte Carlo simulation.

DownLoad: Full-Size Img PowerPoint

The resource discovery modes corresponding to each cycle during the simulation are shown in Fig.13, where 1 indicates the agent mode and 0 indicates the self-directed mode. In addition, as the simulation proceeds, the structure of the dispersed computing network changes, which in turn affects the energy consumption and accuracy of the information state in resource discovery.

Figure  13.  Results of the resource discovery mode run in the simulation.

DownLoad: Full-Size Img PowerPoint

Figs.14 and 15 show the total energy consumption and the expected values of RIS for resource discovery, respectively. It can be seen that as the cycle evolves, the corresponding decision-making constraints change significantly. The influence of network migration is further accentuated.

Figure  14.  Total energy consumption for resource discovery in simulation.

DownLoad: Full-Size Img PowerPoint

Figure  15.  RIS expected value for resource discovery in simulation.

DownLoad: Full-Size Img PowerPoint

Furthermore, the key metrics of the energy consumption and the expected value of the RIS for resource discovery in the different modes are measured and analyzed, which allows an intuitive comparison of the effectiveness of the two modes applied in resource discovery, as shown in Table 3. In terms of total energy consumption, the agent mode is smaller than the self-directed mode regarding the maximum, minimum and average values. In terms of the expected value of RIS, the corresponding indexes of the agent mode are larger than those of the self-directed mode. It can be inferred that the agent mode is more applicable than the self-directed mode for the resource discovery simulation. The agent mode is more consistent with the resource discovery requirements of dispersed computing with low energy consumption and high accuracy. However, this applicable effect is only related to the optimization process of the lower-level model. Adopting the agent mode alone can be too costly in terms of time, so the two resource discovery modes should be combined when making optimization decisions. The comparison of the two modes reflects the different states of resource discovery. The comparison results show that there is no fixed discovery mode for dynamic and complex networks. Different time windows, different types of resources, and different nodes may affect the mode of resource discovery.

Table  3.  Comparison of the effect of different resource discovery modes

Modes	# migration cycles	Max. TEC3	Min. TEC	Avg. TEC	Max. RIS EV4	Min. RIS EV	Avg. RIS EV
AM1	46	495.95	107.83	296.76	0.93	0.24	0.59
SM2	54	497.48	117.78	305.51	0.75	0.04	0.34
Note: 1 AM: Agent mode; 2 SM: Self-directed mode; 3 (T)EC: (Total) energy consumption; 4 EV: Expected value.

 | Show Table

DownLoad: CSV

Fig.16 shows the distribution of the number of updates of the nodes (agent mode) and the average HCs (self-directed mode) in a single cycle of network migration in relation to the total energy consumption of the resource discovery and the expected value of the RIS. For the total energy consumption, the distribution trends of the number of updates and the average HCs are significantly different, that is, there are distinct “peaks” and “valleys”. The reason is that the energy consumption is related to the frequency of packet transmission between nodes, whereas a large number of updates and multi-hop broadcasts lead to a high transmission frequency. For the expected information state, the distribution trends of both the number of updates and the average HCs are more regular, that is, there are no significant numerical fluctuations. In the optimization process of the model, the simulation results of the number of updates and the average HCs indicate well-adapted patterns. Rationally, the accuracy of the RIS is not only related to the number of valid packets and the reachable range of the broadcast, but also influenced by the frequency of packet transmission and the number of nodes. The structure of the bi-level programming model and the form of lower-level decision variables indicate that the frequency of packet transmission and the number of nodes play a more prominent role in the optimization process. The synergy of these two variables makes the value of the RIS stable.

Figure  16.  Distribution of the average HCs, node updates and total energy consumption and expected RIS in a single cycle of network migration.

DownLoad: Full-Size Img PowerPoint

Fig.17 shows the game-driven situation of the bi-level objectives in the resource discovery model, where the horizontal axis represents the total energy consumption of resource discovery in a single cycle and the vertical axis represents the total time cost of resource discovery in a single cycle. The distribution of data points shows a negative correlation between total time cost and total energy consumption. The reason for this is that these two optimization objectives are mutually constrained and it is difficult to achieve optimal results by simultaneous optimization. Moreover, Table 4 lists the objective function values of the model driven by different optimization directions. The driven directions include the minimum total energy consumption, the optimal solution obtained from the proposed STRA, the median solution, and the minimum total time cost, where the median solution is the average of the 50th and 51st positions in Fig.17. These schemes help to achieve specific decision objectives for resource discovery, such as time cost only, system energy only, and both time cost and system energy. In the bi-level programming model, the median solution of the upper and lower-level objectives represents the trade-off solution of the two objectives. From a computational perspective, the median solution represents a more desirable optimization. In addition, the optimal solution obtained in this paper based on the STRA is closer to the median solution, which initially verifies the effectiveness and feasibility of the algorithm.

Figure  17.  Game-driven bi-level objectives in the resource discovery model.

DownLoad: Full-Size Img PowerPoint

Table  4.  The objective function values of the model under different optimization directions

Optimization directions	EC			TC			# nodes
	Total	AM	SM	Total	AM	SM
Min. TEC	107.83	79.04	28.79	85.25	32.91	52.34	51
Optimal solution	298.07	208.49	89.58	53.68	27.24	26.44	54
Median solution	305.77	234.13	71.64	53.63	21.22	32.41	49
Min. TTC1	497.48	344.65	152.83	14.41	8.24	6.17	53
Note: 1 TTC: (Total) time cost.

 | Show Table

DownLoad: CSV

To further verify the accuracy and computational efficiency of STRA, we introduce the tabu search algorithm (TSA) [19], which is similar to the trust region algorithm, to perform the computation under the same conditions and compare the results, as shown in Table 5. Considering the objective function, STRA outperforms TSA in terms of total energy consumption and total time cost. STRA achieves higher computational accuracy. In terms of efficiency, the number of convergence iterations and computing time of STRA are significantly lower than those of TSA, that is, STRA is more efficient for solving network optimization problems under polymorphic migration. In addition, compared with TSA, STRA has a smaller gap in the difficulty of obtaining the initial solution. The reason is that i) the system model is a bi-level programming model; ii) the coupling effect between decision variables is obvious; and iii) the construction of the symmetric trust domain in the initial stage is relatively complicated, which leads to a stochastic limitation of the initial solution in the iteration.

Table  5.  Comparison of STRA, TSA and meta-heuristic algorithms

Algorithms	TEC	TCC	Convergence iterations	Computing time (s)	Time for initial solution (s)
STRA	298.07	53.68	424	3955	408.55
TSA	314.82	61.44	562	5049	396.85
GA1	327.45	70.29	403	3764	412.37
SAA2	341.26	73.02	411	3850	427.19
PSO3	329.93	76.63	428	4014	422.52
ACO4	345.78	80.39	433	4195	410.20
Note: 1 GA: genetic algorithm; 2 SAA: simulated annealing algorithm; 3 PSO: particle swarm optimization; 4 ACO: ant colony optimization.

 | Show Table

DownLoad: CSV

In addition, compared with meta-heuristic algorithms (GA, SAA, PSO, ACO), STRA has significant advantages regarding the objective function (i.e., higher computational accuracy). But STRA does not perform better in terms of convergence iterations and computing time. This is related to the convergence rules of the algorithm. In terms of the computing time for initial solution, STRA outperforms meta-heuristic algorithms. This is because the complex encoding rules of the meta-heuristic algorithm in this model lead to difficulties in obtaining the initial solution.

In order to analyze the adaptability of the resource discovery model for network polymorphic migration, we adjust the range of increase and decrease of the total number of nodes in the network. The simulation of the whole process is implemented for the networks containing different numbers of nodes. The corresponding results are shown in Table 6. It can be seen that the energy and time costs for different resource discovery modes are less affected by the increase or decrease of the limitation of the number of nodes in the network. The total number of nodes in the network does not show a significant correlation with the magnitude of the limitation. The reason for this is that the dispersed computing network has a strong ad hoc characteristic in the resource discovery process, that is, the QAN and GCNs can interchange roles freely and the physical connection between nodes is characterized by a high degree of freedom in terms of probability.

Table  6.  The effect of the limitation of the total number of nodes in the network on the optimization process

Range	EC			TC			# nodes
	Total	AM	SM	Total	AM	SM
50$\pm$10%	298.07	208.49	89.58	53.68	27.24	26.44	54
50$\pm$20%	335.09	234.38	100.71	60.35	30.63	29.72	58
50$\pm$30%	250.22	175.01	75.20	45.06	22.89	22.19	40
50$\pm$40%	368.63	257.84	110.79	66.39	33.69	32.70	66
50$\pm$50%	267.98	187.44	80.54	48.26	24.49	23.77	45
50$\pm$60%	236.98	165.76	71.22	42.68	21.66	21.02	37
50$\pm$70%	354.56	247.99	106.57	63.85	32.41	31.45	63
50$\pm$80%	313.96	219.60	94.36	56.54	28.70	27.85	56
50$\pm$90%	404.72	283.08	121.64	72.89	36.99	35.90	78

 | Show Table

DownLoad: CSV

To verify the reasonability and practicability of the model and parameters, a sensitivity analysis of the lower bound constraints $Q_{i\_agent}^{(k)(m)}$ and $Q_{i\_self}^{(k)(m)}$ on the expected value of RIS under different modes is conducted. As shown in Figs.18 and 19, when resource discovery runs in the agent mode, the total energy consumption gradually increases and the total time cost decreases as $Q_{i\_agent}^{(k)(m)}$ increases. The reason is that as the lower limit of the expected value of the RIS increases, the difficulty of running the agent mode gradually increases. As the driving effect of the optimization objective in the lower-level model gradually weakens, the driving direction of the time cost in the upper-level model becomes more obvious. As shown in Figs.20 and 21, there is no obvious pattern in the change of total energy consumption and total time cost with increasing $Q_{i\_self}^{(k)(m)}$ in the self-directed mode of resource discovery. As the lower bound of the constraint on the expected value of the RIS increases, the difficulty of running the self-directed mode increases. While the effect of the optimization objective in the lower-level model becomes weaker, the time cost in the upper-level model still does not show a significant driving effect due to its low correlation with the self-directed mode.

Figure  18.  Sensitivity analysis of lower bound of RIS expected value under agent mode on total energy consumption.

DownLoad: Full-Size Img PowerPoint

Figure  19.  Sensitivity analysis of lower bound of RIS expected value under agent mode on total time cost.

DownLoad: Full-Size Img PowerPoint

Figure  20.  Sensitivity analysis of lower bound of RIS expected value under self-directed mode on total energy consumption.

DownLoad: Full-Size Img PowerPoint

Figure  21.  Sensitivity analysis of lower bound of RIS expected value under self-directed mode on total time cost.

DownLoad: Full-Size Img PowerPoint

In the process of resource discovery, $\Delta t_{2}$ in agent mode is the time interval between two consecutive updates of the information status of a resource on a single NCP. This parameter intuitively indicates the frequency of information updates in agent mode, which indirectly affects the accuracy of resource discovery. Figs.22 and 23 show the sensitivity results of $\Delta t_{2}$ for the objective function values, where Fig.22 shows the effect on the energy consumption and Fig.23 shows the effect on the time cost. On the one hand, it can be seen that with the increase of $\Delta t_{2}$, energy consumption in the agent mode decreases, while the overall trend of energy consumption in the autonomous mode does not change significantly, so the total energy consumption also decreases. The reason for this is that when $\Delta t_{2}$ increases (i.e., the frequency of resource information updates decreases), the energy consumption in the agent mode decreases due to fewer updates. The self-directed mode is not affected by $\Delta t_{2}$, and thus its energy consumption does not change much. The increase in total energy consumption is mainly affected by the energy consumption in the self-directed mode. On the other hand, as $\Delta t_{2}$ increases, the time cost in the agent mode increases, the time cost in the self-directed mode fluctuates insignificantly, and the total time cost gradually increases. The reason for this is that when $\Delta t_{2}$ increases (i.e., the frequency of resource information updates decreases), the objective function value of the lower-level model in the agent mode decreases (i.e., energy consumption decreases) and the objective function value of the upper-level model increases (i.e., time cost increases) due to the mutual constraints of optimization. Moreover, the time cost in the self-directed mode is not affected by $\Delta t_{2}$, while the total time cost increases with the increase of time cost in the agent mode.

Figure  22.  Sensitivity analysis of the time intervals of resource information update in the agent mode on total energy consumption.

DownLoad: Full-Size Img PowerPoint

Figure  23.  Sensitivity analysis of the time intervals of resource information update in the agent mode on total time cost.

DownLoad: Full-Size Img PowerPoint

VI.   Conclusions

In this paper, we propose a dispersed computing resource discovery model based on polymorphic migration networks. The model explores reasonable network structures for resource discovery and dynamically selects resource discovery modes driven by the time cost, energy consumption, and the accuracy of information acquisition. The feasibility of the dispersed computing network to maintain multi-site data transfer and collaborative retrieval of multiple types of resources under polymorphic migration is demonstrated through the features of complex network topology. Through an integrative approach, the calibration of energy consumption in both discovery modes is achieved. In addition, we propose a heuristic algorithm based on the symmetric trust region, which is capable of fast convergence vertically and easy to nest the results of energy consumption optimization in the lower-level model. Finally, numerical simulation results show the feasibility of the model and the effectiveness of the algorithm.