Dynamic Human Digital Twin Deployment at the Edge for Task Execution: A Two-Timescale Accuracy-Aware Online Optimization

Consider an HDT system building upon an end-edge-cloud collaborative framework, as illustrated in Fig. 1, consisting of a set of end users (regarded as PTs) $\mathcal{I}$ with cardinality of $\mid\mathcal{I}\mid=I$, multiple geographically distributed ESs denoted as $\mathcal{M}$ with $\mid\mathcal{M}\mid=M$, and a cloud center (acting as the central controller). PTs (roaming around) generate streams of complex tasks which require the construction of exclusive VT models (forming one-to-one PT-VT pairs) at the edge to assist their task executions. Each VT should be deployed on the ES to which its associated PT may access for offering high-quality and low-delay services. Note that one ES can host multiple VT models for different PTs, and the corresponding communication and computation resources are shared among them. Furthermore, the construction of a high-fidelity VT on the ES consists of two main procedures, i.e., generic model placement and customized model update [26]. For each VT, the generic part of the model is obtained by downloading the experiential knowledge with a selected granularity¹¹1Selecting a large (small) granularity of experiential knowledge for generic model placement may increase (decrease) the fidelity of the VT model, while also introducing a large (small) amount of data to be transferred, resulting in high (low) service delay and energy consumption. from the cloud center, and the target ES for its placement is determined following the access selection of the associated PT. By contrast, the customized part of each VT model is updated by uploading the personalized data with an optimized data size²²2The required size of personalized data for customized model update affects not only the fidelity of the VT model, but also the uplink communication and computation resource allocations among different PT-VT pairs and between their data transmission and task offloading. obtained from sensors worn on the associated PT. After VT establishment, PTs’ tasks can be either transmitted (offloaded) to VTs deployed on the ES or processed locally, depending on the demands of task execution accuracy versus the requirements of service delay and energy consumptions. It is worth noting that although VT models are not able to be built locally, PTs’ tasks can be executed by running offline service applications pre-installed on PTs, which are much less powerful but do not require to be real-time updated.

In practice, the dynamic placement of generic VT model and ES access handover of each PT commonly happen in a low frequency (i.e., over a large-timescale)³³3Particularly, frequently downloading experiential knowledge and switching access points can lead to large configuration costs, including the dramatic increase of delays and energy consumptions [5]., while the update of customized VT models and task offloading together with corresponding communication and computation resource allocations require immediate and frequent adaptation to accommodate the status variation of PT and its task generations [2]. To this end, we define that in the considered online optimization framework, the access selection of each PT and the granularity of experiential knowledge for its generic VT model placement are decided in the large-timescale, while the amount of personalized data for its customized VT model update, task offloading, communication and computation resource allocations are decided in the small-timescale, as shown in Fig. 2. Specifically, the timeline is segmented into $T\in\mathbb{N}^{+}$ coarse-grained time frames, and each frame can be further divided into a combination of $K\in\mathbb{N}^{+}$ fine-grained time slots. Let $t\in\mathcal{T}=\{0,1,\ldots,T-1\}$ be the index of the $t$-th time frame, and define $\tau\in\mathcal{T}_{t}=\{tK,tK+1,\ldots,tK+K-1\}$ as the index of the $\tau$-th time slot in the $t$-th time frame.

Overall speaking, we target to optimize the long-term system performance (i.e., the average accuracy of complex task execution assisted by HDT under stringent delay and energy consumption constraints) by determining i) which ES should be selected to access for each PT and what level of granularity of the experiential knowledge should be chosen for placing its generic VT model on the ES in each time frame, and ii) how large the personalized data is required for updating the customized part of each VT model and whether the task of each PT should be processed locally or on the ES (deployed with its associated VT) together with communication and computation resource allocations in each time slot, in an online manner. For convenience, all important notations in this paper are listed in Table I.

Since PTs are mobile, to construct VT for each of them at the network edge so as to enable seamless PT-VT interactions, the generic VT model should be re-displaced on the ES that its associated PT switches its access to in each time frame $t\in\mathcal{T}$. Denote $a_{i,m}(t)\in\{0,1\}$ as the access selection decision in the large-timescale indicating whether PT $i\in\mathcal{I}$ selects to access ES $m\in\mathcal{M}$ or not in time frame $t\in\mathcal{T}$, i.e., $a_{i,m}(t)=1$ if PT $i\in\mathcal{I}$ connects to ES $m\in\mathcal{M}$, and $a_{i,m}(t)=0$ otherwise. Obviously, we should have $\sum_{m\in\mathcal{M}}a_{i,m}(t)\leq 1$, meaning that PT $i$ cannot access multiple ESs simultaneously [16]. For each PT $i\in\mathcal{I}$, its generic VT model is placed on the accessed ES by downloading a certain granularity of experiential knowledge from the cloud center. We define that the full experiential knowledge of each PT $i\in\mathcal{I}$ for its generic VT model placement has a total size of $D_{i}(t)$, and denote $x_{i}(t)\in[0,1]$ as its decision of granularity in time frame $t\in\mathcal{T}$. Then, the data size of downloading the experiential knowledge for placing PT $i$’s VT model in time frame $t\in\mathcal{T}$ can be represented as $x_{i}(t)D_{i}(t)$. Based on these, the corresponding delay and energy consumption of downloading such experiential knowledge can be respectively expressed as⁴⁴4Note that even for a special case that PT $i$’s access selection remains unchanged, it is still necessary to periodically replace its generic VT model on the same ES, because the experiential knowledge may experience “data drift” over the time [27].

where $r^{c}$ and $p^{c}$ stand for the downlink transmission rate and unit transmission power from the cloud center to each ES, respectively, which are both considered as constants [25], [28].

To exploit this experiential knowledge, each ES has to allocate a proportion of its computation resource for completing the generic VT model placement at the beginning of each time frame. The delay of doing this for PT $i\in\mathcal{I}$ on ES $m\in\mathcal{M}$ in time frame $t\in\mathcal{T}$ can be calculated as

where $C_{m}$ is the number of CPU cycles required for ES $m$ to process a unit of data, $F_{m}$ is the CPU speed (measured by cycles/s) of ES $m$, and $f_{i}(tK)\in(0,1]$ represents the ratio of computation resource allocated to PT $i$ for its VT construction at the beginning of time frame $t$ (i.e., the first time slot of the frame with $\tau=tK$). Referring to the energy model widely used in CMOS circuits[29], the energy consumption of constructing the generic VT model of the associated PT $i\in\mathcal{I}$ on the ES $m\in\mathcal{M}$ in each time frame $t\in\mathcal{T}$ can be calculated as

where $\rho_{m}$ is the effective switched capacitance of ES $m$ depending on its chip architecture.

Since PTs are personalized and their status may vary frequently due to uncertain external or internal factors, to guarantee the timeliness and high-fidelity of VTs on ESs, the customized VT model of each PT should be updated in each time slot $\tau\in\mathcal{T}_{t}$. Let $S_{i}(\tau)$ be the total amount of personalized data generated by PT $i\in\mathcal{I}$, and define $y_{i}(\tau)\in[0,1]$ as the percentage of personalized data chosen to be uploaded in time slot $\tau\in\mathcal{T}_{t}$. Then, the size of personalized data uploaded for updating PT $i$’s customized VT model in time slot $\tau\in\mathcal{T}_{t}$ can be expressed as $y_{i}(\tau)S_{i}(\tau)$.

Within each time slot $\tau\in\mathcal{T}_{t}$, we denote the location of PT $i\in\mathcal{I}$ as $(x_{i}(\tau),y_{i}(\tau))$, which is a state information following its random mobility pattern, and let $(x_{m},y_{m})$ be the fixed location of each ES $m\in\mathcal{M}$. The distance between any PT $i\in\mathcal{I}$ and ES $m\in\mathcal{M}$ can then be calculated as $S_{i,m}(\tau)=\sqrt{\left(x_{i}(\tau)-x_{m}\right)^{2}+\left(y_{i}(\tau)-y_{m}\right)^{2}}$, and according to Shannon-Hartley formula, the transmission rate from PT $i\in\mathcal{I}$ to its accessed ES $m\in\mathcal{M}$ is written as

where $b_{i}(\tau)\in(0,1]$ is the proportion of communication resource allocated to PT $i\in\mathcal{I}$ in time slot $\tau\in\mathcal{T}_{t}$, $h_{i,m}(\tau)$ is the fading amplitude between PT $i\in\mathcal{I}$ and ES $m\in\mathcal{M}$ in time slot $\tau\in\mathcal{T}_{t}$ (modeled as a circularly symmetric complex Gaussian random variable [30]), $B_{m}$ is the communication bandwidth of ES $m\in\mathcal{M}$, $N_{0}$ is the spectral density of the channel noise power, $p_{i}$ is the pre-determined transmission power of PT $i\in\mathcal{I}$, and $\theta\geq 2$ is the path loss exponent [30]. Correspondingly, the delay and energy consumption of PT $i\in\mathcal{I}$ in uploading the personalized data with size $y_{i}(\tau)S_{i}(\tau)$ for updating its VT on ES $m\in\mathcal{M}$ in each time slot $\tau\in\mathcal{T}_{t}$ can be respectively expressed as

To utilize this personalized data, each ES has to allocate a proportion of its computation resource for completing the customized VT model update in each time slot. The delay of doing this for PT $i\in\mathcal{I}$ on ES $m\in\mathcal{M}$ in time slot $\tau\in\mathcal{T}_{t}$ can be calculated as

where $f_{i}(\tau)\in(0,1]$ indicates the proportion of computation resource allocated to PT $i$ for its VT update in each time slot $\tau\in[tK,tK+K-1]$. Besides, the corresponding energy consumption can be calculated as

Let $\lambda_{i}(\tau)$ be the data size of the complex task produced by PT $i\in\mathcal{I}$ in each time slot $\tau\in\mathcal{T}_{t}$, which is allowed to follow a general random distribution. Denote the task offloading decision of PT $i\in\mathcal{I}$ in time slot $\tau\in\mathcal{T}_{t}$ as $z_{i}(\tau)\in\{0,1\}$, i.e., $z_{i}(\tau)=1$ if PT $i$ offloads the task to its VT on the ES for assistance, and $z_{i}(\tau)=0$ if PT $i$ processes it locally. The delay and energy consumption of offloading/transmitting such task from PT $i\in\mathcal{I}$ to its associated VT deployed on the ES $m\in\mathcal{M}$ in time slot $\tau\in\mathcal{T}_{t}$ can be respectively expressed as

Considering the possibility of both edge and local processing, the delay of HDT-assisted task execution of PT $i\in\mathcal{I}$ in time slot $\tau\in\mathcal{T}_{t}$ can be calculated as

where $C_{i}$ is the number of CPU cycles required for PT $i$ to locally process a unit of data, and $F_{i}$ denotes its CPU speed (measured by cycles/s). Besides, the corresponding energy consumption can be calculated as

With the help of HDT at the edge, the accuracy of executing each task from PT $i\in\mathcal{I}$ in each time slot $\tau\in\mathcal{T}_{t}$ can be defined as

where $g_{i}^{local}$ represents the task execution accuracy of local processing on PT $i$ itself, and $g_{i}^{edge}(d_{i}(\tau))$ stands for the task execution accuracy of edge computing for PT $i$ depending on the total size of data used for its VT construction, i.e., $d_{i}(\tau)=x_{i}(t)D_{i}(t)+y_{i}(\tau)S_{i}(\tau),\forall\tau\in\mathcal{T}_{t},\forall t\in\mathcal{T}$, consisting of both experiential knowledge for generic VT model placement in the large-timescale and personalized data for customized VT model update in the small-timescale. Note that $g_{i}^{edge}(d_{i}(\tau))$ is a mapping function that can be obtained via empirical studies or experiments [31].

Similar to [29], [32], we ignore overheads induced by computing outcomes feedback and system control signals. This is because the size of computing outcomes and control signals are much smaller than that of the input data. Technically, these overheads can be seen as small constants [33], which will not affect our analyses.

In summary, the total response delay for all tasks of PT $i\in\mathcal{I}$ in each time frame $t\in\mathcal{T}$ can be derived as

and the system overall energy consumption in each time frame $t\in\mathcal{T}$ can be derived as

To evaluate the core value of building HDT at the network edge, we take the long-term average accuracy of complex task execution assisted by the considered end-edge-cloud collaborative HDT system over all time frames as the performance measurement, which can be expressed as

With the objective of maximizing $\mathcal{A}$ while ensuring that the response delay for all tasks of each PT $i\in\mathcal{I}$ and the overall system energy consumption do not exceed certain thresholds, we formulate a two-timescale online optimization problem by jointly optimizing $a_{i,m}(t)$ and $x_{i}(t)$, denoted in short by a set of large-timescale decision variables $\mathcal{J}_{i}^{A}(t)=\{a_{i,m}(t),x_{i}(t)\}$, for each PT $i$ in any time frame $t\in\mathcal{T}$, and $y_{i}(\tau)$, $b_{i}(\tau)$, $f_{i}(\tau)$ and $z_{i}(\tau)$, denoted in short by a set of small-timescale decision variables $\mathcal{J}_{i}^{B}(\tau)=\{b_{i}(\tau),y_{i}(\tau),f_{i}(\tau),z_{i}(\tau)\}$, for each PT $i$ in any time slot $\tau\in\mathcal{T}_{t}$.

Mathematically, such a two-timescale online optimization problem can be formulated as

where constraint (18a) guarantees that one PT can connect to at most one ES in each time frame $t\in\mathcal{T}$; constraints (18b) and (18c) restrict that the communication and computation resource allocation should be less than the total capacities of each ES in any time slot $\tau\in\mathcal{T}_{t}$; constraints (18d) and (18e) are the long-term average task response delay and system overall energy consumption constraints (in which $T_{i}^{max}$ and $E^{max}$ represent the pre-determined response delay threshold of each PT $i\in\mathcal{I}$ and the overall system energy consumption threshold, respectively).

Obviously, solving problem $\mathcal{P}_{1}$ directly is very challenging because $i)$ PTs’ mobilities and status variations, due to human-related characteristics, are highly unpredictable, meaning that it is extremely hard, if not impossible, to obtain system statistics in advance, which necessitates the design of an online optimization algorithm; $ii)$ although Lyapunov optimization [34] is well-known as an effective method to solve such an online problem in general, decision variables in different timescales (i.e., $\mathcal{J}_{i}^{A}(t)$ and $\mathcal{J}_{i}^{B}(\tau)$) are tightly coupled in not only the objective function but also constraints (18d) and (18e); and $iii)$ all constraints include discrete decision variables (i.e., $a_{i,m}(t)$ or $z_{i}(\tau)$), and constraints (18d) and (18e) are both non-convex. These indicate that $\mathcal{P}_{1}$ is a two-timescale online non-convex mixed integer programming problem, which must be NP-hard.

Observed from problem $\mathcal{P}_{1}$ that the delay and energy consumptions caused by the generic VT model placement are on the large-timescale, while those caused by customized VT model update and task execution are on the small-timescale. To facilitate the solution, we evenly distribute the task response delay and system overall energy consumption in each time frame $t\in\mathcal{T}$ into all $\mid\mathcal{T}_{t}\mid=K$ time slots within this frame, which yields

Substituting (19) and (4.1) into (18d) and (18e) of problem $\mathcal{P}_{1}$, we have

Note that the reformulated problem $\mathcal{P}_{2}$ is equivalent to the original problem $\mathcal{P}_{1}$ with exactly the same decision variables remaining in two different timescales, while all long-term constraints have been unified into a single timescale (i.e., in terms of the time slot only) but will not affect the optimization performance.

Obviously, $\mathcal{P}_{2}$ is still a long-term optimization problem, and the major difficulties for solving it are i) how to address the long-term average delay and energy consumption constraints; and ii) how to optimize two-timescale decision variables simultaneously. To this end, in the next subsection, we employ the Lyapunov method [34], and reformulate $\mathcal{P}_{2}$ to accommodate the two-timescale features.

We first define a delay overflow queue and an energy deficit queue to respectively describe how task response delay $T_{i}^{tol}(\tau)$ of each PT $i\in\mathcal{I}$ and the overall system energy consumption $E^{tol}(\tau)$ in time slot $\tau\in\mathcal{T}_{t}$ may deviate from the long-term budget $T_{i}^{max}/K$ and $E^{max}/K$. The dynamic evolution of these two queues can be expressed as

After that, we combine the delay overflow queue $H_{i}(\tau)$ for all tasks of PTs and energy deficit queue $E^{tol}(\tau)$ by a vector as $\bm{\Theta}(\tau)=[\bm{H}(\tau),E(\tau)]$, and introduce a quadratic Lyapunov function as [34]:

which quantitatively reflects the congestion of all queues, and should be persistently pushed towards a minimum value to keep queue stabilities. Referring to [35], the conditional Lyapunov drift is given by

where $\mathbb{E}[\cdot]$ denotes the expectation, and $\Delta(\bm{\Theta}(\tau))$ measures the difference of the Lyapunov function between $K$ consecutive time slots. Intuitively, by minimizing the Lyapunov drift in (25), we can prevent queue backlogs from the unbounded growth, and thus guarantee that the desired delay and energy consumption constraints can be met.

Accordingly, the Lyapunov drift-plus-penalty function becomes

where a control parameter $V>0$ is introduced, representing the weight of significance on maximizing the HDT-assisted task execution accuracy versus that of strictly satisfying the delay and energy consumption constraints.

Theorem 1 shows that the drift-plus-penalty is deterministically upper bounded in each time slot $\tau\in\mathcal{T}_{t}$. Then, taking the sum over all time slots within time frame $t$ for both sides of (27), we have

Then, $\mathcal{P}_{2}$ can be decomposed into multiple subproblems, each of which opportunistically minimize the right-hand-side of (4.2) in one time frame $t\in\mathcal{T}$, i.e.,

Note that, in problem $\mathcal{P}_{3}$, decisions $\mathcal{J}_{i}^{A}(t)=\{a_{i,m}(t),x_{i}(t)\}$ and $\mathcal{J}_{i}^{B}(\tau)=\{b_{i}(\tau),y_{i}(\tau),f_{i}(\tau),z_{i}(\tau)\}$ remain unchanged as those in $\mathcal{P}_{3}$. This means that, although $\mathcal{P}_{3}$ focuses on the optimization in a single time frame, it still includes two-timescale variables.