Digital Twins are softwarized mirrors of physical systems. They can represent their corresponding physical counterparts in real-world applications and reflect the behavior of the latter under different scenarios with decent accuracy. In this thesis, we consider the case where an application requests data from multiple digital twins, each representing a physical system. The digital twins are hosted on execution servers located between the application and the set of physical devices. Each digital twin has to be periodically updated by its physical system and uses a portion of the execution server’s computing resource to refresh itself. Due to the scarcity of computation resources of the execution servers, in this thesis, we have tackled the problem of optimal digital twin placement onto a limited set of execution servers. We are aiming at minimizing the latency of the digital twins’ responses to the application’s requests while keeping the age of information of served data below a certain threshold. We first formulate the problem as an integer quadratic program (IQP) and then transform it into a semidefinite program (SDP). We prove that the problem is NP-complete and propose polynomial-time approximation algorithms that solve the problem with different trade-offs between the accommodation of the application’s request latency and the achievement of data age targets. / Thesis / Master of Applied Science (MASc)

Digital Twins (DTs) are software representations of physical systems (PSs) that interact with other entities on behalf of their real-world counterparts. To ensure accurate representation and effective interaction, DTs must remain synchronized with their PSs through timely updates—a process known as DT synchronization. This thesis addresses key challenges related to DT synchronization to optimize performance metrics, including the synchronization period and Age of Information (AoI). In the first part, we address the challenge of optimally placing DTs on execution servers (ESs) to minimize both the data request-response delay experienced by applications and the synchronization period between PSs and their DTs, while satisfying communication and computation constraints. We formulate the DT placement problem in two ways. First, we model it as an integer quadratic program (IQP) aiming to minimize the maximum application response delay subject to maximum data age target constraints at the DTs and the application server. Due to the NP-completeness of the problem, we develop practical polynomial-time approximation algorithms that offer trade-offs between application latency and data age targets. Second, we tackle the Minimum Synchronization Period (MSP) problem by modeling it as a multi-commodity quickest flow evacuation problem, considering synchronization data and processing tasks as network flows with flow dependent edge delays. This innovative approach allows us to use well-established techniques from flow network theory to efficiently find the quickest flow solution. An unsplittable flow rounding procedure ensures that each DT is assigned to a single ES. Simulation results demonstrate the effectiveness of our proposed algorithms in both methods, compared to optimal solutions serving as lower bounds. In the second part, we address DT migration in vehicular systems, where maintaining acceptable AoI is challenging due to high mobility and frequent handoffs between cellular domains. We formulate the optimal initiation time for migrating a vehicle's DT as a Markov decision process, aiming to minimize the time-averaged AoI at the DT. An online optimal migration initiation algorithm is proposed using dynamic programming and optimal stopping problem. We also develop a more computationally intensive adaptive version of this algorithm, which recalculates the decision policy at each time step for improved performance. Additionally, we introduce a best-in-expectation algorithm that offers a balance between computational efficiency and AoI performance. These algorithms are compared with heuristic approaches, such as immediate migration and migration at handoff, as well as an offline algorithm providing a theoretical lower bound on the average AoI. Performance evaluations show that our proposed algorithms significantly enhance the efficiency of DT migrations while minimizing the time-averaged AoI compared to other methods. / Dissertation / Candidate in Philosophy / Digital Twins (DTs) are virtual replicas of real-world Physical Systems (PSs), such as mobile devices, vehicles, or smart cities. These digital counterparts are hosted by network servers. They mirror the state and behavior of their physical versions in real time, allowing them to interact with other devices or applications on behalf of their PSs. For a DT to effectively mirror and reflect any changes in its PS, it must consistently remain synchronized through timely updates, which consume the network resources. As a result, the placement of DTs on network servers affects the quality of the DTs. The problem becomes challenging when placing the DTs of a large number of PSs, and is further complicated when the PSs are mobile. This thesis tackles some key challenges towards optimal DT placements. \begin{enumerate} \item Optimizing Synchronization Timing and Placement: We investigate how to optimally place DTs within the network infrastructure to minimize synchronization delay. To achieve this, we develop algorithms that efficiently assign DTs to servers, balancing the need for timely updates, quick application responses, and the amount of network resources. \item Enhancing DT Migration in Vehicular Systems: Vehicles are constantly on the move. Therefor, the PS-DT synchronization delay varies with the PS locations, and at some point, it is better to migrate the DT to a different server. We develop algorithms that decide when to initiate the migration to minimize costs associated with the migration.

Many automotive systems are real-time systems, which means that not only correct operationsbut also appropriate timings are their main requirements. Considering the in uence that end-to-end delay might have on the performance of the systems, the calculation of it is of necessity.Abundant techniques have actually been proposed, and some of them have already been applied intopractical systems. In spite of this, some further work still needs to be done. The target of thisthesis is to evaluate and compare two end-to-end timing analysis methods from dierent aspectssuch as data age, consumption time, and then decide which method is a prior choice for end-to-end timing analysis. The experiments can be divided into three blocks, system generation andend-to-end delay calculation by two methods respectively. The experiments focus on two kinds ofperformance parameters, data age and the consumption time that these two methods cost duringtheir execution. By changing the system generating parameters like task number and periods, thechanges of performances of the two methods are analyzed. The performances of the two dierentmethods are also compared when they are applied into the same automotive systems. According tothe results of the experiments, the second method can calculate more accurate data age and consumeless time than the rst method does.

Many automotive systems are real-time systems, which means that not only correct operationsbut also appropriate timings are their main requirements. Considering the in uence that end-to-end delay might have on the performance of the systems, the calculation of it is of necessity.Abundant techniques have actually been proposed, and some of them have already been applied intopractical systems. In spite of this, some further work still needs to be done. The target of thisthesis is to evaluate and compare two end-to-end timing analysis methods from dierent aspectssuch as data age, consumption time, and then decide which method is a prior choice for end-to-end timing analysis. The experiments can be divided into three blocks, system generation andend-to-end delay calculation by two methods respectively. The experiments focus on two kinds ofperformance parameters, data age and the consumption time that these two methods cost duringtheir execution. By changing the system generating parameters like task number and periods, thechanges of performances of the two methods are analyzed. The performances of the two dierentmethods are also compared when they are applied into the same automotive systems. According tothe results of the experiments, the second method can calculate more accurate data age and consumeless time than the rst method does.